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
  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 STATIC int
 460 xfs_bmbt_killroot(
 461         xfs_btree_cur_t         *cur)
 462 {
 463         xfs_bmbt_block_t        *block;
 464         xfs_bmbt_block_t        *cblock;
 465         xfs_buf_t               *cbp;
 466         xfs_bmbt_key_t          *ckp;
 467         xfs_bmbt_ptr_t          *cpp;
 468 #ifdef DEBUG
 469         int                     error;
 470 #endif
 471         int                     i;
 472         xfs_bmbt_key_t          *kp;
 473         xfs_inode_t             *ip;
 474         xfs_ifork_t             *ifp;
 475         int                     level;
 476         xfs_bmbt_ptr_t          *pp;
 477
 478         XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
 479         level = cur->bc_nlevels - 1;
 480         ASSERT(level >= 1);
 481         /*
 482          * Don't deal with the root block needs to be a leaf case.
 483          * We're just going to turn the thing back into extents anyway.
 484          */
 485         if (level == 1) {
 486                 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
 487                 return 0;
 488         }
 489         block = xfs_bmbt_get_block(cur, level, &cbp);
 490         /*
 491          * Give up if the root has multiple children.
 492          */
 493         if (be16_to_cpu(block->bb_numrecs) != 1) {
 494                 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
 495                 return 0;
 496         }
 497         /*
 498          * Only do this if the next level will fit.
 499          * Then the data must be copied up to the inode,
 500          * instead of freeing the root you free the next level.
 501          */
 502         cbp = cur->bc_bufs[level - 1];
 503         cblock = XFS_BUF_TO_BMBT_BLOCK(cbp);
 504         if (be16_to_cpu(cblock->bb_numrecs) > XFS_BMAP_BLOCK_DMAXRECS(level, cur)) {
 505                 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
 506                 return 0;
 507         }
 508         ASSERT(be64_to_cpu(cblock->bb_leftsib) == NULLDFSBNO);
 509         ASSERT(be64_to_cpu(cblock->bb_rightsib) == NULLDFSBNO);
 510         ip = cur->bc_private.b.ip;
 511         ifp = XFS_IFORK_PTR(ip, cur->bc_private.b.whichfork);
 512         ASSERT(XFS_BMAP_BLOCK_IMAXRECS(level, cur) ==
 513                XFS_BMAP_BROOT_MAXRECS(ifp->if_broot_bytes));
 514         i = (int)(be16_to_cpu(cblock->bb_numrecs) - XFS_BMAP_BLOCK_IMAXRECS(level, cur));
 515         if (i) {
 516                 xfs_iroot_realloc(ip, i, cur->bc_private.b.whichfork);
 517                 block = ifp->if_broot;
 518         }
 519         be16_add_cpu(&block->bb_numrecs, i);
 520         ASSERT(block->bb_numrecs == cblock->bb_numrecs);
 521         kp = XFS_BMAP_KEY_IADDR(block, 1, cur);
 522         ckp = XFS_BMAP_KEY_IADDR(cblock, 1, cur);
 523         memcpy(kp, ckp, be16_to_cpu(block->bb_numrecs) * sizeof(*kp));
 524         pp = XFS_BMAP_PTR_IADDR(block, 1, cur);
 525         cpp = XFS_BMAP_PTR_IADDR(cblock, 1, cur);
 526 #ifdef DEBUG
 527         for (i = 0; i < be16_to_cpu(cblock->bb_numrecs); i++) {
 528                 if ((error = xfs_btree_check_lptr_disk(cur, cpp[i], level - 1))) {
 529                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
 530                         return error;
 531                 }
 532         }
 533 #endif
 534         memcpy(pp, cpp, be16_to_cpu(block->bb_numrecs) * sizeof(*pp));
 535         xfs_bmap_add_free(XFS_DADDR_TO_FSB(cur->bc_mp, XFS_BUF_ADDR(cbp)), 1,
 536                         cur->bc_private.b.flist, cur->bc_mp);
 537         ip->i_d.di_nblocks--;
 538         XFS_TRANS_MOD_DQUOT_BYINO(cur->bc_mp, cur->bc_tp, ip,
 539                         XFS_TRANS_DQ_BCOUNT, -1L);
 540         xfs_trans_binval(cur->bc_tp, cbp);
 541         cur->bc_bufs[level - 1] = NULL;
 542         be16_add_cpu(&block->bb_level, -1);
 543         xfs_trans_log_inode(cur->bc_tp, ip,
 544                 XFS_ILOG_CORE | XFS_ILOG_FBROOT(cur->bc_private.b.whichfork));
 545         cur->bc_nlevels--;
 546         XFS_BMBT_TRACE_CURSOR(cur, EXIT);
 547         return 0;
 548 }
 549
 550 /*
 551  * Log key values from the btree block.
 552  */
 553 STATIC void
 554 xfs_bmbt_log_keys(
 555         xfs_btree_cur_t *cur,
 556         xfs_buf_t       *bp,
 557         int             kfirst,
 558         int             klast)
 559 {
 560         xfs_trans_t     *tp;
 561
 562         XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
 563         XFS_BMBT_TRACE_ARGBII(cur, bp, kfirst, klast);
 564         tp = cur->bc_tp;
 565         if (bp) {
 566                 xfs_bmbt_block_t        *block;
 567                 int                     first;
 568                 xfs_bmbt_key_t          *kp;
 569                 int                     last;
 570
 571                 block = XFS_BUF_TO_BMBT_BLOCK(bp);
 572                 kp = XFS_BMAP_KEY_DADDR(block, 1, cur);
 573                 first = (int)((xfs_caddr_t)&kp[kfirst - 1] - (xfs_caddr_t)block);
 574                 last = (int)(((xfs_caddr_t)&kp[klast] - 1) - (xfs_caddr_t)block);
 575                 xfs_trans_log_buf(tp, bp, first, last);
 576         } else {
 577                 xfs_inode_t              *ip;
 578
 579                 ip = cur->bc_private.b.ip;
 580                 xfs_trans_log_inode(tp, ip,
 581                         XFS_ILOG_FBROOT(cur->bc_private.b.whichfork));
 582         }
 583         XFS_BMBT_TRACE_CURSOR(cur, EXIT);
 584 }
 585
 586 /*
 587  * Log pointer values from the btree block.
 588  */
 589 STATIC void
 590 xfs_bmbt_log_ptrs(
 591         xfs_btree_cur_t *cur,
 592         xfs_buf_t       *bp,
 593         int             pfirst,
 594         int             plast)
 595 {
 596         xfs_trans_t     *tp;
 597
 598         XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
 599         XFS_BMBT_TRACE_ARGBII(cur, bp, pfirst, plast);
 600         tp = cur->bc_tp;
 601         if (bp) {
 602                 xfs_bmbt_block_t        *block;
 603                 int                     first;
 604                 int                     last;
 605                 xfs_bmbt_ptr_t          *pp;
 606
 607                 block = XFS_BUF_TO_BMBT_BLOCK(bp);
 608                 pp = XFS_BMAP_PTR_DADDR(block, 1, cur);
 609                 first = (int)((xfs_caddr_t)&pp[pfirst - 1] - (xfs_caddr_t)block);
 610                 last = (int)(((xfs_caddr_t)&pp[plast] - 1) - (xfs_caddr_t)block);
 611                 xfs_trans_log_buf(tp, bp, first, last);
 612         } else {
 613                 xfs_inode_t             *ip;
 614
 615                 ip = cur->bc_private.b.ip;
 616                 xfs_trans_log_inode(tp, ip,
 617                         XFS_ILOG_FBROOT(cur->bc_private.b.whichfork));
 618         }
 619         XFS_BMBT_TRACE_CURSOR(cur, EXIT);
 620 }
 621
 622 /*
 623  * Determine the extent state.
 624  */
 625 /* ARGSUSED */
 626 STATIC xfs_exntst_t
 627 xfs_extent_state(
 628         xfs_filblks_t           blks,
 629         int                     extent_flag)
 630 {
 631         if (extent_flag) {
 632                 ASSERT(blks != 0);      /* saved for DMIG */
 633                 return XFS_EXT_UNWRITTEN;
 634         }
 635         return XFS_EXT_NORM;
 636 }
 637
 638 /*
 639  * Convert on-disk form of btree root to in-memory form.
 640  */
 641 void
 642 xfs_bmdr_to_bmbt(
 643         xfs_bmdr_block_t        *dblock,
 644         int                     dblocklen,
 645         xfs_bmbt_block_t        *rblock,
 646         int                     rblocklen)
 647 {
 648         int                     dmxr;
 649         xfs_bmbt_key_t          *fkp;
 650         __be64                  *fpp;
 651         xfs_bmbt_key_t          *tkp;
 652         __be64                  *tpp;
 653
 654         rblock->bb_magic = cpu_to_be32(XFS_BMAP_MAGIC);
 655         rblock->bb_level = dblock->bb_level;
 656         ASSERT(be16_to_cpu(rblock->bb_level) > 0);
 657         rblock->bb_numrecs = dblock->bb_numrecs;
 658         rblock->bb_leftsib = cpu_to_be64(NULLDFSBNO);
 659         rblock->bb_rightsib = cpu_to_be64(NULLDFSBNO);
 660         dmxr = (int)XFS_BTREE_BLOCK_MAXRECS(dblocklen, xfs_bmdr, 0);
 661         fkp = XFS_BTREE_KEY_ADDR(xfs_bmdr, dblock, 1);
 662         tkp = XFS_BMAP_BROOT_KEY_ADDR(rblock, 1, rblocklen);
 663         fpp = XFS_BTREE_PTR_ADDR(xfs_bmdr, dblock, 1, dmxr);
 664         tpp = XFS_BMAP_BROOT_PTR_ADDR(rblock, 1, rblocklen);
 665         dmxr = be16_to_cpu(dblock->bb_numrecs);
 666         memcpy(tkp, fkp, sizeof(*fkp) * dmxr);
 667         memcpy(tpp, fpp, sizeof(*fpp) * dmxr);
 668 }
 669
 670 /*
 671  * Delete the record pointed to by cur.
 672  */
 673 int                                     /* error */
 674 xfs_bmbt_delete(
 675         xfs_btree_cur_t *cur,
 676         int             *stat)          /* success/failure */
 677 {
 678         int             error;          /* error return value */
 679         int             i;
 680         int             level;
 681
 682         XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
 683         for (level = 0, i = 2; i == 2; level++) {
 684                 if ((error = xfs_bmbt_delrec(cur, level, &i))) {
 685                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
 686                         return error;
 687                 }
 688         }
 689         if (i == 0) {
 690                 for (level = 1; level < cur->bc_nlevels; level++) {
 691                         if (cur->bc_ptrs[level] == 0) {
 692                                 if ((error = xfs_btree_decrement(cur, level,
 693                                                 &i))) {
 694                                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
 695                                         return error;
 696                                 }
 697                                 break;
 698                         }
 699                 }
 700         }
 701         XFS_BMBT_TRACE_CURSOR(cur, EXIT);
 702         *stat = i;
 703         return 0;
 704 }
 705
 706 /*
 707  * Convert a compressed bmap extent record to an uncompressed form.
 708  * This code must be in sync with the routines xfs_bmbt_get_startoff,
 709  * xfs_bmbt_get_startblock, xfs_bmbt_get_blockcount and xfs_bmbt_get_state.
 710  */
 711
 712 STATIC_INLINE void
 713 __xfs_bmbt_get_all(
 714                 __uint64_t l0,
 715                 __uint64_t l1,
 716                 xfs_bmbt_irec_t *s)
 717 {
 718         int     ext_flag;
 719         xfs_exntst_t st;
 720
 721         ext_flag = (int)(l0 >> (64 - BMBT_EXNTFLAG_BITLEN));
 722         s->br_startoff = ((xfs_fileoff_t)l0 &
 723                            XFS_MASK64LO(64 - BMBT_EXNTFLAG_BITLEN)) >> 9;
 724 #if XFS_BIG_BLKNOS
 725         s->br_startblock = (((xfs_fsblock_t)l0 & XFS_MASK64LO(9)) << 43) |
 726                            (((xfs_fsblock_t)l1) >> 21);
 727 #else
 728 #ifdef DEBUG
 729         {
 730                 xfs_dfsbno_t    b;
 731
 732                 b = (((xfs_dfsbno_t)l0 & XFS_MASK64LO(9)) << 43) |
 733                     (((xfs_dfsbno_t)l1) >> 21);
 734                 ASSERT((b >> 32) == 0 || ISNULLDSTARTBLOCK(b));
 735                 s->br_startblock = (xfs_fsblock_t)b;
 736         }
 737 #else   /* !DEBUG */
 738         s->br_startblock = (xfs_fsblock_t)(((xfs_dfsbno_t)l1) >> 21);
 739 #endif  /* DEBUG */
 740 #endif  /* XFS_BIG_BLKNOS */
 741         s->br_blockcount = (xfs_filblks_t)(l1 & XFS_MASK64LO(21));
 742         /* This is xfs_extent_state() in-line */
 743         if (ext_flag) {
 744                 ASSERT(s->br_blockcount != 0);  /* saved for DMIG */
 745                 st = XFS_EXT_UNWRITTEN;
 746         } else
 747                 st = XFS_EXT_NORM;
 748         s->br_state = st;
 749 }
 750
 751 void
 752 xfs_bmbt_get_all(
 753         xfs_bmbt_rec_host_t *r,
 754         xfs_bmbt_irec_t *s)
 755 {
 756         __xfs_bmbt_get_all(r->l0, r->l1, s);
 757 }
 758
 759 /*
 760  * Get the block pointer for the given level of the cursor.
 761  * Fill in the buffer pointer, if applicable.
 762  */
 763 xfs_bmbt_block_t *
 764 xfs_bmbt_get_block(
 765         xfs_btree_cur_t         *cur,
 766         int                     level,
 767         xfs_buf_t               **bpp)
 768 {
 769         xfs_ifork_t             *ifp;
 770         xfs_bmbt_block_t        *rval;
 771
 772         if (level < cur->bc_nlevels - 1) {
 773                 *bpp = cur->bc_bufs[level];
 774                 rval = XFS_BUF_TO_BMBT_BLOCK(*bpp);
 775         } else {
 776                 *bpp = NULL;
 777                 ifp = XFS_IFORK_PTR(cur->bc_private.b.ip,
 778                         cur->bc_private.b.whichfork);
 779                 rval = ifp->if_broot;
 780         }
 781         return rval;
 782 }
 783
 784 /*
 785  * Extract the blockcount field from an in memory bmap extent record.
 786  */
 787 xfs_filblks_t
 788 xfs_bmbt_get_blockcount(
 789         xfs_bmbt_rec_host_t     *r)
 790 {
 791         return (xfs_filblks_t)(r->l1 & XFS_MASK64LO(21));
 792 }
 793
 794 /*
 795  * Extract the startblock field from an in memory bmap extent record.
 796  */
 797 xfs_fsblock_t
 798 xfs_bmbt_get_startblock(
 799         xfs_bmbt_rec_host_t     *r)
 800 {
 801 #if XFS_BIG_BLKNOS
 802         return (((xfs_fsblock_t)r->l0 & XFS_MASK64LO(9)) << 43) |
 803                (((xfs_fsblock_t)r->l1) >> 21);
 804 #else
 805 #ifdef DEBUG
 806         xfs_dfsbno_t    b;
 807
 808         b = (((xfs_dfsbno_t)r->l0 & XFS_MASK64LO(9)) << 43) |
 809             (((xfs_dfsbno_t)r->l1) >> 21);
 810         ASSERT((b >> 32) == 0 || ISNULLDSTARTBLOCK(b));
 811         return (xfs_fsblock_t)b;
 812 #else   /* !DEBUG */
 813         return (xfs_fsblock_t)(((xfs_dfsbno_t)r->l1) >> 21);
 814 #endif  /* DEBUG */
 815 #endif  /* XFS_BIG_BLKNOS */
 816 }
 817
 818 /*
 819  * Extract the startoff field from an in memory bmap extent record.
 820  */
 821 xfs_fileoff_t
 822 xfs_bmbt_get_startoff(
 823         xfs_bmbt_rec_host_t     *r)
 824 {
 825         return ((xfs_fileoff_t)r->l0 &
 826                  XFS_MASK64LO(64 - BMBT_EXNTFLAG_BITLEN)) >> 9;
 827 }
 828
 829 xfs_exntst_t
 830 xfs_bmbt_get_state(
 831         xfs_bmbt_rec_host_t     *r)
 832 {
 833         int     ext_flag;
 834
 835         ext_flag = (int)((r->l0) >> (64 - BMBT_EXNTFLAG_BITLEN));
 836         return xfs_extent_state(xfs_bmbt_get_blockcount(r),
 837                                 ext_flag);
 838 }
 839
 840 /* Endian flipping versions of the bmbt extraction functions */
 841 void
 842 xfs_bmbt_disk_get_all(
 843         xfs_bmbt_rec_t  *r,
 844         xfs_bmbt_irec_t *s)
 845 {
 846         __xfs_bmbt_get_all(be64_to_cpu(r->l0), be64_to_cpu(r->l1), s);
 847 }
 848
 849 /*
 850  * Extract the blockcount field from an on disk bmap extent record.
 851  */
 852 xfs_filblks_t
 853 xfs_bmbt_disk_get_blockcount(
 854         xfs_bmbt_rec_t  *r)
 855 {
 856         return (xfs_filblks_t)(be64_to_cpu(r->l1) & XFS_MASK64LO(21));
 857 }
 858
 859 /*
 860  * Extract the startoff field from a disk format bmap extent record.
 861  */
 862 xfs_fileoff_t
 863 xfs_bmbt_disk_get_startoff(
 864         xfs_bmbt_rec_t  *r)
 865 {
 866         return ((xfs_fileoff_t)be64_to_cpu(r->l0) &
 867                  XFS_MASK64LO(64 - BMBT_EXNTFLAG_BITLEN)) >> 9;
 868 }
 869
 870 /*
 871  * Log fields from the btree block header.
 872  */
 873 void
 874 xfs_bmbt_log_block(
 875         xfs_btree_cur_t         *cur,
 876         xfs_buf_t               *bp,
 877         int                     fields)
 878 {
 879         int                     first;
 880         int                     last;
 881         xfs_trans_t             *tp;
 882         static const short      offsets[] = {
 883                 offsetof(xfs_bmbt_block_t, bb_magic),
 884                 offsetof(xfs_bmbt_block_t, bb_level),
 885                 offsetof(xfs_bmbt_block_t, bb_numrecs),
 886                 offsetof(xfs_bmbt_block_t, bb_leftsib),
 887                 offsetof(xfs_bmbt_block_t, bb_rightsib),
 888                 sizeof(xfs_bmbt_block_t)
 889         };
 890
 891         XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
 892         XFS_BMBT_TRACE_ARGBI(cur, bp, fields);
 893         tp = cur->bc_tp;
 894         if (bp) {
 895                 xfs_btree_offsets(fields, offsets, XFS_BB_NUM_BITS, &first,
 896                                   &last);
 897                 xfs_trans_log_buf(tp, bp, first, last);
 898         } else
 899                 xfs_trans_log_inode(tp, cur->bc_private.b.ip,
 900                         XFS_ILOG_FBROOT(cur->bc_private.b.whichfork));
 901         XFS_BMBT_TRACE_CURSOR(cur, EXIT);
 902 }
 903
 904 /*
 905  * Log record values from the btree block.
 906  */
 907 void
 908 xfs_bmbt_log_recs(
 909         xfs_btree_cur_t         *cur,
 910         xfs_buf_t               *bp,
 911         int                     rfirst,
 912         int                     rlast)
 913 {
 914         xfs_bmbt_block_t        *block;
 915         int                     first;
 916         int                     last;
 917         xfs_bmbt_rec_t          *rp;
 918         xfs_trans_t             *tp;
 919
 920         XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
 921         XFS_BMBT_TRACE_ARGBII(cur, bp, rfirst, rlast);
 922         ASSERT(bp);
 923         tp = cur->bc_tp;
 924         block = XFS_BUF_TO_BMBT_BLOCK(bp);
 925         rp = XFS_BMAP_REC_DADDR(block, 1, cur);
 926         first = (int)((xfs_caddr_t)&rp[rfirst - 1] - (xfs_caddr_t)block);
 927         last = (int)(((xfs_caddr_t)&rp[rlast] - 1) - (xfs_caddr_t)block);
 928         xfs_trans_log_buf(tp, bp, first, last);
 929         XFS_BMBT_TRACE_CURSOR(cur, EXIT);
 930 }
 931
 932 /*
 933  * Set all the fields in a bmap extent record from the arguments.
 934  */
 935 void
 936 xfs_bmbt_set_allf(
 937         xfs_bmbt_rec_host_t     *r,
 938         xfs_fileoff_t           startoff,
 939         xfs_fsblock_t           startblock,
 940         xfs_filblks_t           blockcount,
 941         xfs_exntst_t            state)
 942 {
 943         int             extent_flag = (state == XFS_EXT_NORM) ? 0 : 1;
 944
 945         ASSERT(state == XFS_EXT_NORM || state == XFS_EXT_UNWRITTEN);
 946         ASSERT((startoff & XFS_MASK64HI(64-BMBT_STARTOFF_BITLEN)) == 0);
 947         ASSERT((blockcount & XFS_MASK64HI(64-BMBT_BLOCKCOUNT_BITLEN)) == 0);
 948
 949 #if XFS_BIG_BLKNOS
 950         ASSERT((startblock & XFS_MASK64HI(64-BMBT_STARTBLOCK_BITLEN)) == 0);
 951
 952         r->l0 = ((xfs_bmbt_rec_base_t)extent_flag << 63) |
 953                 ((xfs_bmbt_rec_base_t)startoff << 9) |
 954                 ((xfs_bmbt_rec_base_t)startblock >> 43);
 955         r->l1 = ((xfs_bmbt_rec_base_t)startblock << 21) |
 956                 ((xfs_bmbt_rec_base_t)blockcount &
 957                 (xfs_bmbt_rec_base_t)XFS_MASK64LO(21));
 958 #else   /* !XFS_BIG_BLKNOS */
 959         if (ISNULLSTARTBLOCK(startblock)) {
 960                 r->l0 = ((xfs_bmbt_rec_base_t)extent_flag << 63) |
 961                         ((xfs_bmbt_rec_base_t)startoff << 9) |
 962                          (xfs_bmbt_rec_base_t)XFS_MASK64LO(9);
 963                 r->l1 = XFS_MASK64HI(11) |
 964                           ((xfs_bmbt_rec_base_t)startblock << 21) |
 965                           ((xfs_bmbt_rec_base_t)blockcount &
 966                            (xfs_bmbt_rec_base_t)XFS_MASK64LO(21));
 967         } else {
 968                 r->l0 = ((xfs_bmbt_rec_base_t)extent_flag << 63) |
 969                         ((xfs_bmbt_rec_base_t)startoff << 9);
 970                 r->l1 = ((xfs_bmbt_rec_base_t)startblock << 21) |
 971                          ((xfs_bmbt_rec_base_t)blockcount &
 972                          (xfs_bmbt_rec_base_t)XFS_MASK64LO(21));
 973         }
 974 #endif  /* XFS_BIG_BLKNOS */
 975 }
 976
 977 /*
 978  * Set all the fields in a bmap extent record from the uncompressed form.
 979  */
 980 void
 981 xfs_bmbt_set_all(
 982         xfs_bmbt_rec_host_t *r,
 983         xfs_bmbt_irec_t *s)
 984 {
 985         xfs_bmbt_set_allf(r, s->br_startoff, s->br_startblock,
 986                              s->br_blockcount, s->br_state);
 987 }
 988
 989
 990 /*
 991  * Set all the fields in a disk format bmap extent record from the arguments.
 992  */
 993 void
 994 xfs_bmbt_disk_set_allf(
 995         xfs_bmbt_rec_t          *r,
 996         xfs_fileoff_t           startoff,
 997         xfs_fsblock_t           startblock,
 998         xfs_filblks_t           blockcount,
 999         xfs_exntst_t            state)
