1 /* $NetBSD: subr_time.c,v 1.36 2023/04/09 09:18:09 riastradh Exp $ */ 2 3 /* 4 * Copyright (c) 1982, 1986, 1989, 1993 5 * The Regents of the University of California. All rights reserved. 6 * 7 * Redistribution and use in source and binary forms, with or without 8 * modification, are permitted provided that the following conditions 9 * are met: 10 * 1. Redistributions of source code must retain the above copyright 11 * notice, this list of conditions and the following disclaimer. 12 * 2. Redistributions in binary form must reproduce the above copyright 13 * notice, this list of conditions and the following disclaimer in the 14 * documentation and/or other materials provided with the distribution. 15 * 3. Neither the name of the University nor the names of its contributors 16 * may be used to endorse or promote products derived from this software 17 * without specific prior written permission. 18 * 19 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 20 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 21 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 22 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 23 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 24 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 25 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 26 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 27 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 28 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 29 * SUCH DAMAGE. 30 * 31 * @(#)kern_clock.c 8.5 (Berkeley) 1/21/94 32 * @(#)kern_time.c 8.4 (Berkeley) 5/26/95 33 */ 34 35 #include <sys/cdefs.h> 36 __KERNEL_RCSID(0, "$NetBSD: subr_time.c,v 1.36 2023/04/09 09:18:09 riastradh Exp $"); 37 38 #include <sys/param.h> 39 #include <sys/kernel.h> 40 #include <sys/proc.h> 41 #include <sys/kauth.h> 42 #include <sys/lwp.h> 43 #include <sys/timex.h> 44 #include <sys/time.h> 45 #include <sys/timetc.h> 46 #include <sys/intr.h> 47 48 #ifdef DEBUG_STICKS 49 #define DPRINTF(a) uprintf a 50 #else 51 #define DPRINTF(a) 52 #endif 53 54 /* 55 * Compute number of hz until specified time. Used to compute second 56 * argument to callout_reset() from an absolute time. 57 */ 58 int 59 tvhzto(const struct timeval *tvp) 60 { 61 struct timeval now, tv; 62 63 tv = *tvp; /* Don't modify original tvp. */ 64 getmicrotime(&now); 65 timersub(&tv, &now, &tv); 66 return tvtohz(&tv); 67 } 68 69 /* 70 * Compute number of ticks in the specified amount of time. 71 */ 72 int 73 tvtohz(const struct timeval *tv) 74 { 75 unsigned long ticks; 76 long sec, usec; 77 78 /* 79 * If the number of usecs in the whole seconds part of the time 80 * difference fits in a long, then the total number of usecs will 81 * fit in an unsigned long. Compute the total and convert it to 82 * ticks, rounding up and adding 1 to allow for the current tick 83 * to expire. Rounding also depends on unsigned long arithmetic 84 * to avoid overflow. 85 * 86 * Otherwise, if the number of ticks in the whole seconds part of 87 * the time difference fits in a long, then convert the parts to 88 * ticks separately and add, using similar rounding methods and 89 * overflow avoidance. This method would work in the previous 90 * case, but it is slightly slower and assumes that hz is integral. 91 * 92 * Otherwise, round the time difference down to the maximum 93 * representable value. 94 * 95 * If ints are 32-bit, then the maximum value for any timeout in 96 * 10ms ticks is 248 days. 97 */ 98 sec = tv->tv_sec; 99 usec = tv->tv_usec; 100 101 KASSERT(usec >= 0); 102 KASSERT(usec < 1000000); 103 104 /* catch overflows in conversion time_t->int */ 105 if (tv->tv_sec > INT_MAX) 106 return INT_MAX; 107 if (tv->tv_sec < 0) 108 return 0; 109 110 if (sec < 0 || (sec == 0 && usec == 0)) { 111 /* 112 * Would expire now or in the past. Return 0 ticks. 113 * This is different from the legacy tvhzto() interface, 114 * and callers need to check for it. 115 */ 116 ticks = 0; 117 } else if (sec <= (LONG_MAX / 1000000)) 118 ticks = (((sec * 1000000) + (unsigned long)usec + (tick - 1)) 119 / tick) + 1; 120 else if (sec <= (LONG_MAX / hz)) 121 ticks = (sec * hz) + 122 (((unsigned long)usec + (tick - 1)) / tick) + 1; 123 else 124 ticks = LONG_MAX; 125 126 if (ticks > INT_MAX) 127 ticks = INT_MAX; 128 129 return ((int)ticks); 130 } 131 132 int 133 tshzto(const struct timespec *tsp) 134 { 135 struct timespec now, ts; 136 137 ts = *tsp; /* Don't modify original tsp. */ 138 getnanotime(&now); 139 timespecsub(&ts, &now, &ts); 140 return tstohz(&ts); 141 } 142 143 int 144 tshztoup(const struct timespec *tsp) 145 { 146 struct timespec now, ts; 147 148 ts = *tsp; /* Don't modify original tsp. */ 149 getnanouptime(&now); 150 timespecsub(&ts, &now, &ts); 151 return tstohz(&ts); 152 } 153 154 /* 155 * Compute number of ticks in the specified amount of time. 156 */ 157 int 158 tstohz(const struct timespec *ts) 159 { 160 struct timeval tv; 161 162 /* 163 * usec has great enough resolution for hz, so convert to a 164 * timeval and use tvtohz() above. 165 */ 166 TIMESPEC_TO_TIMEVAL(&tv, ts); 167 return tvtohz(&tv); 168 } 169 170 /* 171 * Check that a proposed value to load into the .it_value or 172 * .it_interval part of an interval timer is acceptable, and 173 * fix it to have at least minimal value (i.e. if it is less 174 * than the resolution of the clock, round it up.). We don't 175 * timeout the 0,0 value because this means to disable the 176 * timer or the interval. 177 */ 178 int 179 itimerfix(struct timeval *tv) 180 { 181 182 if (tv->tv_usec < 0 || tv->tv_usec >= 1000000) 183 return EINVAL; 184 if (tv->tv_sec < 0) 185 return ETIMEDOUT; 186 if (tv->tv_sec == 0 && tv->tv_usec != 0 && tv->tv_usec < tick) 187 tv->tv_usec = tick; 188 return 0; 189 } 190 191 int 192 itimespecfix(struct timespec *ts) 193 { 194 195 if (ts->tv_nsec < 0 || ts->tv_nsec >= 1000000000) 196 return EINVAL; 197 if (ts->tv_sec < 0) 198 return ETIMEDOUT; 199 if (ts->tv_sec == 0 && ts->tv_nsec != 0 && ts->tv_nsec < tick * 1000) 200 ts->tv_nsec = tick * 1000; 201 return 0; 202 } 203 204 int 205 inittimeleft(struct timespec *ts, struct timespec *sleepts) 206 { 207 208 if (itimespecfix(ts)) { 209 return -1; 210 } 211 KASSERT(ts->tv_sec >= 0); 212 getnanouptime(sleepts); 213 return 0; 214 } 215 216 int 217 gettimeleft(struct timespec *ts, struct timespec *sleepts) 218 { 219 struct timespec now, sleptts; 220 221 KASSERT(ts->tv_sec >= 0); 222 223 /* 224 * Reduce ts by elapsed time based on monotonic time scale. 225 */ 226 getnanouptime(&now); 227 KASSERT(timespeccmp(sleepts, &now, <=)); 228 timespecsub(&now, sleepts, &sleptts); 229 *sleepts = now; 230 231 if (timespeccmp(ts, &sleptts, <=)) { /* timed out */ 232 timespecclear(ts); 233 return 0; 234 } 235 timespecsub(ts, &sleptts, ts); 236 237 return tstohz(ts); 238 } 239 240 void 241 clock_timeleft(clockid_t clockid, struct timespec *ts, struct timespec *sleepts) 242 { 243 struct timespec sleptts; 244 245 clock_gettime1(clockid, &sleptts); 246 timespecadd(ts, sleepts, ts); 247 timespecsub(ts, &sleptts, ts); 248 *sleepts = sleptts; 249 } 250 251 static void 252 ticks2ts(uint64_t ticks, struct timespec *ts) 253 { 254 ts->tv_sec = ticks / hz; 255 uint64_t sticks = ticks - ts->tv_sec * hz; 256 if (sticks > BINTIME_SCALE_MS) /* floor(2^64 / 1000) */ 257 ts->tv_nsec = sticks / hz * 1000000000LL; 258 else if (sticks > BINTIME_SCALE_US) /* floor(2^64 / 1000000) */ 259 ts->tv_nsec = sticks * 1000LL / hz * 1000000LL; 260 else 261 ts->tv_nsec = sticks * 1000000000LL / hz; 262 DPRINTF(("%s: %ju/%ju -> %ju.%ju\n", __func__, 263 (uintmax_t)ticks, (uintmax_t)sticks, 264 (uintmax_t)ts->tv_sec, (uintmax_t)ts->tv_nsec)); 265 } 266 267 int 268 clock_gettime1(clockid_t clock_id, struct timespec *ts) 269 { 270 int error; 271 uint64_t ticks; 272 struct proc *p; 273 274 #define CPUCLOCK_ID_MASK (~(CLOCK_THREAD_CPUTIME_ID|CLOCK_PROCESS_CPUTIME_ID)) 275 if (clock_id & CLOCK_PROCESS_CPUTIME_ID) { 276 pid_t pid = clock_id & CPUCLOCK_ID_MASK; 277 278 mutex_enter(&proc_lock); 279 p = pid == 0 ? curproc : proc_find(pid); 280 if (p == NULL) { 281 mutex_exit(&proc_lock); 282 return ESRCH; 283 } 284 ticks = p->p_uticks + p->p_sticks + p->p_iticks; 285 DPRINTF(("%s: u=%ju, s=%ju, i=%ju\n", __func__, 286 (uintmax_t)p->p_uticks, (uintmax_t)p->p_sticks, 287 (uintmax_t)p->p_iticks)); 288 mutex_exit(&proc_lock); 289 290 // XXX: Perhaps create a special kauth type 291 error = kauth_authorize_process(kauth_cred_get(), 292 KAUTH_PROCESS_PTRACE, p, 293 KAUTH_ARG(KAUTH_REQ_PROCESS_CANSEE_ENTRY), NULL, NULL); 294 if (error) 295 return error; 296 } else if (clock_id & CLOCK_THREAD_CPUTIME_ID) { 297 struct lwp *l; 298 lwpid_t lid = clock_id & CPUCLOCK_ID_MASK; 299 p = curproc; 300 mutex_enter(p->p_lock); 301 l = lid == 0 ? curlwp : lwp_find(p, lid); 302 if (l == NULL) { 303 mutex_exit(p->p_lock); 304 return ESRCH; 305 } 306 ticks = l->l_rticksum + l->l_slpticksum; 307 DPRINTF(("%s: r=%ju, s=%ju\n", __func__, 308 (uintmax_t)l->l_rticksum, (uintmax_t)l->l_slpticksum)); 309 mutex_exit(p->p_lock); 310 } else 311 ticks = (uint64_t)-1; 312 313 if (ticks != (uint64_t)-1) { 314 ticks2ts(ticks, ts); 315 return 0; 316 } 317 318 switch (clock_id) { 319 case CLOCK_REALTIME: 320 nanotime(ts); 321 break; 322 case CLOCK_MONOTONIC: 323 nanouptime(ts); 324 break; 325 default: 326 return EINVAL; 327 } 328 329 return 0; 330 } 331 332 /* 333 * Calculate delta and convert from struct timespec to the ticks. 334 */ 335 int 336 ts2timo(clockid_t clock_id, int flags, struct timespec *ts, 337 int *timo, struct timespec *start) 338 { 339 int error; 340 struct timespec tsd; 341 342 if (ts->tv_nsec < 0 || ts->tv_nsec >= 1000000000L) 343 return EINVAL; 344 345 if ((flags & TIMER_ABSTIME) != 0 || start != NULL) { 346 error = clock_gettime1(clock_id, &tsd); 347 if (error != 0) 348 return error; 349 if (start != NULL) 350 *start = tsd; 351 } 352 353 if ((flags & TIMER_ABSTIME) != 0) { 354 if (!timespecsubok(ts, &tsd)) 355 return EINVAL; 356 timespecsub(ts, &tsd, ts); 357 } 358 359 error = itimespecfix(ts); 360 if (error != 0) 361 return error; 362 363 if (ts->tv_sec == 0 && ts->tv_nsec == 0) 364 return ETIMEDOUT; 365 366 *timo = tstohz(ts); 367 KASSERT(*timo > 0); 368 369 return 0; 370 } 371 372 bool 373 timespecaddok(const struct timespec *tsp, const struct timespec *usp) 374 { 375 enum { TIME_MIN = __type_min(time_t), TIME_MAX = __type_max(time_t) }; 376 time_t a = tsp->tv_sec; 377 time_t b = usp->tv_sec; 378 bool carry; 379 380 /* 381 * Caller is responsible for guaranteeing valid timespec 382 * inputs. Any user-controlled inputs must be validated or 383 * adjusted. 384 */ 385 KASSERT(tsp->tv_nsec >= 0); 386 KASSERT(usp->tv_nsec >= 0); 387 KASSERT(tsp->tv_nsec < 1000000000L); 388 KASSERT(usp->tv_nsec < 1000000000L); 389 CTASSERT(1000000000L <= __type_max(long) - 1000000000L); 390 391 /* 392 * Fail if a + b + carry overflows TIME_MAX, or if a + b 393 * overflows TIME_MIN because timespecadd adds the carry after 394 * computing a + b. 395 * 396 * Break it into two mutually exclusive and exhaustive cases: 397 * I. a >= 0 398 * II. a < 0 399 */ 400 carry = (tsp->tv_nsec + usp->tv_nsec >= 1000000000L); 401 if (a >= 0) { 402 /* 403 * Case I: a >= 0. If b < 0, then b + 1 <= 0, so 404 * 405 * a + b + 1 <= a + 0 <= TIME_MAX, 406 * 407 * and 408 * 409 * a + b >= 0 + b = b >= TIME_MIN, 410 * 411 * so this can't overflow. 412 * 413 * If b >= 0, then a + b + carry >= a + b >= 0, so 414 * negative results and thus results below TIME_MIN are 415 * impossible; we need only avoid 416 * 417 * a + b + carry > TIME_MAX, 418 * 419 * which we will do by rejecting if 420 * 421 * b > TIME_MAX - a - carry, 422 * 423 * which in turn is incidentally always false if b < 0 424 * so we don't need extra logic to discriminate on the 425 * b >= 0 and b < 0 cases. 426 * 427 * Since 0 <= a <= TIME_MAX, we know 428 * 429 * 0 <= TIME_MAX - a <= TIME_MAX, 430 * 431 * and hence 432 * 433 * -1 <= TIME_MAX - a - 1 < TIME_MAX. 434 * 435 * So we can compute TIME_MAX - a - carry (i.e., either 436 * TIME_MAX - a or TIME_MAX - a - 1) safely without 437 * overflow. 438 */ 439 if (b > TIME_MAX - a - carry) 440 return false; 441 } else { 442 /* 443 * Case II: a < 0. If b >= 0, then since a + 1 <= 0, 444 * we have 445 * 446 * a + b + 1 <= b <= TIME_MAX, 447 * 448 * and 449 * 450 * a + b >= a >= TIME_MIN, 451 * 452 * so this can't overflow. 453 * 454 * If b < 0, then the intermediate a + b is negative 455 * and the outcome a + b + 1 is nonpositive, so we need 456 * only avoid 457 * 458 * a + b < TIME_MIN, 459 * 460 * which we will do by rejecting if 461 * 462 * a < TIME_MIN - b. 463 * 464 * (Reminder: The carry is added afterward in 465 * timespecadd, so to avoid overflow it is not enough 466 * to merely reject a + b + carry < TIME_MIN.) 467 * 468 * It is safe to compute the difference TIME_MIN - b 469 * because b is negative, so the result lies in 470 * (TIME_MIN, 0]. 471 */ 472 if (b < 0 && a < TIME_MIN - b) 473 return false; 474 } 475 476 return true; 477 } 478 479 bool 480 timespecsubok(const struct timespec *tsp, const struct timespec *usp) 481 { 482 enum { TIME_MIN = __type_min(time_t), TIME_MAX = __type_max(time_t) }; 483 time_t a = tsp->tv_sec, b = usp->tv_sec; 484 bool borrow; 485 486 /* 487 * Caller is responsible for guaranteeing valid timespec 488 * inputs. Any user-controlled inputs must be validated or 489 * adjusted. 490 */ 491 KASSERT(tsp->tv_nsec >= 0); 492 KASSERT(usp->tv_nsec >= 0); 493 KASSERT(tsp->tv_nsec < 1000000000L); 494 KASSERT(usp->tv_nsec < 1000000000L); 495 CTASSERT(1000000000L <= __type_max(long) - 1000000000L); 496 497 /* 498 * Fail if a - b - borrow overflows TIME_MIN, or if a - b 499 * overflows TIME_MAX because timespecsub subtracts the borrow 500 * after computing a - b. 501 * 502 * Break it into two mutually exclusive and exhaustive cases: 503 * I. a < 0 504 * II. a >= 0 505 */ 506 borrow = (tsp->tv_nsec - usp->tv_nsec < 0); 507 if (a < 0) { 508 /* 509 * Case I: a < 0. If b < 0, then -b - 1 >= 0, so 510 * 511 * a - b - 1 >= a + 0 >= TIME_MIN, 512 * 513 * and, since a <= -1, provided that TIME_MIN <= 514 * -TIME_MAX - 1 so that TIME_MAX <= -TIME_MIN - 1 (in 515 * fact, equality holds, under the assumption of 516 * two's-complement arithmetic), 517 * 518 * a - b <= -1 - b = -b - 1 <= TIME_MAX, 519 * 520 * so this can't overflow. 521 */ 522 CTASSERT(TIME_MIN <= -TIME_MAX - 1); 523 524 /* 525 * If b >= 0, then a - b - borrow <= a - b < 0, so 526 * positive results and thus results above TIME_MAX are 527 * impossible; we need only avoid 528 * 529 * a - b - borrow < TIME_MIN, 530 * 531 * which we will do by rejecting if 532 * 533 * a < TIME_MIN + b + borrow. 534 * 535 * The right-hand side is safe to evaluate for any 536 * values of b and borrow as long as TIME_MIN + 537 * TIME_MAX + 1 <= TIME_MAX, i.e., TIME_MIN <= -1. 538 * (Note: If time_t were unsigned, this would fail!) 539 * 540 * Note: Unlike Case I in timespecaddok, this criterion 541 * does not work for b < 0, nor can the roles of a and 542 * b in the inequality be reversed (e.g., -b < TIME_MIN 543 * - a + borrow) without extra cases like checking for 544 * b = TEST_MIN. 545 */ 546 CTASSERT(TIME_MIN < -1); 547 if (b >= 0 && a < TIME_MIN + b + borrow) 548 return false; 549 } else { 550 /* 551 * Case II: a >= 0. If b >= 0, then 552 * 553 * a - b <= a <= TIME_MAX, 554 * 555 * and, provided TIME_MIN <= -TIME_MAX - 1 (in fact, 556 * equality holds, under the assumption of 557 * two's-complement arithmetic) 558 * 559 * a - b - 1 >= -b - 1 >= -TIME_MAX - 1 >= TIME_MIN, 560 * 561 * so this can't overflow. 562 */ 563 CTASSERT(TIME_MIN <= -TIME_MAX - 1); 564 565 /* 566 * If b < 0, then a - b >= a >= 0, so negative results 567 * and thus results below TIME_MIN are impossible; we 568 * need only avoid 569 * 570 * a - b > TIME_MAX, 571 * 572 * which we will do by rejecting if 573 * 574 * a > TIME_MAX + b. 575 * 576 * (Reminder: The borrow is subtracted afterward in 577 * timespecsub, so to avoid overflow it is not enough 578 * to merely reject a - b - borrow > TIME_MAX.) 579 * 580 * It is safe to compute the sum TIME_MAX + b because b 581 * is negative, so the result lies in [0, TIME_MAX). 582 */ 583 if (b < 0 && a > TIME_MAX + b) 584 return false; 585 } 586 587 return true; 588 } 589