// $Header$
// Kernel Version:
//  VERSION = 2
//  PATCHLEVEL = 5
//  SUBLEVEL = 48
//  EXTRAVERSION =
--- 2.5/include/linux/poll.h	2002-11-20 22:58:18.000000000 +0100
+++ build-2.5/include/linux/poll.h	2002-11-20 22:51:15.000000000 +0100
@@ -37,6 +37,8 @@
  */
 struct poll_table_entry {
 	struct file *filp;
+	int woken;
+	void *handle;
 	wait_queue_t wait;
 	wait_queue_head_t *wait_address;
 };
@@ -47,8 +49,10 @@
 	poll_table pt;
 	int error;
 	int nr;
+	void *handle;
 	struct poll_table_entry internal[POLL_TABLE_INTERNAL];
 	struct poll_table_page *table;
+	struct poll_table_page *last;
 };
 
 extern void poll_initwait(struct poll_wqueues *pwq);
--- 2.5/fs/select.c	2002-11-20 22:58:18.000000000 +0100
+++ build-2.5/fs/select.c	2002-11-20 22:58:01.000000000 +0100
@@ -55,6 +55,7 @@
 	pwq->error = 0;
 	pwq->nr = 0;
 	pwq->table = NULL;
+	pwq->last = NULL;
 }
 /*
  * Dynamic memory allocation is expensive, avoid it by
@@ -95,6 +96,15 @@
 	}
 }
 
+static int poll_wake_func(wait_queue_t *wait, unsigned mode, int sync)
+{
+	struct poll_table_entry *entry = container_of(wait, struct poll_table_entry, wait);
+	entry->woken = 1;
+	mb();
+	wake_up_process(wait->task);
+	return 0;
+}
+
 static void __pollwait(struct file *filp, wait_queue_head_t *wait_address, poll_table *_p)
 {
 	struct poll_wqueues *p = container_of(_p, struct poll_wqueues, pt);
@@ -103,7 +113,7 @@
  	if(p->nr < POLL_TABLE_INTERNAL) {
  		entry = p->internal+p->nr++;
  	} else {
-		struct poll_table_page *table = p->table;
+		struct poll_table_page *table = p->last;
 
 		if (!table || POLL_TABLE_FULL(table)) {
 			struct poll_table_page *new_table;
@@ -115,8 +125,12 @@
 				return;
 			}
 			new_table->entry = new_table->entries;
-			new_table->next = table;
-			p->table = new_table;
+			new_table->next = NULL;
+			if (table)
+				table->next = new_table;
+			else
+				p->table = new_table;
+			p->last = new_table;
 			table = new_table;
 		}
 		entry = table->entry;
@@ -127,7 +141,10 @@
 	get_file(filp);
 	entry->filp = filp;
 	entry->wait_address = wait_address;
-	init_waitqueue_entry(&entry->wait, current);
+	entry->woken = 0;
+	entry->handle = p->handle;
+	init_waitqueue_func_entry(&entry->wait, poll_wake_func);
+	entry->wait.task = current;
 	add_wait_queue(wait_address,&entry->wait);
 }
 
@@ -189,6 +206,51 @@
 #define POLLOUT_SET (POLLWRBAND | POLLWRNORM | POLLOUT | POLLERR)
 #define POLLEX_SET (POLLPRI)
 
+static int parse_mask(fd_set_bits *fds, unsigned long mask, unsigned long off, unsigned long bit)
+{
+	int retval = 0;
+
+	if ((mask & POLLIN_SET) && ISSET(bit, __IN(fds,off))) {
+		SET(bit, __RES_IN(fds,off));
+		retval++;
+	}
+	if ((mask & POLLOUT_SET) && ISSET(bit, __OUT(fds,off))) {
+		SET(bit, __RES_OUT(fds,off));
+		retval++;
+	}
+	if ((mask & POLLEX_SET) && ISSET(bit, __EX(fds,off))) {
+		SET(bit, __RES_EX(fds,off));
+		retval++;
+	}
+	return retval;
+}
+
+static int scan_entries(fd_set_bits *fds, struct poll_table_entry *entries, int size, int *prev)
+{
+	int i;
+	int retval = 0;
+	for (i=0;i<size;i++) {
+		unsigned long mask;
+		int fd;
+		if (!entries[i].woken)
+	       		continue;
+		entries[i].woken = 0;
+		mb();
+		/* drivers are permitted to use multiple waitqueues, but we must
+		 * not double-account that in the return value
+		 */
+		fd = (int)entries[i].handle;
+		if (fd == *prev)
+			continue;
+		*prev = fd;
+		mask = DEFAULT_POLLMASK;
+		if (entries[i].filp->f_op && entries[i].filp->f_op->poll)
+			mask = entries[i].filp->f_op->poll(entries[i].filp, NULL);
+		retval += parse_mask(fds, mask, fd/__NFDBITS, BIT(fd));
+	}
+	return retval;
+}
+
 int do_select(int n, fd_set_bits *fds, long *timeout)
 {
 	struct poll_wqueues table;
@@ -209,41 +271,35 @@
 	if (!__timeout)
 		wait = NULL;
 	retval = 0;
-	for (;;) {
-		set_current_state(TASK_INTERRUPTIBLE);
-		for (i = 0 ; i < n; i++) {
-			unsigned long bit = BIT(i);
-			unsigned long mask;
-			struct file *file;
-
-			off = i / __NFDBITS;
-			if (!(bit & BITS(fds, off)))
-				continue;
-			file = fget(i);
-			mask = POLLNVAL;
-			if (file) {
-				mask = DEFAULT_POLLMASK;
-				if (file->f_op && file->f_op->poll)
-					mask = file->f_op->poll(file, wait);
-				fput(file);
-			}
-			if ((mask & POLLIN_SET) && ISSET(bit, __IN(fds,off))) {
-				SET(bit, __RES_IN(fds,off));
-				retval++;
-				wait = NULL;
-			}
-			if ((mask & POLLOUT_SET) && ISSET(bit, __OUT(fds,off))) {
-				SET(bit, __RES_OUT(fds,off));
-				retval++;
-				wait = NULL;
-			}
-			if ((mask & POLLEX_SET) && ISSET(bit, __EX(fds,off))) {
-				SET(bit, __RES_EX(fds,off));
-				retval++;
-				wait = NULL;
-			}
+	/* step one: build the wait table */
+	set_current_state(TASK_INTERRUPTIBLE);
+	for (i = 0 ; i < n; i++) {
+		unsigned long bit = BIT(i);
+		unsigned long mask;
+		struct file *file;
+
+		off = i / __NFDBITS;
+		if (!(bit & BITS(fds, off)))
+			continue;
+		file = fget(i);
+		mask = POLLNVAL;
+		if (file) {
+			mask = DEFAULT_POLLMASK;
+			table.handle = (void*)i;
+			if (file->f_op && file->f_op->poll)
+				mask = file->f_op->poll(file, wait);
+			fput(file);
 		}
-		wait = NULL;
+		retval += parse_mask(fds, mask, off, bit);
+		if (retval)
+			wait = NULL;
+	}
+	wait = NULL;
+	/* step two: now scan through the wait queues, that's faster
+	 * than the bit lookup */
+	for (;;) {
+		struct poll_table_page *pg;
+		int prev;
 		if (retval || !__timeout || signal_pending(current))
 			break;
 		if(table.error) {
@@ -251,6 +307,14 @@
 			break;
 		}
 		__timeout = schedule_timeout(__timeout);
+		set_current_state(TASK_INTERRUPTIBLE);
+		prev = -1;
+		retval += scan_entries(fds, table.internal, table.nr, &prev);
+		pg = table.table;
+		while (pg) {
+			retval += scan_entries(fds, pg->entries, pg->entry-pg->entries, &prev);
+			pg = pg->next;
+		}
 	}
 	current->state = TASK_RUNNING;