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