varnish-cache/lib/libvarnish/vtim.c
1
/*-
2
 * Copyright (c) 2006 Verdens Gang AS
3
 * Copyright (c) 2006-2011 Varnish Software AS
4
 * All rights reserved.
5
 *
6
 * Author: Poul-Henning Kamp <phk@phk.freebsd.dk>
7
 *
8
 * Redistribution and use in source and binary forms, with or without
9
 * modification, are permitted provided that the following conditions
10
 * are met:
11
 * 1. Redistributions of source code must retain the above copyright
12
 *    notice, this list of conditions and the following disclaimer.
13
 * 2. Redistributions in binary form must reproduce the above copyright
14
 *    notice, this list of conditions and the following disclaimer in the
15
 *    documentation and/or other materials provided with the distribution.
16
 *
17
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
18
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20
 * ARE DISCLAIMED.  IN NO EVENT SHALL AUTHOR OR CONTRIBUTORS BE LIABLE
21
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
22
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
23
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
24
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
25
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
26
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
27
 * SUCH DAMAGE.
28
 *
29
 * Semi-trivial functions to handle HTTP header timestamps according to
30
 * RFC 2616 section 3.3.
31
 *
32
 * We must parse four different formats:
33
 *       000000000011111111112222222222
34
 *       012345678901234567890123456789
35
 *       ------------------------------
36
 *      "Sun, 06 Nov 1994 08:49:37 GMT"         RFC822 & RFC1123
37
 *      "Sunday, 06-Nov-94 08:49:37 GMT"        RFC850
38
 *      "Sun Nov  6 08:49:37 1994"              ANSI-C asctime()
39
 *      "1994-11-06T08:49:37"                   ISO 8601
40
 *
41
 * And always output the RFC1123 format.
42
 *
43
 * So why are these functions hand-built ?
44
 *
45
 * Because the people behind POSIX were short-sighted morons who didn't think
46
 * anybody would ever need to deal with timestamps in multiple different
47
 * timezones at the same time -- for that matter, convert timestamps to
48
 * broken down UTC/GMT time.
49
 *
50
 * We could, and used to, get by by smashing our TZ variable to "UTC" but
51
 * that ruins the LOCALE for VMODs.
52
 *
53
 */
54
55
#include "config.h"
56
57
#include <time.h>
58
#include <sys/time.h>
59
60
#include <math.h>
61
#include <stdio.h>
62
#include <stdlib.h>
63
#include <string.h>
64
#ifdef __MACH__
65
#include <mach/mach_time.h>
66
#endif
67
68
#include "vdef.h"
69
70
#include "vas.h"
71
#include "vtim.h"
72
73
/* relax vtim parsing */
74
unsigned VTIM_postel = 0;
75
76
static const char * const weekday_name[] = {
77
        "Sun", "Mon", "Tue", "Wed", "Thu", "Fri", "Sat"
78
};
79
80
static const char * const more_weekday[] = {
81
        "day", "day", "sday", "nesday", "rsday", "day", "urday"
82
};
83
84
static const char * const month_name[] = {
85
        "Jan", "Feb", "Mar", "Apr", "May", "Jun",
86
        "Jul", "Aug", "Sep", "Oct", "Nov", "Dec"
87
};
88
89
static const int days_in_month[] = {
90
        31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31
91
};
92
93
static const int days_before_month[] = {
94
        0, 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334
95
};
96
97
#ifdef __MACH__
98
// http://stackoverflow.com/a/21352348
99
static uint64_t mt_base;
100
static double   mt_scale;
101
102
static void
103
mach_time_init(void)
104
{
105
        mach_timebase_info_data_t timebase;
106
107
        mt_base = mach_absolute_time();
108
109
        AZ(mach_timebase_info(&timebase));
110
        mt_scale = (double)timebase.numer / (double)timebase.denom * 1e-9;
111
}
112
113
static __attribute__((constructor)) void
114
init(void)
115
{
116
        mach_time_init();
117
}
118
#endif
119
120
/*
121
 * On older Solaris-incarnations, gethrtime() was faster than
122
 * clock_gettime(CLOCK_MONOTONIC). Our configure script prefers
123
 * clock_gettime if it is consistently at least twice as fast as
124
 * gethrtime(), which is the case on modern Solaris descendents.
125
 */
