8 files changed, 203 insertions, 23 deletions

diff --git a/lib/Kconfig b/lib/Kconfig
index 3de93357f5..f6299342b8 100644
--- a/lib/Kconfig
+++ b/lib/Kconfig
@@ -86,4 +86,10 @@ config TEXTSEARCH_BM
 config TEXTSEARCH_FSM
         tristate
 
+#
+# plist support is select#ed if needed
+#
+config PLIST
+        boolean
+
 endmenu
diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug
index ccb0c1fdf1..5330911ebd 100644
--- a/lib/Kconfig.debug
+++ b/lib/Kconfig.debug
@@ -107,6 +107,24 @@ config DEBUG_MUTEXES
          This allows mutex semantics violations and mutex related deadlocks
          (lockups) to be detected and reported automatically.
 
+config DEBUG_RT_MUTEXES
+        bool "RT Mutex debugging, deadlock detection"
+        depends on DEBUG_KERNEL && RT_MUTEXES
+        help
+         This allows rt mutex semantics violations and rt mutex related
+         deadlocks (lockups) to be detected and reported automatically.
+
+config DEBUG_PI_LIST
+        bool
+        default y
+        depends on DEBUG_RT_MUTEXES
+
+config RT_MUTEX_TESTER
+        bool "Built-in scriptable tester for rt-mutexes"
+        depends on DEBUG_KERNEL && RT_MUTEXES
+        help
+          This option enables a rt-mutex tester.
+
 config DEBUG_SPINLOCK
         bool "Spinlock debugging"
         depends on DEBUG_KERNEL
@@ -188,14 +206,22 @@ config FRAME_POINTER
 
 config UNWIND_INFO
         bool "Compile the kernel with frame unwind information"
-        depends on !IA64
-        depends on !MODULES || !(MIPS || PARISC || PPC || SUPERH || V850)
+        depends on !IA64 && !PARISC
+        depends on !MODULES || !(MIPS || PPC || SUPERH || V850)
         help
           If you say Y here the resulting kernel image will be slightly larger
           but not slower, and it will give very useful debugging information.
           If you don't debug the kernel, you can say N, but we may not be able
           to solve problems without frame unwind information or frame pointers.
 
+config STACK_UNWIND
+        bool "Stack unwind support"
+        depends on UNWIND_INFO
+        depends on X86
+        help
+          This enables more precise stack traces, omitting all unrelated
+          occurrences of pointers into kernel code from the dump.
+
 config FORCED_INLINING
         bool "Force gcc to inline functions marked 'inline'"
         depends on DEBUG_KERNEL
diff --git a/lib/Makefile b/lib/Makefile
index 79358ad1f1..10c13c9d78 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -25,6 +25,7 @@ lib-$(CONFIG_SEMAPHORE_SLEEPERS) += semaphore-sleepers.o
 lib-$(CONFIG_GENERIC_FIND_NEXT_BIT) += find_next_bit.o
 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
 
 ifneq ($(CONFIG_HAVE_DEC_LOCK),y)
diff --git a/lib/idr.c b/lib/idr.c
index de19030a99..4d09681951 100644
--- a/lib/idr.c
+++ b/lib/idr.c
@@ -29,6 +29,7 @@
 #include <linux/init.h>
 #include <linux/module.h>
 #endif
+#include <linux/err.h>
 #include <linux/string.h>
 #include <linux/idr.h>
 
@@ -398,6 +399,48 @@ void *idr_find(struct idr *idp, int id)
 }
 EXPORT_SYMBOL(idr_find);
 
