Philip Martin wrote:
> Stefan Fuhrmann <stefanfuhrmann_at_alice-dsl.de> writes:
>
>
>> The improvements:
>>
>> * allow for arbitrary (but preferably very small) number
>> of pinned entries per cache
>> * support pinned entries from multiple threads
>> (i.e. don't use hold the mutex across API calls)
>> * added atomic set&pin operation
>> * check for pin leaks before the pool cleanup
>>
>> An svn_wc__call_with_write_lock-like approach would
>> work for scenarios like the packed_offset_cache one in
>> this patch. But it is much less obvious when the function
>> to execute may or may not create the locked object in
>> the first place. Therefore, I decided against that option.
>>
>
> I don't understand the "may or may not create" bit. Something to do
> with two pins overlapping perhaps?
>
My understanding of svn_wc__call_with_write_lock is
that it provides the following sequence:
(1) lock item
(2) err = call actual function
(3) unlock item
(4) return err
What I need is (pseudo-code):
dir_hash* getDir()
if (exists in cache): pin & return
if (permanent dir): add to cache, pin & return
return dir content (not pinned)
get_entry()
getDir()
extract entry
if (pinned) unpin
So, there is no way, I could pin the dir_hash object
before calling get_entry or getDir because it may not
exist yet or may even not get cached at all.
> This patch relies on apr_pool_pre_cleanup_register which is only
> available in APR 1.3.
>
Will fix that.
>
>> +/**
>> + * Returns a reference to a value indexed by @a key from @a cache into
>> + * @a *value, setting @a *found to TRUE iff it is in the cache and FALSE
>> + * if it is not found. If necessary, temporary objects will be allocated
>> + * in @a pool.
>> + *
>> + * Unlike svn_cache__get, this function does not create a copy of that
>> + * value but returns a reference to the cached value. The reference remains
>> + * valid until svn_cache__unpin is called.
>> + *
>> + * Every value returned by this function must be released explicitly by
>> + * calling svn_cache__unpin. It is suggested that the calling code evaluates
>> + * the returned @a *value immediately and unpins it a.s.a.p.
>> + *
>> + * It is not legal to modify a pinned entry or to destroy the cache
>> + * as long as it contains pinned entries. Failure to comply with this
>> + * will trigger assertions.
>> + *
>> + * svn_cache__get_pinned is not supported by all cache implementations;
>> + * see the svn_cache__create_* function for details.
>> + */
>> +svn_error_t *
>> +svn_cache__get_pinned(void **value,
>>
>
> Should value be const?
>
This is the return value. To be useful in multi-threaded
code, we need an atomic "lookup & pin" command.
Because no additional parameters are required for
pinning, the signature is the same as for svn_cache__get().
>
>> + svn_boolean_t *found,
>> + const svn_cache__t *cache,
>> + const void *key,
>> + apr_pool_t *pool);
>>
>
> In new code use the name scratch_pool if it is only used for temporary
> allocations.
>
O.k. As opposed to svn_cache__get(), the result won't be
allocated in pool. It is only used for scratch.
>
>> Index: subversion/libsvn_subr/cache-inprocess.c
>> ===================================================================
>> --- subversion/libsvn_subr/cache-inprocess.c (revision 937673)
>> +++ subversion/libsvn_subr/cache-inprocess.c (working copy)
>> @@ -66,6 +66,14 @@
>> */
>> apr_pool_t *cache_pool;
>>
>> + /* If NULL, no item has been pined.
>> + * The pinned entries for a double-linked listed.
>> + * While this is efficient for very low numbers of entries,
>> + * we need to switch to some hash once this feature should
>> + * get used more extensively.
>> + */
>> + struct cache_entry *first_pinned_entry;
>> +
>> #if APR_HAS_THREADS
>> /* A lock for intra-process synchronization to the cache, or NULL if
>> * the cache's creator doesn't feel the cache needs to be
>> @@ -89,6 +97,9 @@
>> /* 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;
>> +
>> + /* Number of pinned entries in this page. */
>> + apr_size_t pin_count;
>> };
>>
>> /* An cache entry. */
>> @@ -102,6 +113,16 @@
>>
>> /* Next entry on the page. */
>> struct cache_entry *next_entry;
>> +
>> + /* Next entry that got pinned. NULL, if pin_count == 0 or end of the chain*/
>> + struct cache_entry *next_pinned;
>> +
>> + /* Previous element in the list of pinned entries.
>> + /* NULL, if pin_count == 0 or head of the list. */
>> + struct cache_entry *previous_pinned;
>> +
>> + /* Number of times this entry got pinned. */
>> + apr_size_t pin_count;
>> };
>>
>>
>> @@ -243,6 +264,8 @@
>> {
>> struct cache_entry *e;
>>
>> + SVN_ERR_ASSERT_NO_RETURN(page->pin_count == 0);
>> +
>>
>
> When would this trigger? Is this what happens if I forget to release
> a pin? Or is it that the pinned item is held for too long?
>
When I made a mistake. This is a cache-internal assertion
(LRU must not evict pages with pinned entries in them).
Will add a comment.
If you forget to release a pin, the pool cleanup will catch it.
>
>> remove_page_from_list(page);
>>
>> for (e = page->first_entry;
>> @@ -262,21 +285,38 @@
>> cache->partial_page_number_filled = 0;
>> }
>>
>> +/* Create and initialize a fresh cache page.
>> + * Don't update the global page counter. */
>> +static void
>> +allocate_page(inprocess_cache_t *cache)
>> +{
>> + 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->pin_count = 0;
>> + cache->partial_page_number_filled = 0;
>> +}
>> +
>> +/* Similar to inprocess_cache_set but assumes the cache
>> + * to be already locked (and won't unlock it, either).
>> + * Attempts to modify a pinned entry trigger an assertion.
>> + * Returns the entry that contains the value that has been set. */
>> static svn_error_t *
>> -inprocess_cache_set(void *cache_void,
>> - const void *key,
>> - void *value,
>> - apr_pool_t *pool)
>> +inprocess_cache_set_locked(inprocess_cache_t *cache,
>> + const void *key,
>> + void *value,
>> + struct cache_entry **entry,
>> + apr_pool_t *pool)
>> {
>> - inprocess_cache_t *cache = cache_void;
>> - struct cache_entry *existing_entry;
>> - svn_error_t *err = SVN_NO_ERROR;
>> + struct cache_entry *existing_entry =
>> + apr_hash_get(cache->hash, key, cache->klen);
>>
>> - SVN_ERR(lock_cache(cache));
>> + /* You cannot update a pinned entry because others will
>> + * probably reference the old entry. */
>> + if (existing_entry)
>> + SVN_ERR_ASSERT(existing_entry->pin_count == 0);
>>
>> - 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)
>> @@ -302,19 +342,18 @@
>> struct cache_page *page = existing_entry->page;
>>
>> move_page_to_front(cache, page);
>> - err = duplicate_value(&(existing_entry->value), cache,
>> - value, page->page_pool);
>> - goto cleanup;
>> + SVN_ERR(duplicate_value(&(existing_entry->value), cache,
>> + value, page->page_pool));
>> +
>> + *entry = existing_entry;
>> + 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;
>> + allocate_page(cache);
>> (cache->unallocated_pages)--;
>> }
>>
>> @@ -323,12 +362,39 @@
>> * count? */
>> if (cache->partial_page == NULL)
>> {
>> - struct cache_page *oldest_page = cache->sentinel->prev;
>> + struct cache_page *victim_page;
>>
>> - SVN_ERR_ASSERT(oldest_page != cache->sentinel);
>> + /* Look for a page with no pinned items on it.
>> + * Start at the oldest page. */
>> + for (victim_page = cache->sentinel->prev;
>> + victim_page != cache->sentinel;
>> + victim_page = victim_page->prev)
>> + {
>> + if (victim_page->pin_count == 0)
>> + {
>> + /* Erase the page and put it in cache->partial_page. */
>> + erase_page(cache, victim_page);
>> + break;
>> + }
>> + }
>> + }
>>
>> - /* Erase the page and put it in cache->partial_page. */
>> - erase_page(cache, oldest_page);
>> + /* Cache overflow due to pinned items on every page?
>> + * Tough luck. We don't have any chance other than to
>> + * the original allocation limit. */
>>
>
> Should that say "exceed the original allocation limit"?
>
Yep, typo.
>
>> + if (cache->partial_page == NULL)
>> + {
>> + /* You pinned too many entries. Fix that! */
>> + svn_error_t *svn_warning =
>> + svn_error_create(SVN_ERR_INPROCCACHE_OVERFLOW,
>> + NULL,
>> + _("Cache overflow. Too many entries pinned."));
>> +
>> + svn_handle_warning2(stderr, svn_warning, "svn-debug: ");
>> + svn_error_clear (svn_warning);
>>
>
> We don't want the libraries to use stderr.
>
I couldn't find an example for how to log debug messages.
Can you give me a pointer?
The whole point of this is that you are probably leaking
pins right now or at least your memory usage might go
through the roof. Today, no code should be able to trigger
that but if the pin feature gets used more liberally in other
places, we may want to see this warning as early as possible.
>
>> +
>> + /* Well, until then we need to carry one ... */
>> + allocate_page(cache);
>> }
>>
>
> Perhaps we should return an error and allow the caller to retry
> without the pin?
>
>
Hm, it is not a real bug. If the cache->unallocated_pages
gets initialized with a fairly low value and many threads
use the cache concurrently, we may run in this case.
So, IMO it's better to issue a firm warning instead of
terminating the request. The cache would otherwise become
a limited and limiting resource.
BTW, another typo :(
>>
>> SVN_ERR_ASSERT(cache->partial_page != NULL);
>> @@ -340,16 +406,19 @@
>>
>> /* Copy the key and value into the page's pool. */
>> new_entry->key = duplicate_key(cache, key, page->page_pool);
>> - err = duplicate_value(&(new_entry->value), cache, value,
>> - page->page_pool);
>> - if (err)
>> - goto cleanup;
>> + SVN_ERR(duplicate_value(&(new_entry->value), cache, value,
>> + page->page_pool));
>>
>> /* Add the entry to the page's list. */
>> new_entry->page = page;
>> new_entry->next_entry = page->first_entry;
>> page->first_entry = new_entry;
>>
>> + /* Initialized pinning info */
>> + new_entry->next_pinned = NULL;
>> + new_entry->previous_pinned = NULL;
>> + new_entry->pin_count = 0;
>> +
>> /* 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);
>> @@ -363,10 +432,28 @@
>> insert_page(cache, page);
>> cache->partial_page = NULL;
>> }
>> +
>> + /* Return result*/
>> + *entry = new_entry;
>> + return SVN_NO_ERROR;
>> }
>> +}
>>
>> - cleanup:
>> - return unlock_cache(cache, err);
>> +/* Synchronize access to the cache and then set the value.
>> + * We don't care about the entry being used. */
>> +static svn_error_t *
>> +inprocess_cache_set(void *cache_void,
>> + const void *key,
>> + void *value,
>> + apr_pool_t *pool)
>> +{
>> + inprocess_cache_t *cache = cache_void;
>> + struct cache_entry *existing_entry;
>> +
>> + SVN_ERR(lock_cache(cache));
>> + return unlock_cache(cache,
>> + inprocess_cache_set_locked(cache, key, value,
>> + &existing_entry, pool));
>> }
>>
>> /* Baton type for svn_cache__iter. */
>> @@ -406,15 +493,162 @@
>> return unlock_cache(cache,
>> svn_iter_apr_hash(completed, cache->hash, iter_cb, &b,
>> pool));
>> +}
>>
>> +/* All the counter & pointer update jazz required to pin the
>> + * given entry. */
>> +static void
>> +pin_entry(inprocess_cache_t *cache,
>> + struct cache_entry *entry)
>> +{
>> + /* Entries that have already been pinned just need
>> + * their reference counts to be bumped. */
>> + if (entry->pin_count == 0)
>> + {
>> + /* The entry has not been pinned, yet.
>> + * We put it at the head of the pinned entry list. */
>> + if (cache->first_pinned_entry != NULL)
>> + {
>> + entry->next_pinned = cache->first_pinned_entry;
>> + cache->first_pinned_entry->previous_pinned = entry;
>> + }
>> +
>> + cache->first_pinned_entry = entry;
>> + }
>> +
>> + ++entry->pin_count;
>> + ++entry->page->pin_count;
>> }
>>
>> +/* Very similar to inprocess_cache_get but will return a pinned
>> + * reference to the value instead of a copy. */
>> +static svn_error_t *
>> +inprocess_cache_get_pinned(void **value_p,
>> + svn_boolean_t *found,
>> + void *cache_void,
>> + const void *key,
>> + apr_pool_t *pool)
>> +{
>> + inprocess_cache_t *cache = cache_void;
>> + struct cache_entry *entry;
>> +
>> + SVN_ERR(lock_cache(cache));
>> +
>> + entry = apr_hash_get(cache->hash, key, cache->klen);
>> + if (! entry)
>> + {
>> + *found = FALSE;
>> + return unlock_cache(cache, SVN_NO_ERROR);
>> + }
>> +
>> + move_page_to_front(cache, entry->page);
>> + pin_entry(cache, entry);
>>
>
> So you are keeping it in the LRU list as well as pinned list. Do you
> avoid evicting pinned entries or not? (Is this the reason for the
> SVN_ERR_ASSERT_NO_RETURN above?)
>
The cache is organized as a LRU list of pages each
containing a fixed number of entries. I didn't change
this part of the design.
Once all pages have been filled, the LRU one will
be removed. That got changed to "LRU with no
pinned entry in it". If there is no such page, add a
new page, i.e. exceed the page count limit.
The pinned entries themselves form a double-linked
list for faster lookup only: we get the value reference
as an input to the unpin function and must find the
entry structure that contains this reference.
>
>> +
>> + *found = TRUE;
>> + *value_p = entry->value;
>> +
>> + return unlock_cache(cache, SVN_NO_ERROR);
>> +}
>>
-- Stefan^2.
Received on 2010-04-27 02:46:07 CEST