linux/fs/xfs/xfs_dir2_node.c
<<
>>
Prefs
   1/*
   2 * Copyright (c) 2000-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_log.h"
  22#include "xfs_trans.h"
  23#include "xfs_sb.h"
  24#include "xfs_ag.h"
  25#include "xfs_mount.h"
  26#include "xfs_da_btree.h"
  27#include "xfs_bmap_btree.h"
  28#include "xfs_dinode.h"
  29#include "xfs_inode.h"
  30#include "xfs_bmap.h"
  31#include "xfs_dir2_format.h"
  32#include "xfs_dir2_priv.h"
  33#include "xfs_error.h"
  34#include "xfs_trace.h"
  35
  36/*
  37 * Function declarations.
  38 */
  39static int xfs_dir2_leafn_add(struct xfs_buf *bp, xfs_da_args_t *args,
  40                              int index);
  41#ifdef DEBUG
  42static void xfs_dir2_leafn_check(struct xfs_inode *dp, struct xfs_buf *bp);
  43#else
  44#define xfs_dir2_leafn_check(dp, bp)
  45#endif
  46static void xfs_dir2_leafn_moveents(xfs_da_args_t *args, struct xfs_buf *bp_s,
  47                                    int start_s, struct xfs_buf *bp_d,
  48                                    int start_d, int count);
  49static void xfs_dir2_leafn_rebalance(xfs_da_state_t *state,
  50                                     xfs_da_state_blk_t *blk1,
  51                                     xfs_da_state_blk_t *blk2);
  52static int xfs_dir2_leafn_remove(xfs_da_args_t *args, struct xfs_buf *bp,
  53                                 int index, xfs_da_state_blk_t *dblk,
  54                                 int *rval);
  55static int xfs_dir2_node_addname_int(xfs_da_args_t *args,
  56                                     xfs_da_state_blk_t *fblk);
  57
  58static void
  59xfs_dir2_free_verify(
  60        struct xfs_buf          *bp)
  61{
  62        struct xfs_mount        *mp = bp->b_target->bt_mount;
  63        struct xfs_dir2_free_hdr *hdr = bp->b_addr;
  64        int                     block_ok = 0;
  65
  66        block_ok = hdr->magic == cpu_to_be32(XFS_DIR2_FREE_MAGIC);
  67        if (!block_ok) {
  68                XFS_CORRUPTION_ERROR("xfs_dir2_free_verify magic",
  69                                     XFS_ERRLEVEL_LOW, mp, hdr);
  70                xfs_buf_ioerror(bp, EFSCORRUPTED);
  71        }
  72}
  73
  74static void
  75xfs_dir2_free_read_verify(
  76        struct xfs_buf  *bp)
  77{
  78        xfs_dir2_free_verify(bp);
  79}
  80
  81static void
  82xfs_dir2_free_write_verify(
  83        struct xfs_buf  *bp)
  84{
  85        xfs_dir2_free_verify(bp);
  86}
  87
  88static const struct xfs_buf_ops xfs_dir2_free_buf_ops = {
  89        .verify_read = xfs_dir2_free_read_verify,
  90        .verify_write = xfs_dir2_free_write_verify,
  91};
  92
  93
  94static int
  95__xfs_dir2_free_read(
  96        struct xfs_trans        *tp,
  97        struct xfs_inode        *dp,
  98        xfs_dablk_t             fbno,
  99        xfs_daddr_t             mappedbno,
 100        struct xfs_buf          **bpp)
 101{
 102        return xfs_da_read_buf(tp, dp, fbno, mappedbno, bpp,
 103                                XFS_DATA_FORK, &xfs_dir2_free_buf_ops);
 104}
 105
 106int
 107xfs_dir2_free_read(
 108        struct xfs_trans        *tp,
 109        struct xfs_inode        *dp,
 110        xfs_dablk_t             fbno,
 111        struct xfs_buf          **bpp)
 112{
 113        return __xfs_dir2_free_read(tp, dp, fbno, -1, bpp);
 114}
 115
 116static int
 117xfs_dir2_free_try_read(
 118        struct xfs_trans        *tp,
 119        struct xfs_inode        *dp,
 120        xfs_dablk_t             fbno,
 121        struct xfs_buf          **bpp)
 122{
 123        return __xfs_dir2_free_read(tp, dp, fbno, -2, bpp);
 124}
 125
 126/*
 127 * Log entries from a freespace block.
 128 */
 129STATIC void
 130xfs_dir2_free_log_bests(
 131        struct xfs_trans        *tp,
 132        struct xfs_buf          *bp,
 133        int                     first,          /* first entry to log */
 134        int                     last)           /* last entry to log */
 135{
 136        xfs_dir2_free_t         *free;          /* freespace structure */
 137
 138        free = bp->b_addr;
 139        ASSERT(free->hdr.magic == cpu_to_be32(XFS_DIR2_FREE_MAGIC));
 140        xfs_trans_log_buf(tp, bp,
 141                (uint)((char *)&free->bests[first] - (char *)free),
 142                (uint)((char *)&free->bests[last] - (char *)free +
 143                       sizeof(free->bests[0]) - 1));
 144}
 145
 146/*
 147 * Log header from a freespace block.
 148 */
 149static void
 150xfs_dir2_free_log_header(
 151        struct xfs_trans        *tp,
 152        struct xfs_buf          *bp)
 153{
 154        xfs_dir2_free_t         *free;          /* freespace structure */
 155
 156        free = bp->b_addr;
 157        ASSERT(free->hdr.magic == cpu_to_be32(XFS_DIR2_FREE_MAGIC));
 158        xfs_trans_log_buf(tp, bp, (uint)((char *)&free->hdr - (char *)free),
 159                (uint)(sizeof(xfs_dir2_free_hdr_t) - 1));
 160}
 161
 162/*
 163 * Convert a leaf-format directory to a node-format directory.
 164 * We need to change the magic number of the leaf block, and copy
 165 * the freespace table out of the leaf block into its own block.
 166 */
 167int                                             /* error */
 168xfs_dir2_leaf_to_node(
 169        xfs_da_args_t           *args,          /* operation arguments */
 170        struct xfs_buf          *lbp)           /* leaf buffer */
 171{
 172        xfs_inode_t             *dp;            /* incore directory inode */
 173        int                     error;          /* error return value */
 174        struct xfs_buf          *fbp;           /* freespace buffer */
 175        xfs_dir2_db_t           fdb;            /* freespace block number */
 176        xfs_dir2_free_t         *free;          /* freespace structure */
 177        __be16                  *from;          /* pointer to freespace entry */
 178        int                     i;              /* leaf freespace index */
 179        xfs_dir2_leaf_t         *leaf;          /* leaf structure */
 180        xfs_dir2_leaf_tail_t    *ltp;           /* leaf tail structure */
 181        xfs_mount_t             *mp;            /* filesystem mount point */
 182        int                     n;              /* count of live freespc ents */
 183        xfs_dir2_data_off_t     off;            /* freespace entry value */
 184        __be16                  *to;            /* pointer to freespace entry */
 185        xfs_trans_t             *tp;            /* transaction pointer */
 186
 187        trace_xfs_dir2_leaf_to_node(args);
 188
 189        dp = args->dp;
 190        mp = dp->i_mount;
 191        tp = args->trans;
 192        /*
 193         * Add a freespace block to the directory.
 194         */
 195        if ((error = xfs_dir2_grow_inode(args, XFS_DIR2_FREE_SPACE, &fdb))) {
 196                return error;
 197        }
 198        ASSERT(fdb == XFS_DIR2_FREE_FIRSTDB(mp));
 199        /*
 200         * Get the buffer for the new freespace block.
 201         */
 202        error = xfs_da_get_buf(tp, dp, xfs_dir2_db_to_da(mp, fdb), -1, &fbp,
 203                                XFS_DATA_FORK);
 204        if (error)
 205                return error;
 206        fbp->b_ops = &xfs_dir2_free_buf_ops;
 207
 208        free = fbp->b_addr;
 209        leaf = lbp->b_addr;
 210        ltp = xfs_dir2_leaf_tail_p(mp, leaf);
 211        /*
 212         * Initialize the freespace block header.
 213         */
 214        free->hdr.magic = cpu_to_be32(XFS_DIR2_FREE_MAGIC);
 215        free->hdr.firstdb = 0;
 216        ASSERT(be32_to_cpu(ltp->bestcount) <= (uint)dp->i_d.di_size / mp->m_dirblksize);
 217        free->hdr.nvalid = ltp->bestcount;
 218        /*
 219         * Copy freespace entries from the leaf block to the new block.
 220         * Count active entries.
 221         */
 222        for (i = n = 0, from = xfs_dir2_leaf_bests_p(ltp), to = free->bests;
 223             i < be32_to_cpu(ltp->bestcount); i++, from++, to++) {
 224                if ((off = be16_to_cpu(*from)) != NULLDATAOFF)
 225                        n++;
 226                *to = cpu_to_be16(off);
 227        }
 228        free->hdr.nused = cpu_to_be32(n);
 229
 230        lbp->b_ops = &xfs_dir2_leafn_buf_ops;
 231        leaf->hdr.info.magic = cpu_to_be16(XFS_DIR2_LEAFN_MAGIC);
 232
 233        /*
 234         * Log everything.
 235         */
 236        xfs_dir2_leaf_log_header(tp, lbp);
 237        xfs_dir2_free_log_header(tp, fbp);
 238        xfs_dir2_free_log_bests(tp, fbp, 0, be32_to_cpu(free->hdr.nvalid) - 1);
 239        xfs_dir2_leafn_check(dp, lbp);
 240        return 0;
 241}
 242
 243/*
 244 * Add a leaf entry to a leaf block in a node-form directory.
 245 * The other work necessary is done from the caller.
 246 */
 247static int                                      /* error */
 248xfs_dir2_leafn_add(
 249        struct xfs_buf          *bp,            /* leaf buffer */
 250        xfs_da_args_t           *args,          /* operation arguments */
 251        int                     index)          /* insertion pt for new entry */
 252{
 253        int                     compact;        /* compacting stale leaves */
 254        xfs_inode_t             *dp;            /* incore directory inode */
 255        int                     highstale;      /* next stale entry */
 256        xfs_dir2_leaf_t         *leaf;          /* leaf structure */
 257        xfs_dir2_leaf_entry_t   *lep;           /* leaf entry */
 258        int                     lfloghigh;      /* high leaf entry logging */
 259        int                     lfloglow;       /* low leaf entry logging */
 260        int                     lowstale;       /* previous stale entry */
 261        xfs_mount_t             *mp;            /* filesystem mount point */
 262        xfs_trans_t             *tp;            /* transaction pointer */
 263
 264        trace_xfs_dir2_leafn_add(args, index);
 265
 266        dp = args->dp;
 267        mp = dp->i_mount;
 268        tp = args->trans;
 269        leaf = bp->b_addr;
 270
 271        /*
 272         * Quick check just to make sure we are not going to index
 273         * into other peoples memory
 274         */
 275        if (index < 0)
 276                return XFS_ERROR(EFSCORRUPTED);
 277
 278        /*
 279         * If there are already the maximum number of leaf entries in
 280         * the block, if there are no stale entries it won't fit.
 281         * Caller will do a split.  If there are stale entries we'll do
 282         * a compact.
 283         */
 284
 285        if (be16_to_cpu(leaf->hdr.count) == xfs_dir2_max_leaf_ents(mp)) {
 286                if (!leaf->hdr.stale)
 287                        return XFS_ERROR(ENOSPC);
 288                compact = be16_to_cpu(leaf->hdr.stale) > 1;
 289        } else
 290                compact = 0;
 291        ASSERT(index == 0 || be32_to_cpu(leaf->ents[index - 1].hashval) <= args->hashval);
 292        ASSERT(index == be16_to_cpu(leaf->hdr.count) ||
 293               be32_to_cpu(leaf->ents[index].hashval) >= args->hashval);
 294
 295        if (args->op_flags & XFS_DA_OP_JUSTCHECK)
 296                return 0;
 297
 298        /*
 299         * Compact out all but one stale leaf entry.  Leaves behind
 300         * the entry closest to index.
 301         */
 302        if (compact) {
 303                xfs_dir2_leaf_compact_x1(bp, &index, &lowstale, &highstale,
 304                        &lfloglow, &lfloghigh);
 305        }
 306        /*
 307         * Set impossible logging indices for this case.
 308         */
 309        else if (leaf->hdr.stale) {
 310                lfloglow = be16_to_cpu(leaf->hdr.count);
 311                lfloghigh = -1;
 312        }
 313
 314        /*
 315         * Insert the new entry, log everything.
 316         */
 317        lep = xfs_dir2_leaf_find_entry(leaf, index, compact, lowstale,
 318                                       highstale, &lfloglow, &lfloghigh);
 319
 320        lep->hashval = cpu_to_be32(args->hashval);
 321        lep->address = cpu_to_be32(xfs_dir2_db_off_to_dataptr(mp,
 322                                args->blkno, args->index));
 323        xfs_dir2_leaf_log_header(tp, bp);
 324        xfs_dir2_leaf_log_ents(tp, bp, lfloglow, lfloghigh);
 325        xfs_dir2_leafn_check(dp, bp);
 326        return 0;
 327}
 328
 329#ifdef DEBUG
 330/*
 331 * Check internal consistency of a leafn block.
 332 */
 333void
 334xfs_dir2_leafn_check(
 335        struct xfs_inode *dp,
 336        struct xfs_buf  *bp)
 337{
 338        int             i;                      /* leaf index */
 339        xfs_dir2_leaf_t *leaf;                  /* leaf structure */
 340        xfs_mount_t     *mp;                    /* filesystem mount point */
 341        int             stale;                  /* count of stale leaves */
 342
 343        leaf = bp->b_addr;
 344        mp = dp->i_mount;
 345        ASSERT(leaf->hdr.info.magic == cpu_to_be16(XFS_DIR2_LEAFN_MAGIC));
 346        ASSERT(be16_to_cpu(leaf->hdr.count) <= xfs_dir2_max_leaf_ents(mp));
 347        for (i = stale = 0; i < be16_to_cpu(leaf->hdr.count); i++) {
 348                if (i + 1 < be16_to_cpu(leaf->hdr.count)) {
 349                        ASSERT(be32_to_cpu(leaf->ents[i].hashval) <=
 350                               be32_to_cpu(leaf->ents[i + 1].hashval));
 351                }
 352                if (leaf->ents[i].address == cpu_to_be32(XFS_DIR2_NULL_DATAPTR))
 353                        stale++;
 354        }
 355        ASSERT(be16_to_cpu(leaf->hdr.stale) == stale);
 356}
 357#endif  /* DEBUG */
 358
 359/*
 360 * Return the last hash value in the leaf.
 361 * Stale entries are ok.
 362 */
 363xfs_dahash_t                                    /* hash value */
 364xfs_dir2_leafn_lasthash(
 365        struct xfs_buf  *bp,                    /* leaf buffer */
 366        int             *count)                 /* count of entries in leaf */
 367{
 368        xfs_dir2_leaf_t *leaf;                  /* leaf structure */
 369
 370        leaf = bp->b_addr;
 371        ASSERT(leaf->hdr.info.magic == cpu_to_be16(XFS_DIR2_LEAFN_MAGIC));
 372        if (count)
 373                *count = be16_to_cpu(leaf->hdr.count);
 374        if (!leaf->hdr.count)
 375                return 0;
 376        return be32_to_cpu(leaf->ents[be16_to_cpu(leaf->hdr.count) - 1].hashval);
 377}
 378
 379/*
 380 * Look up a leaf entry for space to add a name in a node-format leaf block.
 381 * The extrablk in state is a freespace block.
 382 */
 383STATIC int
 384xfs_dir2_leafn_lookup_for_addname(
 385        struct xfs_buf          *bp,            /* leaf buffer */
 386        xfs_da_args_t           *args,          /* operation arguments */
 387        int                     *indexp,        /* out: leaf entry index */
 388        xfs_da_state_t          *state)         /* state to fill in */
 389{
 390        struct xfs_buf          *curbp = NULL;  /* current data/free buffer */
 391        xfs_dir2_db_t           curdb = -1;     /* current data block number */
 392        xfs_dir2_db_t           curfdb = -1;    /* current free block number */
 393        xfs_inode_t             *dp;            /* incore directory inode */
 394        int                     error;          /* error return value */
 395        int                     fi;             /* free entry index */
 396        xfs_dir2_free_t         *free = NULL;   /* free block structure */
 397        int                     index;          /* leaf entry index */
 398        xfs_dir2_leaf_t         *leaf;          /* leaf structure */
 399        int                     length;         /* length of new data entry */
 400        xfs_dir2_leaf_entry_t   *lep;           /* leaf entry */
 401        xfs_mount_t             *mp;            /* filesystem mount point */
 402        xfs_dir2_db_t           newdb;          /* new data block number */
 403        xfs_dir2_db_t           newfdb;         /* new free block number */
 404        xfs_trans_t             *tp;            /* transaction pointer */
 405
 406        dp = args->dp;
 407        tp = args->trans;
 408        mp = dp->i_mount;
 409        leaf = bp->b_addr;
 410        ASSERT(leaf->hdr.info.magic == cpu_to_be16(XFS_DIR2_LEAFN_MAGIC));
 411#ifdef __KERNEL__
 412        ASSERT(be16_to_cpu(leaf->hdr.count) > 0);
 413#endif
 414        xfs_dir2_leafn_check(dp, bp);
 415        /*
 416         * Look up the hash value in the leaf entries.
 417         */
 418        index = xfs_dir2_leaf_search_hash(args, bp);
 419        /*
 420         * Do we have a buffer coming in?
 421         */
 422        if (state->extravalid) {
 423                /* If so, it's a free block buffer, get the block number. */
 424                curbp = state->extrablk.bp;
 425                curfdb = state->extrablk.blkno;
 426                free = curbp->b_addr;
 427                ASSERT(free->hdr.magic == cpu_to_be32(XFS_DIR2_FREE_MAGIC));
 428        }
 429        length = xfs_dir2_data_entsize(args->namelen);
 430        /*
 431         * Loop over leaf entries with the right hash value.
 432         */
 433        for (lep = &leaf->ents[index]; index < be16_to_cpu(leaf->hdr.count) &&
 434                                be32_to_cpu(lep->hashval) == args->hashval;
 435                                lep++, index++) {
 436                /*
 437                 * Skip stale leaf entries.
 438                 */
 439                if (be32_to_cpu(lep->address) == XFS_DIR2_NULL_DATAPTR)
 440                        continue;
 441                /*
 442                 * Pull the data block number from the entry.
 443                 */
 444                newdb = xfs_dir2_dataptr_to_db(mp, be32_to_cpu(lep->address));
 445                /*
 446                 * For addname, we're looking for a place to put the new entry.
 447                 * We want to use a data block with an entry of equal
 448                 * hash value to ours if there is one with room.
 449                 *
 450                 * If this block isn't the data block we already have
 451                 * in hand, take a look at it.
 452                 */
 453                if (newdb != curdb) {
 454                        curdb = newdb;
 455                        /*
 456                         * Convert the data block to the free block
 457                         * holding its freespace information.
 458                         */
 459                        newfdb = xfs_dir2_db_to_fdb(mp, newdb);
 460                        /*
 461                         * If it's not the one we have in hand, read it in.
 462                         */
 463                        if (newfdb != curfdb) {
 464                                /*
 465                                 * If we had one before, drop it.
 466                                 */
 467                                if (curbp)
 468                                        xfs_trans_brelse(tp, curbp);
 469
 470                                error = xfs_dir2_free_read(tp, dp,
 471                                                xfs_dir2_db_to_da(mp, newfdb),
 472                                                &curbp);
 473                                if (error)
 474                                        return error;
 475                                free = curbp->b_addr;
 476                                ASSERT(be32_to_cpu(free->hdr.magic) ==
 477                                        XFS_DIR2_FREE_MAGIC);
 478                                ASSERT((be32_to_cpu(free->hdr.firstdb) %
 479                                        xfs_dir2_free_max_bests(mp)) == 0);
 480                                ASSERT(be32_to_cpu(free->hdr.firstdb) <= curdb);
 481                                ASSERT(curdb < be32_to_cpu(free->hdr.firstdb) +
 482                                        be32_to_cpu(free->hdr.nvalid));
 483                        }
 484                        /*
 485                         * Get the index for our entry.
 486                         */
 487                        fi = xfs_dir2_db_to_fdindex(mp, curdb);
 488                        /*
 489                         * If it has room, return it.
 490                         */
 491                        if (unlikely(free->bests[fi] ==
 492                            cpu_to_be16(NULLDATAOFF))) {
 493                                XFS_ERROR_REPORT("xfs_dir2_leafn_lookup_int",
 494                                                        XFS_ERRLEVEL_LOW, mp);
 495                                if (curfdb != newfdb)
 496                                        xfs_trans_brelse(tp, curbp);
 497                                return XFS_ERROR(EFSCORRUPTED);
 498                        }
 499                        curfdb = newfdb;
 500                        if (be16_to_cpu(free->bests[fi]) >= length)
 501                                goto out;
 502                }
 503        }
 504        /* Didn't find any space */
 505        fi = -1;
 506out:
 507        ASSERT(args->op_flags & XFS_DA_OP_OKNOENT);
 508        if (curbp) {
 509                /* Giving back a free block. */
 510                state->extravalid = 1;
 511                state->extrablk.bp = curbp;
 512                state->extrablk.index = fi;
 513                state->extrablk.blkno = curfdb;
 514                state->extrablk.magic = XFS_DIR2_FREE_MAGIC;
 515        } else {
 516                state->extravalid = 0;
 517        }
 518        /*
 519         * Return the index, that will be the insertion point.
 520         */
 521        *indexp = index;
 522        return XFS_ERROR(ENOENT);
 523}
 524
 525/*
 526 * Look up a leaf entry in a node-format leaf block.
 527 * The extrablk in state a data block.
 528 */
 529STATIC int
 530xfs_dir2_leafn_lookup_for_entry(
 531        struct xfs_buf          *bp,            /* leaf buffer */
 532        xfs_da_args_t           *args,          /* operation arguments */
 533        int                     *indexp,        /* out: leaf entry index */
 534        xfs_da_state_t          *state)         /* state to fill in */
 535{
 536        struct xfs_buf          *curbp = NULL;  /* current data/free buffer */
 537        xfs_dir2_db_t           curdb = -1;     /* current data block number */
 538        xfs_dir2_data_entry_t   *dep;           /* data block entry */
 539        xfs_inode_t             *dp;            /* incore directory inode */
 540        int                     error;          /* error return value */
 541        int                     index;          /* leaf entry index */
 542        xfs_dir2_leaf_t         *leaf;          /* leaf structure */
 543        xfs_dir2_leaf_entry_t   *lep;           /* leaf entry */
 544        xfs_mount_t             *mp;            /* filesystem mount point */
 545        xfs_dir2_db_t           newdb;          /* new data block number */
 546        xfs_trans_t             *tp;            /* transaction pointer */
 547        enum xfs_dacmp          cmp;            /* comparison result */
 548
 549        dp = args->dp;
 550        tp = args->trans;
 551        mp = dp->i_mount;
 552        leaf = bp->b_addr;
 553        ASSERT(leaf->hdr.info.magic == cpu_to_be16(XFS_DIR2_LEAFN_MAGIC));
 554#ifdef __KERNEL__
 555        ASSERT(be16_to_cpu(leaf->hdr.count) > 0);
 556#endif
 557        xfs_dir2_leafn_check(dp, bp);
 558        /*
 559         * Look up the hash value in the leaf entries.
 560         */
 561        index = xfs_dir2_leaf_search_hash(args, bp);
 562        /*
 563         * Do we have a buffer coming in?
 564         */
 565        if (state->extravalid) {
 566                curbp = state->extrablk.bp;
 567                curdb = state->extrablk.blkno;
 568        }
 569        /*
 570         * Loop over leaf entries with the right hash value.
 571         */
 572        for (lep = &leaf->ents[index]; index < be16_to_cpu(leaf->hdr.count) &&
 573                                be32_to_cpu(lep->hashval) == args->hashval;
 574                                lep++, index++) {
 575                /*
 576                 * Skip stale leaf entries.
 577                 */
 578                if (be32_to_cpu(lep->address) == XFS_DIR2_NULL_DATAPTR)
 579                        continue;
 580                /*
 581                 * Pull the data block number from the entry.
 582                 */
 583                newdb = xfs_dir2_dataptr_to_db(mp, be32_to_cpu(lep->address));
 584                /*
 585                 * Not adding a new entry, so we really want to find
 586                 * the name given to us.
 587                 *
 588                 * If it's a different data block, go get it.
 589                 */
 590                if (newdb != curdb) {
 591                        /*
 592                         * If we had a block before that we aren't saving
 593                         * for a CI name, drop it
 594                         */
 595                        if (curbp && (args->cmpresult == XFS_CMP_DIFFERENT ||
 596                                                curdb != state->extrablk.blkno))
 597                                xfs_trans_brelse(tp, curbp);
 598                        /*
 599                         * If needing the block that is saved with a CI match,
 600                         * use it otherwise read in the new data block.
 601                         */
 602                        if (args->cmpresult != XFS_CMP_DIFFERENT &&
 603                                        newdb == state->extrablk.blkno) {
 604                                ASSERT(state->extravalid);
 605                                curbp = state->extrablk.bp;
 606                        } else {
 607                                error = xfs_dir2_data_read(tp, dp,
 608                                                xfs_dir2_db_to_da(mp, newdb),
 609                                                -1, &curbp);
 610                                if (error)
 611                                        return error;
 612                        }
 613                        xfs_dir2_data_check(dp, curbp);
 614                        curdb = newdb;
 615                }
 616                /*
 617                 * Point to the data entry.
 618                 */
 619                dep = (xfs_dir2_data_entry_t *)((char *)curbp->b_addr +
 620                        xfs_dir2_dataptr_to_off(mp, be32_to_cpu(lep->address)));
 621                /*
 622                 * Compare the entry and if it's an exact match, return
 623                 * EEXIST immediately. If it's the first case-insensitive
 624                 * match, store the block & inode number and continue looking.
 625                 */
 626                cmp = mp->m_dirnameops->compname(args, dep->name, dep->namelen);
 627                if (cmp != XFS_CMP_DIFFERENT && cmp != args->cmpresult) {
 628                        /* If there is a CI match block, drop it */
 629                        if (args->cmpresult != XFS_CMP_DIFFERENT &&
 630                                                curdb != state->extrablk.blkno)
 631                                xfs_trans_brelse(tp, state->extrablk.bp);
 632                        args->cmpresult = cmp;
 633                        args->inumber = be64_to_cpu(dep->inumber);
 634                        *indexp = index;
 635                        state->extravalid = 1;
 636                        state->extrablk.bp = curbp;
 637                        state->extrablk.blkno = curdb;
 638                        state->extrablk.index = (int)((char *)dep -
 639                                                        (char *)curbp->b_addr);
 640                        state->extrablk.magic = XFS_DIR2_DATA_MAGIC;
 641                        curbp->b_ops = &xfs_dir2_data_buf_ops;
 642                        if (cmp == XFS_CMP_EXACT)
 643                                return XFS_ERROR(EEXIST);
 644                }
 645        }
 646        ASSERT(index == be16_to_cpu(leaf->hdr.count) ||
 647                                        (args->op_flags & XFS_DA_OP_OKNOENT));
 648        if (curbp) {
 649                if (args->cmpresult == XFS_CMP_DIFFERENT) {
 650                        /* Giving back last used data block. */
 651                        state->extravalid = 1;
 652                        state->extrablk.bp = curbp;
 653                        state->extrablk.index = -1;
 654                        state->extrablk.blkno = curdb;
 655                        state->extrablk.magic = XFS_DIR2_DATA_MAGIC;
 656                        curbp->b_ops = &xfs_dir2_data_buf_ops;
 657                } else {
 658                        /* If the curbp is not the CI match block, drop it */
 659                        if (state->extrablk.bp != curbp)
 660                                xfs_trans_brelse(tp, curbp);
 661                }
 662        } else {
 663                state->extravalid = 0;
 664        }
 665        *indexp = index;
 666        return XFS_ERROR(ENOENT);
 667}
 668
 669/*
 670 * Look up a leaf entry in a node-format leaf block.
 671 * If this is an addname then the extrablk in state is a freespace block,
 672 * otherwise it's a data block.
 673 */
 674int
 675xfs_dir2_leafn_lookup_int(
 676        struct xfs_buf          *bp,            /* leaf buffer */
 677        xfs_da_args_t           *args,          /* operation arguments */
 678        int                     *indexp,        /* out: leaf entry index */
 679        xfs_da_state_t          *state)         /* state to fill in */
 680{
 681        if (args->op_flags & XFS_DA_OP_ADDNAME)
 682                return xfs_dir2_leafn_lookup_for_addname(bp, args, indexp,
 683                                                        state);
 684        return xfs_dir2_leafn_lookup_for_entry(bp, args, indexp, state);
 685}
 686
 687/*
 688 * Move count leaf entries from source to destination leaf.
 689 * Log entries and headers.  Stale entries are preserved.
 690 */
 691static void
 692xfs_dir2_leafn_moveents(
 693        xfs_da_args_t   *args,                  /* operation arguments */
 694        struct xfs_buf  *bp_s,                  /* source leaf buffer */
 695        int             start_s,                /* source leaf index */
 696        struct xfs_buf  *bp_d,                  /* destination leaf buffer */
 697        int             start_d,                /* destination leaf index */
 698        int             count)                  /* count of leaves to copy */
 699{
 700        xfs_dir2_leaf_t *leaf_d;                /* destination leaf structure */
 701        xfs_dir2_leaf_t *leaf_s;                /* source leaf structure */
 702        int             stale;                  /* count stale leaves copied */
 703        xfs_trans_t     *tp;                    /* transaction pointer */
 704
 705        trace_xfs_dir2_leafn_moveents(args, start_s, start_d, count);
 706
 707        /*
 708         * Silently return if nothing to do.
 709         */
 710        if (count == 0) {
 711                return;
 712        }
 713        tp = args->trans;
 714        leaf_s = bp_s->b_addr;
 715        leaf_d = bp_d->b_addr;
 716        /*
 717         * If the destination index is not the end of the current
 718         * destination leaf entries, open up a hole in the destination
 719         * to hold the new entries.
 720         */
 721        if (start_d < be16_to_cpu(leaf_d->hdr.count)) {
 722                memmove(&leaf_d->ents[start_d + count], &leaf_d->ents[start_d],
 723                        (be16_to_cpu(leaf_d->hdr.count) - start_d) *
 724                        sizeof(xfs_dir2_leaf_entry_t));
 725                xfs_dir2_leaf_log_ents(tp, bp_d, start_d + count,
 726                        count + be16_to_cpu(leaf_d->hdr.count) - 1);
 727        }
 728        /*
 729         * If the source has stale leaves, count the ones in the copy range
 730         * so we can update the header correctly.
 731         */
 732        if (leaf_s->hdr.stale) {
 733                int     i;                      /* temp leaf index */
 734
 735                for (i = start_s, stale = 0; i < start_s + count; i++) {
 736                        if (leaf_s->ents[i].address ==
 737                            cpu_to_be32(XFS_DIR2_NULL_DATAPTR))
 738                                stale++;
 739                }
 740        } else
 741                stale = 0;
 742        /*
 743         * Copy the leaf entries from source to destination.
 744         */
 745        memcpy(&leaf_d->ents[start_d], &leaf_s->ents[start_s],
 746                count * sizeof(xfs_dir2_leaf_entry_t));
 747        xfs_dir2_leaf_log_ents(tp, bp_d, start_d, start_d + count - 1);
 748        /*
 749         * If there are source entries after the ones we copied,
 750         * delete the ones we copied by sliding the next ones down.
 751         */
 752        if (start_s + count < be16_to_cpu(leaf_s->hdr.count)) {
 753                memmove(&leaf_s->ents[start_s], &leaf_s->ents[start_s + count],
 754                        count * sizeof(xfs_dir2_leaf_entry_t));
 755                xfs_dir2_leaf_log_ents(tp, bp_s, start_s, start_s + count - 1);
 756        }
 757        /*
 758         * Update the headers and log them.
 759         */
 760        be16_add_cpu(&leaf_s->hdr.count, -(count));
 761        be16_add_cpu(&leaf_s->hdr.stale, -(stale));
 762        be16_add_cpu(&leaf_d->hdr.count, count);
 763        be16_add_cpu(&leaf_d->hdr.stale, stale);
 764        xfs_dir2_leaf_log_header(tp, bp_s);
 765        xfs_dir2_leaf_log_header(tp, bp_d);
 766        xfs_dir2_leafn_check(args->dp, bp_s);
 767        xfs_dir2_leafn_check(args->dp, bp_d);
 768}
 769
 770/*
 771 * Determine the sort order of two leaf blocks.
 772 * Returns 1 if both are valid and leaf2 should be before leaf1, else 0.
 773 */
 774int                                             /* sort order */
 775xfs_dir2_leafn_order(
 776        struct xfs_buf  *leaf1_bp,              /* leaf1 buffer */
 777        struct xfs_buf  *leaf2_bp)              /* leaf2 buffer */
 778{
 779        xfs_dir2_leaf_t *leaf1;                 /* leaf1 structure */
 780        xfs_dir2_leaf_t *leaf2;                 /* leaf2 structure */
 781
 782        leaf1 = leaf1_bp->b_addr;
 783        leaf2 = leaf2_bp->b_addr;
 784        ASSERT(leaf1->hdr.info.magic == cpu_to_be16(XFS_DIR2_LEAFN_MAGIC));
 785        ASSERT(leaf2->hdr.info.magic == cpu_to_be16(XFS_DIR2_LEAFN_MAGIC));
 786        if (be16_to_cpu(leaf1->hdr.count) > 0 &&
 787            be16_to_cpu(leaf2->hdr.count) > 0 &&
 788            (be32_to_cpu(leaf2->ents[0].hashval) < be32_to_cpu(leaf1->ents[0].hashval) ||
 789             be32_to_cpu(leaf2->ents[be16_to_cpu(leaf2->hdr.count) - 1].hashval) <
 790             be32_to_cpu(leaf1->ents[be16_to_cpu(leaf1->hdr.count) - 1].hashval)))
 791                return 1;
 792        return 0;
 793}
 794
 795/*
 796 * Rebalance leaf entries between two leaf blocks.
 797 * This is actually only called when the second block is new,
 798 * though the code deals with the general case.
 799 * A new entry will be inserted in one of the blocks, and that
 800 * entry is taken into account when balancing.
 801 */
 802static void
 803xfs_dir2_leafn_rebalance(
 804        xfs_da_state_t          *state,         /* btree cursor */
 805        xfs_da_state_blk_t      *blk1,          /* first btree block */
 806        xfs_da_state_blk_t      *blk2)          /* second btree block */
 807{
 808        xfs_da_args_t           *args;          /* operation arguments */
 809        int                     count;          /* count (& direction) leaves */
 810        int                     isleft;         /* new goes in left leaf */
 811        xfs_dir2_leaf_t         *leaf1;         /* first leaf structure */
 812        xfs_dir2_leaf_t         *leaf2;         /* second leaf structure */
 813        int                     mid;            /* midpoint leaf index */
 814#ifdef DEBUG
 815        int                     oldstale;       /* old count of stale leaves */
 816#endif
 817        int                     oldsum;         /* old total leaf count */
 818        int                     swap;           /* swapped leaf blocks */
 819
 820        args = state->args;
 821        /*
 822         * If the block order is wrong, swap the arguments.
 823         */
 824        if ((swap = xfs_dir2_leafn_order(blk1->bp, blk2->bp))) {
 825                xfs_da_state_blk_t      *tmp;   /* temp for block swap */
 826
 827                tmp = blk1;
 828                blk1 = blk2;
 829                blk2 = tmp;
 830        }
 831        leaf1 = blk1->bp->b_addr;
 832        leaf2 = blk2->bp->b_addr;
 833        oldsum = be16_to_cpu(leaf1->hdr.count) + be16_to_cpu(leaf2->hdr.count);
 834#ifdef DEBUG
 835        oldstale = be16_to_cpu(leaf1->hdr.stale) + be16_to_cpu(leaf2->hdr.stale);
 836#endif
 837        mid = oldsum >> 1;
 838        /*
 839         * If the old leaf count was odd then the new one will be even,
 840         * so we need to divide the new count evenly.
 841         */
 842        if (oldsum & 1) {
 843                xfs_dahash_t    midhash;        /* middle entry hash value */
 844
 845                if (mid >= be16_to_cpu(leaf1->hdr.count))
 846                        midhash = be32_to_cpu(leaf2->ents[mid - be16_to_cpu(leaf1->hdr.count)].hashval);
 847                else
 848                        midhash = be32_to_cpu(leaf1->ents[mid].hashval);
 849                isleft = args->hashval <= midhash;
 850        }
 851        /*
 852         * If the old count is even then the new count is odd, so there's
 853         * no preferred side for the new entry.
 854         * Pick the left one.
 855         */
 856        else
 857                isleft = 1;
 858        /*
 859         * Calculate moved entry count.  Positive means left-to-right,
 860         * negative means right-to-left.  Then move the entries.
 861         */
 862        count = be16_to_cpu(leaf1->hdr.count) - mid + (isleft == 0);
 863        if (count > 0)
 864                xfs_dir2_leafn_moveents(args, blk1->bp,
 865                        be16_to_cpu(leaf1->hdr.count) - count, blk2->bp, 0, count);
 866        else if (count < 0)
 867                xfs_dir2_leafn_moveents(args, blk2->bp, 0, blk1->bp,
 868                        be16_to_cpu(leaf1->hdr.count), count);
 869        ASSERT(be16_to_cpu(leaf1->hdr.count) + be16_to_cpu(leaf2->hdr.count) == oldsum);
 870        ASSERT(be16_to_cpu(leaf1->hdr.stale) + be16_to_cpu(leaf2->hdr.stale) == oldstale);
 871        /*
 872         * Mark whether we're inserting into the old or new leaf.
 873         */
 874        if (be16_to_cpu(leaf1->hdr.count) < be16_to_cpu(leaf2->hdr.count))
 875                state->inleaf = swap;
 876        else if (be16_to_cpu(leaf1->hdr.count) > be16_to_cpu(leaf2->hdr.count))
 877                state->inleaf = !swap;
 878        else
 879                state->inleaf =
 880                        swap ^ (blk1->index <= be16_to_cpu(leaf1->hdr.count));
 881        /*
 882         * Adjust the expected index for insertion.
 883         */
 884        if (!state->inleaf)
 885                blk2->index = blk1->index - be16_to_cpu(leaf1->hdr.count);
 886
 887        /*
 888         * Finally sanity check just to make sure we are not returning a
 889         * negative index
 890         */
 891        if(blk2->index < 0) {
 892                state->inleaf = 1;
 893                blk2->index = 0;
 894                xfs_alert(args->dp->i_mount,
 895        "%s: picked the wrong leaf? reverting original leaf: blk1->index %d\n",
 896                        __func__, blk1->index);
 897        }
 898}
 899
 900static int
 901xfs_dir2_data_block_free(
 902        xfs_da_args_t           *args,
 903        struct xfs_dir2_data_hdr *hdr,
 904        struct xfs_dir2_free    *free,
 905        xfs_dir2_db_t           fdb,
 906        int                     findex,
 907        struct xfs_buf          *fbp,
 908        int                     longest)
 909{
 910        struct xfs_trans        *tp = args->trans;
 911        int                     logfree = 0;
 912
 913        if (!hdr) {
 914                /* One less used entry in the free table.  */
 915                be32_add_cpu(&free->hdr.nused, -1);
 916                xfs_dir2_free_log_header(tp, fbp);
 917
 918                /*
 919                 * If this was the last entry in the table, we can trim the
 920                 * table size back.  There might be other entries at the end
 921                 * referring to non-existent data blocks, get those too.
 922                 */
 923                if (findex == be32_to_cpu(free->hdr.nvalid) - 1) {
 924                        int     i;              /* free entry index */
 925
 926                        for (i = findex - 1; i >= 0; i--) {
 927                                if (free->bests[i] != cpu_to_be16(NULLDATAOFF))
 928                                        break;
 929                        }
 930                        free->hdr.nvalid = cpu_to_be32(i + 1);
 931                        logfree = 0;
 932                } else {
 933                        /* Not the last entry, just punch it out.  */
 934                        free->bests[findex] = cpu_to_be16(NULLDATAOFF);
 935                        logfree = 1;
 936                }
 937                /*
 938                 * If there are no useful entries left in the block,
 939                 * get rid of the block if we can.
 940                 */
 941                if (!free->hdr.nused) {
 942                        int error;
 943
 944                        error = xfs_dir2_shrink_inode(args, fdb, fbp);
 945                        if (error == 0) {
 946                                fbp = NULL;
 947                                logfree = 0;
 948                        } else if (error != ENOSPC || args->total != 0)
 949                                return error;
 950                        /*
 951                         * It's possible to get ENOSPC if there is no
 952                         * space reservation.  In this case some one
 953                         * else will eventually get rid of this block.
 954                         */
 955                }
 956        } else {
 957                /*
 958                 * Data block is not empty, just set the free entry to the new
 959                 * value.
 960                 */
 961                free->bests[findex] = cpu_to_be16(longest);
 962                logfree = 1;
 963        }
 964
 965        /* Log the free entry that changed, unless we got rid of it.  */
 966        if (logfree)
 967                xfs_dir2_free_log_bests(tp, fbp, findex, findex);
 968        return 0;
 969}
 970
 971/*
 972 * Remove an entry from a node directory.
 973 * This removes the leaf entry and the data entry,
 974 * and updates the free block if necessary.
 975 */
 976static int                                      /* error */
 977xfs_dir2_leafn_remove(
 978        xfs_da_args_t           *args,          /* operation arguments */
 979        struct xfs_buf          *bp,            /* leaf buffer */
 980        int                     index,          /* leaf entry index */
 981        xfs_da_state_blk_t      *dblk,          /* data block */
 982        int                     *rval)          /* resulting block needs join */
 983{
 984        xfs_dir2_data_hdr_t     *hdr;           /* data block header */
 985        xfs_dir2_db_t           db;             /* data block number */
 986        struct xfs_buf          *dbp;           /* data block buffer */
 987        xfs_dir2_data_entry_t   *dep;           /* data block entry */
 988        xfs_inode_t             *dp;            /* incore directory inode */
 989        xfs_dir2_leaf_t         *leaf;          /* leaf structure */
 990        xfs_dir2_leaf_entry_t   *lep;           /* leaf entry */
 991        int                     longest;        /* longest data free entry */
 992        int                     off;            /* data block entry offset */
 993        xfs_mount_t             *mp;            /* filesystem mount point */
 994        int                     needlog;        /* need to log data header */
 995        int                     needscan;       /* need to rescan data frees */
 996        xfs_trans_t             *tp;            /* transaction pointer */
 997
 998        trace_xfs_dir2_leafn_remove(args, index);
 999
1000        dp = args->dp;
1001        tp = args->trans;
1002        mp = dp->i_mount;
1003        leaf = bp->b_addr;
1004        ASSERT(leaf->hdr.info.magic == cpu_to_be16(XFS_DIR2_LEAFN_MAGIC));
1005        /*
1006         * Point to the entry we're removing.
1007         */
1008        lep = &leaf->ents[index];
1009        /*
1010         * Extract the data block and offset from the entry.
1011         */
1012        db = xfs_dir2_dataptr_to_db(mp, be32_to_cpu(lep->address));
1013        ASSERT(dblk->blkno == db);
1014        off = xfs_dir2_dataptr_to_off(mp, be32_to_cpu(lep->address));
1015        ASSERT(dblk->index == off);
1016        /*
1017         * Kill the leaf entry by marking it stale.
1018         * Log the leaf block changes.
1019         */
1020        be16_add_cpu(&leaf->hdr.stale, 1);
1021        xfs_dir2_leaf_log_header(tp, bp);
1022        lep->address = cpu_to_be32(XFS_DIR2_NULL_DATAPTR);
1023        xfs_dir2_leaf_log_ents(tp, bp, index, index);
1024        /*
1025         * Make the data entry free.  Keep track of the longest freespace
1026         * in the data block in case it changes.
1027         */
1028        dbp = dblk->bp;
1029        hdr = dbp->b_addr;
1030        dep = (xfs_dir2_data_entry_t *)((char *)hdr + off);
1031        longest = be16_to_cpu(hdr->bestfree[0].length);
1032        needlog = needscan = 0;
1033        xfs_dir2_data_make_free(tp, dbp, off,
1034                xfs_dir2_data_entsize(dep->namelen), &needlog, &needscan);
1035        /*
1036         * Rescan the data block freespaces for bestfree.
1037         * Log the data block header if needed.
1038         */
1039        if (needscan)
1040                xfs_dir2_data_freescan(mp, hdr, &needlog);
1041        if (needlog)
1042                xfs_dir2_data_log_header(tp, dbp);
1043        xfs_dir2_data_check(dp, dbp);
1044        /*
1045         * If the longest data block freespace changes, need to update
1046         * the corresponding freeblock entry.
1047         */
1048        if (longest < be16_to_cpu(hdr->bestfree[0].length)) {
1049                int             error;          /* error return value */
1050                struct xfs_buf  *fbp;           /* freeblock buffer */
1051                xfs_dir2_db_t   fdb;            /* freeblock block number */
1052                int             findex;         /* index in freeblock entries */
1053                xfs_dir2_free_t *free;          /* freeblock structure */
1054
1055                /*
1056                 * Convert the data block number to a free block,
1057                 * read in the free block.
1058                 */
1059                fdb = xfs_dir2_db_to_fdb(mp, db);
1060                error = xfs_dir2_free_read(tp, dp, xfs_dir2_db_to_da(mp, fdb),
1061                                           &fbp);
1062                if (error)
1063                        return error;
1064                free = fbp->b_addr;
1065                ASSERT(free->hdr.magic == cpu_to_be32(XFS_DIR2_FREE_MAGIC));
1066                ASSERT(be32_to_cpu(free->hdr.firstdb) ==
1067                       xfs_dir2_free_max_bests(mp) *
1068                       (fdb - XFS_DIR2_FREE_FIRSTDB(mp)));
1069                /*
1070                 * Calculate which entry we need to fix.
1071                 */
1072                findex = xfs_dir2_db_to_fdindex(mp, db);
1073                longest = be16_to_cpu(hdr->bestfree[0].length);
1074                /*
1075                 * If the data block is now empty we can get rid of it
1076                 * (usually).
1077                 */
1078                if (longest == mp->m_dirblksize - (uint)sizeof(*hdr)) {
1079                        /*
1080                         * Try to punch out the data block.
1081                         */
1082                        error = xfs_dir2_shrink_inode(args, db, dbp);
1083                        if (error == 0) {
1084                                dblk->bp = NULL;
1085                                hdr = NULL;
1086                        }
1087                        /*
1088                         * We can get ENOSPC if there's no space reservation.
1089                         * In this case just drop the buffer and some one else
1090                         * will eventually get rid of the empty block.
1091                         */
1092                        else if (!(error == ENOSPC && args->total == 0))
1093                                return error;
1094                }
1095                /*
1096                 * If we got rid of the data block, we can eliminate that entry
1097                 * in the free block.
1098                 */
1099                error = xfs_dir2_data_block_free(args, hdr, free,
1100                                                 fdb, findex, fbp, longest);
1101                if (error)
1102                        return error;
1103        }
1104
1105        xfs_dir2_leafn_check(dp, bp);
1106        /*
1107         * Return indication of whether this leaf block is empty enough
1108         * to justify trying to join it with a neighbor.
1109         */
1110        *rval =
1111                ((uint)sizeof(leaf->hdr) +
1112                 (uint)sizeof(leaf->ents[0]) *
1113                 (be16_to_cpu(leaf->hdr.count) - be16_to_cpu(leaf->hdr.stale))) <
1114                mp->m_dir_magicpct;
1115        return 0;
1116}
1117
1118/*
1119 * Split the leaf entries in the old block into old and new blocks.
1120 */
1121int                                             /* error */
1122xfs_dir2_leafn_split(
1123        xfs_da_state_t          *state,         /* btree cursor */
1124        xfs_da_state_blk_t      *oldblk,        /* original block */
1125        xfs_da_state_blk_t      *newblk)        /* newly created block */
1126{
1127        xfs_da_args_t           *args;          /* operation arguments */
1128        xfs_dablk_t             blkno;          /* new leaf block number */
1129        int                     error;          /* error return value */
1130        xfs_mount_t             *mp;            /* filesystem mount point */
1131
1132        /*
1133         * Allocate space for a new leaf node.
1134         */
1135        args = state->args;
1136        mp = args->dp->i_mount;
1137        ASSERT(args != NULL);
1138        ASSERT(oldblk->magic == XFS_DIR2_LEAFN_MAGIC);
1139        error = xfs_da_grow_inode(args, &blkno);
1140        if (error) {
1141                return error;
1142        }
1143        /*
1144         * Initialize the new leaf block.
1145         */
1146        error = xfs_dir2_leaf_init(args, xfs_dir2_da_to_db(mp, blkno),
1147                &newblk->bp, XFS_DIR2_LEAFN_MAGIC);
1148        if (error) {
1149                return error;
1150        }
1151        newblk->blkno = blkno;
1152        newblk->magic = XFS_DIR2_LEAFN_MAGIC;
1153        /*
1154         * Rebalance the entries across the two leaves, link the new
1155         * block into the leaves.
1156         */
1157        xfs_dir2_leafn_rebalance(state, oldblk, newblk);
1158        error = xfs_da_blk_link(state, oldblk, newblk);
1159        if (error) {
1160                return error;
1161        }
1162        /*
1163         * Insert the new entry in the correct block.
1164         */
1165        if (state->inleaf)
1166                error = xfs_dir2_leafn_add(oldblk->bp, args, oldblk->index);
1167        else
1168                error = xfs_dir2_leafn_add(newblk->bp, args, newblk->index);
1169        /*
1170         * Update last hashval in each block since we added the name.
1171         */
1172        oldblk->hashval = xfs_dir2_leafn_lasthash(oldblk->bp, NULL);
1173        newblk->hashval = xfs_dir2_leafn_lasthash(newblk->bp, NULL);
1174        xfs_dir2_leafn_check(args->dp, oldblk->bp);
1175        xfs_dir2_leafn_check(args->dp, newblk->bp);
1176        return error;
1177}
1178
1179/*
1180 * Check a leaf block and its neighbors to see if the block should be
1181 * collapsed into one or the other neighbor.  Always keep the block
1182 * with the smaller block number.
1183 * If the current block is over 50% full, don't try to join it, return 0.
1184 * If the block is empty, fill in the state structure and return 2.
1185 * If it can be collapsed, fill in the state structure and return 1.
1186 * If nothing can be done, return 0.
1187 */
1188int                                             /* error */
1189xfs_dir2_leafn_toosmall(
1190        xfs_da_state_t          *state,         /* btree cursor */
1191        int                     *action)        /* resulting action to take */
1192{
1193        xfs_da_state_blk_t      *blk;           /* leaf block */
1194        xfs_dablk_t             blkno;          /* leaf block number */
1195        struct xfs_buf          *bp;            /* leaf buffer */
1196        int                     bytes;          /* bytes in use */
1197        int                     count;          /* leaf live entry count */
1198        int                     error;          /* error return value */
1199        int                     forward;        /* sibling block direction */
1200        int                     i;              /* sibling counter */
1201        xfs_da_blkinfo_t        *info;          /* leaf block header */
1202        xfs_dir2_leaf_t         *leaf;          /* leaf structure */
1203        int                     rval;           /* result from path_shift */
1204
1205        /*
1206         * Check for the degenerate case of the block being over 50% full.
1207         * If so, it's not worth even looking to see if we might be able
1208         * to coalesce with a sibling.
1209         */
1210        blk = &state->path.blk[state->path.active - 1];
1211        info = blk->bp->b_addr;
1212        ASSERT(info->magic == cpu_to_be16(XFS_DIR2_LEAFN_MAGIC));
1213        leaf = (xfs_dir2_leaf_t *)info;
1214        count = be16_to_cpu(leaf->hdr.count) - be16_to_cpu(leaf->hdr.stale);
1215        bytes = (uint)sizeof(leaf->hdr) + count * (uint)sizeof(leaf->ents[0]);
1216        if (bytes > (state->blocksize >> 1)) {
1217                /*
1218                 * Blk over 50%, don't try to join.
1219                 */
1220                *action = 0;
1221                return 0;
1222        }
1223        /*
1224         * Check for the degenerate case of the block being empty.
1225         * If the block is empty, we'll simply delete it, no need to
1226         * coalesce it with a sibling block.  We choose (arbitrarily)
1227         * to merge with the forward block unless it is NULL.
1228         */
1229        if (count == 0) {
1230                /*
1231                 * Make altpath point to the block we want to keep and
1232                 * path point to the block we want to drop (this one).
1233                 */
1234                forward = (info->forw != 0);
1235                memcpy(&state->altpath, &state->path, sizeof(state->path));
1236                error = xfs_da_path_shift(state, &state->altpath, forward, 0,
1237                        &rval);
1238                if (error)
1239                        return error;
1240                *action = rval ? 2 : 0;
1241                return 0;
1242        }
1243        /*
1244         * Examine each sibling block to see if we can coalesce with
1245         * at least 25% free space to spare.  We need to figure out
1246         * whether to merge with the forward or the backward block.
1247         * We prefer coalescing with the lower numbered sibling so as
1248         * to shrink a directory over time.
1249         */
1250        forward = be32_to_cpu(info->forw) < be32_to_cpu(info->back);
1251        for (i = 0, bp = NULL; i < 2; forward = !forward, i++) {
1252                blkno = forward ? be32_to_cpu(info->forw) : be32_to_cpu(info->back);
1253                if (blkno == 0)
1254                        continue;
1255                /*
1256                 * Read the sibling leaf block.
1257                 */
1258                error = xfs_dir2_leafn_read(state->args->trans, state->args->dp,
1259                                            blkno, -1, &bp);
1260                if (error)
1261                        return error;
1262
1263                /*
1264                 * Count bytes in the two blocks combined.
1265                 */
1266                leaf = (xfs_dir2_leaf_t *)info;
1267                count = be16_to_cpu(leaf->hdr.count) - be16_to_cpu(leaf->hdr.stale);
1268                bytes = state->blocksize - (state->blocksize >> 2);
1269                leaf = bp->b_addr;
1270                ASSERT(leaf->hdr.info.magic == cpu_to_be16(XFS_DIR2_LEAFN_MAGIC));
1271                count += be16_to_cpu(leaf->hdr.count) - be16_to_cpu(leaf->hdr.stale);
1272                bytes -= count * (uint)sizeof(leaf->ents[0]);
1273                /*
1274                 * Fits with at least 25% to spare.
1275                 */
1276                if (bytes >= 0)
1277                        break;
1278                xfs_trans_brelse(state->args->trans, bp);
1279        }
1280        /*
1281         * Didn't like either block, give up.
1282         */
1283        if (i >= 2) {
1284                *action = 0;
1285                return 0;
1286        }
1287
1288        /*
1289         * Make altpath point to the block we want to keep (the lower
1290         * numbered block) and path point to the block we want to drop.
1291         */
1292        memcpy(&state->altpath, &state->path, sizeof(state->path));
1293        if (blkno < blk->blkno)
1294                error = xfs_da_path_shift(state, &state->altpath, forward, 0,
1295                        &rval);
1296        else
1297                error = xfs_da_path_shift(state, &state->path, forward, 0,
1298                        &rval);
1299        if (error) {
1300                return error;
1301        }
1302        *action = rval ? 0 : 1;
1303        return 0;
1304}
1305
1306/*
1307 * Move all the leaf entries from drop_blk to save_blk.
1308 * This is done as part of a join operation.
1309 */
1310void
1311xfs_dir2_leafn_unbalance(
1312        xfs_da_state_t          *state,         /* cursor */
1313        xfs_da_state_blk_t      *drop_blk,      /* dead block */
1314        xfs_da_state_blk_t      *save_blk)      /* surviving block */
1315{
1316        xfs_da_args_t           *args;          /* operation arguments */
1317        xfs_dir2_leaf_t         *drop_leaf;     /* dead leaf structure */
1318        xfs_dir2_leaf_t         *save_leaf;     /* surviving leaf structure */
1319
1320        args = state->args;
1321        ASSERT(drop_blk->magic == XFS_DIR2_LEAFN_MAGIC);
1322        ASSERT(save_blk->magic == XFS_DIR2_LEAFN_MAGIC);
1323        drop_leaf = drop_blk->bp->b_addr;
1324        save_leaf = save_blk->bp->b_addr;
1325        ASSERT(drop_leaf->hdr.info.magic == cpu_to_be16(XFS_DIR2_LEAFN_MAGIC));
1326        ASSERT(save_leaf->hdr.info.magic == cpu_to_be16(XFS_DIR2_LEAFN_MAGIC));
1327        /*
1328         * If there are any stale leaf entries, take this opportunity
1329         * to purge them.
1330         */
1331        if (drop_leaf->hdr.stale)
1332                xfs_dir2_leaf_compact(args, drop_blk->bp);
1333        if (save_leaf->hdr.stale)
1334                xfs_dir2_leaf_compact(args, save_blk->bp);
1335        /*
1336         * Move the entries from drop to the appropriate end of save.
1337         */
1338        drop_blk->hashval = be32_to_cpu(drop_leaf->ents[be16_to_cpu(drop_leaf->hdr.count) - 1].hashval);
1339        if (xfs_dir2_leafn_order(save_blk->bp, drop_blk->bp))
1340                xfs_dir2_leafn_moveents(args, drop_blk->bp, 0, save_blk->bp, 0,
1341                        be16_to_cpu(drop_leaf->hdr.count));
1342        else
1343                xfs_dir2_leafn_moveents(args, drop_blk->bp, 0, save_blk->bp,
1344                        be16_to_cpu(save_leaf->hdr.count), be16_to_cpu(drop_leaf->hdr.count));
1345        save_blk->hashval = be32_to_cpu(save_leaf->ents[be16_to_cpu(save_leaf->hdr.count) - 1].hashval);
1346        xfs_dir2_leafn_check(args->dp, save_blk->bp);
1347}
1348
1349/*
1350 * Top-level node form directory addname routine.
1351 */
1352int                                             /* error */
1353xfs_dir2_node_addname(
1354        xfs_da_args_t           *args)          /* operation arguments */
1355{
1356        xfs_da_state_blk_t      *blk;           /* leaf block for insert */
1357        int                     error;          /* error return value */
1358        int                     rval;           /* sub-return value */
1359        xfs_da_state_t          *state;         /* btree cursor */
1360
1361        trace_xfs_dir2_node_addname(args);
1362
1363        /*
1364         * Allocate and initialize the state (btree cursor).
1365         */
1366        state = xfs_da_state_alloc();
1367        state->args = args;
1368        state->mp = args->dp->i_mount;
1369        state->blocksize = state->mp->m_dirblksize;
1370        state->node_ents = state->mp->m_dir_node_ents;
1371        /*
1372         * Look up the name.  We're not supposed to find it, but
1373         * this gives us the insertion point.
1374         */
1375        error = xfs_da_node_lookup_int(state, &rval);
1376        if (error)
1377                rval = error;
1378        if (rval != ENOENT) {
1379                goto done;
1380        }
1381        /*
1382         * Add the data entry to a data block.
1383         * Extravalid is set to a freeblock found by lookup.
1384         */
1385        rval = xfs_dir2_node_addname_int(args,
1386                state->extravalid ? &state->extrablk : NULL);
1387        if (rval) {
1388                goto done;
1389        }
1390        blk = &state->path.blk[state->path.active - 1];
1391        ASSERT(blk->magic == XFS_DIR2_LEAFN_MAGIC);
1392        /*
1393         * Add the new leaf entry.
1394         */
1395        rval = xfs_dir2_leafn_add(blk->bp, args, blk->index);
1396        if (rval == 0) {
1397                /*
1398                 * It worked, fix the hash values up the btree.
1399                 */
1400                if (!(args->op_flags & XFS_DA_OP_JUSTCHECK))
1401                        xfs_da_fixhashpath(state, &state->path);
1402        } else {
1403                /*
1404                 * It didn't work, we need to split the leaf block.
1405                 */
1406                if (args->total == 0) {
1407                        ASSERT(rval == ENOSPC);
1408                        goto done;
1409                }
1410                /*
1411                 * Split the leaf block and insert the new entry.
1412                 */
1413                rval = xfs_da_split(state);
1414        }
1415done:
1416        xfs_da_state_free(state);
1417        return rval;
1418}
1419
1420/*
1421 * Add the data entry for a node-format directory name addition.
1422 * The leaf entry is added in xfs_dir2_leafn_add.
1423 * We may enter with a freespace block that the lookup found.
1424 */
1425static int                                      /* error */
1426xfs_dir2_node_addname_int(
1427        xfs_da_args_t           *args,          /* operation arguments */
1428        xfs_da_state_blk_t      *fblk)          /* optional freespace block */
1429{
1430        xfs_dir2_data_hdr_t     *hdr;           /* data block header */
1431        xfs_dir2_db_t           dbno;           /* data block number */
1432        struct xfs_buf          *dbp;           /* data block buffer */
1433        xfs_dir2_data_entry_t   *dep;           /* data entry pointer */
1434        xfs_inode_t             *dp;            /* incore directory inode */
1435        xfs_dir2_data_unused_t  *dup;           /* data unused entry pointer */
1436        int                     error;          /* error return value */
1437        xfs_dir2_db_t           fbno;           /* freespace block number */
1438        struct xfs_buf          *fbp;           /* freespace buffer */
1439        int                     findex;         /* freespace entry index */
1440        xfs_dir2_free_t         *free=NULL;     /* freespace block structure */
1441        xfs_dir2_db_t           ifbno;          /* initial freespace block no */
1442        xfs_dir2_db_t           lastfbno=0;     /* highest freespace block no */
1443        int                     length;         /* length of the new entry */
1444        int                     logfree;        /* need to log free entry */
1445        xfs_mount_t             *mp;            /* filesystem mount point */
1446        int                     needlog;        /* need to log data header */
1447        int                     needscan;       /* need to rescan data frees */
1448        __be16                  *tagp;          /* data entry tag pointer */
1449        xfs_trans_t             *tp;            /* transaction pointer */
1450
1451        dp = args->dp;
1452        mp = dp->i_mount;
1453        tp = args->trans;
1454        length = xfs_dir2_data_entsize(args->namelen);
1455        /*
1456         * If we came in with a freespace block that means that lookup
1457         * found an entry with our hash value.  This is the freespace
1458         * block for that data entry.
1459         */
1460        if (fblk) {
1461                fbp = fblk->bp;
1462                /*
1463                 * Remember initial freespace block number.
1464                 */
1465                ifbno = fblk->blkno;
1466                free = fbp->b_addr;
1467                ASSERT(free->hdr.magic == cpu_to_be32(XFS_DIR2_FREE_MAGIC));
1468                findex = fblk->index;
1469                /*
1470                 * This means the free entry showed that the data block had
1471                 * space for our entry, so we remembered it.
1472                 * Use that data block.
1473                 */
1474                if (findex >= 0) {
1475                        ASSERT(findex < be32_to_cpu(free->hdr.nvalid));
1476                        ASSERT(be16_to_cpu(free->bests[findex]) != NULLDATAOFF);
1477                        ASSERT(be16_to_cpu(free->bests[findex]) >= length);
1478                        dbno = be32_to_cpu(free->hdr.firstdb) + findex;
1479                }
1480                /*
1481                 * The data block looked at didn't have enough room.
1482                 * We'll start at the beginning of the freespace entries.
1483                 */
1484                else {
1485                        dbno = -1;
1486                        findex = 0;
1487                }
1488        }
1489        /*
1490         * Didn't come in with a freespace block, so don't have a data block.
1491         */
1492        else {
1493                ifbno = dbno = -1;
1494                fbp = NULL;
1495                findex = 0;
1496        }
1497        /*
1498         * If we don't have a data block yet, we're going to scan the
1499         * freespace blocks looking for one.  Figure out what the
1500         * highest freespace block number is.
1501         */
1502        if (dbno == -1) {
1503                xfs_fileoff_t   fo;             /* freespace block number */
1504
1505                if ((error = xfs_bmap_last_offset(tp, dp, &fo, XFS_DATA_FORK)))
1506                        return error;
1507                lastfbno = xfs_dir2_da_to_db(mp, (xfs_dablk_t)fo);
1508                fbno = ifbno;
1509        }
1510        /*
1511         * While we haven't identified a data block, search the freeblock
1512         * data for a good data block.  If we find a null freeblock entry,
1513         * indicating a hole in the data blocks, remember that.
1514         */
1515        while (dbno == -1) {
1516                /*
1517                 * If we don't have a freeblock in hand, get the next one.
1518                 */
1519                if (fbp == NULL) {
1520                        /*
1521                         * Happens the first time through unless lookup gave
1522                         * us a freespace block to start with.
1523                         */
1524                        if (++fbno == 0)
1525                                fbno = XFS_DIR2_FREE_FIRSTDB(mp);
1526                        /*
1527                         * If it's ifbno we already looked at it.
1528                         */
1529                        if (fbno == ifbno)
1530                                fbno++;
1531                        /*
1532                         * If it's off the end we're done.
1533                         */
1534                        if (fbno >= lastfbno)
1535                                break;
1536                        /*
1537                         * Read the block.  There can be holes in the
1538                         * freespace blocks, so this might not succeed.
1539                         * This should be really rare, so there's no reason
1540                         * to avoid it.
1541                         */
1542                        error = xfs_dir2_free_try_read(tp, dp,
1543                                                xfs_dir2_db_to_da(mp, fbno),
1544                                                &fbp);
1545                        if (error)
1546                                return error;
1547                        if (!fbp)
1548                                continue;
1549                        free = fbp->b_addr;
1550                        ASSERT(free->hdr.magic == cpu_to_be32(XFS_DIR2_FREE_MAGIC));
1551                        findex = 0;
1552                }
1553                /*
1554                 * Look at the current free entry.  Is it good enough?
1555                 */
1556                if (be16_to_cpu(free->bests[findex]) != NULLDATAOFF &&
1557                    be16_to_cpu(free->bests[findex]) >= length)
1558                        dbno = be32_to_cpu(free->hdr.firstdb) + findex;
1559                else {
1560                        /*
1561                         * Are we done with the freeblock?
1562                         */
1563                        if (++findex == be32_to_cpu(free->hdr.nvalid)) {
1564                                /*
1565                                 * Drop the block.
1566                                 */
1567                                xfs_trans_brelse(tp, fbp);
1568                                fbp = NULL;
1569                                if (fblk && fblk->bp)
1570                                        fblk->bp = NULL;
1571                        }
1572                }
1573        }
1574        /*
1575         * If we don't have a data block, we need to allocate one and make
1576         * the freespace entries refer to it.
1577         */
1578        if (unlikely(dbno == -1)) {
1579                /*
1580                 * Not allowed to allocate, return failure.
1581                 */
1582                if ((args->op_flags & XFS_DA_OP_JUSTCHECK) || args->total == 0)
1583                        return XFS_ERROR(ENOSPC);
1584
1585                /*
1586                 * Allocate and initialize the new data block.
1587                 */
1588                if (unlikely((error = xfs_dir2_grow_inode(args,
1589                                                         XFS_DIR2_DATA_SPACE,
1590                                                         &dbno)) ||
1591                    (error = xfs_dir2_data_init(args, dbno, &dbp))))
1592                        return error;
1593
1594                /*
1595                 * If (somehow) we have a freespace block, get rid of it.
1596                 */
1597                if (fbp)
1598                        xfs_trans_brelse(tp, fbp);
1599                if (fblk && fblk->bp)
1600                        fblk->bp = NULL;
1601
1602                /*
1603                 * Get the freespace block corresponding to the data block
1604                 * that was just allocated.
1605                 */
1606                fbno = xfs_dir2_db_to_fdb(mp, dbno);
1607                error = xfs_dir2_free_try_read(tp, dp,
1608                                               xfs_dir2_db_to_da(mp, fbno),
1609                                               &fbp);
1610                if (error)
1611                        return error;
1612
1613                /*
1614                 * If there wasn't a freespace block, the read will
1615                 * return a NULL fbp.  Allocate and initialize a new one.
1616                 */
1617                if( fbp == NULL ) {
1618                        if ((error = xfs_dir2_grow_inode(args, XFS_DIR2_FREE_SPACE,
1619                                                        &fbno))) {
1620                                return error;
1621                        }
1622
1623                        if (unlikely(xfs_dir2_db_to_fdb(mp, dbno) != fbno)) {
1624                                xfs_alert(mp,
1625                        "%s: dir ino %llu needed freesp block %lld for\n"
1626                        "  data block %lld, got %lld ifbno %llu lastfbno %d",
1627                                        __func__, (unsigned long long)dp->i_ino,
1628                                        (long long)xfs_dir2_db_to_fdb(mp, dbno),
1629                                        (long long)dbno, (long long)fbno,
1630                                        (unsigned long long)ifbno, lastfbno);
1631                                if (fblk) {
1632                                        xfs_alert(mp,
1633                                " fblk 0x%p blkno %llu index %d magic 0x%x",
1634                                                fblk,
1635                                                (unsigned long long)fblk->blkno,
1636                                                fblk->index,
1637                                                fblk->magic);
1638                                } else {
1639                                        xfs_alert(mp, " ... fblk is NULL");
1640                                }
1641                                XFS_ERROR_REPORT("xfs_dir2_node_addname_int",
1642                                                 XFS_ERRLEVEL_LOW, mp);
1643                                return XFS_ERROR(EFSCORRUPTED);
1644                        }
1645
1646                        /*
1647                         * Get a buffer for the new block.
1648                         */
1649                        error = xfs_da_get_buf(tp, dp,
1650                                               xfs_dir2_db_to_da(mp, fbno),
1651                                               -1, &fbp, XFS_DATA_FORK);
1652                        if (error)
1653                                return error;
1654                        fbp->b_ops = &xfs_dir2_free_buf_ops;
1655
1656                        /*
1657                         * Initialize the new block to be empty, and remember
1658                         * its first slot as our empty slot.
1659                         */
1660                        free = fbp->b_addr;
1661                        free->hdr.magic = cpu_to_be32(XFS_DIR2_FREE_MAGIC);
1662                        free->hdr.firstdb = cpu_to_be32(
1663                                (fbno - XFS_DIR2_FREE_FIRSTDB(mp)) *
1664                                xfs_dir2_free_max_bests(mp));
1665                        free->hdr.nvalid = 0;
1666                        free->hdr.nused = 0;
1667                } else {
1668                        free = fbp->b_addr;
1669                        ASSERT(free->hdr.magic == cpu_to_be32(XFS_DIR2_FREE_MAGIC));
1670                }
1671
1672                /*
1673                 * Set the freespace block index from the data block number.
1674                 */
1675                findex = xfs_dir2_db_to_fdindex(mp, dbno);
1676                /*
1677                 * If it's after the end of the current entries in the
1678                 * freespace block, extend that table.
1679                 */
1680                if (findex >= be32_to_cpu(free->hdr.nvalid)) {
1681                        ASSERT(findex < xfs_dir2_free_max_bests(mp));
1682                        free->hdr.nvalid = cpu_to_be32(findex + 1);
1683                        /*
1684                         * Tag new entry so nused will go up.
1685                         */
1686                        free->bests[findex] = cpu_to_be16(NULLDATAOFF);
1687                }
1688                /*
1689                 * If this entry was for an empty data block
1690                 * (this should always be true) then update the header.
1691                 */
1692                if (free->bests[findex] == cpu_to_be16(NULLDATAOFF)) {
1693                        be32_add_cpu(&free->hdr.nused, 1);
1694                        xfs_dir2_free_log_header(tp, fbp);
1695                }
1696                /*
1697                 * Update the real value in the table.
1698                 * We haven't allocated the data entry yet so this will
1699                 * change again.
1700                 */
1701                hdr = dbp->b_addr;
1702                free->bests[findex] = hdr->bestfree[0].length;
1703                logfree = 1;
1704        }
1705        /*
1706         * We had a data block so we don't have to make a new one.
1707         */
1708        else {
1709                /*
1710                 * If just checking, we succeeded.
1711                 */
1712                if (args->op_flags & XFS_DA_OP_JUSTCHECK)
1713                        return 0;
1714
1715                /*
1716                 * Read the data block in.
1717                 */
1718                error = xfs_dir2_data_read(tp, dp, xfs_dir2_db_to_da(mp, dbno),
1719                                           -1, &dbp);
1720                if (error)
1721                        return error;
1722                hdr = dbp->b_addr;
1723                logfree = 0;
1724        }
1725        ASSERT(be16_to_cpu(hdr->bestfree[0].length) >= length);
1726        /*
1727         * Point to the existing unused space.
1728         */
1729        dup = (xfs_dir2_data_unused_t *)
1730              ((char *)hdr + be16_to_cpu(hdr->bestfree[0].offset));
1731        needscan = needlog = 0;
1732        /*
1733         * Mark the first part of the unused space, inuse for us.
1734         */
1735        xfs_dir2_data_use_free(tp, dbp, dup,
1736                (xfs_dir2_data_aoff_t)((char *)dup - (char *)hdr), length,
1737                &needlog, &needscan);
1738        /*
1739         * Fill in the new entry and log it.
1740         */
1741        dep = (xfs_dir2_data_entry_t *)dup;
1742        dep->inumber = cpu_to_be64(args->inumber);
1743        dep->namelen = args->namelen;
1744        memcpy(dep->name, args->name, dep->namelen);
1745        tagp = xfs_dir2_data_entry_tag_p(dep);
1746        *tagp = cpu_to_be16((char *)dep - (char *)hdr);
1747        xfs_dir2_data_log_entry(tp, dbp, dep);
1748        /*
1749         * Rescan the block for bestfree if needed.
1750         */
1751        if (needscan)
1752                xfs_dir2_data_freescan(mp, hdr, &needlog);
1753        /*
1754         * Log the data block header if needed.
1755         */
1756        if (needlog)
1757                xfs_dir2_data_log_header(tp, dbp);
1758        /*
1759         * If the freespace entry is now wrong, update it.
1760         */
1761        if (be16_to_cpu(free->bests[findex]) != be16_to_cpu(hdr->bestfree[0].length)) {
1762                free->bests[findex] = hdr->bestfree[0].length;
1763                logfree = 1;
1764        }
1765        /*
1766         * Log the freespace entry if needed.
1767         */
1768        if (logfree)
1769                xfs_dir2_free_log_bests(tp, fbp, findex, findex);
1770        /*
1771         * Return the data block and offset in args, then drop the data block.
1772         */
1773        args->blkno = (xfs_dablk_t)dbno;
1774        args->index = be16_to_cpu(*tagp);
1775        return 0;
1776}
1777
1778/*
1779 * Lookup an entry in a node-format directory.
1780 * All the real work happens in xfs_da_node_lookup_int.
1781 * The only real output is the inode number of the entry.
1782 */
1783int                                             /* error */
1784xfs_dir2_node_lookup(
1785        xfs_da_args_t   *args)                  /* operation arguments */
1786{
1787        int             error;                  /* error return value */
1788        int             i;                      /* btree level */
1789        int             rval;                   /* operation return value */
1790        xfs_da_state_t  *state;                 /* btree cursor */
1791
1792        trace_xfs_dir2_node_lookup(args);
1793
1794        /*
1795         * Allocate and initialize the btree cursor.
1796         */
1797        state = xfs_da_state_alloc();
1798        state->args = args;
1799        state->mp = args->dp->i_mount;
1800        state->blocksize = state->mp->m_dirblksize;
1801        state->node_ents = state->mp->m_dir_node_ents;
1802        /*
1803         * Fill in the path to the entry in the cursor.
1804         */
1805        error = xfs_da_node_lookup_int(state, &rval);
1806        if (error)
1807                rval = error;
1808        else if (rval == ENOENT && args->cmpresult == XFS_CMP_CASE) {
1809                /* If a CI match, dup the actual name and return EEXIST */
1810                xfs_dir2_data_entry_t   *dep;
1811
1812                dep = (xfs_dir2_data_entry_t *)
1813                        ((char *)state->extrablk.bp->b_addr +
1814                                                 state->extrablk.index);
1815                rval = xfs_dir_cilookup_result(args, dep->name, dep->namelen);
1816        }
1817        /*
1818         * Release the btree blocks and leaf block.
1819         */
1820        for (i = 0; i < state->path.active; i++) {
1821                xfs_trans_brelse(args->trans, state->path.blk[i].bp);
1822                state->path.blk[i].bp = NULL;
1823        }
1824        /*
1825         * Release the data block if we have it.
1826         */
1827        if (state->extravalid && state->extrablk.bp) {
1828                xfs_trans_brelse(args->trans, state->extrablk.bp);
1829                state->extrablk.bp = NULL;
1830        }
1831        xfs_da_state_free(state);
1832        return rval;
1833}
1834
1835/*
1836 * Remove an entry from a node-format directory.
1837 */
1838int                                             /* error */
1839xfs_dir2_node_removename(
1840        xfs_da_args_t           *args)          /* operation arguments */
1841{
1842        xfs_da_state_blk_t      *blk;           /* leaf block */
1843        int                     error;          /* error return value */
1844        int                     rval;           /* operation return value */
1845        xfs_da_state_t          *state;         /* btree cursor */
1846
1847        trace_xfs_dir2_node_removename(args);
1848
1849        /*
1850         * Allocate and initialize the btree cursor.
1851         */
1852        state = xfs_da_state_alloc();
1853        state->args = args;
1854        state->mp = args->dp->i_mount;
1855        state->blocksize = state->mp->m_dirblksize;
1856        state->node_ents = state->mp->m_dir_node_ents;
1857        /*
1858         * Look up the entry we're deleting, set up the cursor.
1859         */
1860        error = xfs_da_node_lookup_int(state, &rval);
1861        if (error)
1862                rval = error;
1863        /*
1864         * Didn't find it, upper layer screwed up.
1865         */
1866        if (rval != EEXIST) {
1867                xfs_da_state_free(state);
1868                return rval;
1869        }
1870        blk = &state->path.blk[state->path.active - 1];
1871        ASSERT(blk->magic == XFS_DIR2_LEAFN_MAGIC);
1872        ASSERT(state->extravalid);
1873        /*
1874         * Remove the leaf and data entries.
1875         * Extrablk refers to the data block.
1876         */
1877        error = xfs_dir2_leafn_remove(args, blk->bp, blk->index,
1878                &state->extrablk, &rval);
1879        if (error)
1880                return error;
1881        /*
1882         * Fix the hash values up the btree.
1883         */
1884        xfs_da_fixhashpath(state, &state->path);
1885        /*
1886         * If we need to join leaf blocks, do it.
1887         */
1888        if (rval && state->path.active > 1)
1889                error = xfs_da_join(state);
1890        /*
1891         * If no errors so far, try conversion to leaf format.
1892         */
1893        if (!error)
1894                error = xfs_dir2_node_to_leaf(state);
1895        xfs_da_state_free(state);
1896        return error;
1897}
1898
1899/*
1900 * Replace an entry's inode number in a node-format directory.
1901 */
1902int                                             /* error */
1903xfs_dir2_node_replace(
1904        xfs_da_args_t           *args)          /* operation arguments */
1905{
1906        xfs_da_state_blk_t      *blk;           /* leaf block */
1907        xfs_dir2_data_hdr_t     *hdr;           /* data block header */
1908        xfs_dir2_data_entry_t   *dep;           /* data entry changed */
1909        int                     error;          /* error return value */
1910        int                     i;              /* btree level */
1911        xfs_ino_t               inum;           /* new inode number */
1912        xfs_dir2_leaf_t         *leaf;          /* leaf structure */
1913        xfs_dir2_leaf_entry_t   *lep;           /* leaf entry being changed */
1914        int                     rval;           /* internal return value */
1915        xfs_da_state_t          *state;         /* btree cursor */
1916
1917        trace_xfs_dir2_node_replace(args);
1918
1919        /*
1920         * Allocate and initialize the btree cursor.
1921         */
1922        state = xfs_da_state_alloc();
1923        state->args = args;
1924        state->mp = args->dp->i_mount;
1925        state->blocksize = state->mp->m_dirblksize;
1926        state->node_ents = state->mp->m_dir_node_ents;
1927        inum = args->inumber;
1928        /*
1929         * Lookup the entry to change in the btree.
1930         */
1931        error = xfs_da_node_lookup_int(state, &rval);
1932        if (error) {
1933                rval = error;
1934        }
1935        /*
1936         * It should be found, since the vnodeops layer has looked it up
1937         * and locked it.  But paranoia is good.
1938         */
1939        if (rval == EEXIST) {
1940                /*
1941                 * Find the leaf entry.
1942                 */
1943                blk = &state->path.blk[state->path.active - 1];
1944                ASSERT(blk->magic == XFS_DIR2_LEAFN_MAGIC);
1945                leaf = blk->bp->b_addr;
1946                lep = &leaf->ents[blk->index];
1947                ASSERT(state->extravalid);
1948                /*
1949                 * Point to the data entry.
1950                 */
1951                hdr = state->extrablk.bp->b_addr;
1952                ASSERT(hdr->magic == cpu_to_be32(XFS_DIR2_DATA_MAGIC));
1953                dep = (xfs_dir2_data_entry_t *)
1954                      ((char *)hdr +
1955                       xfs_dir2_dataptr_to_off(state->mp, be32_to_cpu(lep->address)));
1956                ASSERT(inum != be64_to_cpu(dep->inumber));
1957                /*
1958                 * Fill in the new inode number and log the entry.
1959                 */
1960                dep->inumber = cpu_to_be64(inum);
1961                xfs_dir2_data_log_entry(args->trans, state->extrablk.bp, dep);
1962                rval = 0;
1963        }
1964        /*
1965         * Didn't find it, and we're holding a data block.  Drop it.
1966         */
1967        else if (state->extravalid) {
1968                xfs_trans_brelse(args->trans, state->extrablk.bp);
1969                state->extrablk.bp = NULL;
1970        }
1971        /*
1972         * Release all the buffers in the cursor.
1973         */
1974        for (i = 0; i < state->path.active; i++) {
1975                xfs_trans_brelse(args->trans, state->path.blk[i].bp);
1976                state->path.blk[i].bp = NULL;
1977        }
1978        xfs_da_state_free(state);
1979        return rval;
1980}
1981
1982/*
1983 * Trim off a trailing empty freespace block.
1984 * Return (in rvalp) 1 if we did it, 0 if not.
1985 */
1986int                                             /* error */
1987xfs_dir2_node_trim_free(
1988        xfs_da_args_t           *args,          /* operation arguments */
1989        xfs_fileoff_t           fo,             /* free block number */
1990        int                     *rvalp)         /* out: did something */
1991{
1992        struct xfs_buf          *bp;            /* freespace buffer */
1993        xfs_inode_t             *dp;            /* incore directory inode */
1994        int                     error;          /* error return code */
1995        xfs_dir2_free_t         *free;          /* freespace structure */
1996        xfs_mount_t             *mp;            /* filesystem mount point */
1997        xfs_trans_t             *tp;            /* transaction pointer */
1998
1999        dp = args->dp;
2000        mp = dp->i_mount;
2001        tp = args->trans;
2002        /*
2003         * Read the freespace block.
2004         */
2005        error = xfs_dir2_free_try_read(tp, dp, fo, &bp);
2006        if (error)
2007                return error;
2008        /*
2009         * There can be holes in freespace.  If fo is a hole, there's
2010         * nothing to do.
2011         */
2012        if (!bp)
2013                return 0;
2014        free = bp->b_addr;
2015        ASSERT(free->hdr.magic == cpu_to_be32(XFS_DIR2_FREE_MAGIC));
2016        /*
2017         * If there are used entries, there's nothing to do.
2018         */
2019        if (be32_to_cpu(free->hdr.nused) > 0) {
2020                xfs_trans_brelse(tp, bp);
2021                *rvalp = 0;
2022                return 0;
2023        }
2024        /*
2025         * Blow the block away.
2026         */
2027        if ((error =
2028            xfs_dir2_shrink_inode(args, xfs_dir2_da_to_db(mp, (xfs_dablk_t)fo),
2029                    bp))) {
2030                /*
2031                 * Can't fail with ENOSPC since that only happens with no
2032                 * space reservation, when breaking up an extent into two
2033                 * pieces.  This is the last block of an extent.
2034                 */
2035                ASSERT(error != ENOSPC);
2036                xfs_trans_brelse(tp, bp);
2037                return error;
2038        }
2039        /*
2040         * Return that we succeeded.
2041         */
2042        *rvalp = 1;
2043        return 0;
2044}
2045
lxr.linux.no kindly hosted by Redpill Linpro AS, provider of Linux consulting and operations services since 1995.