6 files changed, 205 insertions, 104 deletions

diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug
index eb9e9a7870fa..acedbe626d47 100644
--- a/lib/Kconfig.debug
+++ b/lib/Kconfig.debug
@@ -716,6 +716,19 @@ source "lib/Kconfig.kmemcheck"
 
 source "lib/Kconfig.kasan"
 
+config DEBUG_REFCOUNT
+        bool "Verbose refcount checks"
+        help
+          Say Y here if you want reference counters (refcount_t and kref) to
+          generate WARNs on dubious usage. Without this refcount_t will still
+          be a saturating counter and avoid Use-After-Free by turning it into
+          a resource leak Denial-Of-Service.
+
+          Use of this option will increase kernel text size but will alert the
+          admin of potential abuse.
+
+          If in doubt, say "N".
+
 endmenu # "Memory Debugging"
 
 config ARCH_HAS_KCOV
@@ -980,20 +993,6 @@ config DEBUG_TIMEKEEPING
 
           If unsure, say N.
 
-config TIMER_STATS
-        bool "Collect kernel timers statistics"
-        depends on DEBUG_KERNEL && PROC_FS
-        help
-          If you say Y here, additional code will be inserted into the
-          timer routines to collect statistics about kernel timers being
-          reprogrammed. The statistics can be read from /proc/timer_stats.
-          The statistics collection is started by writing 1 to /proc/timer_stats,
-          writing 0 stops it. This feature is useful to collect information
-          about timer usage patterns in kernel and userspace. This feature
-          is lightweight if enabled in the kernel config but not activated
-          (it defaults to deactivated on bootup and will only be activated
-          if some application like powertop activates it explicitly).
-
 config DEBUG_PREEMPT
         bool "Debug preemptible kernel"
         depends on DEBUG_KERNEL && PREEMPT && TRACE_IRQFLAGS_SUPPORT
@@ -1180,6 +1179,18 @@ config LOCK_TORTURE_TEST
           Say M if you want these torture tests to build as a module.
           Say N if you are unsure.
 
+config WW_MUTEX_SELFTEST
+        tristate "Wait/wound mutex selftests"
+        help
+          This option provides a kernel module that runs tests on the
+          on the struct ww_mutex locking API.
+
+          It is recommended to enable DEBUG_WW_MUTEX_SLOWPATH in conjunction
+          with this test harness.
+
+          Say M if you want these self tests to build as a module.
+          Say N if you are unsure.
+
 endmenu # lock debugging
 
 config TRACE_IRQFLAGS
@@ -1450,6 +1461,7 @@ config RCU_CPU_STALL_TIMEOUT
 config RCU_TRACE
         bool "Enable tracing for RCU"
         depends on DEBUG_KERNEL
+        default y if TREE_RCU
         select TRACE_CLOCK
         help
           This option provides tracing in RCU which presents stats
diff --git a/lib/Makefile b/lib/Makefile
index bc4073a8cd08..19ea76149a37 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -31,7 +31,7 @@ lib-$(CONFIG_HAS_DMA) += dma-noop.o
 lib-y   += kobject.o klist.o
 obj-y   += lockref.o
 
-obj-y += bcd.o div64.o sort.o parser.o halfmd4.o debug_locks.o random32.o \
+obj-y += bcd.o div64.o sort.o parser.o debug_locks.o random32.o \
          bust_spinlocks.o kasprintf.o bitmap.o scatterlist.o \
          gcd.o lcm.o list_sort.o uuid.o flex_array.o iov_iter.o clz_ctz.o \
          bsearch.o find_bit.o llist.o memweight.o kfifo.o \
diff --git a/lib/debugobjects.c b/lib/debugobjects.c
index 04c1ef717fe0..8c28cbd7e104 100644
--- a/lib/debugobjects.c
+++ b/lib/debugobjects.c
@@ -52,9 +52,18 @@ static int			debug_objects_fixups __read_mostly;
 static int                      debug_objects_warnings __read_mostly;
 static int                      debug_objects_enabled __read_mostly
                                 = CONFIG_DEBUG_OBJECTS_ENABLE_DEFAULT;
-
+static int                      debug_objects_pool_size __read_mostly
+                                = ODEBUG_POOL_SIZE;
+static int                      debug_objects_pool_min_level __read_mostly
+                                = ODEBUG_POOL_MIN_LEVEL;
 static struct debug_obj_descr   *descr_test  __read_mostly;
 
