View | Details | Raw Unified | Return to bug 54363
Collapse All | Expand All

(-)server/util_time.c.orig (-77 / +69 lines)
Lines 15-20 Link Here
15
 */
15
 */
16
16
17
#include "util_time.h"
17
#include "util_time.h"
18
#include <apr_atomic.h>
18
19
19
20
20
/* Number of characters needed to format the microsecond part of a timestamp.
21
/* Number of characters needed to format the microsecond part of a timestamp.
Lines 30-38 Link Here
30
 */
31
 */
31
32
32
struct exploded_time_cache_element {
33
struct exploded_time_cache_element {
33
    apr_int64_t t;
34
    apr_time_exp_t xt; /* First for alignment of copies */
34
    apr_time_exp_t xt;
35
    apr_uint32_t key;
35
    apr_int64_t t_validate; /* please see comments in cached_explode() */
36
};
36
};
37
37
38
/* the "+ 1" is for the current second: */
38
/* the "+ 1" is for the current second: */
Lines 51-142 Link Here
51
51
52
52
53
static apr_status_t cached_explode(apr_time_exp_t *xt, apr_time_t t,
53
static apr_status_t cached_explode(apr_time_exp_t *xt, apr_time_t t,
54
                                   struct exploded_time_cache_element *cache,
54
    struct exploded_time_cache_element *cache,
55
                                   int use_gmt)
55
    apr_status_t (*explode)(apr_time_exp_t *, apr_time_t))
