navit/navit/cache.c

#include "glib_slice.h"
#ifdef DEBUG_CACHE
#include <stdio.h>
#endif
#include <string.h>
#include "debug.h"
#include "cache.h"

struct cache_entry {
        int usage;
        int size;
        struct cache_entry_list *where;
        struct cache_entry *next;
        struct cache_entry *prev;
        int id[0];
};

struct cache_entry_list {
        struct cache_entry *first, *last;
        int size;
};

struct cache {
        struct cache_entry_list t1,b1,t2,b2,*insert;
        int size,id_size,entry_size;
        int t1_target;
        int misses;
        int hits;
        GHashTable *hash;
};

static void
cache_entry_dump(struct cache *cache, struct cache_entry *entry)
{
        int i,size;
        dbg(0,"Usage: %d size %d\n",entry->usage, entry->size);
        if (cache)
                size=cache->id_size;
        else
                size=5;
        for (i = 0 ; i < size ; i++) {
                dbg(0,"0x%x\n", entry->id[i]);
        }
}

static void
cache_list_dump(char *str, struct cache *cache, struct cache_entry_list *list)
{
        struct cache_entry *first=list->first;
        dbg(0,"dump %s %d\n",str, list->size);
        while (first) {
                cache_entry_dump(cache, first);
                first=first->next;
        }
}

static guint
cache_hash4(gconstpointer key)
{
        int *id=(int *)key;
        return id[0];
}

static guint
cache_hash20(gconstpointer key)
{
        int *id=(int *)key;
        return id[0]^id[1]^id[2]^id[3]^id[4];
}

static gboolean
cache_equal4(gconstpointer a, gconstpointer b)
{
        int *ida=(int *)a;
        int *idb=(int *)b;

        return ida[0] == idb[0];
}

static gboolean
cache_equal20(gconstpointer a, gconstpointer b)
{
        int *ida=(int *)a;
        int *idb=(int *)b;

        return(ida[0] == idb[0] &&
               ida[1] == idb[1] &&
               ida[2] == idb[2] &&
               ida[3] == idb[3] &&
               ida[4] == idb[4]);
}

struct cache *
cache_new(int id_size, int size)
{
        struct cache *cache=g_new0(struct cache, 1);
        
        cache->id_size=id_size/4;
        cache->entry_size=cache->id_size*sizeof(int)+sizeof(struct cache_entry);
        cache->size=size;
        switch (id_size) {
        case 4:
                cache->hash=g_hash_table_new(cache_hash4, cache_equal4);
                break;
        case 20:
                cache->hash=g_hash_table_new(cache_hash20, cache_equal20);
                break;
        default:
                dbg(0,"cache with id_size of %d not supported\n", id_size);
                g_free(cache);
                cache=NULL;
        }
        return cache;
}

static void
cache_insert_mru(struct cache *cache, struct cache_entry_list *list, struct cache_entry *entry)
{
        entry->prev=NULL;
        entry->next=list->first;
        entry->where=list;
        if (entry->next)
                entry->next->prev=entry;
        list->first=entry;
        if (! list->last)
                list->last=entry;
        list->size+=entry->size;
        if (cache) 
                g_hash_table_insert(cache->hash, (gpointer)entry->id, entry);
}

static void
cache_remove_from_list(struct cache_entry_list *list, struct cache_entry *entry)
{
        if (entry->prev) 
                entry->prev->next=entry->next;
        else
                list->first=entry->next;
        if (entry->next)
                entry->next->prev=entry->prev;
        else
                list->last=entry->prev;
        list->size-=entry->size;
}

static void
cache_remove(struct cache *cache, struct cache_entry *entry)
{
        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]);
        g_hash_table_remove(cache->hash, (gpointer)(entry->id));
        g_slice_free1(entry->size, entry);
}

static struct cache_entry *
cache_remove_lru_helper(struct cache_entry_list *list)
{
        struct cache_entry *last=list->last;
        if (! last)
                return NULL;
        list->last=last->prev;
        if (last->prev)
                last->prev->next=NULL;
        else
                list->first=NULL;
        list->size-=last->size;
        return last;
}