+/*
+ * Track numbers of kmem_cache_alloc()/free() calls done.
+ */
+static int                      debug_objects_allocated;
+static int                      debug_objects_freed;
+
 static void free_obj_work(struct work_struct *work);
 static DECLARE_WORK(debug_obj_work, free_obj_work);
 
@@ -88,13 +97,13 @@ static void fill_pool(void)
         struct debug_obj *new;
         unsigned long flags;
 
-        if (likely(obj_pool_free >= ODEBUG_POOL_MIN_LEVEL))
+        if (likely(obj_pool_free >= debug_objects_pool_min_level))
                 return;
 
         if (unlikely(!obj_cache))
                 return;
 
-        while (obj_pool_free < ODEBUG_POOL_MIN_LEVEL) {
+        while (obj_pool_free < debug_objects_pool_min_level) {
 
                 new = kmem_cache_zalloc(obj_cache, gfp);
                 if (!new)
@@ -102,6 +111,7 @@ static void fill_pool(void)
 
                 raw_spin_lock_irqsave(&pool_lock, flags);
                 hlist_add_head(&new->node, &obj_pool);
+                debug_objects_allocated++;
                 obj_pool_free++;
                 raw_spin_unlock_irqrestore(&pool_lock, flags);
         }
@@ -162,24 +172,39 @@ alloc_object(void *addr, struct debug_bucket *b, struct debug_obj_descr *descr)
 
 /*
  * workqueue function to free objects.
+ *
+ * To reduce contention on the global pool_lock, the actual freeing of
+ * debug objects will be delayed if the pool_lock is busy. We also free
+ * the objects in a batch of 4 for each lock/unlock cycle.
  */
+#define ODEBUG_FREE_BATCH       4
+
 static void free_obj_work(struct work_struct *work)
 {
-        struct debug_obj *obj;
+        struct debug_obj *objs[ODEBUG_FREE_BATCH];
         unsigned long flags;
+        int i;
 
-        raw_spin_lock_irqsave(&pool_lock, flags);
-        while (obj_pool_free > ODEBUG_POOL_SIZE) {
-                obj = hlist_entry(obj_pool.first, typeof(*obj), node);
-                hlist_del(&obj->node);
-                obj_pool_free--;
+        if (!raw_spin_trylock_irqsave(&pool_lock, flags))
+                return;
+        while (obj_pool_free >= debug_objects_pool_size + ODEBUG_FREE_BATCH) {
+                for (i = 0; i < ODEBUG_FREE_BATCH; i++) {
+                        objs[i] = hlist_entry(obj_pool.first,
+                                              typeof(*objs[0]), node);
+                        hlist_del(&objs[i]->node);
+                }
+
+                obj_pool_free -= ODEBUG_FREE_BATCH;
+                debug_objects_freed += ODEBUG_FREE_BATCH;
                 /*
                  * We release pool_lock across kmem_cache_free() to
                  * avoid contention on pool_lock.
                  */
                 raw_spin_unlock_irqrestore(&pool_lock, flags);
-                kmem_cache_free(obj_cache, obj);
-                raw_spin_lock_irqsave(&pool_lock, flags);
+                for (i = 0; i < ODEBUG_FREE_BATCH; i++)
+                        kmem_cache_free(obj_cache, objs[i]);
+                if (!raw_spin_trylock_irqsave(&pool_lock, flags))
+                        return;
         }
         raw_spin_unlock_irqrestore(&pool_lock, flags);
 }
@@ -198,7 +223,7 @@ static void free_object(struct debug_obj *obj)
          * schedule work when the pool is filled and the cache is
          * initialized:
          */
-        if (obj_pool_free > ODEBUG_POOL_SIZE && obj_cache)
+        if (obj_pool_free > debug_objects_pool_size && obj_cache)
                 sched = 1;
         hlist_add_head(&obj->node, &obj_pool);
         obj_pool_free++;
@@ -758,6 +783,8 @@ static int debug_stats_show(struct seq_file *m, void *v)
         seq_printf(m, "pool_min_free :%d\n", obj_pool_min_free);
         seq_printf(m, "pool_used     :%d\n", obj_pool_used);
         seq_printf(m, "pool_max_used :%d\n", obj_pool_max_used);
+        seq_printf(m, "objs_allocated:%d\n", debug_objects_allocated);
+        seq_printf(m, "objs_freed    :%d\n", debug_objects_freed);
         return 0;
 }
 
@@ -1116,4 +1143,11 @@ void __init debug_objects_mem_init(void)
                 pr_warn("out of memory.\n");
         } else
                 debug_objects_selftest();
