src/shared/calendarspec.c

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