SAFE public projects git trees. - safe/jmp/linux-2.6/blob - fs/xfs/xfs_bmap_btree.c

   1 /*
   2  * Copyright (c) 2000-2003,2005 Silicon Graphics, Inc.
   3  * All Rights Reserved.
   4  *
   5  * This program is free software; you can redistribute it and/or
   6  * modify it under the terms of the GNU General Public License as
   7  * published by the Free Software Foundation.
   8  *
   9  * This program is distributed in the hope that it would be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  * GNU General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program; if not, write the Free Software Foundation,
  16  * Inc.,  51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  17  */
  18 #include "xfs.h"
  19 #include "xfs_fs.h"
  20 #include "xfs_types.h"
  21 #include "xfs_bit.h"
  22 #include "xfs_log.h"
  23 #include "xfs_inum.h"
  24 #include "xfs_trans.h"
  25 #include "xfs_sb.h"
  26 #include "xfs_ag.h"
  27 #include "xfs_dir2.h"
  28 #include "xfs_dmapi.h"
  29 #include "xfs_mount.h"
  30 #include "xfs_bmap_btree.h"
  31 #include "xfs_alloc_btree.h"
  32 #include "xfs_ialloc_btree.h"
  33 #include "xfs_dir2_sf.h"
  34 #include "xfs_attr_sf.h"
  35 #include "xfs_dinode.h"
  36 #include "xfs_inode.h"
  37 #include "xfs_inode_item.h"
  38 #include "xfs_alloc.h"
  39 #include "xfs_btree.h"
  40 #include "xfs_btree_trace.h"
  41 #include "xfs_ialloc.h"
  42 #include "xfs_itable.h"
  43 #include "xfs_bmap.h"
  44 #include "xfs_error.h"
  45 #include "xfs_quota.h"
  46
  47 #undef EXIT
  48
  49 #define ENTRY   XBT_ENTRY
  50 #define ERROR   XBT_ERROR
  51 #define EXIT    XBT_EXIT
  52
  53 /*
  54  * Keep the XFS_BMBT_TRACE_ names around for now until all code using them
  55  * is converted to be generic and thus switches to the XFS_BTREE_TRACE_ names.
  56  */
  57 #define XFS_BMBT_TRACE_ARGBI(c,b,i) \
  58         XFS_BTREE_TRACE_ARGBI(c,b,i)
  59 #define XFS_BMBT_TRACE_ARGBII(c,b,i,j) \
  60         XFS_BTREE_TRACE_ARGBII(c,b,i,j)
  61 #define XFS_BMBT_TRACE_ARGFFFI(c,o,b,i,j) \
  62         XFS_BTREE_TRACE_ARGFFFI(c,o,b,i,j)
  63 #define XFS_BMBT_TRACE_ARGI(c,i) \
  64         XFS_BTREE_TRACE_ARGI(c,i)
  65 #define XFS_BMBT_TRACE_ARGIFK(c,i,f,s) \
  66         XFS_BTREE_TRACE_ARGIPK(c,i,(union xfs_btree_ptr)f,s)
  67 #define XFS_BMBT_TRACE_ARGIFR(c,i,f,r) \
  68         XFS_BTREE_TRACE_ARGIPR(c,i, \
  69                 (union xfs_btree_ptr)f, (union xfs_btree_rec *)r)
  70 #define XFS_BMBT_TRACE_ARGIK(c,i,k) \
  71         XFS_BTREE_TRACE_ARGIK(c,i,(union xfs_btree_key *)k)
  72 #define XFS_BMBT_TRACE_CURSOR(c,s) \
  73         XFS_BTREE_TRACE_CURSOR(c,s)
  74
  75 /*
  76  * Determine the extent state.
  77  */
  78 /* ARGSUSED */
  79 STATIC xfs_exntst_t
  80 xfs_extent_state(
  81         xfs_filblks_t           blks,
  82         int                     extent_flag)
  83 {
  84         if (extent_flag) {
  85                 ASSERT(blks != 0);      /* saved for DMIG */
  86                 return XFS_EXT_UNWRITTEN;
  87         }
  88         return XFS_EXT_NORM;
  89 }
  90
  91 /*
  92  * Convert on-disk form of btree root to in-memory form.
  93  */
  94 void
  95 xfs_bmdr_to_bmbt(
  96         xfs_bmdr_block_t        *dblock,
  97         int                     dblocklen,
  98         xfs_bmbt_block_t        *rblock,
  99         int                     rblocklen)
 100 {
 101         int                     dmxr;
 102         xfs_bmbt_key_t          *fkp;
 103         __be64                  *fpp;
 104         xfs_bmbt_key_t          *tkp;
 105         __be64                  *tpp;
 106
 107         rblock->bb_magic = cpu_to_be32(XFS_BMAP_MAGIC);
 108         rblock->bb_level = dblock->bb_level;
 109         ASSERT(be16_to_cpu(rblock->bb_level) > 0);
 110         rblock->bb_numrecs = dblock->bb_numrecs;
 111         rblock->bb_leftsib = cpu_to_be64(NULLDFSBNO);
 112         rblock->bb_rightsib = cpu_to_be64(NULLDFSBNO);
 113         dmxr = (int)XFS_BTREE_BLOCK_MAXRECS(dblocklen, xfs_bmdr, 0);
 114         fkp = XFS_BTREE_KEY_ADDR(xfs_bmdr, dblock, 1);
 115         tkp = XFS_BMAP_BROOT_KEY_ADDR(rblock, 1, rblocklen);
 116         fpp = XFS_BTREE_PTR_ADDR(xfs_bmdr, dblock, 1, dmxr);
 117         tpp = XFS_BMAP_BROOT_PTR_ADDR(rblock, 1, rblocklen);
 118         dmxr = be16_to_cpu(dblock->bb_numrecs);
 119         memcpy(tkp, fkp, sizeof(*fkp) * dmxr);
 120         memcpy(tpp, fpp, sizeof(*fpp) * dmxr);
 121 }
 122
 123 /*
 124  * Convert a compressed bmap extent record to an uncompressed form.
 125  * This code must be in sync with the routines xfs_bmbt_get_startoff,
 126  * xfs_bmbt_get_startblock, xfs_bmbt_get_blockcount and xfs_bmbt_get_state.
 127  */
 128
 129 STATIC_INLINE void
 130 __xfs_bmbt_get_all(
 131                 __uint64_t l0,
 132                 __uint64_t l1,
 133                 xfs_bmbt_irec_t *s)
 134 {
 135         int     ext_flag;
 136         xfs_exntst_t st;
 137
 138         ext_flag = (int)(l0 >> (64 - BMBT_EXNTFLAG_BITLEN));
 139         s->br_startoff = ((xfs_fileoff_t)l0 &
 140                            XFS_MASK64LO(64 - BMBT_EXNTFLAG_BITLEN)) >> 9;
 141 #if XFS_BIG_BLKNOS
 142         s->br_startblock = (((xfs_fsblock_t)l0 & XFS_MASK64LO(9)) << 43) |
 143                            (((xfs_fsblock_t)l1) >> 21);
 144 #else
 145 #ifdef DEBUG
 146         {
 147                 xfs_dfsbno_t    b;
 148
 149                 b = (((xfs_dfsbno_t)l0 & XFS_MASK64LO(9)) << 43) |
 150                     (((xfs_dfsbno_t)l1) >> 21);
 151                 ASSERT((b >> 32) == 0 || ISNULLDSTARTBLOCK(b));
 152                 s->br_startblock = (xfs_fsblock_t)b;
 153         }
 154 #else   /* !DEBUG */
 155         s->br_startblock = (xfs_fsblock_t)(((xfs_dfsbno_t)l1) >> 21);
 156 #endif  /* DEBUG */
 157 #endif  /* XFS_BIG_BLKNOS */
 158         s->br_blockcount = (xfs_filblks_t)(l1 & XFS_MASK64LO(21));
 159         /* This is xfs_extent_state() in-line */
 160         if (ext_flag) {
 161                 ASSERT(s->br_blockcount != 0);  /* saved for DMIG */
 162                 st = XFS_EXT_UNWRITTEN;
 163         } else
 164                 st = XFS_EXT_NORM;
 165         s->br_state = st;
 166 }
 167
 168 void
 169 xfs_bmbt_get_all(
 170         xfs_bmbt_rec_host_t *r,
 171         xfs_bmbt_irec_t *s)
 172 {
 173         __xfs_bmbt_get_all(r->l0, r->l1, s);
 174 }
 175
 176 /*
 177  * Extract the blockcount field from an in memory bmap extent record.
 178  */
 179 xfs_filblks_t
 180 xfs_bmbt_get_blockcount(
 181         xfs_bmbt_rec_host_t     *r)
 182 {
 183         return (xfs_filblks_t)(r->l1 & XFS_MASK64LO(21));
 184 }
 185
 186 /*
 187  * Extract the startblock field from an in memory bmap extent record.
 188  */
 189 xfs_fsblock_t
 190 xfs_bmbt_get_startblock(
 191         xfs_bmbt_rec_host_t     *r)
 192 {
 193 #if XFS_BIG_BLKNOS
 194         return (((xfs_fsblock_t)r->l0 & XFS_MASK64LO(9)) << 43) |
 195                (((xfs_fsblock_t)r->l1) >> 21);
 196 #else
 197 #ifdef DEBUG
 198         xfs_dfsbno_t    b;
 199
 200         b = (((xfs_dfsbno_t)r->l0 & XFS_MASK64LO(9)) << 43) |
 201             (((xfs_dfsbno_t)r->l1) >> 21);
 202         ASSERT((b >> 32) == 0 || ISNULLDSTARTBLOCK(b));
 203         return (xfs_fsblock_t)b;
 204 #else   /* !DEBUG */
 205         return (xfs_fsblock_t)(((xfs_dfsbno_t)r->l1) >> 21);
 206 #endif  /* DEBUG */
 207 #endif  /* XFS_BIG_BLKNOS */
 208 }
 209
 210 /*
 211  * Extract the startoff field from an in memory bmap extent record.
 212  */
 213 xfs_fileoff_t
 214 xfs_bmbt_get_startoff(
 215         xfs_bmbt_rec_host_t     *r)
 216 {
 217         return ((xfs_fileoff_t)r->l0 &
 218                  XFS_MASK64LO(64 - BMBT_EXNTFLAG_BITLEN)) >> 9;
 219 }
 220
 221 xfs_exntst_t
 222 xfs_bmbt_get_state(
 223         xfs_bmbt_rec_host_t     *r)
 224 {
 225         int     ext_flag;
 226
 227         ext_flag = (int)((r->l0) >> (64 - BMBT_EXNTFLAG_BITLEN));
 228         return xfs_extent_state(xfs_bmbt_get_blockcount(r),
 229                                 ext_flag);
 230 }
 231
 232 /* Endian flipping versions of the bmbt extraction functions */
 233 void
 234 xfs_bmbt_disk_get_all(
 235         xfs_bmbt_rec_t  *r,
 236         xfs_bmbt_irec_t *s)
 237 {
 238         __xfs_bmbt_get_all(be64_to_cpu(r->l0), be64_to_cpu(r->l1), s);
 239 }
 240
 241 /*
 242  * Extract the blockcount field from an on disk bmap extent record.
 243  */
 244 xfs_filblks_t
 245 xfs_bmbt_disk_get_blockcount(
 246         xfs_bmbt_rec_t  *r)
 247 {
 248         return (xfs_filblks_t)(be64_to_cpu(r->l1) & XFS_MASK64LO(21));
 249 }
 250
 251 /*
 252  * Extract the startoff field from a disk format bmap extent record.
 253  */
 254 xfs_fileoff_t
 255 xfs_bmbt_disk_get_startoff(
 256         xfs_bmbt_rec_t  *r)
 257 {
 258         return ((xfs_fileoff_t)be64_to_cpu(r->l0) &
 259                  XFS_MASK64LO(64 - BMBT_EXNTFLAG_BITLEN)) >> 9;
 260 }
 261
 262 /*
 263  * Log fields from the btree block header.
 264  */
 265 void
 266 xfs_bmbt_log_block(
 267         xfs_btree_cur_t         *cur,
 268         xfs_buf_t               *bp,
 269         int                     fields)
 270 {
 271         int                     first;
 272         int                     last;
 273         xfs_trans_t             *tp;
 274         static const short      offsets[] = {
 275                 offsetof(xfs_bmbt_block_t, bb_magic),
 276                 offsetof(xfs_bmbt_block_t, bb_level),
 277                 offsetof(xfs_bmbt_block_t, bb_numrecs),
 278                 offsetof(xfs_bmbt_block_t, bb_leftsib),
 279                 offsetof(xfs_bmbt_block_t, bb_rightsib),
 280                 sizeof(xfs_bmbt_block_t)
 281         };
 282
 283         XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
 284         XFS_BMBT_TRACE_ARGBI(cur, bp, fields);
 285         tp = cur->bc_tp;
 286         if (bp) {
 287                 xfs_btree_offsets(fields, offsets, XFS_BB_NUM_BITS, &first,
 288                                   &last);
 289                 xfs_trans_log_buf(tp, bp, first, last);
 290         } else
 291                 xfs_trans_log_inode(tp, cur->bc_private.b.ip,
 292                         XFS_ILOG_FBROOT(cur->bc_private.b.whichfork));
 293         XFS_BMBT_TRACE_CURSOR(cur, EXIT);
 294 }
 295
 296 /*
 297  * Log record values from the btree block.
 298  */
 299 void
 300 xfs_bmbt_log_recs(
 301         xfs_btree_cur_t         *cur,
 302         xfs_buf_t               *bp,
 303         int                     rfirst,
 304         int                     rlast)
 305 {
 306         xfs_bmbt_block_t        *block;
 307         int                     first;
 308         int                     last;
 309         xfs_bmbt_rec_t          *rp;
 310         xfs_trans_t             *tp;
 311
 312         XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
 313         XFS_BMBT_TRACE_ARGBII(cur, bp, rfirst, rlast);
 314         ASSERT(bp);
 315         tp = cur->bc_tp;
 316         block = XFS_BUF_TO_BMBT_BLOCK(bp);
 317         rp = XFS_BMAP_REC_DADDR(block, 1, cur);
 318         first = (int)((xfs_caddr_t)&rp[rfirst - 1] - (xfs_caddr_t)block);
 319         last = (int)(((xfs_caddr_t)&rp[rlast] - 1) - (xfs_caddr_t)block);
 320         xfs_trans_log_buf(tp, bp, first, last);
 321         XFS_BMBT_TRACE_CURSOR(cur, EXIT);
 322 }
 323
 324 /*
 325  * Set all the fields in a bmap extent record from the arguments.
 326  */
 327 void
 328 xfs_bmbt_set_allf(
 329         xfs_bmbt_rec_host_t     *r,
 330         xfs_fileoff_t           startoff,
 331         xfs_fsblock_t           startblock,
 332         xfs_filblks_t           blockcount,
 333         xfs_exntst_t            state)
 334 {
 335         int             extent_flag = (state == XFS_EXT_NORM) ? 0 : 1;
 336
 337         ASSERT(state == XFS_EXT_NORM || state == XFS_EXT_UNWRITTEN);
 338         ASSERT((startoff & XFS_MASK64HI(64-BMBT_STARTOFF_BITLEN)) == 0);
 339         ASSERT((blockcount & XFS_MASK64HI(64-BMBT_BLOCKCOUNT_BITLEN)) == 0);
 340
 341 #if XFS_BIG_BLKNOS
 342         ASSERT((startblock & XFS_MASK64HI(64-BMBT_STARTBLOCK_BITLEN)) == 0);
 343
 344         r->l0 = ((xfs_bmbt_rec_base_t)extent_flag << 63) |
 345                 ((xfs_bmbt_rec_base_t)startoff << 9) |
 346                 ((xfs_bmbt_rec_base_t)startblock >> 43);
 347         r->l1 = ((xfs_bmbt_rec_base_t)startblock << 21) |
 348                 ((xfs_bmbt_rec_base_t)blockcount &
 349                 (xfs_bmbt_rec_base_t)XFS_MASK64LO(21));
 350 #else   /* !XFS_BIG_BLKNOS */
 351         if (ISNULLSTARTBLOCK(startblock)) {
 352                 r->l0 = ((xfs_bmbt_rec_base_t)extent_flag << 63) |
 353                         ((xfs_bmbt_rec_base_t)startoff << 9) |
 354                          (xfs_bmbt_rec_base_t)XFS_MASK64LO(9);
 355                 r->l1 = XFS_MASK64HI(11) |
 356                           ((xfs_bmbt_rec_base_t)startblock << 21) |
 357                           ((xfs_bmbt_rec_base_t)blockcount &
 358                            (xfs_bmbt_rec_base_t)XFS_MASK64LO(21));
 359         } else {
 360                 r->l0 = ((xfs_bmbt_rec_base_t)extent_flag << 63) |
 361                         ((xfs_bmbt_rec_base_t)startoff << 9);
 362                 r->l1 = ((xfs_bmbt_rec_base_t)startblock << 21) |
 363                          ((xfs_bmbt_rec_base_t)blockcount &
 364                          (xfs_bmbt_rec_base_t)XFS_MASK64LO(21));
 365         }
 366 #endif  /* XFS_BIG_BLKNOS */
 367 }
 368
 369 /*
 370  * Set all the fields in a bmap extent record from the uncompressed form.
 371  */
 372 void
 373 xfs_bmbt_set_all(
 374         xfs_bmbt_rec_host_t *r,
 375         xfs_bmbt_irec_t *s)
 376 {
 377         xfs_bmbt_set_allf(r, s->br_startoff, s->br_startblock,
 378                              s->br_blockcount, s->br_state);
 379 }
 380
 381
 382 /*
 383  * Set all the fields in a disk format bmap extent record from the arguments.
 384  */
 385 void
 386 xfs_bmbt_disk_set_allf(
 387         xfs_bmbt_rec_t          *r,
 388         xfs_fileoff_t           startoff,
 389         xfs_fsblock_t           startblock,
 390         xfs_filblks_t           blockcount,
 391         xfs_exntst_t            state)
 392 {
 393         int                     extent_flag = (state == XFS_EXT_NORM) ? 0 : 1;
 394
 395         ASSERT(state == XFS_EXT_NORM || state == XFS_EXT_UNWRITTEN);
 396         ASSERT((startoff & XFS_MASK64HI(64-BMBT_STARTOFF_BITLEN)) == 0);
 397         ASSERT((blockcount & XFS_MASK64HI(64-BMBT_BLOCKCOUNT_BITLEN)) == 0);
 398
 399 #if XFS_BIG_BLKNOS
 400         ASSERT((startblock & XFS_MASK64HI(64-BMBT_STARTBLOCK_BITLEN)) == 0);
 401
 402         r->l0 = cpu_to_be64(
 403                 ((xfs_bmbt_rec_base_t)extent_flag << 63) |
 404                  ((xfs_bmbt_rec_base_t)startoff << 9) |
 405                  ((xfs_bmbt_rec_base_t)startblock >> 43));
 406         r->l1 = cpu_to_be64(
 407                 ((xfs_bmbt_rec_base_t)startblock << 21) |
 408                  ((xfs_bmbt_rec_base_t)blockcount &
 409                   (xfs_bmbt_rec_base_t)XFS_MASK64LO(21)));
 410 #else   /* !XFS_BIG_BLKNOS */
 411         if (ISNULLSTARTBLOCK(startblock)) {
 412                 r->l0 = cpu_to_be64(
 413                         ((xfs_bmbt_rec_base_t)extent_flag << 63) |
 414                          ((xfs_bmbt_rec_base_t)startoff << 9) |
 415                           (xfs_bmbt_rec_base_t)XFS_MASK64LO(9));
 416                 r->l1 = cpu_to_be64(XFS_MASK64HI(11) |
 417                           ((xfs_bmbt_rec_base_t)startblock << 21) |
 418                           ((xfs_bmbt_rec_base_t)blockcount &
 419                            (xfs_bmbt_rec_base_t)XFS_MASK64LO(21)));
 420         } else {
 421                 r->l0 = cpu_to_be64(
 422                         ((xfs_bmbt_rec_base_t)extent_flag << 63) |
 423                          ((xfs_bmbt_rec_base_t)startoff << 9));
 424                 r->l1 = cpu_to_be64(
 425                         ((xfs_bmbt_rec_base_t)startblock << 21) |
 426                          ((xfs_bmbt_rec_base_t)blockcount &
 427                           (xfs_bmbt_rec_base_t)XFS_MASK64LO(21)));
 428         }
 429 #endif  /* XFS_BIG_BLKNOS */
 430 }
 431
 432 /*
 433  * Set all the fields in a bmap extent record from the uncompressed form.
 434  */
 435 void
 436 xfs_bmbt_disk_set_all(
 437         xfs_bmbt_rec_t  *r,
 438         xfs_bmbt_irec_t *s)
 439 {
 440         xfs_bmbt_disk_set_allf(r, s->br_startoff, s->br_startblock,
 441                                   s->br_blockcount, s->br_state);
 442 }
 443
 444 /*
 445  * Set the blockcount field in a bmap extent record.
 446  */
 447 void
 448 xfs_bmbt_set_blockcount(
 449         xfs_bmbt_rec_host_t *r,
 450         xfs_filblks_t   v)
 451 {
 452         ASSERT((v & XFS_MASK64HI(43)) == 0);
 453         r->l1 = (r->l1 & (xfs_bmbt_rec_base_t)XFS_MASK64HI(43)) |
 454                   (xfs_bmbt_rec_base_t)(v & XFS_MASK64LO(21));
 455 }
 456
 457 /*
 458  * Set the startblock field in a bmap extent record.
 459  */
 460 void
 461 xfs_bmbt_set_startblock(
 462         xfs_bmbt_rec_host_t *r,
 463         xfs_fsblock_t   v)
 464 {
 465 #if XFS_BIG_BLKNOS
 466         ASSERT((v & XFS_MASK64HI(12)) == 0);
 467         r->l0 = (r->l0 & (xfs_bmbt_rec_base_t)XFS_MASK64HI(55)) |
 468                   (xfs_bmbt_rec_base_t)(v >> 43);
 469         r->l1 = (r->l1 & (xfs_bmbt_rec_base_t)XFS_MASK64LO(21)) |
 470                   (xfs_bmbt_rec_base_t)(v << 21);
 471 #else   /* !XFS_BIG_BLKNOS */
 472         if (ISNULLSTARTBLOCK(v)) {
 473                 r->l0 |= (xfs_bmbt_rec_base_t)XFS_MASK64LO(9);
 474                 r->l1 = (xfs_bmbt_rec_base_t)XFS_MASK64HI(11) |
 475                           ((xfs_bmbt_rec_base_t)v << 21) |
 476                           (r->l1 & (xfs_bmbt_rec_base_t)XFS_MASK64LO(21));
 477         } else {
 478                 r->l0 &= ~(xfs_bmbt_rec_base_t)XFS_MASK64LO(9);
 479                 r->l1 = ((xfs_bmbt_rec_base_t)v << 21) |
 480                           (r->l1 & (xfs_bmbt_rec_base_t)XFS_MASK64LO(21));
 481         }
 482 #endif  /* XFS_BIG_BLKNOS */
 483 }
 484
 485 /*
 486  * Set the startoff field in a bmap extent record.
 487  */
 488 void
 489 xfs_bmbt_set_startoff(
 490         xfs_bmbt_rec_host_t *r,
 491         xfs_fileoff_t   v)
 492 {
 493         ASSERT((v & XFS_MASK64HI(9)) == 0);
 494         r->l0 = (r->l0 & (xfs_bmbt_rec_base_t) XFS_MASK64HI(1)) |
 495                 ((xfs_bmbt_rec_base_t)v << 9) |
 496                   (r->l0 & (xfs_bmbt_rec_base_t)XFS_MASK64LO(9));
 497 }
 498
 499 /*
 500  * Set the extent state field in a bmap extent record.
 501  */
 502 void
 503 xfs_bmbt_set_state(
 504         xfs_bmbt_rec_host_t *r,
 505         xfs_exntst_t    v)
 506 {
 507         ASSERT(v == XFS_EXT_NORM || v == XFS_EXT_UNWRITTEN);
 508         if (v == XFS_EXT_NORM)
 509                 r->l0 &= XFS_MASK64LO(64 - BMBT_EXNTFLAG_BITLEN);
 510         else
 511                 r->l0 |= XFS_MASK64HI(BMBT_EXNTFLAG_BITLEN);
 512 }
 513
 514 /*
 515  * Convert in-memory form of btree root to on-disk form.
 516  */
 517 void
 518 xfs_bmbt_to_bmdr(
 519         xfs_bmbt_block_t        *rblock,
 520         int                     rblocklen,
 521         xfs_bmdr_block_t        *dblock,
 522         int                     dblocklen)
 523 {
 524         int                     dmxr;
 525         xfs_bmbt_key_t          *fkp;
 526         __be64                  *fpp;
 527         xfs_bmbt_key_t          *tkp;
 528         __be64                  *tpp;
 529
 530         ASSERT(be32_to_cpu(rblock->bb_magic) == XFS_BMAP_MAGIC);
 531         ASSERT(be64_to_cpu(rblock->bb_leftsib) == NULLDFSBNO);
 532         ASSERT(be64_to_cpu(rblock->bb_rightsib) == NULLDFSBNO);
 533         ASSERT(be16_to_cpu(rblock->bb_level) > 0);
 534         dblock->bb_level = rblock->bb_level;
 535         dblock->bb_numrecs = rblock->bb_numrecs;
 536         dmxr = (int)XFS_BTREE_BLOCK_MAXRECS(dblocklen, xfs_bmdr, 0);
 537         fkp = XFS_BMAP_BROOT_KEY_ADDR(rblock, 1, rblocklen);
 538         tkp = XFS_BTREE_KEY_ADDR(xfs_bmdr, dblock, 1);
 539         fpp = XFS_BMAP_BROOT_PTR_ADDR(rblock, 1, rblocklen);
 540         tpp = XFS_BTREE_PTR_ADDR(xfs_bmdr, dblock, 1, dmxr);
 541         dmxr = be16_to_cpu(dblock->bb_numrecs);
 542         memcpy(tkp, fkp, sizeof(*fkp) * dmxr);
 543         memcpy(tpp, fpp, sizeof(*fpp) * dmxr);
 544 }
 545
 546 /*
 547  * Check extent records, which have just been read, for
 548  * any bit in the extent flag field. ASSERT on debug
 549  * kernels, as this condition should not occur.
 550  * Return an error condition (1) if any flags found,
 551  * otherwise return 0.
 552  */
 553
 554 int
 555 xfs_check_nostate_extents(
 556         xfs_ifork_t             *ifp,
 557         xfs_extnum_t            idx,
 558         xfs_extnum_t            num)
 559 {
 560         for (; num > 0; num--, idx++) {
 561                 xfs_bmbt_rec_host_t *ep = xfs_iext_get_ext(ifp, idx);
 562                 if ((ep->l0 >>
 563                      (64 - BMBT_EXNTFLAG_BITLEN)) != 0) {
 564                         ASSERT(0);
 565                         return 1;
 566                 }
 567         }
 568         return 0;
 569 }
 570
 571
 572 STATIC struct xfs_btree_cur *
 573 xfs_bmbt_dup_cursor(
 574         struct xfs_btree_cur    *cur)
 575 {
 576         struct xfs_btree_cur    *new;
 577
 578         new = xfs_bmbt_init_cursor(cur->bc_mp, cur->bc_tp,
 579                         cur->bc_private.b.ip, cur->bc_private.b.whichfork);
 580
 581         /*
 582          * Copy the firstblock, flist, and flags values,
 583          * since init cursor doesn't get them.
 584          */
 585         new->bc_private.b.firstblock = cur->bc_private.b.firstblock;
 586         new->bc_private.b.flist = cur->bc_private.b.flist;
 587         new->bc_private.b.flags = cur->bc_private.b.flags;
 588
 589         return new;
 590 }
 591
 592 STATIC void
 593 xfs_bmbt_update_cursor(
 594         struct xfs_btree_cur    *src,
 595         struct xfs_btree_cur    *dst)
 596 {
 597         ASSERT((dst->bc_private.b.firstblock != NULLFSBLOCK) ||
 598                (dst->bc_private.b.ip->i_d.di_flags & XFS_DIFLAG_REALTIME));
 599         ASSERT(dst->bc_private.b.flist == src->bc_private.b.flist);
 600
 601         dst->bc_private.b.allocated += src->bc_private.b.allocated;
 602         dst->bc_private.b.firstblock = src->bc_private.b.firstblock;
 603
 604         src->bc_private.b.allocated = 0;
 605 }
 606
 607 STATIC int
 608 xfs_bmbt_alloc_block(
 609         struct xfs_btree_cur    *cur,
 610         union xfs_btree_ptr     *start,
 611         union xfs_btree_ptr     *new,
 612         int                     length,
 613         int                     *stat)
 614 {
 615         xfs_alloc_arg_t         args;           /* block allocation args */
 616         int                     error;          /* error return value */
 617
 618         memset(&args, 0, sizeof(args));
 619         args.tp = cur->bc_tp;
 620         args.mp = cur->bc_mp;
 621         args.fsbno = cur->bc_private.b.firstblock;
 622         args.firstblock = args.fsbno;
 623
 624         if (args.fsbno == NULLFSBLOCK) {
 625                 args.fsbno = be64_to_cpu(start->l);
 626                 args.type = XFS_ALLOCTYPE_START_BNO;
 627                 /*
 628                  * Make sure there is sufficient room left in the AG to
 629                  * complete a full tree split for an extent insert.  If
 630                  * we are converting the middle part of an extent then
 631                  * we may need space for two tree splits.
 632                  *
 633                  * We are relying on the caller to make the correct block
 634                  * reservation for this operation to succeed.  If the
 635                  * reservation amount is insufficient then we may fail a
 636                  * block allocation here and corrupt the filesystem.
 637                  */
 638                 args.minleft = xfs_trans_get_block_res(args.tp);
 639         } else if (cur->bc_private.b.flist->xbf_low) {
 640                 args.type = XFS_ALLOCTYPE_START_BNO;
 641         } else {
 642                 args.type = XFS_ALLOCTYPE_NEAR_BNO;
 643         }
 644
 645         args.minlen = args.maxlen = args.prod = 1;
 646         args.wasdel = cur->bc_private.b.flags & XFS_BTCUR_BPRV_WASDEL;
 647         if (!args.wasdel && xfs_trans_get_block_res(args.tp) == 0) {
 648                 error = XFS_ERROR(ENOSPC);
 649                 goto error0;
 650         }
 651         error = xfs_alloc_vextent(&args);
 652         if (error)
 653                 goto error0;
 654
 655         if (args.fsbno == NULLFSBLOCK && args.minleft) {
 656                 /*
 657                  * Could not find an AG with enough free space to satisfy
 658                  * a full btree split.  Try again without minleft and if
 659                  * successful activate the lowspace algorithm.
 660                  */
 661                 args.fsbno = 0;
 662                 args.type = XFS_ALLOCTYPE_FIRST_AG;
 663                 args.minleft = 0;
 664                 error = xfs_alloc_vextent(&args);
 665                 if (error)
 666                         goto error0;
 667                 cur->bc_private.b.flist->xbf_low = 1;
 668         }
 669         if (args.fsbno == NULLFSBLOCK) {
 670                 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
 671                 *stat = 0;
 672                 return 0;
 673         }
 674         ASSERT(args.len == 1);
 675         cur->bc_private.b.firstblock = args.fsbno;
 676         cur->bc_private.b.allocated++;
 677         cur->bc_private.b.ip->i_d.di_nblocks++;
 678         xfs_trans_log_inode(args.tp, cur->bc_private.b.ip, XFS_ILOG_CORE);
 679         XFS_TRANS_MOD_DQUOT_BYINO(args.mp, args.tp, cur->bc_private.b.ip,
 680                         XFS_TRANS_DQ_BCOUNT, 1L);
 681
 682         new->l = cpu_to_be64(args.fsbno);
 683
 684         XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
 685         *stat = 1;
 686         return 0;
 687
 688  error0:
 689         XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR);
 690         return error;
 691 }
 692
 693 STATIC int
 694 xfs_bmbt_free_block(
 695         struct xfs_btree_cur    *cur,
 696         struct xfs_buf          *bp)
 697 {
 698         struct xfs_mount        *mp = cur->bc_mp;
 699         struct xfs_inode        *ip = cur->bc_private.b.ip;
 700         struct xfs_trans        *tp = cur->bc_tp;
 701         xfs_fsblock_t           fsbno = XFS_DADDR_TO_FSB(mp, XFS_BUF_ADDR(bp));
 702
 703         xfs_bmap_add_free(fsbno, 1, cur->bc_private.b.flist, mp);
 704         ip->i_d.di_nblocks--;
 705
 706         xfs_trans_log_inode(tp, ip, XFS_ILOG_CORE);
 707         XFS_TRANS_MOD_DQUOT_BYINO(mp, tp, ip, XFS_TRANS_DQ_BCOUNT, -1L);
 708         xfs_trans_binval(tp, bp);
 709         return 0;
 710 }
 711
 712 STATIC int
 713 xfs_bmbt_get_minrecs(
 714         struct xfs_btree_cur    *cur,
 715         int                     level)
 716 {
 717         return XFS_BMAP_BLOCK_IMINRECS(level, cur);
 718 }
 719
 720 STATIC int
 721 xfs_bmbt_get_maxrecs(
 722         struct xfs_btree_cur    *cur,
 723         int                     level)
 724 {
 725         return XFS_BMAP_BLOCK_IMAXRECS(level, cur);
 726 }
 727
 728 /*
 729  * Get the maximum records we could store in the on-disk format.
 730  *
 731  * For non-root nodes this is equivalent to xfs_bmbt_get_maxrecs, but
 732  * for the root node this checks the available space in the dinode fork
 733  * so that we can resize the in-memory buffer to match it.  After a
 734  * resize to the maximum size this function returns the same value
 735  * as xfs_bmbt_get_maxrecs for the root node, too.
 736  */
 737 STATIC int
 738 xfs_bmbt_get_dmaxrecs(
 739         struct xfs_btree_cur    *cur,
 740         int                     level)
 741 {
 742         return XFS_BMAP_BLOCK_DMAXRECS(level, cur);
 743 }
 744
 745 STATIC void
 746 xfs_bmbt_init_key_from_rec(
 747         union xfs_btree_key     *key,
 748         union xfs_btree_rec     *rec)
 749 {
 750         key->bmbt.br_startoff =
 751                 cpu_to_be64(xfs_bmbt_disk_get_startoff(&rec->bmbt));
 752 }
 753
 754 STATIC void
 755 xfs_bmbt_init_rec_from_key(
 756         union xfs_btree_key     *key,
 757         union xfs_btree_rec     *rec)
 758 {
 759         ASSERT(key->bmbt.br_startoff != 0);
 760
 761         xfs_bmbt_disk_set_allf(&rec->bmbt, be64_to_cpu(key->bmbt.br_startoff),
 762                                0, 0, XFS_EXT_NORM);
 763 }
 764
 765 STATIC void
 766 xfs_bmbt_init_rec_from_cur(
 767         struct xfs_btree_cur    *cur,
 768         union xfs_btree_rec     *rec)
 769 {
 770         xfs_bmbt_disk_set_all(&rec->bmbt, &cur->bc_rec.b);
 771 }
 772
 773 STATIC void
 774 xfs_bmbt_init_ptr_from_cur(
 775         struct xfs_btree_cur    *cur,
 776         union xfs_btree_ptr     *ptr)
 777 {
 778         ptr->l = 0;
 779 }
 780
 781 STATIC __int64_t
 782 xfs_bmbt_key_diff(
 783         struct xfs_btree_cur    *cur,
 784         union xfs_btree_key     *key)
 785 {
 786         return (__int64_t)be64_to_cpu(key->bmbt.br_startoff) -
 787                                       cur->bc_rec.b.br_startoff;
 788 }
 789
 790 #ifdef XFS_BTREE_TRACE
 791 ktrace_t        *xfs_bmbt_trace_buf;
 792
 793 STATIC void
 794 xfs_bmbt_trace_enter(
 795         struct xfs_btree_cur    *cur,
 796         const char              *func,
 797         char                    *s,
 798         int                     type,
 799         int                     line,
 800         __psunsigned_t          a0,
 801         __psunsigned_t          a1,
 802         __psunsigned_t          a2,
 803         __psunsigned_t          a3,
 804         __psunsigned_t          a4,
 805         __psunsigned_t          a5,
 806         __psunsigned_t          a6,
 807         __psunsigned_t          a7,
 808         __psunsigned_t          a8,
 809         __psunsigned_t          a9,
 810         __psunsigned_t          a10)
 811 {
 812         struct xfs_inode        *ip = cur->bc_private.b.ip;
 813         int                     whichfork = cur->bc_private.b.whichfork;
 814
 815         ktrace_enter(xfs_bmbt_trace_buf,
 816                 (void *)((__psint_t)type | (whichfork << 8) | (line << 16)),
 817                 (void *)func, (void *)s, (void *)ip, (void *)cur,
 818                 (void *)a0, (void *)a1, (void *)a2, (void *)a3,
 819                 (void *)a4, (void *)a5, (void *)a6, (void *)a7,
 820                 (void *)a8, (void *)a9, (void *)a10);
 821         ktrace_enter(ip->i_btrace,
 822                 (void *)((__psint_t)type | (whichfork << 8) | (line << 16)),
 823                 (void *)func, (void *)s, (void *)ip, (void *)cur,
 824                 (void *)a0, (void *)a1, (void *)a2, (void *)a3,
 825                 (void *)a4, (void *)a5, (void *)a6, (void *)a7,
 826                 (void *)a8, (void *)a9, (void *)a10);
 827 }
 828
 829 STATIC void
 830 xfs_bmbt_trace_cursor(
 831         struct xfs_btree_cur    *cur,
 832         __uint32_t              *s0,
 833         __uint64_t              *l0,
 834         __uint64_t              *l1)
 835 {
 836         struct xfs_bmbt_rec_host r;
 837
 838         xfs_bmbt_set_all(&r, &cur->bc_rec.b);
 839
 840         *s0 = (cur->bc_nlevels << 24) |
 841               (cur->bc_private.b.flags << 16) |
 842                cur->bc_private.b.allocated;
 843         *l0 = r.l0;
 844         *l1 = r.l1;
 845 }
 846
 847 STATIC void
 848 xfs_bmbt_trace_key(
 849         struct xfs_btree_cur    *cur,
 850         union xfs_btree_key     *key,
 851         __uint64_t              *l0,
 852         __uint64_t              *l1)
 853 {
 854         *l0 = be64_to_cpu(key->bmbt.br_startoff);
 855         *l1 = 0;
 856 }
 857
 858 STATIC void
 859 xfs_bmbt_trace_record(
 860         struct xfs_btree_cur    *cur,
 861         union xfs_btree_rec     *rec,
 862         __uint64_t              *l0,
 863         __uint64_t              *l1,
 864         __uint64_t              *l2)
 865 {
 866         struct xfs_bmbt_irec    irec;
 867
 868         xfs_bmbt_disk_get_all(&rec->bmbt, &irec);
 869         *l0 = irec.br_startoff;
 870         *l1 = irec.br_startblock;
 871         *l2 = irec.br_blockcount;
 872 }
 873 #endif /* XFS_BTREE_TRACE */
 874
 875 static const struct xfs_btree_ops xfs_bmbt_ops = {
 876         .rec_len                = sizeof(xfs_bmbt_rec_t),
 877         .key_len                = sizeof(xfs_bmbt_key_t),
 878
 879         .dup_cursor             = xfs_bmbt_dup_cursor,
 880         .update_cursor          = xfs_bmbt_update_cursor,
 881         .alloc_block            = xfs_bmbt_alloc_block,
 882         .free_block             = xfs_bmbt_free_block,
 883         .get_maxrecs            = xfs_bmbt_get_maxrecs,
 884         .get_minrecs            = xfs_bmbt_get_minrecs,
 885         .get_dmaxrecs           = xfs_bmbt_get_dmaxrecs,
 886         .init_key_from_rec      = xfs_bmbt_init_key_from_rec,
 887         .init_rec_from_key      = xfs_bmbt_init_rec_from_key,
 888         .init_rec_from_cur      = xfs_bmbt_init_rec_from_cur,
 889         .init_ptr_from_cur      = xfs_bmbt_init_ptr_from_cur,
 890         .key_diff               = xfs_bmbt_key_diff,
 891
 892 #ifdef XFS_BTREE_TRACE
 893         .trace_enter            = xfs_bmbt_trace_enter,
 894         .trace_cursor           = xfs_bmbt_trace_cursor,
 895         .trace_key              = xfs_bmbt_trace_key,
 896         .trace_record           = xfs_bmbt_trace_record,
 897 #endif
 898 };
 899
 900 /*
 901  * Allocate a new bmap btree cursor.
 902  */
 903 struct xfs_btree_cur *                          /* new bmap btree cursor */
 904 xfs_bmbt_init_cursor(
 905         struct xfs_mount        *mp,            /* file system mount point */
 906         struct xfs_trans        *tp,            /* transaction pointer */
 907         struct xfs_inode        *ip,            /* inode owning the btree */
 908         int                     whichfork)      /* data or attr fork */
 909 {
 910         struct xfs_ifork        *ifp = XFS_IFORK_PTR(ip, whichfork);
 911         struct xfs_btree_cur    *cur;
 912
 913         cur = kmem_zone_zalloc(xfs_btree_cur_zone, KM_SLEEP);
 914
 915         cur->bc_tp = tp;
 916         cur->bc_mp = mp;
 917         cur->bc_nlevels = be16_to_cpu(ifp->if_broot->bb_level) + 1;
 918         cur->bc_btnum = XFS_BTNUM_BMAP;
 919         cur->bc_blocklog = mp->m_sb.sb_blocklog;
 920
 921         cur->bc_ops = &xfs_bmbt_ops;
 922         cur->bc_flags = XFS_BTREE_LONG_PTRS | XFS_BTREE_ROOT_IN_INODE;
 923
 924         cur->bc_private.b.forksize = XFS_IFORK_SIZE(ip, whichfork);
 925         cur->bc_private.b.ip = ip;
 926         cur->bc_private.b.firstblock = NULLFSBLOCK;
 927         cur->bc_private.b.flist = NULL;
 928         cur->bc_private.b.allocated = 0;
 929         cur->bc_private.b.flags = 0;
 930         cur->bc_private.b.whichfork = whichfork;
 931
 932         return cur;
 933 }