You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@subversion.apache.org by st...@apache.org on 2014/02/13 19:24:17 UTC

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

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++;
+
+  /* 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
@@ -2054,10 +2076,7 @@ membuffer_cache_get_internal(svn_membuff
 
   /* update hit statistics
    */
-  entry->hit_count++;
-  cache->hit_count++;
-  cache->total_hits++;
-
+  increment_hit_counters(cache, entry);
   *item_size = entry->size;
 
   return SVN_NO_ERROR;
@@ -2116,14 +2135,12 @@ membuffer_cache_has_key_internal(svn_mem
   entry_t *entry = find_entry(cache, group_index, to_find, FALSE);
   if (entry)
     {
-      /* This is often happen in "block read" where most data is already
+      /* 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 for survival. */
-      entry->hit_count++;
-      cache->hit_count++;
-      cache->total_hits++;
+         them a higher chance of survival. */
+      increment_hit_counters(cache, entry);
 
       *found = TRUE;
     }
@@ -2194,9 +2211,7 @@ membuffer_cache_get_partial_internal(svn
     {
       *found = TRUE;
 
-      entry->hit_count++;
-      cache->hit_count++;
-      cache->total_hits++;
+      increment_hit_counters(cache, entry);
 
 #ifdef SVN_DEBUG_CACHE_MEMBUFFER
 
@@ -2286,8 +2301,7 @@ membuffer_cache_set_partial_internal(svn
       char *orig_data = data;
       apr_size_t size = entry->size;
 
-      entry->hit_count++;
-      cache->hit_count++;
+      increment_hit_counters(cache, entry);
       cache->total_writes++;
 
 #ifdef SVN_DEBUG_CACHE_MEMBUFFER



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

Posted by André Malo <nd...@perlig.de>.
* Philip Martin wrote:

> André Malo <nd...@perlig.de> writes:
> > isn't that even elying on undefined/unspecified behaviour, since
> > hit_count is unsigned?
>
> It's signed overflow that is undefined in C, unsigned overflow is
> defined.

Ah, well.

nd
-- 
Gefunden auf einer "Webdesigner"-Seite:
        > Programmierung in HTML, XML, WML, CGI, FLASH <

# André Malo # http://www.perlig.de/ #

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

Posted by Philip Martin <ph...@wandisco.com>.
André Malo <nd...@perlig.de> writes:

> isn't that even elying on undefined/unspecified behaviour, since
> hit_count is unsigned?

It's signed overflow that is undefined in C, unsigned overflow is
defined.

-- 
Philip Martin | Subversion Committer
WANdisco // *Non-Stop Data*

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

Posted by André Malo <nd...@perlig.de>.
* Ivan Zhakov wrote:

> On 13 February 2014 23:40, Stefan Fuhrmann <st...@wandisco.com> 
wrote:
> > On Thu, Feb 13, 2014 at 7:55 PM, Ivan Zhakov <iv...@visualsvn.com> wrote:
> >> On 13 February 2014 22:24,  <st...@apache.org> wrote:
> >> > Author: stefan2
> >> > Date: Thu Feb 13 18:24:17 2014
> >> > New Revision: 1567996
> >> >
> >> > URL: http://svn.apache.org/r1567996
> >> >
> >> >
> >> >
> >> > +/* 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?
> >
> > That is correct.
> >
> >> In that case we have to use atomic functions to
> >> increment them, otherwise we may skip hit_count == 0 in some cases.
> >
> > No.
> >
> > Assuming that the system does not split 32 bit read nor write operation
>
> I really, really don't like such assumptions in Subversion code. APR
> and OS already provides functions for proper inter process
> manipulations and we must use them, instead of saving several cycles.

Just stumbling over this debate. Besides the existence of CPU caches and no 
synchronizing between them (or I'm just missing it) - isn't that even 
relying on undefined/unspecified behaviour, since hit_count is unsigned? 
That code might just get optimized away.

nd
-- 
>kann mir jemand sagen, was genau @-Domains sind?
Ein Mythos. Ein Werbetrick. Verarsche. Nenn es wie du willst...

                 -- Alexandra Buss und Björn Höhrmann in dciwam

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

Posted by Stefan Fuhrmann <st...@wandisco.com>.
On Fri, Feb 14, 2014 at 1:01 AM, Bert Huijben <be...@qqmail.nl> wrote:

> Sorry for the big number of small replies...
>
>
>
> And the 'cache->total_reads++;' calls?
>
>
>
> Doesn't that need a similar handling?
>
>
>
>                 Bert
>
>
>
> *From:* Bert Huijben [mailto:bert@qqmail.nl]
> *Sent:* vrijdag 14 februari 2014 00:58
> *To:* 'Stefan Fuhrmann'; 'Ivan Zhakov'
>
> *Cc:* 'Subversion Development'; 'Stefan Fuhrman'
> *Subject:* RE: svn commit: r1567996 -
> /subversion/trunk/subversion/libsvn_subr/cache-membuffer.c
>
>
>
> [[
>
> Well, you were wrong on your initial point ("missing zero crossing").
>
> And you have been wrong on the "use the atomic functions" bit because
> they don't cover 64 bit integers. The only available option is a critical
> section (svn_mutex__t).
>
> ]]
>
>
>
> The 64 bit integer is for statistics only...
>
>
>
> If you just drop that one (that you only used for debugging your code...
> There is no single read of that variable) the rest can be an atomic
> increment.
>

entry->hit_count is 32 bits and atomic increment would be possible.
cache->hit_count is 64 bits for which we don't have portable atomic
operations.

cache->total_xzy are 64 bits but are for dev statistics only and not an
input
for any logic. When they happen to be updated in a synchronized environment,
that's fine, if not it's o.k., too. There is no need to write 3 or 4 extra
serializable
"increment" functions.

-- Stefan^2.

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

Posted by Bert Huijben <be...@qqmail.nl>.
Sorry for the big number of small replies.

 

And the 'cache->total_reads++;' calls?

 

Doesn't that need a similar handling?

 

                Bert

 

From: Bert Huijben [mailto:bert@qqmail.nl] 
Sent: vrijdag 14 februari 2014 00:58
To: 'Stefan Fuhrmann'; 'Ivan Zhakov'
Cc: 'Subversion Development'; 'Stefan Fuhrman'
Subject: RE: svn commit: r1567996 -
/subversion/trunk/subversion/libsvn_subr/cache-membuffer.c

 

[[

Well, you were wrong on your initial point ("missing zero crossing").

And you have been wrong on the "use the atomic functions" bit because
they don't cover 64 bit integers. The only available option is a critical
section (svn_mutex__t).

]]

 

The 64 bit integer is for statistics only.

 

If you just drop that one (that you only used for debugging your code. There
is no single read of that variable) the rest can be an atomic increment.

 

            Bert

 

 

From: Stefan Fuhrmann [mailto:stefan.fuhrmann@wandisco.com] 
Sent: donderdag 13 februari 2014 23:57
To: Ivan Zhakov
Cc: Subversion Development; Stefan Fuhrman
Subject: Re: svn commit: r1567996 -
/subversion/trunk/subversion/libsvn_subr/cache-membuffer.c

 

On Thu, Feb 13, 2014 at 9:02 PM, Ivan Zhakov <ivan@visualsvn.com
<ma...@visualsvn.com> > wrote:

On 13 February 2014 23:40, Stefan Fuhrmann <stefan.fuhrmann@wandisco.com
<ma...@wandisco.com> > wrote:
> On Thu, Feb 13, 2014 at 7:55 PM, Ivan Zhakov <ivan@visualsvn.com
<ma...@visualsvn.com> > wrote:
>>
>> On 13 February 2014 22:24,  <stefan2@apache.org
<ma...@apache.org> > wrote:
>> > Author: stefan2
>> > Date: Thu Feb 13 18:24:17 2014
>> > New Revision: 1567996
>> >
>> > URL: http://svn.apache.org/r1567996
>
>
>>
>> > +/* 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?
>
>
> That is correct.
>
>>
>> In that case we have to use atomic functions to
>> increment them, otherwise we may skip hit_count == 0 in some cases.
>
>
> No.

> Assuming that the system does not split 32 bit read nor write operation

I really, really don't like such assumptions in Subversion code. APR
and OS already provides functions for proper inter process
manipulations and we must use them, instead of saving several cycles.

 

Well, you were wrong on your initial point ("missing zero crossing").

And you have been wrong on the "use the atomic functions" bit because
they don't cover 64 bit integers. The only available option is a critical
section (svn_mutex__t).

 

So, I spent a few hours running actual load tests to see how lock
contention in a critical section would play out on a "real" server
machine with high multi-threaded load. And we got lucky (as opposed
to e.g. the APR thread pool code that we currently use in svnserve).

The new code is in r1568062.

-- Stefan^2.


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

Posted by Bert Huijben <be...@qqmail.nl>.
[[

Well, you were wrong on your initial point ("missing zero crossing").

And you have been wrong on the "use the atomic functions" bit because
they don't cover 64 bit integers. The only available option is a critical
section (svn_mutex__t).

]]

 

The 64 bit integer is for statistics only.

 

If you just drop that one (that you only used for debugging your code. There
is no single read of that variable) the rest can be an atomic increment.

 

            Bert

 

 

From: Stefan Fuhrmann [mailto:stefan.fuhrmann@wandisco.com] 
Sent: donderdag 13 februari 2014 23:57
To: Ivan Zhakov
Cc: Subversion Development; Stefan Fuhrman
Subject: Re: svn commit: r1567996 -
/subversion/trunk/subversion/libsvn_subr/cache-membuffer.c

 

On Thu, Feb 13, 2014 at 9:02 PM, Ivan Zhakov <ivan@visualsvn.com
<ma...@visualsvn.com> > wrote:

On 13 February 2014 23:40, Stefan Fuhrmann <stefan.fuhrmann@wandisco.com
<ma...@wandisco.com> > wrote:
> On Thu, Feb 13, 2014 at 7:55 PM, Ivan Zhakov <ivan@visualsvn.com
<ma...@visualsvn.com> > wrote:
>>
>> On 13 February 2014 22:24,  <stefan2@apache.org
<ma...@apache.org> > wrote:
>> > Author: stefan2
>> > Date: Thu Feb 13 18:24:17 2014
>> > New Revision: 1567996
>> >
>> > URL: http://svn.apache.org/r1567996
>
>
>>
>> > +/* 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?
>
>
> That is correct.
>
>>
>> In that case we have to use atomic functions to
>> increment them, otherwise we may skip hit_count == 0 in some cases.
>
>
> No.

> Assuming that the system does not split 32 bit read nor write operation

I really, really don't like such assumptions in Subversion code. APR
and OS already provides functions for proper inter process
manipulations and we must use them, instead of saving several cycles.

 

Well, you were wrong on your initial point ("missing zero crossing").

And you have been wrong on the "use the atomic functions" bit because
they don't cover 64 bit integers. The only available option is a critical
section (svn_mutex__t).

 

So, I spent a few hours running actual load tests to see how lock
contention in a critical section would play out on a "real" server
machine with high multi-threaded load. And we got lucky (as opposed
to e.g. the APR thread pool code that we currently use in svnserve).

The new code is in r1568062.

-- Stefan^2.


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

Posted by Stefan Fuhrmann <st...@wandisco.com>.
On Thu, Feb 13, 2014 at 9:02 PM, Ivan Zhakov <iv...@visualsvn.com> wrote:

> On 13 February 2014 23:40, Stefan Fuhrmann <st...@wandisco.com>
> wrote:
> > On Thu, Feb 13, 2014 at 7:55 PM, Ivan Zhakov <iv...@visualsvn.com> wrote:
> >>
> >> On 13 February 2014 22:24,  <st...@apache.org> wrote:
> >> > Author: stefan2
> >> > Date: Thu Feb 13 18:24:17 2014
> >> > New Revision: 1567996
> >> >
> >> > URL: http://svn.apache.org/r1567996
> >
> >
> >>
> >> > +/* 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?
> >
> >
> > That is correct.
> >
> >>
> >> In that case we have to use atomic functions to
> >> increment them, otherwise we may skip hit_count == 0 in some cases.
> >
> >
> > No.
>
> > Assuming that the system does not split 32 bit read nor write operation
> I really, really don't like such assumptions in Subversion code. APR
> and OS already provides functions for proper inter process
> manipulations and we must use them, instead of saving several cycles.
>

Well, you were wrong on your initial point ("missing zero crossing").
And you have been wrong on the "use the atomic functions" bit because
they don't cover 64 bit integers. The only available option is a critical
section (svn_mutex__t).

So, I spent a few hours running actual load tests to see how lock
contention in a critical section would play out on a "real" server
machine with high multi-threaded load. And we got lucky (as opposed
to e.g. the APR thread pool code that we currently use in svnserve).
The new code is in r1568062.

-- Stefan^2.

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

Posted by Branko Čibej <br...@wandisco.com>.
On 13.02.2014 21:02, Ivan Zhakov wrote:
> On 13 February 2014 23:40, Stefan Fuhrmann <st...@wandisco.com> wrote:
>> On Thu, Feb 13, 2014 at 7:55 PM, Ivan Zhakov <iv...@visualsvn.com> wrote:
>>> On 13 February 2014 22:24,  <st...@apache.org> wrote:
>>>> Author: stefan2
>>>> Date: Thu Feb 13 18:24:17 2014
>>>> New Revision: 1567996
>>>>
>>>> URL: http://svn.apache.org/r1567996
>>
>>>> +/* 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?
>>
>> That is correct.
>>
>>> In that case we have to use atomic functions to
>>> increment them, otherwise we may skip hit_count == 0 in some cases.
>>
>> No.
>> Assuming that the system does not split 32 bit read nor write operation
> I really, really don't like such assumptions in Subversion code. APR
> and OS already provides functions for proper inter process
> manipulations and we must use them, instead of saving several cycles.


Well, I've argued about such platform-specific micro-optimizations with
Stefan several times, to no avail.

Stefan, I really, really don't want this to become a veto war. Can you,
please, for once, stop assuming that all the world is running on the
latest versions of this or that architecture? We want Subversion to run
well on architectures that appear in the next 10 years without having to
find all the places you skipped using atomic instructions.

-- Brane

-- 
Branko Čibej | Director of Subversion
WANdisco // Non-Stop Data
e. brane@wandisco.com

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

Posted by Ivan Zhakov <iv...@visualsvn.com>.
On 13 February 2014 23:40, Stefan Fuhrmann <st...@wandisco.com> wrote:
> On Thu, Feb 13, 2014 at 7:55 PM, Ivan Zhakov <iv...@visualsvn.com> wrote:
>>
>> On 13 February 2014 22:24,  <st...@apache.org> wrote:
>> > Author: stefan2
>> > Date: Thu Feb 13 18:24:17 2014
>> > New Revision: 1567996
>> >
>> > URL: http://svn.apache.org/r1567996
>
>
>>
>> > +/* 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?
>
>
> That is correct.
>
>>
>> In that case we have to use atomic functions to
>> increment them, otherwise we may skip hit_count == 0 in some cases.
>
>
> No.

> Assuming that the system does not split 32 bit read nor write operation
I really, really don't like such assumptions in Subversion code. APR
and OS already provides functions for proper inter process
manipulations and we must use them, instead of saving several cycles.


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

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

Posted by Stefan Fuhrmann <st...@wandisco.com>.
On Thu, Feb 13, 2014 at 7:55 PM, Ivan Zhakov <iv...@visualsvn.com> wrote:

> On 13 February 2014 22:24,  <st...@apache.org> wrote:
> > Author: stefan2
> > Date: Thu Feb 13 18:24:17 2014
> > New Revision: 1567996
> >
> > URL: http://svn.apache.org/r1567996
>


> > +/* 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?


That is correct.


> In that case we have to use atomic functions to
> increment them, otherwise we may skip hit_count == 0 in some cases.
>

No. Assuming that the system does not split 32 bit read
nor write operations, one (or more) of the threads must
increment the value to APR_UINT32_MAX+1==0. No
thread will accidentally add by 2 (or more) missing the
actual overflow.

-- Stefan^2.

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

Posted by Ivan Zhakov <iv...@visualsvn.com>.
On 13 February 2014 22:24,  <st...@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