SAFE public projects git trees. - safe/jmp/linux-2.6/blob - 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_rshift(xfs_btree_cur_t *, int, int *);
  57 STATIC int xfs_bmbt_split(xfs_btree_cur_t *, int, xfs_fsblock_t *,
  58                 __uint64_t *, xfs_btree_cur_t **, int *);
  59 STATIC int xfs_bmbt_updkey(xfs_btree_cur_t *, xfs_bmbt_key_t *, int);
  60
  61 #undef EXIT
  62
  63 #define ENTRY   XBT_ENTRY
  64 #define ERROR   XBT_ERROR
  65 #define EXIT    XBT_EXIT
  66
  67 /*
  68  * Keep the XFS_BMBT_TRACE_ names around for now until all code using them
  69  * is converted to be generic and thus switches to the XFS_BTREE_TRACE_ names.
  70  */
  71 #define XFS_BMBT_TRACE_ARGBI(c,b,i) \
  72         XFS_BTREE_TRACE_ARGBI(c,b,i)
  73 #define XFS_BMBT_TRACE_ARGBII(c,b,i,j) \
  74         XFS_BTREE_TRACE_ARGBII(c,b,i,j)
  75 #define XFS_BMBT_TRACE_ARGFFFI(c,o,b,i,j) \
  76         XFS_BTREE_TRACE_ARGFFFI(c,o,b,i,j)
  77 #define XFS_BMBT_TRACE_ARGI(c,i) \
  78         XFS_BTREE_TRACE_ARGI(c,i)
  79 #define XFS_BMBT_TRACE_ARGIFK(c,i,f,s) \
  80         XFS_BTREE_TRACE_ARGIPK(c,i,(union xfs_btree_ptr)f,s)
  81 #define XFS_BMBT_TRACE_ARGIFR(c,i,f,r) \
  82         XFS_BTREE_TRACE_ARGIPR(c,i, \
  83                 (union xfs_btree_ptr)f, (union xfs_btree_rec *)r)
  84 #define XFS_BMBT_TRACE_ARGIK(c,i,k) \
  85         XFS_BTREE_TRACE_ARGIK(c,i,(union xfs_btree_key *)k)
  86 #define XFS_BMBT_TRACE_CURSOR(c,s) \
  87         XFS_BTREE_TRACE_CURSOR(c,s)
  88
  89
  90 /*
  91  * Internal functions.
  92  */
  93
  94 /*
  95  * Delete record pointed to by cur/level.
  96  */
  97 STATIC int                                      /* error */
  98 xfs_bmbt_delrec(
  99         xfs_btree_cur_t         *cur,
 100         int                     level,
 101         int                     *stat)          /* success/failure */
 102 {
 103         xfs_bmbt_block_t        *block;         /* bmap btree block */
 104         xfs_fsblock_t           bno;            /* fs-relative block number */
 105         xfs_buf_t               *bp;            /* buffer for block */
 106         int                     error;          /* error return value */
 107         int                     i;              /* loop counter */
 108         int                     j;              /* temp state */
 109         xfs_bmbt_key_t          key;            /* bmap btree key */
 110         xfs_bmbt_key_t          *kp=NULL;       /* pointer to bmap btree key */
 111         xfs_fsblock_t           lbno;           /* left sibling block number */
 112         xfs_buf_t               *lbp;           /* left buffer pointer */
 113         xfs_bmbt_block_t        *left;          /* left btree block */
 114         xfs_bmbt_key_t          *lkp;           /* left btree key */
 115         xfs_bmbt_ptr_t          *lpp;           /* left address pointer */
 116         int                     lrecs=0;        /* left record count */
 117         xfs_bmbt_rec_t          *lrp;           /* left record pointer */
 118         xfs_mount_t             *mp;            /* file system mount point */
 119         xfs_bmbt_ptr_t          *pp;            /* pointer to bmap block addr */
 120         int                     ptr;            /* key/record index */
 121         xfs_fsblock_t           rbno;           /* right sibling block number */
 122         xfs_buf_t               *rbp;           /* right buffer pointer */
 123         xfs_bmbt_block_t        *right;         /* right btree block */
 124         xfs_bmbt_key_t          *rkp;           /* right btree key */
 125         xfs_bmbt_rec_t          *rp;            /* pointer to bmap btree rec */
 126         xfs_bmbt_ptr_t          *rpp;           /* right address pointer */
 127         xfs_bmbt_block_t        *rrblock;       /* right-right btree block */
 128         xfs_buf_t               *rrbp;          /* right-right buffer pointer */
 129         int                     rrecs=0;        /* right record count */
 130         xfs_bmbt_rec_t          *rrp;           /* right record pointer */
 131         xfs_btree_cur_t         *tcur;          /* temporary btree cursor */
 132         int                     numrecs;        /* temporary numrec count */
 133         int                     numlrecs, numrrecs;
 134
 135         XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
 136         XFS_BMBT_TRACE_ARGI(cur, level);
 137         ptr = cur->bc_ptrs[level];
 138         tcur = NULL;
 139         if (ptr == 0) {
 140                 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
 141                 *stat = 0;
 142                 return 0;
 143         }
 144         block = xfs_bmbt_get_block(cur, level, &bp);
 145         numrecs = be16_to_cpu(block->bb_numrecs);
 146 #ifdef DEBUG
 147         if ((error = xfs_btree_check_lblock(cur, block, level, bp))) {
 148                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
 149                 goto error0;
 150         }
 151 #endif
 152         if (ptr > numrecs) {
 153                 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
 154                 *stat = 0;
 155                 return 0;
 156         }
 157         XFS_STATS_INC(xs_bmbt_delrec);
 158         if (level > 0) {
 159                 kp = XFS_BMAP_KEY_IADDR(block, 1, cur);
 160                 pp = XFS_BMAP_PTR_IADDR(block, 1, cur);
 161 #ifdef DEBUG
 162                 for (i = ptr; i < numrecs; i++) {
 163                         if ((error = xfs_btree_check_lptr_disk(cur, pp[i], level))) {
 164                                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
 165                                 goto error0;
 166                         }
 167                 }
 168 #endif
 169                 if (ptr < numrecs) {
 170                         memmove(&kp[ptr - 1], &kp[ptr],
 171                                 (numrecs - ptr) * sizeof(*kp));
 172                         memmove(&pp[ptr - 1], &pp[ptr],
 173                                 (numrecs - ptr) * sizeof(*pp));
 174                         xfs_bmbt_log_ptrs(cur, bp, ptr, numrecs - 1);
 175                         xfs_bmbt_log_keys(cur, bp, ptr, numrecs - 1);
 176                 }
 177         } else {
 178                 rp = XFS_BMAP_REC_IADDR(block, 1, cur);
 179                 if (ptr < numrecs) {
 180                         memmove(&rp[ptr - 1], &rp[ptr],
 181                                 (numrecs - ptr) * sizeof(*rp));
 182                         xfs_bmbt_log_recs(cur, bp, ptr, numrecs - 1);
 183                 }
 184                 if (ptr == 1) {
 185                         key.br_startoff =
 186                                 cpu_to_be64(xfs_bmbt_disk_get_startoff(rp));
 187                         kp = &key;
 188                 }
 189         }
 190         numrecs--;
 191         block->bb_numrecs = cpu_to_be16(numrecs);
 192         xfs_bmbt_log_block(cur, bp, XFS_BB_NUMRECS);
 193         /*
 194          * We're at the root level.
 195          * First, shrink the root block in-memory.
 196          * Try to get rid of the next level down.
 197          * If we can't then there's nothing left to do.
 198          */
 199         if (level == cur->bc_nlevels - 1) {
 200                 xfs_iroot_realloc(cur->bc_private.b.ip, -1,
 201                         cur->bc_private.b.whichfork);
 202                 if ((error = xfs_bmbt_killroot(cur))) {
 203                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
 204                         goto error0;
 205                 }
 206                 if (level > 0 && (error = xfs_bmbt_decrement(cur, level, &j))) {
 207                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
 208                         goto error0;
 209                 }
 210                 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
 211                 *stat = 1;
 212                 return 0;
 213         }
 214         if (ptr == 1 && (error = xfs_bmbt_updkey(cur, kp, level + 1))) {
 215                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
 216                 goto error0;
 217         }
 218         if (numrecs >= XFS_BMAP_BLOCK_IMINRECS(level, cur)) {
 219                 if (level > 0 && (error = xfs_bmbt_decrement(cur, level, &j))) {
 220                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
 221                         goto error0;
 222                 }
 223                 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
 224                 *stat = 1;
 225                 return 0;
 226         }
 227         rbno = be64_to_cpu(block->bb_rightsib);
 228         lbno = be64_to_cpu(block->bb_leftsib);
 229         /*
 230          * One child of root, need to get a chance to copy its contents
 231          * into the root and delete it. Can't go up to next level,
 232          * there's nothing to delete there.
 233          */
 234         if (lbno == NULLFSBLOCK && rbno == NULLFSBLOCK &&
 235             level == cur->bc_nlevels - 2) {
 236                 if ((error = xfs_bmbt_killroot(cur))) {
 237                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
 238                         goto error0;
 239                 }
 240                 if (level > 0 && (error = xfs_bmbt_decrement(cur, level, &i))) {
 241                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
 242                         goto error0;
 243                 }
 244                 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
 245                 *stat = 1;
 246                 return 0;
 247         }
 248         ASSERT(rbno != NULLFSBLOCK || lbno != NULLFSBLOCK);
 249         if ((error = xfs_btree_dup_cursor(cur, &tcur))) {
 250                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
 251                 goto error0;
 252         }
 253         bno = NULLFSBLOCK;
 254         if (rbno != NULLFSBLOCK) {
 255                 i = xfs_btree_lastrec(tcur, level);
 256                 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
 257                 if ((error = xfs_bmbt_increment(tcur, level, &i))) {
 258                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
 259                         goto error0;
 260                 }
 261                 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
 262                 i = xfs_btree_lastrec(tcur, level);
 263                 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
 264                 rbp = tcur->bc_bufs[level];
 265                 right = XFS_BUF_TO_BMBT_BLOCK(rbp);
 266 #ifdef DEBUG
 267                 if ((error = xfs_btree_check_lblock(cur, right, level, rbp))) {
 268                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
 269                         goto error0;
 270                 }
 271 #endif
 272                 bno = be64_to_cpu(right->bb_leftsib);
 273                 if (be16_to_cpu(right->bb_numrecs) - 1 >=
 274                     XFS_BMAP_BLOCK_IMINRECS(level, cur)) {
 275                         if ((error = xfs_bmbt_lshift(tcur, level, &i))) {
 276                                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
 277                                 goto error0;
 278                         }
 279                         if (i) {
 280                                 ASSERT(be16_to_cpu(block->bb_numrecs) >=
 281                                        XFS_BMAP_BLOCK_IMINRECS(level, tcur));
 282                                 xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
 283                                 tcur = NULL;
 284                                 if (level > 0) {
 285                                         if ((error = xfs_bmbt_decrement(cur,
 286                                                         level, &i))) {
 287                                                 XFS_BMBT_TRACE_CURSOR(cur,
 288                                                         ERROR);
 289                                                 goto error0;
 290                                         }
 291                                 }
 292                                 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
 293                                 *stat = 1;
 294                                 return 0;
 295                         }
 296                 }
 297                 rrecs = be16_to_cpu(right->bb_numrecs);
 298                 if (lbno != NULLFSBLOCK) {
 299                         i = xfs_btree_firstrec(tcur, level);
 300                         XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
 301                         if ((error = xfs_bmbt_decrement(tcur, level, &i))) {
 302                                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
 303                                 goto error0;
 304                         }
 305                         XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
 306                 }
 307         }
 308         if (lbno != NULLFSBLOCK) {
 309                 i = xfs_btree_firstrec(tcur, level);
 310                 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
 311                 /*
 312                  * decrement to last in block
 313                  */
 314                 if ((error = xfs_bmbt_decrement(tcur, level, &i))) {
 315                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
 316                         goto error0;
 317                 }
 318                 i = xfs_btree_firstrec(tcur, level);
 319                 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
 320                 lbp = tcur->bc_bufs[level];
 321                 left = XFS_BUF_TO_BMBT_BLOCK(lbp);
 322 #ifdef DEBUG
 323                 if ((error = xfs_btree_check_lblock(cur, left, level, lbp))) {
 324                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
 325                         goto error0;
 326                 }
 327 #endif
 328                 bno = be64_to_cpu(left->bb_rightsib);
 329                 if (be16_to_cpu(left->bb_numrecs) - 1 >=
 330                     XFS_BMAP_BLOCK_IMINRECS(level, cur)) {
 331                         if ((error = xfs_bmbt_rshift(tcur, level, &i))) {
 332                                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
 333                                 goto error0;
 334                         }
 335                         if (i) {
 336                                 ASSERT(be16_to_cpu(block->bb_numrecs) >=
 337                                        XFS_BMAP_BLOCK_IMINRECS(level, tcur));
 338                                 xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
 339                                 tcur = NULL;
 340                                 if (level == 0)
 341                                         cur->bc_ptrs[0]++;
 342                                 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
 343                                 *stat = 1;
 344                                 return 0;
 345                         }
 346                 }
 347                 lrecs = be16_to_cpu(left->bb_numrecs);
 348         }
 349         xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
 350         tcur = NULL;
 351         mp = cur->bc_mp;
 352         ASSERT(bno != NULLFSBLOCK);
 353         if (lbno != NULLFSBLOCK &&
 354             lrecs + be16_to_cpu(block->bb_numrecs) <= XFS_BMAP_BLOCK_IMAXRECS(level, cur)) {
 355                 rbno = bno;
 356                 right = block;
 357                 rbp = bp;
 358                 if ((error = xfs_btree_read_bufl(mp, cur->bc_tp, lbno, 0, &lbp,
 359                                 XFS_BMAP_BTREE_REF))) {
 360                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
 361                         goto error0;
 362                 }
 363                 left = XFS_BUF_TO_BMBT_BLOCK(lbp);
 364                 if ((error = xfs_btree_check_lblock(cur, left, level, lbp))) {
 365                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
 366                         goto error0;
 367                 }
 368         } else if (rbno != NULLFSBLOCK &&
 369                    rrecs + be16_to_cpu(block->bb_numrecs) <=
 370                    XFS_BMAP_BLOCK_IMAXRECS(level, cur)) {
 371                 lbno = bno;
 372                 left = block;
 373                 lbp = bp;
 374                 if ((error = xfs_btree_read_bufl(mp, cur->bc_tp, rbno, 0, &rbp,
 375                                 XFS_BMAP_BTREE_REF))) {
 376                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
 377                         goto error0;
 378                 }
 379                 right = XFS_BUF_TO_BMBT_BLOCK(rbp);
 380                 if ((error = xfs_btree_check_lblock(cur, right, level, rbp))) {
 381                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
 382                         goto error0;
 383                 }
 384                 lrecs = be16_to_cpu(left->bb_numrecs);
 385         } else {
 386                 if (level > 0 && (error = xfs_bmbt_decrement(cur, level, &i))) {
 387                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
 388                         goto error0;
 389                 }
 390                 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
 391                 *stat = 1;
 392                 return 0;
 393         }
 394         numlrecs = be16_to_cpu(left->bb_numrecs);
 395         numrrecs = be16_to_cpu(right->bb_numrecs);
 396         if (level > 0) {
 397                 lkp = XFS_BMAP_KEY_IADDR(left, numlrecs + 1, cur);
 398                 lpp = XFS_BMAP_PTR_IADDR(left, numlrecs + 1, cur);
 399                 rkp = XFS_BMAP_KEY_IADDR(right, 1, cur);
 400                 rpp = XFS_BMAP_PTR_IADDR(right, 1, cur);
 401 #ifdef DEBUG
 402                 for (i = 0; i < numrrecs; i++) {
 403                         if ((error = xfs_btree_check_lptr_disk(cur, rpp[i], level))) {
 404                                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
 405                                 goto error0;
 406                         }
 407                 }
 408 #endif
 409                 memcpy(lkp, rkp, numrrecs * sizeof(*lkp));
 410                 memcpy(lpp, rpp, numrrecs * sizeof(*lpp));
 411                 xfs_bmbt_log_keys(cur, lbp, numlrecs + 1, numlrecs + numrrecs);
 412                 xfs_bmbt_log_ptrs(cur, lbp, numlrecs + 1, numlrecs + numrrecs);
 413         } else {
 414                 lrp = XFS_BMAP_REC_IADDR(left, numlrecs + 1, cur);
 415                 rrp = XFS_BMAP_REC_IADDR(right, 1, cur);
 416                 memcpy(lrp, rrp, numrrecs * sizeof(*lrp));
 417                 xfs_bmbt_log_recs(cur, lbp, numlrecs + 1, numlrecs + numrrecs);
 418         }
 419         be16_add_cpu(&left->bb_numrecs, numrrecs);
 420         left->bb_rightsib = right->bb_rightsib;
 421         xfs_bmbt_log_block(cur, lbp, XFS_BB_RIGHTSIB | XFS_BB_NUMRECS);
 422         if (be64_to_cpu(left->bb_rightsib) != NULLDFSBNO) {
 423                 if ((error = xfs_btree_read_bufl(mp, cur->bc_tp,
 424                                 be64_to_cpu(left->bb_rightsib),
 425                                 0, &rrbp, XFS_BMAP_BTREE_REF))) {
 426                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
 427                         goto error0;
 428                 }
 429                 rrblock = XFS_BUF_TO_BMBT_BLOCK(rrbp);
 430                 if ((error = xfs_btree_check_lblock(cur, rrblock, level, rrbp))) {
 431                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
 432                         goto error0;
 433                 }
 434                 rrblock->bb_leftsib = cpu_to_be64(lbno);
 435                 xfs_bmbt_log_block(cur, rrbp, XFS_BB_LEFTSIB);
 436         }
 437         xfs_bmap_add_free(XFS_DADDR_TO_FSB(mp, XFS_BUF_ADDR(rbp)), 1,
 438                 cur->bc_private.b.flist, mp);
 439         cur->bc_private.b.ip->i_d.di_nblocks--;
 440         xfs_trans_log_inode(cur->bc_tp, cur->bc_private.b.ip, XFS_ILOG_CORE);
 441         XFS_TRANS_MOD_DQUOT_BYINO(mp, cur->bc_tp, cur->bc_private.b.ip,
 442                         XFS_TRANS_DQ_BCOUNT, -1L);
 443         xfs_trans_binval(cur->bc_tp, rbp);
 444         if (bp != lbp) {
 445                 cur->bc_bufs[level] = lbp;
 446                 cur->bc_ptrs[level] += lrecs;
 447                 cur->bc_ra[level] = 0;
 448         } else if ((error = xfs_bmbt_increment(cur, level + 1, &i))) {
 449                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
 450                 goto error0;
 451         }
 452         if (level > 0)
 453                 cur->bc_ptrs[level]--;
 454         XFS_BMBT_TRACE_CURSOR(cur, EXIT);
 455         *stat = 2;
 456         return 0;
 457
 458 error0:
 459         if (tcur)
 460                 xfs_btree_del_cursor(tcur, XFS_BTREE_ERROR);
 461         return error;
 462 }
 463
 464 /*
 465  * Insert one record/level.  Return information to the caller
 466  * allowing the next level up to proceed if necessary.
 467  */
 468 STATIC int                                      /* error */
 469 xfs_bmbt_insrec(
 470         xfs_btree_cur_t         *cur,
 471         int                     level,
 472         xfs_fsblock_t           *bnop,
 473         xfs_bmbt_rec_t          *recp,
 474         xfs_btree_cur_t         **curp,
 475         int                     *stat)          /* no-go/done/continue */
 476 {
 477         xfs_bmbt_block_t        *block;         /* bmap btree block */
 478         xfs_buf_t               *bp;            /* buffer for block */
 479         int                     error;          /* error return value */
 480         int                     i;              /* loop index */
 481         xfs_bmbt_key_t          key;            /* bmap btree key */
 482         xfs_bmbt_key_t          *kp=NULL;       /* pointer to bmap btree key */
 483         int                     logflags;       /* inode logging flags */
 484         xfs_fsblock_t           nbno;           /* new block number */
 485         struct xfs_btree_cur    *ncur;          /* new btree cursor */
 486         __uint64_t              startoff;       /* new btree key value */
 487         xfs_bmbt_rec_t          nrec;           /* new record count */
 488         int                     optr;           /* old key/record index */
 489         xfs_bmbt_ptr_t          *pp;            /* pointer to bmap block addr */
 490         int                     ptr;            /* key/record index */
 491         xfs_bmbt_rec_t          *rp=NULL;       /* pointer to bmap btree rec */
 492         int                     numrecs;
 493
 494         ASSERT(level < cur->bc_nlevels);
 495         XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
 496         XFS_BMBT_TRACE_ARGIFR(cur, level, *bnop, recp);
 497         ncur = NULL;
 498         key.br_startoff = cpu_to_be64(xfs_bmbt_disk_get_startoff(recp));
 499         optr = ptr = cur->bc_ptrs[level];
 500         if (ptr == 0) {
 501                 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
 502                 *stat = 0;
 503                 return 0;
 504         }
 505         XFS_STATS_INC(xs_bmbt_insrec);
 506         block = xfs_bmbt_get_block(cur, level, &bp);
 507         numrecs = be16_to_cpu(block->bb_numrecs);
 508 #ifdef DEBUG
 509         if ((error = xfs_btree_check_lblock(cur, block, level, bp))) {
 510                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
 511                 return error;
 512         }
 513         if (ptr <= numrecs) {
 514                 if (level == 0) {
 515                         rp = XFS_BMAP_REC_IADDR(block, ptr, cur);
 516                         xfs_btree_check_rec(XFS_BTNUM_BMAP, recp, rp);
 517                 } else {
 518                         kp = XFS_BMAP_KEY_IADDR(block, ptr, cur);
 519                         xfs_btree_check_key(XFS_BTNUM_BMAP, &key, kp);
 520                 }
 521         }
 522 #endif
 523         nbno = NULLFSBLOCK;
 524         if (numrecs == XFS_BMAP_BLOCK_IMAXRECS(level, cur)) {
 525                 if (numrecs < XFS_BMAP_BLOCK_DMAXRECS(level, cur)) {
 526                         /*
 527                          * A root block, that can be made bigger.
 528                          */
 529                         xfs_iroot_realloc(cur->bc_private.b.ip, 1,
 530                                 cur->bc_private.b.whichfork);
 531                         block = xfs_bmbt_get_block(cur, level, &bp);
 532                 } else if (level == cur->bc_nlevels - 1) {
 533                         if ((error = xfs_bmbt_newroot(cur, &logflags, stat)) ||
 534                             *stat == 0) {
 535                                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
 536                                 return error;
 537                         }
 538                         xfs_trans_log_inode(cur->bc_tp, cur->bc_private.b.ip,
 539                                 logflags);
 540                         block = xfs_bmbt_get_block(cur, level, &bp);
 541                 } else {
 542                         if ((error = xfs_bmbt_rshift(cur, level, &i))) {
 543                                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
 544                                 return error;
 545                         }
 546                         if (i) {
 547                                 /* nothing */
 548                         } else {
 549                                 if ((error = xfs_bmbt_lshift(cur, level, &i))) {
 550                                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
 551                                         return error;
 552                                 }
 553                                 if (i) {
 554                                         optr = ptr = cur->bc_ptrs[level];
 555                                 } else {
 556                                         if ((error = xfs_bmbt_split(cur, level,
 557                                                         &nbno, &startoff, &ncur,
 558                                                         &i))) {
 559                                                 XFS_BMBT_TRACE_CURSOR(cur,
 560                                                         ERROR);
 561                                                 return error;
 562                                         }
 563                                         if (i) {
 564                                                 block = xfs_bmbt_get_block(
 565                                                             cur, level, &bp);
 566 #ifdef DEBUG
 567                                                 if ((error =
 568                                                     xfs_btree_check_lblock(cur,
 569                                                             block, level, bp))) {
 570                                                         XFS_BMBT_TRACE_CURSOR(
 571                                                                 cur, ERROR);
 572                                                         return error;
 573                                                 }
 574 #endif
 575                                                 ptr = cur->bc_ptrs[level];
 576                                                 xfs_bmbt_disk_set_allf(&nrec,
 577                                                         startoff, 0, 0,
 578                                                         XFS_EXT_NORM);
 579                                         } else {
 580                                                 XFS_BMBT_TRACE_CURSOR(cur,
 581                                                         EXIT);
 582                                                 *stat = 0;
 583                                                 return 0;
 584                                         }
 585                                 }
 586                         }
 587                 }
 588         }
 589         numrecs = be16_to_cpu(block->bb_numrecs);
 590         if (level > 0) {
 591                 kp = XFS_BMAP_KEY_IADDR(block, 1, cur);
 592                 pp = XFS_BMAP_PTR_IADDR(block, 1, cur);
 593 #ifdef DEBUG
 594                 for (i = numrecs; i >= ptr; i--) {
 595                         if ((error = xfs_btree_check_lptr_disk(cur, pp[i - 1],
 596                                         level))) {
 597                                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
 598                                 return error;
 599                         }
 600                 }
 601 #endif
 602                 memmove(&kp[ptr], &kp[ptr - 1],
 603                         (numrecs - ptr + 1) * sizeof(*kp));
 604                 memmove(&pp[ptr], &pp[ptr - 1],
 605                         (numrecs - ptr + 1) * sizeof(*pp));
 606 #ifdef DEBUG
 607                 if ((error = xfs_btree_check_lptr(cur, *bnop, level))) {
 608                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
 609                         return error;
 610                 }
 611 #endif
 612                 kp[ptr - 1] = key;
 613                 pp[ptr - 1] = cpu_to_be64(*bnop);
 614                 numrecs++;
 615                 block->bb_numrecs = cpu_to_be16(numrecs);
 616                 xfs_bmbt_log_keys(cur, bp, ptr, numrecs);
 617                 xfs_bmbt_log_ptrs(cur, bp, ptr, numrecs);
 618         } else {
 619                 rp = XFS_BMAP_REC_IADDR(block, 1, cur);
 620                 memmove(&rp[ptr], &rp[ptr - 1],
 621                         (numrecs - ptr + 1) * sizeof(*rp));
 622                 rp[ptr - 1] = *recp;
 623                 numrecs++;
 624                 block->bb_numrecs = cpu_to_be16(numrecs);
 625                 xfs_bmbt_log_recs(cur, bp, ptr, numrecs);
 626         }
 627         xfs_bmbt_log_block(cur, bp, XFS_BB_NUMRECS);
 628 #ifdef DEBUG
 629         if (ptr < numrecs) {
 630                 if (level == 0)
 631                         xfs_btree_check_rec(XFS_BTNUM_BMAP, rp + ptr - 1,
 632                                 rp + ptr);
 633                 else
 634                         xfs_btree_check_key(XFS_BTNUM_BMAP, kp + ptr - 1,
 635                                 kp + ptr);
 636         }
 637 #endif
 638         if (optr == 1 && (error = xfs_bmbt_updkey(cur, &key, level + 1))) {
 639                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
 640                 return error;
 641         }
 642         *bnop = nbno;
 643         if (nbno != NULLFSBLOCK) {
 644                 *recp = nrec;
 645                 *curp = ncur;
 646         }
 647         XFS_BMBT_TRACE_CURSOR(cur, EXIT);
 648         *stat = 1;
 649         return 0;
 650 }
 651
 652 STATIC int
 653 xfs_bmbt_killroot(
 654         xfs_btree_cur_t         *cur)
 655 {
 656         xfs_bmbt_block_t        *block;
 657         xfs_bmbt_block_t        *cblock;
 658         xfs_buf_t               *cbp;
 659         xfs_bmbt_key_t          *ckp;
 660         xfs_bmbt_ptr_t          *cpp;
 661 #ifdef DEBUG
 662         int                     error;
 663 #endif
 664         int                     i;
 665         xfs_bmbt_key_t          *kp;
 666         xfs_inode_t             *ip;
 667         xfs_ifork_t             *ifp;
 668         int                     level;
 669         xfs_bmbt_ptr_t          *pp;
 670
 671         XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
 672         level = cur->bc_nlevels - 1;
 673         ASSERT(level >= 1);
 674         /*
 675          * Don't deal with the root block needs to be a leaf case.
 676          * We're just going to turn the thing back into extents anyway.
 677          */
 678         if (level == 1) {
 679                 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
 680                 return 0;
 681         }
 682         block = xfs_bmbt_get_block(cur, level, &cbp);
 683         /*
 684          * Give up if the root has multiple children.
 685          */
 686         if (be16_to_cpu(block->bb_numrecs) != 1) {
 687                 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
 688                 return 0;
 689         }
 690         /*
 691          * Only do this if the next level will fit.
 692          * Then the data must be copied up to the inode,
 693          * instead of freeing the root you free the next level.
 694          */
 695         cbp = cur->bc_bufs[level - 1];
 696         cblock = XFS_BUF_TO_BMBT_BLOCK(cbp);
 697         if (be16_to_cpu(cblock->bb_numrecs) > XFS_BMAP_BLOCK_DMAXRECS(level, cur)) {
 698                 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
 699                 return 0;
 700         }
 701         ASSERT(be64_to_cpu(cblock->bb_leftsib) == NULLDFSBNO);
 702         ASSERT(be64_to_cpu(cblock->bb_rightsib) == NULLDFSBNO);
 703         ip = cur->bc_private.b.ip;
 704         ifp = XFS_IFORK_PTR(ip, cur->bc_private.b.whichfork);
 705         ASSERT(XFS_BMAP_BLOCK_IMAXRECS(level, cur) ==
 706                XFS_BMAP_BROOT_MAXRECS(ifp->if_broot_bytes));
 707         i = (int)(be16_to_cpu(cblock->bb_numrecs) - XFS_BMAP_BLOCK_IMAXRECS(level, cur));
 708         if (i) {
 709                 xfs_iroot_realloc(ip, i, cur->bc_private.b.whichfork);
 710                 block = ifp->if_broot;
 711         }
 712         be16_add_cpu(&block->bb_numrecs, i);
 713         ASSERT(block->bb_numrecs == cblock->bb_numrecs);
 714         kp = XFS_BMAP_KEY_IADDR(block, 1, cur);
 715         ckp = XFS_BMAP_KEY_IADDR(cblock, 1, cur);
 716         memcpy(kp, ckp, be16_to_cpu(block->bb_numrecs) * sizeof(*kp));
 717         pp = XFS_BMAP_PTR_IADDR(block, 1, cur);
 718         cpp = XFS_BMAP_PTR_IADDR(cblock, 1, cur);
 719 #ifdef DEBUG
 720         for (i = 0; i < be16_to_cpu(cblock->bb_numrecs); i++) {
 721                 if ((error = xfs_btree_check_lptr_disk(cur, cpp[i], level - 1))) {
 722                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
 723                         return error;
 724                 }
 725         }
 726 #endif
 727         memcpy(pp, cpp, be16_to_cpu(block->bb_numrecs) * sizeof(*pp));
 728         xfs_bmap_add_free(XFS_DADDR_TO_FSB(cur->bc_mp, XFS_BUF_ADDR(cbp)), 1,
 729                         cur->bc_private.b.flist, cur->bc_mp);
 730         ip->i_d.di_nblocks--;
 731         XFS_TRANS_MOD_DQUOT_BYINO(cur->bc_mp, cur->bc_tp, ip,
 732                         XFS_TRANS_DQ_BCOUNT, -1L);
 733         xfs_trans_binval(cur->bc_tp, cbp);
 734         cur->bc_bufs[level - 1] = NULL;
 735         be16_add_cpu(&block->bb_level, -1);
 736         xfs_trans_log_inode(cur->bc_tp, ip,
 737                 XFS_ILOG_CORE | XFS_ILOG_FBROOT(cur->bc_private.b.whichfork));
 738         cur->bc_nlevels--;
 739         XFS_BMBT_TRACE_CURSOR(cur, EXIT);
 740         return 0;
 741 }
 742
 743 /*
 744  * Log key values from the btree block.
 745  */
 746 STATIC void
 747 xfs_bmbt_log_keys(
 748         xfs_btree_cur_t *cur,
 749         xfs_buf_t       *bp,
 750         int             kfirst,
 751         int             klast)
 752 {
 753         xfs_trans_t     *tp;
 754
 755         XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
 756         XFS_BMBT_TRACE_ARGBII(cur, bp, kfirst, klast);
 757         tp = cur->bc_tp;
 758         if (bp) {
 759                 xfs_bmbt_block_t        *block;
 760                 int                     first;
 761                 xfs_bmbt_key_t          *kp;
 762                 int                     last;
 763
 764                 block = XFS_BUF_TO_BMBT_BLOCK(bp);
 765                 kp = XFS_BMAP_KEY_DADDR(block, 1, cur);
 766                 first = (int)((xfs_caddr_t)&kp[kfirst - 1] - (xfs_caddr_t)block);
 767                 last = (int)(((xfs_caddr_t)&kp[klast] - 1) - (xfs_caddr_t)block);
 768                 xfs_trans_log_buf(tp, bp, first, last);
 769         } else {
 770                 xfs_inode_t              *ip;
 771
 772                 ip = cur->bc_private.b.ip;
 773                 xfs_trans_log_inode(tp, ip,
 774                         XFS_ILOG_FBROOT(cur->bc_private.b.whichfork));
 775         }
 776         XFS_BMBT_TRACE_CURSOR(cur, EXIT);
 777 }
 778
 779 /*
 780  * Log pointer values from the btree block.
 781  */
 782 STATIC void
 783 xfs_bmbt_log_ptrs(
 784         xfs_btree_cur_t *cur,
 785         xfs_buf_t       *bp,
 786         int             pfirst,
 787         int             plast)
 788 {
 789         xfs_trans_t     *tp;
 790
 791         XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
 792         XFS_BMBT_TRACE_ARGBII(cur, bp, pfirst, plast);
 793         tp = cur->bc_tp;
 794         if (bp) {
 795                 xfs_bmbt_block_t        *block;
 796                 int                     first;
 797                 int                     last;
 798                 xfs_bmbt_ptr_t          *pp;
 799
 800                 block = XFS_BUF_TO_BMBT_BLOCK(bp);
 801                 pp = XFS_BMAP_PTR_DADDR(block, 1, cur);
 802                 first = (int)((xfs_caddr_t)&pp[pfirst - 1] - (xfs_caddr_t)block);
 803                 last = (int)(((xfs_caddr_t)&pp[plast] - 1) - (xfs_caddr_t)block);
 804                 xfs_trans_log_buf(tp, bp, first, last);
 805         } else {
 806                 xfs_inode_t             *ip;
 807
 808                 ip = cur->bc_private.b.ip;
 809                 xfs_trans_log_inode(tp, ip,
 810                         XFS_ILOG_FBROOT(cur->bc_private.b.whichfork));
 811         }
 812         XFS_BMBT_TRACE_CURSOR(cur, EXIT);
 813 }
 814
 815 /*
 816  * Lookup the record.  The cursor is made to point to it, based on dir.
 817  */
 818 STATIC int                              /* error */
 819 xfs_bmbt_lookup(
 820         xfs_btree_cur_t         *cur,
 821         xfs_lookup_t            dir,
 822         int                     *stat)          /* success/failure */
 823 {
 824         xfs_bmbt_block_t        *block=NULL;
 825         xfs_buf_t               *bp;
 826         xfs_daddr_t             d;
 827         xfs_sfiloff_t           diff;
 828         int                     error;          /* error return value */
 829         xfs_fsblock_t           fsbno=0;
 830         int                     high;
 831         int                     i;
 832         int                     keyno=0;
 833         xfs_bmbt_key_t          *kkbase=NULL;
 834         xfs_bmbt_key_t          *kkp;
 835         xfs_bmbt_rec_t          *krbase=NULL;
 836         xfs_bmbt_rec_t          *krp;
 837         int                     level;
 838         int                     low;
 839         xfs_mount_t             *mp;
 840         xfs_bmbt_ptr_t          *pp;
 841         xfs_bmbt_irec_t         *rp;
 842         xfs_fileoff_t           startoff;
 843         xfs_trans_t             *tp;
 844
 845         XFS_STATS_INC(xs_bmbt_lookup);
 846         XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
 847         XFS_BMBT_TRACE_ARGI(cur, (int)dir);
 848         tp = cur->bc_tp;
 849         mp = cur->bc_mp;
 850         rp = &cur->bc_rec.b;
 851         for (level = cur->bc_nlevels - 1, diff = 1; level >= 0; level--) {
 852                 if (level < cur->bc_nlevels - 1) {
 853                         d = XFS_FSB_TO_DADDR(mp, fsbno);
 854                         bp = cur->bc_bufs[level];
 855                         if (bp && XFS_BUF_ADDR(bp) != d)
 856                                 bp = NULL;
 857                         if (!bp) {
 858                                 if ((error = xfs_btree_read_bufl(mp, tp, fsbno,
 859                                                 0, &bp, XFS_BMAP_BTREE_REF))) {
 860                                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
 861                                         return error;
 862                                 }
 863                                 xfs_btree_setbuf(cur, level, bp);
 864                                 block = XFS_BUF_TO_BMBT_BLOCK(bp);
 865                                 if ((error = xfs_btree_check_lblock(cur, block,
 866                                                 level, bp))) {
 867                                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
 868                                         return error;
 869                                 }
 870                         } else
 871                                 block = XFS_BUF_TO_BMBT_BLOCK(bp);
 872                 } else
 873                         block = xfs_bmbt_get_block(cur, level, &bp);
 874                 if (diff == 0)
 875                         keyno = 1;
 876                 else {
 877                         if (level > 0)
 878                                 kkbase = XFS_BMAP_KEY_IADDR(block, 1, cur);
 879                         else
 880                                 krbase = XFS_BMAP_REC_IADDR(block, 1, cur);
 881                         low = 1;
 882                         if (!(high = be16_to_cpu(block->bb_numrecs))) {
 883                                 ASSERT(level == 0);
 884                                 cur->bc_ptrs[0] = dir != XFS_LOOKUP_LE;
 885                                 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
 886                                 *stat = 0;
 887                                 return 0;
 888                         }
 889                         while (low <= high) {
 890                                 XFS_STATS_INC(xs_bmbt_compare);
 891                                 keyno = (low + high) >> 1;
 892                                 if (level > 0) {
 893                                         kkp = kkbase + keyno - 1;
 894                                         startoff = be64_to_cpu(kkp->br_startoff);
 895                                 } else {
 896                                         krp = krbase + keyno - 1;
 897                                         startoff = xfs_bmbt_disk_get_startoff(krp);
 898                                 }
 899                                 diff = (xfs_sfiloff_t)
 900                                                 (startoff - rp->br_startoff);
 901                                 if (diff < 0)
 902                                         low = keyno + 1;
 903                                 else if (diff > 0)
 904                                         high = keyno - 1;
 905                                 else
 906                                         break;
 907                         }
 908                 }
 909                 if (level > 0) {
 910                         if (diff > 0 && --keyno < 1)
 911                                 keyno = 1;
 912                         pp = XFS_BMAP_PTR_IADDR(block, keyno, cur);
 913                         fsbno = be64_to_cpu(*pp);
 914 #ifdef DEBUG
 915                         if ((error = xfs_btree_check_lptr(cur, fsbno, level))) {
 916                                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
 917                                 return error;
 918                         }
 919 #endif
 920                         cur->bc_ptrs[level] = keyno;
 921                 }
 922         }
 923         if (dir != XFS_LOOKUP_LE && diff < 0) {
 924                 keyno++;
 925                 /*
 926                  * If ge search and we went off the end of the block, but it's
 927                  * not the last block, we're in the wrong block.
 928                  */
 929                 if (dir == XFS_LOOKUP_GE && keyno > be16_to_cpu(block->bb_numrecs) &&
 930                     be64_to_cpu(block->bb_rightsib) != NULLDFSBNO) {
 931                         cur->bc_ptrs[0] = keyno;
 932                         if ((error = xfs_bmbt_increment(cur, 0, &i))) {
 933                                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
 934                                 return error;
 935                         }
 936                         XFS_WANT_CORRUPTED_RETURN(i == 1);
 937                         XFS_BMBT_TRACE_CURSOR(cur, EXIT);
 938                         *stat = 1;
 939                         return 0;
 940                 }
 941         }
 942         else if (dir == XFS_LOOKUP_LE && diff > 0)
 943                 keyno--;
 944         cur->bc_ptrs[0] = keyno;
 945         if (keyno == 0 || keyno > be16_to_cpu(block->bb_numrecs)) {
 946                 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
 947                 *stat = 0;
 948         } else {
 949                 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
 950                 *stat = ((dir != XFS_LOOKUP_EQ) || (diff == 0));
 951         }
 952         return 0;
 953 }
 954
 955 /*
 956  * Move 1 record left from cur/level if possible.
 957  * Update cur to reflect the new path.
 958  */
 959 STATIC int                                      /* error */
 960 xfs_bmbt_lshift(
 961         xfs_btree_cur_t         *cur,
 962         int                     level,
 963         int                     *stat)          /* success/failure */
 964 {
 965         int                     error;          /* error return value */
 966 #ifdef DEBUG
 967         int                     i;              /* loop counter */
 968 #endif
 969         xfs_bmbt_key_t          key;            /* bmap btree key */
 970         xfs_buf_t               *lbp;           /* left buffer pointer */
 971         xfs_bmbt_block_t        *left;          /* left btree block */
 972         xfs_bmbt_key_t          *lkp=NULL;      /* left btree key */
 973         xfs_bmbt_ptr_t          *lpp;           /* left address pointer */
 974         int                     lrecs;          /* left record count */
 975         xfs_bmbt_rec_t          *lrp=NULL;      /* left record pointer */
 976         xfs_mount_t             *mp;            /* file system mount point */
 977         xfs_buf_t               *rbp;           /* right buffer pointer */
 978         xfs_bmbt_block_t        *right;         /* right btree block */
 979         xfs_bmbt_key_t          *rkp=NULL;      /* right btree key */
 980         xfs_bmbt_ptr_t          *rpp=NULL;      /* right address pointer */
 981         xfs_bmbt_rec_t          *rrp=NULL;      /* right record pointer */
 982         int                     rrecs;          /* right record count */
 983
 984         XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
 985         XFS_BMBT_TRACE_ARGI(cur, level);
 986         if (level == cur->bc_nlevels - 1) {
 987                 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
 988                 *stat = 0;
 989                 return 0;
 990         }
 991         rbp = cur->bc_bufs[level];
 992         right = XFS_BUF_TO_BMBT_BLOCK(rbp);
 993 #ifdef DEBUG
 994         if ((error = xfs_btree_check_lblock(cur, right, level, rbp))) {
 995                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
 996                 return error;
 997         }
 998 #endif
 999         if (be64_to_cpu(right->bb_leftsib) == NULLDFSBNO) {
1000                 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1001                 *stat = 0;
1002                 return 0;
1003         }
1004         if (cur->bc_ptrs[level] <= 1) {
1005                 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1006                 *stat = 0;
1007                 return 0;
1008         }
1009         mp = cur->bc_mp;
1010         if ((error = xfs_btree_read_bufl(mp, cur->bc_tp, be64_to_cpu(right->bb_leftsib), 0,
1011                         &lbp, XFS_BMAP_BTREE_REF))) {
1012                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1013                 return error;
1014         }
1015         left = XFS_BUF_TO_BMBT_BLOCK(lbp);
1016         if ((error = xfs_btree_check_lblock(cur, left, level, lbp))) {
1017                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1018                 return error;
1019         }
1020         if (be16_to_cpu(left->bb_numrecs) == XFS_BMAP_BLOCK_IMAXRECS(level, cur)) {
1021                 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1022                 *stat = 0;
1023                 return 0;
1024         }
1025         lrecs = be16_to_cpu(left->bb_numrecs) + 1;
1026         if (level > 0) {
1027                 lkp = XFS_BMAP_KEY_IADDR(left, lrecs, cur);
1028                 rkp = XFS_BMAP_KEY_IADDR(right, 1, cur);
1029                 *lkp = *rkp;
1030                 xfs_bmbt_log_keys(cur, lbp, lrecs, lrecs);
1031                 lpp = XFS_BMAP_PTR_IADDR(left, lrecs, cur);
1032                 rpp = XFS_BMAP_PTR_IADDR(right, 1, cur);
1033 #ifdef DEBUG
1034                 if ((error = xfs_btree_check_lptr_disk(cur, *rpp, level))) {
1035                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1036                         return error;
1037                 }
1038 #endif
1039                 *lpp = *rpp;
1040                 xfs_bmbt_log_ptrs(cur, lbp, lrecs, lrecs);
1041         } else {
1042                 lrp = XFS_BMAP_REC_IADDR(left, lrecs, cur);
1043                 rrp = XFS_BMAP_REC_IADDR(right, 1, cur);
1044                 *lrp = *rrp;
1045                 xfs_bmbt_log_recs(cur, lbp, lrecs, lrecs);
1046         }
1047         left->bb_numrecs = cpu_to_be16(lrecs);
1048         xfs_bmbt_log_block(cur, lbp, XFS_BB_NUMRECS);
1049 #ifdef DEBUG
1050         if (level > 0)
1051                 xfs_btree_check_key(XFS_BTNUM_BMAP, lkp - 1, lkp);
1052         else
1053                 xfs_btree_check_rec(XFS_BTNUM_BMAP, lrp - 1, lrp);
1054 #endif
1055         rrecs = be16_to_cpu(right->bb_numrecs) - 1;
1056         right->bb_numrecs = cpu_to_be16(rrecs);
1057         xfs_bmbt_log_block(cur, rbp, XFS_BB_NUMRECS);
1058         if (level > 0) {
1059 #ifdef DEBUG
1060                 for (i = 0; i < rrecs; i++) {
1061                         if ((error = xfs_btree_check_lptr_disk(cur, rpp[i + 1],
1062                                         level))) {
1063                                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1064                                 return error;
1065                         }
1066                 }
1067 #endif
1068                 memmove(rkp, rkp + 1, rrecs * sizeof(*rkp));
1069                 memmove(rpp, rpp + 1, rrecs * sizeof(*rpp));
1070                 xfs_bmbt_log_keys(cur, rbp, 1, rrecs);
1071                 xfs_bmbt_log_ptrs(cur, rbp, 1, rrecs);
1072         } else {
1073                 memmove(rrp, rrp + 1, rrecs * sizeof(*rrp));
1074                 xfs_bmbt_log_recs(cur, rbp, 1, rrecs);
1075                 key.br_startoff = cpu_to_be64(xfs_bmbt_disk_get_startoff(rrp));
1076                 rkp = &key;
1077         }
1078         if ((error = xfs_bmbt_updkey(cur, rkp, level + 1))) {
1079                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1080                 return error;
1081         }
1082         cur->bc_ptrs[level]--;
1083         XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1084         *stat = 1;
1085         return 0;
1086 }
1087
1088 /*
1089  * Move 1 record right from cur/level if possible.
1090  * Update cur to reflect the new path.
1091  */
1092 STATIC int                                      /* error */
1093 xfs_bmbt_rshift(
1094         xfs_btree_cur_t         *cur,
1095         int                     level,
1096         int                     *stat)          /* success/failure */
1097 {
1098         int                     error;          /* error return value */
1099         int                     i;              /* loop counter */
1100         xfs_bmbt_key_t          key;            /* bmap btree key */
1101         xfs_buf_t               *lbp;           /* left buffer pointer */
1102         xfs_bmbt_block_t        *left;          /* left btree block */
1103         xfs_bmbt_key_t          *lkp;           /* left btree key */
1104         xfs_bmbt_ptr_t          *lpp;           /* left address pointer */
1105         xfs_bmbt_rec_t          *lrp;           /* left record pointer */
1106         xfs_mount_t             *mp;            /* file system mount point */
1107         xfs_buf_t               *rbp;           /* right buffer pointer */
1108         xfs_bmbt_block_t        *right;         /* right btree block */
1109         xfs_bmbt_key_t          *rkp;           /* right btree key */
1110         xfs_bmbt_ptr_t          *rpp;           /* right address pointer */
1111         xfs_bmbt_rec_t          *rrp=NULL;      /* right record pointer */
1112         struct xfs_btree_cur    *tcur;          /* temporary btree cursor */
1113
1114         XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
1115         XFS_BMBT_TRACE_ARGI(cur, level);
1116         if (level == cur->bc_nlevels - 1) {
1117                 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1118                 *stat = 0;
1119                 return 0;
1120         }
1121         lbp = cur->bc_bufs[level];
1122         left = XFS_BUF_TO_BMBT_BLOCK(lbp);
1123 #ifdef DEBUG
1124         if ((error = xfs_btree_check_lblock(cur, left, level, lbp))) {
1125                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1126                 return error;
1127         }
1128 #endif
1129         if (be64_to_cpu(left->bb_rightsib) == NULLDFSBNO) {
1130                 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1131                 *stat = 0;
1132                 return 0;
1133         }
1134         if (cur->bc_ptrs[level] >= be16_to_cpu(left->bb_numrecs)) {
1135                 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1136                 *stat = 0;
1137                 return 0;
1138         }
1139         mp = cur->bc_mp;
1140         if ((error = xfs_btree_read_bufl(mp, cur->bc_tp, be64_to_cpu(left->bb_rightsib), 0,
1141                         &rbp, XFS_BMAP_BTREE_REF))) {
1142                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1143                 return error;
1144         }
1145         right = XFS_BUF_TO_BMBT_BLOCK(rbp);
1146         if ((error = xfs_btree_check_lblock(cur, right, level, rbp))) {
1147                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1148                 return error;
1149         }
1150         if (be16_to_cpu(right->bb_numrecs) == XFS_BMAP_BLOCK_IMAXRECS(level, cur)) {
1151                 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1152                 *stat = 0;
1153                 return 0;
1154         }
1155         if (level > 0) {
1156                 lkp = XFS_BMAP_KEY_IADDR(left, be16_to_cpu(left->bb_numrecs), cur);
1157                 lpp = XFS_BMAP_PTR_IADDR(left, be16_to_cpu(left->bb_numrecs), cur);
1158                 rkp = XFS_BMAP_KEY_IADDR(right, 1, cur);
1159                 rpp = XFS_BMAP_PTR_IADDR(right, 1, cur);
1160 #ifdef DEBUG
1161                 for (i = be16_to_cpu(right->bb_numrecs) - 1; i >= 0; i--) {
1162                         if ((error = xfs_btree_check_lptr_disk(cur, rpp[i], level))) {
1163                                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1164                                 return error;
1165                         }
1166                 }
1167 #endif
1168                 memmove(rkp + 1, rkp, be16_to_cpu(right->bb_numrecs) * sizeof(*rkp));
1169                 memmove(rpp + 1, rpp, be16_to_cpu(right->bb_numrecs) * sizeof(*rpp));
1170 #ifdef DEBUG
1171                 if ((error = xfs_btree_check_lptr_disk(cur, *lpp, level))) {
1172                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1173                         return error;
1174                 }
1175 #endif
1176                 *rkp = *lkp;
1177                 *rpp = *lpp;
1178                 xfs_bmbt_log_keys(cur, rbp, 1, be16_to_cpu(right->bb_numrecs) + 1);
1179                 xfs_bmbt_log_ptrs(cur, rbp, 1, be16_to_cpu(right->bb_numrecs) + 1);
1180         } else {
1181                 lrp = XFS_BMAP_REC_IADDR(left, be16_to_cpu(left->bb_numrecs), cur);
1182                 rrp = XFS_BMAP_REC_IADDR(right, 1, cur);
1183                 memmove(rrp + 1, rrp, be16_to_cpu(right->bb_numrecs) * sizeof(*rrp));
1184                 *rrp = *lrp;
1185                 xfs_bmbt_log_recs(cur, rbp, 1, be16_to_cpu(right->bb_numrecs) + 1);
1186                 key.br_startoff = cpu_to_be64(xfs_bmbt_disk_get_startoff(rrp));
1187                 rkp = &key;
1188         }
1189         be16_add_cpu(&left->bb_numrecs, -1);
1190         xfs_bmbt_log_block(cur, lbp, XFS_BB_NUMRECS);
1191         be16_add_cpu(&right->bb_numrecs, 1);
1192 #ifdef DEBUG
1193         if (level > 0)
1194                 xfs_btree_check_key(XFS_BTNUM_BMAP, rkp, rkp + 1);
1195         else
1196                 xfs_btree_check_rec(XFS_BTNUM_BMAP, rrp, rrp + 1);
1197 #endif
1198         xfs_bmbt_log_block(cur, rbp, XFS_BB_NUMRECS);
1199         if ((error = xfs_btree_dup_cursor(cur, &tcur))) {
1200                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1201                 return error;
1202         }
1203         i = xfs_btree_lastrec(tcur, level);
1204         XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1205         if ((error = xfs_bmbt_increment(tcur, level, &i))) {
1206                 XFS_BMBT_TRACE_CURSOR(tcur, ERROR);
1207                 goto error1;
1208         }
1209         XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1210         if ((error = xfs_bmbt_updkey(tcur, rkp, level + 1))) {
1211                 XFS_BMBT_TRACE_CURSOR(tcur, ERROR);
1212                 goto error1;
1213         }
1214         xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
1215         XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1216         *stat = 1;
1217         return 0;
1218 error0:
1219         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1220 error1:
1221         xfs_btree_del_cursor(tcur, XFS_BTREE_ERROR);
1222         return error;
1223 }
1224
1225 /*
1226  * Determine the extent state.
1227  */
1228 /* ARGSUSED */
1229 STATIC xfs_exntst_t
1230 xfs_extent_state(
1231         xfs_filblks_t           blks,
1232         int                     extent_flag)
1233 {
1234         if (extent_flag) {
1235                 ASSERT(blks != 0);      /* saved for DMIG */
1236                 return XFS_EXT_UNWRITTEN;
1237         }
1238         return XFS_EXT_NORM;
1239 }
1240
1241
1242 /*
1243  * Split cur/level block in half.
1244  * Return new block number and its first record (to be inserted into parent).
1245  */
1246 STATIC int                                      /* error */
1247 xfs_bmbt_split(
1248         xfs_btree_cur_t         *cur,
1249         int                     level,
1250         xfs_fsblock_t           *bnop,
1251         __uint64_t              *startoff,
1252         xfs_btree_cur_t         **curp,
1253         int                     *stat)          /* success/failure */
1254 {
1255         xfs_alloc_arg_t         args;           /* block allocation args */
1256         int                     error;          /* error return value */
1257         int                     i;              /* loop counter */
1258         xfs_fsblock_t           lbno;           /* left sibling block number */
1259         xfs_buf_t               *lbp;           /* left buffer pointer */
1260         xfs_bmbt_block_t        *left;          /* left btree block */
1261         xfs_bmbt_key_t          *lkp;           /* left btree key */
1262         xfs_bmbt_ptr_t          *lpp;           /* left address pointer */
1263         xfs_bmbt_rec_t          *lrp;           /* left record pointer */
1264         xfs_buf_t               *rbp;           /* right buffer pointer */
1265         xfs_bmbt_block_t        *right;         /* right btree block */
1266         xfs_bmbt_key_t          *rkp;           /* right btree key */
1267         xfs_bmbt_ptr_t          *rpp;           /* right address pointer */
1268         xfs_bmbt_block_t        *rrblock;       /* right-right btree block */
1269         xfs_buf_t               *rrbp;          /* right-right buffer pointer */
1270         xfs_bmbt_rec_t          *rrp;           /* right record pointer */
1271
1272         XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
1273         // disable until merged into common code
1274 //      XFS_BMBT_TRACE_ARGIFK(cur, level, *bnop, *startoff);
1275         args.tp = cur->bc_tp;
1276         args.mp = cur->bc_mp;
1277         lbp = cur->bc_bufs[level];
1278         lbno = XFS_DADDR_TO_FSB(args.mp, XFS_BUF_ADDR(lbp));
1279         left = XFS_BUF_TO_BMBT_BLOCK(lbp);
1280         args.fsbno = cur->bc_private.b.firstblock;
1281         args.firstblock = args.fsbno;
1282         args.minleft = 0;
1283         if (args.fsbno == NULLFSBLOCK) {
1284                 args.fsbno = lbno;
1285                 args.type = XFS_ALLOCTYPE_START_BNO;
1286                 /*
1287                  * Make sure there is sufficient room left in the AG to
1288                  * complete a full tree split for an extent insert.  If
1289                  * we are converting the middle part of an extent then
1290                  * we may need space for two tree splits.
1291                  *
1292                  * We are relying on the caller to make the correct block
1293                  * reservation for this operation to succeed.  If the
1294                  * reservation amount is insufficient then we may fail a
1295                  * block allocation here and corrupt the filesystem.
1296                  */
1297                 args.minleft = xfs_trans_get_block_res(args.tp);
1298         } else if (cur->bc_private.b.flist->xbf_low)
1299                 args.type = XFS_ALLOCTYPE_START_BNO;
1300         else
1301                 args.type = XFS_ALLOCTYPE_NEAR_BNO;
1302         args.mod = args.alignment = args.total = args.isfl =
1303                 args.userdata = args.minalignslop = 0;
1304         args.minlen = args.maxlen = args.prod = 1;
1305         args.wasdel = cur->bc_private.b.flags & XFS_BTCUR_BPRV_WASDEL;
1306         if (!args.wasdel && xfs_trans_get_block_res(args.tp) == 0) {
1307                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1308                 return XFS_ERROR(ENOSPC);
1309         }
1310         if ((error = xfs_alloc_vextent(&args))) {
1311                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1312                 return error;
1313         }
1314         if (args.fsbno == NULLFSBLOCK && args.minleft) {
1315                 /*
1316                  * Could not find an AG with enough free space to satisfy
1317                  * a full btree split.  Try again without minleft and if
1318                  * successful activate the lowspace algorithm.
1319                  */
1320                 args.fsbno = 0;
1321                 args.type = XFS_ALLOCTYPE_FIRST_AG;
1322                 args.minleft = 0;
1323                 if ((error = xfs_alloc_vextent(&args))) {
1324                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1325                         return error;
1326                 }
1327                 cur->bc_private.b.flist->xbf_low = 1;
1328         }
1329         if (args.fsbno == NULLFSBLOCK) {
1330                 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1331                 *stat = 0;
1332                 return 0;
1333         }
1334         ASSERT(args.len == 1);
1335         cur->bc_private.b.firstblock = args.fsbno;
1336         cur->bc_private.b.allocated++;
1337         cur->bc_private.b.ip->i_d.di_nblocks++;
1338         xfs_trans_log_inode(args.tp, cur->bc_private.b.ip, XFS_ILOG_CORE);
1339         XFS_TRANS_MOD_DQUOT_BYINO(args.mp, args.tp, cur->bc_private.b.ip,
1340                         XFS_TRANS_DQ_BCOUNT, 1L);
1341         rbp = xfs_btree_get_bufl(args.mp, args.tp, args.fsbno, 0);
1342         right = XFS_BUF_TO_BMBT_BLOCK(rbp);
1343 #ifdef DEBUG
1344         if ((error = xfs_btree_check_lblock(cur, left, level, rbp))) {
1345                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1346                 return error;
1347         }
1348 #endif
1349         right->bb_magic = cpu_to_be32(XFS_BMAP_MAGIC);
1350         right->bb_level = left->bb_level;
1351         right->bb_numrecs = cpu_to_be16(be16_to_cpu(left->bb_numrecs) / 2);
1352         if ((be16_to_cpu(left->bb_numrecs) & 1) &&
1353             cur->bc_ptrs[level] <= be16_to_cpu(right->bb_numrecs) + 1)
1354                 be16_add_cpu(&right->bb_numrecs, 1);
1355         i = be16_to_cpu(left->bb_numrecs) - be16_to_cpu(right->bb_numrecs) + 1;
1356         if (level > 0) {
1357                 lkp = XFS_BMAP_KEY_IADDR(left, i, cur);
1358                 lpp = XFS_BMAP_PTR_IADDR(left, i, cur);
1359                 rkp = XFS_BMAP_KEY_IADDR(right, 1, cur);
1360                 rpp = XFS_BMAP_PTR_IADDR(right, 1, cur);
1361 #ifdef DEBUG
1362                 for (i = 0; i < be16_to_cpu(right->bb_numrecs); i++) {
1363                         if ((error = xfs_btree_check_lptr_disk(cur, lpp[i], level))) {
1364                                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1365                                 return error;
1366                         }
1367                 }
1368 #endif
1369                 memcpy(rkp, lkp, be16_to_cpu(right->bb_numrecs) * sizeof(*rkp));
1370                 memcpy(rpp, lpp, be16_to_cpu(right->bb_numrecs) * sizeof(*rpp));
1371                 xfs_bmbt_log_keys(cur, rbp, 1, be16_to_cpu(right->bb_numrecs));
1372                 xfs_bmbt_log_ptrs(cur, rbp, 1, be16_to_cpu(right->bb_numrecs));
1373                 *startoff = be64_to_cpu(rkp->br_startoff);
1374         } else {
1375                 lrp = XFS_BMAP_REC_IADDR(left, i, cur);
1376                 rrp = XFS_BMAP_REC_IADDR(right, 1, cur);
1377                 memcpy(rrp, lrp, be16_to_cpu(right->bb_numrecs) * sizeof(*rrp));
1378                 xfs_bmbt_log_recs(cur, rbp, 1, be16_to_cpu(right->bb_numrecs));
1379                 *startoff = xfs_bmbt_disk_get_startoff(rrp);
1380         }
1381         be16_add_cpu(&left->bb_numrecs, -(be16_to_cpu(right->bb_numrecs)));
1382         right->bb_rightsib = left->bb_rightsib;
1383         left->bb_rightsib = cpu_to_be64(args.fsbno);
1384         right->bb_leftsib = cpu_to_be64(lbno);
1385         xfs_bmbt_log_block(cur, rbp, XFS_BB_ALL_BITS);
1386         xfs_bmbt_log_block(cur, lbp, XFS_BB_NUMRECS | XFS_BB_RIGHTSIB);
1387         if (be64_to_cpu(right->bb_rightsib) != NULLDFSBNO) {
1388                 if ((error = xfs_btree_read_bufl(args.mp, args.tp,
1389                                 be64_to_cpu(right->bb_rightsib), 0, &rrbp,
1390                                 XFS_BMAP_BTREE_REF))) {
1391                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1392                         return error;
1393                 }
1394                 rrblock = XFS_BUF_TO_BMBT_BLOCK(rrbp);
1395                 if ((error = xfs_btree_check_lblock(cur, rrblock, level, rrbp))) {
1396                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1397                         return error;
1398                 }
1399                 rrblock->bb_leftsib = cpu_to_be64(args.fsbno);
1400                 xfs_bmbt_log_block(cur, rrbp, XFS_BB_LEFTSIB);
1401         }
1402         if (cur->bc_ptrs[level] > be16_to_cpu(left->bb_numrecs) + 1) {
1403                 xfs_btree_setbuf(cur, level, rbp);
1404                 cur->bc_ptrs[level] -= be16_to_cpu(left->bb_numrecs);
1405         }
1406         if (level + 1 < cur->bc_nlevels) {
1407                 if ((error = xfs_btree_dup_cursor(cur, curp))) {
1408                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1409                         return error;
1410                 }
1411                 (*curp)->bc_ptrs[level + 1]++;
1412         }
1413         *bnop = args.fsbno;
1414         XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1415         *stat = 1;
1416         return 0;
1417 }
1418
1419
1420 /*
1421  * Update keys for the record.
1422  */
1423 STATIC int
1424 xfs_bmbt_updkey(
1425         xfs_btree_cur_t         *cur,
1426         xfs_bmbt_key_t          *keyp,  /* on-disk format */
1427         int                     level)
1428 {
1429         xfs_bmbt_block_t        *block;
1430         xfs_buf_t               *bp;
1431 #ifdef DEBUG
1432         int                     error;
1433 #endif
1434         xfs_bmbt_key_t          *kp;
1435         int                     ptr;
1436
1437         ASSERT(level >= 1);
1438         XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
1439         XFS_BMBT_TRACE_ARGIK(cur, level, keyp);
1440         for (ptr = 1; ptr == 1 && level < cur->bc_nlevels; level++) {
1441                 block = xfs_bmbt_get_block(cur, level, &bp);
1442 #ifdef DEBUG
1443                 if ((error = xfs_btree_check_lblock(cur, block, level, bp))) {
1444                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1445                         return error;
1446                 }
1447 #endif
1448                 ptr = cur->bc_ptrs[level];
1449                 kp = XFS_BMAP_KEY_IADDR(block, ptr, cur);
1450                 *kp = *keyp;
1451                 xfs_bmbt_log_keys(cur, bp, ptr, ptr);
1452         }
1453         XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1454         return 0;
1455 }
1456
1457 /*
1458  * Convert on-disk form of btree root to in-memory form.
1459  */
1460 void
1461 xfs_bmdr_to_bmbt(
1462         xfs_bmdr_block_t        *dblock,
1463         int                     dblocklen,
1464         xfs_bmbt_block_t        *rblock,
1465         int                     rblocklen)
1466 {
1467         int                     dmxr;
1468         xfs_bmbt_key_t          *fkp;
1469         __be64                  *fpp;
1470         xfs_bmbt_key_t          *tkp;
1471         __be64                  *tpp;
1472
1473         rblock->bb_magic = cpu_to_be32(XFS_BMAP_MAGIC);
1474         rblock->bb_level = dblock->bb_level;
1475         ASSERT(be16_to_cpu(rblock->bb_level) > 0);
1476         rblock->bb_numrecs = dblock->bb_numrecs;
1477         rblock->bb_leftsib = cpu_to_be64(NULLDFSBNO);
1478         rblock->bb_rightsib = cpu_to_be64(NULLDFSBNO);
1479         dmxr = (int)XFS_BTREE_BLOCK_MAXRECS(dblocklen, xfs_bmdr, 0);
1480         fkp = XFS_BTREE_KEY_ADDR(xfs_bmdr, dblock, 1);
1481         tkp = XFS_BMAP_BROOT_KEY_ADDR(rblock, 1, rblocklen);
1482         fpp = XFS_BTREE_PTR_ADDR(xfs_bmdr, dblock, 1, dmxr);
1483         tpp = XFS_BMAP_BROOT_PTR_ADDR(rblock, 1, rblocklen);
1484         dmxr = be16_to_cpu(dblock->bb_numrecs);
1485         memcpy(tkp, fkp, sizeof(*fkp) * dmxr);
1486         memcpy(tpp, fpp, sizeof(*fpp) * dmxr);
1487 }
1488
1489 /*
1490  * Decrement cursor by one record at the level.
1491  * For nonzero levels the leaf-ward information is untouched.
1492  */
1493 int                                             /* error */
1494 xfs_bmbt_decrement(
1495         xfs_btree_cur_t         *cur,
1496         int                     level,
1497         int                     *stat)          /* success/failure */
1498 {
1499         xfs_bmbt_block_t        *block;
1500         xfs_buf_t               *bp;
1501         int                     error;          /* error return value */
1502         xfs_fsblock_t           fsbno;
1503         int                     lev;
1504         xfs_mount_t             *mp;
1505         xfs_trans_t             *tp;
1506
1507         XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
1508         XFS_BMBT_TRACE_ARGI(cur, level);
1509         ASSERT(level < cur->bc_nlevels);
1510
1511         xfs_btree_readahead(cur, level, XFS_BTCUR_LEFTRA);
1512
1513         if (--cur->bc_ptrs[level] > 0) {
1514                 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1515                 *stat = 1;
1516                 return 0;
1517         }
1518         block = xfs_bmbt_get_block(cur, level, &bp);
1519 #ifdef DEBUG
1520         if ((error = xfs_btree_check_lblock(cur, block, level, bp))) {
1521                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1522                 return error;
1523         }
1524 #endif
1525         if (be64_to_cpu(block->bb_leftsib) == NULLDFSBNO) {
1526                 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1527                 *stat = 0;
1528                 return 0;
1529         }
1530         for (lev = level + 1; lev < cur->bc_nlevels; lev++) {
1531                 if (--cur->bc_ptrs[lev] > 0)
1532                         break;
1533                 xfs_btree_readahead(cur, lev, XFS_BTCUR_LEFTRA);
1534         }
1535         if (lev == cur->bc_nlevels) {
1536                 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1537                 *stat = 0;
1538                 return 0;
1539         }
1540         tp = cur->bc_tp;
1541         mp = cur->bc_mp;
1542         for (block = xfs_bmbt_get_block(cur, lev, &bp); lev > level; ) {
1543                 fsbno = be64_to_cpu(*XFS_BMAP_PTR_IADDR(block, cur->bc_ptrs[lev], cur));
1544                 if ((error = xfs_btree_read_bufl(mp, tp, fsbno, 0, &bp,
1545                                 XFS_BMAP_BTREE_REF))) {
1546                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1547                         return error;
1548                 }
1549                 lev--;
1550                 xfs_btree_setbuf(cur, lev, bp);
1551                 block = XFS_BUF_TO_BMBT_BLOCK(bp);
1552                 if ((error = xfs_btree_check_lblock(cur, block, lev, bp))) {
1553                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1554                         return error;
1555                 }
1556                 cur->bc_ptrs[lev] = be16_to_cpu(block->bb_numrecs);
1557         }
1558         XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1559         *stat = 1;
1560         return 0;
1561 }
1562
1563 /*
1564  * Delete the record pointed to by cur.
1565  */
1566 int                                     /* error */
1567 xfs_bmbt_delete(
1568         xfs_btree_cur_t *cur,
1569         int             *stat)          /* success/failure */
1570 {
1571         int             error;          /* error return value */
1572         int             i;
1573         int             level;
1574
1575         XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
1576         for (level = 0, i = 2; i == 2; level++) {
1577                 if ((error = xfs_bmbt_delrec(cur, level, &i))) {
1578                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1579                         return error;
1580                 }
1581         }
1582         if (i == 0) {
1583                 for (level = 1; level < cur->bc_nlevels; level++) {
1584                         if (cur->bc_ptrs[level] == 0) {
1585                                 if ((error = xfs_bmbt_decrement(cur, level,
1586                                                 &i))) {
1587                                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1588                                         return error;
1589                                 }
1590                                 break;
1591                         }
1592                 }
1593         }
1594         XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1595         *stat = i;
1596         return 0;
1597 }
1598
1599 /*
1600  * Convert a compressed bmap extent record to an uncompressed form.
1601  * This code must be in sync with the routines xfs_bmbt_get_startoff,
1602  * xfs_bmbt_get_startblock, xfs_bmbt_get_blockcount and xfs_bmbt_get_state.
1603  */
1604
1605 STATIC_INLINE void
1606 __xfs_bmbt_get_all(
1607                 __uint64_t l0,
1608                 __uint64_t l1,
1609                 xfs_bmbt_irec_t *s)
1610 {
1611         int     ext_flag;
1612         xfs_exntst_t st;
1613
1614         ext_flag = (int)(l0 >> (64 - BMBT_EXNTFLAG_BITLEN));
1615         s->br_startoff = ((xfs_fileoff_t)l0 &
1616                            XFS_MASK64LO(64 - BMBT_EXNTFLAG_BITLEN)) >> 9;
1617 #if XFS_BIG_BLKNOS
1618         s->br_startblock = (((xfs_fsblock_t)l0 & XFS_MASK64LO(9)) << 43) |
1619                            (((xfs_fsblock_t)l1) >> 21);
1620 #else
1621 #ifdef DEBUG
1622         {
1623                 xfs_dfsbno_t    b;
1624
1625                 b = (((xfs_dfsbno_t)l0 & XFS_MASK64LO(9)) << 43) |
1626                     (((xfs_dfsbno_t)l1) >> 21);
1627                 ASSERT((b >> 32) == 0 || ISNULLDSTARTBLOCK(b));
1628                 s->br_startblock = (xfs_fsblock_t)b;
1629         }
1630 #else   /* !DEBUG */
1631         s->br_startblock = (xfs_fsblock_t)(((xfs_dfsbno_t)l1) >> 21);
1632 #endif  /* DEBUG */
1633 #endif  /* XFS_BIG_BLKNOS */
1634         s->br_blockcount = (xfs_filblks_t)(l1 & XFS_MASK64LO(21));
1635         /* This is xfs_extent_state() in-line */
1636         if (ext_flag) {
1637                 ASSERT(s->br_blockcount != 0);  /* saved for DMIG */
1638                 st = XFS_EXT_UNWRITTEN;
1639         } else
1640                 st = XFS_EXT_NORM;
1641         s->br_state = st;
1642 }
1643
1644 void
1645 xfs_bmbt_get_all(
1646         xfs_bmbt_rec_host_t *r,
1647         xfs_bmbt_irec_t *s)
1648 {
1649         __xfs_bmbt_get_all(r->l0, r->l1, s);
1650 }
1651
1652 /*
1653  * Get the block pointer for the given level of the cursor.
1654  * Fill in the buffer pointer, if applicable.
1655  */
1656 xfs_bmbt_block_t *
1657 xfs_bmbt_get_block(
1658         xfs_btree_cur_t         *cur,
1659         int                     level,
1660         xfs_buf_t               **bpp)
1661 {
1662         xfs_ifork_t             *ifp;
1663         xfs_bmbt_block_t        *rval;
1664
1665         if (level < cur->bc_nlevels - 1) {
1666                 *bpp = cur->bc_bufs[level];
1667                 rval = XFS_BUF_TO_BMBT_BLOCK(*bpp);
1668         } else {
1669                 *bpp = NULL;
1670                 ifp = XFS_IFORK_PTR(cur->bc_private.b.ip,
1671                         cur->bc_private.b.whichfork);
1672                 rval = ifp->if_broot;
1673         }
1674         return rval;
1675 }
1676
1677 /*
1678  * Extract the blockcount field from an in memory bmap extent record.
1679  */
1680 xfs_filblks_t
1681 xfs_bmbt_get_blockcount(
1682         xfs_bmbt_rec_host_t     *r)
1683 {
1684         return (xfs_filblks_t)(r->l1 & XFS_MASK64LO(21));
1685 }
1686
1687 /*
1688  * Extract the startblock field from an in memory bmap extent record.
1689  */
1690 xfs_fsblock_t
1691 xfs_bmbt_get_startblock(
1692         xfs_bmbt_rec_host_t     *r)
1693 {
1694 #if XFS_BIG_BLKNOS
1695         return (((xfs_fsblock_t)r->l0 & XFS_MASK64LO(9)) << 43) |
1696                (((xfs_fsblock_t)r->l1) >> 21);
1697 #else
1698 #ifdef DEBUG
1699         xfs_dfsbno_t    b;
1700
1701         b = (((xfs_dfsbno_t)r->l0 & XFS_MASK64LO(9)) << 43) |
1702             (((xfs_dfsbno_t)r->l1) >> 21);
1703         ASSERT((b >> 32) == 0 || ISNULLDSTARTBLOCK(b));
1704         return (xfs_fsblock_t)b;
1705 #else   /* !DEBUG */
1706         return (xfs_fsblock_t)(((xfs_dfsbno_t)r->l1) >> 21);
1707 #endif  /* DEBUG */
1708 #endif  /* XFS_BIG_BLKNOS */
1709 }
1710
1711 /*
1712  * Extract the startoff field from an in memory bmap extent record.
1713  */
1714 xfs_fileoff_t
1715 xfs_bmbt_get_startoff(
1716         xfs_bmbt_rec_host_t     *r)
1717 {
1718         return ((xfs_fileoff_t)r->l0 &
1719                  XFS_MASK64LO(64 - BMBT_EXNTFLAG_BITLEN)) >> 9;
1720 }
1721
1722 xfs_exntst_t
1723 xfs_bmbt_get_state(
1724         xfs_bmbt_rec_host_t     *r)
1725 {
1726         int     ext_flag;
1727
1728         ext_flag = (int)((r->l0) >> (64 - BMBT_EXNTFLAG_BITLEN));
1729         return xfs_extent_state(xfs_bmbt_get_blockcount(r),
1730                                 ext_flag);
1731 }
1732
1733 /* Endian flipping versions of the bmbt extraction functions */
1734 void
1735 xfs_bmbt_disk_get_all(
1736         xfs_bmbt_rec_t  *r,
1737         xfs_bmbt_irec_t *s)
1738 {
1739         __xfs_bmbt_get_all(be64_to_cpu(r->l0), be64_to_cpu(r->l1), s);
1740 }
1741
1742 /*
1743  * Extract the blockcount field from an on disk bmap extent record.
1744  */
1745 xfs_filblks_t
1746 xfs_bmbt_disk_get_blockcount(
1747         xfs_bmbt_rec_t  *r)
1748 {
1749         return (xfs_filblks_t)(be64_to_cpu(r->l1) & XFS_MASK64LO(21));
1750 }
1751
1752 /*
1753  * Extract the startoff field from a disk format bmap extent record.
1754  */
1755 xfs_fileoff_t
1756 xfs_bmbt_disk_get_startoff(
1757         xfs_bmbt_rec_t  *r)
1758 {
1759         return ((xfs_fileoff_t)be64_to_cpu(r->l0) &
1760                  XFS_MASK64LO(64 - BMBT_EXNTFLAG_BITLEN)) >> 9;
1761 }
1762
1763 /*
1764  * Increment cursor by one record at the level.
1765  * For nonzero levels the leaf-ward information is untouched.
1766  */
1767 int                                             /* error */
1768 xfs_bmbt_increment(
1769         xfs_btree_cur_t         *cur,
1770         int                     level,
1771         int                     *stat)          /* success/failure */
1772 {
1773         xfs_bmbt_block_t        *block;
1774         xfs_buf_t               *bp;
1775         int                     error;          /* error return value */
1776         xfs_fsblock_t           fsbno;
1777         int                     lev;
1778         xfs_mount_t             *mp;
1779         xfs_trans_t             *tp;
1780
1781         XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
1782         XFS_BMBT_TRACE_ARGI(cur, level);
1783         ASSERT(level < cur->bc_nlevels);
1784
1785         xfs_btree_readahead(cur, level, XFS_BTCUR_RIGHTRA);
1786         block = xfs_bmbt_get_block(cur, level, &bp);
1787 #ifdef DEBUG
1788         if ((error = xfs_btree_check_lblock(cur, block, level, bp))) {
1789                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1790                 return error;
1791         }
1792 #endif
1793         if (++cur->bc_ptrs[level] <= be16_to_cpu(block->bb_numrecs)) {
1794                 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1795                 *stat = 1;
1796                 return 0;
1797         }
1798         if (be64_to_cpu(block->bb_rightsib) == NULLDFSBNO) {
1799                 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1800                 *stat = 0;
1801                 return 0;
1802         }
1803         for (lev = level + 1; lev < cur->bc_nlevels; lev++) {
1804                 block = xfs_bmbt_get_block(cur, lev, &bp);
1805 #ifdef DEBUG
1806                 if ((error = xfs_btree_check_lblock(cur, block, lev, bp))) {
1807                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1808                         return error;
1809                 }
1810 #endif
1811                 if (++cur->bc_ptrs[lev] <= be16_to_cpu(block->bb_numrecs))
1812                         break;
1813                 xfs_btree_readahead(cur, lev, XFS_BTCUR_RIGHTRA);
1814         }
1815         if (lev == cur->bc_nlevels) {
1816                 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1817                 *stat = 0;
1818                 return 0;
1819         }
1820         tp = cur->bc_tp;
1821         mp = cur->bc_mp;
1822         for (block = xfs_bmbt_get_block(cur, lev, &bp); lev > level; ) {
1823                 fsbno = be64_to_cpu(*XFS_BMAP_PTR_IADDR(block, cur->bc_ptrs[lev], cur));
1824                 if ((error = xfs_btree_read_bufl(mp, tp, fsbno, 0, &bp,
1825                                 XFS_BMAP_BTREE_REF))) {
1826                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1827                         return error;
1828                 }
1829                 lev--;
1830                 xfs_btree_setbuf(cur, lev, bp);
1831                 block = XFS_BUF_TO_BMBT_BLOCK(bp);
1832                 if ((error = xfs_btree_check_lblock(cur, block, lev, bp))) {
1833                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1834                         return error;
1835                 }
1836                 cur->bc_ptrs[lev] = 1;
1837         }
1838         XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1839         *stat = 1;
1840         return 0;
1841 }
1842
1843 /*
1844  * Insert the current record at the point referenced by cur.
1845  *
1846  * A multi-level split of the tree on insert will invalidate the original
1847  * cursor.  All callers of this function should assume that the cursor is
1848  * no longer valid and revalidate it.
1849  */
1850 int                                     /* error */
1851 xfs_bmbt_insert(
1852         xfs_btree_cur_t *cur,
1853         int             *stat)          /* success/failure */
1854 {
1855         int             error;          /* error return value */
1856         int             i;
1857         int             level;
1858         xfs_fsblock_t   nbno;
1859         xfs_btree_cur_t *ncur;
1860         xfs_bmbt_rec_t  nrec;
1861         xfs_btree_cur_t *pcur;
1862
1863         XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
1864         level = 0;
1865         nbno = NULLFSBLOCK;
1866         xfs_bmbt_disk_set_all(&nrec, &cur->bc_rec.b);
1867         ncur = NULL;
1868         pcur = cur;
1869         do {
1870                 if ((error = xfs_bmbt_insrec(pcur, level++, &nbno, &nrec, &ncur,
1871                                 &i))) {
1872                         if (pcur != cur)
1873                                 xfs_btree_del_cursor(pcur, XFS_BTREE_ERROR);
1874                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1875                         return error;
1876                 }
1877                 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1878                 if (pcur != cur && (ncur || nbno == NULLFSBLOCK)) {
1879                         cur->bc_nlevels = pcur->bc_nlevels;
1880                         cur->bc_private.b.allocated +=
1881                                 pcur->bc_private.b.allocated;
1882                         pcur->bc_private.b.allocated = 0;
1883                         ASSERT((cur->bc_private.b.firstblock != NULLFSBLOCK) ||
1884                                XFS_IS_REALTIME_INODE(cur->bc_private.b.ip));
1885                         cur->bc_private.b.firstblock =
1886                                 pcur->bc_private.b.firstblock;
1887                         ASSERT(cur->bc_private.b.flist ==
1888                                pcur->bc_private.b.flist);
1889                         xfs_btree_del_cursor(pcur, XFS_BTREE_NOERROR);
1890                 }
1891                 if (ncur) {
1892                         pcur = ncur;
1893                         ncur = NULL;
1894                 }
1895         } while (nbno != NULLFSBLOCK);
1896         XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1897         *stat = i;
1898         return 0;
1899 error0:
1900         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1901         return error;
1902 }
1903
1904 /*
1905  * Log fields from the btree block header.
1906  */
1907 void
1908 xfs_bmbt_log_block(
1909         xfs_btree_cur_t         *cur,
1910         xfs_buf_t               *bp,
1911         int                     fields)
1912 {
1913         int                     first;
1914         int                     last;
1915         xfs_trans_t             *tp;
1916         static const short      offsets[] = {
1917                 offsetof(xfs_bmbt_block_t, bb_magic),
1918                 offsetof(xfs_bmbt_block_t, bb_level),
1919                 offsetof(xfs_bmbt_block_t, bb_numrecs),
1920                 offsetof(xfs_bmbt_block_t, bb_leftsib),
1921                 offsetof(xfs_bmbt_block_t, bb_rightsib),
1922                 sizeof(xfs_bmbt_block_t)
1923         };
1924
1925         XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
1926         XFS_BMBT_TRACE_ARGBI(cur, bp, fields);
1927         tp = cur->bc_tp;
1928         if (bp) {
1929                 xfs_btree_offsets(fields, offsets, XFS_BB_NUM_BITS, &first,
1930                                   &last);
1931                 xfs_trans_log_buf(tp, bp, first, last);
1932         } else
1933                 xfs_trans_log_inode(tp, cur->bc_private.b.ip,
1934                         XFS_ILOG_FBROOT(cur->bc_private.b.whichfork));
1935         XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1936 }
1937
1938 /*
1939  * Log record values from the btree block.
1940  */
1941 void
1942 xfs_bmbt_log_recs(
1943         xfs_btree_cur_t         *cur,
1944         xfs_buf_t               *bp,
1945         int                     rfirst,
1946         int                     rlast)
1947 {
1948         xfs_bmbt_block_t        *block;
1949         int                     first;
1950         int                     last;
1951         xfs_bmbt_rec_t          *rp;
1952         xfs_trans_t             *tp;
1953
1954         XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
1955         XFS_BMBT_TRACE_ARGBII(cur, bp, rfirst, rlast);
1956         ASSERT(bp);
1957         tp = cur->bc_tp;
1958         block = XFS_BUF_TO_BMBT_BLOCK(bp);
1959         rp = XFS_BMAP_REC_DADDR(block, 1, cur);
1960         first = (int)((xfs_caddr_t)&rp[rfirst - 1] - (xfs_caddr_t)block);
1961         last = (int)(((xfs_caddr_t)&rp[rlast] - 1) - (xfs_caddr_t)block);
1962         xfs_trans_log_buf(tp, bp, first, last);
1963         XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1964 }
1965
1966 int                                     /* error */
1967 xfs_bmbt_lookup_eq(
1968         xfs_btree_cur_t *cur,
1969         xfs_fileoff_t   off,
1970         xfs_fsblock_t   bno,
1971         xfs_filblks_t   len,
1972         int             *stat)          /* success/failure */
1973 {
1974         cur->bc_rec.b.br_startoff = off;
1975         cur->bc_rec.b.br_startblock = bno;
1976         cur->bc_rec.b.br_blockcount = len;
1977         return xfs_bmbt_lookup(cur, XFS_LOOKUP_EQ, stat);
1978 }
1979
1980 int                                     /* error */
1981 xfs_bmbt_lookup_ge(
1982         xfs_btree_cur_t *cur,
1983         xfs_fileoff_t   off,
1984         xfs_fsblock_t   bno,
1985         xfs_filblks_t   len,
1986         int             *stat)          /* success/failure */
1987 {
1988         cur->bc_rec.b.br_startoff = off;
1989         cur->bc_rec.b.br_startblock = bno;
1990         cur->bc_rec.b.br_blockcount = len;
1991         return xfs_bmbt_lookup(cur, XFS_LOOKUP_GE, stat);
1992 }
1993
1994 /*
1995  * Give the bmap btree a new root block.  Copy the old broot contents
1996  * down into a real block and make the broot point to it.
1997  */
1998 int                                             /* error */
1999 xfs_bmbt_newroot(
2000         xfs_btree_cur_t         *cur,           /* btree cursor */
2001         int                     *logflags,      /* logging flags for inode */
2002         int                     *stat)          /* return status - 0 fail */
2003 {
2004         xfs_alloc_arg_t         args;           /* allocation arguments */
2005         xfs_bmbt_block_t        *block;         /* bmap btree block */
2006         xfs_buf_t               *bp;            /* buffer for block */
2007         xfs_bmbt_block_t        *cblock;        /* child btree block */
2008         xfs_bmbt_key_t          *ckp;           /* child key pointer */
2009         xfs_bmbt_ptr_t          *cpp;           /* child ptr pointer */
2010         int                     error;          /* error return code */
2011 #ifdef DEBUG
2012         int                     i;              /* loop counter */
2013 #endif
2014         xfs_bmbt_key_t          *kp;            /* pointer to bmap btree key */
2015         int                     level;          /* btree level */
2016         xfs_bmbt_ptr_t          *pp;            /* pointer to bmap block addr */
2017
2018         XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
2019         level = cur->bc_nlevels - 1;
2020         block = xfs_bmbt_get_block(cur, level, &bp);
2021         /*
2022          * Copy the root into a real block.
2023          */
2024         args.mp = cur->bc_mp;
2025         pp = XFS_BMAP_PTR_IADDR(block, 1, cur);
2026         args.tp = cur->bc_tp;
2027         args.fsbno = cur->bc_private.b.firstblock;
2028         args.mod = args.minleft = args.alignment = args.total = args.isfl =
2029                 args.userdata = args.minalignslop = 0;
2030         args.minlen = args.maxlen = args.prod = 1;
2031         args.wasdel = cur->bc_private.b.flags & XFS_BTCUR_BPRV_WASDEL;
2032         args.firstblock = args.fsbno;
2033         if (args.fsbno == NULLFSBLOCK) {
2034 #ifdef DEBUG
2035                 if ((error = xfs_btree_check_lptr_disk(cur, *pp, level))) {
2036                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
2037                         return error;
2038                 }
2039 #endif
2040                 args.fsbno = be64_to_cpu(*pp);
2041                 args.type = XFS_ALLOCTYPE_START_BNO;
2042         } else if (cur->bc_private.b.flist->xbf_low)
2043                 args.type = XFS_ALLOCTYPE_START_BNO;
2044         else
2045                 args.type = XFS_ALLOCTYPE_NEAR_BNO;
2046         if ((error = xfs_alloc_vextent(&args))) {
2047                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
2048                 return error;
2049         }
2050         if (args.fsbno == NULLFSBLOCK) {
2051                 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
2052                 *stat = 0;
2053                 return 0;
2054         }
2055         ASSERT(args.len == 1);
2056         cur->bc_private.b.firstblock = args.fsbno;
2057         cur->bc_private.b.allocated++;
2058         cur->bc_private.b.ip->i_d.di_nblocks++;
2059         XFS_TRANS_MOD_DQUOT_BYINO(args.mp, args.tp, cur->bc_private.b.ip,
2060                           XFS_TRANS_DQ_BCOUNT, 1L);
2061         bp = xfs_btree_get_bufl(args.mp, cur->bc_tp, args.fsbno, 0);
2062         cblock = XFS_BUF_TO_BMBT_BLOCK(bp);
2063         *cblock = *block;
2064         be16_add_cpu(&block->bb_level, 1);
2065         block->bb_numrecs = cpu_to_be16(1);
2066         cur->bc_nlevels++;
2067         cur->bc_ptrs[level + 1] = 1;
2068         kp = XFS_BMAP_KEY_IADDR(block, 1, cur);
2069         ckp = XFS_BMAP_KEY_IADDR(cblock, 1, cur);
2070         memcpy(ckp, kp, be16_to_cpu(cblock->bb_numrecs) * sizeof(*kp));
2071         cpp = XFS_BMAP_PTR_IADDR(cblock, 1, cur);
2072 #ifdef DEBUG
2073         for (i = 0; i < be16_to_cpu(cblock->bb_numrecs); i++) {
2074                 if ((error = xfs_btree_check_lptr_disk(cur, pp[i], level))) {
2075                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
2076                         return error;
2077                 }
2078         }
2079 #endif
2080         memcpy(cpp, pp, be16_to_cpu(cblock->bb_numrecs) * sizeof(*pp));
2081 #ifdef DEBUG
2082         if ((error = xfs_btree_check_lptr(cur, args.fsbno, level))) {
2083                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
2084                 return error;
2085         }
2086 #endif
2087         *pp = cpu_to_be64(args.fsbno);
2088         xfs_iroot_realloc(cur->bc_private.b.ip, 1 - be16_to_cpu(cblock->bb_numrecs),
2089                 cur->bc_private.b.whichfork);
2090         xfs_btree_setbuf(cur, level, bp);
2091         /*
2092          * Do all this logging at the end so that
2093          * the root is at the right level.
2094          */
2095         xfs_bmbt_log_block(cur, bp, XFS_BB_ALL_BITS);
2096         xfs_bmbt_log_keys(cur, bp, 1, be16_to_cpu(cblock->bb_numrecs));
2097         xfs_bmbt_log_ptrs(cur, bp, 1, be16_to_cpu(cblock->bb_numrecs));
2098         XFS_BMBT_TRACE_CURSOR(cur, EXIT);
2099         *logflags |=
2100                 XFS_ILOG_CORE | XFS_ILOG_FBROOT(cur->bc_private.b.whichfork);
2101         *stat = 1;
2102         return 0;
2103 }
2104
2105 /*
2106  * Set all the fields in a bmap extent record from the arguments.
2107  */
2108 void
2109 xfs_bmbt_set_allf(
2110         xfs_bmbt_rec_host_t     *r,
2111         xfs_fileoff_t           startoff,
2112         xfs_fsblock_t           startblock,
2113         xfs_filblks_t           blockcount,
2114         xfs_exntst_t            state)
2115 {
2116         int             extent_flag = (state == XFS_EXT_NORM) ? 0 : 1;
2117
2118         ASSERT(state == XFS_EXT_NORM || state == XFS_EXT_UNWRITTEN);
2119         ASSERT((startoff & XFS_MASK64HI(64-BMBT_STARTOFF_BITLEN)) == 0);
2120         ASSERT((blockcount & XFS_MASK64HI(64-BMBT_BLOCKCOUNT_BITLEN)) == 0);
2121
2122 #if XFS_BIG_BLKNOS
2123         ASSERT((startblock & XFS_MASK64HI(64-BMBT_STARTBLOCK_BITLEN)) == 0);
2124
2125         r->l0 = ((xfs_bmbt_rec_base_t)extent_flag << 63) |
2126                 ((xfs_bmbt_rec_base_t)startoff << 9) |
2127                 ((xfs_bmbt_rec_base_t)startblock >> 43);
2128         r->l1 = ((xfs_bmbt_rec_base_t)startblock << 21) |
2129                 ((xfs_bmbt_rec_base_t)blockcount &
2130                 (xfs_bmbt_rec_base_t)XFS_MASK64LO(21));
2131 #else   /* !XFS_BIG_BLKNOS */
2132         if (ISNULLSTARTBLOCK(startblock)) {
2133                 r->l0 = ((xfs_bmbt_rec_base_t)extent_flag << 63) |
2134                         ((xfs_bmbt_rec_base_t)startoff << 9) |
2135                          (xfs_bmbt_rec_base_t)XFS_MASK64LO(9);
2136                 r->l1 = XFS_MASK64HI(11) |
2137                           ((xfs_bmbt_rec_base_t)startblock << 21) |
2138                           ((xfs_bmbt_rec_base_t)blockcount &
2139                            (xfs_bmbt_rec_base_t)XFS_MASK64LO(21));
2140         } else {
2141                 r->l0 = ((xfs_bmbt_rec_base_t)extent_flag << 63) |
2142                         ((xfs_bmbt_rec_base_t)startoff << 9);
2143                 r->l1 = ((xfs_bmbt_rec_base_t)startblock << 21) |
2144                          ((xfs_bmbt_rec_base_t)blockcount &
2145                          (xfs_bmbt_rec_base_t)XFS_MASK64LO(21));
2146         }
2147 #endif  /* XFS_BIG_BLKNOS */
2148 }
2149
2150 /*
2151  * Set all the fields in a bmap extent record from the uncompressed form.
2152  */
2153 void
2154 xfs_bmbt_set_all(
2155         xfs_bmbt_rec_host_t *r,
2156         xfs_bmbt_irec_t *s)
2157 {
2158         xfs_bmbt_set_allf(r, s->br_startoff, s->br_startblock,
2159                              s->br_blockcount, s->br_state);
2160 }
2161
2162
2163 /*
2164  * Set all the fields in a disk format bmap extent record from the arguments.
2165  */
2166 void
2167 xfs_bmbt_disk_set_allf(
2168         xfs_bmbt_rec_t          *r,
2169         xfs_fileoff_t           startoff,
2170         xfs_fsblock_t           startblock,
2171         xfs_filblks_t           blockcount,
2172         xfs_exntst_t            state)
2173 {
2174         int                     extent_flag = (state == XFS_EXT_NORM) ? 0 : 1;
2175
2176         ASSERT(state == XFS_EXT_NORM || state == XFS_EXT_UNWRITTEN);
2177         ASSERT((startoff & XFS_MASK64HI(64-BMBT_STARTOFF_BITLEN)) == 0);
2178         ASSERT((blockcount & XFS_MASK64HI(64-BMBT_BLOCKCOUNT_BITLEN)) == 0);
2179
2180 #if XFS_BIG_BLKNOS
2181         ASSERT((startblock & XFS_MASK64HI(64-BMBT_STARTBLOCK_BITLEN)) == 0);
2182
2183         r->l0 = cpu_to_be64(
2184                 ((xfs_bmbt_rec_base_t)extent_flag << 63) |
2185                  ((xfs_bmbt_rec_base_t)startoff << 9) |
2186                  ((xfs_bmbt_rec_base_t)startblock >> 43));
2187         r->l1 = cpu_to_be64(
2188                 ((xfs_bmbt_rec_base_t)startblock << 21) |
2189                  ((xfs_bmbt_rec_base_t)blockcount &
2190                   (xfs_bmbt_rec_base_t)XFS_MASK64LO(21)));
2191 #else   /* !XFS_BIG_BLKNOS */
2192         if (ISNULLSTARTBLOCK(startblock)) {
2193                 r->l0 = cpu_to_be64(
2194                         ((xfs_bmbt_rec_base_t)extent_flag << 63) |
2195                          ((xfs_bmbt_rec_base_t)startoff << 9) |
2196                           (xfs_bmbt_rec_base_t)XFS_MASK64LO(9));
2197                 r->l1 = cpu_to_be64(XFS_MASK64HI(11) |
2198                           ((xfs_bmbt_rec_base_t)startblock << 21) |
2199                           ((xfs_bmbt_rec_base_t)blockcount &
2200                            (xfs_bmbt_rec_base_t)XFS_MASK64LO(21)));
2201         } else {
2202                 r->l0 = cpu_to_be64(
2203                         ((xfs_bmbt_rec_base_t)extent_flag << 63) |
2204                          ((xfs_bmbt_rec_base_t)startoff << 9));
2205                 r->l1 = cpu_to_be64(
2206                         ((xfs_bmbt_rec_base_t)startblock << 21) |
2207                          ((xfs_bmbt_rec_base_t)blockcount &
2208                           (xfs_bmbt_rec_base_t)XFS_MASK64LO(21)));
2209         }
2210 #endif  /* XFS_BIG_BLKNOS */
2211 }
2212
2213 /*
2214  * Set all the fields in a bmap extent record from the uncompressed form.
2215  */
2216 void
2217 xfs_bmbt_disk_set_all(
2218         xfs_bmbt_rec_t  *r,
2219         xfs_bmbt_irec_t *s)
2220 {
2221         xfs_bmbt_disk_set_allf(r, s->br_startoff, s->br_startblock,
2222                                   s->br_blockcount, s->br_state);
2223 }
2224
2225 /*
2226  * Set the blockcount field in a bmap extent record.
2227  */
2228 void
2229 xfs_bmbt_set_blockcount(
2230         xfs_bmbt_rec_host_t *r,
2231         xfs_filblks_t   v)
2232 {
2233         ASSERT((v & XFS_MASK64HI(43)) == 0);
2234         r->l1 = (r->l1 & (xfs_bmbt_rec_base_t)XFS_MASK64HI(43)) |
2235                   (xfs_bmbt_rec_base_t)(v & XFS_MASK64LO(21));
2236 }
2237
2238 /*
2239  * Set the startblock field in a bmap extent record.
2240  */
2241 void
2242 xfs_bmbt_set_startblock(
2243         xfs_bmbt_rec_host_t *r,
2244         xfs_fsblock_t   v)
2245 {
2246 #if XFS_BIG_BLKNOS
2247         ASSERT((v & XFS_MASK64HI(12)) == 0);
2248         r->l0 = (r->l0 & (xfs_bmbt_rec_base_t)XFS_MASK64HI(55)) |
2249                   (xfs_bmbt_rec_base_t)(v >> 43);
2250         r->l1 = (r->l1 & (xfs_bmbt_rec_base_t)XFS_MASK64LO(21)) |
2251                   (xfs_bmbt_rec_base_t)(v << 21);
2252 #else   /* !XFS_BIG_BLKNOS */
2253         if (ISNULLSTARTBLOCK(v)) {
2254                 r->l0 |= (xfs_bmbt_rec_base_t)XFS_MASK64LO(9);
2255                 r->l1 = (xfs_bmbt_rec_base_t)XFS_MASK64HI(11) |
2256                           ((xfs_bmbt_rec_base_t)v << 21) |
2257                           (r->l1 & (xfs_bmbt_rec_base_t)XFS_MASK64LO(21));
2258         } else {
2259                 r->l0 &= ~(xfs_bmbt_rec_base_t)XFS_MASK64LO(9);
2260                 r->l1 = ((xfs_bmbt_rec_base_t)v << 21) |
2261                           (r->l1 & (xfs_bmbt_rec_base_t)XFS_MASK64LO(21));
2262         }
2263 #endif  /* XFS_BIG_BLKNOS */
2264 }
2265
2266 /*
2267  * Set the startoff field in a bmap extent record.
2268  */
2269 void
2270 xfs_bmbt_set_startoff(
2271         xfs_bmbt_rec_host_t *r,
2272         xfs_fileoff_t   v)
2273 {
2274         ASSERT((v & XFS_MASK64HI(9)) == 0);
2275         r->l0 = (r->l0 & (xfs_bmbt_rec_base_t) XFS_MASK64HI(1)) |
2276                 ((xfs_bmbt_rec_base_t)v << 9) |
2277                   (r->l0 & (xfs_bmbt_rec_base_t)XFS_MASK64LO(9));
2278 }
2279
2280 /*
2281  * Set the extent state field in a bmap extent record.
2282  */
2283 void
2284 xfs_bmbt_set_state(
2285         xfs_bmbt_rec_host_t *r,
2286         xfs_exntst_t    v)
2287 {
2288         ASSERT(v == XFS_EXT_NORM || v == XFS_EXT_UNWRITTEN);
2289         if (v == XFS_EXT_NORM)
2290                 r->l0 &= XFS_MASK64LO(64 - BMBT_EXNTFLAG_BITLEN);
2291         else
2292                 r->l0 |= XFS_MASK64HI(BMBT_EXNTFLAG_BITLEN);
2293 }
2294
2295 /*
2296  * Convert in-memory form of btree root to on-disk form.
2297  */
2298 void
2299 xfs_bmbt_to_bmdr(
2300         xfs_bmbt_block_t        *rblock,
2301         int                     rblocklen,
2302         xfs_bmdr_block_t        *dblock,
2303         int                     dblocklen)
2304 {
2305         int                     dmxr;
2306         xfs_bmbt_key_t          *fkp;
2307         __be64                  *fpp;
2308         xfs_bmbt_key_t          *tkp;
2309         __be64                  *tpp;
2310
2311         ASSERT(be32_to_cpu(rblock->bb_magic) == XFS_BMAP_MAGIC);
2312         ASSERT(be64_to_cpu(rblock->bb_leftsib) == NULLDFSBNO);
2313         ASSERT(be64_to_cpu(rblock->bb_rightsib) == NULLDFSBNO);
2314         ASSERT(be16_to_cpu(rblock->bb_level) > 0);
2315         dblock->bb_level = rblock->bb_level;
2316         dblock->bb_numrecs = rblock->bb_numrecs;
2317         dmxr = (int)XFS_BTREE_BLOCK_MAXRECS(dblocklen, xfs_bmdr, 0);
2318         fkp = XFS_BMAP_BROOT_KEY_ADDR(rblock, 1, rblocklen);
2319         tkp = XFS_BTREE_KEY_ADDR(xfs_bmdr, dblock, 1);
2320         fpp = XFS_BMAP_BROOT_PTR_ADDR(rblock, 1, rblocklen);
2321         tpp = XFS_BTREE_PTR_ADDR(xfs_bmdr, dblock, 1, dmxr);
2322         dmxr = be16_to_cpu(dblock->bb_numrecs);
2323         memcpy(tkp, fkp, sizeof(*fkp) * dmxr);
2324         memcpy(tpp, fpp, sizeof(*fpp) * dmxr);
2325 }
2326
2327 /*
2328  * Update the record to the passed values.
2329  */
2330 int
2331 xfs_bmbt_update(
2332         xfs_btree_cur_t         *cur,
2333         xfs_fileoff_t           off,
2334         xfs_fsblock_t           bno,
2335         xfs_filblks_t           len,
2336         xfs_exntst_t            state)
2337 {
2338         xfs_bmbt_block_t        *block;
2339         xfs_buf_t               *bp;
2340         int                     error;
2341         xfs_bmbt_key_t          key;
2342         int                     ptr;
2343         xfs_bmbt_rec_t          *rp;
2344
2345         XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
2346         XFS_BMBT_TRACE_ARGFFFI(cur, (xfs_dfiloff_t)off, (xfs_dfsbno_t)bno,
2347                 (xfs_dfilblks_t)len, (int)state);
2348         block = xfs_bmbt_get_block(cur, 0, &bp);
2349 #ifdef DEBUG
2350         if ((error = xfs_btree_check_lblock(cur, block, 0, bp))) {
2351                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
2352                 return error;
2353         }
2354 #endif
2355         ptr = cur->bc_ptrs[0];
2356         rp = XFS_BMAP_REC_IADDR(block, ptr, cur);
2357         xfs_bmbt_disk_set_allf(rp, off, bno, len, state);
2358         xfs_bmbt_log_recs(cur, bp, ptr, ptr);
2359         if (ptr > 1) {
2360                 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
2361                 return 0;
2362         }
2363         key.br_startoff = cpu_to_be64(off);
2364         if ((error = xfs_bmbt_updkey(cur, &key, 1))) {
2365                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
2366                 return error;
2367         }
2368         XFS_BMBT_TRACE_CURSOR(cur, EXIT);
2369         return 0;
2370 }
2371
2372 /*
2373  * Check extent records, which have just been read, for
2374  * any bit in the extent flag field. ASSERT on debug
2375  * kernels, as this condition should not occur.
2376  * Return an error condition (1) if any flags found,
2377  * otherwise return 0.
2378  */
2379
2380 int
2381 xfs_check_nostate_extents(
2382         xfs_ifork_t             *ifp,
2383         xfs_extnum_t            idx,
2384         xfs_extnum_t            num)
2385 {
2386         for (; num > 0; num--, idx++) {
2387                 xfs_bmbt_rec_host_t *ep = xfs_iext_get_ext(ifp, idx);
2388                 if ((ep->l0 >>
2389                      (64 - BMBT_EXNTFLAG_BITLEN)) != 0) {
2390                         ASSERT(0);
2391                         return 1;
2392                 }
2393         }
2394         return 0;
2395 }
2396
2397
2398 STATIC struct xfs_btree_cur *
2399 xfs_bmbt_dup_cursor(
2400         struct xfs_btree_cur    *cur)
2401 {
2402         struct xfs_btree_cur    *new;
2403
2404         new = xfs_bmbt_init_cursor(cur->bc_mp, cur->bc_tp,
2405                         cur->bc_private.b.ip, cur->bc_private.b.whichfork);
2406
2407         /*
2408          * Copy the firstblock, flist, and flags values,
2409          * since init cursor doesn't get them.
2410          */
2411         new->bc_private.b.firstblock = cur->bc_private.b.firstblock;
2412         new->bc_private.b.flist = cur->bc_private.b.flist;
2413         new->bc_private.b.flags = cur->bc_private.b.flags;
2414
2415         return new;
2416 }
2417
2418 STATIC int
2419 xfs_bmbt_get_maxrecs(
2420         struct xfs_btree_cur    *cur,
2421         int                     level)
2422 {
2423         return XFS_BMAP_BLOCK_IMAXRECS(level, cur);
2424 }
2425
2426 #ifdef XFS_BTREE_TRACE
2427 ktrace_t        *xfs_bmbt_trace_buf;
2428
2429 STATIC void
2430 xfs_bmbt_trace_enter(
2431         struct xfs_btree_cur    *cur,
2432         const char              *func,
2433         char                    *s,
2434         int                     type,
2435         int                     line,
2436         __psunsigned_t          a0,
2437         __psunsigned_t          a1,
2438         __psunsigned_t          a2,
2439         __psunsigned_t          a3,
2440         __psunsigned_t          a4,
2441         __psunsigned_t          a5,
2442         __psunsigned_t          a6,
2443         __psunsigned_t          a7,
2444         __psunsigned_t          a8,
2445         __psunsigned_t          a9,
2446         __psunsigned_t          a10)
2447 {
2448         struct xfs_inode        *ip = cur->bc_private.b.ip;
2449         int                     whichfork = cur->bc_private.b.whichfork;
2450
2451         ktrace_enter(xfs_bmbt_trace_buf,
2452                 (void *)((__psint_t)type | (whichfork << 8) | (line << 16)),
2453                 (void *)func, (void *)s, (void *)ip, (void *)cur,
2454                 (void *)a0, (void *)a1, (void *)a2, (void *)a3,
2455                 (void *)a4, (void *)a5, (void *)a6, (void *)a7,
2456                 (void *)a8, (void *)a9, (void *)a10);
2457         ktrace_enter(ip->i_btrace,
2458                 (void *)((__psint_t)type | (whichfork << 8) | (line << 16)),
2459                 (void *)func, (void *)s, (void *)ip, (void *)cur,
2460                 (void *)a0, (void *)a1, (void *)a2, (void *)a3,
2461                 (void *)a4, (void *)a5, (void *)a6, (void *)a7,
2462                 (void *)a8, (void *)a9, (void *)a10);
2463 }
2464
2465 STATIC void
2466 xfs_bmbt_trace_cursor(
2467         struct xfs_btree_cur    *cur,
2468         __uint32_t              *s0,
2469         __uint64_t              *l0,
2470         __uint64_t              *l1)
2471 {
2472         struct xfs_bmbt_rec_host r;
2473
2474         xfs_bmbt_set_all(&r, &cur->bc_rec.b);
2475
2476         *s0 = (cur->bc_nlevels << 24) |
2477               (cur->bc_private.b.flags << 16) |
2478                cur->bc_private.b.allocated;
2479         *l0 = r.l0;
2480         *l1 = r.l1;
2481 }
2482
2483 STATIC void
2484 xfs_bmbt_trace_key(
2485         struct xfs_btree_cur    *cur,
2486         union xfs_btree_key     *key,
2487         __uint64_t              *l0,
2488         __uint64_t              *l1)
2489 {
2490         *l0 = be64_to_cpu(key->bmbt.br_startoff);
2491         *l1 = 0;
2492 }
2493
2494 STATIC void
2495 xfs_bmbt_trace_record(
2496         struct xfs_btree_cur    *cur,
2497         union xfs_btree_rec     *rec,
2498         __uint64_t              *l0,
2499         __uint64_t              *l1,
2500         __uint64_t              *l2)
2501 {
2502         struct xfs_bmbt_irec    irec;
2503
2504         xfs_bmbt_disk_get_all(&rec->bmbt, &irec);
2505         *l0 = irec.br_startoff;
2506         *l1 = irec.br_startblock;
2507         *l2 = irec.br_blockcount;
2508 }
2509 #endif /* XFS_BTREE_TRACE */
2510
2511 static const struct xfs_btree_ops xfs_bmbt_ops = {
2512         .dup_cursor             = xfs_bmbt_dup_cursor,
2513         .get_maxrecs            = xfs_bmbt_get_maxrecs,
2514
2515 #ifdef XFS_BTREE_TRACE
2516         .trace_enter            = xfs_bmbt_trace_enter,
2517         .trace_cursor           = xfs_bmbt_trace_cursor,
2518         .trace_key              = xfs_bmbt_trace_key,
2519         .trace_record           = xfs_bmbt_trace_record,
2520 #endif
2521 };
2522
2523 /*
2524  * Allocate a new bmap btree cursor.
2525  */
2526 struct xfs_btree_cur *                          /* new bmap btree cursor */
2527 xfs_bmbt_init_cursor(
2528         struct xfs_mount        *mp,            /* file system mount point */
2529         struct xfs_trans        *tp,            /* transaction pointer */
2530         struct xfs_inode        *ip,            /* inode owning the btree */
2531         int                     whichfork)      /* data or attr fork */
2532 {
2533         struct xfs_ifork        *ifp = XFS_IFORK_PTR(ip, whichfork);
2534         struct xfs_btree_cur    *cur;
2535
2536         cur = kmem_zone_zalloc(xfs_btree_cur_zone, KM_SLEEP);
2537
2538         cur->bc_tp = tp;
2539         cur->bc_mp = mp;
2540         cur->bc_nlevels = be16_to_cpu(ifp->if_broot->bb_level) + 1;
2541         cur->bc_btnum = XFS_BTNUM_BMAP;
2542         cur->bc_blocklog = mp->m_sb.sb_blocklog;
2543
2544         cur->bc_ops = &xfs_bmbt_ops;
2545         cur->bc_flags = XFS_BTREE_LONG_PTRS | XFS_BTREE_ROOT_IN_INODE;
2546
2547         cur->bc_private.b.forksize = XFS_IFORK_SIZE(ip, whichfork);
2548         cur->bc_private.b.ip = ip;
2549         cur->bc_private.b.firstblock = NULLFSBLOCK;
2550         cur->bc_private.b.flist = NULL;
2551         cur->bc_private.b.allocated = 0;
2552         cur->bc_private.b.flags = 0;
2553         cur->bc_private.b.whichfork = whichfork;
2554
2555         return cur;
2556 }