The readahead code has undergone many changes in the 2.6 kernel and the 
current implementation is in my opinion obtuse and hard to maintain.  We 
would like to offer up an alternative simplified design which will not 
only make the code easier to maintain, but as performance tests have 
shown, results in better performance in many cases.

We are very interested in having others review and try out the code and 
run whatever performance tests they see fit.

Quick overview of the new design:

The key design point of the new design is to make the readahead code 
aware of the size of the I/O request.  This change eliminates the need 
for treating large random I/O as sequential and all of the averaging 
code that exists just to support this.  In addition to this change, the 
new design ramps up quicker, and shuts off faster.  This, combined with 
the request size awareness eliminates the so called "slow read path" 
that we try so hard to avoid in the current code.  For complete details 
on the design of the new readahead logic, please refer to 
http://www-124.ibm.com/developerworks/opensource/linuxperf/readahead/read-ahead-design.pdf

There are a few exception cases which still concern me. 

1. pages already in cache
2. I/O queue congestion.
3. page stealing

The first of these is a file already residing in page cache.  If we do 
not code for this case we will end up doing multiple page lookups for 
each page.  The current code tries to handle this using the 
check_ra_success function, but this code does not work.  
check_ra_success will subtract 1 page each time an I/O is completely 
contained in page cache, however on the main path we will increment the 
window size by 2 for each page in the request (up to max_readahead) thus 
negating the reduction.  My question is what is the right behavior.  
Reducing the size of the ahead window doesn't help.  You must turn off 
readahead to have any effect.  Once you believe all pages to be in page 
cache we should just immediately turn off readahead.  What is this 
trigger point?  4 I/Os in a row? 400?  My concern is that the savings 
for skipping the double lookup appears to be on the order of .5% CPU in 
my tests, but the penalty for small I/O in sequential read case can be 
substantial.  Currently the new code does not handle this case, but it 
could be enhanced to do so. 

The second case is on queue congestion.  Current code does not submit 
the I/O if the queue is congested. This will result in each page being 
read serially on the cache miss path.  Does submitting 32 4k I/Os 
instead of 1 128k I/O help queue congestion?  Here is one place where 
the current cod gets real confusing.  We reduce the window by 1 page for 
queue congestion(treated the same as page cache hit), but we leave the 
information about the current and ahead windows alone even though we did 
not issue the I/O to populate it and so we will never issue the I/O from 
the readahead code.  Eventually we will start taking cache misses since 
no one read the pages.  That code decrements the window size by 3, but 
as in the cache hit case since we are still reading sequentially we keep 
incrementing by 2 for each page; net effect -1 for each page not in 
cache.    Again, the new code ignores the congestion case and still 
tries to do readahead, thus minimizing/optimizing the I/O requests sent 
to the device.  Is this right?  If not what should we do?

The third exception case is page stealing where the page into which 
readahead was done is reclaimed before the data is copied to user 
space.  This would seem to be a somewhat rare case only happening under 
sever memory pressure, but my tests have shown that it can occur quite 
frequently with as little as 4 threads doing 1M readahead or 16 threads 
doing 128k readahead on a machine with 1GB memory of which 950MB is page 
cache.  Here it would seem the right thing to do is shrink the window 
size and reduce the  chance for page stealing, this however kill I/O 
performance if done to aggressively.  Again the current code may not 
perform as expected. As in the 2 previous cases, the -3 is offset by a 
+2 and so unless > 2/3 of pages in a given window are stolen the net 
effect is to ignore the page stealing.  New code will slowly shrink the 
window as long as stealing occurs, but will quickly regrow once it stops.

Performance:

A large number of tests have been run to test the performance of the new 
code, but it is in no way comprehensive.  Primarily I ran tiobench to 
ensure that the major code paths were hit.  I also ran sysbench in the 
mode which has been reported to cause problems on the current/recent 
readahead code.  I used multiple machines and disk types to test on.  
The small system is a 1 way pentium III 866MHz with 256MB memory and a 
dedicated IDE test disk.  The second machine is an 8way pentium IV 
2.0GHz with 1GB memory and test were on on both a dedicated 10k-rpm SCSI 
disk on on-board adaptec adapter and on 2GBit QLA2300 Fiber attached 
FAStT700 7 disk RAID0 array.

In summary, the new code was always equal to or better than the current 
code on all variation and all test configurations.  Tests were run 
multiple time on freshly formatted JFS file systems on both 2.6.8.1 and 
2.6.9-rc2-mm1.  Results for the 2 kernel versions were similar so I am 
including only the 2.6.9-rc2-mm1 results.

Tiobench results:

Summary:
    For single threaded tests sequential reads the code is equal on IDE 
and single SCSI disks, but the new code is 10-20% fasted on RAID.  For 
Multi threaded sequential reads the new code is always faster(20-50%).  
For random reads the new code is equal to the old for all cases where 
the request size is less than or equal to the max_readahead size.   For 
request sizes larger than max_readahead the new code is as much as 50% 
faster.

tiobench --block n --size 4000 --numruns 2 --threads m 
	(where m is one of 4096,16384,524288 and n is one of 1,4,16,64)


Graph lines with "new7" are the new readahead code, all others are the 
stock kernel.

Single CPU IDE
http://www-124.ibm.com/developerworks/opensource/linuxperf/readahead/128k-ide.html

8way Single SCSI
http://www-124.ibm.com/developerworks/opensource/linuxperf/readahead/mm1-128k-new7.html

8way RAID0
http://www-124.ibm.com/developerworks/opensource/linuxperf/readahead/mm1-128kRAID-new7.html


Sysbench results:

sysbench --num-threads=254 --test=fileio --file-total-size=4G --file-test-mode=rndrw'


IDE Disk
   Current:  1.303 MB/sec average
    New:      1.314 MB/sec average

SCSI Disk
    Currnent: 2.713 MB/sec average
    New:         2.746 MB/sec average

For full results see:
http://www-124.ibm.com/developerworks/opensource/linuxperf/readahead/sysbench.results


Thanks,
Steve Pratt and Dom Heger