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