opr: Introduce opr_cache
[openafs.git] / 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 }