1 /**************************************************************************
2 *
3 * Copyright 2008 VMware, Inc.
4 * All Rights Reserved.
5 *
6 * Permission is hereby granted, free of charge, to any person obtaining a
7 * copy of this software and associated documentation files (the
8 * "Software"), to deal in the Software without restriction, including
9 * without limitation the rights to use, copy, modify, merge, publish,
10 * distribute, sub license, and/or sell copies of the Software, and to
11 * permit persons to whom the Software is furnished to do so, subject to
12 * the following conditions:
13 *
14 * The above copyright notice and this permission notice (including the
15 * next paragraph) shall be included in all copies or substantial portions
16 * of the Software.
17 *
18 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
19 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
20 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT.
21 * IN NO EVENT SHALL VMWARE AND/OR ITS SUPPLIERS BE LIABLE FOR
22 * ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
23 * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
24 * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
25 *
26 **************************************************************************/
27
28 /**
29 * @file
30 * Improved cache implementation.
31 *
32 * Fixed size array with linear probing on collision and LRU eviction
33 * on full.
34 *
35 * @author Jose Fonseca <jfonseca@vmware.com>
36 */
37
38
39 #include "pipe/p_compiler.h"
40 #include "util/u_debug.h"
41
42 #include "util/u_math.h"
43 #include "util/u_memory.h"
44 #include "util/u_cache.h"
45 #include "util/u_simple_list.h"
46
47
48 struct util_cache_entry
49 {
50 enum { EMPTY = 0, FILLED, DELETED } state;
51 uint32_t hash;
52
53 struct util_cache_entry *next;
54 struct util_cache_entry *prev;
55
56 void *key;
57 void *value;
58
59 #ifdef DEBUG
60 unsigned count;
61 #endif
62 };
63
64
65 struct util_cache
66 {
67 /** Hash function */
68 uint32_t (*hash)(const void *key);
69
70 /** Compare two keys */
71 int (*compare)(const void *key1, const void *key2);
72
73 /** Destroy a (key, value) pair */
74 void (*destroy)(void *key, void *value);
75
76 uint32_t size;
77
78 struct util_cache_entry *entries;
79
80 unsigned count;
81 struct util_cache_entry lru;
82 };
83
84 static void
85 ensure_sanity(const struct util_cache *cache);
86
87 #define CACHE_DEFAULT_ALPHA 2
88
89 struct util_cache *
util_cache_create(uint32_t (* hash)(const void * key),int (* compare)(const void * key1,const void * key2),void (* destroy)(void * key,void * value),uint32_t size)90 util_cache_create(uint32_t (*hash)(const void *key),
91 int (*compare)(const void *key1, const void *key2),
92 void (*destroy)(void *key, void *value),
93 uint32_t size)
94 {
95 struct util_cache *cache;
96
97 cache = CALLOC_STRUCT(util_cache);
98 if(!cache)
99 return NULL;
100
101 cache->hash = hash;
102 cache->compare = compare;
103 cache->destroy = destroy;
104
105 make_empty_list(&cache->lru);
106
107 size *= CACHE_DEFAULT_ALPHA;
108 cache->size = size;
109
110 cache->entries = CALLOC(size, sizeof(struct util_cache_entry));
111 if(!cache->entries) {
112 FREE(cache);
113 return NULL;
114 }
115
116 ensure_sanity(cache);
117 return cache;
118 }
119
120
121 static struct util_cache_entry *
util_cache_entry_get(struct util_cache * cache,uint32_t hash,const void * key)122 util_cache_entry_get(struct util_cache *cache,
123 uint32_t hash,
124 const void *key)
125 {
126 struct util_cache_entry *first_unfilled = NULL;
127 uint32_t index = hash % cache->size;
128 uint32_t probe;
129
130 /* Probe until we find either a matching FILLED entry or an EMPTY
131 * slot (which has never been occupied).
132 *
133 * Deleted or non-matching slots are not indicative of completion
134 * as a previous linear probe for the same key could have continued
135 * past this point.
136 */
137 for (probe = 0; probe < cache->size; probe++) {
138 uint32_t i = (index + probe) % cache->size;
139 struct util_cache_entry *current = &cache->entries[i];
140
141 if (current->state == FILLED) {
142 if (current->hash == hash &&
143 cache->compare(key, current->key) == 0)
144 return current;
145 }
146 else {
147 if (!first_unfilled)
148 first_unfilled = current;
149
150 if (current->state == EMPTY)
151 return first_unfilled;
152 }
153 }
154
155 return NULL;
156 }
157
158 static INLINE void
util_cache_entry_destroy(struct util_cache * cache,struct util_cache_entry * entry)159 util_cache_entry_destroy(struct util_cache *cache,
160 struct util_cache_entry *entry)
161 {
162 void *key = entry->key;
163 void *value = entry->value;
164
165 entry->key = NULL;
166 entry->value = NULL;
167
168 if (entry->state == FILLED) {
169 remove_from_list(entry);
170 cache->count--;
171
172 if(cache->destroy)
173 cache->destroy(key, value);
174
175 entry->state = DELETED;
176 }
177 }
178
179
180 void
util_cache_set(struct util_cache * cache,void * key,void * value)181 util_cache_set(struct util_cache *cache,
182 void *key,
183 void *value)
184 {
185 struct util_cache_entry *entry;
186 uint32_t hash = cache->hash(key);
187
188 assert(cache);
189 if (!cache)
190 return;
191
192 entry = util_cache_entry_get(cache, hash, key);
193 if (!entry)
194 entry = cache->lru.prev;
195
196 if (cache->count >= cache->size / CACHE_DEFAULT_ALPHA)
197 util_cache_entry_destroy(cache, cache->lru.prev);
198
199 util_cache_entry_destroy(cache, entry);
200
201 #ifdef DEBUG
202 ++entry->count;
203 #endif
204
205 entry->key = key;
206 entry->hash = hash;
207 entry->value = value;
208 entry->state = FILLED;
209 insert_at_head(&cache->lru, entry);
210 cache->count++;
211
212 ensure_sanity(cache);
213 }
214
215
216 void *
util_cache_get(struct util_cache * cache,const void * key)217 util_cache_get(struct util_cache *cache,
218 const void *key)
219 {
220 struct util_cache_entry *entry;
221 uint32_t hash = cache->hash(key);
222
223 assert(cache);
224 if (!cache)
225 return NULL;
226
227 entry = util_cache_entry_get(cache, hash, key);
228 if (!entry)
229 return NULL;
230
231 if (entry->state == FILLED)
232 move_to_head(&cache->lru, entry);
233
234 return entry->value;
235 }
236
237
238 void
util_cache_clear(struct util_cache * cache)239 util_cache_clear(struct util_cache *cache)
240 {
241 uint32_t i;
242
243 assert(cache);
244 if (!cache)
245 return;
246
247 for(i = 0; i < cache->size; ++i) {
248 util_cache_entry_destroy(cache, &cache->entries[i]);
249 cache->entries[i].state = EMPTY;
250 }
251
252 assert(cache->count == 0);
253 assert(is_empty_list(&cache->lru));
254 ensure_sanity(cache);
255 }
256
257
258 void
util_cache_destroy(struct util_cache * cache)259 util_cache_destroy(struct util_cache *cache)
260 {
261 assert(cache);
262 if (!cache)
263 return;
264
265 #ifdef DEBUG
266 if(cache->count >= 20*cache->size) {
267 /* Normal approximation of the Poisson distribution */
268 double mean = (double)cache->count/(double)cache->size;
269 double stddev = sqrt(mean);
270 unsigned i;
271 for(i = 0; i < cache->size; ++i) {
272 double z = fabs(cache->entries[i].count - mean)/stddev;
273 /* This assert should not fail 99.9999998027% of the times, unless
274 * the hash function is a poor one */
275 assert(z <= 6.0);
276 }
277 }
278 #endif
279
280 util_cache_clear(cache);
281
282 FREE(cache->entries);
283 FREE(cache);
284 }
285
286
287 void
util_cache_remove(struct util_cache * cache,const void * key)288 util_cache_remove(struct util_cache *cache,
289 const void *key)
290 {
291 struct util_cache_entry *entry;
292 uint32_t hash;
293
294 assert(cache);
295 if (!cache)
296 return;
297
298 hash = cache->hash(key);
299
300 entry = util_cache_entry_get(cache, hash, key);
301 if (!entry)
302 return;
303
304 if (entry->state == FILLED)
305 util_cache_entry_destroy(cache, entry);
306
307 ensure_sanity(cache);
308 }
309
310
311 static void
ensure_sanity(const struct util_cache * cache)312 ensure_sanity(const struct util_cache *cache)
313 {
314 #ifdef DEBUG
315 unsigned i, cnt = 0;
316
317 assert(cache);
318 for (i = 0; i < cache->size; i++) {
319 struct util_cache_entry *header = &cache->entries[i];
320
321 assert(header);
322 assert(header->state == FILLED ||
323 header->state == EMPTY ||
324 header->state == DELETED);
325 if (header->state == FILLED) {
326 cnt++;
327 assert(header->hash == cache->hash(header->key));
328 }
329 }
330
331 assert(cnt == cache->count);
332 assert(cache->size >= cnt);
333
334 if (cache->count == 0) {
335 assert (is_empty_list(&cache->lru));
336 }
337 else {
338 struct util_cache_entry *header = cache->lru.next;
339
340 assert (header);
341 assert (!is_empty_list(&cache->lru));
342
343 for (i = 0; i < cache->count; i++)
344 header = header->next;
345
346 assert(header == &cache->lru);
347 }
348 #endif
349
350 (void)cache;
351 }
352