126
127
vtim_mono
128 853296
VTIM_mono(void)
129
{
130
#if defined(HAVE_CLOCK_GETTIME) && !defined(USE_GETHRTIME)
131
        struct timespec ts;
132
133 853296
        AZ(clock_gettime(CLOCK_MONOTONIC, &ts));
134 853425
        return (ts.tv_sec + 1e-9 * ts.tv_nsec);
135
#elif defined(HAVE_GETHRTIME)
136
        return (gethrtime() * 1e-9);
137
#elif defined(__MACH__)
138
        uint64_t mt = mach_absolute_time() - mt_base;
139
140
        return (mt * mt_scale);
141
#else
142
#error Varnish needs some monotonic time source
143
#endif
144
}
145
146
vtim_real
147 255941
VTIM_real(void)
148
{
149
#ifdef HAVE_CLOCK_GETTIME
150
        struct timespec ts;
151
152 255941
        AZ(clock_gettime(CLOCK_REALTIME, &ts));
153 256024
        return (ts.tv_sec + 1e-9 * ts.tv_nsec);
154
#else
155
        struct timeval tv;
156
157
        AZ(gettimeofday(&tv, NULL));
158
        return (tv.tv_sec + 1e-6 * tv.tv_usec);
159
#endif
160
}
161
162
void
163 8166
VTIM_format(vtim_real t, char *p)
164
{
165
        struct tm tm;
166
        time_t tt;
167
168 8166
        tt = (time_t) t;
169 8166
        (void)gmtime_r(&tt, &tm);
170 8166
        AN(snprintf(p, VTIM_FORMAT_SIZE, "%s, %02d %s %4d %02d:%02d:%02d GMT",
171
            weekday_name[tm.tm_wday], tm.tm_mday, month_name[tm.tm_mon],
172
            tm.tm_year + 1900, tm.tm_hour, tm.tm_min, tm.tm_sec));
173 8166
}
174
175
#ifdef TEST_DRIVER
176
#define FAIL()  \
177
        do { printf("\nFAIL <<%d>>\n", __LINE__); return (0); } while (0)
178
#else
179
#define FAIL()  \
180
        do { return (0); } while (0)
181
#endif
182
183
#define DIGIT(mult, fld)                                        \
184
        do {                                                    \
185
                if (*p < '0' || *p > '9')                       \
186
                        FAIL();                                 \
187
                fld += (*p - '0') * mult;                       \
188
                p++;                                            \
189
        } while(0)
190
191
#define MUSTBE(chr)                                             \
192
        do {                                                    \
193
                if (*p != chr)                                  \
194
                        FAIL();                                 \
195
                p++;                                            \
196
        } while(0)
197
198
#define WEEKDAY()                                               \
199
        do {                                                    \
200
                int i;                                          \
201
                for (i = 0; i < 7; i++) {                       \
202
                        if (!memcmp(p, weekday_name[i], 3)) {   \
203
                                weekday = i;                    \
204
                                break;                          \
205
                        }                                       \
206
                }                                               \
207
                if (i == 7)                                     \
208
                        FAIL();                                 \
209
                p += 3;                                         \
210
        } while(0)
211
212
213
#define MONTH()                                                 \
214
        do {                                                    \
215
                int i;                                          \
216
                for (i = 0; i < 12; i++) {                      \
217
                        if (!memcmp(p, month_name[i], 3)) {     \
218
                                month = i + 1;                  \
219
                                break;                          \
220
                        }                                       \
221
                }                                               \
222
                if (i == 12)                                    \
223
                        FAIL();                                 \
224
                p += 3;                                         \
225
        } while(0)
226
227
#define TIMESTAMP()                                             \
228
        do {                                                    \
229
                DIGIT(10, hour);                                \
230
                DIGIT(1, hour);                                 \
231
                MUSTBE(':');                                    \
232
                DIGIT(10, min);                                 \
233
                DIGIT(1, min);                                  \
234
                MUSTBE(':');                                    \
235
                DIGIT(10, sec);                                 \
236
                DIGIT(1, sec);                                  \
237
        } while(0)
