Skip to contentSkip to conversation

Add hazard pointers to kernel

RFC PATCH In review Boqun Feng 11 participants 67 messages Sep 17, 2024 – Sep 28, 2024

Subsystems (5)
lore
Share & tools
lore

Boqun Feng

author
#0 lore raw

cover Add hazard pointers to kernel

Hi,

This series introduces hazard pointers [1] to kernel space. A TL;DR description of hazard pointers is "a scalable refcounting mechanim with RCU-like API". More information can be found at [2].

The problem we are trying to resolve here is refcount scalability issues that cannot be resolved simply by RCU or SRCU (maybe due to the requirement of an unbound protect duration). Neeraj has tried it in the scalability issue[3] he has been working on, and he will share more information in our LPC session [4] (and I will update in the list for those who cannot make it to the session later).

My micro-benchmark shows the hazard pointers provide very good scalability on par with percpu_ref/RCU/SRCU on the reader side:

(refscale in x86_64 + PREEMPT=y, avg reader duration in ns)
nreaders 1 8 32
percpu_ref 6.95123 10.0869 8.9674
rcu 2.97923 3.243 3.55077
hazptr 8.5991 8.40443 8.5762
srcu 16.7754 22.4807 20.2406

Things that we know are currently not working:

* Handling module unload, probably needs a hazptr_barrier()
similar to rcu_barrier().

* rcutorture support should be added to catch potential bugs (esp.
for callback handling).

* Improvement for updater side performance, currently all
callbacks are handled in one work, this can be improved by using multiple work_structs or threads.

Of course, I might create some bugs, so please take a look. Also love to hear anything on the current API. Any feedback is welcome!

Patch #1 is the implemenation of hazptr, Paul and Neeraj contributed a lot, but all bugs are mine ;-)

Patch 2-3 add micro-benchmarks for hazptr and percpu_ref.

Patch #4 is a simple test I've used for development, I put it here just in case someone wants to give a quick try, eventually, we need to add hazptr to rcutorture (or has its own torture) for more testing.

Regards,
Boqun

[1]: M. M. Michael, "Hazard pointers: safe memory reclamation for
lock-free objects," in IEEE Transactions on Parallel and Distributed Systems, vol. 15, no. 6, pp. 491-504, June 2004
[2]: https://docs.google.com/document/d/113WFjGlAW4m72xNbZWHUSE-yU2HIJnWpiXp91ShtgeE/
[3]: https://lore.kernel.org/lkml/[email protected]/
[4]: https://lpc.events/event/18/contributions/1731/
[5]: Herlihy, Maurice, Victor Luchangco, and Mark Moir. "The repeat
offender problem: A mechanism for supporting dynamic-sized, lock-free data structures." International Symposium on Distributed Computing. Berlin, Heidelberg: Springer Berlin Heidelberg, 2002.

Boqun Feng (4):
hazptr: Add initial implementation of hazard pointers
refscale: Add benchmarks for hazptr
refscale: Add benchmarks for percpu_ref
WIP: hazptr: Add hazptr test sample

 include/linux/hazptr.h       |  83 +++++++
 kernel/Makefile              |   1 +
 kernel/hazptr.c              | 463 +++++++++++++++++++++++++++++++++++
 kernel/rcu/refscale.c        | 127 +++++++++-
 samples/Kconfig              |   6 +
 samples/Makefile             |   1 +
 samples/hazptr/hazptr_test.c |  87 +++++++
 7 files changed, 767 insertions(+), 1 deletion(-)
 create mode 100644 include/linux/hazptr.h
 create mode 100644 kernel/hazptr.c
 create mode 100644 samples/hazptr/hazptr_test.c
Signature · 1 line
2.45.2
author
#1 lore raw

RFC PATCH 1/4 hazptr: Add initial implementation of hazard pointers

Hazard pointers [1] provide a way to dynamically distribute refcounting and can be used to improve the scalability of refcounting without significant space cost.

Hazard pointers are similar to RCU: they build the synchronization between two part, readers and updaters. Readers are refcount users, they acquire and release refcount. Updaters cleanup objects when there are no reader referencing them (via call_hazptr()). The difference is instead of waiting for a grace period, hazard pointers can free an object as long as there is no one referencing the object. This means for a particular workload, hazard pointers may have smaller memory footprint due to fewer pending callbacks.

The synchronization between readers and updaters is built around "hazard pointer slots": a slot readers can use to store a pointer value.

Reader side protection:

1. Read the value of a pointer to the target data element.
2. Store it to a hazard pointer slot.
3. Enforce full ordering (e.g. smp_mb()).
4. Re-read the original pointer, reset the slot and retry if the
value changed.
5. Otherwise, the continued existence of the target data element
is guaranteed.

Updater side check:

1. Unpublish the target data element (e.g. setting the pointer
value to NULL).
2. Enforce full ordering.
3. Read the value from a hazard pointer slot.
4. If the value doesn't match the target data element, then this
slot doesn't represent a reference to it.
5. Otherwise, updater needs to re-check (step 3).

To distribute the accesses of hazptr slots from different contexts, hazptr_context is introduced. Users need to define/allocate their own hazptr_context to allocate hazard pointer slots.

For the updater side to confirm no existing reference, it needs to scan all the possible slots, and to speed up this process, hazptr_context also contains an rbtree node for each slot so that updater can cache the reader-scan result in an rbtree. The rbtree nodes are pre-allocated in this way to prevent "allocate memory to free memory" in extreme cases.

[1]: M. M. Michael, "Hazard pointers: safe memory reclamation for
lock-free objects," in IEEE Transactions on Parallel and Distributed Systems, vol. 15, no. 6, pp. 491-504, June 2004

---
 include/linux/hazptr.h |  83 ++++++++
 kernel/Makefile        |   1 +
 kernel/hazptr.c        | 463 +++++++++++++++++++++++++++++++++++++++++
 3 files changed, 547 insertions(+)
 create mode 100644 include/linux/hazptr.h
 create mode 100644 kernel/hazptr.c
include/linux/hazptr.h new file +83 -0
new file mode 100644
index 000000000000..4548ca8c75eb
@@ -0,0 +1,83 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+#ifndef _LINUX_HAZPTR_H
+#define _LINUX_HAZPTR_H
+
+#include <linux/list.h>
+#include <linux/spinlock.h>
+#include <linux/rbtree.h>
+
+/* Hazard pointer slot. */
+typedef void* hazptr_t;
+
+#define HAZPTR_SLOT_PER_CTX 8
+
+struct hazptr_slot_snap {
+	struct rb_node node;
+	hazptr_t slot;
+};
+
+/*
+ * A set of hazard pointer slots for a context.
+ *
+ * The context can be a task, CPU or reader (depends on the use case). It may
+ * be allocated statically or dynamically. It can only be used after calling
+ * init_hazptr_context(), and users are also responsible to call
+ * cleaup_hazptr_context() when it's not used any more.
+ */
+struct hazptr_context {
+	// The lock of the percpu context lists.
+	spinlock_t *lock;
+
+	struct list_head list;
+	struct hazptr_slot_snap snaps[HAZPTR_SLOT_PER_CTX];
+	____cacheline_aligned hazptr_t slots[HAZPTR_SLOT_PER_CTX];
+};
+
+void init_hazptr_context(struct hazptr_context *hzcp);
+void cleanup_hazptr_context(struct hazptr_context *hzcp);
+hazptr_t *hazptr_alloc(struct hazptr_context *hzcp);
+void hazptr_free(struct hazptr_context *hzcp, hazptr_t *hzp);
+
+#define hazptr_tryprotect(hzp, gp, field)	(typeof(gp))__hazptr_tryprotect(hzp, (void **)&(gp), offsetof(typeof(*gp), field))
+#define hazptr_protect(hzp, gp, field) ({				\
+	typeof(gp) ___p;						\
+									\
+	___p = hazptr_tryprotect(hzp, gp, field);			\
+	BUG_ON(!___p);							\
+	___p;								\
+})
+
+static inline void *__hazptr_tryprotect(hazptr_t *hzp,
+					void *const *p,
+					unsigned long head_offset)
+{
+	void *ptr;
+	struct callback_head *head;
+
+	ptr = READ_ONCE(*p);
+
+	if (ptr == NULL)
+		return NULL;
+
+	head = (struct callback_head *)(ptr + head_offset);
+
+	WRITE_ONCE(*hzp, head);
+	smp_mb();
+
+	ptr = READ_ONCE(*p); // read again
+
+	if (ptr + head_offset != head) { // pointer changed
+		WRITE_ONCE(*hzp, NULL);  // reset hazard pointer
+		return NULL;
+	} else
+		return ptr;
+}
+
+static inline void hazptr_clear(hazptr_t *hzp)
+{
+	/* Pairs with smp_load_acquire() in reader scan. */
+	smp_store_release(hzp, NULL);
+}
+
+void call_hazptr(struct callback_head *head, rcu_callback_t func);
+#endif
kernel/Makefile +1 -0
index 3c13240dfc9f..7927264b9870 100644
@@ -50,6 +50,7 @@ obj-y += rcu/
 obj-y += livepatch/
 obj-y += dma/
 obj-y += entry/
+obj-y += hazptr.o
 obj-$(CONFIG_MODULES) += module/
 
 obj-$(CONFIG_KCMP) += kcmp.o
kernel/hazptr.c new file +463 -0

463 lines not on this page · raw message

Signature · 1 line
2.45.2
#2 lore raw

Re: [RFC PATCH 1/4] hazptr: Add initial implementation of hazard pointers

On 2024-09-17 16:33, Boqun Feng wrote:
[...]

Quoted 16 lines

The synchronization between readers and updaters is built around "hazard pointer slots": a slot readers can use to store a pointer value.

Reader side protection:

1. Read the value of a pointer to the target data element.
2. Store it to a hazard pointer slot.
3. Enforce full ordering (e.g. smp_mb()).
4. Re-read the original pointer, reset the slot and retry if the
value changed.
5. Otherwise, the continued existence of the target data element
is guaranteed.

Updater side check:

Quoted 7 lines

1. Unpublish the target data element (e.g. setting the pointer
value to NULL).
2. Enforce full ordering.
3. Read the value from a hazard pointer slot.
4. If the value doesn't match the target data element, then this
slot doesn't represent a reference to it.
5. Otherwise, updater needs to re-check (step 3).

Cool! I look forward to see where this is meant to be used. I would expect it to be a useful tool to speed up reference counting of things like the mm_struct and for TLB flush IPIs.

On a related note, with a userspace port in mind, the membarrier(2) syscall can be useful to turn the smp_mb() in (3) from the reader side into a simple compiler barrier, assuming (2) from the updater is using membarrier. If IPIs are acceptable (or already required) for some kernel use-cases, this means a similar asymmetric fence scheme could be used to speed up readers.

Thanks,

Mathieu

Signature · 3 lines
Mathieu Desnoyers
EfficiOS Inc.
https://www.efficios.com
#3 lore raw

Re: [RFC PATCH 1/4] hazptr: Add initial implementation of hazard pointers

In reply to Boqun Feng

2024年9月17日 22:33,Boqun Feng <[email protected]> wrote:

Quoted 106 lines

Hazard pointers [1] provide a way to dynamically distribute refcounting and can be used to improve the scalability of refcounting without significant space cost.

Hazard pointers are similar to RCU: they build the synchronization between two part, readers and updaters. Readers are refcount users, they acquire and release refcount. Updaters cleanup objects when there are no reader referencing them (via call_hazptr()). The difference is instead of waiting for a grace period, hazard pointers can free an object as long as there is no one referencing the object. This means for a particular workload, hazard pointers may have smaller memory footprint due to fewer pending callbacks.

The synchronization between readers and updaters is built around "hazard pointer slots": a slot readers can use to store a pointer value.

Reader side protection:

1. Read the value of a pointer to the target data element.
2. Store it to a hazard pointer slot.
3. Enforce full ordering (e.g. smp_mb()).
4. Re-read the original pointer, reset the slot and retry if the value changed.
5. Otherwise, the continued existence of the target data element is guaranteed.

Updater side check:

1. Unpublish the target data element (e.g. setting the pointer value to NULL).
2. Enforce full ordering.
3. Read the value from a hazard pointer slot.
4. If the value doesn't match the target data element, then this slot doesn't represent a reference to it.
5. Otherwise, updater needs to re-check (step 3).

To distribute the accesses of hazptr slots from different contexts, hazptr_context is introduced. Users need to define/allocate their own hazptr_context to allocate hazard pointer slots.

For the updater side to confirm no existing reference, it needs to scan all the possible slots, and to speed up this process, hazptr_context also contains an rbtree node for each slot so that updater can cache the reader-scan result in an rbtree. The rbtree nodes are pre-allocated in this way to prevent "allocate memory to free memory" in extreme cases.

[1]: M. M. Michael, "Hazard pointers: safe memory reclamation for
lock-free objects," in IEEE Transactions on Parallel and Distributed Systems, vol. 15, no. 6, pp. 491-504, June 2004

---

include/linux/hazptr.h |  83 ++++++++
kernel/Makefile        |   1 +
kernel/hazptr.c        | 463 +++++++++++++++++++++++++++++++++++++++++
3 files changed, 547 insertions(+)

create mode 100644 include/linux/hazptr.h
create mode 100644 kernel/hazptr.c

include/linux/hazptr.h new file +36 -0
new file mode 100644
index 000000000000..4548ca8c75eb
@@ -0,0 +1,83 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+#ifndef _LINUX_HAZPTR_H
+#define _LINUX_HAZPTR_H
+
+#include <linux/list.h>
+#include <linux/spinlock.h>
+#include <linux/rbtree.h>
+
+/* Hazard pointer slot. */
+typedef void* hazptr_t;
+
+#define HAZPTR_SLOT_PER_CTX 8
+
+struct hazptr_slot_snap {
+ struct rb_node node;
+ hazptr_t slot;
+};
+
+/*
+ * A set of hazard pointer slots for a context.
+ *
+ * The context can be a task, CPU or reader (depends on the use case). It may
+ * be allocated statically or dynamically. It can only be used after calling
+ * init_hazptr_context(), and users are also responsible to call
+ * cleaup_hazptr_context() when it's not used any more.
+ */
+struct hazptr_context {
+ // The lock of the percpu context lists.
+ spinlock_t *lock;
+
+ struct list_head list;
+ struct hazptr_slot_snap snaps[HAZPTR_SLOT_PER_CTX];
+ ____cacheline_aligned hazptr_t slots[HAZPTR_SLOT_PER_CTX];
+};
+
+void init_hazptr_context(struct hazptr_context *hzcp);

include/linux/hazptr.h line 46

Quoted 10 lines
include/linux/hazptr.h new file +10 -0
+void cleanup_hazptr_context(struct hazptr_context *hzcp);
+hazptr_t *hazptr_alloc(struct hazptr_context *hzcp);
+void hazptr_free(struct hazptr_context *hzcp, hazptr_t *hzp);
+
+#define hazptr_tryprotect(hzp, gp, field) (typeof(gp))__hazptr_tryprotect(hzp, (void **)&(gp), offsetof(typeof(*gp), field))
+#define hazptr_protect(hzp, gp, field) ({ \
+ typeof(gp) ___p; \
+ \
+ ___p = hazptr_tryprotect(hzp, gp, field); \
+ BUG_ON(!___p); \

hazptr_tryprotect might return NULL, do you need a loop here?

Quoted 522 lines
include/linux/hazptr.h new file +37 -0
+ ___p; \
+})
+
+static inline void *__hazptr_tryprotect(hazptr_t *hzp,
+ void *const *p,
+ unsigned long head_offset)
+{
+ void *ptr;
+ struct callback_head *head;
+
+ ptr = READ_ONCE(*p);
+
+ if (ptr == NULL)
+ return NULL;
+
+ head = (struct callback_head *)(ptr + head_offset);
+
+ WRITE_ONCE(*hzp, head);
+ smp_mb();
+
+ ptr = READ_ONCE(*p); // read again
+
+ if (ptr + head_offset != head) { // pointer changed
+ WRITE_ONCE(*hzp, NULL);  // reset hazard pointer
+ return NULL;
+ } else
+ return ptr;
+}
+
+static inline void hazptr_clear(hazptr_t *hzp)
+{
+ /* Pairs with smp_load_acquire() in reader scan. */
+ smp_store_release(hzp, NULL);
+}
+
+void call_hazptr(struct callback_head *head, rcu_callback_t func);
+#endif
kernel/Makefile +0 -0
index 3c13240dfc9f..7927264b9870 100644
@@ -50,6 +50,7 @@ obj-y += rcu/

obj-y += livepatch/
obj-y += dma/
obj-y += entry/
+obj-y += hazptr.o
obj-$(CONFIG_MODULES) += module/

obj-$(CONFIG_KCMP) += kcmp.o

