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