238
239
vtim_real
240 7160
VTIM_parse(const char *p)
241
{
242
        vtim_real t;
243 7160
        int month = 0, year = 0, weekday = -1, mday = 0;
244 7160
        int hour = 0, min = 0, sec = 0;
245
        int d, leap;
246
247 7160
        if (p == NULL || *p == '\0')
248 6
                FAIL();
249
250 14312
        while (*p == ' ')
251 4
                p++;
252
253 7154
        if (*p >= '0' && *p <= '9') {
254
                /* ISO8601 -- "1994-11-06T08:49:37" */
255 24
                DIGIT(1000, year);
256 24
                DIGIT(100, year);
257 24
                DIGIT(10, year);
258 24
                DIGIT(1, year);
259 24
                MUSTBE('-');
260 12
                DIGIT(10, month);
261 12
                DIGIT(1, month);
262 12
                MUSTBE('-');
263 12
                DIGIT(10, mday);
264 12
                DIGIT(1, mday);
265 12
                MUSTBE('T');
266 12
                TIMESTAMP();
267
        } else {
268 7130
                WEEKDAY();
269 7126
                assert(weekday >= 0 && weekday <= 6);
270 7126
                if (*p == ',') {
271
                        /* RFC822 & RFC1123 - "Sun, 06 Nov 1994 08:49:37 GMT" */
272 3934
                        p++;
273 3934
                        MUSTBE(' ');
274 3934
                        if (VTIM_postel && *p && p[1] == ' ')
275 6
                                DIGIT(1, mday);
276
                        else {
277 3928
                                DIGIT(10, mday);
278 3928
                                DIGIT(1, mday);
279
                        }
280 3934
                        MUSTBE(' ');
281 3934
                        MONTH();
282 3934
                        MUSTBE(' ');
283 3934
                        DIGIT(1000, year);
284 3934
                        DIGIT(100, year);
285 3934
                        DIGIT(10, year);
286 3934
                        DIGIT(1, year);
287 3934
                        MUSTBE(' ');
288 3934
                        TIMESTAMP();
289 3934
                        MUSTBE(' ');
290 3934
                        MUSTBE('G');
291 3934
                        MUSTBE('M');
292 3934
                        MUSTBE('T');
293 3192
                } else if (*p == ' ') {
294
                        /* ANSI-C asctime() -- "Sun Nov  6 08:49:37 1994" */
295 1590
                        p++;
296 1590
                        MONTH();
297 1584
                        MUSTBE(' ');
298 1584
                        if (*p != ' ')
299 6
                                DIGIT(10, mday);
300
                        else
301 1578
                                p++;
302 1584
                        DIGIT(1, mday);
303 1584
                        MUSTBE(' ');
304 1584
                        TIMESTAMP();
305 1584
                        MUSTBE(' ');
306 1584
                        DIGIT(1000, year);
307 1584
                        DIGIT(100, year);
308 1584
                        DIGIT(10, year);
309 1584
                        DIGIT(1, year);
310 1602
                } else if (!memcmp(p, more_weekday[weekday],
311
                    strlen(more_weekday[weekday]))) {
312
                        /* RFC850 -- "Sunday, 06-Nov-94 08:49:37 GMT" */
313 1596
                        p += strlen(more_weekday[weekday]);
314 1596
                        MUSTBE(',');
315 1596
                        MUSTBE(' ');
316 1596
                        DIGIT(10, mday);
317 1596
                        DIGIT(1, mday);
318 1596
                        MUSTBE('-');
319 1596
                        MONTH();
320 1596
                        MUSTBE('-');
321 1596
                        DIGIT(10, year);
322 1596
                        DIGIT(1, year);
323 1596
                        year += 1900;
324 1596
                        if (year < 1969)
325 18
                                year += 100;
326 1596
                        MUSTBE(' ');
327 1596
                        TIMESTAMP();
328 1596
                        MUSTBE(' ');
329 1596
                        MUSTBE('G');
330 1596
                        MUSTBE('M');
331 1596
                        MUSTBE('T');
332
                } else
333 6
                        FAIL();
334
        }
335
336 14258
        while (*p == ' ')
337 6
                p++;
338
339 7126
        if (*p != '\0')
340 6
                FAIL();
341
342 7120
        if (sec < 0 || sec > 60)        /* Leapseconds! */
343 6
                FAIL();
344 7114
        if (min < 0 || min > 59)
345 6
                FAIL();
346 7108
        if (hour < 0 || hour > 23)
347 6
                FAIL();
348 7102
        if (month < 1 || month > 12)
349 6
                FAIL();
350 7096
        if (mday < 1 || mday > days_in_month[month - 1])
351 6
                FAIL();
352 7090
        if (year < 1899)
353 0
                FAIL();
354
355 7090
        leap =
356 7090
            ((year) % 4) == 0 && (((year) % 100) != 0 || ((year) % 400) == 0);
357
358 7090
        if (month == 2 && mday > 28 && !leap)
359 6
                FAIL();
360
361 7084
        if (sec == 60)                  /* Ignore Leapseconds */
362 6
                sec--;
363
364 7084
        t = ((hour * 60.) + min) * 60. + sec;
365
366 7084
        d = (mday - 1) + days_before_month[month - 1];
367
368 7084
        if (month > 2 && leap)
369 124
                d++;
370
371 7084
        d += (year % 100) * 365;        /* There are 365 days in a year */
372
373 7084
        if ((year % 100) > 0)           /* And a leap day every four years */
374 7084
                d += (((year % 100) - 1) / 4);
375
376 7084
        d += ((year / 100) - 20) *      /* Days relative to y2000 */
377
            (100 * 365 + 24);           /* 24 leapdays per year in a century */
378
379 7084
        d += ((year - 1) / 400) - 4;    /* And one more every 400 years */
380
381
        /*
382
         * Now check weekday, if we have one.
383
         * 6 is because 2000-01-01 was a saturday.
384
         * 10000 is to make sure the modulus argument is always positive
385
         */
386 7084
        if (weekday != -1 && (d + 6 + 7 * 10000) % 7 != weekday)
387 12
                FAIL();
388
389 7072
        t += d * 86400.;
390
391 7072
        t += 10957. * 86400.;           /* 10957 days frm UNIX epoch to y2000 */
392
393 7072
        return (t);
394
}
395
396
void
397 253353
VTIM_sleep(vtim_dur t)
398
{
399
#ifdef HAVE_NANOSLEEP
400
        struct timespec ts;
401
402 253353
        ts = VTIM_timespec(t);
403
404 253324
        (void)nanosleep(&ts, NULL);
405
#else
406
        if (t >= 1.) {
407
                (void)sleep(floor(t));
408
                t -= floor(t);
409
        }
410
        /* XXX: usleep() is not mandated to be thread safe */
411
        t *= 1e6;
412
        if (t > 0)
413
                (void)usleep(floor(t));
414
#endif
415 245196
}
416
417
struct timeval
418 7460
VTIM_timeval(vtim_real t)
419
{
420
        struct timeval tv;
421
422 7460
        AZ(isnan(t));
423 7460
        tv.tv_sec = (time_t)trunc(t);
424 7460
        tv.tv_usec = (int)(1e6 * (t - tv.tv_sec));
425 7460
        return (tv);
426
}
427
428
struct timespec
429 253297
VTIM_timespec(vtim_real t)
430
{
431
        struct timespec tv;
432
433 253297
        AZ(isnan(t));
434 253357
        tv.tv_sec = (time_t)trunc(t);
435 253357
        tv.tv_nsec = (int)(1e9 * (t - tv.tv_sec));
436 253357
        return (tv);
437
}
438
439
440
#ifdef TEST_DRIVER
441
442
/**********************************************************************
443
 * Compile with:
444
 *      cc -o foo -DTEST_DRIVER -I../.. -I../../include vtim.c vas.c -lm
445
 * Test with:
446
 *      ./foo
447
 */
