1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
|
/*
* Copyright (C) 2015 Willy Tarreau <w@1wt.eu>
*
* Permission is hereby granted, free of charge, to any person obtaining
* a copy of this software and associated documentation files (the
* "Software"), to deal in the Software without restriction, including
* without limitation the rights to use, copy, modify, merge, publish,
* distribute, sublicense, and/or sell copies of the Software, and to
* permit persons to whom the Software is furnished to do so, subject to
* the following conditions:
*
* The above copyright notice and this permission notice shall be
* included in all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
* OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
* HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
* WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
* OTHER DEALINGS IN THE SOFTWARE.
*/
#include <import/eb64tree.h>
/* The LRU supports a global cache shared between multiple domains and multiple
* versions of their datasets. The purpose is not to have to flush the whole
* LRU once a key is updated and not valid anymore (eg: ACL files), as well as
* to reliably support concurrent accesses and handle conflicts gracefully. For
* each key a pointer to a dataset and its internal data revision are stored.
* All lookups verify that these elements match those passed by the caller and
* only return a valid entry upon matching. Otherwise the entry is either
* allocated or recycled and considered new. New entries are always initialized
* with a NULL domain pointer which is used by the caller to detect that the
* entry is new and must be populated. Such entries never expire and are
* protected from the risk of being recycled. It's then the caller's
* responsibility to perform the operation and commit the entry with its latest
* result. This domain thus serves as a lock to protect the entry during all
* the computation needed to update it. In a simple use case where the cache is
* dedicated, it is recommended to pass the LRU head as the domain pointer and
* for example zero as the revision. The most common use case for the caller
* consists in simply checking that the return is not null and that the domain
* is not null, then to use the result. The get() function returns null if it
* cannot allocate a node (memory or key being currently updated).
*/
struct lru64_list {
struct lru64_list *n;
struct lru64_list *p;
};
struct lru64_head {
struct lru64_list list;
struct eb_root keys;
struct lru64 *spare;
int cache_size;
int cache_usage;
};
struct lru64 {
struct eb64_node node; /* indexing key, typically a hash64 */
struct lru64_list lru; /* LRU list */
void *domain; /* who this data belongs to */
unsigned long long revision; /* data revision (to avoid use-after-free) */
void *data; /* returned value, user decides how to use this */
void (*free)(void *data); /* function to release data, if needed */
};
struct lru64 *lru64_lookup(unsigned long long key, struct lru64_head *lru, void *domain, unsigned long long revision);
struct lru64 *lru64_get(unsigned long long key, struct lru64_head *lru, void *domain, unsigned long long revision);
void lru64_commit(struct lru64 *elem, void *data, void *domain, unsigned long long revision, void (*free)(void *));
struct lru64_head *lru64_new(int size);
int lru64_destroy(struct lru64_head *lru);
void lru64_kill_oldest(struct lru64_head *lru, unsigned long int nb);
|
