1 files changed, 262 insertions, 73 deletions
diff --git a/lib/list_sort.c b/lib/list_sort.c
index 19d11e0bb958..d7325c6b103f 100644
--- a/lib/list_sort.c
+++ b/lib/list_sort.c
@@ -4,99 +4,288 @@
 #include <linux/slab.h>
 #include <linux/list.h>
+#define MAX_LIST_LENGTH_BITS 20
+/*
+ * Returns a list organized in an intermediate format suited
+ * to chaining of merge() calls: null-terminated, no reserved or
+ * sentinel head node, "prev" links not maintained.
+ */
+static struct list_head *merge(void *priv,
+                                int (*cmp)(void *priv, struct list_head *a,
+                                        struct list_head *b),
+                                struct list_head *a, struct list_head *b)
+{
+        struct list_head head, *tail = &head;
+        while (a && b) {
+                /* if equal, take 'a' -- important for sort stability */
+                if ((*cmp)(priv, a, b) <= 0) {
+                        tail->next = a;
+                        a = a->next;
+                } else {
+                        tail->next = b;
+                        b = b->next;
+                }
+                tail = tail->next;
+        }
+        tail->next = a?:b;
+        return head.next;
+}
+/*
+ * Combine final list merge with restoration of standard doubly-linked
+ * list structure.  This approach duplicates code from merge(), but
+ * runs faster than the tidier alternatives of either a separate final
+ * prev-link restoration pass, or maintaining the prev links
+ * throughout.
+ */
+static void merge_and_restore_back_links(void *priv,
+                                int (*cmp)(void *priv, struct list_head *a,
+                                        struct list_head *b),
+                                struct list_head *head,
+                                struct list_head *a, struct list_head *b)
+{
+        struct list_head *tail = head;
+        while (a && b) {
+                /* if equal, take 'a' -- important for sort stability */
+                if ((*cmp)(priv, a, b) <= 0) {
+                        tail->next = a;
+                        a->prev = tail;
+                        a = a->next;
+                } else {
+                        tail->next = b;
+                        b->prev = tail;
+                        b = b->next;
+                }
+                tail = tail->next;
+        }
+        tail->next = a ? : b;
+        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);
+        tail->next = head;
+        head->prev = tail;
+}
 /**
- * list_sort - sort a list.
+ * list_sort - sort a list
- * @priv: private data, passed to @cmp
+ * @priv: private data, opaque to list_sort(), passed to @cmp
 * @head: the list to sort
 * @cmp: the elements comparison function
 *
- * This function has been implemented by Mark J Roberts <mjr@znex.org>. It
+ * This function implements "merge sort", which has O(nlog(n))
- * implements "merge sort" which has O(nlog(n)) complexity. The list is sorted
+ * complexity.
- * in ascending order.
 *
- * The comparison function @cmp is supposed to return a negative value if @a is
+ * The comparison function @cmp must return a negative value if @a
- * less than @b, and a positive value if @a is greater than @b. If @a and @b
+ * should sort before @b, and a positive value if @a should sort after
- * are equivalent, then it does not matter what this function returns.
+ * @b. If @a and @b are equivalent, and their original relative
+ * ordering is to be preserved, @cmp must return 0.
 */
 void list_sort(void *priv, struct list_head *head,
-               int (*cmp)(void *priv, struct list_head *a,
+                int (*cmp)(void *priv, struct list_head *a,
-                          struct list_head *b))
+                        struct list_head *b))
 {
-        struct list_head *p, *q, *e, *list, *tail, *oldhead;
+        struct list_head *part[MAX_LIST_LENGTH_BITS+1]; /* sorted partial lists
-        int insize, nmerges, psize, qsize, i;
+                                                -- last slot is a sentinel */
+        int lev;  /* index into part[] */
+        int max_lev = 0;
+        struct list_head *list;
        if (list_empty(head))
                return;
+        memset(part, 0, sizeof(part));
+        head->prev->next = NULL;
        list = head->next;
-        list_del(head);
-        insize = 1;
-        for (;;) {
-                p = oldhead = list;
-                list = tail = NULL;
-                nmerges = 0;
-                while (p) {
-                        nmerges++;
-                        q = p;
-                        psize = 0;
-                        for (i = 0; i < insize; i++) {
-                                psize++;
-                                q = q->next == oldhead ? NULL : q->next;
-                                if (!q)
-                                        break;
-                        }
-                        qsize = insize;
+        while (list) {
-                        while (psize > 0 || (qsize > 0 && q)) {
+                struct list_head *cur = list;
-                                if (!psize) {
+                list = list->next;
-                                        e = q;
+                cur->next = NULL;
-                                        q = q->next;
-                                        qsize--;
+                for (lev = 0; part[lev]; lev++) {
-                                        if (q == oldhead)
+                        cur = merge(priv, cmp, part[lev], cur);
-                                                q = NULL;
+                        part[lev] = NULL;
-                                } else if (!qsize || !q) {
+                }
-                                        e = p;
+                if (lev > max_lev) {
-                                        p = p->next;
+                        if (unlikely(lev >= ARRAY_SIZE(part)-1)) {
-                                        psize--;
+                                printk_once(KERN_DEBUG "list passed to"
-                                        if (p == oldhead)
+                                        " list_sort() too long for"
-                                                p = NULL;
+                                        " efficiency\n");
-                                } else if (cmp(priv, p, q) <= 0) {
+                                lev--;
-                                        e = p;
-                                        p = p->next;
-                                        psize--;
-                                        if (p == oldhead)
-                                                p = NULL;
-                                } else {
-                                        e = q;
-                                        q = q->next;
-                                        qsize--;
-                                        if (q == oldhead)
-                                                q = NULL;
-                                }
-                                if (tail)
-                                        tail->next = e;
-                                else
-                                        list = e;
-                                e->prev = tail;
-                                tail = e;
                        }
-                        p = q;
+                        max_lev = lev;
                }
+                part[lev] = cur;
+        }
+        for (lev = 0; lev < max_lev; lev++)
+                if (part[lev])
+                        list = merge(priv, cmp, part[lev], list);
+        merge_and_restore_back_links(priv, cmp, head, part[max_lev], list);
+}
+EXPORT_SYMBOL(list_sort);
+#ifdef CONFIG_TEST_LIST_SORT
+#include <linux/random.h>
-                tail->next = list;
+/*
-                list->prev = tail;
+ * The pattern of set bits in the list length determines which cases
+ * are hit in list_sort().
+ */
+#define TEST_LIST_LEN (512+128+2) /* not including head */
+#define TEST_POISON1 0xDEADBEEF
+#define TEST_POISON2 0xA324354C
-                if (nmerges <= 1)
+struct debug_el {
-                        break;
+        unsigned int poison1;
+        struct list_head list;
+        unsigned int poison2;
+        int value;
+        unsigned serial;
+};
-                insize *= 2;
+/* Array, containing pointers to all elements in the test list */
+static struct debug_el **elts __initdata;
+static int __init check(struct debug_el *ela, struct debug_el *elb)
+{
+        if (ela->serial >= TEST_LIST_LEN) {
+                printk(KERN_ERR "list_sort_test: error: incorrect serial %d\n",
+                                ela->serial);
+                return -EINVAL;
        }
+        if (elb->serial >= TEST_LIST_LEN) {
+                printk(KERN_ERR "list_sort_test: error: incorrect serial %d\n",
+                                elb->serial);
+                return -EINVAL;
+        }
+        if (elts[ela->serial] != ela || elts[elb->serial] != elb) {
+                printk(KERN_ERR "list_sort_test: error: phantom element\n");
+                return -EINVAL;
+        }
+        if (ela->poison1 != TEST_POISON1 || ela->poison2 != TEST_POISON2) {
+                printk(KERN_ERR "list_sort_test: error: bad poison: %#x/%#x\n",
+                                ela->poison1, ela->poison2);
+                return -EINVAL;
+        }
+        if (elb->poison1 != TEST_POISON1 || elb->poison2 != TEST_POISON2) {
+                printk(KERN_ERR "list_sort_test: error: bad poison: %#x/%#x\n",
+                                elb->poison1, elb->poison2);
+                return -EINVAL;
+        }
+        return 0;
+}
+static int __init cmp(void *priv, struct list_head *a, struct list_head *b)
+{
+        struct debug_el *ela, *elb;
+        ela = container_of(a, struct debug_el, list);
+        elb = container_of(b, struct debug_el, list);
-        head->next = list;
+        check(ela, elb);
-        head->prev = list->prev;
+        return ela->value - elb->value;
-        list->prev->next = head;
-        list->prev = head;
 }
-EXPORT_SYMBOL(list_sort);
+static int __init list_sort_test(void)
+{
+        int i, count = 1, err = -EINVAL;
+        struct debug_el *el;
+        struct list_head *cur, *tmp;
+        LIST_HEAD(head);
+        printk(KERN_DEBUG "list_sort_test: start testing list_sort()\n");
+        elts = kmalloc(sizeof(void *) * TEST_LIST_LEN, GFP_KERNEL);
+        if (!elts) {
+                printk(KERN_ERR "list_sort_test: error: cannot allocate "
+                                "memory\n");
+                goto exit;
+        }
+        for (i = 0; i < TEST_LIST_LEN; i++) {
+                el = kmalloc(sizeof(*el), GFP_KERNEL);
+                if (!el) {
+                        printk(KERN_ERR "list_sort_test: error: cannot "
+                                        "allocate memory\n");
+                        goto exit;
+                }
+                 /* force some equivalencies */
+                el->value = random32() % (TEST_LIST_LEN/3);
+                el->serial = i;
+                el->poison1 = TEST_POISON1;
+                el->poison2 = TEST_POISON2;
+                elts[i] = el;
+                list_add_tail(&el->list, &head);
+        }
+        list_sort(NULL, &head, cmp);
+        for (cur = head.next; cur->next != &head; cur = cur->next) {
+                struct debug_el *el1;
+                int cmp_result;
+                if (cur->next->prev != cur) {
+                        printk(KERN_ERR "list_sort_test: error: list is "
+                                        "corrupted\n");
+                        goto exit;
+                }
+                cmp_result = cmp(NULL, cur, cur->next);
+                if (cmp_result > 0) {
+                        printk(KERN_ERR "list_sort_test: error: list is not "
+                                        "sorted\n");
+                        goto exit;
+                }
+                el = container_of(cur, struct debug_el, list);
+                el1 = container_of(cur->next, struct debug_el, list);
+                if (cmp_result == 0 && el->serial >= el1->serial) {
+                        printk(KERN_ERR "list_sort_test: error: order of "
+                                        "equivalent elements not preserved\n");
+                        goto exit;
+                }
+                if (check(el, el1)) {
+                        printk(KERN_ERR "list_sort_test: error: element check "
+                                        "failed\n");
+                        goto exit;
+                }
+                count++;
+        }
+        if (count != TEST_LIST_LEN) {
+                printk(KERN_ERR "list_sort_test: error: bad list length %d",
+                                count);
+                goto exit;
+        }
+        err = 0;
+exit:
+        kfree(elts);
+        list_for_each_safe(cur, tmp, &head) {
+                list_del(cur);
+                kfree(container_of(cur, struct debug_el, list));
+        }
+        return err;
+}
+module_init(list_sort_test);
+#endif /* CONFIG_TEST_LIST_SORT */

diff --git a/lib/list_sort.c b/lib/list_sort.c index 19d11e0bb958..d7325c6b103f 100644 --- a/lib/list_sort.c +++ b/lib/list_sort.c
@@ -4,99 +4,288 @@
4	#include <linux/slab.h>	4	#include <linux/slab.h>
5	#include <linux/list.h>	5	#include <linux/list.h>
6		6
		7	#define MAX_LIST_LENGTH_BITS 20
		8
		9	/*
		10	* Returns a list organized in an intermediate format suited
		11	* to chaining of merge() calls: null-terminated, no reserved or
		12	* sentinel head node, "prev" links not maintained.
		13	*/
		14	static struct list_head merge(void priv,
		15	int (cmp)(void priv, struct list_head *a,
		16	struct list_head *b),
		17	struct list_head a, struct list_head b)
		18	{
		19	struct list_head head, *tail = &head;
		20
		21	while (a && b) {
		22	/* if equal, take 'a' -- important for sort stability */
		23	if ((*cmp)(priv, a, b) <= 0) {
		24	tail->next = a;
		25	a = a->next;
		26	} else {
		27	tail->next = b;
		28	b = b->next;
		29	}
		30	tail = tail->next;
		31	}
		32	tail->next = a?:b;
		33	return head.next;
		34	}
		35
		36	/*
		37	* Combine final list merge with restoration of standard doubly-linked
		38	* list structure. This approach duplicates code from merge(), but
		39	* runs faster than the tidier alternatives of either a separate final
		40	* prev-link restoration pass, or maintaining the prev links
		41	* throughout.
		42	*/
		43	static void merge_and_restore_back_links(void *priv,
		44	int (cmp)(void priv, struct list_head *a,
		45	struct list_head *b),
		46	struct list_head *head,
		47	struct list_head a, struct list_head b)
		48	{
		49	struct list_head *tail = head;
		50
		51	while (a && b) {
		52	/* if equal, take 'a' -- important for sort stability */
		53	if ((*cmp)(priv, a, b) <= 0) {
		54	tail->next = a;
		55	a->prev = tail;
		56	a = a->next;
		57	} else {
		58	tail->next = b;
		59	b->prev = tail;
		60	b = b->next;
		61	}
		62	tail = tail->next;
		63	}
		64	tail->next = a ? : b;
		65
		66	do {
		67	/*
		68	* In worst cases this loop may run many iterations.
		69	* Continue callbacks to the client even though no
		70	* element comparison is needed, so the client's cmp()
		71	* routine can invoke cond_resched() periodically.
		72	*/
		73	(*cmp)(priv, tail->next, tail->next);
		74
		75	tail->next->prev = tail;
		76	tail = tail->next;
		77	} while (tail->next);
		78
		79	tail->next = head;
		80	head->prev = tail;
		81	}
		82
7	/**	83	/**
8	* list_sort - sort a list.	84	* list_sort - sort a list
9	* @priv: private data, passed to @cmp	85	* @priv: private data, opaque to list_sort(), passed to @cmp
10	* @head: the list to sort	86	* @head: the list to sort
11	* @cmp: the elements comparison function	87	* @cmp: the elements comparison function
12	*	88	*
13	* This function has been implemented by Mark J Roberts <mjr@znex.org>. It	89	* This function implements "merge sort", which has O(nlog(n))
14	* implements "merge sort" which has O(nlog(n)) complexity. The list is sorted	90	* complexity.
15	* in ascending order.
16	*	91	*
17	* The comparison function @cmp is supposed to return a negative value if @a is	92	* The comparison function @cmp must return a negative value if @a
18	* less than @b, and a positive value if @a is greater than @b. If @a and @b	93	* should sort before @b, and a positive value if @a should sort after
19	* are equivalent, then it does not matter what this function returns.	94	* @b. If @a and @b are equivalent, and their original relative
		95	* ordering is to be preserved, @cmp must return 0.
20	*/	96	*/
21	void list_sort(void priv, struct list_head head,	97	void list_sort(void priv, struct list_head head,
22	int (cmp)(void priv, struct list_head *a,	98	int (cmp)(void priv, struct list_head *a,
23	struct list_head *b))	99	struct list_head *b))
24	{	100	{
25	struct list_head p, q, e, list, tail, oldhead;	101	struct list_head part[MAX_LIST_LENGTH_BITS+1]; / sorted partial lists
26	int insize, nmerges, psize, qsize, i;	102	-- last slot is a sentinel */
		103	int lev; /* index into part[] */
		104	int max_lev = 0;
		105	struct list_head *list;
27		106
28	if (list_empty(head))	107	if (list_empty(head))
29	return;	108	return;
30		109
		110	memset(part, 0, sizeof(part));
		111
		112	head->prev->next = NULL;
31	list = head->next;	113	list = head->next;
32	list_del(head);
33	insize = 1;
34	for (;;) {
35	p = oldhead = list;
36	list = tail = NULL;
37	nmerges = 0;
38
39	while (p) {
40	nmerges++;
41	q = p;
42	psize = 0;
43	for (i = 0; i < insize; i++) {
44	psize++;
45	q = q->next == oldhead ? NULL : q->next;
46	if (!q)
47	break;
48	}
49		114
50	qsize = insize;	115	while (list) {
51	while (psize > 0 \|\| (qsize > 0 && q)) {	116	struct list_head *cur = list;
52	if (!psize) {	117	list = list->next;
53	e = q;	118	cur->next = NULL;
54	q = q->next;	119
55	qsize--;	120	for (lev = 0; part[lev]; lev++) {
56	if (q == oldhead)	121	cur = merge(priv, cmp, part[lev], cur);
57	q = NULL;	122	part[lev] = NULL;
58	} else if (!qsize \|\| !q) {	123	}
59	e = p;	124	if (lev > max_lev) {
60	p = p->next;	125	if (unlikely(lev >= ARRAY_SIZE(part)-1)) {
61	psize--;	126	printk_once(KERN_DEBUG "list passed to"
62	if (p == oldhead)	127	" list_sort() too long for"
63	p = NULL;	128	" efficiency\n");
64	} else if (cmp(priv, p, q) <= 0) {	129	lev--;
65	e = p;
66	p = p->next;
67	psize--;
68	if (p == oldhead)
69	p = NULL;
70	} else {
71	e = q;
72	q = q->next;
73	qsize--;
74	if (q == oldhead)
75	q = NULL;
76	}
77	if (tail)
78	tail->next = e;
79	else
80	list = e;
81	e->prev = tail;
82	tail = e;
83	}	130	}
84	p = q;	131	max_lev = lev;
85	}	132	}
		133	part[lev] = cur;
		134	}
		135
		136	for (lev = 0; lev < max_lev; lev++)
		137	if (part[lev])
		138	list = merge(priv, cmp, part[lev], list);
		139
		140	merge_and_restore_back_links(priv, cmp, head, part[max_lev], list);
		141	}
		142	EXPORT_SYMBOL(list_sort);
		143
		144	#ifdef CONFIG_TEST_LIST_SORT
		145
		146	#include <linux/random.h>
86		147
87	tail->next = list;	148	/*
88	list->prev = tail;	149	* The pattern of set bits in the list length determines which cases
		150	* are hit in list_sort().
		151	*/
		152	#define TEST_LIST_LEN (512+128+2) /* not including head */
		153
		154	#define TEST_POISON1 0xDEADBEEF
		155	#define TEST_POISON2 0xA324354C
89		156
90	if (nmerges <= 1)	157	struct debug_el {
91	break;	158	unsigned int poison1;
		159	struct list_head list;
		160	unsigned int poison2;
		161	int value;
		162	unsigned serial;
		163	};
92		164
93	insize *= 2;	165	/* Array, containing pointers to all elements in the test list */
		166	static struct debug_el **elts __initdata;
		167
		168	static int __init check(struct debug_el ela, struct debug_el elb)
		169	{
		170	if (ela->serial >= TEST_LIST_LEN) {
		171	printk(KERN_ERR "list_sort_test: error: incorrect serial %d\n",
		172	ela->serial);
		173	return -EINVAL;
94	}	174	}
		175	if (elb->serial >= TEST_LIST_LEN) {
		176	printk(KERN_ERR "list_sort_test: error: incorrect serial %d\n",
		177	elb->serial);
		178	return -EINVAL;
		179	}
		180	if (elts[ela->serial] != ela \|\| elts[elb->serial] != elb) {
		181	printk(KERN_ERR "list_sort_test: error: phantom element\n");
		182	return -EINVAL;
		183	}
		184	if (ela->poison1 != TEST_POISON1 \|\| ela->poison2 != TEST_POISON2) {
		185	printk(KERN_ERR "list_sort_test: error: bad poison: %#x/%#x\n",
		186	ela->poison1, ela->poison2);
		187	return -EINVAL;
		188	}
		189	if (elb->poison1 != TEST_POISON1 \|\| elb->poison2 != TEST_POISON2) {
		190	printk(KERN_ERR "list_sort_test: error: bad poison: %#x/%#x\n",
		191	elb->poison1, elb->poison2);
		192	return -EINVAL;
		193	}
		194	return 0;
		195	}
		196
		197	static int __init cmp(void priv, struct list_head a, struct list_head *b)
		198	{
		199	struct debug_el ela, elb;
		200
		201	ela = container_of(a, struct debug_el, list);
		202	elb = container_of(b, struct debug_el, list);
95		203
96	head->next = list;	204	check(ela, elb);
97	head->prev = list->prev;	205	return ela->value - elb->value;
98	list->prev->next = head;
99	list->prev = head;
100	}	206	}
101		207
102	EXPORT_SYMBOL(list_sort);	208	static int __init list_sort_test(void)
		209	{
		210	int i, count = 1, err = -EINVAL;
		211	struct debug_el *el;
		212	struct list_head cur, tmp;
		213	LIST_HEAD(head);
		214
		215	printk(KERN_DEBUG "list_sort_test: start testing list_sort()\n");
		216
		217	elts = kmalloc(sizeof(void ) TEST_LIST_LEN, GFP_KERNEL);
		218	if (!elts) {
		219	printk(KERN_ERR "list_sort_test: error: cannot allocate "
		220	"memory\n");
		221	goto exit;
		222	}
		223
		224	for (i = 0; i < TEST_LIST_LEN; i++) {
		225	el = kmalloc(sizeof(*el), GFP_KERNEL);
		226	if (!el) {
		227	printk(KERN_ERR "list_sort_test: error: cannot "
		228	"allocate memory\n");
		229	goto exit;
		230	}
		231	/* force some equivalencies */
		232	el->value = random32() % (TEST_LIST_LEN/3);
		233	el->serial = i;
		234	el->poison1 = TEST_POISON1;
		235	el->poison2 = TEST_POISON2;
		236	elts[i] = el;
		237	list_add_tail(&el->list, &head);
		238	}
		239
		240	list_sort(NULL, &head, cmp);
		241
		242	for (cur = head.next; cur->next != &head; cur = cur->next) {
		243	struct debug_el *el1;
		244	int cmp_result;
		245
		246	if (cur->next->prev != cur) {
		247	printk(KERN_ERR "list_sort_test: error: list is "
		248	"corrupted\n");
		249	goto exit;
		250	}
		251
		252	cmp_result = cmp(NULL, cur, cur->next);
		253	if (cmp_result > 0) {
		254	printk(KERN_ERR "list_sort_test: error: list is not "
		255	"sorted\n");
		256	goto exit;
		257	}
		258
		259	el = container_of(cur, struct debug_el, list);
		260	el1 = container_of(cur->next, struct debug_el, list);
		261	if (cmp_result == 0 && el->serial >= el1->serial) {
		262	printk(KERN_ERR "list_sort_test: error: order of "
		263	"equivalent elements not preserved\n");
		264	goto exit;
		265	}
		266
		267	if (check(el, el1)) {
		268	printk(KERN_ERR "list_sort_test: error: element check "
		269	"failed\n");
		270	goto exit;
		271	}
		272	count++;
		273	}
		274
		275	if (count != TEST_LIST_LEN) {
		276	printk(KERN_ERR "list_sort_test: error: bad list length %d",
		277	count);
		278	goto exit;
		279	}
		280
		281	err = 0;
		282	exit:
		283	kfree(elts);
		284	list_for_each_safe(cur, tmp, &head) {
		285	list_del(cur);
		286	kfree(container_of(cur, struct debug_el, list));
		287	}
		288	return err;
		289	}
		290	module_init(list_sort_test);
		291	#endif /* CONFIG_TEST_LIST_SORT */