fs/xfs/xfs_dir2_node.c

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