12c761270SDave Chinner #include <linux/kernel.h> 22c761270SDave Chinner #include <linux/module.h> 32c761270SDave Chinner #include <linux/list_sort.h> 42c761270SDave Chinner #include <linux/slab.h> 52c761270SDave Chinner #include <linux/list.h> 62c761270SDave Chinner 7835cc0c8SDon Mullis #define MAX_LIST_LENGTH_BITS 20 8835cc0c8SDon Mullis 9835cc0c8SDon Mullis /* 10835cc0c8SDon Mullis * Returns a list organized in an intermediate format suited 11835cc0c8SDon Mullis * to chaining of merge() calls: null-terminated, no reserved or 12835cc0c8SDon Mullis * sentinel head node, "prev" links not maintained. 13835cc0c8SDon Mullis */ 14835cc0c8SDon Mullis static struct list_head *merge(void *priv, 15835cc0c8SDon Mullis int (*cmp)(void *priv, struct list_head *a, 16835cc0c8SDon Mullis struct list_head *b), 17835cc0c8SDon Mullis struct list_head *a, struct list_head *b) 18835cc0c8SDon Mullis { 19835cc0c8SDon Mullis struct list_head head, *tail = &head; 20835cc0c8SDon Mullis 21835cc0c8SDon Mullis while (a && b) { 22835cc0c8SDon Mullis /* if equal, take 'a' -- important for sort stability */ 23835cc0c8SDon Mullis if ((*cmp)(priv, a, b) <= 0) { 24835cc0c8SDon Mullis tail->next = a; 25835cc0c8SDon Mullis a = a->next; 26835cc0c8SDon Mullis } else { 27835cc0c8SDon Mullis tail->next = b; 28835cc0c8SDon Mullis b = b->next; 29835cc0c8SDon Mullis } 30835cc0c8SDon Mullis tail = tail->next; 31835cc0c8SDon Mullis } 32835cc0c8SDon Mullis tail->next = a?:b; 33835cc0c8SDon Mullis return head.next; 34835cc0c8SDon Mullis } 35835cc0c8SDon Mullis 36835cc0c8SDon Mullis /* 37835cc0c8SDon Mullis * Combine final list merge with restoration of standard doubly-linked 38835cc0c8SDon Mullis * list structure. This approach duplicates code from merge(), but 39835cc0c8SDon Mullis * runs faster than the tidier alternatives of either a separate final 40835cc0c8SDon Mullis * prev-link restoration pass, or maintaining the prev links 41835cc0c8SDon Mullis * throughout. 42835cc0c8SDon Mullis */ 43835cc0c8SDon Mullis static void merge_and_restore_back_links(void *priv, 44835cc0c8SDon Mullis int (*cmp)(void *priv, struct list_head *a, 45835cc0c8SDon Mullis struct list_head *b), 46835cc0c8SDon Mullis struct list_head *head, 47835cc0c8SDon Mullis struct list_head *a, struct list_head *b) 48835cc0c8SDon Mullis { 49835cc0c8SDon Mullis struct list_head *tail = head; 5061b3d6c4SRasmus Villemoes u8 count = 0; 51835cc0c8SDon Mullis 52835cc0c8SDon Mullis while (a && b) { 53835cc0c8SDon Mullis /* if equal, take 'a' -- important for sort stability */ 54835cc0c8SDon Mullis if ((*cmp)(priv, a, b) <= 0) { 55835cc0c8SDon Mullis tail->next = a; 56835cc0c8SDon Mullis a->prev = tail; 57835cc0c8SDon Mullis a = a->next; 58835cc0c8SDon Mullis } else { 59835cc0c8SDon Mullis tail->next = b; 60835cc0c8SDon Mullis b->prev = tail; 61835cc0c8SDon Mullis b = b->next; 62835cc0c8SDon Mullis } 63835cc0c8SDon Mullis tail = tail->next; 64835cc0c8SDon Mullis } 65835cc0c8SDon Mullis tail->next = a ? : b; 66835cc0c8SDon Mullis 67835cc0c8SDon Mullis do { 68835cc0c8SDon Mullis /* 69835cc0c8SDon Mullis * In worst cases this loop may run many iterations. 70835cc0c8SDon Mullis * Continue callbacks to the client even though no 71835cc0c8SDon Mullis * element comparison is needed, so the client's cmp() 72835cc0c8SDon Mullis * routine can invoke cond_resched() periodically. 73835cc0c8SDon Mullis */ 7461b3d6c4SRasmus Villemoes if (unlikely(!(++count))) 75f015ac3eSDon Mullis (*cmp)(priv, tail->next, tail->next); 76835cc0c8SDon Mullis 77835cc0c8SDon Mullis tail->next->prev = tail; 78835cc0c8SDon Mullis tail = tail->next; 79835cc0c8SDon Mullis } while (tail->next); 80835cc0c8SDon Mullis 81835cc0c8SDon Mullis tail->next = head; 82835cc0c8SDon Mullis head->prev = tail; 83835cc0c8SDon Mullis } 84835cc0c8SDon Mullis 852c761270SDave Chinner /** 8602b12b7aSDon Mullis * list_sort - sort a list 8702b12b7aSDon Mullis * @priv: private data, opaque to list_sort(), passed to @cmp 882c761270SDave Chinner * @head: the list to sort 892c761270SDave Chinner * @cmp: the elements comparison function 902c761270SDave Chinner * 9102b12b7aSDon Mullis * This function implements "merge sort", which has O(nlog(n)) 9202b12b7aSDon Mullis * complexity. 932c761270SDave Chinner * 9402b12b7aSDon Mullis * The comparison function @cmp must return a negative value if @a 9502b12b7aSDon Mullis * should sort before @b, and a positive value if @a should sort after 9602b12b7aSDon Mullis * @b. If @a and @b are equivalent, and their original relative 9702b12b7aSDon Mullis * ordering is to be preserved, @cmp must return 0. 982c761270SDave Chinner */ 992c761270SDave Chinner void list_sort(void *priv, struct list_head *head, 1002c761270SDave Chinner int (*cmp)(void *priv, struct list_head *a, 1012c761270SDave Chinner struct list_head *b)) 1022c761270SDave Chinner { 103835cc0c8SDon Mullis struct list_head *part[MAX_LIST_LENGTH_BITS+1]; /* sorted partial lists 104835cc0c8SDon Mullis -- last slot is a sentinel */ 105835cc0c8SDon Mullis int lev; /* index into part[] */ 106835cc0c8SDon Mullis int max_lev = 0; 107835cc0c8SDon Mullis struct list_head *list; 1082c761270SDave Chinner 1092c761270SDave Chinner if (list_empty(head)) 1102c761270SDave Chinner return; 1112c761270SDave Chinner 112835cc0c8SDon Mullis memset(part, 0, sizeof(part)); 113835cc0c8SDon Mullis 114835cc0c8SDon Mullis head->prev->next = NULL; 1152c761270SDave Chinner list = head->next; 1162c761270SDave Chinner 117835cc0c8SDon Mullis while (list) { 118835cc0c8SDon Mullis struct list_head *cur = list; 119835cc0c8SDon Mullis list = list->next; 120835cc0c8SDon Mullis cur->next = NULL; 121835cc0c8SDon Mullis 122835cc0c8SDon Mullis for (lev = 0; part[lev]; lev++) { 123835cc0c8SDon Mullis cur = merge(priv, cmp, part[lev], cur); 124835cc0c8SDon Mullis part[lev] = NULL; 125835cc0c8SDon Mullis } 126835cc0c8SDon Mullis if (lev > max_lev) { 127835cc0c8SDon Mullis if (unlikely(lev >= ARRAY_SIZE(part)-1)) { 128835cc0c8SDon Mullis printk_once(KERN_DEBUG "list passed to" 129835cc0c8SDon Mullis " list_sort() too long for" 130835cc0c8SDon Mullis " efficiency\n"); 131835cc0c8SDon Mullis lev--; 132835cc0c8SDon Mullis } 133835cc0c8SDon Mullis max_lev = lev; 134835cc0c8SDon Mullis } 135835cc0c8SDon Mullis part[lev] = cur; 1362c761270SDave Chinner } 1372c761270SDave Chinner 138835cc0c8SDon Mullis for (lev = 0; lev < max_lev; lev++) 139835cc0c8SDon Mullis if (part[lev]) 140835cc0c8SDon Mullis list = merge(priv, cmp, part[lev], list); 1412c761270SDave Chinner 142835cc0c8SDon Mullis merge_and_restore_back_links(priv, cmp, head, part[max_lev], list); 1432c761270SDave Chinner } 1442c761270SDave Chinner EXPORT_SYMBOL(list_sort); 145835cc0c8SDon Mullis 1466d411e6cSArtem Bityutskiy #ifdef CONFIG_TEST_LIST_SORT 147eeee9ebbSArtem Bityutskiy 148eeee9ebbSArtem Bityutskiy #include <linux/random.h> 149eeee9ebbSArtem Bityutskiy 150835cc0c8SDon Mullis /* 151835cc0c8SDon Mullis * The pattern of set bits in the list length determines which cases 152835cc0c8SDon Mullis * are hit in list_sort(). 153835cc0c8SDon Mullis */ 154eeee9ebbSArtem Bityutskiy #define TEST_LIST_LEN (512+128+2) /* not including head */ 155835cc0c8SDon Mullis 156041b78f2SArtem Bityutskiy #define TEST_POISON1 0xDEADBEEF 157041b78f2SArtem Bityutskiy #define TEST_POISON2 0xA324354C 158041b78f2SArtem Bityutskiy 159041b78f2SArtem Bityutskiy struct debug_el { 160041b78f2SArtem Bityutskiy unsigned int poison1; 161041b78f2SArtem Bityutskiy struct list_head list; 162041b78f2SArtem Bityutskiy unsigned int poison2; 163041b78f2SArtem Bityutskiy int value; 164041b78f2SArtem Bityutskiy unsigned serial; 165041b78f2SArtem Bityutskiy }; 166041b78f2SArtem Bityutskiy 167041b78f2SArtem Bityutskiy /* Array, containing pointers to all elements in the test list */ 168041b78f2SArtem Bityutskiy static struct debug_el **elts __initdata; 169041b78f2SArtem Bityutskiy 170041b78f2SArtem Bityutskiy static int __init check(struct debug_el *ela, struct debug_el *elb) 171041b78f2SArtem Bityutskiy { 172041b78f2SArtem Bityutskiy if (ela->serial >= TEST_LIST_LEN) { 173041b78f2SArtem Bityutskiy printk(KERN_ERR "list_sort_test: error: incorrect serial %d\n", 174041b78f2SArtem Bityutskiy ela->serial); 175041b78f2SArtem Bityutskiy return -EINVAL; 176041b78f2SArtem Bityutskiy } 177041b78f2SArtem Bityutskiy if (elb->serial >= TEST_LIST_LEN) { 178041b78f2SArtem Bityutskiy printk(KERN_ERR "list_sort_test: error: incorrect serial %d\n", 179041b78f2SArtem Bityutskiy elb->serial); 180041b78f2SArtem Bityutskiy return -EINVAL; 181041b78f2SArtem Bityutskiy } 182041b78f2SArtem Bityutskiy if (elts[ela->serial] != ela || elts[elb->serial] != elb) { 183041b78f2SArtem Bityutskiy printk(KERN_ERR "list_sort_test: error: phantom element\n"); 184041b78f2SArtem Bityutskiy return -EINVAL; 185041b78f2SArtem Bityutskiy } 186041b78f2SArtem Bityutskiy if (ela->poison1 != TEST_POISON1 || ela->poison2 != TEST_POISON2) { 187041b78f2SArtem Bityutskiy printk(KERN_ERR "list_sort_test: error: bad poison: %#x/%#x\n", 188041b78f2SArtem Bityutskiy ela->poison1, ela->poison2); 189041b78f2SArtem Bityutskiy return -EINVAL; 190041b78f2SArtem Bityutskiy } 191041b78f2SArtem Bityutskiy if (elb->poison1 != TEST_POISON1 || elb->poison2 != TEST_POISON2) { 192041b78f2SArtem Bityutskiy printk(KERN_ERR "list_sort_test: error: bad poison: %#x/%#x\n", 193041b78f2SArtem Bityutskiy elb->poison1, elb->poison2); 194041b78f2SArtem Bityutskiy return -EINVAL; 195041b78f2SArtem Bityutskiy } 196041b78f2SArtem Bityutskiy return 0; 197041b78f2SArtem Bityutskiy } 198041b78f2SArtem Bityutskiy 199041b78f2SArtem Bityutskiy static int __init cmp(void *priv, struct list_head *a, struct list_head *b) 200041b78f2SArtem Bityutskiy { 201041b78f2SArtem Bityutskiy struct debug_el *ela, *elb; 202041b78f2SArtem Bityutskiy 203041b78f2SArtem Bityutskiy ela = container_of(a, struct debug_el, list); 204041b78f2SArtem Bityutskiy elb = container_of(b, struct debug_el, list); 205041b78f2SArtem Bityutskiy 206041b78f2SArtem Bityutskiy check(ela, elb); 207041b78f2SArtem Bityutskiy return ela->value - elb->value; 208041b78f2SArtem Bityutskiy } 209041b78f2SArtem Bityutskiy 210835cc0c8SDon Mullis static int __init list_sort_test(void) 211835cc0c8SDon Mullis { 21227d555d1SRasmus Villemoes int i, count = 1, err = -ENOMEM; 213f3dc0e38SArtem Bityutskiy struct debug_el *el; 21469412303SRasmus Villemoes struct list_head *cur; 215f3dc0e38SArtem Bityutskiy LIST_HEAD(head); 216835cc0c8SDon Mullis 217014afa94SArtem Bityutskiy printk(KERN_DEBUG "list_sort_test: start testing list_sort()\n"); 218835cc0c8SDon Mullis 21969412303SRasmus Villemoes elts = kcalloc(TEST_LIST_LEN, sizeof(*elts), GFP_KERNEL); 220041b78f2SArtem Bityutskiy if (!elts) { 221041b78f2SArtem Bityutskiy printk(KERN_ERR "list_sort_test: error: cannot allocate " 222041b78f2SArtem Bityutskiy "memory\n"); 22369412303SRasmus Villemoes return err; 224041b78f2SArtem Bityutskiy } 225041b78f2SArtem Bityutskiy 226eeee9ebbSArtem Bityutskiy for (i = 0; i < TEST_LIST_LEN; i++) { 227f3dc0e38SArtem Bityutskiy el = kmalloc(sizeof(*el), GFP_KERNEL); 228f3dc0e38SArtem Bityutskiy if (!el) { 229014afa94SArtem Bityutskiy printk(KERN_ERR "list_sort_test: error: cannot " 230f3dc0e38SArtem Bityutskiy "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) { 250014afa94SArtem Bityutskiy printk(KERN_ERR "list_sort_test: error: list is " 251014afa94SArtem Bityutskiy "corrupted\n"); 252f3dc0e38SArtem Bityutskiy goto exit; 253f3dc0e38SArtem Bityutskiy } 254f3dc0e38SArtem Bityutskiy 255f3dc0e38SArtem Bityutskiy cmp_result = cmp(NULL, cur, cur->next); 256f3dc0e38SArtem Bityutskiy if (cmp_result > 0) { 257014afa94SArtem Bityutskiy printk(KERN_ERR "list_sort_test: error: list is not " 258014afa94SArtem Bityutskiy "sorted\n"); 259f3dc0e38SArtem Bityutskiy goto exit; 260f3dc0e38SArtem Bityutskiy } 261f3dc0e38SArtem Bityutskiy 262f3dc0e38SArtem Bityutskiy el = container_of(cur, struct debug_el, list); 263f3dc0e38SArtem Bityutskiy el1 = container_of(cur->next, struct debug_el, list); 264f3dc0e38SArtem Bityutskiy if (cmp_result == 0 && el->serial >= el1->serial) { 265014afa94SArtem Bityutskiy printk(KERN_ERR "list_sort_test: error: order of " 266014afa94SArtem Bityutskiy "equivalent elements not preserved\n"); 267f3dc0e38SArtem Bityutskiy goto exit; 268835cc0c8SDon Mullis } 269041b78f2SArtem Bityutskiy 270041b78f2SArtem Bityutskiy if (check(el, el1)) { 271041b78f2SArtem Bityutskiy printk(KERN_ERR "list_sort_test: error: element check " 272041b78f2SArtem Bityutskiy "failed\n"); 273041b78f2SArtem Bityutskiy goto exit; 274041b78f2SArtem Bityutskiy } 275835cc0c8SDon Mullis count++; 276835cc0c8SDon Mullis } 2779d418dccSRasmus Villemoes if (head.prev != cur) { 2789d418dccSRasmus Villemoes printk(KERN_ERR "list_sort_test: error: list is corrupted\n"); 2799d418dccSRasmus Villemoes goto exit; 2809d418dccSRasmus Villemoes } 2819d418dccSRasmus Villemoes 282f3dc0e38SArtem Bityutskiy 283eeee9ebbSArtem Bityutskiy if (count != TEST_LIST_LEN) { 284014afa94SArtem Bityutskiy printk(KERN_ERR "list_sort_test: error: bad list length %d", 285014afa94SArtem Bityutskiy count); 286f3dc0e38SArtem Bityutskiy goto exit; 287835cc0c8SDon Mullis } 288f3dc0e38SArtem Bityutskiy 289f3dc0e38SArtem Bityutskiy err = 0; 290f3dc0e38SArtem Bityutskiy exit: 29169412303SRasmus Villemoes for (i = 0; i < TEST_LIST_LEN; i++) 29269412303SRasmus Villemoes kfree(elts[i]); 293041b78f2SArtem Bityutskiy kfree(elts); 294f3dc0e38SArtem Bityutskiy return err; 295835cc0c8SDon Mullis } 296835cc0c8SDon Mullis module_init(list_sort_test); 2976d411e6cSArtem Bityutskiy #endif /* CONFIG_TEST_LIST_SORT */ 298