src/shared/calendarspec.c

   1 /* SPDX-License-Identifier: LGPL-2.1+ */
   2
   3 #include <alloca.h>
   4 #include <ctype.h>
   5 #include <errno.h>
   6 #include <limits.h>
   7 #include <stddef.h>
   8 #include <stdio.h>
   9 #include <stdio_ext.h>
  10 #include <stdlib.h>
  11 #include <string.h>
  12 #include <sys/mman.h>
  13 #include <time.h>
  14
  15 #include "alloc-util.h"
  16 #include "calendarspec.h"
  17 #include "fileio.h"
  18 #include "macro.h"
  19 #include "parse-util.h"
  20 #include "process-util.h"
  21 #include "string-util.h"
  22 #include "time-util.h"
  23
  24 #define BITS_WEEKDAYS 127
  25 #define MIN_YEAR 1970
  26 #define MAX_YEAR 2199
  27
  28 /* An arbitrary limit on the length of the chains of components. We don't want to
  29  * build a very long linked list, which would be slow to iterate over and might cause
  30  * our stack to overflow. It's unlikely that legitimate uses require more than a few
  31  * linked compenents anyway. */
  32 #define CALENDARSPEC_COMPONENTS_MAX 240
  33
  34 static void free_chain(CalendarComponent *c) {
  35         CalendarComponent *n;
  36
  37         while (c) {
  38                 n = c->next;
  39                 free(c);
  40                 c = n;
  41         }
  42 }
  43
  44 CalendarSpec* calendar_spec_free(CalendarSpec *c) {
  45
  46         if (!c)
  47                 return NULL;
  48
  49         free_chain(c->year);
  50         free_chain(c->month);
  51         free_chain(c->day);
  52         free_chain(c->hour);
  53         free_chain(c->minute);
  54         free_chain(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(&buf, &sz);
 330         if (!f)
 331                 return -ENOMEM;
 332
 333         (void) __fsetlocking(f, FSETLOCKING_BYCALLER);
 334
 335         if (c->weekdays_bits > 0 && c->weekdays_bits <= BITS_WEEKDAYS) {
 336                 format_weekdays(f, c);
 337                 fputc(' ', f);
 338         }
 339
 340         format_chain(f, 4, c->year, false);
 341         fputc('-', f);
 342         format_chain(f, 2, c->month, false);
 343         fputc(c->end_of_month ? '~' : '-', f);
 344         format_chain(f, 2, c->day, false);
 345         fputc(' ', f);
 346         format_chain(f, 2, c->hour, false);
 347         fputc(':', f);
 348         format_chain(f, 2, c->minute, false);
 349         fputc(':', f);
 350         format_chain(f, 2, c->microsecond, true);
 351
 352         if (c->utc)
 353                 fputs(" UTC", f);
 354         else if (c->timezone != NULL) {
 355                 fputc(' ', f);
 356                 fputs(c->timezone, f);
 357         } else if (IN_SET(c->dst, 0, 1)) {
 358
 359                 /* If daylight saving is explicitly on or off, let's show the used timezone. */
 360
 361                 tzset();
 362
 363                 if (!isempty(tzname[c->dst])) {
 364                         fputc(' ', f);
 365                         fputs(tzname[c->dst], f);
 366                 }
 367         }
 368
 369         r = fflush_and_check(f);
 370         if (r < 0) {
 371                 free(buf);
 372                 fclose(f);
 373                 return r;
 374         }
 375
 376         fclose(f);
 377
 378         *p = buf;
 379         return 0;
 380 }
 381
 382 static int parse_weekdays(const char **p, CalendarSpec *c) {
 383         static const struct {
 384                 const char *name;
 385                 const int nr;
 386         } day_nr[] = {
 387                 { "Monday",    0 },
 388                 { "Mon",       0 },
 389                 { "Tuesday",   1 },
 390                 { "Tue",       1 },
 391                 { "Wednesday", 2 },
 392                 { "Wed",       2 },
 393                 { "Thursday",  3 },
 394                 { "Thu",       3 },
 395                 { "Friday",    4 },
 396                 { "Fri",       4 },
 397                 { "Saturday",  5 },
 398                 { "Sat",       5 },
 399                 { "Sunday",    6 },
 400                 { "Sun",       6 }
 401         };
 402
 403         int l = -1;
 404         bool first = true;
 405
 406         assert(p);
 407         assert(*p);
 408         assert(c);
 409
 410         for (;;) {
 411                 size_t i;
 412
 413                 for (i = 0; i < ELEMENTSOF(day_nr); i++) {
 414                         size_t skip;
 415
 416                         if (!startswith_no_case(*p, day_nr[i].name))
 417                                 continue;
 418
 419                         skip = strlen(day_nr[i].name);
 420
 421                         if (!IN_SET((*p)[skip], 0, '-', '.', ',', ' '))
 422                                 return -EINVAL;
 423
 424                         c->weekdays_bits |= 1 << day_nr[i].nr;
 425
 426                         if (l >= 0) {
 427                                 int j;
 428
 429                                 if (l > day_nr[i].nr)
 430                                         return -EINVAL;
 431
 432                                 for (j = l + 1; j < day_nr[i].nr; j++)
 433                                         c->weekdays_bits |= 1 << j;
 434                         }
 435
 436                         *p += skip;
 437                         break;
 438                 }
 439
 440                 /* Couldn't find this prefix, so let's assume the
 441                    weekday was not specified and let's continue with
 442                    the date */
 443                 if (i >= ELEMENTSOF(day_nr))
 444                         return first ? 0 : -EINVAL;
 445
 446                 /* We reached the end of the string */
 447                 if (**p == 0)
 448                         return 0;
 449
 450                 /* We reached the end of the weekday spec part */
 451                 if (**p == ' ') {
 452                         *p += strspn(*p, " ");
 453                         return 0;
 454                 }
 455
 456                 if (**p == '.') {
 457                         if (l >= 0)
 458                                 return -EINVAL;
 459
 460                         if ((*p)[1] != '.')
 461                                 return -EINVAL;
 462
 463                         l = day_nr[i].nr;
 464                         *p += 2;
 465
 466                 /* Support ranges with "-" for backwards compatibility */
 467                 } else if (**p == '-') {
 468                         if (l >= 0)
 469                                 return -EINVAL;
 470
 471                         l = day_nr[i].nr;
 472                         *p += 1;
 473
 474                 } else if (**p == ',') {
 475                         l = -1;
 476                         *p += 1;
 477                 }
 478
 479                 /* Allow a trailing comma but not an open range */
 480                 if (IN_SET(**p, 0, ' ')) {
 481                         *p += strspn(*p, " ");
 482                         return l < 0 ? 0 : -EINVAL;
 483                 }
 484
 485                 first = false;
 486         }
 487 }
 488
 489 static int parse_one_number(const char *p, const char **e, unsigned long *ret) {
 490         char *ee = NULL;
 491         unsigned long value;
 492
 493         errno = 0;
 494         value = strtoul(p, &ee, 10);
 495         if (errno > 0)
 496                 return -errno;
 497         if (ee == p)
 498                 return -EINVAL;
 499
 500         *ret = value;
 501         *e = ee;
 502         return 0;
 503 }
 504
 505 static int parse_component_decimal(const char **p, bool usec, int *res) {
 506         unsigned long value;
 507         const char *e = NULL;
 508         int r;
 509
 510         if (!isdigit(**p))
 511                 return -EINVAL;
 512
 513         r = parse_one_number(*p, &e, &value);
 514         if (r < 0)
 515                 return r;
 516
 517         if (usec) {
 518                 if (value * USEC_PER_SEC / USEC_PER_SEC != value)
 519                         return -ERANGE;
 520
 521                 value *= USEC_PER_SEC;
 522
 523                 /* One "." is a decimal point, but ".." is a range separator */
 524                 if (e[0] == '.' && e[1] != '.') {
 525                         unsigned add;
 526
 527                         e++;
 528                         r = parse_fractional_part_u(&e, 6, &add);
 529                         if (r < 0)
 530                                 return r;
 531
 532                         if (add + value < value)
 533                                 return -ERANGE;
 534                         value += add;
 535                 }
 536         }
 537
 538         if (value > INT_MAX)
 539                 return -ERANGE;
 540
 541         *p = e;
 542         *res = value;
 543
 544         return 0;
 545 }
 546
 547 static int const_chain(int value, CalendarComponent **c) {
 548         CalendarComponent *cc = NULL;
 549
 550         assert(c);
 551
 552         cc = new0(CalendarComponent, 1);
 553         if (!cc)
 554                 return -ENOMEM;
 555
 556         cc->start = value;
 557         cc->stop = -1;
 558         cc->repeat = 0;
 559         cc->next = *c;
 560
 561         *c = cc;
 562
 563         return 0;
 564 }
 565
 566 static int calendarspec_from_time_t(CalendarSpec *c, time_t time) {
 567         struct tm tm;
 568         CalendarComponent *year = NULL, *month = NULL, *day = NULL, *hour = NULL, *minute = NULL, *us = NULL;
 569         int r;
 570
 571         if (!gmtime_r(&time, &tm))
 572                 return -ERANGE;
 573
 574         r = const_chain(tm.tm_year + 1900, &year);
 575         if (r < 0)
 576                 return r;
 577
 578         r = const_chain(tm.tm_mon + 1, &month);
 579         if (r < 0)
 580                 return r;
 581
 582         r = const_chain(tm.tm_mday, &day);
 583         if (r < 0)
 584                 return r;
 585
 586         r = const_chain(tm.tm_hour, &hour);
 587         if (r < 0)
 588                 return r;
 589
 590         r = const_chain(tm.tm_min, &minute);
 591         if (r < 0)
 592                 return r;
 593
 594         r = const_chain(tm.tm_sec * USEC_PER_SEC, &us);
 595         if (r < 0)
 596                 return r;
 597
 598         c->utc = true;
 599         c->year = year;
 600         c->month = month;
 601         c->day = day;
 602         c->hour = hour;
 603         c->minute = minute;
 604         c->microsecond = us;
 605         return 0;
 606 }
 607
 608 static int prepend_component(const char **p, bool usec, unsigned nesting, CalendarComponent **c) {
 609         int r, start, stop = -1, repeat = 0;
 610         CalendarComponent *cc;
 611         const char *e = *p;
 612
 613         assert(p);
 614         assert(c);
 615
 616         if (nesting > CALENDARSPEC_COMPONENTS_MAX)
 617                 return -ENOBUFS;
 618
 619         r = parse_component_decimal(&e, usec, &start);
 620         if (r < 0)
 621                 return r;
 622
 623         if (e[0] == '.' && e[1] == '.') {
 624                 e += 2;
 625                 r = parse_component_decimal(&e, usec, &stop);
 626                 if (r < 0)
 627                         return r;
 628
 629                 repeat = usec ? USEC_PER_SEC : 1;
 630         }
 631
 632         if (*e == '/') {
 633                 e++;
 634                 r = parse_component_decimal(&e, usec, &repeat);
 635                 if (r < 0)
 636                         return r;
 637
 638                 if (repeat == 0)
 639                         return -ERANGE;
 640         }
 641
 642         if (!IN_SET(*e, 0, ' ', ',', '-', '~', ':'))
 643                 return -EINVAL;
 644
 645         cc = new0(CalendarComponent, 1);
 646         if (!cc)
 647                 return -ENOMEM;
 648
 649         cc->start = start;
 650         cc->stop = stop;
 651         cc->repeat = repeat;
 652         cc->next = *c;
 653
 654         *p = e;
 655         *c = cc;
 656
 657         if (*e ==',') {
 658                 *p += 1;
 659                 return prepend_component(p, usec, nesting + 1, c);
 660         }
 661
 662         return 0;
 663 }
 664
 665 static int parse_chain(const char **p, bool usec, CalendarComponent **c) {
 666         const char *t;
 667         CalendarComponent *cc = NULL;
 668         int r;
 669
 670         assert(p);
 671         assert(c);
 672
 673         t = *p;
 674
 675         if (t[0] == '*') {
 676                 if (usec) {
 677                         r = const_chain(0, c);
 678                         if (r < 0)
 679                                 return r;
 680                         (*c)->repeat = USEC_PER_SEC;
 681                 } else
 682                         *c = NULL;
 683
 684                 *p = t + 1;
 685                 return 0;
 686         }
 687
 688         r = prepend_component(&t, usec, 0, &cc);
 689         if (r < 0) {
 690                 free_chain(cc);
 691                 return r;
 692         }
 693
 694         *p = t;
 695         *c = cc;
 696         return 0;
 697 }
 698
 699 static int parse_date(const char **p, CalendarSpec *c) {
 700         const char *t;
 701         int r;
 702         CalendarComponent *first, *second, *third;
 703
 704         assert(p);
 705         assert(*p);
 706         assert(c);
 707
 708         t = *p;
 709
 710         if (*t == 0)
 711                 return 0;
 712
 713         /* @TIMESTAMP — UNIX time in seconds since the epoch */
 714         if (*t == '@') {
 715                 unsigned long value;
 716                 time_t time;
 717
 718                 r = parse_one_number(t + 1, &t, &value);
 719                 if (r < 0)
 720                         return r;
 721
 722                 time = value;
 723                 if ((unsigned long) time != value)
 724                         return -ERANGE;
 725
 726                 r = calendarspec_from_time_t(c, time);
 727                 if (r < 0)
 728                         return r;
 729
 730                 *p = t;
 731                 return 1; /* finito, don't parse H:M:S after that */
 732         }
 733
 734         r = parse_chain(&t, false, &first);
 735         if (r < 0)
 736                 return r;
 737
 738         /* Already the end? A ':' as separator? In that case this was a time, not a date */
 739         if (IN_SET(*t, 0, ':')) {
 740                 free_chain(first);
 741                 return 0;
 742         }
 743
 744         if (*t == '~')
 745                 c->end_of_month = true;
 746         else if (*t != '-') {
 747                 free_chain(first);
 748                 return -EINVAL;
 749         }
 750
 751         t++;
 752         r = parse_chain(&t, false, &second);
 753         if (r < 0) {
 754                 free_chain(first);
 755                 return r;
 756         }
 757
 758         /* Got two parts, hence it's month and day */
 759         if (IN_SET(*t, 0, ' ')) {
 760                 *p = t + strspn(t, " ");
 761                 c->month = first;
 762                 c->day = second;
 763                 return 0;
 764         } else if (c->end_of_month) {
 765                 free_chain(first);
 766                 free_chain(second);
 767                 return -EINVAL;
 768         }
 769
 770         if (*t == '~')
 771                 c->end_of_month = true;
 772         else if (*t != '-') {
 773                 free_chain(first);
 774                 free_chain(second);
 775                 return -EINVAL;
 776         }
 777
 778         t++;
 779         r = parse_chain(&t, false, &third);
 780         if (r < 0) {
 781                 free_chain(first);
 782                 free_chain(second);
 783                 return r;
 784         }
 785
 786         /* Got three parts, hence it is year, month and day */
 787         if (IN_SET(*t, 0, ' ')) {
 788                 *p = t + strspn(t, " ");
 789                 c->year = first;
 790                 c->month = second;
 791                 c->day = third;
 792                 return 0;
 793         }
 794
 795         free_chain(first);
 796         free_chain(second);
 797         free_chain(third);
 798         return -EINVAL;
 799 }
 800
 801 static int parse_calendar_time(const char **p, CalendarSpec *c) {
 802         CalendarComponent *h = NULL, *m = NULL, *s = NULL;
 803         const char *t;
 804         int r;
 805
 806         assert(p);
 807         assert(*p);
 808         assert(c);
 809
 810         t = *p;
 811
 812         /* If no time is specified at all, then this means 00:00:00 */
 813         if (*t == 0)
 814                 goto null_hour;
 815
 816         r = parse_chain(&t, false, &h);
 817         if (r < 0)
 818                 goto fail;
 819
 820         if (*t != ':') {
 821                 r = -EINVAL;
 822                 goto fail;
 823         }
 824
 825         t++;
 826         r = parse_chain(&t, false, &m);
 827         if (r < 0)
 828                 goto fail;
 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                 r = -EINVAL;
 836                 goto fail;
 837         }
 838
 839         t++;
 840         r = parse_chain(&t, true, &s);
 841         if (r < 0)
 842                 goto fail;
 843
 844         /* At the end? Then it's hours, minutes and seconds */
 845         if (*t == 0)
 846                 goto finish;
 847
 848         r = -EINVAL;
 849         goto fail;
 850
 851 null_hour:
 852         r = const_chain(0, &h);
 853         if (r < 0)
 854                 goto fail;
 855
 856         r = const_chain(0, &m);
 857         if (r < 0)
 858                 goto fail;
 859
 860 null_second:
 861         r = const_chain(0, &s);
 862         if (r < 0)
 863                 goto fail;
 864
 865 finish:
 866         *p = t;
 867         c->hour = h;
 868         c->minute = m;
 869         c->microsecond = s;
 870
 871         return 0;
 872
 873 fail:
 874         free_chain(h);
 875         free_chain(m);
 876         free_chain(s);
 877         return r;
 878 }
 879
 880 int calendar_spec_from_string(const char *p, CalendarSpec **spec) {
 881         const char *utc;
 882         _cleanup_(calendar_spec_freep) CalendarSpec *c = NULL;
 883         int r;
 884
 885         assert(p);
 886         assert(spec);
 887
 888         c = new0(CalendarSpec, 1);
 889         if (!c)
 890                 return -ENOMEM;
 891         c->dst = -1;
 892         c->timezone = NULL;
 893
 894         utc = endswith_no_case(p, " UTC");
 895         if (utc) {
 896                 c->utc = true;
 897                 p = strndupa(p, utc - p);
 898         } else {
 899                 const char *e = NULL;
 900                 int j;
 901
 902                 tzset();
 903
 904                 /* Check if the local timezone was specified? */
 905                 for (j = 0; j <= 1; j++) {
 906                         if (isempty(tzname[j]))
 907                                 continue;
 908
 909                         e = endswith_no_case(p, tzname[j]);
 910                         if (!e)
 911                                 continue;
 912                         if (e == p)
 913                                 continue;
 914                         if (e[-1] != ' ')
 915                                 continue;
 916
 917                         break;
 918                 }
 919
 920                 /* Found one of the two timezones specified? */
 921                 if (IN_SET(j, 0, 1)) {
 922                         p = strndupa(p, e - p - 1);
 923                         c->dst = j;
 924                 } else {
 925                         const char *last_space;
 926
 927                         last_space = strrchr(p, ' ');
 928                         if (last_space != NULL && timezone_is_valid(last_space + 1, LOG_DEBUG)) {
 929                                 c->timezone = strdup(last_space + 1);
 930                                 if (!c->timezone)
 931                                         return -ENOMEM;
 932
 933                                 p = strndupa(p, last_space - p);
 934                         }
 935                 }
 936         }
 937
 938         if (isempty(p))
 939                 return -EINVAL;
 940
 941         if (strcaseeq(p, "minutely")) {
 942                 r = const_chain(0, &c->microsecond);
 943                 if (r < 0)
 944                         return r;
 945
 946         } else if (strcaseeq(p, "hourly")) {
 947                 r = const_chain(0, &c->minute);
 948                 if (r < 0)
 949                         return r;
 950                 r = const_chain(0, &c->microsecond);
 951                 if (r < 0)
 952                         return r;
 953
 954         } else if (strcaseeq(p, "daily")) {
 955                 r = const_chain(0, &c->hour);
 956                 if (r < 0)
 957                         return r;
 958                 r = const_chain(0, &c->minute);
 959                 if (r < 0)
 960                         return r;
 961                 r = const_chain(0, &c->microsecond);
 962                 if (r < 0)
 963                         return r;
 964
 965         } else if (strcaseeq(p, "monthly")) {
 966                 r = const_chain(1, &c->day);
 967                 if (r < 0)
 968                         return r;
 969                 r = const_chain(0, &c->hour);
 970                 if (r < 0)
 971                         return r;
 972                 r = const_chain(0, &c->minute);
 973                 if (r < 0)
 974                         return r;
 975                 r = const_chain(0, &c->microsecond);
 976                 if (r < 0)
 977                         return r;
 978
 979         } else if (strcaseeq(p, "annually") ||
 980                    strcaseeq(p, "yearly") ||
 981                    strcaseeq(p, "anually") /* backwards compatibility */ ) {
 982
 983                 r = const_chain(1, &c->month);
 984                 if (r < 0)
 985                         return r;
 986                 r = const_chain(1, &c->day);
 987                 if (r < 0)
 988                         return r;
 989                 r = const_chain(0, &c->hour);
 990                 if (r < 0)
 991                         return r;
 992                 r = const_chain(0, &c->minute);
 993                 if (r < 0)
 994                         return r;
 995                 r = const_chain(0, &c->microsecond);
 996                 if (r < 0)
 997                         return r;
 998
 999         } else if (strcaseeq(p, "weekly")) {
1000
1001                 c->weekdays_bits = 1;
1002
1003                 r = const_chain(0, &c->hour);
1004                 if (r < 0)
1005                         return r;
1006                 r = const_chain(0, &c->minute);
1007                 if (r < 0)
1008                         return r;
1009                 r = const_chain(0, &c->microsecond);
1010                 if (r < 0)
1011                         return r;
1012
1013         } else if (strcaseeq(p, "quarterly")) {
1014
1015                 r = const_chain(1, &c->month);
1016                 if (r < 0)
1017                         return r;
1018                 r = const_chain(4, &c->month);
1019                 if (r < 0)
1020                         return r;
1021                 r = const_chain(7, &c->month);
1022                 if (r < 0)
1023                         return r;
1024                 r = const_chain(10, &c->month);
1025                 if (r < 0)
1026                         return r;
1027                 r = const_chain(1, &c->day);
1028                 if (r < 0)
1029                         return r;
1030                 r = const_chain(0, &c->hour);
1031                 if (r < 0)
1032                         return r;
1033                 r = const_chain(0, &c->minute);
1034                 if (r < 0)
1035                         return r;
1036                 r = const_chain(0, &c->microsecond);
1037                 if (r < 0)
1038                         return r;
1039
1040         } else if (strcaseeq(p, "biannually") ||
1041                    strcaseeq(p, "bi-annually") ||
1042                    strcaseeq(p, "semiannually") ||
1043                    strcaseeq(p, "semi-annually")) {
1044
1045                 r = const_chain(1, &c->month);
1046                 if (r < 0)
1047                         return r;
1048                 r = const_chain(7, &c->month);
1049                 if (r < 0)
1050                         return r;
1051                 r = const_chain(1, &c->day);
1052                 if (r < 0)
1053                         return r;
1054                 r = const_chain(0, &c->hour);
1055                 if (r < 0)
1056                         return r;
1057                 r = const_chain(0, &c->minute);
1058                 if (r < 0)
1059                         return r;
1060                 r = const_chain(0, &c->microsecond);
1061                 if (r < 0)
1062                         return r;
1063
1064         } else {
1065                 r = parse_weekdays(&p, c);
1066                 if (r < 0)
1067                         return r;
1068
1069                 r = parse_date(&p, c);
1070                 if (r < 0)
1071                         return r;
1072
1073                 if (r == 0) {
1074                         r = parse_calendar_time(&p, c);
1075                         if (r < 0)
1076                                 return r;
1077                 }
1078
1079                 if (*p != 0)
1080                         return -EINVAL;
1081         }
1082
1083         r = calendar_spec_normalize(c);
1084         if (r < 0)
1085                 return r;
1086
1087         if (!calendar_spec_valid(c))
1088                 return -EINVAL;
1089
1090         *spec = TAKE_PTR(c);
1091         return 0;
1092 }
1093
1094 static int find_end_of_month(struct tm *tm, bool utc, int day) {
1095         struct tm t = *tm;
1096
1097         t.tm_mon++;
1098         t.tm_mday = 1 - day;
1099
1100         if (mktime_or_timegm(&t, utc) < 0 ||
1101             t.tm_mon != tm->tm_mon)
1102                 return -1;
1103
1104         return t.tm_mday;
1105 }
1106
1107 static int find_matching_component(const CalendarSpec *spec, const CalendarComponent *c,
1108                                    struct tm *tm, int *val) {
1109         const CalendarComponent *p = c;
1110         int start, stop, d = -1;
1111         bool d_set = false;
1112         int r;
1113
1114         assert(val);
1115
1116         if (!c)
1117                 return 0;
1118
1119         while (c) {
1120                 start = c->start;
1121                 stop = c->stop;
1122
1123                 if (spec->end_of_month && p == spec->day) {
1124                         start = find_end_of_month(tm, spec->utc, start);
1125                         stop = find_end_of_month(tm, spec->utc, stop);
1126
1127                         if (stop > 0)
1128                                 SWAP_TWO(start, stop);
1129                 }
1130
1131                 if (start >= *val) {
1132
1133                         if (!d_set || start < d) {
1134                                 d = start;
1135                                 d_set = true;
1136                         }
1137
1138                 } else if (c->repeat > 0) {
1139                         int k;
1140
1141                         k = start + c->repeat * DIV_ROUND_UP(*val - start, c->repeat);
1142
1143                         if ((!d_set || k < d) && (stop < 0 || k <= stop)) {
1144                                 d = k;
1145                                 d_set = true;
1146                         }
1147                 }
1148
1149                 c = c->next;
1150         }
1151
1152         if (!d_set)
1153                 return -ENOENT;
1154
1155         r = *val != d;
1156         *val = d;
1157         return r;
1158 }
1159
1160 static bool tm_out_of_bounds(const struct tm *tm, bool utc) {
1161         struct tm t;
1162         assert(tm);
1163
1164         t = *tm;
1165
1166         if (mktime_or_timegm(&t, utc) < 0)
1167                 return true;
1168
1169         /*
1170          * Set an upper bound on the year so impossible dates like "*-02-31"
1171          * don't cause find_next() to loop forever. tm_year contains years
1172          * since 1900, so adjust it accordingly.
1173          */
1174         if (tm->tm_year + 1900 > MAX_YEAR)
1175                 return true;
1176
1177         /* Did any normalization take place? If so, it was out of bounds before */
1178         return
1179                 t.tm_year != tm->tm_year ||
1180                 t.tm_mon != tm->tm_mon ||
1181                 t.tm_mday != tm->tm_mday ||
1182                 t.tm_hour != tm->tm_hour ||
1183                 t.tm_min != tm->tm_min ||
1184                 t.tm_sec != tm->tm_sec;
1185 }
1186
1187 static bool matches_weekday(int weekdays_bits, const struct tm *tm, bool utc) {
1188         struct tm t;
1189         int k;
1190
1191         if (weekdays_bits < 0 || weekdays_bits >= BITS_WEEKDAYS)
1192                 return true;
1193
1194         t = *tm;
1195         if (mktime_or_timegm(&t, utc) < 0)
1196                 return false;
1197
1198         k = t.tm_wday == 0 ? 6 : t.tm_wday - 1;
1199         return (weekdays_bits & (1 << k));
1200 }
1201
1202 static int find_next(const CalendarSpec *spec, struct tm *tm, usec_t *usec) {
1203         struct tm c;
1204         int tm_usec;
1205         int r;
1206
1207         assert(spec);
1208         assert(tm);
1209
1210         c = *tm;
1211         tm_usec = *usec;
1212
1213         for (;;) {
1214                 /* Normalize the current date */
1215                 (void) mktime_or_timegm(&c, spec->utc);
1216                 c.tm_isdst = spec->dst;
1217
1218                 c.tm_year += 1900;
1219                 r = find_matching_component(spec, spec->year, &c, &c.tm_year);
1220                 c.tm_year -= 1900;
1221
1222                 if (r > 0) {
1223                         c.tm_mon = 0;
1224                         c.tm_mday = 1;
1225                         c.tm_hour = c.tm_min = c.tm_sec = tm_usec = 0;
1226                 }
1227                 if (r < 0)
1228                         return r;
1229                 if (tm_out_of_bounds(&c, spec->utc))
1230                         return -ENOENT;
1231
1232                 c.tm_mon += 1;
1233                 r = find_matching_component(spec, spec->month, &c, &c.tm_mon);
1234                 c.tm_mon -= 1;
1235
1236                 if (r > 0) {
1237                         c.tm_mday = 1;
1238                         c.tm_hour = c.tm_min = c.tm_sec = tm_usec = 0;
1239                 }
1240                 if (r < 0 || tm_out_of_bounds(&c, spec->utc)) {
1241                         c.tm_year++;
1242                         c.tm_mon = 0;
1243                         c.tm_mday = 1;
1244                         c.tm_hour = c.tm_min = c.tm_sec = tm_usec = 0;
1245                         continue;
1246                 }
1247
1248                 r = find_matching_component(spec, spec->day, &c, &c.tm_mday);
1249                 if (r > 0)
1250                         c.tm_hour = c.tm_min = c.tm_sec = tm_usec = 0;
1251                 if (r < 0 || tm_out_of_bounds(&c, spec->utc)) {
1252                         c.tm_mon++;
1253                         c.tm_mday = 1;
1254                         c.tm_hour = c.tm_min = c.tm_sec = tm_usec = 0;
1255                         continue;
1256                 }
1257
1258                 if (!matches_weekday(spec->weekdays_bits, &c, spec->utc)) {
1259                         c.tm_mday++;
1260                         c.tm_hour = c.tm_min = c.tm_sec = tm_usec = 0;
1261                         continue;
1262                 }
1263
1264                 r = find_matching_component(spec, spec->hour, &c, &c.tm_hour);
1265                 if (r > 0)
1266                         c.tm_min = c.tm_sec = tm_usec = 0;
1267                 if (r < 0 || tm_out_of_bounds(&c, spec->utc)) {
1268                         c.tm_mday++;
1269                         c.tm_hour = c.tm_min = c.tm_sec = tm_usec = 0;
1270                         continue;
1271                 }
1272
1273                 r = find_matching_component(spec, spec->minute, &c, &c.tm_min);
1274                 if (r > 0)
1275                         c.tm_sec = tm_usec = 0;
1276                 if (r < 0 || tm_out_of_bounds(&c, spec->utc)) {
1277                         c.tm_hour++;
1278                         c.tm_min = c.tm_sec = tm_usec = 0;
1279                         continue;
1280                 }
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 || tm_out_of_bounds(&c, spec->utc)) {
1288                         c.tm_min++;
1289                         c.tm_sec = tm_usec = 0;
1290                         continue;
1291                 }
1292
1293                 *tm = c;
1294                 *usec = tm_usec;
1295                 return 0;
1296         }
1297 }
1298
1299 static int calendar_spec_next_usec_impl(const CalendarSpec *spec, usec_t usec, usec_t *next) {
1300         struct tm tm;
1301         time_t t;
1302         int r;
1303         usec_t tm_usec;
1304
1305         assert(spec);
1306         assert(next);
1307
1308         if (usec > USEC_TIMESTAMP_FORMATTABLE_MAX)
1309                 return -EINVAL;
1310
1311         usec++;
1312         t = (time_t) (usec / USEC_PER_SEC);
1313         assert_se(localtime_or_gmtime_r(&t, &tm, spec->utc));
1314         tm_usec = usec % USEC_PER_SEC;
1315
1316         r = find_next(spec, &tm, &tm_usec);
1317         if (r < 0)
1318                 return r;
1319
1320         t = mktime_or_timegm(&tm, spec->utc);
1321         if (t < 0)
1322                 return -EINVAL;
1323
1324         *next = (usec_t) t * USEC_PER_SEC + tm_usec;
1325         return 0;
1326 }
1327
1328 typedef struct SpecNextResult {
1329         usec_t next;
1330         int return_value;
1331 } SpecNextResult;
1332
1333 int calendar_spec_next_usec(const CalendarSpec *spec, usec_t usec, usec_t *next) {
1334         SpecNextResult *shared, tmp;
1335         int r;
1336
1337         if (isempty(spec->timezone))
1338                 return calendar_spec_next_usec_impl(spec, usec, next);
1339
1340         shared = mmap(NULL, sizeof *shared, PROT_READ|PROT_WRITE, MAP_SHARED|MAP_ANONYMOUS, -1, 0);
1341         if (shared == MAP_FAILED)
1342                 return negative_errno();
1343
1344         r = safe_fork("(sd-calendar)", FORK_RESET_SIGNALS|FORK_CLOSE_ALL_FDS|FORK_DEATHSIG|FORK_WAIT, NULL);
1345         if (r < 0) {
1346                 (void) munmap(shared, sizeof *shared);
1347                 return r;
1348         }
1349         if (r == 0) {
1350                 if (setenv("TZ", spec->timezone, 1) != 0) {
1351                         shared->return_value = negative_errno();
1352                         _exit(EXIT_FAILURE);
1353                 }
1354
1355                 tzset();
1356
1357                 shared->return_value = calendar_spec_next_usec_impl(spec, usec, &shared->next);
1358
1359                 _exit(EXIT_SUCCESS);
1360         }
1361
1362         tmp = *shared;
1363         if (munmap(shared, sizeof *shared) < 0)
1364                 return negative_errno();
1365
1366         if (tmp.return_value == 0)
1367                 *next = tmp.next;
1368
1369         return tmp.return_value;
1370 }