SAFE public projects git trees. - safe/jmp/linux-2.6/blob - fs/xfs/xfs_dir_leaf.c

   1 /*
   2  * Copyright (c) 2000-2003 Silicon Graphics, Inc.  All Rights Reserved.
   3  *
   4  * This program is free software; you can redistribute it and/or modify it
   5  * under the terms of version 2 of the GNU General Public License as
   6  * published by the Free Software Foundation.
   7  *
   8  * This program is distributed in the hope that it would be useful, but
   9  * WITHOUT ANY WARRANTY; without even the implied warranty of
  10  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
  11  *
  12  * Further, this software is distributed without any warranty that it is
  13  * free of the rightful claim of any third person regarding infringement
  14  * or the like.  Any license provided herein, whether implied or
  15  * otherwise, applies only to this software file.  Patent licenses, if
  16  * any, provided herein do not apply to combinations of this program with
  17  * other software, or any other product whatsoever.
  18  *
  19  * You should have received a copy of the GNU General Public License along
  20  * with this program; if not, write the Free Software Foundation, Inc., 59
  21  * Temple Place - Suite 330, Boston MA 02111-1307, USA.
  22  *
  23  * Contact information: Silicon Graphics, Inc., 1600 Amphitheatre Pkwy,
  24  * Mountain View, CA  94043, or:
  25  *
  26  * http://www.sgi.com
  27  *
  28  * For further information regarding this notice, see:
  29  *
  30  * http://oss.sgi.com/projects/GenInfo/SGIGPLNoticeExplan/
  31  */
  32
  33 /*
  34  * xfs_dir_leaf.c
  35  *
  36  * GROT: figure out how to recover gracefully when bmap returns ENOSPC.
  37  */
  38
  39 #include "xfs.h"
  40
  41 #include "xfs_macros.h"
  42 #include "xfs_types.h"
  43 #include "xfs_inum.h"
  44 #include "xfs_log.h"
  45 #include "xfs_trans.h"
  46 #include "xfs_sb.h"
  47 #include "xfs_dir.h"
  48 #include "xfs_dir2.h"
  49 #include "xfs_dmapi.h"
  50 #include "xfs_mount.h"
  51 #include "xfs_alloc_btree.h"
  52 #include "xfs_bmap_btree.h"
  53 #include "xfs_ialloc_btree.h"
  54 #include "xfs_alloc.h"
  55 #include "xfs_btree.h"
  56 #include "xfs_attr_sf.h"
  57 #include "xfs_dir_sf.h"
  58 #include "xfs_dir2_sf.h"
  59 #include "xfs_dinode.h"
  60 #include "xfs_inode_item.h"
  61 #include "xfs_inode.h"
  62 #include "xfs_bmap.h"
  63 #include "xfs_da_btree.h"
  64 #include "xfs_dir_leaf.h"
  65 #include "xfs_error.h"
  66
  67 /*
  68  * xfs_dir_leaf.c
  69  *
  70  * Routines to implement leaf blocks of directories as Btrees of hashed names.
  71  */
  72
  73 /*========================================================================
  74  * Function prototypes for the kernel.
  75  *========================================================================*/
  76
  77 /*
  78  * Routines used for growing the Btree.
  79  */
  80 STATIC void xfs_dir_leaf_add_work(xfs_dabuf_t *leaf_buffer, xfs_da_args_t *args,
  81                                               int insertion_index,
  82                                               int freemap_index);
  83 STATIC int xfs_dir_leaf_compact(xfs_trans_t *trans, xfs_dabuf_t *leaf_buffer,
  84                                             int musthave, int justcheck);
  85 STATIC void xfs_dir_leaf_rebalance(xfs_da_state_t *state,
  86                                                   xfs_da_state_blk_t *blk1,
  87                                                   xfs_da_state_blk_t *blk2);
  88 STATIC int xfs_dir_leaf_figure_balance(xfs_da_state_t *state,
  89                                           xfs_da_state_blk_t *leaf_blk_1,
  90                                           xfs_da_state_blk_t *leaf_blk_2,
  91                                           int *number_entries_in_blk1,
  92                                           int *number_namebytes_in_blk1);
  93
  94 STATIC int xfs_dir_leaf_create(struct xfs_da_args *args,
  95                                 xfs_dablk_t which_block,
  96                                 struct xfs_dabuf **bpp);
  97
  98 /*
  99  * Utility routines.
 100  */
 101 STATIC void xfs_dir_leaf_moveents(xfs_dir_leafblock_t *src_leaf,
 102                                               int src_start,
 103                                               xfs_dir_leafblock_t *dst_leaf,
 104                                               int dst_start, int move_count,
 105                                               xfs_mount_t *mp);
 106
 107
 108 /*========================================================================
 109  * External routines when dirsize < XFS_IFORK_DSIZE(dp).
 110  *========================================================================*/
 111
 112
 113 /*
 114  * Validate a given inode number.
 115  */
 116 int
 117 xfs_dir_ino_validate(xfs_mount_t *mp, xfs_ino_t ino)
 118 {
 119         xfs_agblock_t   agblkno;
 120         xfs_agino_t     agino;
 121         xfs_agnumber_t  agno;
 122         int             ino_ok;
 123         int             ioff;
 124
 125         agno = XFS_INO_TO_AGNO(mp, ino);
 126         agblkno = XFS_INO_TO_AGBNO(mp, ino);
 127         ioff = XFS_INO_TO_OFFSET(mp, ino);
 128         agino = XFS_OFFBNO_TO_AGINO(mp, agblkno, ioff);
 129         ino_ok =
 130                 agno < mp->m_sb.sb_agcount &&
 131                 agblkno < mp->m_sb.sb_agblocks &&
 132                 agblkno != 0 &&
 133                 ioff < (1 << mp->m_sb.sb_inopblog) &&
 134                 XFS_AGINO_TO_INO(mp, agno, agino) == ino;
 135         if (unlikely(XFS_TEST_ERROR(!ino_ok, mp, XFS_ERRTAG_DIR_INO_VALIDATE,
 136                         XFS_RANDOM_DIR_INO_VALIDATE))) {
 137                 xfs_fs_cmn_err(CE_WARN, mp, "Invalid inode number 0x%Lx",
 138                                 (unsigned long long) ino);
 139                 XFS_ERROR_REPORT("xfs_dir_ino_validate", XFS_ERRLEVEL_LOW, mp);
 140                 return XFS_ERROR(EFSCORRUPTED);
 141         }
 142         return 0;
 143 }
 144
 145 /*
 146  * Create the initial contents of a shortform directory.
 147  */
 148 int
 149 xfs_dir_shortform_create(xfs_da_args_t *args, xfs_ino_t parent)
 150 {
 151         xfs_dir_sf_hdr_t *hdr;
 152         xfs_inode_t *dp;
 153
 154         dp = args->dp;
 155         ASSERT(dp != NULL);
 156         ASSERT(dp->i_d.di_size == 0);
 157         if (dp->i_d.di_format == XFS_DINODE_FMT_EXTENTS) {
 158                 dp->i_df.if_flags &= ~XFS_IFEXTENTS;    /* just in case */
 159                 dp->i_d.di_format = XFS_DINODE_FMT_LOCAL;
 160                 xfs_trans_log_inode(args->trans, dp, XFS_ILOG_CORE);
 161                 dp->i_df.if_flags |= XFS_IFINLINE;
 162         }
 163         ASSERT(dp->i_df.if_flags & XFS_IFINLINE);
 164         ASSERT(dp->i_df.if_bytes == 0);
 165         xfs_idata_realloc(dp, sizeof(*hdr), XFS_DATA_FORK);
 166         hdr = (xfs_dir_sf_hdr_t *)dp->i_df.if_u1.if_data;
 167         XFS_DIR_SF_PUT_DIRINO(&parent, &hdr->parent);
 168
 169         hdr->count = 0;
 170         dp->i_d.di_size = sizeof(*hdr);
 171         xfs_trans_log_inode(args->trans, dp, XFS_ILOG_CORE | XFS_ILOG_DDATA);
 172         return(0);
 173 }
 174
 175 /*
 176  * Add a name to the shortform directory structure.
 177  * Overflow from the inode has already been checked for.
 178  */
 179 int
 180 xfs_dir_shortform_addname(xfs_da_args_t *args)
 181 {
 182         xfs_dir_shortform_t *sf;
 183         xfs_dir_sf_entry_t *sfe;
 184         int i, offset, size;
 185         xfs_inode_t *dp;
 186
 187         dp = args->dp;
 188         ASSERT(dp->i_df.if_flags & XFS_IFINLINE);
 189         /*
 190          * Catch the case where the conversion from shortform to leaf
 191          * failed part way through.
 192          */
 193         if (dp->i_d.di_size < sizeof(xfs_dir_sf_hdr_t)) {
 194                 ASSERT(XFS_FORCED_SHUTDOWN(dp->i_mount));
 195                 return XFS_ERROR(EIO);
 196         }
 197         ASSERT(dp->i_df.if_bytes == dp->i_d.di_size);
 198         ASSERT(dp->i_df.if_u1.if_data != NULL);
 199         sf = (xfs_dir_shortform_t *)dp->i_df.if_u1.if_data;
 200         sfe = &sf->list[0];
 201         for (i = INT_GET(sf->hdr.count, ARCH_CONVERT)-1; i >= 0; i--) {
 202                 if (sfe->namelen == args->namelen &&
 203                     args->name[0] == sfe->name[0] &&
 204                     memcmp(args->name, sfe->name, args->namelen) == 0)
 205                         return(XFS_ERROR(EEXIST));
 206                 sfe = XFS_DIR_SF_NEXTENTRY(sfe);
 207         }
 208
 209         offset = (int)((char *)sfe - (char *)sf);
 210         size = XFS_DIR_SF_ENTSIZE_BYNAME(args->namelen);
 211         xfs_idata_realloc(dp, size, XFS_DATA_FORK);
 212         sf = (xfs_dir_shortform_t *)dp->i_df.if_u1.if_data;
 213         sfe = (xfs_dir_sf_entry_t *)((char *)sf + offset);
 214
 215         XFS_DIR_SF_PUT_DIRINO(&args->inumber, &sfe->inumber);
 216         sfe->namelen = args->namelen;
 217         memcpy(sfe->name, args->name, sfe->namelen);
 218         INT_MOD(sf->hdr.count, ARCH_CONVERT, +1);
 219
 220         dp->i_d.di_size += size;
 221         xfs_trans_log_inode(args->trans, dp, XFS_ILOG_CORE | XFS_ILOG_DDATA);
 222
 223         return(0);
 224 }
 225
 226 /*
 227  * Remove a name from the shortform directory structure.
 228  */
 229 int
 230 xfs_dir_shortform_removename(xfs_da_args_t *args)
 231 {
 232         xfs_dir_shortform_t *sf;
 233         xfs_dir_sf_entry_t *sfe;
 234         int base, size = 0, i;
 235         xfs_inode_t *dp;
 236
 237         dp = args->dp;
 238         ASSERT(dp->i_df.if_flags & XFS_IFINLINE);
 239         /*
 240          * Catch the case where the conversion from shortform to leaf
 241          * failed part way through.
 242          */
 243         if (dp->i_d.di_size < sizeof(xfs_dir_sf_hdr_t)) {
 244                 ASSERT(XFS_FORCED_SHUTDOWN(dp->i_mount));
 245                 return XFS_ERROR(EIO);
 246         }
 247         ASSERT(dp->i_df.if_bytes == dp->i_d.di_size);
 248         ASSERT(dp->i_df.if_u1.if_data != NULL);
 249         base = sizeof(xfs_dir_sf_hdr_t);
 250         sf = (xfs_dir_shortform_t *)dp->i_df.if_u1.if_data;
 251         sfe = &sf->list[0];
 252         for (i = INT_GET(sf->hdr.count, ARCH_CONVERT)-1; i >= 0; i--) {
 253                 size = XFS_DIR_SF_ENTSIZE_BYENTRY(sfe);
 254                 if (sfe->namelen == args->namelen &&
 255                     sfe->name[0] == args->name[0] &&
 256                     memcmp(sfe->name, args->name, args->namelen) == 0)
 257                         break;
 258                 base += size;
 259                 sfe = XFS_DIR_SF_NEXTENTRY(sfe);
 260         }
 261         if (i < 0) {
 262                 ASSERT(args->oknoent);
 263                 return(XFS_ERROR(ENOENT));
 264         }
 265
 266         if ((base + size) != dp->i_d.di_size) {
 267                 memmove(&((char *)sf)[base], &((char *)sf)[base+size],
 268                                               dp->i_d.di_size - (base+size));
 269         }
 270         INT_MOD(sf->hdr.count, ARCH_CONVERT, -1);
 271
 272         xfs_idata_realloc(dp, -size, XFS_DATA_FORK);
 273         dp->i_d.di_size -= size;
 274         xfs_trans_log_inode(args->trans, dp, XFS_ILOG_CORE | XFS_ILOG_DDATA);
 275
 276         return(0);
 277 }
 278
 279 /*
 280  * Look up a name in a shortform directory structure.
 281  */
 282 int
 283 xfs_dir_shortform_lookup(xfs_da_args_t *args)
 284 {
 285         xfs_dir_shortform_t *sf;
 286         xfs_dir_sf_entry_t *sfe;
 287         int i;
 288         xfs_inode_t *dp;
 289
 290         dp = args->dp;
 291         ASSERT(dp->i_df.if_flags & XFS_IFINLINE);
 292         /*
 293          * Catch the case where the conversion from shortform to leaf
 294          * failed part way through.
 295          */
 296         if (dp->i_d.di_size < sizeof(xfs_dir_sf_hdr_t)) {
 297                 ASSERT(XFS_FORCED_SHUTDOWN(dp->i_mount));
 298                 return XFS_ERROR(EIO);
 299         }
 300         ASSERT(dp->i_df.if_bytes == dp->i_d.di_size);
 301         ASSERT(dp->i_df.if_u1.if_data != NULL);
 302         sf = (xfs_dir_shortform_t *)dp->i_df.if_u1.if_data;
 303         if (args->namelen == 2 &&
 304             args->name[0] == '.' && args->name[1] == '.') {
 305                 XFS_DIR_SF_GET_DIRINO(&sf->hdr.parent, &args->inumber);
 306                 return(XFS_ERROR(EEXIST));
 307         }
 308         if (args->namelen == 1 && args->name[0] == '.') {
 309                 args->inumber = dp->i_ino;
 310                 return(XFS_ERROR(EEXIST));
 311         }
 312         sfe = &sf->list[0];
 313         for (i = INT_GET(sf->hdr.count, ARCH_CONVERT)-1; i >= 0; i--) {
 314                 if (sfe->namelen == args->namelen &&
 315                     sfe->name[0] == args->name[0] &&
 316                     memcmp(args->name, sfe->name, args->namelen) == 0) {
 317                         XFS_DIR_SF_GET_DIRINO(&sfe->inumber, &args->inumber);
 318                         return(XFS_ERROR(EEXIST));
 319                 }
 320                 sfe = XFS_DIR_SF_NEXTENTRY(sfe);
 321         }
 322         ASSERT(args->oknoent);
 323         return(XFS_ERROR(ENOENT));
 324 }
 325
 326 /*
 327  * Convert from using the shortform to the leaf.
 328  */
 329 int
 330 xfs_dir_shortform_to_leaf(xfs_da_args_t *iargs)
 331 {
 332         xfs_inode_t *dp;
 333         xfs_dir_shortform_t *sf;
 334         xfs_dir_sf_entry_t *sfe;
 335         xfs_da_args_t args;
 336         xfs_ino_t inumber;
 337         char *tmpbuffer;
 338         int retval, i, size;
 339         xfs_dablk_t blkno;
 340         xfs_dabuf_t *bp;
 341
 342         dp = iargs->dp;
 343         /*
 344          * Catch the case where the conversion from shortform to leaf
 345          * failed part way through.
 346          */
 347         if (dp->i_d.di_size < sizeof(xfs_dir_sf_hdr_t)) {
 348                 ASSERT(XFS_FORCED_SHUTDOWN(dp->i_mount));
 349                 return XFS_ERROR(EIO);
 350         }
 351         ASSERT(dp->i_df.if_bytes == dp->i_d.di_size);
 352         ASSERT(dp->i_df.if_u1.if_data != NULL);
 353         size = dp->i_df.if_bytes;
 354         tmpbuffer = kmem_alloc(size, KM_SLEEP);
 355         ASSERT(tmpbuffer != NULL);
 356
 357         memcpy(tmpbuffer, dp->i_df.if_u1.if_data, size);
 358
 359         sf = (xfs_dir_shortform_t *)tmpbuffer;
 360         XFS_DIR_SF_GET_DIRINO(&sf->hdr.parent, &inumber);
 361
 362         xfs_idata_realloc(dp, -size, XFS_DATA_FORK);
 363         dp->i_d.di_size = 0;
 364         xfs_trans_log_inode(iargs->trans, dp, XFS_ILOG_CORE);
 365         retval = xfs_da_grow_inode(iargs, &blkno);
 366         if (retval)
 367                 goto out;
 368
 369         ASSERT(blkno == 0);
 370         retval = xfs_dir_leaf_create(iargs, blkno, &bp);
 371         if (retval)
 372                 goto out;
 373         xfs_da_buf_done(bp);
 374
 375         args.name = ".";
 376         args.namelen = 1;
 377         args.hashval = xfs_dir_hash_dot;
 378         args.inumber = dp->i_ino;
 379         args.dp = dp;
 380         args.firstblock = iargs->firstblock;
 381         args.flist = iargs->flist;
 382         args.total = iargs->total;
 383         args.whichfork = XFS_DATA_FORK;
 384         args.trans = iargs->trans;
 385         args.justcheck = 0;
 386         args.addname = args.oknoent = 1;
 387         retval = xfs_dir_leaf_addname(&args);
 388         if (retval)
 389                 goto out;
 390
 391         args.name = "..";
 392         args.namelen = 2;
 393         args.hashval = xfs_dir_hash_dotdot;
 394         args.inumber = inumber;
 395         retval = xfs_dir_leaf_addname(&args);
 396         if (retval)
 397                 goto out;
 398
 399         sfe = &sf->list[0];
 400         for (i = 0; i < INT_GET(sf->hdr.count, ARCH_CONVERT); i++) {
 401                 args.name = (char *)(sfe->name);
 402                 args.namelen = sfe->namelen;
 403                 args.hashval = xfs_da_hashname((char *)(sfe->name),
 404                                                sfe->namelen);
 405                 XFS_DIR_SF_GET_DIRINO(&sfe->inumber, &args.inumber);
 406                 retval = xfs_dir_leaf_addname(&args);
 407                 if (retval)
 408                         goto out;
 409                 sfe = XFS_DIR_SF_NEXTENTRY(sfe);
 410         }
 411         retval = 0;
 412
 413 out:
 414         kmem_free(tmpbuffer, size);
 415         return(retval);
 416 }
 417
 418 STATIC int
 419 xfs_dir_shortform_compare(const void *a, const void *b)
 420 {
 421         xfs_dir_sf_sort_t *sa, *sb;
 422
 423         sa = (xfs_dir_sf_sort_t *)a;
 424         sb = (xfs_dir_sf_sort_t *)b;
 425         if (sa->hash < sb->hash)
 426                 return -1;
 427         else if (sa->hash > sb->hash)
 428                 return 1;
 429         else
 430                 return sa->entno - sb->entno;
 431 }
 432
 433 /*
 434  * Copy out directory entries for getdents(), for shortform directories.
 435  */
 436 /*ARGSUSED*/
 437 int
 438 xfs_dir_shortform_getdents(xfs_inode_t *dp, uio_t *uio, int *eofp,
 439                                        xfs_dirent_t *dbp, xfs_dir_put_t put)
 440 {
 441         xfs_dir_shortform_t *sf;
 442         xfs_dir_sf_entry_t *sfe;
 443         int retval, i, sbsize, nsbuf, lastresid=0, want_entno;
 444         xfs_mount_t *mp;
 445         xfs_dahash_t cookhash, hash;
 446         xfs_dir_put_args_t p;
 447         xfs_dir_sf_sort_t *sbuf, *sbp;
 448
 449         mp = dp->i_mount;
 450         sf = (xfs_dir_shortform_t *)dp->i_df.if_u1.if_data;
 451         cookhash = XFS_DA_COOKIE_HASH(mp, uio->uio_offset);
 452         want_entno = XFS_DA_COOKIE_ENTRY(mp, uio->uio_offset);
 453         nsbuf = INT_GET(sf->hdr.count, ARCH_CONVERT) + 2;
 454         sbsize = (nsbuf + 1) * sizeof(*sbuf);
 455         sbp = sbuf = kmem_alloc(sbsize, KM_SLEEP);
 456
 457         xfs_dir_trace_g_du("sf: start", dp, uio);
 458
 459         /*
 460          * Collect all the entries into the buffer.
 461          * Entry 0 is .
 462          */
 463         sbp->entno = 0;
 464         sbp->seqno = 0;
 465         sbp->hash = xfs_dir_hash_dot;
 466         sbp->ino = dp->i_ino;
 467         sbp->name = ".";
 468         sbp->namelen = 1;
 469         sbp++;
 470
 471         /*
 472          * Entry 1 is ..
 473          */
 474         sbp->entno = 1;
 475         sbp->seqno = 0;
 476         sbp->hash = xfs_dir_hash_dotdot;
 477         sbp->ino = XFS_GET_DIR_INO8(sf->hdr.parent);
 478         sbp->name = "..";
 479         sbp->namelen = 2;
 480         sbp++;
 481
 482         /*
 483          * Scan the directory data for the rest of the entries.
 484          */
 485         for (i = 0, sfe = &sf->list[0];
 486                         i < INT_GET(sf->hdr.count, ARCH_CONVERT); i++) {
 487
 488                 if (unlikely(
 489                     ((char *)sfe < (char *)sf) ||
 490                     ((char *)sfe >= ((char *)sf + dp->i_df.if_bytes)))) {
 491                         xfs_dir_trace_g_du("sf: corrupted", dp, uio);
 492                         XFS_CORRUPTION_ERROR("xfs_dir_shortform_getdents",
 493                                              XFS_ERRLEVEL_LOW, mp, sfe);
 494                         kmem_free(sbuf, sbsize);
 495                         return XFS_ERROR(EFSCORRUPTED);
 496                 }
 497
 498                 sbp->entno = i + 2;
 499                 sbp->seqno = 0;
 500                 sbp->hash = xfs_da_hashname((char *)sfe->name, sfe->namelen);
 501                 sbp->ino = XFS_GET_DIR_INO8(sfe->inumber);
 502                 sbp->name = (char *)sfe->name;
 503                 sbp->namelen = sfe->namelen;
 504                 sfe = XFS_DIR_SF_NEXTENTRY(sfe);
 505                 sbp++;
 506         }
 507
 508         /*
 509          * Sort the entries on hash then entno.
 510          */
 511         qsort(sbuf, nsbuf, sizeof(*sbuf), xfs_dir_shortform_compare);
 512         /*
 513          * Stuff in last entry.
 514          */
 515         sbp->entno = nsbuf;
 516         sbp->hash = XFS_DA_MAXHASH;
 517         sbp->seqno = 0;
 518         /*
 519          * Figure out the sequence numbers in case there's a hash duplicate.
 520          */
 521         for (hash = sbuf->hash, sbp = sbuf + 1;
 522                                 sbp < &sbuf[nsbuf + 1]; sbp++) {
 523                 if (sbp->hash == hash)
 524                         sbp->seqno = sbp[-1].seqno + 1;
 525                 else
 526                         hash = sbp->hash;
 527         }
 528
 529         /*
 530          * Set up put routine.
 531          */
 532         p.dbp = dbp;
 533         p.put = put;
 534         p.uio = uio;
 535
 536         /*
 537          * Find our place.
 538          */
 539         for (sbp = sbuf; sbp < &sbuf[nsbuf + 1]; sbp++) {
 540                 if (sbp->hash > cookhash ||
 541                     (sbp->hash == cookhash && sbp->seqno >= want_entno))
 542                         break;
 543         }
 544
 545         /*
 546          * Did we fail to find anything?  We stop at the last entry,
 547          * the one we put maxhash into.
 548          */
 549         if (sbp == &sbuf[nsbuf]) {
 550                 kmem_free(sbuf, sbsize);
 551                 xfs_dir_trace_g_du("sf: hash beyond end", dp, uio);
 552                 uio->uio_offset = XFS_DA_MAKE_COOKIE(mp, 0, 0, XFS_DA_MAXHASH);
 553                 *eofp = 1;
 554                 return 0;
 555         }
 556
 557         /*
 558          * Loop putting entries into the user buffer.
 559          */
 560         while (sbp < &sbuf[nsbuf]) {
 561                 /*
 562                  * Save the first resid in a run of equal-hashval entries
 563                  * so that we can back them out if they don't all fit.
 564                  */
 565                 if (sbp->seqno == 0 || sbp == sbuf)
 566                         lastresid = uio->uio_resid;
 567                 XFS_PUT_COOKIE(p.cook, mp, 0, sbp[1].seqno, sbp[1].hash);
 568                 p.ino = sbp->ino;
 569 #if XFS_BIG_INUMS
 570                 p.ino += mp->m_inoadd;
 571 #endif
 572                 p.name = sbp->name;
 573                 p.namelen = sbp->namelen;
 574                 retval = p.put(&p);
 575                 if (!p.done) {
 576                         uio->uio_offset =
 577                                 XFS_DA_MAKE_COOKIE(mp, 0, 0, sbp->hash);
 578                         kmem_free(sbuf, sbsize);
 579                         uio->uio_resid = lastresid;
 580                         xfs_dir_trace_g_du("sf: E-O-B", dp, uio);
 581                         return retval;
 582                 }
 583                 sbp++;
 584         }
 585         kmem_free(sbuf, sbsize);
 586         uio->uio_offset = p.cook.o;
 587         *eofp = 1;
 588         xfs_dir_trace_g_du("sf: E-O-F", dp, uio);
 589         return 0;
 590 }
 591
 592 /*
 593  * Look up a name in a shortform directory structure, replace the inode number.
 594  */
 595 int
 596 xfs_dir_shortform_replace(xfs_da_args_t *args)
 597 {
 598         xfs_dir_shortform_t *sf;
 599         xfs_dir_sf_entry_t *sfe;
 600         xfs_inode_t *dp;
 601         int i;
 602
 603         dp = args->dp;
 604         ASSERT(dp->i_df.if_flags & XFS_IFINLINE);
 605         /*
 606          * Catch the case where the conversion from shortform to leaf
 607          * failed part way through.
 608          */
 609         if (dp->i_d.di_size < sizeof(xfs_dir_sf_hdr_t)) {
 610                 ASSERT(XFS_FORCED_SHUTDOWN(dp->i_mount));
 611                 return XFS_ERROR(EIO);
 612         }
 613         ASSERT(dp->i_df.if_bytes == dp->i_d.di_size);
 614         ASSERT(dp->i_df.if_u1.if_data != NULL);
 615         sf = (xfs_dir_shortform_t *)dp->i_df.if_u1.if_data;
 616         if (args->namelen == 2 &&
 617             args->name[0] == '.' && args->name[1] == '.') {
 618                 /* XXX - replace assert? */
 619                 XFS_DIR_SF_PUT_DIRINO(&args->inumber, &sf->hdr.parent);
 620                 xfs_trans_log_inode(args->trans, dp, XFS_ILOG_DDATA);
 621                 return(0);
 622         }
 623         ASSERT(args->namelen != 1 || args->name[0] != '.');
 624         sfe = &sf->list[0];
 625         for (i = INT_GET(sf->hdr.count, ARCH_CONVERT)-1; i >= 0; i--) {
 626                 if (sfe->namelen == args->namelen &&
 627                     sfe->name[0] == args->name[0] &&
 628                     memcmp(args->name, sfe->name, args->namelen) == 0) {
 629                         ASSERT(memcmp((char *)&args->inumber,
 630                                 (char *)&sfe->inumber, sizeof(xfs_ino_t)));
 631                         XFS_DIR_SF_PUT_DIRINO(&args->inumber, &sfe->inumber);
 632                         xfs_trans_log_inode(args->trans, dp, XFS_ILOG_DDATA);
 633                         return(0);
 634                 }
 635                 sfe = XFS_DIR_SF_NEXTENTRY(sfe);
 636         }
 637         ASSERT(args->oknoent);
 638         return(XFS_ERROR(ENOENT));
 639 }
 640
 641 /*
 642  * Convert a leaf directory to shortform structure
 643  */
 644 int
 645 xfs_dir_leaf_to_shortform(xfs_da_args_t *iargs)
 646 {
 647         xfs_dir_leafblock_t *leaf;
 648         xfs_dir_leaf_hdr_t *hdr;
 649         xfs_dir_leaf_entry_t *entry;
 650         xfs_dir_leaf_name_t *namest;
 651         xfs_da_args_t args;
 652         xfs_inode_t *dp;
 653         xfs_ino_t parent;
 654         char *tmpbuffer;
 655         int retval, i;
 656         xfs_dabuf_t *bp;
 657
 658         dp = iargs->dp;
 659         tmpbuffer = kmem_alloc(XFS_LBSIZE(dp->i_mount), KM_SLEEP);
 660         ASSERT(tmpbuffer != NULL);
 661
 662         retval = xfs_da_read_buf(iargs->trans, iargs->dp, 0, -1, &bp,
 663                                                XFS_DATA_FORK);
 664         if (retval)
 665                 goto out;
 666         ASSERT(bp != NULL);
 667         memcpy(tmpbuffer, bp->data, XFS_LBSIZE(dp->i_mount));
 668         leaf = (xfs_dir_leafblock_t *)tmpbuffer;
 669         ASSERT(INT_GET(leaf->hdr.info.magic, ARCH_CONVERT) == XFS_DIR_LEAF_MAGIC);
 670         memset(bp->data, 0, XFS_LBSIZE(dp->i_mount));
 671
 672         /*
 673          * Find and special case the parent inode number
 674          */
 675         hdr = &leaf->hdr;
 676         entry = &leaf->entries[0];
 677         for (i = INT_GET(hdr->count, ARCH_CONVERT)-1; i >= 0; entry++, i--) {
 678                 namest = XFS_DIR_LEAF_NAMESTRUCT(leaf, INT_GET(entry->nameidx, ARCH_CONVERT));
 679                 if ((entry->namelen == 2) &&
 680                     (namest->name[0] == '.') &&
 681                     (namest->name[1] == '.')) {
 682                         XFS_DIR_SF_GET_DIRINO(&namest->inumber, &parent);
 683                         entry->nameidx = 0;
 684                 } else if ((entry->namelen == 1) && (namest->name[0] == '.')) {
 685                         entry->nameidx = 0;
 686                 }
 687         }
 688         retval = xfs_da_shrink_inode(iargs, 0, bp);
 689         if (retval)
 690                 goto out;
 691         retval = xfs_dir_shortform_create(iargs, parent);
 692         if (retval)
 693                 goto out;
 694
 695         /*
 696          * Copy the rest of the filenames
 697          */
 698         entry = &leaf->entries[0];
 699         args.dp = dp;
 700         args.firstblock = iargs->firstblock;
 701         args.flist = iargs->flist;
 702         args.total = iargs->total;
 703         args.whichfork = XFS_DATA_FORK;
 704         args.trans = iargs->trans;
 705         args.justcheck = 0;
 706         args.addname = args.oknoent = 1;
 707         for (i = 0; i < INT_GET(hdr->count, ARCH_CONVERT); entry++, i++) {
 708                 if (!entry->nameidx)
 709                         continue;
 710                 namest = XFS_DIR_LEAF_NAMESTRUCT(leaf, INT_GET(entry->nameidx, ARCH_CONVERT));
 711                 args.name = (char *)(namest->name);
 712                 args.namelen = entry->namelen;
 713                 args.hashval = INT_GET(entry->hashval, ARCH_CONVERT);
 714                 XFS_DIR_SF_GET_DIRINO(&namest->inumber, &args.inumber);
 715                 xfs_dir_shortform_addname(&args);
 716         }
 717
 718 out:
 719         kmem_free(tmpbuffer, XFS_LBSIZE(dp->i_mount));
 720         return(retval);
 721 }
 722
 723 /*
 724  * Convert from using a single leaf to a root node and a leaf.
 725  */
 726 int
 727 xfs_dir_leaf_to_node(xfs_da_args_t *args)
 728 {
 729         xfs_dir_leafblock_t *leaf;
 730         xfs_da_intnode_t *node;
 731         xfs_inode_t *dp;
 732         xfs_dabuf_t *bp1, *bp2;
 733         xfs_dablk_t blkno;
 734         int retval;
 735
 736         dp = args->dp;
 737         retval = xfs_da_grow_inode(args, &blkno);
 738         ASSERT(blkno == 1);
 739         if (retval)
 740                 return(retval);
 741         retval = xfs_da_read_buf(args->trans, args->dp, 0, -1, &bp1,
 742                                               XFS_DATA_FORK);
 743         if (retval)
 744                 return(retval);
 745         ASSERT(bp1 != NULL);
 746         retval = xfs_da_get_buf(args->trans, args->dp, 1, -1, &bp2,
 747                                              XFS_DATA_FORK);
 748         if (retval) {
 749                 xfs_da_buf_done(bp1);
 750                 return(retval);
 751         }
 752         ASSERT(bp2 != NULL);
 753         memcpy(bp2->data, bp1->data, XFS_LBSIZE(dp->i_mount));
 754         xfs_da_buf_done(bp1);
 755         xfs_da_log_buf(args->trans, bp2, 0, XFS_LBSIZE(dp->i_mount) - 1);
 756
 757         /*
 758          * Set up the new root node.
 759          */
 760         retval = xfs_da_node_create(args, 0, 1, &bp1, XFS_DATA_FORK);
 761         if (retval) {
 762                 xfs_da_buf_done(bp2);
 763                 return(retval);
 764         }
 765         node = bp1->data;
 766         leaf = bp2->data;
 767         ASSERT(INT_GET(leaf->hdr.info.magic, ARCH_CONVERT) == XFS_DIR_LEAF_MAGIC);
 768         INT_SET(node->btree[0].hashval, ARCH_CONVERT, INT_GET(leaf->entries[ INT_GET(leaf->hdr.count, ARCH_CONVERT)-1 ].hashval, ARCH_CONVERT));
 769         xfs_da_buf_done(bp2);
 770         INT_SET(node->btree[0].before, ARCH_CONVERT, blkno);
 771         INT_SET(node->hdr.count, ARCH_CONVERT, 1);
 772         xfs_da_log_buf(args->trans, bp1,
 773                 XFS_DA_LOGRANGE(node, &node->btree[0], sizeof(node->btree[0])));
 774         xfs_da_buf_done(bp1);
 775
 776         return(retval);
 777 }
 778
 779
 780 /*========================================================================
 781  * Routines used for growing the Btree.
 782  *========================================================================*/
 783
 784 /*
 785  * Create the initial contents of a leaf directory
 786  * or a leaf in a node directory.
 787  */
 788 STATIC int
 789 xfs_dir_leaf_create(xfs_da_args_t *args, xfs_dablk_t blkno, xfs_dabuf_t **bpp)
 790 {
 791         xfs_dir_leafblock_t *leaf;
 792         xfs_dir_leaf_hdr_t *hdr;
 793         xfs_inode_t *dp;
 794         xfs_dabuf_t *bp;
 795         int retval;
 796
 797         dp = args->dp;
 798         ASSERT(dp != NULL);
 799         retval = xfs_da_get_buf(args->trans, dp, blkno, -1, &bp, XFS_DATA_FORK);
 800         if (retval)
 801                 return(retval);
 802         ASSERT(bp != NULL);
 803         leaf = bp->data;
 804         memset((char *)leaf, 0, XFS_LBSIZE(dp->i_mount));
 805         hdr = &leaf->hdr;
 806         INT_SET(hdr->info.magic, ARCH_CONVERT, XFS_DIR_LEAF_MAGIC);
 807         INT_SET(hdr->firstused, ARCH_CONVERT, XFS_LBSIZE(dp->i_mount));
 808         if (!hdr->firstused)
 809                 INT_SET(hdr->firstused, ARCH_CONVERT, XFS_LBSIZE(dp->i_mount) - 1);
 810         INT_SET(hdr->freemap[0].base, ARCH_CONVERT, sizeof(xfs_dir_leaf_hdr_t));
 811         INT_SET(hdr->freemap[0].size, ARCH_CONVERT, INT_GET(hdr->firstused, ARCH_CONVERT) - INT_GET(hdr->freemap[0].base, ARCH_CONVERT));
 812
 813         xfs_da_log_buf(args->trans, bp, 0, XFS_LBSIZE(dp->i_mount) - 1);
 814
 815         *bpp = bp;
 816         return(0);
 817 }
 818
 819 /*
 820  * Split the leaf node, rebalance, then add the new entry.
 821  */
 822 int
 823 xfs_dir_leaf_split(xfs_da_state_t *state, xfs_da_state_blk_t *oldblk,
 824                                   xfs_da_state_blk_t *newblk)
 825 {
 826         xfs_dablk_t blkno;
 827         xfs_da_args_t *args;
 828         int error;
 829
 830         /*
 831          * Allocate space for a new leaf node.
 832          */
 833         args = state->args;
 834         ASSERT(args != NULL);
 835         ASSERT(oldblk->magic == XFS_DIR_LEAF_MAGIC);
 836         error = xfs_da_grow_inode(args, &blkno);
 837         if (error)
 838                 return(error);
 839         error = xfs_dir_leaf_create(args, blkno, &newblk->bp);
 840         if (error)
 841                 return(error);
 842         newblk->blkno = blkno;
 843         newblk->magic = XFS_DIR_LEAF_MAGIC;
 844
 845         /*
 846          * Rebalance the entries across the two leaves.
 847          */
 848         xfs_dir_leaf_rebalance(state, oldblk, newblk);
 849         error = xfs_da_blk_link(state, oldblk, newblk);
 850         if (error)
 851                 return(error);
 852
 853         /*
 854          * Insert the new entry in the correct block.
 855          */
 856         if (state->inleaf) {
 857                 error = xfs_dir_leaf_add(oldblk->bp, args, oldblk->index);
 858         } else {
 859                 error = xfs_dir_leaf_add(newblk->bp, args, newblk->index);
 860         }
 861
 862         /*
 863          * Update last hashval in each block since we added the name.
 864          */
 865         oldblk->hashval = xfs_dir_leaf_lasthash(oldblk->bp, NULL);
 866         newblk->hashval = xfs_dir_leaf_lasthash(newblk->bp, NULL);
 867         return(error);
 868 }
 869
 870 /*
 871  * Add a name to the leaf directory structure.
 872  *
 873  * Must take into account fragmented leaves and leaves where spacemap has
 874  * lost some freespace information (ie: holes).
 875  */
 876 int
 877 xfs_dir_leaf_add(xfs_dabuf_t *bp, xfs_da_args_t *args, int index)
 878 {
 879         xfs_dir_leafblock_t *leaf;
 880         xfs_dir_leaf_hdr_t *hdr;
 881         xfs_dir_leaf_map_t *map;
 882         int tablesize, entsize, sum, i, tmp, error;
 883
 884         leaf = bp->data;
 885         ASSERT(INT_GET(leaf->hdr.info.magic, ARCH_CONVERT) == XFS_DIR_LEAF_MAGIC);
 886         ASSERT((index >= 0) && (index <= INT_GET(leaf->hdr.count, ARCH_CONVERT)));
 887         hdr = &leaf->hdr;
 888         entsize = XFS_DIR_LEAF_ENTSIZE_BYNAME(args->namelen);
 889
 890         /*
 891          * Search through freemap for first-fit on new name length.
 892          * (may need to figure in size of entry struct too)
 893          */
 894         tablesize = (INT_GET(hdr->count, ARCH_CONVERT) + 1) * (uint)sizeof(xfs_dir_leaf_entry_t)
 895                         + (uint)sizeof(xfs_dir_leaf_hdr_t);
 896         map = &hdr->freemap[XFS_DIR_LEAF_MAPSIZE-1];
 897         for (sum = 0, i = XFS_DIR_LEAF_MAPSIZE-1; i >= 0; map--, i--) {
 898                 if (tablesize > INT_GET(hdr->firstused, ARCH_CONVERT)) {
 899                         sum += INT_GET(map->size, ARCH_CONVERT);
 900                         continue;
 901                 }
 902                 if (!map->size)
 903                         continue;       /* no space in this map */
 904                 tmp = entsize;
 905                 if (INT_GET(map->base, ARCH_CONVERT) < INT_GET(hdr->firstused, ARCH_CONVERT))
 906                         tmp += (uint)sizeof(xfs_dir_leaf_entry_t);
 907                 if (INT_GET(map->size, ARCH_CONVERT) >= tmp) {
 908                         if (!args->justcheck)
 909                                 xfs_dir_leaf_add_work(bp, args, index, i);
 910                         return(0);
 911                 }
 912                 sum += INT_GET(map->size, ARCH_CONVERT);
 913         }
 914
 915         /*
 916          * If there are no holes in the address space of the block,
 917          * and we don't have enough freespace, then compaction will do us
 918          * no good and we should just give up.
 919          */
 920         if (!hdr->holes && (sum < entsize))
 921                 return(XFS_ERROR(ENOSPC));
 922
 923         /*
 924          * Compact the entries to coalesce free space.
 925          * Pass the justcheck flag so the checking pass can return
 926          * an error, without changing anything, if it won't fit.
 927          */
 928         error = xfs_dir_leaf_compact(args->trans, bp,
 929                         args->total == 0 ?
 930                                 entsize +
 931                                 (uint)sizeof(xfs_dir_leaf_entry_t) : 0,
 932                         args->justcheck);
 933         if (error)
 934                 return(error);
 935         /*
 936          * After compaction, the block is guaranteed to have only one
 937          * free region, in freemap[0].  If it is not big enough, give up.
 938          */
 939         if (INT_GET(hdr->freemap[0].size, ARCH_CONVERT) <
 940             (entsize + (uint)sizeof(xfs_dir_leaf_entry_t)))
 941                 return(XFS_ERROR(ENOSPC));
 942
 943         if (!args->justcheck)
 944                 xfs_dir_leaf_add_work(bp, args, index, 0);
 945         return(0);
 946 }
 947
 948 /*
 949  * Add a name to a leaf directory structure.
 950  */
 951 STATIC void
 952 xfs_dir_leaf_add_work(xfs_dabuf_t *bp, xfs_da_args_t *args, int index,
 953                       int mapindex)
 954 {
 955         xfs_dir_leafblock_t *leaf;
 956         xfs_dir_leaf_hdr_t *hdr;
 957         xfs_dir_leaf_entry_t *entry;
 958         xfs_dir_leaf_name_t *namest;
 959         xfs_dir_leaf_map_t *map;
 960         /* REFERENCED */
 961         xfs_mount_t *mp;
 962         int tmp, i;
 963
 964         leaf = bp->data;
 965         ASSERT(INT_GET(leaf->hdr.info.magic, ARCH_CONVERT) == XFS_DIR_LEAF_MAGIC);
 966         hdr = &leaf->hdr;
 967         ASSERT((mapindex >= 0) && (mapindex < XFS_DIR_LEAF_MAPSIZE));
 968         ASSERT((index >= 0) && (index <= INT_GET(hdr->count, ARCH_CONVERT)));
 969
 970         /*
 971          * Force open some space in the entry array and fill it in.
 972          */
 973         entry = &leaf->entries[index];
 974         if (index < INT_GET(hdr->count, ARCH_CONVERT)) {
 975                 tmp  = INT_GET(hdr->count, ARCH_CONVERT) - index;
 976                 tmp *= (uint)sizeof(xfs_dir_leaf_entry_t);
 977                 memmove(entry + 1, entry, tmp);
 978                 xfs_da_log_buf(args->trans, bp,
 979                     XFS_DA_LOGRANGE(leaf, entry, tmp + (uint)sizeof(*entry)));
 980         }
 981         INT_MOD(hdr->count, ARCH_CONVERT, +1);
 982
 983         /*
 984          * Allocate space for the new string (at the end of the run).
 985          */
 986         map = &hdr->freemap[mapindex];
 987         mp = args->trans->t_mountp;
 988         ASSERT(INT_GET(map->base, ARCH_CONVERT) < XFS_LBSIZE(mp));
 989         ASSERT(INT_GET(map->size, ARCH_CONVERT) >= XFS_DIR_LEAF_ENTSIZE_BYNAME(args->namelen));
 990         ASSERT(INT_GET(map->size, ARCH_CONVERT) < XFS_LBSIZE(mp));
 991         INT_MOD(map->size, ARCH_CONVERT, -(XFS_DIR_LEAF_ENTSIZE_BYNAME(args->namelen)));
 992         INT_SET(entry->nameidx, ARCH_CONVERT, INT_GET(map->base, ARCH_CONVERT) + INT_GET(map->size, ARCH_CONVERT));
 993         INT_SET(entry->hashval, ARCH_CONVERT, args->hashval);
 994         entry->namelen = args->namelen;
 995         xfs_da_log_buf(args->trans, bp,
 996             XFS_DA_LOGRANGE(leaf, entry, sizeof(*entry)));
 997
 998         /*
 999          * Copy the string and inode number into the new space.
1000          */
1001         namest = XFS_DIR_LEAF_NAMESTRUCT(leaf, INT_GET(entry->nameidx, ARCH_CONVERT));
1002         XFS_DIR_SF_PUT_DIRINO(&args->inumber, &namest->inumber);
1003         memcpy(namest->name, args->name, args->namelen);
1004         xfs_da_log_buf(args->trans, bp,
1005             XFS_DA_LOGRANGE(leaf, namest, XFS_DIR_LEAF_ENTSIZE_BYENTRY(entry)));
1006
1007         /*
1008          * Update the control info for this leaf node
1009          */
1010         if (INT_GET(entry->nameidx, ARCH_CONVERT) < INT_GET(hdr->firstused, ARCH_CONVERT))
1011                 INT_COPY(hdr->firstused, entry->nameidx, ARCH_CONVERT);
1012         ASSERT(INT_GET(hdr->firstused, ARCH_CONVERT) >= ((INT_GET(hdr->count, ARCH_CONVERT)*sizeof(*entry))+sizeof(*hdr)));
1013         tmp = (INT_GET(hdr->count, ARCH_CONVERT)-1) * (uint)sizeof(xfs_dir_leaf_entry_t)
1014                         + (uint)sizeof(xfs_dir_leaf_hdr_t);
1015         map = &hdr->freemap[0];
1016         for (i = 0; i < XFS_DIR_LEAF_MAPSIZE; map++, i++) {
1017                 if (INT_GET(map->base, ARCH_CONVERT) == tmp) {
1018                         INT_MOD(map->base, ARCH_CONVERT, (uint)sizeof(xfs_dir_leaf_entry_t));
1019                         INT_MOD(map->size, ARCH_CONVERT, -((uint)sizeof(xfs_dir_leaf_entry_t)));
1020                 }
1021         }
1022         INT_MOD(hdr->namebytes, ARCH_CONVERT, args->namelen);
1023         xfs_da_log_buf(args->trans, bp,
1024                 XFS_DA_LOGRANGE(leaf, hdr, sizeof(*hdr)));
1025 }
1026
1027 /*
1028  * Garbage collect a leaf directory block by copying it to a new buffer.
1029  */
1030 STATIC int
1031 xfs_dir_leaf_compact(xfs_trans_t *trans, xfs_dabuf_t *bp, int musthave,
1032                      int justcheck)
1033 {
1034         xfs_dir_leafblock_t *leaf_s, *leaf_d;
1035         xfs_dir_leaf_hdr_t *hdr_s, *hdr_d;
1036         xfs_mount_t *mp;
1037         char *tmpbuffer;
1038         char *tmpbuffer2=NULL;
1039         int rval;
1040         int lbsize;
1041
1042         mp = trans->t_mountp;
1043         lbsize = XFS_LBSIZE(mp);
1044         tmpbuffer = kmem_alloc(lbsize, KM_SLEEP);
1045         ASSERT(tmpbuffer != NULL);
1046         memcpy(tmpbuffer, bp->data, lbsize);
1047
1048         /*
1049          * Make a second copy in case xfs_dir_leaf_moveents()
1050          * below destroys the original.
1051          */
1052         if (musthave || justcheck) {
1053                 tmpbuffer2 = kmem_alloc(lbsize, KM_SLEEP);
1054                 memcpy(tmpbuffer2, bp->data, lbsize);
1055         }
1056         memset(bp->data, 0, lbsize);
1057
1058         /*
1059          * Copy basic information
1060          */
1061         leaf_s = (xfs_dir_leafblock_t *)tmpbuffer;
1062         leaf_d = bp->data;
1063         hdr_s = &leaf_s->hdr;
1064         hdr_d = &leaf_d->hdr;
1065         hdr_d->info = hdr_s->info;      /* struct copy */
1066         INT_SET(hdr_d->firstused, ARCH_CONVERT, lbsize);
1067         if (!hdr_d->firstused)
1068                 INT_SET(hdr_d->firstused, ARCH_CONVERT, lbsize - 1);
1069         hdr_d->namebytes = 0;
1070         hdr_d->count = 0;
1071         hdr_d->holes = 0;
1072         INT_SET(hdr_d->freemap[0].base, ARCH_CONVERT, sizeof(xfs_dir_leaf_hdr_t));
1073         INT_SET(hdr_d->freemap[0].size, ARCH_CONVERT, INT_GET(hdr_d->firstused, ARCH_CONVERT) - INT_GET(hdr_d->freemap[0].base, ARCH_CONVERT));
1074
1075         /*
1076          * Copy all entry's in the same (sorted) order,
1077          * but allocate filenames packed and in sequence.
1078          * This changes the source (leaf_s) as well.
1079          */
1080         xfs_dir_leaf_moveents(leaf_s, 0, leaf_d, 0, (int)INT_GET(hdr_s->count, ARCH_CONVERT), mp);
1081
1082         if (musthave && INT_GET(hdr_d->freemap[0].size, ARCH_CONVERT) < musthave)
1083                 rval = XFS_ERROR(ENOSPC);
1084         else
1085                 rval = 0;
1086
1087         if (justcheck || rval == ENOSPC) {
1088                 ASSERT(tmpbuffer2);
1089                 memcpy(bp->data, tmpbuffer2, lbsize);
1090         } else {
1091                 xfs_da_log_buf(trans, bp, 0, lbsize - 1);
1092         }
1093
1094         kmem_free(tmpbuffer, lbsize);
1095         if (musthave || justcheck)
1096                 kmem_free(tmpbuffer2, lbsize);
1097         return(rval);
1098 }
1099
1100 /*
1101  * Redistribute the directory entries between two leaf nodes,
1102  * taking into account the size of the new entry.
1103  *
1104  * NOTE: if new block is empty, then it will get the upper half of old block.
1105  */
1106 STATIC void
1107 xfs_dir_leaf_rebalance(xfs_da_state_t *state, xfs_da_state_blk_t *blk1,
1108                                       xfs_da_state_blk_t *blk2)
1109 {
1110         xfs_da_state_blk_t *tmp_blk;
1111         xfs_dir_leafblock_t *leaf1, *leaf2;
1112         xfs_dir_leaf_hdr_t *hdr1, *hdr2;
1113         int count, totallen, max, space, swap;
1114
1115         /*
1116          * Set up environment.
1117          */
1118         ASSERT(blk1->magic == XFS_DIR_LEAF_MAGIC);
1119         ASSERT(blk2->magic == XFS_DIR_LEAF_MAGIC);
1120         leaf1 = blk1->bp->data;
1121         leaf2 = blk2->bp->data;
1122         ASSERT(INT_GET(leaf1->hdr.info.magic, ARCH_CONVERT) == XFS_DIR_LEAF_MAGIC);
1123         ASSERT(INT_GET(leaf2->hdr.info.magic, ARCH_CONVERT) == XFS_DIR_LEAF_MAGIC);
1124
1125         /*
1126          * Check ordering of blocks, reverse if it makes things simpler.
1127          */
1128         swap = 0;
1129         if (xfs_dir_leaf_order(blk1->bp, blk2->bp)) {
1130                 tmp_blk = blk1;
1131                 blk1 = blk2;
1132                 blk2 = tmp_blk;
1133                 leaf1 = blk1->bp->data;
1134                 leaf2 = blk2->bp->data;
1135                 swap = 1;
1136         }
1137         hdr1 = &leaf1->hdr;
1138         hdr2 = &leaf2->hdr;
1139
1140         /*
1141          * Examine entries until we reduce the absolute difference in
1142          * byte usage between the two blocks to a minimum.  Then get
1143          * the direction to copy and the number of elements to move.
1144          */
1145         state->inleaf = xfs_dir_leaf_figure_balance(state, blk1, blk2,
1146                                                            &count, &totallen);
1147         if (swap)
1148                 state->inleaf = !state->inleaf;
1149
1150         /*
1151          * Move any entries required from leaf to leaf:
1152          */
1153         if (count < INT_GET(hdr1->count, ARCH_CONVERT)) {
1154                 /*
1155                  * Figure the total bytes to be added to the destination leaf.
1156                  */
1157                 count = INT_GET(hdr1->count, ARCH_CONVERT) - count;     /* number entries being moved */
1158                 space  = INT_GET(hdr1->namebytes, ARCH_CONVERT) - totallen;
1159                 space += count * ((uint)sizeof(xfs_dir_leaf_name_t)-1);
1160                 space += count * (uint)sizeof(xfs_dir_leaf_entry_t);
1161
1162                 /*
1163                  * leaf2 is the destination, compact it if it looks tight.
1164                  */
1165                 max  = INT_GET(hdr2->firstused, ARCH_CONVERT) - (uint)sizeof(xfs_dir_leaf_hdr_t);
1166                 max -= INT_GET(hdr2->count, ARCH_CONVERT) * (uint)sizeof(xfs_dir_leaf_entry_t);
1167                 if (space > max) {
1168                         xfs_dir_leaf_compact(state->args->trans, blk2->bp,
1169                                                                  0, 0);
1170                 }
1171
1172                 /*
1173                  * Move high entries from leaf1 to low end of leaf2.
1174                  */
1175                 xfs_dir_leaf_moveents(leaf1, INT_GET(hdr1->count, ARCH_CONVERT) - count,
1176                                              leaf2, 0, count, state->mp);
1177
1178                 xfs_da_log_buf(state->args->trans, blk1->bp, 0,
1179                                                    state->blocksize-1);
1180                 xfs_da_log_buf(state->args->trans, blk2->bp, 0,
1181                                                    state->blocksize-1);
1182
1183         } else if (count > INT_GET(hdr1->count, ARCH_CONVERT)) {
1184                 /*
1185                  * Figure the total bytes to be added to the destination leaf.
1186                  */
1187                 count -= INT_GET(hdr1->count, ARCH_CONVERT);            /* number entries being moved */
1188                 space  = totallen - INT_GET(hdr1->namebytes, ARCH_CONVERT);
1189                 space += count * ((uint)sizeof(xfs_dir_leaf_name_t)-1);
1190                 space += count * (uint)sizeof(xfs_dir_leaf_entry_t);
1191
1192                 /*
1193                  * leaf1 is the destination, compact it if it looks tight.
1194                  */
1195                 max  = INT_GET(hdr1->firstused, ARCH_CONVERT) - (uint)sizeof(xfs_dir_leaf_hdr_t);
1196                 max -= INT_GET(hdr1->count, ARCH_CONVERT) * (uint)sizeof(xfs_dir_leaf_entry_t);
1197                 if (space > max) {
1198                         xfs_dir_leaf_compact(state->args->trans, blk1->bp,
1199                                                                  0, 0);
1200                 }
1201
1202                 /*
1203                  * Move low entries from leaf2 to high end of leaf1.
1204                  */
1205                 xfs_dir_leaf_moveents(leaf2, 0, leaf1, (int)INT_GET(hdr1->count, ARCH_CONVERT),
1206                                              count, state->mp);
1207
1208                 xfs_da_log_buf(state->args->trans, blk1->bp, 0,
1209                                                    state->blocksize-1);
1210                 xfs_da_log_buf(state->args->trans, blk2->bp, 0,
1211                                                    state->blocksize-1);
1212         }
1213
1214         /*
1215          * Copy out last hashval in each block for B-tree code.
1216          */
1217         blk1->hashval = INT_GET(leaf1->entries[ INT_GET(leaf1->hdr.count, ARCH_CONVERT)-1 ].hashval, ARCH_CONVERT);
1218         blk2->hashval = INT_GET(leaf2->entries[ INT_GET(leaf2->hdr.count, ARCH_CONVERT)-1 ].hashval, ARCH_CONVERT);
1219
1220         /*
1221          * Adjust the expected index for insertion.
1222          * GROT: this doesn't work unless blk2 was originally empty.
1223          */
1224         if (!state->inleaf) {
1225                 blk2->index = blk1->index - INT_GET(leaf1->hdr.count, ARCH_CONVERT);
1226         }
1227 }
1228
1229 /*
1230  * Examine entries until we reduce the absolute difference in
1231  * byte usage between the two blocks to a minimum.
1232  * GROT: Is this really necessary?  With other than a 512 byte blocksize,
1233  * GROT: there will always be enough room in either block for a new entry.
1234  * GROT: Do a double-split for this case?
1235  */
1236 STATIC int
1237 xfs_dir_leaf_figure_balance(xfs_da_state_t *state,
1238                                            xfs_da_state_blk_t *blk1,
1239                                            xfs_da_state_blk_t *blk2,
1240                                            int *countarg, int *namebytesarg)
1241 {
1242         xfs_dir_leafblock_t *leaf1, *leaf2;
1243         xfs_dir_leaf_hdr_t *hdr1, *hdr2;
1244         xfs_dir_leaf_entry_t *entry;
1245         int count, max, totallen, half;
1246         int lastdelta, foundit, tmp;
1247
1248         /*
1249          * Set up environment.
1250          */
1251         leaf1 = blk1->bp->data;
1252         leaf2 = blk2->bp->data;
1253         hdr1 = &leaf1->hdr;
1254         hdr2 = &leaf2->hdr;
1255         foundit = 0;
1256         totallen = 0;
1257
1258         /*
1259          * Examine entries until we reduce the absolute difference in
1260          * byte usage between the two blocks to a minimum.
1261          */
1262         max = INT_GET(hdr1->count, ARCH_CONVERT) + INT_GET(hdr2->count, ARCH_CONVERT);
1263         half  = (max+1) * (uint)(sizeof(*entry)+sizeof(xfs_dir_leaf_entry_t)-1);
1264         half += INT_GET(hdr1->namebytes, ARCH_CONVERT) + INT_GET(hdr2->namebytes, ARCH_CONVERT) + state->args->namelen;
1265         half /= 2;
1266         lastdelta = state->blocksize;
1267         entry = &leaf1->entries[0];
1268         for (count = 0; count < max; entry++, count++) {
1269
1270 #define XFS_DIR_ABS(A)  (((A) < 0) ? -(A) : (A))
1271                 /*
1272                  * The new entry is in the first block, account for it.
1273                  */
1274                 if (count == blk1->index) {
1275                         tmp = totallen + (uint)sizeof(*entry)
1276                                 + XFS_DIR_LEAF_ENTSIZE_BYNAME(state->args->namelen);
1277                         if (XFS_DIR_ABS(half - tmp) > lastdelta)
1278                                 break;
1279                         lastdelta = XFS_DIR_ABS(half - tmp);
1280                         totallen = tmp;
1281                         foundit = 1;
1282                 }
1283
1284                 /*
1285                  * Wrap around into the second block if necessary.
1286                  */
1287                 if (count == INT_GET(hdr1->count, ARCH_CONVERT)) {
1288                         leaf1 = leaf2;
1289                         entry = &leaf1->entries[0];
1290                 }
1291
1292                 /*
1293                  * Figure out if next leaf entry would be too much.
1294                  */
1295                 tmp = totallen + (uint)sizeof(*entry)
1296                                 + XFS_DIR_LEAF_ENTSIZE_BYENTRY(entry);
1297                 if (XFS_DIR_ABS(half - tmp) > lastdelta)
1298                         break;
1299                 lastdelta = XFS_DIR_ABS(half - tmp);
1300                 totallen = tmp;
1301 #undef XFS_DIR_ABS
1302         }
1303
1304         /*
1305          * Calculate the number of namebytes that will end up in lower block.
1306          * If new entry not in lower block, fix up the count.
1307          */
1308         totallen -=
1309                 count * (uint)(sizeof(*entry)+sizeof(xfs_dir_leaf_entry_t)-1);
1310         if (foundit) {
1311                 totallen -= (sizeof(*entry)+sizeof(xfs_dir_leaf_entry_t)-1) +
1312                             state->args->namelen;
1313         }
1314
1315         *countarg = count;
1316         *namebytesarg = totallen;
1317         return(foundit);
1318 }
1319
1320 /*========================================================================
1321  * Routines used for shrinking the Btree.
1322  *========================================================================*/
1323
1324 /*
1325  * Check a leaf block and its neighbors to see if the block should be
1326  * collapsed into one or the other neighbor.  Always keep the block
1327  * with the smaller block number.
1328  * If the current block is over 50% full, don't try to join it, return 0.
1329  * If the block is empty, fill in the state structure and return 2.
1330  * If it can be collapsed, fill in the state structure and return 1.
1331  * If nothing can be done, return 0.
1332  */
1333 int
1334 xfs_dir_leaf_toosmall(xfs_da_state_t *state, int *action)
1335 {
1336         xfs_dir_leafblock_t *leaf;
1337         xfs_da_state_blk_t *blk;
1338         xfs_da_blkinfo_t *info;
1339         int count, bytes, forward, error, retval, i;
1340         xfs_dablk_t blkno;
1341         xfs_dabuf_t *bp;
1342
1343         /*
1344          * Check for the degenerate case of the block being over 50% full.
1345          * If so, it's not worth even looking to see if we might be able
1346          * to coalesce with a sibling.
1347          */
1348         blk = &state->path.blk[ state->path.active-1 ];
1349         info = blk->bp->data;
1350         ASSERT(INT_GET(info->magic, ARCH_CONVERT) == XFS_DIR_LEAF_MAGIC);
1351         leaf = (xfs_dir_leafblock_t *)info;
1352         count = INT_GET(leaf->hdr.count, ARCH_CONVERT);
1353         bytes = (uint)sizeof(xfs_dir_leaf_hdr_t) +
1354                 count * (uint)sizeof(xfs_dir_leaf_entry_t) +
1355                 count * ((uint)sizeof(xfs_dir_leaf_name_t)-1) +
1356                 INT_GET(leaf->hdr.namebytes, ARCH_CONVERT);
1357         if (bytes > (state->blocksize >> 1)) {
1358                 *action = 0;    /* blk over 50%, don't try to join */
1359                 return(0);
1360         }
1361
1362         /*
1363          * Check for the degenerate case of the block being empty.
1364          * If the block is empty, we'll simply delete it, no need to
1365          * coalesce it with a sibling block.  We choose (aribtrarily)
1366          * to merge with the forward block unless it is NULL.
1367          */
1368         if (count == 0) {
1369                 /*
1370                  * Make altpath point to the block we want to keep and
1371                  * path point to the block we want to drop (this one).
1372                  */
1373                 forward = info->forw;
1374                 memcpy(&state->altpath, &state->path, sizeof(state->path));
1375                 error = xfs_da_path_shift(state, &state->altpath, forward,
1376                                                  0, &retval);
1377                 if (error)
1378                         return(error);
1379                 if (retval) {
1380                         *action = 0;
1381                 } else {
1382                         *action = 2;
1383                 }
1384                 return(0);
1385         }
1386
1387         /*
1388          * Examine each sibling block to see if we can coalesce with
1389          * at least 25% free space to spare.  We need to figure out
1390          * whether to merge with the forward or the backward block.
1391          * We prefer coalescing with the lower numbered sibling so as
1392          * to shrink a directory over time.
1393          */
1394         forward = (INT_GET(info->forw, ARCH_CONVERT) < INT_GET(info->back, ARCH_CONVERT));      /* start with smaller blk num */
1395         for (i = 0; i < 2; forward = !forward, i++) {
1396                 if (forward)
1397                         blkno = INT_GET(info->forw, ARCH_CONVERT);
1398                 else
1399                         blkno = INT_GET(info->back, ARCH_CONVERT);
1400                 if (blkno == 0)
1401                         continue;
1402                 error = xfs_da_read_buf(state->args->trans, state->args->dp,
1403                                                             blkno, -1, &bp,
1404                                                             XFS_DATA_FORK);
1405                 if (error)
1406                         return(error);
1407                 ASSERT(bp != NULL);
1408
1409                 leaf = (xfs_dir_leafblock_t *)info;
1410                 count  = INT_GET(leaf->hdr.count, ARCH_CONVERT);
1411                 bytes  = state->blocksize - (state->blocksize>>2);
1412                 bytes -= INT_GET(leaf->hdr.namebytes, ARCH_CONVERT);
1413                 leaf = bp->data;
1414                 ASSERT(INT_GET(leaf->hdr.info.magic, ARCH_CONVERT) == XFS_DIR_LEAF_MAGIC);
1415                 count += INT_GET(leaf->hdr.count, ARCH_CONVERT);
1416                 bytes -= INT_GET(leaf->hdr.namebytes, ARCH_CONVERT);
1417                 bytes -= count * ((uint)sizeof(xfs_dir_leaf_name_t) - 1);
1418                 bytes -= count * (uint)sizeof(xfs_dir_leaf_entry_t);
1419                 bytes -= (uint)sizeof(xfs_dir_leaf_hdr_t);
1420                 if (bytes >= 0)
1421                         break;  /* fits with at least 25% to spare */
1422
1423                 xfs_da_brelse(state->args->trans, bp);
1424         }
1425         if (i >= 2) {
1426                 *action = 0;
1427                 return(0);
1428         }
1429         xfs_da_buf_done(bp);
1430
1431         /*
1432          * Make altpath point to the block we want to keep (the lower
1433          * numbered block) and path point to the block we want to drop.
1434          */
1435         memcpy(&state->altpath, &state->path, sizeof(state->path));
1436         if (blkno < blk->blkno) {
1437                 error = xfs_da_path_shift(state, &state->altpath, forward,
1438                                                  0, &retval);
1439         } else {
1440                 error = xfs_da_path_shift(state, &state->path, forward,
1441                                                  0, &retval);
1442         }
1443         if (error)
1444                 return(error);
1445         if (retval) {
1446                 *action = 0;
1447         } else {
1448                 *action = 1;
1449         }
1450         return(0);
1451 }
1452
1453 /*
1454  * Remove a name from the leaf directory structure.
1455  *
1456  * Return 1 if leaf is less than 37% full, 0 if >= 37% full.
1457  * If two leaves are 37% full, when combined they will leave 25% free.
1458  */
1459 int
1460 xfs_dir_leaf_remove(xfs_trans_t *trans, xfs_dabuf_t *bp, int index)
1461 {
1462         xfs_dir_leafblock_t *leaf;
1463         xfs_dir_leaf_hdr_t *hdr;
1464         xfs_dir_leaf_map_t *map;
1465         xfs_dir_leaf_entry_t *entry;
1466         xfs_dir_leaf_name_t *namest;
1467         int before, after, smallest, entsize;
1468         int tablesize, tmp, i;
1469         xfs_mount_t *mp;
1470
1471         leaf = bp->data;
1472         ASSERT(INT_GET(leaf->hdr.info.magic, ARCH_CONVERT) == XFS_DIR_LEAF_MAGIC);
1473         hdr = &leaf->hdr;
1474         mp = trans->t_mountp;
1475         ASSERT((INT_GET(hdr->count, ARCH_CONVERT) > 0) && (INT_GET(hdr->count, ARCH_CONVERT) < (XFS_LBSIZE(mp)/8)));
1476         ASSERT((index >= 0) && (index < INT_GET(hdr->count, ARCH_CONVERT)));
1477         ASSERT(INT_GET(hdr->firstused, ARCH_CONVERT) >= ((INT_GET(hdr->count, ARCH_CONVERT)*sizeof(*entry))+sizeof(*hdr)));
1478         entry = &leaf->entries[index];
1479         ASSERT(INT_GET(entry->nameidx, ARCH_CONVERT) >= INT_GET(hdr->firstused, ARCH_CONVERT));
1480         ASSERT(INT_GET(entry->nameidx, ARCH_CONVERT) < XFS_LBSIZE(mp));
1481
1482         /*
1483          * Scan through free region table:
1484          *    check for adjacency of free'd entry with an existing one,
1485          *    find smallest free region in case we need to replace it,
1486          *    adjust any map that borders the entry table,
1487          */
1488         tablesize = INT_GET(hdr->count, ARCH_CONVERT) * (uint)sizeof(xfs_dir_leaf_entry_t)
1489                         + (uint)sizeof(xfs_dir_leaf_hdr_t);
1490         map = &hdr->freemap[0];
1491         tmp = INT_GET(map->size, ARCH_CONVERT);
1492         before = after = -1;
1493         smallest = XFS_DIR_LEAF_MAPSIZE - 1;
1494         entsize = XFS_DIR_LEAF_ENTSIZE_BYENTRY(entry);
1495         for (i = 0; i < XFS_DIR_LEAF_MAPSIZE; map++, i++) {
1496                 ASSERT(INT_GET(map->base, ARCH_CONVERT) < XFS_LBSIZE(mp));
1497                 ASSERT(INT_GET(map->size, ARCH_CONVERT) < XFS_LBSIZE(mp));
1498                 if (INT_GET(map->base, ARCH_CONVERT) == tablesize) {
1499                         INT_MOD(map->base, ARCH_CONVERT, -((uint)sizeof(xfs_dir_leaf_entry_t)));
1500                         INT_MOD(map->size, ARCH_CONVERT, (uint)sizeof(xfs_dir_leaf_entry_t));
1501                 }
1502
1503                 if ((INT_GET(map->base, ARCH_CONVERT) + INT_GET(map->size, ARCH_CONVERT)) == INT_GET(entry->nameidx, ARCH_CONVERT)) {
1504                         before = i;
1505                 } else if (INT_GET(map->base, ARCH_CONVERT) == (INT_GET(entry->nameidx, ARCH_CONVERT) + entsize)) {
1506                         after = i;
1507                 } else if (INT_GET(map->size, ARCH_CONVERT) < tmp) {
1508                         tmp = INT_GET(map->size, ARCH_CONVERT);
1509                         smallest = i;
1510                 }
1511         }
1512
1513         /*
1514          * Coalesce adjacent freemap regions,
1515          * or replace the smallest region.
1516          */
1517         if ((before >= 0) || (after >= 0)) {
1518                 if ((before >= 0) && (after >= 0)) {
1519                         map = &hdr->freemap[before];
1520                         INT_MOD(map->size, ARCH_CONVERT, entsize);
1521                         INT_MOD(map->size, ARCH_CONVERT, INT_GET(hdr->freemap[after].size, ARCH_CONVERT));
1522                         hdr->freemap[after].base = 0;
1523                         hdr->freemap[after].size = 0;
1524                 } else if (before >= 0) {
1525                         map = &hdr->freemap[before];
1526                         INT_MOD(map->size, ARCH_CONVERT, entsize);
1527                 } else {
1528                         map = &hdr->freemap[after];
1529                         INT_COPY(map->base, entry->nameidx, ARCH_CONVERT);
1530                         INT_MOD(map->size, ARCH_CONVERT, entsize);
1531                 }
1532         } else {
1533                 /*
1534                  * Replace smallest region (if it is smaller than free'd entry)
1535                  */
1536                 map = &hdr->freemap[smallest];
1537                 if (INT_GET(map->size, ARCH_CONVERT) < entsize) {
1538                         INT_COPY(map->base, entry->nameidx, ARCH_CONVERT);
1539                         INT_SET(map->size, ARCH_CONVERT, entsize);
1540                 }
1541         }
1542
1543         /*
1544          * Did we remove the first entry?
1545          */
1546         if (INT_GET(entry->nameidx, ARCH_CONVERT) == INT_GET(hdr->firstused, ARCH_CONVERT))
1547                 smallest = 1;
1548         else
1549                 smallest = 0;
1550
1551         /*
1552          * Compress the remaining entries and zero out the removed stuff.
1553          */
1554         namest = XFS_DIR_LEAF_NAMESTRUCT(leaf, INT_GET(entry->nameidx, ARCH_CONVERT));
1555         memset((char *)namest, 0, entsize);
1556         xfs_da_log_buf(trans, bp, XFS_DA_LOGRANGE(leaf, namest, entsize));
1557
1558         INT_MOD(hdr->namebytes, ARCH_CONVERT, -(entry->namelen));
1559         tmp = (INT_GET(hdr->count, ARCH_CONVERT) - index) * (uint)sizeof(xfs_dir_leaf_entry_t);
1560         memmove(entry, entry + 1, tmp);
1561         INT_MOD(hdr->count, ARCH_CONVERT, -1);
1562         xfs_da_log_buf(trans, bp,
1563             XFS_DA_LOGRANGE(leaf, entry, tmp + (uint)sizeof(*entry)));
1564         entry = &leaf->entries[INT_GET(hdr->count, ARCH_CONVERT)];
1565         memset((char *)entry, 0, sizeof(xfs_dir_leaf_entry_t));
1566
1567         /*
1568          * If we removed the first entry, re-find the first used byte
1569          * in the name area.  Note that if the entry was the "firstused",
1570          * then we don't have a "hole" in our block resulting from
1571          * removing the name.
1572          */
1573         if (smallest) {
1574                 tmp = XFS_LBSIZE(mp);
1575                 entry = &leaf->entries[0];
1576                 for (i = INT_GET(hdr->count, ARCH_CONVERT)-1; i >= 0; entry++, i--) {
1577                         ASSERT(INT_GET(entry->nameidx, ARCH_CONVERT) >= INT_GET(hdr->firstused, ARCH_CONVERT));
1578                         ASSERT(INT_GET(entry->nameidx, ARCH_CONVERT) < XFS_LBSIZE(mp));
1579                         if (INT_GET(entry->nameidx, ARCH_CONVERT) < tmp)
1580                                 tmp = INT_GET(entry->nameidx, ARCH_CONVERT);
1581                 }
1582                 INT_SET(hdr->firstused, ARCH_CONVERT, tmp);
1583                 if (!hdr->firstused)
1584                         INT_SET(hdr->firstused, ARCH_CONVERT, tmp - 1);
1585         } else {
1586                 hdr->holes = 1;         /* mark as needing compaction */
1587         }
1588
1589         xfs_da_log_buf(trans, bp, XFS_DA_LOGRANGE(leaf, hdr, sizeof(*hdr)));
1590
1591         /*
1592          * Check if leaf is less than 50% full, caller may want to
1593          * "join" the leaf with a sibling if so.
1594          */
1595         tmp  = (uint)sizeof(xfs_dir_leaf_hdr_t);
1596         tmp += INT_GET(leaf->hdr.count, ARCH_CONVERT) * (uint)sizeof(xfs_dir_leaf_entry_t);
1597         tmp += INT_GET(leaf->hdr.count, ARCH_CONVERT) * ((uint)sizeof(xfs_dir_leaf_name_t) - 1);
1598         tmp += INT_GET(leaf->hdr.namebytes, ARCH_CONVERT);
1599         if (tmp < mp->m_dir_magicpct)
1600                 return(1);                      /* leaf is < 37% full */
1601         return(0);
1602 }
1603
1604 /*
1605  * Move all the directory entries from drop_leaf into save_leaf.
1606  */
1607 void
1608 xfs_dir_leaf_unbalance(xfs_da_state_t *state, xfs_da_state_blk_t *drop_blk,
1609                                       xfs_da_state_blk_t *save_blk)
1610 {
1611         xfs_dir_leafblock_t *drop_leaf, *save_leaf, *tmp_leaf;
1612         xfs_dir_leaf_hdr_t *drop_hdr, *save_hdr, *tmp_hdr;
1613         xfs_mount_t *mp;
1614         char *tmpbuffer;
1615
1616         /*
1617          * Set up environment.
1618          */
1619         mp = state->mp;
1620         ASSERT(drop_blk->magic == XFS_DIR_LEAF_MAGIC);
1621         ASSERT(save_blk->magic == XFS_DIR_LEAF_MAGIC);
1622         drop_leaf = drop_blk->bp->data;
1623         save_leaf = save_blk->bp->data;
1624         ASSERT(INT_GET(drop_leaf->hdr.info.magic, ARCH_CONVERT) == XFS_DIR_LEAF_MAGIC);
1625         ASSERT(INT_GET(save_leaf->hdr.info.magic, ARCH_CONVERT) == XFS_DIR_LEAF_MAGIC);
1626         drop_hdr = &drop_leaf->hdr;
1627         save_hdr = &save_leaf->hdr;
1628
1629         /*
1630          * Save last hashval from dying block for later Btree fixup.
1631          */
1632         drop_blk->hashval = INT_GET(drop_leaf->entries[ drop_leaf->hdr.count-1 ].hashval, ARCH_CONVERT);
1633
1634         /*
1635          * Check if we need a temp buffer, or can we do it in place.
1636          * Note that we don't check "leaf" for holes because we will
1637          * always be dropping it, toosmall() decided that for us already.
1638          */
1639         if (save_hdr->holes == 0) {
1640                 /*
1641                  * dest leaf has no holes, so we add there.  May need
1642                  * to make some room in the entry array.
1643                  */
1644                 if (xfs_dir_leaf_order(save_blk->bp, drop_blk->bp)) {
1645                         xfs_dir_leaf_moveents(drop_leaf, 0, save_leaf, 0,
1646                                                  (int)INT_GET(drop_hdr->count, ARCH_CONVERT), mp);
1647                 } else {
1648                         xfs_dir_leaf_moveents(drop_leaf, 0,
1649                                               save_leaf, INT_GET(save_hdr->count, ARCH_CONVERT),
1650                                               (int)INT_GET(drop_hdr->count, ARCH_CONVERT), mp);
1651                 }
1652         } else {
1653                 /*
1654                  * Destination has holes, so we make a temporary copy
1655                  * of the leaf and add them both to that.
1656                  */
1657                 tmpbuffer = kmem_alloc(state->blocksize, KM_SLEEP);
1658                 ASSERT(tmpbuffer != NULL);
1659                 memset(tmpbuffer, 0, state->blocksize);
1660                 tmp_leaf = (xfs_dir_leafblock_t *)tmpbuffer;
1661                 tmp_hdr = &tmp_leaf->hdr;
1662                 tmp_hdr->info = save_hdr->info; /* struct copy */
1663                 tmp_hdr->count = 0;
1664                 INT_SET(tmp_hdr->firstused, ARCH_CONVERT, state->blocksize);
1665                 if (!tmp_hdr->firstused)
1666                         INT_SET(tmp_hdr->firstused, ARCH_CONVERT, state->blocksize - 1);
1667                 tmp_hdr->namebytes = 0;
1668                 if (xfs_dir_leaf_order(save_blk->bp, drop_blk->bp)) {
1669                         xfs_dir_leaf_moveents(drop_leaf, 0, tmp_leaf, 0,
1670                                                  (int)INT_GET(drop_hdr->count, ARCH_CONVERT), mp);
1671                         xfs_dir_leaf_moveents(save_leaf, 0,
1672                                               tmp_leaf, INT_GET(tmp_leaf->hdr.count, ARCH_CONVERT),
1673                                               (int)INT_GET(save_hdr->count, ARCH_CONVERT), mp);
1674                 } else {
1675                         xfs_dir_leaf_moveents(save_leaf, 0, tmp_leaf, 0,
1676                                                  (int)INT_GET(save_hdr->count, ARCH_CONVERT), mp);
1677                         xfs_dir_leaf_moveents(drop_leaf, 0,
1678                                               tmp_leaf, INT_GET(tmp_leaf->hdr.count, ARCH_CONVERT),
1679                                               (int)INT_GET(drop_hdr->count, ARCH_CONVERT), mp);
1680                 }
1681                 memcpy(save_leaf, tmp_leaf, state->blocksize);
1682                 kmem_free(tmpbuffer, state->blocksize);
1683         }
1684
1685         xfs_da_log_buf(state->args->trans, save_blk->bp, 0,
1686                                            state->blocksize - 1);
1687
1688         /*
1689          * Copy out last hashval in each block for B-tree code.
1690          */
1691         save_blk->hashval = INT_GET(save_leaf->entries[ INT_GET(save_leaf->hdr.count, ARCH_CONVERT)-1 ].hashval, ARCH_CONVERT);
1692 }
1693
1694 /*========================================================================
1695  * Routines used for finding things in the Btree.
1696  *========================================================================*/
1697
1698 /*
1699  * Look up a name in a leaf directory structure.
1700  * This is the internal routine, it uses the caller's buffer.
1701  *
1702  * Note that duplicate keys are allowed, but only check within the
1703  * current leaf node.  The Btree code must check in adjacent leaf nodes.
1704  *
1705  * Return in *index the index into the entry[] array of either the found
1706  * entry, or where the entry should have been (insert before that entry).
1707  *
1708  * Don't change the args->inumber unless we find the filename.
1709  */
1710 int
1711 xfs_dir_leaf_lookup_int(xfs_dabuf_t *bp, xfs_da_args_t *args, int *index)
1712 {
1713         xfs_dir_leafblock_t *leaf;
1714         xfs_dir_leaf_entry_t *entry;
1715         xfs_dir_leaf_name_t *namest;
1716         int probe, span;
1717         xfs_dahash_t hashval;
1718
1719         leaf = bp->data;
1720         ASSERT(INT_GET(leaf->hdr.info.magic, ARCH_CONVERT) == XFS_DIR_LEAF_MAGIC);
1721         ASSERT(INT_GET(leaf->hdr.count, ARCH_CONVERT) < (XFS_LBSIZE(args->dp->i_mount)/8));
1722
1723         /*
1724          * Binary search.  (note: small blocks will skip this loop)
1725          */
1726         hashval = args->hashval;
1727         probe = span = INT_GET(leaf->hdr.count, ARCH_CONVERT) / 2;
1728         for (entry = &leaf->entries[probe]; span > 4;
1729                    entry = &leaf->entries[probe]) {
1730                 span /= 2;
1731                 if (INT_GET(entry->hashval, ARCH_CONVERT) < hashval)
1732                         probe += span;
1733                 else if (INT_GET(entry->hashval, ARCH_CONVERT) > hashval)
1734                         probe -= span;
1735                 else
1736                         break;
1737         }
1738         ASSERT((probe >= 0) && \
1739                ((!leaf->hdr.count) || (probe < INT_GET(leaf->hdr.count, ARCH_CONVERT))));
1740         ASSERT((span <= 4) || (INT_GET(entry->hashval, ARCH_CONVERT) == hashval));
1741
1742         /*
1743          * Since we may have duplicate hashval's, find the first matching
1744          * hashval in the leaf.
1745          */
1746         while ((probe > 0) && (INT_GET(entry->hashval, ARCH_CONVERT) >= hashval)) {
1747                 entry--;
1748                 probe--;
1749         }
1750         while ((probe < INT_GET(leaf->hdr.count, ARCH_CONVERT)) && (INT_GET(entry->hashval, ARCH_CONVERT) < hashval)) {
1751                 entry++;
1752                 probe++;
1753         }
1754         if ((probe == INT_GET(leaf->hdr.count, ARCH_CONVERT)) || (INT_GET(entry->hashval, ARCH_CONVERT) != hashval)) {
1755                 *index = probe;
1756                 ASSERT(args->oknoent);
1757                 return(XFS_ERROR(ENOENT));
1758         }
1759
1760         /*
1761          * Duplicate keys may be present, so search all of them for a match.
1762          */
1763         while ((probe < INT_GET(leaf->hdr.count, ARCH_CONVERT)) && (INT_GET(entry->hashval, ARCH_CONVERT) == hashval)) {
1764                 namest = XFS_DIR_LEAF_NAMESTRUCT(leaf, INT_GET(entry->nameidx, ARCH_CONVERT));
1765                 if (entry->namelen == args->namelen &&
1766                     namest->name[0] == args->name[0] &&
1767                     memcmp(args->name, namest->name, args->namelen) == 0) {
1768                         XFS_DIR_SF_GET_DIRINO(&namest->inumber, &args->inumber);
1769                         *index = probe;
1770                         return(XFS_ERROR(EEXIST));
1771                 }
1772                 entry++;
1773                 probe++;
1774         }
1775         *index = probe;
1776         ASSERT(probe == INT_GET(leaf->hdr.count, ARCH_CONVERT) || args->oknoent);
1777         return(XFS_ERROR(ENOENT));
1778 }
1779
1780 /*========================================================================
1781  * Utility routines.
1782  *========================================================================*/
1783
1784 /*
1785  * Move the indicated entries from one leaf to another.
1786  * NOTE: this routine modifies both source and destination leaves.
1787  */
1788 /* ARGSUSED */
1789 STATIC void
1790 xfs_dir_leaf_moveents(xfs_dir_leafblock_t *leaf_s, int start_s,
1791                       xfs_dir_leafblock_t *leaf_d, int start_d,
1792                       int count, xfs_mount_t *mp)
1793 {
1794         xfs_dir_leaf_hdr_t *hdr_s, *hdr_d;
1795         xfs_dir_leaf_entry_t *entry_s, *entry_d;
1796         int tmp, i;
1797
1798         /*
1799          * Check for nothing to do.
1800          */
1801         if (count == 0)
1802                 return;
1803
1804         /*
1805          * Set up environment.
1806          */
1807         ASSERT(INT_GET(leaf_s->hdr.info.magic, ARCH_CONVERT) == XFS_DIR_LEAF_MAGIC);
1808         ASSERT(INT_GET(leaf_d->hdr.info.magic, ARCH_CONVERT) == XFS_DIR_LEAF_MAGIC);
1809         hdr_s = &leaf_s->hdr;
1810         hdr_d = &leaf_d->hdr;
1811         ASSERT((INT_GET(hdr_s->count, ARCH_CONVERT) > 0) && (INT_GET(hdr_s->count, ARCH_CONVERT) < (XFS_LBSIZE(mp)/8)));
1812         ASSERT(INT_GET(hdr_s->firstused, ARCH_CONVERT) >=
1813                 ((INT_GET(hdr_s->count, ARCH_CONVERT)*sizeof(*entry_s))+sizeof(*hdr_s)));
1814         ASSERT(INT_GET(hdr_d->count, ARCH_CONVERT) < (XFS_LBSIZE(mp)/8));
1815         ASSERT(INT_GET(hdr_d->firstused, ARCH_CONVERT) >=
1816                 ((INT_GET(hdr_d->count, ARCH_CONVERT)*sizeof(*entry_d))+sizeof(*hdr_d)));
1817
1818         ASSERT(start_s < INT_GET(hdr_s->count, ARCH_CONVERT));
1819         ASSERT(start_d <= INT_GET(hdr_d->count, ARCH_CONVERT));
1820         ASSERT(count <= INT_GET(hdr_s->count, ARCH_CONVERT));
1821
1822         /*
1823          * Move the entries in the destination leaf up to make a hole?
1824          */
1825         if (start_d < INT_GET(hdr_d->count, ARCH_CONVERT)) {
1826                 tmp  = INT_GET(hdr_d->count, ARCH_CONVERT) - start_d;
1827                 tmp *= (uint)sizeof(xfs_dir_leaf_entry_t);
1828                 entry_s = &leaf_d->entries[start_d];
1829                 entry_d = &leaf_d->entries[start_d + count];
1830                 memcpy(entry_d, entry_s, tmp);
1831         }
1832
1833         /*
1834          * Copy all entry's in the same (sorted) order,
1835          * but allocate filenames packed and in sequence.
1836          */
1837         entry_s = &leaf_s->entries[start_s];
1838         entry_d = &leaf_d->entries[start_d];
1839         for (i = 0; i < count; entry_s++, entry_d++, i++) {
1840                 ASSERT(INT_GET(entry_s->nameidx, ARCH_CONVERT) >= INT_GET(hdr_s->firstused, ARCH_CONVERT));
1841                 tmp = XFS_DIR_LEAF_ENTSIZE_BYENTRY(entry_s);
1842                 INT_MOD(hdr_d->firstused, ARCH_CONVERT, -(tmp));
1843                 entry_d->hashval = entry_s->hashval; /* INT_: direct copy */
1844                 INT_COPY(entry_d->nameidx, hdr_d->firstused, ARCH_CONVERT);
1845                 entry_d->namelen = entry_s->namelen;
1846                 ASSERT(INT_GET(entry_d->nameidx, ARCH_CONVERT) + tmp <= XFS_LBSIZE(mp));
1847                 memcpy(XFS_DIR_LEAF_NAMESTRUCT(leaf_d, INT_GET(entry_d->nameidx, ARCH_CONVERT)),
1848                        XFS_DIR_LEAF_NAMESTRUCT(leaf_s, INT_GET(entry_s->nameidx, ARCH_CONVERT)), tmp);
1849                 ASSERT(INT_GET(entry_s->nameidx, ARCH_CONVERT) + tmp <= XFS_LBSIZE(mp));
1850                 memset((char *)XFS_DIR_LEAF_NAMESTRUCT(leaf_s, INT_GET(entry_s->nameidx, ARCH_CONVERT)),
1851                       0, tmp);
1852                 INT_MOD(hdr_s->namebytes, ARCH_CONVERT, -(entry_d->namelen));
1853                 INT_MOD(hdr_d->namebytes, ARCH_CONVERT, entry_d->namelen);
1854                 INT_MOD(hdr_s->count, ARCH_CONVERT, -1);
1855                 INT_MOD(hdr_d->count, ARCH_CONVERT, +1);
1856                 tmp  = INT_GET(hdr_d->count, ARCH_CONVERT) * (uint)sizeof(xfs_dir_leaf_entry_t)
1857                                 + (uint)sizeof(xfs_dir_leaf_hdr_t);
1858                 ASSERT(INT_GET(hdr_d->firstused, ARCH_CONVERT) >= tmp);
1859
1860         }
1861
1862         /*
1863          * Zero out the entries we just copied.
1864          */
1865         if (start_s == INT_GET(hdr_s->count, ARCH_CONVERT)) {
1866                 tmp = count * (uint)sizeof(xfs_dir_leaf_entry_t);
1867                 entry_s = &leaf_s->entries[start_s];
1868                 ASSERT((char *)entry_s + tmp <= (char *)leaf_s + XFS_LBSIZE(mp));
1869                 memset((char *)entry_s, 0, tmp);
1870         } else {
1871                 /*
1872                  * Move the remaining entries down to fill the hole,
1873                  * then zero the entries at the top.
1874                  */
1875                 tmp  = INT_GET(hdr_s->count, ARCH_CONVERT) - count;
1876                 tmp *= (uint)sizeof(xfs_dir_leaf_entry_t);
1877                 entry_s = &leaf_s->entries[start_s + count];
1878                 entry_d = &leaf_s->entries[start_s];
1879                 memcpy(entry_d, entry_s, tmp);
1880
1881                 tmp = count * (uint)sizeof(xfs_dir_leaf_entry_t);
1882                 entry_s = &leaf_s->entries[INT_GET(hdr_s->count, ARCH_CONVERT)];
1883                 ASSERT((char *)entry_s + tmp <= (char *)leaf_s + XFS_LBSIZE(mp));
1884                 memset((char *)entry_s, 0, tmp);
1885         }
1886
1887         /*
1888          * Fill in the freemap information
1889          */
1890         INT_SET(hdr_d->freemap[0].base, ARCH_CONVERT, (uint)sizeof(xfs_dir_leaf_hdr_t));
1891         INT_MOD(hdr_d->freemap[0].base, ARCH_CONVERT, INT_GET(hdr_d->count, ARCH_CONVERT) * (uint)sizeof(xfs_dir_leaf_entry_t));
1892         INT_SET(hdr_d->freemap[0].size, ARCH_CONVERT, INT_GET(hdr_d->firstused, ARCH_CONVERT) - INT_GET(hdr_d->freemap[0].base, ARCH_CONVERT));
1893         INT_SET(hdr_d->freemap[1].base, ARCH_CONVERT, (hdr_d->freemap[2].base = 0));
1894         INT_SET(hdr_d->freemap[1].size, ARCH_CONVERT, (hdr_d->freemap[2].size = 0));
1895         hdr_s->holes = 1;       /* leaf may not be compact */
1896 }
1897
1898 /*
1899  * Compare two leaf blocks "order".
1900  */
1901 int
1902 xfs_dir_leaf_order(xfs_dabuf_t *leaf1_bp, xfs_dabuf_t *leaf2_bp)
1903 {
1904         xfs_dir_leafblock_t *leaf1, *leaf2;
1905
1906         leaf1 = leaf1_bp->data;
1907         leaf2 = leaf2_bp->data;
1908         ASSERT((INT_GET(leaf1->hdr.info.magic, ARCH_CONVERT) == XFS_DIR_LEAF_MAGIC) &&
1909                (INT_GET(leaf2->hdr.info.magic, ARCH_CONVERT) == XFS_DIR_LEAF_MAGIC));
1910         if ((INT_GET(leaf1->hdr.count, ARCH_CONVERT) > 0) && (INT_GET(leaf2->hdr.count, ARCH_CONVERT) > 0) &&
1911             ((INT_GET(leaf2->entries[ 0 ].hashval, ARCH_CONVERT) <
1912               INT_GET(leaf1->entries[ 0 ].hashval, ARCH_CONVERT)) ||
1913              (INT_GET(leaf2->entries[ INT_GET(leaf2->hdr.count, ARCH_CONVERT)-1 ].hashval, ARCH_CONVERT) <
1914               INT_GET(leaf1->entries[ INT_GET(leaf1->hdr.count, ARCH_CONVERT)-1 ].hashval, ARCH_CONVERT)))) {
1915                 return(1);
1916         }
1917         return(0);
1918 }
1919
1920 /*
1921  * Pick up the last hashvalue from a leaf block.
1922  */
1923 xfs_dahash_t
1924 xfs_dir_leaf_lasthash(xfs_dabuf_t *bp, int *count)
1925 {
1926         xfs_dir_leafblock_t *leaf;
1927
1928         leaf = bp->data;
1929         ASSERT(INT_GET(leaf->hdr.info.magic, ARCH_CONVERT) == XFS_DIR_LEAF_MAGIC);
1930         if (count)
1931                 *count = INT_GET(leaf->hdr.count, ARCH_CONVERT);
1932         if (!leaf->hdr.count)
1933                 return(0);
1934         return(INT_GET(leaf->entries[ INT_GET(leaf->hdr.count, ARCH_CONVERT)-1 ].hashval, ARCH_CONVERT));
1935 }
1936
1937 /*
1938  * Copy out directory entries for getdents(), for leaf directories.
1939  */
1940 int
1941 xfs_dir_leaf_getdents_int(
1942         xfs_dabuf_t     *bp,
1943         xfs_inode_t     *dp,
1944         xfs_dablk_t     bno,
1945         uio_t           *uio,
1946         int             *eobp,
1947         xfs_dirent_t    *dbp,
1948         xfs_dir_put_t   put,
1949         xfs_daddr_t             nextda)
1950 {
1951         xfs_dir_leafblock_t     *leaf;
1952         xfs_dir_leaf_entry_t    *entry;
1953         xfs_dir_leaf_name_t     *namest;
1954         int                     entno, want_entno, i, nextentno;
1955         xfs_mount_t             *mp;
1956         xfs_dahash_t            cookhash;
1957         xfs_dahash_t            nexthash = 0;
1958 #if (BITS_PER_LONG == 32)
1959         xfs_dahash_t            lasthash = XFS_DA_MAXHASH;
1960 #endif
1961         xfs_dir_put_args_t      p;
1962
1963         mp = dp->i_mount;
1964         leaf = bp->data;
1965         if (INT_GET(leaf->hdr.info.magic, ARCH_CONVERT) != XFS_DIR_LEAF_MAGIC) {
1966                 *eobp = 1;
1967                 return(XFS_ERROR(ENOENT));      /* XXX wrong code */
1968         }
1969
1970         want_entno = XFS_DA_COOKIE_ENTRY(mp, uio->uio_offset);
1971
1972         cookhash = XFS_DA_COOKIE_HASH(mp, uio->uio_offset);
1973
1974         xfs_dir_trace_g_dul("leaf: start", dp, uio, leaf);
1975
1976         /*
1977          * Re-find our place.
1978          */
1979         for (i = entno = 0, entry = &leaf->entries[0];
1980                      i < INT_GET(leaf->hdr.count, ARCH_CONVERT);
1981                              entry++, i++) {
1982
1983                 namest = XFS_DIR_LEAF_NAMESTRUCT(leaf,
1984                                     INT_GET(entry->nameidx, ARCH_CONVERT));
1985
1986                 if (unlikely(
1987                     ((char *)namest < (char *)leaf) ||
1988                     ((char *)namest >= (char *)leaf + XFS_LBSIZE(mp)))) {
1989                         XFS_CORRUPTION_ERROR("xfs_dir_leaf_getdents_int(1)",
1990                                              XFS_ERRLEVEL_LOW, mp, leaf);
1991                         xfs_dir_trace_g_du("leaf: corrupted", dp, uio);
1992                         return XFS_ERROR(EFSCORRUPTED);
1993                 }
1994                 if (INT_GET(entry->hashval, ARCH_CONVERT) >= cookhash) {
1995                         if (   entno < want_entno
1996                             && INT_GET(entry->hashval, ARCH_CONVERT)
1997                                                         == cookhash) {
1998                                 /*
1999                                  * Trying to get to a particular offset in a
2000                                  * run of equal-hashval entries.
2001                                  */
2002                                 entno++;
2003                         } else if (   want_entno > 0
2004                                    && entno == want_entno
2005                                    && INT_GET(entry->hashval, ARCH_CONVERT)
2006                                                         == cookhash) {
2007                                 break;
2008                         } else {
2009                                 entno = 0;
2010                                 break;
2011                         }
2012                 }
2013         }
2014
2015         if (i == INT_GET(leaf->hdr.count, ARCH_CONVERT)) {
2016                 xfs_dir_trace_g_du("leaf: hash not found", dp, uio);
2017                 if (!INT_GET(leaf->hdr.info.forw, ARCH_CONVERT))
2018                         uio->uio_offset =
2019                                 XFS_DA_MAKE_COOKIE(mp, 0, 0, XFS_DA_MAXHASH);
2020                 /*
2021                  * Don't set uio_offset if there's another block:
2022                  * the node code will be setting uio_offset anyway.
2023                  */
2024                 *eobp = 0;
2025                 return(0);
2026         }
2027         xfs_dir_trace_g_due("leaf: hash found", dp, uio, entry);
2028
2029         p.dbp = dbp;
2030         p.put = put;
2031         p.uio = uio;
2032
2033         /*
2034          * We're synchronized, start copying entries out to the user.
2035          */
2036         for (; entno >= 0 && i < INT_GET(leaf->hdr.count, ARCH_CONVERT);
2037                              entry++, i++, (entno = nextentno)) {
2038                 int lastresid=0, retval;
2039                 xfs_dircook_t lastoffset;
2040                 xfs_dahash_t thishash;
2041
2042                 /*
2043                  * Check for a damaged directory leaf block and pick up
2044                  * the inode number from this entry.
2045                  */
2046                 namest = XFS_DIR_LEAF_NAMESTRUCT(leaf,
2047                                     INT_GET(entry->nameidx, ARCH_CONVERT));
2048
2049                 if (unlikely(
2050                     ((char *)namest < (char *)leaf) ||
2051                     ((char *)namest >= (char *)leaf + XFS_LBSIZE(mp)))) {
2052                         XFS_CORRUPTION_ERROR("xfs_dir_leaf_getdents_int(2)",
2053                                              XFS_ERRLEVEL_LOW, mp, leaf);
2054                         xfs_dir_trace_g_du("leaf: corrupted", dp, uio);
2055                         return XFS_ERROR(EFSCORRUPTED);
2056                 }
2057
2058                 xfs_dir_trace_g_duc("leaf: middle cookie  ",
2059                                                    dp, uio, p.cook.o);
2060
2061                 if (i < (INT_GET(leaf->hdr.count, ARCH_CONVERT) - 1)) {
2062                         nexthash = INT_GET(entry[1].hashval, ARCH_CONVERT);
2063
2064                         if (nexthash == INT_GET(entry->hashval, ARCH_CONVERT))
2065                                 nextentno = entno + 1;
2066                         else
2067                                 nextentno = 0;
2068                         XFS_PUT_COOKIE(p.cook, mp, bno, nextentno, nexthash);
2069                         xfs_dir_trace_g_duc("leaf: middle cookie  ",
2070                                                    dp, uio, p.cook.o);
2071
2072                 } else if ((thishash = INT_GET(leaf->hdr.info.forw,
2073                                                         ARCH_CONVERT))) {
2074                         xfs_dabuf_t *bp2;
2075                         xfs_dir_leafblock_t *leaf2;
2076
2077                         ASSERT(nextda != -1);
2078
2079                         retval = xfs_da_read_buf(dp->i_transp, dp, thishash,
2080                                                  nextda, &bp2, XFS_DATA_FORK);
2081                         if (retval)
2082                                 return(retval);
2083
2084                         ASSERT(bp2 != NULL);
2085
2086                         leaf2 = bp2->data;
2087
2088                         if (unlikely(
2089                                (INT_GET(leaf2->hdr.info.magic, ARCH_CONVERT)
2090                                                 != XFS_DIR_LEAF_MAGIC)
2091                             || (INT_GET(leaf2->hdr.info.back, ARCH_CONVERT)
2092                                                 != bno))) {     /* GROT */
2093                                 XFS_CORRUPTION_ERROR("xfs_dir_leaf_getdents_int(3)",
2094                                                      XFS_ERRLEVEL_LOW, mp,
2095                                                      leaf2);
2096                                 xfs_da_brelse(dp->i_transp, bp2);
2097
2098                                 return(XFS_ERROR(EFSCORRUPTED));
2099                         }
2100
2101                         nexthash = INT_GET(leaf2->entries[0].hashval,
2102                                                                 ARCH_CONVERT);
2103                         nextentno = -1;
2104                         XFS_PUT_COOKIE(p.cook, mp, thishash, 0, nexthash);
2105                         xfs_da_brelse(dp->i_transp, bp2);
2106                         xfs_dir_trace_g_duc("leaf: next blk cookie",
2107                                                    dp, uio, p.cook.o);
2108                 } else {
2109                         nextentno = -1;
2110                         XFS_PUT_COOKIE(p.cook, mp, 0, 0, XFS_DA_MAXHASH);
2111                 }
2112
2113                 /*
2114                  * Save off the cookie so we can fall back should the
2115                  * 'put' into the outgoing buffer fails.  To handle a run
2116                  * of equal-hashvals, the off_t structure on 64bit
2117                  * builds has entno built into the cookie to ID the
2118                  * entry.  On 32bit builds, we only have space for the
2119                  * hashval so we can't ID specific entries within a group
2120                  * of same hashval entries.   For this, lastoffset is set
2121                  * to the first in the run of equal hashvals so we don't
2122                  * include any entries unless we can include all entries
2123                  * that share the same hashval.  Hopefully the buffer
2124                  * provided is big enough to handle it (see pv763517).
2125                  */
2126 #if (BITS_PER_LONG == 32)
2127                 if ((thishash = INT_GET(entry->hashval, ARCH_CONVERT))
2128                                                                 != lasthash) {
2129                         XFS_PUT_COOKIE(lastoffset, mp, bno, entno, thishash);
2130                         lastresid = uio->uio_resid;
2131                         lasthash = thishash;
2132                 } else {
2133                         xfs_dir_trace_g_duc("leaf: DUP COOKIES, skipped",
2134                                                    dp, uio, p.cook.o);
2135                 }
2136 #else
2137                 thishash = INT_GET(entry->hashval, ARCH_CONVERT);
2138                 XFS_PUT_COOKIE(lastoffset, mp, bno, entno, thishash);
2139                 lastresid = uio->uio_resid;
2140 #endif /* BITS_PER_LONG == 32 */
2141
2142                 /*
2143                  * Put the current entry into the outgoing buffer.  If we fail
2144                  * then restore the UIO to the first entry in the current
2145                  * run of equal-hashval entries (probably one 1 entry long).
2146                  */
2147                 p.ino = XFS_GET_DIR_INO8(namest->inumber);
2148 #if XFS_BIG_INUMS
2149                 p.ino += mp->m_inoadd;
2150 #endif
2151                 p.name = (char *)namest->name;
2152                 p.namelen = entry->namelen;
2153
2154                 retval = p.put(&p);
2155
2156                 if (!p.done) {
2157                         uio->uio_offset = lastoffset.o;
2158                         uio->uio_resid = lastresid;
2159
2160                         *eobp = 1;
2161
2162                         xfs_dir_trace_g_du("leaf: E-O-B", dp, uio);
2163
2164                         return(retval);
2165                 }
2166         }
2167
2168         uio->uio_offset = p.cook.o;
2169
2170         *eobp = 0;
2171
2172         xfs_dir_trace_g_du("leaf: E-O-F", dp, uio);
2173
2174         return(0);
2175 }
2176
2177 /*
2178  * Format a dirent64 structure and copy it out the the user's buffer.
2179  */
2180 int
2181 xfs_dir_put_dirent64_direct(xfs_dir_put_args_t *pa)
2182 {
2183         iovec_t *iovp;
2184         int reclen, namelen;
2185         xfs_dirent_t *idbp;
2186         uio_t *uio;
2187
2188         namelen = pa->namelen;
2189         reclen = DIRENTSIZE(namelen);
2190         uio = pa->uio;
2191         if (reclen > uio->uio_resid) {
2192                 pa->done = 0;
2193                 return 0;
2194         }
2195         iovp = uio->uio_iov;
2196         idbp = (xfs_dirent_t *)iovp->iov_base;
2197         iovp->iov_base = (char *)idbp + reclen;
2198         iovp->iov_len -= reclen;
2199         uio->uio_resid -= reclen;
2200         idbp->d_reclen = reclen;
2201         idbp->d_ino = pa->ino;
2202         idbp->d_off = pa->cook.o;
2203         idbp->d_name[namelen] = '\0';
2204         pa->done = 1;
2205         memcpy(idbp->d_name, pa->name, namelen);
2206         return 0;
2207 }
2208
2209 /*
2210  * Format a dirent64 structure and copy it out the the user's buffer.
2211  */
2212 int
2213 xfs_dir_put_dirent64_uio(xfs_dir_put_args_t *pa)
2214 {
2215         int             retval, reclen, namelen;
2216         xfs_dirent_t    *idbp;
2217         uio_t           *uio;
2218
2219         namelen = pa->namelen;
2220         reclen = DIRENTSIZE(namelen);
2221         uio = pa->uio;
2222         if (reclen > uio->uio_resid) {
2223                 pa->done = 0;
2224                 return 0;
2225         }
2226         idbp = pa->dbp;
2227         idbp->d_reclen = reclen;
2228         idbp->d_ino = pa->ino;
2229         idbp->d_off = pa->cook.o;
2230         idbp->d_name[namelen] = '\0';
2231         memcpy(idbp->d_name, pa->name, namelen);
2232         retval = uio_read((caddr_t)idbp, reclen, uio);
2233         pa->done = (retval == 0);
2234         return retval;
2235 }