time/mktime.c

   1 /* Convert a 'struct tm' to a time_t value.
   2    Copyright (C) 1993-2021 Free Software Foundation, Inc.
   3    This file is part of the GNU C Library.
   4    Contributed by Paul Eggert <eggert@twinsun.com>.
   5
   6    The GNU C Library is free software; you can redistribute it and/or
   7    modify it under the terms of the GNU Lesser General Public
   8    License as published by the Free Software Foundation; either
   9    version 2.1 of the License, or (at your option) any later version.
  10
  11    The GNU C Library is distributed in the hope that it will be useful,
  12    but WITHOUT ANY WARRANTY; without even the implied warranty of
  13    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14    Lesser General Public License for more details.
  15
  16    You should have received a copy of the GNU Lesser General Public
  17    License along with the GNU C Library; if not, see
  18    <https://www.gnu.org/licenses/>.  */
  19
  20 /* The following macros influence what gets defined when this file is compiled:
  21
  22    Macro/expression            Which gnulib module    This compilation unit
  23                                                       should define
  24
  25    _LIBC                       (glibc proper)         mktime
  26
  27    NEED_MKTIME_WORKING         mktime                 rpl_mktime
  28    || NEED_MKTIME_WINDOWS
  29
  30    NEED_MKTIME_INTERNAL        mktime-internal        mktime_internal
  31  */
  32
  33 #ifndef _LIBC
  34 # include <libc-config.h>
  35 #endif
  36
  37 /* Assume that leap seconds are possible, unless told otherwise.
  38    If the host has a 'zic' command with a '-L leapsecondfilename' option,
  39    then it supports leap seconds; otherwise it probably doesn't.  */
  40 #ifndef LEAP_SECONDS_POSSIBLE
  41 # define LEAP_SECONDS_POSSIBLE 1
  42 #endif
  43
  44 #include <time.h>
  45
  46 #include <errno.h>
  47 #include <limits.h>
  48 #include <stdbool.h>
  49 #include <stdlib.h>
  50 #include <string.h>
  51
  52 #include <intprops.h>
  53 #include <verify.h>
  54
  55 #ifndef NEED_MKTIME_INTERNAL
  56 # define NEED_MKTIME_INTERNAL 0
  57 #endif
  58 #ifndef NEED_MKTIME_WINDOWS
  59 # define NEED_MKTIME_WINDOWS 0
  60 #endif
  61 #ifndef NEED_MKTIME_WORKING
  62 # define NEED_MKTIME_WORKING 0
  63 #endif
  64
  65 #include "mktime-internal.h"
  66
  67 #if !defined _LIBC && (NEED_MKTIME_WORKING || NEED_MKTIME_WINDOWS)
  68 static void
  69 my_tzset (void)
  70 {
  71 # if NEED_MKTIME_WINDOWS
  72   /* Rectify the value of the environment variable TZ.
  73      There are four possible kinds of such values:
  74        - Traditional US time zone names, e.g. "PST8PDT".  Syntax: see
  75          <https://docs.microsoft.com/en-us/cpp/c-runtime-library/reference/tzset>
  76        - Time zone names based on geography, that contain one or more
  77          slashes, e.g. "Europe/Moscow".
  78        - Time zone names based on geography, without slashes, e.g.
  79          "Singapore".
  80        - Time zone names that contain explicit DST rules.  Syntax: see
  81          <https://pubs.opengroup.org/onlinepubs/9699919799/basedefs/V1_chap08.html#tag_08_03>
  82      The Microsoft CRT understands only the first kind.  It produces incorrect
  83      results if the value of TZ is of the other kinds.
  84      But in a Cygwin environment, /etc/profile.d/tzset.sh sets TZ to a value
  85      of the second kind for most geographies, or of the first kind in a few
  86      other geographies.  If it is of the second kind, neutralize it.  For the
  87      Microsoft CRT, an absent or empty TZ means the time zone that the user
  88      has set in the Windows Control Panel.
  89      If the value of TZ is of the third or fourth kind -- Cygwin programs
  90      understand these syntaxes as well --, it does not matter whether we
  91      neutralize it or not, since these values occur only when a Cygwin user
  92      has set TZ explicitly; this case is 1. rare and 2. under the user's
  93      responsibility.  */
  94   const char *tz = getenv ("TZ");
  95   if (tz != NULL && strchr (tz, '/') != NULL)
  96     _putenv ("TZ=");
  97 # elif HAVE_TZSET
  98   tzset ();
  99 # endif
 100 }
 101 # undef __tzset
 102 # define __tzset() my_tzset ()
 103 #endif
 104
 105 #if defined _LIBC || NEED_MKTIME_WORKING || NEED_MKTIME_INTERNAL
 106
 107 /* A signed type that can represent an integer number of years
 108    multiplied by four times the number of seconds in a year.  It is
 109    needed when converting a tm_year value times the number of seconds
 110    in a year.  The factor of four comes because these products need
 111    to be subtracted from each other, and sometimes with an offset
 112    added to them, and then with another timestamp added, without
 113    worrying about overflow.
 114
 115    Much of the code uses long_int to represent __time64_t values, to
 116    lessen the hassle of dealing with platforms where __time64_t is
 117    unsigned, and because long_int should suffice to represent all
 118    __time64_t values that mktime can generate even on platforms where
 119    __time64_t is wider than the int components of struct tm.  */
 120
 121 #if INT_MAX <= LONG_MAX / 4 / 366 / 24 / 60 / 60
 122 typedef long int long_int;
 123 #else
 124 typedef long long int long_int;
 125 #endif
 126 verify (INT_MAX <= TYPE_MAXIMUM (long_int) / 4 / 366 / 24 / 60 / 60);
 127
 128 /* Shift A right by B bits portably, by dividing A by 2**B and
 129    truncating towards minus infinity.  B should be in the range 0 <= B
 130    <= LONG_INT_BITS - 2, where LONG_INT_BITS is the number of useful
 131    bits in a long_int.  LONG_INT_BITS is at least 32.
 132
 133    ISO C99 says that A >> B is implementation-defined if A < 0.  Some
 134    implementations (e.g., UNICOS 9.0 on a Cray Y-MP EL) don't shift
 135    right in the usual way when A < 0, so SHR falls back on division if
 136    ordinary A >> B doesn't seem to be the usual signed shift.  */
 137
 138 static long_int
 139 shr (long_int a, int b)
 140 {
 141   long_int one = 1;
 142   return (-one >> 1 == -1
 143           ? a >> b
 144           : (a + (a < 0)) / (one << b) - (a < 0));
 145 }
 146
 147 /* Bounds for the intersection of __time64_t and long_int.  */
 148
 149 static long_int const mktime_min
 150   = ((TYPE_SIGNED (__time64_t)
 151       && TYPE_MINIMUM (__time64_t) < TYPE_MINIMUM (long_int))
 152      ? TYPE_MINIMUM (long_int) : TYPE_MINIMUM (__time64_t));
 153 static long_int const mktime_max
 154   = (TYPE_MAXIMUM (long_int) < TYPE_MAXIMUM (__time64_t)
 155      ? TYPE_MAXIMUM (long_int) : TYPE_MAXIMUM (__time64_t));
 156
 157 #define EPOCH_YEAR 1970
 158 #define TM_YEAR_BASE 1900
 159 verify (TM_YEAR_BASE % 100 == 0);
 160
 161 /* Is YEAR + TM_YEAR_BASE a leap year?  */
 162 static bool
 163 leapyear (long_int year)
 164 {
 165   /* Don't add YEAR to TM_YEAR_BASE, as that might overflow.
 166      Also, work even if YEAR is negative.  */
 167   return
 168     ((year & 3) == 0
 169      && (year % 100 != 0
 170          || ((year / 100) & 3) == (- (TM_YEAR_BASE / 100) & 3)));
 171 }
 172
 173 /* How many days come before each month (0-12).  */
 174 #ifndef _LIBC
 175 static
 176 #endif
 177 const unsigned short int __mon_yday[2][13] =
 178   {
 179     /* Normal years.  */
 180     { 0, 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334, 365 },
 181     /* Leap years.  */
 182     { 0, 31, 60, 91, 121, 152, 182, 213, 244, 274, 305, 335, 366 }
 183   };
 184
 185
 186 /* Do the values A and B differ according to the rules for tm_isdst?
 187    A and B differ if one is zero and the other positive.  */
 188 static bool
 189 isdst_differ (int a, int b)
 190 {
 191   return (!a != !b) && (0 <= a) && (0 <= b);
 192 }
 193
 194 /* Return an integer value measuring (YEAR1-YDAY1 HOUR1:MIN1:SEC1) -
 195    (YEAR0-YDAY0 HOUR0:MIN0:SEC0) in seconds, assuming that the clocks
 196    were not adjusted between the timestamps.
 197
 198    The YEAR values uses the same numbering as TP->tm_year.  Values
 199    need not be in the usual range.  However, YEAR1 - YEAR0 must not
 200    overflow even when multiplied by three times the number of seconds
 201    in a year, and likewise for YDAY1 - YDAY0 and three times the
 202    number of seconds in a day.  */
 203
 204 static long_int
 205 ydhms_diff (long_int year1, long_int yday1, int hour1, int min1, int sec1,
 206             int year0, int yday0, int hour0, int min0, int sec0)
 207 {
 208   verify (-1 / 2 == 0);
 209
 210   /* Compute intervening leap days correctly even if year is negative.
 211      Take care to avoid integer overflow here.  */
 212   int a4 = shr (year1, 2) + shr (TM_YEAR_BASE, 2) - ! (year1 & 3);
 213   int b4 = shr (year0, 2) + shr (TM_YEAR_BASE, 2) - ! (year0 & 3);
 214   int a100 = (a4 + (a4 < 0)) / 25 - (a4 < 0);
 215   int b100 = (b4 + (b4 < 0)) / 25 - (b4 < 0);
 216   int a400 = shr (a100, 2);
 217   int b400 = shr (b100, 2);
 218   int intervening_leap_days = (a4 - b4) - (a100 - b100) + (a400 - b400);
 219
 220   /* Compute the desired time without overflowing.  */
 221   long_int years = year1 - year0;
 222   long_int days = 365 * years + yday1 - yday0 + intervening_leap_days;
 223   long_int hours = 24 * days + hour1 - hour0;
 224   long_int minutes = 60 * hours + min1 - min0;
 225   long_int seconds = 60 * minutes + sec1 - sec0;
 226   return seconds;
 227 }
 228
 229 /* Return the average of A and B, even if A + B would overflow.
 230    Round toward positive infinity.  */
 231 static long_int
 232 long_int_avg (long_int a, long_int b)
 233 {
 234   return shr (a, 1) + shr (b, 1) + ((a | b) & 1);
 235 }
 236
 237 /* Return a long_int value corresponding to (YEAR-YDAY HOUR:MIN:SEC)
 238    minus *TP seconds, assuming no clock adjustments occurred between
 239    the two timestamps.
 240
 241    YEAR and YDAY must not be so large that multiplying them by three times the
 242    number of seconds in a year (or day, respectively) would overflow long_int.
 243    *TP should be in the usual range.  */
 244 static long_int
 245 tm_diff (long_int year, long_int yday, int hour, int min, int sec,
 246          struct tm const *tp)
 247 {
 248   return ydhms_diff (year, yday, hour, min, sec,
 249                      tp->tm_year, tp->tm_yday,
 250                      tp->tm_hour, tp->tm_min, tp->tm_sec);
 251 }
 252
 253 /* Use CONVERT to convert T to a struct tm value in *TM.  T must be in
 254    range for __time64_t.  Return TM if successful, NULL (setting errno) on
 255    failure.  */
 256 static struct tm *
 257 convert_time (struct tm *(*convert) (const __time64_t *, struct tm *),
 258               long_int t, struct tm *tm)
 259 {
 260   __time64_t x = t;
 261   return convert (&x, tm);
 262 }
 263
 264 /* Use CONVERT to convert *T to a broken down time in *TP.
 265    If *T is out of range for conversion, adjust it so that
 266    it is the nearest in-range value and then convert that.
 267    A value is in range if it fits in both __time64_t and long_int.
 268    Return TP on success, NULL (setting errno) on failure.  */
 269 static struct tm *
 270 ranged_convert (struct tm *(*convert) (const __time64_t *, struct tm *),
 271                 long_int *t, struct tm *tp)
 272 {
 273   long_int t1 = (*t < mktime_min ? mktime_min
 274                  : *t <= mktime_max ? *t : mktime_max);
 275   struct tm *r = convert_time (convert, t1, tp);
 276   if (r)
 277     {
 278       *t = t1;
 279       return r;
 280     }
 281   if (errno != EOVERFLOW)
 282     return NULL;
 283
 284   long_int bad = t1;
 285   long_int ok = 0;
 286   struct tm oktm; oktm.tm_sec = -1;
 287
 288   /* BAD is a known out-of-range value, and OK is a known in-range one.
 289      Use binary search to narrow the range between BAD and OK until
 290      they differ by 1.  */
 291   while (true)
 292     {
 293       long_int mid = long_int_avg (ok, bad);
 294       if (mid == ok || mid == bad)
 295         break;
 296       if (convert_time (convert, mid, tp))
 297         ok = mid, oktm = *tp;
 298       else if (errno != EOVERFLOW)
 299         return NULL;
 300       else
 301         bad = mid;
 302     }
 303
 304   if (oktm.tm_sec < 0)
 305     return NULL;
 306   *t = ok;
 307   *tp = oktm;
 308   return tp;
 309 }
 310
 311
 312 /* Convert *TP to a __time64_t value, inverting
 313    the monotonic and mostly-unit-linear conversion function CONVERT.
 314    Use *OFFSET to keep track of a guess at the offset of the result,
 315    compared to what the result would be for UTC without leap seconds.
 316    If *OFFSET's guess is correct, only one CONVERT call is needed.
 317    If successful, set *TP to the canonicalized struct tm;
 318    otherwise leave *TP alone, return ((time_t) -1) and set errno.
 319    This function is external because it is used also by timegm.c.  */
 320 __time64_t
 321 __mktime_internal (struct tm *tp,
 322                    struct tm *(*convert) (const __time64_t *, struct tm *),
 323                    mktime_offset_t *offset)
 324 {
 325   struct tm tm;
 326
 327   /* The maximum number of probes (calls to CONVERT) should be enough
 328      to handle any combinations of time zone rule changes, solar time,
 329      leap seconds, and oscillations around a spring-forward gap.
 330      POSIX.1 prohibits leap seconds, but some hosts have them anyway.  */
 331   int remaining_probes = 6;
 332
 333   /* Time requested.  Copy it in case CONVERT modifies *TP; this can
 334      occur if TP is localtime's returned value and CONVERT is localtime.  */
 335   int sec = tp->tm_sec;
 336   int min = tp->tm_min;
 337   int hour = tp->tm_hour;
 338   int mday = tp->tm_mday;
 339   int mon = tp->tm_mon;
 340   int year_requested = tp->tm_year;
 341   int isdst = tp->tm_isdst;
 342
 343   /* 1 if the previous probe was DST.  */
 344   int dst2 = 0;
 345
 346   /* Ensure that mon is in range, and set year accordingly.  */
 347   int mon_remainder = mon % 12;
 348   int negative_mon_remainder = mon_remainder < 0;
 349   int mon_years = mon / 12 - negative_mon_remainder;
 350   long_int lyear_requested = year_requested;
 351   long_int year = lyear_requested + mon_years;
 352
 353   /* The other values need not be in range:
 354      the remaining code handles overflows correctly.  */
 355
 356   /* Calculate day of year from year, month, and day of month.
 357      The result need not be in range.  */
 358   int mon_yday = ((__mon_yday[leapyear (year)]
 359                    [mon_remainder + 12 * negative_mon_remainder])
 360                   - 1);
 361   long_int lmday = mday;
 362   long_int yday = mon_yday + lmday;
 363
 364   mktime_offset_t off = *offset;
 365   int negative_offset_guess;
 366
 367   int sec_requested = sec;
 368
 369   if (LEAP_SECONDS_POSSIBLE)
 370     {
 371       /* Handle out-of-range seconds specially,
 372          since ydhms_diff assumes every minute has 60 seconds.  */
 373       if (sec < 0)
 374         sec = 0;
 375       if (59 < sec)
 376         sec = 59;
 377     }
 378
 379   /* Invert CONVERT by probing.  First assume the same offset as last
 380      time.  */
 381
 382   INT_SUBTRACT_WRAPV (0, off, &negative_offset_guess);
 383   long_int t0 = ydhms_diff (year, yday, hour, min, sec,
 384                             EPOCH_YEAR - TM_YEAR_BASE, 0, 0, 0,
 385                             negative_offset_guess);
 386   long_int t = t0, t1 = t0, t2 = t0;
 387
 388   /* Repeatedly use the error to improve the guess.  */
 389
 390   while (true)
 391     {
 392       if (! ranged_convert (convert, &t, &tm))
 393         return -1;
 394       long_int dt = tm_diff (year, yday, hour, min, sec, &tm);
 395       if (dt == 0)
 396         break;
 397
 398       if (t == t1 && t != t2
 399           && (tm.tm_isdst < 0
 400               || (isdst < 0
 401                   ? dst2 <= (tm.tm_isdst != 0)
 402                   : (isdst != 0) != (tm.tm_isdst != 0))))
 403         /* We can't possibly find a match, as we are oscillating
 404            between two values.  The requested time probably falls
 405            within a spring-forward gap of size DT.  Follow the common
 406            practice in this case, which is to return a time that is DT
 407            away from the requested time, preferring a time whose
 408            tm_isdst differs from the requested value.  (If no tm_isdst
 409            was requested and only one of the two values has a nonzero
 410            tm_isdst, prefer that value.)  In practice, this is more
 411            useful than returning -1.  */
 412         goto offset_found;
 413
 414       remaining_probes--;
 415       if (remaining_probes == 0)
 416         {
 417           __set_errno (EOVERFLOW);
 418           return -1;
 419         }
 420
 421       t1 = t2, t2 = t, t += dt, dst2 = tm.tm_isdst != 0;
 422     }
 423
 424   /* We have a match.  Check whether tm.tm_isdst has the requested
 425      value, if any.  */
 426   if (isdst_differ (isdst, tm.tm_isdst))
 427     {
 428       /* tm.tm_isdst has the wrong value.  Look for a neighboring
 429          time with the right value, and use its UTC offset.
 430
 431          Heuristic: probe the adjacent timestamps in both directions,
 432          looking for the desired isdst.  This should work for all real
 433          time zone histories in the tz database.  */
 434
 435       /* Distance between probes when looking for a DST boundary.  In
 436          tzdata2003a, the shortest period of DST is 601200 seconds
 437          (e.g., America/Recife starting 2000-10-08 01:00), and the
 438          shortest period of non-DST surrounded by DST is 694800
 439          seconds (Africa/Tunis starting 1943-04-17 01:00).  Use the
 440          minimum of these two values, so we don't miss these short
 441          periods when probing.  */
 442       int stride = 601200;
 443
 444       /* The longest period of DST in tzdata2003a is 536454000 seconds
 445          (e.g., America/Jujuy starting 1946-10-01 01:00).  The longest
 446          period of non-DST is much longer, but it makes no real sense
 447          to search for more than a year of non-DST, so use the DST
 448          max.  */
 449       int duration_max = 536454000;
 450
 451       /* Search in both directions, so the maximum distance is half
 452          the duration; add the stride to avoid off-by-1 problems.  */
 453       int delta_bound = duration_max / 2 + stride;
 454
 455       int delta, direction;
 456
 457       for (delta = stride; delta < delta_bound; delta += stride)
 458         for (direction = -1; direction <= 1; direction += 2)
 459           {
 460             long_int ot;
 461             if (! INT_ADD_WRAPV (t, delta * direction, &ot))
 462               {
 463                 struct tm otm;
 464                 if (! ranged_convert (convert, &ot, &otm))
 465                   return -1;
 466                 if (! isdst_differ (isdst, otm.tm_isdst))
 467                   {
 468                     /* We found the desired tm_isdst.
 469                        Extrapolate back to the desired time.  */
 470                     long_int gt = ot + tm_diff (year, yday, hour, min, sec,
 471                                                 &otm);
 472                     if (mktime_min <= gt && gt <= mktime_max)
 473                       {
 474                         if (convert_time (convert, gt, &tm))
 475                           {
 476                             t = gt;
 477                             goto offset_found;
 478                           }
 479                         if (errno != EOVERFLOW)
 480                           return -1;
 481                       }
 482                   }
 483               }
 484           }
 485
 486       __set_errno (EOVERFLOW);
 487       return -1;
 488     }
 489
 490  offset_found:
 491   /* Set *OFFSET to the low-order bits of T - T0 - NEGATIVE_OFFSET_GUESS.
 492      This is just a heuristic to speed up the next mktime call, and
 493      correctness is unaffected if integer overflow occurs here.  */
 494   INT_SUBTRACT_WRAPV (t, t0, offset);
 495   INT_SUBTRACT_WRAPV (*offset, negative_offset_guess, offset);
 496
 497   if (LEAP_SECONDS_POSSIBLE && sec_requested != tm.tm_sec)
 498     {
 499       /* Adjust time to reflect the tm_sec requested, not the normalized value.
 500          Also, repair any damage from a false match due to a leap second.  */
 501       long_int sec_adjustment = sec == 0 && tm.tm_sec == 60;
 502       sec_adjustment -= sec;
 503       sec_adjustment += sec_requested;
 504       if (INT_ADD_WRAPV (t, sec_adjustment, &t)
 505           || ! (mktime_min <= t && t <= mktime_max))
 506         {
 507           __set_errno (EOVERFLOW);
 508           return -1;
 509         }
 510       if (! convert_time (convert, t, &tm))
 511         return -1;
 512     }
 513
 514   *tp = tm;
 515   return t;
 516 }
 517
 518 #endif /* _LIBC || NEED_MKTIME_WORKING || NEED_MKTIME_INTERNAL */
 519
 520 #if defined _LIBC || NEED_MKTIME_WORKING || NEED_MKTIME_WINDOWS
 521
 522 /* Convert *TP to a __time64_t value.  */
 523 __time64_t
 524 __mktime64 (struct tm *tp)
 525 {
 526   /* POSIX.1 8.1.1 requires that whenever mktime() is called, the
 527      time zone names contained in the external variable 'tzname' shall
 528      be set as if the tzset() function had been called.  */
 529   __tzset ();
 530
 531 # if defined _LIBC || NEED_MKTIME_WORKING
 532   static mktime_offset_t localtime_offset;
 533   return __mktime_internal (tp, __localtime64_r, &localtime_offset);
 534 # else
 535 #  undef mktime
 536   return mktime (tp);
 537 # endif
 538 }
 539 #endif /* _LIBC || NEED_MKTIME_WORKING || NEED_MKTIME_WINDOWS */
 540
 541 #if defined _LIBC && __TIMESIZE != 64
 542
 543 libc_hidden_def (__mktime64)
 544
 545 time_t
 546 mktime (struct tm *tp)
 547 {
 548   struct tm tm = *tp;
 549   __time64_t t = __mktime64 (&tm);
 550   if (in_time_t_range (t))
 551     {
 552       *tp = tm;
 553       return t;
 554     }
 555   else
 556     {
 557       __set_errno (EOVERFLOW);
 558       return -1;
 559     }
 560 }
 561
 562 #endif
 563
 564 weak_alias (mktime, timelocal)
 565 libc_hidden_def (mktime)
 566 libc_hidden_weak (timelocal)