fs/xfs/libxfs/xfs_dir2_leaf.c

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