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         /*
 619          * GCC doesn't understand the (arguably complex) control flow in
 620          * this function and complains about uninitialized structure fields
 621          * without this.
 622          */
 623         memset(&nrec, 0, sizeof(nrec));
 624
 625         /*
 626          * If we made it to the root level, allocate a new root block
 627          * and we're done.
 628          */
 629         if (level >= cur->bc_nlevels) {
 630                 XFS_STATS_INC(xs_abt_insrec);
 631                 if ((error = xfs_alloc_newroot(cur, &i)))
 632                         return error;
 633                 *bnop = NULLAGBLOCK;
 634                 *stat = i;
 635                 return 0;
 636         }
 637         /*
 638          * Make a key out of the record data to be inserted, and save it.
 639          */
 640         key.ar_startblock = recp->ar_startblock; /* INT_: direct copy */
 641         key.ar_blockcount = recp->ar_blockcount; /* INT_: direct copy */
 642         optr = ptr = cur->bc_ptrs[level];
 643         /*
 644          * If we're off the left edge, return failure.
 645          */
 646         if (ptr == 0) {
 647                 *stat = 0;
 648                 return 0;
 649         }
 650         XFS_STATS_INC(xs_abt_insrec);
 651         /*
 652          * Get pointers to the btree buffer and block.
 653          */
 654         bp = cur->bc_bufs[level];
 655         block = XFS_BUF_TO_ALLOC_BLOCK(bp);
 656 #ifdef DEBUG
 657         if ((error = xfs_btree_check_sblock(cur, block, level, bp)))
 658                 return error;
 659         /*
 660          * Check that the new entry is being inserted in the right place.
 661          */
 662         if (ptr <= INT_GET(block->bb_numrecs, ARCH_CONVERT)) {
 663                 if (level == 0) {
 664                         rp = XFS_ALLOC_REC_ADDR(block, ptr, cur);
 665                         xfs_btree_check_rec(cur->bc_btnum, recp, rp);
 666                 } else {
 667                         kp = XFS_ALLOC_KEY_ADDR(block, ptr, cur);
 668                         xfs_btree_check_key(cur->bc_btnum, &key, kp);
 669                 }
 670         }
 671 #endif
 672         nbno = NULLAGBLOCK;
 673         ncur = (xfs_btree_cur_t *)0;
 674         /*
 675          * If the block is full, we can't insert the new entry until we
 676          * make the block un-full.
 677          */
 678         if (INT_GET(block->bb_numrecs, ARCH_CONVERT) == XFS_ALLOC_BLOCK_MAXRECS(level, cur)) {
 679                 /*
 680                  * First, try shifting an entry to the right neighbor.
 681                  */
 682                 if ((error = xfs_alloc_rshift(cur, level, &i)))
 683                         return error;
 684                 if (i) {
 685                         /* nothing */
 686                 }
 687                 /*
 688                  * Next, try shifting an entry to the left neighbor.
 689                  */
 690                 else {
 691                         if ((error = xfs_alloc_lshift(cur, level, &i)))
 692                                 return error;
 693                         if (i)
 694                                 optr = ptr = cur->bc_ptrs[level];
 695                         else {
 696                                 /*
 697                                  * Next, try splitting the current block in
 698                                  * half. If this works we have to re-set our
 699                                  * variables because we could be in a
 700                                  * different block now.
 701                                  */
 702                                 if ((error = xfs_alloc_split(cur, level, &nbno,
 703                                                 &nkey, &ncur, &i)))
 704                                         return error;
 705                                 if (i) {
 706                                         bp = cur->bc_bufs[level];
 707                                         block = XFS_BUF_TO_ALLOC_BLOCK(bp);
 708 #ifdef DEBUG
 709                                         if ((error =
 710                                                 xfs_btree_check_sblock(cur,
 711                                                         block, level, bp)))
 712                                                 return error;
 713 #endif
 714                                         ptr = cur->bc_ptrs[level];
 715                                         nrec.ar_startblock = nkey.ar_startblock; /* INT_: direct copy */
 716                                         nrec.ar_blockcount = nkey.ar_blockcount; /* INT_: direct copy */
 717                                 }
 718                                 /*
 719                                  * Otherwise the insert fails.
 720                                  */
 721                                 else {
 722                                         *stat = 0;
 723                                         return 0;
 724                                 }
 725                         }
 726                 }
 727         }
 728         /*
 729          * At this point we know there's room for our new entry in the block
 730          * we're pointing at.
 731          */
 732         if (level > 0) {
 733                 /*
 734                  * It's a non-leaf entry.  Make a hole for the new data
 735                  * in the key and ptr regions of the block.
 736                  */
 737                 kp = XFS_ALLOC_KEY_ADDR(block, 1, cur);
 738                 pp = XFS_ALLOC_PTR_ADDR(block, 1, cur);
 739 #ifdef DEBUG
 740                 for (i = INT_GET(block->bb_numrecs, ARCH_CONVERT); i >= ptr; i--) {
 741                         if ((error = xfs_btree_check_sptr(cur, INT_GET(pp[i - 1], ARCH_CONVERT), level)))
 742                                 return error;
 743                 }
 744 #endif
 745                 memmove(&kp[ptr], &kp[ptr - 1],
 746                         (INT_GET(block->bb_numrecs, ARCH_CONVERT) - ptr + 1) * sizeof(*kp)); /* INT_: copy */
 747                 memmove(&pp[ptr], &pp[ptr - 1],
 748                         (INT_GET(block->bb_numrecs, ARCH_CONVERT) - ptr + 1) * sizeof(*pp)); /* INT_: copy */
 749 #ifdef DEBUG
 750                 if ((error = xfs_btree_check_sptr(cur, *bnop, level)))
 751                         return error;
 752 #endif
 753                 /*
 754                  * Now stuff the new data in, bump numrecs and log the new data.
 755                  */
 756                 kp[ptr - 1] = key;
 757                 INT_SET(pp[ptr - 1], ARCH_CONVERT, *bnop);
 758                 INT_MOD(block->bb_numrecs, ARCH_CONVERT, +1);
 759                 xfs_alloc_log_keys(cur, bp, ptr, INT_GET(block->bb_numrecs, ARCH_CONVERT));
 760                 xfs_alloc_log_ptrs(cur, bp, ptr, INT_GET(block->bb_numrecs, ARCH_CONVERT));
 761 #ifdef DEBUG
 762                 if (ptr < INT_GET(block->bb_numrecs, ARCH_CONVERT))
 763                         xfs_btree_check_key(cur->bc_btnum, kp + ptr - 1,
 764                                 kp + ptr);
 765 #endif
 766         } else {
 767                 /*
 768                  * It's a leaf entry.  Make a hole for the new record.
 769                  */
 770                 rp = XFS_ALLOC_REC_ADDR(block, 1, cur);
 771                 memmove(&rp[ptr], &rp[ptr - 1],
 772                         (INT_GET(block->bb_numrecs, ARCH_CONVERT) - ptr + 1) * sizeof(*rp));
 773                 /*
 774                  * Now stuff the new record in, bump numrecs
 775                  * and log the new data.
 776                  */
 777                 rp[ptr - 1] = *recp; /* INT_: struct copy */
 778                 INT_MOD(block->bb_numrecs, ARCH_CONVERT, +1);
 779                 xfs_alloc_log_recs(cur, bp, ptr, INT_GET(block->bb_numrecs, ARCH_CONVERT));
 780 #ifdef DEBUG
 781                 if (ptr < INT_GET(block->bb_numrecs, ARCH_CONVERT))
 782                         xfs_btree_check_rec(cur->bc_btnum, rp + ptr - 1,
 783                                 rp + ptr);
 784 #endif
 785         }
 786         /*
 787          * Log the new number of records in the btree header.
 788          */
 789         xfs_alloc_log_block(cur->bc_tp, bp, XFS_BB_NUMRECS);
 790         /*
 791          * If we inserted at the start of a block, update the parents' keys.
 792          */
 793         if (optr == 1 && (error = xfs_alloc_updkey(cur, &key, level + 1)))
 794                 return error;
 795         /*
 796          * Look to see if the longest extent in the allocation group
 797          * needs to be updated.
 798          */
 799
 800         agf = XFS_BUF_TO_AGF(cur->bc_private.a.agbp);
 801         if (level == 0 &&
 802             cur->bc_btnum == XFS_BTNUM_CNT &&
 803             INT_GET(block->bb_rightsib, ARCH_CONVERT) == NULLAGBLOCK &&
 804             INT_GET(recp->ar_blockcount, ARCH_CONVERT) > INT_GET(agf->agf_longest, ARCH_CONVERT)) {
 805                 /*
 806                  * If this is a leaf in the by-size btree and there
 807                  * is no right sibling block and this block is bigger
 808                  * than the previous longest block, update it.
 809                  */
 810                 INT_COPY(agf->agf_longest, recp->ar_blockcount, ARCH_CONVERT);
 811                 cur->bc_mp->m_perag[INT_GET(agf->agf_seqno, ARCH_CONVERT)].pagf_longest
 812                         = INT_GET(recp->ar_blockcount, ARCH_CONVERT);
 813                 xfs_alloc_log_agf(cur->bc_tp, cur->bc_private.a.agbp,
 814                         XFS_AGF_LONGEST);
 815         }
 816         /*
 817          * Return the new block number, if any.
 818          * If there is one, give back a record value and a cursor too.
 819          */
 820         *bnop = nbno;
 821         if (nbno != NULLAGBLOCK) {
 822                 *recp = nrec; /* INT_: struct copy */
 823                 *curp = ncur; /* INT_: struct copy */
 824         }
 825         *stat = 1;
 826         return 0;
 827 }
 828
 829 /*
 830  * Log header fields from a btree block.
 831  */
 832 STATIC void
 833 xfs_alloc_log_block(
 834         xfs_trans_t             *tp,    /* transaction pointer */
 835         xfs_buf_t               *bp,    /* buffer containing btree block */
 836         int                     fields) /* mask of fields: XFS_BB_... */
 837 {
 838         int                     first;  /* first byte offset logged */
 839         int                     last;   /* last byte offset logged */
 840         static const short      offsets[] = {   /* table of offsets */
 841                 offsetof(xfs_alloc_block_t, bb_magic),
 842                 offsetof(xfs_alloc_block_t, bb_level),
 843                 offsetof(xfs_alloc_block_t, bb_numrecs),
 844                 offsetof(xfs_alloc_block_t, bb_leftsib),
 845                 offsetof(xfs_alloc_block_t, bb_rightsib),
 846                 sizeof(xfs_alloc_block_t)
 847         };
 848
 849         xfs_btree_offsets(fields, offsets, XFS_BB_NUM_BITS, &first, &last);
 850         xfs_trans_log_buf(tp, bp, first, last);
 851 }
 852
 853 /*
 854  * Log keys from a btree block (nonleaf).
 855  */
 856 STATIC void
 857 xfs_alloc_log_keys(
 858         xfs_btree_cur_t         *cur,   /* btree cursor */
 859         xfs_buf_t               *bp,    /* buffer containing btree block */
 860         int                     kfirst, /* index of first key to log */
 861         int                     klast)  /* index of last key to log */
 862 {
 863         xfs_alloc_block_t       *block; /* btree block to log from */
 864         int                     first;  /* first byte offset logged */
 865         xfs_alloc_key_t         *kp;    /* key pointer in btree block */
 866         int                     last;   /* last byte offset logged */
 867
 868         block = XFS_BUF_TO_ALLOC_BLOCK(bp);
 869         kp = XFS_ALLOC_KEY_ADDR(block, 1, cur);
 870         first = (int)((xfs_caddr_t)&kp[kfirst - 1] - (xfs_caddr_t)block);
 871         last = (int)(((xfs_caddr_t)&kp[klast] - 1) - (xfs_caddr_t)block);
 872         xfs_trans_log_buf(cur->bc_tp, bp, first, last);
 873 }
 874
 875 /*
 876  * Log block pointer fields from a btree block (nonleaf).
 877  */
 878 STATIC void
 879 xfs_alloc_log_ptrs(
 880         xfs_btree_cur_t         *cur,   /* btree cursor */
 881         xfs_buf_t               *bp,    /* buffer containing btree block */
 882         int                     pfirst, /* index of first pointer to log */
 883         int                     plast)  /* index of last pointer to log */
 884 {
 885         xfs_alloc_block_t       *block; /* btree block to log from */
 886         int                     first;  /* first byte offset logged */
 887         int                     last;   /* last byte offset logged */
 888         xfs_alloc_ptr_t         *pp;    /* block-pointer pointer in btree blk */
 889
 890         block = XFS_BUF_TO_ALLOC_BLOCK(bp);
 891         pp = XFS_ALLOC_PTR_ADDR(block, 1, cur);
 892         first = (int)((xfs_caddr_t)&pp[pfirst - 1] - (xfs_caddr_t)block);
 893         last = (int)(((xfs_caddr_t)&pp[plast] - 1) - (xfs_caddr_t)block);
 894         xfs_trans_log_buf(cur->bc_tp, bp, first, last);
 895 }
 896
 897 /*
 898  * Log records from a btree block (leaf).
 899  */
 900 STATIC void
 901 xfs_alloc_log_recs(
 902         xfs_btree_cur_t         *cur,   /* btree cursor */
 903         xfs_buf_t               *bp,    /* buffer containing btree block */
 904         int                     rfirst, /* index of first record to log */
 905         int                     rlast)  /* index of last record to log */
 906 {
 907         xfs_alloc_block_t       *block; /* btree block to log from */
 908         int                     first;  /* first byte offset logged */
 909         int                     last;   /* last byte offset logged */
 910         xfs_alloc_rec_t         *rp;    /* record pointer for btree block */
 911
 912
 913         block = XFS_BUF_TO_ALLOC_BLOCK(bp);
 914         rp = XFS_ALLOC_REC_ADDR(block, 1, cur);
 915 #ifdef DEBUG
 916         {
 917                 xfs_agf_t       *agf;
 918                 xfs_alloc_rec_t *p;
 919
 920                 agf = XFS_BUF_TO_AGF(cur->bc_private.a.agbp);
 921                 for (p = &rp[rfirst - 1]; p <= &rp[rlast - 1]; p++)
 922                         ASSERT(INT_GET(p->ar_startblock, ARCH_CONVERT) + INT_GET(p->ar_blockcount, ARCH_CONVERT) <=
 923                                INT_GET(agf->agf_length, ARCH_CONVERT));
 924         }
 925 #endif
 926         first = (int)((xfs_caddr_t)&rp[rfirst - 1] - (xfs_caddr_t)block);
 927         last = (int)(((xfs_caddr_t)&rp[rlast] - 1) - (xfs_caddr_t)block);
 928         xfs_trans_log_buf(cur->bc_tp, bp, first, last);
 929 }
 930
 931 /*
 932  * Lookup the record.  The cursor is made to point to it, based on dir.
 933  * Return 0 if can't find any such record, 1 for success.
 934  */
 935 STATIC int                              /* error */
 936 xfs_alloc_lookup(
 937         xfs_btree_cur_t         *cur,   /* btree cursor */
 938         xfs_lookup_t            dir,    /* <=, ==, or >= */
 939         int                     *stat)  /* success/failure */
 940 {
 941         xfs_agblock_t           agbno;  /* a.g. relative btree block number */
 942         xfs_agnumber_t          agno;   /* allocation group number */
 943         xfs_alloc_block_t       *block=NULL;    /* current btree block */
 944         int                     diff;   /* difference for the current key */
 945         int                     error;  /* error return value */
 946         int                     keyno=0;        /* current key number */
 947         int                     level;  /* level in the btree */
 948         xfs_mount_t             *mp;    /* file system mount point */
 949
 950         XFS_STATS_INC(xs_abt_lookup);
 951         /*
 952          * Get the allocation group header, and the root block number.
 953          */
 954         mp = cur->bc_mp;
 955
 956         {
 957                 xfs_agf_t       *agf;   /* a.g. freespace header */
 958
 959                 agf = XFS_BUF_TO_AGF(cur->bc_private.a.agbp);
 960                 agno = INT_GET(agf->agf_seqno, ARCH_CONVERT);
 961                 agbno = INT_GET(agf->agf_roots[cur->bc_btnum], ARCH_CONVERT);
 962         }
 963         /*
 964          * Iterate over each level in the btree, starting at the root.
 965          * For each level above the leaves, find the key we need, based
 966          * on the lookup record, then follow the corresponding block
 967          * pointer down to the next level.
 968          */
 969         for (level = cur->bc_nlevels - 1, diff = 1; level >= 0; level--) {
 970                 xfs_buf_t       *bp;    /* buffer pointer for btree block */
 971                 xfs_daddr_t     d;      /* disk address of btree block */
 972
 973                 /*
 974                  * Get the disk address we're looking for.
 975                  */
 976                 d = XFS_AGB_TO_DADDR(mp, agno, agbno);
 977                 /*
 978                  * If the old buffer at this level is for a different block,
 979                  * throw it away, otherwise just use it.
 980                  */
 981                 bp = cur->bc_bufs[level];
 982                 if (bp && XFS_BUF_ADDR(bp) != d)
 983                         bp = (xfs_buf_t *)0;
 984                 if (!bp) {
 985                         /*
 986                          * Need to get a new buffer.  Read it, then
 987                          * set it in the cursor, releasing the old one.
 988                          */
 989                         if ((error = xfs_btree_read_bufs(mp, cur->bc_tp, agno,
 990                                         agbno, 0, &bp, XFS_ALLOC_BTREE_REF)))
 991                                 return error;
 992                         xfs_btree_setbuf(cur, level, bp);
 993                         /*
 994                          * Point to the btree block, now that we have the buffer
 995                          */
 996                         block = XFS_BUF_TO_ALLOC_BLOCK(bp);
 997                         if ((error = xfs_btree_check_sblock(cur, block, level,
 998                                         bp)))
 999                                 return error;
1000                 } else
1001                         block = XFS_BUF_TO_ALLOC_BLOCK(bp);
1002                 /*
1003                  * If we already had a key match at a higher level, we know
1004                  * we need to use the first entry in this block.
1005                  */
1006                 if (diff == 0)
1007                         keyno = 1;
1008                 /*
1009                  * Otherwise we need to search this block.  Do a binary search.
1010                  */
1011                 else {
1012                         int             high;   /* high entry number */
1013                         xfs_alloc_key_t *kkbase=NULL;/* base of keys in block */
1014                         xfs_alloc_rec_t *krbase=NULL;/* base of records in block */
1015                         int             low;    /* low entry number */
1016
1017                         /*
1018                          * Get a pointer to keys or records.
1019                          */
1020                         if (level > 0)
1021                                 kkbase = XFS_ALLOC_KEY_ADDR(block, 1, cur);
1022                         else
1023                                 krbase = XFS_ALLOC_REC_ADDR(block, 1, cur);
1024                         /*
1025                          * Set low and high entry numbers, 1-based.
1026                          */
1027                         low = 1;
1028                         if (!(high = INT_GET(block->bb_numrecs, ARCH_CONVERT))) {
1029                                 /*
1030                                  * If the block is empty, the tree must
1031                                  * be an empty leaf.
1032                                  */
1033                                 ASSERT(level == 0 && cur->bc_nlevels == 1);
1034                                 cur->bc_ptrs[0] = dir != XFS_LOOKUP_LE;
1035                                 *stat = 0;
1036                                 return 0;
1037                         }
1038                         /*
1039                          * Binary search the block.
1040                          */
1041                         while (low <= high) {
1042                                 xfs_extlen_t    blockcount;     /* key value */
1043                                 xfs_agblock_t   startblock;     /* key value */
1044
1045                                 XFS_STATS_INC(xs_abt_compare);
1046                                 /*
1047                                  * keyno is average of low and high.
1048                                  */
1049                                 keyno = (low + high) >> 1;
1050                                 /*
1051                                  * Get startblock & blockcount.
1052                                  */
1053                                 if (level > 0) {
1054                                         xfs_alloc_key_t *kkp;
1055
1056                                         kkp = kkbase + keyno - 1;
1057                                         startblock = INT_GET(kkp->ar_startblock, ARCH_CONVERT);
1058                                         blockcount = INT_GET(kkp->ar_blockcount, ARCH_CONVERT);
1059                                 } else {
1060                                         xfs_alloc_rec_t *krp;
1061
1062                                         krp = krbase + keyno - 1;
1063                                         startblock = INT_GET(krp->ar_startblock, ARCH_CONVERT);
1064                                         blockcount = INT_GET(krp->ar_blockcount, ARCH_CONVERT);
1065                                 }
1066                                 /*
1067                                  * Compute difference to get next direction.
1068                                  */
1069                                 if (cur->bc_btnum == XFS_BTNUM_BNO)
1070                                         diff = (int)startblock -
1071                                                (int)cur->bc_rec.a.ar_startblock;
1072                                 else if (!(diff = (int)blockcount -
1073                                             (int)cur->bc_rec.a.ar_blockcount))
1074                                         diff = (int)startblock -
1075                                             (int)cur->bc_rec.a.ar_startblock;
1076                                 /*
1077                                  * Less than, move right.
1078                                  */
1079                                 if (diff < 0)
1080                                         low = keyno + 1;
1081                                 /*
1082                                  * Greater than, move left.
1083                                  */
1084                                 else if (diff > 0)
1085                                         high = keyno - 1;
1086                                 /*
1087                                  * Equal, we're done.
1088                                  */
1089                                 else
1090                                         break;
1091                         }
1092                 }
1093                 /*
1094                  * If there are more levels, set up for the next level
1095                  * by getting the block number and filling in the cursor.
1096                  */
1097                 if (level > 0) {
1098                         /*
1099                          * If we moved left, need the previous key number,
1100                          * unless there isn't one.
1101                          */
1102                         if (diff > 0 && --keyno < 1)
1103                                 keyno = 1;
1104                         agbno = INT_GET(*XFS_ALLOC_PTR_ADDR(block, keyno, cur), ARCH_CONVERT);
1105 #ifdef DEBUG
1106                         if ((error = xfs_btree_check_sptr(cur, agbno, level)))
1107                                 return error;
1108 #endif
1109                         cur->bc_ptrs[level] = keyno;
1110                 }
1111         }
1112         /*
1113          * Done with the search.
1114          * See if we need to adjust the results.
1115          */
1116         if (dir != XFS_LOOKUP_LE && diff < 0) {
1117                 keyno++;
1118                 /*
1119                  * If ge search and we went off the end of the block, but it's
1120                  * not the last block, we're in the wrong block.
1121                  */
1122                 if (dir == XFS_LOOKUP_GE &&
1123                     keyno > INT_GET(block->bb_numrecs, ARCH_CONVERT) &&
1124                     INT_GET(block->bb_rightsib, ARCH_CONVERT) != NULLAGBLOCK) {
1125                         int     i;
1126
1127                         cur->bc_ptrs[0] = keyno;
1128                         if ((error = xfs_alloc_increment(cur, 0, &i)))
1129                                 return error;
1130                         XFS_WANT_CORRUPTED_RETURN(i == 1);
1131                         *stat = 1;
1132                         return 0;
1133                 }
1134         }
1135         else if (dir == XFS_LOOKUP_LE && diff > 0)
1136                 keyno--;
1137         cur->bc_ptrs[0] = keyno;
1138         /*
1139          * Return if we succeeded or not.
1140          */
1141         if (keyno == 0 || keyno > INT_GET(block->bb_numrecs, ARCH_CONVERT))
1142                 *stat = 0;
1143         else
1144                 *stat = ((dir != XFS_LOOKUP_EQ) || (diff == 0));
1145         return 0;
1146 }
1147
1148 /*
1149  * Move 1 record left from cur/level if possible.
1150  * Update cur to reflect the new path.
1151  */
1152 STATIC int                              /* error */
1153 xfs_alloc_lshift(
1154         xfs_btree_cur_t         *cur,   /* btree cursor */
1155         int                     level,  /* level to shift record on */
1156         int                     *stat)  /* success/failure */
1157 {
1158         int                     error;  /* error return value */
1159 #ifdef DEBUG
1160         int                     i;      /* loop index */
1161 #endif
1162         xfs_alloc_key_t         key;    /* key value for leaf level upward */
1163         xfs_buf_t               *lbp;   /* buffer for left neighbor block */
1164         xfs_alloc_block_t       *left;  /* left neighbor btree block */
1165         int                     nrec;   /* new number of left block entries */
1166         xfs_buf_t               *rbp;   /* buffer for right (current) block */
1167         xfs_alloc_block_t       *right; /* right (current) btree block */
1168         xfs_alloc_key_t         *rkp=NULL;      /* key pointer for right block */
1169         xfs_alloc_ptr_t         *rpp=NULL;      /* address pointer for right block */
1170         xfs_alloc_rec_t         *rrp=NULL;      /* record pointer for right block */
1171
1172         /*
1173          * Set up variables for this block as "right".
1174          */
1175         rbp = cur->bc_bufs[level];
1176         right = XFS_BUF_TO_ALLOC_BLOCK(rbp);
1177 #ifdef DEBUG
1178         if ((error = xfs_btree_check_sblock(cur, right, level, rbp)))
1179                 return error;
1180 #endif
1181         /*
1182          * If we've got no left sibling then we can't shift an entry left.
1183          */
1184         if (INT_GET(right->bb_leftsib, ARCH_CONVERT) == NULLAGBLOCK) {
1185                 *stat = 0;
1186                 return 0;
1187         }
1188         /*
1189          * If the cursor entry is the one that would be moved, don't
1190          * do it... it's too complicated.
1191          */
1192         if (cur->bc_ptrs[level] <= 1) {
1193                 *stat = 0;
1194                 return 0;
1195         }
1196         /*
1197          * Set up the left neighbor as "left".
1198          */
1199         if ((error = xfs_btree_read_bufs(cur->bc_mp, cur->bc_tp,
1200                         cur->bc_private.a.agno, INT_GET(right->bb_leftsib, ARCH_CONVERT), 0, &lbp,
1201                         XFS_ALLOC_BTREE_REF)))
1202                 return error;
1203         left = XFS_BUF_TO_ALLOC_BLOCK(lbp);
1204         if ((error = xfs_btree_check_sblock(cur, left, level, lbp)))
1205                 return error;
1206         /*
1207          * If it's full, it can't take another entry.
1208          */
1209         if (INT_GET(left->bb_numrecs, ARCH_CONVERT) == XFS_ALLOC_BLOCK_MAXRECS(level, cur)) {
1210                 *stat = 0;
1211                 return 0;
1212         }
1213         nrec = INT_GET(left->bb_numrecs, ARCH_CONVERT) + 1;
1214         /*
1215          * If non-leaf, copy a key and a ptr to the left block.
1216          */
1217         if (level > 0) {
1218                 xfs_alloc_key_t *lkp;   /* key pointer for left block */
1219                 xfs_alloc_ptr_t *lpp;   /* address pointer for left block */
1220
1221                 lkp = XFS_ALLOC_KEY_ADDR(left, nrec, cur);
1222                 rkp = XFS_ALLOC_KEY_ADDR(right, 1, cur);
1223                 *lkp = *rkp;
1224                 xfs_alloc_log_keys(cur, lbp, nrec, nrec);
1225                 lpp = XFS_ALLOC_PTR_ADDR(left, nrec, cur);
1226                 rpp = XFS_ALLOC_PTR_ADDR(right, 1, cur);
1227 #ifdef DEBUG
1228                 if ((error = xfs_btree_check_sptr(cur, INT_GET(*rpp, ARCH_CONVERT), level)))
1229                         return error;
1230 #endif
1231                 *lpp = *rpp; /* INT_: copy */
1232                 xfs_alloc_log_ptrs(cur, lbp, nrec, nrec);
1233                 xfs_btree_check_key(cur->bc_btnum, lkp - 1, lkp);
1234         }
1235         /*
1236          * If leaf, copy a record to the left block.
1237          */
1238         else {
1239                 xfs_alloc_rec_t *lrp;   /* record pointer for left block */
1240
1241                 lrp = XFS_ALLOC_REC_ADDR(left, nrec, cur);
1242                 rrp = XFS_ALLOC_REC_ADDR(right, 1, cur);
1243                 *lrp = *rrp;
1244                 xfs_alloc_log_recs(cur, lbp, nrec, nrec);
1245                 xfs_btree_check_rec(cur->bc_btnum, lrp - 1, lrp);
1246         }
1247         /*
1248          * Bump and log left's numrecs, decrement and log right's numrecs.
1249          */
1250         INT_MOD(left->bb_numrecs, ARCH_CONVERT, +1);
1251         xfs_alloc_log_block(cur->bc_tp, lbp, XFS_BB_NUMRECS);
1252         INT_MOD(right->bb_numrecs, ARCH_CONVERT, -1);
1253         xfs_alloc_log_block(cur->bc_tp, rbp, XFS_BB_NUMRECS);
1254         /*
1255          * Slide the contents of right down one entry.
1256          */
1257         if (level > 0) {
1258 #ifdef DEBUG
1259                 for (i = 0; i < INT_GET(right->bb_numrecs, ARCH_CONVERT); i++) {
1260                         if ((error = xfs_btree_check_sptr(cur, INT_GET(rpp[i + 1], ARCH_CONVERT),
1261                                         level)))
1262                                 return error;
1263                 }
1264 #endif
1265                 memmove(rkp, rkp + 1, INT_GET(right->bb_numrecs, ARCH_CONVERT) * sizeof(*rkp));
1266                 memmove(rpp, rpp + 1, INT_GET(right->bb_numrecs, ARCH_CONVERT) * sizeof(*rpp));
1267                 xfs_alloc_log_keys(cur, rbp, 1, INT_GET(right->bb_numrecs, ARCH_CONVERT));
1268                 xfs_alloc_log_ptrs(cur, rbp, 1, INT_GET(right->bb_numrecs, ARCH_CONVERT));
1269         } else {
1270                 memmove(rrp, rrp + 1, INT_GET(right->bb_numrecs, ARCH_CONVERT) * sizeof(*rrp));
1271                 xfs_alloc_log_recs(cur, rbp, 1, INT_GET(right->bb_numrecs, ARCH_CONVERT));
1272                 key.ar_startblock = rrp->ar_startblock; /* INT_: direct copy */
1273                 key.ar_blockcount = rrp->ar_blockcount; /* INT_: direct copy */
1274                 rkp = &key;
1275         }
1276         /*
1277          * Update the parent key values of right.
1278          */
1279         if ((error = xfs_alloc_updkey(cur, rkp, level + 1)))
1280                 return error;
1281         /*
1282          * Slide the cursor value left one.
1283          */
1284         cur->bc_ptrs[level]--;
1285         *stat = 1;
1286         return 0;
1287 }
1288
1289 /*
1290  * Allocate a new root block, fill it in.
1291  */
1292 STATIC int                              /* error */
1293 xfs_alloc_newroot(
1294         xfs_btree_cur_t         *cur,   /* btree cursor */
1295         int                     *stat)  /* success/failure */
1296 {
1297         int                     error;  /* error return value */
1298         xfs_agblock_t           lbno;   /* left block number */
1299         xfs_buf_t               *lbp;   /* left btree buffer */
1300         xfs_alloc_block_t       *left;  /* left btree block */
1301         xfs_mount_t             *mp;    /* mount structure */
1302         xfs_agblock_t           nbno;   /* new block number */
1303         xfs_buf_t               *nbp;   /* new (root) buffer */
1304         xfs_alloc_block_t       *new;   /* new (root) btree block */
1305         int                     nptr;   /* new value for key index, 1 or 2 */
1306         xfs_agblock_t           rbno;   /* right block number */
1307         xfs_buf_t               *rbp;   /* right btree buffer */
1308         xfs_alloc_block_t       *right; /* right btree block */
1309
1310         mp = cur->bc_mp;
1311
1312         ASSERT(cur->bc_nlevels < XFS_AG_MAXLEVELS(mp));
1313         /*
1314          * Get a buffer from the freelist blocks, for the new root.
1315          */
1316         if ((error = xfs_alloc_get_freelist(cur->bc_tp, cur->bc_private.a.agbp,
1317                         &nbno)))
1318                 return error;
1319         /*
1320          * None available, we fail.
1321          */
1322         if (nbno == NULLAGBLOCK) {
1323                 *stat = 0;
1324                 return 0;
1325         }
1326         xfs_trans_agbtree_delta(cur->bc_tp, 1);
1327         nbp = xfs_btree_get_bufs(mp, cur->bc_tp, cur->bc_private.a.agno, nbno,
1328                 0);
1329         new = XFS_BUF_TO_ALLOC_BLOCK(nbp);
1330         /*
1331          * Set the root data in the a.g. freespace structure.
1332          */
1333         {
1334                 xfs_agf_t       *agf;   /* a.g. freespace header */
1335                 xfs_agnumber_t  seqno;
1336
1337                 agf = XFS_BUF_TO_AGF(cur->bc_private.a.agbp);
1338                 INT_SET(agf->agf_roots[cur->bc_btnum], ARCH_CONVERT, nbno);
1339                 INT_MOD(agf->agf_levels[cur->bc_btnum], ARCH_CONVERT, 1);
1340                 seqno = INT_GET(agf->agf_seqno, ARCH_CONVERT);
1341                 mp->m_perag[seqno].pagf_levels[cur->bc_btnum]++;
1342                 xfs_alloc_log_agf(cur->bc_tp, cur->bc_private.a.agbp,
1343                         XFS_AGF_ROOTS | XFS_AGF_LEVELS);
1344         }
1345         /*
1346          * At the previous root level there are now two blocks: the old
1347          * root, and the new block generated when it was split.
1348          * We don't know which one the cursor is pointing at, so we
1349          * set up variables "left" and "right" for each case.
1350          */
1351         lbp = cur->bc_bufs[cur->bc_nlevels - 1];
1352         left = XFS_BUF_TO_ALLOC_BLOCK(lbp);
1353 #ifdef DEBUG
1354         if ((error = xfs_btree_check_sblock(cur, left, cur->bc_nlevels - 1, lbp)))
1355                 return error;
1356 #endif
1357         if (INT_GET(left->bb_rightsib, ARCH_CONVERT) != NULLAGBLOCK) {
1358                 /*
1359                  * Our block is left, pick up the right block.
1360                  */
1361                 lbno = XFS_DADDR_TO_AGBNO(mp, XFS_BUF_ADDR(lbp));
1362                 rbno = INT_GET(left->bb_rightsib, ARCH_CONVERT);
1363                 if ((error = xfs_btree_read_bufs(mp, cur->bc_tp,
1364                                 cur->bc_private.a.agno, rbno, 0, &rbp,
1365                                 XFS_ALLOC_BTREE_REF)))
1366                         return error;
1367                 right = XFS_BUF_TO_ALLOC_BLOCK(rbp);
1368                 if ((error = xfs_btree_check_sblock(cur, right,
1369                                 cur->bc_nlevels - 1, rbp)))
1370                         return error;
1371                 nptr = 1;
1372         } else {
1373                 /*
1374                  * Our block is right, pick up the left block.
1375                  */
1376                 rbp = lbp;
1377                 right = left;
1378                 rbno = XFS_DADDR_TO_AGBNO(mp, XFS_BUF_ADDR(rbp));
1379                 lbno = INT_GET(right->bb_leftsib, ARCH_CONVERT);
1380                 if ((error = xfs_btree_read_bufs(mp, cur->bc_tp,
1381                                 cur->bc_private.a.agno, lbno, 0, &lbp,
1382                                 XFS_ALLOC_BTREE_REF)))
1383                         return error;
1384                 left = XFS_BUF_TO_ALLOC_BLOCK(lbp);
1385                 if ((error = xfs_btree_check_sblock(cur, left,
1386                                 cur->bc_nlevels - 1, lbp)))
1387                         return error;
1388                 nptr = 2;
1389         }
1390         /*
1391          * Fill in the new block's btree header and log it.
1392          */
1393         INT_SET(new->bb_magic, ARCH_CONVERT, xfs_magics[cur->bc_btnum]);
1394         INT_SET(new->bb_level, ARCH_CONVERT, (__uint16_t)cur->bc_nlevels);
1395         INT_SET(new->bb_numrecs, ARCH_CONVERT, 2);
1396         INT_SET(new->bb_leftsib, ARCH_CONVERT, NULLAGBLOCK);
1397         INT_SET(new->bb_rightsib, ARCH_CONVERT, NULLAGBLOCK);
1398         xfs_alloc_log_block(cur->bc_tp, nbp, XFS_BB_ALL_BITS);
1399         ASSERT(lbno != NULLAGBLOCK && rbno != NULLAGBLOCK);
1400         /*
1401          * Fill in the key data in the new root.
1402          */
1403         {
1404                 xfs_alloc_key_t         *kp;    /* btree key pointer */
1405
1406                 kp = XFS_ALLOC_KEY_ADDR(new, 1, cur);
1407                 if (INT_GET(left->bb_level, ARCH_CONVERT) > 0) {
1408                         kp[0] = *XFS_ALLOC_KEY_ADDR(left, 1, cur); /* INT_: structure copy */
1409                         kp[1] = *XFS_ALLOC_KEY_ADDR(right, 1, cur);/* INT_: structure copy */
1410                 } else {
1411                         xfs_alloc_rec_t *rp;    /* btree record pointer */
1412
1413                         rp = XFS_ALLOC_REC_ADDR(left, 1, cur);
1414                         kp[0].ar_startblock = rp->ar_startblock; /* INT_: direct copy */
1415                         kp[0].ar_blockcount = rp->ar_blockcount; /* INT_: direct copy */
1416                         rp = XFS_ALLOC_REC_ADDR(right, 1, cur);
1417                         kp[1].ar_startblock = rp->ar_startblock; /* INT_: direct copy */
1418                         kp[1].ar_blockcount = rp->ar_blockcount; /* INT_: direct copy */
1419                 }
1420         }
1421         xfs_alloc_log_keys(cur, nbp, 1, 2);
1422         /*
1423          * Fill in the pointer data in the new root.
1424          */
1425         {
1426                 xfs_alloc_ptr_t         *pp;    /* btree address pointer */
1427
1428                 pp = XFS_ALLOC_PTR_ADDR(new, 1, cur);
1429                 INT_SET(pp[0], ARCH_CONVERT, lbno);
1430                 INT_SET(pp[1], ARCH_CONVERT, rbno);
1431         }
1432         xfs_alloc_log_ptrs(cur, nbp, 1, 2);
1433         /*
1434          * Fix up the cursor.
1435          */
1436         xfs_btree_setbuf(cur, cur->bc_nlevels, nbp);
1437         cur->bc_ptrs[cur->bc_nlevels] = nptr;
1438         cur->bc_nlevels++;
1439         *stat = 1;
1440         return 0;
1441 }
1442
1443 /*
1444  * Move 1 record right from cur/level if possible.
1445  * Update cur to reflect the new path.
1446  */
1447 STATIC int                              /* error */
1448 xfs_alloc_rshift(
1449         xfs_btree_cur_t         *cur,   /* btree cursor */
1450         int                     level,  /* level to shift record on */
1451         int                     *stat)  /* success/failure */
1452 {
1453         int                     error;  /* error return value */
1454         int                     i;      /* loop index */
1455         xfs_alloc_key_t         key;    /* key value for leaf level upward */
1456         xfs_buf_t               *lbp;   /* buffer for left (current) block */
1457         xfs_alloc_block_t       *left;  /* left (current) btree block */
1458         xfs_buf_t               *rbp;   /* buffer for right neighbor block */
1459         xfs_alloc_block_t       *right; /* right neighbor btree block */
1460         xfs_alloc_key_t         *rkp;   /* key pointer for right block */
1461         xfs_btree_cur_t         *tcur;  /* temporary cursor */
1462
1463         /*
1464          * Set up variables for this block as "left".
1465          */
1466         lbp = cur->bc_bufs[level];
1467         left = XFS_BUF_TO_ALLOC_BLOCK(lbp);
1468 #ifdef DEBUG
1469         if ((error = xfs_btree_check_sblock(cur, left, level, lbp)))
1470                 return error;
1471 #endif
1472         /*
1473          * If we've got no right sibling then we can't shift an entry right.
1474          */
1475         if (INT_GET(left->bb_rightsib, ARCH_CONVERT) == NULLAGBLOCK) {
1476                 *stat = 0;
1477                 return 0;
1478         }
1479         /*
1480          * If the cursor entry is the one that would be moved, don't
1481          * do it... it's too complicated.
1482          */
1483         if (cur->bc_ptrs[level] >= INT_GET(left->bb_numrecs, ARCH_CONVERT)) {
1484                 *stat = 0;
1485                 return 0;
1486         }
1487         /*
1488          * Set up the right neighbor as "right".
1489          */
1490         if ((error = xfs_btree_read_bufs(cur->bc_mp, cur->bc_tp,
1491                         cur->bc_private.a.agno, INT_GET(left->bb_rightsib, ARCH_CONVERT), 0, &rbp,
1492                         XFS_ALLOC_BTREE_REF)))
1493                 return error;
1494         right = XFS_BUF_TO_ALLOC_BLOCK(rbp);
1495         if ((error = xfs_btree_check_sblock(cur, right, level, rbp)))
1496                 return error;
1497         /*
1498          * If it's full, it can't take another entry.
1499          */
1500         if (INT_GET(right->bb_numrecs, ARCH_CONVERT) == XFS_ALLOC_BLOCK_MAXRECS(level, cur)) {
1501                 *stat = 0;
1502                 return 0;
1503         }
1504         /*
1505          * Make a hole at the start of the right neighbor block, then
1506          * copy the last left block entry to the hole.
1507          */
1508         if (level > 0) {
1509                 xfs_alloc_key_t *lkp;   /* key pointer for left block */
1510                 xfs_alloc_ptr_t *lpp;   /* address pointer for left block */
1511                 xfs_alloc_ptr_t *rpp;   /* address pointer for right block */
1512
1513                 lkp = XFS_ALLOC_KEY_ADDR(left, INT_GET(left->bb_numrecs, ARCH_CONVERT), cur);
1514                 lpp = XFS_ALLOC_PTR_ADDR(left, INT_GET(left->bb_numrecs, ARCH_CONVERT), cur);
1515                 rkp = XFS_ALLOC_KEY_ADDR(right, 1, cur);
1516                 rpp = XFS_ALLOC_PTR_ADDR(right, 1, cur);
1517 #ifdef DEBUG
1518                 for (i = INT_GET(right->bb_numrecs, ARCH_CONVERT) - 1; i >= 0; i--) {
1519                         if ((error = xfs_btree_check_sptr(cur, INT_GET(rpp[i], ARCH_CONVERT), level)))
1520                                 return error;
1521                 }
1522 #endif
1523                 memmove(rkp + 1, rkp, INT_GET(right->bb_numrecs, ARCH_CONVERT) * sizeof(*rkp));
1524                 memmove(rpp + 1, rpp, INT_GET(right->bb_numrecs, ARCH_CONVERT) * sizeof(*rpp));
1525 #ifdef DEBUG
1526                 if ((error = xfs_btree_check_sptr(cur, INT_GET(*lpp, ARCH_CONVERT), level)))
1527                         return error;
1528 #endif
1529                 *rkp = *lkp; /* INT_: copy */
1530                 *rpp = *lpp; /* INT_: copy */
1531                 xfs_alloc_log_keys(cur, rbp, 1, INT_GET(right->bb_numrecs, ARCH_CONVERT) + 1);
1532                 xfs_alloc_log_ptrs(cur, rbp, 1, INT_GET(right->bb_numrecs, ARCH_CONVERT) + 1);
1533                 xfs_btree_check_key(cur->bc_btnum, rkp, rkp + 1);
1534         } else {
1535                 xfs_alloc_rec_t *lrp;   /* record pointer for left block */
1536                 xfs_alloc_rec_t *rrp;   /* record pointer for right block */
1537
1538                 lrp = XFS_ALLOC_REC_ADDR(left, INT_GET(left->bb_numrecs, ARCH_CONVERT), cur);
1539                 rrp = XFS_ALLOC_REC_ADDR(right, 1, cur);
1540                 memmove(rrp + 1, rrp, INT_GET(right->bb_numrecs, ARCH_CONVERT) * sizeof(*rrp));
1541                 *rrp = *lrp;
1542                 xfs_alloc_log_recs(cur, rbp, 1, INT_GET(right->bb_numrecs, ARCH_CONVERT) + 1);
1543                 key.ar_startblock = rrp->ar_startblock; /* INT_: direct copy */
1544                 key.ar_blockcount = rrp->ar_blockcount; /* INT_: direct copy */
1545                 rkp = &key;
1546                 xfs_btree_check_rec(cur->bc_btnum, rrp, rrp + 1);
1547         }
1548         /*
1549          * Decrement and log left's numrecs, bump and log right's numrecs.
1550          */
1551         INT_MOD(left->bb_numrecs, ARCH_CONVERT, -1);
1552         xfs_alloc_log_block(cur->bc_tp, lbp, XFS_BB_NUMRECS);
1553         INT_MOD(right->bb_numrecs, ARCH_CONVERT, +1);
1554         xfs_alloc_log_block(cur->bc_tp, rbp, XFS_BB_NUMRECS);
1555         /*
1556          * Using a temporary cursor, update the parent key values of the
1557          * block on the right.
1558          */
1559         if ((error = xfs_btree_dup_cursor(cur, &tcur)))
1560                 return error;
1561         i = xfs_btree_lastrec(tcur, level);
1562         XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1563         if ((error = xfs_alloc_increment(tcur, level, &i)) ||
1564             (error = xfs_alloc_updkey(tcur, rkp, level + 1)))
1565                 goto error0;
1566         xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
1567         *stat = 1;
1568         return 0;
1569 error0:
1570         xfs_btree_del_cursor(tcur, XFS_BTREE_ERROR);
1571         return error;
1572 }
1573
1574 /*
1575  * Split cur/level block in half.
1576  * Return new block number and its first record (to be inserted into parent).
1577  */
1578 STATIC int                              /* error */
1579 xfs_alloc_split(
1580         xfs_btree_cur_t         *cur,   /* btree cursor */
1581         int                     level,  /* level to split */
1582         xfs_agblock_t           *bnop,  /* output: block number allocated */
1583         xfs_alloc_key_t         *keyp,  /* output: first key of new block */
1584         xfs_btree_cur_t         **curp, /* output: new cursor */
1585         int                     *stat)  /* success/failure */
1586 {
1587         int                     error;  /* error return value */
1588         int                     i;      /* loop index/record number */
1589         xfs_agblock_t           lbno;   /* left (current) block number */
1590         xfs_buf_t               *lbp;   /* buffer for left block */
1591         xfs_alloc_block_t       *left;  /* left (current) btree block */
1592         xfs_agblock_t           rbno;   /* right (new) block number */
1593         xfs_buf_t               *rbp;   /* buffer for right block */
1594         xfs_alloc_block_t       *right; /* right (new) btree block */
1595
1596         /*
1597          * Allocate the new block from the freelist.
1598          * If we can't do it, we're toast.  Give up.
1599          */
1600         if ((error = xfs_alloc_get_freelist(cur->bc_tp, cur->bc_private.a.agbp,
1601                         &rbno)))
1602                 return error;
1603         if (rbno == NULLAGBLOCK) {
1604                 *stat = 0;
1605                 return 0;
1606         }
1607         xfs_trans_agbtree_delta(cur->bc_tp, 1);
1608         rbp = xfs_btree_get_bufs(cur->bc_mp, cur->bc_tp, cur->bc_private.a.agno,
1609                 rbno, 0);
1610         /*
1611          * Set up the new block as "right".
1612          */
1613         right = XFS_BUF_TO_ALLOC_BLOCK(rbp);
1614         /*
1615          * "Left" is the current (according to the cursor) block.
1616          */
1617         lbp = cur->bc_bufs[level];
1618         left = XFS_BUF_TO_ALLOC_BLOCK(lbp);
1619 #ifdef DEBUG
1620         if ((error = xfs_btree_check_sblock(cur, left, level, lbp)))
1621                 return error;
1622 #endif
1623         /*
1624          * Fill in the btree header for the new block.
1625          */
1626         INT_SET(right->bb_magic, ARCH_CONVERT, xfs_magics[cur->bc_btnum]);
1627         right->bb_level = left->bb_level; /* INT_: direct copy */
1628         INT_SET(right->bb_numrecs, ARCH_CONVERT, (__uint16_t)(INT_GET(left->bb_numrecs, ARCH_CONVERT) / 2));
1629         /*
1630          * Make sure that if there's an odd number of entries now, that
1631          * each new block will have the same number of entries.
1632          */
1633         if ((INT_GET(left->bb_numrecs, ARCH_CONVERT) & 1) &&
1634             cur->bc_ptrs[level] <= INT_GET(right->bb_numrecs, ARCH_CONVERT) + 1)
1635                 INT_MOD(right->bb_numrecs, ARCH_CONVERT, +1);
1636         i = INT_GET(left->bb_numrecs, ARCH_CONVERT) - INT_GET(right->bb_numrecs, ARCH_CONVERT) + 1;
1637         /*
1638          * For non-leaf blocks, copy keys and addresses over to the new block.
1639          */
1640         if (level > 0) {
1641                 xfs_alloc_key_t *lkp;   /* left btree key pointer */
1642                 xfs_alloc_ptr_t *lpp;   /* left btree address pointer */
1643                 xfs_alloc_key_t *rkp;   /* right btree key pointer */
1644                 xfs_alloc_ptr_t *rpp;   /* right btree address pointer */
1645
1646                 lkp = XFS_ALLOC_KEY_ADDR(left, i, cur);
1647                 lpp = XFS_ALLOC_PTR_ADDR(left, i, cur);
1648                 rkp = XFS_ALLOC_KEY_ADDR(right, 1, cur);
1649                 rpp = XFS_ALLOC_PTR_ADDR(right, 1, cur);
1650 #ifdef DEBUG
1651                 for (i = 0; i < INT_GET(right->bb_numrecs, ARCH_CONVERT); i++) {
1652                         if ((error = xfs_btree_check_sptr(cur, INT_GET(lpp[i], ARCH_CONVERT), level)))
1653                                 return error;
1654                 }
1655 #endif
1656                 memcpy(rkp, lkp, INT_GET(right->bb_numrecs, ARCH_CONVERT) * sizeof(*rkp)); /* INT_: copy */
1657                 memcpy(rpp, lpp, INT_GET(right->bb_numrecs, ARCH_CONVERT) * sizeof(*rpp)); /* INT_: copy */
1658                 xfs_alloc_log_keys(cur, rbp, 1, INT_GET(right->bb_numrecs, ARCH_CONVERT));
1659                 xfs_alloc_log_ptrs(cur, rbp, 1, INT_GET(right->bb_numrecs, ARCH_CONVERT));
1660                 *keyp = *rkp;
1661         }
1662         /*
1663          * For leaf blocks, copy records over to the new block.
1664          */
1665         else {
1666                 xfs_alloc_rec_t *lrp;   /* left btree record pointer */
1667                 xfs_alloc_rec_t *rrp;   /* right btree record pointer */
1668
1669                 lrp = XFS_ALLOC_REC_ADDR(left, i, cur);
1670                 rrp = XFS_ALLOC_REC_ADDR(right, 1, cur);
1671                 memcpy(rrp, lrp, INT_GET(right->bb_numrecs, ARCH_CONVERT) * sizeof(*rrp));
1672                 xfs_alloc_log_recs(cur, rbp, 1, INT_GET(right->bb_numrecs, ARCH_CONVERT));
1673                 keyp->ar_startblock = rrp->ar_startblock; /* INT_: direct copy */
1674                 keyp->ar_blockcount = rrp->ar_blockcount; /* INT_: direct copy */
1675         }
1676         /*
1677          * Find the left block number by looking in the buffer.
1678          * Adjust numrecs, sibling pointers.
1679          */
1680         lbno = XFS_DADDR_TO_AGBNO(cur->bc_mp, XFS_BUF_ADDR(lbp));
1681         INT_MOD(left->bb_numrecs, ARCH_CONVERT, -(INT_GET(right->bb_numrecs, ARCH_CONVERT)));
1682         right->bb_rightsib = left->bb_rightsib; /* INT_: direct copy */
1683         INT_SET(left->bb_rightsib, ARCH_CONVERT, rbno);
1684         INT_SET(right->bb_leftsib, ARCH_CONVERT, lbno);
1685         xfs_alloc_log_block(cur->bc_tp, rbp, XFS_BB_ALL_BITS);
1686         xfs_alloc_log_block(cur->bc_tp, lbp, XFS_BB_NUMRECS | XFS_BB_RIGHTSIB);
1687         /*
1688          * If there's a block to the new block's right, make that block
1689          * point back to right instead of to left.
1690          */
1691         if (INT_GET(right->bb_rightsib, ARCH_CONVERT) != NULLAGBLOCK) {
1692                 xfs_alloc_block_t       *rrblock;       /* rr btree block */
1693                 xfs_buf_t               *rrbp;          /* buffer for rrblock */
1694
1695                 if ((error = xfs_btree_read_bufs(cur->bc_mp, cur->bc_tp,
1696                                 cur->bc_private.a.agno, INT_GET(right->bb_rightsib, ARCH_CONVERT), 0,
1697                                 &rrbp, XFS_ALLOC_BTREE_REF)))
1698                         return error;
1699                 rrblock = XFS_BUF_TO_ALLOC_BLOCK(rrbp);
1700                 if ((error = xfs_btree_check_sblock(cur, rrblock, level, rrbp)))
1701                         return error;
1702                 INT_SET(rrblock->bb_leftsib, ARCH_CONVERT, rbno);
1703                 xfs_alloc_log_block(cur->bc_tp, rrbp, XFS_BB_LEFTSIB);
1704         }
1705         /*
1706          * If the cursor is really in the right block, move it there.
1707          * If it's just pointing past the last entry in left, then we'll
1708          * insert there, so don't change anything in that case.
1709          */
1710         if (cur->bc_ptrs[level] > INT_GET(left->bb_numrecs, ARCH_CONVERT) + 1) {
1711                 xfs_btree_setbuf(cur, level, rbp);
1712                 cur->bc_ptrs[level] -= INT_GET(left->bb_numrecs, ARCH_CONVERT);
1713         }
1714         /*
1715          * If there are more levels, we'll need another cursor which refers to
1716          * the right block, no matter where this cursor was.
1717          */
1718         if (level + 1 < cur->bc_nlevels) {
1719                 if ((error = xfs_btree_dup_cursor(cur, curp)))
1720                         return error;
1721                 (*curp)->bc_ptrs[level + 1]++;
1722         }
1723         *bnop = rbno;
1724         *stat = 1;
1725         return 0;
1726 }
1727
1728 /*
1729  * Update keys at all levels from here to the root along the cursor's path.
1730  */
1731 STATIC int                              /* error */
1732 xfs_alloc_updkey(
1733         xfs_btree_cur_t         *cur,   /* btree cursor */
1734         xfs_alloc_key_t         *keyp,  /* new key value to update to */
1735         int                     level)  /* starting level for update */
1736 {
1737         int                     ptr;    /* index of key in block */
1738
1739         /*
1740          * Go up the tree from this level toward the root.
1741          * At each level, update the key value to the value input.
1742          * Stop when we reach a level where the cursor isn't pointing
1743          * at the first entry in the block.
1744          */
1745         for (ptr = 1; ptr == 1 && level < cur->bc_nlevels; level++) {
1746                 xfs_alloc_block_t       *block; /* btree block */
1747                 xfs_buf_t               *bp;    /* buffer for block */
1748 #ifdef DEBUG
1749                 int                     error;  /* error return value */
1750 #endif
1751                 xfs_alloc_key_t         *kp;    /* ptr to btree block keys */
1752
1753                 bp = cur->bc_bufs[level];
1754                 block = XFS_BUF_TO_ALLOC_BLOCK(bp);
1755 #ifdef DEBUG
1756                 if ((error = xfs_btree_check_sblock(cur, block, level, bp)))
1757                         return error;
1758 #endif
1759                 ptr = cur->bc_ptrs[level];
1760                 kp = XFS_ALLOC_KEY_ADDR(block, ptr, cur);
1761                 *kp = *keyp;
1762                 xfs_alloc_log_keys(cur, bp, ptr, ptr);
1763         }
1764         return 0;
1765 }
1766
1767 /*
1768  * Externally visible routines.
1769  */
1770
1771 /*
1772  * Decrement cursor by one record at the level.
1773  * For nonzero levels the leaf-ward information is untouched.
1774  */
1775 int                                     /* error */
1776 xfs_alloc_decrement(
1777         xfs_btree_cur_t         *cur,   /* btree cursor */
1778         int                     level,  /* level in btree, 0 is leaf */
1779         int                     *stat)  /* success/failure */
1780 {
1781         xfs_alloc_block_t       *block; /* btree block */
1782         int                     error;  /* error return value */
1783         int                     lev;    /* btree level */
1784
1785         ASSERT(level < cur->bc_nlevels);
1786         /*
1787          * Read-ahead to the left at this level.
1788          */
1789         xfs_btree_readahead(cur, level, XFS_BTCUR_LEFTRA);
1790         /*
1791          * Decrement the ptr at this level.  If we're still in the block
1792          * then we're done.
1793          */
1794         if (--cur->bc_ptrs[level] > 0) {
1795                 *stat = 1;
1796                 return 0;
1797         }
1798         /*
1799          * Get a pointer to the btree block.
1800          */
1801         block = XFS_BUF_TO_ALLOC_BLOCK(cur->bc_bufs[level]);
1802 #ifdef DEBUG
1803         if ((error = xfs_btree_check_sblock(cur, block, level,
1804                         cur->bc_bufs[level])))
1805                 return error;
1806 #endif
1807         /*
1808          * If we just went off the left edge of the tree, return failure.
1809          */
1810         if (INT_GET(block->bb_leftsib, ARCH_CONVERT) == NULLAGBLOCK) {
1811                 *stat = 0;
1812                 return 0;
1813         }
1814         /*
1815          * March up the tree decrementing pointers.
1816          * Stop when we don't go off the left edge of a block.
1817          */
1818         for (lev = level + 1; lev < cur->bc_nlevels; lev++) {
1819                 if (--cur->bc_ptrs[lev] > 0)
1820                         break;
1821                 /*
1822                  * Read-ahead the left block, we're going to read it
1823                  * in the next loop.
1824                  */
1825                 xfs_btree_readahead(cur, lev, XFS_BTCUR_LEFTRA);
1826         }
1827         /*
1828          * If we went off the root then we are seriously confused.
1829          */
1830         ASSERT(lev < cur->bc_nlevels);
1831         /*
1832          * Now walk back down the tree, fixing up the cursor's buffer
1833          * pointers and key numbers.
1834          */
1835         for (block = XFS_BUF_TO_ALLOC_BLOCK(cur->bc_bufs[lev]); lev > level; ) {
1836                 xfs_agblock_t   agbno;  /* block number of btree block */
1837                 xfs_buf_t       *bp;    /* buffer pointer for block */
1838
1839                 agbno = INT_GET(*XFS_ALLOC_PTR_ADDR(block, cur->bc_ptrs[lev], cur), ARCH_CONVERT);
1840                 if ((error = xfs_btree_read_bufs(cur->bc_mp, cur->bc_tp,
1841                                 cur->bc_private.a.agno, agbno, 0, &bp,
1842                                 XFS_ALLOC_BTREE_REF)))
1843                         return error;
1844                 lev--;
1845                 xfs_btree_setbuf(cur, lev, bp);
1846                 block = XFS_BUF_TO_ALLOC_BLOCK(bp);
1847                 if ((error = xfs_btree_check_sblock(cur, block, lev, bp)))
1848                         return error;
1849                 cur->bc_ptrs[lev] = INT_GET(block->bb_numrecs, ARCH_CONVERT);
1850         }
1851         *stat = 1;
1852         return 0;
1853 }
1854
1855 /*
1856  * Delete the record pointed to by cur.
1857  * The cursor refers to the place where the record was (could be inserted)
1858  * when the operation returns.
1859  */
1860 int                                     /* error */
1861 xfs_alloc_delete(
1862         xfs_btree_cur_t *cur,           /* btree cursor */
1863         int             *stat)          /* success/failure */
1864 {
1865         int             error;          /* error return value */
1866         int             i;              /* result code */
1867         int             level;          /* btree level */
1868
1869         /*
1870          * Go up the tree, starting at leaf level.
1871          * If 2 is returned then a join was done; go to the next level.
1872          * Otherwise we are done.
1873          */
1874         for (level = 0, i = 2; i == 2; level++) {
1875                 if ((error = xfs_alloc_delrec(cur, level, &i)))
1876                         return error;
1877         }
1878         if (i == 0) {
1879                 for (level = 1; level < cur->bc_nlevels; level++) {
1880                         if (cur->bc_ptrs[level] == 0) {
1881                                 if ((error = xfs_alloc_decrement(cur, level, &i)))
1882                                         return error;
1883                                 break;
1884                         }
1885                 }
1886         }
1887         *stat = i;
1888         return 0;
1889 }
1890
1891 /*
1892  * Get the data from the pointed-to record.
1893  */
1894 int                                     /* error */
1895 xfs_alloc_get_rec(
1896         xfs_btree_cur_t         *cur,   /* btree cursor */
1897         xfs_agblock_t           *bno,   /* output: starting block of extent */
1898         xfs_extlen_t            *len,   /* output: length of extent */
1899         int                     *stat)  /* output: success/failure */
1900 {
1901         xfs_alloc_block_t       *block; /* btree block */
1902 #ifdef DEBUG
1903         int                     error;  /* error return value */
1904 #endif
1905         int                     ptr;    /* record number */
1906
1907         ptr = cur->bc_ptrs[0];
1908         block = XFS_BUF_TO_ALLOC_BLOCK(cur->bc_bufs[0]);
1909 #ifdef DEBUG
1910         if ((error = xfs_btree_check_sblock(cur, block, 0, cur->bc_bufs[0])))
1911                 return error;
1912 #endif
1913         /*
1914          * Off the right end or left end, return failure.
1915          */
1916         if (ptr > INT_GET(block->bb_numrecs, ARCH_CONVERT) || ptr <= 0) {
1917                 *stat = 0;
1918                 return 0;
1919         }
1920         /*
1921          * Point to the record and extract its data.
1922          */
1923         {
1924                 xfs_alloc_rec_t         *rec;   /* record data */
1925
1926                 rec = XFS_ALLOC_REC_ADDR(block, ptr, cur);
1927                 *bno = INT_GET(rec->ar_startblock, ARCH_CONVERT);
1928                 *len = INT_GET(rec->ar_blockcount, ARCH_CONVERT);
1929         }
1930         *stat = 1;
1931         return 0;
1932 }
1933
1934 /*
1935  * Increment cursor by one record at the level.
1936  * For nonzero levels the leaf-ward information is untouched.
1937  */
1938 int                                     /* error */
1939 xfs_alloc_increment(
1940         xfs_btree_cur_t         *cur,   /* btree cursor */
1941         int                     level,  /* level in btree, 0 is leaf */
1942         int                     *stat)  /* success/failure */
1943 {
1944         xfs_alloc_block_t       *block; /* btree block */
1945         xfs_buf_t               *bp;    /* tree block buffer */
1946         int                     error;  /* error return value */
1947         int                     lev;    /* btree level */
1948
1949         ASSERT(level < cur->bc_nlevels);
1950         /*
1951          * Read-ahead to the right at this level.
1952          */
1953         xfs_btree_readahead(cur, level, XFS_BTCUR_RIGHTRA);
1954         /*
1955          * Get a pointer to the btree block.
1956          */
1957         bp = cur->bc_bufs[level];
1958         block = XFS_BUF_TO_ALLOC_BLOCK(bp);
1959 #ifdef DEBUG
1960         if ((error = xfs_btree_check_sblock(cur, block, level, bp)))
1961                 return error;
1962 #endif
1963         /*
1964          * Increment the ptr at this level.  If we're still in the block
1965          * then we're done.
1966          */
1967         if (++cur->bc_ptrs[level] <= INT_GET(block->bb_numrecs, ARCH_CONVERT)) {
1968                 *stat = 1;
1969                 return 0;
1970         }
1971         /*
1972          * If we just went off the right edge of the tree, return failure.
1973          */
1974         if (INT_GET(block->bb_rightsib, ARCH_CONVERT) == NULLAGBLOCK) {
1975                 *stat = 0;
1976                 return 0;
1977         }
1978         /*
1979          * March up the tree incrementing pointers.
1980          * Stop when we don't go off the right edge of a block.
1981          */
1982         for (lev = level + 1; lev < cur->bc_nlevels; lev++) {
1983                 bp = cur->bc_bufs[lev];
1984                 block = XFS_BUF_TO_ALLOC_BLOCK(bp);
1985 #ifdef DEBUG
1986                 if ((error = xfs_btree_check_sblock(cur, block, lev, bp)))
1987                         return error;
1988 #endif
1989                 if (++cur->bc_ptrs[lev] <= INT_GET(block->bb_numrecs, ARCH_CONVERT))
1990                         break;
1991                 /*
1992                  * Read-ahead the right block, we're going to read it
1993                  * in the next loop.
1994                  */
1995                 xfs_btree_readahead(cur, lev, XFS_BTCUR_RIGHTRA);
1996         }
1997         /*
1998          * If we went off the root then we are seriously confused.
1999          */
2000         ASSERT(lev < cur->bc_nlevels);
2001         /*
2002          * Now walk back down the tree, fixing up the cursor's buffer
2003          * pointers and key numbers.
2004          */
2005         for (bp = cur->bc_bufs[lev], block = XFS_BUF_TO_ALLOC_BLOCK(bp);
2006              lev > level; ) {
2007                 xfs_agblock_t   agbno;  /* block number of btree block */
2008
2009                 agbno = INT_GET(*XFS_ALLOC_PTR_ADDR(block, cur->bc_ptrs[lev], cur), ARCH_CONVERT);
2010                 if ((error = xfs_btree_read_bufs(cur->bc_mp, cur->bc_tp,
2011                                 cur->bc_private.a.agno, agbno, 0, &bp,
2012                                 XFS_ALLOC_BTREE_REF)))
2013                         return error;
2014                 lev--;
2015                 xfs_btree_setbuf(cur, lev, bp);
2016                 block = XFS_BUF_TO_ALLOC_BLOCK(bp);
2017                 if ((error = xfs_btree_check_sblock(cur, block, lev, bp)))
2018                         return error;
2019                 cur->bc_ptrs[lev] = 1;
2020         }
2021         *stat = 1;
2022         return 0;
2023 }
2024
2025 /*
2026  * Insert the current record at the point referenced by cur.
2027  * The cursor may be inconsistent on return if splits have been done.
2028  */
2029 int                                     /* error */
2030 xfs_alloc_insert(
2031         xfs_btree_cur_t *cur,           /* btree cursor */
2032         int             *stat)          /* success/failure */
2033 {
2034         int             error;          /* error return value */
2035         int             i;              /* result value, 0 for failure */
2036         int             level;          /* current level number in btree */
2037         xfs_agblock_t   nbno;           /* new block number (split result) */
2038         xfs_btree_cur_t *ncur;          /* new cursor (split result) */
2039         xfs_alloc_rec_t nrec;           /* record being inserted this level */
2040         xfs_btree_cur_t *pcur;          /* previous level's cursor */
2041
2042         level = 0;
2043         nbno = NULLAGBLOCK;
2044         INT_SET(nrec.ar_startblock, ARCH_CONVERT, cur->bc_rec.a.ar_startblock);
2045         INT_SET(nrec.ar_blockcount, ARCH_CONVERT, cur->bc_rec.a.ar_blockcount);
2046         ncur = (xfs_btree_cur_t *)0;
2047         pcur = cur;
2048         /*
2049          * Loop going up the tree, starting at the leaf level.
2050          * Stop when we don't get a split block, that must mean that
2051          * the insert is finished with this level.
2052          */
2053         do {
2054                 /*
2055                  * Insert nrec/nbno into this level of the tree.
2056                  * Note if we fail, nbno will be null.
2057                  */
2058                 if ((error = xfs_alloc_insrec(pcur, level++, &nbno, &nrec, &ncur,
2059                                 &i))) {
2060                         if (pcur != cur)
2061                                 xfs_btree_del_cursor(pcur, XFS_BTREE_ERROR);
2062                         return error;
2063                 }
2064                 /*
2065                  * See if the cursor we just used is trash.
2066                  * Can't trash the caller's cursor, but otherwise we should
2067                  * if ncur is a new cursor or we're about to be done.
2068                  */
2069                 if (pcur != cur && (ncur || nbno == NULLAGBLOCK)) {
2070                         cur->bc_nlevels = pcur->bc_nlevels;
2071                         xfs_btree_del_cursor(pcur, XFS_BTREE_NOERROR);
2072                 }
2073                 /*
2074                  * If we got a new cursor, switch to it.
2075                  */
2076                 if (ncur) {
2077                         pcur = ncur;
2078                         ncur = (xfs_btree_cur_t *)0;
2079                 }
2080         } while (nbno != NULLAGBLOCK);
2081         *stat = i;
2082         return 0;
2083 }
2084
2085 /*
2086  * Lookup the record equal to [bno, len] in the btree given by cur.
2087  */
2088 int                                     /* error */
2089 xfs_alloc_lookup_eq(
2090         xfs_btree_cur_t *cur,           /* btree cursor */
2091         xfs_agblock_t   bno,            /* starting block of extent */
2092         xfs_extlen_t    len,            /* length of extent */
2093         int             *stat)          /* success/failure */
2094 {
2095         cur->bc_rec.a.ar_startblock = bno;
2096         cur->bc_rec.a.ar_blockcount = len;
2097         return xfs_alloc_lookup(cur, XFS_LOOKUP_EQ, stat);
2098 }
2099
2100 /*
2101  * Lookup the first record greater than or equal to [bno, len]
2102  * in the btree given by cur.
2103  */
2104 int                                     /* error */
2105 xfs_alloc_lookup_ge(
2106         xfs_btree_cur_t *cur,           /* btree cursor */
2107         xfs_agblock_t   bno,            /* starting block of extent */
2108         xfs_extlen_t    len,            /* length of extent */
2109         int             *stat)          /* success/failure */
2110 {
2111         cur->bc_rec.a.ar_startblock = bno;
2112         cur->bc_rec.a.ar_blockcount = len;
2113         return xfs_alloc_lookup(cur, XFS_LOOKUP_GE, stat);
2114 }
2115
2116 /*
2117  * Lookup the first record less than or equal to [bno, len]
2118  * in the btree given by cur.
2119  */
2120 int                                     /* error */
2121 xfs_alloc_lookup_le(
2122         xfs_btree_cur_t *cur,           /* btree cursor */
2123         xfs_agblock_t   bno,            /* starting block of extent */
2124         xfs_extlen_t    len,            /* length of extent */
2125         int             *stat)          /* success/failure */
2126 {
2127         cur->bc_rec.a.ar_startblock = bno;
2128         cur->bc_rec.a.ar_blockcount = len;
2129         return xfs_alloc_lookup(cur, XFS_LOOKUP_LE, stat);
2130 }
2131
2132 /*
2133  * Update the record referred to by cur, to the value given by [bno, len].
2134  * This either works (return 0) or gets an EFSCORRUPTED error.
2135  */
2136 int                                     /* error */
2137 xfs_alloc_update(
2138         xfs_btree_cur_t         *cur,   /* btree cursor */
2139         xfs_agblock_t           bno,    /* starting block of extent */
2140         xfs_extlen_t            len)    /* length of extent */
2141 {
2142         xfs_alloc_block_t       *block; /* btree block to update */
2143         int                     error;  /* error return value */
2144         int                     ptr;    /* current record number (updating) */
2145
2146         ASSERT(len > 0);
2147         /*
2148          * Pick up the a.g. freelist struct and the current block.
2149          */
2150         block = XFS_BUF_TO_ALLOC_BLOCK(cur->bc_bufs[0]);
2151 #ifdef DEBUG
2152         if ((error = xfs_btree_check_sblock(cur, block, 0, cur->bc_bufs[0])))
2153                 return error;
2154 #endif
2155         /*
2156          * Get the address of the rec to be updated.
2157          */
2158         ptr = cur->bc_ptrs[0];
2159         {
2160                 xfs_alloc_rec_t         *rp;    /* pointer to updated record */
2161
2162                 rp = XFS_ALLOC_REC_ADDR(block, ptr, cur);
2163                 /*
2164                  * Fill in the new contents and log them.
2165                  */
2166                 INT_SET(rp->ar_startblock, ARCH_CONVERT, bno);
2167                 INT_SET(rp->ar_blockcount, ARCH_CONVERT, len);
2168                 xfs_alloc_log_recs(cur, cur->bc_bufs[0], ptr, ptr);
2169         }
2170         /*
2171          * If it's the by-size btree and it's the last leaf block and
2172          * it's the last record... then update the size of the longest
2173          * extent in the a.g., which we cache in the a.g. freelist header.
2174          */
2175         if (cur->bc_btnum == XFS_BTNUM_CNT &&
2176             INT_GET(block->bb_rightsib, ARCH_CONVERT) == NULLAGBLOCK &&
2177             ptr == INT_GET(block->bb_numrecs, ARCH_CONVERT)) {
2178                 xfs_agf_t       *agf;   /* a.g. freespace header */
2179                 xfs_agnumber_t  seqno;
2180
2181                 agf = XFS_BUF_TO_AGF(cur->bc_private.a.agbp);
2182                 seqno = INT_GET(agf->agf_seqno, ARCH_CONVERT);
2183                 cur->bc_mp->m_perag[seqno].pagf_longest = len;
2184                 INT_SET(agf->agf_longest, ARCH_CONVERT, len);
2185                 xfs_alloc_log_agf(cur->bc_tp, cur->bc_private.a.agbp,
2186                         XFS_AGF_LONGEST);
2187         }
2188         /*
2189          * Updating first record in leaf. Pass new key value up to our parent.
2190          */
2191         if (ptr == 1) {
2192                 xfs_alloc_key_t key;    /* key containing [bno, len] */
2193
2194                 INT_SET(key.ar_startblock, ARCH_CONVERT, bno);
2195                 INT_SET(key.ar_blockcount, ARCH_CONVERT, len);
2196                 if ((error = xfs_alloc_updkey(cur, &key, 1)))
2197                         return error;
2198         }
2199         return 0;
2200 }