+
+        /*
+         * Increase the thresholds for allocating and freeing objects
+         * according to the number of possible CPUs available in the system.
+         */
+        debug_objects_pool_size += num_possible_cpus() * 32;
+        debug_objects_pool_min_level += num_possible_cpus() * 4;
 }
diff --git a/lib/halfmd4.c b/lib/halfmd4.c
deleted file mode 100644
index 137e861d9690..000000000000
--- a/lib/halfmd4.c
+++ /dev/null
@@ -1,67 +0,0 @@
-#include <linux/compiler.h>
-#include <linux/export.h>
-#include <linux/cryptohash.h>
-#include <linux/bitops.h>
-
-/* F, G and H are basic MD4 functions: selection, majority, parity */
-#define F(x, y, z) ((z) ^ ((x) & ((y) ^ (z))))
-#define G(x, y, z) (((x) & (y)) + (((x) ^ (y)) & (z)))
-#define H(x, y, z) ((x) ^ (y) ^ (z))
-
-/*
- * The generic round function.  The application is so specific that
- * we don't bother protecting all the arguments with parens, as is generally
- * good macro practice, in favor of extra legibility.
- * Rotation is separate from addition to prevent recomputation
- */
-#define ROUND(f, a, b, c, d, x, s)      \
-        (a += f(b, c, d) + x, a = rol32(a, s))
-#define K1 0
-#define K2 013240474631UL
-#define K3 015666365641UL
-
-/*
- * Basic cut-down MD4 transform.  Returns only 32 bits of result.
- */
-__u32 half_md4_transform(__u32 buf[4], __u32 const in[8])
-{
-        __u32 a = buf[0], b = buf[1], c = buf[2], d = buf[3];
-
-        /* Round 1 */
-        ROUND(F, a, b, c, d, in[0] + K1,  3);
-        ROUND(F, d, a, b, c, in[1] + K1,  7);
-        ROUND(F, c, d, a, b, in[2] + K1, 11);
-        ROUND(F, b, c, d, a, in[3] + K1, 19);
-        ROUND(F, a, b, c, d, in[4] + K1,  3);
-        ROUND(F, d, a, b, c, in[5] + K1,  7);
-        ROUND(F, c, d, a, b, in[6] + K1, 11);
-        ROUND(F, b, c, d, a, in[7] + K1, 19);
-
-        /* Round 2 */
-        ROUND(G, a, b, c, d, in[1] + K2,  3);
-        ROUND(G, d, a, b, c, in[3] + K2,  5);
-        ROUND(G, c, d, a, b, in[5] + K2,  9);
-        ROUND(G, b, c, d, a, in[7] + K2, 13);
-        ROUND(G, a, b, c, d, in[0] + K2,  3);
-        ROUND(G, d, a, b, c, in[2] + K2,  5);
-        ROUND(G, c, d, a, b, in[4] + K2,  9);
-        ROUND(G, b, c, d, a, in[6] + K2, 13);
-
-        /* Round 3 */
-        ROUND(H, a, b, c, d, in[3] + K3,  3);
-        ROUND(H, d, a, b, c, in[7] + K3,  9);
-        ROUND(H, c, d, a, b, in[2] + K3, 11);
-        ROUND(H, b, c, d, a, in[6] + K3, 15);
-        ROUND(H, a, b, c, d, in[1] + K3,  3);
-        ROUND(H, d, a, b, c, in[5] + K3,  9);
-        ROUND(H, c, d, a, b, in[0] + K3, 11);
-        ROUND(H, b, c, d, a, in[4] + K3, 15);
-
-        buf[0] += a;
-        buf[1] += b;
-        buf[2] += c;
-        buf[3] += d;
-
-        return buf[1]; /* "most hashed" word */
-}
-EXPORT_SYMBOL(half_md4_transform);
diff --git a/lib/sbitmap.c b/lib/sbitmap.c
index 2cecf05c82fd..55e11c4b2f3b 100644
--- a/lib/sbitmap.c
+++ b/lib/sbitmap.c
@@ -17,6 +17,7 @@
 
 #include <linux/random.h>
 #include <linux/sbitmap.h>