448
449
#include <stdint.h>
450
451
static void
452
tst(const char *s, time_t good)
453
{
454
        time_t t;
455
        char buf[BUFSIZ];
456
457
        t = VTIM_parse(s);
458
        VTIM_format(t, buf);
459
        printf("%-30s -> %12jd -> %s\n", s, (intmax_t)t, buf);
460
        if (t != good) {
461
                printf("Parse error! Got: %jd should have %jd diff %jd\n",
462
                    (intmax_t)t, (intmax_t)good, (intmax_t)(t - good));
463
                exit(4);
464
        }
465
}
466
467
/* XXX keep as double for the time being */
468
static int
469
tst_delta_check(const char *name, double begin, double end, vtim_dur ref)
470
{
471
        const double tol_max = 1.1;
472
        const double tol_min = 1;
473
474
        printf("%s delta for %fs sleep: %f\n", name, ref, (end - begin));
475
476
        if ((end - begin) > tol_max * ref) {
477
                printf("%s delta above tolerance: ((%f - %f) = %f) > %f\n",
478
                    name, end, begin, (end - begin), tol_max);
479
                return (1);
480
        } else if ((end - begin) < tol_min * ref) {
481
                printf("%s delta below tolerance: ((%f - %f) = %f) < %f\n",
482
                    name, end, begin, (end - begin), tol_min);
483
                return (1);
484
        }
485
        return (0);
486
}
487
488
static void
489
tst_delta()
490
{
491
        vtim_mono m_begin, m_end;
492
        vtim_real r_begin, r_end;
493
        const vtim_dur ref = 1;
494
        int err = 0;
495
496
        r_begin = VTIM_real();
497
        m_begin = VTIM_mono();
498
        VTIM_sleep(ref);
499
        r_end = VTIM_real();
500
        m_end = VTIM_mono();
501
502
        err += tst_delta_check("VTIM_mono", m_begin, m_end, ref);
503
        err += tst_delta_check("VTIM_real", r_begin, r_end, ref);
504
505
        if (err) {
506
                printf("%d time delta test errors\n", err);
507
                exit(4);
508
        }
509
}
510
511
static void
512
bench()
513
{
514
        vtim_mono s, e;
515
        vtim_mono t_m;
516
        vtim_real t_r;
517
        unsigned long t_i;
518
        int i;
519
        char buf[64];
520
521
        t_r = 0;
522
        s = VTIM_mono();
523
        for (i=0; i<100000; i++)
524
                t_r += VTIM_real();
525
        e = VTIM_mono();
526
        printf("real: %fs / %d = %fns - tst val %f\n",
527
            e - s, i, 1e9 * (e - s) / i, t_r);
528
529
        t_i = 0;
530
        s = VTIM_mono();
531
        for (i=0; i<100000; i++)
532
                t_m += VTIM_mono();
533
        e = VTIM_mono();
534
        printf("mono: %fs / %d = %fns - tst val %f\n",
535
            e - s, i, 1e9 * (e - s) / i, t_m);
536
537
        t_i = 0;
538
        s = VTIM_mono();
539
        for (i=0; i<100000; i++) {
540
                snprintf(buf, sizeof(buf), "%.6f", s);
541
                t_i += buf[4];
542
        }
543
        e = VTIM_mono();
544
        printf("printf %%.6f: %fs / %d = %fns - tst val %lu %s\n",
545
            e - s, i, 1e9 * (e - s) / i, t_i, buf);
546
547
        t_i = 0;
548
        s = VTIM_mono();
549
        for (i=0; i<100000; i++) {
550
                snprintf(buf, sizeof(buf), "%ju.%06ju",
551
                    (uint64_t)floor(s),
552
                    (uint64_t)floor((s * 1e6)) % 1000000UL);
553
                t_i += buf[4];
554
        }
555
        e = VTIM_mono();
556
        printf("printf %%ju.%%06ju: %fs / %d = %fns - tst val %lu %s\n",
557
            e - s, i, 1e9 * (e - s) / i, t_i, buf);
558
}
559
560
void
561
parse_check(time_t t, const char *s)
562
{
563
        vtim_real tt;
564
        char buf[BUFSIZ];
565
566
        tt = VTIM_parse(s);
567
        if (tt != t) {
568
                VTIM_format(tt, buf);
569
                printf("  fm: %12jd <%s>\n", (intmax_t)t, s);
570
                printf("  to: %12.0f <%s>\n", tt, buf);
571
                exit(2);
572
        }
573
}
574
575
int
576
main(int argc, char **argv)
577
{
578
        time_t t;
579
        struct tm tm;
580
        char buf[BUFSIZ];
581
        char buf1[BUFSIZ];
582
583
        AZ(setenv("TZ", "UTC", 1));
584
        assert(sizeof t >= 8);
585
586
        bench();
587
588
        /* Brute force test against libc version */
589
        for (t = -2209852800; t < 20000000000; t += 3599) {
590
                gmtime_r(&t, &tm);
591
                strftime(buf1, sizeof buf1, "%a, %d %b %Y %T GMT", &tm);
592
                VTIM_format(t, buf);
593
                if (strcmp(buf, buf1)) {
594
                        printf("libc: <%s> Vtim <%s> %jd\n",
595
                            buf1, buf, (intmax_t)t);
596
                        exit(2);
597
                }
598
                parse_check(t, buf1);
599
600
                strftime(buf1, sizeof buf1, "%a %b %e %T %Y", &tm);
601
                parse_check(t, buf1);
602
603
                strftime(buf1, sizeof buf1, "%Y-%m-%dT%T", &tm);
604
                parse_check(t, buf1);
605
606
                if (tm.tm_year >= 69 && tm.tm_year < 169) {
607
                        strftime(buf1, sizeof buf1, "%A, %d-%b-%y %T GMT", &tm);
608
                        parse_check(t, buf1);
609
                }
610
        }
611
612
        /* Examples from RFC2616 section 3.3.1 */
613
        tst("Sun, 06 Nov 1994 08:49:37 GMT", 784111777);
614
        tst("Sunday, 06-Nov-94 08:49:37 GMT", 784111777);
615
        tst("Sun Nov  6 08:49:37 1994", 784111777);
616
617
        tst("1994-11-06T08:49:37", 784111777);
618
619
        tst_delta();
620
621
        return (0);
622
}
623
#endif