12 struct cache_entry_list *where;
13 struct cache_entry *next;
14 struct cache_entry *prev;
18 struct cache_entry_list {
19 struct cache_entry *first, *last;
24 struct cache_entry_list t1,b1,t2,b2,*insert;
25 int size,id_size,entry_size;
33 cache_entry_dump(struct cache *cache, struct cache_entry *entry)
36 dbg(0,"Usage: %d size %d\n",entry->usage, entry->size);
41 for (i = 0 ; i < size ; i++) {
42 dbg(0,"0x%x\n", entry->id[i]);
47 cache_list_dump(char *str, struct cache *cache, struct cache_entry_list *list)
49 struct cache_entry *first=list->first;
50 dbg(0,"dump %s %d\n",str, list->size);
52 cache_entry_dump(cache, first);
58 cache_hash4(gconstpointer key)
65 cache_hash20(gconstpointer key)
68 return id[0]^id[1]^id[2]^id[3]^id[4];
72 cache_equal4(gconstpointer a, gconstpointer b)
77 return ida[0] == idb[0];
81 cache_equal20(gconstpointer a, gconstpointer b)
86 return(ida[0] == idb[0] &&
94 cache_new(int id_size, int size)
96 struct cache *cache=g_new0(struct cache, 1);
98 cache->id_size=id_size/4;
99 cache->entry_size=cache->id_size*sizeof(int)+sizeof(struct cache_entry);
103 cache->hash=g_hash_table_new(cache_hash4, cache_equal4);
106 cache->hash=g_hash_table_new(cache_hash20, cache_equal20);
109 dbg(0,"cache with id_size of %d not supported\n", id_size);
117 cache_insert_mru(struct cache *cache, struct cache_entry_list *list, struct cache_entry *entry)
120 entry->next=list->first;
123 entry->next->prev=entry;
127 list->size+=entry->size;
129 g_hash_table_insert(cache->hash, (gpointer)entry->id, entry);
133 cache_remove_from_list(struct cache_entry_list *list, struct cache_entry *entry)
136 entry->prev->next=entry->next;
138 list->first=entry->next;
140 entry->next->prev=entry->prev;
142 list->last=entry->prev;
143 list->size-=entry->size;
147 cache_remove(struct cache *cache, struct cache_entry *entry)
149 dbg(1,"remove 0x%x 0x%x 0x%x 0x%x 0x%x\n", entry->id[0], entry->id[1], entry->id[2], entry->id[3], entry->id[4]);
150 g_hash_table_remove(cache->hash, (gpointer)(entry->id));
154 static struct cache_entry *
155 cache_remove_lru_helper(struct cache_entry_list *list)
157 struct cache_entry *last=list->last;
160 list->last=last->prev;
162 last->prev->next=NULL;
165 list->size-=last->size;
169 static struct cache_entry *
170 cache_remove_lru(struct cache *cache, struct cache_entry_list *list)
172 struct cache_entry *last;
174 while (list->last && list->last->usage && seen < list->size) {
175 last=cache_remove_lru_helper(list);
176 cache_insert_mru(NULL, list, last);
180 if (! last || last->usage || seen >= list->size)
182 dbg(1,"removing %d\n", last->id[0]);
183 cache_remove_lru_helper(list);
185 cache_remove(cache, last);
192 cache_entry_new(struct cache *cache, void *id, int size)
194 size+=cache->entry_size;
196 struct cache_entry *ret=(struct cache_entry *)g_malloc0(size);
199 memcpy(ret->id, id, cache->id_size*sizeof(int));
200 return &ret->id[cache->id_size];
204 cache_entry_destroy(struct cache *cache, void *data)
206 struct cache_entry *entry=(struct cache_entry *)((char *)data-cache->entry_size);
207 dbg(1,"destroy 0x%x 0x%x 0x%x 0x%x 0x%x\n", entry->id[0], entry->id[1], entry->id[2], entry->id[3], entry->id[4]);
211 static struct cache_entry *
212 cache_trim(struct cache *cache, struct cache_entry *entry)
214 dbg(1,"trim 0x%x 0x%x 0x%x 0x%x 0x%x\n", entry->id[0], entry->id[1], entry->id[2], entry->id[3], entry->id[4]);
215 return g_realloc(entry, cache->entry_size);
218 static struct cache_entry *
219 cache_move(struct cache *cache, struct cache_entry_list *old, struct cache_entry_list *new)
221 struct cache_entry *entry;
222 entry=cache_remove_lru(NULL, old);
225 entry=cache_trim(cache, entry);
226 cache_insert_mru(NULL, new, entry);
231 cache_replace(struct cache *cache)
233 if (cache->t1.size >= MAX(1,cache->t1_target)) {
234 dbg(1,"replace 12\n");
235 if (!cache_move(cache, &cache->t1, &cache->b1))
236 cache_move(cache, &cache->t2, &cache->b2);
238 dbg(1,"replace t2\n");
239 if (!cache_move(cache, &cache->t2, &cache->b2))
240 cache_move(cache, &cache->t1, &cache->b1);
252 cache_flush(struct cache *cache, void *id)
254 struct cache_entry *entry=g_hash_table_lookup(cache->hash, id);
256 cache_remove(cache, entry);
261 cache_lookup(struct cache *cache, void *id) {
262 struct cache_entry *entry;
264 dbg(1,"get %d\n", ((int *)id)[0]);
265 entry=g_hash_table_lookup(cache->hash, id);
267 cache->insert=&cache->t1;
271 dbg(1,"not in cache\n");
274 dbg(1,"found 0x%x 0x%x 0x%x 0x%x 0x%x\n", entry->id[0], entry->id[1], entry->id[2], entry->id[3], entry->id[4]);
275 if (entry->where == &cache->t1 || entry->where == &cache->t2) {
276 cache->hits+=entry->size;
278 if (entry->where == &cache->t1)
283 dbg(1,"in cache %s\n", entry->where == &cache->t1 ? "T1" : "T2");
284 cache_remove_from_list(entry->where, entry);
285 cache_insert_mru(NULL, &cache->t2, entry);
287 return &entry->id[cache->id_size];
289 if (entry->where == &cache->b1) {
293 dbg(1,"in phantom cache B1\n");
294 cache->t1_target=MIN(cache->t1_target+MAX(cache->b2.size/cache->b1.size, 1),cache->size);
295 cache_remove_from_list(&cache->b1, entry);
296 } else if (entry->where == &cache->b2) {
300 dbg(1,"in phantom cache B2\n");
301 cache->t1_target=MAX(cache->t1_target-MAX(cache->b1.size/cache->b2.size, 1),0);
302 cache_remove_from_list(&cache->b2, entry);
304 dbg(0,"**ERROR** invalid where\n");
306 cache_replace(cache);
307 cache_remove(cache, entry);
308 cache->insert=&cache->t2;
314 cache_insert(struct cache *cache, void *data)
316 struct cache_entry *entry=(struct cache_entry *)((char *)data-cache->entry_size);
317 dbg(1,"insert 0x%x 0x%x 0x%x 0x%x 0x%x\n", entry->id[0], entry->id[1], entry->id[2], entry->id[3], entry->id[4]);
318 if (cache->insert == &cache->t1) {
319 if (cache->t1.size + cache->b1.size >= cache->size) {
320 if (cache->t1.size < cache->size) {
321 cache_remove_lru(cache, &cache->b1);
322 cache_replace(cache);
324 cache_remove_lru(cache, &cache->t1);
327 if (cache->t1.size + cache->t2.size + cache->b1.size + cache->b2.size >= cache->size) {
328 if (cache->t1.size + cache->t2.size + cache->b1.size + cache->b2.size >= 2*cache->size)
329 cache_remove_lru(cache, &cache->b2);
330 cache_replace(cache);
334 cache_insert_mru(cache, cache->insert, entry);
338 cache_insert_new(struct cache *cache, void *id, int size)
340 void *data=cache_entry_new(cache, id, size);
341 cache_insert(cache, data);
346 cache_stats(struct cache *cache)
348 dbg(0,"hits %d misses %d hitratio %d size %d entry_size %d id_size %d T1 target %d\n", cache->hits, cache->misses, cache->hits*100/(cache->hits+cache->misses), cache->size, cache->entry_size, cache->id_size, cache->t1_target);
349 dbg(0,"T1:%d B1:%d T2:%d B2:%d\n", cache->t1.size, cache->b1.size, cache->t2.size, cache->b2.size);
355 cache_dump(struct cache *cache)
357 struct cache_entry *first;
358 first=cache->t1.first;
360 cache_list_dump("T1", cache, &cache->t1);
361 cache_list_dump("B1", cache, &cache->b1);
362 cache_list_dump("T2", cache, &cache->t2);
363 cache_list_dump("B2", cache, &cache->b2);