Commit | Line | Data |
---|---|---|
6f7b6c68 | 1 | /* |
ec54f0cc KB |
2 | * Copyright (c) 1989, 1993 |
3 | * The Regents of the University of California. All rights reserved. | |
6f7b6c68 | 4 | * |
dbf0c423 | 5 | * %sccs.include.redist.c% |
6f7b6c68 | 6 | * |
3ef0a118 | 7 | * @(#)vfs_cache.c 8.3 (Berkeley) %G% |
6f7b6c68 KM |
8 | */ |
9 | ||
38a01dbe KB |
10 | #include <sys/param.h> |
11 | #include <sys/systm.h> | |
12 | #include <sys/time.h> | |
13 | #include <sys/mount.h> | |
14 | #include <sys/vnode.h> | |
15 | #include <sys/namei.h> | |
16 | #include <sys/errno.h> | |
17 | #include <sys/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 | */ | |
3ef0a118 | 40 | LIST_HEAD(nchashhead, namecache) *nchashtbl; |
1dfa72b1 KM |
41 | u_long nchash; /* size of hash table - 1 */ |
42 | long numcache; /* number of cache entries allocated */ | |
3ef0a118 | 43 | TAILQ_HEAD(, namecache) nclruhead; /* LRU chain */ |
6f7b6c68 KM |
44 | struct nchstats nchstats; /* cache effectiveness statistics */ |
45 | ||
ea5eb849 KM |
46 | int doingcache = 1; /* 1 => enable the cache */ |
47 | ||
6f7b6c68 KM |
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). | |
ea5eb849 KM |
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. | |
6f7b6c68 | 61 | */ |
cfef4373 | 62 | int |
f7c1c550 | 63 | cache_lookup(dvp, vpp, cnp) |
cfef4373 JH |
64 | struct vnode *dvp; |
65 | struct vnode **vpp; | |
66 | struct componentname *cnp; | |
6f7b6c68 | 67 | { |
3ef0a118 KM |
68 | register struct namecache *ncp; |
69 | register struct nchashhead *ncpp; | |
6f7b6c68 | 70 | |
807b7aa2 KM |
71 | if (!doingcache) { |
72 | cnp->cn_flags &= ~MAKEENTRY; | |
ea5eb849 | 73 | return (0); |
807b7aa2 | 74 | } |
cfef4373 | 75 | if (cnp->cn_namelen > NCHNAMLEN) { |
6f7b6c68 | 76 | nchstats.ncs_long++; |
cfef4373 | 77 | cnp->cn_flags &= ~MAKEENTRY; |
6f7b6c68 KM |
78 | return (0); |
79 | } | |
12e9ded3 | 80 | ncpp = &nchashtbl[cnp->cn_hash & nchash]; |
3ef0a118 | 81 | for (ncp = ncpp->lh_first; ncp != 0; ncp = ncp->nc_hash.le_next) { |
ea5eb849 KM |
82 | if (ncp->nc_dvp == dvp && |
83 | ncp->nc_dvpid == dvp->v_id && | |
cfef4373 | 84 | ncp->nc_nlen == cnp->cn_namelen && |
12e9ded3 | 85 | !bcmp(ncp->nc_name, cnp->cn_nameptr, (u_int)ncp->nc_nlen)) |
6f7b6c68 KM |
86 | break; |
87 | } | |
3ef0a118 | 88 | if (ncp == 0) { |
6f7b6c68 | 89 | nchstats.ncs_miss++; |
6f7b6c68 KM |
90 | return (0); |
91 | } | |
3ef0a118 | 92 | if ((cnp->cn_flags & MAKEENTRY) == 0) { |
ea5eb849 KM |
93 | nchstats.ncs_badhits++; |
94 | } else if (ncp->nc_vp == NULL) { | |
f7c1c550 | 95 | if (cnp->cn_nameiop != CREATE) { |
e828c39a KM |
96 | nchstats.ncs_neghits++; |
97 | /* | |
98 | * Move this slot to end of LRU chain, | |
99 | * if not already there. | |
100 | */ | |
3ef0a118 KM |
101 | if (ncp->nc_lru.tqe_next != 0) { |
102 | TAILQ_REMOVE(&nclruhead, ncp, nc_lru); | |
103 | TAILQ_INSERT_TAIL(&nclruhead, ncp, nc_lru); | |
e828c39a KM |
104 | } |
105 | return (ENOENT); | |
6f7b6c68 | 106 | } |
ea5eb849 KM |
107 | } else if (ncp->nc_vpid != ncp->nc_vp->v_id) { |
108 | nchstats.ncs_falsehits++; | |
109 | } else { | |
6f7b6c68 | 110 | nchstats.ncs_goodhits++; |
ea5eb849 KM |
111 | /* |
112 | * move this slot to end of LRU chain, if not already there | |
113 | */ | |
3ef0a118 KM |
114 | if (ncp->nc_lru.tqe_next != 0) { |
115 | TAILQ_REMOVE(&nclruhead, ncp, nc_lru); | |
116 | TAILQ_INSERT_TAIL(&nclruhead, ncp, nc_lru); | |
ea5eb849 | 117 | } |
cfef4373 | 118 | *vpp = ncp->nc_vp; |
ea5eb849 | 119 | return (-1); |
6f7b6c68 KM |
120 | } |
121 | ||
122 | /* | |
123 | * Last component and we are renaming or deleting, | |
124 | * the cache entry is invalid, or otherwise don't | |
125 | * want cache entry to exist. | |
126 | */ | |
3ef0a118 KM |
127 | TAILQ_REMOVE(&nclruhead, ncp, nc_lru); |
128 | LIST_REMOVE(ncp, nc_hash); | |
129 | ncp->nc_hash.le_prev = 0; | |
130 | TAILQ_INSERT_HEAD(&nclruhead, ncp, nc_lru); | |
6f7b6c68 KM |
131 | return (0); |
132 | } | |
133 | ||
134 | /* | |
135 | * Add an entry to the cache | |
136 | */ | |
f7c1c550 | 137 | cache_enter(dvp, vp, cnp) |
cfef4373 JH |
138 | struct vnode *dvp; |
139 | struct vnode *vp; | |
140 | struct componentname *cnp; | |
6f7b6c68 | 141 | { |
3ef0a118 KM |
142 | register struct namecache *ncp; |
143 | register struct nchashhead *ncpp; | |
6f7b6c68 | 144 | |
7f213083 KM |
145 | #ifdef DIAGNOSTIC |
146 | if (cnp->cn_namelen > NCHNAMLEN) | |
147 | panic("cache_enter: name too long"); | |
148 | #endif | |
ea5eb849 KM |
149 | if (!doingcache) |
150 | return; | |
6f7b6c68 KM |
151 | /* |
152 | * Free the cache slot at head of lru chain. | |
153 | */ | |
1dfa72b1 KM |
154 | if (numcache < desiredvnodes) { |
155 | ncp = (struct namecache *) | |
aacc1bff | 156 | malloc((u_long)sizeof *ncp, M_CACHE, M_WAITOK); |
1dfa72b1 KM |
157 | bzero((char *)ncp, sizeof *ncp); |
158 | numcache++; | |
3ef0a118 KM |
159 | } else if (ncp = nclruhead.tqh_first) { |
160 | TAILQ_REMOVE(&nclruhead, ncp, nc_lru); | |
161 | if (ncp->nc_hash.le_prev != 0) { | |
162 | LIST_REMOVE(ncp, nc_hash); | |
163 | ncp->nc_hash.le_prev = 0; | |
40d2c81e | 164 | } |
1dfa72b1 KM |
165 | } else |
166 | return; | |
167 | /* grab the vnode we just found */ | |
cfef4373 JH |
168 | ncp->nc_vp = vp; |
169 | if (vp) | |
170 | ncp->nc_vpid = vp->v_id; | |
1dfa72b1 KM |
171 | else |
172 | ncp->nc_vpid = 0; | |
173 | /* fill in cache info */ | |
cfef4373 JH |
174 | ncp->nc_dvp = dvp; |
175 | ncp->nc_dvpid = dvp->v_id; | |
176 | ncp->nc_nlen = cnp->cn_namelen; | |
177 | bcopy(cnp->cn_nameptr, ncp->nc_name, (unsigned)ncp->nc_nlen); | |
3ef0a118 | 178 | TAILQ_INSERT_TAIL(&nclruhead, ncp, nc_lru); |
12e9ded3 | 179 | ncpp = &nchashtbl[cnp->cn_hash & nchash]; |
3ef0a118 | 180 | LIST_INSERT_HEAD(ncpp, ncp, nc_hash); |
6f7b6c68 KM |
181 | } |
182 | ||
183 | /* | |
1dfa72b1 | 184 | * Name cache initialization, from vfs_init() when we are booting |
6f7b6c68 KM |
185 | */ |
186 | nchinit() | |
187 | { | |
6f7b6c68 | 188 | |
3ef0a118 | 189 | TAILQ_INIT(&nclruhead); |
12e9ded3 | 190 | nchashtbl = hashinit(desiredvnodes, M_CACHE, &nchash); |
6f7b6c68 KM |
191 | } |
192 | ||
193 | /* | |
194 | * Cache flush, a particular vnode; called when a vnode is renamed to | |
ea5eb849 | 195 | * hide entries that would now be invalid |
6f7b6c68 KM |
196 | */ |
197 | cache_purge(vp) | |
ea5eb849 | 198 | struct vnode *vp; |
6f7b6c68 | 199 | { |
3ef0a118 KM |
200 | struct namecache *ncp; |
201 | struct nchashhead *ncpp; | |
6f7b6c68 | 202 | |
ea5eb849 KM |
203 | vp->v_id = ++nextvnodeid; |
204 | if (nextvnodeid != 0) | |
205 | return; | |
12e9ded3 | 206 | for (ncpp = &nchashtbl[nchash]; ncpp >= nchashtbl; ncpp--) { |
3ef0a118 | 207 | for (ncp = ncpp->lh_first; ncp != 0; ncp = ncp->nc_hash.le_next) { |
1dfa72b1 KM |
208 | ncp->nc_vpid = 0; |
209 | ncp->nc_dvpid = 0; | |
210 | } | |
6f7b6c68 | 211 | } |
ea5eb849 | 212 | vp->v_id = ++nextvnodeid; |
6f7b6c68 KM |
213 | } |
214 | ||
215 | /* | |
216 | * Cache flush, a whole filesystem; called when filesys is umounted to | |
217 | * remove entries that would now be invalid | |
218 | * | |
219 | * The line "nxtcp = nchhead" near the end is to avoid potential problems | |
220 | * if the cache lru chain is modified while we are dumping the | |
221 | * inode. This makes the algorithm O(n^2), but do you think I care? | |
222 | */ | |
223 | cache_purgevfs(mp) | |
aacc1bff | 224 | struct mount *mp; |
6f7b6c68 KM |
225 | { |
226 | register struct namecache *ncp, *nxtcp; | |
227 | ||
3ef0a118 | 228 | for (ncp = nclruhead.tqh_first; ncp != 0; ncp = nxtcp) { |
12e9ded3 | 229 | if (ncp->nc_dvp == NULL || ncp->nc_dvp->v_mount != mp) { |
3ef0a118 | 230 | nxtcp = ncp->nc_lru.tqe_next; |
6f7b6c68 | 231 | continue; |
12e9ded3 | 232 | } |
6f7b6c68 KM |
233 | /* free the resources we had */ |
234 | ncp->nc_vp = NULL; | |
ea5eb849 | 235 | ncp->nc_dvp = NULL; |
3ef0a118 KM |
236 | TAILQ_REMOVE(&nclruhead, ncp, nc_lru); |
237 | if (ncp->nc_hash.le_prev != 0) { | |
238 | LIST_REMOVE(ncp, nc_hash); | |
239 | ncp->nc_hash.le_prev = 0; | |
40d2c81e | 240 | } |
6f7b6c68 | 241 | /* cause rescan of list, it may have altered */ |
3ef0a118 KM |
242 | nxtcp = nclruhead.tqh_first; |
243 | TAILQ_INSERT_HEAD(&nclruhead, ncp, nc_lru); | |
6f7b6c68 KM |
244 | } |
245 | } |