[PATCH] AB-BA deadlock between uidhash_lock and tasklist_lock.

[PATCH] AB-BA deadlock between uidhash_lock and tasklist_lock.

[Robin Holt]

We have uncovered a very difficult to trip AB-BA deadlock between the
uidhash_lock and tasklist_lock.

reparent_to_init() does write_lock_irq(&tasklist_lock) then calls
switch_uid() which calls free_uid() which grabs the uidhash_lock.

Independent of that, we have seen a different cpu call free_uid as a
result of sys_wait4 and, immediately after acquiring the uidhash_lock,
receive a timer interrupt which eventually leads to an attempt to grab
the tasklist_lock.

Signed-off-by: Robin Holt <holt@sgi.com>


Index: linux/kernel/user.c
===================================================================
--- linux.orig/kernel/user.c	2004-12-22 13:10:49.000000000 -0600
+++ linux/kernel/user.c	2004-12-22 16:04:40.244569776 -0600
@@ -90,6 +90,9 @@
 
 void free_uid(struct user_struct *up)
 {
+	unsigned long   flags;
+
+	local_irq_save(flags);
 	if (up && atomic_dec_and_lock(&up->__count, &uidhash_lock)) {
 		uid_hash_remove(up);
 		key_put(up->uid_keyring);
@@ -97,6 +100,7 @@
 		kmem_cache_free(uid_cachep, up);
 		spin_unlock(&uidhash_lock);
 	}
+	local_irq_restore(flags);
 }
 
 struct user_struct * alloc_uid(uid_t uid)

Re: [PATCH] AB-BA deadlock between uidhash_lock and tasklist_lock.

[Robin Holt]

This is a replacement patch to one I sent yesterday.  I missed a
couple instances of the uidhash_lock and was also told I should
have sent it directly to Linus instead of Andrew.

We have uncovered a very difficult to trip AB-BA deadlock between the
uidhash_lock and tasklist_lock.

reparent_to_init() does write_lock_irq(&tasklist_lock) then calls
switch_uid() which calls free_uid() which grabs the uidhash_lock.

Independent of that, we have seen a different cpu call free_uid as a
result of sys_wait4 and, immediately after acquiring the uidhash_lock,
receive a timer interrupt which eventually leads to an attempt to grab
the tasklist_lock.


Signed-off-by: Robin Holt <holt@sgi.com>


