Skip to contentSkip to conversation

kprobes: Make kretprobes lockless

RFC PATCH In review Peter Zijlstra 7 participants 38 messages Aug 27, 2020 – Aug 29, 2020 1 message not in the archive

Subsystems (9)
DRM drivers x86 Intel i915 MM core +5 more subsystems
lore
Share & tools
lore
author maintainer
#17 lore raw

RFC PATCH 4/7 kprobe: Dont kfree() from breakpoint context

In reply to Peter Zijlstra

Breakpoint context might not be a safe context for kfree(), push it out to RCU.

---
 include/linux/kprobes.h |    2 +-
 kernel/kprobes.c        |   27 ++++++---------------------
 2 files changed, 7 insertions(+), 22 deletions(-)
include/linux/kprobes.h +1 -1
@@ -159,6 +159,7 @@ struct kretprobe_instance {
 	union {
 		struct llist_node llist;
 		struct hlist_node hlist;
+		struct rcu_head rcu;
 	};
 	struct kretprobe *rp;
 	kprobe_opcode_t *ret_addr;
@@ -398,7 +399,6 @@ int register_kretprobes(struct kretprobe
 void unregister_kretprobes(struct kretprobe **rps, int num);
 
 void kprobe_flush_task(struct task_struct *tk);
-void recycle_rp_inst(struct kretprobe_instance *ri, struct hlist_head *head);
 
 int disable_kprobe(struct kprobe *kp);
 int enable_kprobe(struct kprobe *kp);
kernel/kprobes.c +6 -21
@@ -1214,8 +1214,7 @@ void kprobes_inc_nmissed_count(struct kp
 }
 NOKPROBE_SYMBOL(kprobes_inc_nmissed_count);
 
-void recycle_rp_inst(struct kretprobe_instance *ri,
-		     struct hlist_head *head)
+static void recycle_rp_inst(struct kretprobe_instance *ri)
 {
 	struct kretprobe *rp = ri->rp;
 
@@ -1226,9 +1225,9 @@ void recycle_rp_inst(struct kretprobe_in
 		raw_spin_lock(&rp->lock);
 		hlist_add_head(&ri->hlist, &rp->free_instances);
 		raw_spin_unlock(&rp->lock);
-	} else
-		/* Unregistering */
-		hlist_add_head(&ri->hlist, head);
+	} else {
+		kfree_rcu(ri, rcu);
+	}
 }
 NOKPROBE_SYMBOL(recycle_rp_inst);
 
@@ -1261,15 +1260,12 @@ void kprobe_busy_end(void)
 void kprobe_flush_task(struct task_struct *tk)
 {
 	struct kretprobe_instance *ri;
-	struct hlist_head empty_rp;
 	struct llist_node *node;
-	struct hlist_node *tmp;
 
 	/* Early boot, not yet initialized. */
 	if (unlikely(!kprobes_initialized))
 		return;
 
-	INIT_HLIST_HEAD(&empty_rp);
 
 	kprobe_busy_begin();
 
@@ -1280,12 +1276,7 @@ void kprobe_flush_task(struct task_struc
 		ri = container_of(node, struct kretprobe_instance, llist);
 		node = node->next;
 
-		recycle_rp_inst(ri, &empty_rp);
-	}
-
-	hlist_for_each_entry_safe(ri, tmp, &empty_rp, hlist) {
-		hlist_del(&ri->hlist);
-		kfree(ri);
+		recycle_rp_inst(ri);
 	}
 
 	kprobe_busy_end();
@@ -1937,7 +1928,6 @@ unsigned long __kretprobe_trampoline_han
 	unsigned long orig_ret_address = 0;
 	struct llist_node *first, *node;
 	struct hlist_head empty_rp;
-	struct hlist_node *tmp;
 
 	INIT_HLIST_HEAD(&empty_rp);
 
@@ -1980,16 +1970,11 @@ unsigned long __kretprobe_trampoline_han
 			__this_cpu_write(current_kprobe, &kprobe_busy);
 		}
 
-		recycle_rp_inst(ri, &empty_rp);
+		recycle_rp_inst(ri);
 
 		first = node;
 	}
 
-	hlist_for_each_entry_safe(ri, tmp, &empty_rp, hlist) {
-		hlist_del(&ri->hlist);
-		kfree(ri);
-	}
-
 	return orig_ret_address;
 }
 NOKPROBE_SYMBOL(__kretprobe_trampoline_handler)
author maintainer
#1 lore raw

RFC PATCH 1/7 llist: Add nonatomic __llist_add()

In reply to Peter Zijlstra
---
 drivers/gpu/drm/i915/i915_request.c |    6 ------
 include/linux/llist.h               |   15 +++++++++++++++
 2 files changed, 15 insertions(+), 6 deletions(-)
drivers/gpu/drm/i915/i915_request.c +0 -6
@@ -357,12 +357,6 @@ void i915_request_retire_upto(struct i91
 	} while (i915_request_retire(tmp) && tmp != rq);
 }
 
