Volatile ranges (v4)
Subsystems (5)
cover Volatile ranges (v4)
Ok. So here's another iteration of the fadvise volatile range code.
I realize this is still a way off from being ready, but I wanted to post what I have to share with folks working on the various range/interval management ideas as well as update folks who've provided feedback on the volatile range code.
So just on the premise: Ideally, I want delayed reclaim based hole punching.
Application has a possibly shared mmapped cache file, which it can mark chunks of which volatile or nonvolatile as it uses it. If the kernel needs memory, it can zap any ranges that are currently marked volatile.
Some examples would be rendering of images or web pages that are not on-screen. This allows the application to volunteer memory for reclaiming, and the kernel to grab it only when it needs. This differs from some of the memory notification schemes, in that it allows the kernel to immediately reclaim what it needs, rather then having to request applications to give up memory (which may add further memory load) until enough is free. However, unlike the notification scheme, it does require applications to mark and unmark pages as volatile as they use them.
Current use cases (ie: users of Android's ashmem) only use shmfs/tmpfs. However, I don't see right off why it should be limited to shm. As long as punching a hole in a file can be done w/ minimal memory overhead this could be useful and have somewhat sane behavior.
We could also only zap the page cache, not writing any dirty data out. However, w/ non-shm files, discarding dirty data without hole punching would obviously leave persistent files in a non-coherent state. This may further re-inforce that the design should be shm only if we don't do hole punching.
On the topic of hole punching, the kernel doesn't seem completely unified in this as well. As I understand, there are two methods to do hole punching: FALLOCATE_FL_PUNCH_HOLE vs MADV_REMOVE, and they don't necessarily overlap in support. For the most part, it seems persistent filesystems require FALLOCATE_FL_PUNCH, where as shmfs/tmpfs uses MADV_REMOVE. But I may be misunderstanding the subtle difference here, so if anyone wants to clarify this, it would be great.
One concern was that if the design is shm only, fadvise might not be the right interface, as it should be generic. The madvise(MADV_REMOVE,...) interface gives some precedence to shmfs/tmpfs only calls, but I'd like to get some further feedback as to what folks think of this. If we are shm/tmpfs only, I could rework this design to use madvise instead of fadvise if folks would prefer.
Also, there's still the issue that lockdep doesn't like me calling vmtruncate_range from the shrinker due to any allocations being done while the i_mutex is taken could cause the shrinker to run and need the i_mutex again. I did try using invalidate_inode_pages2_range() but it always returns EBUSY in this context, so I suspect I want something else. I'm currently reading shmem_truncate_range() and zap_page_range() to get a better idea of how to this might be best accomplished.
Regarding feedback suggesting dropping the LRU ranges, and instead keeping the volatile/purged data in radix tags and to manage things at writeout time. My concern there is having the LRU behavior on the entire range from when it was marked volatile instead of the actual last page access (you might have ranges that have frequent use areas and non-frequent use). Also sorting out how to evict the entire range when one page is dropped might be funky. However, I'll likely revisit this soon, but for this iteration I didn't get to it.
I still also realize I have the issue of bloating the address_space structure to handle, and I suspect if I continue w/ this approach I'll use a separate hash table to store the range-tree roots in my next revision.
Anyway, thanks for the continued advice and feedback! -john
John Stultz (2):
[RFC] Range tree implementation
[RFC] fadvise: Add _VOLATILE,_ISVOLATILE, and _NONVOLATILE flags
fs/inode.c | 4 + include/linux/fadvise.h | 5 + include/linux/fs.h | 2 + include/linux/rangetree.h | 53 ++++++++ include/linux/volatile.h | 14 ++ lib/Makefile | 2 +- lib/rangetree.c | 105 +++++++++++++++ mm/Makefile | 2 +- mm/fadvise.c | 16 ++- mm/volatile.c | 313 +++++++++++++++++++++++++++++++++++++++++++++ 10 files changed, 513 insertions(+), 3 deletions(-) create mode 100644 include/linux/rangetree.h create mode 100644 include/linux/volatile.h create mode 100644 lib/rangetree.c create mode 100644 mm/volatile.c
Signature · 1 line
1.7.3.2.146.gca209
RFC PATCH 1/2 Range tree implementation
After Andrew suggested something like his mumbletree idea to better store a list of ranges, I worked on a few different approaches, and this is what I've finally managed to get working.
I suspect range-tree isn't a totally accurate name, but I couldn't quite make out the difference between range trees and interval trees, so I just picked one to call it. Do let me know if you have a better name.
The idea of storing ranges in a tree is nice, but has a number of complications. When adding a range, its possible that a large range will consume and merge a number of smaller ranges. When removing a range, its possible you may end up splitting an existing range, causing one range to become two. This makes it very difficult to provide generic list_head like behavior, as the parent structures would need to be duplicated and removed, and that has lots of memory ownership issues.
So, this is a much simplified and more list_head like implementation. You can add a node to a tree, or remove a node to a tree, but the generic implementation doesn't do the merging or splitting for you. But it does provide helpers to find overlapping and adjacent ranges.
Andrew also really wanted this range-tree implementation to be resuable so we don't duplicate the file locking logic. I'm not totally convinced that the requirements between the volatile ranges and file locking are really equivelent, but this reduced impelementation may make it possible.
Do let me know what you think or if you have other ideas for better ways to do the same.
Changelog:
v2:
* Reworked code to use an rbtree instead of splaying
--- include/linux/rangetree.h | 53 +++++++++++++++++++++++ lib/Makefile | 2 +- lib/rangetree.c | 105 +++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 159 insertions(+), 1 deletions(-) create mode 100644 include/linux/rangetree.h create mode 100644 lib/rangetree.c
include/linux/rangetree.h new file +53 -0
@@ -0,0 +1,53 @@ +#ifndef _LINUX_RANGETREE_H +#define _LINUX_RANGETREE_H + +#include <linux/types.h> +#include <linux/rbtree.h> + +struct range_tree_node { +struct rb_node rb; +u64 start; +u64 end; +}; + +struct range_tree_root { +struct rb_root head; +}; + +static inline void range_tree_init (struct range_tree_root *root) +{ + root->head =RB_ROOT ; +} + +static inline void range_tree_node_init (struct range_tree_node *node) +{ +rb_init_node (&node->rb); + node->start =0 ; + node->end =0 ; +} + +static inline int range_tree_empty (struct range_tree_root *root) +{ +return RB_EMPTY_ROOT (&root->head); +} + +static inline +struct range_tree_node *range_tree_root_node (struct range_tree_root *root) +{ +struct range_tree_node *ret; + ret = container_of(root->head.rb_node, struct range_tree_node, rb); +return ret; +} + +extern struct range_tree_node *range_tree_in_range (struct range_tree_root *root, +u64 start,u64 end); +extern struct range_tree_node *range_tree_in_range_adjacent ( +struct range_tree_root *root, +u64 start,u64 end); +extern void range_tree_add (struct range_tree_root *root, +struct range_tree_node *node); +extern void range_tree_remove (struct range_tree_root *root, +struct range_tree_node *node); +#endif + +
lib/Makefile +1 -1
@@ -12,7 +12,7 @@ lib-y := ctype.o string.o vsprintf.o cmdline.o \ idr.o int_sqrt.o extable.o prio_tree.o \ sha1.o md5.o irq_regs.o reciprocal_div.o argv_split.o \ proportions.o prio_heap.o ratelimit.o show_mem.o \ - is_single_threaded.o plist.o decompress.o + is_single_threaded.o plist.o decompress.o rangetree.o lib-$(CONFIG_MMU) += ioremap.o lib-$(CONFIG_SMP) += cpumask.o
lib/rangetree.c new file +105 -0
105 lines not on this page · raw message
Signature · 1 line
1.7.3.2.146.gca209
Re: [PATCH 1/2] [RFC] Range tree implementation
Hi John,
Quoted 4 lines · John Stultz
After Andrew suggested something like his mumbletree idea to better store a list of ranges, I worked on a few different approaches, and this is what I've finally managed to get working.
Quoted 8 lines
I suspect range-tree isn't a totally accurate name, but I couldn't quite make out the difference between range trees and interval trees, so I just picked one to call it. Do let me know if you have a better name.
The idea of storing ranges in a tree is nice, but has a number of complications. When adding a range, its possible that a large range will consume and merge a number of smaller ranges.
Have you considered using 'prio_tree' (include/linux/prio_tree.h)? If we aim at addressing a wide range of possible use-cases (different patterns of adding/removing volatile ranges), then, at first glance, prio_tree looks like a better approach.
e.g. for the "consume and merge a number of smaller ranges" scenario above, prio_tree gives O(log n) [ O(log n + m) ] behavior iso O(m log
n) in your case.
--Dmitry
Re: [PATCH 1/2] [RFC] Range tree implementation
Quoted 12 lines · Dmitry Adamushko
Hi John,
Quoted 9 lines · John Stultz
After Andrew suggested something like his mumbletree idea to better store a list of ranges, I worked on a few different approaches, and this is what I've finally managed to get working.
I suspect range-tree isn't a totally accurate name, but I couldn't quite make out the difference between range trees and interval trees, so I just picked one to call it. Do let me know if you have a better name.
Quoted 7 lines
Quoted 3 lines
The idea of storing ranges in a tree is nice, but has a number of complications. When adding a range, its possible that a large range will consume and merge a number of smaller ranges.
Have you considered using '
prio_tree' (include/linux/prio_tree.h)? If we aim at addressing a wide range of possible use-cases (different patterns of adding/removing volatile ranges), then, at first glance,prio_treelooks like a better approach.
I'll take a closer look at that!
Quoted 3 lines
e.g. for the "consume and merge a number of smaller ranges" scenario above,
prio_treegives O(log n) [ O(log n + m) ] behavior iso O(m log
n) in your case.
Yea, one of the items I was looking at yesterday was to improve the range insert/remove usage, since I end up starting each lookup from the root node over and over. I'm thinking of adding a iterate-next type call so that we don't re-start the lookup each iteration of the loop once we've found an item.
Thanks again for the great feedback!
-john
Re: [PATCH 1/2] [RFC] Range tree implementation
In reply to John StultzJohn Stultz <[email protected]> writes:
....
Quoted 15 lines
(quoted diff) +15
-0+/** + * range_tree_in_range - Returns the first node that overlaps with the + * given range + * @root: range_tree root + * @start: range start + * @end: range end + * + */ +struct range_tree_node *range_tree_in_range(struct range_tree_root *root, + u64 start, u64 end) +{ + struct rb_node **p = &root->head.rb_node; + struct range_tree_node *candidate; + + while (*p) {
Review
Quoted 10 lines
(quoted diff) +10
-0+ candidate = rb_entry(*p, struct range_tree_node, rb); + if (end < candidate->start) + p = &(*p)->rb_left; + else if (start > candidate->end) + p = &(*p)->rb_right; + else + return candidate; + } + + return 0;
return NULL ?
Review
Quoted 11 lines
(quoted diff) +11
-0+} + + +/** + * range_tree_in_range - Returns the first node that overlaps or is adjacent + * with the given range + * @root: range_tree root + * @start: range start + * @end: range end + * + */
The comment needs update
Quoted 9 lines
(quoted diff) +9
-0+struct range_tree_node *range_tree_in_range_adjacent( + struct range_tree_root *root, + u64 start, u64 end) +{ + struct rb_node **p = &root->head.rb_node; + struct range_tree_node *candidate; + + while (*p) { + candidate = rb_entry(*p, struct range_tree_node, rb);
Review
Quoted 10 lines
(quoted diff) +10
-0+ if (end+1 < candidate->start) + p = &(*p)->rb_left; + else if (start > candidate->end + 1) + p = &(*p)->rb_right; + else + return candidate; + } + return 0; +} +
Below is my hack to get hugetlbfs code converted. The patch compiles. Will test and send a signed-off-by version later.
fs/hugetlbfs/inode.c | 3 +- include/linux/hugetlb.h | 2 + mm/hugetlb.c | 291 ++++++++++++++++++++++------------------------- 3 files changed, 139 insertions(+), 157 deletions(-)
fs/hugetlbfs/inode.c +2 -1
@@ -455,6 +455,7 @@ static struct inode *hugetlbfs_get_root(struct super_block *sb, inode->i_atime = inode->i_mtime = inode->i_ctime =CURRENT_TIME ; info =HUGETLBFS_I (inode);mpol_shared_policy_init (&info->policy,NULL ); +range_tree_init (&info->rg_root); inode->i_op = &hugetlbfs_dir_inode_operations; inode->i_fop = &simple_dir_operations;/* directory inodes start off with i_nlink == 2 (for "." entry) */
@@ -478,7 +479,6 @@ static struct inode *hugetlbfs_get_inode(struct super_block *sb, inode->i_mapping->a_ops = &hugetlbfs_aops; inode->i_mapping->backing_dev_info =&hugetlbfs_backing_dev_info; inode->i_atime = inode->i_mtime = inode->i_ctime =CURRENT_TIME ; -INIT_LIST_HEAD (&inode->i_mapping->private_list); info =HUGETLBFS_I (inode);/* * The policy is initialized here even if we are creating a
@@ -488,6 +488,7 @@ static struct inode *hugetlbfs_get_inode(struct super_block *sb,* the rb tree will still be empty. */ mpol_shared_policy_init (&info->policy,NULL ); +range_tree_init (&info->rg_root);switch (mode &S_IFMT ) {default :init_special_inode (inode, mode, dev);
include/linux/hugetlb.h +2 -0
@@ -5,6 +5,7 @@#include <linux/fs.h> #include <linux/hugetlb_inline.h> #include <linux/cgroup.h> +#include <linux/rangetree.h> struct ctl_table ;struct user_struct ;
@@ -150,6 +151,7 @@ struct hugetlbfs_sb_info {struct hugetlbfs_inode_info {struct shared_policy policy; +struct range_tree_root rg_root;struct inode vfs_inode; };
mm/hugetlb.c +135 -156
471 lines not on this page · raw message
RFC PATCH 2/2 fadvise: Add _VOLATILE,_ISVOLATILE, and _NONVOLATILE flags
In reply to John StultzThis 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.
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.
v2:
* After the valid critique that just dropping pages would poke holes in volatile ranges, and instead we should zap an entire range if we drop any of it, I changed the code to more closely mimic the ashmem implementation, which zaps entire ranges via a shrinker using an lru list that tracks which range has been marked volatile the longest.
v3:
* Reworked to use range tree implementation.
v4:
* Renamed functions to avoid confusion.
* More consistant PAGE_CACHE_SHIFT usage, suggested by Dmitry Adamushko
* Fixes exit without unlocking issue found by Dmitry Adamushko
* Migrate to rbtree based rangetree implementation
* Simplified locking to use global lock (we were grabbing global lru lock every time anyway).
* Avoid ENOMEM isses by allocating before we get into complicated code.
* Add some documentation to the volatile.c file from Neil Brown
Known issues:
* Lockdep doesn't like calling vmtruncate_range() from a shrinker. Any help here on how to address this would be appreciated. I've tried switching to invalidate_inode_pages2_range, but that always returns EBUSY in my testing, and I don't really want to launder dirty pages, instead I want to zap them.
* Concern over bloating the address_space struct
--- fs/inode.c | 4 + include/linux/fadvise.h | 5 + include/linux/fs.h | 2 + include/linux/volatile.h | 14 ++ mm/Makefile | 2 +- mm/fadvise.c | 16 +++- mm/volatile.c | 313 ++++++++++++++++++++++++++++++++++++++++++++++ 7 files changed, 354 insertions(+), 2 deletions(-) create mode 100644 include/linux/volatile.h create mode 100644 mm/volatile.c
fs/inode.c +4 -0
@@ -27,6 +27,7 @@#include <linux/cred.h> #include <linux/buffer_head.h> /* for inode_has_buffers */ #include <linux/ratelimit.h> +#include <linux/volatile.h> #include "internal.h" /*
@@ -254,6 +255,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);
@@ -360,6 +362,8 @@ 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); +range_tree_init (&mapping->volatile_root); + }EXPORT_SYMBOL (address_space_init_once);
include/linux/fadvise.h +5 -0
@@ -18,4 +18,9 @@#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 */ + + +#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/rangetree.h> /* * It's silly to have NR_OPEN bigger than NR_FILE, but you can change
@@ -655,6 +656,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 range_tree_root volatile_root;/* volatile range list */ } __attribute__((aligned(sizeof(long))));/* * On most architectures that alignment is already the case; but
include/linux/volatile.h new file +14 -0
@@ -0,0 +1,14 @@ +#ifndef _LINUX_VOLATILE_H +#define _LINUX_VOLATILE_H + +#include <linux/fs.h> + +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 +15 -1
@@ -17,6 +17,7 @@#include <linux/fadvise.h> #include <linux/writeback.h> #include <linux/syscalls.h> +#include <linux/volatile.h> #include <asm/unistd.h>
@@ -106,7 +107,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);
@@ -128,6 +129,19 @@ 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 ;default : ret = -EINVAL ; }
mm/volatile.c new file +313 -0
313 lines not on this page · raw message
Signature · 1 line
1.7.3.2.146.gca209
PATCH 1/1 fadvise volatile fixes from Dmitry
Quoted 3 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.
Right after sending this I realized I had forgotten to include some fixes for issues Dmitry pointed out. So I've included them here.
--- mm/volatile.c | 5 +++-- 1 files changed, 3 insertions(+), 2 deletions(-)
mm/volatile.c +3 -2
@@ -220,11 +220,12 @@ long mapping_range_nonvolatile(struct address_space *mapping, new->mapping = mapping; new->range_node.start = end +1 ; new->range_node.end = node->end; -volatile_range_resize (vrange, node->start, start-1 ); + new->purged = vrange->purged;range_tree_add (&mapping->volatile_root, &new->range_node);if (range_on_lru (new))lru_add (new); +volatile_range_resize (vrange, node->start, start-1 );break ; }
@@ -263,7 +264,7 @@ void mapping_clear_volatile_ranges(struct address_space *mapping)static int volatile_shrink (struct shrinker *ignored,struct shrink_control *sc) {struct volatile_range *range, *next; -unsigned long nr_to_scan = sc->nr_to_scan; +s64 nr_to_scan = sc->nr_to_scan;const gfp_t gfp_mask = sc->gfp_mask;if (nr_to_scan&& !(gfp_mask& __GFP_FS))
Signature · 1 line
1.7.3.2.146.gca209
Re: [PATCH 2/2] [RFC] fadvise: Add _VOLATILE,_ISVOLATILE, and _NONVOLATILE flags
In reply to John StultzHi John,
[ ... ]
Quoted 36 lines
mm/volatile.c new file +36
-0+/* +* Mark a region as volatile, allowing dirty pages to be purged +* under memory pressure +*/ +long mapping_range_volatile (struct address_space *mapping, + pgoff_t start_index, pgoff_t end_index) +{ + struct volatile_range *new; + struct range_tree_node *node; + + u64 start, end; + int purged = 0; + start = (u64)start_index; + end = (u64)end_index; + + new = vrange_alloc(); + if (!new) + return -ENOMEM; + + mutex_lock(&volatile_mutex); + + node = range_tree_in_range_adjacent(&mapping->volatile_root, + start, end); + while (node) { + struct volatile_range *vrange; + + /* Already entirely marked volatile, so we're done */ + if (node->start < start && node->end > end) { + /* don't need the allocated value */ + kfree(new); + goto out; + } + + /* Grab containing volatile range */ + vrange = container_of(node, struct volatile_range, range_node); +
mm/volatile.c line 162
Quoted 10 lines
mm/volatile.c new file +10
-0+ /* resize range */ + start = min_t(u64, start, node->start); + end = max_t(u64, end, node->end); + purged |= vrange->purged; + + + vrange_del(vrange); + + /* get the next possible overlap */ + node = range_tree_in_range(&mapping->volatile_root, start, end);
I guess range_tree_in_range_adjacent() should be used here again. There can be 2 adjacent regions (left and right), and we'll miss one of them with range_tree_in_range().
Also (as I had already mentioned before), I think that new ranges must not be merged with the existing "vrange->purged == 1" ranges. Otherwise, for some use cases, the whole idea of 'volatility' gets broken. For example, when an application is processing a big buffer in small consequent chunks (marking a chunk as volatile when done with it), and the range gets 'purged' by the kernel early in this process (when it's still small).
-- Dmitry
Re: [PATCH 2/2] [RFC] fadvise: Add _VOLATILE,_ISVOLATILE, and _NONVOLATILE flags
Quoted 55 lines · Dmitry Adamushko
Hi John,
[ ... ]
Quoted 36 lines
mm/volatile.c new file +36
-0+/* +* Mark a region as volatile, allowing dirty pages to be purged +* under memory pressure +*/ +long mapping_range_volatile (struct address_space *mapping, + pgoff_t start_index, pgoff_t end_index) +{ + struct volatile_range *new; + struct range_tree_node *node; + + u64 start, end; + int purged = 0; + start = (u64)start_index; + end = (u64)end_index; + + new = vrange_alloc(); + if (!new) + return -ENOMEM; + + mutex_lock(&volatile_mutex); + + node = range_tree_in_range_adjacent(&mapping->volatile_root, + start, end); + while (node) { + struct volatile_range *vrange; + + /* Already entirely marked volatile, so we're done */ + if (node->start < start && node->end > end) { + /* don't need the allocated value */ + kfree(new); + goto out; + } + + /* Grab containing volatile range */ + vrange = container_of(node, struct volatile_range, range_node); +mm/volatile.c line 162
Quoted 10 lines
mm/volatile.c new file +10
-0+ /* resize range */ + start = min_t(u64, start, node->start); + end = max_t(u64, end, node->end); + purged |= vrange->purged; + + + vrange_del(vrange); + + /* get the next possible overlap */ + node = range_tree_in_range(&mapping->volatile_root, start, end);I guess
range_tree_in_range_adjacent()should be used here again. There can be 2 adjacent regions (left and right), and we'll miss one of them withrange_tree_in_range().
Quoted 7 lines
Also (as I had already mentioned before), I think that new ranges must not be merged with the existing "
vrange->purged== 1" ranges. Otherwise, for some use cases, the whole idea of 'volatility' gets broken. For example, when an application is processing a big buffer in small consequent chunks (marking a chunk as volatile when done with it), and the range gets 'purged' by the kernel early in this process (when it's still small).
Alternatively, we could immediately truncate purged==0 ranges (including the one for which mapping_range_volatile() is called) when merging them with purged==1 ranges. This would result in a more consistent, but perhaps too aggressive behavior.
Let's consider the following use case:
[1, 10] is an existing purged==1 volatile region, and an application declares [11, 12] as volatile.
1) current approach: [1, 12] a single purged==1 region, where [11, 12] was not really truncated (and it could have been [11, 100]);
2) aggressive purge-it-all approach: a single [1, 12] purged==1 region. The newly added region gets truncated even when there is no shortage of memory at the moment of addition.
3) do-not-merge approach: [1, 10] purged==1 and [11, 12] purged==0 regions; the later is on the lru list.
it adds extra complexities though (e.g. the need to merge purged ranges in the shrinker code).
But what's more important, do we have a model of application behavior that is expected to be observed in, say, 90+% of cases? What patterns are more common?
For example,
1) make_volatile [1, 10] ; ... ; make_volatile [5, 15] //
overlapping volatile regions
2) make_volatile [1, 10] ; ... ; make_volatile [1, 15] // explicit merge
3) make_volatile [1, 10] ; ... ; make_volatile [11, 15] // adjacent volatile regions
I guess (2) and (3) would be more common, and (3) even more so with independently used regions (say, by different threads). For (3), do we really want to merge purged==0 regions when they are adjacent? What if they are used independently? Let's consider this case:
(a) make_volatile [1, 100] ; ... ; (z) make_volatile [101, 102]
(z) region is used much more frequently by the application [ make_nonvolatile -> do-smth -> make_volatile ], and (a) is not used often - it's volatile most of the time. If we merge both regions when they are still purged==0, the whole [1, 102] will tend to be at the end of the LRU list =>
- we miss an opportunity to truncate (a);
- other regions that are more frequently used than (a) get truncated.
In this light, (3) would be better off behaving as if (a) and (z) were not adjacent, i.e. no merge...
-- Dmitry
Re: [PATCH 2/2] [RFC] fadvise: Add _VOLATILE,_ISVOLATILE, and _NONVOLATILE flags
In reply to Dmitry AdamushkoQuoted 45 lines · Dmitry Adamushko
Hi John,
[ ... ]
Quoted 41 lines
mm/volatile.c new file +41
-0+/* +* Mark a region as volatile, allowing dirty pages to be purged +* under memory pressure +*/ +long mapping_range_volatile (struct address_space *mapping, +pgoff_t start_index,pgoff_t end_index) +{ +struct volatile_range *new; +struct range_tree_node *node; + +u64 start, end; +int purged =0 ; + start = (u64 )start_index; + end = (u64 )end_index; + + new =vrange_alloc (); +if (!new) +return -ENOMEM ; + +mutex_lock (&volatile_mutex); + + node =range_tree_in_range_adjacent (&mapping->volatile_root, + start, end); +while (node) { +struct volatile_range *vrange; + +/* Already entirely marked volatile, so we're done */ +if (node->start< start&& node->end> end) { +/* don't need the allocated value */ +kfree (new); + goto out; + } + +/* Grab containing volatile range */ + vrange = container_of(node, struct volatile_range, range_node); + +/* resize range */ + start =min_t (u64, start, node->start); + end =max_t (u64, end, node->end); + purged |= vrange->purged; +
Quoted 8 lines
mm/volatile.c line 162
Quoted 5 lines
mm/volatile.c new file +5
-0+ +vrange_del (vrange); + +/* get the next possible overlap */ + node =range_tree_in_range (&mapping->volatile_root, start, end);I guess
range_tree_in_range_adjacent()should be used here again. There can be 2 adjacent regions (left and right), and we'll miss one of them withrange_tree_in_range().
Good catch, thank you!
Quoted 8 lines
Also (as I had already mentioned before), I think that new ranges must not be merged with the existing "
vrange->purged== 1" ranges. Otherwise, for some use cases, the whole idea of 'volatility' gets broken. For example, when an application is processing a big buffer in small consequent chunks (marking a chunk as volatile when done with it), and the range gets 'purged' by the kernel early in this process (when it's still small).
I agree that this seems like a much more intelligent way coalesce regions. I hadn't yet implemented it, as I was hoping for some comment from the Android folks if there was a specific use for the design they selected for ashmem, but I suspect there isn't.
I'll go ahead and integrate this for the next revision.
Thanks again for the feedback!
-john
Quoted 6 lines · John Stultz <john.stultz <at> linaro.org> writes:
Ok. So here's another iteration of the fadvise volatile range code.
I realize this is still a way off from being ready, but I wanted to post what I have to share with folks working on the various range/interval management ideas as well as update folks who've provided feedback on the volatile range code.
Hi John,
May you please confirm whether the fadvise(FADV_VOLATILE) will work for me in the following case?
I am developing a dynamic data race detector (ThreadSanitizer). It needs to associate some meta-data (shadow) with each byte of application memory (4 bytes of shadow for 1 byte of app memory). We mmap(MAP_ANONYMOUS|MAP_NORESERVE)
40TB of virtual address space for
shadow, and then just access it as needed. It works.
But for some apps that consume too much
memory, it eventually leads to swapping/OOM kills.
There is a property of shadow memory that I would like to exploit
- any region of shadow memory can be reset to zero at any point
w/o any bad consequences (it can lead to missed data races, but it's better than OOM kill).
I've tried to execute madvise(MADV_DONTNEED) every X seconds for whole shadow memory. It almost works.
The problem is that madvise() seems to be
not atomic, occasionally I see missed writes, that's not acceptable, I need either zero pages or
consistent pages.
Your FADV_VOLATILE looks like it may be the solution.
To summarize: I have a huge region of memory that
I would like to mark as "volatile" at program
startup. The region is anonymous (not backed by any file). The kernel must be able to take away
any pages in the range, and then return zero pages later. I do have concurrent writes to the
range, and missed writes are unacceptable.
Ideally, pages are revoked on LRU basis
TIA
A message that is not in the archive (sent off-list or not yet received): CAO6Zf6BSpq53UqYjCkq0b3pTPW=WDTnCorQ59tONnV7U-U6EOg@mail.gmail.com
A message that is not in the archive (sent off-list or not yet received): CACT4Y+ZgBo9=HX5MHhmWBiQcdiGMss9RSS_reF4gJimivJx7sQ@mail.gmail.com
[ cc: lkml ]
Quoted 28 lines
Quoted 22 lines
Quoted 8 lines
There is a property of shadow memory that I would like to exploit
- any region of shadow memory can be reset to zero at any point
w/o any bad consequences (it can lead to missed data races, but it's better than OOM kill).
I've tried to executemadvise(MADV_DONTNEED)every X seconds for whole shadow memory. It almost works.
The problem is thatmadvise()seems to be
not atomic, occasionally I see missed writes, that's not acceptable,Just to be sure, you mean that if you do, say
*ptr = 1; // [1]
...
value = *ptr; // [2] value is 1 here
...
*ptr = 2; // possibly from another thread, but we can be certain that it's after [1], perhaps because we checked the content with [2]
...
//madvise(..., MADV_DONTNEED); _might_ have been called
...
value = *ptr;Quoted 3 lines
so here we expect 'value' to be either 2 or 0 (zero page iff
madvise()did take place), but you get '1' occasionally?
Is that what you mean or something else?
Quoted 6 lines
Yes, that's what I mean.
Basically I observed inconsistent state of memory that must never happen. I had no other explanations except that themadvise()call works as a time machine. I executedmadvise()every 3 seconds, and the inconsistencies happened exactly at the same times. When I turned offmadvise(), the problems disappear.
Did you try disabling swapping? The "time machine" (if it's not a problem somewhere else) should take old stuff from somewhere.
mmap's man indicates "zero-fill-on-demand pages for mappings without an underlying file" and the comment in madvise_dontneed() says "Be sure to free swap resources too", but then looking at the code in zap_pte_ranges(), there are a few corner cases where swap entries seem to be left over intact. In any case, given that you can reproduce it easily, it'll be a quick check.
Also, it's a MAP_PRIVATE mapping, isn't it?
Quoted 66 lines
I am not sure whether it's a bug or not, because the man says "For the time being, the application is finished with the given range", and we are obviously do not since we have concurrent accesses. However I would be great if it is "fixed".
Quoted 9 lines
Quoted 8 lines
I need either zero pages or
consistent pages.
YourFADV_VOLATILElooks like it may be the solution. To summarize: I have a huge region of memory that I would like to mark as "volatile" at program startup. The region is anonymous (not backed by any file). The kernel must be able to take away
any pages in the range, and then return zero pages later.Quoted 3 lines
I guess that for the use-cases that people have considered so far, users are supposed to mark regions NONVOLATILE before accessing them again. If I understand correctly, that's not what you want to do...
No, it's not what I want to do. I can't do any tracking during accesses. Ideally I just mark the range during startup, it's also possible to do some work on a periodic basis.
Quoted 11 lines
does it mean that your 'transactions' are always write-a-single-word? i.e. you don't need to make sure that, say, in
ptr[0] =
val_a;
ptr[1] =val_b;
... // no accesses to ptr [0] and [1]
c = ptr[0];
d = ptr[1];either c ==
val_aand d ==val_bor both are 0?Exactly. Any transaction first issues N independent 8-byte atomic reads, and then optionally 1 atomic 8-byte write. Value of 0 especially means "no data here", because, well, I do not want to setup 40TB of memory to some other value :)
Quoted 6 lines
Also, the current implementation of volatile-ranges will try to 'zap' the whole volatile range... not just some of its pages. Perhaps, it's not something you need too. Of course, this can be addressed one way or another.
Well, yes, it's not ideal (but we had lived with
MADV_DONTNEEDfor the whole range for some time). Ideally, kernel just takes pages away as it needs them.Quoted 4 lines
Basically, in your specific case, the pages of your region should be, kind of, swapped out to
/dev/zero:-)) meaning that once the system decides to swap such a page out, no actual swap is required and, once the area is being accessed again, a zero-page is mapped into it.
Quoted 6 lines
Yes, I believe that's how
MADV_DONTNEEDcurrently works (... or zero-fill-on-demand pages for mappings without an underlying file). Also the pages must be "swapped out" with higher prio.
I think what I want is somewhat similar to page cache. Kind of best effort LRU caching.
-- Dmitry