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, struct memcache_element *e)
 227 {
 228         struct memcache_element *tail = NULL;
 229
 230         if (cache->max_size == 0) {
 231                 return;
 232         }
 233
 234         for (tail = DLIST_TAIL(cache->mru);
 235              (cache->size > cache->max_size) && (tail != NULL);
 236              tail = DLIST_TAIL(cache->mru))
 237         {
 238                 if (tail == e) {
 239                         tail = DLIST_PREV(tail);
 240                         if (tail == NULL) {
 241                                 break;
 242                         }
 243                 }
 244                 memcache_delete_element(cache, tail);
 245         }
 246 }
 247
 248 void memcache_delete(struct memcache *cache, enum memcache_number n,
 249                      DATA_BLOB key)
 250 {
 251         struct memcache_element *e;
 252
 253         if (cache == NULL) {
 254                 cache = global_cache;
 255         }
 256         if (cache == NULL) {
 257                 return;
 258         }
 259
 260         e = memcache_find(cache, n, key);
 261         if (e == NULL) {
 262                 return;
 263         }
 264
 265         memcache_delete_element(cache, e);
 266 }
 267
 268 void memcache_add(struct memcache *cache, enum memcache_number n,
 269                   DATA_BLOB key, DATA_BLOB value)
 270 {
 271         struct memcache_element *e;
 272         struct rb_node **p;
 273         struct rb_node *parent;
 274         DATA_BLOB cache_key, cache_value;
 275         size_t element_size;
 276
 277         if (cache == NULL) {
 278                 cache = global_cache;
 279         }
 280         if (cache == NULL) {
 281                 return;
 282         }
 283
 284         if (key.length == 0) {
 285                 return;
 286         }
 287
 288         e = memcache_find(cache, n, key);
 289
 290         if (e != NULL) {
 291                 memcache_element_parse(e, &cache_key, &cache_value);
 292
 293                 if (value.length <= cache_value.length) {
 294                         if (memcache_is_talloc(e->n)) {
 295                                 struct memcache_talloc_value mtv;
 296
 297                                 SMB_ASSERT(cache_value.length == sizeof(mtv));
 298                                 memcpy(&mtv, cache_value.data, sizeof(mtv));
 299                                 cache->size -= mtv.len;
 300                                 TALLOC_FREE(mtv.ptr);
 301                         }
 302                         /*
 303                          * We can reuse the existing record
 304                          */
 305                         memcpy(cache_value.data, value.data, value.length);
 306                         e->valuelength = value.length;
 307
 308                         if (memcache_is_talloc(e->n)) {
 309                                 struct memcache_talloc_value mtv;
 310
 311                                 SMB_ASSERT(cache_value.length == sizeof(mtv));
 312                                 memcpy(&mtv, cache_value.data, sizeof(mtv));
 313                                 cache->size += mtv.len;
 314                         }
 315                         return;
 316                 }
 317
 318                 memcache_delete_element(cache, e);
 319         }
 320
 321         element_size = memcache_element_size(key.length, value.length);
 322
 323         e = talloc_size(cache, element_size);
 324         if (e == NULL) {
 325                 DEBUG(0, ("talloc failed\n"));
 326                 return;
 327         }
 328         talloc_set_type(e, struct memcache_element);
 329
 330         e->n = n;
 331         e->keylength = key.length;
 332         e->valuelength = value.length;
 333
 334         memcache_element_parse(e, &cache_key, &cache_value);
 335         memcpy(cache_key.data, key.data, key.length);
 336         memcpy(cache_value.data, value.data, value.length);
 337
 338         parent = NULL;
 339         p = &cache->tree.rb_node;
 340
 341         while (*p) {
 342                 struct memcache_element *elem = memcache_node2elem(*p);
 343                 int cmp;
 344
 345                 parent = (*p);
 346
 347                 cmp = memcache_compare(elem, n, key);
 348
 349                 p = (cmp < 0) ? &(*p)->rb_left : &(*p)->rb_right;
 350         }
 351
 352         rb_link_node(&e->rb_node, parent, p);
 353         rb_insert_color(&e->rb_node, &cache->tree);
 354
 355         DLIST_ADD(cache->mru, e);
 356
 357         cache->size += element_size;
 358         if (memcache_is_talloc(e->n)) {
 359                 struct memcache_talloc_value mtv;
 360
 361                 SMB_ASSERT(cache_value.length == sizeof(mtv));
 362                 memcpy(&mtv, cache_value.data, sizeof(mtv));
 363                 cache->size += mtv.len;
 364         }
 365         memcache_trim(cache, e);
 366 }
 367
 368 void memcache_add_talloc(struct memcache *cache, enum memcache_number n,
 369                          DATA_BLOB key, void *pptr)
 370 {
 371         struct memcache_talloc_value mtv;
 372         void **ptr = (void **)pptr;
 373
 374         if (cache == NULL) {
 375                 cache = global_cache;
 376         }
 377         if (cache == NULL) {
 378                 return;
 379         }
 380
 381         mtv.len = talloc_total_size(*ptr);
 382         mtv.ptr = talloc_move(cache, ptr);
 383         memcache_add(cache, n, key, data_blob_const(&mtv, sizeof(mtv)));
 384 }
 385
 386 void memcache_flush(struct memcache *cache, enum memcache_number n)
 387 {
 388         struct rb_node *node;
 389
 390         if (cache == NULL) {
 391                 cache = global_cache;
 392         }
 393         if (cache == NULL) {
 394                 return;
 395         }
 396
 397         /*
 398          * Find the smallest element of number n
 399          */
 400
 401         node = cache->tree.rb_node;
 402         if (node == NULL) {
 403                 return;
 404         }
 405
 406         /*
 407          * First, find *any* element of number n
 408          */
 409
 410         while (true) {
 411                 struct memcache_element *elem = memcache_node2elem(node);
 412                 struct rb_node *next;
 413
 414                 if ((int)elem->n == (int)n) {
 415                         break;
 416                 }
 417
 418                 if ((int)elem->n < (int)n) {
 419                         next = node->rb_right;
 420                 }
 421                 else {
 422                         next = node->rb_left;
 423                 }
 424                 if (next == NULL) {
 425                         break;
 426                 }
 427                 node = next;
 428         }
 429
 430         /*
 431          * Then, find the leftmost element with number n
 432          */
 433
 434         while (true) {
 435                 struct rb_node *prev = rb_prev(node);
 436                 struct memcache_element *elem;
 437
 438                 if (prev == NULL) {
 439                         break;
 440                 }
 441                 elem = memcache_node2elem(prev);
 442                 if ((int)elem->n != (int)n) {
 443                         break;
 444                 }
 445                 node = prev;
 446         }
 447
 448         while (node != NULL) {
 449                 struct memcache_element *e = memcache_node2elem(node);
 450                 struct rb_node *next = rb_next(node);
 451
 452                 if (e->n != n) {
 453                         break;
 454                 }
 455
 456                 memcache_delete_element(cache, e);
 457                 node = next;
 458         }
 459 }