extent-overlap-bugfix

   1 [PATCH 1/1] Extent overlap bugfix in ext4
   2
   3 Note: This patch is being resubmitted as part of the recall of all the
   4 patches for ext4. It uses 2.6.20-rc5 version as the base.
   5
   6 Problem Description:
   7 -------------------
   8 The ext4_ext_get_blocks() and ext4_ext_insert_extent() routines do not
   9 have a complete check for extent overlap, when a new extent needs to be
  10 inserted in an inode. With the current implementation, an overlap is
  11 possible when the new extent being inserted has ee_block that is not
  12 part of any of the existing extents, but the tail/center portion of this
  13 new extent _is_. This is possible only when we are writing/preallocating
  14 blocks across a hole.
  15 Though this problem was discovered while stress testing persistent
  16 preallocation patches (using modified fsx-linux); this essentially is an
  17 independent problem and should be fixed by a separate patch. Hence this
  18 fix.
  19
  20 The Fix:
  21 -------
  22 The suggested patch fixes this by having a check in get_blocks() for
  23 finding if the new extent overlaps with an existing one. If it does, the
  24 length of the new extent is modified such that the overlap does not
  25 happen at all.
  26
  27 Other option discussed:
  28 ----------------------
  29 The other option discussed was to not to use ext4_ext_get_blocks() for
  30 persistent preallocation, and use ext4_ext_walk_space() with some helper
  31 function instead. This was considered because walk_space() already does
  32 a complete check for overlap and hence we can avoid duplication of this
  33 part of the logic in get_blocks(). But, again, there will be a
  34 duplication of code in the new helper function that may be required for
  35 this (like, calling ext4_new_blocks() and ext4_ext_insert_extent()).
  36
  37 Updates from the original (first) version:
  38 -----------------------------------------
  39 This patch takes care of following review comments from Mingming, Alex
  40 and Suparna:
  41 (a) Not to use ext4_ext_find_extent() in check_overlap(), since it is an
  42 expensive operation.
  43 (b) Use "unsigned long" for (logical) block numbers everywhere.
  44 (c) Return true/false by check_overlap(), rather than extent pointer or
  45 the block number.
  46 (d) Update the length of the new extent in check_overlap(), if there is
  47 an overlap detected.
  48 (e) No need to have a check in insert_extent() (i.e. no BUG_ON required)
  49
  50
  51 Here is the patch:
  52
  53 Signed-off-by: Amit Arora <aarora@in.ibm.com>
  54 ---
  55
  56  fs/ext4/extents.c               |   50 +++++++++++++++++++++++++++++++++++++--
  57  include/linux/ext4_fs_extents.h |    1 +
  58  2 files changed, 49 insertions(+), 2 deletions(-)
  59
  60 diff --git a/fs/ext4/extents.c b/fs/ext4/extents.c
  61 index dc2724f..2f958fb 100644
  62 --- a/fs/ext4/extents.c
  63 +++ b/fs/ext4/extents.c
  64 @@ -1129,6 +1129,45 @@ ext4_can_extents_be_merged(struct inode *inode, struct ext4_extent *ex1,
  65  }
  66
  67  /*
  68 + * ext4_ext_check_overlap:
  69 + * check if a portion of the "newext" extent overlaps with an
  70 + * existing extent.
  71 + *
  72 + * If there is an overlap discovered, it updates the length of the newext
  73 + * such that there will be no overlap, and then returns 1.
  74 + * If there is no overlap found, it returns 0.
  75 + */
  76 +unsigned int ext4_ext_check_overlap(struct inode *inode,
  77 +                                       struct ext4_extent *newext,
  78 +                                       struct ext4_ext_path *path)
  79 +{
  80 +       unsigned long b1, b2;
  81 +       unsigned int depth, len1;
  82 +
  83 +       b1 = le32_to_cpu(newext->ee_block);
  84 +       len1 = le16_to_cpu(newext->ee_len);
  85 +       depth = ext_depth(inode);
  86 +       if (!path[depth].p_ext)
  87 +               goto out;
  88 +       b2 = le32_to_cpu(path[depth].p_ext->ee_block);
  89 +
  90 +       /* get the next allocated block if the extent in the path
  91 +        * is before the requested block(s) */
  92 +       if (b2 < b1) {
  93 +               b2 = ext4_ext_next_allocated_block(path);
  94 +               if (b2 == EXT_MAX_BLOCK)
  95 +                       goto out;
  96 +       }
  97 +
  98 +       if (b1 + len1 > b2) {
  99 +               newext->ee_len = cpu_to_le16(b2 - b1);
 100 +               return 1;
 101 +       }
 102 +out:
 103 +       return 0;
 104 +}
 105 +
 106 +/*
 107   * ext4_ext_insert_extent:
 108   * tries to merge requsted extent into the existing extent or
 109   * inserts requested extent as new one into the tree,
 110 @@ -2032,7 +2071,15 @@ int ext4_ext_get_blocks(handle_t *handle, struct inode *inode,
 111
 112         /* allocate new block */
 113         goal = ext4_ext_find_goal(inode, path, iblock);
 114 -       allocated = max_blocks;
 115 +
 116 +       /* Check if we can really insert (iblock)::(iblock+max_blocks) extent */
 117 +       newex.ee_block = cpu_to_le32(iblock);
 118 +       newex.ee_len = cpu_to_le16(max_blocks);
 119 +       err = ext4_ext_check_overlap(inode, &newex, path);
 120 +       if (err)
 121 +               allocated = le16_to_cpu(newex.ee_len);
 122 +       else
 123 +               allocated = max_blocks;
 124         newblock = ext4_new_blocks(handle, inode, goal, &allocated, &err);
 125         if (!newblock)
 126                 goto out2;
 127 @@ -2040,7 +2087,6 @@ int ext4_ext_get_blocks(handle_t *handle, struct inode *inode,
 128                         goal, newblock, allocated);
 129
 130         /* try to insert new extent into found leaf and return */
 131 -       newex.ee_block = cpu_to_le32(iblock);
 132         ext4_ext_store_pblock(&newex, newblock);
 133         newex.ee_len = cpu_to_le16(allocated);
 134         err = ext4_ext_insert_extent(handle, inode, path, &newex);
 135 diff --git a/include/linux/ext4_fs_extents.h b/include/linux/ext4_fs_extents.h
 136 index a41cc24..0226703 100644
 137 --- a/include/linux/ext4_fs_extents.h
 138 +++ b/include/linux/ext4_fs_extents.h
 139 @@ -190,6 +190,7 @@ ext4_ext_invalidate_cache(struct inode *inode)
 140
 141  extern int ext4_extent_tree_init(handle_t *, struct inode *);
 142  extern int ext4_ext_calc_credits_for_insert(struct inode *, struct ext4_ext_path *);
 143 +extern unsigned int ext4_ext_check_overlap(struct inode *, struct ext4_extent *, struct ext4_ext_path *);
 144  extern int ext4_ext_insert_extent(handle_t *, struct inode *, struct ext4_ext_path *, struct ext4_extent *);
 145  extern int ext4_ext_walk_space(struct inode *, unsigned long, unsigned long, ext_prepare_callback, void *);
 146  extern struct ext4_ext_path * ext4_ext_find_extent(struct inode *, int, struct ext4_ext_path *);