diff options
Diffstat (limited to 'subversion/libsvn_subr/cache-inprocess.c')
| -rw-r--r-- | subversion/libsvn_subr/cache-inprocess.c | 648 |
1 files changed, 648 insertions, 0 deletions
diff --git a/subversion/libsvn_subr/cache-inprocess.c b/subversion/libsvn_subr/cache-inprocess.c new file mode 100644 index 0000000..6401f9f --- /dev/null +++ b/subversion/libsvn_subr/cache-inprocess.c @@ -0,0 +1,648 @@ +/* + * cache-inprocess.c: in-memory caching for Subversion + * + * ==================================================================== + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, + * software distributed under the License is distributed on an + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY + * KIND, either express or implied. See the License for the + * specific language governing permissions and limitations + * under the License. + * ==================================================================== + */ + +#include <assert.h> + +#include <apr_thread_mutex.h> + +#include "svn_pools.h" + +#include "svn_private_config.h" + +#include "cache.h" +#include "private/svn_mutex.h" + +/* The (internal) cache object. */ +typedef struct inprocess_cache_t { + /* A user-defined identifier for this cache instance. */ + const char *id; + + /* HASH maps a key (of size KLEN) to a struct cache_entry. */ + apr_hash_t *hash; + apr_ssize_t klen; + + /* Used to copy values into the cache. */ + svn_cache__serialize_func_t serialize_func; + + /* Used to copy values out of the cache. */ + svn_cache__deserialize_func_t deserialize_func; + + /* Maximum number of pages that this cache instance may allocate */ + apr_uint64_t total_pages; + /* The number of pages we're allowed to allocate before having to + * try to reuse one. */ + apr_uint64_t unallocated_pages; + /* Number of cache entries stored on each page. Must be at least 1. */ + apr_uint64_t items_per_page; + + /* A dummy cache_page serving as the head of a circular doubly + * linked list of cache_pages. SENTINEL->NEXT is the most recently + * used page, and SENTINEL->PREV is the least recently used page. + * All pages in this list are "full"; the page currently being + * filled (PARTIAL_PAGE) is not in the list. */ + struct cache_page *sentinel; + + /* A page currently being filled with entries, or NULL if there's no + * partially-filled page. This page is not in SENTINEL's list. */ + struct cache_page *partial_page; + /* If PARTIAL_PAGE is not null, this is the number of entries + * currently on PARTIAL_PAGE. */ + apr_uint64_t partial_page_number_filled; + + /* The pool that the svn_cache__t itself, HASH, and all pages are + * allocated in; subpools of this pool are used for the cache_entry + * structs, as well as the dup'd values and hash keys. + */ + apr_pool_t *cache_pool; + + /* Sum of the SIZE members of all cache_entry elements that are + * accessible from HASH. This is used to make statistics available + * even if the sub-pools have already been destroyed. + */ + apr_size_t data_size; + + /* A lock for intra-process synchronization to the cache, or NULL if + * the cache's creator doesn't feel the cache needs to be + * thread-safe. */ + svn_mutex__t *mutex; +} inprocess_cache_t; + +/* A cache page; all items on the page are allocated from the same + * pool. */ +struct cache_page { + /* Pointers for the LRU list anchored at the cache's SENTINEL. + * (NULL for the PARTIAL_PAGE.) */ + struct cache_page *prev; + struct cache_page *next; + + /* The pool in which cache_entry structs, hash keys, and dup'd + * values are allocated. The CACHE_PAGE structs are allocated + * in CACHE_POOL and have the same lifetime as the cache itself. + * (The cache will never allocate more than TOTAL_PAGES page + * structs (inclusive of the sentinel) from CACHE_POOL.) + */ + apr_pool_t *page_pool; + + /* A singly linked list of the entries on this page; used to remove + * them from the cache's HASH before reusing the page. */ + struct cache_entry *first_entry; +}; + +/* An cache entry. */ +struct cache_entry { + const void *key; + + /* serialized value */ + void *value; + + /* length of the serialized value in bytes */ + apr_size_t size; + + /* The page it's on (needed so that the LRU list can be + * maintained). */ + struct cache_page *page; + + /* Next entry on the page. */ + struct cache_entry *next_entry; +}; + + +/* Removes PAGE from the doubly-linked list it is in (leaving its PREV + * and NEXT fields undefined). */ +static void +remove_page_from_list(struct cache_page *page) +{ + page->prev->next = page->next; + page->next->prev = page->prev; +} + +/* Inserts PAGE after CACHE's sentinel. */ +static void +insert_page(inprocess_cache_t *cache, + struct cache_page *page) +{ + struct cache_page *pred = cache->sentinel; + + page->prev = pred; + page->next = pred->next; + page->prev->next = page; + page->next->prev = page; +} + +/* If PAGE is in the circularly linked list (eg, its NEXT isn't NULL), + * move it to the front of the list. */ +static svn_error_t * +move_page_to_front(inprocess_cache_t *cache, + struct cache_page *page) +{ + /* This function is called whilst CACHE is locked. */ + + SVN_ERR_ASSERT(page != cache->sentinel); + + if (! page->next) + return SVN_NO_ERROR; + + remove_page_from_list(page); + insert_page(cache, page); + + return SVN_NO_ERROR; +} + +/* Return a copy of KEY inside POOL, using CACHE->KLEN to figure out + * how. */ +static const void * +duplicate_key(inprocess_cache_t *cache, + const void *key, + apr_pool_t *pool) +{ + if (cache->klen == APR_HASH_KEY_STRING) + return apr_pstrdup(pool, key); + else + return apr_pmemdup(pool, key, cache->klen); +} + +static svn_error_t * +inprocess_cache_get_internal(char **buffer, + apr_size_t *size, + inprocess_cache_t *cache, + const void *key, + apr_pool_t *result_pool) +{ + struct cache_entry *entry = apr_hash_get(cache->hash, key, cache->klen); + + *buffer = NULL; + if (entry) + { + SVN_ERR(move_page_to_front(cache, entry->page)); + + /* duplicate the buffer entry */ + *buffer = apr_palloc(result_pool, entry->size); + memcpy(*buffer, entry->value, entry->size); + + *size = entry->size; + } + + return SVN_NO_ERROR; +} + +static svn_error_t * +inprocess_cache_get(void **value_p, + svn_boolean_t *found, + void *cache_void, + const void *key, + apr_pool_t *result_pool) +{ + inprocess_cache_t *cache = cache_void; + char* buffer = NULL; + apr_size_t size; + + if (key) + SVN_MUTEX__WITH_LOCK(cache->mutex, + inprocess_cache_get_internal(&buffer, + &size, + cache, + key, + result_pool)); + + /* deserialize the buffer content. Usually, this will directly + modify the buffer content directly. + */ + *value_p = NULL; + *found = buffer != NULL; + return buffer && size + ? cache->deserialize_func(value_p, buffer, size, result_pool) + : SVN_NO_ERROR; +} + +/* Removes PAGE from the LRU list, removes all of its entries from + * CACHE's hash, clears its pool, and sets its entry pointer to NULL. + * Finally, puts it in the "partial page" slot in the cache and sets + * partial_page_number_filled to 0. Must be called on a page actually + * in the list. */ +static void +erase_page(inprocess_cache_t *cache, + struct cache_page *page) +{ + struct cache_entry *e; + + remove_page_from_list(page); + + for (e = page->first_entry; + e; + e = e->next_entry) + { + cache->data_size -= e->size; + apr_hash_set(cache->hash, e->key, cache->klen, NULL); + } + + svn_pool_clear(page->page_pool); + + page->first_entry = NULL; + page->prev = NULL; + page->next = NULL; + + cache->partial_page = page; + cache->partial_page_number_filled = 0; +} + + +static svn_error_t * +inprocess_cache_set_internal(inprocess_cache_t *cache, + const void *key, + void *value, + apr_pool_t *scratch_pool) +{ + struct cache_entry *existing_entry; + + existing_entry = apr_hash_get(cache->hash, key, cache->klen); + + /* Is it already here, but we can do the one-item-per-page + * optimization? */ + if (existing_entry && cache->items_per_page == 1) + { + /* Special case! ENTRY is the *only* entry on this page, so + * why not wipe it (so as not to leak the previous value). + */ + struct cache_page *page = existing_entry->page; + + /* This can't be the partial page: items_per_page == 1 + * *never* has a partial page (except for in the temporary state + * that we're about to fake). */ + SVN_ERR_ASSERT(page->next != NULL); + SVN_ERR_ASSERT(cache->partial_page == NULL); + + erase_page(cache, page); + existing_entry = NULL; + } + + /* Is it already here, and we just have to leak the old value? */ + if (existing_entry) + { + struct cache_page *page = existing_entry->page; + + SVN_ERR(move_page_to_front(cache, page)); + cache->data_size -= existing_entry->size; + if (value) + { + SVN_ERR(cache->serialize_func(&existing_entry->value, + &existing_entry->size, + value, + page->page_pool)); + cache->data_size += existing_entry->size; + if (existing_entry->size == 0) + existing_entry->value = NULL; + } + else + { + existing_entry->value = NULL; + existing_entry->size = 0; + } + + return SVN_NO_ERROR; + } + + /* Do we not have a partial page to put it on, but we are allowed to + * allocate more? */ + if (cache->partial_page == NULL && cache->unallocated_pages > 0) + { + cache->partial_page = apr_pcalloc(cache->cache_pool, + sizeof(*(cache->partial_page))); + cache->partial_page->page_pool = svn_pool_create(cache->cache_pool); + cache->partial_page_number_filled = 0; + (cache->unallocated_pages)--; + } + + /* Do we really not have a partial page to put it on, even after the + * one-item-per-page optimization and checking the unallocated page + * count? */ + if (cache->partial_page == NULL) + { + struct cache_page *oldest_page = cache->sentinel->prev; + + SVN_ERR_ASSERT(oldest_page != cache->sentinel); + + /* Erase the page and put it in cache->partial_page. */ + erase_page(cache, oldest_page); + } + + SVN_ERR_ASSERT(cache->partial_page != NULL); + + { + struct cache_page *page = cache->partial_page; + struct cache_entry *new_entry = apr_pcalloc(page->page_pool, + sizeof(*new_entry)); + + /* Copy the key and value into the page's pool. */ + new_entry->key = duplicate_key(cache, key, page->page_pool); + if (value) + { + SVN_ERR(cache->serialize_func(&new_entry->value, + &new_entry->size, + value, + page->page_pool)); + cache->data_size += new_entry->size; + if (new_entry->size == 0) + new_entry->value = NULL; + } + else + { + new_entry->value = NULL; + new_entry->size = 0; + } + + /* Add the entry to the page's list. */ + new_entry->page = page; + new_entry->next_entry = page->first_entry; + page->first_entry = new_entry; + + /* Add the entry to the hash, using the *entry's* copy of the + * key. */ + apr_hash_set(cache->hash, new_entry->key, cache->klen, new_entry); + + /* We've added something else to the partial page. */ + (cache->partial_page_number_filled)++; + + /* Is it full? */ + if (cache->partial_page_number_filled >= cache->items_per_page) + { + insert_page(cache, page); + cache->partial_page = NULL; + } + } + + return SVN_NO_ERROR; +} + +static svn_error_t * +inprocess_cache_set(void *cache_void, + const void *key, + void *value, + apr_pool_t *scratch_pool) +{ + inprocess_cache_t *cache = cache_void; + + if (key) + SVN_MUTEX__WITH_LOCK(cache->mutex, + inprocess_cache_set_internal(cache, + key, + value, + scratch_pool)); + + return SVN_NO_ERROR; +} + +/* Baton type for svn_cache__iter. */ +struct cache_iter_baton { + svn_iter_apr_hash_cb_t user_cb; + void *user_baton; +}; + +/* Call the user's callback with the actual value, not the + cache_entry. Implements the svn_iter_apr_hash_cb_t + prototype. */ +static svn_error_t * +iter_cb(void *baton, + const void *key, + apr_ssize_t klen, + void *val, + apr_pool_t *pool) +{ + struct cache_iter_baton *b = baton; + struct cache_entry *entry = val; + return (b->user_cb)(b->user_baton, key, klen, entry->value, pool); +} + +static svn_error_t * +inprocess_cache_iter(svn_boolean_t *completed, + void *cache_void, + svn_iter_apr_hash_cb_t user_cb, + void *user_baton, + apr_pool_t *scratch_pool) +{ + inprocess_cache_t *cache = cache_void; + struct cache_iter_baton b; + b.user_cb = user_cb; + b.user_baton = user_baton; + + SVN_MUTEX__WITH_LOCK(cache->mutex, + svn_iter_apr_hash(completed, cache->hash, + iter_cb, &b, scratch_pool)); + + return SVN_NO_ERROR; +} + +static svn_error_t * +inprocess_cache_get_partial_internal(void **value_p, + svn_boolean_t *found, + inprocess_cache_t *cache, + const void *key, + svn_cache__partial_getter_func_t func, + void *baton, + apr_pool_t *result_pool) +{ + struct cache_entry *entry = apr_hash_get(cache->hash, key, cache->klen); + if (! entry) + { + *found = FALSE; + return SVN_NO_ERROR; + } + + SVN_ERR(move_page_to_front(cache, entry->page)); + + *found = TRUE; + return func(value_p, entry->value, entry->size, baton, result_pool); +} + +static svn_error_t * +inprocess_cache_get_partial(void **value_p, + svn_boolean_t *found, + void *cache_void, + const void *key, + svn_cache__partial_getter_func_t func, + void *baton, + apr_pool_t *result_pool) +{ + inprocess_cache_t *cache = cache_void; + + if (key) + SVN_MUTEX__WITH_LOCK(cache->mutex, + inprocess_cache_get_partial_internal(value_p, + found, + cache, + key, + func, + baton, + result_pool)); + else + *found = FALSE; + + return SVN_NO_ERROR; +} + +static svn_error_t * +inprocess_cache_set_partial_internal(inprocess_cache_t *cache, + const void *key, + svn_cache__partial_setter_func_t func, + void *baton, + apr_pool_t *scratch_pool) +{ + struct cache_entry *entry = apr_hash_get(cache->hash, key, cache->klen); + if (entry) + { + SVN_ERR(move_page_to_front(cache, entry->page)); + + cache->data_size -= entry->size; + SVN_ERR(func(&entry->value, + &entry->size, + baton, + entry->page->page_pool)); + cache->data_size += entry->size; + } + + return SVN_NO_ERROR; +} + +static svn_error_t * +inprocess_cache_set_partial(void *cache_void, + const void *key, + svn_cache__partial_setter_func_t func, + void *baton, + apr_pool_t *scratch_pool) +{ + inprocess_cache_t *cache = cache_void; + + if (key) + SVN_MUTEX__WITH_LOCK(cache->mutex, + inprocess_cache_set_partial_internal(cache, + key, + func, + baton, + scratch_pool)); + + return SVN_NO_ERROR; +} + +static svn_boolean_t +inprocess_cache_is_cachable(void *cache_void, apr_size_t size) +{ + /* Be relatively strict: per page we should not allocate more than + * we could spare as "unused" memory. + * But in most cases, nobody will ask anyway. And in no case, this + * will be used for checks _inside_ the cache code. + */ + inprocess_cache_t *cache = cache_void; + return size < SVN_ALLOCATOR_RECOMMENDED_MAX_FREE / cache->items_per_page; +} + +static svn_error_t * +inprocess_cache_get_info_internal(inprocess_cache_t *cache, + svn_cache__info_t *info, + apr_pool_t *result_pool) +{ + info->id = apr_pstrdup(result_pool, cache->id); + + info->used_entries = apr_hash_count(cache->hash); + info->total_entries = cache->items_per_page * cache->total_pages; + + info->used_size = cache->data_size; + info->data_size = cache->data_size; + info->total_size = cache->data_size + + cache->items_per_page * sizeof(struct cache_page) + + info->used_entries * sizeof(struct cache_entry); + + return SVN_NO_ERROR; +} + + +static svn_error_t * +inprocess_cache_get_info(void *cache_void, + svn_cache__info_t *info, + svn_boolean_t reset, + apr_pool_t *result_pool) +{ + inprocess_cache_t *cache = cache_void; + + SVN_MUTEX__WITH_LOCK(cache->mutex, + inprocess_cache_get_info_internal(cache, + info, + result_pool)); + + return SVN_NO_ERROR; +} + +static svn_cache__vtable_t inprocess_cache_vtable = { + inprocess_cache_get, + inprocess_cache_set, + inprocess_cache_iter, + inprocess_cache_is_cachable, + inprocess_cache_get_partial, + inprocess_cache_set_partial, + inprocess_cache_get_info +}; + +svn_error_t * +svn_cache__create_inprocess(svn_cache__t **cache_p, + svn_cache__serialize_func_t serialize, + svn_cache__deserialize_func_t deserialize, + apr_ssize_t klen, + apr_int64_t pages, + apr_int64_t items_per_page, + svn_boolean_t thread_safe, + const char *id, + apr_pool_t *pool) +{ + svn_cache__t *wrapper = apr_pcalloc(pool, sizeof(*wrapper)); + inprocess_cache_t *cache = apr_pcalloc(pool, sizeof(*cache)); + + cache->id = apr_pstrdup(pool, id); + + SVN_ERR_ASSERT(klen == APR_HASH_KEY_STRING || klen >= 1); + + cache->hash = apr_hash_make(pool); + cache->klen = klen; + + cache->serialize_func = serialize; + cache->deserialize_func = deserialize; + + SVN_ERR_ASSERT(pages >= 1); + cache->total_pages = pages; + cache->unallocated_pages = pages; + SVN_ERR_ASSERT(items_per_page >= 1); + cache->items_per_page = items_per_page; + + cache->sentinel = apr_pcalloc(pool, sizeof(*(cache->sentinel))); + cache->sentinel->prev = cache->sentinel; + cache->sentinel->next = cache->sentinel; + /* The sentinel doesn't need a pool. (We're happy to crash if we + * accidentally try to treat it like a real page.) */ + + SVN_ERR(svn_mutex__init(&cache->mutex, thread_safe, pool)); + + cache->cache_pool = pool; + + wrapper->vtable = &inprocess_cache_vtable; + wrapper->cache_internal = cache; + + *cache_p = wrapper; + return SVN_NO_ERROR; +} |
