12 files changed, 284 insertions, 40 deletions

diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug
index b0f5ca72599f..756a908c441d 100644
--- a/lib/Kconfig.debug
+++ b/lib/Kconfig.debug
@@ -320,6 +320,15 @@ config DEBUG_VM
 
           If unsure, say N.
 
+config DEBUG_LIST
+        bool "Debug linked list manipulation"
+        depends on DEBUG_KERNEL
+        help
+          Enable this to turn on extended checks in the linked-list
+          walking routines.
+
+          If unsure, say N.
+
 config FRAME_POINTER
         bool "Compile the kernel with frame pointers"
         depends on DEBUG_KERNEL && (X86 || CRIS || M68K || M68KNOMMU || FRV || UML || S390 || AVR32 || SUPERH)
@@ -375,3 +384,17 @@ config RCU_TORTURE_TEST
           at boot time (you probably don't).
           Say M if you want the RCU torture tests to build as a module.
           Say N if you are unsure.
+
+config LKDTM
+        tristate "Linux Kernel Dump Test Tool Module"
+        depends on KPROBES
+        default n
+        help
+        This module enables testing of the different dumping mechanisms by
+        inducing system failures at predefined crash points.
+        If you don't need it: say N
+        Choose M here to compile this code as a module. The module will be
+        called lkdtm.
+
+        Documentation on how to use the module can be found in
+        drivers/misc/lkdtm.c
diff --git a/lib/Makefile b/lib/Makefile
index ef1d37afbbb6..b0361756e22e 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -2,11 +2,12 @@
 # Makefile for some libs needed in the kernel.
 #
 
-lib-y := errno.o ctype.o string.o vsprintf.o cmdline.o \
+lib-y := ctype.o string.o vsprintf.o cmdline.o \
          bust_spinlocks.o rbtree.o radix-tree.o dump_stack.o \
          idr.o div64.o int_sqrt.o bitmap.o extable.o prio_tree.o \
          sha1.o
 
+lib-$(CONFIG_MMU) += ioremap.o
 lib-$(CONFIG_SMP) += cpumask.o
 
 lib-y   += kobject.o kref.o kobject_uevent.o klist.o
@@ -28,6 +29,7 @@ lib-$(CONFIG_GENERIC_HWEIGHT) += hweight.o
 obj-$(CONFIG_LOCK_KERNEL) += kernel_lock.o
 obj-$(CONFIG_PLIST) += plist.o
 obj-$(CONFIG_DEBUG_PREEMPT) += smp_processor_id.o
+obj-$(CONFIG_DEBUG_LIST) += list_debug.o
 
 ifneq ($(CONFIG_HAVE_DEC_LOCK),y)
   lib-y += dec_and_lock.o
diff --git a/lib/cpumask.c b/lib/cpumask.c
index 3a67dc5ada7d..7a2a73f88d59 100644
--- a/lib/cpumask.c
+++ b/lib/cpumask.c
@@ -43,3 +43,19 @@ int __any_online_cpu(const cpumask_t *mask)
         return cpu;
 }
 EXPORT_SYMBOL(__any_online_cpu);
+
+#if MAX_NUMNODES > 1
+/*
+ * Find the highest possible node id.
+ */
+int highest_possible_node_id(void)
+{
+        unsigned int node;
+        unsigned int highest = 0;
+
+        for_each_node_mask(node, node_possible_map)
+                highest = node;
+        return highest;
+}
+EXPORT_SYMBOL(highest_possible_node_id);
+#endif
diff --git a/lib/errno.c b/lib/errno.c
deleted file mode 100644
index 41cb9d76c052..000000000000
--- a/lib/errno.c
+++ /dev/null
@@ -1,7 +0,0 @@
-/*
- *  linux/lib/errno.c
- *
- *  Copyright (C) 1991, 1992  Linus Torvalds
- */
-
-int errno;
diff --git a/lib/genalloc.c b/lib/genalloc.c
index 71338b48e889..75ae68ce03e1 100644
--- a/lib/genalloc.c
+++ b/lib/genalloc.c
@@ -14,11 +14,13 @@
 #include <linux/genalloc.h>
 
 
