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