FreeBSD/Linux Kernel Cross Reference
sys/kern/subr_time.c
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 }
Cache object: 3a52da1024c91b57bcd24cdf2f8cec38
|