improve list_sort test
in [Kernel]
|
Prev: Waiting for your response
Next: drivers/mtd/ubi: Eliminate update of list_for_each_entry loop cursor
From: Artem Bityutskiy on 8 Aug 2010 06:10 On Sat, 2010-08-07 at 11:10 +0300, Artem Bityutskiy wrote: > Hi, > > while hunting a non-existing bug in 'list_sort()', I've improved the > 'list_sort_test()' function which tests the 'list_sort()' library call. Although > at the end I found a bug in my code, but not in 'list_sort()', I think my > clean-ups and improvements are worth merging because they make the test function > better. Actually, your 'list_sort()' version does have a problem. I found out that it calls 'cmp(priv, a, b)' with 'a = b' sometimes, and in these cases 'a' and 'b' can point to something which is not a valid element of the original list. Probably a senitel or something like that. It is easy to work around this by adding: if (a == b) return 0; in the 'cmp()' function, but this is nevertheless a bug (not too bad, though) and should be fixed. Also, the fact that 'cmp()' is called with 'a==b' sometimes should be documented. I'm CC-ing 2 other users of 'list_sort()' for head-ups (xfs, drm). I've fixed assertions in UBIFS using the following patch: =========================================================================== From 3ea1708e2d0462dc8eaf1076ebf973d82700952b Mon Sep 17 00:00:00 2001 From: Artem Bityutskiy <Artem.Bityutskiy(a)nokia.com> Date: Sun, 8 Aug 2010 12:45:23 +0300 Subject: [PATCHv2 8/9] UBIFS: fix assertion warnings in comparison function When running the integrity test ('integck' from mtd-utils) on current UBIFS on 2.6.35, I see that assertions in UBIFS 'list_sort()' comparison functions trigger sometimes, e.g.: UBIFS assert failed in data_nodes_cmp at 132 (pid 28311) My investigation showed that this happens when 'list_sort()' calls the 'cmp()' function with equivalent arguments. In this case, the 'struct list_head' parameter, passed to 'cmp()' is bogus, and it does not belong to any element in the original list. And this issue seems to be introduced by commit: commit 835cc0c8477fdbc59e0217891d6f11061b1ac4e2 Author: Don Mullis <don.mullis(a)gmail.com> Date: Fri Mar 5 13:43:15 2010 -0800 It is easy to work around the issue by doing: if (a == b) return 0; in UBIFS. It works, but 'lib_sort()' should nevertheless be fixed. Although it is harmless to have this piece of code in UBIFS. This patch adds that code to both UBIFS 'cmp()' functions: 'data_nodes_cmp()' and 'nondata_nodes_cmp()'. Signed-off-by: Artem Bityutskiy <Artem.Bityutskiy(a)nokia.com> --- fs/ubifs/gc.c | 6 ++++++ 1 files changed, 6 insertions(+), 0 deletions(-) diff --git a/fs/ubifs/gc.c b/fs/ubifs/gc.c index 8dbe36f..84ab9aa 100644 --- a/fs/ubifs/gc.c +++ b/fs/ubifs/gc.c @@ -125,6 +125,9 @@ int data_nodes_cmp(void *priv, struct list_head *a, struct list_head *b) struct ubifs_scan_node *sa, *sb; cond_resched(); + if (a == b) + return 0; + sa = list_entry(a, struct ubifs_scan_node, list); sb = list_entry(b, struct ubifs_scan_node, list); @@ -165,6 +168,9 @@ int nondata_nodes_cmp(void *priv, struct list_head *a, struct list_head *b) struct ubifs_scan_node *sa, *sb; cond_resched(); + if (a == b) + return 0; + sa = list_entry(a, struct ubifs_scan_node, list); sb = list_entry(b, struct ubifs_scan_node, list); -- 1.7.1.1 -- Best Regards, Artem Bityutskiy (Артём Битюцкий) -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo(a)vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
From: Don Mullis on 8 Aug 2010 15:40 Artem Bityutskiy <dedekind1(a)gmail.com> writes: > Actually, your 'list_sort()' version does have a problem. I found out > that it calls 'cmp(priv, a, b)' with 'a = b' sometimes, and in these > cases 'a' and 'b' can point to something which is not a valid element of > the original list. Probably a senitel or something like that. > > It is easy to work around this by adding: > > if (a == b) > return 0; > > in the 'cmp()' function, but this is nevertheless a bug (not too bad, > though) and should be fixed. Yes, invalid 'a' or 'b' pointers would be a bug. If providing a test case is hard, can you say what segment is pointed to? Into the stack? Into address ranges normal for elements, but not now on the list? Is there a pattern to the values returned? Is it perhaps always the first or last callback from a particular call to list_sort()? That sometimes a==b is, on the other hand, by design: /* * In worst cases this loop may run many iterations. * Continue callbacks to the client even though no * element comparison is needed, so the client's cmp() * routine can invoke cond_resched() periodically. */ (*cmp)(priv, tail, tail); Adding a sentence to the function header comment reminding callers that they need to be able to handle a==b seems like a good idea. -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo(a)vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
From: Don Mullis on 8 Aug 2010 16:10 On Sun, Aug 8, 2010 at 12:31 PM, Don Mullis <don.mullis(a)gmail.com> wrote: > Artem Bityutskiy <dedekind1(a)gmail.com> writes: >> Actually, your 'list_sort()' version does have a problem. I found out >> that it calls 'cmp(priv, a, b)' with 'a = b' sometimes, and in these >> cases 'a' and 'b' can point to something which is not a valid element of >> the original list. Probably a senitel or something like that. Looks like if the original list is a POT in length, the first callback from line 73 will pass a==b both pointing to the original list_head. Would you be able to test this fix? --- linux-2.6.orig/lib/list_sort.c +++ linux-2.6/lib/list_sort.c @@ -70,7 +70,7 @@ static void merge_and_restore_back_links * element comparison is needed, so the client's cmp() * routine can invoke cond_resched() periodically. */ - (*cmp)(priv, tail, tail); + (*cmp)(priv, tail->next, tail->next); tail->next->prev = tail; tail = tail->next; -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo(a)vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
From: Artem Bityutskiy on 9 Aug 2010 02:10
On Sun, 2010-08-08 at 13:07 -0700, Don Mullis wrote: > On Sun, Aug 8, 2010 at 12:31 PM, Don Mullis <don.mullis(a)gmail.com> wrote: > > Artem Bityutskiy <dedekind1(a)gmail.com> writes: > >> Actually, your 'list_sort()' version does have a problem. I found out > >> that it calls 'cmp(priv, a, b)' with 'a = b' sometimes, and in these > >> cases 'a' and 'b' can point to something which is not a valid element of > >> the original list. Probably a senitel or something like that. > > Looks like if the original list is a POT in length, the first callback > from line 73 will pass a==b both pointing to the original list_head. > Would you be able to test this fix? > > --- linux-2.6.orig/lib/list_sort.c > +++ linux-2.6/lib/list_sort.c > @@ -70,7 +70,7 @@ static void merge_and_restore_back_links > * element comparison is needed, so the client's cmp() > * routine can invoke cond_resched() periodically. > */ > - (*cmp)(priv, tail, tail); > + (*cmp)(priv, tail->next, tail->next); > > tail->next->prev = tail; > tail = tail->next; Hi, thanks. I'm out of office, and probably will be able to do this few weeks later. Artem. -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo(a)vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/ |