linux/fs/ocfs2/alloc.c
<<
>>
Prefs
   1// SPDX-License-Identifier: GPL-2.0-or-later
   2/* -*- mode: c; c-basic-offset: 8; -*-
   3 * vim: noexpandtab sw=8 ts=8 sts=0:
   4 *
   5 * alloc.c
   6 *
   7 * Extent allocs and frees
   8 *
   9 * Copyright (C) 2002, 2004 Oracle.  All rights reserved.
  10 */
  11
  12#include <linux/fs.h>
  13#include <linux/types.h>
  14#include <linux/slab.h>
  15#include <linux/highmem.h>
  16#include <linux/swap.h>
  17#include <linux/quotaops.h>
  18#include <linux/blkdev.h>
  19#include <linux/sched/signal.h>
  20
  21#include <cluster/masklog.h>
  22
  23#include "ocfs2.h"
  24
  25#include "alloc.h"
  26#include "aops.h"
  27#include "blockcheck.h"
  28#include "dlmglue.h"
  29#include "extent_map.h"
  30#include "inode.h"
  31#include "journal.h"
  32#include "localalloc.h"
  33#include "suballoc.h"
  34#include "sysfile.h"
  35#include "file.h"
  36#include "super.h"
  37#include "uptodate.h"
  38#include "xattr.h"
  39#include "refcounttree.h"
  40#include "ocfs2_trace.h"
  41
  42#include "buffer_head_io.h"
  43
  44enum ocfs2_contig_type {
  45        CONTIG_NONE = 0,
  46        CONTIG_LEFT,
  47        CONTIG_RIGHT,
  48        CONTIG_LEFTRIGHT,
  49};
  50
  51static enum ocfs2_contig_type
  52        ocfs2_extent_rec_contig(struct super_block *sb,
  53                                struct ocfs2_extent_rec *ext,
  54                                struct ocfs2_extent_rec *insert_rec);
  55/*
  56 * Operations for a specific extent tree type.
  57 *
  58 * To implement an on-disk btree (extent tree) type in ocfs2, add
  59 * an ocfs2_extent_tree_operations structure and the matching
  60 * ocfs2_init_<thingy>_extent_tree() function.  That's pretty much it
  61 * for the allocation portion of the extent tree.
  62 */
  63struct ocfs2_extent_tree_operations {
  64        /*
  65         * last_eb_blk is the block number of the right most leaf extent
  66         * block.  Most on-disk structures containing an extent tree store
  67         * this value for fast access.  The ->eo_set_last_eb_blk() and
  68         * ->eo_get_last_eb_blk() operations access this value.  They are
  69         *  both required.
  70         */
  71        void (*eo_set_last_eb_blk)(struct ocfs2_extent_tree *et,
  72                                   u64 blkno);
  73        u64 (*eo_get_last_eb_blk)(struct ocfs2_extent_tree *et);
  74
  75        /*
  76         * The on-disk structure usually keeps track of how many total
  77         * clusters are stored in this extent tree.  This function updates
  78         * that value.  new_clusters is the delta, and must be
  79         * added to the total.  Required.
  80         */
  81        void (*eo_update_clusters)(struct ocfs2_extent_tree *et,
  82                                   u32 new_clusters);
  83
  84        /*
  85         * If this extent tree is supported by an extent map, insert
  86         * a record into the map.
  87         */
  88        void (*eo_extent_map_insert)(struct ocfs2_extent_tree *et,
  89                                     struct ocfs2_extent_rec *rec);
  90
  91        /*
  92         * If this extent tree is supported by an extent map, truncate the
  93         * map to clusters,
  94         */
  95        void (*eo_extent_map_truncate)(struct ocfs2_extent_tree *et,
  96                                       u32 clusters);
  97
  98        /*
  99         * If ->eo_insert_check() exists, it is called before rec is
 100         * inserted into the extent tree.  It is optional.
 101         */
 102        int (*eo_insert_check)(struct ocfs2_extent_tree *et,
 103                               struct ocfs2_extent_rec *rec);
 104        int (*eo_sanity_check)(struct ocfs2_extent_tree *et);
 105
 106        /*
 107         * --------------------------------------------------------------
 108         * The remaining are internal to ocfs2_extent_tree and don't have
 109         * accessor functions
 110         */
 111
 112        /*
 113         * ->eo_fill_root_el() takes et->et_object and sets et->et_root_el.
 114         * It is required.
 115         */
 116        void (*eo_fill_root_el)(struct ocfs2_extent_tree *et);
 117
 118        /*
 119         * ->eo_fill_max_leaf_clusters sets et->et_max_leaf_clusters if
 120         * it exists.  If it does not, et->et_max_leaf_clusters is set
 121         * to 0 (unlimited).  Optional.
 122         */
 123        void (*eo_fill_max_leaf_clusters)(struct ocfs2_extent_tree *et);
 124
 125        /*
 126         * ->eo_extent_contig test whether the 2 ocfs2_extent_rec
 127         * are contiguous or not. Optional. Don't need to set it if use
 128         * ocfs2_extent_rec as the tree leaf.
 129         */
 130        enum ocfs2_contig_type
 131                (*eo_extent_contig)(struct ocfs2_extent_tree *et,
 132                                    struct ocfs2_extent_rec *ext,
 133                                    struct ocfs2_extent_rec *insert_rec);
 134};
 135
 136
 137/*
 138 * Pre-declare ocfs2_dinode_et_ops so we can use it as a sanity check
 139 * in the methods.
 140 */
 141static u64 ocfs2_dinode_get_last_eb_blk(struct ocfs2_extent_tree *et);
 142static void ocfs2_dinode_set_last_eb_blk(struct ocfs2_extent_tree *et,
 143                                         u64 blkno);
 144static void ocfs2_dinode_update_clusters(struct ocfs2_extent_tree *et,
 145                                         u32 clusters);
 146static void ocfs2_dinode_extent_map_insert(struct ocfs2_extent_tree *et,
 147                                           struct ocfs2_extent_rec *rec);
 148static void ocfs2_dinode_extent_map_truncate(struct ocfs2_extent_tree *et,
 149                                             u32 clusters);
 150static int ocfs2_dinode_insert_check(struct ocfs2_extent_tree *et,
 151                                     struct ocfs2_extent_rec *rec);
 152static int ocfs2_dinode_sanity_check(struct ocfs2_extent_tree *et);
 153static void ocfs2_dinode_fill_root_el(struct ocfs2_extent_tree *et);
 154
 155static int ocfs2_reuse_blk_from_dealloc(handle_t *handle,
 156                                        struct ocfs2_extent_tree *et,
 157                                        struct buffer_head **new_eb_bh,
 158                                        int blk_wanted, int *blk_given);
 159static int ocfs2_is_dealloc_empty(struct ocfs2_extent_tree *et);
 160
 161static const struct ocfs2_extent_tree_operations ocfs2_dinode_et_ops = {
 162        .eo_set_last_eb_blk     = ocfs2_dinode_set_last_eb_blk,
 163        .eo_get_last_eb_blk     = ocfs2_dinode_get_last_eb_blk,
 164        .eo_update_clusters     = ocfs2_dinode_update_clusters,
 165        .eo_extent_map_insert   = ocfs2_dinode_extent_map_insert,
 166        .eo_extent_map_truncate = ocfs2_dinode_extent_map_truncate,
 167        .eo_insert_check        = ocfs2_dinode_insert_check,
 168        .eo_sanity_check        = ocfs2_dinode_sanity_check,
 169        .eo_fill_root_el        = ocfs2_dinode_fill_root_el,
 170};
 171
 172static void ocfs2_dinode_set_last_eb_blk(struct ocfs2_extent_tree *et,
 173                                         u64 blkno)
 174{
 175        struct ocfs2_dinode *di = et->et_object;
 176
 177        BUG_ON(et->et_ops != &ocfs2_dinode_et_ops);
 178        di->i_last_eb_blk = cpu_to_le64(blkno);
 179}
 180
 181static u64 ocfs2_dinode_get_last_eb_blk(struct ocfs2_extent_tree *et)
 182{
 183        struct ocfs2_dinode *di = et->et_object;
 184
 185        BUG_ON(et->et_ops != &ocfs2_dinode_et_ops);
 186        return le64_to_cpu(di->i_last_eb_blk);
 187}
 188
 189static void ocfs2_dinode_update_clusters(struct ocfs2_extent_tree *et,
 190                                         u32 clusters)
 191{
 192        struct ocfs2_inode_info *oi = cache_info_to_inode(et->et_ci);
 193        struct ocfs2_dinode *di = et->et_object;
 194
 195        le32_add_cpu(&di->i_clusters, clusters);
 196        spin_lock(&oi->ip_lock);
 197        oi->ip_clusters = le32_to_cpu(di->i_clusters);
 198        spin_unlock(&oi->ip_lock);
 199}
 200
 201static void ocfs2_dinode_extent_map_insert(struct ocfs2_extent_tree *et,
 202                                           struct ocfs2_extent_rec *rec)
 203{
 204        struct inode *inode = &cache_info_to_inode(et->et_ci)->vfs_inode;
 205
 206        ocfs2_extent_map_insert_rec(inode, rec);
 207}
 208
 209static void ocfs2_dinode_extent_map_truncate(struct ocfs2_extent_tree *et,
 210                                             u32 clusters)
 211{
 212        struct inode *inode = &cache_info_to_inode(et->et_ci)->vfs_inode;
 213
 214        ocfs2_extent_map_trunc(inode, clusters);
 215}
 216
 217static int ocfs2_dinode_insert_check(struct ocfs2_extent_tree *et,
 218                                     struct ocfs2_extent_rec *rec)
 219{
 220        struct ocfs2_inode_info *oi = cache_info_to_inode(et->et_ci);
 221        struct ocfs2_super *osb = OCFS2_SB(oi->vfs_inode.i_sb);
 222
 223        BUG_ON(oi->ip_dyn_features & OCFS2_INLINE_DATA_FL);
 224        mlog_bug_on_msg(!ocfs2_sparse_alloc(osb) &&
 225                        (oi->ip_clusters != le32_to_cpu(rec->e_cpos)),
 226                        "Device %s, asking for sparse allocation: inode %llu, "
 227                        "cpos %u, clusters %u\n",
 228                        osb->dev_str,
 229                        (unsigned long long)oi->ip_blkno,
 230                        rec->e_cpos, oi->ip_clusters);
 231
 232        return 0;
 233}
 234
 235static int ocfs2_dinode_sanity_check(struct ocfs2_extent_tree *et)
 236{
 237        struct ocfs2_dinode *di = et->et_object;
 238
 239        BUG_ON(et->et_ops != &ocfs2_dinode_et_ops);
 240        BUG_ON(!OCFS2_IS_VALID_DINODE(di));
 241
 242        return 0;
 243}
 244
 245static void ocfs2_dinode_fill_root_el(struct ocfs2_extent_tree *et)
 246{
 247        struct ocfs2_dinode *di = et->et_object;
 248
 249        et->et_root_el = &di->id2.i_list;
 250}
 251
 252
 253static void ocfs2_xattr_value_fill_root_el(struct ocfs2_extent_tree *et)
 254{
 255        struct ocfs2_xattr_value_buf *vb = et->et_object;
 256
 257        et->et_root_el = &vb->vb_xv->xr_list;
 258}
 259
 260static void ocfs2_xattr_value_set_last_eb_blk(struct ocfs2_extent_tree *et,
 261                                              u64 blkno)
 262{
 263        struct ocfs2_xattr_value_buf *vb = et->et_object;
 264
 265        vb->vb_xv->xr_last_eb_blk = cpu_to_le64(blkno);
 266}
 267
 268static u64 ocfs2_xattr_value_get_last_eb_blk(struct ocfs2_extent_tree *et)
 269{
 270        struct ocfs2_xattr_value_buf *vb = et->et_object;
 271
 272        return le64_to_cpu(vb->vb_xv->xr_last_eb_blk);
 273}
 274
 275static void ocfs2_xattr_value_update_clusters(struct ocfs2_extent_tree *et,
 276                                              u32 clusters)
 277{
 278        struct ocfs2_xattr_value_buf *vb = et->et_object;
 279
 280        le32_add_cpu(&vb->vb_xv->xr_clusters, clusters);
 281}
 282
 283static const struct ocfs2_extent_tree_operations ocfs2_xattr_value_et_ops = {
 284        .eo_set_last_eb_blk     = ocfs2_xattr_value_set_last_eb_blk,
 285        .eo_get_last_eb_blk     = ocfs2_xattr_value_get_last_eb_blk,
 286        .eo_update_clusters     = ocfs2_xattr_value_update_clusters,
 287        .eo_fill_root_el        = ocfs2_xattr_value_fill_root_el,
 288};
 289
 290static void ocfs2_xattr_tree_fill_root_el(struct ocfs2_extent_tree *et)
 291{
 292        struct ocfs2_xattr_block *xb = et->et_object;
 293
 294        et->et_root_el = &xb->xb_attrs.xb_root.xt_list;
 295}
 296
 297static void ocfs2_xattr_tree_fill_max_leaf_clusters(struct ocfs2_extent_tree *et)
 298{
 299        struct super_block *sb = ocfs2_metadata_cache_get_super(et->et_ci);
 300        et->et_max_leaf_clusters =
 301                ocfs2_clusters_for_bytes(sb, OCFS2_MAX_XATTR_TREE_LEAF_SIZE);
 302}
 303
 304static void ocfs2_xattr_tree_set_last_eb_blk(struct ocfs2_extent_tree *et,
 305                                             u64 blkno)
 306{
 307        struct ocfs2_xattr_block *xb = et->et_object;
 308        struct ocfs2_xattr_tree_root *xt = &xb->xb_attrs.xb_root;
 309
 310        xt->xt_last_eb_blk = cpu_to_le64(blkno);
 311}
 312
 313static u64 ocfs2_xattr_tree_get_last_eb_blk(struct ocfs2_extent_tree *et)
 314{
 315        struct ocfs2_xattr_block *xb = et->et_object;
 316        struct ocfs2_xattr_tree_root *xt = &xb->xb_attrs.xb_root;
 317
 318        return le64_to_cpu(xt->xt_last_eb_blk);
 319}
 320
 321static void ocfs2_xattr_tree_update_clusters(struct ocfs2_extent_tree *et,
 322                                             u32 clusters)
 323{
 324        struct ocfs2_xattr_block *xb = et->et_object;
 325
 326        le32_add_cpu(&xb->xb_attrs.xb_root.xt_clusters, clusters);
 327}
 328
 329static const struct ocfs2_extent_tree_operations ocfs2_xattr_tree_et_ops = {
 330        .eo_set_last_eb_blk     = ocfs2_xattr_tree_set_last_eb_blk,
 331        .eo_get_last_eb_blk     = ocfs2_xattr_tree_get_last_eb_blk,
 332        .eo_update_clusters     = ocfs2_xattr_tree_update_clusters,
 333        .eo_fill_root_el        = ocfs2_xattr_tree_fill_root_el,
 334        .eo_fill_max_leaf_clusters = ocfs2_xattr_tree_fill_max_leaf_clusters,
 335};
 336
 337static void ocfs2_dx_root_set_last_eb_blk(struct ocfs2_extent_tree *et,
 338                                          u64 blkno)
 339{
 340        struct ocfs2_dx_root_block *dx_root = et->et_object;
 341
 342        dx_root->dr_last_eb_blk = cpu_to_le64(blkno);
 343}
 344
 345static u64 ocfs2_dx_root_get_last_eb_blk(struct ocfs2_extent_tree *et)
 346{
 347        struct ocfs2_dx_root_block *dx_root = et->et_object;
 348
 349        return le64_to_cpu(dx_root->dr_last_eb_blk);
 350}
 351
 352static void ocfs2_dx_root_update_clusters(struct ocfs2_extent_tree *et,
 353                                          u32 clusters)
 354{
 355        struct ocfs2_dx_root_block *dx_root = et->et_object;
 356
 357        le32_add_cpu(&dx_root->dr_clusters, clusters);
 358}
 359
 360static int ocfs2_dx_root_sanity_check(struct ocfs2_extent_tree *et)
 361{
 362        struct ocfs2_dx_root_block *dx_root = et->et_object;
 363
 364        BUG_ON(!OCFS2_IS_VALID_DX_ROOT(dx_root));
 365
 366        return 0;
 367}
 368
 369static void ocfs2_dx_root_fill_root_el(struct ocfs2_extent_tree *et)
 370{
 371        struct ocfs2_dx_root_block *dx_root = et->et_object;
 372
 373        et->et_root_el = &dx_root->dr_list;
 374}
 375
 376static const struct ocfs2_extent_tree_operations ocfs2_dx_root_et_ops = {
 377        .eo_set_last_eb_blk     = ocfs2_dx_root_set_last_eb_blk,
 378        .eo_get_last_eb_blk     = ocfs2_dx_root_get_last_eb_blk,
 379        .eo_update_clusters     = ocfs2_dx_root_update_clusters,
 380        .eo_sanity_check        = ocfs2_dx_root_sanity_check,
 381        .eo_fill_root_el        = ocfs2_dx_root_fill_root_el,
 382};
 383
 384static void ocfs2_refcount_tree_fill_root_el(struct ocfs2_extent_tree *et)
 385{
 386        struct ocfs2_refcount_block *rb = et->et_object;
 387
 388        et->et_root_el = &rb->rf_list;
 389}
 390
 391static void ocfs2_refcount_tree_set_last_eb_blk(struct ocfs2_extent_tree *et,
 392                                                u64 blkno)
 393{
 394        struct ocfs2_refcount_block *rb = et->et_object;
 395
 396        rb->rf_last_eb_blk = cpu_to_le64(blkno);
 397}
 398
 399static u64 ocfs2_refcount_tree_get_last_eb_blk(struct ocfs2_extent_tree *et)
 400{
 401        struct ocfs2_refcount_block *rb = et->et_object;
 402
 403        return le64_to_cpu(rb->rf_last_eb_blk);
 404}
 405
 406static void ocfs2_refcount_tree_update_clusters(struct ocfs2_extent_tree *et,
 407                                                u32 clusters)
 408{
 409        struct ocfs2_refcount_block *rb = et->et_object;
 410
 411        le32_add_cpu(&rb->rf_clusters, clusters);
 412}
 413
 414static enum ocfs2_contig_type
 415ocfs2_refcount_tree_extent_contig(struct ocfs2_extent_tree *et,
 416                                  struct ocfs2_extent_rec *ext,
 417                                  struct ocfs2_extent_rec *insert_rec)
 418{
 419        return CONTIG_NONE;
 420}
 421
 422static const struct ocfs2_extent_tree_operations ocfs2_refcount_tree_et_ops = {
 423        .eo_set_last_eb_blk     = ocfs2_refcount_tree_set_last_eb_blk,
 424        .eo_get_last_eb_blk     = ocfs2_refcount_tree_get_last_eb_blk,
 425        .eo_update_clusters     = ocfs2_refcount_tree_update_clusters,
 426        .eo_fill_root_el        = ocfs2_refcount_tree_fill_root_el,
 427        .eo_extent_contig       = ocfs2_refcount_tree_extent_contig,
 428};
 429
 430static void __ocfs2_init_extent_tree(struct ocfs2_extent_tree *et,
 431                                     struct ocfs2_caching_info *ci,
 432                                     struct buffer_head *bh,
 433                                     ocfs2_journal_access_func access,
 434                                     void *obj,
 435                                     const struct ocfs2_extent_tree_operations *ops)
 436{
 437        et->et_ops = ops;
 438        et->et_root_bh = bh;
 439        et->et_ci = ci;
 440        et->et_root_journal_access = access;
 441        if (!obj)
 442                obj = (void *)bh->b_data;
 443        et->et_object = obj;
 444        et->et_dealloc = NULL;
 445
 446        et->et_ops->eo_fill_root_el(et);
 447        if (!et->et_ops->eo_fill_max_leaf_clusters)
 448                et->et_max_leaf_clusters = 0;
 449        else
 450                et->et_ops->eo_fill_max_leaf_clusters(et);
 451}
 452
 453void ocfs2_init_dinode_extent_tree(struct ocfs2_extent_tree *et,
 454                                   struct ocfs2_caching_info *ci,
 455                                   struct buffer_head *bh)
 456{
 457        __ocfs2_init_extent_tree(et, ci, bh, ocfs2_journal_access_di,
 458                                 NULL, &ocfs2_dinode_et_ops);
 459}
 460
 461void ocfs2_init_xattr_tree_extent_tree(struct ocfs2_extent_tree *et,
 462                                       struct ocfs2_caching_info *ci,
 463                                       struct buffer_head *bh)
 464{
 465        __ocfs2_init_extent_tree(et, ci, bh, ocfs2_journal_access_xb,
 466                                 NULL, &ocfs2_xattr_tree_et_ops);
 467}
 468
 469void ocfs2_init_xattr_value_extent_tree(struct ocfs2_extent_tree *et,
 470                                        struct ocfs2_caching_info *ci,
 471                                        struct ocfs2_xattr_value_buf *vb)
 472{
 473        __ocfs2_init_extent_tree(et, ci, vb->vb_bh, vb->vb_access, vb,
 474                                 &ocfs2_xattr_value_et_ops);
 475}
 476
 477void ocfs2_init_dx_root_extent_tree(struct ocfs2_extent_tree *et,
 478                                    struct ocfs2_caching_info *ci,
 479                                    struct buffer_head *bh)
 480{
 481        __ocfs2_init_extent_tree(et, ci, bh, ocfs2_journal_access_dr,
 482                                 NULL, &ocfs2_dx_root_et_ops);
 483}
 484
 485void ocfs2_init_refcount_extent_tree(struct ocfs2_extent_tree *et,
 486                                     struct ocfs2_caching_info *ci,
 487                                     struct buffer_head *bh)
 488{
 489        __ocfs2_init_extent_tree(et, ci, bh, ocfs2_journal_access_rb,
 490                                 NULL, &ocfs2_refcount_tree_et_ops);
 491}
 492
 493static inline void ocfs2_et_set_last_eb_blk(struct ocfs2_extent_tree *et,
 494                                            u64 new_last_eb_blk)
 495{
 496        et->et_ops->eo_set_last_eb_blk(et, new_last_eb_blk);
 497}
 498
 499static inline u64 ocfs2_et_get_last_eb_blk(struct ocfs2_extent_tree *et)
 500{
 501        return et->et_ops->eo_get_last_eb_blk(et);
 502}
 503
 504static inline void ocfs2_et_update_clusters(struct ocfs2_extent_tree *et,
 505                                            u32 clusters)
 506{
 507        et->et_ops->eo_update_clusters(et, clusters);
 508}
 509
 510static inline void ocfs2_et_extent_map_insert(struct ocfs2_extent_tree *et,
 511                                              struct ocfs2_extent_rec *rec)
 512{
 513        if (et->et_ops->eo_extent_map_insert)
 514                et->et_ops->eo_extent_map_insert(et, rec);
 515}
 516
 517static inline void ocfs2_et_extent_map_truncate(struct ocfs2_extent_tree *et,
 518                                                u32 clusters)
 519{
 520        if (et->et_ops->eo_extent_map_truncate)
 521                et->et_ops->eo_extent_map_truncate(et, clusters);
 522}
 523
 524static inline int ocfs2_et_root_journal_access(handle_t *handle,
 525                                               struct ocfs2_extent_tree *et,
 526                                               int type)
 527{
 528        return et->et_root_journal_access(handle, et->et_ci, et->et_root_bh,
 529                                          type);
 530}
 531
 532static inline enum ocfs2_contig_type
 533        ocfs2_et_extent_contig(struct ocfs2_extent_tree *et,
 534                               struct ocfs2_extent_rec *rec,
 535                               struct ocfs2_extent_rec *insert_rec)
 536{
 537        if (et->et_ops->eo_extent_contig)
 538                return et->et_ops->eo_extent_contig(et, rec, insert_rec);
 539
 540        return ocfs2_extent_rec_contig(
 541                                ocfs2_metadata_cache_get_super(et->et_ci),
 542                                rec, insert_rec);
 543}
 544
 545static inline int ocfs2_et_insert_check(struct ocfs2_extent_tree *et,
 546                                        struct ocfs2_extent_rec *rec)
 547{
 548        int ret = 0;
 549
 550        if (et->et_ops->eo_insert_check)
 551                ret = et->et_ops->eo_insert_check(et, rec);
 552        return ret;
 553}
 554
 555static inline int ocfs2_et_sanity_check(struct ocfs2_extent_tree *et)
 556{
 557        int ret = 0;
 558
 559        if (et->et_ops->eo_sanity_check)
 560                ret = et->et_ops->eo_sanity_check(et);
 561        return ret;
 562}
 563
 564static int ocfs2_cache_extent_block_free(struct ocfs2_cached_dealloc_ctxt *ctxt,
 565                                         struct ocfs2_extent_block *eb);
 566static void ocfs2_adjust_rightmost_records(handle_t *handle,
 567                                           struct ocfs2_extent_tree *et,
 568                                           struct ocfs2_path *path,
 569                                           struct ocfs2_extent_rec *insert_rec);
 570/*
 571 * Reset the actual path elements so that we can re-use the structure
 572 * to build another path. Generally, this involves freeing the buffer
 573 * heads.
 574 */
 575void ocfs2_reinit_path(struct ocfs2_path *path, int keep_root)
 576{
 577        int i, start = 0, depth = 0;
 578        struct ocfs2_path_item *node;
 579
 580        if (keep_root)
 581                start = 1;
 582
 583        for(i = start; i < path_num_items(path); i++) {
 584                node = &path->p_node[i];
 585
 586                brelse(node->bh);
 587                node->bh = NULL;
 588                node->el = NULL;
 589        }
 590
 591        /*
 592         * Tree depth may change during truncate, or insert. If we're
 593         * keeping the root extent list, then make sure that our path
 594         * structure reflects the proper depth.
 595         */
 596        if (keep_root)
 597                depth = le16_to_cpu(path_root_el(path)->l_tree_depth);
 598        else
 599                path_root_access(path) = NULL;
 600
 601        path->p_tree_depth = depth;
 602}
 603
 604void ocfs2_free_path(struct ocfs2_path *path)
 605{
 606        if (path) {
 607                ocfs2_reinit_path(path, 0);
 608                kfree(path);
 609        }
 610}
 611
 612/*
 613 * All the elements of src into dest. After this call, src could be freed
 614 * without affecting dest.
 615 *
 616 * Both paths should have the same root. Any non-root elements of dest
 617 * will be freed.
 618 */
 619static void ocfs2_cp_path(struct ocfs2_path *dest, struct ocfs2_path *src)
 620{
 621        int i;
 622
 623        BUG_ON(path_root_bh(dest) != path_root_bh(src));
 624        BUG_ON(path_root_el(dest) != path_root_el(src));
 625        BUG_ON(path_root_access(dest) != path_root_access(src));
 626
 627        ocfs2_reinit_path(dest, 1);
 628
 629        for(i = 1; i < OCFS2_MAX_PATH_DEPTH; i++) {
 630                dest->p_node[i].bh = src->p_node[i].bh;
 631                dest->p_node[i].el = src->p_node[i].el;
 632
 633                if (dest->p_node[i].bh)
 634                        get_bh(dest->p_node[i].bh);
 635        }
 636}
 637
 638/*
 639 * Make the *dest path the same as src and re-initialize src path to
 640 * have a root only.
 641 */
 642static void ocfs2_mv_path(struct ocfs2_path *dest, struct ocfs2_path *src)
 643{
 644        int i;
 645
 646        BUG_ON(path_root_bh(dest) != path_root_bh(src));
 647        BUG_ON(path_root_access(dest) != path_root_access(src));
 648
 649        for(i = 1; i < OCFS2_MAX_PATH_DEPTH; i++) {
 650                brelse(dest->p_node[i].bh);
 651
 652                dest->p_node[i].bh = src->p_node[i].bh;
 653                dest->p_node[i].el = src->p_node[i].el;
 654
 655                src->p_node[i].bh = NULL;
 656                src->p_node[i].el = NULL;
 657        }
 658}
 659
 660/*
 661 * Insert an extent block at given index.
 662 *
 663 * This will not take an additional reference on eb_bh.
 664 */
 665static inline void ocfs2_path_insert_eb(struct ocfs2_path *path, int index,
 666                                        struct buffer_head *eb_bh)
 667{
 668        struct ocfs2_extent_block *eb = (struct ocfs2_extent_block *)eb_bh->b_data;
 669
 670        /*
 671         * Right now, no root bh is an extent block, so this helps
 672         * catch code errors with dinode trees. The assertion can be
 673         * safely removed if we ever need to insert extent block
 674         * structures at the root.
 675         */
 676        BUG_ON(index == 0);
 677
 678        path->p_node[index].bh = eb_bh;
 679        path->p_node[index].el = &eb->h_list;
 680}
 681
 682static struct ocfs2_path *ocfs2_new_path(struct buffer_head *root_bh,
 683                                         struct ocfs2_extent_list *root_el,
 684                                         ocfs2_journal_access_func access)
 685{
 686        struct ocfs2_path *path;
 687
 688        BUG_ON(le16_to_cpu(root_el->l_tree_depth) >= OCFS2_MAX_PATH_DEPTH);
 689
 690        path = kzalloc(sizeof(*path), GFP_NOFS);
 691        if (path) {
 692                path->p_tree_depth = le16_to_cpu(root_el->l_tree_depth);
 693                get_bh(root_bh);
 694                path_root_bh(path) = root_bh;
 695                path_root_el(path) = root_el;
 696                path_root_access(path) = access;
 697        }
 698
 699        return path;
 700}
 701
 702struct ocfs2_path *ocfs2_new_path_from_path(struct ocfs2_path *path)
 703{
 704        return ocfs2_new_path(path_root_bh(path), path_root_el(path),
 705                              path_root_access(path));
 706}
 707
 708struct ocfs2_path *ocfs2_new_path_from_et(struct ocfs2_extent_tree *et)
 709{
 710        return ocfs2_new_path(et->et_root_bh, et->et_root_el,
 711                              et->et_root_journal_access);
 712}
 713
 714/*
 715 * Journal the buffer at depth idx.  All idx>0 are extent_blocks,
 716 * otherwise it's the root_access function.
 717 *
 718 * I don't like the way this function's name looks next to
 719 * ocfs2_journal_access_path(), but I don't have a better one.
 720 */
 721int ocfs2_path_bh_journal_access(handle_t *handle,
 722                                 struct ocfs2_caching_info *ci,
 723                                 struct ocfs2_path *path,
 724                                 int idx)
 725{
 726        ocfs2_journal_access_func access = path_root_access(path);
 727
 728        if (!access)
 729                access = ocfs2_journal_access;
 730
 731        if (idx)
 732                access = ocfs2_journal_access_eb;
 733
 734        return access(handle, ci, path->p_node[idx].bh,
 735                      OCFS2_JOURNAL_ACCESS_WRITE);
 736}
 737
 738/*
 739 * Convenience function to journal all components in a path.
 740 */
 741int ocfs2_journal_access_path(struct ocfs2_caching_info *ci,
 742                              handle_t *handle,
 743                              struct ocfs2_path *path)
 744{
 745        int i, ret = 0;
 746
 747        if (!path)
 748                goto out;
 749
 750        for(i = 0; i < path_num_items(path); i++) {
 751                ret = ocfs2_path_bh_journal_access(handle, ci, path, i);
 752                if (ret < 0) {
 753                        mlog_errno(ret);
 754                        goto out;
 755                }
 756        }
 757
 758out:
 759        return ret;
 760}
 761
 762/*
 763 * Return the index of the extent record which contains cluster #v_cluster.
 764 * -1 is returned if it was not found.
 765 *
 766 * Should work fine on interior and exterior nodes.
 767 */
 768int ocfs2_search_extent_list(struct ocfs2_extent_list *el, u32 v_cluster)
 769{
 770        int ret = -1;
 771        int i;
 772        struct ocfs2_extent_rec *rec;
 773        u32 rec_end, rec_start, clusters;
 774
 775        for(i = 0; i < le16_to_cpu(el->l_next_free_rec); i++) {
 776                rec = &el->l_recs[i];
 777
 778                rec_start = le32_to_cpu(rec->e_cpos);
 779                clusters = ocfs2_rec_clusters(el, rec);
 780
 781                rec_end = rec_start + clusters;
 782
 783                if (v_cluster >= rec_start && v_cluster < rec_end) {
 784                        ret = i;
 785                        break;
 786                }
 787        }
 788
 789        return ret;
 790}
 791
 792/*
 793 * NOTE: ocfs2_block_extent_contig(), ocfs2_extents_adjacent() and
 794 * ocfs2_extent_rec_contig only work properly against leaf nodes!
 795 */
 796static int ocfs2_block_extent_contig(struct super_block *sb,
 797                                     struct ocfs2_extent_rec *ext,
 798                                     u64 blkno)
 799{
 800        u64 blk_end = le64_to_cpu(ext->e_blkno);
 801
 802        blk_end += ocfs2_clusters_to_blocks(sb,
 803                                    le16_to_cpu(ext->e_leaf_clusters));
 804
 805        return blkno == blk_end;
 806}
 807
 808static int ocfs2_extents_adjacent(struct ocfs2_extent_rec *left,
 809                                  struct ocfs2_extent_rec *right)
 810{
 811        u32 left_range;
 812
 813        left_range = le32_to_cpu(left->e_cpos) +
 814                le16_to_cpu(left->e_leaf_clusters);
 815
 816        return (left_range == le32_to_cpu(right->e_cpos));
 817}
 818
 819static enum ocfs2_contig_type
 820        ocfs2_extent_rec_contig(struct super_block *sb,
 821                                struct ocfs2_extent_rec *ext,
 822                                struct ocfs2_extent_rec *insert_rec)
 823{
 824        u64 blkno = le64_to_cpu(insert_rec->e_blkno);
 825
 826        /*
 827         * Refuse to coalesce extent records with different flag
 828         * fields - we don't want to mix unwritten extents with user
 829         * data.
 830         */
 831        if (ext->e_flags != insert_rec->e_flags)
 832                return CONTIG_NONE;
 833
 834        if (ocfs2_extents_adjacent(ext, insert_rec) &&
 835            ocfs2_block_extent_contig(sb, ext, blkno))
 836                        return CONTIG_RIGHT;
 837
 838        blkno = le64_to_cpu(ext->e_blkno);
 839        if (ocfs2_extents_adjacent(insert_rec, ext) &&
 840            ocfs2_block_extent_contig(sb, insert_rec, blkno))
 841                return CONTIG_LEFT;
 842
 843        return CONTIG_NONE;
 844}
 845
 846/*
 847 * NOTE: We can have pretty much any combination of contiguousness and
 848 * appending.
 849 *
 850 * The usefulness of APPEND_TAIL is more in that it lets us know that
 851 * we'll have to update the path to that leaf.
 852 */
 853enum ocfs2_append_type {
 854        APPEND_NONE = 0,
 855        APPEND_TAIL,
 856};
 857
 858enum ocfs2_split_type {
 859        SPLIT_NONE = 0,
 860        SPLIT_LEFT,
 861        SPLIT_RIGHT,
 862};
 863
 864struct ocfs2_insert_type {
 865        enum ocfs2_split_type   ins_split;
 866        enum ocfs2_append_type  ins_appending;
 867        enum ocfs2_contig_type  ins_contig;
 868        int                     ins_contig_index;
 869        int                     ins_tree_depth;
 870};
 871
 872struct ocfs2_merge_ctxt {
 873        enum ocfs2_contig_type  c_contig_type;
 874        int                     c_has_empty_extent;
 875        int                     c_split_covers_rec;
 876};
 877
 878static int ocfs2_validate_extent_block(struct super_block *sb,
 879                                       struct buffer_head *bh)
 880{
 881        int rc;
 882        struct ocfs2_extent_block *eb =
 883                (struct ocfs2_extent_block *)bh->b_data;
 884
 885        trace_ocfs2_validate_extent_block((unsigned long long)bh->b_blocknr);
 886
 887        BUG_ON(!buffer_uptodate(bh));
 888
 889        /*
 890         * If the ecc fails, we return the error but otherwise
 891         * leave the filesystem running.  We know any error is
 892         * local to this block.
 893         */
 894        rc = ocfs2_validate_meta_ecc(sb, bh->b_data, &eb->h_check);
 895        if (rc) {
 896                mlog(ML_ERROR, "Checksum failed for extent block %llu\n",
 897                     (unsigned long long)bh->b_blocknr);
 898                return rc;
 899        }
 900
 901        /*
 902         * Errors after here are fatal.
 903         */
 904
 905        if (!OCFS2_IS_VALID_EXTENT_BLOCK(eb)) {
 906                rc = ocfs2_error(sb,
 907                                 "Extent block #%llu has bad signature %.*s\n",
 908                                 (unsigned long long)bh->b_blocknr, 7,
 909                                 eb->h_signature);
 910                goto bail;
 911        }
 912
 913        if (le64_to_cpu(eb->h_blkno) != bh->b_blocknr) {
 914                rc = ocfs2_error(sb,
 915                                 "Extent block #%llu has an invalid h_blkno of %llu\n",
 916                                 (unsigned long long)bh->b_blocknr,
 917                                 (unsigned long long)le64_to_cpu(eb->h_blkno));
 918                goto bail;
 919        }
 920
 921        if (le32_to_cpu(eb->h_fs_generation) != OCFS2_SB(sb)->fs_generation)
 922                rc = ocfs2_error(sb,
 923                                 "Extent block #%llu has an invalid h_fs_generation of #%u\n",
 924                                 (unsigned long long)bh->b_blocknr,
 925                                 le32_to_cpu(eb->h_fs_generation));
 926bail:
 927        return rc;
 928}
 929
 930int ocfs2_read_extent_block(struct ocfs2_caching_info *ci, u64 eb_blkno,
 931                            struct buffer_head **bh)
 932{
 933        int rc;
 934        struct buffer_head *tmp = *bh;
 935
 936        rc = ocfs2_read_block(ci, eb_blkno, &tmp,
 937                              ocfs2_validate_extent_block);
 938
 939        /* If ocfs2_read_block() got us a new bh, pass it up. */
 940        if (!rc && !*bh)
 941                *bh = tmp;
 942
 943        return rc;
 944}
 945
 946
 947/*
 948 * How many free extents have we got before we need more meta data?
 949 */
 950int ocfs2_num_free_extents(struct ocfs2_extent_tree *et)
 951{
 952        int retval;
 953        struct ocfs2_extent_list *el = NULL;
 954        struct ocfs2_extent_block *eb;
 955        struct buffer_head *eb_bh = NULL;
 956        u64 last_eb_blk = 0;
 957
 958        el = et->et_root_el;
 959        last_eb_blk = ocfs2_et_get_last_eb_blk(et);
 960
 961        if (last_eb_blk) {
 962                retval = ocfs2_read_extent_block(et->et_ci, last_eb_blk,
 963                                                 &eb_bh);
 964                if (retval < 0) {
 965                        mlog_errno(retval);
 966                        goto bail;
 967                }
 968                eb = (struct ocfs2_extent_block *) eb_bh->b_data;
 969                el = &eb->h_list;
 970        }
 971
 972        BUG_ON(el->l_tree_depth != 0);
 973
 974        retval = le16_to_cpu(el->l_count) - le16_to_cpu(el->l_next_free_rec);
 975bail:
 976        brelse(eb_bh);
 977
 978        trace_ocfs2_num_free_extents(retval);
 979        return retval;
 980}
 981
 982/* expects array to already be allocated
 983 *
 984 * sets h_signature, h_blkno, h_suballoc_bit, h_suballoc_slot, and
 985 * l_count for you
 986 */
 987static int ocfs2_create_new_meta_bhs(handle_t *handle,
 988                                     struct ocfs2_extent_tree *et,
 989                                     int wanted,
 990                                     struct ocfs2_alloc_context *meta_ac,
 991                                     struct buffer_head *bhs[])
 992{
 993        int count, status, i;
 994        u16 suballoc_bit_start;
 995        u32 num_got;
 996        u64 suballoc_loc, first_blkno;
 997        struct ocfs2_super *osb =
 998                OCFS2_SB(ocfs2_metadata_cache_get_super(et->et_ci));
 999        struct ocfs2_extent_block *eb;
1000
1001        count = 0;
1002        while (count < wanted) {
1003                status = ocfs2_claim_metadata(handle,
1004                                              meta_ac,
1005                                              wanted - count,
1006                                              &suballoc_loc,
1007                                              &suballoc_bit_start,
1008                                              &num_got,
1009                                              &first_blkno);
1010                if (status < 0) {
1011                        mlog_errno(status);
1012                        goto bail;
1013                }
1014
1015                for(i = count;  i < (num_got + count); i++) {
1016                        bhs[i] = sb_getblk(osb->sb, first_blkno);
1017                        if (bhs[i] == NULL) {
1018                                status = -ENOMEM;
1019                                mlog_errno(status);
1020                                goto bail;
1021                        }
1022                        ocfs2_set_new_buffer_uptodate(et->et_ci, bhs[i]);
1023
1024                        status = ocfs2_journal_access_eb(handle, et->et_ci,
1025                                                         bhs[i],
1026                                                         OCFS2_JOURNAL_ACCESS_CREATE);
1027                        if (status < 0) {
1028                                mlog_errno(status);
1029                                goto bail;
1030                        }
1031
1032                        memset(bhs[i]->b_data, 0, osb->sb->s_blocksize);
1033                        eb = (struct ocfs2_extent_block *) bhs[i]->b_data;
1034                        /* Ok, setup the minimal stuff here. */
1035                        strcpy(eb->h_signature, OCFS2_EXTENT_BLOCK_SIGNATURE);
1036                        eb->h_blkno = cpu_to_le64(first_blkno);
1037                        eb->h_fs_generation = cpu_to_le32(osb->fs_generation);
1038                        eb->h_suballoc_slot =
1039                                cpu_to_le16(meta_ac->ac_alloc_slot);
1040                        eb->h_suballoc_loc = cpu_to_le64(suballoc_loc);
1041                        eb->h_suballoc_bit = cpu_to_le16(suballoc_bit_start);
1042                        eb->h_list.l_count =
1043                                cpu_to_le16(ocfs2_extent_recs_per_eb(osb->sb));
1044
1045                        suballoc_bit_start++;
1046                        first_blkno++;
1047
1048                        /* We'll also be dirtied by the caller, so
1049                         * this isn't absolutely necessary. */
1050                        ocfs2_journal_dirty(handle, bhs[i]);
1051                }
1052
1053                count += num_got;
1054        }
1055
1056        status = 0;
1057bail:
1058        if (status < 0) {
1059                for(i = 0; i < wanted; i++) {
1060                        brelse(bhs[i]);
1061                        bhs[i] = NULL;
1062                }
1063                mlog_errno(status);
1064        }
1065        return status;
1066}
1067
1068/*
1069 * Helper function for ocfs2_add_branch() and ocfs2_shift_tree_depth().
1070 *
1071 * Returns the sum of the rightmost extent rec logical offset and
1072 * cluster count.
1073 *
1074 * ocfs2_add_branch() uses this to determine what logical cluster
1075 * value should be populated into the leftmost new branch records.
1076 *
1077 * ocfs2_shift_tree_depth() uses this to determine the # clusters
1078 * value for the new topmost tree record.
1079 */
1080static inline u32 ocfs2_sum_rightmost_rec(struct ocfs2_extent_list  *el)
1081{
1082        int i;
1083
1084        i = le16_to_cpu(el->l_next_free_rec) - 1;
1085
1086        return le32_to_cpu(el->l_recs[i].e_cpos) +
1087                ocfs2_rec_clusters(el, &el->l_recs[i]);
1088}
1089
1090/*
1091 * Change range of the branches in the right most path according to the leaf
1092 * extent block's rightmost record.
1093 */
1094static int ocfs2_adjust_rightmost_branch(handle_t *handle,
1095                                         struct ocfs2_extent_tree *et)
1096{
1097        int status;
1098        struct ocfs2_path *path = NULL;
1099        struct ocfs2_extent_list *el;
1100        struct ocfs2_extent_rec *rec;
1101
1102        path = ocfs2_new_path_from_et(et);
1103        if (!path) {
1104                status = -ENOMEM;
1105                return status;
1106        }
1107
1108        status = ocfs2_find_path(et->et_ci, path, UINT_MAX);
1109        if (status < 0) {
1110                mlog_errno(status);
1111                goto out;
1112        }
1113
1114        status = ocfs2_extend_trans(handle, path_num_items(path));
1115        if (status < 0) {
1116                mlog_errno(status);
1117                goto out;
1118        }
1119
1120        status = ocfs2_journal_access_path(et->et_ci, handle, path);
1121        if (status < 0) {
1122                mlog_errno(status);
1123                goto out;
1124        }
1125
1126        el = path_leaf_el(path);
1127        rec = &el->l_recs[le16_to_cpu(el->l_next_free_rec) - 1];
1128
1129        ocfs2_adjust_rightmost_records(handle, et, path, rec);
1130
1131out:
1132        ocfs2_free_path(path);
1133        return status;
1134}
1135
1136/*
1137 * Add an entire tree branch to our inode. eb_bh is the extent block
1138 * to start at, if we don't want to start the branch at the root
1139 * structure.
1140 *
1141 * last_eb_bh is required as we have to update it's next_leaf pointer
1142 * for the new last extent block.
1143 *
1144 * the new branch will be 'empty' in the sense that every block will
1145 * contain a single record with cluster count == 0.
1146 */
1147static int ocfs2_add_branch(handle_t *handle,
1148                            struct ocfs2_extent_tree *et,
1149                            struct buffer_head *eb_bh,
1150                            struct buffer_head **last_eb_bh,
1151                            struct ocfs2_alloc_context *meta_ac)
1152{
1153        int status, new_blocks, i, block_given = 0;
1154        u64 next_blkno, new_last_eb_blk;
1155        struct buffer_head *bh;
1156        struct buffer_head **new_eb_bhs = NULL;
1157        struct ocfs2_extent_block *eb;
1158        struct ocfs2_extent_list  *eb_el;
1159        struct ocfs2_extent_list  *el;
1160        u32 new_cpos, root_end;
1161
1162        BUG_ON(!last_eb_bh || !*last_eb_bh);
1163
1164        if (eb_bh) {
1165                eb = (struct ocfs2_extent_block *) eb_bh->b_data;
1166                el = &eb->h_list;
1167        } else
1168                el = et->et_root_el;
1169
1170        /* we never add a branch to a leaf. */
1171        BUG_ON(!el->l_tree_depth);
1172
1173        new_blocks = le16_to_cpu(el->l_tree_depth);
1174
1175        eb = (struct ocfs2_extent_block *)(*last_eb_bh)->b_data;
1176        new_cpos = ocfs2_sum_rightmost_rec(&eb->h_list);
1177        root_end = ocfs2_sum_rightmost_rec(et->et_root_el);
1178
1179        /*
1180         * If there is a gap before the root end and the real end
1181         * of the righmost leaf block, we need to remove the gap
1182         * between new_cpos and root_end first so that the tree
1183         * is consistent after we add a new branch(it will start
1184         * from new_cpos).
1185         */
1186        if (root_end > new_cpos) {
1187                trace_ocfs2_adjust_rightmost_branch(
1188                        (unsigned long long)
1189                        ocfs2_metadata_cache_owner(et->et_ci),
1190                        root_end, new_cpos);
1191
1192                status = ocfs2_adjust_rightmost_branch(handle, et);
1193                if (status) {
1194                        mlog_errno(status);
1195                        goto bail;
1196                }
1197        }
1198
1199        /* allocate the number of new eb blocks we need */
1200        new_eb_bhs = kcalloc(new_blocks, sizeof(struct buffer_head *),
1201                             GFP_KERNEL);
1202        if (!new_eb_bhs) {
1203                status = -ENOMEM;
1204                mlog_errno(status);
1205                goto bail;
1206        }
1207
1208        /* Firstyly, try to reuse dealloc since we have already estimated how
1209         * many extent blocks we may use.
1210         */
1211        if (!ocfs2_is_dealloc_empty(et)) {
1212                status = ocfs2_reuse_blk_from_dealloc(handle, et,
1213                                                      new_eb_bhs, new_blocks,
1214                                                      &block_given);
1215                if (status < 0) {
1216                        mlog_errno(status);
1217                        goto bail;
1218                }
1219        }
1220
1221        BUG_ON(block_given > new_blocks);
1222
1223        if (block_given < new_blocks) {
1224                BUG_ON(!meta_ac);
1225                status = ocfs2_create_new_meta_bhs(handle, et,
1226                                                   new_blocks - block_given,
1227                                                   meta_ac,
1228                                                   &new_eb_bhs[block_given]);
1229                if (status < 0) {
1230                        mlog_errno(status);
1231                        goto bail;
1232                }
1233        }
1234
1235        /* Note: new_eb_bhs[new_blocks - 1] is the guy which will be
1236         * linked with the rest of the tree.
1237         * conversly, new_eb_bhs[0] is the new bottommost leaf.
1238         *
1239         * when we leave the loop, new_last_eb_blk will point to the
1240         * newest leaf, and next_blkno will point to the topmost extent
1241         * block. */
1242        next_blkno = new_last_eb_blk = 0;
1243        for(i = 0; i < new_blocks; i++) {
1244                bh = new_eb_bhs[i];
1245                eb = (struct ocfs2_extent_block *) bh->b_data;
1246                /* ocfs2_create_new_meta_bhs() should create it right! */
1247                BUG_ON(!OCFS2_IS_VALID_EXTENT_BLOCK(eb));
1248                eb_el = &eb->h_list;
1249
1250                status = ocfs2_journal_access_eb(handle, et->et_ci, bh,
1251                                                 OCFS2_JOURNAL_ACCESS_CREATE);
1252                if (status < 0) {
1253                        mlog_errno(status);
1254                        goto bail;
1255                }
1256
1257                eb->h_next_leaf_blk = 0;
1258                eb_el->l_tree_depth = cpu_to_le16(i);
1259                eb_el->l_next_free_rec = cpu_to_le16(1);
1260                /*
1261                 * This actually counts as an empty extent as
1262                 * c_clusters == 0
1263                 */
1264                eb_el->l_recs[0].e_cpos = cpu_to_le32(new_cpos);
1265                eb_el->l_recs[0].e_blkno = cpu_to_le64(next_blkno);
1266                /*
1267                 * eb_el isn't always an interior node, but even leaf
1268                 * nodes want a zero'd flags and reserved field so
1269                 * this gets the whole 32 bits regardless of use.
1270                 */
1271                eb_el->l_recs[0].e_int_clusters = cpu_to_le32(0);
1272                if (!eb_el->l_tree_depth)
1273                        new_last_eb_blk = le64_to_cpu(eb->h_blkno);
1274
1275                ocfs2_journal_dirty(handle, bh);
1276                next_blkno = le64_to_cpu(eb->h_blkno);
1277        }
1278
1279        /* This is a bit hairy. We want to update up to three blocks
1280         * here without leaving any of them in an inconsistent state
1281         * in case of error. We don't have to worry about
1282         * journal_dirty erroring as it won't unless we've aborted the
1283         * handle (in which case we would never be here) so reserving
1284         * the write with journal_access is all we need to do. */
1285        status = ocfs2_journal_access_eb(handle, et->et_ci, *last_eb_bh,
1286                                         OCFS2_JOURNAL_ACCESS_WRITE);
1287        if (status < 0) {
1288                mlog_errno(status);
1289                goto bail;
1290        }
1291        status = ocfs2_et_root_journal_access(handle, et,
1292                                              OCFS2_JOURNAL_ACCESS_WRITE);
1293        if (status < 0) {
1294                mlog_errno(status);
1295                goto bail;
1296        }
1297        if (eb_bh) {
1298                status = ocfs2_journal_access_eb(handle, et->et_ci, eb_bh,
1299                                                 OCFS2_JOURNAL_ACCESS_WRITE);
1300                if (status < 0) {
1301                        mlog_errno(status);
1302                        goto bail;
1303                }
1304        }
1305
1306        /* Link the new branch into the rest of the tree (el will
1307         * either be on the root_bh, or the extent block passed in. */
1308        i = le16_to_cpu(el->l_next_free_rec);
1309        el->l_recs[i].e_blkno = cpu_to_le64(next_blkno);
1310        el->l_recs[i].e_cpos = cpu_to_le32(new_cpos);
1311        el->l_recs[i].e_int_clusters = 0;
1312        le16_add_cpu(&el->l_next_free_rec, 1);
1313
1314        /* fe needs a new last extent block pointer, as does the
1315         * next_leaf on the previously last-extent-block. */
1316        ocfs2_et_set_last_eb_blk(et, new_last_eb_blk);
1317
1318        eb = (struct ocfs2_extent_block *) (*last_eb_bh)->b_data;
1319        eb->h_next_leaf_blk = cpu_to_le64(new_last_eb_blk);
1320
1321        ocfs2_journal_dirty(handle, *last_eb_bh);
1322        ocfs2_journal_dirty(handle, et->et_root_bh);
1323        if (eb_bh)
1324                ocfs2_journal_dirty(handle, eb_bh);
1325
1326        /*
1327         * Some callers want to track the rightmost leaf so pass it
1328         * back here.
1329         */
1330        brelse(*last_eb_bh);
1331        get_bh(new_eb_bhs[0]);
1332        *last_eb_bh = new_eb_bhs[0];
1333
1334        status = 0;
1335bail:
1336        if (new_eb_bhs) {
1337                for (i = 0; i < new_blocks; i++)
1338                        brelse(new_eb_bhs[i]);
1339                kfree(new_eb_bhs);
1340        }
1341
1342        return status;
1343}
1344
1345/*
1346 * adds another level to the allocation tree.
1347 * returns back the new extent block so you can add a branch to it
1348 * after this call.
1349 */
1350static int ocfs2_shift_tree_depth(handle_t *handle,
1351                                  struct ocfs2_extent_tree *et,
1352                                  struct ocfs2_alloc_context *meta_ac,
1353                                  struct buffer_head **ret_new_eb_bh)
1354{
1355        int status, i, block_given = 0;
1356        u32 new_clusters;
1357        struct buffer_head *new_eb_bh = NULL;
1358        struct ocfs2_extent_block *eb;
1359        struct ocfs2_extent_list  *root_el;
1360        struct ocfs2_extent_list  *eb_el;
1361
1362        if (!ocfs2_is_dealloc_empty(et)) {
1363                status = ocfs2_reuse_blk_from_dealloc(handle, et,
1364                                                      &new_eb_bh, 1,
1365                                                      &block_given);
1366        } else if (meta_ac) {
1367                status = ocfs2_create_new_meta_bhs(handle, et, 1, meta_ac,
1368                                                   &new_eb_bh);
1369
1370        } else {
1371                BUG();
1372        }
1373
1374        if (status < 0) {
1375                mlog_errno(status);
1376                goto bail;
1377        }
1378
1379        eb = (struct ocfs2_extent_block *) new_eb_bh->b_data;
1380        /* ocfs2_create_new_meta_bhs() should create it right! */
1381        BUG_ON(!OCFS2_IS_VALID_EXTENT_BLOCK(eb));
1382
1383        eb_el = &eb->h_list;
1384        root_el = et->et_root_el;
1385
1386        status = ocfs2_journal_access_eb(handle, et->et_ci, new_eb_bh,
1387                                         OCFS2_JOURNAL_ACCESS_CREATE);
1388        if (status < 0) {
1389                mlog_errno(status);
1390                goto bail;
1391        }
1392
1393        /* copy the root extent list data into the new extent block */
1394        eb_el->l_tree_depth = root_el->l_tree_depth;
1395        eb_el->l_next_free_rec = root_el->l_next_free_rec;
1396        for (i = 0; i < le16_to_cpu(root_el->l_next_free_rec); i++)
1397                eb_el->l_recs[i] = root_el->l_recs[i];
1398
1399        ocfs2_journal_dirty(handle, new_eb_bh);
1400
1401        status = ocfs2_et_root_journal_access(handle, et,
1402                                              OCFS2_JOURNAL_ACCESS_WRITE);
1403        if (status < 0) {
1404                mlog_errno(status);
1405                goto bail;
1406        }
1407
1408        new_clusters = ocfs2_sum_rightmost_rec(eb_el);
1409
1410        /* update root_bh now */
1411        le16_add_cpu(&root_el->l_tree_depth, 1);
1412        root_el->l_recs[0].e_cpos = 0;
1413        root_el->l_recs[0].e_blkno = eb->h_blkno;
1414        root_el->l_recs[0].e_int_clusters = cpu_to_le32(new_clusters);
1415        for (i = 1; i < le16_to_cpu(root_el->l_next_free_rec); i++)
1416                memset(&root_el->l_recs[i], 0, sizeof(struct ocfs2_extent_rec));
1417        root_el->l_next_free_rec = cpu_to_le16(1);
1418
1419        /* If this is our 1st tree depth shift, then last_eb_blk
1420         * becomes the allocated extent block */
1421        if (root_el->l_tree_depth == cpu_to_le16(1))
1422                ocfs2_et_set_last_eb_blk(et, le64_to_cpu(eb->h_blkno));
1423
1424        ocfs2_journal_dirty(handle, et->et_root_bh);
1425
1426        *ret_new_eb_bh = new_eb_bh;
1427        new_eb_bh = NULL;
1428        status = 0;
1429bail:
1430        brelse(new_eb_bh);
1431
1432        return status;
1433}
1434
1435/*
1436 * Should only be called when there is no space left in any of the
1437 * leaf nodes. What we want to do is find the lowest tree depth
1438 * non-leaf extent block with room for new records. There are three
1439 * valid results of this search:
1440 *
1441 * 1) a lowest extent block is found, then we pass it back in
1442 *    *lowest_eb_bh and return '0'
1443 *
1444 * 2) the search fails to find anything, but the root_el has room. We
1445 *    pass NULL back in *lowest_eb_bh, but still return '0'
1446 *
1447 * 3) the search fails to find anything AND the root_el is full, in
1448 *    which case we return > 0
1449 *
1450 * return status < 0 indicates an error.
1451 */
1452static int ocfs2_find_branch_target(struct ocfs2_extent_tree *et,
1453                                    struct buffer_head **target_bh)
1454{
1455        int status = 0, i;
1456        u64 blkno;
1457        struct ocfs2_extent_block *eb;
1458        struct ocfs2_extent_list  *el;
1459        struct buffer_head *bh = NULL;
1460        struct buffer_head *lowest_bh = NULL;
1461
1462        *target_bh = NULL;
1463
1464        el = et->et_root_el;
1465
1466        while(le16_to_cpu(el->l_tree_depth) > 1) {
1467                if (le16_to_cpu(el->l_next_free_rec) == 0) {
1468                        status = ocfs2_error(ocfs2_metadata_cache_get_super(et->et_ci),
1469                                        "Owner %llu has empty extent list (next_free_rec == 0)\n",
1470                                        (unsigned long long)ocfs2_metadata_cache_owner(et->et_ci));
1471                        goto bail;
1472                }
1473                i = le16_to_cpu(el->l_next_free_rec) - 1;
1474                blkno = le64_to_cpu(el->l_recs[i].e_blkno);
1475                if (!blkno) {
1476                        status = ocfs2_error(ocfs2_metadata_cache_get_super(et->et_ci),
1477                                        "Owner %llu has extent list where extent # %d has no physical block start\n",
1478                                        (unsigned long long)ocfs2_metadata_cache_owner(et->et_ci), i);
1479                        goto bail;
1480                }
1481
1482                brelse(bh);
1483                bh = NULL;
1484
1485                status = ocfs2_read_extent_block(et->et_ci, blkno, &bh);
1486                if (status < 0) {
1487                        mlog_errno(status);
1488                        goto bail;
1489                }
1490
1491                eb = (struct ocfs2_extent_block *) bh->b_data;
1492                el = &eb->h_list;
1493
1494                if (le16_to_cpu(el->l_next_free_rec) <
1495                    le16_to_cpu(el->l_count)) {
1496                        brelse(lowest_bh);
1497                        lowest_bh = bh;
1498                        get_bh(lowest_bh);
1499                }
1500        }
1501
1502        /* If we didn't find one and the fe doesn't have any room,
1503         * then return '1' */
1504        el = et->et_root_el;
1505        if (!lowest_bh && (el->l_next_free_rec == el->l_count))
1506                status = 1;
1507
1508        *target_bh = lowest_bh;
1509bail:
1510        brelse(bh);
1511
1512        return status;
1513}
1514
1515/*
1516 * Grow a b-tree so that it has more records.
1517 *
1518 * We might shift the tree depth in which case existing paths should
1519 * be considered invalid.
1520 *
1521 * Tree depth after the grow is returned via *final_depth.
1522 *
1523 * *last_eb_bh will be updated by ocfs2_add_branch().
1524 */
1525static int ocfs2_grow_tree(handle_t *handle, struct ocfs2_extent_tree *et,
1526                           int *final_depth, struct buffer_head **last_eb_bh,
1527                           struct ocfs2_alloc_context *meta_ac)
1528{
1529        int ret, shift;
1530        struct ocfs2_extent_list *el = et->et_root_el;
1531        int depth = le16_to_cpu(el->l_tree_depth);
1532        struct buffer_head *bh = NULL;
1533
1534        BUG_ON(meta_ac == NULL && ocfs2_is_dealloc_empty(et));
1535
1536        shift = ocfs2_find_branch_target(et, &bh);
1537        if (shift < 0) {
1538                ret = shift;
1539                mlog_errno(ret);
1540                goto out;
1541        }
1542
1543        /* We traveled all the way to the bottom of the allocation tree
1544         * and didn't find room for any more extents - we need to add
1545         * another tree level */
1546        if (shift) {
1547                BUG_ON(bh);
1548                trace_ocfs2_grow_tree(
1549                        (unsigned long long)
1550                        ocfs2_metadata_cache_owner(et->et_ci),
1551                        depth);
1552
1553                /* ocfs2_shift_tree_depth will return us a buffer with
1554                 * the new extent block (so we can pass that to
1555                 * ocfs2_add_branch). */
1556                ret = ocfs2_shift_tree_depth(handle, et, meta_ac, &bh);
1557                if (ret < 0) {
1558                        mlog_errno(ret);
1559                        goto out;
1560                }
1561                depth++;
1562                if (depth == 1) {
1563                        /*
1564                         * Special case: we have room now if we shifted from
1565                         * tree_depth 0, so no more work needs to be done.
1566                         *
1567                         * We won't be calling add_branch, so pass
1568                         * back *last_eb_bh as the new leaf. At depth
1569                         * zero, it should always be null so there's
1570                         * no reason to brelse.
1571                         */
1572                        BUG_ON(*last_eb_bh);
1573                        get_bh(bh);
1574                        *last_eb_bh = bh;
1575                        goto out;
1576                }
1577        }
1578
1579        /* call ocfs2_add_branch to add the final part of the tree with
1580         * the new data. */
1581        ret = ocfs2_add_branch(handle, et, bh, last_eb_bh,
1582                               meta_ac);
1583        if (ret < 0)
1584                mlog_errno(ret);
1585
1586out:
1587        if (final_depth)
1588                *final_depth = depth;
1589        brelse(bh);
1590        return ret;
1591}
1592
1593/*
1594 * This function will discard the rightmost extent record.
1595 */
1596static void ocfs2_shift_records_right(struct ocfs2_extent_list *el)
1597{
1598        int next_free = le16_to_cpu(el->l_next_free_rec);
1599        int count = le16_to_cpu(el->l_count);
1600        unsigned int num_bytes;
1601
1602        BUG_ON(!next_free);
1603        /* This will cause us to go off the end of our extent list. */
1604        BUG_ON(next_free >= count);
1605
1606        num_bytes = sizeof(struct ocfs2_extent_rec) * next_free;
1607
1608        memmove(&el->l_recs[1], &el->l_recs[0], num_bytes);
1609}
1610
1611static void ocfs2_rotate_leaf(struct ocfs2_extent_list *el,
1612                              struct ocfs2_extent_rec *insert_rec)
1613{
1614        int i, insert_index, next_free, has_empty, num_bytes;
1615        u32 insert_cpos = le32_to_cpu(insert_rec->e_cpos);
1616        struct ocfs2_extent_rec *rec;
1617
1618        next_free = le16_to_cpu(el->l_next_free_rec);
1619        has_empty = ocfs2_is_empty_extent(&el->l_recs[0]);
1620
1621        BUG_ON(!next_free);
1622
1623        /* The tree code before us didn't allow enough room in the leaf. */
1624        BUG_ON(el->l_next_free_rec == el->l_count && !has_empty);
1625
1626        /*
1627         * The easiest way to approach this is to just remove the
1628         * empty extent and temporarily decrement next_free.
1629         */
1630        if (has_empty) {
1631                /*
1632                 * If next_free was 1 (only an empty extent), this
1633                 * loop won't execute, which is fine. We still want
1634                 * the decrement above to happen.
1635                 */
1636                for(i = 0; i < (next_free - 1); i++)
1637                        el->l_recs[i] = el->l_recs[i+1];
1638
1639                next_free--;
1640        }
1641
1642        /*
1643         * Figure out what the new record index should be.
1644         */
1645        for(i = 0; i < next_free; i++) {
1646                rec = &el->l_recs[i];
1647
1648                if (insert_cpos < le32_to_cpu(rec->e_cpos))
1649                        break;
1650        }
1651        insert_index = i;
1652
1653        trace_ocfs2_rotate_leaf(insert_cpos, insert_index,
1654                                has_empty, next_free,
1655                                le16_to_cpu(el->l_count));
1656
1657        BUG_ON(insert_index < 0);
1658        BUG_ON(insert_index >= le16_to_cpu(el->l_count));
1659        BUG_ON(insert_index > next_free);
1660
1661        /*
1662         * No need to memmove if we're just adding to the tail.
1663         */
1664        if (insert_index != next_free) {
1665                BUG_ON(next_free >= le16_to_cpu(el->l_count));
1666
1667                num_bytes = next_free - insert_index;
1668                num_bytes *= sizeof(struct ocfs2_extent_rec);
1669                memmove(&el->l_recs[insert_index + 1],
1670                        &el->l_recs[insert_index],
1671                        num_bytes);
1672        }
1673
1674        /*
1675         * Either we had an empty extent, and need to re-increment or
1676         * there was no empty extent on a non full rightmost leaf node,
1677         * in which case we still need to increment.
1678         */
1679        next_free++;
1680        el->l_next_free_rec = cpu_to_le16(next_free);
1681        /*
1682         * Make sure none of the math above just messed up our tree.
1683         */
1684        BUG_ON(le16_to_cpu(el->l_next_free_rec) > le16_to_cpu(el->l_count));
1685
1686        el->l_recs[insert_index] = *insert_rec;
1687
1688}
1689
1690static void ocfs2_remove_empty_extent(struct ocfs2_extent_list *el)
1691{
1692        int size, num_recs = le16_to_cpu(el->l_next_free_rec);
1693
1694        BUG_ON(num_recs == 0);
1695
1696        if (ocfs2_is_empty_extent(&el->l_recs[0])) {
1697                num_recs--;
1698                size = num_recs * sizeof(struct ocfs2_extent_rec);
1699                memmove(&el->l_recs[0], &el->l_recs[1], size);
1700                memset(&el->l_recs[num_recs], 0,
1701                       sizeof(struct ocfs2_extent_rec));
1702                el->l_next_free_rec = cpu_to_le16(num_recs);
1703        }
1704}
1705
1706/*
1707 * Create an empty extent record .
1708 *
1709 * l_next_free_rec may be updated.
1710 *
1711 * If an empty extent already exists do nothing.
1712 */
1713static void ocfs2_create_empty_extent(struct ocfs2_extent_list *el)
1714{
1715        int next_free = le16_to_cpu(el->l_next_free_rec);
1716
1717        BUG_ON(le16_to_cpu(el->l_tree_depth) != 0);
1718
1719        if (next_free == 0)
1720                goto set_and_inc;
1721
1722        if (ocfs2_is_empty_extent(&el->l_recs[0]))
1723                return;
1724
1725        mlog_bug_on_msg(el->l_count == el->l_next_free_rec,
1726                        "Asked to create an empty extent in a full list:\n"
1727                        "count = %u, tree depth = %u",
1728                        le16_to_cpu(el->l_count),
1729                        le16_to_cpu(el->l_tree_depth));
1730
1731        ocfs2_shift_records_right(el);
1732
1733set_and_inc:
1734        le16_add_cpu(&el->l_next_free_rec, 1);
1735        memset(&el->l_recs[0], 0, sizeof(struct ocfs2_extent_rec));
1736}
1737
1738/*
1739 * For a rotation which involves two leaf nodes, the "root node" is
1740 * the lowest level tree node which contains a path to both leafs. This
1741 * resulting set of information can be used to form a complete "subtree"
1742 *
1743 * This function is passed two full paths from the dinode down to a
1744 * pair of adjacent leaves. It's task is to figure out which path
1745 * index contains the subtree root - this can be the root index itself
1746 * in a worst-case rotation.
1747 *
1748 * The array index of the subtree root is passed back.
1749 */
1750int ocfs2_find_subtree_root(struct ocfs2_extent_tree *et,
1751                            struct ocfs2_path *left,
1752                            struct ocfs2_path *right)
1753{
1754        int i = 0;
1755
1756        /*
1757         * Check that the caller passed in two paths from the same tree.
1758         */
1759        BUG_ON(path_root_bh(left) != path_root_bh(right));
1760
1761        do {
1762                i++;
1763
1764                /*
1765                 * The caller didn't pass two adjacent paths.
1766                 */
1767                mlog_bug_on_msg(i > left->p_tree_depth,
1768                                "Owner %llu, left depth %u, right depth %u\n"
1769                                "left leaf blk %llu, right leaf blk %llu\n",
1770                                (unsigned long long)ocfs2_metadata_cache_owner(et->et_ci),
1771                                left->p_tree_depth, right->p_tree_depth,
1772                                (unsigned long long)path_leaf_bh(left)->b_blocknr,
1773                                (unsigned long long)path_leaf_bh(right)->b_blocknr);
1774        } while (left->p_node[i].bh->b_blocknr ==
1775                 right->p_node[i].bh->b_blocknr);
1776
1777        return i - 1;
1778}
1779
1780typedef void (path_insert_t)(void *, struct buffer_head *);
1781
1782/*
1783 * Traverse a btree path in search of cpos, starting at root_el.
1784 *
1785 * This code can be called with a cpos larger than the tree, in which
1786 * case it will return the rightmost path.
1787 */
1788static int __ocfs2_find_path(struct ocfs2_caching_info *ci,
1789                             struct ocfs2_extent_list *root_el, u32 cpos,
1790                             path_insert_t *func, void *data)
1791{
1792        int i, ret = 0;
1793        u32 range;
1794        u64 blkno;
1795        struct buffer_head *bh = NULL;
1796        struct ocfs2_extent_block *eb;
1797        struct ocfs2_extent_list *el;
1798        struct ocfs2_extent_rec *rec;
1799
1800        el = root_el;
1801        while (el->l_tree_depth) {
1802                if (le16_to_cpu(el->l_next_free_rec) == 0) {
1803                        ocfs2_error(ocfs2_metadata_cache_get_super(ci),
1804                                    "Owner %llu has empty extent list at depth %u\n",
1805                                    (unsigned long long)ocfs2_metadata_cache_owner(ci),
1806                                    le16_to_cpu(el->l_tree_depth));
1807                        ret = -EROFS;
1808                        goto out;
1809
1810                }
1811
1812                for(i = 0; i < le16_to_cpu(el->l_next_free_rec) - 1; i++) {
1813                        rec = &el->l_recs[i];
1814
1815                        /*
1816                         * In the case that cpos is off the allocation
1817                         * tree, this should just wind up returning the
1818                         * rightmost record.
1819                         */
1820                        range = le32_to_cpu(rec->e_cpos) +
1821                                ocfs2_rec_clusters(el, rec);
1822                        if (cpos >= le32_to_cpu(rec->e_cpos) && cpos < range)
1823                            break;
1824                }
1825
1826                blkno = le64_to_cpu(el->l_recs[i].e_blkno);
1827                if (blkno == 0) {
1828                        ocfs2_error(ocfs2_metadata_cache_get_super(ci),
1829                                    "Owner %llu has bad blkno in extent list at depth %u (index %d)\n",
1830                                    (unsigned long long)ocfs2_metadata_cache_owner(ci),
1831                                    le16_to_cpu(el->l_tree_depth), i);
1832                        ret = -EROFS;
1833                        goto out;
1834                }
1835
1836                brelse(bh);
1837                bh = NULL;
1838                ret = ocfs2_read_extent_block(ci, blkno, &bh);
1839                if (ret) {
1840                        mlog_errno(ret);
1841                        goto out;
1842                }
1843
1844                eb = (struct ocfs2_extent_block *) bh->b_data;
1845                el = &eb->h_list;
1846
1847                if (le16_to_cpu(el->l_next_free_rec) >
1848                    le16_to_cpu(el->l_count)) {
1849                        ocfs2_error(ocfs2_metadata_cache_get_super(ci),
1850                                    "Owner %llu has bad count in extent list at block %llu (next free=%u, count=%u)\n",
1851                                    (unsigned long long)ocfs2_metadata_cache_owner(ci),
1852                                    (unsigned long long)bh->b_blocknr,
1853                                    le16_to_cpu(el->l_next_free_rec),
1854                                    le16_to_cpu(el->l_count));
1855                        ret = -EROFS;
1856                        goto out;
1857                }
1858
1859                if (func)
1860                        func(data, bh);
1861        }
1862
1863out:
1864        /*
1865         * Catch any trailing bh that the loop didn't handle.
1866         */
1867        brelse(bh);
1868
1869        return ret;
1870}
1871
1872/*
1873 * Given an initialized path (that is, it has a valid root extent
1874 * list), this function will traverse the btree in search of the path
1875 * which would contain cpos.
1876 *
1877 * The path traveled is recorded in the path structure.
1878 *
1879 * Note that this will not do any comparisons on leaf node extent
1880 * records, so it will work fine in the case that we just added a tree
1881 * branch.
1882 */
1883struct find_path_data {
1884        int index;
1885        struct ocfs2_path *path;
1886};
1887static void find_path_ins(void *data, struct buffer_head *bh)
1888{
1889        struct find_path_data *fp = data;
1890
1891        get_bh(bh);
1892        ocfs2_path_insert_eb(fp->path, fp->index, bh);
1893        fp->index++;
1894}
1895int ocfs2_find_path(struct ocfs2_caching_info *ci,
1896                    struct ocfs2_path *path, u32 cpos)
1897{
1898        struct find_path_data data;
1899
1900        data.index = 1;
1901        data.path = path;
1902        return __ocfs2_find_path(ci, path_root_el(path), cpos,
1903                                 find_path_ins, &data);
1904}
1905
1906static void find_leaf_ins(void *data, struct buffer_head *bh)
1907{
1908        struct ocfs2_extent_block *eb =(struct ocfs2_extent_block *)bh->b_data;
1909        struct ocfs2_extent_list *el = &eb->h_list;
1910        struct buffer_head **ret = data;
1911
1912        /* We want to retain only the leaf block. */
1913        if (le16_to_cpu(el->l_tree_depth) == 0) {
1914                get_bh(bh);
1915                *ret = bh;
1916        }
1917}
1918/*
1919 * Find the leaf block in the tree which would contain cpos. No
1920 * checking of the actual leaf is done.
1921 *
1922 * Some paths want to call this instead of allocating a path structure
1923 * and calling ocfs2_find_path().
1924 *
1925 * This function doesn't handle non btree extent lists.
1926 */
1927int ocfs2_find_leaf(struct ocfs2_caching_info *ci,
1928                    struct ocfs2_extent_list *root_el, u32 cpos,
1929                    struct buffer_head **leaf_bh)
1930{
1931        int ret;
1932        struct buffer_head *bh = NULL;
1933
1934        ret = __ocfs2_find_path(ci, root_el, cpos, find_leaf_ins, &bh);
1935        if (ret) {
1936                mlog_errno(ret);
1937                goto out;
1938        }
1939
1940        *leaf_bh = bh;
1941out:
1942        return ret;
1943}
1944
1945/*
1946 * Adjust the adjacent records (left_rec, right_rec) involved in a rotation.
1947 *
1948 * Basically, we've moved stuff around at the bottom of the tree and
1949 * we need to fix up the extent records above the changes to reflect
1950 * the new changes.
1951 *
1952 * left_rec: the record on the left.
1953 * right_rec: the record to the right of left_rec
1954 * right_child_el: is the child list pointed to by right_rec
1955 *
1956 * By definition, this only works on interior nodes.
1957 */
1958static void ocfs2_adjust_adjacent_records(struct ocfs2_extent_rec *left_rec,
1959                                  struct ocfs2_extent_rec *right_rec,
1960                                  struct ocfs2_extent_list *right_child_el)
1961{
1962        u32 left_clusters, right_end;
1963
1964        /*
1965         * Interior nodes never have holes. Their cpos is the cpos of
1966         * the leftmost record in their child list. Their cluster
1967         * count covers the full theoretical range of their child list
1968         * - the range between their cpos and the cpos of the record
1969         * immediately to their right.
1970         */
1971        left_clusters = le32_to_cpu(right_child_el->l_recs[0].e_cpos);
1972        if (!ocfs2_rec_clusters(right_child_el, &right_child_el->l_recs[0])) {
1973                BUG_ON(right_child_el->l_tree_depth);
1974                BUG_ON(le16_to_cpu(right_child_el->l_next_free_rec) <= 1);
1975                left_clusters = le32_to_cpu(right_child_el->l_recs[1].e_cpos);
1976        }
1977        left_clusters -= le32_to_cpu(left_rec->e_cpos);
1978        left_rec->e_int_clusters = cpu_to_le32(left_clusters);
1979
1980        /*
1981         * Calculate the rightmost cluster count boundary before
1982         * moving cpos - we will need to adjust clusters after
1983         * updating e_cpos to keep the same highest cluster count.
1984         */
1985        right_end = le32_to_cpu(right_rec->e_cpos);
1986        right_end += le32_to_cpu(right_rec->e_int_clusters);
1987
1988        right_rec->e_cpos = left_rec->e_cpos;
1989        le32_add_cpu(&right_rec->e_cpos, left_clusters);
1990
1991        right_end -= le32_to_cpu(right_rec->e_cpos);
1992        right_rec->e_int_clusters = cpu_to_le32(right_end);
1993}
1994
1995/*
1996 * Adjust the adjacent root node records involved in a
1997 * rotation. left_el_blkno is passed in as a key so that we can easily
1998 * find it's index in the root list.
1999 */
2000static void ocfs2_adjust_root_records(struct ocfs2_extent_list *root_el,
2001                                      struct ocfs2_extent_list *left_el,
2002                                      struct ocfs2_extent_list *right_el,
2003                                      u64 left_el_blkno)
2004{
2005        int i;
2006
2007        BUG_ON(le16_to_cpu(root_el->l_tree_depth) <=
2008               le16_to_cpu(left_el->l_tree_depth));
2009
2010        for(i = 0; i < le16_to_cpu(root_el->l_next_free_rec) - 1; i++) {
2011                if (le64_to_cpu(root_el->l_recs[i].e_blkno) == left_el_blkno)
2012                        break;
2013        }
2014
2015        /*
2016         * The path walking code should have never returned a root and
2017         * two paths which are not adjacent.
2018         */
2019        BUG_ON(i >= (le16_to_cpu(root_el->l_next_free_rec) - 1));
2020
2021        ocfs2_adjust_adjacent_records(&root_el->l_recs[i],
2022                                      &root_el->l_recs[i + 1], right_el);
2023}
2024
2025/*
2026 * We've changed a leaf block (in right_path) and need to reflect that
2027 * change back up the subtree.
2028 *
2029 * This happens in multiple places:
2030 *   - When we've moved an extent record from the left path leaf to the right
2031 *     path leaf to make room for an empty extent in the left path leaf.
2032 *   - When our insert into the right path leaf is at the leftmost edge
2033 *     and requires an update of the path immediately to it's left. This
2034 *     can occur at the end of some types of rotation and appending inserts.
2035 *   - When we've adjusted the last extent record in the left path leaf and the
2036 *     1st extent record in the right path leaf during cross extent block merge.
2037 */
2038static void ocfs2_complete_edge_insert(handle_t *handle,
2039                                       struct ocfs2_path *left_path,
2040                                       struct ocfs2_path *right_path,
2041                                       int subtree_index)
2042{
2043        int i, idx;
2044        struct ocfs2_extent_list *el, *left_el, *right_el;
2045        struct ocfs2_extent_rec *left_rec, *right_rec;
2046        struct buffer_head *root_bh = left_path->p_node[subtree_index].bh;
2047
2048        /*
2049         * Update the counts and position values within all the
2050         * interior nodes to reflect the leaf rotation we just did.
2051         *
2052         * The root node is handled below the loop.
2053         *
2054         * We begin the loop with right_el and left_el pointing to the
2055         * leaf lists and work our way up.
2056         *
2057         * NOTE: within this loop, left_el and right_el always refer
2058         * to the *child* lists.
2059         */
2060        left_el = path_leaf_el(left_path);
2061        right_el = path_leaf_el(right_path);
2062        for(i = left_path->p_tree_depth - 1; i > subtree_index; i--) {
2063                trace_ocfs2_complete_edge_insert(i);
2064
2065                /*
2066                 * One nice property of knowing that all of these
2067                 * nodes are below the root is that we only deal with
2068                 * the leftmost right node record and the rightmost
2069                 * left node record.
2070                 */
2071                el = left_path->p_node[i].el;
2072                idx = le16_to_cpu(left_el->l_next_free_rec) - 1;
2073                left_rec = &el->l_recs[idx];
2074
2075                el = right_path->p_node[i].el;
2076                right_rec = &el->l_recs[0];
2077
2078                ocfs2_adjust_adjacent_records(left_rec, right_rec, right_el);
2079
2080                ocfs2_journal_dirty(handle, left_path->p_node[i].bh);
2081                ocfs2_journal_dirty(handle, right_path->p_node[i].bh);
2082
2083                /*
2084                 * Setup our list pointers now so that the current
2085                 * parents become children in the next iteration.
2086                 */
2087                left_el = left_path->p_node[i].el;
2088                right_el = right_path->p_node[i].el;
2089        }
2090
2091        /*
2092         * At the root node, adjust the two adjacent records which
2093         * begin our path to the leaves.
2094         */
2095
2096        el = left_path->p_node[subtree_index].el;
2097        left_el = left_path->p_node[subtree_index + 1].el;
2098        right_el = right_path->p_node[subtree_index + 1].el;
2099
2100        ocfs2_adjust_root_records(el, left_el, right_el,
2101                                  left_path->p_node[subtree_index + 1].bh->b_blocknr);
2102
2103        root_bh = left_path->p_node[subtree_index].bh;
2104
2105        ocfs2_journal_dirty(handle, root_bh);
2106}
2107
2108static int ocfs2_rotate_subtree_right(handle_t *handle,
2109                                      struct ocfs2_extent_tree *et,
2110                                      struct ocfs2_path *left_path,
2111                                      struct ocfs2_path *right_path,
2112                                      int subtree_index)
2113{
2114        int ret, i;
2115        struct buffer_head *right_leaf_bh;
2116        struct buffer_head *left_leaf_bh = NULL;
2117        struct buffer_head *root_bh;
2118        struct ocfs2_extent_list *right_el, *left_el;
2119        struct ocfs2_extent_rec move_rec;
2120
2121        left_leaf_bh = path_leaf_bh(left_path);
2122        left_el = path_leaf_el(left_path);
2123
2124        if (left_el->l_next_free_rec != left_el->l_count) {
2125                ocfs2_error(ocfs2_metadata_cache_get_super(et->et_ci),
2126                            "Inode %llu has non-full interior leaf node %llu (next free = %u)\n",
2127                            (unsigned long long)ocfs2_metadata_cache_owner(et->et_ci),
2128                            (unsigned long long)left_leaf_bh->b_blocknr,
2129                            le16_to_cpu(left_el->l_next_free_rec));
2130                return -EROFS;
2131        }
2132
2133        /*
2134         * This extent block may already have an empty record, so we
2135         * return early if so.
2136         */
2137        if (ocfs2_is_empty_extent(&left_el->l_recs[0]))
2138                return 0;
2139
2140        root_bh = left_path->p_node[subtree_index].bh;
2141        BUG_ON(root_bh != right_path->p_node[subtree_index].bh);
2142
2143        ret = ocfs2_path_bh_journal_access(handle, et->et_ci, right_path,
2144                                           subtree_index);
2145        if (ret) {
2146                mlog_errno(ret);
2147                goto out;
2148        }
2149
2150        for(i = subtree_index + 1; i < path_num_items(right_path); i++) {
2151                ret = ocfs2_path_bh_journal_access(handle, et->et_ci,
2152                                                   right_path, i);
2153                if (ret) {
2154                        mlog_errno(ret);
2155                        goto out;
2156                }
2157
2158                ret = ocfs2_path_bh_journal_access(handle, et->et_ci,
2159                                                   left_path, i);
2160                if (ret) {
2161                        mlog_errno(ret);
2162                        goto out;
2163                }
2164        }
2165
2166        right_leaf_bh = path_leaf_bh(right_path);
2167        right_el = path_leaf_el(right_path);
2168
2169        /* This is a code error, not a disk corruption. */
2170        mlog_bug_on_msg(!right_el->l_next_free_rec, "Inode %llu: Rotate fails "
2171                        "because rightmost leaf block %llu is empty\n",
2172                        (unsigned long long)ocfs2_metadata_cache_owner(et->et_ci),
2173                        (unsigned long long)right_leaf_bh->b_blocknr);
2174
2175        ocfs2_create_empty_extent(right_el);
2176
2177        ocfs2_journal_dirty(handle, right_leaf_bh);
2178
2179        /* Do the copy now. */
2180        i = le16_to_cpu(left_el->l_next_free_rec) - 1;
2181        move_rec = left_el->l_recs[i];
2182        right_el->l_recs[0] = move_rec;
2183
2184        /*
2185         * Clear out the record we just copied and shift everything
2186         * over, leaving an empty extent in the left leaf.
2187         *
2188         * We temporarily subtract from next_free_rec so that the
2189         * shift will lose the tail record (which is now defunct).
2190         */
2191        le16_add_cpu(&left_el->l_next_free_rec, -1);
2192        ocfs2_shift_records_right(left_el);
2193        memset(&left_el->l_recs[0], 0, sizeof(struct ocfs2_extent_rec));
2194        le16_add_cpu(&left_el->l_next_free_rec, 1);
2195
2196        ocfs2_journal_dirty(handle, left_leaf_bh);
2197
2198        ocfs2_complete_edge_insert(handle, left_path, right_path,
2199                                   subtree_index);
2200
2201out:
2202        return ret;
2203}
2204
2205/*
2206 * Given a full path, determine what cpos value would return us a path
2207 * containing the leaf immediately to the left of the current one.
2208 *
2209 * Will return zero if the path passed in is already the leftmost path.
2210 */
2211int ocfs2_find_cpos_for_left_leaf(struct super_block *sb,
2212                                  struct ocfs2_path *path, u32 *cpos)
2213{
2214        int i, j, ret = 0;
2215        u64 blkno;
2216        struct ocfs2_extent_list *el;
2217
2218        BUG_ON(path->p_tree_depth == 0);
2219
2220        *cpos = 0;
2221
2222        blkno = path_leaf_bh(path)->b_blocknr;
2223
2224        /* Start at the tree node just above the leaf and work our way up. */
2225        i = path->p_tree_depth - 1;
2226        while (i >= 0) {
2227                el = path->p_node[i].el;
2228
2229                /*
2230                 * Find the extent record just before the one in our
2231                 * path.
2232                 */
2233                for(j = 0; j < le16_to_cpu(el->l_next_free_rec); j++) {
2234                        if (le64_to_cpu(el->l_recs[j].e_blkno) == blkno) {
2235                                if (j == 0) {
2236                                        if (i == 0) {
2237                                                /*
2238                                                 * We've determined that the
2239                                                 * path specified is already
2240                                                 * the leftmost one - return a
2241                                                 * cpos of zero.
2242                                                 */
2243                                                goto out;
2244                                        }
2245                                        /*
2246                                         * The leftmost record points to our
2247                                         * leaf - we need to travel up the
2248                                         * tree one level.
2249                                         */
2250                                        goto next_node;
2251                                }
2252
2253                                *cpos = le32_to_cpu(el->l_recs[j - 1].e_cpos);
2254                                *cpos = *cpos + ocfs2_rec_clusters(el,
2255                                                           &el->l_recs[j - 1]);
2256                                *cpos = *cpos - 1;
2257                                goto out;
2258                        }
2259                }
2260
2261                /*
2262                 * If we got here, we never found a valid node where
2263                 * the tree indicated one should be.
2264                 */
2265                ocfs2_error(sb, "Invalid extent tree at extent block %llu\n",
2266                            (unsigned long long)blkno);
2267                ret = -EROFS;
2268                goto out;
2269
2270next_node:
2271                blkno = path->p_node[i].bh->b_blocknr;
2272                i--;
2273        }
2274
2275out:
2276        return ret;
2277}
2278
2279/*
2280 * Extend the transaction by enough credits to complete the rotation,
2281 * and still leave at least the original number of credits allocated
2282 * to this transaction.
2283 */
2284static int ocfs2_extend_rotate_transaction(handle_t *handle, int subtree_depth,
2285                                           int op_credits,
2286                                           struct ocfs2_path *path)
2287{
2288        int ret = 0;
2289        int credits = (path->p_tree_depth - subtree_depth) * 2 + 1 + op_credits;
2290
2291        if (handle->h_buffer_credits < credits)
2292                ret = ocfs2_extend_trans(handle,
2293                                         credits - handle->h_buffer_credits);
2294
2295        return ret;
2296}
2297
2298/*
2299 * Trap the case where we're inserting into the theoretical range past
2300 * the _actual_ left leaf range. Otherwise, we'll rotate a record
2301 * whose cpos is less than ours into the right leaf.
2302 *
2303 * It's only necessary to look at the rightmost record of the left
2304 * leaf because the logic that calls us should ensure that the
2305 * theoretical ranges in the path components above the leaves are
2306 * correct.
2307 */
2308static int ocfs2_rotate_requires_path_adjustment(struct ocfs2_path *left_path,
2309                                                 u32 insert_cpos)
2310{
2311        struct ocfs2_extent_list *left_el;
2312        struct ocfs2_extent_rec *rec;
2313        int next_free;
2314
2315        left_el = path_leaf_el(left_path);
2316        next_free = le16_to_cpu(left_el->l_next_free_rec);
2317        rec = &left_el->l_recs[next_free - 1];
2318
2319        if (insert_cpos > le32_to_cpu(rec->e_cpos))
2320                return 1;
2321        return 0;
2322}
2323
2324static int ocfs2_leftmost_rec_contains(struct ocfs2_extent_list *el, u32 cpos)
2325{
2326        int next_free = le16_to_cpu(el->l_next_free_rec);
2327        unsigned int range;
2328        struct ocfs2_extent_rec *rec;
2329
2330        if (next_free == 0)
2331                return 0;
2332
2333        rec = &el->l_recs[0];
2334        if (ocfs2_is_empty_extent(rec)) {
2335                /* Empty list. */
2336                if (next_free == 1)
2337                        return 0;
2338                rec = &el->l_recs[1];
2339        }
2340
2341        range = le32_to_cpu(rec->e_cpos) + ocfs2_rec_clusters(el, rec);
2342        if (cpos >= le32_to_cpu(rec->e_cpos) && cpos < range)
2343                return 1;
2344        return 0;
2345}
2346
2347/*
2348 * Rotate all the records in a btree right one record, starting at insert_cpos.
2349 *
2350 * The path to the rightmost leaf should be passed in.
2351 *
2352 * The array is assumed to be large enough to hold an entire path (tree depth).
2353 *
2354 * Upon successful return from this function:
2355 *
2356 * - The 'right_path' array will contain a path to the leaf block
2357 *   whose range contains e_cpos.
2358 * - That leaf block will have a single empty extent in list index 0.
2359 * - In the case that the rotation requires a post-insert update,
2360 *   *ret_left_path will contain a valid path which can be passed to
2361 *   ocfs2_insert_path().
2362 */
2363static int ocfs2_rotate_tree_right(handle_t *handle,
2364                                   struct ocfs2_extent_tree *et,
2365                                   enum ocfs2_split_type split,
2366                                   u32 insert_cpos,
2367                                   struct ocfs2_path *right_path,
2368                                   struct ocfs2_path **ret_left_path)
2369{
2370        int ret, start, orig_credits = handle->h_buffer_credits;
2371        u32 cpos;
2372        struct ocfs2_path *left_path = NULL;
2373        struct super_block *sb = ocfs2_metadata_cache_get_super(et->et_ci);
2374
2375        *ret_left_path = NULL;
2376
2377        left_path = ocfs2_new_path_from_path(right_path);
2378        if (!left_path) {
2379                ret = -ENOMEM;
2380                mlog_errno(ret);
2381                goto out;
2382        }
2383
2384        ret = ocfs2_find_cpos_for_left_leaf(sb, right_path, &cpos);
2385        if (ret) {
2386                mlog_errno(ret);
2387                goto out;
2388        }
2389
2390        trace_ocfs2_rotate_tree_right(
2391                (unsigned long long)ocfs2_metadata_cache_owner(et->et_ci),
2392                insert_cpos, cpos);
2393
2394        /*
2395         * What we want to do here is:
2396         *
2397         * 1) Start with the rightmost path.
2398         *
2399         * 2) Determine a path to the leaf block directly to the left
2400         *    of that leaf.
2401         *
2402         * 3) Determine the 'subtree root' - the lowest level tree node
2403         *    which contains a path to both leaves.
2404         *
2405         * 4) Rotate the subtree.
2406         *
2407         * 5) Find the next subtree by considering the left path to be
2408         *    the new right path.
2409         *
2410         * The check at the top of this while loop also accepts
2411         * insert_cpos == cpos because cpos is only a _theoretical_
2412         * value to get us the left path - insert_cpos might very well
2413         * be filling that hole.
2414         *
2415         * Stop at a cpos of '0' because we either started at the
2416         * leftmost branch (i.e., a tree with one branch and a
2417         * rotation inside of it), or we've gone as far as we can in
2418         * rotating subtrees.
2419         */
2420        while (cpos && insert_cpos <= cpos) {
2421                trace_ocfs2_rotate_tree_right(
2422                        (unsigned long long)
2423                        ocfs2_metadata_cache_owner(et->et_ci),
2424                        insert_cpos, cpos);
2425
2426                ret = ocfs2_find_path(et->et_ci, left_path, cpos);
2427                if (ret) {
2428                        mlog_errno(ret);
2429                        goto out;
2430                }
2431
2432                mlog_bug_on_msg(path_leaf_bh(left_path) ==
2433                                path_leaf_bh(right_path),
2434                                "Owner %llu: error during insert of %u "
2435                                "(left path cpos %u) results in two identical "
2436                                "paths ending at %llu\n",
2437                                (unsigned long long)ocfs2_metadata_cache_owner(et->et_ci),
2438                                insert_cpos, cpos,
2439                                (unsigned long long)
2440                                path_leaf_bh(left_path)->b_blocknr);
2441
2442                if (split == SPLIT_NONE &&
2443                    ocfs2_rotate_requires_path_adjustment(left_path,
2444                                                          insert_cpos)) {
2445
2446                        /*
2447                         * We've rotated the tree as much as we
2448                         * should. The rest is up to
2449                         * ocfs2_insert_path() to complete, after the
2450                         * record insertion. We indicate this
2451                         * situation by returning the left path.
2452                         *
2453                         * The reason we don't adjust the records here
2454                         * before the record insert is that an error
2455                         * later might break the rule where a parent
2456                         * record e_cpos will reflect the actual
2457                         * e_cpos of the 1st nonempty record of the
2458                         * child list.
2459                         */
2460                        *ret_left_path = left_path;
2461                        goto out_ret_path;
2462                }
2463
2464                start = ocfs2_find_subtree_root(et, left_path, right_path);
2465
2466                trace_ocfs2_rotate_subtree(start,
2467                        (unsigned long long)
2468                        right_path->p_node[start].bh->b_blocknr,
2469                        right_path->p_tree_depth);
2470
2471                ret = ocfs2_extend_rotate_transaction(handle, start,
2472                                                      orig_credits, right_path);
2473                if (ret) {
2474                        mlog_errno(ret);
2475                        goto out;
2476                }
2477
2478                ret = ocfs2_rotate_subtree_right(handle, et, left_path,
2479                                                 right_path, start);
2480                if (ret) {
2481                        mlog_errno(ret);
2482                        goto out;
2483                }
2484
2485                if (split != SPLIT_NONE &&
2486                    ocfs2_leftmost_rec_contains(path_leaf_el(right_path),
2487                                                insert_cpos)) {
2488                        /*
2489                         * A rotate moves the rightmost left leaf
2490                         * record over to the leftmost right leaf
2491                         * slot. If we're doing an extent split
2492                         * instead of a real insert, then we have to
2493                         * check that the extent to be split wasn't
2494                         * just moved over. If it was, then we can
2495                         * exit here, passing left_path back -
2496                         * ocfs2_split_extent() is smart enough to
2497                         * search both leaves.
2498                         */
2499                        *ret_left_path = left_path;
2500                        goto out_ret_path;
2501                }
2502
2503                /*
2504                 * There is no need to re-read the next right path
2505                 * as we know that it'll be our current left
2506                 * path. Optimize by copying values instead.
2507                 */
2508                ocfs2_mv_path(right_path, left_path);
2509
2510                ret = ocfs2_find_cpos_for_left_leaf(sb, right_path, &cpos);
2511                if (ret) {
2512                        mlog_errno(ret);
2513                        goto out;
2514                }
2515        }
2516
2517out:
2518        ocfs2_free_path(left_path);
2519
2520out_ret_path:
2521        return ret;
2522}
2523
2524static int ocfs2_update_edge_lengths(handle_t *handle,
2525                                     struct ocfs2_extent_tree *et,
2526                                     struct ocfs2_path *path)
2527{
2528        int i, idx, ret;
2529        struct ocfs2_extent_rec *rec;
2530        struct ocfs2_extent_list *el;
2531        struct ocfs2_extent_block *eb;
2532        u32 range;
2533
2534        ret = ocfs2_journal_access_path(et->et_ci, handle, path);
2535        if (ret) {
2536                mlog_errno(ret);
2537                goto out;
2538        }
2539
2540        /* Path should always be rightmost. */
2541        eb = (struct ocfs2_extent_block *)path_leaf_bh(path)->b_data;
2542        BUG_ON(eb->h_next_leaf_blk != 0ULL);
2543
2544        el = &eb->h_list;
2545        BUG_ON(le16_to_cpu(el->l_next_free_rec) == 0);
2546        idx = le16_to_cpu(el->l_next_free_rec) - 1;
2547        rec = &el->l_recs[idx];
2548        range = le32_to_cpu(rec->e_cpos) + ocfs2_rec_clusters(el, rec);
2549
2550        for (i = 0; i < path->p_tree_depth; i++) {
2551                el = path->p_node[i].el;
2552                idx = le16_to_cpu(el->l_next_free_rec) - 1;
2553                rec = &el->l_recs[idx];
2554
2555                rec->e_int_clusters = cpu_to_le32(range);
2556                le32_add_cpu(&rec->e_int_clusters, -le32_to_cpu(rec->e_cpos));
2557
2558                ocfs2_journal_dirty(handle, path->p_node[i].bh);
2559        }
2560out:
2561        return ret;
2562}
2563
2564static void ocfs2_unlink_path(handle_t *handle,
2565                              struct ocfs2_extent_tree *et,
2566                              struct ocfs2_cached_dealloc_ctxt *dealloc,
2567                              struct ocfs2_path *path, int unlink_start)
2568{
2569        int ret, i;
2570        struct ocfs2_extent_block *eb;
2571        struct ocfs2_extent_list *el;
2572        struct buffer_head *bh;
2573
2574        for(i = unlink_start; i < path_num_items(path); i++) {
2575                bh = path->p_node[i].bh;
2576
2577                eb = (struct ocfs2_extent_block *)bh->b_data;
2578                /*
2579                 * Not all nodes might have had their final count
2580                 * decremented by the caller - handle this here.
2581                 */
2582                el = &eb->h_list;
2583                if (le16_to_cpu(el->l_next_free_rec) > 1) {
2584                        mlog(ML_ERROR,
2585                             "Inode %llu, attempted to remove extent block "
2586                             "%llu with %u records\n",
2587                             (unsigned long long)ocfs2_metadata_cache_owner(et->et_ci),
2588                             (unsigned long long)le64_to_cpu(eb->h_blkno),
2589                             le16_to_cpu(el->l_next_free_rec));
2590
2591                        ocfs2_journal_dirty(handle, bh);
2592                        ocfs2_remove_from_cache(et->et_ci, bh);
2593                        continue;
2594                }
2595
2596                el->l_next_free_rec = 0;
2597                memset(&el->l_recs[0], 0, sizeof(struct ocfs2_extent_rec));
2598
2599                ocfs2_journal_dirty(handle, bh);
2600
2601                ret = ocfs2_cache_extent_block_free(dealloc, eb);
2602                if (ret)
2603                        mlog_errno(ret);
2604
2605                ocfs2_remove_from_cache(et->et_ci, bh);
2606        }
2607}
2608
2609static void ocfs2_unlink_subtree(handle_t *handle,
2610                                 struct ocfs2_extent_tree *et,
2611                                 struct ocfs2_path *left_path,
2612                                 struct ocfs2_path *right_path,
2613                                 int subtree_index,
2614                                 struct ocfs2_cached_dealloc_ctxt *dealloc)
2615{
2616        int i;
2617        struct buffer_head *root_bh = left_path->p_node[subtree_index].bh;
2618        struct ocfs2_extent_list *root_el = left_path->p_node[subtree_index].el;
2619        struct ocfs2_extent_block *eb;
2620
2621        eb = (struct ocfs2_extent_block *)right_path->p_node[subtree_index + 1].bh->b_data;
2622
2623        for(i = 1; i < le16_to_cpu(root_el->l_next_free_rec); i++)
2624                if (root_el->l_recs[i].e_blkno == eb->h_blkno)
2625                        break;
2626
2627        BUG_ON(i >= le16_to_cpu(root_el->l_next_free_rec));
2628
2629        memset(&root_el->l_recs[i], 0, sizeof(struct ocfs2_extent_rec));
2630        le16_add_cpu(&root_el->l_next_free_rec, -1);
2631
2632        eb = (struct ocfs2_extent_block *)path_leaf_bh(left_path)->b_data;
2633        eb->h_next_leaf_blk = 0;
2634
2635        ocfs2_journal_dirty(handle, root_bh);
2636        ocfs2_journal_dirty(handle, path_leaf_bh(left_path));
2637
2638        ocfs2_unlink_path(handle, et, dealloc, right_path,
2639                          subtree_index + 1);
2640}
2641
2642static int ocfs2_rotate_subtree_left(handle_t *handle,
2643                                     struct ocfs2_extent_tree *et,
2644                                     struct ocfs2_path *left_path,
2645                                     struct ocfs2_path *right_path,
2646                                     int subtree_index,
2647                                     struct ocfs2_cached_dealloc_ctxt *dealloc,
2648                                     int *deleted)
2649{
2650        int ret, i, del_right_subtree = 0, right_has_empty = 0;
2651        struct buffer_head *root_bh, *et_root_bh = path_root_bh(right_path);
2652        struct ocfs2_extent_list *right_leaf_el, *left_leaf_el;
2653        struct ocfs2_extent_block *eb;
2654
2655        *deleted = 0;
2656
2657        right_leaf_el = path_leaf_el(right_path);
2658        left_leaf_el = path_leaf_el(left_path);
2659        root_bh = left_path->p_node[subtree_index].bh;
2660        BUG_ON(root_bh != right_path->p_node[subtree_index].bh);
2661
2662        if (!ocfs2_is_empty_extent(&left_leaf_el->l_recs[0]))
2663                return 0;
2664
2665        eb = (struct ocfs2_extent_block *)path_leaf_bh(right_path)->b_data;
2666        if (ocfs2_is_empty_extent(&right_leaf_el->l_recs[0])) {
2667                /*
2668                 * It's legal for us to proceed if the right leaf is
2669                 * the rightmost one and it has an empty extent. There
2670                 * are two cases to handle - whether the leaf will be
2671                 * empty after removal or not. If the leaf isn't empty
2672                 * then just remove the empty extent up front. The
2673                 * next block will handle empty leaves by flagging
2674                 * them for unlink.
2675                 *
2676                 * Non rightmost leaves will throw -EAGAIN and the
2677                 * caller can manually move the subtree and retry.
2678                 */
2679
2680                if (eb->h_next_leaf_blk != 0ULL)
2681                        return -EAGAIN;
2682
2683                if (le16_to_cpu(right_leaf_el->l_next_free_rec) > 1) {
2684                        ret = ocfs2_journal_access_eb(handle, et->et_ci,
2685                                                      path_leaf_bh(right_path),
2686                                                      OCFS2_JOURNAL_ACCESS_WRITE);
2687                        if (ret) {
2688                                mlog_errno(ret);
2689                                goto out;
2690                        }
2691
2692                        ocfs2_remove_empty_extent(right_leaf_el);
2693                } else
2694                        right_has_empty = 1;
2695        }
2696
2697        if (eb->h_next_leaf_blk == 0ULL &&
2698            le16_to_cpu(right_leaf_el->l_next_free_rec) == 1) {
2699                /*
2700                 * We have to update i_last_eb_blk during the meta
2701                 * data delete.
2702                 */
2703                ret = ocfs2_et_root_journal_access(handle, et,
2704                                                   OCFS2_JOURNAL_ACCESS_WRITE);
2705                if (ret) {
2706                        mlog_errno(ret);
2707                        goto out;
2708                }
2709
2710                del_right_subtree = 1;
2711        }
2712
2713        /*
2714         * Getting here with an empty extent in the right path implies
2715         * that it's the rightmost path and will be deleted.
2716         */
2717        BUG_ON(right_has_empty && !del_right_subtree);
2718
2719        ret = ocfs2_path_bh_journal_access(handle, et->et_ci, right_path,
2720                                           subtree_index);
2721        if (ret) {
2722                mlog_errno(ret);
2723                goto out;
2724        }
2725
2726        for(i = subtree_index + 1; i < path_num_items(right_path); i++) {
2727                ret = ocfs2_path_bh_journal_access(handle, et->et_ci,
2728                                                   right_path, i);
2729                if (ret) {
2730                        mlog_errno(ret);
2731                        goto out;
2732                }
2733
2734                ret = ocfs2_path_bh_journal_access(handle, et->et_ci,
2735                                                   left_path, i);
2736                if (ret) {
2737                        mlog_errno(ret);
2738                        goto out;
2739                }
2740        }
2741
2742        if (!right_has_empty) {
2743                /*
2744                 * Only do this if we're moving a real
2745                 * record. Otherwise, the action is delayed until
2746                 * after removal of the right path in which case we
2747                 * can do a simple shift to remove the empty extent.
2748                 */
2749                ocfs2_rotate_leaf(left_leaf_el, &right_leaf_el->l_recs[0]);
2750                memset(&right_leaf_el->l_recs[0], 0,
2751                       sizeof(struct ocfs2_extent_rec));
2752        }
2753        if (eb->h_next_leaf_blk == 0ULL) {
2754                /*
2755                 * Move recs over to get rid of empty extent, decrease
2756                 * next_free. This is allowed to remove the last
2757                 * extent in our leaf (setting l_next_free_rec to
2758                 * zero) - the delete code below won't care.
2759                 */
2760                ocfs2_remove_empty_extent(right_leaf_el);
2761        }
2762
2763        ocfs2_journal_dirty(handle, path_leaf_bh(left_path));
2764        ocfs2_journal_dirty(handle, path_leaf_bh(right_path));
2765
2766        if (del_right_subtree) {
2767                ocfs2_unlink_subtree(handle, et, left_path, right_path,
2768                                     subtree_index, dealloc);
2769                ret = ocfs2_update_edge_lengths(handle, et, left_path);
2770                if (ret) {
2771                        mlog_errno(ret);
2772                        goto out;
2773                }
2774
2775                eb = (struct ocfs2_extent_block *)path_leaf_bh(left_path)->b_data;
2776                ocfs2_et_set_last_eb_blk(et, le64_to_cpu(eb->h_blkno));
2777
2778                /*
2779                 * Removal of the extent in the left leaf was skipped
2780                 * above so we could delete the right path
2781                 * 1st.
2782                 */
2783                if (right_has_empty)
2784                        ocfs2_remove_empty_extent(left_leaf_el);
2785
2786                ocfs2_journal_dirty(handle, et_root_bh);
2787
2788                *deleted = 1;
2789        } else
2790                ocfs2_complete_edge_insert(handle, left_path, right_path,
2791                                           subtree_index);
2792
2793out:
2794        return ret;
2795}
2796
2797/*
2798 * Given a full path, determine what cpos value would return us a path
2799 * containing the leaf immediately to the right of the current one.
2800 *
2801 * Will return zero if the path passed in is already the rightmost path.
2802 *
2803 * This looks similar, but is subtly different to
2804 * ocfs2_find_cpos_for_left_leaf().
2805 */
2806int ocfs2_find_cpos_for_right_leaf(struct super_block *sb,
2807                                   struct ocfs2_path *path, u32 *cpos)
2808{
2809        int i, j, ret = 0;
2810        u64 blkno;
2811        struct ocfs2_extent_list *el;
2812
2813        *cpos = 0;
2814
2815        if (path->p_tree_depth == 0)
2816                return 0;
2817
2818        blkno = path_leaf_bh(path)->b_blocknr;
2819
2820        /* Start at the tree node just above the leaf and work our way up. */
2821        i = path->p_tree_depth - 1;
2822        while (i >= 0) {
2823                int next_free;
2824
2825                el = path->p_node[i].el;
2826
2827                /*
2828                 * Find the extent record just after the one in our
2829                 * path.
2830                 */
2831                next_free = le16_to_cpu(el->l_next_free_rec);
2832                for(j = 0; j < le16_to_cpu(el->l_next_free_rec); j++) {
2833                        if (le64_to_cpu(el->l_recs[j].e_blkno) == blkno) {
2834                                if (j == (next_free - 1)) {
2835                                        if (i == 0) {
2836                                                /*
2837                                                 * We've determined that the
2838                                                 * path specified is already
2839                                                 * the rightmost one - return a
2840                                                 * cpos of zero.
2841                                                 */
2842                                                goto out;
2843                                        }
2844                                        /*
2845                                         * The rightmost record points to our
2846                                         * leaf - we need to travel up the
2847                                         * tree one level.
2848                                         */
2849                                        goto next_node;
2850                                }
2851
2852                                *cpos = le32_to_cpu(el->l_recs[j + 1].e_cpos);
2853                                goto out;
2854                        }
2855                }
2856
2857                /*
2858                 * If we got here, we never found a valid node where
2859                 * the tree indicated one should be.
2860                 */
2861                ocfs2_error(sb, "Invalid extent tree at extent block %llu\n",
2862                            (unsigned long long)blkno);
2863                ret = -EROFS;
2864                goto out;
2865
2866next_node:
2867                blkno = path->p_node[i].bh->b_blocknr;
2868                i--;
2869        }
2870
2871out:
2872        return ret;
2873}
2874
2875static int ocfs2_rotate_rightmost_leaf_left(handle_t *handle,
2876                                            struct ocfs2_extent_tree *et,
2877                                            struct ocfs2_path *path)
2878{
2879        int ret;
2880        struct buffer_head *bh = path_leaf_bh(path);
2881        struct ocfs2_extent_list *el = path_leaf_el(path);
2882
2883        if (!ocfs2_is_empty_extent(&el->l_recs[0]))
2884                return 0;
2885
2886        ret = ocfs2_path_bh_journal_access(handle, et->et_ci, path,
2887                                           path_num_items(path) - 1);
2888        if (ret) {
2889                mlog_errno(ret);
2890                goto out;
2891        }
2892
2893        ocfs2_remove_empty_extent(el);
2894        ocfs2_journal_dirty(handle, bh);
2895
2896out:
2897        return ret;
2898}
2899
2900static int __ocfs2_rotate_tree_left(handle_t *handle,
2901                                    struct ocfs2_extent_tree *et,
2902                                    int orig_credits,
2903                                    struct ocfs2_path *path,
2904                                    struct ocfs2_cached_dealloc_ctxt *dealloc,
2905                                    struct ocfs2_path **empty_extent_path)
2906{
2907        int ret, subtree_root, deleted;
2908        u32 right_cpos;
2909        struct ocfs2_path *left_path = NULL;
2910        struct ocfs2_path *right_path = NULL;
2911        struct super_block *sb = ocfs2_metadata_cache_get_super(et->et_ci);
2912
2913        if (!ocfs2_is_empty_extent(&(path_leaf_el(path)->l_recs[0])))
2914                return 0;
2915
2916        *empty_extent_path = NULL;
2917
2918        ret = ocfs2_find_cpos_for_right_leaf(sb, path, &right_cpos);
2919        if (ret) {
2920                mlog_errno(ret);
2921                goto out;
2922        }
2923
2924        left_path = ocfs2_new_path_from_path(path);
2925        if (!left_path) {
2926                ret = -ENOMEM;
2927                mlog_errno(ret);
2928                goto out;
2929        }
2930
2931        ocfs2_cp_path(left_path, path);
2932
2933        right_path = ocfs2_new_path_from_path(path);
2934        if (!right_path) {
2935                ret = -ENOMEM;
2936                mlog_errno(ret);
2937                goto out;
2938        }
2939
2940        while (right_cpos) {
2941                ret = ocfs2_find_path(et->et_ci, right_path, right_cpos);
2942                if (ret) {
2943                        mlog_errno(ret);
2944                        goto out;
2945                }
2946
2947                subtree_root = ocfs2_find_subtree_root(et, left_path,
2948                                                       right_path);
2949
2950                trace_ocfs2_rotate_subtree(subtree_root,
2951                     (unsigned long long)
2952                     right_path->p_node[subtree_root].bh->b_blocknr,
2953                     right_path->p_tree_depth);
2954
2955                ret = ocfs2_extend_rotate_transaction(handle, 0,
2956                                                      orig_credits, left_path);
2957                if (ret) {
2958                        mlog_errno(ret);
2959                        goto out;
2960                }
2961
2962                /*
2963                 * Caller might still want to make changes to the
2964                 * tree root, so re-add it to the journal here.
2965                 */
2966                ret = ocfs2_path_bh_journal_access(handle, et->et_ci,
2967                                                   left_path, 0);
2968                if (ret) {
2969                        mlog_errno(ret);
2970                        goto out;
2971                }
2972
2973                ret = ocfs2_rotate_subtree_left(handle, et, left_path,
2974                                                right_path, subtree_root,
2975                                                dealloc, &deleted);
2976                if (ret == -EAGAIN) {
2977                        /*
2978                         * The rotation has to temporarily stop due to
2979                         * the right subtree having an empty
2980                         * extent. Pass it back to the caller for a
2981                         * fixup.
2982                         */
2983                        *empty_extent_path = right_path;
2984                        right_path = NULL;
2985                        goto out;
2986                }
2987                if (ret) {
2988                        mlog_errno(ret);
2989                        goto out;
2990                }
2991
2992                /*
2993                 * The subtree rotate might have removed records on
2994                 * the rightmost edge. If so, then rotation is
2995                 * complete.
2996                 */
2997                if (deleted)
2998                        break;
2999
3000                ocfs2_mv_path(left_path, right_path);
3001
3002                ret = ocfs2_find_cpos_for_right_leaf(sb, left_path,
3003                                                     &right_cpos);
3004                if (ret) {
3005                        mlog_errno(ret);
3006                        goto out;
3007                }
3008        }
3009
3010out:
3011        ocfs2_free_path(right_path);
3012        ocfs2_free_path(left_path);
3013
3014        return ret;
3015}
3016
3017static int ocfs2_remove_rightmost_path(handle_t *handle,
3018                                struct ocfs2_extent_tree *et,
3019                                struct ocfs2_path *path,
3020                                struct ocfs2_cached_dealloc_ctxt *dealloc)
3021{
3022        int ret, subtree_index;
3023        u32 cpos;
3024        struct ocfs2_path *left_path = NULL;
3025        struct ocfs2_extent_block *eb;
3026        struct ocfs2_extent_list *el;
3027
3028        ret = ocfs2_et_sanity_check(et);
3029        if (ret)
3030                goto out;
3031
3032        ret = ocfs2_journal_access_path(et->et_ci, handle, path);
3033        if (ret) {
3034                mlog_errno(ret);
3035                goto out;
3036        }
3037
3038        ret = ocfs2_find_cpos_for_left_leaf(ocfs2_metadata_cache_get_super(et->et_ci),
3039                                            path, &cpos);
3040        if (ret) {
3041                mlog_errno(ret);
3042                goto out;
3043        }
3044
3045        if (cpos) {
3046                /*
3047                 * We have a path to the left of this one - it needs
3048                 * an update too.
3049                 */
3050                left_path = ocfs2_new_path_from_path(path);
3051                if (!left_path) {
3052                        ret = -ENOMEM;
3053                        mlog_errno(ret);
3054                        goto out;
3055                }
3056
3057                ret = ocfs2_find_path(et->et_ci, left_path, cpos);
3058                if (ret) {
3059                        mlog_errno(ret);
3060                        goto out;
3061                }
3062
3063                ret = ocfs2_journal_access_path(et->et_ci, handle, left_path);
3064                if (ret) {
3065                        mlog_errno(ret);
3066                        goto out;
3067                }
3068
3069                subtree_index = ocfs2_find_subtree_root(et, left_path, path);
3070
3071                ocfs2_unlink_subtree(handle, et, left_path, path,
3072                                     subtree_index, dealloc);
3073                ret = ocfs2_update_edge_lengths(handle, et, left_path);
3074                if (ret) {
3075                        mlog_errno(ret);
3076                        goto out;
3077                }
3078
3079                eb = (struct ocfs2_extent_block *)path_leaf_bh(left_path)->b_data;
3080                ocfs2_et_set_last_eb_blk(et, le64_to_cpu(eb->h_blkno));
3081        } else {
3082                /*
3083                 * 'path' is also the leftmost path which
3084                 * means it must be the only one. This gets
3085                 * handled differently because we want to
3086                 * revert the root back to having extents
3087                 * in-line.
3088                 */
3089                ocfs2_unlink_path(handle, et, dealloc, path, 1);
3090
3091                el = et->et_root_el;
3092                el->l_tree_depth = 0;
3093                el->l_next_free_rec = 0;
3094                memset(&el->l_recs[0], 0, sizeof(struct ocfs2_extent_rec));
3095
3096                ocfs2_et_set_last_eb_blk(et, 0);
3097        }
3098
3099        ocfs2_journal_dirty(handle, path_root_bh(path));
3100
3101out:
3102        ocfs2_free_path(left_path);
3103        return ret;
3104}
3105
3106static int ocfs2_remove_rightmost_empty_extent(struct ocfs2_super *osb,
3107                                struct ocfs2_extent_tree *et,
3108                                struct ocfs2_path *path,
3109                                struct ocfs2_cached_dealloc_ctxt *dealloc)
3110{
3111        handle_t *handle;
3112        int ret;
3113        int credits = path->p_tree_depth * 2 + 1;
3114
3115        handle = ocfs2_start_trans(osb, credits);
3116        if (IS_ERR(handle)) {
3117                ret = PTR_ERR(handle);
3118                mlog_errno(ret);
3119                return ret;
3120        }
3121
3122        ret = ocfs2_remove_rightmost_path(handle, et, path, dealloc);
3123        if (ret)
3124                mlog_errno(ret);
3125
3126        ocfs2_commit_trans(osb, handle);
3127        return ret;
3128}
3129
3130/*
3131 * Left rotation of btree records.
3132 *
3133 * In many ways, this is (unsurprisingly) the opposite of right
3134 * rotation. We start at some non-rightmost path containing an empty
3135 * extent in the leaf block. The code works its way to the rightmost
3136 * path by rotating records to the left in every subtree.
3137 *
3138 * This is used by any code which reduces the number of extent records
3139 * in a leaf. After removal, an empty record should be placed in the
3140 * leftmost list position.
3141 *
3142 * This won't handle a length update of the rightmost path records if
3143 * the rightmost tree leaf record is removed so the caller is
3144 * responsible for detecting and correcting that.
3145 */
3146static int ocfs2_rotate_tree_left(handle_t *handle,
3147                                  struct ocfs2_extent_tree *et,
3148                                  struct ocfs2_path *path,
3149                                  struct ocfs2_cached_dealloc_ctxt *dealloc)
3150{
3151        int ret, orig_credits = handle->h_buffer_credits;
3152        struct ocfs2_path *tmp_path = NULL, *restart_path = NULL;
3153        struct ocfs2_extent_block *eb;
3154        struct ocfs2_extent_list *el;
3155
3156        el = path_leaf_el(path);
3157        if (!ocfs2_is_empty_extent(&el->l_recs[0]))
3158                return 0;
3159
3160        if (path->p_tree_depth == 0) {
3161rightmost_no_delete:
3162                /*
3163                 * Inline extents. This is trivially handled, so do
3164                 * it up front.
3165                 */
3166                ret = ocfs2_rotate_rightmost_leaf_left(handle, et, path);
3167                if (ret)
3168                        mlog_errno(ret);
3169                goto out;
3170        }
3171
3172        /*
3173         * Handle rightmost branch now. There's several cases:
3174         *  1) simple rotation leaving records in there. That's trivial.
3175         *  2) rotation requiring a branch delete - there's no more
3176         *     records left. Two cases of this:
3177         *     a) There are branches to the left.
3178         *     b) This is also the leftmost (the only) branch.
3179         *
3180         *  1) is handled via ocfs2_rotate_rightmost_leaf_left()
3181         *  2a) we need the left branch so that we can update it with the unlink
3182         *  2b) we need to bring the root back to inline extents.
3183         */
3184
3185        eb = (struct ocfs2_extent_block *)path_leaf_bh(path)->b_data;
3186        el = &eb->h_list;
3187        if (eb->h_next_leaf_blk == 0) {
3188                /*
3189                 * This gets a bit tricky if we're going to delete the
3190                 * rightmost path. Get the other cases out of the way
3191                 * 1st.
3192                 */
3193                if (le16_to_cpu(el->l_next_free_rec) > 1)
3194                        goto rightmost_no_delete;
3195
3196                if (le16_to_cpu(el->l_next_free_rec) == 0) {
3197                        ret = ocfs2_error(ocfs2_metadata_cache_get_super(et->et_ci),
3198                                        "Owner %llu has empty extent block at %llu\n",
3199                                        (unsigned long long)ocfs2_metadata_cache_owner(et->et_ci),
3200                                        (unsigned long long)le64_to_cpu(eb->h_blkno));
3201                        goto out;
3202                }
3203
3204                /*
3205                 * XXX: The caller can not trust "path" any more after
3206                 * this as it will have been deleted. What do we do?
3207                 *
3208                 * In theory the rotate-for-merge code will never get
3209                 * here because it'll always ask for a rotate in a
3210                 * nonempty list.
3211                 */
3212
3213                ret = ocfs2_remove_rightmost_path(handle, et, path,
3214                                                  dealloc);
3215                if (ret)
3216                        mlog_errno(ret);
3217                goto out;
3218        }
3219
3220        /*
3221         * Now we can loop, remembering the path we get from -EAGAIN
3222         * and restarting from there.
3223         */
3224try_rotate:
3225        ret = __ocfs2_rotate_tree_left(handle, et, orig_credits, path,
3226                                       dealloc, &restart_path);
3227        if (ret && ret != -EAGAIN) {
3228                mlog_errno(ret);
3229                goto out;
3230        }
3231
3232        while (ret == -EAGAIN) {
3233                tmp_path = restart_path;
3234                restart_path = NULL;
3235
3236                ret = __ocfs2_rotate_tree_left(handle, et, orig_credits,
3237                                               tmp_path, dealloc,
3238                                               &restart_path);
3239                if (ret && ret != -EAGAIN) {
3240                        mlog_errno(ret);
3241                        goto out;
3242                }
3243
3244                ocfs2_free_path(tmp_path);
3245                tmp_path = NULL;
3246
3247                if (ret == 0)
3248                        goto try_rotate;
3249        }
3250
3251out:
3252        ocfs2_free_path(tmp_path);
3253        ocfs2_free_path(restart_path);
3254        return ret;
3255}
3256
3257static void ocfs2_cleanup_merge(struct ocfs2_extent_list *el,
3258                                int index)
3259{
3260        struct ocfs2_extent_rec *rec = &el->l_recs[index];
3261        unsigned int size;
3262
3263        if (rec->e_leaf_clusters == 0) {
3264                /*
3265                 * We consumed all of the merged-from record. An empty
3266                 * extent cannot exist anywhere but the 1st array
3267                 * position, so move things over if the merged-from
3268                 * record doesn't occupy that position.
3269                 *
3270                 * This creates a new empty extent so the caller
3271                 * should be smart enough to have removed any existing
3272                 * ones.
3273                 */
3274                if (index > 0) {
3275                        BUG_ON(ocfs2_is_empty_extent(&el->l_recs[0]));
3276                        size = index * sizeof(struct ocfs2_extent_rec);
3277                        memmove(&el->l_recs[1], &el->l_recs[0], size);
3278                }
3279
3280                /*
3281                 * Always memset - the caller doesn't check whether it
3282                 * created an empty extent, so there could be junk in
3283                 * the other fields.
3284                 */
3285                memset(&el->l_recs[0], 0, sizeof(struct ocfs2_extent_rec));
3286        }
3287}
3288
3289static int ocfs2_get_right_path(struct ocfs2_extent_tree *et,
3290                                struct ocfs2_path *left_path,
3291                                struct ocfs2_path **ret_right_path)
3292{
3293        int ret;
3294        u32 right_cpos;
3295        struct ocfs2_path *right_path = NULL;
3296        struct ocfs2_extent_list *left_el;
3297
3298        *ret_right_path = NULL;
3299
3300        /* This function shouldn't be called for non-trees. */
3301        BUG_ON(left_path->p_tree_depth == 0);
3302
3303        left_el = path_leaf_el(left_path);
3304        BUG_ON(left_el->l_next_free_rec != left_el->l_count);
3305
3306        ret = ocfs2_find_cpos_for_right_leaf(ocfs2_metadata_cache_get_super(et->et_ci),
3307                                             left_path, &right_cpos);
3308        if (ret) {
3309                mlog_errno(ret);
3310                goto out;
3311        }
3312
3313        /* This function shouldn't be called for the rightmost leaf. */
3314        BUG_ON(right_cpos == 0);
3315
3316        right_path = ocfs2_new_path_from_path(left_path);
3317        if (!right_path) {
3318                ret = -ENOMEM;
3319                mlog_errno(ret);
3320                goto out;
3321        }
3322
3323        ret = ocfs2_find_path(et->et_ci, right_path, right_cpos);
3324        if (ret) {
3325                mlog_errno(ret);
3326                goto out;
3327        }
3328
3329        *ret_right_path = right_path;
3330out:
3331        if (ret)
3332                ocfs2_free_path(right_path);
3333        return ret;
3334}
3335
3336/*
3337 * Remove split_rec clusters from the record at index and merge them
3338 * onto the beginning of the record "next" to it.
3339 * For index < l_count - 1, the next means the extent rec at index + 1.
3340 * For index == l_count - 1, the "next" means the 1st extent rec of the
3341 * next extent block.
3342 */
3343static int ocfs2_merge_rec_right(struct ocfs2_path *left_path,
3344                                 handle_t *handle,
3345                                 struct ocfs2_extent_tree *et,
3346                                 struct ocfs2_extent_rec *split_rec,
3347                                 int index)
3348{
3349        int ret, next_free, i;
3350        unsigned int split_clusters = le16_to_cpu(split_rec->e_leaf_clusters);
3351        struct ocfs2_extent_rec *left_rec;
3352        struct ocfs2_extent_rec *right_rec;
3353        struct ocfs2_extent_list *right_el;
3354        struct ocfs2_path *right_path = NULL;
3355        int subtree_index = 0;
3356        struct ocfs2_extent_list *el = path_leaf_el(left_path);
3357        struct buffer_head *bh = path_leaf_bh(left_path);
3358        struct buffer_head *root_bh = NULL;
3359
3360        BUG_ON(index >= le16_to_cpu(el->l_next_free_rec));
3361        left_rec = &el->l_recs[index];
3362
3363        if (index == le16_to_cpu(el->l_next_free_rec) - 1 &&
3364            le16_to_cpu(el->l_next_free_rec) == le16_to_cpu(el->l_count)) {
3365                /* we meet with a cross extent block merge. */
3366                ret = ocfs2_get_right_path(et, left_path, &right_path);
3367                if (ret) {
3368                        mlog_errno(ret);
3369                        return ret;
3370                }
3371
3372                right_el = path_leaf_el(right_path);
3373                next_free = le16_to_cpu(right_el->l_next_free_rec);
3374                BUG_ON(next_free <= 0);
3375                right_rec = &right_el->l_recs[0];
3376                if (ocfs2_is_empty_extent(right_rec)) {
3377                        BUG_ON(next_free <= 1);
3378                        right_rec = &right_el->l_recs[1];
3379                }
3380
3381                BUG_ON(le32_to_cpu(left_rec->e_cpos) +
3382                       le16_to_cpu(left_rec->e_leaf_clusters) !=
3383                       le32_to_cpu(right_rec->e_cpos));
3384
3385                subtree_index = ocfs2_find_subtree_root(et, left_path,
3386                                                        right_path);
3387
3388                ret = ocfs2_extend_rotate_transaction(handle, subtree_index,
3389                                                      handle->h_buffer_credits,
3390                                                      right_path);
3391                if (ret) {
3392                        mlog_errno(ret);
3393                        goto out;
3394                }
3395
3396                root_bh = left_path->p_node[subtree_index].bh;
3397                BUG_ON(root_bh != right_path->p_node[subtree_index].bh);
3398
3399                ret = ocfs2_path_bh_journal_access(handle, et->et_ci, right_path,
3400                                                   subtree_index);
3401                if (ret) {
3402                        mlog_errno(ret);
3403                        goto out;
3404                }
3405
3406                for (i = subtree_index + 1;
3407                     i < path_num_items(right_path); i++) {
3408                        ret = ocfs2_path_bh_journal_access(handle, et->et_ci,
3409                                                           right_path, i);
3410                        if (ret) {
3411                                mlog_errno(ret);
3412                                goto out;
3413                        }
3414
3415                        ret = ocfs2_path_bh_journal_access(handle, et->et_ci,
3416                                                           left_path, i);
3417                        if (ret) {
3418                                mlog_errno(ret);
3419                                goto out;
3420                        }
3421                }
3422
3423        } else {
3424                BUG_ON(index == le16_to_cpu(el->l_next_free_rec) - 1);
3425                right_rec = &el->l_recs[index + 1];
3426        }
3427
3428        ret = ocfs2_path_bh_journal_access(handle, et->et_ci, left_path,
3429                                           path_num_items(left_path) - 1);
3430        if (ret) {
3431                mlog_errno(ret);
3432                goto out;
3433        }
3434
3435        le16_add_cpu(&left_rec->e_leaf_clusters, -split_clusters);
3436
3437        le32_add_cpu(&right_rec->e_cpos, -split_clusters);
3438        le64_add_cpu(&right_rec->e_blkno,
3439                     -ocfs2_clusters_to_blocks(ocfs2_metadata_cache_get_super(et->et_ci),
3440                                               split_clusters));
3441        le16_add_cpu(&right_rec->e_leaf_clusters, split_clusters);
3442
3443        ocfs2_cleanup_merge(el, index);
3444
3445        ocfs2_journal_dirty(handle, bh);
3446        if (right_path) {
3447                ocfs2_journal_dirty(handle, path_leaf_bh(right_path));
3448                ocfs2_complete_edge_insert(handle, left_path, right_path,
3449                                           subtree_index);
3450        }
3451out:
3452        ocfs2_free_path(right_path);
3453        return ret;
3454}
3455
3456static int ocfs2_get_left_path(struct ocfs2_extent_tree *et,
3457                               struct ocfs2_path *right_path,
3458                               struct ocfs2_path **ret_left_path)
3459{
3460        int ret;
3461        u32 left_cpos;
3462        struct ocfs2_path *left_path = NULL;
3463
3464        *ret_left_path = NULL;
3465
3466        /* This function shouldn't be called for non-trees. */
3467        BUG_ON(right_path->p_tree_depth == 0);
3468
3469        ret = ocfs2_find_cpos_for_left_leaf(ocfs2_metadata_cache_get_super(et->et_ci),
3470                                            right_path, &left_cpos);
3471        if (ret) {
3472                mlog_errno(ret);
3473                goto out;
3474        }
3475
3476        /* This function shouldn't be called for the leftmost leaf. */
3477        BUG_ON(left_cpos == 0);
3478
3479        left_path = ocfs2_new_path_from_path(right_path);
3480        if (!left_path) {
3481                ret = -ENOMEM;
3482                mlog_errno(ret);
3483                goto out;
3484        }
3485
3486        ret = ocfs2_find_path(et->et_ci, left_path, left_cpos);
3487        if (ret) {
3488                mlog_errno(ret);
3489                goto out;
3490        }
3491
3492        *ret_left_path = left_path;
3493out:
3494        if (ret)
3495                ocfs2_free_path(left_path);
3496        return ret;
3497}
3498
3499/*
3500 * Remove split_rec clusters from the record at index and merge them
3501 * onto the tail of the record "before" it.
3502 * For index > 0, the "before" means the extent rec at index - 1.
3503 *
3504 * For index == 0, the "before" means the last record of the previous
3505 * extent block. And there is also a situation that we may need to
3506 * remove the rightmost leaf extent block in the right_path and change
3507 * the right path to indicate the new rightmost path.
3508 */
3509static int ocfs2_merge_rec_left(struct ocfs2_path *right_path,
3510                                handle_t *handle,
3511                                struct ocfs2_extent_tree *et,
3512                                struct ocfs2_extent_rec *split_rec,
3513                                struct ocfs2_cached_dealloc_ctxt *dealloc,
3514                                int index)
3515{
3516        int ret, i, subtree_index = 0, has_empty_extent = 0;
3517        unsigned int split_clusters = le16_to_cpu(split_rec->e_leaf_clusters);
3518        struct ocfs2_extent_rec *left_rec;
3519        struct ocfs2_extent_rec *right_rec;
3520        struct ocfs2_extent_list *el = path_leaf_el(right_path);
3521        struct buffer_head *bh = path_leaf_bh(right_path);
3522        struct buffer_head *root_bh = NULL;
3523        struct ocfs2_path *left_path = NULL;
3524        struct ocfs2_extent_list *left_el;
3525
3526        BUG_ON(index < 0);
3527
3528        right_rec = &el->l_recs[index];
3529        if (index == 0) {
3530                /* we meet with a cross extent block merge. */
3531                ret = ocfs2_get_left_path(et, right_path, &left_path);
3532                if (ret) {
3533                        mlog_errno(ret);
3534                        return ret;
3535                }
3536
3537                left_el = path_leaf_el(left_path);
3538                BUG_ON(le16_to_cpu(left_el->l_next_free_rec) !=
3539                       le16_to_cpu(left_el->l_count));
3540
3541                left_rec = &left_el->l_recs[
3542                                le16_to_cpu(left_el->l_next_free_rec) - 1];
3543                BUG_ON(le32_to_cpu(left_rec->e_cpos) +
3544                       le16_to_cpu(left_rec->e_leaf_clusters) !=
3545                       le32_to_cpu(split_rec->e_cpos));
3546
3547                subtree_index = ocfs2_find_subtree_root(et, left_path,
3548                                                        right_path);
3549
3550                ret = ocfs2_extend_rotate_transaction(handle, subtree_index,
3551                                                      handle->h_buffer_credits,
3552                                                      left_path);
3553                if (ret) {
3554                        mlog_errno(ret);
3555                        goto out;
3556                }
3557
3558                root_bh = left_path->p_node[subtree_index].bh;
3559                BUG_ON(root_bh != right_path->p_node[subtree_index].bh);
3560
3561                ret = ocfs2_path_bh_journal_access(handle, et->et_ci, right_path,
3562                                                   subtree_index);
3563                if (ret) {
3564                        mlog_errno(ret);
3565                        goto out;
3566                }
3567
3568                for (i = subtree_index + 1;
3569                     i < path_num_items(right_path); i++) {
3570                        ret = ocfs2_path_bh_journal_access(handle, et->et_ci,
3571                                                           right_path, i);
3572                        if (ret) {
3573                                mlog_errno(ret);
3574                                goto out;
3575                        }
3576
3577                        ret = ocfs2_path_bh_journal_access(handle, et->et_ci,
3578                                                           left_path, i);
3579                        if (ret) {
3580                                mlog_errno(ret);
3581                                goto out;
3582                        }
3583                }
3584        } else {
3585                left_rec = &el->l_recs[index - 1];
3586                if (ocfs2_is_empty_extent(&el->l_recs[0]))
3587                        has_empty_extent = 1;
3588        }
3589
3590        ret = ocfs2_path_bh_journal_access(handle, et->et_ci, right_path,
3591                                           path_num_items(right_path) - 1);
3592        if (ret) {
3593                mlog_errno(ret);
3594                goto out;
3595        }
3596
3597        if (has_empty_extent && index == 1) {
3598                /*
3599                 * The easy case - we can just plop the record right in.
3600                 */
3601                *left_rec = *split_rec;
3602        } else
3603                le16_add_cpu(&left_rec->e_leaf_clusters, split_clusters);
3604
3605        le32_add_cpu(&right_rec->e_cpos, split_clusters);
3606        le64_add_cpu(&right_rec->e_blkno,
3607                     ocfs2_clusters_to_blocks(ocfs2_metadata_cache_get_super(et->et_ci),
3608                                              split_clusters));
3609        le16_add_cpu(&right_rec->e_leaf_clusters, -split_clusters);
3610
3611        ocfs2_cleanup_merge(el, index);
3612
3613        ocfs2_journal_dirty(handle, bh);
3614        if (left_path) {
3615                ocfs2_journal_dirty(handle, path_leaf_bh(left_path));
3616
3617                /*
3618                 * In the situation that the right_rec is empty and the extent
3619                 * block is empty also,  ocfs2_complete_edge_insert can't handle
3620                 * it and we need to delete the right extent block.
3621                 */
3622                if (le16_to_cpu(right_rec->e_leaf_clusters) == 0 &&
3623                    le16_to_cpu(el->l_next_free_rec) == 1) {
3624                        /* extend credit for ocfs2_remove_rightmost_path */
3625                        ret = ocfs2_extend_rotate_transaction(handle, 0,
3626                                        handle->h_buffer_credits,
3627                                        right_path);
3628                        if (ret) {
3629                                mlog_errno(ret);
3630                                goto out;
3631                        }
3632
3633                        ret = ocfs2_remove_rightmost_path(handle, et,
3634                                                          right_path,
3635                                                          dealloc);
3636                        if (ret) {
3637                                mlog_errno(ret);
3638                                goto out;
3639                        }
3640
3641                        /* Now the rightmost extent block has been deleted.
3642                         * So we use the new rightmost path.
3643                         */
3644                        ocfs2_mv_path(right_path, left_path);
3645                        left_path = NULL;
3646                } else
3647                        ocfs2_complete_edge_insert(handle, left_path,
3648                                                   right_path, subtree_index);
3649        }
3650out:
3651        ocfs2_free_path(left_path);
3652        return ret;
3653}
3654
3655static int ocfs2_try_to_merge_extent(handle_t *handle,
3656                                     struct ocfs2_extent_tree *et,
3657                                     struct ocfs2_path *path,
3658                                     int split_index,
3659                                     struct ocfs2_extent_rec *split_rec,
3660                                     struct ocfs2_cached_dealloc_ctxt *dealloc,
3661                                     struct ocfs2_merge_ctxt *ctxt)
3662{
3663        int ret = 0;
3664        struct ocfs2_extent_list *el = path_leaf_el(path);
3665        struct ocfs2_extent_rec *rec = &el->l_recs[split_index];
3666
3667        BUG_ON(ctxt->c_contig_type == CONTIG_NONE);
3668
3669        if (ctxt->c_split_covers_rec && ctxt->c_has_empty_extent) {
3670                /* extend credit for ocfs2_remove_rightmost_path */
3671                ret = ocfs2_extend_rotate_transaction(handle, 0,
3672                                handle->h_buffer_credits,
3673                                path);
3674                if (ret) {
3675                        mlog_errno(ret);
3676                        goto out;
3677                }
3678                /*
3679                 * The merge code will need to create an empty
3680                 * extent to take the place of the newly
3681                 * emptied slot. Remove any pre-existing empty
3682                 * extents - having more than one in a leaf is
3683                 * illegal.
3684                 */
3685                ret = ocfs2_rotate_tree_left(handle, et, path, dealloc);
3686                if (ret) {
3687                        mlog_errno(ret);
3688                        goto out;
3689                }
3690                split_index--;
3691                rec = &el->l_recs[split_index];
3692        }
3693
3694        if (ctxt->c_contig_type == CONTIG_LEFTRIGHT) {
3695                /*
3696                 * Left-right contig implies this.
3697                 */
3698                BUG_ON(!ctxt->c_split_covers_rec);
3699
3700                /*
3701                 * Since the leftright insert always covers the entire
3702                 * extent, this call will delete the insert record
3703                 * entirely, resulting in an empty extent record added to
3704                 * the extent block.
3705                 *
3706                 * Since the adding of an empty extent shifts
3707                 * everything back to the right, there's no need to
3708                 * update split_index here.
3709                 *
3710                 * When the split_index is zero, we need to merge it to the
3711                 * prevoius extent block. It is more efficient and easier
3712                 * if we do merge_right first and merge_left later.
3713                 */
3714                ret = ocfs2_merge_rec_right(path, handle, et, split_rec,
3715                                            split_index);
3716                if (ret) {
3717                        mlog_errno(ret);
3718                        goto out;
3719                }
3720
3721                /*
3722                 * We can only get this from logic error above.
3723                 */
3724                BUG_ON(!ocfs2_is_empty_extent(&el->l_recs[0]));
3725
3726                /* extend credit for ocfs2_remove_rightmost_path */
3727                ret = ocfs2_extend_rotate_transaction(handle, 0,
3728                                        handle->h_buffer_credits,
3729                                        path);
3730                if (ret) {
3731                        mlog_errno(ret);
3732                        goto out;
3733                }
3734
3735                /* The merge left us with an empty extent, remove it. */
3736                ret = ocfs2_rotate_tree_left(handle, et, path, dealloc);
3737                if (ret) {
3738                        mlog_errno(ret);
3739                        goto out;
3740                }
3741
3742                rec = &el->l_recs[split_index];
3743
3744                /*
3745                 * Note that we don't pass split_rec here on purpose -
3746                 * we've merged it into the rec already.
3747                 */
3748                ret = ocfs2_merge_rec_left(path, handle, et, rec,
3749                                           dealloc, split_index);
3750
3751                if (ret) {
3752                        mlog_errno(ret);
3753                        goto out;
3754                }
3755
3756                /* extend credit for ocfs2_remove_rightmost_path */
3757                ret = ocfs2_extend_rotate_transaction(handle, 0,
3758                                handle->h_buffer_credits,
3759                                path);
3760                if (ret) {
3761                        mlog_errno(ret);
3762                        goto out;
3763                }
3764
3765                ret = ocfs2_rotate_tree_left(handle, et, path, dealloc);
3766                /*
3767                 * Error from this last rotate is not critical, so
3768                 * print but don't bubble it up.
3769                 */
3770                if (ret)
3771                        mlog_errno(ret);
3772                ret = 0;
3773        } else {
3774                /*
3775                 * Merge a record to the left or right.
3776                 *
3777                 * 'contig_type' is relative to the existing record,
3778                 * so for example, if we're "right contig", it's to
3779                 * the record on the left (hence the left merge).
3780                 */
3781                if (ctxt->c_contig_type == CONTIG_RIGHT) {
3782                        ret = ocfs2_merge_rec_left(path, handle, et,
3783                                                   split_rec, dealloc,
3784                                                   split_index);
3785                        if (ret) {
3786                                mlog_errno(ret);
3787                                goto out;
3788                        }
3789                } else {
3790                        ret = ocfs2_merge_rec_right(path, handle,
3791                                                    et, split_rec,
3792                                                    split_index);
3793                        if (ret) {
3794                                mlog_errno(ret);
3795                                goto out;
3796                        }
3797                }
3798
3799                if (ctxt->c_split_covers_rec) {
3800                        /* extend credit for ocfs2_remove_rightmost_path */
3801                        ret = ocfs2_extend_rotate_transaction(handle, 0,
3802                                        handle->h_buffer_credits,
3803                                        path);
3804                        if (ret) {
3805                                mlog_errno(ret);
3806                                ret = 0;
3807                                goto out;
3808                        }
3809
3810                        /*
3811                         * The merge may have left an empty extent in
3812                         * our leaf. Try to rotate it away.
3813                         */
3814                        ret = ocfs2_rotate_tree_left(handle, et, path,
3815                                                     dealloc);
3816                        if (ret)
3817                                mlog_errno(ret);
3818                        ret = 0;
3819                }
3820        }
3821
3822out:
3823        return ret;
3824}
3825
3826static void ocfs2_subtract_from_rec(struct super_block *sb,
3827                                    enum ocfs2_split_type split,
3828                                    struct ocfs2_extent_rec *rec,
3829                                    struct ocfs2_extent_rec *split_rec)
3830{
3831        u64 len_blocks;
3832
3833        len_blocks = ocfs2_clusters_to_blocks(sb,
3834                                le16_to_cpu(split_rec->e_leaf_clusters));
3835
3836        if (split == SPLIT_LEFT) {
3837                /*
3838                 * Region is on the left edge of the existing
3839                 * record.
3840                 */
3841                le32_add_cpu(&rec->e_cpos,
3842                             le16_to_cpu(split_rec->e_leaf_clusters));
3843                le64_add_cpu(&rec->e_blkno, len_blocks);
3844                le16_add_cpu(&rec->e_leaf_clusters,
3845                             -le16_to_cpu(split_rec->e_leaf_clusters));
3846        } else {
3847                /*
3848                 * Region is on the right edge of the existing
3849                 * record.
3850                 */
3851                le16_add_cpu(&rec->e_leaf_clusters,
3852                             -le16_to_cpu(split_rec->e_leaf_clusters));
3853        }
3854}
3855
3856/*
3857 * Do the final bits of extent record insertion at the target leaf
3858 * list. If this leaf is part of an allocation tree, it is assumed
3859 * that the tree above has been prepared.
3860 */
3861static void ocfs2_insert_at_leaf(struct ocfs2_extent_tree *et,
3862                                 struct ocfs2_extent_rec *insert_rec,
3863                                 struct ocfs2_extent_list *el,
3864                                 struct ocfs2_insert_type *insert)
3865{
3866        int i = insert->ins_contig_index;
3867        unsigned int range;
3868        struct ocfs2_extent_rec *rec;
3869
3870        BUG_ON(le16_to_cpu(el->l_tree_depth) != 0);
3871
3872        if (insert->ins_split != SPLIT_NONE) {
3873                i = ocfs2_search_extent_list(el, le32_to_cpu(insert_rec->e_cpos));
3874                BUG_ON(i == -1);
3875                rec = &el->l_recs[i];
3876                ocfs2_subtract_from_rec(ocfs2_metadata_cache_get_super(et->et_ci),
3877                                        insert->ins_split, rec,
3878                                        insert_rec);
3879                goto rotate;
3880        }
3881
3882        /*
3883         * Contiguous insert - either left or right.
3884         */
3885        if (insert->ins_contig != CONTIG_NONE) {
3886                rec = &el->l_recs[i];
3887                if (insert->ins_contig == CONTIG_LEFT) {
3888                        rec->e_blkno = insert_rec->e_blkno;
3889                        rec->e_cpos = insert_rec->e_cpos;
3890                }
3891                le16_add_cpu(&rec->e_leaf_clusters,
3892                             le16_to_cpu(insert_rec->e_leaf_clusters));
3893                return;
3894        }
3895
3896        /*
3897         * Handle insert into an empty leaf.
3898         */
3899        if (le16_to_cpu(el->l_next_free_rec) == 0 ||
3900            ((le16_to_cpu(el->l_next_free_rec) == 1) &&
3901             ocfs2_is_empty_extent(&el->l_recs[0]))) {
3902                el->l_recs[0] = *insert_rec;
3903                el->l_next_free_rec = cpu_to_le16(1);
3904                return;
3905        }
3906
3907        /*
3908         * Appending insert.
3909         */
3910        if (insert->ins_appending == APPEND_TAIL) {
3911                i = le16_to_cpu(el->l_next_free_rec) - 1;
3912                rec = &el->l_recs[i];
3913                range = le32_to_cpu(rec->e_cpos)
3914                        + le16_to_cpu(rec->e_leaf_clusters);
3915                BUG_ON(le32_to_cpu(insert_rec->e_cpos) < range);
3916
3917                mlog_bug_on_msg(le16_to_cpu(el->l_next_free_rec) >=
3918                                le16_to_cpu(el->l_count),
3919                                "owner %llu, depth %u, count %u, next free %u, "
3920                                "rec.cpos %u, rec.clusters %u, "
3921                                "insert.cpos %u, insert.clusters %u\n",
3922                                ocfs2_metadata_cache_owner(et->et_ci),
3923                                le16_to_cpu(el->l_tree_depth),
3924                                le16_to_cpu(el->l_count),
3925                                le16_to_cpu(el->l_next_free_rec),
3926                                le32_to_cpu(el->l_recs[i].e_cpos),
3927                                le16_to_cpu(el->l_recs[i].e_leaf_clusters),
3928                                le32_to_cpu(insert_rec->e_cpos),
3929                                le16_to_cpu(insert_rec->e_leaf_clusters));
3930                i++;
3931                el->l_recs[i] = *insert_rec;
3932                le16_add_cpu(&el->l_next_free_rec, 1);
3933                return;
3934        }
3935
3936rotate:
3937        /*
3938         * Ok, we have to rotate.
3939         *
3940         * At this point, it is safe to assume that inserting into an
3941         * empty leaf and appending to a leaf have both been handled
3942         * above.
3943         *
3944         * This leaf needs to have space, either by the empty 1st
3945         * extent record, or by virtue of an l_next_rec < l_count.
3946         */
3947        ocfs2_rotate_leaf(el, insert_rec);
3948}
3949
3950static void ocfs2_adjust_rightmost_records(handle_t *handle,
3951                                           struct ocfs2_extent_tree *et,
3952                                           struct ocfs2_path *path,
3953                                           struct ocfs2_extent_rec *insert_rec)
3954{
3955        int i, next_free;
3956        struct buffer_head *bh;
3957        struct ocfs2_extent_list *el;
3958        struct ocfs2_extent_rec *rec;
3959
3960        /*
3961         * Update everything except the leaf block.
3962         */
3963        for (i = 0; i < path->p_tree_depth; i++) {
3964                bh = path->p_node[i].bh;
3965                el = path->p_node[i].el;
3966
3967                next_free = le16_to_cpu(el->l_next_free_rec);
3968                if (next_free == 0) {
3969                        ocfs2_error(ocfs2_metadata_cache_get_super(et->et_ci),
3970                                    "Owner %llu has a bad extent list\n",
3971                                    (unsigned long long)ocfs2_metadata_cache_owner(et->et_ci));
3972                        return;
3973                }
3974
3975                rec = &el->l_recs[next_free - 1];
3976
3977                rec->e_int_clusters = insert_rec->e_cpos;
3978                le32_add_cpu(&rec->e_int_clusters,
3979                             le16_to_cpu(insert_rec->e_leaf_clusters));
3980                le32_add_cpu(&rec->e_int_clusters,
3981                             -le32_to_cpu(rec->e_cpos));
3982
3983                ocfs2_journal_dirty(handle, bh);
3984        }
3985}
3986
3987static int ocfs2_append_rec_to_path(handle_t *handle,
3988                                    struct ocfs2_extent_tree *et,
3989                                    struct ocfs2_extent_rec *insert_rec,
3990                                    struct ocfs2_path *right_path,
3991                                    struct ocfs2_path **ret_left_path)
3992{
3993        int ret, next_free;
3994        struct ocfs2_extent_list *el;
3995        struct ocfs2_path *left_path = NULL;
3996
3997        *ret_left_path = NULL;
3998
3999        /*
4000         * This shouldn't happen for non-trees. The extent rec cluster
4001         * count manipulation below only works for interior nodes.
4002         */
4003        BUG_ON(right_path->p_tree_depth == 0);
4004
4005        /*
4006         * If our appending insert is at the leftmost edge of a leaf,
4007         * then we might need to update the rightmost records of the
4008         * neighboring path.
4009         */
4010        el = path_leaf_el(right_path);
4011        next_free = le16_to_cpu(el->l_next_free_rec);
4012        if (next_free == 0 ||
4013            (next_free == 1 && ocfs2_is_empty_extent(&el->l_recs[0]))) {
4014                u32 left_cpos;
4015
4016                ret = ocfs2_find_cpos_for_left_leaf(ocfs2_metadata_cache_get_super(et->et_ci),
4017                                                    right_path, &left_cpos);
4018                if (ret) {
4019                        mlog_errno(ret);
4020                        goto out;
4021                }
4022
4023                trace_ocfs2_append_rec_to_path(
4024                        (unsigned long long)
4025                        ocfs2_metadata_cache_owner(et->et_ci),
4026                        le32_to_cpu(insert_rec->e_cpos),
4027                        left_cpos);
4028
4029                /*
4030                 * No need to worry if the append is already in the
4031                 * leftmost leaf.
4032                 */
4033                if (left_cpos) {
4034                        left_path = ocfs2_new_path_from_path(right_path);
4035                        if (!left_path) {
4036                                ret = -ENOMEM;
4037                                mlog_errno(ret);
4038                                goto out;
4039                        }
4040
4041                        ret = ocfs2_find_path(et->et_ci, left_path,
4042                                              left_cpos);
4043                        if (ret) {
4044                                mlog_errno(ret);
4045                                goto out;
4046                        }
4047
4048                        /*
4049                         * ocfs2_insert_path() will pass the left_path to the
4050                         * journal for us.
4051                         */
4052                }
4053        }
4054
4055        ret = ocfs2_journal_access_path(et->et_ci, handle, right_path);
4056        if (ret) {
4057                mlog_errno(ret);
4058                goto out;
4059        }
4060
4061        ocfs2_adjust_rightmost_records(handle, et, right_path, insert_rec);
4062
4063        *ret_left_path = left_path;
4064        ret = 0;
4065out:
4066        if (ret != 0)
4067                ocfs2_free_path(left_path);
4068
4069        return ret;
4070}
4071
4072static void ocfs2_split_record(struct ocfs2_extent_tree *et,
4073                               struct ocfs2_path *left_path,
4074                               struct ocfs2_path *right_path,
4075                               struct ocfs2_extent_rec *split_rec,
4076                               enum ocfs2_split_type split)
4077{
4078        int index;
4079        u32 cpos = le32_to_cpu(split_rec->e_cpos);
4080        struct ocfs2_extent_list *left_el = NULL, *right_el, *insert_el, *el;
4081        struct ocfs2_extent_rec *rec, *tmprec;
4082
4083        right_el = path_leaf_el(right_path);
4084        if (left_path)
4085                left_el = path_leaf_el(left_path);
4086
4087        el = right_el;
4088        insert_el = right_el;
4089        index = ocfs2_search_extent_list(el, cpos);
4090        if (index != -1) {
4091                if (index == 0 && left_path) {
4092                        BUG_ON(ocfs2_is_empty_extent(&el->l_recs[0]));
4093
4094                        /*
4095                         * This typically means that the record
4096                         * started in the left path but moved to the
4097                         * right as a result of rotation. We either
4098                         * move the existing record to the left, or we
4099                         * do the later insert there.
4100                         *
4101                         * In this case, the left path should always
4102                         * exist as the rotate code will have passed
4103                         * it back for a post-insert update.
4104                         */
4105
4106                        if (split == SPLIT_LEFT) {
4107                                /*
4108                                 * It's a left split. Since we know
4109                                 * that the rotate code gave us an
4110                                 * empty extent in the left path, we
4111                                 * can just do the insert there.
4112                                 */
4113                                insert_el = left_el;
4114                        } else {
4115                                /*
4116                                 * Right split - we have to move the
4117                                 * existing record over to the left
4118                                 * leaf. The insert will be into the
4119                                 * newly created empty extent in the
4120                                 * right leaf.
4121                                 */
4122                                tmprec = &right_el->l_recs[index];
4123                                ocfs2_rotate_leaf(left_el, tmprec);
4124                                el = left_el;
4125
4126                                memset(tmprec, 0, sizeof(*tmprec));
4127                                index = ocfs2_search_extent_list(left_el, cpos);
4128                                BUG_ON(index == -1);
4129                        }
4130                }
4131        } else {
4132                BUG_ON(!left_path);
4133                BUG_ON(!ocfs2_is_empty_extent(&left_el->l_recs[0]));
4134                /*
4135                 * Left path is easy - we can just allow the insert to
4136                 * happen.
4137                 */
4138                el = left_el;
4139                insert_el = left_el;
4140                index = ocfs2_search_extent_list(el, cpos);
4141                BUG_ON(index == -1);
4142        }
4143
4144        rec = &el->l_recs[index];
4145        ocfs2_subtract_from_rec(ocfs2_metadata_cache_get_super(et->et_ci),
4146                                split, rec, split_rec);
4147        ocfs2_rotate_leaf(insert_el, split_rec);
4148}
4149
4150/*
4151 * This function only does inserts on an allocation b-tree. For tree
4152 * depth = 0, ocfs2_insert_at_leaf() is called directly.
4153 *
4154 * right_path is the path we want to do the actual insert
4155 * in. left_path should only be passed in if we need to update that
4156 * portion of the tree after an edge insert.
4157 */
4158static int ocfs2_insert_path(handle_t *handle,
4159                             struct ocfs2_extent_tree *et,
4160                             struct ocfs2_path *left_path,
4161                             struct ocfs2_path *right_path,
4162                             struct ocfs2_extent_rec *insert_rec,
4163                             struct ocfs2_insert_type *insert)
4164{
4165        int ret, subtree_index;
4166        struct buffer_head *leaf_bh = path_leaf_bh(right_path);
4167
4168        if (left_path) {
4169                /*
4170                 * There's a chance that left_path got passed back to
4171                 * us without being accounted for in the
4172                 * journal. Extend our transaction here to be sure we
4173                 * can change those blocks.
4174                 */
4175                ret = ocfs2_extend_trans(handle, left_path->p_tree_depth);
4176                if (ret < 0) {
4177                        mlog_errno(ret);
4178                        goto out;
4179                }
4180
4181                ret = ocfs2_journal_access_path(et->et_ci, handle, left_path);
4182                if (ret < 0) {
4183                        mlog_errno(ret);
4184                        goto out;
4185                }
4186        }
4187
4188        /*
4189         * Pass both paths to the journal. The majority of inserts
4190         * will be touching all components anyway.
4191         */
4192        ret = ocfs2_journal_access_path(et->et_ci, handle, right_path);
4193        if (ret < 0) {
4194                mlog_errno(ret);
4195                goto out;
4196        }
4197
4198        if (insert->ins_split != SPLIT_NONE) {
4199                /*
4200                 * We could call ocfs2_insert_at_leaf() for some types
4201                 * of splits, but it's easier to just let one separate
4202                 * function sort it all out.
4203                 */
4204                ocfs2_split_record(et, left_path, right_path,
4205                                   insert_rec, insert->ins_split);
4206
4207                /*
4208                 * Split might have modified either leaf and we don't
4209                 * have a guarantee that the later edge insert will
4210                 * dirty this for us.
4211                 */
4212                if (left_path)
4213                        ocfs2_journal_dirty(handle,
4214                                            path_leaf_bh(left_path));
4215        } else
4216                ocfs2_insert_at_leaf(et, insert_rec, path_leaf_el(right_path),
4217                                     insert);
4218
4219        ocfs2_journal_dirty(handle, leaf_bh);
4220
4221        if (left_path) {
4222                /*
4223                 * The rotate code has indicated that we need to fix
4224                 * up portions of the tree after the insert.
4225                 *
4226                 * XXX: Should we extend the transaction here?
4227                 */
4228                subtree_index = ocfs2_find_subtree_root(et, left_path,
4229                                                        right_path);
4230                ocfs2_complete_edge_insert(handle, left_path, right_path,
4231                                           subtree_index);
4232        }
4233
4234        ret = 0;
4235out:
4236        return ret;
4237}
4238
4239static int ocfs2_do_insert_extent(handle_t *handle,
4240                                  struct ocfs2_extent_tree *et,
4241                                  struct ocfs2_extent_rec *insert_rec,
4242                                  struct ocfs2_insert_type *type)
4243{
4244        int ret, rotate = 0;
4245        u32 cpos;
4246        struct ocfs2_path *right_path = NULL;
4247        struct ocfs2_path *left_path = NULL;
4248        struct ocfs2_extent_list *el;
4249
4250        el = et->et_root_el;
4251
4252        ret = ocfs2_et_root_journal_access(handle, et,
4253                                           OCFS2_JOURNAL_ACCESS_WRITE);
4254        if (ret) {
4255                mlog_errno(ret);
4256                goto out;
4257        }
4258
4259        if (le16_to_cpu(el->l_tree_depth) == 0) {
4260                ocfs2_insert_at_leaf(et, insert_rec, el, type);
4261                goto out_update_clusters;
4262        }
4263
4264        right_path = ocfs2_new_path_from_et(et);
4265        if (!right_path) {
4266                ret = -ENOMEM;
4267                mlog_errno(ret);
4268                goto out;
4269        }
4270
4271        /*
4272         * Determine the path to start with. Rotations need the
4273         * rightmost path, everything else can go directly to the
4274         * target leaf.
4275         */
4276        cpos = le32_to_cpu(insert_rec->e_cpos);
4277        if (type->ins_appending == APPEND_NONE &&
4278            type->ins_contig == CONTIG_NONE) {
4279                rotate = 1;
4280                cpos = UINT_MAX;
4281        }
4282
4283        ret = ocfs2_find_path(et->et_ci, right_path, cpos);
4284        if (ret) {
4285                mlog_errno(ret);
4286                goto out;
4287        }
4288
4289        /*
4290         * Rotations and appends need special treatment - they modify
4291         * parts of the tree's above them.
4292         *
4293         * Both might pass back a path immediate to the left of the
4294         * one being inserted to. This will be cause
4295         * ocfs2_insert_path() to modify the rightmost records of
4296         * left_path to account for an edge insert.
4297         *
4298         * XXX: When modifying this code, keep in mind that an insert
4299         * can wind up skipping both of these two special cases...
4300         */
4301        if (rotate) {
4302                ret = ocfs2_rotate_tree_right(handle, et, type->ins_split,
4303                                              le32_to_cpu(insert_rec->e_cpos),
4304                                              right_path, &left_path);
4305                if (ret) {
4306                        mlog_errno(ret);
4307                        goto out;
4308                }
4309
4310                /*
4311                 * ocfs2_rotate_tree_right() might have extended the
4312                 * transaction without re-journaling our tree root.
4313                 */
4314                ret = ocfs2_et_root_journal_access(handle, et,
4315                                                   OCFS2_JOURNAL_ACCESS_WRITE);
4316                if (ret) {
4317                        mlog_errno(ret);
4318                        goto out;
4319                }
4320        } else if (type->ins_appending == APPEND_TAIL
4321                   && type->ins_contig != CONTIG_LEFT) {
4322                ret = ocfs2_append_rec_to_path(handle, et, insert_rec,
4323                                               right_path, &left_path);
4324                if (ret) {
4325                        mlog_errno(ret);
4326                        goto out;
4327                }
4328        }
4329
4330        ret = ocfs2_insert_path(handle, et, left_path, right_path,
4331                                insert_rec, type);
4332        if (ret) {
4333                mlog_errno(ret);
4334                goto out;
4335        }
4336
4337out_update_clusters:
4338        if (type->ins_split == SPLIT_NONE)
4339                ocfs2_et_update_clusters(et,
4340                                         le16_to_cpu(insert_rec->e_leaf_clusters));
4341
4342        ocfs2_journal_dirty(handle, et->et_root_bh);
4343
4344out:
4345        ocfs2_free_path(left_path);
4346        ocfs2_free_path(right_path);
4347
4348        return ret;
4349}
4350
4351static int ocfs2_figure_merge_contig_type(struct ocfs2_extent_tree *et,
4352                               struct ocfs2_path *path,
4353                               struct ocfs2_extent_list *el, int index,
4354                               struct ocfs2_extent_rec *split_rec,
4355                               struct ocfs2_merge_ctxt *ctxt)
4356{
4357        int status = 0;
4358        enum ocfs2_contig_type ret = CONTIG_NONE;
4359        u32 left_cpos, right_cpos;
4360        struct ocfs2_extent_rec *rec = NULL;
4361        struct ocfs2_extent_list *new_el;
4362        struct ocfs2_path *left_path = NULL, *right_path = NULL;
4363        struct buffer_head *bh;
4364        struct ocfs2_extent_block *eb;
4365        struct super_block *sb = ocfs2_metadata_cache_get_super(et->et_ci);
4366
4367        if (index > 0) {
4368                rec = &el->l_recs[index - 1];
4369        } else if (path->p_tree_depth > 0) {
4370                status = ocfs2_find_cpos_for_left_leaf(sb, path, &left_cpos);
4371                if (status)
4372                        goto exit;
4373
4374                if (left_cpos != 0) {
4375                        left_path = ocfs2_new_path_from_path(path);
4376                        if (!left_path) {
4377                                status = -ENOMEM;
4378                                mlog_errno(status);
4379                                goto exit;
4380                        }
4381
4382                        status = ocfs2_find_path(et->et_ci, left_path,
4383                                                 left_cpos);
4384                        if (status)
4385                                goto free_left_path;
4386
4387                        new_el = path_leaf_el(left_path);
4388
4389                        if (le16_to_cpu(new_el->l_next_free_rec) !=
4390                            le16_to_cpu(new_el->l_count)) {
4391                                bh = path_leaf_bh(left_path);
4392                                eb = (struct ocfs2_extent_block *)bh->b_data;
4393                                status = ocfs2_error(sb,
4394                                                "Extent block #%llu has an invalid l_next_free_rec of %d.  It should have matched the l_count of %d\n",
4395                                                (unsigned long long)le64_to_cpu(eb->h_blkno),
4396                                                le16_to_cpu(new_el->l_next_free_rec),
4397                                                le16_to_cpu(new_el->l_count));
4398                                goto free_left_path;
4399                        }
4400                        rec = &new_el->l_recs[
4401                                le16_to_cpu(new_el->l_next_free_rec) - 1];
4402                }
4403        }
4404
4405        /*
4406         * We're careful to check for an empty extent record here -
4407         * the merge code will know what to do if it sees one.
4408         */
4409        if (rec) {
4410                if (index == 1 && ocfs2_is_empty_extent(rec)) {
4411                        if (split_rec->e_cpos == el->l_recs[index].e_cpos)
4412                                ret = CONTIG_RIGHT;
4413                } else {
4414                        ret = ocfs2_et_extent_contig(et, rec, split_rec);
4415                }
4416        }
4417
4418        rec = NULL;
4419        if (index < (le16_to_cpu(el->l_next_free_rec) - 1))
4420                rec = &el->l_recs[index + 1];
4421        else if (le16_to_cpu(el->l_next_free_rec) == le16_to_cpu(el->l_count) &&
4422                 path->p_tree_depth > 0) {
4423                status = ocfs2_find_cpos_for_right_leaf(sb, path, &right_cpos);
4424                if (status)
4425                        goto free_left_path;
4426
4427                if (right_cpos == 0)
4428                        goto free_left_path;
4429
4430                right_path = ocfs2_new_path_from_path(path);
4431                if (!right_path) {
4432                        status = -ENOMEM;
4433                        mlog_errno(status);
4434                        goto free_left_path;
4435                }
4436
4437                status = ocfs2_find_path(et->et_ci, right_path, right_cpos);
4438                if (status)
4439                        goto free_right_path;
4440
4441                new_el = path_leaf_el(right_path);
4442                rec = &new_el->l_recs[0];
4443                if (ocfs2_is_empty_extent(rec)) {
4444                        if (le16_to_cpu(new_el->l_next_free_rec) <= 1) {
4445                                bh = path_leaf_bh(right_path);
4446                                eb = (struct ocfs2_extent_block *)bh->b_data;
4447                                status = ocfs2_error(sb,
4448                                                "Extent block #%llu has an invalid l_next_free_rec of %d\n",
4449                                                (unsigned long long)le64_to_cpu(eb->h_blkno),
4450                                                le16_to_cpu(new_el->l_next_free_rec));
4451                                goto free_right_path;
4452                        }
4453                        rec = &new_el->l_recs[1];
4454                }
4455        }
4456
4457        if (rec) {
4458                enum ocfs2_contig_type contig_type;
4459
4460                contig_type = ocfs2_et_extent_contig(et, rec, split_rec);
4461
4462                if (contig_type == CONTIG_LEFT && ret == CONTIG_RIGHT)
4463                        ret = CONTIG_LEFTRIGHT;
4464                else if (ret == CONTIG_NONE)
4465                        ret = contig_type;
4466        }
4467
4468free_right_path:
4469        ocfs2_free_path(right_path);
4470free_left_path:
4471        ocfs2_free_path(left_path);
4472exit:
4473        if (status == 0)
4474                ctxt->c_contig_type = ret;
4475
4476        return status;
4477}
4478
4479static void ocfs2_figure_contig_type(struct ocfs2_extent_tree *et,
4480                                     struct ocfs2_insert_type *insert,
4481                                     struct ocfs2_extent_list *el,
4482                                     struct ocfs2_extent_rec *insert_rec)
4483{
4484        int i;
4485        enum ocfs2_contig_type contig_type = CONTIG_NONE;
4486
4487        BUG_ON(le16_to_cpu(el->l_tree_depth) != 0);
4488
4489        for(i = 0; i < le16_to_cpu(el->l_next_free_rec); i++) {
4490                contig_type = ocfs2_et_extent_contig(et, &el->l_recs[i],
4491                                                     insert_rec);
4492                if (contig_type != CONTIG_NONE) {
4493                        insert->ins_contig_index = i;
4494                        break;
4495                }
4496        }
4497        insert->ins_contig = contig_type;
4498
4499        if (insert->ins_contig != CONTIG_NONE) {
4500                struct ocfs2_extent_rec *rec =
4501                                &el->l_recs[insert->ins_contig_index];
4502                unsigned int len = le16_to_cpu(rec->e_leaf_clusters) +
4503                                   le16_to_cpu(insert_rec->e_leaf_clusters);
4504
4505                /*
4506                 * Caller might want us to limit the size of extents, don't
4507                 * calculate contiguousness if we might exceed that limit.
4508                 */
4509                if (et->et_max_leaf_clusters &&
4510                    (len > et->et_max_leaf_clusters))
4511                        insert->ins_contig = CONTIG_NONE;
4512        }
4513}
4514
4515/*
4516 * This should only be called against the righmost leaf extent list.
4517 *
4518 * ocfs2_figure_appending_type() will figure out whether we'll have to
4519 * insert at the tail of the rightmost leaf.
4520 *
4521 * This should also work against the root extent list for tree's with 0
4522 * depth. If we consider the root extent list to be the rightmost leaf node
4523 * then the logic here makes sense.
4524 */
4525static void ocfs2_figure_appending_type(struct ocfs2_insert_type *insert,
4526                                        struct ocfs2_extent_list *el,
4527                                        struct ocfs2_extent_rec *insert_rec)
4528{
4529        int i;
4530        u32 cpos = le32_to_cpu(insert_rec->e_cpos);
4531        struct ocfs2_extent_rec *rec;
4532
4533        insert->ins_appending = APPEND_NONE;
4534
4535        BUG_ON(le16_to_cpu(el->l_tree_depth) != 0);
4536
4537        if (!el->l_next_free_rec)
4538                goto set_tail_append;
4539
4540        if (ocfs2_is_empty_extent(&el->l_recs[0])) {
4541                /* Were all records empty? */
4542                if (le16_to_cpu(el->l_next_free_rec) == 1)
4543                        goto set_tail_append;
4544        }
4545
4546        i = le16_to_cpu(el->l_next_free_rec) - 1;
4547        rec = &el->l_recs[i];
4548
4549        if (cpos >=
4550            (le32_to_cpu(rec->e_cpos) + le16_to_cpu(rec->e_leaf_clusters)))
4551                goto set_tail_append;
4552
4553        return;
4554
4555set_tail_append:
4556        insert->ins_appending = APPEND_TAIL;
4557}
4558
4559/*
4560 * Helper function called at the beginning of an insert.
4561 *
4562 * This computes a few things that are commonly used in the process of
4563 * inserting into the btree:
4564 *   - Whether the new extent is contiguous with an existing one.
4565 *   - The current tree depth.
4566 *   - Whether the insert is an appending one.
4567 *   - The total # of free records in the tree.
4568 *
4569 * All of the information is stored on the ocfs2_insert_type
4570 * structure.
4571 */
4572static int ocfs2_figure_insert_type(struct ocfs2_extent_tree *et,
4573                                    struct buffer_head **last_eb_bh,
4574                                    struct ocfs2_extent_rec *insert_rec,
4575                                    int *free_records,
4576                                    struct ocfs2_insert_type *insert)
4577{
4578        int ret;
4579        struct ocfs2_extent_block *eb;
4580        struct ocfs2_extent_list *el;
4581        struct ocfs2_path *path = NULL;
4582        struct buffer_head *bh = NULL;
4583
4584        insert->ins_split = SPLIT_NONE;
4585
4586        el = et->et_root_el;
4587        insert->ins_tree_depth = le16_to_cpu(el->l_tree_depth);
4588
4589        if (el->l_tree_depth) {
4590                /*
4591                 * If we have tree depth, we read in the
4592                 * rightmost extent block ahead of time as
4593                 * ocfs2_figure_insert_type() and ocfs2_add_branch()
4594                 * may want it later.
4595                 */
4596                ret = ocfs2_read_extent_block(et->et_ci,
4597                                              ocfs2_et_get_last_eb_blk(et),
4598                                              &bh);
4599                if (ret) {
4600                        mlog_errno(ret);
4601                        goto out;
4602                }
4603                eb = (struct ocfs2_extent_block *) bh->b_data;
4604                el = &eb->h_list;
4605        }
4606
4607        /*
4608         * Unless we have a contiguous insert, we'll need to know if
4609         * there is room left in our allocation tree for another
4610         * extent record.
4611         *
4612         * XXX: This test is simplistic, we can search for empty
4613         * extent records too.
4614         */
4615        *free_records = le16_to_cpu(el->l_count) -
4616                le16_to_cpu(el->l_next_free_rec);
4617
4618        if (!insert->ins_tree_depth) {
4619                ocfs2_figure_contig_type(et, insert, el, insert_rec);
4620                ocfs2_figure_appending_type(insert, el, insert_rec);
4621                return 0;
4622        }
4623
4624        path = ocfs2_new_path_from_et(et);
4625        if (!path) {
4626                ret = -ENOMEM;
4627                mlog_errno(ret);
4628                goto out;
4629        }
4630
4631        /*
4632         * In the case that we're inserting past what the tree
4633         * currently accounts for, ocfs2_find_path() will return for
4634         * us the rightmost tree path. This is accounted for below in
4635         * the appending code.
4636         */
4637        ret = ocfs2_find_path(et->et_ci, path, le32_to_cpu(insert_rec->e_cpos));
4638        if (ret) {
4639                mlog_errno(ret);
4640                goto out;
4641        }
4642
4643        el = path_leaf_el(path);
4644
4645        /*
4646         * Now that we have the path, there's two things we want to determine:
4647         * 1) Contiguousness (also set contig_index if this is so)
4648         *
4649         * 2) Are we doing an append? We can trivially break this up
4650         *     into two types of appends: simple record append, or a
4651         *     rotate inside the tail leaf.
4652         */
4653        ocfs2_figure_contig_type(et, insert, el, insert_rec);
4654
4655        /*
4656         * The insert code isn't quite ready to deal with all cases of
4657         * left contiguousness. Specifically, if it's an insert into
4658         * the 1st record in a leaf, it will require the adjustment of
4659         * cluster count on the last record of the path directly to it's
4660         * left. For now, just catch that case and fool the layers
4661         * above us. This works just fine for tree_depth == 0, which
4662         * is why we allow that above.
4663         */
4664        if (insert->ins_contig == CONTIG_LEFT &&
4665            insert->ins_contig_index == 0)
4666                insert->ins_contig = CONTIG_NONE;
4667
4668        /*
4669         * Ok, so we can simply compare against last_eb to figure out
4670         * whether the path doesn't exist. This will only happen in
4671         * the case that we're doing a tail append, so maybe we can
4672         * take advantage of that information somehow.
4673         */
4674        if (ocfs2_et_get_last_eb_blk(et) ==
4675            path_leaf_bh(path)->b_blocknr) {
4676                /*
4677                 * Ok, ocfs2_find_path() returned us the rightmost
4678                 * tree path. This might be an appending insert. There are
4679                 * two cases:
4680                 *    1) We're doing a true append at the tail:
4681                 *      -This might even be off the end of the leaf
4682                 *    2) We're "appending" by rotating in the tail
4683                 */
4684                ocfs2_figure_appending_type(insert, el, insert_rec);
4685        }
4686
4687out:
4688        ocfs2_free_path(path);
4689
4690        if (ret == 0)
4691                *last_eb_bh = bh;
4692        else
4693                brelse(bh);
4694        return ret;
4695}
4696
4697/*
4698 * Insert an extent into a btree.
4699 *
4700 * The caller needs to update the owning btree's cluster count.
4701 */
4702int ocfs2_insert_extent(handle_t *handle,
4703                        struct ocfs2_extent_tree *et,
4704                        u32 cpos,
4705                        u64 start_blk,
4706                        u32 new_clusters,
4707                        u8 flags,
4708                        struct ocfs2_alloc_context *meta_ac)
4709{
4710        int status;
4711        int uninitialized_var(free_records);
4712        struct buffer_head *last_eb_bh = NULL;
4713        struct ocfs2_insert_type insert = {0, };
4714        struct ocfs2_extent_rec rec;
4715
4716        trace_ocfs2_insert_extent_start(
4717                (unsigned long long)ocfs2_metadata_cache_owner(et->et_ci),
4718                cpos, new_clusters);
4719
4720        memset(&rec, 0, sizeof(rec));
4721        rec.e_cpos = cpu_to_le32(cpos);
4722        rec.e_blkno = cpu_to_le64(start_blk);
4723        rec.e_leaf_clusters = cpu_to_le16(new_clusters);
4724        rec.e_flags = flags;
4725        status = ocfs2_et_insert_check(et, &rec);
4726        if (status) {
4727                mlog_errno(status);
4728                goto bail;
4729        }
4730
4731        status = ocfs2_figure_insert_type(et, &last_eb_bh, &rec,
4732                                          &free_records, &insert);
4733        if (status < 0) {
4734                mlog_errno(status);
4735                goto bail;
4736        }
4737
4738        trace_ocfs2_insert_extent(insert.ins_appending, insert.ins_contig,
4739                                  insert.ins_contig_index, free_records,
4740                                  insert.ins_tree_depth);
4741
4742        if (insert.ins_contig == CONTIG_NONE && free_records == 0) {
4743                status = ocfs2_grow_tree(handle, et,
4744                                         &insert.ins_tree_depth, &last_eb_bh,
4745                                         meta_ac);
4746                if (status) {
4747                        mlog_errno(status);
4748                        goto bail;
4749                }
4750        }
4751
4752        /* Finally, we can add clusters. This might rotate the tree for us. */
4753        status = ocfs2_do_insert_extent(handle, et, &rec, &insert);
4754        if (status < 0)
4755                mlog_errno(status);
4756        else
4757                ocfs2_et_extent_map_insert(et, &rec);
4758
4759bail:
4760        brelse(last_eb_bh);
4761
4762        return status;
4763}
4764
4765/*
4766 * Allcate and add clusters into the extent b-tree.
4767 * The new clusters(clusters_to_add) will be inserted at logical_offset.
4768 * The extent b-tree's root is specified by et, and
4769 * it is not limited to the file storage. Any extent tree can use this
4770 * function if it implements the proper ocfs2_extent_tree.
4771 */
4772int ocfs2_add_clusters_in_btree(handle_t *handle,
4773                                struct ocfs2_extent_tree *et,
4774                                u32 *logical_offset,
4775                                u32 clusters_to_add,
4776                                int mark_unwritten,
4777                                struct ocfs2_alloc_context *data_ac,
4778                                struct ocfs2_alloc_context *meta_ac,
4779                                enum ocfs2_alloc_restarted *reason_ret)
4780{
4781        int status = 0, err = 0;
4782        int need_free = 0;
4783        int free_extents;
4784        enum ocfs2_alloc_restarted reason = RESTART_NONE;
4785        u32 bit_off, num_bits;
4786        u64 block;
4787        u8 flags = 0;
4788        struct ocfs2_super *osb =
4789                OCFS2_SB(ocfs2_metadata_cache_get_super(et->et_ci));
4790
4791        BUG_ON(!clusters_to_add);
4792
4793        if (mark_unwritten)
4794                flags = OCFS2_EXT_UNWRITTEN;
4795
4796        free_extents = ocfs2_num_free_extents(et);
4797        if (free_extents < 0) {
4798                status = free_extents;
4799                mlog_errno(status);
4800                goto leave;
4801        }
4802
4803        /* there are two cases which could cause us to EAGAIN in the
4804         * we-need-more-metadata case:
4805         * 1) we haven't reserved *any*
4806         * 2) we are so fragmented, we've needed to add metadata too
4807         *    many times. */
4808        if (!free_extents && !meta_ac) {
4809                err = -1;
4810                status = -EAGAIN;
4811                reason = RESTART_META;
4812                goto leave;
4813        } else if ((!free_extents)
4814                   && (ocfs2_alloc_context_bits_left(meta_ac)
4815                       < ocfs2_extend_meta_needed(et->et_root_el))) {
4816                err = -2;
4817                status = -EAGAIN;
4818                reason = RESTART_META;
4819                goto leave;
4820        }
4821
4822        status = __ocfs2_claim_clusters(handle, data_ac, 1,
4823                                        clusters_to_add, &bit_off, &num_bits);
4824        if (status < 0) {
4825                if (status != -ENOSPC)
4826                        mlog_errno(status);
4827                goto leave;
4828        }
4829
4830        BUG_ON(num_bits > clusters_to_add);
4831
4832        /* reserve our write early -- insert_extent may update the tree root */
4833        status = ocfs2_et_root_journal_access(handle, et,
4834                                              OCFS2_JOURNAL_ACCESS_WRITE);
4835        if (status < 0) {
4836                mlog_errno(status);
4837                need_free = 1;
4838                goto bail;
4839        }
4840
4841        block = ocfs2_clusters_to_blocks(osb->sb, bit_off);
4842        trace_ocfs2_add_clusters_in_btree(
4843             (unsigned long long)ocfs2_metadata_cache_owner(et->et_ci),
4844             bit_off, num_bits);
4845        status = ocfs2_insert_extent(handle, et, *logical_offset, block,
4846                                     num_bits, flags, meta_ac);
4847        if (status < 0) {
4848                mlog_errno(status);
4849                need_free = 1;
4850                goto bail;
4851        }
4852
4853        ocfs2_journal_dirty(handle, et->et_root_bh);
4854
4855        clusters_to_add -= num_bits;
4856        *logical_offset += num_bits;
4857
4858        if (clusters_to_add) {
4859                err = clusters_to_add;
4860                status = -EAGAIN;
4861                reason = RESTART_TRANS;
4862        }
4863
4864bail:
4865        if (need_free) {
4866                if (data_ac->ac_which == OCFS2_AC_USE_LOCAL)
4867                        ocfs2_free_local_alloc_bits(osb, handle, data_ac,
4868                                        bit_off, num_bits);
4869                else
4870                        ocfs2_free_clusters(handle,
4871                                        data_ac->ac_inode,
4872                                        data_ac->ac_bh,
4873                                        ocfs2_clusters_to_blocks(osb->sb, bit_off),
4874                                        num_bits);
4875        }
4876
4877leave:
4878        if (reason_ret)
4879                *reason_ret = reason;
4880        trace_ocfs2_add_clusters_in_btree_ret(status, reason, err);
4881        return status;
4882}
4883
4884static void ocfs2_make_right_split_rec(struct super_block *sb,
4885                                       struct ocfs2_extent_rec *split_rec,
4886                                       u32 cpos,
4887                                       struct ocfs2_extent_rec *rec)
4888{
4889        u32 rec_cpos = le32_to_cpu(rec->e_cpos);
4890        u32 rec_range = rec_cpos + le16_to_cpu(rec->e_leaf_clusters);
4891
4892        memset(split_rec, 0, sizeof(struct ocfs2_extent_rec));
4893
4894        split_rec->e_cpos = cpu_to_le32(cpos);
4895        split_rec->e_leaf_clusters = cpu_to_le16(rec_range - cpos);
4896
4897        split_rec->e_blkno = rec->e_blkno;
4898        le64_add_cpu(&split_rec->e_blkno,
4899                     ocfs2_clusters_to_blocks(sb, cpos - rec_cpos));
4900
4901        split_rec->e_flags = rec->e_flags;
4902}
4903
4904static int ocfs2_split_and_insert(handle_t *handle,
4905                                  struct ocfs2_extent_tree *et,
4906                                  struct ocfs2_path *path,
4907                                  struct buffer_head **last_eb_bh,
4908                                  int split_index,
4909                                  struct ocfs2_extent_rec *orig_split_rec,
4910                                  struct ocfs2_alloc_context *meta_ac)
4911{
4912        int ret = 0, depth;
4913        unsigned int insert_range, rec_range, do_leftright = 0;
4914        struct ocfs2_extent_rec tmprec;
4915        struct ocfs2_extent_list *rightmost_el;
4916        struct ocfs2_extent_rec rec;
4917        struct ocfs2_extent_rec split_rec = *orig_split_rec;
4918        struct ocfs2_insert_type insert;
4919        struct ocfs2_extent_block *eb;
4920
4921leftright:
4922        /*
4923         * Store a copy of the record on the stack - it might move
4924         * around as the tree is manipulated below.
4925         */
4926        rec = path_leaf_el(path)->l_recs[split_index];
4927
4928        rightmost_el = et->et_root_el;
4929
4930        depth = le16_to_cpu(rightmost_el->l_tree_depth);
4931        if (depth) {
4932                BUG_ON(!(*last_eb_bh));
4933                eb = (struct ocfs2_extent_block *) (*last_eb_bh)->b_data;
4934                rightmost_el = &eb->h_list;
4935        }
4936
4937        if (le16_to_cpu(rightmost_el->l_next_free_rec) ==
4938            le16_to_cpu(rightmost_el->l_count)) {
4939                ret = ocfs2_grow_tree(handle, et,
4940                                      &depth, last_eb_bh, meta_ac);
4941                if (ret) {
4942                        mlog_errno(ret);
4943                        goto out;
4944                }
4945        }
4946
4947        memset(&insert, 0, sizeof(struct ocfs2_insert_type));
4948        insert.ins_appending = APPEND_NONE;
4949        insert.ins_contig = CONTIG_NONE;
4950        insert.ins_tree_depth = depth;
4951
4952        insert_range = le32_to_cpu(split_rec.e_cpos) +
4953                le16_to_cpu(split_rec.e_leaf_clusters);
4954        rec_range = le32_to_cpu(rec.e_cpos) +
4955                le16_to_cpu(rec.e_leaf_clusters);
4956
4957        if (split_rec.e_cpos == rec.e_cpos) {
4958                insert.ins_split = SPLIT_LEFT;
4959        } else if (insert_range == rec_range) {
4960                insert.ins_split = SPLIT_RIGHT;
4961        } else {
4962                /*
4963                 * Left/right split. We fake this as a right split
4964                 * first and then make a second pass as a left split.
4965                 */
4966                insert.ins_split = SPLIT_RIGHT;
4967
4968                ocfs2_make_right_split_rec(ocfs2_metadata_cache_get_super(et->et_ci),
4969                                           &tmprec, insert_range, &rec);
4970
4971                split_rec = tmprec;
4972
4973                BUG_ON(do_leftright);
4974                do_leftright = 1;
4975        }
4976
4977        ret = ocfs2_do_insert_extent(handle, et, &split_rec, &insert);
4978        if (ret) {
4979                mlog_errno(ret);
4980                goto out;
4981        }
4982
4983        if (do_leftright == 1) {
4984                u32 cpos;
4985                struct ocfs2_extent_list *el;
4986
4987                do_leftright++;
4988                split_rec = *orig_split_rec;
4989
4990                ocfs2_reinit_path(path, 1);
4991
4992                cpos = le32_to_cpu(split_rec.e_cpos);
4993                ret = ocfs2_find_path(et->et_ci, path, cpos);
4994                if (ret) {
4995                        mlog_errno(ret);
4996                        goto out;
4997                }
4998
4999                el = path_leaf_el(path);
5000                split_index = ocfs2_search_extent_list(el, cpos);
5001                if (split_index == -1) {
5002                        ocfs2_error(ocfs2_metadata_cache_get_super(et->et_ci),
5003                                    "Owner %llu has an extent at cpos %u which can no longer be found\n",
5004                                    (unsigned long long)ocfs2_metadata_cache_owner(et->et_ci),
5005                                    cpos);
5006                        ret = -EROFS;
5007                        goto out;
5008                }
5009                goto leftright;
5010        }
5011out:
5012
5013        return ret;
5014}
5015
5016static int ocfs2_replace_extent_rec(handle_t *handle,
5017                                    struct ocfs2_extent_tree *et,
5018                                    struct ocfs2_path *path,
5019                                    struct ocfs2_extent_list *el,
5020                                    int split_index,
5021                                    struct ocfs2_extent_rec *split_rec)
5022{
5023        int ret;
5024
5025        ret = ocfs2_path_bh_journal_access(handle, et->et_ci, path,
5026                                           path_num_items(path) - 1);
5027        if (ret) {
5028                mlog_errno(ret);
5029                goto out;
5030        }
5031
5032        el->l_recs[split_index] = *split_rec;
5033
5034        ocfs2_journal_dirty(handle, path_leaf_bh(path));
5035out:
5036        return ret;
5037}
5038
5039/*
5040 * Split part or all of the extent record at split_index in the leaf
5041 * pointed to by path. Merge with the contiguous extent record if needed.
5042 *
5043 * Care is taken to handle contiguousness so as to not grow the tree.
5044 *
5045 * meta_ac is not strictly necessary - we only truly need it if growth
5046 * of the tree is required. All other cases will degrade into a less
5047 * optimal tree layout.
5048 *
5049 * last_eb_bh should be the rightmost leaf block for any extent
5050 * btree. Since a split may grow the tree or a merge might shrink it,
5051 * the caller cannot trust the contents of that buffer after this call.
5052 *
5053 * This code is optimized for readability - several passes might be
5054 * made over certain portions of the tree. All of those blocks will
5055 * have been brought into cache (and pinned via the journal), so the
5056 * extra overhead is not expressed in terms of disk reads.
5057 */
5058int ocfs2_split_extent(handle_t *handle,
5059                       struct ocfs2_extent_tree *et,
5060                       struct ocfs2_path *path,
5061                       int split_index,
5062                       struct ocfs2_extent_rec *split_rec,
5063                       struct ocfs2_alloc_context *meta_ac,
5064                       struct ocfs2_cached_dealloc_ctxt *dealloc)
5065{
5066        int ret = 0;
5067        struct ocfs2_extent_list *el = path_leaf_el(path);
5068        struct buffer_head *last_eb_bh = NULL;
5069        struct ocfs2_extent_rec *rec = &el->l_recs[split_index];
5070        struct ocfs2_merge_ctxt ctxt;
5071
5072        if (le32_to_cpu(rec->e_cpos) > le32_to_cpu(split_rec->e_cpos) ||
5073            ((le32_to_cpu(rec->e_cpos) + le16_to_cpu(rec->e_leaf_clusters)) <
5074             (le32_to_cpu(split_rec->e_cpos) + le16_to_cpu(split_rec->e_leaf_clusters)))) {
5075                ret = -EIO;
5076                mlog_errno(ret);
5077                goto out;
5078        }
5079
5080        ret = ocfs2_figure_merge_contig_type(et, path, el,
5081                                             split_index,
5082                                             split_rec,
5083                                             &ctxt);
5084        if (ret) {
5085                mlog_errno(ret);
5086                goto out;
5087        }
5088
5089        /*
5090         * The core merge / split code wants to know how much room is
5091         * left in this allocation tree, so we pass the
5092         * rightmost extent list.
5093         */
5094        if (path->p_tree_depth) {
5095                ret = ocfs2_read_extent_block(et->et_ci,
5096                                              ocfs2_et_get_last_eb_blk(et),
5097                                              &last_eb_bh);
5098                if (ret) {
5099                        mlog_errno(ret);
5100                        goto out;
5101                }
5102        }
5103
5104        if (rec->e_cpos == split_rec->e_cpos &&
5105            rec->e_leaf_clusters == split_rec->e_leaf_clusters)
5106                ctxt.c_split_covers_rec = 1;
5107        else
5108                ctxt.c_split_covers_rec = 0;
5109
5110        ctxt.c_has_empty_extent = ocfs2_is_empty_extent(&el->l_recs[0]);
5111
5112        trace_ocfs2_split_extent(split_index, ctxt.c_contig_type,
5113                                 ctxt.c_has_empty_extent,
5114                                 ctxt.c_split_covers_rec);
5115
5116        if (ctxt.c_contig_type == CONTIG_NONE) {
5117                if (ctxt.c_split_covers_rec)
5118                        ret = ocfs2_replace_extent_rec(handle, et, path, el,
5119                                                       split_index, split_rec);
5120                else
5121                        ret = ocfs2_split_and_insert(handle, et, path,
5122                                                     &last_eb_bh, split_index,
5123                                                     split_rec, meta_ac);
5124                if (ret)
5125                        mlog_errno(ret);
5126        } else {
5127                ret = ocfs2_try_to_merge_extent(handle, et, path,
5128                                                split_index, split_rec,
5129                                                dealloc, &ctxt);
5130                if (ret)
5131                        mlog_errno(ret);
5132        }
5133
5134out:
5135        brelse(last_eb_bh);
5136        return ret;
5137}
5138
5139/*
5140 * Change the flags of the already-existing extent at cpos for len clusters.
5141 *
5142 * new_flags: the flags we want to set.
5143 * clear_flags: the flags we want to clear.
5144 * phys: the new physical offset we want this new extent starts from.
5145 *
5146 * If the existing extent is larger than the request, initiate a
5147 * split. An attempt will be made at merging with adjacent extents.
5148 *
5149 * The caller is responsible for passing down meta_ac if we'll need it.
5150 */
5151int ocfs2_change_extent_flag(handle_t *handle,
5152                             struct ocfs2_extent_tree *et,
5153                             u32 cpos, u32 len, u32 phys,
5154                             struct ocfs2_alloc_context *meta_ac,
5155                             struct ocfs2_cached_dealloc_ctxt *dealloc,
5156                             int new_flags, int clear_flags)
5157{
5158        int ret, index;
5159        struct super_block *sb = ocfs2_metadata_cache_get_super(et->et_ci);
5160        u64 start_blkno = ocfs2_clusters_to_blocks(sb, phys);
5161        struct ocfs2_extent_rec split_rec;
5162        struct ocfs2_path *left_path = NULL;
5163        struct ocfs2_extent_list *el;
5164        struct ocfs2_extent_rec *rec;
5165
5166        left_path = ocfs2_new_path_from_et(et);
5167        if (!left_path) {
5168                ret = -ENOMEM;
5169                mlog_errno(ret);
5170                goto out;
5171        }
5172
5173        ret = ocfs2_find_path(et->et_ci, left_path, cpos);
5174        if (ret) {
5175                mlog_errno(ret);
5176                goto out;
5177        }
5178        el = path_leaf_el(left_path);
5179
5180        index = ocfs2_search_extent_list(el, cpos);
5181        if (index == -1) {
5182                ocfs2_error(sb,
5183                            "Owner %llu has an extent at cpos %u which can no longer be found\n",
5184                            (unsigned long long)ocfs2_metadata_cache_owner(et->et_ci),
5185                            cpos);
5186                ret = -EROFS;
5187                goto out;
5188        }
5189
5190        ret = -EIO;
5191        rec = &el->l_recs[index];
5192        if (new_flags && (rec->e_flags & new_flags)) {
5193                mlog(ML_ERROR, "Owner %llu tried to set %d flags on an "
5194                     "extent that already had them\n",
5195                     (unsigned long long)ocfs2_metadata_cache_owner(et->et_ci),
5196                     new_flags);
5197                goto out;
5198        }
5199
5200        if (clear_flags && !(rec->e_flags & clear_flags)) {
5201                mlog(ML_ERROR, "Owner %llu tried to clear %d flags on an "
5202                     "extent that didn't have them\n",
5203                     (unsigned long long)ocfs2_metadata_cache_owner(et->et_ci),
5204                     clear_flags);
5205                goto out;
5206        }
5207
5208        memset(&split_rec, 0, sizeof(struct ocfs2_extent_rec));
5209        split_rec.e_cpos = cpu_to_le32(cpos);
5210        split_rec.e_leaf_clusters = cpu_to_le16(len);
5211        split_rec.e_blkno = cpu_to_le64(start_blkno);
5212        split_rec.e_flags = rec->e_flags;
5213        if (new_flags)
5214                split_rec.e_flags |= new_flags;
5215        if (clear_flags)
5216                split_rec.e_flags &= ~clear_flags;
5217
5218        ret = ocfs2_split_extent(handle, et, left_path,
5219                                 index, &split_rec, meta_ac,
5220                                 dealloc);
5221        if (ret)
5222                mlog_errno(ret);
5223
5224out:
5225        ocfs2_free_path(left_path);
5226        return ret;
5227
5228}
5229
5230/*
5231 * Mark the already-existing extent at cpos as written for len clusters.
5232 * This removes the unwritten extent flag.
5233 *
5234 * If the existing extent is larger than the request, initiate a
5235 * split. An attempt will be made at merging with adjacent extents.
5236 *
5237 * The caller is responsible for passing down meta_ac if we'll need it.
5238 */
5239int ocfs2_mark_extent_written(struct inode *inode,
5240                              struct ocfs2_extent_tree *et,
5241                              handle_t *handle, u32 cpos, u32 len, u32 phys,
5242                              struct ocfs2_alloc_context *meta_ac,
5243                              struct ocfs2_cached_dealloc_ctxt *dealloc)
5244{
5245        int ret;
5246
5247        trace_ocfs2_mark_extent_written(
5248                (unsigned long long)OCFS2_I(inode)->ip_blkno,
5249                cpos, len, phys);
5250
5251        if (!ocfs2_writes_unwritten_extents(OCFS2_SB(inode->i_sb))) {
5252                ocfs2_error(inode->i_sb, "Inode %llu has unwritten extents that are being written to, but the feature bit is not set in the super block\n",
5253                            (unsigned long long)OCFS2_I(inode)->ip_blkno);
5254                ret = -EROFS;
5255                goto out;
5256        }
5257
5258        /*
5259         * XXX: This should be fixed up so that we just re-insert the
5260         * next extent records.
5261         */
5262        ocfs2_et_extent_map_truncate(et, 0);
5263
5264        ret = ocfs2_change_extent_flag(handle, et, cpos,
5265                                       len, phys, meta_ac, dealloc,
5266                                       0, OCFS2_EXT_UNWRITTEN);
5267        if (ret)
5268                mlog_errno(ret);
5269
5270out:
5271        return ret;
5272}
5273
5274static int ocfs2_split_tree(handle_t *handle, struct ocfs2_extent_tree *et,
5275                            struct ocfs2_path *path,
5276                            int index, u32 new_range,
5277                            struct ocfs2_alloc_context *meta_ac)
5278{
5279        int ret, depth, credits;
5280        struct buffer_head *last_eb_bh = NULL;
5281        struct ocfs2_extent_block *eb;
5282        struct ocfs2_extent_list *rightmost_el, *el;
5283        struct ocfs2_extent_rec split_rec;
5284        struct ocfs2_extent_rec *rec;
5285        struct ocfs2_insert_type insert;
5286
5287        /*
5288         * Setup the record to split before we grow the tree.
5289         */
5290        el = path_leaf_el(path);
5291        rec = &el->l_recs[index];
5292        ocfs2_make_right_split_rec(ocfs2_metadata_cache_get_super(et->et_ci),
5293                                   &split_rec, new_range, rec);
5294
5295        depth = path->p_tree_depth;
5296        if (depth > 0) {
5297                ret = ocfs2_read_extent_block(et->et_ci,
5298                                              ocfs2_et_get_last_eb_blk(et),
5299                                              &last_eb_bh);
5300                if (ret < 0) {
5301                        mlog_errno(ret);
5302                        goto out;
5303                }
5304
5305                eb = (struct ocfs2_extent_block *) last_eb_bh->b_data;
5306                rightmost_el = &eb->h_list;
5307        } else
5308                rightmost_el = path_leaf_el(path);
5309
5310        credits = path->p_tree_depth +
5311                  ocfs2_extend_meta_needed(et->et_root_el);
5312        ret = ocfs2_extend_trans(handle, credits);
5313        if (ret) {
5314                mlog_errno(ret);
5315                goto out;
5316        }
5317
5318        if (le16_to_cpu(rightmost_el->l_next_free_rec) ==
5319            le16_to_cpu(rightmost_el->l_count)) {
5320                ret = ocfs2_grow_tree(handle, et, &depth, &last_eb_bh,
5321                                      meta_ac);
5322                if (ret) {
5323                        mlog_errno(ret);
5324                        goto out;
5325                }
5326        }
5327
5328        memset(&insert, 0, sizeof(struct ocfs2_insert_type));
5329        insert.ins_appending = APPEND_NONE;
5330        insert.ins_contig = CONTIG_NONE;
5331        insert.ins_split = SPLIT_RIGHT;
5332        insert.ins_tree_depth = depth;
5333
5334        ret = ocfs2_do_insert_extent(handle, et, &split_rec, &insert);
5335        if (ret)
5336                mlog_errno(ret);
5337
5338out:
5339        brelse(last_eb_bh);
5340        return ret;
5341}
5342
5343static int ocfs2_truncate_rec(handle_t *handle,
5344                              struct ocfs2_extent_tree *et,
5345                              struct ocfs2_path *path, int index,
5346                              struct ocfs2_cached_dealloc_ctxt *dealloc,
5347                              u32 cpos, u32 len)
5348{
5349        int ret;
5350        u32 left_cpos, rec_range, trunc_range;
5351        int is_rightmost_tree_rec = 0;
5352        struct super_block *sb = ocfs2_metadata_cache_get_super(et->et_ci);
5353        struct ocfs2_path *left_path = NULL;
5354        struct ocfs2_extent_list *el = path_leaf_el(path);
5355        struct ocfs2_extent_rec *rec;
5356        struct ocfs2_extent_block *eb;
5357
5358        if (ocfs2_is_empty_extent(&el->l_recs[0]) && index > 0) {
5359                /* extend credit for ocfs2_remove_rightmost_path */
5360                ret = ocfs2_extend_rotate_transaction(handle, 0,
5361                                handle->h_buffer_credits,
5362                                path);
5363                if (ret) {
5364                        mlog_errno(ret);
5365                        goto out;
5366                }
5367
5368                ret = ocfs2_rotate_tree_left(handle, et, path, dealloc);
5369                if (ret) {
5370                        mlog_errno(ret);
5371                        goto out;
5372                }
5373
5374                index--;
5375        }
5376
5377        if (index == (le16_to_cpu(el->l_next_free_rec) - 1) &&
5378            path->p_tree_depth) {
5379                /*
5380                 * Check whether this is the rightmost tree record. If
5381                 * we remove all of this record or part of its right
5382                 * edge then an update of the record lengths above it
5383                 * will be required.
5384                 */
5385                eb = (struct ocfs2_extent_block *)path_leaf_bh(path)->b_data;
5386                if (eb->h_next_leaf_blk == 0)
5387                        is_rightmost_tree_rec = 1;
5388        }
5389
5390        rec = &el->l_recs[index];
5391        if (index == 0 && path->p_tree_depth &&
5392            le32_to_cpu(rec->e_cpos) == cpos) {
5393                /*
5394                 * Changing the leftmost offset (via partial or whole
5395                 * record truncate) of an interior (or rightmost) path
5396                 * means we have to update the subtree that is formed
5397                 * by this leaf and the one to it's left.
5398                 *
5399                 * There are two cases we can skip:
5400                 *   1) Path is the leftmost one in our btree.
5401                 *   2) The leaf is rightmost and will be empty after
5402                 *      we remove the extent record - the rotate code
5403                 *      knows how to update the newly formed edge.
5404                 */
5405
5406                ret = ocfs2_find_cpos_for_left_leaf(sb, path, &left_cpos);
5407                if (ret) {
5408                        mlog_errno(ret);
5409                        goto out;
5410                }
5411
5412                if (left_cpos && le16_to_cpu(el->l_next_free_rec) > 1) {
5413                        left_path = ocfs2_new_path_from_path(path);
5414                        if (!left_path) {
5415                                ret = -ENOMEM;
5416                                mlog_errno(ret);
5417                                goto out;
5418                        }
5419
5420                        ret = ocfs2_find_path(et->et_ci, left_path,
5421                                              left_cpos);
5422                        if (ret) {
5423                                mlog_errno(ret);
5424                                goto out;
5425                        }
5426                }
5427        }
5428
5429        ret = ocfs2_extend_rotate_transaction(handle, 0,
5430                                              handle->h_buffer_credits,
5431                                              path);
5432        if (ret) {
5433                mlog_errno(ret);
5434                goto out;
5435        }
5436
5437        ret = ocfs2_journal_access_path(et->et_ci, handle, path);
5438        if (ret) {
5439                mlog_errno(ret);
5440                goto out;
5441        }
5442
5443        ret = ocfs2_journal_access_path(et->et_ci, handle, left_path);
5444        if (ret) {
5445                mlog_errno(ret);
5446                goto out;
5447        }
5448
5449        rec_range = le32_to_cpu(rec->e_cpos) + ocfs2_rec_clusters(el, rec);
5450        trunc_range = cpos + len;
5451
5452        if (le32_to_cpu(rec->e_cpos) == cpos && rec_range == trunc_range) {
5453                int next_free;
5454
5455                memset(rec, 0, sizeof(*rec));
5456                ocfs2_cleanup_merge(el, index);
5457
5458                next_free = le16_to_cpu(el->l_next_free_rec);
5459                if (is_rightmost_tree_rec && next_free > 1) {
5460                        /*
5461                         * We skip the edge update if this path will
5462                         * be deleted by the rotate code.
5463                         */
5464                        rec = &el->l_recs[next_free - 1];
5465                        ocfs2_adjust_rightmost_records(handle, et, path,
5466                                                       rec);
5467                }
5468        } else if (le32_to_cpu(rec->e_cpos) == cpos) {
5469                /* Remove leftmost portion of the record. */
5470                le32_add_cpu(&rec->e_cpos, len);
5471                le64_add_cpu(&rec->e_blkno, ocfs2_clusters_to_blocks(sb, len));
5472                le16_add_cpu(&rec->e_leaf_clusters, -len);
5473        } else if (rec_range == trunc_range) {
5474                /* Remove rightmost portion of the record */
5475                le16_add_cpu(&rec->e_leaf_clusters, -len);
5476                if (is_rightmost_tree_rec)
5477                        ocfs2_adjust_rightmost_records(handle, et, path, rec);
5478        } else {
5479                /* Caller should have trapped this. */
5480                mlog(ML_ERROR, "Owner %llu: Invalid record truncate: (%u, %u) "
5481                     "(%u, %u)\n",
5482                     (unsigned long long)ocfs2_metadata_cache_owner(et->et_ci),
5483                     le32_to_cpu(rec->e_cpos),
5484                     le16_to_cpu(rec->e_leaf_clusters), cpos, len);
5485                BUG();
5486        }
5487
5488        if (left_path) {
5489                int subtree_index;
5490
5491                subtree_index = ocfs2_find_subtree_root(et, left_path, path);
5492                ocfs2_complete_edge_insert(handle, left_path, path,
5493                                           subtree_index);
5494        }
5495
5496        ocfs2_journal_dirty(handle, path_leaf_bh(path));
5497
5498        ret = ocfs2_rotate_tree_left(handle, et, path, dealloc);
5499        if (ret)
5500                mlog_errno(ret);
5501
5502out:
5503        ocfs2_free_path(left_path);
5504        return ret;
5505}
5506
5507int ocfs2_remove_extent(handle_t *handle,
5508                        struct ocfs2_extent_tree *et,
5509                        u32 cpos, u32 len,
5510                        struct ocfs2_alloc_context *meta_ac,
5511                        struct ocfs2_cached_dealloc_ctxt *dealloc)
5512{
5513        int ret, index;
5514        u32 rec_range, trunc_range;
5515        struct ocfs2_extent_rec *rec;
5516        struct ocfs2_extent_list *el;
5517        struct ocfs2_path *path = NULL;
5518
5519        /*
5520         * XXX: Why are we truncating to 0 instead of wherever this
5521         * affects us?
5522         */
5523        ocfs2_et_extent_map_truncate(et, 0);
5524
5525        path = ocfs2_new_path_from_et(et);
5526        if (!path) {
5527                ret = -ENOMEM;
5528                mlog_errno(ret);
5529                goto out;
5530        }
5531
5532        ret = ocfs2_find_path(et->et_ci, path, cpos);
5533        if (ret) {
5534                mlog_errno(ret);
5535                goto out;
5536        }
5537
5538        el = path_leaf_el(path);
5539        index = ocfs2_search_extent_list(el, cpos);
5540        if (index == -1) {
5541                ocfs2_error(ocfs2_metadata_cache_get_super(et->et_ci),
5542                            "Owner %llu has an extent at cpos %u which can no longer be found\n",
5543                            (unsigned long long)ocfs2_metadata_cache_owner(et->et_ci),
5544                            cpos);
5545                ret = -EROFS;
5546                goto out;
5547        }
5548
5549        /*
5550         * We have 3 cases of extent removal:
5551         *   1) Range covers the entire extent rec
5552         *   2) Range begins or ends on one edge of the extent rec
5553         *   3) Range is in the middle of the extent rec (no shared edges)
5554         *
5555         * For case 1 we remove the extent rec and left rotate to
5556         * fill the hole.
5557         *
5558         * For case 2 we just shrink the existing extent rec, with a
5559         * tree update if the shrinking edge is also the edge of an
5560         * extent block.
5561         *
5562         * For case 3 we do a right split to turn the extent rec into
5563         * something case 2 can handle.
5564         */
5565        rec = &el->l_recs[index];
5566        rec_range = le32_to_cpu(rec->e_cpos) + ocfs2_rec_clusters(el, rec);
5567        trunc_range = cpos + len;
5568
5569        BUG_ON(cpos < le32_to_cpu(rec->e_cpos) || trunc_range > rec_range);
5570
5571        trace_ocfs2_remove_extent(
5572                (unsigned long long)ocfs2_metadata_cache_owner(et->et_ci),
5573                cpos, len, index, le32_to_cpu(rec->e_cpos),
5574                ocfs2_rec_clusters(el, rec));
5575
5576        if (le32_to_cpu(rec->e_cpos) == cpos || rec_range == trunc_range) {
5577                ret = ocfs2_truncate_rec(handle, et, path, index, dealloc,
5578                                         cpos, len);
5579                if (ret) {
5580                        mlog_errno(ret);
5581                        goto out;
5582                }
5583        } else {
5584                ret = ocfs2_split_tree(handle, et, path, index,
5585                                       trunc_range, meta_ac);
5586                if (ret) {
5587                        mlog_errno(ret);
5588                        goto out;
5589                }
5590
5591                /*
5592                 * The split could have manipulated the tree enough to
5593                 * move the record location, so we have to look for it again.
5594                 */
5595                ocfs2_reinit_path(path, 1);
5596
5597                ret = ocfs2_find_path(et->et_ci, path, cpos);
5598                if (ret) {
5599                        mlog_errno(ret);
5600                        goto out;
5601                }
5602
5603                el = path_leaf_el(path);
5604                index = ocfs2_search_extent_list(el, cpos);
5605                if (index == -1) {
5606                        ocfs2_error(ocfs2_metadata_cache_get_super(et->et_ci),
5607                                    "Owner %llu: split at cpos %u lost record\n",
5608                                    (unsigned long long)ocfs2_metadata_cache_owner(et->et_ci),
5609                                    cpos);
5610                        ret = -EROFS;
5611                        goto out;
5612                }
5613
5614                /*
5615                 * Double check our values here. If anything is fishy,
5616                 * it's easier to catch it at the top level.
5617                 */
5618                rec = &el->l_recs[index];
5619                rec_range = le32_to_cpu(rec->e_cpos) +
5620                        ocfs2_rec_clusters(el, rec);
5621                if (rec_range != trunc_range) {
5622                        ocfs2_error(ocfs2_metadata_cache_get_super(et->et_ci),
5623                                    "Owner %llu: error after split at cpos %u trunc len %u, existing record is (%u,%u)\n",
5624                                    (unsigned long long)ocfs2_metadata_cache_owner(et->et_ci),
5625                                    cpos, len, le32_to_cpu(rec->e_cpos),
5626                                    ocfs2_rec_clusters(el, rec));
5627                        ret = -EROFS;
5628                        goto out;
5629                }
5630
5631                ret = ocfs2_truncate_rec(handle, et, path, index, dealloc,
5632                                         cpos, len);
5633                if (ret)
5634                        mlog_errno(ret);
5635        }
5636
5637out:
5638        ocfs2_free_path(path);
5639        return ret;
5640}
5641
5642/*
5643 * ocfs2_reserve_blocks_for_rec_trunc() would look basically the
5644 * same as ocfs2_lock_alloctors(), except for it accepts a blocks
5645 * number to reserve some extra blocks, and it only handles meta
5646 * data allocations.
5647 *
5648 * Currently, only ocfs2_remove_btree_range() uses it for truncating
5649 * and punching holes.
5650 */
5651static int ocfs2_reserve_blocks_for_rec_trunc(struct inode *inode,
5652                                              struct ocfs2_extent_tree *et,
5653                                              u32 extents_to_split,
5654                                              struct ocfs2_alloc_context **ac,
5655                                              int extra_blocks)
5656{
5657        int ret = 0, num_free_extents;
5658        unsigned int max_recs_needed = 2 * extents_to_split;
5659        struct ocfs2_super *osb = OCFS2_SB(inode->i_sb);
5660
5661        *ac = NULL;
5662
5663        num_free_extents = ocfs2_num_free_extents(et);
5664        if (num_free_extents < 0) {
5665                ret = num_free_extents;
5666                mlog_errno(ret);
5667                goto out;
5668        }
5669
5670        if (!num_free_extents ||
5671            (ocfs2_sparse_alloc(osb) && num_free_extents < max_recs_needed))
5672                extra_blocks += ocfs2_extend_meta_needed(et->et_root_el);
5673
5674        if (extra_blocks) {
5675                ret = ocfs2_reserve_new_metadata_blocks(osb, extra_blocks, ac);
5676                if (ret < 0) {
5677                        if (ret != -ENOSPC)
5678                                mlog_errno(ret);
5679                }
5680        }
5681
5682out:
5683        if (ret) {
5684                if (*ac) {
5685                        ocfs2_free_alloc_context(*ac);
5686                        *ac = NULL;
5687                }
5688        }
5689
5690        return ret;
5691}
5692
5693int ocfs2_remove_btree_range(struct inode *inode,
5694                             struct ocfs2_extent_tree *et,
5695                             u32 cpos, u32 phys_cpos, u32 len, int flags,
5696                             struct ocfs2_cached_dealloc_ctxt *dealloc,
5697                             u64 refcount_loc, bool refcount_tree_locked)
5698{
5699        int ret, credits = 0, extra_blocks = 0;
5700        u64 phys_blkno = ocfs2_clusters_to_blocks(inode->i_sb, phys_cpos);
5701        struct ocfs2_super *osb = OCFS2_SB(inode->i_sb);
5702        struct inode *tl_inode = osb->osb_tl_inode;
5703        handle_t *handle;
5704        struct ocfs2_alloc_context *meta_ac = NULL;
5705        struct ocfs2_refcount_tree *ref_tree = NULL;
5706
5707        if ((flags & OCFS2_EXT_REFCOUNTED) && len) {
5708                BUG_ON(!ocfs2_is_refcount_inode(inode));
5709
5710                if (!refcount_tree_locked) {
5711                        ret = ocfs2_lock_refcount_tree(osb, refcount_loc, 1,
5712                                                       &ref_tree, NULL);
5713                        if (ret) {
5714                                mlog