8 files changed, 242 insertions, 135 deletions

diff --git a/lib/Kconfig b/lib/Kconfig
index 97b136ff117e..8034c46327cb 100644
--- a/lib/Kconfig
+++ b/lib/Kconfig
@@ -160,6 +160,9 @@ config TEXTSEARCH_BM
 config TEXTSEARCH_FSM
         tristate
 
+config LIST_SORT
+        boolean
+
 config HAS_IOMEM
         boolean
         depends on !NO_IOMEM
diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug
index 5e3407d997b2..b520ec1f33c5 100644
--- a/lib/Kconfig.debug
+++ b/lib/Kconfig.debug
@@ -864,8 +864,7 @@ config DEBUG_FORCE_WEAK_PER_CPU
 
 config LKDTM
         tristate "Linux Kernel Dump Test Tool Module"
-        depends on DEBUG_KERNEL
-        depends on KPROBES
+        depends on DEBUG_FS
         depends on BLOCK
         default n
         help
@@ -876,7 +875,7 @@ config LKDTM
         called lkdtm.
 
         Documentation on how to use the module can be found in
-        drivers/misc/lkdtm.c
+        Documentation/fault-injection/provoke-crashes.txt
 
 config FAULT_INJECTION
         bool "Fault-injection framework"
diff --git a/lib/Makefile b/lib/Makefile
index 3b0b4a696db9..e39c361b0be3 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -21,7 +21,7 @@ lib-y	+= kobject.o kref.o klist.o
 
 obj-y += bcd.o div64.o sort.o parser.o halfmd4.o debug_locks.o random32.o \
          bust_spinlocks.o hexdump.o kasprintf.o bitmap.o scatterlist.o \
-         string_helpers.o gcd.o list_sort.o
+         string_helpers.o gcd.o
 
 ifeq ($(CONFIG_DEBUG_KOBJECT),y)
 CFLAGS_kobject.o += -DDEBUG
@@ -40,6 +40,7 @@ lib-$(CONFIG_GENERIC_FIND_FIRST_BIT) += find_next_bit.o
 lib-$(CONFIG_GENERIC_FIND_NEXT_BIT) += find_next_bit.o
 obj-$(CONFIG_GENERIC_FIND_LAST_BIT) += find_last_bit.o
 obj-$(CONFIG_GENERIC_HWEIGHT) += hweight.o
+obj-$(CONFIG_LIST_SORT) += list_sort.o
 obj-$(CONFIG_LOCK_KERNEL) += kernel_lock.o
 obj-$(CONFIG_DEBUG_PREEMPT) += smp_processor_id.o
 obj-$(CONFIG_DEBUG_LIST) += list_debug.o
