diff options
Diffstat (limited to 'subversion/libsvn_subr/cache-membuffer.c')
| -rw-r--r-- | subversion/libsvn_subr/cache-membuffer.c | 1889 |
1 files changed, 1345 insertions, 544 deletions
diff --git a/subversion/libsvn_subr/cache-membuffer.c b/subversion/libsvn_subr/cache-membuffer.c index 7aa90cd7937d..8aeaf775d771 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,13 +138,6 @@ # 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. * Must be a power of 2. */ @@ -170,11 +185,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 +224,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 +234,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 +260,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 +299,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 +341,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 +359,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 +374,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 +388,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 +416,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 +498,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 +562,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 @@ -507,33 +641,32 @@ struct svn_membuffer_t 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,259 @@ 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) + { + /* Low prio items can only be accepted only if the current + * entry is of even lower prio and has fewer hits. + */ + if ( entry->priority > to_fit_in->priority + || entry->hit_count > to_fit_in->hit_count) + return FALSE; + } + + if (entry->priority <= SVN_CACHE__MEMBUFFER_LOW_PRIORITY) + { + /* Be quick to remove low-prio entries - even if the incoming + * one is low-prio as well. This makes room for more important + * data and replaces existing data with newly read information. + */ + keep = FALSE; + } + else + { + /* If the existing data is the same prio as the incoming data, + * drop the existing entry if it had seen fewer (probably 0) + * hits than the entry coming in from L1. In case of different + * priorities, keep the current entry of it has higher prio. + * The new entry may still find room by ousting other entries. + */ + keep = to_fit_in->priority == entry->priority + ? entry->hit_count >= to_fit_in->hit_count + : entry->priority > to_fit_in->priority; + } + + /* keepers or destroyers? */ + if (keep) { + /* Moving entries around is not for free -> track costs. */ + moved_size += entry->size; + moved_count++; + move_entry(cache, entry); } else { - svn_boolean_t keep; + /* 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; - 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; + drop_entry(cache, entry); + } + } + } - 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); - } + /* This will never be reached. But if it was, "can't insert" was the + * right answer. */ +} + +/* This function implements the cache insertion / eviction strategy for L1. + * + * If necessary, enlarge the insertion window of CACHE->L1 by promoting + * entries to L2 until it is at least SIZE bytes long. + * + * Return TRUE if enough room could be found or made. A FALSE result + * indicates that the respective item shall not be added because it is + * too large. + */ +static svn_boolean_t +ensure_data_insertable_l1(svn_membuffer_t *cache, apr_size_t size) +{ + /* Guarantees that the while loop will terminate. */ + if (size > cache->l1.size) + return FALSE; + + /* This loop will eventually terminate because every cache entry + * would get dropped eventually. + */ + while (1) + { + /* first offset behind the insertion window + */ + apr_uint32_t entry_index = cache->l1.next; + entry_t *entry = get_entry(cache, entry_index); + apr_uint64_t end = cache->l1.next == NO_INDEX + ? cache->l1.start_offset + cache->l1.size + : entry->offset; + + /* leave function as soon as the insertion window is large enough + */ + if (end >= 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); - /* keepers or destroyers? */ + /* We might have touched the group that contains ENTRY. Recheck. */ + if (entry_index == cache->l1.next) + { if (keep) - { - move_entry(cache, entry); - } + promote_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); } } } @@ -1188,6 +1678,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 +1754,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 +1764,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 +1783,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 +1795,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 +1807,29 @@ 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; + /* 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 = data_size - c[seg].l1.size; + c[seg].l2.current_data = c[seg].l2.start_offset; - c[seg].data_size = data_size; c[seg].data = secure_aligned_alloc(pool, (apr_size_t)data_size, FALSE); - c[seg].current_data = 0; c[seg].data_used = 0; c[seg].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 +1844,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 +1861,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 +1873,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 +1937,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 +1950,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 +1962,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; + } + + /* Don't cache large, unimportant items. */ + return 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. +/* 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 +2006,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 +2034,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 +2058,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 +2067,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 +2085,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 +2119,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 +2132,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 +2147,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 +2175,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 +2203,9 @@ membuffer_cache_get_internal(svn_membuffer_t *cache, return SVN_NO_ERROR; } - size = ALIGN_VALUE(entry->size); + size = ALIGN_VALUE(entry->size) - entry->key.key_len; *buffer = ALIGN_POINTER(apr_palloc(result_pool, size + ITEM_ALIGNMENT-1)); - memcpy(*buffer, (const char*)cache->data + entry->offset, size); + memcpy(*buffer, cache->data + entry->offset + entry->key.key_len, size); #ifdef SVN_DEBUG_CACHE_MEMBUFFER @@ -1592,18 +2217,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 +2238,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 +2250,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 +2272,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 +2338,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 +2357,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 +2372,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 +2389,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 +2397,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 +2421,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 +2439,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 +2452,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 +2473,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 +2512,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 +2529,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 +2537,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 +2582,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 +2609,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 +2705,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 +2723,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 +2731,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 +2777,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 +2792,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 +2826,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 +2838,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 +2860,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 +2886,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 +2938,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 +2957,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 +2986,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 +3070,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 +3125,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 +3147,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 +3187,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; +} |