Add a in-memory cache
[nivanova/samba-autobuild/.git] / source3 / lib / cache.c
1 /*
2    Unix SMB/CIFS implementation.
3    In-memory cache
4    Copyright (C) Volker Lendecke 2007
5
6    This program is free software; you can redistribute it and/or modify
7    it under the terms of the GNU General Public License as published by
8    the Free Software Foundation; either version 3 of the License, or
9    (at your option) any later version.
10
11    This program is distributed in the hope that it will be useful,
12    but WITHOUT ANY WARRANTY; without even the implied warranty of
13    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14    GNU General Public License for more details.
15
16    You should have received a copy of the GNU General Public License
17    along with this program.  If not, see <http://www.gnu.org/licenses/>.
18 */
19
20 #include "cache.h"
21 #include "rbtree.h"
22
23 struct memcache_element {
24         struct rb_node rb_node;
25         struct memcache_element *prev, *next;
26         size_t keylength, valuelength;
27         uint8 n;                /* This is really an enum, but save memory */
28         char data[1];           /* placeholder for offsetof */
29 };
30
31 struct memcache {
32         struct memcache_element *mru, *lru;
33         struct rb_root tree;
34         size_t size;
35         size_t max_size;
36 };
37
38 static int memcache_destructor(struct memcache *cache) {
39         struct memcache_element *e, *next;
40
41         for (e = cache->mru; e != NULL; e = next) {
42                 next = e->next;
43                 SAFE_FREE(e);
44         }
45         return 0;
46 }
47
48 struct memcache *memcache_init(TALLOC_CTX *mem_ctx, size_t max_size)
49 {
50         struct memcache *result;
51
52         result = TALLOC_ZERO_P(mem_ctx, struct memcache);
53         if (result == NULL) {
54                 return NULL;
55         }
56         result->max_size = max_size;
57         talloc_set_destructor(result, memcache_destructor);
58         return result;
59 }
60
61 static struct memcache_element *memcache_node2elem(struct rb_node *node)
62 {
63         return (struct memcache_element *)
64                 ((char *)node - offsetof(struct memcache_element, rb_node));
65 }
66
67 static void memcache_element_parse(struct memcache_element *e,
68                                    DATA_BLOB *key, DATA_BLOB *value)
69 {
70         key->data = ((uint8 *)e) + offsetof(struct memcache_element, data);
71         key->length = e->keylength;
72         value->data = key->data + e->keylength;
73         value->length = e->valuelength;
74 }
75
76 static size_t memcache_element_size(size_t key_length, size_t value_length)
77 {
78         return sizeof(struct memcache_element) - 1 + key_length + value_length;
79 }
80
81 static int memcache_compare(struct memcache_element *e, enum memcache_number n,
82                             DATA_BLOB key)
83 {
84         DATA_BLOB this_key, this_value;
85
86         if ((int)e->n < (int)n) return -1;
87         if ((int)e->n > (int)n) return 1;
88
89         if (e->keylength < key.length) return -1;
90         if (e->keylength > key.length) return 1;
91
92         memcache_element_parse(e, &this_key, &this_value);
93         return memcmp(this_key.data, key.data, key.length);
94 }
95
96 static struct memcache_element *memcache_find(
97         struct memcache *cache, enum memcache_number n, DATA_BLOB key)
98 {
99         struct rb_node *node;
100
101         node = cache->tree.rb_node;
102
103         while (node != NULL) {
104                 struct memcache_element *elem = memcache_node2elem(node);
105                 int cmp;
106
107                 cmp = memcache_compare(elem, n, key);
108                 if (cmp == 0) {
109                         return elem;
110                 }
111                 node = (cmp < 0) ? node->rb_left : node->rb_right;
112         }
113
114         return NULL;
115 }
116
117 bool memcache_lookup(struct memcache *cache, enum memcache_number n,
118                      DATA_BLOB key, DATA_BLOB *value)
119 {
120         struct memcache_element *e;
121
122         e = memcache_find(cache, n, key);
123         if (e == NULL) {
124                 return false;
125         }
126
127         if (cache->size != 0) {
128                 /*
129                  * Do LRU promotion only when we will ever shrink
130                  */
131                 if (e == cache->lru) {
132                         cache->lru = e->prev;
133                 }
134                 DLIST_PROMOTE(cache->mru, e);
135                 if (cache->mru == NULL) {
136                         cache->mru = e;
137                 }
138         }
139
140         memcache_element_parse(e, &key, value);
141         return true;
142 }
143
144 static void memcache_delete_element(struct memcache *cache,
145                                     struct memcache_element *e)
146 {
147         rb_erase(&e->rb_node, &cache->tree);
148
149         if (e == cache->lru) {
150                 cache->lru = e->prev;
151         }
152         DLIST_REMOVE(cache->mru, e);
153
154         cache->size -= memcache_element_size(e->keylength, e->valuelength);
155
156         SAFE_FREE(e);
157 }
158
159 static void memcache_trim(struct memcache *cache)
160 {
161         if (cache->max_size == 0) {
162                 return;
163         }
164
165         while ((cache->size > cache->max_size) && (cache->lru != NULL)) {
166                 memcache_delete_element(cache, cache->lru);
167         }
168 }
169
170 void memcache_delete(struct memcache *cache, enum memcache_number n,
171                      DATA_BLOB key)
172 {
173         struct memcache_element *e;
174
175         e = memcache_find(cache, n, key);
176         if (e == NULL) {
177                 return;
178         }
179
180         memcache_delete_element(cache, e);
181 }
182
183 void memcache_add(struct memcache *cache, enum memcache_number n,
184                   DATA_BLOB key, DATA_BLOB value)
185 {
186         struct memcache_element *e;
187         struct rb_node **p;
188         struct rb_node *parent;
189         DATA_BLOB cache_key, cache_value;
190         size_t element_size;
191
192         if (key.length == 0) {
193                 return;
194         }
195
196         e = memcache_find(cache, n, key);
197
198         if (e != NULL) {
199                 memcache_element_parse(e, &cache_key, &cache_value);
200
201                 if (value.length <= cache_value.length) {
202                         /*
203                          * We can reuse the existing record
204                          */
205                         memcpy(cache_value.data, value.data, value.length);
206                         e->valuelength = value.length;
207                         return;
208                 }
209
210                 memcache_delete_element(cache, e);
211         }
212
213         element_size = memcache_element_size(key.length, value.length);
214
215
216         e = (struct memcache_element *)SMB_MALLOC(element_size);
217
218         if (e == NULL) {
219                 DEBUG(0, ("malloc failed\n"));
220                 return;
221         }
222
223         e->n = n;
224         e->keylength = key.length;
225         e->valuelength = value.length;
226
227         memcache_element_parse(e, &cache_key, &cache_value);
228         memcpy(cache_key.data, key.data, key.length);
229         memcpy(cache_value.data, value.data, value.length);
230
231         parent = NULL;
232         p = &cache->tree.rb_node;
233
234         while (*p) {
235                 struct memcache_element *elem = memcache_node2elem(*p);
236                 int cmp;
237
238                 parent = (*p);
239
240                 cmp = memcache_compare(elem, n, key);
241
242                 p = (cmp < 0) ? &(*p)->rb_left : &(*p)->rb_right;
243         }
244
245         rb_link_node(&e->rb_node, parent, p);
246         rb_insert_color(&e->rb_node, &cache->tree);
247
248         DLIST_ADD(cache->mru, e);
249         if (cache->lru == NULL) {
250                 cache->lru = e;
251         }
252
253         cache->size += element_size;
254         memcache_trim(cache);
255 }
256
257 void memcache_flush(struct memcache *cache, enum memcache_number n)
258 {
259         struct rb_node *node;
260
261         /*
262          * Find the smallest element of number n
263          */
264
265         node = cache->tree.rb_node;
266         if (node == NULL) {
267                 return;
268         }
269
270         while (true) {
271                 struct memcache_element *elem = memcache_node2elem(node);
272                 struct rb_node *next;
273
274                 if ((int)elem->n < (int)n) {
275                         next = node->rb_right;
276                 }
277                 else {
278                         next = node->rb_left;
279                 }
280                 if (next == NULL) {
281                         break;
282                 }
283                 node = next;
284         }
285
286         node = rb_next(node);
287         if (node == NULL) {
288                 return;
289         }
290
291         while (node != NULL) {
292                 struct memcache_element *e = memcache_node2elem(node);
293                 struct rb_node *next = rb_next(node);
294
295                 memcache_delete_element(cache, e);
296                 node = next;
297         }
298 }