-static void __llist_add(struct llist_node *node, struct llist_head *head)
-{
-	node->next = head->first;
-	head->first = node;
-}
-
 static struct i915_request * const *
 __engine_active(struct intel_engine_cs *engine)
 {
include/linux/llist.h +15 -0
@@ -197,6 +197,16 @@ static inline struct llist_node *llist_n
 extern bool llist_add_batch(struct llist_node *new_first,
 			    struct llist_node *new_last,
 			    struct llist_head *head);
+
+static inline bool __llist_add_batch(struct llist_node *new_first,
+				     struct llist_node *new_last,
+				     struct llist_head *head)
+{
+	new_last->next = head->first;
+	head->first = new_first;
+	return new_last->next == NULL;
+}
+
 /**
  * llist_add - add a new entry
  * @new:	new entry to be added
@@ -209,6 +219,11 @@ static inline bool llist_add(struct llis
 	return llist_add_batch(new, new, head);
 }
 
+static inline bool __llist_add(struct llist_node *new, struct llist_head *head)
+{
+	return __llist_add_batch(new, new, head);
+}
+
 /**
  * llist_del_all - delete all entries from lock-less list
  * @head:	the head of lock-less list to delete all entries
author maintainer
#19 lore raw

RFC PATCH 6/7 freelist: Lock less freelist

In reply to Peter Zijlstra
---
 include/linux/freelist.h |  129 +++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 129 insertions(+)
include/linux/freelist.h new file +129 -0
@@ -0,0 +1,129 @@
+// SPDX-License-Identifier: GPL-2.0-only OR BSD-2-Clause
+#ifndef FREELIST_H
+#define FREELIST_H
+
+#include <linux/atomic.h>
+
+/*
+ * Copyright: [email protected]
+ *
+ * A simple CAS-based lock-free free list. Not the fastest thing in the world
+ * under heavy contention, but simple and correct (assuming nodes are never
+ * freed until after the free list is destroyed), and fairly speedy under low
+ * contention.
+ *
+ * Adapted from: https://moodycamel.com/blog/2014/solving-the-aba-problem-for-lock-free-free-lists
+ */
+
+struct freelist_node {
+	atomic_t		refs;
+	struct freelist_node	*next;
+};
+
+struct freelist_head {
+	struct freelist_node	*head;
+};
+
+#define REFS_ON_FREELIST 0x80000000
+#define REFS_MASK	 0x7FFFFFFF
+
+static inline void __freelist_add(struct freelist_node *node, struct freelist_head *list)
+{
+	/*
+	 * Since the refcount is zero, and nobody can increase it once it's
+	 * zero (except us, and we run only one copy of this method per node at
+	 * a time, i.e. the single thread case), then we know we can safely
+	 * change the next pointer of the node; however, once the refcount is
+	 * back above zero, then other threads could increase it (happens under
+	 * heavy contention, when the refcount goes to zero in between a load
+	 * and a refcount increment of a node in try_get, then back up to
+	 * something non-zero, then the refcount increment is done by the other
+	 * thread) -- so if the CAS to add the node to the actual list fails,
+	 * decrese the refcount and leave the add operation to the next thread
+	 * who puts the refcount back to zero (which could be us, hence the
+	 * loop).
+	 */
+	struct freelist_node *head = READ_ONCE(list->head);
+
+	for (;;) {
+		WRITE_ONCE(node->next, head);
+		atomic_set_release(&node->refs, 1);
+
+		if (!try_cmpxchg_release(&list->head, &head, node)) {
+			/*
+			 * Hmm, the add failed, but we can only try again when
+			 * the refcount goes back to zero.
+			 */
+			if (atomic_fetch_add_release(REFS_ON_FREELIST - 1, &node->refs) == 1)
+				continue;
+		}
+		return;
+	}
+}
+
+static inline void freelist_add(struct freelist_node *node, struct freelist_head *list)
+{
+	/*
+	 * We know that the should-be-on-freelist bit is 0 at this point, so
+	 * it's safe to set it using a fetch_add.
+	 */
+	if (!atomic_fetch_add_release(REFS_ON_FREELIST, &node->refs)) {
+		/*
+		 * Oh look! We were the last ones referencing this node, and we
+		 * know we want to add it to the free list, so let's do it!
+		 */
+		__freelist_add(node, list);
+	}
+}
+
+static inline struct freelist_node *freelist_try_get(struct freelist_head *list)
+{
+	struct freelist_node *prev, *next, *head = smp_load_acquire(&list->head);
+	unsigned int refs;
+
+	while (head) {
+		prev = head;
+		refs = atomic_read(&head->refs);
+		if ((refs & REFS_MASK) == 0 ||
+		    !atomic_try_cmpxchg_acquire(&head->refs, &refs, refs+1)) {
+			head = smp_load_acquire(&list->head);
+			continue;
+		}
+
+		/*
+		 * Good, reference count has been incremented (it wasn't at
+		 * zero), which means we can read the next and not worry about
+		 * it changing between now and the time we do the CAS.
+		 */
+		next = READ_ONCE(head->next);
+		if (try_cmpxchg_acquire(&list->head, &head, next)) {
+			/*
+			 * Yay, got the node. This means it was on the list,
+			 * which means should-be-on-freelist must be false no
+			 * matter the refcount (because nobody else knows it's
+			 * been taken off yet, it can't have been put back on).
+			 */
+			WARN_ON_ONCE(atomic_read(&head->refs) & REFS_ON_FREELIST);
+
+			/*
+			 * Decrease refcount twice, once for our ref, and once
+			 * for the list's ref.
+			 */
+			atomic_fetch_add(-2, &head->refs);
+
+			return head;
+		}
+
+		/*
+		 * OK, the head must have changed on us, but we still need to decrement
+		 * the refcount we increased.
+		 */
+		refs = atomic_fetch_add(-1, &prev->refs);
+		if (refs == REFS_ON_FREELIST + 1)
+			__freelist_add(prev, list);
+	}
+
+	return NULL;
+}
+
+#endif /* FREELIST_H */
author maintainer
#2 lore raw

RFC PATCH 2/7 sched: Fix try_invoke_on_locked_down_task() semantics

In reply to Peter Zijlstra
---
 kernel/sched/core.c |    9 ++++-----
 1 file changed, 4 insertions(+), 5 deletions(-)
kernel/sched/core.c +4 -5
@@ -3006,15 +3006,14 @@ try_to_wake_up(struct task_struct *p, un
  */
 bool try_invoke_on_locked_down_task(struct task_struct *p, bool (*func)(struct task_struct *t, void *arg), void *arg)
 {
-	bool ret = false;
 	struct rq_flags rf;
+	bool ret = false;
 	struct rq *rq;
 
-	lockdep_assert_irqs_enabled();
-	raw_spin_lock_irq(&p->pi_lock);
+	raw_spin_lock_irqsave(&p->pi_lock, rf.flags);
 	if (p->on_rq) {
 		rq = __task_rq_lock(p, &rf);
-		if (task_rq(p) == rq)
+		if (task_rq(p) == rq && rq->curr != p)
 			ret = func(p, arg);
 		rq_unlock(rq, &rf);
 	} else {
@@ -3028,7 +3027,7 @@ bool try_invoke_on_locked_down_task(stru
 				ret = func(p, arg);
 		}
 	}
-	raw_spin_unlock_irq(&p->pi_lock);
+	raw_spin_unlock_irqrestore(&p->pi_lock, rf.flags);
 	return ret;
 }
 
author maintainer
#31 lore raw

RFC PATCH 7/7 kprobes: Replace rp->free_instance with freelist

In reply to Peter Zijlstra

Gets rid of rp->lock, and as a result kretprobes are now fully lockless.

---
 include/linux/kprobes.h |   11 ++++++--
 kernel/kprobes.c        |   63 +++++++++++++++++++-----------------------------
 2 files changed, 34 insertions(+), 40 deletions(-)
include/linux/kprobes.h +8 -3
@@ -27,6 +27,7 @@
 #include <linux/rcupdate.h>
 #include <linux/mutex.h>
 #include <linux/ftrace.h>
+#include <linux/freelist.h>
 #include <asm/kprobes.h>
 
 #ifdef CONFIG_KPROBES
@@ -151,14 +152,18 @@ struct kretprobe {
 	int maxactive;
 	int nmissed;
 	size_t data_size;
-	struct hlist_head free_instances;
-	raw_spinlock_t lock;
+	struct freelist_head freelist;
 };
 
 struct kretprobe_instance {
 	union {
+		/*
+		 * Dodgy as heck, this relies on not clobbering freelist::refs.
+		 * llist: only clobbers freelist::next.
+		 * rcu: clobbers both, but only after rp::freelist is gone.
+		 */
+		struct freelist_node freelist;
 		struct llist_node llist;
-		struct hlist_node hlist;
 		struct rcu_head rcu;
 	};
 	struct kretprobe *rp;
kernel/kprobes.c +26 -37

100 lines not on this page · raw message

author maintainer
#3 lore raw

RFC PATCH 3/7 kprobes: Remove kretprobe hash

In reply to Peter Zijlstra

The kretprobe hash is mostly superfluous, replace it with a per-task variable.

This gets rid of the task hash and it's related locking.

The whole invalidate_rp_inst() is tedious and could go away once we drop rp specific ri size.

---
 include/linux/kprobes.h |    5 -
 include/linux/sched.h   |    4 
 kernel/fork.c           |    4 
 kernel/kprobes.c        |  239 +++++++++++++++++++-----------------------------
 4 files changed, 110 insertions(+), 142 deletions(-)
include/linux/kprobes.h +4 -1
@@ -156,7 +156,10 @@ struct kretprobe {
 };
 
 struct kretprobe_instance {
-	struct hlist_node hlist;
+	union {
+		struct llist_node llist;
+		struct hlist_node hlist;
+	};
 	struct kretprobe *rp;
 	kprobe_opcode_t *ret_addr;
 	struct task_struct *task;
include/linux/sched.h +4 -0
@@ -1315,6 +1315,10 @@ struct task_struct {
 	struct callback_head		mce_kill_me;
 #endif
 
+#ifdef CONFIG_KRETPROBES
+	struct llist_head               kretprobe_instances;
+#endif
+
 	/*
 	 * New fields for task_struct should be added above here, so that
 	 * they are included in the randomized portion of task_struct.
kernel/fork.c +4 -0
@@ -2161,6 +2161,10 @@ static __latent_entropy struct task_stru
 	INIT_LIST_HEAD(&p->thread_group);
 	p->task_works = NULL;
 
+#ifdef CONFIG_KRETPROBES
+	p->kretprobe_instances.first = NULL;
+#endif
+
 	/*
 	 * Ensure that the cgroup subsystem policies allow the new process to be
 	 * forked. It should be noted the the new process's css_set can be changed
kernel/kprobes.c +98 -141

333 lines not on this page · raw message

author maintainer
#18 lore raw

RFC PATCH 5/7 asm-generic/atomic: Add try_cmpxchg() fallbacks

In reply to Peter Zijlstra

Only x86 provides try_cmpxchg() outside of the atomic_t interfaces, provide generic fallbacks to create this interface from the widely available cmpxchg() function.

---
 arch/x86/include/asm/atomic.h             |    2 
 arch/x86/include/asm/atomic64_64.h        |    2 
 arch/x86/include/asm/cmpxchg.h            |    2 
 include/asm-generic/atomic-instrumented.h |  216 ++++++++++++++++++------------
 include/linux/atomic-arch-fallback.h      |   90 +++++++++++-
 include/linux/atomic-fallback.h           |   90 +++++++++++-
 scripts/atomic/gen-atomic-fallback.sh     |   63 +++++++-
 scripts/atomic/gen-atomic-instrumented.sh |   29 +++-
 8 files changed, 372 insertions(+), 122 deletions(-)
arch/x86/include/asm/atomic.h +1 -1
@@ -199,7 +199,7 @@ static __always_inline int arch_atomic_c
 
 static __always_inline bool arch_atomic_try_cmpxchg(atomic_t *v, int *old, int new)
 {
-	return try_cmpxchg(&v->counter, old, new);
+	return arch_try_cmpxchg(&v->counter, old, new);
 }
 #define arch_atomic_try_cmpxchg arch_atomic_try_cmpxchg
 
arch/x86/include/asm/atomic64_64.h +1 -1
@@ -187,7 +187,7 @@ static inline s64 arch_atomic64_cmpxchg(
 
 static __always_inline bool arch_atomic64_try_cmpxchg(atomic64_t *v, s64 *old, s64 new)
 {
-	return try_cmpxchg(&v->counter, old, new);
+	return arch_try_cmpxchg(&v->counter, old, new);
 }
 #define arch_atomic64_try_cmpxchg arch_atomic64_try_cmpxchg
 
arch/x86/include/asm/cmpxchg.h +1 -1
@@ -221,7 +221,7 @@ extern void __add_wrong_size(void)
 #define __try_cmpxchg(ptr, pold, new, size)				\
 	__raw_try_cmpxchg((ptr), (pold), (new), (size), LOCK_PREFIX)
 
-#define try_cmpxchg(ptr, pold, new) 					\
+#define arch_try_cmpxchg(ptr, pold, new) 				\
 	__try_cmpxchg((ptr), (pold), (new), sizeof(*(ptr)))
 
 /*
include/asm-generic/atomic-instrumented.h +130 -86

278 lines not on this page · raw message

include/linux/atomic-arch-fallback.h +80 -10

117 lines not on this page · raw message

include/linux/atomic-fallback.h +80 -10

117 lines not on this page · raw message

scripts/atomic/gen-atomic-fallback.sh +56 -7

88 lines not on this page · raw message

scripts/atomic/gen-atomic-instrumented.sh +23 -6
@@ -103,14 +103,31 @@ gen_xchg()
 	local xchg="$1"; shift
 	local mult="$1"; shift
 
+	if [ "${xchg%${xchg#try_cmpxchg}}" = "try_cmpxchg" ] ; then
+
 cat <<EOF
-#define ${xchg}(ptr, ...)						\\
-({									\\
-	typeof(ptr) __ai_ptr = (ptr);					\\
-	instrument_atomic_write(__ai_ptr, ${mult}sizeof(*__ai_ptr));		\\
-	arch_${xchg}(__ai_ptr, __VA_ARGS__);				\\
+#define ${xchg}(ptr, oldp, ...) \\
+({ \\
+	typeof(ptr) __ai_ptr = (ptr); \\
+	typeof(oldp) __ai_oldp = (oldp); \\
+	instrument_atomic_write(__ai_ptr, ${mult}sizeof(*__ai_ptr)); \\
+	instrument_atomic_write(__ai_oldp, ${mult}sizeof(*__ai_oldp)); \\
+	arch_${xchg}(__ai_ptr, __ai_oldp, __VA_ARGS__); \\
 })
 EOF
+
+	else
+
+cat <<EOF
+#define ${xchg}(ptr, ...) \\
+({ \\
+	typeof(ptr) __ai_ptr = (ptr); \\
+	instrument_atomic_write(__ai_ptr, ${mult}sizeof(*__ai_ptr)); \\
+	arch_${xchg}(__ai_ptr, __VA_ARGS__); \\
+})
+EOF
+
+	fi
 }
 
 gen_optional_xchg()
@@ -160,7 +177,7 @@ grep '^[a-z]' "$1" | while read name met
 	gen_proto "${meta}" "${name}" "atomic64" "s64" ${args}
 done
 
-for xchg in "xchg" "cmpxchg" "cmpxchg64"; do
+for xchg in "xchg" "cmpxchg" "cmpxchg64" "try_cmpxchg"; do
 	for order in "" "_acquire" "_release" "_relaxed"; do
 		gen_optional_xchg "${xchg}" "${order}"
 	done
author maintainer
#20 lore raw

Re: [RFC][PATCH 6/7] freelist: Lock less freelist

In reply to Peter Zijlstra

include/linux/freelist.h line 21

Quoted 4 lines · Peter Zijlstra
include/linux/freelist.h new file +4 -0
+struct freelist_node {
+	atomic_t		refs;
+	struct freelist_node	*next;
+};

Bah, the next patch relies on this structure to be ordered the other way around.

Clearly writing code and listening to talks isn't ideal :-)

author maintainer
#22 lore raw

Re: [RFC][PATCH 6/7] freelist: Lock less freelist

In reply to a message not in the archive
Quoted 3 lines · Cameron

For what it's worth, the freelist.h code seems to be a faithful adaptation of my original blog post code. Didn't think it would end up in the Linux kernel one day :-)

Hehe, I ran into the traditional ABA problem for the lockless stack and asked google, your blog came up.

I'll try and actually think about it a little when the current (virtual) conference is over.

Are you Ok with the License I put on it, GPLv2 or BDS-2 ?

Quoted 2 lines

I'm just wondering if the assumption that "nodes are never freed until after the free list is destroyed" will hold true in the intended use case?

It does, the nodes are only deleted once the whole freelist object is discarded.

#23 lore raw

Re: [RFC][PATCH 6/7] freelist: Lock less freelist

Quoted 1 line · On Thu, Aug 27, 2020 at 12:56 PM <[email protected]> wrote:

Are you Ok with the License I put on it, GPLv2 or BDS-2 ?

Yes, both GPLv2 and BSD-2 (my personal favourite) are fine.

maintainer
#4 lore raw

Re: [RFC][PATCH 3/7] kprobes: Remove kretprobe hash

In reply to Peter Zijlstra
Quoted 6 lines · On Thu, 27 Aug 2020 18:12:40 +0200 Peter Zijlstra <[email protected]> wrote:
kernel/kprobes.c +6 -0
+static void invalidate_rp_inst(struct task_struct *t, struct kretprobe *rp)
+{
+	struct invl_rp_ipi iri = {
+		.task = t,
+		.rp = rp,
+		.done = false

kernel/kprobes.c static inline void free_rp_inst(struct k · line 1353

Quoted 10 lines
kernel/kprobes.c +10 -0
+	};
+
+	for (;;) {
+		if (try_invoke_on_locked_down_task(t, __invalidate_rp_inst, rp))
+			return;
+
+		smp_call_function_single(task_cpu(t), __invalidate_rp_ipi, &iri, 1);
+		if (iri.done)
+			return;
+	}

Hmm, what about making a status place holder and point it from each instance to tell it is valid or not?

struct kretprobe_holder {
	atomic_t refcnt;
	struct kretprobe *rp;
};

struct kretprobe {
...
struct kretprobe_holder *rph; // allocate at register
...
};

struct kretprobe_instance {
...

	struct kretprobe_holder	*rph; // free if refcnt == 0

...
};

cleanup_rp_inst(struct kretprobe *rp)

{
	rp->rph->rp = NULL;
}

kretprobe_trampoline_handler()
{
...

	rp = READ_ONCE(ri->rph-rp);
	if (likely(rp)) {
		// call rp->handler
	} else
		rcu_call(ri, free_rp_inst_rcu);

...
}

free_rp_inst_rcu()

{
	if (!atomic_dec_return(ri->rph->refcnt))
		kfree(ri->rph);
	kfree(ri);
}

This increase kretprobe_instance a bit, but make things simpler. (and still keep lockless, atomic op is in the rcu callback).

Thank you,

Signature · 1 line
Masami Hiramatsu <[email protected]>
#24 lore raw

Re: [RFC][PATCH 6/7] freelist: Lock less freelist

In reply to Peter Zijlstra
Quoted 102 lines · Peter Zijlstra
---
 include/linux/freelist.h |  129 +++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 129 insertions(+)
include/linux/freelist.h new file +89 -0
@@ -0,0 +1,129 @@
+// SPDX-License-Identifier: GPL-2.0-only OR BSD-2-Clause
+#ifndef FREELIST_H
+#define FREELIST_H
+
+#include <linux/atomic.h>
+
+/*
+ * Copyright: [email protected]
+ *
+ * A simple CAS-based lock-free free list. Not the fastest thing in the world
+ * under heavy contention, but simple and correct (assuming nodes are never
+ * freed until after the free list is destroyed), and fairly speedy under low
+ * contention.
+ *
+ * Adapted from: https://moodycamel.com/blog/2014/solving-the-aba-problem-for-lock-free-free-lists
+ */
+
+struct freelist_node {
+	atomic_t		refs;
+	struct freelist_node	*next;
+};
+
+struct freelist_head {
+	struct freelist_node	*head;
+};
+
+#define REFS_ON_FREELIST 0x80000000
+#define REFS_MASK	 0x7FFFFFFF
+
+static inline void __freelist_add(struct freelist_node *node, struct freelist_head *list)
+{
+	/*
+	 * Since the refcount is zero, and nobody can increase it once it's
+	 * zero (except us, and we run only one copy of this method per node at
+	 * a time, i.e. the single thread case), then we know we can safely
+	 * change the next pointer of the node; however, once the refcount is
+	 * back above zero, then other threads could increase it (happens under
+	 * heavy contention, when the refcount goes to zero in between a load
+	 * and a refcount increment of a node in try_get, then back up to
+	 * something non-zero, then the refcount increment is done by the other
+	 * thread) -- so if the CAS to add the node to the actual list fails,
+	 * decrese the refcount and leave the add operation to the next thread
+	 * who puts the refcount back to zero (which could be us, hence the
+	 * loop).
+	 */
+	struct freelist_node *head = READ_ONCE(list->head);
+
+	for (;;) {
+		WRITE_ONCE(node->next, head);
+		atomic_set_release(&node->refs, 1);
+
+		if (!try_cmpxchg_release(&list->head, &head, node)) {
+			/*
+			 * Hmm, the add failed, but we can only try again when
+			 * the refcount goes back to zero.
+			 */
+			if (atomic_fetch_add_release(REFS_ON_FREELIST - 1, &node->refs) == 1)
+				continue;
+		}
+		return;
+	}
+}
+
+static inline void freelist_add(struct freelist_node *node, struct freelist_head *list)
+{
+	/*
+	 * We know that the should-be-on-freelist bit is 0 at this point, so
+	 * it's safe to set it using a fetch_add.
+	 */
+	if (!atomic_fetch_add_release(REFS_ON_FREELIST, &node->refs)) {
+		/*
+		 * Oh look! We were the last ones referencing this node, and we
+		 * know we want to add it to the free list, so let's do it!
+		 */
+		__freelist_add(node, list);
+	}
+}
+
+static inline struct freelist_node *freelist_try_get(struct freelist_head *list)
+{
+	struct freelist_node *prev, *next, *head = smp_load_acquire(&list->head);
+	unsigned int refs;
+
+	while (head) {
+		prev = head;
+		refs = atomic_read(&head->refs);
+		if ((refs & REFS_MASK) == 0 ||
+		    !atomic_try_cmpxchg_acquire(&head->refs, &refs, refs+1)) {
+			head = smp_load_acquire(&list->head);

include/linux/freelist.h line 99

Quoted 10 lines
include/linux/freelist.h new file +10 -0
+			continue;
+		}
+
+		/*
+		 * Good, reference count has been incremented (it wasn't at
+		 * zero), which means we can read the next and not worry about
+		 * it changing between now and the time we do the CAS.
+		 */
+		next = READ_ONCE(head->next);
+		if (try_cmpxchg_acquire(&list->head, &head, next)) {

So if try_cmpxchg_acquire() fails, we don't have ACQUIRE semantics on read of the new list->head, right? Then probably a smp_mb__after_atomic() is needed in that case?

Regards,
Boqun

Quoted 32 lines
include/linux/freelist.h new file +30 -0
+			/*
+			 * Yay, got the node. This means it was on the list,
+			 * which means should-be-on-freelist must be false no
+			 * matter the refcount (because nobody else knows it's
+			 * been taken off yet, it can't have been put back on).
+			 */
+			WARN_ON_ONCE(atomic_read(&head->refs) & REFS_ON_FREELIST);
+
+			/*
+			 * Decrease refcount twice, once for our ref, and once
+			 * for the list's ref.
+			 */
+			atomic_fetch_add(-2, &head->refs);
+
+			return head;
+		}
+
+		/*
+		 * OK, the head must have changed on us, but we still need to decrement
+		 * the refcount we increased.
+		 */
+		refs = atomic_fetch_add(-1, &prev->refs);
+		if (refs == REFS_ON_FREELIST + 1)
+			__freelist_add(prev, list);
+	}
+
+	return NULL;
+}
+
+#endif /* FREELIST_H */
#25 lore raw

Re: [RFC][PATCH 6/7] freelist: Lock less freelist

Quoted 3 lines · Boqun Feng

So if try_cmpxchg_acquire() fails, we don't have ACQUIRE semantics on read of the new list->head, right? Then probably a smp_mb__after_atomic() is needed in that case?

Yes, there needs to be an acquire on the head after a failed cmpxchg; does the atomic_fetch_add following that not have acquire semantics?

Cameron

#26 lore raw

Re: [RFC][PATCH 6/7] freelist: Lock less freelist

Quoted 8 lines · Cameron
Quoted 3 lines · Boqun Feng

So if try_cmpxchg_acquire() fails, we don't have ACQUIRE semantics on read of the new list->head, right? Then probably a smp_mb__after_atomic() is needed in that case?

Yes, there needs to be an acquire on the head after a failed cmpxchg; does the atomic_fetch_add following that not have acquire semantics?

Yes, you're right, the atomic_fecth_add() following is a fully-ordered atomic, so could provide the necessary ACQUIRE semantics. I was missing that. Maybe a few words explaining this helps.

Regards,
Boqun

Quoted 1 line

Cameron

#27 lore raw

Re: [RFC][PATCH 6/7] freelist: Lock less freelist

In reply to Peter Zijlstra
Quoted 6 lines · Peter Zijlstra
include/linux/freelist.h new file +6 -0
+static inline void __freelist_add(struct freelist_node *node, struct freelist_head *list)
+{
+       /*
+        * Since the refcount is zero, and nobody can increase it once it's
+        * zero (except us, and we run only one copy of this method per node at
+        * a time, i.e. the single thread case), then we know we can safely

include/linux/freelist.h

Quoted 10 lines
include/linux/freelist.h new file +8 -0
 
 
+
+               /*
+                * OK, the head must have changed on us, but we still need to decrement
+                * the refcount we increased.
+                */
+               refs = atomic_fetch_add(-1, &prev->refs);
+               if (refs == REFS_ON_FREELIST + 1)
+                       __freelist_add(prev, list);

I'm curious whether it is correct to just set the prev->refs to zero and return @prev? So that it can remove an unneeded "add()&get()" pair (although in an unlikely branch) and __freelist_add() can be folded into freelist_add() for tidier code.

Thanks
Lai.

maintainer
#7 lore raw

Re: [RFC][PATCH 3/7] kprobes: Remove kretprobe hash

In reply to Peter Zijlstra

kernel/kprobes.c void kprobe_busy_end(void) · line 1266

Quoted 8 lines · On Thu, 27 Aug 2020 18:12:40 +0200 Peter Zijlstra <[email protected]> wrote:
kernel/kprobes.c +2 -1
@@ -1313,25 +1261,28 @@ void kprobe_busy_end(void)
 void kprobe_flush_task(struct task_struct *tk)
 {
 	struct kretprobe_instance *ri;
-	struct hlist_head *head, empty_rp;
+	struct hlist_head empty_rp;
+	struct llist_node *node;
 	struct hlist_node *tmp;

We don't need this tmp anymore.

kernel/kprobes.c unsigned long __kretprobe_trampoline_han · line 1940

Quoted 11 lines
kernel/kprobes.c +4 -1
@@ -1935,71 +1932,45 @@ unsigned long __kretprobe_trampoline_han
 					unsigned long trampoline_address,
 					void *frame_pointer)
 {
+	kprobe_opcode_t *correct_ret_addr = NULL;
 	struct kretprobe_instance *ri = NULL;
-	struct hlist_head *head, empty_rp;
+	unsigned long orig_ret_address = 0;
+	struct llist_node *first, *node;
+	struct hlist_head empty_rp;
 	struct hlist_node *tmp;

Here too.

I'm trying to port this patch on my v4 series. I'll add my RFC patch of kretprobe_holder too.

Thank you,

Signature · 1 line
Masami Hiramatsu <[email protected]>
author maintainer
#5 lore raw

Re: [RFC][PATCH 3/7] kprobes: Remove kretprobe hash

In reply to Masami Hiramatsu
Quoted 57 lines · Masami Hiramatsu
Quoted 6 lines · On Thu, 27 Aug 2020 18:12:40 +0200 Peter Zijlstra <[email protected]> wrote:
kernel/kprobes.c +6 -0
+static void invalidate_rp_inst(struct task_struct *t, struct kretprobe *rp)
+{
+	struct invl_rp_ipi iri = {
+		.task = t,
+		.rp = rp,
+		.done = false

kernel/kprobes.c static inline void free_rp_inst(struct k · line 1353

Quoted 10 lines
kernel/kprobes.c +10 -0
+	};
+
+	for (;;) {
+		if (try_invoke_on_locked_down_task(t, __invalidate_rp_inst, rp))
+			return;
+
+		smp_call_function_single(task_cpu(t), __invalidate_rp_ipi, &iri, 1);
+		if (iri.done)
+			return;
+	}

Hmm, what about making a status place holder and point it from each instance to tell it is valid or not?

struct kretprobe_holder {
	atomic_t refcnt;
	struct kretprobe *rp;
};

struct kretprobe {
...
struct kretprobe_holder *rph; // allocate at register
...
};

struct kretprobe_instance {
...

	struct kretprobe_holder	*rph; // free if refcnt == 0

...
};

cleanup_rp_inst(struct kretprobe *rp)

{
	rp->rph->rp = NULL;
}

kretprobe_trampoline_handler()
{
...

	rp = READ_ONCE(ri->rph-rp);
	if (likely(rp)) {
		// call rp->handler
	} else
		rcu_call(ri, free_rp_inst_rcu);

...
}

free_rp_inst_rcu()

Quoted 8 lines
{
	if (!atomic_dec_return(ri->rph->refcnt))
		kfree(ri->rph);
	kfree(ri);
}

This increase kretprobe_instance a bit, but make things simpler. (and still keep lockless, atomic op is in the rcu callback).

Yes, much better.

Although I'd _love_ to get rid of rp->data_size, then we can simplify all of this even more. I was thinking we could then have a single global freelist thing and add some per-cpu cache to it (say 4-8 entries) to avoid the worst contention.

And then make function-graph use this, instead of the other way around :-)

author maintainer
#32 lore raw

Re: [RFC][PATCH 7/7] kprobes: Replace rp->free_instance with freelist

In reply to Peter Zijlstra

include/linux/kprobes.h struct kretprobe { · line 168

Quoted 12 lines · Peter Zijlstra

struct kretprobe_instance {

include/linux/kprobes.h +6 -1
 	union {
+		/*
+		 * Dodgy as heck, this relies on not clobbering freelist::refs.
+		 * llist: only clobbers freelist::next.
+		 * rcu: clobbers both, but only after rp::freelist is gone.
+		 */
+		struct freelist_node freelist;
 		struct llist_node llist;
-		struct hlist_node hlist;
 		struct rcu_head rcu;
 	};

Masami, make sure to make this something like:

	union {
		struct freelist_node freelist;
		struct rcu_head rcu;
	};
	struct llist_node llist;

for v4, because after some sleep I'm fairly sure what I wrote above was broken.

We'll only use RCU once the freelist is gone, so sharing that storage should still be okay.

maintainer
#6 lore raw

Re: [RFC][PATCH 3/7] kprobes: Remove kretprobe hash

In reply to Masami Hiramatsu
Quoted 57 lines · On Fri, 28 Aug 2020 03:00:59 +0900 Masami Hiramatsu <[email protected]> wrote:
Quoted 6 lines · On Thu, 27 Aug 2020 18:12:40 +0200 Peter Zijlstra <[email protected]> wrote:
kernel/kprobes.c +6 -0
+static void invalidate_rp_inst(struct task_struct *t, struct kretprobe *rp)
+{
+	struct invl_rp_ipi iri = {
+		.task = t,
+		.rp = rp,
+		.done = false

kernel/kprobes.c static inline void free_rp_inst(struct k · line 1353

Quoted 10 lines
kernel/kprobes.c +10 -0
+	};
+
+	for (;;) {
+		if (try_invoke_on_locked_down_task(t, __invalidate_rp_inst, rp))
+			return;
+
+		smp_call_function_single(task_cpu(t), __invalidate_rp_ipi, &iri, 1);
+		if (iri.done)
+			return;
+	}

Hmm, what about making a status place holder and point it from each instance to tell it is valid or not?

struct kretprobe_holder {
	atomic_t refcnt;
	struct kretprobe *rp;
};

struct kretprobe {
...
struct kretprobe_holder *rph; // allocate at register
...
};

struct kretprobe_instance {
...

	struct kretprobe_holder	*rph; // free if refcnt == 0

...
};

cleanup_rp_inst(struct kretprobe *rp)

{
	rp->rph->rp = NULL;
}

kretprobe_trampoline_handler()
{
...

	rp = READ_ONCE(ri->rph-rp);
	if (likely(rp)) {
		// call rp->handler
	} else
		rcu_call(ri, free_rp_inst_rcu);

...
}

free_rp_inst_rcu()

Quoted 8 lines
{
	if (!atomic_dec_return(ri->rph->refcnt))
		kfree(ri->rph);
	kfree(ri);
}

This increase kretprobe_instance a bit, but make things simpler. (and still keep lockless, atomic op is in the rcu callback).

OK, I've written the code and run a smoke test on it. I'll send it with my 4th version of series.

Thank you,

Signature · 1 line
Masami Hiramatsu <[email protected]>
maintainer
#33 lore raw

Re: [RFC][PATCH 7/7] kprobes: Replace rp->free_instance with freelist

In reply to [email protected]
Quoted 22 lines · On Fri, 28 Aug 2020 10:48:51 +0200 [email protected] wrote:

include/linux/kprobes.h struct kretprobe { · line 168

Quoted 12 lines · Peter Zijlstra

struct kretprobe_instance {

include/linux/kprobes.h +6 -1
 	union {
+		/*
+		 * Dodgy as heck, this relies on not clobbering freelist::refs.
+		 * llist: only clobbers freelist::next.
+		 * rcu: clobbers both, but only after rp::freelist is gone.
+		 */
+		struct freelist_node freelist;
 		struct llist_node llist;
-		struct hlist_node hlist;
 		struct rcu_head rcu;
 	};

Masami, make sure to make this something like:

	union {
		struct freelist_node freelist;
		struct rcu_head rcu;
	};
	struct llist_node llist;
Quoted 5 lines

for v4, because after some sleep I'm fairly sure what I wrote above was broken.

We'll only use RCU once the freelist is gone, so sharing that storage should still be okay.

Hmm, would you mean there is a chance that an instance belongs to both freelist and llist?

Thank you,

Signature · 1 line
Masami Hiramatsu <[email protected]>
author maintainer
#34 lore raw

Re: [RFC][PATCH 7/7] kprobes: Replace rp->free_instance with freelist

Quoted 25 lines · Masami Hiramatsu
Quoted 22 lines · On Fri, 28 Aug 2020 10:48:51 +0200 [email protected] wrote:

include/linux/kprobes.h struct kretprobe { · line 168

Quoted 12 lines · Peter Zijlstra

struct kretprobe_instance {

include/linux/kprobes.h +6 -1
 	union {
+		/*
+		 * Dodgy as heck, this relies on not clobbering freelist::refs.
+		 * llist: only clobbers freelist::next.
+		 * rcu: clobbers both, but only after rp::freelist is gone.
+		 */
+		struct freelist_node freelist;
 		struct llist_node llist;
-		struct hlist_node hlist;
 		struct rcu_head rcu;
 	};

Masami, make sure to make this something like:

	union {
		struct freelist_node freelist;
		struct rcu_head rcu;
	};
	struct llist_node llist;
Quoted 8 lines
Quoted 5 lines

for v4, because after some sleep I'm fairly sure what I wrote above was broken.

We'll only use RCU once the freelist is gone, so sharing that storage should still be okay.

Hmm, would you mean there is a chance that an instance belongs to both freelist and llist?

So the freelist->refs thing is supposed to pin freelist->next for concurrent usage, but if we instantly stick it on the current->kretprobe_instances llist while it's still elevated, we'll overwrite ->next, which would be bad.

maintainer
#35 lore raw

Re: [RFC][PATCH 7/7] kprobes: Replace rp->free_instance with freelist

Quoted 32 lines · On Fri, 28 Aug 2020 11:18:13 +0200 [email protected] wrote:
Quoted 31 lines · Masami Hiramatsu
Quoted 27 lines · On Fri, 28 Aug 2020 10:48:51 +0200 [email protected] wrote:

include/linux/kprobes.h struct kretprobe { · line 168

Quoted 12 lines · Peter Zijlstra

struct kretprobe_instance {

include/linux/kprobes.h +6 -1
 	union {
+		/*
+		 * Dodgy as heck, this relies on not clobbering freelist::refs.
+		 * llist: only clobbers freelist::next.
+		 * rcu: clobbers both, but only after rp::freelist is gone.
+		 */
+		struct freelist_node freelist;
 		struct llist_node llist;
-		struct hlist_node hlist;
 		struct rcu_head rcu;
 	};

Masami, make sure to make this something like:

	union {
		struct freelist_node freelist;
		struct rcu_head rcu;
	};
	struct llist_node llist;

for v4, because after some sleep I'm fairly sure what I wrote above was broken.

We'll only use RCU once the freelist is gone, so sharing that storage should still be okay.

Quoted 7 lines
Quoted 2 lines

Hmm, would you mean there is a chance that an instance belongs to both freelist and llist?

So the freelist->refs thing is supposed to pin freelist->next for concurrent usage, but if we instantly stick it on the current->kretprobe_instances llist while it's still elevated, we'll overwrite ->next, which would be bad.

OK, I'll pick these up for my v4 series with that fix.

Thank you,

Signature · 1 line
Masami Hiramatsu <[email protected]>
#8 lore raw

RE: [RFC][PATCH 3/7] kprobes: Remove kretprobe hash

In reply to Peter Zijlstra
Quoted 29 lines

-----Original Message-----
From: Peter Zijlstra <[email protected]>
Sent: Friday, August 28, 2020 12:13 AM
To: [email protected]; [email protected]
Cc: Eddy Wu (RD-TW) <[email protected]>; [email protected]; [email protected]; [email protected]; [email protected]; [email protected]; [email protected]; [email protected]; [email protected]; [email protected]; [email protected]; [email protected]
Subject: [RFC][PATCH 3/7] kprobes: Remove kretprobe hash

kernel/kprobes.c +6 -5
@@ -1935,71 +1932,45 @@ unsigned long __kretprobe_trampoline_han
                                        unsigned long trampoline_address,
                                        void *frame_pointer)
 {
 // ... removed
 // NULL here
+       first = node = current->kretprobe_instances.first;
+       while (node) {
+               ri = container_of(node, struct kretprobe_instance, llist);
 
-               orig_ret_address = (unsigned long)ri->ret_addr;
-               if (skipped)
-                       pr_warn("%ps must be blacklisted because of incorrect kretprobe order\n",
-                               ri->rp->kp.addr);
+               BUG_ON(ri->fp != frame_pointer);
 
-               if (orig_ret_address != trampoline_address)
+               orig_ret_address = (unsigned long)ri->ret_addr;
+               if (orig_ret_address != trampoline_address) {
                        /*

kernel/kprobes.c unsigned long __kretprobe_trampoline_han · line 1955

Quoted 10 lines
kernel/kprobes.c +3 -0
                         * This is the real return address. Any other
                         * instances associated with this task are for
                         * other calls deeper on the call stack
                         */
                        break;
+               }
+
+               node = node->next;
        }
 

Hi, I found a NULL pointer dereference here, where current->kretprobe_instances.first == NULL in these two scenario:

1) In task "rs:main Q:Reg"

# insmod samples/kprobes/kretprobe_example.ko func=schedule
# pkill sddm-greeter

2) In task "llvmpipe-10"

# insmod samples/kprobes/kretprobe_example.ko func=schedule
login plasmashell session from sddm graphical interface

based on Masami's v2 + Peter's lockless patch, I'll try the new branch once I can compile kernel

Stacktrace may not be really useful here:

[  402.008630] BUG: kernel NULL pointer dereference, address: 0000000000000018
[  402.008633] #PF: supervisor read access in kernel mode
[  402.008642] #PF: error_code(0x0000) - not-present page
[  402.008644] PGD 0 P4D 0
[  402.008646] Oops: 0000 [#1] PREEMPT SMP PTI
[  402.008649] CPU: 7 PID: 1505 Comm: llvmpipe-10 Kdump: loaded Not tainted 5.9.0-rc2-00111-g72091ec08f03-dirty #45
[  402.008650] Hardware name: VMware, Inc. VMware Virtual Platform/440BX Desktop Reference Platform, BIOS 6.00 07/29/2019
[  402.008653] RIP: 0010:__kretprobe_trampoline_handler+0xb8/0x17f
[  402.008655] Code: 65 4c 8b 34 25 80 6d 01 00 4c 89 e2 48 c7 c7 91 6b 85 91 49 8d b6 38 07 00 00 e8 d1 1a f9 ff 48 85 db 74 06 48 3b 5d d0 75 16 <49> 8b 75 18 48 c7 c7 a0 6c 85 91 48
 8b 56 28 e8 b2 1a f9 ff 0f 0b
[  402.008655] RSP: 0018:ffffab408147bde0 EFLAGS: 00010246
[  402.008656] RAX: 0000000000000021 RBX: 0000000000000000 RCX: 0000000000000002
[  402.008657] RDX: 0000000080000002 RSI: ffffffff9189757d RDI: 00000000ffffffff
[  402.008658] RBP: ffffab408147be20 R08: 0000000000000001 R09: 000000000000955c
[  402.008658] R10: 0000000000000004 R11: 0000000000000000 R12: 0000000000000000
[  402.008659] R13: 0000000000000000 R14: ffff90736d305f40 R15: 0000000000000000
[  402.008661] FS:  00007f20f6ffd700(0000) GS:ffff9073781c0000(0000) knlGS:0000000000000000
[  402.008675] CS:  0010 DS: 0000 ES: 0000 CR0: 0000000080050033
[  402.008678] CR2: 0000000000000018 CR3: 00000001ed256006 CR4: 00000000003706e0
[  402.008684] Call Trace:
[  402.008689]  ? elfcorehdr_read+0x40/0x40
[  402.008690]  ? elfcorehdr_read+0x40/0x40
[  402.008691]  trampoline_handler+0x42/0x60
[  402.008692]  kretprobe_trampoline+0x2a/0x50
[  402.008693] RIP: 0010:kretprobe_trampoline+0x0/0x50

TREND MICRO EMAIL NOTICE

The information contained in this email and any attachments is confidential and may be subject to copyright or other intellectual property protection. If you are not the intended recipient, you are not authorized to use or disclose this information, and we request that you notify us by reply mail or telephone and delete the original message from your mail system.

For details about what personal information we collect and why, please see our Privacy Notice on our website at: Read privacy policy<http://www.trendmicro.com/privacy>

author maintainer
#9 lore raw

Re: [RFC][PATCH 3/7] kprobes: Remove kretprobe hash

Quoted 34 lines · On Fri, Aug 28, 2020 at 01:11:15PM +0000, [email protected] wrote:
Quoted 34 lines

-----Original Message-----
From: Peter Zijlstra <[email protected]>
Sent: Friday, August 28, 2020 12:13 AM
To: [email protected]; [email protected]
Cc: Eddy Wu (RD-TW) <[email protected]>; [email protected]; [email protected]; [email protected]; [email protected]; [email protected]; [email protected]; [email protected]; [email protected]; [email protected]; [email protected]; [email protected]
Subject: [RFC][PATCH 3/7] kprobes: Remove kretprobe hash

kernel/kprobes.c +6 -5
@@ -1935,71 +1932,45 @@ unsigned long __kretprobe_trampoline_han
                                        unsigned long trampoline_address,
                                        void *frame_pointer)
 {
 // ... removed
 // NULL here
+       first = node = current->kretprobe_instances.first;
+       while (node) {
+               ri = container_of(node, struct kretprobe_instance, llist);
 
-               orig_ret_address = (unsigned long)ri->ret_addr;
-               if (skipped)
-                       pr_warn("%ps must be blacklisted because of incorrect kretprobe order\n",
-                               ri->rp->kp.addr);
+               BUG_ON(ri->fp != frame_pointer);
 
-               if (orig_ret_address != trampoline_address)
+               orig_ret_address = (unsigned long)ri->ret_addr;
+               if (orig_ret_address != trampoline_address) {
                        /*
                         * This is the real return address. Any other
                         * instances associated with this task are for
                         * other calls deeper on the call stack
                         */
                        break;
Quoted 8 lines

kernel/kprobes.c unsigned long __kretprobe_trampoline_han · line 1962

Quoted 5 lines
kernel/kprobes.c +3 -0
+               }
+
+               node = node->next;
        }
 

Hi, I found a NULL pointer dereference here, where current->kretprobe_instances.first == NULL in these two scenario:

Hurmph, that would mean hitting the trampoline and not having a kretprobe_instance, weird. Let me try and reproduce.

maintainer
#10 lore raw

Re: [RFC][PATCH 3/7] kprobes: Remove kretprobe hash

In reply to [email protected]
Quoted 25 lines · On Fri, 28 Aug 2020 13:11:15 +0000 "[email protected]"…
Quoted 25 lines

-----Original Message-----
From: Peter Zijlstra <[email protected]>
Sent: Friday, August 28, 2020 12:13 AM
To: [email protected]; [email protected]
Cc: Eddy Wu (RD-TW) <[email protected]>; [email protected]; [email protected]; [email protected]; [email protected]; [email protected]; [email protected]; [email protected]; [email protected]; [email protected]; [email protected]; [email protected]
Subject: [RFC][PATCH 3/7] kprobes: Remove kretprobe hash

kernel/kprobes.c +4 -4
@@ -1935,71 +1932,45 @@ unsigned long __kretprobe_trampoline_han
                                        unsigned long trampoline_address,
                                        void *frame_pointer)
 {
 // ... removed
 // NULL here
+       first = node = current->kretprobe_instances.first;
+       while (node) {
+               ri = container_of(node, struct kretprobe_instance, llist);
 
-               orig_ret_address = (unsigned long)ri->ret_addr;
-               if (skipped)
-                       pr_warn("%ps must be blacklisted because of incorrect kretprobe order\n",
-                               ri->rp->kp.addr);
+               BUG_ON(ri->fp != frame_pointer);
 
Quoted 16 lines
Quoted 4 lines
kernel/kprobes.c +2 -1
-               if (orig_ret_address != trampoline_address)
+               orig_ret_address = (unsigned long)ri->ret_addr;
+               if (orig_ret_address != trampoline_address) {
                        /*

kernel/kprobes.c unsigned long __kretprobe_trampoline_han · line 1962

Quoted 10 lines
kernel/kprobes.c +3 -0
                         * This is the real return address. Any other
                         * instances associated with this task are for
                         * other calls deeper on the call stack
                         */
                        break;
+               }
+
+               node = node->next;
        }
 

Hi, I found a NULL pointer dereference here, where current->kretprobe_instances.first == NULL in these two scenario:

Thanks! that may be what I'm chasing.

Quoted 8 lines

1) In task "rs:main Q:Reg"

# insmod samples/kprobes/kretprobe_example.ko func=schedule
# pkill sddm-greeter

2) In task "llvmpipe-10"

# insmod samples/kprobes/kretprobe_example.ko func=schedule
login plasmashell session from sddm graphical interface

OK, schedule function will be the key. I guess the senario is..

1) kretporbe replace the return address with kretprobe_trampoline on task1's kernel stack
2) the task1 forks task2 before returning to the kretprobe_trampoline
3) while copying the process with the kernel stack, task2->kretprobe_instances.first = NULL
4) task2 returns to the kretprobe_trampoline
5) Bomb!

Hmm, we need to fixup the kernel stack when copying process.

Thank you,

Quoted 35 lines

based on Masami's v2 + Peter's lockless patch, I'll try the new branch once I can compile kernel

Stacktrace may not be really useful here:

[  402.008630] BUG: kernel NULL pointer dereference, address: 0000000000000018
[  402.008633] #PF: supervisor read access in kernel mode
[  402.008642] #PF: error_code(0x0000) - not-present page
[  402.008644] PGD 0 P4D 0
[  402.008646] Oops: 0000 [#1] PREEMPT SMP PTI
[  402.008649] CPU: 7 PID: 1505 Comm: llvmpipe-10 Kdump: loaded Not tainted 5.9.0-rc2-00111-g72091ec08f03-dirty #45
[  402.008650] Hardware name: VMware, Inc. VMware Virtual Platform/440BX Desktop Reference Platform, BIOS 6.00 07/29/2019
[  402.008653] RIP: 0010:__kretprobe_trampoline_handler+0xb8/0x17f
[  402.008655] Code: 65 4c 8b 34 25 80 6d 01 00 4c 89 e2 48 c7 c7 91 6b 85 91 49 8d b6 38 07 00 00 e8 d1 1a f9 ff 48 85 db 74 06 48 3b 5d d0 75 16 <49> 8b 75 18 48 c7 c7 a0 6c 85 91 48
 8b 56 28 e8 b2 1a f9 ff 0f 0b
[  402.008655] RSP: 0018:ffffab408147bde0 EFLAGS: 00010246
[  402.008656] RAX: 0000000000000021 RBX: 0000000000000000 RCX: 0000000000000002
[  402.008657] RDX: 0000000080000002 RSI: ffffffff9189757d RDI: 00000000ffffffff
[  402.008658] RBP: ffffab408147be20 R08: 0000000000000001 R09: 000000000000955c
[  402.008658] R10: 0000000000000004 R11: 0000000000000000 R12: 0000000000000000
[  402.008659] R13: 0000000000000000 R14: ffff90736d305f40 R15: 0000000000000000
[  402.008661] FS:  00007f20f6ffd700(0000) GS:ffff9073781c0000(0000) knlGS:0000000000000000
[  402.008675] CS:  0010 DS: 0000 ES: 0000 CR0: 0000000080050033
[  402.008678] CR2: 0000000000000018 CR3: 00000001ed256006 CR4: 00000000003706e0
[  402.008684] Call Trace:
[  402.008689]  ? elfcorehdr_read+0x40/0x40
[  402.008690]  ? elfcorehdr_read+0x40/0x40
[  402.008691]  trampoline_handler+0x42/0x60
[  402.008692]  kretprobe_trampoline+0x2a/0x50
[  402.008693] RIP: 0010:kretprobe_trampoline+0x0/0x50

TREND MICRO EMAIL NOTICE

The information contained in this email and any attachments is confidential and may be subject to copyright or other intellectual property protection. If you are not the intended recipient, you are not authorized to use or disclose this information, and we request that you notify us by reply mail or telephone and delete the original message from your mail system.

For details about what personal information we collect and why, please see our Privacy Notice on our website at: Read privacy policy<http://www.trendmicro.com/privacy>

Signature · 1 line
Masami Hiramatsu <[email protected]>
author maintainer
#11 lore raw

Re: [RFC][PATCH 3/7] kprobes: Remove kretprobe hash

Quoted 9 lines · Masami Hiramatsu

OK, schedule function will be the key. I guess the senario is..

1) kretporbe replace the return address with kretprobe_trampoline on task1's kernel stack
2) the task1 forks task2 before returning to the kretprobe_trampoline
3) while copying the process with the kernel stack, task2->kretprobe_instances.first = NULL
4) task2 returns to the kretprobe_trampoline
5) Bomb!

Hmm, we need to fixup the kernel stack when copying process.

How would that scenario have been avoided in the old code? Because there task2 would have a different has and not have found a kretprobe_instance either.

#13 lore raw

RE: [RFC][PATCH 3/7] kprobes: Remove kretprobe hash

In reply to Masami Hiramatsu
Quoted 7 lines

From: Masami Hiramatsu <[email protected]>

OK, schedule function will be the key. I guess the senario is..

1) kretporbe replace the return address with kretprobe_trampoline on task1's kernel stack
2) the task1 forks task2 before returning to the kretprobe_trampoline
3) while copying the process with the kernel stack, task2->kretprobe_instances.first = NULL

I think new process created by fork/clone uses a brand new kernel stack? I thought only user stack are copied. Otherwise any process launch should crash in the same way

By the way, I can reproduce this on the latest branch(v4) TREND MICRO EMAIL NOTICE

The information contained in this email and any attachments is confidential and may be subject to copyright or other intellectual property protection. If you are not the intended recipient, you are not authorized to use or disclose this information, and we request that you notify us by reply mail or telephone and delete the original message from your mail system.

For details about what personal information we collect and why, please see our Privacy Notice on our website at: Read privacy policy<http://www.trendmicro.com/privacy>

maintainer
#12 lore raw

Re: [RFC][PATCH 3/7] kprobes: Remove kretprobe hash

In reply to [email protected]
Quoted 10 lines · On Fri, 28 Aug 2020 15:58:24 +0200 [email protected] wrote:
Quoted 8 lines · Masami Hiramatsu

OK, schedule function will be the key. I guess the senario is..

1) kretporbe replace the return address with kretprobe_trampoline on task1's kernel stack
2) the task1 forks task2 before returning to the kretprobe_trampoline
3) while copying the process with the kernel stack, task2->kretprobe_instances.first = NULL
4) task2 returns to the kretprobe_trampoline
5) Bomb!