kernel/hazptr.c new file +463 -0
new file mode 100644
index 000000000000..f22ccc2a4a62
@@ -0,0 +1,463 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+
+#include <linux/spinlock.h>
+#include <linux/cleanup.h>
+#include <linux/hazptr.h>
+#include <linux/percpu.h>
+#include <linux/workqueue.h>
+
+#define HAZPTR_UNUSED (1ul)
+
+/* Per-CPU data for hazard pointer management. */
+struct hazptr_percpu {
+ spinlock_t ctx_lock; /* hazptr context list lock */
+ struct list_head ctx_list; /* hazptr context list */
+ spinlock_t callback_lock; /* Per-CPU callback queue lock */
+ struct callback_head *queued; /* Per-CPU callback queue */
+ struct callback_head **tail;
+};
+
+/*
+ * Per-CPU data contains context lists and callbacks, which are maintained in a
+ * per-CPU maner to reduce potential contention. This means a global scan (for
+ * readers or callbacks) has to take each CPU's lock, but it's less problematic
+ * because that's a slowpath.
+ */
+DEFINE_PER_CPU(struct hazptr_percpu, hzpcpu);
+
+/* A RBTree that stores the reader scan result of all hazptr slot */
+struct hazptr_reader_tree {
+ spinlock_t lock;
+ struct rb_root root;
+};
+
+static void init_hazptr_reader_tree(struct hazptr_reader_tree *tree)
+{
+ spin_lock_init(&tree->lock);
+ tree->root = RB_ROOT;
+}
+
+static bool is_null_or_unused(hazptr_t slot)
+{
+ return slot == NULL || ((unsigned long)slot) == HAZPTR_UNUSED;
+}
+
+static int hazptr_node_cmp(const void *key, const struct rb_node *curr)
+{
+ unsigned long slot = (unsigned long)key;
+ struct hazptr_slot_snap *curr_snap = container_of(curr, struct hazptr_slot_snap, node);
+ unsigned long curr_slot = (unsigned long)(curr_snap->slot);
+
+ if (slot < curr_slot)
+ return -1;
+ else if (slot > curr_slot)
+ return 1;
+ else
+ return 0;
+}
+
+static bool hazptr_node_less(struct rb_node *new, const struct rb_node *curr)
+{
+ struct hazptr_slot_snap *new_snap = container_of(new, struct hazptr_slot_snap, node);
+
+ return hazptr_node_cmp((void *)new_snap->slot, curr) < 0;
+}
+
+/* Add the snapshot into a search tree. tree->lock must be held. */
+static inline void reader_add_locked(struct hazptr_reader_tree *tree,
+     struct hazptr_slot_snap *snap)
+{
+ lockdep_assert_held(&tree->lock);
+ BUG_ON(is_null_or_unused(snap->slot));
+
+ rb_add(&snap->node, &tree->root, hazptr_node_less);
+}
+
+static inline void reader_add(struct hazptr_reader_tree *tree,
+      struct hazptr_slot_snap *snap)
+{
+ guard(spinlock_irqsave)(&tree->lock);
+
+ reader_add_locked(tree, snap);
+}
+
+/* Delete the snapshot from a search tree. tree->lock must be held. */
+static inline void reader_del_locked(struct hazptr_reader_tree *tree,
+     struct hazptr_slot_snap *snap)
+{
+ lockdep_assert_held(&tree->lock);
+
+ rb_erase(&snap->node, &tree->root);
+}
+
+static inline void reader_del(struct hazptr_reader_tree *tree,
+      struct hazptr_slot_snap *snap)
+{
+ guard(spinlock_irqsave)(&tree->lock);
+
+ reader_del_locked(tree, snap);
+}
+
+/* Find whether a read exists. tree->lock must be held. */
+static inline bool reader_exist_locked(struct hazptr_reader_tree *tree,
+       unsigned long slot)
+{
+ lockdep_assert_held(&tree->lock);
+
+ return !!rb_find((void *)slot, &tree->root, hazptr_node_cmp);
+}
+
+static inline bool reader_exist(struct hazptr_reader_tree *tree,
+ unsigned long slot)
+{
+ guard(spinlock_irqsave)(&tree->lock);
+
+ return reader_exist_locked(tree, slot);
+}
+
+/*
+ * Scan the readers from one hazptr context and update the global readers tree.
+ *
+ * Must be called with hzcp->lock held.
+ */
+static void hazptr_context_snap_readers_locked(struct hazptr_reader_tree *tree,
+       struct hazptr_context *hzcp)
+{
+ lockdep_assert_held(hzcp->lock);
+
+ for (int i = 0; i < HAZPTR_SLOT_PER_CTX; i++) {
+ /*
+ * Pairs with smp_store_release() in hazptr_{clear,free}().
+ *
+ * Ensure
+ *
+ * <reader> <updater>
+ *
+ * [access protected pointers]
+ * hazptr_clear();
+ *   smp_store_release()
+ * // in reader scan.
+ * smp_load_acquire(); // is null or unused.
+ * [run callbacks] // all accesses from
+ * // reader must be
+ * // observed.
+ */
+ hazptr_t val = smp_load_acquire(&hzcp->slots[i]);
+
+ if (!is_null_or_unused(val)) {
+ struct hazptr_slot_snap *snap = &hzcp->snaps[i];
+
+ // Already in the tree, need to remove first.
+ if (!is_null_or_unused(snap->slot)) {
+ reader_del(tree, snap);
+ }
+ snap->slot = val;
+ reader_add(tree, snap);
+ }
+ }
+}
+
+/*
+ * Initialize a hazptr context.
+ *
+ * Must be called before using the context for hazptr allocation.
+ */
+void init_hazptr_context(struct hazptr_context *hzcp)
+{
+ struct hazptr_percpu *pcpu = this_cpu_ptr(&hzpcpu);
+
+ for (int i = 0; i < HAZPTR_SLOT_PER_CTX; i++) {
+ hzcp->slots[i] = (hazptr_t)HAZPTR_UNUSED;
+ hzcp->snaps[i].slot = (hazptr_t)HAZPTR_UNUSED;
+ }
+
+ guard(spinlock_irqsave)(&pcpu->ctx_lock);
+ list_add(&hzcp->list, &pcpu->ctx_list);
+ hzcp->lock = &pcpu->ctx_lock;
+}
+
+struct hazptr_struct {
+ struct work_struct work;
+ bool scheduled;
+
+ // list of callbacks, we move percpu queued callbacks into the global
+ // queued list in workqueue function.
+ spinlock_t callback_lock;
+ struct callback_head *queued;
+ struct callback_head **tail;
+
+ struct hazptr_reader_tree readers;
+};
+
+static struct hazptr_struct hazptr_struct;
+
+/*
+ * Clean up hazptr context.
+ *
+ * Must call before freeing the context. This function also removes any
+ * reference held by the hazard pointer slots in the context, even
+ * hazptr_clear() or hazptr_free() is not called previously.
+ */
+void cleanup_hazptr_context(struct hazptr_context *hzcp)
+{
+ if (hzcp->lock) {
+ scoped_guard(spinlock_irqsave, hzcp->lock) {
+ list_del(&hzcp->list);
+ hzcp->lock = NULL;
+ }
+
+ for (int i = 0; i < HAZPTR_SLOT_PER_CTX; i++) {
+ struct hazptr_slot_snap *snap = &hzcp->snaps[i];
+
+ if (!is_null_or_unused(snap->slot))
+ reader_del(&hazptr_struct.readers, snap);
+ }
+ }
+}
+
+/*
+ * Allocate a hazptr slot from a hazptr_context.
+ *
+ * Return: NULL means fail to allocate, otherwise the address of the allocated
+ * slot.
+ */
+hazptr_t *hazptr_alloc(struct hazptr_context *hzcp)
+{
+ unsigned long unused;
+
+ for (int i = 0; i < HAZPTR_SLOT_PER_CTX; i++) {
+ if (((unsigned long)READ_ONCE(hzcp->slots[i])) == HAZPTR_UNUSED) {
+ unused = HAZPTR_UNUSED;
+
+ /*
+ * rwm-sequence is relied on here.
+ *
+ * This is needed since in case of a previous reader:
+ *
+ * <reader 1> <reader 2> <updater>
+ * [access protected pointers]
+ * hazptr_free():
+ *   smp_store_release(); // hzptr == UNUSED
+ * hazptr_alloc():
+ *  try_cmpxchg_relaxed(); // hzptr == NULL
+ *
+ * // in reader scan
+ * smp_load_acquire(); // is null
+ * [run callbacks]
+ *
+ * Because of the rwm-sequence of release operations,
+ * when callbacks are run, accesses from reader 1 must
+ * be already observed by the updater.
+ */
+ if (try_cmpxchg_relaxed(&hzcp->slots[i], &unused, NULL)) {
+ return (hazptr_t *)&hzcp->slots[i];
+ }
+ }
+ }
+
+ return NULL;
+}
+
+/* Free a hazptr slot. */
+void hazptr_free(struct hazptr_context *hzcp, hazptr_t *hzptr)
+{
+ WARN_ON(((unsigned long)*hzptr) == HAZPTR_UNUSED);
+
+ /* Pairs with smp_load_acquire() in reader scan */
+ smp_store_release(hzptr, (void *)HAZPTR_UNUSED);
+}
+
+/* Scan all possible readers, and update the global reader tree. */
+static void check_readers(struct hazptr_struct *hzst)
+{
+ int cpu;
+
+ for_each_possible_cpu(cpu) {
+ struct hazptr_percpu *pcpu = per_cpu_ptr(&hzpcpu, cpu);
+ struct hazptr_context *ctx;
+
+ guard(spinlock_irqsave)(&pcpu->ctx_lock);
+ list_for_each_entry(ctx, &pcpu->ctx_list, list)
+ hazptr_context_snap_readers_locked(&hzst->readers, ctx);
+ }
+}
+
+/*
+ * Start the background work for hazptr callback handling if not started.
+ *
+ * Must be called with hazptr_struct lock held.
+ */
+static void kick_hazptr_work(void)
+{
+ if (hazptr_struct.scheduled)
+ return;
+
+ queue_work(system_wq, &hazptr_struct.work);
+ hazptr_struct.scheduled = true;
+}
+
+/*
+ * Check which callbacks are ready to be called.
+ *
+ * Return: a callback list that no reader is referencing the corresponding
+ * objects.
+ */
+static struct callback_head *do_hazptr(struct hazptr_struct *hzst)
+{
+ struct callback_head *tmp, **curr;
+ struct callback_head *todo = NULL, **todo_tail = &todo;
+
+ // Currently, the lock is unnecessary, but maybe we will have multiple
+ // work_structs sharing the same callback list in the future;
+ guard(spinlock_irqsave)(&hzst->callback_lock);
+
+ curr = &hzst->queued;
+
+ while ((tmp = *curr)) {
+ // No reader, we can free the object.
+ if (!reader_exist(&hzst->readers, (unsigned long)tmp)) {
+ // Add tmp into todo.
+ *todo_tail = tmp;
+ todo_tail = &tmp->next;
+
+ // Delete tmp from ->queued and move to the next entry.
+ *curr = tmp->next;
+ } else
+ curr = &tmp->next;
+ }
+
+ hzst->tail = curr;
+
+ // Keep checking if callback list is not empty.
+ if (hzst->queued)
+ kick_hazptr_work();
+
+ *todo_tail = NULL;
+
+ return todo;
+}
+
+static void hazptr_work_func(struct work_struct *work)
+{
+ struct hazptr_struct *hzst = container_of(work, struct hazptr_struct, work);
+ struct callback_head *todo;
+
+ // Advance callbacks from hzpcpu to hzst
+ scoped_guard(spinlock_irqsave, &hzst->callback_lock) {
+ int cpu;
+
+ hzst->scheduled = false;
+ for_each_possible_cpu(cpu) {
+ struct hazptr_percpu *pcpu = per_cpu_ptr(&hzpcpu, cpu);
+
+ guard(spinlock)(&pcpu->callback_lock);
+
+ if (pcpu->queued) {
+ *(hzst->tail) = pcpu->queued;
+ hzst->tail = pcpu->tail;
+ pcpu->queued = NULL;
+ pcpu->tail = &pcpu->queued;
+ }
+ }
+ }
+
+ // Pairs with the smp_mb() on the reader side. This guarantees that if
+ // the hazptr work picked up the callback from an updater and the
+ // updater set the global pointer to NULL before enqueue the callback,
+ // the hazptr work must observe a reader that protects the hazptr before
+ // the updater.
+ //
+ // <reader> <updater> <hazptr work>
+ // ptr = READ_ONCE(gp);
+ // WRITE_ONCE(*hazptr, ptr);
+ // smp_mb(); // => ->strong-fence
+ // tofree = gp;
+ // ptr = READ_ONCE(gp); // re-read, gp is not NULL
+ // // => ->fre
+ // WRITE_ONCE(gp, NULL);
+ // call_hazptr(gp, ...):
+ //  lock(->callback_lock);
+ //  [queued the callback]
+ //  unlock(->callback_lock);// => ->po-unlock-lock-po
+ // lock(->callback_lock);
+ // [move from hzpcpu to hzst]
+ //
+ // smp_mb(); => ->strong-fence
+ // ptr = READ_ONCE(*hazptr);
+ // // ptr == gp, otherwise => ->fre
+ //
+ // If ptr != gp, it means there exists a circle with the following
+ // memory ordering relationships:
+ // ->strong-fence ->fre ->po-unlock-lock-po ->strong-fence ->fre
+ // => (due to the definition of prop)
+ // ->strong-fence ->prop ->strong-fence ->hb ->prop
+ // => (rotate the circle)
+ // ->prop ->strong-fence ->prop ->strong-fence ->hb
+ // => (due to the definition of pb)
+ // ->pb ->pb
+ // but pb is acyclic according to LKMM, so this cannot happen.
+ smp_mb();
+ check_readers(hzst);
+
+ todo = do_hazptr(hzst);
+
+ while (todo) {
+ struct callback_head *next = todo->next;
+ void (*func)(struct callback_head *) = todo->func;
+
+ func(todo);
+
+ todo = next;
+ }
+}
+
+/*
+ * Put @head into the cleanup callback queue.
+ *
+ * @func(@head) will be called after no one is referencing the object. Caller
+ * must ensure the object has been unpublished before calling this.
+ */
+void call_hazptr(struct callback_head *head, rcu_callback_t func)
+{
+ struct hazptr_percpu *pcpu = this_cpu_ptr(&hzpcpu);
+
+ head->func = func;
+ head->next = NULL;
+
+ scoped_guard(spinlock_irqsave, &pcpu->callback_lock) {
+ *(pcpu->tail) = head;
+ pcpu->tail = &head->next;
+ }
+
+ guard(spinlock_irqsave)(&hazptr_struct.callback_lock);
+ kick_hazptr_work();
+}
+
+static int init_hazptr_struct(void)
+{
+ int cpu;
+
+ INIT_WORK(&hazptr_struct.work, hazptr_work_func);
+
+ spin_lock_init(&hazptr_struct.callback_lock);
+ hazptr_struct.queued = NULL;
+ hazptr_struct.tail = &hazptr_struct.queued;
+
+ for_each_possible_cpu(cpu) {
+ struct hazptr_percpu *pcpu = per_cpu_ptr(&hzpcpu, cpu);
+
+ spin_lock_init(&pcpu->ctx_lock);
+ INIT_LIST_HEAD(&pcpu->ctx_list);
+
+ spin_lock_init(&pcpu->callback_lock);
+ pcpu->queued = NULL;
+ pcpu->tail = &pcpu->queued;
+
+ }
+
+ init_hazptr_reader_tree(&hazptr_struct.readers);
+
+ return 0;
+}
+
+early_initcall(init_hazptr_struct);
Signature · 1 line
2.45.2
author
#4 lore raw

Re: [RFC PATCH 1/4] hazptr: Add initial implementation of hazard pointers

On Wed, Sep 18, 2024 at 11:17:37PM +0800, Alan Huang wrote:
[...]

Quoted 9 lines

include/linux/hazptr.h line 46

Quoted 6 lines
include/linux/hazptr.h new file +6 -0
+#define hazptr_tryprotect(hzp, gp, field) (typeof(gp))__hazptr_tryprotect(hzp, (void **)&(gp), offsetof(typeof(*gp), field))
+#define hazptr_protect(hzp, gp, field) ({ \
+ typeof(gp) ___p; \
+ \
+ ___p = hazptr_tryprotect(hzp, gp, field); \
+ BUG_ON(!___p); \

hazptr_tryprotect might return NULL, do you need a loop here?

Thanks for the review. It's me who didn't do a good job here on the documentation. hazptr_protect() is supposed to use for the case where readers know the gp won't change.

Regards,
Boqun

Quoted 3 lines
Quoted 3 lines

+ ___p; \

(quoted diff) +2 -0
+})
+
#5 lore raw

Re: [RFC PATCH 1/4] hazptr: Add initial implementation of hazard pointers

Am 9/19/2024 um 8:56 AM schrieb Boqun Feng:

Quoted 16 lines · Alan Huang

[...]

Quoted 9 lines

include/linux/hazptr.h line 46

Quoted 6 lines
include/linux/hazptr.h new file +6 -0
+#define hazptr_tryprotect(hzp, gp, field) (typeof(gp))__hazptr_tryprotect(hzp, (void **)&(gp), offsetof(typeof(*gp), field))
+#define hazptr_protect(hzp, gp, field) ({ \
+ typeof(gp) ___p; \
+ \
+ ___p = hazptr_tryprotect(hzp, gp, field); \
+ BUG_ON(!___p); \

hazptr_tryprotect might return NULL, do you need a loop here?

Thanks for the review. It's me who didn't do a good job here on the documentation. hazptr_protect() is supposed to use for the case where readers know the gp won't change.

Quoted 6 lines

Regards,
Boqun

Quoted 3 lines

Review

Quoted 3 lines

+ ___p; \

(quoted diff) +2 -0
+})
+

Oh, disregard my other e-mail, I hadn't seen this discussion.

Do you have any specific use case of this in mind? If you know that the pointer can't change, I would assume you can also just read the pointer normally and assign to the hazard pointer without a fence, no?

have fun, jonas

#6 lore raw

Re: [RFC PATCH 1/4] hazptr: Add initial implementation of hazard pointers

In reply to Boqun Feng
Quoted 19 lines · Boqun Feng

Hazard pointers [1] provide a way to dynamically distribute refcounting and can be used to improve the scalability of refcounting without significant space cost.

include/linux/hazptr.h new file +15 -0
+static inline void *__hazptr_tryprotect(hazptr_t *hzp,
+                                       void *const *p,
+                                       unsigned long head_offset)
+{
+       void *ptr;
+       struct callback_head *head;
+
+       ptr = READ_ONCE(*p);
+
+       if (ptr == NULL)
+               return NULL;
+
+       head = (struct callback_head *)(ptr + head_offset);
+
+       WRITE_ONCE(*hzp, head);

include/linux/hazptr.h line 74

Quoted 10 lines
include/linux/hazptr.h new file +10 -0
+       smp_mb();
+
+       ptr = READ_ONCE(*p); // read again
+
+       if (ptr + head_offset != head) { // pointer changed
+               WRITE_ONCE(*hzp, NULL);  // reset hazard pointer
+               return NULL;
+       } else
+               return ptr;
+}

I got nerdsniped by the Plumbers talk. So, about that smp_mb()...

I think you should be able to avoid the smp_mb() using relaxed atomics (on architectures that have those), at the cost of something like a cmpxchg-acquire sandwiched between a load-acquire and a relaxed load? I'm not sure how their cost compares to an smp_mb() though.

Something like this, *assuming there can only be one context at a time waiting for a given hazptr_t*:

typedef struct {
/* consists of: marker bit in least significant bit, rest is normal pointer */ atomic_long_t value;
} hazptr_t;

/* assumes that hzp is currently set to NULL (but it may contain a marker bit) */
static inline void *__hazptr_tryprotect(hazptr_t *hzp, void *const *p) {
/* note that the loads of these three operations are ordered using
acquire semantics */
void *ptr = smp_load_acquire(p);
/* set pointer while leaving marker bit intact */
unsigned long hazard_scanning =
atomic_long_fetch_or_acquire((unsigned long)ptr, &hzp->value);

  if (unlikely(hazard_scanning)) {
    BUG_ON(hazard_scanning != 1);
    /* slowpath, concurrent hazard pointer waiter */
    smp_mb();
  }
  if (READ_ONCE(*p) == ptr) { /* recheck */
    atomic_long_and(~1UL, &hzp->value);
    return NULL;

}
return ptr;
}

/* simplified for illustration, assumes there's only a single hazard pointer @hzp that could point to @ptr */
static void remove_pointer_and_wait_for_hazard(hazptr_t *hzp, void *ptr, void *const *p) {
WRITE_ONCE(*p, NULL);
smb_mb();
/* set marker bit */
atomic_long_or(1UL, &hzp->value);
while ((void*)(atomic_long_read(&hzp->value) & ~1UL) == ptr))

    wait();

/* clear marker bit */
atomic_long_and(~1UL, &hzp->value);
}

The idea would be that the possible orderings when these two functions race against each other are:

Ordering A: The atomic_long_fetch_or_acquire() in __hazptr_tryprotect() happens after the atomic_long_or(), two subcases:
Ordering A1 (slowpath): atomic_long_fetch_or_acquire() is ordered before the atomic_long_and() in remove_pointer_and_wait_for_hazard(), so the marker bit is observed set, "hazard_scanning" is true. We go on the safe slowpath which is like the original patch, so it's safe. Ordering A2 (recheck fails): atomic_long_fetch_or_acquire() is ordered after the atomic_long_and() in remove_pointer_and_wait_for_hazard(), so the subsequent READ_ONCE(*p) is also ordered after the atomic_long_and(), which is ordered after the WRITE_ONCE(*p, NULL), so the READ_ONCE(*p) recheck must see a NULL pointer and fail. Ordering B (hazard pointer visible): The atomic_long_fetch_or_acquire() in __hazptr_tryprotect() happens before the atomic_long_or(). In that case, it also happens before the atomic_long_read() in remove_pointer_and_wait_for_hazard(), so the hazard pointer will be visible to remove_pointer_and_wait_for_hazard().

But this seems pretty gnarly/complicated, so even if my 2AM reasoning ability is correct, actually implementing this might not be a good idea... and it definitely wouldn't help on X86 at all, since X86 doesn't have such nice relaxed RMW ops.

#7 lore raw

Re: [RFC PATCH 1/4] hazptr: Add initial implementation of hazard pointers

Am 9/19/2024 um 2:12 AM schrieb Jann Horn:

Quoted 33 lines · Boqun Feng
Quoted 19 lines

Hazard pointers [1] provide a way to dynamically distribute refcounting and can be used to improve the scalability of refcounting without significant space cost.

include/linux/hazptr.h new file +15 -0
+static inline void *__hazptr_tryprotect(hazptr_t *hzp,
+                                       void *const *p,
+                                       unsigned long head_offset)
+{
+       void *ptr;
+       struct callback_head *head;
+
+       ptr = READ_ONCE(*p);
+
+       if (ptr == NULL)
+               return NULL;
+
+       head = (struct callback_head *)(ptr + head_offset);
+
+       WRITE_ONCE(*hzp, head);

include/linux/hazptr.h line 74

Quoted 10 lines
include/linux/hazptr.h new file +10 -0
+       smp_mb();
+
+       ptr = READ_ONCE(*p); // read again
+
+       if (ptr + head_offset != head) { // pointer changed
+               WRITE_ONCE(*hzp, NULL);  // reset hazard pointer
+               return NULL;
+       } else
+               return ptr;
+}

I got nerdsniped by the Plumbers talk. So, about that smp_mb()...

Quoted 4 lines

I think you should be able to avoid the smp_mb() using relaxed atomics (on architectures that have those), at the cost of something like a cmpxchg-acquire sandwiched between a load-acquire and a relaxed load? I'm not sure how their cost compares to an smp_mb() though.

We have done a similar scheme before, and on some architectures (not x86) the RMW is slightly cheaper than the mb.

Your reasoning is a bit simplified because it seems to assume a stronger concept of ordering than LKMM has, but even with LKMM's ordering your code seems fine.

