linux/fs/xfs/xfs_bmap_btree.c
<<
>>
Prefs
   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_trans.h"
  24#include "xfs_sb.h"
  25#include "xfs_ag.h"
  26#include "xfs_mount.h"
  27#include "xfs_bmap_btree.h"
  28#include "xfs_alloc_btree.h"
  29#include "xfs_ialloc_btree.h"
  30#include "xfs_dinode.h"
  31#include "xfs_inode.h"
  32#include "xfs_inode_item.h"
  33#include "xfs_alloc.h"
  34#include "xfs_btree.h"
  35#include "xfs_itable.h"
  36#include "xfs_bmap.h"
  37#include "xfs_error.h"
  38#include "xfs_quota.h"
  39#include "xfs_trace.h"
  40
  41/*
  42 * Determine the extent state.
  43 */
  44/* ARGSUSED */
  45STATIC xfs_exntst_t
  46xfs_extent_state(
  47        xfs_filblks_t           blks,
  48        int                     extent_flag)
  49{
  50        if (extent_flag) {
  51                ASSERT(blks != 0);      /* saved for DMIG */
  52                return XFS_EXT_UNWRITTEN;
  53        }
  54        return XFS_EXT_NORM;
  55}
  56
  57/*
  58 * Convert on-disk form of btree root to in-memory form.
  59 */
  60void
  61xfs_bmdr_to_bmbt(
  62        struct xfs_mount        *mp,
  63        xfs_bmdr_block_t        *dblock,
  64        int                     dblocklen,
  65        struct xfs_btree_block  *rblock,
  66        int                     rblocklen)
  67{
  68        int                     dmxr;
  69        xfs_bmbt_key_t          *fkp;
  70        __be64                  *fpp;
  71        xfs_bmbt_key_t          *tkp;
  72        __be64                  *tpp;
  73
  74        rblock->bb_magic = cpu_to_be32(XFS_BMAP_MAGIC);
  75        rblock->bb_level = dblock->bb_level;
  76        ASSERT(be16_to_cpu(rblock->bb_level) > 0);
  77        rblock->bb_numrecs = dblock->bb_numrecs;
  78        rblock->bb_u.l.bb_leftsib = cpu_to_be64(NULLDFSBNO);
  79        rblock->bb_u.l.bb_rightsib = cpu_to_be64(NULLDFSBNO);
  80        dmxr = xfs_bmdr_maxrecs(mp, dblocklen, 0);
  81        fkp = XFS_BMDR_KEY_ADDR(dblock, 1);
  82        tkp = XFS_BMBT_KEY_ADDR(mp, rblock, 1);
  83        fpp = XFS_BMDR_PTR_ADDR(dblock, 1, dmxr);
  84        tpp = XFS_BMAP_BROOT_PTR_ADDR(mp, rblock, 1, rblocklen);
  85        dmxr = be16_to_cpu(dblock->bb_numrecs);
  86        memcpy(tkp, fkp, sizeof(*fkp) * dmxr);
  87        memcpy(tpp, fpp, sizeof(*fpp) * dmxr);
  88}
  89
  90/*
  91 * Convert a compressed bmap extent record to an uncompressed form.
  92 * This code must be in sync with the routines xfs_bmbt_get_startoff,
  93 * xfs_bmbt_get_startblock, xfs_bmbt_get_blockcount and xfs_bmbt_get_state.
  94 */
  95STATIC void
  96__xfs_bmbt_get_all(
  97                __uint64_t l0,
  98                __uint64_t l1,
  99                xfs_bmbt_irec_t *s)
 100{
 101        int     ext_flag;
 102        xfs_exntst_t st;
 103
 104        ext_flag = (int)(l0 >> (64 - BMBT_EXNTFLAG_BITLEN));
 105        s->br_startoff = ((xfs_fileoff_t)l0 &
 106                           xfs_mask64lo(64 - BMBT_EXNTFLAG_BITLEN)) >> 9;
 107#if XFS_BIG_BLKNOS
 108        s->br_startblock = (((xfs_fsblock_t)l0 & xfs_mask64lo(9)) << 43) |
 109                           (((xfs_fsblock_t)l1) >> 21);
 110#else
 111#ifdef DEBUG
 112        {
 113                xfs_dfsbno_t    b;
 114
 115                b = (((xfs_dfsbno_t)l0 & xfs_mask64lo(9)) << 43) |
 116                    (((xfs_dfsbno_t)l1) >> 21);
 117                ASSERT((b >> 32) == 0 || isnulldstartblock(b));
 118                s->br_startblock = (xfs_fsblock_t)b;
 119        }
 120#else   /* !DEBUG */
 121        s->br_startblock = (xfs_fsblock_t)(((xfs_dfsbno_t)l1) >> 21);
 122#endif  /* DEBUG */
 123#endif  /* XFS_BIG_BLKNOS */
 124        s->br_blockcount = (xfs_filblks_t)(l1 & xfs_mask64lo(21));
 125        /* This is xfs_extent_state() in-line */
 126        if (ext_flag) {
 127                ASSERT(s->br_blockcount != 0);  /* saved for DMIG */
 128                st = XFS_EXT_UNWRITTEN;
 129        } else
 130                st = XFS_EXT_NORM;
 131        s->br_state = st;
 132}
 133
 134void
 135xfs_bmbt_get_all(
 136        xfs_bmbt_rec_host_t *r,
 137        xfs_bmbt_irec_t *s)
 138{
 139        __xfs_bmbt_get_all(r->l0, r->l1, s);
 140}
 141
 142/*
 143 * Extract the blockcount field from an in memory bmap extent record.
 144 */
 145xfs_filblks_t
 146xfs_bmbt_get_blockcount(
 147        xfs_bmbt_rec_host_t     *r)
 148{
 149        return (xfs_filblks_t)(r->l1 & xfs_mask64lo(21));
 150}
 151
 152/*
 153 * Extract the startblock field from an in memory bmap extent record.
 154 */
 155xfs_fsblock_t
 156xfs_bmbt_get_startblock(
 157        xfs_bmbt_rec_host_t     *r)
 158{
 159#if XFS_BIG_BLKNOS
 160        return (((xfs_fsblock_t)r->l0 & xfs_mask64lo(9)) << 43) |
 161               (((xfs_fsblock_t)r->l1) >> 21);
 162#else
 163#ifdef DEBUG
 164        xfs_dfsbno_t    b;
 165
 166        b = (((xfs_dfsbno_t)r->l0 & xfs_mask64lo(9)) << 43) |
 167            (((xfs_dfsbno_t)r->l1) >> 21);
 168        ASSERT((b >> 32) == 0 || isnulldstartblock(b));
 169        return (xfs_fsblock_t)b;
 170#else   /* !DEBUG */
 171        return (xfs_fsblock_t)(((xfs_dfsbno_t)r->l1) >> 21);
 172#endif  /* DEBUG */
 173#endif  /* XFS_BIG_BLKNOS */
 174}
 175
 176/*
 177 * Extract the startoff field from an in memory bmap extent record.
 178 */
 179xfs_fileoff_t
 180xfs_bmbt_get_startoff(
 181        xfs_bmbt_rec_host_t     *r)
 182{
 183        return ((xfs_fileoff_t)r->l0 &
 184                 xfs_mask64lo(64 - BMBT_EXNTFLAG_BITLEN)) >> 9;
 185}
 186
 187xfs_exntst_t
 188xfs_bmbt_get_state(
 189        xfs_bmbt_rec_host_t     *r)
 190{
 191        int     ext_flag;
 192
 193        ext_flag = (int)((r->l0) >> (64 - BMBT_EXNTFLAG_BITLEN));
 194        return xfs_extent_state(xfs_bmbt_get_blockcount(r),
 195                                ext_flag);
 196}
 197
 198/*
 199 * Extract the blockcount field from an on disk bmap extent record.
 200 */
 201xfs_filblks_t
 202xfs_bmbt_disk_get_blockcount(
 203        xfs_bmbt_rec_t  *r)
 204{
 205        return (xfs_filblks_t)(be64_to_cpu(r->l1) & xfs_mask64lo(21));
 206}
 207
 208/*
 209 * Extract the startoff field from a disk format bmap extent record.
 210 */
 211xfs_fileoff_t
 212xfs_bmbt_disk_get_startoff(
 213        xfs_bmbt_rec_t  *r)
 214{
 215        return ((xfs_fileoff_t)be64_to_cpu(r->l0) &
 216                 xfs_mask64lo(64 - BMBT_EXNTFLAG_BITLEN)) >> 9;
 217}
 218
 219
 220/*
 221 * Set all the fields in a bmap extent record from the arguments.
 222 */
 223void
 224xfs_bmbt_set_allf(
 225        xfs_bmbt_rec_host_t     *r,
 226        xfs_fileoff_t           startoff,
 227        xfs_fsblock_t           startblock,
 228        xfs_filblks_t           blockcount,
 229        xfs_exntst_t            state)
 230{
 231        int             extent_flag = (state == XFS_EXT_NORM) ? 0 : 1;
 232
 233        ASSERT(state == XFS_EXT_NORM || state == XFS_EXT_UNWRITTEN);
 234        ASSERT((startoff & xfs_mask64hi(64-BMBT_STARTOFF_BITLEN)) == 0);
 235        ASSERT((blockcount & xfs_mask64hi(64-BMBT_BLOCKCOUNT_BITLEN)) == 0);
 236
 237#if XFS_BIG_BLKNOS
 238        ASSERT((startblock & xfs_mask64hi(64-BMBT_STARTBLOCK_BITLEN)) == 0);
 239
 240        r->l0 = ((xfs_bmbt_rec_base_t)extent_flag << 63) |
 241                ((xfs_bmbt_rec_base_t)startoff << 9) |
 242                ((xfs_bmbt_rec_base_t)startblock >> 43);
 243        r->l1 = ((xfs_bmbt_rec_base_t)startblock << 21) |
 244                ((xfs_bmbt_rec_base_t)blockcount &
 245                (xfs_bmbt_rec_base_t)xfs_mask64lo(21));
 246#else   /* !XFS_BIG_BLKNOS */
 247        if (isnullstartblock(startblock)) {
 248                r->l0 = ((xfs_bmbt_rec_base_t)extent_flag << 63) |
 249                        ((xfs_bmbt_rec_base_t)startoff << 9) |
 250                         (xfs_bmbt_rec_base_t)xfs_mask64lo(9);
 251                r->l1 = xfs_mask64hi(11) |
 252                          ((xfs_bmbt_rec_base_t)startblock << 21) |
 253                          ((xfs_bmbt_rec_base_t)blockcount &
 254                           (xfs_bmbt_rec_base_t)xfs_mask64lo(21));
 255        } else {
 256                r->l0 = ((xfs_bmbt_rec_base_t)extent_flag << 63) |
 257                        ((xfs_bmbt_rec_base_t)startoff << 9);
 258                r->l1 = ((xfs_bmbt_rec_base_t)startblock << 21) |
 259                         ((xfs_bmbt_rec_base_t)blockcount &
 260                         (xfs_bmbt_rec_base_t)xfs_mask64lo(21));
 261        }
 262#endif  /* XFS_BIG_BLKNOS */
 263}
 264
 265/*
 266 * Set all the fields in a bmap extent record from the uncompressed form.
 267 */
 268void
 269xfs_bmbt_set_all(
 270        xfs_bmbt_rec_host_t *r,
 271        xfs_bmbt_irec_t *s)
 272{
 273        xfs_bmbt_set_allf(r, s->br_startoff, s->br_startblock,
 274                             s->br_blockcount, s->br_state);
 275}
 276
 277
 278/*
 279 * Set all the fields in a disk format bmap extent record from the arguments.
 280 */
 281void
 282xfs_bmbt_disk_set_allf(
 283        xfs_bmbt_rec_t          *r,
 284        xfs_fileoff_t           startoff,
 285        xfs_fsblock_t           startblock,
 286        xfs_filblks_t           blockcount,
 287        xfs_exntst_t            state)
 288{
 289        int                     extent_flag = (state == XFS_EXT_NORM) ? 0 : 1;
 290
 291        ASSERT(state == XFS_EXT_NORM || state == XFS_EXT_UNWRITTEN);
 292        ASSERT((startoff & xfs_mask64hi(64-BMBT_STARTOFF_BITLEN)) == 0);
 293        ASSERT((blockcount & xfs_mask64hi(64-BMBT_BLOCKCOUNT_BITLEN)) == 0);
 294
 295#if XFS_BIG_BLKNOS
 296        ASSERT((startblock & xfs_mask64hi(64-BMBT_STARTBLOCK_BITLEN)) == 0);
 297
 298        r->l0 = cpu_to_be64(
 299                ((xfs_bmbt_rec_base_t)extent_flag << 63) |
 300                 ((xfs_bmbt_rec_base_t)startoff << 9) |
 301                 ((xfs_bmbt_rec_base_t)startblock >> 43));
 302        r->l1 = cpu_to_be64(
 303                ((xfs_bmbt_rec_base_t)startblock << 21) |
 304                 ((xfs_bmbt_rec_base_t)blockcount &
 305                  (xfs_bmbt_rec_base_t)xfs_mask64lo(21)));
 306#else   /* !XFS_BIG_BLKNOS */
 307        if (isnullstartblock(startblock)) {
 308                r->l0 = cpu_to_be64(
 309                        ((xfs_bmbt_rec_base_t)extent_flag << 63) |
 310                         ((xfs_bmbt_rec_base_t)startoff << 9) |
 311                          (xfs_bmbt_rec_base_t)xfs_mask64lo(9));
 312                r->l1 = cpu_to_be64(xfs_mask64hi(11) |
 313                          ((xfs_bmbt_rec_base_t)startblock << 21) |
 314                          ((xfs_bmbt_rec_base_t)blockcount &
 315                           (xfs_bmbt_rec_base_t)xfs_mask64lo(21)));
 316        } else {
 317                r->l0 = cpu_to_be64(
 318                        ((xfs_bmbt_rec_base_t)extent_flag << 63) |
 319                         ((xfs_bmbt_rec_base_t)startoff << 9));
 320                r->l1 = cpu_to_be64(
 321                        ((xfs_bmbt_rec_base_t)startblock << 21) |
 322                         ((xfs_bmbt_rec_base_t)blockcount &
 323                          (xfs_bmbt_rec_base_t)xfs_mask64lo(21)));
 324        }
 325#endif  /* XFS_BIG_BLKNOS */
 326}
 327
 328/*
 329 * Set all the fields in a bmap extent record from the uncompressed form.
 330 */
 331STATIC void
 332xfs_bmbt_disk_set_all(
 333        xfs_bmbt_rec_t  *r,
 334        xfs_bmbt_irec_t *s)
 335{
 336        xfs_bmbt_disk_set_allf(r, s->br_startoff, s->br_startblock,
 337                                  s->br_blockcount, s->br_state);
 338}
 339
 340/*
 341 * Set the blockcount field in a bmap extent record.
 342 */
 343void
 344xfs_bmbt_set_blockcount(
 345        xfs_bmbt_rec_host_t *r,
 346        xfs_filblks_t   v)
 347{
 348        ASSERT((v & xfs_mask64hi(43)) == 0);
 349        r->l1 = (r->l1 & (xfs_bmbt_rec_base_t)xfs_mask64hi(43)) |
 350                  (xfs_bmbt_rec_base_t)(v & xfs_mask64lo(21));
 351}
 352
 353/*
 354 * Set the startblock field in a bmap extent record.
 355 */
 356void
 357xfs_bmbt_set_startblock(
 358        xfs_bmbt_rec_host_t *r,
 359        xfs_fsblock_t   v)
 360{
 361#if XFS_BIG_BLKNOS
 362        ASSERT((v & xfs_mask64hi(12)) == 0);
 363        r->l0 = (r->l0 & (xfs_bmbt_rec_base_t)xfs_mask64hi(55)) |
 364                  (xfs_bmbt_rec_base_t)(v >> 43);
 365        r->l1 = (r->l1 & (xfs_bmbt_rec_base_t)xfs_mask64lo(21)) |
 366                  (xfs_bmbt_rec_base_t)(v << 21);
 367#else   /* !XFS_BIG_BLKNOS */
 368        if (isnullstartblock(v)) {
 369                r->l0 |= (xfs_bmbt_rec_base_t)xfs_mask64lo(9);
 370                r->l1 = (xfs_bmbt_rec_base_t)xfs_mask64hi(11) |
 371                          ((xfs_bmbt_rec_base_t)v << 21) |
 372                          (r->l1 & (xfs_bmbt_rec_base_t)xfs_mask64lo(21));
 373        } else {
 374                r->l0 &= ~(xfs_bmbt_rec_base_t)xfs_mask64lo(9);
 375                r->l1 = ((xfs_bmbt_rec_base_t)v << 21) |
 376                          (r->l1 & (xfs_bmbt_rec_base_t)xfs_mask64lo(21));
 377        }
 378#endif  /* XFS_BIG_BLKNOS */
 379}
 380
 381/*
 382 * Set the startoff field in a bmap extent record.
 383 */
 384void
 385xfs_bmbt_set_startoff(
 386        xfs_bmbt_rec_host_t *r,
 387        xfs_fileoff_t   v)
 388{
 389        ASSERT((v & xfs_mask64hi(9)) == 0);
 390        r->l0 = (r->l0 & (xfs_bmbt_rec_base_t) xfs_mask64hi(1)) |
 391                ((xfs_bmbt_rec_base_t)v << 9) |
 392                  (r->l0 & (xfs_bmbt_rec_base_t)xfs_mask64lo(9));
 393}
 394
 395/*
 396 * Set the extent state field in a bmap extent record.
 397 */
 398void
 399xfs_bmbt_set_state(
 400        xfs_bmbt_rec_host_t *r,
 401        xfs_exntst_t    v)
 402{
 403        ASSERT(v == XFS_EXT_NORM || v == XFS_EXT_UNWRITTEN);
 404        if (v == XFS_EXT_NORM)
 405                r->l0 &= xfs_mask64lo(64 - BMBT_EXNTFLAG_BITLEN);
 406        else
 407                r->l0 |= xfs_mask64hi(BMBT_EXNTFLAG_BITLEN);
 408}
 409
 410/*
 411 * Convert in-memory form of btree root to on-disk form.
 412 */
 413void
 414xfs_bmbt_to_bmdr(
 415        struct xfs_mount        *mp,
 416        struct xfs_btree_block  *rblock,
 417        int                     rblocklen,
 418        xfs_bmdr_block_t        *dblock,
 419        int                     dblocklen)
 420{
 421        int                     dmxr;
 422        xfs_bmbt_key_t          *fkp;
 423        __be64                  *fpp;
 424        xfs_bmbt_key_t          *tkp;
 425        __be64                  *tpp;
 426
 427        ASSERT(rblock->bb_magic == cpu_to_be32(XFS_BMAP_MAGIC));
 428        ASSERT(rblock->bb_u.l.bb_leftsib == cpu_to_be64(NULLDFSBNO));
 429        ASSERT(rblock->bb_u.l.bb_rightsib == cpu_to_be64(NULLDFSBNO));
 430        ASSERT(rblock->bb_level != 0);
 431        dblock->bb_level = rblock->bb_level;
 432        dblock->bb_numrecs = rblock->bb_numrecs;
 433        dmxr = xfs_bmdr_maxrecs(mp, dblocklen, 0);
 434        fkp = XFS_BMBT_KEY_ADDR(mp, rblock, 1);
 435        tkp = XFS_BMDR_KEY_ADDR(dblock, 1);
 436        fpp = XFS_BMAP_BROOT_PTR_ADDR(mp, rblock, 1, rblocklen);
 437        tpp = XFS_BMDR_PTR_ADDR(dblock, 1, dmxr);
 438        dmxr = be16_to_cpu(dblock->bb_numrecs);
 439        memcpy(tkp, fkp, sizeof(*fkp) * dmxr);
 440        memcpy(tpp, fpp, sizeof(*fpp) * dmxr);
 441}
 442
 443/*
 444 * Check extent records, which have just been read, for
 445 * any bit in the extent flag field. ASSERT on debug
 446 * kernels, as this condition should not occur.
 447 * Return an error condition (1) if any flags found,
 448 * otherwise return 0.
 449 */
 450
 451int
 452xfs_check_nostate_extents(
 453        xfs_ifork_t             *ifp,
 454        xfs_extnum_t            idx,
 455        xfs_extnum_t            num)
 456{
 457        for (; num > 0; num--, idx++) {
 458                xfs_bmbt_rec_host_t *ep = xfs_iext_get_ext(ifp, idx);
 459                if ((ep->l0 >>
 460                     (64 - BMBT_EXNTFLAG_BITLEN)) != 0) {
 461                        ASSERT(0);
 462                        return 1;
 463                }
 464        }
 465        return 0;
 466}
 467
 468
 469STATIC struct xfs_btree_cur *
 470xfs_bmbt_dup_cursor(
 471        struct xfs_btree_cur    *cur)
 472{
 473        struct xfs_btree_cur    *new;
 474
 475        new = xfs_bmbt_init_cursor(cur->bc_mp, cur->bc_tp,
 476                        cur->bc_private.b.ip, cur->bc_private.b.whichfork);
 477
 478        /*
 479         * Copy the firstblock, flist, and flags values,
 480         * since init cursor doesn't get them.
 481         */
 482        new->bc_private.b.firstblock = cur->bc_private.b.firstblock;
 483        new->bc_private.b.flist = cur->bc_private.b.flist;
 484        new->bc_private.b.flags = cur->bc_private.b.flags;
 485
 486        return new;
 487}
 488
 489STATIC void
 490xfs_bmbt_update_cursor(
 491        struct xfs_btree_cur    *src,
 492        struct xfs_btree_cur    *dst)
 493{
 494        ASSERT((dst->bc_private.b.firstblock != NULLFSBLOCK) ||
 495               (dst->bc_private.b.ip->i_d.di_flags & XFS_DIFLAG_REALTIME));
 496        ASSERT(dst->bc_private.b.flist == src->bc_private.b.flist);
 497
 498        dst->bc_private.b.allocated += src->bc_private.b.allocated;
 499        dst->bc_private.b.firstblock = src->bc_private.b.firstblock;
 500
 501        src->bc_private.b.allocated = 0;
 502}
 503
 504STATIC int
 505xfs_bmbt_alloc_block(
 506        struct xfs_btree_cur    *cur,
 507        union xfs_btree_ptr     *start,
 508        union xfs_btree_ptr     *new,
 509        int                     length,
 510        int                     *stat)
 511{
 512        xfs_alloc_arg_t         args;           /* block allocation args */
 513        int                     error;          /* error return value */
 514
 515        memset(&args, 0, sizeof(args));
 516        args.tp = cur->bc_tp;
 517        args.mp = cur->bc_mp;
 518        args.fsbno = cur->bc_private.b.firstblock;
 519        args.firstblock = args.fsbno;
 520
 521        if (args.fsbno == NULLFSBLOCK) {
 522                args.fsbno = be64_to_cpu(start->l);
 523                args.type = XFS_ALLOCTYPE_START_BNO;
 524                /*
 525                 * Make sure there is sufficient room left in the AG to
 526                 * complete a full tree split for an extent insert.  If
 527                 * we are converting the middle part of an extent then
 528                 * we may need space for two tree splits.
 529                 *
 530                 * We are relying on the caller to make the correct block
 531                 * reservation for this operation to succeed.  If the
 532                 * reservation amount is insufficient then we may fail a
 533                 * block allocation here and corrupt the filesystem.
 534                 */
 535                args.minleft = xfs_trans_get_block_res(args.tp);
 536        } else if (cur->bc_private.b.flist->xbf_low) {
 537                args.type = XFS_ALLOCTYPE_START_BNO;
 538        } else {
 539                args.type = XFS_ALLOCTYPE_NEAR_BNO;
 540        }
 541
 542        args.minlen = args.maxlen = args.prod = 1;
 543        args.wasdel = cur->bc_private.b.flags & XFS_BTCUR_BPRV_WASDEL;
 544        if (!args.wasdel && xfs_trans_get_block_res(args.tp) == 0) {
 545                error = XFS_ERROR(ENOSPC);
 546                goto error0;
 547        }
 548        error = xfs_alloc_vextent(&args);
 549        if (error)
 550                goto error0;
 551
 552        if (args.fsbno == NULLFSBLOCK && args.minleft) {
 553                /*
 554                 * Could not find an AG with enough free space to satisfy
 555                 * a full btree split.  Try again without minleft and if
 556                 * successful activate the lowspace algorithm.
 557                 */
 558                args.fsbno = 0;
 559                args.type = XFS_ALLOCTYPE_FIRST_AG;
 560                args.minleft = 0;
 561                error = xfs_alloc_vextent(&args);
 562                if (error)
 563                        goto error0;
 564                cur->bc_private.b.flist->xbf_low = 1;
 565        }
 566        if (args.fsbno == NULLFSBLOCK) {
 567                XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
 568                *stat = 0;
 569                return 0;
 570        }
 571        ASSERT(args.len == 1);
 572        cur->bc_private.b.firstblock = args.fsbno;
 573        cur->bc_private.b.allocated++;
 574        cur->bc_private.b.ip->i_d.di_nblocks++;
 575        xfs_trans_log_inode(args.tp, cur->bc_private.b.ip, XFS_ILOG_CORE);
 576        xfs_trans_mod_dquot_byino(args.tp, cur->bc_private.b.ip,
 577                        XFS_TRANS_DQ_BCOUNT, 1L);
 578
 579        new->l = cpu_to_be64(args.fsbno);
 580
 581        XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
 582        *stat = 1;
 583        return 0;
 584
 585 error0:
 586        XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR);
 587        return error;
 588}
 589
 590STATIC int
 591xfs_bmbt_free_block(
 592        struct xfs_btree_cur    *cur,
 593        struct xfs_buf          *bp)
 594{
 595        struct xfs_mount        *mp = cur->bc_mp;
 596        struct xfs_inode        *ip = cur->bc_private.b.ip;
 597        struct xfs_trans        *tp = cur->bc_tp;
 598        xfs_fsblock_t           fsbno = XFS_DADDR_TO_FSB(mp, XFS_BUF_ADDR(bp));
 599
 600        xfs_bmap_add_free(fsbno, 1, cur->bc_private.b.flist, mp);
 601        ip->i_d.di_nblocks--;
 602
 603        xfs_trans_log_inode(tp, ip, XFS_ILOG_CORE);
 604        xfs_trans_mod_dquot_byino(tp, ip, XFS_TRANS_DQ_BCOUNT, -1L);
 605        xfs_trans_binval(tp, bp);
 606        return 0;
 607}
 608
 609STATIC int
 610xfs_bmbt_get_minrecs(
 611        struct xfs_btree_cur    *cur,
 612        int                     level)
 613{
 614        if (level == cur->bc_nlevels - 1) {
 615                struct xfs_ifork        *ifp;
 616
 617                ifp = XFS_IFORK_PTR(cur->bc_private.b.ip,
 618                                    cur->bc_private.b.whichfork);
 619
 620                return xfs_bmbt_maxrecs(cur->bc_mp,
 621                                        ifp->if_broot_bytes, level == 0) / 2;
 622        }
 623
 624        return cur->bc_mp->m_bmap_dmnr[level != 0];
 625}
 626
 627int
 628xfs_bmbt_get_maxrecs(
 629        struct xfs_btree_cur    *cur,
 630        int                     level)
 631{
 632        if (level == cur->bc_nlevels - 1) {
 633                struct xfs_ifork        *ifp;
 634
 635                ifp = XFS_IFORK_PTR(cur->bc_private.b.ip,
 636                                    cur->bc_private.b.whichfork);
 637
 638                return xfs_bmbt_maxrecs(cur->bc_mp,
 639                                        ifp->if_broot_bytes, level == 0);
 640        }
 641
 642        return cur->bc_mp->m_bmap_dmxr[level != 0];
 643
 644}
 645
 646/*
 647 * Get the maximum records we could store in the on-disk format.
 648 *
 649 * For non-root nodes this is equivalent to xfs_bmbt_get_maxrecs, but
 650 * for the root node this checks the available space in the dinode fork
 651 * so that we can resize the in-memory buffer to match it.  After a
 652 * resize to the maximum size this function returns the same value
 653 * as xfs_bmbt_get_maxrecs for the root node, too.
 654 */
 655STATIC int
 656xfs_bmbt_get_dmaxrecs(
 657        struct xfs_btree_cur    *cur,
 658        int                     level)
 659{
 660        if (level != cur->bc_nlevels - 1)
 661                return cur->bc_mp->m_bmap_dmxr[level != 0];
 662        return xfs_bmdr_maxrecs(cur->bc_mp, cur->bc_private.b.forksize,
 663                                level == 0);
 664}
 665
 666STATIC void
 667xfs_bmbt_init_key_from_rec(
 668        union xfs_btree_key     *key,
 669        union xfs_btree_rec     *rec)
 670{
 671        key->bmbt.br_startoff =
 672                cpu_to_be64(xfs_bmbt_disk_get_startoff(&rec->bmbt));
 673}
 674
 675STATIC void
 676xfs_bmbt_init_rec_from_key(
 677        union xfs_btree_key     *key,
 678        union xfs_btree_rec     *rec)
 679{
 680        ASSERT(key->bmbt.br_startoff != 0);
 681
 682        xfs_bmbt_disk_set_allf(&rec->bmbt, be64_to_cpu(key->bmbt.br_startoff),
 683                               0, 0, XFS_EXT_NORM);
 684}
 685
 686STATIC void
 687xfs_bmbt_init_rec_from_cur(
 688        struct xfs_btree_cur    *cur,
 689        union xfs_btree_rec     *rec)
 690{
 691        xfs_bmbt_disk_set_all(&rec->bmbt, &cur->bc_rec.b);
 692}
 693
 694STATIC void
 695xfs_bmbt_init_ptr_from_cur(
 696        struct xfs_btree_cur    *cur,
 697        union xfs_btree_ptr     *ptr)
 698{
 699        ptr->l = 0;
 700}
 701
 702STATIC __int64_t
 703xfs_bmbt_key_diff(
 704        struct xfs_btree_cur    *cur,
 705        union xfs_btree_key     *key)
 706{
 707        return (__int64_t)be64_to_cpu(key->bmbt.br_startoff) -
 708                                      cur->bc_rec.b.br_startoff;
 709}
 710
 711static void
 712xfs_bmbt_verify(
 713        struct xfs_buf          *bp)
 714{
 715        struct xfs_mount        *mp = bp->b_target->bt_mount;
 716        struct xfs_btree_block  *block = XFS_BUF_TO_BLOCK(bp);
 717        unsigned int            level;
 718        int                     lblock_ok; /* block passes checks */
 719
 720        /* magic number and level verification.
 721         *
 722         * We don't know waht fork we belong to, so just verify that the level
 723         * is less than the maximum of the two. Later checks will be more
 724         * precise.
 725         */
 726        level = be16_to_cpu(block->bb_level);
 727        lblock_ok = block->bb_magic == cpu_to_be32(XFS_BMAP_MAGIC) &&
 728                    level < max(mp->m_bm_maxlevels[0], mp->m_bm_maxlevels[1]);
 729
 730        /* numrecs verification */
 731        lblock_ok = lblock_ok &&
 732                be16_to_cpu(block->bb_numrecs) <= mp->m_bmap_dmxr[level != 0];
 733
 734        /* sibling pointer verification */
 735        lblock_ok = lblock_ok &&
 736                block->bb_u.l.bb_leftsib &&
 737                (block->bb_u.l.bb_leftsib == cpu_to_be64(NULLDFSBNO) ||
 738                 XFS_FSB_SANITY_CHECK(mp,
 739                        be64_to_cpu(block->bb_u.l.bb_leftsib))) &&
 740                block->bb_u.l.bb_rightsib &&
 741                (block->bb_u.l.bb_rightsib == cpu_to_be64(NULLDFSBNO) ||
 742                 XFS_FSB_SANITY_CHECK(mp,
 743                        be64_to_cpu(block->bb_u.l.bb_rightsib)));
 744
 745        if (!lblock_ok) {
 746                trace_xfs_btree_corrupt(bp, _RET_IP_);
 747                XFS_CORRUPTION_ERROR(__func__, XFS_ERRLEVEL_LOW, mp, block);
 748                xfs_buf_ioerror(bp, EFSCORRUPTED);
 749        }
 750}
 751
 752static void
 753xfs_bmbt_read_verify(
 754        struct xfs_buf  *bp)
 755{
 756        xfs_bmbt_verify(bp);
 757}
 758
 759static void
 760xfs_bmbt_write_verify(
 761        struct xfs_buf  *bp)
 762{
 763        xfs_bmbt_verify(bp);
 764}
 765
 766const struct xfs_buf_ops xfs_bmbt_buf_ops = {
 767        .verify_read = xfs_bmbt_read_verify,
 768        .verify_write = xfs_bmbt_write_verify,
 769};
 770
 771
 772#ifdef DEBUG
 773STATIC int
 774xfs_bmbt_keys_inorder(
 775        struct xfs_btree_cur    *cur,
 776        union xfs_btree_key     *k1,
 777        union xfs_btree_key     *k2)
 778{
 779        return be64_to_cpu(k1->bmbt.br_startoff) <
 780                be64_to_cpu(k2->bmbt.br_startoff);
 781}
 782
 783STATIC int
 784xfs_bmbt_recs_inorder(
 785        struct xfs_btree_cur    *cur,
 786        union xfs_btree_rec     *r1,
 787        union xfs_btree_rec     *r2)
 788{
 789        return xfs_bmbt_disk_get_startoff(&r1->bmbt) +
 790                xfs_bmbt_disk_get_blockcount(&r1->bmbt) <=
 791                xfs_bmbt_disk_get_startoff(&r2->bmbt);
 792}
 793#endif  /* DEBUG */
 794
 795static const struct xfs_btree_ops xfs_bmbt_ops = {
 796        .rec_len                = sizeof(xfs_bmbt_rec_t),
 797        .key_len                = sizeof(xfs_bmbt_key_t),
 798
 799        .dup_cursor             = xfs_bmbt_dup_cursor,
 800        .update_cursor          = xfs_bmbt_update_cursor,
 801        .alloc_block            = xfs_bmbt_alloc_block,
 802        .free_block             = xfs_bmbt_free_block,
 803        .get_maxrecs            = xfs_bmbt_get_maxrecs,
 804        .get_minrecs            = xfs_bmbt_get_minrecs,
 805        .get_dmaxrecs           = xfs_bmbt_get_dmaxrecs,
 806        .init_key_from_rec      = xfs_bmbt_init_key_from_rec,
 807        .init_rec_from_key      = xfs_bmbt_init_rec_from_key,
 808        .init_rec_from_cur      = xfs_bmbt_init_rec_from_cur,
 809        .init_ptr_from_cur      = xfs_bmbt_init_ptr_from_cur,
 810        .key_diff               = xfs_bmbt_key_diff,
 811        .buf_ops                = &xfs_bmbt_buf_ops,
 812#ifdef DEBUG
 813        .keys_inorder           = xfs_bmbt_keys_inorder,
 814        .recs_inorder           = xfs_bmbt_recs_inorder,
 815#endif
 816};
 817
 818/*
 819 * Allocate a new bmap btree cursor.
 820 */
 821struct xfs_btree_cur *                          /* new bmap btree cursor */
 822xfs_bmbt_init_cursor(
 823        struct xfs_mount        *mp,            /* file system mount point */
 824        struct xfs_trans        *tp,            /* transaction pointer */
 825        struct xfs_inode        *ip,            /* inode owning the btree */
 826        int                     whichfork)      /* data or attr fork */
 827{
 828        struct xfs_ifork        *ifp = XFS_IFORK_PTR(ip, whichfork);
 829        struct xfs_btree_cur    *cur;
 830
 831        cur = kmem_zone_zalloc(xfs_btree_cur_zone, KM_SLEEP);
 832
 833        cur->bc_tp = tp;
 834        cur->bc_mp = mp;
 835        cur->bc_nlevels = be16_to_cpu(ifp->if_broot->bb_level) + 1;
 836        cur->bc_btnum = XFS_BTNUM_BMAP;
 837        cur->bc_blocklog = mp->m_sb.sb_blocklog;
 838
 839        cur->bc_ops = &xfs_bmbt_ops;
 840        cur->bc_flags = XFS_BTREE_LONG_PTRS | XFS_BTREE_ROOT_IN_INODE;
 841
 842        cur->bc_private.b.forksize = XFS_IFORK_SIZE(ip, whichfork);
 843        cur->bc_private.b.ip = ip;
 844        cur->bc_private.b.firstblock = NULLFSBLOCK;
 845        cur->bc_private.b.flist = NULL;
 846        cur->bc_private.b.allocated = 0;
 847        cur->bc_private.b.flags = 0;
 848        cur->bc_private.b.whichfork = whichfork;
 849
 850        return cur;
 851}
 852
 853/*
 854 * Calculate number of records in a bmap btree block.
 855 */
 856int
 857xfs_bmbt_maxrecs(
 858        struct xfs_mount        *mp,
 859        int                     blocklen,
 860        int                     leaf)
 861{
 862        blocklen -= XFS_BMBT_BLOCK_LEN(mp);
 863
 864        if (leaf)
 865                return blocklen / sizeof(xfs_bmbt_rec_t);
 866        return blocklen / (sizeof(xfs_bmbt_key_t) + sizeof(xfs_bmbt_ptr_t));
 867}
 868
 869/*
 870 * Calculate number of records in a bmap btree inode root.
 871 */
 872int
 873xfs_bmdr_maxrecs(
 874        struct xfs_mount        *mp,
 875        int                     blocklen,
 876        int                     leaf)
 877{
 878        blocklen -= sizeof(xfs_bmdr_block_t);
 879
 880        if (leaf)
 881                return blocklen / sizeof(xfs_bmdr_rec_t);
 882        return blocklen / (sizeof(xfs_bmdr_key_t) + sizeof(xfs_bmdr_ptr_t));
 883}
 884
lxr.linux.no kindly hosted by Redpill Linpro AS, provider of Linux consulting and operations services since 1995.