lib/util/memcache.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 "replace.h"
  21 #include <talloc.h>
  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"
  26 #include "memcache.h"
  27
  28 static struct memcache *global_cache;
  29
  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 */
  36 };
  37
  38 struct memcache {
  39         struct memcache_element *mru;
  40         struct rb_root tree;
  41         size_t size;
  42         size_t max_size;
  43 };
  44
  45 static void memcache_element_parse(struct memcache_element *e,
  46                                    DATA_BLOB *key, DATA_BLOB *value);
  47
  48 static bool memcache_is_talloc(enum memcache_number n)
  49 {
  50         bool result;
  51
  52         switch (n) {
  53         case GETPWNAM_CACHE:
  54         case PDB_GETPWSID_CACHE:
  55         case SINGLETON_CACHE_TALLOC:
  56         case SHARE_MODE_LOCK_CACHE:
  57                 result = true;
  58                 break;
  59         default:
  60                 result = false;
  61                 break;
  62         }
  63
  64         return result;
  65 }
  66
  67 static int memcache_destructor(struct memcache *cache) {
  68         struct memcache_element *e, *next;
  69
  70         for (e = cache->mru; e != NULL; e = next) {
  71                 next = e->next;
  72                 TALLOC_FREE(e);
  73         }
  74         return 0;
  75 }
  76
  77 struct memcache *memcache_init(TALLOC_CTX *mem_ctx, size_t max_size)
  78 {
  79         struct memcache *result;
  80
  81         result = talloc_zero(mem_ctx, struct memcache);
  82         if (result == NULL) {
  83                 return NULL;
  84         }
  85         result->max_size = max_size;
  86         talloc_set_destructor(result, memcache_destructor);
  87         return result;
  88 }
  89
  90 void memcache_set_global(struct memcache *cache)
  91 {
  92         TALLOC_FREE(global_cache);
  93         global_cache = cache;
  94 }
  95
  96 static struct memcache_element *memcache_node2elem(struct rb_node *node)
  97 {
  98         return (struct memcache_element *)
  99                 ((char *)node - offsetof(struct memcache_element, rb_node));
 100 }
 101
 102 static void memcache_element_parse(struct memcache_element *e,
 103                                    DATA_BLOB *key, DATA_BLOB *value)
 104 {
 105         key->data = ((uint8_t *)e) + offsetof(struct memcache_element, data);
 106         key->length = e->keylength;
 107         value->data = key->data + e->keylength;
 108         value->length = e->valuelength;
 109 }
 110
 111 static size_t memcache_element_size(size_t key_length, size_t value_length)
 112 {
 113         return sizeof(struct memcache_element) - 1 + key_length + value_length;
 114 }
 115
 116 static int memcache_compare(struct memcache_element *e, enum memcache_number n,
 117                             DATA_BLOB key)
 118 {
 119         DATA_BLOB this_key, this_value;
 120
 121         if ((int)e->n < (int)n) return 1;
 122         if ((int)e->n > (int)n) return -1;
 123
 124         if (e->keylength < key.length) return 1;
 125         if (e->keylength > key.length) return -1;
 126
 127         memcache_element_parse(e, &this_key, &this_value);
 128         return memcmp(this_key.data, key.data, key.length);
 129 }
 130
 131 static struct memcache_element *memcache_find(
 132         struct memcache *cache, enum memcache_number n, DATA_BLOB key)
 133 {
 134         struct rb_node *node;
 135
 136         node = cache->tree.rb_node;
 137
 138         while (node != NULL) {
 139                 struct memcache_element *elem = memcache_node2elem(node);
 140                 int cmp;
 141
 142                 cmp = memcache_compare(elem, n, key);
 143                 if (cmp == 0) {
 144                         return elem;
 145                 }
 146                 node = (cmp < 0) ? node->rb_left : node->rb_right;
 147         }
 148
 149         return NULL;
 150 }
 151
 152 bool memcache_lookup(struct memcache *cache, enum memcache_number n,
 153                      DATA_BLOB key, DATA_BLOB *value)
 154 {
 155         struct memcache_element *e;
 156
 157         if (cache == NULL) {
 158                 cache = global_cache;
 159         }
 160         if (cache == NULL) {
 161                 return false;
 162         }
 163
 164         e = memcache_find(cache, n, key);
 165         if (e == NULL) {
 166                 return false;
 167         }
 168
 169         if (cache->size != 0) {
 170                 DLIST_PROMOTE(cache->mru, e);
 171         }
 172
 173         memcache_element_parse(e, &key, value);
 174         return true;
 175 }
 176
 177 void *memcache_lookup_talloc(struct memcache *cache, enum memcache_number n,
 178                              DATA_BLOB key)
 179 {
 180         DATA_BLOB value;
 181         void *result;
 182
 183         if (!memcache_lookup(cache, n, key, &value)) {
 184                 return NULL;
 185         }
 186
 187         if (value.length != sizeof(result)) {
 188                 return NULL;
 189         }
 190
 191         memcpy(&result, value.data, sizeof(result));
 192
 193         return result;
 194 }
 195
 196 static void memcache_delete_element(struct memcache *cache,
 197                                     struct memcache_element *e)
 198 {
 199         rb_erase(&e->rb_node, &cache->tree);
 200
 201         DLIST_REMOVE(cache->mru, e);
 202
 203         if (memcache_is_talloc(e->n)) {
 204                 DATA_BLOB cache_key, cache_value;
 205                 void *ptr;
 206
 207                 memcache_element_parse(e, &cache_key, &cache_value);
 208                 SMB_ASSERT(cache_value.length == sizeof(ptr));
 209                 memcpy(&ptr, cache_value.data, sizeof(ptr));
 210                 TALLOC_FREE(ptr);
 211         }
 212
 213         cache->size -= memcache_element_size(e->keylength, e->valuelength);
 214
 215         TALLOC_FREE(e);
 216 }
 217
 218 static void memcache_trim(struct memcache *cache)
 219 {
 220         if (cache->max_size == 0) {
 221                 return;
 222         }
 223
 224         while ((cache->size > cache->max_size) && DLIST_TAIL(cache->mru)) {
 225                 memcache_delete_element(cache, DLIST_TAIL(cache->mru));
 226         }
 227 }
 228
 229 void memcache_delete(struct memcache *cache, enum memcache_number n,
 230                      DATA_BLOB key)
 231 {
 232         struct memcache_element *e;
 233
 234         if (cache == NULL) {
 235                 cache = global_cache;
 236         }
 237         if (cache == NULL) {
 238                 return;
 239         }
 240
 241         e = memcache_find(cache, n, key);
 242         if (e == NULL) {
 243                 return;
 244         }
 245
 246         memcache_delete_element(cache, e);
 247 }
 248
 249 void memcache_add(struct memcache *cache, enum memcache_number n,
 250                   DATA_BLOB key, DATA_BLOB value)
 251 {
 252         struct memcache_element *e;
 253         struct rb_node **p;
 254         struct rb_node *parent;
 255         DATA_BLOB cache_key, cache_value;
 256         size_t element_size;
 257
 258         if (cache == NULL) {
 259                 cache = global_cache;
 260         }
 261         if (cache == NULL) {
 262                 return;
 263         }
 264
 265         if (key.length == 0) {
 266                 return;
 267         }
 268
 269         e = memcache_find(cache, n, key);
 270
 271         if (e != NULL) {
 272                 memcache_element_parse(e, &cache_key, &cache_value);
 273
 274                 if (value.length <= cache_value.length) {
 275                         if (memcache_is_talloc(e->n)) {
 276                                 void *ptr;
 277                                 SMB_ASSERT(cache_value.length == sizeof(ptr));
 278                                 memcpy(&ptr, cache_value.data, sizeof(ptr));
 279                                 TALLOC_FREE(ptr);
 280                         }
 281                         /*
 282                          * We can reuse the existing record
 283                          */
 284                         memcpy(cache_value.data, value.data, value.length);
 285                         e->valuelength = value.length;
 286                         return;
 287                 }
 288
 289                 memcache_delete_element(cache, e);
 290         }
 291
 292         element_size = memcache_element_size(key.length, value.length);
 293
 294         e = talloc_size(cache, element_size);
 295         if (e == NULL) {
 296                 DEBUG(0, ("talloc failed\n"));
 297                 return;
 298         }
 299         talloc_set_type(e, struct memcache_element);
 300
 301         e->n = n;
 302         e->keylength = key.length;
 303         e->valuelength = value.length;
 304
 305         memcache_element_parse(e, &cache_key, &cache_value);
 306         memcpy(cache_key.data, key.data, key.length);
 307         memcpy(cache_value.data, value.data, value.length);
 308
 309         parent = NULL;
 310         p = &cache->tree.rb_node;
 311
 312         while (*p) {
 313                 struct memcache_element *elem = memcache_node2elem(*p);
 314                 int cmp;
 315
 316                 parent = (*p);
 317
 318                 cmp = memcache_compare(elem, n, key);
 319
 320                 p = (cmp < 0) ? &(*p)->rb_left : &(*p)->rb_right;
 321         }
 322
 323         rb_link_node(&e->rb_node, parent, p);
 324         rb_insert_color(&e->rb_node, &cache->tree);
 325
 326         DLIST_ADD(cache->mru, e);
 327
 328         cache->size += element_size;
 329         memcache_trim(cache);
 330 }
 331
 332 void memcache_add_talloc(struct memcache *cache, enum memcache_number n,
 333                          DATA_BLOB key, void *pptr)
 334 {
 335         void **ptr = (void **)pptr;
 336         void *p;
 337
 338         if (cache == NULL) {
 339                 cache = global_cache;
 340         }
 341         if (cache == NULL) {
 342                 return;
 343         }
 344
 345         p = talloc_move(cache, ptr);
 346         memcache_add(cache, n, key, data_blob_const(&p, sizeof(p)));
 347 }
 348
 349 void memcache_flush(struct memcache *cache, enum memcache_number n)
 350 {
 351         struct rb_node *node;
 352
 353         if (cache == NULL) {
 354                 cache = global_cache;
 355         }
 356         if (cache == NULL) {
 357                 return;
 358         }
 359
 360         /*
 361          * Find the smallest element of number n
 362          */
 363
 364         node = cache->tree.rb_node;
 365         if (node == NULL) {
 366                 return;
 367         }
 368
 369         /*
 370          * First, find *any* element of number n
 371          */
 372
 373         while (true) {
 374                 struct memcache_element *elem = memcache_node2elem(node);
 375                 struct rb_node *next;
 376
 377                 if ((int)elem->n == (int)n) {
 378                         break;
 379                 }
 380
 381                 if ((int)elem->n < (int)n) {
 382                         next = node->rb_right;
 383                 }
 384                 else {
 385                         next = node->rb_left;
 386                 }
 387                 if (next == NULL) {
 388                         break;
 389                 }
 390                 node = next;
 391         }
 392
 393         /*
 394          * Then, find the leftmost element with number n
 395          */
 396
 397         while (true) {
 398                 struct rb_node *prev = rb_prev(node);
 399                 struct memcache_element *elem;
 400
 401                 if (prev == NULL) {
 402                         break;
 403                 }
 404                 elem = memcache_node2elem(prev);
 405                 if ((int)elem->n != (int)n) {
 406                         break;
 407                 }
 408                 node = prev;
 409         }
 410
 411         while (node != NULL) {
 412                 struct memcache_element *e = memcache_node2elem(node);
 413                 struct rb_node *next = rb_next(node);
 414
 415                 if (e->n != n) {
 416                         break;
 417                 }
 418
 419                 memcache_delete_element(cache, e);
 420                 node = next;
 421         }
 422 }