git.oblomov.eu Git - linux-2.6/blob - fs/xfs/xfs_bmap_btree.c

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