sys/ufs/ext2fs/ext2fs_lookup.c

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