|
|
1 | /** |
|
|
2 | * ZANavi, Zoff Android Navigation system. |
|
|
3 | * Copyright (C) 2011-2012 Zoff <zoff@zoff.cc> |
|
|
4 | * |
|
|
5 | * This program is free software; you can redistribute it and/or |
|
|
6 | * modify it under the terms of the GNU General Public License |
|
|
7 | * version 2 as published by the Free Software Foundation. |
|
|
8 | * |
|
|
9 | * This program is distributed in the hope that it will be useful, |
|
|
10 | * but WITHOUT ANY WARRANTY; without even the implied warranty of |
|
|
11 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
|
|
12 | * GNU General Public License for more details. |
|
|
13 | * |
|
|
14 | * You should have received a copy of the GNU General Public License |
|
|
15 | * along with this program; if not, write to the |
|
|
16 | * Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, |
|
|
17 | * Boston, MA 02110-1301, USA. |
|
|
18 | */ |
|
|
19 | |
1 | #include "glib_slice.h" |
20 | #include "glib_slice.h" |
2 | #ifdef DEBUG_CACHE |
21 | #ifdef DEBUG_CACHE |
3 | #include <stdio.h> |
22 | #include <stdio.h> |
4 | #endif |
23 | #endif |
5 | #include <string.h> |
24 | #include <string.h> |
6 | #include "debug.h" |
25 | #include "debug.h" |
7 | #include "cache.h" |
26 | #include "cache.h" |
8 | |
27 | |
9 | struct cache_entry { |
28 | struct cache_entry |
|
|
29 | { |
10 | int usage; |
30 | int usage; |
11 | int size; |
31 | int size; |
12 | struct cache_entry_list *where; |
32 | struct cache_entry_list *where; |
13 | struct cache_entry *next; |
33 | struct cache_entry *next; |
14 | struct cache_entry *prev; |
34 | struct cache_entry *prev; |
15 | int id[0]; |
35 | int id[0]; |
16 | }; |
36 | }; |
17 | |
37 | |
18 | struct cache_entry_list { |
38 | struct cache_entry_list |
|
|
39 | { |
19 | struct cache_entry *first, *last; |
40 | struct cache_entry *first, *last; |
20 | int size; |
41 | int size; |
21 | }; |
42 | }; |
22 | |
43 | |
23 | struct cache { |
44 | struct cache |
|
|
45 | { |
24 | struct cache_entry_list t1,b1,t2,b2,*insert; |
46 | struct cache_entry_list t1, b1, t2, b2, *insert; |
25 | int size,id_size,entry_size; |
47 | int size, id_size, entry_size; |
26 | int t1_target; |
48 | int t1_target; |
27 | int misses; |
49 | long misses; |
28 | int hits; |
50 | long hits; |
29 | GHashTable *hash; |
51 | GHashTable *hash; |
30 | }; |
52 | }; |
31 | |
53 | |
32 | static void |
|
|
33 | cache_entry_dump(struct cache *cache, struct cache_entry *entry) |
54 | static void cache_entry_dump(struct cache *cache, struct cache_entry *entry) |
34 | { |
55 | { |
35 | int i,size; |
56 | int i, size; |
36 | dbg(0,"Usage: %d size %d\n",entry->usage, entry->size); |
57 | //dbg(0,"Usage: %d size %d\n",entry->usage, entry->size); |
37 | if (cache) |
58 | if (cache) |
38 | size=cache->id_size; |
59 | size = cache->id_size; |
39 | else |
60 | else |
40 | size=5; |
61 | size = 5; |
41 | for (i = 0 ; i < size ; i++) { |
62 | for (i = 0; i < size; i++) |
|
|
63 | { |
42 | dbg(0,"0x%x\n", entry->id[i]); |
64 | dbg(0, "0x%x\n", entry->id[i]); |
43 | } |
65 | } |
44 | } |
66 | } |
45 | |
67 | |
46 | static void |
|
|
47 | cache_list_dump(char *str, struct cache *cache, struct cache_entry_list *list) |
68 | static void cache_list_dump(char *str, struct cache *cache, struct cache_entry_list *list) |
48 | { |
69 | { |
49 | struct cache_entry *first=list->first; |
70 | struct cache_entry *first = list->first; |
50 | dbg(0,"dump %s %d\n",str, list->size); |
71 | dbg(0, "dump %s %d\n", str, list->size); |
51 | while (first) { |
72 | while (first) |
|
|
73 | { |
52 | cache_entry_dump(cache, first); |
74 | cache_entry_dump(cache, first); |
53 | first=first->next; |
75 | first = first->next; |
54 | } |
76 | } |
55 | } |
77 | } |
56 | |
78 | |
57 | static guint |
|
|
58 | cache_hash4(gconstpointer key) |
79 | static guint cache_hash4(gconstpointer key) |
59 | { |
80 | { |
60 | int *id=(int *)key; |
81 | int *id = (int *) key; |
61 | return id[0]; |
82 | return id[0]; |
62 | } |
83 | } |
63 | |
84 | |
64 | static guint |
|
|
65 | cache_hash20(gconstpointer key) |
85 | static guint cache_hash20(gconstpointer key) |
66 | { |
86 | { |
67 | int *id=(int *)key; |
87 | int *id = (int *) key; |
68 | return id[0]^id[1]^id[2]^id[3]^id[4]; |
88 | return id[0] ^ id[1] ^ id[2] ^ id[3] ^ id[4]; |
69 | } |
89 | } |
70 | |
90 | |
71 | static gboolean |
|
|
72 | cache_equal4(gconstpointer a, gconstpointer b) |
91 | static gboolean cache_equal4(gconstpointer a, gconstpointer b) |
73 | { |
92 | { |
74 | int *ida=(int *)a; |
93 | int *ida = (int *) a; |
75 | int *idb=(int *)b; |
94 | int *idb = (int *) b; |
76 | |
95 | |
77 | return ida[0] == idb[0]; |
96 | return ida[0] == idb[0]; |
78 | } |
97 | } |
79 | |
98 | |
80 | static gboolean |
|
|
81 | cache_equal20(gconstpointer a, gconstpointer b) |
99 | static gboolean cache_equal20(gconstpointer a, gconstpointer b) |
82 | { |
100 | { |
83 | int *ida=(int *)a; |
101 | int *ida = (int *) a; |
84 | int *idb=(int *)b; |
102 | int *idb = (int *) b; |
85 | |
103 | |
86 | return(ida[0] == idb[0] && |
104 | return (ida[0] == idb[0] && ida[1] == idb[1] && ida[2] == idb[2] && ida[3] == idb[3] && ida[4] == idb[4]); |
87 | ida[1] == idb[1] && |
|
|
88 | ida[2] == idb[2] && |
|
|
89 | ida[3] == idb[3] && |
|
|
90 | ida[4] == idb[4]); |
|
|
91 | } |
105 | } |
92 | |
106 | |
93 | struct cache * |
107 | struct cache * |
94 | cache_new(int id_size, int size) |
108 | cache_new(int id_size, int size) |
95 | { |
109 | { |
96 | struct cache *cache=g_new0(struct cache, 1); |
110 | struct cache *cache=g_new0(struct cache, 1); |
97 | |
111 | |
98 | cache->id_size=id_size/4; |
112 | cache->id_size = id_size / 4; |
99 | cache->entry_size=cache->id_size*sizeof(int)+sizeof(struct cache_entry); |
113 | cache->entry_size = cache->id_size * sizeof(int) + sizeof(struct cache_entry); |
100 | cache->size=size; |
114 | cache->size = size; |
|
|
115 | |
|
|
116 | dbg(0, "_c size=%d\n", size); |
|
|
117 | |
101 | switch (id_size) { |
118 | switch (id_size) |
|
|
119 | { |
102 | case 4: |
120 | case 4: |
103 | cache->hash=g_hash_table_new(cache_hash4, cache_equal4); |
121 | cache->hash = g_hash_table_new(cache_hash4, cache_equal4); |
104 | break; |
122 | break; |
105 | case 20: |
123 | case 20: |
106 | cache->hash=g_hash_table_new(cache_hash20, cache_equal20); |
124 | cache->hash = g_hash_table_new(cache_hash20, cache_equal20); |
107 | break; |
125 | break; |
108 | default: |
126 | default: |
109 | dbg(0,"cache with id_size of %d not supported\n", id_size); |
127 | dbg(0, "cache with id_size of %d not supported\n", id_size); |
110 | g_free(cache); |
128 | g_free(cache); |
111 | cache=NULL; |
129 | cache = NULL; |
112 | } |
130 | } |
113 | return cache; |
131 | return cache; |
114 | } |
132 | } |
115 | |
133 | |
116 | static void |
|
|
117 | cache_insert_mru(struct cache *cache, struct cache_entry_list *list, struct cache_entry *entry) |
134 | static void cache_insert_mru(struct cache *cache, struct cache_entry_list *list, struct cache_entry *entry) |
118 | { |
135 | { |
119 | entry->prev=NULL; |
136 | entry->prev = NULL; |
120 | entry->next=list->first; |
137 | entry->next = list->first; |
121 | entry->where=list; |
138 | entry->where = list; |
122 | if (entry->next) |
139 | if (entry->next) |
123 | entry->next->prev=entry; |
140 | entry->next->prev = entry; |
124 | list->first=entry; |
141 | list->first = entry; |
125 | if (! list->last) |
142 | if (!list->last) |
126 | list->last=entry; |
143 | list->last = entry; |
127 | list->size+=entry->size; |
144 | list->size += entry->size; |
128 | if (cache) |
145 | if (cache) |
129 | g_hash_table_insert(cache->hash, (gpointer)entry->id, entry); |
146 | g_hash_table_insert(cache->hash, (gpointer) entry->id, entry); |
130 | } |
147 | } |
131 | |
148 | |
132 | static void |
|
|
133 | cache_remove_from_list(struct cache_entry_list *list, struct cache_entry *entry) |
149 | static void cache_remove_from_list(struct cache_entry_list *list, struct cache_entry *entry) |
134 | { |
150 | { |
135 | if (entry->prev) |
151 | if (entry->prev) |
136 | entry->prev->next=entry->next; |
152 | entry->prev->next = entry->next; |
137 | else |
153 | else |
138 | list->first=entry->next; |
154 | list->first = entry->next; |
139 | if (entry->next) |
155 | if (entry->next) |
140 | entry->next->prev=entry->prev; |
156 | entry->next->prev = entry->prev; |
141 | else |
157 | else |
142 | list->last=entry->prev; |
158 | list->last = entry->prev; |
143 | list->size-=entry->size; |
159 | list->size -= entry->size; |
144 | } |
160 | } |
145 | |
161 | |
146 | static void |
|
|
147 | cache_remove(struct cache *cache, struct cache_entry *entry) |
162 | static void cache_remove(struct cache *cache, struct cache_entry *entry) |
148 | { |
163 | { |
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]); |
164 | // 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)); |
165 | g_hash_table_remove(cache->hash, (gpointer)(entry->id)); |
151 | g_slice_free1(entry->size, entry); |
166 | g_slice_free1(entry->size, entry); |
152 | } |
167 | } |
153 | |
168 | |
154 | static struct cache_entry * |
169 | static struct cache_entry * |
155 | cache_remove_lru_helper(struct cache_entry_list *list) |
170 | cache_remove_lru_helper(struct cache_entry_list *list) |
156 | { |
171 | { |
157 | struct cache_entry *last=list->last; |
172 | struct cache_entry *last = list->last; |
158 | if (! last) |
173 | if (!last) |
159 | return NULL; |
174 | return NULL; |
160 | list->last=last->prev; |
175 | list->last = last->prev; |
161 | if (last->prev) |
176 | if (last->prev) |
162 | last->prev->next=NULL; |
177 | last->prev->next = NULL; |
163 | else |
178 | else |
164 | list->first=NULL; |
179 | list->first = NULL; |
165 | list->size-=last->size; |
180 | list->size -= last->size; |
166 | return last; |
181 | return last; |
167 | } |
182 | } |
168 | |
183 | |
169 | static struct cache_entry * |
184 | static struct cache_entry * |
170 | cache_remove_lru(struct cache *cache, struct cache_entry_list *list) |
185 | cache_remove_lru(struct cache *cache, struct cache_entry_list *list) |
171 | { |
186 | { |
172 | struct cache_entry *last; |
187 | struct cache_entry *last; |
173 | int seen=0; |
188 | int seen = 0; |
174 | while (list->last && list->last->usage && seen < list->size) { |
189 | while (list->last && list->last->usage && seen < list->size) |
|
|
190 | { |
175 | last=cache_remove_lru_helper(list); |
191 | last = cache_remove_lru_helper(list); |
176 | cache_insert_mru(NULL, list, last); |
192 | cache_insert_mru(NULL, list, last); |
177 | seen+=last->size; |
193 | seen += last->size; |
178 | } |
194 | } |
179 | last=list->last; |
195 | last = list->last; |
180 | if (! last || last->usage || seen >= list->size) |
196 | if (!last || last->usage || seen >= list->size) |
|
|
197 | { |
181 | return NULL; |
198 | return NULL; |
|
|
199 | } |
182 | dbg(1,"removing %d\n", last->id[0]); |
200 | //dbg(1,"removing %d\n", last->id[0]); |
183 | cache_remove_lru_helper(list); |
201 | cache_remove_lru_helper(list); |
184 | if (cache) { |
202 | if (cache) |
|
|
203 | { |
185 | cache_remove(cache, last); |
204 | cache_remove(cache, last); |
186 | return NULL; |
205 | return NULL; |
187 | } |
206 | } |
188 | return last; |
207 | return last; |
189 | } |
208 | } |
190 | |
209 | |
191 | void * |
210 | void * |
192 | cache_entry_new(struct cache *cache, void *id, int size) |
211 | cache_entry_new(struct cache *cache, void *id, int size) |
193 | { |
212 | { |
194 | struct cache_entry *ret; |
213 | struct cache_entry *ret; |
195 | size+=cache->entry_size; |
214 | size += cache->entry_size; |
196 | cache->misses+=size; |
215 | cache->misses += size; |
197 | ret=(struct cache_entry *)g_slice_alloc0(size); |
216 | ret = (struct cache_entry *) g_slice_alloc0(size); |
198 | ret->size=size; |
217 | ret->size = size; |
199 | ret->usage=1; |
218 | ret->usage = 1; |
200 | memcpy(ret->id, id, cache->id_size*sizeof(int)); |
219 | memcpy(ret->id, id, cache->id_size * sizeof(int)); |
201 | return &ret->id[cache->id_size]; |
220 | return &ret->id[cache->id_size]; |
202 | } |
221 | } |
203 | |
222 | |
204 | void |
|
|
205 | cache_entry_destroy(struct cache *cache, void *data) |
223 | void cache_entry_destroy(struct cache *cache, void *data) |
206 | { |
224 | { |
207 | struct cache_entry *entry=(struct cache_entry *)((char *)data-cache->entry_size); |
225 | 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]); |
226 | // 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--; |
227 | entry->usage--; |
210 | } |
228 | } |
211 | |
229 | |
212 | static struct cache_entry * |
230 | static struct cache_entry * |
213 | cache_trim(struct cache *cache, struct cache_entry *entry) |
231 | cache_trim(struct cache *cache, struct cache_entry *entry) |
214 | { |
232 | { |
215 | struct cache_entry *new_entry; |
233 | 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]); |
234 | //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); |
235 | //dbg(1,"Trim %x from %d -> %d\n", entry->id[0], entry->size, cache->size); |
218 | if ( cache->entry_size < entry->size ) |
236 | if (cache->entry_size < entry->size) |
219 | { |
237 | { |
220 | g_hash_table_remove(cache->hash, (gpointer)(entry->id)); |
238 | g_hash_table_remove(cache->hash, (gpointer)(entry->id)); |
221 | |
239 | |
222 | new_entry = g_slice_alloc0(cache->entry_size); |
240 | new_entry = g_slice_alloc0(cache->entry_size); |
223 | memcpy(new_entry, entry, cache->entry_size); |
241 | memcpy(new_entry, entry, cache->entry_size); |
224 | g_slice_free1( entry->size, entry); |
242 | g_slice_free1(entry->size, entry); |
225 | new_entry->size = cache->entry_size; |
243 | new_entry->size = cache->entry_size; |
226 | |
244 | |
227 | g_hash_table_insert(cache->hash, (gpointer)new_entry->id, new_entry); |
245 | g_hash_table_insert(cache->hash, (gpointer) new_entry->id, new_entry); |
228 | } |
246 | } |
229 | else |
247 | else |
230 | { |
248 | { |
231 | new_entry = entry; |
249 | new_entry = entry; |
232 | } |
250 | } |
233 | |
251 | |
234 | return new_entry; |
252 | return new_entry; |
235 | } |
253 | } |
236 | |
254 | |
237 | static struct cache_entry * |
255 | static struct cache_entry * |
238 | cache_move(struct cache *cache, struct cache_entry_list *old, struct cache_entry_list *new) |
256 | cache_move(struct cache *cache, struct cache_entry_list *old, struct cache_entry_list *new) |
239 | { |
257 | { |
240 | struct cache_entry *entry; |
258 | struct cache_entry *entry; |
241 | entry=cache_remove_lru(NULL, old); |
259 | entry = cache_remove_lru(NULL, old); |
242 | if (! entry) |
260 | if (!entry) |
243 | return NULL; |
261 | return NULL; |
244 | entry=cache_trim(cache, entry); |
262 | entry = cache_trim(cache, entry); |
245 | cache_insert_mru(NULL, new, entry); |
263 | cache_insert_mru(NULL, new, entry); |
246 | return entry; |
264 | return entry; |
247 | } |
265 | } |
248 | |
266 | |
249 | static int |
|
|
250 | cache_replace(struct cache *cache) |
267 | static int cache_replace(struct cache *cache) |
251 | { |
268 | { |
252 | if (cache->t1.size >= MAX(1,cache->t1_target)) { |
269 | if (cache->t1.size >= MAX(1, cache->t1_target)) |
|
|
270 | { |
253 | dbg(1,"replace 12\n"); |
271 | //dbg(1,"replace 12\n"); |
254 | if (!cache_move(cache, &cache->t1, &cache->b1)) |
272 | if (!cache_move(cache, &cache->t1, &cache->b1)) |
255 | cache_move(cache, &cache->t2, &cache->b2); |
273 | cache_move(cache, &cache->t2, &cache->b2); |
256 | } else { |
274 | } |
|
|
275 | else |
|
|
276 | { |
257 | dbg(1,"replace t2\n"); |
277 | //dbg(1,"replace t2\n"); |
258 | if (!cache_move(cache, &cache->t2, &cache->b2)) |
278 | if (!cache_move(cache, &cache->t2, &cache->b2)) |
259 | cache_move(cache, &cache->t1, &cache->b1); |
279 | cache_move(cache, &cache->t1, &cache->b1); |
260 | } |
280 | } |
261 | #if 0 |
281 | #if 0 |
262 | if (! entry) { |
282 | if (! entry) |
|
|
283 | { |
263 | cache_dump(cache); |
284 | cache_dump(cache); |
264 | exit(0); |
285 | exit(0); |
265 | } |
286 | } |
266 | #endif |
287 | #endif |
267 | return 1; |
288 | return 1; |
268 | } |
289 | } |
269 | |
290 | |
270 | void |
|
|
271 | cache_flush(struct cache *cache, void *id) |
291 | void cache_flush(struct cache *cache, void *id) |
272 | { |
292 | { |
273 | struct cache_entry *entry=g_hash_table_lookup(cache->hash, id); |
293 | struct cache_entry *entry = g_hash_table_lookup(cache->hash, id); |
274 | if (entry) { |
294 | if (entry) |
|
|
295 | { |
275 | cache_remove_from_list(entry->where, entry); |
296 | cache_remove_from_list(entry->where, entry); |
276 | cache_remove(cache, entry); |
297 | cache_remove(cache, entry); |
277 | } |
298 | } |
278 | } |
299 | } |
279 | |
300 | |
280 | void |
|
|
281 | cache_flush_data(struct cache *cache, void *data) |
301 | void cache_flush_data(struct cache *cache, void *data) |
282 | { |
302 | { |
283 | struct cache_entry *entry=(struct cache_entry *)((char *)data-cache->entry_size); |
303 | struct cache_entry *entry = (struct cache_entry *) ((char *) data - cache->entry_size); |
284 | if (entry) { |
304 | if (entry) |
|
|
305 | { |
285 | cache_remove_from_list(entry->where, entry); |
306 | cache_remove_from_list(entry->where, entry); |
286 | cache_remove(cache, entry); |
307 | cache_remove(cache, entry); |
287 | } |
308 | } |
288 | } |
309 | } |
289 | |
310 | |
290 | |
|
|
291 | void * |
311 | void * |
292 | cache_lookup(struct cache *cache, void *id) { |
312 | cache_lookup(struct cache *cache, void *id) |
|
|
313 | { |
293 | struct cache_entry *entry; |
314 | struct cache_entry *entry; |
294 | |
315 | |
295 | dbg(1,"get %d\n", ((int *)id)[0]); |
316 | //dbg(1,"get %d\n", ((int *)id)[0]); |
296 | entry=g_hash_table_lookup(cache->hash, id); |
317 | entry = g_hash_table_lookup(cache->hash, id); |
297 | if (entry == NULL) { |
318 | if (entry == NULL) |
|
|
319 | { |
298 | cache->insert=&cache->t1; |
320 | cache->insert = &cache->t1; |
299 | #ifdef DEBUG_CACHE |
321 | #ifdef DEBUG_CACHE |
300 | fprintf(stderr,"-"); |
322 | fprintf(stderr,"-"); |
301 | #endif |
323 | #endif |
302 | dbg(1,"not in cache\n"); |
324 | //dbg(1,"not in cache\n"); |
303 | return NULL; |
325 | return NULL; |
304 | } |
326 | } |
|
|
327 | |
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]); |
328 | // 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) { |
329 | if (entry->where == &cache->t1 || entry->where == &cache->t2) |
|
|
330 | { |
307 | cache->hits+=entry->size; |
331 | cache->hits += entry->size; |
308 | #ifdef DEBUG_CACHE |
332 | #ifdef DEBUG_CACHE |
309 | if (entry->where == &cache->t1) |
333 | if (entry->where == &cache->t1) |
|
|
334 | { |
310 | fprintf(stderr,"h"); |
335 | fprintf(stderr,"h"); |
|
|
336 | } |
311 | else |
337 | else |
|
|
338 | { |
312 | fprintf(stderr,"H"); |
339 | fprintf(stderr,"H"); |
|
|
340 | } |
313 | #endif |
341 | #endif |
314 | dbg(1,"in cache %s\n", entry->where == &cache->t1 ? "T1" : "T2"); |
342 | // dbg(1,"in cache %s\n", entry->where == &cache->t1 ? "T1" : "T2"); |
315 | cache_remove_from_list(entry->where, entry); |
343 | cache_remove_from_list(entry->where, entry); |
316 | cache_insert_mru(NULL, &cache->t2, entry); |
344 | cache_insert_mru(NULL, &cache->t2, entry); |
317 | entry->usage++; |
345 | entry->usage++; |
318 | return &entry->id[cache->id_size]; |
346 | return &entry->id[cache->id_size]; |
319 | } else { |
347 | } |
|
|
348 | else |
|
|
349 | { |
320 | if (entry->where == &cache->b1) { |
350 | if (entry->where == &cache->b1) |
|
|
351 | { |
321 | #ifdef DEBUG_CACHE |
352 | #ifdef DEBUG_CACHE |
322 | fprintf(stderr,"m"); |
353 | fprintf(stderr,"m"); |
323 | #endif |
354 | #endif |
324 | dbg(1,"in phantom cache B1\n"); |
355 | //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); |
356 | 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); |
357 | cache_remove_from_list(&cache->b1, entry); |
|
|
358 | } |
327 | } else if (entry->where == &cache->b2) { |
359 | else if (entry->where == &cache->b2) |
|
|
360 | { |
328 | #ifdef DEBUG_CACHE |
361 | #ifdef DEBUG_CACHE |
329 | fprintf(stderr,"M"); |
362 | fprintf(stderr,"M"); |
330 | #endif |
363 | #endif |
331 | dbg(1,"in phantom cache B2\n"); |
364 | //dbg(1,"in phantom cache B2\n"); |
332 | cache->t1_target=MAX(cache->t1_target-MAX(cache->b1.size/cache->b2.size, 1),0); |
365 | cache->t1_target = MAX(cache->t1_target - MAX(cache->b1.size / cache->b2.size, 1), 0); |
333 | cache_remove_from_list(&cache->b2, entry); |
366 | cache_remove_from_list(&cache->b2, entry); |
|
|
367 | } |
334 | } else { |
368 | else |
|
|
369 | { |
335 | dbg(0,"**ERROR** invalid where\n"); |
370 | //dbg(0,"**ERROR** invalid where\n"); |
336 | } |
371 | } |
337 | cache_replace(cache); |
372 | cache_replace(cache); |
338 | cache_remove(cache, entry); |
373 | cache_remove(cache, entry); |
339 | cache->insert=&cache->t2; |
374 | cache->insert = &cache->t2; |
340 | return NULL; |
375 | return NULL; |
341 | } |
376 | } |
342 | } |
377 | } |
343 | |
378 | |
344 | void |
|
|
345 | cache_insert(struct cache *cache, void *data) |
379 | void cache_insert(struct cache *cache, void *data) |
346 | { |
380 | { |
347 | struct cache_entry *entry=(struct cache_entry *)((char *)data-cache->entry_size); |
381 | 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]); |
382 | //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) { |
383 | if (cache->insert == &cache->t1) |
|
|
384 | { |
350 | if (cache->t1.size + cache->b1.size >= cache->size) { |
385 | if (cache->t1.size + cache->b1.size >= cache->size) |
|
|
386 | { |
351 | if (cache->t1.size < cache->size) { |
387 | if (cache->t1.size < cache->size) |
|
|
388 | { |
352 | cache_remove_lru(cache, &cache->b1); |
389 | cache_remove_lru(cache, &cache->b1); |
353 | cache_replace(cache); |
390 | cache_replace(cache); |
|
|
391 | } |
354 | } else { |
392 | else |
|
|
393 | { |
355 | cache_remove_lru(cache, &cache->t1); |
394 | cache_remove_lru(cache, &cache->t1); |
356 | } |
395 | } |
|
|
396 | } |
357 | } else { |
397 | else |
|
|
398 | { |
358 | if (cache->t1.size + cache->t2.size + cache->b1.size + cache->b2.size >= cache->size) { |
399 | if (cache->t1.size + cache->t2.size + cache->b1.size + cache->b2.size >= cache->size) |
|
|
400 | { |
359 | if (cache->t1.size + cache->t2.size + cache->b1.size + cache->b2.size >= 2*cache->size) |
401 | if (cache->t1.size + cache->t2.size + cache->b1.size + cache->b2.size >= 2 * cache->size) |
360 | cache_remove_lru(cache, &cache->b2); |
402 | cache_remove_lru(cache, &cache->b2); |
361 | cache_replace(cache); |
403 | cache_replace(cache); |
362 | } |
404 | } |
363 | } |
405 | } |
364 | } |
406 | } |
… | |
… | |
366 | } |
408 | } |
367 | |
409 | |
368 | void * |
410 | void * |
369 | cache_insert_new(struct cache *cache, void *id, int size) |
411 | cache_insert_new(struct cache *cache, void *id, int size) |
370 | { |
412 | { |
371 | void *data=cache_entry_new(cache, id, size); |
413 | void *data = cache_entry_new(cache, id, size); |
372 | cache_insert(cache, data); |
414 | cache_insert(cache, data); |
373 | return data; |
415 | return data; |
374 | } |
416 | } |
375 | |
417 | |
376 | static void |
|
|
377 | cache_stats(struct cache *cache) |
418 | void cache_stats(struct cache *cache) |
378 | { |
419 | { |
|
|
420 | unsigned long c_ratio = 0; |
|
|
421 | if ((cache->hits + cache->misses) > 0) |
|
|
422 | { |
|
|
423 | c_ratio = (long) (cache->hits) * (long) (100L); |
|
|
424 | //dbg(0,"1 c_ratio=%lu\n", c_ratio); |
|
|
425 | c_ratio = c_ratio / (long) (cache->hits + cache->misses); |
|
|
426 | //dbg(0,"2 c_ratio=%lu\n", c_ratio); |
|
|
427 | |
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); |
428 | dbg(0, "hits %d misses %lu hitratio %d size %d entry_size %d id_size %d T1 target %d\n", cache->hits, cache->misses, c_ratio, 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); |
429 | // dbg(0,"T1:%d B1:%d T2:%d B2:%d\n", cache->t1.size, cache->b1.size, cache->t2.size, cache->b2.size); |
|
|
430 | |
|
|
431 | // if numbers are too big, reset them |
|
|
432 | if ((cache->hits > 1000000000) || (cache->misses > 1000000000)) |
|
|
433 | { |
381 | cache->hits=0; |
434 | cache->hits = 0; |
382 | cache->misses=0; |
435 | cache->misses = 0; |
|
|
436 | } |
|
|
437 | } |
383 | } |
438 | } |
384 | |
439 | |
385 | void |
|
|
386 | cache_dump(struct cache *cache) |
440 | void cache_dump(struct cache *cache) |
387 | { |
441 | { |
388 | struct cache_entry *first; |
442 | struct cache_entry *first; |
389 | first=cache->t1.first; |
443 | first = cache->t1.first; |
390 | cache_stats(cache); |
444 | cache_stats(cache); |
391 | cache_list_dump("T1", cache, &cache->t1); |
445 | cache_list_dump("T1", cache, &cache->t1); |
392 | cache_list_dump("B1", cache, &cache->b1); |
446 | cache_list_dump("B1", cache, &cache->b1); |
393 | cache_list_dump("T2", cache, &cache->t2); |
447 | cache_list_dump("T2", cache, &cache->t2); |
394 | cache_list_dump("B2", cache, &cache->b2); |
448 | cache_list_dump("B2", cache, &cache->b2); |
395 | dbg(0,"dump end\n"); |
449 | dbg(0, "dump end\n"); |
396 | } |
450 | } |
397 | |
451 | |