This source file includes following definitions.
- init_cache
- find_name
- show_cache
- add_to_cache
- add_to_queue
- remove_from_cache
- remove_from_queue
- ext2_dcache_invalidate
- ext2_dcache_lookup
- ext2_dcache_add
- ext2_dcache_remove
1
2
3
4
5
6
7
8
9
10
11
12
13 #include <asm/segment.h>
14
15 #include <linux/fs.h>
16 #include <linux/ext2_fs.h>
17 #include <linux/kernel.h>
18 #include <linux/string.h>
19
20 #ifndef DONT_USE_DCACHE
21
22 struct dir_cache_entry {
23 unsigned short dev;
24 unsigned long dir;
25 unsigned long ino;
26 char name[EXT2_NAME_LEN];
27 int len;
28 struct dir_cache_entry * queue_prev;
29 struct dir_cache_entry * queue_next;
30 struct dir_cache_entry * prev;
31 struct dir_cache_entry * next;
32 };
33
34 static struct dir_cache_entry * first = NULL;
35 static struct dir_cache_entry * last = NULL;
36 static struct dir_cache_entry * first_free = NULL;
37 static int cache_initialized = 0;
38 #ifdef EXT2FS_DEBUG_CACHE
39 static int hits = 0;
40 static int misses = 0;
41 #endif
42
43 #define CACHE_SIZE 128
44
45 static struct dir_cache_entry dcache[CACHE_SIZE];
46
47 #define HASH_QUEUES 16
48
49 static struct dir_cache_entry * queue_head[HASH_QUEUES];
50 static struct dir_cache_entry * queue_tail[HASH_QUEUES];
51
52 #define hash(dev,dir) ((dev ^ dir) % HASH_QUEUES)
53
54
55
56
57 static void init_cache (void)
58 {
59 int i;
60
61 dcache[0].prev = NULL;
62 dcache[0].next = &dcache[1];
63 dcache[0].queue_next = dcache[0].queue_prev = NULL;
64 for (i = 1; i < CACHE_SIZE - 1; i++) {
65 dcache[i].prev = &dcache[i - 1];
66 dcache[i].next = &dcache[i + 1];
67 dcache[i].queue_next = dcache[i].queue_prev = NULL;
68 }
69 dcache[i].prev = &dcache[i - 1];
70 dcache[i].next = NULL;
71 dcache[i].queue_next = dcache[i].queue_prev = NULL;
72 first_free = &dcache[0];
73 for (i = 0; i < HASH_QUEUES; i++)
74 queue_tail[i] = queue_head[i] = NULL;
75 cache_initialized = 1;
76 }
77
78
79
80
81 static struct dir_cache_entry * find_name (int queue, unsigned short dev,
82 unsigned long dir,
83 const char * name, int len)
84 {
85 struct dir_cache_entry * p;
86
87 for (p = queue_head[queue]; p != NULL && (p->dev != dev ||
88 p->dir != dir || p->len != len ||
89 strncmp (name, p->name, p->len) != 0);
90 p = p->queue_next)
91 ;
92 return p;
93 }
94
95 #ifdef EXT2FS_DEBUG_CACHE
96
97
98
99 static void show_cache (const char * func_name)
100 {
101 struct dir_cache_entry * p;
102
103 printk ("%s: cache status\n", func_name);
104 for (p = first; p != NULL; p = p->next)
105 printk ("dev:%04x, dir=%4d, name=%s\n",
106 p->dev, p->dir, p->name);
107 }
108 #endif
109
110
111
112
113 static void add_to_cache (struct dir_cache_entry * p)
114 {
115 p->prev = NULL;
116 p->next = first;
117 if (first)
118 first->prev = p;
119 if (!last)
120 last = p;
121 first = p;
122 }
123
124
125
126
127 static void add_to_queue (int queue, struct dir_cache_entry * p)
128 {
129 p->queue_prev = NULL;
130 p->queue_next = queue_head[queue];
131 if (queue_head[queue])
132 queue_head[queue]->queue_prev = p;
133 if (!queue_tail[queue])
134 queue_tail[queue] = p;
135 queue_head[queue] = p;
136 }
137
138
139
140
141 static void remove_from_cache (struct dir_cache_entry * p)
142 {
143 if (p->prev)
144 p->prev->next = p->next;
145 else
146 first = p->next;
147 if (p->next)
148 p->next->prev = p->prev;
149 else
150 last = p->prev;
151 }
152
153
154
155
156 static void remove_from_queue (int queue, struct dir_cache_entry * p)
157 {
158 if (p->queue_prev)
159 p->queue_prev->queue_next = p->queue_next;
160 else
161 queue_head[queue] = p->queue_next;
162 if (p->queue_next)
163 p->queue_next->queue_prev = p->queue_prev;
164 else
165 queue_tail[queue] = p->queue_prev;
166 }
167
168
169
170
171
172 void ext2_dcache_invalidate (unsigned short dev)
173 {
174 struct dir_cache_entry * p;
175 struct dir_cache_entry * p2;
176
177 if (!cache_initialized)
178 init_cache ();
179 for (p = first; p != NULL; p = p2) {
180 p2 = p->next;
181 if (p->dev == dev) {
182 remove_from_cache (p);
183 remove_from_queue (hash (p->dev, p->dir), p);
184 p->next = first_free;
185 first_free = p;
186 }
187 }
188 #ifdef EXT2FS_DEBUG_CACHE
189 show_cache ("dcache_invalidate");
190 #endif
191 }
192
193
194
195
196 unsigned long ext2_dcache_lookup (unsigned short dev, unsigned long dir,
197 const char * name, int len)
198 {
199 char our_name[EXT2_NAME_LEN];
200 int queue;
201 struct dir_cache_entry * p;
202
203 if (!cache_initialized)
204 init_cache ();
205 if (len > EXT2_NAME_LEN)
206 len = EXT2_NAME_LEN;
207 memcpy (our_name, (char *) name, len);
208 our_name[len] = '\0';
209 #ifdef EXT2FS_DEBUG_CACHE
210 printk ("dcache_lookup (%04x, %d, %s, %d)\n", dev, dir, our_name, len);
211 #endif
212 queue = hash (dev, dir);
213 if ((p = find_name (queue, dev, dir, our_name, len))) {
214 if (p != first) {
215 remove_from_cache (p);
216 add_to_cache (p);
217 }
218 if (p != queue_head[queue]) {
219 remove_from_queue (queue, p);
220 add_to_queue (queue, p);
221 }
222 #ifdef EXT2FS_DEBUG_CACHE
223 hits++;
224 printk ("dcache_lookup: %s,hit,inode=%d,hits=%d,misses=%d\n",
225 our_name, p->ino, hits, misses);
226 show_cache ("dcache_lookup");
227 #endif
228 return p->ino;
229 } else {
230 #ifdef EXT2FS_DEBUG_CACHE
231 misses++;
232 printk ("dcache_lookup: %s,miss,hits=%d,misses=%d\n",
233 our_name, hits, misses);
234 show_cache ("dcache_lookup");
235 #endif
236 return 0;
237 }
238 }
239
240
241
242
243
244
245
246 void ext2_dcache_add (unsigned short dev, unsigned long dir, const char * name,
247 int len, int ino)
248 {
249 struct dir_cache_entry * p;
250 int queue;
251
252 if (!cache_initialized)
253 init_cache ();
254 #ifdef EXT2FS_DEBUG_CACHE
255 printk ("dcache_add (%04x, %d, %s, %d, %d)\n",
256 dev, dir, name, len, ino);
257 #endif
258 if (len > EXT2_NAME_LEN)
259 len = EXT2_NAME_LEN;
260 queue = hash (dev, dir);
261 if ((p = find_name (queue, dev, dir, name, len))) {
262 p->dir = dir;
263 p->ino = ino;
264 if (p != first) {
265 remove_from_cache (p);
266 add_to_cache (p);
267 }
268 if (p != queue_head[queue]) {
269 remove_from_queue (queue, p);
270 add_to_queue (queue, p);
271 }
272 } else {
273 if (first_free) {
274 p = first_free;
275 first_free = p->next;
276 } else {
277 if (!last)
278 panic ("dcache_add: last == NULL\n");
279 else {
280 p = last;
281 last = p->prev;
282 if (last)
283 last->next = NULL;
284 remove_from_queue (hash (p->dev, p->dir), p);
285 }
286 }
287 p->dev = dev;
288 p->dir = dir;
289 p->ino = ino;
290 strncpy (p->name, name, len);
291 p->len = len;
292 p->name[len] = '\0';
293 add_to_cache (p);
294 add_to_queue (queue, p);
295 }
296 #ifdef EXT2FS_DEBUG_CACHE
297 show_cache ("dcache_add");
298 #endif
299 }
300
301
302
303
304
305
306 void ext2_dcache_remove (unsigned short dev, unsigned long dir,
307 const char * name, int len)
308 {
309 struct dir_cache_entry * p;
310 int queue;
311
312 if (!cache_initialized)
313 init_cache ();
314 #ifdef EXT2FS_DEBUG_CACHE
315 printk ("dcache_remove (%04x, %d, %s, %d)\n", dev, dir, name, len);
316 #endif
317 if (len > EXT2_NAME_LEN)
318 len = EXT2_NAME_LEN;
319 queue = hash (dev, dir);
320 if ((p = find_name (queue, dev, dir, name, len))) {
321 remove_from_cache (p);
322 remove_from_queue (queue, p);
323 p->next = first_free;
324 first_free = p;
325 }
326 #ifdef EXT2FS_DEBUG_CACHE
327 show_cache ("dcache_remove");
328 #endif
329 }
330
331 #endif