Quoted 5 lines
Quoted 1 line

Hmm, we need to fixup the kernel stack when copying process.

How would that scenario have been avoided in the old code? Because there task2 would have a different has and not have found a kretprobe_instance either.

Good question, I think this bug has not been solved in old code too. Let me check.

Thanks,

Signature · 1 line
Masami Hiramatsu <[email protected]>
author maintainer
#14 lore raw

Re: [RFC][PATCH 3/7] kprobes: Remove kretprobe hash

In reply to [email protected]
Quoted 11 lines · On Fri, Aug 28, 2020 at 02:11:18PM +0000, [email protected] wrote:
Quoted 7 lines

From: Masami Hiramatsu <[email protected]>

OK, schedule function will be the key. I guess the senario is..

1) kretporbe replace the return address with kretprobe_trampoline on task1's kernel stack
2) the task1 forks task2 before returning to the kretprobe_trampoline
3) while copying the process with the kernel stack, task2->kretprobe_instances.first = NULL

I think new process created by fork/clone uses a brand new kernel stack? I thought only user stack are copied. Otherwise any process launch should crash in the same way

I was under the same impression, we create a brand new stack-frame for the new task, this 'fake' frame we can schedule into.

It either points to ret_from_fork() for new user tasks, or kthread_frame_init() for kernel threads.

