context readahead for concurrent IO take 2

Introduce page cache context based readahead algorithm. This is to better support concurrent read streams in general.

/*
+ * Count contiguously cached pages from @offset-1 to @offset-@max,
+ * this count is a conservative estimation of
+ * - length of the sequential read sequence, or
+ * - thrashing threshold in memory tight systems
+ */

mm/readahead.c +2 -0

+static pgoff_t count_history_pages(struct address_space *mapping,
+				   struct file_ra_state *ra,

Quoted 11 lines · Wu Fengguang

Introduce page cache context based readahead algorithm. This is to better support concurrent read streams in general.

/*
+ * Count contiguously cached pages from @offset-1 to @offset-@max,
+ * this count is a conservative estimation of
+ * - length of the sequential read sequence, or
+ * - thrashing threshold in memory tight systems
+ */

mm/readahead.c +2 -0

+static pgoff_t count_history_pages(struct address_space *mapping,
+				   struct file_ra_state *ra,

mm/readahead.c static unsigned long get_next_ra_size(st · line 349

Quoted 10 lines

mm/readahead.c +10 -0

+				   pgoff_t offset, unsigned long max)
+{
+	pgoff_t head;
+
+	rcu_read_lock();
+	head = radix_tree_prev_hole(&mapping->page_tree, offset - 1, max);
+	rcu_read_unlock();
+
+	return offset - 1 - head;
+}

Very elegant method! I suspect this will work far better than adding various increasingly more complex heuristics.

Emphatically-Acked-by Ingo Molnar <[email protected]>

lib/radix-tree.c +5 -0

+unsigned long radix_tree_prev_hole(struct radix_tree_root *root,
+				   unsigned long index, unsigned long max_scan)
+{
+	unsigned long i;
+

Quoted 9 lines · On Sun, 12 Apr 2009 15:19:51 +0800 Wu Fengguang <[email protected]> wrote:

lib/radix-tree.c +9 -0

+unsigned long radix_tree_prev_hole(struct radix_tree_root *root,
+				   unsigned long index, unsigned long max_scan)
+{
+	unsigned long i;
+
+	for (i = 0; i < max_scan; i++) {
+		if (!radix_tree_lookup(root, index))
+			break;
+		index--;

lib/radix-tree.c unsigned long radix_tree_next_hole(struc · line 703

Quoted 6 lines

lib/radix-tree.c +6 -0

+		if (index == LONG_MAX)
+			break;
+	}
+
+	return index;
+}

argh. This is about as inefficient as we could possibly make it :(

Really, this function should dive into radix-tree internals and walk individual radix_tree_node.slots[] arrays. And heck, it can peek at radix_tree_node.count and _bypass_ entire nodes, too.

Quoted 8 lines · Wu Fengguang

The context readahead algorithm guarantees to discover the sequentialness no matter how the streams are interleaved. For the above example, it will start sequential readahead since page 2 and 1002.

The trick is to poke for page @offset-1 in the page cache when it has no other clues on the sequentialness of request @offset: if the current requenst belongs to a sequential stream, that stream must have accessed page @offset-1 recently,

Really? The page could be just randomly cached from some previous IO, right? I don't think you can detect that right? [maybe you could play some games with the LRU list, but that would be likely not O(1)]

I wonder if this could cause the prefetcher to "switch gears" suddenly when it first walks a long stretch of non cached file data and then suddenly hits a cached page.

One possible way around this would be to add a concept of "page generation". e.g. use a few bits of page flags. keep a global generation count that increases slowly (let's say every few seconds) Mark the page with the current generation count when the prefetcher takes it. When doing your algorithm check the count first and only use pages with a recent count.

Not sure if it's a real problem or not.

I'll list some possible situations. I guess you are referring to (2.3)?

2.3) readahead cache hits: rare case and the impact is temporary

The page at @offset-1 does get referenced by this stream, but it's created by someone else at some distant time ago. The page at @offset-1 may be lifted to active lru by this second reference, or too late and get reclaimed - by the time we reference page @offset.

Normally its a range of cached pages. We are a) either walking inside the range and enjoying the cache hits, b) or we walk out of it and restart readahead by ourself, c) or the range of cached pages get reclaimed while we are walking on them, and hence cannot find page @offset-1.

Obviously (c) is rare and temporary and is the main cause of (2.3). As soon as we goto the next page at @offset+1, we'll its 'previous' page at @offset to be cached(it is created by us!). So the context readahead starts working again - it's merely delayed by one page :-)

Quoted 1 line

I'll list some possible situations. I guess you are referring to (2.3)?

Yep. Thanks for the detailed analysis.

Quoted 12 lines

2.3) readahead cache hits: rare case and the impact is temporary

