fs/xfs/libxfs/xfs_dir2_leaf.c

   1 // SPDX-License-Identifier: GPL-2.0
   2 /*
   3  * Copyright (c) 2000-2003,2005 Silicon Graphics, Inc.
   4  * Copyright (c) 2013 Red Hat, Inc.
   5  * All Rights Reserved.
   6  */
   7 #include "xfs.h"
   8 #include "xfs_fs.h"
   9 #include "xfs_format.h"
  10 #include "xfs_log_format.h"
  11 #include "xfs_trans_resv.h"
  12 #include "xfs_mount.h"
  13 #include "xfs_da_format.h"
  14 #include "xfs_da_btree.h"
  15 #include "xfs_inode.h"
  16 #include "xfs_bmap.h"
  17 #include "xfs_dir2.h"
  18 #include "xfs_dir2_priv.h"
  19 #include "xfs_error.h"
  20 #include "xfs_trace.h"
  21 #include "xfs_trans.h"
  22 #include "xfs_buf_item.h"
  23 #include "xfs_cksum.h"
  24 #include "xfs_log.h"
  25
  26 /*
  27  * Local function declarations.
  28  */
  29 static int xfs_dir2_leaf_lookup_int(xfs_da_args_t *args, struct xfs_buf **lbpp,
  30                                     int *indexp, struct xfs_buf **dbpp);
  31 static void xfs_dir3_leaf_log_bests(struct xfs_da_args *args,
  32                                     struct xfs_buf *bp, int first, int last);
  33 static void xfs_dir3_leaf_log_tail(struct xfs_da_args *args,
  34                                    struct xfs_buf *bp);
  35
  36 /*
  37  * Check the internal consistency of a leaf1 block.
  38  * Pop an assert if something is wrong.
  39  */
  40 #ifdef DEBUG
  41 static xfs_failaddr_t
  42 xfs_dir3_leaf1_check(
  43         struct xfs_inode        *dp,
  44         struct xfs_buf          *bp)
  45 {
  46         struct xfs_dir2_leaf    *leaf = bp->b_addr;
  47         struct xfs_dir3_icleaf_hdr leafhdr;
  48
  49         dp->d_ops->leaf_hdr_from_disk(&leafhdr, leaf);
  50
  51         if (leafhdr.magic == XFS_DIR3_LEAF1_MAGIC) {
  52                 struct xfs_dir3_leaf_hdr *leaf3 = bp->b_addr;
  53                 if (be64_to_cpu(leaf3->info.blkno) != bp->b_bn)
  54                         return __this_address;
  55         } else if (leafhdr.magic != XFS_DIR2_LEAF1_MAGIC)
  56                 return __this_address;
  57
  58         return xfs_dir3_leaf_check_int(dp->i_mount, dp, &leafhdr, leaf);
  59 }
  60
  61 static inline void
  62 xfs_dir3_leaf_check(
  63         struct xfs_inode        *dp,
  64         struct xfs_buf          *bp)
  65 {
  66         xfs_failaddr_t          fa;
  67
  68         fa = xfs_dir3_leaf1_check(dp, bp);
  69         if (!fa)
  70                 return;
  71         xfs_corruption_error(__func__, XFS_ERRLEVEL_LOW, dp->i_mount,
  72                         bp->b_addr, BBTOB(bp->b_length), __FILE__, __LINE__,
  73                         fa);
  74         ASSERT(0);
  75 }
  76 #else
  77 #define xfs_dir3_leaf_check(dp, bp)
  78 #endif
  79
  80 xfs_failaddr_t
  81 xfs_dir3_leaf_check_int(
  82         struct xfs_mount        *mp,
  83         struct xfs_inode        *dp,
  84         struct xfs_dir3_icleaf_hdr *hdr,
  85         struct xfs_dir2_leaf    *leaf)
  86 {
  87         struct xfs_dir2_leaf_entry *ents;
  88         xfs_dir2_leaf_tail_t    *ltp;
  89         int                     stale;
  90         int                     i;
  91         const struct xfs_dir_ops *ops;
  92         struct xfs_dir3_icleaf_hdr leafhdr;
  93         struct xfs_da_geometry  *geo = mp->m_dir_geo;
  94
  95         /*
  96          * we can be passed a null dp here from a verifier, so we need to go the
  97          * hard way to get them.
  98          */
  99         ops = xfs_dir_get_ops(mp, dp);
 100
 101         if (!hdr) {
 102                 ops->leaf_hdr_from_disk(&leafhdr, leaf);
 103                 hdr = &leafhdr;
 104         }
 105
 106         ents = ops->leaf_ents_p(leaf);
 107         ltp = xfs_dir2_leaf_tail_p(geo, leaf);
 108
 109         /*
 110          * XXX (dgc): This value is not restrictive enough.
 111          * Should factor in the size of the bests table as well.
 112          * We can deduce a value for that from di_size.
 113          */
 114         if (hdr->count > ops->leaf_max_ents(geo))
 115                 return __this_address;
 116
 117         /* Leaves and bests don't overlap in leaf format. */
 118         if ((hdr->magic == XFS_DIR2_LEAF1_MAGIC ||
 119              hdr->magic == XFS_DIR3_LEAF1_MAGIC) &&
 120             (char *)&ents[hdr->count] > (char *)xfs_dir2_leaf_bests_p(ltp))
 121                 return __this_address;
 122
 123         /* Check hash value order, count stale entries.  */
 124         for (i = stale = 0; i < hdr->count; i++) {
 125                 if (i + 1 < hdr->count) {
 126                         if (be32_to_cpu(ents[i].hashval) >
 127                                         be32_to_cpu(ents[i + 1].hashval))
 128                                 return __this_address;
 129                 }
 130                 if (ents[i].address == cpu_to_be32(XFS_DIR2_NULL_DATAPTR))
 131                         stale++;
 132         }
 133         if (hdr->stale != stale)
 134                 return __this_address;
 135         return NULL;
 136 }
 137
 138 /*
 139  * We verify the magic numbers before decoding the leaf header so that on debug
 140  * kernels we don't get assertion failures in xfs_dir3_leaf_hdr_from_disk() due
 141  * to incorrect magic numbers.
 142  */
 143 static xfs_failaddr_t
 144 xfs_dir3_leaf_verify(
 145         struct xfs_buf          *bp,
 146         uint16_t                magic)
 147 {
 148         struct xfs_mount        *mp = bp->b_target->bt_mount;
 149         struct xfs_dir2_leaf    *leaf = bp->b_addr;
 150
 151         ASSERT(magic == XFS_DIR2_LEAF1_MAGIC || magic == XFS_DIR2_LEAFN_MAGIC);
 152
 153         if (xfs_sb_version_hascrc(&mp->m_sb)) {
 154                 struct xfs_dir3_leaf_hdr *leaf3 = bp->b_addr;
 155                 uint16_t                magic3;
 156
 157                 magic3 = (magic == XFS_DIR2_LEAF1_MAGIC) ? XFS_DIR3_LEAF1_MAGIC
 158                                                          : XFS_DIR3_LEAFN_MAGIC;
 159
 160                 if (leaf3->info.hdr.magic != cpu_to_be16(magic3))
 161                         return __this_address;
 162                 if (!uuid_equal(&leaf3->info.uuid, &mp->m_sb.sb_meta_uuid))
 163                         return __this_address;
 164                 if (be64_to_cpu(leaf3->info.blkno) != bp->b_bn)
 165                         return __this_address;
 166                 if (!xfs_log_check_lsn(mp, be64_to_cpu(leaf3->info.lsn)))
 167                         return __this_address;
 168         } else {
 169                 if (leaf->hdr.info.magic != cpu_to_be16(magic))
 170                         return __this_address;
 171         }
 172
 173         return xfs_dir3_leaf_check_int(mp, NULL, NULL, leaf);
 174 }
 175
 176 static void
 177 __read_verify(
 178         struct xfs_buf  *bp,
 179         uint16_t        magic)
 180 {
 181         struct xfs_mount        *mp = bp->b_target->bt_mount;
 182         xfs_failaddr_t          fa;
 183
 184         if (xfs_sb_version_hascrc(&mp->m_sb) &&
 185              !xfs_buf_verify_cksum(bp, XFS_DIR3_LEAF_CRC_OFF))
 186                 xfs_verifier_error(bp, -EFSBADCRC, __this_address);
 187         else {
 188                 fa = xfs_dir3_leaf_verify(bp, magic);
 189                 if (fa)
 190                         xfs_verifier_error(bp, -EFSCORRUPTED, fa);
 191         }
 192 }
 193
 194 static void
 195 __write_verify(
 196         struct xfs_buf  *bp,
 197         uint16_t        magic)
 198 {
 199         struct xfs_mount        *mp = bp->b_target->bt_mount;
 200         struct xfs_buf_log_item *bip = bp->b_log_item;
 201         struct xfs_dir3_leaf_hdr *hdr3 = bp->b_addr;
 202         xfs_failaddr_t          fa;
 203
 204         fa = xfs_dir3_leaf_verify(bp, magic);
 205         if (fa) {
 206                 xfs_verifier_error(bp, -EFSCORRUPTED, fa);
 207                 return;
 208         }
 209
 210         if (!xfs_sb_version_hascrc(&mp->m_sb))
 211                 return;
 212
 213         if (bip)
 214                 hdr3->info.lsn = cpu_to_be64(bip->bli_item.li_lsn);
 215
 216         xfs_buf_update_cksum(bp, XFS_DIR3_LEAF_CRC_OFF);
 217 }
 218
 219 static xfs_failaddr_t
 220 xfs_dir3_leaf1_verify(
 221         struct xfs_buf  *bp)
 222 {
 223         return xfs_dir3_leaf_verify(bp, XFS_DIR2_LEAF1_MAGIC);
 224 }
 225
 226 static void
 227 xfs_dir3_leaf1_read_verify(
 228         struct xfs_buf  *bp)
 229 {
 230         __read_verify(bp, XFS_DIR2_LEAF1_MAGIC);
 231 }
 232
 233 static void
 234 xfs_dir3_leaf1_write_verify(
 235         struct xfs_buf  *bp)
 236 {
 237         __write_verify(bp, XFS_DIR2_LEAF1_MAGIC);
 238 }
 239
 240 static xfs_failaddr_t
 241 xfs_dir3_leafn_verify(
 242         struct xfs_buf  *bp)
 243 {
 244         return xfs_dir3_leaf_verify(bp, XFS_DIR2_LEAFN_MAGIC);
 245 }
 246
 247 static void
 248 xfs_dir3_leafn_read_verify(
 249         struct xfs_buf  *bp)
 250 {
 251         __read_verify(bp, XFS_DIR2_LEAFN_MAGIC);
 252 }
 253
 254 static void
 255 xfs_dir3_leafn_write_verify(
 256         struct xfs_buf  *bp)
 257 {
 258         __write_verify(bp, XFS_DIR2_LEAFN_MAGIC);
 259 }
 260
 261 const struct xfs_buf_ops xfs_dir3_leaf1_buf_ops = {
 262         .name = "xfs_dir3_leaf1",
 263         .verify_read = xfs_dir3_leaf1_read_verify,
 264         .verify_write = xfs_dir3_leaf1_write_verify,
 265         .verify_struct = xfs_dir3_leaf1_verify,
 266 };
 267
 268 const struct xfs_buf_ops xfs_dir3_leafn_buf_ops = {
 269         .name = "xfs_dir3_leafn",
 270         .verify_read = xfs_dir3_leafn_read_verify,
 271         .verify_write = xfs_dir3_leafn_write_verify,
 272         .verify_struct = xfs_dir3_leafn_verify,
 273 };
 274
 275 int
 276 xfs_dir3_leaf_read(
 277         struct xfs_trans        *tp,
 278         struct xfs_inode        *dp,
 279         xfs_dablk_t             fbno,
 280         xfs_daddr_t             mappedbno,
 281         struct xfs_buf          **bpp)
 282 {
 283         int                     err;
 284
 285         err = xfs_da_read_buf(tp, dp, fbno, mappedbno, bpp,
 286                                 XFS_DATA_FORK, &xfs_dir3_leaf1_buf_ops);
 287         if (!err && tp && *bpp)
 288                 xfs_trans_buf_set_type(tp, *bpp, XFS_BLFT_DIR_LEAF1_BUF);
 289         return err;
 290 }
 291
 292 int
 293 xfs_dir3_leafn_read(
 294         struct xfs_trans        *tp,
 295         struct xfs_inode        *dp,
 296         xfs_dablk_t             fbno,
 297         xfs_daddr_t             mappedbno,
 298         struct xfs_buf          **bpp)
 299 {
 300         int                     err;
 301
 302         err = xfs_da_read_buf(tp, dp, fbno, mappedbno, bpp,
 303                                 XFS_DATA_FORK, &xfs_dir3_leafn_buf_ops);
 304         if (!err && tp && *bpp)
 305                 xfs_trans_buf_set_type(tp, *bpp, XFS_BLFT_DIR_LEAFN_BUF);
 306         return err;
 307 }
 308
 309 /*
 310  * Initialize a new leaf block, leaf1 or leafn magic accepted.
 311  */
 312 static void
 313 xfs_dir3_leaf_init(
 314         struct xfs_mount        *mp,
 315         struct xfs_trans        *tp,
 316         struct xfs_buf          *bp,
 317         xfs_ino_t               owner,
 318         uint16_t                type)
 319 {
 320         struct xfs_dir2_leaf    *leaf = bp->b_addr;
 321
 322         ASSERT(type == XFS_DIR2_LEAF1_MAGIC || type == XFS_DIR2_LEAFN_MAGIC);
 323
 324         if (xfs_sb_version_hascrc(&mp->m_sb)) {
 325                 struct xfs_dir3_leaf_hdr *leaf3 = bp->b_addr;
 326
 327                 memset(leaf3, 0, sizeof(*leaf3));
 328
 329                 leaf3->info.hdr.magic = (type == XFS_DIR2_LEAF1_MAGIC)
 330                                          ? cpu_to_be16(XFS_DIR3_LEAF1_MAGIC)
 331                                          : cpu_to_be16(XFS_DIR3_LEAFN_MAGIC);
 332                 leaf3->info.blkno = cpu_to_be64(bp->b_bn);
 333                 leaf3->info.owner = cpu_to_be64(owner);
 334                 uuid_copy(&leaf3->info.uuid, &mp->m_sb.sb_meta_uuid);
 335         } else {
 336                 memset(leaf, 0, sizeof(*leaf));
 337                 leaf->hdr.info.magic = cpu_to_be16(type);
 338         }
 339
 340         /*
 341          * If it's a leaf-format directory initialize the tail.
 342          * Caller is responsible for initialising the bests table.
 343          */
 344         if (type == XFS_DIR2_LEAF1_MAGIC) {
 345                 struct xfs_dir2_leaf_tail *ltp;
 346
 347                 ltp = xfs_dir2_leaf_tail_p(mp->m_dir_geo, leaf);
 348                 ltp->bestcount = 0;
 349                 bp->b_ops = &xfs_dir3_leaf1_buf_ops;
 350                 xfs_trans_buf_set_type(tp, bp, XFS_BLFT_DIR_LEAF1_BUF);
 351         } else {
 352                 bp->b_ops = &xfs_dir3_leafn_buf_ops;
 353                 xfs_trans_buf_set_type(tp, bp, XFS_BLFT_DIR_LEAFN_BUF);
 354         }
 355 }
 356
 357 int
 358 xfs_dir3_leaf_get_buf(
 359         xfs_da_args_t           *args,
 360         xfs_dir2_db_t           bno,
 361         struct xfs_buf          **bpp,
 362         uint16_t                magic)
 363 {
 364         struct xfs_inode        *dp = args->dp;
 365         struct xfs_trans        *tp = args->trans;
 366         struct xfs_mount        *mp = dp->i_mount;
 367         struct xfs_buf          *bp;
 368         int                     error;
 369
 370         ASSERT(magic == XFS_DIR2_LEAF1_MAGIC || magic == XFS_DIR2_LEAFN_MAGIC);
 371         ASSERT(bno >= xfs_dir2_byte_to_db(args->geo, XFS_DIR2_LEAF_OFFSET) &&
 372                bno < xfs_dir2_byte_to_db(args->geo, XFS_DIR2_FREE_OFFSET));
 373
 374         error = xfs_da_get_buf(tp, dp, xfs_dir2_db_to_da(args->geo, bno),
 375                                -1, &bp, XFS_DATA_FORK);
 376         if (error)
 377                 return error;
 378
 379         xfs_dir3_leaf_init(mp, tp, bp, dp->i_ino, magic);
 380         xfs_dir3_leaf_log_header(args, bp);
 381         if (magic == XFS_DIR2_LEAF1_MAGIC)
 382                 xfs_dir3_leaf_log_tail(args, bp);
 383         *bpp = bp;
 384         return 0;
 385 }
 386
 387 /*
 388  * Convert a block form directory to a leaf form directory.
 389  */
 390 int                                             /* error */
 391 xfs_dir2_block_to_leaf(
 392         xfs_da_args_t           *args,          /* operation arguments */
 393         struct xfs_buf          *dbp)           /* input block's buffer */
 394 {
 395         __be16                  *bestsp;        /* leaf's bestsp entries */
 396         xfs_dablk_t             blkno;          /* leaf block's bno */
 397         xfs_dir2_data_hdr_t     *hdr;           /* block header */
 398         xfs_dir2_leaf_entry_t   *blp;           /* block's leaf entries */
 399         xfs_dir2_block_tail_t   *btp;           /* block's tail */
 400         xfs_inode_t             *dp;            /* incore directory inode */
 401         int                     error;          /* error return code */
 402         struct xfs_buf          *lbp;           /* leaf block's buffer */
 403         xfs_dir2_db_t           ldb;            /* leaf block's bno */
 404         xfs_dir2_leaf_t         *leaf;          /* leaf structure */
 405         xfs_dir2_leaf_tail_t    *ltp;           /* leaf's tail */
 406         int                     needlog;        /* need to log block header */
 407         int                     needscan;       /* need to rescan bestfree */
 408         xfs_trans_t             *tp;            /* transaction pointer */
 409         struct xfs_dir2_data_free *bf;
 410         struct xfs_dir2_leaf_entry *ents;
 411         struct xfs_dir3_icleaf_hdr leafhdr;
 412
 413         trace_xfs_dir2_block_to_leaf(args);
 414
 415         dp = args->dp;
 416         tp = args->trans;
 417         /*
 418          * Add the leaf block to the inode.
 419          * This interface will only put blocks in the leaf/node range.
 420          * Since that's empty now, we'll get the root (block 0 in range).
 421          */
 422         if ((error = xfs_da_grow_inode(args, &blkno))) {
 423                 return error;
 424         }
 425         ldb = xfs_dir2_da_to_db(args->geo, blkno);
 426         ASSERT(ldb == xfs_dir2_byte_to_db(args->geo, XFS_DIR2_LEAF_OFFSET));
 427         /*
 428          * Initialize the leaf block, get a buffer for it.
 429          */
 430         error = xfs_dir3_leaf_get_buf(args, ldb, &lbp, XFS_DIR2_LEAF1_MAGIC);
 431         if (error)
 432                 return error;
 433
 434         leaf = lbp->b_addr;
 435         hdr = dbp->b_addr;
 436         xfs_dir3_data_check(dp, dbp);
 437         btp = xfs_dir2_block_tail_p(args->geo, hdr);
 438         blp = xfs_dir2_block_leaf_p(btp);
 439         bf = dp->d_ops->data_bestfree_p(hdr);
 440         ents = dp->d_ops->leaf_ents_p(leaf);
 441
 442         /*
 443          * Set the counts in the leaf header.
 444          */
 445         dp->d_ops->leaf_hdr_from_disk(&leafhdr, leaf);
 446         leafhdr.count = be32_to_cpu(btp->count);
 447         leafhdr.stale = be32_to_cpu(btp->stale);
 448         dp->d_ops->leaf_hdr_to_disk(leaf, &leafhdr);
 449         xfs_dir3_leaf_log_header(args, lbp);
 450
 451         /*
 452          * Could compact these but I think we always do the conversion
 453          * after squeezing out stale entries.
 454          */
 455         memcpy(ents, blp, be32_to_cpu(btp->count) * sizeof(xfs_dir2_leaf_entry_t));
 456         xfs_dir3_leaf_log_ents(args, lbp, 0, leafhdr.count - 1);
 457         needscan = 0;
 458         needlog = 1;
 459         /*
 460          * Make the space formerly occupied by the leaf entries and block
 461          * tail be free.
 462          */
 463         xfs_dir2_data_make_free(args, dbp,
 464                 (xfs_dir2_data_aoff_t)((char *)blp - (char *)hdr),
 465                 (xfs_dir2_data_aoff_t)((char *)hdr + args->geo->blksize -
 466                                        (char *)blp),
 467                 &needlog, &needscan);
 468         /*
 469          * Fix up the block header, make it a data block.
 470          */
 471         dbp->b_ops = &xfs_dir3_data_buf_ops;
 472         xfs_trans_buf_set_type(tp, dbp, XFS_BLFT_DIR_DATA_BUF);
 473         if (hdr->magic == cpu_to_be32(XFS_DIR2_BLOCK_MAGIC))
 474                 hdr->magic = cpu_to_be32(XFS_DIR2_DATA_MAGIC);
 475         else
 476                 hdr->magic = cpu_to_be32(XFS_DIR3_DATA_MAGIC);
 477
 478         if (needscan)
 479                 xfs_dir2_data_freescan(dp, hdr, &needlog);
 480         /*
 481          * Set up leaf tail and bests table.
 482          */
 483         ltp = xfs_dir2_leaf_tail_p(args->geo, leaf);
 484         ltp->bestcount = cpu_to_be32(1);
 485         bestsp = xfs_dir2_leaf_bests_p(ltp);
 486         bestsp[0] =  bf[0].length;
 487         /*
 488          * Log the data header and leaf bests table.
 489          */
 490         if (needlog)
 491                 xfs_dir2_data_log_header(args, dbp);
 492         xfs_dir3_leaf_check(dp, lbp);
 493         xfs_dir3_data_check(dp, dbp);
 494         xfs_dir3_leaf_log_bests(args, lbp, 0, 0);
 495         return 0;
 496 }
 497
 498 STATIC void
 499 xfs_dir3_leaf_find_stale(
 500         struct xfs_dir3_icleaf_hdr *leafhdr,
 501         struct xfs_dir2_leaf_entry *ents,
 502         int                     index,
 503         int                     *lowstale,
 504         int                     *highstale)
 505 {
 506         /*
 507          * Find the first stale entry before our index, if any.
 508          */
 509         for (*lowstale = index - 1; *lowstale >= 0; --*lowstale) {
 510                 if (ents[*lowstale].address ==
 511                     cpu_to_be32(XFS_DIR2_NULL_DATAPTR))
 512                         break;
 513         }
 514
 515         /*
 516          * Find the first stale entry at or after our index, if any.
 517          * Stop if the result would require moving more entries than using
 518          * lowstale.
 519          */
 520         for (*highstale = index; *highstale < leafhdr->count; ++*highstale) {
 521                 if (ents[*highstale].address ==
 522                     cpu_to_be32(XFS_DIR2_NULL_DATAPTR))
 523                         break;
 524                 if (*lowstale >= 0 && index - *lowstale <= *highstale - index)
 525                         break;
 526         }
 527 }
 528
 529 struct xfs_dir2_leaf_entry *
 530 xfs_dir3_leaf_find_entry(
 531         struct xfs_dir3_icleaf_hdr *leafhdr,
 532         struct xfs_dir2_leaf_entry *ents,
 533         int                     index,          /* leaf table position */
 534         int                     compact,        /* need to compact leaves */
 535         int                     lowstale,       /* index of prev stale leaf */
 536         int                     highstale,      /* index of next stale leaf */
 537         int                     *lfloglow,      /* low leaf logging index */
 538         int                     *lfloghigh)     /* high leaf logging index */
 539 {
 540         if (!leafhdr->stale) {
 541                 xfs_dir2_leaf_entry_t   *lep;   /* leaf entry table pointer */
 542
 543                 /*
 544                  * Now we need to make room to insert the leaf entry.
 545                  *
 546                  * If there are no stale entries, just insert a hole at index.
 547                  */
 548                 lep = &ents[index];
 549                 if (index < leafhdr->count)
 550                         memmove(lep + 1, lep,
 551                                 (leafhdr->count - index) * sizeof(*lep));
 552
 553                 /*
 554                  * Record low and high logging indices for the leaf.
 555                  */
 556                 *lfloglow = index;
 557                 *lfloghigh = leafhdr->count++;
 558                 return lep;
 559         }
 560
 561         /*
 562          * There are stale entries.
 563          *
 564          * We will use one of them for the new entry.  It's probably not at
 565          * the right location, so we'll have to shift some up or down first.
 566          *
 567          * If we didn't compact before, we need to find the nearest stale
 568          * entries before and after our insertion point.
 569          */
 570         if (compact == 0)
 571                 xfs_dir3_leaf_find_stale(leafhdr, ents, index,
 572                                          &lowstale, &highstale);
 573
 574         /*
 575          * If the low one is better, use it.
 576          */
 577         if (lowstale >= 0 &&
 578             (highstale == leafhdr->count ||
 579              index - lowstale - 1 < highstale - index)) {
 580                 ASSERT(index - lowstale - 1 >= 0);
 581                 ASSERT(ents[lowstale].address ==
 582                        cpu_to_be32(XFS_DIR2_NULL_DATAPTR));
 583
 584                 /*
 585                  * Copy entries up to cover the stale entry and make room
 586                  * for the new entry.
 587                  */
 588                 if (index - lowstale - 1 > 0) {
 589                         memmove(&ents[lowstale], &ents[lowstale + 1],
 590                                 (index - lowstale - 1) *
 591                                         sizeof(xfs_dir2_leaf_entry_t));
 592                 }
 593                 *lfloglow = min(lowstale, *lfloglow);
 594                 *lfloghigh = max(index - 1, *lfloghigh);
 595                 leafhdr->stale--;
 596                 return &ents[index - 1];
 597         }
 598
 599         /*
 600          * The high one is better, so use that one.
 601          */
 602         ASSERT(highstale - index >= 0);
 603         ASSERT(ents[highstale].address == cpu_to_be32(XFS_DIR2_NULL_DATAPTR));
 604
 605         /*
 606          * Copy entries down to cover the stale entry and make room for the
 607          * new entry.
 608          */
 609         if (highstale - index > 0) {
 610                 memmove(&ents[index + 1], &ents[index],
 611                         (highstale - index) * sizeof(xfs_dir2_leaf_entry_t));
 612         }
 613         *lfloglow = min(index, *lfloglow);
 614         *lfloghigh = max(highstale, *lfloghigh);
 615         leafhdr->stale--;
 616         return &ents[index];
 617 }
 618
 619 /*
 620  * Add an entry to a leaf form directory.
 621  */
 622 int                                             /* error */
 623 xfs_dir2_leaf_addname(
 624         xfs_da_args_t           *args)          /* operation arguments */
 625 {
 626         __be16                  *bestsp;        /* freespace table in leaf */
 627         int                     compact;        /* need to compact leaves */
 628         xfs_dir2_data_hdr_t     *hdr;           /* data block header */
 629         struct xfs_buf          *dbp;           /* data block buffer */
 630         xfs_dir2_data_entry_t   *dep;           /* data block entry */
 631         xfs_inode_t             *dp;            /* incore directory inode */
 632         xfs_dir2_data_unused_t  *dup;           /* data unused entry */
 633         int                     error;          /* error return value */
 634         int                     grown;          /* allocated new data block */
 635         int                     highstale;      /* index of next stale leaf */
 636         int                     i;              /* temporary, index */
 637         int                     index;          /* leaf table position */
 638         struct xfs_buf          *lbp;           /* leaf's buffer */
 639         xfs_dir2_leaf_t         *leaf;          /* leaf structure */
 640         int                     length;         /* length of new entry */
 641         xfs_dir2_leaf_entry_t   *lep;           /* leaf entry table pointer */
 642         int                     lfloglow;       /* low leaf logging index */
 643         int                     lfloghigh;      /* high leaf logging index */
 644         int                     lowstale;       /* index of prev stale leaf */
 645         xfs_dir2_leaf_tail_t    *ltp;           /* leaf tail pointer */
 646         int                     needbytes;      /* leaf block bytes needed */
 647         int                     needlog;        /* need to log data header */
 648         int                     needscan;       /* need to rescan data free */
 649         __be16                  *tagp;          /* end of data entry */
 650         xfs_trans_t             *tp;            /* transaction pointer */
 651         xfs_dir2_db_t           use_block;      /* data block number */
 652         struct xfs_dir2_data_free *bf;          /* bestfree table */
 653         struct xfs_dir2_leaf_entry *ents;
 654         struct xfs_dir3_icleaf_hdr leafhdr;
 655
 656         trace_xfs_dir2_leaf_addname(args);
 657
 658         dp = args->dp;
 659         tp = args->trans;
 660
 661         error = xfs_dir3_leaf_read(tp, dp, args->geo->leafblk, -1, &lbp);
 662         if (error)
 663                 return error;
 664
 665         /*
 666          * Look up the entry by hash value and name.
 667          * We know it's not there, our caller has already done a lookup.
 668          * So the index is of the entry to insert in front of.
 669          * But if there are dup hash values the index is of the first of those.
 670          */
 671         index = xfs_dir2_leaf_search_hash(args, lbp);
 672         leaf = lbp->b_addr;
 673         ltp = xfs_dir2_leaf_tail_p(args->geo, leaf);
 674         ents = dp->d_ops->leaf_ents_p(leaf);
 675         dp->d_ops->leaf_hdr_from_disk(&leafhdr, leaf);
 676         bestsp = xfs_dir2_leaf_bests_p(ltp);
 677         length = dp->d_ops->data_entsize(args->namelen);
 678
 679         /*
 680          * See if there are any entries with the same hash value
 681          * and space in their block for the new entry.
 682          * This is good because it puts multiple same-hash value entries
 683          * in a data block, improving the lookup of those entries.
 684          */
 685         for (use_block = -1, lep = &ents[index];
 686              index < leafhdr.count && be32_to_cpu(lep->hashval) == args->hashval;
 687              index++, lep++) {
 688                 if (be32_to_cpu(lep->address) == XFS_DIR2_NULL_DATAPTR)
 689                         continue;
 690                 i = xfs_dir2_dataptr_to_db(args->geo, be32_to_cpu(lep->address));
 691                 ASSERT(i < be32_to_cpu(ltp->bestcount));
 692                 ASSERT(bestsp[i] != cpu_to_be16(NULLDATAOFF));
 693                 if (be16_to_cpu(bestsp[i]) >= length) {
 694                         use_block = i;
 695                         break;
 696                 }
 697         }
 698         /*
 699          * Didn't find a block yet, linear search all the data blocks.
 700          */
 701         if (use_block == -1) {
 702                 for (i = 0; i < be32_to_cpu(ltp->bestcount); i++) {
 703                         /*
 704                          * Remember a block we see that's missing.
 705                          */
 706                         if (bestsp[i] == cpu_to_be16(NULLDATAOFF) &&
 707                             use_block == -1)
 708                                 use_block = i;
 709                         else if (be16_to_cpu(bestsp[i]) >= length) {
 710                                 use_block = i;
 711                                 break;
 712                         }
 713                 }
 714         }
 715         /*
 716          * How many bytes do we need in the leaf block?
 717          */
 718         needbytes = 0;
 719         if (!leafhdr.stale)
 720                 needbytes += sizeof(xfs_dir2_leaf_entry_t);
 721         if (use_block == -1)
 722                 needbytes += sizeof(xfs_dir2_data_off_t);
 723
 724         /*
 725          * Now kill use_block if it refers to a missing block, so we
 726          * can use it as an indication of allocation needed.
 727          */
 728         if (use_block != -1 && bestsp[use_block] == cpu_to_be16(NULLDATAOFF))
 729                 use_block = -1;
 730         /*
 731          * If we don't have enough free bytes but we can make enough
 732          * by compacting out stale entries, we'll do that.
 733          */
 734         if ((char *)bestsp - (char *)&ents[leafhdr.count] < needbytes &&
 735             leafhdr.stale > 1)
 736                 compact = 1;
 737
 738         /*
 739          * Otherwise if we don't have enough free bytes we need to
 740          * convert to node form.
 741          */
 742         else if ((char *)bestsp - (char *)&ents[leafhdr.count] < needbytes) {
 743                 /*
 744                  * Just checking or no space reservation, give up.
 745                  */
 746                 if ((args->op_flags & XFS_DA_OP_JUSTCHECK) ||
 747                                                         args->total == 0) {
 748                         xfs_trans_brelse(tp, lbp);
 749                         return -ENOSPC;
 750                 }
 751                 /*
 752                  * Convert to node form.
 753                  */
 754                 error = xfs_dir2_leaf_to_node(args, lbp);
 755                 if (error)
 756                         return error;
 757                 /*
 758                  * Then add the new entry.
 759                  */
 760                 return xfs_dir2_node_addname(args);
 761         }
 762         /*
 763          * Otherwise it will fit without compaction.
 764          */
 765         else
 766                 compact = 0;
 767         /*
 768          * If just checking, then it will fit unless we needed to allocate
 769          * a new data block.
 770          */
 771         if (args->op_flags & XFS_DA_OP_JUSTCHECK) {
 772                 xfs_trans_brelse(tp, lbp);
 773                 return use_block == -1 ? -ENOSPC : 0;
 774         }
 775         /*
 776          * If no allocations are allowed, return now before we've
 777          * changed anything.
 778          */
 779         if (args->total == 0 && use_block == -1) {
 780                 xfs_trans_brelse(tp, lbp);
 781                 return -ENOSPC;
 782         }
 783         /*
 784          * Need to compact the leaf entries, removing stale ones.
 785          * Leave one stale entry behind - the one closest to our
 786          * insertion index - and we'll shift that one to our insertion
 787          * point later.
 788          */
 789         if (compact) {
 790                 xfs_dir3_leaf_compact_x1(&leafhdr, ents, &index, &lowstale,
 791                         &highstale, &lfloglow, &lfloghigh);
 792         }
 793         /*
 794          * There are stale entries, so we'll need log-low and log-high
 795          * impossibly bad values later.
 796          */
 797         else if (leafhdr.stale) {
 798                 lfloglow = leafhdr.count;
 799                 lfloghigh = -1;
 800         }
 801         /*
 802          * If there was no data block space found, we need to allocate
 803          * a new one.
 804          */
 805         if (use_block == -1) {
 806                 /*
 807                  * Add the new data block.
 808                  */
 809                 if ((error = xfs_dir2_grow_inode(args, XFS_DIR2_DATA_SPACE,
 810                                 &use_block))) {
 811                         xfs_trans_brelse(tp, lbp);
 812                         return error;
 813                 }
 814                 /*
 815                  * Initialize the block.
 816                  */
 817                 if ((error = xfs_dir3_data_init(args, use_block, &dbp))) {
 818                         xfs_trans_brelse(tp, lbp);
 819                         return error;
 820                 }
 821                 /*
 822                  * If we're adding a new data block on the end we need to
 823                  * extend the bests table.  Copy it up one entry.
 824                  */
 825                 if (use_block >= be32_to_cpu(ltp->bestcount)) {
 826                         bestsp--;
 827                         memmove(&bestsp[0], &bestsp[1],
 828                                 be32_to_cpu(ltp->bestcount) * sizeof(bestsp[0]));
 829                         be32_add_cpu(&ltp->bestcount, 1);
 830                         xfs_dir3_leaf_log_tail(args, lbp);
 831                         xfs_dir3_leaf_log_bests(args, lbp, 0,
 832                                                 be32_to_cpu(ltp->bestcount) - 1);
 833                 }
 834                 /*
 835                  * If we're filling in a previously empty block just log it.
 836                  */
 837                 else
 838                         xfs_dir3_leaf_log_bests(args, lbp, use_block, use_block);
 839                 hdr = dbp->b_addr;
 840                 bf = dp->d_ops->data_bestfree_p(hdr);
 841                 bestsp[use_block] = bf[0].length;
 842                 grown = 1;
 843         } else {
 844                 /*
 845                  * Already had space in some data block.
 846                  * Just read that one in.
 847                  */
 848                 error = xfs_dir3_data_read(tp, dp,
 849                                    xfs_dir2_db_to_da(args->geo, use_block),
 850                                    -1, &dbp);
 851                 if (error) {
 852                         xfs_trans_brelse(tp, lbp);
 853                         return error;
 854                 }
 855                 hdr = dbp->b_addr;
 856                 bf = dp->d_ops->data_bestfree_p(hdr);
 857                 grown = 0;
 858         }
 859         /*
 860          * Point to the biggest freespace in our data block.
 861          */
 862         dup = (xfs_dir2_data_unused_t *)
 863               ((char *)hdr + be16_to_cpu(bf[0].offset));
 864         needscan = needlog = 0;
 865         /*
 866          * Mark the initial part of our freespace in use for the new entry.
 867          */
 868         error = xfs_dir2_data_use_free(args, dbp, dup,
 869                         (xfs_dir2_data_aoff_t)((char *)dup - (char *)hdr),
 870                         length, &needlog, &needscan);
 871         if (error) {
 872                 xfs_trans_brelse(tp, lbp);
 873                 return error;
 874         }
 875         /*
 876          * Initialize our new entry (at last).
 877          */
 878         dep = (xfs_dir2_data_entry_t *)dup;
 879         dep->inumber = cpu_to_be64(args->inumber);
 880         dep->namelen = args->namelen;
 881         memcpy(dep->name, args->name, dep->namelen);
 882         dp->d_ops->data_put_ftype(dep, args->filetype);
 883         tagp = dp->d_ops->data_entry_tag_p(dep);
 884         *tagp = cpu_to_be16((char *)dep - (char *)hdr);
 885         /*
 886          * Need to scan fix up the bestfree table.
 887          */
 888         if (needscan)
 889                 xfs_dir2_data_freescan(dp, hdr, &needlog);
 890         /*
 891          * Need to log the data block's header.
 892          */
 893         if (needlog)
 894                 xfs_dir2_data_log_header(args, dbp);
 895         xfs_dir2_data_log_entry(args, dbp, dep);
 896         /*
 897          * If the bests table needs to be changed, do it.
 898          * Log the change unless we've already done that.
 899          */
 900         if (be16_to_cpu(bestsp[use_block]) != be16_to_cpu(bf[0].length)) {
 901                 bestsp[use_block] = bf[0].length;
 902                 if (!grown)
 903                         xfs_dir3_leaf_log_bests(args, lbp, use_block, use_block);
 904         }
 905
 906         lep = xfs_dir3_leaf_find_entry(&leafhdr, ents, index, compact, lowstale,
 907                                        highstale, &lfloglow, &lfloghigh);
 908
 909         /*
 910          * Fill in the new leaf entry.
 911          */
 912         lep->hashval = cpu_to_be32(args->hashval);
 913         lep->address = cpu_to_be32(
 914                                 xfs_dir2_db_off_to_dataptr(args->geo, use_block,
 915                                 be16_to_cpu(*tagp)));
 916         /*
 917          * Log the leaf fields and give up the buffers.
 918          */
 919         dp->d_ops->leaf_hdr_to_disk(leaf, &leafhdr);
 920         xfs_dir3_leaf_log_header(args, lbp);
 921         xfs_dir3_leaf_log_ents(args, lbp, lfloglow, lfloghigh);
 922         xfs_dir3_leaf_check(dp, lbp);
 923         xfs_dir3_data_check(dp, dbp);
 924         return 0;
 925 }
 926
 927 /*
 928  * Compact out any stale entries in the leaf.
 929  * Log the header and changed leaf entries, if any.
 930  */
 931 void
 932 xfs_dir3_leaf_compact(
 933         xfs_da_args_t   *args,          /* operation arguments */
 934         struct xfs_dir3_icleaf_hdr *leafhdr,
 935         struct xfs_buf  *bp)            /* leaf buffer */
 936 {
 937         int             from;           /* source leaf index */
 938         xfs_dir2_leaf_t *leaf;          /* leaf structure */
 939         int             loglow;         /* first leaf entry to log */
 940         int             to;             /* target leaf index */
 941         struct xfs_dir2_leaf_entry *ents;
 942         struct xfs_inode *dp = args->dp;
 943
 944         leaf = bp->b_addr;
 945         if (!leafhdr->stale)
 946                 return;
 947
 948         /*
 949          * Compress out the stale entries in place.
 950          */
 951         ents = dp->d_ops->leaf_ents_p(leaf);
 952         for (from = to = 0, loglow = -1; from < leafhdr->count; from++) {
 953                 if (ents[from].address == cpu_to_be32(XFS_DIR2_NULL_DATAPTR))
 954                         continue;
 955                 /*
 956                  * Only actually copy the entries that are different.
 957                  */
 958                 if (from > to) {
 959                         if (loglow == -1)
 960                                 loglow = to;
 961                         ents[to] = ents[from];
 962                 }
 963                 to++;
 964         }
 965         /*
 966          * Update and log the header, log the leaf entries.
 967          */
 968         ASSERT(leafhdr->stale == from - to);
 969         leafhdr->count -= leafhdr->stale;
 970         leafhdr->stale = 0;
 971
 972         dp->d_ops->leaf_hdr_to_disk(leaf, leafhdr);
 973         xfs_dir3_leaf_log_header(args, bp);
 974         if (loglow != -1)
 975                 xfs_dir3_leaf_log_ents(args, bp, loglow, to - 1);
 976 }
 977
 978 /*
 979  * Compact the leaf entries, removing stale ones.
 980  * Leave one stale entry behind - the one closest to our
 981  * insertion index - and the caller will shift that one to our insertion
 982  * point later.
 983  * Return new insertion index, where the remaining stale entry is,
 984  * and leaf logging indices.
 985  */
 986 void
 987 xfs_dir3_leaf_compact_x1(
 988         struct xfs_dir3_icleaf_hdr *leafhdr,
 989         struct xfs_dir2_leaf_entry *ents,
 990         int             *indexp,        /* insertion index */
 991         int             *lowstalep,     /* out: stale entry before us */
 992         int             *highstalep,    /* out: stale entry after us */
 993         int             *lowlogp,       /* out: low log index */
 994         int             *highlogp)      /* out: high log index */
 995 {
 996         int             from;           /* source copy index */
 997         int             highstale;      /* stale entry at/after index */
 998         int             index;          /* insertion index */
 999         int             keepstale;      /* source index of kept stale */
1000         int             lowstale;       /* stale entry before index */
1001         int             newindex=0;     /* new insertion index */
1002         int             to;             /* destination copy index */
1003
1004         ASSERT(leafhdr->stale > 1);
1005         index = *indexp;
1006
1007         xfs_dir3_leaf_find_stale(leafhdr, ents, index, &lowstale, &highstale);
1008
1009         /*
1010          * Pick the better of lowstale and highstale.
1011          */
1012         if (lowstale >= 0 &&
1013             (highstale == leafhdr->count ||
1014              index - lowstale <= highstale - index))
1015                 keepstale = lowstale;
1016         else
1017                 keepstale = highstale;
1018         /*
1019          * Copy the entries in place, removing all the stale entries
1020          * except keepstale.
1021          */
1022         for (from = to = 0; from < leafhdr->count; from++) {
1023                 /*
1024                  * Notice the new value of index.
1025                  */
1026                 if (index == from)
1027                         newindex = to;
1028                 if (from != keepstale &&
1029                     ents[from].address == cpu_to_be32(XFS_DIR2_NULL_DATAPTR)) {
1030                         if (from == to)
1031                                 *lowlogp = to;
1032                         continue;
1033                 }
1034                 /*
1035                  * Record the new keepstale value for the insertion.
1036                  */
1037                 if (from == keepstale)
1038                         lowstale = highstale = to;
1039                 /*
1040                  * Copy only the entries that have moved.
1041                  */
1042                 if (from > to)
1043                         ents[to] = ents[from];
1044                 to++;
1045         }
1046         ASSERT(from > to);
1047         /*
1048          * If the insertion point was past the last entry,
1049          * set the new insertion point accordingly.
1050          */
1051         if (index == from)
1052                 newindex = to;
1053         *indexp = newindex;
1054         /*
1055          * Adjust the leaf header values.
1056          */
1057         leafhdr->count -= from - to;
1058         leafhdr->stale = 1;
1059         /*
1060          * Remember the low/high stale value only in the "right"
1061          * direction.
1062          */
1063         if (lowstale >= newindex)
1064                 lowstale = -1;
1065         else
1066                 highstale = leafhdr->count;
1067         *highlogp = leafhdr->count - 1;
1068         *lowstalep = lowstale;
1069         *highstalep = highstale;
1070 }
1071
1072 /*
1073  * Log the bests entries indicated from a leaf1 block.
1074  */
1075 static void
1076 xfs_dir3_leaf_log_bests(
1077         struct xfs_da_args      *args,
1078         struct xfs_buf          *bp,            /* leaf buffer */
1079         int                     first,          /* first entry to log */
1080         int                     last)           /* last entry to log */
1081 {
1082         __be16                  *firstb;        /* pointer to first entry */
1083         __be16                  *lastb;         /* pointer to last entry */
1084         struct xfs_dir2_leaf    *leaf = bp->b_addr;
1085         xfs_dir2_leaf_tail_t    *ltp;           /* leaf tail structure */
1086
1087         ASSERT(leaf->hdr.info.magic == cpu_to_be16(XFS_DIR2_LEAF1_MAGIC) ||
1088                leaf->hdr.info.magic == cpu_to_be16(XFS_DIR3_LEAF1_MAGIC));
1089
1090         ltp = xfs_dir2_leaf_tail_p(args->geo, leaf);
1091         firstb = xfs_dir2_leaf_bests_p(ltp) + first;
1092         lastb = xfs_dir2_leaf_bests_p(ltp) + last;
1093         xfs_trans_log_buf(args->trans, bp,
1094                 (uint)((char *)firstb - (char *)leaf),
1095                 (uint)((char *)lastb - (char *)leaf + sizeof(*lastb) - 1));
1096 }
1097
1098 /*
1099  * Log the leaf entries indicated from a leaf1 or leafn block.
1100  */
1101 void
1102 xfs_dir3_leaf_log_ents(
1103         struct xfs_da_args      *args,
1104         struct xfs_buf          *bp,
1105         int                     first,
1106         int                     last)
1107 {
1108         xfs_dir2_leaf_entry_t   *firstlep;      /* pointer to first entry */
1109         xfs_dir2_leaf_entry_t   *lastlep;       /* pointer to last entry */
1110         struct xfs_dir2_leaf    *leaf = bp->b_addr;
1111         struct xfs_dir2_leaf_entry *ents;
1112
1113         ASSERT(leaf->hdr.info.magic == cpu_to_be16(XFS_DIR2_LEAF1_MAGIC) ||
1114                leaf->hdr.info.magic == cpu_to_be16(XFS_DIR3_LEAF1_MAGIC) ||
1115                leaf->hdr.info.magic == cpu_to_be16(XFS_DIR2_LEAFN_MAGIC) ||
1116                leaf->hdr.info.magic == cpu_to_be16(XFS_DIR3_LEAFN_MAGIC));
1117
1118         ents = args->dp->d_ops->leaf_ents_p(leaf);
1119         firstlep = &ents[first];
1120         lastlep = &ents[last];
1121         xfs_trans_log_buf(args->trans, bp,
1122                 (uint)((char *)firstlep - (char *)leaf),
1123                 (uint)((char *)lastlep - (char *)leaf + sizeof(*lastlep) - 1));
1124 }
1125
1126 /*
1127  * Log the header of the leaf1 or leafn block.
1128  */
1129 void
1130 xfs_dir3_leaf_log_header(
1131         struct xfs_da_args      *args,
1132         struct xfs_buf          *bp)
1133 {
1134         struct xfs_dir2_leaf    *leaf = bp->b_addr;
1135
1136         ASSERT(leaf->hdr.info.magic == cpu_to_be16(XFS_DIR2_LEAF1_MAGIC) ||
1137                leaf->hdr.info.magic == cpu_to_be16(XFS_DIR3_LEAF1_MAGIC) ||
1138                leaf->hdr.info.magic == cpu_to_be16(XFS_DIR2_LEAFN_MAGIC) ||
1139                leaf->hdr.info.magic == cpu_to_be16(XFS_DIR3_LEAFN_MAGIC));
1140
1141         xfs_trans_log_buf(args->trans, bp,
1142                           (uint)((char *)&leaf->hdr - (char *)leaf),
1143                           args->dp->d_ops->leaf_hdr_size - 1);
1144 }
1145
1146 /*
1147  * Log the tail of the leaf1 block.
1148  */
1149 STATIC void
1150 xfs_dir3_leaf_log_tail(
1151         struct xfs_da_args      *args,
1152         struct xfs_buf          *bp)
1153 {
1154         struct xfs_dir2_leaf    *leaf = bp->b_addr;
1155         xfs_dir2_leaf_tail_t    *ltp;           /* leaf tail structure */
1156
1157         ASSERT(leaf->hdr.info.magic == cpu_to_be16(XFS_DIR2_LEAF1_MAGIC) ||
1158                leaf->hdr.info.magic == cpu_to_be16(XFS_DIR3_LEAF1_MAGIC) ||
1159                leaf->hdr.info.magic == cpu_to_be16(XFS_DIR2_LEAFN_MAGIC) ||
1160                leaf->hdr.info.magic == cpu_to_be16(XFS_DIR3_LEAFN_MAGIC));
1161
1162         ltp = xfs_dir2_leaf_tail_p(args->geo, leaf);
1163         xfs_trans_log_buf(args->trans, bp, (uint)((char *)ltp - (char *)leaf),
1164                 (uint)(args->geo->blksize - 1));
1165 }
1166
1167 /*
1168  * Look up the entry referred to by args in the leaf format directory.
1169  * Most of the work is done by the xfs_dir2_leaf_lookup_int routine which
1170  * is also used by the node-format code.
1171  */
1172 int
1173 xfs_dir2_leaf_lookup(
1174         xfs_da_args_t           *args)          /* operation arguments */
1175 {
1176         struct xfs_buf          *dbp;           /* data block buffer */
1177         xfs_dir2_data_entry_t   *dep;           /* data block entry */
1178         xfs_inode_t             *dp;            /* incore directory inode */
1179         int                     error;          /* error return code */
1180         int                     index;          /* found entry index */
1181         struct xfs_buf          *lbp;           /* leaf buffer */
1182         xfs_dir2_leaf_t         *leaf;          /* leaf structure */
1183         xfs_dir2_leaf_entry_t   *lep;           /* leaf entry */
1184         xfs_trans_t             *tp;            /* transaction pointer */
1185         struct xfs_dir2_leaf_entry *ents;
1186
1187         trace_xfs_dir2_leaf_lookup(args);
1188
1189         /*
1190          * Look up name in the leaf block, returning both buffers and index.
1191          */
1192         if ((error = xfs_dir2_leaf_lookup_int(args, &lbp, &index, &dbp))) {
1193                 return error;
1194         }
1195         tp = args->trans;
1196         dp = args->dp;
1197         xfs_dir3_leaf_check(dp, lbp);
1198         leaf = lbp->b_addr;
1199         ents = dp->d_ops->leaf_ents_p(leaf);
1200         /*
1201          * Get to the leaf entry and contained data entry address.
1202          */
1203         lep = &ents[index];
1204
1205         /*
1206          * Point to the data entry.
1207          */
1208         dep = (xfs_dir2_data_entry_t *)
1209               ((char *)dbp->b_addr +
1210                xfs_dir2_dataptr_to_off(args->geo, be32_to_cpu(lep->address)));
1211         /*
1212          * Return the found inode number & CI name if appropriate
1213          */
1214         args->inumber = be64_to_cpu(dep->inumber);
1215         args->filetype = dp->d_ops->data_get_ftype(dep);
1216         error = xfs_dir_cilookup_result(args, dep->name, dep->namelen);
1217         xfs_trans_brelse(tp, dbp);
1218         xfs_trans_brelse(tp, lbp);
1219         return error;
1220 }
1221
1222 /*
1223  * Look up name/hash in the leaf block.
1224  * Fill in indexp with the found index, and dbpp with the data buffer.
1225  * If not found dbpp will be NULL, and ENOENT comes back.
1226  * lbpp will always be filled in with the leaf buffer unless there's an error.
1227  */
1228 static int                                      /* error */
1229 xfs_dir2_leaf_lookup_int(
1230         xfs_da_args_t           *args,          /* operation arguments */
1231         struct xfs_buf          **lbpp,         /* out: leaf buffer */
1232         int                     *indexp,        /* out: index in leaf block */
1233         struct xfs_buf          **dbpp)         /* out: data buffer */
1234 {
1235         xfs_dir2_db_t           curdb = -1;     /* current data block number */
1236         struct xfs_buf          *dbp = NULL;    /* data buffer */
1237         xfs_dir2_data_entry_t   *dep;           /* data entry */
1238         xfs_inode_t             *dp;            /* incore directory inode */
1239         int                     error;          /* error return code */
1240         int                     index;          /* index in leaf block */
1241         struct xfs_buf          *lbp;           /* leaf buffer */
1242         xfs_dir2_leaf_entry_t   *lep;           /* leaf entry */
1243         xfs_dir2_leaf_t         *leaf;          /* leaf structure */
1244         xfs_mount_t             *mp;            /* filesystem mount point */
1245         xfs_dir2_db_t           newdb;          /* new data block number */
1246         xfs_trans_t             *tp;            /* transaction pointer */
1247         xfs_dir2_db_t           cidb = -1;      /* case match data block no. */
1248         enum xfs_dacmp          cmp;            /* name compare result */
1249         struct xfs_dir2_leaf_entry *ents;
1250         struct xfs_dir3_icleaf_hdr leafhdr;
1251
1252         dp = args->dp;
1253         tp = args->trans;
1254         mp = dp->i_mount;
1255
1256         error = xfs_dir3_leaf_read(tp, dp, args->geo->leafblk, -1, &lbp);
1257         if (error)
1258                 return error;
1259
1260         *lbpp = lbp;
1261         leaf = lbp->b_addr;
1262         xfs_dir3_leaf_check(dp, lbp);
1263         ents = dp->d_ops->leaf_ents_p(leaf);
1264         dp->d_ops->leaf_hdr_from_disk(&leafhdr, leaf);
1265
1266         /*
1267          * Look for the first leaf entry with our hash value.
1268          */
1269         index = xfs_dir2_leaf_search_hash(args, lbp);
1270         /*
1271          * Loop over all the entries with the right hash value
1272          * looking to match the name.
1273          */
1274         for (lep = &ents[index];
1275              index < leafhdr.count && be32_to_cpu(lep->hashval) == args->hashval;
1276              lep++, index++) {
1277                 /*
1278                  * Skip over stale leaf entries.
1279                  */
1280                 if (be32_to_cpu(lep->address) == XFS_DIR2_NULL_DATAPTR)
1281                         continue;
1282                 /*
1283                  * Get the new data block number.
1284                  */
1285                 newdb = xfs_dir2_dataptr_to_db(args->geo,
1286                                                be32_to_cpu(lep->address));
1287                 /*
1288                  * If it's not the same as the old data block number,
1289                  * need to pitch the old one and read the new one.
1290                  */
1291                 if (newdb != curdb) {
1292                         if (dbp)
1293                                 xfs_trans_brelse(tp, dbp);
1294                         error = xfs_dir3_data_read(tp, dp,
1295                                            xfs_dir2_db_to_da(args->geo, newdb),
1296                                            -1, &dbp);
1297                         if (error) {
1298                                 xfs_trans_brelse(tp, lbp);
1299                                 return error;
1300                         }
1301                         curdb = newdb;
1302                 }
1303                 /*
1304                  * Point to the data entry.
1305                  */
1306                 dep = (xfs_dir2_data_entry_t *)((char *)dbp->b_addr +
1307                         xfs_dir2_dataptr_to_off(args->geo,
1308                                                 be32_to_cpu(lep->address)));
1309                 /*
1310                  * Compare name and if it's an exact match, return the index
1311                  * and buffer. If it's the first case-insensitive match, store
1312                  * the index and buffer and continue looking for an exact match.
1313                  */
1314                 cmp = mp->m_dirnameops->compname(args, dep->name, dep->namelen);
1315                 if (cmp != XFS_CMP_DIFFERENT && cmp != args->cmpresult) {
1316                         args->cmpresult = cmp;
1317                         *indexp = index;
1318                         /* case exact match: return the current buffer. */
1319                         if (cmp == XFS_CMP_EXACT) {
1320                                 *dbpp = dbp;
1321                                 return 0;
1322                         }
1323                         cidb = curdb;
1324                 }
1325         }
1326         ASSERT(args->op_flags & XFS_DA_OP_OKNOENT);
1327         /*
1328          * Here, we can only be doing a lookup (not a rename or remove).
1329          * If a case-insensitive match was found earlier, re-read the
1330          * appropriate data block if required and return it.
1331          */
1332         if (args->cmpresult == XFS_CMP_CASE) {
1333                 ASSERT(cidb != -1);
1334                 if (cidb != curdb) {
1335                         xfs_trans_brelse(tp, dbp);
1336                         error = xfs_dir3_data_read(tp, dp,
1337                                            xfs_dir2_db_to_da(args->geo, cidb),
1338                                            -1, &dbp);
1339                         if (error) {
1340                                 xfs_trans_brelse(tp, lbp);
1341                                 return error;
1342                         }
1343                 }
1344                 *dbpp = dbp;
1345                 return 0;
1346         }
1347         /*
1348          * No match found, return -ENOENT.
1349          */
1350         ASSERT(cidb == -1);
1351         if (dbp)
1352                 xfs_trans_brelse(tp, dbp);
1353         xfs_trans_brelse(tp, lbp);
1354         return -ENOENT;
1355 }
1356
1357 /*
1358  * Remove an entry from a leaf format directory.
1359  */
1360 int                                             /* error */
1361 xfs_dir2_leaf_removename(
1362         xfs_da_args_t           *args)          /* operation arguments */
1363 {
1364         __be16                  *bestsp;        /* leaf block best freespace */
1365         xfs_dir2_data_hdr_t     *hdr;           /* data block header */
1366         xfs_dir2_db_t           db;             /* data block number */
1367         struct xfs_buf          *dbp;           /* data block buffer */
1368         xfs_dir2_data_entry_t   *dep;           /* data entry structure */
1369         xfs_inode_t             *dp;            /* incore directory inode */
1370         int                     error;          /* error return code */
1371         xfs_dir2_db_t           i;              /* temporary data block # */
1372         int                     index;          /* index into leaf entries */
1373         struct xfs_buf          *lbp;           /* leaf buffer */
1374         xfs_dir2_leaf_t         *leaf;          /* leaf structure */
1375         xfs_dir2_leaf_entry_t   *lep;           /* leaf entry */
1376         xfs_dir2_leaf_tail_t    *ltp;           /* leaf tail structure */
1377         int                     needlog;        /* need to log data header */
1378         int                     needscan;       /* need to rescan data frees */
1379         xfs_dir2_data_off_t     oldbest;        /* old value of best free */
1380         struct xfs_dir2_data_free *bf;          /* bestfree table */
1381         struct xfs_dir2_leaf_entry *ents;
1382         struct xfs_dir3_icleaf_hdr leafhdr;
1383
1384         trace_xfs_dir2_leaf_removename(args);
1385
1386         /*
1387          * Lookup the leaf entry, get the leaf and data blocks read in.
1388          */
1389         if ((error = xfs_dir2_leaf_lookup_int(args, &lbp, &index, &dbp))) {
1390                 return error;
1391         }
1392         dp = args->dp;
1393         leaf = lbp->b_addr;
1394         hdr = dbp->b_addr;
1395         xfs_dir3_data_check(dp, dbp);
1396         bf = dp->d_ops->data_bestfree_p(hdr);
1397         dp->d_ops->leaf_hdr_from_disk(&leafhdr, leaf);
1398         ents = dp->d_ops->leaf_ents_p(leaf);
1399         /*
1400          * Point to the leaf entry, use that to point to the data entry.
1401          */
1402         lep = &ents[index];
1403         db = xfs_dir2_dataptr_to_db(args->geo, be32_to_cpu(lep->address));
1404         dep = (xfs_dir2_data_entry_t *)((char *)hdr +
1405                 xfs_dir2_dataptr_to_off(args->geo, be32_to_cpu(lep->address)));
1406         needscan = needlog = 0;
1407         oldbest = be16_to_cpu(bf[0].length);
1408         ltp = xfs_dir2_leaf_tail_p(args->geo, leaf);
1409         bestsp = xfs_dir2_leaf_bests_p(ltp);
1410         if (be16_to_cpu(bestsp[db]) != oldbest)
1411                 return -EFSCORRUPTED;
1412         /*
1413          * Mark the former data entry unused.
1414          */
1415         xfs_dir2_data_make_free(args, dbp,
1416                 (xfs_dir2_data_aoff_t)((char *)dep - (char *)hdr),
1417                 dp->d_ops->data_entsize(dep->namelen), &needlog, &needscan);
1418         /*
1419          * We just mark the leaf entry stale by putting a null in it.
1420          */
1421         leafhdr.stale++;
1422         dp->d_ops->leaf_hdr_to_disk(leaf, &leafhdr);
1423         xfs_dir3_leaf_log_header(args, lbp);
1424
1425         lep->address = cpu_to_be32(XFS_DIR2_NULL_DATAPTR);
1426         xfs_dir3_leaf_log_ents(args, lbp, index, index);
1427
1428         /*
1429          * Scan the freespace in the data block again if necessary,
1430          * log the data block header if necessary.
1431          */
1432         if (needscan)
1433                 xfs_dir2_data_freescan(dp, hdr, &needlog);
1434         if (needlog)
1435                 xfs_dir2_data_log_header(args, dbp);
1436         /*
1437          * If the longest freespace in the data block has changed,
1438          * put the new value in the bests table and log that.
1439          */
1440         if (be16_to_cpu(bf[0].length) != oldbest) {
1441                 bestsp[db] = bf[0].length;
1442                 xfs_dir3_leaf_log_bests(args, lbp, db, db);
1443         }
1444         xfs_dir3_data_check(dp, dbp);
1445         /*
1446          * If the data block is now empty then get rid of the data block.
1447          */
1448         if (be16_to_cpu(bf[0].length) ==
1449                         args->geo->blksize - dp->d_ops->data_entry_offset) {
1450                 ASSERT(db != args->geo->datablk);
1451                 if ((error = xfs_dir2_shrink_inode(args, db, dbp))) {
1452                         /*
1453                          * Nope, can't get rid of it because it caused
1454                          * allocation of a bmap btree block to do so.
1455                          * Just go on, returning success, leaving the
1456                          * empty block in place.
1457                          */
1458                         if (error == -ENOSPC && args->total == 0)
1459                                 error = 0;
1460                         xfs_dir3_leaf_check(dp, lbp);
1461                         return error;
1462                 }
1463                 dbp = NULL;
1464                 /*
1465                  * If this is the last data block then compact the
1466                  * bests table by getting rid of entries.
1467                  */
1468                 if (db == be32_to_cpu(ltp->bestcount) - 1) {
1469                         /*
1470                          * Look for the last active entry (i).
1471                          */
1472                         for (i = db - 1; i > 0; i--) {
1473                                 if (bestsp[i] != cpu_to_be16(NULLDATAOFF))
1474                                         break;
1475                         }
1476                         /*
1477                          * Copy the table down so inactive entries at the
1478                          * end are removed.
1479                          */
1480                         memmove(&bestsp[db - i], bestsp,
1481                                 (be32_to_cpu(ltp->bestcount) - (db - i)) * sizeof(*bestsp));
1482                         be32_add_cpu(&ltp->bestcount, -(db - i));
1483                         xfs_dir3_leaf_log_tail(args, lbp);
1484                         xfs_dir3_leaf_log_bests(args, lbp, 0,
1485                                                 be32_to_cpu(ltp->bestcount) - 1);
1486                 } else
1487                         bestsp[db] = cpu_to_be16(NULLDATAOFF);
1488         }
1489         /*
1490          * If the data block was not the first one, drop it.
1491          */
1492         else if (db != args->geo->datablk)
1493                 dbp = NULL;
1494
1495         xfs_dir3_leaf_check(dp, lbp);
1496         /*
1497          * See if we can convert to block form.
1498          */
1499         return xfs_dir2_leaf_to_block(args, lbp, dbp);
1500 }
1501
1502 /*
1503  * Replace the inode number in a leaf format directory entry.
1504  */
1505 int                                             /* error */
1506 xfs_dir2_leaf_replace(
1507         xfs_da_args_t           *args)          /* operation arguments */
1508 {
1509         struct xfs_buf          *dbp;           /* data block buffer */
1510         xfs_dir2_data_entry_t   *dep;           /* data block entry */
1511         xfs_inode_t             *dp;            /* incore directory inode */
1512         int                     error;          /* error return code */
1513         int                     index;          /* index of leaf entry */
1514         struct xfs_buf          *lbp;           /* leaf buffer */
1515         xfs_dir2_leaf_t         *leaf;          /* leaf structure */
1516         xfs_dir2_leaf_entry_t   *lep;           /* leaf entry */
1517         xfs_trans_t             *tp;            /* transaction pointer */
1518         struct xfs_dir2_leaf_entry *ents;
1519
1520         trace_xfs_dir2_leaf_replace(args);
1521
1522         /*
1523          * Look up the entry.
1524          */
1525         if ((error = xfs_dir2_leaf_lookup_int(args, &lbp, &index, &dbp))) {
1526                 return error;
1527         }
1528         dp = args->dp;
1529         leaf = lbp->b_addr;
1530         ents = dp->d_ops->leaf_ents_p(leaf);
1531         /*
1532          * Point to the leaf entry, get data address from it.
1533          */
1534         lep = &ents[index];
1535         /*
1536          * Point to the data entry.
1537          */
1538         dep = (xfs_dir2_data_entry_t *)
1539               ((char *)dbp->b_addr +
1540                xfs_dir2_dataptr_to_off(args->geo, be32_to_cpu(lep->address)));
1541         ASSERT(args->inumber != be64_to_cpu(dep->inumber));
1542         /*
1543          * Put the new inode number in, log it.
1544          */
1545         dep->inumber = cpu_to_be64(args->inumber);
1546         dp->d_ops->data_put_ftype(dep, args->filetype);
1547         tp = args->trans;
1548         xfs_dir2_data_log_entry(args, dbp, dep);
1549         xfs_dir3_leaf_check(dp, lbp);
1550         xfs_trans_brelse(tp, lbp);
1551         return 0;
1552 }
1553
1554 /*
1555  * Return index in the leaf block (lbp) which is either the first
1556  * one with this hash value, or if there are none, the insert point
1557  * for that hash value.
1558  */
1559 int                                             /* index value */
1560 xfs_dir2_leaf_search_hash(
1561         xfs_da_args_t           *args,          /* operation arguments */
1562         struct xfs_buf          *lbp)           /* leaf buffer */
1563 {
1564         xfs_dahash_t            hash=0;         /* hash from this entry */
1565         xfs_dahash_t            hashwant;       /* hash value looking for */
1566         int                     high;           /* high leaf index */
1567         int                     low;            /* low leaf index */
1568         xfs_dir2_leaf_t         *leaf;          /* leaf structure */
1569         xfs_dir2_leaf_entry_t   *lep;           /* leaf entry */
1570         int                     mid=0;          /* current leaf index */
1571         struct xfs_dir2_leaf_entry *ents;
1572         struct xfs_dir3_icleaf_hdr leafhdr;
1573
1574         leaf = lbp->b_addr;
1575         ents = args->dp->d_ops->leaf_ents_p(leaf);
1576         args->dp->d_ops->leaf_hdr_from_disk(&leafhdr, leaf);
1577
1578         /*
1579          * Note, the table cannot be empty, so we have to go through the loop.
1580          * Binary search the leaf entries looking for our hash value.
1581          */
1582         for (lep = ents, low = 0, high = leafhdr.count - 1,
1583                 hashwant = args->hashval;
1584              low <= high; ) {
1585                 mid = (low + high) >> 1;
1586                 if ((hash = be32_to_cpu(lep[mid].hashval)) == hashwant)
1587                         break;
1588                 if (hash < hashwant)
1589                         low = mid + 1;
1590                 else
1591                         high = mid - 1;
1592         }
1593         /*
1594          * Found one, back up through all the equal hash values.
1595          */
1596         if (hash == hashwant) {
1597                 while (mid > 0 && be32_to_cpu(lep[mid - 1].hashval) == hashwant) {
1598                         mid--;
1599                 }
1600         }
1601         /*
1602          * Need to point to an entry higher than ours.
1603          */
1604         else if (hash < hashwant)
1605                 mid++;
1606         return mid;
1607 }
1608
1609 /*
1610  * Trim off a trailing data block.  We know it's empty since the leaf
1611  * freespace table says so.
1612  */
1613 int                                             /* error */
1614 xfs_dir2_leaf_trim_data(
1615         xfs_da_args_t           *args,          /* operation arguments */
1616         struct xfs_buf          *lbp,           /* leaf buffer */
1617         xfs_dir2_db_t           db)             /* data block number */
1618 {
1619         __be16                  *bestsp;        /* leaf bests table */
1620         struct xfs_buf          *dbp;           /* data block buffer */
1621         xfs_inode_t             *dp;            /* incore directory inode */
1622         int                     error;          /* error return value */
1623         xfs_dir2_leaf_t         *leaf;          /* leaf structure */
1624         xfs_dir2_leaf_tail_t    *ltp;           /* leaf tail structure */
1625         xfs_trans_t             *tp;            /* transaction pointer */
1626
1627         dp = args->dp;
1628         tp = args->trans;
1629         /*
1630          * Read the offending data block.  We need its buffer.
1631          */
1632         error = xfs_dir3_data_read(tp, dp, xfs_dir2_db_to_da(args->geo, db),
1633                                    -1, &dbp);
1634         if (error)
1635                 return error;
1636
1637         leaf = lbp->b_addr;
1638         ltp = xfs_dir2_leaf_tail_p(args->geo, leaf);
1639
1640 #ifdef DEBUG
1641 {
1642         struct xfs_dir2_data_hdr *hdr = dbp->b_addr;
1643         struct xfs_dir2_data_free *bf = dp->d_ops->data_bestfree_p(hdr);
1644
1645         ASSERT(hdr->magic == cpu_to_be32(XFS_DIR2_DATA_MAGIC) ||
1646                hdr->magic == cpu_to_be32(XFS_DIR3_DATA_MAGIC));
1647         ASSERT(be16_to_cpu(bf[0].length) ==
1648                args->geo->blksize - dp->d_ops->data_entry_offset);
1649         ASSERT(db == be32_to_cpu(ltp->bestcount) - 1);
1650 }
1651 #endif
1652
1653         /*
1654          * Get rid of the data block.
1655          */
1656         if ((error = xfs_dir2_shrink_inode(args, db, dbp))) {
1657                 ASSERT(error != -ENOSPC);
1658                 xfs_trans_brelse(tp, dbp);
1659                 return error;
1660         }
1661         /*
1662          * Eliminate the last bests entry from the table.
1663          */
1664         bestsp = xfs_dir2_leaf_bests_p(ltp);
1665         be32_add_cpu(&ltp->bestcount, -1);
1666         memmove(&bestsp[1], &bestsp[0], be32_to_cpu(ltp->bestcount) * sizeof(*bestsp));
1667         xfs_dir3_leaf_log_tail(args, lbp);
1668         xfs_dir3_leaf_log_bests(args, lbp, 0, be32_to_cpu(ltp->bestcount) - 1);
1669         return 0;
1670 }
1671
1672 static inline size_t
1673 xfs_dir3_leaf_size(
1674         struct xfs_dir3_icleaf_hdr      *hdr,
1675         int                             counts)
1676 {
1677         int     entries;
1678         int     hdrsize;
1679
1680         entries = hdr->count - hdr->stale;
1681         if (hdr->magic == XFS_DIR2_LEAF1_MAGIC ||
1682             hdr->magic == XFS_DIR2_LEAFN_MAGIC)
1683                 hdrsize = sizeof(struct xfs_dir2_leaf_hdr);
1684         else
1685                 hdrsize = sizeof(struct xfs_dir3_leaf_hdr);
1686
1687         return hdrsize + entries * sizeof(xfs_dir2_leaf_entry_t)
1688                        + counts * sizeof(xfs_dir2_data_off_t)
1689                        + sizeof(xfs_dir2_leaf_tail_t);
1690 }
1691
1692 /*
1693  * Convert node form directory to leaf form directory.
1694  * The root of the node form dir needs to already be a LEAFN block.
1695  * Just return if we can't do anything.
1696  */
1697 int                                             /* error */
1698 xfs_dir2_node_to_leaf(
1699         xfs_da_state_t          *state)         /* directory operation state */
1700 {
1701         xfs_da_args_t           *args;          /* operation arguments */
1702         xfs_inode_t             *dp;            /* incore directory inode */
1703         int                     error;          /* error return code */
1704         struct xfs_buf          *fbp;           /* buffer for freespace block */
1705         xfs_fileoff_t           fo;             /* freespace file offset */
1706         xfs_dir2_free_t         *free;          /* freespace structure */
1707         struct xfs_buf          *lbp;           /* buffer for leaf block */
1708         xfs_dir2_leaf_tail_t    *ltp;           /* tail of leaf structure */
1709         xfs_dir2_leaf_t         *leaf;          /* leaf structure */
1710         xfs_mount_t             *mp;            /* filesystem mount point */
1711         int                     rval;           /* successful free trim? */
1712         xfs_trans_t             *tp;            /* transaction pointer */
1713         struct xfs_dir3_icleaf_hdr leafhdr;
1714         struct xfs_dir3_icfree_hdr freehdr;
1715
1716         /*
1717          * There's more than a leaf level in the btree, so there must
1718          * be multiple leafn blocks.  Give up.
1719          */
1720         if (state->path.active > 1)
1721                 return 0;
1722         args = state->args;
1723
1724         trace_xfs_dir2_node_to_leaf(args);
1725
1726         mp = state->mp;
1727         dp = args->dp;
1728         tp = args->trans;
1729         /*
1730          * Get the last offset in the file.
1731          */
1732         if ((error = xfs_bmap_last_offset(dp, &fo, XFS_DATA_FORK))) {
1733                 return error;
1734         }
1735         fo -= args->geo->fsbcount;
1736         /*
1737          * If there are freespace blocks other than the first one,
1738          * take this opportunity to remove trailing empty freespace blocks
1739          * that may have been left behind during no-space-reservation
1740          * operations.
1741          */
1742         while (fo > args->geo->freeblk) {
1743                 if ((error = xfs_dir2_node_trim_free(args, fo, &rval))) {
1744                         return error;
1745                 }
1746                 if (rval)
1747                         fo -= args->geo->fsbcount;
1748                 else
1749                         return 0;
1750         }
1751         /*
1752          * Now find the block just before the freespace block.
1753          */
1754         if ((error = xfs_bmap_last_before(tp, dp, &fo, XFS_DATA_FORK))) {
1755                 return error;
1756         }
1757         /*
1758          * If it's not the single leaf block, give up.
1759          */
1760         if (XFS_FSB_TO_B(mp, fo) > XFS_DIR2_LEAF_OFFSET + args->geo->blksize)
1761                 return 0;
1762         lbp = state->path.blk[0].bp;
1763         leaf = lbp->b_addr;
1764         dp->d_ops->leaf_hdr_from_disk(&leafhdr, leaf);
1765
1766         ASSERT(leafhdr.magic == XFS_DIR2_LEAFN_MAGIC ||
1767                leafhdr.magic == XFS_DIR3_LEAFN_MAGIC);
1768
1769         /*
1770          * Read the freespace block.
1771          */
1772         error = xfs_dir2_free_read(tp, dp,  args->geo->freeblk, &fbp);
1773         if (error)
1774                 return error;
1775         free = fbp->b_addr;
1776         dp->d_ops->free_hdr_from_disk(&freehdr, free);
1777
1778         ASSERT(!freehdr.firstdb);
1779
1780         /*
1781          * Now see if the leafn and free data will fit in a leaf1.
1782          * If not, release the buffer and give up.
1783          */
1784         if (xfs_dir3_leaf_size(&leafhdr, freehdr.nvalid) > args->geo->blksize) {
1785                 xfs_trans_brelse(tp, fbp);
1786                 return 0;
1787         }
1788
1789         /*
1790          * If the leaf has any stale entries in it, compress them out.
1791          */
1792         if (leafhdr.stale)
1793                 xfs_dir3_leaf_compact(args, &leafhdr, lbp);
1794
1795         lbp->b_ops = &xfs_dir3_leaf1_buf_ops;
1796         xfs_trans_buf_set_type(tp, lbp, XFS_BLFT_DIR_LEAF1_BUF);
1797         leafhdr.magic = (leafhdr.magic == XFS_DIR2_LEAFN_MAGIC)
1798                                         ? XFS_DIR2_LEAF1_MAGIC
1799                                         : XFS_DIR3_LEAF1_MAGIC;
1800
1801         /*
1802          * Set up the leaf tail from the freespace block.
1803          */
1804         ltp = xfs_dir2_leaf_tail_p(args->geo, leaf);
1805         ltp->bestcount = cpu_to_be32(freehdr.nvalid);
1806
1807         /*
1808          * Set up the leaf bests table.
1809          */
1810         memcpy(xfs_dir2_leaf_bests_p(ltp), dp->d_ops->free_bests_p(free),
1811                 freehdr.nvalid * sizeof(xfs_dir2_data_off_t));
1812
1813         dp->d_ops->leaf_hdr_to_disk(leaf, &leafhdr);
1814         xfs_dir3_leaf_log_header(args, lbp);
1815         xfs_dir3_leaf_log_bests(args, lbp, 0, be32_to_cpu(ltp->bestcount) - 1);
1816         xfs_dir3_leaf_log_tail(args, lbp);
1817         xfs_dir3_leaf_check(dp, lbp);
1818
1819         /*
1820          * Get rid of the freespace block.
1821          */
1822         error = xfs_dir2_shrink_inode(args,
1823                         xfs_dir2_byte_to_db(args->geo, XFS_DIR2_FREE_OFFSET),
1824                         fbp);
1825         if (error) {
1826                 /*
1827                  * This can't fail here because it can only happen when
1828                  * punching out the middle of an extent, and this is an
1829                  * isolated block.
1830                  */
1831                 ASSERT(error != -ENOSPC);
1832                 return error;
1833         }
1834         fbp = NULL;
1835         /*
1836          * Now see if we can convert the single-leaf directory
1837          * down to a block form directory.
1838          * This routine always kills the dabuf for the leaf, so
1839          * eliminate it from the path.
1840          */
1841         error = xfs_dir2_leaf_to_block(args, lbp, NULL);
1842         state->path.blk[0].bp = NULL;
1843         return error;
1844 }