static struct cache_entry *
cache_remove_lru(struct cache *cache, struct cache_entry_list *list)
{
        struct cache_entry *last;
        int seen=0;
        while (list->last && list->last->usage && seen < list->size) {
                last=cache_remove_lru_helper(list);
                cache_insert_mru(NULL, list, last);
                seen+=last->size;
        }
        last=list->last;
        if (! last || last->usage || seen >= list->size) 
                return NULL;
        dbg(1,"removing %d\n", last->id[0]);
        cache_remove_lru_helper(list);
        if (cache) {
                cache_remove(cache, last);
                return NULL;
        }
        return last;
}

void *
cache_entry_new(struct cache *cache, void *id, int size)
{
        struct cache_entry *ret;
        size+=cache->entry_size;
        cache->misses+=size;
        ret=(struct cache_entry *)g_slice_alloc0(size);
        ret->size=size;
        ret->usage=1;
        memcpy(ret->id, id, cache->id_size*sizeof(int));
        return &ret->id[cache->id_size];
}

void
cache_entry_destroy(struct cache *cache, void *data)
{
        struct cache_entry *entry=(struct cache_entry *)((char *)data-cache->entry_size);
        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]);
        entry->usage--;
}

static struct cache_entry *
cache_trim(struct cache *cache, struct cache_entry *entry)
{
        struct cache_entry *new_entry;
        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]);
        dbg(1,"Trim %x from %d -> %d\n", entry->id[0], entry->size, cache->size);
        if ( cache->entry_size < entry->size )
        {
            g_hash_table_remove(cache->hash, (gpointer)(entry->id));

            new_entry = g_slice_alloc0(cache->entry_size);
            memcpy(new_entry, entry, cache->entry_size);
            g_slice_free1( entry->size, entry);
            new_entry->size = cache->entry_size;

            g_hash_table_insert(cache->hash, (gpointer)new_entry->id, new_entry);
        }
        else
        {
            new_entry = entry; 
        }
        
        return new_entry;
}

static struct cache_entry *
cache_move(struct cache *cache, struct cache_entry_list *old, struct cache_entry_list *new)
{
        struct cache_entry *entry;
        entry=cache_remove_lru(NULL, old);
        if (! entry)
                return NULL;
        entry=cache_trim(cache, entry);
        cache_insert_mru(NULL, new, entry);
        return entry;
}

static int
cache_replace(struct cache *cache)
{
        if (cache->t1.size >= MAX(1,cache->t1_target)) {
                dbg(1,"replace 12\n");
                if (!cache_move(cache, &cache->t1, &cache->b1))
                        cache_move(cache, &cache->t2, &cache->b2);
        } else {
                dbg(1,"replace t2\n");
                if (!cache_move(cache, &cache->t2, &cache->b2))
                        cache_move(cache, &cache->t1, &cache->b1);
        }
#if 0
        if (! entry) {
                cache_dump(cache);
                exit(0);
        }
#endif
        return 1;
}

void
cache_flush(struct cache *cache, void *id)
{
        struct cache_entry *entry=g_hash_table_lookup(cache->hash, id);
        if (entry) {
                cache_remove_from_list(entry->where, entry);
                cache_remove(cache, entry);
        }
}

void
cache_flush_data(struct cache *cache, void *data)
{
        struct cache_entry *entry=(struct cache_entry *)((char *)data-cache->entry_size);
        if (entry) {
                cache_remove_from_list(entry->where, entry);
                cache_remove(cache, entry);
        }
}


