8 ms·

MMU gang wars: the TLB drive-by shootdown

163 points by matt_d 6y ago

joe_the_user 6y ago
Every once in a while I get involuntarily dragged into heated debates about whether reusing memory is better for performance than freeing it. I couldn't comment on all the instances the article talks about. But this way of asking the question seems to me to hide the problem. It seems simpler to say "what memory allocation algorithm should you use?" Which is to say, "does your knowledge of your application's memory needs and memory performance trump all the effort and knowledge that went into creating the memory allocator of the operating system you're using?". And so then you get into the massive number of technical considerations the article and others might raise. Memory allocation is a weird thing, it's an algorithm but it's often taken as a given in programming languages and discussions of algorithms.
- bitcharmer 6y ago
  Hi, author here. I'm not sure if I follow your argument. This article doesn't touch on allocators at all (ie. SLUB vs SLAB). It focuses solely on the cost of freeing memory which TLB-shootdowns are a notable part of. I even mention it at the beginning: > Regardless of the method by which your program acquired memory there are side effects of freeing/reclaiming it. This post focuses on the impact of so called TLB-shootdowns. Hope this helps.
  - joe_the_user 6y ago
    As I understand things, allocating and freeing memory pretty much forms a single system. Especially, if I have a system where I "manually" allocate 10 meg for my use, never free it but use an internal method to mark the memory free or used, I will still have issues with caching and virtual memory based on my use of the memory. IE, reusing memory effectively creating a "roll your own" free and allocate functions. And in general, how contiguously you allocate memory plays a big part in whether freed memory can be easily discarded from the cache. If you get the heap to be exactly like a stack, then the cache shouldn't have problems. But I'll admit I'm not an expert and I could be missing something.
    - rocqua 6y ago
      This article isn't so much about free-ing, but about unmapping memory. It could well be that you have an allocator that decides not to un-map free-ed memory so that it can quickly be re-used later. That said, as per https://linux.die.net/man/3/malloc https://linux.die.net/man/3/malloc (and the article) the default implementation of free will (in some cases) unmap memory. It is this un-mapping of memory that causes other threads to be affected. Because those threads should get a seg-fault after the unmapping if they try to access that memory.
- deleted 6y ago
  [deleted]
- userbinator 6y ago
  Which is to say, "does your knowledge of your application's memory needs and memory performance trump all the effort and knowledge that went into creating the memory allocator of the operating system you're using?". The OS's memory allocator will likely be optimised for good all-round performance on some benchmark which may or may not be representative of your application.
  - teknopaul 6y ago
    Re: "does your knowledge of your application's memory needs and memory performance trump all the effort and knowledge that went into creating the memory allocator of the operating system you're using?". Almost always. You can almost always answer the question "am I going to need memory again after this free()". If memory is tied to a request or some other object you almost always know that. You can almost always make a good guess at how much data a repeated operation will need, thus how much memory to reuse. You almost always know the benefit of caching data in memory that is otherwise on disk. Often the OS is better at this than the developer thinks! You almost always know if data is likely to be needed in memory again. When you free() you lose the space and the data. Quite often you can benefit from a managed free() that you can ask for the memory again still populated if nothing else needed the space it in the end. You almost always know the security concequences of reusing memory. e.g. the OS cannot tell if calloc or malloc is needed. Secure(ish) allocators are a thing. You almost always know if a memory block might grow or is fixed size. You almost always know when you need an i/o buffer that can be reused. You almost always know if smart pointers are beneficial or not. In C its perfectly normal to allocate on the stack rather than the heap because you know better than malloc(). You often know more than the allocator about memory alignment. I think you could almost always do better than the OS allocator when writing servers. I'd agree its often not worth the effort. Unless you are writing lots of C. free() is such a pain. You can almost always write better, safer, faster memory allocators than ad hoc use of malloc() and free().
brandmeyer 6y ago
This whole rigmarole is necessary for a single reason: TLBs don't participate in the cache coherency system. Uh, why is that? If they did participate, then the mere act of writing to the cache line(s) which change the mapping would implicitly invalidate all of the associated entries in all of the system's TLBs. (Handwave, handwave), maybe you still end up needing a barrier similar to the instruction barrier needed when altering the content of executable pages. What's the downside? Is it just power? Or is there something more fundamental about the TLB structure that makes it impractical?
- ip26 6y ago
  I would love to hear from someone with the real answer but I've always assumed it is legacy baggage from the old days. The impact on performance has probably never been big enough to compel the entire x86 ecosystem to make them coherent.
  - monocasa 6y ago
    I imagine it's because the hardware doesn't have enough context to know which virtual address spaces exist in which cores' TLBs. ASIDs were only added in the virtualization instructions on x86, and I can't think of an OS where those are the same namespace across cores. A side reason is that it'd probably heavily complicate the top level TLBs to have "please flush yourself" coming from anywhere other than the core they're attached to, and those are in the critical path between L1 and L2. Totally spitballing here FWIW, I haven't been part of the design process for a TLB.
