Search this blog...

MAX_JIFFY_OFFSET: msleep() beyond infinity

Ever wondered what would happen if a driver in the Linux kernel were to invoke Buzz Lightyear's oft-quoted catchphrase?


If not then today is your lucky day, you can ponder over this million-dollar(price of Lightyear's left wing-nut :P) question safe in the comfort of the fact that the definitive answer is only as far as a couple of clicks of your mouse-wheel.

NOTE: This article discusses the intricacies of the implementation of msleep(), specifically the conversion between milliseconds and jiffies within the Linux kernel. For details on implementing blocking calls and other such constructs that wait indefinitely, refer to Section 6.2 Blocking I/O of LDD3 here or here.

First a few numerical constants relevant to this discussion
Largest unsigned 32bit number = ULONG_MAX         = 0xFFFFFFFF
Largest signed 32bit number   = LONG_MAX          = 0x7FFFFFFF
Largest jiffies defined       = MAX_JIFFY_OFFSET  = 0x3FFFFFFE


A "jiffy" is defined as 1/HZ seconds. On a typical system with HZ=100, 1Jiffy works out to be 10ms in terms of real world units of time.

MAX_JIFFY_OFFSET = 0x3FFFFFFE jiffies
= 1073741822jiffies
= ~10737418seconds
= ~2982 hrs
= ~124days
= ~17weeks

msleep() uses msecs_to_jiffies(), which relies on MAX_JIFFY_OFFSET as the definition of infinite sleep timeout.

Now consider the following input/output map of the msec_to_jiffies() for the entire range of 32bit unsigned int.



As is apparent, msecs-jiffies mapping is mostly linearly. Starting from 0, for increasing values of input, msec_to_jiffies() returns correspondingly larger values. However once the input msecs exceeds LONG_MAX, the output jiffies is clamped to MAX_JIFFY_OFFSET.

Its obvious that, for certain values of input to msecs_to_jiffies() the output result exceeds its definition of "infinity" i.e. exceeds MAX_JIFFY_OFFSET. In fact, this happens for a quarter of the range of 32bit unsigned int! Pretty brain-dead, you say, eh?

https://www.youtube.com/watch?v=-vohNUTTx3A

To be fair, the patch that introduced this definition of MAX_JIFFY_OFFSET is perfectly fine as it solves a genuine practical problem.
commit 9f907c0144496e464bd5ed5a99a51227d63a9c0b
Author: Ingo Molnar
[PATCH] Fix timeout overflow with jiffies
Prevent timeout overflow if timer ticks are behind jiffies
(due to high softirq load or due to dyntick),
by limiting the valid timeout range to MAX_LONG/2.


So what can be done for msecs_to_jiffies()?

Instead of clamping negative values to MAX_JIFFY_OFFSET
502         /*
503          * Negative value, means infinite timeout:
504          */
505         if ((int)m < 0)
506                 return MAX_JIFFY_OFFSET;

Should values larger than (MAX_LONG/2) be clamped to MAX_JIFFY_OFFSET?
502         /*
503          * Prevent timeout overflow if timer ticks are behind jiffies
504          * by limiting the valid timeout range to MAX_LONG/2.
505          */
506         if (m > MAX_JIFFY_OFFSET)
507                 return MAX_JIFFY_OFFSET;

This update follows the spirit of the patch that introduced the current definition of MAX_JIFFY_OFFSET. Heck, even the comment is borrowed from it!

To answer the original question, any invocation of  msleep(N)
where MAX_JIFFY_OFFSET < N < LONG_MAX
technically sleeps for longer than "infinity" as defined in the context of msleep().

For the technically inclined, a parting question -

Q. With the current implementation in the Linux kernel,
under what circumstances will msleep(10) return sooner than 10ms?

No comments :

Post a Comment