The page at @offset-1 does get referenced by this stream, but it's created by someone else at some distant time ago. The page at @offset-1 may be lifted to active lru by this second reference, or too late and get reclaimed - by the time we reference page @offset.

Normally its a range of cached pages. We are a) either walking inside the range and enjoying the cache hits, b) or we walk out of it and restart readahead by ourself, c) or the range of cached pages get reclaimed while we are walking on them, and hence cannot find page @offset-1.

Quoted 4 lines

Obviously (c) is rare and temporary and is the main cause of (2.3). As soon as we goto the next page at @offset+1, we'll its 'previous' page at @offset to be cached(it is created by us!). So the context readahead starts working again - it's merely delayed by one page :-)

Thanks. The question is how much performance impact this has on the stream that is readaheaded. I guess it would be only a smaller "hickup", with some luck hidden by the block level RA?

The other question would be if it could cause the readahead code to do a lot of unnecessary work, but your answer seems to be "no". Fine.

I think the concept is sound.

Quoted 3 lines · Andi Kleen

Quoted 1 line

I'll list some possible situations. I guess you are referring to (2.3)?

Yep. Thanks for the detailed analysis.

You are welcome :-)

Quoted 20 lines

Quoted 12 lines

2.3) readahead cache hits: rare case and the impact is temporary

The page at @offset-1 does get referenced by this stream, but it's created by someone else at some distant time ago. The page at @offset-1 may be lifted to active lru by this second reference, or too late and get reclaimed - by the time we reference page @offset.

Normally its a range of cached pages. We are a) either walking inside the range and enjoying the cache hits, b) or we walk out of it and restart readahead by ourself, c) or the range of cached pages get reclaimed while we are walking on them, and hence cannot find page @offset-1.

Quoted 4 lines

Obviously (c) is rare and temporary and is the main cause of (2.3). As soon as we goto the next page at @offset+1, we'll its 'previous' page at @offset to be cached(it is created by us!). So the context readahead starts working again - it's merely delayed by one page :-)

Thanks. The question is how much performance impact this has on the stream that is readaheaded. I guess it would be only a smaller "hickup", with some luck hidden by the block level RA?

Yes there will be hickup: whenever the stream walks out of the current cached page range(or the pages get reclaimed while we are walking in it), there will be a 1-page read, followed by a 4-page readahead, and then 8, 16, ... page sized readahead, i.e. a readahead window rampup process.

That's assuming we are doing 1-page reads. For large sendfile() calls, the readahead size will be instantly restored to its full size on the first cache miss.

Quoted 2 lines

The other question would be if it could cause the readahead code to do a lot of unnecessary work, but your answer seems to be "no". Fine.

Right. The readahead will automatically be turned off inside the cached page ranges, and restarted after walking out of it.

Quoted 1 line

I think the concept is sound.

^_^ Thanks for your appreciation!

Best Regards,
Fengguang

Introduce page cache context based readahead algorithm. This is to better support concurrent read streams in general.

RATIONALE
---------
The current readahead algorithm detects interleaved reads in a _passive_ way. Given a sequence of interleaved streams 1,1001,2,1002,3,4,1003,5,1004,1005,6,... By checking for (offset == prev_offset + 1), it will discover the sequentialness between 3,4 and between 1004,1005, and start doing sequential readahead for the individual streams since page 4 and page 1005.

The context readahead algorithm guarantees to discover the sequentialness no matter how the streams are interleaved. For the above example, it will start sequential readahead since page 2 and 1002.

The trick is to poke for page @offset-1 in the page cache when it has no other clues on the sequentialness of request @offset: if the current requenst belongs to a sequential stream, that stream must have accessed page @offset-1 recently, and the page will still be cached now. So if page @offset-1 is there, we can take request @offset as a sequential access.