void *
cache_lookup(struct cache *cache, void *id) {
        struct cache_entry *entry;

        dbg(1,"get %d\n", ((int *)id)[0]);
        entry=g_hash_table_lookup(cache->hash, id);
        if (entry == NULL) {
                cache->insert=&cache->t1;
#ifdef DEBUG_CACHE
                fprintf(stderr,"-");
#endif
                dbg(1,"not in cache\n");
                return NULL;
        }
        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]);
        if (entry->where == &cache->t1 || entry->where == &cache->t2) {
                cache->hits+=entry->size;
#ifdef DEBUG_CACHE
                if (entry->where == &cache->t1)
                        fprintf(stderr,"h");
                else
                        fprintf(stderr,"H");
#endif
                dbg(1,"in cache %s\n", entry->where == &cache->t1 ? "T1" : "T2");
                cache_remove_from_list(entry->where, entry);
                cache_insert_mru(NULL, &cache->t2, entry);
                entry->usage++;
                return &entry->id[cache->id_size];
        } else {
                if (entry->where == &cache->b1) {
#ifdef DEBUG_CACHE
                        fprintf(stderr,"m");
#endif
                        dbg(1,"in phantom cache B1\n");
                        cache->t1_target=MIN(cache->t1_target+MAX(cache->b2.size/cache->b1.size, 1),cache->size);
                        cache_remove_from_list(&cache->b1, entry);
                } else if (entry->where == &cache->b2) {
#ifdef DEBUG_CACHE
                        fprintf(stderr,"M");
#endif
                        dbg(1,"in phantom cache B2\n");
                        cache->t1_target=MAX(cache->t1_target-MAX(cache->b1.size/cache->b2.size, 1),0);
                        cache_remove_from_list(&cache->b2, entry);
                } else {
                        dbg(0,"**ERROR** invalid where\n");
                }
                cache_replace(cache);
                cache_remove(cache, entry);
                cache->insert=&cache->t2;
                return NULL;
        }
}

void
cache_insert(struct cache *cache, void *data)
{
        struct cache_entry *entry=(struct cache_entry *)((char *)data-cache->entry_size);
        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]);
        if (cache->insert == &cache->t1) {
                if (cache->t1.size + cache->b1.size >= cache->size) {
                        if (cache->t1.size < cache->size) {
                                cache_remove_lru(cache, &cache->b1);
                                cache_replace(cache);
                        } else {
                                cache_remove_lru(cache, &cache->t1);
                        }
                } else {
                        if (cache->t1.size + cache->t2.size + cache->b1.size + cache->b2.size >= cache->size) {
                                if (cache->t1.size + cache->t2.size + cache->b1.size + cache->b2.size >= 2*cache->size) 
                                        cache_remove_lru(cache, &cache->b2);
                                cache_replace(cache);
                        }
                }
        }
        cache_insert_mru(cache, cache->insert, entry);
}

void *
cache_insert_new(struct cache *cache, void *id, int size)
{
        void *data=cache_entry_new(cache, id, size);
        cache_insert(cache, data);
        return data;    
}

static void
cache_stats(struct cache *cache)
{
        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);
        dbg(0,"T1:%d B1:%d T2:%d B2:%d\n", cache->t1.size, cache->b1.size, cache->t2.size, cache->b2.size);
        cache->hits=0;
        cache->misses=0;
}

void
cache_dump(struct cache *cache)
{
        struct cache_entry *first;
        first=cache->t1.first;
        cache_stats(cache);
        cache_list_dump("T1", cache, &cache->t1);
        cache_list_dump("B1", cache, &cache->b1);
        cache_list_dump("T2", cache, &cache->t2);
        cache_list_dump("B2", cache, &cache->b2);
        dbg(0,"dump end\n");
}

