Re: [patch] sys_epoll_wait() timeout saga ...

Willy Tarreau
2005-09-24T07:54:04Z

On Sat, Sep 24, 2005 at 12:33:05AM -0700, Vadim Lobanov wrote:
> On Sat, 24 Sep 2005, Willy Tarreau wrote:
>
> > On Fri, Sep 23, 2005 at 09:44:10PM -0700, Nish Aravamudan wrote:
> > > > > * that why (t * HZ) / 1000.
> > > > > */
> > > > > - jtimeout = timeout == -1 || timeout > (MAX_SCHEDULE_TIMEOUT - 1000) / HZ ?
> > > > > + jtimeout = timeout < 0 || (timeout / 1000) >= (MAX_SCHEDULE_TIMEOUT / HZ) ?
> > > > > MAX_SCHEDULE_TIMEOUT: (timeout * HZ + 999) / 1000;
> > > >
> > > > Here, I'm not certain that gcc will optimize the divide. It would be better
> > > > anyway to write this which is equivalent, and a pure integer comparison :
> > > >
> > > > + jtimeout = timeout < 0 || timeout >= 1000 * MAX_SCHEDULE_TIMEOUT / HZ ?
> > > > > MAX_SCHEDULE_TIMEOUT: (timeout * HZ + 999) / 1000;
> > >
> > > Just a question here, maybe it's dumb.
> >
> > Your question is not dumb, this code is not trivial at all !
> >
> > > * and / have the same priority in the order of operations, yes? If so,
> > > won't the the 1000 * MAX_SCHEDULE_TIMEOUT overflow
> > > (MAX_SCHEDULE_TIMEOUT is LONG_MAX)?
> >
> > Yes it can, and that's why I said that gcc should send a warning when
> > comparing an int with something too large for an int. But I should have
> > forced the constant to be evaluated as long long. At the moment, the
> > constant cannot overflow, but it can reach a value so high that
> > timeout/1000 will never reach it. Example :
> > MAX_SCHEDULE_TIMEOUT=LONG_MAX
> > HZ=250
> > timeout=LONG_MAX-1
> > => timeout/1000 < MAX_SCHEDULE_TIMEOUT/HZ
> > but (timeout * HZ + 999) / 1000 will still overflow !
> >
> > So I finally think that the safest test would be to avoid the timeout
> > range which can overflow in the computation, using something like this
> > (but which will limit the timeout to 49 days on HZ=1000 machines) :
> >
> > + jtimeout = timeout < 0 || \
> > + timeout >= (1000ULL * MAX_SCHEDULE_TIMEOUT / HZ) || \
> > + timeout >= (LONG_MAX / HZ - 1000) ?
> > MAX_SCHEDULE_TIMEOUT: (timeout * HZ + 999) / 1000;
>
> It seems that we can make the second overflow test be less strict by
> doing the following instead:
> timeout >= (LONG_MAX - 1000) / HZ
> Unless I'm confused. :-)

oops, you're right. Then it produces the following patch :

diff -purN linux-2.6.13/fs/eventpoll.c linux-2.6.13-epoll/fs/eventpoll.c
--- linux-2.6.13/fs/eventpoll.c Sun Sep 11 08:25:26 2005
+++ linux-2.6.13-epoll/fs/eventpoll.c Sat Sep 24 09:49:43 2005
@@ -1504,9 +1504,12 @@ static int ep_poll(struct eventpoll *ep,
/*
* Calculate the timeout by checking for the "infinite" value ( -1 )
* and the overflow condition. The passed timeout is in milliseconds,
- * that why (t * HZ) / 1000.
+ * that why (t * HZ) / 1000. Note that we also want to avoid an
+ * overflow in the multiply.
*/
- jtimeout = timeout == -1 || timeout > (MAX_SCHEDULE_TIMEOUT - 1000) / HZ ?
+ jtimeout = timeout < 0 ||
+ timeout > (MAX_SCHEDULE_TIMEOUT * 1000ULL / HZ) ||
+ timeout > (LONG_MAX - 1000) / HZ ?
MAX_SCHEDULE_TIMEOUT: (timeout * HZ + 999) / 1000;

retry:

Interestingly, as long as MAC_SCHEDULE_TIMEOUT == LONG_MAX, the check is
identical to the initial one (and does not add any divide) !

Regards,
Willy