Commit | Line | Data |
---|---|---|
ad93134a WJ |
1 | /* |
2 | * Copyright (c) 1989 The Regents of the University of California. | |
3 | * All rights reserved. | |
4 | * | |
5 | * Redistribution and use in source and binary forms, with or without | |
6 | * modification, are permitted provided that the following conditions | |
7 | * are met: | |
8 | * 1. Redistributions of source code must retain the above copyright | |
9 | * notice, this list of conditions and the following disclaimer. | |
10 | * 2. Redistributions in binary form must reproduce the above copyright | |
11 | * notice, this list of conditions and the following disclaimer in the | |
12 | * documentation and/or other materials provided with the distribution. | |
13 | * 3. All advertising materials mentioning features or use of this software | |
14 | * must display the following acknowledgement: | |
15 | * This product includes software developed by the University of | |
16 | * California, Berkeley and its contributors. | |
17 | * 4. Neither the name of the University nor the names of its contributors | |
18 | * may be used to endorse or promote products derived from this software | |
19 | * without specific prior written permission. | |
20 | * | |
21 | * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND | |
22 | * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE | |
23 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE | |
24 | * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE | |
25 | * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL | |
26 | * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS | |
27 | * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) | |
28 | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT | |
29 | * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY | |
30 | * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF | |
31 | * SUCH DAMAGE. | |
32 | * | |
33 | * @(#)ufs_lookup.c 7.33 (Berkeley) 5/19/91 | |
34 | */ | |
35 | ||
36 | #include "param.h" | |
37 | #include "namei.h" | |
38 | #include "buf.h" | |
39 | #include "file.h" | |
40 | #include "vnode.h" | |
41 | #include "mount.h" | |
42 | ||
43 | #include "iso.h" | |
44 | #include "isofs_node.h" | |
45 | ||
46 | struct nchstats nchstats; | |
47 | ||
48 | /* | |
49 | * Convert a component of a pathname into a pointer to a locked inode. | |
50 | * This is a very central and rather complicated routine. | |
51 | * If the file system is not maintained in a strict tree hierarchy, | |
52 | * this can result in a deadlock situation (see comments in code below). | |
53 | * | |
54 | * The flag argument is LOOKUP, CREATE, RENAME, or DELETE depending on | |
55 | * whether the name is to be looked up, created, renamed, or deleted. | |
56 | * When CREATE, RENAME, or DELETE is specified, information usable in | |
57 | * creating, renaming, or deleting a directory entry may be calculated. | |
58 | * If flag has LOCKPARENT or'ed into it and the target of the pathname | |
59 | * exists, lookup returns both the target and its parent directory locked. | |
60 | * When creating or renaming and LOCKPARENT is specified, the target may | |
61 | * not be ".". When deleting and LOCKPARENT is specified, the target may | |
62 | * be "."., but the caller must check to ensure it does an vrele and iput | |
63 | * instead of two iputs. | |
64 | * | |
65 | * Overall outline of ufs_lookup: | |
66 | * | |
67 | * check accessibility of directory | |
68 | * look for name in cache, if found, then if at end of path | |
69 | * and deleting or creating, drop it, else return name | |
70 | * search for name in directory, to found or notfound | |
71 | * notfound: | |
72 | * if creating, return locked directory, leaving info on available slots | |
73 | * else return error | |
74 | * found: | |
75 | * if at end of path and deleting, return information to allow delete | |
76 | * if at end of path and rewriting (RENAME and LOCKPARENT), lock target | |
77 | * inode and return info to allow rewrite | |
78 | * if not at end, add name to cache; if at end and neither creating | |
79 | * nor deleting, add name to cache | |
80 | * | |
81 | * NOTE: (LOOKUP | LOCKPARENT) currently returns the parent inode unlocked. | |
82 | */ | |
83 | isofs_lookup(vdp, ndp, p) | |
84 | register struct vnode *vdp; | |
85 | register struct nameidata *ndp; | |
86 | struct proc *p; | |
87 | { | |
88 | register struct iso_node *dp; /* the directory we are searching */ | |
89 | register struct iso_mnt *imp; /* file system that directory is in */ | |
90 | struct buf *bp = 0; /* a buffer of directory entries */ | |
91 | register struct iso_directory_record *ep; | |
92 | /* the current directory entry */ | |
93 | int entryoffsetinblock; /* offset of ep in bp's buffer */ | |
94 | enum {NONE, COMPACT, FOUND} slotstatus; | |
95 | int slotoffset = -1; /* offset of area with free space */ | |
96 | int slotsize; /* size of area at slotoffset */ | |
97 | int slotfreespace; /* amount of space free in slot */ | |
98 | int slotneeded; /* size of the entry we're seeking */ | |
99 | int numdirpasses; /* strategy for directory search */ | |
100 | int endsearch; /* offset to end directory search */ | |
101 | struct iso_node *pdp; /* saved dp during symlink work */ | |
102 | struct iso_node *tdp; /* returned by iget */ | |
103 | int flag; /* LOOKUP, CREATE, RENAME, or DELETE */ | |
104 | int lockparent; /* 1 => lockparent flag is set */ | |
105 | int wantparent; /* 1 => wantparent or lockparent flag */ | |
106 | int error; | |
107 | ||
108 | int reclen; | |
109 | int namelen; | |
110 | ||
111 | ndp->ni_dvp = vdp; | |
112 | ndp->ni_vp = NULL; | |
113 | dp = VTOI(vdp); | |
114 | imp = dp->i_mnt; | |
115 | lockparent = ndp->ni_nameiop & LOCKPARENT; | |
116 | flag = ndp->ni_nameiop & OPMASK; | |
117 | wantparent = ndp->ni_nameiop & (LOCKPARENT|WANTPARENT); | |
118 | ||
119 | /* | |
120 | * Check accessiblity of directory. | |
121 | */ | |
122 | if ((dp->iso_flags & 2) == 0) | |
123 | return (ENOTDIR); | |
124 | ||
125 | /* | |
126 | * We now have a segment name to search for, and a directory to search. | |
127 | * | |
128 | * Before tediously performing a linear scan of the directory, | |
129 | * check the name cache to see if the directory/name pair | |
130 | * we are looking for is known already. | |
131 | */ | |
132 | if (error = cache_lookup(ndp)) { | |
133 | int vpid; /* capability number of vnode */ | |
134 | ||
135 | if (error == ENOENT) | |
136 | return (error); | |
137 | #ifdef PARANOID | |
138 | if (vdp == ndp->ni_rdir && ndp->ni_isdotdot) | |
139 | panic("ufs_lookup: .. through root"); | |
140 | #endif | |
141 | /* | |
142 | * Get the next vnode in the path. | |
143 | * See comment below starting `Step through' for | |
144 | * an explaination of the locking protocol. | |
145 | */ | |
146 | pdp = dp; | |
147 | dp = VTOI(ndp->ni_vp); | |
148 | vdp = ndp->ni_vp; | |
149 | vpid = vdp->v_id; | |
150 | if (pdp == dp) { | |
151 | VREF(vdp); | |
152 | error = 0; | |
153 | } else if (ndp->ni_isdotdot) { | |
154 | ISO_IUNLOCK(pdp); | |
155 | error = vget(vdp); | |
156 | if (!error && lockparent && *ndp->ni_next == '\0') | |
157 | ISO_ILOCK(pdp); | |
158 | } else { | |
159 | error = vget(vdp); | |
160 | if (!lockparent || error || *ndp->ni_next != '\0') | |
161 | ISO_IUNLOCK(pdp); | |
162 | } | |
163 | /* | |
164 | * Check that the capability number did not change | |
165 | * while we were waiting for the lock. | |
166 | */ | |
167 | if (!error) { | |
168 | if (vpid == vdp->v_id) | |
169 | return (0); | |
170 | iso_iput(dp); | |
171 | if (lockparent && pdp != dp && *ndp->ni_next == '\0') | |
172 | ISO_IUNLOCK(pdp); | |
173 | } | |
174 | ISO_ILOCK(pdp); | |
175 | dp = pdp; | |
176 | vdp = ITOV(dp); | |
177 | ndp->ni_vp = NULL; | |
178 | } | |
179 | ||
180 | /* | |
181 | * If there is cached information on a previous search of | |
182 | * this directory, pick up where we last left off. | |
183 | * We cache only lookups as these are the most common | |
184 | * and have the greatest payoff. Caching CREATE has little | |
185 | * benefit as it usually must search the entire directory | |
186 | * to determine that the entry does not exist. Caching the | |
187 | * location of the last DELETE or RENAME has not reduced | |
188 | * profiling time and hence has been removed in the interest | |
189 | * of simplicity. | |
190 | */ | |
191 | if (flag != LOOKUP || dp->i_diroff == 0 || dp->i_diroff > dp->i_size) { | |
192 | ndp->ni_ufs.ufs_offset = 0; | |
193 | numdirpasses = 1; | |
194 | } else { | |
195 | ndp->ni_ufs.ufs_offset = dp->i_diroff; | |
196 | entryoffsetinblock = iso_blkoff(imp, ndp->ni_ufs.ufs_offset); | |
197 | if (entryoffsetinblock != 0) { | |
198 | if (error = iso_blkatoff(dp, ndp->ni_ufs.ufs_offset, | |
199 | (char **)0, &bp)) | |
200 | return (error); | |
201 | } | |
202 | numdirpasses = 2; | |
203 | nchstats.ncs_2passes++; | |
204 | } | |
205 | endsearch = roundup(dp->i_size, imp->logical_block_size); | |
206 | ||
207 | searchloop: | |
208 | while (ndp->ni_ufs.ufs_offset < endsearch) { | |
209 | /* | |
210 | * If offset is on a block boundary, | |
211 | * read the next directory block. | |
212 | * Release previous if it exists. | |
213 | */ | |
214 | if (iso_blkoff(imp, ndp->ni_ufs.ufs_offset) == 0) { | |
215 | if (bp != NULL) | |
216 | brelse(bp); | |
217 | if (error = iso_blkatoff(dp, ndp->ni_ufs.ufs_offset, | |
218 | (char **)0, &bp)) | |
219 | return (error); | |
220 | entryoffsetinblock = 0; | |
221 | } | |
222 | /* | |
223 | * Get pointer to next entry. | |
224 | */ | |
225 | ||
226 | ep = (struct iso_directory_record *) | |
227 | (bp->b_un.b_addr + entryoffsetinblock); | |
228 | ||
229 | reclen = isonum_711 (ep->length); | |
230 | if (reclen == 0) { | |
231 | /* skip to next block, if any */ | |
232 | ndp->ni_ufs.ufs_offset = | |
233 | roundup (ndp->ni_ufs.ufs_offset, | |
234 | imp->logical_block_size); | |
235 | continue; | |
236 | } | |
237 | ||
238 | if (reclen < sizeof (struct iso_directory_record)) | |
239 | /* illegal entry, stop */ | |
240 | break; | |
241 | ||
242 | if (entryoffsetinblock + reclen >= imp->logical_block_size) | |
243 | /* entries are not allowed to cross boundaries */ | |
244 | break; | |
245 | ||
246 | /* | |
247 | * Check for a name match. | |
248 | */ | |
249 | namelen = isonum_711 (ep->name_len); | |
250 | ||
251 | if (reclen < sizeof (struct iso_directory_record) + namelen) | |
252 | /* illegal entry, stop */ | |
253 | break; | |
254 | ||
255 | if ((namelen == 1 | |
256 | && ((ndp->ni_namelen == 1 | |
257 | && ndp->ni_ptr[0] == '.' | |
258 | && ep->name[0] == 0) | |
259 | || (ndp->ni_isdotdot && ep->name[0] == 1))) | |
260 | || (namelen >= ndp->ni_namelen | |
261 | && isofncmp(ndp->ni_ptr, ndp->ni_namelen, ep->name, | |
262 | namelen))) { | |
263 | /* | |
264 | * Save directory entry's inode number and | |
265 | * reclen in ndp->ni_ufs area, and release | |
266 | * directory buffer. | |
267 | */ | |
268 | ndp->ni_ufs.ufs_ino = isonum_733 (ep->extent); | |
269 | brelse(bp); | |
270 | goto found; | |
271 | } | |
272 | ndp->ni_ufs.ufs_offset += reclen; | |
273 | entryoffsetinblock += reclen; | |
274 | } | |
275 | /* notfound: */ | |
276 | /* | |
277 | * If we started in the middle of the directory and failed | |
278 | * to find our target, we must check the beginning as well. | |
279 | */ | |
280 | if (numdirpasses == 2) { | |
281 | numdirpasses--; | |
282 | ndp->ni_ufs.ufs_offset = 0; | |
283 | endsearch = dp->i_diroff; | |
284 | goto searchloop; | |
285 | } | |
286 | if (bp != NULL) | |
287 | brelse(bp); | |
288 | /* | |
289 | * Insert name into cache (as non-existent) if appropriate. | |
290 | */ | |
291 | if (ndp->ni_makeentry) | |
292 | cache_enter(ndp); | |
293 | return (ENOENT); | |
294 | ||
295 | found: | |
296 | if (numdirpasses == 2) | |
297 | nchstats.ncs_pass2++; | |
298 | ||
299 | /* | |
300 | * Found component in pathname. | |
301 | * If the final component of path name, save information | |
302 | * in the cache as to where the entry was found. | |
303 | */ | |
304 | if (*ndp->ni_next == '\0' && flag == LOOKUP) | |
305 | dp->i_diroff = ndp->ni_ufs.ufs_offset | |
306 | &~ (imp->logical_block_size - 1); | |
307 | ||
308 | /* | |
309 | * Step through the translation in the name. We do not `iput' the | |
310 | * directory because we may need it again if a symbolic link | |
311 | * is relative to the current directory. Instead we save it | |
312 | * unlocked as "pdp". We must get the target inode before unlocking | |
313 | * the directory to insure that the inode will not be removed | |
314 | * before we get it. We prevent deadlock by always fetching | |
315 | * inodes from the root, moving down the directory tree. Thus | |
316 | * when following backward pointers ".." we must unlock the | |
317 | * parent directory before getting the requested directory. | |
318 | * There is a potential race condition here if both the current | |
319 | * and parent directories are removed before the `iget' for the | |
320 | * inode associated with ".." returns. We hope that this occurs | |
321 | * infrequently since we cannot avoid this race condition without | |
322 | * implementing a sophisticated deadlock detection algorithm. | |
323 | * Note also that this simple deadlock detection scheme will not | |
324 | * work if the file system has any hard links other than ".." | |
325 | * that point backwards in the directory structure. | |
326 | */ | |
327 | pdp = dp; | |
328 | if (ndp->ni_isdotdot) { | |
329 | ISO_IUNLOCK(pdp); /* race to get the inode */ | |
330 | if (error = iso_iget(dp, ndp->ni_ufs.ufs_ino, &tdp, ep)) { | |
331 | ISO_ILOCK(pdp); | |
332 | return (error); | |
333 | } | |
334 | if (lockparent && *ndp->ni_next == '\0') | |
335 | ISO_ILOCK(pdp); | |
336 | ndp->ni_vp = ITOV(tdp); | |
337 | } else if (dp->i_number == ndp->ni_ufs.ufs_ino) { | |
338 | VREF(vdp); /* we want ourself, ie "." */ | |
339 | ndp->ni_vp = vdp; | |
340 | } else { | |
341 | if (error = iso_iget(dp, ndp->ni_ufs.ufs_ino, &tdp, ep)) | |
342 | return (error); | |
343 | if (!lockparent || *ndp->ni_next != '\0') | |
344 | ISO_IUNLOCK(pdp); | |
345 | ndp->ni_vp = ITOV(tdp); | |
346 | } | |
347 | ||
348 | /* | |
349 | * Insert name into cache if appropriate. | |
350 | */ | |
351 | if (ndp->ni_makeentry) | |
352 | cache_enter(ndp); | |
353 | return (0); | |
354 | } | |
355 | ||
356 | ||
357 | /* | |
358 | * Return buffer with contents of block "offset" | |
359 | * from the beginning of directory "ip". If "res" | |
360 | * is non-zero, fill it in with a pointer to the | |
361 | * remaining space in the directory. | |
362 | */ | |
363 | iso_blkatoff(ip, offset, res, bpp) | |
364 | struct iso_node *ip; | |
365 | off_t offset; | |
366 | char **res; | |
367 | struct buf **bpp; | |
368 | { | |
369 | register struct iso_mnt *imp = ip->i_mnt; | |
370 | daddr_t lbn = iso_lblkno (imp, offset); | |
371 | int bsize = iso_blksize (imp, ip, lbn); | |
372 | struct buf *bp; | |
373 | int error; | |
374 | ||
375 | *bpp = 0; | |
376 | if (error = bread(ITOV(ip), lbn, bsize, NOCRED, &bp)) { | |
377 | brelse(bp); | |
378 | return (error); | |
379 | } | |
380 | if (res) | |
381 | *res = bp->b_un.b_addr + iso_blkoff(imp, offset); | |
382 | *bpp = bp; | |
383 | ||
384 | return (0); | |
385 | } | |
386 | ||
387 |