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

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