| /* |
| * cache-membuffer.c: in-memory caching for Subversion |
| * |
| * ==================================================================== |
| * Licensed to the Apache Software Foundation (ASF) under one |
| * or more contributor license agreements. See the NOTICE file |
| * distributed with this work for additional information |
| * regarding copyright ownership. The ASF licenses this file |
| * to you under the Apache License, Version 2.0 (the |
| * "License"); you may not use this file except in compliance |
| * with the License. You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, |
| * software distributed under the License is distributed on an |
| * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY |
| * KIND, either express or implied. See the License for the |
| * specific language governing permissions and limitations |
| * under the License. |
| * ==================================================================== |
| */ |
| |
| #include <assert.h> |
| #include <apr_md5.h> |
| #include <apr_thread_rwlock.h> |
| |
| #include "svn_pools.h" |
| #include "svn_checksum.h" |
| #include "svn_private_config.h" |
| #include "svn_hash.h" |
| #include "svn_string.h" |
| #include "svn_sorts.h" /* get the MIN macro */ |
| |
| #include "private/svn_atomic.h" |
| #include "private/svn_dep_compat.h" |
| #include "private/svn_mutex.h" |
| #include "private/svn_subr_private.h" |
| #include "private/svn_string_private.h" |
| |
| #include "cache.h" |
| #include "fnv1a.h" |
| |
| /* |
| * This svn_cache__t implementation actually consists of two parts: |
| * a shared (per-process) singleton membuffer cache instance and shallow |
| * svn_cache__t front-end instances that each use different key spaces. |
| * For data management, they all forward to the singleton membuffer cache. |
| * |
| * A membuffer cache consists of two parts: |
| * |
| * 1. A linear data buffer containing cached items in a serialized |
| * representation, prefixed by their full cache keys. There may be |
| * arbitrary gaps between entries. This buffer is sub-devided into |
| * (currently two) cache levels. |
| * |
| * 2. A directory of cache entries. This is organized similar to CPU |
| * data caches: for every possible key, there is exactly one group |
| * of entries that may contain the header info for an item with |
| * that given key. The result is a GROUP_SIZE+-way associative cache |
| * whose associativity can be dynamically increased. |
| * |
| * Only the start address of these two data parts are given as a native |
| * pointer. All other references are expressed as offsets to these pointers. |
| * With that design, it is relatively easy to share the same data structure |
| * between different processes and / or to persist them on disk. These |
| * out-of-process features have not been implemented, yet. |
| * |
| * Superficially, cache levels are being used as usual: insertion happens |
| * into L1 and evictions will promote items to L2. But their whole point |
| * is a different one. L1 uses a circular buffer, i.e. we have perfect |
| * caching for the last N bytes where N is the size of L1. L2 uses a more |
| * elaborate scheme based on priorities and hit counts as described below. |
| * |
| * The data buffer usage information is implicitly given by the directory |
| * entries. Every USED entry has a reference to the previous and the next |
| * used dictionary entry and this double-linked list is ordered by the |
| * offsets of their item data within the data buffer. So removing data, |
| * for instance, is done simply by unlinking it from the chain, implicitly |
| * marking the entry as well as the data buffer section previously |
| * associated to it as unused. First and last element of that chain are |
| * being referenced from the respective cache level. |
| * |
| * Insertion can occur at only one, sliding position per cache level. It is |
| * marked by its offset in the data buffer and the index of the first used |
| * entry at or behind that position. If this gap is too small to accommodate |
| * the new item (plus its full key), the insertion window is extended as |
| * described below. The new entry will always be inserted at the bottom end |
| * of the window and since the next used entry is known, properly sorted |
| * insertion is possible. |
| * |
| * To make the cache perform robustly in a wide range of usage scenarios, |
| * L2 uses a randomized variant of LFU (see ensure_data_insertable_l2 for |
| * details). Every item holds a read hit counter and there is a global read |
| * hit counter. The more hits an entry has in relation to the average, the |
| * more it is likely to be kept using a rand()-based condition. The test is |
| * applied only to the entry following the insertion window. If it doesn't |
| * get evicted, it is moved to the begin of that window and the window is |
| * moved. |
| * |
| * Moreover, the entry's hits get halved to make that entry more likely to |
| * be removed the next time the sliding insertion / removal window comes by. |
| * As a result, frequently used entries are likely not to be dropped until |
| * they get not used for a while. Also, even a cache thrashing situation |
| * about 50% of the content survives every 50% of the cache being re-written |
| * with new entries. For details on the fine-tuning involved, see the |
| * comments in ensure_data_insertable_l2(). |
| * |
| * Due to the randomized mapping of keys to entry groups, some groups may |
| * overflow. In that case, there are spare groups that can be chained to |
| * an already used group to extend it. |
| * |
| * To limit the entry size and management overhead, not the actual item keys |
| * but only their hashed "fingerprint" will be stored. These are reasonably |
| * unique to prevent collisions, so we only need to support up to one entry |
| * per entry key. To guarantee that there are no conflicts, however, we |
| * store the actual full key immediately in front of the serialized item |
| * data. That is, the entry offset actually points to the full key and the |
| * key length stored in the entry acts as an additional offset to find the |
| * actual item. |
| * |
| * Most keys are 16 bytes or less. We use the prefix indexes returned by |
| * a prefix_pool_t instance to uniquely identify the prefix in that case. |
| * Then the combination of prefix index and key stored in the fingerprint |
| * is then unique, too, and can never conflict. No full key construction, |
| * storage and comparison is needed in that case. |
| * |
| * All access to the cached data needs to be serialized. Because we want |
| * to scale well despite that bottleneck, we simply segment the cache into |
| * a number of independent caches (segments). Items will be multiplexed based |
| * on their hash key. |
| */ |
| |
| /* APR's read-write lock implementation on Windows is horribly inefficient. |
| * Even with very low contention a runtime overhead of 35% percent has been |
| * measured for 'svn-bench null-export' over ra_serf. |
| * |
| * Use a simple mutex on Windows. Because there is one mutex per segment, |
| * large machines should (and usually can) be configured with large caches |
| * such that read contention is kept low. This is basically the situation |
| * we had before 1.8. |
| */ |
| #ifdef WIN32 |
| # define USE_SIMPLE_MUTEX 1 |
| #else |
| # define USE_SIMPLE_MUTEX 0 |
| #endif |
| |
| /* For more efficient copy operations, let's align all data items properly. |
| * Since we can't portably align pointers, this is rather the item size |
| * granularity which ensures *relative* alignment within the cache - still |
| * giving us decent copy speeds on most machines. |
| * |
| * Must be a power of 2. |
| */ |
| #define ITEM_ALIGNMENT 16 |
| |
| /* By default, don't create cache segments smaller than this value unless |
| * the total cache size itself is smaller. |
| */ |
| #define DEFAULT_MIN_SEGMENT_SIZE APR_UINT64_C(0x2000000) |
| |
| /* The minimum segment size we will allow for multi-segmented caches |
| */ |
| #define MIN_SEGMENT_SIZE APR_UINT64_C(0x10000) |
| |
| /* The maximum number of segments allowed. Larger numbers reduce the size |
| * of each segment, in turn reducing the max size of a cachable item. |
| * Also, each segment gets its own lock object. The actual number supported |
| * by the OS may therefore be lower and svn_cache__membuffer_cache_create |
| * may return an error. |
| */ |
| #define MAX_SEGMENT_COUNT 0x10000 |
| |
| /* As of today, APR won't allocate chunks of 4GB or more. So, limit the |
| * segment size to slightly below that. |
| */ |
| #define MAX_SEGMENT_SIZE APR_UINT64_C(0xffff0000) |
| |
| /* We don't mark the initialization status for every group but initialize |
| * a number of groups at once. That will allow for a very small init flags |
| * vector that is likely to fit into the CPU caches even for fairly large |
| * membuffer caches. For instance, the default of 32 means 8x32 groups per |
| * byte, i.e. 8 flags/byte x 32 groups/flag x 8 entries/group x 40 index |
| * bytes/entry x 8 cache bytes/index byte = 1kB init vector / 640MB cache. |
| */ |
| #define GROUP_INIT_GRANULARITY 32 |
| |
| /* Invalid index reference value. Equivalent to APR_UINT32_T(-1) |
| */ |
| #define NO_INDEX APR_UINT32_MAX |
| |
| /* To save space in our group structure, we only use 32 bit size values |
| * and, therefore, limit the size of each entry to just below 4GB. |
| * Supporting larger items is not a good idea as the data transfer |
| * to and from the cache would block other threads for a very long time. |
| */ |
| #define MAX_ITEM_SIZE ((apr_uint32_t)(0 - ITEM_ALIGNMENT)) |
| |
| /* We use this structure to identify cache entries. There cannot be two |
| * entries with the same entry key. However unlikely, though, two different |
| * full keys (see full_key_t) may have the same entry key. That is a |
| * collision and at most one of them can be stored in the cache at any time. |
| * |
| * If the prefix is shared, which implies that the variable key part is no |
| * longer than 16 bytes, then there is a 1:1 mapping between full key and |
| * entry key. |
| */ |
| typedef struct entry_key_t |
| { |
| /* 16 byte finger print of the full key. */ |
| apr_uint64_t fingerprint[2]; |
| |
| /* Length of the full key. This value is aligned to ITEM_ALIGNMENT to |
| * make sure the subsequent item content is properly aligned. If 0, |
| * PREFIX_KEY is implied to be != NO_INDEX. */ |
| apr_size_t key_len; |
| |
| /* Unique index of the shared key prefix, i.e. it's index within the |
| * prefix pool (see prefix_pool_t). NO_INDEX if the key prefix is not |
| * shared, otherwise KEY_LEN==0 is implied. */ |
| apr_uint32_t prefix_idx; |
| } entry_key_t; |
| |
| /* A full key, i.e. the combination of the cache's key prefix with some |
| * dynamic part appended to it. It also contains its ENTRY_KEY. |
| * |
| * If the ENTRY_KEY has a 1:1 mapping to the FULL_KEY, then the latter |
| * will be empty and remains unused. |
| */ |
| typedef struct full_key_t |
| { |
| /* Reduced form identifying the cache entry (if such an entry exists). */ |
| entry_key_t entry_key; |
| |
| /* If ENTRY_KEY is not a 1:1 mapping of the prefix + dynamic key |
| * combination, then this contains the full combination. Note that the |
| * SIZE element may be larger than ENTRY_KEY.KEY_LEN, but only the latter |
| * determines the valid key size. */ |
| svn_membuf_t full_key; |
| } full_key_t; |
| |
| /* A limited capacity, thread-safe pool of unique C strings. Operations on |
| * this data structure are defined by prefix_pool_* functions. The only |
| * "public" member is VALUES (r/o access only). |
| */ |
| typedef struct prefix_pool_t |
| { |
| /* Map C string to a pointer into VALUES with the same contents. */ |
| apr_hash_t *map; |
| |
| /* Pointer to an array of strings. These are the contents of this pool |
| * and each one of them is referenced by MAP. Valid indexes are 0 to |
| * VALUES_USED - 1. May be NULL if VALUES_MAX is 0. */ |
| const char **values; |
| |
| /* Number of used entries that VALUES may have. */ |
| apr_uint32_t values_max; |
| |
| /* Number of used entries in VALUES. Never exceeds VALUES_MAX. */ |
| apr_uint32_t values_used; |
| |
| /* Maximum number of bytes to allocate. */ |
| apr_size_t bytes_max; |
| |
| /* Number of bytes currently allocated. Should not exceed BYTES_MAX but |
| * the implementation may . */ |
| apr_size_t bytes_used; |
| |
| /* The serialization object. */ |
| svn_mutex__t *mutex; |
| } prefix_pool_t; |
| |
| /* Set *PREFIX_POOL to a new instance that tries to limit allocation to |
| * BYTES_MAX bytes. If MUTEX_REQUIRED is set and multi-threading is |
| * supported, serialize all access to the new instance. Allocate the |
| * object from *RESULT_POOL. */ |
| static svn_error_t * |
| prefix_pool_create(prefix_pool_t **prefix_pool, |
| apr_size_t bytes_max, |
| svn_boolean_t mutex_required, |
| apr_pool_t *result_pool) |
| { |
| enum |
| { |
| /* With 56 byes of overhead under 64 bits, we will probably never get |
| * substantially below this. If we accidentally do, we will simply |
| * run out of entries in the VALUES array before running out of |
| * allocated memory. */ |
| ESTIMATED_BYTES_PER_ENTRY = 120 |
| }; |
| |
| /* Number of entries we are going to support. */ |
| apr_size_t capacity = MIN(APR_UINT32_MAX, |
| bytes_max / ESTIMATED_BYTES_PER_ENTRY); |
| |
| /* Construct the result struct. */ |
| prefix_pool_t *result = apr_pcalloc(result_pool, sizeof(*result)); |
| result->map = svn_hash__make(result_pool); |
| |
| result->values = capacity |
| ? apr_pcalloc(result_pool, capacity * sizeof(const char *)) |
| : NULL; |
| result->values_max = (apr_uint32_t)capacity; |
| result->values_used = 0; |
| |
| result->bytes_max = bytes_max; |
| result->bytes_used = capacity * sizeof(svn_membuf_t); |
| |
| SVN_ERR(svn_mutex__init(&result->mutex, mutex_required, result_pool)); |
| |
| /* Done. */ |
| *prefix_pool = result; |
| return SVN_NO_ERROR; |
| } |
| |
| /* Set *PREFIX_IDX to the offset in PREFIX_POOL->VALUES that contains the |
| * value PREFIX. If none exists, auto-insert it. If we can't due to |
| * capacity exhaustion, set *PREFIX_IDX to NO_INDEX. |
| * To be called by prefix_pool_get() only. */ |
| static svn_error_t * |
| prefix_pool_get_internal(apr_uint32_t *prefix_idx, |
| prefix_pool_t *prefix_pool, |
| const char *prefix) |
| { |
| enum |
| { |
| /* Size of an hash entry plus (max.) APR alignment loss. |
| * |
| * This may be slightly off if e.g. APR changes its internal data |
| * structures but that will translate in just a few percent (~10%) |
| * over-allocation. Memory consumption will still be capped. |
| */ |
| OVERHEAD = 40 + 8 |
| }; |
| |
| const char **value; |
| apr_size_t prefix_len = strlen(prefix); |
| apr_size_t bytes_needed; |
| apr_pool_t *pool; |
| |
| /* Lookup. If we already know that prefix, return its index. */ |
| value = apr_hash_get(prefix_pool->map, prefix, prefix_len); |
| if (value != NULL) |
| { |
| const apr_size_t idx = value - prefix_pool->values; |
| SVN_ERR_ASSERT(idx < prefix_pool->values_used); |
| *prefix_idx = (apr_uint32_t) idx; |
| return SVN_NO_ERROR; |
| } |
| |
| /* Capacity checks. */ |
| if (prefix_pool->values_used == prefix_pool->values_max) |
| { |
| *prefix_idx = NO_INDEX; |
| return SVN_NO_ERROR; |
| } |
| |
| bytes_needed = prefix_len + 1 + OVERHEAD; |
| assert(prefix_pool->bytes_max >= prefix_pool->bytes_used); |
| if (prefix_pool->bytes_max - prefix_pool->bytes_used < bytes_needed) |
| { |
| *prefix_idx = NO_INDEX; |
| return SVN_NO_ERROR; |
| } |
| |
| /* Add new entry. */ |
| pool = apr_hash_pool_get(prefix_pool->map); |
| |
| value = &prefix_pool->values[prefix_pool->values_used]; |
| *value = apr_pstrndup(pool, prefix, prefix_len + 1); |
| apr_hash_set(prefix_pool->map, *value, prefix_len, value); |
| |
| *prefix_idx = prefix_pool->values_used; |
| ++prefix_pool->values_used; |
| prefix_pool->bytes_used += bytes_needed; |
| |
| return SVN_NO_ERROR; |
| } |
| |
| /* Thread-safe wrapper around prefix_pool_get_internal. */ |
| static svn_error_t * |
| prefix_pool_get(apr_uint32_t *prefix_idx, |
| prefix_pool_t *prefix_pool, |
| const char *prefix) |
| { |
| SVN_MUTEX__WITH_LOCK(prefix_pool->mutex, |
| prefix_pool_get_internal(prefix_idx, prefix_pool, |
| prefix)); |
| |
| return SVN_NO_ERROR; |
| } |
| |
| /* Debugging / corruption detection support. |
| * If you define this macro, the getter functions will performed expensive |
| * checks on the item data, requested keys and entry types. If there is |
| * a mismatch found in any of them when being compared with the values |
| * remembered in the setter function, an error will be returned. |
| */ |
| #ifdef SVN_DEBUG_CACHE_MEMBUFFER |
| |
| /* The prefix passed to svn_cache__create_membuffer_cache() effectively |
| * defines the type of all items stored by that cache instance. We'll take |
| * the last 15 bytes + \0 as plaintext for easy identification by the dev. |
| */ |
| #define PREFIX_TAIL_LEN 16 |
| |
| /* This record will be attached to any cache entry. It tracks item data |
| * (content), key and type as hash values and is the baseline against which |
| * the getters will compare their results to detect inconsistencies. |
| */ |
| typedef struct entry_tag_t |
| { |
| /* MD5 checksum over the serialized item data. |
| */ |
| unsigned char content_hash[APR_MD5_DIGESTSIZE]; |
| |
| /* Hash value of the svn_cache_t instance that wrote the item |
| * (i.e. a combination of type and repository) |
| */ |
| unsigned char prefix_hash[APR_MD5_DIGESTSIZE]; |
| |
| /* Note that this only covers the variable part of the key, |
| * i.e. it will be different from the full key hash used for |
| * cache indexing. |
| */ |
| unsigned char key_hash[APR_MD5_DIGESTSIZE]; |
| |
| /* Last letters from of the key in human readable format |
| * (ends with the type identifier, e.g. "DAG") |
| */ |
| char prefix_tail[PREFIX_TAIL_LEN]; |
| |
| /* Length of the variable key part. |
| */ |
| apr_size_t key_len; |
| |
| } entry_tag_t; |
| |
| /* Initialize all members of TAG except for the content hash. |
| */ |
| static svn_error_t *store_key_part(entry_tag_t *tag, |
| const char *prefix, |
| const void *key, |
| apr_size_t key_len, |
| apr_pool_t *scratch_pool) |
| { |
| svn_checksum_t *checksum; |
| apr_size_t prefix_len = strlen(prefix); |
| |
| if (prefix_len > sizeof(tag->prefix_tail)) |
| { |
| prefix += prefix_len - (sizeof(tag->prefix_tail) - 1); |
| prefix_len = sizeof(tag->prefix_tail) - 1; |
| } |
| |
| SVN_ERR(svn_checksum(&checksum, |
| svn_checksum_md5, |
| prefix, |
| strlen(prefix), |
| scratch_pool)); |
| memcpy(tag->prefix_hash, checksum->digest, sizeof(tag->prefix_hash)); |
| |
| SVN_ERR(svn_checksum(&checksum, |
| svn_checksum_md5, |
| key, |
| key_len, |
| scratch_pool)); |
| memcpy(tag->key_hash, checksum->digest, sizeof(tag->key_hash)); |
| |
| memset(tag->prefix_tail, 0, sizeof(tag->key_hash)); |
| memcpy(tag->prefix_tail, prefix, prefix_len + 1); |
| |
| tag->key_len = key_len; |
| |
| return SVN_NO_ERROR; |
| } |
| |
| /* Initialize the content hash member of TAG. |
| */ |
| static svn_error_t* store_content_part(entry_tag_t *tag, |
| const void *data, |
| apr_size_t size, |
| apr_pool_t *pool) |
| { |
| svn_checksum_t *checksum; |
| SVN_ERR(svn_checksum(&checksum, |
| svn_checksum_md5, |
| data, |
| size, |
| pool)); |
| |
| memcpy(tag->content_hash, checksum->digest, sizeof(tag->content_hash)); |
| |
| return SVN_NO_ERROR; |
| } |
| |
| /* Compare two tags and fail with an assertion upon differences. |
| */ |
| static svn_error_t* assert_equal_tags(const entry_tag_t *lhs, |
| const entry_tag_t *rhs) |
| { |
| SVN_ERR_ASSERT(memcmp(lhs->content_hash, rhs->content_hash, |
| sizeof(lhs->content_hash)) == 0); |
| SVN_ERR_ASSERT(memcmp(lhs->prefix_hash, rhs->prefix_hash, |
| sizeof(lhs->prefix_hash)) == 0); |
| SVN_ERR_ASSERT(memcmp(lhs->key_hash, rhs->key_hash, |
| sizeof(lhs->key_hash)) == 0); |
| SVN_ERR_ASSERT(memcmp(lhs->prefix_tail, rhs->prefix_tail, |
| sizeof(lhs->prefix_tail)) == 0); |
| |
| SVN_ERR_ASSERT(lhs->key_len == rhs->key_len); |
| |
| return SVN_NO_ERROR; |
| } |
| |
| /* Reoccurring code snippets. |
| */ |
| |
| #define DEBUG_CACHE_MEMBUFFER_TAG_ARG entry_tag_t *tag, |
| |
| #define DEBUG_CACHE_MEMBUFFER_TAG tag, |
| |
| #define DEBUG_CACHE_MEMBUFFER_INIT_TAG(pool) \ |
| entry_tag_t _tag; \ |
| entry_tag_t *tag = &_tag; \ |
| if (key) \ |
| SVN_ERR(store_key_part(tag, \ |
| get_prefix_key(cache), \ |
| key, \ |
| cache->key_len == APR_HASH_KEY_STRING \ |
| ? strlen((const char *) key) \ |
| : cache->key_len, \ |
| pool)); |
| |
| #else |
| |
| /* Don't generate any checks if consistency checks have not been enabled. |
| */ |
| #define DEBUG_CACHE_MEMBUFFER_TAG_ARG |
| #define DEBUG_CACHE_MEMBUFFER_TAG |
| #define DEBUG_CACHE_MEMBUFFER_INIT_TAG(pool) |
| |
| #endif /* SVN_DEBUG_CACHE_MEMBUFFER */ |
| |
| /* A single dictionary entry. Since all entries will be allocated once |
| * during cache creation, those entries might be either used or unused. |
| * An entry is used if and only if it is contained in the doubly-linked |
| * list of used entries per cache level. |
| */ |
| typedef struct entry_t |
| { |
| /* Identifying the data item. Only valid for used entries. |
| */ |
| entry_key_t key; |
| |
| /* The offset of the cached item's serialized data within the caches |
| * DATA buffer. |
| */ |
| apr_uint64_t offset; |
| |
| /* Size of the serialized item data. May be 0. The MAX_ITEM_SIZE macro |
| * above ensures that there will be no overflows. |
| * Only valid for used entries. |
| */ |
| apr_size_t size; |
| |
| /* Number of (read) hits for this entry. Will be reset upon write. |
| * Only valid for used entries. |
| */ |
| svn_atomic_t hit_count; |
| |
| /* Reference to the next used entry in the order defined by offset. |
| * NO_INDEX indicates the end of the list; this entry must be referenced |
| * by the caches cache_level_t.last member. NO_INDEX also implies that |
| * the data buffer is not used beyond offset+size. |
| * Only valid for used entries. |
| */ |
| apr_uint32_t next; |
| |
| /* Reference to the previous used entry in the order defined by offset. |
| * NO_INDEX indicates the end of the list; this entry must be referenced |
| * by the caches cache_level_t.first member. |
| * Only valid for used entries. |
| */ |
| apr_uint32_t previous; |
| |
| /* Priority of this entry. This entry will not be replaced by lower- |
| * priority items. |
| */ |
| apr_uint32_t priority; |
| #ifdef SVN_DEBUG_CACHE_MEMBUFFER |
| /* Remember type, content and key hashes. |
| */ |
| entry_tag_t tag; |
| #endif |
| } entry_t; |
| |
| /* Group header struct. |
| */ |
| typedef struct group_header_t |
| { |
| /* number of entries used [0 .. USED-1] */ |
| apr_uint32_t used; |
| |
| /* next group in the chain or NO_INDEX for the last. |
| * For recycleable unused spare groups, this points to the next |
| * unused spare group */ |
| apr_uint32_t next; |
| |
| /* previously group in the chain or NO_INDEX for the first */ |
| apr_uint32_t previous; |
| |
| /* number of elements in the chain from start to here. |
| * >= 1 for used groups, 0 for unused spare groups */ |
| apr_uint32_t chain_length; |
| |
| } group_header_t; |
| |
| /* The size of the group struct should be a power of two make sure it does |
| * not cross memory page boundaries. Since we already access the cache |
| * randomly, having two page table lookups instead of one is bad. |
| */ |
| #define GROUP_BLOCK_SIZE 512 |
| |
| /* A ~10-way associative cache seems to be a good compromise between |
| * performance (worst-case lookups) and efficiency-loss due to collisions. |
| * |
| * This value may be changed to any positive integer. |
| */ |
| #define GROUP_SIZE \ |
| ((GROUP_BLOCK_SIZE - sizeof(group_header_t)) / sizeof(entry_t)) |
| |
| /* Maximum number of groups in a chain, i.e. a cache index group can hold |
| * up to GROUP_SIZE * MAX_GROUP_CHAIN_LENGTH entries. |
| */ |
| #define MAX_GROUP_CHAIN_LENGTH 8 |
| |
| /* We group dictionary entries to make this GROUP-SIZE-way associative. |
| */ |
| typedef struct entry_group_t |
| { |
| /* group globals */ |
| group_header_t header; |
| |
| /* padding and also room for future extensions */ |
| char padding[GROUP_BLOCK_SIZE - sizeof(group_header_t) |
| - sizeof(entry_t) * GROUP_SIZE]; |
| |
| /* the actual entries */ |
| entry_t entries[GROUP_SIZE]; |
| |
| } entry_group_t; |
| |
| /* Per-cache level header structure. Instances of this are members of |
| * svn_membuffer_t and will use non-overlapping sections of its DATA buffer. |
| * All offset values are global / absolute to that whole buffer. |
| */ |
| typedef struct cache_level_t |
| { |
| /* Reference to the first (defined by the order content in the data |
| * buffer) dictionary entry used by any data item. |
| * NO_INDEX for an empty cache. |
| */ |
| apr_uint32_t first; |
| |
| /* Reference to the last (defined by the order content in the data |
| * buffer) dictionary entry used by any data item. |
| * NO_INDEX for an empty cache. |
| */ |
| apr_uint32_t last; |
| |
| /* Reference to the first (defined by the order content in the data |
| * buffer) used dictionary entry behind the insertion position |
| * (current_data). If NO_INDEX, the data buffer is free starting at the |
| * current_data offset. |
| */ |
| apr_uint32_t next; |
| |
| |
| /* First offset in the caches DATA buffer that belongs to this level. |
| */ |
| apr_uint64_t start_offset; |
| |
| /* Size of data buffer allocated to this level in bytes. Must be > 0. |
| */ |
| apr_uint64_t size; |
| |
| /* Offset in the data buffer where the next insertion shall occur. |
| */ |
| apr_uint64_t current_data; |
| |
| } cache_level_t; |
| |
| /* The cache header structure. |
| */ |
| struct svn_membuffer_t |
| { |
| /* Number of cache segments. Must be a power of 2. |
| Please note that this structure represents only one such segment |
| and that all segments must / will report the same values here. */ |
| apr_uint32_t segment_count; |
| |
| /* Collection of prefixes shared among all instances accessing the |
| * same membuffer cache backend. If a prefix is contained in this |
| * pool then all cache instances using an equal prefix must actually |
| * use the one stored in this pool. */ |
| prefix_pool_t *prefix_pool; |
| |
| /* The dictionary, GROUP_SIZE * (group_count + spare_group_count) |
| * entries long. Never NULL. |
| */ |
| entry_group_t *directory; |
| |
| /* Flag array with group_count / GROUP_INIT_GRANULARITY _bit_ elements. |
| * Allows for efficiently marking groups as "not initialized". |
| */ |
| unsigned char *group_initialized; |
| |
| /* Size of dictionary in groups. Must be > 0. |
| */ |
| apr_uint32_t group_count; |
| |
| /* Total number of spare groups. |
| */ |
| apr_uint32_t spare_group_count; |
| |
| /* First recycleable spare group. |
| */ |
| apr_uint32_t first_spare_group; |
| |
| /* Maximum number of spare groups ever used. I.e. group index |
| * group_count + max_spare_used is the first unused spare group |
| * if first_spare_group is NO_INDEX. |
| */ |
| apr_uint32_t max_spare_used; |
| |
| /* Pointer to the data buffer, data_size bytes long. Never NULL. |
| */ |
| unsigned char *data; |
| |
| /* Total number of data buffer bytes in use. |
| */ |
| apr_uint64_t data_used; |
| |
| /* Largest entry size that we would accept. For total cache sizes |
| * less than 4TB (sic!), this is determined by the total cache size. |
| */ |
| apr_uint64_t max_entry_size; |
| |
| /* The cache levels, organized as sub-buffers. Since entries in the |
| * DIRECTORY use offsets in DATA for addressing, a cache lookup does |
| * not need to know the cache level of a specific item. Cache levels |
| * are only used to implement a hybrid insertion / eviction strategy. |
| */ |
| |
| /* First cache level, i.e. most insertions happen here. Very large |
| * items might get inserted directly into L2. L1 is a strict FIFO |
| * ring buffer that does not care about item priorities. All evicted |
| * items get a chance to be promoted to L2. |
| */ |
| cache_level_t l1; |
| |
| /* Second cache level, i.e. data evicted from L1 will be added here |
| * if the item is "important" enough or the L2 insertion window is large |
| * enough. |
| */ |
| cache_level_t l2; |
| |
| |
| /* Number of used dictionary entries, i.e. number of cached items. |
| * Purely statistical information that may be used for profiling only. |
| * Updates are not synchronized and values may be nonsensicle on some |
| * platforms. |
| */ |
| apr_uint32_t used_entries; |
| |
| /* Total number of calls to membuffer_cache_get. |
| * Purely statistical information that may be used for profiling only. |
| * Updates are not synchronized and values may be nonsensicle on some |
| * platforms. |
| */ |
| apr_uint64_t total_reads; |
| |
| /* Total number of calls to membuffer_cache_set. |
| * Purely statistical information that may be used for profiling only. |
| * Updates are not synchronized and values may be nonsensicle on some |
| * platforms. |
| */ |
| apr_uint64_t total_writes; |
| |
| /* Total number of hits since the cache's creation. |
| * Purely statistical information that may be used for profiling only. |
| * Updates are not synchronized and values may be nonsensicle on some |
| * platforms. |
| */ |
| apr_uint64_t total_hits; |
| |
| #if (APR_HAS_THREADS && USE_SIMPLE_MUTEX) |
| /* A lock for intra-process synchronization to the cache, or NULL if |
| * the cache's creator doesn't feel the cache needs to be |
| * thread-safe. |
| */ |
| svn_mutex__t *lock; |
| #elif (APR_HAS_THREADS && !USE_SIMPLE_MUTEX) |
| /* Same for read-write lock. */ |
| apr_thread_rwlock_t *lock; |
| |
| /* If set, write access will wait until they get exclusive access. |
| * Otherwise, they will become no-ops if the segment is currently |
| * read-locked. Only used when LOCK is an r/w lock. |
| */ |
| svn_boolean_t allow_blocking_writes; |
| #endif |
| |
| /* A write lock counter, must be either 0 or 1. |
| * This one is only used in debug assertions to verify that you used |
| * the correct multi-threading settings. */ |
| svn_atomic_t write_lock_count; |
| }; |
| |
| /* Align integer VALUE to the next ITEM_ALIGNMENT boundary. |
| */ |
| #define ALIGN_VALUE(value) (((value) + ITEM_ALIGNMENT-1) & -ITEM_ALIGNMENT) |
| |
| /* If locking is supported for CACHE, acquire a read lock for it. |
| */ |
| static svn_error_t * |
| read_lock_cache(svn_membuffer_t *cache) |
| { |
| #if (APR_HAS_THREADS && USE_SIMPLE_MUTEX) |
| return svn_mutex__lock(cache->lock); |
| #elif (APR_HAS_THREADS && !USE_SIMPLE_MUTEX) |
| if (cache->lock) |
| { |
| apr_status_t status = apr_thread_rwlock_rdlock(cache->lock); |
| if (status) |
| return svn_error_wrap_apr(status, _("Can't lock cache mutex")); |
| } |
| |
| return SVN_NO_ERROR; |
| #else |
| return SVN_NO_ERROR; |
| #endif |
| } |
| |
| /* If locking is supported for CACHE, acquire a write lock for it. |
| * Set *SUCCESS to FALSE, if we couldn't acquire the write lock; |
| * leave it untouched otherwise. |
| */ |
| static svn_error_t * |
| write_lock_cache(svn_membuffer_t *cache, svn_boolean_t *success) |
| { |
| #if (APR_HAS_THREADS && USE_SIMPLE_MUTEX) |
| return svn_mutex__lock(cache->lock); |
| #elif (APR_HAS_THREADS && !USE_SIMPLE_MUTEX) |
| if (cache->lock) |
| { |
| apr_status_t status; |
| if (cache->allow_blocking_writes) |
| { |
| status = apr_thread_rwlock_wrlock(cache->lock); |
| } |
| else |
| { |
| status = apr_thread_rwlock_trywrlock(cache->lock); |
| if (SVN_LOCK_IS_BUSY(status)) |
| { |
| *success = FALSE; |
| status = APR_SUCCESS; |
| } |
| } |
| |
| if (status) |
| return svn_error_wrap_apr(status, |
| _("Can't write-lock cache mutex")); |
| } |
| |
| return SVN_NO_ERROR; |
| #else |
| return SVN_NO_ERROR; |
| #endif |
| } |
| |
| /* If locking is supported for CACHE, acquire an unconditional write lock |
| * for it. |
| */ |
| static svn_error_t * |
| force_write_lock_cache(svn_membuffer_t *cache) |
| { |
| #if (APR_HAS_THREADS && USE_SIMPLE_MUTEX) |
| return svn_mutex__lock(cache->lock); |
| #elif (APR_HAS_THREADS && !USE_SIMPLE_MUTEX) |
| apr_status_t status = apr_thread_rwlock_wrlock(cache->lock); |
| if (status) |
| return svn_error_wrap_apr(status, |
| _("Can't write-lock cache mutex")); |
| |
| return SVN_NO_ERROR; |
| #else |
| return SVN_NO_ERROR; |
| #endif |
| } |
| |
| /* If locking is supported for CACHE, release the current lock |
| * (read or write). Return ERR upon success. |
| */ |
| static svn_error_t * |
| unlock_cache(svn_membuffer_t *cache, svn_error_t *err) |
| { |
| #if (APR_HAS_THREADS && USE_SIMPLE_MUTEX) |
| return svn_mutex__unlock(cache->lock, err); |
| #elif (APR_HAS_THREADS && !USE_SIMPLE_MUTEX) |
| if (cache->lock) |
| { |
| apr_status_t status = apr_thread_rwlock_unlock(cache->lock); |
| if (err) |
| return err; |
| |
| if (status) |
| return svn_error_wrap_apr(status, _("Can't unlock cache mutex")); |
| } |
| |
| return err; |
| #else |
| return err; |
| #endif |
| } |
| |
| /* If supported, guard the execution of EXPR with a read lock to CACHE. |
| * The macro has been modeled after SVN_MUTEX__WITH_LOCK. |
| */ |
| #define WITH_READ_LOCK(cache, expr) \ |
| do { \ |
| SVN_ERR(read_lock_cache(cache)); \ |
| SVN_ERR(unlock_cache(cache, (expr))); \ |
| } while (0) |
| |
| /* If supported, guard the execution of EXPR with a write lock to CACHE. |
| * The macro has been modeled after SVN_MUTEX__WITH_LOCK. |
| * |
| * The write lock process is complicated if we don't allow to wait for |
| * the lock: If we didn't get the lock, we may still need to remove an |
| * existing entry for the given key because that content is now stale. |
| * Once we discovered such an entry, we unconditionally do a blocking |
| * wait for the write lock. In case no old content could be found, a |
| * failing lock attempt is simply a no-op and we exit the macro. |
| */ |
| #define WITH_WRITE_LOCK(cache, expr) \ |
| do { \ |
| svn_boolean_t got_lock = TRUE; \ |
| SVN_ERR(write_lock_cache(cache, &got_lock)); \ |
| if (!got_lock) \ |
| { \ |
| svn_boolean_t exists; \ |
| SVN_ERR(entry_exists(cache, group_index, key, &exists)); \ |
| if (exists) \ |
| SVN_ERR(force_write_lock_cache(cache)); \ |
| else \ |
| break; \ |
| } \ |
| SVN_ERR(unlock_cache(cache, (expr))); \ |
| } while (0) |
| |
| /* Returns 0 if the entry group identified by GROUP_INDEX in CACHE has not |
| * been initialized, yet. In that case, this group can not data. Otherwise, |
| * a non-zero value is returned. |
| */ |
| static APR_INLINE unsigned char |
| is_group_initialized(svn_membuffer_t *cache, apr_uint32_t group_index) |
| { |
| unsigned char flags |
| = cache->group_initialized[group_index / (8 * GROUP_INIT_GRANULARITY)]; |
| unsigned char bit_mask |
| = (unsigned char)(1 << ((group_index / GROUP_INIT_GRANULARITY) % 8)); |
| |
| return flags & bit_mask; |
| } |
| |
| /* Initializes the section of the directory in CACHE that contains |
| * the entry group identified by GROUP_INDEX. */ |
| static void |
| initialize_group(svn_membuffer_t *cache, apr_uint32_t group_index) |
| { |
| unsigned char bit_mask; |
| apr_uint32_t i; |
| |
| /* range of groups to initialize due to GROUP_INIT_GRANULARITY */ |
| apr_uint32_t first_index = |
| (group_index / GROUP_INIT_GRANULARITY) * GROUP_INIT_GRANULARITY; |
| apr_uint32_t last_index = first_index + GROUP_INIT_GRANULARITY; |
| if (last_index > cache->group_count + cache->spare_group_count) |
| last_index = cache->group_count + cache->spare_group_count; |
| |
| for (i = first_index; i < last_index; ++i) |
| { |
| group_header_t *header = &cache->directory[i].header; |
| header->used = 0; |
| header->chain_length = 1; |
| header->next = NO_INDEX; |
| header->previous = NO_INDEX; |
| } |
| |
| /* set the "initialized" bit for these groups */ |
| bit_mask |
| = (unsigned char)(1 << ((group_index / GROUP_INIT_GRANULARITY) % 8)); |
| cache->group_initialized[group_index / (8 * GROUP_INIT_GRANULARITY)] |
| |= bit_mask; |
| } |
| |
| /* Return the next available spare group from CACHE and mark it as used. |
| * May return NULL. |
| */ |
| static entry_group_t * |
| allocate_spare_group(svn_membuffer_t *cache) |
| { |
| entry_group_t *group = NULL; |
| |
| /* is there some ready-to-use group? */ |
| if (cache->first_spare_group != NO_INDEX) |
| { |
| group = &cache->directory[cache->first_spare_group]; |
| cache->first_spare_group = group->header.next; |
| } |
| |
| /* any so far untouched spares available? */ |
| else if (cache->max_spare_used < cache->spare_group_count) |
| { |
| apr_uint32_t group_index = cache->group_count + cache->max_spare_used; |
| ++cache->max_spare_used; |
| |
| if (!is_group_initialized(cache, group_index)) |
| initialize_group(cache, group_index); |
| |
| group = &cache->directory[group_index]; |
| } |
| |
| /* spare groups must be empty */ |
| assert(!group || !group->header.used); |
| return group; |
| } |
| |
| /* Mark previously allocated spare group GROUP in CACHE as "unused". |
| */ |
| static void |
| free_spare_group(svn_membuffer_t *cache, |
| entry_group_t *group) |
| { |
| assert(group->header.used == 0); |
| assert(group->header.previous != NO_INDEX); |
| assert(group - cache->directory >= (apr_ssize_t)cache->group_count); |
| |
| /* unchain */ |
| cache->directory[group->header.previous].header.next = NO_INDEX; |
| group->header.chain_length = 0; |
| group->header.previous = NO_INDEX; |
| |
| /* add to chain of spares */ |
| group->header.next = cache->first_spare_group; |
| cache->first_spare_group = (apr_uint32_t) (group - cache->directory); |
| } |
| |
| /* Follow the group chain from GROUP in CACHE to its end and return the last |
| * group. May return GROUP. |
| */ |
| static entry_group_t * |
| last_group_in_chain(svn_membuffer_t *cache, |
| entry_group_t *group) |
| { |
| while (group->header.next != NO_INDEX) |
| group = &cache->directory[group->header.next]; |
| |
| return group; |
| } |
| |
| /* Return the CHAIN_INDEX-th element in the group chain starting from group |
| * START_GROUP_INDEX in CACHE. |
| */ |
| static entry_group_t * |
| get_group(svn_membuffer_t *cache, |
| apr_uint32_t start_group_index, |
| apr_uint32_t chain_index) |
| { |
| entry_group_t *group = &cache->directory[start_group_index]; |
| for (; chain_index; --chain_index) |
| group = &cache->directory[group->header.next]; |
| |
| return group; |
| } |
| |
| /* Resolve a dictionary entry reference, i.e. return the entry |
| * for the given IDX. |
| */ |
| static APR_INLINE entry_t * |
| get_entry(svn_membuffer_t *cache, apr_uint32_t idx) |
| { |
| return &cache->directory[idx / GROUP_SIZE].entries[idx % GROUP_SIZE]; |
| } |
| |
| /* Get the entry references for the given ENTRY. |
| */ |
| static APR_INLINE apr_uint32_t |
| get_index(svn_membuffer_t *cache, entry_t *entry) |
| { |
| apr_size_t group_index |
| = ((char *)entry - (char *)cache->directory) / sizeof(entry_group_t); |
| |
| return (apr_uint32_t)group_index * GROUP_SIZE |
| + (apr_uint32_t)(entry - cache->directory[group_index].entries); |
| } |
| |
| /* Return the cache level of ENTRY in CACHE. |
| */ |
| static cache_level_t * |
| get_cache_level(svn_membuffer_t *cache, entry_t *entry) |
| { |
| return entry->offset < cache->l1.size ? &cache->l1 |
| : &cache->l2; |
| } |
| |
| /* Insert ENTRY to the chain of items that belong to LEVEL in CACHE. IDX |
| * is ENTRY's item index and is only given for efficiency. The insertion |
| * takes place just before LEVEL->NEXT. *CACHE will not be modified. |
| */ |
| static void |
| chain_entry(svn_membuffer_t *cache, |
| cache_level_t *level, |
| entry_t *entry, |
| apr_uint32_t idx) |
| { |
| /* insert ENTRY before this item */ |
| entry_t *next = level->next == NO_INDEX |
| ? NULL |
| : get_entry(cache, level->next); |
| assert(idx == get_index(cache, entry)); |
| |
| /* update entry chain |
| */ |
| entry->next = level->next; |
| if (level->first == NO_INDEX) |
| { |
| /* insert as the first entry and only in the chain |
| */ |
| entry->previous = NO_INDEX; |
| level->last = idx; |
| level->first = idx; |
| } |
| else if (next == NULL) |
| { |
| /* insert as the last entry in the chain. |
| * Note that it cannot also be at the beginning of the chain. |
| */ |
| entry->previous = level->last; |
| get_entry(cache, level->last)->next = idx; |
| level->last = idx; |
| } |
| else |
| { |
| /* insert either at the start of a non-empty list or |
| * somewhere in the middle |
| */ |
| entry->previous = next->previous; |
| next->previous = idx; |
| |
| if (entry->previous != NO_INDEX) |
| get_entry(cache, entry->previous)->next = idx; |
| else |
| level->first = idx; |
| } |
| } |
| |
| /* Remove ENTRY from the chain of items that belong to LEVEL in CACHE. IDX |
| * is ENTRY's item index and is only given for efficiency. Please note |
| * that neither *CACHE nor *ENTRY will not be modified. |
| */ |
| static void |
| unchain_entry(svn_membuffer_t *cache, |
| cache_level_t *level, |
| entry_t *entry, |
| apr_uint32_t idx) |
| { |
| assert(idx == get_index(cache, entry)); |
| |
| /* update |
| */ |
| if (level->next == idx) |
| level->next = entry->next; |
| |
| /* unlink it from the chain of used entries |
| */ |
| if (entry->previous == NO_INDEX) |
| level->first = entry->next; |
| else |
| get_entry(cache, entry->previous)->next = entry->next; |
| |
| if (entry->next == NO_INDEX) |
| level->last = entry->previous; |
| else |
| get_entry(cache, entry->next)->previous = entry->previous; |
| } |
| |
| /* Remove the used ENTRY from the CACHE, i.e. make it "unused". |
| * In contrast to insertion, removal is possible for any entry. |
| */ |
| static void |
| drop_entry(svn_membuffer_t *cache, entry_t *entry) |
| { |
| /* the group that ENTRY belongs to plus a number of useful index values |
| */ |
| apr_uint32_t idx = get_index(cache, entry); |
| apr_uint32_t group_index = idx / GROUP_SIZE; |
| entry_group_t *last_group |
| = last_group_in_chain(cache, &cache->directory[group_index]); |
| apr_uint32_t last_in_group |
| = (apr_uint32_t) ((last_group - cache->directory) * GROUP_SIZE |
| + last_group->header.used - 1); |
| |
| cache_level_t *level = get_cache_level(cache, entry); |
| |
| /* update global cache usage counters |
| */ |
| cache->used_entries--; |
| cache->data_used -= entry->size; |
| |
| /* extend the insertion window, if the entry happens to border it |
| */ |
| if (idx == level->next) |
| level->next = entry->next; |
| else |
| if (entry->next == level->next) |
| { |
| /* insertion window starts right behind the entry to remove |
| */ |
| if (entry->previous == NO_INDEX) |
| { |
| /* remove the first entry -> insertion may start at pos 0, now */ |
| level->current_data = level->start_offset; |
| } |
| else |
| { |
| /* insertion may start right behind the previous entry */ |
| entry_t *previous = get_entry(cache, entry->previous); |
| level->current_data = ALIGN_VALUE( previous->offset |
| + previous->size); |
| } |
| } |
| |
| /* unlink it from the chain of used entries |
| */ |
| unchain_entry(cache, level, entry, idx); |
| |
| /* Move last entry into hole (if the removed one is not the last used). |
| * We need to do this since all used entries are at the beginning of |
| * the group's entries array. |
| */ |
| if (idx != last_in_group) |
| { |
| /* copy the last used entry to the removed entry's index |
| */ |
| *entry = last_group->entries[last_group->header.used-1]; |
| |
| /* this ENTRY may belong to a different cache level than the entry |
| * we have just removed */ |
| level = get_cache_level(cache, entry); |
| |
| /* update foreign links to new index |
| */ |
| if (last_in_group == level->next) |
| level->next = idx; |
| |
| if (entry->previous == NO_INDEX) |
| level->first = idx; |
| else |
| get_entry(cache, entry->previous)->next = idx; |
| |
| if (entry->next == NO_INDEX) |
| level->last = idx; |
| else |
| get_entry(cache, entry->next)->previous = idx; |
| } |
| |
| /* Update the number of used entries. |
| */ |
| last_group->header.used--; |
| |
| /* Release the last group in the chain if it is a spare group |
| */ |
| if (!last_group->header.used && last_group->header.previous != NO_INDEX) |
| free_spare_group(cache, last_group); |
| } |
| |
| /* Insert ENTRY into the chain of used dictionary entries. The entry's |
| * offset and size members must already have been initialized. Also, |
| * the offset must match the beginning of the insertion window. |
| */ |
| static void |
| insert_entry(svn_membuffer_t *cache, entry_t *entry) |
| { |
| /* the group that ENTRY belongs to plus a number of useful index values |
| */ |
| apr_uint32_t idx = get_index(cache, entry); |
| apr_uint32_t group_index = idx / GROUP_SIZE; |
| entry_group_t *group = &cache->directory[group_index]; |
| cache_level_t *level = get_cache_level(cache, entry); |
| |
| /* The entry must start at the beginning of the insertion window. |
| * It must also be the first unused entry in the group. |
| */ |
| assert(entry->offset == level->current_data); |
| assert(idx == group_index * GROUP_SIZE + group->header.used); |
| level->current_data = ALIGN_VALUE(entry->offset + entry->size); |
| |
| /* update usage counters |
| */ |
| cache->used_entries++; |
| cache->data_used += entry->size; |
| entry->hit_count = 0; |
| group->header.used++; |
| |
| /* update entry chain |
| */ |
| chain_entry(cache, level, entry, idx); |
| |
| /* The current insertion position must never point outside our |
| * data buffer. |
| */ |
| assert(level->current_data <= level->start_offset + level->size); |
| } |
| |
| /* Map a KEY of 16 bytes to the CACHE and group that shall contain the |
| * respective item. |
| */ |
| static apr_uint32_t |
| get_group_index(svn_membuffer_t **cache, |
| const entry_key_t *key) |
| { |
| svn_membuffer_t *segment0 = *cache; |
| apr_uint64_t key0 = key->fingerprint[0]; |
| apr_uint64_t key1 = key->fingerprint[1]; |
| |
| /* select the cache segment to use. they have all the same group_count. |
| * Since key may not be well-distributed, pre-fold it to a smaller but |
| * "denser" ranger. The modulus is a prime larger than the largest |
| * counts. */ |
| *cache = &segment0[(key1 % APR_UINT64_C(2809637) + (key0 / 37)) |
| & (segment0->segment_count - 1)]; |
| return (key0 % APR_UINT64_C(5030895599)) % segment0->group_count; |
| } |
| |
| /* Reduce the hit count of ENTRY and update the accumulated hit info |
| * in CACHE accordingly. |
| */ |
| static APR_INLINE void |
| let_entry_age(svn_membuffer_t *cache, entry_t *entry) |
| { |
| apr_uint32_t hits_removed = (entry->hit_count + 1) >> 1; |
| |
| if (hits_removed) |
| { |
| entry->hit_count -= hits_removed; |
| } |
| else |
| { |
| entry->priority /= 2; |
| } |
| } |
| |
| /* Return whether the keys in LHS and RHS match. |
| */ |
| static svn_boolean_t |
| entry_keys_match(const entry_key_t *lhs, |
| const entry_key_t *rhs) |
| { |
| return (lhs->fingerprint[0] == rhs->fingerprint[0]) |
| && (lhs->fingerprint[1] == rhs->fingerprint[1]) |
| && (lhs->prefix_idx == rhs->prefix_idx) |
| && (lhs->key_len == rhs->key_len); |
| } |
| |
| /* Given the GROUP_INDEX that shall contain an entry with the hash key |
| * TO_FIND, find that entry in the specified group. |
| * |
| * If FIND_EMPTY is not set, this function will return the one used entry |
| * that actually matches the hash or NULL, if no such entry exists. |
| * |
| * If FIND_EMPTY has been set, this function will drop the one used entry |
| * that actually matches the hash (i.e. make it fit to be replaced with |
| * new content), an unused entry or a forcibly removed entry (if all |
| * group entries are currently in use). The entries' hash value will be |
| * initialized with TO_FIND. |
| * |
| * Note: This function requires the caller to appropriately lock the CACHE. |
| * For FIND_EMPTY==FALSE, a read lock is required, for FIND_EMPTY==TRUE, |
| * the write lock must have been acquired. |
| */ |
| static entry_t * |
| find_entry(svn_membuffer_t *cache, |
| apr_uint32_t group_index, |
| const full_key_t *to_find, |
| svn_boolean_t find_empty) |
| { |
| entry_group_t *group; |
| entry_t *entry = NULL; |
| apr_size_t i; |
| |
| /* get the group that *must* contain the entry |
| */ |
| group = &cache->directory[group_index]; |
| |
| /* If the entry group has not been initialized, yet, there is no data. |
| */ |
| if (! is_group_initialized(cache, group_index)) |
| { |
| if (find_empty) |
| { |
| initialize_group(cache, group_index); |
| entry = &group->entries[0]; |
| |
| /* initialize entry for the new key */ |
| entry->key = to_find->entry_key; |
| } |
| |
| return entry; |
| } |
| |
| /* try to find the matching entry |
| */ |
| while (1) |
| { |
| for (i = 0; i < group->header.used; ++i) |
| if (entry_keys_match(&group->entries[i].key, &to_find->entry_key)) |
| { |
| /* This is the only entry that _may_ contain the correct data. */ |
| entry = &group->entries[i]; |
| |
| /* If we want to preserve it, check that it is actual a match. */ |
| if (!find_empty) |
| { |
| /* If the full key is fully defined in prefix_id & mangeled |
| * key, we are done. */ |
| if (!entry->key.key_len) |
| return entry; |
| |
| /* Compare the full key. */ |
| if (memcmp(to_find->full_key.data, |
| cache->data + entry->offset, |
| entry->key.key_len) == 0) |
| return entry; |
| |
| /* Key conflict. The entry to find cannot be anywhere else. |
| * Therefore, it is not cached. */ |
| return NULL; |
| } |
| |
| /* need to empty that entry */ |
| drop_entry(cache, entry); |
| if (group->header.used == GROUP_SIZE) |
| group = last_group_in_chain(cache, group); |
| else if (group->header.chain_length == 0) |
| group = last_group_in_chain(cache, |
| &cache->directory[group_index]); |
| |
| /* No entry found (actually, none left to find). */ |
| entry = NULL; |
| break; |
| } |
| |
| /* end of chain? */ |
| if (group->header.next == NO_INDEX) |
| break; |
| |
| /* only full groups may chain */ |
| assert(group->header.used == GROUP_SIZE); |
| group = &cache->directory[group->header.next]; |
| } |
| |
| /* None found. Are we looking for a free entry? |
| */ |
| if (find_empty) |
| { |
| /* There is no empty entry in the chain, try chaining a spare group. |
| */ |
| if ( group->header.used == GROUP_SIZE |
| && group->header.chain_length < MAX_GROUP_CHAIN_LENGTH) |
| { |
| entry_group_t *new_group = allocate_spare_group(cache); |
| if (new_group) |
| { |
| /* chain groups |
| */ |
| new_group->header.chain_length = group->header.chain_length + 1; |
| new_group->header.previous = (apr_uint32_t) (group - |
| cache->directory); |
| new_group->header.next = NO_INDEX; |
| group->header.next = (apr_uint32_t) (new_group - |
| cache->directory); |
| group = new_group; |
| } |
| } |
| |
| /* if GROUP is still filled, we need to remove a random entry */ |
| if (group->header.used == GROUP_SIZE) |
| { |
| /* every entry gets the same chance of being removed. |
| * Otherwise, we free the first entry, fill it and |
| * remove it again on the next occasion without considering |
| * the other entries in this group. |
| * |
| * We hit only one random group instead of processing all |
| * groups in the chain. |
| */ |
| cache_level_t *entry_level; |
| int to_remove = rand() % (GROUP_SIZE * group->header.chain_length); |
| entry_group_t *to_shrink |
| = get_group(cache, group_index, to_remove / GROUP_SIZE); |
| |
| entry = &to_shrink->entries[to_remove % GROUP_SIZE]; |
| entry_level = get_cache_level(cache, entry); |
| for (i = 0; i < GROUP_SIZE; ++i) |
| { |
| /* keep L1 entries whenever possible */ |
| |
| cache_level_t *level |
| = get_cache_level(cache, &to_shrink->entries[i]); |
| if ( (level != entry_level && entry_level == &cache->l1) |
| || (entry->hit_count > to_shrink->entries[i].hit_count)) |
| { |
| entry_level = level; |
| entry = &to_shrink->entries[i]; |
| } |
| } |
| |
| /* for the entries that don't have been removed, |
| * reduce their hit counts to put them at a relative |
| * disadvantage the next time. |
| */ |
| for (i = 0; i < GROUP_SIZE; ++i) |
| if (entry != &to_shrink->entries[i]) |
| let_entry_age(cache, &to_shrink->entries[i]); |
| |
| drop_entry(cache, entry); |
| } |
| |
| /* initialize entry for the new key |
| */ |
| entry = &group->entries[group->header.used]; |
| entry->key = to_find->entry_key; |
| } |
| |
| return entry; |
| } |
| |
| /* Move a surviving ENTRY from just behind the insertion window to |
| * its beginning and move the insertion window up accordingly. |
| */ |
| static void |
| move_entry(svn_membuffer_t *cache, entry_t *entry) |
| { |
| apr_size_t size = ALIGN_VALUE(entry->size); |
| cache_level_t *level = get_cache_level(cache, entry); |
| |
| /* This entry survived this cleansing run. Reset half of its |
| * hit count so that its removal gets more likely in the next |
| * run unless someone read / hit this entry in the meantime. |
| */ |
| let_entry_age(cache, entry); |
| |
| /* Move the entry to the start of the empty / insertion section |
| * (if it isn't there already). Size-aligned moves are legal |
| * since all offsets and block sizes share this same alignment. |
| * Size-aligned moves tend to be faster than non-aligned ones |
| * because no "odd" bytes at the end need to special treatment. |
| */ |
| if (entry->offset != level->current_data) |
| { |
| memmove(cache->data + level->current_data, |
| cache->data + entry->offset, |
| size); |
| entry->offset = level->current_data; |
| } |
| |
| /* The insertion position is now directly behind this entry. |
| */ |
| level->current_data = entry->offset + size; |
| level->next = entry->next; |
| |
| /* The current insertion position must never point outside our |
| * data buffer. |
| */ |
| assert(level->current_data <= level->start_offset + level->size); |
| } |
| |
| /* Move ENTRY in CACHE from L1 to L2. |
| */ |
| static void |
| promote_entry(svn_membuffer_t *cache, entry_t *entry) |
| { |
| apr_uint32_t idx = get_index(cache, entry); |
| apr_size_t size = ALIGN_VALUE(entry->size); |
| assert(get_cache_level(cache, entry) == &cache->l1); |
| assert(idx == cache->l1.next); |
| |
| /* copy item from the current location in L1 to the start of L2's |
| * insertion window */ |
| memmove(cache->data + cache->l2.current_data, |
| cache->data + entry->offset, |
| size); |
| entry->offset = cache->l2.current_data; |
| |
| /* The insertion position is now directly behind this entry. |
| */ |
| cache->l2.current_data += size; |
| |
| /* remove ENTRY from chain of L1 entries and put it into L2 |
| */ |
| unchain_entry(cache, &cache->l1, entry, idx); |
| chain_entry(cache, &cache->l2, entry, idx); |
| } |
| |
| /* This function implements the cache insertion / eviction strategy for L2. |
| * |
| * If necessary, enlarge the insertion window of CACHE->L2 until it is at |
| * least TO_FIT_IN->SIZE bytes long. TO_FIT_IN->SIZE must not exceed the |
| * data buffer size allocated to CACHE->L2. IDX is the item index of |
| * TO_FIT_IN and is given for performance reasons. |
| * |
| * Return TRUE if enough room could be found or made. A FALSE result |
| * indicates that the respective item shall not be added. |
| */ |
| static svn_boolean_t |
| ensure_data_insertable_l2(svn_membuffer_t *cache, |
| entry_t *to_fit_in) |
| { |
| entry_t *entry; |
| |
| /* accumulated size of the entries that have been removed to make |
| * room for the new one. |
| */ |
| apr_uint64_t moved_size = 0; |
| |
| /* count the number of entries that got moved. A single large entry |
| * being moved is not enough to reject an insertion. |
| */ |
| apr_size_t moved_count = 0; |
| |
| /* accumulated "worth" of items dropped so far */ |
| apr_uint64_t drop_hits = 0; |
| |
| /* estimated "worth" of the new entry */ |
| apr_uint64_t drop_hits_limit = (to_fit_in->hit_count + 1) |
| * (apr_uint64_t)to_fit_in->priority; |
| |
| /* This loop will eventually terminate because every cache entry |
| * would get dropped eventually: |
| * |
| * - the incoming entry is small enough to fit into L2 |
| * - every iteration either frees parts of L2 or counts the moved size |
| * - eventually, we either moved too many items with too much total size |
| * to accept the new entry, or made enough room in L2 for the new entry |
| * |
| * Low-prio items get rejected even sooner. |
| */ |
| while (1) |
| { |
| /* first offset behind the insertion window |
| */ |
| apr_uint64_t end = cache->l2.next == NO_INDEX |
| ? cache->l2.start_offset + cache->l2.size |
| : get_entry(cache, cache->l2.next)->offset; |
| |
| /* leave function as soon as the insertion window is large enough |
| */ |
| if (end - cache->l2.current_data >= to_fit_in->size) |
| return TRUE; |
| |
| /* Don't be too eager to cache data. If a lot of data has been moved |
| * around, the current item has probably a relatively low priority. |
| * We must also limit the effort spent here (even in case of faulty |
| * heuristics). Therefore, give up after some time. |
| */ |
| if (moved_size / 4 > to_fit_in->size && moved_count > 7) |
| return FALSE; |
| |
| /* if the net worth (in weighted hits) of items removed is already |
| * larger than what we want to insert, reject TO_FIT_IN because it |
| * still does not fit in. */ |
| if (drop_hits > drop_hits_limit) |
| return FALSE; |
| |
| /* try to enlarge the insertion window |
| */ |
| if (cache->l2.next == NO_INDEX) |
| { |
| /* We reached the end of the data buffer; restart at the beginning. |
| * Due to the randomized nature of our LFU implementation, very |
| * large data items may require multiple passes. Therefore, SIZE |
| * should be restricted to significantly less than data_size. |
| */ |
| cache->l2.current_data = cache->l2.start_offset; |
| cache->l2.next = cache->l2.first; |
| } |
| else |
| { |
| svn_boolean_t keep; |
| entry = get_entry(cache, cache->l2.next); |
| |
| if (to_fit_in->priority < SVN_CACHE__MEMBUFFER_DEFAULT_PRIORITY) |
| { |
| /* Low prio items can only be accepted only if the current |
| * entry is of even lower prio and has fewer hits. |
| */ |
| if ( entry->priority > to_fit_in->priority |
| || entry->hit_count > to_fit_in->hit_count) |
| return FALSE; |
| } |
| |
| if (entry->priority <= SVN_CACHE__MEMBUFFER_LOW_PRIORITY) |
| { |
| /* Be quick to remove low-prio entries - even if the incoming |
| * one is low-prio as well. This makes room for more important |
| * data and replaces existing data with newly read information. |
| */ |
| keep = FALSE; |
| } |
| else |
| { |
| /* If the existing data is the same prio as the incoming data, |
| * drop the existing entry if it had seen fewer (probably 0) |
| * hits than the entry coming in from L1. In case of different |
| * priorities, keep the current entry of it has higher prio. |
| * The new entry may still find room by ousting other entries. |
| */ |
| keep = to_fit_in->priority == entry->priority |
| ? entry->hit_count >= to_fit_in->hit_count |
| : entry->priority > to_fit_in->priority; |
| } |
| |
| /* keepers or destroyers? */ |
| if (keep) |
| { |
| /* Moving entries around is not for free -> track costs. */ |
| moved_size += entry->size; |
| moved_count++; |
| |
| move_entry(cache, entry); |
| } |
| else |
| { |
| /* Drop the entry from the end of the insertion window. |
| * Count the "hit importance" such that we are not sacrificing |
| * too much of the high-hit contents. However, don't count |
| * low-priority hits because higher prio entries will often |
| * provide the same data but in a further stage of processing. |
| */ |
| if (entry->priority > SVN_CACHE__MEMBUFFER_LOW_PRIORITY) |
| drop_hits += entry->hit_count * (apr_uint64_t)entry->priority; |
| |
| drop_entry(cache, entry); |
| } |
| } |
| } |
| |
| /* This will never be reached. But if it was, "can't insert" was the |
| * right answer. */ |
| } |
| |
| /* This function implements the cache insertion / eviction strategy for L1. |
| * |
| * If necessary, enlarge the insertion window of CACHE->L1 by promoting |
| * entries to L2 until it is at least SIZE bytes long. |
| * |
| * Return TRUE if enough room could be found or made. A FALSE result |
| * indicates that the respective item shall not be added because it is |
| * too large. |
| */ |
| static svn_boolean_t |
| ensure_data_insertable_l1(svn_membuffer_t *cache, apr_size_t size) |
| { |
| /* Guarantees that the while loop will terminate. */ |
| if (size > cache->l1.size) |
| return FALSE; |
| |
| /* This loop will eventually terminate because every cache entry |
| * would get dropped eventually. |
| */ |
| while (1) |
| { |
| /* first offset behind the insertion window |
| */ |
| apr_uint32_t entry_index = cache->l1.next; |
| entry_t *entry = get_entry(cache, entry_index); |
| apr_uint64_t end = cache->l1.next == NO_INDEX |
| ? cache->l1.start_offset + cache->l1.size |
| : entry->offset; |
| |
| /* leave function as soon as the insertion window is large enough |
| */ |
| if (end - cache->l1.current_data >= size) |
| return TRUE; |
| |
| /* Enlarge the insertion window |
| */ |
| if (cache->l1.next == NO_INDEX) |
| { |
| /* We reached the end of the data buffer; restart at the beginning. |
| * Due to the randomized nature of our LFU implementation, very |
| * large data items may require multiple passes. Therefore, SIZE |
| * should be restricted to significantly less than data_size. |
| */ |
| cache->l1.current_data = cache->l1.start_offset; |
| cache->l1.next = cache->l1.first; |
| } |
| else |
| { |
| /* Remove the entry from the end of insertion window and promote |
| * it to L2, if it is important enough. |
| */ |
| svn_boolean_t keep = ensure_data_insertable_l2(cache, entry); |
| |
| /* We might have touched the group that contains ENTRY. Recheck. */ |
| if (entry_index == cache->l1.next) |
| { |
| if (keep) |
| promote_entry(cache, entry); |
| else |
| drop_entry(cache, entry); |
| } |
| } |
| } |
| |
| /* This will never be reached. But if it was, "can't insert" was the |
| * right answer. */ |
| } |
| |
| svn_error_t * |
| svn_cache__membuffer_cache_create(svn_membuffer_t **cache, |
| apr_size_t total_size, |
| apr_size_t directory_size, |
| apr_size_t segment_count, |
| svn_boolean_t thread_safe, |
| svn_boolean_t allow_blocking_writes, |
| apr_pool_t *pool) |
| { |
| svn_membuffer_t *c; |
| prefix_pool_t *prefix_pool; |
| |
| apr_uint32_t seg; |
| apr_uint32_t group_count; |
| apr_uint32_t main_group_count; |
| apr_uint32_t spare_group_count; |
| apr_uint32_t group_init_size; |
| apr_uint64_t data_size; |
| apr_uint64_t max_entry_size; |
| |
| /* Allocate 1% of the cache capacity to the prefix string pool. |
| */ |
| SVN_ERR(prefix_pool_create(&prefix_pool, total_size / 100, thread_safe, |
| pool)); |
| total_size -= total_size / 100; |
| |
| /* Limit the total size (only relevant if we can address > 4GB) |
| */ |
| #if APR_SIZEOF_VOIDP > 4 |
| if (total_size > MAX_SEGMENT_SIZE * MAX_SEGMENT_COUNT) |
| total_size = MAX_SEGMENT_SIZE * MAX_SEGMENT_COUNT; |
| #endif |
| |
| /* Limit the segment count |
| */ |
| if (segment_count > MAX_SEGMENT_COUNT) |
| segment_count = MAX_SEGMENT_COUNT; |
| if (segment_count * MIN_SEGMENT_SIZE > total_size) |
| segment_count = total_size / MIN_SEGMENT_SIZE; |
| |
| /* The segment count must be a power of two. Round it down as necessary. |
| */ |
| while ((segment_count & (segment_count-1)) != 0) |
| segment_count &= segment_count-1; |
| |
| /* if the caller hasn't provided a reasonable segment count or the above |
| * limitations set it to 0, derive one from the absolute cache size |
| */ |
| if (segment_count < 1) |
| { |
| /* Determine a reasonable number of cache segments. Segmentation is |
| * only useful for multi-threaded / multi-core servers as it reduces |
| * lock contention on these systems. |
| * |
| * But on these systems, we can assume that ample memory has been |
| * allocated to this cache. Smaller caches should not be segmented |
| * as this severely limits the maximum size of cachable items. |
| * |
| * Segments should not be smaller than 32MB and max. cachable item |
| * size should grow as fast as segmentation. |
| */ |
| |
| apr_uint32_t segment_count_shift = 0; |
| while (((2 * DEFAULT_MIN_SEGMENT_SIZE) << (2 * segment_count_shift)) |
| < total_size) |
| ++segment_count_shift; |
| |
| segment_count = (apr_size_t)1 << segment_count_shift; |
| } |
| |
| /* If we have an extremely large cache (>512 GB), the default segment |
| * size may exceed the amount allocatable as one chunk. In that case, |
| * increase segmentation until we are under the threshold. |
| */ |
| while ( total_size / segment_count > MAX_SEGMENT_SIZE |
| && segment_count < MAX_SEGMENT_COUNT) |
| segment_count *= 2; |
| |
| /* allocate cache as an array of segments / cache objects */ |
| c = apr_palloc(pool, segment_count * sizeof(*c)); |
| |
| /* Split total cache size into segments of equal size |
| */ |
| total_size /= segment_count; |
| directory_size /= segment_count; |
| |
| /* prevent pathological conditions: ensure a certain minimum cache size |
| */ |
| if (total_size < 2 * sizeof(entry_group_t)) |
| total_size = 2 * sizeof(entry_group_t); |
| |
| /* adapt the dictionary size accordingly, if necessary: |
| * It must hold at least one group and must not exceed the cache size. |
| */ |
| if (directory_size > total_size - sizeof(entry_group_t)) |
| directory_size = total_size - sizeof(entry_group_t); |
| if (directory_size < 2 * sizeof(entry_group_t)) |
| directory_size = 2 * sizeof(entry_group_t); |
| |
| /* limit the data size to what we can address. |
| * Note that this cannot overflow since all values are of size_t. |
| * Also, make it a multiple of the item placement granularity to |
| * prevent subtle overflows. |
| */ |
| data_size = ALIGN_VALUE(total_size - directory_size + 1) - ITEM_ALIGNMENT; |
| |
| /* For cache sizes > 16TB, individual cache segments will be larger |
| * than 32GB allowing for >4GB entries. But caching chunks larger |
| * than 4GB are simply not supported. |
| */ |
| max_entry_size = data_size / 8 > MAX_ITEM_SIZE |
| ? MAX_ITEM_SIZE |
| : data_size / 8; |
| |
| /* to keep the entries small, we use 32 bit indexes only |
| * -> we need to ensure that no more than 4G entries exist. |
| * |
| * Note, that this limit could only be exceeded in a very |
| * theoretical setup with about 1EB of cache. |
| */ |
| group_count = directory_size / sizeof(entry_group_t) |
| >= (APR_UINT32_MAX / GROUP_SIZE) |
| ? (APR_UINT32_MAX / GROUP_SIZE) - 1 |
| : (apr_uint32_t)(directory_size / sizeof(entry_group_t)); |
| |
| /* set some of the index directory aside as over-flow (spare) buffers */ |
| spare_group_count = MAX(group_count / 4, 1); |
| main_group_count = group_count - spare_group_count; |
| assert(spare_group_count > 0 && main_group_count > 0); |
| |
| group_init_size = 1 + group_count / (8 * GROUP_INIT_GRANULARITY); |
| for (seg = 0; seg < segment_count; ++seg) |
| { |
| /* allocate buffers and initialize cache members |
| */ |
| c[seg].segment_count = (apr_uint32_t)segment_count; |
| c[seg].prefix_pool = prefix_pool; |
| |
| c[seg].group_count = main_group_count; |
| c[seg].spare_group_count = spare_group_count; |
| c[seg].first_spare_group = NO_INDEX; |
| c[seg].max_spare_used = 0; |
| |
| /* Allocate but don't clear / zero the directory because it would add |
| significantly to the server start-up time if the caches are large. |
| Group initialization will take care of that in stead. */ |
| c[seg].directory = apr_palloc(pool, |
| group_count * sizeof(entry_group_t)); |
| |
| /* Allocate and initialize directory entries as "not initialized", |
| hence "unused" */ |
| c[seg].group_initialized = apr_pcalloc(pool, group_init_size); |
| |
| /* Allocate 1/4th of the data buffer to L1 |
| */ |
| c[seg].l1.first = NO_INDEX; |
| c[seg].l1.last = NO_INDEX; |
| c[seg].l1.next = NO_INDEX; |
| c[seg].l1.start_offset = 0; |
| c[seg].l1.size = ALIGN_VALUE(data_size / 4); |
| c[seg].l1.current_data = 0; |
| |
| /* The remaining 3/4th will be used as L2 |
| */ |
| c[seg].l2.first = NO_INDEX; |
| c[seg].l2.last = NO_INDEX; |
| c[seg].l2.next = NO_INDEX; |
| c[seg].l2.start_offset = c[seg].l1.size; |
| c[seg].l2.size = ALIGN_VALUE(data_size) - c[seg].l1.size; |
| c[seg].l2.current_data = c[seg].l2.start_offset; |
| |
| /* This cast is safe because DATA_SIZE <= MAX_SEGMENT_SIZE. */ |
| c[seg].data = apr_palloc(pool, (apr_size_t)ALIGN_VALUE(data_size)); |
| c[seg].data_used = 0; |
| c[seg].max_entry_size = max_entry_size; |
| |
| c[seg].used_entries = 0; |
| c[seg].total_reads = 0; |
| c[seg].total_writes = 0; |
| c[seg].total_hits = 0; |
| |
| /* were allocations successful? |
| * If not, initialize a minimal cache structure. |
| */ |
| if (c[seg].data == NULL || c[seg].directory == NULL) |
| { |
| /* We are OOM. There is no need to proceed with "half a cache". |
| */ |
| return svn_error_wrap_apr(APR_ENOMEM, "OOM"); |
| } |
| |
| #if (APR_HAS_THREADS && USE_SIMPLE_MUTEX) |
| /* A lock for intra-process synchronization to the cache, or NULL if |
| * the cache's creator doesn't feel the cache needs to be |
| * thread-safe. |
| */ |
| SVN_ERR(svn_mutex__init(&c[seg].lock, thread_safe, pool)); |
| #elif (APR_HAS_THREADS && !USE_SIMPLE_MUTEX) |
| /* Same for read-write lock. */ |
| c[seg].lock = NULL; |
| if (thread_safe) |
| { |
| apr_status_t status = |
| apr_thread_rwlock_create(&(c[seg].lock), pool); |
| if (status) |
| return svn_error_wrap_apr(status, _("Can't create cache mutex")); |
| } |
| |
| /* Select the behavior of write operations. |
| */ |
| c[seg].allow_blocking_writes = allow_blocking_writes; |
| #endif |
| /* No writers at the moment. */ |
| c[seg].write_lock_count = 0; |
| } |
| |
| /* done here |
| */ |
| *cache = c; |
| return SVN_NO_ERROR; |
| } |
| |
| svn_error_t * |
| svn_cache__membuffer_clear(svn_membuffer_t *cache) |
| { |
| apr_size_t seg; |
| apr_size_t segment_count = cache->segment_count; |
| |
| /* Length of the group_initialized array in bytes. |
| See also svn_cache__membuffer_cache_create(). */ |
| apr_size_t group_init_size |
| = 1 + (cache->group_count + cache->spare_group_count) |
| / (8 * GROUP_INIT_GRANULARITY); |
| |
| /* Clear segment by segment. This implies that other thread may read |
| and write to other segments after we cleared them and before the |
| last segment is done. |
| |
| However, that is no different from a write request coming through |
| right after we cleared all segments because dependencies between |
| cache entries (recursive lookup / access locks) are not allowed. |
| */ |
| for (seg = 0; seg < segment_count; ++seg) |
| { |
| /* Unconditionally acquire the write lock. */ |
| SVN_ERR(force_write_lock_cache(&cache[seg])); |
| |
| /* Mark all groups as "not initialized", which implies "empty". */ |
| cache[seg].first_spare_group = NO_INDEX; |
| cache[seg].max_spare_used = 0; |
| |
| memset(cache[seg].group_initialized, 0, group_init_size); |
| |
| /* Unlink L1 contents. */ |
| cache[seg].l1.first = NO_INDEX; |
| cache[seg].l1.last = NO_INDEX; |
| cache[seg].l1.next = NO_INDEX; |
| cache[seg].l1.current_data = cache[seg].l1.start_offset; |
| |
| /* Unlink L2 contents. */ |
| cache[seg].l2.first = NO_INDEX; |
| cache[seg].l2.last = NO_INDEX; |
| cache[seg].l2.next = NO_INDEX; |
| cache[seg].l2.current_data = cache[seg].l2.start_offset; |
| |
| /* Reset content counters. */ |
| cache[seg].data_used = 0; |
| cache[seg].used_entries = 0; |
| |
| /* Segment may be used again. */ |
| SVN_ERR(unlock_cache(&cache[seg], SVN_NO_ERROR)); |
| } |
| |
| /* done here */ |
| return SVN_NO_ERROR; |
| } |
| |
| /* Look for the cache entry in group GROUP_INDEX of CACHE, identified |
| * by the hash value TO_FIND and set *FOUND accordingly. |
| * |
| * Note: This function requires the caller to serialize access. |
| * Don't call it directly, call entry_exists instead. |
| */ |
| static svn_error_t * |
| entry_exists_internal(svn_membuffer_t *cache, |
| apr_uint32_t group_index, |
| const full_key_t *to_find, |
| svn_boolean_t *found) |
| { |
| *found = find_entry(cache, group_index, to_find, FALSE) != NULL; |
| return SVN_NO_ERROR; |
| } |
| |
| /* Look for the cache entry in group GROUP_INDEX of CACHE, identified |
| * by the hash value TO_FIND and set *FOUND accordingly. |
| */ |
| static svn_error_t * |
| entry_exists(svn_membuffer_t *cache, |
| apr_uint32_t group_index, |
| const full_key_t *to_find, |
| svn_boolean_t *found) |
| { |
| WITH_READ_LOCK(cache, |
| entry_exists_internal(cache, |
| group_index, |
| to_find, |
| found)); |
| |
| return SVN_NO_ERROR; |
| } |
| |
| /* Given the SIZE and PRIORITY of a new item, return the cache level |
| (L1 or L2) in fragment CACHE that this item shall be inserted into. |
| If we can't find nor make enough room for the item, return NULL. |
| */ |
| static cache_level_t * |
| select_level(svn_membuffer_t *cache, |
| apr_size_t size, |
| apr_uint32_t priority) |
| { |
| if (cache->max_entry_size >= size) |
| { |
| /* Small items go into L1. */ |
| return ensure_data_insertable_l1(cache, size) |
| ? &cache->l1 |
| : NULL; |
| } |
| else if ( cache->l2.size >= size |
| && MAX_ITEM_SIZE >= size |
| && priority > SVN_CACHE__MEMBUFFER_DEFAULT_PRIORITY) |
| { |
| /* Large but important items go into L2. */ |
| entry_t dummy_entry = { { { 0 } } }; |
| dummy_entry.priority = priority; |
| dummy_entry.size = size; |
| |
| return ensure_data_insertable_l2(cache, &dummy_entry) |
| ? &cache->l2 |
| : NULL; |
| } |
| |
| /* Don't cache large, unimportant items. */ |
| return NULL; |
| } |
| |
| /* Try to insert the serialized item given in BUFFER with ITEM_SIZE |
| * into the group GROUP_INDEX of CACHE and uniquely identify it by |
| * hash value TO_FIND. |
| * |
| * However, there is no guarantee that it will actually be put into |
| * the cache. If there is already some data associated with TO_FIND, |
| * it will be removed from the cache even if the new data cannot |
| * be inserted. |
| * |
| * Note: This function requires the caller to serialization access. |
| * Don't call it directly, call membuffer_cache_set instead. |
| */ |
| static svn_error_t * |
| membuffer_cache_set_internal(svn_membuffer_t *cache, |
| const full_key_t *to_find, |
| apr_uint32_t group_index, |
| char *buffer, |
| apr_size_t item_size, |
| apr_uint32_t priority, |
| DEBUG_CACHE_MEMBUFFER_TAG_ARG |
| apr_pool_t *scratch_pool) |
| { |
| cache_level_t *level; |
| apr_size_t size; |
| |
| /* first, look for a previous entry for the given key */ |
| entry_t *entry = find_entry(cache, group_index, to_find, FALSE); |
| |
| /* If this one fails, you are using multiple threads but created the |
| * membuffer in single-threaded mode. */ |
| assert(0 == svn_atomic_inc(&cache->write_lock_count)); |
| |
| /* Quick check make sure arithmetics will work further down the road. */ |
| size = item_size + to_find->entry_key.key_len; |
| if (size < item_size) |
| { |
| /* Arithmetic overflow, so combination of serialized ITEM and KEY |
| * cannot not fit into the cache. Setting BUFFER to NULL will cause |
| * the removal of any entry if that exists without writing new data. */ |
| buffer = NULL; |
| } |
| |
| /* if there is an old version of that entry and the new data fits into |
| * the old spot, just re-use that space. */ |
| if (entry && buffer && ALIGN_VALUE(entry->size) >= size) |
| { |
| /* Careful! We need to cast SIZE to the full width of CACHE->DATA_USED |
| * lest we run into trouble with 32 bit underflow *not* treated as a |
| * negative value. |
| */ |
| cache->data_used += (apr_uint64_t)size - entry->size; |
| entry->size = size; |
| entry->priority = priority; |
| |
| #ifdef SVN_DEBUG_CACHE_MEMBUFFER |
| |
| /* Remember original content, type and key (hashes) |
| */ |
| SVN_ERR(store_content_part(tag, buffer, item_size, scratch_pool)); |
| memcpy(&entry->tag, tag, sizeof(*tag)); |
| |
| #endif |
| |
| if (entry->key.key_len) |
| memcpy(cache->data + entry->offset, to_find->full_key.data, |
| entry->key.key_len); |
| if (item_size) |
| memcpy(cache->data + entry->offset + entry->key.key_len, buffer, |
| item_size); |
| |
| cache->total_writes++; |
| |
| /* Putting the decrement into an assert() to make it disappear |
| * in production code. */ |
| assert(0 == svn_atomic_dec(&cache->write_lock_count)); |
| return SVN_NO_ERROR; |
| } |
| |
| /* if necessary, enlarge the insertion window. |
| */ |
| level = buffer ? select_level(cache, size, priority) : NULL; |
| if (level) |
| { |
| /* Remove old data for this key, if that exists. |
| * Get an unused entry for the key and and initialize it with |
| * the serialized item's (future) position within data buffer. |
| */ |
| entry = find_entry(cache, group_index, to_find, TRUE); |
| entry->size = size; |
| entry->offset = level->current_data; |
| entry->priority = priority; |
| |
| #ifdef SVN_DEBUG_CACHE_MEMBUFFER |
| |
| /* Remember original content, type and key (hashes) |
| */ |
| SVN_ERR(store_content_part(tag, buffer, item_size, scratch_pool)); |
| memcpy(&entry->tag, tag, sizeof(*tag)); |
| |
| #endif |
| |
| /* Link the entry properly. |
| */ |
| insert_entry(cache, entry); |
| |
| /* Copy the serialized item data into the cache. |
| */ |
| if (entry->key.key_len) |
| memcpy(cache->data + entry->offset, to_find->full_key.data, |
| entry->key.key_len); |
| if (item_size) |
| memcpy(cache->data + entry->offset + entry->key.key_len, buffer, |
| item_size); |
| |
| cache->total_writes++; |
| } |
| else |
| { |
| /* if there is already an entry for this key, drop it. |
| * Since ensure_data_insertable may have removed entries from |
| * ENTRY's group, re-do the lookup. |
| */ |
| entry = find_entry(cache, group_index, to_find, FALSE); |
| if (entry) |
| drop_entry(cache, entry); |
| } |
| |
| /* Putting the decrement into an assert() to make it disappear |
| * in production code. */ |
| assert(0 == svn_atomic_dec(&cache->write_lock_count)); |
| return SVN_NO_ERROR; |
| } |
| |
| /* Try to insert the ITEM and use the KEY to uniquely identify it. |
| * However, there is no guarantee that it will actually be put into |
| * the cache. If there is already some data associated to the KEY, |
| * it will be removed from the cache even if the new data cannot |
| * be inserted. |
| * |
| * The SERIALIZER is called to transform the ITEM into a single, |
| * flat data buffer. Temporary allocations may be done in POOL. |
| */ |
| static svn_error_t * |
| membuffer_cache_set(svn_membuffer_t *cache, |
| const full_key_t *key, |
| void *item, |
| svn_cache__serialize_func_t serializer, |
| apr_uint32_t priority, |
| DEBUG_CACHE_MEMBUFFER_TAG_ARG |
| apr_pool_t *scratch_pool) |
| { |
| apr_uint32_t group_index; |
| void *buffer = NULL; |
| apr_size_t size = 0; |
| |
| /* find the entry group that will hold the key. |
| */ |
| group_index = get_group_index(&cache, &key->entry_key); |
| |
| /* Serialize data data. |
| */ |
| if (item) |
| SVN_ERR(serializer(&buffer, &size, item, scratch_pool)); |
| |
| /* The actual cache data access needs to sync'ed |
| */ |
| WITH_WRITE_LOCK(cache, |
| membuffer_cache_set_internal(cache, |
| key, |
| group_index, |
| buffer, |
| size, |
| priority, |
| DEBUG_CACHE_MEMBUFFER_TAG |
| scratch_pool)); |
| return SVN_NO_ERROR; |
| } |
| |
| /* Count a hit in ENTRY within CACHE. |
| */ |
| static void |
| increment_hit_counters(svn_membuffer_t *cache, entry_t *entry) |
| { |
| /* To minimize the memory footprint of the cache index, we limit local |
| * hit counters to 32 bits. These may overflow but we don't really |
| * care because at worst, ENTRY will be dropped from cache once every |
| * few billion hits. */ |
| svn_atomic_inc(&entry->hit_count); |
| |
| /* That one is for stats only. */ |
| cache->total_hits++; |
| } |
| |
| /* Look for the cache entry in group GROUP_INDEX of CACHE, identified |
| * by the hash value TO_FIND. If no item has been stored for KEY, |
| * *BUFFER will be NULL. Otherwise, return a copy of the serialized |
| * data in *BUFFER and return its size in *ITEM_SIZE. Allocations will |
| * be done in POOL. |
| * |
| * Note: This function requires the caller to serialization access. |
| * Don't call it directly, call membuffer_cache_get instead. |
| */ |
| static svn_error_t * |
| membuffer_cache_get_internal(svn_membuffer_t *cache, |
| apr_uint32_t group_index, |
| const full_key_t *to_find, |
| char **buffer, |
| apr_size_t *item_size, |
| DEBUG_CACHE_MEMBUFFER_TAG_ARG |
| apr_pool_t *result_pool) |
| { |
| entry_t *entry; |
| apr_size_t size; |
| |
| /* The actual cache data access needs to sync'ed |
| */ |
| entry = find_entry(cache, group_index, to_find, FALSE); |
| cache->total_reads++; |
| if (entry == NULL) |
| { |
| /* no such entry found. |
| */ |
| *buffer = NULL; |
| *item_size = 0; |
| |
| return SVN_NO_ERROR; |
| } |
| |
| size = ALIGN_VALUE(entry->size) - entry->key.key_len; |
| *buffer = apr_palloc(result_pool, size); |
| memcpy(*buffer, cache->data + entry->offset + entry->key.key_len, size); |
| |
| #ifdef SVN_DEBUG_CACHE_MEMBUFFER |
| |
| /* Check for overlapping entries. |
| */ |
| SVN_ERR_ASSERT(entry->next == NO_INDEX || |
| entry->offset + size |
| <= get_entry(cache, entry->next)->offset); |
| |
| /* Compare original content, type and key (hashes) |
| */ |
| SVN_ERR(store_content_part(tag, *buffer, entry->size - entry->key.key_len, |
| result_pool)); |
| SVN_ERR(assert_equal_tags(&entry->tag, tag)); |
| |
| #endif |
| |
| /* update hit statistics |
| */ |
| increment_hit_counters(cache, entry); |
| *item_size = entry->size - entry->key.key_len; |
| |
| return SVN_NO_ERROR; |
| } |
| |
| /* Look for the *ITEM identified by KEY. If no item has been stored |
| * for KEY, *ITEM will be NULL. Otherwise, the DESERIALIZER is called |
| * to re-construct the proper object from the serialized data. |
| * Allocations will be done in POOL. |
| */ |
| static svn_error_t * |
| membuffer_cache_get(svn_membuffer_t *cache, |
| const full_key_t *key, |
| void **item, |
| svn_cache__deserialize_func_t deserializer, |
| DEBUG_CACHE_MEMBUFFER_TAG_ARG |
| apr_pool_t *result_pool) |
| { |
| apr_uint32_t group_index; |
| char *buffer; |
| apr_size_t size; |
| |
| /* find the entry group that will hold the key. |
| */ |
| group_index = get_group_index(&cache, &key->entry_key); |
| WITH_READ_LOCK(cache, |
| membuffer_cache_get_internal(cache, |
| group_index, |
| key, |
| &buffer, |
| &size, |
| DEBUG_CACHE_MEMBUFFER_TAG |
| result_pool)); |
| |
| /* re-construct the original data object from its serialized form. |
| */ |
| if (buffer == NULL) |
| { |
| *item = NULL; |
| return SVN_NO_ERROR; |
| } |
| |
| return deserializer(item, buffer, size, result_pool); |
| } |
| |
| /* Look for the cache entry in group GROUP_INDEX of CACHE, identified |
| * by the hash value TO_FIND. If no item has been stored for KEY, *FOUND |
| * will be FALSE and TRUE otherwise. |
| */ |
| static svn_error_t * |
| membuffer_cache_has_key_internal(svn_membuffer_t *cache, |
| apr_uint32_t group_index, |
| const full_key_t *to_find, |
| svn_boolean_t *found) |
| { |
| entry_t *entry = find_entry(cache, group_index, to_find, FALSE); |
| if (entry) |
| { |
| /* This often be called by "block read" when most data is already |
| in L2 and only a few previously evicted items are added to L1 |
| again. While items in L1 are well protected for a while, L2 |
| items may get evicted soon. Thus, mark all them as "hit" to give |
| them a higher chance of survival. */ |
| increment_hit_counters(cache, entry); |
| *found = TRUE; |
| } |
| else |
| { |
| *found = FALSE; |
| } |
| |
| return SVN_NO_ERROR; |
| } |
| |
| /* Look for an entry identified by KEY. If no item has been stored |
| * for KEY, *FOUND will be set to FALSE and TRUE otherwise. |
| */ |
| /* Implements svn_cache__has_key for membuffer caches. |
| */ |
| static svn_error_t * |
| membuffer_cache_has_key(svn_membuffer_t *cache, |
| const full_key_t *key, |
| svn_boolean_t *found) |
| { |
| /* find the entry group that will hold the key. |
| */ |
| apr_uint32_t group_index = get_group_index(&cache, &key->entry_key); |
| cache->total_reads++; |
| |
| WITH_READ_LOCK(cache, |
| membuffer_cache_has_key_internal(cache, |
| group_index, |
| key, |
| found)); |
| |
| return SVN_NO_ERROR; |
| } |
| |
| /* Look for the cache entry in group GROUP_INDEX of CACHE, identified |
| * by the hash value TO_FIND. FOUND indicates whether that entry exists. |
| * If not found, *ITEM will be NULL. |
| * |
| * Otherwise, the DESERIALIZER is called with that entry and the BATON |
| * provided and will extract the desired information. The result is set |
| * in *ITEM. Allocations will be done in POOL. |
| * |
| * Note: This function requires the caller to serialization access. |
| * Don't call it directly, call membuffer_cache_get_partial instead. |
| */ |
| static svn_error_t * |
| membuffer_cache_get_partial_internal(svn_membuffer_t *cache, |
| apr_uint32_t group_index, |
| const full_key_t *to_find, |
| void **item, |
| svn_boolean_t *found, |
| svn_cache__partial_getter_func_t deserializer, |
| void *baton, |
| DEBUG_CACHE_MEMBUFFER_TAG_ARG |
| apr_pool_t *result_pool) |
| { |
| entry_t *entry = find_entry(cache, group_index, to_find, FALSE); |
| cache->total_reads++; |
| if (entry == NULL) |
| { |
| *item = NULL; |
| *found = FALSE; |
| |
| return SVN_NO_ERROR; |
| } |
| else |
| { |
| const void *item_data = cache->data + entry->offset + entry->key.key_len; |
| apr_size_t item_size = entry->size - entry->key.key_len; |
| *found = TRUE; |
| increment_hit_counters(cache, entry); |
| |
| #ifdef SVN_DEBUG_CACHE_MEMBUFFER |
| |
| /* Check for overlapping entries. |
| */ |
| SVN_ERR_ASSERT(entry->next == NO_INDEX || |
| entry->offset + entry->size |
| <= get_entry(cache, entry->next)->offset); |
| |
| /* Compare original content, type and key (hashes) |
| */ |
| SVN_ERR(store_content_part(tag, item_data, item_size, result_pool)); |
| SVN_ERR(assert_equal_tags(&entry->tag, tag)); |
| |
| #endif |
| |
| return deserializer(item, item_data, item_size, baton, result_pool); |
| } |
| } |
| |
| /* Look for the cache entry identified by KEY. FOUND indicates |
| * whether that entry exists. If not found, *ITEM will be NULL. Otherwise, |
| * the DESERIALIZER is called with that entry and the BATON provided |
| * and will extract the desired information. The result is set in *ITEM. |
| * Allocations will be done in POOL. |
| */ |
| static svn_error_t * |
| membuffer_cache_get_partial(svn_membuffer_t *cache, |
| const full_key_t *key, |
| void **item, |
| svn_boolean_t *found, |
| svn_cache__partial_getter_func_t deserializer, |
| void *baton, |
| DEBUG_CACHE_MEMBUFFER_TAG_ARG |
| apr_pool_t *result_pool) |
| { |
| apr_uint32_t group_index = get_group_index(&cache, &key->entry_key); |
| |
| WITH_READ_LOCK(cache, |
| membuffer_cache_get_partial_internal |
| (cache, group_index, key, item, found, |
| deserializer, baton, DEBUG_CACHE_MEMBUFFER_TAG |
| result_pool)); |
| |
| return SVN_NO_ERROR; |
| } |
| |
| /* Look for the cache entry in group GROUP_INDEX of CACHE, identified |
| * by the hash value TO_FIND. If no entry has been found, the function |
| * returns without modifying the cache. |
| * |
| * Otherwise, FUNC is called with that entry and the BATON provided |
| * and may modify the cache entry. Allocations will be done in POOL. |
| * |
| * Note: This function requires the caller to serialization access. |
| * Don't call it directly, call membuffer_cache_set_partial instead. |
| */ |
| static svn_error_t * |
| membuffer_cache_set_partial_internal(svn_membuffer_t *cache, |
| apr_uint32_t group_index, |
| const full_key_t *to_find, |
| svn_cache__partial_setter_func_t func, |
| void *baton, |
| DEBUG_CACHE_MEMBUFFER_TAG_ARG |
| apr_pool_t *scratch_pool) |
| { |
| /* cache item lookup |
| */ |
| entry_t *entry = find_entry(cache, group_index, to_find, FALSE); |
| cache->total_reads++; |
| |
| /* this function is a no-op if the item is not in cache |
| */ |
| if (entry != NULL) |
| { |
| svn_error_t *err; |
| |
| /* access the serialized cache item */ |
| apr_size_t key_len = entry->key.key_len; |
| void *item_data = cache->data + entry->offset + key_len; |
| void *orig_data = item_data; |
| apr_size_t item_size = entry->size - key_len; |
| |
| increment_hit_counters(cache, entry); |
| cache->total_writes++; |
| |
| #ifdef SVN_DEBUG_CACHE_MEMBUFFER |
| |
| /* Check for overlapping entries. |
| */ |
| SVN_ERR_ASSERT(entry->next == NO_INDEX || |
| entry->offset + entry->size |
| <= get_entry(cache, entry->next)->offset); |
| |
| /* Compare original content, type and key (hashes) |
| */ |
| SVN_ERR(store_content_part(tag, item_data, item_size, scratch_pool)); |
| SVN_ERR(assert_equal_tags(&entry->tag, tag)); |
| |
| #endif |
| |
| /* modify it, preferably in-situ. |
| */ |
| err = func(&item_data, &item_size, baton, scratch_pool); |
| |
| if (err) |
| { |
| /* Something somewhere when wrong while FUNC was modifying the |
| * changed item. Thus, it might have become invalid /corrupted. |
| * We better drop that. |
| */ |
| drop_entry(cache, entry); |
| |
| return err; |
| } |
| else |
| { |
| /* if the modification caused a re-allocation, we need to remove |
| * the old entry and to copy the new data back into cache. |
| */ |
| if (item_data != orig_data) |
| { |
| /* Remove the old entry and try to make space for the new one. |
| * Note that the key has already been stored in the past, i.e. |
| * it is shorter than the MAX_ENTRY_SIZE. |
| */ |
| drop_entry(cache, entry); |
| if ( (cache->max_entry_size - key_len >= item_size) |
| && ensure_data_insertable_l1(cache, item_size + key_len)) |
| { |
| /* Write the new entry. |
| */ |
| entry = find_entry(cache, group_index, to_find, TRUE); |
| entry->size = item_size + key_len; |
| entry->offset = cache->l1.current_data; |
| |
| if (key_len) |
| memcpy(cache->data + entry->offset, |
| to_find->full_key.data, key_len); |
| if (item_size) |
| memcpy(cache->data + entry->offset + key_len, item_data, |
| item_size); |
| |
| /* Link the entry properly. |
| */ |
| insert_entry(cache, entry); |
| } |
| } |
| |
| #ifdef SVN_DEBUG_CACHE_MEMBUFFER |
| |
| /* Remember original content, type and key (hashes) |
| */ |
| SVN_ERR(store_content_part(tag, item_data, item_size, scratch_pool)); |
| memcpy(&entry->tag, tag, sizeof(*tag)); |
| |
| #endif |
| } |
| } |
| |
| return SVN_NO_ERROR; |
| } |
| |
| /* Look for the cache entry identified by KEY. If no entry |
| * has been found, the function returns without modifying the cache. |
| * Otherwise, FUNC is called with that entry and the BATON provided |
| * and may modify the cache entry. Allocations will be done in POOL. |
| */ |
| static svn_error_t * |
| membuffer_cache_set_partial(svn_membuffer_t *cache, |
| const full_key_t *key, |
| svn_cache__partial_setter_func_t func, |
| void *baton, |
| DEBUG_CACHE_MEMBUFFER_TAG_ARG |
| apr_pool_t *scratch_pool) |
| { |
| /* cache item lookup |
| */ |
| apr_uint32_t group_index = get_group_index(&cache, &key->entry_key); |
| WITH_WRITE_LOCK(cache, |
| membuffer_cache_set_partial_internal |
| (cache, group_index, key, func, baton, |
| DEBUG_CACHE_MEMBUFFER_TAG |
| scratch_pool)); |
| |
| /* done here -> unlock the cache |
| */ |
| return SVN_NO_ERROR; |
| } |
| |
| /* Implement the svn_cache__t interface on top of a shared membuffer cache. |
| * |
| * Because membuffer caches tend to be very large, there will be rather few |
| * of them (usually only one). Thus, the same instance shall be used as the |
| * backend to many application-visible svn_cache__t instances. This should |
| * also achieve global resource usage fairness. |
| * |
| * To accommodate items from multiple resources, the individual keys must be |
| * unique over all sources. This is achieved by simply adding a prefix key |
| * that unambiguously identifies the item's context (e.g. path to the |
| * respective repository). The prefix will be set upon construction of the |
| * svn_cache__t instance. |
| */ |
| |
| /* Internal cache structure (used in svn_cache__t.cache_internal) basically |
| * holding the additional parameters needed to call the respective membuffer |
| * functions. |
| */ |
| typedef struct svn_membuffer_cache_t |
| { |
| /* this is where all our data will end up in |
| */ |
| svn_membuffer_t *membuffer; |
| |
| /* use this conversion function when inserting an item into the memcache |
| */ |
| svn_cache__serialize_func_t serializer; |
| |
| /* use this conversion function when reading an item from the memcache |
| */ |
| svn_cache__deserialize_func_t deserializer; |
| |
| /* Prepend this to any key passed to us. |
| * This makes our keys different from all keys used by svn_membuffer_cache_t |
| * instances that we don't want to share cached data with. |
| */ |
| entry_key_t prefix; |
| |
| /* length of the keys that will be passed to us through the |
| * svn_cache_t interface. May be APR_HASH_KEY_STRING. |
| */ |
| apr_ssize_t key_len; |
| |
| /* priority class for all items written through this interface */ |
| apr_uint32_t priority; |
| |
| /* Temporary buffer containing the hash key for the current access |
| */ |
| full_key_t combined_key; |
| |
| /* if enabled, this will serialize the access to this instance. |
| */ |
| svn_mutex__t *mutex; |
| } svn_membuffer_cache_t; |
| |
| /* Return the prefix key used by CACHE. */ |
| static const char * |
| get_prefix_key(const svn_membuffer_cache_t *cache) |
| { |
| return (cache->prefix.prefix_idx == NO_INDEX |
| ? cache->combined_key.full_key.data |
| : cache->membuffer->prefix_pool->values[cache->prefix.prefix_idx]); |
| } |
| |
| /* Basically calculate a hash value for KEY of length KEY_LEN, combine it |
| * with the CACHE->PREFIX and write the result in CACHE->COMBINED_KEY. |
| * This could replace combine_key() entirely but we actually use it only |
| * when the quick path failed. |
| */ |
| static void |
| combine_long_key(svn_membuffer_cache_t *cache, |
| const void *key, |
| apr_ssize_t key_len) |
| { |
| apr_uint32_t *digest_buffer; |
| char *key_copy; |
| apr_size_t prefix_len = cache->prefix.key_len; |
| apr_size_t aligned_key_len; |
| |
| /* handle variable-length keys */ |
| if (key_len == APR_HASH_KEY_STRING) |
| key_len = strlen((const char *) key); |
| |
| aligned_key_len = ALIGN_VALUE(key_len); |
| |
| /* Combine keys. */ |
| svn_membuf__ensure(&cache->combined_key.full_key, |
| aligned_key_len + prefix_len); |
| |
| key_copy = (char *)cache->combined_key.full_key.data + prefix_len; |
| cache->combined_key.entry_key.key_len = aligned_key_len + prefix_len; |
| memcpy(key_copy, key, key_len); |
| memset(key_copy + key_len, 0, aligned_key_len - key_len); |
| |
| /* Hash key into 16 bytes. */ |
| digest_buffer = (apr_uint32_t *)cache->combined_key.entry_key.fingerprint; |
| svn__fnv1a_32x4_raw(digest_buffer, key, key_len); |
| |
| /* Combine with prefix. */ |
| cache->combined_key.entry_key.fingerprint[0] |
| ^= cache->prefix.fingerprint[0]; |
| cache->combined_key.entry_key.fingerprint[1] |
| ^= cache->prefix.fingerprint[1]; |
| } |
| |
| /* Basically calculate a hash value for KEY of length KEY_LEN, combine it |
| * with the CACHE->PREFIX and write the result in CACHE->COMBINED_KEY. |
| */ |
| static void |
| combine_key(svn_membuffer_cache_t *cache, |
| const void *key, |
| apr_ssize_t key_len) |
| { |
| /* copy of *key, padded with 0 */ |
| apr_uint64_t data[2]; |
| |
| /* Do we have to compare full keys? */ |
| if (cache->prefix.prefix_idx == NO_INDEX) |
| { |
| combine_long_key(cache, key, key_len); |
| return; |
| } |
| |
| /* short, fixed-size keys are the most common case */ |
| if (key_len == 16) |
| { |
| memcpy(data, key, 16); |
| } |
| else if (key_len == 8) |
| { |
| memcpy(data, key, 8); |
| data[1] = 0; |
| } |
| else |
| { |
| assert(key_len != APR_HASH_KEY_STRING && key_len < 16); |
| data[0] = 0; |
| data[1] = 0; |
| memcpy(data, key, key_len); |
| } |
| |
| /* Scramble key DATA to spread the key space more evenly across the |
| * cache segments and entry buckets. All of this shall be reversible |
| * to prevent key collisions. So, we limit ourselves to xor and |
| * permutations. |
| * |
| * Since the entry key must preserve the full key (prefix and KEY), |
| * the scramble must not introduce KEY collisions. |
| */ |
| data[1] = (data[1] << 27) | (data[1] >> 37); |
| data[1] ^= data[0] & 0xffff; |
| data[0] ^= data[1] & APR_UINT64_C(0xffffffffffff0000); |
| |
| /* Combine with this cache's prefix. This is reversible because the |
| * prefix is known through to the respective entry_key element. So, |
| * knowing entry_key.prefix_id, we can still reconstruct KEY (and the |
| * prefix key). |
| */ |
| cache->combined_key.entry_key.fingerprint[0] |
| = data[0] ^ cache->prefix.fingerprint[0]; |
| cache->combined_key.entry_key.fingerprint[1] |
| = data[1] ^ cache->prefix.fingerprint[1]; |
| } |
| |
| /* Implement svn_cache__vtable_t.get (not thread-safe) |
| */ |
| static svn_error_t * |
| svn_membuffer_cache_get(void **value_p, |
| svn_boolean_t *found, |
| void *cache_void, |
| const void *key, |
| apr_pool_t *result_pool) |
| { |
| svn_membuffer_cache_t *cache = cache_void; |
| |
| DEBUG_CACHE_MEMBUFFER_INIT_TAG(result_pool) |
| |
| /* special case */ |
| if (key == NULL) |
| { |
| *value_p = NULL; |
| *found = FALSE; |
| |
| return SVN_NO_ERROR; |
| } |
| |
| /* construct the full, i.e. globally unique, key by adding |
| * this cache instances' prefix |
| */ |
| combine_key(cache, key, cache->key_len); |
| |
| /* Look the item up. */ |
| SVN_ERR(membuffer_cache_get(cache->membuffer, |
| &cache->combined_key, |
| value_p, |
| cache->deserializer, |
| DEBUG_CACHE_MEMBUFFER_TAG |
| result_pool)); |
| |
| /* return result */ |
| *found = *value_p != NULL; |
| |
| return SVN_NO_ERROR; |
| } |
| |
| /* Implement svn_cache__vtable_t.has_key (not thread-safe) |
| */ |
| static svn_error_t * |
| svn_membuffer_cache_has_key(svn_boolean_t *found, |
| void *cache_void, |
| const void *key, |
| apr_pool_t *scratch_pool) |
| { |
| svn_membuffer_cache_t *cache = cache_void; |
| |
| /* special case */ |
| if (key == NULL) |
| { |
| *found = FALSE; |
| |
| return SVN_NO_ERROR; |
| } |
| |
| /* construct the full, i.e. globally unique, key by adding |
| * this cache instances' prefix |
| */ |
| combine_key(cache, key, cache->key_len); |
| |
| /* Look the item up. */ |
| SVN_ERR(membuffer_cache_has_key(cache->membuffer, |
| &cache->combined_key, |
| found)); |
| |
| /* return result */ |
| return SVN_NO_ERROR; |
| } |
| |
| /* Implement svn_cache__vtable_t.set (not thread-safe) |
| */ |
| static svn_error_t * |
| svn_membuffer_cache_set(void *cache_void, |
| const void *key, |
| void *value, |
| apr_pool_t *scratch_pool) |
| { |
| svn_membuffer_cache_t *cache = cache_void; |
| |
| DEBUG_CACHE_MEMBUFFER_INIT_TAG(scratch_pool) |
| |
| /* special case */ |
| if (key == NULL) |
| return SVN_NO_ERROR; |
| |
| /* construct the full, i.e. globally unique, key by adding |
| * this cache instances' prefix |
| */ |
| combine_key(cache, key, cache->key_len); |
| |
| /* (probably) add the item to the cache. But there is no real guarantee |
| * that the item will actually be cached afterwards. |
| */ |
| return membuffer_cache_set(cache->membuffer, |
| &cache->combined_key, |
| value, |
| cache->serializer, |
| cache->priority, |
| DEBUG_CACHE_MEMBUFFER_TAG |
| scratch_pool); |
| } |
| |
| /* Implement svn_cache__vtable_t.iter as "not implemented" |
| */ |
| static svn_error_t * |
| svn_membuffer_cache_iter(svn_boolean_t *completed, |
| void *cache_void, |
| svn_iter_apr_hash_cb_t user_cb, |
| void *user_baton, |
| apr_pool_t *scratch_pool) |
| { |
| return svn_error_create(SVN_ERR_UNSUPPORTED_FEATURE, NULL, |
| _("Can't iterate a membuffer-based cache")); |
| } |
| |
| /* Implement svn_cache__vtable_t.get_partial (not thread-safe) |
| */ |
| static svn_error_t * |
| svn_membuffer_cache_get_partial(void **value_p, |
| svn_boolean_t *found, |
| void *cache_void, |
| const void *key, |
| svn_cache__partial_getter_func_t func, |
| void *baton, |
| apr_pool_t *result_pool) |
| { |
| svn_membuffer_cache_t *cache = cache_void; |
| |
| DEBUG_CACHE_MEMBUFFER_INIT_TAG(result_pool) |
| |
| if (key == NULL) |
| { |
| *value_p = NULL; |
| *found = FALSE; |
| |
| return SVN_NO_ERROR; |
| } |
| |
| combine_key(cache, key, cache->key_len); |
| SVN_ERR(membuffer_cache_get_partial(cache->membuffer, |
| &cache->combined_key, |
| value_p, |
| found, |
| func, |
| baton, |
| DEBUG_CACHE_MEMBUFFER_TAG |
| result_pool)); |
| |
| return SVN_NO_ERROR; |
| } |
| |
| /* Implement svn_cache__vtable_t.set_partial (not thread-safe) |
| */ |
| static svn_error_t * |
| svn_membuffer_cache_set_partial(void *cache_void, |
| const void *key, |
| svn_cache__partial_setter_func_t func, |
| void *baton, |
| apr_pool_t *scratch_pool) |
| { |
| svn_membuffer_cache_t *cache = cache_void; |
| |
| DEBUG_CACHE_MEMBUFFER_INIT_TAG(scratch_pool) |
| |
| if (key != NULL) |
| { |
| combine_key(cache, key, cache->key_len); |
| SVN_ERR(membuffer_cache_set_partial(cache->membuffer, |
| &cache->combined_key, |
| func, |
| baton, |
| DEBUG_CACHE_MEMBUFFER_TAG |
| scratch_pool)); |
| } |
| return SVN_NO_ERROR; |
| } |
| |
| /* Implement svn_cache__vtable_t.is_cachable |
| * (thread-safe even without mutex) |
| */ |
| static svn_boolean_t |
| svn_membuffer_cache_is_cachable(void *cache_void, apr_size_t size) |
| { |
| /* Don't allow extremely large element sizes. Otherwise, the cache |
| * might by thrashed by a few extremely large entries. And the size |
| * must be small enough to be stored in a 32 bit value. |
| */ |
| svn_membuffer_cache_t *cache = cache_void; |
| return cache->priority > SVN_CACHE__MEMBUFFER_DEFAULT_PRIORITY |
| ? cache->membuffer->l2.size >= size && MAX_ITEM_SIZE >= size |
| : size <= cache->membuffer->max_entry_size; |
| } |
| |
| /* Add statistics of SEGMENT to INFO. If INCLUDE_HISTOGRAM is TRUE, |
| * accumulate index bucket fill levels in INFO->HISTOGRAM. |
| */ |
| static svn_error_t * |
| svn_membuffer_get_segment_info(svn_membuffer_t *segment, |
| svn_cache__info_t *info, |
| svn_boolean_t include_histogram) |
| { |
| apr_uint32_t i; |
| |
| info->data_size += segment->l1.size + segment->l2.size; |
| info->used_size += segment->data_used; |
| info->total_size += segment->l1.size + segment->l2.size + |
| segment->group_count * GROUP_SIZE * sizeof(entry_t); |
| |
| info->used_entries += segment->used_entries; |
| info->total_entries += segment->group_count * GROUP_SIZE; |
| |
| if (include_histogram) |
| for (i = 0; i < segment->group_count; ++i) |
| if (is_group_initialized(segment, i)) |
| { |
| entry_group_t *chain_end |
| = last_group_in_chain(segment, &segment->directory[i]); |
| apr_size_t use |
| = MIN(chain_end->header.used, |
| sizeof(info->histogram) / sizeof(info->histogram[0]) - 1); |
| info->histogram[use]++; |
| } |
| |
| return SVN_NO_ERROR; |
| } |
| |
| /* Implement svn_cache__vtable_t.get_info |
| * (thread-safe even without mutex) |
| */ |
| static svn_error_t * |
| svn_membuffer_cache_get_info(void *cache_void, |
| svn_cache__info_t *info, |
| svn_boolean_t reset, |
| apr_pool_t *result_pool) |
| { |
| svn_membuffer_cache_t *cache = cache_void; |
| apr_uint32_t i; |
| |
| /* cache front-end specific data */ |
| |
| info->id = apr_pstrdup(result_pool, get_prefix_key(cache)); |
| |
| /* collect info from shared cache back-end */ |
| |
| for (i = 0; i < cache->membuffer->segment_count; ++i) |
| { |
| svn_membuffer_t *segment = cache->membuffer + i; |
| WITH_READ_LOCK(segment, |
| svn_membuffer_get_segment_info(segment, info, FALSE)); |
| } |
| |
| return SVN_NO_ERROR; |
| } |
| |
| |
| /* the v-table for membuffer-based caches (single-threaded access) |
| */ |
| static svn_cache__vtable_t membuffer_cache_vtable = { |
| svn_membuffer_cache_get, |
| svn_membuffer_cache_has_key, |
| svn_membuffer_cache_set, |
| svn_membuffer_cache_iter, |
| svn_membuffer_cache_is_cachable, |
| svn_membuffer_cache_get_partial, |
| svn_membuffer_cache_set_partial, |
| svn_membuffer_cache_get_info |
| }; |
| |
| /* Implement svn_cache__vtable_t.get and serialize all cache access. |
| */ |
| static svn_error_t * |
| svn_membuffer_cache_get_synced(void **value_p, |
| svn_boolean_t *found, |
| void *cache_void, |
| const void *key, |
| apr_pool_t *result_pool) |
| { |
| svn_membuffer_cache_t *cache = cache_void; |
| SVN_MUTEX__WITH_LOCK(cache->mutex, |
| svn_membuffer_cache_get(value_p, |
| found, |
| cache_void, |
| key, |
| result_pool)); |
| |
| return SVN_NO_ERROR; |
| } |
| |
| /* Implement svn_cache__vtable_t.has_key and serialize all cache access. |
| */ |
| static svn_error_t * |
| svn_membuffer_cache_has_key_synced(svn_boolean_t *found, |
| void *cache_void, |
| const void *key, |
| apr_pool_t *result_pool) |
| { |
| svn_membuffer_cache_t *cache = cache_void; |
| SVN_MUTEX__WITH_LOCK(cache->mutex, |
| svn_membuffer_cache_has_key(found, |
| cache_void, |
| key, |
| result_pool)); |
| |
| return SVN_NO_ERROR; |
| } |
| |
| /* Implement svn_cache__vtable_t.set and serialize all cache access. |
| */ |
| static svn_error_t * |
| svn_membuffer_cache_set_synced(void *cache_void, |
| const void *key, |
| void *value, |
| apr_pool_t *scratch_pool) |
| { |
| svn_membuffer_cache_t *cache = cache_void; |
| SVN_MUTEX__WITH_LOCK(cache->mutex, |
| svn_membuffer_cache_set(cache_void, |
| key, |
| value, |
| scratch_pool)); |
| |
| return SVN_NO_ERROR; |
| } |
| |
| /* Implement svn_cache__vtable_t.get_partial and serialize all cache access. |
| */ |
| static svn_error_t * |
| svn_membuffer_cache_get_partial_synced(void **value_p, |
| svn_boolean_t *found, |
| void *cache_void, |
| const void *key, |
| svn_cache__partial_getter_func_t func, |
| void *baton, |
| apr_pool_t *result_pool) |
| { |
| svn_membuffer_cache_t *cache = cache_void; |
| SVN_MUTEX__WITH_LOCK(cache->mutex, |
| svn_membuffer_cache_get_partial(value_p, |
| found, |
| cache_void, |
| key, |
| func, |
| baton, |
| result_pool)); |
| |
| return SVN_NO_ERROR; |
| } |
| |
| /* Implement svn_cache__vtable_t.set_partial and serialize all cache access. |
| */ |
| static svn_error_t * |
| svn_membuffer_cache_set_partial_synced(void *cache_void, |
| const void *key, |
| svn_cache__partial_setter_func_t func, |
| void *baton, |
| apr_pool_t *scratch_pool) |
| { |
| svn_membuffer_cache_t *cache = cache_void; |
| SVN_MUTEX__WITH_LOCK(cache->mutex, |
| svn_membuffer_cache_set_partial(cache_void, |
| key, |
| func, |
| baton, |
| scratch_pool)); |
| |
| return SVN_NO_ERROR; |
| } |
| |
| /* the v-table for membuffer-based caches with multi-threading support) |
| */ |
| static svn_cache__vtable_t membuffer_cache_synced_vtable = { |
| svn_membuffer_cache_get_synced, |
| svn_membuffer_cache_has_key_synced, |
| svn_membuffer_cache_set_synced, |
| svn_membuffer_cache_iter, /* no sync required */ |
| svn_membuffer_cache_is_cachable, /* no sync required */ |
| svn_membuffer_cache_get_partial_synced, |
| svn_membuffer_cache_set_partial_synced, |
| svn_membuffer_cache_get_info /* no sync required */ |
| }; |
| |
| /* standard serialization function for svn_stringbuf_t items. |
| * Implements svn_cache__serialize_func_t. |
| */ |
| static svn_error_t * |
| serialize_svn_stringbuf(void **buffer, |
| apr_size_t *buffer_size, |
| void *item, |
| apr_pool_t *result_pool) |
| { |
| svn_stringbuf_t *value_str = item; |
| |
| *buffer = value_str->data; |
| *buffer_size = value_str->len + 1; |
| |
| return SVN_NO_ERROR; |
| } |
| |
| /* standard de-serialization function for svn_stringbuf_t items. |
| * Implements svn_cache__deserialize_func_t. |
| */ |
| static svn_error_t * |
| deserialize_svn_stringbuf(void **item, |
| void *buffer, |
| apr_size_t buffer_size, |
| apr_pool_t *result_pool) |
| { |
| svn_stringbuf_t *value_str = apr_palloc(result_pool, sizeof(svn_stringbuf_t)); |
| |
| value_str->pool = result_pool; |
| value_str->blocksize = buffer_size; |
| value_str->data = buffer; |
| value_str->len = buffer_size-1; |
| *item = value_str; |
| |
| return SVN_NO_ERROR; |
| } |
| |
| /* Construct a svn_cache__t object on top of a shared memcache. |
| */ |
| svn_error_t * |
| svn_cache__create_membuffer_cache(svn_cache__t **cache_p, |
| svn_membuffer_t *membuffer, |
| svn_cache__serialize_func_t serializer, |
| svn_cache__deserialize_func_t deserializer, |
| apr_ssize_t klen, |
| const char *prefix, |
| apr_uint32_t priority, |
| svn_boolean_t thread_safe, |
| svn_boolean_t short_lived, |
| apr_pool_t *result_pool, |
| apr_pool_t *scratch_pool) |
| { |
| svn_checksum_t *checksum; |
| apr_size_t prefix_len, prefix_orig_len; |
| |
| /* allocate the cache header structures |
| */ |
| svn_cache__t *wrapper = apr_pcalloc(result_pool, sizeof(*wrapper)); |
| svn_membuffer_cache_t *cache = apr_pcalloc(result_pool, sizeof(*cache)); |
| |
| /* initialize our internal cache header |
| */ |
| cache->membuffer = membuffer; |
| cache->serializer = serializer |
| ? serializer |
| : serialize_svn_stringbuf; |
| cache->deserializer = deserializer |
| ? deserializer |
| : deserialize_svn_stringbuf; |
| cache->priority = priority; |
| cache->key_len = klen; |
| |
| SVN_ERR(svn_mutex__init(&cache->mutex, thread_safe, result_pool)); |
| |
| /* Copy the prefix into the prefix full key. Align it to ITEM_ALIGMENT. |
| * Don't forget to include the terminating NUL. */ |
| prefix_orig_len = strlen(prefix) + 1; |
| prefix_len = ALIGN_VALUE(prefix_orig_len); |
| |
| /* Paranoia check to ensure pointer arithmetics work as expected. */ |
| if (prefix_orig_len >= SVN_MAX_OBJECT_SIZE) |
| return svn_error_create(SVN_ERR_INCORRECT_PARAMS, NULL, |
| _("Prefix too long")); |
| |
| /* Construct the folded prefix key. */ |
| SVN_ERR(svn_checksum(&checksum, |
| svn_checksum_md5, |
| prefix, |
| strlen(prefix), |
| scratch_pool)); |
| memcpy(cache->prefix.fingerprint, checksum->digest, |
| sizeof(cache->prefix.fingerprint)); |
| cache->prefix.key_len = prefix_len; |
| |
| /* Fix-length keys of up to 16 bytes may be handled without storing the |
| * full key separately for each item. */ |
| if ( (klen != APR_HASH_KEY_STRING) |
| && (klen <= sizeof(cache->combined_key.entry_key.fingerprint)) |
| && !short_lived) |
| SVN_ERR(prefix_pool_get(&cache->prefix.prefix_idx, |
| membuffer->prefix_pool, |
| prefix)); |
| else |
| cache->prefix.prefix_idx = NO_INDEX; |
| |
| /* If key combining is not guaranteed to produce unique results, we have |
| * to handle full keys. Otherwise, leave it NULL. */ |
| if (cache->prefix.prefix_idx == NO_INDEX) |
| { |
| /* Initialize the combined key. Pre-allocate some extra room in the |
| * full key such that we probably don't need to re-alloc. */ |
| cache->combined_key.entry_key = cache->prefix; |
| svn_membuf__create(&cache->combined_key.full_key, prefix_len + 200, |
| result_pool); |
| memcpy((char *)cache->combined_key.full_key.data, prefix, |
| prefix_orig_len); |
| memset((char *)cache->combined_key.full_key.data + prefix_orig_len, 0, |
| prefix_len - prefix_orig_len); |
| } |
| else |
| { |
| /* Initialize the combined key. We will never have the full combined |
| * key, so leave it NULL and set its length to 0 to prevent access to |
| * it. Keep the fingerprint 0 as well b/c it will always be set anew |
| * by combine_key(). */ |
| cache->combined_key.entry_key.prefix_idx = cache->prefix.prefix_idx; |
| cache->combined_key.entry_key.key_len = 0; |
| } |
| |
| /* initialize the generic cache wrapper |
| */ |
| wrapper->vtable = thread_safe ? &membuffer_cache_synced_vtable |
| : &membuffer_cache_vtable; |
| wrapper->cache_internal = cache; |
| wrapper->error_handler = 0; |
| wrapper->error_baton = 0; |
| wrapper->pretend_empty = !!getenv("SVN_X_DOES_NOT_MARK_THE_SPOT"); |
| |
| *cache_p = wrapper; |
| return SVN_NO_ERROR; |
| } |
| |
| static svn_error_t * |
| svn_membuffer_get_global_segment_info(svn_membuffer_t *segment, |
| svn_cache__info_t *info) |
| { |
| info->gets += segment->total_reads; |
| info->sets += segment->total_writes; |
| info->hits += segment->total_hits; |
| |
| WITH_READ_LOCK(segment, |
| svn_membuffer_get_segment_info(segment, info, TRUE)); |
| |
| return SVN_NO_ERROR; |
| } |
| |
| svn_cache__info_t * |
| svn_cache__membuffer_get_global_info(apr_pool_t *pool) |
| { |
| apr_uint32_t i; |
| |
| svn_membuffer_t *membuffer = svn_cache__get_global_membuffer_cache(); |
| svn_cache__info_t *info = apr_pcalloc(pool, sizeof(*info)); |
| |
| /* cache front-end specific data */ |
| |
| info->id = "membuffer globals"; |
| |
| /* collect info from shared cache back-end */ |
| |
| for (i = 0; i < membuffer->segment_count; ++i) |
| svn_error_clear(svn_membuffer_get_global_segment_info(membuffer + i, |
| info)); |
| |
| return info; |
| } |