9 files changed, 308 insertions, 24 deletions

diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug
index 935248bdbc47..d85be90d5888 100644
--- a/lib/Kconfig.debug
+++ b/lib/Kconfig.debug
@@ -512,6 +512,18 @@ config PROVE_RCU
 
          Say N if you are unsure.
 
+config PROVE_RCU_REPEATEDLY
+        bool "RCU debugging: don't disable PROVE_RCU on first splat"
+        depends on PROVE_RCU
+        default n
+        help
+         By itself, PROVE_RCU will disable checking upon issuing the
+         first warning (or "splat").  This feature prevents such
+         disabling, allowing multiple RCU-lockdep warnings to be printed
+         on a single reboot.
+
+         Say N if you are unsure.
+
 config LOCKDEP
         bool
         depends on DEBUG_KERNEL && TRACE_IRQFLAGS_SUPPORT && STACKTRACE_SUPPORT && LOCKDEP_SUPPORT
@@ -793,7 +805,7 @@ config RCU_CPU_STALL_DETECTOR
 config RCU_CPU_STALL_VERBOSE
         bool "Print additional per-task information for RCU_CPU_STALL_DETECTOR"
         depends on RCU_CPU_STALL_DETECTOR && TREE_PREEMPT_RCU
-        default n
+        default y
         help
           This option causes RCU to printk detailed per-task information
           for any tasks that are stalling the current RCU grace period.
@@ -1086,6 +1098,13 @@ config DMA_API_DEBUG
           This option causes a performance degredation.  Use only if you want
           to debug device drivers. If unsure, say N.
 
+config ATOMIC64_SELFTEST
+        bool "Perform an atomic64_t self-test at boot"
+        help
+          Enable this option to test the atomic64_t functions at boot.
+
+          If unsure, say N.
+
 source "samples/Kconfig"
 
 source "lib/Kconfig.kgdb"
diff --git a/lib/Makefile b/lib/Makefile
index 0d4015205c64..9e6d3c29d73a 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -39,7 +39,10 @@ lib-$(CONFIG_RWSEM_XCHGADD_ALGORITHM) += rwsem.o
 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
+
+CFLAGS_hweight.o = $(subst $(quote),,$(CONFIG_ARCH_HWEIGHT_CFLAGS))
 obj-$(CONFIG_GENERIC_HWEIGHT) += hweight.o
+
 obj-$(CONFIG_LOCK_KERNEL) += kernel_lock.o
 obj-$(CONFIG_BTREE) += btree.o
 obj-$(CONFIG_DEBUG_PREEMPT) += smp_processor_id.o
@@ -101,6 +104,8 @@ obj-$(CONFIG_GENERIC_CSUM) += checksum.o
 
 obj-$(CONFIG_GENERIC_ATOMIC64) += atomic64.o
 
+obj-$(CONFIG_ATOMIC64_SELFTEST) += atomic64_test.o
+
 hostprogs-y     := gen_crc32table
 clean-files     := crc32table.h
 
