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