I feel it can even be simplified a little, the hazard bit does not seem necessary.

Assuming atomic operations for everything racy, relaxed unless stated otherwise:

(R)eader:

old = read p // I don't think this needs acq, because of address
dependencies (*)
haz ||=_acq old
if (read p != old) retry;
*old

(W)riter:

p =_??? ... // assuming we don't set it to null this needs a rel --- mb ---
haz ||= 0
while (read_acq haz == old) retry;
delete old

In order to get a use-after-free, both of the R:read p need to read before W:p = ... , so because of the W:mb, they execute before W:haz||=0 .

Also, for the use-after-free, W:read_acq haz needs to read before (the write part of) R:haz||=_acq old .

Then the W:haz ||= 0 also needs to read before (the write part of) R:haz||=_acq old because of coherence on the same location.

Since both of them are atomic RMW, the W:haz||= 0 also needs to write before (the write part of) R:haz||=_acq old , and in the absence of non-RMW writes (so assuming no thread will just store to the hazard pointer), this implies that the latter reads-from an rmw-sequence-later store than W:haz||=0 , which therefore executes before R:haz||=_acq old .

But because of the acquire barrier, R:haz||=_acq old executes before the second R:read p .

This gives a cycle
(2nd)R:read p ->xb W:haz||=0 ->xb R:haz||=_acq ->xb (2nd)R:read p

and therefore is forbidden.

Note that in this argument, the two R:read p are not necessarily reading from the same store. Because of ABA, it can happen that they read from distinct stores and see the same value.

It does require clearing hazard pointers with an RMW like atomic_and(0) (**). The combination of the two RMW (for setting & clearing the hazard pointer) might in total be slower again than an mb.

(I took the liberty to add an acquire barrier in the writer's while loop for the case where we read from the (not shown) release store of the reader that clears the hazard pointer. It's arguable whether that acq is needed since one could argue that a delete is a kind of store, in which case control dependency would handle it.)

have fun,
jonas

(*
you talk about sandwiching, and the data dependency does guarantee
some weaker form of sandwiching than the acq, but I don't think sandwiching is required at all. If you happened to be able to set the hazard pointer before reading the pointer, that would just extend the protected area, wouldn't it? )

(**
I think if you clear the pointer with a store, the hazard bit does not help. You could be overwriting the hazard bit, and the RMWs that set the hazard bit might never propagate to your CPU.

Also in your code you probably meant to clear the whole hazard pointer in the retry code of the reader, not just the hazard bit.)

#8 lore raw

Re: [RFC PATCH 1/4] hazptr: Add initial implementation of hazard pointers

Am 9/19/2024 um 10:30 PM schrieb Jonas Oberhauser:

Quoted 50 lines

Am 9/19/2024 um 2:12 AM schrieb Jann Horn:

Quoted 33 lines · Boqun Feng
Quoted 19 lines

Hazard pointers [1] provide a way to dynamically distribute refcounting and can be used to improve the scalability of refcounting without significant space cost.

include/linux/hazptr.h new file +15 -0
+static inline void *__hazptr_tryprotect(hazptr_t *hzp,
+                                       void *const *p,
+                                       unsigned long head_offset)
+{
+       void *ptr;
+       struct callback_head *head;
+
+       ptr = READ_ONCE(*p);
+
+       if (ptr == NULL)
+               return NULL;
+
+       head = (struct callback_head *)(ptr + head_offset);
+
+       WRITE_ONCE(*hzp, head);

include/linux/hazptr.h line 74

Quoted 10 lines
include/linux/hazptr.h new file +10 -0
+       smp_mb();
+
+       ptr = READ_ONCE(*p); // read again
+
+       if (ptr + head_offset != head) { // pointer changed
+               WRITE_ONCE(*hzp, NULL);  // reset hazard pointer
+               return NULL;
+       } else
+               return ptr;
+}

I got nerdsniped by the Plumbers talk. So, about that smp_mb()...

Quoted 4 lines

I think you should be able to avoid the smp_mb() using relaxed atomics (on architectures that have those), at the cost of something like a cmpxchg-acquire sandwiched between a load-acquire and a relaxed load? I'm not sure how their cost compares to an smp_mb() though.

We have done a similar scheme before, and on some architectures (not x86) the RMW is slightly cheaper than the mb.

Your reasoning is a bit simplified because it seems to assume a stronger concept of ordering than LKMM has, but even with LKMM's ordering your code seems fine.

I feel it can even be simplified a little, the hazard bit does not seem necessary.

Quoted 8 lines

Assuming atomic operations for everything racy, relaxed unless stated otherwise:

(R)eader:

   old = read p // I don't think this needs acq, because of address
dependencies (*)
   haz ||=_acq old
   if (read p != old) retry;

I realized before going to bed that I copied a subtle mistake here from Jann's code, we need an address dependency from this read, or it is not ABA safe. This can be done with the small detour that Boqun used:

head = read p // I don't think this needs acq, because of address
dependencies (*)

     haz ||=_acq head
     old = read p // again
     if (head != old) retry;
     barrier(); // ensure compiler does not use its knowledge that head 

== old to do *head instead!
*old // definitely use the second read pointer so hardware can't
speculatively dereference this before the second read!

Have a good time,
jonas

reviewer
#9 lore raw

Re: [RFC PATCH 1/4] hazptr: Add initial implementation of hazard pointers

In reply to Boqun Feng
Quoted 26 lines · Boqun Feng
kernel/hazptr.c new file +26 -0
+static void hazptr_context_snap_readers_locked(struct hazptr_reader_tree *tree,
+                                              struct hazptr_context *hzcp)
+{
+       lockdep_assert_held(hzcp->lock);
+
+       for (int i = 0; i < HAZPTR_SLOT_PER_CTX; i++) {
+               /*
+                * Pairs with smp_store_release() in hazptr_{clear,free}().
+                *
+                * Ensure
+                *
+                * <reader>             <updater>
+                *
+                * [access protected pointers]
+                * hazptr_clear();
+                *   smp_store_release()
+                *                      // in reader scan.
+                *                      smp_load_acquire(); // is null or unused.
+                *                      [run callbacks] // all accesses from
+                *                                      // reader must be
+                *                                      // observed.
+                */
+               hazptr_t val = smp_load_acquire(&hzcp->slots[i]);
+
+               if (!is_null_or_unused(val)) {
+                       struct hazptr_slot_snap *snap = &hzcp->snaps[i];

kernel/hazptr.c line 158

Quoted 10 lines
kernel/hazptr.c new file +10 -0
+
+                       // Already in the tree, need to remove first.
+                       if (!is_null_or_unused(snap->slot)) {
+                               reader_del(tree, snap);
+                       }
+                       snap->slot = val;
+                       reader_add(tree, snap);
+               }
+       }
+}

Hello

I'm curious about whether there are any possible memory leaks here.

It seems that call_hazptr() never frees the memory until the slot is set to another valid value.

In the code here, the snap is not deleted when hzcp->snaps[i] is null/unused and snap->slot is not which I think it should be.

And it can cause unneeded deletion and addition of the snap if the slot value is unchanged.

I'm not so sure...

Thanks
Lai

author
#10 lore raw

Re: [RFC PATCH 1/4] hazptr: Add initial implementation of hazard pointers

Quoted 43 lines · Lai Jiangshan
Quoted 26 lines · Boqun Feng
kernel/hazptr.c new file +26 -0
+static void hazptr_context_snap_readers_locked(struct hazptr_reader_tree *tree,
+                                              struct hazptr_context *hzcp)
+{
+       lockdep_assert_held(hzcp->lock);
+
+       for (int i = 0; i < HAZPTR_SLOT_PER_CTX; i++) {
+               /*
+                * Pairs with smp_store_release() in hazptr_{clear,free}().
+                *
+                * Ensure
+                *
+                * <reader>             <updater>
+                *
+                * [access protected pointers]
+                * hazptr_clear();
+                *   smp_store_release()
+                *                      // in reader scan.
+                *                      smp_load_acquire(); // is null or unused.
+                *                      [run callbacks] // all accesses from
+                *                                      // reader must be
+                *                                      // observed.
+                */
+               hazptr_t val = smp_load_acquire(&hzcp->slots[i]);
+
+               if (!is_null_or_unused(val)) {
+                       struct hazptr_slot_snap *snap = &hzcp->snaps[i];

kernel/hazptr.c line 158

Quoted 10 lines
kernel/hazptr.c new file +10 -0
+
+                       // Already in the tree, need to remove first.
+                       if (!is_null_or_unused(snap->slot)) {
+                               reader_del(tree, snap);
+                       }
+                       snap->slot = val;
+                       reader_add(tree, snap);
+               }
+       }
+}

Hello

I'm curious about whether there are any possible memory leaks here.

Quoted 9 lines

It seems that call_hazptr() never frees the memory until the slot is set to another valid value.

In the code here, the snap is not deleted when hzcp->snaps[i] is null/unused and snap->slot is not which I think it should be.

And it can cause unneeded deletion and addition of the snap if the slot value is unchanged.

I think you're right. (Although the node will be eventually deleted at cleanup_hazptr_context(), however there could be a long-live hazptr_context). It should be:

		hazptr_t val = smp_load_acquire(&hzcp->slots[i]);
		struct hazptr_slot_snap *snap = &hzcp->snaps[i];

		if (val != snap->slot) { // val changed, need to update the tree node.
			// Already in the tree, need to remove first.
			if (!is_null_or_unused(snap->slot)) {
				reader_del(tree, snap);
			}

			// use the latest snapshot.
			snap->slot = val;

			// Add it into tree if there is a reader
			if (!is_null_or_unused(val))
				reader_add(tree, snap);
		}

Regards,
Boqun

Quoted 4 lines

I'm not so sure...

Thanks
Lai

#11 lore raw

Re: [RFC PATCH 1/4] hazptr: Add initial implementation of hazard pointers

2024年9月19日 15:10,Boqun Feng <[email protected]> wrote:

Quoted 68 lines · Lai Jiangshan
Quoted 43 lines · Boqun Feng
Quoted 27 lines
kernel/hazptr.c new file +26 -0
+static void hazptr_context_snap_readers_locked(struct hazptr_reader_tree *tree,
+                                              struct hazptr_context *hzcp)
+{
+       lockdep_assert_held(hzcp->lock);
+
+       for (int i = 0; i < HAZPTR_SLOT_PER_CTX; i++) {
+               /*
+                * Pairs with smp_store_release() in hazptr_{clear,free}().
+                *
+                * Ensure
+                *
+                * <reader>             <updater>
+                *
+                * [access protected pointers]
+                * hazptr_clear();
+                *   smp_store_release()
+                *                      // in reader scan.
+                *                      smp_load_acquire(); // is null or unused.
+                *                      [run callbacks] // all accesses from
+                *                                      // reader must be
+                *                                      // observed.
+                */
+               hazptr_t val = smp_load_acquire(&hzcp->slots[i]);
+
+               if (!is_null_or_unused(val)) {
+                       struct hazptr_slot_snap *snap = &hzcp->snaps[i];

kernel/hazptr.c line 158

Quoted 10 lines
kernel/hazptr.c new file +10 -0
+
+                       // Already in the tree, need to remove first.
+                       if (!is_null_or_unused(snap->slot)) {
+                               reader_del(tree, snap);
+                       }
+                       snap->slot = val;
+                       reader_add(tree, snap);
+               }
+       }
+}

Hello

I'm curious about whether there are any possible memory leaks here.

Quoted 9 lines

It seems that call_hazptr() never frees the memory until the slot is set to another valid value.

In the code here, the snap is not deleted when hzcp->snaps[i] is null/unused and snap->slot is not which I think it should be.

And it can cause unneeded deletion and addition of the snap if the slot value is unchanged.

I think you're right. (Although the node will be eventually deleted at cleanup_hazptr_context(), however there could be a long-live hazptr_context). It should be:

hazptr_t val = smp_load_acquire(&hzcp->slots[i]);
struct hazptr_slot_snap *snap = &hzcp->snaps[i];

if (val != snap->slot) { // val changed, need to update the tree node. // Already in the tree, need to remove first.
if (!is_null_or_unused(snap->slot)) {
reader_del(tree, snap);
}

Quoted 7 lines

// use the latest snapshot.
snap->slot = val;

// Add it into tree if there is a reader
if (!is_null_or_unused(val))
reader_add(tree, snap);
}

With this changed, and force users call hazptr_clear() like rcu_read_unlock(), we could remove the reader_del() in cleanup_hazptr_context(), then remove the tree->lock?

Quoted 8 lines

Regards,
Boqun

Quoted 4 lines

I'm not so sure...

Thanks
Lai

#12 lore raw

Re: [RFC PATCH 1/4] hazptr: Add initial implementation of hazard pointers

In reply to Boqun Feng

2024年9月19日 15:10,Boqun Feng <[email protected]> wrote:

Quoted 68 lines · Lai Jiangshan
Quoted 43 lines · Boqun Feng
Quoted 27 lines
kernel/hazptr.c new file +26 -0
+static void hazptr_context_snap_readers_locked(struct hazptr_reader_tree *tree,
+                                              struct hazptr_context *hzcp)
+{
+       lockdep_assert_held(hzcp->lock);
+
+       for (int i = 0; i < HAZPTR_SLOT_PER_CTX; i++) {
+               /*
+                * Pairs with smp_store_release() in hazptr_{clear,free}().
+                *
+                * Ensure
+                *
+                * <reader>             <updater>
+                *
+                * [access protected pointers]
+                * hazptr_clear();
+                *   smp_store_release()
+                *                      // in reader scan.
+                *                      smp_load_acquire(); // is null or unused.
+                *                      [run callbacks] // all accesses from
+                *                                      // reader must be
+                *                                      // observed.
+                */
+               hazptr_t val = smp_load_acquire(&hzcp->slots[i]);
+
+               if (!is_null_or_unused(val)) {
+                       struct hazptr_slot_snap *snap = &hzcp->snaps[i];

kernel/hazptr.c line 158

Quoted 10 lines
kernel/hazptr.c new file +10 -0
+
+                       // Already in the tree, need to remove first.
+                       if (!is_null_or_unused(snap->slot)) {
+                               reader_del(tree, snap);
+                       }
+                       snap->slot = val;
+                       reader_add(tree, snap);
+               }
+       }
+}

Hello

I'm curious about whether there are any possible memory leaks here.

Quoted 9 lines

It seems that call_hazptr() never frees the memory until the slot is set to another valid value.

In the code here, the snap is not deleted when hzcp->snaps[i] is null/unused and snap->slot is not which I think it should be.

And it can cause unneeded deletion and addition of the snap if the slot value is unchanged.

I think you're right. (Although the node will be eventually deleted at cleanup_hazptr_context(), however there could be a long-live hazptr_context). It should be:

hazptr_t val = smp_load_acquire(&hzcp->slots[i]);
struct hazptr_slot_snap *snap = &hzcp->snaps[i];

if (val != snap->slot) { // val changed, need to update the tree node. // Already in the tree, need to remove first.
if (!is_null_or_unused(snap->slot)) {
reader_del(tree, snap);
}

Quoted 7 lines

// use the latest snapshot.
snap->slot = val;

// Add it into tree if there is a reader
if (!is_null_or_unused(val))
reader_add(tree, snap);
}

It seems like that two different hazptr_context can’t be used to protect the same pointer?

Otherwise the following can happen?

thread1 thread2 thread3(worker) thread4
hazptr_tryprotect(hzp1, ptr1) hazptr_tryprotect(hzp2, ptr1)
add ptr1 to tree
hazptr_clear(hzp1)
hazptr_tryprotect(hzp1, ptr2)
delete ptr1 from tree unpub ptr1
call_hazptr(ptr1)
oops: invoke ptr1's callback
Or am I missing something?

Quoted 8 lines

Regards,
Boqun

Quoted 4 lines

I'm not so sure...

Thanks
Lai

author
#13 lore raw

Re: [RFC PATCH 1/4] hazptr: Add initial implementation of hazard pointers

On Thu, Sep 19, 2024 at 09:57:12PM +0800, Alan Huang wrote:
[...]

Quoted 22 lines
Quoted 14 lines

I think you're right. (Although the node will be eventually deleted at cleanup_hazptr_context(), however there could be a long-live hazptr_context). It should be:

hazptr_t val = smp_load_acquire(&hzcp->slots[i]);
struct hazptr_slot_snap *snap = &hzcp->snaps[i];

if (val != snap->slot) { // val changed, need to update the tree node. // Already in the tree, need to remove first.
if (!is_null_or_unused(snap->slot)) {
reader_del(tree, snap);
}

Quoted 7 lines

// use the latest snapshot.
snap->slot = val;

// Add it into tree if there is a reader
if (!is_null_or_unused(val))
reader_add(tree, snap);
}

Quoted 7 lines

It seems like that two different hazptr_context can’t be used to protect the same pointer?

Otherwise the following can happen?

thread1 thread2 thread3(worker) thread4
hazptr_tryprotect(hzp1, ptr1) hazptr_tryprotect(hzp2, ptr1)
add ptr1 to tree

Note that we have snapshot rb_node for each hazard pointer slot, so here thread3 actually would add two rb_nodes with ->slot == ptr1 here.

Quoted 3 lines

hazptr_clear(hzp1)
hazptr_tryprotect(hzp1, ptr2)
delete ptr1 from tree unpub ptr1

Therefore, there is still one rb_node with ->slot == ptr1 in the tree after the deletion, so updaters won't invoke ptr1's callback.

Regards,
Boqun

Quoted 14 lines

call_hazptr(ptr1)
oops: invoke ptr1's callback
Or am I missing something?

Quoted 8 lines

Regards,
Boqun

Quoted 4 lines

I'm not so sure...

Thanks
Lai

#14 lore raw

Re: [RFC PATCH 1/4] hazptr: Add initial implementation of hazard pointers

2024年9月20日 02:58,Boqun Feng <[email protected]> wrote:

Quoted 27 lines · Alan Huang

[...]

Quoted 24 lines
Quoted 14 lines

I think you're right. (Although the node will be eventually deleted at cleanup_hazptr_context(), however there could be a long-live hazptr_context). It should be:

hazptr_t val = smp_load_acquire(&hzcp->slots[i]);
struct hazptr_slot_snap *snap = &hzcp->snaps[i];

if (val != snap->slot) { // val changed, need to update the tree node. // Already in the tree, need to remove first.
if (!is_null_or_unused(snap->slot)) {
reader_del(tree, snap);
}

Quoted 7 lines

// use the latest snapshot.
snap->slot = val;

// Add it into tree if there is a reader
if (!is_null_or_unused(val))
reader_add(tree, snap);
}

It seems like that two different hazptr_context can’t be used to protect the same pointer?

Quoted 8 lines
Quoted 5 lines

Otherwise the following can happen?

thread1 thread2 thread3(worker) thread4
hazptr_tryprotect(hzp1, ptr1) hazptr_tryprotect(hzp2, ptr1)
add ptr1 to tree

Note that we have snapshot rb_node for each hazard pointer slot, so here thread3 actually would add two rb_nodes with ->slot == ptr1 here.

Ok, good to know the rbtree can have multiple nodes with the same key.

Thanks for the explanation!

Quoted 23 lines
Quoted 4 lines

hazptr_clear(hzp1)
hazptr_tryprotect(hzp1, ptr2)
delete ptr1 from tree unpub ptr1

Therefore, there is still one rb_node with ->slot == ptr1 in the tree after the deletion, so updaters won't invoke ptr1's callback.

Regards,
Boqun

Quoted 12 lines

call_hazptr(ptr1)
oops: invoke ptr1's callback
Or am I missing something?

Quoted 8 lines

Regards,
Boqun

Quoted 4 lines

I'm not so sure...

Thanks
Lai

#15 lore raw

Re: [RFC PATCH 1/4] hazptr: Add initial implementation of hazard pointers

In reply to Boqun Feng

2024年9月19日 15:10,Boqun Feng <[email protected]> wrote:

