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