httpd-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Daniel Lescohier <daniel.lescoh...@cbsi.com>
Subject Re: thread-safety of time conversion caches in util_time.c and mod_log_config.c
Date Sat, 05 Jan 2013 03:07:06 GMT
apr_atomic_read32 is not implemented with a memory barrier.  The
implementation of apr_atomic_read32 in the APR code base is just a read
from a pointer marked volatile.  E.g., here is the atomic/unix/builtins.c
implementation:

APR_DECLARE(apr_uint32_t) apr_atomic_read32(volatile apr_uint32_t *mem)
{
    return *mem;
}

The atomic/unix/builtins.c implementation would have to change to this to
have a memory barrier:

APR_DECLARE(apr_uint32_t) apr_atomic_read32(volatile apr_uint32_t *mem)
{
    __sync_synchronize();
    return *mem;
}

All the other apr atomic implementations would have to change if
apr_atomic_read32 is supposed to mean "with-a-memory-barrier."  All the
current implementations don't implement a memory barrier (all the
implementations use the C definition shown at the beginning of this email),
so I assume apr_atomic_read32 (and apr_atomic_set32) means
"without-a-memory-barrier."

The Apache Portable Runtime API has no "memory barrier" function in the API
(like gcc's builtin __sync_synchronize()), so I had to choose among the
other functions in the API.  I decided to use Compare-And-Swap for the
memory barrier, because the generic Compare-And-Swap concept implies the
use of memory barriers, and also the APR implementation actually implements
a memory barrier in apr_atomic_cas32.  I also could've used
apr_atomic_add32(&cache_element->key, 0)==seconds, but Compare-And-Swap is
the more generic concept, so I used that instead.  I agree, though, for the
read-the-cache_element portion of the function, it'd be better to do just
an atomic_read, instead of a compare-and-swap, if only the APR Atomic API
had a memory barrier function that I could call before the read.

After copying from the time cache_element to this thread's memory allocated
from the request pool, the thread needs a memory barrier when checking the
cache_element->key, in order to make sure another cpu thread/core didn't
start modifying the cache_element while this thread was copying it.  But
note, before doing the copy to this thread's memory, the function doesn't
use a memory barrier, it checks the cache_element->key without a memory
barrier, because it's speculatively doing the copy (because almost all the
time there won't be a conflict), and then doing the validation with a
memory barrier after the copy is done (and in the rare case that the
validation fails, the thread just calculates the time value itself).

For the old code, I haven't seen bad results in practice (not that I
probably would've noticed it), I only noticed that the code is not portably
thread-safe because I was working on a project to upgrade our web servers
to 2.4, and I was updating our own internal custom Apache modules, and I
noticed this when looking at the source of mod_log_config.c.  So, I brought
it up because the algorithm does not look correct.  The problem was that
the old code was supposedly a lock-free and wait-free algorithm, but it
didn't use the atomic processor instructions you need to use in order to
implement lock-free and wait-free algorithms.

On Fri, Jan 4, 2013 at 7:58 PM, Stefan Fritsch <sf@sfritsch.de> wrote:

> On Friday 04 January 2013, Daniel Lescohier wrote:
> > I entered a bug on the thread-safety of the time conversion caches
> > in server/util_time.c and modules/loggers/mod_log_config.c.
> >
> > In brief, they're not thread-safe because:
> >
> >    1. The algorithm depends on total memory ordering, and both the
> > volatile qualifier and memory barriers are not used.
> >    2. The algorithm is subject to the "ABA problem."
>
> I agree that the lack of memory barriers is a problem.
>
> And it ABA problem would not exist if callers of ap_recent_* would
> actually check that the time *is* recent (as written in the docs in
> util_time.h). This is not a problem for the error log, because it
> always uses apr_time_now(). But the request time in mod_log_config may
> be further in the past.
>
> Out of interest, have you seen the function give wrong results in
> practice?
>
> > The details of the problem are here:
> >
> > https://issues.apache.org/bugzilla/show_bug.cgi?id=54363
> >
> > I included in the bug not-yet-tested patches with a different
> > algorithm.
> >
> > Do other people agree that the existing algorithm have the problems
> > explained in detail in the bug?
>
> I haven't reviewed your patches in detail, yet. One thing:
> apr_atomic_read should be enough, you don't need apr_atomic_cas with
> the same value.
>
> Cheers,
> Stefan
>

Mime
View raw message