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