contrib/subversion/subversion/libsvn_subr/cache-inprocess.c

   1 /*
   2  * cache-inprocess.c: in-memory caching for Subversion
   3  *
   4  * ====================================================================
   5  *    Licensed to the Apache Software Foundation (ASF) under one
   6  *    or more contributor license agreements.  See the NOTICE file
   7  *    distributed with this work for additional information
   8  *    regarding copyright ownership.  The ASF licenses this file
   9  *    to you under the Apache License, Version 2.0 (the
  10  *    "License"); you may not use this file except in compliance
  11  *    with the License.  You may obtain a copy of the License at
  12  *
  13  *      http://www.apache.org/licenses/LICENSE-2.0
  14  *
  15  *    Unless required by applicable law or agreed to in writing,
  16  *    software distributed under the License is distributed on an
  17  *    "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
  18  *    KIND, either express or implied.  See the License for the
  19  *    specific language governing permissions and limitations
  20  *    under the License.
  21  * ====================================================================
  22  */
  23
  24 #include <assert.h>
  25
  26 #include <apr_thread_mutex.h>
  27
  28 #include "svn_pools.h"
  29
  30 #include "svn_private_config.h"
  31
  32 #include "cache.h"
  33 #include "private/svn_mutex.h"
  34
  35 /* The (internal) cache object. */
  36 typedef struct inprocess_cache_t {
  37   /* A user-defined identifier for this cache instance. */
  38   const char *id;
  39
  40   /* HASH maps a key (of size KLEN) to a struct cache_entry. */
  41   apr_hash_t *hash;
  42   apr_ssize_t klen;
  43
  44   /* Used to copy values into the cache. */
  45   svn_cache__serialize_func_t serialize_func;
  46
  47   /* Used to copy values out of the cache. */
  48   svn_cache__deserialize_func_t deserialize_func;
  49
  50   /* Maximum number of pages that this cache instance may allocate */
  51   apr_uint64_t total_pages;
  52   /* The number of pages we're allowed to allocate before having to
  53    * try to reuse one. */
  54   apr_uint64_t unallocated_pages;
  55   /* Number of cache entries stored on each page.  Must be at least 1. */
  56   apr_uint64_t items_per_page;
  57
  58   /* A dummy cache_page serving as the head of a circular doubly
  59    * linked list of cache_pages.  SENTINEL->NEXT is the most recently
  60    * used page, and SENTINEL->PREV is the least recently used page.
  61    * All pages in this list are "full"; the page currently being
  62    * filled (PARTIAL_PAGE) is not in the list. */
  63   struct cache_page *sentinel;
  64
  65   /* A page currently being filled with entries, or NULL if there's no
  66    * partially-filled page.  This page is not in SENTINEL's list. */
  67   struct cache_page *partial_page;
  68   /* If PARTIAL_PAGE is not null, this is the number of entries
  69    * currently on PARTIAL_PAGE. */
  70   apr_uint64_t partial_page_number_filled;
  71
  72   /* The pool that the svn_cache__t itself, HASH, and all pages are
  73    * allocated in; subpools of this pool are used for the cache_entry
  74    * structs, as well as the dup'd values and hash keys.
  75    */
  76   apr_pool_t *cache_pool;
  77
  78   /* Sum of the SIZE members of all cache_entry elements that are
  79    * accessible from HASH. This is used to make statistics available
  80    * even if the sub-pools have already been destroyed.
  81    */
  82   apr_size_t data_size;
  83
  84   /* A lock for intra-process synchronization to the cache, or NULL if
  85    * the cache's creator doesn't feel the cache needs to be
  86    * thread-safe. */
  87   svn_mutex__t *mutex;
  88 } inprocess_cache_t;
  89
  90 /* A cache page; all items on the page are allocated from the same
  91  * pool. */
  92 struct cache_page {
  93   /* Pointers for the LRU list anchored at the cache's SENTINEL.
  94    * (NULL for the PARTIAL_PAGE.) */
  95   struct cache_page *prev;
  96   struct cache_page *next;
  97
  98   /* The pool in which cache_entry structs, hash keys, and dup'd
  99    * values are allocated.  The CACHE_PAGE structs are allocated
 100    * in CACHE_POOL and have the same lifetime as the cache itself.
 101    * (The cache will never allocate more than TOTAL_PAGES page
 102    * structs (inclusive of the sentinel) from CACHE_POOL.)
 103    */
 104   apr_pool_t *page_pool;
 105
 106   /* A singly linked list of the entries on this page; used to remove
 107    * them from the cache's HASH before reusing the page. */
 108   struct cache_entry *first_entry;
 109 };
 110
 111 /* An cache entry. */
 112 struct cache_entry {
 113   const void *key;
 114
 115   /* serialized value */
 116   void *value;
 117
 118   /* length of the serialized value in bytes */
 119   apr_size_t size;
 120
 121   /* The page it's on (needed so that the LRU list can be
 122    * maintained). */
 123   struct cache_page *page;
 124
 125   /* Next entry on the page. */
 126   struct cache_entry *next_entry;
 127 };
 128
 129
 130 /* Removes PAGE from the doubly-linked list it is in (leaving its PREV
 131  * and NEXT fields undefined). */
 132 static void
 133 remove_page_from_list(struct cache_page *page)
 134 {
 135   page->prev->next = page->next;
 136   page->next->prev = page->prev;
 137 }
 138
 139 /* Inserts PAGE after CACHE's sentinel. */
 140 static void
 141 insert_page(inprocess_cache_t *cache,
 142             struct cache_page *page)
 143 {
 144   struct cache_page *pred = cache->sentinel;
 145
 146   page->prev = pred;
 147   page->next = pred->next;
 148   page->prev->next = page;
 149   page->next->prev = page;
 150 }
 151
 152 /* If PAGE is in the circularly linked list (eg, its NEXT isn't NULL),
 153  * move it to the front of the list. */
 154 static svn_error_t *
 155 move_page_to_front(inprocess_cache_t *cache,
 156                    struct cache_page *page)
 157 {
 158   /* This function is called whilst CACHE is locked. */
 159
 160   SVN_ERR_ASSERT(page != cache->sentinel);
 161
 162   if (! page->next)
 163     return SVN_NO_ERROR;
 164
 165   remove_page_from_list(page);
 166   insert_page(cache, page);
 167
 168   return SVN_NO_ERROR;
 169 }
 170
 171 /* Return a copy of KEY inside POOL, using CACHE->KLEN to figure out
 172  * how. */
 173 static const void *
 174 duplicate_key(inprocess_cache_t *cache,
 175               const void *key,
 176               apr_pool_t *pool)
 177 {
 178   if (cache->klen == APR_HASH_KEY_STRING)
 179     return apr_pstrdup(pool, key);
 180   else
 181     return apr_pmemdup(pool, key, cache->klen);
 182 }
 183
 184 static svn_error_t *
 185 inprocess_cache_get_internal(char **buffer,
 186                              apr_size_t *size,
 187                              inprocess_cache_t *cache,
 188                              const void *key,
 189                              apr_pool_t *result_pool)
 190 {
 191   struct cache_entry *entry = apr_hash_get(cache->hash, key, cache->klen);
 192
 193   if (entry)
 194     {
 195       SVN_ERR(move_page_to_front(cache, entry->page));
 196
 197       /* duplicate the buffer entry */
 198       *buffer = apr_palloc(result_pool, entry->size);
 199       if (entry->size)
 200         memcpy(*buffer, entry->value, entry->size);
 201
 202       *size = entry->size;
 203     }
 204   else
 205     {
 206       *buffer = NULL;
 207       *size = 0;
 208     }
 209
 210   return SVN_NO_ERROR;
 211 }
 212
 213 static svn_error_t *
 214 inprocess_cache_get(void **value_p,
 215                     svn_boolean_t *found,
 216                     void *cache_void,
 217                     const void *key,
 218                     apr_pool_t *result_pool)
 219 {
 220   inprocess_cache_t *cache = cache_void;
 221
 222   if (key)
 223     {
 224       char* buffer;
 225       apr_size_t size;
 226
 227       SVN_MUTEX__WITH_LOCK(cache->mutex,
 228                            inprocess_cache_get_internal(&buffer,
 229                                                         &size,
 230                                                         cache,
 231                                                         key,
 232                                                         result_pool));
 233       /* deserialize the buffer content. Usually, this will directly
 234          modify the buffer content directly. */
 235       *found = (buffer != NULL);
 236       if (!buffer || !size)
 237         *value_p = NULL;
 238       else
 239         return cache->deserialize_func(value_p, buffer, size, result_pool);
 240     }
 241   else
 242     {
 243       *value_p = NULL;
 244       *found = FALSE;
 245     }
 246
 247   return SVN_NO_ERROR;
 248 }
 249
 250 static svn_error_t *
 251 inprocess_cache_has_key_internal(svn_boolean_t *found,
 252                                  inprocess_cache_t *cache,
 253                                  const void *key,
 254                                  apr_pool_t *scratch_pool)
 255 {
 256   *found = apr_hash_get(cache->hash, key, cache->klen) != NULL;
 257
 258   return SVN_NO_ERROR;
 259 }
 260
 261 static svn_error_t *
 262 inprocess_cache_has_key(svn_boolean_t *found,
 263                         void *cache_void,
 264                         const void *key,
 265                         apr_pool_t *scratch_pool)
 266 {
 267   inprocess_cache_t *cache = cache_void;
 268
 269   if (key)
 270     SVN_MUTEX__WITH_LOCK(cache->mutex,
 271                          inprocess_cache_has_key_internal(found,
 272                                                           cache,
 273                                                           key,
 274                                                           scratch_pool));
 275   else
 276     *found = FALSE;
 277
 278   return SVN_NO_ERROR;
 279 }
 280
 281 /* Removes PAGE from the LRU list, removes all of its entries from
 282  * CACHE's hash, clears its pool, and sets its entry pointer to NULL.
 283  * Finally, puts it in the "partial page" slot in the cache and sets
 284  * partial_page_number_filled to 0.  Must be called on a page actually
 285  * in the list. */
 286 static void
 287 erase_page(inprocess_cache_t *cache,
 288            struct cache_page *page)
 289 {
 290   struct cache_entry *e;
 291
 292   remove_page_from_list(page);
 293
 294   for (e = page->first_entry;
 295        e;
 296        e = e->next_entry)
 297     {
 298       cache->data_size -= e->size;
 299       apr_hash_set(cache->hash, e->key, cache->klen, NULL);
 300     }
 301
 302   svn_pool_clear(page->page_pool);
 303
 304   page->first_entry = NULL;
 305   page->prev = NULL;
 306   page->next = NULL;
 307
 308   cache->partial_page = page;
 309   cache->partial_page_number_filled = 0;
 310 }
 311
 312
 313 static svn_error_t *
 314 inprocess_cache_set_internal(inprocess_cache_t *cache,
 315                              const void *key,
 316                              void *value,
 317                              apr_pool_t *scratch_pool)
 318 {
 319   struct cache_entry *existing_entry;
 320
 321   existing_entry = apr_hash_get(cache->hash, key, cache->klen);
 322
 323   /* Is it already here, but we can do the one-item-per-page
 324    * optimization? */
 325   if (existing_entry && cache->items_per_page == 1)
 326     {
 327       /* Special case!  ENTRY is the *only* entry on this page, so
 328        * why not wipe it (so as not to leak the previous value).
 329        */
 330       struct cache_page *page = existing_entry->page;
 331
 332       /* This can't be the partial page: items_per_page == 1
 333        * *never* has a partial page (except for in the temporary state
 334        * that we're about to fake). */
 335       SVN_ERR_ASSERT(page->next != NULL);
 336       SVN_ERR_ASSERT(cache->partial_page == NULL);
 337
 338       erase_page(cache, page);
 339       existing_entry = NULL;
 340     }
 341
 342   /* Is it already here, and we just have to leak the old value? */
 343   if (existing_entry)
 344     {
 345       struct cache_page *page = existing_entry->page;
 346
 347       SVN_ERR(move_page_to_front(cache, page));
 348       cache->data_size -= existing_entry->size;
 349       if (value)
 350         {
 351           SVN_ERR(cache->serialize_func(&existing_entry->value,
 352                                         &existing_entry->size,
 353                                         value,
 354                                         page->page_pool));
 355           cache->data_size += existing_entry->size;
 356           if (existing_entry->size == 0)
 357             existing_entry->value = NULL;
 358         }
 359       else
 360         {
 361           existing_entry->value = NULL;
 362           existing_entry->size = 0;
 363         }
 364
 365       return SVN_NO_ERROR;
 366     }
 367
 368   /* Do we not have a partial page to put it on, but we are allowed to
 369    * allocate more? */
 370   if (cache->partial_page == NULL && cache->unallocated_pages > 0)
 371     {
 372       cache->partial_page = apr_pcalloc(cache->cache_pool,
 373                                         sizeof(*(cache->partial_page)));
 374       cache->partial_page->page_pool = svn_pool_create(cache->cache_pool);
 375       cache->partial_page_number_filled = 0;
 376       (cache->unallocated_pages)--;
 377     }
 378
 379   /* Do we really not have a partial page to put it on, even after the
 380    * one-item-per-page optimization and checking the unallocated page
 381    * count? */
 382   if (cache->partial_page == NULL)
 383     {
 384       struct cache_page *oldest_page = cache->sentinel->prev;
 385
 386       SVN_ERR_ASSERT(oldest_page != cache->sentinel);
 387
 388       /* Erase the page and put it in cache->partial_page. */
 389       erase_page(cache, oldest_page);
 390     }
 391
 392   SVN_ERR_ASSERT(cache->partial_page != NULL);
 393
 394   {
 395     struct cache_page *page = cache->partial_page;
 396     struct cache_entry *new_entry = apr_pcalloc(page->page_pool,
 397                                                 sizeof(*new_entry));
 398
 399     /* Copy the key and value into the page's pool.  */
 400     new_entry->key = duplicate_key(cache, key, page->page_pool);
 401     if (value)
 402       {
 403         SVN_ERR(cache->serialize_func(&new_entry->value,
 404                                       &new_entry->size,
 405                                       value,
 406                                       page->page_pool));
 407         cache->data_size += new_entry->size;
 408         if (new_entry->size == 0)
 409           new_entry->value = NULL;
 410       }
 411     else
 412       {
 413         new_entry->value = NULL;
 414         new_entry->size = 0;
 415       }
 416
 417     /* Add the entry to the page's list. */
 418     new_entry->page = page;
 419     new_entry->next_entry = page->first_entry;
 420     page->first_entry = new_entry;
 421
 422     /* Add the entry to the hash, using the *entry's* copy of the
 423      * key. */
 424     apr_hash_set(cache->hash, new_entry->key, cache->klen, new_entry);
 425
 426     /* We've added something else to the partial page. */
 427     (cache->partial_page_number_filled)++;
 428
 429     /* Is it full? */
 430     if (cache->partial_page_number_filled >= cache->items_per_page)
 431       {
 432         insert_page(cache, page);
 433         cache->partial_page = NULL;
 434       }
 435   }
 436
 437   return SVN_NO_ERROR;
 438 }
 439
 440 static svn_error_t *
 441 inprocess_cache_set(void *cache_void,
 442                     const void *key,
 443                     void *value,
 444                     apr_pool_t *scratch_pool)
 445 {
 446   inprocess_cache_t *cache = cache_void;
 447
 448   if (key)
 449     SVN_MUTEX__WITH_LOCK(cache->mutex,
 450                          inprocess_cache_set_internal(cache,
 451                                                       key,
 452                                                       value,
 453                                                       scratch_pool));
 454
 455   return SVN_NO_ERROR;
 456 }
 457
 458 /* Baton type for svn_cache__iter. */
 459 struct cache_iter_baton {
 460   svn_iter_apr_hash_cb_t user_cb;
 461   void *user_baton;
 462 };
 463
 464 /* Call the user's callback with the actual value, not the
 465    cache_entry.  Implements the svn_iter_apr_hash_cb_t
 466    prototype. */
 467 static svn_error_t *
 468 iter_cb(void *baton,
 469         const void *key,
 470         apr_ssize_t klen,
 471         void *val,
 472         apr_pool_t *pool)
 473 {
 474   struct cache_iter_baton *b = baton;
 475   struct cache_entry *entry = val;
 476   return (b->user_cb)(b->user_baton, key, klen, entry->value, pool);
 477 }
 478
 479 static svn_error_t *
 480 inprocess_cache_iter(svn_boolean_t *completed,
 481                      void *cache_void,
 482                      svn_iter_apr_hash_cb_t user_cb,
 483                      void *user_baton,
 484                      apr_pool_t *scratch_pool)
 485 {
 486   inprocess_cache_t *cache = cache_void;
 487   struct cache_iter_baton b;
 488   b.user_cb = user_cb;
 489   b.user_baton = user_baton;
 490
 491   SVN_MUTEX__WITH_LOCK(cache->mutex,
 492                        svn_iter_apr_hash(completed, cache->hash,
 493                                          iter_cb, &b, scratch_pool));
 494
 495   return SVN_NO_ERROR;
 496 }
 497
 498 static svn_error_t *
 499 inprocess_cache_get_partial_internal(void **value_p,
 500                                      svn_boolean_t *found,
 501                                      inprocess_cache_t *cache,
 502                                      const void *key,
 503                                      svn_cache__partial_getter_func_t func,
 504                                      void *baton,
 505                                      apr_pool_t *result_pool)
 506 {
 507   struct cache_entry *entry = apr_hash_get(cache->hash, key, cache->klen);
 508   if (! entry)
 509     {
 510       *found = FALSE;
 511       return SVN_NO_ERROR;
 512     }
 513
 514   SVN_ERR(move_page_to_front(cache, entry->page));
 515
 516   *found = TRUE;
 517   return func(value_p, entry->value, entry->size, baton, result_pool);
 518 }
 519
 520 static svn_error_t *
 521 inprocess_cache_get_partial(void **value_p,
 522                             svn_boolean_t *found,
 523                             void *cache_void,
 524                             const void *key,
 525                             svn_cache__partial_getter_func_t func,
 526                             void *baton,
 527                             apr_pool_t *result_pool)
 528 {
 529   inprocess_cache_t *cache = cache_void;
 530
 531   if (key)
 532     SVN_MUTEX__WITH_LOCK(cache->mutex,
 533                          inprocess_cache_get_partial_internal(value_p,
 534                                                               found,
 535                                                               cache,
 536                                                               key,
 537                                                               func,
 538                                                               baton,
 539                                                               result_pool));
 540   else
 541     *found = FALSE;
 542
 543   return SVN_NO_ERROR;
 544 }
 545
 546 static svn_error_t *
 547 inprocess_cache_set_partial_internal(inprocess_cache_t *cache,
 548                                      const void *key,
 549                                      svn_cache__partial_setter_func_t func,
 550                                      void *baton,
 551                                      apr_pool_t *scratch_pool)
 552 {
 553   struct cache_entry *entry = apr_hash_get(cache->hash, key, cache->klen);
 554   if (entry)
 555     {
 556       SVN_ERR(move_page_to_front(cache, entry->page));
 557
 558       cache->data_size -= entry->size;
 559       SVN_ERR(func(&entry->value,
 560                    &entry->size,
 561                    baton,
 562                    entry->page->page_pool));
 563       cache->data_size += entry->size;
 564     }
 565
 566   return SVN_NO_ERROR;
 567 }
 568
 569 static svn_error_t *
 570 inprocess_cache_set_partial(void *cache_void,
 571                             const void *key,
 572                             svn_cache__partial_setter_func_t func,
 573                             void *baton,
 574                             apr_pool_t *scratch_pool)
 575 {
 576   inprocess_cache_t *cache = cache_void;
 577
 578   if (key)
 579     SVN_MUTEX__WITH_LOCK(cache->mutex,
 580                          inprocess_cache_set_partial_internal(cache,
 581                                                               key,
 582                                                               func,
 583                                                               baton,
 584                                                               scratch_pool));
 585
 586   return SVN_NO_ERROR;
 587 }
 588
 589 static svn_boolean_t
 590 inprocess_cache_is_cachable(void *cache_void, apr_size_t size)
 591 {
 592   /* Be relatively strict: per page we should not allocate more than
 593    * we could spare as "unused" memory.
 594    * But in most cases, nobody will ask anyway. And in no case, this
 595    * will be used for checks _inside_ the cache code.
 596    */
 597   inprocess_cache_t *cache = cache_void;
 598   return size < SVN_ALLOCATOR_RECOMMENDED_MAX_FREE / cache->items_per_page;
 599 }
 600
 601 static svn_error_t *
 602 inprocess_cache_get_info_internal(inprocess_cache_t *cache,
 603                                   svn_cache__info_t *info,
 604                                   apr_pool_t *result_pool)
 605 {
 606   info->id = apr_pstrdup(result_pool, cache->id);
 607
 608   info->used_entries = apr_hash_count(cache->hash);
 609   info->total_entries = cache->items_per_page * cache->total_pages;
 610
 611   info->used_size = cache->data_size;
 612   info->data_size = cache->data_size;
 613   info->total_size = cache->data_size
 614                    + cache->items_per_page * sizeof(struct cache_page)
 615                    + info->used_entries * sizeof(struct cache_entry);
 616
 617   return SVN_NO_ERROR;
 618 }
 619
 620
 621 static svn_error_t *
 622 inprocess_cache_get_info(void *cache_void,
 623                          svn_cache__info_t *info,
 624                          svn_boolean_t reset,
 625                          apr_pool_t *result_pool)
 626 {
 627   inprocess_cache_t *cache = cache_void;
 628
 629   SVN_MUTEX__WITH_LOCK(cache->mutex,
 630                        inprocess_cache_get_info_internal(cache,
 631                                                          info,
 632                                                          result_pool));
 633
 634   return SVN_NO_ERROR;
 635 }
 636
 637 static svn_cache__vtable_t inprocess_cache_vtable = {
 638   inprocess_cache_get,
 639   inprocess_cache_has_key,
 640   inprocess_cache_set,
 641   inprocess_cache_iter,
 642   inprocess_cache_is_cachable,
 643   inprocess_cache_get_partial,
 644   inprocess_cache_set_partial,
 645   inprocess_cache_get_info
 646 };
 647
 648 svn_error_t *
 649 svn_cache__create_inprocess(svn_cache__t **cache_p,
 650                             svn_cache__serialize_func_t serialize,
 651                             svn_cache__deserialize_func_t deserialize,
 652                             apr_ssize_t klen,
 653                             apr_int64_t pages,
 654                             apr_int64_t items_per_page,
 655                             svn_boolean_t thread_safe,
 656                             const char *id,
 657                             apr_pool_t *pool)
 658 {
 659   svn_cache__t *wrapper = apr_pcalloc(pool, sizeof(*wrapper));
 660   inprocess_cache_t *cache = apr_pcalloc(pool, sizeof(*cache));
 661
 662   cache->id = apr_pstrdup(pool, id);
 663
 664   SVN_ERR_ASSERT(klen == APR_HASH_KEY_STRING || klen >= 1);
 665
 666   cache->hash = apr_hash_make(pool);
 667   cache->klen = klen;
 668
 669   cache->serialize_func = serialize;
 670   cache->deserialize_func = deserialize;
 671
 672   SVN_ERR_ASSERT(pages >= 1);
 673   cache->total_pages = pages;
 674   cache->unallocated_pages = pages;
 675   SVN_ERR_ASSERT(items_per_page >= 1);
 676   cache->items_per_page = items_per_page;
 677
 678   cache->sentinel = apr_pcalloc(pool, sizeof(*(cache->sentinel)));
 679   cache->sentinel->prev = cache->sentinel;
 680   cache->sentinel->next = cache->sentinel;
 681   /* The sentinel doesn't need a pool.  (We're happy to crash if we
 682    * accidentally try to treat it like a real page.) */
 683
 684   SVN_ERR(svn_mutex__init(&cache->mutex, thread_safe, pool));
 685
 686   cache->cache_pool = pool;
 687
 688   wrapper->vtable = &inprocess_cache_vtable;
 689   wrapper->cache_internal = cache;
 690   wrapper->pretend_empty = !!getenv("SVN_X_DOES_NOT_MARK_THE_SPOT");
 691
 692   *cache_p = wrapper;
 693   return SVN_NO_ERROR;
 694 }