granicus.if.org Git - apache/blob - server/util_time.c

   1 /* ====================================================================
   2  * The Apache Software License, Version 1.1
   3  *
   4  * Copyright (c) 2001 The Apache Software Foundation.  All rights
   5  * reserved.
   6  *
   7  * Redistribution and use in source and binary forms, with or without
   8  * modification, are permitted provided that the following conditions
   9  * are met:
  10  *
  11  * 1. Redistributions of source code must retain the above copyright
  12  *    notice, this list of conditions and the following disclaimer.
  13  *
  14  * 2. Redistributions in binary form must reproduce the above copyright
  15  *    notice, this list of conditions and the following disclaimer in
  16  *    the documentation and/or other materials provided with the
  17  *    distribution.
  18  *
  19  * 3. The end-user documentation included with the redistribution,
  20  *    if any, must include the following acknowledgment:
  21  *       "This product includes software developed by the
  22  *        Apache Software Foundation (http://www.apache.org/)."
  23  *    Alternately, this acknowledgment may appear in the software itself,
  24  *    if and wherever such third-party acknowledgments normally appear.
  25  *
  26  * 4. The names "Apache" and "Apache Software Foundation" must
  27  *    not be used to endorse or promote products derived from this
  28  *    software without prior written permission. For written
  29  *    permission, please contact apache@apache.org.
  30  *
  31  * 5. Products derived from this software may not be called "Apache",
  32  *    nor may "Apache" appear in their name, without prior written
  33  *    permission of the Apache Software Foundation.
  34  *
  35  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
  36  * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  37  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  38  * DISCLAIMED.  IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
  39  * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  40  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  41  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
  42  * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
  43  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  44  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
  45  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  46  * SUCH DAMAGE.
  47  * ====================================================================
  48  *
  49  * This software consists of voluntary contributions made by many
  50  * individuals on behalf of the Apache Software Foundation.  For more
  51  * information on the Apache Software Foundation, please see
  52  * <http://www.apache.org/>.
  53  *
  54  */
  55
  56 #include "util_time.h"
  57
  58 /* Cache for exploded values of recent timestamps
  59  */
  60
  61 struct exploded_time_cache_element {
  62     apr_int64_t t;
  63     apr_exploded_time_t xt;
  64     apr_int64_t t_validate; /* please see comments in cached_explode() */
  65 };
  66
  67 /* the "+ 1" is for the current second: */
  68 #define TIME_CACHE_SIZE (AP_TIME_RECENT_THRESHOLD + 1)
  69
  70 static struct exploded_time_cache_element exploded_cache_localtime[TIME_CACHE_SIZE];
  71 static struct exploded_time_cache_element exploded_cache_gmt[TIME_CACHE_SIZE];
  72
  73
  74 static apr_status_t cached_explode(apr_exploded_time_t *xt, apr_time_t t,
  75                                    struct exploded_time_cache_element *cache,
  76                                    int use_gmt)
  77 {
  78     apr_int64_t seconds = t / APR_USEC_PER_SEC;
  79     struct exploded_time_cache_element *cache_element =
  80         &(cache[seconds % TIME_CACHE_SIZE]);
  81     struct exploded_time_cache_element cache_element_snapshot;
  82
  83     /* The cache is implemented as a ring buffer.  Each second,
  84      * it uses a different element in the buffer.  The timestamp
  85      * in the element indicates whether the element contains the
  86      * exploded time for the current second (vs the time
  87      * 'now - AP_TIME_RECENT_THRESHOLD' seconds ago).  If the
  88      * cached value is for the current time, we use it.  Otherwise,
  89      * we compute the apr_exploded_time_t and store it in this
  90      * cache element. Note that the timestamp in the cache
  91      * element is updated only after the exploded time.  Thus
  92      * if two threads hit this cache element simultaneously
  93      * at the start of a new second, they'll both explode the
  94      * time and store it.  I.e., the writers will collide, but
  95      * they'll be writing the same value.
  96      */
  97     if (cache_element->t >= seconds) {
  98         /* There is an intentional race condition in this design:
  99          * in a multithreaded app, one thread might be reading
 100          * from this cache_element to resolve a timestamp from
 101          * TIME_CACHE_SIZE seconds ago at the same time that
 102          * another thread is copying the exploded form of the
 103          * current time into the same cache_element.  (I.e., the
 104          * first thread might hit this element of the ring buffer
 105          * just as the element is being recycled.)  This can
 106          * also happen at the start of a new second, if a
 107          * reader accesses the cache_element after a writer
 108          * has updated cache_element.t but before the writer
 109          * has finished updating the whole cache_element.
 110          *
 111          * Rather than trying to prevent this race condition
 112          * with locks, we allow it to happen and then detect
 113          * and correct it.  The detection works like this:
 114          *   Step 1: Take a "snapshot" of the cache element by
 115          *           copying it into a temporary buffer.
 116          *   Step 2: Check whether the snapshot contains consistent
 117          *           data: the timestamps at the start and end of
 118          *           the cache_element should both match the 'seconds'
 119          *           value that we computed from the input time.
 120          *           If these three don't match, then the snapshot
 121          *           shows the cache_element in the middle of an
 122          *           update, and its contents are invalid.
 123          *   Step 3: If the snapshot is valid, use it.  Otherwise,
 124          *           just give up on the cache and explode the
 125          *           input time.
 126          */
 127         memcpy(&cache_element_snapshot, cache_element,
 128                sizeof(struct exploded_time_cache_element));
 129         if ((seconds != cache_element_snapshot.t) ||
 130             (seconds != cache_element_snapshot.t_validate)) {
 131             /* Invalid snapshot */
 132             if (use_gmt) {
 133                 return apr_explode_gmt(xt, t);
 134             }
 135             else {
 136                 return apr_explode_localtime(xt, t);
 137             }
 138         }
 139         else {
 140             /* Valid snapshot */
 141             memcpy(xt, &(cache_element_snapshot.xt),
 142                    sizeof(apr_exploded_time_t));
 143         }
 144     }
 145     else {
 146         apr_status_t r;
 147         if (use_gmt) {
 148             r = apr_explode_gmt(xt, t);
 149         }
 150         else {
 151             r = apr_explode_localtime(xt, t);
 152         }
 153         if (!APR_STATUS_IS_SUCCESS(r)) {
 154             return r;
 155         }
 156         cache_element->t = seconds;
 157         memcpy(&(cache_element->xt), xt, sizeof(apr_exploded_time_t));
 158         cache_element->t_validate = seconds;
 159     }
 160     xt->tm_usec = (int)(t % APR_USEC_PER_SEC);
 161     return APR_SUCCESS;
 162 }
 163
 164
 165 AP_DECLARE(apr_status_t) ap_explode_recent_localtime(apr_exploded_time_t * tm,
 166                                                      apr_time_t t)
 167 {
 168     return cached_explode(tm, t, exploded_cache_localtime, 0);
 169 }
 170
 171 AP_DECLARE(apr_status_t) ap_explode_recent_gmt(apr_exploded_time_t * tm,
 172                                                apr_time_t t)
 173 {
 174     return cached_explode(tm, t, exploded_cache_gmt, 1);
 175 }