X-Git-Url: https://git.subgeniuskitty.com/unix-history/.git/blobdiff_plain/6bd0bb9244463fd2114cd973f275c3753ca06608..658f5fdcff636c9b1a09f81684b1128aca389721:/usr/src/sys/kern/vfs_lookup.c diff --git a/usr/src/sys/kern/vfs_lookup.c b/usr/src/sys/kern/vfs_lookup.c index 9455339280..60e571f568 100644 --- a/usr/src/sys/kern/vfs_lookup.c +++ b/usr/src/sys/kern/vfs_lookup.c @@ -1,65 +1,135 @@ -/* vfs_lookup.c 4.19 82/07/25 */ - -#include "../h/param.h" -#include "../h/systm.h" -#include "../h/inode.h" -#include "../h/fs.h" -#include "../h/mount.h" -#include "../h/dir.h" -#include "../h/user.h" -#include "../h/buf.h" -#include "../h/conf.h" - -#ifdef EFS -extern int efs_major; +/* + * Copyright (c) 1982, 1986 Regents of the University of California. + * All rights reserved. The Berkeley software License Agreement + * specifies the terms and conditions for redistribution. + * + * @(#)vfs_lookup.c 7.6 (Berkeley) %G% + */ + +#include "param.h" +#include "systm.h" +#include "inode.h" +#include "fs.h" +#include "mount.h" +#include "dir.h" +#include "user.h" +#include "buf.h" +#include "conf.h" +#include "uio.h" +#include "kernel.h" +#include "malloc.h" +#ifdef KTRACE +#include "proc.h" +#include "ktrace.h" #endif -struct buf *batoffset(); +struct buf *blkatoff(); int dirchk = 1; + +/* + * Structures associated with name cacheing. + */ +#define NCHHASH 32 /* size of hash table */ + +#if ((NCHHASH)&((NCHHASH)-1)) != 0 +#define NHASH(h, i, d) ((unsigned)((h) + (i) + 13 * (int)(d)) % (NCHHASH)) +#else +#define NHASH(h, i, d) ((unsigned)((h) + (i) + 13 * (int)(d)) & ((NCHHASH)-1)) +#endif + +union nchash { + union nchash *nch_head[2]; + struct namecache *nch_chain[2]; +} nchash[NCHHASH]; +#define nch_forw nch_chain[0] +#define nch_back nch_chain[1] + +struct namecache *nchhead, **nchtail; /* LRU chain pointers */ +struct nchstats nchstats; /* cache effectiveness statistics */ + /* - * Convert a pathname into a pointer to a locked inode, - * with side effects usable in creating and removing files. + * Convert a pathname into a pointer to a locked inode. * This is a very central and rather complicated routine. + * If the file system is not maintained in a strict tree hierarchy, + * this can result in a deadlock situation (see comments in code below). + * + * The flag argument is LOOKUP, CREATE, or DELETE depending on whether + * the name is to be looked up, created, or deleted. When CREATE or + * DELETE is specified, information usable in creating or deleteing a + * directory entry is also calculated. If flag has LOCKPARENT or'ed + * into it and the target of the pathname exists, namei returns both + * the target and its parent directory locked. When creating and + * LOCKPARENT is specified, the target may not be ".". When deleting + * and LOCKPARENT is specified, the target may be ".", but the caller + * must check to insure it does an irele and iput instead of two iputs. + * + * The FOLLOW flag is set when symbolic links are to be followed + * when they occur at the end of the name translation process. + * Symbolic links are always followed for all other pathname + * components other than the last. * - * The func argument gives the routine which returns successive - * characters of the name to be translated. The flag - * argument is (0, 1, 2) depending on whether the name is to be - * (looked up, created, deleted). The follow argument is 1 when - * symbolic links are to be followed when they occur at the end of - * the name translation process. + * The segflg defines whether the name is to be copied from user + * space or kernel space. * - * Overall outline: + * Name caching works as follows: + * + * Names found by directory scans are retained in a cache + * for future reference. It is managed LRU, so frequently + * used names will hang around. Cache is indexed by hash value + * obtained from (ino,dev,name) where ino & dev refer to the + * directory containing name. + * + * For simplicity (and economy of storage), names longer than + * a maximum length of NCHNAMLEN are not cached; they occur + * infrequently in any case, and are almost never of interest. + * + * Upon reaching the last segment of a path, if the reference + * is for DELETE, or NOCACHE is set (rewrite), and the + * name is located in the cache, it will be dropped. + * + * Overall outline of namei: * * copy in name * get starting directory * dirloop: * check accessibility of directory * dirloop2: - * copy next component of name to u.u_dent + * copy next component of name to ndp->ni_dent * handle degenerate case where name is null string + * look for name in cache, if found, then if at end of path + * and deleting or creating, drop it, else to haveino * search for name in directory, to found or notfound * notfound: - * if creating, return locked inode, leaving information on avail. slots + * if creating, return locked directory, leaving info on avail. slots * else return error * found: * if at end of path and deleting, return information to allow delete + * if at end of path and rewriting (CREATE and LOCKPARENT), lock target + * inode and return info to allow rewrite * if .. and on mounted filesys, look in mount table for parent + * if not at end, add name to cache; if at end and neither creating + * nor deleting, add name to cache + * haveino: * if symbolic link, massage name in buffer and continue at dirloop * if more components of name, do next level at dirloop * return the answer as locked inode + * + * NOTE: (LOOKUP | LOCKPARENT) currently returns the parent inode, + * but unlocked. */ struct inode * -namei(func, flag, follow) - int (*func)(), flag, follow; +namei(ndp) + register struct nameidata *ndp; { register char *cp; /* pointer into pathname argument */ /* these variables refer to things which must be freed or unlocked */ register struct inode *dp = 0; /* the directory we are searching */ + register struct namecache *ncp; /* cache slot for entry */ register struct fs *fs; /* file system that directory is in */ register struct buf *bp = 0; /* a buffer of directory entries */ register struct direct *ep; /* the current directory entry */ int entryoffsetinblock; /* offset of ep in bp's buffer */ - register struct buf *nbp; /* buffer storing path name argument */ + register caddr_t nbp; /* buffer storing path name argument */ /* these variables hold information about the search for a slot */ enum {NONE, COMPACT, FOUND} slotstatus; int slotoffset = -1; /* offset of area with free space */ @@ -67,35 +137,48 @@ namei(func, flag, follow) int slotfreespace; /* amount of space free in slot */ int slotneeded; /* size of the entry we're seeking */ /* */ - int dirsize; - int prevoff; /* u.u_offset of previous entry */ + int numdirpasses; /* strategy for directory search */ + int endsearch; /* offset to end directory search */ + int prevoff; /* ndp->ni_offset of previous entry */ int nlink = 0; /* number of symbolic links taken */ struct inode *pdp; /* saved dp during symlink work */ - int i; + int error, i; + int lockparent; + int docache; /* == 0 do not cache last component */ + int makeentry; /* != 0 if name to be added to cache */ + unsigned hash; /* value of name hash for entry */ + union nchash *nhp; /* cache chain head for entry */ + int isdotdot; /* != 0 if current name is ".." */ + int flag; /* op ie, LOOKUP, CREATE, or DELETE */ + off_t enduseful; /* pointer past last used dir slot */ + lockparent = ndp->ni_nameiop & LOCKPARENT; + docache = (ndp->ni_nameiop & NOCACHE) ^ NOCACHE; + flag = ndp->ni_nameiop &~ (LOCKPARENT|NOCACHE|FOLLOW); + if (flag == DELETE || lockparent) + docache = 0; /* * Get a buffer for the name to be translated, and copy the * name into the buffer. */ - nbp = geteblk(MAXPATHLEN); - for (cp = nbp->b_un.b_addr; *cp = (*func)(); ) { - if ((*cp&0377) == ('/'|0200) || (*cp&0200) && flag != 2) { - u.u_error = EPERM; - goto bad; - } - cp++; - if (cp >= nbp->b_un.b_addr + MAXPATHLEN) { - u.u_error = ENOENT; - goto bad; - } - } - if (u.u_error) + MALLOC(nbp, caddr_t, MAXPATHLEN, M_NAMEI, M_WAITOK); + if (ndp->ni_segflg == UIO_SYSSPACE) + error = copystr(ndp->ni_dirp, nbp, MAXPATHLEN, (u_int *)0); + else + error = copyinstr(ndp->ni_dirp, nbp, MAXPATHLEN, (u_int *)0); + if (error) { + u.u_error = error; goto bad; + } +#ifdef KTRACE + if (KTRPOINT(u.u_procp, KTR_NAMEI)) + ktrnamei(u.u_procp->p_tracep, nbp); +#endif /* * Get starting directory. */ - cp = nbp->b_un.b_addr; + cp = nbp; if (*cp == '/') { while (*cp == '/') cp++; @@ -104,9 +187,10 @@ namei(func, flag, follow) } else dp = u.u_cdir; fs = dp->i_fs; - ilock(dp); + ILOCK(dp); dp->i_count++; - u.u_pdir = (struct inode *)0xc0000000; /* illegal */ + ndp->ni_pdir = (struct inode *)0xc0000000; /* illegal */ + ndp->ni_endoff = 0; /* * We come to dirloop to search a new directory. @@ -117,12 +201,6 @@ dirloop: /* * Check accessiblity of directory. */ -#ifdef EFS - if ((dp->i_mode & IFMT) == IFCHR && major(dp->i_rdev) == efs_major) { - brelse(nbp); - return(dp); - } -#endif if ((dp->i_mode&IFMT) != IFDIR) { u.u_error = ENOTDIR; goto bad; @@ -132,32 +210,184 @@ dirloop: dirloop2: /* - * Copy next component of name to u.u_dent. + * Copy next component of name to ndp->ni_dent. */ + hash = 0; for (i = 0; *cp != 0 && *cp != '/'; cp++) { if (i >= MAXNAMLEN) { - u.u_error = ENOENT; + u.u_error = ENAMETOOLONG; goto bad; } - u.u_dent.d_name[i++] = *cp; + if (*cp & 0200) + if ((*cp&0377) == ('/'|0200) || flag != DELETE) { + u.u_error = EINVAL; + goto bad; + } + ndp->ni_dent.d_name[i++] = *cp; + hash += (unsigned char)*cp * i; } - u.u_dent.d_namlen = i; - u.u_dent.d_name[i] = 0; + ndp->ni_dent.d_namlen = i; + ndp->ni_dent.d_name[i] = '\0'; + isdotdot = (i == 2 && + ndp->ni_dent.d_name[0] == '.' && ndp->ni_dent.d_name[1] == '.'); + makeentry = 1; + if (*cp == '\0' && docache == 0) + makeentry = 0; /* * Check for degenerate name (e.g. / or "") * which is a way of talking about a directory, * e.g. like "/." or ".". */ - if (u.u_dent.d_name[0] == 0) { - if (flag) { - u.u_error = ENOENT; + if (ndp->ni_dent.d_name[0] == '\0') { + if (flag != LOOKUP || lockparent) { + u.u_error = EISDIR; goto bad; } - brelse(nbp); + FREE(nbp, M_NAMEI); return (dp); } + /* + * Special handling for ".." allowing chdir out of mounted + * file system: indirect .. in root inode to reevaluate + * in directory file system was mounted on. + */ + if (isdotdot) { + for (;;) { + if (dp == u.u_rdir || dp == rootdir) { + ndp->ni_dent.d_ino = dp->i_number; + pdp = dp; + dp->i_count++; + goto haveino; + } + if (dp->i_number != ROOTINO) + break; + for (i = 1; i < NMOUNT; i++) { + if (mount[i].m_fs != NULL && + mount[i].m_dev == dp->i_dev) { + iput(dp); + dp = mount[i].m_inodp; + ILOCK(dp); + dp->i_count++; + fs = dp->i_fs; + break; + } + } + } + } + + /* + * We now have a segment name to search for, and a directory to search. + * + * Before tediously performing a linear scan of the directory, + * check the name cache to see if the directory/name pair + * we are looking for is known already. We don't do this + * if the segment name is long, simply so the cache can avoid + * holding long names (which would either waste space, or + * add greatly to the complexity). + */ + if (ndp->ni_dent.d_namlen > NCHNAMLEN) { + nchstats.ncs_long++; + makeentry = 0; + } else { + nhp = &nchash[NHASH(hash, dp->i_number, dp->i_dev)]; + for (ncp = nhp->nch_forw; ncp != (struct namecache *)nhp; + ncp = ncp->nc_forw) { + if (ncp->nc_ino == dp->i_number && + ncp->nc_dev == dp->i_dev && + ncp->nc_nlen == ndp->ni_dent.d_namlen && + !bcmp(ncp->nc_name, ndp->ni_dent.d_name, + (unsigned)ncp->nc_nlen)) + break; + } + if (ncp == (struct namecache *)nhp) { + nchstats.ncs_miss++; + ncp = NULL; + } else { + if (ncp->nc_id != ncp->nc_ip->i_id) + nchstats.ncs_falsehits++; + else if (!makeentry) + nchstats.ncs_badhits++; + else { + /* + * move this slot to end of LRU + * chain, if not already there + */ + if (ncp->nc_nxt) { + /* remove from LRU chain */ + *ncp->nc_prev = ncp->nc_nxt; + ncp->nc_nxt->nc_prev = ncp->nc_prev; + + /* and replace at end of it */ + ncp->nc_nxt = NULL; + ncp->nc_prev = nchtail; + *nchtail = ncp; + nchtail = &ncp->nc_nxt; + } + + /* + * Get the next inode in the path. + * See comment above other `IUNLOCK' code for + * an explaination of the locking protocol. + */ + pdp = dp; + if (!isdotdot || dp != u.u_rdir) + dp = ncp->nc_ip; + if (dp == NULL) + panic("namei: null cache ino"); + if (pdp == dp) + dp->i_count++; + else if (isdotdot) { + IUNLOCK(pdp); + igrab(dp); + } else { + igrab(dp); + IUNLOCK(pdp); + } + + /* + * Verify that the inode that we got + * did not change while we were waiting + * for it to be locked. + */ + if (ncp->nc_id != ncp->nc_ip->i_id) { + iput(dp); + ILOCK(pdp); + dp = pdp; + nchstats.ncs_falsehits++; + } else { + ndp->ni_dent.d_ino = dp->i_number; + /* ni_dent.d_reclen is garbage ... */ + nchstats.ncs_goodhits++; + goto haveino; + } + } + + /* + * Last component and we are renaming or deleting, + * the cache entry is invalid, or otherwise don't + * want cache entry to exist. + */ + /* remove from LRU chain */ + *ncp->nc_prev = ncp->nc_nxt; + if (ncp->nc_nxt) + ncp->nc_nxt->nc_prev = ncp->nc_prev; + else + nchtail = ncp->nc_prev; + remque(ncp); /* remove from hash chain */ + /* insert at head of LRU list (first to grab) */ + ncp->nc_nxt = nchhead; + ncp->nc_prev = &nchhead; + nchhead->nc_prev = &ncp->nc_nxt; + nchhead = ncp; + /* and make a dummy hash chain */ + ncp->nc_forw = ncp; + ncp->nc_back = ncp; + ncp = NULL; + } + } + /* * Suppress search for slots unless creating * file and at end of pathname, in which case @@ -165,55 +395,81 @@ dirloop2: * case it doesn't already exist. */ slotstatus = FOUND; - if (flag == 1 && *cp == 0) { + if (flag == CREATE && *cp == 0) { slotstatus = NONE; slotfreespace = 0; - slotneeded = DIRSIZ(&u.u_dent); + slotneeded = DIRSIZ(&ndp->ni_dent); + } + /* + * If this is the same directory that this process + * previously searched, pick up where we last left off. + * We cache only lookups as these are the most common + * and have the greatest payoff. Caching CREATE has little + * benefit as it usually must search the entire directory + * to determine that the entry does not exist. Caching the + * location of the last DELETE has not reduced profiling time + * and hence has been removed in the interest of simplicity. + */ + if (flag != LOOKUP || dp->i_number != u.u_ncache.nc_inumber || + dp->i_dev != u.u_ncache.nc_dev) { + ndp->ni_offset = 0; + numdirpasses = 1; + } else { + if (u.u_ncache.nc_prevoffset > dp->i_size) + u.u_ncache.nc_prevoffset = 0; + ndp->ni_offset = u.u_ncache.nc_prevoffset; + entryoffsetinblock = blkoff(fs, ndp->ni_offset); + if (entryoffsetinblock != 0) { + bp = blkatoff(dp, ndp->ni_offset, (char **)0); + if (bp == 0) + goto bad; + } + numdirpasses = 2; + nchstats.ncs_2passes++; } + endsearch = roundup(dp->i_size, DIRBLKSIZ); + enduseful = 0; - dirsize = roundup(dp->i_size, DIRBLKSIZ); - u.u_offset = 0; - while (u.u_offset < dirsize) { +#ifdef NAMEI_DIAGNOSTIC + printf("{%s}:\n", ndp->ni_dent.d_name); +#endif +searchloop: + while (ndp->ni_offset < endsearch) { /* * If offset is on a block boundary, * read the next directory block. * Release previous if it exists. */ - if (blkoff(fs, u.u_offset) == 0) { + if (blkoff(fs, ndp->ni_offset) == 0) { if (bp != NULL) brelse(bp); - bp = batoffset(dp, u.u_offset, (char **)0); + bp = blkatoff(dp, ndp->ni_offset, (char **)0); if (bp == 0) goto bad; entryoffsetinblock = 0; } - /* * If still looking for a slot, and at a DIRBLKSIZE - * boundary, have to start looking for free space - * again. + * boundary, have to start looking for free space again. */ if (slotstatus == NONE && (entryoffsetinblock&(DIRBLKSIZ-1)) == 0) { slotoffset = -1; slotfreespace = 0; } - /* - * Get pointer to next entry, and do consistency checking: - * record length must be multiple of 4 - * entry must fit in rest of this DIRBLKSIZ block - * record must be large enough to contain name - * name must be as long as advertised, and null terminated - * Checking last condition is expensive, it is done only - * when dirchk is set. + * Get pointer to next entry. + * Full validation checks are slow, so we only check + * enough to insure forward progress through the + * directory. Complete checks can be run by patching + * "dirchk" to be true. */ ep = (struct direct *)(bp->b_un.b_addr + entryoffsetinblock); - i = DIRBLKSIZ - (entryoffsetinblock & (DIRBLKSIZ - 1)); - if ((ep->d_reclen & 0x3) || ep->d_reclen > i || - DIRSIZ(ep) > ep->d_reclen || dirchk && dirbadname(ep)) { - dirbad(dp, "mangled entry"); - u.u_offset += i; + if (ep->d_reclen == 0 || + dirchk && dirbadentry(ep, entryoffsetinblock)) { + dirbad(dp, ndp->ni_offset, "mangled entry"); + i = DIRBLKSIZ - (entryoffsetinblock & (DIRBLKSIZ - 1)); + ndp->ni_offset += i; entryoffsetinblock += i; continue; } @@ -232,17 +488,16 @@ dirloop2: if (size > 0) { if (size >= slotneeded) { slotstatus = FOUND; - slotoffset = u.u_offset; + slotoffset = ndp->ni_offset; slotsize = ep->d_reclen; } else if (slotstatus == NONE) { slotfreespace += size; if (slotoffset == -1) - slotoffset = u.u_offset; + slotoffset = ndp->ni_offset; if (slotfreespace >= slotneeded) { slotstatus = COMPACT; - slotsize = - u.u_offset+ep->d_reclen - - slotoffset; + slotsize = ndp->ni_offset + + ep->d_reclen - slotoffset; } } } @@ -252,21 +507,40 @@ dirloop2: * Check for a name match. */ if (ep->d_ino) { - if (ep->d_namlen == u.u_dent.d_namlen && - !bcmp(u.u_dent.d_name, ep->d_name, ep->d_namlen)) +#ifdef NAMEI_DIAGNOSTIC + printf("{%s} ", ep->d_name); +#endif + if (ep->d_namlen == ndp->ni_dent.d_namlen && + !bcmp(ndp->ni_dent.d_name, ep->d_name, + (unsigned)ep->d_namlen)) goto found; } - prevoff = u.u_offset; - u.u_offset += ep->d_reclen; + prevoff = ndp->ni_offset; + ndp->ni_offset += ep->d_reclen; entryoffsetinblock += ep->d_reclen; + if (ep->d_ino) + enduseful = ndp->ni_offset; } +#ifdef NAMEI_DIAGNOSTIC + printf("\nnotfound\n"); +#endif /* notfound: */ + /* + * If we started in the middle of the directory and failed + * to find our target, we must check the beginning as well. + */ + if (numdirpasses == 2) { + numdirpasses--; + ndp->ni_offset = 0; + endsearch = u.u_ncache.nc_prevoffset; + goto searchloop; + } /* * If creating, and at end of pathname and current - * directory has not been removed, then can consider allowing - * file to be created. + * directory has not been removed, then can consider + * allowing file to be created. */ - if (flag == 1 && *cp == 0 && dp->i_nlink != 0) { + if (flag == CREATE && *cp == 0 && dp->i_nlink != 0) { /* * Access for write is interpreted as allowing * creation of files in the directory. @@ -276,140 +550,251 @@ dirloop2: /* * Return an indication of where the new directory * entry should be put. If we didn't find a slot, - * then set u.u_count to 0 indicating that the - * new slot belongs at the end of the directory. - * If we found a slot, then the new entry can be - * put in the range [u.u_offset..u.u_offset+u.u_count) + * then set ndp->ni_count to 0 indicating that the new + * slot belongs at the end of the directory. If we found + * a slot, then the new entry can be put in the range + * [ndp->ni_offset .. ndp->ni_offset + ndp->ni_count) */ - if (slotstatus == NONE) - u.u_count = 0; - else { - u.u_offset = slotoffset; - u.u_count = slotsize; + if (slotstatus == NONE) { + ndp->ni_offset = roundup(dp->i_size, DIRBLKSIZ); + ndp->ni_count = 0; + enduseful = ndp->ni_offset; + } else { + ndp->ni_offset = slotoffset; + ndp->ni_count = slotsize; + if (enduseful < slotoffset + slotsize) + enduseful = slotoffset + slotsize; } + ndp->ni_endoff = roundup(enduseful, DIRBLKSIZ); dp->i_flag |= IUPD|ICHG; if (bp) brelse(bp); - brelse(nbp); + FREE(nbp, M_NAMEI); /* * We return with the directory locked, so that * the parameters we set up above will still be * valid if we actually decide to do a direnter(). * We return NULL to indicate that the entry doesn't * currently exist, leaving a pointer to the (locked) - * directory inode in u.u_pdir. + * directory inode in ndp->ni_pdir. */ - u.u_pdir = dp; + ndp->ni_pdir = dp; return (NULL); } u.u_error = ENOENT; goto bad; found: +#ifdef NAMEI_DIAGNOSTIC + printf("\nfound\n"); +#endif + if (numdirpasses == 2) + nchstats.ncs_pass2++; /* * Check that directory length properly reflects presence * of this entry. */ - if (entryoffsetinblock + ep->d_reclen > dp->i_size) { - dirbad(dp, "i_size too small"); - dp->i_size = entryoffsetinblock + ep->d_reclen; + if (entryoffsetinblock + DIRSIZ(ep) > dp->i_size) { + dirbad(dp, ndp->ni_offset, "i_size too small"); + dp->i_size = entryoffsetinblock + DIRSIZ(ep); dp->i_flag |= IUPD|ICHG; } /* - * Found component in pathname; save directory - * entry in u.u_dent, and release directory buffer. + * Found component in pathname. + * If the final component of path name, save information + * in the cache as to where the entry was found. + */ + if (*cp == '\0' && flag == LOOKUP) { + u.u_ncache.nc_prevoffset = ndp->ni_offset &~ (DIRBLKSIZ - 1); + u.u_ncache.nc_inumber = dp->i_number; + u.u_ncache.nc_dev = dp->i_dev; + } + /* + * Save directory entry's inode number and reclen in ndp->ni_dent, + * and release directory buffer. */ - bcopy((caddr_t)ep, (caddr_t)&u.u_dent, DIRSIZ(ep)); + ndp->ni_dent.d_ino = ep->d_ino; + ndp->ni_dent.d_reclen = ep->d_reclen; brelse(bp); bp = NULL; /* * If deleting, and at end of pathname, return * parameters which can be used to remove file. - * Note that in this case we return the directory - * inode, not the inode of the file being deleted. + * If the lockparent flag isn't set, we return only + * the directory (in ndp->ni_pdir), otherwise we go + * on and lock the inode, being careful with ".". */ - if (flag == 2 && *cp == 0) { + if (flag == DELETE && *cp == 0) { /* * Write access to directory required to delete files. */ if (access(dp, IWRITE)) goto bad; + ndp->ni_pdir = dp; /* for dirremove() */ /* - * Return pointer to current entry in u.u_offset, + * Return pointer to current entry in ndp->ni_offset, * and distance past previous entry (if there - * is a previous entry in this block) in u.u_count. - * Save directory inode pointer in u.u_pdir for dirremove(). + * is a previous entry in this block) in ndp->ni_count. + * Save directory inode pointer in ndp->ni_pdir for dirremove(). */ - if ((u.u_offset&(DIRBLKSIZ-1)) == 0) - u.u_count = 0; + if ((ndp->ni_offset&(DIRBLKSIZ-1)) == 0) + ndp->ni_count = 0; else - u.u_count = u.u_offset - prevoff; - brelse(nbp); - u.u_pdir = dp; /* for dirremove() */ + ndp->ni_count = ndp->ni_offset - prevoff; + if (lockparent) { + if (dp->i_number == ndp->ni_dent.d_ino) + dp->i_count++; + else { + dp = iget(dp->i_dev, fs, ndp->ni_dent.d_ino); + if (dp == NULL) { + iput(ndp->ni_pdir); + goto bad; + } + /* + * If directory is "sticky", then user must own + * the directory, or the file in it, else he + * may not delete it (unless he's root). This + * implements append-only directories. + */ + if ((ndp->ni_pdir->i_mode & ISVTX) && + u.u_uid != 0 && + u.u_uid != ndp->ni_pdir->i_uid && + dp->i_uid != u.u_uid) { + iput(ndp->ni_pdir); + u.u_error = EPERM; + goto bad; + } + } + } + FREE(nbp, M_NAMEI); return (dp); } /* - * Special handling for ".." allowing chdir out of mounted - * file system: indirect .. in root inode to reevaluate - * in directory file system was mounted on. + * If rewriting (rename), return the inode and the + * information required to rewrite the present directory + * Must get inode of directory entry to verify it's a + * regular file, or empty directory. */ - if (u.u_dent.d_name[0] == '.' && u.u_dent.d_name[1] == '.' && - u.u_dent.d_name[2] == '\0') { - if (dp == u.u_rdir) - u.u_dent.d_ino = dp->i_number; - else if (u.u_dent.d_ino == ROOTINO && - dp->i_number == ROOTINO) { - for (i = 1; i < NMOUNT; i++) - if (mount[i].m_bufp != NULL && - mount[i].m_dev == dp->i_dev) { - iput(dp); - dp = mount[i].m_inodp; - ilock(dp); - dp->i_count++; - fs = dp->i_fs; - cp -= 2; /* back over .. */ - goto dirloop2; - } + if ((flag == CREATE && lockparent) && *cp == 0) { + if (access(dp, IWRITE)) + goto bad; + ndp->ni_pdir = dp; /* for dirrewrite() */ + /* + * Careful about locking second inode. + * This can only occur if the target is ".". + */ + if (dp->i_number == ndp->ni_dent.d_ino) { + u.u_error = EISDIR; /* XXX */ + goto bad; + } + dp = iget(dp->i_dev, fs, ndp->ni_dent.d_ino); + if (dp == NULL) { + iput(ndp->ni_pdir); + goto bad; } + FREE(nbp, M_NAMEI); + return (dp); } /* - * Check for symbolic link, which may require us - * to massage the name before we continue translation. - * To avoid deadlock have to unlock the current directory, - * but don't iput it because we may need it again (if - * the symbolic link is relative to .). Instead save - * it (unlocked) as pdp. + * Check for symbolic link, which may require us to massage the + * name before we continue translation. We do not `iput' the + * directory because we may need it again if the symbolic link + * is relative to the current directory. Instead we save it + * unlocked as "pdp". We must get the target inode before unlocking + * the directory to insure that the inode will not be removed + * before we get it. We prevent deadlock by always fetching + * inodes from the root, moving down the directory tree. Thus + * when following backward pointers ".." we must unlock the + * parent directory before getting the requested directory. + * There is a potential race condition here if both the current + * and parent directories are removed before the `iget' for the + * inode associated with ".." returns. We hope that this occurs + * infrequently since we cannot avoid this race condition without + * implementing a sophisticated deadlock detection algorithm. + * Note also that this simple deadlock detection scheme will not + * work if the file system has any hard links other than ".." + * that point backwards in the directory structure. */ pdp = dp; - iunlock(pdp); - dp = iget(dp->i_dev, fs, u.u_dent.d_ino); - if (dp == NULL) - goto bad2; + if (isdotdot) { + IUNLOCK(pdp); /* race to get the inode */ + dp = iget(dp->i_dev, fs, ndp->ni_dent.d_ino); + if (dp == NULL) + goto bad2; + } else if (dp->i_number == ndp->ni_dent.d_ino) { + dp->i_count++; /* we want ourself, ie "." */ + } else { + dp = iget(dp->i_dev, fs, ndp->ni_dent.d_ino); + IUNLOCK(pdp); + if (dp == NULL) + goto bad2; + } + + /* + * Insert name into cache if appropriate. + */ + if (makeentry) { + if (ncp != NULL) + panic("namei: duplicating cache"); + /* + * Free the cache slot at head of lru chain. + */ + if (ncp = nchhead) { + /* remove from lru chain */ + *ncp->nc_prev = ncp->nc_nxt; + if (ncp->nc_nxt) + ncp->nc_nxt->nc_prev = ncp->nc_prev; + else + nchtail = ncp->nc_prev; + remque(ncp); /* remove from old hash chain */ + /* grab the inode we just found */ + ncp->nc_ip = dp; + /* fill in cache info */ + ncp->nc_ino = pdp->i_number; /* parents inum */ + ncp->nc_dev = pdp->i_dev; /* & device */ + ncp->nc_idev = dp->i_dev; /* our device */ + ncp->nc_id = dp->i_id; /* identifier */ + ncp->nc_nlen = ndp->ni_dent.d_namlen; + bcopy(ndp->ni_dent.d_name, ncp->nc_name, + (unsigned)ncp->nc_nlen); + /* link at end of lru chain */ + ncp->nc_nxt = NULL; + ncp->nc_prev = nchtail; + *nchtail = ncp; + nchtail = &ncp->nc_nxt; + /* and insert on hash chain */ + insque(ncp, nhp); + } + } + +haveino: fs = dp->i_fs; /* * Check for symbolic link */ - if ((dp->i_mode & IFMT) == IFLNK && (follow || *cp == '/')) { - int pathlen = strlen(cp) + 1; - int bn; + if ((dp->i_mode & IFMT) == IFLNK && + ((ndp->ni_nameiop & FOLLOW) || *cp == '/')) { + u_int pathlen = strlen(cp) + 1; - if (dp->i_size + pathlen >= MAXPATHLEN - 1 || - ++nlink > MAXSYMLINKS) { + if (dp->i_size + pathlen >= MAXPATHLEN - 1) { + u.u_error = ENAMETOOLONG; + goto bad2; + } + if (++nlink > MAXSYMLINKS) { u.u_error = ELOOP; goto bad2; } - bcopy(cp, nbp->b_un.b_addr + dp->i_size, pathlen); - u.u_segflg = 1; - u.u_base = nbp->b_un.b_addr; - u.u_count = dp->i_size; - readi(dp); + ovbcopy(cp, nbp + dp->i_size, pathlen); + u.u_error = + rdwri(UIO_READ, dp, nbp, (int)dp->i_size, + (off_t)0, 1, (int *)0); if (u.u_error) goto bad2; - cp = nbp->b_un.b_addr; + cp = nbp; iput(dp); if (*cp == '/') { irele(pdp); @@ -417,16 +802,15 @@ found: cp++; if ((dp = u.u_rdir) == NULL) dp = rootdir; - ilock(dp); + ILOCK(dp); dp->i_count++; } else { dp = pdp; - ilock(dp); + ILOCK(dp); } fs = dp->i_fs; goto dirloop; } - irele(pdp); /* * Not a symbolic link. If more pathname, @@ -435,9 +819,14 @@ found: if (*cp == '/') { while (*cp == '/') cp++; + irele(pdp); goto dirloop; } - brelse(nbp); + FREE(nbp, M_NAMEI); + if (lockparent) + ndp->ni_pdir = pdp; + else + irele(pdp); return (dp); bad2: irele(pdp); @@ -446,98 +835,90 @@ bad: brelse(bp); if (dp) iput(dp); - brelse(nbp); + FREE(nbp, M_NAMEI); return (NULL); } -dirbad(ip, how) + +dirbad(ip, offset, how) struct inode *ip; + off_t offset; char *how; { printf("%s: bad dir ino %d at offset %d: %s\n", - ip->i_fs->fs_fsmnt, ip->i_number, u.u_offset, how); + ip->i_fs->fs_fsmnt, ip->i_number, offset, how); } -dirbadname(ep) +/* + * Do consistency checking on a directory entry: + * record length must be multiple of 4 + * entry must fit in rest of its DIRBLKSIZ block + * record must be large enough to contain entry + * name is not longer than MAXNAMLEN + * name must be as long as advertised, and null terminated + */ +dirbadentry(ep, entryoffsetinblock) register struct direct *ep; + int entryoffsetinblock; { - register char *cp; register int i; + if ((ep->d_reclen & 0x3) != 0 || + ep->d_reclen > DIRBLKSIZ - (entryoffsetinblock & (DIRBLKSIZ - 1)) || + ep->d_reclen < DIRSIZ(ep) || ep->d_namlen > MAXNAMLEN) + return (1); for (i = 0; i < ep->d_namlen; i++) - if (ep->d_name[i] == 0) + if (ep->d_name[i] == '\0') return (1); return (ep->d_name[i]); } -/* - * Return the next character from the - * kernel string pointed at by dirp. - */ -schar() -{ - - return (*u.u_dirp++ & 0377); -} - -/* - * Return the next character from the - * user string pointed at by dirp. - */ -uchar() -{ - register c; - - c = fubyte(u.u_dirp++); - if (c == -1) { - u.u_error = EFAULT; - c = 0; - } - return (c); -} - /* * Write a directory entry after a call to namei, using the parameters * which it left in the u. area. The argument ip is the inode which - * the new directory entry will refer to. The u. area field u.u_pdir is + * the new directory entry will refer to. The u. area field ndp->ni_pdir is * a pointer to the directory to be written, which was left locked by - * namei. Remaining parameters (u.u_offset, u.u_count) indicate + * namei. Remaining parameters (ndp->ni_offset, ndp->ni_count) indicate * how the space for the new entry is to be gotten. */ -direnter(ip) +direnter(ip, ndp) struct inode *ip; + register struct nameidata *ndp; { register struct direct *ep, *nep; - struct fs *fs; + register struct inode *dp = ndp->ni_pdir; struct buf *bp; - int loc, dsize, freespace, newentrysize; + int loc, spacefree, error = 0; + u_int dsize; + int newentrysize; char *dirbuf; - u.u_dent.d_ino = ip->i_number; - u.u_segflg = 1; - newentrysize = DIRSIZ(&u.u_dent); - if (u.u_count == 0) { + ndp->ni_dent.d_ino = ip->i_number; + newentrysize = DIRSIZ(&ndp->ni_dent); + if (ndp->ni_count == 0) { /* - * If u.u_count is 0, then namei could find no space in the - * directory. In this case u.u_offset will be on a directory + * If ndp->ni_count is 0, then namei could find no space in the + * directory. In this case ndp->ni_offset will be on a directory * block boundary and we will write the new entry into a fresh * block. */ - if (u.u_offset&(DIRBLKSIZ-1)) + if (ndp->ni_offset&(DIRBLKSIZ-1)) panic("wdir: newblk"); - u.u_dent.d_reclen = DIRBLKSIZ; - u.u_count = newentrysize; - u.u_base = (caddr_t)&u.u_dent; - u.u_segflg = 1; - writei(u.u_pdir); - iput(u.u_pdir); - return; + ndp->ni_dent.d_reclen = DIRBLKSIZ; + error = rdwri(UIO_WRITE, dp, (caddr_t)&ndp->ni_dent, + newentrysize, ndp->ni_offset, 1, (int *)0); + if (DIRBLKSIZ > dp->i_fs->fs_fsize) + panic("wdir: blksize"); /* XXX - should grow w/bmap() */ + else + dp->i_size = roundup(dp->i_size, DIRBLKSIZ); + iput(dp); + return (error); } /* - * If u.u_count is non-zero, then namei found space for the - * new entry in the range u.u_offset to u.u_offset+u.u_count. + * If ndp->ni_count is non-zero, then namei found space for the new + * entry in the range ndp->ni_offset to ndp->ni_offset + ndp->ni_count. * in the directory. To use this space, we may have to compact * the entries located there, by copying them together towards * the beginning of the block, leaving the free space in @@ -548,38 +929,30 @@ direnter(ip) * Increase size of directory if entry eats into new space. * This should never push the size past a new multiple of * DIRBLKSIZE. + * + * N.B. - THIS IS AN ARTIFACT OF 4.2 AND SHOULD NEVER HAPPEN. */ - if (u.u_offset+u.u_count > u.u_pdir->i_size) { - if (((u.u_offset+u.u_count-1)&~(DIRBLKSIZ-1)) != - ((u.u_pdir->i_size-1)&~(DIRBLKSIZ-1))) { -printf("wdir i_size dir %s/%d (of=%d,cnt=%d,psz=%d))\n", -u.u_pdir->i_fs->fs_fsmnt,u.u_pdir->i_number,u.u_offset, -u.u_count,u.u_pdir->i_size); - panic("wdir: span"); - } - u.u_pdir->i_size = u.u_offset + u.u_count; - } - + if (ndp->ni_offset + ndp->ni_count > dp->i_size) + dp->i_size = ndp->ni_offset + ndp->ni_count; /* * Get the block containing the space for the new directory - * entry. + * entry. Should return error by result instead of u.u_error. */ - bp = batoffset(u.u_pdir, u.u_offset, (char **)&dirbuf); - if (bp == 0) - return; -printf("direnter u.u_offset %d u.u_count %d, bpaddr %x, dirbuf %x\n", - u.u_offset, u.u_count, bp->b_un.b_addr, dirbuf); - + bp = blkatoff(dp, ndp->ni_offset, (char **)&dirbuf); + if (bp == 0) { + iput(dp); + return (u.u_error); + } /* * Find space for the new entry. In the simple case, the * entry at offset base will have the space. If it does * not, then namei arranged that compacting the region - * u.u_offset to u.u_offset+u.u_count would yield the space. + * ndp->ni_offset to ndp->ni_offset+ndp->ni_count would yield the space. */ ep = (struct direct *)dirbuf; dsize = DIRSIZ(ep); - freespace = ep->d_reclen - dsize; - for (loc = ep->d_reclen; loc < u.u_count; ) { + spacefree = ep->d_reclen - dsize; + for (loc = ep->d_reclen; loc < ndp->ni_count; ) { nep = (struct direct *)(dirbuf + loc); if (ep->d_ino) { /* trim the existing slot */ @@ -587,96 +960,317 @@ printf("direnter u.u_offset %d u.u_count %d, bpaddr %x, dirbuf %x\n", ep = (struct direct *)((char *)ep + dsize); } else { /* overwrite; nothing there; header is ours */ - freespace += dsize; + spacefree += dsize; } dsize = DIRSIZ(nep); - freespace += nep->d_reclen - dsize; + spacefree += nep->d_reclen - dsize; loc += nep->d_reclen; -/*ZZ*/if((loc&~0x1ff)!=(loc+nep->d_reclen-1&~0x1ff)) -/*ZZ*/printf("wdir: compact loc %d reclen %d (dir %s/%d)\n",loc,nep->d_reclen, -/*ZZ*/u.u_pdir->i_fs->fs_fsmnt,u.u_pdir->i_number); - bcopy(nep, ep, dsize); + bcopy((caddr_t)nep, (caddr_t)ep, dsize); } /* * Update the pointer fields in the previous entry (if any), * copy in the new entry, and write out the block. */ if (ep->d_ino == 0) { - if (freespace + dsize < newentrysize) + if (spacefree + dsize < newentrysize) panic("wdir: compact1"); -/*ZZ*/if(freespace+dsize>512)panic("wdir: compact screwup"); - u.u_dent.d_reclen = freespace + dsize; + ndp->ni_dent.d_reclen = spacefree + dsize; } else { - if (freespace < newentrysize) + if (spacefree < newentrysize) panic("wdir: compact2"); - u.u_dent.d_reclen = freespace; -/*ZZ*/if ((((char *)ep-bp->b_un.b_addr)&0x1ff)+dsize>512) panic("wdir: reclen"); + ndp->ni_dent.d_reclen = spacefree; ep->d_reclen = dsize; ep = (struct direct *)((char *)ep + dsize); } -/*ZZ*/if((((char*)ep-bp->b_un.b_addr)&0x1ff)+u.u_dent.d_reclen>512)panic("wdir: botch"); - bcopy(&u.u_dent, ep, newentrysize); + bcopy((caddr_t)&ndp->ni_dent, (caddr_t)ep, (u_int)newentrysize); bwrite(bp); - u.u_pdir->i_flag |= IUPD|ICHG; - iput(u.u_pdir); + dp->i_flag |= IUPD|ICHG; + if (ndp->ni_endoff && ndp->ni_endoff < dp->i_size) + itrunc(dp, (u_long)ndp->ni_endoff); + iput(dp); + return (error); } -dirremove() +/* + * Remove a directory entry after a call to namei, using the + * parameters which it left in the u. area. The u. entry + * ni_offset contains the offset into the directory of the + * entry to be eliminated. The ni_count field contains the + * size of the previous record in the directory. If this + * is 0, the first entry is being deleted, so we need only + * zero the inode number to mark the entry as free. If the + * entry isn't the first in the directory, we must reclaim + * the space of the now empty record by adding the record size + * to the size of the previous entry. + */ +dirremove(ndp) + register struct nameidata *ndp; { - register struct inode *dp = u.u_pdir; - register struct fs *fs = dp->i_fs; + register struct inode *dp = ndp->ni_pdir; register struct buf *bp; struct direct *ep; -printf("dirremove u.u_offset %d u.u_count %d\n", u.u_offset, u.u_count); - if (u.u_count == 0) { + if (ndp->ni_count == 0) { /* * First entry in block: set d_ino to zero. */ -/*ZZ*/if(u.u_offset&0x1ff)printf("missed dir compact dir %s/%d off %d file %s\n" -/*ZZ*/,dp->i_fs->fs_fsmnt,dp->i_number,u.u_offset,u.u_dent.d_name); - u.u_base = (caddr_t)&u.u_dent; - u.u_count = DIRSIZ(&u.u_dent); - u.u_dent.d_ino = 0; - writei(dp); + ndp->ni_dent.d_ino = 0; + (void) rdwri(UIO_WRITE, dp, (caddr_t)&ndp->ni_dent, + (int)DIRSIZ(&ndp->ni_dent), ndp->ni_offset, 1, (int *)0); } else { /* * Collapse new free space into previous entry. */ - bp = batoffset(dp, u.u_offset - u.u_count, (char **)&ep); + bp = blkatoff(dp, ndp->ni_offset - ndp->ni_count, (char **)&ep); if (bp == 0) return (0); - ep->d_reclen += u.u_dent.d_reclen; -/*ZZ*/if((((char *)ep - bp->b_un.b_addr)&0x1ff)+u.u_dent.d_reclen > 512) -/*ZZ*/ panic("unlink: reclen"); + ep->d_reclen += ndp->ni_dent.d_reclen; bwrite(bp); dp->i_flag |= IUPD|ICHG; } return (1); } +/* + * Rewrite an existing directory entry to point at the inode + * supplied. The parameters describing the directory entry are + * set up by a call to namei. + */ +dirrewrite(dp, ip, ndp) + struct inode *dp, *ip; + struct nameidata *ndp; +{ + + ndp->ni_dent.d_ino = ip->i_number; + u.u_error = rdwri(UIO_WRITE, dp, (caddr_t)&ndp->ni_dent, + (int)DIRSIZ(&ndp->ni_dent), ndp->ni_offset, 1, (int *)0); + iput(dp); +} + +/* + * Return buffer with contents of block "offset" + * from the beginning of directory "ip". If "res" + * is non-zero, fill it in with a pointer to the + * remaining space in the directory. + */ struct buf * -batoffset(ip, offset, res) +blkatoff(ip, offset, res) struct inode *ip; off_t offset; char **res; { register struct fs *fs = ip->i_fs; - int lbn = lblkno(fs, offset); - int base = blkoff(fs, offset); + daddr_t lbn = lblkno(fs, offset); int bsize = blksize(fs, ip, lbn); - int bn = fsbtodb(fs, bmap(ip, lbn, B_WRITE, base, bsize)); register struct buf *bp; + daddr_t bn; + bn = bmap(ip, lbn, B_READ, bsize); if (u.u_error) return (0); - bp = bread(ip->i_dev, bn, bsize); + if (bn == (daddr_t)-1) { + dirbad(ip, offset, "hole in dir"); + return (0); + } +#ifdef SECSIZE + bp = bread(ip->i_dev, fsbtodb(fs, bn), bsize, fs->fs_dbsize); +#else SECSIZE + bp = bread(ip->i_dev, fsbtodb(fs, bn), bsize); +#endif SECSIZE if (bp->b_flags & B_ERROR) { brelse(bp); return (0); } if (res) - *res = bp->b_un.b_addr + base; -printf("b_addr %x res pointer %x\n", bp->b_un.b_addr, *res); + *res = bp->b_un.b_addr + blkoff(fs, offset); return (bp); } + +/* + * Check if a directory is empty or not. + * Inode supplied must be locked. + * + * Using a struct dirtemplate here is not precisely + * what we want, but better than using a struct direct. + * + * NB: does not handle corrupted directories. + */ +dirempty(ip, parentino) + register struct inode *ip; + ino_t parentino; +{ + register off_t off; + struct dirtemplate dbuf; + register struct direct *dp = (struct direct *)&dbuf; + int error, count; +#define MINDIRSIZ (sizeof (struct dirtemplate) / 2) + + for (off = 0; off < ip->i_size; off += dp->d_reclen) { + error = rdwri(UIO_READ, ip, (caddr_t)dp, MINDIRSIZ, + off, 1, &count); + /* + * Since we read MINDIRSIZ, residual must + * be 0 unless we're at end of file. + */ + if (error || count != 0) + return (0); + /* avoid infinite loops */ + if (dp->d_reclen == 0) + return (0); + /* skip empty entries */ + if (dp->d_ino == 0) + continue; + /* accept only "." and ".." */ + if (dp->d_namlen > 2) + return (0); + if (dp->d_name[0] != '.') + return (0); + /* + * At this point d_namlen must be 1 or 2. + * 1 implies ".", 2 implies ".." if second + * char is also "." + */ + if (dp->d_namlen == 1) + continue; + if (dp->d_name[1] == '.' && dp->d_ino == parentino) + continue; + return (0); + } + return (1); +} + +/* + * Check if source directory is in the path of the target directory. + * Target is supplied locked, source is unlocked. + * The target is always iput() before returning. + */ +checkpath(source, target) + struct inode *source, *target; +{ + struct dirtemplate dirbuf; + register struct inode *ip; + int error = 0; + + ip = target; + if (ip->i_number == source->i_number) { + error = EEXIST; + goto out; + } + if (ip->i_number == ROOTINO) + goto out; + + for (;;) { + if ((ip->i_mode&IFMT) != IFDIR) { + error = ENOTDIR; + break; + } + error = rdwri(UIO_READ, ip, (caddr_t)&dirbuf, + sizeof (struct dirtemplate), (off_t)0, 1, (int *)0); + if (error != 0) + break; + if (dirbuf.dotdot_namlen != 2 || + dirbuf.dotdot_name[0] != '.' || + dirbuf.dotdot_name[1] != '.') { + error = ENOTDIR; + break; + } + if (dirbuf.dotdot_ino == source->i_number) { + error = EINVAL; + break; + } + if (dirbuf.dotdot_ino == ROOTINO) + break; + iput(ip); + ip = iget(ip->i_dev, ip->i_fs, dirbuf.dotdot_ino); + if (ip == NULL) { + error = u.u_error; + break; + } + } + +out: + if (error == ENOTDIR) + printf("checkpath: .. not a directory\n"); + if (ip != NULL) + iput(ip); + return (error); +} + +/* + * Name cache initialization, from main() when we are booting + */ +nchinit() +{ + register union nchash *nchp; + register struct namecache *ncp; + + nchhead = 0; + nchtail = &nchhead; + for (ncp = namecache; ncp < &namecache[nchsize]; ncp++) { + ncp->nc_forw = ncp; /* hash chain */ + ncp->nc_back = ncp; + ncp->nc_nxt = NULL; /* lru chain */ + *nchtail = ncp; + ncp->nc_prev = nchtail; + nchtail = &ncp->nc_nxt; + /* all else is zero already */ + } + for (nchp = nchash; nchp < &nchash[NCHHASH]; nchp++) { + nchp->nch_head[0] = nchp; + nchp->nch_head[1] = nchp; + } +} + +/* + * Cache flush, called when filesys is umounted to + * remove entries that would now be invalid + * + * The line "nxtcp = nchhead" near the end is to avoid potential problems + * if the cache lru chain is modified while we are dumping the + * inode. This makes the algorithm O(n^2), but do you think I care? + */ +nchinval(dev) + register dev_t dev; +{ + register struct namecache *ncp, *nxtcp; + + for (ncp = nchhead; ncp; ncp = nxtcp) { + nxtcp = ncp->nc_nxt; + if (ncp->nc_ip == NULL || + (ncp->nc_idev != dev && ncp->nc_dev != dev)) + continue; + /* free the resources we had */ + ncp->nc_idev = NODEV; + ncp->nc_dev = NODEV; + ncp->nc_id = NULL; + ncp->nc_ino = 0; + ncp->nc_ip = NULL; + remque(ncp); /* remove entry from its hash chain */ + ncp->nc_forw = ncp; /* and make a dummy one */ + ncp->nc_back = ncp; + /* delete this entry from LRU chain */ + *ncp->nc_prev = nxtcp; + if (nxtcp) + nxtcp->nc_prev = ncp->nc_prev; + else + nchtail = ncp->nc_prev; + /* cause rescan of list, it may have altered */ + nxtcp = nchhead; + /* put the now-free entry at head of LRU */ + ncp->nc_nxt = nxtcp; + ncp->nc_prev = &nchhead; + nxtcp->nc_prev = &ncp->nc_nxt; + nchhead = ncp; + } +} + +/* + * Name cache invalidation of all entries. + */ +cacheinvalall() +{ + register struct namecache *ncp; + + for (ncp = namecache; ncp < &namecache[nchsize]; ncp++) + ncp->nc_id = 0; +}