The Design and Implementation of the FreeBSD Operating System, Second Edition
Now available: The Design and Implementation of the FreeBSD Operating System (Second Edition)


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]

FreeBSD/Linux Kernel Cross Reference
sys/kern/subr_time.c

Version: -  FREEBSD  -  FREEBSD-13-STABLE  -  FREEBSD-13-0  -  FREEBSD-12-STABLE  -  FREEBSD-12-0  -  FREEBSD-11-STABLE  -  FREEBSD-11-0  -  FREEBSD-10-STABLE  -  FREEBSD-10-0  -  FREEBSD-9-STABLE  -  FREEBSD-9-0  -  FREEBSD-8-STABLE  -  FREEBSD-8-0  -  FREEBSD-7-STABLE  -  FREEBSD-7-0  -  FREEBSD-6-STABLE  -  FREEBSD-6-0  -  FREEBSD-5-STABLE  -  FREEBSD-5-0  -  FREEBSD-4-STABLE  -  FREEBSD-3-STABLE  -  FREEBSD22  -  l41  -  OPENBSD  -  linux-2.6  -  MK84  -  PLAN9  -  xnu-8792 
SearchContext: -  none  -  3  -  10 

    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


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]


This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.