vfs_cache.c revision 1.5 1 1.1 cgd /*
2 1.5 mycroft * Copyright (c) 1989, 1993
3 1.5 mycroft * The Regents of the University of California. All rights reserved.
4 1.1 cgd *
5 1.1 cgd * Redistribution and use in source and binary forms, with or without
6 1.1 cgd * modification, are permitted provided that the following conditions
7 1.1 cgd * are met:
8 1.1 cgd * 1. Redistributions of source code must retain the above copyright
9 1.1 cgd * notice, this list of conditions and the following disclaimer.
10 1.1 cgd * 2. Redistributions in binary form must reproduce the above copyright
11 1.1 cgd * notice, this list of conditions and the following disclaimer in the
12 1.1 cgd * documentation and/or other materials provided with the distribution.
13 1.1 cgd * 3. All advertising materials mentioning features or use of this software
14 1.1 cgd * must display the following acknowledgement:
15 1.1 cgd * This product includes software developed by the University of
16 1.1 cgd * California, Berkeley and its contributors.
17 1.1 cgd * 4. Neither the name of the University nor the names of its contributors
18 1.1 cgd * may be used to endorse or promote products derived from this software
19 1.1 cgd * without specific prior written permission.
20 1.1 cgd *
21 1.1 cgd * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
22 1.1 cgd * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
23 1.1 cgd * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
24 1.1 cgd * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
25 1.1 cgd * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
26 1.1 cgd * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
27 1.1 cgd * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
28 1.1 cgd * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
29 1.1 cgd * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
30 1.1 cgd * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
31 1.1 cgd * SUCH DAMAGE.
32 1.1 cgd *
33 1.5 mycroft * from: @(#)vfs_cache.c 8.1 (Berkeley) 6/10/93
34 1.5 mycroft * $Id: vfs_cache.c,v 1.5 1994/06/08 11:28:50 mycroft Exp $
35 1.1 cgd */
36 1.1 cgd
37 1.4 mycroft #include <sys/param.h>
38 1.4 mycroft #include <sys/systm.h>
39 1.4 mycroft #include <sys/time.h>
40 1.4 mycroft #include <sys/mount.h>
41 1.4 mycroft #include <sys/vnode.h>
42 1.4 mycroft #include <sys/namei.h>
43 1.4 mycroft #include <sys/errno.h>
44 1.4 mycroft #include <sys/malloc.h>
45 1.1 cgd
46 1.1 cgd /*
47 1.1 cgd * Name caching works as follows:
48 1.1 cgd *
49 1.1 cgd * Names found by directory scans are retained in a cache
50 1.1 cgd * for future reference. It is managed LRU, so frequently
51 1.1 cgd * used names will hang around. Cache is indexed by hash value
52 1.1 cgd * obtained from (vp, name) where vp refers to the directory
53 1.1 cgd * containing name.
54 1.1 cgd *
55 1.1 cgd * For simplicity (and economy of storage), names longer than
56 1.1 cgd * a maximum length of NCHNAMLEN are not cached; they occur
57 1.1 cgd * infrequently in any case, and are almost never of interest.
58 1.1 cgd *
59 1.1 cgd * Upon reaching the last segment of a path, if the reference
60 1.1 cgd * is for DELETE, or NOCACHE is set (rewrite), and the
61 1.1 cgd * name is located in the cache, it will be dropped.
62 1.1 cgd */
63 1.1 cgd
64 1.1 cgd /*
65 1.1 cgd * Structures associated with name cacheing.
66 1.1 cgd */
67 1.5 mycroft struct namecache **nchashtbl;
68 1.1 cgd u_long nchash; /* size of hash table - 1 */
69 1.1 cgd long numcache; /* number of cache entries allocated */
70 1.1 cgd struct namecache *nchhead, **nchtail; /* LRU chain pointers */
71 1.1 cgd struct nchstats nchstats; /* cache effectiveness statistics */
72 1.1 cgd
73 1.1 cgd int doingcache = 1; /* 1 => enable the cache */
74 1.1 cgd
75 1.1 cgd /*
76 1.1 cgd * Look for a the name in the cache. We don't do this
77 1.1 cgd * if the segment name is long, simply so the cache can avoid
78 1.1 cgd * holding long names (which would either waste space, or
79 1.1 cgd * add greatly to the complexity).
80 1.1 cgd *
81 1.1 cgd * Lookup is called with ni_dvp pointing to the directory to search,
82 1.1 cgd * ni_ptr pointing to the name of the entry being sought, ni_namelen
83 1.1 cgd * tells the length of the name, and ni_hash contains a hash of
84 1.5 mycroft * the name. If the lookup succeeds, the vnode is returned in ni_vp
85 1.5 mycroft * and a status of -1 is returned. If the lookup determines that
86 1.5 mycroft * the name does not exist (negative cacheing), a status of ENOENT
87 1.5 mycroft * is returned. If the lookup fails, a status of zero is returned.
88 1.1 cgd */
89 1.5 mycroft int
90 1.5 mycroft cache_lookup(dvp, vpp, cnp)
91 1.5 mycroft struct vnode *dvp;
92 1.5 mycroft struct vnode **vpp;
93 1.5 mycroft struct componentname *cnp;
94 1.1 cgd {
95 1.5 mycroft register struct namecache *ncp, *ncq, **ncpp;
96 1.1 cgd
97 1.1 cgd if (!doingcache)
98 1.1 cgd return (0);
99 1.5 mycroft if (cnp->cn_namelen > NCHNAMLEN) {
100 1.1 cgd nchstats.ncs_long++;
101 1.5 mycroft cnp->cn_flags &= ~MAKEENTRY;
102 1.1 cgd return (0);
103 1.1 cgd }
104 1.5 mycroft ncpp = &nchashtbl[cnp->cn_hash & nchash];
105 1.5 mycroft for (ncp = *ncpp; ncp; ncp = ncp->nc_forw) {
106 1.1 cgd if (ncp->nc_dvp == dvp &&
107 1.1 cgd ncp->nc_dvpid == dvp->v_id &&
108 1.5 mycroft ncp->nc_nlen == cnp->cn_namelen &&
109 1.5 mycroft !bcmp(ncp->nc_name, cnp->cn_nameptr, (u_int)ncp->nc_nlen))
110 1.1 cgd break;
111 1.1 cgd }
112 1.5 mycroft if (ncp == NULL) {
113 1.1 cgd nchstats.ncs_miss++;
114 1.1 cgd return (0);
115 1.1 cgd }
116 1.5 mycroft if (!(cnp->cn_flags & MAKEENTRY)) {
117 1.1 cgd nchstats.ncs_badhits++;
118 1.1 cgd } else if (ncp->nc_vp == NULL) {
119 1.5 mycroft if (cnp->cn_nameiop != CREATE) {
120 1.1 cgd nchstats.ncs_neghits++;
121 1.1 cgd /*
122 1.1 cgd * Move this slot to end of LRU chain,
123 1.1 cgd * if not already there.
124 1.1 cgd */
125 1.1 cgd if (ncp->nc_nxt) {
126 1.1 cgd /* remove from LRU chain */
127 1.1 cgd *ncp->nc_prev = ncp->nc_nxt;
128 1.1 cgd ncp->nc_nxt->nc_prev = ncp->nc_prev;
129 1.1 cgd /* and replace at end of it */
130 1.1 cgd ncp->nc_nxt = NULL;
131 1.1 cgd ncp->nc_prev = nchtail;
132 1.1 cgd *nchtail = ncp;
133 1.1 cgd nchtail = &ncp->nc_nxt;
134 1.1 cgd }
135 1.1 cgd return (ENOENT);
136 1.1 cgd }
137 1.1 cgd } else if (ncp->nc_vpid != ncp->nc_vp->v_id) {
138 1.1 cgd nchstats.ncs_falsehits++;
139 1.1 cgd } else {
140 1.1 cgd nchstats.ncs_goodhits++;
141 1.1 cgd /*
142 1.1 cgd * move this slot to end of LRU chain, if not already there
143 1.1 cgd */
144 1.1 cgd if (ncp->nc_nxt) {
145 1.1 cgd /* remove from LRU chain */
146 1.1 cgd *ncp->nc_prev = ncp->nc_nxt;
147 1.1 cgd ncp->nc_nxt->nc_prev = ncp->nc_prev;
148 1.1 cgd /* and replace at end of it */
149 1.1 cgd ncp->nc_nxt = NULL;
150 1.1 cgd ncp->nc_prev = nchtail;
151 1.1 cgd *nchtail = ncp;
152 1.1 cgd nchtail = &ncp->nc_nxt;
153 1.1 cgd }
154 1.5 mycroft *vpp = ncp->nc_vp;
155 1.1 cgd return (-1);
156 1.1 cgd }
157 1.1 cgd
158 1.1 cgd /*
159 1.1 cgd * Last component and we are renaming or deleting,
160 1.1 cgd * the cache entry is invalid, or otherwise don't
161 1.1 cgd * want cache entry to exist.
162 1.1 cgd */
163 1.1 cgd /* remove from LRU chain */
164 1.5 mycroft if (ncq = ncp->nc_nxt)
165 1.5 mycroft ncq->nc_prev = ncp->nc_prev;
166 1.1 cgd else
167 1.1 cgd nchtail = ncp->nc_prev;
168 1.5 mycroft *ncp->nc_prev = ncq;
169 1.1 cgd /* remove from hash chain */
170 1.5 mycroft if (ncq = ncp->nc_forw)
171 1.5 mycroft ncq->nc_back = ncp->nc_back;
172 1.5 mycroft *ncp->nc_back = ncq;
173 1.5 mycroft /* and make a dummy hash chain */
174 1.5 mycroft ncp->nc_forw = NULL;
175 1.5 mycroft ncp->nc_back = NULL;
176 1.1 cgd /* insert at head of LRU list (first to grab) */
177 1.5 mycroft if (ncq = nchhead)
178 1.5 mycroft ncq->nc_prev = &ncp->nc_nxt;
179 1.5 mycroft else
180 1.5 mycroft nchtail = &ncp->nc_nxt;
181 1.5 mycroft nchhead = ncp;
182 1.5 mycroft ncp->nc_nxt = ncq;
183 1.1 cgd ncp->nc_prev = &nchhead;
184 1.1 cgd return (0);
185 1.1 cgd }
186 1.1 cgd
187 1.1 cgd /*
188 1.1 cgd * Add an entry to the cache
189 1.1 cgd */
190 1.5 mycroft cache_enter(dvp, vp, cnp)
191 1.5 mycroft struct vnode *dvp;
192 1.5 mycroft struct vnode *vp;
193 1.5 mycroft struct componentname *cnp;
194 1.1 cgd {
195 1.5 mycroft register struct namecache *ncp, *ncq, **ncpp;
196 1.1 cgd
197 1.5 mycroft #ifdef DIAGNOSTIC
198 1.5 mycroft if (cnp->cn_namelen > NCHNAMLEN)
199 1.5 mycroft panic("cache_enter: name too long");
200 1.5 mycroft #endif
201 1.1 cgd if (!doingcache)
202 1.1 cgd return;
203 1.1 cgd /*
204 1.1 cgd * Free the cache slot at head of lru chain.
205 1.1 cgd */
206 1.1 cgd if (numcache < desiredvnodes) {
207 1.1 cgd ncp = (struct namecache *)
208 1.1 cgd malloc((u_long)sizeof *ncp, M_CACHE, M_WAITOK);
209 1.1 cgd bzero((char *)ncp, sizeof *ncp);
210 1.1 cgd numcache++;
211 1.1 cgd } else if (ncp = nchhead) {
212 1.1 cgd /* remove from lru chain */
213 1.5 mycroft if (ncq = ncp->nc_nxt)
214 1.5 mycroft ncq->nc_prev = ncp->nc_prev;
215 1.1 cgd else
216 1.1 cgd nchtail = ncp->nc_prev;
217 1.5 mycroft *ncp->nc_prev = ncq;
218 1.5 mycroft /* remove from old hash chain, if on one */
219 1.5 mycroft if (ncp->nc_back) {
220 1.5 mycroft if (ncq = ncp->nc_forw)
221 1.5 mycroft ncq->nc_back = ncp->nc_back;
222 1.5 mycroft *ncp->nc_back = ncq;
223 1.5 mycroft ncp->nc_forw = NULL;
224 1.5 mycroft ncp->nc_back = NULL;
225 1.5 mycroft }
226 1.1 cgd } else
227 1.1 cgd return;
228 1.1 cgd /* grab the vnode we just found */
229 1.5 mycroft ncp->nc_vp = vp;
230 1.5 mycroft if (vp)
231 1.5 mycroft ncp->nc_vpid = vp->v_id;
232 1.1 cgd else
233 1.1 cgd ncp->nc_vpid = 0;
234 1.1 cgd /* fill in cache info */
235 1.5 mycroft ncp->nc_dvp = dvp;
236 1.5 mycroft ncp->nc_dvpid = dvp->v_id;
237 1.5 mycroft ncp->nc_nlen = cnp->cn_namelen;
238 1.5 mycroft bcopy(cnp->cn_nameptr, ncp->nc_name, (unsigned)ncp->nc_nlen);
239 1.1 cgd /* link at end of lru chain */
240 1.1 cgd ncp->nc_nxt = NULL;
241 1.1 cgd ncp->nc_prev = nchtail;
242 1.1 cgd *nchtail = ncp;
243 1.1 cgd nchtail = &ncp->nc_nxt;
244 1.1 cgd /* and insert on hash chain */
245 1.5 mycroft ncpp = &nchashtbl[cnp->cn_hash & nchash];
246 1.5 mycroft if (ncq = *ncpp)
247 1.5 mycroft ncq->nc_back = &ncp->nc_forw;
248 1.5 mycroft ncp->nc_forw = ncq;
249 1.5 mycroft ncp->nc_back = ncpp;
250 1.5 mycroft *ncpp = ncp;
251 1.1 cgd }
252 1.1 cgd
253 1.1 cgd /*
254 1.1 cgd * Name cache initialization, from vfs_init() when we are booting
255 1.1 cgd */
256 1.1 cgd nchinit()
257 1.1 cgd {
258 1.1 cgd
259 1.1 cgd nchtail = &nchhead;
260 1.5 mycroft nchashtbl = hashinit(desiredvnodes, M_CACHE, &nchash);
261 1.1 cgd }
262 1.1 cgd
263 1.1 cgd /*
264 1.1 cgd * Cache flush, a particular vnode; called when a vnode is renamed to
265 1.1 cgd * hide entries that would now be invalid
266 1.1 cgd */
267 1.1 cgd cache_purge(vp)
268 1.1 cgd struct vnode *vp;
269 1.1 cgd {
270 1.5 mycroft struct namecache *ncp, **ncpp;
271 1.1 cgd
272 1.1 cgd vp->v_id = ++nextvnodeid;
273 1.1 cgd if (nextvnodeid != 0)
274 1.1 cgd return;
275 1.5 mycroft for (ncpp = &nchashtbl[nchash]; ncpp >= nchashtbl; ncpp--) {
276 1.5 mycroft for (ncp = *ncpp; ncp; ncp = ncp->nc_forw) {
277 1.1 cgd ncp->nc_vpid = 0;
278 1.1 cgd ncp->nc_dvpid = 0;
279 1.1 cgd }
280 1.1 cgd }
281 1.1 cgd vp->v_id = ++nextvnodeid;
282 1.1 cgd }
283 1.1 cgd
284 1.1 cgd /*
285 1.1 cgd * Cache flush, a whole filesystem; called when filesys is umounted to
286 1.1 cgd * remove entries that would now be invalid
287 1.1 cgd *
288 1.1 cgd * The line "nxtcp = nchhead" near the end is to avoid potential problems
289 1.1 cgd * if the cache lru chain is modified while we are dumping the
290 1.1 cgd * inode. This makes the algorithm O(n^2), but do you think I care?
291 1.1 cgd */
292 1.1 cgd cache_purgevfs(mp)
293 1.1 cgd struct mount *mp;
294 1.1 cgd {
295 1.1 cgd register struct namecache *ncp, *nxtcp;
296 1.1 cgd
297 1.1 cgd for (ncp = nchhead; ncp; ncp = nxtcp) {
298 1.5 mycroft if (ncp->nc_dvp == NULL || ncp->nc_dvp->v_mount != mp) {
299 1.5 mycroft nxtcp = ncp->nc_nxt;
300 1.1 cgd continue;
301 1.5 mycroft }
302 1.1 cgd /* free the resources we had */
303 1.1 cgd ncp->nc_vp = NULL;
304 1.1 cgd ncp->nc_dvp = NULL;
305 1.5 mycroft /* remove from old hash chain, if on one */
306 1.5 mycroft if (ncp->nc_back) {
307 1.5 mycroft if (nxtcp = ncp->nc_forw)
308 1.5 mycroft nxtcp->nc_back = ncp->nc_back;
309 1.5 mycroft *ncp->nc_back = nxtcp;
310 1.5 mycroft ncp->nc_forw = NULL;
311 1.5 mycroft ncp->nc_back = NULL;
312 1.5 mycroft }
313 1.1 cgd /* delete this entry from LRU chain */
314 1.5 mycroft if (nxtcp = ncp->nc_nxt)
315 1.1 cgd nxtcp->nc_prev = ncp->nc_prev;
316 1.1 cgd else
317 1.1 cgd nchtail = ncp->nc_prev;
318 1.5 mycroft *ncp->nc_prev = nxtcp;
319 1.1 cgd /* cause rescan of list, it may have altered */
320 1.5 mycroft /* also put the now-free entry at head of LRU */
321 1.5 mycroft if (nxtcp = nchhead)
322 1.5 mycroft nxtcp->nc_prev = &ncp->nc_nxt;
323 1.5 mycroft else
324 1.5 mycroft nchtail = &ncp->nc_nxt;
325 1.5 mycroft nchhead = ncp;
326 1.1 cgd ncp->nc_nxt = nxtcp;
327 1.1 cgd ncp->nc_prev = &nchhead;
328 1.1 cgd }
329 1.1 cgd }
330