Avoid a rare deadlock during unwind

There is a rare deadlock condition during unwind script creation. If build_script() is interrupted in the middle of creating the script, it holds the script write lock. If the interrupt handler needs to call unwind for some failure condition, unwind will try to read the incomplete script and will deadlock on the script lock.

The fix is to disable interrupts while building the script, so interrupt handlers never see partial scripts.

Promoting spin_lock_irqsave() from script_new() to find_save_locs() changes the indentation, so the patch looks bigger than it really is.

Index: linux/arch/ia64/kernel/unwind.c
=================================--- linux.orig/arch/ia64/kernel/unwind.c Tue Oct 19 12:19:32 2004
+++ linux/arch/ia64/kernel/unwind.c Tue Oct 19 17:58:19 2004
@@ -1279,7 +1279,6 @@ script_new (unsigned long ip)
{
struct unw_script *script, *prev, *tmp; unw_hash_index_t index;
- unsigned long flags;
unsigned short head;

STAT(++unw.stat.script.news);
@@ -1288,13 +1287,9 @@ script_new (unsigned long ip)
* Can't (easily) use cmpxchg() here because of ABA problem
* that is intrinsic in cmpxchg()...
*/
- spin_lock_irqsave(&unw.lock, flags);
- {
- head = unw.lru_head;
- script = unw.cache + head;
- unw.lru_head = script->lru_chain;
- }
- spin_unlock(&unw.lock);
+ head = unw.lru_head;
+ script = unw.cache + head;
+ unw.lru_head = script->lru_chain;

/*
* We'd deadlock here if we interrupted a thread that is holding a read lock on
@@ -1305,43 +1300,39 @@ script_new (unsigned long ip)
if (!write_trylock(&script->lock))
return NULL;

- spin_lock(&unw.lock);
- {
- /* re-insert script at the tail of the LRU chain: */
- unw.cache[unw.lru_tail].lru_chain = head;
- unw.lru_tail = head;
-
- /* remove the old script from the hash table (if it's there): */
- if (script->ip) {
- index = hash(script->ip);
- tmp = unw.cache + unw.hash[index];
- prev = NULL;
- while (1) {
- if (tmp = script) {
- if (prev)
- prev->coll_chain = tmp->coll_chain;
- else
- unw.hash[index] = tmp->coll_chain;
- break;
- } else
- prev = tmp;
- if (tmp->coll_chain >= UNW_CACHE_SIZE)
- /* old script wasn't in the hash-table */
- break;
- tmp = unw.cache + tmp->coll_chain;
- }
+ /* re-insert script at the tail of the LRU chain: */
+ unw.cache[unw.lru_tail].lru_chain = head;
+ unw.lru_tail = head;
+
+ /* remove the old script from the hash table (if it's there): */
+ if (script->ip) {
+ index = hash(script->ip);
+ tmp = unw.cache + unw.hash[index];
+ prev = NULL;
+ while (1) {
+ if (tmp = script) {
+ if (prev)
+ prev->coll_chain = tmp->coll_chain;
+ else
+ unw.hash[index] = tmp->coll_chain;
+ break;
+ } else
+ prev = tmp;
+ if (tmp->coll_chain >= UNW_CACHE_SIZE)
+ /* old script wasn't in the hash-table */
+ break;
+ tmp = unw.cache + tmp->coll_chain;
}
+ }

- /* enter new script in the hash table */
- index = hash(ip);
- script->coll_chain = unw.hash[index];
- unw.hash[index] = script - unw.cache;
+ /* enter new script in the hash table */
+ index = hash(ip);
+ script->coll_chain = unw.hash[index];
+ unw.hash[index] = script - unw.cache;

- script->ip = ip; /* set new IP while we're holding the locks */
+ script->ip = ip; /* set new IP while we're holding the locks */

- STAT(if (script->coll_chain < UNW_CACHE_SIZE) ++unw.stat.script.collisions);
- }
- spin_unlock_irqrestore(&unw.lock, flags);
+ STAT(if (script->coll_chain < UNW_CACHE_SIZE) ++unw.stat.script.collisions);

script->flags = 0;
script->hint = 0;
@@ -1840,6 +1831,7 @@ find_save_locs (struct unw_frame_info *i
{
int have_write_lock = 0;
struct unw_script *scr;
+ unsigned long flags = 0;

if ((info->ip & (local_cpu_data->unimpl_va_mask | 0xf)) || info->ip < TASK_SIZE) {
/* don't let obviously bad addresses pollute the cache */
@@ -1851,8 +1843,10 @@ find_save_locs (struct unw_frame_info *i

scr = script_lookup(info);
if (!scr) {
+ spin_lock_irqsave(&unw.lock, flags);
scr = build_script(info);
if (!scr) {
+ spin_unlock_irqrestore(&unw.lock, flags);
UNW_DPRINT(0,
"unwind.%s: failed to locate/build unwind script for ip %lx\n", __FUNCTION__, info->ip);
@@ -1865,9 +1859,10 @@ find_save_locs (struct unw_frame_info *i

run_script(scr, info);

- if (have_write_lock)
+ if (have_write_lock) {
write_unlock(&scr->lock);
- else
+ spin_unlock_irqrestore(&unw.lock, flags);
+ } else
read_unlock(&scr->lock);
return 0;
}

Keith> There is a rare deadlock condition during unwind script Keith> creation. If build_script() is interrupted in the middle of Keith> creating the script, it holds the script write lock. If the Keith> interrupt handler needs to call unwind for some failure Keith> condition, unwind will try to read the incomplete script and Keith> will deadlock on the script lock.

Keith> The fix is to disable interrupts while building the script, Keith> so interrupt handlers never see partial scripts.

Keith> Promoting spin_lock_irqsave() from script_new() to Keith> find_save_locs() changes the indentation, so the patch looks Keith> bigger than it really is.

I'm not sure this is safe. You're now acquiring the read/write-lock after the spinlock and according to the SMP conventions mentionted at the beginning of the file, this isn't safe:

* o if both the unw.lock spinlock and a script's read-write lock must be
* acquired, then the read-write lock must be acquired first.

Did you check that this isn't a problem? If so, it would at least be necessary to update the comment.

	--david

Emprically it works. The patched code has been hammered several million times, using modifying oprofile code that generates gprof backtraces whenever the profile interrupt pops. That was the code that found the original deadlock in unwind.

The comment does not say why the order is required. I believe that it really meant

o if both the unw.lock spinlock and a script's read-write lock must be acquired using a method that might sleep, then the read-write lock must be acquired first.

adding "using a method that might sleep". The only read-write lock code under spinlock(unw.lock) is write_trylock(), which never sleeps. If you agree with this analysis, then I am happy to update the comment.

Keith> Emprically it works. The patched code has been hammered Keith> several million times, using modifying oprofile code that Keith> generates gprof backtraces whenever the profile interrupt Keith> pops. That was the code that found the original deadlock in Keith> unwind.

Yes, that's certainly a good way to test.

Keith> o if both the unw.lock spinlock and a script's read-write lock must be Keith> acquired using a method that might sleep, then the read-write lock Keith> must be acquired first.

Keith> adding "using a method that might sleep". The only read-write lock Keith> code under spinlock(unw.lock) is write_trylock(), which never sleeps. Keith> If you agree with this analysis, then I am happy to update the comment.

No, the comment was intending to establish the lock hierarchy. If there are no other paths where the locks are acquire in the other order, then it's OK. I'd just reverse the comment to match the (new) reality.

	--david

Reversing the comment would also be wrong. You are not allowed to sleep while holding a spinlock.

Ignore that, brain malfunction. read/write_lock does not sleep. read_lock != semaphore.

Keith> Ignore that, brain malfunction. read/write_lock does not sleep. Keith> read_lock != semaphore.

Yup.

	--david