fadvise: Add _VOLATILE,_ISVOLATILE, and _NONVOLATILE flags
Subsystems (4)
RFC PATCH 1/1 fadvise: Add _VOLATILE,_ISVOLATILE, and _NONVOLATILE flags
This patch provides new fadvise flags that can be used to mark file pages as volatile, which will allow it to be discarded if the kernel wants to reclaim memory.
This is useful for userspace to allocate things like caches, and lets the kernel destructively (but safely) reclaim them when there's memory pressure.
Right now, we can simply throw away pages if they are clean (backed by a current on-disk copy). That only happens for anonymous/tmpfs/shmfs pages when they're swapped out. This patch lets userspace select dirty pages which can be simply thrown away instead of writing them to disk first. See the mm/shmem.c for this bit of code. It's different from FADV_DONTNEED since the pages are not immediately discarded; they are only discarded under pressure.
This is very much influenced by the Android Ashmem interface by Robert Love so credits to him and the Android developers. In many cases the code & logic come directly from the ashmem patch. The intent of this patch is to allow for ashmem-like behavior, but embeds the idea a little deeper into the VM code, instead of isolating it into a specific driver.
I'm very much a newbie at the VM code, so At this point, I just want to try to get some input on the patch, so if you have another idea for using something other then fadvise, or other thoughts on how the volatile ranges are stored, I'd be really interested in hearing them. So let me know if you have any comments for feedback!
Also many thanks to Dave Hansen who helped design and develop the initial version of this patch, and has provided continued review and mentoring for me in the VM code.
--- fs/inode.c | 2 + include/linux/fadvise.h | 6 + include/linux/fs.h | 2 + include/linux/volatile.h | 34 ++++++ mm/Makefile | 2 +- mm/fadvise.c | 21 ++++- mm/shmem.c | 14 +++ mm/volatile.c | 253 ++++++++++++++++++++++++++++++++++++++++++++++ 8 files changed, 332 insertions(+), 2 deletions(-) create mode 100644 include/linux/volatile.h create mode 100644 mm/volatile.c
fs/inode.c +2 -0
@@ -247,6 +247,7 @@ void __destroy_inode(struct inode *inode)if (inode->i_default_acl && inode->i_default_acl !=ACL_NOT_CACHED )posix_acl_release (inode->i_default_acl);#endif +mapping_clear_volatile_ranges (&inode->i_data);this_cpu_dec (nr_inodes); }EXPORT_SYMBOL (__destroy_inode);
@@ -278,6 +279,7 @@ void address_space_init_once(struct address_space *mapping)spin_lock_init (&mapping->private_lock);INIT_RAW_PRIO_TREE_ROOT (&mapping->i_mmap);INIT_LIST_HEAD (&mapping->i_mmap_nonlinear); +INIT_LIST_HEAD (&mapping->volatile_list); }EXPORT_SYMBOL (address_space_init_once);
include/linux/fadvise.h +6 -0
@@ -18,4 +18,10 @@#define POSIX_FADV_NOREUSE 5/* Data will be accessed once. */ #endif +#define POSIX_FADV_VOLATILE 8/* _can_ toss, but don't toss now */ +#define POSIX_FADV_NONVOLATILE 9/* Remove VOLATILE flag */ +#define POSIX_FADV_ISVOLATILE 10/* Returns volatile flag for region */ + + +#endif /* FADVISE_H_INCLUDED */
include/linux/fs.h +2 -0
@@ -10,6 +10,7 @@#include <linux/ioctl.h> #include <linux/blk_types.h> #include <linux/types.h> +#include <linux/volatile.h> /* * It's silly to have NR_OPEN bigger than NR_FILE, but you can change
@@ -650,6 +651,7 @@ struct address_space {spinlock_t private_lock;/* for use by the address_space */ struct list_head private_list;/* ditto */ struct address_space *assoc_mapping;/* ditto */ +struct list_head volatile_list;/* volatile range list */ } __attribute__((aligned(sizeof(long))));/* * On most architectures that alignment is already the case; but
include/linux/volatile.h new file +34 -0
@@ -0,0 +1,34 @@ +#ifndef _LINUX_VOLATILE_H +#define _LINUX_VOLATILE_H + +struct address_space ; + + +struct volatile_range { +/* +* List is sorted, and no two ranges +* on the same list should overlap. +*/ +struct list_head unpinned; +pgoff_t start_page; +pgoff_t end_page; +unsigned int purged; +}; + +static inline bool page_in_range (struct volatile_range *range, +pgoff_t page_index) +{ +return (range->start_page <= page_index) && + (range->end_page >= page_index); +} + +extern long mapping_range_volatile (struct address_space *mapping, +pgoff_t start_index,pgoff_t end_index); +extern long mapping_range_nonvolatile (struct address_space *mapping, +pgoff_t start_index,pgoff_t end_index); +extern long mapping_range_isvolatile (struct address_space *mapping, +pgoff_t start_index,pgoff_t end_index); +extern void mapping_clear_volatile_ranges (struct address_space *mapping); + + +#endif /* _LINUX_VOLATILE_H */
mm/Makefile +1 -1
@@ -13,7 +13,7 @@ obj-y := filemap.o mempool.o oom_kill.o fadvise.o \ readahead.o swap.o truncate.o vmscan.o shmem.o \ prio_tree.o util.o mmzone.o vmstat.o backing-dev.o \ page_isolation.o mm_init.o mmu_context.o percpu.o \ - $(mmu-y) + volatile.o $(mmu-y) obj-y += init-mm.o ifdef CONFIG_NO_BOOTMEM
mm/fadvise.c +20 -1
@@ -106,7 +106,7 @@ SYSCALL_DEFINE(fadvise64_64)(int fd, loff_t offset, loff_t len, int advice) nrpages = end_index - start_index +1 ;if (!nrpages) nrpages = ~0UL ; - + ret =force_page_cache_readahead (mapping, file, start_index, nrpages);
@@ -127,6 +127,25 @@ SYSCALL_DEFINE(fadvise64_64)(int fd, loff_t offset, loff_t len, int advice)invalidate_mapping_pages (mapping, start_index, end_index);break ; +case POSIX_FADV_VOLATILE : +/* First and last PARTIAL page! */ + start_index = offset >>PAGE_CACHE_SHIFT ; + end_index = endbyte >>PAGE_CACHE_SHIFT ; + ret =mapping_range_volatile (mapping, start_index, end_index); +break ; +case POSIX_FADV_NONVOLATILE : +/* First and last PARTIAL page! */ + start_index = offset >>PAGE_CACHE_SHIFT ; + end_index = endbyte >>PAGE_CACHE_SHIFT ; + ret =mapping_range_nonvolatile (mapping, start_index, + end_index); +break ; +case POSIX_FADV_ISVOLATILE : +/* First and last PARTIAL page! */ + start_index = offset >>PAGE_CACHE_SHIFT ; + end_index = endbyte >>PAGE_CACHE_SHIFT ; + ret =mapping_range_isvolatile (mapping, start_index, end_index); +break ;default : ret = -EINVAL ; }
mm/shmem.c +14 -0
@@ -679,6 +679,20 @@ static int shmem_writepage(struct page *page, struct writeback_control *wbc) index = page->index; inode = mapping->host; info =SHMEM_I (inode); + +/* Check if page is in volatile range */ +if (!list_empty (&mapping->volatile_list)) { +struct volatile_range *range, *next; +list_for_each_entry_safe (range, next, &mapping->volatile_list, + unpinned) { +if (page_in_range (range, index)) { + range->purged =1 ; +unlock_page (page); +return 0 ; + } + } + } +if (info->flags &VM_LOCKED ) goto redirty;if (!total_swap_pages)
mm/volatile.c new file +253 -0
253 lines not on this page · raw message
Signature · 1 line
1.7.3.2.146.gca209
Quoted 8 lines · John Stultz
This patch provides new fadvise flags that can be used to mark file pages as volatile, which will allow it to be discarded if the kernel wants to reclaim memory.
This is useful for userspace to allocate things like caches, and lets the kernel destructively (but safely) reclaim them when there's memory pressure.
Quoted 7 lines
Right now, we can simply throw away pages if they are clean (backed by a current on-disk copy). That only happens for anonymous/tmpfs/shmfs pages when they're swapped out. This patch lets userspace select dirty pages which can be simply thrown away instead of writing them to disk first. See the
mm/shmem.cfor this bit of code. It's different fromFADV_DONTNEEDsince the pages are not immediately discarded; they are only discarded under pressure.
I've got a few questions:
1) How do you tell userspace some of its data got
discarded?
2) How do you prevent the situation where every volatile object gets a few pages discarded, making them all unusable?
(better to throw away an entire object at once)
3) Isn't it too slow for something like Firefox to create a new tmpfs object for every single throw-away cache object?
Johannes, Jon and I have looked at an alternative way to allow the kernel and userspace to cooperate in throwing out cached data. This alternative way does not touch the alloc/free fast path at all, but does require some cooperation at "shrink cache" time.
The idea is quite simple:
1) Every program that we are interested in already has some kind of main loop where it polls on file descriptors. It is easy for such programs to add an additional file, which would be a device or sysfs file that wakes up the program from its poll/select loop when memory is getting full to the point that userspace needs to shrink its caches.
The kernel can be smart here and wake up just one process at a time, targeting specific NUMA nodes or cgroups. Such kernel smarts do not require additional userspace changes.
2) When userspace gets such a "please shrink your caches" event, it can do various things. A program like firefox could throw away several cached objects, eg. uncompressed images or entire pre-rendered tabs, while a JVM can shrink its heap size and a database could shrink its internal cache.
3) After doing that, they could all call the same glibc function that walks across program-internal free memory and calls MADV_FREE on all free regions that span multiple pages, which gives the pages back to the kernel, without needing to move VMA boundaries. This is relatively light weight and allows for the nuking of pages right in the middle of a heap VMA.
4) In some GUI libraries, like gtk/glib, we could open the memory pressure device node (or sysfs file) by default, hooking it up to the glibc function from (3) by default, which would give all gtk/glib programs the ability to give free()d memory back to the kernel on request, without needing to even modify the program.
Program modification would only be needed in order to free cached objects, etc. The modification of programs running under those libraries would consist of overriding the "shrink caches" hook with their own function, which first does program-specific stuff and then calls the default hook to take care of the glibc side.
We considered the same approach you are proposing as well, but we did not come up with satisfactory answers to the questions I asked above, which is why we came up with this scheme.
Unfortunately we have not gotten around to implementing it yet, but I'd be happy to work on it with you guys if you are interested.
Quoted 22 lines · Rik van Riel
Quoted 8 lines · John Stultz
This patch provides new fadvise flags that can be used to mark file pages as volatile, which will allow it to be discarded if the kernel wants to reclaim memory.
This is useful for userspace to allocate things like caches, and lets the kernel destructively (but safely) reclaim them when there's memory pressure.
Quoted 7 lines
Right now, we can simply throw away pages if they are clean (backed by a current on-disk copy). That only happens for anonymous/tmpfs/shmfs pages when they're swapped out. This patch lets userspace select dirty pages which can be simply thrown away instead of writing them to disk first. See the
mm/shmem.cfor this bit of code. It's different fromFADV_DONTNEEDsince the pages are not immediately discarded; they are only discarded under pressure.I've got a few questions:
1) How do you tell userspace some of its data got
discarded?
Quoted 8 lines
2) How do you prevent the situation where every volatile object gets a few pages discarded, making them all unusable?
(better to throw away an entire object at once)3) Isn't it too slow for something like Firefox to create a new tmpfs object for every single throw-away cache object?
Oh, and a fourth issue with the _VOLATILE approach, which I forgot to write down before:
4) Virtualization. Marking an object (and its pages) _VOLATILE inside a guest will not be visible on the host side, which means a virtual system may continue to suffer the performance penalty anyway.
On the other hand, the approach I outlined will simply result in a virtual machine being asked to reduce its memory, and possibly later on passing that notification on to the programs running inside. In other words, the "please shrink your caches" notification naturally recurses into cgroups and virtual machines.
Quoted 4 lines · Rik van Riel
4) Virtualization. Marking an object (and its pages)
_VOLATILEinside a guest will not be visible on the host side, which means a virtual system may continue to suffer the performance penalty anyway.
Yeah, I guess we still have to communicate it _somehow_.
I guess we could theoretically pass the calls up to the hypervisor and it could even make its own VOLATILE calls to the host kernel. We'd also have to pass back down the "was this evicted" information during a re-pin. That seems messy to me.
Is it really any different of a problem than page cache? The guest has data sitting in RAM that it probably doesn't need. If we passed up just the amount of unpinned data back up to the hypervisor, it would have a decent idea how much it could balloon the guest, for instance. That would fit in well with some of the existing schemes that folks have and be *much* nicer than what they've got at the moment.
First, thanks to John for driving this. I'd love to see something like ashmem's cache functionality in Linux.
Comments inline:
Quoted 2 lines · Rik van Riel
1) How do you tell userspace some of its data got discarded?
This is my big question, too. This must be addressed to make this usable by user-space. Unfortunately there isn't a side channel available in madvise or fadvise.
The ashmem use case is like this:
1. Create an ashmem mapping. All pages start off pinned.
2. Populate pages
3. Use pages.
4. Unpin some or all pages.
5. Re-pin pages. Return value tells you if they were jettisoned. If so, goto #2. If not, goto #3.
Quoted 4 lines
2) How do you prevent the situation where every volatile object gets a few pages discarded, making them all unusable?
(better to throw away an entire object at once)
In ashmem, I prevent this by jettisoning pages in units of unpinned chunks, ordered by least-recently-unpinned. Since pinned/unpinned chunks tend to relate to user-space objects (e.g. you'd unpin a whole image), you end up throwing away the entire user-space object.
Put another way, the eviction algorithm is least-recently-unpinned chunk, not least-recently-unpinned page, which prevents thrashing lots of objects. An alternative would be to toss not whole chunks, but whole mappings.
Quoted 3 lines
3) Isn't it too slow for something like Firefox to create a new tmpfs object for every single throw-away cache object?
Nope, although user-space might want to create larger mappings and sub-divide them if its objects are *really* small.
Quoted 5 lines
Johannes, Jon and I have looked at an alternative way to allow the kernel and userspace to cooperate in throwing out cached data. This alternative way does not touch the alloc/free fast path at all, but does require some cooperation at "shrink cache" time.
I'm open to whatever works, and I need to think about your proposal more, but it sounds inferior to the model John is proposing.
I think we can sum the two models up as,
- User-space pins, unpins objects, and kernel handles eviction
- Kernel lets user-space register callbacks for notification during cache shrink, user handles eviction
Right?
Actually, I can see the need for both. But the first is simpler, lets the kernel evict pages from user-space even in low memory situations (since you can call the cache shrinker atomically), and relies on the fact that the "free caches" action is just jettisoning the pages, so the kernel can do it. The actual work is in repopulating the caches.
That last point, btw, is why user-space developers like ashmem: It fits their models of how they do work. They pin/unpin objects as part of their normal access and repopulating is tied into the re-pin path, which is where it makes sense.
In a callback model, you have two issues: One, user-space needs to do its own jettisoning. Two, user-space now needs to keep track of whether an object was jettisoned and repopulate it (when? on next use? now you have user-space reimplementing the pin/unpin logic, right?).
Robert
Quoted 17 lines · Rik van Riel
Quoted 8 lines · John Stultz
This patch provides new fadvise flags that can be used to mark file pages as volatile, which will allow it to be discarded if the kernel wants to reclaim memory.
This is useful for userspace to allocate things like caches, and lets the kernel destructively (but safely) reclaim them when there's memory pressure.
Quoted 7 lines
Right now, we can simply throw away pages if they are clean (backed by a current on-disk copy). That only happens for anonymous/tmpfs/shmfs pages when they're swapped out. This patch lets userspace select dirty pages which can be simply thrown away instead of writing them to disk first. See the
mm/shmem.cfor this bit of code. It's different fromFADV_DONTNEEDsince the pages are not immediately discarded; they are only discarded under pressure.
Quoted 4 lines
I've got a few questions:
1) How do you tell userspace some of its data got discarded?
You get a return code when marking the page non-volatile if it has been discarded. This follows the ashmem style that Robert described in the other mail.
Quoted 4 lines
2) How do you prevent the situation where every volatile object gets a few pages discarded, making them all unusable?
(better to throw away an entire object at once)
Indeed. One of the issues folks brought up about the ashmem code was that it manages its own lru. This attempt just simplifies the code, by using the kerenl's own lru, but does have the draw back that it is page based instead of object or range-based.
We could try to zap the entire range when a page from the range is written out, or we could go back to using a range based lru, like ashmem does.
Quoted 3 lines
3) Isn't it too slow for something like Firefox to create a new tmpfs object for every single throw-away cache object?
So, if you mean creating a new file for every cache object, that doesn't seem necessary, as you could map a number of objects into the same file and mark the ranges as volatile or not as needed.
Or are you worried about the allocation of the range structure when we mark a region as volatile?
Either way, I'd defer to Robert on real-world usage.
Quoted 20 lines
Johannes, Jon and I have looked at an alternative way to allow the kernel and userspace to cooperate in throwing out cached data. This alternative way does not touch the alloc/free fast path at all, but does require some cooperation at "shrink cache" time.
The idea is quite simple:
1) Every program that we are interested in already has some kind of main loop where it polls on file descriptors. It is easy for such programs to add an additional file, which would be a device or sysfs file that wakes up the program from its poll/select loop when memory is getting full to the point that userspace needs to shrink its caches.
The kernel can be smart here and wake up just one process at a time, targeting specific NUMA nodes or cgroups. Such kernel smarts do not require additional userspace changes.
Quoted 6 lines
2) When userspace gets such a "please shrink your caches" event, it can do various things. A program like firefox could throw away several cached objects, eg. uncompressed images or entire pre-rendered tabs, while a JVM can shrink its heap size and a database could shrink its internal cache.
So similarly to Robert, I don't see this approach as necessarily exclusive to the volatile flags. There are just some tradeoffs with the different approaches.
The upside with your approach is that applications don't have to remember to re-pin the cache before using it and unpin it after its done using it.
The downside is that the "please shrink your caches" message is likely to arrive when the system is low on resources. Once applications have been asked to "be nice and get small!", having to wait for that action to occur might not be great. Where as with the volatile regions, there are just additionally easily freeable pages available when the kernel needs them.
thanks
-john
Quoted 6 lines · John Stultz
Quoted 1 line · Rik van Riel
On 11/21/2011 10:33 PM, John Stultz wrote:
So similarly to Robert, I don't see this approach as necessarily exclusive to the volatile flags. There are just some tradeoffs with the different approaches.
Agreed, they might be complementary.
Quoted 3 lines
The upside with your approach is that applications don't have to remember to re-pin the cache before using it and unpin it after its done using it.
If using these volatile regions is going to become common, programs will be pinning and unpinning those cache regions all the time, even when there is no memory pressure at all.
At that point, I wonder if userspace programmers will not end up making an automatic choice for a method that does not impact their fast path at all, and only gets invoked rarely.
Quoted 4 lines
The downside is that the "please shrink your caches" message is likely to arrive when the system is low on resources. Once applications have been asked to "be nice and get small!", having to wait for that action to occur might not be great.
The pageout code in vmscan.c can send these messages before we actually get around to evicting any anonymous page from memory.
I believe the code we have there today can get these signals sent before we get in any serious trouble.
Quoted 3 lines
Where as with the volatile regions, there
are just additionally easily freeable pages available when the kernel needs them.
That is certainly true. However, it is unclear how that would translate to virtualized solutions, since there is no way for a virtual machine to mark pages as volatile with the host (especially since there is no way to tell the host what pages belong together in objects).
I'm not objecting to your idea - in fact I like it.
However, I believe it would be good to answer some of these questions before adding another interface to the kernel that needs to be maintained forever.
A message that is not in the archive (sent off-list or not yet received): CAG6tG3xTkW1J=6xmUmmJoswJyR6ii5RDXvAsYrcH0CkVuUmJrQ@mail.gmail.com
Quoted 7 lines · Robert Love
3) Isn't it too slow for something like Firefox to create a new tmpfs object for every single throw-away cache object?
Nope, although user-space might want to create larger mappings and sub-divide them if its objects are *really* small.
At first glance, it sounds like a great idea to have a program like Firefox create a new object for every tab.
However, this quickly runs into the practical problem that Firefox does not know in advance how much memory each tab will require.
Without a good way to size each mapping in advance, it may not be practical to group related bits of memory together.
Never mind that it would require userspace programs to grow new memory allocators...
Quoted 11 lines
Johannes, Jon and I have looked at an alternative way to allow the kernel and userspace to cooperate in throwing out cached data. This alternative way does not touch the alloc/free fast path at all, but does require some cooperation at "shrink cache" time.
I'm open to whatever works, and I need to think about your proposal more, but it sounds inferior to the model John is proposing. I think we can sum the two models up as,
Quoted 5 lines
- User-space pins, unpins objects, and kernel handles eviction
- Kernel lets user-space register callbacks for notification during cache shrink, user handles evictionRight?
Yes, this characterization is correct.
Note how in the object I proposed, when there is no memory pressure, userspace can hold on to freed pages and quickly reuse them for something else.
There is no need for pages to be handed back to the kernel, and then zeroed again when they get handed back to userspace later on.
There is also no need to write a new memory allocator for programs that want to pack related objects together in one _VOLATILE mapping.
The reason is that, on memory pressure, any arbitrary set of pages can be nuked from userspace, so any memory allocator will be compatible.
Quoted 10 lines
Actually, I can see the need for both. But the first is simpler, lets the kernel evict pages from user-space even in low memory situations (since you can call the cache shrinker atomically), and relies on the fact that the "free caches" action is just jettisoning the pages, so the kernel can do it. The actual work is in repopulating the caches.
That last point, btw, is why user-space developers like ashmem: It fits their models of how they do work. They pin/unpin objects as part of their normal access and repopulating is tied into the re-pin path, which is where it makes sense.
Which userspace programs work that way already?
Hi, Rik.
Quoted 9 lines · Rik van Riel
At first glance, it sounds like a great idea to have a program like Firefox create a new object for every tab.
However, this quickly runs into the practical problem that Firefox does not know in advance how much memory each tab will require.
Without a good way to size each mapping in advance, it may not be practical to group related bits of memory together.
On Android (and Firefox for Android for that matter) we manage just about every resource (such as images, rendered web pages, etc) through ashmem. I don't recall the details of how the various subsystems that utilize ashmem decide whether to use a mapping-per-object versus packing multiple objects into a single mapping, but it works.
Quoted 2 lines
Never mind that it would require userspace programs to grow new memory allocators...
Agreed.
Quoted 9 lines
Yes, this characterization is correct.
Note how in the object I proposed, when there is no memory pressure, userspace can hold on to freed pages and quickly reuse them for something else.
There is no need for pages to be handed back to the kernel, and then zeroed again when they get handed back to userspace later on.
Agreed, this is a nice benefit. However, couldn't user-space do the same thing now with MADV_DONTNEED?
I do think we have two different features here, and we may want both.
I'm concerned your proposal isn't ideal for Android or similar systems. It is heavy, and will involve too much process involvement. Remember, these systems are always running at memory capacity and are constantly LRU-freeing small amounts of pages. Having a way to say to the kernel, "you can toss these pages if you must, just let me know later if I try to reuse them" -- in a way that is very simple and very cheap -- is really valuable.
Quoted 7 lines
There is also no need to write a new memory allocator for programs that want to pack related objects together in one
_VOLATILEmapping.The reason is that, on memory pressure, any arbitrary set of pages can be nuked from userspace, so any memory allocator will be compatible.
In ashmem, you can pin and unpin any arbitrary set of pages. You don't have to pin the whole mapping, allowing user-space to pack arbitrary mappings into a single mapping and have the kernel jettison only the unused objects.
Quoted 6 lines
Quoted 4 lines
That last point, btw, is why user-space developers like ashmem: It fits their models of how they do work. They pin/unpin objects as part of their normal access and repopulating is tied into the re-pin path, which is where it makes sense.
Which userspace programs work that way already?
What I mean is, user-space implicitly (if not explicitly) has get and put methods via things like reference counting, locking & unlocking, or the RAII pattern. And user-space already has a concept of "populate this object." So adding ashmem pin and unpin calls is often very simple, because the ashmem use case maps very nicely on top of how user-space applications are already managing resources.
Robert
Jan Kara
reviewerQuoted 15 lines · Rik van Riel
On 11/21/2011 10:33 PM, John Stultz wrote:
The idea is quite simple:1) Every program that we are interested in already has some kind of main loop where it polls on file descriptors. It is easy for such programs to add an additional file, which would be a device or sysfs file that wakes up the program from its poll/select loop when memory is getting full to the point that userspace needs to shrink its caches.
The kernel can be smart here and wake up just one process at a time, targeting specific NUMA nodes or cgroups. Such kernel smarts do not require additional userspace changes.
Quoted 6 lines
2) When userspace gets such a "please shrink your caches" event, it can do various things. A program like firefox could throw away several cached objects, eg. uncompressed images or entire pre-rendered tabs, while a JVM can shrink its heap size and a database could shrink its internal cache.
Hmm, I wonder here: How much should a program free? A single object? Or
one meg of memory? I find this decision rather problematic. How much should be reclaimed depends on the number of applications listening, how aggressive they are, and current memory pressure => it's basically unpredictable from userspace so you are almost guaranteed to either reclaim too much or too few. Advantage of the VOLATILE approach is that kernel (which is the only place where there is all necessary information) controls how much memory is evicted... Just one argument for VOLATILE approach I didn't see mentioned in the discussion yet.
Honza
Andrew Morton
maintainerQuoted 29 lines · On Mon, 21 Nov 2011 19:33:08 -0800 John Stultz <[email protected]> wrote:
This patch provides new fadvise flags that can be used to mark file pages as volatile, which will allow it to be discarded if the kernel wants to reclaim memory.
This is useful for userspace to allocate things like caches, and lets the kernel destructively (but safely) reclaim them when there's memory pressure.
Right now, we can simply throw away pages if they are clean (backed by a current on-disk copy). That only happens for anonymous/tmpfs/shmfs pages when they're swapped out. This patch lets userspace select dirty pages which can be simply thrown away instead of writing them to disk first. See the
mm/shmem.cfor this bit of code. It's different fromFADV_DONTNEEDsince the pages are not immediately discarded; they are only discarded under pressure.This is very much influenced by the Android Ashmem interface by Robert Love so credits to him and the Android developers. In many cases the code & logic come directly from the ashmem patch. The intent of this patch is to allow for ashmem-like behavior, but embeds the idea a little deeper into the VM code, instead of isolating it into a specific driver.
I'm very much a newbie at the VM code, so At this point, I just want to try to get some input on the patch, so if you have another idea for using something other then fadvise, or other thoughts on how the volatile ranges are stored, I'd be really interested in hearing them. So let me know if you have any comments for feedback!
Quoted 3 lines
Also many thanks to Dave Hansen who helped design and develop the initial version of this patch, and has provided continued review and mentoring for me in the VM code.
I'm interestedly watching the design/use-case discussion. Meanwhile, some comments on the implementation.
include/linux/fadvise.h line 23
Quoted 6 lines
...
include/linux/fadvise.h +3
-0+#define POSIX_FADV_VOLATILE 8/* _can_ toss, but don't toss now */ +#define POSIX_FADV_NONVOLATILE 9/* Remove VOLATILE flag */ +#define POSIX_FADV_ISVOLATILE 10/* Returns volatile flag for region */
[email protected] will want to be told all about these at some stage.
include/linux/fs.h line 13
Quoted 12 lines
include/linux/fadvise.h +2
-0+ +#endif /* FADVISE_H_INCLUDED */ include/linux/fs.h +1
-0@@ -10,6 +10,7 @@#include <linux/ioctl.h> #include <linux/blk_types.h> #include <linux/types.h> +#include <linux/volatile.h>
volatile is a C keyword. This is a bit confusing/misleading.
include/linux/fs.h struct address_space { · line 654
Quoted 7 lines
include/linux/fs.h +1
-0/* * It's silly to have NR_OPEN bigger than NR_FILE, but you can change @@ -650,6 +651,7 @@ struct address_space {spinlock_t private_lock;/* for use by the address_space */ struct list_head private_list;/* ditto */ struct address_space *assoc_mapping;/* ditto */ +struct list_head volatile_list;/* volatile range list */
Comment should tell us what lock protects this.
It appers to be i_mmap_lock, which is weird.
Quoted 9 lines
include/linux/fs.h +0
-0} __attribute__((aligned(sizeof(long))));/* * On most architectures that alignment is already the case; but include/linux/volatile.h new file +0
-0
include/linux/volatile.h line 9
Quoted 9 lines
include/linux/volatile.h new file +9
-0@@ -0,0 +1,34 @@ +#ifndef _LINUX_VOLATILE_H +#define _LINUX_VOLATILE_H + +struct address_space ; + + +struct volatile_range { +/* +* List is sorted, and no two ranges
sorted by pgoff_t, it appears.
include/linux/volatile.h line 12
Quoted 3 lines
include/linux/volatile.h new file +3
-0+* on the same list should overlap. +*/ +struct list_head unpinned;
What's this do? It appears to be the list anchored in address_space.volatile_list and protected by i_mmap_lock to maintain all these things. "unpinned" is a strange name for such a thing.
include/linux/volatile.h line 15
Quoted 3 lines
include/linux/volatile.h new file +3
-0+pgoff_t start_page; +pgoff_t end_page; +unsigned int purged;
Some description here would be good. What's it for, when is it set and cleared.
include/linux/volatile.h line 23
Quoted 8 lines
include/linux/volatile.h new file +8
-0+}; + +static inline bool page_in_range (struct volatile_range *range, +pgoff_t page_index) +{ +return (range->start_page <= page_index) && + (range->end_page >= page_index); +}
"page_in_range" is too vague a name for this...
Quoted 22 lines
include/linux/volatile.h new file +10
-0+extern long mapping_range_volatile (struct address_space *mapping, +pgoff_t start_index,pgoff_t end_index); +extern long mapping_range_nonvolatile (struct address_space *mapping, +pgoff_t start_index,pgoff_t end_index); +extern long mapping_range_isvolatile (struct address_space *mapping, +pgoff_t start_index,pgoff_t end_index); +extern void mapping_clear_volatile_ranges (struct address_space *mapping); + + +#endif /* _LINUX_VOLATILE_H */ mm/shmem.c +3
-0@@ -679,6 +679,20 @@ static int shmem_writepage(struct page *page, struct writeback_control *wbc) index = page->index; inode = mapping->host; info =SHMEM_I (inode); + +/* Check if page is in volatile range */ +if (!list_empty (&mapping->volatile_list)) {
mm/shmem.c static int shmem_writepage(struct page *page, struct writeback_control *wbc) · line 694
Quoted 10 lines
mm/shmem.c +10
-0+struct volatile_range *range, *next; +list_for_each_entry_safe (range, next, &mapping->volatile_list, + unpinned) { +if (page_in_range (range, index)) { + range->purged =1 ; +unlock_page (page); +return 0 ; + } + } + }
That's very optimistic code :(
We've handed users a way in which to consume arbitrarily vast amounts of kernel CPU time. Putting a cond_resched() in there won't fix this.
Also, the volatile_range's are kmalloced so we have also given the user a way of quickly consuming unlimited amounts of kernel memory. Not good.
Quoted 15 lines
...
mm/shmem.c +12
-0+/* +* Allocates a volatile_range, and adds it to the address_space's +* volatile list +*/ +static int volatile_range_alloc (struct volatile_range *prev_range, +unsigned int purged, +pgoff_t start_index,pgoff_t end_index) +{ +struct volatile_range *range; + + range =kzalloc (sizeof (struct volatile_range ),GFP_KERNEL ); +if (!range)
mm/shmem.c
Quoted 10 lines
mm/shmem.c +10
-0+return -ENOMEM ; + + range->start_page = start_index; + range->end_page = end_index; + range->purged = purged; + +list_add_tail (&range->unpinned, &prev_range->unpinned); + +return 0 ; +}
Back in, ahem, 1999 I wrote a piece of tree code which I think does this. Each node represents a span and the nodes are kept sorted in the tree and it does merging and splitting of nodes as ranges are added. Removal and lookup don't appear to be implemented yet, but they're easy enough. Pretty complex but everything is O(log(n)) and I think it could be made to work here.
<rummage rummage>
OK, see attached.
Also, do you know what this code is like? Posix and BSD file locking. It has the same requirement to maintain state about arbitrary spans of a single file.
The locking code is an utter pig and has well known (?) O(N^2) and even O(N^3) failure modes. But don't let that deter you ;) We should strenuously avoid duplicating such a similar thing.
Quoted 13 lines · Andrew Morton
include/linux/fs.h line 13
Quoted 9 lines · On Mon, 21 Nov 2011 19:33:08 -0800 John Stultz <[email protected]> wrote:
include/linux/fs.h +1
-0@@ -10,6 +10,7 @@#include <linux/ioctl.h> #include <linux/blk_types.h> #include <linux/types.h> +#include <linux/volatile.h> volatile is a C keyword. This is a bit confusing/misleading.
Yea. This struck me as well, but I didn't have a better name, so I went ahead and sent it out. I'd be happy with any suggestions, or ideas for where such code should live.
Quoted 11 lines
include/linux/fs.h struct address_space { · line 654
Quoted 7 lines
include/linux/fs.h +1
-0/* * It's silly to have NR_OPEN bigger than NR_FILE, but you can change @@ -650,6 +651,7 @@ struct address_space {spinlock_t private_lock;/* for use by the address_space */ struct list_head private_list;/* ditto */ struct address_space *assoc_mapping;/* ditto */ +struct list_head volatile_list;/* volatile range list */ Comment should tell us what lock protects this.
It appers to be
i_mmap_lock, which is weird.
Yea. I need a mutex connected to the address_space, so i_mmap_lock looked possibly useful for this. It was really a last minute stab.
Any suggestions? I can introduce my own, but Dave was already grumbling about the list_head living on the address_space structure.
Quoted 21 lines
Quoted 9 lines
include/linux/fs.h +0
-0} __attribute__((aligned(sizeof(long))));/* * On most architectures that alignment is already the case; but include/linux/volatile.h new file +0
-0include/linux/volatile.h line 9
Quoted 9 lines
include/linux/volatile.h new file +9
-0@@ -0,0 +1,34 @@ +#ifndef _LINUX_VOLATILE_H +#define _LINUX_VOLATILE_H + +struct address_space ; + + +struct volatile_range { +/* +* List is sorted, and no two ranges sorted by
pgoff_t, it appears.
Quoted 7 lines
include/linux/volatile.h line 12
Quoted 3 lines
include/linux/volatile.h new file +3
-0+* on the same list should overlap. +*/ +struct list_head unpinned;What's this do? It appears to be the list anchored in address_space.volatile_list and protected by
i_mmap_lockto maintain all these things. "unpinned" is a strange name for such a thing.
Unpinned comes from the ashmem patch. Assuming folks think this basic approach is worth continuing, I'll try to come up with a more sane name for the next version.
Quoted 7 lines
include/linux/volatile.h line 15
Quoted 3 lines
include/linux/volatile.h new file +3
-0+pgoff_t start_page; +pgoff_t end_page; +unsigned int purged;Some description here would be good. What's it for, when is it set and cleared.
Quoted 10 lines
include/linux/volatile.h line 23
Quoted 8 lines
include/linux/volatile.h new file +8
-0+}; + +static inline bool page_in_range (struct volatile_range *range, +pgoff_t page_index) +{ +return (range->start_page <= page_index) && + (range->end_page >= page_index); +}"
page_in_range" is too vague a name for this...
Agreed.
Quoted 35 lines
Quoted 22 lines
include/linux/volatile.h new file +10
-0+extern long mapping_range_volatile (struct address_space *mapping, +pgoff_t start_index,pgoff_t end_index); +extern long mapping_range_nonvolatile (struct address_space *mapping, +pgoff_t start_index,pgoff_t end_index); +extern long mapping_range_isvolatile (struct address_space *mapping, +pgoff_t start_index,pgoff_t end_index); +extern void mapping_clear_volatile_ranges (struct address_space *mapping); + + +#endif /* _LINUX_VOLATILE_H */ mm/shmem.c +3
-0@@ -679,6 +679,20 @@ static int shmem_writepage(struct page *page, struct writeback_control *wbc) index = page->index; inode = mapping->host; info =SHMEM_I (inode); + +/* Check if page is in volatile range */ +if (!list_empty (&mapping->volatile_list)) {mm/shmem.c static int shmem_writepage(struct page *page, struct writeback_control *wbc) · line 694
Quoted 10 lines
mm/shmem.c +10
-0+struct volatile_range *range, *next; +list_for_each_entry_safe (range, next, &mapping->volatile_list, + unpinned) { +if (page_in_range (range, index)) { + range->purged =1 ; +unlock_page (page); +return 0 ; + } + } + }That's very optimistic code :(
Quoted 6 lines
We've handed users a way in which to consume arbitrarily vast amounts of kernel CPU time. Putting a
cond_resched()in there won't fix this.Also, the volatile_range's are kmalloced so we have also given the user a way of quickly consuming unlimited amounts of kernel memory. Not good.
Indeed. Besides the missing locking, this is a very good critique and probably a very good argument for not-pushing such functionality too deeply down into the VM. Maybe the shrinker strategy used in the ashmem patch is the better approach, as its a less critical path?
Quoted 30 lines
Quoted 12 lines
mm/shmem.c +12
-0+/* +* Allocates a volatile_range, and adds it to the address_space's +* volatile list +*/ +static int volatile_range_alloc (struct volatile_range *prev_range, +unsigned int purged, +pgoff_t start_index,pgoff_t end_index) +{ +struct volatile_range *range; + + range =kzalloc (sizeof (struct volatile_range ),GFP_KERNEL ); +if (!range)mm/shmem.c static int shmem_writepage(struct page *page, struct writeback_control *wbc)
Quoted 10 lines
mm/shmem.c +10
-0+return -ENOMEM ; + + range->start_page = start_index; + range->end_page = end_index; + range->purged = purged; + +list_add_tail (&range->unpinned, &prev_range->unpinned); + +return 0 ; +}Back in, ahem, 1999 I wrote a piece of tree code which I think does this. Each node represents a span and the nodes are kept sorted in the tree and it does merging and splitting of nodes as ranges are added. Removal and lookup don't appear to be implemented yet, but they're easy enough. Pretty complex but everything is O(log(n)) and I think it could be made to work here.
Quoted 3 lines
<rummage rummage>
OK, see attached.
Very cool! Yea. Dave brought up that the list was fairly inefficient, but I figured I'd get more feedback on the mechanism before spending too much time optimizing the structure. I'll look at your mumbletree code and see how it can be adapted. Other then apparently being a nod to the "original neo-grunge/indie-rock band from Rochester", is there a story to the name? :)
Again, I appreciate the feedback! Thanks so much!
-john
Andrew Morton
maintainerQuoted 6 lines · On Tue, 22 Nov 2011 13:32:18 -0800 John Stultz <[email protected]> wrote:
Very cool! Yea. Dave brought up that the list was fairly inefficient, but I figured I'd get more feedback on the mechanism before spending too much time optimizing the structure. I'll look at your mumbletree code and see how it can be adapted. Other then apparently being a nod to the "original neo-grunge/indie-rock band from Rochester", is there a story to the name? :)
I was first!
I was sure there was some correct term for such a tree in the literature, but I didn't know what it was and the compiler didn't like "*_tree".
Quoted 1 line
Again, I appreciate the feedback! Thanks so much!
I note you sneakily deleted the bit about posix/bsd file locking.
Quoted 11 lines · Andrew Morton
Quoted 6 lines · On Tue, 22 Nov 2011 13:32:18 -0800 John Stultz <[email protected]> wrote:
Very cool! Yea. Dave brought up that the list was fairly inefficient, but I figured I'd get more feedback on the mechanism before spending too much time optimizing the structure. I'll look at your mumbletree code and see how it can be adapted. Other then apparently being a nod to the "original neo-grunge/indie-rock band from Rochester", is there a story to the name? :)
I was first!
Sorry! Didn't realize it was the other way around. Hopefully reading the code will inform my listening. :)
Quoted 7 lines
I was sure there was some correct term for such a tree in the literature, but I didn't know what it was and the compiler didn't like "
*_tree".Quoted 1 line
Again, I appreciate the feedback! Thanks so much!
I note you sneakily deleted the bit about posix/bsd file locking.
Oh, no sneakiness intended. I agree about the parallels, and didn't really have anything to add. Hopefully the needs here are a little bit simpler, since we can coalesce regions. Maybe that will let us avoid the worst of it?
thanks
-john