+/**
+ * idr_replace - replace pointer for given id
+ * @idp: idr handle
+ * @ptr: pointer you want associated with the id
+ * @id: lookup key
+ *
+ * Replace the pointer registered with an id and return the old value.
+ * A -ENOENT return indicates that @id was not found.
+ * A -EINVAL return indicates that @id was not within valid constraints.
+ *
+ * The caller must serialize vs idr_find(), idr_get_new(), and idr_remove().
+ */
+void *idr_replace(struct idr *idp, void *ptr, int id)
+{
+        int n;
+        struct idr_layer *p, *old_p;
+
+        n = idp->layers * IDR_BITS;
+        p = idp->top;
+
+        id &= MAX_ID_MASK;
+
+        if (id >= (1 << n))
+                return ERR_PTR(-EINVAL);
+
+        n -= IDR_BITS;
+        while ((n > 0) && p) {
+                p = p->ary[(id >> n) & IDR_MASK];
+                n -= IDR_BITS;
+        }
+
+        n = id & IDR_MASK;
+        if (unlikely(p == NULL || !test_bit(n, &p->bitmap)))
+                return ERR_PTR(-ENOENT);
+
+        old_p = p->ary[n];
+        p->ary[n] = ptr;
+
+        return old_p;
+}
+EXPORT_SYMBOL(idr_replace);
+
 static void idr_cache_ctor(void * idr_layer, kmem_cache_t *idr_layer_cache,
                 unsigned long flags)
 {
diff --git a/lib/kernel_lock.c b/lib/kernel_lock.c
index cb5490ec00..e713e86811 100644
--- a/lib/kernel_lock.c
+++ b/lib/kernel_lock.c
@@ -14,7 +14,7 @@
  * The 'big kernel semaphore'
  *
  * This mutex is taken and released recursively by lock_kernel()
- * and unlock_kernel().  It is transparently dropped and reaquired
+ * and unlock_kernel().  It is transparently dropped and reacquired
  * over schedule().  It is used to protect legacy code that hasn't
  * been migrated to a proper locking design yet.
  *
@@ -92,7 +92,7 @@ void __lockfunc unlock_kernel(void)
  * The 'big kernel lock'
  *
  * This spinlock is taken and released recursively by lock_kernel()
- * and unlock_kernel().  It is transparently dropped and reaquired
+ * and unlock_kernel().  It is transparently dropped and reacquired
  * over schedule().  It is used to protect legacy code that hasn't
  * been migrated to a proper locking design yet.
  *
diff --git a/lib/plist.c b/lib/plist.c
new file mode 100644
index 0000000000..3074a02272
--- /dev/null
+++ b/lib/plist.c
@@ -0,0 +1,118 @@
+/*
+ * lib/plist.c
+ *
+ * Descending-priority-sorted double-linked list
+ *
+ * (C) 2002-2003 Intel Corp
+ * Inaky Perez-Gonzalez <inaky.perez-gonzalez@intel.com>.
+ *
+ * 2001-2005 (c) MontaVista Software, Inc.
+ * Daniel Walker <dwalker@mvista.com>
+ *
+ * (C) 2005 Thomas Gleixner <tglx@linutronix.de>
+ *
+ * Simplifications of the original code by
+ * Oleg Nesterov <oleg@tv-sign.ru>
+ *
+ * Licensed under the FSF's GNU Public License v2 or later.
+ *
+ * Based on simple lists (include/linux/list.h).
+ *
+ * This file contains the add / del functions which are considered to
+ * be too large to inline. See include/linux/plist.h for further
+ * information.
+ */
+
+#include <linux/plist.h>
+#include <linux/spinlock.h>
+
+#ifdef CONFIG_DEBUG_PI_LIST
+
+static void plist_check_prev_next(struct list_head *t, struct list_head *p,
+                                  struct list_head *n)
+{
+        if (n->prev != p || p->next != n) {
+                printk("top: %p, n: %p, p: %p\n", t, t->next, t->prev);
+                printk("prev: %p, n: %p, p: %p\n", p, p->next, p->prev);
+                printk("next: %p, n: %p, p: %p\n", n, n->next, n->prev);
+                WARN_ON(1);
+        }
+}
+
+static void plist_check_list(struct list_head *top)
+{
+        struct list_head *prev = top, *next = top->next;
+
+        plist_check_prev_next(top, prev, next);
+        while (next != top) {
+                prev = next;
+                next = prev->next;
+                plist_check_prev_next(top, prev, next);
+        }
+}
+
+static void plist_check_head(struct plist_head *head)
+{
+        WARN_ON(!head->lock);
+        if (head->lock)
+                WARN_ON_SMP(!spin_is_locked(head->lock));
+        plist_check_list(&head->prio_list);
+        plist_check_list(&head->node_list);
+}
+
+#else
+# define plist_check_head(h)    do { } while (0)
+#endif
+
+/**
+ * plist_add - add @node to @head
+ *
+ * @node:       &struct plist_node pointer
+ * @head:       &struct plist_head pointer
+ */
+void plist_add(struct plist_node *node, struct plist_head *head)
+{
+        struct plist_node *iter;
+
+        plist_check_head(head);
+        WARN_ON(!plist_node_empty(node));
+
+        list_for_each_entry(iter, &head->prio_list, plist.prio_list) {
+                if (node->prio < iter->prio)
+                        goto lt_prio;
+                else if (node->prio == iter->prio) {
+                        iter = list_entry(iter->plist.prio_list.next,
+                                        struct plist_node, plist.prio_list);
+                        goto eq_prio;
+                }
+        }
+
+lt_prio:
+        list_add_tail(&node->plist.prio_list, &iter->plist.prio_list);
+eq_prio:
+        list_add_tail(&node->plist.node_list, &iter->plist.node_list);
+
+        plist_check_head(head);
+}
+
+/**
+ * plist_del - Remove a @node from plist.
+ *
+ * @node:       &struct plist_node pointer - entry to be removed
+ * @head:       &struct plist_head pointer - list head
+ */
+void plist_del(struct plist_node *node, struct plist_head *head)
+{
+        plist_check_head(head);
+
+        if (!list_empty(&node->plist.prio_list)) {
+                struct plist_node *next = plist_first(&node->plist);
+
+                list_move_tail(&next->plist.prio_list, &node->plist.prio_list);
+                list_del_init(&node->plist.prio_list);
+        }
+
+        list_del_init(&node->plist.node_list);
+
+        plist_check_head(head);
+}
diff --git a/lib/zlib_inflate/inffast.c b/lib/zlib_inflate/inffast.c
index 02a16eacb7..d84560c076 100644
--- a/lib/zlib_inflate/inffast.c
+++ b/lib/zlib_inflate/inffast.c
@@ -63,10 +63,10 @@
       bytes, which is the maximum length that can be coded.  inflate_fast()
       requires strm->avail_out >= 258 for each loop to avoid checking for
       output space.
+
+    - @start:   inflate()'s starting value for strm->avail_out
  */
-void inflate_fast(strm, start)
-z_streamp strm;
-unsigned start;         /* inflate()'s starting value for strm->avail_out */
+void inflate_fast(z_streamp strm, unsigned start)
 {
     struct inflate_state *state;
     unsigned char *in;      /* local strm->next_in */
diff --git a/lib/zlib_inflate/inftrees.c b/lib/zlib_inflate/inftrees.c
index 62343c53bf..3fe6ce5b53 100644
--- a/lib/zlib_inflate/inftrees.c
+++ b/lib/zlib_inflate/inftrees.c
@@ -8,15 +8,6 @@
 
 #define MAXBITS 15
 
-const char inflate_copyright[] =
-   " inflate 1.2.3 Copyright 1995-2005 Mark Adler ";
-/*
-  If you use the zlib library in a product, an acknowledgment is welcome
-  in the documentation of your product. If for some reason you cannot
-  include such an acknowledgment, I would appreciate that you keep this
-  copyright string in the executable of your product.
- */
-
 /*
    Build a set of tables to decode the provided canonical Huffman code.
    The code lengths are lens[0..codes-1].  The result starts at *table,
@@ -29,13 +20,8 @@ const char inflate_copyright[] =
    table index bits.  It will differ if the request is greater than the
    longest code or if it is less than the shortest code.
  */
-int zlib_inflate_table(type, lens, codes, table, bits, work)
-codetype type;
-unsigned short *lens;
-unsigned codes;
-code **table;
-unsigned *bits;
-unsigned short *work;
+int zlib_inflate_table(codetype type, unsigned short *lens, unsigned codes,
+                        code **table, unsigned *bits, unsigned short *work)
 {
     unsigned len;               /* a code's length in bits */
     unsigned sym;               /* index of code symbols */