- eqvinox 6y ago
  I'm guessing what you mean is for the TLB to get a notification when the physical memory that contains the page mapping it was loaded from is changed. (As opposed to, some weird contortion the other way around where you touch the cache for the mapping that got changed.) It'd probably require holding the cacheline for the TLB entry in the actual cache in at least MESI "S" state. For 5 levels of page tables. And you can't do non-flushing changes (e.g. dirty bit) anymore. I'm no CPU designer but it sounds complicated and bug prone...
eqvinox 6y ago
There is a very glaring omission (or call it gloss-over) in this article - whether and when a free() even causes the allocator to actually release memory to the OS. JVMs are kinda famous for their "om nom nom" attitude on this, but you can't transfer from ptmalloc (glibc, whose man page is cited regarding >=128k mmap) to tcmalloc and jemalloc. Also, on Linux, an allocator may use madvise(MADV_FREE) instead of munmap(); this tells the kernel that the data in a page is no longer needed but can be unmapped at the kernel's discretion, possibly even at different times for different threads (e.g. when doing a task switch for an unrelated reason.) [EDIT: this doesn't actually work, see below. Sorry.]
- kentonv 6y ago
  IIRC MADV_FREE doesn't actually let the kernel avoid shootdowns. From the man page (http://man7.org/linux/man-pages/man2/madvise.2.html http://man7.org/linux/man-pages/man2/madvise.2.html): MADV_FREE (since Linux 4.5) The application no longer requires the pages in the range specified by addr and len. The kernel can thus free these pages, but the freeing could be delayed until memory pressure occurs. For each of the pages that has been marked to be freed but has not yet been freed, the free operation will be canceled if the caller writes into the page. (...) The problem is with this bit about a write to the page canceling the free... This side effect needs to be implemented in a page fault. But if the page is still in the TLB, then writes to it won't fault. So... you need a TLB shootdown. :( I do wonder why there isn't an API for "lazy munmap()"... it would behave exactly like munmap(), except that the pages might remain accessible in other threads until the end of their timeslices, when the kernel can apply queued TLB flushes. It seems to me likely that 99.9% of uses of munmap() could be switched to this lazy operation without introducing any bugs. I'm not a kernel programmer, though. Maybe there's some reason this doesn't work, or maybe the performance improvements aren't worth the effort?
  - eqvinox 6y ago
    > The problem is with this bit about a write to the page canceling the free... This side effect needs to be implemented in a page fault. On some architectures, yes, but x86 has the dirty bit in the PTE for this; if it's cleared you're out easy (but that's unlikely); if it's already set I honestly don't know how costly it is to clear. You don't necessarily need to shoot the TLB on other CPUs though since the mapping is still valid; if there is some easier way to get the D flag cleared you can use that. > But if the page is still in the TLB, then writes to it won't fault. They can, a TLB entry has the full range of PTE flags to work with, e.g. a page may be flagged read-only for the kernel to do copy-on-write handling. I have no clue how exactly the dirty flag is set though :/ — I only know the function is indeed provided by the MMU itself, not a page fault.
ncmncm 6y ago
All of this is moot if you have only the one thread. If you need parallelism, and can afford its complexity, separate processes sharing only what must be shared can eliminate your TLB exposure. Single-writer mappings eliminate cache storms. All of this is moot if you allocate all your memory upfront. All of this is moot if you can identify junctures when a stall is free, and cluster your shootdowns at such times.
- adwn 6y ago
  > If you need parallelism, and can afford its complexity, separate processes sharing only what must be shared can eliminate your TLB exposure. Then you need to ensure that all shared data structures are exclusively allocated from a dedicated memory pool which is mapped to all processes. Oh, and you must make sure that you either don't use any pointers within those datastructures, or that the shared memory pool is mapped to the same address in all processes. And no pointers must point from within to outside that memory pool. In theory, it is possible. In practice, this would preclude any kind of non-trivial parallelism.
  - ncmncm 6y ago
    I see that you just haven't done it yet. "Allocation" in this context just means open(), mmap(). A "shared memory pool" is a thing I would have no use for. But I can assure you that you can have excellent, non-trivial parallelism with separate processes and chosen shared memory pages -- much moreso than with threads that must battle one another for access to locks, queues, and "pools". I routinely get order-of-magnitude performance improvement by reorganizing this way. The single-writer ring buffer is the component that makes it all work. The environment might seem stark, but in exchange you can have exactly 0% concurrency overhead. Not wasting 90% on pool management and thread contention means other optimizations become meaningful. And, you can start and stop the processes independently.
lonelappde 6y ago
The title is absolutely obnoxious.
- idoncarfb 6y ago
  That's only if you're devoid of sense of humor.
forrestthewoods 6y ago
The anti-windows nipple rubbing was... weird. And not helpful. As a primarily Windows guy I’d rather just know what, if any, differences there are. =/
- deleted 6y ago
  [deleted]
- pete23 6y ago
  I like the nipple rubbing!
- idoncarfb 6y ago
  Is this the only thing from the article you found worth pointing out? Also, no one here had a problem with that except you. What does it tell you?
  - forrestthewoods 6y ago
    That everyone here uses Linux and MacBooks.
cryptonector 6y ago
Nice write-up. I've long believed that malloc(4192) == mmap() is a very bad idea for this reason -- in fact, let your heap get giant pages, damn it. Also, fork() turns out to be pretty evil. fork() is OK when you're forking worker processes very early in a daemon's life, but for most other uses it's just a very bad idea -- use vfork() or posix_spawn() instead. There are just too many problems with fork(). That paper about vfork() being harmful had it exactly backwards. It is fork() that is harmful. It has safety issues that make using it safely sufficiently hard as to not be worth it in many cases, but the real killer is fork()'s copy semantics, which just kills performance. (A colleague of mine has used fork() in signal handlers to call abort() on the child side as a way of getting core dumps from live processes without killing them. That's pretty neat, and one of the very few uses of fork() I would endorse.)
rawoke083600 6y ago
Awesome article... Extra points for posting on blogger.com :)
7532yahoogmail 6y ago
A hell of a good write up. I learned tons here.

163 points by matt_d 6y ago

Every once in a while I get involuntarily dragged into heated debates about whether reusing memory is better for performance than freeing it. I couldn't comment on all the instances the article talks about. But this way of asking the question seems to me to hide the problem. It seems simpler to say "what memory allocation algorithm should you use?" Which is to say, "does your knowledge of your application's memory needs and memory performance trump all the effort and knowledge that went into creating the memory allocator of the operating system you're using?". And so then you get into the massive number of technical considerations the article and others might raise. Memory allocation is a weird thing, it's an algorithm but it's often taken as a given in programming languages and discussions of algorithms.

bitcharmer 6y ago
Hi, author here. I'm not sure if I follow your argument. This article doesn't touch on allocators at all (ie. SLUB vs SLAB). It focuses solely on the cost of freeing memory which TLB-shootdowns are a notable part of. I even mention it at the beginning: > Regardless of the method by which your program acquired memory there are side effects of freeing/reclaiming it. This post focuses on the impact of so called TLB-shootdowns. Hope this helps.
- joe_the_user 6y ago
  As I understand things, allocating and freeing memory pretty much forms a single system. Especially, if I have a system where I "manually" allocate 10 meg for my use, never free it but use an internal method to mark the memory free or used, I will still have issues with caching and virtual memory based on my use of the memory. IE, reusing memory effectively creating a "roll your own" free and allocate functions. And in general, how contiguously you allocate memory plays a big part in whether freed memory can be easily discarded from the cache. If you get the heap to be exactly like a stack, then the cache shouldn't have problems. But I'll admit I'm not an expert and I could be missing something.
  - rocqua 6y ago
    This article isn't so much about free-ing, but about unmapping memory. It could well be that you have an allocator that decides not to un-map free-ed memory so that it can quickly be re-used later. That said, as per https://linux.die.net/man/3/malloc https://linux.die.net/man/3/malloc (and the article) the default implementation of free will (in some cases) unmap memory. It is this un-mapping of memory that causes other threads to be affected. Because those threads should get a seg-fault after the unmapping if they try to access that memory.
deleted 6y ago
[deleted]
userbinator 6y ago
Which is to say, "does your knowledge of your application's memory needs and memory performance trump all the effort and knowledge that went into creating the memory allocator of the operating system you're using?". The OS's memory allocator will likely be optimised for good all-round performance on some benchmark which may or may not be representative of your application.
- teknopaul 6y ago
  Re: "does your knowledge of your application's memory needs and memory performance trump all the effort and knowledge that went into creating the memory allocator of the operating system you're using?". Almost always. You can almost always answer the question "am I going to need memory again after this free()". If memory is tied to a request or some other object you almost always know that. You can almost always make a good guess at how much data a repeated operation will need, thus how much memory to reuse. You almost always know the benefit of caching data in memory that is otherwise on disk. Often the OS is better at this than the developer thinks! You almost always know if data is likely to be needed in memory again. When you free() you lose the space and the data. Quite often you can benefit from a managed free() that you can ask for the memory again still populated if nothing else needed the space it in the end. You almost always know the security concequences of reusing memory. e.g. the OS cannot tell if calloc or malloc is needed. Secure(ish) allocators are a thing. You almost always know if a memory block might grow or is fixed size. You almost always know when you need an i/o buffer that can be reused. You almost always know if smart pointers are beneficial or not. In C its perfectly normal to allocate on the stack rather than the heap because you know better than malloc(). You often know more than the allocator about memory alignment. I think you could almost always do better than the OS allocator when writing servers. I'd agree its often not worth the effort. Unless you are writing lots of C. free() is such a pain. You can almost always write better, safer, faster memory allocators than ad hoc use of malloc() and free().

brandmeyer 6y ago

This whole rigmarole is necessary for a single reason: TLBs don't participate in the cache coherency system. Uh, why is that? If they did participate, then the mere act of writing to the cache line(s) which change the mapping would implicitly invalidate all of the associated entries in all of the system's TLBs. (Handwave, handwave), maybe you still end up needing a barrier similar to the instruction barrier needed when altering the content of executable pages. What's the downside? Is it just power? Or is there something more fundamental about the TLB structure that makes it impractical?

ip26 6y ago
I would love to hear from someone with the real answer but I've always assumed it is legacy baggage from the old days. The impact on performance has probably never been big enough to compel the entire x86 ecosystem to make them coherent.
- monocasa 6y ago
  I imagine it's because the hardware doesn't have enough context to know which virtual address spaces exist in which cores' TLBs. ASIDs were only added in the virtualization instructions on x86, and I can't think of an OS where those are the same namespace across cores. A side reason is that it'd probably heavily complicate the top level TLBs to have "please flush yourself" coming from anywhere other than the core they're attached to, and those are in the critical path between L1 and L2. Totally spitballing here FWIW, I haven't been part of the design process for a TLB.
eqvinox 6y ago
I'm guessing what you mean is for the TLB to get a notification when the physical memory that contains the page mapping it was loaded from is changed. (As opposed to, some weird contortion the other way around where you touch the cache for the mapping that got changed.) It'd probably require holding the cacheline for the TLB entry in the actual cache in at least MESI "S" state. For 5 levels of page tables. And you can't do non-flushing changes (e.g. dirty bit) anymore. I'm no CPU designer but it sounds complicated and bug prone...

eqvinox 6y ago

There is a very glaring omission (or call it gloss-over) in this article - whether and when a free() even causes the allocator to actually release memory to the OS. JVMs are kinda famous for their "om nom nom" attitude on this, but you can't transfer from ptmalloc (glibc, whose man page is cited regarding >=128k mmap) to tcmalloc and jemalloc. Also, on Linux, an allocator may use madvise(MADV_FREE) instead of munmap(); this tells the kernel that the data in a page is no longer needed but can be unmapped at the kernel's discretion, possibly even at different times for different threads (e.g. when doing a task switch for an unrelated reason.) [EDIT: this doesn't actually work, see below. Sorry.]

kentonv 6y ago
IIRC MADV_FREE doesn't actually let the kernel avoid shootdowns. From the man page (http://man7.org/linux/man-pages/man2/madvise.2.html http://man7.org/linux/man-pages/man2/madvise.2.html): MADV_FREE (since Linux 4.5) The application no longer requires the pages in the range specified by addr and len. The kernel can thus free these pages, but the freeing could be delayed until memory pressure occurs. For each of the pages that has been marked to be freed but has not yet been freed, the free operation will be canceled if the caller writes into the page. (...) The problem is with this bit about a write to the page canceling the free... This side effect needs to be implemented in a page fault. But if the page is still in the TLB, then writes to it won't fault. So... you need a TLB shootdown. :( I do wonder why there isn't an API for "lazy munmap()"... it would behave exactly like munmap(), except that the pages might remain accessible in other threads until the end of their timeslices, when the kernel can apply queued TLB flushes. It seems to me likely that 99.9% of uses of munmap() could be switched to this lazy operation without introducing any bugs. I'm not a kernel programmer, though. Maybe there's some reason this doesn't work, or maybe the performance improvements aren't worth the effort?
- eqvinox 6y ago
  > The problem is with this bit about a write to the page canceling the free... This side effect needs to be implemented in a page fault. On some architectures, yes, but x86 has the dirty bit in the PTE for this; if it's cleared you're out easy (but that's unlikely); if it's already set I honestly don't know how costly it is to clear. You don't necessarily need to shoot the TLB on other CPUs though since the mapping is still valid; if there is some easier way to get the D flag cleared you can use that. > But if the page is still in the TLB, then writes to it won't fault. They can, a TLB entry has the full range of PTE flags to work with, e.g. a page may be flagged read-only for the kernel to do copy-on-write handling. I have no clue how exactly the dirty flag is set though :/ — I only know the function is indeed provided by the MMU itself, not a page fault.

ncmncm 6y ago

All of this is moot if you have only the one thread. If you need parallelism, and can afford its complexity, separate processes sharing only what must be shared can eliminate your TLB exposure. Single-writer mappings eliminate cache storms. All of this is moot if you allocate all your memory upfront. All of this is moot if you can identify junctures when a stall is free, and cluster your shootdowns at such times.

adwn 6y ago
> If you need parallelism, and can afford its complexity, separate processes sharing only what must be shared can eliminate your TLB exposure. Then you need to ensure that all shared data structures are exclusively allocated from a dedicated memory pool which is mapped to all processes. Oh, and you must make sure that you either don't use any pointers within those datastructures, or that the shared memory pool is mapped to the same address in all processes. And no pointers must point from within to outside that memory pool. In theory, it is possible. In practice, this would preclude any kind of non-trivial parallelism.
- ncmncm 6y ago
  I see that you just haven't done it yet. "Allocation" in this context just means open(), mmap(). A "shared memory pool" is a thing I would have no use for. But I can assure you that you can have excellent, non-trivial parallelism with separate processes and chosen shared memory pages -- much moreso than with threads that must battle one another for access to locks, queues, and "pools". I routinely get order-of-magnitude performance improvement by reorganizing this way. The single-writer ring buffer is the component that makes it all work. The environment might seem stark, but in exchange you can have exactly 0% concurrency overhead. Not wasting 90% on pool management and thread contention means other optimizations become meaningful. And, you can start and stop the processes independently.

lonelappde 6y ago

The title is absolutely obnoxious.

idoncarfb 6y ago
That's only if you're devoid of sense of humor.

forrestthewoods 6y ago

The anti-windows nipple rubbing was... weird. And not helpful. As a primarily Windows guy I’d rather just know what, if any, differences there are. =/

deleted 6y ago
[deleted]
pete23 6y ago
I like the nipple rubbing!
idoncarfb 6y ago
Is this the only thing from the article you found worth pointing out? Also, no one here had a problem with that except you. What does it tell you?
- forrestthewoods 6y ago
  That everyone here uses Linux and MacBooks.

cryptonector 6y ago

Nice write-up. I've long believed that malloc(4192) == mmap() is a very bad idea for this reason -- in fact, let your heap get giant pages, damn it. Also, fork() turns out to be pretty evil. fork() is OK when you're forking worker processes very early in a daemon's life, but for most other uses it's just a very bad idea -- use vfork() or posix_spawn() instead. There are just too many problems with fork(). That paper about vfork() being harmful had it exactly backwards. It is fork() that is harmful. It has safety issues that make using it safely sufficiently hard as to not be worth it in many cases, but the real killer is fork()'s copy semantics, which just kills performance. (A colleague of mine has used fork() in signal handlers to call abort() on the child side as a way of getting core dumps from live processes without killing them. That's pretty neat, and one of the very few uses of fork() I would endorse.)

rawoke083600 6y ago

Awesome article... Extra points for posting on blogger.com :)

7532yahoogmail 6y ago

A hell of a good write up. I learned tons here.