bsd/isofs/cd9660/cd9660_lookup.c

   1 /*
   2  * Copyright (c) 2000-2003 Apple Computer, Inc. All rights reserved.
   3  *
   4  * @APPLE_LICENSE_HEADER_START@
   5  *
   6  * The contents of this file constitute Original Code as defined in and
   7  * are subject to the Apple Public Source License Version 1.1 (the
   8  * "License").  You may not use this file except in compliance with the
   9  * License.  Please obtain a copy of the License at
  10  * http://www.apple.com/publicsource and read it before using this file.
  11  *
  12  * This Original Code and all software distributed under the License are
  13  * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  14  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  15  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  16  * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT.  Please see the
  17  * License for the specific language governing rights and limitations
  18  * under the License.
  19  *
  20  * @APPLE_LICENSE_HEADER_END@
  21  */
  22 /*      $NetBSD: cd9660_lookup.c,v 1.13 1994/12/24 15:30:03 cgd Exp $   */
  23
  24 /*-
  25  * Copyright (c) 1989, 1993, 1994
  26  *      The Regents of the University of California.  All rights reserved.
  27  *
  28  * This code is derived from software contributed to Berkeley
  29  * by Pace Willisson (pace@blitz.com).  The Rock Ridge Extension
  30  * Support code is derived from software contributed to Berkeley
  31  * by Atsushi Murai (amurai@spec.co.jp).
  32  *
  33  * Redistribution and use in source and binary forms, with or without
  34  * modification, are permitted provided that the following conditions
  35  * are met:
  36  * 1. Redistributions of source code must retain the above copyright
  37  *    notice, this list of conditions and the following disclaimer.
  38  * 2. Redistributions in binary form must reproduce the above copyright
  39  *    notice, this list of conditions and the following disclaimer in the
  40  *    documentation and/or other materials provided with the distribution.
  41  * 3. All advertising materials mentioning features or use of this software
  42  *    must display the following acknowledgement:
  43  *      This product includes software developed by the University of
  44  *      California, Berkeley and its contributors.
  45  * 4. Neither the name of the University nor the names of its contributors
  46  *    may be used to endorse or promote products derived from this software
  47  *    without specific prior written permission.
  48  *
  49  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  50  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  51  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  52  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  53  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  54  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  55  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  56  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  57  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  58  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  59  * SUCH DAMAGE.
  60  *
  61  *      from: @(#)ufs_lookup.c  7.33 (Berkeley) 5/19/91
  62  *
  63  *      @(#)cd9660_lookup.c     8.5 (Berkeley) 12/5/94
  64  *
  65  */
  66
  67 #include <sys/param.h>
  68 #include <sys/vnode.h>
  69 #include <sys/mount.h>
  70 #include <sys/namei.h>
  71 #include <sys/buf.h>
  72 #include <sys/file.h>
  73 #include <sys/utfconv.h>
  74
  75 #include <isofs/cd9660/iso.h>
  76 #include <isofs/cd9660/cd9660_node.h>
  77 #include <isofs/cd9660/iso_rrip.h>
  78 #include <isofs/cd9660/cd9660_rrip.h>
  79
  80 struct  nchstats iso_nchstats;
  81
  82 /*
  83  * Convert a component of a pathname into a pointer to a locked inode.
  84  * This is a very central and rather complicated routine.
  85  * If the file system is not maintained in a strict tree hierarchy,
  86  * this can result in a deadlock situation (see comments in code below).
  87  *
  88  * The flag argument is LOOKUP, CREATE, RENAME, or DELETE depending on
  89  * whether the name is to be looked up, created, renamed, or deleted.
  90  * When CREATE, RENAME, or DELETE is specified, information usable in
  91  * creating, renaming, or deleting a directory entry may be calculated.
  92  * If flag has LOCKPARENT or'ed into it and the target of the pathname
  93  * exists, lookup returns both the target and its parent directory locked.
  94  * When creating or renaming and LOCKPARENT is specified, the target may
  95  * not be ".".  When deleting and LOCKPARENT is specified, the target may
  96  * be "."., but the caller must check to ensure it does an vrele and iput
  97  * instead of two iputs.
  98  *
  99  * Overall outline of ufs_lookup:
 100  *
 101  *      check accessibility of directory
 102  *      look for name in cache, if found, then if at end of path
 103  *        and deleting or creating, drop it, else return name
 104  *      search for name in directory, to found or notfound
 105  * notfound:
 106  *      if creating, return locked directory, leaving info on available slots
 107  *      else return error
 108  * found:
 109  *      if at end of path and deleting, return information to allow delete
 110  *      if at end of path and rewriting (RENAME and LOCKPARENT), lock target
 111  *        inode and return info to allow rewrite
 112  *      if not at end, add name to cache; if at end and neither creating
 113  *        nor deleting, add name to cache
 114  *
 115  * NOTE: (LOOKUP | LOCKPARENT) currently returns the parent inode unlocked.
 116  */
 117 int
 118 cd9660_lookup(ap)
 119         struct vop_lookup_args /* {
 120                 struct vnode *a_dvp;
 121                 struct vnode **a_vpp;
 122                 struct componentname *a_cnp;
 123         } */ *ap;
 124 {
 125         register struct vnode *vdp;     /* vnode for directory being searched */
 126         register struct iso_node *dp;   /* inode for directory being searched */
 127         register struct iso_mnt *imp;   /* file system that directory is in */
 128         struct buf *bp;                 /* a buffer of directory entries */
 129         struct iso_directory_record *ep = NULL;/* the current directory entry */
 130         int entryoffsetinblock;         /* offset of ep in bp's buffer */
 131         int saveoffset = 0;             /* offset of last directory entry in dir */
 132         int numdirpasses;               /* strategy for directory search */
 133         doff_t endsearch;               /* offset to end directory search */
 134         struct vnode *pdp;              /* saved dp during symlink work */
 135         struct vnode *tdp;              /* returned by cd9660_vget_internal */
 136         u_long bmask;                   /* block offset mask */
 137         int lockparent;                 /* 1 => lockparent flag is set */
 138         int wantparent;                 /* 1 => wantparent or lockparent flag */
 139         int wantassoc;
 140         int error;
 141         ino_t ino = 0;
 142         int reclen;
 143         u_short namelen;
 144         int isoflags;
 145         char altname[ISO_RRIP_NAMEMAX];
 146         int res;
 147         int len;
 148         char *name;
 149         struct vnode **vpp = ap->a_vpp;
 150         struct componentname *cnp = ap->a_cnp;
 151         int flags = cnp->cn_flags;
 152         int nameiop = cnp->cn_nameiop;
 153         struct proc *p = cnp->cn_proc;
 154         int devBlockSize=0;
 155         size_t altlen;
 156
 157         bp = NULL;
 158         *vpp = NULL;
 159         vdp = ap->a_dvp;
 160         dp = VTOI(vdp);
 161         imp = dp->i_mnt;
 162         lockparent = flags & LOCKPARENT;
 163         wantparent = flags & (LOCKPARENT|WANTPARENT);
 164         wantassoc = 0;
 165
 166
 167         /*
 168          * Check accessiblity of directory.
 169          */
 170         if (vdp->v_type != VDIR)
 171                 return (ENOTDIR);
 172         if ( (error = VOP_ACCESS(vdp, VEXEC, cnp->cn_cred, p)) )
 173                 return (error);
 174
 175         /*
 176          * We now have a segment name to search for, and a directory to search.
 177          *
 178          * Before tediously performing a linear scan of the directory,
 179          * check the name cache to see if the directory/name pair
 180          * we are looking for is known already.
 181          */
 182         if ((error = cache_lookup(vdp, vpp, cnp))) {
 183                 int vpid;       /* capability number of vnode */
 184
 185                 if (error == ENOENT)
 186                         return (error);
 187                 /*
 188                  * Get the next vnode in the path.
 189                  * See comment below starting `Step through' for
 190                  * an explaination of the locking protocol.
 191                  */
 192                 pdp = vdp;
 193                 dp = VTOI(*vpp);
 194                 vdp = *vpp;
 195                 vpid = vdp->v_id;
 196                 if (pdp == vdp) {
 197                         VREF(vdp);
 198                         error = 0;
 199                 } else if (flags & ISDOTDOT) {
 200                         VOP_UNLOCK(pdp, 0, p);
 201                         error = vget(vdp, LK_EXCLUSIVE | LK_RETRY, p);
 202                         if (!error && lockparent && (flags & ISLASTCN))
 203                                 error = VOP_LOCK(pdp, LK_EXCLUSIVE | LK_RETRY, p);
 204                 } else {
 205                         error = vget(vdp, LK_EXCLUSIVE | LK_RETRY, p);
 206                         if (!lockparent || error || !(flags & ISLASTCN))
 207                                 VOP_UNLOCK(pdp, 0, p);
 208                 }
 209                 /*
 210                  * Check that the capability number did not change
 211                  * while we were waiting for the lock.
 212                  */
 213                 if (!error) {
 214                         if (vpid == vdp->v_id)
 215                                 return (0);
 216                         vput(vdp);
 217                         if (lockparent && pdp != vdp && (flags & ISLASTCN))
 218                                 VOP_UNLOCK(pdp, 0, p);
 219                 }
 220                 if ( (error = VOP_LOCK(pdp, LK_EXCLUSIVE | LK_RETRY, p)) )
 221                         return (error);
 222                 vdp = pdp;
 223                 dp = VTOI(pdp);
 224                 *vpp = NULL;
 225         }
 226
 227         len = cnp->cn_namelen;
 228         name = cnp->cn_nameptr;
 229         altname[0] = '\0';
 230         /*
 231          * A "._" prefix means, we are looking for an associated file
 232          */
 233         if (imp->iso_ftype != ISO_FTYPE_RRIP &&
 234             *name == ASSOCCHAR1 && *(name+1) == ASSOCCHAR2) {
 235                 wantassoc = 1;
 236                 len -= 2;
 237                 name += 2;
 238         }
 239         /*
 240          * Decode search name into UCS-2 (Unicode)
 241          */
 242         if ((imp->iso_ftype == ISO_FTYPE_JOLIET) &&
 243             !((len == 1 && *name == '.') || (flags & ISDOTDOT))) {
 244                 int flags = UTF_PRECOMPOSED;
 245
 246                 if (BYTE_ORDER != BIG_ENDIAN)
 247                         flags |= UTF_REVERSE_ENDIAN;
 248
 249                 (void) utf8_decodestr(name, len, (u_int16_t*) altname, &altlen,
 250                                         sizeof(altname), 0, flags);
 251                 name = altname;
 252                 len = altlen;
 253         }
 254         /*
 255          * If there is cached information on a previous search of
 256          * this directory, pick up where we last left off.
 257          * We cache only lookups as these are the most common
 258          * and have the greatest payoff. Caching CREATE has little
 259          * benefit as it usually must search the entire directory
 260          * to determine that the entry does not exist. Caching the
 261          * location of the last DELETE or RENAME has not reduced
 262          * profiling time and hence has been removed in the interest
 263          * of simplicity.
 264          */
 265         bmask = imp->im_sector_size - 1;
 266         if (nameiop != LOOKUP || dp->i_diroff == 0 ||
 267             dp->i_diroff > dp->i_size) {
 268                 entryoffsetinblock = 0;
 269                 dp->i_offset = 0;
 270                 numdirpasses = 1;
 271         } else {
 272                 dp->i_offset = dp->i_diroff;
 273
 274                 if ((entryoffsetinblock = dp->i_offset & bmask) &&
 275                     (error = VOP_BLKATOFF(vdp, SECTOFF(imp, dp->i_offset), NULL, &bp)))
 276                                 return (error);
 277                 numdirpasses = 2;
 278                 iso_nchstats.ncs_2passes++;
 279         }
 280         endsearch = dp->i_size;
 281
 282 searchloop:
 283         while (dp->i_offset < endsearch) {
 284                 /*
 285                  * If offset is on a block boundary,
 286                  * read the next directory block.
 287                  * Release previous if it exists.
 288                  */
 289                 if ((dp->i_offset & bmask) == 0) {
 290                         if (bp != NULL)
 291                                 brelse(bp);
 292                         if ( (error = VOP_BLKATOFF(vdp, SECTOFF(imp,dp->i_offset), NULL, &bp)) )
 293                                 return (error);
 294                         entryoffsetinblock = 0;
 295                 }
 296                 /*
 297                  * Get pointer to next entry.
 298                  */
 299                 ep = (struct iso_directory_record *)
 300                         ((char *)bp->b_data + entryoffsetinblock);
 301
 302                 reclen = isonum_711(ep->length);
 303                 if (reclen == 0) {
 304                         /* skip to next block, if any */
 305                         dp->i_offset =
 306                             (dp->i_offset & ~bmask) + imp->im_sector_size;
 307                         continue;
 308                 }
 309
 310                 if (reclen < ISO_DIRECTORY_RECORD_SIZE) {
 311                         /* illegal entry, stop */
 312                         break;
 313                 }
 314                 if (entryoffsetinblock + reclen > imp->im_sector_size) {
 315                         /* entries are not allowed to cross sector boundaries */
 316                         break;
 317                 }
 318                 namelen = isonum_711(ep->name_len);
 319                 isoflags = isonum_711(ep->flags);
 320
 321                 if (reclen < ISO_DIRECTORY_RECORD_SIZE + namelen)
 322                         /* illegal entry, stop */
 323                         break;
 324                 /*
 325                  * Check for a name match.
 326                  */
 327                 if (imp->iso_ftype == ISO_FTYPE_RRIP) {
 328                         if (isoflags & directoryBit)
 329                                 ino = isodirino(ep, imp);
 330                         else
 331                                 ino = (bp->b_blkno << imp->im_bshift) + entryoffsetinblock;
 332                         dp->i_ino = ino;
 333                         cd9660_rrip_getname(ep,altname,&namelen,&dp->i_ino,imp);
 334                         if (namelen == cnp->cn_namelen
 335                             && !bcmp(name,altname,namelen))
 336                                 goto found;
 337                         ino = 0;
 338                 } else {
 339                         if ((!(isoflags & associatedBit)) == !wantassoc) {
 340                                 if ((len == 1
 341                                      && *name == '.')
 342                                     || (flags & ISDOTDOT)) {
 343                                         if (namelen == 1
 344                                             && ep->name[0] == ((flags & ISDOTDOT) ? 1 : 0)) {
 345                                                 /*
 346                                                  * Save directory entry's inode number and
 347                                                  * release directory buffer.
 348                                                  */
 349                                                 dp->i_ino = isodirino(ep, imp);
 350                                                 goto found;
 351                                         }
 352                                         if (namelen != 1
 353                                             || ep->name[0] != 0)
 354                                                 goto notfound;
 355                                 } else if (imp->iso_ftype != ISO_FTYPE_JOLIET && !(res = isofncmp(name,len,
 356                                                             ep->name,namelen))) {
 357                                         if ( isoflags & directoryBit )
 358                                                 ino = isodirino(ep, imp);
 359                                         else
 360                                                 ino = (bp->b_blkno << imp->im_bshift) + entryoffsetinblock;
 361                                         saveoffset = dp->i_offset;
 362                                 } else if (imp->iso_ftype == ISO_FTYPE_JOLIET && !(res = ucsfncmp((u_int16_t*)name, len,
 363                                                             (u_int16_t*) ep->name, namelen))) {
 364                                         if ( isoflags & directoryBit )
 365                                                 ino = isodirino(ep, imp);
 366                                         else
 367                                                 ino = (bp->b_blkno << imp->im_bshift) + entryoffsetinblock;
 368                                         saveoffset = dp->i_offset;
 369                                 } else if (ino)
 370                                         goto foundino;
 371 #ifdef  NOSORTBUG       /* On some CDs directory entries are not sorted correctly */
 372                                 else if (res < 0)
 373                                         goto notfound;
 374                                 else if (res > 0 && numdirpasses == 2)
 375                                         numdirpasses++;
 376 #endif
 377                         }
 378                 }
 379                 dp->i_offset += reclen;
 380                 entryoffsetinblock += reclen;
 381         } /* endwhile */
 382
 383         if (ino) {
 384 foundino:
 385                 dp->i_ino = ino;
 386                 if (saveoffset != dp->i_offset) {
 387                         if (lblkno(imp, dp->i_offset) !=
 388                             lblkno(imp, saveoffset)) {
 389                                 if (bp != NULL)
 390                                         brelse(bp);
 391                                 if ( (error = VOP_BLKATOFF(vdp, SECTOFF(imp, saveoffset), NULL, &bp)) )
 392                                         return (error);
 393                         }
 394                         entryoffsetinblock = saveoffset & bmask;
 395                         ep = (struct iso_directory_record *)
 396                                 ((char *)bp->b_data + entryoffsetinblock);
 397                         dp->i_offset = saveoffset;
 398                 }
 399                 goto found;
 400         }
 401 notfound:
 402         /*
 403          * If we started in the middle of the directory and failed
 404          * to find our target, we must check the beginning as well.
 405          */
 406         if (numdirpasses == 2) {
 407                 numdirpasses--;
 408                 dp->i_offset = 0;
 409                 endsearch = dp->i_diroff;
 410                 goto searchloop;
 411         }
 412         if (bp != NULL)
 413                 brelse(bp);
 414
 415         /*
 416          * Insert name into cache (as non-existent) if appropriate.
 417          */
 418         if (cnp->cn_flags & MAKEENTRY)
 419                 cache_enter(vdp, *vpp, cnp);
 420         if (nameiop == CREATE || nameiop == RENAME) {
 421                 /*
 422                  * return EROFS (NOT EJUSTRETURN).  The caller will then unlock
 423                  * the parent for us.
 424                  */
 425                 return (EROFS);
 426         }
 427         return (ENOENT);
 428
 429 found:
 430         if (numdirpasses == 2)
 431                 iso_nchstats.ncs_pass2++;
 432
 433         /*
 434          * Found component in pathname.
 435          * If the final component of path name, save information
 436          * in the cache as to where the entry was found.
 437          */
 438         if ((flags & ISLASTCN) && nameiop == LOOKUP)
 439                 dp->i_diroff = dp->i_offset;
 440
 441         /*
 442          * Step through the translation in the name.  We do not `iput' the
 443          * directory because we may need it again if a symbolic link
 444          * is relative to the current directory.  Instead we save it
 445          * unlocked as "pdp".  We must get the target inode before unlocking
 446          * the directory to insure that the inode will not be removed
 447          * before we get it.  We prevent deadlock by always fetching
 448          * inodes from the root, moving down the directory tree. Thus
 449          * when following backward pointers ".." we must unlock the
 450          * parent directory before getting the requested directory.
 451          * There is a potential race condition here if both the current
 452          * and parent directories are removed before the `iget' for the
 453          * inode associated with ".." returns.  We hope that this occurs
 454          * infrequently since we cannot avoid this race condition without
 455          * implementing a sophisticated deadlock detection algorithm.
 456          * Note also that this simple deadlock detection scheme will not
 457          * work if the file system has any hard links other than ".."
 458          * that point backwards in the directory structure.
 459          */
 460         pdp = vdp;
 461         /*
 462          * If ino is different from dp->i_ino,
 463          * it's a relocated directory.
 464          */
 465         if (flags & ISDOTDOT) {
 466                 VOP_UNLOCK(pdp, 0, p);  /* race to get the inode */
 467                 error = cd9660_vget_internal(vdp->v_mount, dp->i_ino, &tdp,
 468                                              dp->i_ino != ino, ep, p);
 469                 VTOI(tdp)->i_parent = VTOI(pdp)->i_number;
 470                 brelse(bp);
 471                 if (error) {
 472                         VOP_LOCK(pdp, LK_EXCLUSIVE | LK_RETRY, p);
 473                         return (error);
 474                 }
 475                 if (lockparent && (flags & ISLASTCN) &&
 476                     (error = VOP_LOCK(pdp, LK_EXCLUSIVE | LK_RETRY, p))) {
 477                         vput(tdp);
 478                         return (error);
 479                 }
 480                 *vpp = tdp;
 481         } else if (dp->i_number == dp->i_ino) {
 482                 brelse(bp);
 483                 VREF(vdp);      /* we want ourself, ie "." */
 484                 *vpp = vdp;
 485         } else {
 486                 error = cd9660_vget_internal(vdp->v_mount, dp->i_ino, &tdp,
 487                                              dp->i_ino != ino, ep, p);
 488                 /* save parent inode number */
 489                 VTOI(tdp)->i_parent = VTOI(pdp)->i_number;
 490                 brelse(bp);
 491                 if (error)
 492                         return (error);
 493                 if (!lockparent || !(flags & ISLASTCN))
 494                         VOP_UNLOCK(pdp, 0, p);
 495                 *vpp = tdp;
 496         }
 497
 498         /*
 499          * Insert name into cache if appropriate.
 500          */
 501         if (cnp->cn_flags & MAKEENTRY)
 502                 cache_enter(vdp, *vpp, cnp);
 503
 504         return (0);
 505 }
 506
 507
 508 /*
 509  * Return buffer with the contents of block "offset" from the beginning of
 510  * directory "ip".  If "res" is non-zero, fill it in with a pointer to the
 511  * remaining space in the directory.
 512  */
 513 int
 514 cd9660_blkatoff(ap)
 515         struct vop_blkatoff_args /* {
 516                 struct vnode *a_vp;
 517                 off_t a_offset;
 518                 char **a_res;
 519                 struct buf **a_bpp;
 520         } */ *ap;
 521 {
 522         struct iso_node *ip;
 523         register struct iso_mnt *imp;
 524         struct buf *bp;
 525         daddr_t lbn;
 526         int bsize, error;
 527
 528         ip = VTOI(ap->a_vp);
 529         imp = ip->i_mnt;
 530         lbn = lblkno(imp, ap->a_offset);
 531         bsize = blksize(imp, ip, lbn);
 532         if ((bsize != imp->im_sector_size) &&
 533             (ap->a_offset & (imp->im_sector_size - 1)) == 0) {
 534                 bsize = imp->im_sector_size;
 535         }
 536
 537         if ( (error = bread(ap->a_vp, lbn, bsize, NOCRED, &bp)) ) {
 538                 brelse(bp);
 539                 *ap->a_bpp = NULL;
 540                 return (error);
 541         }
 542         if (ap->a_res)
 543                 *ap->a_res = (char *)bp->b_data + blkoff(imp, ap->a_offset);
 544         *ap->a_bpp = bp;
 545
 546         return (0);
 547 }