time/mktime.c

   1 /* Convert a 'struct tm' to a time_t value.
   2    Copyright (C) 1993-2024 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 # else
  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.  If none is found within a
 433          reasonable duration bound, assume a one-hour DST difference.
 434          This should work for all real time zone histories in the tz
 435          database.  */
 436
 437       /* +1 if we wanted standard time but got DST, -1 if the reverse.  */
 438       int dst_difference = (isdst == 0) - (tm.tm_isdst == 0);
 439
 440       /* Distance between probes when looking for a DST boundary.  In
 441          tzdata2003a, the shortest period of DST is 601200 seconds
 442          (e.g., America/Recife starting 2000-10-08 01:00), and the
 443          shortest period of non-DST surrounded by DST is 694800
 444          seconds (Africa/Tunis starting 1943-04-17 01:00).  Use the
 445          minimum of these two values, so we don't miss these short
 446          periods when probing.  */
 447       int stride = 601200;
 448
 449       /* In TZDB 2021e, the longest period of DST (or of non-DST), in
 450          which the DST (or adjacent DST) difference is not one hour,
 451          is 457243209 seconds: e.g., America/Cambridge_Bay with leap
 452          seconds, starting 1965-10-31 00:00 in a switch from
 453          double-daylight time (-05) to standard time (-07), and
 454          continuing to 1980-04-27 02:00 in a switch from standard time
 455          (-07) to daylight time (-06).  */
 456       int duration_max = 457243209;
 457
 458       /* Search in both directions, so the maximum distance is half
 459          the duration; add the stride to avoid off-by-1 problems.  */
 460       int delta_bound = duration_max / 2 + stride;
 461
 462       int delta, direction;
 463
 464       for (delta = stride; delta < delta_bound; delta += stride)
 465         for (direction = -1; direction <= 1; direction += 2)
 466           {
 467             long_int ot;
 468             if (! INT_ADD_WRAPV (t, delta * direction, &ot))
 469               {
 470                 struct tm otm;
 471                 if (! ranged_convert (convert, &ot, &otm))
 472                   return -1;
 473                 if (! isdst_differ (isdst, otm.tm_isdst))
 474                   {
 475                     /* We found the desired tm_isdst.
 476                        Extrapolate back to the desired time.  */
 477                     long_int gt = ot + tm_diff (year, yday, hour, min, sec,
 478                                                 &otm);
 479                     if (mktime_min <= gt && gt <= mktime_max)
 480                       {
 481                         if (convert_time (convert, gt, &tm))
 482                           {
 483                             t = gt;
 484                             goto offset_found;
 485                           }
 486                         if (errno != EOVERFLOW)
 487                           return -1;
 488                       }
 489                   }
 490               }
 491           }
 492
 493       /* No unusual DST offset was found nearby.  Assume one-hour DST.  */
 494       t += 60 * 60 * dst_difference;
 495       if (mktime_min <= t && t <= mktime_max && convert_time (convert, t, &tm))
 496         goto offset_found;
 497
 498       __set_errno (EOVERFLOW);
 499       return -1;
 500     }
 501
 502  offset_found:
 503   /* Set *OFFSET to the low-order bits of T - T0 - NEGATIVE_OFFSET_GUESS.
 504      This is just a heuristic to speed up the next mktime call, and
 505      correctness is unaffected if integer overflow occurs here.  */
 506   INT_SUBTRACT_WRAPV (t, t0, offset);
 507   INT_SUBTRACT_WRAPV (*offset, negative_offset_guess, offset);
 508
 509   if (LEAP_SECONDS_POSSIBLE && sec_requested != tm.tm_sec)
 510     {
 511       /* Adjust time to reflect the tm_sec requested, not the normalized value.
 512          Also, repair any damage from a false match due to a leap second.  */
 513       long_int sec_adjustment = sec == 0 && tm.tm_sec == 60;
 514       sec_adjustment -= sec;
 515       sec_adjustment += sec_requested;
 516       if (INT_ADD_WRAPV (t, sec_adjustment, &t)
 517           || ! (mktime_min <= t && t <= mktime_max))
 518         {
 519           __set_errno (EOVERFLOW);
 520           return -1;
 521         }
 522       if (! convert_time (convert, t, &tm))
 523         return -1;
 524     }
 525
 526   *tp = tm;
 527   return t;
 528 }
 529
 530 #endif /* _LIBC || NEED_MKTIME_WORKING || NEED_MKTIME_INTERNAL */
 531
 532 #if defined _LIBC || NEED_MKTIME_WORKING || NEED_MKTIME_WINDOWS
 533
 534 /* Convert *TP to a __time64_t value.  */
 535 __time64_t
 536 __mktime64 (struct tm *tp)
 537 {
 538   /* POSIX.1 8.1.1 requires that whenever mktime() is called, the
 539      time zone abbreviations contained in the external variable 'tzname' shall
 540      be set as if the tzset() function had been called.  */
 541   __tzset ();
 542
 543 # if defined _LIBC || NEED_MKTIME_WORKING
 544   static mktime_offset_t localtime_offset;
 545   return __mktime_internal (tp, __localtime64_r, &localtime_offset);
 546 # else
 547 #  undef mktime
 548   return mktime (tp);
 549 # endif
 550 }
 551 #endif /* _LIBC || NEED_MKTIME_WORKING || NEED_MKTIME_WINDOWS */
 552
 553 #if defined _LIBC && __TIMESIZE != 64
 554
 555 libc_hidden_def (__mktime64)
 556
 557 time_t
 558 mktime (struct tm *tp)
 559 {
 560   struct tm tm = *tp;
 561   __time64_t t = __mktime64 (&tm);
 562   if (in_time_t_range (t))
 563     {
 564       *tp = tm;
 565       return t;
 566     }
 567   else
 568     {
 569       __set_errno (EOVERFLOW);
 570       return -1;
 571     }
 572 }
 573
 574 #endif
 575
 576 weak_alias (mktime, timelocal)
 577 libc_hidden_def (mktime)
 578 libc_hidden_weak (timelocal)