lkml.org 
[lkml]   [1998]   [Nov]   [26]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
Patch in this message
/
Date
From
Subject[patch] Re: Timeout overflow in select()
On Sun, 22 Nov 1998, Stephane Belmon wrote:

>I think there is an overflow in the timeout computation in select().

I had just partially fixed this in my tree (and now I should have
finisched the work). Here my latest diff against 2.1.129 (the diff
will happly specifying the filename, so I suggest you to grab my latest
arca-30 from ftp://e-mind.com/pub/linux/kernel-patches/arca-30...):

Index: fs/select.c
===================================================================
RCS file: /var/cvs/linux/fs/select.c,v
retrieving revision 1.1.1.1
retrieving revision 1.1.1.1.2.2
diff -u -r1.1.1.1 -r1.1.1.1.2.2
--- select.c 1998/11/19 23:01:07 1.1.1.1
+++ select.c 1998/11/25 19:48:06 1.1.1.1.2.2
@@ -17,7 +17,6 @@

#include <asm/uaccess.h>

-#define ROUND_UP(x,y) (((x)+(y)-1)/(y))
#define DEFAULT_POLLMASK (POLLIN | POLLOUT | POLLRDNORM | POLLWRNORM)

/*
@@ -209,18 +208,17 @@
long timeout;
int ret;

- timeout = MAX_SCHEDULE_TIMEOUT;
if (tvp) {
- time_t sec, usec;
+ struct timeval ktvp;

if ((ret = verify_area(VERIFY_READ, tvp, sizeof(*tvp)))
- || (ret = __get_user(sec, &tvp->tv_sec))
- || (ret = __get_user(usec, &tvp->tv_usec)))
+ || (ret = __get_user(ktvp.tv_sec, &tvp->tv_sec))
+ || (ret = __get_user(ktvp.tv_usec, &tvp->tv_usec)))
goto out_nofds;

- timeout = ROUND_UP(usec, 1000000/HZ);
- timeout += sec * (unsigned long) HZ;
- }
+ timeout = timeval_to_jiffies(&ktvp);
+ } else
+ timeout = MAX_SCHEDULE_TIMEOUT;

ret = -ENOMEM;
fds = (fd_set_buffer *) __get_free_page(GFP_KERNEL);
@@ -242,14 +240,15 @@
ret = do_select(n, fds, &timeout);

if (tvp && !(current->personality & STICKY_TIMEOUTS)) {
- time_t sec = 0, usec = 0;
+ struct timeval ktvp;
if (timeout) {
- sec = timeout / HZ;
- usec = timeout % HZ;
- usec *= (1000000/HZ);
+ jiffies_to_timeval(timeout, &ktvp);
+ } else {
+ ktvp.tv_sec = 0;
+ ktvp.tv_usec = 0;
}
- put_user(sec, &tvp->tv_sec);
- put_user(usec, &tvp->tv_usec);
+ put_user(ktvp.tv_sec, &tvp->tv_sec);
+ put_user(ktvp.tv_usec, &tvp->tv_usec);
}

if (ret < 0)
@@ -328,8 +327,8 @@

if (timeout < 0)
timeout = MAX_SCHEDULE_TIMEOUT;
- else if (timeout)
- timeout = (timeout*HZ+999)/1000+1;
+ else
+ timeout = msec_to_jiffies_plus_one(timeout);

err = -ENOMEM;
if (timeout) {
Index: include/linux/time.h
===================================================================
RCS file: /var/cvs/linux/include/linux/time.h,v
retrieving revision 1.1.1.1
retrieving revision 1.1.1.1.2.5
diff -u -r1.1.1.1 -r1.1.1.1.2.5
--- time.h 1998/11/19 23:01:14 1.1.1.1
+++ time.h 1998/11/25 19:49:59 1.1.1.1.2.5
@@ -12,34 +12,185 @@
};
#endif /* _STRUCT_TIMESPEC */

+#define MAX_JIFFY (~0UL >> 1)
+
/*
- * change timeval to jiffies, trying to avoid the
+ * change timespec to jiffies, trying to avoid the
* most obvious overflows..
+ * Mainly rewritten by Andrea Arcangeli
*/
-static __inline__ unsigned long
-timespec_to_jiffies(struct timespec *value)
+static __inline__ long
+timespec_to_jiffies(const struct timespec *value)
{
- unsigned long sec = value->tv_sec;
- long nsec = value->tv_nsec;
+ unsigned long sec = value->tv_sec, nsec = value->tv_nsec, nsec_tmp;
+ long retval;
+
+ if (sec >= MAX_JIFFY / HZ)
+ return MAX_JIFFY;
+ sec *= HZ;

- if (sec > ((long)(~0UL >> 1) / HZ))
- return ~0UL >> 1;
- nsec += 1000000000L / HZ - 1;
- nsec /= 1000000000L / HZ;
- return HZ * sec + nsec;
+ nsec_tmp = nsec + (1000000000UL+HZ-1)/HZ - 1;
+ if (nsec_tmp > nsec)
+ nsec = nsec_tmp;
+ nsec /= (1000000000UL+HZ-1)/HZ;
+ if (nsec >= MAX_JIFFY)
+ return MAX_JIFFY;
+
+ retval = nsec + sec;
+ if (retval < 0)
+ return MAX_JIFFY;
+ return retval;
}

+/*
+ * change timeval to jiffies plus one if the timespec struct is not null
+ * by Andrea Arcangeli
+ */
+static __inline__ long
+timespec_to_jiffies_plus_one(const struct timespec *value)
+{
+ unsigned long sec = value->tv_sec, nsec = value->tv_nsec, nsec_tmp;
+ long retval;
+
+ if (sec >= (MAX_JIFFY-1) / HZ)
+ return MAX_JIFFY;
+ sec *= HZ;
+
+ nsec_tmp = nsec + (1000000000UL+HZ-1)/HZ - 1;
+ if (nsec_tmp > nsec)
+ nsec = nsec_tmp;
+ nsec /= (1000000000UL+HZ-1)/HZ;
+ if (nsec >= MAX_JIFFY-1)
+ return MAX_JIFFY;
+
+ retval = nsec + sec + (value->tv_sec || value->tv_nsec);
+ if (retval < 0)
+ return MAX_JIFFY;
+ return retval;
+}
+
static __inline__ void
-jiffies_to_timespec(unsigned long jiffies, struct timespec *value)
+jiffies_to_timespec(const long jiffies, struct timespec *value)
{
- value->tv_nsec = (jiffies % HZ) * (1000000000L / HZ);
value->tv_sec = jiffies / HZ;
+ value->tv_nsec = (jiffies % HZ) * (1000000000L / HZ);
}
-
+
struct timeval {
time_t tv_sec; /* seconds */
suseconds_t tv_usec; /* microseconds */
};
+
+/*
+ * change timeval to jiffies
+ * I assume that suseconds_t is a long
+ * -arca
+ */
+static __inline__ long
+timeval_to_jiffies(const struct timeval *value)
+{
+ unsigned long sec = value->tv_sec, usec = value->tv_usec, usec_tmp;
+ long retval;
+
+ if (sec >= MAX_JIFFY / HZ)
+ return MAX_JIFFY;
+ sec *= HZ;
+
+ usec_tmp = usec + (1000000UL+HZ-1)/HZ - 1;
+ if (usec_tmp > usec)
+ usec = usec_tmp;
+ usec /= (1000000UL+HZ-1)/HZ;
+ if (usec >= MAX_JIFFY)
+ return MAX_JIFFY;
+
+ retval = usec + sec;
+ if (retval < 0)
+ return MAX_JIFFY;
+ return retval;
+}
+
+/*
+ * change timeval to jiffies plus one
+ * I assume that suseconds_t is a long
+ * -arca
+ */
+static __inline__ long
+timeval_to_jiffies_plus_one(const struct timeval *value)
+{
+ unsigned long sec = value->tv_sec, usec = value->tv_usec, usec_tmp;
+ long retval;
+
+ if (sec >= (MAX_JIFFY-1) / HZ)
+ return MAX_JIFFY;
+ sec *= HZ;
+
+ usec_tmp = usec + (1000000UL+HZ-1)/HZ - 1;
+ if (usec_tmp > usec)
+ usec = usec_tmp;
+ usec /= (1000000UL+HZ-1)/HZ;
+ if (usec >= MAX_JIFFY-1)
+ return MAX_JIFFY;
+
+ retval = usec + sec + 1;
+ if (retval < 0)
+ return MAX_JIFFY;
+ return retval;
+}
+
+static __inline__ void
+jiffies_to_timeval(const long jiffies, struct timeval *value)
+{
+ value->tv_sec = jiffies / HZ;
+ value->tv_usec = (jiffies % HZ) * (1000000L / HZ);
+}
+
+/*
+ * change msec to jiffies. -arca
+ */
+static __inline__ long
+msec_to_jiffies(unsigned long msec)
+{
+#if HZ >= 1000
+ if (msec >= MAX_JIFFY / ((HZ+999)/1000))
+ return MAX_JIFFY;
+ msec = (msec*HZ+999)/1000;
+#else
+ unsigned long msec_tmp;
+ msec_tmp = msec + (1000+HZ-1)/HZ - 1;
+ if (msec_tmp > msec)
+ msec = msec_tmp;
+ msec /= (1000+HZ-1)/HZ;
+
+ if ((signed) msec < 0)
+ return MAX_JIFFY;
+#endif
+
+ return msec;
+}
+
+/*
+ * change msec to jiffies plus one. -arca
+ */
+static __inline__ long
+msec_to_jiffies_plus_one(unsigned long msec)
+{
+#if HZ >= 1000
+ if (msec >= (MAX_JIFFY-1) / ((HZ+999)/1000))
+ return MAX_JIFFY;
+ msec = (msec*HZ+999)/1000 + 1;
+#else
+ unsigned long msec_tmp;
+ msec_tmp = msec + (1000+HZ-1)/HZ - 1;
+ if (msec_tmp > msec)
+ msec = msec_tmp;
+ msec = msec / (1000+HZ-1)/HZ + 1;
+
+ if ((signed) msec < 0)
+ return MAX_JIFFY;
+#endif
+
+ return msec;
+}

struct timezone {
int tz_minuteswest; /* minutes west of Greenwich */
Index: kernel/sched.c
===================================================================
RCS file: /var/cvs/linux/kernel/sched.c,v
retrieving revision 1.1.1.1
retrieving revision 1.1.1.1.2.11
diff -u -r1.1.1.1 -r1.1.1.1.2.11
--- sched.c 1998/11/19 23:01:12 1.1.1.1
+++ sched.c 1998/11/24 00:20:16 1.1.1.1.2.11
@@ -7,6 +7,8 @@
* 1996-12-23 Modified by Dave Grothe to fix bugs in semaphores and
* make semaphores SMP safe
* 1997-01-28 Modified by Finn Arne Gangstad to make timers scale better.
+ * 1998-11-19 Implemented schedule_timeout() and related stuff
+ * by Andrea Arcangeli
*/

/*
@@ -135,8 +138,15 @@
}
#endif
#endif
- if (p->policy != SCHED_OTHER || p->counter > current->counter + 3)
- current->need_resched = 1;
+ /*
+ * If the current process is the idle one, we must reschedule ASAP.
+ * Checking for p->counter >= current->counter we have the idle task
+ * check implicit.
+ * -arca
+ */
+ if (/* idle_task == current || */ p->counter >= current->counter ||
+ p->policy != SCHED_OTHER)
+ current->need_resched = 1;
}

/*
@@ -442,17 +456,18 @@
struct timer_list timer;
unsigned long expire;

- /*
- * PARANOID.
- */
- if (current->state == TASK_UNINTERRUPTIBLE)
+ switch (current->state)
{
- printk(KERN_WARNING "schedule_timeout: task not interrutible "
- "from %p\n", __builtin_return_address(0));
+ case TASK_INTERRUPTIBLE:
+ case TASK_RUNNING:
+ break;
+ default:
/*
* We don' t want to interrupt a not interruptible task
* risking to cause corruption. Better a a deadlock ;-).
*/
+ printk(KERN_ERR "schedule_timeout: task state %ld, from %p!\n",
+ current->state, __builtin_return_address(0));
timeout = MAX_SCHEDULE_TIMEOUT;
}

@@ -599,10 +614,12 @@

#ifdef __SMP__
next->has_cpu = 1;
- next->processor = this_cpu;
#endif

if (prev != next) {
+#ifdef __SMP__
+ next->processor = this_cpu;
+#endif
kstat.context_swtch++;
get_mmu_context(next);
switch_to(prev,next);
@@ -1604,7 +1621,7 @@
asmlinkage int sys_nanosleep(struct timespec *rqtp, struct timespec *rmtp)
{
struct timespec t;
- unsigned long expire;
+ long expire;

if(copy_from_user(&t, rqtp, sizeof(struct timespec)))
return -EFAULT;
@@ -1626,7 +1643,7 @@
return 0;
}

- expire = timespec_to_jiffies(&t) + (t.tv_sec || t.tv_nsec);
+ expire = timespec_to_jiffies_plus_one(&t);

current->state = TASK_INTERRUPTIBLE;
expire = schedule_timeout(expire);
Index: kernel/signal.c
===================================================================
RCS file: /var/cvs/linux/kernel/signal.c,v
retrieving revision 1.1.1.1
retrieving revision 1.1.1.1.2.2
diff -u -r1.1.1.1 -r1.1.1.1.2.2
--- signal.c 1998/11/19 23:01:12 1.1.1.1
+++ signal.c 1998/11/20 10:39:11 1.1.1.1.2.2
@@ -742,8 +742,7 @@

timeout = MAX_SCHEDULE_TIMEOUT;
if (uts)
- timeout = (timespec_to_jiffies(&ts)
- + (ts.tv_sec || ts.tv_nsec));
+ timeout = timespec_to_jiffies_plus_one(&ts);

current->state = TASK_INTERRUPTIBLE;
timeout = schedule_timeout(timeout);

This diff fix also reschedule_idle() (to use the CPU if the old process
was current and the new one has not high counter) and make
schedule_timeout() more pedantic on strange things.

Andrea Arcangeli


-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.rutgers.edu
Please read the FAQ at http://www.tux.org/lkml/

\
 
 \ /
  Last update: 2005-03-22 13:45    [W:0.056 / U:0.068 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site