/*
* 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 "svn_pools.h"
#include "svn_checksum.h"
#include "md5.h"
#include "svn_private_config.h"
#include "cache.h"
#include "svn_string.h"
#include "private/svn_dep_compat.h"
/*
* This svn_cache__t implementation actually consists of two parts:
* a shared (per-process) singleton membuffer cache instance and shallow
* svn_cache__t frontend 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. There may be arbitrary gaps between entries.
* 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.
*
* 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.
*
* 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 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.
*
* Insertion can occur at only one, sliding position. It is marked by its
* offset in the data buffer plus the index of the first used entry at or
* behind that position. If this gap is too small to accomodate the new
* item, 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,
* a randomized variant of LFU is used (see ensure_data_insertable 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 halfed 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().
*
* To limit the entry size and management overhead, not the actual item keys
* but only their MD5 checksums will not be stored. This is reasonably safe
* to do since users have only limited control over the full keys, even if
* these contain folder paths. So, it is very hard to deliberately construct
* colliding keys. Random checksum collisions can be shown to be extremely
* unlikely.
*
* 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.
*/
/* A 4-way associative cache seems to be the best compromise between
* performance (worst-case lookups) and efficiency-loss due to collisions.
*
* This value may be changed to any positive integer.
*/
#define GROUP_SIZE 4
/* We use MD5 for digest size and speed (SHA1 is >2x slower, for instance).
*/
#define KEY_SIZE APR_MD5_DIGESTSIZE
/* For more efficient copy operations, let'a align all data items properly.
* Must be a power of 2.
*/
#define ITEM_ALIGNMENT 16
/* Don't create cache segments smaller than this value unless the total
* cache size itself is smaller.
*/
#define MIN_SEGMENT_SIZE 0x2000000ull
/* 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
* caches. For instance, the default of 32 means 8x32 groups per byte, i.e.
* 8 flags/byte x 32 groups/flag x 4 entries/group x 40 index bytes/entry
* x 16 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
/* Invalid buffer offset reference value. Equivalent to APR_UINT32_T(-1)
*/
#define NO_OFFSET APR_UINT64_MAX
/* 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 7 bytes + \0 as plaintext for easy identification by the dev.
*/
#define PREFIX_TAIL_LEN 8
/* 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 the 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;
/* Per svn_cache_t instance initialization helper.
*/
static void get_prefix_tail(const char *prefix, char *prefix_tail)
{
apr_size_t len = strlen(prefix);
apr_size_t to_copy = len > PREFIX_TAIL_LEN-1 ? PREFIX_TAIL_LEN-1 : len;
memset(prefix_tail, 0, PREFIX_TAIL_LEN);
memcpy(prefix_tail, prefix + len - to_copy, to_copy);
}
/* Initialize all members of TAG except for the content hash.
*/
static svn_error_t* store_key_part(entry_tag_t *tag,
unsigned char *prefix_hash,
char *prefix_tail,
const void *key,
apr_size_t size,
apr_pool_t *pool)
{
svn_checksum_t *checksum;
SVN_ERR(svn_checksum(&checksum,
svn_checksum_md5,
key,
size,
pool));
memcpy(tag->prefix_hash, prefix_hash, sizeof(tag->prefix_hash));
memcpy(tag->key_hash, checksum->digest, sizeof(tag->key_hash));
memcpy(tag->prefix_tail, prefix_tail, sizeof(tag->prefix_tail));
tag->key_len = size;
return SVN_NO_ERROR;
}
/* Initialize the content hash member of TAG.
*/
static svn_error_t* store_content_part(entry_tag_t *tag,
const char *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;
}
/* Reoccuring code snippets.
*/
#define DEBUG_CACHE_MEMBUFFER_TAG_ARG entry_tag_t *tag,
#define DEBUG_CACHE_MEMBUFFER_TAG &tag,
#define DEBUG_CACHE_MEMBUFFER_INIT_TAG \
entry_tag_t tag; \
SVN_ERR(store_key_part(&tag, \
cache->prefix, \
cache->prefix_tail, \
key, \
cache->key_len == APR_HASH_KEY_STRING \
? strlen((const char *) key) \
: cache->key_len, \
cache->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
#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. An entry is unused if and only if its OFFSET
* member is NO_OFFSET.
*/
typedef struct entry_t
{
/* Identifying the data item. Only valid for used entries.
*/
unsigned char key [KEY_SIZE];
/* If NO_OFFSET, the entry is not in used. Otherwise, it is the offset
* of the cached item's serialized data within the data buffer.
*/
apr_uint64_t offset;
/* Size of the serialized item data. May be 0.
* Only valid for used entries.
*/
apr_uint32_t size;
/* Number of (read) hits for this entry. Will be reset upon write.
* Only valid for used entries.
*/
apr_uint32_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 membuffer_cache_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 membuffer_cache_t.first member.
* Only valid for used entries.
*/
apr_uint32_t previous;
#ifdef SVN_DEBUG_CACHE_MEMBUFFER
/* Remember type, content and key hashes.
*/
entry_tag_t tag;
#endif
} entry_t;
/* We group dictionary entries to make this GROUP-SIZE-way assicative.
*/
typedef entry_t entry_group_t[GROUP_SIZE];
/* 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;
/* The dictionary, GROUP_SIZE * 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;
/* 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;
/* Pointer to the data buffer, data_size bytes long. Never NULL.
*/
unsigned char *data;
/* Size of data buffer in bytes. Must be > 0.
*/
apr_uint64_t data_size;
/* Offset in the data buffer where the next insertion shall occur.
*/
apr_uint64_t current_data;
/* Total number of data buffer bytes in use. This is for statistics only.
*/
apr_uint64_t data_used;
/* Number of used dictionary entries, i.e. number of cached items.
* In conjunction with hit_cout, this is used calculate the average
* hit count as part of the randomized LFU algorithm.
*/
apr_uint32_t used_entries;
/* Sum of (read) hit counts of all used dictionary entries.
* In conjunction used_entries used_entries, this is used calculate
* the average hit count as part of the randomized LFU algorithm.
*/
apr_uint64_t hit_count;
/* Total number of calls to membuffer_cache_get.
* Purely statistical information that may be used for profiling.
*/
apr_uint64_t total_reads;
/* Total number of calls to membuffer_cache_set.
* Purely statistical information that may be used for profiling.
*/
apr_uint64_t total_writes;
/* Total number of hits since the cache's creation.
* Purely statistical information that may be used for profiling.
*/
apr_uint64_t total_hits;
#if APR_HAS_THREADS
/* 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.
*/
apr_thread_mutex_t *mutex;
#endif
};
/* Align integer VALUE to the next ITEM_ALIGNMENT boundary.
*/
#define ALIGN_VALUE(value) (((value) + ITEM_ALIGNMENT-1) & -ITEM_ALIGNMENT)
/* Align POINTER value to the next ITEM_ALIGNMENT boundary.
*/
#define ALIGN_POINTER(pointer) ((void*)ALIGN_VALUE((apr_size_t)(char*)(pointer)))
/* Acquire the cache mutex, if necessary.
*/
static svn_error_t *
lock_cache(svn_membuffer_t *cache)
{
#if APR_HAS_THREADS
if (cache->mutex)
{
apr_status_t status = apr_thread_mutex_lock(cache->mutex);
if (status)
return svn_error_wrap_apr(status, _("Can't lock cache mutex"));
}
#endif
return SVN_NO_ERROR;
}
/* Release the cache mutex, if necessary.
*/
static svn_error_t *
unlock_cache(svn_membuffer_t *cache, svn_error_t *err)
{
#if APR_HAS_THREADS
if (cache->mutex)
{
apr_status_t status = apr_thread_mutex_unlock(cache->mutex);
if (err)
return err;
if (status)
return svn_error_wrap_apr(status, _("Can't unlock cache mutex"));
}
#endif
return err;
}
/* 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][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)
{
return (apr_uint32_t)(entry - (entry_t *)cache->directory);
}
/* 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)
{
apr_uint32_t idx = get_index(cache, entry);
/* Only valid to be called for used entries.
*/
assert(entry->offset != NO_OFFSET);
/* update global cache usage counters
*/
cache->used_entries--;
cache->hit_count -= entry->hit_count;
cache->data_used -= entry->size;
/* extend the insertion window, if the entry happens to border it
*/
if (idx == cache->next)
cache->next = entry->next;
else
if (entry->next == cache->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 */
cache->current_data = 0;
}
else
{
/* insertion may start right behind the previous entry */
entry_t *previous = get_entry(cache, entry->previous);
cache->current_data = ALIGN_VALUE( previous->offset
+ previous->size);
}
}
/* unlink it from the chain of used entries
*/
if (entry->previous == NO_INDEX)
cache->first = entry->next;
else
get_entry(cache, entry->previous)->next = entry->next;
if (entry->next == NO_INDEX)
cache->last = entry->previous;
else
get_entry(cache, entry->next)->previous = entry->previous;
/* Mark the entry as unused.
*/
entry->offset = NO_OFFSET;
}
/* 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)
{
apr_uint32_t idx = get_index(cache, entry);
entry_t *next = cache->next == NO_INDEX
? NULL
: get_entry(cache, cache->next);
/* The entry must start at the beginning of the insertion window.
*/
assert(entry->offset == cache->current_data);
cache->current_data = ALIGN_VALUE(entry->offset + entry->size);
/* update global cache usage counters
*/
cache->used_entries++;
cache->data_used += entry->size;
entry->hit_count = 0;
/* update entry chain
*/
entry->next = cache->next;
if (cache->first == NO_INDEX)
{
/* insert as the first entry and only in the chain
*/
entry->previous = NO_INDEX;
cache->last = idx;
cache->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 = cache->last;
get_entry(cache, cache->last)->next = idx;
cache->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
cache->first = idx;
}
}
/* Map a KEY of length LEN to the CACHE and group that shall contain the
* respective item. Return the hash value in TO_FIND. Returns -1 upon error.
*/
static apr_uint32_t
get_group_index(svn_membuffer_t **cache,
const void *key,
apr_size_t len,
unsigned char *to_find,
apr_pool_t *pool)
{
apr_uint32_t hash = 0;
int i;
/* calculate a hash value for the key */
svn_checksum_t *checksum;
svn_error_t *err;
err = svn_checksum(&checksum, svn_checksum_md5, key, len, pool);
if (err != NULL)
{
svn_error_clear(err);
return NO_INDEX;
}
memcpy(to_find, checksum->digest, APR_MD5_DIGESTSIZE);
/* select the cache segment to use */
*cache = &(*cache)[to_find[0] & ((*cache)->segment_count -1)];
/* Get the group that *must* contain the entry. Fold the hash value
* just to be sure (it should not be necessary for perfect hashes).
*/
for (i = 0; i < sizeof(to_find) / sizeof(apr_uint32_t); ++i)
hash += ((apr_uint32_t*)to_find)[i] ^ ((hash >> 19) || (hash << 13));
return hash % (*cache)->group_count;
}
/* Reduce the hit count of ENTRY and update the accumunated 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;
cache->hit_count -= hits_removed;
entry->hit_count -= hits_removed;
}
/* Returns 0 if the entry group idenified by GROUP_INDEX in CACHE has not
* been intialized, 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 = 1 << ((group_index / GROUP_INIT_GRANULARITY) % 8);
return flags & bit_mask;
}
/* Initializes the section of the directory in CACHE that contains
* the entry group indentified by GROUP_INDEX. */
static void
initialize_group(svn_membuffer_t *cache, apr_uint32_t group_index)
{
unsigned char bit_mask;
apr_uint32_t i, j;
/* 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)
last_index = cache->group_count;
for (i = first_index; i < last_index; ++i)
for (j = 0; j < GROUP_SIZE; j++)
cache->directory[i][j].offset = NO_OFFSET;
/* set the "initialized" bit for these groups */
bit_mask = 1 << ((group_index / GROUP_INIT_GRANULARITY) % 8);
cache->group_initialized[group_index / (8 * GROUP_INIT_GRANULARITY)]
|= bit_mask;
}
/* 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.
*/
static entry_t *
find_entry(svn_membuffer_t *cache,
apr_uint32_t group_index,
unsigned char *to_find,
svn_boolean_t find_empty)
{
entry_t *group;
entry_t *entry = NULL;
int i;
/* get the group that *must* contain the entry
*/
group = &cache->directory[group_index][0];
/* 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;
/* initialize entry for the new key */
memcpy(entry->key, to_find, KEY_SIZE);
}
return entry;
}
/* try to find the matching entry
*/
for (i = 0; i < GROUP_SIZE; ++i)
if (group[i].offset != NO_OFFSET &&
!memcmp(to_find, group[i].key, KEY_SIZE))
{
/* found it
*/
entry = &group[i];
if (find_empty)
drop_entry(cache, entry);
return entry;
}
/* None found. Are we looking for a free entry?
*/
if (find_empty)
{
/* look for an empty entry and return that ...
*/
for (i = 0; i < GROUP_SIZE; ++i)
if (group[i].offset == NO_OFFSET)
{
entry = &group[i];
break;
}
/* ... or, if none is empty, delete the oldest entry
*/
if (entry == NULL)
{
entry = &group[0];
for (i = 1; i < GROUP_SIZE; ++i)
if (entry->hit_count > group[i].hit_count)
entry = &group[i];
/* for the entries that don't have been removed,
* reduce their hitcounts to put them at a relative
* disadvantage the next time.
*/
for (i = 0; i < GROUP_SIZE; ++i)
if (entry != &group[i])
let_entry_age(cache, entry);
drop_entry(cache, entry);
}
/* initialize entry for the new key */
memcpy(entry->key, to_find, KEY_SIZE);
}
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);
/* 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 aligment.
* 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 != cache->current_data)
{
memmove(cache->data + cache->current_data,
cache->data + entry->offset,
size);
entry->offset = cache->current_data;
}
/* The insertion position is now directly behind this entry.
*/
cache->current_data = entry->offset + size;
cache->next = entry->next;
}
/* If necessary, enlarge the insertion window until it is at least
* SIZE bytes long. SIZE must not exceed the data buffer size.
* 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(svn_membuffer_t *cache, apr_size_t size)
{
entry_t *entry;
apr_uint64_t average_hit_value;
apr_uint64_t threshold;
/* accumulated size of the entries that have been removed to make
* room for the new one.
*/
apr_size_t drop_size = 0;
/* This loop will eventually terminate because every cache entry
* would get dropped eventually:
* - hit counts become 0 after the got kept for 32 full scans
* - larger elements get dropped as soon as their hit count is 0
* - smaller and smaller elements get removed as the average
* entry size drops (average drops by a factor of 8 per scan)
* - after no more than 43 full scans, all elements would be removed
*
* Since size is < 4th of the cache size and about 50% of all
* entries get removed by a scan, it is very unlikely that more
* than a fractional scan will be necessary.
*/
while (1)
{
/* first offset behind the insertion window
*/
apr_uint64_t end = cache->next == NO_INDEX
? cache->data_size
: get_entry(cache, cache->next)->offset;
/* leave function as soon as the insertion window is large enough
*/
if (end - cache->current_data >= size)
return TRUE;
/* Don't be too eager to cache data. Smaller items will fit into
* the cache after dropping a single item. Of the larger ones, we
* will only accept about 50%. They are also likely to get evicted
* soon due to their notoriously low hit counts.
*
* As long as enough similarly or even larger sized entries already
* exist in the cache, much less insert requests will be rejected.
*/
if (2 * drop_size > size)
return FALSE;
/* try to enlarge the insertion window
*/
if (cache->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->current_data = 0;
cache->next = cache->first;
}
else
{
entry = get_entry(cache, cache->next);
/* Keep entries that are very small. Those are likely to be data
* headers or similar management structures. So, they are probably
* important while not occupying much space.
* But keep them only as long as they are a minority.
*/
if ( (apr_uint64_t)entry->size * cache->used_entries
< cache->data_used / 8)
{
move_entry(cache, entry);
}
else
{
/* Roll the dice and determine a threshold somewhere from 0 up
* to 2 times the average hit count.
*/
average_hit_value = cache->hit_count / cache->used_entries;
threshold = (average_hit_value+1) * (rand() % 4096) / 2048;
/* Drop the entry from the end of the insertion window, if it
* has been hit less than the threshold. Otherwise, keep it and
* move the insertion window one entry further.
*/
if (entry->hit_count >= threshold)
{
move_entry(cache, entry);
}
else
{
drop_size += entry->size;
drop_entry(cache, entry);
}
}
}
}
/* This will never be reached. But if it was, "can't insert" was the
* right answer. */
}
/* Mimic apr_pcalloc in APR_POOL_DEBUG mode, i.e. handle failed allocations
* (e.g. OOM) properly: Allocate at least SIZE bytes from POOL and zero
* the content of the allocated memory if ZERO has been set. Return NULL
* upon failed allocations.
*
* Also, satisfy our buffer alignment needs for performance reasons.
*/
static void* secure_aligned_alloc(apr_pool_t *pool,
apr_size_t size,
svn_boolean_t zero)
{
void* memory = apr_palloc(pool, size + ITEM_ALIGNMENT);
if (memory != NULL)
{
memory = ALIGN_POINTER(memory);
if (zero)
memset(memory, 0, size);
}
return memory;
}
/* Create a new membuffer cache instance. If the TOTAL_SIZE of the
* memory i too small to accomodate the DICTIONARY_SIZE, the latte
* will be resized automatically. Also, a minumum size is assured
* for the DICTIONARY_SIZE. THREAD_SAFE may be FALSE, if there will
* be no concurrent acccess to the CACHE returned.
*
* All allocations, in particular the data buffer and dictionary will
* be made from POOL.
*/
svn_error_t *
svn_cache__membuffer_cache_create(svn_membuffer_t **cache,
apr_size_t total_size,
apr_size_t directory_size,
svn_boolean_t thread_safe,
apr_pool_t *pool)
{
svn_membuffer_t *c;
apr_uint32_t segment_count_shift = 0;
apr_uint32_t segment_count = 1;
apr_uint32_t seg;
apr_uint32_t group_count;
apr_uint32_t group_init_size;
apr_uint64_t data_size;
/* 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 limites the maximum size of cachable items.
*
* Segments should not be smaller than 32MB and max. cachable item
* size should grow as fast as segmentation.
*/
while (((2 * MIN_SEGMENT_SIZE) << (2 * segment_count_shift)) < total_size)
++segment_count_shift;
segment_count = 1 << segment_count_shift;
/* 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_shift;
directory_size >>= segment_count_shift;
/* 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 < sizeof(entry_group_t))
directory_size = 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.
*/
data_size = total_size - directory_size;
/* to keep the entries small, we use 32 bit indices only
* -> we need to ensure that no more then 4G entries exist
*/
group_count = directory_size / sizeof(entry_group_t);
if (group_count >= (APR_UINT32_MAX / GROUP_SIZE))
{
group_count = (APR_UINT32_MAX / GROUP_SIZE) - 1;
}
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 = segment_count;
c[seg].group_count = group_count;
c[seg].directory = apr_pcalloc(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);
c[seg].first = NO_INDEX;
c[seg].last = NO_INDEX;
c[seg].next = NO_INDEX;
c[seg].data_size = data_size;
c[seg].data = secure_aligned_alloc(pool, (apr_size_t)data_size, FALSE);
c[seg].current_data = 0;
c[seg].data_used = 0;
c[seg].used_entries = 0;
c[seg].hit_count = 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
/* 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. */
c[seg].mutex = NULL;
if (thread_safe)
{
apr_status_t status =
apr_thread_mutex_create(&(c[seg].mutex),
APR_THREAD_MUTEX_DEFAULT,
pool);
if (status)
return svn_error_wrap_apr(status, _("Can't create cache mutex"));
}
#else
if (thread_safe)
return svn_error_wrap_apr(APR_ENOTIMPL, _("APR doesn't support threads"));
#endif
}
/* done here
*/
*cache = c;
return SVN_NO_ERROR;
}
/* Try to insert the ITEM and use the KEY to unqiuely 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 void *key,
apr_size_t key_len,
void *item,
svn_cache__serialize_func_t serializer,
DEBUG_CACHE_MEMBUFFER_TAG_ARG
apr_pool_t *scratch_pool)
{
apr_uint32_t group_index;
unsigned char to_find[KEY_SIZE];
entry_t *entry;
char *buffer;
apr_size_t size;
/* find the entry group that will hold the key.
*/
group_index = get_group_index(&cache, key, key_len, to_find, scratch_pool);
if (group_index == NO_INDEX)
return SVN_NO_ERROR;
/* Serialize data data.
*/
if (item)
SVN_ERR(serializer(&buffer, &size, item, scratch_pool));
/* The actual cache data access needs to sync'ed
*/
SVN_ERR(lock_cache(cache));
/* if necessary, enlarge the insertion window.
*/
if ( item != NULL
&& cache->data_size / 4 > size
&& ensure_data_insertable(cache, size))
{
/* 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) posion within data buffer.
*/
entry = find_entry(cache, group_index, to_find, TRUE);
entry->size = size;
entry->offset = cache->current_data;
#ifdef SVN_DEBUG_CACHE_MEMBUFFER
/* Remember original content, type and key (hashes)
*/
SVN_ERR(store_content_part(tag, buffer, size, scratch_pool));
memcpy(&entry->tag, tag, sizeof(*tag));
#endif
/* Copy the serialized item data into the cache.
*/
if (size)
memcpy(cache->data + entry->offset, buffer, size);
/* Link the entry properly.
*/
insert_entry(cache, entry);
cache->total_writes++;
}
else
{
/* if there is already an entry for this key, drop it.
*/
find_entry(cache, group_index, to_find, TRUE);
}
/* done here -> unlock the cache
*/
return unlock_cache(cache, 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
* 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 void *key,
apr_size_t key_len,
void **item,
svn_cache__deserialize_func_t deserializer,
DEBUG_CACHE_MEMBUFFER_TAG_ARG
apr_pool_t *result_pool)
{
apr_uint32_t group_index;
unsigned char to_find[KEY_SIZE];
entry_t *entry;
char *buffer;
apr_size_t size;
/* find the entry group that will hold the key.
*/
group_index = get_group_index(&cache, key, key_len, to_find, result_pool);
if (group_index == NO_INDEX)
{
/* Some error occured, return "item not found".
*/
*item = NULL;
return SVN_NO_ERROR;
}
SVN_ERR(lock_cache(cache));
/* 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.
*/
*item = NULL;
return unlock_cache(cache, SVN_NO_ERROR);
}
size = ALIGN_VALUE(entry->size);
buffer = ALIGN_POINTER(apr_palloc(result_pool, size + ITEM_ALIGNMENT-1));
memcpy(buffer, (const char*)cache->data + entry->offset, 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, result_pool));
SVN_ERR(assert_equal_tags(&entry->tag, tag));
#endif
/* update hit statistics
*/
entry->hit_count++;
cache->hit_count++;
cache->total_hits++;
SVN_ERR(unlock_cache(cache, SVN_NO_ERROR));
/* re-construct the original data object from its serialized form.
*/
return deserializer(item, buffer, entry->size, result_pool);
}
/* Look for the cache entry identified by KEY and KEY_LEN. 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 void *key,
apr_size_t key_len,
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;
unsigned char to_find[KEY_SIZE];
entry_t *entry;
svn_error_t *err = SVN_NO_ERROR;
group_index = get_group_index(&cache, key, key_len, to_find, result_pool);
SVN_ERR(lock_cache(cache));
entry = find_entry(cache, group_index, to_find, FALSE);
cache->total_reads++;
if (entry == NULL)
{
*item = NULL;
*found = FALSE;
}
else
{
*found = TRUE;
entry->hit_count++;
cache->hit_count++;
cache->total_hits++;
#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,
(const char*)cache->data + entry->offset,
entry->size,
result_pool));
SVN_ERR(assert_equal_tags(&entry->tag, tag));
#endif
err = deserializer(item,
(const char*)cache->data + entry->offset,
entry->size,
baton,
result_pool);
}
/* done here -> unlock the cache
*/
return unlock_cache(cache, err);
}
/* Look for the cache entry identified by KEY and KEY_LEN. 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 void *key,
apr_size_t key_len,
svn_cache__partial_setter_func_t func,
void *baton,
DEBUG_CACHE_MEMBUFFER_TAG_ARG
apr_pool_t *scratch_pool)
{
apr_uint32_t group_index;
unsigned char to_find[KEY_SIZE];
entry_t *entry;
svn_error_t *err = SVN_NO_ERROR;
/* cache item lookup
*/
group_index = get_group_index(&cache, key, key_len, to_find, scratch_pool);
SVN_ERR(lock_cache(cache));
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)
{
/* access the serialized cache item */
char *data = (char*)cache->data + entry->offset;
char *orig_data = data;
apr_size_t size = entry->size;
entry->hit_count++;
cache->hit_count++;
cache->total_writes++;
#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, data, size, scratch_pool));
SVN_ERR(assert_equal_tags(&entry->tag, tag));
#endif
/* modify it, preferrably in-situ.
*/
err = func(&data, &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);
}
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 (data != orig_data)
{
/* Remove the old entry and try to make space for the new one.
*/
drop_entry(cache, entry);
if ( (cache->data_size / 4 > size)
&& ensure_data_insertable(cache, size))
{
/* Write the new entry.
*/
entry->size = size;
entry->offset = cache->current_data;
if (size)
memcpy(cache->data + entry->offset, data, 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, data, size, scratch_pool));
memcpy(&entry->tag, tag, sizeof(*tag));
#endif
}
}
}
}
/* done here -> unlock the cache
*/
return unlock_cache(cache, err);
}
/* 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 achive global resource usage fairness.
*
* To accomodate items from multiple resources, the individual keys must be
* unique over all sources. This is achived by simply adding a prefix key
* that unambigously 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 byte sequence to any key passed to us.
* This makes (very likely) our keys different from all keys used
* by other svn_membuffer_cache_t instances.
*/
unsigned char prefix [APR_MD5_DIGESTSIZE];
/* A copy of the unmodified prefix. It is being used as a user-visible
* ID for this cache instance.
*/
const char* full_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;
/* a pool for temporary allocations during get() and set()
*/
apr_pool_t *pool;
/* an internal counter that is used to clear the pool from time to time
* but not too frequently.
*/
int alloc_counter;
#ifdef SVN_DEBUG_CACHE_MEMBUFFER
/* Invariant tag info for all items stored by this cache instance.
*/
char prefix_tail[PREFIX_TAIL_LEN];
#endif
} svn_membuffer_cache_t;
/* After an estimated ALLOCATIONS_PER_POOL_CLEAR allocations, we should
* clear the svn_membuffer_cache_t.pool to keep memory consumption in check.
*/
#define ALLOCATIONS_PER_POOL_CLEAR 10
/* Basically concatenate PREFIX and KEY and return the result in FULL_KEY.
* Allocations will be made in POOL.
*/
static void
combine_key(const void *prefix,
apr_size_t prefix_len,
const void *key,
apr_ssize_t key_len,
void **full_key,
apr_size_t *full_key_len,
apr_pool_t *pool)
{
if (key_len == APR_HASH_KEY_STRING)
key_len = strlen((const char *) key);
*full_key_len = prefix_len + key_len;
*full_key = apr_palloc(pool, *full_key_len);
memcpy(*full_key, prefix, prefix_len);
memcpy((char *)*full_key + prefix_len, key, key_len);
}
/* Implement svn_cache__vtable_t.get
*/
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;
/* construct the full, i.e. globally unique, key by adding
* this cache instances' prefix
*/
void *full_key;
apr_size_t full_key_len;
DEBUG_CACHE_MEMBUFFER_INIT_TAG
combine_key(cache->prefix,
sizeof(cache->prefix),
key,
cache->key_len,
&full_key,
&full_key_len,
cache->pool);
/* Look the item up. */
SVN_ERR(membuffer_cache_get(cache->membuffer,
full_key,
full_key_len,
value_p,
cache->deserializer,
DEBUG_CACHE_MEMBUFFER_TAG
result_pool));
/* We don't need more the key anymore.
* But since we allocate only small amounts of data per get() call and
* apr_pool_clear is somewhat expensive, we clear it only now and then.
*/
if (++cache->alloc_counter > ALLOCATIONS_PER_POOL_CLEAR)
{
apr_pool_clear(cache->pool);
cache->alloc_counter = 0;
}
/* return result */
*found = *value_p != NULL;
return SVN_NO_ERROR;
}
/* Implement svn_cache__vtable_t.set
*/
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;
void *full_key;
apr_size_t full_key_len;
DEBUG_CACHE_MEMBUFFER_INIT_TAG
/* we do some allocations below, so increase the allocation counter
* by a slightly larger amount. Free allocated memory every now and then.
*/
cache->alloc_counter += 3;
if (cache->alloc_counter > ALLOCATIONS_PER_POOL_CLEAR)
{
apr_pool_clear(cache->pool);
cache->alloc_counter = 0;
}
/* construct the full, i.e. globally unique, key by adding
* this cache instances' prefix
*/
combine_key(cache->prefix,
sizeof(cache->prefix),
key,
cache->key_len,
&full_key,
&full_key_len,
cache->pool);
/* (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,
full_key,
full_key_len,
value,
cache->serializer,
DEBUG_CACHE_MEMBUFFER_TAG
cache->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"));
}
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;
void *full_key;
apr_size_t full_key_len;
DEBUG_CACHE_MEMBUFFER_INIT_TAG
if (++cache->alloc_counter > ALLOCATIONS_PER_POOL_CLEAR)
{
apr_pool_clear(cache->pool);
cache->alloc_counter = 0;
}
combine_key(cache->prefix,
sizeof(cache->prefix),
key,
cache->key_len,
&full_key,
&full_key_len,
cache->pool);
SVN_ERR(membuffer_cache_get_partial(cache->membuffer,
full_key,
full_key_len,
value_p,
found,
func,
baton,
DEBUG_CACHE_MEMBUFFER_TAG
result_pool));
return SVN_NO_ERROR;
}
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;
void *full_key;
apr_size_t full_key_len;
DEBUG_CACHE_MEMBUFFER_INIT_TAG
combine_key(cache->prefix,
sizeof(cache->prefix),
key,
cache->key_len,
&full_key,
&full_key_len,
scratch_pool);
SVN_ERR(membuffer_cache_set_partial(cache->membuffer,
full_key,
full_key_len,
func,
baton,
DEBUG_CACHE_MEMBUFFER_TAG
scratch_pool));
return SVN_NO_ERROR;
}
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 (size < cache->membuffer->data_size / 4)
&& (size < APR_UINT32_MAX - ITEM_ALIGNMENT);
}
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 frontend specific data */
info->id = apr_pstrdup(result_pool, cache->full_prefix);
/* collect info from shared cache backend */
info->data_size = 0;
info->used_size = 0;
info->total_size = 0;
info->used_entries = 0;
info->total_entries = 0;
for (i = 0; i < cache->membuffer->segment_count; ++i)
{
svn_membuffer_t *segment = cache->membuffer + i;
SVN_ERR(lock_cache(segment));
info->data_size += segment->data_size;
info->used_size += segment->data_used;
info->total_size += segment->data_size +
segment->group_count * GROUP_SIZE * sizeof(entry_t);
info->used_entries += segment->used_entries;
info->total_entries += segment->group_count * GROUP_SIZE;
SVN_ERR(unlock_cache(segment, SVN_NO_ERROR));
}
return SVN_NO_ERROR;
}
/* the v-table for membuffer-based caches
*/
static svn_cache__vtable_t membuffer_cache_vtable = {
svn_membuffer_cache_get,
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
};
/* standard serialization function for svn_stringbuf_t items.
* Implements svn_cache__serialize_func_t.
*/
static svn_error_t *
serialize_svn_stringbuf(char **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,
char *buffer,
apr_size_t buffer_size,
apr_pool_t *result_pool)
{
svn_string_t *value_str = apr_palloc(result_pool, sizeof(svn_string_t));
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_pool_t *pool)
{
svn_checksum_t *checksum;
/* allocate the cache header structures
*/
svn_cache__t *wrapper = apr_pcalloc(pool, sizeof(*wrapper));
svn_membuffer_cache_t *cache = apr_palloc(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->full_prefix = apr_pstrdup(pool, prefix);
cache->key_len = klen;
cache->pool = svn_pool_create(pool);
cache->alloc_counter = 0;
/* for performance reasons, we don't actually store the full prefix but a
* hash value of it
*/
SVN_ERR(svn_checksum(&checksum,
svn_checksum_md5,
prefix,
strlen(prefix),
pool));
memcpy(cache->prefix, checksum->digest, sizeof(cache->prefix));
#ifdef SVN_DEBUG_CACHE_MEMBUFFER
/* Initialize cache debugging support.
*/
get_prefix_tail(prefix, cache->prefix_tail);
#endif
/* initialize the generic cache wrapper
*/
wrapper->vtable = &membuffer_cache_vtable;
wrapper->cache_internal = cache;
wrapper->error_handler = 0;
wrapper->error_baton = 0;
*cache_p = wrapper;
return SVN_NO_ERROR;
}