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