2 * ntp_leapsec.c - leap second processing for NTPD
4 * Written by Juergen Perlinger (perlinger@ntp.org) for the NTP project.
5 * The contents of 'html/copyright.html' apply.
6 * ----------------------------------------------------------------------
7 * This is an attempt to get the leap second handling into a dedicated
8 * module to make the somewhat convoluted logic testable.
12 #include <sys/types.h>
16 #include "ntp_types.h"
18 #include "ntp_stdlib.h"
19 #include "ntp_calendar.h"
20 #include "ntp_leapsec.h"
22 #include "vint64ops.h"
23 #include "lib_strbuf.h"
27 static const char * const logPrefix = "leapsecond file";
29 /* ---------------------------------------------------------------------
30 * GCC is rather sticky with its 'const' attribute. We have to do it more
31 * explicit than with a cast if we want to get rid of a CONST qualifier.
32 * Greetings from the PASCAL world, where casting was only possible via
48 /* ---------------------------------------------------------------------
49 * Our internal data structure
51 #define MAX_HIST 10 /* history of leap seconds */
54 vint64 ttime; /* transition time (after the step, ntp scale) */
55 uint32_t stime; /* schedule limit (a month before transition) */
56 int16_t taiof; /* TAI offset on and after the transition */
57 uint8_t dynls; /* dynamic: inserted on peer/clock request */
59 typedef struct leap_info leap_info_t;
62 vint64 update; /* time of information update */
63 vint64 expire; /* table expiration time */
64 uint16_t size; /* number of infos in table */
65 int16_t base_tai; /* total leaps before first entry */
66 int16_t this_tai; /* current TAI offset */
67 int16_t next_tai; /* TAI offset after 'when' */
68 vint64 dtime; /* due time (current era end) */
69 vint64 ttime; /* nominal transition time (next era start) */
70 vint64 stime; /* schedule time (when we take notice) */
71 vint64 ebase; /* base time of this leap era */
72 uint8_t dynls; /* next leap is dynamic (by peer request) */
74 typedef struct leap_head leap_head_t;
77 leap_signature_t lsig;
79 leap_info_t info[MAX_HIST];
82 /* Where we store our tables */
83 static leap_table_t _ltab[2], *_lptr;
84 static int/*BOOL*/ _electric;
86 /* Forward decls of local helpers */
87 static int add_range(leap_table_t*, const leap_info_t*);
88 static char * get_line(leapsec_reader, void*, char*, size_t);
89 static char * skipws(const char*);
90 static int parsefail(const char * cp, const char * ep);
91 static void reload_limits(leap_table_t*, const vint64*);
92 static int betweenu32(uint32_t, uint32_t, uint32_t);
93 static void reset_times(leap_table_t*);
94 static int leapsec_add(leap_table_t*, const vint64*, int);
95 static int leapsec_raw(leap_table_t*, const vint64 *, int, int);
96 static char * lstostr(const vint64 * ts);
98 /* =====================================================================
99 * Get & Set the current leap table
102 /* ------------------------------------------------------------------ */
107 leap_table_t *p1, *p2;
110 p1 = &_ltab[p1 == &_ltab[1]];
111 p2 = &_ltab[p1 == &_ltab[0]];
113 memcpy(p2, p1, sizeof(leap_table_t));
120 /* ------------------------------------------------------------------ */
125 if (pt == &_ltab[0] || pt == &_ltab[1])
130 /* ------------------------------------------------------------------ */
139 _electric = (on != 0);
140 if (_electric == res)
143 if (_lptr == &_ltab[0] || _lptr == &_ltab[1])
149 /* =====================================================================
150 * API functions that operate on tables
153 /* ---------------------------------------------------------------------
154 * Clear all leap second data. Use it for init & cleanup
160 memset(&pt->lsig, 0, sizeof(pt->lsig));
161 memset(&pt->head, 0, sizeof(pt->head));
165 /* ---------------------------------------------------------------------
166 * Load a leap second file and check expiration on the go
175 char *cp, *ep, linebuf[50];
178 struct calendar build;
181 if (use_build_limit && ntpcal_get_build_date(&build))
182 limit = ntpcal_date_to_ntp64(&build);
184 memset(&limit, 0, sizeof(limit));
186 while (get_line(func, farg, linebuf, sizeof(linebuf))) {
192 pt->head.expire = strtouv64(cp, &ep, 10);
193 if (parsefail(cp, ep))
195 pt->lsig.etime = pt->head.expire.D_s.lo;
196 } else if (*cp == '$') {
198 pt->head.update = strtouv64(cp, &ep, 10);
199 if (parsefail(cp, ep))
202 } else if (isdigit((u_char)*cp)) {
203 ttime = strtouv64(cp, &ep, 10);
204 if (parsefail(cp, ep))
207 taiof = strtol(cp, &ep, 10);
208 if ( parsefail(cp, ep)
209 || taiof > SHRT_MAX || taiof < SHRT_MIN)
211 if (ucmpv64(&ttime, &limit) >= 0) {
212 if (!leapsec_raw(pt, &ttime,
216 pt->head.base_tai = (int16_t)taiof;
218 pt->lsig.ttime = ttime.D_s.lo;
219 pt->lsig.taiof = (int16_t)taiof;
231 /* ---------------------------------------------------------------------
232 * Dump a table in human-readable format. Use 'fprintf' and a FILE
233 * pointer if you want to get it printed into a stream.
237 const leap_table_t * pt ,
243 struct calendar atb, ttb;
245 ntpcal_ntp64_to_date(&ttb, &pt->head.expire);
246 (*func)(farg, "leap table (%u entries) expires at %04u-%02u-%02u:\n",
248 ttb.year, ttb.month, ttb.monthday);
251 ts = pt->info[idx].ttime;
252 ntpcal_ntp64_to_date(&ttb, &ts);
253 ts = subv64u32(&ts, pt->info[idx].stime);
254 ntpcal_ntp64_to_date(&atb, &ts);
256 (*func)(farg, "%04u-%02u-%02u [%c] (%04u-%02u-%02u) - %d\n",
257 ttb.year, ttb.month, ttb.monthday,
258 "-*"[pt->info[idx].dynls != 0],
259 atb.year, atb.month, atb.monthday,
260 pt->info[idx].taiof);
264 /* =====================================================================
265 * usecase driven API functions
272 const time_t * pivot)
275 vint64 ts64, last, next;
279 /* preset things we use later on... */
281 ts64 = ntpcal_ntp_to_ntp(ts32, pivot);
282 pt = leapsec_get_table(FALSE);
283 memset(qr, 0, sizeof(leap_result_t));
285 if (ucmpv64(&ts64, &pt->head.ebase) < 0) {
286 /* Most likely after leap frame reset. Could also be a
287 * backstep of the system clock. Anyway, get the new
290 reload_limits(pt, &ts64);
291 } else if (ucmpv64(&ts64, &pt->head.dtime) >= 0) {
292 /* Boundary crossed in forward direction. This might
293 * indicate a leap transition, so we prepare for that
296 * Some operations below are actually NOPs in electric
297 * mode, but having only one code path that works for
298 * both modes is easier to maintain.
300 last = pt->head.ttime;
301 qr->warped = (int16_t)(last.D_s.lo -
302 pt->head.dtime.D_s.lo);
303 next = addv64i32(&ts64, qr->warped);
304 reload_limits(pt, &next);
305 fired = ucmpv64(&pt->head.ebase, &last) == 0;
314 qr->tai_offs = pt->head.this_tai;
316 /* If before the next scheduling alert, we're done. */
317 if (ucmpv64(&ts64, &pt->head.stime) < 0)
320 /* now start to collect the remaing data */
321 due32 = pt->head.dtime.D_s.lo;
323 qr->tai_diff = pt->head.next_tai - pt->head.this_tai;
324 qr->ttime = pt->head.ttime;
325 qr->ddist = due32 - ts32;
326 qr->dynamic = pt->head.dynls;
327 qr->proximity = LSPROX_SCHEDULE;
329 /* if not in the last day before transition, we're done. */
330 if (!betweenu32(due32 - SECSPERDAY, ts32, due32))
333 qr->proximity = LSPROX_ANNOUNCE;
334 if (!betweenu32(due32 - 10, ts32, due32))
337 /* The last 10s before the transition. Prepare for action! */
338 qr->proximity = LSPROX_ALERT;
342 /* ------------------------------------------------------------------ */
347 const leap_table_t * pt;
349 memset(qr, 0, sizeof(leap_result_t));
350 pt = leapsec_get_table(FALSE);
351 if (ucmpv64(&pt->head.ttime, &pt->head.stime) <= 0)
354 qr->tai_offs = pt->head.this_tai;
355 qr->tai_diff = pt->head.next_tai - pt->head.this_tai;
356 qr->ttime = pt->head.ttime;
357 qr->dynamic = pt->head.dynls;
362 /* ------------------------------------------------------------------ */
363 /* Reset the current leap frame */
365 leapsec_reset_frame(void)
367 reset_times(leapsec_get_table(FALSE));
370 /* ------------------------------------------------------------------ */
371 /* load a file from a FILE pointer. Note: If hcheck is true, load
372 * only after successful signature check. The stream must be seekable
387 rcheck = leapsec_validate((leapsec_reader)getc, ifp);
391 case LSVALID_GOODHASH:
392 msyslog(LOG_NOTICE, "%s ('%s'): good hash signature",
397 msyslog(LOG_ERR, "%s ('%s'): no hash signature",
400 case LSVALID_BADHASH:
401 msyslog(LOG_ERR, "%s ('%s'): signature mismatch",
404 case LSVALID_BADFORMAT:
405 msyslog(LOG_ERR, "%s ('%s'): malformed hash signature",
409 msyslog(LOG_ERR, "%s ('%s'): unknown error code %d",
410 logPrefix, fname, rcheck);
417 pt = leapsec_get_table(TRUE);
418 if (!leapsec_load(pt, (leapsec_reader)getc, ifp, TRUE)) {
421 msyslog(LOG_ERR, "%s ('%s'): bad transition time",
425 msyslog(LOG_ERR, "%s ('%s'): times not ascending",
429 msyslog(LOG_ERR, "%s ('%s'): parsing error",
437 msyslog(LOG_NOTICE, "%s ('%s'): loaded, expire=%s last=%s ofs=%d",
438 logPrefix, fname, lstostr(&pt->head.expire),
439 lstostr(&pt->info[0].ttime), pt->info[0].taiof);
442 "%s ('%s'): loaded, expire=%s ofs=%d (no entries after build date)",
443 logPrefix, fname, lstostr(&pt->head.expire),
446 return leapsec_set_table(pt);
449 /* ------------------------------------------------------------------ */
453 struct stat * sb_old,
461 /* just do nothing if there is no leap file */
462 if ( !(fname && *fname) )
465 /* try to stat the leapfile */
466 if (0 != stat(fname, &sb_new)) {
468 msyslog(LOG_ERR, "%s ('%s'): stat failed: %m",
473 /* silently skip to postcheck if no new file found */
474 if (NULL != sb_old) {
476 && sb_old->st_mtime == sb_new.st_mtime
477 && sb_old->st_ctime == sb_new.st_ctime
483 /* try to open the leap file, complain if that fails
485 * [perlinger@ntp.org]
486 * coverity raises a TOCTOU (time-of-check/time-of-use) issue
487 * here, which is not entirely helpful: While there is indeed a
488 * possible race condition between the 'stat()' call above and
489 * the 'fopen)' call below, I intentionally want to omit the
490 * overhead of opening the file and calling 'fstat()', because
491 * in most cases the file would have be to closed anyway without
492 * reading the contents. I chose to disable the coverity
495 * So unless someone comes up with a reasonable argument why
496 * this could be a real issue, I'll just try to silence coverity
499 /* coverity[toctou] */
500 if ((fp = fopen(fname, "r")) == NULL) {
503 "%s ('%s'): open failed: %m",
508 rc = leapsec_load_stream(fp, fname, logall);
513 /* ------------------------------------------------------------------ */
516 leap_signature_t * psig)
518 const leap_table_t * pt;
520 pt = leapsec_get_table(FALSE);
521 memcpy(psig, &pt->lsig, sizeof(leap_signature_t));
524 /* ------------------------------------------------------------------ */
530 const leap_table_t * pt;
533 pt = leapsec_get_table(FALSE);
534 limit = ntpcal_ntp_to_ntp(when, tpiv);
535 return ucmpv64(&limit, &pt->head.expire) >= 0;
538 /* ------------------------------------------------------------------ */
544 const leap_table_t * pt;
547 pt = leapsec_get_table(FALSE);
548 limit = ntpcal_ntp_to_ntp(when, tpiv);
549 limit = subv64(&pt->head.expire, &limit);
550 return ntpcal_daysplit(&limit).hi;
553 /* ------------------------------------------------------------------ */
559 const time_t * pivot)
570 et64 = ntpcal_ntp_to_ntp(etime, pivot);
571 tt64 = ntpcal_ntp_to_ntp(ttime, pivot);
572 pt = leapsec_get_table(TRUE);
574 if ( ucmpv64(&et64, &pt->head.expire) <= 0
575 || !leapsec_raw(pt, &tt64, total, FALSE) )
578 pt->lsig.etime = etime;
579 pt->lsig.ttime = ttime;
580 pt->lsig.taiof = (int16_t)total;
582 pt->head.expire = et64;
584 return leapsec_set_table(pt);
587 /* ------------------------------------------------------------------ */
592 const time_t * pivot )
597 pt = leapsec_get_table(TRUE);
598 now64 = ntpcal_ntp_to_ntp(ntpnow, pivot);
599 return ( leapsec_add(pt, &now64, (insert != 0))
600 && leapsec_set_table(pt));
603 /* =====================================================================
607 /* [internal] Reset / init the time window in the leap processor to
608 * force reload on next query. Since a leap transition cannot take place
609 * at an odd second, the value chosen avoids spurious leap transition
610 * triggers. Making all three times equal forces a reload. Using the
611 * maximum value for unsigned 64 bits makes finding the next leap frame
618 memset(&pt->head.ebase, 0xFF, sizeof(vint64));
619 pt->head.stime = pt->head.ebase;
620 pt->head.ttime = pt->head.ebase;
621 pt->head.dtime = pt->head.ebase;
624 /* [internal] Add raw data to the table, removing old entries on the
625 * fly. This cannot fail currently.
630 const leap_info_t * pi)
632 /* If the table is full, make room by throwing out the oldest
633 * entry. But remember the accumulated leap seconds!
635 if (pt->head.size >= MAX_HIST) {
636 pt->head.size = MAX_HIST - 1;
637 pt->head.base_tai = pt->info[pt->head.size].taiof;
640 /* make room in lower end and insert item */
641 memmove(pt->info+1, pt->info, pt->head.size*sizeof(*pt->info));
645 /* invalidate the cached limit data -- we might have news ;-)
647 * This blocks a spurious transition detection. OTOH, if you add
648 * a value after the last query before a leap transition was
649 * expected to occur, this transition trigger is lost. But we
650 * can probably live with that.
656 /* [internal] given a reader function, read characters into a buffer
657 * until either EOL or EOF is reached. Makes sure that the buffer is
658 * always NUL terminated, but silently truncates excessive data. The
659 * EOL-marker ('\n') is *not* stored in the buffer.
661 * Returns the pointer to the buffer, unless EOF was reached when trying
662 * to read the first character of a line.
674 /* if we cannot even store the delimiter, declare failure */
675 if (buff == NULL || size == 0)
679 while (EOF != (ch = (*func)(farg)) && '\n' != ch)
684 /* discard trailing whitespace */
685 while (ptr != buff && isspace((u_char)ptr[-1]))
688 return (ptr == buff && ch == EOF) ? NULL : buff;
691 /* [internal] skips whitespace characters from a character buffer. */
696 while (isspace((u_char)*ptr))
698 return (char*)noconst(ptr);
701 /* [internal] check if a strtoXYZ ended at EOL or whistespace and
702 * converted something at all. Return TRUE if something went wrong.
710 || (*ep && *ep != '#' && !isspace((u_char)*ep));
713 /* [internal] reload the table limits around the given time stamp. This
714 * is where the real work is done when it comes to table lookup and
715 * evaluation. Some care has been taken to have correct code for dealing
716 * with boundary conditions and empty tables.
718 * In electric mode, transition and trip time are the same. In dumb
719 * mode, the difference of the TAI offsets must be taken into account
720 * and trip time and transition time become different. The difference
721 * becomes the warping distance when the trip time is reached.
730 /* Get full time and search the true lower bound. Use a
731 * simple loop here, since the number of entries does
732 * not warrant a binary search. This also works for an empty
733 * table, so there is no shortcut for that case.
735 for (idx = 0; idx != pt->head.size; idx++)
736 if (ucmpv64(ts, &pt->info[idx].ttime) >= 0)
739 /* get time limits with proper bound conditions. Note that the
740 * bounds of the table will be observed even if the table is
741 * empty -- no undefined condition must arise from this code.
743 if (idx >= pt->head.size) {
744 memset(&pt->head.ebase, 0x00, sizeof(vint64));
745 pt->head.this_tai = pt->head.base_tai;
747 pt->head.ebase = pt->info[idx].ttime;
748 pt->head.this_tai = pt->info[idx].taiof;
751 pt->head.next_tai = pt->info[idx].taiof;
752 pt->head.dynls = pt->info[idx].dynls;
753 pt->head.ttime = pt->info[idx].ttime;
756 pt->head.dtime = pt->head.ttime;
758 pt->head.dtime = addv64i32(
760 pt->head.next_tai - pt->head.this_tai);
762 pt->head.stime = subv64u32(
763 &pt->head.ttime, pt->info[idx].stime);
766 memset(&pt->head.ttime, 0xFF, sizeof(vint64));
767 pt->head.stime = pt->head.ttime;
768 pt->head.dtime = pt->head.ttime;
769 pt->head.next_tai = pt->head.this_tai;
774 /* [internal] Take a time stamp and create a leap second frame for
775 * it. This will schedule a leap second for the beginning of the next
776 * month, midnight UTC. The 'insert' argument tells if a leap second is
777 * added (!=0) or removed (==0). We do not handle multiple inserts
780 * Returns 1 if the insert worked, 0 otherwise. (It's not possible to
781 * insert a leap second into the current history -- only appending
782 * towards the future is allowed!)
787 const vint64 * now64 ,
790 vint64 ttime, starttime;
794 /* Check against the table expiration and the lates available
795 * leap entry. Do not permit inserts, only appends, and only if
796 * the extend the table beyond the expiration!
798 if ( ucmpv64(now64, &pt->head.expire) < 0
799 || (pt->head.size && ucmpv64(now64, &pt->info[0].ttime) <= 0)) {
804 ntpcal_ntp64_to_date(&fts, now64);
805 /* To guard against dangling leap flags: do not accept leap
806 * second request on the 1st hour of the 1st day of the month.
808 if (fts.monthday == 1 && fts.hour == 0) {
813 /* Ok, do the remaining calculations */
818 starttime = ntpcal_date_to_ntp64(&fts);
820 ttime = ntpcal_date_to_ntp64(&fts);
823 li.stime = ttime.D_s.lo - starttime.D_s.lo;
824 li.taiof = (pt->head.size ? pt->info[0].taiof : pt->head.base_tai)
827 return add_range(pt, &li);
830 /* [internal] Given a time stamp for a leap insertion (the exact begin
831 * of the new leap era), create new leap frame and put it into the
832 * table. This is the work horse for reading a leap file and getting a
833 * leap second update via authenticated network packet.
838 const vint64 * ttime,
846 /* Check that we only extend the table. Paranoia rulez! */
847 if (pt->head.size && ucmpv64(ttime, &pt->info[0].ttime) <= 0) {
852 ntpcal_ntp64_to_date(&fts, ttime);
853 /* If this does not match the exact month start, bail out. */
854 if (fts.monthday != 1 || fts.hour || fts.minute || fts.second) {
858 fts.month--; /* was in range 1..12, no overflow here! */
859 starttime = ntpcal_date_to_ntp64(&fts);
861 li.stime = ttime->D_s.lo - starttime.D_s.lo;
862 li.taiof = (int16_t)taiof;
863 li.dynls = (dynls != 0);
864 return add_range(pt, &li);
867 /* [internal] Do a wrap-around save range inclusion check.
868 * Returns TRUE if x in [lo,hi[ (intervall open on right side) with full
869 * handling of an overflow / wrap-around.
880 rc = (lo <= x) && (x < hi);
882 rc = (lo <= x) || (x < hi);
886 /* =====================================================================
891 unsigned char hv[ISC_SHA1_DIGESTLENGTH];
894 /* [internal] parse a digest line to get the hash signature
895 * The NIST code creating the hash writes them out as 5 hex integers
896 * without leading zeros. This makes reading them back as hex-encoded
897 * BLOB impossible, because there might be less than 40 hex digits.
899 * The solution is to read the values back as integers, and then do the
900 * byte twiddle necessary to get it into an array of 20 chars. The
901 * drawback is that it permits any acceptable number syntax provided by
902 * 'scanf()' and 'strtoul()', including optional signs and '0x'
910 int wi, di, num, len;
911 unsigned long tmp[5];
913 memset(mac, 0, sizeof(*mac));
914 num = sscanf(cp, " %lx %lx %lx %lx %lx%n",
915 &tmp[0], &tmp[1], &tmp[2], &tmp[3], &tmp[4],
917 if (num != 5 || cp[len] > ' ')
920 /* now do the byte twiddle */
921 for (wi=0; wi < 5; ++wi)
922 for (di=3; di >= 0; --di) {
924 (unsigned char)(tmp[wi] & 0x0FF);
930 /* [internal] add the digits of a data line to the hash, stopping at the
931 * next hash ('#') character.
938 unsigned char text[32]; // must be power of two!
939 unsigned int tlen = 0;
942 while ('\0' != (ch = *cp++) && '#' != ch)
945 tlen &= (sizeof(text)-1);
948 mdctx, text, sizeof(text));
952 isc_sha1_update(mdctx, text, tlen);
955 /* given a reader and a reader arg, calculate and validate the the hash
956 * signature of a NIST leap second file.
964 sha1_digest rdig, ldig; /* remote / local digests */
968 isc_sha1_init(&mdctx);
969 while (get_line(func, farg, line, sizeof(line))) {
970 if (!strncmp(line, "#h", 2))
971 hlseen = do_leap_hash(&rdig, line+2);
972 else if (!strncmp(line, "#@", 2))
973 do_hash_data(&mdctx, line+2);
974 else if (!strncmp(line, "#$", 2))
975 do_hash_data(&mdctx, line+2);
976 else if (isdigit((unsigned char)line[0]))
977 do_hash_data(&mdctx, line);
979 isc_sha1_final(&mdctx, ldig.hv);
980 isc_sha1_invalidate(&mdctx);
983 return LSVALID_NOHASH;
985 return LSVALID_BADFORMAT;
986 if (0 != memcmp(&rdig, &ldig, sizeof(sha1_digest)))
987 return LSVALID_BADHASH;
988 return LSVALID_GOODHASH;
992 * lstostr - prettyprint NTP seconds
994 static char * lstostr(
1001 ntpcal_ntp64_to_date(&tm, ts);
1002 snprintf(buf, LIB_BUFLENGTH, "%04d-%02d-%02dT%02d:%02dZ",
1003 tm.year, tm.month, tm.monthday,
1004 tm.hour, tm.minute);
1010 /* -*- that's all folks! -*- */