diff --git a/lib/atomic64.c b/lib/atomic64.c
index 8bee16ec7524..a21c12bc727c 100644
--- a/lib/atomic64.c
+++ b/lib/atomic64.c
@@ -162,12 +162,12 @@ int atomic64_add_unless(atomic64_t *v, long long a, long long u)
 {
         unsigned long flags;
         spinlock_t *lock = lock_addr(v);
-        int ret = 1;
+        int ret = 0;
 
         spin_lock_irqsave(lock, flags);
         if (v->counter != u) {
                 v->counter += a;
-                ret = 0;
+                ret = 1;
         }
         spin_unlock_irqrestore(lock, flags);
         return ret;
diff --git a/lib/atomic64_test.c b/lib/atomic64_test.c
new file mode 100644
index 000000000000..65e482caf5e9
--- /dev/null
+++ b/lib/atomic64_test.c
@@ -0,0 +1,164 @@
+/*
+ * Testsuite for atomic64_t functions
+ *
+ * Copyright © 2010  Luca Barbieri
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ */
+#include <linux/init.h>
+#include <asm/atomic.h>
+
+#define INIT(c) do { atomic64_set(&v, c); r = c; } while (0)
+static __init int test_atomic64(void)
+{
+        long long v0 = 0xaaa31337c001d00dLL;
+        long long v1 = 0xdeadbeefdeafcafeLL;
+        long long v2 = 0xfaceabadf00df001LL;
+        long long onestwos = 0x1111111122222222LL;
+        long long one = 1LL;
+
+        atomic64_t v = ATOMIC64_INIT(v0);
+        long long r = v0;
+        BUG_ON(v.counter != r);
+
+        atomic64_set(&v, v1);
+        r = v1;
+        BUG_ON(v.counter != r);
+        BUG_ON(atomic64_read(&v) != r);
+
+        INIT(v0);
+        atomic64_add(onestwos, &v);
+        r += onestwos;
+        BUG_ON(v.counter != r);
+
+        INIT(v0);
+        atomic64_add(-one, &v);
+        r += -one;
+        BUG_ON(v.counter != r);
+
+        INIT(v0);
+        r += onestwos;
+        BUG_ON(atomic64_add_return(onestwos, &v) != r);
+        BUG_ON(v.counter != r);
+
+        INIT(v0);
+        r += -one;
+        BUG_ON(atomic64_add_return(-one, &v) != r);
+        BUG_ON(v.counter != r);
+
+        INIT(v0);
+        atomic64_sub(onestwos, &v);
+        r -= onestwos;
+        BUG_ON(v.counter != r);
+
+        INIT(v0);
+        atomic64_sub(-one, &v);
+        r -= -one;
+        BUG_ON(v.counter != r);
+
+        INIT(v0);
+        r -= onestwos;
+        BUG_ON(atomic64_sub_return(onestwos, &v) != r);
+        BUG_ON(v.counter != r);
+
+        INIT(v0);
+        r -= -one;
+        BUG_ON(atomic64_sub_return(-one, &v) != r);
+        BUG_ON(v.counter != r);
+
+        INIT(v0);
+        atomic64_inc(&v);
+        r += one;
+        BUG_ON(v.counter != r);
+
+        INIT(v0);
+        r += one;
+        BUG_ON(atomic64_inc_return(&v) != r);
+        BUG_ON(v.counter != r);
+
+        INIT(v0);
+        atomic64_dec(&v);
+        r -= one;
+        BUG_ON(v.counter != r);
+
+        INIT(v0);
+        r -= one;
+        BUG_ON(atomic64_dec_return(&v) != r);
+        BUG_ON(v.counter != r);
+
+        INIT(v0);
+        BUG_ON(atomic64_xchg(&v, v1) != v0);
+        r = v1;
+        BUG_ON(v.counter != r);
+
+        INIT(v0);
+        BUG_ON(atomic64_cmpxchg(&v, v0, v1) != v0);
+        r = v1;
+        BUG_ON(v.counter != r);
+
+        INIT(v0);
+        BUG_ON(atomic64_cmpxchg(&v, v2, v1) != v0);
+        BUG_ON(v.counter != r);
+
+        INIT(v0);
+        BUG_ON(atomic64_add_unless(&v, one, v0));
+        BUG_ON(v.counter != r);
+
+        INIT(v0);
+        BUG_ON(!atomic64_add_unless(&v, one, v1));
+        r += one;
+        BUG_ON(v.counter != r);
+
+#if defined(CONFIG_X86) || defined(CONFIG_MIPS) || defined(CONFIG_PPC) || defined(_ASM_GENERIC_ATOMIC64_H)
+        INIT(onestwos);
+        BUG_ON(atomic64_dec_if_positive(&v) != (onestwos - 1));
+        r -= one;
+        BUG_ON(v.counter != r);
+
+        INIT(0);
+        BUG_ON(atomic64_dec_if_positive(&v) != -one);
+        BUG_ON(v.counter != r);
+
+        INIT(-one);
+        BUG_ON(atomic64_dec_if_positive(&v) != (-one - one));
+        BUG_ON(v.counter != r);
+#else
+#warning Please implement atomic64_dec_if_positive for your architecture, and add it to the IF above
+#endif
+
+        INIT(onestwos);
+        BUG_ON(!atomic64_inc_not_zero(&v));
+        r += one;
+        BUG_ON(v.counter != r);
+
+        INIT(0);
+        BUG_ON(atomic64_inc_not_zero(&v));
+        BUG_ON(v.counter != r);
+
+        INIT(-one);
+        BUG_ON(!atomic64_inc_not_zero(&v));
+        r += one;
+        BUG_ON(v.counter != r);
+
+#ifdef CONFIG_X86
+        printk(KERN_INFO "atomic64 test passed for %s platform %s CX8 and %s SSE\n",
+#ifdef CONFIG_X86_64
+               "x86-64",
+#elif defined(CONFIG_X86_CMPXCHG64)
+               "i586+",
+#else
+               "i386+",
+#endif
+               boot_cpu_has(X86_FEATURE_CX8) ? "with" : "without",
+               boot_cpu_has(X86_FEATURE_XMM) ? "with" : "without");
+#else
+        printk(KERN_INFO "atomic64 test passed\n");
+#endif
+
+        return 0;
+}
+
+core_initcall(test_atomic64);
diff --git a/lib/btree.c b/lib/btree.c
index 41859a820218..c9c6f0351526 100644
--- a/lib/btree.c
+++ b/lib/btree.c
@@ -95,7 +95,8 @@ static unsigned long *btree_node_alloc(struct btree_head *head, gfp_t gfp)
         unsigned long *node;
 
         node = mempool_alloc(head->mempool, gfp);
-        memset(node, 0, NODESIZE);
+        if (likely(node))
+                memset(node, 0, NODESIZE);
         return node;
 }
 
