summaryrefslogtreecommitdiff
path: root/subversion/libsvn_subr/cache-membuffer.c
diff options
context:
space:
mode:
Diffstat (limited to 'subversion/libsvn_subr/cache-membuffer.c')
-rw-r--r--subversion/libsvn_subr/cache-membuffer.c1916
1 files changed, 1348 insertions, 568 deletions
diff --git a/subversion/libsvn_subr/cache-membuffer.c b/subversion/libsvn_subr/cache-membuffer.c
index 7aa90cd..87ac961 100644
--- a/subversion/libsvn_subr/cache-membuffer.c
+++ b/subversion/libsvn_subr/cache-membuffer.c
@@ -27,13 +27,17 @@
#include "svn_pools.h"
#include "svn_checksum.h"
-#include "md5.h"
#include "svn_private_config.h"
-#include "cache.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_pseudo_md5.h"
+#include "private/svn_string_private.h"
+
+#include "cache.h"
+#include "fnv1a.h"
/*
* This svn_cache__t implementation actually consists of two parts:
@@ -44,11 +48,15 @@
* 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.
+ * 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.
+ * 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.
@@ -56,23 +64,31 @@
* 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.
+ * 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. 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 accommodate 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.
+ * 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,
- * a randomized variant of LFU is used (see ensure_data_insertable for
+ * 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
@@ -86,14 +102,20 @@
* 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().
+ * 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 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.
+ * 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.
*
* 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
@@ -108,7 +130,7 @@
* 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 head before 1.8.
+ * we had before 1.8.
*/
#ifdef WIN32
# define USE_SIMPLE_MUTEX 1
@@ -116,14 +138,11 @@
# define USE_SIMPLE_MUTEX 0
#endif
-/* A 16-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 16
-
/* 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
@@ -170,11 +189,34 @@
*/
#define MAX_ITEM_SIZE ((apr_uint32_t)(0 - ITEM_ALIGNMENT))
-/* A 16 byte key type. We use that to identify cache entries.
- * The notation as just two integer values will cause many compilers
- * to create better code.
+/* 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.
+ */
+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. */
+ apr_size_t key_len;
+} 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.
*/
-typedef apr_uint64_t entry_key_t[2];
+typedef struct full_key_t
+{
+ /* Reduced form identifying the cache entry (if such an entry exists). */
+ entry_key_t entry_key;
+
+ /* 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;
/* Debugging / corruption detection support.
* If you define this macro, the getter functions will performed expensive
@@ -186,9 +228,9 @@ typedef apr_uint64_t entry_key_t[2];
/* 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.
+ * the last 15 bytes + \0 as plaintext for easy identification by the dev.
*/
-#define PREFIX_TAIL_LEN 8
+#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
@@ -196,20 +238,20 @@ typedef apr_uint64_t entry_key_t[2];
*/
typedef struct entry_tag_t
{
- /* MD5 checksum over the serialized the item data.
+ /* MD5 checksum over the serialized item data.
*/
- unsigned char content_hash [APR_MD5_DIGESTSIZE];
+ 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];
+ 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];
+ 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")
@@ -222,36 +264,36 @@ typedef struct entry_tag_t
} 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,
- entry_key_t prefix_hash,
- char *prefix_tail,
+ const full_key_t *prefix_key,
const void *key,
apr_size_t key_len,
apr_pool_t *pool)
{
svn_checksum_t *checksum;
+ const char *prefix = prefix_key->full_key.data;
+ 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,
key,
key_len,
pool));
- memcpy(tag->prefix_hash, prefix_hash, sizeof(tag->prefix_hash));
+ memcpy(tag->prefix_hash, prefix_key->entry_key.fingerprint,
+ sizeof(tag->prefix_hash));
memcpy(tag->key_hash, checksum->digest, sizeof(tag->key_hash));
- memcpy(tag->prefix_tail, prefix_tail, sizeof(tag->prefix_tail));
+
+ memset(tag->prefix_tail, 0, sizeof(tag->key_hash));
+ memcpy(tag->prefix_tail, prefix, prefix_len + 1);
tag->key_len = key_len;
@@ -261,7 +303,7 @@ static svn_error_t *store_key_part(entry_tag_t *tag,
/* Initialize the content hash member of TAG.
*/
static svn_error_t* store_content_part(entry_tag_t *tag,
- const char *data,
+ const void *data,
apr_size_t size,
apr_pool_t *pool)
{
@@ -303,17 +345,17 @@ static svn_error_t* assert_equal_tags(const entry_tag_t *lhs,
#define DEBUG_CACHE_MEMBUFFER_TAG tag,
-#define DEBUG_CACHE_MEMBUFFER_INIT_TAG \
- entry_tag_t _tag; \
- entry_tag_t *tag = &_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));
+#define DEBUG_CACHE_MEMBUFFER_INIT_TAG(pool) \
+ entry_tag_t _tag; \
+ entry_tag_t *tag = &_tag; \
+ if (key) \
+ SVN_ERR(store_key_part(tag, \
+ &cache->prefix, \
+ key, \
+ cache->key_len == APR_HASH_KEY_STRING \
+ ? strlen((const char *) key) \
+ : cache->key_len, \
+ pool));
#else
@@ -321,14 +363,14 @@ static svn_error_t* assert_equal_tags(const entry_tag_t *lhs,
*/
#define DEBUG_CACHE_MEMBUFFER_TAG_ARG
#define DEBUG_CACHE_MEMBUFFER_TAG
-#define DEBUG_CACHE_MEMBUFFER_INIT_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.
+ * list of used entries per cache level.
*/
typedef struct entry_t
{
@@ -336,11 +378,13 @@ typedef struct entry_t
*/
entry_key_t key;
- /* The offset of the cached item's serialized data within the data buffer.
+ /* 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.
+ /* 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;
@@ -348,23 +392,27 @@ typedef struct entry_t
/* Number of (read) hits for this entry. Will be reset upon write.
* Only valid for used entries.
*/
- apr_uint32_t hit_count;
+ 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 membuffer_cache_t.last member. NO_INDEX also implies
- * that the data buffer is not used beyond offset+size.
+ * 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 membuffer_cache_t.first member.
+ * 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.
*/
@@ -372,39 +420,68 @@ typedef struct entry_t
#endif
} entry_t;
-/* We group dictionary entries to make this GROUP-SIZE-way associative.
+/* Group header struct.
*/
-typedef struct entry_group_t
+typedef struct group_header_t
{
/* number of entries used [0 .. USED-1] */
apr_uint32_t used;
- /* the actual entries */
- entry_t entries[GROUP_SIZE];
-} entry_group_t;
+ /* 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;
-/* The cache header structure.
+ /* 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.
*/
-struct svn_membuffer_t
+#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
{
- /* 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;
+ /* group globals */
+ group_header_t header;
- /* The dictionary, GROUP_SIZE * group_count entries long. Never NULL.
- */
- entry_group_t *directory;
+ /* padding and also room for future extensions */
+ char padding[GROUP_BLOCK_SIZE - sizeof(group_header_t)
+ - sizeof(entry_t) * GROUP_SIZE];
- /* Flag array with group_count / GROUP_INIT_GRANULARITY _bit_ elements.
- * Allows for efficiently marking groups as "not initialized".
- */
- unsigned char *group_initialized;
+ /* the actual entries */
+ entry_t entries[GROUP_SIZE];
- /* Size of dictionary in groups. Must be > 0.
- */
- apr_uint32_t group_count;
+} 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.
@@ -425,18 +502,61 @@ struct svn_membuffer_t
apr_uint32_t next;
- /* Pointer to the data buffer, data_size bytes long. Never NULL.
+ /* First offset in the caches DATA buffer that belongs to this level.
*/
- unsigned char *data;
+ apr_uint64_t start_offset;
- /* Size of data buffer in bytes. Must be > 0.
+ /* Size of data buffer allocated to this level in bytes. Must be > 0.
*/
- apr_uint64_t data_size;
+ 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;
+
+ /* 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;
@@ -446,45 +566,63 @@ struct svn_membuffer_t
*/
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.
+ */
- /* Number of used dictionary entries, i.e. number of cached items.
- * In conjunction with hit_count, this is used calculate the average
- * hit count as part of the randomized LFU algorithm.
+ /* 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.
*/
- apr_uint32_t used_entries;
+ cache_level_t l1;
- /* 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.
+ /* 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.
*/
- apr_uint64_t hit_count;
+ 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.
+ * 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.
+ * 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.
+ * 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
+#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.
*/
-# if USE_SIMPLE_MUTEX
svn_mutex__t *lock;
-# else
+#elif (APR_HAS_THREADS && !USE_SIMPLE_MUTEX)
+ /* Same for read-write lock. */
apr_thread_rwlock_t *lock;
-# endif
/* If set, write access will wait until they get exclusive access.
* Otherwise, they will become no-ops if the segment is currently
@@ -498,42 +636,37 @@ struct svn_membuffer_t
*/
#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)))
-
/* 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
-# if USE_SIMPLE_MUTEX
+#if (APR_HAS_THREADS && USE_SIMPLE_MUTEX)
return svn_mutex__lock(cache->lock);
-# else
+#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"));
}
-# endif
-#endif
+
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
-# if USE_SIMPLE_MUTEX
-
+#if (APR_HAS_THREADS && USE_SIMPLE_MUTEX)
return svn_mutex__lock(cache->lock);
-
-# else
-
+#elif (APR_HAS_THREADS && !USE_SIMPLE_MUTEX)
if (cache->lock)
{
apr_status_t status;
@@ -556,9 +689,10 @@ write_lock_cache(svn_membuffer_t *cache, svn_boolean_t *success)
_("Can't write-lock cache mutex"));
}
-# endif
-#endif
return SVN_NO_ERROR;
+#else
+ return SVN_NO_ERROR;
+#endif
}
/* If locking is supported for CACHE, acquire an unconditional write lock
@@ -567,36 +701,29 @@ write_lock_cache(svn_membuffer_t *cache, svn_boolean_t *success)
static svn_error_t *
force_write_lock_cache(svn_membuffer_t *cache)
{
-#if APR_HAS_THREADS
-# if USE_SIMPLE_MUTEX
-
+#if (APR_HAS_THREADS && USE_SIMPLE_MUTEX)
return svn_mutex__lock(cache->lock);
-
-# else
-
+#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"));
-# endif
-#endif
return SVN_NO_ERROR;
+#else
+ return SVN_NO_ERROR;
+#endif
}
/* If locking is supported for CACHE, release the current lock
- * (read or write).
+ * (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
-# if USE_SIMPLE_MUTEX
-
+#if (APR_HAS_THREADS && USE_SIMPLE_MUTEX)
return svn_mutex__unlock(cache->lock, err);
-
-# else
-
+#elif (APR_HAS_THREADS && !USE_SIMPLE_MUTEX)
if (cache->lock)
{
apr_status_t status = apr_thread_rwlock_unlock(cache->lock);
@@ -607,13 +734,14 @@ unlock_cache(svn_membuffer_t *cache, svn_error_t *err)
return svn_error_wrap_apr(status, _("Can't unlock cache mutex"));
}
-# endif
-#endif
return err;
+#else
+ return err;
+#endif
}
-/* If supported, guard the execution of EXPR with a read lock to cache.
- * Macro has been modeled after SVN_MUTEX__WITH_LOCK.
+/* 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 { \
@@ -621,8 +749,8 @@ do { \
SVN_ERR(unlock_cache(cache, (expr))); \
} while (0)
-/* If supported, guard the execution of EXPR with a write lock to cache.
- * Macro has been modeled after SVN_MUTEX__WITH_LOCK.
+/* 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
@@ -647,6 +775,132 @@ do { \
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.
*/
@@ -668,6 +922,96 @@ get_index(svn_membuffer_t *cache, entry_t *entry)
+ (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.
*/
@@ -678,83 +1022,84 @@ drop_entry(svn_membuffer_t *cache, entry_t *entry)
*/
apr_uint32_t idx = get_index(cache, entry);
apr_uint32_t group_index = idx / GROUP_SIZE;
- entry_group_t *group = &cache->directory[group_index];
- apr_uint32_t last_in_group = group_index * GROUP_SIZE + group->used - 1;
+ 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);
- /* Only valid to be called for used entries.
- */
- assert(idx <= last_in_group);
+ cache_level_t *level = get_cache_level(cache, entry);
/* 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;
+ if (idx == level->next)
+ level->next = entry->next;
else
- if (entry->next == cache->next)
+ 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 */
- cache->current_data = 0;
+ level->current_data = level->start_offset;
}
else
{
/* insertion may start right behind the previous entry */
entry_t *previous = get_entry(cache, entry->previous);
- cache->current_data = ALIGN_VALUE( previous->offset
+ level->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;
+ 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)
+ if (idx != last_in_group)
{
/* copy the last used entry to the removed entry's index
*/
- *entry = group->entries[group->used-1];
+ *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 == cache->next)
- cache->next = idx;
+ if (last_in_group == level->next)
+ level->next = idx;
if (entry->previous == NO_INDEX)
- cache->first = idx;
+ level->first = idx;
else
get_entry(cache, entry->previous)->next = idx;
if (entry->next == NO_INDEX)
- cache->last = idx;
+ level->last = idx;
else
get_entry(cache, entry->next)->previous = idx;
}
/* Update the number of used entries.
*/
- group->used--;
+ 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
@@ -769,62 +1114,30 @@ insert_entry(svn_membuffer_t *cache, entry_t *entry)
apr_uint32_t idx = get_index(cache, entry);
apr_uint32_t group_index = idx / GROUP_SIZE;
entry_group_t *group = &cache->directory[group_index];
- entry_t *next = cache->next == NO_INDEX
- ? NULL
- : get_entry(cache, cache->next);
+ 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 == cache->current_data);
- assert(idx == group_index * GROUP_SIZE + group->used);
- cache->current_data = ALIGN_VALUE(entry->offset + entry->size);
+ 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->used++;
+ group->header.used++;
/* 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;
- }
+ chain_entry(cache, level, entry, idx);
/* The current insertion position must never point outside our
* data buffer.
*/
- assert(cache->current_data <= cache->data_size);
+ assert(level->current_data <= level->start_offset + level->size);
}
/* Map a KEY of 16 bytes to the CACHE and group that shall contain the
@@ -832,13 +1145,19 @@ insert_entry(svn_membuffer_t *cache, entry_t *entry)
*/
static apr_uint32_t
get_group_index(svn_membuffer_t **cache,
- entry_key_t key)
+ const entry_key_t *key)
{
svn_membuffer_t *segment0 = *cache;
-
- /* select the cache segment to use. they have all the same group_count */
- *cache = &segment0[key[0] & (segment0->segment_count -1)];
- return key[1] % segment0->group_count;
+ 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
@@ -849,48 +1168,25 @@ 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;
+ if (hits_removed)
+ {
+ entry->hit_count -= hits_removed;
+ }
+ else
+ {
+ entry->priority /= 2;
+ }
}
-/* 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.
+/* Return whether the keys in LHS and RHS match.
*/
-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)
+static svn_boolean_t
+entry_keys_match(const entry_key_t *lhs,
+ const entry_key_t *rhs)
{
- 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)
- last_index = cache->group_count;
-
- for (i = first_index; i < last_index; ++i)
- cache->directory[i].used = 0;
-
- /* 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 (lhs->fingerprint[0] == rhs->fingerprint[0])
+ && (lhs->fingerprint[1] == rhs->fingerprint[1])
+ && (lhs->key_len == rhs->key_len);
}
/* Given the GROUP_INDEX that shall contain an entry with the hash key
@@ -904,11 +1200,15 @@ initialize_group(svn_membuffer_t *cache, apr_uint32_t group_index)
* 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 apr_uint64_t to_find[2],
+ const full_key_t *to_find,
svn_boolean_t find_empty)
{
entry_group_t *group;
@@ -929,8 +1229,7 @@ find_entry(svn_membuffer_t *cache,
entry = &group->entries[0];
/* initialize entry for the new key */
- entry->key[0] = to_find[0];
- entry->key[1] = to_find[1];
+ entry->key = to_find->entry_key;
}
return entry;
@@ -938,43 +1237,116 @@ find_entry(svn_membuffer_t *cache,
/* try to find the matching entry
*/
- for (i = 0; i < group->used; ++i)
- if ( to_find[0] == group->entries[i].key[0]
- && to_find[1] == group->entries[i].key[1])
- {
- /* found it
- */
- entry = &group->entries[i];
- if (find_empty)
- drop_entry(cache, entry);
- else
- return 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 there is no full key to compare, 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)
{
- /* if there is no empty entry, delete the oldest entry
+ /* There is no empty entry in the chain, try chaining a spare group.
*/
- if (group->used == GROUP_SIZE)
+ 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.
*/
- entry = &group->entries[rand() % GROUP_SIZE];
- for (i = 1; i < GROUP_SIZE; ++i)
- if (entry->hit_count > group->entries[i].hit_count)
- entry = &group->entries[i];
+ 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 != &group->entries[i])
+ if (entry != &to_shrink->entries[i])
let_entry_age(cache, entry);
drop_entry(cache, entry);
@@ -982,9 +1354,8 @@ find_entry(svn_membuffer_t *cache,
/* initialize entry for the new key
*/
- entry = &group->entries[group->used];
- entry->key[0] = to_find[0];
- entry->key[1] = to_find[1];
+ entry = &group->entries[group->header.used];
+ entry->key = to_find->entry_key;
}
return entry;
@@ -997,6 +1368,7 @@ 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
@@ -1010,141 +1382,191 @@ move_entry(svn_membuffer_t *cache, entry_t *entry)
* 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)
+ if (entry->offset != level->current_data)
{
- memmove(cache->data + cache->current_data,
+ memmove(cache->data + level->current_data,
cache->data + entry->offset,
size);
- entry->offset = cache->current_data;
+ entry->offset = level->current_data;
}
/* The insertion position is now directly behind this entry.
*/
- cache->current_data = entry->offset + size;
- cache->next = entry->next;
+ level->current_data = entry->offset + size;
+ level->next = entry->next;
/* The current insertion position must never point outside our
* data buffer.
*/
- assert(cache->current_data <= cache->data_size);
+ 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);
}
-/* 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
+/* 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(svn_membuffer_t *cache, apr_size_t size)
+ensure_data_insertable_l2(svn_membuffer_t *cache,
+ entry_t *to_fit_in)
{
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;
+ apr_size_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:
- * - 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.
+ * - 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->next == NO_INDEX
- ? cache->data_size
- : get_entry(cache, cache->next)->offset;
+ 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 >= size + cache->current_data)
+ if (end >= to_fit_in->size + cache->l2.current_data)
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.
+ /* 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 (if even in case of faulty
+ * heuristics). Therefore, give up after some time.
*/
- if (2 * drop_size > size)
+ 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->next == NO_INDEX)
+ 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->current_data = 0;
- cache->next = cache->first;
+ cache->l2.current_data = cache->l2.start_offset;
+ cache->l2.next = cache->l2.first;
}
else
{
- entry = get_entry(cache, cache->next);
+ svn_boolean_t keep;
+ entry = get_entry(cache, cache->l2.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)
+ if (to_fit_in->priority < SVN_CACHE__MEMBUFFER_DEFAULT_PRIORITY)
{
- move_entry(cache, entry);
+ /* 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
{
- svn_boolean_t keep;
+ /* 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;
+ }
- if (cache->hit_count > cache->used_entries)
- {
- /* 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;
+ /* keepers or destroyers? */
+ if (keep)
+ {
+ /* Moving entries around is not for free -> track costs. */
+ moved_size += entry->size;
+ moved_count++;
- keep = entry->hit_count >= threshold;
- }
- else
- {
- /* general hit count is low. Keep everything that got hit
- * at all and assign some 50% survival chance to everything
- * else.
- */
- keep = (entry->hit_count > 0) || (rand() & 1);
- }
+ 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;
- /* keepers or destroyers? */
- if (keep)
- {
- move_entry(cache, entry);
- }
- else
- {
- /* 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.
- */
- drop_size += entry->size;
- drop_entry(cache, entry);
- }
+ drop_entry(cache, entry);
}
}
}
@@ -1153,26 +1575,72 @@ ensure_data_insertable(svn_membuffer_t *cache, apr_size_t size)
* 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.
+/* 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.
*
- * Also, satisfy our buffer alignment needs 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 because it is
+ * too large.
*/
-static void* secure_aligned_alloc(apr_pool_t *pool,
- apr_size_t size,
- svn_boolean_t zero)
+static svn_boolean_t
+ensure_data_insertable_l1(svn_membuffer_t *cache, apr_size_t size)
{
- void* memory = apr_palloc(pool, size + ITEM_ALIGNMENT);
- if (memory != NULL)
+ /* 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)
{
- memory = ALIGN_POINTER(memory);
- if (zero)
- memset(memory, 0, size);
+ /* 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 >= size + cache->l1.current_data)
+ 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);
+ }
+ }
}
- return memory;
+ /* This will never be reached. But if it was, "can't insert" was the
+ * right answer. */
}
svn_error_t *
@@ -1188,6 +1656,8 @@ svn_cache__membuffer_cache_create(svn_membuffer_t **cache,
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;
@@ -1262,8 +1732,8 @@ svn_cache__membuffer_cache_create(svn_membuffer_t **cache,
*/
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);
+ 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.
@@ -1272,13 +1742,13 @@ svn_cache__membuffer_cache_create(svn_membuffer_t **cache,
*/
data_size = ALIGN_VALUE(total_size - directory_size + 1) - ITEM_ALIGNMENT;
- /* For cache sizes > 4TB, individual cache segments will be larger
- * than 16GB allowing for >4GB entries. But caching chunks larger
- * than 4GB is simply not supported.
+ /* 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 / 4 > MAX_ITEM_SIZE
+ max_entry_size = data_size / 8 > MAX_ITEM_SIZE
? MAX_ITEM_SIZE
- : data_size / 4;
+ : data_size / 8;
/* to keep the entries small, we use 32 bit indexes only
* -> we need to ensure that no more then 4G entries exist.
@@ -1291,6 +1761,11 @@ svn_cache__membuffer_cache_create(svn_membuffer_t **cache,
? (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)
{
@@ -1298,7 +1773,11 @@ svn_cache__membuffer_cache_create(svn_membuffer_t **cache,
*/
c[seg].segment_count = (apr_uint32_t)segment_count;
- c[seg].group_count = group_count;
+ 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;
+
c[seg].directory = apr_pcalloc(pool,
group_count * sizeof(entry_group_t));
@@ -1306,18 +1785,30 @@ svn_cache__membuffer_cache_create(svn_membuffer_t **cache,
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;
+ /* 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].hit_count = 0;
c[seg].total_reads = 0;
c[seg].total_writes = 0;
c[seg].total_hits = 0;
@@ -1332,17 +1823,14 @@ svn_cache__membuffer_cache_create(svn_membuffer_t **cache,
return svn_error_wrap_apr(APR_ENOMEM, "OOM");
}
-#if APR_HAS_THREADS
+#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.
*/
-# if USE_SIMPLE_MUTEX
-
SVN_ERR(svn_mutex__init(&c[seg].lock, thread_safe, pool));
-
-# else
-
+#elif (APR_HAS_THREADS && !USE_SIMPLE_MUTEX)
+ /* Same for read-write lock. */
c[seg].lock = NULL;
if (thread_safe)
{
@@ -1352,8 +1840,6 @@ svn_cache__membuffer_cache_create(svn_membuffer_t **cache,
return svn_error_wrap_apr(status, _("Can't create cache mutex"));
}
-# endif
-
/* Select the behavior of write operations.
*/
c[seg].allow_blocking_writes = allow_blocking_writes;
@@ -1366,6 +1852,61 @@ svn_cache__membuffer_cache_create(svn_membuffer_t **cache,
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.
*
@@ -1375,7 +1916,7 @@ svn_cache__membuffer_cache_create(svn_membuffer_t **cache,
static svn_error_t *
entry_exists_internal(svn_membuffer_t *cache,
apr_uint32_t group_index,
- entry_key_t to_find,
+ const full_key_t *to_find,
svn_boolean_t *found)
{
*found = find_entry(cache, group_index, to_find, FALSE) != NULL;
@@ -1388,7 +1929,7 @@ entry_exists_internal(svn_membuffer_t *cache,
static svn_error_t *
entry_exists(svn_membuffer_t *cache,
apr_uint32_t group_index,
- entry_key_t to_find,
+ const full_key_t *to_find,
svn_boolean_t *found)
{
WITH_READ_LOCK(cache,
@@ -1400,10 +1941,43 @@ entry_exists(svn_membuffer_t *cache,
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;
+ }
-/* Try to insert the serialized item given in BUFFER with SIZE into
- * the group GROUP_INDEX of CACHE and uniquely identify it by hash
- * value TO_FIND.
+ /* 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,
@@ -1411,17 +1985,21 @@ entry_exists(svn_membuffer_t *cache,
* be inserted.
*
* Note: This function requires the caller to serialization access.
- * Don't call it directly, call membuffer_cache_get_partial instead.
+ * Don't call it directly, call membuffer_cache_set instead.
*/
static svn_error_t *
membuffer_cache_set_internal(svn_membuffer_t *cache,
- entry_key_t to_find,
+ const full_key_t *to_find,
apr_uint32_t group_index,
char *buffer,
- apr_size_t size,
+ 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 = item_size + to_find->entry_key.key_len;
+
/* first, look for a previous entry for the given key */
entry_t *entry = find_entry(cache, group_index, to_find, FALSE);
@@ -1435,18 +2013,23 @@ membuffer_cache_set_internal(svn_membuffer_t *cache,
*/
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, size, scratch_pool));
+ SVN_ERR(store_content_part(tag, buffer, item_size, scratch_pool));
memcpy(&entry->tag, tag, sizeof(*tag));
#endif
- if (size)
- memcpy(cache->data + entry->offset, buffer, size);
+ 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++;
return SVN_NO_ERROR;
@@ -1454,9 +2037,8 @@ membuffer_cache_set_internal(svn_membuffer_t *cache,
/* if necessary, enlarge the insertion window.
*/
- if ( buffer != NULL
- && cache->max_entry_size >= size
- && ensure_data_insertable(cache, size))
+ 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
@@ -1464,13 +2046,14 @@ membuffer_cache_set_internal(svn_membuffer_t *cache,
*/
entry = find_entry(cache, group_index, to_find, TRUE);
entry->size = size;
- entry->offset = cache->current_data;
+ 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, size, scratch_pool));
+ SVN_ERR(store_content_part(tag, buffer, item_size, scratch_pool));
memcpy(&entry->tag, tag, sizeof(*tag));
#endif
@@ -1481,8 +2064,12 @@ membuffer_cache_set_internal(svn_membuffer_t *cache,
/* Copy the serialized item data into the cache.
*/
- if (size)
- memcpy(cache->data + entry->offset, buffer, size);
+ 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++;
}
@@ -1511,9 +2098,10 @@ membuffer_cache_set_internal(svn_membuffer_t *cache,
*/
static svn_error_t *
membuffer_cache_set(svn_membuffer_t *cache,
- entry_key_t key,
+ 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)
{
@@ -1523,7 +2111,7 @@ membuffer_cache_set(svn_membuffer_t *cache,
/* find the entry group that will hold the key.
*/
- group_index = get_group_index(&cache, key);
+ group_index = get_group_index(&cache, &key->entry_key);
/* Serialize data data.
*/
@@ -1538,11 +2126,27 @@ membuffer_cache_set(svn_membuffer_t *cache,
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
@@ -1550,12 +2154,12 @@ membuffer_cache_set(svn_membuffer_t *cache,
* be done in POOL.
*
* Note: This function requires the caller to serialization access.
- * Don't call it directly, call membuffer_cache_get_partial instead.
+ * 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,
- entry_key_t to_find,
+ const full_key_t *to_find,
char **buffer,
apr_size_t *item_size,
DEBUG_CACHE_MEMBUFFER_TAG_ARG
@@ -1578,9 +2182,9 @@ membuffer_cache_get_internal(svn_membuffer_t *cache,
return 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);
+ 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
@@ -1592,18 +2196,16 @@ membuffer_cache_get_internal(svn_membuffer_t *cache,
/* Compare original content, type and key (hashes)
*/
- SVN_ERR(store_content_part(tag, *buffer, entry->size, result_pool));
+ 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
*/
- entry->hit_count++;
- cache->hit_count++;
- cache->total_hits++;
-
- *item_size = entry->size;
+ increment_hit_counters(cache, entry);
+ *item_size = entry->size - entry->key.key_len;
return SVN_NO_ERROR;
}
@@ -1615,7 +2217,7 @@ membuffer_cache_get_internal(svn_membuffer_t *cache,
*/
static svn_error_t *
membuffer_cache_get(svn_membuffer_t *cache,
- entry_key_t key,
+ const full_key_t *key,
void **item,
svn_cache__deserialize_func_t deserializer,
DEBUG_CACHE_MEMBUFFER_TAG_ARG
@@ -1627,7 +2229,7 @@ membuffer_cache_get(svn_membuffer_t *cache,
/* find the entry group that will hold the key.
*/
- group_index = get_group_index(&cache, key);
+ group_index = get_group_index(&cache, &key->entry_key);
WITH_READ_LOCK(cache,
membuffer_cache_get_internal(cache,
group_index,
@@ -1649,6 +2251,59 @@ membuffer_cache_get(svn_membuffer_t *cache,
}
/* 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.
*
@@ -1662,7 +2317,7 @@ membuffer_cache_get(svn_membuffer_t *cache,
static svn_error_t *
membuffer_cache_get_partial_internal(svn_membuffer_t *cache,
apr_uint32_t group_index,
- entry_key_t to_find,
+ const full_key_t *to_find,
void **item,
svn_boolean_t *found,
svn_cache__partial_getter_func_t deserializer,
@@ -1681,11 +2336,10 @@ membuffer_cache_get_partial_internal(svn_membuffer_t *cache,
}
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;
-
- entry->hit_count++;
- cache->hit_count++;
- cache->total_hits++;
+ increment_hit_counters(cache, entry);
#ifdef SVN_DEBUG_CACHE_MEMBUFFER
@@ -1697,19 +2351,12 @@ membuffer_cache_get_partial_internal(svn_membuffer_t *cache,
/* 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(store_content_part(tag, item_data, item_size, result_pool));
SVN_ERR(assert_equal_tags(&entry->tag, tag));
#endif
- return deserializer(item,
- (const char*)cache->data + entry->offset,
- entry->size,
- baton,
- result_pool);
+ return deserializer(item, item_data, item_size, baton, result_pool);
}
}
@@ -1721,7 +2368,7 @@ membuffer_cache_get_partial_internal(svn_membuffer_t *cache,
*/
static svn_error_t *
membuffer_cache_get_partial(svn_membuffer_t *cache,
- entry_key_t key,
+ const full_key_t *key,
void **item,
svn_boolean_t *found,
svn_cache__partial_getter_func_t deserializer,
@@ -1729,7 +2376,7 @@ membuffer_cache_get_partial(svn_membuffer_t *cache,
DEBUG_CACHE_MEMBUFFER_TAG_ARG
apr_pool_t *result_pool)
{
- apr_uint32_t group_index = get_group_index(&cache, key);
+ apr_uint32_t group_index = get_group_index(&cache, &key->entry_key);
WITH_READ_LOCK(cache,
membuffer_cache_get_partial_internal
@@ -1753,7 +2400,7 @@ membuffer_cache_get_partial(svn_membuffer_t *cache,
static svn_error_t *
membuffer_cache_set_partial_internal(svn_membuffer_t *cache,
apr_uint32_t group_index,
- entry_key_t to_find,
+ const full_key_t *to_find,
svn_cache__partial_setter_func_t func,
void *baton,
DEBUG_CACHE_MEMBUFFER_TAG_ARG
@@ -1771,12 +2418,12 @@ membuffer_cache_set_partial_internal(svn_membuffer_t *cache,
svn_error_t *err;
/* access the serialized cache item */
- char *data = (char*)cache->data + entry->offset;
- char *orig_data = data;
- apr_size_t size = entry->size;
+ 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;
- entry->hit_count++;
- cache->hit_count++;
+ increment_hit_counters(cache, entry);
cache->total_writes++;
#ifdef SVN_DEBUG_CACHE_MEMBUFFER
@@ -1784,19 +2431,19 @@ membuffer_cache_set_partial_internal(svn_membuffer_t *cache,
/* Check for overlapping entries.
*/
SVN_ERR_ASSERT(entry->next == NO_INDEX ||
- entry->offset + size
+ entry->offset + entry->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(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((void **)&data, &size, baton, scratch_pool);
+ err = func(&item_data, &item_size, baton, scratch_pool);
if (err)
{
@@ -1805,27 +2452,34 @@ membuffer_cache_set_partial_internal(svn_membuffer_t *cache,
* 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 (data != orig_data)
+ if (item_data != orig_data)
{
/* Remove the old entry and try to make space for the new one.
*/
drop_entry(cache, entry);
- if ( (cache->max_entry_size >= size)
- && ensure_data_insertable(cache, size))
+ if ( (cache->max_entry_size >= item_size + key_len)
+ && ensure_data_insertable_l1(cache, item_size + key_len))
{
/* Write the new entry.
*/
entry = find_entry(cache, group_index, to_find, TRUE);
- entry->size = size;
- entry->offset = cache->current_data;
- if (size)
- memcpy(cache->data + entry->offset, data, size);
+ 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.
*/
@@ -1837,7 +2491,7 @@ membuffer_cache_set_partial_internal(svn_membuffer_t *cache,
/* Remember original content, type and key (hashes)
*/
- SVN_ERR(store_content_part(tag, data, size, scratch_pool));
+ SVN_ERR(store_content_part(tag, item_data, item_size, scratch_pool));
memcpy(&entry->tag, tag, sizeof(*tag));
#endif
@@ -1854,7 +2508,7 @@ membuffer_cache_set_partial_internal(svn_membuffer_t *cache,
*/
static svn_error_t *
membuffer_cache_set_partial(svn_membuffer_t *cache,
- entry_key_t key,
+ const full_key_t *key,
svn_cache__partial_setter_func_t func,
void *baton,
DEBUG_CACHE_MEMBUFFER_TAG_ARG
@@ -1862,7 +2516,7 @@ membuffer_cache_set_partial(svn_membuffer_t *cache,
{
/* cache item lookup
*/
- apr_uint32_t group_index = get_group_index(&cache, key);
+ 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,
@@ -1907,44 +2561,26 @@ typedef struct svn_membuffer_cache_t
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.
+ * 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;
-
- /* A copy of the unmodified prefix. It is being used as a user-visible
- * ID for this cache instance.
- */
- const char* full_prefix;
+ full_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;
- /* Temporary buffer containing the hash key for the current access
- */
- entry_key_t combined_key;
-
- /* a pool for temporary allocations during get() and set()
- */
- apr_pool_t *pool;
+ /* priority class for all items written through this interface */
+ apr_uint32_t priority;
- /* an internal counter that is used to clear the pool from time to time
- * but not too frequently.
+ /* Temporary buffer containing the hash key for the current access
*/
- int alloc_counter;
+ full_key_t combined_key;
/* if enabled, this will serialize the access to this instance.
*/
svn_mutex__t *mutex;
-#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
@@ -1952,46 +2588,89 @@ typedef struct svn_membuffer_cache_t
*/
#define ALLOCATIONS_PER_POOL_CLEAR 10
-
/* 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_key(svn_membuffer_cache_t *cache,
- const void *key,
- apr_ssize_t key_len)
+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.entry_key.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);
- if (key_len < 16)
- {
- apr_uint32_t data[4] = { 0 };
- memcpy(data, key, key_len);
+ aligned_key_len = ALIGN_VALUE(key_len);
- svn__pseudo_md5_15((apr_uint32_t *)cache->combined_key, data);
- }
- else if (key_len < 32)
- {
- apr_uint32_t data[8] = { 0 };
- memcpy(data, key, key_len);
+ /* Combine keys. */
+ svn_membuf__ensure(&cache->combined_key.full_key,
+ aligned_key_len + prefix_len);
- svn__pseudo_md5_31((apr_uint32_t *)cache->combined_key, data);
- }
- else if (key_len < 64)
+ 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.entry_key.fingerprint[0];
+ cache->combined_key.entry_key.fingerprint[1]
+ ^= cache->prefix.entry_key.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)
+{
+ /* short, fixed-size keys are the most common case */
+ if (key_len != APR_HASH_KEY_STRING && key_len <= 16)
{
- apr_uint32_t data[16] = { 0 };
+ const apr_size_t prefix_len = cache->prefix.entry_key.key_len;
+
+ /* Copy of *key, padded with 0.
+ * We put it just behind the prefix already copied into the COMBINED_KEY.
+ * The buffer space has been allocated when the cache was created. */
+ apr_uint64_t *data = (void *)((char *)cache->combined_key.full_key.data +
+ prefix_len);
+ assert(prefix_len <= cache->combined_key.full_key.size - 16);
+ cache->combined_key.entry_key.key_len = prefix_len + 16;
+
+ data[0] = 0;
+ data[1] = 0;
memcpy(data, key, key_len);
- svn__pseudo_md5_63((apr_uint32_t *)cache->combined_key, data);
+ /* scramble key DATA. All of this must be reversible to prevent key
+ * collisions. So, we limit ourselves to xor and permutations. */
+ 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 namespace */
+ cache->combined_key.entry_key.fingerprint[0]
+ = data[0] ^ cache->prefix.entry_key.fingerprint[0];
+ cache->combined_key.entry_key.fingerprint[1]
+ = data[1] ^ cache->prefix.entry_key.fingerprint[1];
}
else
{
- apr_md5((unsigned char*)cache->combined_key, key, key_len);
+ /* longer or variably sized keys */
+ combine_long_key(cache, key, key_len);
}
-
- cache->combined_key[0] ^= cache->prefix[0];
- cache->combined_key[1] ^= cache->prefix[1];
}
/* Implement svn_cache__vtable_t.get (not thread-safe)
@@ -2005,7 +2684,7 @@ svn_membuffer_cache_get(void **value_p,
{
svn_membuffer_cache_t *cache = cache_void;
- DEBUG_CACHE_MEMBUFFER_INIT_TAG
+ DEBUG_CACHE_MEMBUFFER_INIT_TAG(result_pool)
/* special case */
if (key == NULL)
@@ -2023,7 +2702,7 @@ svn_membuffer_cache_get(void **value_p,
/* Look the item up. */
SVN_ERR(membuffer_cache_get(cache->membuffer,
- cache->combined_key,
+ &cache->combined_key,
value_p,
cache->deserializer,
DEBUG_CACHE_MEMBUFFER_TAG
@@ -2031,6 +2710,39 @@ svn_membuffer_cache_get(void **value_p,
/* 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;
}
@@ -2044,22 +2756,12 @@ svn_membuffer_cache_set(void *cache_void,
{
svn_membuffer_cache_t *cache = cache_void;
- DEBUG_CACHE_MEMBUFFER_INIT_TAG
+ DEBUG_CACHE_MEMBUFFER_INIT_TAG(scratch_pool)
/* special case */
if (key == NULL)
return SVN_NO_ERROR;
- /* 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)
- {
- svn_pool_clear(cache->pool);
- cache->alloc_counter = 0;
- }
-
/* construct the full, i.e. globally unique, key by adding
* this cache instances' prefix
*/
@@ -2069,11 +2771,12 @@ svn_membuffer_cache_set(void *cache_void,
* that the item will actually be cached afterwards.
*/
return membuffer_cache_set(cache->membuffer,
- cache->combined_key,
+ &cache->combined_key,
value,
cache->serializer,
+ cache->priority,
DEBUG_CACHE_MEMBUFFER_TAG
- cache->pool);
+ scratch_pool);
}
/* Implement svn_cache__vtable_t.iter as "not implemented"
@@ -2102,7 +2805,7 @@ svn_membuffer_cache_get_partial(void **value_p,
{
svn_membuffer_cache_t *cache = cache_void;
- DEBUG_CACHE_MEMBUFFER_INIT_TAG
+ DEBUG_CACHE_MEMBUFFER_INIT_TAG(result_pool)
if (key == NULL)
{
@@ -2114,7 +2817,7 @@ svn_membuffer_cache_get_partial(void **value_p,
combine_key(cache, key, cache->key_len);
SVN_ERR(membuffer_cache_get_partial(cache->membuffer,
- cache->combined_key,
+ &cache->combined_key,
value_p,
found,
func,
@@ -2136,13 +2839,13 @@ svn_membuffer_cache_set_partial(void *cache_void,
{
svn_membuffer_cache_t *cache = cache_void;
- DEBUG_CACHE_MEMBUFFER_INIT_TAG
+ 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,
+ &cache->combined_key,
func,
baton,
DEBUG_CACHE_MEMBUFFER_TAG
@@ -2162,23 +2865,41 @@ svn_membuffer_cache_is_cachable(void *cache_void, apr_size_t size)
* must be small enough to be stored in a 32 bit value.
*/
svn_membuffer_cache_t *cache = cache_void;
- return size <= cache->membuffer->max_entry_size;
+ 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.
+/* 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_cache__info_t *info,
+ svn_boolean_t include_histogram)
{
- info->data_size += segment->data_size;
+ apr_uint32_t i;
+
+ info->data_size += segment->l1.size + segment->l2.size;
info->used_size += segment->data_used;
- info->total_size += segment->data_size +
+ 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;
}
@@ -2196,22 +2917,15 @@ svn_membuffer_cache_get_info(void *cache_void,
/* cache front-end specific data */
- info->id = apr_pstrdup(result_pool, cache->full_prefix);
+ info->id = apr_pstrdup(result_pool, cache->prefix.full_key.data);
/* collect info from shared cache back-end */
- 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;
WITH_READ_LOCK(segment,
- svn_membuffer_get_segment_info(segment, info));
+ svn_membuffer_get_segment_info(segment, info, FALSE));
}
return SVN_NO_ERROR;
@@ -2222,6 +2936,7 @@ svn_membuffer_cache_get_info(void *cache_void,
*/
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,
@@ -2250,6 +2965,24 @@ svn_membuffer_cache_get_synced(void **value_p,
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 *
@@ -2316,6 +3049,7 @@ svn_membuffer_cache_set_partial_synced(void *cache_void,
*/
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 */
@@ -2370,15 +3104,18 @@ svn_cache__create_membuffer_cache(svn_cache__t **cache_p,
svn_cache__deserialize_func_t deserializer,
apr_ssize_t klen,
const char *prefix,
+ apr_uint32_t priority,
svn_boolean_t thread_safe,
- apr_pool_t *pool)
+ 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(pool, sizeof(*wrapper));
- svn_membuffer_cache_t *cache = apr_palloc(pool, sizeof(*cache));
+ 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
*/
@@ -2389,30 +3126,38 @@ svn_cache__create_membuffer_cache(svn_cache__t **cache_p,
cache->deserializer = deserializer
? deserializer
: deserialize_svn_stringbuf;
- cache->full_prefix = apr_pstrdup(pool, prefix);
+ cache->priority = priority;
cache->key_len = klen;
- cache->pool = svn_pool_create(pool);
- cache->alloc_counter = 0;
- SVN_ERR(svn_mutex__init(&cache->mutex, thread_safe, pool));
+ SVN_ERR(svn_mutex__init(&cache->mutex, thread_safe, result_pool));
- /* for performance reasons, we don't actually store the full prefix but a
- * hash value of it
- */
+ /* 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);
+
+ svn_membuf__create(&cache->prefix.full_key, prefix_len, result_pool);
+ memcpy((char *)cache->prefix.full_key.data, prefix, prefix_orig_len);
+ memset((char *)cache->prefix.full_key.data + prefix_orig_len, 0,
+ prefix_len - prefix_orig_len);
+
+ /* Construct the folded prefix key. */
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
+ scratch_pool));
+ memcpy(cache->prefix.entry_key.fingerprint, checksum->digest,
+ sizeof(cache->prefix.entry_key.fingerprint));
+ cache->prefix.entry_key.key_len = prefix_len;
+
+ /* 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.entry_key;
+ svn_membuf__create(&cache->combined_key.full_key, prefix_len + 200,
+ result_pool);
+ memcpy(cache->combined_key.full_key.data, cache->prefix.full_key.data,
+ prefix_len);
/* initialize the generic cache wrapper
*/
@@ -2421,8 +3166,43 @@ svn_cache__create_membuffer_cache(svn_cache__t **cache_p,
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;
+}