blob: 4a46505f334d46b33e5456fb79460f62ee92799c [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 <import/lru.h>
26
27/* Minimal list manipulation macros for lru64_list */
28#define LIST_ADD(lh, el) ({ (el)->n = (lh)->n; (el)->n->p = (lh)->n = (el); (el)->p = (lh); })
29#define LIST_DEL(el) ({ (el)->n->p = (el)->p; (el)->p->n = (el)->n; })
30
Christopher Faulet92939d22015-06-11 13:33:13 +020031
32/* Lookup key <key> in LRU cache <lru> for use with domain <domain> whose data's
33 * current version is <revision>. It differs from lru64_get as it does not
34 * create missing keys. The function returns NULL if an error or a cache miss
35 * occurs. */
36struct lru64 *lru64_lookup(unsigned long long key, struct lru64_head *lru,
37 void *domain, unsigned long long revision)
38{
39 struct eb64_node *node;
40 struct lru64 *elem;
41
42 if (!lru->spare) {
43 if (!lru->cache_size)
44 return NULL;
45 lru->spare = malloc(sizeof(*lru->spare));
46 if (!lru->spare)
47 return NULL;
48 lru->spare->domain = NULL;
49 }
50
51 node = __eb64_lookup(&lru->keys, key);
52 elem = container_of(node, typeof(*elem), node);
53 if (elem) {
54 /* Existing entry found, check validity then move it at the
55 * head of the LRU list.
56 */
57 if (elem->domain == domain && elem->revision == revision) {
58 LIST_DEL(&elem->lru);
59 LIST_ADD(&lru->list, &elem->lru);
60 return elem;
61 }
62 }
63 return NULL;
64}
65
Willy Tarreau69c696c2015-04-28 10:18:09 +020066/* Get key <key> from LRU cache <lru> for use with domain <domain> whose data's
67 * current revision is <revision>. If the key doesn't exist it's first created
68 * with ->domain = NULL. The caller detects this situation by checking ->domain
69 * and must perform the operation to be cached then call lru64_commit() to
70 * complete the operation. A lock (mutex or spinlock) may be added around the
71 * function to permit use in a multi-threaded environment. The function may
72 * return NULL upon memory allocation failure.
73 */
74struct lru64 *lru64_get(unsigned long long key, struct lru64_head *lru,
75 void *domain, unsigned long long revision)
76{
77 struct eb64_node *node;
78 struct lru64 *elem;
79
80 if (!lru->spare) {
81 if (!lru->cache_size)
82 return NULL;
83 lru->spare = malloc(sizeof(*lru->spare));
84 if (!lru->spare)
85 return NULL;
86 lru->spare->domain = NULL;
87 }
88
89 /* Lookup or insert */
90 lru->spare->node.key = key;
91 node = __eb64_insert(&lru->keys, &lru->spare->node);
92 elem = container_of(node, typeof(*elem), node);
93
94 if (elem != lru->spare) {
95 /* Existing entry found, check validity then move it at the
96 * head of the LRU list.
97 */
98 if (elem->domain == domain && elem->revision == revision) {
99 LIST_DEL(&elem->lru);
100 LIST_ADD(&lru->list, &elem->lru);
101 return elem;
102 }
103
104 if (!elem->domain)
105 return NULL; // currently locked
106
107 /* recycle this entry */
108 LIST_DEL(&elem->lru);
109 }
110 else {
111 /* New entry inserted, initialize and move to the head of the
112 * LRU list, and lock it until commit.
113 */
114 lru->cache_usage++;
115 lru->spare = NULL; // used, need a new one next time
116 }
117
118 elem->domain = NULL;
119 LIST_ADD(&lru->list, &elem->lru);
120
121 if (lru->cache_usage > lru->cache_size) {
122 /* try to kill oldest entry */
123 struct lru64 *old;
124
125 old = container_of(lru->list.p, typeof(*old), lru);
126 if (old->domain) {
127 /* not locked */
128 LIST_DEL(&old->lru);
129 __eb64_delete(&old->node);
Willy Tarreau57b8a532015-06-17 20:33:30 +0200130 if (old->data && old->free)
131 old->free(old->data);
Willy Tarreau69c696c2015-04-28 10:18:09 +0200132 if (!lru->spare)
133 lru->spare = old;
Christopher Fauletf90ac552015-06-09 17:06:17 +0200134 else {
Willy Tarreau69c696c2015-04-28 10:18:09 +0200135 free(old);
Christopher Fauletf90ac552015-06-09 17:06:17 +0200136 }
Willy Tarreau69c696c2015-04-28 10:18:09 +0200137 lru->cache_usage--;
138 }
139 }
140 return elem;
141}
142
143/* Commit element <elem> with data <data>, domain <domain> and revision
144 * <revision>. <elem> is checked for NULL so that it's possible to call it
145 * with the result from a call to lru64_get(). The caller might lock it using a
146 * spinlock or mutex shared with the one around lru64_get().
147 */
Christopher Fauletf90ac552015-06-09 17:06:17 +0200148void lru64_commit(struct lru64 *elem, void *data, void *domain,
149 unsigned long long revision, void (*free)(void *))
Willy Tarreau69c696c2015-04-28 10:18:09 +0200150{
151 if (!elem)
152 return;
153
154 elem->data = data;
155 elem->revision = revision;
156 elem->domain = domain;
Christopher Fauletf90ac552015-06-09 17:06:17 +0200157 elem->free = free;
Willy Tarreau69c696c2015-04-28 10:18:09 +0200158}
159
160/* Create a new LRU cache of <size> entries. Returns the new cache or NULL in
161 * case of allocation failure.
162 */
163struct lru64_head *lru64_new(int size)
164{
165 struct lru64_head *lru;
166
167 lru = malloc(sizeof(*lru));
168 if (lru) {
169 lru->list.p = lru->list.n = &lru->list;
170 lru->keys = EB_ROOT_UNIQUE;
171 lru->spare = NULL;
172 lru->cache_size = size;
173 lru->cache_usage = 0;
174 }
175 return lru;
176}
177
178/* Tries to destroy the LRU cache <lru>. Returns the number of locked entries
179 * that prevent it from being destroyed, or zero meaning everything was done.
180 */
181int lru64_destroy(struct lru64_head *lru)
182{
183 struct lru64 *elem, *next;
184
185 if (!lru)
186 return 0;
187
188 elem = container_of(lru->list.p, typeof(*elem), lru);
189 while (&elem->lru != &lru->list) {
190 next = container_of(elem->lru.p, typeof(*next), lru);
191 if (elem->domain) {
192 /* not locked */
193 LIST_DEL(&elem->lru);
194 eb64_delete(&elem->node);
Willy Tarreau7810ad72015-06-17 19:53:03 +0200195 if (elem->data && elem->free)
Christopher Fauletf90ac552015-06-09 17:06:17 +0200196 elem->free(elem->data);
Willy Tarreau69c696c2015-04-28 10:18:09 +0200197 free(elem);
198 lru->cache_usage--;
199 lru->cache_size--;
200 }
201 elem = next;
202 }
203
204 if (lru->cache_usage)
205 return lru->cache_usage;
206
207 free(lru);
208 return 0;
209}
210
211/* The code below is just for validation and performance testing. It's an
212 * example of a function taking some time to return results that could be
213 * cached.
214 */
215#ifdef STANDALONE
216
217#include <stdio.h>
218
219static unsigned int misses;
220
221static unsigned long long sum(unsigned long long x)
222{
223#ifndef TEST_LRU_FAST_OPERATION
224 if (x < 1)
225 return 0;
226 return x + sum(x * 99 / 100 - 1);
227#else
228 return (x << 16) - (x << 8) - 1;
229#endif
230}
231
232static long get_value(struct lru64_head *lru, long a)
233{
234 struct lru64 *item;
235
236 if (lru) {
237 item = lru64_get(a, lru, lru, 0);
238 if (item && item->domain)
239 return (long)item->data;
240 }
241 misses++;
242 /* do the painful work here */
243 a = sum(a);
244 if (item)
245 lru64_commit(item, (void *)a, lru, 0);
246 return a;
247}
248
249/* pass #of loops in argv[1] and set argv[2] to something to use the LRU */
250int main(int argc, char **argv)
251{
252 struct lru64_head *lru = NULL;
253 long long ret;
254 int total, loops;
255
256 if (argc < 2) {
257 printf("Need a number of rounds and optionally an LRU cache size (0..65536)\n");
258 exit(1);
259 }
260
261 total = atoi(argv[1]);
262
263 if (argc > 2) /* cache size */
264 lru = lru64_new(atoi(argv[2]));
265
266 ret = 0;
267 for (loops = 0; loops < total; loops++) {
268 ret += get_value(lru, rand() & 65535);
269 }
270 /* just for accuracy control */
271 printf("ret=%llx, hits=%d, misses=%d (%d %% hits)\n", ret, total-misses, misses, (int)((float)(total-misses) * 100.0 / total));
272
273 while (lru64_destroy(lru));
274
275 return 0;
276}
277
278#endif