maintainer
#15 lore raw

Re: [RFC][PATCH 3/7] kprobes: Remove kretprobe hash

Quoted 13 lines · On Fri, 28 Aug 2020 16:19:17 +0200 [email protected] wrote:
Quoted 11 lines · On Fri, Aug 28, 2020 at 02:11:18PM +0000, [email protected] wrote:
Quoted 7 lines

From: Masami Hiramatsu <[email protected]>

OK, schedule function will be the key. I guess the senario is..

1) kretporbe replace the return address with kretprobe_trampoline on task1's kernel stack
2) the task1 forks task2 before returning to the kretprobe_trampoline
3) while copying the process with the kernel stack, task2->kretprobe_instances.first = NULL

I think new process created by fork/clone uses a brand new kernel stack? I thought only user stack are copied. Otherwise any process launch should crash in the same way

Quoted 5 lines

I was under the same impression, we create a brand new stack-frame for the new task, this 'fake' frame we can schedule into.

It either points to ret_from_fork() for new user tasks, or kthread_frame_init() for kernel threads.

Ah sorry, then it's my misreading... anyway, I could reproduce the crash with probing on schedule(). Hmm, it is better to dump the current comm with BUG().

Thank you,

Signature · 1 line
Masami Hiramatsu <[email protected]>
#28 lore raw

