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