src/shared/calendarspec.c

   1 /* SPDX-License-Identifier: LGPL-2.1-or-later */
   2
   3 #include <ctype.h>
   4 #include <errno.h>
   5 #include <limits.h>
   6 #include <stddef.h>
   7 #include <stdio.h>
   8 #include <stdlib.h>
   9 #include <sys/mman.h>
  10 #include <unistd.h>
  11
  12 #include "alloc-util.h"
  13 #include "calendarspec.h"
  14 #include "errno-util.h"
  15 #include "fd-util.h"
  16 #include "fileio.h"
  17 #include "macro.h"
  18 #include "memstream-util.h"
  19 #include "parse-util.h"
  20 #include "process-util.h"
  21 #include "sort-util.h"
  22 #include "string-util.h"
  23 #include "strv.h"
  24 #include "time-util.h"
  25
  26 #define BITS_WEEKDAYS 127
  27 #define MIN_YEAR 1970
  28 #define MAX_YEAR 2199
  29
  30 /* An arbitrary limit on the length of the chains of components. We don't want to
  31  * build a very long linked list, which would be slow to iterate over and might cause
  32  * our stack to overflow. It's unlikely that legitimate uses require more than a few
  33  * linked components anyway. */
  34 #define CALENDARSPEC_COMPONENTS_MAX 240
  35
  36 /* Let's make sure that the microsecond component is safe to be stored in an 'int' */
  37 assert_cc(INT_MAX >= USEC_PER_SEC);
  38
  39 static CalendarComponent* chain_free(CalendarComponent *c) {
  40         while (c) {
  41                 CalendarComponent *n = c->next;
  42                 free_and_replace(c, n);
  43         }
  44         return NULL;
  45 }
  46
  47 DEFINE_TRIVIAL_CLEANUP_FUNC(CalendarComponent*, chain_free);
  48
  49 CalendarSpec* calendar_spec_free(CalendarSpec *c) {
  50
  51         if (!c)
  52                 return NULL;
  53
  54         chain_free(c->year);
  55         chain_free(c->month);
  56         chain_free(c->day);
  57         chain_free(c->hour);
  58         chain_free(c->minute);
  59         chain_free(c->microsecond);
  60         free(c->timezone);
  61
  62         return mfree(c);
  63 }
  64
  65 static int component_compare(CalendarComponent * const *a, CalendarComponent * const *b) {
  66         int r;
  67
  68         r = CMP((*a)->start, (*b)->start);
  69         if (r != 0)
  70                 return r;
  71
  72         r = CMP((*a)->stop, (*b)->stop);
  73         if (r != 0)
  74                 return r;
  75
  76         return CMP((*a)->repeat, (*b)->repeat);
  77 }
  78
  79 static void normalize_chain(CalendarComponent **c) {
  80         assert(c);
  81
  82         size_t n = 0;
  83         for (CalendarComponent *i = *c; i; i = i->next) {
  84                 n++;
  85
  86                 /* While we're counting the chain, also normalize 'stop'
  87                  * so the length of the range is a multiple of 'repeat'. */
  88                 if (i->stop > i->start && i->repeat > 0)
  89                         i->stop -= (i->stop - i->start) % i->repeat;
  90
  91                 /* If a repeat value is specified, but it cannot even be triggered once, let's suppress it.
  92                  *
  93                  * Similarly, if the stop value is the same as the start value, then let's just make this a
  94                  * non-repeating chain element. */
  95                 if ((i->stop > i->start && i->repeat > 0 && i->start + i->repeat > i->stop) ||
  96                     i->start == i->stop) {
  97                         i->repeat = 0;
  98                         i->stop = -1;
  99                 }
 100         }
 101
 102         if (n <= 1)
 103                 return;
 104
 105         CalendarComponent **b, **j;
 106         b = j = newa(CalendarComponent*, n);
 107         for (CalendarComponent *i = *c; i; i = i->next)
 108                 *(j++) = i;
 109
 110         typesafe_qsort(b, n, component_compare);
 111
 112         b[n-1]->next = NULL;
 113         CalendarComponent *next = b[n-1];
 114
 115         /* Drop non-unique entries */
 116         for (size_t k = n-1; k > 0; k--) {
 117                 if (component_compare(&b[k-1], &next) == 0) {
 118                         free(b[k-1]);
 119                         continue;
 120                 }
 121
 122                 b[k-1]->next = next;
 123                 next = b[k-1];
 124         }
 125
 126         *c = next;
 127 }
 128
 129 static void fix_year(CalendarComponent *c) {
 130         /* Turns 12 → 2012, 89 → 1989 */
 131
 132         while (c) {
 133                 if (c->start >= 0 && c->start < 70)
 134                         c->start += 2000;
 135
 136                 if (c->stop >= 0 && c->stop < 70)
 137                         c->stop += 2000;
 138
 139                 if (c->start >= 70 && c->start < 100)
 140                         c->start += 1900;
 141
 142                 if (c->stop >= 70 && c->stop < 100)
 143                         c->stop += 1900;
 144
 145                 c = c->next;
 146         }
 147 }
 148
 149 static void calendar_spec_normalize(CalendarSpec *c) {
 150         assert(c);
 151
 152         if (streq_ptr(c->timezone, "UTC")) {
 153                 c->utc = true;
 154                 c->timezone = mfree(c->timezone);
 155         }
 156
 157         if (c->weekdays_bits <= 0 || c->weekdays_bits >= BITS_WEEKDAYS)
 158                 c->weekdays_bits = -1;
 159
 160         if (c->end_of_month && !c->day)
 161                 c->end_of_month = false;
 162
 163         fix_year(c->year);
 164
 165         normalize_chain(&c->year);
 166         normalize_chain(&c->month);
 167         normalize_chain(&c->day);
 168         normalize_chain(&c->hour);
 169         normalize_chain(&c->minute);
 170         normalize_chain(&c->microsecond);
 171 }
 172
 173 static bool chain_valid(CalendarComponent *c, int from, int to, bool end_of_month) {
 174         assert(to >= from);
 175
 176         if (!c)
 177                 return true;
 178
 179         /* Forbid dates more than 28 days from the end of the month */
 180         if (end_of_month)
 181                 to -= 3;
 182
 183         if (c->start < from || c->start > to)
 184                 return false;
 185
 186         /* Avoid overly large values that could cause overflow */
 187         if (c->repeat > to - from)
 188                 return false;
 189
 190         /*
 191          * c->repeat must be short enough so at least one repetition may
 192          * occur before the end of the interval.  For dates scheduled
 193          * relative to the end of the month, c->start and c->stop
 194          * correspond to the Nth last day of the month.
 195          */
 196         if (c->stop >= 0) {
 197                 if (c->stop < from || c ->stop > to)
 198                         return false;
 199
 200                 if (c->start + c->repeat > c->stop)
 201                         return false;
 202         } else {
 203                 if (end_of_month && c->start - c->repeat < from)
 204                         return false;
 205
 206                 if (!end_of_month && c->start + c->repeat > to)
 207                         return false;
 208         }
 209
 210         if (c->next)
 211                 return chain_valid(c->next, from, to, end_of_month);
 212
 213         return true;
 214 }
 215
 216 _pure_ bool calendar_spec_valid(CalendarSpec *c) {
 217         assert(c);
 218
 219         if (c->weekdays_bits > BITS_WEEKDAYS)
 220                 return false;
 221
 222         if (!chain_valid(c->year, MIN_YEAR, MAX_YEAR, false))
 223                 return false;
 224
 225         if (!chain_valid(c->month, 1, 12, false))
 226                 return false;
 227
 228         if (!chain_valid(c->day, 1, 31, c->end_of_month))
 229                 return false;
 230
 231         if (!chain_valid(c->hour, 0, 23, false))
 232                 return false;
 233
 234         if (!chain_valid(c->minute, 0, 59, false))
 235                 return false;
 236
 237         if (!chain_valid(c->microsecond, 0, 60*USEC_PER_SEC-1, false))
 238                 return false;
 239
 240         return true;
 241 }
 242
 243 static void format_weekdays(FILE *f, const CalendarSpec *c) {
 244         static const char *const days[] = {
 245                 "Mon",
 246                 "Tue",
 247                 "Wed",
 248                 "Thu",
 249                 "Fri",
 250                 "Sat",
 251                 "Sun",
 252         };
 253
 254         int l, x;
 255         bool need_comma = false;
 256
 257         assert(f);
 258         assert(c);
 259         assert(c->weekdays_bits > 0 && c->weekdays_bits <= BITS_WEEKDAYS);
 260
 261         for (x = 0, l = -1; x < (int) ELEMENTSOF(days); x++) {
 262
 263                 if (c->weekdays_bits & (1 << x)) {
 264
 265                         if (l < 0) {
 266                                 if (need_comma)
 267                                         fputc(',', f);
 268                                 else
 269                                         need_comma = true;
 270
 271                                 fputs(days[x], f);
 272                                 l = x;
 273                         }
 274
 275                 } else if (l >= 0) {
 276
 277                         if (x > l + 1) {
 278                                 fputs(x > l + 2 ? ".." : ",", f);
 279                                 fputs(days[x-1], f);
 280                         }
 281
 282                         l = -1;
 283                 }
 284         }
 285
 286         if (l >= 0 && x > l + 1) {
 287                 fputs(x > l + 2 ? ".." : ",", f);
 288                 fputs(days[x-1], f);
 289         }
 290 }
 291
 292 static bool chain_is_star(const CalendarComponent *c, bool usec) {
 293         /* Return true if the whole chain can be replaced by '*'.
 294          * This happens when the chain is empty or one of the components covers all. */
 295         if (!c)
 296                 return true;
 297         if (usec)
 298                 for (; c; c = c->next)
 299                         if (c->start == 0 && c->stop < 0 && c->repeat == USEC_PER_SEC)
 300                                 return true;
 301         return false;
 302 }
 303
 304 static void _format_chain(FILE *f, int space, const CalendarComponent *c, bool start, bool usec) {
 305         int d = usec ? (int) USEC_PER_SEC : 1;
 306
 307         assert(f);
 308
 309         if (start && chain_is_star(c, usec)) {
 310                 fputc('*', f);
 311                 return;
 312         }
 313
 314         assert(c->start >= 0);
 315
 316         fprintf(f, "%0*i", space, c->start / d);
 317         if (c->start % d > 0)
 318                 fprintf(f, ".%06i", c->start % d);
 319
 320         if (c->stop > 0)
 321                 fprintf(f, "..%0*i", space, c->stop / d);
 322         if (c->stop % d > 0)
 323                 fprintf(f, ".%06i", c->stop % d);
 324
 325         if (c->repeat > 0 && !(c->stop > 0 && c->repeat == d))
 326                 fprintf(f, "/%i", c->repeat / d);
 327         if (c->repeat % d > 0)
 328                 fprintf(f, ".%06i", c->repeat % d);
 329
 330         if (c->next) {
 331                 fputc(',', f);
 332                 _format_chain(f, space, c->next, false, usec);
 333         }
 334 }
 335
 336 static void format_chain(FILE *f, int space, const CalendarComponent *c, bool usec) {
 337         _format_chain(f, space, c, /* start = */ true, usec);
 338 }
 339
 340 int calendar_spec_to_string(const CalendarSpec *c, char **ret) {
 341         _cleanup_(memstream_done) MemStream m = {};
 342         FILE *f;
 343
 344         assert(c);
 345         assert(ret);
 346
 347         f = memstream_init(&m);
 348         if (!f)
 349                 return -ENOMEM;
 350
 351         if (c->weekdays_bits > 0 && c->weekdays_bits <= BITS_WEEKDAYS) {
 352                 format_weekdays(f, c);
 353                 fputc(' ', f);
 354         }
 355
 356         format_chain(f, 4, c->year, false);
 357         fputc('-', f);
 358         format_chain(f, 2, c->month, false);
 359         fputc(c->end_of_month ? '~' : '-', f);
 360         format_chain(f, 2, c->day, false);
 361         fputc(' ', f);
 362         format_chain(f, 2, c->hour, false);
 363         fputc(':', f);
 364         format_chain(f, 2, c->minute, false);
 365         fputc(':', f);
 366         format_chain(f, 2, c->microsecond, true);
 367
 368         if (c->utc)
 369                 fputs(" UTC", f);
 370         else if (c->timezone) {
 371                 fputc(' ', f);
 372                 fputs(c->timezone, f);
 373         } else if (IN_SET(c->dst, 0, 1)) {
 374
 375                 /* If daylight saving is explicitly on or off, let's show the used timezone. */
 376
 377                 tzset();
 378
 379                 if (!isempty(tzname[c->dst])) {
 380                         fputc(' ', f);
 381                         fputs(tzname[c->dst], f);
 382                 }
 383         }
 384
 385         return memstream_finalize(&m, ret, NULL);
 386 }
 387
 388 static int parse_weekdays(const char **p, CalendarSpec *c) {
 389         static const struct {
 390                 const char *name;
 391                 const int nr;
 392         } day_nr[] = {
 393                 { "Monday",    0 },
 394                 { "Mon",       0 },
 395                 { "Tuesday",   1 },
 396                 { "Tue",       1 },
 397                 { "Wednesday", 2 },
 398                 { "Wed",       2 },
 399                 { "Thursday",  3 },
 400                 { "Thu",       3 },
 401                 { "Friday",    4 },
 402                 { "Fri",       4 },
 403                 { "Saturday",  5 },
 404                 { "Sat",       5 },
 405                 { "Sunday",    6 },
 406                 { "Sun",       6 },
 407         };
 408
 409         int l = -1;
 410         bool first = true;
 411
 412         assert(p);
 413         assert(*p);
 414         assert(c);
 415
 416         for (;;) {
 417                 size_t i;
 418
 419                 for (i = 0; i < ELEMENTSOF(day_nr); i++) {
 420                         size_t skip;
 421
 422                         if (!startswith_no_case(*p, day_nr[i].name))
 423                                 continue;
 424
 425                         skip = strlen(day_nr[i].name);
 426
 427                         if (!IN_SET((*p)[skip], 0, '-', '.', ',', ' '))
 428                                 return -EINVAL;
 429
 430                         c->weekdays_bits |= 1 << day_nr[i].nr;
 431
 432                         if (l >= 0) {
 433                                 if (l > day_nr[i].nr)
 434                                         return -EINVAL;
 435
 436                                 for (int j = l + 1; j < day_nr[i].nr; j++)
 437                                         c->weekdays_bits |= 1 << j;
 438                         }
 439
 440                         *p += skip;
 441                         break;
 442                 }
 443
 444                 /* Couldn't find this prefix, so let's assume the
 445                    weekday was not specified and let's continue with
 446                    the date */
 447                 if (i >= ELEMENTSOF(day_nr))
 448                         return first ? 0 : -EINVAL;
 449
 450                 /* We reached the end of the string */
 451                 if (**p == 0)
 452                         return 0;
 453
 454                 /* We reached the end of the weekday spec part */
 455                 if (**p == ' ') {
 456                         *p += strspn(*p, " ");
 457                         return 0;
 458                 }
 459
 460                 if (**p == '.') {
 461                         if (l >= 0)
 462                                 return -EINVAL;
 463
 464                         if ((*p)[1] != '.')
 465                                 return -EINVAL;
 466
 467                         l = day_nr[i].nr;
 468                         *p += 2;
 469
 470                 /* Support ranges with "-" for backwards compatibility */
 471                 } else if (**p == '-') {
 472                         if (l >= 0)
 473                                 return -EINVAL;
 474
 475                         l = day_nr[i].nr;
 476                         *p += 1;
 477
 478                 } else if (**p == ',') {
 479                         l = -1;
 480                         *p += 1;
 481                 }
 482
 483                 /* Allow a trailing comma but not an open range */
 484                 if (IN_SET(**p, 0, ' ')) {
 485                         *p += strspn(*p, " ");
 486                         return l < 0 ? 0 : -EINVAL;
 487                 }
 488
 489                 first = false;
 490         }
 491 }
 492
 493 static int parse_one_number(const char *p, const char **e, unsigned long *ret) {
 494         char *ee = NULL;
 495         unsigned long value;
 496
 497         errno = 0;
 498         value = strtoul(p, &ee, 10);
 499         if (errno > 0)
 500                 return -errno;
 501         if (ee == p)
 502                 return -EINVAL;
 503
 504         *ret = value;
 505         *e = ee;
 506         return 0;
 507 }
 508
 509 static int parse_component_decimal(const char **p, bool usec, int *res) {
 510         unsigned long value;
 511         const char *e = NULL;
 512         int r;
 513
 514         if (!ascii_isdigit(**p))
 515                 return -EINVAL;
 516
 517         r = parse_one_number(*p, &e, &value);
 518         if (r < 0)
 519                 return r;
 520
 521         if (usec) {
 522                 if (value * USEC_PER_SEC / USEC_PER_SEC != value)
 523                         return -ERANGE;
 524
 525                 value *= USEC_PER_SEC;
 526
 527                 /* One "." is a decimal point, but ".." is a range separator */
 528                 if (e[0] == '.' && e[1] != '.') {
 529                         unsigned add;
 530
 531                         e++;
 532                         r = parse_fractional_part_u(&e, 6, &add);
 533                         if (r < 0)
 534                                 return r;
 535
 536                         if (add + value < value)
 537                                 return -ERANGE;
 538                         value += add;
 539                 }
 540         }
 541
 542         if (value > INT_MAX)
 543                 return -ERANGE;
 544
 545         *p = e;
 546         *res = value;
 547
 548         return 0;
 549 }
 550
 551 static int const_chain(int value, CalendarComponent **c) {
 552         CalendarComponent *cc = NULL;
 553
 554         assert(c);
 555
 556         cc = new(CalendarComponent, 1);
 557         if (!cc)
 558                 return -ENOMEM;
 559
 560         *cc = (CalendarComponent) {
 561                 .start = value,
 562                 .stop = -1,
 563                 .repeat = 0,
 564                 .next = *c,
 565         };
 566
 567         *c = cc;
 568
 569         return 0;
 570 }
 571
 572 static int calendarspec_from_time_t(CalendarSpec *c, time_t time) {
 573         _cleanup_(chain_freep) CalendarComponent
 574                 *year = NULL, *month = NULL, *day = NULL,
 575                 *hour = NULL, *minute = NULL, *us = NULL;
 576         struct tm tm;
 577         int r;
 578
 579         if (!gmtime_r(&time, &tm))
 580                 return -ERANGE;
 581
 582         if (tm.tm_year > INT_MAX - 1900)
 583                 return -ERANGE;
 584
 585         r = const_chain(tm.tm_year + 1900, &year);
 586         if (r < 0)
 587                 return r;
 588
 589         r = const_chain(tm.tm_mon + 1, &month);
 590         if (r < 0)
 591                 return r;
 592
 593         r = const_chain(tm.tm_mday, &day);
 594         if (r < 0)
 595                 return r;
 596
 597         r = const_chain(tm.tm_hour, &hour);
 598         if (r < 0)
 599                 return r;
 600
 601         r = const_chain(tm.tm_min, &minute);
 602         if (r < 0)
 603                 return r;
 604
 605         r = const_chain(tm.tm_sec * USEC_PER_SEC, &us);
 606         if (r < 0)
 607                 return r;
 608
 609         c->utc = true;
 610         c->year = TAKE_PTR(year);
 611         c->month = TAKE_PTR(month);
 612         c->day = TAKE_PTR(day);
 613         c->hour = TAKE_PTR(hour);
 614         c->minute = TAKE_PTR(minute);
 615         c->microsecond = TAKE_PTR(us);
 616         return 0;
 617 }
 618
 619 static int prepend_component(const char **p, bool usec, unsigned nesting, CalendarComponent **c) {
 620         int r, start, stop = -1, repeat = 0;
 621         CalendarComponent *cc;
 622         const char *e = *p;
 623
 624         assert(p);
 625         assert(c);
 626
 627         if (nesting > CALENDARSPEC_COMPONENTS_MAX)
 628                 return -ENOBUFS;
 629
 630         r = parse_component_decimal(&e, usec, &start);
 631         if (r < 0)
 632                 return r;
 633
 634         if (e[0] == '.' && e[1] == '.') {
 635                 e += 2;
 636                 r = parse_component_decimal(&e, usec, &stop);
 637                 if (r < 0)
 638                         return r;
 639
 640                 repeat = usec ? USEC_PER_SEC : 1;
 641         }
 642
 643         if (*e == '/') {
 644                 e++;
 645                 r = parse_component_decimal(&e, usec, &repeat);
 646                 if (r < 0)
 647                         return r;
 648
 649                 if (repeat == 0)
 650                         return -ERANGE;
 651         } else {
 652                 /* If no repeat value is specified for the μs component, then let's explicitly refuse ranges
 653                  * below 1s because our default repeat granularity is beyond that. */
 654
 655                 /* Overflow check */
 656                 if (start > INT_MAX - repeat)
 657                         return -ERANGE;
 658
 659                 if (usec && stop >= 0 && start + repeat > stop)
 660                         return -EINVAL;
 661         }
 662
 663         if (!IN_SET(*e, 0, ' ', ',', '-', '~', ':'))
 664                 return -EINVAL;
 665
 666         cc = new(CalendarComponent, 1);
 667         if (!cc)
 668                 return -ENOMEM;
 669
 670         *cc = (CalendarComponent) {
 671                 .start = start,
 672                 .stop = stop,
 673                 .repeat = repeat,
 674                 .next = *c,
 675         };
 676
 677         *p = e;
 678         *c = cc;
 679
 680         if (*e ==',') {
 681                 *p += 1;
 682                 return prepend_component(p, usec, nesting + 1, c);
 683         }
 684
 685         return 0;
 686 }
 687
 688 static int parse_chain(const char **p, bool usec, CalendarComponent **c) {
 689         _cleanup_(chain_freep) CalendarComponent *cc = NULL;
 690         const char *t;
 691         int r;
 692
 693         assert(p);
 694         assert(c);
 695
 696         t = *p;
 697
 698         if (t[0] == '*') {
 699                 if (usec) {
 700                         r = const_chain(0, c);
 701                         if (r < 0)
 702                                 return r;
 703                         (*c)->repeat = USEC_PER_SEC;
 704                 } else
 705                         *c = NULL;
 706
 707                 *p = t + 1;
 708                 return 0;
 709         }
 710
 711         r = prepend_component(&t, usec, 0, &cc);
 712         if (r < 0)
 713                 return r;
 714
 715         *p = t;
 716         *c = TAKE_PTR(cc);
 717         return 0;
 718 }
 719
 720 static int parse_date(const char **p, CalendarSpec *c) {
 721         _cleanup_(chain_freep) CalendarComponent *first = NULL, *second = NULL, *third = NULL;
 722         const char *t;
 723         int r;
 724
 725         assert(p);
 726         assert(*p);
 727         assert(c);
 728
 729         t = *p;
 730
 731         if (*t == 0)
 732                 return 0;
 733
 734         /* @TIMESTAMP — UNIX time in seconds since the epoch */
 735         if (*t == '@') {
 736                 unsigned long value;
 737                 time_t time;
 738
 739                 r = parse_one_number(t + 1, &t, &value);
 740                 if (r < 0)
 741                         return r;
 742
 743                 time = value;
 744                 if ((unsigned long) time != value)
 745                         return -ERANGE;
 746
 747                 r = calendarspec_from_time_t(c, time);
 748                 if (r < 0)
 749                         return r;
 750
 751                 *p = t;
 752                 return 1; /* finito, don't parse H:M:S after that */
 753         }
 754
 755         r = parse_chain(&t, false, &first);
 756         if (r < 0)
 757                 return r;
 758
 759         /* Already the end? A ':' as separator? In that case this was a time, not a date */
 760         if (IN_SET(*t, 0, ':'))
 761                 return 0;
 762
 763         if (*t == '~')
 764                 c->end_of_month = true;
 765         else if (*t != '-')
 766                 return -EINVAL;
 767
 768         t++;
 769         r = parse_chain(&t, false, &second);
 770         if (r < 0)
 771                 return r;
 772
 773         /* Got two parts, hence it's month and day */
 774         if (IN_SET(*t, 0, ' ')) {
 775                 *p = t + strspn(t, " ");
 776                 c->month = TAKE_PTR(first);
 777                 c->day = TAKE_PTR(second);
 778                 return 0;
 779         } else if (c->end_of_month)
 780                 return -EINVAL;
 781
 782         if (*t == '~')
 783                 c->end_of_month = true;
 784         else if (*t != '-')
 785                 return -EINVAL;
 786
 787         t++;
 788         r = parse_chain(&t, false, &third);
 789         if (r < 0)
 790                 return r;
 791
 792         if (!IN_SET(*t, 0, ' '))
 793                 return -EINVAL;
 794
 795         /* Got three parts, hence it is year, month and day */
 796         *p = t + strspn(t, " ");
 797         c->year = TAKE_PTR(first);
 798         c->month = TAKE_PTR(second);
 799         c->day = TAKE_PTR(third);
 800         return 0;
 801 }
 802
 803 static int parse_calendar_time(const char **p, CalendarSpec *c) {
 804         _cleanup_(chain_freep) CalendarComponent *h = NULL, *m = NULL, *s = NULL;
 805         const char *t;
 806         int r;
 807
 808         assert(p);
 809         assert(*p);
 810         assert(c);
 811
 812         t = *p;
 813
 814         /* If no time is specified at all, then this means 00:00:00 */
 815         if (*t == 0)
 816                 goto null_hour;
 817
 818         r = parse_chain(&t, false, &h);
 819         if (r < 0)
 820                 return r;
 821
 822         if (*t != ':')
 823                 return -EINVAL;
 824
 825         t++;
 826         r = parse_chain(&t, false, &m);
 827         if (r < 0)
 828                 return r;
 829
 830         /* Already at the end? Then it's hours and minutes, and seconds are 0 */
 831         if (*t == 0)
 832                 goto null_second;
 833
 834         if (*t != ':')
 835                 return -EINVAL;
 836
 837         t++;
 838         r = parse_chain(&t, true, &s);
 839         if (r < 0)
 840                 return r;
 841
 842         /* At the end? Then it's hours, minutes and seconds */
 843         if (*t == 0)
 844                 goto finish;
 845
 846         return -EINVAL;
 847
 848 null_hour:
 849         r = const_chain(0, &h);
 850         if (r < 0)
 851                 return r;
 852
 853         r = const_chain(0, &m);
 854         if (r < 0)
 855                 return r;
 856
 857 null_second:
 858         r = const_chain(0, &s);
 859         if (r < 0)
 860                 return r;
 861
 862 finish:
 863         *p = t;
 864         c->hour = TAKE_PTR(h);
 865         c->minute = TAKE_PTR(m);
 866         c->microsecond = TAKE_PTR(s);
 867
 868         return 0;
 869 }
 870
 871 int calendar_spec_from_string(const char *p, CalendarSpec **ret) {
 872         const char *utc;
 873         _cleanup_(calendar_spec_freep) CalendarSpec *c = NULL;
 874         _cleanup_free_ char *p_tmp = NULL;
 875         int r;
 876
 877         assert(p);
 878
 879         c = new(CalendarSpec, 1);
 880         if (!c)
 881                 return -ENOMEM;
 882
 883         *c = (CalendarSpec) {
 884                 .dst = -1,
 885                 .timezone = NULL,
 886         };
 887
 888         utc = endswith_no_case(p, " UTC");
 889         if (utc) {
 890                 c->utc = true;
 891                 p = p_tmp = strndup(p, utc - p);
 892                 if (!p)
 893                         return -ENOMEM;
 894         } else {
 895                 const char *e = NULL;
 896                 int j;
 897
 898                 tzset();
 899
 900                 /* Check if the local timezone was specified? */
 901                 for (j = 0; j <= 1; j++) {
 902                         if (isempty(tzname[j]))
 903                                 continue;
 904
 905                         e = endswith_no_case(p, tzname[j]);
 906                         if (!e)
 907                                 continue;
 908                         if (e == p)
 909                                 continue;
 910                         if (e[-1] != ' ')
 911                                 continue;
 912
 913                         break;
 914                 }
 915
 916                 /* Found one of the two timezones specified? */
 917                 if (IN_SET(j, 0, 1)) {
 918                         p = p_tmp = strndup(p, e - p - 1);
 919                         if (!p)
 920                                 return -ENOMEM;
 921
 922                         c->dst = j;
 923                 } else {
 924                         const char *last_space;
 925
 926                         last_space = strrchr(p, ' ');
 927                         if (last_space != NULL && timezone_is_valid(last_space + 1, LOG_DEBUG)) {
 928                                 c->timezone = strdup(last_space + 1);
 929                                 if (!c->timezone)
 930                                         return -ENOMEM;
 931
 932                                 p = p_tmp = strndup(p, last_space - p);
 933                                 if (!p)
 934                                         return -ENOMEM;
 935                         }
 936                 }
 937         }
 938
 939         if (isempty(p))
 940                 return -EINVAL;
 941
 942         if (strcaseeq(p, "minutely")) {
 943                 r = const_chain(0, &c->microsecond);
 944                 if (r < 0)
 945                         return r;
 946
 947         } else if (strcaseeq(p, "hourly")) {
 948                 r = const_chain(0, &c->minute);
 949                 if (r < 0)
 950                         return r;
 951                 r = const_chain(0, &c->microsecond);
 952                 if (r < 0)
 953                         return r;
 954
 955         } else if (strcaseeq(p, "daily")) {
 956                 r = const_chain(0, &c->hour);
 957                 if (r < 0)
 958                         return r;
 959                 r = const_chain(0, &c->minute);
 960                 if (r < 0)
 961                         return r;
 962                 r = const_chain(0, &c->microsecond);
 963                 if (r < 0)
 964                         return r;
 965
 966         } else if (strcaseeq(p, "monthly")) {
 967                 r = const_chain(1, &c->day);
 968                 if (r < 0)
 969                         return r;
 970                 r = const_chain(0, &c->hour);
 971                 if (r < 0)
 972                         return r;
 973                 r = const_chain(0, &c->minute);
 974                 if (r < 0)
 975                         return r;
 976                 r = const_chain(0, &c->microsecond);
 977                 if (r < 0)
 978                         return r;
 979
 980         } else if (STRCASE_IN_SET(p,
 981                                   "annually",
 982                                   "yearly",
 983                                   "anually") /* backwards compatibility */ ) {
 984
 985                 r = const_chain(1, &c->month);
 986                 if (r < 0)
 987                         return r;
 988                 r = const_chain(1, &c->day);
 989                 if (r < 0)
 990                         return r;
 991                 r = const_chain(0, &c->hour);
 992                 if (r < 0)
 993                         return r;
 994                 r = const_chain(0, &c->minute);
 995                 if (r < 0)
 996                         return r;
 997                 r = const_chain(0, &c->microsecond);
 998                 if (r < 0)
 999                         return r;
1000
1001         } else if (strcaseeq(p, "weekly")) {
1002
1003                 c->weekdays_bits = 1;
1004
1005                 r = const_chain(0, &c->hour);
1006                 if (r < 0)
1007                         return r;
1008                 r = const_chain(0, &c->minute);
1009                 if (r < 0)
1010                         return r;
1011                 r = const_chain(0, &c->microsecond);
1012                 if (r < 0)
1013                         return r;
1014
1015         } else if (strcaseeq(p, "quarterly")) {
1016
1017                 r = const_chain(1, &c->month);
1018                 if (r < 0)
1019                         return r;
1020                 r = const_chain(4, &c->month);
1021                 if (r < 0)
1022                         return r;
1023                 r = const_chain(7, &c->month);
1024                 if (r < 0)
1025                         return r;
1026                 r = const_chain(10, &c->month);
1027                 if (r < 0)
1028                         return r;
1029                 r = const_chain(1, &c->day);
1030                 if (r < 0)
1031                         return r;
1032                 r = const_chain(0, &c->hour);
1033                 if (r < 0)
1034                         return r;
1035                 r = const_chain(0, &c->minute);
1036                 if (r < 0)
1037                         return r;
1038                 r = const_chain(0, &c->microsecond);
1039                 if (r < 0)
1040                         return r;
1041
1042         } else if (STRCASE_IN_SET(p,
1043                                   "biannually",
1044                                   "bi-annually",
1045                                   "semiannually",
1046                                   "semi-annually")) {
1047
1048                 r = const_chain(1, &c->month);
1049                 if (r < 0)
1050                         return r;
1051                 r = const_chain(7, &c->month);
1052                 if (r < 0)
1053                         return r;
1054                 r = const_chain(1, &c->day);
1055                 if (r < 0)
1056                         return r;
1057                 r = const_chain(0, &c->hour);
1058                 if (r < 0)
1059                         return r;
1060                 r = const_chain(0, &c->minute);
1061                 if (r < 0)
1062                         return r;
1063                 r = const_chain(0, &c->microsecond);
1064                 if (r < 0)
1065                         return r;
1066
1067         } else {
1068                 r = parse_weekdays(&p, c);
1069                 if (r < 0)
1070                         return r;
1071
1072                 r = parse_date(&p, c);
1073                 if (r < 0)
1074                         return r;
1075
1076                 if (r == 0) {
1077                         r = parse_calendar_time(&p, c);
1078                         if (r < 0)
1079                                 return r;
1080                 }
1081
1082                 if (*p != 0)
1083                         return -EINVAL;
1084         }
1085
1086         calendar_spec_normalize(c);
1087
1088         if (!calendar_spec_valid(c))
1089                 return -EINVAL;
1090
1091         if (ret)
1092                 *ret = TAKE_PTR(c);
1093         return 0;
1094 }
1095
1096 static int find_end_of_month(const struct tm *tm, bool utc, int day) {
1097         struct tm t = *tm;
1098
1099         t.tm_mon++;
1100         t.tm_mday = 1 - day;
1101
1102         if (mktime_or_timegm(&t, utc) < 0 ||
1103             t.tm_mon != tm->tm_mon)
1104                 return -1;
1105
1106         return t.tm_mday;
1107 }
1108
1109 static int find_matching_component(
1110                 const CalendarSpec *spec,
1111                 const CalendarComponent *c,
1112                 const struct tm *tm,           /* tm is only used for end-of-month calculations */
1113                 int *val) {
1114
1115         int d = -1, r;
1116         bool d_set = false;
1117
1118         assert(val);
1119
1120         /* Finds the *earliest* matching time specified by one of the CalendarCompoment items in chain c.
1121          * If no matches can be found, returns -ENOENT.
1122          * Otherwise, updates *val to the matching time. 1 is returned if *val was changed, 0 otherwise.
1123          */
1124
1125         if (!c)
1126                 return 0;
1127
1128         bool end_of_month = spec->end_of_month && c == spec->day;
1129
1130         while (c) {
1131                 int start, stop;
1132
1133                 if (end_of_month) {
1134                         start = find_end_of_month(tm, spec->utc, c->start);
1135                         stop = find_end_of_month(tm, spec->utc, c->stop);
1136
1137                         if (stop > 0)
1138                                 SWAP_TWO(start, stop);
1139                 } else {
1140                         start = c->start;
1141                         stop = c->stop;
1142                 }
1143
1144                 if (start >= *val) {
1145
1146                         if (!d_set || start < d) {
1147                                 d = start;
1148                                 d_set = true;
1149                         }
1150
1151                 } else if (c->repeat > 0) {
1152                         int k;
1153
1154                         k = start + ROUND_UP(*val - start, c->repeat);
1155
1156                         if ((!d_set || k < d) && (stop < 0 || k <= stop)) {
1157                                 d = k;
1158                                 d_set = true;
1159                         }
1160                 }
1161
1162                 c = c->next;
1163         }
1164
1165         if (!d_set)
1166                 return -ENOENT;
1167
1168         r = *val != d;
1169         *val = d;
1170         return r;
1171 }
1172
1173 static int tm_within_bounds(struct tm *tm, bool utc) {
1174         struct tm t;
1175         int cmp;
1176         assert(tm);
1177
1178         /*
1179          * Set an upper bound on the year so impossible dates like "*-02-31"
1180          * don't cause find_next() to loop forever. tm_year contains years
1181          * since 1900, so adjust it accordingly.
1182          */
1183         if (tm->tm_year + 1900 > MAX_YEAR)
1184                 return -ERANGE;
1185
1186         t = *tm;
1187         if (mktime_or_timegm(&t, utc) < 0)
1188                 return negative_errno();
1189
1190         /*
1191          * Did any normalization take place? If so, it was out of bounds before.
1192          * Normalization could skip next elapse, e.g. result of normalizing 3-33
1193          * is 4-2. This skips 4-1. So reset the sub time unit if upper unit was
1194          * out of bounds. Normalization has occurred implies find_matching_component() > 0,
1195          * other sub time units are already reset in find_next().
1196          */
1197         if ((cmp = CMP(t.tm_year, tm->tm_year)) != 0)
1198                 t.tm_mon = 0;
1199         else if ((cmp = CMP(t.tm_mon, tm->tm_mon)) != 0)
1200                 t.tm_mday = 1;
1201         else if ((cmp = CMP(t.tm_mday, tm->tm_mday)) != 0)
1202                 t.tm_hour = 0;
1203         else if ((cmp = CMP(t.tm_hour, tm->tm_hour)) != 0)
1204                 t.tm_min = 0;
1205         else if ((cmp = CMP(t.tm_min, tm->tm_min)) != 0)
1206                 t.tm_sec = 0;
1207         else
1208                 cmp = CMP(t.tm_sec, tm->tm_sec);
1209
1210         if (cmp < 0)
1211                 return -EDEADLK; /* Refuse to go backward */
1212         if (cmp > 0)
1213                 *tm = t;
1214         return cmp == 0;
1215 }
1216
1217 static bool matches_weekday(int weekdays_bits, const struct tm *tm, bool utc) {
1218         struct tm t;
1219         int k;
1220
1221         if (weekdays_bits < 0 || weekdays_bits >= BITS_WEEKDAYS)
1222                 return true;
1223
1224         t = *tm;
1225         if (mktime_or_timegm(&t, utc) < 0)
1226                 return false;
1227
1228         k = t.tm_wday == 0 ? 6 : t.tm_wday - 1;
1229         return (weekdays_bits & (1 << k));
1230 }
1231
1232 /* A safety valve: if we get stuck in the calculation, return an error.
1233  * C.f. https://bugzilla.redhat.com/show_bug.cgi?id=1941335. */
1234 #define MAX_CALENDAR_ITERATIONS 1000
1235
1236 static int find_next(const CalendarSpec *spec, struct tm *tm, usec_t *usec) {
1237         struct tm c;
1238         int tm_usec;
1239         int r;
1240
1241         /* Returns -ENOENT if the expression is not going to elapse anymore */
1242
1243         assert(spec);
1244         assert(tm);
1245
1246         c = *tm;
1247         tm_usec = *usec;
1248
1249         for (unsigned iteration = 0; iteration < MAX_CALENDAR_ITERATIONS; iteration++) {
1250                 /* Normalize the current date */
1251                 (void) mktime_or_timegm(&c, spec->utc);
1252                 c.tm_isdst = spec->dst;
1253
1254                 c.tm_year += 1900;
1255                 r = find_matching_component(spec, spec->year, &c, &c.tm_year);
1256                 c.tm_year -= 1900;
1257
1258                 if (r > 0) {
1259                         c.tm_mon = 0;
1260                         c.tm_mday = 1;
1261                         c.tm_hour = c.tm_min = c.tm_sec = tm_usec = 0;
1262                 }
1263                 if (r < 0)
1264                         return r;
1265                 if (tm_within_bounds(&c, spec->utc) <= 0)
1266                         return -ENOENT;
1267
1268                 c.tm_mon += 1;
1269                 r = find_matching_component(spec, spec->month, &c, &c.tm_mon);
1270                 c.tm_mon -= 1;
1271
1272                 if (r > 0) {
1273                         c.tm_mday = 1;
1274                         c.tm_hour = c.tm_min = c.tm_sec = tm_usec = 0;
1275                 }
1276                 if (r < 0 || (r = tm_within_bounds(&c, spec->utc)) < 0) {
1277                         c.tm_year++;
1278                         c.tm_mon = 0;
1279                         c.tm_mday = 1;
1280                         c.tm_hour = c.tm_min = c.tm_sec = tm_usec = 0;
1281                         continue;
1282                 }
1283                 if (r == 0)
1284                         continue;
1285
1286                 r = find_matching_component(spec, spec->day, &c, &c.tm_mday);
1287                 if (r > 0)
1288                         c.tm_hour = c.tm_min = c.tm_sec = tm_usec = 0;
1289                 if (r < 0 || (r = tm_within_bounds(&c, spec->utc)) < 0) {
1290                         c.tm_mon++;
1291                         c.tm_mday = 1;
1292                         c.tm_hour = c.tm_min = c.tm_sec = tm_usec = 0;
1293                         continue;
1294                 }
1295                 if (r == 0)
1296                         continue;
1297
1298                 if (!matches_weekday(spec->weekdays_bits, &c, spec->utc)) {
1299                         c.tm_mday++;
1300                         c.tm_hour = c.tm_min = c.tm_sec = tm_usec = 0;
1301                         continue;
1302                 }
1303
1304                 r = find_matching_component(spec, spec->hour, &c, &c.tm_hour);
1305                 if (r > 0)
1306                         c.tm_min = c.tm_sec = tm_usec = 0;
1307                 if (r < 0 || (r = tm_within_bounds(&c, spec->utc)) < 0) {
1308                         c.tm_mday++;
1309                         c.tm_hour = c.tm_min = c.tm_sec = tm_usec = 0;
1310                         continue;
1311                 }
1312                 if (r == 0)
1313                         /* The next hour we set might be missing if there
1314                          * are time zone changes. Let's try again starting at
1315                          * normalized time. */
1316                         continue;
1317
1318                 r = find_matching_component(spec, spec->minute, &c, &c.tm_min);
1319                 if (r > 0)
1320                         c.tm_sec = tm_usec = 0;
1321                 if (r < 0 || (r = tm_within_bounds(&c, spec->utc)) < 0) {
1322                         c.tm_hour++;
1323                         c.tm_min = c.tm_sec = tm_usec = 0;
1324                         continue;
1325                 }
1326                 if (r == 0)
1327                         continue;
1328
1329                 c.tm_sec = c.tm_sec * USEC_PER_SEC + tm_usec;
1330                 r = find_matching_component(spec, spec->microsecond, &c, &c.tm_sec);
1331                 tm_usec = c.tm_sec % USEC_PER_SEC;
1332                 c.tm_sec /= USEC_PER_SEC;
1333
1334                 if (r < 0 || (r = tm_within_bounds(&c, spec->utc)) < 0) {
1335                         c.tm_min++;
1336                         c.tm_sec = tm_usec = 0;
1337                         continue;
1338                 }
1339                 if (r == 0)
1340                         continue;
1341
1342                 *tm = c;
1343                 *usec = tm_usec;
1344                 return 0;
1345         }
1346
1347         /* It seems we entered an infinite loop. Let's gracefully return an error instead of hanging or
1348          * aborting. This code is also exercised when timers.target is brought up during early boot, so
1349          * aborting here is problematic and hard to diagnose for users. */
1350         _cleanup_free_ char *s = NULL;
1351         (void) calendar_spec_to_string(spec, &s);
1352         return log_warning_errno(SYNTHETIC_ERRNO(EDEADLK),
1353                                  "Infinite loop in calendar calculation: %s", strna(s));
1354 }
1355
1356 static int calendar_spec_next_usec_impl(const CalendarSpec *spec, usec_t usec, usec_t *ret_next) {
1357         struct tm tm;
1358         time_t t;
1359         int r;
1360         usec_t tm_usec;
1361
1362         assert(spec);
1363
1364         if (usec > USEC_TIMESTAMP_FORMATTABLE_MAX)
1365                 return -EINVAL;
1366
1367         usec++;
1368         t = (time_t) (usec / USEC_PER_SEC);
1369         assert_se(localtime_or_gmtime_r(&t, &tm, spec->utc));
1370         tm_usec = usec % USEC_PER_SEC;
1371
1372         r = find_next(spec, &tm, &tm_usec);
1373         if (r < 0)
1374                 return r;
1375
1376         t = mktime_or_timegm(&tm, spec->utc);
1377         if (t < 0)
1378                 return -EINVAL;
1379
1380         if (ret_next)
1381                 *ret_next = (usec_t) t * USEC_PER_SEC + tm_usec;
1382
1383         return 0;
1384 }
1385
1386 typedef struct SpecNextResult {
1387         usec_t next;
1388         int return_value;
1389 } SpecNextResult;
1390
1391 int calendar_spec_next_usec(const CalendarSpec *spec, usec_t usec, usec_t *ret_next) {
1392         SpecNextResult *shared, tmp;
1393         int r;
1394
1395         assert(spec);
1396
1397         if (isempty(spec->timezone))
1398                 return calendar_spec_next_usec_impl(spec, usec, ret_next);
1399
1400         shared = mmap(NULL, sizeof *shared, PROT_READ|PROT_WRITE, MAP_SHARED|MAP_ANONYMOUS, -1, 0);
1401         if (shared == MAP_FAILED)
1402                 return negative_errno();
1403
1404         r = safe_fork("(sd-calendar)", FORK_RESET_SIGNALS|FORK_CLOSE_ALL_FDS|FORK_DEATHSIG_SIGKILL|FORK_WAIT, NULL);
1405         if (r < 0) {
1406                 (void) munmap(shared, sizeof *shared);
1407                 return r;
1408         }
1409         if (r == 0) {
1410                 char *colon_tz;
1411
1412                 /* tzset(3) says $TZ should be prefixed with ":" if we reference timezone files */
1413                 colon_tz = strjoina(":", spec->timezone);
1414
1415                 if (setenv("TZ", colon_tz, 1) != 0) {
1416                         shared->return_value = negative_errno();
1417                         _exit(EXIT_FAILURE);
1418                 }
1419
1420                 tzset();
1421
1422                 shared->return_value = calendar_spec_next_usec_impl(spec, usec, &shared->next);
1423
1424                 _exit(EXIT_SUCCESS);
1425         }
1426
1427         tmp = *shared;
1428         if (munmap(shared, sizeof *shared) < 0)
1429                 return negative_errno();
1430
1431         if (tmp.return_value == 0 && ret_next)
1432                 *ret_next = tmp.next;
1433
1434         return tmp.return_value;
1435 }