RE: pingpong, etc. programs
"Perez-Gonzalez, Inaky" <[email protected]>
| Newsgroups | gmane.comp.lib.phil |
|---|---|
| Message-ID | <[email protected]> |
> From: Ulrich Drepper [mailto:[email protected]] > The correct solution is to have the kernel handle the wakeup correctly. > Our current thinking is to wake up only one thread. All the other > threads are moved from the wait-queue of the condvar to the wait-queue > of the mutex. Since there is exactly one mutex involved with every > condvar at any one time the pthread_cond_broadcast function knows where > the mutex wait list is. > > I just have to wait for Ingo to have some time to implement this. I tried to take a spin at this: basically moving all waiters from the condvar's futex to the mutex's futex, right? I twidled the futex code to do this, creating FUTEX_WAKE_REQUEUE. I am sure I must have missed a bunch of things, but as a proof-of-concept it should be ok. I tried to modify NPTL to play with it, but I got nowhere. The problem is in __pthread_cond_broadcast (the asm version), when the first waiter gets out of the futex_wait and gets the mutex without knowing that there are waiters in the kernel; I tried to play dirty a wee bit, but I didn't invest too much effort, as I need to move on to other stuff. So I thought maybe you guys would like to play with it. Attached are the patch for the requeue kernel support (2.5.68) and the hacks I did to nptl 0.30 trying to get it to work ... Ulrich, is this something like what you are looking for? Could you pipe it to Ingo? Iñaky Pérez-González -- Not speaking for Intel -- all opinions are my own (and my fault)
requeue-1.patch
(application/octet-stream, 5.7 KB)
diff -u linux/kernel/futex.c:1.1.1.1 linux/kernel/futex.c:1.1.1.1.2.2
--- linux/kernel/futex.c:1.1.1.1 Thu May 1 13:11:20 2003
+++ linux/kernel/futex.c Fri May 2 16:38:25 2003
@@ -48,7 +48,9 @@
/* Page struct and offset within it. */
struct page *page;
int offset;
-
+ /* Task (for requeuing, task->mm is needed) */
+ task_t *task;
+
/* the virtual => physical COW-safe cache */
vcache_t vcache;
@@ -209,6 +211,7 @@
if (!list_empty(&q->list)) {
q->page = new_page;
+#warning FIXME: unpin oldpage, pin newpage?
list_del(&q->list);
list_add_tail(&q->list, head);
}
@@ -218,7 +221,8 @@
static inline void __queue_me(struct futex_q *q, struct page *page,
unsigned long uaddr, int offset,
- int fd, struct file *filp)
+ int fd, struct file *filp,
+ task_t *task)
{
struct list_head *head = hash_futex(page, offset);
@@ -226,29 +230,117 @@
q->fd = fd;
q->filp = filp;
q->page = page;
-
+ q->task = task;
+
list_add_tail(&q->list, head);
/*
* We register a futex callback to this virtual address,
* to make sure a COW properly rehashes the futex-queue.
*/
- __attach_vcache(&q->vcache, uaddr, current->mm, futex_vcache_callback);
+ __attach_vcache(&q->vcache, uaddr, task->mm, futex_vcache_callback);
}
/* Return 1 if we were still queued (ie. 0 means we were woken) */
-static inline int unqueue_me(struct futex_q *q)
+static inline struct page * unqueue_me(struct futex_q *q)
{
- int ret = 0;
-
+ struct page *page = NULL;
+
spin_lock(&vcache_lock);
spin_lock(&futex_lock);
if (!list_empty(&q->list)) {
list_del(&q->list);
+ page = q->page;
__detach_vcache(&q->vcache);
- ret = 1;
}
spin_unlock(&futex_lock);
spin_unlock(&vcache_lock);
+ return page;
+}
+
+/**
+ * Wake up one waiter hashed on the physical page that is mapped to
+ * @uaddr. Requeue the remainder (up to @num) to a new queue hashed on
+ * @newuaddr.
+ *
+ * @uaddr: address of the futex where the waiters are.
+ * @offset: offset of the futex within the page.
+ * @num: number of waiters to requeue (INT_MAX for all).
+ * @newuaddr: Address of the new futex (in the current mm) where to
+ * queue them.
+ *
+ * Currently it is limited to requeue to addresses that are on the
+ * same memory space.
+ *
+ * @return: < 0 errno code on error, 1 when one waiter is woken up. >
+ * N, 1 waiter woken up, N-1 requeued.
+ */
+static int futex_wake_requeue(unsigned long uaddr, int offset, int num,
+ unsigned long newuaddr)
+{
+ struct list_head *i, *next, *head;
+ struct page *page, *newpage;
+ int newoffset;
+ int ret = -EFAULT;
+
+ lock_futex_mm();
+
+ newoffset = newuaddr % PAGE_SIZE;
+
+ page = __pin_page(uaddr - offset);
+ if (!page)
+ goto out_unlock;
+
+ newpage = __pin_page(newuaddr - newoffset);
+ if (!newpage)
+ goto out_unpin;
+
+ head = hash_futex(page, offset);
+ /* Wake up one guy */
+ ret = 0;
+ list_for_each_safe(i, next, head) {
+ struct futex_q *this = list_entry(i, struct futex_q, list);
+
+ if (this->page == page && this->offset == offset) {
+ list_del_init(i);
+ __detach_vcache(&this->vcache);
+ tell_waiter(this);
+ ret = 1;
+ break;
+ }
+ }
+
+ /* Requeue num guys out to newaddr */
+ list_for_each_safe(i, next, next) {
+ struct futex_q *this = list_entry(i, struct futex_q, list);
+ if (this->page == page && this->offset == offset) {
+ int do_lock = this->task->mm != current->mm;
+
+ list_del_init(i);
+ if (do_lock)
+ _raw_spin_lock(&this->task->mm->page_table_lock);
+ __detach_vcache(&this->vcache);
+ unpin_page(this->page);
+ if(!PageReserved(page))
+ get_page(newpage);
+ __queue_me(this, newpage, newuaddr, newoffset,
+ this->fd, this->filp, this->task);
+ if (do_lock)
+ _raw_spin_unlock(&this->task->mm->page_table_lock);
+ ret++;
+ }
+ }
+
+ unlock_futex_mm();
+ unpin_page(newpage);
+ unpin_page(page);
+
+ return ret;
+
+
+out_unpin:
+ unpin_page (page);
+out_unlock:
+ unlock_futex_mm();
return ret;
}
@@ -259,7 +351,7 @@
{
DECLARE_WAITQUEUE(wait, current);
int ret = 0, curval;
- struct page *page;
+ struct page *page, *upage;
struct futex_q q;
init_waitqueue_head(&q.waiters);
@@ -271,7 +363,7 @@
unlock_futex_mm();
return -EFAULT;
}
- __queue_me(&q, page, uaddr, offset, -1, NULL);
+ __queue_me(&q, page, uaddr, offset, -1, NULL, current);
unlock_futex_mm();
@@ -308,8 +400,11 @@
ret = -EINTR;
out:
/* Were we woken up anyway? */
- if (!unqueue_me(&q))
+ upage = unqueue_me(&q);
+ if (upage != NULL) {
+ page = upage;
ret = 0;
+ }
unpin_page(page);
return ret;
@@ -407,7 +502,7 @@
init_waitqueue_head(&q->waiters);
filp->private_data = q;
- __queue_me(q, page, uaddr, offset, ret, filp);
+ __queue_me(q, page, uaddr, offset, ret, filp, current);
unlock_futex_mm();
@@ -438,6 +533,9 @@
case FUTEX_WAKE:
ret = futex_wake(uaddr, pos_in_page, val);
break;
+ case FUTEX_WAKE_REQUEUE:
+ ret = futex_wake_requeue(uaddr, pos_in_page, val, timeout /* newuaddr */);
+ break;
case FUTEX_FD:
/* non-zero val means F_SETOWN(getpid()) & F_SETSIG(val) */
ret = futex_fd(uaddr, pos_in_page, val);
@@ -451,13 +549,18 @@
asmlinkage long sys_futex(u32 __user *uaddr, int op, int val, struct timespec __user *utime)
{
struct timespec t;
- unsigned long timeout = MAX_SCHEDULE_TIMEOUT;
+ unsigned long timeout;
- if ((op == FUTEX_WAIT) && utime) {
- if (copy_from_user(&t, utime, sizeof(t)) != 0)
- return -EFAULT;
- timeout = timespec_to_jiffies(&t) + 1;
+ if (op == FUTEX_WAIT) {
+ timeout = MAX_SCHEDULE_TIMEOUT;
+ if (utime) {
+ if (copy_from_user(&t, utime, sizeof(t)) != 0)
+ return -EFAULT;
+ timeout = timespec_to_jiffies(&t) + 1;
+ }
}
+ else
+ timeout = (unsigned long) utime;
return do_futex((unsigned long)uaddr, op, val, timeout);
}
requeue-nptl-0.30.patch
(application/octet-stream, 3.4 KB)
diff -u -r -N 0.30/src/nptl/sysdeps/unix/sysv/linux/i386/bits/pthreadtypes.h ./sysdeps/unix/sysv/linux/i386/bits/pthreadtypes.h
--- 0.30/src/nptl/sysdeps/unix/sysv/linux/i386/bits/pthreadtypes.h 2003-02-16 01:56:13.000000000 -0800
+++ ./sysdeps/unix/sysv/linux/i386/bits/pthreadtypes.h 2003-05-01 15:31:36.000000000 -0700
@@ -77,6 +77,7 @@
unsigned long long int __total_seq;
unsigned long long int __wakeup_seq;
unsigned long long int __woken_seq;
+ pthread_mutex_t *__mutex;
} __data;
char __size[__SIZEOF_PTHREAD_COND_T];
long long int __align;
diff -u -r -N 0.30/src/nptl/sysdeps/unix/sysv/linux/i386/i486/pthread_cond_broadcast.S ./sysdeps/unix/sysv/linux/i386/i486/pthread_cond_broadcast.S
--- 0.30/src/nptl/sysdeps/unix/sysv/linux/i386/i486/pthread_cond_broadcast.S 2003-03-08 02:11:14.000000000 -0800
+++ ./sysdeps/unix/sysv/linux/i386/i486/pthread_cond_broadcast.S 2003-05-02 15:05:32.000000000 -0700
@@ -30,6 +30,7 @@
#define SYS_futex 240
#define FUTEX_WAIT 0
#define FUTEX_WAKE 1
+#define FUTEX_WAKE_REQUEUE 3
.text
@@ -74,12 +75,25 @@
subl $1, cond_lock-wakeup_seq(%ebx)
jne 7f
- /* Wake up all threads. */
+#if 0
+ /* Wake up all threads. */
8: movl $FUTEX_WAKE, %ecx
movl $SYS_futex, %eax
movl $0x7fffffff, %edx
ENTER_KERNEL
+#endif
+ /* Wake up 1 thread, requeue the rest. */
+8: movl $FUTEX_WAKE_REQUEUE, %ecx
+ pushl %esi
+ movl mutex-wakeup_seq(%ebx), %edx /* %edx = cond->__data.__mutex */
+ leal mutex_lock(%edx), %edx /* %edx = &cond->__data.__mutex->__data.__lock */
+ movl %edx, %esi
+ movl $SYS_futex, %eax
+ movl $0x7fffffff, %edx
+ ENTER_KERNEL
+
+ popl %esi
xorl %eax, %eax
popl %ebx
ret
diff -u -r -N 0.30/src/nptl/sysdeps/unix/sysv/linux/i386/i486/pthread_cond_wait.S ./sysdeps/unix/sysv/linux/i386/i486/pthread_cond_wait.S
--- 0.30/src/nptl/sysdeps/unix/sysv/linux/i386/i486/pthread_cond_wait.S 2003-03-16 13:07:04.000000000 -0800
+++ ./sysdeps/unix/sysv/linux/i386/i486/pthread_cond_wait.S 2003-05-02 15:05:57.000000000 -0700
@@ -110,6 +110,14 @@
xorl %esi, %esi
movl 16(%esp), %ebx
+ /* Stick mutex to cond->__data.__mutex - I cannot find the right place
+ * to do it only once, asm was never my favourite girl, but it
+ * will do for demonstration purposes - FIXME. */
+
+ leal 28(%ebx), %edx /* %ebx = cond, %edx = cond->__data.__mutex */
+ movl 20(%esp), %eax /* %eax = mutex */
+ movl %eax, (%edx) /* cond->__data.__mutex = mutex */
+
/* Get internal lock. */
movl $1, %eax
LOCK
@@ -225,6 +233,7 @@
/* Trick ahead: 8(%esp) contains the address of the mutex. */
addl $8, %esp
call __pthread_mutex_lock_internal
+ movl $2, mutex_lock(%esp) /* FIXME: ugly hack - there are always waiters */
addl $28, %esp
14: popl %ebx
diff -u -r -N 0.30/src/nptl/sysdeps/unix/sysv/linux/lowlevelcond.sym ./sysdeps/unix/sysv/linux/lowlevelcond.sym
--- 0.30/src/nptl/sysdeps/unix/sysv/linux/lowlevelcond.sym 2003-03-10 00:50:26.000000000 -0800
+++ ./sysdeps/unix/sysv/linux/lowlevelcond.sym 2003-05-01 17:04:04.000000000 -0700
@@ -7,3 +7,5 @@
total_seq offsetof (pthread_cond_t, __data.__total_seq)
wakeup_seq offsetof (pthread_cond_t, __data.__wakeup_seq)
woken_seq offsetof (pthread_cond_t, __data.__woken_seq)
+mutex offsetof (pthread_cond_t, __data.__mutex)
+mutex_lock offsetof (pthread_mutex_t, __data.__lock)