Re: svn commit: r1567996 - /subversion/trunk/subversion/libsvn_subr/cache-membuffer.c

On 13 February 2014 22:24, <stefan2_at_apache.org> wrote:
> Author: stefan2
> Date: Thu Feb 13 18:24:17 2014
> New Revision: 1567996
>
> URL: http://svn.apache.org/r1567996
> Log:
> In the membuffer cache code, we update hit counters without further
> synchronization as they are mere hints. However, that can cause
> 64 bit underflows in the global hit counters which will make all
> entry hit counters appear to be very small in comparison, i.e.
> entries get evicted sooner than they should.
>
> We fix this by simply switching to signed global counters which
> compare nicely to unsigned values of less precision. This allows
> us to remain race without introducing a bias (e.g. by saturating
> at 0 upon underflow).
>
> Once at it, fix the local <-> global hit counter inconsistency
> that occurs when the entry hit counter exceeds 4G - which might
> happen for certain root objects.
>
> * subversion/libsvn_subr/cache-membuffer.c
> (svn_membuffer_t): Switch to signed counters as those work
> nicely with our comparison / eviction logic
> even if we underflow to negative values.
> (increment_hit_counters): New utility function handling the
> potential 32 bit counter overflow.
> (membuffer_cache_get_internal,
> membuffer_cache_has_key_internal,
> membuffer_cache_get_partial_internal,
> membuffer_cache_set_partial_internal): Call the new utility.
>
> Found by: vitalif{_AT_}yourcmc.ru
>
> Modified:
> subversion/trunk/subversion/libsvn_subr/cache-membuffer.c
>
> Modified: subversion/trunk/subversion/libsvn_subr/cache-membuffer.c
> URL: http://svn.apache.org/viewvc/subversion/trunk/subversion/libsvn_subr/cache-membuffer.c?rev=1567996&r1=1567995&r2=1567996&view=diff
> ==============================================================================
> --- subversion/trunk/subversion/libsvn_subr/cache-membuffer.c (original)
> +++ subversion/trunk/subversion/libsvn_subr/cache-membuffer.c Thu Feb 13 18:24:17 2014
> @@ -545,8 +545,12 @@ struct svn_membuffer_t
> /* 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.
> + *
> + * Note that we update this value "racily" from multiple threads.
> + * Thus, allow it to hover around the actual value which includes the
> + * possibility of being slightly below 0.
> */
> - apr_uint64_t hit_count;
> + apr_int64_t hit_count;
>
>
> /* Total number of calls to membuffer_cache_get.
> @@ -1998,6 +2002,24 @@ membuffer_cache_set(svn_membuffer_t *cac
> 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 and we must make sure that
> + * the global sums are still (roughly due to races) the sum of all local
> + * counters. */
> + if (++entry->hit_count == 0)
> + cache->hit_count -= APR_UINT32_MAX;
> + else
> + cache->hit_count++;
> +
As far I understand this counters are updated from several threads
without mutex? In that case we have to use atomic functions to
increment them, otherwise we may skip hit_count == 0 in some cases.

-- 
Ivan Zhakov
CTO | VisualSVN | http://www.visualsvn.com