readahead.c 17 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580
  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. #include <linux/kernel.h>
  10. #include <linux/fs.h>
  11. #include <linux/mm.h>
  12. #include <linux/module.h>
  13. #include <linux/blkdev.h>
  14. #include <linux/backing-dev.h>
  15. #include <linux/task_io_accounting_ops.h>
  16. #include <linux/pagevec.h>
  17. void default_unplug_io_fn(struct backing_dev_info *bdi, struct page *page)
  18. {
  19. }
  20. EXPORT_SYMBOL(default_unplug_io_fn);
  21. struct backing_dev_info default_backing_dev_info = {
  22. .ra_pages = (VM_MAX_READAHEAD * 1024) / PAGE_CACHE_SIZE,
  23. .state = 0,
  24. .capabilities = BDI_CAP_MAP_COPY,
  25. .unplug_io_fn = default_unplug_io_fn,
  26. };
  27. EXPORT_SYMBOL_GPL(default_backing_dev_info);
  28. /*
  29. * Initialise a struct file's readahead state. Assumes that the caller has
  30. * memset *ra to zero.
  31. */
  32. void
  33. file_ra_state_init(struct file_ra_state *ra, struct address_space *mapping)
  34. {
  35. ra->ra_pages = mapping->backing_dev_info->ra_pages;
  36. ra->prev_page = -1;
  37. }
  38. EXPORT_SYMBOL_GPL(file_ra_state_init);
  39. /*
  40. * Return max readahead size for this inode in number-of-pages.
  41. */
  42. static inline unsigned long get_max_readahead(struct file_ra_state *ra)
  43. {
  44. return ra->ra_pages;
  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. static inline void reset_ahead_window(struct file_ra_state *ra)
  51. {
  52. /*
  53. * ... but preserve ahead_start + ahead_size value,
  54. * see 'recheck:' label in page_cache_readahead().
  55. * Note: We never use ->ahead_size as rvalue without
  56. * checking ->ahead_start != 0 first.
  57. */
  58. ra->ahead_size += ra->ahead_start;
  59. ra->ahead_start = 0;
  60. }
  61. static inline void ra_off(struct file_ra_state *ra)
  62. {
  63. ra->start = 0;
  64. ra->flags = 0;
  65. ra->size = 0;
  66. reset_ahead_window(ra);
  67. return;
  68. }
  69. /*
  70. * Set the initial window size, round to next power of 2 and square
  71. * for small size, x 4 for medium, and x 2 for large
  72. * for 128k (32 page) max ra
  73. * 1-8 page = 32k initial, > 8 page = 128k initial
  74. */
  75. static unsigned long get_init_ra_size(unsigned long size, unsigned long max)
  76. {
  77. unsigned long newsize = roundup_pow_of_two(size);
  78. if (newsize <= max / 32)
  79. newsize = newsize * 4;
  80. else if (newsize <= max / 4)
  81. newsize = newsize * 2;
  82. else
  83. newsize = max;
  84. return newsize;
  85. }
  86. /*
  87. * Set the new window size, this is called only when I/O is to be submitted,
  88. * not for each call to readahead. If a cache miss occured, reduce next I/O
  89. * size, else increase depending on how close to max we are.
  90. */
  91. static inline unsigned long get_next_ra_size(struct file_ra_state *ra)
  92. {
  93. unsigned long max = get_max_readahead(ra);
  94. unsigned long min = get_min_readahead(ra);
  95. unsigned long cur = ra->size;
  96. unsigned long newsize;
  97. if (ra->flags & RA_FLAG_MISS) {
  98. ra->flags &= ~RA_FLAG_MISS;
  99. newsize = max((cur - 2), min);
  100. } else if (cur < max / 16) {
  101. newsize = 4 * cur;
  102. } else {
  103. newsize = 2 * cur;
  104. }
  105. return min(newsize, max);
  106. }
  107. #define list_to_page(head) (list_entry((head)->prev, struct page, lru))
  108. /**
  109. * read_cache_pages - populate an address space with some pages & start reads against them
  110. * @mapping: the address_space
  111. * @pages: The address of a list_head which contains the target pages. These
  112. * pages have their ->index populated and are otherwise uninitialised.
  113. * @filler: callback routine for filling a single page.
  114. * @data: private data for the callback routine.
  115. *
  116. * Hides the details of the LRU cache etc from the filesystems.
  117. */
  118. int read_cache_pages(struct address_space *mapping, struct list_head *pages,
  119. int (*filler)(void *, struct page *), void *data)
  120. {
  121. struct page *page;
  122. struct pagevec lru_pvec;
  123. int ret = 0;
  124. pagevec_init(&lru_pvec, 0);
  125. while (!list_empty(pages)) {
  126. page = list_to_page(pages);
  127. list_del(&page->lru);
  128. if (add_to_page_cache(page, mapping, page->index, GFP_KERNEL)) {
  129. page_cache_release(page);
  130. continue;
  131. }
  132. ret = filler(data, page);
  133. if (!pagevec_add(&lru_pvec, page))
  134. __pagevec_lru_add(&lru_pvec);
  135. if (ret) {
  136. put_pages_list(pages);
  137. break;
  138. }
  139. task_io_account_read(PAGE_CACHE_SIZE);
  140. }
  141. pagevec_lru_add(&lru_pvec);
  142. return ret;
  143. }
  144. EXPORT_SYMBOL(read_cache_pages);
  145. static int read_pages(struct address_space *mapping, struct file *filp,
  146. struct list_head *pages, unsigned nr_pages)
  147. {
  148. unsigned page_idx;
  149. struct pagevec lru_pvec;
  150. int ret;
  151. if (mapping->a_ops->readpages) {
  152. ret = mapping->a_ops->readpages(filp, mapping, pages, nr_pages);
  153. /* Clean up the remaining pages */
  154. put_pages_list(pages);
  155. goto out;
  156. }
  157. pagevec_init(&lru_pvec, 0);
  158. for (page_idx = 0; page_idx < nr_pages; page_idx++) {
  159. struct page *page = list_to_page(pages);
  160. list_del(&page->lru);
  161. if (!add_to_page_cache(page, mapping,
  162. page->index, GFP_KERNEL)) {
  163. mapping->a_ops->readpage(filp, page);
  164. if (!pagevec_add(&lru_pvec, page))
  165. __pagevec_lru_add(&lru_pvec);
  166. } else
  167. page_cache_release(page);
  168. }
  169. pagevec_lru_add(&lru_pvec);
  170. ret = 0;
  171. out:
  172. return ret;
  173. }
  174. /*
  175. * Readahead design.
  176. *
  177. * The fields in struct file_ra_state represent the most-recently-executed
  178. * readahead attempt:
  179. *
  180. * start: Page index at which we started the readahead
  181. * size: Number of pages in that read
  182. * Together, these form the "current window".
  183. * Together, start and size represent the `readahead window'.
  184. * prev_page: The page which the readahead algorithm most-recently inspected.
  185. * It is mainly used to detect sequential file reading.
  186. * If page_cache_readahead sees that it is again being called for
  187. * a page which it just looked at, it can return immediately without
  188. * making any state changes.
  189. * ahead_start,
  190. * ahead_size: Together, these form the "ahead window".
  191. * ra_pages: The externally controlled max readahead for this fd.
  192. *
  193. * When readahead is in the off state (size == 0), readahead is disabled.
  194. * In this state, prev_page is used to detect the resumption of sequential I/O.
  195. *
  196. * The readahead code manages two windows - the "current" and the "ahead"
  197. * windows. The intent is that while the application is walking the pages
  198. * in the current window, I/O is underway on the ahead window. When the
  199. * current window is fully traversed, it is replaced by the ahead window
  200. * and the ahead window is invalidated. When this copying happens, the
  201. * new current window's pages are probably still locked. So
  202. * we submit a new batch of I/O immediately, creating a new ahead window.
  203. *
  204. * So:
  205. *
  206. * ----|----------------|----------------|-----
  207. * ^start ^start+size
  208. * ^ahead_start ^ahead_start+ahead_size
  209. *
  210. * ^ When this page is read, we submit I/O for the
  211. * ahead window.
  212. *
  213. * A `readahead hit' occurs when a read request is made against a page which is
  214. * the next sequential page. Ahead window calculations are done only when it
  215. * is time to submit a new IO. The code ramps up the size agressively at first,
  216. * but slow down as it approaches max_readhead.
  217. *
  218. * Any seek/ramdom IO will result in readahead being turned off. It will resume
  219. * at the first sequential access.
  220. *
  221. * There is a special-case: if the first page which the application tries to
  222. * read happens to be the first page of the file, it is assumed that a linear
  223. * read is about to happen and the window is immediately set to the initial size
  224. * based on I/O request size and the max_readahead.
  225. *
  226. * This function is to be called for every read request, rather than when
  227. * it is time to perform readahead. It is called only once for the entire I/O
  228. * regardless of size unless readahead is unable to start enough I/O to satisfy
  229. * the request (I/O request > max_readahead).
  230. */
  231. /*
  232. * do_page_cache_readahead actually reads a chunk of disk. It allocates all
  233. * the pages first, then submits them all for I/O. This avoids the very bad
  234. * behaviour which would occur if page allocations are causing VM writeback.
  235. * We really don't want to intermingle reads and writes like that.
  236. *
  237. * Returns the number of pages requested, or the maximum amount of I/O allowed.
  238. *
  239. * do_page_cache_readahead() returns -1 if it encountered request queue
  240. * congestion.
  241. */
  242. static int
  243. __do_page_cache_readahead(struct address_space *mapping, struct file *filp,
  244. pgoff_t offset, unsigned long nr_to_read)
  245. {
  246. struct inode *inode = mapping->host;
  247. struct page *page;
  248. unsigned long end_index; /* The last page we want to read */
  249. LIST_HEAD(page_pool);
  250. int page_idx;
  251. int ret = 0;
  252. loff_t isize = i_size_read(inode);
  253. if (isize == 0)
  254. goto out;
  255. end_index = ((isize - 1) >> PAGE_CACHE_SHIFT);
  256. /*
  257. * Preallocate as many pages as we will need.
  258. */
  259. read_lock_irq(&mapping->tree_lock);
  260. for (page_idx = 0; page_idx < nr_to_read; page_idx++) {
  261. pgoff_t page_offset = offset + page_idx;
  262. if (page_offset > end_index)
  263. break;
  264. page = radix_tree_lookup(&mapping->page_tree, page_offset);
  265. if (page)
  266. continue;
  267. read_unlock_irq(&mapping->tree_lock);
  268. page = page_cache_alloc_cold(mapping);
  269. read_lock_irq(&mapping->tree_lock);
  270. if (!page)
  271. break;
  272. page->index = page_offset;
  273. list_add(&page->lru, &page_pool);
  274. ret++;
  275. }
  276. read_unlock_irq(&mapping->tree_lock);
  277. /*
  278. * Now start the IO. We ignore I/O errors - if the page is not
  279. * uptodate then the caller will launch readpage again, and
  280. * will then handle the error.
  281. */
  282. if (ret)
  283. read_pages(mapping, filp, &page_pool, ret);
  284. BUG_ON(!list_empty(&page_pool));
  285. out:
  286. return ret;
  287. }
  288. /*
  289. * Chunk the readahead into 2 megabyte units, so that we don't pin too much
  290. * memory at once.
  291. */
  292. int force_page_cache_readahead(struct address_space *mapping, struct file *filp,
  293. pgoff_t offset, unsigned long nr_to_read)
  294. {
  295. int ret = 0;
  296. if (unlikely(!mapping->a_ops->readpage && !mapping->a_ops->readpages))
  297. return -EINVAL;
  298. while (nr_to_read) {
  299. int err;
  300. unsigned long this_chunk = (2 * 1024 * 1024) / PAGE_CACHE_SIZE;
  301. if (this_chunk > nr_to_read)
  302. this_chunk = nr_to_read;
  303. err = __do_page_cache_readahead(mapping, filp,
  304. offset, this_chunk);
  305. if (err < 0) {
  306. ret = err;
  307. break;
  308. }
  309. ret += err;
  310. offset += this_chunk;
  311. nr_to_read -= this_chunk;
  312. }
  313. return ret;
  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.
  319. *
  320. */
  321. static inline int check_ra_success(struct file_ra_state *ra,
  322. unsigned long nr_to_read, unsigned long actual)
  323. {
  324. if (actual == 0) {
  325. ra->cache_hit += nr_to_read;
  326. if (ra->cache_hit >= VM_MAX_CACHE_HIT) {
  327. ra_off(ra);
  328. ra->flags |= RA_FLAG_INCACHE;
  329. return 0;
  330. }
  331. } else {
  332. ra->cache_hit=0;
  333. }
  334. return 1;
  335. }
  336. /*
  337. * This version skips the IO if the queue is read-congested, and will tell the
  338. * block layer to abandon the readahead if request allocation would block.
  339. *
  340. * force_page_cache_readahead() will ignore queue congestion and will block on
  341. * request queues.
  342. */
  343. int do_page_cache_readahead(struct address_space *mapping, struct file *filp,
  344. pgoff_t offset, unsigned long nr_to_read)
  345. {
  346. if (bdi_read_congested(mapping->backing_dev_info))
  347. return -1;
  348. return __do_page_cache_readahead(mapping, filp, offset, nr_to_read);
  349. }
  350. /*
  351. * Read 'nr_to_read' pages starting at page 'offset'. If the flag 'block'
  352. * is set wait till the read completes. Otherwise attempt to read without
  353. * blocking.
  354. * Returns 1 meaning 'success' if read is successful without switching off
  355. * readahead mode. Otherwise return failure.
  356. */
  357. static int
  358. blockable_page_cache_readahead(struct address_space *mapping, struct file *filp,
  359. pgoff_t offset, unsigned long nr_to_read,
  360. struct file_ra_state *ra, int block)
  361. {
  362. int actual;
  363. if (!block && bdi_read_congested(mapping->backing_dev_info))
  364. return 0;
  365. actual = __do_page_cache_readahead(mapping, filp, offset, nr_to_read);
  366. return check_ra_success(ra, nr_to_read, actual);
  367. }
  368. static int make_ahead_window(struct address_space *mapping, struct file *filp,
  369. struct file_ra_state *ra, int force)
  370. {
  371. int block, ret;
  372. ra->ahead_size = get_next_ra_size(ra);
  373. ra->ahead_start = ra->start + ra->size;
  374. block = force || (ra->prev_page >= ra->ahead_start);
  375. ret = blockable_page_cache_readahead(mapping, filp,
  376. ra->ahead_start, ra->ahead_size, ra, block);
  377. if (!ret && !force) {
  378. /* A read failure in blocking mode, implies pages are
  379. * all cached. So we can safely assume we have taken
  380. * care of all the pages requested in this call.
  381. * A read failure in non-blocking mode, implies we are
  382. * reading more pages than requested in this call. So
  383. * we safely assume we have taken care of all the pages
  384. * requested in this call.
  385. *
  386. * Just reset the ahead window in case we failed due to
  387. * congestion. The ahead window will any way be closed
  388. * in case we failed due to excessive page cache hits.
  389. */
  390. reset_ahead_window(ra);
  391. }
  392. return ret;
  393. }
  394. /**
  395. * page_cache_readahead - generic adaptive readahead
  396. * @mapping: address_space which holds the pagecache and I/O vectors
  397. * @ra: file_ra_state which holds the readahead state
  398. * @filp: passed on to ->readpage() and ->readpages()
  399. * @offset: start offset into @mapping, in PAGE_CACHE_SIZE units
  400. * @req_size: hint: total size of the read which the caller is performing in
  401. * PAGE_CACHE_SIZE units
  402. *
  403. * page_cache_readahead() is the main function. If performs the adaptive
  404. * readahead window size management and submits the readahead I/O.
  405. *
  406. * Note that @filp is purely used for passing on to the ->readpage[s]()
  407. * handler: it may refer to a different file from @mapping (so we may not use
  408. * @filp->f_mapping or @filp->f_path.dentry->d_inode here).
  409. * Also, @ra may not be equal to &@filp->f_ra.
  410. *
  411. */
  412. unsigned long
  413. page_cache_readahead(struct address_space *mapping, struct file_ra_state *ra,
  414. struct file *filp, pgoff_t offset, unsigned long req_size)
  415. {
  416. unsigned long max, newsize;
  417. int sequential;
  418. /*
  419. * We avoid doing extra work and bogusly perturbing the readahead
  420. * window expansion logic.
  421. */
  422. if (offset == ra->prev_page && --req_size)
  423. ++offset;
  424. /* Note that prev_page == -1 if it is a first read */
  425. sequential = (offset == ra->prev_page + 1);
  426. ra->prev_page = offset;
  427. max = get_max_readahead(ra);
  428. newsize = min(req_size, max);
  429. /* No readahead or sub-page sized read or file already in cache */
  430. if (newsize == 0 || (ra->flags & RA_FLAG_INCACHE))
  431. goto out;
  432. ra->prev_page += newsize - 1;
  433. /*
  434. * Special case - first read at start of file. We'll assume it's
  435. * a whole-file read and grow the window fast. Or detect first
  436. * sequential access
  437. */
  438. if (sequential && ra->size == 0) {
  439. ra->size = get_init_ra_size(newsize, max);
  440. ra->start = offset;
  441. if (!blockable_page_cache_readahead(mapping, filp, offset,
  442. ra->size, ra, 1))
  443. goto out;
  444. /*
  445. * If the request size is larger than our max readahead, we
  446. * at least want to be sure that we get 2 IOs in flight and
  447. * we know that we will definitly need the new I/O.
  448. * once we do this, subsequent calls should be able to overlap
  449. * IOs,* thus preventing stalls. so issue the ahead window
  450. * immediately.
  451. */
  452. if (req_size >= max)
  453. make_ahead_window(mapping, filp, ra, 1);
  454. goto out;
  455. }
  456. /*
  457. * Now handle the random case:
  458. * partial page reads and first access were handled above,
  459. * so this must be the next page otherwise it is random
  460. */
  461. if (!sequential) {
  462. ra_off(ra);
  463. blockable_page_cache_readahead(mapping, filp, offset,
  464. newsize, ra, 1);
  465. goto out;
  466. }
  467. /*
  468. * If we get here we are doing sequential IO and this was not the first
  469. * occurence (ie we have an existing window)
  470. */
  471. if (ra->ahead_start == 0) { /* no ahead window yet */
  472. if (!make_ahead_window(mapping, filp, ra, 0))
  473. goto recheck;
  474. }
  475. /*
  476. * Already have an ahead window, check if we crossed into it.
  477. * If so, shift windows and issue a new ahead window.
  478. * Only return the #pages that are in the current window, so that
  479. * we get called back on the first page of the ahead window which
  480. * will allow us to submit more IO.
  481. */
  482. if (ra->prev_page >= ra->ahead_start) {
  483. ra->start = ra->ahead_start;
  484. ra->size = ra->ahead_size;
  485. make_ahead_window(mapping, filp, ra, 0);
  486. recheck:
  487. /* prev_page shouldn't overrun the ahead window */
  488. ra->prev_page = min(ra->prev_page,
  489. ra->ahead_start + ra->ahead_size - 1);
  490. }
  491. out:
  492. return ra->prev_page + 1;
  493. }
  494. EXPORT_SYMBOL_GPL(page_cache_readahead);
  495. /*
  496. * handle_ra_miss() is called when it is known that a page which should have
  497. * been present in the pagecache (we just did some readahead there) was in fact
  498. * not found. This will happen if it was evicted by the VM (readahead
  499. * thrashing)
  500. *
  501. * Turn on the cache miss flag in the RA struct, this will cause the RA code
  502. * to reduce the RA size on the next read.
  503. */
  504. void handle_ra_miss(struct address_space *mapping,
  505. struct file_ra_state *ra, pgoff_t offset)
  506. {
  507. ra->flags |= RA_FLAG_MISS;
  508. ra->flags &= ~RA_FLAG_INCACHE;
  509. ra->cache_hit = 0;
  510. }
  511. /*
  512. * Given a desired number of PAGE_CACHE_SIZE readahead pages, return a
  513. * sensible upper limit.
  514. */
  515. unsigned long max_sane_readahead(unsigned long nr)
  516. {
  517. return min(nr, (node_page_state(numa_node_id(), NR_INACTIVE)
  518. + node_page_state(numa_node_id(), NR_FREE_PAGES)) / 2);
  519. }