This source file includes following definitions.
- remove_lru
- add_lru
- update_lru
- namehash
- remove_hash
- add_hash
- find_entry
- move_to_level2
- dcache_lookup
- dcache_add
- name_cache_init
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 #include <stddef.h>
22
23 #include <linux/fs.h>
24 #include <linux/string.h>
25
26
27
28
29
30
31 #define DCACHE_NAME_LEN 15
32 #define DCACHE_SIZE 128
33
34 struct hash_list {
35 struct dir_cache_entry * next;
36 struct dir_cache_entry * prev;
37 };
38
39
40
41
42 struct dir_cache_entry {
43 struct hash_list h;
44 unsigned long dev;
45 unsigned long dir;
46 unsigned long version;
47 unsigned long ino;
48 unsigned char name_len;
49 char name[DCACHE_NAME_LEN];
50 struct dir_cache_entry ** lru_head;
51 struct dir_cache_entry * next_lru, * prev_lru;
52 };
53
54 #define COPYDATA(de, newde) \
55 memcpy((void *) &newde->dev, (void *) &de->dev, \
56 4*sizeof(unsigned long) + 1 + DCACHE_NAME_LEN)
57
58 static struct dir_cache_entry level1_cache[DCACHE_SIZE];
59 static struct dir_cache_entry level2_cache[DCACHE_SIZE];
60
61
62
63
64
65 static struct dir_cache_entry * level1_head;
66 static struct dir_cache_entry * level2_head;
67
68
69
70
71
72 #define DCACHE_HASH_QUEUES 19
73 #define hash_fn(dev,dir,namehash) (((dev) ^ (dir) ^ (namehash)) % DCACHE_HASH_QUEUES)
74
75 static struct hash_list hash_table[DCACHE_HASH_QUEUES];
76
77 static inline void remove_lru(struct dir_cache_entry * de)
78 {
79 de->next_lru->prev_lru = de->prev_lru;
80 de->prev_lru->next_lru = de->next_lru;
81 }
82
83 static inline void add_lru(struct dir_cache_entry * de, struct dir_cache_entry *head)
84 {
85 de->next_lru = head;
86 de->prev_lru = head->prev_lru;
87 de->prev_lru->next_lru = de;
88 head->prev_lru = de;
89 }
90
91 static inline void update_lru(struct dir_cache_entry * de)
92 {
93 if (de == *de->lru_head)
94 *de->lru_head = de->next_lru;
95 else {
96 remove_lru(de);
97 add_lru(de,*de->lru_head);
98 }
99 }
100
101
102
103
104
105 static inline unsigned long namehash(const char * name, int len)
106 {
107 return len * *(unsigned char *) name;
108 }
109
110
111
112
113 static inline void remove_hash(struct dir_cache_entry * de)
114 {
115 if (de->h.next) {
116 de->h.next->h.prev = de->h.prev;
117 de->h.prev->h.next = de->h.next;
118 de->h.next = NULL;
119 }
120 }
121
122 static inline void add_hash(struct dir_cache_entry * de, struct hash_list * hash)
123 {
124 de->h.next = hash->next;
125 de->h.prev = (struct dir_cache_entry *) hash;
126 hash->next->h.prev = de;
127 hash->next = de;
128 }
129
130
131
132
133 static struct dir_cache_entry * find_entry(struct inode * dir, const char * name, int len, struct hash_list * hash)
134 {
135 struct dir_cache_entry * de = hash->next;
136
137 for (de = hash->next ; de != (struct dir_cache_entry *) hash ; de = de->h.next) {
138 if (de->dev != dir->i_dev)
139 continue;
140 if (de->dir != dir->i_ino)
141 continue;
142 if (de->version != dir->i_version)
143 continue;
144 if (de->name_len != len)
145 continue;
146 if (memcmp(de->name, name, len))
147 continue;
148 return de;
149 }
150 return NULL;
151 }
152
153
154
155
156
157 static inline void move_to_level2(struct dir_cache_entry * old_de, struct hash_list * hash)
158 {
159 struct dir_cache_entry * de;
160
161 if (old_de->lru_head == &level2_head) {
162 update_lru(old_de);
163 return;
164 }
165 de = level2_head;
166 level2_head = de->next_lru;
167 remove_hash(de);
168 COPYDATA(old_de, de);
169 add_hash(de, hash);
170 }
171
172 int dcache_lookup(struct inode * dir, const char * name, int len, unsigned long * ino)
173 {
174 struct hash_list * hash;
175 struct dir_cache_entry *de;
176
177 if (len > DCACHE_NAME_LEN)
178 return 0;
179 hash = hash_table + hash_fn(dir->i_dev, dir->i_ino, namehash(name,len));
180 de = find_entry(dir, name, len, hash);
181 if (!de)
182 return 0;
183 *ino = de->ino;
184 move_to_level2(de, hash);
185 return 1;
186 }
187
188 void dcache_add(struct inode * dir, const char * name, int len, unsigned long ino)
189 {
190 struct hash_list * hash;
191 struct dir_cache_entry *de;
192
193 if (len > DCACHE_NAME_LEN)
194 return;
195 hash = hash_table + hash_fn(dir->i_dev, dir->i_ino, namehash(name,len));
196 if ((de = find_entry(dir, name, len, hash)) != NULL) {
197 de->ino = ino;
198 update_lru(de);
199 return;
200 }
201 de = level1_head;
202 level1_head = de->next_lru;
203 remove_hash(de);
204 de->dev = dir->i_dev;
205 de->dir = dir->i_ino;
206 de->version = dir->i_version;
207 de->ino = ino;
208 de->name_len = len;
209 memcpy(de->name, name, len);
210 add_hash(de, hash);
211 }
212
213 unsigned long name_cache_init(unsigned long mem_start, unsigned long mem_end)
214 {
215 int i;
216 struct dir_cache_entry * p;
217
218
219
220
221 p = level1_cache;
222 do {
223 p[1].prev_lru = p;
224 p[0].next_lru = p+1;
225 p[0].lru_head = &level1_head;
226 } while (++p < level1_cache + DCACHE_SIZE-1);
227 level1_cache[0].prev_lru = p;
228 p[0].next_lru = &level1_cache[0];
229 p[0].lru_head = &level1_head;
230 level1_head = level1_cache;
231
232
233
234
235 p = level2_cache;
236 do {
237 p[1].prev_lru = p;
238 p[0].next_lru = p+1;
239 p[0].lru_head = &level2_head;
240 } while (++p < level2_cache + DCACHE_SIZE-1);
241 level2_cache[0].prev_lru = p;
242 p[0].next_lru = &level2_cache[0];
243 p[0].lru_head = &level2_head;
244 level2_head = level2_cache;
245
246
247
248
249 for (i = 0 ; i < DCACHE_HASH_QUEUES ; i++)
250 hash_table[i].next = hash_table[i].next =
251 (struct dir_cache_entry *) &hash_table[i];
252 return mem_start;
253 }