On Thu, 2007-08-16 at 09:39 +0200, Peter Zijlstra wrote:
> On Wed, 2007-08-15 at 18:39 -0700, john stultz wrote:
> > Hey Ingo, Thomas,
> >
> > I was playing with the latency tracer on 2.6.23-rc2-rt2 while a "make
> > -j8" was going on in the background and the box hung with this on the
> > console:
>
> Hmm, this would have been me :-/
>
> I'll go play...
Could you give this a spin...
(not sure on the added rmbs, but they can't hurt)
---
Fix a deadlock in the fine grain locked list primitives.
Delete and splice use a double lock, which normally locks in the
prev->cur order. For delete this is deadlock free provided one will
never delete the list head - which is exactly what splice attempts.
In order to solve this, use the reverse locking order for splice - which
then assumes that the list passes is indeed the list head (no fancy
dummy item headless lists here).
Signed-off-by: Peter Zijlstra <[EMAIL PROTECTED]>
---
lib/lock_list.c | 66 ++++++++++++++++++++++++++++++++++++++++++++++++++------
1 file changed, 60 insertions(+), 6 deletions(-)
Index: linux-2.6/lib/lock_list.c
===================================================================
--- linux-2.6.orig/lib/lock_list.c
+++ linux-2.6/lib/lock_list.c
@@ -11,7 +11,7 @@
*
* Passed pointers are assumed to be stable by external means such as
* refcounts or RCU. The individual list entries are assumed to be RCU
- * freed (requirement of __lock_list_del).
+ * freed (requirement of __lock_list).
*/
#include <linux/lock_list.h>
@@ -19,12 +19,9 @@
void lock_list_add(struct lock_list_head *new,
struct lock_list_head *list)
{
- struct lock_list_head *next;
-
spin_lock(&new->lock);
spin_lock_nested(&list->lock, LOCK_LIST_NESTING_PREV);
- next = list->next;
- __list_add(&new->head, &list->head, &next->head);
+ __list_add(&new->head, &list->head, &list->next->head);
spin_unlock(&list->lock);
spin_unlock(&new->lock);
}
@@ -35,6 +32,13 @@ static spinlock_t *__lock_list(struct lo
spinlock_t *lock = NULL;
again:
+ /*
+ * all modifications are done under spinlocks
+ * but this read is not, the unlock acks as a wmb
+ * for modifications.
+ */
+ smp_rmb();
+
prev = entry->prev;
if (prev == entry)
goto one;
@@ -52,6 +56,56 @@ one:
return lock;
}
+/*
+ * deadlock galore...
+ *
+ * when using __lock_list to lock the list head we get this:
+ *
+ * lock H 2 1
+ * lock 1 a b
+ * lock 2 A B
+ *
+ * list: ..-> [H] <-> [1] <-> [2] <-..
+ *
+ * obvious dead-lock, to solve this we must use a reverse order
+ * when trying to acquire a double lock on the head:
+ *
+ * lock H r 1 2
+ * lock 1 a b
+ * lock 2 A B
+ *
+ * list: ..-> [H] <-> [1] <-> [2] <-..
+ */
+static spinlock_t *__lock_list_reverse(struct lock_list_head *entry)
+{
+ struct lock_list_head *prev;
+ spinlock_t *lock = NULL;
+
+ spin_lock(&entry->lock);
+again:
+ /*
+ * all modifications are done under spinlocks
+ * but this read is not, the unlock acks as a wmb
+ * for modifications.
+ */
+ smp_rmb();
+ prev = entry->prev;
+ if (prev == entry)
+ goto done;
+
+ spin_lock_nested(&prev->lock, LOCK_LIST_NESTING_PREV);
+ if (unlikely(entry->prev != prev)) {
+ /*
+ * we lost
+ */
+ spin_unlock(&prev->lock);
+ goto again;
+ }
+ lock = &prev->lock;
+done:
+ return lock;
+}
+
void lock_list_del_init(struct lock_list_head *entry)
{
spinlock_t *lock;
@@ -71,7 +125,7 @@ void lock_list_splice_init(struct lock_l
spinlock_t *lock;
rcu_read_lock();
- lock = __lock_list(list);
+ lock = __lock_list_reverse(list);
if (!list_empty(&list->head)) {
spin_lock_nested(&head->lock, LOCK_LIST_NESTING_NEXT);
__list_splice(&list->head, &head->head);
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to [EMAIL PROTECTED]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
