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/debug.h"
23 #include "../lib/util/samba_util.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
:
56 case SHARE_MODE_LOCK_CACHE
:
58 case VIRUSFILTER_SCAN_RESULTS_CACHE_TALLOC
:
69 static int memcache_destructor(struct memcache
*cache
) {
70 struct memcache_element
*e
, *next
;
72 for (e
= cache
->mru
; e
!= NULL
; e
= next
) {
79 struct memcache
*memcache_init(TALLOC_CTX
*mem_ctx
, size_t max_size
)
81 struct memcache
*result
;
83 result
= talloc_zero(mem_ctx
, struct memcache
);
87 result
->max_size
= max_size
;
88 talloc_set_destructor(result
, memcache_destructor
);
92 void memcache_set_global(struct memcache
*cache
)
94 TALLOC_FREE(global_cache
);
98 static struct memcache_element
*memcache_node2elem(struct rb_node
*node
)
100 return (struct memcache_element
*)
101 ((char *)node
- offsetof(struct memcache_element
, rb_node
));
104 static void memcache_element_parse(struct memcache_element
*e
,
105 DATA_BLOB
*key
, DATA_BLOB
*value
)
107 key
->data
= ((uint8_t *)e
) + offsetof(struct memcache_element
, data
);
108 key
->length
= e
->keylength
;
109 value
->data
= key
->data
+ e
->keylength
;
110 value
->length
= e
->valuelength
;
113 static size_t memcache_element_size(size_t key_length
, size_t value_length
)
115 return sizeof(struct memcache_element
) - 1 + key_length
+ value_length
;
118 static int memcache_compare(struct memcache_element
*e
, enum memcache_number n
,
121 DATA_BLOB this_key
, this_value
;
123 if ((int)e
->n
< (int)n
) return 1;
124 if ((int)e
->n
> (int)n
) return -1;
126 if (e
->keylength
< key
.length
) return 1;
127 if (e
->keylength
> key
.length
) return -1;
129 memcache_element_parse(e
, &this_key
, &this_value
);
130 return memcmp(this_key
.data
, key
.data
, key
.length
);
133 static struct memcache_element
*memcache_find(
134 struct memcache
*cache
, enum memcache_number n
, DATA_BLOB key
)
136 struct rb_node
*node
;
138 node
= cache
->tree
.rb_node
;
140 while (node
!= NULL
) {
141 struct memcache_element
*elem
= memcache_node2elem(node
);
144 cmp
= memcache_compare(elem
, n
, key
);
148 node
= (cmp
< 0) ? node
->rb_left
: node
->rb_right
;
154 bool memcache_lookup(struct memcache
*cache
, enum memcache_number n
,
155 DATA_BLOB key
, DATA_BLOB
*value
)
157 struct memcache_element
*e
;
160 cache
= global_cache
;
166 e
= memcache_find(cache
, n
, key
);
171 if (cache
->size
!= 0) {
172 DLIST_PROMOTE(cache
->mru
, e
);
175 memcache_element_parse(e
, &key
, value
);
179 void *memcache_lookup_talloc(struct memcache
*cache
, enum memcache_number n
,
185 if (!memcache_lookup(cache
, n
, key
, &value
)) {
189 if (value
.length
!= sizeof(result
)) {
193 memcpy(&result
, value
.data
, sizeof(result
));
198 static void memcache_delete_element(struct memcache
*cache
,
199 struct memcache_element
*e
)
201 rb_erase(&e
->rb_node
, &cache
->tree
);
203 DLIST_REMOVE(cache
->mru
, e
);
205 if (memcache_is_talloc(e
->n
)) {
206 DATA_BLOB cache_key
, cache_value
;
209 memcache_element_parse(e
, &cache_key
, &cache_value
);
210 SMB_ASSERT(cache_value
.length
== sizeof(ptr
));
211 memcpy(&ptr
, cache_value
.data
, sizeof(ptr
));
215 cache
->size
-= memcache_element_size(e
->keylength
, e
->valuelength
);
220 static void memcache_trim(struct memcache
*cache
)
222 if (cache
->max_size
== 0) {
226 while ((cache
->size
> cache
->max_size
) && DLIST_TAIL(cache
->mru
)) {
227 memcache_delete_element(cache
, DLIST_TAIL(cache
->mru
));
231 void memcache_delete(struct memcache
*cache
, enum memcache_number n
,
234 struct memcache_element
*e
;
237 cache
= global_cache
;
243 e
= memcache_find(cache
, n
, key
);
248 memcache_delete_element(cache
, e
);
251 void memcache_add(struct memcache
*cache
, enum memcache_number n
,
252 DATA_BLOB key
, DATA_BLOB value
)
254 struct memcache_element
*e
;
256 struct rb_node
*parent
;
257 DATA_BLOB cache_key
, cache_value
;
261 cache
= global_cache
;
267 if (key
.length
== 0) {
271 e
= memcache_find(cache
, n
, key
);
274 memcache_element_parse(e
, &cache_key
, &cache_value
);
276 if (value
.length
<= cache_value
.length
) {
277 if (memcache_is_talloc(e
->n
)) {
279 SMB_ASSERT(cache_value
.length
== sizeof(ptr
));
280 memcpy(&ptr
, cache_value
.data
, sizeof(ptr
));
284 * We can reuse the existing record
286 memcpy(cache_value
.data
, value
.data
, value
.length
);
287 e
->valuelength
= value
.length
;
291 memcache_delete_element(cache
, e
);
294 element_size
= memcache_element_size(key
.length
, value
.length
);
296 e
= talloc_size(cache
, element_size
);
298 DEBUG(0, ("talloc failed\n"));
301 talloc_set_type(e
, struct memcache_element
);
304 e
->keylength
= key
.length
;
305 e
->valuelength
= value
.length
;
307 memcache_element_parse(e
, &cache_key
, &cache_value
);
308 memcpy(cache_key
.data
, key
.data
, key
.length
);
309 memcpy(cache_value
.data
, value
.data
, value
.length
);
312 p
= &cache
->tree
.rb_node
;
315 struct memcache_element
*elem
= memcache_node2elem(*p
);
320 cmp
= memcache_compare(elem
, n
, key
);
322 p
= (cmp
< 0) ? &(*p
)->rb_left
: &(*p
)->rb_right
;
325 rb_link_node(&e
->rb_node
, parent
, p
);
326 rb_insert_color(&e
->rb_node
, &cache
->tree
);
328 DLIST_ADD(cache
->mru
, e
);
330 cache
->size
+= element_size
;
331 memcache_trim(cache
);
334 void memcache_add_talloc(struct memcache
*cache
, enum memcache_number n
,
335 DATA_BLOB key
, void *pptr
)
337 void **ptr
= (void **)pptr
;
341 cache
= global_cache
;
347 p
= talloc_move(cache
, ptr
);
348 memcache_add(cache
, n
, key
, data_blob_const(&p
, sizeof(p
)));
351 void memcache_flush(struct memcache
*cache
, enum memcache_number n
)
353 struct rb_node
*node
;
356 cache
= global_cache
;
363 * Find the smallest element of number n
366 node
= cache
->tree
.rb_node
;
372 * First, find *any* element of number n
376 struct memcache_element
*elem
= memcache_node2elem(node
);
377 struct rb_node
*next
;
379 if ((int)elem
->n
== (int)n
) {
383 if ((int)elem
->n
< (int)n
) {
384 next
= node
->rb_right
;
387 next
= node
->rb_left
;
396 * Then, find the leftmost element with number n
400 struct rb_node
*prev
= rb_prev(node
);
401 struct memcache_element
*elem
;
406 elem
= memcache_node2elem(prev
);
407 if ((int)elem
->n
!= (int)n
) {
413 while (node
!= NULL
) {
414 struct memcache_element
*e
= memcache_node2elem(node
);
415 struct rb_node
*next
= rb_next(node
);
421 memcache_delete_element(cache
, e
);