1 /* $NetBSD: subr_time_arith.c,v 1.1 2024/12/22 23:24:20 riastradh Exp $ */ 2 3 /*- 4 * Copyright (c) 2000, 2004, 2005, 2007, 2008, 2009, 2020 5 * The NetBSD Foundation, Inc. 6 * All rights reserved. 7 * 8 * This code is derived from software contributed to The NetBSD Foundation 9 * by Christopher G. Demetriou, by Andrew Doran, and by Jason R. Thorpe. 10 * 11 * Redistribution and use in source and binary forms, with or without 12 * modification, are permitted provided that the following conditions 13 * are met: 14 * 1. Redistributions of source code must retain the above copyright 15 * notice, this list of conditions and the following disclaimer. 16 * 2. Redistributions in binary form must reproduce the above copyright 17 * notice, this list of conditions and the following disclaimer in the 18 * documentation and/or other materials provided with the distribution. 19 * 20 * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS 21 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 22 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 23 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS 24 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 25 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 26 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 27 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 28 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 29 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 30 * POSSIBILITY OF SUCH DAMAGE. 31 */ 32 33 /* 34 * Copyright (c) 1982, 1986, 1989, 1993 35 * The Regents of the University of California. All rights reserved. 36 * 37 * Redistribution and use in source and binary forms, with or without 38 * modification, are permitted provided that the following conditions 39 * are met: 40 * 1. Redistributions of source code must retain the above copyright 41 * notice, this list of conditions and the following disclaimer. 42 * 2. Redistributions in binary form must reproduce the above copyright 43 * notice, this list of conditions and the following disclaimer in the 44 * documentation and/or other materials provided with the distribution. 45 * 3. Neither the name of the University nor the names of its contributors 46 * may be used to endorse or promote products derived from this software 47 * without specific prior written permission. 48 * 49 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 50 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 51 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 52 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 53 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 54 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 55 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 56 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 57 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 58 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 59 * SUCH DAMAGE. 60 * 61 * @(#)kern_clock.c 8.5 (Berkeley) 1/21/94 62 * @(#)kern_time.c 8.4 (Berkeley) 5/26/95 63 */ 64 65 #include <sys/cdefs.h> 66 __KERNEL_RCSID(0, "$NetBSD: subr_time_arith.c,v 1.1 2024/12/22 23:24:20 riastradh Exp $"); 67 68 #include <sys/types.h> 69 70 #include <sys/errno.h> 71 #include <sys/time.h> 72 #include <sys/timearith.h> 73 74 #if defined(_KERNEL) 75 76 #include <sys/kernel.h> 77 #include <sys/systm.h> 78 79 #include <machine/limits.h> 80 81 #elif defined(_TIME_TESTING) 82 83 #include <assert.h> 84 #include <limits.h> 85 #include <stdbool.h> 86 87 extern int hz; 88 extern long tick; 89 90 #define KASSERT assert 91 92 #endif 93 94 /* 95 * Compute number of ticks in the specified amount of time. 96 */ 97 int 98 tvtohz(const struct timeval *tv) 99 { 100 unsigned long ticks; 101 long sec, usec; 102 103 /* 104 * If the number of usecs in the whole seconds part of the time 105 * difference fits in a long, then the total number of usecs will 106 * fit in an unsigned long. Compute the total and convert it to 107 * ticks, rounding up and adding 1 to allow for the current tick 108 * to expire. Rounding also depends on unsigned long arithmetic 109 * to avoid overflow. 110 * 111 * Otherwise, if the number of ticks in the whole seconds part of 112 * the time difference fits in a long, then convert the parts to 113 * ticks separately and add, using similar rounding methods and 114 * overflow avoidance. This method would work in the previous 115 * case, but it is slightly slower and assumes that hz is integral. 116 * 117 * Otherwise, round the time difference down to the maximum 118 * representable value. 119 * 120 * If ints are 32-bit, then the maximum value for any timeout in 121 * 10ms ticks is 248 days. 122 */ 123 sec = tv->tv_sec; 124 usec = tv->tv_usec; 125 126 KASSERT(usec >= 0); 127 KASSERT(usec < 1000000); 128 129 /* catch overflows in conversion time_t->int */ 130 if (tv->tv_sec > INT_MAX) 131 return INT_MAX; 132 if (tv->tv_sec < 0) 133 return 0; 134 135 if (sec < 0 || (sec == 0 && usec == 0)) { 136 /* 137 * Would expire now or in the past. Return 0 ticks. 138 * This is different from the legacy tvhzto() interface, 139 * and callers need to check for it. 140 */ 141 ticks = 0; 142 } else if (sec <= (LONG_MAX / 1000000)) 143 ticks = (((sec * 1000000) + (unsigned long)usec + (tick - 1)) 144 / tick) + 1; 145 else if (sec <= (LONG_MAX / hz)) 146 ticks = (sec * hz) + 147 (((unsigned long)usec + (tick - 1)) / tick) + 1; 148 else 149 ticks = LONG_MAX; 150 151 if (ticks > INT_MAX) 152 ticks = INT_MAX; 153 154 return ((int)ticks); 155 } 156 157 /* 158 * Check that a proposed value to load into the .it_value or 159 * .it_interval part of an interval timer is acceptable, and 160 * fix it to have at least minimal value (i.e. if it is less 161 * than the resolution of the clock, round it up.). We don't 162 * timeout the 0,0 value because this means to disable the 163 * timer or the interval. 164 */ 165 int 166 itimerfix(struct timeval *tv) 167 { 168 169 if (tv->tv_usec < 0 || tv->tv_usec >= 1000000) 170 return EINVAL; 171 if (tv->tv_sec < 0) 172 return ETIMEDOUT; 173 if (tv->tv_sec == 0 && tv->tv_usec != 0 && tv->tv_usec < tick) 174 tv->tv_usec = tick; 175 return 0; 176 } 177 178 int 179 itimespecfix(struct timespec *ts) 180 { 181 182 if (ts->tv_nsec < 0 || ts->tv_nsec >= 1000000000) 183 return EINVAL; 184 if (ts->tv_sec < 0) 185 return ETIMEDOUT; 186 if (ts->tv_sec == 0 && ts->tv_nsec != 0 && ts->tv_nsec < tick * 1000) 187 ts->tv_nsec = tick * 1000; 188 return 0; 189 } 190 191 /* 192 * timespecaddok(tsp, usp) 193 * 194 * True if tsp + usp can be computed without overflow, i.e., if it 195 * is OK to do timespecadd(tsp, usp, ...). 196 */ 197 bool 198 timespecaddok(const struct timespec *tsp, const struct timespec *usp) 199 { 200 enum { TIME_MIN = __type_min(time_t), TIME_MAX = __type_max(time_t) }; 201 time_t a = tsp->tv_sec; 202 time_t b = usp->tv_sec; 203 bool carry; 204 205 /* 206 * Caller is responsible for guaranteeing valid timespec 207 * inputs. Any user-controlled inputs must be validated or 208 * adjusted. 209 */ 210 KASSERT(tsp->tv_nsec >= 0); 211 KASSERT(usp->tv_nsec >= 0); 212 KASSERT(tsp->tv_nsec < 1000000000L); 213 KASSERT(usp->tv_nsec < 1000000000L); 214 __CTASSERT(1000000000L <= __type_max(long) - 1000000000L); 215 216 /* 217 * Fail if a + b + carry overflows TIME_MAX, or if a + b 218 * overflows TIME_MIN because timespecadd adds the carry after 219 * computing a + b. 220 * 221 * Break it into two mutually exclusive and exhaustive cases: 222 * I. a >= 0 223 * II. a < 0 224 */ 225 carry = (tsp->tv_nsec + usp->tv_nsec >= 1000000000L); 226 if (a >= 0) { 227 /* 228 * Case I: a >= 0. If b < 0, then b + 1 <= 0, so 229 * 230 * a + b + 1 <= a + 0 <= TIME_MAX, 231 * 232 * and 233 * 234 * a + b >= 0 + b = b >= TIME_MIN, 235 * 236 * so this can't overflow. 237 * 238 * If b >= 0, then a + b + carry >= a + b >= 0, so 239 * negative results and thus results below TIME_MIN are 240 * impossible; we need only avoid 241 * 242 * a + b + carry > TIME_MAX, 243 * 244 * which we will do by rejecting if 245 * 246 * b > TIME_MAX - a - carry, 247 * 248 * which in turn is incidentally always false if b < 0 249 * so we don't need extra logic to discriminate on the 250 * b >= 0 and b < 0 cases. 251 * 252 * Since 0 <= a <= TIME_MAX, we know 253 * 254 * 0 <= TIME_MAX - a <= TIME_MAX, 255 * 256 * and hence 257 * 258 * -1 <= TIME_MAX - a - 1 < TIME_MAX. 259 * 260 * So we can compute TIME_MAX - a - carry (i.e., either 261 * TIME_MAX - a or TIME_MAX - a - 1) safely without 262 * overflow. 263 */ 264 if (b > TIME_MAX - a - carry) 265 return false; 266 } else { 267 /* 268 * Case II: a < 0. If b >= 0, then since a + 1 <= 0, 269 * we have 270 * 271 * a + b + 1 <= b <= TIME_MAX, 272 * 273 * and 274 * 275 * a + b >= a >= TIME_MIN, 276 * 277 * so this can't overflow. 278 * 279 * If b < 0, then the intermediate a + b is negative 280 * and the outcome a + b + 1 is nonpositive, so we need 281 * only avoid 282 * 283 * a + b < TIME_MIN, 284 * 285 * which we will do by rejecting if 286 * 287 * a < TIME_MIN - b. 288 * 289 * (Reminder: The carry is added afterward in 290 * timespecadd, so to avoid overflow it is not enough 291 * to merely reject a + b + carry < TIME_MIN.) 292 * 293 * It is safe to compute the difference TIME_MIN - b 294 * because b is negative, so the result lies in 295 * (TIME_MIN, 0]. 296 */ 297 if (b < 0 && a < TIME_MIN - b) 298 return false; 299 } 300 301 return true; 302 } 303 304 /* 305 * timespecsubok(tsp, usp) 306 * 307 * True if tsp - usp can be computed without overflow, i.e., if it 308 * is OK to do timespecsub(tsp, usp, ...). 309 */ 310 bool 311 timespecsubok(const struct timespec *tsp, const struct timespec *usp) 312 { 313 enum { TIME_MIN = __type_min(time_t), TIME_MAX = __type_max(time_t) }; 314 time_t a = tsp->tv_sec, b = usp->tv_sec; 315 bool borrow; 316 317 /* 318 * Caller is responsible for guaranteeing valid timespec 319 * inputs. Any user-controlled inputs must be validated or 320 * adjusted. 321 */ 322 KASSERT(tsp->tv_nsec >= 0); 323 KASSERT(usp->tv_nsec >= 0); 324 KASSERT(tsp->tv_nsec < 1000000000L); 325 KASSERT(usp->tv_nsec < 1000000000L); 326 __CTASSERT(1000000000L <= __type_max(long) - 1000000000L); 327 328 /* 329 * Fail if a - b - borrow overflows TIME_MIN, or if a - b 330 * overflows TIME_MAX because timespecsub subtracts the borrow 331 * after computing a - b. 332 * 333 * Break it into two mutually exclusive and exhaustive cases: 334 * I. a < 0 335 * II. a >= 0 336 */ 337 borrow = (tsp->tv_nsec - usp->tv_nsec < 0); 338 if (a < 0) { 339 /* 340 * Case I: a < 0. If b < 0, then -b - 1 >= 0, so 341 * 342 * a - b - 1 >= a + 0 >= TIME_MIN, 343 * 344 * and, since a <= -1, provided that TIME_MIN <= 345 * -TIME_MAX - 1 so that TIME_MAX <= -TIME_MIN - 1 (in 346 * fact, equality holds, under the assumption of 347 * two's-complement arithmetic), 348 * 349 * a - b <= -1 - b = -b - 1 <= TIME_MAX, 350 * 351 * so this can't overflow. 352 */ 353 __CTASSERT(TIME_MIN <= -TIME_MAX - 1); 354 355 /* 356 * If b >= 0, then a - b - borrow <= a - b < 0, so 357 * positive results and thus results above TIME_MAX are 358 * impossible; we need only avoid 359 * 360 * a - b - borrow < TIME_MIN, 361 * 362 * which we will do by rejecting if 363 * 364 * a < TIME_MIN + b + borrow. 365 * 366 * The right-hand side is safe to evaluate for any 367 * values of b and borrow as long as TIME_MIN + 368 * TIME_MAX + 1 <= TIME_MAX, i.e., TIME_MIN <= -1. 369 * (Note: If time_t were unsigned, this would fail!) 370 * 371 * Note: Unlike Case I in timespecaddok, this criterion 372 * does not work for b < 0, nor can the roles of a and 373 * b in the inequality be reversed (e.g., -b < TIME_MIN 374 * - a + borrow) without extra cases like checking for 375 * b = TEST_MIN. 376 */ 377 __CTASSERT(TIME_MIN < -1); 378 if (b >= 0 && a < TIME_MIN + b + borrow) 379 return false; 380 } else { 381 /* 382 * Case II: a >= 0. If b >= 0, then 383 * 384 * a - b <= a <= TIME_MAX, 385 * 386 * and, provided TIME_MIN <= -TIME_MAX - 1 (in fact, 387 * equality holds, under the assumption of 388 * two's-complement arithmetic) 389 * 390 * a - b - 1 >= -b - 1 >= -TIME_MAX - 1 >= TIME_MIN, 391 * 392 * so this can't overflow. 393 */ 394 __CTASSERT(TIME_MIN <= -TIME_MAX - 1); 395 396 /* 397 * If b < 0, then a - b >= a >= 0, so negative results 398 * and thus results below TIME_MIN are impossible; we 399 * need only avoid 400 * 401 * a - b > TIME_MAX, 402 * 403 * which we will do by rejecting if 404 * 405 * a > TIME_MAX + b. 406 * 407 * (Reminder: The borrow is subtracted afterward in 408 * timespecsub, so to avoid overflow it is not enough 409 * to merely reject a - b - borrow > TIME_MAX.) 410 * 411 * It is safe to compute the sum TIME_MAX + b because b 412 * is negative, so the result lies in [0, TIME_MAX). 413 */ 414 if (b < 0 && a > TIME_MAX + b) 415 return false; 416 } 417 418 return true; 419 } 420 421 /* 422 * itimer_transition(it, now, next, &overruns) 423 * 424 * Given: 425 * 426 * - it: the current state of an itimer (it_value = last expiry 427 * time, it_interval = periodic rescheduling interval), and 428 * 429 * - now: the current time on the itimer's clock; 430 * 431 * compute: 432 * 433 * - next: the next time the itimer should be scheduled for, and 434 * - overruns: the number of overruns if we're firing late. 435 * 436 * XXX This should maybe also say whether the itimer should expire 437 * at all. 438 */ 439 void 440 itimer_transition(const struct itimerspec *restrict it, 441 const struct timespec *restrict now, 442 struct timespec *restrict next, 443 int *restrict overrunsp) 444 { 445 uint64_t last_val, next_val, interval, now_ns; 446 int backwards; 447 448 /* 449 * Zero the outputs so we can test assertions in userland 450 * without undefined behaviour. 451 */ 452 timespecclear(next); 453 *overrunsp = 0; 454 455 /* 456 * Paranoia: Caller should guarantee this. 457 */ 458 if (!timespecisset(&it->it_interval)) { 459 timespecclear(next); 460 return; 461 } 462 463 backwards = (timespeccmp(&it->it_value, now, >)); 464 465 /* Nonnegative interval guaranteed by itimerfix. */ 466 KASSERT(it->it_interval.tv_sec >= 0); 467 KASSERT(it->it_interval.tv_nsec >= 0); 468 469 /* Handle the easy case of non-overflown timers first. */ 470 if (!backwards && 471 timespecaddok(&it->it_value, &it->it_interval)) { 472 timespecadd(&it->it_value, &it->it_interval, 473 next); 474 } else { 475 now_ns = timespec2ns(now); 476 last_val = timespec2ns(&it->it_value); 477 interval = timespec2ns(&it->it_interval); 478 479 next_val = now_ns + 480 (now_ns - last_val + interval - 1) % interval; 481 482 if (backwards) 483 next_val += interval; 484 else 485 *overrunsp = (now_ns - last_val) / interval; 486 487 next->tv_sec = next_val / 1000000000; 488 next->tv_nsec = next_val % 1000000000; 489 } 490 } 491