From 712a28aaae6671be673f9b125cae59aec628d267 Mon Sep 17 00:00:00 2001 From: Volker Lendecke Date: Wed, 19 Dec 2007 15:45:22 +0100 Subject: Rename cache.[ch] to memcache.[ch] cache.h conflicts with an XFS DMAPI include on "opi" :-( (This used to be commit b8db804e07cc19d406ba3892d6eecbe16132a89a) --- source3/lib/memcache.c | 298 +++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 298 insertions(+) create mode 100644 source3/lib/memcache.c (limited to 'source3/lib/memcache.c') diff --git a/source3/lib/memcache.c b/source3/lib/memcache.c new file mode 100644 index 0000000000..17630066ae --- /dev/null +++ b/source3/lib/memcache.c @@ -0,0 +1,298 @@ +/* + Unix SMB/CIFS implementation. + In-memory cache + Copyright (C) Volker Lendecke 2007 + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see . +*/ + +#include "memcache.h" +#include "rbtree.h" + +struct memcache_element { + struct rb_node rb_node; + struct memcache_element *prev, *next; + size_t keylength, valuelength; + uint8 n; /* This is really an enum, but save memory */ + char data[1]; /* placeholder for offsetof */ +}; + +struct memcache { + struct memcache_element *mru, *lru; + struct rb_root tree; + size_t size; + size_t max_size; +}; + +static int memcache_destructor(struct memcache *cache) { + struct memcache_element *e, *next; + + for (e = cache->mru; e != NULL; e = next) { + next = e->next; + SAFE_FREE(e); + } + return 0; +} + +struct memcache *memcache_init(TALLOC_CTX *mem_ctx, size_t max_size) +{ + struct memcache *result; + + result = TALLOC_ZERO_P(mem_ctx, struct memcache); + if (result == NULL) { + return NULL; + } + result->max_size = max_size; + talloc_set_destructor(result, memcache_destructor); + return result; +} + +static struct memcache_element *memcache_node2elem(struct rb_node *node) +{ + return (struct memcache_element *) + ((char *)node - offsetof(struct memcache_element, rb_node)); +} + +static void memcache_element_parse(struct memcache_element *e, + DATA_BLOB *key, DATA_BLOB *value) +{ + key->data = ((uint8 *)e) + offsetof(struct memcache_element, data); + key->length = e->keylength; + value->data = key->data + e->keylength; + value->length = e->valuelength; +} + +static size_t memcache_element_size(size_t key_length, size_t value_length) +{ + return sizeof(struct memcache_element) - 1 + key_length + value_length; +} + +static int memcache_compare(struct memcache_element *e, enum memcache_number n, + DATA_BLOB key) +{ + DATA_BLOB this_key, this_value; + + if ((int)e->n < (int)n) return -1; + if ((int)e->n > (int)n) return 1; + + if (e->keylength < key.length) return -1; + if (e->keylength > key.length) return 1; + + memcache_element_parse(e, &this_key, &this_value); + return memcmp(this_key.data, key.data, key.length); +} + +static struct memcache_element *memcache_find( + struct memcache *cache, enum memcache_number n, DATA_BLOB key) +{ + struct rb_node *node; + + node = cache->tree.rb_node; + + while (node != NULL) { + struct memcache_element *elem = memcache_node2elem(node); + int cmp; + + cmp = memcache_compare(elem, n, key); + if (cmp == 0) { + return elem; + } + node = (cmp < 0) ? node->rb_left : node->rb_right; + } + + return NULL; +} + +bool memcache_lookup(struct memcache *cache, enum memcache_number n, + DATA_BLOB key, DATA_BLOB *value) +{ + struct memcache_element *e; + + e = memcache_find(cache, n, key); + if (e == NULL) { + return false; + } + + if (cache->size != 0) { + /* + * Do LRU promotion only when we will ever shrink + */ + if (e == cache->lru) { + cache->lru = e->prev; + } + DLIST_PROMOTE(cache->mru, e); + if (cache->mru == NULL) { + cache->mru = e; + } + } + + memcache_element_parse(e, &key, value); + return true; +} + +static void memcache_delete_element(struct memcache *cache, + struct memcache_element *e) +{ + rb_erase(&e->rb_node, &cache->tree); + + if (e == cache->lru) { + cache->lru = e->prev; + } + DLIST_REMOVE(cache->mru, e); + + cache->size -= memcache_element_size(e->keylength, e->valuelength); + + SAFE_FREE(e); +} + +static void memcache_trim(struct memcache *cache) +{ + if (cache->max_size == 0) { + return; + } + + while ((cache->size > cache->max_size) && (cache->lru != NULL)) { + memcache_delete_element(cache, cache->lru); + } +} + +void memcache_delete(struct memcache *cache, enum memcache_number n, + DATA_BLOB key) +{ + struct memcache_element *e; + + e = memcache_find(cache, n, key); + if (e == NULL) { + return; + } + + memcache_delete_element(cache, e); +} + +void memcache_add(struct memcache *cache, enum memcache_number n, + DATA_BLOB key, DATA_BLOB value) +{ + struct memcache_element *e; + struct rb_node **p; + struct rb_node *parent; + DATA_BLOB cache_key, cache_value; + size_t element_size; + + if (key.length == 0) { + return; + } + + e = memcache_find(cache, n, key); + + if (e != NULL) { + memcache_element_parse(e, &cache_key, &cache_value); + + if (value.length <= cache_value.length) { + /* + * We can reuse the existing record + */ + memcpy(cache_value.data, value.data, value.length); + e->valuelength = value.length; + return; + } + + memcache_delete_element(cache, e); + } + + element_size = memcache_element_size(key.length, value.length); + + + e = (struct memcache_element *)SMB_MALLOC(element_size); + + if (e == NULL) { + DEBUG(0, ("malloc failed\n")); + return; + } + + e->n = n; + e->keylength = key.length; + e->valuelength = value.length; + + memcache_element_parse(e, &cache_key, &cache_value); + memcpy(cache_key.data, key.data, key.length); + memcpy(cache_value.data, value.data, value.length); + + parent = NULL; + p = &cache->tree.rb_node; + + while (*p) { + struct memcache_element *elem = memcache_node2elem(*p); + int cmp; + + parent = (*p); + + cmp = memcache_compare(elem, n, key); + + p = (cmp < 0) ? &(*p)->rb_left : &(*p)->rb_right; + } + + rb_link_node(&e->rb_node, parent, p); + rb_insert_color(&e->rb_node, &cache->tree); + + DLIST_ADD(cache->mru, e); + if (cache->lru == NULL) { + cache->lru = e; + } + + cache->size += element_size; + memcache_trim(cache); +} + +void memcache_flush(struct memcache *cache, enum memcache_number n) +{ + struct rb_node *node; + + /* + * Find the smallest element of number n + */ + + node = cache->tree.rb_node; + if (node == NULL) { + return; + } + + while (true) { + struct memcache_element *elem = memcache_node2elem(node); + struct rb_node *next; + + if ((int)elem->n < (int)n) { + next = node->rb_right; + } + else { + next = node->rb_left; + } + if (next == NULL) { + break; + } + node = next; + } + + node = rb_next(node); + if (node == NULL) { + return; + } + + while (node != NULL) { + struct memcache_element *e = memcache_node2elem(node); + struct rb_node *next = rb_next(node); + + memcache_delete_element(cache, e); + node = next; + } +} -- cgit From cc48010f41684b5ef8c2e8a5511528cc426d300f Mon Sep 17 00:00:00 2001 From: Volker Lendecke Date: Thu, 20 Dec 2007 10:55:45 +0100 Subject: Add a global cache It hurts, but I think this global variable is necessary for transition, and it has the potential to remove quite a few other global variables without messing with APIs too much. (This used to be commit c131d0dc52ec09c9227eff3d68877369c37aaed5) --- source3/lib/memcache.c | 36 ++++++++++++++++++++++++++++++++++++ 1 file changed, 36 insertions(+) (limited to 'source3/lib/memcache.c') diff --git a/source3/lib/memcache.c b/source3/lib/memcache.c index 17630066ae..38bbd66085 100644 --- a/source3/lib/memcache.c +++ b/source3/lib/memcache.c @@ -20,6 +20,8 @@ #include "memcache.h" #include "rbtree.h" +static struct memcache *global_cache; + struct memcache_element { struct rb_node rb_node; struct memcache_element *prev, *next; @@ -58,6 +60,12 @@ struct memcache *memcache_init(TALLOC_CTX *mem_ctx, size_t max_size) return result; } +void memcache_set_global(struct memcache *cache) +{ + TALLOC_FREE(global_cache); + global_cache = cache; +} + static struct memcache_element *memcache_node2elem(struct rb_node *node) { return (struct memcache_element *) @@ -119,6 +127,13 @@ bool memcache_lookup(struct memcache *cache, enum memcache_number n, { struct memcache_element *e; + if (cache == NULL) { + cache = global_cache; + } + if (cache == NULL) { + return false; + } + e = memcache_find(cache, n, key); if (e == NULL) { return false; @@ -172,6 +187,13 @@ void memcache_delete(struct memcache *cache, enum memcache_number n, { struct memcache_element *e; + if (cache == NULL) { + cache = global_cache; + } + if (cache == NULL) { + return; + } + e = memcache_find(cache, n, key); if (e == NULL) { return; @@ -189,6 +211,13 @@ void memcache_add(struct memcache *cache, enum memcache_number n, DATA_BLOB cache_key, cache_value; size_t element_size; + if (cache == NULL) { + cache = global_cache; + } + if (cache == NULL) { + return; + } + if (key.length == 0) { return; } @@ -258,6 +287,13 @@ void memcache_flush(struct memcache *cache, enum memcache_number n) { struct rb_node *node; + if (cache == NULL) { + cache = global_cache; + } + if (cache == NULL) { + return; + } + /* * Find the smallest element of number n */ -- cgit From d3d870cc07447cf08a776c714a39f40f9c72da2c Mon Sep 17 00:00:00 2001 From: Volker Lendecke Date: Thu, 20 Dec 2007 14:41:58 +0100 Subject: Add memcache_add_talloc The first memcache API only had blobs, but we have quite a few objects that are more complex talloc'ed structues. The current one I'm looking at is the getpwnam cache, but there are others around. (This used to be commit ea0e5ad9a15c848904dee8cb2d3e392b6a894705) --- source3/lib/memcache.c | 52 ++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 52 insertions(+) (limited to 'source3/lib/memcache.c') diff --git a/source3/lib/memcache.c b/source3/lib/memcache.c index 38bbd66085..192a822cde 100644 --- a/source3/lib/memcache.c +++ b/source3/lib/memcache.c @@ -37,11 +37,38 @@ struct memcache { size_t max_size; }; +static void memcache_element_parse(struct memcache_element *e, + DATA_BLOB *key, DATA_BLOB *value); + +static bool memcache_is_talloc(enum memcache_number n) +{ + bool result; + + switch (n) { + case GETPWNAM_CACHE: + result = true; + break; + default: + result = false; + break; + } + + return result; +} + static int memcache_destructor(struct memcache *cache) { struct memcache_element *e, *next; for (e = cache->mru; e != NULL; e = next) { next = e->next; + if (memcache_is_talloc(e->n) + && (e->valuelength == sizeof(void *))) { + DATA_BLOB key, value; + void *ptr; + memcache_element_parse(e, &key, &value); + memcpy(&ptr, value.data, sizeof(ptr)); + TALLOC_FREE(ptr); + } SAFE_FREE(e); } return 0; @@ -156,6 +183,25 @@ bool memcache_lookup(struct memcache *cache, enum memcache_number n, return true; } +void *memcache_lookup_talloc(struct memcache *cache, enum memcache_number n, + DATA_BLOB key) +{ + DATA_BLOB value; + void *result; + + if (!memcache_lookup(cache, n, key, &value)) { + return NULL; + } + + if (value.length != sizeof(result)) { + return NULL; + } + + memcpy(&result, value.data, sizeof(result)); + + return result; +} + static void memcache_delete_element(struct memcache *cache, struct memcache_element *e) { @@ -283,6 +329,12 @@ void memcache_add(struct memcache *cache, enum memcache_number n, memcache_trim(cache); } +void memcache_add_talloc(struct memcache *cache, enum memcache_number n, + DATA_BLOB key, void *ptr) +{ + return memcache_add(cache, n, key, data_blob_const(&ptr, sizeof(ptr))); +} + void memcache_flush(struct memcache *cache, enum memcache_number n) { struct rb_node *node; -- cgit From addf598cde41d17ad4cf497a64b9a2b27e4028c5 Mon Sep 17 00:00:00 2001 From: Volker Lendecke Date: Thu, 20 Dec 2007 22:17:16 +0100 Subject: Some C++ warnings (This used to be commit 5ab82d4f574f2a2e2761e9e414c66a70aeffb05d) --- source3/lib/memcache.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'source3/lib/memcache.c') diff --git a/source3/lib/memcache.c b/source3/lib/memcache.c index 192a822cde..448b8b2f84 100644 --- a/source3/lib/memcache.c +++ b/source3/lib/memcache.c @@ -61,7 +61,7 @@ static int memcache_destructor(struct memcache *cache) { for (e = cache->mru; e != NULL; e = next) { next = e->next; - if (memcache_is_talloc(e->n) + if (memcache_is_talloc((enum memcache_number)e->n) && (e->valuelength == sizeof(void *))) { DATA_BLOB key, value; void *ptr; -- cgit From 4418b989e7009c63d2206cecdfaa50cc66e1d8da Mon Sep 17 00:00:00 2001 From: Volker Lendecke Date: Fri, 21 Dec 2007 12:53:12 +0100 Subject: Fix the build on Solaris (This used to be commit 5f5e52ba7b3862dc72a16d84e07503e98ccbbf8a) --- source3/lib/memcache.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'source3/lib/memcache.c') diff --git a/source3/lib/memcache.c b/source3/lib/memcache.c index 448b8b2f84..457586bd68 100644 --- a/source3/lib/memcache.c +++ b/source3/lib/memcache.c @@ -332,7 +332,7 @@ void memcache_add(struct memcache *cache, enum memcache_number n, void memcache_add_talloc(struct memcache *cache, enum memcache_number n, DATA_BLOB key, void *ptr) { - return memcache_add(cache, n, key, data_blob_const(&ptr, sizeof(ptr))); + memcache_add(cache, n, key, data_blob_const(&ptr, sizeof(ptr))); } void memcache_flush(struct memcache *cache, enum memcache_number n) -- cgit From 3c99b7773ef62d13a7e3611be0603a5807315d9d Mon Sep 17 00:00:00 2001 From: Volker Lendecke Date: Fri, 28 Dec 2007 13:13:29 +0100 Subject: Convert csamuser to memcache (This used to be commit 476d3abf9c6142d99822212141fc3d843aca4798) --- source3/lib/memcache.c | 1 + 1 file changed, 1 insertion(+) (limited to 'source3/lib/memcache.c') diff --git a/source3/lib/memcache.c b/source3/lib/memcache.c index 457586bd68..c06e7ceacc 100644 --- a/source3/lib/memcache.c +++ b/source3/lib/memcache.c @@ -46,6 +46,7 @@ static bool memcache_is_talloc(enum memcache_number n) switch (n) { case GETPWNAM_CACHE: + case PDB_GETPWSID_CACHE: result = true; break; default: -- cgit From 245537f9bd1bddc496da0155012c34a2c7a18668 Mon Sep 17 00:00:00 2001 From: Volker Lendecke Date: Fri, 28 Dec 2007 17:24:39 +0100 Subject: Convert get_root_nt_token to memcache (This used to be commit fada689893314bed2fc78588b3fd9b144f4c808a) --- source3/lib/memcache.c | 1 + 1 file changed, 1 insertion(+) (limited to 'source3/lib/memcache.c') diff --git a/source3/lib/memcache.c b/source3/lib/memcache.c index c06e7ceacc..6dee61af50 100644 --- a/source3/lib/memcache.c +++ b/source3/lib/memcache.c @@ -47,6 +47,7 @@ static bool memcache_is_talloc(enum memcache_number n) switch (n) { case GETPWNAM_CACHE: case PDB_GETPWSID_CACHE: + case SINGLETON_CACHE_TALLOC: result = true; break; default: -- cgit From e84026a29b795ab5fc73c81d7790ec83aad83987 Mon Sep 17 00:00:00 2001 From: Volker Lendecke Date: Tue, 20 May 2008 18:35:23 +0200 Subject: Fix memcache_flush() I have no idea what I've been smoking when I checked this in :-( Karolin, this fixes the join bug 3.0.28->3.2.0rc1 Thanks, Volker (This used to be commit f845dbbceeff032cd248117ddf63af3d3736b21c) --- source3/lib/memcache.c | 39 ++++++++++++++++++++++++++++++++++----- 1 file changed, 34 insertions(+), 5 deletions(-) (limited to 'source3/lib/memcache.c') diff --git a/source3/lib/memcache.c b/source3/lib/memcache.c index 6dee61af50..e1426bc811 100644 --- a/source3/lib/memcache.c +++ b/source3/lib/memcache.c @@ -120,11 +120,11 @@ static int memcache_compare(struct memcache_element *e, enum memcache_number n, { DATA_BLOB this_key, this_value; - if ((int)e->n < (int)n) return -1; - if ((int)e->n > (int)n) return 1; + if ((int)e->n < (int)n) return 1; + if ((int)e->n > (int)n) return -1; - if (e->keylength < key.length) return -1; - if (e->keylength > key.length) return 1; + if (e->keylength < key.length) return 1; + if (e->keylength > key.length) return -1; memcache_element_parse(e, &this_key, &this_value); return memcmp(this_key.data, key.data, key.length); @@ -357,10 +357,18 @@ void memcache_flush(struct memcache *cache, enum memcache_number n) return; } + /* + * First, find *any* element of number n + */ + while (true) { struct memcache_element *elem = memcache_node2elem(node); struct rb_node *next; + if ((int)elem->n == (int)n) { + break; + } + if ((int)elem->n < (int)n) { next = node->rb_right; } @@ -373,15 +381,36 @@ void memcache_flush(struct memcache *cache, enum memcache_number n) node = next; } - node = rb_next(node); if (node == NULL) { return; } + /* + * Then, find the leftmost element with number n + */ + + while (true) { + struct rb_node *prev = rb_prev(node); + struct memcache_element *elem; + + if (prev == NULL) { + break; + } + elem = memcache_node2elem(prev); + if ((int)elem->n != (int)n) { + break; + } + node = prev; + } + while (node != NULL) { struct memcache_element *e = memcache_node2elem(node); struct rb_node *next = rb_next(node); + if (e->n != n) { + break; + } + memcache_delete_element(cache, e); node = next; } -- cgit