diff --git a/lib/debugobjects.c b/lib/debugobjects.c
index b862b30369ff..deebcc57d4e6 100644
--- a/lib/debugobjects.c
+++ b/lib/debugobjects.c
@@ -141,6 +141,7 @@ alloc_object(void *addr, struct debug_bucket *b, struct debug_obj_descr *descr)
                 obj->object = addr;
                 obj->descr  = descr;
                 obj->state  = ODEBUG_STATE_NONE;
+                obj->astate = 0;
                 hlist_del(&obj->node);
 
                 hlist_add_head(&obj->node, &b->list);
@@ -252,8 +253,10 @@ static void debug_print_object(struct debug_obj *obj, char *msg)
 
         if (limit < 5 && obj->descr != descr_test) {
                 limit++;
-                WARN(1, KERN_ERR "ODEBUG: %s %s object type: %s\n", msg,
-                       obj_states[obj->state], obj->descr->name);
+                WARN(1, KERN_ERR "ODEBUG: %s %s (active state %u) "
+                                 "object type: %s\n",
+                        msg, obj_states[obj->state], obj->astate,
+                        obj->descr->name);
         }
         debug_objects_warnings++;
 }
@@ -447,7 +450,10 @@ void debug_object_deactivate(void *addr, struct debug_obj_descr *descr)
                 case ODEBUG_STATE_INIT:
                 case ODEBUG_STATE_INACTIVE:
                 case ODEBUG_STATE_ACTIVE:
-                        obj->state = ODEBUG_STATE_INACTIVE;
+                        if (!obj->astate)
+                                obj->state = ODEBUG_STATE_INACTIVE;
+                        else
+                                debug_print_object(obj, "deactivate");
                         break;
 
                 case ODEBUG_STATE_DESTROYED:
@@ -553,6 +559,53 @@ out_unlock:
         raw_spin_unlock_irqrestore(&db->lock, flags);
 }
 