Quoted 68 lines · Lai Jiangshan
Quoted 43 lines · Boqun Feng
Quoted 27 lines
kernel/hazptr.c new file +26 -0
+static void hazptr_context_snap_readers_locked(struct hazptr_reader_tree *tree,
+                                              struct hazptr_context *hzcp)
+{
+       lockdep_assert_held(hzcp->lock);
+
+       for (int i = 0; i < HAZPTR_SLOT_PER_CTX; i++) {
+               /*
+                * Pairs with smp_store_release() in hazptr_{clear,free}().
+                *
+                * Ensure
+                *
+                * <reader>             <updater>
+                *
+                * [access protected pointers]
+                * hazptr_clear();
+                *   smp_store_release()
+                *                      // in reader scan.
+                *                      smp_load_acquire(); // is null or unused.
+                *                      [run callbacks] // all accesses from
+                *                                      // reader must be
+                *                                      // observed.
+                */
+               hazptr_t val = smp_load_acquire(&hzcp->slots[i]);
+
+               if (!is_null_or_unused(val)) {
+                       struct hazptr_slot_snap *snap = &hzcp->snaps[i];

kernel/hazptr.c line 158

Quoted 10 lines
kernel/hazptr.c new file +10 -0
+
+                       // Already in the tree, need to remove first.
+                       if (!is_null_or_unused(snap->slot)) {
+                               reader_del(tree, snap);
+                       }
+                       snap->slot = val;
+                       reader_add(tree, snap);
+               }
+       }
+}

Hello

I'm curious about whether there are any possible memory leaks here.

Quoted 9 lines

It seems that call_hazptr() never frees the memory until the slot is set to another valid value.

In the code here, the snap is not deleted when hzcp->snaps[i] is null/unused and snap->slot is not which I think it should be.

And it can cause unneeded deletion and addition of the snap if the slot value is unchanged.

I think you're right. (Although the node will be eventually deleted at cleanup_hazptr_context(), however there could be a long-live hazptr_context). It should be:

hazptr_t val = smp_load_acquire(&hzcp->slots[i]);
struct hazptr_slot_snap *snap = &hzcp->snaps[i];

if (val != snap->slot) { // val changed, need to update the tree node. // Already in the tree, need to remove first.
if (!is_null_or_unused(snap->slot)) {
reader_del(tree, snap);
}

Quoted 7 lines

// use the latest snapshot.
snap->slot = val;

// Add it into tree if there is a reader
if (!is_null_or_unused(val))
reader_add(tree, snap);
}

Even using the same context, if two slots are used to protect the same pointer, let it be ptr1, then if the second slot is reused for ptr2, ptr1’s callback will be invoked even the first slot still has the ptr1.

The original patch also has this problem.

Quoted 8 lines

Regards,
Boqun

Quoted 4 lines

I'm not so sure...

Thanks
Lai

#16 lore raw

Re: [RFC PATCH 1/4] hazptr: Add initial implementation of hazard pointers

In reply to Boqun Feng

Am 9/17/2024 um 4:33 PM schrieb Boqun Feng:

include/linux/hazptr.h line 48

Quoted 7 lines
include/linux/hazptr.h new file +7 -0
+#define hazptr_protect(hzp, gp, field) ({				\
+	typeof(gp) ___p;						\
+									\
+	___p = hazptr_tryprotect(hzp, gp, field);			\
+	BUG_ON(!___p);							\
+	___p;								\
+})

Hi Boqun, why crash instead of retry?

jonas

#17 lore raw

Re: [RFC PATCH 1/4] hazptr: Add initial implementation of hazard pointers

In reply to Boqun Feng

Am 9/17/2024 um 4:33 PM schrieb Boqun Feng:

Quoted 15 lines
include/linux/hazptr.h new file +15 -0
+static inline void *__hazptr_tryprotect(hazptr_t *hzp,
+					void *const *p,
+					unsigned long head_offset)
+{
+	void *ptr;
+	struct callback_head *head;
+
+	ptr = READ_ONCE(*p);
+
+	if (ptr == NULL)
+		return NULL;
+
+	head = (struct callback_head *)(ptr + head_offset);
+
+	WRITE_ONCE(*hzp, head);

include/linux/hazptr.h line 74

Quoted 10 lines
include/linux/hazptr.h new file +10 -0
+	smp_mb();
+
+	ptr = READ_ONCE(*p); // read again
+
+	if (ptr + head_offset != head) { // pointer changed
+		WRITE_ONCE(*hzp, NULL);  // reset hazard pointer
+		return NULL;
+	} else
+		return ptr;
+}

There is a subtle potential for ABA issues here.

If the compiler replaces 'return ptr;' with 'return head - head_offset;', then you do not have an address dependency from the second read.

In this case, in ABA, the first read can read from a stale store, then the second read reads the same value from a newer store but only establishes control-dependency based synchronization with that store; any reads from *ptr could be speculatively executed before doing the second ptr = READ_ONCE(*p).

Therefore you could read the object state before it is properly reinitialized by the second store.

I'm not sure what the most efficient fix is or if you just want to gamble that "the compiler will never do that". I guess either READ_ONCE(ptr) or a compiler barrier before return ptr might do it?

Have fun,
jonas

author
#18 lore raw

Re: [RFC PATCH 1/4] hazptr: Add initial implementation of hazard pointers

Hi Jonas,

Quoted 34 lines · Jonas Oberhauser

Am 9/17/2024 um 4:33 PM schrieb Boqun Feng:

Quoted 15 lines
include/linux/hazptr.h new file +15 -0
+static inline void *__hazptr_tryprotect(hazptr_t *hzp,
+					void *const *p,
+					unsigned long head_offset)
+{
+	void *ptr;
+	struct callback_head *head;
+
+	ptr = READ_ONCE(*p);
+
+	if (ptr == NULL)
+		return NULL;
+
+	head = (struct callback_head *)(ptr + head_offset);
+
+	WRITE_ONCE(*hzp, head);

include/linux/hazptr.h line 74

Quoted 10 lines
include/linux/hazptr.h new file +10 -0
+	smp_mb();
+
+	ptr = READ_ONCE(*p); // read again
+
+	if (ptr + head_offset != head) { // pointer changed
+		WRITE_ONCE(*hzp, NULL);  // reset hazard pointer
+		return NULL;
+	} else
+		return ptr;
+}

There is a subtle potential for ABA issues here.

If the compiler replaces 'return ptr;' with 'return head - head_offset;', then you do not have an address dependency from the second read.

Quoted 9 lines

In this case, in ABA, the first read can read from a stale store, then the second read reads the same value from a newer store but only establishes control-dependency based synchronization with that store; any reads from *ptr could be speculatively executed before doing the second ptr = READ_ONCE(*p).

Therefore you could read the object state before it is properly reinitialized by the second store.

Thanks for taking a look, and nice find!

Quoted 5 lines

I'm not sure what the most efficient fix is or if you just want to gamble that "the compiler will never do that".
I guess either READ_ONCE(ptr) or a compiler barrier before return ptr might do it?

I think the root cause of this is that compiler can replace 'ptr' with 'head - head_offset' based on pointer value comparison. A fix would be converting pointer to unsigned long and doing the comparison:

	if ((unsigned long)ptr + head_offset != (unsigned long)head) {
		WRITE_ONCE(*hzp, NULL);
		return NULL;
	} else
		return ptr;

because of the conversion, compilers lose the information of pointer equality, therefore cannot replace 'ptr' with 'head - head_offset'. Of course, if we are really worried about compilers being too "smart", we can always do the comparison in asm code, then compilers don't know anything of the equality between 'ptr' and 'head - head_offset'.

Regards,
boqun

Quoted 3 lines

Have fun,
jonas

#19 lore raw

Re: [RFC PATCH 1/4] hazptr: Add initial implementation of hazard pointers

Am 9/25/2024 um 12:02 PM schrieb Boqun Feng:

Quoted 4 lines

Hi Jonas,

Of
course, if we are really worried about compilers being too "smart"

Ah, I see you know me better and better...

Quoted 2 lines

we can always do the comparison in asm code, then compilers don't know anything of the equality between 'ptr' and 'head - head_offset'.

Yes, but then a simple compiler barrier between the comparison and returning ptr would also do the trick, right? And maybe easier on the eyes.

Have fun,
jonas

author
#20 lore raw

Re: [RFC PATCH 1/4] hazptr: Add initial implementation of hazard pointers

Quoted 8 lines · Jonas Oberhauser

Am 9/25/2024 um 12:02 PM schrieb Boqun Feng:

Quoted 4 lines

Hi Jonas,

Of
course, if we are really worried about compilers being too "smart"

Quoted 7 lines

Ah, I see you know me better and better...

Quoted 2 lines

we can always do the comparison in asm code, then compilers don't know anything of the equality between 'ptr' and 'head - head_offset'.

Yes, but then a simple compiler barrier between the comparison and returning ptr would also do the trick, right? And maybe easier on the eyes.

The thing about putting a compiler barrier is that it will prevent all compiler reorderings, and some of the reordering may contribute to better codegen. (I know in this case, we have a smp_mb(), but still compilers can move unrelated code upto the second load for optimization purpose). Asm comparison is cheaper in this way. But TBH, compilers should provide a way to compare pointer values without using the result for pointer equality proof, if "convert to unsigned long" doesn't work, some other ways should work.

Regards,
Boqun

Quoted 4 lines

Have fun,
jonas

#21 lore raw

Re: [RFC PATCH 1/4] hazptr: Add initial implementation of hazard pointers

Quoted 17 lines · Boqun Feng
Quoted 8 lines · Jonas Oberhauser

Am 9/25/2024 um 12:02 PM schrieb Boqun Feng:

Quoted 4 lines

Hi Jonas,

Of
course, if we are really worried about compilers being too "smart"

Quoted 7 lines

Ah, I see you know me better and better...

Quoted 2 lines

we can always do the comparison in asm code, then compilers don't know anything of the equality between 'ptr' and 'head - head_offset'.

Yes, but then a simple compiler barrier between the comparison and returning ptr would also do the trick, right? And maybe easier on the eyes.

Quoted 9 lines

The thing about putting a compiler barrier is that it will prevent all compiler reorderings, and some of the reordering may contribute to better codegen. (I know in this case, we have a smp_mb(), but still compilers can move unrelated code upto the second load for optimization purpose). Asm comparison is cheaper in this way. But TBH, compilers should provide a way to compare pointer values without using the result for pointer equality proof, if "convert to unsigned long" doesn't work, some other ways should work.

Based on Documentation/RCU/rcu_dereference.rst :

- Be very careful about comparing pointers obtained from
rcu_dereference() against non-NULL values. As Linus Torvalds explained, if the two pointers are equal, the compiler could substitute the pointer you are comparing against for the pointer obtained from rcu_dereference(). For example::

p = rcu_dereference(gp);
if (p == &default_struct)
do_default(p->a);

Because the compiler now knows that the value of "p" is exactly the address of the variable "default_struct", it is free to transform this code into the following::

p = rcu_dereference(gp);
if (p == &default_struct)
do_default(default_struct.a);

On ARM and Power hardware, the load from "default_struct.a" can now be speculated, such that it might happen before the rcu_dereference(). This could result in bugs due to misordering.

So I am not only concerned about compiler proofs here, as it appears that the speculation done by the CPU can also cause issues on some architectures.

Thanks,

Mathieu

Quoted 7 lines

Regards,
Boqun

Quoted 4 lines

Have fun,
jonas

Signature · 3 lines
Mathieu Desnoyers
EfficiOS Inc.
https://www.efficios.com
author
#22 lore raw

Re: [RFC PATCH 1/4] hazptr: Add initial implementation of hazard pointers

Quoted 48 lines · Mathieu Desnoyers
Quoted 17 lines · Boqun Feng
Quoted 8 lines · Jonas Oberhauser

Am 9/25/2024 um 12:02 PM schrieb Boqun Feng:

Quoted 4 lines

Hi Jonas,

Of
course, if we are really worried about compilers being too "smart"

Quoted 7 lines

Ah, I see you know me better and better...

Quoted 2 lines

we can always do the comparison in asm code, then compilers don't know anything of the equality between 'ptr' and 'head - head_offset'.

Yes, but then a simple compiler barrier between the comparison and returning ptr would also do the trick, right? And maybe easier on the eyes.

Quoted 9 lines

The thing about putting a compiler barrier is that it will prevent all compiler reorderings, and some of the reordering may contribute to better codegen. (I know in this case, we have a smp_mb(), but still compilers can move unrelated code upto the second load for optimization purpose). Asm comparison is cheaper in this way. But TBH, compilers should provide a way to compare pointer values without using the result for pointer equality proof, if "convert to unsigned long" doesn't work, some other ways should work.

Based on Documentation/RCU/rcu_dereference.rst :

- Be very careful about comparing pointers obtained from
rcu_dereference() against non-NULL values. As Linus Torvalds explained, if the two pointers are equal, the compiler could substitute the pointer you are comparing against for the pointer obtained from rcu_dereference(). For example::

p = rcu_dereference(gp);
if (p == &default_struct)
do_default(p->a);

Because the compiler now knows that the value of "p" is exactly the address of the variable "default_struct", it is free to transform this code into the following::

p = rcu_dereference(gp);
if (p == &default_struct)
do_default(default_struct.a);

Quoted 8 lines

On ARM and Power hardware, the load from "default_struct.a" can now be speculated, such that it might happen before the rcu_dereference(). This could result in bugs due to misordering.

So I am not only concerned about compiler proofs here, as it appears that the speculation done by the CPU can also cause issues on some architectures.

Note that the issue is caused by compiler replacing one pointer with the other, CPU speculation won't cause the issue solely, because all architectures Linux supports honor address dependencies (except for Alpha, but on Alpha, READ_ONCE() has a smp_mb() after the load). That
is: if the compiler generates code as the code is written, there should be no problem.

Regards,
Boqun

Quoted 17 lines

Thanks,

Mathieu

Quoted 7 lines

Regards,
Boqun

Quoted 4 lines

Have fun,
jonas

Signature · 3 lines
Mathieu Desnoyers
EfficiOS Inc.
https://www.efficios.com
#23 lore raw

Re: [RFC PATCH 1/4] hazptr: Add initial implementation of hazard pointers

Quoted 58 lines · Boqun Feng
Quoted 48 lines · Mathieu Desnoyers
Quoted 17 lines · Boqun Feng
Quoted 8 lines · Jonas Oberhauser

Am 9/25/2024 um 12:02 PM schrieb Boqun Feng:

Quoted 4 lines

Hi Jonas,

Of
course, if we are really worried about compilers being too "smart"

Quoted 7 lines

Ah, I see you know me better and better...

Quoted 2 lines

we can always do the comparison in asm code, then compilers don't know anything of the equality between 'ptr' and 'head - head_offset'.

Yes, but then a simple compiler barrier between the comparison and returning ptr would also do the trick, right? And maybe easier on the eyes.

Quoted 9 lines

The thing about putting a compiler barrier is that it will prevent all compiler reorderings, and some of the reordering may contribute to better codegen. (I know in this case, we have a smp_mb(), but still compilers can move unrelated code upto the second load for optimization purpose). Asm comparison is cheaper in this way. But TBH, compilers should provide a way to compare pointer values without using the result for pointer equality proof, if "convert to unsigned long" doesn't work, some other ways should work.

Based on Documentation/RCU/rcu_dereference.rst :

- Be very careful about comparing pointers obtained from
rcu_dereference() against non-NULL values. As Linus Torvalds explained, if the two pointers are equal, the compiler could substitute the pointer you are comparing against for the pointer obtained from rcu_dereference(). For example::

p = rcu_dereference(gp);
if (p == &default_struct)
do_default(p->a);

Because the compiler now knows that the value of "p" is exactly the address of the variable "default_struct", it is free to transform this code into the following::

p = rcu_dereference(gp);
if (p == &default_struct)
do_default(default_struct.a);

Quoted 8 lines

On ARM and Power hardware, the load from "default_struct.a" can now be speculated, such that it might happen before the rcu_dereference(). This could result in bugs due to misordering.

So I am not only concerned about compiler proofs here, as it appears that the speculation done by the CPU can also cause issues on some architectures.

Quoted 6 lines

Note that the issue is caused by compiler replacing one pointer with the other, CPU speculation won't cause the issue solely, because all architectures Linux supports honor address dependencies (except for Alpha, but on Alpha, READ_ONCE() has a smp_mb() after the load). That
is: if the compiler generates code as the code is written, there should be no problem.

I am starting to wonder if it would not be more robust to just bite the bullet and add the inline asm helpers to do the pointer comparison outside of the compiler knowledge for each architecture. This should work fine in the short term, until compilers eventually give us a "compare pointers without allowing the compiler to infer anything about pointer equality".

Like so:

#include <stdio.h>

#define __str_1(x) #x
#define __str(x) __str_1(x)

/* x86-64 */

#define bne_ptr(_a, _b, _label) \
    asm goto ( \
        "cmpq %[a], %[b]\n\t" \
        "jne %l[" __str(_label) "]\n\t" \
        : : [a] "r" (_a), [b] "r" (_b) \
        : : _label)

int x;

int v[2];

int main(void)

{
    bne_ptr(v, v + 1, label_same);
    x = 1;
label_same:
    printf("%d\n", x);
    return 0;
}
Quoted 21 lines

Regards,
Boqun

Quoted 17 lines

Thanks,

Mathieu

Quoted 7 lines

Regards,
Boqun

Quoted 4 lines

Have fun,
jonas

Signature · 3 lines
Mathieu Desnoyers
EfficiOS Inc.
https://www.efficios.com
Signature · 3 lines
Mathieu Desnoyers
EfficiOS Inc.
https://www.efficios.com
#24 lore raw

Re: [RFC PATCH 1/4] hazptr: Add initial implementation of hazard pointers

On 2024-09-25 14:47, Mathieu Desnoyers wrote:
[...]

Quoted 17 lines

Like so:

#include <stdio.h>

#define __str_1(x)  #x
#define __str(x)    __str_1(x)

/* x86-64 */
#define bne_ptr(_a, _b, _label) \
    asm goto ( \
        "cmpq %[a], %[b]\n\t" \
        "jne %l[" __str(_label) "]\n\t" \
        : : [a] "r" (_a), [b] "r" (_b) \
        : : _label)

int x;

Quoted 7 lines

int v[2];

int main(void)
{
    bne_ptr(v, v + 1, label_same);
    x = 1;
label_same:

Note that this label should probably be called "label_ne". I flipped the macro logic without changing the labels.

Thanks,

Mathieu

Quoted 27 lines

    printf("%d\n", x);
    return 0;
}

Quoted 21 lines

Regards,
Boqun

Quoted 17 lines

Thanks,

Mathieu

Quoted 7 lines

Regards,
Boqun

Quoted 4 lines

Have fun,
     jonas

Signature · 3 lines
Mathieu Desnoyers
EfficiOS Inc.
https://www.efficios.com
Signature · 3 lines
Mathieu Desnoyers
EfficiOS Inc.
https://www.efficios.com
#25 lore raw

Re: [RFC PATCH 1/4] hazptr: Add initial implementation of hazard pointers

On 2024-09-25 15:10, Mathieu Desnoyers wrote:
[...]

Cleaner without goto in the user code:

#include <stdio.h>
#include <stdbool.h>

static inline
bool same_ptr(void *a, void *b)

{
    asm goto (
        "cmpq %[a], %[b]\n\t"
        "jne %l[ne]\n\t"
        : : [a] "r" (a), [b] "r" (b)
        : : ne);
    return true;
ne:
    return false;
}

int x;

int v[2];

int main(void)

{
    if (same_ptr(v, v + 1))
        x = 1;
    printf("%d\n", x);
    return 0;
}
Signature · 3 lines
Mathieu Desnoyers
EfficiOS Inc.
https://www.efficios.com
#26 lore raw

Re: [RFC PATCH 1/4] hazptr: Add initial implementation of hazard pointers

On 2024-09-25 15:20, Mathieu Desnoyers wrote:
[...]

Quoted 4 lines

static inline
bool same_ptr(void *a, void *b)
{
    asm goto (

Quoted 8 lines

        "cmpq %[a], %[b]\n\t"
        "jne %l[ne]\n\t"
        : : [a] "r" (a), [b] "r" (b)
        : : ne);
    return true;
ne:
    return false;
}

Based on the information provided in this email thread, it appears the only concern when it comes to comparing a pointer loaded by rcu_dereference() with another pointer is the possibility of compiler optimizations.

In the specific case of hazard pointer hpref_hp_get(), this function does both loads which are then compared with one another. Therefore, it is not possible for the user to provide a comparison value known at compile-time, except in the unlikely scenario where the hazard pointer would be const, which does not really make much sense.

Therefore, just using rcu_dereference() for the second load should be fine.

Thanks,

Mathieu

Signature · 3 lines
Mathieu Desnoyers
EfficiOS Inc.
https://www.efficios.com
#27 lore raw

Re: [RFC PATCH 1/4] hazptr: Add initial implementation of hazard pointers

Am 9/26/2024 um 8:16 AM schrieb Mathieu Desnoyers:

Quoted 27 lines · Mathieu Desnoyers

