readahead.c 18 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652
  1. // SPDX-License-Identifier: GPL-2.0-only
  2. /*
  3. * mm/readahead.c - address_space-level file readahead.
  4. *
  5. * Copyright (C) 2002, Linus Torvalds
  6. *
  7. * 09Apr2002 Andrew Morton
  8. * Initial version.
  9. */
  10. #include <linux/kernel.h>
  11. #include <linux/dax.h>
  12. #include <linux/gfp.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. #include <linux/mm_inline.h>
  22. #include <linux/blk-cgroup.h>
  23. #include <linux/fadvise.h>
  24. #include <linux/sched/mm.h>
  25. #include <trace/hooks/mm.h>
  26. #include "internal.h"
  27. /*
  28. * Initialise a struct file's readahead state. Assumes that the caller has
  29. * memset *ra to zero.
  30. */
  31. void
  32. file_ra_state_init(struct file_ra_state *ra, struct address_space *mapping)
  33. {
  34. ra->ra_pages = inode_to_bdi(mapping->host)->ra_pages;
  35. ra->prev_pos = -1;
  36. }
  37. EXPORT_SYMBOL_GPL(file_ra_state_init);
  38. /*
  39. * see if a page needs releasing upon read_cache_pages() failure
  40. * - the caller of read_cache_pages() may have set PG_private or PG_fscache
  41. * before calling, such as the NFS fs marking pages that are cached locally
  42. * on disk, thus we need to give the fs a chance to clean up in the event of
  43. * an error
  44. */
  45. static void read_cache_pages_invalidate_page(struct address_space *mapping,
  46. struct page *page)
  47. {
  48. if (page_has_private(page)) {
  49. if (!trylock_page(page))
  50. BUG();
  51. page->mapping = mapping;
  52. do_invalidatepage(page, 0, PAGE_SIZE);
  53. page->mapping = NULL;
  54. unlock_page(page);
  55. }
  56. put_page(page);
  57. }
  58. /*
  59. * release a list of pages, invalidating them first if need be
  60. */
  61. static void read_cache_pages_invalidate_pages(struct address_space *mapping,
  62. struct list_head *pages)
  63. {
  64. struct page *victim;
  65. while (!list_empty(pages)) {
  66. victim = lru_to_page(pages);
  67. list_del(&victim->lru);
  68. read_cache_pages_invalidate_page(mapping, victim);
  69. }
  70. }
  71. /**
  72. * read_cache_pages - populate an address space with some pages & start reads against them
  73. * @mapping: the address_space
  74. * @pages: The address of a list_head which contains the target pages. These
  75. * pages have their ->index populated and are otherwise uninitialised.
  76. * @filler: callback routine for filling a single page.
  77. * @data: private data for the callback routine.
  78. *
  79. * Hides the details of the LRU cache etc from the filesystems.
  80. *
  81. * Returns: %0 on success, error return by @filler otherwise
  82. */
  83. int read_cache_pages(struct address_space *mapping, struct list_head *pages,
  84. int (*filler)(void *, struct page *), void *data)
  85. {
  86. struct page *page;
  87. int ret = 0;
  88. while (!list_empty(pages)) {
  89. page = lru_to_page(pages);
  90. list_del(&page->lru);
  91. if (add_to_page_cache_lru(page, mapping, page->index,
  92. readahead_gfp_mask(mapping))) {
  93. read_cache_pages_invalidate_page(mapping, page);
  94. continue;
  95. }
  96. put_page(page);
  97. ret = filler(data, page);
  98. if (unlikely(ret)) {
  99. read_cache_pages_invalidate_pages(mapping, pages);
  100. break;
  101. }
  102. task_io_account_read(PAGE_SIZE);
  103. }
  104. return ret;
  105. }
  106. EXPORT_SYMBOL(read_cache_pages);
  107. gfp_t readahead_gfp_mask(struct address_space *x)
  108. {
  109. gfp_t mask = mapping_gfp_mask(x) | __GFP_NORETRY | __GFP_NOWARN;
  110. trace_android_rvh_set_readahead_gfp_mask(&mask);
  111. return mask;
  112. }
  113. EXPORT_SYMBOL_GPL(readahead_gfp_mask);
  114. static void read_pages(struct readahead_control *rac, struct list_head *pages,
  115. bool skip_page)
  116. {
  117. const struct address_space_operations *aops = rac->mapping->a_ops;
  118. struct page *page;
  119. struct blk_plug plug;
  120. if (!readahead_count(rac))
  121. goto out;
  122. blk_start_plug(&plug);
  123. if (aops->readahead) {
  124. aops->readahead(rac);
  125. /* Clean up the remaining pages */
  126. while ((page = readahead_page(rac))) {
  127. unlock_page(page);
  128. put_page(page);
  129. }
  130. } else if (aops->readpages) {
  131. aops->readpages(rac->file, rac->mapping, pages,
  132. readahead_count(rac));
  133. /* Clean up the remaining pages */
  134. put_pages_list(pages);
  135. rac->_index += rac->_nr_pages;
  136. rac->_nr_pages = 0;
  137. } else {
  138. while ((page = readahead_page(rac))) {
  139. aops->readpage(rac->file, page);
  140. put_page(page);
  141. }
  142. }
  143. blk_finish_plug(&plug);
  144. BUG_ON(!list_empty(pages));
  145. BUG_ON(readahead_count(rac));
  146. out:
  147. if (skip_page)
  148. rac->_index++;
  149. }
  150. /**
  151. * page_cache_ra_unbounded - Start unchecked readahead.
  152. * @ractl: Readahead control.
  153. * @nr_to_read: The number of pages to read.
  154. * @lookahead_size: Where to start the next readahead.
  155. *
  156. * This function is for filesystems to call when they want to start
  157. * readahead beyond a file's stated i_size. This is almost certainly
  158. * not the function you want to call. Use page_cache_async_readahead()
  159. * or page_cache_sync_readahead() instead.
  160. *
  161. * Context: File is referenced by caller. Mutexes may be held by caller.
  162. * May sleep, but will not reenter filesystem to reclaim memory.
  163. */
  164. void page_cache_ra_unbounded(struct readahead_control *ractl,
  165. unsigned long nr_to_read, unsigned long lookahead_size)
  166. {
  167. struct address_space *mapping = ractl->mapping;
  168. unsigned long index = readahead_index(ractl);
  169. LIST_HEAD(page_pool);
  170. gfp_t gfp_mask = readahead_gfp_mask(mapping);
  171. unsigned long i;
  172. /*
  173. * Partway through the readahead operation, we will have added
  174. * locked pages to the page cache, but will not yet have submitted
  175. * them for I/O. Adding another page may need to allocate memory,
  176. * which can trigger memory reclaim. Telling the VM we're in
  177. * the middle of a filesystem operation will cause it to not
  178. * touch file-backed pages, preventing a deadlock. Most (all?)
  179. * filesystems already specify __GFP_NOFS in their mapping's
  180. * gfp_mask, but let's be explicit here.
  181. */
  182. unsigned int nofs = memalloc_nofs_save();
  183. /*
  184. * Preallocate as many pages as we will need.
  185. */
  186. for (i = 0; i < nr_to_read; i++) {
  187. struct page *page = xa_load(&mapping->i_pages, index + i);
  188. BUG_ON(index + i != ractl->_index + ractl->_nr_pages);
  189. if (page && !xa_is_value(page)) {
  190. /*
  191. * Page already present? Kick off the current batch
  192. * of contiguous pages before continuing with the
  193. * next batch. This page may be the one we would
  194. * have intended to mark as Readahead, but we don't
  195. * have a stable reference to this page, and it's
  196. * not worth getting one just for that.
  197. */
  198. read_pages(ractl, &page_pool, true);
  199. continue;
  200. }
  201. page = __page_cache_alloc(gfp_mask);
  202. if (!page)
  203. break;
  204. if (mapping->a_ops->readpages) {
  205. page->index = index + i;
  206. list_add(&page->lru, &page_pool);
  207. } else if (add_to_page_cache_lru(page, mapping, index + i,
  208. gfp_mask) < 0) {
  209. put_page(page);
  210. read_pages(ractl, &page_pool, true);
  211. continue;
  212. }
  213. if (i == nr_to_read - lookahead_size)
  214. SetPageReadahead(page);
  215. ractl->_nr_pages++;
  216. }
  217. /*
  218. * Now start the IO. We ignore I/O errors - if the page is not
  219. * uptodate then the caller will launch readpage again, and
  220. * will then handle the error.
  221. */
  222. read_pages(ractl, &page_pool, false);
  223. memalloc_nofs_restore(nofs);
  224. }
  225. EXPORT_SYMBOL_GPL(page_cache_ra_unbounded);
  226. /*
  227. * do_page_cache_ra() actually reads a chunk of disk. It allocates
  228. * the pages first, then submits them for I/O. This avoids the very bad
  229. * behaviour which would occur if page allocations are causing VM writeback.
  230. * We really don't want to intermingle reads and writes like that.
  231. */
  232. void do_page_cache_ra(struct readahead_control *ractl,
  233. unsigned long nr_to_read, unsigned long lookahead_size)
  234. {
  235. struct inode *inode = ractl->mapping->host;
  236. unsigned long index = readahead_index(ractl);
  237. loff_t isize = i_size_read(inode);
  238. pgoff_t end_index; /* The last page we want to read */
  239. if (isize == 0)
  240. return;
  241. end_index = (isize - 1) >> PAGE_SHIFT;
  242. if (index > end_index)
  243. return;
  244. /* Don't read past the page containing the last byte of the file */
  245. if (nr_to_read > end_index - index)
  246. nr_to_read = end_index - index + 1;
  247. page_cache_ra_unbounded(ractl, nr_to_read, lookahead_size);
  248. }
  249. /*
  250. * Chunk the readahead into 2 megabyte units, so that we don't pin too much
  251. * memory at once.
  252. */
  253. void force_page_cache_ra(struct readahead_control *ractl,
  254. struct file_ra_state *ra, unsigned long nr_to_read)
  255. {
  256. struct address_space *mapping = ractl->mapping;
  257. struct backing_dev_info *bdi = inode_to_bdi(mapping->host);
  258. unsigned long max_pages, index;
  259. if (unlikely(!mapping->a_ops->readpage && !mapping->a_ops->readpages &&
  260. !mapping->a_ops->readahead))
  261. return;
  262. /*
  263. * If the request exceeds the readahead window, allow the read to
  264. * be up to the optimal hardware IO size
  265. */
  266. index = readahead_index(ractl);
  267. max_pages = max_t(unsigned long, bdi->io_pages, ra->ra_pages);
  268. nr_to_read = min_t(unsigned long, nr_to_read, max_pages);
  269. while (nr_to_read) {
  270. unsigned long this_chunk = (2 * 1024 * 1024) / PAGE_SIZE;
  271. if (this_chunk > nr_to_read)
  272. this_chunk = nr_to_read;
  273. ractl->_index = index;
  274. do_page_cache_ra(ractl, this_chunk, 0);
  275. index += this_chunk;
  276. nr_to_read -= this_chunk;
  277. }
  278. }
  279. /*
  280. * Set the initial window size, round to next power of 2 and square
  281. * for small size, x 4 for medium, and x 2 for large
  282. * for 128k (32 page) max ra
  283. * 1-8 page = 32k initial, > 8 page = 128k initial
  284. */
  285. static unsigned long get_init_ra_size(unsigned long size, unsigned long max)
  286. {
  287. unsigned long newsize = roundup_pow_of_two(size);
  288. if (newsize <= max / 32)
  289. newsize = newsize * 4;
  290. else if (newsize <= max / 4)
  291. newsize = newsize * 2;
  292. else
  293. newsize = max;
  294. return newsize;
  295. }
  296. /*
  297. * Get the previous window size, ramp it up, and
  298. * return it as the new window size.
  299. */
  300. static unsigned long get_next_ra_size(struct file_ra_state *ra,
  301. unsigned long max)
  302. {
  303. unsigned long cur = ra->size;
  304. if (cur < max / 16)
  305. return 4 * cur;
  306. if (cur <= max / 2)
  307. return 2 * cur;
  308. return max;
  309. }
  310. /*
  311. * On-demand readahead design.
  312. *
  313. * The fields in struct file_ra_state represent the most-recently-executed
  314. * readahead attempt:
  315. *
  316. * |<----- async_size ---------|
  317. * |------------------- size -------------------->|
  318. * |==================#===========================|
  319. * ^start ^page marked with PG_readahead
  320. *
  321. * To overlap application thinking time and disk I/O time, we do
  322. * `readahead pipelining': Do not wait until the application consumed all
  323. * readahead pages and stalled on the missing page at readahead_index;
  324. * Instead, submit an asynchronous readahead I/O as soon as there are
  325. * only async_size pages left in the readahead window. Normally async_size
  326. * will be equal to size, for maximum pipelining.
  327. *
  328. * In interleaved sequential reads, concurrent streams on the same fd can
  329. * be invalidating each other's readahead state. So we flag the new readahead
  330. * page at (start+size-async_size) with PG_readahead, and use it as readahead
  331. * indicator. The flag won't be set on already cached pages, to avoid the
  332. * readahead-for-nothing fuss, saving pointless page cache lookups.
  333. *
  334. * prev_pos tracks the last visited byte in the _previous_ read request.
  335. * It should be maintained by the caller, and will be used for detecting
  336. * small random reads. Note that the readahead algorithm checks loosely
  337. * for sequential patterns. Hence interleaved reads might be served as
  338. * sequential ones.
  339. *
  340. * There is a special-case: if the first page which the application tries to
  341. * read happens to be the first page of the file, it is assumed that a linear
  342. * read is about to happen and the window is immediately set to the initial size
  343. * based on I/O request size and the max_readahead.
  344. *
  345. * The code ramps up the readahead size aggressively at first, but slow down as
  346. * it approaches max_readhead.
  347. */
  348. /*
  349. * Count contiguously cached pages from @index-1 to @index-@max,
  350. * this count is a conservative estimation of
  351. * - length of the sequential read sequence, or
  352. * - thrashing threshold in memory tight systems
  353. */
  354. static pgoff_t count_history_pages(struct address_space *mapping,
  355. pgoff_t index, unsigned long max)
  356. {
  357. pgoff_t head;
  358. rcu_read_lock();
  359. head = page_cache_prev_miss(mapping, index - 1, max);
  360. rcu_read_unlock();
  361. return index - 1 - head;
  362. }
  363. /*
  364. * page cache context based read-ahead
  365. */
  366. static int try_context_readahead(struct address_space *mapping,
  367. struct file_ra_state *ra,
  368. pgoff_t index,
  369. unsigned long req_size,
  370. unsigned long max)
  371. {
  372. pgoff_t size;
  373. size = count_history_pages(mapping, index, max);
  374. /*
  375. * not enough history pages:
  376. * it could be a random read
  377. */
  378. if (size <= req_size)
  379. return 0;
  380. /*
  381. * starts from beginning of file:
  382. * it is a strong indication of long-run stream (or whole-file-read)
  383. */
  384. if (size >= index)
  385. size *= 2;
  386. ra->start = index;
  387. ra->size = min(size + req_size, max);
  388. ra->async_size = 1;
  389. return 1;
  390. }
  391. /*
  392. * A minimal readahead algorithm for trivial sequential/random reads.
  393. */
  394. static void ondemand_readahead(struct readahead_control *ractl,
  395. struct file_ra_state *ra, bool hit_readahead_marker,
  396. unsigned long req_size)
  397. {
  398. struct backing_dev_info *bdi = inode_to_bdi(ractl->mapping->host);
  399. unsigned long max_pages = ra->ra_pages;
  400. unsigned long add_pages;
  401. unsigned long index = readahead_index(ractl);
  402. pgoff_t prev_index;
  403. /*
  404. * If the request exceeds the readahead window, allow the read to
  405. * be up to the optimal hardware IO size
  406. */
  407. if (req_size > max_pages && bdi->io_pages > max_pages)
  408. max_pages = min(req_size, bdi->io_pages);
  409. trace_android_vh_ra_tuning_max_page(ractl, &max_pages);
  410. /*
  411. * start of file
  412. */
  413. if (!index)
  414. goto initial_readahead;
  415. /*
  416. * It's the expected callback index, assume sequential access.
  417. * Ramp up sizes, and push forward the readahead window.
  418. */
  419. if ((index == (ra->start + ra->size - ra->async_size) ||
  420. index == (ra->start + ra->size))) {
  421. ra->start += ra->size;
  422. ra->size = get_next_ra_size(ra, max_pages);
  423. ra->async_size = ra->size;
  424. goto readit;
  425. }
  426. /*
  427. * Hit a marked page without valid readahead state.
  428. * E.g. interleaved reads.
  429. * Query the pagecache for async_size, which normally equals to
  430. * readahead size. Ramp it up and use it as the new readahead size.
  431. */
  432. if (hit_readahead_marker) {
  433. pgoff_t start;
  434. rcu_read_lock();
  435. start = page_cache_next_miss(ractl->mapping, index + 1,
  436. max_pages);
  437. rcu_read_unlock();
  438. if (!start || start - index > max_pages)
  439. return;
  440. ra->start = start;
  441. ra->size = start - index; /* old async_size */
  442. ra->size += req_size;
  443. ra->size = get_next_ra_size(ra, max_pages);
  444. ra->async_size = ra->size;
  445. goto readit;
  446. }
  447. /*
  448. * oversize read
  449. */
  450. if (req_size > max_pages)
  451. goto initial_readahead;
  452. /*
  453. * sequential cache miss
  454. * trivial case: (index - prev_index) == 1
  455. * unaligned reads: (index - prev_index) == 0
  456. */
  457. prev_index = (unsigned long long)ra->prev_pos >> PAGE_SHIFT;
  458. if (index - prev_index <= 1UL)
  459. goto initial_readahead;
  460. /*
  461. * Query the page cache and look for the traces(cached history pages)
  462. * that a sequential stream would leave behind.
  463. */
  464. if (try_context_readahead(ractl->mapping, ra, index, req_size,
  465. max_pages))
  466. goto readit;
  467. /*
  468. * standalone, small random read
  469. * Read as is, and do not pollute the readahead state.
  470. */
  471. do_page_cache_ra(ractl, req_size, 0);
  472. return;
  473. initial_readahead:
  474. ra->start = index;
  475. ra->size = get_init_ra_size(req_size, max_pages);
  476. ra->async_size = ra->size > req_size ? ra->size - req_size : ra->size;
  477. readit:
  478. /*
  479. * Will this read hit the readahead marker made by itself?
  480. * If so, trigger the readahead marker hit now, and merge
  481. * the resulted next readahead window into the current one.
  482. * Take care of maximum IO pages as above.
  483. */
  484. if (index == ra->start && ra->size == ra->async_size) {
  485. add_pages = get_next_ra_size(ra, max_pages);
  486. if (ra->size + add_pages <= max_pages) {
  487. ra->async_size = add_pages;
  488. ra->size += add_pages;
  489. } else {
  490. ra->size = max_pages;
  491. ra->async_size = max_pages >> 1;
  492. }
  493. }
  494. ractl->_index = ra->start;
  495. do_page_cache_ra(ractl, ra->size, ra->async_size);
  496. }
  497. void page_cache_sync_ra(struct readahead_control *ractl,
  498. struct file_ra_state *ra, unsigned long req_count)
  499. {
  500. bool do_forced_ra = ractl->file && (ractl->file->f_mode & FMODE_RANDOM);
  501. /*
  502. * Even if read-ahead is disabled, issue this request as read-ahead
  503. * as we'll need it to satisfy the requested range. The forced
  504. * read-ahead will do the right thing and limit the read to just the
  505. * requested range, which we'll set to 1 page for this case.
  506. */
  507. if (!ra->ra_pages || blk_cgroup_congested()) {
  508. if (!ractl->file)
  509. return;
  510. req_count = 1;
  511. do_forced_ra = true;
  512. }
  513. /* be dumb */
  514. if (do_forced_ra) {
  515. force_page_cache_ra(ractl, ra, req_count);
  516. return;
  517. }
  518. /* do read-ahead */
  519. ondemand_readahead(ractl, ra, false, req_count);
  520. }
  521. EXPORT_SYMBOL_GPL(page_cache_sync_ra);
  522. void page_cache_async_ra(struct readahead_control *ractl,
  523. struct file_ra_state *ra, struct page *page,
  524. unsigned long req_count)
  525. {
  526. /* no read-ahead */
  527. if (!ra->ra_pages)
  528. return;
  529. /*
  530. * Same bit is used for PG_readahead and PG_reclaim.
  531. */
  532. if (PageWriteback(page))
  533. return;
  534. ClearPageReadahead(page);
  535. /*
  536. * Defer asynchronous read-ahead on IO congestion.
  537. */
  538. if (inode_read_congested(ractl->mapping->host))
  539. return;
  540. if (blk_cgroup_congested())
  541. return;
  542. /* do read-ahead */
  543. ondemand_readahead(ractl, ra, true, req_count);
  544. }
  545. EXPORT_SYMBOL_GPL(page_cache_async_ra);
  546. ssize_t ksys_readahead(int fd, loff_t offset, size_t count)
  547. {
  548. ssize_t ret;
  549. struct fd f;
  550. ret = -EBADF;
  551. f = fdget(fd);
  552. if (!f.file || !(f.file->f_mode & FMODE_READ))
  553. goto out;
  554. /*
  555. * The readahead() syscall is intended to run only on files
  556. * that can execute readahead. If readahead is not possible
  557. * on this file, then we must return -EINVAL.
  558. */
  559. ret = -EINVAL;
  560. if (!f.file->f_mapping || !f.file->f_mapping->a_ops ||
  561. !S_ISREG(file_inode(f.file)->i_mode))
  562. goto out;
  563. ret = vfs_fadvise(f.file, offset, count, POSIX_FADV_WILLNEED);
  564. out:
  565. fdput(f);
  566. return ret;
  567. }
  568. SYSCALL_DEFINE3(readahead, int, fd, loff_t, offset, size_t, count)
  569. {
  570. return ksys_readahead(fd, offset, count);
  571. }