mm/readahead.c

   1 /*
   2  * mm/readahead.c - address_space-level file readahead.
   3  *
   4  * Copyright (C) 2002, Linus Torvalds
   5  *
   6  * 09Apr2002    akpm@zip.com.au
   7  *              Initial version.
   8  */
   9
  10 #include <linux/kernel.h>
  11 #include <linux/fs.h>
  12 #include <linux/mm.h>
  13 #include <linux/module.h>
  14 #include <linux/blkdev.h>
  15 #include <linux/backing-dev.h>
  16 #include <linux/pagevec.h>
  17
  18 struct backing_dev_info default_backing_dev_info = {
  19         .ra_pages       = (VM_MAX_READAHEAD * 1024) / PAGE_CACHE_SIZE,
  20         .state          = 0,
  21 };
  22
  23 EXPORT_SYMBOL_GPL(default_backing_dev_info);
  24
  25 /*
  26  * Initialise a struct file's readahead state
  27  */
  28 void
  29 file_ra_state_init(struct file_ra_state *ra, struct address_space *mapping)
  30 {
  31         memset(ra, 0, sizeof(*ra));
  32         ra->ra_pages = mapping->backing_dev_info->ra_pages;
  33         ra->average = ra->ra_pages / 2;
  34 }
  35
  36 EXPORT_SYMBOL(file_ra_state_init);
  37
  38 /*
  39  * Return max readahead size for this inode in number-of-pages.
  40  */
  41 static inline unsigned long get_max_readahead(struct file_ra_state *ra)
  42 {
  43         return ra->ra_pages;
  44 }
  45
  46 static inline unsigned long get_min_readahead(struct file_ra_state *ra)
  47 {
  48         return (VM_MIN_READAHEAD * 1024) / PAGE_CACHE_SIZE;
  49 }
  50
  51 #define list_to_page(head) (list_entry((head)->prev, struct page, list))
  52
  53 /**
  54  * read_cache_pages - populate an address space with some pages, and
  55  *                      start reads against them.
  56  * @mapping: the address_space
  57  * @pages: The address of a list_head which contains the target pages.  These
  58  *   pages have their ->index populated and are otherwise uninitialised.
  59  * @filler: callback routine for filling a single page.
  60  * @data: private data for the callback routine.
  61  *
  62  * Hides the details of the LRU cache etc from the filesystems.
  63  */
  64 int read_cache_pages(struct address_space *mapping, struct list_head *pages,
  65                  int (*filler)(void *, struct page *), void *data)
  66 {
  67         struct page *page;
  68         struct pagevec lru_pvec;
  69         int ret = 0;
  70
  71         pagevec_init(&lru_pvec, 0);
  72
  73         while (!list_empty(pages)) {
  74                 page = list_to_page(pages);
  75                 list_del(&page->list);
  76                 if (add_to_page_cache(page, mapping, page->index, GFP_KERNEL)) {
  77                         page_cache_release(page);
  78                         continue;
  79                 }
  80                 ret = filler(data, page);
  81                 if (!pagevec_add(&lru_pvec, page))
  82                         __pagevec_lru_add(&lru_pvec);
  83                 if (ret) {
  84                         while (!list_empty(pages)) {
  85                                 struct page *victim;
  86
  87                                 victim = list_to_page(pages);
  88                                 list_del(&victim->list);
  89                                 page_cache_release(victim);
  90                         }
  91                         break;
  92                 }
  93         }
  94         pagevec_lru_add(&lru_pvec);
  95         return ret;
  96 }
  97
  98 EXPORT_SYMBOL(read_cache_pages);
  99
 100 static int read_pages(struct address_space *mapping, struct file *filp,
 101                 struct list_head *pages, unsigned nr_pages)
 102 {
 103         unsigned page_idx;
 104         struct pagevec lru_pvec;
 105         int ret = 0;
 106
 107         if (mapping->a_ops->readpages) {
 108                 ret = mapping->a_ops->readpages(filp, mapping, pages, nr_pages);
 109                 goto out;
 110         }
 111
 112         pagevec_init(&lru_pvec, 0);
 113         for (page_idx = 0; page_idx < nr_pages; page_idx++) {
 114                 struct page *page = list_to_page(pages);
 115                 list_del(&page->list);
 116                 if (!add_to_page_cache(page, mapping,
 117                                         page->index, GFP_KERNEL)) {
 118                         mapping->a_ops->readpage(filp, page);
 119                         if (!pagevec_add(&lru_pvec, page))
 120                                 __pagevec_lru_add(&lru_pvec);
 121                 } else {
 122                         page_cache_release(page);
 123                 }
 124         }
 125         pagevec_lru_add(&lru_pvec);
 126 out:
 127         return ret;
 128 }
 129
 130 /*
 131  * Readahead design.
 132  *
 133  * The fields in struct file_ra_state represent the most-recently-executed
 134  * readahead attempt:
 135  *
 136  * start:       Page index at which we started the readahead
 137  * size:        Number of pages in that read
 138  *              Together, these form the "current window".
 139  *              Together, start and size represent the `readahead window'.
 140  * next_size:   The number of pages to read on the next readahead miss.
 141  *              Has the magical value -1UL if readahead has been disabled.
 142  * prev_page:   The page which the readahead algorithm most-recently inspected.
 143  *              prev_page is mainly an optimisation: if page_cache_readahead
 144  *              sees that it is again being called for a page which it just
 145  *              looked at, it can return immediately without making any state
 146  *              changes.
 147  * ahead_start,
 148  * ahead_size:  Together, these form the "ahead window".
 149  * ra_pages:    The externally controlled max readahead for this fd.
 150  *
 151  * When readahead is in the "maximally shrunk" state (next_size == -1UL),
 152  * readahead is disabled.  In this state, prev_page and size are used, inside
 153  * handle_ra_miss(), to detect the resumption of sequential I/O.  Once there
 154  * has been a decent run of sequential I/O (defined by get_min_readahead),
 155  * readahead is reenabled.
 156  *
 157  * The readahead code manages two windows - the "current" and the "ahead"
 158  * windows.  The intent is that while the application is walking the pages
 159  * in the current window, I/O is underway on the ahead window.  When the
 160  * current window is fully traversed, it is replaced by the ahead window
 161  * and the ahead window is invalidated.  When this copying happens, the
 162  * new current window's pages are probably still locked.  When I/O has
 163  * completed, we submit a new batch of I/O, creating a new ahead window.
 164  *
 165  * So:
 166  *
 167  *   ----|----------------|----------------|-----
 168  *       ^start           ^start+size
 169  *                        ^ahead_start     ^ahead_start+ahead_size
 170  *
 171  *         ^ When this page is read, we submit I/O for the
 172  *           ahead window.
 173  *
 174  * A `readahead hit' occurs when a read request is made against a page which is
 175  * inside the current window.  Hits are good, and the window size (next_size)
 176  * is grown aggressively when hits occur.  Two pages are added to the next
 177  * window size on each hit, which will end up doubling the next window size by
 178  * the time I/O is submitted for it.
 179  *
 180  * If readahead hits are more sparse (say, the application is only reading
 181  * every second page) then the window will build more slowly.
 182  *
 183  * On a readahead miss (the application seeked away) the readahead window is
 184  * shrunk by 25%.  We don't want to drop it too aggressively, because it is a
 185  * good assumption that an application which has built a good readahead window
 186  * will continue to perform linear reads.  Either at the new file position, or
 187  * at the old one after another seek.
 188  *
 189  * After enough misses, readahead is fully disabled. (next_size = -1UL).
 190  *
 191  * There is a special-case: if the first page which the application tries to
 192  * read happens to be the first page of the file, it is assumed that a linear
 193  * read is about to happen and the window is immediately set to half of the
 194  * device maximum.
 195  *
 196  * A page request at (start + size) is not a miss at all - it's just a part of
 197  * sequential file reading.
 198  *
 199  * This function is to be called for every page which is read, rather than when
 200  * it is time to perform readahead.  This is so the readahead algorithm can
 201  * centrally work out the access patterns.  This could be costly with many tiny
 202  * read()s, so we specifically optimise for that case with prev_page.
 203  */
 204
 205 /*
 206  * do_page_cache_readahead actually reads a chunk of disk.  It allocates all
 207  * the pages first, then submits them all for I/O. This avoids the very bad
 208  * behaviour which would occur if page allocations are causing VM writeback.
 209  * We really don't want to intermingle reads and writes like that.
 210  *
 211  * Returns the number of pages which actually had IO started against them.
 212  */
 213 static inline int
 214 __do_page_cache_readahead(struct address_space *mapping, struct file *filp,
 215                         unsigned long offset, unsigned long nr_to_read)
 216 {
 217         struct inode *inode = mapping->host;
 218         struct page *page;
 219         unsigned long end_index;        /* The last page we want to read */
 220         LIST_HEAD(page_pool);
 221         int page_idx;
 222         int ret = 0;
 223         loff_t isize = i_size_read(inode);
 224
 225         if (isize == 0)
 226                 goto out;
 227
 228         end_index = ((isize - 1) >> PAGE_CACHE_SHIFT);
 229
 230         /*
 231          * Preallocate as many pages as we will need.
 232          */
 233         spin_lock_irq(&mapping->tree_lock);
 234         for (page_idx = 0; page_idx < nr_to_read; page_idx++) {
 235                 unsigned long page_offset = offset + page_idx;
 236
 237                 if (page_offset > end_index)
 238                         break;
 239
 240                 page = radix_tree_lookup(&mapping->page_tree, page_offset);
 241                 if (page)
 242                         continue;
 243
 244                 spin_unlock_irq(&mapping->tree_lock);
 245                 page = page_cache_alloc_cold(mapping);
 246                 spin_lock_irq(&mapping->tree_lock);
 247                 if (!page)
 248                         break;
 249                 page->index = page_offset;
 250                 list_add(&page->list, &page_pool);
 251                 ret++;
 252         }
 253         spin_unlock_irq(&mapping->tree_lock);
 254
 255         /*
 256          * Now start the IO.  We ignore I/O errors - if the page is not
 257          * uptodate then the caller will launch readpage again, and
 258          * will then handle the error.
 259          */
 260         if (ret)
 261                 read_pages(mapping, filp, &page_pool, ret);
 262         BUG_ON(!list_empty(&page_pool));
 263 out:
 264         return ret;
 265 }
 266
 267 /*
 268  * Chunk the readahead into 2 megabyte units, so that we don't pin too much
 269  * memory at once.
 270  */
 271 int force_page_cache_readahead(struct address_space *mapping, struct file *filp,
 272                 unsigned long offset, unsigned long nr_to_read)
 273 {
 274         int ret = 0;
 275
 276         if (unlikely(!mapping->a_ops->readpage && !mapping->a_ops->readpages))
 277                 return -EINVAL;
 278
 279         while (nr_to_read) {
 280                 int err;
 281
 282                 unsigned long this_chunk = (2 * 1024 * 1024) / PAGE_CACHE_SIZE;
 283
 284                 if (this_chunk > nr_to_read)
 285                         this_chunk = nr_to_read;
 286                 err = __do_page_cache_readahead(mapping, filp,
 287                                                 offset, this_chunk);
 288                 if (err < 0) {
 289                         ret = err;
 290                         break;
 291                 }
 292                 ret += err;
 293                 offset += this_chunk;
 294                 nr_to_read -= this_chunk;
 295         }
 296         return ret;
 297 }
 298
 299 /*
 300  * This version skips the IO if the queue is read-congested, and will tell the
 301  * block layer to abandon the readahead if request allocation would block.
 302  *
 303  * force_page_cache_readahead() will ignore queue congestion and will block on
 304  * request queues.
 305  */
 306 int do_page_cache_readahead(struct address_space *mapping, struct file *filp,
 307                         unsigned long offset, unsigned long nr_to_read)
 308 {
 309         if (!bdi_read_congested(mapping->backing_dev_info))
 310                 return __do_page_cache_readahead(mapping, filp,
 311                                                 offset, nr_to_read);
 312         return 0;
 313 }
 314
 315 /*
 316  * Check how effective readahead is being.  If the amount of started IO is
 317  * less than expected then the file is partly or fully in pagecache and
 318  * readahead isn't helping.  Shrink the window.
 319  *
 320  * But don't shrink it too much - the application may read the same page
 321  * occasionally.
 322  */
 323 static inline void
 324 check_ra_success(struct file_ra_state *ra, pgoff_t attempt,
 325                         pgoff_t actual, pgoff_t orig_next_size)
 326 {
 327         if (actual == 0) {
 328                 if (orig_next_size > 1) {
 329                         ra->next_size = orig_next_size - 1;
 330                         if (ra->ahead_size)
 331                                 ra->ahead_size = ra->next_size;
 332                 } else {
 333                         ra->next_size = -1UL;
 334                         ra->size = 0;
 335                 }
 336         }
 337 }
 338
 339 /*
 340  * page_cache_readahead is the main function.  If performs the adaptive
 341  * readahead window size management and submits the readahead I/O.
 342  */
 343 void
 344 page_cache_readahead(struct address_space *mapping, struct file_ra_state *ra,
 345                         struct file *filp, unsigned long offset)
 346 {
 347         unsigned max;
 348         unsigned min;
 349         unsigned orig_next_size;
 350         unsigned actual;
 351         int first_access=0;
 352         unsigned long preoffset=0;
 353
 354         /*
 355          * Here we detect the case where the application is performing
 356          * sub-page sized reads.  We avoid doing extra work and bogusly
 357          * perturbing the readahead window expansion logic.
 358          * If next_size is zero, this is the very first read for this
 359          * file handle, or the window is maximally shrunk.
 360          */
 361         if (offset == ra->prev_page) {
 362                 if (ra->next_size != 0)
 363                         goto out;
 364         }
 365
 366         if (ra->next_size == -1UL)
 367                 goto out;       /* Maximally shrunk */
 368
 369         max = get_max_readahead(ra);
 370         if (max == 0)
 371                 goto out;       /* No readahead */
 372
 373         min = get_min_readahead(ra);
 374         orig_next_size = ra->next_size;
 375
 376         if (ra->next_size == 0) {
 377                 /*
 378                  * Special case - first read.
 379                  * We'll assume it's a whole-file read, and
 380                  * grow the window fast.
 381                  */
 382                 first_access=1;
 383                 ra->next_size = max / 2;
 384                 ra->prev_page = offset;
 385                 ra->serial_cnt++;
 386                 goto do_io;
 387         }
 388
 389         if (offset == ra->prev_page + 1) {
 390                 if (ra->serial_cnt <= (max * 2))
 391                         ra->serial_cnt++;
 392         } else {
 393                 ra->average = (ra->average + ra->serial_cnt) / 2;
 394                 ra->serial_cnt = 1;
 395         }
 396         preoffset = ra->prev_page;
 397         ra->prev_page = offset;
 398
 399         if (offset >= ra->start && offset <= (ra->start + ra->size)) {
 400                 /*
 401                  * A readahead hit.  Either inside the window, or one
 402                  * page beyond the end.  Expand the next readahead size.
 403                  */
 404                 ra->next_size += 2;
 405         } else {
 406                 /*
 407                  * A miss - lseek, pagefault, pread, etc.  Shrink the readahead
 408                  * window.
 409                  */
 410                 ra->next_size -= 2;
 411         }
 412
 413         if ((long)ra->next_size > (long)max)
 414                 ra->next_size = max;
 415         if ((long)ra->next_size <= 0L) {
 416                 ra->next_size = -1UL;
 417                 ra->size = 0;
 418                 goto out;               /* Readahead is off */
 419         }
 420
 421         /*
 422          * Is this request outside the current window?
 423          */
 424         if (offset < ra->start || offset >= (ra->start + ra->size)) {
 425                 /*
 426                  * A miss against the current window.  Have we merely
 427                  * advanced into the ahead window?
 428                  */
 429                 if (offset == ra->ahead_start) {
 430                         /*
 431                          * Yes, we have.  The ahead window now becomes
 432                          * the current window.
 433                          */
 434                         ra->start = ra->ahead_start;
 435                         ra->size = ra->ahead_size;
 436                         ra->prev_page = ra->start;
 437                         ra->ahead_start = 0;
 438                         ra->ahead_size = 0;
 439
 440                         /*
 441                          * Control now returns, probably to sleep until I/O
 442                          * completes against the first ahead page.
 443                          * When the second page in the old ahead window is
 444                          * requested, control will return here and more I/O
 445                          * will be submitted to build the new ahead window.
 446                          */
 447                         goto out;
 448                 }
 449 do_io:
 450                 /*
 451                  * This is the "unusual" path.  We come here during
 452                  * startup or after an lseek.  We invalidate the
 453                  * ahead window and get some I/O underway for the new
 454                  * current window.
 455                  */
 456                 if (!first_access && preoffset >= ra->start &&
 457                                 preoffset < (ra->start + ra->size)) {
 458                          /* Heuristic:  If 'n' pages were
 459                           * accessed in the current window, there
 460                           * is a high probability that around 'n' pages
 461                           * shall be used in the next current window.
 462                           *
 463                           * To minimize lazy-readahead triggered
 464                           * in the next current window, read in
 465                           * an extra page.
 466                           */
 467                         ra->next_size = preoffset - ra->start + 2;
 468                 }
 469                 ra->start = offset;
 470                 ra->size = ra->next_size;
 471                 ra->ahead_start = 0;            /* Invalidate these */
 472                 ra->ahead_size = 0;
 473                 actual = do_page_cache_readahead(mapping, filp, offset,
 474                                                  ra->size);
 475                 if(!first_access) {
 476                         /*
 477                          * do not adjust the readahead window size the first
 478                          * time, the ahead window might get closed if all
 479                          * the pages are already in the cache.
 480                          */
 481                         check_ra_success(ra, ra->size, actual, orig_next_size);
 482                 }
 483         } else {
 484                 /*
 485                  * This read request is within the current window.  It may be
 486                  * time to submit I/O for the ahead window while the
 487                  * application is about to step into the ahead window.
 488                  */
 489                 if (ra->ahead_start == 0) {
 490                         /*
 491                          * if the average io-size is less than maximum
 492                          * readahead size of the file the io pattern is
 493                          * sequential. Hence  bring in the readahead window
 494                          * immediately.
 495                          * Else the i/o pattern is random. Bring
 496                          * in the readahead window only if the last page of
 497                          * the current window is accessed (lazy readahead).
 498                          */
 499                         unsigned long average = ra->average;
 500
 501                         if (ra->serial_cnt > average)
 502                                 average = (ra->serial_cnt + ra->average) / 2;
 503
 504                         if ((average >= max) || (offset == (ra->start +
 505                                                         ra->size - 1))) {
 506                                 ra->ahead_start = ra->start + ra->size;
 507                                 ra->ahead_size = ra->next_size;
 508                                 actual = do_page_cache_readahead(mapping, filp,
 509                                         ra->ahead_start, ra->ahead_size);
 510                                 check_ra_success(ra, ra->ahead_size,
 511                                                 actual, orig_next_size);
 512                         }
 513                 }
 514         }
 515 out:
 516         return;
 517 }
 518
 519
 520 /*
 521  * handle_ra_miss() is called when it is known that a page which should have
 522  * been present in the pagecache (we just did some readahead there) was in fact
 523  * not found.  This will happen if it was evicted by the VM (readahead
 524  * thrashing) or if the readahead window is maximally shrunk.
 525  *
 526  * If the window has been maximally shrunk (next_size == -1UL) then look to see
 527  * if we are getting misses against sequential file offsets.  If so, and this
 528  * persists then resume readahead.
 529  *
 530  * Otherwise we're thrashing, so shrink the readahead window by three pages.
 531  * This is because it is grown by two pages on a readahead hit.  Theory being
 532  * that the readahead window size will stabilise around the maximum level at
 533  * which there is no thrashing.
 534  */
 535 void handle_ra_miss(struct address_space *mapping,
 536                 struct file_ra_state *ra, pgoff_t offset)
 537 {
 538         if (ra->next_size == -1UL) {
 539                 const unsigned long max = get_max_readahead(ra);
 540
 541                 if (offset != ra->prev_page + 1) {
 542                         ra->size = ra->size?ra->size-1:0; /* Not sequential */
 543                 } else {
 544                         ra->size++;                     /* A sequential read */
 545                         if (ra->size >= max) {          /* Resume readahead */
 546                                 ra->start = offset - max;
 547                                 ra->next_size = max;
 548                                 ra->size = max;
 549                                 ra->ahead_start = 0;
 550                                 ra->ahead_size = 0;
 551                         }
 552                 }
 553                 ra->prev_page = offset;
 554         } else {
 555                 const unsigned long min = get_min_readahead(ra);
 556
 557                 ra->next_size -= 3;
 558                 if (ra->next_size < min)
 559                         ra->next_size = min;
 560         }
 561 }
 562
 563 /*
 564  * Given a desired number of PAGE_CACHE_SIZE readahead pages, return a
 565  * sensible upper limit.
 566  */
 567 unsigned long max_sane_readahead(unsigned long nr)
 568 {
 569         unsigned long active;
 570         unsigned long inactive;
 571         unsigned long free;
 572
 573         get_zone_counts(&active, &inactive, &free);
 574         return min(nr, (inactive + free) / 2);
 575 }