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