1	zoff99	2	#include "glib_slice.h"
2			#ifdef DEBUG_CACHE
3			#include <stdio.h>
4			#endif
5			#include <string.h>
6			#include "debug.h"
7			#include "cache.h"
8
9			struct cache_entry {
10			int usage;
11			int size;
12			struct cache_entry_list *where;
13			struct cache_entry *next;
14			struct cache_entry *prev;
15			int id[0];
16			};
17
18			struct cache_entry_list {
19			struct cache_entry first, last;
20			int size;
21			};
22
23			struct cache {
24			struct cache_entry_list t1,b1,t2,b2,*insert;
25			int size,id_size,entry_size;
26			int t1_target;
27			int misses;
28			int hits;
29			GHashTable *hash;
30			};
31
32			static void
33			cache_entry_dump(struct cache cache, struct cache_entry entry)
34			{
35			int i,size;
36			dbg(0,"Usage: %d size %d\n",entry->usage, entry->size);
37			if (cache)
38			size=cache->id_size;
39			else
40			size=5;
41			for (i = 0 ; i < size ; i++) {
42			dbg(0,"0x%x\n", entry->id[i]);
43			}
44			}
45
46			static void
47			cache_list_dump(char str, struct cache cache, struct cache_entry_list *list)
48			{
49			struct cache_entry *first=list->first;
50			dbg(0,"dump %s %d\n",str, list->size);
51			while (first) {
52			cache_entry_dump(cache, first);
53			first=first->next;
54			}
55			}
56
57			static guint
58			cache_hash4(gconstpointer key)
59			{
60			int id=(int )key;
61			return id[0];
62			}
63
64			static guint
65			cache_hash20(gconstpointer key)
66			{
67			int id=(int )key;
68			return id[0]^id[1]^id[2]^id[3]^id[4];
69			}
70
71			static gboolean
72			cache_equal4(gconstpointer a, gconstpointer b)
73			{
74			int ida=(int )a;
75			int idb=(int )b;
76
77			return ida[0] == idb[0];
78			}
79
80			static gboolean
81			cache_equal20(gconstpointer a, gconstpointer b)
82			{
83			int ida=(int )a;
84			int idb=(int )b;
85
86			return(ida[0] == idb[0] &&
87			ida[1] == idb[1] &&
88			ida[2] == idb[2] &&
89			ida[3] == idb[3] &&
90			ida[4] == idb[4]);
91			}
92
93			struct cache *
94			cache_new(int id_size, int size)
95			{
96			struct cache *cache=g_new0(struct cache, 1);
97
98			cache->id_size=id_size/4;
99			cache->entry_size=cache->id_size*sizeof(int)+sizeof(struct cache_entry);
100			cache->size=size;
101			switch (id_size) {
102			case 4:
103			cache->hash=g_hash_table_new(cache_hash4, cache_equal4);
104			break;
105			case 20:
106			cache->hash=g_hash_table_new(cache_hash20, cache_equal20);
107			break;
108			default:
109			dbg(0,"cache with id_size of %d not supported\n", id_size);
110			g_free(cache);
111			cache=NULL;
112			}
113			return cache;
114			}
115
116			static void
117			cache_insert_mru(struct cache cache, struct cache_entry_list list, struct cache_entry *entry)
118			{
119			entry->prev=NULL;
120			entry->next=list->first;
121			entry->where=list;
122			if (entry->next)
123			entry->next->prev=entry;
124			list->first=entry;
125			if (! list->last)
126			list->last=entry;
127			list->size+=entry->size;
128			if (cache)
129			g_hash_table_insert(cache->hash, (gpointer)entry->id, entry);
130			}
131
132			static void
133			cache_remove_from_list(struct cache_entry_list list, struct cache_entry entry)
134			{
135			if (entry->prev)
136			entry->prev->next=entry->next;
137			else
138			list->first=entry->next;
139			if (entry->next)
140			entry->next->prev=entry->prev;
141			else
142			list->last=entry->prev;
143			list->size-=entry->size;
144			}
145
146			static void
147			cache_remove(struct cache cache, struct cache_entry entry)
148			{
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));
151			g_slice_free1(entry->size, entry);
152			}
153
154			static struct cache_entry *
155			cache_remove_lru_helper(struct cache_entry_list *list)
156			{
157			struct cache_entry *last=list->last;
158			if (! last)
159			return NULL;
160			list->last=last->prev;
161			if (last->prev)
162			last->prev->next=NULL;
163			else
164			list->first=NULL;
165			list->size-=last->size;
166			return last;
167			}
168
169			static struct cache_entry *
170			cache_remove_lru(struct cache cache, struct cache_entry_list list)
171			{
172			struct cache_entry *last;
173			int seen=0;
174			while (list->last && list->last->usage && seen < list->size) {
175			last=cache_remove_lru_helper(list);
176			cache_insert_mru(NULL, list, last);
177			seen+=last->size;
178			}
179			last=list->last;
180			if (! last \|\| last->usage \|\| seen >= list->size)
181			return NULL;
182			dbg(1,"removing %d\n", last->id[0]);
183			cache_remove_lru_helper(list);
184			if (cache) {
185			cache_remove(cache, last);
186			return NULL;
187			}
188			return last;
189			}
190
191			void *
192			cache_entry_new(struct cache cache, void id, int size)
193			{
194			struct cache_entry *ret;
195			size+=cache->entry_size;
196			cache->misses+=size;
197			ret=(struct cache_entry *)g_slice_alloc0(size);
198			ret->size=size;
199			ret->usage=1;
200			memcpy(ret->id, id, cache->id_size*sizeof(int));
201			return &ret->id[cache->id_size];
202			}
203
204			void
205			cache_entry_destroy(struct cache cache, void data)
206			{
207			struct cache_entry entry=(struct cache_entry )((char *)data-cache->entry_size);
208			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]);
209			entry->usage--;
210			}
211
212			static struct cache_entry *
213			cache_trim(struct cache cache, struct cache_entry entry)
214			{
215			struct cache_entry *new_entry;
216			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]);
217			dbg(1,"Trim %x from %d -> %d\n", entry->id[0], entry->size, cache->size);
218			if ( cache->entry_size < entry->size )
219			{
220			g_hash_table_remove(cache->hash, (gpointer)(entry->id));
221
222			new_entry = g_slice_alloc0(cache->entry_size);
223			memcpy(new_entry, entry, cache->entry_size);
224			g_slice_free1( entry->size, entry);
225			new_entry->size = cache->entry_size;
226
227			g_hash_table_insert(cache->hash, (gpointer)new_entry->id, new_entry);
228			}
229			else
230			{
231			new_entry = entry;
232			}
233
234			return new_entry;
235			}
236
237			static struct cache_entry *
238			cache_move(struct cache cache, struct cache_entry_list old, struct cache_entry_list *new)
239			{
240			struct cache_entry *entry;
241			entry=cache_remove_lru(NULL, old);
242			if (! entry)
243			return NULL;
244			entry=cache_trim(cache, entry);
245			cache_insert_mru(NULL, new, entry);
246			return entry;
247			}
248
249			static int
250			cache_replace(struct cache *cache)
251			{
252			if (cache->t1.size >= MAX(1,cache->t1_target)) {
253			dbg(1,"replace 12\n");
254			if (!cache_move(cache, &cache->t1, &cache->b1))
255			cache_move(cache, &cache->t2, &cache->b2);
256			} else {
257			dbg(1,"replace t2\n");
258			if (!cache_move(cache, &cache->t2, &cache->b2))
259			cache_move(cache, &cache->t1, &cache->b1);
260			}
261			#if 0
262			if (! entry) {
263			cache_dump(cache);
264			exit(0);
265			}
266			#endif
267			return 1;
268			}
269
270			void
271			cache_flush(struct cache cache, void id)
272			{
273			struct cache_entry *entry=g_hash_table_lookup(cache->hash, id);
274			if (entry) {
275			cache_remove_from_list(entry->where, entry);
276			cache_remove(cache, entry);
277			}
278			}
279
280			void
281			cache_flush_data(struct cache cache, void data)
282			{
283			struct cache_entry entry=(struct cache_entry )((char *)data-cache->entry_size);
284			if (entry) {
285			cache_remove_from_list(entry->where, entry);
286			cache_remove(cache, entry);
287			}
288			}
289
290
291			void *
292			cache_lookup(struct cache cache, void id) {
293			struct cache_entry *entry;
294
295			dbg(1,"get %d\n", ((int *)id)[0]);
296			entry=g_hash_table_lookup(cache->hash, id);
297			if (entry == NULL) {
298			cache->insert=&cache->t1;
299			#ifdef DEBUG_CACHE
300			fprintf(stderr,"-");
301			#endif
302			dbg(1,"not in cache\n");
303			return NULL;
304			}
305			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]);
306			if (entry->where == &cache->t1 \|\| entry->where == &cache->t2) {
307			cache->hits+=entry->size;
308			#ifdef DEBUG_CACHE
309			if (entry->where == &cache->t1)
310			fprintf(stderr,"h");
311			else
312			fprintf(stderr,"H");
313			#endif
314			dbg(1,"in cache %s\n", entry->where == &cache->t1 ? "T1" : "T2");
315			cache_remove_from_list(entry->where, entry);
316			cache_insert_mru(NULL, &cache->t2, entry);
317			entry->usage++;
318			return &entry->id[cache->id_size];
319			} else {
320			if (entry->where == &cache->b1) {
321			#ifdef DEBUG_CACHE
322			fprintf(stderr,"m");
323			#endif
324			dbg(1,"in phantom cache B1\n");
325			cache->t1_target=MIN(cache->t1_target+MAX(cache->b2.size/cache->b1.size, 1),cache->size);
326			cache_remove_from_list(&cache->b1, entry);
327			} else if (entry->where == &cache->b2) {
328			#ifdef DEBUG_CACHE
329			fprintf(stderr,"M");
330			#endif
331			dbg(1,"in phantom cache B2\n");
332			cache->t1_target=MAX(cache->t1_target-MAX(cache->b1.size/cache->b2.size, 1),0);
333			cache_remove_from_list(&cache->b2, entry);
334			} else {
335			dbg(0,"ERROR invalid where\n");
336			}
337			cache_replace(cache);
338			cache_remove(cache, entry);
339			cache->insert=&cache->t2;
340			return NULL;
341			}
342			}
343
344			void
345			cache_insert(struct cache cache, void data)
346			{
347			struct cache_entry entry=(struct cache_entry )((char *)data-cache->entry_size);
348			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]);
349			if (cache->insert == &cache->t1) {
350			if (cache->t1.size + cache->b1.size >= cache->size) {
351			if (cache->t1.size < cache->size) {
352			cache_remove_lru(cache, &cache->b1);
353			cache_replace(cache);
354			} else {
355			cache_remove_lru(cache, &cache->t1);
356			}
357			} else {
358			if (cache->t1.size + cache->t2.size + cache->b1.size + cache->b2.size >= cache->size) {
359			if (cache->t1.size + cache->t2.size + cache->b1.size + cache->b2.size >= 2*cache->size)
360			cache_remove_lru(cache, &cache->b2);
361			cache_replace(cache);
362			}
363			}
364			}
365			cache_insert_mru(cache, cache->insert, entry);
366			}
367
368			void *
369			cache_insert_new(struct cache cache, void id, int size)
370			{
371			void *data=cache_entry_new(cache, id, size);
372			cache_insert(cache, data);
373			return data;
374			}
375
376			static void
377			cache_stats(struct cache *cache)
378			{
379			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);
380			dbg(0,"T1:%d B1:%d T2:%d B2:%d\n", cache->t1.size, cache->b1.size, cache->t2.size, cache->b2.size);
381			cache->hits=0;
382			cache->misses=0;
383			}
384
385			void
386			cache_dump(struct cache *cache)
387			{
388			struct cache_entry *first;
389			first=cache->t1.first;
390			cache_stats(cache);
391			cache_list_dump("T1", cache, &cache->t1);
392			cache_list_dump("B1", cache, &cache->b1);
393			cache_list_dump("T2", cache, &cache->t2);
394			cache_list_dump("B2", cache, &cache->b2);
395			dbg(0,"dump end\n");
396			}
397