sys/gnu/fs/xfs/xfs_alloc_btree.c

   1 /*
   2  * Copyright (c) 2000-2001,2005 Silicon Graphics, Inc.
   3  * All Rights Reserved.
   4  *
   5  * This program is free software; you can redistribute it and/or
   6  * modify it under the terms of the GNU General Public License as
   7  * published by the Free Software Foundation.
   8  *
   9  * This program is distributed in the hope that it would be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  * GNU General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program; if not, write the Free Software Foundation,
  16  * Inc.,  51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  17  */
  18 #include "xfs.h"
  19 #include "xfs_fs.h"
  20 #include "xfs_types.h"
  21 #include "xfs_bit.h"
  22 #include "xfs_log.h"
  23 #include "xfs_inum.h"
  24 #include "xfs_trans.h"
  25 #include "xfs_sb.h"
  26 #include "xfs_ag.h"
  27 #include "xfs_dir.h"
  28 #include "xfs_dir2.h"
  29 #include "xfs_dmapi.h"
  30 #include "xfs_mount.h"
  31 #include "xfs_bmap_btree.h"
  32 #include "xfs_alloc_btree.h"
  33 #include "xfs_ialloc_btree.h"
  34 #include "xfs_dir_sf.h"
  35 #include "xfs_dir2_sf.h"
  36 #include "xfs_attr_sf.h"
  37 #include "xfs_dinode.h"
  38 #include "xfs_inode.h"
  39 #include "xfs_btree.h"
  40 #include "xfs_ialloc.h"
  41 #include "xfs_alloc.h"
  42 #include "xfs_error.h"
  43
  44 /*
  45  * Prototypes for internal functions.
  46  */
  47
  48 STATIC void xfs_alloc_log_block(xfs_trans_t *, xfs_buf_t *, int);
  49 STATIC void xfs_alloc_log_keys(xfs_btree_cur_t *, xfs_buf_t *, int, int);
  50 STATIC void xfs_alloc_log_ptrs(xfs_btree_cur_t *, xfs_buf_t *, int, int);
  51 STATIC void xfs_alloc_log_recs(xfs_btree_cur_t *, xfs_buf_t *, int, int);
  52 STATIC int xfs_alloc_lshift(xfs_btree_cur_t *, int, int *);
  53 STATIC int xfs_alloc_newroot(xfs_btree_cur_t *, int *);
  54 STATIC int xfs_alloc_rshift(xfs_btree_cur_t *, int, int *);
  55 STATIC int xfs_alloc_split(xfs_btree_cur_t *, int, xfs_agblock_t *,
  56                 xfs_alloc_key_t *, xfs_btree_cur_t **, int *);
  57 STATIC int xfs_alloc_updkey(xfs_btree_cur_t *, xfs_alloc_key_t *, int);
  58
  59 /*
  60  * Internal functions.
  61  */
  62
  63 /*
  64  * Single level of the xfs_alloc_delete record deletion routine.
  65  * Delete record pointed to by cur/level.
  66  * Remove the record from its block then rebalance the tree.
  67  * Return 0 for error, 1 for done, 2 to go on to the next level.
  68  */
  69 STATIC int                              /* error */
  70 xfs_alloc_delrec(
  71         xfs_btree_cur_t         *cur,   /* btree cursor */
  72         int                     level,  /* level removing record from */
  73         int                     *stat)  /* fail/done/go-on */
  74 {
  75         xfs_agf_t               *agf;   /* allocation group freelist header */
  76         xfs_alloc_block_t       *block; /* btree block record/key lives in */
  77         xfs_agblock_t           bno;    /* btree block number */
  78         xfs_buf_t               *bp;    /* buffer for block */
  79         int                     error;  /* error return value */
  80         int                     i;      /* loop index */
  81         xfs_alloc_key_t         key;    /* kp points here if block is level 0 */
  82         xfs_agblock_t           lbno;   /* left block's block number */
  83         xfs_buf_t               *lbp;   /* left block's buffer pointer */
  84         xfs_alloc_block_t       *left;  /* left btree block */
  85         xfs_alloc_key_t         *lkp=NULL;      /* left block key pointer */
  86         xfs_alloc_ptr_t         *lpp=NULL;      /* left block address pointer */
  87         int                     lrecs=0;        /* number of records in left block */
  88         xfs_alloc_rec_t         *lrp;   /* left block record pointer */
  89         xfs_mount_t             *mp;    /* mount structure */
  90         int                     ptr;    /* index in btree block for this rec */
  91         xfs_agblock_t           rbno;   /* right block's block number */
  92         xfs_buf_t               *rbp;   /* right block's buffer pointer */
  93         xfs_alloc_block_t       *right; /* right btree block */
  94         xfs_alloc_key_t         *rkp;   /* right block key pointer */
  95         xfs_alloc_ptr_t         *rpp;   /* right block address pointer */
  96         int                     rrecs=0;        /* number of records in right block */
  97         xfs_alloc_rec_t         *rrp;   /* right block record pointer */
  98         xfs_btree_cur_t         *tcur;  /* temporary btree cursor */
  99
 100         /*
 101          * Get the index of the entry being deleted, check for nothing there.
 102          */
 103         ptr = cur->bc_ptrs[level];
 104         if (ptr == 0) {
 105                 *stat = 0;
 106                 return 0;
 107         }
 108         /*
 109          * Get the buffer & block containing the record or key/ptr.
 110          */
 111         bp = cur->bc_bufs[level];
 112         block = XFS_BUF_TO_ALLOC_BLOCK(bp);
 113 #ifdef DEBUG
 114         if ((error = xfs_btree_check_sblock(cur, block, level, bp)))
 115                 return error;
 116 #endif
 117         /*
 118          * Fail if we're off the end of the block.
 119          */
 120         if (ptr > be16_to_cpu(block->bb_numrecs)) {
 121                 *stat = 0;
 122                 return 0;
 123         }
 124         XFS_STATS_INC(xs_abt_delrec);
 125         /*
 126          * It's a nonleaf.  Excise the key and ptr being deleted, by
 127          * sliding the entries past them down one.
 128          * Log the changed areas of the block.
 129          */
 130         if (level > 0) {
 131                 lkp = XFS_ALLOC_KEY_ADDR(block, 1, cur);
 132                 lpp = XFS_ALLOC_PTR_ADDR(block, 1, cur);
 133 #ifdef DEBUG
 134                 for (i = ptr; i < be16_to_cpu(block->bb_numrecs); i++) {
 135                         if ((error = xfs_btree_check_sptr(cur, be32_to_cpu(lpp[i]), level)))
 136                                 return error;
 137                 }
 138 #endif
 139                 if (ptr < be16_to_cpu(block->bb_numrecs)) {
 140                         memmove(&lkp[ptr - 1], &lkp[ptr],
 141                                 (be16_to_cpu(block->bb_numrecs) - ptr) * sizeof(*lkp));
 142                         memmove(&lpp[ptr - 1], &lpp[ptr],
 143                                 (be16_to_cpu(block->bb_numrecs) - ptr) * sizeof(*lpp));
 144                         xfs_alloc_log_ptrs(cur, bp, ptr, be16_to_cpu(block->bb_numrecs) - 1);
 145                         xfs_alloc_log_keys(cur, bp, ptr, be16_to_cpu(block->bb_numrecs) - 1);
 146                 }
 147         }
 148         /*
 149          * It's a leaf.  Excise the record being deleted, by sliding the
 150          * entries past it down one.  Log the changed areas of the block.
 151          */
 152         else {
 153                 lrp = XFS_ALLOC_REC_ADDR(block, 1, cur);
 154                 if (ptr < be16_to_cpu(block->bb_numrecs)) {
 155                         memmove(&lrp[ptr - 1], &lrp[ptr],
 156                                 (be16_to_cpu(block->bb_numrecs) - ptr) * sizeof(*lrp));
 157                         xfs_alloc_log_recs(cur, bp, ptr, be16_to_cpu(block->bb_numrecs) - 1);
 158                 }
 159                 /*
 160                  * If it's the first record in the block, we'll need a key
 161                  * structure to pass up to the next level (updkey).
 162                  */
 163                 if (ptr == 1) {
 164                         key.ar_startblock = lrp->ar_startblock;
 165                         key.ar_blockcount = lrp->ar_blockcount;
 166                         lkp = &key;
 167                 }
 168         }
 169         /*
 170          * Decrement and log the number of entries in the block.
 171          */
 172         be16_add(&block->bb_numrecs, -1);
 173         xfs_alloc_log_block(cur->bc_tp, bp, XFS_BB_NUMRECS);
 174         /*
 175          * See if the longest free extent in the allocation group was
 176          * changed by this operation.  True if it's the by-size btree, and
 177          * this is the leaf level, and there is no right sibling block,
 178          * and this was the last record.
 179          */
 180         agf = XFS_BUF_TO_AGF(cur->bc_private.a.agbp);
 181         mp = cur->bc_mp;
 182
 183         if (level == 0 &&
 184             cur->bc_btnum == XFS_BTNUM_CNT &&
 185             be32_to_cpu(block->bb_rightsib) == NULLAGBLOCK &&
 186             ptr > be16_to_cpu(block->bb_numrecs)) {
 187                 ASSERT(ptr == be16_to_cpu(block->bb_numrecs) + 1);
 188                 /*
 189                  * There are still records in the block.  Grab the size
 190                  * from the last one.
 191                  */
 192                 if (be16_to_cpu(block->bb_numrecs)) {
 193                         rrp = XFS_ALLOC_REC_ADDR(block, be16_to_cpu(block->bb_numrecs), cur);
 194                         agf->agf_longest = rrp->ar_blockcount;
 195                 }
 196                 /*
 197                  * No free extents left.
 198                  */
 199                 else
 200                         agf->agf_longest = 0;
 201                 mp->m_perag[be32_to_cpu(agf->agf_seqno)].pagf_longest =
 202                         be32_to_cpu(agf->agf_longest);
 203                 xfs_alloc_log_agf(cur->bc_tp, cur->bc_private.a.agbp,
 204                         XFS_AGF_LONGEST);
 205         }
 206         /*
 207          * Is this the root level?  If so, we're almost done.
 208          */
 209         if (level == cur->bc_nlevels - 1) {
 210                 /*
 211                  * If this is the root level,
 212                  * and there's only one entry left,
 213                  * and it's NOT the leaf level,
 214                  * then we can get rid of this level.
 215                  */
 216                 if (be16_to_cpu(block->bb_numrecs) == 1 && level > 0) {
 217                         /*
 218                          * lpp is still set to the first pointer in the block.
 219                          * Make it the new root of the btree.
 220                          */
 221                         bno = be32_to_cpu(agf->agf_roots[cur->bc_btnum]);
 222                         agf->agf_roots[cur->bc_btnum] = *lpp;
 223                         be32_add(&agf->agf_levels[cur->bc_btnum], -1);
 224                         mp->m_perag[be32_to_cpu(agf->agf_seqno)].pagf_levels[cur->bc_btnum]--;
 225                         /*
 226                          * Put this buffer/block on the ag's freelist.
 227                          */
 228                         if ((error = xfs_alloc_put_freelist(cur->bc_tp,
 229                                         cur->bc_private.a.agbp, NULL, bno)))
 230                                 return error;
 231                         /*
 232                          * Since blocks move to the free list without the
 233                          * coordination used in xfs_bmap_finish, we can't allow
 234                          * block to be available for reallocation and
 235                          * non-transaction writing (user data) until we know
 236                          * that the transaction that moved it to the free list
 237                          * is permanently on disk. We track the blocks by
 238                          * declaring these blocks as "busy"; the busy list is
 239                          * maintained on a per-ag basis and each transaction
 240                          * records which entries should be removed when the
 241                          * iclog commits to disk. If a busy block is
 242                          * allocated, the iclog is pushed up to the LSN
 243                          * that freed the block.
 244                          */
 245                         xfs_alloc_mark_busy(cur->bc_tp,
 246                                 be32_to_cpu(agf->agf_seqno), bno, 1);
 247
 248                         xfs_trans_agbtree_delta(cur->bc_tp, -1);
 249                         xfs_alloc_log_agf(cur->bc_tp, cur->bc_private.a.agbp,
 250                                 XFS_AGF_ROOTS | XFS_AGF_LEVELS);
 251                         /*
 252                          * Update the cursor so there's one fewer level.
 253                          */
 254                         xfs_btree_setbuf(cur, level, NULL);
 255                         cur->bc_nlevels--;
 256                 } else if (level > 0 &&
 257                            (error = xfs_alloc_decrement(cur, level, &i)))
 258                         return error;
 259                 *stat = 1;
 260                 return 0;
 261         }
 262         /*
 263          * If we deleted the leftmost entry in the block, update the
 264          * key values above us in the tree.
 265          */
 266         if (ptr == 1 && (error = xfs_alloc_updkey(cur, lkp, level + 1)))
 267                 return error;
 268         /*
 269          * If the number of records remaining in the block is at least
 270          * the minimum, we're done.
 271          */
 272         if (be16_to_cpu(block->bb_numrecs) >= XFS_ALLOC_BLOCK_MINRECS(level, cur)) {
 273                 if (level > 0 && (error = xfs_alloc_decrement(cur, level, &i)))
 274                         return error;
 275                 *stat = 1;
 276                 return 0;
 277         }
 278         /*
 279          * Otherwise, we have to move some records around to keep the
 280          * tree balanced.  Look at the left and right sibling blocks to
 281          * see if we can re-balance by moving only one record.
 282          */
 283         rbno = be32_to_cpu(block->bb_rightsib);
 284         lbno = be32_to_cpu(block->bb_leftsib);
 285         bno = NULLAGBLOCK;
 286         ASSERT(rbno != NULLAGBLOCK || lbno != NULLAGBLOCK);
 287         /*
 288          * Duplicate the cursor so our btree manipulations here won't
 289          * disrupt the next level up.
 290          */
 291         if ((error = xfs_btree_dup_cursor(cur, &tcur)))
 292                 return error;
 293         /*
 294          * If there's a right sibling, see if it's ok to shift an entry
 295          * out of it.
 296          */
 297         if (rbno != NULLAGBLOCK) {
 298                 /*
 299                  * Move the temp cursor to the last entry in the next block.
 300                  * Actually any entry but the first would suffice.
 301                  */
 302                 i = xfs_btree_lastrec(tcur, level);
 303                 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
 304                 if ((error = xfs_alloc_increment(tcur, level, &i)))
 305                         goto error0;
 306                 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
 307                 i = xfs_btree_lastrec(tcur, level);
 308                 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
 309                 /*
 310                  * Grab a pointer to the block.
 311                  */
 312                 rbp = tcur->bc_bufs[level];
 313                 right = XFS_BUF_TO_ALLOC_BLOCK(rbp);
 314 #ifdef DEBUG
 315                 if ((error = xfs_btree_check_sblock(cur, right, level, rbp)))
 316                         goto error0;
 317 #endif
 318                 /*
 319                  * Grab the current block number, for future use.
 320                  */
 321                 bno = be32_to_cpu(right->bb_leftsib);
 322                 /*
 323                  * If right block is full enough so that removing one entry
 324                  * won't make it too empty, and left-shifting an entry out
 325                  * of right to us works, we're done.
 326                  */
 327                 if (be16_to_cpu(right->bb_numrecs) - 1 >=
 328                      XFS_ALLOC_BLOCK_MINRECS(level, cur)) {
 329                         if ((error = xfs_alloc_lshift(tcur, level, &i)))
 330                                 goto error0;
 331                         if (i) {
 332                                 ASSERT(be16_to_cpu(block->bb_numrecs) >=
 333                                        XFS_ALLOC_BLOCK_MINRECS(level, cur));
 334                                 xfs_btree_del_cursor(tcur,
 335                                                      XFS_BTREE_NOERROR);
 336                                 if (level > 0 &&
 337                                     (error = xfs_alloc_decrement(cur, level,
 338                                             &i)))
 339                                         return error;
 340                                 *stat = 1;
 341                                 return 0;
 342                         }
 343                 }
 344                 /*
 345                  * Otherwise, grab the number of records in right for
 346                  * future reference, and fix up the temp cursor to point
 347                  * to our block again (last record).
 348                  */
 349                 rrecs = be16_to_cpu(right->bb_numrecs);
 350                 if (lbno != NULLAGBLOCK) {
 351                         i = xfs_btree_firstrec(tcur, level);
 352                         XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
 353                         if ((error = xfs_alloc_decrement(tcur, level, &i)))
 354                                 goto error0;
 355                         XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
 356                 }
 357         }
 358         /*
 359          * If there's a left sibling, see if it's ok to shift an entry
 360          * out of it.
 361          */
 362         if (lbno != NULLAGBLOCK) {
 363                 /*
 364                  * Move the temp cursor to the first entry in the
 365                  * previous block.
 366                  */
 367                 i = xfs_btree_firstrec(tcur, level);
 368                 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
 369                 if ((error = xfs_alloc_decrement(tcur, level, &i)))
 370                         goto error0;
 371                 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
 372                 xfs_btree_firstrec(tcur, level);
 373                 /*
 374                  * Grab a pointer to the block.
 375                  */
 376                 lbp = tcur->bc_bufs[level];
 377                 left = XFS_BUF_TO_ALLOC_BLOCK(lbp);
 378 #ifdef DEBUG
 379                 if ((error = xfs_btree_check_sblock(cur, left, level, lbp)))
 380                         goto error0;
 381 #endif
 382                 /*
 383                  * Grab the current block number, for future use.
 384                  */
 385                 bno = be32_to_cpu(left->bb_rightsib);
 386                 /*
 387                  * If left block is full enough so that removing one entry
 388                  * won't make it too empty, and right-shifting an entry out
 389                  * of left to us works, we're done.
 390                  */
 391                 if (be16_to_cpu(left->bb_numrecs) - 1 >=
 392                      XFS_ALLOC_BLOCK_MINRECS(level, cur)) {
 393                         if ((error = xfs_alloc_rshift(tcur, level, &i)))
 394                                 goto error0;
 395                         if (i) {
 396                                 ASSERT(be16_to_cpu(block->bb_numrecs) >=
 397                                        XFS_ALLOC_BLOCK_MINRECS(level, cur));
 398                                 xfs_btree_del_cursor(tcur,
 399                                                      XFS_BTREE_NOERROR);
 400                                 if (level == 0)
 401                                         cur->bc_ptrs[0]++;
 402                                 *stat = 1;
 403                                 return 0;
 404                         }
 405                 }
 406                 /*
 407                  * Otherwise, grab the number of records in right for
 408                  * future reference.
 409                  */
 410                 lrecs = be16_to_cpu(left->bb_numrecs);
 411         }
 412         /*
 413          * Delete the temp cursor, we're done with it.
 414          */
 415         xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
 416         /*
 417          * If here, we need to do a join to keep the tree balanced.
 418          */
 419         ASSERT(bno != NULLAGBLOCK);
 420         /*
 421          * See if we can join with the left neighbor block.
 422          */
 423         if (lbno != NULLAGBLOCK &&
 424             lrecs + be16_to_cpu(block->bb_numrecs) <= XFS_ALLOC_BLOCK_MAXRECS(level, cur)) {
 425                 /*
 426                  * Set "right" to be the starting block,
 427                  * "left" to be the left neighbor.
 428                  */
 429                 rbno = bno;
 430                 right = block;
 431                 rbp = bp;
 432                 if ((error = xfs_btree_read_bufs(mp, cur->bc_tp,
 433                                 cur->bc_private.a.agno, lbno, 0, &lbp,
 434                                 XFS_ALLOC_BTREE_REF)))
 435                         return error;
 436                 left = XFS_BUF_TO_ALLOC_BLOCK(lbp);
 437                 if ((error = xfs_btree_check_sblock(cur, left, level, lbp)))
 438                         return error;
 439         }
 440         /*
 441          * If that won't work, see if we can join with the right neighbor block.
 442          */
 443         else if (rbno != NULLAGBLOCK &&
 444                  rrecs + be16_to_cpu(block->bb_numrecs) <=
 445                   XFS_ALLOC_BLOCK_MAXRECS(level, cur)) {
 446                 /*
 447                  * Set "left" to be the starting block,
 448                  * "right" to be the right neighbor.
 449                  */
 450                 lbno = bno;
 451                 left = block;
 452                 lbp = bp;
 453                 if ((error = xfs_btree_read_bufs(mp, cur->bc_tp,
 454                                 cur->bc_private.a.agno, rbno, 0, &rbp,
 455                                 XFS_ALLOC_BTREE_REF)))
 456                         return error;
 457                 right = XFS_BUF_TO_ALLOC_BLOCK(rbp);
 458                 if ((error = xfs_btree_check_sblock(cur, right, level, rbp)))
 459                         return error;
 460         }
 461         /*
 462          * Otherwise, we can't fix the imbalance.
 463          * Just return.  This is probably a logic error, but it's not fatal.
 464          */
 465         else {
 466                 if (level > 0 && (error = xfs_alloc_decrement(cur, level, &i)))
 467                         return error;
 468                 *stat = 1;
 469                 return 0;
 470         }
 471         /*
 472          * We're now going to join "left" and "right" by moving all the stuff
 473          * in "right" to "left" and deleting "right".
 474          */
 475         if (level > 0) {
 476                 /*
 477                  * It's a non-leaf.  Move keys and pointers.
 478                  */
 479                 lkp = XFS_ALLOC_KEY_ADDR(left, be16_to_cpu(left->bb_numrecs) + 1, cur);
 480                 lpp = XFS_ALLOC_PTR_ADDR(left, be16_to_cpu(left->bb_numrecs) + 1, cur);
 481                 rkp = XFS_ALLOC_KEY_ADDR(right, 1, cur);
 482                 rpp = XFS_ALLOC_PTR_ADDR(right, 1, cur);
 483 #ifdef DEBUG
 484                 for (i = 0; i < be16_to_cpu(right->bb_numrecs); i++) {
 485                         if ((error = xfs_btree_check_sptr(cur, be32_to_cpu(rpp[i]), level)))
 486                                 return error;
 487                 }
 488 #endif
 489                 memcpy(lkp, rkp, be16_to_cpu(right->bb_numrecs) * sizeof(*lkp));
 490                 memcpy(lpp, rpp, be16_to_cpu(right->bb_numrecs) * sizeof(*lpp));
 491                 xfs_alloc_log_keys(cur, lbp, be16_to_cpu(left->bb_numrecs) + 1,
 492                                    be16_to_cpu(left->bb_numrecs) +
 493                                    be16_to_cpu(right->bb_numrecs));
 494                 xfs_alloc_log_ptrs(cur, lbp, be16_to_cpu(left->bb_numrecs) + 1,
 495                                    be16_to_cpu(left->bb_numrecs) +
 496                                    be16_to_cpu(right->bb_numrecs));
 497         } else {
 498                 /*
 499                  * It's a leaf.  Move records.
 500                  */
 501                 lrp = XFS_ALLOC_REC_ADDR(left, be16_to_cpu(left->bb_numrecs) + 1, cur);
 502                 rrp = XFS_ALLOC_REC_ADDR(right, 1, cur);
 503                 memcpy(lrp, rrp, be16_to_cpu(right->bb_numrecs) * sizeof(*lrp));
 504                 xfs_alloc_log_recs(cur, lbp, be16_to_cpu(left->bb_numrecs) + 1,
 505                                    be16_to_cpu(left->bb_numrecs) +
 506                                    be16_to_cpu(right->bb_numrecs));
 507         }
 508         /*
 509          * If we joined with the left neighbor, set the buffer in the
 510          * cursor to the left block, and fix up the index.
 511          */
 512         if (bp != lbp) {
 513                 xfs_btree_setbuf(cur, level, lbp);
 514                 cur->bc_ptrs[level] += be16_to_cpu(left->bb_numrecs);
 515         }
 516         /*
 517          * If we joined with the right neighbor and there's a level above
 518          * us, increment the cursor at that level.
 519          */
 520         else if (level + 1 < cur->bc_nlevels &&
 521                  (error = xfs_alloc_increment(cur, level + 1, &i)))
 522                 return error;
 523         /*
 524          * Fix up the number of records in the surviving block.
 525          */
 526         be16_add(&left->bb_numrecs, be16_to_cpu(right->bb_numrecs));
 527         /*
 528          * Fix up the right block pointer in the surviving block, and log it.
 529          */
 530         left->bb_rightsib = right->bb_rightsib;
 531         xfs_alloc_log_block(cur->bc_tp, lbp, XFS_BB_NUMRECS | XFS_BB_RIGHTSIB);
 532         /*
 533          * If there is a right sibling now, make it point to the
 534          * remaining block.
 535          */
 536         if (be32_to_cpu(left->bb_rightsib) != NULLAGBLOCK) {
 537                 xfs_alloc_block_t       *rrblock;
 538                 xfs_buf_t               *rrbp;
 539
 540                 if ((error = xfs_btree_read_bufs(mp, cur->bc_tp,
 541                                 cur->bc_private.a.agno, be32_to_cpu(left->bb_rightsib), 0,
 542                                 &rrbp, XFS_ALLOC_BTREE_REF)))
 543                         return error;
 544                 rrblock = XFS_BUF_TO_ALLOC_BLOCK(rrbp);
 545                 if ((error = xfs_btree_check_sblock(cur, rrblock, level, rrbp)))
 546                         return error;
 547                 rrblock->bb_leftsib = cpu_to_be32(lbno);
 548                 xfs_alloc_log_block(cur->bc_tp, rrbp, XFS_BB_LEFTSIB);
 549         }
 550         /*
 551          * Free the deleting block by putting it on the freelist.
 552          */
 553         if ((error = xfs_alloc_put_freelist(cur->bc_tp, cur->bc_private.a.agbp,
 554                         NULL, rbno)))
 555                 return error;
 556         /*
 557          * Since blocks move to the free list without the coordination
 558          * used in xfs_bmap_finish, we can't allow block to be available
 559          * for reallocation and non-transaction writing (user data)
 560          * until we know that the transaction that moved it to the free
 561          * list is permanently on disk. We track the blocks by declaring
 562          * these blocks as "busy"; the busy list is maintained on a
 563          * per-ag basis and each transaction records which entries
 564          * should be removed when the iclog commits to disk. If a
 565          * busy block is allocated, the iclog is pushed up to the
 566          * LSN that freed the block.
 567          */
 568         xfs_alloc_mark_busy(cur->bc_tp, be32_to_cpu(agf->agf_seqno), bno, 1);
 569         xfs_trans_agbtree_delta(cur->bc_tp, -1);
 570
 571         /*
 572          * Adjust the current level's cursor so that we're left referring
 573          * to the right node, after we're done.
 574          * If this leaves the ptr value 0 our caller will fix it up.
 575          */
 576         if (level > 0)
 577                 cur->bc_ptrs[level]--;
 578         /*
 579          * Return value means the next level up has something to do.
 580          */
 581         *stat = 2;
 582         return 0;
 583
 584 error0:
 585         xfs_btree_del_cursor(tcur, XFS_BTREE_ERROR);
 586         return error;
 587 }
 588
 589 /*
 590  * Insert one record/level.  Return information to the caller
 591  * allowing the next level up to proceed if necessary.
 592  */
 593 STATIC int                              /* error */
 594 xfs_alloc_insrec(
 595         xfs_btree_cur_t         *cur,   /* btree cursor */
 596         int                     level,  /* level to insert record at */
 597         xfs_agblock_t           *bnop,  /* i/o: block number inserted */
 598         xfs_alloc_rec_t         *recp,  /* i/o: record data inserted */
 599         xfs_btree_cur_t         **curp, /* output: new cursor replacing cur */
 600         int                     *stat)  /* output: success/failure */
 601 {
 602         xfs_agf_t               *agf;   /* allocation group freelist header */
 603         xfs_alloc_block_t       *block; /* btree block record/key lives in */
 604         xfs_buf_t               *bp;    /* buffer for block */
 605         int                     error;  /* error return value */
 606         int                     i;      /* loop index */
 607         xfs_alloc_key_t         key;    /* key value being inserted */
 608         xfs_alloc_key_t         *kp;    /* pointer to btree keys */
 609         xfs_agblock_t           nbno;   /* block number of allocated block */
 610         xfs_btree_cur_t         *ncur;  /* new cursor to be used at next lvl */
 611         xfs_alloc_key_t         nkey;   /* new key value, from split */
 612         xfs_alloc_rec_t         nrec;   /* new record value, for caller */
 613         int                     optr;   /* old ptr value */
 614         xfs_alloc_ptr_t         *pp;    /* pointer to btree addresses */
 615         int                     ptr;    /* index in btree block for this rec */
 616         xfs_alloc_rec_t         *rp;    /* pointer to btree records */
 617
 618         ASSERT(be32_to_cpu(recp->ar_blockcount) > 0);
 619
 620         /*
 621          * GCC doesn't understand the (arguably complex) control flow in
 622          * this function and complains about uninitialized structure fields
 623          * without this.
 624          */
 625         memset(&nrec, 0, sizeof(nrec));
 626
 627         /*
 628          * If we made it to the root level, allocate a new root block
 629          * and we're done.
 630          */
 631         if (level >= cur->bc_nlevels) {
 632                 XFS_STATS_INC(xs_abt_insrec);
 633                 if ((error = xfs_alloc_newroot(cur, &i)))
 634                         return error;
 635                 *bnop = NULLAGBLOCK;
 636                 *stat = i;
 637                 return 0;
 638         }
 639         /*
 640          * Make a key out of the record data to be inserted, and save it.
 641          */
 642         key.ar_startblock = recp->ar_startblock;
 643         key.ar_blockcount = recp->ar_blockcount;
 644         optr = ptr = cur->bc_ptrs[level];
 645         /*
 646          * If we're off the left edge, return failure.
 647          */
 648         if (ptr == 0) {
 649                 *stat = 0;
 650                 return 0;
 651         }
 652         XFS_STATS_INC(xs_abt_insrec);
 653         /*
 654          * Get pointers to the btree buffer and block.
 655          */
 656         bp = cur->bc_bufs[level];
 657         block = XFS_BUF_TO_ALLOC_BLOCK(bp);
 658 #ifdef DEBUG
 659         if ((error = xfs_btree_check_sblock(cur, block, level, bp)))
 660                 return error;
 661         /*
 662          * Check that the new entry is being inserted in the right place.
 663          */
 664         if (ptr <= be16_to_cpu(block->bb_numrecs)) {
 665                 if (level == 0) {
 666                         rp = XFS_ALLOC_REC_ADDR(block, ptr, cur);
 667                         xfs_btree_check_rec(cur->bc_btnum, recp, rp);
 668                 } else {
 669                         kp = XFS_ALLOC_KEY_ADDR(block, ptr, cur);
 670                         xfs_btree_check_key(cur->bc_btnum, &key, kp);
 671                 }
 672         }
 673 #endif
 674         nbno = NULLAGBLOCK;
 675         ncur = (xfs_btree_cur_t *)0;
 676         /*
 677          * If the block is full, we can't insert the new entry until we
 678          * make the block un-full.
 679          */
 680         if (be16_to_cpu(block->bb_numrecs) == XFS_ALLOC_BLOCK_MAXRECS(level, cur)) {
 681                 /*
 682                  * First, try shifting an entry to the right neighbor.
 683                  */
 684                 if ((error = xfs_alloc_rshift(cur, level, &i)))
 685                         return error;
 686                 if (i) {
 687                         /* nothing */
 688                 }
 689                 /*
 690                  * Next, try shifting an entry to the left neighbor.
 691                  */
 692                 else {
 693                         if ((error = xfs_alloc_lshift(cur, level, &i)))
 694                                 return error;
 695                         if (i)
 696                                 optr = ptr = cur->bc_ptrs[level];
 697                         else {
 698                                 /*
 699                                  * Next, try splitting the current block in
 700                                  * half. If this works we have to re-set our
 701                                  * variables because we could be in a
 702                                  * different block now.
 703                                  */
 704                                 if ((error = xfs_alloc_split(cur, level, &nbno,
 705                                                 &nkey, &ncur, &i)))
 706                                         return error;
 707                                 if (i) {
 708                                         bp = cur->bc_bufs[level];
 709                                         block = XFS_BUF_TO_ALLOC_BLOCK(bp);
 710 #ifdef DEBUG
 711                                         if ((error =
 712                                                 xfs_btree_check_sblock(cur,
 713                                                         block, level, bp)))
 714                                                 return error;
 715 #endif
 716                                         ptr = cur->bc_ptrs[level];
 717                                         nrec.ar_startblock = nkey.ar_startblock;
 718                                         nrec.ar_blockcount = nkey.ar_blockcount;
 719                                 }
 720                                 /*
 721                                  * Otherwise the insert fails.
 722                                  */
 723                                 else {
 724                                         *stat = 0;
 725                                         return 0;
 726                                 }
 727                         }
 728                 }
 729         }
 730         /*
 731          * At this point we know there's room for our new entry in the block
 732          * we're pointing at.
 733          */
 734         if (level > 0) {
 735                 /*
 736                  * It's a non-leaf entry.  Make a hole for the new data
 737                  * in the key and ptr regions of the block.
 738                  */
 739                 kp = XFS_ALLOC_KEY_ADDR(block, 1, cur);
 740                 pp = XFS_ALLOC_PTR_ADDR(block, 1, cur);
 741 #ifdef DEBUG
 742                 for (i = be16_to_cpu(block->bb_numrecs); i >= ptr; i--) {
 743                         if ((error = xfs_btree_check_sptr(cur, be32_to_cpu(pp[i - 1]), level)))
 744                                 return error;
 745                 }
 746 #endif
 747                 memmove(&kp[ptr], &kp[ptr - 1],
 748                         (be16_to_cpu(block->bb_numrecs) - ptr + 1) * sizeof(*kp));
 749                 memmove(&pp[ptr], &pp[ptr - 1],
 750                         (be16_to_cpu(block->bb_numrecs) - ptr + 1) * sizeof(*pp));
 751 #ifdef DEBUG
 752                 if ((error = xfs_btree_check_sptr(cur, *bnop, level)))
 753                         return error;
 754 #endif
 755                 /*
 756                  * Now stuff the new data in, bump numrecs and log the new data.
 757                  */
 758                 kp[ptr - 1] = key;
 759                 pp[ptr - 1] = cpu_to_be32(*bnop);
 760                 be16_add(&block->bb_numrecs, 1);
 761                 xfs_alloc_log_keys(cur, bp, ptr, be16_to_cpu(block->bb_numrecs));
 762                 xfs_alloc_log_ptrs(cur, bp, ptr, be16_to_cpu(block->bb_numrecs));
 763 #ifdef DEBUG
 764                 if (ptr < be16_to_cpu(block->bb_numrecs))
 765                         xfs_btree_check_key(cur->bc_btnum, kp + ptr - 1,
 766                                 kp + ptr);
 767 #endif
 768         } else {
 769                 /*
 770                  * It's a leaf entry.  Make a hole for the new record.
 771                  */
 772                 rp = XFS_ALLOC_REC_ADDR(block, 1, cur);
 773                 memmove(&rp[ptr], &rp[ptr - 1],
 774                         (be16_to_cpu(block->bb_numrecs) - ptr + 1) * sizeof(*rp));
 775                 /*
 776                  * Now stuff the new record in, bump numrecs
 777                  * and log the new data.
 778                  */
 779                 rp[ptr - 1] = *recp; /* INT_: struct copy */
 780                 be16_add(&block->bb_numrecs, 1);
 781                 xfs_alloc_log_recs(cur, bp, ptr, be16_to_cpu(block->bb_numrecs));
 782 #ifdef DEBUG
 783                 if (ptr < be16_to_cpu(block->bb_numrecs))
 784                         xfs_btree_check_rec(cur->bc_btnum, rp + ptr - 1,
 785                                 rp + ptr);
 786 #endif
 787         }
 788         /*
 789          * Log the new number of records in the btree header.
 790          */
 791         xfs_alloc_log_block(cur->bc_tp, bp, XFS_BB_NUMRECS);
 792         /*
 793          * If we inserted at the start of a block, update the parents' keys.
 794          */
 795         if (optr == 1 && (error = xfs_alloc_updkey(cur, &key, level + 1)))
 796                 return error;
 797         /*
 798          * Look to see if the longest extent in the allocation group
 799          * needs to be updated.
 800          */
 801
 802         agf = XFS_BUF_TO_AGF(cur->bc_private.a.agbp);
 803         if (level == 0 &&
 804             cur->bc_btnum == XFS_BTNUM_CNT &&
 805             be32_to_cpu(block->bb_rightsib) == NULLAGBLOCK &&
 806             be32_to_cpu(recp->ar_blockcount) > be32_to_cpu(agf->agf_longest)) {
 807                 /*
 808                  * If this is a leaf in the by-size btree and there
 809                  * is no right sibling block and this block is bigger
 810                  * than the previous longest block, update it.
 811                  */
 812                 agf->agf_longest = recp->ar_blockcount;
 813                 cur->bc_mp->m_perag[be32_to_cpu(agf->agf_seqno)].pagf_longest
 814                         = be32_to_cpu(recp->ar_blockcount);
 815                 xfs_alloc_log_agf(cur->bc_tp, cur->bc_private.a.agbp,
 816                         XFS_AGF_LONGEST);
 817         }
 818         /*
 819          * Return the new block number, if any.
 820          * If there is one, give back a record value and a cursor too.
 821          */
 822         *bnop = nbno;
 823         if (nbno != NULLAGBLOCK) {
 824                 *recp = nrec; /* INT_: struct copy */
 825                 *curp = ncur; /* INT_: struct copy */
 826         }
 827         *stat = 1;
 828         return 0;
 829 }
 830
 831 /*
 832  * Log header fields from a btree block.
 833  */
 834 STATIC void
 835 xfs_alloc_log_block(
 836         xfs_trans_t             *tp,    /* transaction pointer */
 837         xfs_buf_t               *bp,    /* buffer containing btree block */
 838         int                     fields) /* mask of fields: XFS_BB_... */
 839 {
 840         int                     first;  /* first byte offset logged */
 841         int                     last;   /* last byte offset logged */
 842         static const short      offsets[] = {   /* table of offsets */
 843                 offsetof(xfs_alloc_block_t, bb_magic),
 844                 offsetof(xfs_alloc_block_t, bb_level),
 845                 offsetof(xfs_alloc_block_t, bb_numrecs),
 846                 offsetof(xfs_alloc_block_t, bb_leftsib),
 847                 offsetof(xfs_alloc_block_t, bb_rightsib),
 848                 sizeof(xfs_alloc_block_t)
 849         };
 850
 851         xfs_btree_offsets(fields, offsets, XFS_BB_NUM_BITS, &first, &last);
 852         xfs_trans_log_buf(tp, bp, first, last);
 853 }
 854
 855 /*
 856  * Log keys from a btree block (nonleaf).
 857  */
 858 STATIC void
 859 xfs_alloc_log_keys(
 860         xfs_btree_cur_t         *cur,   /* btree cursor */
 861         xfs_buf_t               *bp,    /* buffer containing btree block */
 862         int                     kfirst, /* index of first key to log */
 863         int                     klast)  /* index of last key to log */
 864 {
 865         xfs_alloc_block_t       *block; /* btree block to log from */
 866         int                     first;  /* first byte offset logged */
 867         xfs_alloc_key_t         *kp;    /* key pointer in btree block */
 868         int                     last;   /* last byte offset logged */
 869
 870         block = XFS_BUF_TO_ALLOC_BLOCK(bp);
 871         kp = XFS_ALLOC_KEY_ADDR(block, 1, cur);
 872         first = (int)((xfs_caddr_t)&kp[kfirst - 1] - (xfs_caddr_t)block);
 873         last = (int)(((xfs_caddr_t)&kp[klast] - 1) - (xfs_caddr_t)block);
 874         xfs_trans_log_buf(cur->bc_tp, bp, first, last);
 875 }
 876
 877 /*
 878  * Log block pointer fields from a btree block (nonleaf).
 879  */
 880 STATIC void
 881 xfs_alloc_log_ptrs(
 882         xfs_btree_cur_t         *cur,   /* btree cursor */
 883         xfs_buf_t               *bp,    /* buffer containing btree block */
 884         int                     pfirst, /* index of first pointer to log */
 885         int                     plast)  /* index of last pointer to log */
 886 {
 887         xfs_alloc_block_t       *block; /* btree block to log from */
 888         int                     first;  /* first byte offset logged */
 889         int                     last;   /* last byte offset logged */
 890         xfs_alloc_ptr_t         *pp;    /* block-pointer pointer in btree blk */
 891
 892         block = XFS_BUF_TO_ALLOC_BLOCK(bp);
 893         pp = XFS_ALLOC_PTR_ADDR(block, 1, cur);
 894         first = (int)((xfs_caddr_t)&pp[pfirst - 1] - (xfs_caddr_t)block);
 895         last = (int)(((xfs_caddr_t)&pp[plast] - 1) - (xfs_caddr_t)block);
 896         xfs_trans_log_buf(cur->bc_tp, bp, first, last);
 897 }
 898
 899 /*
 900  * Log records from a btree block (leaf).
 901  */
 902 STATIC void
 903 xfs_alloc_log_recs(
 904         xfs_btree_cur_t         *cur,   /* btree cursor */
 905         xfs_buf_t               *bp,    /* buffer containing btree block */
 906         int                     rfirst, /* index of first record to log */
 907         int                     rlast)  /* index of last record to log */
 908 {
 909         xfs_alloc_block_t       *block; /* btree block to log from */
 910         int                     first;  /* first byte offset logged */
 911         int                     last;   /* last byte offset logged */
 912         xfs_alloc_rec_t         *rp;    /* record pointer for btree block */
 913
 914
 915         block = XFS_BUF_TO_ALLOC_BLOCK(bp);
 916         rp = XFS_ALLOC_REC_ADDR(block, 1, cur);
 917 #ifdef DEBUG
 918         {
 919                 xfs_agf_t       *agf;
 920                 xfs_alloc_rec_t *p;
 921
 922                 agf = XFS_BUF_TO_AGF(cur->bc_private.a.agbp);
 923                 for (p = &rp[rfirst - 1]; p <= &rp[rlast - 1]; p++)
 924                         ASSERT(be32_to_cpu(p->ar_startblock) +
 925                                be32_to_cpu(p->ar_blockcount) <=
 926                                be32_to_cpu(agf->agf_length));
 927         }
 928 #endif
 929         first = (int)((xfs_caddr_t)&rp[rfirst - 1] - (xfs_caddr_t)block);
 930         last = (int)(((xfs_caddr_t)&rp[rlast] - 1) - (xfs_caddr_t)block);
 931         xfs_trans_log_buf(cur->bc_tp, bp, first, last);
 932 }
 933
 934 /*
 935  * Lookup the record.  The cursor is made to point to it, based on dir.
 936  * Return 0 if can't find any such record, 1 for success.
 937  */
 938 STATIC int                              /* error */
 939 xfs_alloc_lookup(
 940         xfs_btree_cur_t         *cur,   /* btree cursor */
 941         xfs_lookup_t            dir,    /* <=, ==, or >= */
 942         int                     *stat)  /* success/failure */
 943 {
 944         xfs_agblock_t           agbno;  /* a.g. relative btree block number */
 945         xfs_agnumber_t          agno;   /* allocation group number */
 946         xfs_alloc_block_t       *block=NULL;    /* current btree block */
 947         int                     diff;   /* difference for the current key */
 948         int                     error;  /* error return value */
 949         int                     keyno=0;        /* current key number */
 950         int                     level;  /* level in the btree */
 951         xfs_mount_t             *mp;    /* file system mount point */
 952
 953         XFS_STATS_INC(xs_abt_lookup);
 954         /*
 955          * Get the allocation group header, and the root block number.
 956          */
 957         mp = cur->bc_mp;
 958
 959         {
 960                 xfs_agf_t       *agf;   /* a.g. freespace header */
 961
 962                 agf = XFS_BUF_TO_AGF(cur->bc_private.a.agbp);
 963                 agno = be32_to_cpu(agf->agf_seqno);
 964                 agbno = be32_to_cpu(agf->agf_roots[cur->bc_btnum]);
 965         }
 966         /*
 967          * Iterate over each level in the btree, starting at the root.
 968          * For each level above the leaves, find the key we need, based
 969          * on the lookup record, then follow the corresponding block
 970          * pointer down to the next level.
 971          */
 972         for (level = cur->bc_nlevels - 1, diff = 1; level >= 0; level--) {
 973                 xfs_buf_t       *bp;    /* buffer pointer for btree block */
 974                 xfs_daddr_t     d;      /* disk address of btree block */
 975
 976                 /*
 977                  * Get the disk address we're looking for.
 978                  */
 979                 d = XFS_AGB_TO_DADDR(mp, agno, agbno);
 980                 /*
 981                  * If the old buffer at this level is for a different block,
 982                  * throw it away, otherwise just use it.
 983                  */
 984                 bp = cur->bc_bufs[level];
 985                 if (bp && XFS_BUF_ADDR(bp) != d)
 986                         bp = (xfs_buf_t *)0;
 987                 if (!bp) {
 988                         /*
 989                          * Need to get a new buffer.  Read it, then
 990                          * set it in the cursor, releasing the old one.
 991                          */
 992                         if ((error = xfs_btree_read_bufs(mp, cur->bc_tp, agno,
 993                                         agbno, 0, &bp, XFS_ALLOC_BTREE_REF)))
 994                                 return error;
 995                         xfs_btree_setbuf(cur, level, bp);
 996                         /*
 997                          * Point to the btree block, now that we have the buffer
 998                          */
 999                         block = XFS_BUF_TO_ALLOC_BLOCK(bp);
1000                         if ((error = xfs_btree_check_sblock(cur, block, level,
1001                                         bp)))
1002                                 return error;
1003                 } else
1004                         block = XFS_BUF_TO_ALLOC_BLOCK(bp);
1005                 /*
1006                  * If we already had a key match at a higher level, we know
1007                  * we need to use the first entry in this block.
1008                  */
1009                 if (diff == 0)
1010                         keyno = 1;
1011                 /*
1012                  * Otherwise we need to search this block.  Do a binary search.
1013                  */
1014                 else {
1015                         int             high;   /* high entry number */
1016                         xfs_alloc_key_t *kkbase=NULL;/* base of keys in block */
1017                         xfs_alloc_rec_t *krbase=NULL;/* base of records in block */
1018                         int             low;    /* low entry number */
1019
1020                         /*
1021                          * Get a pointer to keys or records.
1022                          */
1023                         if (level > 0)
1024                                 kkbase = XFS_ALLOC_KEY_ADDR(block, 1, cur);
1025                         else
1026                                 krbase = XFS_ALLOC_REC_ADDR(block, 1, cur);
1027                         /*
1028                          * Set low and high entry numbers, 1-based.
1029                          */
1030                         low = 1;
1031                         if (!(high = be16_to_cpu(block->bb_numrecs))) {
1032                                 /*
1033                                  * If the block is empty, the tree must
1034                                  * be an empty leaf.
1035                                  */
1036                                 ASSERT(level == 0 && cur->bc_nlevels == 1);
1037                                 cur->bc_ptrs[0] = dir != XFS_LOOKUP_LE;
1038                                 *stat = 0;
1039                                 return 0;
1040                         }
1041                         /*
1042                          * Binary search the block.
1043                          */
1044                         while (low <= high) {
1045                                 xfs_extlen_t    blockcount;     /* key value */
1046                                 xfs_agblock_t   startblock;     /* key value */
1047
1048                                 XFS_STATS_INC(xs_abt_compare);
1049                                 /*
1050                                  * keyno is average of low and high.
1051                                  */
1052                                 keyno = (low + high) >> 1;
1053                                 /*
1054                                  * Get startblock & blockcount.
1055                                  */
1056                                 if (level > 0) {
1057                                         xfs_alloc_key_t *kkp;
1058
1059                                         kkp = kkbase + keyno - 1;
1060                                         startblock = be32_to_cpu(kkp->ar_startblock);
1061                                         blockcount = be32_to_cpu(kkp->ar_blockcount);
1062                                 } else {
1063                                         xfs_alloc_rec_t *krp;
1064
1065                                         krp = krbase + keyno - 1;
1066                                         startblock = be32_to_cpu(krp->ar_startblock);
1067                                         blockcount = be32_to_cpu(krp->ar_blockcount);
1068                                 }
1069                                 /*
1070                                  * Compute difference to get next direction.
1071                                  */
1072                                 if (cur->bc_btnum == XFS_BTNUM_BNO)
1073                                         diff = (int)startblock -
1074                                                (int)cur->bc_rec.a.ar_startblock;
1075                                 else if (!(diff = (int)blockcount -
1076                                             (int)cur->bc_rec.a.ar_blockcount))
1077                                         diff = (int)startblock -
1078                                             (int)cur->bc_rec.a.ar_startblock;
1079                                 /*
1080                                  * Less than, move right.
1081                                  */
1082                                 if (diff < 0)
1083                                         low = keyno + 1;
1084                                 /*
1085                                  * Greater than, move left.
1086                                  */
1087                                 else if (diff > 0)
1088                                         high = keyno - 1;
1089                                 /*
1090                                  * Equal, we're done.
1091                                  */
1092                                 else
1093                                         break;
1094                         }
1095                 }
1096                 /*
1097                  * If there are more levels, set up for the next level
1098                  * by getting the block number and filling in the cursor.
1099                  */
1100                 if (level > 0) {
1101                         /*
1102                          * If we moved left, need the previous key number,
1103                          * unless there isn't one.
1104                          */
1105                         if (diff > 0 && --keyno < 1)
1106                                 keyno = 1;
1107                         agbno = be32_to_cpu(*XFS_ALLOC_PTR_ADDR(block, keyno, cur));
1108 #ifdef DEBUG
1109                         if ((error = xfs_btree_check_sptr(cur, agbno, level)))
1110                                 return error;
1111 #endif
1112                         cur->bc_ptrs[level] = keyno;
1113                 }
1114         }
1115         /*
1116          * Done with the search.
1117          * See if we need to adjust the results.
1118          */
1119         if (dir != XFS_LOOKUP_LE && diff < 0) {
1120                 keyno++;
1121                 /*
1122                  * If ge search and we went off the end of the block, but it's
1123                  * not the last block, we're in the wrong block.
1124                  */
1125                 if (dir == XFS_LOOKUP_GE &&
1126                     keyno > be16_to_cpu(block->bb_numrecs) &&
1127                     be32_to_cpu(block->bb_rightsib) != NULLAGBLOCK) {
1128                         int     i;
1129
1130                         cur->bc_ptrs[0] = keyno;
1131                         if ((error = xfs_alloc_increment(cur, 0, &i)))
1132                                 return error;
1133                         XFS_WANT_CORRUPTED_RETURN(i == 1);
1134                         *stat = 1;
1135                         return 0;
1136                 }
1137         }
1138         else if (dir == XFS_LOOKUP_LE && diff > 0)
1139                 keyno--;
1140         cur->bc_ptrs[0] = keyno;
1141         /*
1142          * Return if we succeeded or not.
1143          */
1144         if (keyno == 0 || keyno > be16_to_cpu(block->bb_numrecs))
1145                 *stat = 0;
1146         else
1147                 *stat = ((dir != XFS_LOOKUP_EQ) || (diff == 0));
1148         return 0;
1149 }
1150
1151 /*
1152  * Move 1 record left from cur/level if possible.
1153  * Update cur to reflect the new path.
1154  */
1155 STATIC int                              /* error */
1156 xfs_alloc_lshift(
1157         xfs_btree_cur_t         *cur,   /* btree cursor */
1158         int                     level,  /* level to shift record on */
1159         int                     *stat)  /* success/failure */
1160 {
1161         int                     error;  /* error return value */
1162 #ifdef DEBUG
1163         int                     i;      /* loop index */
1164 #endif
1165         xfs_alloc_key_t         key;    /* key value for leaf level upward */
1166         xfs_buf_t               *lbp;   /* buffer for left neighbor block */
1167         xfs_alloc_block_t       *left;  /* left neighbor btree block */
1168         int                     nrec;   /* new number of left block entries */
1169         xfs_buf_t               *rbp;   /* buffer for right (current) block */
1170         xfs_alloc_block_t       *right; /* right (current) btree block */
1171         xfs_alloc_key_t         *rkp=NULL;      /* key pointer for right block */
1172         xfs_alloc_ptr_t         *rpp=NULL;      /* address pointer for right block */
1173         xfs_alloc_rec_t         *rrp=NULL;      /* record pointer for right block */
1174
1175         /*
1176          * Set up variables for this block as "right".
1177          */
1178         rbp = cur->bc_bufs[level];
1179         right = XFS_BUF_TO_ALLOC_BLOCK(rbp);
1180 #ifdef DEBUG
1181         if ((error = xfs_btree_check_sblock(cur, right, level, rbp)))
1182                 return error;
1183 #endif
1184         /*
1185          * If we've got no left sibling then we can't shift an entry left.
1186          */
1187         if (be32_to_cpu(right->bb_leftsib) == NULLAGBLOCK) {
1188                 *stat = 0;
1189                 return 0;
1190         }
1191         /*
1192          * If the cursor entry is the one that would be moved, don't
1193          * do it... it's too complicated.
1194          */
1195         if (cur->bc_ptrs[level] <= 1) {
1196                 *stat = 0;
1197                 return 0;
1198         }
1199         /*
1200          * Set up the left neighbor as "left".
1201          */
1202         if ((error = xfs_btree_read_bufs(cur->bc_mp, cur->bc_tp,
1203                         cur->bc_private.a.agno, be32_to_cpu(right->bb_leftsib),
1204                         0, &lbp, XFS_ALLOC_BTREE_REF)))
1205                 return error;
1206         left = XFS_BUF_TO_ALLOC_BLOCK(lbp);
1207         if ((error = xfs_btree_check_sblock(cur, left, level, lbp)))
1208                 return error;
1209         /*
1210          * If it's full, it can't take another entry.
1211          */
1212         if (be16_to_cpu(left->bb_numrecs) == XFS_ALLOC_BLOCK_MAXRECS(level, cur)) {
1213                 *stat = 0;
1214                 return 0;
1215         }
1216         nrec = be16_to_cpu(left->bb_numrecs) + 1;
1217         /*
1218          * If non-leaf, copy a key and a ptr to the left block.
1219          */
1220         if (level > 0) {
1221                 xfs_alloc_key_t *lkp;   /* key pointer for left block */
1222                 xfs_alloc_ptr_t *lpp;   /* address pointer for left block */
1223
1224                 lkp = XFS_ALLOC_KEY_ADDR(left, nrec, cur);
1225                 rkp = XFS_ALLOC_KEY_ADDR(right, 1, cur);
1226                 *lkp = *rkp;
1227                 xfs_alloc_log_keys(cur, lbp, nrec, nrec);
1228                 lpp = XFS_ALLOC_PTR_ADDR(left, nrec, cur);
1229                 rpp = XFS_ALLOC_PTR_ADDR(right, 1, cur);
1230 #ifdef DEBUG
1231                 if ((error = xfs_btree_check_sptr(cur, be32_to_cpu(*rpp), level)))
1232                         return error;
1233 #endif
1234                 *lpp = *rpp; /* INT_: copy */
1235                 xfs_alloc_log_ptrs(cur, lbp, nrec, nrec);
1236                 xfs_btree_check_key(cur->bc_btnum, lkp - 1, lkp);
1237         }
1238         /*
1239          * If leaf, copy a record to the left block.
1240          */
1241         else {
1242                 xfs_alloc_rec_t *lrp;   /* record pointer for left block */
1243
1244                 lrp = XFS_ALLOC_REC_ADDR(left, nrec, cur);
1245                 rrp = XFS_ALLOC_REC_ADDR(right, 1, cur);
1246                 *lrp = *rrp;
1247                 xfs_alloc_log_recs(cur, lbp, nrec, nrec);
1248                 xfs_btree_check_rec(cur->bc_btnum, lrp - 1, lrp);
1249         }
1250         /*
1251          * Bump and log left's numrecs, decrement and log right's numrecs.
1252          */
1253         be16_add(&left->bb_numrecs, 1);
1254         xfs_alloc_log_block(cur->bc_tp, lbp, XFS_BB_NUMRECS);
1255         be16_add(&right->bb_numrecs, -1);
1256         xfs_alloc_log_block(cur->bc_tp, rbp, XFS_BB_NUMRECS);
1257         /*
1258          * Slide the contents of right down one entry.
1259          */
1260         if (level > 0) {
1261 #ifdef DEBUG
1262                 for (i = 0; i < be16_to_cpu(right->bb_numrecs); i++) {
1263                         if ((error = xfs_btree_check_sptr(cur, be32_to_cpu(rpp[i + 1]),
1264                                         level)))
1265                                 return error;
1266                 }
1267 #endif
1268                 memmove(rkp, rkp + 1, be16_to_cpu(right->bb_numrecs) * sizeof(*rkp));
1269                 memmove(rpp, rpp + 1, be16_to_cpu(right->bb_numrecs) * sizeof(*rpp));
1270                 xfs_alloc_log_keys(cur, rbp, 1, be16_to_cpu(right->bb_numrecs));
1271                 xfs_alloc_log_ptrs(cur, rbp, 1, be16_to_cpu(right->bb_numrecs));
1272         } else {
1273                 memmove(rrp, rrp + 1, be16_to_cpu(right->bb_numrecs) * sizeof(*rrp));
1274                 xfs_alloc_log_recs(cur, rbp, 1, be16_to_cpu(right->bb_numrecs));
1275                 key.ar_startblock = rrp->ar_startblock;
1276                 key.ar_blockcount = rrp->ar_blockcount;
1277                 rkp = &key;
1278         }
1279         /*
1280          * Update the parent key values of right.
1281          */
1282         if ((error = xfs_alloc_updkey(cur, rkp, level + 1)))
1283                 return error;
1284         /*
1285          * Slide the cursor value left one.
1286          */
1287         cur->bc_ptrs[level]--;
1288         *stat = 1;
1289         return 0;
1290 }
1291
1292 /*
1293  * Allocate a new root block, fill it in.
1294  */
1295 STATIC int                              /* error */
1296 xfs_alloc_newroot(
1297         xfs_btree_cur_t         *cur,   /* btree cursor */
1298         int                     *stat)  /* success/failure */
1299 {
1300         int                     error;  /* error return value */
1301         xfs_agblock_t           lbno;   /* left block number */
1302         xfs_buf_t               *lbp;   /* left btree buffer */
1303         xfs_alloc_block_t       *left;  /* left btree block */
1304         xfs_mount_t             *mp;    /* mount structure */
1305         xfs_agblock_t           nbno;   /* new block number */
1306         xfs_buf_t               *nbp;   /* new (root) buffer */
1307         xfs_alloc_block_t       *new;   /* new (root) btree block */
1308         int                     nptr;   /* new value for key index, 1 or 2 */
1309         xfs_agblock_t           rbno;   /* right block number */
1310         xfs_buf_t               *rbp;   /* right btree buffer */
1311         xfs_alloc_block_t       *right; /* right btree block */
1312
1313         mp = cur->bc_mp;
1314
1315         ASSERT(cur->bc_nlevels < XFS_AG_MAXLEVELS(mp));
1316         /*
1317          * Get a buffer from the freelist blocks, for the new root.
1318          */
1319         if ((error = xfs_alloc_get_freelist(cur->bc_tp, cur->bc_private.a.agbp,
1320                         &nbno)))
1321                 return error;
1322         /*
1323          * None available, we fail.
1324          */
1325         if (nbno == NULLAGBLOCK) {
1326                 *stat = 0;
1327                 return 0;
1328         }
1329         xfs_trans_agbtree_delta(cur->bc_tp, 1);
1330         nbp = xfs_btree_get_bufs(mp, cur->bc_tp, cur->bc_private.a.agno, nbno,
1331                 0);
1332         new = XFS_BUF_TO_ALLOC_BLOCK(nbp);
1333         /*
1334          * Set the root data in the a.g. freespace structure.
1335          */
1336         {
1337                 xfs_agf_t       *agf;   /* a.g. freespace header */
1338                 xfs_agnumber_t  seqno;
1339
1340                 agf = XFS_BUF_TO_AGF(cur->bc_private.a.agbp);
1341                 agf->agf_roots[cur->bc_btnum] = cpu_to_be32(nbno);
1342                 be32_add(&agf->agf_levels[cur->bc_btnum], 1);
1343                 seqno = be32_to_cpu(agf->agf_seqno);
1344                 mp->m_perag[seqno].pagf_levels[cur->bc_btnum]++;
1345                 xfs_alloc_log_agf(cur->bc_tp, cur->bc_private.a.agbp,
1346                         XFS_AGF_ROOTS | XFS_AGF_LEVELS);
1347         }
1348         /*
1349          * At the previous root level there are now two blocks: the old
1350          * root, and the new block generated when it was split.
1351          * We don't know which one the cursor is pointing at, so we
1352          * set up variables "left" and "right" for each case.
1353          */
1354         lbp = cur->bc_bufs[cur->bc_nlevels - 1];
1355         left = XFS_BUF_TO_ALLOC_BLOCK(lbp);
1356 #ifdef DEBUG
1357         if ((error = xfs_btree_check_sblock(cur, left, cur->bc_nlevels - 1, lbp)))
1358                 return error;
1359 #endif
1360         if (be32_to_cpu(left->bb_rightsib) != NULLAGBLOCK) {
1361                 /*
1362                  * Our block is left, pick up the right block.
1363                  */
1364                 lbno = XFS_DADDR_TO_AGBNO(mp, XFS_BUF_ADDR(lbp));
1365                 rbno = be32_to_cpu(left->bb_rightsib);
1366                 if ((error = xfs_btree_read_bufs(mp, cur->bc_tp,
1367                                 cur->bc_private.a.agno, rbno, 0, &rbp,
1368                                 XFS_ALLOC_BTREE_REF)))
1369                         return error;
1370                 right = XFS_BUF_TO_ALLOC_BLOCK(rbp);
1371                 if ((error = xfs_btree_check_sblock(cur, right,
1372                                 cur->bc_nlevels - 1, rbp)))
1373                         return error;
1374                 nptr = 1;
1375         } else {
1376                 /*
1377                  * Our block is right, pick up the left block.
1378                  */
1379                 rbp = lbp;
1380                 right = left;
1381                 rbno = XFS_DADDR_TO_AGBNO(mp, XFS_BUF_ADDR(rbp));
1382                 lbno = be32_to_cpu(right->bb_leftsib);
1383                 if ((error = xfs_btree_read_bufs(mp, cur->bc_tp,
1384                                 cur->bc_private.a.agno, lbno, 0, &lbp,
1385                                 XFS_ALLOC_BTREE_REF)))
1386                         return error;
1387                 left = XFS_BUF_TO_ALLOC_BLOCK(lbp);
1388                 if ((error = xfs_btree_check_sblock(cur, left,
1389                                 cur->bc_nlevels - 1, lbp)))
1390                         return error;
1391                 nptr = 2;
1392         }
1393         /*
1394          * Fill in the new block's btree header and log it.
1395          */
1396         new->bb_magic = cpu_to_be32(xfs_magics[cur->bc_btnum]);
1397         new->bb_level = cpu_to_be16(cur->bc_nlevels);
1398         new->bb_numrecs = cpu_to_be16(2);
1399         new->bb_leftsib = cpu_to_be32(NULLAGBLOCK);
1400         new->bb_rightsib = cpu_to_be32(NULLAGBLOCK);
1401         xfs_alloc_log_block(cur->bc_tp, nbp, XFS_BB_ALL_BITS);
1402         ASSERT(lbno != NULLAGBLOCK && rbno != NULLAGBLOCK);
1403         /*
1404          * Fill in the key data in the new root.
1405          */
1406         {
1407                 xfs_alloc_key_t         *kp;    /* btree key pointer */
1408
1409                 kp = XFS_ALLOC_KEY_ADDR(new, 1, cur);
1410                 if (be16_to_cpu(left->bb_level) > 0) {
1411                         kp[0] = *XFS_ALLOC_KEY_ADDR(left, 1, cur); /* INT_: structure copy */
1412                         kp[1] = *XFS_ALLOC_KEY_ADDR(right, 1, cur);/* INT_: structure copy */
1413                 } else {
1414                         xfs_alloc_rec_t *rp;    /* btree record pointer */
1415
1416                         rp = XFS_ALLOC_REC_ADDR(left, 1, cur);
1417                         kp[0].ar_startblock = rp->ar_startblock;
1418                         kp[0].ar_blockcount = rp->ar_blockcount;
1419                         rp = XFS_ALLOC_REC_ADDR(right, 1, cur);
1420                         kp[1].ar_startblock = rp->ar_startblock;
1421                         kp[1].ar_blockcount = rp->ar_blockcount;
1422                 }
1423         }
1424         xfs_alloc_log_keys(cur, nbp, 1, 2);
1425         /*
1426          * Fill in the pointer data in the new root.
1427          */
1428         {
1429                 xfs_alloc_ptr_t         *pp;    /* btree address pointer */
1430
1431                 pp = XFS_ALLOC_PTR_ADDR(new, 1, cur);
1432                 pp[0] = cpu_to_be32(lbno);
1433                 pp[1] = cpu_to_be32(rbno);
1434         }
1435         xfs_alloc_log_ptrs(cur, nbp, 1, 2);
1436         /*
1437          * Fix up the cursor.
1438          */
1439         xfs_btree_setbuf(cur, cur->bc_nlevels, nbp);
1440         cur->bc_ptrs[cur->bc_nlevels] = nptr;
1441         cur->bc_nlevels++;
1442         *stat = 1;
1443         return 0;
1444 }
1445
1446 /*
1447  * Move 1 record right from cur/level if possible.
1448  * Update cur to reflect the new path.
1449  */
1450 STATIC int                              /* error */
1451 xfs_alloc_rshift(
1452         xfs_btree_cur_t         *cur,   /* btree cursor */
1453         int                     level,  /* level to shift record on */
1454         int                     *stat)  /* success/failure */
1455 {
1456         int                     error;  /* error return value */
1457         int                     i;      /* loop index */
1458         xfs_alloc_key_t         key;    /* key value for leaf level upward */
1459         xfs_buf_t               *lbp;   /* buffer for left (current) block */
1460         xfs_alloc_block_t       *left;  /* left (current) btree block */
1461         xfs_buf_t               *rbp;   /* buffer for right neighbor block */
1462         xfs_alloc_block_t       *right; /* right neighbor btree block */
1463         xfs_alloc_key_t         *rkp;   /* key pointer for right block */
1464         xfs_btree_cur_t         *tcur;  /* temporary cursor */
1465
1466         /*
1467          * Set up variables for this block as "left".
1468          */
1469         lbp = cur->bc_bufs[level];
1470         left = XFS_BUF_TO_ALLOC_BLOCK(lbp);
1471 #ifdef DEBUG
1472         if ((error = xfs_btree_check_sblock(cur, left, level, lbp)))
1473                 return error;
1474 #endif
1475         /*
1476          * If we've got no right sibling then we can't shift an entry right.
1477          */
1478         if (be32_to_cpu(left->bb_rightsib) == NULLAGBLOCK) {
1479                 *stat = 0;
1480                 return 0;
1481         }
1482         /*
1483          * If the cursor entry is the one that would be moved, don't
1484          * do it... it's too complicated.
1485          */
1486         if (cur->bc_ptrs[level] >= be16_to_cpu(left->bb_numrecs)) {
1487                 *stat = 0;
1488                 return 0;
1489         }
1490         /*
1491          * Set up the right neighbor as "right".
1492          */
1493         if ((error = xfs_btree_read_bufs(cur->bc_mp, cur->bc_tp,
1494                         cur->bc_private.a.agno, be32_to_cpu(left->bb_rightsib),
1495                         0, &rbp, XFS_ALLOC_BTREE_REF)))
1496                 return error;
1497         right = XFS_BUF_TO_ALLOC_BLOCK(rbp);
1498         if ((error = xfs_btree_check_sblock(cur, right, level, rbp)))
1499                 return error;
1500         /*
1501          * If it's full, it can't take another entry.
1502          */
1503         if (be16_to_cpu(right->bb_numrecs) == XFS_ALLOC_BLOCK_MAXRECS(level, cur)) {
1504                 *stat = 0;
1505                 return 0;
1506         }
1507         /*
1508          * Make a hole at the start of the right neighbor block, then
1509          * copy the last left block entry to the hole.
1510          */
1511         if (level > 0) {
1512                 xfs_alloc_key_t *lkp;   /* key pointer for left block */
1513                 xfs_alloc_ptr_t *lpp;   /* address pointer for left block */
1514                 xfs_alloc_ptr_t *rpp;   /* address pointer for right block */
1515
1516                 lkp = XFS_ALLOC_KEY_ADDR(left, be16_to_cpu(left->bb_numrecs), cur);
1517                 lpp = XFS_ALLOC_PTR_ADDR(left, be16_to_cpu(left->bb_numrecs), cur);
1518                 rkp = XFS_ALLOC_KEY_ADDR(right, 1, cur);
1519                 rpp = XFS_ALLOC_PTR_ADDR(right, 1, cur);
1520 #ifdef DEBUG
1521                 for (i = be16_to_cpu(right->bb_numrecs) - 1; i >= 0; i--) {
1522                         if ((error = xfs_btree_check_sptr(cur, be32_to_cpu(rpp[i]), level)))
1523                                 return error;
1524                 }
1525 #endif
1526                 memmove(rkp + 1, rkp, be16_to_cpu(right->bb_numrecs) * sizeof(*rkp));
1527                 memmove(rpp + 1, rpp, be16_to_cpu(right->bb_numrecs) * sizeof(*rpp));
1528 #ifdef DEBUG
1529                 if ((error = xfs_btree_check_sptr(cur, be32_to_cpu(*lpp), level)))
1530                         return error;
1531 #endif
1532                 *rkp = *lkp; /* INT_: copy */
1533                 *rpp = *lpp; /* INT_: copy */
1534                 xfs_alloc_log_keys(cur, rbp, 1, be16_to_cpu(right->bb_numrecs) + 1);
1535                 xfs_alloc_log_ptrs(cur, rbp, 1, be16_to_cpu(right->bb_numrecs) + 1);
1536                 xfs_btree_check_key(cur->bc_btnum, rkp, rkp + 1);
1537         } else {
1538                 xfs_alloc_rec_t *lrp;   /* record pointer for left block */
1539                 xfs_alloc_rec_t *rrp;   /* record pointer for right block */
1540
1541                 lrp = XFS_ALLOC_REC_ADDR(left, be16_to_cpu(left->bb_numrecs), cur);
1542                 rrp = XFS_ALLOC_REC_ADDR(right, 1, cur);
1543                 memmove(rrp + 1, rrp, be16_to_cpu(right->bb_numrecs) * sizeof(*rrp));
1544                 *rrp = *lrp;
1545                 xfs_alloc_log_recs(cur, rbp, 1, be16_to_cpu(right->bb_numrecs) + 1);
1546                 key.ar_startblock = rrp->ar_startblock;
1547                 key.ar_blockcount = rrp->ar_blockcount;
1548                 rkp = &key;
1549                 xfs_btree_check_rec(cur->bc_btnum, rrp, rrp + 1);
1550         }
1551         /*
1552          * Decrement and log left's numrecs, bump and log right's numrecs.
1553          */
1554         be16_add(&left->bb_numrecs, -1);
1555         xfs_alloc_log_block(cur->bc_tp, lbp, XFS_BB_NUMRECS);
1556         be16_add(&right->bb_numrecs, 1);
1557         xfs_alloc_log_block(cur->bc_tp, rbp, XFS_BB_NUMRECS);
1558         /*
1559          * Using a temporary cursor, update the parent key values of the
1560          * block on the right.
1561          */
1562         if ((error = xfs_btree_dup_cursor(cur, &tcur)))
1563                 return error;
1564         i = xfs_btree_lastrec(tcur, level);
1565         XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1566         if ((error = xfs_alloc_increment(tcur, level, &i)) ||
1567             (error = xfs_alloc_updkey(tcur, rkp, level + 1)))
1568                 goto error0;
1569         xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
1570         *stat = 1;
1571         return 0;
1572 error0:
1573         xfs_btree_del_cursor(tcur, XFS_BTREE_ERROR);
1574         return error;
1575 }
1576
1577 /*
1578  * Split cur/level block in half.
1579  * Return new block number and its first record (to be inserted into parent).
1580  */
1581 STATIC int                              /* error */
1582 xfs_alloc_split(
1583         xfs_btree_cur_t         *cur,   /* btree cursor */
1584         int                     level,  /* level to split */
1585         xfs_agblock_t           *bnop,  /* output: block number allocated */
1586         xfs_alloc_key_t         *keyp,  /* output: first key of new block */
1587         xfs_btree_cur_t         **curp, /* output: new cursor */
1588         int                     *stat)  /* success/failure */
1589 {
1590         int                     error;  /* error return value */
1591         int                     i;      /* loop index/record number */
1592         xfs_agblock_t           lbno;   /* left (current) block number */
1593         xfs_buf_t               *lbp;   /* buffer for left block */
1594         xfs_alloc_block_t       *left;  /* left (current) btree block */
1595         xfs_agblock_t           rbno;   /* right (new) block number */
1596         xfs_buf_t               *rbp;   /* buffer for right block */
1597         xfs_alloc_block_t       *right; /* right (new) btree block */
1598
1599         /*
1600          * Allocate the new block from the freelist.
1601          * If we can't do it, we're toast.  Give up.
1602          */
1603         if ((error = xfs_alloc_get_freelist(cur->bc_tp, cur->bc_private.a.agbp,
1604                         &rbno)))
1605                 return error;
1606         if (rbno == NULLAGBLOCK) {
1607                 *stat = 0;
1608                 return 0;
1609         }
1610         xfs_trans_agbtree_delta(cur->bc_tp, 1);
1611         rbp = xfs_btree_get_bufs(cur->bc_mp, cur->bc_tp, cur->bc_private.a.agno,
1612                 rbno, 0);
1613         /*
1614          * Set up the new block as "right".
1615          */
1616         right = XFS_BUF_TO_ALLOC_BLOCK(rbp);
1617         /*
1618          * "Left" is the current (according to the cursor) block.
1619          */
1620         lbp = cur->bc_bufs[level];
1621         left = XFS_BUF_TO_ALLOC_BLOCK(lbp);
1622 #ifdef DEBUG
1623         if ((error = xfs_btree_check_sblock(cur, left, level, lbp)))
1624                 return error;
1625 #endif
1626         /*
1627          * Fill in the btree header for the new block.
1628          */
1629         right->bb_magic = cpu_to_be32(xfs_magics[cur->bc_btnum]);
1630         right->bb_level = left->bb_level;
1631         right->bb_numrecs = cpu_to_be16(be16_to_cpu(left->bb_numrecs) / 2);
1632         /*
1633          * Make sure that if there's an odd number of entries now, that
1634          * each new block will have the same number of entries.
1635          */
1636         if ((be16_to_cpu(left->bb_numrecs) & 1) &&
1637             cur->bc_ptrs[level] <= be16_to_cpu(right->bb_numrecs) + 1)
1638                 be16_add(&right->bb_numrecs, 1);
1639         i = be16_to_cpu(left->bb_numrecs) - be16_to_cpu(right->bb_numrecs) + 1;
1640         /*
1641          * For non-leaf blocks, copy keys and addresses over to the new block.
1642          */
1643         if (level > 0) {
1644                 xfs_alloc_key_t *lkp;   /* left btree key pointer */
1645                 xfs_alloc_ptr_t *lpp;   /* left btree address pointer */
1646                 xfs_alloc_key_t *rkp;   /* right btree key pointer */
1647                 xfs_alloc_ptr_t *rpp;   /* right btree address pointer */
1648
1649                 lkp = XFS_ALLOC_KEY_ADDR(left, i, cur);
1650                 lpp = XFS_ALLOC_PTR_ADDR(left, i, cur);
1651                 rkp = XFS_ALLOC_KEY_ADDR(right, 1, cur);
1652                 rpp = XFS_ALLOC_PTR_ADDR(right, 1, cur);
1653 #ifdef DEBUG
1654                 for (i = 0; i < be16_to_cpu(right->bb_numrecs); i++) {
1655                         if ((error = xfs_btree_check_sptr(cur, be32_to_cpu(lpp[i]), level)))
1656                                 return error;
1657                 }
1658 #endif
1659                 memcpy(rkp, lkp, be16_to_cpu(right->bb_numrecs) * sizeof(*rkp));
1660                 memcpy(rpp, lpp, be16_to_cpu(right->bb_numrecs) * sizeof(*rpp));
1661                 xfs_alloc_log_keys(cur, rbp, 1, be16_to_cpu(right->bb_numrecs));
1662                 xfs_alloc_log_ptrs(cur, rbp, 1, be16_to_cpu(right->bb_numrecs));
1663                 *keyp = *rkp;
1664         }
1665         /*
1666          * For leaf blocks, copy records over to the new block.
1667          */
1668         else {
1669                 xfs_alloc_rec_t *lrp;   /* left btree record pointer */
1670                 xfs_alloc_rec_t *rrp;   /* right btree record pointer */
1671
1672                 lrp = XFS_ALLOC_REC_ADDR(left, i, cur);
1673                 rrp = XFS_ALLOC_REC_ADDR(right, 1, cur);
1674                 memcpy(rrp, lrp, be16_to_cpu(right->bb_numrecs) * sizeof(*rrp));
1675                 xfs_alloc_log_recs(cur, rbp, 1, be16_to_cpu(right->bb_numrecs));
1676                 keyp->ar_startblock = rrp->ar_startblock;
1677                 keyp->ar_blockcount = rrp->ar_blockcount;
1678         }
1679         /*
1680          * Find the left block number by looking in the buffer.
1681          * Adjust numrecs, sibling pointers.
1682          */
1683         lbno = XFS_DADDR_TO_AGBNO(cur->bc_mp, XFS_BUF_ADDR(lbp));
1684         be16_add(&left->bb_numrecs, -(be16_to_cpu(right->bb_numrecs)));
1685         right->bb_rightsib = left->bb_rightsib;
1686         left->bb_rightsib = cpu_to_be32(rbno);
1687         right->bb_leftsib = cpu_to_be32(lbno);
1688         xfs_alloc_log_block(cur->bc_tp, rbp, XFS_BB_ALL_BITS);
1689         xfs_alloc_log_block(cur->bc_tp, lbp, XFS_BB_NUMRECS | XFS_BB_RIGHTSIB);
1690         /*
1691          * If there's a block to the new block's right, make that block
1692          * point back to right instead of to left.
1693          */
1694         if (be32_to_cpu(right->bb_rightsib) != NULLAGBLOCK) {
1695                 xfs_alloc_block_t       *rrblock;       /* rr btree block */
1696                 xfs_buf_t               *rrbp;          /* buffer for rrblock */
1697
1698                 if ((error = xfs_btree_read_bufs(cur->bc_mp, cur->bc_tp,
1699                                 cur->bc_private.a.agno, be32_to_cpu(right->bb_rightsib), 0,
1700                                 &rrbp, XFS_ALLOC_BTREE_REF)))
1701                         return error;
1702                 rrblock = XFS_BUF_TO_ALLOC_BLOCK(rrbp);
1703                 if ((error = xfs_btree_check_sblock(cur, rrblock, level, rrbp)))
1704                         return error;
1705                 rrblock->bb_leftsib = cpu_to_be32(rbno);
1706                 xfs_alloc_log_block(cur->bc_tp, rrbp, XFS_BB_LEFTSIB);
1707         }
1708         /*
1709          * If the cursor is really in the right block, move it there.
1710          * If it's just pointing past the last entry in left, then we'll
1711          * insert there, so don't change anything in that case.
1712          */
1713         if (cur->bc_ptrs[level] > be16_to_cpu(left->bb_numrecs) + 1) {
1714                 xfs_btree_setbuf(cur, level, rbp);
1715                 cur->bc_ptrs[level] -= be16_to_cpu(left->bb_numrecs);
1716         }
1717         /*
1718          * If there are more levels, we'll need another cursor which refers to
1719          * the right block, no matter where this cursor was.
1720          */
1721         if (level + 1 < cur->bc_nlevels) {
1722                 if ((error = xfs_btree_dup_cursor(cur, curp)))
1723                         return error;
1724                 (*curp)->bc_ptrs[level + 1]++;
1725         }
1726         *bnop = rbno;
1727         *stat = 1;
1728         return 0;
1729 }
1730
1731 /*
1732  * Update keys at all levels from here to the root along the cursor's path.
1733  */
1734 STATIC int                              /* error */
1735 xfs_alloc_updkey(
1736         xfs_btree_cur_t         *cur,   /* btree cursor */
1737         xfs_alloc_key_t         *keyp,  /* new key value to update to */
1738         int                     level)  /* starting level for update */
1739 {
1740         int                     ptr;    /* index of key in block */
1741
1742         /*
1743          * Go up the tree from this level toward the root.
1744          * At each level, update the key value to the value input.
1745          * Stop when we reach a level where the cursor isn't pointing
1746          * at the first entry in the block.
1747          */
1748         for (ptr = 1; ptr == 1 && level < cur->bc_nlevels; level++) {
1749                 xfs_alloc_block_t       *block; /* btree block */
1750                 xfs_buf_t               *bp;    /* buffer for block */
1751 #ifdef DEBUG
1752                 int                     error;  /* error return value */
1753 #endif
1754                 xfs_alloc_key_t         *kp;    /* ptr to btree block keys */
1755
1756                 bp = cur->bc_bufs[level];
1757                 block = XFS_BUF_TO_ALLOC_BLOCK(bp);
1758 #ifdef DEBUG
1759                 if ((error = xfs_btree_check_sblock(cur, block, level, bp)))
1760                         return error;
1761 #endif
1762                 ptr = cur->bc_ptrs[level];
1763                 kp = XFS_ALLOC_KEY_ADDR(block, ptr, cur);
1764                 *kp = *keyp;
1765                 xfs_alloc_log_keys(cur, bp, ptr, ptr);
1766         }
1767         return 0;
1768 }
1769
1770 /*
1771  * Externally visible routines.
1772  */
1773
1774 /*
1775  * Decrement cursor by one record at the level.
1776  * For nonzero levels the leaf-ward information is untouched.
1777  */
1778 int                                     /* error */
1779 xfs_alloc_decrement(
1780         xfs_btree_cur_t         *cur,   /* btree cursor */
1781         int                     level,  /* level in btree, 0 is leaf */
1782         int                     *stat)  /* success/failure */
1783 {
1784         xfs_alloc_block_t       *block; /* btree block */
1785         int                     error;  /* error return value */
1786         int                     lev;    /* btree level */
1787
1788         ASSERT(level < cur->bc_nlevels);
1789         /*
1790          * Read-ahead to the left at this level.
1791          */
1792         xfs_btree_readahead(cur, level, XFS_BTCUR_LEFTRA);
1793         /*
1794          * Decrement the ptr at this level.  If we're still in the block
1795          * then we're done.
1796          */
1797         if (--cur->bc_ptrs[level] > 0) {
1798                 *stat = 1;
1799                 return 0;
1800         }
1801         /*
1802          * Get a pointer to the btree block.
1803          */
1804         block = XFS_BUF_TO_ALLOC_BLOCK(cur->bc_bufs[level]);
1805 #ifdef DEBUG
1806         if ((error = xfs_btree_check_sblock(cur, block, level,
1807                         cur->bc_bufs[level])))
1808                 return error;
1809 #endif
1810         /*
1811          * If we just went off the left edge of the tree, return failure.
1812          */
1813         if (be32_to_cpu(block->bb_leftsib) == NULLAGBLOCK) {
1814                 *stat = 0;
1815                 return 0;
1816         }
1817         /*
1818          * March up the tree decrementing pointers.
1819          * Stop when we don't go off the left edge of a block.
1820          */
1821         for (lev = level + 1; lev < cur->bc_nlevels; lev++) {
1822                 if (--cur->bc_ptrs[lev] > 0)
1823                         break;
1824                 /*
1825                  * Read-ahead the left block, we're going to read it
1826                  * in the next loop.
1827                  */
1828                 xfs_btree_readahead(cur, lev, XFS_BTCUR_LEFTRA);
1829         }
1830         /*
1831          * If we went off the root then we are seriously confused.
1832          */
1833         ASSERT(lev < cur->bc_nlevels);
1834         /*
1835          * Now walk back down the tree, fixing up the cursor's buffer
1836          * pointers and key numbers.
1837          */
1838         for (block = XFS_BUF_TO_ALLOC_BLOCK(cur->bc_bufs[lev]); lev > level; ) {
1839                 xfs_agblock_t   agbno;  /* block number of btree block */
1840                 xfs_buf_t       *bp;    /* buffer pointer for block */
1841
1842                 agbno = be32_to_cpu(*XFS_ALLOC_PTR_ADDR(block, cur->bc_ptrs[lev], cur));
1843                 if ((error = xfs_btree_read_bufs(cur->bc_mp, cur->bc_tp,
1844                                 cur->bc_private.a.agno, agbno, 0, &bp,
1845                                 XFS_ALLOC_BTREE_REF)))
1846                         return error;
1847                 lev--;
1848                 xfs_btree_setbuf(cur, lev, bp);
1849                 block = XFS_BUF_TO_ALLOC_BLOCK(bp);
1850                 if ((error = xfs_btree_check_sblock(cur, block, lev, bp)))
1851                         return error;
1852                 cur->bc_ptrs[lev] = be16_to_cpu(block->bb_numrecs);
1853         }
1854         *stat = 1;
1855         return 0;
1856 }
1857
1858 /*
1859  * Delete the record pointed to by cur.
1860  * The cursor refers to the place where the record was (could be inserted)
1861  * when the operation returns.
1862  */
1863 int                                     /* error */
1864 xfs_alloc_delete(
1865         xfs_btree_cur_t *cur,           /* btree cursor */
1866         int             *stat)          /* success/failure */
1867 {
1868         int             error;          /* error return value */
1869         int             i;              /* result code */
1870         int             level;          /* btree level */
1871
1872         /*
1873          * Go up the tree, starting at leaf level.
1874          * If 2 is returned then a join was done; go to the next level.
1875          * Otherwise we are done.
1876          */
1877         for (level = 0, i = 2; i == 2; level++) {
1878                 if ((error = xfs_alloc_delrec(cur, level, &i)))
1879                         return error;
1880         }
1881         if (i == 0) {
1882                 for (level = 1; level < cur->bc_nlevels; level++) {
1883                         if (cur->bc_ptrs[level] == 0) {
1884                                 if ((error = xfs_alloc_decrement(cur, level, &i)))
1885                                         return error;
1886                                 break;
1887                         }
1888                 }
1889         }
1890         *stat = i;
1891         return 0;
1892 }
1893
1894 /*
1895  * Get the data from the pointed-to record.
1896  */
1897 int                                     /* error */
1898 xfs_alloc_get_rec(
1899         xfs_btree_cur_t         *cur,   /* btree cursor */
1900         xfs_agblock_t           *bno,   /* output: starting block of extent */
1901         xfs_extlen_t            *len,   /* output: length of extent */
1902         int                     *stat)  /* output: success/failure */
1903 {
1904         xfs_alloc_block_t       *block; /* btree block */
1905 #ifdef DEBUG
1906         int                     error;  /* error return value */
1907 #endif
1908         int                     ptr;    /* record number */
1909
1910         ptr = cur->bc_ptrs[0];
1911         block = XFS_BUF_TO_ALLOC_BLOCK(cur->bc_bufs[0]);
1912 #ifdef DEBUG
1913         if ((error = xfs_btree_check_sblock(cur, block, 0, cur->bc_bufs[0])))
1914                 return error;
1915 #endif
1916         /*
1917          * Off the right end or left end, return failure.
1918          */
1919         if (ptr > be16_to_cpu(block->bb_numrecs) || ptr <= 0) {
1920                 *stat = 0;
1921                 return 0;
1922         }
1923         /*
1924          * Point to the record and extract its data.
1925          */
1926         {
1927                 xfs_alloc_rec_t         *rec;   /* record data */
1928
1929                 rec = XFS_ALLOC_REC_ADDR(block, ptr, cur);
1930                 *bno = be32_to_cpu(rec->ar_startblock);
1931                 *len = be32_to_cpu(rec->ar_blockcount);
1932         }
1933         *stat = 1;
1934         return 0;
1935 }
1936
1937 /*
1938  * Increment cursor by one record at the level.
1939  * For nonzero levels the leaf-ward information is untouched.
1940  */
1941 int                                     /* error */
1942 xfs_alloc_increment(
1943         xfs_btree_cur_t         *cur,   /* btree cursor */
1944         int                     level,  /* level in btree, 0 is leaf */
1945         int                     *stat)  /* success/failure */
1946 {
1947         xfs_alloc_block_t       *block; /* btree block */
1948         xfs_buf_t               *bp;    /* tree block buffer */
1949         int                     error;  /* error return value */
1950         int                     lev;    /* btree level */
1951
1952         ASSERT(level < cur->bc_nlevels);
1953         /*
1954          * Read-ahead to the right at this level.
1955          */
1956         xfs_btree_readahead(cur, level, XFS_BTCUR_RIGHTRA);
1957         /*
1958          * Get a pointer to the btree block.
1959          */
1960         bp = cur->bc_bufs[level];
1961         block = XFS_BUF_TO_ALLOC_BLOCK(bp);
1962 #ifdef DEBUG
1963         if ((error = xfs_btree_check_sblock(cur, block, level, bp)))
1964                 return error;
1965 #endif
1966         /*
1967          * Increment the ptr at this level.  If we're still in the block
1968          * then we're done.
1969          */
1970         if (++cur->bc_ptrs[level] <= be16_to_cpu(block->bb_numrecs)) {
1971                 *stat = 1;
1972                 return 0;
1973         }
1974         /*
1975          * If we just went off the right edge of the tree, return failure.
1976          */
1977         if (be32_to_cpu(block->bb_rightsib) == NULLAGBLOCK) {
1978                 *stat = 0;
1979                 return 0;
1980         }
1981         /*
1982          * March up the tree incrementing pointers.
1983          * Stop when we don't go off the right edge of a block.
1984          */
1985         for (lev = level + 1; lev < cur->bc_nlevels; lev++) {
1986                 bp = cur->bc_bufs[lev];
1987                 block = XFS_BUF_TO_ALLOC_BLOCK(bp);
1988 #ifdef DEBUG
1989                 if ((error = xfs_btree_check_sblock(cur, block, lev, bp)))
1990                         return error;
1991 #endif
1992                 if (++cur->bc_ptrs[lev] <= be16_to_cpu(block->bb_numrecs))
1993                         break;
1994                 /*
1995                  * Read-ahead the right block, we're going to read it
1996                  * in the next loop.
1997                  */
1998                 xfs_btree_readahead(cur, lev, XFS_BTCUR_RIGHTRA);
1999         }
2000         /*
2001          * If we went off the root then we are seriously confused.
2002          */
2003         ASSERT(lev < cur->bc_nlevels);
2004         /*
2005          * Now walk back down the tree, fixing up the cursor's buffer
2006          * pointers and key numbers.
2007          */
2008         for (bp = cur->bc_bufs[lev], block = XFS_BUF_TO_ALLOC_BLOCK(bp);
2009              lev > level; ) {
2010                 xfs_agblock_t   agbno;  /* block number of btree block */
2011
2012                 agbno = be32_to_cpu(*XFS_ALLOC_PTR_ADDR(block, cur->bc_ptrs[lev], cur));
2013                 if ((error = xfs_btree_read_bufs(cur->bc_mp, cur->bc_tp,
2014                                 cur->bc_private.a.agno, agbno, 0, &bp,
2015                                 XFS_ALLOC_BTREE_REF)))
2016                         return error;
2017                 lev--;
2018                 xfs_btree_setbuf(cur, lev, bp);
2019                 block = XFS_BUF_TO_ALLOC_BLOCK(bp);
2020                 if ((error = xfs_btree_check_sblock(cur, block, lev, bp)))
2021                         return error;
2022                 cur->bc_ptrs[lev] = 1;
2023         }
2024         *stat = 1;
2025         return 0;
2026 }
2027
2028 /*
2029  * Insert the current record at the point referenced by cur.
2030  * The cursor may be inconsistent on return if splits have been done.
2031  */
2032 int                                     /* error */
2033 xfs_alloc_insert(
2034         xfs_btree_cur_t *cur,           /* btree cursor */
2035         int             *stat)          /* success/failure */
2036 {
2037         int             error;          /* error return value */
2038         int             i;              /* result value, 0 for failure */
2039         int             level;          /* current level number in btree */
2040         xfs_agblock_t   nbno;           /* new block number (split result) */
2041         xfs_btree_cur_t *ncur;          /* new cursor (split result) */
2042         xfs_alloc_rec_t nrec;           /* record being inserted this level */
2043         xfs_btree_cur_t *pcur;          /* previous level's cursor */
2044
2045         level = 0;
2046         nbno = NULLAGBLOCK;
2047         nrec.ar_startblock = cpu_to_be32(cur->bc_rec.a.ar_startblock);
2048         nrec.ar_blockcount = cpu_to_be32(cur->bc_rec.a.ar_blockcount);
2049         ncur = (xfs_btree_cur_t *)0;
2050         pcur = cur;
2051         /*
2052          * Loop going up the tree, starting at the leaf level.
2053          * Stop when we don't get a split block, that must mean that
2054          * the insert is finished with this level.
2055          */
2056         do {
2057                 /*
2058                  * Insert nrec/nbno into this level of the tree.
2059                  * Note if we fail, nbno will be null.
2060                  */
2061                 if ((error = xfs_alloc_insrec(pcur, level++, &nbno, &nrec, &ncur,
2062                                 &i))) {
2063                         if (pcur != cur)
2064                                 xfs_btree_del_cursor(pcur, XFS_BTREE_ERROR);
2065                         return error;
2066                 }
2067                 /*
2068                  * See if the cursor we just used is trash.
2069                  * Can't trash the caller's cursor, but otherwise we should
2070                  * if ncur is a new cursor or we're about to be done.
2071                  */
2072                 if (pcur != cur && (ncur || nbno == NULLAGBLOCK)) {
2073                         cur->bc_nlevels = pcur->bc_nlevels;
2074                         xfs_btree_del_cursor(pcur, XFS_BTREE_NOERROR);
2075                 }
2076                 /*
2077                  * If we got a new cursor, switch to it.
2078                  */
2079                 if (ncur) {
2080                         pcur = ncur;
2081                         ncur = (xfs_btree_cur_t *)0;
2082                 }
2083         } while (nbno != NULLAGBLOCK);
2084         *stat = i;
2085         return 0;
2086 }
2087
2088 /*
2089  * Lookup the record equal to [bno, len] in the btree given by cur.
2090  */
2091 int                                     /* error */
2092 xfs_alloc_lookup_eq(
2093         xfs_btree_cur_t *cur,           /* btree cursor */
2094         xfs_agblock_t   bno,            /* starting block of extent */
2095         xfs_extlen_t    len,            /* length of extent */
2096         int             *stat)          /* success/failure */
2097 {
2098         cur->bc_rec.a.ar_startblock = bno;
2099         cur->bc_rec.a.ar_blockcount = len;
2100         return xfs_alloc_lookup(cur, XFS_LOOKUP_EQ, stat);
2101 }
2102
2103 /*
2104  * Lookup the first record greater than or equal to [bno, len]
2105  * in the btree given by cur.
2106  */
2107 int                                     /* error */
2108 xfs_alloc_lookup_ge(
2109         xfs_btree_cur_t *cur,           /* btree cursor */
2110         xfs_agblock_t   bno,            /* starting block of extent */
2111         xfs_extlen_t    len,            /* length of extent */
2112         int             *stat)          /* success/failure */
2113 {
2114         cur->bc_rec.a.ar_startblock = bno;
2115         cur->bc_rec.a.ar_blockcount = len;
2116         return xfs_alloc_lookup(cur, XFS_LOOKUP_GE, stat);
2117 }
2118
2119 /*
2120  * Lookup the first record less than or equal to [bno, len]
2121  * in the btree given by cur.
2122  */
2123 int                                     /* error */
2124 xfs_alloc_lookup_le(
2125         xfs_btree_cur_t *cur,           /* btree cursor */
2126         xfs_agblock_t   bno,            /* starting block of extent */
2127         xfs_extlen_t    len,            /* length of extent */
2128         int             *stat)          /* success/failure */
2129 {
2130         cur->bc_rec.a.ar_startblock = bno;
2131         cur->bc_rec.a.ar_blockcount = len;
2132         return xfs_alloc_lookup(cur, XFS_LOOKUP_LE, stat);
2133 }
2134
2135 /*
2136  * Update the record referred to by cur, to the value given by [bno, len].
2137  * This either works (return 0) or gets an EFSCORRUPTED error.
2138  */
2139 int                                     /* error */
2140 xfs_alloc_update(
2141         xfs_btree_cur_t         *cur,   /* btree cursor */
2142         xfs_agblock_t           bno,    /* starting block of extent */
2143         xfs_extlen_t            len)    /* length of extent */
2144 {
2145         xfs_alloc_block_t       *block; /* btree block to update */
2146         int                     error;  /* error return value */
2147         int                     ptr;    /* current record number (updating) */
2148
2149         ASSERT(len > 0);
2150         /*
2151          * Pick up the a.g. freelist struct and the current block.
2152          */
2153         block = XFS_BUF_TO_ALLOC_BLOCK(cur->bc_bufs[0]);
2154 #ifdef DEBUG
2155         if ((error = xfs_btree_check_sblock(cur, block, 0, cur->bc_bufs[0])))
2156                 return error;
2157 #endif
2158         /*
2159          * Get the address of the rec to be updated.
2160          */
2161         ptr = cur->bc_ptrs[0];
2162         {
2163                 xfs_alloc_rec_t         *rp;    /* pointer to updated record */
2164
2165                 rp = XFS_ALLOC_REC_ADDR(block, ptr, cur);
2166                 /*
2167                  * Fill in the new contents and log them.
2168                  */
2169                 rp->ar_startblock = cpu_to_be32(bno);
2170                 rp->ar_blockcount = cpu_to_be32(len);
2171                 xfs_alloc_log_recs(cur, cur->bc_bufs[0], ptr, ptr);
2172         }
2173         /*
2174          * If it's the by-size btree and it's the last leaf block and
2175          * it's the last record... then update the size of the longest
2176          * extent in the a.g., which we cache in the a.g. freelist header.
2177          */
2178         if (cur->bc_btnum == XFS_BTNUM_CNT &&
2179             be32_to_cpu(block->bb_rightsib) == NULLAGBLOCK &&
2180             ptr == be16_to_cpu(block->bb_numrecs)) {
2181                 xfs_agf_t       *agf;   /* a.g. freespace header */
2182                 xfs_agnumber_t  seqno;
2183
2184                 agf = XFS_BUF_TO_AGF(cur->bc_private.a.agbp);
2185                 seqno = be32_to_cpu(agf->agf_seqno);
2186                 cur->bc_mp->m_perag[seqno].pagf_longest = len;
2187                 agf->agf_longest = cpu_to_be32(len);
2188                 xfs_alloc_log_agf(cur->bc_tp, cur->bc_private.a.agbp,
2189                         XFS_AGF_LONGEST);
2190         }
2191         /*
2192          * Updating first record in leaf. Pass new key value up to our parent.
2193          */
2194         if (ptr == 1) {
2195                 xfs_alloc_key_t key;    /* key containing [bno, len] */
2196
2197                 key.ar_startblock = cpu_to_be32(bno);
2198                 key.ar_blockcount = cpu_to_be32(len);
2199                 if ((error = xfs_alloc_updkey(cur, &key, 1)))
2200                         return error;
2201         }
2202         return 0;
2203 }