Signed-off-by: Kunwu Chan <[email protected]>
---
kernel/hazptr.c | 93 +++++++++++++++++++++++++++++++++++++++++++------
1 file changed, 83 insertions(+), 10 deletions(-)
diff --git a/kernel/hazptr.c b/kernel/hazptr.c
index 9e274a691af5..900ba35de2cb 100644
--- a/kernel/hazptr.c
+++ b/kernel/hazptr.c
@@ -7,6 +7,7 @@
*/
#include <linux/hazptr.h>
+#include <linux/bitops.h>
#include <linux/percpu.h>
#include <linux/spinlock.h>
#include <linux/mutex.h>
@@ -16,6 +17,7 @@
#include <linux/kthread.h>
#include <linux/swait.h>
#include <linux/sched.h>
+#include <linux/bitmap.h>
/*
* The current hazard pointer wildcard. Flips between 1UL and 2UL to guarantee
@@ -213,6 +215,55 @@ void hazptr_scan_period(void *addr, void *scan_wildcard)
}
}
+/* Number of hash functions for the Bloom filter. */
+#define HAZPTR_BLOOM_HASHES 3
+
+/* Number of bits in the Bloom filter bitmap: one page. */
+#define HAZPTR_BLOOM_NBITS (PAGE_SIZE * 8)
+
+struct hazptr_bloom {
+ unsigned long map[PAGE_SIZE / sizeof(unsigned long)];
+};
+
+/*
+ * Multiply @addr by a per-hash odd constant and use the high bits
+ * as the Bloom filter index.
+ */
+static unsigned long hazptr_bloom_hash(void *addr, unsigned int i)
+{
+ static const u64 mult[HAZPTR_BLOOM_HASHES] = {
+ 0x9E3779B97F4A7C15ULL,
+ 0xC2B2AE3D27D4EB4FULL,
+ 0x165667B19E3779F9ULL,
+ };
+ u64 hash = (u64)(unsigned long)addr * mult[i];
+
+ return hash >> (64 - ilog2(HAZPTR_BLOOM_NBITS));
+}
+
+static void hazptr_bloom_reset(struct hazptr_bloom *bloom)
+{
+ bitmap_zero(bloom->map, HAZPTR_BLOOM_NBITS);
+}
+
+static void hazptr_bloom_add(struct hazptr_bloom *bloom, void *addr)
+{
+ unsigned int i;
+
+ for (i = 0; i < HAZPTR_BLOOM_HASHES; i++)
+ __set_bit(hazptr_bloom_hash(addr, i), bloom->map);
+}
+
+static bool hazptr_bloom_contains(const struct hazptr_bloom *bloom, void *addr)
+{
+ unsigned int i;
+
+ for (i = 0; i < HAZPTR_BLOOM_HASHES; i++)
+ if (!test_bit(hazptr_bloom_hash(addr, i), bloom->map))
+ return false;
+ return true;
+}
+
struct hazptr_waiter {
struct list_head node;
void *addr;
@@ -226,17 +277,26 @@ struct hazptr_scan_state {
struct mutex lock;
struct list_head pending;
struct list_head scanning; /* kthread only */
+ struct hazptr_bloom bloom; /* kthread only */
};
static struct hazptr_scan_state hazptr_scan;
/*
- * Check per-CPU slots before overflow-list slots to match the
- * acquisition ordering of promoted slots.
+ * Walk all slots and return true if @watch is present. If @bloom
+ * is non-NULL, record observed non-wildcard addresses in it.
+ *
+ * Per-CPU slots are examined before overflow-list slots on each CPU
+ * to preserve the acquisition ordering required by the promote path:
+ * synchronize must observe the per-CPU slot release before the
+ * overflow-list entry can be missed.
*/
-static bool hazptr_value_present(void *val)
+static bool hazptr_scan_walk(void *watch, struct hazptr_bloom *bloom)
{
int cpu;
+ if (bloom)
+ hazptr_bloom_reset(bloom);
+
for_each_possible_cpu(cpu) {
struct hazptr_percpu_slots *percpu_slots =
per_cpu_ptr(&hazptr_percpu_slots, cpu);
struct hazptr_overflow_list_flip *overflow_list_flip =
per_cpu_ptr(&percpu_overflow_list_flip, cpu);
@@ -244,10 +304,14 @@ static bool hazptr_value_present(void *val)
for (idx = 0; idx < NR_HAZPTR_PERCPU_SLOTS; idx++) {
struct hazptr_slot_item *item =
&percpu_slots->items[idx];
+ void *v;
/* Pairs with smp_store_release in hazptr_release(). */
- if (smp_load_acquire(&item->slot.addr) == val)
+ v = smp_load_acquire(&item->slot.addr);
+ if (v == watch)
return true;
+ if (bloom && v && !is_wildcard(v))
+ hazptr_bloom_add(bloom, v);
}
for (int i = 0; i < 2; i++) {
struct hazptr_overflow_list *list =
&overflow_list_flip->array[i];
@@ -256,11 +320,16 @@ static bool hazptr_value_present(void *val)
raw_spin_lock_irqsave(&list->lock, flags);
hlist_for_each_entry(b, &list->head, overflow_node) {
+ void *v;
+
/* Pairs with smp_store_release in
hazptr_release(). */
- if (smp_load_acquire(&b->slot.addr) == val) {
+ v = smp_load_acquire(&b->slot.addr);
+ if (v == watch) {
raw_spin_unlock_irqrestore(&list->lock,
flags);
return true;
}
+ if (bloom && v && !is_wildcard(v))
+ hazptr_bloom_add(bloom, v);
}
raw_spin_unlock_irqrestore(&list->lock, flags);
}
@@ -276,7 +345,7 @@ static bool hazptr_value_present(void *val)
*/
static void hazptr_drain_wildcard(void *wc)
{
- while (hazptr_value_present(wc))
+ while (hazptr_scan_walk(wc, NULL))
cond_resched();
}
@@ -309,12 +378,16 @@ static void hazptr_scan_do_cycle(void)
WRITE_ONCE(hazptr_wildcard, scan_wildcard);
old_wildcard = flip_wildcard(scan_wildcard);
- /* Pass 2: drain the old wildcard. */
- hazptr_drain_wildcard(old_wildcard);
+ /*
+ * Pass 2: drain the old wildcard while collecting observed
+ * addresses into the Bloom filter.
+ */
+ while (hazptr_scan_walk(old_wildcard, &hazptr_scan.bloom))
+ cond_resched();
- /* Complete waiters whose address is no longer held by any slot. */
+ /* Complete waiters whose address is not in the filter. */
list_for_each_entry_safe(w, n, &hazptr_scan.scanning, node) {
- if (!hazptr_value_present(w->addr))
+ if (!hazptr_bloom_contains(&hazptr_scan.bloom, w->addr))
list_move(&w->node, &done);
}