+/**
+ * debug_object_active_state - debug checks object usage state machine
+ * @addr:       address of the object
+ * @descr:      pointer to an object specific debug description structure
+ * @expect:     expected state
+ * @next:       state to move to if expected state is found
+ */
+void
+debug_object_active_state(void *addr, struct debug_obj_descr *descr,
+                          unsigned int expect, unsigned int next)
+{
+        struct debug_bucket *db;
+        struct debug_obj *obj;
+        unsigned long flags;
+
+        if (!debug_objects_enabled)
+                return;
+
+        db = get_bucket((unsigned long) addr);
+
+        raw_spin_lock_irqsave(&db->lock, flags);
+
+        obj = lookup_object(addr, db);
+        if (obj) {
+                switch (obj->state) {
+                case ODEBUG_STATE_ACTIVE:
+                        if (obj->astate == expect)
+                                obj->astate = next;
+                        else
+                                debug_print_object(obj, "active_state");
+                        break;
+
+                default:
+                        debug_print_object(obj, "active_state");
+                        break;
+                }
+        } else {
+                struct debug_obj o = { .object = addr,
+                                       .state = ODEBUG_STATE_NOTAVAILABLE,
+                                       .descr = descr };
+
+                debug_print_object(&o, "active_state");
+        }
+
+        raw_spin_unlock_irqrestore(&db->lock, flags);
+}
+
 #ifdef CONFIG_DEBUG_OBJECTS_FREE
 static void __debug_check_no_obj_freed(const void *address, unsigned long size)
 {
@@ -774,7 +827,7 @@ static int __init fixup_free(void *addr, enum debug_obj_state state)
         }
 }
 
