src/basic/calendarspec.c

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