extents_status.c 30 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121
  1. /*
  2. * fs/ext4/extents_status.c
  3. *
  4. * Written by Yongqiang Yang <xiaoqiangnk@gmail.com>
  5. * Modified by
  6. * Allison Henderson <achender@linux.vnet.ibm.com>
  7. * Hugh Dickins <hughd@google.com>
  8. * Zheng Liu <wenqing.lz@taobao.com>
  9. *
  10. * Ext4 extents status tree core functions.
  11. */
  12. #include <linux/rbtree.h>
  13. #include <linux/list_sort.h>
  14. #include "ext4.h"
  15. #include "extents_status.h"
  16. #include <trace/events/ext4.h>
  17. /*
  18. * According to previous discussion in Ext4 Developer Workshop, we
  19. * will introduce a new structure called io tree to track all extent
  20. * status in order to solve some problems that we have met
  21. * (e.g. Reservation space warning), and provide extent-level locking.
  22. * Delay extent tree is the first step to achieve this goal. It is
  23. * original built by Yongqiang Yang. At that time it is called delay
  24. * extent tree, whose goal is only track delayed extents in memory to
  25. * simplify the implementation of fiemap and bigalloc, and introduce
  26. * lseek SEEK_DATA/SEEK_HOLE support. That is why it is still called
  27. * delay extent tree at the first commit. But for better understand
  28. * what it does, it has been rename to extent status tree.
  29. *
  30. * Step1:
  31. * Currently the first step has been done. All delayed extents are
  32. * tracked in the tree. It maintains the delayed extent when a delayed
  33. * allocation is issued, and the delayed extent is written out or
  34. * invalidated. Therefore the implementation of fiemap and bigalloc
  35. * are simplified, and SEEK_DATA/SEEK_HOLE are introduced.
  36. *
  37. * The following comment describes the implemenmtation of extent
  38. * status tree and future works.
  39. *
  40. * Step2:
  41. * In this step all extent status are tracked by extent status tree.
  42. * Thus, we can first try to lookup a block mapping in this tree before
  43. * finding it in extent tree. Hence, single extent cache can be removed
  44. * because extent status tree can do a better job. Extents in status
  45. * tree are loaded on-demand. Therefore, the extent status tree may not
  46. * contain all of the extents in a file. Meanwhile we define a shrinker
  47. * to reclaim memory from extent status tree because fragmented extent
  48. * tree will make status tree cost too much memory. written/unwritten/-
  49. * hole extents in the tree will be reclaimed by this shrinker when we
  50. * are under high memory pressure. Delayed extents will not be
  51. * reclimed because fiemap, bigalloc, and seek_data/hole need it.
  52. */
  53. /*
  54. * Extent status tree implementation for ext4.
  55. *
  56. *
  57. * ==========================================================================
  58. * Extent status tree tracks all extent status.
  59. *
  60. * 1. Why we need to implement extent status tree?
  61. *
  62. * Without extent status tree, ext4 identifies a delayed extent by looking
  63. * up page cache, this has several deficiencies - complicated, buggy,
  64. * and inefficient code.
  65. *
  66. * FIEMAP, SEEK_HOLE/DATA, bigalloc, and writeout all need to know if a
  67. * block or a range of blocks are belonged to a delayed extent.
  68. *
  69. * Let us have a look at how they do without extent status tree.
  70. * -- FIEMAP
  71. * FIEMAP looks up page cache to identify delayed allocations from holes.
  72. *
  73. * -- SEEK_HOLE/DATA
  74. * SEEK_HOLE/DATA has the same problem as FIEMAP.
  75. *
  76. * -- bigalloc
  77. * bigalloc looks up page cache to figure out if a block is
  78. * already under delayed allocation or not to determine whether
  79. * quota reserving is needed for the cluster.
  80. *
  81. * -- writeout
  82. * Writeout looks up whole page cache to see if a buffer is
  83. * mapped, If there are not very many delayed buffers, then it is
  84. * time comsuming.
  85. *
  86. * With extent status tree implementation, FIEMAP, SEEK_HOLE/DATA,
  87. * bigalloc and writeout can figure out if a block or a range of
  88. * blocks is under delayed allocation(belonged to a delayed extent) or
  89. * not by searching the extent tree.
  90. *
  91. *
  92. * ==========================================================================
  93. * 2. Ext4 extent status tree impelmentation
  94. *
  95. * -- extent
  96. * A extent is a range of blocks which are contiguous logically and
  97. * physically. Unlike extent in extent tree, this extent in ext4 is
  98. * a in-memory struct, there is no corresponding on-disk data. There
  99. * is no limit on length of extent, so an extent can contain as many
  100. * blocks as they are contiguous logically and physically.
  101. *
  102. * -- extent status tree
  103. * Every inode has an extent status tree and all allocation blocks
  104. * are added to the tree with different status. The extent in the
  105. * tree are ordered by logical block no.
  106. *
  107. * -- operations on a extent status tree
  108. * There are three important operations on a delayed extent tree: find
  109. * next extent, adding a extent(a range of blocks) and removing a extent.
  110. *
  111. * -- race on a extent status tree
  112. * Extent status tree is protected by inode->i_es_lock.
  113. *
  114. * -- memory consumption
  115. * Fragmented extent tree will make extent status tree cost too much
  116. * memory. Hence, we will reclaim written/unwritten/hole extents from
  117. * the tree under a heavy memory pressure.
  118. *
  119. *
  120. * ==========================================================================
  121. * 3. Performance analysis
  122. *
  123. * -- overhead
  124. * 1. There is a cache extent for write access, so if writes are
  125. * not very random, adding space operaions are in O(1) time.
  126. *
  127. * -- gain
  128. * 2. Code is much simpler, more readable, more maintainable and
  129. * more efficient.
  130. *
  131. *
  132. * ==========================================================================
  133. * 4. TODO list
  134. *
  135. * -- Refactor delayed space reservation
  136. *
  137. * -- Extent-level locking
  138. */
  139. static struct kmem_cache *ext4_es_cachep;
  140. static int __es_insert_extent(struct inode *inode, struct extent_status *newes);
  141. static int __es_remove_extent(struct inode *inode, ext4_lblk_t lblk,
  142. ext4_lblk_t end);
  143. static int __es_try_to_reclaim_extents(struct ext4_inode_info *ei,
  144. int nr_to_scan);
  145. static int __ext4_es_shrink(struct ext4_sb_info *sbi, int nr_to_scan,
  146. struct ext4_inode_info *locked_ei);
  147. int __init ext4_init_es(void)
  148. {
  149. ext4_es_cachep = kmem_cache_create("ext4_extent_status",
  150. sizeof(struct extent_status),
  151. 0, (SLAB_RECLAIM_ACCOUNT), NULL);
  152. if (ext4_es_cachep == NULL)
  153. return -ENOMEM;
  154. return 0;
  155. }
  156. void ext4_exit_es(void)
  157. {
  158. if (ext4_es_cachep)
  159. kmem_cache_destroy(ext4_es_cachep);
  160. }
  161. void ext4_es_init_tree(struct ext4_es_tree *tree)
  162. {
  163. tree->root = RB_ROOT;
  164. tree->cache_es = NULL;
  165. }
  166. #ifdef ES_DEBUG__
  167. static void ext4_es_print_tree(struct inode *inode)
  168. {
  169. struct ext4_es_tree *tree;
  170. struct rb_node *node;
  171. printk(KERN_DEBUG "status extents for inode %lu:", inode->i_ino);
  172. tree = &EXT4_I(inode)->i_es_tree;
  173. node = rb_first(&tree->root);
  174. while (node) {
  175. struct extent_status *es;
  176. es = rb_entry(node, struct extent_status, rb_node);
  177. printk(KERN_DEBUG " [%u/%u) %llu %x",
  178. es->es_lblk, es->es_len,
  179. ext4_es_pblock(es), ext4_es_status(es));
  180. node = rb_next(node);
  181. }
  182. printk(KERN_DEBUG "\n");
  183. }
  184. #else
  185. #define ext4_es_print_tree(inode)
  186. #endif
  187. static inline ext4_lblk_t ext4_es_end(struct extent_status *es)
  188. {
  189. BUG_ON(es->es_lblk + es->es_len < es->es_lblk);
  190. return es->es_lblk + es->es_len - 1;
  191. }
  192. /*
  193. * search through the tree for an delayed extent with a given offset. If
  194. * it can't be found, try to find next extent.
  195. */
  196. static struct extent_status *__es_tree_search(struct rb_root *root,
  197. ext4_lblk_t lblk)
  198. {
  199. struct rb_node *node = root->rb_node;
  200. struct extent_status *es = NULL;
  201. while (node) {
  202. es = rb_entry(node, struct extent_status, rb_node);
  203. if (lblk < es->es_lblk)
  204. node = node->rb_left;
  205. else if (lblk > ext4_es_end(es))
  206. node = node->rb_right;
  207. else
  208. return es;
  209. }
  210. if (es && lblk < es->es_lblk)
  211. return es;
  212. if (es && lblk > ext4_es_end(es)) {
  213. node = rb_next(&es->rb_node);
  214. return node ? rb_entry(node, struct extent_status, rb_node) :
  215. NULL;
  216. }
  217. return NULL;
  218. }
  219. /*
  220. * ext4_es_find_delayed_extent_range: find the 1st delayed extent covering
  221. * @es->lblk if it exists, otherwise, the next extent after @es->lblk.
  222. *
  223. * @inode: the inode which owns delayed extents
  224. * @lblk: the offset where we start to search
  225. * @end: the offset where we stop to search
  226. * @es: delayed extent that we found
  227. */
  228. void ext4_es_find_delayed_extent_range(struct inode *inode,
  229. ext4_lblk_t lblk, ext4_lblk_t end,
  230. struct extent_status *es)
  231. {
  232. struct ext4_es_tree *tree = NULL;
  233. struct extent_status *es1 = NULL;
  234. struct rb_node *node;
  235. BUG_ON(es == NULL);
  236. BUG_ON(end < lblk);
  237. trace_ext4_es_find_delayed_extent_range_enter(inode, lblk);
  238. read_lock(&EXT4_I(inode)->i_es_lock);
  239. tree = &EXT4_I(inode)->i_es_tree;
  240. /* find extent in cache firstly */
  241. es->es_lblk = es->es_len = es->es_pblk = 0;
  242. if (tree->cache_es) {
  243. es1 = tree->cache_es;
  244. if (in_range(lblk, es1->es_lblk, es1->es_len)) {
  245. es_debug("%u cached by [%u/%u) %llu %x\n",
  246. lblk, es1->es_lblk, es1->es_len,
  247. ext4_es_pblock(es1), ext4_es_status(es1));
  248. goto out;
  249. }
  250. }
  251. es1 = __es_tree_search(&tree->root, lblk);
  252. out:
  253. if (es1 && !ext4_es_is_delayed(es1)) {
  254. while ((node = rb_next(&es1->rb_node)) != NULL) {
  255. es1 = rb_entry(node, struct extent_status, rb_node);
  256. if (es1->es_lblk > end) {
  257. es1 = NULL;
  258. break;
  259. }
  260. if (ext4_es_is_delayed(es1))
  261. break;
  262. }
  263. }
  264. if (es1 && ext4_es_is_delayed(es1)) {
  265. tree->cache_es = es1;
  266. es->es_lblk = es1->es_lblk;
  267. es->es_len = es1->es_len;
  268. es->es_pblk = es1->es_pblk;
  269. }
  270. read_unlock(&EXT4_I(inode)->i_es_lock);
  271. trace_ext4_es_find_delayed_extent_range_exit(inode, es);
  272. }
  273. static struct extent_status *
  274. ext4_es_alloc_extent(struct inode *inode, ext4_lblk_t lblk, ext4_lblk_t len,
  275. ext4_fsblk_t pblk)
  276. {
  277. struct extent_status *es;
  278. es = kmem_cache_alloc(ext4_es_cachep, GFP_ATOMIC);
  279. if (es == NULL)
  280. return NULL;
  281. es->es_lblk = lblk;
  282. es->es_len = len;
  283. es->es_pblk = pblk;
  284. /*
  285. * We don't count delayed extent because we never try to reclaim them
  286. */
  287. if (!ext4_es_is_delayed(es)) {
  288. EXT4_I(inode)->i_es_lru_nr++;
  289. percpu_counter_inc(&EXT4_SB(inode->i_sb)->s_extent_cache_cnt);
  290. }
  291. return es;
  292. }
  293. static void ext4_es_free_extent(struct inode *inode, struct extent_status *es)
  294. {
  295. /* Decrease the lru counter when this es is not delayed */
  296. if (!ext4_es_is_delayed(es)) {
  297. BUG_ON(EXT4_I(inode)->i_es_lru_nr == 0);
  298. EXT4_I(inode)->i_es_lru_nr--;
  299. percpu_counter_dec(&EXT4_SB(inode->i_sb)->s_extent_cache_cnt);
  300. }
  301. kmem_cache_free(ext4_es_cachep, es);
  302. }
  303. /*
  304. * Check whether or not two extents can be merged
  305. * Condition:
  306. * - logical block number is contiguous
  307. * - physical block number is contiguous
  308. * - status is equal
  309. */
  310. static int ext4_es_can_be_merged(struct extent_status *es1,
  311. struct extent_status *es2)
  312. {
  313. if (ext4_es_status(es1) != ext4_es_status(es2))
  314. return 0;
  315. if (((__u64) es1->es_len) + es2->es_len > 0xFFFFFFFFULL)
  316. return 0;
  317. if (((__u64) es1->es_lblk) + es1->es_len != es2->es_lblk)
  318. return 0;
  319. if ((ext4_es_is_written(es1) || ext4_es_is_unwritten(es1)) &&
  320. (ext4_es_pblock(es1) + es1->es_len == ext4_es_pblock(es2)))
  321. return 1;
  322. if (ext4_es_is_hole(es1))
  323. return 1;
  324. /* we need to check delayed extent is without unwritten status */
  325. if (ext4_es_is_delayed(es1) && !ext4_es_is_unwritten(es1))
  326. return 1;
  327. return 0;
  328. }
  329. static struct extent_status *
  330. ext4_es_try_to_merge_left(struct inode *inode, struct extent_status *es)
  331. {
  332. struct ext4_es_tree *tree = &EXT4_I(inode)->i_es_tree;
  333. struct extent_status *es1;
  334. struct rb_node *node;
  335. node = rb_prev(&es->rb_node);
  336. if (!node)
  337. return es;
  338. es1 = rb_entry(node, struct extent_status, rb_node);
  339. if (ext4_es_can_be_merged(es1, es)) {
  340. es1->es_len += es->es_len;
  341. rb_erase(&es->rb_node, &tree->root);
  342. ext4_es_free_extent(inode, es);
  343. es = es1;
  344. }
  345. return es;
  346. }
  347. static struct extent_status *
  348. ext4_es_try_to_merge_right(struct inode *inode, struct extent_status *es)
  349. {
  350. struct ext4_es_tree *tree = &EXT4_I(inode)->i_es_tree;
  351. struct extent_status *es1;
  352. struct rb_node *node;
  353. node = rb_next(&es->rb_node);
  354. if (!node)
  355. return es;
  356. es1 = rb_entry(node, struct extent_status, rb_node);
  357. if (ext4_es_can_be_merged(es, es1)) {
  358. es->es_len += es1->es_len;
  359. rb_erase(node, &tree->root);
  360. ext4_es_free_extent(inode, es1);
  361. }
  362. return es;
  363. }
  364. #ifdef ES_AGGRESSIVE_TEST
  365. #include "ext4_extents.h" /* Needed when ES_AGGRESSIVE_TEST is defined */
  366. static void ext4_es_insert_extent_ext_check(struct inode *inode,
  367. struct extent_status *es)
  368. {
  369. struct ext4_ext_path *path = NULL;
  370. struct ext4_extent *ex;
  371. ext4_lblk_t ee_block;
  372. ext4_fsblk_t ee_start;
  373. unsigned short ee_len;
  374. int depth, ee_status, es_status;
  375. path = ext4_ext_find_extent(inode, es->es_lblk, NULL, EXT4_EX_NOCACHE);
  376. if (IS_ERR(path))
  377. return;
  378. depth = ext_depth(inode);
  379. ex = path[depth].p_ext;
  380. if (ex) {
  381. ee_block = le32_to_cpu(ex->ee_block);
  382. ee_start = ext4_ext_pblock(ex);
  383. ee_len = ext4_ext_get_actual_len(ex);
  384. ee_status = ext4_ext_is_uninitialized(ex) ? 1 : 0;
  385. es_status = ext4_es_is_unwritten(es) ? 1 : 0;
  386. /*
  387. * Make sure ex and es are not overlap when we try to insert
  388. * a delayed/hole extent.
  389. */
  390. if (!ext4_es_is_written(es) && !ext4_es_is_unwritten(es)) {
  391. if (in_range(es->es_lblk, ee_block, ee_len)) {
  392. pr_warn("ES insert assertion failed for "
  393. "inode: %lu we can find an extent "
  394. "at block [%d/%d/%llu/%c], but we "
  395. "want to add a delayed/hole extent "
  396. "[%d/%d/%llu/%x]\n",
  397. inode->i_ino, ee_block, ee_len,
  398. ee_start, ee_status ? 'u' : 'w',
  399. es->es_lblk, es->es_len,
  400. ext4_es_pblock(es), ext4_es_status(es));
  401. }
  402. goto out;
  403. }
  404. /*
  405. * We don't check ee_block == es->es_lblk, etc. because es
  406. * might be a part of whole extent, vice versa.
  407. */
  408. if (es->es_lblk < ee_block ||
  409. ext4_es_pblock(es) != ee_start + es->es_lblk - ee_block) {
  410. pr_warn("ES insert assertion failed for inode: %lu "
  411. "ex_status [%d/%d/%llu/%c] != "
  412. "es_status [%d/%d/%llu/%c]\n", inode->i_ino,
  413. ee_block, ee_len, ee_start,
  414. ee_status ? 'u' : 'w', es->es_lblk, es->es_len,
  415. ext4_es_pblock(es), es_status ? 'u' : 'w');
  416. goto out;
  417. }
  418. if (ee_status ^ es_status) {
  419. pr_warn("ES insert assertion failed for inode: %lu "
  420. "ex_status [%d/%d/%llu/%c] != "
  421. "es_status [%d/%d/%llu/%c]\n", inode->i_ino,
  422. ee_block, ee_len, ee_start,
  423. ee_status ? 'u' : 'w', es->es_lblk, es->es_len,
  424. ext4_es_pblock(es), es_status ? 'u' : 'w');
  425. }
  426. } else {
  427. /*
  428. * We can't find an extent on disk. So we need to make sure
  429. * that we don't want to add an written/unwritten extent.
  430. */
  431. if (!ext4_es_is_delayed(es) && !ext4_es_is_hole(es)) {
  432. pr_warn("ES insert assertion failed for inode: %lu "
  433. "can't find an extent at block %d but we want "
  434. "to add a written/unwritten extent "
  435. "[%d/%d/%llu/%x]\n", inode->i_ino,
  436. es->es_lblk, es->es_lblk, es->es_len,
  437. ext4_es_pblock(es), ext4_es_status(es));
  438. }
  439. }
  440. out:
  441. if (path) {
  442. ext4_ext_drop_refs(path);
  443. kfree(path);
  444. }
  445. }
  446. static void ext4_es_insert_extent_ind_check(struct inode *inode,
  447. struct extent_status *es)
  448. {
  449. struct ext4_map_blocks map;
  450. int retval;
  451. /*
  452. * Here we call ext4_ind_map_blocks to lookup a block mapping because
  453. * 'Indirect' structure is defined in indirect.c. So we couldn't
  454. * access direct/indirect tree from outside. It is too dirty to define
  455. * this function in indirect.c file.
  456. */
  457. map.m_lblk = es->es_lblk;
  458. map.m_len = es->es_len;
  459. retval = ext4_ind_map_blocks(NULL, inode, &map, 0);
  460. if (retval > 0) {
  461. if (ext4_es_is_delayed(es) || ext4_es_is_hole(es)) {
  462. /*
  463. * We want to add a delayed/hole extent but this
  464. * block has been allocated.
  465. */
  466. pr_warn("ES insert assertion failed for inode: %lu "
  467. "We can find blocks but we want to add a "
  468. "delayed/hole extent [%d/%d/%llu/%x]\n",
  469. inode->i_ino, es->es_lblk, es->es_len,
  470. ext4_es_pblock(es), ext4_es_status(es));
  471. return;
  472. } else if (ext4_es_is_written(es)) {
  473. if (retval != es->es_len) {
  474. pr_warn("ES insert assertion failed for "
  475. "inode: %lu retval %d != es_len %d\n",
  476. inode->i_ino, retval, es->es_len);
  477. return;
  478. }
  479. if (map.m_pblk != ext4_es_pblock(es)) {
  480. pr_warn("ES insert assertion failed for "
  481. "inode: %lu m_pblk %llu != "
  482. "es_pblk %llu\n",
  483. inode->i_ino, map.m_pblk,
  484. ext4_es_pblock(es));
  485. return;
  486. }
  487. } else {
  488. /*
  489. * We don't need to check unwritten extent because
  490. * indirect-based file doesn't have it.
  491. */
  492. BUG_ON(1);
  493. }
  494. } else if (retval == 0) {
  495. if (ext4_es_is_written(es)) {
  496. pr_warn("ES insert assertion failed for inode: %lu "
  497. "We can't find the block but we want to add "
  498. "a written extent [%d/%d/%llu/%x]\n",
  499. inode->i_ino, es->es_lblk, es->es_len,
  500. ext4_es_pblock(es), ext4_es_status(es));
  501. return;
  502. }
  503. }
  504. }
  505. static inline void ext4_es_insert_extent_check(struct inode *inode,
  506. struct extent_status *es)
  507. {
  508. /*
  509. * We don't need to worry about the race condition because
  510. * caller takes i_data_sem locking.
  511. */
  512. BUG_ON(!rwsem_is_locked(&EXT4_I(inode)->i_data_sem));
  513. if (ext4_test_inode_flag(inode, EXT4_INODE_EXTENTS))
  514. ext4_es_insert_extent_ext_check(inode, es);
  515. else
  516. ext4_es_insert_extent_ind_check(inode, es);
  517. }
  518. #else
  519. static inline void ext4_es_insert_extent_check(struct inode *inode,
  520. struct extent_status *es)
  521. {
  522. }
  523. #endif
  524. static int __es_insert_extent(struct inode *inode, struct extent_status *newes)
  525. {
  526. struct ext4_es_tree *tree = &EXT4_I(inode)->i_es_tree;
  527. struct rb_node **p = &tree->root.rb_node;
  528. struct rb_node *parent = NULL;
  529. struct extent_status *es;
  530. while (*p) {
  531. parent = *p;
  532. es = rb_entry(parent, struct extent_status, rb_node);
  533. if (newes->es_lblk < es->es_lblk) {
  534. if (ext4_es_can_be_merged(newes, es)) {
  535. /*
  536. * Here we can modify es_lblk directly
  537. * because it isn't overlapped.
  538. */
  539. es->es_lblk = newes->es_lblk;
  540. es->es_len += newes->es_len;
  541. if (ext4_es_is_written(es) ||
  542. ext4_es_is_unwritten(es))
  543. ext4_es_store_pblock(es,
  544. newes->es_pblk);
  545. es = ext4_es_try_to_merge_left(inode, es);
  546. goto out;
  547. }
  548. p = &(*p)->rb_left;
  549. } else if (newes->es_lblk > ext4_es_end(es)) {
  550. if (ext4_es_can_be_merged(es, newes)) {
  551. es->es_len += newes->es_len;
  552. es = ext4_es_try_to_merge_right(inode, es);
  553. goto out;
  554. }
  555. p = &(*p)->rb_right;
  556. } else {
  557. BUG_ON(1);
  558. return -EINVAL;
  559. }
  560. }
  561. es = ext4_es_alloc_extent(inode, newes->es_lblk, newes->es_len,
  562. newes->es_pblk);
  563. if (!es)
  564. return -ENOMEM;
  565. rb_link_node(&es->rb_node, parent, p);
  566. rb_insert_color(&es->rb_node, &tree->root);
  567. out:
  568. tree->cache_es = es;
  569. return 0;
  570. }
  571. /*
  572. * ext4_es_insert_extent() adds information to an inode's extent
  573. * status tree.
  574. *
  575. * Return 0 on success, error code on failure.
  576. */
  577. int ext4_es_insert_extent(struct inode *inode, ext4_lblk_t lblk,
  578. ext4_lblk_t len, ext4_fsblk_t pblk,
  579. unsigned int status)
  580. {
  581. struct extent_status newes;
  582. ext4_lblk_t end = lblk + len - 1;
  583. int err = 0;
  584. es_debug("add [%u/%u) %llu %x to extent status tree of inode %lu\n",
  585. lblk, len, pblk, status, inode->i_ino);
  586. if (!len)
  587. return 0;
  588. BUG_ON(end < lblk);
  589. newes.es_lblk = lblk;
  590. newes.es_len = len;
  591. ext4_es_store_pblock_status(&newes, pblk, status);
  592. trace_ext4_es_insert_extent(inode, &newes);
  593. ext4_es_insert_extent_check(inode, &newes);
  594. write_lock(&EXT4_I(inode)->i_es_lock);
  595. err = __es_remove_extent(inode, lblk, end);
  596. if (err != 0)
  597. goto error;
  598. retry:
  599. err = __es_insert_extent(inode, &newes);
  600. if (err == -ENOMEM && __ext4_es_shrink(EXT4_SB(inode->i_sb), 1,
  601. EXT4_I(inode)))
  602. goto retry;
  603. if (err == -ENOMEM && !ext4_es_is_delayed(&newes))
  604. err = 0;
  605. error:
  606. write_unlock(&EXT4_I(inode)->i_es_lock);
  607. ext4_es_print_tree(inode);
  608. return err;
  609. }
  610. /*
  611. * ext4_es_cache_extent() inserts information into the extent status
  612. * tree if and only if there isn't information about the range in
  613. * question already.
  614. */
  615. void ext4_es_cache_extent(struct inode *inode, ext4_lblk_t lblk,
  616. ext4_lblk_t len, ext4_fsblk_t pblk,
  617. unsigned int status)
  618. {
  619. struct extent_status *es;
  620. struct extent_status newes;
  621. ext4_lblk_t end = lblk + len - 1;
  622. newes.es_lblk = lblk;
  623. newes.es_len = len;
  624. ext4_es_store_pblock_status(&newes, pblk, status);
  625. trace_ext4_es_cache_extent(inode, &newes);
  626. if (!len)
  627. return;
  628. BUG_ON(end < lblk);
  629. write_lock(&EXT4_I(inode)->i_es_lock);
  630. es = __es_tree_search(&EXT4_I(inode)->i_es_tree.root, lblk);
  631. if (!es || es->es_lblk > end)
  632. __es_insert_extent(inode, &newes);
  633. write_unlock(&EXT4_I(inode)->i_es_lock);
  634. }
  635. /*
  636. * ext4_es_lookup_extent() looks up an extent in extent status tree.
  637. *
  638. * ext4_es_lookup_extent is called by ext4_map_blocks/ext4_da_map_blocks.
  639. *
  640. * Return: 1 on found, 0 on not
  641. */
  642. int ext4_es_lookup_extent(struct inode *inode, ext4_lblk_t lblk,
  643. struct extent_status *es)
  644. {
  645. struct ext4_es_tree *tree;
  646. struct extent_status *es1 = NULL;
  647. struct rb_node *node;
  648. int found = 0;
  649. trace_ext4_es_lookup_extent_enter(inode, lblk);
  650. es_debug("lookup extent in block %u\n", lblk);
  651. tree = &EXT4_I(inode)->i_es_tree;
  652. read_lock(&EXT4_I(inode)->i_es_lock);
  653. /* find extent in cache firstly */
  654. es->es_lblk = es->es_len = es->es_pblk = 0;
  655. if (tree->cache_es) {
  656. es1 = tree->cache_es;
  657. if (in_range(lblk, es1->es_lblk, es1->es_len)) {
  658. es_debug("%u cached by [%u/%u)\n",
  659. lblk, es1->es_lblk, es1->es_len);
  660. found = 1;
  661. goto out;
  662. }
  663. }
  664. node = tree->root.rb_node;
  665. while (node) {
  666. es1 = rb_entry(node, struct extent_status, rb_node);
  667. if (lblk < es1->es_lblk)
  668. node = node->rb_left;
  669. else if (lblk > ext4_es_end(es1))
  670. node = node->rb_right;
  671. else {
  672. found = 1;
  673. break;
  674. }
  675. }
  676. out:
  677. if (found) {
  678. BUG_ON(!es1);
  679. es->es_lblk = es1->es_lblk;
  680. es->es_len = es1->es_len;
  681. es->es_pblk = es1->es_pblk;
  682. }
  683. read_unlock(&EXT4_I(inode)->i_es_lock);
  684. trace_ext4_es_lookup_extent_exit(inode, es, found);
  685. return found;
  686. }
  687. static int __es_remove_extent(struct inode *inode, ext4_lblk_t lblk,
  688. ext4_lblk_t end)
  689. {
  690. struct ext4_es_tree *tree = &EXT4_I(inode)->i_es_tree;
  691. struct rb_node *node;
  692. struct extent_status *es;
  693. struct extent_status orig_es;
  694. ext4_lblk_t len1, len2;
  695. ext4_fsblk_t block;
  696. int err;
  697. retry:
  698. err = 0;
  699. es = __es_tree_search(&tree->root, lblk);
  700. if (!es)
  701. goto out;
  702. if (es->es_lblk > end)
  703. goto out;
  704. /* Simply invalidate cache_es. */
  705. tree->cache_es = NULL;
  706. orig_es.es_lblk = es->es_lblk;
  707. orig_es.es_len = es->es_len;
  708. orig_es.es_pblk = es->es_pblk;
  709. len1 = lblk > es->es_lblk ? lblk - es->es_lblk : 0;
  710. len2 = ext4_es_end(es) > end ? ext4_es_end(es) - end : 0;
  711. if (len1 > 0)
  712. es->es_len = len1;
  713. if (len2 > 0) {
  714. if (len1 > 0) {
  715. struct extent_status newes;
  716. newes.es_lblk = end + 1;
  717. newes.es_len = len2;
  718. block = 0x7FDEADBEEFULL;
  719. if (ext4_es_is_written(&orig_es) ||
  720. ext4_es_is_unwritten(&orig_es))
  721. block = ext4_es_pblock(&orig_es) +
  722. orig_es.es_len - len2;
  723. ext4_es_store_pblock_status(&newes, block,
  724. ext4_es_status(&orig_es));
  725. err = __es_insert_extent(inode, &newes);
  726. if (err) {
  727. es->es_lblk = orig_es.es_lblk;
  728. es->es_len = orig_es.es_len;
  729. if ((err == -ENOMEM) &&
  730. __ext4_es_shrink(EXT4_SB(inode->i_sb), 1,
  731. EXT4_I(inode)))
  732. goto retry;
  733. goto out;
  734. }
  735. } else {
  736. es->es_lblk = end + 1;
  737. es->es_len = len2;
  738. if (ext4_es_is_written(es) ||
  739. ext4_es_is_unwritten(es)) {
  740. block = orig_es.es_pblk + orig_es.es_len - len2;
  741. ext4_es_store_pblock(es, block);
  742. }
  743. }
  744. goto out;
  745. }
  746. if (len1 > 0) {
  747. node = rb_next(&es->rb_node);
  748. if (node)
  749. es = rb_entry(node, struct extent_status, rb_node);
  750. else
  751. es = NULL;
  752. }
  753. while (es && ext4_es_end(es) <= end) {
  754. node = rb_next(&es->rb_node);
  755. rb_erase(&es->rb_node, &tree->root);
  756. ext4_es_free_extent(inode, es);
  757. if (!node) {
  758. es = NULL;
  759. break;
  760. }
  761. es = rb_entry(node, struct extent_status, rb_node);
  762. }
  763. if (es && es->es_lblk < end + 1) {
  764. ext4_lblk_t orig_len = es->es_len;
  765. len1 = ext4_es_end(es) - end;
  766. es->es_lblk = end + 1;
  767. es->es_len = len1;
  768. if (ext4_es_is_written(es) || ext4_es_is_unwritten(es)) {
  769. block = es->es_pblk + orig_len - len1;
  770. ext4_es_store_pblock(es, block);
  771. }
  772. }
  773. out:
  774. return err;
  775. }
  776. /*
  777. * ext4_es_remove_extent() removes a space from a extent status tree.
  778. *
  779. * Return 0 on success, error code on failure.
  780. */
  781. int ext4_es_remove_extent(struct inode *inode, ext4_lblk_t lblk,
  782. ext4_lblk_t len)
  783. {
  784. ext4_lblk_t end;
  785. int err = 0;
  786. trace_ext4_es_remove_extent(inode, lblk, len);
  787. es_debug("remove [%u/%u) from extent status tree of inode %lu\n",
  788. lblk, len, inode->i_ino);
  789. if (!len)
  790. return err;
  791. end = lblk + len - 1;
  792. BUG_ON(end < lblk);
  793. write_lock(&EXT4_I(inode)->i_es_lock);
  794. err = __es_remove_extent(inode, lblk, end);
  795. write_unlock(&EXT4_I(inode)->i_es_lock);
  796. ext4_es_print_tree(inode);
  797. return err;
  798. }
  799. static int ext4_inode_touch_time_cmp(void *priv, struct list_head *a,
  800. struct list_head *b)
  801. {
  802. struct ext4_inode_info *eia, *eib;
  803. eia = list_entry(a, struct ext4_inode_info, i_es_lru);
  804. eib = list_entry(b, struct ext4_inode_info, i_es_lru);
  805. if (ext4_test_inode_state(&eia->vfs_inode, EXT4_STATE_EXT_PRECACHED) &&
  806. !ext4_test_inode_state(&eib->vfs_inode, EXT4_STATE_EXT_PRECACHED))
  807. return 1;
  808. if (!ext4_test_inode_state(&eia->vfs_inode, EXT4_STATE_EXT_PRECACHED) &&
  809. ext4_test_inode_state(&eib->vfs_inode, EXT4_STATE_EXT_PRECACHED))
  810. return -1;
  811. if (eia->i_touch_when == eib->i_touch_when)
  812. return 0;
  813. if (time_after(eia->i_touch_when, eib->i_touch_when))
  814. return 1;
  815. else
  816. return -1;
  817. }
  818. static int __ext4_es_shrink(struct ext4_sb_info *sbi, int nr_to_scan,
  819. struct ext4_inode_info *locked_ei)
  820. {
  821. struct ext4_inode_info *ei;
  822. struct list_head *cur, *tmp;
  823. LIST_HEAD(skipped);
  824. int nr_shrunk = 0;
  825. int retried = 0, skip_precached = 1, nr_skipped = 0;
  826. spin_lock(&sbi->s_es_lru_lock);
  827. retry:
  828. list_for_each_safe(cur, tmp, &sbi->s_es_lru) {
  829. int shrunk;
  830. /*
  831. * If we have already reclaimed all extents from extent
  832. * status tree, just stop the loop immediately.
  833. */
  834. if (percpu_counter_read_positive(&sbi->s_extent_cache_cnt) == 0)
  835. break;
  836. ei = list_entry(cur, struct ext4_inode_info, i_es_lru);
  837. /*
  838. * Skip the inode that is newer than the last_sorted
  839. * time. Normally we try hard to avoid shrinking
  840. * precached inodes, but we will as a last resort.
  841. */
  842. if ((sbi->s_es_last_sorted < ei->i_touch_when) ||
  843. (skip_precached && ext4_test_inode_state(&ei->vfs_inode,
  844. EXT4_STATE_EXT_PRECACHED))) {
  845. nr_skipped++;
  846. list_move_tail(cur, &skipped);
  847. continue;
  848. }
  849. if (ei->i_es_lru_nr == 0 || ei == locked_ei)
  850. continue;
  851. write_lock(&ei->i_es_lock);
  852. shrunk = __es_try_to_reclaim_extents(ei, nr_to_scan);
  853. if (ei->i_es_lru_nr == 0)
  854. list_del_init(&ei->i_es_lru);
  855. write_unlock(&ei->i_es_lock);
  856. nr_shrunk += shrunk;
  857. nr_to_scan -= shrunk;
  858. if (nr_to_scan == 0)
  859. break;
  860. }
  861. /* Move the newer inodes into the tail of the LRU list. */
  862. list_splice_tail(&skipped, &sbi->s_es_lru);
  863. INIT_LIST_HEAD(&skipped);
  864. /*
  865. * If we skipped any inodes, and we weren't able to make any
  866. * forward progress, sort the list and try again.
  867. */
  868. if ((nr_shrunk == 0) && nr_skipped && !retried) {
  869. retried++;
  870. list_sort(NULL, &sbi->s_es_lru, ext4_inode_touch_time_cmp);
  871. sbi->s_es_last_sorted = jiffies;
  872. ei = list_first_entry(&sbi->s_es_lru, struct ext4_inode_info,
  873. i_es_lru);
  874. /*
  875. * If there are no non-precached inodes left on the
  876. * list, start releasing precached extents.
  877. */
  878. if (ext4_test_inode_state(&ei->vfs_inode,
  879. EXT4_STATE_EXT_PRECACHED))
  880. skip_precached = 0;
  881. goto retry;
  882. }
  883. spin_unlock(&sbi->s_es_lru_lock);
  884. if (locked_ei && nr_shrunk == 0)
  885. nr_shrunk = __es_try_to_reclaim_extents(locked_ei, nr_to_scan);
  886. return nr_shrunk;
  887. }
  888. static unsigned long ext4_es_count(struct shrinker *shrink,
  889. struct shrink_control *sc)
  890. {
  891. unsigned long nr;
  892. struct ext4_sb_info *sbi;
  893. sbi = container_of(shrink, struct ext4_sb_info, s_es_shrinker);
  894. nr = percpu_counter_read_positive(&sbi->s_extent_cache_cnt);
  895. trace_ext4_es_shrink_enter(sbi->s_sb, sc->nr_to_scan, nr);
  896. return nr;
  897. }
  898. static unsigned long ext4_es_scan(struct shrinker *shrink,
  899. struct shrink_control *sc)
  900. {
  901. struct ext4_sb_info *sbi = container_of(shrink,
  902. struct ext4_sb_info, s_es_shrinker);
  903. int nr_to_scan = sc->nr_to_scan;
  904. int ret, nr_shrunk;
  905. ret = percpu_counter_read_positive(&sbi->s_extent_cache_cnt);
  906. trace_ext4_es_shrink_enter(sbi->s_sb, nr_to_scan, ret);
  907. if (!nr_to_scan)
  908. return ret;
  909. nr_shrunk = __ext4_es_shrink(sbi, nr_to_scan, NULL);
  910. trace_ext4_es_shrink_exit(sbi->s_sb, nr_shrunk, ret);
  911. return nr_shrunk;
  912. }
  913. void ext4_es_register_shrinker(struct ext4_sb_info *sbi)
  914. {
  915. INIT_LIST_HEAD(&sbi->s_es_lru);
  916. spin_lock_init(&sbi->s_es_lru_lock);
  917. sbi->s_es_last_sorted = 0;
  918. sbi->s_es_shrinker.scan_objects = ext4_es_scan;
  919. sbi->s_es_shrinker.count_objects = ext4_es_count;
  920. sbi->s_es_shrinker.seeks = DEFAULT_SEEKS;
  921. register_shrinker(&sbi->s_es_shrinker);
  922. }
  923. void ext4_es_unregister_shrinker(struct ext4_sb_info *sbi)
  924. {
  925. unregister_shrinker(&sbi->s_es_shrinker);
  926. }
  927. void ext4_es_lru_add(struct inode *inode)
  928. {
  929. struct ext4_inode_info *ei = EXT4_I(inode);
  930. struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
  931. ei->i_touch_when = jiffies;
  932. if (!list_empty(&ei->i_es_lru))
  933. return;
  934. spin_lock(&sbi->s_es_lru_lock);
  935. if (list_empty(&ei->i_es_lru))
  936. list_add_tail(&ei->i_es_lru, &sbi->s_es_lru);
  937. spin_unlock(&sbi->s_es_lru_lock);
  938. }
  939. void ext4_es_lru_del(struct inode *inode)
  940. {
  941. struct ext4_inode_info *ei = EXT4_I(inode);
  942. struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
  943. spin_lock(&sbi->s_es_lru_lock);
  944. if (!list_empty(&ei->i_es_lru))
  945. list_del_init(&ei->i_es_lru);
  946. spin_unlock(&sbi->s_es_lru_lock);
  947. }
  948. static int __es_try_to_reclaim_extents(struct ext4_inode_info *ei,
  949. int nr_to_scan)
  950. {
  951. struct inode *inode = &ei->vfs_inode;
  952. struct ext4_es_tree *tree = &ei->i_es_tree;
  953. struct rb_node *node;
  954. struct extent_status *es;
  955. unsigned long nr_shrunk = 0;
  956. static DEFINE_RATELIMIT_STATE(_rs, DEFAULT_RATELIMIT_INTERVAL,
  957. DEFAULT_RATELIMIT_BURST);
  958. if (ei->i_es_lru_nr == 0)
  959. return 0;
  960. if (ext4_test_inode_state(inode, EXT4_STATE_EXT_PRECACHED) &&
  961. __ratelimit(&_rs))
  962. ext4_warning(inode->i_sb, "forced shrink of precached extents");
  963. node = rb_first(&tree->root);
  964. while (node != NULL) {
  965. es = rb_entry(node, struct extent_status, rb_node);
  966. node = rb_next(&es->rb_node);
  967. /*
  968. * We can't reclaim delayed extent from status tree because
  969. * fiemap, bigallic, and seek_data/hole need to use it.
  970. */
  971. if (!ext4_es_is_delayed(es)) {
  972. rb_erase(&es->rb_node, &tree->root);
  973. ext4_es_free_extent(inode, es);
  974. nr_shrunk++;
  975. if (--nr_to_scan == 0)
  976. break;
  977. }
  978. }
  979. tree->cache_es = NULL;
  980. return nr_shrunk;
  981. }