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