fs/xfs/xfs_bmap_btree.c

   1 /*
   2  * Copyright (c) 2000-2003,2005 Silicon Graphics, Inc.
   3  * All Rights Reserved.
   4  *
   5  * This program is free software; you can redistribute it and/or
   6  * modify it under the terms of the GNU General Public License as
   7  * published by the Free Software Foundation.
   8  *
   9  * This program is distributed in the hope that it would be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  * GNU General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program; if not, write the Free Software Foundation,
  16  * Inc.,  51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  17  */
  18 #include "xfs.h"
  19 #include "xfs_fs.h"
  20 #include "xfs_types.h"
  21 #include "xfs_bit.h"
  22 #include "xfs_log.h"
  23 #include "xfs_inum.h"
  24 #include "xfs_trans.h"
  25 #include "xfs_sb.h"
  26 #include "xfs_ag.h"
  27 #include "xfs_dir2.h"
  28 #include "xfs_dmapi.h"
  29 #include "xfs_mount.h"
  30 #include "xfs_bmap_btree.h"
  31 #include "xfs_alloc_btree.h"
  32 #include "xfs_ialloc_btree.h"
  33 #include "xfs_dir2_sf.h"
  34 #include "xfs_attr_sf.h"
  35 #include "xfs_dinode.h"
  36 #include "xfs_inode.h"
  37 #include "xfs_inode_item.h"
  38 #include "xfs_alloc.h"
  39 #include "xfs_btree.h"
  40 #include "xfs_btree_trace.h"
  41 #include "xfs_ialloc.h"
  42 #include "xfs_itable.h"
  43 #include "xfs_bmap.h"
  44 #include "xfs_error.h"
  45 #include "xfs_quota.h"
  46
  47 /*
  48  * Prototypes for internal btree functions.
  49  */
  50
  51
  52 STATIC int xfs_bmbt_killroot(xfs_btree_cur_t *);
  53 STATIC void xfs_bmbt_log_keys(xfs_btree_cur_t *, xfs_buf_t *, int, int);
  54 STATIC void xfs_bmbt_log_ptrs(xfs_btree_cur_t *, xfs_buf_t *, int, int);
  55 STATIC int xfs_bmbt_lshift(xfs_btree_cur_t *, int, int *);
  56 STATIC int xfs_bmbt_split(xfs_btree_cur_t *, int, xfs_fsblock_t *,
  57                 __uint64_t *, xfs_btree_cur_t **, int *);
  58
  59 #undef EXIT
  60
  61 #define ENTRY   XBT_ENTRY
  62 #define ERROR   XBT_ERROR
  63 #define EXIT    XBT_EXIT
  64
  65 /*
  66  * Keep the XFS_BMBT_TRACE_ names around for now until all code using them
  67  * is converted to be generic and thus switches to the XFS_BTREE_TRACE_ names.
  68  */
  69 #define XFS_BMBT_TRACE_ARGBI(c,b,i) \
  70         XFS_BTREE_TRACE_ARGBI(c,b,i)
  71 #define XFS_BMBT_TRACE_ARGBII(c,b,i,j) \
  72         XFS_BTREE_TRACE_ARGBII(c,b,i,j)
  73 #define XFS_BMBT_TRACE_ARGFFFI(c,o,b,i,j) \
  74         XFS_BTREE_TRACE_ARGFFFI(c,o,b,i,j)
  75 #define XFS_BMBT_TRACE_ARGI(c,i) \
  76         XFS_BTREE_TRACE_ARGI(c,i)
  77 #define XFS_BMBT_TRACE_ARGIFK(c,i,f,s) \
  78         XFS_BTREE_TRACE_ARGIPK(c,i,(union xfs_btree_ptr)f,s)
  79 #define XFS_BMBT_TRACE_ARGIFR(c,i,f,r) \
  80         XFS_BTREE_TRACE_ARGIPR(c,i, \
  81                 (union xfs_btree_ptr)f, (union xfs_btree_rec *)r)
  82 #define XFS_BMBT_TRACE_ARGIK(c,i,k) \
  83         XFS_BTREE_TRACE_ARGIK(c,i,(union xfs_btree_key *)k)
  84 #define XFS_BMBT_TRACE_CURSOR(c,s) \
  85         XFS_BTREE_TRACE_CURSOR(c,s)
  86
  87
  88 /*
  89  * Internal functions.
  90  */
  91
  92 /*
  93  * Delete record pointed to by cur/level.
  94  */
  95 STATIC int                                      /* error */
  96 xfs_bmbt_delrec(
  97         xfs_btree_cur_t         *cur,
  98         int                     level,
  99         int                     *stat)          /* success/failure */
 100 {
 101         xfs_bmbt_block_t        *block;         /* bmap btree block */
 102         xfs_fsblock_t           bno;            /* fs-relative block number */
 103         xfs_buf_t               *bp;            /* buffer for block */
 104         int                     error;          /* error return value */
 105         int                     i;              /* loop counter */
 106         int                     j;              /* temp state */
 107         xfs_bmbt_key_t          key;            /* bmap btree key */
 108         xfs_bmbt_key_t          *kp=NULL;       /* pointer to bmap btree key */
 109         xfs_fsblock_t           lbno;           /* left sibling block number */
 110         xfs_buf_t               *lbp;           /* left buffer pointer */
 111         xfs_bmbt_block_t        *left;          /* left btree block */
 112         xfs_bmbt_key_t          *lkp;           /* left btree key */
 113         xfs_bmbt_ptr_t          *lpp;           /* left address pointer */
 114         int                     lrecs=0;        /* left record count */
 115         xfs_bmbt_rec_t          *lrp;           /* left record pointer */
 116         xfs_mount_t             *mp;            /* file system mount point */
 117         xfs_bmbt_ptr_t          *pp;            /* pointer to bmap block addr */
 118         int                     ptr;            /* key/record index */
 119         xfs_fsblock_t           rbno;           /* right sibling block number */
 120         xfs_buf_t               *rbp;           /* right buffer pointer */
 121         xfs_bmbt_block_t        *right;         /* right btree block */
 122         xfs_bmbt_key_t          *rkp;           /* right btree key */
 123         xfs_bmbt_rec_t          *rp;            /* pointer to bmap btree rec */
 124         xfs_bmbt_ptr_t          *rpp;           /* right address pointer */
 125         xfs_bmbt_block_t        *rrblock;       /* right-right btree block */
 126         xfs_buf_t               *rrbp;          /* right-right buffer pointer */
 127         int                     rrecs=0;        /* right record count */
 128         xfs_bmbt_rec_t          *rrp;           /* right record pointer */
 129         xfs_btree_cur_t         *tcur;          /* temporary btree cursor */
 130         int                     numrecs;        /* temporary numrec count */
 131         int                     numlrecs, numrrecs;
 132
 133         XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
 134         XFS_BMBT_TRACE_ARGI(cur, level);
 135         ptr = cur->bc_ptrs[level];
 136         tcur = NULL;
 137         if (ptr == 0) {
 138                 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
 139                 *stat = 0;
 140                 return 0;
 141         }
 142         block = xfs_bmbt_get_block(cur, level, &bp);
 143         numrecs = be16_to_cpu(block->bb_numrecs);
 144 #ifdef DEBUG
 145         if ((error = xfs_btree_check_lblock(cur, block, level, bp))) {
 146                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
 147                 goto error0;
 148         }
 149 #endif
 150         if (ptr > numrecs) {
 151                 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
 152                 *stat = 0;
 153                 return 0;
 154         }
 155         XFS_STATS_INC(xs_bmbt_delrec);
 156         if (level > 0) {
 157                 kp = XFS_BMAP_KEY_IADDR(block, 1, cur);
 158                 pp = XFS_BMAP_PTR_IADDR(block, 1, cur);
 159 #ifdef DEBUG
 160                 for (i = ptr; i < numrecs; i++) {
 161                         if ((error = xfs_btree_check_lptr_disk(cur, pp[i], level))) {
 162                                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
 163                                 goto error0;
 164                         }
 165                 }
 166 #endif
 167                 if (ptr < numrecs) {
 168                         memmove(&kp[ptr - 1], &kp[ptr],
 169                                 (numrecs - ptr) * sizeof(*kp));
 170                         memmove(&pp[ptr - 1], &pp[ptr],
 171                                 (numrecs - ptr) * sizeof(*pp));
 172                         xfs_bmbt_log_ptrs(cur, bp, ptr, numrecs - 1);
 173                         xfs_bmbt_log_keys(cur, bp, ptr, numrecs - 1);
 174                 }
 175         } else {
 176                 rp = XFS_BMAP_REC_IADDR(block, 1, cur);
 177                 if (ptr < numrecs) {
 178                         memmove(&rp[ptr - 1], &rp[ptr],
 179                                 (numrecs - ptr) * sizeof(*rp));
 180                         xfs_bmbt_log_recs(cur, bp, ptr, numrecs - 1);
 181                 }
 182                 if (ptr == 1) {
 183                         key.br_startoff =
 184                                 cpu_to_be64(xfs_bmbt_disk_get_startoff(rp));
 185                         kp = &key;
 186                 }
 187         }
 188         numrecs--;
 189         block->bb_numrecs = cpu_to_be16(numrecs);
 190         xfs_bmbt_log_block(cur, bp, XFS_BB_NUMRECS);
 191         /*
 192          * We're at the root level.
 193          * First, shrink the root block in-memory.
 194          * Try to get rid of the next level down.
 195          * If we can't then there's nothing left to do.
 196          */
 197         if (level == cur->bc_nlevels - 1) {
 198                 xfs_iroot_realloc(cur->bc_private.b.ip, -1,
 199                         cur->bc_private.b.whichfork);
 200                 if ((error = xfs_bmbt_killroot(cur))) {
 201                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
 202                         goto error0;
 203                 }
 204                 if (level > 0 && (error = xfs_btree_decrement(cur, level, &j))) {
 205                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
 206                         goto error0;
 207                 }
 208                 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
 209                 *stat = 1;
 210                 return 0;
 211         }
 212         if (ptr == 1 && (error = xfs_btree_updkey(cur, (union xfs_btree_key *)kp, level + 1))) {
 213                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
 214                 goto error0;
 215         }
 216         if (numrecs >= XFS_BMAP_BLOCK_IMINRECS(level, cur)) {
 217                 if (level > 0 && (error = xfs_btree_decrement(cur, level, &j))) {
 218                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
 219                         goto error0;
 220                 }
 221                 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
 222                 *stat = 1;
 223                 return 0;
 224         }
 225         rbno = be64_to_cpu(block->bb_rightsib);
 226         lbno = be64_to_cpu(block->bb_leftsib);
 227         /*
 228          * One child of root, need to get a chance to copy its contents
 229          * into the root and delete it. Can't go up to next level,
 230          * there's nothing to delete there.
 231          */
 232         if (lbno == NULLFSBLOCK && rbno == NULLFSBLOCK &&
 233             level == cur->bc_nlevels - 2) {
 234                 if ((error = xfs_bmbt_killroot(cur))) {
 235                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
 236                         goto error0;
 237                 }
 238                 if (level > 0 && (error = xfs_btree_decrement(cur, level, &i))) {
 239                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
 240                         goto error0;
 241                 }
 242                 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
 243                 *stat = 1;
 244                 return 0;
 245         }
 246         ASSERT(rbno != NULLFSBLOCK || lbno != NULLFSBLOCK);
 247         if ((error = xfs_btree_dup_cursor(cur, &tcur))) {
 248                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
 249                 goto error0;
 250         }
 251         bno = NULLFSBLOCK;
 252         if (rbno != NULLFSBLOCK) {
 253                 i = xfs_btree_lastrec(tcur, level);
 254                 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
 255                 if ((error = xfs_btree_increment(tcur, level, &i))) {
 256                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
 257                         goto error0;
 258                 }
 259                 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
 260                 i = xfs_btree_lastrec(tcur, level);
 261                 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
 262                 rbp = tcur->bc_bufs[level];
 263                 right = XFS_BUF_TO_BMBT_BLOCK(rbp);
 264 #ifdef DEBUG
 265                 if ((error = xfs_btree_check_lblock(cur, right, level, rbp))) {
 266                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
 267                         goto error0;
 268                 }
 269 #endif
 270                 bno = be64_to_cpu(right->bb_leftsib);
 271                 if (be16_to_cpu(right->bb_numrecs) - 1 >=
 272                     XFS_BMAP_BLOCK_IMINRECS(level, cur)) {
 273                         if ((error = xfs_bmbt_lshift(tcur, level, &i))) {
 274                                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
 275                                 goto error0;
 276                         }
 277                         if (i) {
 278                                 ASSERT(be16_to_cpu(block->bb_numrecs) >=
 279                                        XFS_BMAP_BLOCK_IMINRECS(level, tcur));
 280                                 xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
 281                                 tcur = NULL;
 282                                 if (level > 0) {
 283                                         if ((error = xfs_btree_decrement(cur,
 284                                                         level, &i))) {
 285                                                 XFS_BMBT_TRACE_CURSOR(cur,
 286                                                         ERROR);
 287                                                 goto error0;
 288                                         }
 289                                 }
 290                                 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
 291                                 *stat = 1;
 292                                 return 0;
 293                         }
 294                 }
 295                 rrecs = be16_to_cpu(right->bb_numrecs);
 296                 if (lbno != NULLFSBLOCK) {
 297                         i = xfs_btree_firstrec(tcur, level);
 298                         XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
 299                         if ((error = xfs_btree_decrement(tcur, level, &i))) {
 300                                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
 301                                 goto error0;
 302                         }
 303                         XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
 304                 }
 305         }
 306         if (lbno != NULLFSBLOCK) {
 307                 i = xfs_btree_firstrec(tcur, level);
 308                 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
 309                 /*
 310                  * decrement to last in block
 311                  */
 312                 if ((error = xfs_btree_decrement(tcur, level, &i))) {
 313                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
 314                         goto error0;
 315                 }
 316                 i = xfs_btree_firstrec(tcur, level);
 317                 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
 318                 lbp = tcur->bc_bufs[level];
 319                 left = XFS_BUF_TO_BMBT_BLOCK(lbp);
 320 #ifdef DEBUG
 321                 if ((error = xfs_btree_check_lblock(cur, left, level, lbp))) {
 322                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
 323                         goto error0;
 324                 }
 325 #endif
 326                 bno = be64_to_cpu(left->bb_rightsib);
 327                 if (be16_to_cpu(left->bb_numrecs) - 1 >=
 328                     XFS_BMAP_BLOCK_IMINRECS(level, cur)) {
 329                         if ((error = xfs_btree_rshift(tcur, level, &i))) {
 330                                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
 331                                 goto error0;
 332                         }
 333                         if (i) {
 334                                 ASSERT(be16_to_cpu(block->bb_numrecs) >=
 335                                        XFS_BMAP_BLOCK_IMINRECS(level, tcur));
 336                                 xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
 337                                 tcur = NULL;
 338                                 if (level == 0)
 339                                         cur->bc_ptrs[0]++;
 340                                 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
 341                                 *stat = 1;
 342                                 return 0;
 343                         }
 344                 }
 345                 lrecs = be16_to_cpu(left->bb_numrecs);
 346         }
 347         xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
 348         tcur = NULL;
 349         mp = cur->bc_mp;
 350         ASSERT(bno != NULLFSBLOCK);
 351         if (lbno != NULLFSBLOCK &&
 352             lrecs + be16_to_cpu(block->bb_numrecs) <= XFS_BMAP_BLOCK_IMAXRECS(level, cur)) {
 353                 rbno = bno;
 354                 right = block;
 355                 rbp = bp;
 356                 if ((error = xfs_btree_read_bufl(mp, cur->bc_tp, lbno, 0, &lbp,
 357                                 XFS_BMAP_BTREE_REF))) {
 358                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
 359                         goto error0;
 360                 }
 361                 left = XFS_BUF_TO_BMBT_BLOCK(lbp);
 362                 if ((error = xfs_btree_check_lblock(cur, left, level, lbp))) {
 363                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
 364                         goto error0;
 365                 }
 366         } else if (rbno != NULLFSBLOCK &&
 367                    rrecs + be16_to_cpu(block->bb_numrecs) <=
 368                    XFS_BMAP_BLOCK_IMAXRECS(level, cur)) {
 369                 lbno = bno;
 370                 left = block;
 371                 lbp = bp;
 372                 if ((error = xfs_btree_read_bufl(mp, cur->bc_tp, rbno, 0, &rbp,
 373                                 XFS_BMAP_BTREE_REF))) {
 374                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
 375                         goto error0;
 376                 }
 377                 right = XFS_BUF_TO_BMBT_BLOCK(rbp);
 378                 if ((error = xfs_btree_check_lblock(cur, right, level, rbp))) {
 379                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
 380                         goto error0;
 381                 }
 382                 lrecs = be16_to_cpu(left->bb_numrecs);
 383         } else {
 384                 if (level > 0 && (error = xfs_btree_decrement(cur, level, &i))) {
 385                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
 386                         goto error0;
 387                 }
 388                 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
 389                 *stat = 1;
 390                 return 0;
 391         }
 392         numlrecs = be16_to_cpu(left->bb_numrecs);
 393         numrrecs = be16_to_cpu(right->bb_numrecs);
 394         if (level > 0) {
 395                 lkp = XFS_BMAP_KEY_IADDR(left, numlrecs + 1, cur);
 396                 lpp = XFS_BMAP_PTR_IADDR(left, numlrecs + 1, cur);
 397                 rkp = XFS_BMAP_KEY_IADDR(right, 1, cur);
 398                 rpp = XFS_BMAP_PTR_IADDR(right, 1, cur);
 399 #ifdef DEBUG
 400                 for (i = 0; i < numrrecs; i++) {
 401                         if ((error = xfs_btree_check_lptr_disk(cur, rpp[i], level))) {
 402                                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
 403                                 goto error0;
 404                         }
 405                 }
 406 #endif
 407                 memcpy(lkp, rkp, numrrecs * sizeof(*lkp));
 408                 memcpy(lpp, rpp, numrrecs * sizeof(*lpp));
 409                 xfs_bmbt_log_keys(cur, lbp, numlrecs + 1, numlrecs + numrrecs);
 410                 xfs_bmbt_log_ptrs(cur, lbp, numlrecs + 1, numlrecs + numrrecs);
 411         } else {
 412                 lrp = XFS_BMAP_REC_IADDR(left, numlrecs + 1, cur);
 413                 rrp = XFS_BMAP_REC_IADDR(right, 1, cur);
 414                 memcpy(lrp, rrp, numrrecs * sizeof(*lrp));
 415                 xfs_bmbt_log_recs(cur, lbp, numlrecs + 1, numlrecs + numrrecs);
 416         }
 417         be16_add_cpu(&left->bb_numrecs, numrrecs);
 418         left->bb_rightsib = right->bb_rightsib;
 419         xfs_bmbt_log_block(cur, lbp, XFS_BB_RIGHTSIB | XFS_BB_NUMRECS);
 420         if (be64_to_cpu(left->bb_rightsib) != NULLDFSBNO) {
 421                 if ((error = xfs_btree_read_bufl(mp, cur->bc_tp,
 422                                 be64_to_cpu(left->bb_rightsib),
 423                                 0, &rrbp, XFS_BMAP_BTREE_REF))) {
 424                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
 425                         goto error0;
 426                 }
 427                 rrblock = XFS_BUF_TO_BMBT_BLOCK(rrbp);
 428                 if ((error = xfs_btree_check_lblock(cur, rrblock, level, rrbp))) {
 429                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
 430                         goto error0;
 431                 }
 432                 rrblock->bb_leftsib = cpu_to_be64(lbno);
 433                 xfs_bmbt_log_block(cur, rrbp, XFS_BB_LEFTSIB);
 434         }
 435         xfs_bmap_add_free(XFS_DADDR_TO_FSB(mp, XFS_BUF_ADDR(rbp)), 1,
 436                 cur->bc_private.b.flist, mp);
 437         cur->bc_private.b.ip->i_d.di_nblocks--;
 438         xfs_trans_log_inode(cur->bc_tp, cur->bc_private.b.ip, XFS_ILOG_CORE);
 439         XFS_TRANS_MOD_DQUOT_BYINO(mp, cur->bc_tp, cur->bc_private.b.ip,
 440                         XFS_TRANS_DQ_BCOUNT, -1L);
 441         xfs_trans_binval(cur->bc_tp, rbp);
 442         if (bp != lbp) {
 443                 cur->bc_bufs[level] = lbp;
 444                 cur->bc_ptrs[level] += lrecs;
 445                 cur->bc_ra[level] = 0;
 446         } else if ((error = xfs_btree_increment(cur, level + 1, &i))) {
 447                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
 448                 goto error0;
 449         }
 450         if (level > 0)
 451                 cur->bc_ptrs[level]--;
 452         XFS_BMBT_TRACE_CURSOR(cur, EXIT);
 453         *stat = 2;
 454         return 0;
 455
 456 error0:
 457         if (tcur)
 458                 xfs_btree_del_cursor(tcur, XFS_BTREE_ERROR);
 459         return error;
 460 }
 461
 462 /*
 463  * Insert one record/level.  Return information to the caller
 464  * allowing the next level up to proceed if necessary.
 465  */
 466 STATIC int                                      /* error */
 467 xfs_bmbt_insrec(
 468         xfs_btree_cur_t         *cur,
 469         int                     level,
 470         xfs_fsblock_t           *bnop,
 471         xfs_bmbt_rec_t          *recp,
 472         xfs_btree_cur_t         **curp,
 473         int                     *stat)          /* no-go/done/continue */
 474 {
 475         xfs_bmbt_block_t        *block;         /* bmap btree block */
 476         xfs_buf_t               *bp;            /* buffer for block */
 477         int                     error;          /* error return value */
 478         int                     i;              /* loop index */
 479         xfs_bmbt_key_t          key;            /* bmap btree key */
 480         xfs_bmbt_key_t          *kp=NULL;       /* pointer to bmap btree key */
 481         int                     logflags;       /* inode logging flags */
 482         xfs_fsblock_t           nbno;           /* new block number */
 483         struct xfs_btree_cur    *ncur;          /* new btree cursor */
 484         __uint64_t              startoff;       /* new btree key value */
 485         xfs_bmbt_rec_t          nrec;           /* new record count */
 486         int                     optr;           /* old key/record index */
 487         xfs_bmbt_ptr_t          *pp;            /* pointer to bmap block addr */
 488         int                     ptr;            /* key/record index */
 489         xfs_bmbt_rec_t          *rp=NULL;       /* pointer to bmap btree rec */
 490         int                     numrecs;
 491
 492         ASSERT(level < cur->bc_nlevels);
 493         XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
 494         XFS_BMBT_TRACE_ARGIFR(cur, level, *bnop, recp);
 495         ncur = NULL;
 496         key.br_startoff = cpu_to_be64(xfs_bmbt_disk_get_startoff(recp));
 497         optr = ptr = cur->bc_ptrs[level];
 498         if (ptr == 0) {
 499                 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
 500                 *stat = 0;
 501                 return 0;
 502         }
 503         XFS_STATS_INC(xs_bmbt_insrec);
 504         block = xfs_bmbt_get_block(cur, level, &bp);
 505         numrecs = be16_to_cpu(block->bb_numrecs);
 506 #ifdef DEBUG
 507         if ((error = xfs_btree_check_lblock(cur, block, level, bp))) {
 508                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
 509                 return error;
 510         }
 511         if (ptr <= numrecs) {
 512                 if (level == 0) {
 513                         rp = XFS_BMAP_REC_IADDR(block, ptr, cur);
 514                         xfs_btree_check_rec(XFS_BTNUM_BMAP, recp, rp);
 515                 } else {
 516                         kp = XFS_BMAP_KEY_IADDR(block, ptr, cur);
 517                         xfs_btree_check_key(XFS_BTNUM_BMAP, &key, kp);
 518                 }
 519         }
 520 #endif
 521         nbno = NULLFSBLOCK;
 522         if (numrecs == XFS_BMAP_BLOCK_IMAXRECS(level, cur)) {
 523                 if (numrecs < XFS_BMAP_BLOCK_DMAXRECS(level, cur)) {
 524                         /*
 525                          * A root block, that can be made bigger.
 526                          */
 527                         xfs_iroot_realloc(cur->bc_private.b.ip, 1,
 528                                 cur->bc_private.b.whichfork);
 529                         block = xfs_bmbt_get_block(cur, level, &bp);
 530                 } else if (level == cur->bc_nlevels - 1) {
 531                         if ((error = xfs_bmbt_newroot(cur, &logflags, stat)) ||
 532                             *stat == 0) {
 533                                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
 534                                 return error;
 535                         }
 536                         xfs_trans_log_inode(cur->bc_tp, cur->bc_private.b.ip,
 537                                 logflags);
 538                         block = xfs_bmbt_get_block(cur, level, &bp);
 539                 } else {
 540                         if ((error = xfs_btree_rshift(cur, level, &i))) {
 541                                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
 542                                 return error;
 543                         }
 544                         if (i) {
 545                                 /* nothing */
 546                         } else {
 547                                 if ((error = xfs_bmbt_lshift(cur, level, &i))) {
 548                                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
 549                                         return error;
 550                                 }
 551                                 if (i) {
 552                                         optr = ptr = cur->bc_ptrs[level];
 553                                 } else {
 554                                         if ((error = xfs_bmbt_split(cur, level,
 555                                                         &nbno, &startoff, &ncur,
 556                                                         &i))) {
 557                                                 XFS_BMBT_TRACE_CURSOR(cur,
 558                                                         ERROR);
 559                                                 return error;
 560                                         }
 561                                         if (i) {
 562                                                 block = xfs_bmbt_get_block(
 563                                                             cur, level, &bp);
 564 #ifdef DEBUG
 565                                                 if ((error =
 566                                                     xfs_btree_check_lblock(cur,
 567                                                             block, level, bp))) {
 568                                                         XFS_BMBT_TRACE_CURSOR(
 569                                                                 cur, ERROR);
 570                                                         return error;
 571                                                 }
 572 #endif
 573                                                 ptr = cur->bc_ptrs[level];
 574                                                 xfs_bmbt_disk_set_allf(&nrec,
 575                                                         startoff, 0, 0,
 576                                                         XFS_EXT_NORM);
 577                                         } else {
 578                                                 XFS_BMBT_TRACE_CURSOR(cur,
 579                                                         EXIT);
 580                                                 *stat = 0;
 581                                                 return 0;
 582                                         }
 583                                 }
 584                         }
 585                 }
 586         }
 587         numrecs = be16_to_cpu(block->bb_numrecs);
 588         if (level > 0) {
 589                 kp = XFS_BMAP_KEY_IADDR(block, 1, cur);
 590                 pp = XFS_BMAP_PTR_IADDR(block, 1, cur);
 591 #ifdef DEBUG
 592                 for (i = numrecs; i >= ptr; i--) {
 593                         if ((error = xfs_btree_check_lptr_disk(cur, pp[i - 1],
 594                                         level))) {
 595                                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
 596                                 return error;
 597                         }
 598                 }
 599 #endif
 600                 memmove(&kp[ptr], &kp[ptr - 1],
 601                         (numrecs - ptr + 1) * sizeof(*kp));
 602                 memmove(&pp[ptr], &pp[ptr - 1],
 603                         (numrecs - ptr + 1) * sizeof(*pp));
 604 #ifdef DEBUG
 605                 if ((error = xfs_btree_check_lptr(cur, *bnop, level))) {
 606                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
 607                         return error;
 608                 }
 609 #endif
 610                 kp[ptr - 1] = key;
 611                 pp[ptr - 1] = cpu_to_be64(*bnop);
 612                 numrecs++;
 613                 block->bb_numrecs = cpu_to_be16(numrecs);
 614                 xfs_bmbt_log_keys(cur, bp, ptr, numrecs);
 615                 xfs_bmbt_log_ptrs(cur, bp, ptr, numrecs);
 616         } else {
 617                 rp = XFS_BMAP_REC_IADDR(block, 1, cur);
 618                 memmove(&rp[ptr], &rp[ptr - 1],
 619                         (numrecs - ptr + 1) * sizeof(*rp));
 620                 rp[ptr - 1] = *recp;
 621                 numrecs++;
 622                 block->bb_numrecs = cpu_to_be16(numrecs);
 623                 xfs_bmbt_log_recs(cur, bp, ptr, numrecs);
 624         }
 625         xfs_bmbt_log_block(cur, bp, XFS_BB_NUMRECS);
 626 #ifdef DEBUG
 627         if (ptr < numrecs) {
 628                 if (level == 0)
 629                         xfs_btree_check_rec(XFS_BTNUM_BMAP, rp + ptr - 1,
 630                                 rp + ptr);
 631                 else
 632                         xfs_btree_check_key(XFS_BTNUM_BMAP, kp + ptr - 1,
 633                                 kp + ptr);
 634         }
 635 #endif
 636         if (optr == 1 && (error = xfs_btree_updkey(cur, (union xfs_btree_key *)&key, level + 1))) {
 637                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
 638                 return error;
 639         }
 640         *bnop = nbno;
 641         if (nbno != NULLFSBLOCK) {
 642                 *recp = nrec;
 643                 *curp = ncur;
 644         }
 645         XFS_BMBT_TRACE_CURSOR(cur, EXIT);
 646         *stat = 1;
 647         return 0;
 648 }
 649
 650 STATIC int
 651 xfs_bmbt_killroot(
 652         xfs_btree_cur_t         *cur)
 653 {
 654         xfs_bmbt_block_t        *block;
 655         xfs_bmbt_block_t        *cblock;
 656         xfs_buf_t               *cbp;
 657         xfs_bmbt_key_t          *ckp;
 658         xfs_bmbt_ptr_t          *cpp;
 659 #ifdef DEBUG
 660         int                     error;
 661 #endif
 662         int                     i;
 663         xfs_bmbt_key_t          *kp;
 664         xfs_inode_t             *ip;
 665         xfs_ifork_t             *ifp;
 666         int                     level;
 667         xfs_bmbt_ptr_t          *pp;
 668
 669         XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
 670         level = cur->bc_nlevels - 1;
 671         ASSERT(level >= 1);
 672         /*
 673          * Don't deal with the root block needs to be a leaf case.
 674          * We're just going to turn the thing back into extents anyway.
 675          */
 676         if (level == 1) {
 677                 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
 678                 return 0;
 679         }
 680         block = xfs_bmbt_get_block(cur, level, &cbp);
 681         /*
 682          * Give up if the root has multiple children.
 683          */
 684         if (be16_to_cpu(block->bb_numrecs) != 1) {
 685                 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
 686                 return 0;
 687         }
 688         /*
 689          * Only do this if the next level will fit.
 690          * Then the data must be copied up to the inode,
 691          * instead of freeing the root you free the next level.
 692          */
 693         cbp = cur->bc_bufs[level - 1];
 694         cblock = XFS_BUF_TO_BMBT_BLOCK(cbp);
 695         if (be16_to_cpu(cblock->bb_numrecs) > XFS_BMAP_BLOCK_DMAXRECS(level, cur)) {
 696                 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
 697                 return 0;
 698         }
 699         ASSERT(be64_to_cpu(cblock->bb_leftsib) == NULLDFSBNO);
 700         ASSERT(be64_to_cpu(cblock->bb_rightsib) == NULLDFSBNO);
 701         ip = cur->bc_private.b.ip;
 702         ifp = XFS_IFORK_PTR(ip, cur->bc_private.b.whichfork);
 703         ASSERT(XFS_BMAP_BLOCK_IMAXRECS(level, cur) ==
 704                XFS_BMAP_BROOT_MAXRECS(ifp->if_broot_bytes));
 705         i = (int)(be16_to_cpu(cblock->bb_numrecs) - XFS_BMAP_BLOCK_IMAXRECS(level, cur));
 706         if (i) {
 707                 xfs_iroot_realloc(ip, i, cur->bc_private.b.whichfork);
 708                 block = ifp->if_broot;
 709         }
 710         be16_add_cpu(&block->bb_numrecs, i);
 711         ASSERT(block->bb_numrecs == cblock->bb_numrecs);
 712         kp = XFS_BMAP_KEY_IADDR(block, 1, cur);
 713         ckp = XFS_BMAP_KEY_IADDR(cblock, 1, cur);
 714         memcpy(kp, ckp, be16_to_cpu(block->bb_numrecs) * sizeof(*kp));
 715         pp = XFS_BMAP_PTR_IADDR(block, 1, cur);
 716         cpp = XFS_BMAP_PTR_IADDR(cblock, 1, cur);
 717 #ifdef DEBUG
 718         for (i = 0; i < be16_to_cpu(cblock->bb_numrecs); i++) {
 719                 if ((error = xfs_btree_check_lptr_disk(cur, cpp[i], level - 1))) {
 720                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
 721                         return error;
 722                 }
 723         }
 724 #endif
 725         memcpy(pp, cpp, be16_to_cpu(block->bb_numrecs) * sizeof(*pp));
 726         xfs_bmap_add_free(XFS_DADDR_TO_FSB(cur->bc_mp, XFS_BUF_ADDR(cbp)), 1,
 727                         cur->bc_private.b.flist, cur->bc_mp);
 728         ip->i_d.di_nblocks--;
 729         XFS_TRANS_MOD_DQUOT_BYINO(cur->bc_mp, cur->bc_tp, ip,
 730                         XFS_TRANS_DQ_BCOUNT, -1L);
 731         xfs_trans_binval(cur->bc_tp, cbp);
 732         cur->bc_bufs[level - 1] = NULL;
 733         be16_add_cpu(&block->bb_level, -1);
 734         xfs_trans_log_inode(cur->bc_tp, ip,
 735                 XFS_ILOG_CORE | XFS_ILOG_FBROOT(cur->bc_private.b.whichfork));
 736         cur->bc_nlevels--;
 737         XFS_BMBT_TRACE_CURSOR(cur, EXIT);
 738         return 0;
 739 }
 740
 741 /*
 742  * Log key values from the btree block.
 743  */
 744 STATIC void
 745 xfs_bmbt_log_keys(
 746         xfs_btree_cur_t *cur,
 747         xfs_buf_t       *bp,
 748         int             kfirst,
 749         int             klast)
 750 {
 751         xfs_trans_t     *tp;
 752
 753         XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
 754         XFS_BMBT_TRACE_ARGBII(cur, bp, kfirst, klast);
 755         tp = cur->bc_tp;
 756         if (bp) {
 757                 xfs_bmbt_block_t        *block;
 758                 int                     first;
 759                 xfs_bmbt_key_t          *kp;
 760                 int                     last;
 761
 762                 block = XFS_BUF_TO_BMBT_BLOCK(bp);
 763                 kp = XFS_BMAP_KEY_DADDR(block, 1, cur);
 764                 first = (int)((xfs_caddr_t)&kp[kfirst - 1] - (xfs_caddr_t)block);
 765                 last = (int)(((xfs_caddr_t)&kp[klast] - 1) - (xfs_caddr_t)block);
 766                 xfs_trans_log_buf(tp, bp, first, last);
 767         } else {
 768                 xfs_inode_t              *ip;
 769
 770                 ip = cur->bc_private.b.ip;
 771                 xfs_trans_log_inode(tp, ip,
 772                         XFS_ILOG_FBROOT(cur->bc_private.b.whichfork));
 773         }
 774         XFS_BMBT_TRACE_CURSOR(cur, EXIT);
 775 }
 776
 777 /*
 778  * Log pointer values from the btree block.
 779  */
 780 STATIC void
 781 xfs_bmbt_log_ptrs(
 782         xfs_btree_cur_t *cur,
 783         xfs_buf_t       *bp,
 784         int             pfirst,
 785         int             plast)
 786 {
 787         xfs_trans_t     *tp;
 788
 789         XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
 790         XFS_BMBT_TRACE_ARGBII(cur, bp, pfirst, plast);
 791         tp = cur->bc_tp;
 792         if (bp) {
 793                 xfs_bmbt_block_t        *block;
 794                 int                     first;
 795                 int                     last;
 796                 xfs_bmbt_ptr_t          *pp;
 797
 798                 block = XFS_BUF_TO_BMBT_BLOCK(bp);
 799                 pp = XFS_BMAP_PTR_DADDR(block, 1, cur);
 800                 first = (int)((xfs_caddr_t)&pp[pfirst - 1] - (xfs_caddr_t)block);
 801                 last = (int)(((xfs_caddr_t)&pp[plast] - 1) - (xfs_caddr_t)block);
 802                 xfs_trans_log_buf(tp, bp, first, last);
 803         } else {
 804                 xfs_inode_t             *ip;
 805
 806                 ip = cur->bc_private.b.ip;
 807                 xfs_trans_log_inode(tp, ip,
 808                         XFS_ILOG_FBROOT(cur->bc_private.b.whichfork));
 809         }
 810         XFS_BMBT_TRACE_CURSOR(cur, EXIT);
 811 }
 812
 813 /*
 814  * Move 1 record left from cur/level if possible.
 815  * Update cur to reflect the new path.
 816  */
 817 STATIC int                                      /* error */
 818 xfs_bmbt_lshift(
 819         xfs_btree_cur_t         *cur,
 820         int                     level,
 821         int                     *stat)          /* success/failure */
 822 {
 823         int                     error;          /* error return value */
 824 #ifdef DEBUG
 825         int                     i;              /* loop counter */
 826 #endif
 827         xfs_bmbt_key_t          key;            /* bmap btree key */
 828         xfs_buf_t               *lbp;           /* left buffer pointer */
 829         xfs_bmbt_block_t        *left;          /* left btree block */
 830         xfs_bmbt_key_t          *lkp=NULL;      /* left btree key */
 831         xfs_bmbt_ptr_t          *lpp;           /* left address pointer */
 832         int                     lrecs;          /* left record count */
 833         xfs_bmbt_rec_t          *lrp=NULL;      /* left record pointer */
 834         xfs_mount_t             *mp;            /* file system mount point */
 835         xfs_buf_t               *rbp;           /* right buffer pointer */
 836         xfs_bmbt_block_t        *right;         /* right btree block */
 837         xfs_bmbt_key_t          *rkp=NULL;      /* right btree key */
 838         xfs_bmbt_ptr_t          *rpp=NULL;      /* right address pointer */
 839         xfs_bmbt_rec_t          *rrp=NULL;      /* right record pointer */
 840         int                     rrecs;          /* right record count */
 841
 842         XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
 843         XFS_BMBT_TRACE_ARGI(cur, level);
 844         if (level == cur->bc_nlevels - 1) {
 845                 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
 846                 *stat = 0;
 847                 return 0;
 848         }
 849         rbp = cur->bc_bufs[level];
 850         right = XFS_BUF_TO_BMBT_BLOCK(rbp);
 851 #ifdef DEBUG
 852         if ((error = xfs_btree_check_lblock(cur, right, level, rbp))) {
 853                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
 854                 return error;
 855         }
 856 #endif
 857         if (be64_to_cpu(right->bb_leftsib) == NULLDFSBNO) {
 858                 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
 859                 *stat = 0;
 860                 return 0;
 861         }
 862         if (cur->bc_ptrs[level] <= 1) {
 863                 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
 864                 *stat = 0;
 865                 return 0;
 866         }
 867         mp = cur->bc_mp;
 868         if ((error = xfs_btree_read_bufl(mp, cur->bc_tp, be64_to_cpu(right->bb_leftsib), 0,
 869                         &lbp, XFS_BMAP_BTREE_REF))) {
 870                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
 871                 return error;
 872         }
 873         left = XFS_BUF_TO_BMBT_BLOCK(lbp);
 874         if ((error = xfs_btree_check_lblock(cur, left, level, lbp))) {
 875                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
 876                 return error;
 877         }
 878         if (be16_to_cpu(left->bb_numrecs) == XFS_BMAP_BLOCK_IMAXRECS(level, cur)) {
 879                 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
 880                 *stat = 0;
 881                 return 0;
 882         }
 883         lrecs = be16_to_cpu(left->bb_numrecs) + 1;
 884         if (level > 0) {
 885                 lkp = XFS_BMAP_KEY_IADDR(left, lrecs, cur);
 886                 rkp = XFS_BMAP_KEY_IADDR(right, 1, cur);
 887                 *lkp = *rkp;
 888                 xfs_bmbt_log_keys(cur, lbp, lrecs, lrecs);
 889                 lpp = XFS_BMAP_PTR_IADDR(left, lrecs, cur);
 890                 rpp = XFS_BMAP_PTR_IADDR(right, 1, cur);
 891 #ifdef DEBUG
 892                 if ((error = xfs_btree_check_lptr_disk(cur, *rpp, level))) {
 893                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
 894                         return error;
 895                 }
 896 #endif
 897                 *lpp = *rpp;
 898                 xfs_bmbt_log_ptrs(cur, lbp, lrecs, lrecs);
 899         } else {
 900                 lrp = XFS_BMAP_REC_IADDR(left, lrecs, cur);
 901                 rrp = XFS_BMAP_REC_IADDR(right, 1, cur);
 902                 *lrp = *rrp;
 903                 xfs_bmbt_log_recs(cur, lbp, lrecs, lrecs);
 904         }
 905         left->bb_numrecs = cpu_to_be16(lrecs);
 906         xfs_bmbt_log_block(cur, lbp, XFS_BB_NUMRECS);
 907 #ifdef DEBUG
 908         if (level > 0)
 909                 xfs_btree_check_key(XFS_BTNUM_BMAP, lkp - 1, lkp);
 910         else
 911                 xfs_btree_check_rec(XFS_BTNUM_BMAP, lrp - 1, lrp);
 912 #endif
 913         rrecs = be16_to_cpu(right->bb_numrecs) - 1;
 914         right->bb_numrecs = cpu_to_be16(rrecs);
 915         xfs_bmbt_log_block(cur, rbp, XFS_BB_NUMRECS);
 916         if (level > 0) {
 917 #ifdef DEBUG
 918                 for (i = 0; i < rrecs; i++) {
 919                         if ((error = xfs_btree_check_lptr_disk(cur, rpp[i + 1],
 920                                         level))) {
 921                                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
 922                                 return error;
 923                         }
 924                 }
 925 #endif
 926                 memmove(rkp, rkp + 1, rrecs * sizeof(*rkp));
 927                 memmove(rpp, rpp + 1, rrecs * sizeof(*rpp));
 928                 xfs_bmbt_log_keys(cur, rbp, 1, rrecs);
 929                 xfs_bmbt_log_ptrs(cur, rbp, 1, rrecs);
 930         } else {
 931                 memmove(rrp, rrp + 1, rrecs * sizeof(*rrp));
 932                 xfs_bmbt_log_recs(cur, rbp, 1, rrecs);
 933                 key.br_startoff = cpu_to_be64(xfs_bmbt_disk_get_startoff(rrp));
 934                 rkp = &key;
 935         }
 936         if ((error = xfs_btree_updkey(cur, (union xfs_btree_key *)rkp, level + 1))) {
 937                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
 938                 return error;
 939         }
 940         cur->bc_ptrs[level]--;
 941         XFS_BMBT_TRACE_CURSOR(cur, EXIT);
 942         *stat = 1;
 943         return 0;
 944 }
 945
 946 /*
 947  * Determine the extent state.
 948  */
 949 /* ARGSUSED */
 950 STATIC xfs_exntst_t
 951 xfs_extent_state(
 952         xfs_filblks_t           blks,
 953         int                     extent_flag)
 954 {
 955         if (extent_flag) {
 956                 ASSERT(blks != 0);      /* saved for DMIG */
 957                 return XFS_EXT_UNWRITTEN;
 958         }
 959         return XFS_EXT_NORM;
 960 }
 961
 962
 963 /*
 964  * Split cur/level block in half.
 965  * Return new block number and its first record (to be inserted into parent).
 966  */
 967 STATIC int                                      /* error */
 968 xfs_bmbt_split(
 969         xfs_btree_cur_t         *cur,
 970         int                     level,
 971         xfs_fsblock_t           *bnop,
 972         __uint64_t              *startoff,
 973         xfs_btree_cur_t         **curp,
 974         int                     *stat)          /* success/failure */
 975 {
 976         xfs_alloc_arg_t         args;           /* block allocation args */
 977         int                     error;          /* error return value */
 978         int                     i;              /* loop counter */
 979         xfs_fsblock_t           lbno;           /* left sibling block number */
 980         xfs_buf_t               *lbp;           /* left buffer pointer */
 981         xfs_bmbt_block_t        *left;          /* left btree block */
 982         xfs_bmbt_key_t          *lkp;           /* left btree key */
 983         xfs_bmbt_ptr_t          *lpp;           /* left address pointer */
 984         xfs_bmbt_rec_t          *lrp;           /* left record pointer */
 985         xfs_buf_t               *rbp;           /* right buffer pointer */
 986         xfs_bmbt_block_t        *right;         /* right btree block */
 987         xfs_bmbt_key_t          *rkp;           /* right btree key */
 988         xfs_bmbt_ptr_t          *rpp;           /* right address pointer */
 989         xfs_bmbt_block_t        *rrblock;       /* right-right btree block */
 990         xfs_buf_t               *rrbp;          /* right-right buffer pointer */
 991         xfs_bmbt_rec_t          *rrp;           /* right record pointer */
 992
 993         XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
 994         // disable until merged into common code
 995 //      XFS_BMBT_TRACE_ARGIFK(cur, level, *bnop, *startoff);
 996         args.tp = cur->bc_tp;
 997         args.mp = cur->bc_mp;
 998         lbp = cur->bc_bufs[level];
 999         lbno = XFS_DADDR_TO_FSB(args.mp, XFS_BUF_ADDR(lbp));
1000         left = XFS_BUF_TO_BMBT_BLOCK(lbp);
1001         args.fsbno = cur->bc_private.b.firstblock;
1002         args.firstblock = args.fsbno;
1003         args.minleft = 0;
1004         if (args.fsbno == NULLFSBLOCK) {
1005                 args.fsbno = lbno;
1006                 args.type = XFS_ALLOCTYPE_START_BNO;
1007                 /*
1008                  * Make sure there is sufficient room left in the AG to
1009                  * complete a full tree split for an extent insert.  If
1010                  * we are converting the middle part of an extent then
1011                  * we may need space for two tree splits.
1012                  *
1013                  * We are relying on the caller to make the correct block
1014                  * reservation for this operation to succeed.  If the
1015                  * reservation amount is insufficient then we may fail a
1016                  * block allocation here and corrupt the filesystem.
1017                  */
1018                 args.minleft = xfs_trans_get_block_res(args.tp);
1019         } else if (cur->bc_private.b.flist->xbf_low)
1020                 args.type = XFS_ALLOCTYPE_START_BNO;
1021         else
1022                 args.type = XFS_ALLOCTYPE_NEAR_BNO;
1023         args.mod = args.alignment = args.total = args.isfl =
1024                 args.userdata = args.minalignslop = 0;
1025         args.minlen = args.maxlen = args.prod = 1;
1026         args.wasdel = cur->bc_private.b.flags & XFS_BTCUR_BPRV_WASDEL;
1027         if (!args.wasdel && xfs_trans_get_block_res(args.tp) == 0) {
1028                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1029                 return XFS_ERROR(ENOSPC);
1030         }
1031         if ((error = xfs_alloc_vextent(&args))) {
1032                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1033                 return error;
1034         }
1035         if (args.fsbno == NULLFSBLOCK && args.minleft) {
1036                 /*
1037                  * Could not find an AG with enough free space to satisfy
1038                  * a full btree split.  Try again without minleft and if
1039                  * successful activate the lowspace algorithm.
1040                  */
1041                 args.fsbno = 0;
1042                 args.type = XFS_ALLOCTYPE_FIRST_AG;
1043                 args.minleft = 0;
1044                 if ((error = xfs_alloc_vextent(&args))) {
1045                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1046                         return error;
1047                 }
1048                 cur->bc_private.b.flist->xbf_low = 1;
1049         }
1050         if (args.fsbno == NULLFSBLOCK) {
1051                 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1052                 *stat = 0;
1053                 return 0;
1054         }
1055         ASSERT(args.len == 1);
1056         cur->bc_private.b.firstblock = args.fsbno;
1057         cur->bc_private.b.allocated++;
1058         cur->bc_private.b.ip->i_d.di_nblocks++;
1059         xfs_trans_log_inode(args.tp, cur->bc_private.b.ip, XFS_ILOG_CORE);
1060         XFS_TRANS_MOD_DQUOT_BYINO(args.mp, args.tp, cur->bc_private.b.ip,
1061                         XFS_TRANS_DQ_BCOUNT, 1L);
1062         rbp = xfs_btree_get_bufl(args.mp, args.tp, args.fsbno, 0);
1063         right = XFS_BUF_TO_BMBT_BLOCK(rbp);
1064 #ifdef DEBUG
1065         if ((error = xfs_btree_check_lblock(cur, left, level, rbp))) {
1066                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1067                 return error;
1068         }
1069 #endif
1070         right->bb_magic = cpu_to_be32(XFS_BMAP_MAGIC);
1071         right->bb_level = left->bb_level;
1072         right->bb_numrecs = cpu_to_be16(be16_to_cpu(left->bb_numrecs) / 2);
1073         if ((be16_to_cpu(left->bb_numrecs) & 1) &&
1074             cur->bc_ptrs[level] <= be16_to_cpu(right->bb_numrecs) + 1)
1075                 be16_add_cpu(&right->bb_numrecs, 1);
1076         i = be16_to_cpu(left->bb_numrecs) - be16_to_cpu(right->bb_numrecs) + 1;
1077         if (level > 0) {
1078                 lkp = XFS_BMAP_KEY_IADDR(left, i, cur);
1079                 lpp = XFS_BMAP_PTR_IADDR(left, i, cur);
1080                 rkp = XFS_BMAP_KEY_IADDR(right, 1, cur);
1081                 rpp = XFS_BMAP_PTR_IADDR(right, 1, cur);
1082 #ifdef DEBUG
1083                 for (i = 0; i < be16_to_cpu(right->bb_numrecs); i++) {
1084                         if ((error = xfs_btree_check_lptr_disk(cur, lpp[i], level))) {
1085                                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1086                                 return error;
1087                         }
1088                 }
1089 #endif
1090                 memcpy(rkp, lkp, be16_to_cpu(right->bb_numrecs) * sizeof(*rkp));
1091                 memcpy(rpp, lpp, be16_to_cpu(right->bb_numrecs) * sizeof(*rpp));
1092                 xfs_bmbt_log_keys(cur, rbp, 1, be16_to_cpu(right->bb_numrecs));
1093                 xfs_bmbt_log_ptrs(cur, rbp, 1, be16_to_cpu(right->bb_numrecs));
1094                 *startoff = be64_to_cpu(rkp->br_startoff);
1095         } else {
1096                 lrp = XFS_BMAP_REC_IADDR(left, i, cur);
1097                 rrp = XFS_BMAP_REC_IADDR(right, 1, cur);
1098                 memcpy(rrp, lrp, be16_to_cpu(right->bb_numrecs) * sizeof(*rrp));
1099                 xfs_bmbt_log_recs(cur, rbp, 1, be16_to_cpu(right->bb_numrecs));
1100                 *startoff = xfs_bmbt_disk_get_startoff(rrp);
1101         }
1102         be16_add_cpu(&left->bb_numrecs, -(be16_to_cpu(right->bb_numrecs)));
1103         right->bb_rightsib = left->bb_rightsib;
1104         left->bb_rightsib = cpu_to_be64(args.fsbno);
1105         right->bb_leftsib = cpu_to_be64(lbno);
1106         xfs_bmbt_log_block(cur, rbp, XFS_BB_ALL_BITS);
1107         xfs_bmbt_log_block(cur, lbp, XFS_BB_NUMRECS | XFS_BB_RIGHTSIB);
1108         if (be64_to_cpu(right->bb_rightsib) != NULLDFSBNO) {
1109                 if ((error = xfs_btree_read_bufl(args.mp, args.tp,
1110                                 be64_to_cpu(right->bb_rightsib), 0, &rrbp,
1111                                 XFS_BMAP_BTREE_REF))) {
1112                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1113                         return error;
1114                 }
1115                 rrblock = XFS_BUF_TO_BMBT_BLOCK(rrbp);
1116                 if ((error = xfs_btree_check_lblock(cur, rrblock, level, rrbp))) {
1117                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1118                         return error;
1119                 }
1120                 rrblock->bb_leftsib = cpu_to_be64(args.fsbno);
1121                 xfs_bmbt_log_block(cur, rrbp, XFS_BB_LEFTSIB);
1122         }
1123         if (cur->bc_ptrs[level] > be16_to_cpu(left->bb_numrecs) + 1) {
1124                 xfs_btree_setbuf(cur, level, rbp);
1125                 cur->bc_ptrs[level] -= be16_to_cpu(left->bb_numrecs);
1126         }
1127         if (level + 1 < cur->bc_nlevels) {
1128                 if ((error = xfs_btree_dup_cursor(cur, curp))) {
1129                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1130                         return error;
1131                 }
1132                 (*curp)->bc_ptrs[level + 1]++;
1133         }
1134         *bnop = args.fsbno;
1135         XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1136         *stat = 1;
1137         return 0;
1138 }
1139
1140 /*
1141  * Convert on-disk form of btree root to in-memory form.
1142  */
1143 void
1144 xfs_bmdr_to_bmbt(
1145         xfs_bmdr_block_t        *dblock,
1146         int                     dblocklen,
1147         xfs_bmbt_block_t        *rblock,
1148         int                     rblocklen)
1149 {
1150         int                     dmxr;
1151         xfs_bmbt_key_t          *fkp;
1152         __be64                  *fpp;
1153         xfs_bmbt_key_t          *tkp;
1154         __be64                  *tpp;
1155
1156         rblock->bb_magic = cpu_to_be32(XFS_BMAP_MAGIC);
1157         rblock->bb_level = dblock->bb_level;
1158         ASSERT(be16_to_cpu(rblock->bb_level) > 0);
1159         rblock->bb_numrecs = dblock->bb_numrecs;
1160         rblock->bb_leftsib = cpu_to_be64(NULLDFSBNO);
1161         rblock->bb_rightsib = cpu_to_be64(NULLDFSBNO);
1162         dmxr = (int)XFS_BTREE_BLOCK_MAXRECS(dblocklen, xfs_bmdr, 0);
1163         fkp = XFS_BTREE_KEY_ADDR(xfs_bmdr, dblock, 1);
1164         tkp = XFS_BMAP_BROOT_KEY_ADDR(rblock, 1, rblocklen);
1165         fpp = XFS_BTREE_PTR_ADDR(xfs_bmdr, dblock, 1, dmxr);
1166         tpp = XFS_BMAP_BROOT_PTR_ADDR(rblock, 1, rblocklen);
1167         dmxr = be16_to_cpu(dblock->bb_numrecs);
1168         memcpy(tkp, fkp, sizeof(*fkp) * dmxr);
1169         memcpy(tpp, fpp, sizeof(*fpp) * dmxr);
1170 }
1171
1172 /*
1173  * Delete the record pointed to by cur.
1174  */
1175 int                                     /* error */
1176 xfs_bmbt_delete(
1177         xfs_btree_cur_t *cur,
1178         int             *stat)          /* success/failure */
1179 {
1180         int             error;          /* error return value */
1181         int             i;
1182         int             level;
1183
1184         XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
1185         for (level = 0, i = 2; i == 2; level++) {
1186                 if ((error = xfs_bmbt_delrec(cur, level, &i))) {
1187                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1188                         return error;
1189                 }
1190         }
1191         if (i == 0) {
1192                 for (level = 1; level < cur->bc_nlevels; level++) {
1193                         if (cur->bc_ptrs[level] == 0) {
1194                                 if ((error = xfs_btree_decrement(cur, level,
1195                                                 &i))) {
1196                                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1197                                         return error;
1198                                 }
1199                                 break;
1200                         }
1201                 }
1202         }
1203         XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1204         *stat = i;
1205         return 0;
1206 }
1207
1208 /*
1209  * Convert a compressed bmap extent record to an uncompressed form.
1210  * This code must be in sync with the routines xfs_bmbt_get_startoff,
1211  * xfs_bmbt_get_startblock, xfs_bmbt_get_blockcount and xfs_bmbt_get_state.
1212  */
1213
1214 STATIC_INLINE void
1215 __xfs_bmbt_get_all(
1216                 __uint64_t l0,
1217                 __uint64_t l1,
1218                 xfs_bmbt_irec_t *s)
1219 {
1220         int     ext_flag;
1221         xfs_exntst_t st;
1222
1223         ext_flag = (int)(l0 >> (64 - BMBT_EXNTFLAG_BITLEN));
1224         s->br_startoff = ((xfs_fileoff_t)l0 &
1225                            XFS_MASK64LO(64 - BMBT_EXNTFLAG_BITLEN)) >> 9;
1226 #if XFS_BIG_BLKNOS
1227         s->br_startblock = (((xfs_fsblock_t)l0 & XFS_MASK64LO(9)) << 43) |
1228                            (((xfs_fsblock_t)l1) >> 21);
1229 #else
1230 #ifdef DEBUG
1231         {
1232                 xfs_dfsbno_t    b;
1233
1234                 b = (((xfs_dfsbno_t)l0 & XFS_MASK64LO(9)) << 43) |
1235                     (((xfs_dfsbno_t)l1) >> 21);
1236                 ASSERT((b >> 32) == 0 || ISNULLDSTARTBLOCK(b));
1237                 s->br_startblock = (xfs_fsblock_t)b;
1238         }
1239 #else   /* !DEBUG */
1240         s->br_startblock = (xfs_fsblock_t)(((xfs_dfsbno_t)l1) >> 21);
1241 #endif  /* DEBUG */
1242 #endif  /* XFS_BIG_BLKNOS */
1243         s->br_blockcount = (xfs_filblks_t)(l1 & XFS_MASK64LO(21));
1244         /* This is xfs_extent_state() in-line */
1245         if (ext_flag) {
1246                 ASSERT(s->br_blockcount != 0);  /* saved for DMIG */
1247                 st = XFS_EXT_UNWRITTEN;
1248         } else
1249                 st = XFS_EXT_NORM;
1250         s->br_state = st;
1251 }
1252
1253 void
1254 xfs_bmbt_get_all(
1255         xfs_bmbt_rec_host_t *r,
1256         xfs_bmbt_irec_t *s)
1257 {
1258         __xfs_bmbt_get_all(r->l0, r->l1, s);
1259 }
1260
1261 /*
1262  * Get the block pointer for the given level of the cursor.
1263  * Fill in the buffer pointer, if applicable.
1264  */
1265 xfs_bmbt_block_t *
1266 xfs_bmbt_get_block(
1267         xfs_btree_cur_t         *cur,
1268         int                     level,
1269         xfs_buf_t               **bpp)
1270 {
1271         xfs_ifork_t             *ifp;
1272         xfs_bmbt_block_t        *rval;
1273
1274         if (level < cur->bc_nlevels - 1) {
1275                 *bpp = cur->bc_bufs[level];
1276                 rval = XFS_BUF_TO_BMBT_BLOCK(*bpp);
1277         } else {
1278                 *bpp = NULL;
1279                 ifp = XFS_IFORK_PTR(cur->bc_private.b.ip,
1280                         cur->bc_private.b.whichfork);
1281                 rval = ifp->if_broot;
1282         }
1283         return rval;
1284 }
1285
1286 /*
1287  * Extract the blockcount field from an in memory bmap extent record.
1288  */
1289 xfs_filblks_t
1290 xfs_bmbt_get_blockcount(
1291         xfs_bmbt_rec_host_t     *r)
1292 {
1293         return (xfs_filblks_t)(r->l1 & XFS_MASK64LO(21));
1294 }
1295
1296 /*
1297  * Extract the startblock field from an in memory bmap extent record.
1298  */
1299 xfs_fsblock_t
1300 xfs_bmbt_get_startblock(
1301         xfs_bmbt_rec_host_t     *r)
1302 {
1303 #if XFS_BIG_BLKNOS
1304         return (((xfs_fsblock_t)r->l0 & XFS_MASK64LO(9)) << 43) |
1305                (((xfs_fsblock_t)r->l1) >> 21);
1306 #else
1307 #ifdef DEBUG
1308         xfs_dfsbno_t    b;
1309
1310         b = (((xfs_dfsbno_t)r->l0 & XFS_MASK64LO(9)) << 43) |
1311             (((xfs_dfsbno_t)r->l1) >> 21);
1312         ASSERT((b >> 32) == 0 || ISNULLDSTARTBLOCK(b));
1313         return (xfs_fsblock_t)b;
1314 #else   /* !DEBUG */
1315         return (xfs_fsblock_t)(((xfs_dfsbno_t)r->l1) >> 21);
1316 #endif  /* DEBUG */
1317 #endif  /* XFS_BIG_BLKNOS */
1318 }
1319
1320 /*
1321  * Extract the startoff field from an in memory bmap extent record.
1322  */
1323 xfs_fileoff_t
1324 xfs_bmbt_get_startoff(
1325         xfs_bmbt_rec_host_t     *r)
1326 {
1327         return ((xfs_fileoff_t)r->l0 &
1328                  XFS_MASK64LO(64 - BMBT_EXNTFLAG_BITLEN)) >> 9;
1329 }
1330
1331 xfs_exntst_t
1332 xfs_bmbt_get_state(
1333         xfs_bmbt_rec_host_t     *r)
1334 {
1335         int     ext_flag;
1336
1337         ext_flag = (int)((r->l0) >> (64 - BMBT_EXNTFLAG_BITLEN));
1338         return xfs_extent_state(xfs_bmbt_get_blockcount(r),
1339                                 ext_flag);
1340 }
1341
1342 /* Endian flipping versions of the bmbt extraction functions */
1343 void
1344 xfs_bmbt_disk_get_all(
1345         xfs_bmbt_rec_t  *r,
1346         xfs_bmbt_irec_t *s)
1347 {
1348         __xfs_bmbt_get_all(be64_to_cpu(r->l0), be64_to_cpu(r->l1), s);
1349 }
1350
1351 /*
1352  * Extract the blockcount field from an on disk bmap extent record.
1353  */
1354 xfs_filblks_t
1355 xfs_bmbt_disk_get_blockcount(
1356         xfs_bmbt_rec_t  *r)
1357 {
1358         return (xfs_filblks_t)(be64_to_cpu(r->l1) & XFS_MASK64LO(21));
1359 }
1360
1361 /*
1362  * Extract the startoff field from a disk format bmap extent record.
1363  */
1364 xfs_fileoff_t
1365 xfs_bmbt_disk_get_startoff(
1366         xfs_bmbt_rec_t  *r)
1367 {
1368         return ((xfs_fileoff_t)be64_to_cpu(r->l0) &
1369                  XFS_MASK64LO(64 - BMBT_EXNTFLAG_BITLEN)) >> 9;
1370 }
1371
1372 /*
1373  * Insert the current record at the point referenced by cur.
1374  *
1375  * A multi-level split of the tree on insert will invalidate the original
1376  * cursor.  All callers of this function should assume that the cursor is
1377  * no longer valid and revalidate it.
1378  */
1379 int                                     /* error */
1380 xfs_bmbt_insert(
1381         xfs_btree_cur_t *cur,
1382         int             *stat)          /* success/failure */
1383 {
1384         int             error;          /* error return value */
1385         int             i;
1386         int             level;
1387         xfs_fsblock_t   nbno;
1388         xfs_btree_cur_t *ncur;
1389         xfs_bmbt_rec_t  nrec;
1390         xfs_btree_cur_t *pcur;
1391
1392         XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
1393         level = 0;
1394         nbno = NULLFSBLOCK;
1395         xfs_bmbt_disk_set_all(&nrec, &cur->bc_rec.b);
1396         ncur = NULL;
1397         pcur = cur;
1398         do {
1399                 if ((error = xfs_bmbt_insrec(pcur, level++, &nbno, &nrec, &ncur,
1400                                 &i))) {
1401                         if (pcur != cur)
1402                                 xfs_btree_del_cursor(pcur, XFS_BTREE_ERROR);
1403                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1404                         return error;
1405                 }
1406                 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1407                 if (pcur != cur && (ncur || nbno == NULLFSBLOCK)) {
1408                         cur->bc_nlevels = pcur->bc_nlevels;
1409                         cur->bc_private.b.allocated +=
1410                                 pcur->bc_private.b.allocated;
1411                         pcur->bc_private.b.allocated = 0;
1412                         ASSERT((cur->bc_private.b.firstblock != NULLFSBLOCK) ||
1413                                XFS_IS_REALTIME_INODE(cur->bc_private.b.ip));
1414                         cur->bc_private.b.firstblock =
1415                                 pcur->bc_private.b.firstblock;
1416                         ASSERT(cur->bc_private.b.flist ==
1417                                pcur->bc_private.b.flist);
1418                         xfs_btree_del_cursor(pcur, XFS_BTREE_NOERROR);
1419                 }
1420                 if (ncur) {
1421                         pcur = ncur;
1422                         ncur = NULL;
1423                 }
1424         } while (nbno != NULLFSBLOCK);
1425         XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1426         *stat = i;
1427         return 0;
1428 error0:
1429         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1430         return error;
1431 }
1432
1433 /*
1434  * Log fields from the btree block header.
1435  */
1436 void
1437 xfs_bmbt_log_block(
1438         xfs_btree_cur_t         *cur,
1439         xfs_buf_t               *bp,
1440         int                     fields)
1441 {
1442         int                     first;
1443         int                     last;
1444         xfs_trans_t             *tp;
1445         static const short      offsets[] = {
1446                 offsetof(xfs_bmbt_block_t, bb_magic),
1447                 offsetof(xfs_bmbt_block_t, bb_level),
1448                 offsetof(xfs_bmbt_block_t, bb_numrecs),
1449                 offsetof(xfs_bmbt_block_t, bb_leftsib),
1450                 offsetof(xfs_bmbt_block_t, bb_rightsib),
1451                 sizeof(xfs_bmbt_block_t)
1452         };
1453
1454         XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
1455         XFS_BMBT_TRACE_ARGBI(cur, bp, fields);
1456         tp = cur->bc_tp;
1457         if (bp) {
1458                 xfs_btree_offsets(fields, offsets, XFS_BB_NUM_BITS, &first,
1459                                   &last);
1460                 xfs_trans_log_buf(tp, bp, first, last);
1461         } else
1462                 xfs_trans_log_inode(tp, cur->bc_private.b.ip,
1463                         XFS_ILOG_FBROOT(cur->bc_private.b.whichfork));
1464         XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1465 }
1466
1467 /*
1468  * Log record values from the btree block.
1469  */
1470 void
1471 xfs_bmbt_log_recs(
1472         xfs_btree_cur_t         *cur,
1473         xfs_buf_t               *bp,
1474         int                     rfirst,
1475         int                     rlast)
1476 {
1477         xfs_bmbt_block_t        *block;
1478         int                     first;
1479         int                     last;
1480         xfs_bmbt_rec_t          *rp;
1481         xfs_trans_t             *tp;
1482
1483         XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
1484         XFS_BMBT_TRACE_ARGBII(cur, bp, rfirst, rlast);
1485         ASSERT(bp);
1486         tp = cur->bc_tp;
1487         block = XFS_BUF_TO_BMBT_BLOCK(bp);
1488         rp = XFS_BMAP_REC_DADDR(block, 1, cur);
1489         first = (int)((xfs_caddr_t)&rp[rfirst - 1] - (xfs_caddr_t)block);
1490         last = (int)(((xfs_caddr_t)&rp[rlast] - 1) - (xfs_caddr_t)block);
1491         xfs_trans_log_buf(tp, bp, first, last);
1492         XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1493 }
1494
1495 /*
1496  * Give the bmap btree a new root block.  Copy the old broot contents
1497  * down into a real block and make the broot point to it.
1498  */
1499 int                                             /* error */
1500 xfs_bmbt_newroot(
1501         xfs_btree_cur_t         *cur,           /* btree cursor */
1502         int                     *logflags,      /* logging flags for inode */
1503         int                     *stat)          /* return status - 0 fail */
1504 {
1505         xfs_alloc_arg_t         args;           /* allocation arguments */
1506         xfs_bmbt_block_t        *block;         /* bmap btree block */
1507         xfs_buf_t               *bp;            /* buffer for block */
1508         xfs_bmbt_block_t        *cblock;        /* child btree block */
1509         xfs_bmbt_key_t          *ckp;           /* child key pointer */
1510         xfs_bmbt_ptr_t          *cpp;           /* child ptr pointer */
1511         int                     error;          /* error return code */
1512 #ifdef DEBUG
1513         int                     i;              /* loop counter */
1514 #endif
1515         xfs_bmbt_key_t          *kp;            /* pointer to bmap btree key */
1516         int                     level;          /* btree level */
1517         xfs_bmbt_ptr_t          *pp;            /* pointer to bmap block addr */
1518
1519         XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
1520         level = cur->bc_nlevels - 1;
1521         block = xfs_bmbt_get_block(cur, level, &bp);
1522         /*
1523          * Copy the root into a real block.
1524          */
1525         args.mp = cur->bc_mp;
1526         pp = XFS_BMAP_PTR_IADDR(block, 1, cur);
1527         args.tp = cur->bc_tp;
1528         args.fsbno = cur->bc_private.b.firstblock;
1529         args.mod = args.minleft = args.alignment = args.total = args.isfl =
1530                 args.userdata = args.minalignslop = 0;
1531         args.minlen = args.maxlen = args.prod = 1;
1532         args.wasdel = cur->bc_private.b.flags & XFS_BTCUR_BPRV_WASDEL;
1533         args.firstblock = args.fsbno;
1534         if (args.fsbno == NULLFSBLOCK) {
1535 #ifdef DEBUG
1536                 if ((error = xfs_btree_check_lptr_disk(cur, *pp, level))) {
1537                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1538                         return error;
1539                 }
1540 #endif
1541                 args.fsbno = be64_to_cpu(*pp);
1542                 args.type = XFS_ALLOCTYPE_START_BNO;
1543         } else if (cur->bc_private.b.flist->xbf_low)
1544                 args.type = XFS_ALLOCTYPE_START_BNO;
1545         else
1546                 args.type = XFS_ALLOCTYPE_NEAR_BNO;
1547         if ((error = xfs_alloc_vextent(&args))) {
1548                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1549                 return error;
1550         }
1551         if (args.fsbno == NULLFSBLOCK) {
1552                 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1553                 *stat = 0;
1554                 return 0;
1555         }
1556         ASSERT(args.len == 1);
1557         cur->bc_private.b.firstblock = args.fsbno;
1558         cur->bc_private.b.allocated++;
1559         cur->bc_private.b.ip->i_d.di_nblocks++;
1560         XFS_TRANS_MOD_DQUOT_BYINO(args.mp, args.tp, cur->bc_private.b.ip,
1561                           XFS_TRANS_DQ_BCOUNT, 1L);
1562         bp = xfs_btree_get_bufl(args.mp, cur->bc_tp, args.fsbno, 0);
1563         cblock = XFS_BUF_TO_BMBT_BLOCK(bp);
1564         *cblock = *block;
1565         be16_add_cpu(&block->bb_level, 1);
1566         block->bb_numrecs = cpu_to_be16(1);
1567         cur->bc_nlevels++;
1568         cur->bc_ptrs[level + 1] = 1;
1569         kp = XFS_BMAP_KEY_IADDR(block, 1, cur);
1570         ckp = XFS_BMAP_KEY_IADDR(cblock, 1, cur);
1571         memcpy(ckp, kp, be16_to_cpu(cblock->bb_numrecs) * sizeof(*kp));
1572         cpp = XFS_BMAP_PTR_IADDR(cblock, 1, cur);
1573 #ifdef DEBUG
1574         for (i = 0; i < be16_to_cpu(cblock->bb_numrecs); i++) {
1575                 if ((error = xfs_btree_check_lptr_disk(cur, pp[i], level))) {
1576                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1577                         return error;
1578                 }
1579         }
1580 #endif
1581         memcpy(cpp, pp, be16_to_cpu(cblock->bb_numrecs) * sizeof(*pp));
1582 #ifdef DEBUG
1583         if ((error = xfs_btree_check_lptr(cur, args.fsbno, level))) {
1584                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1585                 return error;
1586         }
1587 #endif
1588         *pp = cpu_to_be64(args.fsbno);
1589         xfs_iroot_realloc(cur->bc_private.b.ip, 1 - be16_to_cpu(cblock->bb_numrecs),
1590                 cur->bc_private.b.whichfork);
1591         xfs_btree_setbuf(cur, level, bp);
1592         /*
1593          * Do all this logging at the end so that
1594          * the root is at the right level.
1595          */
1596         xfs_bmbt_log_block(cur, bp, XFS_BB_ALL_BITS);
1597         xfs_bmbt_log_keys(cur, bp, 1, be16_to_cpu(cblock->bb_numrecs));
1598         xfs_bmbt_log_ptrs(cur, bp, 1, be16_to_cpu(cblock->bb_numrecs));
1599         XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1600         *logflags |=
1601                 XFS_ILOG_CORE | XFS_ILOG_FBROOT(cur->bc_private.b.whichfork);
1602         *stat = 1;
1603         return 0;
1604 }
1605
1606 /*
1607  * Set all the fields in a bmap extent record from the arguments.
1608  */
1609 void
1610 xfs_bmbt_set_allf(
1611         xfs_bmbt_rec_host_t     *r,
1612         xfs_fileoff_t           startoff,
1613         xfs_fsblock_t           startblock,
1614         xfs_filblks_t           blockcount,
1615         xfs_exntst_t            state)
1616 {
1617         int             extent_flag = (state == XFS_EXT_NORM) ? 0 : 1;
1618
1619         ASSERT(state == XFS_EXT_NORM || state == XFS_EXT_UNWRITTEN);
1620         ASSERT((startoff & XFS_MASK64HI(64-BMBT_STARTOFF_BITLEN)) == 0);
1621         ASSERT((blockcount & XFS_MASK64HI(64-BMBT_BLOCKCOUNT_BITLEN)) == 0);
1622
1623 #if XFS_BIG_BLKNOS
1624         ASSERT((startblock & XFS_MASK64HI(64-BMBT_STARTBLOCK_BITLEN)) == 0);
1625
1626         r->l0 = ((xfs_bmbt_rec_base_t)extent_flag << 63) |
1627                 ((xfs_bmbt_rec_base_t)startoff << 9) |
1628                 ((xfs_bmbt_rec_base_t)startblock >> 43);
1629         r->l1 = ((xfs_bmbt_rec_base_t)startblock << 21) |
1630                 ((xfs_bmbt_rec_base_t)blockcount &
1631                 (xfs_bmbt_rec_base_t)XFS_MASK64LO(21));
1632 #else   /* !XFS_BIG_BLKNOS */
1633         if (ISNULLSTARTBLOCK(startblock)) {
1634                 r->l0 = ((xfs_bmbt_rec_base_t)extent_flag << 63) |
1635                         ((xfs_bmbt_rec_base_t)startoff << 9) |
1636                          (xfs_bmbt_rec_base_t)XFS_MASK64LO(9);
1637                 r->l1 = XFS_MASK64HI(11) |
1638                           ((xfs_bmbt_rec_base_t)startblock << 21) |
1639                           ((xfs_bmbt_rec_base_t)blockcount &
1640                            (xfs_bmbt_rec_base_t)XFS_MASK64LO(21));
1641         } else {
1642                 r->l0 = ((xfs_bmbt_rec_base_t)extent_flag << 63) |
1643                         ((xfs_bmbt_rec_base_t)startoff << 9);
1644                 r->l1 = ((xfs_bmbt_rec_base_t)startblock << 21) |
1645                          ((xfs_bmbt_rec_base_t)blockcount &
1646                          (xfs_bmbt_rec_base_t)XFS_MASK64LO(21));
1647         }
1648 #endif  /* XFS_BIG_BLKNOS */
1649 }
1650
1651 /*
1652  * Set all the fields in a bmap extent record from the uncompressed form.
1653  */
1654 void
1655 xfs_bmbt_set_all(
1656         xfs_bmbt_rec_host_t *r,
1657         xfs_bmbt_irec_t *s)
1658 {
1659         xfs_bmbt_set_allf(r, s->br_startoff, s->br_startblock,
1660                              s->br_blockcount, s->br_state);
1661 }
1662
1663
1664 /*
1665  * Set all the fields in a disk format bmap extent record from the arguments.
1666  */
1667 void
1668 xfs_bmbt_disk_set_allf(
1669         xfs_bmbt_rec_t          *r,
1670         xfs_fileoff_t           startoff,
1671         xfs_fsblock_t           startblock,
1672         xfs_filblks_t           blockcount,
1673         xfs_exntst_t            state)
1674 {
1675         int                     extent_flag = (state == XFS_EXT_NORM) ? 0 : 1;
1676
1677         ASSERT(state == XFS_EXT_NORM || state == XFS_EXT_UNWRITTEN);
1678         ASSERT((startoff & XFS_MASK64HI(64-BMBT_STARTOFF_BITLEN)) == 0);
1679         ASSERT((blockcount & XFS_MASK64HI(64-BMBT_BLOCKCOUNT_BITLEN)) == 0);
1680
1681 #if XFS_BIG_BLKNOS
1682         ASSERT((startblock & XFS_MASK64HI(64-BMBT_STARTBLOCK_BITLEN)) == 0);
1683
1684         r->l0 = cpu_to_be64(
1685                 ((xfs_bmbt_rec_base_t)extent_flag << 63) |
1686                  ((xfs_bmbt_rec_base_t)startoff << 9) |
1687                  ((xfs_bmbt_rec_base_t)startblock >> 43));
1688         r->l1 = cpu_to_be64(
1689                 ((xfs_bmbt_rec_base_t)startblock << 21) |
1690                  ((xfs_bmbt_rec_base_t)blockcount &
1691                   (xfs_bmbt_rec_base_t)XFS_MASK64LO(21)));
1692 #else   /* !XFS_BIG_BLKNOS */
1693         if (ISNULLSTARTBLOCK(startblock)) {
1694                 r->l0 = cpu_to_be64(
1695                         ((xfs_bmbt_rec_base_t)extent_flag << 63) |
1696                          ((xfs_bmbt_rec_base_t)startoff << 9) |
1697                           (xfs_bmbt_rec_base_t)XFS_MASK64LO(9));
1698                 r->l1 = cpu_to_be64(XFS_MASK64HI(11) |
1699                           ((xfs_bmbt_rec_base_t)startblock << 21) |
1700                           ((xfs_bmbt_rec_base_t)blockcount &
1701                            (xfs_bmbt_rec_base_t)XFS_MASK64LO(21)));
1702         } else {
1703                 r->l0 = cpu_to_be64(
1704                         ((xfs_bmbt_rec_base_t)extent_flag << 63) |
1705                          ((xfs_bmbt_rec_base_t)startoff << 9));
1706                 r->l1 = cpu_to_be64(
1707                         ((xfs_bmbt_rec_base_t)startblock << 21) |
1708                          ((xfs_bmbt_rec_base_t)blockcount &
1709                           (xfs_bmbt_rec_base_t)XFS_MASK64LO(21)));
1710         }
1711 #endif  /* XFS_BIG_BLKNOS */
1712 }
1713
1714 /*
1715  * Set all the fields in a bmap extent record from the uncompressed form.
1716  */
1717 void
1718 xfs_bmbt_disk_set_all(
1719         xfs_bmbt_rec_t  *r,
1720         xfs_bmbt_irec_t *s)
1721 {
1722         xfs_bmbt_disk_set_allf(r, s->br_startoff, s->br_startblock,
1723                                   s->br_blockcount, s->br_state);
1724 }
1725
1726 /*
1727  * Set the blockcount field in a bmap extent record.
1728  */
1729 void
1730 xfs_bmbt_set_blockcount(
1731         xfs_bmbt_rec_host_t *r,
1732         xfs_filblks_t   v)
1733 {
1734         ASSERT((v & XFS_MASK64HI(43)) == 0);
1735         r->l1 = (r->l1 & (xfs_bmbt_rec_base_t)XFS_MASK64HI(43)) |
1736                   (xfs_bmbt_rec_base_t)(v & XFS_MASK64LO(21));
1737 }
1738
1739 /*
1740  * Set the startblock field in a bmap extent record.
1741  */
1742 void
1743 xfs_bmbt_set_startblock(
1744         xfs_bmbt_rec_host_t *r,
1745         xfs_fsblock_t   v)
1746 {
1747 #if XFS_BIG_BLKNOS
1748         ASSERT((v & XFS_MASK64HI(12)) == 0);
1749         r->l0 = (r->l0 & (xfs_bmbt_rec_base_t)XFS_MASK64HI(55)) |
1750                   (xfs_bmbt_rec_base_t)(v >> 43);
1751         r->l1 = (r->l1 & (xfs_bmbt_rec_base_t)XFS_MASK64LO(21)) |
1752                   (xfs_bmbt_rec_base_t)(v << 21);
1753 #else   /* !XFS_BIG_BLKNOS */
1754         if (ISNULLSTARTBLOCK(v)) {
1755                 r->l0 |= (xfs_bmbt_rec_base_t)XFS_MASK64LO(9);
1756                 r->l1 = (xfs_bmbt_rec_base_t)XFS_MASK64HI(11) |
1757                           ((xfs_bmbt_rec_base_t)v << 21) |
1758                           (r->l1 & (xfs_bmbt_rec_base_t)XFS_MASK64LO(21));
1759         } else {
1760                 r->l0 &= ~(xfs_bmbt_rec_base_t)XFS_MASK64LO(9);
1761                 r->l1 = ((xfs_bmbt_rec_base_t)v << 21) |
1762                           (r->l1 & (xfs_bmbt_rec_base_t)XFS_MASK64LO(21));
1763         }
1764 #endif  /* XFS_BIG_BLKNOS */
1765 }
1766
1767 /*
1768  * Set the startoff field in a bmap extent record.
1769  */
1770 void
1771 xfs_bmbt_set_startoff(
1772         xfs_bmbt_rec_host_t *r,
1773         xfs_fileoff_t   v)
1774 {
1775         ASSERT((v & XFS_MASK64HI(9)) == 0);
1776         r->l0 = (r->l0 & (xfs_bmbt_rec_base_t) XFS_MASK64HI(1)) |
1777                 ((xfs_bmbt_rec_base_t)v << 9) |
1778                   (r->l0 & (xfs_bmbt_rec_base_t)XFS_MASK64LO(9));
1779 }
1780
1781 /*
1782  * Set the extent state field in a bmap extent record.
1783  */
1784 void
1785 xfs_bmbt_set_state(
1786         xfs_bmbt_rec_host_t *r,
1787         xfs_exntst_t    v)
1788 {
1789         ASSERT(v == XFS_EXT_NORM || v == XFS_EXT_UNWRITTEN);
1790         if (v == XFS_EXT_NORM)
1791                 r->l0 &= XFS_MASK64LO(64 - BMBT_EXNTFLAG_BITLEN);
1792         else
1793                 r->l0 |= XFS_MASK64HI(BMBT_EXNTFLAG_BITLEN);
1794 }
1795
1796 /*
1797  * Convert in-memory form of btree root to on-disk form.
1798  */
1799 void
1800 xfs_bmbt_to_bmdr(
1801         xfs_bmbt_block_t        *rblock,
1802         int                     rblocklen,
1803         xfs_bmdr_block_t        *dblock,
1804         int                     dblocklen)
1805 {
1806         int                     dmxr;
1807         xfs_bmbt_key_t          *fkp;
1808         __be64                  *fpp;
1809         xfs_bmbt_key_t          *tkp;
1810         __be64                  *tpp;
1811
1812         ASSERT(be32_to_cpu(rblock->bb_magic) == XFS_BMAP_MAGIC);
1813         ASSERT(be64_to_cpu(rblock->bb_leftsib) == NULLDFSBNO);
1814         ASSERT(be64_to_cpu(rblock->bb_rightsib) == NULLDFSBNO);
1815         ASSERT(be16_to_cpu(rblock->bb_level) > 0);
1816         dblock->bb_level = rblock->bb_level;
1817         dblock->bb_numrecs = rblock->bb_numrecs;
1818         dmxr = (int)XFS_BTREE_BLOCK_MAXRECS(dblocklen, xfs_bmdr, 0);
1819         fkp = XFS_BMAP_BROOT_KEY_ADDR(rblock, 1, rblocklen);
1820         tkp = XFS_BTREE_KEY_ADDR(xfs_bmdr, dblock, 1);
1821         fpp = XFS_BMAP_BROOT_PTR_ADDR(rblock, 1, rblocklen);
1822         tpp = XFS_BTREE_PTR_ADDR(xfs_bmdr, dblock, 1, dmxr);
1823         dmxr = be16_to_cpu(dblock->bb_numrecs);
1824         memcpy(tkp, fkp, sizeof(*fkp) * dmxr);
1825         memcpy(tpp, fpp, sizeof(*fpp) * dmxr);
1826 }
1827
1828 /*
1829  * Check extent records, which have just been read, for
1830  * any bit in the extent flag field. ASSERT on debug
1831  * kernels, as this condition should not occur.
1832  * Return an error condition (1) if any flags found,
1833  * otherwise return 0.
1834  */
1835
1836 int
1837 xfs_check_nostate_extents(
1838         xfs_ifork_t             *ifp,
1839         xfs_extnum_t            idx,
1840         xfs_extnum_t            num)
1841 {
1842         for (; num > 0; num--, idx++) {
1843                 xfs_bmbt_rec_host_t *ep = xfs_iext_get_ext(ifp, idx);
1844                 if ((ep->l0 >>
1845                      (64 - BMBT_EXNTFLAG_BITLEN)) != 0) {
1846                         ASSERT(0);
1847                         return 1;
1848                 }
1849         }
1850         return 0;
1851 }
1852
1853
1854 STATIC struct xfs_btree_cur *
1855 xfs_bmbt_dup_cursor(
1856         struct xfs_btree_cur    *cur)
1857 {
1858         struct xfs_btree_cur    *new;
1859
1860         new = xfs_bmbt_init_cursor(cur->bc_mp, cur->bc_tp,
1861                         cur->bc_private.b.ip, cur->bc_private.b.whichfork);
1862
1863         /*
1864          * Copy the firstblock, flist, and flags values,
1865          * since init cursor doesn't get them.
1866          */
1867         new->bc_private.b.firstblock = cur->bc_private.b.firstblock;
1868         new->bc_private.b.flist = cur->bc_private.b.flist;
1869         new->bc_private.b.flags = cur->bc_private.b.flags;
1870
1871         return new;
1872 }
1873
1874 STATIC int
1875 xfs_bmbt_get_maxrecs(
1876         struct xfs_btree_cur    *cur,
1877         int                     level)
1878 {
1879         return XFS_BMAP_BLOCK_IMAXRECS(level, cur);
1880 }
1881
1882 STATIC void
1883 xfs_bmbt_init_key_from_rec(
1884         union xfs_btree_key     *key,
1885         union xfs_btree_rec     *rec)
1886 {
1887         key->bmbt.br_startoff =
1888                 cpu_to_be64(xfs_bmbt_disk_get_startoff(&rec->bmbt));
1889 }
1890
1891 STATIC void
1892 xfs_bmbt_init_ptr_from_cur(
1893         struct xfs_btree_cur    *cur,
1894         union xfs_btree_ptr     *ptr)
1895 {
1896         ptr->l = 0;
1897 }
1898
1899 STATIC __int64_t
1900 xfs_bmbt_key_diff(
1901         struct xfs_btree_cur    *cur,
1902         union xfs_btree_key     *key)
1903 {
1904         return (__int64_t)be64_to_cpu(key->bmbt.br_startoff) -
1905                                       cur->bc_rec.b.br_startoff;
1906 }
1907
1908 #ifdef XFS_BTREE_TRACE
1909 ktrace_t        *xfs_bmbt_trace_buf;
1910
1911 STATIC void
1912 xfs_bmbt_trace_enter(
1913         struct xfs_btree_cur    *cur,
1914         const char              *func,
1915         char                    *s,
1916         int                     type,
1917         int                     line,
1918         __psunsigned_t          a0,
1919         __psunsigned_t          a1,
1920         __psunsigned_t          a2,
1921         __psunsigned_t          a3,
1922         __psunsigned_t          a4,
1923         __psunsigned_t          a5,
1924         __psunsigned_t          a6,
1925         __psunsigned_t          a7,
1926         __psunsigned_t          a8,
1927         __psunsigned_t          a9,
1928         __psunsigned_t          a10)
1929 {
1930         struct xfs_inode        *ip = cur->bc_private.b.ip;
1931         int                     whichfork = cur->bc_private.b.whichfork;
1932
1933         ktrace_enter(xfs_bmbt_trace_buf,
1934                 (void *)((__psint_t)type | (whichfork << 8) | (line << 16)),
1935                 (void *)func, (void *)s, (void *)ip, (void *)cur,
1936                 (void *)a0, (void *)a1, (void *)a2, (void *)a3,
1937                 (void *)a4, (void *)a5, (void *)a6, (void *)a7,
1938                 (void *)a8, (void *)a9, (void *)a10);
1939         ktrace_enter(ip->i_btrace,
1940                 (void *)((__psint_t)type | (whichfork << 8) | (line << 16)),
1941                 (void *)func, (void *)s, (void *)ip, (void *)cur,
1942                 (void *)a0, (void *)a1, (void *)a2, (void *)a3,
1943                 (void *)a4, (void *)a5, (void *)a6, (void *)a7,
1944                 (void *)a8, (void *)a9, (void *)a10);
1945 }
1946
1947 STATIC void
1948 xfs_bmbt_trace_cursor(
1949         struct xfs_btree_cur    *cur,
1950         __uint32_t              *s0,
1951         __uint64_t              *l0,
1952         __uint64_t              *l1)
1953 {
1954         struct xfs_bmbt_rec_host r;
1955
1956         xfs_bmbt_set_all(&r, &cur->bc_rec.b);
1957
1958         *s0 = (cur->bc_nlevels << 24) |
1959               (cur->bc_private.b.flags << 16) |
1960                cur->bc_private.b.allocated;
1961         *l0 = r.l0;
1962         *l1 = r.l1;
1963 }
1964
1965 STATIC void
1966 xfs_bmbt_trace_key(
1967         struct xfs_btree_cur    *cur,
1968         union xfs_btree_key     *key,
1969         __uint64_t              *l0,
1970         __uint64_t              *l1)
1971 {
1972         *l0 = be64_to_cpu(key->bmbt.br_startoff);
1973         *l1 = 0;
1974 }
1975
1976 STATIC void
1977 xfs_bmbt_trace_record(
1978         struct xfs_btree_cur    *cur,
1979         union xfs_btree_rec     *rec,
1980         __uint64_t              *l0,
1981         __uint64_t              *l1,
1982         __uint64_t              *l2)
1983 {
1984         struct xfs_bmbt_irec    irec;
1985
1986         xfs_bmbt_disk_get_all(&rec->bmbt, &irec);
1987         *l0 = irec.br_startoff;
1988         *l1 = irec.br_startblock;
1989         *l2 = irec.br_blockcount;
1990 }
1991 #endif /* XFS_BTREE_TRACE */
1992
1993 static const struct xfs_btree_ops xfs_bmbt_ops = {
1994         .rec_len                = sizeof(xfs_bmbt_rec_t),
1995         .key_len                = sizeof(xfs_bmbt_key_t),
1996
1997         .dup_cursor             = xfs_bmbt_dup_cursor,
1998         .get_maxrecs            = xfs_bmbt_get_maxrecs,
1999         .init_key_from_rec      = xfs_bmbt_init_key_from_rec,
2000         .init_ptr_from_cur      = xfs_bmbt_init_ptr_from_cur,
2001         .key_diff               = xfs_bmbt_key_diff,
2002
2003 #ifdef XFS_BTREE_TRACE
2004         .trace_enter            = xfs_bmbt_trace_enter,
2005         .trace_cursor           = xfs_bmbt_trace_cursor,
2006         .trace_key              = xfs_bmbt_trace_key,
2007         .trace_record           = xfs_bmbt_trace_record,
2008 #endif
2009 };
2010
2011 /*
2012  * Allocate a new bmap btree cursor.
2013  */
2014 struct xfs_btree_cur *                          /* new bmap btree cursor */
2015 xfs_bmbt_init_cursor(
2016         struct xfs_mount        *mp,            /* file system mount point */
2017         struct xfs_trans        *tp,            /* transaction pointer */
2018         struct xfs_inode        *ip,            /* inode owning the btree */
2019         int                     whichfork)      /* data or attr fork */
2020 {
2021         struct xfs_ifork        *ifp = XFS_IFORK_PTR(ip, whichfork);
2022         struct xfs_btree_cur    *cur;
2023
2024         cur = kmem_zone_zalloc(xfs_btree_cur_zone, KM_SLEEP);
2025
2026         cur->bc_tp = tp;
2027         cur->bc_mp = mp;
2028         cur->bc_nlevels = be16_to_cpu(ifp->if_broot->bb_level) + 1;
2029         cur->bc_btnum = XFS_BTNUM_BMAP;
2030         cur->bc_blocklog = mp->m_sb.sb_blocklog;
2031
2032         cur->bc_ops = &xfs_bmbt_ops;
2033         cur->bc_flags = XFS_BTREE_LONG_PTRS | XFS_BTREE_ROOT_IN_INODE;
2034
2035         cur->bc_private.b.forksize = XFS_IFORK_SIZE(ip, whichfork);
2036         cur->bc_private.b.ip = ip;
2037         cur->bc_private.b.firstblock = NULLFSBLOCK;
2038         cur->bc_private.b.flist = NULL;
2039         cur->bc_private.b.allocated = 0;
2040         cur->bc_private.b.flags = 0;
2041         cur->bc_private.b.whichfork = whichfork;
2042
2043         return cur;
2044 }