readahead.c 16 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601
  1. /*
  2. * mm/readahead.c - address_space-level file readahead.
  3. *
  4. * Copyright (C) 2002, Linus Torvalds
  5. *
  6. * 09Apr2002 Andrew Morton
  7. * Initial version.
  8. */
  9. #include <linux/kernel.h>
  10. #include <linux/fs.h>
  11. #include <linux/gfp.h>
  12. #include <linux/mm.h>
  13. #include <linux/export.h>
  14. #include <linux/blkdev.h>
  15. #include <linux/backing-dev.h>
  16. #include <linux/task_io_accounting_ops.h>
  17. #include <linux/pagevec.h>
  18. #include <linux/pagemap.h>
  19. #include <linux/syscalls.h>
  20. #include <linux/file.h>
  21. /*
  22. * Initialise a struct file's readahead state. Assumes that the caller has
  23. * memset *ra to zero.
  24. */
  25. void
  26. file_ra_state_init(struct file_ra_state *ra, struct address_space *mapping)
  27. {
  28. ra->ra_pages = mapping->backing_dev_info->ra_pages;
  29. ra->prev_pos = -1;
  30. }
  31. EXPORT_SYMBOL_GPL(file_ra_state_init);
  32. #define list_to_page(head) (list_entry((head)->prev, struct page, lru))
  33. /*
  34. * see if a page needs releasing upon read_cache_pages() failure
  35. * - the caller of read_cache_pages() may have set PG_private or PG_fscache
  36. * before calling, such as the NFS fs marking pages that are cached locally
  37. * on disk, thus we need to give the fs a chance to clean up in the event of
  38. * an error
  39. */
  40. static void read_cache_pages_invalidate_page(struct address_space *mapping,
  41. struct page *page)
  42. {
  43. if (page_has_private(page)) {
  44. if (!trylock_page(page))
  45. BUG();
  46. page->mapping = mapping;
  47. do_invalidatepage(page, 0, PAGE_CACHE_SIZE);
  48. page->mapping = NULL;
  49. unlock_page(page);
  50. }
  51. page_cache_release(page);
  52. }
  53. /*
  54. * release a list of pages, invalidating them first if need be
  55. */
  56. static void read_cache_pages_invalidate_pages(struct address_space *mapping,
  57. struct list_head *pages)
  58. {
  59. struct page *victim;
  60. while (!list_empty(pages)) {
  61. victim = list_to_page(pages);
  62. list_del(&victim->lru);
  63. read_cache_pages_invalidate_page(mapping, victim);
  64. }
  65. }
  66. /**
  67. * read_cache_pages - populate an address space with some pages & start reads against them
  68. * @mapping: the address_space
  69. * @pages: The address of a list_head which contains the target pages. These
  70. * pages have their ->index populated and are otherwise uninitialised.
  71. * @filler: callback routine for filling a single page.
  72. * @data: private data for the callback routine.
  73. *
  74. * Hides the details of the LRU cache etc from the filesystems.
  75. */
  76. int read_cache_pages(struct address_space *mapping, struct list_head *pages,
  77. int (*filler)(void *, struct page *), void *data)
  78. {
  79. struct page *page;
  80. int ret = 0;
  81. while (!list_empty(pages)) {
  82. page = list_to_page(pages);
  83. list_del(&page->lru);
  84. if (add_to_page_cache_lru(page, mapping,
  85. page->index, GFP_KERNEL)) {
  86. read_cache_pages_invalidate_page(mapping, page);
  87. continue;
  88. }
  89. page_cache_release(page);
  90. ret = filler(data, page);
  91. if (unlikely(ret)) {
  92. read_cache_pages_invalidate_pages(mapping, pages);
  93. break;
  94. }
  95. task_io_account_read(PAGE_CACHE_SIZE);
  96. }
  97. return ret;
  98. }
  99. EXPORT_SYMBOL(read_cache_pages);
  100. static int read_pages(struct address_space *mapping, struct file *filp,
  101. struct list_head *pages, unsigned nr_pages)
  102. {
  103. struct blk_plug plug;
  104. unsigned page_idx;
  105. int ret;
  106. blk_start_plug(&plug);
  107. if (mapping->a_ops->readpages) {
  108. ret = mapping->a_ops->readpages(filp, mapping, pages, nr_pages);
  109. /* Clean up the remaining pages */
  110. put_pages_list(pages);
  111. goto out;
  112. }
  113. for (page_idx = 0; page_idx < nr_pages; page_idx++) {
  114. struct page *page = list_to_page(pages);
  115. list_del(&page->lru);
  116. if (!add_to_page_cache_lru(page, mapping,
  117. page->index, GFP_KERNEL)) {
  118. mapping->a_ops->readpage(filp, page);
  119. }
  120. page_cache_release(page);
  121. }
  122. ret = 0;
  123. out:
  124. blk_finish_plug(&plug);
  125. return ret;
  126. }
  127. /*
  128. * __do_page_cache_readahead() actually reads a chunk of disk. It allocates all
  129. * the pages first, then submits them all for I/O. This avoids the very bad
  130. * behaviour which would occur if page allocations are causing VM writeback.
  131. * We really don't want to intermingle reads and writes like that.
  132. *
  133. * Returns the number of pages requested, or the maximum amount of I/O allowed.
  134. */
  135. static int
  136. __do_page_cache_readahead(struct address_space *mapping, struct file *filp,
  137. pgoff_t offset, unsigned long nr_to_read,
  138. unsigned long lookahead_size)
  139. {
  140. struct inode *inode = mapping->host;
  141. struct page *page;
  142. unsigned long end_index; /* The last page we want to read */
  143. LIST_HEAD(page_pool);
  144. int page_idx;
  145. int ret = 0;
  146. loff_t isize = i_size_read(inode);
  147. if (isize == 0)
  148. goto out;
  149. end_index = ((isize - 1) >> PAGE_CACHE_SHIFT);
  150. /*
  151. * Preallocate as many pages as we will need.
  152. */
  153. for (page_idx = 0; page_idx < nr_to_read; page_idx++) {
  154. pgoff_t page_offset = offset + page_idx;
  155. if (page_offset > end_index)
  156. break;
  157. rcu_read_lock();
  158. page = radix_tree_lookup(&mapping->page_tree, page_offset);
  159. rcu_read_unlock();
  160. if (page)
  161. continue;
  162. page = page_cache_alloc_readahead(mapping);
  163. if (!page)
  164. break;
  165. page->index = page_offset;
  166. list_add(&page->lru, &page_pool);
  167. if (page_idx == nr_to_read - lookahead_size)
  168. SetPageReadahead(page);
  169. ret++;
  170. }
  171. /*
  172. * Now start the IO. We ignore I/O errors - if the page is not
  173. * uptodate then the caller will launch readpage again, and
  174. * will then handle the error.
  175. */
  176. if (ret)
  177. read_pages(mapping, filp, &page_pool, ret);
  178. BUG_ON(!list_empty(&page_pool));
  179. out:
  180. return ret;
  181. }
  182. /*
  183. * Chunk the readahead into 2 megabyte units, so that we don't pin too much
  184. * memory at once.
  185. */
  186. int force_page_cache_readahead(struct address_space *mapping, struct file *filp,
  187. pgoff_t offset, unsigned long nr_to_read)
  188. {
  189. int ret = 0;
  190. if (unlikely(!mapping->a_ops->readpage && !mapping->a_ops->readpages))
  191. return -EINVAL;
  192. nr_to_read = max_sane_readahead(nr_to_read);
  193. while (nr_to_read) {
  194. int err;
  195. unsigned long this_chunk = (2 * 1024 * 1024) / PAGE_CACHE_SIZE;
  196. if (this_chunk > nr_to_read)
  197. this_chunk = nr_to_read;
  198. err = __do_page_cache_readahead(mapping, filp,
  199. offset, this_chunk, 0);
  200. if (err < 0) {
  201. ret = err;
  202. break;
  203. }
  204. ret += err;
  205. offset += this_chunk;
  206. nr_to_read -= this_chunk;
  207. }
  208. return ret;
  209. }
  210. /*
  211. * Given a desired number of PAGE_CACHE_SIZE readahead pages, return a
  212. * sensible upper limit.
  213. */
  214. unsigned long max_sane_readahead(unsigned long nr)
  215. {
  216. return min(nr, (node_page_state(numa_node_id(), NR_INACTIVE_FILE)
  217. + node_page_state(numa_node_id(), NR_FREE_PAGES)) / 2);
  218. }
  219. /*
  220. * Submit IO for the read-ahead request in file_ra_state.
  221. */
  222. unsigned long ra_submit(struct file_ra_state *ra,
  223. struct address_space *mapping, struct file *filp)
  224. {
  225. int actual;
  226. actual = __do_page_cache_readahead(mapping, filp,
  227. ra->start, ra->size, ra->async_size);
  228. return actual;
  229. }
  230. /*
  231. * Set the initial window size, round to next power of 2 and square
  232. * for small size, x 4 for medium, and x 2 for large
  233. * for 128k (32 page) max ra
  234. * 1-8 page = 32k initial, > 8 page = 128k initial
  235. */
  236. static unsigned long get_init_ra_size(unsigned long size, unsigned long max)
  237. {
  238. unsigned long newsize = roundup_pow_of_two(size);
  239. if (newsize <= max / 32)
  240. newsize = newsize * 4;
  241. else if (newsize <= max / 4)
  242. newsize = newsize * 2;
  243. else
  244. newsize = max;
  245. return newsize;
  246. }
  247. /*
  248. * Get the previous window size, ramp it up, and
  249. * return it as the new window size.
  250. */
  251. static unsigned long get_next_ra_size(struct file_ra_state *ra,
  252. unsigned long max)
  253. {
  254. unsigned long cur = ra->size;
  255. unsigned long newsize;
  256. if (cur < max / 16)
  257. newsize = 4 * cur;
  258. else
  259. newsize = 2 * cur;
  260. return min(newsize, max);
  261. }
  262. /*
  263. * On-demand readahead design.
  264. *
  265. * The fields in struct file_ra_state represent the most-recently-executed
  266. * readahead attempt:
  267. *
  268. * |<----- async_size ---------|
  269. * |------------------- size -------------------->|
  270. * |==================#===========================|
  271. * ^start ^page marked with PG_readahead
  272. *
  273. * To overlap application thinking time and disk I/O time, we do
  274. * `readahead pipelining': Do not wait until the application consumed all
  275. * readahead pages and stalled on the missing page at readahead_index;
  276. * Instead, submit an asynchronous readahead I/O as soon as there are
  277. * only async_size pages left in the readahead window. Normally async_size
  278. * will be equal to size, for maximum pipelining.
  279. *
  280. * In interleaved sequential reads, concurrent streams on the same fd can
  281. * be invalidating each other's readahead state. So we flag the new readahead
  282. * page at (start+size-async_size) with PG_readahead, and use it as readahead
  283. * indicator. The flag won't be set on already cached pages, to avoid the
  284. * readahead-for-nothing fuss, saving pointless page cache lookups.
  285. *
  286. * prev_pos tracks the last visited byte in the _previous_ read request.
  287. * It should be maintained by the caller, and will be used for detecting
  288. * small random reads. Note that the readahead algorithm checks loosely
  289. * for sequential patterns. Hence interleaved reads might be served as
  290. * sequential ones.
  291. *
  292. * There is a special-case: if the first page which the application tries to
  293. * read happens to be the first page of the file, it is assumed that a linear
  294. * read is about to happen and the window is immediately set to the initial size
  295. * based on I/O request size and the max_readahead.
  296. *
  297. * The code ramps up the readahead size aggressively at first, but slow down as
  298. * it approaches max_readhead.
  299. */
  300. /*
  301. * Count contiguously cached pages from @offset-1 to @offset-@max,
  302. * this count is a conservative estimation of
  303. * - length of the sequential read sequence, or
  304. * - thrashing threshold in memory tight systems
  305. */
  306. static pgoff_t count_history_pages(struct address_space *mapping,
  307. struct file_ra_state *ra,
  308. pgoff_t offset, unsigned long max)
  309. {
  310. pgoff_t head;
  311. rcu_read_lock();
  312. head = radix_tree_prev_hole(&mapping->page_tree, offset - 1, max);
  313. rcu_read_unlock();
  314. return offset - 1 - head;
  315. }
  316. /*
  317. * page cache context based read-ahead
  318. */
  319. static int try_context_readahead(struct address_space *mapping,
  320. struct file_ra_state *ra,
  321. pgoff_t offset,
  322. unsigned long req_size,
  323. unsigned long max)
  324. {
  325. pgoff_t size;
  326. size = count_history_pages(mapping, ra, offset, max);
  327. /*
  328. * not enough history pages:
  329. * it could be a random read
  330. */
  331. if (size <= req_size)
  332. return 0;
  333. /*
  334. * starts from beginning of file:
  335. * it is a strong indication of long-run stream (or whole-file-read)
  336. */
  337. if (size >= offset)
  338. size *= 2;
  339. ra->start = offset;
  340. ra->size = min(size + req_size, max);
  341. ra->async_size = 1;
  342. return 1;
  343. }
  344. /*
  345. * A minimal readahead algorithm for trivial sequential/random reads.
  346. */
  347. static unsigned long
  348. ondemand_readahead(struct address_space *mapping,
  349. struct file_ra_state *ra, struct file *filp,
  350. bool hit_readahead_marker, pgoff_t offset,
  351. unsigned long req_size)
  352. {
  353. unsigned long max = max_sane_readahead(ra->ra_pages);
  354. pgoff_t prev_offset;
  355. /*
  356. * start of file
  357. */
  358. if (!offset)
  359. goto initial_readahead;
  360. /*
  361. * It's the expected callback offset, assume sequential access.
  362. * Ramp up sizes, and push forward the readahead window.
  363. */
  364. if ((offset == (ra->start + ra->size - ra->async_size) ||
  365. offset == (ra->start + ra->size))) {
  366. ra->start += ra->size;
  367. ra->size = get_next_ra_size(ra, max);
  368. ra->async_size = ra->size;
  369. goto readit;
  370. }
  371. /*
  372. * Hit a marked page without valid readahead state.
  373. * E.g. interleaved reads.
  374. * Query the pagecache for async_size, which normally equals to
  375. * readahead size. Ramp it up and use it as the new readahead size.
  376. */
  377. if (hit_readahead_marker) {
  378. pgoff_t start;
  379. rcu_read_lock();
  380. start = radix_tree_next_hole(&mapping->page_tree, offset+1,max);
  381. rcu_read_unlock();
  382. if (!start || start - offset > max)
  383. return 0;
  384. ra->start = start;
  385. ra->size = start - offset; /* old async_size */
  386. ra->size += req_size;
  387. ra->size = get_next_ra_size(ra, max);
  388. ra->async_size = ra->size;
  389. goto readit;
  390. }
  391. /*
  392. * oversize read
  393. */
  394. if (req_size > max)
  395. goto initial_readahead;
  396. /*
  397. * sequential cache miss
  398. * trivial case: (offset - prev_offset) == 1
  399. * unaligned reads: (offset - prev_offset) == 0
  400. */
  401. prev_offset = (unsigned long long)ra->prev_pos >> PAGE_CACHE_SHIFT;
  402. if (offset - prev_offset <= 1UL)
  403. goto initial_readahead;
  404. /*
  405. * Query the page cache and look for the traces(cached history pages)
  406. * that a sequential stream would leave behind.
  407. */
  408. if (try_context_readahead(mapping, ra, offset, req_size, max))
  409. goto readit;
  410. /*
  411. * standalone, small random read
  412. * Read as is, and do not pollute the readahead state.
  413. */
  414. return __do_page_cache_readahead(mapping, filp, offset, req_size, 0);
  415. initial_readahead:
  416. ra->start = offset;
  417. ra->size = get_init_ra_size(req_size, max);
  418. ra->async_size = ra->size > req_size ? ra->size - req_size : ra->size;
  419. readit:
  420. /*
  421. * Will this read hit the readahead marker made by itself?
  422. * If so, trigger the readahead marker hit now, and merge
  423. * the resulted next readahead window into the current one.
  424. */
  425. if (offset == ra->start && ra->size == ra->async_size) {
  426. ra->async_size = get_next_ra_size(ra, max);
  427. ra->size += ra->async_size;
  428. }
  429. return ra_submit(ra, mapping, filp);
  430. }
  431. /**
  432. * page_cache_sync_readahead - generic file readahead
  433. * @mapping: address_space which holds the pagecache and I/O vectors
  434. * @ra: file_ra_state which holds the readahead state
  435. * @filp: passed on to ->readpage() and ->readpages()
  436. * @offset: start offset into @mapping, in pagecache page-sized units
  437. * @req_size: hint: total size of the read which the caller is performing in
  438. * pagecache pages
  439. *
  440. * page_cache_sync_readahead() should be called when a cache miss happened:
  441. * it will submit the read. The readahead logic may decide to piggyback more
  442. * pages onto the read request if access patterns suggest it will improve
  443. * performance.
  444. */
  445. void page_cache_sync_readahead(struct address_space *mapping,
  446. struct file_ra_state *ra, struct file *filp,
  447. pgoff_t offset, unsigned long req_size)
  448. {
  449. /* no read-ahead */
  450. if (!ra->ra_pages)
  451. return;
  452. /* be dumb */
  453. if (filp && (filp->f_mode & FMODE_RANDOM)) {
  454. force_page_cache_readahead(mapping, filp, offset, req_size);
  455. return;
  456. }
  457. /* do read-ahead */
  458. ondemand_readahead(mapping, ra, filp, false, offset, req_size);
  459. }
  460. EXPORT_SYMBOL_GPL(page_cache_sync_readahead);
  461. /**
  462. * page_cache_async_readahead - file readahead for marked pages
  463. * @mapping: address_space which holds the pagecache and I/O vectors
  464. * @ra: file_ra_state which holds the readahead state
  465. * @filp: passed on to ->readpage() and ->readpages()
  466. * @page: the page at @offset which has the PG_readahead flag set
  467. * @offset: start offset into @mapping, in pagecache page-sized units
  468. * @req_size: hint: total size of the read which the caller is performing in
  469. * pagecache pages
  470. *
  471. * page_cache_async_readahead() should be called when a page is used which
  472. * has the PG_readahead flag; this is a marker to suggest that the application
  473. * has used up enough of the readahead window that we should start pulling in
  474. * more pages.
  475. */
  476. void
  477. page_cache_async_readahead(struct address_space *mapping,
  478. struct file_ra_state *ra, struct file *filp,
  479. struct page *page, pgoff_t offset,
  480. unsigned long req_size)
  481. {
  482. /* no read-ahead */
  483. if (!ra->ra_pages)
  484. return;
  485. /*
  486. * Same bit is used for PG_readahead and PG_reclaim.
  487. */
  488. if (PageWriteback(page))
  489. return;
  490. ClearPageReadahead(page);
  491. /*
  492. * Defer asynchronous read-ahead on IO congestion.
  493. */
  494. if (bdi_read_congested(mapping->backing_dev_info))
  495. return;
  496. /* do read-ahead */
  497. ondemand_readahead(mapping, ra, filp, true, offset, req_size);
  498. }
  499. EXPORT_SYMBOL_GPL(page_cache_async_readahead);
  500. static ssize_t
  501. do_readahead(struct address_space *mapping, struct file *filp,
  502. pgoff_t index, unsigned long nr)
  503. {
  504. if (!mapping || !mapping->a_ops)
  505. return -EINVAL;
  506. force_page_cache_readahead(mapping, filp, index, nr);
  507. return 0;
  508. }
  509. SYSCALL_DEFINE3(readahead, int, fd, loff_t, offset, size_t, count)
  510. {
  511. ssize_t ret;
  512. struct fd f;
  513. ret = -EBADF;
  514. f = fdget(fd);
  515. if (f.file) {
  516. if (f.file->f_mode & FMODE_READ) {
  517. struct address_space *mapping = f.file->f_mapping;
  518. pgoff_t start = offset >> PAGE_CACHE_SHIFT;
  519. pgoff_t end = (offset + count - 1) >> PAGE_CACHE_SHIFT;
  520. unsigned long len = end - start + 1;
  521. ret = do_readahead(mapping, f.file, start, len);
  522. }
  523. fdput(f);
  524. }
  525. return ret;
  526. }