4 ms·

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/ma

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.
- kentonv 6y ago
  > if there is some easier way to get the D flag cleared you can use that. Is there though? I didn't know about the dirty bit, so obviously I don't know much about x86 TLB, but I'm having trouble imagining any reasonable implementation where clearing the dirty bit wouldn't itself require a shootdown. Have you seen somewhere claim that MADV_FREE allows avoiding a shootdown? The man page doesn't say that and I am pretty sure I heard before that it does not, but would be very interested to know if that's incorrect.
  - eqvinox 6y ago
    > Have you seen somewhere claim that MADV_FREE allows avoiding a shootdown? I haven't, and after looking at mm/madvise.c [ https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/mm/madvise.c#n700 https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/lin... ] I guess it doesn't. Also, the unmapping happens immediately. MADV_DONTNEED doesn't help either, it also seems to invalidate immediately. That only leaves MADV_REMOVE, which AFAIK doesn't work on anonymous mappings... sigh [Edit: good thing I don't write allocators :D]
  - eqvinox 6y ago
    Intel docs say this on CPU behaviour: https://software.intel.com/content/www/us/en/develop/download/intel-64-and-ia-32-architectures-sdm-combined-volumes-1-2a-2b-2c-2d-3a-3b-3c-3d-and-4.html https://software.intel.com/content/www/us/en/develop/downloa... [4.8 ACCESSED AND DIRTY FLAGS] Memory-management software may clear these flags when a page or a paging structure is initially loaded into physical memory. These flags are “sticky,” meaning that, once set, the processor does not clear them; only software can clear them. A processor may cache information from the paging-structure entries in TLBs and paging-structure caches (see Section 4.10). This fact implies that, if software changes an accessed flag or a dirty flag from 1 to 0, the processor might not set the corresponding bit in memory on a subsequent access using an affected linear address (see Section 4.10.4.3). See Section 4.10.4.2 for how software can ensure that these bits are updated as desired. [4.10.4 Invalidation of TLBs and Paging-Structure Caches] [4.10.4.2 Recommended Invalidation] ... so, I guess, yeah, this doesn't really help :|
zozbot234 6y ago
> 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. You would effectively need to run different address spaces in different threads of the "same" process, which might interoperate badly with whatever guarantees the kernel provides or relies on elsewhere based on the assumption of having a unified address space for the whole process. Though I absolutely agree that this is worthwhile, it probably needs to be designed carefully and can't just transparently replace any and all uses of munmap().
- eqvinox 6y ago
  Hmm - both maps and unmaps are already non-atomic though; there's gonna be some however minor span of time where different CPUs will have different state regarding a page that is being updated. IPIs don't grind the entire system to a halt to guarantee everyone is getting the same update at the same time. I.e. you can already have a syscall on thread A racing against the incoming IPI on thread B's mmap/munmap...
  - new_realist 6y ago
    Sure, but the munmap() won’t return to the caller until the effects are visible in all processors.
    - kentonv 6y ago
      Imagine a program that, instead of calling munmap() directly, spins up a separate thread to call it, with the main thread proceeding on its way. Doesn't such a program today already observe all the weirdness of the page "disappearing" from different threads at different points in time? What difference would there be with a lazy mmap(), except that the window during which these inconsistencies are observable would be longer?
      - new_realist 6y ago
davidtgoldblatt 6y ago
> Maybe there's some reason this doesn't work, or maybe the performance improvements aren't worth the effort? I work on an allocator, and I've lobbied (Linux) kernel people for this over the years. I think everyone mostly agrees it'd be useful (and, the TLB shootdown cost is indeed often nontrivial), but the current architecture of the various subsystem's you'd need to touch makes it hard to do. As allocators move more and more to a hugepages-first world, I think we'll see fewer and fewer benefits from faster unmappings (instead, we'll just spend more effort making sure we fill in the holes in existing in-use ranges).
cyphar 6y ago
> 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. That does exist, it's called MADV_DONTNEED and most operating systems have implemented it. However, MADV_DONTNEED on Linux was incorrectly implemented and (from memory) would always result in the page being unmapped immediately -- making it roughly equivalent to MADV_FREE. To quote the man page: > All of the advice values listed here have analogs in the POSIX-specified posix_madvise(3) function, and the values have the same meanings, with the exception of MADV_DONTNEED.
- comex 6y ago
  After reading that I wondered what happens on Linux if you actually call posix_madvise(POSIX_MADV_DONTNEED). The answer, from glibc: /* We have one problem: the kernel's MADV_DONTNEED does not correspond to POSIX's POSIX_MADV_DONTNEED. The former simply discards changes made to the memory without writing it back to disk, if this would be necessary. The POSIX behavior does not allow this. There is no functionality mapping the POSIX behavior so far so we ignore that advice for now. */ if (advice == POSIX_MADV_DONTNEED) return 0;
- kentonv 6y ago
  AFAICT the POSIX behavior for MADV_DONTNEED is just a hint that the memory won't be accessed soon. https://pubs.opengroup.org/onlinepubs/009695399/functions/posix_madvise.html https://pubs.opengroup.org/onlinepubs/009695399/functions/po... says: POSIX_MADV_DONTNEED Specifies that the application expects that it will not access the specified range in the near future. https://www.freebsd.org/cgi/man.cgi?query=madvise&sektion=2 https://www.freebsd.org/cgi/man.cgi?query=madvise&sektion=2 says: MADV_DONTNEED Allows the VM system to decrease the in-memory priority of pages in the specified address range. Consequently, future references to this address range are more likely to incur a page fault. Neither of these suggest that the contents of the memory content can be discarded (as Linux does), only that it can be swapped out. So it doesn't appear that this provides the "lazy unmap to avoid shootdown" behavior on any OS.
markjdb 6y ago
> I do wonder why there isn't an API for "lazy munmap()" You don't really need a separate API. The kernel can implement munmap() lazily, it just needs to also ensure that the address range isn't reused until a TLB shootdown is completed. LATR is a system that leverages this to implement lazy TLB shootdowns for munmap(): http://www.cs.yale.edu/homes/abhishek/kumar-asplos18.pdf http://www.cs.yale.edu/homes/abhishek/kumar-asplos18.pdf
- BeeOnRope 6y ago
  Wouldn't this break the existing semantics of mmap, which is after the mmap call returns, other threads in the same process will fault if the they access the mapping? Sure, avoiding re-use prevents some types of bugs but not others.
  - londons_explore 6y ago
    Id be interested to know if any program relies on freeing memory in one thread, then (with some lock for synchronization) deliberately accessing it from another thread causing a segfault. Sure, it's possible, but if no programs do it, it might be worth breaking the behaviour for the performance increase.
    - kentonv 6y ago
      If the program is just using mmap/munmap for memory allocation, then I agree with you. But some programs do crazier things. Imagine a program that implements mmap of a file entirely in userspace. For example, say I have a file that's stored on a distributed filesystem that dosen't have kernel drivers. So I catch SIGSEGV in userspace and populate pages on-demand by fetching them from the remote server. Later on, the page hasn't been used in a while, so I munmap() it to reclaim memory. I expect that any further uses after this point (especially writes, which maybe I need to sync back?) will raise a new SIGSEGV which I can handle. I think something like that, unfortunately, could be broken by changing all munmaps to be lazy...
      - 6y ago

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.

kentonv 6y ago
> if there is some easier way to get the D flag cleared you can use that. Is there though? I didn't know about the dirty bit, so obviously I don't know much about x86 TLB, but I'm having trouble imagining any reasonable implementation where clearing the dirty bit wouldn't itself require a shootdown. Have you seen somewhere claim that MADV_FREE allows avoiding a shootdown? The man page doesn't say that and I am pretty sure I heard before that it does not, but would be very interested to know if that's incorrect.
- eqvinox 6y ago
  > Have you seen somewhere claim that MADV_FREE allows avoiding a shootdown? I haven't, and after looking at mm/madvise.c [ https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/mm/madvise.c#n700 https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/lin... ] I guess it doesn't. Also, the unmapping happens immediately. MADV_DONTNEED doesn't help either, it also seems to invalidate immediately. That only leaves MADV_REMOVE, which AFAIK doesn't work on anonymous mappings... sigh [Edit: good thing I don't write allocators :D]
- eqvinox 6y ago
  Intel docs say this on CPU behaviour: https://software.intel.com/content/www/us/en/develop/download/intel-64-and-ia-32-architectures-sdm-combined-volumes-1-2a-2b-2c-2d-3a-3b-3c-3d-and-4.html https://software.intel.com/content/www/us/en/develop/downloa... [4.8 ACCESSED AND DIRTY FLAGS] Memory-management software may clear these flags when a page or a paging structure is initially loaded into physical memory. These flags are “sticky,” meaning that, once set, the processor does not clear them; only software can clear them. A processor may cache information from the paging-structure entries in TLBs and paging-structure caches (see Section 4.10). This fact implies that, if software changes an accessed flag or a dirty flag from 1 to 0, the processor might not set the corresponding bit in memory on a subsequent access using an affected linear address (see Section 4.10.4.3). See Section 4.10.4.2 for how software can ensure that these bits are updated as desired. [4.10.4 Invalidation of TLBs and Paging-Structure Caches] [4.10.4.2 Recommended Invalidation] ... so, I guess, yeah, this doesn't really help :|

zozbot234 6y ago

> 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. You would effectively need to run different address spaces in different threads of the "same" process, which might interoperate badly with whatever guarantees the kernel provides or relies on elsewhere based on the assumption of having a unified address space for the whole process. Though I absolutely agree that this is worthwhile, it probably needs to be designed carefully and can't just transparently replace any and all uses of munmap().

eqvinox 6y ago
Hmm - both maps and unmaps are already non-atomic though; there's gonna be some however minor span of time where different CPUs will have different state regarding a page that is being updated. IPIs don't grind the entire system to a halt to guarantee everyone is getting the same update at the same time. I.e. you can already have a syscall on thread A racing against the incoming IPI on thread B's mmap/munmap...
- new_realist 6y ago
  Sure, but the munmap() won’t return to the caller until the effects are visible in all processors.
  - kentonv 6y ago
    Imagine a program that, instead of calling munmap() directly, spins up a separate thread to call it, with the main thread proceeding on its way. Doesn't such a program today already observe all the weirdness of the page "disappearing" from different threads at different points in time? What difference would there be with a lazy mmap(), except that the window during which these inconsistencies are observable would be longer?
    - new_realist 6y ago

davidtgoldblatt 6y ago

> Maybe there's some reason this doesn't work, or maybe the performance improvements aren't worth the effort? I work on an allocator, and I've lobbied (Linux) kernel people for this over the years. I think everyone mostly agrees it'd be useful (and, the TLB shootdown cost is indeed often nontrivial), but the current architecture of the various subsystem's you'd need to touch makes it hard to do. As allocators move more and more to a hugepages-first world, I think we'll see fewer and fewer benefits from faster unmappings (instead, we'll just spend more effort making sure we fill in the holes in existing in-use ranges).

cyphar 6y ago

> 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. That does exist, it's called MADV_DONTNEED and most operating systems have implemented it. However, MADV_DONTNEED on Linux was incorrectly implemented and (from memory) would always result in the page being unmapped immediately -- making it roughly equivalent to MADV_FREE. To quote the man page: > All of the advice values listed here have analogs in the POSIX-specified posix_madvise(3) function, and the values have the same meanings, with the exception of MADV_DONTNEED.

comex 6y ago
After reading that I wondered what happens on Linux if you actually call posix_madvise(POSIX_MADV_DONTNEED). The answer, from glibc: /* We have one problem: the kernel's MADV_DONTNEED does not correspond to POSIX's POSIX_MADV_DONTNEED. The former simply discards changes made to the memory without writing it back to disk, if this would be necessary. The POSIX behavior does not allow this. There is no functionality mapping the POSIX behavior so far so we ignore that advice for now. */ if (advice == POSIX_MADV_DONTNEED) return 0;
kentonv 6y ago
AFAICT the POSIX behavior for MADV_DONTNEED is just a hint that the memory won't be accessed soon. https://pubs.opengroup.org/onlinepubs/009695399/functions/posix_madvise.html https://pubs.opengroup.org/onlinepubs/009695399/functions/po... says: POSIX_MADV_DONTNEED Specifies that the application expects that it will not access the specified range in the near future. https://www.freebsd.org/cgi/man.cgi?query=madvise&sektion=2 https://www.freebsd.org/cgi/man.cgi?query=madvise&sektion=2 says: MADV_DONTNEED Allows the VM system to decrease the in-memory priority of pages in the specified address range. Consequently, future references to this address range are more likely to incur a page fault. Neither of these suggest that the contents of the memory content can be discarded (as Linux does), only that it can be swapped out. So it doesn't appear that this provides the "lazy unmap to avoid shootdown" behavior on any OS.

markjdb 6y ago

> I do wonder why there isn't an API for "lazy munmap()" You don't really need a separate API. The kernel can implement munmap() lazily, it just needs to also ensure that the address range isn't reused until a TLB shootdown is completed. LATR is a system that leverages this to implement lazy TLB shootdowns for munmap(): http://www.cs.yale.edu/homes/abhishek/kumar-asplos18.pdf http://www.cs.yale.edu/homes/abhishek/kumar-asplos18.pdf

BeeOnRope 6y ago
Wouldn't this break the existing semantics of mmap, which is after the mmap call returns, other threads in the same process will fault if the they access the mapping? Sure, avoiding re-use prevents some types of bugs but not others.
- londons_explore 6y ago
  Id be interested to know if any program relies on freeing memory in one thread, then (with some lock for synchronization) deliberately accessing it from another thread causing a segfault. Sure, it's possible, but if no programs do it, it might be worth breaking the behaviour for the performance increase.
  - kentonv 6y ago
    If the program is just using mmap/munmap for memory allocation, then I agree with you. But some programs do crazier things. Imagine a program that implements mmap of a file entirely in userspace. For example, say I have a file that's stored on a distributed filesystem that dosen't have kernel drivers. So I catch SIGSEGV in userspace and populate pages on-demand by fetching them from the remote server. Later on, the page hasn't been used in a while, so I munmap() it to reclaim memory. I expect that any further uses after this point (especially writes, which maybe I need to sync back?) will raise a new SIGSEGV which I can handle. I think something like that, unfortunately, could be broken by changing all munmaps to be lazy...
    - 6y ago