-/*
- * Create a new special memory pool.
- *
+/**
+ * gen_pool_create - create a new special memory pool
  * @min_alloc_order: log base 2 of number of bytes each bitmap bit represents
  * @nid: node id of the node the pool structure should be allocated on, or -1
+ *
+ * Create a new special memory pool that can be used to manage special purpose
+ * memory not managed by the regular kmalloc/kfree interface.
  */
 struct gen_pool *gen_pool_create(int min_alloc_order, int nid)
 {
@@ -34,15 +36,15 @@ struct gen_pool *gen_pool_create(int min_alloc_order, int nid)
 }
 EXPORT_SYMBOL(gen_pool_create);
 
-
-/*
- * Add a new chunk of memory to the specified pool.
- *
+/**
+ * gen_pool_add - add a new chunk of special memory to the pool
  * @pool: pool to add new memory chunk to
  * @addr: starting address of memory chunk to add to pool
  * @size: size in bytes of the memory chunk to add to pool
  * @nid: node id of the node the chunk structure and bitmap should be
  *       allocated on, or -1
+ *
+ * Add a new chunk of special memory to the specified pool.
  */
 int gen_pool_add(struct gen_pool *pool, unsigned long addr, size_t size,
                  int nid)
@@ -69,13 +71,44 @@ int gen_pool_add(struct gen_pool *pool, unsigned long addr, size_t size,
 }
 EXPORT_SYMBOL(gen_pool_add);
 
-
-/*
- * Allocate the requested number of bytes from the specified pool.
- * Uses a first-fit algorithm.
+/**
+ * gen_pool_destroy - destroy a special memory pool
+ * @pool: pool to destroy
  *
+ * Destroy the specified special memory pool. Verifies that there are no
+ * outstanding allocations.
+ */
+void gen_pool_destroy(struct gen_pool *pool)
+{
+        struct list_head *_chunk, *_next_chunk;
+        struct gen_pool_chunk *chunk;
+        int order = pool->min_alloc_order;
+        int bit, end_bit;
+
+
+        write_lock(&pool->lock);
+        list_for_each_safe(_chunk, _next_chunk, &pool->chunks) {
+                chunk = list_entry(_chunk, struct gen_pool_chunk, next_chunk);
+                list_del(&chunk->next_chunk);
+
+                end_bit = (chunk->end_addr - chunk->start_addr) >> order;
+                bit = find_next_bit(chunk->bits, end_bit, 0);
+                BUG_ON(bit < end_bit);
+
+                kfree(chunk);
+        }
+        kfree(pool);
+        return;
+}
+EXPORT_SYMBOL(gen_pool_destroy);
+
+/**
+ * gen_pool_alloc - allocate special memory from the pool
  * @pool: pool to allocate from
  * @size: number of bytes to allocate from the pool
+ *
+ * Allocate the requested number of bytes from the specified pool.
+ * Uses a first-fit algorithm.
  */
 unsigned long gen_pool_alloc(struct gen_pool *pool, size_t size)
 {
@@ -127,13 +160,13 @@ unsigned long gen_pool_alloc(struct gen_pool *pool, size_t size)
 }
 EXPORT_SYMBOL(gen_pool_alloc);
 
