bsd/hfs/hfs_lookup.c

   1 /*
   2  * Copyright (c) 1999-2008 Apple Inc. All rights reserved.
   3  *
   4  * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
   5  *
   6  * This file contains Original Code and/or Modifications of Original Code
   7  * as defined in and that are subject to the Apple Public Source License
   8  * Version 2.0 (the 'License'). You may not use this file except in
   9  * compliance with the License. The rights granted to you under the License
  10  * may not be used to create, or enable the creation or redistribution of,
  11  * unlawful or unlicensed copies of an Apple operating system, or to
  12  * circumvent, violate, or enable the circumvention or violation of, any
  13  * terms of an Apple operating system software license agreement.
  14  *
  15  * Please obtain a copy of the License at
  16  * http://www.opensource.apple.com/apsl/ and read it before using this file.
  17  *
  18  * The Original Code and all software distributed under the License are
  19  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  20  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  21  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  22  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  23  * Please see the License for the specific language governing rights and
  24  * limitations under the License.
  25  *
  26  * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
  27  */
  28 /*
  29  * Copyright (c) 1989, 1993
  30  *      The Regents of the University of California.  All rights reserved.
  31  * (c) UNIX System Laboratories, Inc.
  32  * All or some portions of this file are derived from material licensed
  33  * to the University of California by American Telephone and Telegraph
  34  * Co. or Unix System Laboratories, Inc. and are reproduced herein with
  35  * the permission of UNIX System Laboratories, Inc.
  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  *      @(#)hfs_lookup.c        1.0
  66  *      derived from @(#)ufs_lookup.c   8.15 (Berkeley) 6/16/95
  67  *
  68  *      (c) 1998-1999   Apple Computer, Inc.     All Rights Reserved
  69  *      (c) 1990, 1992  NeXT Computer, Inc.     All Rights Reserved
  70  *
  71  *
  72  *      hfs_lookup.c -- code to handle directory traversal on HFS/HFS+ volume
  73  */
  74
  75 #include <sys/param.h>
  76 #include <sys/file.h>
  77 #include <sys/mount.h>
  78 #include <sys/vnode.h>
  79 #include <sys/malloc.h>
  80 #include <sys/kdebug.h>
  81 #include <sys/kauth.h>
  82 #include <sys/namei.h>
  83
  84 #include "hfs.h"
  85 #include "hfs_catalog.h"
  86 #include "hfs_cnode.h"
  87
  88
  89 /*
  90  * FROM FREEBSD 3.1
  91  * Convert a component of a pathname into a pointer to a locked cnode.
  92  * This is a very central and rather complicated routine.
  93  * If the file system is not maintained in a strict tree hierarchy,
  94  * this can result in a deadlock situation (see comments in code below).
  95  *
  96  * The cnp->cn_nameiop argument is LOOKUP, CREATE, RENAME, or DELETE depending
  97  * on whether the name is to be looked up, created, renamed, or deleted.
  98  * When CREATE, RENAME, or DELETE is specified, information usable in
  99  * creating, renaming, or deleting a directory entry may be calculated.
 100  * Notice that these are the only operations that can affect the directory of the target.
 101  *
 102  * LOCKPARENT and WANTPARENT actually refer to the parent of the last item,
 103  * so if ISLASTCN is not set, they should be ignored. Also they are mutually exclusive, or
 104  * WANTPARENT really implies DONTLOCKPARENT. Either of them set means that the calling
 105  * routine wants to access the parent of the target, locked or unlocked.
 106  *
 107  * Keeping the parent locked as long as possible protects from other processes
 108  * looking up the same item, so it has to be locked until the cnode is totally finished
 109  *
 110  * hfs_cache_lookup() performs the following for us:
 111  *      check that it is a directory
 112  *      check accessibility of directory
 113  *      check for modification attempts on read-only mounts
 114  *      if name found in cache
 115  *              if at end of path and deleting or creating
 116  *              drop it
 117  *               else
 118  *              return name.
 119  *      return hfs_lookup()
 120  *
 121  * Overall outline of hfs_lookup:
 122  *
 123  *      handle simple cases of . and ..
 124  *      search for name in directory, to found or notfound
 125  * notfound:
 126  *      if creating, return locked directory, leaving info on available slots
 127  *      else return error
 128  * found:
 129  *      if at end of path and deleting, return information to allow delete
 130  *      if at end of path and rewriting (RENAME and LOCKPARENT), lock target
 131  *        cnode and return info to allow rewrite
 132  *      if not at end, add name to cache; if at end and neither creating
 133  *        nor deleting, add name to cache
 134  */
 135
 136
 137 /*
 138  *      Lookup *cnp in directory *dvp, return it in *vpp.
 139  *      **vpp is held on exit.
 140  *      We create a cnode for the file, but we do NOT open the file here.
 141
 142 #% lookup       dvp L ? ?
 143 #% lookup       vpp - L -
 144
 145         IN struct vnode *dvp - Parent node of file;
 146         INOUT struct vnode **vpp - node of target file, its a new node if
 147                 the target vnode did not exist;
 148         IN struct componentname *cnp - Name of file;
 149
 150  *      When should we lock parent_hp in here ??
 151  */
 152 static int
 153 hfs_lookup(struct vnode *dvp, struct vnode **vpp, struct componentname *cnp, int *cnode_locked)
 154 {
 155         struct cnode *dcp;      /* cnode for directory being searched */
 156         struct vnode *tvp;      /* target vnode */
 157         struct hfsmount *hfsmp;
 158         int flags;
 159         int nameiop;
 160         int retval = 0;
 161         int isDot;
 162         struct cat_desc desc;
 163         struct cat_desc cndesc;
 164         struct cat_attr attr;
 165         struct cat_fork fork;
 166         int lockflags;
 167         int newvnode_flags;
 168
 169   retry:
 170         newvnode_flags = 0;
 171         dcp = NULL;
 172         hfsmp = VTOHFS(dvp);
 173         *vpp = NULL;
 174         *cnode_locked = 0;
 175         isDot = FALSE;
 176         tvp = NULL;
 177         nameiop = cnp->cn_nameiop;
 178         flags = cnp->cn_flags;
 179         bzero(&desc, sizeof(desc));
 180
 181         /*
 182          * First check to see if it is a . or .., else look it up.
 183          */
 184         if (flags & ISDOTDOT) {         /* Wanting the parent */
 185                 cnp->cn_flags &= ~MAKEENTRY;
 186                 goto found;     /* .. is always defined */
 187         } else if ((cnp->cn_nameptr[0] == '.') && (cnp->cn_namelen == 1)) {
 188                 isDot = TRUE;
 189                 cnp->cn_flags &= ~MAKEENTRY;
 190                 goto found;     /* We always know who we are */
 191         } else {
 192                 if (hfs_lock(VTOC(dvp), HFS_EXCLUSIVE_LOCK) != 0) {
 193                         retval = ENOENT;  /* The parent no longer exists ? */
 194                         goto exit;
 195                 }
 196                 dcp = VTOC(dvp);
 197
 198                 if (dcp->c_flag & C_DIR_MODIFICATION) {
 199                     // XXXdbg - if we could msleep on a lck_rw_t then we would do that
 200                     //          but since we can't we have to unlock, delay for a bit
 201                     //          and then retry...
 202                     // msleep((caddr_t)&dcp->c_flag, &dcp->c_rwlock, PINOD, "hfs_vnop_lookup", 0);
 203                     hfs_unlock(dcp);
 204                     tsleep((caddr_t)dvp, PRIBIO, "hfs_lookup", 1);
 205
 206                     goto retry;
 207                 }
 208
 209                 /* No need to go to catalog if there are no children */
 210                 if (dcp->c_entries == 0) {
 211                         goto notfound;
 212                 }
 213
 214                 bzero(&cndesc, sizeof(cndesc));
 215                 cndesc.cd_nameptr = (const u_int8_t *)cnp->cn_nameptr;
 216                 cndesc.cd_namelen = cnp->cn_namelen;
 217                 cndesc.cd_parentcnid = dcp->c_fileid;
 218                 cndesc.cd_hint = dcp->c_childhint;
 219
 220                 lockflags = hfs_systemfile_lock(hfsmp, SFL_CATALOG, HFS_SHARED_LOCK);
 221
 222                 retval = cat_lookup(hfsmp, &cndesc, 0, &desc, &attr, &fork, NULL);
 223
 224                 hfs_systemfile_unlock(hfsmp, lockflags);
 225
 226                 if (retval == 0) {
 227                         dcp->c_childhint = desc.cd_hint;
 228                         /*
 229                          * Note: We must drop the parent lock here before calling
 230                          * hfs_getnewvnode (which takes the child lock).
 231                          */
 232                         hfs_unlock(dcp);
 233                         dcp = NULL;
 234
 235                         /* Verify that the item just looked up isn't one of the hidden directories. */
 236                         if (desc.cd_cnid == hfsmp->hfs_private_desc[FILE_HARDLINKS].cd_cnid ||
 237                                 desc.cd_cnid == hfsmp->hfs_private_desc[DIR_HARDLINKS].cd_cnid) {
 238                                 retval = ENOENT;
 239                                 goto exit;
 240                         }
 241
 242                         goto found;
 243                 }
 244 notfound:
 245                 /*
 246                  * ENAMETOOLONG supersedes other errors
 247                  *
 248                  * For a CREATE or RENAME operation on the last component
 249                  * the ENAMETOOLONG will be handled in the next VNOP.
 250                  */
 251                 if ((retval != ENAMETOOLONG) &&
 252                     (cnp->cn_namelen > kHFSPlusMaxFileNameChars) &&
 253                     (((flags & ISLASTCN) == 0) || ((nameiop != CREATE) && (nameiop != RENAME)))) {
 254                         retval = ENAMETOOLONG;
 255                 } else if (retval == 0) {
 256                         retval = ENOENT;
 257                 }
 258                 if (retval != ENOENT)
 259                         goto exit;
 260                 /*
 261                  * This is a non-existing entry
 262                  *
 263                  * If creating, and at end of pathname and current
 264                  * directory has not been removed, then can consider
 265                  * allowing file to be created.
 266                  */
 267                 if ((nameiop == CREATE || nameiop == RENAME ||
 268                     (nameiop == DELETE &&
 269                     (cnp->cn_flags & DOWHITEOUT) &&
 270                     (cnp->cn_flags & ISWHITEOUT))) &&
 271                     (flags & ISLASTCN) &&
 272                     !(ISSET(dcp->c_flag, C_DELETED | C_NOEXISTS))) {
 273                         retval = EJUSTRETURN;
 274                         goto exit;
 275                 }
 276                 /*
 277                  * Insert name into the name cache (as non-existent).
 278                  */
 279                 if ((hfsmp->hfs_flags & HFS_STANDARD) == 0 &&
 280                     (cnp->cn_flags & MAKEENTRY) &&
 281                     (nameiop != CREATE)) {
 282                         cache_enter(dvp, NULL, cnp);
 283                         dcp->c_flag |= C_NEG_ENTRIES;
 284                 }
 285                 goto exit;
 286         }
 287
 288 found:
 289         if (flags & ISLASTCN) {
 290                 switch(nameiop) {
 291                 case DELETE:
 292                         cnp->cn_flags &= ~MAKEENTRY;
 293                         break;
 294
 295                 case RENAME:
 296                         cnp->cn_flags &= ~MAKEENTRY;
 297                         if (isDot) {
 298                                 retval = EISDIR;
 299                                 goto exit;
 300                         }
 301                         break;
 302                 }
 303         }
 304
 305         if (isDot) {
 306                 if ((retval = vnode_get(dvp)))
 307                         goto exit;
 308                 *vpp = dvp;
 309         } else if (flags & ISDOTDOT) {
 310                 /*
 311                  * Directory hard links can have multiple parents so
 312                  * find the appropriate parent for the current thread.
 313                  */
 314                 if ((retval = hfs_vget(hfsmp, hfs_currentparent(VTOC(dvp)), &tvp, 0, 0))) {
 315                         goto exit;
 316                 }
 317                 *cnode_locked = 1;
 318                 *vpp = tvp;
 319         } else {
 320                 int type = (attr.ca_mode & S_IFMT);
 321
 322                 if (!(flags & ISLASTCN) && (type != S_IFDIR) && (type != S_IFLNK)) {
 323                         retval = ENOTDIR;
 324                         goto exit;
 325                 }
 326                 /* Don't cache directory hardlink names. */
 327                 if (attr.ca_recflags & kHFSHasLinkChainMask) {
 328                         cnp->cn_flags &= ~MAKEENTRY;
 329                 }
 330                 /* Names with composed chars are not cached. */
 331                 if (cnp->cn_namelen != desc.cd_namelen)
 332                         cnp->cn_flags &= ~MAKEENTRY;
 333
 334                 retval = hfs_getnewvnode(hfsmp, dvp, cnp, &desc, 0, &attr, &fork, &tvp, &newvnode_flags);
 335
 336                 if (retval) {
 337                         /*
 338                          * If this was a create/rename operation lookup, then by this point
 339                          * we expected to see the item returned from hfs_getnewvnode above.
 340                          * In the create case, it would probably eventually bubble out an EEXIST
 341                          * because the item existed when we were trying to create it.  In the
 342                          * rename case, it would let us know that we need to go ahead and
 343                          * delete it as part of the rename.  However, if we hit the condition below
 344                          * then it means that we found the element during cat_lookup above, but
 345                          * it is now no longer there.  We simply behave as though we never found
 346                          * the element at all and return EJUSTRETURN.
 347                          */
 348                         if ((retval == ENOENT) &&
 349                                         ((cnp->cn_nameiop == CREATE) || (cnp->cn_nameiop == RENAME)) &&
 350                                         (flags & ISLASTCN)) {
 351                                 retval = EJUSTRETURN;
 352                         }
 353
 354                         /*
 355                          * If this was a straight lookup operation, we may need to redrive the entire
 356                          * lookup starting from cat_lookup if the element was deleted as the result of
 357                          * a rename operation.  Since rename is supposed to guarantee atomicity, then
 358                          * lookups cannot fail because the underlying element is deleted as a result of
 359                          * the rename call -- either they returned the looked up element prior to rename
 360                          * or return the newer element.  If we are in this region, then all we can do is add
 361                          * workarounds to guarantee the latter case. The element has already been deleted, so
 362                          * we just re-try the lookup to ensure the caller gets the most recent element.
 363                          */
 364                         if ((retval == ENOENT) && (cnp->cn_nameiop == LOOKUP) &&
 365                                 (newvnode_flags & (GNV_CHASH_RENAMED | GNV_CAT_DELETED))) {
 366                                 if (dcp) {
 367                                         hfs_unlock (dcp);
 368                                 }
 369                                 /* get rid of any name buffers that may have lingered from the cat_lookup call */
 370                                 cat_releasedesc (&desc);
 371                                 goto retry;
 372                         }
 373
 374                         /* Also, re-drive the lookup if the item we looked up was a hardlink, and the number
 375                          * or name of hardlinks has changed in the interim between the cat_lookup above, and
 376                          * our call to hfs_getnewvnode.  hfs_getnewvnode will validate the cattr we passed it
 377                          * against what is actually in the catalog after the cnode is created.  If there were
 378                          * any issues, it will bubble out ERECYCLE, which we need to swallow and use as the
 379                          * key to redrive as well.  We need to special case this below because in this case,
 380                          * it needs to occur regardless of the type of lookup we're doing here.
 381                          */
 382                         if ((retval == ERECYCLE) && (newvnode_flags & GNV_CAT_ATTRCHANGED)) {
 383                                 if (dcp) {
 384                                         hfs_unlock (dcp);
 385                                 }
 386                                 /* get rid of any name buffers that may have lingered from the cat_lookup call */
 387                                 cat_releasedesc (&desc);
 388                                 retval = 0;
 389                                 goto retry;
 390                         }
 391
 392                         /* skip to the error-handling code if we can't retry */
 393                         goto exit;
 394                 }
 395
 396                 /*
 397                  * Save the origin info for file and directory hardlinks.  Directory hardlinks
 398                  * need the origin for '..' lookups, and file hardlinks need it to ensure that
 399                  * competing lookups do not cause us to vend different hardlinks than the ones requested.
 400                  * We want to restrict saving the cache entries to LOOKUP namei operations, since
 401                  * we're really doing this to protect getattr.
 402                  */
 403                 if ((nameiop == LOOKUP) && (VTOC(tvp)->c_flag & C_HARDLINK)) {
 404                         hfs_savelinkorigin(VTOC(tvp), VTOC(dvp)->c_fileid);
 405                 }
 406                 *cnode_locked = 1;
 407                 *vpp = tvp;
 408         }
 409 exit:
 410         if (dcp) {
 411                 hfs_unlock(dcp);
 412         }
 413         cat_releasedesc(&desc);
 414         return (retval);
 415 }
 416
 417
 418
 419 /*
 420  * Name caching works as follows:
 421  *
 422  * Names found by directory scans are retained in a cache
 423  * for future reference.  It is managed LRU, so frequently
 424  * used names will hang around.  Cache is indexed by hash value
 425  * obtained from (vp, name) where vp refers to the directory
 426  * containing name.
 427  *
 428  * If it is a "negative" entry, (i.e. for a name that is known NOT to
 429  * exist) the vnode pointer will be NULL.
 430  *
 431  * Upon reaching the last segment of a path, if the reference
 432  * is for DELETE, or NOCACHE is set (rewrite), and the
 433  * name is located in the cache, it will be dropped.
 434  *
 435  */
 436
 437 #define S_IXALL 0000111
 438
 439 int
 440 hfs_vnop_lookup(struct vnop_lookup_args *ap)
 441 {
 442         struct vnode *dvp = ap->a_dvp;
 443         struct vnode *vp;
 444         struct cnode *cp;
 445         struct cnode *dcp;
 446         struct hfsmount *hfsmp;
 447         int error;
 448         struct vnode **vpp = ap->a_vpp;
 449         struct componentname *cnp = ap->a_cnp;
 450         int flags = cnp->cn_flags;
 451         int cnode_locked;
 452
 453         *vpp = NULL;
 454         dcp = VTOC(dvp);
 455
 456         hfsmp = VTOHFS(dvp);
 457
 458         /*
 459          * Lookup an entry in the cache
 460          *
 461          * If the lookup succeeds, the vnode is returned in *vpp,
 462          * and a status of -1 is returned.
 463          *
 464          * If the lookup determines that the name does not exist
 465          * (negative cacheing), a status of ENOENT is returned.
 466          *
 467          * If the lookup fails, a status of zero is returned.
 468          */
 469         error = cache_lookup(dvp, vpp, cnp);
 470         if (error != -1) {
 471                 if ((error == ENOENT) && (cnp->cn_nameiop != CREATE))
 472                         goto exit;      /* found a negative cache entry */
 473                 goto lookup;            /* did not find it in the cache */
 474         }
 475         /*
 476          * We have a name that matched
 477          * cache_lookup returns the vp with an iocount reference already taken
 478          */
 479         error = 0;
 480         vp = *vpp;
 481         cp = VTOC(vp);
 482
 483         /* We aren't allowed to vend out vp's via lookup to the hidden directory */
 484         if (cp->c_cnid == hfsmp->hfs_private_desc[FILE_HARDLINKS].cd_cnid ||
 485                 cp->c_cnid == hfsmp->hfs_private_desc[DIR_HARDLINKS].cd_cnid) {
 486                 /* Drop the iocount from cache_lookup */
 487                 vnode_put (vp);
 488                 error = ENOENT;
 489                 goto exit;
 490         }
 491
 492
 493         /*
 494          * If this is a hard-link vnode then we need to update
 495          * the name (of the link), the parent ID, the cnid, the
 496          * text encoding and the catalog hint.  This enables
 497          * getattrlist calls to return the correct link info.
 498          */
 499
 500         if ((flags & ISLASTCN) && (cp->c_flag & C_HARDLINK)) {
 501                 hfs_lock(cp, HFS_FORCE_LOCK);
 502                 if ((cp->c_parentcnid != dcp->c_cnid) ||
 503                     (bcmp(cnp->cn_nameptr, cp->c_desc.cd_nameptr, cp->c_desc.cd_namelen) != 0)) {
 504                         struct cat_desc desc;
 505                         int lockflags;
 506
 507                         /*
 508                          * Get an updated descriptor
 509                          */
 510                         desc.cd_nameptr = (const u_int8_t *)cnp->cn_nameptr;
 511                         desc.cd_namelen = cnp->cn_namelen;
 512                         desc.cd_parentcnid = dcp->c_fileid;
 513                         desc.cd_hint = dcp->c_childhint;
 514                         desc.cd_encoding = 0;
 515                         desc.cd_cnid = 0;
 516                         desc.cd_flags = S_ISDIR(cp->c_mode) ? CD_ISDIR : 0;
 517
 518
 519                         lockflags = hfs_systemfile_lock(VTOHFS(dvp), SFL_CATALOG, HFS_SHARED_LOCK);
 520                         if (cat_lookup(VTOHFS(vp), &desc, 0, &desc, NULL, NULL, NULL) == 0)
 521                                 replace_desc(cp, &desc);
 522                         hfs_systemfile_unlock(VTOHFS(dvp), lockflags);
 523
 524                         /*
 525                          * Save the origin info for file and directory hardlinks.  Directory hardlinks
 526                          * need the origin for '..' lookups, and file hardlinks need it to ensure that
 527                          * competing lookups do not cause us to vend different hardlinks than the ones requested.
 528                          * We want to restrict saving the cache entries to LOOKUP namei operations, since
 529                          * we're really doing this to protect getattr.
 530                          */
 531                         if (cnp->cn_nameiop == LOOKUP) {
 532                                 hfs_savelinkorigin(cp, dcp->c_fileid);
 533                         }
 534                 }
 535                 hfs_unlock(cp);
 536         }
 537
 538         return (error);
 539
 540 lookup:
 541         /*
 542          * The vnode was not in the name cache or it was stale.
 543          *
 544          * So we need to do a real lookup.
 545          */
 546         cnode_locked = 0;
 547
 548         error = hfs_lookup(dvp, vpp, cnp, &cnode_locked);
 549
 550         if (cnode_locked)
 551                 hfs_unlock(VTOC(*vpp));
 552 exit:
 553         return (error);
 554 }
 555
 556