56
{
56
{
57
    apr_int64_t seconds = apr_time_sec(t);
57
#define SECONDS_MASK 0x7FFFFFFF
58
    struct exploded_time_cache_element *cache_element =
58
    /* High bit is used to indicate invalid cache_element */
59
    const apr_uint32_t seconds = apr_time_sec(t) & SECONDS_MASK;
60
    volatile struct exploded_time_cache_element * const cache_element =
59
        &(cache[seconds & TIME_CACHE_MASK]);
61
        &(cache[seconds & TIME_CACHE_MASK]);
60
    struct exploded_time_cache_element cache_element_snapshot;
61
62
    /* The cache is implemented as a ring buffer.  Each second,
62
    /* The cache is implemented as a ring buffer.  Each second,
63
     * it uses a different element in the buffer.  The timestamp
63
     * it uses a different element in the buffer.  The timestamp
64
     * in the element indicates whether the element contains the
64
     * in the element indicates whether the element contains the
65
     * exploded time for the current second (vs the time
65
     * exploded time for the current second (vs the time
66
     * 'now - AP_TIME_RECENT_THRESHOLD' seconds ago).  If the
66
     * 'now - AP_TIME_RECENT_THRESHOLD' seconds ago).  If the
67
     * cached value is for the current time, we use it.  Otherwise,
67
     * cached value is for the current time, we copy the exploded time.
68
     * we compute the apr_time_exp_t and store it in this
68
     * After copying, we check the cache_element to see if it still has the 
69
     * cache element. Note that the timestamp in the cache
69
     * same second. If so, the copy is valid, because we always set the key 
70
     * element is updated only after the exploded time.  Thus
70
     * after copying the exploded time into the cache, and we're using 
71
     * if two threads hit this cache element simultaneously
71
     * memory barriers (implemented with Compare-And-Swap) 
72
     * at the start of a new second, they'll both explode the
72
     * that guarantee total memory ordering.
73
     * time and store it.  I.e., the writers will collide, but
74
     * they'll be writing the same value.
75
     */
73
     */
76
    if (cache_element->t >= seconds) {
74
    const apr_uint32_t key = cache_element->key; 
77
        /* There is an intentional race condition in this design:
75
    /* Above is done speculatively, no memory barrier used.
78
         * in a multithreaded app, one thread might be reading
76
     * It's doing the same thing as apr_atomic_read32, a read of
79
         * from this cache_element to resolve a timestamp from
77
     * memory marked volatile, but without doing the function call. */
80
         * TIME_CACHE_SIZE seconds ago at the same time that
78
    if (seconds == key && seconds != 0) {
81
         * another thread is copying the exploded form of the
79
        /* seconds == 0 may mean cache is uninitialized, so don't use cache */
82
         * current time into the same cache_element.  (I.e., the
80
        *xt = cache_element->xt;
83
         * first thread might hit this element of the ring buffer
81
        /* After copying xt, make sure cache_element was not marked invalid
84
         * just as the element is being recycled.)  This can
82
         * by another thread beginning an update, and that cache_element
85
         * also happen at the start of a new second, if a
83
         * really contained data for our second.
86
         * reader accesses the cache_element after a writer
84
         * Requires memory barrier, so use CAS. */
87
         * has updated cache_element.t but before the writer
85
        if (apr_atomic_cas32(&cache_element->key, seconds, seconds)==seconds) {
88
         * has finished updating the whole cache_element.
86
            xt->tm_usec = (int)apr_time_usec(t);
89
         *
87
            return APR_SUCCESS;
90
         * Rather than trying to prevent this race condition
91
         * with locks, we allow it to happen and then detect
92
         * and correct it.  The detection works like this:
93
         *   Step 1: Take a "snapshot" of the cache element by
94
         *           copying it into a temporary buffer.
95
         *   Step 2: Check whether the snapshot contains consistent
96
         *           data: the timestamps at the start and end of
97
         *           the cache_element should both match the 'seconds'
98
         *           value that we computed from the input time.
99
         *           If these three don't match, then the snapshot
100
         *           shows the cache_element in the middle of an
101
         *           update, and its contents are invalid.
102
         *   Step 3: If the snapshot is valid, use it.  Otherwise,
103
         *           just give up on the cache and explode the
104
         *           input time.
105
         */
106
        memcpy(&cache_element_snapshot, cache_element,
107
               sizeof(struct exploded_time_cache_element));
108
        if ((seconds != cache_element_snapshot.t) ||
109
            (seconds != cache_element_snapshot.t_validate)) {
110
            /* Invalid snapshot */
111
            if (use_gmt) {
112
                return apr_time_exp_gmt(xt, t);
113
            }
114
            else {
115
                return apr_time_exp_lt(xt, t);
116
            }
117
        }
118
        else {
119
            /* Valid snapshot */
120
            memcpy(xt, &(cache_element_snapshot.xt),
121
                   sizeof(apr_time_exp_t));
122
        }
88
        }
123
    }
89
    }
124
    else {
90
    /* Invalid cache element, so calculate the exploded time value.
125
        apr_status_t r;
91
       This is a wait-free algorithm, and we purposely don't spin and
126
        if (use_gmt) {
92
       retry to get from the cache, we just continue and calculate it
127
            r = apr_time_exp_gmt(xt, t);
93
       and do useful work, instead of spinning. */
128
        }
94
    do {
129
        else {
95
        const apr_status_t r = explode(xt, t);
130
            r = apr_time_exp_lt(xt, t);
131
        }
132
        if (r != APR_SUCCESS) {
96
        if (r != APR_SUCCESS) {
133
            return r;
97
            return r;
134
        }
98
        }
135
        cache_element->t = seconds;
99
    } while (0);
136
        memcpy(&(cache_element->xt), xt, sizeof(apr_time_exp_t));
100
    
137
        cache_element->t_validate = seconds;
101
    /* Attempt to update the cache */
102
    
103
    /* To prevent ABA problem, don't update the cache unless we have a
104
     * newer time value (so that we never go from B->A). 
105
     * Handle cases where seconds overflows (e.g. year 2038), 
106
     * and cases where cache is uninitialized.
107
     * Handle overflow, otherwise it will stop caching after overflow,
108
     * until server process is restarted, which may be months later.
109
     */
110
#define OVERFLOW (((SECONDS_MASK)>>1) + 1)
111
    if (key <= SECONDS_MASK /* another thread not updating cache_element */
112
        && seconds != 0 /* new key distinguishable from uninitialized */
113
        && (
114
        (seconds > key && seconds - key < OVERFLOW) || /* normal */
115
        (seconds < key && key - seconds > OVERFLOW) || /* overflow */
116
        (key == 0 && seconds < SECONDS_MASK - 0x100)))
117
        /* cache is perhaps uninitialized, and not recent overflow */
118
    {
119
        if (key == apr_atomic_cas32(&cache_element->key, ~seconds, key))
120
        {   /* We won the race to update this cache_element.
121
             * Above marks cache_element as invalid by using ~seconds, 
122
             * because we are starting an update: it's the start of a
123
             * transaction. */
124
            cache_element->xt = *xt;
125
            /* Finished copying, now update key with our key,
126
             * ending the transaction. Need to use CAS for the
127
             * memory barrier. 
128
             */
129
            apr_atomic_cas32(&cache_element->key, seconds, ~seconds);
130
        }
138
    }
131
    }
139
    xt->tm_usec = (int)apr_time_usec(t);
140
    return APR_SUCCESS;
132
    return APR_SUCCESS;
141
}
133
}
142
134
Lines 144-156 Link Here
144
AP_DECLARE(apr_status_t) ap_explode_recent_localtime(apr_time_exp_t * tm,
136
AP_DECLARE(apr_status_t) ap_explode_recent_localtime(apr_time_exp_t * tm,
145
                                                     apr_time_t t)
137
                                                     apr_time_t t)
146
{
138
{
147
    return cached_explode(tm, t, exploded_cache_localtime, 0);
139
    return cached_explode(tm, t, exploded_cache_localtime, &apr_time_exp_lt);
148
}
140
}
149
141
150
AP_DECLARE(apr_status_t) ap_explode_recent_gmt(apr_time_exp_t * tm,
142
AP_DECLARE(apr_status_t) ap_explode_recent_gmt(apr_time_exp_t * tm,
151
                                               apr_time_t t)
143
                                               apr_time_t t)
152
{
144
{
153
    return cached_explode(tm, t, exploded_cache_gmt, 1);
145
    return cached_explode(tm, t, exploded_cache_gmt, &apr_time_exp_gmt);
154
}
146
}
155
147
156
AP_DECLARE(apr_status_t) ap_recent_ctime(char *date_str, apr_time_t t)
148
AP_DECLARE(apr_status_t) ap_recent_ctime(char *date_str, apr_time_t t)

Return to bug 54363