fs/xfs/xfs_alloc_btree.c

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