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