fs/ext4/extents_status.c

   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 "ext4.h"
  14 #include "extents_status.h"
  15 #include "ext4_extents.h"
  16
  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 delay extent 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 following comment.  But for better
  28  * understand what it does, it has been rename to extent status tree.
  29  *
  30  * Currently the first step has been done.  All delay extents are
  31  * tracked in the tree.  It maintains the delay extent when a delay
  32  * allocation is issued, and the delay extent is written out or
  33  * invalidated.  Therefore the implementation of fiemap and bigalloc
  34  * are simplified, and SEEK_DATA/SEEK_HOLE are introduced.
  35  *
  36  * The following comment describes the implemenmtation of extent
  37  * status tree and future works.
  38  */
  39
  40 /*
  41  * extents status tree implementation for ext4.
  42  *
  43  *
  44  * ==========================================================================
  45  * Extents status encompass delayed extents and extent locks
  46  *
  47  * 1. Why delayed extent implementation ?
  48  *
  49  * Without delayed extent, ext4 identifies a delayed extent by looking
  50  * up page cache, this has several deficiencies - complicated, buggy,
  51  * and inefficient code.
  52  *
  53  * FIEMAP, SEEK_HOLE/DATA, bigalloc, punch hole and writeout all need
  54  * to know if a block or a range of blocks are belonged to a delayed
  55  * extent.
  56  *
  57  * Let us have a look at how they do without delayed extents implementation.
  58  *   -- FIEMAP
  59  *      FIEMAP looks up page cache to identify delayed allocations from holes.
  60  *
  61  *   -- SEEK_HOLE/DATA
  62  *      SEEK_HOLE/DATA has the same problem as FIEMAP.
  63  *
  64  *   -- bigalloc
  65  *      bigalloc looks up page cache to figure out if a block is
  66  *      already under delayed allocation or not to determine whether
  67  *      quota reserving is needed for the cluster.
  68  *
  69  *   -- punch hole
  70  *      punch hole looks up page cache to identify a delayed extent.
  71  *
  72  *   -- writeout
  73  *      Writeout looks up whole page cache to see if a buffer is
  74  *      mapped, If there are not very many delayed buffers, then it is
  75  *      time comsuming.
  76  *
  77  * With delayed extents implementation, FIEMAP, SEEK_HOLE/DATA,
  78  * bigalloc and writeout can figure out if a block or a range of
  79  * blocks is under delayed allocation(belonged to a delayed extent) or
  80  * not by searching the delayed extent tree.
  81  *
  82  *
  83  * ==========================================================================
  84  * 2. ext4 delayed extents impelmentation
  85  *
  86  *   -- delayed extent
  87  *      A delayed extent is a range of blocks which are contiguous
  88  *      logically and under delayed allocation.  Unlike extent in
  89  *      ext4, delayed extent in ext4 is a in-memory struct, there is
  90  *      no corresponding on-disk data.  There is no limit on length of
  91  *      delayed extent, so a delayed extent can contain as many blocks
  92  *      as they are contiguous logically.
  93  *
  94  *   -- delayed extent tree
  95  *      Every inode has a delayed extent tree and all under delayed
  96  *      allocation blocks are added to the tree as delayed extents.
  97  *      Delayed extents in the tree are ordered by logical block no.
  98  *
  99  *   -- operations on a delayed extent tree
 100  *      There are three operations on a delayed extent tree: find next
 101  *      delayed extent, adding a space(a range of blocks) and removing
 102  *      a space.
 103  *
 104  *   -- race on a delayed extent tree
 105  *      Delayed extent tree is protected inode->i_es_lock.
 106  *
 107  *
 108  * ==========================================================================
 109  * 3. performance analysis
 110  *   -- overhead
 111  *      1. There is a cache extent for write access, so if writes are
 112  *      not very random, adding space operaions are in O(1) time.
 113  *
 114  *   -- gain
 115  *      2. Code is much simpler, more readable, more maintainable and
 116  *      more efficient.
 117  *
 118  *
 119  * ==========================================================================
 120  * 4. TODO list
 121  *   -- Track all extent status
 122  *
 123  *   -- Improve get block process
 124  *
 125  *   -- Extent-level locking
 126  */
 127
 128 static struct kmem_cache *ext4_es_cachep;
 129
 130 int __init ext4_init_es(void)
 131 {
 132         ext4_es_cachep = KMEM_CACHE(extent_status, SLAB_RECLAIM_ACCOUNT);
 133         if (ext4_es_cachep == NULL)
 134                 return -ENOMEM;
 135         return 0;
 136 }
 137
 138 void ext4_exit_es(void)
 139 {
 140         if (ext4_es_cachep)
 141                 kmem_cache_destroy(ext4_es_cachep);
 142 }
 143
 144 void ext4_es_init_tree(struct ext4_es_tree *tree)
 145 {
 146         tree->root = RB_ROOT;
 147         tree->cache_es = NULL;
 148 }
 149
 150 #ifdef ES_DEBUG__
 151 static void ext4_es_print_tree(struct inode *inode)
 152 {
 153         struct ext4_es_tree *tree;
 154         struct rb_node *node;
 155
 156         printk(KERN_DEBUG "status extents for inode %lu:", inode->i_ino);
 157         tree = &EXT4_I(inode)->i_es_tree;
 158         node = rb_first(&tree->root);
 159         while (node) {
 160                 struct extent_status *es;
 161                 es = rb_entry(node, struct extent_status, rb_node);
 162                 printk(KERN_DEBUG " [%u/%u)", es->start, es->len);
 163                 node = rb_next(node);
 164         }
 165         printk(KERN_DEBUG "\n");
 166 }
 167 #else
 168 #define ext4_es_print_tree(inode)
 169 #endif
 170
 171 static inline ext4_lblk_t extent_status_end(struct extent_status *es)
 172 {
 173         BUG_ON(es->start + es->len < es->start);
 174         return es->start + es->len - 1;
 175 }
 176
 177 /*
 178  * search through the tree for an delayed extent with a given offset.  If
 179  * it can't be found, try to find next extent.
 180  */
 181 static struct extent_status *__es_tree_search(struct rb_root *root,
 182                                               ext4_lblk_t offset)
 183 {
 184         struct rb_node *node = root->rb_node;
 185         struct extent_status *es = NULL;
 186
 187         while (node) {
 188                 es = rb_entry(node, struct extent_status, rb_node);
 189                 if (offset < es->start)
 190                         node = node->rb_left;
 191                 else if (offset > extent_status_end(es))
 192                         node = node->rb_right;
 193                 else
 194                         return es;
 195         }
 196
 197         if (es && offset < es->start)
 198                 return es;
 199
 200         if (es && offset > extent_status_end(es)) {
 201                 node = rb_next(&es->rb_node);
 202                 return node ? rb_entry(node, struct extent_status, rb_node) :
 203                               NULL;
 204         }
 205
 206         return NULL;
 207 }
 208
 209 /*
 210  * ext4_es_find_extent: find the 1st delayed extent covering @es->start
 211  * if it exists, otherwise, the next extent after @es->start.
 212  *
 213  * @inode: the inode which owns delayed extents
 214  * @es: delayed extent that we found
 215  *
 216  * Returns the first block of the next extent after es, otherwise
 217  * EXT_MAX_BLOCKS if no delay extent is found.
 218  * Delayed extent is returned via @es.
 219  */
 220 ext4_lblk_t ext4_es_find_extent(struct inode *inode, struct extent_status *es)
 221 {
 222         struct ext4_es_tree *tree = NULL;
 223         struct extent_status *es1 = NULL;
 224         struct rb_node *node;
 225         ext4_lblk_t ret = EXT_MAX_BLOCKS;
 226
 227         read_lock(&EXT4_I(inode)->i_es_lock);
 228         tree = &EXT4_I(inode)->i_es_tree;
 229
 230         /* find delay extent in cache firstly */
 231         if (tree->cache_es) {
 232                 es1 = tree->cache_es;
 233                 if (in_range(es->start, es1->start, es1->len)) {
 234                         es_debug("%u cached by [%u/%u)\n",
 235                                  es->start, es1->start, es1->len);
 236                         goto out;
 237                 }
 238         }
 239
 240         es->len = 0;
 241         es1 = __es_tree_search(&tree->root, es->start);
 242
 243 out:
 244         if (es1) {
 245                 tree->cache_es = es1;
 246                 es->start = es1->start;
 247                 es->len = es1->len;
 248                 node = rb_next(&es1->rb_node);
 249                 if (node) {
 250                         es1 = rb_entry(node, struct extent_status, rb_node);
 251                         ret = es1->start;
 252                 }
 253         }
 254
 255         read_unlock(&EXT4_I(inode)->i_es_lock);
 256         return ret;
 257 }
 258
 259 static struct extent_status *
 260 ext4_es_alloc_extent(ext4_lblk_t start, ext4_lblk_t len)
 261 {
 262         struct extent_status *es;
 263         es = kmem_cache_alloc(ext4_es_cachep, GFP_ATOMIC);
 264         if (es == NULL)
 265                 return NULL;
 266         es->start = start;
 267         es->len = len;
 268         return es;
 269 }
 270
 271 static void ext4_es_free_extent(struct extent_status *es)
 272 {
 273         kmem_cache_free(ext4_es_cachep, es);
 274 }
 275
 276 static struct extent_status *
 277 ext4_es_try_to_merge_left(struct ext4_es_tree *tree, struct extent_status *es)
 278 {
 279         struct extent_status *es1;
 280         struct rb_node *node;
 281
 282         node = rb_prev(&es->rb_node);
 283         if (!node)
 284                 return es;
 285
 286         es1 = rb_entry(node, struct extent_status, rb_node);
 287         if (es->start == extent_status_end(es1) + 1) {
 288                 es1->len += es->len;
 289                 rb_erase(&es->rb_node, &tree->root);
 290                 ext4_es_free_extent(es);
 291                 es = es1;
 292         }
 293
 294         return es;
 295 }
 296
 297 static struct extent_status *
 298 ext4_es_try_to_merge_right(struct ext4_es_tree *tree, struct extent_status *es)
 299 {
 300         struct extent_status *es1;
 301         struct rb_node *node;
 302
 303         node = rb_next(&es->rb_node);
 304         if (!node)
 305                 return es;
 306
 307         es1 = rb_entry(node, struct extent_status, rb_node);
 308         if (es1->start == extent_status_end(es) + 1) {
 309                 es->len += es1->len;
 310                 rb_erase(node, &tree->root);
 311                 ext4_es_free_extent(es1);
 312         }
 313
 314         return es;
 315 }
 316
 317 static int __es_insert_extent(struct ext4_es_tree *tree, ext4_lblk_t offset,
 318                               ext4_lblk_t len)
 319 {
 320         struct rb_node **p = &tree->root.rb_node;
 321         struct rb_node *parent = NULL;
 322         struct extent_status *es;
 323         ext4_lblk_t end = offset + len - 1;
 324
 325         BUG_ON(end < offset);
 326         es = tree->cache_es;
 327         if (es && offset == (extent_status_end(es) + 1)) {
 328                 es_debug("cached by [%u/%u)\n", es->start, es->len);
 329                 es->len += len;
 330                 es = ext4_es_try_to_merge_right(tree, es);
 331                 goto out;
 332         } else if (es && es->start == end + 1) {
 333                 es_debug("cached by [%u/%u)\n", es->start, es->len);
 334                 es->start = offset;
 335                 es->len += len;
 336                 es = ext4_es_try_to_merge_left(tree, es);
 337                 goto out;
 338         } else if (es && es->start <= offset &&
 339                    end <= extent_status_end(es)) {
 340                 es_debug("cached by [%u/%u)\n", es->start, es->len);
 341                 goto out;
 342         }
 343
 344         while (*p) {
 345                 parent = *p;
 346                 es = rb_entry(parent, struct extent_status, rb_node);
 347
 348                 if (offset < es->start) {
 349                         if (es->start == end + 1) {
 350                                 es->start = offset;
 351                                 es->len += len;
 352                                 es = ext4_es_try_to_merge_left(tree, es);
 353                                 goto out;
 354                         }
 355                         p = &(*p)->rb_left;
 356                 } else if (offset > extent_status_end(es)) {
 357                         if (offset == extent_status_end(es) + 1) {
 358                                 es->len += len;
 359                                 es = ext4_es_try_to_merge_right(tree, es);
 360                                 goto out;
 361                         }
 362                         p = &(*p)->rb_right;
 363                 } else {
 364                         if (extent_status_end(es) <= end)
 365                                 es->len = offset - es->start + len;
 366                         goto out;
 367                 }
 368         }
 369
 370         es = ext4_es_alloc_extent(offset, len);
 371         if (!es)
 372                 return -ENOMEM;
 373         rb_link_node(&es->rb_node, parent, p);
 374         rb_insert_color(&es->rb_node, &tree->root);
 375
 376 out:
 377         tree->cache_es = es;
 378         return 0;
 379 }
 380
 381 /*
 382  * ext4_es_insert_extent() adds a space to a delayed extent tree.
 383  * Caller holds inode->i_es_lock.
 384  *
 385  * ext4_es_insert_extent is called by ext4_da_write_begin and
 386  * ext4_es_remove_extent.
 387  *
 388  * Return 0 on success, error code on failure.
 389  */
 390 int ext4_es_insert_extent(struct inode *inode, ext4_lblk_t offset,
 391                           ext4_lblk_t len)
 392 {
 393         struct ext4_es_tree *tree;
 394         int err = 0;
 395
 396         es_debug("add [%u/%u) to extent status tree of inode %lu\n",
 397                  offset, len, inode->i_ino);
 398
 399         write_lock(&EXT4_I(inode)->i_es_lock);
 400         tree = &EXT4_I(inode)->i_es_tree;
 401         err = __es_insert_extent(tree, offset, len);
 402         write_unlock(&EXT4_I(inode)->i_es_lock);
 403
 404         ext4_es_print_tree(inode);
 405
 406         return err;
 407 }
 408
 409 /*
 410  * ext4_es_remove_extent() removes a space from a delayed extent tree.
 411  * Caller holds inode->i_es_lock.
 412  *
 413  * Return 0 on success, error code on failure.
 414  */
 415 int ext4_es_remove_extent(struct inode *inode, ext4_lblk_t offset,
 416                           ext4_lblk_t len)
 417 {
 418         struct rb_node *node;
 419         struct ext4_es_tree *tree;
 420         struct extent_status *es;
 421         struct extent_status orig_es;
 422         ext4_lblk_t len1, len2, end;
 423         int err = 0;
 424
 425         es_debug("remove [%u/%u) from extent status tree of inode %lu\n",
 426                  offset, len, inode->i_ino);
 427
 428         end = offset + len - 1;
 429         BUG_ON(end < offset);
 430         write_lock(&EXT4_I(inode)->i_es_lock);
 431         tree = &EXT4_I(inode)->i_es_tree;
 432         es = __es_tree_search(&tree->root, offset);
 433         if (!es)
 434                 goto out;
 435         if (es->start > end)
 436                 goto out;
 437
 438         /* Simply invalidate cache_es. */
 439         tree->cache_es = NULL;
 440
 441         orig_es.start = es->start;
 442         orig_es.len = es->len;
 443         len1 = offset > es->start ? offset - es->start : 0;
 444         len2 = extent_status_end(es) > end ?
 445                extent_status_end(es) - end : 0;
 446         if (len1 > 0)
 447                 es->len = len1;
 448         if (len2 > 0) {
 449                 if (len1 > 0) {
 450                         err = __es_insert_extent(tree, end + 1, len2);
 451                         if (err) {
 452                                 es->start = orig_es.start;
 453                                 es->len = orig_es.len;
 454                                 goto out;
 455                         }
 456                 } else {
 457                         es->start = end + 1;
 458                         es->len = len2;
 459                 }
 460                 goto out;
 461         }
 462
 463         if (len1 > 0) {
 464                 node = rb_next(&es->rb_node);
 465                 if (node)
 466                         es = rb_entry(node, struct extent_status, rb_node);
 467                 else
 468                         es = NULL;
 469         }
 470
 471         while (es && extent_status_end(es) <= end) {
 472                 node = rb_next(&es->rb_node);
 473                 rb_erase(&es->rb_node, &tree->root);
 474                 ext4_es_free_extent(es);
 475                 if (!node) {
 476                         es = NULL;
 477                         break;
 478                 }
 479                 es = rb_entry(node, struct extent_status, rb_node);
 480         }
 481
 482         if (es && es->start < end + 1) {
 483                 len1 = extent_status_end(es) - end;
 484                 es->start = end + 1;
 485                 es->len = len1;
 486         }
 487
 488 out:
 489         write_unlock(&EXT4_I(inode)->i_es_lock);
 490         ext4_es_print_tree(inode);
 491         return err;
 492 }