util_time.c revision e302f38fd646764ce1a1e1c578d794aef514a9e5
f3ec420152ca921e4c1ce77782f51b53f659018dnd/* Licensed to the Apache Software Foundation (ASF) under one or more
f3ec420152ca921e4c1ce77782f51b53f659018dnd * contributor license agreements. See the NOTICE file distributed with
fd9abdda70912b99b24e3bf1a38f26fde908a74cnd * this work for additional information regarding copyright ownership.
fd9abdda70912b99b24e3bf1a38f26fde908a74cnd * The ASF licenses this file to You under the Apache License, Version 2.0
fd9abdda70912b99b24e3bf1a38f26fde908a74cnd * (the "License"); you may not use this file except in compliance with
f3ec420152ca921e4c1ce77782f51b53f659018dnd * the License. You may obtain a copy of the License at
96ad5d81ee4a2cc66a4ae19893efc8aa6d06fae7jailletc * Unless required by applicable law or agreed to in writing, software
f3ec420152ca921e4c1ce77782f51b53f659018dnd * distributed under the License is distributed on an "AS IS" BASIS,
f3ec420152ca921e4c1ce77782f51b53f659018dnd * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
d29d9ab4614ff992b0e8de6e2b88d52b6f1f153erbowen * See the License for the specific language governing permissions and
2e545ce2450a9953665f701bb05350f0d3f26275nd * limitations under the License.
3f08db06526d6901aa08c110b5bc7dde6bc39905nd/* Number of characters needed to format the microsecond part of a timestamp.
f3ec420152ca921e4c1ce77782f51b53f659018dnd * Microseconds have 6 digits plus one separator character makes 7.
f3ec420152ca921e4c1ce77782f51b53f659018dnd/* Length of ISO 8601 date/time */
f3ec420152ca921e4c1ce77782f51b53f659018dnd/* Cache for exploded values of recent timestamps
d03cac4d8ba79a23cfda410d35b614b0d805ba4cnilgun apr_int64_t t_validate; /* please see comments in cached_explode() */
d03cac4d8ba79a23cfda410d35b614b0d805ba4cnilgun/* the "+ 1" is for the current second: */
d03cac4d8ba79a23cfda410d35b614b0d805ba4cnilgun#define TIME_CACHE_SIZE (AP_TIME_RECENT_THRESHOLD + 1)
f3ec420152ca921e4c1ce77782f51b53f659018dnd/* Note that AP_TIME_RECENT_THRESHOLD is defined to
f3ec420152ca921e4c1ce77782f51b53f659018dnd * be a power of two minus one in util_time.h, so that
f3ec420152ca921e4c1ce77782f51b53f659018dnd * we can replace a modulo operation with a bitwise AND
f3ec420152ca921e4c1ce77782f51b53f659018dnd * when hashing items into a cache of size
d03cac4d8ba79a23cfda410d35b614b0d805ba4cnilgun * AP_TIME_RECENT_THRESHOLD+1
f3ec420152ca921e4c1ce77782f51b53f659018dndstatic struct exploded_time_cache_element exploded_cache_localtime[TIME_CACHE_SIZE];
f3ec420152ca921e4c1ce77782f51b53f659018dndstatic struct exploded_time_cache_element exploded_cache_gmt[TIME_CACHE_SIZE];
f3ec420152ca921e4c1ce77782f51b53f659018dndstatic apr_status_t cached_explode(apr_time_exp_t *xt, apr_time_t t,
d03cac4d8ba79a23cfda410d35b614b0d805ba4cnilgun struct exploded_time_cache_element cache_element_snapshot;
f3ec420152ca921e4c1ce77782f51b53f659018dnd /* The cache is implemented as a ring buffer. Each second,
f3ec420152ca921e4c1ce77782f51b53f659018dnd * it uses a different element in the buffer. The timestamp
f3ec420152ca921e4c1ce77782f51b53f659018dnd * in the element indicates whether the element contains the
f3ec420152ca921e4c1ce77782f51b53f659018dnd * exploded time for the current second (vs the time
d03cac4d8ba79a23cfda410d35b614b0d805ba4cnilgun * 'now - AP_TIME_RECENT_THRESHOLD' seconds ago). If the
d03cac4d8ba79a23cfda410d35b614b0d805ba4cnilgun * cached value is for the current time, we use it. Otherwise,
d03cac4d8ba79a23cfda410d35b614b0d805ba4cnilgun * we compute the apr_time_exp_t and store it in this
d03cac4d8ba79a23cfda410d35b614b0d805ba4cnilgun * cache element. Note that the timestamp in the cache
d03cac4d8ba79a23cfda410d35b614b0d805ba4cnilgun * element is updated only after the exploded time. Thus
f3ec420152ca921e4c1ce77782f51b53f659018dnd * if two threads hit this cache element simultaneously
f3ec420152ca921e4c1ce77782f51b53f659018dnd * at the start of a new second, they'll both explode the
d03cac4d8ba79a23cfda410d35b614b0d805ba4cnilgun * time and store it. I.e., the writers will collide, but
d03cac4d8ba79a23cfda410d35b614b0d805ba4cnilgun * they'll be writing the same value.
d03cac4d8ba79a23cfda410d35b614b0d805ba4cnilgun /* There is an intentional race condition in this design:
d03cac4d8ba79a23cfda410d35b614b0d805ba4cnilgun * in a multithreaded app, one thread might be reading
d03cac4d8ba79a23cfda410d35b614b0d805ba4cnilgun * from this cache_element to resolve a timestamp from
f3ec420152ca921e4c1ce77782f51b53f659018dnd * TIME_CACHE_SIZE seconds ago at the same time that
d03cac4d8ba79a23cfda410d35b614b0d805ba4cnilgun * another thread is copying the exploded form of the
d03cac4d8ba79a23cfda410d35b614b0d805ba4cnilgun * current time into the same cache_element. (I.e., the
f3ec420152ca921e4c1ce77782f51b53f659018dnd * first thread might hit this element of the ring buffer
f3ec420152ca921e4c1ce77782f51b53f659018dnd * just as the element is being recycled.) This can
d03cac4d8ba79a23cfda410d35b614b0d805ba4cnilgun * also happen at the start of a new second, if a
f3ec420152ca921e4c1ce77782f51b53f659018dnd * reader accesses the cache_element after a writer
d03cac4d8ba79a23cfda410d35b614b0d805ba4cnilgun * has updated cache_element.t but before the writer
d03cac4d8ba79a23cfda410d35b614b0d805ba4cnilgun * has finished updating the whole cache_element.
f3ec420152ca921e4c1ce77782f51b53f659018dnd * Rather than trying to prevent this race condition
d03cac4d8ba79a23cfda410d35b614b0d805ba4cnilgun * with locks, we allow it to happen and then detect
d03cac4d8ba79a23cfda410d35b614b0d805ba4cnilgun * and correct it. The detection works like this:
d03cac4d8ba79a23cfda410d35b614b0d805ba4cnilgun * Step 1: Take a "snapshot" of the cache element by
f3ec420152ca921e4c1ce77782f51b53f659018dnd * copying it into a temporary buffer.
f3ec420152ca921e4c1ce77782f51b53f659018dnd * Step 2: Check whether the snapshot contains consistent
d03cac4d8ba79a23cfda410d35b614b0d805ba4cnilgun * data: the timestamps at the start and end of
f3ec420152ca921e4c1ce77782f51b53f659018dnd * the cache_element should both match the 'seconds'
f3ec420152ca921e4c1ce77782f51b53f659018dnd * value that we computed from the input time.
f3ec420152ca921e4c1ce77782f51b53f659018dnd * If these three don't match, then the snapshot
f3ec420152ca921e4c1ce77782f51b53f659018dnd * shows the cache_element in the middle of an
94cfb5d816f18c39adb74a03b6502ab73e35a73bnilgun * update, and its contents are invalid.
94cfb5d816f18c39adb74a03b6502ab73e35a73bnilgun * Step 3: If the snapshot is valid, use it. Otherwise,
94cfb5d816f18c39adb74a03b6502ab73e35a73bnilgun * just give up on the cache and explode the
94cfb5d816f18c39adb74a03b6502ab73e35a73bnilgun * input time.
f3ec420152ca921e4c1ce77782f51b53f659018dnd sizeof(struct exploded_time_cache_element));
f3ec420152ca921e4c1ce77782f51b53f659018dnd /* Invalid snapshot */
94cfb5d816f18c39adb74a03b6502ab73e35a73bnilgun /* Valid snapshot */
f3ec420152ca921e4c1ce77782f51b53f659018dnd memcpy(&(cache_element->xt), xt, sizeof(apr_time_exp_t));
d03cac4d8ba79a23cfda410d35b614b0d805ba4cnilgunAP_DECLARE(apr_status_t) ap_explode_recent_localtime(apr_time_exp_t * tm,
d03cac4d8ba79a23cfda410d35b614b0d805ba4cnilgun return cached_explode(tm, t, exploded_cache_localtime, 0);
f3ec420152ca921e4c1ce77782f51b53f659018dndAP_DECLARE(apr_status_t) ap_explode_recent_gmt(apr_time_exp_t * tm,
f3ec420152ca921e4c1ce77782f51b53f659018dndAP_DECLARE(apr_status_t) ap_recent_ctime(char *date_str, apr_time_t t)
f3ec420152ca921e4c1ce77782f51b53f659018dnd return ap_recent_ctime_ex(date_str, t, AP_CTIME_OPTION_NONE, &len);
f3ec420152ca921e4c1ce77782f51b53f659018dndAP_DECLARE(apr_status_t) ap_recent_ctime_ex(char *date_str, apr_time_t t,
f3ec420152ca921e4c1ce77782f51b53f659018dnd /* ### This code is a clone of apr_ctime(), except that it
f3ec420152ca921e4c1ce77782f51b53f659018dnd * uses ap_explode_recent_localtime() instead of apr_time_exp_lt().
f3ec420152ca921e4c1ce77782f51b53f659018dnd const char *s;
f3ec420152ca921e4c1ce77782f51b53f659018dnd /* Calculate the needed buffer length */
f3ec420152ca921e4c1ce77782f51b53f659018dnd /* Check the provided buffer length */
f3ec420152ca921e4c1ce77782f51b53f659018dnd /* example without options: "Wed Jun 30 21:49:08 1993" */
f3ec420152ca921e4c1ce77782f51b53f659018dnd /* 123456789012345678901234 */
f3ec420152ca921e4c1ce77782f51b53f659018dnd /* example for compact format: "1993-06-30 21:49:08" */
f3ec420152ca921e4c1ce77782f51b53f659018dnd /* 1234567890123456789 */
f3ec420152ca921e4c1ce77782f51b53f659018dndAP_DECLARE(apr_status_t) ap_recent_rfc822_date(char *date_str, apr_time_t t)
d03cac4d8ba79a23cfda410d35b614b0d805ba4cnilgun /* ### This code is a clone of apr_rfc822_date(), except that it
f3ec420152ca921e4c1ce77782f51b53f659018dnd * uses ap_explode_recent_gmt() instead of apr_time_exp_gmt().
d03cac4d8ba79a23cfda410d35b614b0d805ba4cnilgun const char *s;
f3ec420152ca921e4c1ce77782f51b53f659018dnd /* example: "Sat, 08 Jan 2000 18:31:41 GMT" */
f3ec420152ca921e4c1ce77782f51b53f659018dnd /* 12345678901234567890123456789 */
f3ec420152ca921e4c1ce77782f51b53f659018dnd /* This routine isn't y10k ready. */