fs/xfs/xfs_alloc_btree.c

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