src/gallium/auxiliary/util/u_cache.c

   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 *
  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 *
 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
 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
 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 *
 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
 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
 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
 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
 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 }