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