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