[...]

Quoted 4 lines

static inline
bool same_ptr(void *a, void *b)
{
     asm goto (

Quoted 8 lines

         "cmpq %[a], %[b]\n\t"
         "jne %l[ne]\n\t"
         : : [a] "r" (a), [b] "r" (b)
         : : ne);
     return true;
ne:
     return false;
}

Based on the information provided in this email thread, it appears the only concern when it comes to comparing a pointer loaded by rcu_dereference() with another pointer is the possibility of compiler optimizations.

In the specific case of hazard pointer hpref_hp_get(), this function does both loads which are then compared with one another. Therefore, it is not possible for the user to provide a comparison value known at compile-time, except in the unlikely scenario where the hazard pointer would be const, which does not really make much sense.

Quoted 7 lines

Therefore, just using rcu_dereference() for the second load should be fine.

Thanks,

Mathieu

No, the issue introduced by the compiler optimization (or by your original patch) is that the CPU can speculatively load from the first pointer as soon as it has completeled the load of that poitner:

node = ...
// t's value can be computed here, since the value of node is known
...
node2 = ...
if (node == node2) // just a control dependency, doesn't prevent speculatively loading node
t = *node

if we can force the compiler's hand, it will generate this code which provides the necessary ordering at hardware level:

node = ...
// t can't be computed here since the value of node2 is not known here
...
node2 = ...
// t can be computed here
if (node == node2)
t = *node2

Kind regards,

jonas

#28 lore raw

Re: [RFC PATCH 1/4] hazptr: Add initial implementation of hazard pointers

Quoted 4 lines · Jonas Oberhauser

No, the issue introduced by the compiler optimization (or by your original patch) is that the CPU can speculatively load from the first pointer as soon as it has completed the load of that pointer:

You mean the compiler can do it. The inline asm has no impact on what the CPU does. The conditional isn't a barrier for the actual hardware. But once the compiler doesn't try to do it, the data dependency on the address does end up being an ordering constraint on the hardware too (I'm happy to say that I haven't heard from the crazies that want value prediction in a long time).

Just use a barrier. Or make sure to use the proper ordered memory accesses when possible. Don't use an inline asm for the compare - we don't even have anything insane like that as a portable helper, and we shouldn't have it.

Linus

#29 lore raw

Re: [RFC PATCH 1/4] hazptr: Add initial implementation of hazard pointers

Am 9/26/2024 um 6:12 PM schrieb Linus Torvalds:

Quoted 8 lines
Quoted 4 lines · Jonas Oberhauser

No, the issue introduced by the compiler optimization (or by your original patch) is that the CPU can speculatively load from the first pointer as soon as it has completed the load of that pointer:

You mean the compiler can do it.

What I mean is that if we only use rcu_dereference for the second load (and not either some form of compiler barrier or an acquire load), then the compiler can transform the second program from my previous e-mail (which if mapped 1:1 to hardware would be correct because hardware ensures the ordering based on the address dependency) into the first one (which is incorrect).

In particular, the compiler can change

if (node == node2) t = *node2;

into

if (node == node2) t = *node;

and then the CPU can speculatively read *node before knowing the value of node2.

The compiler can also speculatively read *node in this case, but that is not what I meant.

The code in Mathieu's original patch is already like the latter one and is broken even if the compiler does not do any optimizations.

Quoted 4 lines

The inline asm has no impact on what
the CPU does. The conditional isn't a barrier for the actual hardware. But once the compiler doesn't try to do it, the data dependency on the address does end up being an ordering constraint on the hardware too

Exactly. The inline asm would prevent the compiler from doing the transformation though, which would mean that the address dependency appears in the final compiler output.

Quoted 6 lines

Just use a barrier. Or make sure to use the proper ordered memory accesses when possible.

Don't use an inline asm for the compare - we
don't even have anything insane like that as a portable helper, and we shouldn't have it.

I'm glad you say that :))

I would also just use a barrier before returing the pointer.

Boqun seems to be unhappy with a barrier though, because it would theoretically also forbid unrelated optimizations. But I have not seen any evidence that there are any unrelated optimizations going on in the first place that would be forbidden by this.

Have fun,
jonas

#30 lore raw

Re: [RFC PATCH 1/4] hazptr: Add initial implementation of hazard pointers

Quoted 3 lines · Jonas Oberhauser

Boqun seems to be unhappy with a barrier though, because it would theoretically also forbid unrelated optimizations.

Well, doing a "barrier()" is kind of a big hammer thing, but honestly, I don't think we've ever seen any real situation where it makes a noticeable difference. Yes, it can pessimize compiler output more than strictly necessary, but the kind of code generation issues it causes tends to be the non-problematic kind (and particularly the kind that even a trivial OoO core will deal with well).

We do have some more directed compiler barriers available, and this code might be able to use OPTIMIZER_HIDE_VAR() for example. It's kind of a "single variable value barrier".

Honestly, we don't use it much. It just tends to be _too_specific. But it is there if somebody wants to use it.

Quoted 2 lines

But I have not seen any evidence that there are any unrelated optimizations going on in the first place that would be forbidden by this.

Compared to something like "smp_mb()", which is not just a compiler barrier but also generates typically very expensive instructions that completely mess with an OoO core, a regular compiler barrier is a complete non-issue. When you have those two close to each other, you'd have to make up some very odd situation where the plain "barrier()" is even noticeable.

Linus

author
#31 lore raw

Re: [RFC PATCH 1/4] hazptr: Add initial implementation of hazard pointers

Quoted 13 lines · Linus Torvalds
Quoted 3 lines · Jonas Oberhauser

Boqun seems to be unhappy with a barrier though, because it would theoretically also forbid unrelated optimizations.

Well, doing a "barrier()" is kind of a big hammer thing, but honestly, I don't think we've ever seen any real situation where it makes a noticeable difference. Yes, it can pessimize compiler output more than strictly necessary, but the kind of code generation issues it causes tends to be the non-problematic kind (and particularly the kind that even a trivial OoO core will deal with well).

Quoted 4 lines

We do have some more directed compiler barriers available, and this code might be able to use OPTIMIZER_HIDE_VAR() for example. It's kind of a "single variable value barrier".

Hmm.. this seems can do the trick?

	#define ADDRESS_EQ(var, expr)							\
	({										\
		bool _____cmp_res = (unsigned long)(var) == (unsigned long)(expr);	\
											\
		OPTIMIZER_HIDE_VAR(var);						\
		_____cmp_res;								\
	})

i.e. compare the address and hide the equality information immediately, so in hazptr code:

	ptr = READ_ONCE(*p);	// first read

	if (ptr == NULL)
		return NULL;

	head = (struct callback_head *)(ptr + head_offset);

	WRITE_ONCE(*hzp, head);
	smp_mb();

	ptr = READ_ONCE(*p); // read again

	if (!ADDRESS_EQ(ptr, (void *)head - head_offset)) { // pointer changed
		WRITE_ONCE(*hzp, NULL);  // reset hazard pointer
		return NULL;
	} else {
		// Optimizer lost the information on the value of 'ptr',
		// so it cannot replace it with head - head_offset.
		return ptr;
	}

Regards,
Boqun

Quoted 15 lines

Honestly, we don't use it much. It just tends to be _too_specific. But it is there if somebody wants to use it.

Quoted 2 lines

But I have not seen any evidence that there are any unrelated optimizations going on in the first place that would be forbidden by this.

Compared to something like "smp_mb()", which is not just a compiler barrier but also generates typically very expensive instructions that completely mess with an OoO core, a regular compiler barrier is a complete non-issue. When you have those two close to each other, you'd have to make up some very odd situation where the plain "barrier()" is even noticeable.

Linus

#32 lore raw

Re: [RFC PATCH 1/4] hazptr: Add initial implementation of hazard pointers

Quoted 7 lines · Boqun Feng
	#define ADDRESS_EQ(var, expr)							\
	({										\
		bool _____cmp_res = (unsigned long)(var) == (unsigned long)(expr);	\
											\
		OPTIMIZER_HIDE_VAR(var);						\
		_____cmp_res;								\
	})

If the goal is to ensure gcc uses the register populated by the second, I'm afraid it does not work. AFAIU, "hiding" the dependency chain does not prevent the SSA GVN optimization from combining the registers as being one and choosing one arbitrary source. "hiding" the dependency chain before or after the comparison won't help here.

int fct_hide_var_compare(void)

{
    int *a, *b;

    do {
        a = READ_ONCE(p);
        asm volatile ("" : : : "memory");
        b = READ_ONCE(p);
    } while (!ADDRESS_EQ(a, b));
    return *b;
}

gcc 14.2 x86-64:

fct_hide_var_compare:

 mov    rax,QWORD PTR [rip+0x0]        # 67 <fct_hide_var_compare+0x7>
 mov    rdx,QWORD PTR [rip+0x0]        # 6e <fct_hide_var_compare+0xe>
 cmp    rax,rdx
 jne    60 <fct_hide_var_compare>
 mov    eax,DWORD PTR [rax]

ret
main:
xor eax,eax
ret

gcc 14.2.0 ARM64:

fct_hide_var_compare:
adrp x0, .LANCHOR0
add x0, x0, :lo12:.LANCHOR0
.L12:

        ldr     x1, [x0]
        ldr     x2, [x0]
        cmp     x1, x2
        bne     .L12
        ldr     w0, [x1]

ret
p:
.zero 8

Signature · 3 lines
Mathieu Desnoyers
EfficiOS Inc.
https://www.efficios.com
author
#33 lore raw

Re: [RFC PATCH 1/4] hazptr: Add initial implementation of hazard pointers

Quoted 16 lines · Mathieu Desnoyers
Quoted 7 lines · Boqun Feng
	#define ADDRESS_EQ(var, expr)							\
	({										\
		bool _____cmp_res = (unsigned long)(var) == (unsigned long)(expr);	\
											\
		OPTIMIZER_HIDE_VAR(var);						\
		_____cmp_res;								\
	})

If the goal is to ensure gcc uses the register populated by the second, I'm afraid it does not work. AFAIU, "hiding" the dependency chain does not prevent the SSA GVN optimization from combining the registers as being one and choosing one arbitrary source. "hiding" the dependency chain before or after the comparison won't help here.

int fct_hide_var_compare(void)

Quoted 8 lines
{
     int *a, *b;

     do {
         a = READ_ONCE(p);
         asm volatile ("" : : : "memory");
         b = READ_ONCE(p);
     } while (!ADDRESS_EQ(a, b));

Note that ADDRESS_EQ() only hide first parameter, so this should be ADDRESS_EQ(b, a).

Regards,
Boqun

Quoted 36 lines
     return *b;
}

gcc 14.2 x86-64:

fct_hide_var_compare:

  mov    rax,QWORD PTR [rip+0x0]        # 67 <fct_hide_var_compare+0x7>
  mov    rdx,QWORD PTR [rip+0x0]        # 6e <fct_hide_var_compare+0xe>
  cmp    rax,rdx
  jne    60 <fct_hide_var_compare>
  mov    eax,DWORD PTR [rax]

ret
main:
xor eax,eax
ret

gcc 14.2.0 ARM64:

fct_hide_var_compare:
adrp x0, .LANCHOR0
add x0, x0, :lo12:.LANCHOR0
.L12:

         ldr     x1, [x0]
         ldr     x2, [x0]
         cmp     x1, x2
         bne     .L12
         ldr     w0, [x1]

ret
p:
.zero 8

Signature · 3 lines
Mathieu Desnoyers
EfficiOS Inc.
https://www.efficios.com
author
#34 lore raw

Re: [RFC PATCH 1/4] hazptr: Add initial implementation of hazard pointers

Quoted 12 lines · Boqun Feng
Quoted 9 lines · Mathieu Desnoyers
Quoted 7 lines · Boqun Feng
	#define ADDRESS_EQ(var, expr)							\
	({										\
		bool _____cmp_res = (unsigned long)(var) == (unsigned long)(expr);	\
											\
		OPTIMIZER_HIDE_VAR(var);						\
		_____cmp_res;								\
	})
Quoted 3 lines
Quoted 3 lines

If the goal is to ensure gcc uses the register populated by the second, I'm afraid it does not work. AFAIU, "hiding" the dependency chain does not prevent the SSA GVN optimization from combining the

Note it's not hiding the dependency, rather the equality,

Quoted 1 line
Quoted 1 line

registers as being one and choosing one arbitrary source. "hiding"

after OPTIMIZER_HIDE_VAR(var), compiler doesn't know whether 'var' is equal to 'expr' anymore, because OPTIMIZER_HIDE_VAR(var) uses "=r"(var) to indicate the output is overwritten. So when 'var' is referred later, compiler cannot use the register for a 'expr' value or any other register that has the same value, because 'var' may have a different value from the compiler's POV.

Quoted 6 lines
Quoted 6 lines

the dependency chain before or after the comparison won't help here.

int fct_hide_var_compare(void)

{
     int *a, *b;
Quoted 8 lines
Quoted 5 lines
     do {
         a = READ_ONCE(p);
         asm volatile ("" : : : "memory");
         b = READ_ONCE(p);
     } while (!ADDRESS_EQ(a, b));

Note that ADDRESS_EQ() only hide first parameter, so this should be ADDRESS_EQ(b, a).

I replaced ADDRESS_EQ(a, b) with ADDRESS_EQ(b, a), and the compile result shows it can prevent the issue:

gcc 14.2 x86-64:

fct_hide_var_compare:
.L2:

        mov     rcx, QWORD PTR p[rip]
        mov     rdx, QWORD PTR p[rip]
        mov     rax, rdx
        cmp     rcx, rdx
        jne     .L2
        mov     eax, DWORD PTR [rax]

ret

gcc 14.2.0 ARM64:

fct_hide_var_compare:
adrp x2, p
add x2, x2, :lo12:p
.L2:

        ldr     x3, [x2]
        ldr     x1, [x2]
        mov     x0, x1
        cmp     x3, x1
        bne     .L2
        ldr     w0, [x0]

ret

Link to godbolt:

https://godbolt.org/z/a7jsfzjxY

Regards,
Boqun

Quoted 40 lines

Regards,
Boqun

Quoted 36 lines
     return *b;
}

gcc 14.2 x86-64:

fct_hide_var_compare:

  mov    rax,QWORD PTR [rip+0x0]        # 67 <fct_hide_var_compare+0x7>
  mov    rdx,QWORD PTR [rip+0x0]        # 6e <fct_hide_var_compare+0xe>
  cmp    rax,rdx
  jne    60 <fct_hide_var_compare>
  mov    eax,DWORD PTR [rax]

ret
main:
xor eax,eax
ret

gcc 14.2.0 ARM64:

fct_hide_var_compare:
adrp x0, .LANCHOR0
add x0, x0, :lo12:.LANCHOR0
.L12:

         ldr     x1, [x0]
         ldr     x2, [x0]
         cmp     x1, x2
         bne     .L12
         ldr     w0, [x1]

ret
p:
.zero 8

Signature · 3 lines
Mathieu Desnoyers
EfficiOS Inc.
https://www.efficios.com
#35 lore raw

Re: [RFC PATCH 1/4] hazptr: Add initial implementation of hazard pointers

Quoted 40 lines · Boqun Feng
Quoted 12 lines · Boqun Feng
Quoted 9 lines · Mathieu Desnoyers
Quoted 7 lines · Boqun Feng
	#define ADDRESS_EQ(var, expr)							\
	({										\
		bool _____cmp_res = (unsigned long)(var) == (unsigned long)(expr);	\
											\
		OPTIMIZER_HIDE_VAR(var);						\
		_____cmp_res;								\
	})
Quoted 3 lines
Quoted 3 lines

If the goal is to ensure gcc uses the register populated by the second, I'm afraid it does not work. AFAIU, "hiding" the dependency chain does not prevent the SSA GVN optimization from combining the

Note it's not hiding the dependency, rather the equality,

Quoted 1 line
Quoted 1 line

registers as being one and choosing one arbitrary source. "hiding"

after OPTIMIZER_HIDE_VAR(var), compiler doesn't know whether 'var' is equal to 'expr' anymore, because OPTIMIZER_HIDE_VAR(var) uses "=r"(var) to indicate the output is overwritten. So when 'var' is referred later, compiler cannot use the register for a 'expr' value or any other register that has the same value, because 'var' may have a different value from the compiler's POV.

Quoted 12 lines
Quoted 11 lines

the dependency chain before or after the comparison won't help here.

int fct_hide_var_compare(void)