Re: [RFC][PATCH 6/7] freelist: Lock less freelist

In reply to Peter Zijlstra
Quoted 2 lines · Peter Zijlstra
 1 file changed, 129 insertions(+)

129 lines! And I spent more than 2 hours trying to understand these 129 lines ;) looks correct...

However, I still can't understand the usage of _acquire/release ops in this code.

Quoted 13 lines
include/linux/freelist.h new file +13 -0
+static inline void __freelist_add(struct freelist_node *node, struct freelist_head *list)
+{
+	/*
+	 * Since the refcount is zero, and nobody can increase it once it's
+	 * zero (except us, and we run only one copy of this method per node at
+	 * a time, i.e. the single thread case), then we know we can safely
+	 * change the next pointer of the node; however, once the refcount is
+	 * back above zero, then other threads could increase it (happens under
+	 * heavy contention, when the refcount goes to zero in between a load
+	 * and a refcount increment of a node in try_get, then back up to
+	 * something non-zero, then the refcount increment is done by the other
+	 * thread) -- so if the CAS to add the node to the actual list fails,
+	 * decrese the refcount and leave the add operation to the next thread

include/linux/freelist.h line 52

Quoted 10 lines
include/linux/freelist.h new file +10 -0
+	 * who puts the refcount back to zero (which could be us, hence the
+	 * loop).
+	 */
+	struct freelist_node *head = READ_ONCE(list->head);
+
+	for (;;) {
+		WRITE_ONCE(node->next, head);
+		atomic_set_release(&node->refs, 1);
+
+		if (!try_cmpxchg_release(&list->head, &head, node)) {

OK, these 2 _release above look understandable, they pair with atomic_try_cmpxchg_acquire/try_cmpxchg_acquire in freelist_try_get().

include/linux/freelist.h line 58

Quoted 6 lines
include/linux/freelist.h new file +6 -0
+			/*
+			 * Hmm, the add failed, but we can only try again when
+			 * the refcount goes back to zero.
+			 */
+			if (atomic_fetch_add_release(REFS_ON_FREELIST - 1, &node->refs) == 1)
+				continue;

Do we really need _release ? Why can't atomic_fetch_add_relaxed() work?

Quoted 24 lines
include/linux/freelist.h new file +24 -0
+static inline struct freelist_node *freelist_try_get(struct freelist_head *list)
+{
+	struct freelist_node *prev, *next, *head = smp_load_acquire(&list->head);
+	unsigned int refs;
+
+	while (head) {
+		prev = head;
+		refs = atomic_read(&head->refs);
+		if ((refs & REFS_MASK) == 0 ||
+		    !atomic_try_cmpxchg_acquire(&head->refs, &refs, refs+1)) {
+			head = smp_load_acquire(&list->head);
+			continue;
+		}
+
+		/*
+		 * Good, reference count has been incremented (it wasn't at
+		 * zero), which means we can read the next and not worry about
+		 * it changing between now and the time we do the CAS.
+		 */
+		next = READ_ONCE(head->next);
+		if (try_cmpxchg_acquire(&list->head, &head, next)) {
+			/*
+			 * Yay, got the node. This means it was on the list,
+			 * which means should-be-on-freelist must be false no

include/linux/freelist.h line 112

Quoted 10 lines
include/linux/freelist.h new file +10 -0
+			 * matter the refcount (because nobody else knows it's
+			 * been taken off yet, it can't have been put back on).
+			 */
+			WARN_ON_ONCE(atomic_read(&head->refs) & REFS_ON_FREELIST);
+
+			/*
+			 * Decrease refcount twice, once for our ref, and once
+			 * for the list's ref.
+			 */
+			atomic_fetch_add(-2, &head->refs);

Do we the barriers implied by _fetch_? Why can't atomic_sub(2, refs) work?

include/linux/freelist.h line 121

Quoted 5 lines
include/linux/freelist.h new file +5 -0
+		/*
+		 * OK, the head must have changed on us, but we still need to decrement
+		 * the refcount we increased.
+		 */
+		refs = atomic_fetch_add(-1, &prev->refs);

Cosmetic, but why not atomic_fetch_dec() ?

Oleg.

maintainer
#16 lore raw

Re: [RFC][PATCH 3/7] kprobes: Remove kretprobe hash

In reply to [email protected]
Quoted 13 lines · On Fri, 28 Aug 2020 13:11:15 +0000 "[email protected]"…
Quoted 1 line

-----Original Message----

Hi, I found a NULL pointer dereference here, where current->kretprobe_instances.first == NULL in these two scenario:

1) In task "rs:main Q:Reg"

# insmod samples/kprobes/kretprobe_example.ko func=schedule
# pkill sddm-greeter

2) In task "llvmpipe-10"

# insmod samples/kprobes/kretprobe_example.ko func=schedule
login plasmashell session from sddm graphical interface

based on Masami's v2 + Peter's lockless patch, I'll try the new branch once I can compile kernel

Quoted 7 lines

Stacktrace may not be really useful here:

[  402.008630] BUG: kernel NULL pointer dereference, address: 0000000000000018
[  402.008633] #PF: supervisor read access in kernel mode
[  402.008642] #PF: error_code(0x0000) - not-present page
[  402.008644] PGD 0 P4D 0
[  402.008646] Oops: 0000 [#1] PREEMPT SMP PTI
[  402.008649] CPU: 7 PID: 1505 Comm: llvmpipe-10 Kdump: loaded Not tainted 5.9.0-rc2-00111-g72091ec08f03-dirty #45

Hmm, this case llvmpipe will be the user task (not kthread, I guess)

Here are some logs, both happened with following command and wait 5min or so.

cd /sys/kernel/debug/tracing/
echo r:event1 vfs_read >> kprobe_events
echo r:event2 vfs_read %ax >> kprobe_events
echo r:event3 rw_verify_area %ax >> kprobe_events
echo r:schedule schedule >> kprobe_events
echo 1 > events/kprobes/enable

[  332.986337] ------------[ cut here ]------------
[  332.987312] kernel BUG at kernel/kprobes.c:1893!
[  332.988237] invalid opcode: 0000 [#1] PREEMPT SMP PTI
[  332.989108] CPU: 7 PID: 55 Comm: kcompactd0 Not tainted 5.9.0-rc2+ #54
[  332.990480] Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS 1.13.0-1ubuntu1 04/01/2014
[  332.994600] RIP: 0010:__kretprobe_trampoline_handler+0xf2/0x100
[  332.995551] Code: 48 c7 05 e5 40 ec 7e c0 cc 28 82 4c 89 ff e8 c5 fe ff ff 48 85 db 75 92 48 83 c4 08 4c 89 e0 5b 41 5c 41 5d 41 5e 41 5f 5d c3 <0f> 0b 66 66 2e 0f 1f 84 00 00 00 00 00 90 55 48 89 e5 41 56 41 55
[  332.998498] RSP: 0000:ffffc90000217cf8 EFLAGS: 00010246
[  332.999405] RAX: ffff88807cfe9700 RBX: 0000000000000000 RCX: 0000000000000000
[  333.000597] RDX: ffffc90000217de8 RSI: ffffffff810471e0 RDI: ffffc90000217d50
[  333.002058] RBP: ffffc90000217d28 R08: 0000000000000001 R09: 0000000000000001
[  333.003594] R10: 0000000000000000 R11: 0000000000000001 R12: ffffc90000217d50
[  333.005219] R13: ffff88807d7dbac0 R14: ffffc90000217e00 R15: ffff88807d7dbac0
[  333.006826] FS:  0000000000000000(0000) GS:ffff88807d7c0000(0000) knlGS:0000000000000000
[  333.008787] CS:  0010 DS: 0000 ES: 0000 CR0: 0000000080050033
[  333.010249] CR2: 0000000000000000 CR3: 0000000002220000 CR4: 00000000000006a0
[  333.011895] Call Trace:
[  333.012529]  trampoline_handler+0x43/0x60
[  333.013214]  kretprobe_trampoline+0x2a/0x50
[  333.014028] RIP: 0010:kretprobe_trampoline+0x0/0x50
[  333.014856] Code: c7 e9 2d 04 82 e8 a0 f2 0d 00 5d c3 31 f6 e9 79 ff ff ff be 01 00 00 00 e9 6f ff ff ff cc cc cc cc cc cc cc cc cc cc cc cc cc <54> 9c 48 83 ec 18 57 56 52 51 50 41 50 41 51 41 52 41 53 53 55 41
[  333.017750] RSP: 81170fba:ffffc90000217df0 EFLAGS: 00000246
[  333.018894] RAX: 0000000040200040 RBX: ffff88807d7dbac0 RCX: 0000000000000000
[  333.020232] RDX: 0000000000000001 RSI: ffffffff818e51b4 RDI: ffffffff818e51b4
[  333.021476] RBP: ffffc90000217e88 R08: 0000000000000001 R09: 0000000000000001
[  333.022603] R10: 0000000000000000 R11: 0000000000000001 R12: 0000000100008044
[  333.024221] R13: ffff88807d7dbac0 R14: ffffc90000217e00 R15: ffff88807d7dbac0
[  333.025851]  ? schedule+0x54/0x100
[  333.026717]  ? schedule+0x54/0x100
[  333.027400]  ? trace_preempt_on+0x2a/0xd0
[  333.028161]  ? __next_timer_interrupt+0x110/0x110
[  333.029080]  kcompactd+0x20e/0x350
[  333.029882]  ? wait_woken+0x80/0x80
[  333.030593]  ? kcompactd_do_work+0x3a0/0x3a0
[  333.031347]  kthread+0x13c/0x180
[  333.031988]  ? kthread_park+0x90/0x90
[  333.032734]  ret_from_fork+0x22/0x30
[  333.033557] Modules linked in:
[  333.034451] ---[ end trace 901e8137e8d04982 ]---
[  333.035601] RIP: 0010:__kretprobe_trampoline_handler+0xf2/0x100
[  333.037073] Code: 48 c7 05 e5 40 ec 7e c0 cc 28 82 4c 89 ff e8 c5 fe ff ff 48 85 db 75 92 48 83 c4 08 4c 89 e0 5b 41 5c 41 5d 41 5e 41 5f 5d c3 <0f> 0b 66 66 2e 0f 1f 84 00 00 00 00 00 90 55 48 89 e5 41 56 41 55
[  333.041089] RSP: 0000:ffffc90000217cf8 EFLAGS: 00010246
[  333.042201] RAX: ffff88807cfe9700 RBX: 0000000000000000 RCX: 0000000000000000
[  333.043747] RDX: ffffc90000217de8 RSI: ffffffff810471e0 RDI: ffffc90000217d50
[  333.045063] RBP: ffffc90000217d28 R08: 0000000000000001 R09: 0000000000000001
[  333.046547] R10: 0000000000000000 R11: 0000000000000001 R12: ffffc90000217d50
[  333.048055] R13: ffff88807d7dbac0 R14: ffffc90000217e00 R15: ffff88807d7dbac0
[  333.049616] FS:  0000000000000000(0000) GS:ffff88807d7c0000(0000) knlGS:0000000000000000
[  333.051487] CS:  0010 DS: 0000 ES: 0000 CR0: 0000000080050033
[  333.052737] CR2: 0000000000000000 CR3: 0000000002220000 CR4: 00000000000006a0
[  333.054127] Kernel panic - not syncing: Fatal exception
[  333.055450] Kernel Offset: disabled
[  333.056207] ---[ end Kernel panic - not syncing: Fatal exception ]---

Another one is here.

 [  335.258721] ------------[ cut here ]------------
[  335.264413] kernel BUG at kernel/kprobes.c:1893!
[  335.267757] invalid opcode: 0000 [#1] PREEMPT SMP PTI
[  335.272090] CPU: 7 PID: 71 Comm: kworker/7:1 Not tainted 5.9.0-rc2+ #54
[  335.277787] Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS 1.13.0-1ubuntu1 04/01/2014
[  335.285971] Workqueue:  0x0 (mm_percpu_wq)
[  335.288156] RIP: 0010:__kretprobe_trampoline_handler+0xf2/0x100
[  335.295194] Code: 48 c7 05 e5 40 ec 7e c0 cc 28 82 4c 89 ff e8 c5 fe ff ff 48 85 db 75 92 48 83 c4 08 4c 89 e0 5b 41 5c 41 5d 41 5e 41 5f 5d c3 <0f> 0b 66 66 2e 0f 1f 84 00 00 00 00 00 90 55 48 89 e5 41 56 41 55
[  335.300922] RSP: 0018:ffffc9000028fdb8 EFLAGS: 00010246
[  335.302336] RAX: ffff88807c4e9700 RBX: 0000000000000000 RCX: 0000000000000000
[  335.304154] RDX: ffffc9000028fea8 RSI: ffffffff810471e0 RDI: ffffc9000028fe10
[  335.305688] RBP: ffffc9000028fde8 R08: 0000000000000001 R09: 0000000000000001
[  335.307486] R10: 0000000000000000 R11: 0000000000000001 R12: ffffc9000028fe10
[  335.309131] R13: ffff88807d7ea440 R14: ffffc900001cbd58 R15: ffff88807c4e4000
[  335.310472] FS:  0000000000000000(0000) GS:ffff88807d7c0000(0000) knlGS:0000000000000000
[  335.312121] CS:  0010 DS: 0000 ES: 0000 CR0: 0000000080050033
[  335.313261] CR2: 00000000005c0a56 CR3: 0000000002220000 CR4: 00000000000006a0
[  335.314561] Call Trace:
[  335.315089]  trampoline_handler+0x43/0x60
[  335.315844]  kretprobe_trampoline+0x2a/0x50
[  335.316774] RIP: 0010:kretprobe_trampoline+0x0/0x50
[  335.317651] Code: c7 e9 2d 04 82 e8 a0 f2 0d 00 5d c3 31 f6 e9 79 ff ff ff be 01 00 00 00 e9 6f ff ff ff cc cc cc cc cc cc cc cc cc cc cc cc cc <54> 9c 48 83 ec 18 57 56 52 51 50 41 50 41 51 41 52 41 53 53 55 41
[  335.320480] RSP: 7c4e9700:ffffc9000028feb0 EFLAGS: 00000246
[  335.321410] RAX: ffff88807c4e4000 RBX: ffff88807d7ea440 RCX: 0000000000000000
[  335.322508] RDX: 0000000000000000 RSI: ffffffff818e51b4 RDI: ffff88807c4e9700
[  335.323611] RBP: ffffc9000028ff00 R08: 0000000000000001 R09: 0000000000000001
[  335.324699] R10: 0000000000000000 R11: 0000000000000001 R12: ffff88807c4e4028
[  335.325903] R13: ffff88807d7ea440 R14: ffffc900001cbd58 R15: ffff88807c4e4000
[  335.327012]  ? schedule+0x54/0x100
[  335.327570]  ? process_one_work+0x5c0/0x5c0
[  335.328127]  kthread+0x13c/0x180
[  335.328583]  ? kthread_park+0x90/0x90
[  335.329063]  ret_from_fork+0x22/0x30
[  335.329558] Modules linked in:
[  335.329974] ---[ end trace bd6d1f4d3806b3de ]---
[  335.330562] RIP: 0010:__kretprobe_trampoline_handler+0xf2/0x100
[  335.331294] Code: 48 c7 05 e5 40 ec 7e c0 cc 28 82 4c 89 ff e8 c5 fe ff ff 48 85 db 75 92 48 83 c4 08 4c 89 e0 5b 41 5c 41 5d 41 5e 41 5f 5d c3 <0f> 0b 66 66 2e 0f 1f 84 00 00 00 00 00 90 55 48 89 e5 41 56 41 55
[  335.333433] RSP: 0018:ffffc9000028fdb8 EFLAGS: 00010246
[  335.334091] RAX: ffff88807c4e9700 RBX: 0000000000000000 RCX: 0000000000000000
[  335.334959] RDX: ffffc9000028fea8 RSI: ffffffff810471e0 RDI: ffffc9000028fe10
[  335.335697] RBP: ffffc9000028fde8 R08: 0000000000000001 R09: 0000000000000001
[  335.336447] R10: 0000000000000000 R11: 0000000000000001 R12: ffffc9000028fe10
[  335.337192] R13: ffff88807d7ea440 R14: ffffc900001cbd58 R15: ffff88807c4e4000
[  335.337956] FS:  0000000000000000(0000) GS:ffff88807d7c0000(0000) knlGS:0000000000000000
[  335.338917] CS:  0010 DS: 0000 ES: 0000 CR0: 0000000080050033
[  335.339618] CR2: 00000000005c0a56 CR3: 0000000002220000 CR4: 00000000000006a0
[  335.340373] Kernel panic - not syncing: Fatal exception
[  335.341086] Kernel Offset: disabled
[  335.341587] ---[ end Kernel panic - not syncing: Fatal exception ]---
Signature · 1 line
Masami Hiramatsu <[email protected]>
author maintainer
#29 lore raw

Re: [RFC][PATCH 6/7] freelist: Lock less freelist

In reply to Oleg Nesterov
Quoted 6 lines · Oleg Nesterov
Quoted 2 lines · Peter Zijlstra
 1 file changed, 129 insertions(+)

129 lines! And I spent more than 2 hours trying to understand these 129 lines ;) looks correct...

Yes, even though it already has a bunch of comments, I do feel we can maybe improve on that a little.

For now I went for a 1:1 transliteration of the blog post though.

Quoted 7 lines
Quoted 7 lines
include/linux/freelist.h new file +7 -0
+			/*
+			 * Yay, got the node. This means it was on the list,
+			 * which means should-be-on-freelist must be false no
+			 * matter the refcount (because nobody else knows it's
+			 * been taken off yet, it can't have been put back on).
+			 */
+			WARN_ON_ONCE(atomic_read(&head->refs) & REFS_ON_FREELIST);
Quoted 8 lines

include/linux/freelist.h line 112

Quoted 6 lines
include/linux/freelist.h new file +6 -0
+
+			/*
+			 * Decrease refcount twice, once for our ref, and once
+			 * for the list's ref.
+			 */
+			atomic_fetch_add(-2, &head->refs);

Do we the barriers implied by _fetch_? Why can't atomic_sub(2, refs) work?

I think we can, the original has std::memory_order_relaxed here. So I should've used atomic_fetch_add_relaxed() but since we don't use the return value, atomic_sub() would work just fine too.

Quoted 7 lines

include/linux/freelist.h line 121

Quoted 5 lines
include/linux/freelist.h new file +5 -0
+		/*
+		 * OK, the head must have changed on us, but we still need to decrement
+		 * the refcount we increased.
+		 */
+		refs = atomic_fetch_add(-1, &prev->refs);

Cosmetic, but why not atomic_fetch_dec() ?

The original had that, I didn't want to risk more bugs by 'improving' things. But yes, that can definitely become dec().

#36 lore raw

Re: [RFC][PATCH 7/7] kprobes: Replace rp->free_instance with freelist

In reply to [email protected]
Quoted 4 lines · On Fri, Aug 28, 2020 at 5:18 AM <[email protected]> wrote:

So the freelist->refs thing is supposed to pin freelist->next for concurrent usage, but if we instantly stick it on the current->kretprobe_instances llist while it's still elevated, we'll overwrite ->next, which would be bad.

I thought about this some more, and actually, it should be safe.

The next is not supposed to be changed while the node has non-zero ref-count, true, but this is only important while the node is in the freelist. If it's never added back to the freelist, then there is no problem (the overwritten next may be read but never used).

But even if it is later re-added to the freelist, as long as the refcount is still above zero, the node won't actually be in the list right away, and again its next won't matter. When the refcount finally goes down to zero, it will be put on the list but its next will be blindly overwritten at that point.

Cameron

#37 lore raw

Re: [RFC][PATCH 7/7] kprobes: Replace rp->free_instance with freelist

Quoted 1 line · Cameron

I thought about this some more, and actually, it should be safe.

Although I should note that it's important that the flags/refcount are not overwritten
even after the node is taken off the freelist.

Cameron

#30 lore raw

Re: [RFC][PATCH 6/7] freelist: Lock less freelist

In reply to [email protected]
Quoted 4 lines

I'm curious whether it is correct to just set the prev->refs to zero and return @prev? So that it can remove an unneeded "add()&get()" pair (although in an unlikely branch) and __freelist_add() can be folded into freelist_add() for tidier code.

That is a very good question. I believe it would be correct, yes, and would certainly simplify the code. The reference count is zero, so nobody can increment it again, and REFS_ON_FREELIST is set (the should-be-on-freelist flag), so instead of adding it to the freelist to be removed later, it can be returned directly.

Quoted 3 lines · Oleg Nesterov
Quoted 2 lines

129 lines! And I spent more than 2 hours trying to understand these 129 lines ;) looks correct...

Hahaha. Sorry about that. Some of the most mind-bending code I've ever written. :-)

Quoted 7 lines

include/linux/freelist.h line 58

Quoted 6 lines
include/linux/freelist.h new file +6 -0
+                     /*
+                      * Hmm, the add failed, but we can only try again when
+                      * the refcount goes back to zero.
+                      */
+                     if (atomic_fetch_add_release(REFS_ON_FREELIST - 1, &node->refs) == 1)
+                             continue;

Do we really need _release ? Why can't atomic_fetch_add_relaxed() work?

The release is to synchronize with the acquire in the compare-exchange of try_get. However, I think you're right, between the previous release-write to the refs and that point, there are no memory effects that need to be synchronized, and so it could be safely replaced with a relaxed operation.

Quoted 1 line

Cosmetic, but why not atomic_fetch_dec() ?

This is just one of my idiosyncrasies. I prefer exclusively using atomic add, I find it easier to read. Feel free to change them all to subs!

Cameron

Quoted 17 lines
Quoted 2 lines

Do we the barriers implied by _fetch_? Why can't atomic_sub(2, refs) work?

I think we can, the original has std::memory_order_relaxed here. So I should've used atomic_fetch_add_relaxed() but since we don't use the return value, atomic_sub() would work just fine too.

Quoted 7 lines

include/linux/freelist.h line 121

Quoted 5 lines
include/linux/freelist.h new file +5 -0
+           /*
+            * OK, the head must have changed on us, but we still need to decrement
+            * the refcount we increased.
+            */
+           refs = atomic_fetch_add(-1, &prev->refs);

Cosmetic, but why not atomic_fetch_dec() ?

The original had that, I didn't want to risk more bugs by 'improving' things. But yes, that can definitely become dec().

maintainer
#38 lore raw

Re: [RFC][PATCH 7/7] kprobes: Replace rp->free_instance with freelist

In reply to Cameron
Quoted 6 lines · On Fri, 28 Aug 2020 22:31:17 -0400 Cameron <[email protected]> wrote:
Quoted 1 line · Cameron

I thought about this some more, and actually, it should be safe.

Although I should note that it's important that the flags/refcount are not overwritten
even after the node is taken off the freelist.

Thanks for the check, but I personally would like to keep it separated because the memory layouts of those in-kernel list-like data structures can be changed by debug config option...

Thank you,

Signature · 1 line
Masami Hiramatsu <[email protected]>