kprobes: Make kretprobes lockless
Subsystems (9)
Peter Zijlstra
maintainerRFC PATCH 4/7 kprobe: Dont kfree() from breakpoint context
In reply to Peter ZijlstraBreakpoint 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 kretprobevoid 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_inraw_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_hanunsigned 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)
Peter Zijlstra
maintainerRFC 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_nextern 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 llisreturn 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
Peter Zijlstra
maintainerRFC 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 */
Peter Zijlstra
maintainerRFC 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; }
Peter Zijlstra
maintainerRFC PATCH 7/7 kprobes: Replace rp->free_instance with freelist
In reply to Peter ZijlstraGets 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
Peter Zijlstra
maintainerRFC PATCH 3/7 kprobes: Remove kretprobe hash
In reply to Peter ZijlstraThe 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_struINIT_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
Peter Zijlstra
maintainerRFC PATCH 5/7 asm-generic/atomic: Add try_cmpxchg() fallbacks
In reply to Peter ZijlstraOnly 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
Peter Zijlstra
maintainercover kprobes: Make kretprobes lockless
Hi,
These are on top of Masami's generic kretprobe handler patches (v1):
https://lkml.kernel.org/r/159844957216.510284.17683703701627367133.stgit@devnote2
They are very lightly tested, esp. the freelist stuff has basically only been translated to kernel C without much thinking (while attending LPC), all bugs are undoubted mine and not Cameron's.
Changelogs are terse or nonexistant :/
[email protected]
maintainerRe: [RFC][PATCH 6/7] freelist: Lock less freelist
In reply to Peter Zijlstrainclude/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 :-)
[email protected]
maintainerRe: [RFC][PATCH 6/7] freelist: Lock less freelist
In reply to a message not in the archiveQuoted 3 lines · Cameron
For what it's worth, the
freelist.hcode 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.
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.
Masami Hiramatsu
maintainerRe: [RFC][PATCH 3/7] kprobes: Remove kretprobe hash
In reply to Peter ZijlstraQuoted 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]>
Re: [RFC][PATCH 6/7] freelist: Lock less freelist
In reply to Peter ZijlstraQuoted 102 lines · Peter Zijlstra
Signed-off-by Peter Zijlstra (Intel) <[email protected]>--- 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 */
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 newlist->head, right? Then probably asmp_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
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 newlist->head, right? Then probably asmp_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_addfollowing 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
Re: [RFC][PATCH 6/7] freelist: Lock less freelist
In reply to Peter ZijlstraQuoted 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.
Masami Hiramatsu
maintainerRe: [RFC][PATCH 3/7] kprobes: Remove kretprobe hash
In reply to Peter Zijlstrakernel/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_hanunsigned 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]>
[email protected]
maintainerRe: [RFC][PATCH 3/7] kprobes: Remove kretprobe hash
In reply to Masami HiramatsuQuoted 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 = falsekernel/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 {
...
structkretprobe_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_instancea 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 :-)
[email protected]
maintainerRe: [RFC][PATCH 7/7] kprobes: Replace rp->free_instance with freelist
In reply to Peter Zijlstrainclude/linux/kprobes.h struct kretprobe { · line 168
Quoted 12 lines · Peter Zijlstra
struct
kretprobe_instance{include/linux/kprobes.h +6
-1union { +/* +* 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.
Masami Hiramatsu
maintainerRe: [RFC][PATCH 3/7] kprobes: Remove kretprobe hash
In reply to Masami HiramatsuQuoted 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 = falsekernel/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 {
...
structkretprobe_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_instancea 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]>
Masami Hiramatsu
maintainerRe: [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
-1union { +/* +* 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]>
[email protected]
maintainerRe: [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
-1union { +/* +* 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.
Masami Hiramatsu
maintainerRe: [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
-1union { +/* +* 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->refsthing is supposed to pinfreelist->nextfor concurrent usage, but if we instantly stick it on thecurrent->kretprobe_instancesllist 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]>
RE: [RFC][PATCH 3/7] kprobes: Remove kretprobe hash
In reply to Peter ZijlstraQuoted 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 hashkernel/kprobes.c +6
-5@@ -1935,71 +1932,45 @@ unsigned long __kretprobe_trampoline_hanunsigned 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>
[email protected]
maintainerRe: [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 hashkernel/kprobes.c +6
-5@@ -1935,71 +1932,45 @@ unsigned long __kretprobe_trampoline_hanunsigned 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.
Masami Hiramatsu
maintainerRe: [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 hashkernel/kprobes.c +4
-4@@ -1935,71 +1932,45 @@ unsigned long __kretprobe_trampoline_hanunsigned 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-greeter2) 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/0x50TREND 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]>
[email protected]
maintainerRe: [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_trampolineon task1's kernel stack
2) the task1 forks task2 before returning to thekretprobe_trampoline
3) while copying the process with the kernel stack,task2->kretprobe_instances.first= NULL
4) task2 returns to thekretprobe_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.
RE: [RFC][PATCH 3/7] kprobes: Remove kretprobe hash
In reply to Masami HiramatsuQuoted 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_trampolineon task1's kernel stack
2) the task1 forks task2 before returning to thekretprobe_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>
Masami Hiramatsu
maintainerRe: [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_trampolineon task1's kernel stack
2) the task1 forks task2 before returning to thekretprobe_trampoline
3) while copying the process with the kernel stack,task2->kretprobe_instances.first= NULL
4) task2 returns to thekretprobe_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_instanceeither.
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]>
[email protected]
maintainerRe: [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_trampolineon task1's kernel stack
2) the task1 forks task2 before returning to thekretprobe_trampoline
3) while copying the process with the kernel stack,task2->kretprobe_instances.first= NULLI 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.
Masami Hiramatsu
maintainerRe: [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_trampolineon task1's kernel stack
2) the task1 forks task2 before returning to thekretprobe_trampoline
3) while copying the process with the kernel stack,task2->kretprobe_instances.first= NULLI 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, orkthread_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]>
Re: [RFC][PATCH 6/7] freelist: Lock less freelist
In reply to Peter ZijlstraQuoted 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.
Masami Hiramatsu
maintainerRe: [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-greeter2) In task "llvmpipe-10"
# insmod samples/kprobes/kretprobe_example.ko func=schedule login plasmashell session from sddm graphical interfacebased 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]>
[email protected]
maintainerRe: [RFC][PATCH 6/7] freelist: Lock less freelist
In reply to Oleg NesterovQuoted 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().
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->refsthing is supposed to pinfreelist->nextfor concurrent usage, but if we instantly stick it on thecurrent->kretprobe_instancesllist 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
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
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->refsto 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 intofreelist_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'tatomic_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_relaxedhere. So I should've usedatomic_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().
Masami Hiramatsu
maintainerRe: [RFC][PATCH 7/7] kprobes: Replace rp->free_instance with freelist
In reply to CameronQuoted 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]>