BENEFICIARIES
-------------
- strictly interleaved reads i.e. 1,1001,2,1002,3,1003,... the current readahead will take them as silly random reads; the context readahead will take them as two sequential streams.

- cooperative IO processes i.e. NFS and SCST
They create a thread pool, farming off (sequential) IO requests to different threads which will be performing interleaved IO.

It was not easy(or possible) to reliably tell from file->f_ra all those cooperative processes working on the same sequential stream, since they will have different file->f_ra instances. And NFSD's file->f_ra is particularly unusable, since their file objects are dynamically created for each request. The nfsd does have code trying to restore the f_ra bits, but not satisfactory.

Quoted 31 lines · Wu Fengguang

Introduce page cache context based readahead algorithm. This is to better support concurrent read streams in general.

RATIONALE
---------
The current readahead algorithm detects interleaved reads in a _passive_ way. Given a sequence of interleaved streams 1,1001,2,1002,3,4,1003,5,1004,1005,6,... By checking for (offset == prev_offset + 1), it will discover the sequentialness between 3,4 and between 1004,1005, and start doing sequential readahead for the individual streams since page 4 and page 1005.

The context readahead algorithm guarantees to discover the sequentialness no matter how the streams are interleaved. For the above example, it will start sequential readahead since page 2 and 1002.

The trick is to poke for page @offset-1 in the page cache when it has no other clues on the sequentialness of request @offset: if the current requenst belongs to a sequential stream, that stream must have accessed page @offset-1 recently, and the page will still be cached now. So if page @offset-1 is there, we can take request @offset as a sequential access.

BENEFICIARIES
-------------
- strictly interleaved reads i.e. 1,1001,2,1002,3,1003,... the current readahead will take them as silly random reads; the context readahead will take them as two sequential streams.

- cooperative IO processes i.e. NFS and SCST
They create a thread pool, farming off (sequential) IO requests to different threads which will be performing interleaved IO.

Quoted 5 lines

It was not easy(or possible) to reliably tell from file->f_ra all those cooperative processes working on the same sequential stream, since they will have different file->f_ra instances. And NFSD's file->f_ra is particularly unusable, since their file objects are dynamically created for each request. The nfsd does have code trying to restore the f_ra bits, but not satisfactory.

Hi, Wu,

I tested out your patches. Below are some basic iozone numbers for a single NFS client reading a file. The iozone command line is:

iozone -s 2000000 -r 64 -f /mnt/test/testfile -i 1 -w

The file system is unmounted after each run to flush the cache. The numbers below reflect only a single run each. The file system was also unmounted on the NFS client after each run.

KEY
---
vanilla: 2.6.30-rc1
readahead: 2.6.30-rc1 + your 10 readahead patches
context readahead: 2.6.30-rc1 + your 10 readahead patches + the 3
context readahead patches.
nfsd's: number of NFSD threads on the server

I'll note that the cfq in 2.6.30-rc1 is crippled, and that Jens has a patch posted that makes the numbers look at least a little better, but that's immaterial to this discussion, I think.

vanilla

nfsd's | 1 | 2 | 4 | 8
--------+---------------+-------+------

cfq     | 43127 | 22354 | 20858 | 21179
deadline| 43732 | 68059 | 76659 | 83231

readahead

nfsd's | 1 | 2 | 4 | 8
--------+---------------+-------+------

cfq     | 42471 | 21913 | 21252 | 20979
deadline| 42801 | 70158 | 82068 | 82406

context readahead

nfsd's | 1 | 2 | 4 | 8
--------+---------------+-------+------

cfq     | 42827 | 21882 | 20678 | 21508
deadline| 43040 | 71173 | 82407 | 86583

Quoted 4 lines

I tested out your patches. Below are some basic iozone numbers for a single NFS client reading a file. The iozone command line is:

iozone -s 2000000 -r 64 -f /mnt/test/testfile -i 1 -w

Jeff, thank you very much for the testing out!

Quoted 11 lines

The file system is unmounted after each run to flush the cache. The numbers below reflect only a single run each. The file system was also unmounted on the NFS client after each run.

KEY
---
vanilla: 2.6.30-rc1
readahead: 2.6.30-rc1 + your 10 readahead patches
context readahead: 2.6.30-rc1 + your 10 readahead patches + the 3
context readahead patches.
nfsd's: number of NFSD threads on the server

