bsd/isofs/cd9660/cd9660_lookup.c

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