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