2 Unix SMB/CIFS implementation.
4 Copyright (C) Volker Lendecke 2007
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.
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.
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/>.
22 #include "../lib/util/samba_util.h"
23 #include "../lib/util/debug.h"
24 #include "../lib/util/dlinklist.h"
25 #include "../lib/util/rbtree.h"
28 static struct memcache
*global_cache
;
30 struct memcache_element
{
31 struct rb_node rb_node
;
32 struct memcache_element
*prev
, *next
;
33 size_t keylength
, valuelength
;
34 uint8_t n
; /* This is really an enum, but save memory */
35 char data
[1]; /* placeholder for offsetof */
39 struct memcache_element
*mru
;
45 static void memcache_element_parse(struct memcache_element
*e
,
46 DATA_BLOB
*key
, DATA_BLOB
*value
);
48 static bool memcache_is_talloc(enum memcache_number n
)
54 case PDB_GETPWSID_CACHE
:
55 case SINGLETON_CACHE_TALLOC
:
66 static int memcache_destructor(struct memcache
*cache
) {
67 struct memcache_element
*e
, *next
;
69 for (e
= cache
->mru
; e
!= NULL
; e
= next
) {
76 struct memcache
*memcache_init(TALLOC_CTX
*mem_ctx
, size_t max_size
)
78 struct memcache
*result
;
80 result
= talloc_zero(mem_ctx
, struct memcache
);
84 result
->max_size
= max_size
;
85 talloc_set_destructor(result
, memcache_destructor
);
89 void memcache_set_global(struct memcache
*cache
)
91 TALLOC_FREE(global_cache
);
95 static struct memcache_element
*memcache_node2elem(struct rb_node
*node
)
97 return (struct memcache_element
*)
98 ((char *)node
- offsetof(struct memcache_element
, rb_node
));
101 static void memcache_element_parse(struct memcache_element
*e
,
102 DATA_BLOB
*key
, DATA_BLOB
*value
)
104 key
->data
= ((uint8_t *)e
) + offsetof(struct memcache_element
, data
);
105 key
->length
= e
->keylength
;
106 value
->data
= key
->data
+ e
->keylength
;
107 value
->length
= e
->valuelength
;
110 static size_t memcache_element_size(size_t key_length
, size_t value_length
)
112 return sizeof(struct memcache_element
) - 1 + key_length
+ value_length
;
115 static int memcache_compare(struct memcache_element
*e
, enum memcache_number n
,
118 DATA_BLOB this_key
, this_value
;
120 if ((int)e
->n
< (int)n
) return 1;
121 if ((int)e
->n
> (int)n
) return -1;
123 if (e
->keylength
< key
.length
) return 1;
124 if (e
->keylength
> key
.length
) return -1;
126 memcache_element_parse(e
, &this_key
, &this_value
);
127 return memcmp(this_key
.data
, key
.data
, key
.length
);
130 static struct memcache_element
*memcache_find(
131 struct memcache
*cache
, enum memcache_number n
, DATA_BLOB key
)
133 struct rb_node
*node
;
135 node
= cache
->tree
.rb_node
;
137 while (node
!= NULL
) {
138 struct memcache_element
*elem
= memcache_node2elem(node
);
141 cmp
= memcache_compare(elem
, n
, key
);
145 node
= (cmp
< 0) ? node
->rb_left
: node
->rb_right
;
151 bool memcache_lookup(struct memcache
*cache
, enum memcache_number n
,
152 DATA_BLOB key
, DATA_BLOB
*value
)
154 struct memcache_element
*e
;
157 cache
= global_cache
;
163 e
= memcache_find(cache
, n
, key
);
168 if (cache
->size
!= 0) {
169 DLIST_PROMOTE(cache
->mru
, e
);
172 memcache_element_parse(e
, &key
, value
);
176 void *memcache_lookup_talloc(struct memcache
*cache
, enum memcache_number n
,
182 if (!memcache_lookup(cache
, n
, key
, &value
)) {
186 if (value
.length
!= sizeof(result
)) {
190 memcpy(&result
, value
.data
, sizeof(result
));
195 static void memcache_delete_element(struct memcache
*cache
,
196 struct memcache_element
*e
)
198 rb_erase(&e
->rb_node
, &cache
->tree
);
200 DLIST_REMOVE(cache
->mru
, e
);
202 if (memcache_is_talloc(e
->n
)) {
203 DATA_BLOB cache_key
, cache_value
;
206 memcache_element_parse(e
, &cache_key
, &cache_value
);
207 SMB_ASSERT(cache_value
.length
== sizeof(ptr
));
208 memcpy(&ptr
, cache_value
.data
, sizeof(ptr
));
212 cache
->size
-= memcache_element_size(e
->keylength
, e
->valuelength
);
217 static void memcache_trim(struct memcache
*cache
)
219 if (cache
->max_size
== 0) {
223 while ((cache
->size
> cache
->max_size
) && DLIST_TAIL(cache
->mru
)) {
224 memcache_delete_element(cache
, DLIST_TAIL(cache
->mru
));
228 void memcache_delete(struct memcache
*cache
, enum memcache_number n
,
231 struct memcache_element
*e
;
234 cache
= global_cache
;
240 e
= memcache_find(cache
, n
, key
);
245 memcache_delete_element(cache
, e
);
248 void memcache_add(struct memcache
*cache
, enum memcache_number n
,
249 DATA_BLOB key
, DATA_BLOB value
)
251 struct memcache_element
*e
;
253 struct rb_node
*parent
;
254 DATA_BLOB cache_key
, cache_value
;
258 cache
= global_cache
;
264 if (key
.length
== 0) {
268 e
= memcache_find(cache
, n
, key
);
271 memcache_element_parse(e
, &cache_key
, &cache_value
);
273 if (value
.length
<= cache_value
.length
) {
274 if (memcache_is_talloc(e
->n
)) {
276 SMB_ASSERT(cache_value
.length
== sizeof(ptr
));
277 memcpy(&ptr
, cache_value
.data
, sizeof(ptr
));
281 * We can reuse the existing record
283 memcpy(cache_value
.data
, value
.data
, value
.length
);
284 e
->valuelength
= value
.length
;
288 memcache_delete_element(cache
, e
);
291 element_size
= memcache_element_size(key
.length
, value
.length
);
293 e
= talloc_size(cache
, element_size
);
295 DEBUG(0, ("talloc failed\n"));
298 talloc_set_type(e
, struct memcache_element
);
301 e
->keylength
= key
.length
;
302 e
->valuelength
= value
.length
;
304 memcache_element_parse(e
, &cache_key
, &cache_value
);
305 memcpy(cache_key
.data
, key
.data
, key
.length
);
306 memcpy(cache_value
.data
, value
.data
, value
.length
);
309 p
= &cache
->tree
.rb_node
;
312 struct memcache_element
*elem
= memcache_node2elem(*p
);
317 cmp
= memcache_compare(elem
, n
, key
);
319 p
= (cmp
< 0) ? &(*p
)->rb_left
: &(*p
)->rb_right
;
322 rb_link_node(&e
->rb_node
, parent
, p
);
323 rb_insert_color(&e
->rb_node
, &cache
->tree
);
325 DLIST_ADD(cache
->mru
, e
);
327 cache
->size
+= element_size
;
328 memcache_trim(cache
);
331 void memcache_add_talloc(struct memcache
*cache
, enum memcache_number n
,
332 DATA_BLOB key
, void *pptr
)
334 void **ptr
= (void **)pptr
;
338 cache
= global_cache
;
344 p
= talloc_move(cache
, ptr
);
345 memcache_add(cache
, n
, key
, data_blob_const(&p
, sizeof(p
)));
348 void memcache_flush(struct memcache
*cache
, enum memcache_number n
)
350 struct rb_node
*node
;
353 cache
= global_cache
;
360 * Find the smallest element of number n
363 node
= cache
->tree
.rb_node
;
369 * First, find *any* element of number n
373 struct memcache_element
*elem
= memcache_node2elem(node
);
374 struct rb_node
*next
;
376 if ((int)elem
->n
== (int)n
) {
380 if ((int)elem
->n
< (int)n
) {
381 next
= node
->rb_right
;
384 next
= node
->rb_left
;
393 * Then, find the leftmost element with number n
397 struct rb_node
*prev
= rb_prev(node
);
398 struct memcache_element
*elem
;
403 elem
= memcache_node2elem(prev
);
404 if ((int)elem
->n
!= (int)n
) {
410 while (node
!= NULL
) {
411 struct memcache_element
*e
= memcache_node2elem(node
);
412 struct rb_node
*next
= rb_next(node
);
418 memcache_delete_element(cache
, e
);