1d0da23b0SAndrew Morton 2d0da23b0SAndrew Morton #define pr_fmt(fmt) "list_sort_test: " fmt 3d0da23b0SAndrew Morton 42c761270SDave Chinner #include <linux/kernel.h> 57259fa04SRasmus Villemoes #include <linux/bug.h> 67259fa04SRasmus Villemoes #include <linux/compiler.h> 77259fa04SRasmus Villemoes #include <linux/export.h> 87259fa04SRasmus Villemoes #include <linux/string.h> 92c761270SDave Chinner #include <linux/list_sort.h> 102c761270SDave Chinner #include <linux/list.h> 112c761270SDave Chinner 12835cc0c8SDon Mullis #define MAX_LIST_LENGTH_BITS 20 13835cc0c8SDon Mullis 14835cc0c8SDon Mullis /* 15835cc0c8SDon Mullis * Returns a list organized in an intermediate format suited 16835cc0c8SDon Mullis * to chaining of merge() calls: null-terminated, no reserved or 17835cc0c8SDon Mullis * sentinel head node, "prev" links not maintained. 18835cc0c8SDon Mullis */ 19835cc0c8SDon Mullis static struct list_head *merge(void *priv, 20835cc0c8SDon Mullis int (*cmp)(void *priv, struct list_head *a, 21835cc0c8SDon Mullis struct list_head *b), 22835cc0c8SDon Mullis struct list_head *a, struct list_head *b) 23835cc0c8SDon Mullis { 24835cc0c8SDon Mullis struct list_head head, *tail = &head; 25835cc0c8SDon Mullis 26835cc0c8SDon Mullis while (a && b) { 27835cc0c8SDon Mullis /* if equal, take 'a' -- important for sort stability */ 28835cc0c8SDon Mullis if ((*cmp)(priv, a, b) <= 0) { 29835cc0c8SDon Mullis tail->next = a; 30835cc0c8SDon Mullis a = a->next; 31835cc0c8SDon Mullis } else { 32835cc0c8SDon Mullis tail->next = b; 33835cc0c8SDon Mullis b = b->next; 34835cc0c8SDon Mullis } 35835cc0c8SDon Mullis tail = tail->next; 36835cc0c8SDon Mullis } 37835cc0c8SDon Mullis tail->next = a?:b; 38835cc0c8SDon Mullis return head.next; 39835cc0c8SDon Mullis } 40835cc0c8SDon Mullis 41835cc0c8SDon Mullis /* 42835cc0c8SDon Mullis * Combine final list merge with restoration of standard doubly-linked 43835cc0c8SDon Mullis * list structure. This approach duplicates code from merge(), but 44835cc0c8SDon Mullis * runs faster than the tidier alternatives of either a separate final 45835cc0c8SDon Mullis * prev-link restoration pass, or maintaining the prev links 46835cc0c8SDon Mullis * throughout. 47835cc0c8SDon Mullis */ 48835cc0c8SDon Mullis static void merge_and_restore_back_links(void *priv, 49835cc0c8SDon Mullis int (*cmp)(void *priv, struct list_head *a, 50835cc0c8SDon Mullis struct list_head *b), 51835cc0c8SDon Mullis struct list_head *head, 52835cc0c8SDon Mullis struct list_head *a, struct list_head *b) 53835cc0c8SDon Mullis { 54835cc0c8SDon Mullis struct list_head *tail = head; 5561b3d6c4SRasmus Villemoes u8 count = 0; 56835cc0c8SDon Mullis 57835cc0c8SDon Mullis while (a && b) { 58835cc0c8SDon Mullis /* if equal, take 'a' -- important for sort stability */ 59835cc0c8SDon Mullis if ((*cmp)(priv, a, b) <= 0) { 60835cc0c8SDon Mullis tail->next = a; 61835cc0c8SDon Mullis a->prev = tail; 62835cc0c8SDon Mullis a = a->next; 63835cc0c8SDon Mullis } else { 64835cc0c8SDon Mullis tail->next = b; 65835cc0c8SDon Mullis b->prev = tail; 66835cc0c8SDon Mullis b = b->next; 67835cc0c8SDon Mullis } 68835cc0c8SDon Mullis tail = tail->next; 69835cc0c8SDon Mullis } 70835cc0c8SDon Mullis tail->next = a ? : b; 71835cc0c8SDon Mullis 72835cc0c8SDon Mullis do { 73835cc0c8SDon Mullis /* 74835cc0c8SDon Mullis * In worst cases this loop may run many iterations. 75835cc0c8SDon Mullis * Continue callbacks to the client even though no 76835cc0c8SDon Mullis * element comparison is needed, so the client's cmp() 77835cc0c8SDon Mullis * routine can invoke cond_resched() periodically. 78835cc0c8SDon Mullis */ 7961b3d6c4SRasmus Villemoes if (unlikely(!(++count))) 80f015ac3eSDon Mullis (*cmp)(priv, tail->next, tail->next); 81835cc0c8SDon Mullis 82835cc0c8SDon Mullis tail->next->prev = tail; 83835cc0c8SDon Mullis tail = tail->next; 84835cc0c8SDon Mullis } while (tail->next); 85835cc0c8SDon Mullis 86835cc0c8SDon Mullis tail->next = head; 87835cc0c8SDon Mullis head->prev = tail; 88835cc0c8SDon Mullis } 89835cc0c8SDon Mullis 902c761270SDave Chinner /** 9102b12b7aSDon Mullis * list_sort - sort a list 9202b12b7aSDon Mullis * @priv: private data, opaque to list_sort(), passed to @cmp 932c761270SDave Chinner * @head: the list to sort 942c761270SDave Chinner * @cmp: the elements comparison function 952c761270SDave Chinner * 9602b12b7aSDon Mullis * This function implements "merge sort", which has O(nlog(n)) 9702b12b7aSDon Mullis * complexity. 982c761270SDave Chinner * 9902b12b7aSDon Mullis * The comparison function @cmp must return a negative value if @a 10002b12b7aSDon Mullis * should sort before @b, and a positive value if @a should sort after 10102b12b7aSDon Mullis * @b. If @a and @b are equivalent, and their original relative 10202b12b7aSDon Mullis * ordering is to be preserved, @cmp must return 0. 1032c761270SDave Chinner */ 1042c761270SDave Chinner void list_sort(void *priv, struct list_head *head, 1052c761270SDave Chinner int (*cmp)(void *priv, struct list_head *a, 1062c761270SDave Chinner struct list_head *b)) 1072c761270SDave Chinner { 108835cc0c8SDon Mullis struct list_head *part[MAX_LIST_LENGTH_BITS+1]; /* sorted partial lists 109835cc0c8SDon Mullis -- last slot is a sentinel */ 110835cc0c8SDon Mullis int lev; /* index into part[] */ 111835cc0c8SDon Mullis int max_lev = 0; 112835cc0c8SDon Mullis struct list_head *list; 1132c761270SDave Chinner 1142c761270SDave Chinner if (list_empty(head)) 1152c761270SDave Chinner return; 1162c761270SDave Chinner 117835cc0c8SDon Mullis memset(part, 0, sizeof(part)); 118835cc0c8SDon Mullis 119835cc0c8SDon Mullis head->prev->next = NULL; 1202c761270SDave Chinner list = head->next; 1212c761270SDave Chinner 122835cc0c8SDon Mullis while (list) { 123835cc0c8SDon Mullis struct list_head *cur = list; 124835cc0c8SDon Mullis list = list->next; 125835cc0c8SDon Mullis cur->next = NULL; 126835cc0c8SDon Mullis 127835cc0c8SDon Mullis for (lev = 0; part[lev]; lev++) { 128835cc0c8SDon Mullis cur = merge(priv, cmp, part[lev], cur); 129835cc0c8SDon Mullis part[lev] = NULL; 130835cc0c8SDon Mullis } 131835cc0c8SDon Mullis if (lev > max_lev) { 132835cc0c8SDon Mullis if (unlikely(lev >= ARRAY_SIZE(part)-1)) { 133d0da23b0SAndrew Morton printk_once(KERN_DEBUG "list too long for efficiency\n"); 134835cc0c8SDon Mullis lev--; 135835cc0c8SDon Mullis } 136835cc0c8SDon Mullis max_lev = lev; 137835cc0c8SDon Mullis } 138835cc0c8SDon Mullis part[lev] = cur; 1392c761270SDave Chinner } 1402c761270SDave Chinner 141835cc0c8SDon Mullis for (lev = 0; lev < max_lev; lev++) 142835cc0c8SDon Mullis if (part[lev]) 143835cc0c8SDon Mullis list = merge(priv, cmp, part[lev], list); 1442c761270SDave Chinner 145835cc0c8SDon Mullis merge_and_restore_back_links(priv, cmp, head, part[max_lev], list); 1462c761270SDave Chinner } 1472c761270SDave Chinner EXPORT_SYMBOL(list_sort); 148835cc0c8SDon Mullis 1496d411e6cSArtem Bityutskiy #ifdef CONFIG_TEST_LIST_SORT 150eeee9ebbSArtem Bityutskiy 1517259fa04SRasmus Villemoes #include <linux/slab.h> 152eeee9ebbSArtem Bityutskiy #include <linux/random.h> 153eeee9ebbSArtem Bityutskiy 154835cc0c8SDon Mullis /* 155835cc0c8SDon Mullis * The pattern of set bits in the list length determines which cases 156835cc0c8SDon Mullis * are hit in list_sort(). 157835cc0c8SDon Mullis */ 158eeee9ebbSArtem Bityutskiy #define TEST_LIST_LEN (512+128+2) /* not including head */ 159835cc0c8SDon Mullis 160041b78f2SArtem Bityutskiy #define TEST_POISON1 0xDEADBEEF 161041b78f2SArtem Bityutskiy #define TEST_POISON2 0xA324354C 162041b78f2SArtem Bityutskiy 163041b78f2SArtem Bityutskiy struct debug_el { 164041b78f2SArtem Bityutskiy unsigned int poison1; 165041b78f2SArtem Bityutskiy struct list_head list; 166041b78f2SArtem Bityutskiy unsigned int poison2; 167041b78f2SArtem Bityutskiy int value; 168041b78f2SArtem Bityutskiy unsigned serial; 169041b78f2SArtem Bityutskiy }; 170041b78f2SArtem Bityutskiy 171041b78f2SArtem Bityutskiy /* Array, containing pointers to all elements in the test list */ 172041b78f2SArtem Bityutskiy static struct debug_el **elts __initdata; 173041b78f2SArtem Bityutskiy 174041b78f2SArtem Bityutskiy static int __init check(struct debug_el *ela, struct debug_el *elb) 175041b78f2SArtem Bityutskiy { 176041b78f2SArtem Bityutskiy if (ela->serial >= TEST_LIST_LEN) { 177d0da23b0SAndrew Morton pr_err("error: incorrect serial %d\n", ela->serial); 178041b78f2SArtem Bityutskiy return -EINVAL; 179041b78f2SArtem Bityutskiy } 180041b78f2SArtem Bityutskiy if (elb->serial >= TEST_LIST_LEN) { 181d0da23b0SAndrew Morton pr_err("error: incorrect serial %d\n", elb->serial); 182041b78f2SArtem Bityutskiy return -EINVAL; 183041b78f2SArtem Bityutskiy } 184041b78f2SArtem Bityutskiy if (elts[ela->serial] != ela || elts[elb->serial] != elb) { 185d0da23b0SAndrew Morton pr_err("error: phantom element\n"); 186041b78f2SArtem Bityutskiy return -EINVAL; 187041b78f2SArtem Bityutskiy } 188041b78f2SArtem Bityutskiy if (ela->poison1 != TEST_POISON1 || ela->poison2 != TEST_POISON2) { 189d0da23b0SAndrew Morton pr_err("error: bad poison: %#x/%#x\n", 190041b78f2SArtem Bityutskiy ela->poison1, ela->poison2); 191041b78f2SArtem Bityutskiy return -EINVAL; 192041b78f2SArtem Bityutskiy } 193041b78f2SArtem Bityutskiy if (elb->poison1 != TEST_POISON1 || elb->poison2 != TEST_POISON2) { 194d0da23b0SAndrew Morton pr_err("error: bad poison: %#x/%#x\n", 195041b78f2SArtem Bityutskiy elb->poison1, elb->poison2); 196041b78f2SArtem Bityutskiy return -EINVAL; 197041b78f2SArtem Bityutskiy } 198041b78f2SArtem Bityutskiy return 0; 199041b78f2SArtem Bityutskiy } 200041b78f2SArtem Bityutskiy 201041b78f2SArtem Bityutskiy static int __init cmp(void *priv, struct list_head *a, struct list_head *b) 202041b78f2SArtem Bityutskiy { 203041b78f2SArtem Bityutskiy struct debug_el *ela, *elb; 204041b78f2SArtem Bityutskiy 205041b78f2SArtem Bityutskiy ela = container_of(a, struct debug_el, list); 206041b78f2SArtem Bityutskiy elb = container_of(b, struct debug_el, list); 207041b78f2SArtem Bityutskiy 208041b78f2SArtem Bityutskiy check(ela, elb); 209041b78f2SArtem Bityutskiy return ela->value - elb->value; 210041b78f2SArtem Bityutskiy } 211041b78f2SArtem Bityutskiy 212835cc0c8SDon Mullis static int __init list_sort_test(void) 213835cc0c8SDon Mullis { 21427d555d1SRasmus Villemoes int i, count = 1, err = -ENOMEM; 215f3dc0e38SArtem Bityutskiy struct debug_el *el; 21669412303SRasmus Villemoes struct list_head *cur; 217f3dc0e38SArtem Bityutskiy LIST_HEAD(head); 218835cc0c8SDon Mullis 219d0da23b0SAndrew Morton pr_debug("start testing list_sort()\n"); 220835cc0c8SDon Mullis 22169412303SRasmus Villemoes elts = kcalloc(TEST_LIST_LEN, sizeof(*elts), GFP_KERNEL); 222041b78f2SArtem Bityutskiy if (!elts) { 223d0da23b0SAndrew Morton pr_err("error: cannot allocate memory\n"); 22469412303SRasmus Villemoes return err; 225041b78f2SArtem Bityutskiy } 226041b78f2SArtem Bityutskiy 227eeee9ebbSArtem Bityutskiy for (i = 0; i < TEST_LIST_LEN; i++) { 228f3dc0e38SArtem Bityutskiy el = kmalloc(sizeof(*el), GFP_KERNEL); 229f3dc0e38SArtem Bityutskiy if (!el) { 230d0da23b0SAndrew Morton pr_err("error: cannot allocate memory\n"); 231f3dc0e38SArtem Bityutskiy goto exit; 232f3dc0e38SArtem Bityutskiy } 233835cc0c8SDon Mullis /* force some equivalencies */ 234f39fee5fSAkinobu Mita el->value = prandom_u32() % (TEST_LIST_LEN / 3); 235835cc0c8SDon Mullis el->serial = i; 236041b78f2SArtem Bityutskiy el->poison1 = TEST_POISON1; 237041b78f2SArtem Bityutskiy el->poison2 = TEST_POISON2; 238041b78f2SArtem Bityutskiy elts[i] = el; 239f3dc0e38SArtem Bityutskiy list_add_tail(&el->list, &head); 240835cc0c8SDon Mullis } 241835cc0c8SDon Mullis 242f3dc0e38SArtem Bityutskiy list_sort(NULL, &head, cmp); 243835cc0c8SDon Mullis 24427d555d1SRasmus Villemoes err = -EINVAL; 245f3dc0e38SArtem Bityutskiy for (cur = head.next; cur->next != &head; cur = cur->next) { 246f3dc0e38SArtem Bityutskiy struct debug_el *el1; 247f3dc0e38SArtem Bityutskiy int cmp_result; 248f3dc0e38SArtem Bityutskiy 249835cc0c8SDon Mullis if (cur->next->prev != cur) { 250d0da23b0SAndrew Morton pr_err("error: list is corrupted\n"); 251f3dc0e38SArtem Bityutskiy goto exit; 252f3dc0e38SArtem Bityutskiy } 253f3dc0e38SArtem Bityutskiy 254f3dc0e38SArtem Bityutskiy cmp_result = cmp(NULL, cur, cur->next); 255f3dc0e38SArtem Bityutskiy if (cmp_result > 0) { 256d0da23b0SAndrew Morton pr_err("error: list is not sorted\n"); 257f3dc0e38SArtem Bityutskiy goto exit; 258f3dc0e38SArtem Bityutskiy } 259f3dc0e38SArtem Bityutskiy 260f3dc0e38SArtem Bityutskiy el = container_of(cur, struct debug_el, list); 261f3dc0e38SArtem Bityutskiy el1 = container_of(cur->next, struct debug_el, list); 262f3dc0e38SArtem Bityutskiy if (cmp_result == 0 && el->serial >= el1->serial) { 263d0da23b0SAndrew Morton pr_err("error: order of equivalent elements not " 264d0da23b0SAndrew Morton "preserved\n"); 265f3dc0e38SArtem Bityutskiy goto exit; 266835cc0c8SDon Mullis } 267041b78f2SArtem Bityutskiy 268041b78f2SArtem Bityutskiy if (check(el, el1)) { 269d0da23b0SAndrew Morton pr_err("error: element check failed\n"); 270041b78f2SArtem Bityutskiy goto exit; 271041b78f2SArtem Bityutskiy } 272835cc0c8SDon Mullis count++; 273835cc0c8SDon Mullis } 2749d418dccSRasmus Villemoes if (head.prev != cur) { 275d0da23b0SAndrew Morton pr_err("error: list is corrupted\n"); 2769d418dccSRasmus Villemoes goto exit; 2779d418dccSRasmus Villemoes } 2789d418dccSRasmus Villemoes 279f3dc0e38SArtem Bityutskiy 280eeee9ebbSArtem Bityutskiy if (count != TEST_LIST_LEN) { 281d0da23b0SAndrew Morton pr_err("error: bad list length %d", count); 282f3dc0e38SArtem Bityutskiy goto exit; 283835cc0c8SDon Mullis } 284f3dc0e38SArtem Bityutskiy 285f3dc0e38SArtem Bityutskiy err = 0; 286f3dc0e38SArtem Bityutskiy exit: 28769412303SRasmus Villemoes for (i = 0; i < TEST_LIST_LEN; i++) 28869412303SRasmus Villemoes kfree(elts[i]); 289041b78f2SArtem Bityutskiy kfree(elts); 290f3dc0e38SArtem Bityutskiy return err; 291835cc0c8SDon Mullis } 292835cc0c8SDon Mullis module_init(list_sort_test); 2936d411e6cSArtem Bityutskiy #endif /* CONFIG_TEST_LIST_SORT */ 294