1 /* $NetBSD: subr_time.c,v 1.35 2022/06/28 02:04:51 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.35 2022/06/28 02:04:51 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 && usec < 1000000); 102 103 /* catch overflows in conversion time_t->int */ 104 if (tv->tv_sec > INT_MAX) 105 return INT_MAX; 106 if (tv->tv_sec < 0) 107 return 0; 108 109 if (sec < 0 || (sec == 0 && usec == 0)) { 110 /* 111 * Would expire now or in the past. Return 0 ticks. 112 * This is different from the legacy tvhzto() interface, 113 * and callers need to check for it. 114 */ 115 ticks = 0; 116 } else if (sec <= (LONG_MAX / 1000000)) 117 ticks = (((sec * 1000000) + (unsigned long)usec + (tick - 1)) 118 / tick) + 1; 119 else if (sec <= (LONG_MAX / hz)) 120 ticks = (sec * hz) + 121 (((unsigned long)usec + (tick - 1)) / tick) + 1; 122 else 123 ticks = LONG_MAX; 124 125 if (ticks > INT_MAX) 126 ticks = INT_MAX; 127 128 return ((int)ticks); 129 } 130 131 int 132 tshzto(const struct timespec *tsp) 133 { 134 struct timespec now, ts; 135 136 ts = *tsp; /* Don't modify original tsp. */ 137 getnanotime(&now); 138 timespecsub(&ts, &now, &ts); 139 return tstohz(&ts); 140 } 141 142 int 143 tshztoup(const struct timespec *tsp) 144 { 145 struct timespec now, ts; 146 147 ts = *tsp; /* Don't modify original tsp. */ 148 getnanouptime(&now); 149 timespecsub(&ts, &now, &ts); 150 return tstohz(&ts); 151 } 152 153 /* 154 * Compute number of ticks in the specified amount of time. 155 */ 156 int 157 tstohz(const struct timespec *ts) 158 { 159 struct timeval tv; 160 161 /* 162 * usec has great enough resolution for hz, so convert to a 163 * timeval and use tvtohz() above. 164 */ 165 TIMESPEC_TO_TIMEVAL(&tv, ts); 166 return tvtohz(&tv); 167 } 168 169 /* 170 * Check that a proposed value to load into the .it_value or 171 * .it_interval part of an interval timer is acceptable, and 172 * fix it to have at least minimal value (i.e. if it is less 173 * than the resolution of the clock, round it up.). We don't 174 * timeout the 0,0 value because this means to disable the 175 * timer or the interval. 176 */ 177 int 178 itimerfix(struct timeval *tv) 179 { 180 181 if (tv->tv_usec < 0 || tv->tv_usec >= 1000000) 182 return EINVAL; 183 if (tv->tv_sec < 0) 184 return ETIMEDOUT; 185 if (tv->tv_sec == 0 && tv->tv_usec != 0 && tv->tv_usec < tick) 186 tv->tv_usec = tick; 187 return 0; 188 } 189 190 int 191 itimespecfix(struct timespec *ts) 192 { 193 194 if (ts->tv_nsec < 0 || ts->tv_nsec >= 1000000000) 195 return EINVAL; 196 if (ts->tv_sec < 0) 197 return ETIMEDOUT; 198 if (ts->tv_sec == 0 && ts->tv_nsec != 0 && ts->tv_nsec < tick * 1000) 199 ts->tv_nsec = tick * 1000; 200 return 0; 201 } 202 203 int 204 inittimeleft(struct timespec *ts, struct timespec *sleepts) 205 { 206 207 if (itimespecfix(ts)) { 208 return -1; 209 } 210 KASSERT(ts->tv_sec >= 0); 211 getnanouptime(sleepts); 212 return 0; 213 } 214 215 int 216 gettimeleft(struct timespec *ts, struct timespec *sleepts) 217 { 218 struct timespec now, sleptts; 219 220 KASSERT(ts->tv_sec >= 0); 221 222 /* 223 * Reduce ts by elapsed time based on monotonic time scale. 224 */ 225 getnanouptime(&now); 226 KASSERT(timespeccmp(sleepts, &now, <=)); 227 timespecsub(&now, sleepts, &sleptts); 228 *sleepts = now; 229 230 if (timespeccmp(ts, &sleptts, <=)) { /* timed out */ 231 timespecclear(ts); 232 return 0; 233 } 234 timespecsub(ts, &sleptts, ts); 235 236 return tstohz(ts); 237 } 238 239 void 240 clock_timeleft(clockid_t clockid, struct timespec *ts, struct timespec *sleepts) 241 { 242 struct timespec sleptts; 243 244 clock_gettime1(clockid, &sleptts); 245 timespecadd(ts, sleepts, ts); 246 timespecsub(ts, &sleptts, ts); 247 *sleepts = sleptts; 248 } 249 250 static void 251 ticks2ts(uint64_t ticks, struct timespec *ts) 252 { 253 ts->tv_sec = ticks / hz; 254 uint64_t sticks = ticks - ts->tv_sec * hz; 255 if (sticks > BINTIME_SCALE_MS) /* floor(2^64 / 1000) */ 256 ts->tv_nsec = sticks / hz * 1000000000LL; 257 else if (sticks > BINTIME_SCALE_US) /* floor(2^64 / 1000000) */ 258 ts->tv_nsec = sticks * 1000LL / hz * 1000000LL; 259 else 260 ts->tv_nsec = sticks * 1000000000LL / hz; 261 DPRINTF(("%s: %ju/%ju -> %ju.%ju\n", __func__, 262 (uintmax_t)ticks, (uintmax_t)sticks, 263 (uintmax_t)ts->tv_sec, (uintmax_t)ts->tv_nsec)); 264 } 265 266 int 267 clock_gettime1(clockid_t clock_id, struct timespec *ts) 268 { 269 int error; 270 uint64_t ticks; 271 struct proc *p; 272 273 #define CPUCLOCK_ID_MASK (~(CLOCK_THREAD_CPUTIME_ID|CLOCK_PROCESS_CPUTIME_ID)) 274 if (clock_id & CLOCK_PROCESS_CPUTIME_ID) { 275 pid_t pid = clock_id & CPUCLOCK_ID_MASK; 276 277 mutex_enter(&proc_lock); 278 p = pid == 0 ? curproc : proc_find(pid); 279 if (p == NULL) { 280 mutex_exit(&proc_lock); 281 return ESRCH; 282 } 283 ticks = p->p_uticks + p->p_sticks + p->p_iticks; 284 DPRINTF(("%s: u=%ju, s=%ju, i=%ju\n", __func__, 285 (uintmax_t)p->p_uticks, (uintmax_t)p->p_sticks, 286 (uintmax_t)p->p_iticks)); 287 mutex_exit(&proc_lock); 288 289 // XXX: Perhaps create a special kauth type 290 error = kauth_authorize_process(kauth_cred_get(), 291 KAUTH_PROCESS_PTRACE, p, 292 KAUTH_ARG(KAUTH_REQ_PROCESS_CANSEE_ENTRY), NULL, NULL); 293 if (error) 294 return error; 295 } else if (clock_id & CLOCK_THREAD_CPUTIME_ID) { 296 struct lwp *l; 297 lwpid_t lid = clock_id & CPUCLOCK_ID_MASK; 298 p = curproc; 299 mutex_enter(p->p_lock); 300 l = lid == 0 ? curlwp : lwp_find(p, lid); 301 if (l == NULL) { 302 mutex_exit(p->p_lock); 303 return ESRCH; 304 } 305 ticks = l->l_rticksum + l->l_slpticksum; 306 DPRINTF(("%s: r=%ju, s=%ju\n", __func__, 307 (uintmax_t)l->l_rticksum, (uintmax_t)l->l_slpticksum)); 308 mutex_exit(p->p_lock); 309 } else 310 ticks = (uint64_t)-1; 311 312 if (ticks != (uint64_t)-1) { 313 ticks2ts(ticks, ts); 314 return 0; 315 } 316 317 switch (clock_id) { 318 case CLOCK_REALTIME: 319 nanotime(ts); 320 break; 321 case CLOCK_MONOTONIC: 322 nanouptime(ts); 323 break; 324 default: 325 return EINVAL; 326 } 327 328 return 0; 329 } 330 331 /* 332 * Calculate delta and convert from struct timespec to the ticks. 333 */ 334 int 335 ts2timo(clockid_t clock_id, int flags, struct timespec *ts, 336 int *timo, struct timespec *start) 337 { 338 int error; 339 struct timespec tsd; 340 341 if (ts->tv_nsec < 0 || ts->tv_nsec >= 1000000000L) 342 return EINVAL; 343 344 if ((flags & TIMER_ABSTIME) != 0 || start != NULL) { 345 error = clock_gettime1(clock_id, &tsd); 346 if (error != 0) 347 return error; 348 if (start != NULL) 349 *start = tsd; 350 } 351 352 if ((flags & TIMER_ABSTIME) != 0) { 353 if (!timespecsubok(ts, &tsd)) 354 return EINVAL; 355 timespecsub(ts, &tsd, ts); 356 } 357 358 error = itimespecfix(ts); 359 if (error != 0) 360 return error; 361 362 if (ts->tv_sec == 0 && ts->tv_nsec == 0) 363 return ETIMEDOUT; 364 365 *timo = tstohz(ts); 366 KASSERT(*timo > 0); 367 368 return 0; 369 } 370 371 bool 372 timespecaddok(const struct timespec *tsp, const struct timespec *usp) 373 { 374 enum { TIME_MIN = __type_min(time_t), TIME_MAX = __type_max(time_t) }; 375 time_t a = tsp->tv_sec; 376 time_t b = usp->tv_sec; 377 bool carry; 378 379 /* 380 * Caller is responsible for guaranteeing valid timespec 381 * inputs. Any user-controlled inputs must be validated or 382 * adjusted. 383 */ 384 KASSERT(tsp->tv_nsec >= 0); 385 KASSERT(usp->tv_nsec >= 0); 386 KASSERT(tsp->tv_nsec < 1000000000L); 387 KASSERT(usp->tv_nsec < 1000000000L); 388 CTASSERT(1000000000L <= __type_max(long) - 1000000000L); 389 390 /* 391 * Fail if a + b + carry overflows TIME_MAX, or if a + b 392 * overflows TIME_MIN because timespecadd adds the carry after 393 * computing a + b. 394 * 395 * Break it into two mutually exclusive and exhaustive cases: 396 * I. a >= 0 397 * II. a < 0 398 */ 399 carry = (tsp->tv_nsec + usp->tv_nsec >= 1000000000L); 400 if (a >= 0) { 401 /* 402 * Case I: a >= 0. If b < 0, then b + 1 <= 0, so 403 * 404 * a + b + 1 <= a + 0 <= TIME_MAX, 405 * 406 * and 407 * 408 * a + b >= 0 + b = b >= TIME_MIN, 409 * 410 * so this can't overflow. 411 * 412 * If b >= 0, then a + b + carry >= a + b >= 0, so 413 * negative results and thus results below TIME_MIN are 414 * impossible; we need only avoid 415 * 416 * a + b + carry > TIME_MAX, 417 * 418 * which we will do by rejecting if 419 * 420 * b > TIME_MAX - a - carry, 421 * 422 * which in turn is incidentally always false if b < 0 423 * so we don't need extra logic to discriminate on the 424 * b >= 0 and b < 0 cases. 425 * 426 * Since 0 <= a <= TIME_MAX, we know 427 * 428 * 0 <= TIME_MAX - a <= TIME_MAX, 429 * 430 * and hence 431 * 432 * -1 <= TIME_MAX - a - 1 < TIME_MAX. 433 * 434 * So we can compute TIME_MAX - a - carry (i.e., either 435 * TIME_MAX - a or TIME_MAX - a - 1) safely without 436 * overflow. 437 */ 438 if (b > TIME_MAX - a - carry) 439 return false; 440 } else { 441 /* 442 * Case II: a < 0. If b >= 0, then since a + 1 <= 0, 443 * we have 444 * 445 * a + b + 1 <= b <= TIME_MAX, 446 * 447 * and 448 * 449 * a + b >= a >= TIME_MIN, 450 * 451 * so this can't overflow. 452 * 453 * If b < 0, then the intermediate a + b is negative 454 * and the outcome a + b + 1 is nonpositive, so we need 455 * only avoid 456 * 457 * a + b < TIME_MIN, 458 * 459 * which we will do by rejecting if 460 * 461 * a < TIME_MIN - b. 462 * 463 * (Reminder: The carry is added afterward in 464 * timespecadd, so to avoid overflow it is not enough 465 * to merely reject a + b + carry < TIME_MIN.) 466 * 467 * It is safe to compute the difference TIME_MIN - b 468 * because b is negative, so the result lies in 469 * (TIME_MIN, 0]. 470 */ 471 if (b < 0 && a < TIME_MIN - b) 472 return false; 473 } 474 475 return true; 476 } 477 478 bool 479 timespecsubok(const struct timespec *tsp, const struct timespec *usp) 480 { 481 enum { TIME_MIN = __type_min(time_t), TIME_MAX = __type_max(time_t) }; 482 time_t a = tsp->tv_sec, b = usp->tv_sec; 483 bool borrow; 484 485 /* 486 * Caller is responsible for guaranteeing valid timespec 487 * inputs. Any user-controlled inputs must be validated or 488 * adjusted. 489 */ 490 KASSERT(tsp->tv_nsec >= 0); 491 KASSERT(usp->tv_nsec >= 0); 492 KASSERT(tsp->tv_nsec < 1000000000L); 493 KASSERT(usp->tv_nsec < 1000000000L); 494 CTASSERT(1000000000L <= __type_max(long) - 1000000000L); 495 496 /* 497 * Fail if a - b - borrow overflows TIME_MIN, or if a - b 498 * overflows TIME_MAX because timespecsub subtracts the borrow 499 * after computing a - b. 500 * 501 * Break it into two mutually exclusive and exhaustive cases: 502 * I. a < 0 503 * II. a >= 0 504 */ 505 borrow = (tsp->tv_nsec - usp->tv_nsec < 0); 506 if (a < 0) { 507 /* 508 * Case I: a < 0. If b < 0, then -b - 1 >= 0, so 509 * 510 * a - b - 1 >= a + 0 >= TIME_MIN, 511 * 512 * and, since a <= -1, provided that TIME_MIN <= 513 * -TIME_MAX - 1 so that TIME_MAX <= -TIME_MIN - 1 (in 514 * fact, equality holds, under the assumption of 515 * two's-complement arithmetic), 516 * 517 * a - b <= -1 - b = -b - 1 <= TIME_MAX, 518 * 519 * so this can't overflow. 520 */ 521 CTASSERT(TIME_MIN <= -TIME_MAX - 1); 522 523 /* 524 * If b >= 0, then a - b - borrow <= a - b < 0, so 525 * positive results and thus results above TIME_MAX are 526 * impossible; we need only avoid 527 * 528 * a - b - borrow < TIME_MIN, 529 * 530 * which we will do by rejecting if 531 * 532 * a < TIME_MIN + b + borrow. 533 * 534 * The right-hand side is safe to evaluate for any 535 * values of b and borrow as long as TIME_MIN + 536 * TIME_MAX + 1 <= TIME_MAX, i.e., TIME_MIN <= -1. 537 * (Note: If time_t were unsigned, this would fail!) 538 * 539 * Note: Unlike Case I in timespecaddok, this criterion 540 * does not work for b < 0, nor can the roles of a and 541 * b in the inequality be reversed (e.g., -b < TIME_MIN 542 * - a + borrow) without extra cases like checking for 543 * b = TEST_MIN. 544 */ 545 CTASSERT(TIME_MIN < -1); 546 if (b >= 0 && a < TIME_MIN + b + borrow) 547 return false; 548 } else { 549 /* 550 * Case II: a >= 0. If b >= 0, then 551 * 552 * a - b <= a <= TIME_MAX, 553 * 554 * and, provided TIME_MIN <= -TIME_MAX - 1 (in fact, 555 * equality holds, under the assumption of 556 * two's-complement arithmetic) 557 * 558 * a - b - 1 >= -b - 1 >= -TIME_MAX - 1 >= TIME_MIN, 559 * 560 * so this can't overflow. 561 */ 562 CTASSERT(TIME_MIN <= -TIME_MAX - 1); 563 564 /* 565 * If b < 0, then a - b >= a >= 0, so negative results 566 * and thus results below TIME_MIN are impossible; we 567 * need only avoid 568 * 569 * a - b > TIME_MAX, 570 * 571 * which we will do by rejecting if 572 * 573 * a > TIME_MAX + b. 574 * 575 * (Reminder: The borrow is subtracted afterward in 576 * timespecsub, so to avoid overflow it is not enough 577 * to merely reject a - b - borrow > TIME_MAX.) 578 * 579 * It is safe to compute the sum TIME_MAX + b because b 580 * is negative, so the result lies in [0, TIME_MAX). 581 */ 582 if (b < 0 && a > TIME_MAX + b) 583 return false; 584 } 585 586 return true; 587 } 588