I guess you are applying the readahead patches to the server side?

What's the NFS mount options and client/server side readahead size? The context readahead is pretty sensible to these parameters.

Quoted 18 lines

I'll note that the cfq in 2.6.30-rc1 is crippled, and that Jens has a patch posted that makes the numbers look at least a little better, but that's immaterial to this discussion, I think.

vanilla

nfsd's | 1 | 2 | 4 | 8
--------+---------------+-------+------

cfq     | 43127 | 22354 | 20858 | 21179
deadline| 43732 | 68059 | 76659 | 83231

readahead

nfsd's | 1 | 2 | 4 | 8
--------+---------------+-------+------

cfq     | 42471 | 21913 | 21252 | 20979
deadline| 42801 | 70158 | 82068 | 82406

Quoted 6 lines

context readahead

nfsd's | 1 | 2 | 4 | 8
--------+---------------+-------+------

cfq     | 42827 | 21882 | 20678 | 21508
deadline| 43040 | 71173 | 82407 | 86583

Let me transform them into relative numbers:

             A     B     C      A..B      A..C         
cfq-1      43127 42471 42827    -1.5%     -0.7%         
cfq-2      22354 21913 21882    -2.0%     -2.1%         
cfq-4      20858 21252 20678    +1.9%     -0.9%         
cfq-8      21179 20979 21508    -0.9%     +1.6%         

deadline-1 43732 42801 43040    -2.1%     -1.6%         
deadline-2 68059 70158 71173    +3.1%     +4.6%         
deadline-4 76659 82068 82407    +7.1%     +7.5%         
deadline-8 83231 82406 86583    -1.0%     +4.0%         

Summaries:
1) the overall numbers are slightly negative for CFQ and looks better with deadline.

Anyway we have the io context problem for CFQ. And I'm planning to dive into the CFQ code and your patch on that :-)

2) the single thread case performance consistently dropped by 1-2%.

It seems not related to the behavior changes introduced by the mmap readahead patches and context readahead patches. And looks more like some overheads created by the code reorganization and the patch "readahead: apply max_sane_readahead() limit in ondemand_readahead()" which adds a bit overhead with the call max_sane_readahead().

I'll try to root cause it.

Thanks again for the numbers!

Quoted 24 lines · Ingo Molnar

Quoted 10 lines · Wu Fengguang

Introduce page cache context based readahead algorithm. This is to better support concurrent read streams in general.
/*
+ * Count contiguously cached pages from @offset-1 to @offset-@max,
+ * this count is a conservative estimation of
+ * - length of the sequential read sequence, or
+ * - thrashing threshold in memory tight systems
+ */

mm/readahead.c +2 -0