{
      int *a, *b;

      do {
          a = READ_ONCE(p);
          asm volatile ("" : : : "memory");
          b = READ_ONCE(p);
      } while (!ADDRESS_EQ(a, b));
Quoted 5 lines
Quoted 2 lines

Note that ADDRESS_EQ() only hide first parameter, so this should be ADDRESS_EQ(b, a).

I replaced ADDRESS_EQ(a, b) with ADDRESS_EQ(b, a), and the compile result shows it can prevent the issue:

I see, yes. It prevents the issue by making the compiler create a copy of the value "modified" by the asm before doing the equality comparison.

This means the compiler cannot derive the value for b from the first load when b is used after after the equality comparison.

The only downside of OPTIMIZER_HIDE_VAR() is that it adds an extra "mov" instruction to move the content across registers. I don't think it matters performance wise though, so that solution is appealing because it is arch-agnostic.

One small improvement over your proposed solution would be to apply OPTIMIZER_HIDE_VAR() on both inputs. Because this is not a volatile asm, it is simply optimized away if var1 or var2 is unused following the equality comparison. It is more convenient to prevent replacement of both addresses being compared by the other rather than providing the guarantee only on a single parameter:

#define OPTIMIZER_HIDE_VAR(var)			\
        __asm__ ("" : "+r" (var))

#define ADDRESS_EQ(var1, var2) \

({						\
	bool _____cmp_res = (var1) == (var2);	\
						\
	OPTIMIZER_HIDE_VAR(var1);		\
	OPTIMIZER_HIDE_VAR(var2);		\
	_____cmp_res;				\
})

Thanks,

Mathieu

Quoted 25 lines

gcc 14.2 x86-64:

fct_hide_var_compare:
.L2:

         mov     rcx, QWORD PTR p[rip]
         mov     rdx, QWORD PTR p[rip]
         mov     rax, rdx
         cmp     rcx, rdx
         jne     .L2
         mov     eax, DWORD PTR [rax]

ret

gcc 14.2.0 ARM64:

fct_hide_var_compare:
adrp x2, p
add x2, x2, :lo12:p
.L2:

         ldr     x3, [x2]
         ldr     x1, [x2]
         mov     x0, x1
         cmp     x3, x1
         bne     .L2
         ldr     w0, [x0]
Quoted 5 lines

ret

Link to godbolt:

	https://godbolt.org/z/a7jsfzjxY-- 

Mathieu Desnoyers
EfficiOS Inc.
https://www.efficios.com

#36 lore raw

Re: [RFC PATCH 1/4] hazptr: Add initial implementation of hazard pointers

Quoted 1 line · Mathieu Desnoyers

On 2024-09-27 06:28, Boqun Feng wrote:

[...]

Quoted 15 lines
Quoted 2 lines

I replaced ADDRESS_EQ(a, b) with ADDRESS_EQ(b, a), and the compile result shows it can prevent the issue:

I see, yes. It prevents the issue by making the compiler create a copy of the value "modified" by the asm before doing the equality comparison.

This means the compiler cannot derive the value for b from the first load when b is used after after the equality comparison.

The only downside of OPTIMIZER_HIDE_VAR() is that it adds an extra "mov" instruction to move the content across registers. I don't think it matters performance wise though, so that solution is appealing because it is arch-agnostic.

Quoted 6 lines

One small improvement over your proposed solution would be to apply OPTIMIZER_HIDE_VAR() on both inputs. Because this is not a volatile asm, it is simply optimized away if var1 or var2 is unused following the equality comparison. It is more convenient to prevent replacement of both addresses being compared by the other rather than providing the guarantee only on a single parameter:

Actually, your approach is better (only preserving the address dependency on the first parameter), because it allows the second parameter to be a constant.

Here is a diff. Please let me know if I need to improve anything wrt comments or implementation:

include/linux/compiler.h +26 -0
index 2df665fa2964..52434eccd715 100644
@@ -186,6 +186,32 @@ void ftrace_likely_update(struct ftrace_likely_data *f, int val,
 	__asm__ ("" : "=r" (var) : "0" (var))
 #endif
 
+/*
+ * Compare an address with an expression while preserving the address
+ * dependencies for later use of the address. It should be used when
+ * comparing an address returned by rcu_dereference() with another
+ * address (either constant or in registers).
+ *
+ * This is needed to prevent the compiler SSA GVN optimization pass from
+ * replacing the register holding @addr by @expr (either a constant or a
+ * register) based on their equality, which does not preserve address
+ * dependencies and allows the following misordering speculations:
+ *
+ * - If @expr is a constant, the compiler can issue the loads which depend
+ *   on @addr before the load of @addr.
+ * - If @expr is a register populated by a prior load, weakly-ordered
+ *   CPUs can speculate loads which depend on @addr before the load of the
+ *   address they depend on.
+ */
+#ifndef ADDRESS_EQ
+#define ADDRESS_EQ(addr, expr)					\
+	({							\
+		bool __res = (addr) == (expr);			\
+		OPTIMIZER_HIDE_VAR(addr);			\
+		__res;						\
+	})
+#endif
+
 #define __UNIQUE_ID(prefix) __PASTE(__PASTE(__UNIQUE_ID_, prefix), __COUNTER__)
 
 /**
Signature · 3 lines
Mathieu Desnoyers
EfficiOS Inc.
https://www.efficios.com
#37 lore raw

Re: [RFC PATCH 1/4] hazptr: Add initial implementation of hazard pointers

Quoted 39 lines · Mathieu Desnoyers
Quoted 1 line · Mathieu Desnoyers

On 2024-09-27 06:28, Boqun Feng wrote:

[...]

Quoted 15 lines
Quoted 2 lines

I replaced ADDRESS_EQ(a, b) with ADDRESS_EQ(b, a), and the compile result shows it can prevent the issue:

I see, yes. It prevents the issue by making the compiler create a copy of the value "modified" by the asm before doing the equality comparison.

This means the compiler cannot derive the value for b from the first load when b is used after after the equality comparison.

The only downside of OPTIMIZER_HIDE_VAR() is that it adds an extra "mov" instruction to move the content across registers. I don't think it matters performance wise though, so that solution is appealing because it is arch-agnostic.

Quoted 6 lines

One small improvement over your proposed solution would be to apply OPTIMIZER_HIDE_VAR() on both inputs. Because this is not a volatile asm, it is simply optimized away if var1 or var2 is unused following the equality comparison. It is more convenient to prevent replacement of both addresses being compared by the other rather than providing the guarantee only on a single parameter:

Actually, your approach is better (only preserving the address dependency on the first parameter), because it allows the second parameter to be a constant.

Here is a diff. Please let me know if I need to improve anything wrt comments or implementation:

include/linux/compiler.h +0 -0
index 2df665fa2964..52434eccd715 100644
@@ -186,6 +186,32 @@ void ftrace_likely_update(struct ftrace_likely_data 
 *f, int val,
      __asm__ ("" : "=r" (var) : "0" (var))

include/linux/compiler.h void ftrace_likely_update(struct ftrace_likely_data · line 197

Quoted 10 lines
include/linux/compiler.h +8 -0
  #endif
 
+/*
+ * Compare an address with an expression while preserving the address
+ * dependencies for later use of the address. It should be used when
+ * comparing an address returned by rcu_dereference() with another
+ * address (either constant or in registers).
+ *
+ * This is needed to prevent the compiler SSA GVN optimization pass from
+ * replacing the register holding @addr by @expr (either a constant or a

Actually, I've done a bit on testing on godbolt, and it appears that disabling this specific optimization makes the problem disappear:
-fcse-follow-jumps (by use of -fno-cse-follow-jumps).

I will update this comment to state that both CSE and SSA GVN optimizations can cause issues there.

Thanks,

Mathieu

Quoted 23 lines
include/linux/compiler.h +18 -0
+ * register) based on their equality, which does not preserve address
+ * dependencies and allows the following misordering speculations:
+ *
+ * - If @expr is a constant, the compiler can issue the loads which depend
+ *   on @addr before the load of @addr.
+ * - If @expr is a register populated by a prior load, weakly-ordered
+ *   CPUs can speculate loads which depend on @addr before the load of the
+ *   address they depend on.
+ */
+#ifndef ADDRESS_EQ
+#define ADDRESS_EQ(addr, expr)                    \
+    ({                            \
+        bool __res = (addr) == (expr);            \
+        OPTIMIZER_HIDE_VAR(addr);            \
+        __res;                        \
+    })
+#endif
+
  #define __UNIQUE_ID(prefix) __PASTE(__PASTE(__UNIQUE_ID_, prefix), 
 __COUNTER__)

 /**

Signature · 3 lines
Mathieu Desnoyers
EfficiOS Inc.
https://www.efficios.com
#38 lore raw

Re: [RFC PATCH 1/4] hazptr: Add initial implementation of hazard pointers

In reply to Boqun Feng

2024年9月27日 12:28,Boqun Feng <[email protected]> wrote:

Quoted 71 lines · Boqun Feng
Quoted 12 lines · Mathieu Desnoyers
Quoted 9 lines · Boqun Feng
Quoted 7 lines

#define ADDRESS_EQ(var, expr) \
({ \
bool _____cmp_res = (unsigned long)(var) == (unsigned long)(expr); \
\
OPTIMIZER_HIDE_VAR(var); \
_____cmp_res; \
})

Quoted 3 lines
Quoted 3 lines

If the goal is to ensure gcc uses the register populated by the second, I'm afraid it does not work. AFAIU, "hiding" the dependency chain does not prevent the SSA GVN optimization from combining the

Note it's not hiding the dependency, rather the equality,

Quoted 1 line
Quoted 1 line

registers as being one and choosing one arbitrary source. "hiding"

after OPTIMIZER_HIDE_VAR(var), compiler doesn't know whether 'var' is equal to 'expr' anymore, because OPTIMIZER_HIDE_VAR(var) uses "=r"(var) to indicate the output is overwritten. So when 'var' is referred later, compiler cannot use the register for a 'expr' value or any other register that has the same value, because 'var' may have a different value from the compiler's POV.

Quoted 6 lines
Quoted 6 lines

the dependency chain before or after the comparison won't help here.

int fct_hide_var_compare(void)

{
    int *a, *b;
Quoted 8 lines
Quoted 5 lines
    do {
        a = READ_ONCE(p);
        asm volatile ("" : : : "memory");
        b = READ_ONCE(p);
    } while (!ADDRESS_EQ(a, b));

Note that ADDRESS_EQ() only hide first parameter, so this should be ADDRESS_EQ(b, a).

I replaced ADDRESS_EQ(a, b) with ADDRESS_EQ(b, a), and the compile result shows it can prevent the issue:

gcc 14.2 x86-64:

fct_hide_var_compare:
.L2:

       mov     rcx, QWORD PTR p[rip]
       mov     rdx, QWORD PTR p[rip]
       mov     rax, rdx
       cmp     rcx, rdx
       jne     .L2
       mov     eax, DWORD PTR [rax]

ret

gcc 14.2.0 ARM64:

fct_hide_var_compare:
adrp x2, p
add x2, x2, :lo12:p
.L2:

       ldr     x3, [x2]
       ldr     x1, [x2]
       mov     x0, x1
       cmp     x3, x1
       bne     .L2
       ldr     w0, [x0]
Quoted 5 lines

ret

Link to godbolt:

https://godbolt.org/z/a7jsfzjxY

Checking the assembly generated by different compilers for the kernel on the local machine will yield more accurate results. Some optimizations are restricted by the kernel. Therefore, if you use Godbolt, ensure that the compiler arguments match those used for the kernel.

Quoted 43 lines

Regards,
Boqun

Quoted 39 lines

Regards,
Boqun

Quoted 36 lines
    return *b;
}

gcc 14.2 x86-64:

fct_hide_var_compare:

 mov    rax,QWORD PTR [rip+0x0]        # 67 <fct_hide_var_compare+0x7>
 mov    rdx,QWORD PTR [rip+0x0]        # 6e <fct_hide_var_compare+0xe>
 cmp    rax,rdx
 jne    60 <fct_hide_var_compare>
 mov    eax,DWORD PTR [rax]

ret
main:
xor eax,eax
ret

gcc 14.2.0 ARM64:

fct_hide_var_compare:
adrp x0, .LANCHOR0
add x0, x0, :lo12:.LANCHOR0
.L12:

        ldr     x1, [x0]
        ldr     x2, [x0]
        cmp     x1, x2
        bne     .L12
        ldr     w0, [x1]

ret
p:
.zero 8

Signature · 3 lines
Mathieu Desnoyers
EfficiOS Inc.
https://www.efficios.com
#39 lore raw

Re: [RFC PATCH 1/4] hazptr: Add initial implementation of hazard pointers

In reply to Boqun Feng
Quoted 2 lines · Boqun Feng

Note that ADDRESS_EQ() only hide first parameter, so this should be ADDRESS_EQ(b, a).

Yeah, please stop making things unnecessarily complicated.

Just use a barrier(). Please. Stop these stupid games until you can show why it matters.

And by "why it matters" I mean "major difference in code generation", not some "it uses one more register and has to spill" kind of small detail.

At this point, I'm not even convinced the whole hazard pointer approach makes sense. And you're not helping by making it more complicated than it needs to be.

Linus

#40 lore raw

Re: [RFC PATCH 1/4] hazptr: Add initial implementation of hazard pointers

Quoted 8 lines · Linus Torvalds
Quoted 2 lines · Boqun Feng

Note that ADDRESS_EQ() only hide first parameter, so this should be ADDRESS_EQ(b, a).

Yeah, please stop making things unnecessarily complicated.

Just use a barrier(). Please. Stop these stupid games until you can show why it matters.

The barrier() is ineffective at fixing the issue. It does not prevent the compiler CSE from losing the address dependency:

int fct_2_volatile_barriers(void)

{
    int *a, *b;

    do {
        a = READ_ONCE(p);
        asm volatile ("" : : : "memory");
        b = READ_ONCE(p);
    } while (a != b);
    asm volatile ("" : : : "memory");  <----- where you would like your barrier
    return *b;
}

With gcc 14.2 (arm64):

fct_2_volatile_barriers:
adrp x0, .LANCHOR0
add x0, x0, :lo12:.LANCHOR0
.L2:

        ldr     x1, [x0]    <------ x1 populated by first load.
        ldr     x2, [x0]
        cmp     x1, x2
        bne     .L2
        ldr     w0, [x1]    <------ x1 is used for access which should depend on b.

ret

On weakly-ordered architectures, this lets CPU speculation use the result from the first load to speculate "ldr w0, [x1]" before "ldr x2, [x0]".
Based on the RCU documentation, the control dependency does not prevent the CPU from speculating loads.

There are a few ways to fix this:

- Compile everything with -fno-cse-follow-jumps.
- Make the compiler unaware of the relationship between the address equality and address-dependent use of b. This can be done either using ADDRESS_EQ() or asm goto.

I prefer ADDRESS_EQ() because it is arch-agnostic. I don't care that it adds one more register movement instruction.

Quoted 3 lines

And by "why it matters" I mean "major difference in code generation", not some "it uses one more register and has to spill" kind of small detail.

Why it matters is because gcc generates code that does not preserve address dependency of the second READ_ONCE().

Quoted 3 lines

At this point, I'm not even convinced the whole hazard pointer approach makes sense. And you're not helping by making it more complicated than it needs to be.

I'm preparing a small series that aims to show how a minimal hazard pointer implementation can help improve common scenarios:

- Guarantee object existence on pointer dereference to increment a reference count:
- replace locking used for that purpose in drivers (e.g. usb),
- replace RCU + inc_not_zero pattern,
- rtmutex: I suspect we can improve situations where locks need to be taken in reverse dependency chain order by guaranteeing existence of first and second locks in traversal order, allowing them to be locked in the correct order (which is reverse from traversal order) rather than try-lock+retry on nested lock. This can be done with hazard pointers without requiring object reclaim to be delayed by an RCU grace period.

Thanks,

Mathieu

Signature · 3 lines
Mathieu Desnoyers
EfficiOS Inc.
https://www.efficios.com
#41 lore raw

Re: [RFC PATCH 1/4] hazptr: Add initial implementation of hazard pointers

Quoted 4 lines · Mathieu Desnoyers

The barrier() is ineffective at fixing the issue. It does not prevent the compiler CSE from losing the address dependency:

Ok. Thanks for actually specifying code.

That needs to be

(a) in a comment

(b) the value barrier needs to be on *both* values so that the order
of the equality testing doesn't matter.

Quoted 2 lines

I'm preparing a small series that aims to show how a minimal hazard pointer implementation can help improve common scenarios:

I want actual numbers on real loads. Just so you know. Not "this can help". But "this actually really _does_ help".

Linus

#42 lore raw

Re: [RFC PATCH 1/4] hazptr: Add initial implementation of hazard pointers

Quoted 7 lines · Linus Torvalds
Quoted 4 lines · Mathieu Desnoyers

The barrier() is ineffective at fixing the issue. It does not prevent the compiler CSE from losing the address dependency:

Quoted 5 lines

Ok. Thanks for actually specifying code.

That needs to be

(a) in a comment

OK. I'll add the code/asm examples to the comment above ADDRESS_EQ().

Quoted 3 lines

(b) the value barrier needs to be on *both* values so that the order
of the equality testing doesn't matter.

If we use OPTIMIZER_HIDE_VAR() on both parameters, it indeed minimizes the odds that someone get the order wrong, but it disallows using ADDRESS_EQ() with a constant parameter
(e.g. ADDRESS_EQ(ptr, &mystruct)), which would be nice to cover. It works fine with using OPTIMIZER_HIDE_VAR() on the first argument, but it opens the door to misuses.

Perhaps there is a trick with compiler builtins we could do to only use OPTIMIZER_HIDE_VAR() on non-constant arguments, but I can't get it to work so far.

Quoted 6 lines
Quoted 3 lines

I'm preparing a small series that aims to show how a minimal hazard pointer implementation can help improve common scenarios:

I want actual numbers on real loads. Just so you know. Not "this can help". But "this actually really _does_ help".

Noted, thanks!

Mathieu

Signature · 3 lines
Mathieu Desnoyers
EfficiOS Inc.
https://www.efficios.com
#43 lore raw

Re: [RFC PATCH 1/4] hazptr: Add initial implementation of hazard pointers

Quoted 7 lines · Mathieu Desnoyers
Quoted 3 lines

(b) the value barrier needs to be on *both* values so that the order
of the equality testing doesn't matter.

If we use OPTIMIZER_HIDE_VAR() on both parameters, it indeed minimizes the odds that someone get the order wrong, but it disallows using ADDRESS_EQ() with a constant parameter

No it doesn't.

This is trivial - just hide the source of the *comparison*, so that the compiler doesn't know what you are comparing, and can't use it to then replace one with the other:

static __always_inline bool compare_ptr(const volatile void *a,
const volatile void *b)

   {
        OPTIMIZER_HIDE_VAR(a);
        OPTIMIZER_HIDE_VAR(b);
        return a == b;

}

compares two arbitrary pointer values without allowing the compiler to then use the comparison result to use either of the original values as a replacement for the other.

And yes, that "hide both" model will cause a bit more register pressure, because the compiler will now compare two values that it really thinks are potentially different from the originals. So you'll have two "useless" temporaries that contain the same values as the source pointers, but if that's the cost of having a comparison that the compiler can't see, that's fine.

Making it a bit less obvious, you can hide just one of the variables - you don't actually need to hide both m(but for clarity, maybe you want to).

Because even hiding the value one from the compiler will mean that it can't use the comparison to decide that the originals are equal, even if one of them is unhidden.

No?

Linus

#44 lore raw

Re: [RFC PATCH 1/4] hazptr: Add initial implementation of hazard pointers

Am 9/27/2024 um 8:13 PM schrieb Linus Torvalds:

Quoted 7 lines

Because even hiding the value one from the compiler will mean that it can't use the comparison to decide that the originals are equal, even if one of them is unhidden.

No?

Linus

I think it depends on which one you hide.

If you do

z = b;
hide(z);
if (a==z) { *b; }

then it will be fine, because it knows a==z but nothing about the relation of b with a or z.

But for

z = a;
hide(z);
if (z==b) { *b; }

then it would still know that b == z, and could replace *b with *z (which really is *a).

Best wishes,
jonas

#45 lore raw

Re: [RFC PATCH 1/4] hazptr: Add initial implementation of hazard pointers

Quoted 2 lines · Jonas Oberhauser

I think it depends on which one you hide.

No.

Dammit, people, read the code I posted.

Quoted 5 lines

But for

  z = a;
  hide(z);
  if (z==b) { *b; }

No.

I *intentionally* made it an inline function, and only hid the arguments to the equality comparison.

So the "hide(z)" hides the argument to the inline function - NOT THE ORIGINAL.

Quoted 2 lines

then it would still know that b == z, and could replace *b with *z (which really is *a).

No.

The hiding is literally *ONLY* for the comparison. It's inside the helper function. It doesn't affect the originals at all.

Which means that the compiler CANNOT KNOW anything about the original pointers when it compares for equality (or inequality).

Basically, the comparison is now a black box to the compiler, and the compiler cannot use the result of the comparison to make ANY judgment on whether the two original pointers were related or not.

Linus

#46 lore raw

Re: [RFC PATCH 1/4] hazptr: Add initial implementation of hazard pointers

Quoted 2 lines · Linus Torvalds

Dammit, people, read the code I posted.

Actually, no, apologies. You were right, and I was wrong.

It does need both of the sources of the comparison to be hidden, because while even hiding just one side makes the comparison result "meaningless" as far as the compiler is concerned, the compiler will still have generated a pseudo for the hidden value, and might decide that it can re-use that pseudo for the non-hidden pointer if the two then match.

So yeah, the example function I posted should be safe, but my "you can probably make do with hiding just one side" was actually a bogus and invalid optimization. You do need to hide both sides. Not just for clarity, but for correctness.

Linus

#47 lore raw

Re: [RFC PATCH 1/4] hazptr: Add initial implementation of hazard pointers

In reply to Linus Torvalds
Quoted 16 lines · Linus Torvalds
Quoted 7 lines · Mathieu Desnoyers
Quoted 3 lines

(b) the value barrier needs to be on *both* values so that the order
of the equality testing doesn't matter.

If we use OPTIMIZER_HIDE_VAR() on both parameters, it indeed minimizes the odds that someone get the order wrong, but it disallows using ADDRESS_EQ() with a constant parameter

No it doesn't.

This is trivial - just hide the source of the *comparison*, so that the compiler doesn't know what you are comparing, and can't use it to then replace one with the other:

Quoted 7 lines

static __always_inline bool compare_ptr(const volatile void *a,
const volatile void *b)

    {
         OPTIMIZER_HIDE_VAR(a);
         OPTIMIZER_HIDE_VAR(b);
         return a == b;
    }

Cool! It works! Thanks!

Quoted 4 lines

compares two arbitrary pointer values without allowing the compiler to then use the comparison result to use either of the original values as a replacement for the other.

Yep. And the static inline is much cleaner as it allows users to pass constants as well.

Quoted 7 lines

And yes, that "hide both" model will cause a bit more register pressure, because the compiler will now compare two values that it really thinks are potentially different from the originals. So you'll have two "useless" temporaries that contain the same values as the source pointers, but if that's the cost of having a comparison that the compiler can't see, that's fine.

I've tried it and it seems that the compiler only leaves one "mov" extra there, since the extra register movement on the input that is not used afterwards can then be optimized away.

Quoted 10 lines

Making it a bit less obvious, you can hide just one of the variables - you don't actually need to hide both m(but for clarity, maybe you want to).

Because even hiding the value one from the compiler will mean that it can't use the comparison to decide that the originals are equal, even if one of them is unhidden.

No?

I would prefer hiding the two input variables.

Hust hiding one variable might work for CSE (and light godbolt attempts seem to confirm this), but I'm worried that it eventually breaks when compilers start making SSA GVN optimizations smarter.

AFAIU, in the SSA GVN model, if we just hide @a before the comparison and don't hide @b, we'd be in a situation where the compiler could know that the version of the variable generated by hiding @a (call it a') is equal to @b, and therefore when using @b afterward could instead use a', which is derived from @a rather than @b.

It may not happen in practice just because why would a sane optimization would prefer using a version that is deeper in the dependency chain (a') rather than @b, but that would be based on assumptions on how specific heuristics work, and would therefore be fragile.

Thanks,

Mathieu

Signature · 3 lines
Mathieu Desnoyers
EfficiOS Inc.
https://www.efficios.com
#48 lore raw

Re: [RFC PATCH 1/4] hazptr: Add initial implementation of hazard pointers

In reply to Linus Torvalds
Quoted 14 lines · Linus Torvalds
Quoted 4 lines · Jonas Oberhauser

No, the issue introduced by the compiler optimization (or by your original patch) is that the CPU can speculatively load from the first pointer as soon as it has completed the load of that pointer:

You mean the compiler can do it. The inline asm has no impact on what the CPU does. The conditional isn't a barrier for the actual hardware. But once the compiler doesn't try to do it, the data dependency on the address does end up being an ordering constraint on the hardware too (I'm happy to say that I haven't heard from the crazies that want value prediction in a long time).

Quoted 4 lines

Just use a barrier. Or make sure to use the proper ordered memory accesses when possible. Don't use an inline asm for the compare - we don't even have anything insane like that as a portable helper, and we shouldn't have it.

How does the compiler barrier help in any way here ?

I am concerned about the compiler SSA GVN (Global Value Numbering) optimizations, and I don't think a compiler barrier solves anything. (or I'm missing something obvious)

I was concerned about the suggestion from Jonas to use "node2" rather than "node" after the equality check as a way to ensure the intended register is used to return the pointer, because after the SSA GVN optimization pass, AFAIU this won't help in any way. I have a set of examples below that show gcc use the result of the first load, and clang use the result of the second load (on both x86-64 and aarch64). Likewise when a load-acquire is used as second load, which I find odd. Hopefully mixing this optimization from gcc with speculation still abide by the memory model.

Only the asm goto approach ensures that gcc uses the result from the second load.

#include <stdbool.h>

#define READ_ONCE(x)   \
    (*(__volatile__  __typeof__(x) *)&(x))

static inline
bool same_ptr(void *a, void *b)

{
    asm goto (
#ifdef __x86_64__
        "cmpq %[a], %[b]\n\t"
        "jne %l[ne]\n\t"
#elif defined(__aarch64__)
        "cmp %[a], %[b]\n\t"
        "bne %l[ne]\n\t"
#else
# error "unimplemented"
#endif
        : : [a] "r" (a), [b] "r" (b)
        : : ne);
    return true;
ne:
    return false;
}

int *p;

int fct_2_volatile(void)

{
    int *a, *b;

    do {
        a = READ_ONCE(p);
        asm volatile ("" : : : "memory");
        b = READ_ONCE(p);
    } while (a != b);
    return *b;
}

int fct_volatile_acquire(void)

{
    int *a, *b;

    do {
        a = READ_ONCE(p);
        asm volatile ("" : : : "memory");
        b = __atomic_load_n(&p, __ATOMIC_ACQUIRE);
    } while (a != b);
    return *b;
}

int fct_asm_compare(void)

{
    int *a, *b;

    do {
        a = READ_ONCE(p);
        asm volatile ("" : : : "memory");
        b = READ_ONCE(p);
    } while (!same_ptr(a, b));
    return *b;
}

x86-64 gcc 14.2:

fct_2_volatile:

 mov    rax,QWORD PTR [rip+0x0]        # 7 <fct_2_volatile+0x7>
 mov    rdx,QWORD PTR [rip+0x0]        # e <fct_2_volatile+0xe>
 cmp    rax,rdx
 jne    0 <fct_2_volatile>
 mov    eax,DWORD PTR [rax]
 ret
 cs nop WORD PTR [rax+rax*1+0x0]
fct_volatile_acquire:
 mov    rax,QWORD PTR [rip+0x0]        # 27 <fct_volatile_acquire+0x7>
 mov    rdx,QWORD PTR [rip+0x0]        # 2e <fct_volatile_acquire+0xe>
 cmp    rax,rdx
 jne    20 <fct_volatile_acquire>
 mov    eax,DWORD PTR [rax]
 ret
 cs nop WORD PTR [rax+rax*1+0x0]
fct_asm_compare:
 mov    rdx,QWORD PTR [rip+0x0]        # 47 <fct_asm_compare+0x7>
 mov    rax,QWORD PTR [rip+0x0]        # 4e <fct_asm_compare+0xe>
 cmp    rax,rdx
 jne    40 <fct_asm_compare>
 mov    eax,DWORD PTR [rax]

ret
main:
xor eax,eax
ret

x86-64 clang 19.1.0:

fct_2_volatile:

 mov    rcx,QWORD PTR [rip+0x0]        # 7 <fct_2_volatile+0x7>
 mov    rax,QWORD PTR [rip+0x0]        # e <fct_2_volatile+0xe>
 cmp    rcx,rax
 jne    0 <fct_2_volatile>
 mov    eax,DWORD PTR [rax]
 ret
 cs nop WORD PTR [rax+rax*1+0x0]
fct_volatile_acquire:
 mov    rcx,QWORD PTR [rip+0x0]        # 27 <fct_volatile_acquire+0x7>
 mov    rax,QWORD PTR [rip+0x0]        # 2e <fct_volatile_acquire+0xe>
 cmp    rcx,rax
 jne    20 <fct_volatile_acquire>
 mov    eax,DWORD PTR [rax]
 ret
 cs nop WORD PTR [rax+rax*1+0x0]
fct_asm_compare:
 mov    rcx,QWORD PTR [rip+0x0]        # 47 <fct_asm_compare+0x7>
 mov    rax,QWORD PTR [rip+0x0]        # 4e <fct_asm_compare+0xe>
 cmp    rax,rcx
 jne    40 <fct_asm_compare>
 mov    eax,DWORD PTR [rax]

ret
cs nop WORD PTR [rax+rax*1+0x0]
main:
xor eax,eax
ret

ARM64 gcc 14.2.0:

fct_2_volatile:
adrp x0, .LANCHOR0
add x0, x0, :lo12:.LANCHOR0
.L2:

        ldr     x1, [x0]
        ldr     x2, [x0]
        cmp     x1, x2
        bne     .L2
        ldr     w0, [x1]

ret
fct_volatile_acquire:
adrp x0, .LANCHOR0
add x0, x0, :lo12:.LANCHOR0
.L6:

        ldr     x1, [x0]
        ldar    x2, [x0]
        cmp     x1, x2
        bne     .L6
        ldr     w0, [x1]

ret
fct_asm_compare:
adrp x1, .LANCHOR0
add x1, x1, :lo12:.LANCHOR0
.L9:

        ldr     x2, [x1]
        ldr     x0, [x1]
        cmp x2, x0
        bne .L9

        ldr     w0, [x0]
        ret

p:
.zero 8

armv8-a clang (trunk):

fct_2_volatile:
adrp x8, 0 <fct_2_volatile>
ldr x10, [x8]
ldr x9, [x8]
cmp x10, x9
b.ne 4 <fct_2_volatile+0x4> // b.any
ldr w0, [x9]
ret
fct_volatile_acquire:
adrp x8, 0 <fct_2_volatile>
add x8, x8, #0x0
ldr x10, [x8]
ldar x9, [x8]
cmp x10, x9
b.ne 24 <fct_volatile_acquire+0x8> // b.any
ldr w0, [x9]
ret
fct_asm_compare:
adrp x8, 0 <fct_2_volatile>
ldr x9, [x8]
ldr x8, [x8]
cmp x9, x8
b.ne 3c <fct_asm_compare> // b.any
ldr w0, [x8]
ret
main:
mov w0, wzr

Signature · 3 lines
Mathieu Desnoyers
EfficiOS Inc.
https://www.efficios.com
author
#49 lore raw

Re: [RFC PATCH 1/4] hazptr: Add initial implementation of hazard pointers

Quoted 20 lines · Mathieu Desnoyers
Quoted 14 lines · Linus Torvalds
Quoted 4 lines · Jonas Oberhauser

No, the issue introduced by the compiler optimization (or by your original patch) is that the CPU can speculatively load from the first pointer as soon as it has completed the load of that pointer:

You mean the compiler can do it. The inline asm has no impact on what the CPU does. The conditional isn't a barrier for the actual hardware. But once the compiler doesn't try to do it, the data dependency on the address does end up being an ordering constraint on the hardware too (I'm happy to say that I haven't heard from the crazies that want value prediction in a long time).

Quoted 4 lines

Just use a barrier. Or make sure to use the proper ordered memory accesses when possible. Don't use an inline asm for the compare - we don't even have anything insane like that as a portable helper, and we shouldn't have it.

Quoted 5 lines

How does the compiler barrier help in any way here ?

I am concerned about the compiler SSA GVN (Global Value Numbering) optimizations, and I don't think a compiler barrier solves anything. (or I'm missing something obvious)

I think you're right, a compiler barrier doesn't help here:

	head = READ_ONCE(p);
	smp_mb();
	WRITE_ONCE(*slot, head);

	ptr = READ_ONCE(p);
	if (ptr != head) {
		...
	} else {
		barrier();
		return ptr;
	}

compilers can replace 'ptr' with 'head' because of the equality, and even putting barrier() here cannot prevent compiler to rewrite the else branch into:

	else {
		barrier();
		return head;
	}

because that's just using a different register, unrelated to memory accesses.

Jonas, am I missing something subtle? Or this is different than what you proposed?

Regards,
Boqun

Quoted 14 lines

I was concerned about the suggestion from Jonas to use "node2" rather than "node" after the equality check as a way to ensure the intended register is used to return the pointer, because after the SSA GVN optimization pass, AFAIU this won't help in any way. I have a set of examples below that show gcc use the result of the first load, and clang use the result of the second load (on both x86-64 and aarch64). Likewise when a load-acquire is used as second load, which I find odd. Hopefully mixing this optimization from gcc with speculation still abide by the memory model.

Only the asm goto approach ensures that gcc uses the result from the second load.

[...]

#50 lore raw

Re: [RFC PATCH 1/4] hazptr: Add initial implementation of hazard pointers

Two comments inline,

Am 9/27/2024 um 6:38 AM schrieb Boqun Feng:

Quoted 11 lines

compilers can replace 'ptr' with 'head' because of the equality, and even putting barrier() here cannot prevent compiler to rewrite the else branch into:

	else {
		barrier();
		return head;
	}

because that's just using a different register, unrelated to memory accesses.

Yeah, that was the solution I had in mind. My reasoning was that from the C abstract machine, head is still a memory access, and the barrier() should make the compiler forget everything it knew about the value of head from before the barrier().

So I had a gap in my understanding of the strength of barrier(). Can I understand it to mean that the compiler can do escape analysis to reason that a volatile asm code with ::memory can't possibly be manipulating some variables (like head in this case)?

That idea seems to be confirmed by this (atrocious, not to be copied!) example:

int fct_escape_address_of_b(void)

{
    int *a, *b;

    do {
        a = READ_ONCE(p);
        asm volatile ("" : : : "memory");
        b = READ_ONCE(p);
    } while (a != b);

    // really really hide b
    int **p = &b;
    OPTIMIZER_HIDE_VAR(p);

    asm volatile ("" : : : "memory");
    return *b;
}

This also does not generate any additional instructions, unlike just using OPTIMIZER_HIDE_VAR(b).

What is the advantage of defining OPTIMIZE_HIDE_VAR the way it currently works instead of like above?

Quoted 6 lines · Mathieu Desnoyers
Quoted 5 lines

I have a set of examples below that show gcc use the result of the first load, and clang use the result of the second load (on both x86-64 and aarch64). Likewise when a load-acquire is used as second load, which I find odd.

Note that if you use acquire on the second load, the code is correct even if the compiler uses the result of the first load.

That is because the acquire load will still synchronize sufficiently with the second publishing store after the ABA, and then we can get the right data even from the old address.

Best wishes,

jonas

#51 lore raw

Re: [RFC PATCH 1/4] hazptr: Add initial implementation of hazard pointers

On 2024-09-27 21:23, Jonas Oberhauser wrote:
[...]

Quoted 16 lines

That idea seems to be confirmed by this (atrocious, not to be copied!) example:

int fct_escape_address_of_b(void)
{
    int *a, *b;

    do {
        a = READ_ONCE(p);
        asm volatile ("" : : : "memory");
        b = READ_ONCE(p);
    } while (a != b);

    // really really hide b
    int **p = &b;
    OPTIMIZER_HIDE_VAR(p);

Quoted 7 lines

    asm volatile ("" : : : "memory");
    return *b;
}

This also does not generate any additional instructions, unlike just using OPTIMIZER_HIDE_VAR(b).

What is the advantage of defining OPTIMIZE_HIDE_VAR the way it currently works instead of like above?

Did you try it on godbolt.org ? Does it have the intended effect ? By the looks of it, you're just creating another version of @b called "p", which is then never used and would be discarded by further optimization. I'm unsure what you are trying to achieve here.

Thanks,

Mathieu

Signature · 3 lines
Mathieu Desnoyers
EfficiOS Inc.
https://www.efficios.com
#52 lore raw

Re: [RFC PATCH 1/4] hazptr: Add initial implementation of hazard pointers

Am 9/27/2024 um 10:10 PM schrieb Mathieu Desnoyers:

Quoted 22 lines · Jonas Oberhauser

[...]

Quoted 20 lines

That idea seems to be confirmed by this (atrocious, not to be copied!) example:

int fct_escape_address_of_b(void)
{
     int *a, *b;

     do {
         a = READ_ONCE(p);
         asm volatile ("" : : : "memory");
         b = READ_ONCE(p);
     } while (a != b);

     // really really hide b
     int **p = &b;
     OPTIMIZER_HIDE_VAR(p);

     asm volatile ("" : : : "memory");
     return *b;
}

Quoted 5 lines
Quoted 3 lines

This also does not generate any additional instructions, unlike just using OPTIMIZER_HIDE_VAR(b).

What is the advantage of defining OPTIMIZE_HIDE_VAR the way it currently works instead of like above?

Did you try it on godbolt.org ? Does it have the intended effect ?

I certainly did try and certainly read it as having the intended effect, otherwise I wouldn't have written that it seems confirmed.

However, just because my eyes read it doesn't mean that's what happened, and even if it happened doesn't mean that it is guaranteed to happen.

Quoted 4 lines

By the looks of it, you're just creating another version of @b called "p", which is then never used and would be discarded by further optimization. >
I'm unsure what you are trying to achieve here.

Simply put I'm trying to let the compiler think that I leaked the address of b. After that, the memory barrier should let it think that the b after the memory barrier might not be the same as the one before it (which was equal to a), forcing it to read from b.

However, I suppose on second thought that that might not be enough, because the compiler could still simply do b = a right after exiting the while loop.

And that is true no matter what we put behind the while loop or before the condition, as long as the condition compares a and b, right after it the compiler can do b = a. Just took me a while to see :))

I'm not sure why gcc does the b=a with the normal OPTIMIZER_HIDE_VAR but (as far as I read the code) doesn't do it with the above. Maybe just a weird corner case...

Have fun,
jonas

#53 lore raw

Re: [RFC PATCH 1/4] hazptr: Add initial implementation of hazard pointers

2024年9月28日 06:18,Jonas Oberhauser <[email protected]> wrote:

Quoted 40 lines

Am 9/27/2024 um 10:10 PM schrieb Mathieu Desnoyers:

Quoted 18 lines · Jonas Oberhauser

[...]

Quoted 16 lines

That idea seems to be confirmed by this (atrocious, not to be copied!) example:

int fct_escape_address_of_b(void)

{
     int *a, *b;

     do {
         a = READ_ONCE(p);
         asm volatile ("" : : : "memory");
         b = READ_ONCE(p);
     } while (a != b);

     // really really hide b
     int **p = &b;
     OPTIMIZER_HIDE_VAR(p);
Quoted 8 lines
Quoted 7 lines
     asm volatile ("" : : : "memory");
     return *b;
}

This also does not generate any additional instructions, unlike just using OPTIMIZER_HIDE_VAR(b).

What is the advantage of defining OPTIMIZE_HIDE_VAR the way it currently works instead of like above?

Did you try it on godbolt.org ? Does it have the intended effect ?

I certainly did try and certainly read it as having the intended effect, otherwise I wouldn't have written that it seems confirmed.

However, just because my eyes read it doesn't mean that's what happened, and even if it happened doesn't mean that it is guaranteed to happen.

Quoted 4 lines

By the looks of it, you're just creating another version of @b called "p", which is then never used and would be discarded by further optimization. >
I'm unsure what you are trying to achieve here.

Quoted 7 lines

Simply put I'm trying to let the compiler think that I leaked the address of b. After that, the memory barrier should let it think that the b after the memory barrier might not be the same as the one before it (which was equal to a), forcing it to read from b.

However, I suppose on second thought that that might not be enough, because the compiler could still simply do b = a right after exiting the while loop.

And that is true no matter what we put behind the while loop or before the condition, as long as the condition compares a and b, right after it the compiler can do b = a. Just took me a while to see :))

I'm not sure why gcc does the b=a with the normal OPTIMIZER_HIDE_VAR but (as far as I read the code) doesn't do it with the above. Maybe just a weird corner case...

Let the p to be a static variable out of the function will make a difference.

Or the following:

	int **p = &b;
	barrier_data(p);

also works.

BTW, barrier_data(&b) generates more instructions than godbolt when build the kernel.

Quoted 5 lines

Have fun,
jonas

#54 lore raw

Re: [RFC PATCH 1/4] hazptr: Add initial implementation of hazard pointers

2024年9月29日 06:10,Alan Huang <[email protected]> wrote:

Quoted 48 lines

2024年9月28日 06:18,Jonas Oberhauser <[email protected]> wrote:

Quoted 46 lines

Am 9/27/2024 um 10:10 PM schrieb Mathieu Desnoyers:

Quoted 18 lines · Jonas Oberhauser

[...]

Quoted 16 lines

That idea seems to be confirmed by this (atrocious, not to be copied!) example:

int fct_escape_address_of_b(void)

{
    int *a, *b;

    do {
        a = READ_ONCE(p);
        asm volatile ("" : : : "memory");
        b = READ_ONCE(p);
    } while (a != b);

    // really really hide b
    int **p = &b;
    OPTIMIZER_HIDE_VAR(p);
Quoted 8 lines
Quoted 7 lines
    asm volatile ("" : : : "memory");
    return *b;
}

This also does not generate any additional instructions, unlike just using OPTIMIZER_HIDE_VAR(b).

What is the advantage of defining OPTIMIZE_HIDE_VAR the way it currently works instead of like above?

Did you try it on godbolt.org ? Does it have the intended effect ?

I certainly did try and certainly read it as having the intended effect, otherwise I wouldn't have written that it seems confirmed.

However, just because my eyes read it doesn't mean that's what happened, and even if it happened doesn't mean that it is guaranteed to happen.

Quoted 4 lines

By the looks of it, you're just creating another version of @b called "p", which is then never used and would be discarded by further optimization. >
I'm unsure what you are trying to achieve here.

Simply put I'm trying to let the compiler think that I leaked the address of b. After that, the memory barrier should let it think that the b after the memory barrier might not be the same as the one before it (which was equal to a), forcing it to read from b.

However, I suppose on second thought that that might not be enough, because the compiler could still simply do b = a right after exiting the while loop.

And that is true no matter what we put behind the while loop or before the condition, as long as the condition compares a and b, right after it the compiler can do b = a. Just took me a while to see :))

Quoted 8 lines
Quoted 1 line

I'm not sure why gcc does the b=a with the normal OPTIMIZER_HIDE_VAR but (as far as I read the code) doesn't do it with the above. Maybe just a weird corner case...

Let the p to be a static variable out of the function will make a difference.

Or the following:

int **p = &b;
barrier_data(p);

Or the following:

	int **t = &b;
	WRITE_ONCE(t, &b);
	barrier();

return *b;

also works.

Quoted 8 lines

also works.

BTW, barrier_data(&b) generates more instructions than godbolt when build the kernel.

Quoted 3 lines

Have fun,
jonas

#55 lore raw

Re: [RFC PATCH 1/4] hazptr: Add initial implementation of hazard pointers

In reply to Mathieu Desnoyers

Am 9/25/2024 um 1:59 PM schrieb Mathieu Desnoyers:

Quoted 48 lines · Boqun Feng
Quoted 17 lines · Jonas Oberhauser
Quoted 8 lines

Am 9/25/2024 um 12:02 PM schrieb Boqun Feng:

Quoted 4 lines

Hi Jonas,

Of
course, if we are really worried about compilers being too "smart"

Quoted 7 lines

Ah, I see you know me better and better...

Quoted 2 lines

we can always do the comparison in asm code, then compilers don't know anything of the equality between 'ptr' and 'head - head_offset'.

Yes, but then a simple compiler barrier between the comparison and returning ptr would also do the trick, right? And maybe easier on the eyes.

Quoted 9 lines

The thing about putting a compiler barrier is that it will prevent all compiler reorderings, and some of the reordering may contribute to better codegen. (I know in this case, we have a smp_mb(), but still compilers can move unrelated code upto the second load for optimization purpose). Asm comparison is cheaper in this way. But TBH, compilers should provide a way to compare pointer values without using the result for pointer equality proof, if "convert to unsigned long" doesn't work, some other ways should work.

Based on Documentation/RCU/rcu_dereference.rst :

-       Be very careful about comparing pointers obtained from
        rcu_dereference() against non-NULL values.  As Linus Torvalds explained, if the two pointers are equal, the compiler could substitute the pointer you are comparing against for the pointer obtained from rcu_dereference().  For example::

                p = rcu_dereference(gp);
                if (p == &default_struct)
                        do_default(p->a);

        Because the compiler now knows that the value of "p" is exactly the address of the variable "default_struct", it is free to transform this code into the following::

                p = rcu_dereference(gp);
                if (p == &default_struct) do_default(default_struct.a);

Quoted 7 lines

        On ARM and Power hardware, the load from "default_struct.a" can now be speculated, such that it might happen before the rcu_dereference().  This could result in bugs due to misordering.

So I am not only concerned about compiler proofs here, as it appears that the speculation done by the CPU can also cause issues on some architectures.

No, this is only possible in this example because of the compiler first doing some other optimizations (like what I mentioned on Boqun's original patch).

If you can ensure that the instruction sequence corresponds to more or less

t = load p // again
// on alpha: dep fence
...

*t

then you can be sure that there is an address dependency which orders the access. This is guaranteed by LKMM, or if you don't trust LKMM, also by Arm, Power, Alpha etc.

The extra dep fence on alpha is automatically inserted if you use READ_ONCE as boqun did (and I assumed your uatomic_load or whatever is doing the same thing, but I didn't check).

Given that the hazard-pointer-protected object presumably is not a single static non-freeable object, but some dynamically allocated object, it is pretty much impossible for the compiler to guess the address like in the example you shared above.

Note that inside the if, the code after transform is do_default(default_struct.a); which is an address that is known to the hardware before it loads from gp.

That would not be the case here (if the compiler optimization is ruled out).

jonas

author
#56 lore raw

RFC PATCH 2/4 refscale: Add benchmarks for hazptr

In reply to Boqun Feng

Benchmarks for hazptr are added to evaluate the reader side performance between hazptr and other refcounting mechanisms.

---
 kernel/rcu/refscale.c | 79 ++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 78 insertions(+), 1 deletion(-)
kernel/rcu/refscale.c +78 -1
index f4ea5b1ec068..7e76ae5159e6 100644
@@ -35,6 +35,7 @@
 #include <linux/slab.h>
 #include <linux/torture.h>
 #include <linux/types.h>
+#include <linux/hazptr.h>
 
 #include "rcu.h"
 
@@ -316,6 +317,82 @@ static struct ref_scale_ops refcnt_ops = {
 	.name		= "refcnt"
 };
 
+struct hazptr_data {
+	struct callback_head head;
+	int i;
+};
+
+static struct hazptr_data *hazptr_data;
+
+static bool hazptr_scale_init(void)
+{
+	hazptr_data = kmalloc(sizeof(*hazptr_data), GFP_KERNEL);
+
+	return !!hazptr_data;
+}
+
+static void free_hazptr_data(struct callback_head *head)
+{
+	struct hazptr_data *tofree = container_of(head, struct hazptr_data, head);
+
+	kfree(tofree);
+}
+
+static void hazptr_scale_cleanup(void)
+{
+	if (hazptr_data) {
+		struct hazptr_data *tmp = hazptr_data;
+		WRITE_ONCE(hazptr_data, NULL);
+
+		call_hazptr(&tmp->head, free_hazptr_data);
+	}
+}
+
+static void hazptr_section(const int nloops)
+{
+	int i;
+	struct hazptr_context ctx;
+	hazptr_t *hzptr;
+
+	init_hazptr_context(&ctx);
+	hzptr = hazptr_alloc(&ctx);
+
+	for (i = nloops; i >= 0; i--) {
+		BUG_ON(!hazptr_protect(hzptr, hazptr_data, head));
+		hazptr_clear(hzptr);
+	}
+
+	hazptr_free(&ctx, hzptr);
+	cleanup_hazptr_context(&ctx);
+}
+
+static void hazptr_delay_section(const int nloops, const int udl, const int ndl)
+{
+	int i;
+	struct hazptr_context ctx;
+	hazptr_t *hzptr;
+
+	init_hazptr_context(&ctx);
+	hzptr = hazptr_alloc(&ctx);
+
+	for (i = nloops; i >= 0; i--) {
+		BUG_ON(!hazptr_protect(hzptr, hazptr_data, head));
+		un_delay(udl, ndl);
+		hazptr_clear(hzptr);
+	}
+
+	hazptr_free(&ctx, hzptr);
+	cleanup_hazptr_context(&ctx);
+}
+
+static struct ref_scale_ops hazptr_ops = {
+	.init		= hazptr_scale_init,
+	.cleanup	= hazptr_scale_cleanup,
+	.readsection	= hazptr_section,
+	.delaysection	= hazptr_delay_section,
+	.name		= "hazptr"
+};
+
 // Definitions for rwlock
 static rwlock_t test_rwlock;
 
@@ -1081,7 +1158,7 @@ ref_scale_init(void)
 	static struct ref_scale_ops *scale_ops[] = {
 		&rcu_ops, &srcu_ops, RCU_TRACE_OPS RCU_TASKS_OPS &refcnt_ops, &rwlock_ops,
 		&rwsem_ops, &lock_ops, &lock_irq_ops, &acqrel_ops, &clock_ops, &jiffies_ops,
-		&typesafe_ref_ops, &typesafe_lock_ops, &typesafe_seqlock_ops,
+		&typesafe_ref_ops, &typesafe_lock_ops, &typesafe_seqlock_ops, &hazptr_ops,
 	};
 
 	if (!torture_init_begin(scale_type, verbose))
Signature · 1 line
2.45.2
author
#57 lore raw

RFC PATCH 3/4 refscale: Add benchmarks for percpu_ref

In reply to Boqun Feng

Benchmarks for percpu_ref are added to evaluate the reader side performance between percpu_ref and other refcounting mechanisms.

---
 kernel/rcu/refscale.c | 50 ++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 49 insertions(+), 1 deletion(-)
kernel/rcu/refscale.c +49 -1
index 7e76ae5159e6..97b73c980c5d 100644
@@ -393,6 +393,54 @@ static struct ref_scale_ops hazptr_ops = {
 	.name		= "hazptr"
 };
 
+struct percpu_ref percpu_ref;
+
+static void percpu_ref_dummy(struct percpu_ref *ref) {}
+
+static bool percpu_ref_scale_init(void)
+{
+	int ret;
+
+	ret = percpu_ref_init(&percpu_ref, percpu_ref_dummy, PERCPU_REF_INIT_ATOMIC, GFP_KERNEL);
+	percpu_ref_switch_to_percpu(&percpu_ref);
+
+	return !ret;
+}
+
+static void percpu_ref_scale_cleanup(void)
+{
+	percpu_ref_exit(&percpu_ref);
+}
+
+static void percpu_ref_section(const int nloops)
+{
+	int i;
+
+	for (i = nloops; i >= 0; i--) {
+		percpu_ref_get(&percpu_ref);
+		percpu_ref_put(&percpu_ref);
+	}
+}
+
+static void percpu_ref_delay_section(const int nloops, const int udl, const int ndl)
+{
+	int i;
+
+	for (i = nloops; i >= 0; i--) {
+		percpu_ref_get(&percpu_ref);
+		un_delay(udl, ndl);
+		percpu_ref_put(&percpu_ref);
+	}
+}
+
+static struct ref_scale_ops percpu_ref_ops = {
+	.init		= percpu_ref_scale_init,
+	.cleanup	= percpu_ref_scale_cleanup,
+	.readsection	= percpu_ref_section,
+	.delaysection	= percpu_ref_delay_section,
+	.name		= "percpu_ref"
+};
+
 // Definitions for rwlock
 static rwlock_t test_rwlock;
 
@@ -1158,7 +1206,7 @@ ref_scale_init(void)
 	static struct ref_scale_ops *scale_ops[] = {
 		&rcu_ops, &srcu_ops, RCU_TRACE_OPS RCU_TASKS_OPS &refcnt_ops, &rwlock_ops,
 		&rwsem_ops, &lock_ops, &lock_irq_ops, &acqrel_ops, &clock_ops, &jiffies_ops,
-		&typesafe_ref_ops, &typesafe_lock_ops, &typesafe_seqlock_ops, &hazptr_ops,
+		&typesafe_ref_ops, &typesafe_lock_ops, &typesafe_seqlock_ops, &hazptr_ops, &percpu_ref_ops,
 	};
 
 	if (!torture_init_begin(scale_type, verbose))
Signature · 1 line
2.45.2
author
#58 lore raw

RFC PATCH 4/4 WIP: hazptr: Add hazptr test sample

In reply to Boqun Feng

Sample code for hazptr. This should go away or get more polished when hazptr support is added into rcutorture.

---
 samples/Kconfig              |  6 +++
 samples/Makefile             |  1 +
 samples/hazptr/hazptr_test.c | 87 ++++++++++++++++++++++++++++++++++++
 3 files changed, 94 insertions(+)
 create mode 100644 samples/hazptr/hazptr_test.c
samples/Kconfig +6 -0
index b288d9991d27..9b42cde35dca 100644
@@ -293,6 +293,12 @@ config SAMPLE_CGROUP
 
 source "samples/rust/Kconfig"
 
+config SAMPLE_HAZPTR
+	bool "Build hazptr sample code"
+	help
+	  Build samples that shows hazard pointer usage. Currently only
+	  builtin usage is supported.
+
 endif # SAMPLES
 
 config HAVE_SAMPLE_FTRACE_DIRECT
samples/Makefile +1 -0
index b85fa64390c5..0be21edc8a30 100644
@@ -39,3 +39,4 @@ obj-$(CONFIG_SAMPLE_KMEMLEAK)		+= kmemleak/
 obj-$(CONFIG_SAMPLE_CORESIGHT_SYSCFG)	+= coresight/
 obj-$(CONFIG_SAMPLE_FPROBE)		+= fprobe/
 obj-$(CONFIG_SAMPLES_RUST)		+= rust/
+obj-$(CONFIG_SAMPLE_HAZPTR)		+= hazptr/
samples/hazptr/hazptr_test.c new file +87 -0

87 lines not on this page · raw message

Signature · 1 line
2.45.2
#59 lore raw

Re: [RFC PATCH 4/4] WIP: hazptr: Add hazptr test sample

kernel test robot noticed the following build errors:

Hi Boqun,

[This is a private test report for your RFC patch.] kernel test robot noticed the following build errors:

[auto build test ERROR on linus/master]
[also build test ERROR on v6.11 next-20240917]
[cannot apply to paulmck-rcu/dev]
[If your patch is applied to the wrong git tree, kindly drop us a note. And when submitting patch, we suggest to use '--base' as documented in
https://git-scm.com/docs/git-format-patch#_base_tree_information]

url:    https://github.com/intel-lab-lkp/linux/commits/Boqun-Feng/hazptr-Add-initial-implementation-of-hazard-pointers/20240917-223604
base:   linus/master
patch link:    https://lore.kernel.org/r/20240917143402.930114-5-boqun.feng%40gmail.com
patch subject: [RFC PATCH 4/4] WIP: hazptr: Add hazptr test sample
reproduce: (https://download.01.org/0day-ci/archive/20240918/[email protected]/reproduce)

If you fix the issue in a separate patch/commit (i.e. not just a new version of the same patch/commit), kindly add following tags
| Reported-by: kernel test robot <[email protected]>
| Closes: https://lore.kernel.org/oe-kbuild-all/[email protected]/

All errors (new ones prefixed by >>):

>> scripts/Makefile.clean:12: samples/hazptr/Makefile: No such file or directory
>> make[4]: *** No rule to make target 'samples/hazptr/Makefile'.

scripts/Makefile.clean:12: Failed to remake makefile 'samples/hazptr/Makefile'. make[3]: *** [scripts/Makefile.clean:61: samples/hazptr] Error 2 make[3]: Target '__clean' not remade because of errors.
make[2]: *** [scripts/Makefile.clean:61: samples] Error 2
make[2]: Target '__clean' not remade because of errors.

vim +12 scripts/Makefile.clean

^1da177e4c3f41 Linus Torvalds  2005-04-16   7  
4f1933620f5714 Paul Smith      2006-03-05   8  PHONY := __clean
^1da177e4c3f41 Linus Torvalds  2005-04-16   9  __clean:
^1da177e4c3f41 Linus Torvalds  2005-04-16  10  

3204a7fb98a3bc Masahiro Yamada 2021-02-28 11 include $(srctree)/scripts/Kbuild.include a2430b25c31840 Masahiro Yamada 2022-11-19 @12 include $(kbuild-file) ^1da177e4c3f41 Linus Torvalds 2005-04-16 13

Signature · 2 lines
0-DAY CI Kernel Test Service
https://github.com/intel/lkp-tests/wiki
#60 lore raw
In reply to Boqun Feng
Quoted 4 lines · Boqun Feng

This series introduces hazard pointers [1] to kernel space. A TL;DR description of hazard pointers is "a scalable refcounting mechanim with RCU-like API". More information can be found at [2].

Please give actual "this is useful for X, and here is an actual real load with numbers showing why it matters".

We don't just merge random infrastructure without a use-case and an argument for it.

Linus

#61 lore raw
Quoted 9 lines · Linus Torvalds
Quoted 4 lines · Boqun Feng

This series introduces hazard pointers [1] to kernel space. A TL;DR description of hazard pointers is "a scalable refcounting mechanim with RCU-like API". More information can be found at [2].

Please give actual "this is useful for X, and here is an actual real load with numbers showing why it matters".

One of the use case where we had seen improvement is - Nginx web server throughput scalability with AppArmor enabled. For this use case we see refcount scalability problem when kref operations are done for AppArmor label object in Nginx worker's context. More details about this are captured @ [1] [2].

When we switch from kref to hazard pointer in apparmor_file_open(), we see ~7% improvement in Nginx throughput for this use case.

While we were working on this problem, this refcount scalability issue got resolved recently with conditional ref acquisition [3] (however, there are new developments in apparmor code which might bring back the refcount problem [4]).

[1] https://lore.kernel.org/lkml/[email protected]/T/
[2] https://lore.kernel.org/lkml/[email protected]/
[3] https://lore.kernel.org/lkml/[email protected]/
[4] https://lore.kernel.org/lkml/[email protected]/

- Neeraj

Quoted 4 lines

We don't just merge random infrastructure without a use-case and an argument for it.

Linus

#62 lore raw
Quoted 4 lines · Neeraj Upadhyay

While we were working on this problem, this refcount scalability issue got resolved recently with conditional ref acquisition [3] (however, there are new developments in apparmor code which might bring back the refcount problem [4]).

Honestly, the various security layers should be a whole lot more careful about their horrid performance issues, and I think that [4] you point at needs to just be headed off at the pass.

No more "the security layer is so bad at performance that we have to introduce new ref mechanisms", please. Let's push back on bad security layer code instead.

Linus

#63 lore raw
Quoted 6 lines · Linus Torvalds
Quoted 4 lines · Neeraj Upadhyay

While we were working on this problem, this refcount scalability issue got resolved recently with conditional ref acquisition [3] (however, there are new developments in apparmor code which might bring back the refcount problem [4]).

Quoted 8 lines

Honestly, the various security layers should be a whole lot more careful about their horrid performance issues, and I think that [4] you point at needs to just be headed off at the pass.

No more "the security layer is so bad at performance that we have to introduce new ref mechanisms", please. Let's push back on bad security layer code instead.

Ok got it. Thanks for your feedback! I had tried using percpu refcount first (in place of kref) in AppArmor. However, that required managing the last reference drop (implemented in [1] and [2]). Mateusz has shared some ideas in his reply to this thread. Maybe that is a workable solution. Will defer to John on this as I have limited understanding of the cred management code.

- Neeraj

Quoted 1 line

Linus

#64 lore raw
In reply to Neeraj Upadhyay
Quoted 17 lines · Neeraj Upadhyay
Quoted 9 lines · Linus Torvalds
Quoted 4 lines · Boqun Feng

This series introduces hazard pointers [1] to kernel space. A TL;DR description of hazard pointers is "a scalable refcounting mechanim with RCU-like API". More information can be found at [2].

Please give actual "this is useful for X, and here is an actual real load with numbers showing why it matters".

One of the use case where we had seen improvement is - Nginx web server throughput scalability with AppArmor enabled. For this use case we see refcount scalability problem when kref operations are done for AppArmor label object in Nginx worker's context. More details about this are captured @ [1] [2].

Quoted 7 lines

When we switch from kref to hazard pointer in apparmor_file_open(), we see ~7% improvement in Nginx throughput for this use case.

While we were working on this problem, this refcount scalability issue got resolved recently with conditional ref acquisition [3] (however, there are new developments in apparmor code which might bring back the refcount problem [4]).

The open/close thing is still serializing across different processes, the slowdown just got lower. As in apparmor *as is* continues to be a problem at big enough scale.

Per my messages in the area in the past, I'm confident this is fixable with changing the refcount model to cache ref changes per-thread. I employed this very scheme $elsewhere.

Since equivalent mechanism is applicable to creds this may want to be implemented as something under lib/. I even started to work on it for Linux, but real life got in the way and then I could not be arsed to finish.

It is a little reminiscenet of per-cpu refs. Here is the outline again:

kref usage gets replaced with a touple of { kref users; s64 refs; }

task_struct grows a pointer to the cached label and refs counter on it

when a new thread is created it bumps users and stores the pointer. on destruction it decrements users and rolls up the local changes. Similarly, if it turns out the label has to change during thread's lifetime, the same thing happens.

In pseudo-code for apparmor_file_open():

	if (unlikely(current->aa_cached_label != check_label())) {
		/* do a replacement here */
	}
	/* just bump the local counter, no synchronisation with other
	 * cpus in the common case */
	current->aa_cached_label_refs++;

