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