sys/fs/filecorefs/filecore_lookup.c

   1 /*      $NetBSD: filecore_lookup.c,v 1.11 2009/03/14 21:04:23 dsl Exp $ */
   2
   3 /*-
   4  * Copyright (c) 1989, 1993, 1994 The Regents of the University of California.
   5  * All rights reserved.
   6  *
   7  * Redistribution and use in source and binary forms, with or without
   8  * modification, are permitted provided that the following conditions
   9  * are met:
  10  * 1. Redistributions of source code must retain the above copyright
  11  *    notice, this list of conditions and the following disclaimer.
  12  * 2. Redistributions in binary form must reproduce the above copyright
  13  *    notice, this list of conditions and the following disclaimer in the
  14  *    documentation and/or other materials provided with the distribution.
  15  * 3. Neither the name of the University nor the names of its contributors
  16  *    may be used to endorse or promote products derived from this software
  17  *    without specific prior written permission.
  18  *
  19  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  20  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  21  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  22  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  23  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  24  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  25  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  26  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  27  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  28  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  29  * SUCH DAMAGE.
  30  *
  31  *      filecore_lookup.c       1.1     1998/6/26
  32  */
  33
  34 /*-
  35  * Copyright (c) 1998 Andrew McMurry
  36  *
  37  * Redistribution and use in source and binary forms, with or without
  38  * modification, are permitted provided that the following conditions
  39  * are met:
  40  * 1. Redistributions of source code must retain the above copyright
  41  *    notice, this list of conditions and the following disclaimer.
  42  * 2. Redistributions in binary form must reproduce the above copyright
  43  *    notice, this list of conditions and the following disclaimer in the
  44  *    documentation and/or other materials provided with the distribution.
  45  * 3. All advertising materials mentioning features or use of this software
  46  *    must display the following acknowledgement:
  47  *      This product includes software developed by the University of
  48  *      California, Berkeley and its contributors.
  49  * 4. Neither the name of the University nor the names of its contributors
  50  *    may be used to endorse or promote products derived from this software
  51  *    without specific prior written permission.
  52  *
  53  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  54  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  55  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  56  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  57  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  58  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  59  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  60  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  61  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  62  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  63  * SUCH DAMAGE.
  64  *
  65  *      filecore_lookup.c       1.1     1998/6/26
  66  */
  67
  68 #include <sys/cdefs.h>
  69 __KERNEL_RCSID(0, "$NetBSD: filecore_lookup.c,v 1.11 2009/03/14 21:04:23 dsl Exp $");
  70
  71 #include <sys/param.h>
  72 #include <sys/namei.h>
  73 #include <sys/buf.h>
  74 #include <sys/file.h>
  75 #include <sys/vnode.h>
  76 #include <sys/mount.h>
  77 #include <sys/systm.h>
  78
  79 #include <fs/filecorefs/filecore.h>
  80 #include <fs/filecorefs/filecore_extern.h>
  81 #include <fs/filecorefs/filecore_node.h>
  82
  83 struct  nchstats filecore_nchstats;
  84
  85 /*
  86  * Convert a component of a pathname into a pointer to a locked inode.
  87  * This is a very central and rather complicated routine.
  88  * If the file system is not maintained in a strict tree hierarchy,
  89  * this can result in a deadlock situation (see comments in code below).
  90  *
  91  * The flag argument is LOOKUP, CREATE, RENAME, or DELETE depending on
  92  * whether the name is to be looked up, created, renamed, or deleted.
  93  * When CREATE, RENAME, or DELETE is specified, information usable in
  94  * creating, renaming, or deleting a directory entry may be calculated.
  95  * If flag has LOCKPARENT or'ed into it and the target of the pathname
  96  * exists, lookup returns both the target and its parent directory locked.
  97  * When creating or renaming and LOCKPARENT is specified, the target may
  98  * not be ".".  When deleting and LOCKPARENT is specified, the target may
  99  * be "."., but the caller must check to ensure it does an vrele and iput
 100  * instead of two iputs.
 101  *
 102  * Overall outline of ufs_lookup:
 103  *
 104  *      check accessibility of directory
 105  *      look for name in cache, if found, then if at end of path
 106  *        and deleting or creating, drop it, else return name
 107  *      search for name in directory, to found or notfound
 108  * notfound:
 109  *      if creating, return locked directory, leaving info on available slots
 110  *      else return error
 111  * found:
 112  *      if at end of path and deleting, return information to allow delete
 113  *      if at end of path and rewriting (RENAME and LOCKPARENT), lock target
 114  *        inode and return info to allow rewrite
 115  *      if not at end, add name to cache; if at end and neither creating
 116  *        nor deleting, add name to cache
 117  *
 118  * NOTE: (LOOKUP | LOCKPARENT) currently returns the parent inode unlocked.
 119  */
 120 int
 121 filecore_lookup(void *v)
 122 {
 123         struct vop_lookup_args /* {
 124                 struct vnode *a_dvp;
 125                 struct vnode **a_vpp;
 126                 struct componentname *a_cnp;
 127         } */ *ap = v;
 128         struct vnode *vdp;              /* vnode for directory being searched */
 129         struct filecore_node *dp;       /* inode for directory being searched */
 130         struct filecore_mnt *fcmp;      /* file system that directory is in */
 131         struct buf *bp;                 /* a buffer of directory entries */
 132         struct filecore_direntry *de;
 133         int numdirpasses;               /* strategy for directory search */
 134         struct vnode *pdp;              /* saved dp during symlink work */
 135         struct vnode *tdp;              /* returned by filecore_vget_internal */
 136         int error;
 137         u_short namelen;
 138         int res;
 139         const char *name;
 140         struct vnode **vpp = ap->a_vpp;
 141         struct componentname *cnp = ap->a_cnp;
 142         kauth_cred_t cred = cnp->cn_cred;
 143         int flags;
 144         int nameiop = cnp->cn_nameiop;
 145         int i, endsearch;
 146
 147         flags = cnp->cn_flags;
 148
 149         bp = NULL;
 150         *vpp = NULL;
 151         vdp = ap->a_dvp;
 152         dp = VTOI(vdp);
 153         fcmp = dp->i_mnt;
 154
 155         /*
 156          * Check accessiblity of directory.
 157          */
 158         if ((error = VOP_ACCESS(vdp, VEXEC, cred)) != 0)
 159                 return (error);
 160
 161         if ((flags & ISLASTCN) && (vdp->v_mount->mnt_flag & MNT_RDONLY) &&
 162             (cnp->cn_nameiop == DELETE || cnp->cn_nameiop == RENAME))
 163                 return (EROFS);
 164
 165         /*
 166          * We now have a segment name to search for, and a directory to search.
 167          *
 168          * Before tediously performing a linear scan of the directory,
 169          * check the name cache to see if the directory/name pair
 170          * we are looking for is known already.
 171          */
 172         if ((error = cache_lookup(vdp, vpp, cnp)) >= 0)
 173                 return (error);
 174
 175         name = cnp->cn_nameptr;
 176         namelen = cnp->cn_namelen;
 177
 178         /*
 179          * If there is cached information on a previous search of
 180          * this directory, pick up where we last left off.
 181          * We cache only lookups as these are the most common
 182          * and have the greatest payoff. Caching CREATE has little
 183          * benefit as it usually must search the entire directory
 184          * to determine that the entry does not exist. Caching the
 185          * location of the last DELETE or RENAME has not reduced
 186          * profiling time and hence has been removed in the interest
 187          * of simplicity.
 188          */
 189         if (nameiop != LOOKUP || dp->i_diroff == 0 ||
 190             dp->i_diroff >= FILECORE_MAXDIRENTS) {
 191                 i = 0;
 192                 numdirpasses = 1;
 193         } else {
 194                 i = dp->i_diroff;
 195                 numdirpasses = 2;
 196                 filecore_nchstats.ncs_2passes++;
 197         }
 198         endsearch = FILECORE_MAXDIRENTS;
 199
 200         if ((flags & ISDOTDOT) || (name[0] == '.' && namelen == 1))
 201                 goto found;
 202
 203         error = filecore_dbread(dp, &bp);
 204         if (error) {
 205                 brelse(bp, 0);
 206                 return error;
 207         }
 208
 209         de = fcdirentry(bp->b_data, i);
 210
 211 searchloop:
 212         while (de->name[0] != 0 && i < endsearch) {
 213                 /*
 214                  * Check for a name match.
 215                  */
 216                 res = filecore_fncmp(de->name, name, namelen);
 217
 218                 if (res == 0)
 219                         goto found;
 220                 if (res < 0)
 221                         goto notfound;
 222
 223                 i++;
 224                 de++;
 225         }
 226
 227 notfound:
 228         /*
 229          * If we started in the middle of the directory and failed
 230          * to find our target, we must check the beginning as well.
 231          */
 232         if (numdirpasses == 2) {
 233                 numdirpasses--;
 234                 i = 0;
 235                 de = fcdirentry(bp->b_data, i);
 236                 endsearch = dp->i_diroff;
 237                 goto searchloop;
 238         }
 239         if (bp != NULL) {
 240 #ifdef FILECORE_DEBUG_BR
 241                         printf("brelse(%p) lo1\n", bp);
 242 #endif
 243                 brelse(bp, 0);
 244         }
 245
 246         /*
 247          * Insert name into cache (as non-existent) if appropriate.
 248          */
 249         if (cnp->cn_flags & MAKEENTRY)
 250                 cache_enter(vdp, *vpp, cnp);
 251         if (nameiop == CREATE || nameiop == RENAME)
 252                 return (EROFS);
 253         return (ENOENT);
 254
 255 found:
 256         if (numdirpasses == 2)
 257                 filecore_nchstats.ncs_pass2++;
 258
 259         /*
 260          * Found component in pathname.
 261          * If the final component of path name, save information
 262          * in the cache as to where the entry was found.
 263          */
 264         if ((flags & ISLASTCN) && nameiop == LOOKUP)
 265                 dp->i_diroff = i;
 266
 267         /*
 268          * Step through the translation in the name.  We do not `iput' the
 269          * directory because we may need it again if a symbolic link
 270          * is relative to the current directory.  Instead we save it
 271          * unlocked as "pdp".  We must get the target inode before unlocking
 272          * the directory to insure that the inode will not be removed
 273          * before we get it.  We prevent deadlock by always fetching
 274          * inodes from the root, moving down the directory tree. Thus
 275          * when following backward pointers ".." we must unlock the
 276          * parent directory before getting the requested directory.
 277          * There is a potential race condition here if both the current
 278          * and parent directories are removed before the `iget' for the
 279          * inode associated with ".." returns.  We hope that this occurs
 280          * infrequently since we cannot avoid this race condition without
 281          * implementing a sophisticated deadlock detection algorithm.
 282          * Note also that this simple deadlock detection scheme will not
 283          * work if the file system has any hard links other than ".."
 284          * that point backwards in the directory structure.
 285          */
 286         pdp = vdp;
 287
 288         /*
 289          * If ino is different from dp->i_ino,
 290          * it's a relocated directory.
 291          */
 292         if (flags & ISDOTDOT) {
 293                 ino_t pin = filecore_getparent(dp);
 294
 295                 VOP_UNLOCK(pdp, 0);     /* race to get the inode */
 296                 error = VFS_VGET(vdp->v_mount, pin, &tdp);
 297                 vn_lock(pdp, LK_EXCLUSIVE | LK_RETRY);
 298                 if (error) {
 299                         return error;
 300                 }
 301                 *vpp = tdp;
 302         } else if (name[0] == '.' && namelen == 1) {
 303                 vref(vdp);      /* we want ourself, ie "." */
 304                 *vpp = vdp;
 305         } else {
 306 #ifdef FILECORE_DEBUG_BR
 307                         printf("brelse(%p) lo4\n", bp);
 308 #endif
 309                 brelse(bp, 0);
 310                 error = VFS_VGET(vdp->v_mount, dp->i_dirent.addr |
 311                     (i << FILECORE_INO_INDEX), &tdp);
 312                 if (error)
 313                         return (error);
 314                 *vpp = tdp;
 315         }
 316
 317         /*
 318          * Insert name into cache if appropriate.
 319          */
 320         if (cnp->cn_flags & MAKEENTRY)
 321                 cache_enter(vdp, *vpp, cnp);
 322         return (0);
 323 }