In apparmor_file_close():

	/* common case fast path */
	if (file->aa_label == current->aa_cached_label) {
		current->aa_cached_label_refs--;
		return;
	}
	/* we get here if apparmor got reconfigured or this is a file we
	 * inherited from another proc which had a different label and
	 * this is the last fput */
	kref_put(file->aa_label);

Conceptually there is almost nothing to see here.

As outlined above stale labels would clear themselves out as threads open files. However, a thread which stubborly refuses to call allocate a new file obj may hold on to a stale label indefinitely.

One way to sort it out:
I presume there is a spot somewhere in user<->kernel transition handling which updates the credentials pointer, should it have changed.

$elsewhere I patched it up with a "cow" generation counter. If not matching with the real task struct you know you need to take the fast path and check creds, apparmor and whatever else. No extra branches in the fast path, but a new int does have to be read. Given that task_struct is a little bit of a cluster fuck I don't think it's a problem.

That would be a rough sketch, anyone interested can fill in the details. This still performs serializing atomics in *certain* cases, but avoids them in almost all cases and there is nothing complicated about this that I see, just some effort to implement.

So I don't believe patching up RCU with hazard pointers is warranted if apparmor is the only justification.

Anyway no ETA from my end, anyone interested is free to take the idea or do better.

#65 lore raw
In reply to Linus Torvalds
Quoted 8 lines · Linus Torvalds
Quoted 4 lines · Boqun Feng

This series introduces hazard pointers [1] to kernel space. A TL;DR description of hazard pointers is "a scalable refcounting mechanim with RCU-like API". More information can be found at [2].

Please give actual "this is useful for X, and here is an actual real load with numbers showing why it matters".

Agreed. From the description this would seem like a good fit for q_usage_counter in the block layer, which currently makes creative use of percpu counters.

#66 lore raw
Quoted 4 lines · Christoph Hellwig

Agreed. From the description this would seem like a good fit for q_usage_counter in the block layer, which currently makes creative use of percpu counters.

Yes, if this actually could simplify code that currently used percpu counters, that might be lovely.

The percpu counters often perform very well, but then have huge pain in either managing the percpu allocation, or in trying to synchronize across CPU's.

I'd be a lot more interested in "we can fix complex code" than in "we have crappy code in bad subsystems where we can hide the performance impact of the subsystem not having been done right".

Linus