~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

TOMOYO Linux Cross Reference
Linux/fs/ext4/extents_status.c

Version: ~ [ linux-5.12-rc7 ] ~ [ linux-5.11.13 ] ~ [ linux-5.10.29 ] ~ [ linux-5.9.16 ] ~ [ linux-5.8.18 ] ~ [ linux-5.7.19 ] ~ [ linux-5.6.19 ] ~ [ linux-5.5.19 ] ~ [ linux-5.4.111 ] ~ [ linux-5.3.18 ] ~ [ linux-5.2.21 ] ~ [ linux-5.1.21 ] ~ [ linux-5.0.21 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.186 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.230 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.266 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.266 ] ~ [ linux-4.3.6 ] ~ [ linux-4.2.8 ] ~ [ linux-4.1.52 ] ~ [ linux-4.0.9 ] ~ [ linux-3.18.140 ] ~ [ linux-3.16.85 ] ~ [ linux-3.14.79 ] ~ [ linux-3.12.74 ] ~ [ linux-3.10.108 ] ~ [ linux-2.6.32.71 ] ~ [ linux-2.6.0 ] ~ [ linux-2.4.37.11 ] ~ [ unix-v6-master ] ~ [ ccs-tools-1.8.5 ] ~ [ policy-sample ] ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

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

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

kernel.org | git.kernel.org | LWN.net | Project Home | Wiki (Japanese) | Wiki (English) | SVN repository | Mail admin

Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.

osdn.jp