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/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 /** Max entries in the cache */
77 uint32_t size;
78
79 /** Array [size] of entries */
80 struct util_cache_entry *entries;
81
82 /** Number of entries in the cache */
83 unsigned count;
84
85 /** Head of list, sorted from Least-recently used to Most-recently used */
86 struct util_cache_entry lru;
87 };
88
89
90 static void
91 ensure_sanity(const struct util_cache *cache);
92
93 #define CACHE_DEFAULT_ALPHA 2
94
95 /**
96 * Create a new cache with 'size' entries. Also provide functions for
97 * hashing keys, comparing keys and destroying (key,value) pairs.
98 */
99 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)100 util_cache_create(uint32_t (*hash)(const void *key),
101 int (*compare)(const void *key1, const void *key2),
102 void (*destroy)(void *key, void *value),
103 uint32_t size)
104 {
105 struct util_cache *cache;
106
107 cache = CALLOC_STRUCT(util_cache);
108 if (!cache)
109 return NULL;
110
111 cache->hash = hash;
112 cache->compare = compare;
113 cache->destroy = destroy;
114
115 make_empty_list(&cache->lru);
116
117 size *= CACHE_DEFAULT_ALPHA;
118 cache->size = size;
119
120 cache->entries = CALLOC(size, sizeof(struct util_cache_entry));
121 if (!cache->entries) {
122 FREE(cache);
123 return NULL;
124 }
125
126 ensure_sanity(cache);
127 return cache;
128 }
129
130
131 /**
132 * Try to find a cache entry, given the key and hash of the key.
133 */
134 static struct util_cache_entry *
util_cache_entry_get(struct util_cache * cache,uint32_t hash,const void * key)135 util_cache_entry_get(struct util_cache *cache,
136 uint32_t hash,
137 const void *key)
138 {
139 struct util_cache_entry *first_unfilled = NULL;
140 uint32_t index = hash % cache->size;
141 uint32_t probe;
142
143 /* Probe until we find either a matching FILLED entry or an EMPTY
144 * slot (which has never been occupied).
145 *
146 * Deleted or non-matching slots are not indicative of completion
147 * as a previous linear probe for the same key could have continued
148 * past this point.
149 */
150 for (probe = 0; probe < cache->size; probe++) {
151 uint32_t i = (index + probe) % cache->size;
152 struct util_cache_entry *current = &cache->entries[i];
153
154 if (current->state == FILLED) {
155 if (current->hash == hash &&
156 cache->compare(key, current->key) == 0)
157 return current;
158 }
159 else {
160 if (!first_unfilled)
161 first_unfilled = current;
162
163 if (current->state == EMPTY)
164 return first_unfilled;
165 }
166 }
167
168 return NULL;
169 }
170
171 static inline void
util_cache_entry_destroy(struct util_cache * cache,struct util_cache_entry * entry)172 util_cache_entry_destroy(struct util_cache *cache,
173 struct util_cache_entry *entry)
174 {
175 void *key = entry->key;
176 void *value = entry->value;
177
178 entry->key = NULL;
179 entry->value = NULL;
180
181 if (entry->state == FILLED) {
182 remove_from_list(entry);
183 cache->count--;
184
185 if (cache->destroy)
186 cache->destroy(key, value);
187
188 entry->state = DELETED;
189 }
190 }
191
192
193 /**
194 * Insert an entry in the cache, given the key and value.
195 */
196 void
util_cache_set(struct util_cache * cache,void * key,void * value)197 util_cache_set(struct util_cache *cache,
198 void *key,
199 void *value)
200 {
201 struct util_cache_entry *entry;
202 uint32_t hash;
203
204 assert(cache);
205 if (!cache)
206 return;
207 hash = cache->hash(key);
208 entry = util_cache_entry_get(cache, hash, key);
209 if (!entry)
210 entry = cache->lru.prev;
211
212 if (cache->count >= cache->size / CACHE_DEFAULT_ALPHA)
213 util_cache_entry_destroy(cache, cache->lru.prev);
214
215 util_cache_entry_destroy(cache, entry);
216
217 #ifdef DEBUG
218 ++entry->count;
219 #endif
220
221 entry->key = key;
222 entry->hash = hash;
223 entry->value = value;
224 entry->state = FILLED;
225 insert_at_head(&cache->lru, entry);
226 cache->count++;
227
228 ensure_sanity(cache);
229 }
230
231
232 /**
233 * Search the cache for an entry with the given key. Return the corresponding
234 * value or NULL if not found.
235 */
236 void *
util_cache_get(struct util_cache * cache,const void * key)237 util_cache_get(struct util_cache *cache,
238 const void *key)
239 {
240 struct util_cache_entry *entry;
241 uint32_t hash;
242
243 assert(cache);
244 if (!cache)
245 return NULL;
246 hash = cache->hash(key);
247 entry = util_cache_entry_get(cache, hash, key);
248 if (!entry)
249 return NULL;
250
251 if (entry->state == FILLED)
252 move_to_head(&cache->lru, entry);
253
254 return entry->value;
255 }
256
257
258 /**
259 * Remove all entries from the cache. The 'destroy' function will be called
260 * for each entry's (key, value).
261 */
262 void
util_cache_clear(struct util_cache * cache)263 util_cache_clear(struct util_cache *cache)
264 {
265 uint32_t i;
266
267 assert(cache);
268 if (!cache)
269 return;
270
271 for (i = 0; i < cache->size; ++i) {
272 util_cache_entry_destroy(cache, &cache->entries[i]);
273 cache->entries[i].state = EMPTY;
274 }
275
276 assert(cache->count == 0);
277 assert(is_empty_list(&cache->lru));
278 ensure_sanity(cache);
279 }
280
281
282 /**
283 * Destroy the cache and all entries.
284 */
285 void
util_cache_destroy(struct util_cache * cache)286 util_cache_destroy(struct util_cache *cache)
287 {
288 assert(cache);
289 if (!cache)
290 return;
291
292 #ifdef DEBUG
293 if (cache->count >= 20*cache->size) {
294 /* Normal approximation of the Poisson distribution */
295 double mean = (double)cache->count/(double)cache->size;
296 double stddev = sqrt(mean);
297 unsigned i;
298 for (i = 0; i < cache->size; ++i) {
299 double z = fabs(cache->entries[i].count - mean)/stddev;
300 /* This assert should not fail 99.9999998027% of the times, unless
301 * the hash function is a poor one */
302 assert(z <= 6.0);
303 }
304 }
305 #endif
306
307 util_cache_clear(cache);
308
309 FREE(cache->entries);
310 FREE(cache);
311 }
312
313
314 /**
315 * Remove the cache entry which matches the given key.
316 */
317 void
util_cache_remove(struct util_cache * cache,const void * key)318 util_cache_remove(struct util_cache *cache,
319 const void *key)
320 {
321 struct util_cache_entry *entry;
322 uint32_t hash;
323
324 assert(cache);
325 if (!cache)
326 return;
327
328 hash = cache->hash(key);
329
330 entry = util_cache_entry_get(cache, hash, key);
331 if (!entry)
332 return;
333
334 if (entry->state == FILLED)
335 util_cache_entry_destroy(cache, entry);
336
337 ensure_sanity(cache);
338 }
339
340
341 static void
ensure_sanity(const struct util_cache * cache)342 ensure_sanity(const struct util_cache *cache)
343 {
344 #ifdef DEBUG
345 unsigned i, cnt = 0;
346
347 assert(cache);
348 for (i = 0; i < cache->size; i++) {
349 struct util_cache_entry *header = &cache->entries[i];
350
351 assert(header);
352 assert(header->state == FILLED ||
353 header->state == EMPTY ||
354 header->state == DELETED);
355 if (header->state == FILLED) {
356 cnt++;
357 assert(header->hash == cache->hash(header->key));
358 }
359 }
360
361 assert(cnt == cache->count);
362 assert(cache->size >= cnt);
363
364 if (cache->count == 0) {
365 assert (is_empty_list(&cache->lru));
366 }
367 else {
368 struct util_cache_entry *header = cache->lru.next;
369
370 assert (header);
371 assert (!is_empty_list(&cache->lru));
372
373 for (i = 0; i < cache->count; i++)
374 header = header->next;
375
376 assert(header == &cache->lru);
377 }
378 #endif
379
380 (void)cache;
381 }
382