defrag-02-ext4-alloc-contig-blocks-with-mballoc

   1 ext4: online defrag -- Allocate new contiguous blocks with mballoc.
   2
   3 From: Akira Fujita <a-fujita@rs.jp.nec.com>
   4
   5 Search contiguous free blocks with multi-block allocation
   6 and allocate them for the temporary inode.
   7
   8 Signed-off-by: Akira Fujita <a-fujita@rs.jp.nec.com>
   9 Signed-off-by: Takashi Sato <t-sato@yk.jp.nec.com>
  10 ---
  11  fs/ext4/defrag.c       |  224 +++++++++++++++++++++++++++++++++++++++++++++++-
  12  fs/ext4/ext4.h         |    3 +
  13  fs/ext4/ext4_extents.h |    3 +
  14  fs/ext4/extents.c      |    4 +-
  15  4 files changed, 231 insertions(+), 3 deletions(-)
  16
  17 diff --git a/fs/ext4/defrag.c b/fs/ext4/defrag.c
  18 index 1e36193..729f001 100644
  19 --- a/fs/ext4/defrag.c
  20 +++ b/fs/ext4/defrag.c
  21 @@ -91,6 +91,84 @@ err:
  22  }
  23
  24  /**
  25 + * ext4_defrag_fill_ar - Prepare to multiple block allocate for tmp inode
  26 + *
  27 + * @org_inode:         original inode
  28 + * @dest_inode:                temporary inode
  29 + * @ar:                        allocation request for multiple block allocation
  30 + * @org_path:          indicating the original inode's extent
  31 + * @dest_path:         indicating the temporary inode's extent
  32 + * @req_blocks:                contiguous blocks count we need
  33 + * @iblock:            target file offset
  34 + *
  35 + */
  36 +static void
  37 +ext4_defrag_fill_ar(struct inode *org_inode, struct inode *dest_inode,
  38 +                       struct ext4_allocation_request *ar,
  39 +                       struct ext4_ext_path *org_path,
  40 +                       struct ext4_ext_path *dest_path,
  41 +                       ext4_fsblk_t req_blocks, ext4_lblk_t iblock)
  42 +{
  43 +       ar->inode = dest_inode;
  44 +       ar->len = req_blocks;
  45 +       ar->logical = iblock;
  46 +       ar->flags = EXT4_MB_HINT_DATA | EXT4_MB_HINT_RESERVED
  47 +               | EXT4_MB_HINT_NOPREALLOC;
  48 +       ar->lleft = 0;
  49 +       ar->pleft = 0;
  50 +       ar->lright = 0;
  51 +       ar->pright = 0;
  52 +
  53 +       ar->goal = ext4_ext_find_goal(dest_inode, dest_path, iblock);
  54 +}
  55 +
  56 +/**
  57 + * ext4_defrag_alloc_blocks - Allocate contiguous blocks to temporary inode
  58 + *
  59 + * @handle:            journal handle
  60 + * @org_inode:         original inode
  61 + * @dest_inode:                temporary inode for multiple block allocation
  62 + * @ar:                        allocation request for multiple block allocation
  63 + * @dest_path:         indicating the temporary inode's extent
  64 + * @newblock:          start offset of contiguous blocks
  65 + *
  66 + * This function returns 0 if succeed, otherwise returns error value.
  67 + */
  68 +static int
  69 +ext4_defrag_alloc_blocks(handle_t *handle, struct inode *org_inode,
  70 +               struct inode *dest_inode, struct ext4_allocation_request *ar,
  71 +               struct ext4_ext_path *dest_path, ext4_fsblk_t *newblock)
  72 +{
  73 +       struct super_block *sb = org_inode->i_sb;
  74 +       struct buffer_head *bh = NULL;
  75 +       int err, i, credits = 0;
  76 +
  77 +       credits = ext4_ext_calc_credits_for_single_extent(dest_inode,
  78 +                                                         ar->len, dest_path);
  79 +       err = ext4_ext_journal_restart(handle, credits);
  80 +       if (err)
  81 +               return err;
  82 +
  83 +       *newblock = ext4_mb_new_blocks(handle, ar, &err);
  84 +       if (err)
  85 +               return err;
  86 +
  87 +       /*
  88 +        * Dirty buffer_head causes the overwriting
  89 +        * if ext4_mb_new_blocks() allocates the block
  90 +        * which used to be the metadata block.
  91 +        * We should call unmap_underlying_metadata()
  92 +        * to clear the dirty flag.
  93 +        */
  94 +       for (i = 0; i < ar->len; i++) {
  95 +               bh = sb_find_get_block(sb, *newblock + i);
  96 +               unmap_underlying_metadata(sb->s_bdev, *newblock + i);
  97 +       }
  98 +
  99 +       return err;
 100 +}
 101 +
 102 +/**
 103   * ext4_defrag_partial - Defrag a file per page
 104   *
 105   * @tmp_inode:                 temporary inode
 106 @@ -111,6 +189,69 @@ ext4_defrag_partial(struct inode *tmp_inode, struct file *filp,
 107  }
 108
 109  /**
 110 + * ext4_defrag_comp_ext_count- Check whether fragments are improved or not
 111 + *
 112 + * @org_inode:         original inode
 113 + * @path:              the structure holding some info about
 114 + *                     original extent tree
 115 + * @tar_end:           the last block number of the allocated blocks
 116 + * @sum_tmp:           the extents count  in the allocated blocks
 117 + *
 118 + * This function returns the values as below.
 119 + *     0 (improved)
 120 + *     1 (not improved)
 121 + *     negative value (error case)
 122 + */
 123 +static int
 124 +ext4_defrag_comp_ext_count(struct inode *org_inode,
 125 +                       struct ext4_ext_path *org_path, ext4_lblk_t tar_end,
 126 +                       int sum_tmp)
 127 +{
 128 +       struct ext4_extent *ext = NULL;
 129 +       int depth = ext_depth(org_inode);
 130 +       int last_extent = 0;
 131 +       int sum_org = 0;
 132 +       int ret = 0;
 133 +
 134 +       ext = org_path[depth].p_ext;
 135 +
 136 +       /*
 137 +        * Compare the number of the newly allocated extents to
 138 +        * that of existing one.
 139 +        */
 140 +       while (1) {
 141 +               if (!last_extent)
 142 +                       ++sum_org;
 143 +               if (tar_end <= (le32_to_cpu(ext->ee_block) +
 144 +                              le16_to_cpu(ext->ee_len) - 1) ||
 145 +                              last_extent) {
 146 +                       /*
 147 +                        * If the goal has not been set and the fragmentation
 148 +                        * is not improved any more, defrag fails.
 149 +                        */
 150 +                       if (sum_org == sum_tmp) {
 151 +                               /* Not improved */
 152 +                               ret = 1;
 153 +                       } else if (sum_org < sum_tmp) {
 154 +                               /* Fragment increased */
 155 +                               ret = -ENOSPC;
 156 +                               printk(KERN_ERR "ext4 defrag: "
 157 +                                       "Insufficient free blocks\n");
 158 +                       }
 159 +                       break;
 160 +               }
 161 +               last_extent =
 162 +                       ext4_defrag_next_extent(org_inode, org_path, &ext);
 163 +               if (last_extent < 0) {
 164 +                       ret = last_extent;
 165 +                       break;
 166 +               }
 167 +       }
 168 +
 169 +       return ret;
 170 +}
 171 +
 172 +/**
 173   * ext4_defrag_new_extent_tree - Get contiguous blocks and build an extent tree
 174   *
 175   * @org_inode:         original inode
 176 @@ -130,7 +271,88 @@ ext4_defrag_new_extent_tree(struct inode *org_inode, struct inode *tmp_inode,
 177                         struct ext4_ext_path *org_path, ext4_lblk_t req_start,
 178                         ext4_lblk_t req_blocks, ext4_lblk_t iblock)
 179  {
 180 -       return 0;
 181 +       handle_t *handle;
 182 +       struct ext4_sb_info *sbi = EXT4_SB(org_inode->i_sb);
 183 +       struct ext4_extent_header *eh = NULL;
 184 +       struct ext4_allocation_request ar;
 185 +       struct ext4_ext_path *dest_path = NULL;
 186 +       struct ext4_extent newex;
 187 +       ext4_fsblk_t alloc_total = 0;
 188 +       ext4_fsblk_t newblock = 0;
 189 +       ext4_lblk_t req_end = req_start + req_blocks - 1;
 190 +       ext4_lblk_t rest_blocks = 0;
 191 +       int sum_tmp = 0;
 192 +       int metadata = 1;
 193 +       int ret;
 194 +
 195 +       eh = ext_inode_hdr(tmp_inode);
 196 +       eh->eh_depth = 0;
 197 +
 198 +       dest_path = ext4_ext_find_extent(tmp_inode, iblock, NULL);
 199 +       if (IS_ERR(dest_path)) {
 200 +               ret = PTR_ERR(dest_path);
 201 +               dest_path = NULL;
 202 +               goto out2;
 203 +       }
 204 +
 205 +       /* Fill struct ext4_allocation_request with necessary info */
 206 +       ext4_defrag_fill_ar(org_inode, tmp_inode, &ar, org_path,
 207 +                               dest_path, req_blocks, iblock);
 208 +
 209 +       handle = ext4_journal_start(tmp_inode, 0);
 210 +       if (IS_ERR(handle)) {
 211 +               ret = PTR_ERR(handle);
 212 +               goto out2;
 213 +       }
 214 +
 215 +       while (alloc_total != req_blocks) {
 216 +               /* Allocate blocks */
 217 +               ret = ext4_defrag_alloc_blocks(handle, org_inode, tmp_inode,
 218 +                                               &ar, dest_path, &newblock);
 219 +               if (ret < 0)
 220 +                       goto out;
 221 +               /* Claimed blocks are already reserved */
 222 +               EXT4_I(ar.inode)->i_delalloc_reserved_flag = 1;
 223 +
 224 +               alloc_total += ar.len;
 225 +               rest_blocks = req_blocks - alloc_total;
 226 +
 227 +               newex.ee_block = cpu_to_le32(alloc_total - ar.len);
 228 +               ext4_ext_store_pblock(&newex, newblock);
 229 +               newex.ee_len = cpu_to_le16(ar.len);
 230 +
 231 +               ret = ext4_ext_insert_extent(handle, tmp_inode,
 232 +                                               dest_path, &newex);
 233 +               if (ret < 0)
 234 +                       goto out;
 235 +
 236 +               ar.goal = newblock + ar.len;
 237 +               ar.len = req_blocks - alloc_total;
 238 +               sum_tmp++;
 239 +       }
 240 +
 241 +       ret = ext4_defrag_comp_ext_count(org_inode, org_path, req_end,
 242 +                                       sum_tmp);
 243 +
 244 +out:
 245 +       if (ret < 0 && ar.len)
 246 +               ext4_free_blocks(handle, tmp_inode, newblock, ar.len, metadata);
 247 +       /*
 248 +        * Update dirty-blocks counter if we cannot allocate the all of
 249 +        * requested blocks.
 250 +        */
 251 +       if (rest_blocks)
 252 +               percpu_counter_sub(&sbi->s_dirtyblocks_counter, rest_blocks);
 253 +
 254 +       ext4_journal_stop(handle);
 255 +
 256 +out2:
 257 +       if (dest_path) {
 258 +               ext4_ext_drop_refs(dest_path);
 259 +               kfree(dest_path);
 260 +       }
 261 +
 262 +       return ret;
 263  }
 264
 265  /**
 266 diff --git a/fs/ext4/ext4.h b/fs/ext4/ext4.h
 267 index 30e3195..aa3b639 100644
 268 --- a/fs/ext4/ext4.h
 269 +++ b/fs/ext4/ext4.h
 270 @@ -326,6 +326,7 @@ struct ext4_ext_defrag_data {
 271         ext4_fsblk_t goal;              /* block offset for allocation */
 272  };
 273
 274 +#define EXT4_TRANS_META_BLOCKS 4 /* bitmap + group desc + sb + inode */
 275
 276  /*
 277   *  Mount options
 278 @@ -1170,6 +1171,9 @@ extern void ext4_used_dirs_set(struct super_block *sb,
 279  extern void ext4_itable_unused_set(struct super_block *sb,
 280                                    struct ext4_group_desc *bg, __u16 count);
 281
 282 +/* extents.c */
 283 +extern int ext4_ext_journal_restart(handle_t *handle, int needed);
 284 +
 285  /* defrag.c */
 286  extern int ext4_defrag(struct file *filp, ext4_lblk_t block_start,
 287                         ext4_lblk_t defrag_size);
 288 diff --git a/fs/ext4/ext4_extents.h b/fs/ext4/ext4_extents.h
 289 index a28d8d2..39e043b 100644
 290 --- a/fs/ext4/ext4_extents.h
 291 +++ b/fs/ext4/ext4_extents.h
 292 @@ -247,6 +247,9 @@ extern int ext4_ext_search_right(struct inode *, struct ext4_ext_path *,
 293                                                 ext4_lblk_t *, ext4_fsblk_t *);
 294  extern void ext4_ext_drop_refs(struct ext4_ext_path *);
 295  extern ext4_fsblk_t ext_pblock(struct ext4_extent *ex);
 296 +extern ext4_fsblk_t ext4_ext_find_goal(struct inode *inode,
 297 +                                       struct ext4_ext_path *path,
 298 +                                       ext4_lblk_t block);
 299
 300  #endif /* _EXT4_EXTENTS */
 301
 302 diff --git a/fs/ext4/extents.c b/fs/ext4/extents.c
 303 index 406cab9..dde234f 100644
 304 --- a/fs/ext4/extents.c
 305 +++ b/fs/ext4/extents.c
 306 @@ -93,7 +93,7 @@ static void ext4_idx_store_pblock(struct ext4_extent_idx *ix, ext4_fsblk_t pb)
 307         ix->ei_leaf_hi = cpu_to_le16((unsigned long) ((pb >> 31) >> 1) & 0xffff);
 308  }
 309
 310 -static int ext4_ext_journal_restart(handle_t *handle, int needed)
 311 +int ext4_ext_journal_restart(handle_t *handle, int needed)
 312  {
 313         int err;
 314
 315 @@ -142,7 +142,7 @@ static int ext4_ext_dirty(handle_t *handle, struct inode *inode,
 316         return err;
 317  }
 318
 319 -static ext4_fsblk_t ext4_ext_find_goal(struct inode *inode,
 320 +ext4_fsblk_t ext4_ext_find_goal(struct inode *inode,
 321                               struct ext4_ext_path *path,
 322                               ext4_lblk_t block)
 323  {