-static int
+static int __init
 check_results(void *addr, enum debug_obj_state state, int fixups, int warnings)
 {
         struct debug_bucket *db;
@@ -917,7 +970,7 @@ void __init debug_objects_early_init(void)
 /*
  * Convert the statically allocated objects to dynamic ones:
  */
-static int debug_objects_replace_static_objects(void)
+static int __init debug_objects_replace_static_objects(void)
 {
         struct debug_bucket *db = obj_hash;
         struct hlist_node *node, *tmp;
diff --git a/lib/hweight.c b/lib/hweight.c
index 63ee4eb1228d..3c79d50814cf 100644
--- a/lib/hweight.c
+++ b/lib/hweight.c
@@ -9,7 +9,7 @@
  * The Hamming Weight of a number is the total number of bits set in it.
  */
 
-unsigned int hweight32(unsigned int w)
+unsigned int __sw_hweight32(unsigned int w)
 {
 #ifdef ARCH_HAS_FAST_MULTIPLIER
         w -= (w >> 1) & 0x55555555;
@@ -24,29 +24,30 @@ unsigned int hweight32(unsigned int w)
         return (res + (res >> 16)) & 0x000000FF;
 #endif
 }
-EXPORT_SYMBOL(hweight32);
+EXPORT_SYMBOL(__sw_hweight32);
 
-unsigned int hweight16(unsigned int w)
+unsigned int __sw_hweight16(unsigned int w)
 {
         unsigned int res = w - ((w >> 1) & 0x5555);
         res = (res & 0x3333) + ((res >> 2) & 0x3333);
         res = (res + (res >> 4)) & 0x0F0F;
         return (res + (res >> 8)) & 0x00FF;
 }
-EXPORT_SYMBOL(hweight16);
+EXPORT_SYMBOL(__sw_hweight16);
 
-unsigned int hweight8(unsigned int w)
+unsigned int __sw_hweight8(unsigned int w)
 {
         unsigned int res = w - ((w >> 1) & 0x55);
         res = (res & 0x33) + ((res >> 2) & 0x33);
         return (res + (res >> 4)) & 0x0F;
 }
-EXPORT_SYMBOL(hweight8);
+EXPORT_SYMBOL(__sw_hweight8);
 
-unsigned long hweight64(__u64 w)
+unsigned long __sw_hweight64(__u64 w)
 {
 #if BITS_PER_LONG == 32
-        return hweight32((unsigned int)(w >> 32)) + hweight32((unsigned int)w);
+        return __sw_hweight32((unsigned int)(w >> 32)) +
+               __sw_hweight32((unsigned int)w);
 #elif BITS_PER_LONG == 64
 #ifdef ARCH_HAS_FAST_MULTIPLIER
         w -= (w >> 1) & 0x5555555555555555ul;
@@ -63,4 +64,4 @@ unsigned long hweight64(__u64 w)
 #endif
 #endif
 }
-EXPORT_SYMBOL(hweight64);
+EXPORT_SYMBOL(__sw_hweight64);
diff --git a/lib/rbtree.c b/lib/rbtree.c
index e2aa3be29858..15e10b1afdd2 100644
--- a/lib/rbtree.c
+++ b/lib/rbtree.c
@@ -44,6 +44,11 @@ static void __rb_rotate_left(struct rb_node *node, struct rb_root *root)
         else
                 root->rb_node = right;
         rb_set_parent(node, right);
+
+        if (root->augment_cb) {
+                root->augment_cb(node);
+                root->augment_cb(right);
+        }
 }
 
 static void __rb_rotate_right(struct rb_node *node, struct rb_root *root)
@@ -67,12 +72,20 @@ static void __rb_rotate_right(struct rb_node *node, struct rb_root *root)
         else
                 root->rb_node = left;
         rb_set_parent(node, left);
+
+        if (root->augment_cb) {
+                root->augment_cb(node);
+                root->augment_cb(left);
+        }
 }
 
 void rb_insert_color(struct rb_node *node, struct rb_root *root)
 {
         struct rb_node *parent, *gparent;
 
+        if (root->augment_cb)
+                root->augment_cb(node);
+
         while ((parent = rb_parent(node)) && rb_is_red(parent))
         {
                 gparent = rb_parent(parent);
@@ -227,12 +240,15 @@ void rb_erase(struct rb_node *node, struct rb_root *root)
         else
         {
                 struct rb_node *old = node, *left;
+                int old_parent_cb = 0;
+                int successor_parent_cb = 0;
 
                 node = node->rb_right;
                 while ((left = node->rb_left) != NULL)
                         node = left;
 
                 if (rb_parent(old)) {
+                        old_parent_cb = 1;
                         if (rb_parent(old)->rb_left == old)
                                 rb_parent(old)->rb_left = node;
                         else
@@ -247,8 +263,10 @@ void rb_erase(struct rb_node *node, struct rb_root *root)
                 if (parent == old) {
                         parent = node;
                 } else {
+                        successor_parent_cb = 1;
                         if (child)
                                 rb_set_parent(child, parent);
+
                         parent->rb_left = child;
 
                         node->rb_right = old->rb_right;
@@ -259,6 +277,24 @@ void rb_erase(struct rb_node *node, struct rb_root *root)
                 node->rb_left = old->rb_left;
                 rb_set_parent(old->rb_left, node);
 
+                if (root->augment_cb) {
+                        /*
+                         * Here, three different nodes can have new children.
+                         * The parent of the successor node that was selected
+                         * to replace the node to be erased.
+                         * The node that is getting erased and is now replaced
+                         * by its successor.
+                         * The parent of the node getting erased-replaced.
+                         */
+                        if (successor_parent_cb)
+                                root->augment_cb(parent);
+
+                        root->augment_cb(node);
+
+                        if (old_parent_cb)
+                                root->augment_cb(rb_parent(old));
+                }
+
                 goto color;
         }
 
@@ -267,15 +303,19 @@ void rb_erase(struct rb_node *node, struct rb_root *root)
 
         if (child)
                 rb_set_parent(child, parent);
-        if (parent)
-        {
+
+        if (parent) {
                 if (parent->rb_left == node)
                         parent->rb_left = child;
                 else
                         parent->rb_right = child;
-        }
-        else
+
+                if (root->augment_cb)
+                        root->augment_cb(parent);
+
+        } else {
                 root->rb_node = child;
+        }
 
  color:
         if (color == RB_BLACK)
diff --git a/lib/rwsem.c b/lib/rwsem.c
index 3e3365e5665e..ceba8e28807a 100644
--- a/lib/rwsem.c
+++ b/lib/rwsem.c
@@ -136,9 +136,10 @@ __rwsem_do_wake(struct rw_semaphore *sem, int downgrading)
  out:
         return sem;
 
-        /* undo the change to count, but check for a transition 1->0 */
+        /* undo the change to the active count, but check for a transition
+         * 1->0 */
  undo:
-        if (rwsem_atomic_update(-RWSEM_ACTIVE_BIAS, sem) != 0)
+        if (rwsem_atomic_update(-RWSEM_ACTIVE_BIAS, sem) & RWSEM_ACTIVE_MASK)
                 goto out;
         goto try_again;
 }