From aeb583d08172e038552bdefe0a79a9aa9e2ecd7c Mon Sep 17 00:00:00 2001 From: Thiago Farina Date: Mon, 18 Jan 2010 18:57:33 -0500 Subject: lib/dma-debug.c: mark file-local struct symbol static. warning: symbol 'filter_fops' was not declared. Should it be static? Signed-off-by: Thiago Farina Signed-off-by: Joerg Roedel --- lib/dma-debug.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'lib') diff --git a/lib/dma-debug.c b/lib/dma-debug.c index 7399744..e039958 100644 --- a/lib/dma-debug.c +++ b/lib/dma-debug.c @@ -587,7 +587,7 @@ out_unlock: return count; } -const struct file_operations filter_fops = { +static const struct file_operations filter_fops = { .read = filter_read, .write = filter_write, }; -- cgit v1.1 From 859ddf09743a8cc680af33f7259ccd0fd36bfe9d Mon Sep 17 00:00:00 2001 From: Tejun Heo Date: Tue, 2 Feb 2010 13:43:58 -0800 Subject: idr: fix a critical misallocation bug Eric Paris located a bug in idr. With IDR_BITS of 6, it grows to three layers when id 4096 is first allocated. When that happens, idr wraps incorrectly and searches the idr array ignoring the high bits. The following test code from Eric demonstrates the bug nicely. #include #include #include static DEFINE_IDR(test_idr); int init_module(void) { int ret, forty95, forty96; void *addr; /* add 2 entries both with 4095 as the start address */ again1: if (!idr_pre_get(&test_idr, GFP_KERNEL)) return -ENOMEM; ret = idr_get_new_above(&test_idr, (void *)4095, 4095, &forty95); if (ret) { if (ret == -EAGAIN) goto again1; return ret; } if (forty95 != 4095) printk(KERN_ERR "hmmm, forty95=%d\n", forty95); again2: if (!idr_pre_get(&test_idr, GFP_KERNEL)) return -ENOMEM; ret = idr_get_new_above(&test_idr, (void *)4096, 4095, &forty96); if (ret) { if (ret == -EAGAIN) goto again2; return ret; } if (forty96 != 4096) printk(KERN_ERR "hmmm, forty96=%d\n", forty96); /* try to find the 2 entries, noticing that 4096 broke */ addr = idr_find(&test_idr, forty95); if ((int)addr != forty95) printk(KERN_ERR "hmmm, after find forty95=%d addr=%d\n", forty95, (int)addr); addr = idr_find(&test_idr, forty96); if ((int)addr != forty96) printk(KERN_ERR "hmmm, after find forty96=%d addr=%d\n", forty96, (int)addr); /* really weird, the entry which should be at 4096 is actually at 0!! */ addr = idr_find(&test_idr, 0); if ((int)addr) printk(KERN_ERR "found an entry at id=0 for addr=%d\n", (int)addr); idr_remove(&test_idr, forty95); idr_remove(&test_idr, forty96); return 0; } void cleanup_module(void) { } MODULE_AUTHOR("Eric Paris "); MODULE_DESCRIPTION("Simple idr test"); MODULE_LICENSE("GPL"); This happens because when sub_alloc() back tracks it doesn't always do it step-by-step while the over-the-limit detection assumes step-by-step backtracking. The logic in sub_alloc() looks like the following. restart: clear pa[top level + 1] for end cond detection l = top level while (true) { search for empty slot at this level if (not found) { push id to the next possible value l++ A: if (pa[l] is clear) failed, return asking caller to grow the tree if (going up 1 level gives more slots to search) continue the while loop above with the incremented l else C: goto restart } adjust id accordingly to the found slot if (l == 0) return found id; create lower level if not there yet record pa[l] and l-- } Test A is the fail exit condition but this assumes that failure is propagated upwared one level at a time but the B optimization path breaks the assumption and restarts the whole thing with a start value which is above the possible limit with the current layers. sub_alloc() assumes the start id value is inside the limit when called and test A is the only exit condition check, so it ends up searching for empty slot while ignoring high set bit. So, for 4095->4096 test, level0 search fails but pa[1] contains a valid pointer. However, going up 1 level wouldn't give any more empty slot so it takes C and when the whole thing restarts nobody notices the high bit set beyond the top level. This patch fixes the bug by changing the fail exit condition check to full id limit check. Based-on-patch-from: Eric Paris Reported-by: Eric Paris Signed-off-by: Tejun Heo Cc: Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/idr.c | 7 +++---- 1 file changed, 3 insertions(+), 4 deletions(-) (limited to 'lib') diff --git a/lib/idr.c b/lib/idr.c index 1cac726..ba7d37c 100644 --- a/lib/idr.c +++ b/lib/idr.c @@ -140,8 +140,7 @@ static int sub_alloc(struct idr *idp, int *starting_id, struct idr_layer **pa) id = *starting_id; restart: p = idp->top; - l = idp->layers; - pa[l--] = NULL; + l = p->layer; while (1) { /* * We run around this while until we reach the leaf node... @@ -155,8 +154,8 @@ static int sub_alloc(struct idr *idp, int *starting_id, struct idr_layer **pa) oid = id; id = (id | ((1 << (IDR_BITS * l)) - 1)) + 1; - /* if already at the top layer, we need to grow */ - if (!(p = pa[l])) { + /* did id go over the limit? */ + if (id >= (1 << (idp->layers * IDR_BITS))) { *starting_id = id; return IDR_NEED_TO_GROW; } -- cgit v1.1 From 6f14a668f1a8b715a6e855f4e32705e54a6e86a1 Mon Sep 17 00:00:00 2001 From: Tejun Heo Date: Thu, 4 Feb 2010 17:57:37 +0900 Subject: idr: revert misallocation bug fix Commit 859ddf09743a8cc680af33f7259ccd0fd36bfe9d tried to fix misallocation bug but broke full bit marking by not clearing pa[idp->layers] and also is causing X failures due to lookup failure in drm code. The cause of the latter hasn't been found yet. Revert the fix for now. Signed-off-by: Tejun Heo Signed-off-by: Linus Torvalds --- lib/idr.c | 7 ++++--- 1 file changed, 4 insertions(+), 3 deletions(-) (limited to 'lib') diff --git a/lib/idr.c b/lib/idr.c index ba7d37c..1cac726 100644 --- a/lib/idr.c +++ b/lib/idr.c @@ -140,7 +140,8 @@ static int sub_alloc(struct idr *idp, int *starting_id, struct idr_layer **pa) id = *starting_id; restart: p = idp->top; - l = p->layer; + l = idp->layers; + pa[l--] = NULL; while (1) { /* * We run around this while until we reach the leaf node... @@ -154,8 +155,8 @@ static int sub_alloc(struct idr *idp, int *starting_id, struct idr_layer **pa) oid = id; id = (id | ((1 << (IDR_BITS * l)) - 1)) + 1; - /* did id go over the limit? */ - if (id >= (1 << (idp->layers * IDR_BITS))) { + /* if already at the top layer, we need to grow */ + if (!(p = pa[l])) { *starting_id = id; return IDR_NEED_TO_GROW; } -- cgit v1.1