xref: /original-bsd/sys/kern/vfs_cache.c (revision 860e07fc)
1 /*
2  * Copyright (c) 1989 The Regents of the University of California.
3  * All rights reserved.
4  *
5  * %sccs.include.redist.c%
6  *
7  *	@(#)vfs_cache.c	7.14 (Berkeley) 07/25/92
8  */
9 
10 #include "param.h"
11 #include "systm.h"
12 #include "time.h"
13 #include "mount.h"
14 #include "vnode.h"
15 #include "namei.h"
16 #include "errno.h"
17 #include "malloc.h"
18 
19 /*
20  * Name caching works as follows:
21  *
22  * Names found by directory scans are retained in a cache
23  * for future reference.  It is managed LRU, so frequently
24  * used names will hang around.  Cache is indexed by hash value
25  * obtained from (vp, name) where vp refers to the directory
26  * containing name.
27  *
28  * For simplicity (and economy of storage), names longer than
29  * a maximum length of NCHNAMLEN are not cached; they occur
30  * infrequently in any case, and are almost never of interest.
31  *
32  * Upon reaching the last segment of a path, if the reference
33  * is for DELETE, or NOCACHE is set (rewrite), and the
34  * name is located in the cache, it will be dropped.
35  */
36 
37 /*
38  * Structures associated with name cacheing.
39  */
40 struct namecache **nchashtbl;
41 u_long	nchash;				/* size of hash table - 1 */
42 long	numcache;			/* number of cache entries allocated */
43 struct	namecache *nchhead, **nchtail;	/* LRU chain pointers */
44 struct	nchstats nchstats;		/* cache effectiveness statistics */
45 
46 int doingcache = 1;			/* 1 => enable the cache */
47 
48 /*
49  * Look for a the name in the cache. We don't do this
50  * if the segment name is long, simply so the cache can avoid
51  * holding long names (which would either waste space, or
52  * add greatly to the complexity).
53  *
54  * Lookup is called with ni_dvp pointing to the directory to search,
55  * ni_ptr pointing to the name of the entry being sought, ni_namelen
56  * tells the length of the name, and ni_hash contains a hash of
57  * the name. If the lookup succeeds, the vnode is returned in ni_vp
58  * and a status of -1 is returned. If the lookup determines that
59  * the name does not exist (negative cacheing), a status of ENOENT
60  * is returned. If the lookup fails, a status of zero is returned.
61  */
62 int
63 cache_lookup(dvp, vpp, cnp)
64 	struct vnode *dvp;
65 	struct vnode **vpp;
66 	struct componentname *cnp;
67 {
68 	register struct namecache *ncp, *ncq, **ncpp;
69 
70 	if (!doingcache)
71 		return (0);
72 	if (cnp->cn_namelen > NCHNAMLEN) {
73 		nchstats.ncs_long++;
74 		cnp->cn_flags &= ~MAKEENTRY;
75 		return (0);
76 	}
77 	ncpp = &nchashtbl[cnp->cn_hash & nchash];
78 	for (ncp = *ncpp; ncp; ncp = ncp->nc_forw) {
79 		if (ncp->nc_dvp == dvp &&
80 		    ncp->nc_dvpid == dvp->v_id &&
81 		    ncp->nc_nlen == cnp->cn_namelen &&
82 		    !bcmp(ncp->nc_name, cnp->cn_nameptr, (u_int)ncp->nc_nlen))
83 			break;
84 	}
85 	if (ncp == NULL) {
86 		nchstats.ncs_miss++;
87 		return (0);
88 	}
89 	if (!(cnp->cn_flags & MAKEENTRY)) {
90 		nchstats.ncs_badhits++;
91 	} else if (ncp->nc_vp == NULL) {
92 		if (cnp->cn_nameiop != CREATE) {
93 			nchstats.ncs_neghits++;
94 			/*
95 			 * Move this slot to end of LRU chain,
96 			 * if not already there.
97 			 */
98 			if (ncp->nc_nxt) {
99 				/* remove from LRU chain */
100 				*ncp->nc_prev = ncp->nc_nxt;
101 				ncp->nc_nxt->nc_prev = ncp->nc_prev;
102 				/* and replace at end of it */
103 				ncp->nc_nxt = NULL;
104 				ncp->nc_prev = nchtail;
105 				*nchtail = ncp;
106 				nchtail = &ncp->nc_nxt;
107 			}
108 			return (ENOENT);
109 		}
110 	} else if (ncp->nc_vpid != ncp->nc_vp->v_id) {
111 		nchstats.ncs_falsehits++;
112 	} else {
113 		nchstats.ncs_goodhits++;
114 		/*
115 		 * move this slot to end of LRU chain, if not already there
116 		 */
117 		if (ncp->nc_nxt) {
118 			/* remove from LRU chain */
119 			*ncp->nc_prev = ncp->nc_nxt;
120 			ncp->nc_nxt->nc_prev = ncp->nc_prev;
121 			/* and replace at end of it */
122 			ncp->nc_nxt = NULL;
123 			ncp->nc_prev = nchtail;
124 			*nchtail = ncp;
125 			nchtail = &ncp->nc_nxt;
126 		}
127 		*vpp = ncp->nc_vp;
128 		return (-1);
129 	}
130 
131 	/*
132 	 * Last component and we are renaming or deleting,
133 	 * the cache entry is invalid, or otherwise don't
134 	 * want cache entry to exist.
135 	 */
136 	/* remove from LRU chain */
137 	if (ncq = ncp->nc_nxt)
138 		ncq->nc_prev = ncp->nc_prev;
139 	else
140 		nchtail = ncp->nc_prev;
141 	*ncp->nc_prev = ncq;
142 	/* remove from hash chain */
143 	if (ncq = ncp->nc_forw)
144 		ncq->nc_back = ncp->nc_back;
145 	*ncp->nc_back = ncq;
146 	/* and make a dummy hash chain */
147 	ncp->nc_forw = NULL;
148 	ncp->nc_back = NULL;
149 	/* insert at head of LRU list (first to grab) */
150 	ncp->nc_nxt = nchhead;
151 	ncp->nc_prev = &nchhead;
152 	nchhead->nc_prev = &ncp->nc_nxt;
153 	nchhead = ncp;
154 	return (0);
155 }
156 
157 /*
158  * Add an entry to the cache
159  */
160 cache_enter(dvp, vp, cnp)
161 	struct vnode *dvp;
162 	struct vnode *vp;
163 	struct componentname *cnp;
164 {
165 	register struct namecache *ncp, *ncq, **ncpp;
166 
167 #ifdef DIAGNOSTIC
168 	if (cnp->cn_namelen > NCHNAMLEN)
169 		panic("cache_enter: name too long");
170 #endif
171 	if (!doingcache)
172 		return;
173 	/*
174 	 * Free the cache slot at head of lru chain.
175 	 */
176 	if (numcache < desiredvnodes) {
177 		ncp = (struct namecache *)
178 			malloc((u_long)sizeof *ncp, M_CACHE, M_WAITOK);
179 		bzero((char *)ncp, sizeof *ncp);
180 		numcache++;
181 	} else if (ncp = nchhead) {
182 		/* remove from lru chain */
183 		if (ncq = ncp->nc_nxt)
184 			ncq->nc_prev = ncp->nc_prev;
185 		else
186 			nchtail = ncp->nc_prev;
187 		*ncp->nc_prev = ncq;
188 		/* remove from old hash chain, if on one */
189 		if (ncp->nc_back) {
190 			if (ncq = ncp->nc_forw)
191 				ncq->nc_back = ncp->nc_back;
192 			*ncp->nc_back = ncq;
193 			ncp->nc_forw = NULL;
194 			ncp->nc_back = NULL;
195 		}
196 	} else
197 		return;
198 	/* grab the vnode we just found */
199 	ncp->nc_vp = vp;
200 	if (vp)
201 		ncp->nc_vpid = vp->v_id;
202 	else
203 		ncp->nc_vpid = 0;
204 	/* fill in cache info */
205 	ncp->nc_dvp = dvp;
206 	ncp->nc_dvpid = dvp->v_id;
207 	ncp->nc_nlen = cnp->cn_namelen;
208 	bcopy(cnp->cn_nameptr, ncp->nc_name, (unsigned)ncp->nc_nlen);
209 	/* link at end of lru chain */
210 	ncp->nc_nxt = NULL;
211 	ncp->nc_prev = nchtail;
212 	*nchtail = ncp;
213 	nchtail = &ncp->nc_nxt;
214 	/* and insert on hash chain */
215 	ncpp = &nchashtbl[cnp->cn_hash & nchash];
216 	if (ncq = *ncpp)
217 		ncq->nc_back = &ncp->nc_forw;
218 	ncp->nc_forw = ncq;
219 	ncp->nc_back = ncpp;
220 	*ncpp = ncp;
221 }
222 
223 /*
224  * Name cache initialization, from vfs_init() when we are booting
225  */
226 nchinit()
227 {
228 
229 	nchtail = &nchhead;
230 	nchashtbl = hashinit(desiredvnodes, M_CACHE, &nchash);
231 }
232 
233 /*
234  * Cache flush, a particular vnode; called when a vnode is renamed to
235  * hide entries that would now be invalid
236  */
237 cache_purge(vp)
238 	struct vnode *vp;
239 {
240 	struct namecache *ncp, **ncpp;
241 
242 	vp->v_id = ++nextvnodeid;
243 	if (nextvnodeid != 0)
244 		return;
245 	for (ncpp = &nchashtbl[nchash]; ncpp >= nchashtbl; ncpp--) {
246 		for (ncp = *ncpp; ncp; ncp = ncp->nc_forw) {
247 			ncp->nc_vpid = 0;
248 			ncp->nc_dvpid = 0;
249 		}
250 	}
251 	vp->v_id = ++nextvnodeid;
252 }
253 
254 /*
255  * Cache flush, a whole filesystem; called when filesys is umounted to
256  * remove entries that would now be invalid
257  *
258  * The line "nxtcp = nchhead" near the end is to avoid potential problems
259  * if the cache lru chain is modified while we are dumping the
260  * inode.  This makes the algorithm O(n^2), but do you think I care?
261  */
262 cache_purgevfs(mp)
263 	struct mount *mp;
264 {
265 	register struct namecache *ncp, *nxtcp;
266 
267 	for (ncp = nchhead; ncp; ncp = nxtcp) {
268 		if (ncp->nc_dvp == NULL || ncp->nc_dvp->v_mount != mp) {
269 			nxtcp = ncp->nc_nxt;
270 			continue;
271 		}
272 		/* free the resources we had */
273 		ncp->nc_vp = NULL;
274 		ncp->nc_dvp = NULL;
275 		/* remove from old hash chain, if on one */
276 		if (ncp->nc_back) {
277 			if (nxtcp = ncp->nc_forw)
278 				nxtcp->nc_back = ncp->nc_back;
279 			*ncp->nc_back = nxtcp;
280 			ncp->nc_forw = NULL;
281 			ncp->nc_back = NULL;
282 		}
283 		/* delete this entry from LRU chain */
284 		if (nxtcp = ncp->nc_nxt)
285 			nxtcp->nc_prev = ncp->nc_prev;
286 		else
287 			nchtail = ncp->nc_prev;
288 		*ncp->nc_prev = nxtcp;
289 		/* cause rescan of list, it may have altered */
290 		nxtcp = nchhead;
291 		/* put the now-free entry at head of LRU */
292 		ncp->nc_nxt = nxtcp;
293 		ncp->nc_prev = &nchhead;
294 		nxtcp->nc_prev = &ncp->nc_nxt;
295 		nchhead = ncp;
296 	}
297 }
298