1 /* $OpenBSD: ufs_lookup.c,v 1.37 2007/06/01 23:47:57 deraadt Exp $ */
2 /* $NetBSD: ufs_lookup.c,v 1.7 1996/02/09 22:36:06 christos Exp $ */
3
4 /*
5 * Copyright (c) 1989, 1993
6 * The Regents of the University of California. All rights reserved.
7 * (c) UNIX System Laboratories, Inc.
8 * All or some portions of this file are derived from material licensed
9 * to the University of California by American Telephone and Telegraph
10 * Co. or Unix System Laboratories, Inc. and are reproduced herein with
11 * the permission of UNIX System Laboratories, Inc.
12 *
13 * Redistribution and use in source and binary forms, with or without
14 * modification, are permitted provided that the following conditions
15 * are met:
16 * 1. Redistributions of source code must retain the above copyright
17 * notice, this list of conditions and the following disclaimer.
18 * 2. Redistributions in binary form must reproduce the above copyright
19 * notice, this list of conditions and the following disclaimer in the
20 * documentation and/or other materials provided with the distribution.
21 * 3. Neither the name of the University nor the names of its contributors
22 * may be used to endorse or promote products derived from this software
23 * without specific prior written permission.
24 *
25 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
26 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
27 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
28 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
29 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
30 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
31 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
32 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
33 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
34 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
35 * SUCH DAMAGE.
36 *
37 * @(#)ufs_lookup.c 8.9 (Berkeley) 8/11/94
38 */
39
40 #include <sys/param.h>
41 #include <sys/systm.h>
42 #include <sys/kernel.h>
43 #include <sys/namei.h>
44 #include <sys/buf.h>
45 #include <sys/file.h>
46 #include <sys/stat.h>
47 #include <sys/mount.h>
48 #include <sys/vnode.h>
49
50 #include <uvm/uvm_extern.h>
51
52 #include <ufs/ufs/quota.h>
53 #include <ufs/ufs/inode.h>
54 #include <ufs/ufs/dir.h>
55 #ifdef UFS_DIRHASH
56 #include <ufs/ufs/dirhash.h>
57 #endif
58 #include <ufs/ufs/ufsmount.h>
59 #include <ufs/ufs/ufs_extern.h>
60
61 extern struct nchstats nchstats;
62
63 #ifdef DIAGNOSTIC
64 int dirchk = 1;
65 #else
66 int dirchk = 0;
67 #endif
68
69 #define FSFMT(vp) ((vp)->v_mount->mnt_maxsymlinklen <= 0)
70
71 /*
72 * Convert a component of a pathname into a pointer to a locked inode.
73 * This is a very central and rather complicated routine.
74 * If the file system is not maintained in a strict tree hierarchy,
75 * this can result in a deadlock situation (see comments in code below).
76 *
77 * The cnp->cn_nameiop argument is LOOKUP, CREATE, RENAME, or DELETE depending
78 * on whether the name is to be looked up, created, renamed, or deleted.
79 * When CREATE, RENAME, or DELETE is specified, information usable in
80 * creating, renaming, or deleting a directory entry may be calculated.
81 * If flag has LOCKPARENT or'ed into it and the target of the pathname
82 * exists, lookup returns both the target and its parent directory locked.
83 * When creating or renaming and LOCKPARENT is specified, the target may
84 * not be ".". When deleting and LOCKPARENT is specified, the target may
85 * be "."., but the caller must check to ensure it does an vrele and vput
86 * instead of two vputs.
87 *
88 * Overall outline of ufs_lookup:
89 *
90 * check accessibility of directory
91 * look for name in cache, if found, then if at end of path
92 * and deleting or creating, drop it, else return name
93 * search for name in directory, to found or notfound
94 * notfound:
95 * if creating, return locked directory, leaving info on available slots
96 * else return error
97 * found:
98 * if at end of path and deleting, return information to allow delete
99 * if at end of path and rewriting (RENAME and LOCKPARENT), lock target
100 * inode and return info to allow rewrite
101 * if not at end, add name to cache; if at end and neither creating
102 * nor deleting, add name to cache
103 */
104 int
105 ufs_lookup(void *v)
106 {
107 struct vop_lookup_args *ap = v;
108 struct vnode *vdp; /* vnode for directory being searched */
109 struct inode *dp; /* inode for directory being searched */
110 struct buf *bp; /* a buffer of directory entries */
111 struct direct *ep; /* the current directory entry */
112 int entryoffsetinblock; /* offset of ep in bp's buffer */
113 enum {NONE, COMPACT, FOUND} slotstatus;
114 doff_t slotoffset; /* offset of area with free space */
115 int slotsize; /* size of area at slotoffset */
116 int slotfreespace; /* amount of space free in slot */
117 int slotneeded; /* size of the entry we're seeking */
118 int numdirpasses; /* strategy for directory search */
119 doff_t endsearch; /* offset to end directory search */
120 doff_t prevoff; /* prev entry dp->i_offset */
121 struct vnode *pdp; /* saved dp during symlink work */
122 struct vnode *tdp; /* returned by VFS_VGET */
123 doff_t enduseful; /* pointer past last used dir slot */
124 u_long bmask; /* block offset mask */
125 int lockparent; /* 1 => lockparent flag is set */
126 int wantparent; /* 1 => wantparent or lockparent flag */
127 int namlen, error;
128 struct vnode **vpp = ap->a_vpp;
129 struct componentname *cnp = ap->a_cnp;
130 struct ucred *cred = cnp->cn_cred;
131 int flags;
132 int nameiop = cnp->cn_nameiop;
133 struct proc *p = cnp->cn_proc;
134
135 cnp->cn_flags &= ~PDIRUNLOCK;
136 flags = cnp->cn_flags;
137
138 bp = NULL;
139 slotoffset = -1;
140 *vpp = NULL;
141 vdp = ap->a_dvp;
142 dp = VTOI(vdp);
143 lockparent = flags & LOCKPARENT;
144 wantparent = flags & (LOCKPARENT|WANTPARENT);
145
146 /*
147 * Check accessiblity of directory.
148 */
149 if ((DIP(dp, mode) & IFMT) != IFDIR)
150 return (ENOTDIR);
151 if ((error = VOP_ACCESS(vdp, VEXEC, cred, cnp->cn_proc)) != 0)
152 return (error);
153
154 if ((flags & ISLASTCN) && (vdp->v_mount->mnt_flag & MNT_RDONLY) &&
155 (cnp->cn_nameiop == DELETE || cnp->cn_nameiop == RENAME))
156 return (EROFS);
157
158 /*
159 * We now have a segment name to search for, and a directory to search.
160 *
161 * Before tediously performing a linear scan of the directory,
162 * check the name cache to see if the directory/name pair
163 * we are looking for is known already.
164 */
165 if ((error = cache_lookup(vdp, vpp, cnp)) >= 0)
166 return (error);
167
168 /*
169 * Suppress search for slots unless creating
170 * file and at end of pathname, in which case
171 * we watch for a place to put the new file in
172 * case it doesn't already exist.
173 */
174 slotstatus = FOUND;
175 slotfreespace = slotsize = slotneeded = 0;
176 if ((nameiop == CREATE || nameiop == RENAME) &&
177 (flags & ISLASTCN)) {
178 slotstatus = NONE;
179 slotneeded = (sizeof(struct direct) - MAXNAMLEN +
180 cnp->cn_namelen + 3) &~ 3;
181 }
182
183 /*
184 * If there is cached information on a previous search of
185 * this directory, pick up where we last left off.
186 * We cache only lookups as these are the most common
187 * and have the greatest payoff. Caching CREATE has little
188 * benefit as it usually must search the entire directory
189 * to determine that the entry does not exist. Caching the
190 * location of the last DELETE or RENAME has not reduced
191 * profiling time and hence has been removed in the interest
192 * of simplicity.
193 */
194 bmask = VFSTOUFS(vdp->v_mount)->um_mountp->mnt_stat.f_iosize - 1;
195
196 #ifdef UFS_DIRHASH
197 /*
198 * Use dirhash for fast operations on large directories. The logic
199 * to determine whether to hash the directory is contained within
200 * ufsdirhash_build(); a zero return means that it decided to hash
201 * this directory and it successfully built up the hash table.
202 */
203 if (ufsdirhash_build(dp) == 0) {
204 /* Look for a free slot if needed. */
205 enduseful = DIP(dp, size);
206 if (slotstatus != FOUND) {
207 slotoffset = ufsdirhash_findfree(dp, slotneeded,
208 &slotsize);
209 if (slotoffset >= 0) {
210 slotstatus = COMPACT;
211 enduseful = ufsdirhash_enduseful(dp);
212 if (enduseful < 0)
213 enduseful = DIP(dp, size);
214 }
215 }
216 /* Look up the component. */
217 numdirpasses = 1;
218 entryoffsetinblock = 0; /* silence compiler warning */
219 switch (ufsdirhash_lookup(dp, cnp->cn_nameptr, cnp->cn_namelen,
220 &dp->i_offset, &bp, nameiop == DELETE ? &prevoff : NULL)) {
221 case 0:
222 ep = (struct direct *)((char *)bp->b_data +
223 (dp->i_offset & bmask));
224 goto foundentry;
225 case ENOENT:
226 #define roundup2(x, y) (((x)+((y)-1))&(~((y)-1))) /* if y is powers of two */
227 dp->i_offset = roundup2(DIP(dp, size), DIRBLKSIZ);
228 goto notfound;
229 default:
230 /* Something failed; just do a linear search. */
231 break;
232 }
233 }
234 #endif /* UFS_DIRHASH */
235
236 if (nameiop != LOOKUP || dp->i_diroff == 0 ||
237 dp->i_diroff >= DIP(dp, size)) {
238 entryoffsetinblock = 0;
239 dp->i_offset = 0;
240 numdirpasses = 1;
241 } else {
242 dp->i_offset = dp->i_diroff;
243 if ((entryoffsetinblock = dp->i_offset & bmask) &&
244 (error = UFS_BUFATOFF(dp, (off_t)dp->i_offset, NULL, &bp)))
245 return (error);
246 numdirpasses = 2;
247 nchstats.ncs_2passes++;
248 }
249 prevoff = dp->i_offset;
250 endsearch = roundup(DIP(dp, size), DIRBLKSIZ);
251 enduseful = 0;
252
253 searchloop:
254 while (dp->i_offset < endsearch) {
255 /*
256 * If necessary, get the next directory block.
257 */
258 if ((dp->i_offset & bmask) == 0) {
259 if (bp != NULL)
260 brelse(bp);
261 error = UFS_BUFATOFF(dp, (off_t)dp->i_offset, NULL,
262 &bp);
263 if (error)
264 return (error);
265 entryoffsetinblock = 0;
266 }
267 /*
268 * If still looking for a slot, and at a DIRBLKSIZE
269 * boundary, have to start looking for free space again.
270 */
271 if (slotstatus == NONE &&
272 (entryoffsetinblock & (DIRBLKSIZ - 1)) == 0) {
273 slotoffset = -1;
274 slotfreespace = 0;
275 }
276 /*
277 * Get pointer to next entry.
278 * Full validation checks are slow, so we only check
279 * enough to insure forward progress through the
280 * directory. Complete checks can be run by patching
281 * "dirchk" to be true.
282 */
283 ep = (struct direct *)((char *)bp->b_data + entryoffsetinblock);
284 if (ep->d_reclen == 0 ||
285 (dirchk && ufs_dirbadentry(vdp, ep, entryoffsetinblock))) {
286 int i;
287
288 ufs_dirbad(dp, dp->i_offset, "mangled entry");
289 i = DIRBLKSIZ - (entryoffsetinblock & (DIRBLKSIZ - 1));
290 dp->i_offset += i;
291 entryoffsetinblock += i;
292 continue;
293 }
294
295 /*
296 * If an appropriate sized slot has not yet been found,
297 * check to see if one is available. Also accumulate space
298 * in the current block so that we can determine if
299 * compaction is viable.
300 */
301 if (slotstatus != FOUND) {
302 int size = ep->d_reclen;
303
304 if (ep->d_ino != 0)
305 size -= DIRSIZ(FSFMT(vdp), ep);
306 if (size > 0) {
307 if (size >= slotneeded) {
308 slotstatus = FOUND;
309 slotoffset = dp->i_offset;
310 slotsize = ep->d_reclen;
311 } else if (slotstatus == NONE) {
312 slotfreespace += size;
313 if (slotoffset == -1)
314 slotoffset = dp->i_offset;
315 if (slotfreespace >= slotneeded) {
316 slotstatus = COMPACT;
317 slotsize = dp->i_offset +
318 ep->d_reclen - slotoffset;
319 }
320 }
321 }
322 }
323
324 /*
325 * Check for a name match.
326 */
327 if (ep->d_ino) {
328 # if (BYTE_ORDER == LITTLE_ENDIAN)
329 if (vdp->v_mount->mnt_maxsymlinklen > 0)
330 namlen = ep->d_namlen;
331 else
332 namlen = ep->d_type;
333 # else
334 namlen = ep->d_namlen;
335 # endif
336 if (namlen == cnp->cn_namelen &&
337 !bcmp(cnp->cn_nameptr, ep->d_name,
338 (unsigned)namlen)) {
339 #ifdef UFS_DIRHASH
340 foundentry:
341 #endif
342 /*
343 * Save directory entry's inode number and
344 * reclen in ndp->ni_ufs area, and release
345 * directory buffer.
346 */
347 dp->i_ino = ep->d_ino;
348 dp->i_reclen = ep->d_reclen;
349 goto found;
350 }
351 }
352 prevoff = dp->i_offset;
353 dp->i_offset += ep->d_reclen;
354 entryoffsetinblock += ep->d_reclen;
355 if (ep->d_ino)
356 enduseful = dp->i_offset;
357 }
358 #ifdef UFS_DIRHASH
359 notfound:
360 #endif
361 /*
362 * If we started in the middle of the directory and failed
363 * to find our target, we must check the beginning as well.
364 */
365 if (numdirpasses == 2) {
366 numdirpasses--;
367 dp->i_offset = 0;
368 endsearch = dp->i_diroff;
369 goto searchloop;
370 }
371 if (bp != NULL)
372 brelse(bp);
373 /*
374 * If creating, and at end of pathname and current
375 * directory has not been removed, then can consider
376 * allowing file to be created.
377 */
378 if ((nameiop == CREATE || nameiop == RENAME) &&
379 (flags & ISLASTCN) && dp->i_effnlink != 0) {
380 /*
381 * Access for write is interpreted as allowing
382 * creation of files in the directory.
383 */
384 error = VOP_ACCESS(vdp, VWRITE, cred, cnp->cn_proc);
385 if (error)
386 return (error);
387 /*
388 * Return an indication of where the new directory
389 * entry should be put. If we didn't find a slot,
390 * then set dp->i_count to 0 indicating
391 * that the new slot belongs at the end of the
392 * directory. If we found a slot, then the new entry
393 * can be put in the range from dp->i_offset to
394 * dp->i_offset + dp->i_count.
395 */
396 if (slotstatus == NONE) {
397 dp->i_offset = roundup(DIP(dp, size), DIRBLKSIZ);
398 dp->i_count = 0;
399 enduseful = dp->i_offset;
400 } else if (nameiop == DELETE) {
401 dp->i_offset = slotoffset;
402 if ((dp->i_offset & (DIRBLKSIZ - 1)) == 0)
403 dp->i_count = 0;
404 else
405 dp->i_count = dp->i_offset - prevoff;
406 } else {
407 dp->i_offset = slotoffset;
408 dp->i_count = slotsize;
409 if (enduseful < slotoffset + slotsize)
410 enduseful = slotoffset + slotsize;
411 }
412 dp->i_endoff = roundup(enduseful, DIRBLKSIZ);
413 /*
414 * We return with the directory locked, so that
415 * the parameters we set up above will still be
416 * valid if we actually decide to do a direnter().
417 * We return ni_vp == NULL to indicate that the entry
418 * does not currently exist; we leave a pointer to
419 * the (locked) directory inode in ndp->ni_dvp.
420 * The pathname buffer is saved so that the name
421 * can be obtained later.
422 *
423 * NB - if the directory is unlocked, then this
424 * information cannot be used.
425 */
426 cnp->cn_flags |= SAVENAME;
427 if (!lockparent) {
428 VOP_UNLOCK(vdp, 0, p);
429 cnp->cn_flags |= PDIRUNLOCK;
430 }
431 return (EJUSTRETURN);
432 }
433 /*
434 * Insert name into cache (as non-existent) if appropriate.
435 */
436 if ((cnp->cn_flags & MAKEENTRY) && nameiop != CREATE)
437 cache_enter(vdp, *vpp, cnp);
438 return (ENOENT);
439
440 found:
441 if (numdirpasses == 2)
442 nchstats.ncs_pass2++;
443 /*
444 * Check that directory length properly reflects presence
445 * of this entry.
446 */
447 if (dp->i_offset + DIRSIZ(FSFMT(vdp), ep) > DIP(dp, size)) {
448 ufs_dirbad(dp, dp->i_offset, "i_ffs_size too small");
449 DIP_ASSIGN(dp, size, dp->i_offset + DIRSIZ(FSFMT(vdp), ep));
450 dp->i_flag |= IN_CHANGE | IN_UPDATE;
451 }
452 brelse(bp);
453
454 /*
455 * Found component in pathname.
456 * If the final component of path name, save information
457 * in the cache as to where the entry was found.
458 */
459 if ((flags & ISLASTCN) && nameiop == LOOKUP)
460 dp->i_diroff = dp->i_offset &~ (DIRBLKSIZ - 1);
461
462 /*
463 * If deleting, and at end of pathname, return
464 * parameters which can be used to remove file.
465 * If the wantparent flag isn't set, we return only
466 * the directory (in ndp->ni_dvp), otherwise we go
467 * on and lock the inode, being careful with ".".
468 */
469 if (nameiop == DELETE && (flags & ISLASTCN)) {
470 /*
471 * Write access to directory required to delete files.
472 */
473 error = VOP_ACCESS(vdp, VWRITE, cred, cnp->cn_proc);
474 if (error)
475 return (error);
476 /*
477 * Return pointer to current entry in dp->i_offset,
478 * and distance past previous entry (if there
479 * is a previous entry in this block) in dp->i_count.
480 * Save directory inode pointer in ndp->ni_dvp for dirremove().
481 */
482 if ((dp->i_offset & (DIRBLKSIZ - 1)) == 0)
483 dp->i_count = 0;
484 else
485 dp->i_count = dp->i_offset - prevoff;
486 if (dp->i_number == dp->i_ino) {
487 VREF(vdp);
488 *vpp = vdp;
489 return (0);
490 }
491 error = VFS_VGET(vdp->v_mount, dp->i_ino, &tdp);
492 if (error)
493 return (error);
494 /*
495 * If directory is "sticky", then user must own
496 * the directory, or the file in it, else she
497 * may not delete it (unless she's root). This
498 * implements append-only directories.
499 */
500 if ((DIP(dp, mode) & ISVTX) &&
501 cred->cr_uid != 0 &&
502 cred->cr_uid != DIP(dp, uid) &&
503 DIP(VTOI(tdp), uid) != cred->cr_uid) {
504 vput(tdp);
505 return (EPERM);
506 }
507 *vpp = tdp;
508 if (!lockparent) {
509 VOP_UNLOCK(vdp, 0, p);
510 cnp->cn_flags |= PDIRUNLOCK;
511 }
512 return (0);
513 }
514
515 /*
516 * If rewriting (RENAME), return the inode and the
517 * information required to rewrite the present directory
518 * Must get inode of directory entry to verify it's a
519 * regular file, or empty directory.
520 */
521 if (nameiop == RENAME && wantparent &&
522 (flags & ISLASTCN)) {
523 error = VOP_ACCESS(vdp, VWRITE, cred, cnp->cn_proc);
524 if (error)
525 return (error);
526 /*
527 * Careful about locking second inode.
528 * This can only occur if the target is ".".
529 */
530 if (dp->i_number == dp->i_ino)
531 return (EISDIR);
532 error = VFS_VGET(vdp->v_mount, dp->i_ino, &tdp);
533 if (error)
534 return (error);
535 *vpp = tdp;
536 cnp->cn_flags |= SAVENAME;
537 if (!lockparent) {
538 VOP_UNLOCK(vdp, 0, p);
539 cnp->cn_flags |= PDIRUNLOCK;
540 }
541 return (0);
542 }
543
544 /*
545 * Step through the translation in the name. We do not `vput' the
546 * directory because we may need it again if a symbolic link
547 * is relative to the current directory. Instead we save it
548 * unlocked as "pdp". We must get the target inode before unlocking
549 * the directory to insure that the inode will not be removed
550 * before we get it. We prevent deadlock by always fetching
551 * inodes from the root, moving down the directory tree. Thus
552 * when following backward pointers ".." we must unlock the
553 * parent directory before getting the requested directory.
554 * There is a potential race condition here if both the current
555 * and parent directories are removed before the VFS_VGET for the
556 * inode associated with ".." returns. We hope that this occurs
557 * infrequently since we cannot avoid this race condition without
558 * implementing a sophisticated deadlock detection algorithm.
559 * Note also that this simple deadlock detection scheme will not
560 * work if the file system has any hard links other than ".."
561 * that point backwards in the directory structure.
562 */
563 pdp = vdp;
564 if (flags & ISDOTDOT) {
565 VOP_UNLOCK(pdp, 0, p); /* race to get the inode */
566 cnp->cn_flags |= PDIRUNLOCK;
567 error = VFS_VGET(vdp->v_mount, dp->i_ino, &tdp);
568 if (error) {
569 if (vn_lock(pdp, LK_EXCLUSIVE | LK_RETRY, p) == 0)
570 cnp->cn_flags &= ~PDIRUNLOCK;
571 return (error);
572 }
573 if (lockparent && (flags & ISLASTCN)) {
574 if ((error = vn_lock(pdp, LK_EXCLUSIVE, p))) {
575 vput(tdp);
576 return (error);
577 }
578 cnp->cn_flags &= ~PDIRUNLOCK;
579 }
580 *vpp = tdp;
581 } else if (dp->i_number == dp->i_ino) {
582 VREF(vdp); /* we want ourself, ie "." */
583 *vpp = vdp;
584 } else {
585 error = VFS_VGET(vdp->v_mount, dp->i_ino, &tdp);
586 if (error)
587 return (error);
588 if (!lockparent || !(flags & ISLASTCN)) {
589 VOP_UNLOCK(pdp, 0, p);
590 cnp->cn_flags |= PDIRUNLOCK;
591 }
592 *vpp = tdp;
593 }
594
595 /*
596 * Insert name into cache if appropriate.
597 */
598 if (cnp->cn_flags & MAKEENTRY)
599 cache_enter(vdp, *vpp, cnp);
600 return (0);
601 }
602
603 void
604 ufs_dirbad(struct inode *ip, doff_t offset, char *how)
605 {
606 struct mount *mp;
607
608 mp = ITOV(ip)->v_mount;
609 (void)printf("%s: bad dir ino %d at offset %d: %s\n",
610 mp->mnt_stat.f_mntonname, ip->i_number, offset, how);
611 if ((mp->mnt_stat.f_flags & MNT_RDONLY) == 0)
612 panic("bad dir");
613 }
614
615 /*
616 * Do consistency checking on a directory entry:
617 * record length must be multiple of 4
618 * entry must fit in rest of its DIRBLKSIZ block
619 * record must be large enough to contain entry
620 * name is not longer than MAXNAMLEN
621 * name must be as long as advertised, and null terminated
622 */
623 int
624 ufs_dirbadentry(struct vnode *dp, struct direct *ep, int entryoffsetinblock)
625 {
626 int i;
627 int namlen;
628
629 # if (BYTE_ORDER == LITTLE_ENDIAN)
630 if (dp->v_mount->mnt_maxsymlinklen > 0)
631 namlen = ep->d_namlen;
632 else
633 namlen = ep->d_type;
634 # else
635 namlen = ep->d_namlen;
636 # endif
637 if ((ep->d_reclen & 0x3) != 0 ||
638 ep->d_reclen > DIRBLKSIZ - (entryoffsetinblock & (DIRBLKSIZ - 1)) ||
639 ep->d_reclen < DIRSIZ(FSFMT(dp), ep) || namlen > MAXNAMLEN) {
640 /*return (1); */
641 printf("First bad\n");
642 goto bad;
643 }
644 if (ep->d_ino == 0)
645 return (0);
646 for (i = 0; i < namlen; i++)
647 if (ep->d_name[i] == '\0') {
648 /*return (1); */
649 printf("Second bad\n");
650 goto bad;
651 }
652 if (ep->d_name[i])
653 goto bad;
654 return (0);
655 bad:
656 return (1);
657 }
658
659 /*
660 * Construct a new directory entry after a call to namei, using the
661 * parameters that it left in the componentname argument cnp. The
662 * argument ip is the inode to which the new directory entry will refer.
663 */
664 void
665 ufs_makedirentry(struct inode *ip, struct componentname *cnp,
666 struct direct *newdirp)
667 {
668 #ifdef DIAGNOSTIC
669 if ((cnp->cn_flags & SAVENAME) == 0)
670 panic("ufs_makedirentry: missing name");
671 #endif
672 newdirp->d_ino = ip->i_number;
673 newdirp->d_namlen = cnp->cn_namelen;
674 bcopy(cnp->cn_nameptr, newdirp->d_name, (unsigned)cnp->cn_namelen + 1);
675 if (ITOV(ip)->v_mount->mnt_maxsymlinklen > 0)
676 newdirp->d_type = IFTODT(DIP(ip, mode));
677 else {
678 newdirp->d_type = 0;
679 # if (BYTE_ORDER == LITTLE_ENDIAN)
680 { u_char tmp = newdirp->d_namlen;
681 newdirp->d_namlen = newdirp->d_type;
682 newdirp->d_type = tmp; }
683 # endif
684 }
685 }
686
687 /*
688 * Write a directory entry after a call to namei, using the parameters
689 * that it left in nameidata. The argument dirp is the new directory
690 * entry contents. Dvp is a pointer to the directory to be written,
691 * which was left locked by namei. Remaining parameters (dp->i_offset,
692 * dp->i_count) indicate how the space for the new entry is to be obtained.
693 * Non-null bp indicates that a directory is being created (for the
694 * soft dependency code).
695 */
696 int
697 ufs_direnter(struct vnode *dvp, struct vnode *tvp, struct direct *dirp,
698 struct componentname *cnp, struct buf *newdirbp)
699 {
700 struct ucred *cr;
701 struct proc *p;
702 int newentrysize;
703 struct inode *dp;
704 struct buf *bp;
705 u_int dsize;
706 struct direct *ep, *nep;
707 int error, ret, blkoff, loc, spacefree, flags;
708 char *dirbuf;
709
710 error = 0;
711 cr = cnp->cn_cred;
712 p = cnp->cn_proc;
713 dp = VTOI(dvp);
714 newentrysize = DIRSIZ(FSFMT(dvp), dirp);
715
716 if (dp->i_count == 0) {
717 /*
718 * If dp->i_count is 0, then namei could find no
719 * space in the directory. Here, dp->i_offset will
720 * be on a directory block boundary and we will write the
721 * new entry into a fresh block.
722 */
723 if (dp->i_offset & (DIRBLKSIZ - 1))
724 panic("ufs_direnter: newblk");
725 flags = B_CLRBUF;
726 if (!DOINGSOFTDEP(dvp))
727 flags |= B_SYNC;
728 if ((error = UFS_BUF_ALLOC(dp, (off_t)dp->i_offset, DIRBLKSIZ,
729 cr, flags, &bp)) != 0) {
730 if (DOINGSOFTDEP(dvp) && newdirbp != NULL)
731 bdwrite(newdirbp);
732 return (error);
733 }
734 DIP_ASSIGN(dp, size, dp->i_offset + DIRBLKSIZ);
735 dp->i_flag |= IN_CHANGE | IN_UPDATE;
736 uvm_vnp_setsize(dvp, DIP(dp, size));
737 dirp->d_reclen = DIRBLKSIZ;
738 blkoff = dp->i_offset &
739 (VFSTOUFS(dvp->v_mount)->um_mountp->mnt_stat.f_iosize - 1);
740 bcopy((caddr_t)dirp, (caddr_t)bp->b_data + blkoff,newentrysize);
741
742 #ifdef UFS_DIRHASH
743 if (dp->i_dirhash != NULL) {
744 ufsdirhash_newblk(dp, dp->i_offset);
745 ufsdirhash_add(dp, dirp, dp->i_offset);
746 ufsdirhash_checkblock(dp, (char *)bp->b_data + blkoff,
747 dp->i_offset);
748 }
749 #endif
750
751 if (DOINGSOFTDEP(dvp)) {
752 /*
753 * Ensure that the entire newly allocated block is a
754 * valid directory so that future growth within the
755 * block does not have to ensure that the block is
756 * written before the inode.
757 */
758 blkoff += DIRBLKSIZ;
759 while (blkoff < bp->b_bcount) {
760 ((struct direct *)
761 (bp->b_data + blkoff))->d_reclen = DIRBLKSIZ;
762 blkoff += DIRBLKSIZ;
763 }
764 if (softdep_setup_directory_add(bp, dp, dp->i_offset,
765 dirp->d_ino, newdirbp, 1) == 0) {
766 bdwrite(bp);
767 return (UFS_UPDATE(dp, 0));
768 }
769 /* We have just allocated a directory block in an
770 * indirect block. Rather than tracking when it gets
771 * claimed by the inode, we simply do a VOP_FSYNC
772 * now to ensure that it is there (in case the user
773 * does a future fsync). Note that we have to unlock
774 * the inode for the entry that we just entered, as
775 * the VOP_FSYNC may need to lock other inodes which
776 * can lead to deadlock if we also hold a lock on
777 * the newly entered node.
778 */
779 if ((error = VOP_BWRITE(bp)))
780 return (error);
781 if (tvp != NULL)
782 VOP_UNLOCK(tvp, 0, p);
783 error = VOP_FSYNC(dvp, p->p_ucred, MNT_WAIT, p);
784 if (tvp != NULL)
785 vn_lock(tvp, LK_EXCLUSIVE | LK_RETRY, p);
786 return (error);
787 }
788 error = VOP_BWRITE(bp);
789 ret = UFS_UPDATE(dp, !DOINGSOFTDEP(dvp));
790 if (error == 0)
791 return (ret);
792 return (error);
793 }
794
795 /*
796 * If dp->i_count is non-zero, then namei found space for the new
797 * entry in the range dp->i_offset to dp->i_offset + dp->i_count
798 * in the directory. To use this space, we may have to compact
799 * the entries located there, by copying them together towards the
800 * beginning of the block, leaving the free space in one usable
801 * chunk at the end.
802 */
803
804 /*
805 * Increase size of directory if entry eats into new space.
806 * This should never push the size past a new multiple of
807 * DIRBLKSIZE.
808 *
809 * N.B. - THIS IS AN ARTIFACT OF 4.2 AND SHOULD NEVER HAPPEN.
810 */
811 if (dp->i_offset + dp->i_count > DIP(dp, size))
812 DIP_ASSIGN(dp, size, dp->i_offset + dp->i_count);
813 /*
814 * Get the block containing the space for the new directory entry.
815 */
816 if ((error = UFS_BUFATOFF(dp, (off_t)dp->i_offset, &dirbuf, &bp))
817 != 0) {
818 if (DOINGSOFTDEP(dvp) && newdirbp != NULL)
819 bdwrite(newdirbp);
820 return (error);
821 }
822 /*
823 * Find space for the new entry. In the simple case, the entry at
824 * offset base will have the space. If it does not, then namei
825 * arranged that compacting the region dp->i_offset to
826 * dp->i_offset + dp->i_count would yield the space.
827 */
828 ep = (struct direct *)dirbuf;
829 dsize = ep->d_ino ? DIRSIZ(FSFMT(dvp), ep) : 0;
830 spacefree = ep->d_reclen - dsize;
831 for (loc = ep->d_reclen; loc < dp->i_count; ) {
832 nep = (struct direct *)(dirbuf + loc);
833
834 /* Trim the existing slot (NB: dsize may be zero). */
835 ep->d_reclen = dsize;
836 ep = (struct direct *)((char *)ep + dsize);
837
838 /* Read nep->d_reclen now as the bcopy() may clobber it. */
839 loc += nep->d_reclen;
840 if (nep->d_ino == 0) {
841 /*
842 * A mid-block unused entry. Such entries are
843 * never created by the kernel, but fsck_ffs
844 * can create them (and it doesn't fix them).
845 *
846 * Add up the free space, and initialise the
847 * relocated entry since we don't bcopy it.
848 */
849 spacefree += nep->d_reclen;
850 ep->d_ino = 0;
851 dsize = 0;
852 continue;
853 }
854 dsize = DIRSIZ(FSFMT(dvp), nep);
855 spacefree += nep->d_reclen - dsize;
856 #ifdef UFS_DIRHASH
857 if (dp->i_dirhash != NULL)
858 ufsdirhash_move(dp, nep,
859 dp->i_offset + ((char *)nep - dirbuf),
860 dp->i_offset + ((char *)ep - dirbuf));
861 #endif
862 if (DOINGSOFTDEP(dvp))
863 softdep_change_directoryentry_offset(dp, dirbuf,
864 (caddr_t)nep, (caddr_t)ep, dsize);
865 else
866 bcopy((caddr_t)nep, (caddr_t)ep, dsize);
867 }
868 /*
869 * Here, `ep' points to a directory entry containing `dsize' in-use
870 * bytes followed by `spacefree' unused bytes. If ep->d_ino == 0,
871 * then the entry is completely unused (dsize == 0). The value
872 * of ep->d_reclen is always indeterminate.
873 *
874 * Update the pointer fields in the previous entry (if any),
875 * copy in the new entry, and write out the block.
876 */
877 if (ep->d_ino == 0) {
878 if (spacefree + dsize < newentrysize)
879 panic("ufs_direnter: compact1");
880 dirp->d_reclen = spacefree + dsize;
881 } else {
882 if (spacefree < newentrysize)
883 panic("ufs_direnter: compact2");
884 dirp->d_reclen = spacefree;
885 ep->d_reclen = dsize;
886 ep = (struct direct *)((char *)ep + dsize);
887 }
888
889 #ifdef UFS_DIRHASH
890 if (dp->i_dirhash != NULL && (ep->d_ino == 0 ||
891 dirp->d_reclen == spacefree))
892 ufsdirhash_add(dp, dirp, dp->i_offset + ((char *)ep - dirbuf));
893 #endif
894 bcopy((caddr_t)dirp, (caddr_t)ep, (u_int)newentrysize);
895 #ifdef UFS_DIRHASH
896 if (dp->i_dirhash != NULL)
897 ufsdirhash_checkblock(dp, dirbuf -
898 (dp->i_offset & (DIRBLKSIZ - 1)),
899 dp->i_offset & ~(DIRBLKSIZ - 1));
900 #endif
901
902 if (DOINGSOFTDEP(dvp)) {
903 (void)softdep_setup_directory_add(bp, dp,
904 dp->i_offset + (caddr_t)ep - dirbuf,
905 dirp->d_ino, newdirbp, 0);
906 bdwrite(bp);
907 } else {
908 error = VOP_BWRITE(bp);
909 }
910 dp->i_flag |= IN_CHANGE | IN_UPDATE;
911
912 /*
913 * If all went well, and the directory can be shortened, proceed
914 * with the truncation. Note that we have to unlock the inode for
915 * the entry that we just entered, as the truncation may need to
916 * lock other inodes which can lead to deadlock if we also hold a
917 * lock on the newly entered node.
918 */
919
920 if (error == 0 && dp->i_endoff && dp->i_endoff < DIP(dp, size)) {
921 if (tvp != NULL)
922 VOP_UNLOCK(tvp, 0, p);
923 #ifdef UFS_DIRHASH
924 if (dp->i_dirhash != NULL)
925 ufsdirhash_dirtrunc(dp, dp->i_endoff);
926 #endif
927
928
929 error = UFS_TRUNCATE(dp, (off_t)dp->i_endoff, IO_SYNC, cr);
930
931 if (tvp != NULL)
932 vn_lock(tvp, LK_EXCLUSIVE | LK_RETRY, p);
933 }
934 return (error);
935 }
936
937 /*
938 * Remove a directory entry after a call to namei, using
939 * the parameters which it left in nameidata. The entry
940 * dp->i_offset contains the offset into the directory of the
941 * entry to be eliminated. The dp->i_count field contains the
942 * size of the previous record in the directory. If this
943 * is 0, the first entry is being deleted, so we need only
944 * zero the inode number to mark the entry as free. If the
945 * entry is not the first in the directory, we must reclaim
946 * the space of the now empty record by adding the record size
947 * to the size of the previous entry.
948 */
949 int
950 ufs_dirremove(struct vnode *dvp, struct inode *ip, int flags, int isrmdir)
951 {
952 struct inode *dp;
953 struct direct *ep;
954 struct buf *bp;
955 int error;
956
957 dp = VTOI(dvp);
958
959 if ((error = UFS_BUFATOFF(dp,
960 (off_t)(dp->i_offset - dp->i_count), (char **)&ep, &bp)) != 0)
961 return (error);
962 #ifdef UFS_DIRHASH
963 /*
964 * Remove the dirhash entry. This is complicated by the fact
965 * that `ep' is the previous entry when dp->i_count != 0.
966 */
967 if (dp->i_dirhash != NULL)
968 ufsdirhash_remove(dp, (dp->i_count == 0) ? ep :
969 (struct direct *)((char *)ep + ep->d_reclen), dp->i_offset);
970 #endif
971
972 if (dp->i_count == 0) {
973 /*
974 * First entry in block: set d_ino to zero.
975 */
976 ep->d_ino = 0;
977 } else {
978 /*
979 * Collapse new free space into previous entry.
980 */
981 ep->d_reclen += dp->i_reclen;
982 }
983 #ifdef UFS_DIRHASH
984 if (dp->i_dirhash != NULL)
985 ufsdirhash_checkblock(dp, (char *)ep -
986 ((dp->i_offset - dp->i_count) & (DIRBLKSIZ - 1)),
987 dp->i_offset & ~(DIRBLKSIZ - 1));
988 #endif
989 if (DOINGSOFTDEP(dvp)) {
990 if (ip) {
991 ip->i_effnlink--;
992 softdep_change_linkcnt(ip, 0);
993 softdep_setup_remove(bp, dp, ip, isrmdir);
994 }
995 if (softdep_slowdown(dvp)) {
996 error = bwrite(bp);
997 } else {
998 bdwrite(bp);
999 error = 0;
1000 }
1001 } else {
1002 if (ip) {
1003 ip->i_effnlink--;
1004 DIP_ADD(ip, nlink, -1);
1005 ip->i_flag |= IN_CHANGE;
1006 }
1007 if (DOINGASYNC(dvp) && dp->i_count != 0) {
1008 bdwrite(bp);
1009 error = 0;
1010 } else
1011 error = bwrite(bp);
1012 }
1013 dp->i_flag |= IN_CHANGE | IN_UPDATE;
1014 return (error);
1015 }
1016
1017 /*
1018 * Rewrite an existing directory entry to point at the inode
1019 * supplied. The parameters describing the directory entry are
1020 * set up by a call to namei.
1021 */
1022 int
1023 ufs_dirrewrite(struct inode *dp, struct inode *oip, ino_t newinum, int newtype,
1024 int isrmdir)
1025 {
1026 struct buf *bp;
1027 struct direct *ep;
1028 struct vnode *vdp = ITOV(dp);
1029 int error;
1030
1031 error = UFS_BUFATOFF(dp, (off_t)dp->i_offset, (char **)&ep, &bp);
1032 if (error)
1033 return (error);
1034 ep->d_ino = newinum;
1035 if (vdp->v_mount->mnt_maxsymlinklen > 0)
1036 ep->d_type = newtype;
1037 oip->i_effnlink--;
1038 if (DOINGSOFTDEP(vdp)) {
1039 softdep_change_linkcnt(oip, 0);
1040 softdep_setup_directory_change(bp, dp, oip, newinum, isrmdir);
1041 bdwrite(bp);
1042 } else {
1043 DIP_ADD(oip, nlink, -1);
1044 oip->i_flag |= IN_CHANGE;
1045 if (DOINGASYNC(vdp)) {
1046 bdwrite(bp);
1047 error = 0;
1048 } else {
1049 error = VOP_BWRITE(bp);
1050 }
1051 }
1052 dp->i_flag |= IN_CHANGE | IN_UPDATE;
1053 return (error);
1054 }
1055
1056 /*
1057 * Check if a directory is empty or not.
1058 * Inode supplied must be locked.
1059 *
1060 * Using a struct dirtemplate here is not precisely
1061 * what we want, but better than using a struct direct.
1062 *
1063 * NB: does not handle corrupted directories.
1064 */
1065 int
1066 ufs_dirempty(struct inode *ip, ino_t parentino, struct ucred *cred)
1067 {
1068 off_t off, m;
1069 struct dirtemplate dbuf;
1070 struct direct *dp = (struct direct *)&dbuf;
1071 int error, namlen;
1072 size_t count;
1073 #define MINDIRSIZ (sizeof (struct dirtemplate) / 2)
1074
1075 m = DIP(ip, size);
1076 for (off = 0; off < m; off += dp->d_reclen) {
1077 error = vn_rdwr(UIO_READ, ITOV(ip), (caddr_t)dp, MINDIRSIZ, off,
1078 UIO_SYSSPACE, IO_NODELOCKED, cred, &count, (struct proc *)0);
1079 /*
1080 * Since we read MINDIRSIZ, residual must
1081 * be 0 unless we're at end of file.
1082 */
1083 if (error || count != 0)
1084 return (0);
1085 /* avoid infinite loops */
1086 if (dp->d_reclen == 0)
1087 return (0);
1088 /* skip empty entries */
1089 if (dp->d_ino == 0)
1090 continue;
1091 /* accept only "." and ".." */
1092 # if (BYTE_ORDER == LITTLE_ENDIAN)
1093 if (ITOV(ip)->v_mount->mnt_maxsymlinklen > 0)
1094 namlen = dp->d_namlen;
1095 else
1096 namlen = dp->d_type;
1097 # else
1098 namlen = dp->d_namlen;
1099 # endif
1100 if (namlen > 2)
1101 return (0);
1102 if (dp->d_name[0] != '.')
1103 return (0);
1104 /*
1105 * At this point namlen must be 1 or 2.
1106 * 1 implies ".", 2 implies ".." if second
1107 * char is also "."
1108 */
1109 if (namlen == 1 && dp->d_ino == ip->i_number)
1110 continue;
1111 if (dp->d_name[1] == '.' && dp->d_ino == parentino)
1112 continue;
1113 return (0);
1114 }
1115 return (1);
1116 }
1117
1118 /*
1119 * Check if source directory is in the path of the target directory.
1120 * Target is supplied locked, source is unlocked.
1121 * The target is always vput before returning.
1122 */
1123 int
1124 ufs_checkpath(struct inode *source, struct inode *target, struct ucred *cred)
1125 {
1126 struct vnode *vp;
1127 int error, rootino, namlen;
1128 struct dirtemplate dirbuf;
1129
1130 vp = ITOV(target);
1131 if (target->i_number == source->i_number) {
1132 error = EEXIST;
1133 goto out;
1134 }
1135 rootino = ROOTINO;
1136 error = 0;
1137 if (target->i_number == rootino)
1138 goto out;
1139
1140 for (;;) {
1141 if (vp->v_type != VDIR) {
1142 error = ENOTDIR;
1143 break;
1144 }
1145 error = vn_rdwr(UIO_READ, vp, (caddr_t)&dirbuf,
1146 sizeof (struct dirtemplate), (off_t)0, UIO_SYSSPACE,
1147 IO_NODELOCKED, cred, NULL, (struct proc *)0);
1148 if (error != 0)
1149 break;
1150 # if (BYTE_ORDER == LITTLE_ENDIAN)
1151 if (vp->v_mount->mnt_maxsymlinklen > 0)
1152 namlen = dirbuf.dotdot_namlen;
1153 else
1154 namlen = dirbuf.dotdot_type;
1155 # else
1156 namlen = dirbuf.dotdot_namlen;
1157 # endif
1158 if (namlen != 2 ||
1159 dirbuf.dotdot_name[0] != '.' ||
1160 dirbuf.dotdot_name[1] != '.') {
1161 error = ENOTDIR;
1162 break;
1163 }
1164 if (dirbuf.dotdot_ino == source->i_number) {
1165 error = EINVAL;
1166 break;
1167 }
1168 if (dirbuf.dotdot_ino == rootino)
1169 break;
1170 vput(vp);
1171 error = VFS_VGET(vp->v_mount, dirbuf.dotdot_ino, &vp);
1172 if (error) {
1173 vp = NULL;
1174 break;
1175 }
1176 }
1177
1178 out:
1179 if (error == ENOTDIR)
1180 printf("checkpath: .. not a directory\n");
1181 if (vp != NULL)
1182 vput(vp);
1183 return (error);
1184 }