-
-/*
- * Free the specified memory back to the specified pool.
- *
+/**
+ * gen_pool_free - free allocated special memory back to the pool
  * @pool: pool to free to
  * @addr: starting address of memory to free back to pool
  * @size: size in bytes of memory to free
+ *
+ * Free previously allocated special memory back to the specified pool.
  */
 void gen_pool_free(struct gen_pool *pool, unsigned long addr, size_t size)
 {
diff --git a/lib/ioremap.c b/lib/ioremap.c
new file mode 100644
index 000000000000..99fa277f9f7b
--- /dev/null
+++ b/lib/ioremap.c
@@ -0,0 +1,92 @@
+/*
+ * Re-map IO memory to kernel address space so that we can access it.
+ * This is needed for high PCI addresses that aren't mapped in the
+ * 640k-1MB IO memory area on PC's
+ *
+ * (C) Copyright 1995 1996 Linus Torvalds
+ */
+#include <linux/io.h>
+#include <linux/vmalloc.h>
+#include <linux/mm.h>
+
+#include <asm/cacheflush.h>
+#include <asm/pgtable.h>
+
+static int ioremap_pte_range(pmd_t *pmd, unsigned long addr,
+                unsigned long end, unsigned long phys_addr, pgprot_t prot)
+{
+        pte_t *pte;
+        unsigned long pfn;
+
+        pfn = phys_addr >> PAGE_SHIFT;
+        pte = pte_alloc_kernel(pmd, addr);
+        if (!pte)
+                return -ENOMEM;
+        do {
+                BUG_ON(!pte_none(*pte));
+                set_pte_at(&init_mm, addr, pte, pfn_pte(pfn, prot));
+                pfn++;
+        } while (pte++, addr += PAGE_SIZE, addr != end);
+        return 0;
+}
+
+static inline int ioremap_pmd_range(pud_t *pud, unsigned long addr,
+                unsigned long end, unsigned long phys_addr, pgprot_t prot)
+{
+        pmd_t *pmd;
+        unsigned long next;
+
+        phys_addr -= addr;
+        pmd = pmd_alloc(&init_mm, pud, addr);
+        if (!pmd)
+                return -ENOMEM;
+        do {
+                next = pmd_addr_end(addr, end);
+                if (ioremap_pte_range(pmd, addr, next, phys_addr + addr, prot))
+                        return -ENOMEM;
+        } while (pmd++, addr = next, addr != end);
+        return 0;
+}
+
+static inline int ioremap_pud_range(pgd_t *pgd, unsigned long addr,
+                unsigned long end, unsigned long phys_addr, pgprot_t prot)
+{
+        pud_t *pud;
+        unsigned long next;
+
+        phys_addr -= addr;
+        pud = pud_alloc(&init_mm, pgd, addr);
+        if (!pud)
+                return -ENOMEM;
+        do {
+                next = pud_addr_end(addr, end);
+                if (ioremap_pmd_range(pud, addr, next, phys_addr + addr, prot))
+                        return -ENOMEM;
+        } while (pud++, addr = next, addr != end);
+        return 0;
+}
+
+int ioremap_page_range(unsigned long addr,
+                       unsigned long end, unsigned long phys_addr, pgprot_t prot)
+{
+        pgd_t *pgd;
+        unsigned long start;
+        unsigned long next;
+        int err;
+
+        BUG_ON(addr >= end);
+
+        start = addr;
+        phys_addr -= addr;
+        pgd = pgd_offset_k(addr);
+        do {
+                next = pgd_addr_end(addr, end);
+                err = ioremap_pud_range(pgd, addr, next, phys_addr+addr, prot);
+                if (err)
+                        break;
+        } while (pgd++, addr = next, addr != end);
+
+        flush_cache_vmap(start, end);
+
+        return err;
+}
diff --git a/lib/list_debug.c b/lib/list_debug.c
new file mode 100644
index 000000000000..7ba9d823d388
--- /dev/null
+++ b/lib/list_debug.c
@@ -0,0 +1,76 @@
+/*
+ * Copyright 2006, Red Hat, Inc., Dave Jones
+ * Released under the General Public License (GPL).
+ *
+ * This file contains the linked list implementations for
+ * DEBUG_LIST.
+ */
+
+#include <linux/module.h>
+#include <linux/list.h>
+
+/*
+ * Insert a new entry between two known consecutive entries.
+ *
+ * This is only for internal list manipulation where we know
+ * the prev/next entries already!
+ */
+
+void __list_add(struct list_head *new,
+                              struct list_head *prev,
+                              struct list_head *next)
+{
+        if (unlikely(next->prev != prev)) {
+                printk(KERN_ERR "list_add corruption. next->prev should be %p, but was %p\n",
+                        prev, next->prev);
+                BUG();
+        }
+        if (unlikely(prev->next != next)) {
+                printk(KERN_ERR "list_add corruption. prev->next should be %p, but was %p\n",
+                        next, prev->next);
+                BUG();
+        }
+        next->prev = new;
+        new->next = next;
+        new->prev = prev;
+        prev->next = new;
+}
+EXPORT_SYMBOL(__list_add);
+
+/**
+ * list_add - add a new entry
+ * @new: new entry to be added
+ * @head: list head to add it after
+ *
+ * Insert a new entry after the specified head.
+ * This is good for implementing stacks.
+ */
+void list_add(struct list_head *new, struct list_head *head)
+{
+        __list_add(new, head, head->next);
+}
+EXPORT_SYMBOL(list_add);
+
+/**
+ * list_del - deletes entry from list.
+ * @entry: the element to delete from the list.
+ * Note: list_empty on entry does not return true after this, the entry is
+ * in an undefined state.
+ */
+void list_del(struct list_head *entry)
+{
+        if (unlikely(entry->prev->next != entry)) {
+                printk(KERN_ERR "list_del corruption. prev->next should be %p, "
+                                "but was %p\n", entry, entry->prev->next);
+                BUG();
+        }
+        if (unlikely(entry->next->prev != entry)) {
+                printk(KERN_ERR "list_del corruption. next->prev should be %p, "
+                                "but was %p\n", entry, entry->next->prev);
+                BUG();
+        }
+        __list_del(entry->prev, entry->next);
+        entry->next = LIST_POISON1;
+        entry->prev = LIST_POISON2;
+}
+EXPORT_SYMBOL(list_del);
diff --git a/lib/rbtree.c b/lib/rbtree.c
index 1e55ba1c2edf..48499c2d88cc 100644
--- a/lib/rbtree.c
+++ b/lib/rbtree.c
@@ -322,6 +322,9 @@ struct rb_node *rb_next(struct rb_node *node)
 {
         struct rb_node *parent;
 
+        if (rb_parent(node) == node)
+                return NULL;
+
         /* If we have a right-hand child, go down and then left as far
            as we can. */
         if (node->rb_right) {
@@ -348,6 +351,9 @@ struct rb_node *rb_prev(struct rb_node *node)
 {
         struct rb_node *parent;
 
+        if (rb_parent(node) == node)
+                return NULL;
+
         /* If we have a left-hand child, go down and then right as far
            as we can. */
         if (node->rb_left) {
diff --git a/lib/rwsem.c b/lib/rwsem.c
index b322421c2969..901d0e7da892 100644
--- a/lib/rwsem.c
+++ b/lib/rwsem.c
@@ -146,7 +146,7 @@ __rwsem_do_wake(struct rw_semaphore *sem, int downgrading)
 /*
  * wait for a lock to be granted
  */
-static inline struct rw_semaphore *
+static struct rw_semaphore *
 rwsem_down_failed_common(struct rw_semaphore *sem,
                         struct rwsem_waiter *waiter, signed long adjustment)
 {
diff --git a/lib/sort.c b/lib/sort.c
index 5f3b51ffa1dc..488788b341cb 100644
--- a/lib/sort.c
+++ b/lib/sort.c
@@ -49,15 +49,15 @@ void sort(void *base, size_t num, size_t size,
           void (*swap)(void *, void *, int size))
 {
         /* pre-scale counters for performance */
-        int i = (num/2) * size, n = num * size, c, r;
+        int i = (num/2 - 1) * size, n = num * size, c, r;
 
         if (!swap)
                 swap = (size == 4 ? u32_swap : generic_swap);
 
         /* heapify */
         for ( ; i >= 0; i -= size) {
-                for (r = i; r * 2 < n; r  = c) {
-                        c = r * 2;
+                for (r = i; r * 2 + size < n; r  = c) {
+                        c = r * 2 + size;
                         if (c < n - size && cmp(base + c, base + c + size) < 0)
                                 c += size;
                         if (cmp(base + r, base + c) >= 0)
@@ -69,8 +69,8 @@ void sort(void *base, size_t num, size_t size,
         /* sort */
         for (i = n - size; i >= 0; i -= size) {
                 swap(base, base + i, size);
-                for (r = 0; r * 2 < i; r = c) {
-                        c = r * 2;
+                for (r = 0; r * 2 + size < i; r = c) {
+                        c = r * 2 + size;
                         if (c < i - size && cmp(base + c, base + c + size) < 0)
                                 c += size;
                         if (cmp(base + r, base + c) >= 0)
diff --git a/lib/spinlock_debug.c b/lib/spinlock_debug.c
index 58c577dd82e5..dafaf1de2491 100644
--- a/lib/spinlock_debug.c
+++ b/lib/spinlock_debug.c
@@ -99,11 +99,12 @@ static inline void debug_spin_unlock(spinlock_t *lock)
 
 static void __spin_lock_debug(spinlock_t *lock)
 {
-        int print_once = 1;
         u64 i;
+        u64 loops = loops_per_jiffy * HZ;
+        int print_once = 1;
 
         for (;;) {
-                for (i = 0; i < loops_per_jiffy * HZ; i++) {
+                for (i = 0; i < loops; i++) {
                         if (__raw_spin_trylock(&lock->raw_lock))
                                 return;
                         __delay(1);
@@ -165,11 +166,12 @@ static void rwlock_bug(rwlock_t *lock, const char *msg)
 #if 0           /* __write_lock_debug() can lock up - maybe this can too? */
 static void __read_lock_debug(rwlock_t *lock)
 {
-        int print_once = 1;
         u64 i;
+        u64 loops = loops_per_jiffy * HZ;
+        int print_once = 1;
 
         for (;;) {
-                for (i = 0; i < loops_per_jiffy * HZ; i++) {
+                for (i = 0; i < loops; i++) {
                         if (__raw_read_trylock(&lock->raw_lock))
                                 return;
                         __delay(1);
@@ -239,11 +241,12 @@ static inline void debug_write_unlock(rwlock_t *lock)
 #if 0           /* This can cause lockups */
 static void __write_lock_debug(rwlock_t *lock)
 {
-        int print_once = 1;
         u64 i;
+        u64 loops = loops_per_jiffy * HZ;
+        int print_once = 1;
 
         for (;;) {
-                for (i = 0; i < loops_per_jiffy * HZ; i++) {
+                for (i = 0; i < loops; i++) {
                         if (__raw_write_trylock(&lock->raw_lock))
                                 return;
                         __delay(1);
diff --git a/lib/ts_fsm.c b/lib/ts_fsm.c
index 87847c2ae9e2..af575b61526b 100644
--- a/lib/ts_fsm.c
+++ b/lib/ts_fsm.c
@@ -12,13 +12,13 @@
  *
  *   A finite state machine consists of n states (struct ts_fsm_token)
  *   representing the pattern as a finite automation. The data is read
- *   sequentially on a octet basis. Every state token specifies the number
+ *   sequentially on an octet basis. Every state token specifies the number
  *   of recurrences and the type of value accepted which can be either a
  *   specific character or ctype based set of characters. The available
  *   type of recurrences include 1, (0|1), [0 n], and [1 n].
  *
- *   The algorithm differs between strict/non-strict mode specyfing
- *   whether the pattern has to start at the first octect. Strict mode
+ *   The algorithm differs between strict/non-strict mode specifying
+ *   whether the pattern has to start at the first octet. Strict mode
  *   is enabled by default and can be disabled by inserting
  *   TS_FSM_HEAD_IGNORE as the first token in the chain.
  *
@@ -44,7 +44,7 @@ struct ts_fsm
 #define _W              0x200 /* wildcard */
 
 /* Map to _ctype flags and some magic numbers */
-static u16 token_map[TS_FSM_TYPE_MAX+1] = {
+static const u16 token_map[TS_FSM_TYPE_MAX+1] = {
         [TS_FSM_SPECIFIC] = 0,
         [TS_FSM_WILDCARD] = _W,
         [TS_FSM_CNTRL]    = _C,
@@ -61,7 +61,7 @@ static u16 token_map[TS_FSM_TYPE_MAX+1] = {
         [TS_FSM_ASCII]    = _A,
 };
 
-static u16 token_lookup_tbl[256] = {
+static const u16 token_lookup_tbl[256] = {
 _W|_A|_C,      _W|_A|_C,     _W|_A|_C,     _W|_A|_C,            /*   0-  3 */
 _W|_A|_C,      _W|_A|_C,     _W|_A|_C,     _W|_A|_C,            /*   4-  7 */
 _W|_A|_C,      _W|_A|_C|_S,  _W|_A|_C|_S,  _W|_A|_C|_S,         /*   8- 11 */