sys/fs/ext2fs/ext2_lookup.c

   1 /*-
   2  *  modified for Lites 1.1
   3  *
   4  *  Aug 1995, Godmar Back (gback@cs.utah.edu)
   5  *  University of Utah, Department of Computer Science
   6  */
   7 /*-
   8  * Copyright (c) 1989, 1993
   9  *      The Regents of the University of California.  All rights reserved.
  10  * (c) UNIX System Laboratories, Inc.
  11  * All or some portions of this file are derived from material licensed
  12  * to the University of California by American Telephone and Telegraph
  13  * Co. or Unix System Laboratories, Inc. and are reproduced herein with
  14  * the permission of UNIX System Laboratories, Inc.
  15  *
  16  * Redistribution and use in source and binary forms, with or without
  17  * modification, are permitted provided that the following conditions
  18  * are met:
  19  * 1. Redistributions of source code must retain the above copyright
  20  *    notice, this list of conditions and the following disclaimer.
  21  * 2. Redistributions in binary form must reproduce the above copyright
  22  *    notice, this list of conditions and the following disclaimer in the
  23  *    documentation and/or other materials provided with the distribution.
  24  * 4. Neither the name of the University nor the names of its contributors
  25  *    may be used to endorse or promote products derived from this software
  26  *    without specific prior written permission.
  27  *
  28  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  29  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  30  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  31  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  32  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  33  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  34  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  35  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  36  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  37  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  38  * SUCH DAMAGE.
  39  *
  40  *      @(#)ufs_lookup.c        8.6 (Berkeley) 4/1/94
  41  * $FreeBSD$
  42  */
  43
  44 #include <sys/param.h>
  45 #include <sys/systm.h>
  46 #include <sys/namei.h>
  47 #include <sys/bio.h>
  48 #include <sys/buf.h>
  49 #include <sys/endian.h>
  50 #include <sys/mount.h>
  51 #include <sys/vnode.h>
  52 #include <sys/malloc.h>
  53 #include <sys/dirent.h>
  54 #include <sys/sysctl.h>
  55
  56 #include <ufs/ufs/dir.h>
  57
  58 #include <fs/ext2fs/inode.h>
  59 #include <fs/ext2fs/ext2_mount.h>
  60 #include <fs/ext2fs/ext2fs.h>
  61 #include <fs/ext2fs/ext2_dinode.h>
  62 #include <fs/ext2fs/ext2_dir.h>
  63 #include <fs/ext2fs/ext2_extern.h>
  64
  65 #ifdef INVARIANTS
  66 static int dirchk = 1;
  67 #else
  68 static int dirchk = 0;
  69 #endif
  70
  71 static SYSCTL_NODE(_vfs, OID_AUTO, e2fs, CTLFLAG_RD, 0, "EXT2FS filesystem");
  72 SYSCTL_INT(_vfs_e2fs, OID_AUTO, dircheck, CTLFLAG_RW, &dirchk, 0, "");
  73
  74 /*
  75    DIRBLKSIZE in ffs is DEV_BSIZE (in most cases 512)
  76    while it is the native blocksize in ext2fs - thus, a #define
  77    is no longer appropriate
  78 */
  79 #undef  DIRBLKSIZ
  80
  81 static u_char ext2_ft_to_dt[] = {
  82         DT_UNKNOWN,             /* EXT2_FT_UNKNOWN */
  83         DT_REG,                 /* EXT2_FT_REG_FILE */
  84         DT_DIR,                 /* EXT2_FT_DIR */
  85         DT_CHR,                 /* EXT2_FT_CHRDEV */
  86         DT_BLK,                 /* EXT2_FT_BLKDEV */
  87         DT_FIFO,                /* EXT2_FT_FIFO */
  88         DT_SOCK,                /* EXT2_FT_SOCK */
  89         DT_LNK,                 /* EXT2_FT_SYMLINK */
  90 };
  91 #define FTTODT(ft) \
  92     ((ft) < nitems(ext2_ft_to_dt) ? ext2_ft_to_dt[(ft)] : DT_UNKNOWN)
  93
  94 static u_char dt_to_ext2_ft[] = {
  95         EXT2_FT_UNKNOWN,        /* DT_UNKNOWN */
  96         EXT2_FT_FIFO,           /* DT_FIFO */
  97         EXT2_FT_CHRDEV,         /* DT_CHR */
  98         EXT2_FT_UNKNOWN,        /* unused */
  99         EXT2_FT_DIR,            /* DT_DIR */
 100         EXT2_FT_UNKNOWN,        /* unused */
 101         EXT2_FT_BLKDEV,         /* DT_BLK */
 102         EXT2_FT_UNKNOWN,        /* unused */
 103         EXT2_FT_REG_FILE,       /* DT_REG */
 104         EXT2_FT_UNKNOWN,        /* unused */
 105         EXT2_FT_SYMLINK,        /* DT_LNK */
 106         EXT2_FT_UNKNOWN,        /* unused */
 107         EXT2_FT_SOCK,           /* DT_SOCK */
 108         EXT2_FT_UNKNOWN,        /* unused */
 109         EXT2_FT_UNKNOWN,        /* DT_WHT */
 110 };
 111 #define DTTOFT(dt) \
 112     ((dt) < nitems(dt_to_ext2_ft) ? dt_to_ext2_ft[(dt)] : EXT2_FT_UNKNOWN)
 113
 114 static int      ext2_dirbadentry(struct vnode *dp, struct ext2fs_direct_2 *de,
 115                     int entryoffsetinblock);
 116 static int      ext2_lookup_ino(struct vnode *vdp, struct vnode **vpp,
 117                     struct componentname *cnp, ino_t *dd_ino);
 118
 119 /*
 120  * Vnode op for reading directories.
 121  */
 122 int
 123 ext2_readdir(struct vop_readdir_args *ap)
 124 {
 125         struct vnode *vp = ap->a_vp;
 126         struct uio *uio = ap->a_uio;
 127         struct buf *bp;
 128         struct inode *ip;
 129         struct ext2fs_direct_2 *dp, *edp;
 130         u_long *cookies;
 131         struct dirent dstdp;
 132         off_t offset, startoffset;
 133         size_t readcnt, skipcnt;
 134         ssize_t startresid;
 135         int ncookies;
 136         int DIRBLKSIZ = VTOI(ap->a_vp)->i_e2fs->e2fs_bsize;
 137         int error;
 138
 139         if (uio->uio_offset < 0)
 140                 return (EINVAL);
 141         ip = VTOI(vp);
 142         if (ap->a_ncookies != NULL) {
 143                 ncookies = uio->uio_resid;
 144                 if (uio->uio_offset >= ip->i_size)
 145                         ncookies = 0;
 146                 else if (ip->i_size - uio->uio_offset < ncookies)
 147                         ncookies = ip->i_size - uio->uio_offset;
 148                 ncookies = ncookies / (offsetof(struct ext2fs_direct_2,
 149                     e2d_namlen) + 4) + 1;
 150                 cookies = malloc(ncookies * sizeof(*cookies), M_TEMP, M_WAITOK);
 151                 *ap->a_ncookies = ncookies;
 152                 *ap->a_cookies = cookies;
 153         } else {
 154                 ncookies = 0;
 155                 cookies = NULL;
 156         }
 157         offset = startoffset = uio->uio_offset;
 158         startresid = uio->uio_resid;
 159         error = 0;
 160         while (error == 0 && uio->uio_resid > 0 &&
 161             uio->uio_offset < ip->i_size) {
 162                 error = ext2_blkatoff(vp, uio->uio_offset, NULL, &bp);
 163                 if (error)
 164                         break;
 165                 if (bp->b_offset + bp->b_bcount > ip->i_size)
 166                         readcnt = ip->i_size - bp->b_offset;
 167                 else
 168                         readcnt = bp->b_bcount;
 169                 skipcnt = (size_t)(uio->uio_offset - bp->b_offset) &
 170                     ~(size_t)(DIRBLKSIZ - 1);
 171                 offset = bp->b_offset + skipcnt;
 172                 dp = (struct ext2fs_direct_2 *)&bp->b_data[skipcnt];
 173                 edp = (struct ext2fs_direct_2 *)&bp->b_data[readcnt];
 174                 while (error == 0 && uio->uio_resid > 0 && dp < edp) {
 175                         if (dp->e2d_reclen <= offsetof(struct ext2fs_direct_2,
 176                             e2d_namlen) || (caddr_t)dp + dp->e2d_reclen >
 177                             (caddr_t)edp) {
 178                                 error = EIO;
 179                                 break;
 180                         }
 181                         /*-
 182                          * "New" ext2fs directory entries differ in 3 ways
 183                          * from ufs on-disk ones:
 184                          * - the name is not necessarily NUL-terminated.
 185                          * - the file type field always exists and always
 186                          *   follows the name length field.
 187                          * - the file type is encoded in a different way.
 188                          *
 189                          * "Old" ext2fs directory entries need no special
 190                          * conversions, since they are binary compatible
 191                          * with "new" entries having a file type of 0 (i.e.,
 192                          * EXT2_FT_UNKNOWN).  Splitting the old name length
 193                          * field didn't make a mess like it did in ufs,
 194                          * because ext2fs uses a machine-independent disk
 195                          * layout.
 196                          */
 197                         dstdp.d_namlen = dp->e2d_namlen;
 198                         dstdp.d_type = FTTODT(dp->e2d_type);
 199                         if (offsetof(struct ext2fs_direct_2, e2d_namlen) +
 200                             dstdp.d_namlen > dp->e2d_reclen) {
 201                                 error = EIO;
 202                                 break;
 203                         }
 204                         if (offset < startoffset || dp->e2d_ino == 0)
 205                                 goto nextentry;
 206                         dstdp.d_fileno = dp->e2d_ino;
 207                         dstdp.d_reclen = GENERIC_DIRSIZ(&dstdp);
 208                         bcopy(dp->e2d_name, dstdp.d_name, dstdp.d_namlen);
 209                         dstdp.d_name[dstdp.d_namlen] = '\0';
 210                         if (dstdp.d_reclen > uio->uio_resid) {
 211                                 if (uio->uio_resid == startresid)
 212                                         error = EINVAL;
 213                                 else
 214                                         error = EJUSTRETURN;
 215                                 break;
 216                         }
 217                         /* Advance dp. */
 218                         error = uiomove((caddr_t)&dstdp, dstdp.d_reclen, uio);
 219                         if (error)
 220                                 break;
 221                         if (cookies != NULL) {
 222                                 KASSERT(ncookies > 0,
 223                                     ("ext2_readdir: cookies buffer too small"));
 224                                 *cookies = offset + dp->e2d_reclen;
 225                                 cookies++;
 226                                 ncookies--;
 227                         }
 228 nextentry:
 229                         offset += dp->e2d_reclen;
 230                         dp = (struct ext2fs_direct_2 *)((caddr_t)dp +
 231                            dp->e2d_reclen);
 232                 }
 233                 bqrelse(bp);
 234                 uio->uio_offset = offset;
 235         }
 236         /* We need to correct uio_offset. */
 237         uio->uio_offset = offset;
 238         if (error == EJUSTRETURN)
 239                 error = 0;
 240         if (ap->a_ncookies != NULL) {
 241                 if (error == 0) {
 242                         ap->a_ncookies -= ncookies;
 243                 } else {
 244                         free(*ap->a_cookies, M_TEMP);
 245                         *ap->a_ncookies = 0;
 246                         *ap->a_cookies = NULL;
 247                 }
 248         }
 249         if (error == 0 && ap->a_eofflag)
 250                 *ap->a_eofflag = ip->i_size <= uio->uio_offset;
 251         return (error);
 252 }
 253
 254 /*
 255  * Convert a component of a pathname into a pointer to a locked inode.
 256  * This is a very central and rather complicated routine.
 257  * If the file system is not maintained in a strict tree hierarchy,
 258  * this can result in a deadlock situation (see comments in code below).
 259  *
 260  * The cnp->cn_nameiop argument is LOOKUP, CREATE, RENAME, or DELETE depending
 261  * on whether the name is to be looked up, created, renamed, or deleted.
 262  * When CREATE, RENAME, or DELETE is specified, information usable in
 263  * creating, renaming, or deleting a directory entry may be calculated.
 264  * If flag has LOCKPARENT or'ed into it and the target of the pathname
 265  * exists, lookup returns both the target and its parent directory locked.
 266  * When creating or renaming and LOCKPARENT is specified, the target may
 267  * not be ".".  When deleting and LOCKPARENT is specified, the target may
 268  * be "."., but the caller must check to ensure it does an vrele and vput
 269  * instead of two vputs.
 270  *
 271  * Overall outline of ext2_lookup:
 272  *
 273  *      search for name in directory, to found or notfound
 274  * notfound:
 275  *      if creating, return locked directory, leaving info on available slots
 276  *      else return error
 277  * found:
 278  *      if at end of path and deleting, return information to allow delete
 279  *      if at end of path and rewriting (RENAME and LOCKPARENT), lock target
 280  *        inode and return info to allow rewrite
 281  *      if not at end, add name to cache; if at end and neither creating
 282  *        nor deleting, add name to cache
 283  */
 284 int
 285 ext2_lookup(struct vop_cachedlookup_args *ap)
 286 {
 287
 288         return (ext2_lookup_ino(ap->a_dvp, ap->a_vpp, ap->a_cnp, NULL));
 289 }
 290
 291 static int
 292 ext2_lookup_ino(struct vnode *vdp, struct vnode **vpp, struct componentname *cnp,
 293     ino_t *dd_ino)
 294 {
 295         struct inode *dp;               /* inode for directory being searched */
 296         struct buf *bp;                 /* a buffer of directory entries */
 297         struct ext2fs_direct_2 *ep;     /* the current directory entry */
 298         int entryoffsetinblock;         /* offset of ep in bp's buffer */
 299         enum {NONE, COMPACT, FOUND} slotstatus;
 300         doff_t slotoffset;              /* offset of area with free space */
 301         doff_t i_diroff;                /* cached i_diroff value */
 302         doff_t i_offset;                /* cached i_offset value */
 303         int slotsize;                   /* size of area at slotoffset */
 304         int slotfreespace;              /* amount of space free in slot */
 305         int slotneeded;                 /* size of the entry we're seeking */
 306         int numdirpasses;               /* strategy for directory search */
 307         doff_t endsearch;               /* offset to end directory search */
 308         doff_t prevoff;                 /* prev entry dp->i_offset */
 309         struct vnode *pdp;              /* saved dp during symlink work */
 310         struct vnode *tdp;              /* returned by VFS_VGET */
 311         doff_t enduseful;               /* pointer past last used dir slot */
 312         u_long bmask;                   /* block offset mask */
 313         int namlen, error;
 314         struct ucred *cred = cnp->cn_cred;
 315         int flags = cnp->cn_flags;
 316         int nameiop = cnp->cn_nameiop;
 317         ino_t ino, ino1;
 318         int ltype;
 319
 320         int     DIRBLKSIZ = VTOI(vdp)->i_e2fs->e2fs_bsize;
 321
 322         if (vpp != NULL)
 323                 *vpp = NULL;
 324
 325         dp = VTOI(vdp);
 326         bmask = VFSTOEXT2(vdp->v_mount)->um_mountp->mnt_stat.f_iosize - 1;
 327 restart:
 328         bp = NULL;
 329         slotoffset = -1;
 330
 331         /*
 332          * We now have a segment name to search for, and a directory to search.
 333          */
 334
 335         /*
 336          * Suppress search for slots unless creating
 337          * file and at end of pathname, in which case
 338          * we watch for a place to put the new file in
 339          * case it doesn't already exist.
 340          */
 341         i_diroff = dp->i_diroff;
 342         slotstatus = FOUND;
 343         slotfreespace = slotsize = slotneeded = 0;
 344         if ((nameiop == CREATE || nameiop == RENAME) &&
 345             (flags & ISLASTCN)) {
 346                 slotstatus = NONE;
 347                 slotneeded = EXT2_DIR_REC_LEN(cnp->cn_namelen);
 348                 /* was
 349                 slotneeded = (sizeof(struct direct) - MAXNAMLEN +
 350                         cnp->cn_namelen + 3) &~ 3; */
 351         }
 352
 353         /*
 354          * If there is cached information on a previous search of
 355          * this directory, pick up where we last left off.
 356          * We cache only lookups as these are the most common
 357          * and have the greatest payoff. Caching CREATE has little
 358          * benefit as it usually must search the entire directory
 359          * to determine that the entry does not exist. Caching the
 360          * location of the last DELETE or RENAME has not reduced
 361          * profiling time and hence has been removed in the interest
 362          * of simplicity.
 363          */
 364         if (nameiop != LOOKUP || i_diroff == 0 ||
 365             i_diroff > dp->i_size) {
 366                 entryoffsetinblock = 0;
 367                 i_offset = 0;
 368                 numdirpasses = 1;
 369         } else {
 370                 i_offset = i_diroff;
 371                 if ((entryoffsetinblock = i_offset & bmask) &&
 372                     (error = ext2_blkatoff(vdp, (off_t)i_offset, NULL,
 373                     &bp)))
 374                         return (error);
 375                 numdirpasses = 2;
 376                 nchstats.ncs_2passes++;
 377         }
 378         prevoff = i_offset;
 379         endsearch = roundup2(dp->i_size, DIRBLKSIZ);
 380         enduseful = 0;
 381
 382 searchloop:
 383         while (i_offset < endsearch) {
 384                 /*
 385                  * If necessary, get the next directory block.
 386                  */
 387                 if ((i_offset & bmask) == 0) {
 388                         if (bp != NULL)
 389                                 brelse(bp);
 390                         if ((error =
 391                             ext2_blkatoff(vdp, (off_t)i_offset, NULL,
 392                             &bp)) != 0)
 393                                 return (error);
 394                         entryoffsetinblock = 0;
 395                 }
 396                 /*
 397                  * If still looking for a slot, and at a DIRBLKSIZE
 398                  * boundary, have to start looking for free space again.
 399                  */
 400                 if (slotstatus == NONE &&
 401                     (entryoffsetinblock & (DIRBLKSIZ - 1)) == 0) {
 402                         slotoffset = -1;
 403                         slotfreespace = 0;
 404                 }
 405                 /*
 406                  * Get pointer to next entry.
 407                  * Full validation checks are slow, so we only check
 408                  * enough to insure forward progress through the
 409                  * directory. Complete checks can be run by setting
 410                  * "vfs.e2fs.dirchk" to be true.
 411                  */
 412                 ep = (struct ext2fs_direct_2 *)
 413                         ((char *)bp->b_data + entryoffsetinblock);
 414                 if (ep->e2d_reclen == 0 ||
 415                     (dirchk && ext2_dirbadentry(vdp, ep, entryoffsetinblock))) {
 416                         int i;
 417                         ext2_dirbad(dp, i_offset, "mangled entry");
 418                         i = DIRBLKSIZ - (entryoffsetinblock & (DIRBLKSIZ - 1));
 419                         i_offset += i;
 420                         entryoffsetinblock += i;
 421                         continue;
 422                 }
 423
 424                 /*
 425                  * If an appropriate sized slot has not yet been found,
 426                  * check to see if one is available. Also accumulate space
 427                  * in the current block so that we can determine if
 428                  * compaction is viable.
 429                  */
 430                 if (slotstatus != FOUND) {
 431                         int size = ep->e2d_reclen;
 432
 433                         if (ep->e2d_ino != 0)
 434                                 size -= EXT2_DIR_REC_LEN(ep->e2d_namlen);
 435                         if (size > 0) {
 436                                 if (size >= slotneeded) {
 437                                         slotstatus = FOUND;
 438                                         slotoffset = i_offset;
 439                                         slotsize = ep->e2d_reclen;
 440                                 } else if (slotstatus == NONE) {
 441                                         slotfreespace += size;
 442                                         if (slotoffset == -1)
 443                                                 slotoffset = i_offset;
 444                                         if (slotfreespace >= slotneeded) {
 445                                                 slotstatus = COMPACT;
 446                                                 slotsize = i_offset +
 447                                                       ep->e2d_reclen - slotoffset;
 448                                         }
 449                                 }
 450                         }
 451                 }
 452
 453                 /*
 454                  * Check for a name match.
 455                  */
 456                 if (ep->e2d_ino) {
 457                         namlen = ep->e2d_namlen;
 458                         if (namlen == cnp->cn_namelen &&
 459                             !bcmp(cnp->cn_nameptr, ep->e2d_name,
 460                                 (unsigned)namlen)) {
 461                                 /*
 462                                  * Save directory entry's inode number and
 463                                  * reclen in ndp->ni_ufs area, and release
 464                                  * directory buffer.
 465                                  */
 466                                 ino = ep->e2d_ino;
 467                                 goto found;
 468                         }
 469                 }
 470                 prevoff = i_offset;
 471                 i_offset += ep->e2d_reclen;
 472                 entryoffsetinblock += ep->e2d_reclen;
 473                 if (ep->e2d_ino)
 474                         enduseful = i_offset;
 475         }
 476 /* notfound: */
 477         /*
 478          * If we started in the middle of the directory and failed
 479          * to find our target, we must check the beginning as well.
 480          */
 481         if (numdirpasses == 2) {
 482                 numdirpasses--;
 483                 i_offset = 0;
 484                 endsearch = i_diroff;
 485                 goto searchloop;
 486         }
 487         if (bp != NULL)
 488                 brelse(bp);
 489         /*
 490          * If creating, and at end of pathname and current
 491          * directory has not been removed, then can consider
 492          * allowing file to be created.
 493          */
 494         if ((nameiop == CREATE || nameiop == RENAME) &&
 495             (flags & ISLASTCN) && dp->i_nlink != 0) {
 496                 /*
 497                  * Access for write is interpreted as allowing
 498                  * creation of files in the directory.
 499                  */
 500                 if ((error = VOP_ACCESS(vdp, VWRITE, cred, cnp->cn_thread)) != 0)
 501                         return (error);
 502                 /*
 503                  * Return an indication of where the new directory
 504                  * entry should be put.  If we didn't find a slot,
 505                  * then set dp->i_count to 0 indicating
 506                  * that the new slot belongs at the end of the
 507                  * directory. If we found a slot, then the new entry
 508                  * can be put in the range from dp->i_offset to
 509                  * dp->i_offset + dp->i_count.
 510                  */
 511                 if (slotstatus == NONE) {
 512                         dp->i_offset = roundup2(dp->i_size, DIRBLKSIZ);
 513                         dp->i_count = 0;
 514                         enduseful = dp->i_offset;
 515                 } else {
 516                         dp->i_offset = slotoffset;
 517                         dp->i_count = slotsize;
 518                         if (enduseful < slotoffset + slotsize)
 519                                 enduseful = slotoffset + slotsize;
 520                 }
 521                 dp->i_endoff = roundup2(enduseful, DIRBLKSIZ);
 522                 /*
 523                  * We return with the directory locked, so that
 524                  * the parameters we set up above will still be
 525                  * valid if we actually decide to do a direnter().
 526                  * We return ni_vp == NULL to indicate that the entry
 527                  * does not currently exist; we leave a pointer to
 528                  * the (locked) directory inode in ndp->ni_dvp.
 529                  * The pathname buffer is saved so that the name
 530                  * can be obtained later.
 531                  *
 532                  * NB - if the directory is unlocked, then this
 533                  * information cannot be used.
 534                  */
 535                 cnp->cn_flags |= SAVENAME;
 536                 return (EJUSTRETURN);
 537         }
 538         /*
 539          * Insert name into cache (as non-existent) if appropriate.
 540          */
 541         if ((cnp->cn_flags & MAKEENTRY) != 0)
 542                 cache_enter(vdp, NULL, cnp);
 543         return (ENOENT);
 544
 545 found:
 546         if (dd_ino != NULL)
 547                 *dd_ino = ino;
 548         if (numdirpasses == 2)
 549                 nchstats.ncs_pass2++;
 550         /*
 551          * Check that directory length properly reflects presence
 552          * of this entry.
 553          */
 554         if (entryoffsetinblock + EXT2_DIR_REC_LEN(ep->e2d_namlen)
 555                 > dp->i_size) {
 556                 ext2_dirbad(dp, i_offset, "i_size too small");
 557                 dp->i_size = entryoffsetinblock+EXT2_DIR_REC_LEN(ep->e2d_namlen);
 558                 dp->i_flag |= IN_CHANGE | IN_UPDATE;
 559         }
 560         brelse(bp);
 561
 562         /*
 563          * Found component in pathname.
 564          * If the final component of path name, save information
 565          * in the cache as to where the entry was found.
 566          */
 567         if ((flags & ISLASTCN) && nameiop == LOOKUP)
 568                 dp->i_diroff = i_offset &~ (DIRBLKSIZ - 1);
 569         /*
 570          * If deleting, and at end of pathname, return
 571          * parameters which can be used to remove file.
 572          */
 573         if (nameiop == DELETE && (flags & ISLASTCN)) {
 574                 if (flags & LOCKPARENT)
 575                         ASSERT_VOP_ELOCKED(vdp, __FUNCTION__);
 576                 /*
 577                  * Write access to directory required to delete files.
 578                  */
 579                 if ((error = VOP_ACCESS(vdp, VWRITE, cred, cnp->cn_thread)) != 0)
 580                         return (error);
 581                 /*
 582                  * Return pointer to current entry in dp->i_offset,
 583                  * and distance past previous entry (if there
 584                  * is a previous entry in this block) in dp->i_count.
 585                  * Save directory inode pointer in ndp->ni_dvp for dirremove().
 586                  *
 587                  * Technically we shouldn't be setting these in the
 588                  * WANTPARENT case (first lookup in rename()), but any
 589                  * lookups that will result in directory changes will
 590                  * overwrite these.
 591                  */
 592                 dp->i_offset = i_offset;
 593                 if ((dp->i_offset & (DIRBLKSIZ - 1)) == 0)
 594                         dp->i_count = 0;
 595                 else
 596                         dp->i_count = dp->i_offset - prevoff;
 597                 if (dd_ino != NULL)
 598                         return (0);
 599                 if (dp->i_number == ino) {
 600                         VREF(vdp);
 601                         *vpp = vdp;
 602                         return (0);
 603                 }
 604                 if ((error = VFS_VGET(vdp->v_mount, ino, LK_EXCLUSIVE,
 605                     &tdp)) != 0)
 606                         return (error);
 607                 /*
 608                  * If directory is "sticky", then user must own
 609                  * the directory, or the file in it, else she
 610                  * may not delete it (unless she's root). This
 611                  * implements append-only directories.
 612                  */
 613                 if ((dp->i_mode & ISVTX) &&
 614                     cred->cr_uid != 0 &&
 615                     cred->cr_uid != dp->i_uid &&
 616                     VTOI(tdp)->i_uid != cred->cr_uid) {
 617                         vput(tdp);
 618                         return (EPERM);
 619                 }
 620                 *vpp = tdp;
 621                 return (0);
 622         }
 623
 624         /*
 625          * If rewriting (RENAME), return the inode and the
 626          * information required to rewrite the present directory
 627          * Must get inode of directory entry to verify it's a
 628          * regular file, or empty directory.
 629          */
 630         if (nameiop == RENAME && (flags & ISLASTCN)) {
 631                 if ((error = VOP_ACCESS(vdp, VWRITE, cred, cnp->cn_thread)) != 0)
 632                         return (error);
 633                 /*
 634                  * Careful about locking second inode.
 635                  * This can only occur if the target is ".".
 636                  */
 637                 dp->i_offset = i_offset;
 638                 if (dp->i_number == ino)
 639                         return (EISDIR);
 640                 if (dd_ino != NULL)
 641                         return (0);
 642                 if ((error = VFS_VGET(vdp->v_mount, ino, LK_EXCLUSIVE,
 643                     &tdp)) != 0)
 644                         return (error);
 645                 *vpp = tdp;
 646                 cnp->cn_flags |= SAVENAME;
 647                 return (0);
 648         }
 649         if (dd_ino != NULL)
 650                 return (0);
 651
 652         /*
 653          * Step through the translation in the name.  We do not `vput' the
 654          * directory because we may need it again if a symbolic link
 655          * is relative to the current directory.  Instead we save it
 656          * unlocked as "pdp".  We must get the target inode before unlocking
 657          * the directory to insure that the inode will not be removed
 658          * before we get it.  We prevent deadlock by always fetching
 659          * inodes from the root, moving down the directory tree. Thus
 660          * when following backward pointers ".." we must unlock the
 661          * parent directory before getting the requested directory.
 662          * There is a potential race condition here if both the current
 663          * and parent directories are removed before the VFS_VGET for the
 664          * inode associated with ".." returns.  We hope that this occurs
 665          * infrequently since we cannot avoid this race condition without
 666          * implementing a sophisticated deadlock detection algorithm.
 667          * Note also that this simple deadlock detection scheme will not
 668          * work if the file system has any hard links other than ".."
 669          * that point backwards in the directory structure.
 670          */
 671         pdp = vdp;
 672         if (flags & ISDOTDOT) {
 673                 error = vn_vget_ino(pdp, ino, cnp->cn_lkflags, &tdp);
 674                 if (pdp->v_iflag & VI_DOOMED) {
 675                         if (error == 0)
 676                                 vput(tdp);
 677                         error = ENOENT;
 678                 }
 679                 if (error)
 680                         return (error);
 681                 /*
 682                  * Recheck that ".." entry in the vdp directory points
 683                  * to the inode we looked up before vdp lock was
 684                  * dropped.
 685                  */
 686                 error = ext2_lookup_ino(pdp, NULL, cnp, &ino1);
 687                 if (error) {
 688                         vput(tdp);
 689                         return (error);
 690                 }
 691                 if (ino1 != ino) {
 692                         vput(tdp);
 693                         goto restart;
 694                 }
 695                 *vpp = tdp;
 696         } else if (dp->i_number == ino) {
 697                 VREF(vdp);      /* we want ourself, ie "." */
 698                 /*
 699                  * When we lookup "." we still can be asked to lock it
 700                  * differently.
 701                  */
 702                 ltype = cnp->cn_lkflags & LK_TYPE_MASK;
 703                 if (ltype != VOP_ISLOCKED(vdp)) {
 704                         if (ltype == LK_EXCLUSIVE)
 705                                 vn_lock(vdp, LK_UPGRADE | LK_RETRY);
 706                         else /* if (ltype == LK_SHARED) */
 707                                 vn_lock(vdp, LK_DOWNGRADE | LK_RETRY);
 708                 }
 709                 *vpp = vdp;
 710         } else {
 711                 if ((error = VFS_VGET(vdp->v_mount, ino, cnp->cn_lkflags,
 712                     &tdp)) != 0)
 713                         return (error);
 714                 *vpp = tdp;
 715         }
 716
 717         /*
 718          * Insert name into cache if appropriate.
 719          */
 720         if (cnp->cn_flags & MAKEENTRY)
 721                 cache_enter(vdp, *vpp, cnp);
 722         return (0);
 723 }
 724
 725 void
 726 ext2_dirbad(struct inode *ip, doff_t offset, char *how)
 727 {
 728         struct mount *mp;
 729
 730         mp = ITOV(ip)->v_mount;
 731         if ((mp->mnt_flag & MNT_RDONLY) == 0)
 732                 panic("ext2_dirbad: %s: bad dir ino %lu at offset %ld: %s\n",
 733                         mp->mnt_stat.f_mntonname, (u_long)ip->i_number,(long)offset, how);
 734         else
 735         (void)printf("%s: bad dir ino %lu at offset %ld: %s\n",
 736             mp->mnt_stat.f_mntonname, (u_long)ip->i_number, (long)offset, how);
 737
 738 }
 739
 740 /*
 741  * Do consistency checking on a directory entry:
 742  *      record length must be multiple of 4
 743  *      entry must fit in rest of its DIRBLKSIZ block
 744  *      record must be large enough to contain entry
 745  *      name is not longer than MAXNAMLEN
 746  *      name must be as long as advertised, and null terminated
 747  */
 748 /*
 749  *      changed so that it confirms to ext2_check_dir_entry
 750  */
 751 static int
 752 ext2_dirbadentry(struct vnode *dp, struct ext2fs_direct_2 *de,
 753     int entryoffsetinblock)
 754 {
 755         int     DIRBLKSIZ = VTOI(dp)->i_e2fs->e2fs_bsize;
 756
 757         char * error_msg = NULL;
 758
 759         if (de->e2d_reclen < EXT2_DIR_REC_LEN(1))
 760                 error_msg = "rec_len is smaller than minimal";
 761         else if (de->e2d_reclen % 4 != 0)
 762                 error_msg = "rec_len % 4 != 0";
 763         else if (de->e2d_reclen < EXT2_DIR_REC_LEN(de->e2d_namlen))
 764                 error_msg = "reclen is too small for name_len";
 765         else if (entryoffsetinblock + de->e2d_reclen > DIRBLKSIZ)
 766                 error_msg = "directory entry across blocks";
 767         /* else LATER
 768              if (de->inode > dir->i_sb->u.ext2_sb.s_es->s_inodes_count)
 769                 error_msg = "inode out of bounds";
 770         */
 771
 772         if (error_msg != NULL) {
 773                 printf("bad directory entry: %s\n", error_msg);
 774                 printf("offset=%d, inode=%lu, rec_len=%u, name_len=%u\n",
 775                         entryoffsetinblock, (unsigned long)de->e2d_ino,
 776                         de->e2d_reclen, de->e2d_namlen);
 777         }
 778         return error_msg == NULL ? 0 : 1;
 779 }
 780
 781 /*
 782  * Write a directory entry after a call to namei, using the parameters
 783  * that it left in nameidata.  The argument ip is the inode which the new
 784  * directory entry will refer to.  Dvp is a pointer to the directory to
 785  * be written, which was left locked by namei. Remaining parameters
 786  * (dp->i_offset, dp->i_count) indicate how the space for the new
 787  * entry is to be obtained.
 788  */
 789 int
 790 ext2_direnter(struct inode *ip, struct vnode *dvp, struct componentname *cnp)
 791 {
 792         struct ext2fs_direct_2 *ep, *nep;
 793         struct inode *dp;
 794         struct buf *bp;
 795         struct ext2fs_direct_2 newdir;
 796         struct iovec aiov;
 797         struct uio auio;
 798         u_int dsize;
 799         int error, loc, newentrysize, spacefree;
 800         char *dirbuf;
 801         int     DIRBLKSIZ = ip->i_e2fs->e2fs_bsize;
 802
 803
 804 #ifdef INVARIANTS
 805         if ((cnp->cn_flags & SAVENAME) == 0)
 806                 panic("ext2_direnter: missing name");
 807 #endif
 808         dp = VTOI(dvp);
 809         newdir.e2d_ino = ip->i_number;
 810         newdir.e2d_namlen = cnp->cn_namelen;
 811         if (EXT2_HAS_INCOMPAT_FEATURE(ip->i_e2fs,
 812             EXT2F_INCOMPAT_FTYPE))
 813                 newdir.e2d_type = DTTOFT(IFTODT(ip->i_mode));
 814         else
 815                 newdir.e2d_type = EXT2_FT_UNKNOWN;
 816         bcopy(cnp->cn_nameptr, newdir.e2d_name, (unsigned)cnp->cn_namelen + 1);
 817         newentrysize = EXT2_DIR_REC_LEN(newdir.e2d_namlen);
 818         if (dp->i_count == 0) {
 819                 /*
 820                  * If dp->i_count is 0, then namei could find no
 821                  * space in the directory. Here, dp->i_offset will
 822                  * be on a directory block boundary and we will write the
 823                  * new entry into a fresh block.
 824                  */
 825                 if (dp->i_offset & (DIRBLKSIZ - 1))
 826                         panic("ext2_direnter: newblk");
 827                 auio.uio_offset = dp->i_offset;
 828                 newdir.e2d_reclen = DIRBLKSIZ;
 829                 auio.uio_resid = newentrysize;
 830                 aiov.iov_len = newentrysize;
 831                 aiov.iov_base = (caddr_t)&newdir;
 832                 auio.uio_iov = &aiov;
 833                 auio.uio_iovcnt = 1;
 834                 auio.uio_rw = UIO_WRITE;
 835                 auio.uio_segflg = UIO_SYSSPACE;
 836                 auio.uio_td = (struct thread *)0;
 837                 error = VOP_WRITE(dvp, &auio, IO_SYNC, cnp->cn_cred);
 838                 if (DIRBLKSIZ >
 839                     VFSTOEXT2(dvp->v_mount)->um_mountp->mnt_stat.f_bsize)
 840                         /* XXX should grow with balloc() */
 841                         panic("ext2_direnter: frag size");
 842                 else if (!error) {
 843                         dp->i_size = roundup2(dp->i_size, DIRBLKSIZ);
 844                         dp->i_flag |= IN_CHANGE;
 845                 }
 846                 return (error);
 847         }
 848
 849         /*
 850          * If dp->i_count is non-zero, then namei found space
 851          * for the new entry in the range dp->i_offset to
 852          * dp->i_offset + dp->i_count in the directory.
 853          * To use this space, we may have to compact the entries located
 854          * there, by copying them together towards the beginning of the
 855          * block, leaving the free space in one usable chunk at the end.
 856          */
 857
 858         /*
 859          * Increase size of directory if entry eats into new space.
 860          * This should never push the size past a new multiple of
 861          * DIRBLKSIZE.
 862          *
 863          * N.B. - THIS IS AN ARTIFACT OF 4.2 AND SHOULD NEVER HAPPEN.
 864          */
 865         if (dp->i_offset + dp->i_count > dp->i_size)
 866                 dp->i_size = dp->i_offset + dp->i_count;
 867         /*
 868          * Get the block containing the space for the new directory entry.
 869          */
 870         if ((error = ext2_blkatoff(dvp, (off_t)dp->i_offset, &dirbuf,
 871             &bp)) != 0)
 872                 return (error);
 873         /*
 874          * Find space for the new entry. In the simple case, the entry at
 875          * offset base will have the space. If it does not, then namei
 876          * arranged that compacting the region dp->i_offset to
 877          * dp->i_offset + dp->i_count would yield the
 878          * space.
 879          */
 880         ep = (struct ext2fs_direct_2 *)dirbuf;
 881         dsize = EXT2_DIR_REC_LEN(ep->e2d_namlen);
 882         spacefree = ep->e2d_reclen - dsize;
 883         for (loc = ep->e2d_reclen; loc < dp->i_count; ) {
 884                 nep = (struct ext2fs_direct_2 *)(dirbuf + loc);
 885                 if (ep->e2d_ino) {
 886                         /* trim the existing slot */
 887                         ep->e2d_reclen = dsize;
 888                         ep = (struct ext2fs_direct_2 *)((char *)ep + dsize);
 889                 } else {
 890                         /* overwrite; nothing there; header is ours */
 891                         spacefree += dsize;
 892                 }
 893                 dsize = EXT2_DIR_REC_LEN(nep->e2d_namlen);
 894                 spacefree += nep->e2d_reclen - dsize;
 895                 loc += nep->e2d_reclen;
 896                 bcopy((caddr_t)nep, (caddr_t)ep, dsize);
 897         }
 898         /*
 899          * Update the pointer fields in the previous entry (if any),
 900          * copy in the new entry, and write out the block.
 901          */
 902         if (ep->e2d_ino == 0) {
 903                 if (spacefree + dsize < newentrysize)
 904                         panic("ext2_direnter: compact1");
 905                 newdir.e2d_reclen = spacefree + dsize;
 906         } else {
 907                 if (spacefree < newentrysize)
 908                         panic("ext2_direnter: compact2");
 909                 newdir.e2d_reclen = spacefree;
 910                 ep->e2d_reclen = dsize;
 911                 ep = (struct ext2fs_direct_2 *)((char *)ep + dsize);
 912         }
 913         bcopy((caddr_t)&newdir, (caddr_t)ep, (u_int)newentrysize);
 914         if (DOINGASYNC(dvp)) {
 915                 bdwrite(bp);
 916                 error = 0;
 917         } else {
 918                 error = bwrite(bp);
 919         }
 920         dp->i_flag |= IN_CHANGE | IN_UPDATE;
 921         if (!error && dp->i_endoff && dp->i_endoff < dp->i_size)
 922                 error = ext2_truncate(dvp, (off_t)dp->i_endoff, IO_SYNC,
 923                     cnp->cn_cred, cnp->cn_thread);
 924         return (error);
 925 }
 926
 927 /*
 928  * Remove a directory entry after a call to namei, using
 929  * the parameters which it left in nameidata. The entry
 930  * dp->i_offset contains the offset into the directory of the
 931  * entry to be eliminated.  The dp->i_count field contains the
 932  * size of the previous record in the directory.  If this
 933  * is 0, the first entry is being deleted, so we need only
 934  * zero the inode number to mark the entry as free.  If the
 935  * entry is not the first in the directory, we must reclaim
 936  * the space of the now empty record by adding the record size
 937  * to the size of the previous entry.
 938  */
 939 int
 940 ext2_dirremove(struct vnode *dvp, struct componentname *cnp)
 941 {
 942         struct inode *dp;
 943         struct ext2fs_direct_2 *ep, *rep;
 944         struct buf *bp;
 945         int error;
 946
 947         dp = VTOI(dvp);
 948         if (dp->i_count == 0) {
 949                 /*
 950                  * First entry in block: set d_ino to zero.
 951                  */
 952                 if ((error =
 953                     ext2_blkatoff(dvp, (off_t)dp->i_offset, (char **)&ep,
 954                     &bp)) != 0)
 955                         return (error);
 956                 ep->e2d_ino = 0;
 957                 error = bwrite(bp);
 958                 dp->i_flag |= IN_CHANGE | IN_UPDATE;
 959                 return (error);
 960         }
 961         /*
 962          * Collapse new free space into previous entry.
 963          */
 964         if ((error = ext2_blkatoff(dvp, (off_t)(dp->i_offset - dp->i_count),
 965             (char **)&ep, &bp)) != 0)
 966                 return (error);
 967
 968         /* Set 'rep' to the entry being removed. */
 969         if (dp->i_count == 0)
 970                 rep = ep;
 971         else
 972                 rep = (struct ext2fs_direct_2 *)((char *)ep + ep->e2d_reclen);
 973         ep->e2d_reclen += rep->e2d_reclen;
 974         if (DOINGASYNC(dvp) && dp->i_count != 0)
 975                 bdwrite(bp);
 976         else
 977                 error = bwrite(bp);
 978         dp->i_flag |= IN_CHANGE | IN_UPDATE;
 979         return (error);
 980 }
 981
 982 /*
 983  * Rewrite an existing directory entry to point at the inode
 984  * supplied.  The parameters describing the directory entry are
 985  * set up by a call to namei.
 986  */
 987 int
 988 ext2_dirrewrite(struct inode *dp, struct inode *ip, struct componentname *cnp)
 989 {
 990         struct buf *bp;
 991         struct ext2fs_direct_2 *ep;
 992         struct vnode *vdp = ITOV(dp);
 993         int error;
 994
 995         if ((error = ext2_blkatoff(vdp, (off_t)dp->i_offset, (char **)&ep,
 996             &bp)) != 0)
 997                 return (error);
 998         ep->e2d_ino = ip->i_number;
 999         if (EXT2_HAS_INCOMPAT_FEATURE(ip->i_e2fs,
1000             EXT2F_INCOMPAT_FTYPE))
1001                 ep->e2d_type = DTTOFT(IFTODT(ip->i_mode));
1002         else
1003                 ep->e2d_type = EXT2_FT_UNKNOWN;
1004         error = bwrite(bp);
1005         dp->i_flag |= IN_CHANGE | IN_UPDATE;
1006         return (error);
1007 }
1008
1009 /*
1010  * Check if a directory is empty or not.
1011  * Inode supplied must be locked.
1012  *
1013  * Using a struct dirtemplate here is not precisely
1014  * what we want, but better than using a struct direct.
1015  *
1016  * NB: does not handle corrupted directories.
1017  */
1018 int
1019 ext2_dirempty(struct inode *ip, ino_t parentino, struct ucred *cred)
1020 {
1021         off_t off;
1022         struct dirtemplate dbuf;
1023         struct ext2fs_direct_2 *dp = (struct ext2fs_direct_2 *)&dbuf;
1024         int error, namlen;
1025         ssize_t count;
1026 #define MINDIRSIZ (sizeof(struct dirtemplate) / 2)
1027
1028         for (off = 0; off < ip->i_size; off += dp->e2d_reclen) {
1029                 error = vn_rdwr(UIO_READ, ITOV(ip), (caddr_t)dp, MINDIRSIZ,
1030                     off, UIO_SYSSPACE, IO_NODELOCKED | IO_NOMACCHECK, cred,
1031                     NOCRED, &count, (struct thread *)0);
1032                 /*
1033                  * Since we read MINDIRSIZ, residual must
1034                  * be 0 unless we're at end of file.
1035                  */
1036                 if (error || count != 0)
1037                         return (0);
1038                 /* avoid infinite loops */
1039                 if (dp->e2d_reclen == 0)
1040                         return (0);
1041                 /* skip empty entries */
1042                 if (dp->e2d_ino == 0)
1043                         continue;
1044                 /* accept only "." and ".." */
1045                 namlen = dp->e2d_namlen;
1046                 if (namlen > 2)
1047                         return (0);
1048                 if (dp->e2d_name[0] != '.')
1049                         return (0);
1050                 /*
1051                  * At this point namlen must be 1 or 2.
1052                  * 1 implies ".", 2 implies ".." if second
1053                  * char is also "."
1054                  */
1055                 if (namlen == 1)
1056                         continue;
1057                 if (dp->e2d_name[1] == '.' && dp->e2d_ino == parentino)
1058                         continue;
1059                 return (0);
1060         }
1061         return (1);
1062 }
1063
1064 /*
1065  * Check if source directory is in the path of the target directory.
1066  * Target is supplied locked, source is unlocked.
1067  * The target is always vput before returning.
1068  */
1069 int
1070 ext2_checkpath(struct inode *source, struct inode *target, struct ucred *cred)
1071 {
1072         struct vnode *vp;
1073         int error, namlen;
1074         struct dirtemplate dirbuf;
1075
1076         vp = ITOV(target);
1077         if (target->i_number == source->i_number) {
1078                 error = EEXIST;
1079                 goto out;
1080         }
1081         if (target->i_number == EXT2_ROOTINO) {
1082                 error = 0;
1083                 goto out;
1084         }
1085
1086         for (;;) {
1087                 if (vp->v_type != VDIR) {
1088                         error = ENOTDIR;
1089                         break;
1090                 }
1091                 error = vn_rdwr(UIO_READ, vp, (caddr_t)&dirbuf,
1092                         sizeof(struct dirtemplate), (off_t)0, UIO_SYSSPACE,
1093                         IO_NODELOCKED | IO_NOMACCHECK, cred, NOCRED, NULL,
1094                         NULL);
1095                 if (error != 0)
1096                         break;
1097                 namlen = dirbuf.dotdot_type;    /* like ufs little-endian */
1098                 if (namlen != 2 ||
1099                     dirbuf.dotdot_name[0] != '.' ||
1100                     dirbuf.dotdot_name[1] != '.') {
1101                         error = ENOTDIR;
1102                         break;
1103                 }
1104                 if (dirbuf.dotdot_ino == source->i_number) {
1105                         error = EINVAL;
1106                         break;
1107                 }
1108                 if (dirbuf.dotdot_ino == EXT2_ROOTINO)
1109                         break;
1110                 vput(vp);
1111                 if ((error = VFS_VGET(vp->v_mount, dirbuf.dotdot_ino,
1112                     LK_EXCLUSIVE, &vp)) != 0) {
1113                         vp = NULL;
1114                         break;
1115                 }
1116         }
1117
1118 out:
1119         if (error == ENOTDIR)
1120                 printf("checkpath: .. not a directory\n");
1121         if (vp != NULL)
1122                 vput(vp);
1123         return (error);
1124 }