fs/xfs/xfs_alloc_btree.c

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