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