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