Index: linux/kernel/user.c
===================================================================
--- linux.orig/kernel/user.c	2004-12-22 13:10:49.000000000 -0600
+++ linux/kernel/user.c	2004-12-23 11:07:21.100577562 -0600
@@ -90,6 +90,9 @@
 
 void free_uid(struct user_struct *up)
 {
+	unsigned long flags;
+
+	local_irq_save(flags);
 	if (up && atomic_dec_and_lock(&up->__count, &uidhash_lock)) {
 		uid_hash_remove(up);
 		key_put(up->uid_keyring);
@@ -97,16 +100,18 @@
 		kmem_cache_free(uid_cachep, up);
 		spin_unlock(&uidhash_lock);
 	}
+	local_irq_restore(flags);
 }
 
 struct user_struct * alloc_uid(uid_t uid)
 {
 	struct list_head *hashent = uidhashentry(uid);
 	struct user_struct *up;
+	unsigned long flags;
 
-	spin_lock(&uidhash_lock);
+	spin_lock_irqsave(&uidhash_lock, flags);
 	up = uid_hash_find(uid, hashent);
-	spin_unlock(&uidhash_lock);
+	spin_unlock_irqrestore(&uidhash_lock, flags);
 
 	if (!up) {
 		struct user_struct *new;
@@ -132,7 +137,7 @@
 		 * Before adding this, check whether we raced
 		 * on adding the same user already..
 		 */
-		spin_lock(&uidhash_lock);
+		spin_lock_irqsave(&uidhash_lock, flags);
 		up = uid_hash_find(uid, hashent);
 		if (up) {
 			key_put(new->uid_keyring);
@@ -142,7 +147,7 @@
 			uid_hash_insert(new, hashent);
 			up = new;
 		}
-		spin_unlock(&uidhash_lock);
+		spin_unlock_irqrestore(&uidhash_lock, flags);
 
 	}
 	return up;
@@ -170,6 +175,7 @@
 static int __init uid_cache_init(void)
 {
 	int n;
+	unsigned long flags;
 
 	uid_cachep = kmem_cache_create("uid_cache", sizeof(struct user_struct),
 			0, SLAB_HWCACHE_ALIGN|SLAB_PANIC, NULL, NULL);
@@ -178,9 +184,9 @@
 		INIT_LIST_HEAD(uidhash_table + n);
 
 	/* Insert the root user immediately (init already runs as root) */
-	spin_lock(&uidhash_lock);
+	spin_lock_irqsave(&uidhash_lock, flags);
 	uid_hash_insert(&root_user, uidhashentry(0));
-	spin_unlock(&uidhash_lock);
+	spin_unlock_irqrestore(&uidhash_lock, flags);
 
 	return 0;
 }

Re: [PATCH] AB-BA deadlock between uidhash_lock and tasklist_lock.

[Andrew Morton]

Robin Holt <holt@sgi.com> wrote:
>
> We have uncovered a very difficult to trip AB-BA deadlock between the
> uidhash_lock and tasklist_lock.

yup.  I made some changes to your patch - please review.

- s/spin_lock_irqsave/spin_lock_irq/ in those places where local
  interrupts are obviously always enabled.

- your second patch still missed find_user().

- add comment.


--- 25/kernel/user.c~ab-ba-deadlock-between-uidhash_lock-and-tasklist_lock	Thu Dec 23 14:45:02 2004
+++ 25-akpm/kernel/user.c	Thu Dec 23 14:52:07 2004
@@ -26,6 +26,14 @@
 
 static kmem_cache_t *uid_cachep;
 static struct list_head uidhash_table[UIDHASH_SZ];
+
+/*
+ * uidhash_lock is taken inside write_lock_irq(&tasklist_lock).  If a timer
+ * interrupt were to occur while we hold uidhash_lock, and that interrupt takes
+ * read_lock(&tasklist_lock) then we have an ab/ba deadlock scenario.  Hence
+ * uidhash_lock must always be taken in an ir-qsafe manner to hold off the
+ * timer interrupt.
+ */
 static spinlock_t uidhash_lock = SPIN_LOCK_UNLOCKED;
 
 struct user_struct root_user = {
@@ -81,15 +89,19 @@ static inline struct user_struct *uid_ha
 struct user_struct *find_user(uid_t uid)
 {
 	struct user_struct *ret;
+	unsigned long flags;
 
-	spin_lock(&uidhash_lock);
+	spin_lock_irqsave(&uidhash_lock, flags);
 	ret = uid_hash_find(uid, uidhashentry(uid));
-	spin_unlock(&uidhash_lock);
+	spin_unlock_irqrestore(&uidhash_lock, flags);
 	return ret;
 }
 
 void free_uid(struct user_struct *up)
 {
+	unsigned long flags;
+
+	local_irq_save(flags);
 	if (up && atomic_dec_and_lock(&up->__count, &uidhash_lock)) {
 		uid_hash_remove(up);
 		key_put(up->uid_keyring);
@@ -97,6 +109,7 @@ void free_uid(struct user_struct *up)
 		kmem_cache_free(uid_cachep, up);
 		spin_unlock(&uidhash_lock);
 	}
+	local_irq_restore(flags);
 }
 
 struct user_struct * alloc_uid(uid_t uid)
@@ -104,9 +117,9 @@ struct user_struct * alloc_uid(uid_t uid
 	struct list_head *hashent = uidhashentry(uid);
 	struct user_struct *up;
 
-	spin_lock(&uidhash_lock);
+	spin_lock_irq(&uidhash_lock);
 	up = uid_hash_find(uid, hashent);
-	spin_unlock(&uidhash_lock);
+	spin_unlock_irq(&uidhash_lock);
 
 	if (!up) {
 		struct user_struct *new;
@@ -132,7 +145,7 @@ struct user_struct * alloc_uid(uid_t uid
 		 * Before adding this, check whether we raced
 		 * on adding the same user already..
 		 */
-		spin_lock(&uidhash_lock);
+		spin_lock_irq(&uidhash_lock);
 		up = uid_hash_find(uid, hashent);
 		if (up) {
 			key_put(new->uid_keyring);
@@ -142,7 +155,7 @@ struct user_struct * alloc_uid(uid_t uid
 			uid_hash_insert(new, hashent);
 			up = new;
 		}
-		spin_unlock(&uidhash_lock);
+		spin_unlock_irq(&uidhash_lock);
 
 	}
 	return up;
@@ -178,9 +191,9 @@ static int __init uid_cache_init(void)
 		INIT_LIST_HEAD(uidhash_table + n);
 
 	/* Insert the root user immediately (init already runs as root) */
-	spin_lock(&uidhash_lock);
+	spin_lock_irq(&uidhash_lock);
 	uid_hash_insert(&root_user, uidhashentry(0));
-	spin_unlock(&uidhash_lock);
+	spin_unlock_irq(&uidhash_lock);
 
 	return 0;
 }
_

Re: [PATCH] AB-BA deadlock between uidhash_lock and tasklist_lock.

[Jesper Juhl]

On Thu, 23 Dec 2004, Andrew Morton wrote:

> +/*
> + * uidhash_lock is taken inside write_lock_irq(&tasklist_lock).  If a timer
> + * interrupt were to occur while we hold uidhash_lock, and that interrupt takes
> + * read_lock(&tasklist_lock) then we have an ab/ba deadlock scenario.  Hence
> + * uidhash_lock must always be taken in an ir-qsafe manner to hold off the
> + * timer interrupt.
> + */

Miniature nit: You write "... ir-qsafe manner ...", I'm fairly certain you 
mean "... irq-safe manner ..." :-)


-- 
Jesper Juhl

Re: [PATCH] AB-BA deadlock between uidhash_lock and tasklist_lock.

[Andrew Morton]

Jesper Juhl <juhl-lkml@dif.dk> wrote:
>
> On Thu, 23 Dec 2004, Andrew Morton wrote:
> 
> > +/*
> > + * uidhash_lock is taken inside write_lock_irq(&tasklist_lock).  If a timer
> > + * interrupt were to occur while we hold uidhash_lock, and that interrupt takes
> > + * read_lock(&tasklist_lock) then we have an ab/ba deadlock scenario.  Hence
> > + * uidhash_lock must always be taken in an ir-qsafe manner to hold off the
> > + * timer interrupt.
> > + */
> 

hrm.  Why don't we just do this?

--- 25/kernel/exit.c~a	Thu Dec 23 15:29:57 2004
+++ 25-akpm/kernel/exit.c	Thu Dec 23 15:30:04 2004
@@ -242,9 +242,8 @@ void reparent_to_init(void)
 	memcpy(current->signal->rlim, init_task.signal->rlim,
 	       sizeof(current->signal->rlim));
 	atomic_inc(&(INIT_USER->__count));
-	switch_uid(INIT_USER);
-
 	write_unlock_irq(&tasklist_lock);
+	switch_uid(INIT_USER);
 }
 
 void __set_special_pids(pid_t session, pid_t pgrp)
_

I see no reason why switch_uid() needs tasklist_lock.  set_user() doesn't
hold it?

Re: [PATCH] AB-BA deadlock between uidhash_lock and tasklist_lock.

[Linus Torvalds]

On Thu, 23 Dec 2004, Andrew Morton wrote:
> 
> hrm.  Why don't we just do this?

Seems sane enough. Nobody should look at somebody elses user anyway. The
signal code does, though. That's a separate bug (and looks harmless), and
that code doesn't hold tasklist_lock anyway, so the lock doesn't matter
for that thing.

		Linus

Re: [PATCH] AB-BA deadlock between uidhash_lock and tasklist_lock.

[Linus Torvalds]

On Thu, 10 Mar 2005, Robin Holt wrote:
> 
> reparent_to_init() does write_lock_irq(&tasklist_lock) then calls
> switch_uid() which calls free_uid() which grabs the uidhash_lock.
> 
> Independent of that, we have seen a different cpu call free_uid as a
> result of sys_wait4 and, immediately after acquiring the uidhash_lock,
> receive a timer interrupt which eventually leads to an attempt to grab
> the tasklist_lock.

Hmm..  We fixed this already, and the current tree doesn't have this 
problem (and the fix was much simpler: just move "switch_uid()" to outside 
the tasklist_lock.

That fix was done late december last year (current BK revision: 
1.1938.446.38), and I really think your patch is stale. Please 
double-check,

		Linus

[PATCH] AB-BA deadlock between uidhash_lock and tasklist_lock.

[Robin Holt]

We have uncovered a very difficult to trip AB-BA deadlock between the
uidhash_lock and tasklist_lock.

reparent_to_init() does write_lock_irq(&tasklist_lock) then calls
switch_uid() which calls free_uid() which grabs the uidhash_lock.

Independent of that, we have seen a different cpu call free_uid as a
result of sys_wait4 and, immediately after acquiring the uidhash_lock,
receive a timer interrupt which eventually leads to an attempt to grab
the tasklist_lock.


Signed-off-by: Robin Holt <holt@sgi.com>


Index: linux/kernel/user.c
===================================================================
--- linux.orig/kernel/user.c	2004-12-22 13:10:49.000000000 -0600
+++ linux/kernel/user.c	2004-12-23 11:07:21.100577562 -0600
@@ -90,6 +90,9 @@
 
 void free_uid(struct user_struct *up)
 {
+	unsigned long flags;
+
+	local_irq_save(flags);
 	if (up && atomic_dec_and_lock(&up->__count, &uidhash_lock)) {
 		uid_hash_remove(up);
 		key_put(up->uid_keyring);
@@ -97,16 +100,18 @@
 		kmem_cache_free(uid_cachep, up);
 		spin_unlock(&uidhash_lock);
 	}
+	local_irq_restore(flags);
 }
 
 struct user_struct * alloc_uid(uid_t uid)
 {
 	struct list_head *hashent = uidhashentry(uid);
 	struct user_struct *up;
+	unsigned long flags;
 
-	spin_lock(&uidhash_lock);
+	spin_lock_irqsave(&uidhash_lock, flags);
 	up = uid_hash_find(uid, hashent);
-	spin_unlock(&uidhash_lock);
+	spin_unlock_irqrestore(&uidhash_lock, flags);
 
 	if (!up) {
 		struct user_struct *new;
@@ -132,7 +137,7 @@
 		 * Before adding this, check whether we raced
 		 * on adding the same user already..
 		 */
-		spin_lock(&uidhash_lock);
+		spin_lock_irqsave(&uidhash_lock, flags);
 		up = uid_hash_find(uid, hashent);
 		if (up) {
 			key_put(new->uid_keyring);
@@ -142,7 +147,7 @@
 			uid_hash_insert(new, hashent);
 			up = new;
 		}
-		spin_unlock(&uidhash_lock);
+		spin_unlock_irqrestore(&uidhash_lock, flags);
 
 	}
 	return up;
@@ -170,6 +175,7 @@
 static int __init uid_cache_init(void)
 {
 	int n;
+	unsigned long flags;
 
 	uid_cachep = kmem_cache_create("uid_cache", sizeof(struct user_struct),
 			0, SLAB_HWCACHE_ALIGN|SLAB_PANIC, NULL, NULL);
@@ -178,9 +184,9 @@
 		INIT_LIST_HEAD(uidhash_table + n);
 
 	/* Insert the root user immediately (init already runs as root) */
-	spin_lock(&uidhash_lock);
+	spin_lock_irqsave(&uidhash_lock, flags);
 	uid_hash_insert(&root_user, uidhashentry(0));
-	spin_unlock(&uidhash_lock);
+	spin_unlock_irqrestore(&uidhash_lock, flags);
 
 	return 0;
 }