readahead: page flag PG_readahead
Subsystems (12)
A message that is not in the archive (sent off-list or not yet received): [email protected]
PATCH 2/33 radixtree: look-aside cache
Introduce a set of lookup functions to radix tree for the read-ahead logic. Other access patterns with high locality may also benefit from them.
- radix_tree_lookup_parent(root, index, level)
Perform partial lookup, return the @level'th parent of the slot at @index.
- radix_tree_cache_xxx()
Init/Query the cache.
- radix_tree_cache_lookup(root, cache, index)
Perform lookup with the aid of a look-aside cache.
For sequential scans, it has a time complexity of 64*O(1) + 1*O(logN).
Typical usage:
void func() {
+ struct radix_tree_cache cache;
+
+ radix_tree_cache_init(&cache);
read_lock_irq(&mapping->tree_lock);
for(;;) {
- page = radix_tree_lookup(&mapping->page_tree, index);
+ page = radix_tree_cache_lookup(&mapping->page_tree, &cache, index);
}
read_unlock_irq(&mapping->tree_lock);
} ---
include/linux/radix-tree.h | 83 +++++++++++++++++++++++++++++++++++ lib/radix-tree.c | 104 ++++++++++++++++++++++++++++++++++----------- 2 files changed, 161 insertions(+), 26 deletions(-)
include/linux/radix-tree.h +81 -2
@@ -26,12 +26,29 @@#define RADIX_TREE_MAX_TAGS 2/* root tags are stored in gfp_mask, shifted by __GFP_BITS_SHIFT */ +#ifdef __KERNEL__ +#define RADIX_TREE_MAP_SHIFT (CONFIG_BASE_SMALL ? 4 : 6) +#else +#define RADIX_TREE_MAP_SHIFT 3/* For more stressful testing */ +#endif + +#define RADIX_TREE_MAP_SIZE (1UL << RADIX_TREE_MAP_SHIFT) +#define RADIX_TREE_MAP_MASK (RADIX_TREE_MAP_SIZE-1) +struct radix_tree_root {unsigned int height;gfp_t gfp_mask;struct radix_tree_node *rnode; }; +/* +* Lookaside cache to support access patterns with strong locality. +*/ +struct radix_tree_cache { +unsigned long first_index; +struct radix_tree_node *tree_node; +}; +#define RADIX_TREE_INIT (mask) { \ .height = 0, \ .gfp_mask = (mask), \
@@ -49,9 +66,14 @@ do { \ }while (0 ) int radix_tree_insert(struct radix_tree_root *, unsigned long, void *); -void *radix_tree_lookup (struct radix_tree_root *,unsigned long ); -void **radix_tree_lookup_slot (struct radix_tree_root *,unsigned long ); +void *radix_tree_lookup_parent (struct radix_tree_root *,unsigned long , +unsigned int ); +void **radix_tree_lookup_slot (struct radix_tree_root *root,unsigned long );void *radix_tree_delete (struct radix_tree_root *,unsigned long ); +unsigned int radix_tree_cache_count (struct radix_tree_cache *cache); +void *radix_tree_cache_lookup_parent (struct radix_tree_root *root, +struct radix_tree_cache *cache, +unsigned long index,unsigned int level);unsigned int radix_tree_gang_lookup (struct radix_tree_root *root,void **results,unsigned long first_index,unsigned int max_items);
@@ -74,4 +96,61 @@ static inline void radix_tree_preload_en preempt_enable(); } +/** +* radix_tree_lookup - perform lookup operation on a radix tree +* @root: radix tree root +* @index: index key +* +* Lookup the item at the position @index in the radix tree @root. +*/ +static inline void *radix_tree_lookup (struct radix_tree_root *root, +unsigned long index) +{ +return radix_tree_lookup_parent (root, index,0 ); +} + +/** +* radix_tree_cache_init - init a look-aside cache +* @cache: look-aside cache +* +* Init the radix tree look-aside cache @cache. +*/ +static inline void radix_tree_cache_init (struct radix_tree_cache *cache) +{ + cache->first_index =RADIX_TREE_MAP_MASK ; + cache->tree_node =NULL ; +} + +/** +* radix_tree_cache_lookup - cached lookup on a radix tree +* @root: radix tree root +* @cache: look-aside cache +* @index: index key +* +* Lookup the item at the position @index in the radix tree @root, +* and make use of @cache to speedup the lookup process. +*/ +static inline void *radix_tree_cache_lookup (struct radix_tree_root *root, +struct radix_tree_cache *cache, +unsigned long index) +{ +return radix_tree_cache_lookup_parent (root, cache, index,0 ); +} + +static inline unsigned int radix_tree_cache_size (struct radix_tree_cache *cache) +{ +return RADIX_TREE_MAP_SIZE ; +} + +static inline int radix_tree_cache_full (struct radix_tree_cache *cache) +{ +return radix_tree_cache_count (cache) ==radix_tree_cache_size (cache); +} + +static inline unsigned long +radix_tree_cache_first_index (struct radix_tree_cache *cache) +{ +return cache->first_index; +} +#endif /* _LINUX_RADIX_TREE_H */
lib/radix-tree.c +80 -24
141 lines not on this page · raw message
--
PATCH 3/33 radixtree: hole scanning functions
In reply to a message not in the archiveIntroduce a pair of functions to scan radix tree for hole/empty item.
include/linux/radix-tree.h | 4 + lib/radix-tree.c | 104 +++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 108 insertions(+)
---
include/linux/radix-tree.h +4 -0
@@ -74,6 +74,10 @@ unsigned int radix_tree_cache_count(struvoid *radix_tree_cache_lookup_parent (struct radix_tree_root *root,struct radix_tree_cache *cache,unsigned long index,unsigned int level); +unsigned long radix_tree_scan_hole_backward (struct radix_tree_root *root, +unsigned long index,unsigned long max_scan); +unsigned long radix_tree_scan_hole (struct radix_tree_root *root, +unsigned long index,unsigned long max_scan);unsigned int radix_tree_gang_lookup (struct radix_tree_root *root,void **results,unsigned long first_index,unsigned int max_items);
lib/radix-tree.c +104 -0
110 lines not on this page · raw message
--
Re: [PATCH 03/33] radixtree: hole scanning functions
Quoted 3 lines · Wu Fengguang
Introduce a pair of functions to scan radix tree for hole/empty item.
There's a userspace radix-tree test harness at
http://www.zip.com.au/~akpm/linux/patches/stuff/rtth.tar.gz.
If/when these new features are merged up, it would be good to have new testcases added to that suite, please.
In the meanwhile you may care to develop those tests anwyway, see if you can trip up the new features.
Re: [PATCH 03/33] radixtree: hole scanning functions
Quoted 5 lines · Andrew Morton
Quoted 3 lines · Wu Fengguang
Introduce a pair of functions to scan radix tree for hole/empty item.
Quoted 8 lines
There's a userspace radix-tree test harness at
http://www.zip.com.au/~akpm/linux/patches/stuff/rtth.tar.gz.If/when these new features are merged up, it would be good to have new testcases added to that suite, please.
In the meanwhile you may care to develop those tests anwyway, see if you can trip up the new features.
Handy tool.
I'll update it with the newly introduced functions, and write corresponding test cases.
Thanks,
Wu
Re: [PATCH 03/33] radixtree: hole scanning functions
In reply to Andrew MortonQuoted 5 lines · Andrew Morton
Quoted 3 lines · Wu Fengguang
Introduce a pair of functions to scan radix tree for hole/empty item.
Quoted 8 lines
There's a userspace radix-tree test harness at
http://www.zip.com.au/~akpm/linux/patches/stuff/rtth.tar.gz.If/when these new features are merged up, it would be good to have new testcases added to that suite, please.
In the meanwhile you may care to develop those tests anwyway, see if you can trip up the new features.
The new radix-tree.c/.h breaks compiling terribly.
Are there any particular reason not to implement it as a module?
Re: [PATCH 03/33] radixtree: hole scanning functions
Quoted 10 lines · Wu Fengguang
Quoted 8 lines · Andrew Morton
Quoted 3 lines · Wu Fengguang
Introduce a pair of functions to scan radix tree for hole/empty item.
There's a userspace radix-tree test harness at
http://www.zip.com.au/~akpm/linux/patches/stuff/rtth.tar.gz.
Quoted 7 lines
Quoted 5 lines
If/when these new features are merged up, it would be good to have new testcases added to that suite, please.
In the meanwhile you may care to develop those tests anwyway, see if you can trip up the new features.
The new radix-tree.c/.h breaks compiling terribly.
Sprinkling more stub header files in there usually fixes that.
Quoted 1 line
Are there any particular reason not to implement it as a module?
Well. It's a heck of a lot more convenient to throw testcases at a userspace app, and to debug it and to performance analyse it.
PATCH 4/33 readahead: page flag PG_readahead
In reply to a message not in the archiveAn new page flag PG_readahead is introduced as a look-ahead mark, which reminds the caller to give the adaptive read-ahead logic a chance to do read-ahead ahead of time for I/O pipelining.
It roughly corresponds to `ahead_start' of the stock read-ahead logic.
---
include/linux/page-flags.h | 5 +++++ mm/page_alloc.c | 2 +- 2 files changed, 6 insertions(+), 1 deletion(-)
include/linux/page-flags.h +5 -0
@@ -89,6 +89,7 @@#define PG_reclaim 17/* To be reclaimed asap */ #define PG_nosave_free 18/* Free, should not be written */ #define PG_buddy 19/* Page is free, on buddy lists */ +#define PG_readahead 20/* Reminder to do readahead */ #if (BITS_PER_LONG >32 )
@@ -372,6 +373,10 @@ extern void __mod_page_state_offset(unsi#define SetPageUncached (page) set_bit(PG_uncached, &(page)->flags)#define ClearPageUncached (page) clear_bit(PG_uncached, &(page)->flags) +#define PageReadahead (page) test_bit(PG_readahead, &(page)->flags) +#define __SetPageReadahead (page) __set_bit(PG_readahead, &(page)->flags) +#define TestClearPageReadahead (page) test_and_clear_bit(PG_readahead, &(page)->flags) +struct page ;/* forward declaration */ int test_clear_page_dirty (struct page *page);
mm/page_alloc.c +1 -1
@@ -564,7 +564,7 @@ static int prep_new_page(struct page *paif (PageReserved (page))return 1 ; - page->flags &= ~(1 << PG_uptodate |1 << PG_error | + page->flags &= ~(1 << PG_uptodate |1 << PG_error |1 << PG_readahead |1 << PG_referenced |1 << PG_arch_1 |1 << PG_checked |1 << PG_mappedtodisk);set_page_private (page,0 );
--
Quoted 7 lines · Wu Fengguang
An new page flag
PG_readaheadis introduced as a look-ahead mark, which reminds the caller to give the adaptive read-ahead logic a chance to do read-ahead ahead of time for I/O pipelining.It roughly corresponds to `ahead_start' of the stock read-ahead logic.
This isn't a very revealing description of what this flag does.
Quoted 1 line
+#define
__SetPageReadahead(page)__set_bit(PG_readahead, &(page)->flags)
uh-oh. This is extremly risky. Needs extensive justification, please.
Quoted 10 lines · Andrew Morton
Quoted 7 lines · Wu Fengguang
An new page flag
PG_readaheadis introduced as a look-ahead mark, which reminds the caller to give the adaptive read-ahead logic a chance to do read-ahead ahead of time for I/O pipelining.It roughly corresponds to `ahead_start' of the stock read-ahead logic.
This isn't a very revealing description of what this flag does.
Updated to:
An new page flag PG_readahead is introduced.
It acts as a look-ahead mark, which tells the page reader:
Hey, it's time to invoke the adaptive read-ahead logic! For the sake of I/O pipelining, don't wait until it runs out of cached pages. ;-)
Quoted 3 lines
Quoted 1 line
+#define
__SetPageReadahead(page)__set_bit(PG_readahead, &(page)->flags)uh-oh. This is extremly risky. Needs extensive justification, please.
Ok, removed the ugly __ :-)
Wu
PATCH 5/33 readahead: refactor do_generic_mapping_read()
In reply to a message not in the archiveIn do_generic_mapping_read(), release accessed pages some time later, so that it can be passed to and used by the adaptive read-ahead code.
---
mm/filemap.c | 18 ++++++++++++------ 1 files changed, 12 insertions(+), 6 deletions(-)
mm/filemap.c +12 -6
@@ -813,10 +813,12 @@ void do_generic_mapping_read(struct addrunsigned long prev_index;loff_t isize;struct page *cached_page; +struct page *prev_page;int error;struct file_ra_state ra = *_ra; cached_page =NULL ; + prev_page =NULL ; index = *ppos >>PAGE_CACHE_SHIFT ; next_index = index; prev_index = ra.prev_page;
@@ -855,6 +857,11 @@ find_page:handle_ra_miss (mapping, &ra, index); goto no_cached_page; } + +if (prev_page) +page_cache_release (prev_page); + prev_page = page; +if (!PageUptodate (page)) goto page_not_up_to_date; page_ok:
@@ -889,7 +896,6 @@ page_ok: index += offset >>PAGE_CACHE_SHIFT ; offset &= ~PAGE_CACHE_MASK ; -page_cache_release (page);if (ret == nr && desc->count)continue ; goto out;
@@ -901,7 +907,6 @@ page_not_up_to_date:/* Did it get unhashed before we got the lock? */ if (!page->mapping) {unlock_page (page); -page_cache_release (page);continue ; }
@@ -931,7 +936,6 @@ readpage:* invalidate_inode_pages got it */ unlock_page (page); -page_cache_release (page); goto find_page; }unlock_page (page);
@@ -952,7 +956,6 @@ readpage: isize =i_size_read (inode); end_index = (isize -1 ) >>PAGE_CACHE_SHIFT ;if (unlikely (!isize || index > end_index)) { -page_cache_release (page); goto out; }
@@ -961,7 +964,6 @@ readpage:if (index == end_index) { nr = ((isize -1 ) & ~PAGE_CACHE_MASK ) +1 ;if (nr <= offset) { -page_cache_release (page); goto out; } }
@@ -971,7 +973,6 @@ readpage: readpage_error:/* UHHUH! A synchronous read error occurred. Report it */ desc->error = error; -page_cache_release (page); goto out; no_cached_page:
@@ -996,6 +997,9 @@ no_cached_page: } page = cached_page; cached_page =NULL ; +if (prev_page) +page_cache_release (prev_page); + prev_page = page; goto readpage; }
@@ -1005,6 +1009,8 @@ out: *ppos = ((loff_t ) index <<PAGE_CACHE_SHIFT ) + offset;if (cached_page)page_cache_release (cached_page); +if (prev_page) +page_cache_release (prev_page);if (filp)file_accessed (filp); }
--
PATCH 6/33 readahead: refactor __do_page_cache_readahead()
In reply to a message not in the archiveAdd look-ahead support to __do_page_cache_readahead(), which is needed by the adaptive read-ahead logic.
---
mm/readahead.c | 15 +++++++++------ 1 files changed, 9 insertions(+), 6 deletions(-)
mm/readahead.c +9 -6
@@ -266,7 +266,8 @@ out:*/ static int __do_page_cache_readahead (struct address_space *mapping,struct file *filp, -pgoff_t offset,unsigned long nr_to_read) +pgoff_t offset,unsigned long nr_to_read, +unsigned long lookahead_size) {struct inode *inode = mapping->host;struct page *page;
@@ -279,7 +280,7 @@ __do_page_cache_readahead(struct addressif (isize ==0 ) goto out; - end_index = ((isize -1 ) >>PAGE_CACHE_SHIFT ); + end_index = ((isize -1 ) >>PAGE_CACHE_SHIFT );/* * Preallocate as many pages as we will need.
@@ -302,6 +303,8 @@ __do_page_cache_readahead(struct addressbreak ; page->index = page_offset;list_add (&page->lru, &page_pool); +if (page_idx == nr_to_read - lookahead_size) +__SetPageReadahead (page); ret++; }read_unlock_irq (&mapping->tree_lock);
@@ -338,7 +341,7 @@ int force_page_cache_readahead(struct adif (this_chunk > nr_to_read) this_chunk = nr_to_read; err =__do_page_cache_readahead (mapping, filp, - offset, this_chunk); + offset, this_chunk,0 );if (err <0 ) { ret = err;break ;
@@ -385,7 +388,7 @@ int do_page_cache_readahead(struct addreif (bdi_read_congested (mapping->backing_dev_info))return -1 ; -return __do_page_cache_readahead (mapping, filp, offset, nr_to_read); +return __do_page_cache_readahead (mapping, filp, offset, nr_to_read,0 ); }/*
@@ -405,7 +408,7 @@ blockable_page_cache_readahead(struct adif (!block &&bdi_read_congested (mapping->backing_dev_info))return 0 ; - actual =__do_page_cache_readahead (mapping, filp, offset, nr_to_read); + actual =__do_page_cache_readahead (mapping, filp, offset, nr_to_read,0 );return check_ra_success (ra, nr_to_read, actual); }
@@ -450,7 +453,7 @@ static int make_ahead_window(struct addr* @req_size: hint: total size of the read which the caller is performing in * PAGE_CACHE_SIZE units * -* page_cache_readahead() is the main function. If performs the adaptive +* page_cache_readahead() is the main function. It performs the adaptive * readahead window size management and submits the readahead I/O. * * Note that @filp is purely used for passing on to the ->readpage[s]()
--
Re: [PATCH 06/33] readahead: refactor __do_page_cache_readahead()
Quoted 3 lines · Wu Fengguang
Add look-ahead support to
__do_page_cache_readahead(), which is needed by the adaptive read-ahead logic.
You'd need to define "look-ahead support" before telling us you've added it ;)
mm/readahead.c __do_page_cache_readahead(struct address · line 309
Quoted 8 lines
mm/readahead.c +2
-0@@ -302,6 +303,8 @@ __do_page_cache_readahead(struct addressbreak ; page->index = page_offset;list_add (&page->lru, &page_pool); +if (page_idx == nr_to_read - lookahead_size) +__SetPageReadahead (page); ret++; }
OK. But the __SetPageFoo() things still give me the creeps.
OT: look:
read_unlock_irq(&mapping->tree_lock); page = page_cache_alloc_cold(mapping); read_lock_irq(&mapping->tree_lock);
we should have a page allocation function which just allocates a page from this CPU's per-cpu-pages magazine, and fails if the magazine is empty:
page = alloc_pages_local(mapping_gfp_mask(x)|__GFP_COLD);
if (!page) {
read_unlock_irq(&mapping->tree_lock);
/*
* This will refill the per-cpu-pages magazine
*/
page = page_cache_alloc_cold(mapping);
read_lock_irq(&mapping->tree_lock);
}Re: [PATCH 06/33] readahead: refactor __do_page_cache_readahead()
Quoted 11 lines · Andrew Morton
mm/readahead.c __do_page_cache_readahead(struct address · line 309
Quoted 8 lines · Wu Fengguang
mm/readahead.c +2
-0@@ -302,6 +303,8 @@ __do_page_cache_readahead(struct addressbreak ; page->index = page_offset;list_add (&page->lru, &page_pool); +if (page_idx == nr_to_read - lookahead_size) +__SetPageReadahead (page); ret++; }OK. But the
__SetPageFoo()things still give me the creeps.
I just hope that Wu Fengguang, or whoever is making these patches, realizes that on some architectures, doing __set_bit on one CPU concurrently with another CPU doing set_bit on a different bit in the same word can result in the second CPU's update getting lost...
Paul.
Re: [PATCH 06/33] readahead: refactor __do_page_cache_readahead()
Quoted 15 lines · Paul Mackerras
Quoted 11 lines · Andrew Morton
mm/readahead.c __do_page_cache_readahead(struct address · line 309
Quoted 8 lines · Wu Fengguang
mm/readahead.c +2
-0@@ -302,6 +303,8 @@ __do_page_cache_readahead(struct addressbreak ; page->index = page_offset;list_add (&page->lru, &page_pool); +if (page_idx == nr_to_read - lookahead_size) +__SetPageReadahead (page); ret++; }OK. But the
__SetPageFoo()things still give me the creeps.
Quoted 5 lines
I just hope that Wu Fengguang, or whoever is making these patches, realizes that on some architectures, doing
__set_biton one CPU concurrently with another CPU doingset_biton a different bit in the same word can result in the second CPU's update getting lost...
That's true even on x86.
Yes, this is understood - in this case he's following Nick's dubious lead in leveraging our knowledge that no other code path will be attempting to modify this page's flags at this time. It's just been taken off the freelist, it's not yet on the LRU and we own the only ref to it.
The only hole I was able to shoot in this is swsusp, which walks mem_map[] fiddling with page flags. But when it does this, only one CPU is running.
But I'm itching for an excuse to extirpate it all ;)
Re: [PATCH 06/33] readahead: refactor __do_page_cache_readahead()
In reply to Andrew MortonQuoted 7 lines · Andrew Morton
Quoted 3 lines · Wu Fengguang
Add look-ahead support to
__do_page_cache_readahead(), which is needed by the adaptive read-ahead logic.You'd need to define "look-ahead support" before telling us you've added it ;)
Quoted 10 lines
mm/readahead.c __do_page_cache_readahead(struct address · line 309
Quoted 8 lines
mm/readahead.c +2
-0@@ -302,6 +303,8 @@ __do_page_cache_readahead(struct addressbreak ; page->index = page_offset;list_add (&page->lru, &page_pool); +if (page_idx == nr_to_read - lookahead_size) +__SetPageReadahead (page); ret++; }OK. But the
__SetPageFoo()things still give me the creeps.
Hehe, updated to SetPageReadahead().
Quoted 9 lines
OT: look:
read_unlock_irq(&mapping->tree_lock); page = page_cache_alloc_cold(mapping); read_lock_irq(&mapping->tree_lock);we should have a page allocation function which just allocates a page from this CPU's per-cpu-pages magazine, and fails if the magazine is empty:
Quoted 9 lines
page = alloc_pages_local(mapping_gfp_mask(x)|__GFP_COLD);
if (!page) {
read_unlock_irq(&mapping->tree_lock);
/*
* This will refill the per-cpu-pages magazine
*/
page = page_cache_alloc_cold(mapping);
read_lock_irq(&mapping->tree_lock);
}Seems good, except for the alloc_pages_local() not being able to spread memory among nodes as page_cache_alloc_cold() do.
Wu
PATCH 7/33 readahead: insert cond_resched() calls
In reply to a message not in the archiveSince the VM_MAX_READAHEAD is greatly enlarged and the algorithm more complex, it becomes necessary to insert some cond_resched() calls in the read-ahead path.
If desktop users still feel audio jitters with the new read-ahead code, please try one of the following ways to get rid of it:
1) compile kernel with CONFIG_PREEMPT_VOLUNTARY/CONFIG_PREEMPT
2) reduce the read-ahead request size by running
blockdev --setra 256 /dev/hda # or whatever device you are using
---
This patch is recommended by Con Kolivas to improve respond time for desktop. Thanks!
fs/mpage.c | 4 +++- mm/readahead.c | 9 +++++++-- 2 files changed, 10 insertions(+), 3 deletions(-)
mm/readahead.c +7 -2
@@ -146,8 +146,10 @@ int read_cache_pages(struct address_spaccontinue ; } ret =filler (data, page); -if (!pagevec_add (&lru_pvec, page)) +if (!pagevec_add (&lru_pvec, page)) { +cond_resched ();__pagevec_lru_add (&lru_pvec); + }if (ret) {while (!list_empty (pages)) {struct page *victim;
@@ -184,8 +186,10 @@ static int read_pages(struct address_spaif (!add_to_page_cache (page, mapping, page->index,GFP_KERNEL )) { mapping->a_ops->readpage (filp, page); -if (!pagevec_add (&lru_pvec, page)) +if (!pagevec_add (&lru_pvec, page)) { +cond_resched ();__pagevec_lru_add (&lru_pvec); + } }else page_cache_release (page); }
@@ -297,6 +301,7 @@ __do_page_cache_readahead(struct addresscontinue ;read_unlock_irq (&mapping->tree_lock); +cond_resched (); page =page_cache_alloc_cold (mapping);read_lock_irq (&mapping->tree_lock);if (!page)
fs/mpage.c +3 -1
@@ -407,8 +407,10 @@ mpage_readpages(struct address_space *ma &last_block_in_bio, &map_bh, &first_logical_block, get_block); -if (!pagevec_add (&lru_pvec, page)) +if (!pagevec_add (&lru_pvec, page)) { +cond_resched ();__pagevec_lru_add (&lru_pvec); + } }else {page_cache_release (page); }
--
PATCH 8/33 readahead: common macros
In reply to a message not in the archiveDefine some common used macros for the read-ahead logics.
---
mm/readahead.c | 14 ++++++++++++-- 1 files changed, 12 insertions(+), 2 deletions(-)
mm/readahead.c +12 -2
@@ -5,6 +5,8 @@* * 09Apr2002 [email protected] * Initial version. +* 21May2006 Wu Fengguang <[email protected]> +* Adaptive read-ahead framework. */ #include <linux/kernel.h>
@@ -14,6 +16,14 @@#include <linux/blkdev.h> #include <linux/backing-dev.h> #include <linux/pagevec.h> +#include <linux/writeback.h> +#include <linux/nfsd/const.h> + +#define PAGES_BYTE (size) (((size) + PAGE_CACHE_SIZE - 1) >> PAGE_CACHE_SHIFT) +#define PAGES_KB (size) PAGES_BYTE((size)*1024) + +#define next_page (pg) (list_entry((pg)->lru.prev, struct page, lru)) +#define prev_page (pg) (list_entry((pg)->lru.next, struct page, lru))void default_unplug_io_fn (struct backing_dev_info *bdi,struct page *page) {
@@ -21,7 +31,7 @@ void default_unplug_io_fn(struct backingEXPORT_SYMBOL (default_unplug_io_fn);struct backing_dev_info default_backing_dev_info = { - .ra_pages = (VM_MAX_READAHEAD *1024 ) /PAGE_CACHE_SIZE , + .ra_pages =PAGES_KB (VM_MAX_READAHEAD ), .state =0 , .capabilities =BDI_CAP_MAP_COPY , .unplug_io_fn = default_unplug_io_fn,
@@ -50,7 +60,7 @@ static inline unsigned long get_max_readstatic inline unsigned long get_min_readahead (struct file_ra_state *ra) { -return (VM_MIN_READAHEAD *1024 ) /PAGE_CACHE_SIZE ; +return PAGES_KB (VM_MIN_READAHEAD ); }static inline void reset_ahead_window (struct file_ra_state *ra)
--
Re: [PATCH 08/33] readahead: common macros
Quoted 20 lines · Wu Fengguang
Define some common used macros for the read-ahead logics.
Signed-off-by Wu Fengguang <[email protected]>---
mm/readahead.c| 14 ++++++++++++--1 files changed, 12 insertions(+), 2 deletions(-)mm/readahead.c +2
-0@@ -5,6 +5,8 @@* * 09Apr2002 [email protected] * Initial version. +* 21May2006 Wu Fengguang <[email protected]> +* Adaptive read-ahead framework. */ #include <linux/kernel.h>
mm/readahead.c line 21
Quoted 6 lines
mm/readahead.c +2
-0@@ -14,6 +16,14 @@#include <linux/blkdev.h> #include <linux/backing-dev.h> #include <linux/pagevec.h> +#include <linux/writeback.h> +#include <linux/nfsd/const.h>
How come you're adding these includes?
mm/readahead.c line 27
Quoted 4 lines
mm/readahead.c +3
-0+ +#define PAGES_BYTE (size) (((size) + PAGE_CACHE_SIZE - 1) >> PAGE_CACHE_SHIFT) +#define PAGES_KB (size) PAGES_BYTE((size)*1024)
Don't really like the names. Don't think they do anything for clarity, but if you can come up with something better for PAGES_BYTE I might change my mind ;) (just forget about PAGES_KB - people know what *1024 means)
Also: the replacements are wrong: if you've defined VM_MAX_READAHEAD to be 4095 bytes, you don't want the _actual_ readahead to be 4096 bytes, do you? It is saying nothing about minimum, so presumably 0 is the correct choice.
mm/readahead.c line 27
Quoted 4 lines
mm/readahead.c +3
-0+ +#define next_page (pg) (list_entry((pg)->lru.prev, struct page, lru)) +#define prev_page (pg) (list_entry((pg)->lru.next, struct page, lru))
Again, it is probably easier just to use the expanded version. Then the reader can immediately say: ah, the next page on the LRU list (rather than, maybe, the next page in the pagecache).
Quoted 14 lines
void
default_unplug_io_fn(struct backing_dev_info *bdi, struct page *page){mm/readahead.c +1
-1@@ -21,7 +31,7 @@ void default_unplug_io_fn(struct backingEXPORT_SYMBOL (default_unplug_io_fn);struct backing_dev_info default_backing_dev_info = { - .ra_pages = (VM_MAX_READAHEAD *1024 ) /PAGE_CACHE_SIZE , + .ra_pages =PAGES_KB (VM_MAX_READAHEAD ), .state =0 , .capabilities =BDI_CAP_MAP_COPY , .unplug_io_fn = default_unplug_io_fn,
mm/readahead.c static inline unsigned long get_max_read
Quoted 10 lines
mm/readahead.c +1
-2@@ -50,7 +60,7 @@ static inline unsigned long get_max_readstatic inline unsigned long get_min_readahead (struct file_ra_state *ra) { -return (VM_MIN_READAHEAD *1024 ) /PAGE_CACHE_SIZE ; +return PAGES_KB (VM_MIN_READAHEAD ); }static inline void reset_ahead_window (struct file_ra_state *ra) --
Send instant messages to your online friends http://au.messenger.yahoo.com
Re: [PATCH 08/33] readahead: common macros
Quoted 5 lines · Nick Piggin
mm/readahead.c line 20
Quoted 3 lines
mm/readahead.c +2
-0+#include <linux/writeback.h> +#include <linux/nfsd/const.h> How come you're adding these includes?
For something added in the past and removed later...
Quoted 7 lines
Quoted 4 lines
+#define
PAGES_BYTE(size)(((size) +PAGE_CACHE_SIZE- 1) >>PAGE_CACHE_SHIFT)
+#definePAGES_KB(size)PAGES_BYTE((size)*1024)Don't really like the names. Don't think they do anything for clarity, but if you can come up with something better for
PAGES_BYTEI might change my mind ;) (just forget aboutPAGES_KB- people know what *1024 means)
No, they are mainly for concision. Don't you think it's cleaner to write
PAGES_KB(VM_MAX_READAHEAD)
than
(VM_MAX_READAHEAD * 1024) / PAGE_CACHE_SIZE
Admittedly the names are somewhat awkward though :)
Quoted 3 lines
Also: the replacements are wrong: if you've defined
VM_MAX_READAHEADto be 4095 bytes, you don't want the _actual_ readahead to be 4096 bytes, do you? It is saying nothing about minimum, so presumably 0 is the correct choice.
The macros were first introduced exact for this reason ;)
It is rumored that there will be 64K page support, and this macro helps round up the 16K sized VM_MIN_READAHEAD. The eof_index also needs rounding up.
Quoted 7 lines
mm/readahead.c line 26
Quoted 3 lines
mm/readahead.c +2
-0+#define next_page (pg) (list_entry((pg)->lru.prev, struct page, lru)) +#define prev_page (pg) (list_entry((pg)->lru.next, struct page, lru))Again, it is probably easier just to use the expanded version. Then the reader can immediately say: ah, the next page on the LRU list (rather than, maybe, the next page in the pagecache).
Ok, will expand it.
Wu
Re: [PATCH 08/33] readahead: common macros
Quoted 12 lines · Wu Fengguang
Quoted 9 lines · Nick Piggin
Quoted 5 lines
+#define
PAGES_BYTE(size)(((size) +PAGE_CACHE_SIZE- 1) >>PAGE_CACHE_SHIFT)
+#definePAGES_KB(size)PAGES_BYTE((size)*1024)Don't really like the names. Don't think they do anything for clarity, but if you can come up with something better for
PAGES_BYTEI might change my mind ;) (just forget aboutPAGES_KB- people know what *1024 means)
Quoted 6 lines
No, they are mainly for concision. Don't you think it's cleaner to write
PAGES_KB(VM_MAX_READAHEAD)
than(VM_MAX_READAHEAD * 1024) / PAGE_CACHE_SIZE
No. Apart from semantics being different (which I'll address below), anybody with any business looking at this code will immediately know and understand what the latter line means. Not so for the former.
Quoted 8 lines
Admittedly the names are somewhat awkward though :)
Quoted 4 lines
Also: the replacements are wrong: if you've defined
VM_MAX_READAHEADto be 4095 bytes, you don't want the _actual_ readahead to be 4096 bytes, do you? It is saying nothing about minimum, so presumably 0 is the correct choice.
Quoted 6 lines
The macros were first introduced exact for this reason ;)
It is rumored that there will be 64K page support, and this macro helps round up the 16K sized
VM_MIN_READAHEAD. Theeof_indexalso needs rounding up.
But VM_MIN_READAHEAD of course should be rounded up, for the same reasons I said VM_MAX_READAHEAD should be rounded down.
So OK as a bug fix, but it needs to be in its own patch, not in a "common macros" one, and sufficiently commented (and preferably outside your core adaptive readahead code so it can be quickly merged up)
--
Send instant messages to your online friends http://au.messenger.yahoo.com
Re: [PATCH 08/33] readahead: common macros
Hello Nick and Andrew,
Updated the patch as recommended.
Thanks,
Wu
---
readahead-macros-min-max-rapages.patch
---
Subject: readahead: introduce {MIN,MAX}_RA_PAGES
Define two convenient macros for read-ahead:
- MAX_RA_PAGES: rounded down counterpart of VM_MAX_READAHEAD
- MIN_RA_PAGES: rounded _up_ counterpart of VM_MIN_READAHEAD
Note that the rounded _up_ MIN_RA_PAGES will work flawlessly with large page sizes like 64k.
--- mm/readahead.c | 14 ++++++++++++-- 1 files changed, 12 insertions(+), 2 deletions(-)
mm/readahead.c +10 -2
@@ -17,13 +17,21 @@#include <linux/backing-dev.h> #include <linux/pagevec.h> +/* +* Convienent macros for min/max read-ahead pages. +* Note that MAX_RA_PAGES is rounded down, while MIN_RA_PAGES is rounded up. +* The latter is necessary for systems with large page size(i.e. 64k). +*/ +#define MAX_RA_PAGES (VM_MAX_READAHEAD*1024 / PAGE_CACHE_SIZE) +#define MIN_RA_PAGES DIV_ROUND_UP(VM_MIN_READAHEAD*1024, PAGE_CACHE_SIZE) +void default_unplug_io_fn (struct backing_dev_info *bdi,struct page *page) { }EXPORT_SYMBOL (default_unplug_io_fn);struct backing_dev_info default_backing_dev_info = { - .ra_pages = (VM_MAX_READAHEAD *1024 ) /PAGE_CACHE_SIZE , + .ra_pages =MAX_RA_PAGES , .state =0 , .capabilities =BDI_CAP_MAP_COPY , .unplug_io_fn = default_unplug_io_fn,
@@ -52,7 +60,7 @@ static inline unsigned long get_max_readstatic inline unsigned long get_min_readahead (struct file_ra_state *ra) { -return (VM_MIN_READAHEAD *1024 ) /PAGE_CACHE_SIZE ; +return MIN_RA_PAGES ; }static inline void reset_ahead_window (struct file_ra_state *ra)
Re: [PATCH 08/33] readahead: common macros
In reply to Nick PigginQuoted 11 lines · Nick Piggin
Quoted 4 lines
+#define
PAGES_BYTE(size)(((size) +PAGE_CACHE_SIZE- 1) >>PAGE_CACHE_SHIFT)
+#definePAGES_KB(size)PAGES_BYTE((size)*1024)Don't really like the names. Don't think they do anything for clarity, but if you can come up with something better for
PAGES_BYTEI might change my mind ;) (just forget aboutPAGES_KB- people know what *1024 means)Also: the replacements are wrong: if you've defined
VM_MAX_READAHEADto be 4095 bytes, you don't want the _actual_ readahead to be 4096 bytes, do you? It is saying nothing about minimum, so presumably 0 is the correct choice.
Got an idea, how about these ones:
#define FULL_PAGES(bytes) ((bytes) >> PAGE_CACHE_SHIFT)
#define PARTIAL_PAGES(bytes) (((bytes)+PAGE_CACHE_SIZE-1) >> PAGE_CACHE_SHIFT)
Re: [PATCH 08/33] readahead: common macros
Quoted 10 lines · Wu Fengguang
Quoted 8 lines · Nick Piggin
Quoted 4 lines
+#define
PAGES_BYTE(size)(((size) +PAGE_CACHE_SIZE- 1) >>PAGE_CACHE_SHIFT)
+#definePAGES_KB(size)PAGES_BYTE((size)*1024)Don't really like the names. Don't think they do anything for clarity, but if you can come up with something better for
PAGES_BYTEI might change my mind ;) (just forget aboutPAGES_KB- people know what *1024 means)
Quoted 7 lines
Quoted 3 lines
Also: the replacements are wrong: if you've defined
VM_MAX_READAHEADto be 4095 bytes, you don't want the _actual_ readahead to be 4096 bytes, do you? It is saying nothing about minimum, so presumably 0 is the correct choice.Got an idea, how about these ones:
#define
FULL_PAGES(bytes)((bytes) >>PAGE_CACHE_SHIFT)
I dunno. We've traditionally open-coded things like this.
Quoted 1 line
#define
PARTIAL_PAGES(bytes)(((bytes)+PAGE_CACHE_SIZE-1) >>PAGE_CACHE_SHIFT)
That's identical to include/linux/kernel.h:DIV_ROUND_UP(), from the gfs2 tree.
Re: [PATCH 08/33] readahead: common macros
In reply to Wu FengguangQuoted 21 lines · Wu Fengguang
Define some common used macros for the read-ahead logics.
Signed-off-by Wu Fengguang <[email protected]>---
mm/readahead.c | 14 ++++++++++++-- 1 files changed, 12 insertions(+), 2 deletions(-)mm/readahead.c +2
-0@@ -5,6 +5,8 @@* * 09Apr2002 [email protected] * Initial version. +* 21May2006 Wu Fengguang <[email protected]> +* Adaptive read-ahead framework. */ #include <linux/kernel.h>
mm/readahead.c line 20
Quoted 5 lines
mm/readahead.c +2
-0@@ -14,6 +16,14 @@#include <linux/blkdev.h> #include <linux/backing-dev.h> #include <linux/pagevec.h> +#include <linux/writeback.h> +#include <linux/nfsd/const.h>
Why on earth are we including that file?
Whatever goodies it contains should be moved into fs.h or mm.h or something.
mm/readahead.c line 23
Quoted 3 lines
mm/readahead.c +3
-0+ +#define PAGES_BYTE (size) (((size) + PAGE_CACHE_SIZE - 1) >> PAGE_CACHE_SHIFT) +#define PAGES_KB (size) PAGES_BYTE((size)*1024)
These aren't proving popular.
mm/readahead.c line 26
Quoted 2 lines
mm/readahead.c +2
-0+#define next_page (pg) (list_entry((pg)->lru.prev, struct page, lru)) +#define prev_page (pg) (list_entry((pg)->lru.next, struct page, lru))
hm. Makes sense I guess, but normally we'll be iterating across lists with the list_for_each*() helpers, so I'm a little surprised that the above are needed.
PATCH 9/33 readahead: events accounting
In reply to a message not in the archiveA debugfs file named `readahead/events' is created according to advises from J?rn Engel, Andrew Morton and Ingo Oeser.
It reveals various read-ahead activities/events, and is vital to the testing.
---------------------------
If you are experiencing performance problems, or want to help improve the read-ahead logic, please send me the debug data. Thanks.
- Preparations
## First compile kernel with CONFIG_DEBUG_READAHEAD mkdir /debug
mount -t debug none /debug
- For each session with distinct access pattern
echo > /debug/readahead/events # reset the counters
# echo > /var/log/kern.log # you may want to backup it first # echo 3 > /debug/readahead/debug_level # show verbose printk traces ## do one benchmark/task # echo 1 > /debug/readahead/debug_level # revert to normal value cp /debug/readahead/events readahead-events-`date +'%F_%R'` # bzip2 -c /var/log/kern.log > kern.log-`date +'%F_%R'`.bz2
The commented out commands can uncover more detailed file accesses, which are useful sometimes. Note that the log file can grow huge!
---
mm/readahead.c | 293 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++- 1 files changed, 292 insertions(+), 1 deletion(-)
mm/readahead.c +292 -1
@@ -19,12 +19,76 @@#include <linux/writeback.h> #include <linux/nfsd/const.h> +/* +* Detailed classification of read-ahead behaviors. +*/ +#define RA_CLASS_SHIFT 4 +#define RA_CLASS_MASK ((1 << RA_CLASS_SHIFT) - 1) +enum ra_class { +RA_CLASS_ALL , +RA_CLASS_INITIAL , +RA_CLASS_STATE , +RA_CLASS_CONTEXT , +RA_CLASS_CONTEXT_AGGRESSIVE , +RA_CLASS_BACKWARD , +RA_CLASS_THRASHING , +RA_CLASS_SEEK , +RA_CLASS_NONE , +RA_CLASS_COUNT +}; + +/* Read-ahead events to be accounted. */ +enum ra_event { +RA_EVENT_CACHE_MISS ,/* read cache misses */ +RA_EVENT_RANDOM_READ ,/* random reads */ +RA_EVENT_IO_CONGESTION ,/* i/o congestion */ +RA_EVENT_IO_CACHE_HIT ,/* canceled i/o due to cache hit */ +RA_EVENT_IO_BLOCK ,/* wait for i/o completion */ + +RA_EVENT_READAHEAD ,/* read-ahead issued */ +RA_EVENT_READAHEAD_HIT ,/* read-ahead page hit */ +RA_EVENT_LOOKAHEAD ,/* look-ahead issued */ +RA_EVENT_LOOKAHEAD_HIT ,/* look-ahead mark hit */ +RA_EVENT_LOOKAHEAD_NOACTION ,/* look-ahead mark ignored */ +RA_EVENT_READAHEAD_MMAP ,/* read-ahead for mmap access */ +RA_EVENT_READAHEAD_EOF ,/* read-ahead reaches EOF */ +RA_EVENT_READAHEAD_SHRINK ,/* ra_size falls under previous la_size */ +RA_EVENT_READAHEAD_THRASHING ,/* read-ahead thrashing happened */ +RA_EVENT_READAHEAD_MUTILATE ,/* read-ahead mutilated by imbalanced aging */ +RA_EVENT_READAHEAD_RESCUE ,/* read-ahead rescued */ + +RA_EVENT_READAHEAD_CUBE , +RA_EVENT_COUNT +}; + +#ifdef CONFIG_DEBUG_READAHEAD +u32 initial_ra_hit; +u32 initial_ra_miss; +u32 debug_level =1 ; +u32 disable_stateful_method =0 ; +static const char *const ra_class_name[]; +static void ra_account (struct file_ra_state *ra,enum ra_event e,int pages); +# define debug_inc (var) do { var++; } while (0) +# define debug_option (o) (o) +#else +# define ra_account (ra, e, pages) do { } while (0) +# define debug_inc (var) do { } while (0) +# define debug_option (o) (0) +# define debug_level (0) +#endif /* CONFIG_DEBUG_READAHEAD */ + +#define dprintk(args...) \ + do { if (debug_level >= 2) printk(KERN_DEBUG args); } while(0) +#define ddprintk(args...) \ + do { if (debug_level >= 3) printk(KERN_DEBUG args); } while(0) +#define PAGES_BYTE (size) (((size) + PAGE_CACHE_SIZE - 1) >> PAGE_CACHE_SHIFT)#define PAGES_KB (size) PAGES_BYTE((size)*1024)#define next_page (pg) (list_entry((pg)->lru.prev, struct page, lru))#define prev_page (pg) (list_entry((pg)->lru.next, struct page, lru)) +void default_unplug_io_fn (struct backing_dev_info *bdi,struct page *page) { }
@@ -365,6 +429,9 @@ int force_page_cache_readahead(struct ad offset += this_chunk; nr_to_read -= this_chunk; } + +ra_account (NULL ,RA_EVENT_READAHEAD , ret); +return ret; }
@@ -400,10 +467,16 @@ static inline int check_ra_success(strucint do_page_cache_readahead (struct address_space *mapping,struct file *filp,pgoff_t offset,unsigned long nr_to_read) { +unsigned long ret; +if (bdi_read_congested (mapping->backing_dev_info))return -1 ; -return __do_page_cache_readahead (mapping, filp, offset, nr_to_read,0 ); + ret =__do_page_cache_readahead (mapping, filp, offset, nr_to_read,0 ); + +ra_account (NULL ,RA_EVENT_READAHEAD , ret); + +return ret; }/*
@@ -425,6 +498,10 @@ blockable_page_cache_readahead(struct ad actual =__do_page_cache_readahead (mapping, filp, offset, nr_to_read,0 ); +ra_account (NULL ,RA_EVENT_READAHEAD , actual); +dprintk ("blockable-readahead(ino=%lu, ra=%lu+%lu) = %d\n" , + mapping->host->i_ino, offset, nr_to_read, actual); +return check_ra_success (ra, nr_to_read, actual); }
@@ -604,3 +681,217 @@ unsigned long max_sane_readahead(unsigne__get_zone_counts (&active, &inactive, &free,NODE_DATA (numa_node_id ()));return min (nr, (inactive + free) /2 ); } + +/* +* Read-ahead events accounting. +*/ +#ifdef CONFIG_DEBUG_READAHEAD + +#include <linux/init.h> +#include <linux/jiffies.h> +#include <linux/debugfs.h> +#include <linux/seq_file.h> + +static const char *const ra_class_name[] = { +"total" , +"initial" , +"state" , +"context" , +"contexta" , +"backward" , +"onthrash" , +"onseek" , +"none" +}; + +static const char *const ra_event_name[] = { +"cache_miss" , +"random_read" , +"io_congestion" , +"io_cache_hit" , +"io_block" , +"readahead" , +"readahead_hit" , +"lookahead" , +"lookahead_hit" , +"lookahead_ignore" , +"readahead_mmap" , +"readahead_eof" , +"readahead_shrink" , +"readahead_thrash" , +"readahead_mutilt" , +"readahead_rescue" +}; + +static unsigned long ra_events[RA_CLASS_COUNT ][RA_EVENT_COUNT ][2 ]; + +static void ra_account (struct file_ra_state *ra,enum ra_event e,int pages) +{ +enum ra_class c; + +if (!debug_level) +return ; + +if (e ==RA_EVENT_READAHEAD_HIT && pages <0 ) { + c = (ra->flags >>RA_CLASS_SHIFT ) &RA_CLASS_MASK ; + pages = -pages; + }else if (ra) + c = ra->flags &RA_CLASS_MASK ; +else + c =RA_CLASS_NONE ; + +if (!c) + c =RA_CLASS_NONE ; + + ra_events[c][e][0 ] +=1 ; + ra_events[c][e][1 ] += pages; + +if (e ==RA_EVENT_READAHEAD ) + ra_events[c][RA_EVENT_READAHEAD_CUBE ][1 ] += pages * pages; +} + +static int ra_events_show (struct seq_file *s,void *_) +{ +int i; +int c; +int e; +static const char event_fmt[] ="%-16s" ; +static const char class_fmt[] ="%10s" ; +static const char item_fmt[] ="%10lu" ; +static const char percent_format[] ="%9lu%%" ; +static const char *const table_name[] = { +"[table requests]" , +"[table pages]" , +"[table summary]" }; + +for (i =0 ; i <=1 ; i++) { +for (e =0 ; e <RA_EVENT_COUNT ; e++) { + ra_events[RA_CLASS_ALL ][e][i] =0 ; +for (c =RA_CLASS_INITIAL ; c <RA_CLASS_NONE ; c++) + ra_events[RA_CLASS_ALL ][e][i] += ra_events[c][e][i]; + } + +seq_printf (s, event_fmt, table_name[i]); +for (c =0 ; c <RA_CLASS_COUNT ; c++) +seq_printf (s, class_fmt, ra_class_name[c]); +seq_puts (s,"\n" ); + +for (e =0 ; e <RA_EVENT_COUNT ; e++) { +if (e ==RA_EVENT_READAHEAD_CUBE ) +continue ; +if (e ==RA_EVENT_READAHEAD_HIT && i ==0 ) +continue ; +if (e ==RA_EVENT_IO_BLOCK && i ==1 ) +continue ; + +seq_printf (s, event_fmt, ra_event_name[e]); +for (c =0 ; c <RA_CLASS_COUNT ; c++) +seq_printf (s, item_fmt, ra_events[c][e][i]); +seq_puts (s,"\n" ); + } +seq_puts (s,"\n" ); + } + +seq_printf (s, event_fmt, table_name[2 ]); +for (c =0 ; c <RA_CLASS_COUNT ; c++) +seq_printf (s, class_fmt, ra_class_name[c]); +seq_puts (s,"\n" ); + +seq_printf (s, event_fmt,"random_rate" ); +for (c =0 ; c <RA_CLASS_COUNT ; c++) +seq_printf (s, percent_format, + (ra_events[c][RA_EVENT_RANDOM_READ ][0 ] *100 ) / + ((ra_events[c][RA_EVENT_RANDOM_READ ][0 ] + + ra_events[c][RA_EVENT_READAHEAD ][0 ]) |1 )); +seq_puts (s,"\n" ); + +seq_printf (s, event_fmt,"ra_hit_rate" ); +for (c =0 ; c <RA_CLASS_COUNT ; c++) +seq_printf (s, percent_format, + (ra_events[c][RA_EVENT_READAHEAD_HIT ][1 ] *100 ) / + (ra_events[c][RA_EVENT_READAHEAD ][1 ] |1 )); +seq_puts (s,"\n" ); + +seq_printf (s, event_fmt,"la_hit_rate" ); +for (c =0 ; c <RA_CLASS_COUNT ; c++) +seq_printf (s, percent_format, + (ra_events[c][RA_EVENT_LOOKAHEAD_HIT ][0 ] *100 ) / + (ra_events[c][RA_EVENT_LOOKAHEAD ][0 ] |1 )); +seq_puts (s,"\n" ); + +seq_printf (s, event_fmt,"var_ra_size" ); +for (c =0 ; c <RA_CLASS_COUNT ; c++) +seq_printf (s, item_fmt, + (ra_events[c][RA_EVENT_READAHEAD_CUBE ][1 ] - + ra_events[c][RA_EVENT_READAHEAD ][1 ] * + (ra_events[c][RA_EVENT_READAHEAD ][1 ] / + (ra_events[c][RA_EVENT_READAHEAD ][0 ] |1 ))) / + (ra_events[c][RA_EVENT_READAHEAD ][0 ] |1 )); +seq_puts (s,"\n" ); + +seq_printf (s, event_fmt,"avg_ra_size" ); +for (c =0 ; c <RA_CLASS_COUNT ; c++) +seq_printf (s, item_fmt, + (ra_events[c][RA_EVENT_READAHEAD ][1 ] + + ra_events[c][RA_EVENT_READAHEAD ][0 ] /2 ) / + (ra_events[c][RA_EVENT_READAHEAD ][0 ] |1 )); +seq_puts (s,"\n" ); + +seq_printf (s, event_fmt,"avg_la_size" ); +for (c =0 ; c <RA_CLASS_COUNT ; c++) +seq_printf (s, item_fmt, + (ra_events[c][RA_EVENT_LOOKAHEAD ][1 ] + + ra_events[c][RA_EVENT_LOOKAHEAD ][0 ] /2 ) / + (ra_events[c][RA_EVENT_LOOKAHEAD ][0 ] |1 )); +seq_puts (s,"\n" ); + +return 0 ; +} + +static int ra_events_open (struct inode *inode,struct file *file) +{ +return single_open (file, ra_events_show,NULL ); +} + +static ssize_t ra_events_write (struct file *file,const char __user *buf, +size_t size,loff_t *offset) +{ +memset (ra_events,0 ,sizeof (ra_events)); +return 1 ; +} + +struct file_operations ra_events_fops = { + .owner =THIS_MODULE , + .open = ra_events_open, + .write = ra_events_write, + .read = seq_read, + .llseek = seq_lseek, + .release = single_release, +}; + +#define READAHEAD_DEBUGFS_ENTRY_U32 (var) \ + debugfs_create_u32(__stringify(var), 0644, root, &var) + +#define READAHEAD_DEBUGFS_ENTRY_BOOL (var) \ + debugfs_create_bool(__stringify(var), 0644, root, &var) + +static int __init readahead_init (void ) +{ +struct dentry *root; + + root =debugfs_create_dir ("readahead" ,NULL ); + +debugfs_create_file ("events" ,0644 , root,NULL , &ra_events_fops); + +READAHEAD_DEBUGFS_ENTRY_U32 (initial_ra_hit); +READAHEAD_DEBUGFS_ENTRY_U32 (initial_ra_miss); + +READAHEAD_DEBUGFS_ENTRY_U32 (debug_level); +READAHEAD_DEBUGFS_ENTRY_BOOL (disable_stateful_method); + +return 0 ; +} + +module_init(readahead_init) + +#endif /* CONFIG_DEBUG_READAHEAD */
--
Re: [PATCH 09/33] readahead: events accounting
Quoted 3 lines · Wu Fengguang
A debugfs file named `readahead/events' is created according to advises from
J?rn Engel, Andrew Morton and Ingo Oeser.
If everyone's patches all get merged up we'd expect that this facility be migrated over to use Martin Peschke's statistics infrastructure.
That's not a thing you should do now, but it would be a useful test of Martin's work if you could find time to look at it and let us know whether the infrastructure which he has provided would suit this application, thanks.
Re: [PATCH 09/33] readahead: events accounting
Quoted 5 lines · Andrew Morton
Quoted 3 lines · Wu Fengguang
A debugfs file named `readahead/events' is created according to advises from
J?rn Engel, Andrew Morton and Ingo Oeser.
Quoted 7 lines
If everyone's patches all get merged up we'd expect that this facility be migrated over to use Martin Peschke's statistics infrastructure.
That's not a thing you should do now, but it would be a useful test of Martin's work if you could find time to look at it and let us know whether the infrastructure which he has provided would suit this application, thanks.
Sure, I'll look into it when I am able to settle down.
Wu
Re: [PATCH 09/33] readahead: events accounting
In reply to Andrew MortonQuoted 5 lines · Andrew Morton
Quoted 3 lines · Wu Fengguang
A debugfs file named `readahead/events' is created according to advises from
J?rn Engel, Andrew Morton and Ingo Oeser.
Quoted 7 lines
If everyone's patches all get merged up we'd expect that this facility be migrated over to use Martin Peschke's statistics infrastructure.
That's not a thing you should do now, but it would be a useful test of Martin's work if you could find time to look at it and let us know whether the infrastructure which he has provided would suit this application, thanks.
Hi, Martin is doing a great job, thanks.
I have read about its doc. It should be suitable for various readahead numbers. And it seems a trivial work to port to it :)
However it might also make sense to keep the current _table_ interface. It shows us the whole picture at a glance:
% cat /debug/readahead/events
[table requests] total newfile state context contexta [...]cache_miss 136302 538 3860 11317 490read_random 62176 160 424 1633 60io_congestion 0 0 0 0 0
io_cache_hit 34521 663 10071 15611 1423 io_block 204302 42174 10408 68277 2226 readahead 251478 70746 96846 73636 2561 lookahead 136315 14805 86267 32738 2505 lookahead_hit 103384 8038 74605 9097 598 lookahead_ignore 0 0 0 0 0 readahead_mmap 6911 0 0 0 0 readahead_eof 70793 55935 8500 648 581 readahead_shrink 473 0 473 0 0 readahead_thrash 0 0 0 0 0
readahead_mutilt 2526 24 1079 1403 20readahead_rescue 1209 0 0 0 0
[table pages] total newfile state context contextacache_miss 1292350444 282817 35557285 86087568 5592690read_random 10299237 177 426 1903 63io_congestion 0 0 0 0 0io_cache_hit 2194663 9289 1507054 414311 184715io_block 204302 42174 10408 68277 2226
readahead 26122947 770681 21815335 3097682 259587 readahead_hit 23101714 588811 19906233 2209547 191269 lookahead 21397630 173502 19872014 936474 415640 lookahead_hit 18663196 98004 17879848 596562 88782 lookahead_ignore 0 0 0 0 0 readahead_mmap 170509 0 0 0 0 readahead_eof 1950484 432763 1342148 47368 34742 readahead_shrink 19900 0 19900 0 0 readahead_thrash 0 0 0 0 0
readahead_mutilt 220331 485 186922 29900 3024readahead_rescue 119592 0 0 0 0
[table summary] total newfile state context contexta
random_rate 19% 0% 0% 2% 2% ra_hit_rate 88% 76% 91% 71% 73% la_hit_rate 75% 54% 86% 27% 23% var_ra_size 13850 130 5802 6709 10563 avg_ra_size 104 11 225 42 101 avg_la_size 157 12 230 29 166
When Martin's work is included into -mm, I would like to reduce several col/rows from the table to Martin's infrastructure, and perhaps add some more items. One obvious candidate collection is the ra_account(NULL, ...) calls, which do not quite fit the table interface and deserves individual files.
Wu
Re: [PATCH 09/33] readahead: events accounting
Quoted 12 lines · Wu Fengguang
Quoted 10 lines · Andrew Morton
Quoted 2 lines · Wu Fengguang
A debugfs file named `readahead/events' is created according to advises from
J?rn Engel, Andrew Morton and Ingo Oeser.If everyone's patches all get merged up we'd expect that this facility be migrated over to use Martin Peschke's statistics infrastructure.
That's not a thing you should do now, but it would be a useful test of Martin's work if you could find time to look at it and let us know whether the infrastructure which he has provided would suit this application, thanks.
Quoted 4 lines
Hi, Martin is doing a great job, thanks.
I have read about its doc. It should be suitable for various readahead numbers. And it seems a trivial work to port to it :)
Wu, great :) If you got questions (e.g. on how to setup your statistics so that the output looks quite compact) or more requirements (like an enhancement of the code that accumulates numbers) feel free to get back to me. Thanks, Martin
PATCH 10/33 readahead: support functions
In reply to a message not in the archiveSeveral support functions of adaptive read-ahead.
---
include/linux/mm.h | 11 +++++ mm/readahead.c | 107 +++++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 118 insertions(+)
include/linux/mm.h +11 -0
@@ -1029,6 +1029,17 @@ void handle_ra_miss(struct address_space struct file_ra_state *ra, pgoff_t offset);unsigned long max_sane_readahead (unsigned long nr); +#ifdef CONFIG_ADAPTIVE_READAHEAD +extern int readahead_ratio; +#else +#define readahead_ratio 1 +#endif /* CONFIG_ADAPTIVE_READAHEAD */ + +static inline int prefer_adaptive_readahead (void ) +{ +return readahead_ratio >=10 ; +} +/* Do stack extension */ extern int expand_stack (struct vm_area_struct *vma,unsigned long address);#ifdef CONFIG_IA64
mm/readahead.c +107 -0
113 lines not on this page · raw message
--
Re: [PATCH 10/33] readahead: support functions
Quoted 14 lines · Wu Fengguang
mm/readahead.c +12
-0+#ifdef CONFIG_ADAPTIVE_READAHEAD + +/* +* The nature of read-ahead allows false tests to occur occasionally. +* Here we just do not bother to call get_page(), it's meaningless anyway. +*/ +static inline struct page *__find_page (struct address_space *mapping, +pgoff_t offset) +{ +return radix_tree_lookup (&mapping->page_tree, offset); +} +
mm/readahead.c unsigned long max_sane_readahead(unsigne · line 733
Quoted 10 lines
mm/readahead.c +10
-0+static inline struct page *find_page (struct address_space *mapping, +pgoff_t offset) +{ +struct page *page; + +read_lock_irq (&mapping->tree_lock); + page =__find_page (mapping, offset); +read_unlock_irq (&mapping->tree_lock); +return page; +}
Meh, this is just open-coded elsewhere in readahead.c; I'd either open code it, or do a new patch to replace the existing callers. find_page should be in mm/filemap.c, btw (or include/linux/pagemap.h).
mm/readahead.c unsigned long max_sane_readahead(unsigne · line 739
Quoted 8 lines
mm/readahead.c +6
-0+ +/* +* Move pages in danger (of thrashing) to the head of inactive_list. +* Not expected to happen frequently. +*/ +static unsigned long rescue_pages (struct page *page,unsigned long nr_pages)
Should probably be in mm/vmscan.c
--
Send instant messages to your online friends http://au.messenger.yahoo.com
Re: [PATCH 10/33] readahead: support functions
Quoted 22 lines · Nick Piggin
Quoted 20 lines · Wu Fengguang
mm/readahead.c +20
-0+#ifdef CONFIG_ADAPTIVE_READAHEAD + +/* +* The nature of read-ahead allows false tests to occur occasionally. +* Here we just do not bother to call get_page(), it's meaningless anyway. +*/ +static inline struct page *__find_page (struct address_space *mapping, +pgoff_t offset) +{ +return radix_tree_lookup (&mapping->page_tree, offset); +} + +static inline struct page *find_page (struct address_space *mapping, +pgoff_t offset) +{ +struct page *page; + +read_lock_irq (&mapping->tree_lock); + page =__find_page (mapping, offset); +read_unlock_irq (&mapping->tree_lock);
Quoted 8 lines
Review
Quoted 4 lines
(quoted diff) +2
-0+ return page; +}Meh, this is just open-coded elsewhere in
readahead.c; I'd either open code it, or do a new patch to replace the existing callers.find_pageshould be inmm/filemap.c, btw (orinclude/linux/pagemap.h).
Maybe it should stay in readahead.c.
I got this early warning from Andrew:
find_page() is not meant to be a general API, for it can easily be abused.
Quoted 11 lines
Quoted 9 lines
mm/readahead.c +6
-0+ +/* +* Move pages in danger (of thrashing) to the head of inactive_list. +* Not expected to happen frequently. +*/ +static unsigned long rescue_pages(struct page *page, unsigned long
nr_pages)Should probably be in
mm/vmscan.c
Maybe. It's a highly specialized function. It protects a continuous range of sequential readahead pages in a file. Do you mean to move it for the zone->lru_lock protected statements?
Regards,
Wu
Re: [PATCH 10/33] readahead: support functions
In reply to Wu FengguangQuoted 11 lines · Wu Fengguang
mm/readahead.c +10
-0+/* +* The nature of read-ahead allows false tests to occur occasionally. +* Here we just do not bother to call get_page(), it's meaningless anyway. +*/ +static inline struct page *__find_page (struct address_space *mapping, +pgoff_t offset) +{ +return radix_tree_lookup (&mapping->page_tree, offset); +} +
mm/readahead.c unsigned long max_sane_readahead(unsigne · line 733
Quoted 10 lines
mm/readahead.c +10
-0+static inline struct page *find_page (struct address_space *mapping, +pgoff_t offset) +{ +struct page *page; + +read_lock_irq (&mapping->tree_lock); + page =__find_page (mapping, offset); +read_unlock_irq (&mapping->tree_lock); +return page; +}
Would much prefer that this be called probe_page() and that it return 0 or 1, so nobody is tempted to dereference `page'.
Quoted 37 lines
mm/readahead.c +37
-0+/* +* Move pages in danger (of thrashing) to the head of inactive_list. +* Not expected to happen frequently. +*/ +static unsigned long rescue_pages (struct page *page,unsigned long nr_pages) +{ +int pgrescue; +pgoff_t index; +struct zone *zone; +struct address_space *mapping; + +BUG_ON (!nr_pages || !page); + pgrescue =0 ; + index =page_index (page); + mapping =page_mapping (page); + +dprintk ("rescue_pages(ino=%lu, index=%lu nr=%lu)\n" , + mapping->host->i_ino, index, nr_pages); + +for (;;) { + zone =page_zone (page); +spin_lock_irq (&zone->lru_lock); + +if (!PageLRU (page)) + goto out_unlock; + +while (page_mapping (page) == mapping && +page_index (page) == index) { +struct page *the_page = page; + page =next_page (page); +if (!PageActive (the_page) && + !PageLocked (the_page) && +page_count (the_page) ==1 ) { +list_move (&the_page->lru, &zone->inactive_list); + pgrescue++; + } + index++;
mm/readahead.c unsigned long max_sane_readahead(unsigne · line 781
Quoted 10 lines
mm/readahead.c +10
-0+if (!--nr_pages) + goto out_unlock; + } + +spin_unlock_irq (&zone->lru_lock); + +cond_resched (); + page =find_page (mapping, index); +if (!page) + goto out;
Yikes! We do not have a reference on this page. Now, it happens that page_zone() on a random freed page will work OK. At present. I think. Depends on things like memory hot-remove, balloon drivers and heaven knows what.
But it's not at all clear that the combination
spin_lock_irq(&zone->lru_lock); if (!PageLRU(page)) goto out_unlock;
is is a safe thing to do against a freed page, or against a freed and reused-for-we-dont-know-what page. It probably _is_ safe, as we're probably setting and clearing PG_lru inside lru_lock in other places. But it's not obvious that these things will be true for all time and Nick keeps on trying to diddle with that stuff. There's quite a bit of subtle dependency being introduced here.
Re: [PATCH 10/33] readahead: support functions
Quoted 17 lines · Andrew Morton
Quoted 16 lines · Wu Fengguang
mm/readahead.c +15
-0+/* +* The nature of read-ahead allows false tests to occur occasionally. +* Here we just do not bother to call get_page(), it's meaningless anyway. +*/ +static inline struct page *__find_page (struct address_space *mapping, +pgoff_t offset) +{ +return radix_tree_lookup (&mapping->page_tree, offset); +} + +static inline struct page *find_page (struct address_space *mapping, +pgoff_t offset) +{ +struct page *page; +
Quoted 8 lines
mm/readahead.c unsigned long max_sane_readahead(unsigne · line 733
Quoted 5 lines
mm/readahead.c +5
-0+read_lock_irq (&mapping->tree_lock); + page =__find_page (mapping, offset); +read_unlock_irq (&mapping->tree_lock); +return page; +}Would much prefer that this be called
probe_page()and that it return 0 or 1, so nobody is tempted to dereference `page'.
Good idea. I'd add them to filemap.c.
Quoted 60 lines
Quoted 37 lines
mm/readahead.c +37
-0+/* +* Move pages in danger (of thrashing) to the head of inactive_list. +* Not expected to happen frequently. +*/ +static unsigned long rescue_pages (struct page *page,unsigned long nr_pages) +{ +int pgrescue; +pgoff_t index; +struct zone *zone; +struct address_space *mapping; + +BUG_ON (!nr_pages || !page); + pgrescue =0 ; + index =page_index (page); + mapping =page_mapping (page); + +dprintk ("rescue_pages(ino=%lu, index=%lu nr=%lu)\n" , + mapping->host->i_ino, index, nr_pages); + +for (;;) { + zone =page_zone (page); +spin_lock_irq (&zone->lru_lock); + +if (!PageLRU (page)) + goto out_unlock; + +while (page_mapping (page) == mapping && +page_index (page) == index) { +struct page *the_page = page; + page =next_page (page); +if (!PageActive (the_page) && + !PageLocked (the_page) && +page_count (the_page) ==1 ) { +list_move (&the_page->lru, &zone->inactive_list); + pgrescue++; + } + index++;mm/readahead.c unsigned long max_sane_readahead(unsigne · line 781
Quoted 10 lines
mm/readahead.c +10
-0+if (!--nr_pages) + goto out_unlock; + } + +spin_unlock_irq (&zone->lru_lock); + +cond_resched (); + page =find_page (mapping, index); +if (!page) + goto out;Yikes! We do not have a reference on this page. Now, it happens that
page_zone()on a random freed page will work OK. At present. I think. Depends on things like memory hot-remove, balloon drivers and heaven knows what.But it's not at all clear that the combination
spin_lock_irq(&zone->lru_lock); if (!PageLRU(page)) goto out_unlock;
Quoted 6 lines
is is a safe thing to do against a freed page, or against a freed and reused-for-we-dont-know-what page. It probably _is_ safe, as we're probably setting and clearing
PG_lruinsidelru_lockin other places. But it's not obvious that these things will be true for all time and Nick keeps on trying to diddle with that stuff. There's quite a bit of subtle dependency being introduced here.
I saw some code pieces like
spin_lock_irqsave(&zone->lru_lock, flags);
VM_BUG_ON(!PageLRU(page));
__ClearPageLRU(page);
del_page_from_lru(zone, page);
spin_unlock_irqrestore(&zone->lru_lock, flags);They give me an allusion that PG_lru and page->lru are always changed together, under the protection of zone->lru_lock...
I bet correctness is top priority, so I'll stop playing fire with it.
Thanks,
Wu
PATCH 11/33 readahead: sysctl parameters
In reply to a message not in the archiveAdd new sysctl entries in /proc/sys/vm:
- readahead_ratio = 50
i.e. set read-ahead size to <=(readahead_ratio%) thrashing threshold
- readahead_hit_rate = 1
i.e. read-ahead hit ratio >=(1/readahead_hit_rate) is deemed ok
readahead_ratio also provides a way to select read-ahead logic at runtime:
condition action
==========================================================================readahead_ratio == 0 disable read-aheadreadahead_ratio <= 9 select the (old) stock read-ahead logicreadahead_ratio >= 10 select the (new) adaptive read-ahead logic
---
Documentation/sysctl/vm.txt | 37 +++++++++++++++++++++++++++++++++++++ include/linux/sysctl.h | 2 ++ kernel/sysctl.c | 28 ++++++++++++++++++++++++++++ mm/readahead.c | 17 +++++++++++++++++ 4 files changed, 84 insertions(+)
mm/readahead.c +17 -0
@@ -20,6 +20,23 @@#include <linux/nfsd/const.h> /* +* Adaptive read-ahead parameters. +*/ + +/* In laptop mode, poll delayed look-ahead on every ## pages read. */ +#define LAPTOP_POLL_INTERVAL 16 + +/* Set look-ahead size to 1/# of the thrashing-threshold. */ +#define LOOKAHEAD_RATIO 8 + +/* Set read-ahead size to ##% of the thrashing-threshold. */ +int readahead_ratio =50 ; +EXPORT_SYMBOL_GPL (readahead_ratio); + +/* Readahead as long as cache hit ratio keeps above 1/##. */ +int readahead_hit_rate =1 ; + +/* * Detailed classification of read-ahead behaviors. */ #define RA_CLASS_SHIFT 4
include/linux/sysctl.h +2 -0
@@ -194,6 +194,8 @@ enumVM_ZONE_RECLAIM_INTERVAL =32 ,/* time period to wait after reclaim failure */ VM_PANIC_ON_OOM =33 ,/* panic at out-of-memory */ VM_SWAP_PREFETCH =34 ,/* swap prefetch */ +VM_READAHEAD_RATIO =35 ,/* percent of read-ahead size to thrashing-threshold */ + VM_READAHEAD_HIT_RATE=36, /* one accessed page legitimizes so many read-ahead pages */ };/* CTL_NET names: */
kernel/sysctl.c +28 -0
@@ -77,6 +77,12 @@ extern int percpu_pagelist_fraction;extern int compat_log;extern int print_fatal_signals; +#if defined(CONFIG_ADAPTIVE_READAHEAD ) +extern int readahead_ratio; +extern int readahead_hit_rate; +static int one =1 ; +#endif +#if defined(CONFIG_X86_LOCAL_APIC ) && defined(CONFIG_X86 )int unknown_nmi_panic;int nmi_watchdog_enabled;
@@ -987,6 +993,28 @@ static ctl_table vm_table[] = { .proc_handler = &proc_dointvec, },#endif +#ifdef CONFIG_ADAPTIVE_READAHEAD + { + .ctl_name = VM_READAHEAD_RATIO, + .procname = "readahead_ratio", + .data = &readahead_ratio, + .maxlen = sizeof(readahead_ratio), + .mode = 0644, + .proc_handler = &proc_dointvec, + .strategy = &sysctl_intvec, + .extra1 = &zero, + }, + { + .ctl_name = VM_READAHEAD_HIT_RATE, + .procname = "readahead_hit_rate", + .data = &readahead_hit_rate, + .maxlen = sizeof(readahead_hit_rate), + .mode = 0644, + .proc_handler = &proc_dointvec, + .strategy = &sysctl_intvec, + .extra1 = &one, + }, +#endif { .ctl_name = 0 } };
Documentation/sysctl/vm.txt +37 -0
@@ -31,6 +31,8 @@ Currently, these files are in /proc/sys/ - zone_reclaim_interval - panic_on_oom - swap_prefetch +- readahead_ratio +- readahead_hit_rate ==============================================================
@@ -202,3 +204,38 @@ copying back pages from swap into the sw practice it can take many minutes before the vm is idle enough. The default value is 1. + +============================================================== + +readahead_ratio + +This limits readahead size to percent of the thrashing threshold. +The thrashing threshold is dynamicly estimated from the _history_ read +speed and system load, to deduce the _future_ readahead request size. + +Set it to a smaller value if you have not enough memory for all the +concurrent readers, or the I/O loads fluctuate a lot. But if there's +plenty of memory(>2MB per reader), a bigger value may help performance. + +readahead_ratio also selects the readahead logic: + VALUE CODE PATH + ------------------------------------------- + 0 disable readahead totally + 1-9 select the stock readahead logic + 10-inf select the adaptive readahead logic + +The default value is 50. Reasonable values would be [50, 100]. + +============================================================== + +readahead_hit_rate + +This is the max allowed value of (readahead-pages : accessed-pages). +Useful only when (readahead_ratio >= 10). If the previous readahead +request has bad hit rate, the kernel will be reluctant to do the next +readahead. + +Larger values help catch more sparse access patterns. Be aware that +readahead of the sparse patterns sacrifices memory for speed. + +The default value is 1. It is recommended to keep the value below 16.
--
Re: [PATCH 12/33] readahead: min/max sizes
Quoted 5 lines · Wu Fengguang
- Enlarge
VM_MAX_READAHEADto 1024 if new read-ahead code is compiled in. This value is no longer tightly coupled with the thrashing problem, therefore constrained by it. The adaptive read-ahead logic merely takes it as an upper bound, and will not stick to it under memory pressure.
I guess this size enlargement is one of the main reasons your patchset improves performance in some cases.
There is currently some sort of thrashing protection in there. Obviously you've found it to be unable to cope with some situations and introduced a lot of really fancy stuff to fix it. Are these just academic access patterns, or do you have real test cases that demonstrate this failure (ie. can we try to incrementally improve the current logic as well as work towards merging your readahead rewrite?)
--
Send instant messages to your online friends http://au.messenger.yahoo.com
Re: [PATCH 12/33] readahead: min/max sizes
Quoted 10 lines · Nick Piggin
Quoted 5 lines · Wu Fengguang
- Enlarge
VM_MAX_READAHEADto 1024 if new read-ahead code is compiled in. This value is no longer tightly coupled with the thrashing problem, therefore constrained by it. The adaptive read-ahead logic merely takes it as an upper bound, and will not stick to it under memory pressure.I guess this size enlargement is one of the main reasons your patchset improves performance in some cases.
Sure, I started the patch to fulfill the 1M _default_ size dream ;-) The majority users will never enjoy the performance improvement if ever we stick to 128k default size. And it won't be possible for the current readahead logic, since it lacks basic thrashing protection mechanism.
Quoted 7 lines
There is currently some sort of thrashing protection in there. Obviously you've found it to be unable to cope with some situations and introduced a lot of really fancy stuff to fix it. Are these just academic access patterns, or do you have real test cases that demonstrate this failure (ie. can we try to incrementally improve the current logic as well as work towards merging your readahead rewrite?)
But to be serious, in the progress I realized that it's much more beyond the max readahead size. The fancy features are more coming out of _real_ needs than to fulfill academic goals. I've seen real world improvements from desktop/file server/backup server/database users for most of the implemented features.
Wu
PATCH 13/33 readahead: state based method - aging accounting
In reply to a message not in the archiveCollect info about the global available memory and its consumption speed. The data are used by the stateful method to estimate the thrashing threshold.
They are the decisive factor of the correctness/accuracy of the resulting read-ahead size.
- On NUMA systems, the accountings are done on a per-node basis. It works for the two common real-world schemes:
- the reader process allocates caches in a node affined manner;
- the reader process allocates caches _balancely_ from a set of nodes.
- On non-NUMA systems, the readahead_aging is mainly increased on first access of the read-ahead pages, in order to make it go up constantly and smoothly. It helps improve the accuracy on small/fast read-aheads, with the cost of a little more overhead.
---
include/linux/mm.h | 9 +++++++++ include/linux/mmzone.h | 5 +++++ mm/Kconfig | 5 +++++ mm/readahead.c | 49 +++++++++++++++++++++++++++++++++++++++++++++++++ mm/swap.c | 2 ++ mm/vmscan.c | 4 ++++ 6 files changed, 74 insertions(+)
mm/Kconfig +5 -0
@@ -203,3 +203,8 @@ config DEBUG_READAHEAD echo 1 > /debug/readahead/debug_level # stop filling my kern.log Say N for production servers. + +config READAHEAD_SMOOTH_AGING + def_bool n if NUMA + default y if !NUMA + depends on ADAPTIVE_READAHEAD
include/linux/mmzone.h +5 -0
@@ -161,6 +161,11 @@ struct zone {unsigned long pages_scanned;/* since last reclaim */ int all_unreclaimable;/* All pages pinned */ +/* The accumulated number of activities that may cause page aging, +* that is, make some pages closer to the tail of inactive_list. +*/ +unsigned long aging_total; +/* A count of how many reclaimers are scanning this zone */ atomic_t reclaim_in_progress;
include/linux/mm.h +9 -0
@@ -1044,6 +1044,15 @@ static inline int prefer_adaptive_readahreturn readahead_ratio >=10 ; } +DECLARE_PER_CPU(unsigned long, readahead_aging); +static inline void inc_readahead_aging (void ) +{ +#ifdef CONFIG_READAHEAD_SMOOTH_AGING +if (prefer_adaptive_readahead ()) +per_cpu (readahead_aging,raw_smp_processor_id ())++; +#endif +} +/* Do stack extension */ extern int expand_stack (struct vm_area_struct *vma,unsigned long address);#ifdef CONFIG_IA64
mm/vmscan.c +4 -0
@@ -457,6 +457,9 @@ static unsigned long shrink_page_list(stif (PageWriteback (page)) goto keep_locked; +if (!PageReferenced (page)) +inc_readahead_aging (); + referenced =page_referenced (page,1 );/* In active use or really unfreeable? Activate it. */ if (referenced &&page_mapping_inuse (page))
@@ -655,6 +658,7 @@ static unsigned long shrink_inactive_lis &page_list, &nr_scan); zone->nr_inactive -= nr_taken; zone->pages_scanned += nr_scan; + zone->aging_total += nr_scan;spin_unlock_irq (&zone->lru_lock); nr_scanned += nr_scan;
mm/swap.c +2 -0
@@ -127,6 +127,8 @@ void fastcall mark_page_accessed(structClearPageReferenced (page); }else if (!PageReferenced (page)) {SetPageReferenced (page); +if (PageLRU (page)) +inc_readahead_aging (); } }
mm/readahead.c +49 -0
67 lines not on this page · raw message
--
Re: [PATCH 13/33] readahead: state based method - aging accounting
(hey, I haven't finished reading the last batch yet)
Quoted 16 lines · Wu Fengguang
/*
+ * The node's effective length ofinactive_list(s).
+ */
+static unsigned longnode_free_and_cold_pages(void)+{
+ unsigned int i;
+ unsigned long sum = 0;
+ struct zone *zones = NODE_DATA(numa_node_id())->node_zones;
+
+ for (i = 0; i <MAX_NR_ZONES; i++)
+ sum += zones[i].nr_inactive +
+ zones[i].free_pages - zones[i].pages_low;
+
+ return sum;
+}
I guess this should go into page_alloc.c along with all the similar functions.
Is this function well-named? Why does it have "cold" in the name?
Re: [PATCH 13/33] readahead: state based method - aging accounting
Quoted 21 lines · Andrew Morton
(hey, I haven't finished reading the last batch yet)
Quoted 16 lines · Wu Fengguang
/*
+ * The node's effective length ofinactive_list(s).
+ */
+static unsigned longnode_free_and_cold_pages(void)+{
+ unsigned int i;
+ unsigned long sum = 0;
+ struct zone *zones = NODE_DATA(numa_node_id())->node_zones;
+
+ for (i = 0; i <MAX_NR_ZONES; i++)
+ sum += zones[i].nr_inactive +
+ zones[i].free_pages - zones[i].pages_low;
+
+ return sum;
+}
Quoted 1 line
I guess this should go into
page_alloc.calong with all the similar functions.
Moved as adviced.
Quoted 1 line
Is this function well-named? Why does it have "cold" in the name?
Because it only sums nr_inactive', leaving out nr_active'.
Re: [PATCH 13/33] readahead: state based method - aging accounting
Quoted 4 lines · Wu Fengguang
Quoted 2 lines
Is this function well-named? Why does it have "cold" in the name?
Because it only sums
nr_inactive', leaving outnr_active'.
We use the term "cold" to refer to probably-cache-cold pages in the page allocator. How about you use "inactive"?
Re: [PATCH 13/33] readahead: state based method - aging accounting
Quoted 8 lines · Andrew Morton
Quoted 4 lines · Wu Fengguang
Quoted 2 lines
Is this function well-named? Why does it have "cold" in the name?
Because it only sums
nr_inactive', leaving outnr_active'.We use the term "cold" to refer to probably-cache-cold pages in the page allocator. How about you use "inactive"?
Got it, thanks.
PATCH 14/33 readahead: state based method - data structure
In reply to a message not in the archiveExtend struct file_ra_state to support the adaptive read-ahead logic.
---
include/linux/fs.h | 57 +++++++++++++++++++++++++++++++++++++++++++---------- 1 files changed, 47 insertions(+), 10 deletions(-)
include/linux/fs.h +47 -10
@@ -613,21 +613,58 @@ struct fown_struct {/* * Track a single file's readahead state +* +* Diagram for the adaptive readahead logic: +* +* |--------- old chunk ------->|-------------- new chunk -------------->| +* +----------------------------+----------------------------------------+ +* | # | # | +* +----------------------------+----------------------------------------+ +* ^ ^ ^ ^ +* file_ra_state.la_index .ra_index .lookahead_index .readahead_index +* +* Deduced sizes: +* |----------- readahead size ------------>| +* +----------------------------+----------------------------------------+ +* | # | # | +* +----------------------------+----------------------------------------+ +* |------- invoke interval ------>|-- lookahead size -->| */ struct file_ra_state { -unsigned long start;/* Current window */ -unsigned long size; -unsigned long flags;/* ra flags RA_FLAG_xxx*/ -unsigned long cache_hit;/* cache hit count*/ -unsigned long prev_page;/* Cache last read() position */ -unsigned long ahead_start;/* Ahead window */ -unsigned long ahead_size; -unsigned long ra_pages;/* Maximum readahead window */ -unsigned long mmap_hit;/* Cache hit stat for mmap accesses */ -unsigned long mmap_miss;/* Cache miss stat for mmap accesses */ +union { +struct {/* conventional read-ahead */ +unsigned long start;/* Current window */ +unsigned long size; +unsigned long ahead_start;/* Ahead window */ +unsigned long ahead_size; +unsigned long cache_hit;/* cache hit count */ + }; +#ifdef CONFIG_ADAPTIVE_READAHEAD +struct {/* adaptive read-ahead */ +pgoff_t la_index; +pgoff_t ra_index; +pgoff_t lookahead_index; +pgoff_t readahead_index; +unsigned long age; +uint64_t cache_hits; + }; +#endif + }; + +/* mmap read-around */ +unsigned long mmap_hit;/* Cache hit stat for mmap accesses */ +unsigned long mmap_miss;/* Cache miss stat for mmap accesses */ + +/* common ones */ +unsigned long flags;/* ra flags RA_FLAG_xxx*/ +unsigned long prev_page;/* Cache last read() position */ +unsigned long ra_pages;/* Maximum readahead window */ };#define RA_FLAG_MISS 0x01/* a cache miss occured against this file */ #define RA_FLAG_INCACHE 0x02/* file is already in cache */ +#define RA_FLAG_MMAP (1UL<<31)/* mmaped page access */ +#define RA_FLAG_NO_LOOKAHEAD (1UL<<30)/* disable look-ahead */ +#define RA_FLAG_EOF (1UL<<29)/* readahead hits EOF */ struct file {/*
--
Re: [PATCH 14/33] readahead: state based method - data structure
Quoted 2 lines · Wu Fengguang
Extend struct
file_ra_stateto support the adaptive read-ahead logic.
Another nitpick: It is usually OK to do these things in the same patch that actually uses the new data (or functions -- eg. patch 15).
If the addition is complex or in a completely different subsystem (eg. your rescue_pages function), _that_ can justify it being split into its own patch. Then you might also prepend the subject with mm:
and cc linux-mm to get better reviews.
--
Send instant messages to your online friends http://au.messenger.yahoo.com
Re: [PATCH 14/33] readahead: state based method - data structure
Quoted 5 lines · Nick Piggin
Quoted 2 lines · Wu Fengguang
Extend struct
file_ra_stateto support the adaptive read-ahead logic.
Quoted 7 lines
Another nitpick: It is usually OK to do these things in the same patch that actually uses the new data (or functions -- eg. patch 15).
If the addition is complex or in a completely different subsystem (eg. your
rescue_pagesfunction), _that_ can justify it being split into its own patch. Then you might also prepend the subject with mm:
and cc linux-mm to get better reviews.
Ok, thanks for the advice.
Regards,
Wu
Re: [PATCH 14/33] readahead: state based method - data structure
In reply to Wu FengguangQuoted 6 lines · Wu Fengguang
#define
RA_FLAG_MISS0x01/* a cache miss occured against this file */
#defineRA_FLAG_INCACHE0x02/* file is already in cache */
+#defineRA_FLAG_MMAP(1UL<<31) /* mmaped page access */
+#defineRA_FLAG_NO_LOOKAHEAD(1UL<<30) /* disable look-ahead */
+#defineRA_FLAG_EOF(1UL<<29) /* readahead hits EOF */
Odd. Why not use 4, 8, 16?
Re: [PATCH 14/33] readahead: state based method - data structure
Quoted 9 lines · Andrew Morton
Quoted 6 lines · Wu Fengguang
#define
RA_FLAG_MISS0x01/* a cache miss occured against this file */
#defineRA_FLAG_INCACHE0x02/* file is already in cache */
+#defineRA_FLAG_MMAP(1UL<<31) /* mmaped page access */
+#defineRA_FLAG_NO_LOOKAHEAD(1UL<<30) /* disable look-ahead */
+#defineRA_FLAG_EOF(1UL<<29) /* readahead hits EOF */Odd. Why not use 4, 8, 16?
Sorry, the lower 8 bits are for ra_class values in the new code. It can cause data corruption when dynamic switching between the two logics :(
I'd like to change the flags member to explicit ones like
struct {
unsigned miss :1;
unsigned incache :1;
unsigned mmap :1;
unsigned no_lookahead :1;
unsigned eof :1;
} flags;
unsigned class_new :4;
unsigned class_old :4;Reasonable?
Re: [PATCH 14/33] readahead: state based method - data structure
In reply to Andrew MortonQuoted 9 lines · Andrew Morton
Quoted 6 lines · Wu Fengguang
#define
RA_FLAG_MISS0x01/* a cache miss occured against this file */
#defineRA_FLAG_INCACHE0x02/* file is already in cache */
+#defineRA_FLAG_MMAP(1UL<<31) /* mmaped page access */
+#defineRA_FLAG_NO_LOOKAHEAD(1UL<<30) /* disable look-ahead */
+#defineRA_FLAG_EOF(1UL<<29) /* readahead hits EOF */Odd. Why not use 4, 8, 16?
I'm now settled with:
-#define RA_FLAG_MISS 0x01 /* a cache miss occured against this file */
-#define RA_FLAG_INCACHE 0x02 /* file is already in cache */
+#define RA_FLAG_MISS (1UL<<31) /* a cache miss occured against this file */
+#define RA_FLAG_INCACHE (1UL<<30) /* file is already in cache */ +#define RA_FLAG_MMAP (1UL<<29) /* mmaped page access */ +#define RA_FLAG_NO_LOOKAHEAD (1UL<<28) /* disable look-ahead */ +#define RA_FLAG_EOF (1UL<<27) /* readahead hits EOF */
And still let the low bits hold ra_class values.
PATCH 15/33 readahead: state based method - routines
In reply to a message not in the archiveDefine some helpers on struct file_ra_state.
---
mm/readahead.c | 188 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++- 1 files changed, 186 insertions(+), 2 deletions(-)
mm/readahead.c +186 -2
@@ -854,6 +854,190 @@ static unsigned long node_readahead_agin }/* +* Some helpers for querying/building a read-ahead request. +* +* Diagram for some variable names used frequently: +* +* |<------- la_size ------>| +* +-----------------------------------------+ +* | # | +* +-----------------------------------------+ +* ra_index -->|<---------------- ra_size -------------->| +* +*/ + +static enum ra_class ra_class_new (struct file_ra_state *ra) +{ +return ra->flags &RA_CLASS_MASK ; +} + +static inline enum ra_class ra_class_old (struct file_ra_state *ra) +{ +return (ra->flags >>RA_CLASS_SHIFT ) &RA_CLASS_MASK ; +} + +static unsigned long ra_readahead_size (struct file_ra_state *ra) +{ +return ra->readahead_index - ra->ra_index; +} + +static unsigned long ra_lookahead_size (struct file_ra_state *ra) +{ +return ra->readahead_index - ra->lookahead_index; +} + +static unsigned long ra_invoke_interval (struct file_ra_state *ra) +{ +return ra->lookahead_index - ra->la_index; +} + +/* +* The 64bit cache_hits stores three accumulated values and a counter value. +* MSB LSB +* 3333333333333333 : 2222222222222222 : 1111111111111111 : 0000000000000000 +*/ +static int ra_cache_hit (struct file_ra_state *ra,int nr) +{ +return (ra->cache_hits >> (nr *16 )) &0xFFFF ; +} + +/* +* Conceptual code: +* ra_cache_hit(ra, 1) += ra_cache_hit(ra, 0); +* ra_cache_hit(ra, 0) = 0; +*/ +static void ra_addup_cache_hit (struct file_ra_state *ra) +{ +int n; + + n =ra_cache_hit (ra,0 ); + ra->cache_hits -= n; + n <<=16 ; + ra->cache_hits += n; +} + +/* +* The read-ahead is deemed success if cache-hit-rate >= 1/readahead_hit_rate. +*/ +static int ra_cache_hit_ok (struct file_ra_state *ra) +{ +return ra_cache_hit (ra,0 ) * readahead_hit_rate >= + (ra->lookahead_index - ra->la_index); +} + +/* +* Check if @index falls in the @ra request. +*/ +static int ra_has_index (struct file_ra_state *ra,pgoff_t index) +{ +if (index < ra->la_index || index >= ra->readahead_index) +return 0 ; + +if (index >= ra->ra_index) +return 1 ; +else +return -1 ; +} + +/* +* Which method is issuing this read-ahead? +*/ +static void ra_set_class (struct file_ra_state *ra, +enum ra_class ra_class) +{ +unsigned long flags_mask; +unsigned long flags; +unsigned long old_ra_class; + + flags_mask = ~(RA_CLASS_MASK | (RA_CLASS_MASK <<RA_CLASS_SHIFT )); + flags = ra->flags & flags_mask; + + old_ra_class =ra_class_new (ra) <<RA_CLASS_SHIFT ; + + ra->flags = flags | old_ra_class | ra_class; + +ra_addup_cache_hit (ra); +if (ra_class !=RA_CLASS_STATE ) + ra->cache_hits <<=16 ; + + ra->age =node_readahead_aging (); +} + +/* +* Where is the old read-ahead and look-ahead? +*/ +static void ra_set_index (struct file_ra_state *ra, +pgoff_t la_index,pgoff_t ra_index) +{ + ra->la_index = la_index; + ra->ra_index = ra_index; +} + +/* +* Where is the new read-ahead and look-ahead? +*/ +static void ra_set_size (struct file_ra_state *ra, +unsigned long ra_size,unsigned long la_size) +{ +/* Disable look-ahead for loopback file. */ +if (unlikely (ra->flags &RA_FLAG_NO_LOOKAHEAD )) + la_size =0 ; + + ra->readahead_index = ra->ra_index + ra_size; + ra->lookahead_index = ra->readahead_index - la_size; +} + +/* +* Submit IO for the read-ahead request in file_ra_state. +*/ +static int ra_dispatch (struct file_ra_state *ra, +struct address_space *mapping,struct file *filp) +{ +enum ra_class ra_class =ra_class_new (ra); +unsigned long ra_size =ra_readahead_size (ra); +unsigned long la_size =ra_lookahead_size (ra); +pgoff_t eof_index =PAGES_BYTE (i_size_read (mapping->host)) +1 ; +int actual; + +if (unlikely (ra->ra_index >= eof_index)) +return 0 ; + +/* Snap to EOF. */ +if (ra->readahead_index + ra_size /2 > eof_index) { +if (ra_class ==RA_CLASS_CONTEXT_AGGRESSIVE && + eof_index > ra->lookahead_index +1 ) + la_size = eof_index - ra->lookahead_index; +else + la_size =0 ; + ra_size = eof_index - ra->ra_index; +ra_set_size (ra, ra_size, la_size); + ra->flags |=RA_FLAG_EOF ; + } + + actual =__do_page_cache_readahead (mapping, filp, + ra->ra_index, ra_size, la_size); + +#ifdef CONFIG_DEBUG_READAHEAD +if (ra->flags &RA_FLAG_MMAP ) +ra_account (ra,RA_EVENT_READAHEAD_MMAP , actual); +if (ra->readahead_index == eof_index) +ra_account (ra,RA_EVENT_READAHEAD_EOF , actual); +if (la_size) +ra_account (ra,RA_EVENT_LOOKAHEAD , la_size); +if (ra_size > actual) +ra_account (ra,RA_EVENT_IO_CACHE_HIT , ra_size - actual); +ra_account (ra,RA_EVENT_READAHEAD , actual); + +dprintk ("readahead-%s(ino=%lu, index=%lu, ra=%lu+%lu-%lu) = %d\n" , + ra_class_name[ra_class], + mapping->host->i_ino, ra->la_index, + ra->ra_index, ra_size, la_size, actual); +#endif /* CONFIG_DEBUG_READAHEAD */ + +return actual; +} + +/* * ra_min is mainly determined by the size of cache memory. Reasonable? * * Table of concrete numbers for 4KB page size:
@@ -925,10 +1109,10 @@ static void ra_account(struct file_ra_streturn ;if (e ==RA_EVENT_READAHEAD_HIT && pages <0 ) { - c = (ra->flags >>RA_CLASS_SHIFT ) &RA_CLASS_MASK ; + c =ra_class_old (ra); pages = -pages; }else if (ra) - c = ra->flags &RA_CLASS_MASK ; + c =ra_class_new (ra);else c =RA_CLASS_NONE ;
--
Re: [PATCH 15/33] readahead: state based method - routines
mm/readahead.c static unsigned long node_readahead_agin · line 902
Quoted 12 lines · Wu Fengguang
Define some helpers on struct
file_ra_state.mm/readahead.c +9
-0+/* +* The 64bit cache_hits stores three accumulated values and a counter value. +* MSB LSB +* 3333333333333333 : 2222222222222222 : 1111111111111111 : 0000000000000000 +*/ +static int ra_cache_hit (struct file_ra_state *ra,int nr) +{ +return (ra->cache_hits >> (nr *16 )) &0xFFFF ; +}
So... why not use four u16s?
mm/readahead.c static unsigned long node_readahead_agin · line 999
Quoted 10 lines
mm/readahead.c +10
-0+/* +* Submit IO for the read-ahead request in file_ra_state. +*/ +static int ra_dispatch (struct file_ra_state *ra, +struct address_space *mapping,struct file *filp) +{ +enum ra_class ra_class =ra_class_new (ra); +unsigned long ra_size =ra_readahead_size (ra); +unsigned long la_size =ra_lookahead_size (ra); +pgoff_t eof_index =PAGES_BYTE (i_size_read (mapping->host)) +1 ;
Sigh. I guess one gets used to that PAGES_BYTE thing after a while. If you're not familiar with it, it obfuscates things.
<hunts around for its definition>
So in fact it's converting a loff_t to a pgoff_t. Why not call it convert_loff_t_to_pgoff_t()? ;)
Something better, anyway. Something lower-case and an inline-not-a-macro, too.
mm/readahead.c static unsigned long node_readahead_agin · line 1006
Quoted 7 lines
mm/readahead.c +7
-0+int actual; + +if (unlikely (ra->ra_index >= eof_index)) +return 0 ; + +/* Snap to EOF. */ +if (ra->readahead_index + ra_size /2 > eof_index) {
You've had a bit of a think and you've arrived at a design decision surrounding the arithmetic in here. It's very very hard to look at this line of code and to work out why you decided to implement it in this fashion. The only way to make such code comprehensible (and hence maintainable) is to fully comment such things.
Re: [PATCH 15/33] readahead: state based method - routines
Quoted 4 lines · Andrew Morton
Quoted 3 lines · Wu Fengguang
Define some helpers on struct
file_ra_state.
Quoted 11 lines
mm/readahead.c static unsigned long node_readahead_agin · line 902
Quoted 9 lines
mm/readahead.c +9
-0+/* +* The 64bit cache_hits stores three accumulated values and a counter value. +* MSB LSB +* 3333333333333333 : 2222222222222222 : 1111111111111111 : 0000000000000000 +*/ +static int ra_cache_hit (struct file_ra_state *ra,int nr) +{ +return (ra->cache_hits >> (nr *16 )) &0xFFFF ; +}So... why not use four u16s?
Sure, me too, have been thinking about it ;-)
Quoted 14 lines
mm/readahead.c static unsigned long node_readahead_agin · line 999
Quoted 10 lines
mm/readahead.c +10
-0+/* +* Submit IO for the read-ahead request in file_ra_state. +*/ +static int ra_dispatch (struct file_ra_state *ra, +struct address_space *mapping,struct file *filp) +{ +enum ra_class ra_class =ra_class_new (ra); +unsigned long ra_size =ra_readahead_size (ra); +unsigned long la_size =ra_lookahead_size (ra); +pgoff_t eof_index =PAGES_BYTE (i_size_read (mapping->host)) +1 ;Sigh. I guess one gets used to that
PAGES_BYTEthing after a while. If you're not familiar with it, it obfuscates things.
Quoted 6 lines
<hunts around for its definition>
So in fact it's converting a
loff_tto apgoff_t. Why not call itconvert_loff_t_to_pgoff_t()? ;)Something better, anyway. Something lower-case and an inline-not-a-macro, too.
I'm now using DIV_ROUND_UP(), maybe we can settle with that.
Quoted 5 lines
Quoted 5 lines
mm/readahead.c +5
-0+int actual; + +if (unlikely (ra->ra_index >= eof_index)) +return 0 ; +
Quoted 8 lines
mm/readahead.c static unsigned long node_readahead_agin · line 1006
Quoted 2 lines
mm/readahead.c +2
-0+/* Snap to EOF. */ +if (ra->readahead_index + ra_size /2 > eof_index) {You've had a bit of a think and you've arrived at a design decision surrounding the arithmetic in here. It's very very hard to look at this line of code and to work out why you decided to implement it in this fashion. The only way to make such code comprehensible (and hence maintainable) is to fully comment such things.
Sorry for being a bit lazy.
It is true that some situations are rather tricky, and some if()/numbers are carefully chosen. I'll continue expanding/detailing the documentation with future releases. Or would you prefer to add them as small and distinct patches?
Comments for this one(also rationalized code):
/*
* Snap to EOF, if the request
* - crossed the EOF boundary;
* - is close to EOF(explained below).
*
* Imagine a file sized 18 pages, and we dicided to read-ahead the
* first 16 pages. It is highly possible that in the near future we
* will have to do another read-ahead for the remaining 2 pages,
* which is an unfavorable small I/O.
*
* So we prefer to take a bit risk to enlarge the current read-ahead,
* to eliminate possible future small I/O.
*/
if (ra->readahead_index + ra_readahead_size(ra)/4 > eof_index) {
ra->readahead_index = eof_index;
if (ra->lookahead_index > eof_index)
ra->lookahead_index = eof_index;
ra->flags |= RA_FLAG_EOF;
}Wu
PATCH 17/33 readahead: context based method
In reply to a message not in the archiveThis is the slow code path of adaptive read-ahead.
No valid state info is available, so the page cache is queried to obtain the required position/timing info. This kind of estimation is more conservative than the stateful method, and also fluctuates more on load variance.
HOW IT WORKS
============
It works by peeking into the file cache and check if there are any history pages present or accessed. In this way it can detect almost all forms of sequential / semi-sequential read patterns, e.g.
- parallel / interleaved sequential scans on one file
- sequential reads across file open/close
- mixed sequential / random accesses
- sparse / skimming sequential read
HOW DATABASES CAN BENEFIT FROM IT
=================================
The adaptive readahead might help db performance in the following cases:
- concurrent sequential scans
- sequential scan on a fragmented table
- index scan with clustered matches
- index scan on majority rows (in case the planner goes wrong)
ALGORITHM STEPS
===============
- look back/forward to find the ra_index;
- look back to estimate a thrashing safe ra_size;
- assemble the next read-ahead request in file_ra_state;
- submit it.
ALGORITHM DYNAMICS
==================
* startup
When a sequential read is detected, chunk size is set to readahead-min and grows up with each readahead. The grow speed is controlled by readahead-ratio. When readahead-ratio == 100, the new logic grows chunk sizes exponentially -- like the current logic, but lags behind it at early steps.
* stabilize
When chunk size reaches readahead-max, or comes close to
(readahead-ratio * thrashing-threshold)
it stops growing and stay there.
The main difference with the stock readahead logic occurs at and after the time chunk size stops growing:
- The current logic grows chunk size exponentially in normal and decreases it by 2 each time thrashing is seen. That can lead to thrashing with almost every readahead for very slow streams.
- The new logic can stop at a size below the thrashing-threshold, and stay there stable.
* on stream speed up or system load fall
thrashing-threshold follows up and chunk size is likely to be enlarged.
* on stream slow down or system load rocket up thrashing-threshold falls down.
If thrashing happened, the next read would be treated as a random read, and with another read the chunk-size-growing-phase is restarted.
For a slow stream that has (thrashing-threshold < readahead-max):
- When readahead-ratio = 100, there is only one chunk in cache at most time;
- When readahead-ratio = 50, there are two chunks in cache at most time.
- Lowing readahead-ratio helps gracefully cut down the chunk size without thrashing.
OVERHEADS
=========
The context based method has some overheads over the stateful method, due to more lockings and memory scans.
Running oprofile on the following command shows the following differences:
# diff sparse sparse1
total oprofile samples run1 run2 stateful method 560482 558696 stateless method 564463 559413
So the average overhead is about 0.4%.
Detailed diffprofile data:
# diffprofile oprofile.50.stateful oprofile.50.stateless
2998 41.1% isolate_lru_pages
2669 26.4% shrink_zone
1822 14.7% system_call
1419 27.6% radix_tree_delete
1376 14.8% _raw_write_lock
1279 27.4% free_pages_bulk
1111 12.0% _raw_write_unlock
1035 43.3% free_hot_cold_page
849 15.3% unlock_page
786 29.6% page_referenced
710 4.6% kmap_atomic
651 26.4% __pagevec_release_nonlru
586 16.1% __rmqueue
578 11.3% find_get_page
481 15.5% page_waitqueue
440 6.6% add_to_page_cache
420 33.7% fget_light
260 4.3% get_page_from_freelist
223 13.7% find_busiest_group
221 35.1% mutex_debug_check_no_locks_freed
211 0.0% radix_tree_scan_hole
198 35.5% delay_tsc
195 14.8% ext3_get_branch
182 12.6% profile_tick
173 0.0% radix_tree_cache_lookup_node
164 22.9% find_next_bit
162 50.3% page_cache_readahead_adaptive
...
106 0.0% radix_tree_scan_hole_backward
...
-51 -7.6% radix_tree_preload
...
-68 -2.1% radix_tree_insert
...
-87 -2.0% mark_page_accessed
-88 -2.0% __pagevec_lru_add
-103 -7.7% softlockup_tick
-107 -71.8% free_block
-122 -77.7% do_IRQ
-132 -82.0% do_timer
-140 -47.1% ack_edge_ioapic_vector
-168 -81.2% handle_IRQ_event
-192 -35.2% irq_entries_start
-204 -14.8% rw_verify_area
-214 -13.2% account_system_time
-233 -9.5% radix_tree_lookup_node
-234 -16.6% scheduler_tick
-259 -58.7% __do_IRQ
-266 -6.8% put_page
-318 -29.3% rcu_pending
-333 -3.0% do_generic_mapping_read
-337 -28.3% hrtimer_run_queues
-493 -27.0% __rcu_pending
-1038 -9.4% default_idle
-3323 -3.5% __copy_to_user_ll
-10331 -5.9% do_mpage_readpage# diffprofile oprofile.50.stateful2 oprofile.50.stateless2
1739 1.1% do_mpage_readpage
833 0.9% __copy_to_user_ll
340 21.3% find_busiest_group
288 9.5% free_hot_cold_page
261 4.6% _raw_read_unlock
239 3.9% get_page_from_freelist
201 0.0% radix_tree_scan_hole
163 14.3% raise_softirq
160 0.0% radix_tree_cache_lookup_node
160 11.8% update_process_times
136 9.3% fget_light
121 35.1% page_cache_readahead_adaptive
117 36.0% restore_all
117 2.8% mark_page_accessed
109 6.4% rebalance_tick
107 9.4% sys_read
102 0.0% radix_tree_scan_hole_backward
...
63 4.0% readahead_cache_hit
...
-10 -15.9% radix_tree_node_alloc
...
-39 -1.7% radix_tree_lookup_node
-39 -10.3% irq_entries_start
-43 -1.3% radix_tree_insert
...
-47 -4.6% __do_page_cache_readahead
-64 -9.3% radix_tree_preload
-65 -5.4% rw_verify_area
-65 -2.2% vfs_read
-70 -4.7% timer_interrupt
-71 -1.0% __wake_up_bit
-73 -1.1% radix_tree_delete
-79 -12.6% __mod_page_state_offset
-94 -1.8% __find_get_block
-94 -2.2% __pagevec_lru_add
-102 -1.7% free_pages_bulk
-116 -1.3% _raw_read_lock
-123 -7.4% do_sync_read
-130 -8.4% ext3_get_blocks_handle
-142 -3.8% put_page
-146 -7.9% mpage_readpages
-147 -5.6% apic_timer_interrupt
-168 -1.6% _raw_write_unlock
-172 -5.0% page_referenced
-206 -3.2% unlock_page
-212 -15.0% restore_nocheck
-213 -2.1% default_idle
-245 -5.0% __rmqueue
-278 -4.3% find_get_page
-282 -2.1% system_call
-287 -11.8% run_timer_softirq
-300 -2.7% _raw_write_lock
-420 -3.2% shrink_zone
-661 -5.7% isolate_lru_pages---
mm/readahead.c | 329 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 files changed, 329 insertions(+)
mm/readahead.c +329 -0
@@ -1185,6 +1185,335 @@ state_based_readahead(struct address_spa }/* +* Page cache context based estimation of read-ahead/look-ahead size/index. +* +* The logic first looks around to find the start point of next read-ahead, +* and then, if necessary, looks backward in the inactive_list to get an +* estimation of the thrashing-threshold. +* +* The estimation theory can be illustrated with figure: +* +* chunk A chunk B chunk C head +* +* l01 l11 l12 l21 l22 +*| |-->|-->| |------>|-->| |------>| +*| +-------+ +-----------+ +-------------+ | +*| | # | | # | | # | | +*| +-------+ +-----------+ +-------------+ | +*| |<==============|<===========================|<============================| +* L0 L1 L2 +* +* Let f(l) = L be a map from +* l: the number of pages read by the stream +* to +* L: the number of pages pushed into inactive_list in the mean time +* then +* f(l01) <= L0 +* f(l11 + l12) = L1 +* f(l21 + l22) = L2 +* ... +* f(l01 + l11 + ...) <= Sum(L0 + L1 + ...) +* <= Length(inactive_list) = f(thrashing-threshold) +* +* So the count of countinuous history pages left in the inactive_list is always +* a lower estimation of the true thrashing-threshold. +*/ + +#define PAGE_REFCNT_0 0 +#define PAGE_REFCNT_1 (1 << PG_referenced) +#define PAGE_REFCNT_2 (1 << PG_active) +#define PAGE_REFCNT_3 ((1 << PG_active) | (1 << PG_referenced)) +#define PAGE_REFCNT_MASK PAGE_REFCNT_3 + +/* +* STATUS REFERENCE COUNT +* __ 0 +* _R PAGE_REFCNT_1 +* A_ PAGE_REFCNT_2 +* AR PAGE_REFCNT_3 +* +* A/R: Active / Referenced +*/ +static inline unsigned long page_refcnt (struct page *page) +{ +return page->flags &PAGE_REFCNT_MASK ; +} + +/* +* STATUS REFERENCE COUNT TYPE +* __ 0 fresh +* _R PAGE_REFCNT_1 stale +* A_ PAGE_REFCNT_2 disturbed once +* AR PAGE_REFCNT_3 disturbed twice +* +* A/R: Active / Referenced +*/ +static inline unsigned long cold_page_refcnt (struct page *page) +{ +if (!page ||PageActive (page)) +return 0 ; + +return page_refcnt (page); +} + +/* +* Find past-the-end index of the segment at @index. +*/ +static pgoff_t find_segtail (struct address_space *mapping, +pgoff_t index,unsigned long max_scan) +{ +pgoff_t ra_index; + +cond_resched (); +read_lock_irq (&mapping->tree_lock); + ra_index =radix_tree_scan_hole (&mapping->page_tree, index, max_scan); +read_unlock_irq (&mapping->tree_lock); + +if (ra_index <= index + max_scan) +return ra_index; +else +return 0 ; +} + +/* +* Find past-the-end index of the segment before @index. +*/ +static pgoff_t find_segtail_backward (struct address_space *mapping, +pgoff_t index,unsigned long max_scan) +{ +struct radix_tree_cache cache; +struct page *page; +pgoff_t origin; + + origin = index; +if (max_scan > index) + max_scan = index; + +cond_resched (); +radix_tree_cache_init (&cache); +read_lock_irq (&mapping->tree_lock); +for (; origin - index < max_scan;) { + page =radix_tree_cache_lookup (&mapping->page_tree, + &cache, --index); +if (page) { +read_unlock_irq (&mapping->tree_lock); +return index +1 ; + } + } +read_unlock_irq (&mapping->tree_lock); + +return 0 ; +} + +/* +* Count/estimate cache hits in range [first_index, last_index]. +* The estimation is simple and optimistic. +*/ +static int count_cache_hit (struct address_space *mapping, +pgoff_t first_index,pgoff_t last_index) +{ +struct page *page; +int size = last_index - first_index +1 ; +int count =0 ; +int i; + +cond_resched (); +read_lock_irq (&mapping->tree_lock); + +/* +* The first page may well is chunk head and has been accessed, +* so it is index 0 that makes the estimation optimistic. This +* behavior guarantees a readahead when (size < ra_max) and +* (readahead_hit_rate >= 16). +*/ +for (i =0 ; i <16 ;) { + page =__find_page (mapping, first_index + + size * ((i++ *29 ) &15 ) /16 ); +if (cold_page_refcnt (page) >=PAGE_REFCNT_1 && ++count >=2 ) +break ; + } + +read_unlock_irq (&mapping->tree_lock); + +return size * count / i; +} + +/* +* Look back and check history pages to estimate thrashing-threshold. +*/ +static unsigned long query_page_cache_segment (struct address_space *mapping, +struct file_ra_state *ra, +unsigned long *remain,pgoff_t offset, +unsigned long ra_min,unsigned long ra_max) +{ +pgoff_t index; +unsigned long count; +unsigned long nr_lookback; +struct radix_tree_cache cache; + +/* +* Scan backward and check the near @ra_max pages. +* The count here determines ra_size. +*/ +cond_resched (); +read_lock_irq (&mapping->tree_lock); + index =radix_tree_scan_hole_backward (&mapping->page_tree, + offset, ra_max); +read_unlock_irq (&mapping->tree_lock); + + *remain = offset - index; + +if (offset == ra->readahead_index &&ra_cache_hit_ok (ra)) + count = *remain; +else if (count_cache_hit (mapping, index +1 , offset) * + readahead_hit_rate >= *remain) + count = *remain; +else + count = ra_min; + +/* +* Unnecessary to count more? +*/ +if (count < ra_max) + goto out; + +if (unlikely (ra->flags &RA_FLAG_NO_LOOKAHEAD )) + goto out; + +/* +* Check the far pages coarsely. +* The enlarged count here helps increase la_size. +*/ + nr_lookback = ra_max * (LOOKAHEAD_RATIO +1 ) * +100 / (readahead_ratio |1 ); + +cond_resched (); +radix_tree_cache_init (&cache); +read_lock_irq (&mapping->tree_lock); +for (count += ra_max; count < nr_lookback; count += ra_max) { +struct radix_tree_node *node; + node =radix_tree_cache_lookup_parent (&mapping->page_tree, + &cache, offset - count,1 ); +if (!node) +break ; + } +read_unlock_irq (&mapping->tree_lock); + +out: +/* +* For sequential read that extends from index 0, the counted value +* may well be far under the true threshold, so return it unmodified +* for further processing in adjust_rala_aggressive(). +*/ +if (count >= offset) + count = offset; +else + count =max (ra_min, count * readahead_ratio /100 ); + +ddprintk ("query_page_cache_segment: " +"ino=%lu, idx=%lu, count=%lu, remain=%lu\n" , + mapping->host->i_ino, offset, count, *remain); + +return count; +} + +/* +* Determine the request parameters for context based read-ahead that extends +* from start of file. +* +* The major weakness of stateless method is perhaps the slow grow up speed of +* ra_size. The logic tries to make up for this in the important case of +* sequential reads that extend from start of file. In this case, the ra_size +* is not chosen to make the whole next chunk safe (as in normal ones). Only +* half of which is safe. The added 'unsafe' half is the look-ahead part. It +* is expected to be safeguarded by rescue_pages() when the previous chunks are +* lost. +*/ +static int adjust_rala_aggressive (unsigned long ra_max, +unsigned long *ra_size,unsigned long *la_size) +{ +pgoff_t index = *ra_size; + + *ra_size -=min (*ra_size, *la_size); + *ra_size = *ra_size * readahead_ratio /100 ; + *la_size = index * readahead_ratio /100 ; + *ra_size += *la_size; + +if (*ra_size > ra_max) + *ra_size = ra_max; +if (*la_size > *ra_size) + *la_size = *ra_size; + +return 1 ; +} + +/* +* Main function for page context based read-ahead. +* +* RETURN VALUE HINT +* 1 @ra contains a valid ra-request, please submit it +* 0 no seq-pattern discovered, please try the next method +* -1 please don't do _any_ readahead +*/ +static int +try_context_based_readahead (struct address_space *mapping, +struct file_ra_state *ra,struct page *prev_page, +struct page *page,pgoff_t index, +unsigned long ra_min,unsigned long ra_max) +{ +pgoff_t ra_index; +unsigned long ra_size; +unsigned long la_size; +unsigned long remain_pages; + +/* Where to start read-ahead? +* NFSv3 daemons may process adjacent requests in parallel, +* leading to many locally disordered, globally sequential reads. +* So do not require nearby history pages to be present or accessed. +*/ +if (page) { + ra_index =find_segtail (mapping, index, ra_max *5 /4 ); +if (!ra_index) +return -1 ; + }else if (prev_page ||find_page (mapping, index -1 )) { + ra_index = index; + }else if (readahead_hit_rate >1 ) { + ra_index =find_segtail_backward (mapping, index, + readahead_hit_rate + ra_min); +if (!ra_index) +return 0 ; + ra_min +=2 * (index - ra_index); + index = ra_index;/* pretend the request starts here */ + }else +return 0 ; + + ra_size =query_page_cache_segment (mapping, ra, &remain_pages, + index, ra_min, ra_max); + + la_size = ra_index - index; +if (page && remain_pages <= la_size && + remain_pages < index && la_size >1 ) { +rescue_pages (page, la_size); +return -1 ; + } + +if (ra_size == index) { +if (!adjust_rala_aggressive (ra_max, &ra_size, &la_size)) +return -1 ; +ra_set_class (ra,RA_CLASS_CONTEXT_AGGRESSIVE ); + }else { +if (!adjust_rala (ra_max, &ra_size, &la_size)) +return -1 ; +ra_set_class (ra,RA_CLASS_CONTEXT ); + } + +ra_set_index (ra, index, ra_index); +ra_set_size (ra, ra_size, la_size); + +return 1 ; +} + +/* * ra_min is mainly determined by the size of cache memory. Reasonable? * * Table of concrete numbers for 4KB page size:
--
Re: [PATCH 17/33] readahead: context based method
Quoted 14 lines · Wu Fengguang
mm/readahead.c +12
-0+/* +* Look back and check history pages to estimate thrashing-threshold. +*/ +static unsigned long query_page_cache_segment (struct address_space *mapping, +struct file_ra_state *ra, +unsigned long *remain,pgoff_t offset, +unsigned long ra_min,unsigned long ra_max) +{ +pgoff_t index; +unsigned long count; +unsigned long nr_lookback; +struct radix_tree_cache cache;
mm/readahead.c state_based_readahead(struct address_spa · line 1362
Quoted 10 lines
mm/readahead.c +10
-0+ +/* +* Scan backward and check the near @ra_max pages. +* The count here determines ra_size. +*/ +cond_resched (); +read_lock_irq (&mapping->tree_lock); + index =radix_tree_scan_hole_backward (&mapping->page_tree, + offset, ra_max); +read_unlock_irq (&mapping->tree_lock);
Why do you drop this lock just to pick it up again a few instructions down the line? (is ra_cache_hit_ok or cound_cache_hit very big or unable to be called without the lock?)
Quoted 29 lines
mm/readahead.c +28
-0+ + *remain = offset - index; + +if (offset == ra->readahead_index &&ra_cache_hit_ok (ra)) + count = *remain; +else if (count_cache_hit (mapping, index +1 , offset) * + readahead_hit_rate >= *remain) + count = *remain; +else + count = ra_min; + +/* +* Unnecessary to count more? +*/ +if (count < ra_max) + goto out; + +if (unlikely (ra->flags &RA_FLAG_NO_LOOKAHEAD )) + goto out; + +/* +* Check the far pages coarsely. +* The enlarged count here helps increase la_size. +*/ + nr_lookback = ra_max * (LOOKAHEAD_RATIO +1 ) * +100 / (readahead_ratio |1 ); + +cond_resched ();
mm/readahead.c state_based_readahead(struct address_spa · line 1400
Quoted 10 lines
mm/readahead.c +10
-0+radix_tree_cache_init (&cache); +read_lock_irq (&mapping->tree_lock); +for (count += ra_max; count < nr_lookback; count += ra_max) { +struct radix_tree_node *node; + node =radix_tree_cache_lookup_parent (&mapping->page_tree, + &cache, offset - count,1 ); +if (!node) +break ; + } +read_unlock_irq (&mapping->tree_lock);
Yuck. Apart from not being commented, this depends on internal implementation of radix-tree. This should just be packaged up in some radix-tree function to do exactly what you want (eg. is there a hole of N contiguous pages).
And then again you can be rid of the radix-tree cache.
Yes, it increasingly appears that you're using the cache because you're using the wrong abstractions. Eg. this is basically half implementing some data-structure internal detail.
--
Send instant messages to your online friends http://au.messenger.yahoo.com
Re: [PATCH 17/33] readahead: context based method
Quoted 11 lines · Nick Piggin
mm/readahead.c state_based_readahead(struct address_spa · line 1362
Quoted 6 lines · Wu Fengguang
mm/readahead.c +5
-0+cond_resched (); +read_lock_irq (&mapping->tree_lock); + index =radix_tree_scan_hole_backward (&mapping->page_tree, + offset, ra_max); +read_unlock_irq (&mapping->tree_lock);Why do you drop this lock just to pick it up again a few instructions down the line? (is
ra_cache_hit_okorcound_cache_hitvery big or unable to be called without the lock?)
Nice catch, will fix it.
Quoted 37 lines
Quoted 37 lines
mm/readahead.c +7
-0+ + *remain = offset - index; + +if (offset == ra->readahead_index &&ra_cache_hit_ok (ra)) + count = *remain; + else if (count_cache_hit(mapping, index + 1, offset) * + readahead_hit_rate >=*remain)
mm/readahead.c +29
-0+ count = *remain; + else + count = ra_min; + +/* +* Unnecessary to count more? +*/ +if (count < ra_max) + goto out; + +if (unlikely (ra->flags &RA_FLAG_NO_LOOKAHEAD )) + goto out; + +/* +* Check the far pages coarsely. +* The enlarged count here helps increase la_size. +*/ + nr_lookback = ra_max * (LOOKAHEAD_RATIO +1 ) * +100 / (readahead_ratio |1 ); + +cond_resched (); +radix_tree_cache_init (&cache); +read_lock_irq (&mapping->tree_lock); +for (count += ra_max; count < nr_lookback; count += ra_max) { +struct radix_tree_node *node; + node =radix_tree_cache_lookup_parent (&mapping->page_tree, + &cache, offset - count,1 ); +if (!node) +break ;
Quoted 8 lines
Review
Quoted 3 lines
(quoted diff) +2
-0+ } + read_unlock_irq(&mapping->tree_lock);Yuck. Apart from not being commented, this depends on internal implementation of radix-tree. This should just be packaged up in some radix-tree function to do exactly what you want (eg. is there a hole of N contiguous pages).
Yes, it is ugly.
Maybe we can make it a function named radix_tree_scan_hole_coarse().
Quoted 5 lines
And then again you can be rid of the radix-tree cache.
Yes, it increasingly appears that you're using the cache because you're using the wrong abstractions. Eg. this is basically half implementing some data-structure internal detail.
Sorry for not being aware of this problem :)
Wu
Re: [PATCH 17/33] readahead: context based method
In reply to Wu FengguangQuoted 13 lines · Wu Fengguang
+#define
PAGE_REFCNT_00+#define PAGE_REFCNT_1 (1 << PG_referenced) +#define PAGE_REFCNT_2 (1 << PG_active) +#define PAGE_REFCNT_3 ((1 << PG_active) | (1 << PG_referenced)) +#define PAGE_REFCNT_MASK PAGE_REFCNT_3 + +/* + * STATUS REFERENCE COUNT + * __ 0 + * _R PAGE_REFCNT_1 + * A_ PAGE_REFCNT_2 + * AR PAGE_REFCNT_3
Quoted 8 lines
+ *
+ * A/R: Active / Referenced
+ */
+static inline unsigned longpage_refcnt(struct page *page)+{
+ returnpage->flags&PAGE_REFCNT_MASK;
+}
+
This assumes that PG_referenced < PG_active. Nobody knows that this assumption was made and someone might go and reorder the page flags and subtly break readahead.
We need to either not do it this way, or put a big comment in page-flags.h, or even redefine PG_active to be PG_referenced+1.
Re: [PATCH 17/33] readahead: context based method
Quoted 23 lines · Andrew Morton
Quoted 13 lines · Wu Fengguang
+#define
PAGE_REFCNT_00+#define PAGE_REFCNT_1 (1 << PG_referenced) +#define PAGE_REFCNT_2 (1 << PG_active) +#define PAGE_REFCNT_3 ((1 << PG_active) | (1 << PG_referenced)) +#define PAGE_REFCNT_MASK PAGE_REFCNT_3 + +/* + * STATUS REFERENCE COUNT + * __ 0 + * _R PAGE_REFCNT_1 + * A_ PAGE_REFCNT_2 + * AR PAGE_REFCNT_3Quoted 8 lines
+ *
+ * A/R: Active / Referenced
+ */
+static inline unsigned longpage_refcnt(struct page *page)+{
+ returnpage->flags&PAGE_REFCNT_MASK;
+}
+
Quoted 6 lines
This assumes that
PG_referenced<PG_active. Nobody knows that this assumption was made and someone might go and reorder the page flags and subtly break readahead.We need to either not do it this way, or put a big comment in
page-flags.h, or even redefinePG_activeto be PG_referenced+1.
I have had a code segment like:
#if PG_active < PG_referenced
# error unexpected page flags order
#endif
I'd add it back.
Re: [PATCH 17/33] readahead: context based method
In reply to Wu FengguangQuoted 5 lines · Wu Fengguang
This is the slow code path of adaptive read-ahead.
...
mm/readahead.c state_based_readahead(struct address_spa · line 1316
Quoted 10 lines
mm/readahead.c +10
-0+ +/* +* Count/estimate cache hits in range [first_index, last_index]. +* The estimation is simple and optimistic. +*/ +static int count_cache_hit (struct address_space *mapping, +pgoff_t first_index,pgoff_t last_index) +{ +struct page *page; +int size = last_index - first_index +1 ;
`size' might overflow.
Quoted 5 lines
mm/readahead.c +5
-0+int count =0 ; +int i; + +cond_resched (); +read_lock_irq (&mapping->tree_lock);
mm/readahead.c state_based_readahead(struct address_spa · line 1331
Quoted 10 lines
mm/readahead.c +10
-0+ +/* +* The first page may well is chunk head and has been accessed, +* so it is index 0 that makes the estimation optimistic. This +* behavior guarantees a readahead when (size < ra_max) and +* (readahead_hit_rate >= 16). +*/ +for (i =0 ; i <16 ;) { + page =__find_page (mapping, first_index + + size * ((i++ *29 ) &15 ) /16 );
29?
Re: [PATCH 17/33] readahead: context based method
Quoted 6 lines · Andrew Morton
Quoted 5 lines · Wu Fengguang
This is the slow code path of adaptive read-ahead.
...
Quoted 12 lines
mm/readahead.c state_based_readahead(struct address_spa · line 1316
Quoted 10 lines
mm/readahead.c +10
-0+ +/* +* Count/estimate cache hits in range [first_index, last_index]. +* The estimation is simple and optimistic. +*/ +static int count_cache_hit (struct address_space *mapping, +pgoff_t first_index,pgoff_t last_index) +{ +struct page *page; +int size = last_index - first_index +1 ;`size' might overflow.
It does. Fixed the caller:
@@query_page_cache_segment()
index = radix_tree_scan_hole_backward(&mapping->page_tree,- offset, ra_max);
+ offset - 1, ra_max);
Here (offset >= 1) always holds.
Quoted 9 lines
Quoted 9 lines
mm/readahead.c +9
-0+int count =0 ; +int i; + +cond_resched (); +read_lock_irq (&mapping->tree_lock); + +/* +* The first page may well is chunk head and has been accessed, +* so it is index 0 that makes the estimation optimistic. This
Quoted 8 lines
mm/readahead.c state_based_readahead(struct address_spa · line 1331
Quoted 6 lines
mm/readahead.c +6
-0+* behavior guarantees a readahead when (size < ra_max) and +* (readahead_hit_rate >= 16). +*/ +for (i =0 ; i <16 ;) { + page =__find_page (mapping, first_index + + size * ((i++ *29 ) &15 ) /16 );29?
It's a prime number. Should be made obvious by the following macro:
#define CACHE_HIT_HASH_KEY 29 /* some prime number */
PATCH 18/33 readahead: initial method - guiding sizes
In reply to a message not in the archiveIntroduce three guiding sizes for the initial readahead method.
- ra_pages0: recommended readahead on start-of-file
- ra_expect_bytes: expected read size on start-of-file
- ra_thrash_bytes: estimated thrashing threshold
---
block/ll_rw_blk.c | 4 +--- include/linux/backing-dev.h | 3 +++ mm/readahead.c | 3 +++ 3 files changed, 7 insertions(+), 3 deletions(-)
include/linux/backing-dev.h +3 -0
@@ -24,6 +24,9 @@ typedef int (congested_fn)(void *, int);struct backing_dev_info {unsigned long ra_pages;/* max readahead in PAGE_CACHE_SIZE units */ +unsigned long ra_pages0;/* recommended readahead on start of file */ +unsigned long ra_expect_bytes;/* expected read size on start of file */ +unsigned long ra_thrash_bytes;/* thrashing threshold */ unsigned long state;/* Always use atomic bitops on this */ unsigned int capabilities;/* Device capabilities */ congested_fn *congested_fn;/* Function pointer if device is md/dm */
mm/readahead.c +3 -0
@@ -122,6 +122,9 @@ EXPORT_SYMBOL(default_unplug_io_fn);struct backing_dev_info default_backing_dev_info = { .ra_pages =PAGES_KB (VM_MAX_READAHEAD ), + .ra_pages0 =PAGES_KB (128 ), + .ra_expect_bytes =1024 *VM_MIN_READAHEAD , + .ra_thrash_bytes =1024 *VM_MIN_READAHEAD , .state =0 , .capabilities =BDI_CAP_MAP_COPY , .unplug_io_fn = default_unplug_io_fn,
block/ll_rw_blk.c +1 -3
@@ -249,9 +249,6 @@ void blk_queue_make_request(request_queublk_queue_max_phys_segments (q,MAX_PHYS_SEGMENTS );blk_queue_max_hw_segments (q,MAX_HW_SEGMENTS ); q->make_request_fn = mfn; - q->backing_dev_info.ra_pages = (VM_MAX_READAHEAD *1024 ) /PAGE_CACHE_SIZE ; - q->backing_dev_info.state =0 ; - q->backing_dev_info.capabilities =BDI_CAP_MAP_COPY ;blk_queue_max_sectors (q,SAFE_MAX_SECTORS );blk_queue_hardsect_size (q,512 );blk_queue_dma_alignment (q,511 );
@@ -1850,6 +1847,7 @@ request_queue_t *blk_alloc_queue_node(gf q->kobj.ktype = &queue_ktype;kobject_init (&q->kobj); + q->backing_dev_info = default_backing_dev_info; q->backing_dev_info.unplug_io_fn = blk_backing_dev_unplug; q->backing_dev_info.unplug_io_data = q;
--
PATCH 19/33 readahead: initial method - thrashing guard size
In reply to a message not in the archivebacking_dev_info.ra_thrash_bytes is dynamicly updated to be a little above the thrashing safe read-ahead size. It is used in the initial method where the thrashing threshold for the particular reader is still unknown.
---
mm/readahead.c | 20 ++++++++++++++++++++ 1 files changed, 20 insertions(+)
mm/readahead.c +20 -0
@@ -817,6 +817,22 @@ out: }/* +* Update `backing_dev_info.ra_thrash_bytes' to be a _biased_ average of +* read-ahead sizes. Which makes it an a-bit-risky(*) estimation of the +* _minimal_ read-ahead thrashing threshold on the device. +* +* (*) Note that being a bit risky can _help_ overall performance. +*/ +static inline void update_ra_thrash_bytes (struct backing_dev_info *bdi, +unsigned long ra_size) +{ + ra_size <<=PAGE_CACHE_SHIFT ; + bdi->ra_thrash_bytes = (bdi->ra_thrash_bytes < ra_size) ? + (ra_size + bdi->ra_thrash_bytes *1023 ) /1024 : + (ra_size + bdi->ra_thrash_bytes *7 ) /8 ; +} + +/* * The node's effective length of inactive_list(s). */ static unsigned long node_free_and_cold_pages (void )
@@ -1180,6 +1196,10 @@ state_based_readahead(struct address_spaif (!adjust_rala (growth_limit, &ra_size, &la_size))return 0 ; +/* ra_size in its _steady_ state reflects thrashing threshold */ +if (page && ra_old + ra_old /8 >= ra_size) +update_ra_thrash_bytes (mapping->backing_dev_info, ra_size); +ra_set_class (ra,RA_CLASS_STATE );ra_set_index (ra, index, ra->readahead_index);ra_set_size (ra, ra_size, la_size);
--
PATCH 20/33 readahead: initial method - expected read size
In reply to a message not in the archivebacking_dev_info.ra_expect_bytes is dynamicly updated to be the expected read pages on start-of-file. It allows the initial readahead to be more aggressive and hence efficient.
---
fs/file_table.c | 7 ++++++ include/linux/mm.h | 1 mm/readahead.c | 55 +++++++++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 63 insertions(+)
include/linux/mm.h +1 -0
@@ -1032,6 +1032,7 @@ unsigned long page_cache_readahead(strucvoid handle_ra_miss (struct address_space *mapping,struct file_ra_state *ra,pgoff_t offset);unsigned long max_sane_readahead (unsigned long nr); +void fastcall readahead_close(struct file *file);#ifdef CONFIG_ADAPTIVE_READAHEAD extern int readahead_ratio;
fs/file_table.c +7 -0
@@ -12,6 +12,7 @@#include <linux/init.h> #include <linux/module.h> #include <linux/smp_lock.h> +#include <linux/mm.h> #include <linux/fs.h> #include <linux/security.h> #include <linux/eventpoll.h>
@@ -160,6 +161,12 @@ void fastcall __fput(struct file *file)might_sleep ();fsnotify_close (file); + +#ifdef CONFIG_ADAPTIVE_READAHEAD +if (file->f_ra.flags &RA_FLAG_EOF ) +readahead_close (file); +#endif +/* * The function eventpoll_release() should be the first called * in the file cleanup chain.
mm/readahead.c +55 -0
61 lines not on this page · raw message
--
Re: [PATCH 22/33] readahead: initial method
BTW. while your patchset might be nicely broken down, I think your naming and descriptions are letting it down a little bit.
Quoted 10 lines · Wu Fengguang
Aggressive readahead policy for read on start-of-file.
Instead of selecting a conservative readahead size, it tries to do large readahead in the first place.
However we have to watch on two cases:
- do not ruin the hit rate for file-head-checkers
- do not lead to thrashing for memory tight systems
How does it handle
- don't needlessly readahead too much if the file is in cache
Would the current readahead mechanism benefit from more aggressive start-of-file readahead?
--
Send instant messages to your online friends http://au.messenger.yahoo.com
Re: [PATCH 22/33] readahead: initial method
Quoted 2 lines · Nick Piggin
BTW. while your patchset might be nicely broken down, I think your naming and descriptions are letting it down a little bit.
:) Maybe more practices will help.
Quoted 7 lines
Quoted 5 lines · Wu Fengguang
Aggressive readahead policy for read on start-of-file.
Instead of selecting a conservative readahead size, it tries to do large readahead in the first place.
Quoted 8 lines
Quoted 5 lines
However we have to watch on two cases:
- do not ruin the hit rate for file-head-checkers
- do not lead to thrashing for memory tight systemsHow does it handle
- don't needlessly readahead too much if the file is in cache
It is prevented by the calling scheme.
The adaptive readahead logic will only be called on
- read a non-cached page
So readahead will be started/stopped on demand.
- read a PG_readahead marked page
Since the PG_readahead mark will only be set on fresh new pages in __do_page_cache_readahead(), readahead will automatically cease on cache hit.
Quoted 4 lines
Would the current readahead mechanism benefit from more aggressive start-of-file
readahead?
It will have the same benefits(and drawbacks).
[QUOTE FROM ANOTHER MAIL]
Quoted 2 lines
can we try to incrementally improve the current logic as well as work towards merging your readahead rewrite?
The current readahead is left untouched on purpose.
If I understand it right, its simplicity is a great virtue. And it is hard to improve it without loosing this virtue, or avoid disturbing old users.
Then the new framework provides a ideal testbed for fancy new things. We can do experimental things without calling for complaints(before it is stabilized after one year). And then we might port some proved features to the current logic.
Wu
Re: [PATCH 20/33] readahead: initial method - expected read size
In reply to Wu FengguangQuoted 7 lines · Wu Fengguang
backing_dev_info.ra_expect_bytes is dynamicly updated to be the expected read pages on start-of-file. It allows the initial readahead to be more aggressive and hence efficient.
+void fastcall
readahead_close(struct file *file)
eww, fastcall.
mm/readahead.c static inline void get_readahead_bounds( · line 1571
Quoted 5 lines
mm/readahead.c +5
-0+{ +struct inode *inode = file->f_dentry->d_inode; +struct address_space *mapping = inode->i_mapping; +struct backing_dev_info *bdi = mapping->backing_dev_info; +unsigned long pos = file->f_pos;
f_pos is loff_t.
Re: [PATCH 20/33] readahead: initial method - expected read size
Quoted 10 lines · Andrew Morton
Quoted 7 lines · Wu Fengguang
backing_dev_info.ra_expect_bytes is dynamicly updated to be the expected read pages on start-of-file. It allows the initial readahead to be more aggressive and hence efficient.
+void fastcall
readahead_close(struct file *file)eww, fastcall.
Hehe, it's a tiny function, and calls no further sub-routines
except debugging ones. Still not necessary?
Quoted 7 lines
mm/readahead.c static inline void get_readahead_bounds( · line 1571
Quoted 5 lines
mm/readahead.c +5
-0+{ +struct inode *inode = file->f_dentry->d_inode; +struct address_space *mapping = inode->i_mapping; +struct backing_dev_info *bdi = mapping->backing_dev_info; +unsigned long pos = file->f_pos;
f_posisloff_t.
Just meant to be a little more compact ;)
+ unsigned long pos = file->f_pos; + unsigned long pgrahit = file->f_ra.cache_hits; + unsigned long pgaccess = 1 + pos / PAGE_CACHE_SIZE; + unsigned long pgcached = mapping->nrpages;
+
+ if (!pos) /* pread */
+ return;
+
+ if (pgcached > bdi->ra_pages0) /* excessive reads */
+ return;
Here the f_pos will almost definitely has small values.
+
+ if (pgaccess >= pgcached) {
Fixed by adding a comment to clarify it:
+ unsigned long pos = file->f_pos; /* supposed to be small */
PATCH 23/33 readahead: backward prefetching method
In reply to a message not in the archiveReadahead policy for reading backward.
---
mm/readahead.c | 40 ++++++++++++++++++++++++++++++++++++++++ 1 files changed, 40 insertions(+)
mm/readahead.c +40 -0
@@ -1574,6 +1574,46 @@ initial_readahead(struct address_space * }/* +* Backward prefetching. +* +* No look-ahead and thrashing safety guard: should be unnecessary. +*/ +static int +try_read_backward (struct file_ra_state *ra,pgoff_t begin_index, +unsigned long ra_size,unsigned long ra_max) +{ +pgoff_t end_index; + +/* Are we reading backward? */ +if (begin_index > ra->prev_page) +return 0 ; + +if ((ra->flags &RA_CLASS_MASK ) ==RA_CLASS_BACKWARD && +ra_has_index (ra, ra->prev_page)) { + ra_size +=2 *ra_cache_hit (ra,0 ); + end_index = ra->la_index; + }else { + ra_size += ra_size + ra_size * (readahead_hit_rate -1 ) /2 ; + end_index = ra->prev_page; + } + +if (ra_size > ra_max) + ra_size = ra_max; + +/* Read traces close enough to be covered by the prefetching? */ +if (end_index > begin_index + ra_size) +return 0 ; + + begin_index = end_index - ra_size; + +ra_set_class (ra,RA_CLASS_BACKWARD ); +ra_set_index (ra, begin_index, begin_index); +ra_set_size (ra, ra_size,0 ); + +return 1 ; +} + +/* * ra_min is mainly determined by the size of cache memory. Reasonable? * * Table of concrete numbers for 4KB page size:
--
Re: [PATCH 23/33] readahead: backward prefetching method
Quoted 1 line · Wu Fengguang
Readahead policy for reading backward.
Just curious, who actually does this? I noticed you submitted patches to do profiling of actual read loads, so this must be based on data you've seen. Could you include a comment in the actual code relating to the loads that it affects?
thanks
NATE
Re: [PATCH 23/33] readahead: backward prefetching method
Quoted 4 lines · Nate Diller
Quoted 1 line · Wu Fengguang
Readahead policy for reading backward.
Just curious, who actually does this? I noticed you submitted patches
Nastran does this, and probably other FEA codes. IIRC, iozone will measure this too - it is very important to some people in certain scientific arenas.
cheers.
Signature · 1 line
Nathan
Re: [PATCH 23/33] readahead: backward prefetching method
Quoted 9 lines · Nathan Scott
Quoted 4 lines · Nate Diller
Quoted 1 line · Wu Fengguang
Readahead policy for reading backward.
Just curious, who actually does this? I noticed you submitted patches
Nastran does this, and probably other FEA codes. IIRC, iozone will measure this too - it is very important to some people in certain scientific arenas.
Thanks.
It makes sense to have a list of use cases for the less-common-but-still-important access patterns.
Cheers,
Wu
PATCH 24/33 readahead: seeking reads method
In reply to a message not in the archiveReadahead policy on read after seeking.
It tries to detect sequences like:
seek(), 5*read(); seek(), 6*read(); seek(), 4*read(); ...
---
mm/readahead.c | 43 +++++++++++++++++++++++++++++++++++++++++++ 1 files changed, 43 insertions(+)
mm/readahead.c +43 -0
@@ -1614,6 +1614,49 @@ try_read_backward(struct file_ra_state * }/* +* If there is a previous sequential read, it is likely to be another +* sequential read at the new position. +* +* i.e. detect the following sequences: +* seek(), 5*read(); seek(), 6*read(); seek(), 4*read(); ... +* +* Databases are known to have this seek-and-read-N-pages pattern. +*/ +static int +try_readahead_on_seek (struct file_ra_state *ra,pgoff_t index, +unsigned long ra_size,unsigned long ra_max) +{ +unsigned long hit0 =ra_cache_hit (ra,0 ); +unsigned long hit1 =ra_cache_hit (ra,1 ) + hit0; +unsigned long hit2 =ra_cache_hit (ra,2 ); +unsigned long hit3 =ra_cache_hit (ra,3 ); + +/* There's a previous read-ahead request? */ +if (!ra_has_index (ra, ra->prev_page)) +return 0 ; + +/* The previous read-ahead sequences have similiar sizes? */ +if (!(ra_size < hit1 && hit1 > hit2 /2 && + hit2 > hit3 /2 && + hit3 > hit1 /2 )) +return 0 ; + + hit1 =max (hit1, hit2); + +/* Follow the same prefetching direction. */ +if ((ra->flags &RA_CLASS_MASK ) ==RA_CLASS_BACKWARD ) + index = ((index > hit1 - ra_size) ? index - hit1 + ra_size :0 ); + + ra_size =min (hit1, ra_max); + +ra_set_class (ra,RA_CLASS_SEEK ); +ra_set_index (ra, index, index); +ra_set_size (ra, ra_size,0 ); + +return 1 ; +} + +/* * ra_min is mainly determined by the size of cache memory. Reasonable? * * Table of concrete numbers for 4KB page size:
--
PATCH 25/33 readahead: thrashing recovery method
In reply to a message not in the archiveReadahead policy after thrashing.
It tries to recover gracefully from the thrashing.
---
mm/readahead.c | 42 ++++++++++++++++++++++++++++++++++++++++++ 1 files changed, 42 insertions(+)
mm/readahead.c +42 -0
@@ -1657,6 +1657,48 @@ try_readahead_on_seek(struct file_ra_sta }/* +* Readahead thrashing recovery. +*/ +static unsigned long +thrashing_recovery_readahead (struct address_space *mapping, +struct file *filp,struct file_ra_state *ra, +pgoff_t index,unsigned long ra_max) +{ +unsigned long ra_size; + +if (find_page (mapping, index -1 )) +ra_account (ra,RA_EVENT_READAHEAD_MUTILATE , + ra->readahead_index - index); +ra_account (ra,RA_EVENT_READAHEAD_THRASHING , + ra->readahead_index - index); + +/* +* Some thrashing occur in (ra_index, la_index], in which case the +* old read-ahead chunk is lost soon after the new one is allocated. +* Ensure that we recover all needed pages in the old chunk. +*/ +if (index < ra->ra_index) + ra_size = ra->ra_index - index; +else { +/* After thrashing, we know the exact thrashing-threshold. */ + ra_size =ra_cache_hit (ra,0 ); +update_ra_thrash_bytes (mapping->backing_dev_info, ra_size); + +/* And we'd better be a bit conservative. */ + ra_size = ra_size *3 /4 ; + } + +if (ra_size > ra_max) + ra_size = ra_max; + +ra_set_class (ra,RA_CLASS_THRASHING ); +ra_set_index (ra, index, index); +ra_set_size (ra, ra_size, ra_size /LOOKAHEAD_RATIO ); + +return ra_dispatch (ra, mapping, filp); +} + +/* * ra_min is mainly determined by the size of cache memory. Reasonable? * * Table of concrete numbers for 4KB page size:
--
PATCH 26/33 readahead: call scheme
In reply to a message not in the archiveThe read-ahead logic is called when the reading hits
- a look-ahead mark;
- a non-present page.
ra.prev_page should be properly setup on entrance, and readahead_cache_hit() should be called on every page reference to maintain the cache_hits counter.
This call scheme achieves the following goals:
- makes all stateful/stateless methods happy;
- eliminates the cache hit problem naturally;
- lives in harmony with application managed read-aheads via fadvise/madvise.
---
include/linux/mm.h | 6 ++ mm/filemap.c | 51 ++++++++++++++++- mm/readahead.c | 152 +++++++++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 205 insertions(+), 4 deletions(-)
include/linux/mm.h +6 -0
@@ -1033,6 +1033,12 @@ void handle_ra_miss(struct address_space struct file_ra_state *ra, pgoff_t offset);unsigned long max_sane_readahead (unsigned long nr); void fastcall readahead_close(struct file *file); +unsigned long +page_cache_readahead_adaptive (struct address_space *mapping, +struct file_ra_state *ra,struct file *filp, +struct page *prev_page,struct page *page, +pgoff_t first_index,pgoff_t index,pgoff_t last_index); +void fastcall readahead_cache_hit(struct file_ra_state *ra, struct page *page);#ifdef CONFIG_ADAPTIVE_READAHEAD extern int readahead_ratio;
mm/filemap.c +47 -4
110 lines not on this page · raw message
mm/readahead.c +152 -0
158 lines not on this page · raw message
--
PATCH 27/33 readahead: laptop mode
In reply to a message not in the archiveWhen the laptop drive is spinned down, defer look-ahead to spin up time.
The implementation employs a poll based method, for performance is not a concern in this code path. The poll interval is 64KB, which should be small enough for movies/musics. The user space application is responsible for proper caching to hide the spin-up-and-read delay.
------------------------------------------------------------------------
For crazy laptop users who prefer aggressive read-ahead, here is the way:
# echo 1000 > /proc/sys/vm/readahead_ratio # blockdev --setra 524280 /dev/hda # this is the max possible value
Notes:
- It is still an untested feature.
- It is safer to use blockdev+fadvise to increase ra-max for a single file, which needs patching your movie player.
- Be sure to restore them to sane values in normal operations!
---
include/linux/writeback.h | 6 ++++++ mm/page-writeback.c | 2 +- mm/readahead.c | 30 ++++++++++++++++++++++++++++++ 3 files changed, 37 insertions(+), 1 deletion(-)
include/linux/writeback.h +6 -0
@@ -86,6 +86,12 @@ void laptop_io_completion(void);void laptop_sync_completion (void );void throttle_vm_writeout (void ); +extern struct timer_list laptop_mode_wb_timer; +static inline int laptop_spinned_down (void ) +{ +return !timer_pending (&laptop_mode_wb_timer); +} +/* These are exported to sysctl. */ extern int dirty_background_ratio;extern int vm_dirty_ratio;
mm/page-writeback.c +1 -1
@@ -389,7 +389,7 @@ static void wb_timer_fn(unsigned long unstatic void laptop_timer_fn (unsigned long unused); static DEFINE_TIMER(wb_timer, wb_timer_fn, 0, 0); -static DEFINE_TIMER(laptop_mode_wb_timer, laptop_timer_fn, 0, 0); +DEFINE_TIMER (laptop_mode_wb_timer, laptop_timer_fn,0 ,0 );/* * Periodic writeback of "old" data.
mm/readahead.c +30 -0
@@ -817,6 +817,31 @@ out: }/* +* Set a new look-ahead mark at @new_index. +* Return 0 if the new mark is successfully set. +*/ +static inline int renew_lookahead (struct address_space *mapping, +struct file_ra_state *ra, +pgoff_t index,pgoff_t new_index) +{ +struct page *page; + +if (index == ra->lookahead_index && + new_index >= ra->readahead_index) +return 1 ; + + page =find_page (mapping, new_index); +if (!page) +return 1 ; + +__SetPageReadahead (page); +if (ra->lookahead_index == index) + ra->lookahead_index = new_index; + +return 0 ; +} + +/* * Update `backing_dev_info.ra_thrash_bytes' to be a _biased_ average of * read-ahead sizes. Which makes it an a-bit-risky(*) estimation of the * _minimal_ read-ahead thrashing threshold on the device.
@@ -1760,6 +1785,11 @@ page_cache_readahead_adaptive(struct add end_index - index);return 0 ; } +if (laptop_mode &&laptop_spinned_down ()) { +if (!renew_lookahead (mapping, ra, index, + index +LAPTOP_POLL_INTERVAL )) +return 0 ; + } }if (page)
--
Re: [PATCH 27/33] readahead: laptop mode
Quoted 18 lines · Wu Fengguang
/*
+ * Set a new look-ahead mark at @new_index.
+ * Return 0 if the new mark is successfully set.
+ */
+static inline int renew_lookahead(structaddress_space*mapping,
+ structfile_ra_state*ra,
+pgoff_tindex,pgoff_tnew_index)
+{
+ struct page *page;
+
+ if (index ==ra->lookahead_index&&
+new_index>=ra->readahead_index)
+ return 1;
+
+ page =find_page(mapping, new_index);
+ if (!page)
+ return 1;
Quoted 8 lines
+
+__SetPageReadahead(page);
+ if (ra->lookahead_index== index)
+ra->lookahead_index=new_index;
+
+ return 0;
+}
+
This is a pagecache page and other CPUs can look it up and play with it. The __SetPageReadahead() is quite wrong here.
And we don't have a reference on this page, so this code appears to be racy.
You could fix that by taking and dropping a ref on the page, but it'd be quicker to take tree_lock and do the SetPageReadahead() while holding it.
This function is too large to inline.
PATCH 28/33 readahead: loop case
In reply to a message not in the archiveDisable look-ahead for loop file.
Loopback files normally contain filesystems, in which case there are already proper look-aheads in the upper layer, more look-aheads on the loopback file only ruins the read-ahead hit rate.
---
I'd like to thank Tero Grundstr?m for uncovering the loopback problem.
drivers/block/loop.c | 6 ++++++ 1 files changed, 6 insertions(+)
drivers/block/loop.c +6 -0
@@ -779,6 +779,12 @@ static int loop_set_fd(struct loop_devic mapping = file->f_mapping; inode = mapping->host; +/* +* The upper layer should already do proper look-ahead, +* one more look-ahead here only ruins the cache hit rate. +*/ + file->f_ra.flags |=RA_FLAG_NO_LOOKAHEAD ; +if (!(file->f_mode &FMODE_WRITE )) lo_flags |=LO_FLAGS_READ_ONLY ;
--
PATCH 29/33 readahead: nfsd case
In reply to a message not in the archiveBypass nfsd raparms cache -- the new logic do not rely on it.
--------------------------------
For the case of NFS service, the new read-ahead logic
+ can handle disordered nfsd requests
+ can handle concurrent sequential requests on large files with the help of look-ahead
- will have much ado about the concurrent ones on small files
--------------------------------
Notes about the concurrent nfsd requests issue:
nfsd read requests can be out of order, concurrent and with no ra-state info. They are handled by the context based read-ahead method, which does the job in the following steps:
1. scan in page cache
2. make read-ahead decisions
3. alloc new pages
4. insert new pages to page cache
A single read-ahead chunk in the client side will be dissembled and serviced by many concurrent nfsd in the server side. It is highly possible for two or more of these parallel nfsd instances to be in step 1/2/3 at the same time. Without knowing others working on the same file region, they will issue overlapped read-ahead requests, which lead to many conflicts at step 4.
There's no much luck to eliminate the concurrent problem in general and efficient ways. But experiments show that mount with tcp,rsize=32768 can cut down the overhead a lot.
--------------------------------
Here are the benchmark outputs. The test cases cover
- small/big files
- small/big rsize mount option
- serialized/parallel nfsd processing
`serialized' means running the following command to enforce serialized nfsd requests processing:
# for pid in `pidof nfsd`; do taskset -p 1 $pid; done
8 nfsd; local mount with tcp,rsize=8192
=======================================
SERIALIZED, SMALL FILESreadahead_ratio = 0, ra_max = 128kb (old logic, the ra_max is not quite relevant) 96.51s real 11.32s system 3.27s user 160334+2829 cs diff -r $NFSDIR $NFSDIR2 readahead_ratio = 70, ra_max = 1024kb (new read-ahead logic)
94.88s real 11.53s system 3.20s user 152415+3777 cs diff -r $NFSDIR $NFSDIR2
SERIALIZED, BIG FILESreadahead_ratio = 0, ra_max = 128kb
56.52s real 3.38s system 1.23s user 47930+5256 cs diff $NFSFILE $NFSFILE2 readahead_ratio = 70, ra_max = 1024kb
32.54s real 5.71s system 1.38s user 23851+17007 cs diff $NFSFILE $NFSFILE2
PARALLEL, SMALL FILESreadahead_ratio = 0, ra_max = 128kb
99.87s real 11.41s system 3.15s user 173945+9163 cs diff -r $NFSDIR $NFSDIR2 readahead_ratio = 70, ra_max = 1024kb
100.14s real 12.06s system 3.16s user 170865+13406 cs diff -r $NFSDIR $NFSDIR2
PARALLEL, BIG FILESreadahead_ratio = 0, ra_max = 128kb
63.35s real 5.68s system 1.57s user 82594+48747 cs diff $NFSFILE $NFSFILE2 readahead_ratio = 70, ra_max = 1024kb
33.87s real 10.17s system 1.55s user 72291+100079 cs diff $NFSFILE $NFSFILE2
8 nfsd; local mount with tcp,rsize=32768
========================================
Note that the normal data are now much better, and come close to that of the serialized ones.
PARALLEL/NORMAL
readahead_ratio = 8, ra_max = 1024kb (old logic)
48.36s real 2.22s system 1.51s user 7209+4110 cs diff $NFSFILE $NFSFILE2 readahead_ratio = 70, ra_max = 1024kb (new logic)
30.04s real 2.46s system 1.33s user 5420+2492 cs diff $NFSFILE $NFSFILE2
readahead_ratio = 8, ra_max = 1024kb
92.99s real 10.32s system 3.23s user 145004+1826 cs diff -r $NFSDIR $NFSDIR2 > /dev/null readahead_ratio = 70, ra_max = 1024kb
90.96s real 10.68s system 3.22s user 144414+2520 cs diff -r $NFSDIR $NFSDIR2 > /dev/null
SERIALIZED
readahead_ratio = 8, ra_max = 1024kb
47.58s real 2.10s system 1.27s user 7933+1357 cs diff $NFSFILE $NFSFILE2 readahead_ratio = 70, ra_max = 1024kb
29.46s real 2.41s system 1.38s user 5590+2613 cs diff $NFSFILE $NFSFILE2
readahead_ratio = 8, ra_max = 1024kb
93.02s real 10.67s system 3.25s user 144850+2286 cs diff -r $NFSDIR $NFSDIR2 > /dev/null readahead_ratio = 70, ra_max = 1024kb
91.15s real 11.04s system 3.31s user 144432+2814 cs diff -r $NFSDIR $NFSDIR2 > /dev/null
---
Greg Banks gives a valuable recommend on the test cases, which helps me to get the more complete picture. Thanks!
fs/nfsd/vfs.c | 5 ++++- 1 files changed, 4 insertions(+), 1 deletion(-)
fs/nfsd/vfs.c +4 -1
@@ -829,7 +829,10 @@ nfsd_vfs_read(struct svc_rqst *rqstp, st#endif /* Get readahead parameters */ - ra =nfsd_get_raparms (inode->i_sb->s_dev, inode->i_ino); +if (prefer_adaptive_readahead ()) + ra =NULL ; +else + ra =nfsd_get_raparms (inode->i_sb->s_dev, inode->i_ino);if (ra && ra->p_set) file->f_ra = ra->p_ra;
--
PATCH 30/33 readahead: turn on by default
In reply to a message not in the archiveEnable the adaptive readahead logic by default.
It helps collect more early testers, and is meant to be a -mm only patch.
---
mm/Kconfig | 2 +- 1 files changed, 1 insertion(+), 1 deletion(-)
mm/Kconfig +1 -1
@@ -152,7 +152,7 @@ config MIGRATION # config ADAPTIVE_READAHEAD bool "Adaptive file readahead (EXPERIMENTAL)" - default n + default y depends on EXPERIMENTAL help Readahead is a technique employed by the kernel in an attempt
--
PATCH 31/33 readahead: debug radix tree new functions
In reply to a message not in the archiveDo some sanity checkings on the newly added radix tree code.
---
mm/readahead.c | 24 ++++++++++++++++++++++++ 1 files changed, 24 insertions(+)
mm/readahead.c +24 -0
@@ -63,6 +63,8 @@ enum ra_class {RA_CLASS_COUNT }; +#define DEBUG_READAHEAD_RADIXTREE +/* Read-ahead events to be accounted. */ enum ra_event {RA_EVENT_CACHE_MISS ,/* read cache misses */
@@ -1315,6 +1317,16 @@ static pgoff_t find_segtail(struct addrecond_resched ();read_lock_irq (&mapping->tree_lock); ra_index =radix_tree_scan_hole (&mapping->page_tree, index, max_scan); +#ifdef DEBUG_READAHEAD_RADIXTREE +BUG_ON (!__find_page (mapping, index)); +WARN_ON (ra_index < index); +if (ra_index != index && !__find_page (mapping, ra_index -1 )) +printk (KERN_ERR "radix_tree_scan_hole(index=%lu ra_index=%lu " +"max_scan=%lu nrpages=%lu) fooled!\n" , + index, ra_index, max_scan, mapping->nrpages); +if (ra_index != ~0UL && ra_index - index < max_scan) +WARN_ON (__find_page (mapping, ra_index)); +#endif read_unlock_irq (&mapping->tree_lock);if (ra_index <= index + max_scan)
@@ -1407,6 +1419,13 @@ static unsigned long query_page_cache_seread_lock_irq (&mapping->tree_lock); index =radix_tree_scan_hole_backward (&mapping->page_tree, offset, ra_max); +#ifdef DEBUG_READAHEAD_RADIXTREE +WARN_ON (index > offset); +if (index != offset) +WARN_ON (!__find_page (mapping, index +1 )); +if (index && offset - index < ra_max) +WARN_ON (__find_page (mapping, index)); +#endif read_unlock_irq (&mapping->tree_lock); *remain = offset - index;
@@ -1442,6 +1461,11 @@ static unsigned long query_page_cache_sestruct radix_tree_node *node; node =radix_tree_cache_lookup_parent (&mapping->page_tree, &cache, offset - count,1 ); +#ifdef DEBUG_READAHEAD_RADIXTREE +if (node !=radix_tree_lookup_parent (&mapping->page_tree, + offset - count,1 )) +BUG (); +#endif if (!node)break ; }
--
PATCH 32/33 readahead: debug traces showing accessed file names
In reply to a message not in the archivePrint file names on their first read-ahead, for tracing file access patterns.
---
mm/readahead.c | 14 ++++++++++++++ 1 files changed, 14 insertions(+)
mm/readahead.c +14 -0
@@ -1074,6 +1074,20 @@ static int ra_dispatch(struct file_ra_stra_account (ra,RA_EVENT_IO_CACHE_HIT , ra_size - actual);ra_account (ra,RA_EVENT_READAHEAD , actual); +if (!ra->ra_index && filp->f_dentry->d_inode) { +char *fn; +static char path[1024 ]; +unsigned long size; + + size = (i_size_read (filp->f_dentry->d_inode)+1023 )/1024 ; + fn =d_path (filp->f_dentry, filp->f_vfsmnt, path,1000 ); +if (!IS_ERR (fn)) +ddprintk ("ino %lu is %s size %luK by %s(%d)\n" , + filp->f_dentry->d_inode->i_ino, + fn, size, + current->comm, current->pid); + } + dprintk("readahead-%s(ino=%lu, index=%lu, ra=%lu+%lu-%lu) = %d\n", ra_class_name[ra_class], mapping->host->i_ino, ra->la_index,
--
PATCH 33/33 readahead: debug traces showing read patterns
In reply to a message not in the archivePrint all relavant read requests to help discover the access pattern.
If you are experiencing performance problems, or want to help improve the read-ahead logic, please send me the trace data. Thanks.
- Preparations
# Compile kernel with option CONFIG_DEBUG_READAHEAD mkdir /debug
mount -t debug none /debug
- For each session with distinct access pattern
echo > /debug/readahead # reset the counters
# echo > /var/log/kern.log # you may want to backup it first echo 8 > /debug/readahead/debug_level # show verbose printk traces # do one benchmark/task echo 0 > /debug/readahead/debug_level # revert to normal value cp /debug/readahead/events readahead-events-`date +'%F_%R'` bzip2 -c /var/log/kern.log > kern.log-`date +'%F_%R'`.bz2
---
mm/filemap.c | 23 ++++++++++++++++++++++- 1 files changed, 22 insertions(+), 1 deletion(-)
mm/filemap.c +22 -1
@@ -45,6 +45,12 @@ static ssize_t generic_file_direct_IO(int rw, struct kiocb *iocb, const struct iovec *iov, loff_t offset, unsigned long nr_segs); +#ifdef CONFIG_DEBUG_READAHEAD +extern u32 debug_level; +#else +#define debug_level 0 +#endif /* CONFIG_DEBUG_READAHEAD */ +/* * Shared mappings implemented 30.11.1994. It's not fully working yet, * though.
@@ -829,6 +835,10 @@ void do_generic_mapping_read(struct addrif (!isize) goto out; +if (debug_level >=5 ) +printk (KERN_DEBUG "read-file(ino=%lu, req=%lu+%lu)\n" , + inode->i_ino, index, last_index - index); + end_index = (isize -1 ) >>PAGE_CACHE_SHIFT ;for (;;) {struct page *page;
@@ -883,6 +893,11 @@ find_page:if (prefer_adaptive_readahead ())readahead_cache_hit (&ra, page); +if (debug_level >=7 ) +printk (KERN_DEBUG "read-page(ino=%lu, idx=%lu, io=%s)\n" , + inode->i_ino, index, +PageUptodate (page) ?"hit" :"miss" ); +if (!PageUptodate (page)) goto page_not_up_to_date; page_ok:
@@ -1334,7 +1349,6 @@ retry_all:if (!prefer_adaptive_readahead () &&VM_SequentialReadHint (area))page_cache_readahead (mapping, ra, file, pgoff,1 ); -/* * Do we have something in the page cache already? */
@@ -1397,6 +1411,13 @@ retry_find:if (prefer_adaptive_readahead ())readahead_cache_hit (ra, page); +if (debug_level >=6 ) +printk (KERN_DEBUG "read-mmap(ino=%lu, idx=%lu, hint=%s, io=%s)\n" , + inode->i_ino, pgoff, +VM_RandomReadHint (area) ?"random" : + (VM_SequentialReadHint (area) ?"sequential" :"none" ), +PageUptodate (page) ?"hit" :"miss" ); +/* * Ok, found a page in the page cache, now we need to check * that it's up-to-date.
--
A message that is not in the archive (sent off-list or not yet received): [email protected]
Quoted 18 lines · Wu Fengguang
plain text document attachment (readahead-page-flag-PG_readahead.patch)
An new page flagPG_readaheadis introduced as a look-ahead mark, which reminds the caller to give the adaptive read-ahead logic a chance to do read-ahead ahead of time for I/O pipelining.It roughly corresponds to `ahead_start' of the stock read-ahead logic.
Signed-off-by Wu Fengguang <[email protected]>---
include/linux/page-flags.h | 5 +++++ mm/page_alloc.c | 2 +- 2 files changed, 6 insertions(+), 1 deletion(-)
include/linux/page-flags.h line 93
Quoted 5 lines
include/linux/page-flags.h +1
-0@@ -89,6 +89,7 @@#define PG_reclaim 17/* To be reclaimed asap */ #define PG_nosave_free 18/* Free, should not be written */ #define PG_buddy 19/* Page is free, on buddy lists */ +#define PG_readahead 20/* Reminder to do readahead */
Page flags are gouped by four, 20 would start a new set. Also in my tree (git from a few days ago), 20 is taken by PG_unchached. What code is this patch-set against?
Quoted 16 lines · Peter Zijlstra
Quoted 15 lines · Wu Fengguang
plain text document attachment (readahead-page-flag-PG_readahead.patch)
An new page flagPG_readaheadis introduced as a look-ahead mark, which reminds the caller to give the adaptive read-ahead logic a chance to do read-ahead ahead of time for I/O pipelining.It roughly corresponds to `ahead_start' of the stock read-ahead logic.
Signed-off-by Wu Fengguang <[email protected]>---
include/linux/page-flags.h | 5 +++++ mm/page_alloc.c | 2 +- 2 files changed, 6 insertions(+), 1 deletion(-)
Quoted 11 lines
include/linux/page-flags.h line 93
Quoted 8 lines
include/linux/page-flags.h +1
-0@@ -89,6 +89,7 @@#define PG_reclaim 17/* To be reclaimed asap */ #define PG_nosave_free 18/* Free, should not be written */ #define PG_buddy 19/* Page is free, on buddy lists */ +#define PG_readahead 20/* Reminder to do readahead */ Page flags are gouped by four, 20 would start a new set. Also in my tree (git from a few days ago), 20 is taken by
PG_unchached.
Thanks, grouped and renumbered it as 21.
Quoted 1 line
What code is this patch-set against?
It's against the latest -mm tree: linux-2.6.17-rc4-mm3.
Wu
---
Subject: readahead: page flag PG_readahead
An new page flag PG_readahead is introduced as a look-ahead mark, which reminds the caller to give the adaptive read-ahead logic a chance to do read-ahead ahead of time for I/O pipelining.
It roughly corresponds to `ahead_start' of the stock read-ahead logic.
--- include/linux/page-flags.h | 5 +++++ mm/page_alloc.c | 2 +- 2 files changed, 6 insertions(+), 1 deletion(-)
include/linux/page-flags.h +6 -0
@@ -90,6 +90,8 @@#define PG_nosave_free 18/* Free, should not be written */ #define PG_buddy 19/* Page is free, on buddy lists */ +#define PG_readahead 21/* Reminder to do readahead */ +#if (BITS_PER_LONG >32 )/*
@@ -372,6 +374,10 @@ extern void __mod_page_state_offset(unsi#define SetPageUncached (page) set_bit(PG_uncached, &(page)->flags)#define ClearPageUncached (page) clear_bit(PG_uncached, &(page)->flags) +#define PageReadahead (page) test_bit(PG_readahead, &(page)->flags) +#define __SetPageReadahead (page) __set_bit(PG_readahead, &(page)->flags) +#define TestClearPageReadahead (page) test_and_clear_bit(PG_readahead, &(page)->flags) +struct page ;/* forward declaration */ int test_clear_page_dirty (struct page *page);
mm/page_alloc.c +1 -1
@@ -564,7 +564,7 @@ static int prep_new_page(struct page *paif (PageReserved (page))return 1 ; - page->flags &= ~(1 << PG_uptodate |1 << PG_error | + page->flags &= ~(1 << PG_uptodate |1 << PG_error |1 << PG_readahead |1 << PG_referenced |1 << PG_arch_1 |1 << PG_checked |1 << PG_mappedtodisk);set_page_private (page,0 );
A message that is not in the archive (sent off-list or not yet received): [email protected]
Quoted 16 lines · Wu Fengguang
Quoted 14 lines · Peter Zijlstra
include/linux/page-flags.h line 93
Quoted 8 lines · Wu Fengguang
include/linux/page-flags.h +1
-0@@ -89,6 +89,7 @@#define PG_reclaim 17/* To be reclaimed asap */ #define PG_nosave_free 18/* Free, should not be written */ #define PG_buddy 19/* Page is free, on buddy lists */ +#define PG_readahead 20/* Reminder to do readahead */ Page flags are gouped by four, 20 would start a new set. Also in my tree (git from a few days ago), 20 is taken by
PG_unchached.
Quoted 5 lines
Thanks, grouped and renumbered it as 21.
Quoted 1 line
What code is this patch-set against?
It's against the latest -mm tree: linux-2.6.17-rc4-mm3.
Ah, now I see, -mm has got a trick up its sleeve for PG_uncached.
20 would indeed be the correct number for -mm. Then my sole comment would be the grouping, which is a stylish nit really.
Sorry for the confusion.
Peter
A message that is not in the archive (sent off-list or not yet received): [email protected]
Re: [PATCH 17/33] readahead: context based method
Quoted 27 lines · Wu Fengguang
(quoted diff) +27
-0+#define PAGE_REFCNT_0 0 +#define PAGE_REFCNT_1 (1 << PG_referenced) +#define PAGE_REFCNT_2 (1 << PG_active) +#define PAGE_REFCNT_3 ((1 << PG_active) | (1 << PG_referenced)) +#define PAGE_REFCNT_MASK PAGE_REFCNT_3 + +/* + * STATUS REFERENCE COUNT + * __ 0 + * _R PAGE_REFCNT_1 + * A_ PAGE_REFCNT_2 + * AR PAGE_REFCNT_3 + * + * A/R: Active / Referenced + */ +static inline unsigned long page_refcnt(struct page *page) +{ + return page->flags & PAGE_REFCNT_MASK; +} + +/* + * STATUS REFERENCE COUNT TYPE + * __ 0 fresh + * _R PAGE_REFCNT_1 stale + * A_ PAGE_REFCNT_2 disturbed once + * AR PAGE_REFCNT_3 disturbed twice + *
Review
Quoted 10 lines
(quoted diff) +10
-0+ * A/R: Active / Referenced + */ +static inline unsigned long cold_page_refcnt(struct page *page) +{ + if (!page || PageActive(page)) + return 0; + + return page_refcnt(page); +} +
Why all of this if all you're ever going to use is cold_page_refcnt. What about something like this:
static inline int cold_page_referenced(struct page *page)
{
if (!page || PageActive(page))
return 0;
return !!PageReferenced(page);
}Quoted 16 lines
(quoted diff) +16
-0+ +/* + * Count/estimate cache hits in range [first_index, last_index]. + * The estimation is simple and optimistic. + */ +static int count_cache_hit(struct address_space *mapping, + pgoff_t first_index, pgoff_t last_index) +{ + struct page *page; + int size = last_index - first_index + 1; + int count = 0; + int i; + + cond_resched(); + read_lock_irq(&mapping->tree_lock); +
Review
Quoted 10 lines
(quoted diff) +10
-0+ /* + * The first page may well is chunk head and has been accessed, + * so it is index 0 that makes the estimation optimistic. This + * behavior guarantees a readahead when (size < ra_max) and + * (readahead_hit_rate >= 16). + */ + for (i = 0; i < 16;) { + page = __find_page(mapping, first_index + + size * ((i++ * 29) & 15) / 16); + if (cold_page_refcnt(page) >= PAGE_REFCNT_1 && ++count >= 2)
cold_page_referenced(page) && ++count >= 2
Quoted 7 lines
(quoted diff) +7
-0+ break; + } + + read_unlock_irq(&mapping->tree_lock); + + return size * count / i; +}
Re: [PATCH 17/33] readahead: context based method
Quoted 33 lines · Peter Zijlstra
Quoted 31 lines · Wu Fengguang
(quoted diff) +31
-0+#define PAGE_REFCNT_0 0 +#define PAGE_REFCNT_1 (1 << PG_referenced) +#define PAGE_REFCNT_2 (1 << PG_active) +#define PAGE_REFCNT_3 ((1 << PG_active) | (1 << PG_referenced)) +#define PAGE_REFCNT_MASK PAGE_REFCNT_3 + +/* + * STATUS REFERENCE COUNT + * __ 0 + * _R PAGE_REFCNT_1 + * A_ PAGE_REFCNT_2 + * AR PAGE_REFCNT_3 + * + * A/R: Active / Referenced + */ +static inline unsigned long page_refcnt(struct page *page) +{ + return page->flags & PAGE_REFCNT_MASK; +} + +/* + * STATUS REFERENCE COUNT TYPE + * __ 0 fresh + * _R PAGE_REFCNT_1 stale + * A_ PAGE_REFCNT_2 disturbed once + * AR PAGE_REFCNT_3 disturbed twice + * + * A/R: Active / Referenced + */ +static inline unsigned long cold_page_refcnt(struct page *page) +{
Quoted 8 lines
Review
Quoted 6 lines
(quoted diff) +6
-0+ if (!page || PageActive(page)) + return 0; + + return page_refcnt(page); +} +Why all of this if all you're ever going to use is
cold_page_refcnt.
Well, the two functions have a long history...
There has been a PG_activate which makes the two functions quite different. It was later removed for fear of the behavior changes it introduced. However, there's still possibility that someone reintroduce similar flags in the future :)
Quoted 8 lines
What about something like this:
static inline int
cold_page_referenced(struct page *page){ if (!page || PageActive(page)) return 0; return !!PageReferenced(page); }
Ah, here's another theory: the algorithm uses reference count conceptually, so it may be better to retain the current form.
Thanks,
Wu
A message that is not in the archive (sent off-list or not yet received): [email protected]
Re: [PATCH 17/33] readahead: context based method
Quoted 59 lines · Wu Fengguang
Quoted 33 lines · Peter Zijlstra
Quoted 31 lines · Wu Fengguang
(quoted diff) +31
-0+#define PAGE_REFCNT_0 0 +#define PAGE_REFCNT_1 (1 << PG_referenced) +#define PAGE_REFCNT_2 (1 << PG_active) +#define PAGE_REFCNT_3 ((1 << PG_active) | (1 << PG_referenced)) +#define PAGE_REFCNT_MASK PAGE_REFCNT_3 + +/* + * STATUS REFERENCE COUNT + * __ 0 + * _R PAGE_REFCNT_1 + * A_ PAGE_REFCNT_2 + * AR PAGE_REFCNT_3 + * + * A/R: Active / Referenced + */ +static inline unsigned long page_refcnt(struct page *page) +{ + return page->flags & PAGE_REFCNT_MASK; +} + +/* + * STATUS REFERENCE COUNT TYPE + * __ 0 fresh + * _R PAGE_REFCNT_1 stale + * A_ PAGE_REFCNT_2 disturbed once + * AR PAGE_REFCNT_3 disturbed twice + * + * A/R: Active / Referenced + */ +static inline unsigned long cold_page_refcnt(struct page *page) +{Quoted 8 lines
Review
Quoted 6 lines
(quoted diff) +6
-0+ if (!page || PageActive(page)) + return 0; + + return page_refcnt(page); +} +Why all of this if all you're ever going to use is
cold_page_refcnt.Well, the two functions have a long history...
There has been a
PG_activatewhich makes the two functions quite different. It was later removed for fear of the behavior changes it introduced. However, there's still possibility that someone reintroduce similar flags in the future :)Quoted 8 lines
What about something like this:
static inline int
cold_page_referenced(struct page *page){ if (!page || PageActive(page)) return 0; return !!PageReferenced(page); }
Quoted 2 lines
Ah, here's another theory: the algorithm uses reference count conceptually, so it may be better to retain the current form.
Reference count of what exactly, if you were to say of the page, I'd have expected only the first function, page_refcnt().
What I don't exactly understand is why you specialise to the inactive list. Why do you need that?
The reason I'm asking is that when I merge this with my page replacement work, I need to find a generalised concept. cold_page_refcnt() would become to mean something like: number of references for those pages that are direct reclaim candidates. And honestly, that doesn't make a lot of sense.
If you could explain the concept behind this, I'd be grateful.
Peter
Re: [PATCH 17/33] readahead: context based method
Quoted 69 lines · Peter Zijlstra
Quoted 59 lines · Wu Fengguang
Quoted 33 lines · Peter Zijlstra
Quoted 31 lines · Wu Fengguang
(quoted diff) +31
-0+#define PAGE_REFCNT_0 0 +#define PAGE_REFCNT_1 (1 << PG_referenced) +#define PAGE_REFCNT_2 (1 << PG_active) +#define PAGE_REFCNT_3 ((1 << PG_active) | (1 << PG_referenced)) +#define PAGE_REFCNT_MASK PAGE_REFCNT_3 + +/* + * STATUS REFERENCE COUNT + * __ 0 + * _R PAGE_REFCNT_1 + * A_ PAGE_REFCNT_2 + * AR PAGE_REFCNT_3 + * + * A/R: Active / Referenced + */ +static inline unsigned long page_refcnt(struct page *page) +{ + return page->flags & PAGE_REFCNT_MASK; +} + +/* + * STATUS REFERENCE COUNT TYPE + * __ 0 fresh + * _R PAGE_REFCNT_1 stale + * A_ PAGE_REFCNT_2 disturbed once + * AR PAGE_REFCNT_3 disturbed twice + * + * A/R: Active / Referenced + */ +static inline unsigned long cold_page_refcnt(struct page *page) +{Quoted 8 lines
Review
Quoted 6 lines
(quoted diff) +6
-0+ if (!page || PageActive(page)) + return 0; + + return page_refcnt(page); +} +Why all of this if all you're ever going to use is
cold_page_refcnt.Well, the two functions have a long history...
There has been a
PG_activatewhich makes the two functions quite different. It was later removed for fear of the behavior changes it introduced. However, there's still possibility that someone reintroduce similar flags in the future :)Quoted 8 lines
What about something like this:
static inline int
cold_page_referenced(struct page *page){ if (!page || PageActive(page)) return 0; return !!PageReferenced(page); }Quoted 2 lines
Ah, here's another theory: the algorithm uses reference count conceptually, so it may be better to retain the current form.
Reference count of what exactly, if you were to say of the page, I'd have expected only the first function,
page_refcnt().What I don't exactly understand is why you specialise to the inactive list. Why do you need that?
Quoted 7 lines
The reason I'm asking is that when I merge this with my page replacement work, I need to find a generalised concept.
cold_page_refcnt()would become to mean something like: number of references for those pages that are direct reclaim candidates. And honestly, that doesn't make a lot of sense.If you could explain the concept behind this, I'd be grateful.
Good question, and sorry for mentioning this...
There are some background info here:
[DISTURBS] section of
http://marc.theaimsgroup.com/?l=linux-kernel&m=112678976802381&w=2
[DELAYED ACTIVATION] section of
http://marc.theaimsgroup.com/?l=linux-kernel&m=112679176611006&w=2
It involves a tricky situation where there are two sequential readers that come close enough, so that the follower retouched the pages visited by the leader:
chunk 1 chunk 2 chunk 3
========== =============------- --------------------
follower ^ leader ^
It is all ok if the revisited pages still stay in the inactive list, these pages will act as measurement of len(inactive list)/speed(leader). But if the revisited pages(marked by '=') are sent to active list immediately, the measurement will no longer be as accurate. The trace is 'disturbed'. In this case, using page_refcnt() can be aggressive and unsafe from thrashing, while cold_page_refcnt() can be conservative.
So either one of page_refcnt()/cold_page_refcnt() should be ok, as long as we know the consequence of this situation. After all, it is really uncommon to see much invocation of the context based method, and even rare for this kind of situation to happen.
Regards,
Wu
A message that is not in the archive (sent off-list or not yet received): [email protected]
Re: [PATCH 28/33] readahead: loop case
If the loopback files is bigger than the memory size, it may cause miss again and may better to turn on the read ahead?
Regards,
Limin
Quoted 36 lines · Wu Fengguang
Disable look-ahead for loop file.
Loopback files normally contain filesystems, in which case there are already proper look-aheads in the upper layer, more look-aheads on the loopback file only ruins the read-ahead hit rate.
Signed-off-by Wu Fengguang <[email protected]>---
I'd like to thank Tero Grundstr?m for uncovering the loopback problem.
drivers/block/loop.c | 6 ++++++ 1 files changed, 6 insertions(+)drivers/block/loop.c +6
-2@@ -779,6 +779,12 @@ static int loop_set_fd(struct loop_devic mapping = file->f_mapping; inode = mapping->host; +/* +* The upper layer should already do proper look-ahead, +* one more look-ahead here only ruins the cache hit rate. +*/ + file->f_ra.flags |=RA_FLAG_NO_LOOKAHEAD ; +if (!(file->f_mode &FMODE_WRITE )) lo_flags |=LO_FLAGS_READ_ONLY ; -- -To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH 28/33] readahead: loop case
Quoted 4 lines · Limin Wang
If the loopback files is bigger than the memory size, it may cause miss again and may better to turn on the read ahead?
The readahead is always on, it's only disabling lookahead :-)
Quoted 5 lines
Quoted 5 lines
Disable look-ahead for loop file.
Loopback files normally contain filesystems, in which case there are already proper look-aheads in the upper layer, more look-aheads on the loopback file only ruins the read-ahead hit rate.