cache-membuffer.c revision 289166
1/* 2 * cache-membuffer.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#include <apr_md5.h> 26#include <apr_thread_rwlock.h> 27 28#include "svn_pools.h" 29#include "svn_checksum.h" 30#include "md5.h" 31#include "svn_private_config.h" 32#include "cache.h" 33#include "svn_string.h" 34#include "private/svn_dep_compat.h" 35#include "private/svn_mutex.h" 36#include "private/svn_pseudo_md5.h" 37 38/* 39 * This svn_cache__t implementation actually consists of two parts: 40 * a shared (per-process) singleton membuffer cache instance and shallow 41 * svn_cache__t front-end instances that each use different key spaces. 42 * For data management, they all forward to the singleton membuffer cache. 43 * 44 * A membuffer cache consists of two parts: 45 * 46 * 1. A linear data buffer containing cached items in a serialized 47 * representation. There may be arbitrary gaps between entries. 48 * 2. A directory of cache entries. This is organized similar to CPU 49 * data caches: for every possible key, there is exactly one group 50 * of entries that may contain the header info for an item with 51 * that given key. The result is a GROUP_SIZE-way associative cache. 52 * 53 * Only the start address of these two data parts are given as a native 54 * pointer. All other references are expressed as offsets to these pointers. 55 * With that design, it is relatively easy to share the same data structure 56 * between different processes and / or to persist them on disk. These 57 * out-of-process features have not been implemented, yet. 58 * 59 * The data buffer usage information is implicitly given by the directory 60 * entries. Every USED entry has a reference to the previous and the next 61 * used dictionary entry and this double-linked list is ordered by the 62 * offsets of their item data within the data buffer. So removing data, 63 * for instance, is done simply by unlinking it from the chain, implicitly 64 * marking the entry as well as the data buffer section previously 65 * associated to it as unused. 66 * 67 * Insertion can occur at only one, sliding position. It is marked by its 68 * offset in the data buffer plus the index of the first used entry at or 69 * behind that position. If this gap is too small to accommodate the new 70 * item, the insertion window is extended as described below. The new entry 71 * will always be inserted at the bottom end of the window and since the 72 * next used entry is known, properly sorted insertion is possible. 73 * 74 * To make the cache perform robustly in a wide range of usage scenarios, 75 * a randomized variant of LFU is used (see ensure_data_insertable for 76 * details). Every item holds a read hit counter and there is a global read 77 * hit counter. The more hits an entry has in relation to the average, the 78 * more it is likely to be kept using a rand()-based condition. The test is 79 * applied only to the entry following the insertion window. If it doesn't 80 * get evicted, it is moved to the begin of that window and the window is 81 * moved. 82 * 83 * Moreover, the entry's hits get halved to make that entry more likely to 84 * be removed the next time the sliding insertion / removal window comes by. 85 * As a result, frequently used entries are likely not to be dropped until 86 * they get not used for a while. Also, even a cache thrashing situation 87 * about 50% of the content survives every 50% of the cache being re-written 88 * with new entries. For details on the fine-tuning involved, see the 89 * comments in ensure_data_insertable(). 90 * 91 * To limit the entry size and management overhead, not the actual item keys 92 * but only their MD5 checksums will not be stored. This is reasonably safe 93 * to do since users have only limited control over the full keys, even if 94 * these contain folder paths. So, it is very hard to deliberately construct 95 * colliding keys. Random checksum collisions can be shown to be extremely 96 * unlikely. 97 * 98 * All access to the cached data needs to be serialized. Because we want 99 * to scale well despite that bottleneck, we simply segment the cache into 100 * a number of independent caches (segments). Items will be multiplexed based 101 * on their hash key. 102 */ 103 104/* APR's read-write lock implementation on Windows is horribly inefficient. 105 * Even with very low contention a runtime overhead of 35% percent has been 106 * measured for 'svn-bench null-export' over ra_serf. 107 * 108 * Use a simple mutex on Windows. Because there is one mutex per segment, 109 * large machines should (and usually can) be configured with large caches 110 * such that read contention is kept low. This is basically the situation 111 * we head before 1.8. 112 */ 113#ifdef WIN32 114# define USE_SIMPLE_MUTEX 1 115#else 116# define USE_SIMPLE_MUTEX 0 117#endif 118 119/* A 16-way associative cache seems to be a good compromise between 120 * performance (worst-case lookups) and efficiency-loss due to collisions. 121 * 122 * This value may be changed to any positive integer. 123 */ 124#define GROUP_SIZE 16 125 126/* For more efficient copy operations, let's align all data items properly. 127 * Must be a power of 2. 128 */ 129#define ITEM_ALIGNMENT 16 130 131/* By default, don't create cache segments smaller than this value unless 132 * the total cache size itself is smaller. 133 */ 134#define DEFAULT_MIN_SEGMENT_SIZE APR_UINT64_C(0x2000000) 135 136/* The minimum segment size we will allow for multi-segmented caches 137 */ 138#define MIN_SEGMENT_SIZE APR_UINT64_C(0x10000) 139 140/* The maximum number of segments allowed. Larger numbers reduce the size 141 * of each segment, in turn reducing the max size of a cachable item. 142 * Also, each segment gets its own lock object. The actual number supported 143 * by the OS may therefore be lower and svn_cache__membuffer_cache_create 144 * may return an error. 145 */ 146#define MAX_SEGMENT_COUNT 0x10000 147 148/* As of today, APR won't allocate chunks of 4GB or more. So, limit the 149 * segment size to slightly below that. 150 */ 151#define MAX_SEGMENT_SIZE APR_UINT64_C(0xffff0000) 152 153/* We don't mark the initialization status for every group but initialize 154 * a number of groups at once. That will allow for a very small init flags 155 * vector that is likely to fit into the CPU caches even for fairly large 156 * membuffer caches. For instance, the default of 32 means 8x32 groups per 157 * byte, i.e. 8 flags/byte x 32 groups/flag x 8 entries/group x 40 index 158 * bytes/entry x 8 cache bytes/index byte = 1kB init vector / 640MB cache. 159 */ 160#define GROUP_INIT_GRANULARITY 32 161 162/* Invalid index reference value. Equivalent to APR_UINT32_T(-1) 163 */ 164#define NO_INDEX APR_UINT32_MAX 165 166/* To save space in our group structure, we only use 32 bit size values 167 * and, therefore, limit the size of each entry to just below 4GB. 168 * Supporting larger items is not a good idea as the data transfer 169 * to and from the cache would block other threads for a very long time. 170 */ 171#define MAX_ITEM_SIZE ((apr_uint32_t)(0 - ITEM_ALIGNMENT)) 172 173/* A 16 byte key type. We use that to identify cache entries. 174 * The notation as just two integer values will cause many compilers 175 * to create better code. 176 */ 177typedef apr_uint64_t entry_key_t[2]; 178 179/* Debugging / corruption detection support. 180 * If you define this macro, the getter functions will performed expensive 181 * checks on the item data, requested keys and entry types. If there is 182 * a mismatch found in any of them when being compared with the values 183 * remembered in the setter function, an error will be returned. 184 */ 185#ifdef SVN_DEBUG_CACHE_MEMBUFFER 186 187/* The prefix passed to svn_cache__create_membuffer_cache() effectively 188 * defines the type of all items stored by that cache instance. We'll take 189 * the last 7 bytes + \0 as plaintext for easy identification by the dev. 190 */ 191#define PREFIX_TAIL_LEN 8 192 193/* This record will be attached to any cache entry. It tracks item data 194 * (content), key and type as hash values and is the baseline against which 195 * the getters will compare their results to detect inconsistencies. 196 */ 197typedef struct entry_tag_t 198{ 199 /* MD5 checksum over the serialized the item data. 200 */ 201 unsigned char content_hash [APR_MD5_DIGESTSIZE]; 202 203 /* Hash value of the svn_cache_t instance that wrote the item 204 * (i.e. a combination of type and repository) 205 */ 206 unsigned char prefix_hash [APR_MD5_DIGESTSIZE]; 207 208 /* Note that this only covers the variable part of the key, 209 * i.e. it will be different from the full key hash used for 210 * cache indexing. 211 */ 212 unsigned char key_hash [APR_MD5_DIGESTSIZE]; 213 214 /* Last letters from of the key in human readable format 215 * (ends with the type identifier, e.g. "DAG") 216 */ 217 char prefix_tail[PREFIX_TAIL_LEN]; 218 219 /* Length of the variable key part. 220 */ 221 apr_size_t key_len; 222 223} entry_tag_t; 224 225/* Per svn_cache_t instance initialization helper. 226 */ 227static void get_prefix_tail(const char *prefix, char *prefix_tail) 228{ 229 apr_size_t len = strlen(prefix); 230 apr_size_t to_copy = len > PREFIX_TAIL_LEN-1 ? PREFIX_TAIL_LEN-1 : len; 231 232 memset(prefix_tail, 0, PREFIX_TAIL_LEN); 233 memcpy(prefix_tail, prefix + len - to_copy, to_copy); 234} 235 236/* Initialize all members of TAG except for the content hash. 237 */ 238static svn_error_t *store_key_part(entry_tag_t *tag, 239 entry_key_t prefix_hash, 240 char *prefix_tail, 241 const void *key, 242 apr_size_t key_len, 243 apr_pool_t *pool) 244{ 245 svn_checksum_t *checksum; 246 SVN_ERR(svn_checksum(&checksum, 247 svn_checksum_md5, 248 key, 249 key_len, 250 pool)); 251 252 memcpy(tag->prefix_hash, prefix_hash, sizeof(tag->prefix_hash)); 253 memcpy(tag->key_hash, checksum->digest, sizeof(tag->key_hash)); 254 memcpy(tag->prefix_tail, prefix_tail, sizeof(tag->prefix_tail)); 255 256 tag->key_len = key_len; 257 258 return SVN_NO_ERROR; 259} 260 261/* Initialize the content hash member of TAG. 262 */ 263static svn_error_t* store_content_part(entry_tag_t *tag, 264 const char *data, 265 apr_size_t size, 266 apr_pool_t *pool) 267{ 268 svn_checksum_t *checksum; 269 SVN_ERR(svn_checksum(&checksum, 270 svn_checksum_md5, 271 data, 272 size, 273 pool)); 274 275 memcpy(tag->content_hash, checksum->digest, sizeof(tag->content_hash)); 276 277 return SVN_NO_ERROR; 278} 279 280/* Compare two tags and fail with an assertion upon differences. 281 */ 282static svn_error_t* assert_equal_tags(const entry_tag_t *lhs, 283 const entry_tag_t *rhs) 284{ 285 SVN_ERR_ASSERT(memcmp(lhs->content_hash, rhs->content_hash, 286 sizeof(lhs->content_hash)) == 0); 287 SVN_ERR_ASSERT(memcmp(lhs->prefix_hash, rhs->prefix_hash, 288 sizeof(lhs->prefix_hash)) == 0); 289 SVN_ERR_ASSERT(memcmp(lhs->key_hash, rhs->key_hash, 290 sizeof(lhs->key_hash)) == 0); 291 SVN_ERR_ASSERT(memcmp(lhs->prefix_tail, rhs->prefix_tail, 292 sizeof(lhs->prefix_tail)) == 0); 293 294 SVN_ERR_ASSERT(lhs->key_len == rhs->key_len); 295 296 return SVN_NO_ERROR; 297} 298 299/* Reoccurring code snippets. 300 */ 301 302#define DEBUG_CACHE_MEMBUFFER_TAG_ARG entry_tag_t *tag, 303 304#define DEBUG_CACHE_MEMBUFFER_TAG tag, 305 306#define DEBUG_CACHE_MEMBUFFER_INIT_TAG \ 307 entry_tag_t _tag; \ 308 entry_tag_t *tag = &_tag; \ 309 SVN_ERR(store_key_part(tag, \ 310 cache->prefix, \ 311 cache->prefix_tail, \ 312 key, \ 313 cache->key_len == APR_HASH_KEY_STRING \ 314 ? strlen((const char *) key) \ 315 : cache->key_len, \ 316 cache->pool)); 317 318#else 319 320/* Don't generate any checks if consistency checks have not been enabled. 321 */ 322#define DEBUG_CACHE_MEMBUFFER_TAG_ARG 323#define DEBUG_CACHE_MEMBUFFER_TAG 324#define DEBUG_CACHE_MEMBUFFER_INIT_TAG 325 326#endif /* SVN_DEBUG_CACHE_MEMBUFFER */ 327 328/* A single dictionary entry. Since all entries will be allocated once 329 * during cache creation, those entries might be either used or unused. 330 * An entry is used if and only if it is contained in the doubly-linked 331 * list of used entries. 332 */ 333typedef struct entry_t 334{ 335 /* Identifying the data item. Only valid for used entries. 336 */ 337 entry_key_t key; 338 339 /* The offset of the cached item's serialized data within the data buffer. 340 */ 341 apr_uint64_t offset; 342 343 /* Size of the serialized item data. May be 0. 344 * Only valid for used entries. 345 */ 346 apr_size_t size; 347 348 /* Number of (read) hits for this entry. Will be reset upon write. 349 * Only valid for used entries. 350 */ 351 apr_uint32_t hit_count; 352 353 /* Reference to the next used entry in the order defined by offset. 354 * NO_INDEX indicates the end of the list; this entry must be referenced 355 * by the caches membuffer_cache_t.last member. NO_INDEX also implies 356 * that the data buffer is not used beyond offset+size. 357 * Only valid for used entries. 358 */ 359 apr_uint32_t next; 360 361 /* Reference to the previous used entry in the order defined by offset. 362 * NO_INDEX indicates the end of the list; this entry must be referenced 363 * by the caches membuffer_cache_t.first member. 364 * Only valid for used entries. 365 */ 366 apr_uint32_t previous; 367 368#ifdef SVN_DEBUG_CACHE_MEMBUFFER 369 /* Remember type, content and key hashes. 370 */ 371 entry_tag_t tag; 372#endif 373} entry_t; 374 375/* We group dictionary entries to make this GROUP-SIZE-way associative. 376 */ 377typedef struct entry_group_t 378{ 379 /* number of entries used [0 .. USED-1] */ 380 apr_uint32_t used; 381 382 /* the actual entries */ 383 entry_t entries[GROUP_SIZE]; 384} entry_group_t; 385 386/* The cache header structure. 387 */ 388struct svn_membuffer_t 389{ 390 /* Number of cache segments. Must be a power of 2. 391 Please note that this structure represents only one such segment 392 and that all segments must / will report the same values here. */ 393 apr_uint32_t segment_count; 394 395 /* The dictionary, GROUP_SIZE * group_count entries long. Never NULL. 396 */ 397 entry_group_t *directory; 398 399 /* Flag array with group_count / GROUP_INIT_GRANULARITY _bit_ elements. 400 * Allows for efficiently marking groups as "not initialized". 401 */ 402 unsigned char *group_initialized; 403 404 /* Size of dictionary in groups. Must be > 0. 405 */ 406 apr_uint32_t group_count; 407 408 /* Reference to the first (defined by the order content in the data 409 * buffer) dictionary entry used by any data item. 410 * NO_INDEX for an empty cache. 411 */ 412 apr_uint32_t first; 413 414 /* Reference to the last (defined by the order content in the data 415 * buffer) dictionary entry used by any data item. 416 * NO_INDEX for an empty cache. 417 */ 418 apr_uint32_t last; 419 420 /* Reference to the first (defined by the order content in the data 421 * buffer) used dictionary entry behind the insertion position 422 * (current_data). If NO_INDEX, the data buffer is free starting at the 423 * current_data offset. 424 */ 425 apr_uint32_t next; 426 427 428 /* Pointer to the data buffer, data_size bytes long. Never NULL. 429 */ 430 unsigned char *data; 431 432 /* Size of data buffer in bytes. Must be > 0. 433 */ 434 apr_uint64_t data_size; 435 436 /* Offset in the data buffer where the next insertion shall occur. 437 */ 438 apr_uint64_t current_data; 439 440 /* Total number of data buffer bytes in use. 441 */ 442 apr_uint64_t data_used; 443 444 /* Largest entry size that we would accept. For total cache sizes 445 * less than 4TB (sic!), this is determined by the total cache size. 446 */ 447 apr_uint64_t max_entry_size; 448 449 450 /* Number of used dictionary entries, i.e. number of cached items. 451 * In conjunction with hit_count, this is used calculate the average 452 * hit count as part of the randomized LFU algorithm. 453 */ 454 apr_uint32_t used_entries; 455 456 /* Sum of (read) hit counts of all used dictionary entries. 457 * In conjunction used_entries used_entries, this is used calculate 458 * the average hit count as part of the randomized LFU algorithm. 459 */ 460 apr_uint64_t hit_count; 461 462 463 /* Total number of calls to membuffer_cache_get. 464 * Purely statistical information that may be used for profiling. 465 */ 466 apr_uint64_t total_reads; 467 468 /* Total number of calls to membuffer_cache_set. 469 * Purely statistical information that may be used for profiling. 470 */ 471 apr_uint64_t total_writes; 472 473 /* Total number of hits since the cache's creation. 474 * Purely statistical information that may be used for profiling. 475 */ 476 apr_uint64_t total_hits; 477 478#if APR_HAS_THREADS 479 /* A lock for intra-process synchronization to the cache, or NULL if 480 * the cache's creator doesn't feel the cache needs to be 481 * thread-safe. 482 */ 483# if USE_SIMPLE_MUTEX 484 svn_mutex__t *lock; 485# else 486 apr_thread_rwlock_t *lock; 487# endif 488 489 /* If set, write access will wait until they get exclusive access. 490 * Otherwise, they will become no-ops if the segment is currently 491 * read-locked. Only used when LOCK is an r/w lock. 492 */ 493 svn_boolean_t allow_blocking_writes; 494#endif 495}; 496 497/* Align integer VALUE to the next ITEM_ALIGNMENT boundary. 498 */ 499#define ALIGN_VALUE(value) (((value) + ITEM_ALIGNMENT-1) & -ITEM_ALIGNMENT) 500 501/* Align POINTER value to the next ITEM_ALIGNMENT boundary. 502 */ 503#define ALIGN_POINTER(pointer) ((void*)ALIGN_VALUE((apr_size_t)(char*)(pointer))) 504 505/* If locking is supported for CACHE, acquire a read lock for it. 506 */ 507static svn_error_t * 508read_lock_cache(svn_membuffer_t *cache) 509{ 510#if APR_HAS_THREADS 511# if USE_SIMPLE_MUTEX 512 return svn_mutex__lock(cache->lock); 513# else 514 if (cache->lock) 515 { 516 apr_status_t status = apr_thread_rwlock_rdlock(cache->lock); 517 if (status) 518 return svn_error_wrap_apr(status, _("Can't lock cache mutex")); 519 } 520# endif 521#endif 522 return SVN_NO_ERROR; 523} 524 525/* If locking is supported for CACHE, acquire a write lock for it. 526 */ 527static svn_error_t * 528write_lock_cache(svn_membuffer_t *cache, svn_boolean_t *success) 529{ 530#if APR_HAS_THREADS 531# if USE_SIMPLE_MUTEX 532 533 return svn_mutex__lock(cache->lock); 534 535# else 536 537 if (cache->lock) 538 { 539 apr_status_t status; 540 if (cache->allow_blocking_writes) 541 { 542 status = apr_thread_rwlock_wrlock(cache->lock); 543 } 544 else 545 { 546 status = apr_thread_rwlock_trywrlock(cache->lock); 547 if (SVN_LOCK_IS_BUSY(status)) 548 { 549 *success = FALSE; 550 status = APR_SUCCESS; 551 } 552 } 553 554 if (status) 555 return svn_error_wrap_apr(status, 556 _("Can't write-lock cache mutex")); 557 } 558 559# endif 560#endif 561 return SVN_NO_ERROR; 562} 563 564/* If locking is supported for CACHE, acquire an unconditional write lock 565 * for it. 566 */ 567static svn_error_t * 568force_write_lock_cache(svn_membuffer_t *cache) 569{ 570#if APR_HAS_THREADS 571# if USE_SIMPLE_MUTEX 572 573 return svn_mutex__lock(cache->lock); 574 575# else 576 577 apr_status_t status = apr_thread_rwlock_wrlock(cache->lock); 578 if (status) 579 return svn_error_wrap_apr(status, 580 _("Can't write-lock cache mutex")); 581 582# endif 583#endif 584 return SVN_NO_ERROR; 585} 586 587/* If locking is supported for CACHE, release the current lock 588 * (read or write). 589 */ 590static svn_error_t * 591unlock_cache(svn_membuffer_t *cache, svn_error_t *err) 592{ 593#if APR_HAS_THREADS 594# if USE_SIMPLE_MUTEX 595 596 return svn_mutex__unlock(cache->lock, err); 597 598# else 599 600 if (cache->lock) 601 { 602 apr_status_t status = apr_thread_rwlock_unlock(cache->lock); 603 if (err) 604 return err; 605 606 if (status) 607 return svn_error_wrap_apr(status, _("Can't unlock cache mutex")); 608 } 609 610# endif 611#endif 612 return err; 613} 614 615/* If supported, guard the execution of EXPR with a read lock to cache. 616 * Macro has been modeled after SVN_MUTEX__WITH_LOCK. 617 */ 618#define WITH_READ_LOCK(cache, expr) \ 619do { \ 620 SVN_ERR(read_lock_cache(cache)); \ 621 SVN_ERR(unlock_cache(cache, (expr))); \ 622} while (0) 623 624/* If supported, guard the execution of EXPR with a write lock to cache. 625 * Macro has been modeled after SVN_MUTEX__WITH_LOCK. 626 * 627 * The write lock process is complicated if we don't allow to wait for 628 * the lock: If we didn't get the lock, we may still need to remove an 629 * existing entry for the given key because that content is now stale. 630 * Once we discovered such an entry, we unconditionally do a blocking 631 * wait for the write lock. In case no old content could be found, a 632 * failing lock attempt is simply a no-op and we exit the macro. 633 */ 634#define WITH_WRITE_LOCK(cache, expr) \ 635do { \ 636 svn_boolean_t got_lock = TRUE; \ 637 SVN_ERR(write_lock_cache(cache, &got_lock)); \ 638 if (!got_lock) \ 639 { \ 640 svn_boolean_t exists; \ 641 SVN_ERR(entry_exists(cache, group_index, key, &exists)); \ 642 if (exists) \ 643 SVN_ERR(force_write_lock_cache(cache)); \ 644 else \ 645 break; \ 646 } \ 647 SVN_ERR(unlock_cache(cache, (expr))); \ 648} while (0) 649 650/* Resolve a dictionary entry reference, i.e. return the entry 651 * for the given IDX. 652 */ 653static APR_INLINE entry_t * 654get_entry(svn_membuffer_t *cache, apr_uint32_t idx) 655{ 656 return &cache->directory[idx / GROUP_SIZE].entries[idx % GROUP_SIZE]; 657} 658 659/* Get the entry references for the given ENTRY. 660 */ 661static APR_INLINE apr_uint32_t 662get_index(svn_membuffer_t *cache, entry_t *entry) 663{ 664 apr_size_t group_index 665 = ((char *)entry - (char *)cache->directory) / sizeof(entry_group_t); 666 667 return (apr_uint32_t)group_index * GROUP_SIZE 668 + (apr_uint32_t)(entry - cache->directory[group_index].entries); 669} 670 671/* Remove the used ENTRY from the CACHE, i.e. make it "unused". 672 * In contrast to insertion, removal is possible for any entry. 673 */ 674static void 675drop_entry(svn_membuffer_t *cache, entry_t *entry) 676{ 677 /* the group that ENTRY belongs to plus a number of useful index values 678 */ 679 apr_uint32_t idx = get_index(cache, entry); 680 apr_uint32_t group_index = idx / GROUP_SIZE; 681 entry_group_t *group = &cache->directory[group_index]; 682 apr_uint32_t last_in_group = group_index * GROUP_SIZE + group->used - 1; 683 684 /* Only valid to be called for used entries. 685 */ 686 assert(idx <= last_in_group); 687 688 /* update global cache usage counters 689 */ 690 cache->used_entries--; 691 cache->hit_count -= entry->hit_count; 692 cache->data_used -= entry->size; 693 694 /* extend the insertion window, if the entry happens to border it 695 */ 696 if (idx == cache->next) 697 cache->next = entry->next; 698 else 699 if (entry->next == cache->next) 700 { 701 /* insertion window starts right behind the entry to remove 702 */ 703 if (entry->previous == NO_INDEX) 704 { 705 /* remove the first entry -> insertion may start at pos 0, now */ 706 cache->current_data = 0; 707 } 708 else 709 { 710 /* insertion may start right behind the previous entry */ 711 entry_t *previous = get_entry(cache, entry->previous); 712 cache->current_data = ALIGN_VALUE( previous->offset 713 + previous->size); 714 } 715 } 716 717 /* unlink it from the chain of used entries 718 */ 719 if (entry->previous == NO_INDEX) 720 cache->first = entry->next; 721 else 722 get_entry(cache, entry->previous)->next = entry->next; 723 724 if (entry->next == NO_INDEX) 725 cache->last = entry->previous; 726 else 727 get_entry(cache, entry->next)->previous = entry->previous; 728 729 /* Move last entry into hole (if the removed one is not the last used). 730 * We need to do this since all used entries are at the beginning of 731 * the group's entries array. 732 */ 733 if (idx < last_in_group) 734 { 735 /* copy the last used entry to the removed entry's index 736 */ 737 *entry = group->entries[group->used-1]; 738 739 /* update foreign links to new index 740 */ 741 if (last_in_group == cache->next) 742 cache->next = idx; 743 744 if (entry->previous == NO_INDEX) 745 cache->first = idx; 746 else 747 get_entry(cache, entry->previous)->next = idx; 748 749 if (entry->next == NO_INDEX) 750 cache->last = idx; 751 else 752 get_entry(cache, entry->next)->previous = idx; 753 } 754 755 /* Update the number of used entries. 756 */ 757 group->used--; 758} 759 760/* Insert ENTRY into the chain of used dictionary entries. The entry's 761 * offset and size members must already have been initialized. Also, 762 * the offset must match the beginning of the insertion window. 763 */ 764static void 765insert_entry(svn_membuffer_t *cache, entry_t *entry) 766{ 767 /* the group that ENTRY belongs to plus a number of useful index values 768 */ 769 apr_uint32_t idx = get_index(cache, entry); 770 apr_uint32_t group_index = idx / GROUP_SIZE; 771 entry_group_t *group = &cache->directory[group_index]; 772 entry_t *next = cache->next == NO_INDEX 773 ? NULL 774 : get_entry(cache, cache->next); 775 776 /* The entry must start at the beginning of the insertion window. 777 * It must also be the first unused entry in the group. 778 */ 779 assert(entry->offset == cache->current_data); 780 assert(idx == group_index * GROUP_SIZE + group->used); 781 cache->current_data = ALIGN_VALUE(entry->offset + entry->size); 782 783 /* update usage counters 784 */ 785 cache->used_entries++; 786 cache->data_used += entry->size; 787 entry->hit_count = 0; 788 group->used++; 789 790 /* update entry chain 791 */ 792 entry->next = cache->next; 793 if (cache->first == NO_INDEX) 794 { 795 /* insert as the first entry and only in the chain 796 */ 797 entry->previous = NO_INDEX; 798 cache->last = idx; 799 cache->first = idx; 800 } 801 else if (next == NULL) 802 { 803 /* insert as the last entry in the chain. 804 * Note that it cannot also be at the beginning of the chain. 805 */ 806 entry->previous = cache->last; 807 get_entry(cache, cache->last)->next = idx; 808 cache->last = idx; 809 } 810 else 811 { 812 /* insert either at the start of a non-empty list or 813 * somewhere in the middle 814 */ 815 entry->previous = next->previous; 816 next->previous = idx; 817 818 if (entry->previous != NO_INDEX) 819 get_entry(cache, entry->previous)->next = idx; 820 else 821 cache->first = idx; 822 } 823 824 /* The current insertion position must never point outside our 825 * data buffer. 826 */ 827 assert(cache->current_data <= cache->data_size); 828} 829 830/* Map a KEY of 16 bytes to the CACHE and group that shall contain the 831 * respective item. 832 */ 833static apr_uint32_t 834get_group_index(svn_membuffer_t **cache, 835 entry_key_t key) 836{ 837 svn_membuffer_t *segment0 = *cache; 838 839 /* select the cache segment to use. they have all the same group_count */ 840 *cache = &segment0[key[0] & (segment0->segment_count -1)]; 841 return key[1] % segment0->group_count; 842} 843 844/* Reduce the hit count of ENTRY and update the accumulated hit info 845 * in CACHE accordingly. 846 */ 847static APR_INLINE void 848let_entry_age(svn_membuffer_t *cache, entry_t *entry) 849{ 850 apr_uint32_t hits_removed = (entry->hit_count + 1) >> 1; 851 852 cache->hit_count -= hits_removed; 853 entry->hit_count -= hits_removed; 854} 855 856/* Returns 0 if the entry group identified by GROUP_INDEX in CACHE has not 857 * been initialized, yet. In that case, this group can not data. Otherwise, 858 * a non-zero value is returned. 859 */ 860static APR_INLINE unsigned char 861is_group_initialized(svn_membuffer_t *cache, apr_uint32_t group_index) 862{ 863 unsigned char flags 864 = cache->group_initialized[group_index / (8 * GROUP_INIT_GRANULARITY)]; 865 unsigned char bit_mask 866 = (unsigned char)(1 << ((group_index / GROUP_INIT_GRANULARITY) % 8)); 867 868 return flags & bit_mask; 869} 870 871/* Initializes the section of the directory in CACHE that contains 872 * the entry group identified by GROUP_INDEX. */ 873static void 874initialize_group(svn_membuffer_t *cache, apr_uint32_t group_index) 875{ 876 unsigned char bit_mask; 877 apr_uint32_t i; 878 879 /* range of groups to initialize due to GROUP_INIT_GRANULARITY */ 880 apr_uint32_t first_index = 881 (group_index / GROUP_INIT_GRANULARITY) * GROUP_INIT_GRANULARITY; 882 apr_uint32_t last_index = first_index + GROUP_INIT_GRANULARITY; 883 if (last_index > cache->group_count) 884 last_index = cache->group_count; 885 886 for (i = first_index; i < last_index; ++i) 887 cache->directory[i].used = 0; 888 889 /* set the "initialized" bit for these groups */ 890 bit_mask 891 = (unsigned char)(1 << ((group_index / GROUP_INIT_GRANULARITY) % 8)); 892 cache->group_initialized[group_index / (8 * GROUP_INIT_GRANULARITY)] 893 |= bit_mask; 894} 895 896/* Given the GROUP_INDEX that shall contain an entry with the hash key 897 * TO_FIND, find that entry in the specified group. 898 * 899 * If FIND_EMPTY is not set, this function will return the one used entry 900 * that actually matches the hash or NULL, if no such entry exists. 901 * 902 * If FIND_EMPTY has been set, this function will drop the one used entry 903 * that actually matches the hash (i.e. make it fit to be replaced with 904 * new content), an unused entry or a forcibly removed entry (if all 905 * group entries are currently in use). The entries' hash value will be 906 * initialized with TO_FIND. 907 */ 908static entry_t * 909find_entry(svn_membuffer_t *cache, 910 apr_uint32_t group_index, 911 const apr_uint64_t to_find[2], 912 svn_boolean_t find_empty) 913{ 914 entry_group_t *group; 915 entry_t *entry = NULL; 916 apr_size_t i; 917 918 /* get the group that *must* contain the entry 919 */ 920 group = &cache->directory[group_index]; 921 922 /* If the entry group has not been initialized, yet, there is no data. 923 */ 924 if (! is_group_initialized(cache, group_index)) 925 { 926 if (find_empty) 927 { 928 initialize_group(cache, group_index); 929 entry = &group->entries[0]; 930 931 /* initialize entry for the new key */ 932 entry->key[0] = to_find[0]; 933 entry->key[1] = to_find[1]; 934 } 935 936 return entry; 937 } 938 939 /* try to find the matching entry 940 */ 941 for (i = 0; i < group->used; ++i) 942 if ( to_find[0] == group->entries[i].key[0] 943 && to_find[1] == group->entries[i].key[1]) 944 { 945 /* found it 946 */ 947 entry = &group->entries[i]; 948 if (find_empty) 949 drop_entry(cache, entry); 950 else 951 return entry; 952 } 953 954 /* None found. Are we looking for a free entry? 955 */ 956 if (find_empty) 957 { 958 /* if there is no empty entry, delete the oldest entry 959 */ 960 if (group->used == GROUP_SIZE) 961 { 962 /* every entry gets the same chance of being removed. 963 * Otherwise, we free the first entry, fill it and 964 * remove it again on the next occasion without considering 965 * the other entries in this group. 966 */ 967 entry = &group->entries[rand() % GROUP_SIZE]; 968 for (i = 1; i < GROUP_SIZE; ++i) 969 if (entry->hit_count > group->entries[i].hit_count) 970 entry = &group->entries[i]; 971 972 /* for the entries that don't have been removed, 973 * reduce their hit counts to put them at a relative 974 * disadvantage the next time. 975 */ 976 for (i = 0; i < GROUP_SIZE; ++i) 977 if (entry != &group->entries[i]) 978 let_entry_age(cache, entry); 979 980 drop_entry(cache, entry); 981 } 982 983 /* initialize entry for the new key 984 */ 985 entry = &group->entries[group->used]; 986 entry->key[0] = to_find[0]; 987 entry->key[1] = to_find[1]; 988 } 989 990 return entry; 991} 992 993/* Move a surviving ENTRY from just behind the insertion window to 994 * its beginning and move the insertion window up accordingly. 995 */ 996static void 997move_entry(svn_membuffer_t *cache, entry_t *entry) 998{ 999 apr_size_t size = ALIGN_VALUE(entry->size); 1000 1001 /* This entry survived this cleansing run. Reset half of its 1002 * hit count so that its removal gets more likely in the next 1003 * run unless someone read / hit this entry in the meantime. 1004 */ 1005 let_entry_age(cache, entry); 1006 1007 /* Move the entry to the start of the empty / insertion section 1008 * (if it isn't there already). Size-aligned moves are legal 1009 * since all offsets and block sizes share this same alignment. 1010 * Size-aligned moves tend to be faster than non-aligned ones 1011 * because no "odd" bytes at the end need to special treatment. 1012 */ 1013 if (entry->offset != cache->current_data) 1014 { 1015 memmove(cache->data + cache->current_data, 1016 cache->data + entry->offset, 1017 size); 1018 entry->offset = cache->current_data; 1019 } 1020 1021 /* The insertion position is now directly behind this entry. 1022 */ 1023 cache->current_data = entry->offset + size; 1024 cache->next = entry->next; 1025 1026 /* The current insertion position must never point outside our 1027 * data buffer. 1028 */ 1029 assert(cache->current_data <= cache->data_size); 1030} 1031 1032/* If necessary, enlarge the insertion window until it is at least 1033 * SIZE bytes long. SIZE must not exceed the data buffer size. 1034 * Return TRUE if enough room could be found or made. A FALSE result 1035 * indicates that the respective item shall not be added. 1036 */ 1037static svn_boolean_t 1038ensure_data_insertable(svn_membuffer_t *cache, apr_size_t size) 1039{ 1040 entry_t *entry; 1041 apr_uint64_t average_hit_value; 1042 apr_uint64_t threshold; 1043 1044 /* accumulated size of the entries that have been removed to make 1045 * room for the new one. 1046 */ 1047 apr_size_t drop_size = 0; 1048 1049 /* This loop will eventually terminate because every cache entry 1050 * would get dropped eventually: 1051 * - hit counts become 0 after the got kept for 32 full scans 1052 * - larger elements get dropped as soon as their hit count is 0 1053 * - smaller and smaller elements get removed as the average 1054 * entry size drops (average drops by a factor of 8 per scan) 1055 * - after no more than 43 full scans, all elements would be removed 1056 * 1057 * Since size is < 4th of the cache size and about 50% of all 1058 * entries get removed by a scan, it is very unlikely that more 1059 * than a fractional scan will be necessary. 1060 */ 1061 while (1) 1062 { 1063 /* first offset behind the insertion window 1064 */ 1065 apr_uint64_t end = cache->next == NO_INDEX 1066 ? cache->data_size 1067 : get_entry(cache, cache->next)->offset; 1068 1069 /* leave function as soon as the insertion window is large enough 1070 */ 1071 if (end >= size + cache->current_data) 1072 return TRUE; 1073 1074 /* Don't be too eager to cache data. Smaller items will fit into 1075 * the cache after dropping a single item. Of the larger ones, we 1076 * will only accept about 50%. They are also likely to get evicted 1077 * soon due to their notoriously low hit counts. 1078 * 1079 * As long as enough similarly or even larger sized entries already 1080 * exist in the cache, much less insert requests will be rejected. 1081 */ 1082 if (2 * drop_size > size) 1083 return FALSE; 1084 1085 /* try to enlarge the insertion window 1086 */ 1087 if (cache->next == NO_INDEX) 1088 { 1089 /* We reached the end of the data buffer; restart at the beginning. 1090 * Due to the randomized nature of our LFU implementation, very 1091 * large data items may require multiple passes. Therefore, SIZE 1092 * should be restricted to significantly less than data_size. 1093 */ 1094 cache->current_data = 0; 1095 cache->next = cache->first; 1096 } 1097 else 1098 { 1099 entry = get_entry(cache, cache->next); 1100 1101 /* Keep entries that are very small. Those are likely to be data 1102 * headers or similar management structures. So, they are probably 1103 * important while not occupying much space. 1104 * But keep them only as long as they are a minority. 1105 */ 1106 if ( (apr_uint64_t)entry->size * cache->used_entries 1107 < cache->data_used / 8) 1108 { 1109 move_entry(cache, entry); 1110 } 1111 else 1112 { 1113 svn_boolean_t keep; 1114 1115 if (cache->hit_count > cache->used_entries) 1116 { 1117 /* Roll the dice and determine a threshold somewhere from 0 up 1118 * to 2 times the average hit count. 1119 */ 1120 average_hit_value = cache->hit_count / cache->used_entries; 1121 threshold = (average_hit_value+1) * (rand() % 4096) / 2048; 1122 1123 keep = entry->hit_count >= threshold; 1124 } 1125 else 1126 { 1127 /* general hit count is low. Keep everything that got hit 1128 * at all and assign some 50% survival chance to everything 1129 * else. 1130 */ 1131 keep = (entry->hit_count > 0) || (rand() & 1); 1132 } 1133 1134 /* keepers or destroyers? */ 1135 if (keep) 1136 { 1137 move_entry(cache, entry); 1138 } 1139 else 1140 { 1141 /* Drop the entry from the end of the insertion window, if it 1142 * has been hit less than the threshold. Otherwise, keep it and 1143 * move the insertion window one entry further. 1144 */ 1145 drop_size += entry->size; 1146 drop_entry(cache, entry); 1147 } 1148 } 1149 } 1150 } 1151 1152 /* This will never be reached. But if it was, "can't insert" was the 1153 * right answer. */ 1154} 1155 1156/* Mimic apr_pcalloc in APR_POOL_DEBUG mode, i.e. handle failed allocations 1157 * (e.g. OOM) properly: Allocate at least SIZE bytes from POOL and zero 1158 * the content of the allocated memory if ZERO has been set. Return NULL 1159 * upon failed allocations. 1160 * 1161 * Also, satisfy our buffer alignment needs for performance reasons. 1162 */ 1163static void* secure_aligned_alloc(apr_pool_t *pool, 1164 apr_size_t size, 1165 svn_boolean_t zero) 1166{ 1167 void* memory = apr_palloc(pool, size + ITEM_ALIGNMENT); 1168 if (memory != NULL) 1169 { 1170 memory = ALIGN_POINTER(memory); 1171 if (zero) 1172 memset(memory, 0, size); 1173 } 1174 1175 return memory; 1176} 1177 1178svn_error_t * 1179svn_cache__membuffer_cache_create(svn_membuffer_t **cache, 1180 apr_size_t total_size, 1181 apr_size_t directory_size, 1182 apr_size_t segment_count, 1183 svn_boolean_t thread_safe, 1184 svn_boolean_t allow_blocking_writes, 1185 apr_pool_t *pool) 1186{ 1187 svn_membuffer_t *c; 1188 1189 apr_uint32_t seg; 1190 apr_uint32_t group_count; 1191 apr_uint32_t group_init_size; 1192 apr_uint64_t data_size; 1193 apr_uint64_t max_entry_size; 1194 1195 /* Limit the total size (only relevant if we can address > 4GB) 1196 */ 1197#if APR_SIZEOF_VOIDP > 4 1198 if (total_size > MAX_SEGMENT_SIZE * MAX_SEGMENT_COUNT) 1199 total_size = MAX_SEGMENT_SIZE * MAX_SEGMENT_COUNT; 1200#endif 1201 1202 /* Limit the segment count 1203 */ 1204 if (segment_count > MAX_SEGMENT_COUNT) 1205 segment_count = MAX_SEGMENT_COUNT; 1206 if (segment_count * MIN_SEGMENT_SIZE > total_size) 1207 segment_count = total_size / MIN_SEGMENT_SIZE; 1208 1209 /* The segment count must be a power of two. Round it down as necessary. 1210 */ 1211 while ((segment_count & (segment_count-1)) != 0) 1212 segment_count &= segment_count-1; 1213 1214 /* if the caller hasn't provided a reasonable segment count or the above 1215 * limitations set it to 0, derive one from the absolute cache size 1216 */ 1217 if (segment_count < 1) 1218 { 1219 /* Determine a reasonable number of cache segments. Segmentation is 1220 * only useful for multi-threaded / multi-core servers as it reduces 1221 * lock contention on these systems. 1222 * 1223 * But on these systems, we can assume that ample memory has been 1224 * allocated to this cache. Smaller caches should not be segmented 1225 * as this severely limits the maximum size of cachable items. 1226 * 1227 * Segments should not be smaller than 32MB and max. cachable item 1228 * size should grow as fast as segmentation. 1229 */ 1230 1231 apr_uint32_t segment_count_shift = 0; 1232 while (((2 * DEFAULT_MIN_SEGMENT_SIZE) << (2 * segment_count_shift)) 1233 < total_size) 1234 ++segment_count_shift; 1235 1236 segment_count = (apr_size_t)1 << segment_count_shift; 1237 } 1238 1239 /* If we have an extremely large cache (>512 GB), the default segment 1240 * size may exceed the amount allocatable as one chunk. In that case, 1241 * increase segmentation until we are under the threshold. 1242 */ 1243 while ( total_size / segment_count > MAX_SEGMENT_SIZE 1244 && segment_count < MAX_SEGMENT_COUNT) 1245 segment_count *= 2; 1246 1247 /* allocate cache as an array of segments / cache objects */ 1248 c = apr_palloc(pool, segment_count * sizeof(*c)); 1249 1250 /* Split total cache size into segments of equal size 1251 */ 1252 total_size /= segment_count; 1253 directory_size /= segment_count; 1254 1255 /* prevent pathological conditions: ensure a certain minimum cache size 1256 */ 1257 if (total_size < 2 * sizeof(entry_group_t)) 1258 total_size = 2 * sizeof(entry_group_t); 1259 1260 /* adapt the dictionary size accordingly, if necessary: 1261 * It must hold at least one group and must not exceed the cache size. 1262 */ 1263 if (directory_size > total_size - sizeof(entry_group_t)) 1264 directory_size = total_size - sizeof(entry_group_t); 1265 if (directory_size < sizeof(entry_group_t)) 1266 directory_size = sizeof(entry_group_t); 1267 1268 /* limit the data size to what we can address. 1269 * Note that this cannot overflow since all values are of size_t. 1270 * Also, make it a multiple of the item placement granularity to 1271 * prevent subtle overflows. 1272 */ 1273 data_size = ALIGN_VALUE(total_size - directory_size + 1) - ITEM_ALIGNMENT; 1274 1275 /* For cache sizes > 4TB, individual cache segments will be larger 1276 * than 16GB allowing for >4GB entries. But caching chunks larger 1277 * than 4GB is simply not supported. 1278 */ 1279 max_entry_size = data_size / 4 > MAX_ITEM_SIZE 1280 ? MAX_ITEM_SIZE 1281 : data_size / 4; 1282 1283 /* to keep the entries small, we use 32 bit indexes only 1284 * -> we need to ensure that no more then 4G entries exist. 1285 * 1286 * Note, that this limit could only be exceeded in a very 1287 * theoretical setup with about 1EB of cache. 1288 */ 1289 group_count = directory_size / sizeof(entry_group_t) 1290 >= (APR_UINT32_MAX / GROUP_SIZE) 1291 ? (APR_UINT32_MAX / GROUP_SIZE) - 1 1292 : (apr_uint32_t)(directory_size / sizeof(entry_group_t)); 1293 1294 group_init_size = 1 + group_count / (8 * GROUP_INIT_GRANULARITY); 1295 for (seg = 0; seg < segment_count; ++seg) 1296 { 1297 /* allocate buffers and initialize cache members 1298 */ 1299 c[seg].segment_count = (apr_uint32_t)segment_count; 1300 1301 c[seg].group_count = group_count; 1302 c[seg].directory = apr_pcalloc(pool, 1303 group_count * sizeof(entry_group_t)); 1304 1305 /* Allocate and initialize directory entries as "not initialized", 1306 hence "unused" */ 1307 c[seg].group_initialized = apr_pcalloc(pool, group_init_size); 1308 1309 c[seg].first = NO_INDEX; 1310 c[seg].last = NO_INDEX; 1311 c[seg].next = NO_INDEX; 1312 1313 c[seg].data_size = data_size; 1314 c[seg].data = secure_aligned_alloc(pool, (apr_size_t)data_size, FALSE); 1315 c[seg].current_data = 0; 1316 c[seg].data_used = 0; 1317 c[seg].max_entry_size = max_entry_size; 1318 1319 c[seg].used_entries = 0; 1320 c[seg].hit_count = 0; 1321 c[seg].total_reads = 0; 1322 c[seg].total_writes = 0; 1323 c[seg].total_hits = 0; 1324 1325 /* were allocations successful? 1326 * If not, initialize a minimal cache structure. 1327 */ 1328 if (c[seg].data == NULL || c[seg].directory == NULL) 1329 { 1330 /* We are OOM. There is no need to proceed with "half a cache". 1331 */ 1332 return svn_error_wrap_apr(APR_ENOMEM, "OOM"); 1333 } 1334 1335#if APR_HAS_THREADS 1336 /* A lock for intra-process synchronization to the cache, or NULL if 1337 * the cache's creator doesn't feel the cache needs to be 1338 * thread-safe. 1339 */ 1340# if USE_SIMPLE_MUTEX 1341 1342 SVN_ERR(svn_mutex__init(&c[seg].lock, thread_safe, pool)); 1343 1344# else 1345 1346 c[seg].lock = NULL; 1347 if (thread_safe) 1348 { 1349 apr_status_t status = 1350 apr_thread_rwlock_create(&(c[seg].lock), pool); 1351 if (status) 1352 return svn_error_wrap_apr(status, _("Can't create cache mutex")); 1353 } 1354 1355# endif 1356 1357 /* Select the behavior of write operations. 1358 */ 1359 c[seg].allow_blocking_writes = allow_blocking_writes; 1360#endif 1361 } 1362 1363 /* done here 1364 */ 1365 *cache = c; 1366 return SVN_NO_ERROR; 1367} 1368 1369/* Look for the cache entry in group GROUP_INDEX of CACHE, identified 1370 * by the hash value TO_FIND and set *FOUND accordingly. 1371 * 1372 * Note: This function requires the caller to serialize access. 1373 * Don't call it directly, call entry_exists instead. 1374 */ 1375static svn_error_t * 1376entry_exists_internal(svn_membuffer_t *cache, 1377 apr_uint32_t group_index, 1378 entry_key_t to_find, 1379 svn_boolean_t *found) 1380{ 1381 *found = find_entry(cache, group_index, to_find, FALSE) != NULL; 1382 return SVN_NO_ERROR; 1383} 1384 1385/* Look for the cache entry in group GROUP_INDEX of CACHE, identified 1386 * by the hash value TO_FIND and set *FOUND accordingly. 1387 */ 1388static svn_error_t * 1389entry_exists(svn_membuffer_t *cache, 1390 apr_uint32_t group_index, 1391 entry_key_t to_find, 1392 svn_boolean_t *found) 1393{ 1394 WITH_READ_LOCK(cache, 1395 entry_exists_internal(cache, 1396 group_index, 1397 to_find, 1398 found)); 1399 1400 return SVN_NO_ERROR; 1401} 1402 1403 1404/* Try to insert the serialized item given in BUFFER with SIZE into 1405 * the group GROUP_INDEX of CACHE and uniquely identify it by hash 1406 * value TO_FIND. 1407 * 1408 * However, there is no guarantee that it will actually be put into 1409 * the cache. If there is already some data associated with TO_FIND, 1410 * it will be removed from the cache even if the new data cannot 1411 * be inserted. 1412 * 1413 * Note: This function requires the caller to serialization access. 1414 * Don't call it directly, call membuffer_cache_get_partial instead. 1415 */ 1416static svn_error_t * 1417membuffer_cache_set_internal(svn_membuffer_t *cache, 1418 entry_key_t to_find, 1419 apr_uint32_t group_index, 1420 char *buffer, 1421 apr_size_t size, 1422 DEBUG_CACHE_MEMBUFFER_TAG_ARG 1423 apr_pool_t *scratch_pool) 1424{ 1425 /* first, look for a previous entry for the given key */ 1426 entry_t *entry = find_entry(cache, group_index, to_find, FALSE); 1427 1428 /* if there is an old version of that entry and the new data fits into 1429 * the old spot, just re-use that space. */ 1430 if (entry && ALIGN_VALUE(entry->size) >= size && buffer) 1431 { 1432 /* Careful! We need to cast SIZE to the full width of CACHE->DATA_USED 1433 * lest we run into trouble with 32 bit underflow *not* treated as a 1434 * negative value. 1435 */ 1436 cache->data_used += (apr_uint64_t)size - entry->size; 1437 entry->size = size; 1438 1439#ifdef SVN_DEBUG_CACHE_MEMBUFFER 1440 1441 /* Remember original content, type and key (hashes) 1442 */ 1443 SVN_ERR(store_content_part(tag, buffer, size, scratch_pool)); 1444 memcpy(&entry->tag, tag, sizeof(*tag)); 1445 1446#endif 1447 1448 if (size) 1449 memcpy(cache->data + entry->offset, buffer, size); 1450 1451 cache->total_writes++; 1452 return SVN_NO_ERROR; 1453 } 1454 1455 /* if necessary, enlarge the insertion window. 1456 */ 1457 if ( buffer != NULL 1458 && cache->max_entry_size >= size 1459 && ensure_data_insertable(cache, size)) 1460 { 1461 /* Remove old data for this key, if that exists. 1462 * Get an unused entry for the key and and initialize it with 1463 * the serialized item's (future) position within data buffer. 1464 */ 1465 entry = find_entry(cache, group_index, to_find, TRUE); 1466 entry->size = size; 1467 entry->offset = cache->current_data; 1468 1469#ifdef SVN_DEBUG_CACHE_MEMBUFFER 1470 1471 /* Remember original content, type and key (hashes) 1472 */ 1473 SVN_ERR(store_content_part(tag, buffer, size, scratch_pool)); 1474 memcpy(&entry->tag, tag, sizeof(*tag)); 1475 1476#endif 1477 1478 /* Link the entry properly. 1479 */ 1480 insert_entry(cache, entry); 1481 1482 /* Copy the serialized item data into the cache. 1483 */ 1484 if (size) 1485 memcpy(cache->data + entry->offset, buffer, size); 1486 1487 cache->total_writes++; 1488 } 1489 else 1490 { 1491 /* if there is already an entry for this key, drop it. 1492 * Since ensure_data_insertable may have removed entries from 1493 * ENTRY's group, re-do the lookup. 1494 */ 1495 entry = find_entry(cache, group_index, to_find, FALSE); 1496 if (entry) 1497 drop_entry(cache, entry); 1498 } 1499 1500 return SVN_NO_ERROR; 1501} 1502 1503/* Try to insert the ITEM and use the KEY to uniquely identify it. 1504 * However, there is no guarantee that it will actually be put into 1505 * the cache. If there is already some data associated to the KEY, 1506 * it will be removed from the cache even if the new data cannot 1507 * be inserted. 1508 * 1509 * The SERIALIZER is called to transform the ITEM into a single, 1510 * flat data buffer. Temporary allocations may be done in POOL. 1511 */ 1512static svn_error_t * 1513membuffer_cache_set(svn_membuffer_t *cache, 1514 entry_key_t key, 1515 void *item, 1516 svn_cache__serialize_func_t serializer, 1517 DEBUG_CACHE_MEMBUFFER_TAG_ARG 1518 apr_pool_t *scratch_pool) 1519{ 1520 apr_uint32_t group_index; 1521 void *buffer = NULL; 1522 apr_size_t size = 0; 1523 1524 /* find the entry group that will hold the key. 1525 */ 1526 group_index = get_group_index(&cache, key); 1527 1528 /* Serialize data data. 1529 */ 1530 if (item) 1531 SVN_ERR(serializer(&buffer, &size, item, scratch_pool)); 1532 1533 /* The actual cache data access needs to sync'ed 1534 */ 1535 WITH_WRITE_LOCK(cache, 1536 membuffer_cache_set_internal(cache, 1537 key, 1538 group_index, 1539 buffer, 1540 size, 1541 DEBUG_CACHE_MEMBUFFER_TAG 1542 scratch_pool)); 1543 return SVN_NO_ERROR; 1544} 1545 1546/* Look for the cache entry in group GROUP_INDEX of CACHE, identified 1547 * by the hash value TO_FIND. If no item has been stored for KEY, 1548 * *BUFFER will be NULL. Otherwise, return a copy of the serialized 1549 * data in *BUFFER and return its size in *ITEM_SIZE. Allocations will 1550 * be done in POOL. 1551 * 1552 * Note: This function requires the caller to serialization access. 1553 * Don't call it directly, call membuffer_cache_get_partial instead. 1554 */ 1555static svn_error_t * 1556membuffer_cache_get_internal(svn_membuffer_t *cache, 1557 apr_uint32_t group_index, 1558 entry_key_t to_find, 1559 char **buffer, 1560 apr_size_t *item_size, 1561 DEBUG_CACHE_MEMBUFFER_TAG_ARG 1562 apr_pool_t *result_pool) 1563{ 1564 entry_t *entry; 1565 apr_size_t size; 1566 1567 /* The actual cache data access needs to sync'ed 1568 */ 1569 entry = find_entry(cache, group_index, to_find, FALSE); 1570 cache->total_reads++; 1571 if (entry == NULL) 1572 { 1573 /* no such entry found. 1574 */ 1575 *buffer = NULL; 1576 *item_size = 0; 1577 1578 return SVN_NO_ERROR; 1579 } 1580 1581 size = ALIGN_VALUE(entry->size); 1582 *buffer = ALIGN_POINTER(apr_palloc(result_pool, size + ITEM_ALIGNMENT-1)); 1583 memcpy(*buffer, (const char*)cache->data + entry->offset, size); 1584 1585#ifdef SVN_DEBUG_CACHE_MEMBUFFER 1586 1587 /* Check for overlapping entries. 1588 */ 1589 SVN_ERR_ASSERT(entry->next == NO_INDEX || 1590 entry->offset + size 1591 <= get_entry(cache, entry->next)->offset); 1592 1593 /* Compare original content, type and key (hashes) 1594 */ 1595 SVN_ERR(store_content_part(tag, *buffer, entry->size, result_pool)); 1596 SVN_ERR(assert_equal_tags(&entry->tag, tag)); 1597 1598#endif 1599 1600 /* update hit statistics 1601 */ 1602 entry->hit_count++; 1603 cache->hit_count++; 1604 cache->total_hits++; 1605 1606 *item_size = entry->size; 1607 1608 return SVN_NO_ERROR; 1609} 1610 1611/* Look for the *ITEM identified by KEY. If no item has been stored 1612 * for KEY, *ITEM will be NULL. Otherwise, the DESERIALIZER is called 1613 * re-construct the proper object from the serialized data. 1614 * Allocations will be done in POOL. 1615 */ 1616static svn_error_t * 1617membuffer_cache_get(svn_membuffer_t *cache, 1618 entry_key_t key, 1619 void **item, 1620 svn_cache__deserialize_func_t deserializer, 1621 DEBUG_CACHE_MEMBUFFER_TAG_ARG 1622 apr_pool_t *result_pool) 1623{ 1624 apr_uint32_t group_index; 1625 char *buffer; 1626 apr_size_t size; 1627 1628 /* find the entry group that will hold the key. 1629 */ 1630 group_index = get_group_index(&cache, key); 1631 WITH_READ_LOCK(cache, 1632 membuffer_cache_get_internal(cache, 1633 group_index, 1634 key, 1635 &buffer, 1636 &size, 1637 DEBUG_CACHE_MEMBUFFER_TAG 1638 result_pool)); 1639 1640 /* re-construct the original data object from its serialized form. 1641 */ 1642 if (buffer == NULL) 1643 { 1644 *item = NULL; 1645 return SVN_NO_ERROR; 1646 } 1647 1648 return deserializer(item, buffer, size, result_pool); 1649} 1650 1651/* Look for the cache entry in group GROUP_INDEX of CACHE, identified 1652 * by the hash value TO_FIND. FOUND indicates whether that entry exists. 1653 * If not found, *ITEM will be NULL. 1654 * 1655 * Otherwise, the DESERIALIZER is called with that entry and the BATON 1656 * provided and will extract the desired information. The result is set 1657 * in *ITEM. Allocations will be done in POOL. 1658 * 1659 * Note: This function requires the caller to serialization access. 1660 * Don't call it directly, call membuffer_cache_get_partial instead. 1661 */ 1662static svn_error_t * 1663membuffer_cache_get_partial_internal(svn_membuffer_t *cache, 1664 apr_uint32_t group_index, 1665 entry_key_t to_find, 1666 void **item, 1667 svn_boolean_t *found, 1668 svn_cache__partial_getter_func_t deserializer, 1669 void *baton, 1670 DEBUG_CACHE_MEMBUFFER_TAG_ARG 1671 apr_pool_t *result_pool) 1672{ 1673 entry_t *entry = find_entry(cache, group_index, to_find, FALSE); 1674 cache->total_reads++; 1675 if (entry == NULL) 1676 { 1677 *item = NULL; 1678 *found = FALSE; 1679 1680 return SVN_NO_ERROR; 1681 } 1682 else 1683 { 1684 *found = TRUE; 1685 1686 entry->hit_count++; 1687 cache->hit_count++; 1688 cache->total_hits++; 1689 1690#ifdef SVN_DEBUG_CACHE_MEMBUFFER 1691 1692 /* Check for overlapping entries. 1693 */ 1694 SVN_ERR_ASSERT(entry->next == NO_INDEX || 1695 entry->offset + entry->size 1696 <= get_entry(cache, entry->next)->offset); 1697 1698 /* Compare original content, type and key (hashes) 1699 */ 1700 SVN_ERR(store_content_part(tag, 1701 (const char*)cache->data + entry->offset, 1702 entry->size, 1703 result_pool)); 1704 SVN_ERR(assert_equal_tags(&entry->tag, tag)); 1705 1706#endif 1707 1708 return deserializer(item, 1709 (const char*)cache->data + entry->offset, 1710 entry->size, 1711 baton, 1712 result_pool); 1713 } 1714} 1715 1716/* Look for the cache entry identified by KEY. FOUND indicates 1717 * whether that entry exists. If not found, *ITEM will be NULL. Otherwise, 1718 * the DESERIALIZER is called with that entry and the BATON provided 1719 * and will extract the desired information. The result is set in *ITEM. 1720 * Allocations will be done in POOL. 1721 */ 1722static svn_error_t * 1723membuffer_cache_get_partial(svn_membuffer_t *cache, 1724 entry_key_t key, 1725 void **item, 1726 svn_boolean_t *found, 1727 svn_cache__partial_getter_func_t deserializer, 1728 void *baton, 1729 DEBUG_CACHE_MEMBUFFER_TAG_ARG 1730 apr_pool_t *result_pool) 1731{ 1732 apr_uint32_t group_index = get_group_index(&cache, key); 1733 1734 WITH_READ_LOCK(cache, 1735 membuffer_cache_get_partial_internal 1736 (cache, group_index, key, item, found, 1737 deserializer, baton, DEBUG_CACHE_MEMBUFFER_TAG 1738 result_pool)); 1739 1740 return SVN_NO_ERROR; 1741} 1742 1743/* Look for the cache entry in group GROUP_INDEX of CACHE, identified 1744 * by the hash value TO_FIND. If no entry has been found, the function 1745 * returns without modifying the cache. 1746 * 1747 * Otherwise, FUNC is called with that entry and the BATON provided 1748 * and may modify the cache entry. Allocations will be done in POOL. 1749 * 1750 * Note: This function requires the caller to serialization access. 1751 * Don't call it directly, call membuffer_cache_set_partial instead. 1752 */ 1753static svn_error_t * 1754membuffer_cache_set_partial_internal(svn_membuffer_t *cache, 1755 apr_uint32_t group_index, 1756 entry_key_t to_find, 1757 svn_cache__partial_setter_func_t func, 1758 void *baton, 1759 DEBUG_CACHE_MEMBUFFER_TAG_ARG 1760 apr_pool_t *scratch_pool) 1761{ 1762 /* cache item lookup 1763 */ 1764 entry_t *entry = find_entry(cache, group_index, to_find, FALSE); 1765 cache->total_reads++; 1766 1767 /* this function is a no-op if the item is not in cache 1768 */ 1769 if (entry != NULL) 1770 { 1771 svn_error_t *err; 1772 1773 /* access the serialized cache item */ 1774 char *data = (char*)cache->data + entry->offset; 1775 char *orig_data = data; 1776 apr_size_t size = entry->size; 1777 1778 entry->hit_count++; 1779 cache->hit_count++; 1780 cache->total_writes++; 1781 1782#ifdef SVN_DEBUG_CACHE_MEMBUFFER 1783 1784 /* Check for overlapping entries. 1785 */ 1786 SVN_ERR_ASSERT(entry->next == NO_INDEX || 1787 entry->offset + size 1788 <= get_entry(cache, entry->next)->offset); 1789 1790 /* Compare original content, type and key (hashes) 1791 */ 1792 SVN_ERR(store_content_part(tag, data, size, scratch_pool)); 1793 SVN_ERR(assert_equal_tags(&entry->tag, tag)); 1794 1795#endif 1796 1797 /* modify it, preferably in-situ. 1798 */ 1799 err = func((void **)&data, &size, baton, scratch_pool); 1800 1801 if (err) 1802 { 1803 /* Something somewhere when wrong while FUNC was modifying the 1804 * changed item. Thus, it might have become invalid /corrupted. 1805 * We better drop that. 1806 */ 1807 drop_entry(cache, entry); 1808 } 1809 else 1810 { 1811 /* if the modification caused a re-allocation, we need to remove 1812 * the old entry and to copy the new data back into cache. 1813 */ 1814 if (data != orig_data) 1815 { 1816 /* Remove the old entry and try to make space for the new one. 1817 */ 1818 drop_entry(cache, entry); 1819 if ( (cache->max_entry_size >= size) 1820 && ensure_data_insertable(cache, size)) 1821 { 1822 /* Write the new entry. 1823 */ 1824 entry = find_entry(cache, group_index, to_find, TRUE); 1825 entry->size = size; 1826 entry->offset = cache->current_data; 1827 if (size) 1828 memcpy(cache->data + entry->offset, data, size); 1829 1830 /* Link the entry properly. 1831 */ 1832 insert_entry(cache, entry); 1833 } 1834 } 1835 1836#ifdef SVN_DEBUG_CACHE_MEMBUFFER 1837 1838 /* Remember original content, type and key (hashes) 1839 */ 1840 SVN_ERR(store_content_part(tag, data, size, scratch_pool)); 1841 memcpy(&entry->tag, tag, sizeof(*tag)); 1842 1843#endif 1844 } 1845 } 1846 1847 return SVN_NO_ERROR; 1848} 1849 1850/* Look for the cache entry identified by KEY. If no entry 1851 * has been found, the function returns without modifying the cache. 1852 * Otherwise, FUNC is called with that entry and the BATON provided 1853 * and may modify the cache entry. Allocations will be done in POOL. 1854 */ 1855static svn_error_t * 1856membuffer_cache_set_partial(svn_membuffer_t *cache, 1857 entry_key_t key, 1858 svn_cache__partial_setter_func_t func, 1859 void *baton, 1860 DEBUG_CACHE_MEMBUFFER_TAG_ARG 1861 apr_pool_t *scratch_pool) 1862{ 1863 /* cache item lookup 1864 */ 1865 apr_uint32_t group_index = get_group_index(&cache, key); 1866 WITH_WRITE_LOCK(cache, 1867 membuffer_cache_set_partial_internal 1868 (cache, group_index, key, func, baton, 1869 DEBUG_CACHE_MEMBUFFER_TAG 1870 scratch_pool)); 1871 1872 /* done here -> unlock the cache 1873 */ 1874 return SVN_NO_ERROR; 1875} 1876 1877/* Implement the svn_cache__t interface on top of a shared membuffer cache. 1878 * 1879 * Because membuffer caches tend to be very large, there will be rather few 1880 * of them (usually only one). Thus, the same instance shall be used as the 1881 * backend to many application-visible svn_cache__t instances. This should 1882 * also achieve global resource usage fairness. 1883 * 1884 * To accommodate items from multiple resources, the individual keys must be 1885 * unique over all sources. This is achieved by simply adding a prefix key 1886 * that unambiguously identifies the item's context (e.g. path to the 1887 * respective repository). The prefix will be set upon construction of the 1888 * svn_cache__t instance. 1889 */ 1890 1891/* Internal cache structure (used in svn_cache__t.cache_internal) basically 1892 * holding the additional parameters needed to call the respective membuffer 1893 * functions. 1894 */ 1895typedef struct svn_membuffer_cache_t 1896{ 1897 /* this is where all our data will end up in 1898 */ 1899 svn_membuffer_t *membuffer; 1900 1901 /* use this conversion function when inserting an item into the memcache 1902 */ 1903 svn_cache__serialize_func_t serializer; 1904 1905 /* use this conversion function when reading an item from the memcache 1906 */ 1907 svn_cache__deserialize_func_t deserializer; 1908 1909 /* Prepend this byte sequence to any key passed to us. 1910 * This makes (very likely) our keys different from all keys used 1911 * by other svn_membuffer_cache_t instances. 1912 */ 1913 entry_key_t prefix; 1914 1915 /* A copy of the unmodified prefix. It is being used as a user-visible 1916 * ID for this cache instance. 1917 */ 1918 const char* full_prefix; 1919 1920 /* length of the keys that will be passed to us through the 1921 * svn_cache_t interface. May be APR_HASH_KEY_STRING. 1922 */ 1923 apr_ssize_t key_len; 1924 1925 /* Temporary buffer containing the hash key for the current access 1926 */ 1927 entry_key_t combined_key; 1928 1929 /* a pool for temporary allocations during get() and set() 1930 */ 1931 apr_pool_t *pool; 1932 1933 /* an internal counter that is used to clear the pool from time to time 1934 * but not too frequently. 1935 */ 1936 int alloc_counter; 1937 1938 /* if enabled, this will serialize the access to this instance. 1939 */ 1940 svn_mutex__t *mutex; 1941#ifdef SVN_DEBUG_CACHE_MEMBUFFER 1942 1943 /* Invariant tag info for all items stored by this cache instance. 1944 */ 1945 char prefix_tail[PREFIX_TAIL_LEN]; 1946 1947#endif 1948} svn_membuffer_cache_t; 1949 1950/* After an estimated ALLOCATIONS_PER_POOL_CLEAR allocations, we should 1951 * clear the svn_membuffer_cache_t.pool to keep memory consumption in check. 1952 */ 1953#define ALLOCATIONS_PER_POOL_CLEAR 10 1954 1955 1956/* Basically calculate a hash value for KEY of length KEY_LEN, combine it 1957 * with the CACHE->PREFIX and write the result in CACHE->COMBINED_KEY. 1958 */ 1959static void 1960combine_key(svn_membuffer_cache_t *cache, 1961 const void *key, 1962 apr_ssize_t key_len) 1963{ 1964 if (key_len == APR_HASH_KEY_STRING) 1965 key_len = strlen((const char *) key); 1966 1967 if (key_len < 16) 1968 { 1969 apr_uint32_t data[4] = { 0 }; 1970 memcpy(data, key, key_len); 1971 1972 svn__pseudo_md5_15((apr_uint32_t *)cache->combined_key, data); 1973 } 1974 else if (key_len < 32) 1975 { 1976 apr_uint32_t data[8] = { 0 }; 1977 memcpy(data, key, key_len); 1978 1979 svn__pseudo_md5_31((apr_uint32_t *)cache->combined_key, data); 1980 } 1981 else if (key_len < 64) 1982 { 1983 apr_uint32_t data[16] = { 0 }; 1984 memcpy(data, key, key_len); 1985 1986 svn__pseudo_md5_63((apr_uint32_t *)cache->combined_key, data); 1987 } 1988 else 1989 { 1990 apr_md5((unsigned char*)cache->combined_key, key, key_len); 1991 } 1992 1993 cache->combined_key[0] ^= cache->prefix[0]; 1994 cache->combined_key[1] ^= cache->prefix[1]; 1995} 1996 1997/* Implement svn_cache__vtable_t.get (not thread-safe) 1998 */ 1999static svn_error_t * 2000svn_membuffer_cache_get(void **value_p, 2001 svn_boolean_t *found, 2002 void *cache_void, 2003 const void *key, 2004 apr_pool_t *result_pool) 2005{ 2006 svn_membuffer_cache_t *cache = cache_void; 2007 2008 DEBUG_CACHE_MEMBUFFER_INIT_TAG 2009 2010 /* special case */ 2011 if (key == NULL) 2012 { 2013 *value_p = NULL; 2014 *found = FALSE; 2015 2016 return SVN_NO_ERROR; 2017 } 2018 2019 /* construct the full, i.e. globally unique, key by adding 2020 * this cache instances' prefix 2021 */ 2022 combine_key(cache, key, cache->key_len); 2023 2024 /* Look the item up. */ 2025 SVN_ERR(membuffer_cache_get(cache->membuffer, 2026 cache->combined_key, 2027 value_p, 2028 cache->deserializer, 2029 DEBUG_CACHE_MEMBUFFER_TAG 2030 result_pool)); 2031 2032 /* return result */ 2033 *found = *value_p != NULL; 2034 return SVN_NO_ERROR; 2035} 2036 2037/* Implement svn_cache__vtable_t.set (not thread-safe) 2038 */ 2039static svn_error_t * 2040svn_membuffer_cache_set(void *cache_void, 2041 const void *key, 2042 void *value, 2043 apr_pool_t *scratch_pool) 2044{ 2045 svn_membuffer_cache_t *cache = cache_void; 2046 2047 DEBUG_CACHE_MEMBUFFER_INIT_TAG 2048 2049 /* special case */ 2050 if (key == NULL) 2051 return SVN_NO_ERROR; 2052 2053 /* we do some allocations below, so increase the allocation counter 2054 * by a slightly larger amount. Free allocated memory every now and then. 2055 */ 2056 cache->alloc_counter += 3; 2057 if (cache->alloc_counter > ALLOCATIONS_PER_POOL_CLEAR) 2058 { 2059 svn_pool_clear(cache->pool); 2060 cache->alloc_counter = 0; 2061 } 2062 2063 /* construct the full, i.e. globally unique, key by adding 2064 * this cache instances' prefix 2065 */ 2066 combine_key(cache, key, cache->key_len); 2067 2068 /* (probably) add the item to the cache. But there is no real guarantee 2069 * that the item will actually be cached afterwards. 2070 */ 2071 return membuffer_cache_set(cache->membuffer, 2072 cache->combined_key, 2073 value, 2074 cache->serializer, 2075 DEBUG_CACHE_MEMBUFFER_TAG 2076 cache->pool); 2077} 2078 2079/* Implement svn_cache__vtable_t.iter as "not implemented" 2080 */ 2081static svn_error_t * 2082svn_membuffer_cache_iter(svn_boolean_t *completed, 2083 void *cache_void, 2084 svn_iter_apr_hash_cb_t user_cb, 2085 void *user_baton, 2086 apr_pool_t *scratch_pool) 2087{ 2088 return svn_error_create(SVN_ERR_UNSUPPORTED_FEATURE, NULL, 2089 _("Can't iterate a membuffer-based cache")); 2090} 2091 2092/* Implement svn_cache__vtable_t.get_partial (not thread-safe) 2093 */ 2094static svn_error_t * 2095svn_membuffer_cache_get_partial(void **value_p, 2096 svn_boolean_t *found, 2097 void *cache_void, 2098 const void *key, 2099 svn_cache__partial_getter_func_t func, 2100 void *baton, 2101 apr_pool_t *result_pool) 2102{ 2103 svn_membuffer_cache_t *cache = cache_void; 2104 2105 DEBUG_CACHE_MEMBUFFER_INIT_TAG 2106 2107 if (key == NULL) 2108 { 2109 *value_p = NULL; 2110 *found = FALSE; 2111 2112 return SVN_NO_ERROR; 2113 } 2114 2115 combine_key(cache, key, cache->key_len); 2116 SVN_ERR(membuffer_cache_get_partial(cache->membuffer, 2117 cache->combined_key, 2118 value_p, 2119 found, 2120 func, 2121 baton, 2122 DEBUG_CACHE_MEMBUFFER_TAG 2123 result_pool)); 2124 2125 return SVN_NO_ERROR; 2126} 2127 2128/* Implement svn_cache__vtable_t.set_partial (not thread-safe) 2129 */ 2130static svn_error_t * 2131svn_membuffer_cache_set_partial(void *cache_void, 2132 const void *key, 2133 svn_cache__partial_setter_func_t func, 2134 void *baton, 2135 apr_pool_t *scratch_pool) 2136{ 2137 svn_membuffer_cache_t *cache = cache_void; 2138 2139 DEBUG_CACHE_MEMBUFFER_INIT_TAG 2140 2141 if (key != NULL) 2142 { 2143 combine_key(cache, key, cache->key_len); 2144 SVN_ERR(membuffer_cache_set_partial(cache->membuffer, 2145 cache->combined_key, 2146 func, 2147 baton, 2148 DEBUG_CACHE_MEMBUFFER_TAG 2149 scratch_pool)); 2150 } 2151 return SVN_NO_ERROR; 2152} 2153 2154/* Implement svn_cache__vtable_t.is_cachable 2155 * (thread-safe even without mutex) 2156 */ 2157static svn_boolean_t 2158svn_membuffer_cache_is_cachable(void *cache_void, apr_size_t size) 2159{ 2160 /* Don't allow extremely large element sizes. Otherwise, the cache 2161 * might by thrashed by a few extremely large entries. And the size 2162 * must be small enough to be stored in a 32 bit value. 2163 */ 2164 svn_membuffer_cache_t *cache = cache_void; 2165 return size <= cache->membuffer->max_entry_size; 2166} 2167 2168/* Add statistics of SEGMENT to INFO. 2169 */ 2170static svn_error_t * 2171svn_membuffer_get_segment_info(svn_membuffer_t *segment, 2172 svn_cache__info_t *info) 2173{ 2174 info->data_size += segment->data_size; 2175 info->used_size += segment->data_used; 2176 info->total_size += segment->data_size + 2177 segment->group_count * GROUP_SIZE * sizeof(entry_t); 2178 2179 info->used_entries += segment->used_entries; 2180 info->total_entries += segment->group_count * GROUP_SIZE; 2181 2182 return SVN_NO_ERROR; 2183} 2184 2185/* Implement svn_cache__vtable_t.get_info 2186 * (thread-safe even without mutex) 2187 */ 2188static svn_error_t * 2189svn_membuffer_cache_get_info(void *cache_void, 2190 svn_cache__info_t *info, 2191 svn_boolean_t reset, 2192 apr_pool_t *result_pool) 2193{ 2194 svn_membuffer_cache_t *cache = cache_void; 2195 apr_uint32_t i; 2196 2197 /* cache front-end specific data */ 2198 2199 info->id = apr_pstrdup(result_pool, cache->full_prefix); 2200 2201 /* collect info from shared cache back-end */ 2202 2203 info->data_size = 0; 2204 info->used_size = 0; 2205 info->total_size = 0; 2206 2207 info->used_entries = 0; 2208 info->total_entries = 0; 2209 2210 for (i = 0; i < cache->membuffer->segment_count; ++i) 2211 { 2212 svn_membuffer_t *segment = cache->membuffer + i; 2213 WITH_READ_LOCK(segment, 2214 svn_membuffer_get_segment_info(segment, info)); 2215 } 2216 2217 return SVN_NO_ERROR; 2218} 2219 2220 2221/* the v-table for membuffer-based caches (single-threaded access) 2222 */ 2223static svn_cache__vtable_t membuffer_cache_vtable = { 2224 svn_membuffer_cache_get, 2225 svn_membuffer_cache_set, 2226 svn_membuffer_cache_iter, 2227 svn_membuffer_cache_is_cachable, 2228 svn_membuffer_cache_get_partial, 2229 svn_membuffer_cache_set_partial, 2230 svn_membuffer_cache_get_info 2231}; 2232 2233/* Implement svn_cache__vtable_t.get and serialize all cache access. 2234 */ 2235static svn_error_t * 2236svn_membuffer_cache_get_synced(void **value_p, 2237 svn_boolean_t *found, 2238 void *cache_void, 2239 const void *key, 2240 apr_pool_t *result_pool) 2241{ 2242 svn_membuffer_cache_t *cache = cache_void; 2243 SVN_MUTEX__WITH_LOCK(cache->mutex, 2244 svn_membuffer_cache_get(value_p, 2245 found, 2246 cache_void, 2247 key, 2248 result_pool)); 2249 2250 return SVN_NO_ERROR; 2251} 2252 2253/* Implement svn_cache__vtable_t.set and serialize all cache access. 2254 */ 2255static svn_error_t * 2256svn_membuffer_cache_set_synced(void *cache_void, 2257 const void *key, 2258 void *value, 2259 apr_pool_t *scratch_pool) 2260{ 2261 svn_membuffer_cache_t *cache = cache_void; 2262 SVN_MUTEX__WITH_LOCK(cache->mutex, 2263 svn_membuffer_cache_set(cache_void, 2264 key, 2265 value, 2266 scratch_pool)); 2267 2268 return SVN_NO_ERROR; 2269} 2270 2271/* Implement svn_cache__vtable_t.get_partial and serialize all cache access. 2272 */ 2273static svn_error_t * 2274svn_membuffer_cache_get_partial_synced(void **value_p, 2275 svn_boolean_t *found, 2276 void *cache_void, 2277 const void *key, 2278 svn_cache__partial_getter_func_t func, 2279 void *baton, 2280 apr_pool_t *result_pool) 2281{ 2282 svn_membuffer_cache_t *cache = cache_void; 2283 SVN_MUTEX__WITH_LOCK(cache->mutex, 2284 svn_membuffer_cache_get_partial(value_p, 2285 found, 2286 cache_void, 2287 key, 2288 func, 2289 baton, 2290 result_pool)); 2291 2292 return SVN_NO_ERROR; 2293} 2294 2295/* Implement svn_cache__vtable_t.set_partial and serialize all cache access. 2296 */ 2297static svn_error_t * 2298svn_membuffer_cache_set_partial_synced(void *cache_void, 2299 const void *key, 2300 svn_cache__partial_setter_func_t func, 2301 void *baton, 2302 apr_pool_t *scratch_pool) 2303{ 2304 svn_membuffer_cache_t *cache = cache_void; 2305 SVN_MUTEX__WITH_LOCK(cache->mutex, 2306 svn_membuffer_cache_set_partial(cache_void, 2307 key, 2308 func, 2309 baton, 2310 scratch_pool)); 2311 2312 return SVN_NO_ERROR; 2313} 2314 2315/* the v-table for membuffer-based caches with multi-threading support) 2316 */ 2317static svn_cache__vtable_t membuffer_cache_synced_vtable = { 2318 svn_membuffer_cache_get_synced, 2319 svn_membuffer_cache_set_synced, 2320 svn_membuffer_cache_iter, /* no sync required */ 2321 svn_membuffer_cache_is_cachable, /* no sync required */ 2322 svn_membuffer_cache_get_partial_synced, 2323 svn_membuffer_cache_set_partial_synced, 2324 svn_membuffer_cache_get_info /* no sync required */ 2325}; 2326 2327/* standard serialization function for svn_stringbuf_t items. 2328 * Implements svn_cache__serialize_func_t. 2329 */ 2330static svn_error_t * 2331serialize_svn_stringbuf(void **buffer, 2332 apr_size_t *buffer_size, 2333 void *item, 2334 apr_pool_t *result_pool) 2335{ 2336 svn_stringbuf_t *value_str = item; 2337 2338 *buffer = value_str->data; 2339 *buffer_size = value_str->len + 1; 2340 2341 return SVN_NO_ERROR; 2342} 2343 2344/* standard de-serialization function for svn_stringbuf_t items. 2345 * Implements svn_cache__deserialize_func_t. 2346 */ 2347static svn_error_t * 2348deserialize_svn_stringbuf(void **item, 2349 void *buffer, 2350 apr_size_t buffer_size, 2351 apr_pool_t *result_pool) 2352{ 2353 svn_stringbuf_t *value_str = apr_palloc(result_pool, sizeof(svn_stringbuf_t)); 2354 2355 value_str->pool = result_pool; 2356 value_str->blocksize = buffer_size; 2357 value_str->data = buffer; 2358 value_str->len = buffer_size-1; 2359 *item = value_str; 2360 2361 return SVN_NO_ERROR; 2362} 2363 2364/* Construct a svn_cache__t object on top of a shared memcache. 2365 */ 2366svn_error_t * 2367svn_cache__create_membuffer_cache(svn_cache__t **cache_p, 2368 svn_membuffer_t *membuffer, 2369 svn_cache__serialize_func_t serializer, 2370 svn_cache__deserialize_func_t deserializer, 2371 apr_ssize_t klen, 2372 const char *prefix, 2373 svn_boolean_t thread_safe, 2374 apr_pool_t *pool) 2375{ 2376 svn_checksum_t *checksum; 2377 2378 /* allocate the cache header structures 2379 */ 2380 svn_cache__t *wrapper = apr_pcalloc(pool, sizeof(*wrapper)); 2381 svn_membuffer_cache_t *cache = apr_palloc(pool, sizeof(*cache)); 2382 2383 /* initialize our internal cache header 2384 */ 2385 cache->membuffer = membuffer; 2386 cache->serializer = serializer 2387 ? serializer 2388 : serialize_svn_stringbuf; 2389 cache->deserializer = deserializer 2390 ? deserializer 2391 : deserialize_svn_stringbuf; 2392 cache->full_prefix = apr_pstrdup(pool, prefix); 2393 cache->key_len = klen; 2394 cache->pool = svn_pool_create(pool); 2395 cache->alloc_counter = 0; 2396 2397 SVN_ERR(svn_mutex__init(&cache->mutex, thread_safe, pool)); 2398 2399 /* for performance reasons, we don't actually store the full prefix but a 2400 * hash value of it 2401 */ 2402 SVN_ERR(svn_checksum(&checksum, 2403 svn_checksum_md5, 2404 prefix, 2405 strlen(prefix), 2406 pool)); 2407 memcpy(cache->prefix, checksum->digest, sizeof(cache->prefix)); 2408 2409#ifdef SVN_DEBUG_CACHE_MEMBUFFER 2410 2411 /* Initialize cache debugging support. 2412 */ 2413 get_prefix_tail(prefix, cache->prefix_tail); 2414 2415#endif 2416 2417 /* initialize the generic cache wrapper 2418 */ 2419 wrapper->vtable = thread_safe ? &membuffer_cache_synced_vtable 2420 : &membuffer_cache_vtable; 2421 wrapper->cache_internal = cache; 2422 wrapper->error_handler = 0; 2423 wrapper->error_baton = 0; 2424 2425 *cache_p = wrapper; 2426 return SVN_NO_ERROR; 2427} 2428 2429