add-new-pending-reservation-mechanism

   1 ext4: add new pending reservation mechanism
   2
   3 From: Eric Whitney <enwlinux@gmail.com>
   4
   5 Add new pending reservation mechanism to help manage reserved cluster
   6 accounting.  Its primary function is to avoid the need to read extents
   7 from the disk when invalidating pages as a result of a truncate, punch
   8 hole, or collapse range operation.
   9
  10 Signed-off-by: Eric Whitney <enwlinux@gmail.com>
  11 Signed-off-by: Theodore Ts'o <tytso@mit.edu>
  12 ---
  13  fs/ext4/ext4.h           |   3 +
  14  fs/ext4/extents_status.c | 187 +++++++++++++++++++++++++++++++++++++++++++++++
  15  fs/ext4/extents_status.h |  51 +++++++++++++
  16  fs/ext4/super.c          |   8 ++
  17  4 files changed, 249 insertions(+)
  18
  19 diff --git a/fs/ext4/ext4.h b/fs/ext4/ext4.h
  20 index ad2c215720be..fc0f41dbf90b 100644
  21 --- a/fs/ext4/ext4.h
  22 +++ b/fs/ext4/ext4.h
  23 @@ -1030,6 +1030,9 @@ struct ext4_inode_info {
  24         ext4_lblk_t i_da_metadata_calc_last_lblock;
  25         int i_da_metadata_calc_len;
  26
  27 +       /* pending cluster reservations for bigalloc file systems */
  28 +       struct ext4_pending_tree i_pending_tree;
  29 +
  30         /* on-disk additional length */
  31         __u16 i_extra_isize;
  32
  33 diff --git a/fs/ext4/extents_status.c b/fs/ext4/extents_status.c
  34 index 8530fbd3012d..194785ce890a 100644
  35 --- a/fs/ext4/extents_status.c
  36 +++ b/fs/ext4/extents_status.c
  37 @@ -142,6 +142,7 @@
  38   */
  39
  40  static struct kmem_cache *ext4_es_cachep;
  41 +static struct kmem_cache *ext4_pending_cachep;
  42
  43  static int __es_insert_extent(struct inode *inode, struct extent_status *newes);
  44  static int __es_remove_extent(struct inode *inode, ext4_lblk_t lblk,
  45 @@ -1365,3 +1366,189 @@ static int es_reclaim_extents(struct ext4_inode_info *ei, int *nr_to_scan)
  46         ei->i_es_tree.cache_es = NULL;
  47         return nr_shrunk;
  48  }
  49 +
  50 +#ifdef ES_DEBUG__
  51 +static void ext4_print_pending_tree(struct inode *inode)
  52 +{
  53 +       struct ext4_pending_tree *tree;
  54 +       struct rb_node *node;
  55 +       struct pending_reservation *pr;
  56 +
  57 +       printk(KERN_DEBUG "pending reservations for inode %lu:", inode->i_ino);
  58 +       tree = &EXT4_I(inode)->i_pending_tree;
  59 +       node = rb_first(&tree->root);
  60 +       while (node) {
  61 +               pr = rb_entry(node, struct pending_reservation, rb_node);
  62 +               printk(KERN_DEBUG " %u", pr->lclu);
  63 +               node = rb_next(node);
  64 +       }
  65 +       printk(KERN_DEBUG "\n");
  66 +}
  67 +#else
  68 +#define ext4_print_pending_tree(inode)
  69 +#endif
  70 +
  71 +int __init ext4_init_pending(void)
  72 +{
  73 +       ext4_pending_cachep = kmem_cache_create("ext4_pending_reservation",
  74 +                                          sizeof(struct pending_reservation),
  75 +                                          0, (SLAB_RECLAIM_ACCOUNT), NULL);
  76 +       if (ext4_pending_cachep == NULL)
  77 +               return -ENOMEM;
  78 +       return 0;
  79 +}
  80 +
  81 +void ext4_exit_pending(void)
  82 +{
  83 +       kmem_cache_destroy(ext4_pending_cachep);
  84 +}
  85 +
  86 +void ext4_init_pending_tree(struct ext4_pending_tree *tree)
  87 +{
  88 +       tree->root = RB_ROOT;
  89 +}
  90 +
  91 +/*
  92 + * __get_pending - retrieve a pointer to a pending reservation
  93 + *
  94 + * @inode - file containing the pending cluster reservation
  95 + * @lclu - logical cluster of interest
  96 + *
  97 + * Returns a pointer to a pending reservation if it's a member of
  98 + * the set, and NULL if not.  Must be called holding i_es_lock.
  99 + */
 100 +static struct pending_reservation *__get_pending(struct inode *inode,
 101 +                                                ext4_lblk_t lclu)
 102 +{
 103 +       struct ext4_pending_tree *tree;
 104 +       struct rb_node *node;
 105 +       struct pending_reservation *pr = NULL;
 106 +
 107 +       tree = &EXT4_I(inode)->i_pending_tree;
 108 +       node = (&tree->root)->rb_node;
 109 +
 110 +       while (node) {
 111 +               pr = rb_entry(node, struct pending_reservation, rb_node);
 112 +               if (lclu < pr->lclu)
 113 +                       node = node->rb_left;
 114 +               else if (lclu > pr->lclu)
 115 +                       node = node->rb_right;
 116 +               else if (lclu == pr->lclu)
 117 +                       return pr;
 118 +       }
 119 +       return NULL;
 120 +}
 121 +
 122 +/*
 123 + * __insert_pending - adds a pending cluster reservation to the set of
 124 + *                    pending reservations
 125 + *
 126 + * @inode - file containing the cluster
 127 + * @lblk - logical block in the cluster to be added
 128 + *
 129 + * Returns 0 on successful insertion and -ENOMEM on failure.  If the
 130 + * pending reservation is already in the set, returns successfully.
 131 + */
 132 +static int __insert_pending(struct inode *inode, ext4_lblk_t lblk)
 133 +{
 134 +       struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
 135 +       struct ext4_pending_tree *tree = &EXT4_I(inode)->i_pending_tree;
 136 +       struct rb_node **p = &tree->root.rb_node;
 137 +       struct rb_node *parent = NULL;
 138 +       struct pending_reservation *pr;
 139 +       ext4_lblk_t lclu;
 140 +       int ret = 0;
 141 +
 142 +       lclu = EXT4_B2C(sbi, lblk);
 143 +       /* search to find parent for insertion */
 144 +       while (*p) {
 145 +               parent = *p;
 146 +               pr = rb_entry(parent, struct pending_reservation, rb_node);
 147 +
 148 +               if (lclu < pr->lclu) {
 149 +                       p = &(*p)->rb_left;
 150 +               } else if (lclu > pr->lclu) {
 151 +                       p = &(*p)->rb_right;
 152 +               } else {
 153 +                       /* pending reservation already inserted */
 154 +                       goto out;
 155 +               }
 156 +       }
 157 +
 158 +       pr = kmem_cache_alloc(ext4_pending_cachep, GFP_ATOMIC);
 159 +       if (pr == NULL) {
 160 +               ret = -ENOMEM;
 161 +               goto out;
 162 +       }
 163 +       pr->lclu = lclu;
 164 +
 165 +       rb_link_node(&pr->rb_node, parent, p);
 166 +       rb_insert_color(&pr->rb_node, &tree->root);
 167 +
 168 +out:
 169 +       return ret;
 170 +}
 171 +
 172 +/*
 173 + * __remove_pending - removes a pending cluster reservation from the set
 174 + *                    of pending reservations
 175 + *
 176 + * @inode - file containing the cluster
 177 + * @lblk - logical block in the pending cluster reservation to be removed
 178 + *
 179 + * Returns successfully if pending reservation is not a member of the set.
 180 + */
 181 +static void __remove_pending(struct inode *inode, ext4_lblk_t lblk)
 182 +{
 183 +       struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
 184 +       struct pending_reservation *pr;
 185 +       struct ext4_pending_tree *tree;
 186 +
 187 +       pr = __get_pending(inode, EXT4_B2C(sbi, lblk));
 188 +       if (pr != NULL) {
 189 +               tree = &EXT4_I(inode)->i_pending_tree;
 190 +               rb_erase(&pr->rb_node, &tree->root);
 191 +               kmem_cache_free(ext4_pending_cachep, pr);
 192 +       }
 193 +}
 194 +
 195 +/*
 196 + * ext4_remove_pending - removes a pending cluster reservation from the set
 197 + *                       of pending reservations
 198 + *
 199 + * @inode - file containing the cluster
 200 + * @lblk - logical block in the pending cluster reservation to be removed
 201 + *
 202 + * Locking for external use of __remove_pending.
 203 + */
 204 +void ext4_remove_pending(struct inode *inode, ext4_lblk_t lblk)
 205 +{
 206 +       struct ext4_inode_info *ei = EXT4_I(inode);
 207 +
 208 +       write_lock(&ei->i_es_lock);
 209 +       __remove_pending(inode, lblk);
 210 +       write_unlock(&ei->i_es_lock);
 211 +}
 212 +
 213 +/*
 214 + * ext4_is_pending - determine whether a cluster has a pending reservation
 215 + *                   on it
 216 + *
 217 + * @inode - file containing the cluster
 218 + * @lblk - logical block in the cluster
 219 + *
 220 + * Returns true if there's a pending reservation for the cluster in the
 221 + * set of pending reservations, and false if not.
 222 + */
 223 +bool ext4_is_pending(struct inode *inode, ext4_lblk_t lblk)
 224 +{
 225 +       struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
 226 +       struct ext4_inode_info *ei = EXT4_I(inode);
 227 +       bool ret;
 228 +
 229 +       read_lock(&ei->i_es_lock);
 230 +       ret = (bool)(__get_pending(inode, EXT4_B2C(sbi, lblk)) != NULL);
 231 +       read_unlock(&ei->i_es_lock);
 232 +
 233 +       return ret;
 234 +}
 235 diff --git a/fs/ext4/extents_status.h b/fs/ext4/extents_status.h
 236 index df9628c3ec3b..379b7171c67c 100644
 237 --- a/fs/ext4/extents_status.h
 238 +++ b/fs/ext4/extents_status.h
 239 @@ -78,6 +78,51 @@ struct ext4_es_stats {
 240         struct percpu_counter es_stats_shk_cnt;
 241  };
 242
 243 +/*
 244 + * Pending cluster reservations for bigalloc file systems
 245 + *
 246 + * A cluster with a pending reservation is a logical cluster shared by at
 247 + * least one extent in the extents status tree with delayed and unwritten
 248 + * status and at least one other written or unwritten extent.  The
 249 + * reservation is said to be pending because a cluster reservation would
 250 + * have to be taken in the event all blocks in the cluster shared with
 251 + * written or unwritten extents were deleted while the delayed and
 252 + * unwritten blocks remained.
 253 + *
 254 + * The set of pending cluster reservations is an auxiliary data structure
 255 + * used with the extents status tree to implement reserved cluster/block
 256 + * accounting for bigalloc file systems.  The set is kept in memory and
 257 + * records all pending cluster reservations.
 258 + *
 259 + * Its primary function is to avoid the need to read extents from the
 260 + * disk when invalidating pages as a result of a truncate, punch hole, or
 261 + * collapse range operation.  Page invalidation requires a decrease in the
 262 + * reserved cluster count if it results in the removal of all delayed
 263 + * and unwritten extents (blocks) from a cluster that is not shared with a
 264 + * written or unwritten extent, and no decrease otherwise.  Determining
 265 + * whether the cluster is shared can be done by searching for a pending
 266 + * reservation on it.
 267 + *
 268 + * Secondarily, it provides a potentially faster method for determining
 269 + * whether the reserved cluster count should be increased when a physical
 270 + * cluster is deallocated as a result of a truncate, punch hole, or
 271 + * collapse range operation.  The necessary information is also present
 272 + * in the extents status tree, but might be more rapidly accessed in
 273 + * the pending reservation set in many cases due to smaller size.
 274 + *
 275 + * The pending cluster reservation set is implemented as a red-black tree
 276 + * with the goal of minimizing per page search time overhead.
 277 + */
 278 +
 279 +struct pending_reservation {
 280 +       struct rb_node rb_node;
 281 +       ext4_lblk_t lclu;
 282 +};
 283 +
 284 +struct ext4_pending_tree {
 285 +       struct rb_root root;
 286 +};
 287 +
 288  extern int __init ext4_init_es(void);
 289  extern void ext4_exit_es(void);
 290  extern void ext4_es_init_tree(struct ext4_es_tree *tree);
 291 @@ -182,4 +227,10 @@ extern void ext4_es_unregister_shrinker(struct ext4_sb_info *sbi);
 292
 293  extern int ext4_seq_es_shrinker_info_show(struct seq_file *seq, void *v);
 294
 295 +extern int __init ext4_init_pending(void);
 296 +extern void ext4_exit_pending(void);
 297 +extern void ext4_init_pending_tree(struct ext4_pending_tree *tree);
 298 +extern void ext4_remove_pending(struct inode *inode, ext4_lblk_t lblk);
 299 +extern bool ext4_is_pending(struct inode *inode, ext4_lblk_t lblk);
 300 +
 301  #endif /* _EXT4_EXTENTS_STATUS_H */
 302 diff --git a/fs/ext4/super.c b/fs/ext4/super.c
 303 index 1145109968ef..faf293ed8060 100644
 304 --- a/fs/ext4/super.c
 305 +++ b/fs/ext4/super.c
 306 @@ -1040,6 +1040,7 @@ static struct inode *ext4_alloc_inode(struct super_block *sb)
 307         ei->i_da_metadata_calc_len = 0;
 308         ei->i_da_metadata_calc_last_lblock = 0;
 309         spin_lock_init(&(ei->i_block_reservation_lock));
 310 +       ext4_init_pending_tree(&ei->i_pending_tree);
 311  #ifdef CONFIG_QUOTA
 312         ei->i_reserved_quota = 0;
 313         memset(&ei->i_dquot, 0, sizeof(ei->i_dquot));
 314 @@ -5954,6 +5955,10 @@ static int __init ext4_init_fs(void)
 315         if (err)
 316                 return err;
 317
 318 +       err = ext4_init_pending();
 319 +       if (err)
 320 +               goto out6;
 321 +
 322         err = ext4_init_pageio();
 323         if (err)
 324                 goto out5;
 325 @@ -5992,6 +5997,8 @@ static int __init ext4_init_fs(void)
 326  out4:
 327         ext4_exit_pageio();
 328  out5:
 329 +       ext4_exit_pending();
 330 +out6:
 331         ext4_exit_es();
 332
 333         return err;
 334 @@ -6009,6 +6016,7 @@ static void __exit ext4_exit_fs(void)
 335         ext4_exit_system_zone();
 336         ext4_exit_pageio();
 337         ext4_exit_es();
 338 +       ext4_exit_pending();
 339  }
 340
 341  MODULE_AUTHOR("Remy Card, Stephen Tweedie, Andrew Morton, Andreas Dilger, Theodore Ts'o and others");
 342 --
 343 2.11.0
 344
 345