src/opr/cache.c

   1 /*
   2  * Copyright (c) 2019 Sine Nomine Associates. All rights reserved.
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions
   6  * are met:
   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.
  12  *
  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.
  23  */
  24
  25 /*
  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.
  30  */
  31
  32 #include <afsconfig.h>
  33 #include <afs/param.h>
  34
  35 #include <roken.h>
  36 #include <afs/opr.h>
  37
  38 #include <opr/dict.h>
  39 #include <opr/queue.h>
  40 #include <opr/jhash.h>
  41 #ifdef AFS_PTHREAD_ENV
  42 # include <opr/lock.h>
  43 #else
  44 # include <opr/lockstub.h>
  45 #endif
  46
  47 #define MIN_BUCKETS (4)
  48 #define MAX_BUCKETS (1024*1024)
  49
  50 #define MIN_ENTRIES (4)
  51 #define MAX_ENTRIES (1024*1024*1024)
  52
  53 struct opr_cache {
  54     /*
  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!).
  59      */
  60     opr_mutex_t lock;
  61
  62     /* How many items are present in the cache? */
  63     afs_uint32 n_entries;
  64
  65     /* The max number of items we can hold in the cache. */
  66     afs_uint32 max_entries;
  67
  68     /* Our dictionary holding the cached items. Contains cache_entry structs,
  69      * linked together via 'link'. */
  70     struct opr_dict *dict;
  71 };
  72
  73 struct cache_entry {
  74     struct opr_queue link;
  75
  76     size_t key_len;
  77     void *key_buf;
  78
  79     size_t val_len;
  80     void *val_buf;
  81 };
  82
  83 static void
  84 free_entry_contents(struct cache_entry *entry)
  85 {
  86     opr_queue_Remove(&entry->link);
  87
  88     free(entry->key_buf);
  89     free(entry->val_buf);
  90
  91     entry->key_buf = entry->val_buf = NULL;
  92     entry->key_len = entry->val_len = 0;
  93 }
  94
  95 /**
  96  * Evict an entry from the cache.
  97  *
  98  * @pre cache is full.
  99  * @pre cache->lock is held.
 100  *
 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.
 105  */
 106 static void
 107 evict_entry(struct opr_cache *cache, struct cache_entry **a_entry)
 108 {
 109     unsigned int safety, bucket;
 110     struct cache_entry *entry = NULL;
 111
 112     opr_Assert(cache->dict->size > 0);
 113     opr_Assert(cache->n_entries > 0);
 114
 115     /*
 116      * For cache eviction, we pick an entry somewhat randomly, since random
 117      * eviction performs fairly well, and is very simple to implement.
 118      *
 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.
 122      */
 123     bucket = rand() % cache->dict->size;
 124
 125     for (safety = 0; safety < cache->dict->size; safety++) {
 126         struct opr_queue *chain;
 127         chain = &cache->dict->table[bucket];
 128
 129         if (!opr_queue_IsEmpty(chain)) {
 130             entry = opr_queue_Last(chain, struct cache_entry, link);
 131             break;
 132         }
 133
 134         bucket++;
 135         bucket = bucket % cache->dict->size;
 136     }
 137     opr_Assert(entry != NULL);
 138
 139     free_entry_contents(entry);
 140
 141     *a_entry = entry;
 142 }
 143
 144 /**
 145  * Alloc a new entry in the cache.
 146  *
 147  * @pre cache->lock is held.
 148  * @pre The given key does not already exist in the cache.
 149  *
 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
 154  *                          caller.
 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.
 160  *
 161  * @return errno status codes
 162  */
 163 static int
 164 alloc_entry(struct opr_cache *cache, void **a_key_buf, size_t key_len,
 165             struct cache_entry **a_entry)
 166 {
 167     struct cache_entry *entry = NULL;
 168     unsigned int hash;
 169
 170     if (cache->n_entries >= cache->max_entries) {
 171         /*
 172          * The cache is full. "Alloc" an entry by picking an existing entry to
 173          * evict, and just re-use that entry.
 174          */
 175         evict_entry(cache, &entry);
 176
 177     } else {
 178         entry = calloc(1, sizeof(*entry));
 179         if (entry == NULL) {
 180             return ENOMEM;
 181         }
 182         cache->n_entries++;
 183     }
 184
 185     entry->key_len = key_len;
 186     entry->key_buf = *a_key_buf;
 187     *a_key_buf = NULL;
 188
 189     hash = opr_jhash_opaque(entry->key_buf, entry->key_len, 0);
 190     opr_dict_Prepend(cache->dict, hash, &entry->link);
 191
 192     *a_entry = entry;
 193     return 0;
 194 }
 195
 196 /**
 197  * Find a cache entry in the cache.
 198  *
 199  * @pre cache->lock is held.
 200  *
 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.
 205  *
 206  * @return errno status codes
 207  * @retval ENOENT The given key does not exist in the cache.
 208  */
 209 static int
 210 find_entry(struct opr_cache *cache, void *key_buf, size_t key_len,
 211            struct cache_entry **a_entry)
 212 {
 213     struct opr_queue *cursor;
 214     unsigned int hash;
 215
 216     hash = opr_jhash_opaque(key_buf, key_len, 0);
 217
 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) {
 222             continue;
 223         }
 224         if (memcmp(key_buf, entry->key_buf, key_len) != 0) {
 225             continue;
 226         }
 227         opr_dict_Promote(cache->dict, hash, &entry->link);
 228         *a_entry = entry;
 229         return 0;
 230     }
 231
 232     return ENOENT;
 233 }
 234
 235 /**
 236  * Fetch an item from the cache.
 237  *
 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.
 242  *
 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
 251  * @retval 0 success
 252  * @retval ENOENT key not found
 253  * @retval ENOSPC a_val_len is too small to store the retrieved value
 254  */
 255 int
 256 opr_cache_get(struct opr_cache *cache, void *key_buf, size_t key_len,
 257               void *val_buf, size_t *a_val_len)
 258 {
 259     struct cache_entry *entry;
 260     int code;
 261
 262     if (cache == NULL || key_buf == NULL || key_len < 1) {
 263         return ENOENT;
 264     }
 265
 266     opr_mutex_enter(&cache->lock);
 267
 268     code = find_entry(cache, key_buf, key_len, &entry);
 269     if (code != 0) {
 270         goto done;
 271     }
 272
 273     if (entry->val_len > *a_val_len) {
 274         code = ENOSPC;
 275         goto done;
 276     }
 277
 278     memcpy(val_buf, entry->val_buf, entry->val_len);
 279     *a_val_len = entry->val_len;
 280
 281  done:
 282     opr_mutex_exit(&cache->lock);
 283     return code;
 284 }
 285
 286 static void*
 287 memdup(void *src, size_t len)
 288 {
 289     void *buf = malloc(len);
 290     if (buf == NULL) {
 291         return NULL;
 292     }
 293     memcpy(buf, src, len);
 294     return buf;
 295 }
 296
 297 /**
 298  * Store an item in the cache.
 299  *
 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.
 304  *
 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'.
 310  */
 311 void
 312 opr_cache_put(struct opr_cache *cache, void *key_buf, size_t key_len,
 313               void *val_buf, size_t val_len)
 314 {
 315     int code;
 316     struct cache_entry *entry;
 317     void *key_dup = NULL;
 318     void *val_dup = NULL;
 319
 320     if (cache == NULL || key_buf == NULL || val_buf == NULL || key_len < 1 ||
 321         val_len < 1) {
 322         goto done;
 323     }
 324
 325     key_dup = memdup(key_buf, key_len);
 326     val_dup = memdup(val_buf, val_len);
 327     if (key_dup == NULL || val_dup == NULL) {
 328         goto done;
 329     }
 330
 331     opr_mutex_enter(&cache->lock);
 332
 333     code = find_entry(cache, key_buf, key_len, &entry);
 334     if (code == ENOENT) {
 335         code = alloc_entry(cache, &key_dup, key_len, &entry);
 336     }
 337     if (code != 0) {
 338         goto done_locked;
 339     }
 340
 341     free(entry->val_buf);
 342     entry->val_buf = val_dup;
 343     entry->val_len = val_len;
 344     val_dup = NULL;
 345
 346  done_locked:
 347     opr_mutex_exit(&cache->lock);
 348  done:
 349     free(key_dup);
 350     free(val_dup);
 351 }
 352
 353 static_inline int
 354 isPowerOf2(int value)
 355 {
 356     return (value > 0) && (value & (value - 1)) == 0;
 357 }
 358
 359 /**
 360  * Create a new opr_cache.
 361  *
 362  * @param[in] opts  What options to use for the cache.
 363  * @param[out] a_cache  The newly-allocated cache.
 364  *
 365  * @return errno status codes
 366  * @retval EINVAL   invalid option values
 367  */
 368 int
 369 opr_cache_init(struct opr_cache_opts *opts, struct opr_cache **a_cache)
 370 {
 371     struct opr_cache *cache;
 372
 373     if (opts->n_buckets < MIN_BUCKETS || opts->n_buckets > MAX_BUCKETS) {
 374         return EINVAL;
 375     }
 376     if (!isPowerOf2(opts->n_buckets)) {
 377         return EINVAL;
 378     }
 379     if (opts->max_entries < MIN_ENTRIES || opts->max_entries > MAX_ENTRIES) {
 380         return EINVAL;
 381     }
 382
 383     cache = calloc(1, sizeof(*cache));
 384     if (cache == NULL) {
 385         return ENOMEM;
 386     }
 387
 388     opr_mutex_init(&cache->lock);
 389     cache->max_entries = opts->max_entries;
 390
 391     cache->dict = opr_dict_Init(opts->n_buckets);
 392     if (cache->dict == NULL) {
 393         opr_cache_free(&cache);
 394         return ENOMEM;
 395     }
 396
 397     *a_cache = cache;
 398     return 0;
 399 }
 400
 401 /**
 402  * Free an opr_cache.
 403  *
 404  * @param[inout] a_cache    The cache to free. Set to NULL on return.
 405  */
 406 void
 407 opr_cache_free(struct opr_cache **a_cache)
 408 {
 409     struct opr_cache *cache = *a_cache;
 410     if (cache == NULL) {
 411         return;
 412     }
 413     *a_cache = NULL;
 414
 415     if (cache->dict != NULL) {
 416         int bucket;
 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);
 423                 free(entry);
 424             }
 425         }
 426         opr_dict_Free(&cache->dict);
 427     }
 428
 429     opr_mutex_destroy(&cache->lock);
 430
 431     free(cache);
 432 }