1000 {
1001         int                     extent_flag = (state == XFS_EXT_NORM) ? 0 : 1;
1002
1003         ASSERT(state == XFS_EXT_NORM || state == XFS_EXT_UNWRITTEN);
1004         ASSERT((startoff & XFS_MASK64HI(64-BMBT_STARTOFF_BITLEN)) == 0);
1005         ASSERT((blockcount & XFS_MASK64HI(64-BMBT_BLOCKCOUNT_BITLEN)) == 0);
1006
1007 #if XFS_BIG_BLKNOS
1008         ASSERT((startblock & XFS_MASK64HI(64-BMBT_STARTBLOCK_BITLEN)) == 0);
1009
1010         r->l0 = cpu_to_be64(
1011                 ((xfs_bmbt_rec_base_t)extent_flag << 63) |
1012                  ((xfs_bmbt_rec_base_t)startoff << 9) |
1013                  ((xfs_bmbt_rec_base_t)startblock >> 43));
1014         r->l1 = cpu_to_be64(
1015                 ((xfs_bmbt_rec_base_t)startblock << 21) |
1016                  ((xfs_bmbt_rec_base_t)blockcount &
1017                   (xfs_bmbt_rec_base_t)XFS_MASK64LO(21)));
1018 #else   /* !XFS_BIG_BLKNOS */
1019         if (ISNULLSTARTBLOCK(startblock)) {
1020                 r->l0 = cpu_to_be64(
1021                         ((xfs_bmbt_rec_base_t)extent_flag << 63) |
1022                          ((xfs_bmbt_rec_base_t)startoff << 9) |
1023                           (xfs_bmbt_rec_base_t)XFS_MASK64LO(9));
1024                 r->l1 = cpu_to_be64(XFS_MASK64HI(11) |
1025                           ((xfs_bmbt_rec_base_t)startblock << 21) |
1026                           ((xfs_bmbt_rec_base_t)blockcount &
1027                            (xfs_bmbt_rec_base_t)XFS_MASK64LO(21)));
1028         } else {
1029                 r->l0 = cpu_to_be64(
1030                         ((xfs_bmbt_rec_base_t)extent_flag << 63) |
1031                          ((xfs_bmbt_rec_base_t)startoff << 9));
1032                 r->l1 = cpu_to_be64(
1033                         ((xfs_bmbt_rec_base_t)startblock << 21) |
1034                          ((xfs_bmbt_rec_base_t)blockcount &
1035                           (xfs_bmbt_rec_base_t)XFS_MASK64LO(21)));
1036         }
1037 #endif  /* XFS_BIG_BLKNOS */
1038 }
1039
1040 /*
1041  * Set all the fields in a bmap extent record from the uncompressed form.
1042  */
1043 void
1044 xfs_bmbt_disk_set_all(
1045         xfs_bmbt_rec_t  *r,
1046         xfs_bmbt_irec_t *s)
1047 {
1048         xfs_bmbt_disk_set_allf(r, s->br_startoff, s->br_startblock,
1049                                   s->br_blockcount, s->br_state);
1050 }
1051
1052 /*
1053  * Set the blockcount field in a bmap extent record.
1054  */
1055 void
1056 xfs_bmbt_set_blockcount(
1057         xfs_bmbt_rec_host_t *r,
1058         xfs_filblks_t   v)
1059 {
1060         ASSERT((v & XFS_MASK64HI(43)) == 0);
1061         r->l1 = (r->l1 & (xfs_bmbt_rec_base_t)XFS_MASK64HI(43)) |
1062                   (xfs_bmbt_rec_base_t)(v & XFS_MASK64LO(21));
1063 }
1064
1065 /*
1066  * Set the startblock field in a bmap extent record.
1067  */
1068 void
1069 xfs_bmbt_set_startblock(
1070         xfs_bmbt_rec_host_t *r,
1071         xfs_fsblock_t   v)
1072 {
1073 #if XFS_BIG_BLKNOS
1074         ASSERT((v & XFS_MASK64HI(12)) == 0);
1075         r->l0 = (r->l0 & (xfs_bmbt_rec_base_t)XFS_MASK64HI(55)) |
1076                   (xfs_bmbt_rec_base_t)(v >> 43);
1077         r->l1 = (r->l1 & (xfs_bmbt_rec_base_t)XFS_MASK64LO(21)) |
1078                   (xfs_bmbt_rec_base_t)(v << 21);
1079 #else   /* !XFS_BIG_BLKNOS */
1080         if (ISNULLSTARTBLOCK(v)) {
1081                 r->l0 |= (xfs_bmbt_rec_base_t)XFS_MASK64LO(9);
1082                 r->l1 = (xfs_bmbt_rec_base_t)XFS_MASK64HI(11) |
1083                           ((xfs_bmbt_rec_base_t)v << 21) |
1084                           (r->l1 & (xfs_bmbt_rec_base_t)XFS_MASK64LO(21));
1085         } else {
1086                 r->l0 &= ~(xfs_bmbt_rec_base_t)XFS_MASK64LO(9);
1087                 r->l1 = ((xfs_bmbt_rec_base_t)v << 21) |
1088                           (r->l1 & (xfs_bmbt_rec_base_t)XFS_MASK64LO(21));
1089         }
1090 #endif  /* XFS_BIG_BLKNOS */
1091 }
1092
1093 /*
1094  * Set the startoff field in a bmap extent record.
1095  */
1096 void
1097 xfs_bmbt_set_startoff(
1098         xfs_bmbt_rec_host_t *r,
1099         xfs_fileoff_t   v)
1100 {
1101         ASSERT((v & XFS_MASK64HI(9)) == 0);
1102         r->l0 = (r->l0 & (xfs_bmbt_rec_base_t) XFS_MASK64HI(1)) |
1103                 ((xfs_bmbt_rec_base_t)v << 9) |
1104                   (r->l0 & (xfs_bmbt_rec_base_t)XFS_MASK64LO(9));
1105 }
1106
1107 /*
1108  * Set the extent state field in a bmap extent record.
1109  */
1110 void
1111 xfs_bmbt_set_state(
1112         xfs_bmbt_rec_host_t *r,
1113         xfs_exntst_t    v)
1114 {
1115         ASSERT(v == XFS_EXT_NORM || v == XFS_EXT_UNWRITTEN);
1116         if (v == XFS_EXT_NORM)
1117                 r->l0 &= XFS_MASK64LO(64 - BMBT_EXNTFLAG_BITLEN);
1118         else
1119                 r->l0 |= XFS_MASK64HI(BMBT_EXNTFLAG_BITLEN);
1120 }
1121
1122 /*
1123  * Convert in-memory form of btree root to on-disk form.
1124  */
1125 void
1126 xfs_bmbt_to_bmdr(
1127         xfs_bmbt_block_t        *rblock,
1128         int                     rblocklen,
1129         xfs_bmdr_block_t        *dblock,
1130         int                     dblocklen)
1131 {
1132         int                     dmxr;
1133         xfs_bmbt_key_t          *fkp;
1134         __be64                  *fpp;
1135         xfs_bmbt_key_t          *tkp;
1136         __be64                  *tpp;
1137
1138         ASSERT(be32_to_cpu(rblock->bb_magic) == XFS_BMAP_MAGIC);
1139         ASSERT(be64_to_cpu(rblock->bb_leftsib) == NULLDFSBNO);
1140         ASSERT(be64_to_cpu(rblock->bb_rightsib) == NULLDFSBNO);
1141         ASSERT(be16_to_cpu(rblock->bb_level) > 0);
1142         dblock->bb_level = rblock->bb_level;
1143         dblock->bb_numrecs = rblock->bb_numrecs;
1144         dmxr = (int)XFS_BTREE_BLOCK_MAXRECS(dblocklen, xfs_bmdr, 0);
1145         fkp = XFS_BMAP_BROOT_KEY_ADDR(rblock, 1, rblocklen);
1146         tkp = XFS_BTREE_KEY_ADDR(xfs_bmdr, dblock, 1);
1147         fpp = XFS_BMAP_BROOT_PTR_ADDR(rblock, 1, rblocklen);
1148         tpp = XFS_BTREE_PTR_ADDR(xfs_bmdr, dblock, 1, dmxr);
1149         dmxr = be16_to_cpu(dblock->bb_numrecs);
1150         memcpy(tkp, fkp, sizeof(*fkp) * dmxr);
1151         memcpy(tpp, fpp, sizeof(*fpp) * dmxr);
1152 }
1153
1154 /*
1155  * Check extent records, which have just been read, for
1156  * any bit in the extent flag field. ASSERT on debug
1157  * kernels, as this condition should not occur.
1158  * Return an error condition (1) if any flags found,
1159  * otherwise return 0.
1160  */
1161
1162 int
1163 xfs_check_nostate_extents(
1164         xfs_ifork_t             *ifp,
1165         xfs_extnum_t            idx,
1166         xfs_extnum_t            num)
1167 {
1168         for (; num > 0; num--, idx++) {
1169                 xfs_bmbt_rec_host_t *ep = xfs_iext_get_ext(ifp, idx);
1170                 if ((ep->l0 >>
1171                      (64 - BMBT_EXNTFLAG_BITLEN)) != 0) {
1172                         ASSERT(0);
1173                         return 1;
1174                 }
1175         }
1176         return 0;
1177 }
1178
1179
1180 STATIC struct xfs_btree_cur *
1181 xfs_bmbt_dup_cursor(
1182         struct xfs_btree_cur    *cur)
1183 {
1184         struct xfs_btree_cur    *new;
1185
1186         new = xfs_bmbt_init_cursor(cur->bc_mp, cur->bc_tp,
1187                         cur->bc_private.b.ip, cur->bc_private.b.whichfork);
1188
1189         /*
1190          * Copy the firstblock, flist, and flags values,
1191          * since init cursor doesn't get them.
1192          */
1193         new->bc_private.b.firstblock = cur->bc_private.b.firstblock;
1194         new->bc_private.b.flist = cur->bc_private.b.flist;
1195         new->bc_private.b.flags = cur->bc_private.b.flags;
1196
1197         return new;
1198 }
1199
1200 STATIC void
1201 xfs_bmbt_update_cursor(
1202         struct xfs_btree_cur    *src,
1203         struct xfs_btree_cur    *dst)
1204 {
1205         ASSERT((dst->bc_private.b.firstblock != NULLFSBLOCK) ||
1206                (dst->bc_private.b.ip->i_d.di_flags & XFS_DIFLAG_REALTIME));
1207         ASSERT(dst->bc_private.b.flist == src->bc_private.b.flist);
1208
1209         dst->bc_private.b.allocated += src->bc_private.b.allocated;
1210         dst->bc_private.b.firstblock = src->bc_private.b.firstblock;
1211
1212         src->bc_private.b.allocated = 0;
1213 }
1214
1215 STATIC int
1216 xfs_bmbt_alloc_block(
1217         struct xfs_btree_cur    *cur,
1218         union xfs_btree_ptr     *start,
1219         union xfs_btree_ptr     *new,
1220         int                     length,
1221         int                     *stat)
1222 {
1223         xfs_alloc_arg_t         args;           /* block allocation args */
1224         int                     error;          /* error return value */
1225
1226         memset(&args, 0, sizeof(args));
1227         args.tp = cur->bc_tp;
1228         args.mp = cur->bc_mp;
1229         args.fsbno = cur->bc_private.b.firstblock;
1230         args.firstblock = args.fsbno;
1231
1232         if (args.fsbno == NULLFSBLOCK) {
1233                 args.fsbno = be64_to_cpu(start->l);
1234                 args.type = XFS_ALLOCTYPE_START_BNO;
1235                 /*
1236                  * Make sure there is sufficient room left in the AG to
1237                  * complete a full tree split for an extent insert.  If
1238                  * we are converting the middle part of an extent then
1239                  * we may need space for two tree splits.
1240                  *
1241                  * We are relying on the caller to make the correct block
1242                  * reservation for this operation to succeed.  If the
1243                  * reservation amount is insufficient then we may fail a
1244                  * block allocation here and corrupt the filesystem.
1245                  */
1246                 args.minleft = xfs_trans_get_block_res(args.tp);
1247         } else if (cur->bc_private.b.flist->xbf_low) {
1248                 args.type = XFS_ALLOCTYPE_START_BNO;
1249         } else {
1250                 args.type = XFS_ALLOCTYPE_NEAR_BNO;
1251         }
1252
1253         args.minlen = args.maxlen = args.prod = 1;
1254         args.wasdel = cur->bc_private.b.flags & XFS_BTCUR_BPRV_WASDEL;
1255         if (!args.wasdel && xfs_trans_get_block_res(args.tp) == 0) {
1256                 error = XFS_ERROR(ENOSPC);
1257                 goto error0;
1258         }
1259         error = xfs_alloc_vextent(&args);
1260         if (error)
1261                 goto error0;
1262
1263         if (args.fsbno == NULLFSBLOCK && args.minleft) {
1264                 /*
1265                  * Could not find an AG with enough free space to satisfy
1266                  * a full btree split.  Try again without minleft and if
1267                  * successful activate the lowspace algorithm.
1268                  */
1269                 args.fsbno = 0;
1270                 args.type = XFS_ALLOCTYPE_FIRST_AG;
1271                 args.minleft = 0;
1272                 error = xfs_alloc_vextent(&args);
1273                 if (error)
1274                         goto error0;
1275                 cur->bc_private.b.flist->xbf_low = 1;
1276         }
1277         if (args.fsbno == NULLFSBLOCK) {
1278                 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
1279                 *stat = 0;
1280                 return 0;
1281         }
1282         ASSERT(args.len == 1);
1283         cur->bc_private.b.firstblock = args.fsbno;
1284         cur->bc_private.b.allocated++;
1285         cur->bc_private.b.ip->i_d.di_nblocks++;
1286         xfs_trans_log_inode(args.tp, cur->bc_private.b.ip, XFS_ILOG_CORE);
1287         XFS_TRANS_MOD_DQUOT_BYINO(args.mp, args.tp, cur->bc_private.b.ip,
1288                         XFS_TRANS_DQ_BCOUNT, 1L);
1289
1290         new->l = cpu_to_be64(args.fsbno);
1291
1292         XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
1293         *stat = 1;
1294         return 0;
1295
1296  error0:
1297         XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR);
1298         return error;
1299 }
1300
1301 STATIC int
1302 xfs_bmbt_get_maxrecs(
1303         struct xfs_btree_cur    *cur,
1304         int                     level)
1305 {
1306         return XFS_BMAP_BLOCK_IMAXRECS(level, cur);
1307 }
1308
1309 /*
1310  * Get the maximum records we could store in the on-disk format.
1311  *
1312  * For non-root nodes this is equivalent to xfs_bmbt_get_maxrecs, but
1313  * for the root node this checks the available space in the dinode fork
1314  * so that we can resize the in-memory buffer to match it.  After a
1315  * resize to the maximum size this function returns the same value
1316  * as xfs_bmbt_get_maxrecs for the root node, too.
1317  */
1318 STATIC int
1319 xfs_bmbt_get_dmaxrecs(
1320         struct xfs_btree_cur    *cur,
1321         int                     level)
1322 {
1323         return XFS_BMAP_BLOCK_DMAXRECS(level, cur);
1324 }
1325
1326 STATIC void
1327 xfs_bmbt_init_key_from_rec(
1328         union xfs_btree_key     *key,
1329         union xfs_btree_rec     *rec)
1330 {
1331         key->bmbt.br_startoff =
1332                 cpu_to_be64(xfs_bmbt_disk_get_startoff(&rec->bmbt));
1333 }
1334
1335 STATIC void
1336 xfs_bmbt_init_rec_from_key(
1337         union xfs_btree_key     *key,
1338         union xfs_btree_rec     *rec)
1339 {
1340         ASSERT(key->bmbt.br_startoff != 0);
1341
1342         xfs_bmbt_disk_set_allf(&rec->bmbt, be64_to_cpu(key->bmbt.br_startoff),
1343                                0, 0, XFS_EXT_NORM);
1344 }
1345
1346 STATIC void
1347 xfs_bmbt_init_rec_from_cur(
1348         struct xfs_btree_cur    *cur,
1349         union xfs_btree_rec     *rec)
1350 {
1351         xfs_bmbt_disk_set_all(&rec->bmbt, &cur->bc_rec.b);
1352 }
1353
1354 STATIC void
1355 xfs_bmbt_init_ptr_from_cur(
1356         struct xfs_btree_cur    *cur,
1357         union xfs_btree_ptr     *ptr)
1358 {
1359         ptr->l = 0;
1360 }
1361
1362 STATIC __int64_t
1363 xfs_bmbt_key_diff(
1364         struct xfs_btree_cur    *cur,
1365         union xfs_btree_key     *key)
1366 {
1367         return (__int64_t)be64_to_cpu(key->bmbt.br_startoff) -
1368                                       cur->bc_rec.b.br_startoff;
1369 }
1370
1371 #ifdef XFS_BTREE_TRACE
1372 ktrace_t        *xfs_bmbt_trace_buf;
1373
1374 STATIC void
1375 xfs_bmbt_trace_enter(
1376         struct xfs_btree_cur    *cur,
1377         const char              *func,
1378         char                    *s,
1379         int                     type,
1380         int                     line,
1381         __psunsigned_t          a0,
1382         __psunsigned_t          a1,
1383         __psunsigned_t          a2,
1384         __psunsigned_t          a3,
1385         __psunsigned_t          a4,
1386         __psunsigned_t          a5,
1387         __psunsigned_t          a6,
1388         __psunsigned_t          a7,
1389         __psunsigned_t          a8,
1390         __psunsigned_t          a9,
1391         __psunsigned_t          a10)
1392 {
1393         struct xfs_inode        *ip = cur->bc_private.b.ip;
1394         int                     whichfork = cur->bc_private.b.whichfork;
1395
1396         ktrace_enter(xfs_bmbt_trace_buf,
1397                 (void *)((__psint_t)type | (whichfork << 8) | (line << 16)),
1398                 (void *)func, (void *)s, (void *)ip, (void *)cur,
1399                 (void *)a0, (void *)a1, (void *)a2, (void *)a3,
1400                 (void *)a4, (void *)a5, (void *)a6, (void *)a7,
1401                 (void *)a8, (void *)a9, (void *)a10);
1402         ktrace_enter(ip->i_btrace,
1403                 (void *)((__psint_t)type | (whichfork << 8) | (line << 16)),
1404                 (void *)func, (void *)s, (void *)ip, (void *)cur,
1405                 (void *)a0, (void *)a1, (void *)a2, (void *)a3,
1406                 (void *)a4, (void *)a5, (void *)a6, (void *)a7,
1407                 (void *)a8, (void *)a9, (void *)a10);
1408 }
1409
1410 STATIC void
1411 xfs_bmbt_trace_cursor(
1412         struct xfs_btree_cur    *cur,
1413         __uint32_t              *s0,
1414         __uint64_t              *l0,
1415         __uint64_t              *l1)
1416 {
1417         struct xfs_bmbt_rec_host r;
1418
1419         xfs_bmbt_set_all(&r, &cur->bc_rec.b);
1420
1421         *s0 = (cur->bc_nlevels << 24) |
1422               (cur->bc_private.b.flags << 16) |
1423                cur->bc_private.b.allocated;
1424         *l0 = r.l0;
1425         *l1 = r.l1;
1426 }
1427
1428 STATIC void
1429 xfs_bmbt_trace_key(
1430         struct xfs_btree_cur    *cur,
1431         union xfs_btree_key     *key,
1432         __uint64_t              *l0,
1433         __uint64_t              *l1)
1434 {
1435         *l0 = be64_to_cpu(key->bmbt.br_startoff);
1436         *l1 = 0;
1437 }
1438
1439 STATIC void
1440 xfs_bmbt_trace_record(
1441         struct xfs_btree_cur    *cur,
1442         union xfs_btree_rec     *rec,
1443         __uint64_t              *l0,
1444         __uint64_t              *l1,
1445         __uint64_t              *l2)
1446 {
1447         struct xfs_bmbt_irec    irec;
1448
1449         xfs_bmbt_disk_get_all(&rec->bmbt, &irec);
1450         *l0 = irec.br_startoff;
1451         *l1 = irec.br_startblock;
1452         *l2 = irec.br_blockcount;
1453 }
1454 #endif /* XFS_BTREE_TRACE */
1455
1456 static const struct xfs_btree_ops xfs_bmbt_ops = {
1457         .rec_len                = sizeof(xfs_bmbt_rec_t),
1458         .key_len                = sizeof(xfs_bmbt_key_t),
1459
1460         .dup_cursor             = xfs_bmbt_dup_cursor,
1461         .update_cursor          = xfs_bmbt_update_cursor,
1462         .alloc_block            = xfs_bmbt_alloc_block,
1463         .get_maxrecs            = xfs_bmbt_get_maxrecs,
1464         .get_dmaxrecs           = xfs_bmbt_get_dmaxrecs,
1465         .init_key_from_rec      = xfs_bmbt_init_key_from_rec,
1466         .init_rec_from_key      = xfs_bmbt_init_rec_from_key,
1467         .init_rec_from_cur      = xfs_bmbt_init_rec_from_cur,
1468         .init_ptr_from_cur      = xfs_bmbt_init_ptr_from_cur,
1469         .key_diff               = xfs_bmbt_key_diff,
1470
1471 #ifdef XFS_BTREE_TRACE
1472         .trace_enter            = xfs_bmbt_trace_enter,
1473         .trace_cursor           = xfs_bmbt_trace_cursor,
1474         .trace_key              = xfs_bmbt_trace_key,
1475         .trace_record           = xfs_bmbt_trace_record,
1476 #endif
1477 };
1478
1479 /*
1480  * Allocate a new bmap btree cursor.
1481  */
1482 struct xfs_btree_cur *                          /* new bmap btree cursor */
1483 xfs_bmbt_init_cursor(
1484         struct xfs_mount        *mp,            /* file system mount point */
1485         struct xfs_trans        *tp,            /* transaction pointer */
1486         struct xfs_inode        *ip,            /* inode owning the btree */
1487         int                     whichfork)      /* data or attr fork */
1488 {
1489         struct xfs_ifork        *ifp = XFS_IFORK_PTR(ip, whichfork);
1490         struct xfs_btree_cur    *cur;
1491
1492         cur = kmem_zone_zalloc(xfs_btree_cur_zone, KM_SLEEP);
1493
1494         cur->bc_tp = tp;
1495         cur->bc_mp = mp;
1496         cur->bc_nlevels = be16_to_cpu(ifp->if_broot->bb_level) + 1;
1497         cur->bc_btnum = XFS_BTNUM_BMAP;
1498         cur->bc_blocklog = mp->m_sb.sb_blocklog;
1499
1500         cur->bc_ops = &xfs_bmbt_ops;
1501         cur->bc_flags = XFS_BTREE_LONG_PTRS | XFS_BTREE_ROOT_IN_INODE;
1502
1503         cur->bc_private.b.forksize = XFS_IFORK_SIZE(ip, whichfork);
1504         cur->bc_private.b.ip = ip;
1505         cur->bc_private.b.firstblock = NULLFSBLOCK;
1506         cur->bc_private.b.flist = NULL;
1507         cur->bc_private.b.allocated = 0;
1508         cur->bc_private.b.flags = 0;
1509         cur->bc_private.b.whichfork = whichfork;
1510
1511         return cur;
1512 }