+static pgoff_t count_history_pages(struct address_space *mapping,
+				   struct file_ra_state *ra,

mm/readahead.c static unsigned long get_next_ra_size(st · line 349

Quoted 10 lines

mm/readahead.c +10 -0

+				   pgoff_t offset, unsigned long max)
+{
+	pgoff_t head;
+
+	rcu_read_lock();
+	head = radix_tree_prev_hole(&mapping->page_tree, offset - 1, max);
+	rcu_read_unlock();
+
+	return offset - 1 - head;
+}

Very elegant method! I suspect this will work far better than adding various increasingly more complex heuristics.

Quoted 1 line

Emphatically-Acked-by Ingo Molnar <[email protected]>

Thank you Ingo!

The only pity is that this heuristic can be defeated by some user space program that tries to do aggressive drop-behind via fadvise(DONTNEED) calls. But as long as the drop-behind algorithm be a bit lazy and does not try to squeeze the last page at @offset-1, this patch will work just OK.

The context readahead idea is so fundamental, that a slightly modified algorithm can be used for all kinds of sequential patterns, and it can automatically adapt to the thrashing threshold.

        1 if (probe_page(index - 1)) {
        2          begin = next_hole(index, max);
        3          H     = index - prev_hole(index, 2*max);
        4          end   = index + H;
        5          update_window(begin, end);
        6          submit_io();
        7 }

            [=] history [#] current [_] readahead [.] new readahead
            ==========================#____________..............
        1                            ^index-1
        2                             |----------->[begin
        3  |<----------- H -----------|
        4                             |----------- H ----------->]end
        5                                          [ new window ]

We didn't do that because we want to
- avoid unnecessary page cache lookups for normal cases
- be more aggressive when thrashings are not a concern

However, readahead thrashings are far more prevalent than one would expect in a FTP/HTTP file streaming server. It can happen in a modern server with 16GB memory, 1Gbps outbound bandwidth and 1MB readahead size, due to the existences of slow streams.

Let's do a coarse calculation. The 8GB inactive_list pages will be cycled in 64Gb/1Gbps=64 seconds. This means an async readahead window must be consumed in 64s, or it will be thrashed. That's a speed of 2048KB/64s=32KB/s. Any client below this speed will create thrashings in the server. In practice, those poor slow clients could amount to half of the total connections(partly because it will take them more time to download anything). The frequent thrashings will in return speedup the LRU cycling/aging speed...

We need a thrashing safe mode which do
- the above modified context readahead algorithm
- conservative ramp up of readahead size
- conservative async readahead size

The main problem is: when shall we switch into the mode?

We can start with aggressive readahead and try to detect readahead thrashings and switch into thrashing safe mode automatically. This will work for non-interleaved reads. However the big file streamer - lighttpd - does interleaved reads. The current data structure is not able to detect most readahead thrashings for lighttpd.

Luckily, the non-resident page tracking facility could help this case. There the thrashed pages with their timing info can be found, based on which we can have some extended context readahead algorithm that could even overcome the drop-behind problem :)

Thanks,
Fengguang
--
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/

Hi, Fengguang,

Quoted 19 lines · Wu Fengguang

Quoted 4 lines

I tested out your patches. Below are some basic iozone numbers for a single NFS client reading a file. The iozone command line is:

iozone -s 2000000 -r 64 -f /mnt/test/testfile -i 1 -w

Jeff, thank you very much for the testing out!

Quoted 11 lines

The file system is unmounted after each run to flush the cache. The numbers below reflect only a single run each. The file system was also unmounted on the NFS client after each run.

KEY
---
vanilla: 2.6.30-rc1
readahead: 2.6.30-rc1 + your 10 readahead patches
context readahead: 2.6.30-rc1 + your 10 readahead patches + the 3
context readahead patches.
nfsd's: number of NFSD threads on the server

Quoted 1 line

I guess you are applying the readahead patches to the server side?

That's right.

Quoted 2 lines

What's the NFS mount options and client/server side readahead size? The context readahead is pretty sensible to these parameters.

Default options everywhere.

Quoted 3 lines

Quoted 3 lines

I'll note that the cfq in 2.6.30-rc1 is crippled, and that Jens has a patch posted that makes the numbers look at least a little better, but that's immaterial to this discussion, I think.

Quoted 13 lines

Let me transform them into relative numbers:

             A     B     C      A..B      A..C
cfq-1      43127 42471 42827    -1.5%     -0.7%
cfq-2      22354 21913 21882    -2.0%     -2.1%
cfq-4      20858 21252 20678    +1.9%     -0.9%
cfq-8      21179 20979 21508    -0.9%     +1.6%

deadline-1 43732 42801 43040    -2.1%     -1.6%
deadline-2 68059 70158 71173    +3.1%     +4.6%
deadline-4 76659 82068 82407    +7.1%     +7.5%
deadline-8 83231 82406 86583    -1.0%     +4.0%

Quoted 3 lines

Summaries:
1) the overall numbers are slightly negative for CFQ and looks better with deadline.

The variance is probably 1-2%. I'll try to quantify that for you.

Quoted 2 lines

Anyway we have the io context problem for CFQ. And I'm planning to dive into the CFQ code and your patch on that :-)

Jens already reworked the patch and included it in his for-linus branch of the block tree. So, you can start there. ;-)

Quoted 9 lines

2) the single thread case performance consistently dropped by 1-2%.

It seems not related to the behavior changes introduced by the mmap readahead patches and context readahead patches. And looks more like some overheads created by the code reorganization and the patch "readahead: apply max_sane_readahead() limit in ondemand_readahead()" which adds a bit overhead with the call max_sane_readahead().

I'll try to root cause it.