2 * Copyright (c) 2019 Sine Nomine Associates. All rights reserved.
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
7 * 1. Redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer.
9 * 2. Redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution.
13 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR `AS IS'' AND ANY EXPRESS OR
14 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
15 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
16 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
17 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
18 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
19 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
20 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
21 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
22 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26 * opr_cache - A simple general-purpose in-memory cache implementation. Keys
27 * and values are simple flat memory buffers (keys are compared with memcmp),
28 * and currently the only cache eviction strategy is a semi-random approach. We
29 * hash values using opr_jhash_opaque.
32 #include <afsconfig.h>
33 #include <afs/param.h>
39 #include <opr/queue.h>
40 #include <opr/jhash.h>
41 #ifdef AFS_PTHREAD_ENV
42 # include <opr/lock.h>
44 # include <opr/lockstub.h>
47 #define MIN_BUCKETS (4)
48 #define MAX_BUCKETS (1024*1024)
50 #define MIN_ENTRIES (4)
51 #define MAX_ENTRIES (1024*1024*1024)
55 * This lock protects everything in the opr_cache structure. This lock must
56 * be held before touching anything in opr_cache, and before calling any of
57 * our internal functions (unless we're allocating or freeing the cache; in
58 * which case, we had better be the only one touching it!).
62 /* How many items are present in the cache? */
65 /* The max number of items we can hold in the cache. */
66 afs_uint32 max_entries;
68 /* Our dictionary holding the cached items. Contains cache_entry structs,
69 * linked together via 'link'. */
70 struct opr_dict *dict;
74 struct opr_queue link;
84 free_entry_contents(struct cache_entry *entry)
86 opr_queue_Remove(&entry->link);
91 entry->key_buf = entry->val_buf = NULL;
92 entry->key_len = entry->val_len = 0;
96 * Evict an entry from the cache.
99 * @pre cache->lock is held.
101 * @param[in] cache The opr_cache to use.
102 * @param[out] a_entry Set to the cache entry that was evicted. Its contents
103 * have been freed; it can be treated like a
104 * newly-allocated cache entry.
107 evict_entry(struct opr_cache *cache, struct cache_entry **a_entry)
109 unsigned int safety, bucket;
110 struct cache_entry *entry = NULL;
112 opr_Assert(cache->dict->size > 0);
113 opr_Assert(cache->n_entries > 0);
116 * For cache eviction, we pick an entry somewhat randomly, since random
117 * eviction performs fairly well, and is very simple to implement.
119 * Our approach slightly differs from pure random eviction: we pick a
120 * random hash bucket, and evict the least-recently-used entry in that
121 * bucket. If the bucket we picked is empty, just use the next bucket.
123 bucket = rand() % cache->dict->size;
125 for (safety = 0; safety < cache->dict->size; safety++) {
126 struct opr_queue *chain;
127 chain = &cache->dict->table[bucket];
129 if (!opr_queue_IsEmpty(chain)) {
130 entry = opr_queue_Last(chain, struct cache_entry, link);
135 bucket = bucket % cache->dict->size;
137 opr_Assert(entry != NULL);
139 free_entry_contents(entry);
145 * Alloc a new entry in the cache.
147 * @pre cache->lock is held.
148 * @pre The given key does not already exist in the cache.
150 * @param[in] cache The opr_cache to use.
151 * @param[inout] a_key_buf The key for the new cache entry. Set to NULL on
152 * success; the memory is used in the new cache entry,
153 * and must not be freed or otherwise used by the
155 * @param[in] key_len The size of *a_key_buf.
156 * @param[out] a_entry Set to the new cache entry on success. The entry has
157 * been inserted into the cache, and the key has been
158 * populated; it looks identical to a normal entry in the
159 * cache, except the value is set to NULL.
161 * @return errno status codes
164 alloc_entry(struct opr_cache *cache, void **a_key_buf, size_t key_len,
165 struct cache_entry **a_entry)
167 struct cache_entry *entry = NULL;
170 if (cache->n_entries >= cache->max_entries) {
172 * The cache is full. "Alloc" an entry by picking an existing entry to
173 * evict, and just re-use that entry.
175 evict_entry(cache, &entry);
178 entry = calloc(1, sizeof(*entry));
185 entry->key_len = key_len;
186 entry->key_buf = *a_key_buf;
189 hash = opr_jhash_opaque(entry->key_buf, entry->key_len, 0);
190 opr_dict_Prepend(cache->dict, hash, &entry->link);
197 * Find a cache entry in the cache.
199 * @pre cache->lock is held.
201 * @param[in] cache The opr_cache to use.
202 * @param[in] key_buf The key of the entry to find.
203 * @param[in] key_len The size of 'key_buf'.
204 * @param[out] a_entry The found cache entry.
206 * @return errno status codes
207 * @retval ENOENT The given key does not exist in the cache.
210 find_entry(struct opr_cache *cache, void *key_buf, size_t key_len,
211 struct cache_entry **a_entry)
213 struct opr_queue *cursor;
216 hash = opr_jhash_opaque(key_buf, key_len, 0);
218 for (opr_dict_ScanBucket(cache->dict, hash, cursor)) {
219 struct cache_entry *entry;
220 entry = opr_queue_Entry(cursor, struct cache_entry, link);
221 if (key_len != entry->key_len) {
224 if (memcmp(key_buf, entry->key_buf, key_len) != 0) {
227 opr_dict_Promote(cache->dict, hash, &entry->link);
236 * Fetch an item from the cache.
238 * If NULL is given for 'cache' or 'key_buf', or if 0 is given for key_len, we
239 * always return ENOENT. Conceptually, we treat a NULL cache as an empty cache,
240 * and NULL/0-length keys are not allowed in an opr_cache, so returning ENOENT
241 * in these cases is consistent.
243 * @param[in] cache The opr_cache to use.
244 * @param[in] key_buf The key to lookup.
245 * @param[in] key_len The size of 'key_buf'.
246 * @param[out] val_buf On success, where to store the looked-up value.
247 * @param[inout] a_val_len On entry, set to the max size available in
248 * 'val_buf'. On successful return, set to the number
249 * of bytes copied into 'val_buf'.
250 * @return errno status codes
252 * @retval ENOENT key not found
253 * @retval ENOSPC a_val_len is too small to store the retrieved value
256 opr_cache_get(struct opr_cache *cache, void *key_buf, size_t key_len,
257 void *val_buf, size_t *a_val_len)
259 struct cache_entry *entry;
262 if (cache == NULL || key_buf == NULL || key_len < 1) {
266 opr_mutex_enter(&cache->lock);
268 code = find_entry(cache, key_buf, key_len, &entry);
273 if (entry->val_len > *a_val_len) {
278 memcpy(val_buf, entry->val_buf, entry->val_len);
279 *a_val_len = entry->val_len;
282 opr_mutex_exit(&cache->lock);
287 memdup(void *src, size_t len)
289 void *buf = malloc(len);
293 memcpy(buf, src, len);
298 * Store an item in the cache.
300 * This operation is a no-op if NULL is given for 'cache', 'key_buf', or
301 * 'val_buf', or if 'key_len' or 'val_len' are 0. Conceptually, a NULL
302 * opr_cache represents an empty cache, and NULL/0-length keys and values are
303 * not allowed in an opr_cache.
305 * @param[in] cache The opr_cache to use.
306 * @param[in] key_buf The key for the stored value.
307 * @param[in] key_len The size of 'key_buf'.
308 * @param[in] val_buf The value to store.
309 * @param[in] val_len The size of 'val_buf'.
312 opr_cache_put(struct opr_cache *cache, void *key_buf, size_t key_len,
313 void *val_buf, size_t val_len)
316 struct cache_entry *entry;
317 void *key_dup = NULL;
318 void *val_dup = NULL;
320 if (cache == NULL || key_buf == NULL || val_buf == NULL || key_len < 1 ||
325 key_dup = memdup(key_buf, key_len);
326 val_dup = memdup(val_buf, val_len);
327 if (key_dup == NULL || val_dup == NULL) {
331 opr_mutex_enter(&cache->lock);
333 code = find_entry(cache, key_buf, key_len, &entry);
334 if (code == ENOENT) {
335 code = alloc_entry(cache, &key_dup, key_len, &entry);
341 free(entry->val_buf);
342 entry->val_buf = val_dup;
343 entry->val_len = val_len;
347 opr_mutex_exit(&cache->lock);
354 isPowerOf2(int value)
356 return (value > 0) && (value & (value - 1)) == 0;
360 * Create a new opr_cache.
362 * @param[in] opts What options to use for the cache.
363 * @param[out] a_cache The newly-allocated cache.
365 * @return errno status codes
366 * @retval EINVAL invalid option values
369 opr_cache_init(struct opr_cache_opts *opts, struct opr_cache **a_cache)
371 struct opr_cache *cache;
373 if (opts->n_buckets < MIN_BUCKETS || opts->n_buckets > MAX_BUCKETS) {
376 if (!isPowerOf2(opts->n_buckets)) {
379 if (opts->max_entries < MIN_ENTRIES || opts->max_entries > MAX_ENTRIES) {
383 cache = calloc(1, sizeof(*cache));
388 opr_mutex_init(&cache->lock);
389 cache->max_entries = opts->max_entries;
391 cache->dict = opr_dict_Init(opts->n_buckets);
392 if (cache->dict == NULL) {
393 opr_cache_free(&cache);
404 * @param[inout] a_cache The cache to free. Set to NULL on return.
407 opr_cache_free(struct opr_cache **a_cache)
409 struct opr_cache *cache = *a_cache;
415 if (cache->dict != NULL) {
417 for (bucket = 0; bucket < cache->dict->size; bucket++) {
418 struct opr_queue *cursor, *tmp;
419 for (opr_dict_ScanBucketSafe(cache->dict, bucket, cursor, tmp)) {
420 struct cache_entry *entry;
421 entry = opr_queue_Entry(cursor, struct cache_entry, link);
422 free_entry_contents(entry);
426 opr_dict_Free(&cache->dict);
429 opr_mutex_destroy(&cache->lock);