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 64
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 unsigned long dcache_lookup(struct inode * dir, const char * name, int len)
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 move_to_level2(de, hash);
184 return de->ino;
185 }
186
187 void dcache_add(struct inode * dir, const char * name, int len, unsigned long ino)
188 {
189 struct hash_list * hash;
190 struct dir_cache_entry *de;
191
192 if (len > DCACHE_NAME_LEN)
193 return;
194 hash = hash_table + hash_fn(dir->i_dev, dir->i_ino, namehash(name,len));
195 if ((de = find_entry(dir, name, len, hash)) != NULL) {
196 update_lru(de);
197 return;
198 }
199 de = level1_head;
200 level1_head = de->next_lru;
201 remove_hash(de);
202 de->dev = dir->i_dev;
203 de->dir = dir->i_ino;
204 de->version = dir->i_version;
205 de->ino = ino;
206 de->name_len = len;
207 memcpy(de->name, name, len);
208 add_hash(de, hash);
209 }
210
211 unsigned long name_cache_init(unsigned long mem_start, unsigned long mem_end)
212 {
213 int i;
214 struct dir_cache_entry * p;
215
216
217
218
219 p = level1_cache;
220 do {
221 p[1].prev_lru = p;
222 p[0].next_lru = p+1;
223 p[0].lru_head = &level1_head;
224 } while (++p < level1_cache + DCACHE_SIZE-1);
225 level1_cache[0].prev_lru = p;
226 p[0].next_lru = &level1_cache[0];
227 p[0].lru_head = &level1_head;
228 level1_head = level1_cache;
229
230
231
232
233 p = level2_cache;
234 do {
235 p[1].prev_lru = p;
236 p[0].next_lru = p+1;
237 p[0].lru_head = &level2_head;
238 } while (++p < level2_cache + DCACHE_SIZE-1);
239 level2_cache[0].prev_lru = p;
240 p[0].next_lru = &level2_cache[0];
241 p[0].lru_head = &level2_head;
242 level2_head = level2_cache;
243
244
245
246
247 for (i = 0 ; i < DCACHE_HASH_QUEUES ; i++)
248 hash_table[i].next = hash_table[i].next =
249 (struct dir_cache_entry *) &hash_table[i];
250 return mem_start;
251 }