diff --git a/lib/bitmap.c b/lib/bitmap.c
index 11bf49750583..ffb78c916ccd 100644
--- a/lib/bitmap.c
+++ b/lib/bitmap.c
@@ -487,7 +487,7 @@ int __bitmap_parse(const char *buf, unsigned int buflen,
 EXPORT_SYMBOL(__bitmap_parse);
 
 /**
- * bitmap_parse_user()
+ * bitmap_parse_user - convert an ASCII hex string in a user buffer into a bitmap
  *
  * @ubuf: pointer to user buffer containing string.
  * @ulen: buffer size in bytes.  If string is smaller than this
@@ -619,7 +619,7 @@ int bitmap_parselist(const char *bp, unsigned long *maskp, int nmaskbits)
 EXPORT_SYMBOL(bitmap_parselist);
 
 /**
- * bitmap_pos_to_ord(buf, pos, bits)
+ * bitmap_pos_to_ord - find ordinal of set bit at given position in bitmap
  *      @buf: pointer to a bitmap
  *      @pos: a bit position in @buf (0 <= @pos < @bits)
  *      @bits: number of valid bit positions in @buf
@@ -655,7 +655,7 @@ static int bitmap_pos_to_ord(const unsigned long *buf, int pos, int bits)
 }
 
 /**
- * bitmap_ord_to_pos(buf, ord, bits)
+ * bitmap_ord_to_pos - find position of n-th set bit in bitmap
  *      @buf: pointer to bitmap
  *      @ord: ordinal bit position (n-th set bit, n >= 0)
  *      @bits: number of valid bit positions in @buf
@@ -733,10 +733,9 @@ void bitmap_remap(unsigned long *dst, const unsigned long *src,
         bitmap_zero(dst, bits);
 
         w = bitmap_weight(new, bits);
-        for (oldbit = find_first_bit(src, bits);
-             oldbit < bits;
-             oldbit = find_next_bit(src, bits, oldbit + 1)) {
+        for_each_set_bit(oldbit, src, bits) {
                 int n = bitmap_pos_to_ord(old, oldbit, bits);
+
                 if (n < 0 || w == 0)
                         set_bit(oldbit, dst);   /* identity map */
                 else
@@ -903,9 +902,7 @@ void bitmap_onto(unsigned long *dst, const unsigned long *orig,
          */
 
         m = 0;
-        for (n = find_first_bit(relmap, bits);
-             n < bits;
-             n = find_next_bit(relmap, bits, n + 1)) {
+        for_each_set_bit(n, relmap, bits) {
                 /* m == bitmap_pos_to_ord(relmap, n, bits) */
                 if (test_bit(m, orig))
                         set_bit(n, dst);
@@ -934,9 +931,7 @@ void bitmap_fold(unsigned long *dst, const unsigned long *orig,
                 return;
         bitmap_zero(dst, bits);
 
-        for (oldbit = find_first_bit(orig, bits);
-             oldbit < bits;
-             oldbit = find_next_bit(orig, bits, oldbit + 1))
+        for_each_set_bit(oldbit, orig, bits)
                 set_bit(oldbit % sz, dst);
 }
 EXPORT_SYMBOL(bitmap_fold);
diff --git a/lib/crc32.c b/lib/crc32.c
index 02e3b31b3a79..0f45fbff34cb 100644
--- a/lib/crc32.c
+++ b/lib/crc32.c
@@ -30,11 +30,15 @@
 #include <asm/atomic.h>
 #include "crc32defs.h"
 #if CRC_LE_BITS == 8
-#define tole(x) __constant_cpu_to_le32(x)
-#define tobe(x) __constant_cpu_to_be32(x)
+# define tole(x) __constant_cpu_to_le32(x)
 #else
-#define tole(x) (x)
-#define tobe(x) (x)
+# define tole(x) (x)
+#endif
+
+#if CRC_BE_BITS == 8
+# define tobe(x) __constant_cpu_to_be32(x)
+#else
+# define tobe(x) (x)
 #endif
 #include "crc32table.h"
 
@@ -52,20 +56,19 @@ crc32_body(u32 crc, unsigned char const *buf, size_t len, const u32 *tab)
 # else
 #  define DO_CRC(x) crc = tab[((crc >> 24) ^ (x)) & 255] ^ (crc << 8)
 # endif
-        const u32 *b = (const u32 *)buf;
+        const u32 *b;
         size_t    rem_len;
 
         /* Align it */
-        if (unlikely((long)b & 3 && len)) {
-                u8 *p = (u8 *)b;
+        if (unlikely((long)buf & 3 && len)) {
                 do {
-                        DO_CRC(*p++);
-                } while ((--len) && ((long)p)&3);
-                b = (u32 *)p;
+                        DO_CRC(*buf++);
+                } while ((--len) && ((long)buf)&3);
         }
         rem_len = len & 3;
         /* load data 32 bits wide, xor data 32 bits wide. */
         len = len >> 2;
+        b = (const u32 *)buf;
         for (--b; len; --len) {
                 crc ^= *++b; /* use pre increment for speed */
                 DO_CRC(0);
@@ -82,6 +85,7 @@ crc32_body(u32 crc, unsigned char const *buf, size_t len, const u32 *tab)
                 } while (--len);
         }
         return crc;
+#undef DO_CRC
 }
 #endif
 /**
@@ -119,9 +123,6 @@ u32 __pure crc32_le(u32 crc, unsigned char const *p, size_t len)
         crc = __cpu_to_le32(crc);
         crc = crc32_body(crc, p, len, tab);
         return __le32_to_cpu(crc);
-#undef ENDIAN_SHIFT
-#undef DO_CRC
-
 # elif CRC_LE_BITS == 4
         while (len--) {
                 crc ^= *p++;
@@ -179,9 +180,6 @@ u32 __pure crc32_be(u32 crc, unsigned char const *p, size_t len)
         crc = __cpu_to_be32(crc);
         crc = crc32_body(crc, p, len, tab);
         return __be32_to_cpu(crc);
-#undef ENDIAN_SHIFT
-#undef DO_CRC
-
 # elif CRC_BE_BITS == 4
         while (len--) {
                 crc ^= *p++ << 24;
diff --git a/lib/list_sort.c b/lib/list_sort.c
index 19d11e0bb958..4b5cb794c38b 100644
--- a/lib/list_sort.c
+++ b/lib/list_sort.c
@@ -4,99 +4,214 @@
 #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, tail);
+
+                tail->next->prev = tail;
+                tail = tail->next;
+        } while (tail->next);
+
+        tail->next = head;
+        head->prev = tail;
+}
+
 /**
- * list_sort - sort a list.
- * @priv: private data, passed to @cmp
+ * list_sort - sort a list
+ * @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
- * implements "merge sort" which has O(nlog(n)) complexity. The list is sorted
- * in ascending order.
+ * This function implements "merge sort", which has O(nlog(n))
+ * complexity.
  *
- * The comparison function @cmp is supposed to return a negative value if @a is
- * less than @b, and a positive value if @a is greater than @b. If @a and @b
- * are equivalent, then it does not matter what this function returns.
+ * The comparison function @cmp must return a negative value if @a
+ * should sort before @b, and a positive value if @a should sort after
+ * @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,
-                          struct list_head *b))
+                int (*cmp)(void *priv, struct list_head *a,
+                        struct list_head *b))
 {
-        struct list_head *p, *q, *e, *list, *tail, *oldhead;
-        int insize, nmerges, psize, qsize, i;
+        struct list_head *part[MAX_LIST_LENGTH_BITS+1]; /* sorted partial lists
+                                                -- 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 (psize > 0 || (qsize > 0 && q)) {
-                                if (!psize) {
-                                        e = q;
-                                        q = q->next;
-                                        qsize--;
-                                        if (q == oldhead)
-                                                q = NULL;
-                                } else if (!qsize || !q) {
-                                        e = p;
-                                        p = p->next;
-                                        psize--;
-                                        if (p == oldhead)
-                                                p = NULL;
-                                } else if (cmp(priv, p, q) <= 0) {
-                                        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;
+        while (list) {
+                struct list_head *cur = list;
+                list = list->next;
+                cur->next = NULL;
+
+                for (lev = 0; part[lev]; lev++) {
+                        cur = merge(priv, cmp, part[lev], cur);
+                        part[lev] = NULL;
+                }
+                if (lev > max_lev) {
+                        if (unlikely(lev >= ARRAY_SIZE(part)-1)) {
+                                printk_once(KERN_DEBUG "list passed to"
+                                        " list_sort() too long for"
+                                        " efficiency\n");
+                                lev--;
                         }
-                        p = q;
+                        max_lev = lev;
                 }
+                part[lev] = cur;
+        }
 
-                tail->next = list;
-                list->prev = tail;
+        for (lev = 0; lev < max_lev; lev++)
+                if (part[lev])
+                        list = merge(priv, cmp, part[lev], list);
 
-                if (nmerges <= 1)
-                        break;
+        merge_and_restore_back_links(priv, cmp, head, part[max_lev], list);
+}
+EXPORT_SYMBOL(list_sort);
 
-                insize *= 2;
-        }
+#ifdef DEBUG_LIST_SORT
+struct debug_el {
+        struct list_head l_h;
+        int value;
+        unsigned serial;
+};
 
-        head->next = list;
-        head->prev = list->prev;
-        list->prev->next = head;
-        list->prev = head;
+static int cmp(void *priv, struct list_head *a, struct list_head *b)
+{
+        return container_of(a, struct debug_el, l_h)->value
+             - container_of(b, struct debug_el, l_h)->value;
 }
 
-EXPORT_SYMBOL(list_sort);
+/*
+ * The pattern of set bits in the list length determines which cases
+ * are hit in list_sort().
+ */
+#define LIST_SORT_TEST_LENGTH (512+128+2) /* not including head */
+
+static int __init list_sort_test(void)
+{
+        int i, r = 1, count;
+        struct list_head *head = kmalloc(sizeof(*head), GFP_KERNEL);
+        struct list_head *cur;
+
+        printk(KERN_WARNING "testing list_sort()\n");
+
+        cur = head;
+        for (i = 0; i < LIST_SORT_TEST_LENGTH; i++) {
+                struct debug_el *el = kmalloc(sizeof(*el), GFP_KERNEL);
+                BUG_ON(!el);
+                 /* force some equivalencies */
+                el->value = (r = (r * 725861) % 6599) % (LIST_SORT_TEST_LENGTH/3);
+                el->serial = i;
+
+                el->l_h.prev = cur;
+                cur->next = &el->l_h;
+                cur = cur->next;
+        }
+        head->prev = cur;
+
+        list_sort(NULL, head, cmp);
+
+        count = 1;
+        for (cur = head->next; cur->next != head; cur = cur->next) {
+                struct debug_el *el = container_of(cur, struct debug_el, l_h);
+                int cmp_result = cmp(NULL, cur, cur->next);
+                if (cur->next->prev != cur) {
+                        printk(KERN_EMERG "list_sort() returned "
+                                                "a corrupted list!\n");
+                        return 1;
+                } else if (cmp_result > 0) {
+                        printk(KERN_EMERG "list_sort() failed to sort!\n");
+                        return 1;
+                } else if (cmp_result == 0 &&
+                                el->serial >= container_of(cur->next,
+                                        struct debug_el, l_h)->serial) {
+                        printk(KERN_EMERG "list_sort() failed to preserve order"
+                                                 " of equivalent elements!\n");
+                        return 1;
+                }
+                kfree(cur->prev);
+                count++;
+        }
+        kfree(cur);
+        if (count != LIST_SORT_TEST_LENGTH) {
+                printk(KERN_EMERG "list_sort() returned list of"
+                                                "different length!\n");
+                return 1;
+        }
+        return 0;
+}
+module_init(list_sort_test);
+#endif
diff --git a/lib/show_mem.c b/lib/show_mem.c
index 238e72a18ce1..fdc77c82f922 100644
--- a/lib/show_mem.c
+++ b/lib/show_mem.c
@@ -15,7 +15,7 @@ void show_mem(void)
         unsigned long total = 0, reserved = 0, shared = 0,
                 nonshared = 0, highmem = 0;
 
-        printk(KERN_INFO "Mem-Info:\n");
+        printk("Mem-Info:\n");
         show_free_areas();
 
         for_each_online_pgdat(pgdat) {
@@ -49,15 +49,15 @@ void show_mem(void)
                 pgdat_resize_unlock(pgdat, &flags);
         }
 
-        printk(KERN_INFO "%lu pages RAM\n", total);
+        printk("%lu pages RAM\n", total);
 #ifdef CONFIG_HIGHMEM
-        printk(KERN_INFO "%lu pages HighMem\n", highmem);
+        printk("%lu pages HighMem\n", highmem);
 #endif
-        printk(KERN_INFO "%lu pages reserved\n", reserved);
-        printk(KERN_INFO "%lu pages shared\n", shared);
-        printk(KERN_INFO "%lu pages non-shared\n", nonshared);
+        printk("%lu pages reserved\n", reserved);
+        printk("%lu pages shared\n", shared);
+        printk("%lu pages non-shared\n", nonshared);
 #ifdef CONFIG_QUICKLIST
-        printk(KERN_INFO "%lu pages in pagetable cache\n",
+        printk("%lu pages in pagetable cache\n",
                 quicklist_total_size());
 #endif
 }
diff --git a/lib/string.c b/lib/string.c
index a1cdcfcc42d0..f71bead1be3e 100644
--- a/lib/string.c
+++ b/lib/string.c
@@ -36,25 +36,21 @@ int strnicmp(const char *s1, const char *s2, size_t len)
         /* Yes, Virginia, it had better be unsigned */
         unsigned char c1, c2;
 
-        c1 = c2 = 0;
-        if (len) {
-                do {
-                        c1 = *s1;
-                        c2 = *s2;
-                        s1++;
-                        s2++;
-                        if (!c1)
-                                break;
-                        if (!c2)
-                                break;
-                        if (c1 == c2)
-                                continue;
-                        c1 = tolower(c1);
-                        c2 = tolower(c2);
-                        if (c1 != c2)
-                                break;
-                } while (--len);
-        }
+        if (!len)
+                return 0;
+
+        do {
+                c1 = *s1++;
+                c2 = *s2++;
+                if (!c1 || !c2)
+                        break;
+                if (c1 == c2)
+                        continue;
+                c1 = tolower(c1);
+                c2 = tolower(c2);
+                if (c1 != c2)
+                        break;
+        } while (--len);
         return (int)c1 - (int)c2;
 }
 EXPORT_SYMBOL(strnicmp);
@@ -693,13 +689,13 @@ EXPORT_SYMBOL(strstr);
  */
 char *strnstr(const char *s1, const char *s2, size_t len)
 {
-        size_t l1 = len, l2;
+        size_t l2;
 
         l2 = strlen(s2);
         if (!l2)
                 return (char *)s1;
-        while (l1 >= l2) {
-                l1--;
+        while (len >= l2) {
+                len--;
                 if (!memcmp(s1, s2, l2))
                         return (char *)s1;
                 s1++;