list sort

list sort

[Steven Whitehouse]

Hi,

There seems to be an issue with list_sort trying to compare an object to
itself. I spotted it first in a list for which I knew that I had unique
keys, so had put a BUG() in the cmp function if the keys being compared
were equal. While investigating I discovered that the objects themselves
were equal (and hence the keys, also). The following addition to the
list_sort test also triggers twice during the self test:

diff --git a/lib/list_sort.c b/lib/list_sort.c
index d7325c6..afa4a97 100644
--- a/lib/list_sort.c
+++ b/lib/list_sort.c
@@ -198,6 +198,8 @@ static int __init cmp(void *priv, struct list_head *a, struct list_head *b)
 {
 	struct debug_el *ela, *elb;
 
+	WARN_ON(a == b);
+
 	ela = container_of(a, struct debug_el, list);
 	elb = container_of(b, struct debug_el, list);
 

While it appears generally harmless, since the list does appear to be
correctly sorted, it is doing extra work needlessly.

I couldn't find a listing in the maintainers' file for list_sort, so
I used git to find those who'd worked on it recently,

Steve.

Re: list sort

[Clemens Ladisch]

Steven Whitehouse wrote:
> There seems to be an issue with list_sort trying to compare an object to
> itself. [...]
> While it appears generally harmless, since the list does appear to be
> correctly sorted, it is doing extra work needlessly.

There are sort algorithms where this happens naturally, and adding
an additional check to avoid calling the comparison function when the
pointers are equal would be more work overall than just calling cmp().

This does not happen with list_sort()'s merge sort, but I've noticed
the following hack in merge_and_restore_back_links():

	do {
		/*
		 * 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->next, tail->next);

		tail->next->prev = tail;
		tail = tail->next;
	} while (tail->next);

When there is no cond_resched() call, this is indeed needless work.

However, if the list is so short that cond_resched() is not needed,
the additional comparisons should not hurt anyway.


Regards,
Clemens

Re: list sort

[Steven Whitehouse]

Hi,

On Wed, 2011-07-27 at 16:45 +0200, Clemens Ladisch wrote:
> Steven Whitehouse wrote:
> > There seems to be an issue with list_sort trying to compare an object to
> > itself. [...]
> > While it appears generally harmless, since the list does appear to be
> > correctly sorted, it is doing extra work needlessly.
> 
> There are sort algorithms where this happens naturally, and adding
> an additional check to avoid calling the comparison function when the
> pointers are equal would be more work overall than just calling cmp().
> 
> This does not happen with list_sort()'s merge sort, but I've noticed
> the following hack in merge_and_restore_back_links():
> 
> 	do {
> 		/*
> 		 * 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->next, tail->next);
> 
> 		tail->next->prev = tail;
> 		tail = tail->next;
> 	} while (tail->next);
> 
> When there is no cond_resched() call, this is indeed needless work.
> 
> However, if the list is so short that cond_resched() is not needed,
> the additional comparisons should not hurt anyway.
> 
> 
> Regards,
> Clemens

Ah, I see now... that makes some kind of sense I think. I didn't expect
the cmp routine to be dual purpose in that way,

Steve.