git.oblomov.eu Git - linux-2.6/blob - fs/xfs/xfs_dir_leaf.c

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