+#include <linux/seq_file.h>
 
 int sbitmap_init_node(struct sbitmap *sb, unsigned int depth, int shift,
                       gfp_t flags, int node)
@@ -180,6 +181,62 @@ unsigned int sbitmap_weight(const struct sbitmap *sb)
 }
 EXPORT_SYMBOL_GPL(sbitmap_weight);
 
+void sbitmap_show(struct sbitmap *sb, struct seq_file *m)
+{
+        seq_printf(m, "depth=%u\n", sb->depth);
+        seq_printf(m, "busy=%u\n", sbitmap_weight(sb));
+        seq_printf(m, "bits_per_word=%u\n", 1U << sb->shift);
+        seq_printf(m, "map_nr=%u\n", sb->map_nr);
+}
+EXPORT_SYMBOL_GPL(sbitmap_show);
+
+static inline void emit_byte(struct seq_file *m, unsigned int offset, u8 byte)
+{
+        if ((offset & 0xf) == 0) {
+                if (offset != 0)
+                        seq_putc(m, '\n');
+                seq_printf(m, "%08x:", offset);
+        }
+        if ((offset & 0x1) == 0)
+                seq_putc(m, ' ');
+        seq_printf(m, "%02x", byte);
+}
+
+void sbitmap_bitmap_show(struct sbitmap *sb, struct seq_file *m)
+{
+        u8 byte = 0;
+        unsigned int byte_bits = 0;
+        unsigned int offset = 0;
+        int i;
+
+        for (i = 0; i < sb->map_nr; i++) {
+                unsigned long word = READ_ONCE(sb->map[i].word);
+                unsigned int word_bits = READ_ONCE(sb->map[i].depth);
+
+                while (word_bits > 0) {
+                        unsigned int bits = min(8 - byte_bits, word_bits);
+
+                        byte |= (word & (BIT(bits) - 1)) << byte_bits;
+                        byte_bits += bits;
+                        if (byte_bits == 8) {
+                                emit_byte(m, offset, byte);
+                                byte = 0;
+                                byte_bits = 0;
+                                offset++;
+                        }
+                        word >>= bits;
+                        word_bits -= bits;
+                }
+        }
+        if (byte_bits) {
+                emit_byte(m, offset, byte);
+                offset++;
+        }
+        if (offset)
+                seq_putc(m, '\n');
+}
+EXPORT_SYMBOL_GPL(sbitmap_bitmap_show);
+
 static unsigned int sbq_calc_wake_batch(unsigned int depth)
 {
         unsigned int wake_batch;
@@ -239,7 +296,19 @@ EXPORT_SYMBOL_GPL(sbitmap_queue_init_node);
 
 void sbitmap_queue_resize(struct sbitmap_queue *sbq, unsigned int depth)
 {
-        sbq->wake_batch = sbq_calc_wake_batch(depth);
+        unsigned int wake_batch = sbq_calc_wake_batch(depth);
+        int i;
+
+        if (sbq->wake_batch != wake_batch) {
+                WRITE_ONCE(sbq->wake_batch, wake_batch);
+                /*
+                 * Pairs with the memory barrier in sbq_wake_up() to ensure that
+                 * the batch size is updated before the wait counts.
+                 */
+                smp_mb__before_atomic();
+                for (i = 0; i < SBQ_WAIT_QUEUES; i++)
+                        atomic_set(&sbq->ws[i].wait_cnt, 1);
+        }
         sbitmap_resize(&sbq->sb, depth);
 }
 EXPORT_SYMBOL_GPL(sbitmap_queue_resize);
@@ -297,20 +366,39 @@ static struct sbq_wait_state *sbq_wake_ptr(struct sbitmap_queue *sbq)
 static void sbq_wake_up(struct sbitmap_queue *sbq)
 {
         struct sbq_wait_state *ws;
+        unsigned int wake_batch;
         int wait_cnt;
 
-        /* Ensure that the wait list checks occur after clear_bit(). */
-        smp_mb();
+        /*
+         * Pairs with the memory barrier in set_current_state() to ensure the
+         * proper ordering of clear_bit()/waitqueue_active() in the waker and
+         * test_and_set_bit()/prepare_to_wait()/finish_wait() in the waiter. See
+         * the comment on waitqueue_active(). This is __after_atomic because we
+         * just did clear_bit() in the caller.
+         */
+        smp_mb__after_atomic();
 
         ws = sbq_wake_ptr(sbq);
         if (!ws)
                 return;
 
         wait_cnt = atomic_dec_return(&ws->wait_cnt);
-        if (unlikely(wait_cnt < 0))
-                wait_cnt = atomic_inc_return(&ws->wait_cnt);
-        if (wait_cnt == 0) {
-                atomic_add(sbq->wake_batch, &ws->wait_cnt);
+        if (wait_cnt <= 0) {
+                wake_batch = READ_ONCE(sbq->wake_batch);
+                /*
+                 * Pairs with the memory barrier in sbitmap_queue_resize() to
+                 * ensure that we see the batch size update before the wait
+                 * count is reset.
+                 */
+                smp_mb__before_atomic();
+                /*
+                 * If there are concurrent callers to sbq_wake_up(), the last
+                 * one to decrement the wait count below zero will bump it back
+                 * up. If there is a concurrent resize, the count reset will
+                 * either cause the cmpxchg to fail or overwrite after the
+                 * cmpxchg.
+                 */
+                atomic_cmpxchg(&ws->wait_cnt, wait_cnt, wait_cnt + wake_batch);
                 sbq_index_atomic_inc(&sbq->wake_index);
                 wake_up(&ws->wait);
         }
@@ -331,7 +419,8 @@ void sbitmap_queue_wake_all(struct sbitmap_queue *sbq)
         int i, wake_index;
 
         /*
-         * Make sure all changes prior to this are visible from other CPUs.
+         * Pairs with the memory barrier in set_current_state() like in
+         * sbq_wake_up().
          */
         smp_mb();
         wake_index = atomic_read(&sbq->wake_index);
@@ -345,3 +434,37 @@ void sbitmap_queue_wake_all(struct sbitmap_queue *sbq)
         }
 }
 EXPORT_SYMBOL_GPL(sbitmap_queue_wake_all);
+
+void sbitmap_queue_show(struct sbitmap_queue *sbq, struct seq_file *m)
+{
+        bool first;
+        int i;
+
+        sbitmap_show(&sbq->sb, m);
+
+        seq_puts(m, "alloc_hint={");
+        first = true;
+        for_each_possible_cpu(i) {
+                if (!first)
+                        seq_puts(m, ", ");
+                first = false;
+                seq_printf(m, "%u", *per_cpu_ptr(sbq->alloc_hint, i));
+        }
+        seq_puts(m, "}\n");
+
+        seq_printf(m, "wake_batch=%u\n", sbq->wake_batch);
+        seq_printf(m, "wake_index=%d\n", atomic_read(&sbq->wake_index));
+
+        seq_puts(m, "ws={\n");
+        for (i = 0; i < SBQ_WAIT_QUEUES; i++) {
+                struct sbq_wait_state *ws = &sbq->ws[i];
+
+                seq_printf(m, "\t{.wait_cnt=%d, .wait=%s},\n",
+                           atomic_read(&ws->wait_cnt),
+                           waitqueue_active(&ws->wait) ? "active" : "inactive");
+        }
+        seq_puts(m, "}\n");
+
+        seq_printf(m, "round_robin=%d\n", sbq->round_robin);
+}
+EXPORT_SYMBOL_GPL(sbitmap_queue_show);
diff --git a/lib/timerqueue.c b/lib/timerqueue.c
index adc6ee0a5126..4a720ed4fdaf 100644
--- a/lib/timerqueue.c
+++ b/lib/timerqueue.c
@@ -80,8 +80,7 @@ bool timerqueue_del(struct timerqueue_head *head, struct timerqueue_node *node)
         if (head->next == node) {
                 struct rb_node *rbn = rb_next(&node->node);
 
-                head->next = rbn ?
-                        rb_entry(rbn, struct timerqueue_node, node) : NULL;
+                head->next = rb_entry_safe(rbn, struct timerqueue_node, node);
         }
         rb_erase(&node->node, &head->head);
         RB_CLEAR_NODE(&node->node);