root/fs/xfs/libxfs/xfs_dir2_leaf.c

DEFINITIONS

1. xfs_dir3_leaf1_check
2. xfs_dir3_leaf_check
3. xfs_dir3_leaf_check_int
4. xfs_dir3_leaf_verify
5. xfs_dir3_leaf_read_verify
6. xfs_dir3_leaf_write_verify
7. xfs_dir3_leaf_read
8. xfs_dir3_leafn_read
9. xfs_dir3_leaf_init
10. xfs_dir3_leaf_get_buf
11. xfs_dir2_block_to_leaf
12. xfs_dir3_leaf_find_stale
13. xfs_dir3_leaf_find_entry
14. xfs_dir2_leaf_addname
15. xfs_dir3_leaf_compact
16. xfs_dir3_leaf_compact_x1
17. xfs_dir3_leaf_log_bests
18. xfs_dir3_leaf_log_ents
19. xfs_dir3_leaf_log_header
20. xfs_dir3_leaf_log_tail
21. xfs_dir2_leaf_lookup
22. xfs_dir2_leaf_lookup_int
23. xfs_dir2_leaf_removename
24. xfs_dir2_leaf_replace
25. xfs_dir2_leaf_search_hash
26. xfs_dir2_leaf_trim_data
27. xfs_dir3_leaf_size
28. xfs_dir2_node_to_leaf

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