u_cache.c revision 20962bf547f7beabf3a5125552fff81a01136dbb
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 48struct 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 65struct 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#define CACHE_DEFAULT_ALPHA 2 85 86struct util_cache * 87util_cache_create(uint32_t (*hash)(const void *key), 88 int (*compare)(const void *key1, const void *key2), 89 void (*destroy)(void *key, void *value), 90 uint32_t size) 91{ 92 struct util_cache *cache; 93 94 cache = CALLOC_STRUCT(util_cache); 95 if(!cache) 96 return NULL; 97 98 cache->hash = hash; 99 cache->compare = compare; 100 cache->destroy = destroy; 101 102 make_empty_list(&cache->lru); 103 104 size *= CACHE_DEFAULT_ALPHA; 105 cache->size = size; 106 107 cache->entries = CALLOC(size, sizeof(struct util_cache_entry)); 108 if(!cache->entries) { 109 FREE(cache); 110 return NULL; 111 } 112 113 return cache; 114} 115 116 117static struct util_cache_entry * 118util_cache_entry_get(struct util_cache *cache, 119 uint32_t hash, 120 const void *key) 121{ 122 struct util_cache_entry *first_unfilled = NULL; 123 uint32_t index = hash % cache->size; 124 uint32_t probe; 125 126 /* Probe until we find either a matching FILLED entry or an EMPTY 127 * slot (which has never been occupied). 128 * 129 * Deleted or non-matching slots are not indicative of completion 130 * as a previous linear probe for the same key could have continued 131 * past this point. 132 */ 133 for (probe = 0; probe < cache->size; probe++) { 134 uint32_t i = (index + probe) % cache->size; 135 struct util_cache_entry *current = &cache->entries[i]; 136 137 if (current->state == FILLED) { 138 if (current->hash == hash && 139 cache->compare(key, current->key) == 0) 140 return current; 141 } 142 else { 143 if (!first_unfilled) 144 first_unfilled = current; 145 146 if (current->state == EMPTY) 147 return first_unfilled; 148 } 149 } 150 151 return NULL; 152} 153 154static INLINE void 155util_cache_entry_destroy(struct util_cache *cache, 156 struct util_cache_entry *entry) 157{ 158 void *key = entry->key; 159 void *value = entry->value; 160 161 entry->key = NULL; 162 entry->value = NULL; 163 164 if (entry->state == FILLED) { 165 remove_from_list(entry); 166 cache->count--; 167 168 if(cache->destroy) 169 cache->destroy(key, value); 170 171 entry->state = DELETED; 172 } 173} 174 175 176void 177util_cache_set(struct util_cache *cache, 178 void *key, 179 void *value) 180{ 181 struct util_cache_entry *entry; 182 uint32_t hash = cache->hash(key); 183 184 assert(cache); 185 if (!cache) 186 return; 187 188 entry = util_cache_entry_get(cache, hash, key); 189 if (!entry || cache->count >= cache->size / CACHE_DEFAULT_ALPHA) { 190 entry = cache->lru.prev; 191 } 192 193 util_cache_entry_destroy(cache, entry); 194 195#ifdef DEBUG 196 ++entry->count; 197#endif 198 199 entry->key = key; 200 entry->hash = hash; 201 entry->value = value; 202 entry->state = FILLED; 203 insert_at_head(&cache->lru, entry); 204 cache->count++; 205} 206 207 208void * 209util_cache_get(struct util_cache *cache, 210 const void *key) 211{ 212 struct util_cache_entry *entry; 213 uint32_t hash = cache->hash(key); 214 215 assert(cache); 216 if (!cache) 217 return NULL; 218 219 entry = util_cache_entry_get(cache, hash, key); 220 if (!entry) 221 return NULL; 222 223 if (entry->state == FILLED) 224 move_to_head(&cache->lru, entry); 225 226 return entry->value; 227} 228 229 230void 231util_cache_clear(struct util_cache *cache) 232{ 233 uint32_t i; 234 235 assert(cache); 236 if (!cache) 237 return; 238 239 for(i = 0; i < cache->size; ++i) { 240 util_cache_entry_destroy(cache, &cache->entries[i]); 241 cache->entries[i].state = EMPTY; 242 } 243 244 assert(cache->count == 0); 245 assert(is_empty_list(&cache->lru)); 246} 247 248 249void 250util_cache_destroy(struct util_cache *cache) 251{ 252 assert(cache); 253 if (!cache) 254 return; 255 256#ifdef DEBUG 257 if(cache->count >= 20*cache->size) { 258 /* Normal approximation of the Poisson distribution */ 259 double mean = (double)cache->count/(double)cache->size; 260 double stddev = sqrt(mean); 261 unsigned i; 262 for(i = 0; i < cache->size; ++i) { 263 double z = fabs(cache->entries[i].count - mean)/stddev; 264 /* This assert should not fail 99.9999998027% of the times, unless 265 * the hash function is a poor one */ 266 assert(z <= 6.0); 267 } 268 } 269#endif 270 271 util_cache_clear(cache); 272 273 FREE(cache->entries); 274 FREE(cache); 275} 276 277 278void 279util_cache_remove(struct util_cache *cache, 280 const void *key) 281{ 282 struct util_cache_entry *entry; 283 uint32_t hash; 284 285 assert(cache); 286 if (!cache) 287 return; 288 289 hash = cache->hash(key); 290 291 entry = util_cache_entry_get(cache, hash, key); 292 if (!entry) 293 return; 294 295 if (entry->state == FILLED) 296 util_cache_entry_destroy(cache, entry); 297} 298