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