Re: [RFC PATCH 09/11] kprobes: core logic of eraly kprobes

Re: [RFC PATCH 09/11] kprobes: core logic of eraly kprobes

[Hillf Danton]

> 
> +struct early_kprobe_slot {
> +	struct optimized_kprobe op;
> +};
> +
[...]
> 
>  /* Free optimized instructions and optimized_kprobe */
> +static int ek_free_early_kprobe(struct early_kprobe_slot *slot);

[2] How is it implemented? In subsequent patches?

>  static void free_aggr_kprobe(struct kprobe *p)
>  {
>  	struct optimized_kprobe *op;
> +	struct early_kprobe_slot *ep;
> 
>  	op = container_of(p, struct optimized_kprobe, kp);
>  	arch_remove_optimized_kprobe(op);
>  	arch_remove_kprobe(p);
> -	kfree(op);
> +	ep = container_of(op, struct early_kprobe_slot, op);
> +	if (likely(!ek_free_early_kprobe(ep)))
> +		kfree(op);

[1] s/op/ep/   yes?
>  }
> 
[...]
> +#else
> +static int register_early_kprobe(struct kprobe *p) { return -ENOSYS; }
> +static int ek_free_early_kprobe(struct early_kprobe_slot *slot) { return 0; }

[3] Compile-able with CONFIG_EARLY_KPROBES enabled?

> +static void convert_early_kprobes(void) {};
> +#endif
> --
> 1.8.4

Re: [RFC PATCH 09/11] kprobes: core logic of eraly kprobes

[Wang Nan]

On 2015/1/7 17:21, Hillf Danton wrote:
>>
>> +struct early_kprobe_slot {
>> +	struct optimized_kprobe op;
>> +};
>> +
> [...]
>>
>>  /* Free optimized instructions and optimized_kprobe */
>> +static int ek_free_early_kprobe(struct early_kprobe_slot *slot);
> 
> [2] How is it implemented? In subsequent patches?
> 

It is implemented using macro. Please see patch 7/11 and

DEFINE_EKPROBE_ALLOC_OPS(struct early_kprobe_slot, early_kprobe, static);

following.

>>  static void free_aggr_kprobe(struct kprobe *p)
>>  {
>>  	struct optimized_kprobe *op;
>> +	struct early_kprobe_slot *ep;
>>
>>  	op = container_of(p, struct optimized_kprobe, kp);
>>  	arch_remove_optimized_kprobe(op);
>>  	arch_remove_kprobe(p);
>> -	kfree(op);
>> +	ep = container_of(op, struct early_kprobe_slot, op);
>> +	if (likely(!ek_free_early_kprobe(ep)))
>> +		kfree(op);
> 
> [1] s/op/ep/   yes?

Which one? Do you mean kfree(op) --> kfree(ep)?

If ek_free_early_kprobe(ep) fail (not in early_kprobe area defined by
DEFINE_EKPROBE_ALLOC_OPS), then this is a normal aggr probe, allocated
using kzalloc() as struct optimized_kprobe, see alloc_aggr_kprobe().
So kfree corresponding op structure.

If ek_free_early_kprobe(ep) success, then this is an struct early_kprobe_slot
and allocated statically.

>>  }
>>
> [...]
>> +#else
>> +static int register_early_kprobe(struct kprobe *p) { return -ENOSYS; }
>> +static int ek_free_early_kprobe(struct early_kprobe_slot *slot) { return 0; }
> 
> [3] Compile-able with CONFIG_EARLY_KPROBES enabled?

These empty functions are for CONFIG_EARLY_KPROBES disabled. They won't be compiled
when CONFIG_EARLY_KPROBES=y. I have tested both cases on x86 and ARM.

> 
>> +static void convert_early_kprobes(void) {};
>> +#endif
>> --
>> 1.8.4
> 

Thanks.

RE: [RFC PATCH 09/11] kprobes: core logic of eraly kprobes

[Hillf Danton]

> >>
> >> +struct early_kprobe_slot {
> >> +	struct optimized_kprobe op;
> >> +};
> >> +
> > [...]
> >>
> >>  /* Free optimized instructions and optimized_kprobe */
> >> +static int ek_free_early_kprobe(struct early_kprobe_slot *slot);
> >
> > [2] How is it implemented? In subsequent patches?
> >
> 
> It is implemented using macro. Please see patch 7/11 and
> 
> DEFINE_EKPROBE_ALLOC_OPS(struct early_kprobe_slot, early_kprobe, static);
>
What is the reason that it is listed in C file, given that it is done in H already?

Re: [RFC PATCH 09/11] kprobes: core logic of eraly kprobes

[Wang Nan]

On 2015/1/7 18:02, Hillf Danton wrote:
>>>>
>>>> +struct early_kprobe_slot {
>>>> +	struct optimized_kprobe op;
>>>> +};
>>>> +
>>> [...]
>>>>
>>>>  /* Free optimized instructions and optimized_kprobe */
>>>> +static int ek_free_early_kprobe(struct early_kprobe_slot *slot);
>>>
>>> [2] How is it implemented? In subsequent patches?
>>>
>>
>> It is implemented using macro. Please see patch 7/11 and
>>
>> DEFINE_EKPROBE_ALLOC_OPS(struct early_kprobe_slot, early_kprobe, static);
>>
> What is the reason that it is listed in C file, given that it is done in H already?
> 

This macro defines an array and a bitmap, not only declare them. In addition,
the functions defined by it are used only in this specific .c file.

If there are not only one .c files use it, I think patch 7 can be improved:

#define DEFINE_EKPROBE_AREA(__t, __static)				\
__static __t __ek_##__name##_slots[NR_EARLY_KPROBES_SLOTS];		\
__static unsigned long __ek_##__name##_bitmap[EARLY_KPROBES_BITMAP_SZ];

#define DEFINE_EKPROBE_ALLOC_OPS(__t, __name, __static)			\
DEFINE_EKPROBE_AREA(__t, __static)					\
__DEFINE_EKPROBE_ALLOC_OPS(__t, __name)					\
static inline __t *ek_alloc_##__name(void)				\
{									\
...

In .h file(s):
DEFINE_EKPROBE_ALLOC_OPS(struct early_kprobe_slot, early_kprobe, extern)

In .c file:
DEFINE_EKPROBE_AREA(__t, )

What do you think?

RE: [RFC PATCH 09/11] kprobes: core logic of eraly kprobes

[Hillf Danton]

> 
> This macro defines an array and a bitmap, not only declare them. In addition,
> the functions defined by it are used only in this specific .c file.
> 
> If there are not only one .c files use it, I think patch 7 can be improved:
> 
> #define DEFINE_EKPROBE_AREA(__t, __static)				\
> __static __t __ek_##__name##_slots[NR_EARLY_KPROBES_SLOTS];		\
> __static unsigned long __ek_##__name##_bitmap[EARLY_KPROBES_BITMAP_SZ];
> 
> #define DEFINE_EKPROBE_ALLOC_OPS(__t, __name, __static)			\
> DEFINE_EKPROBE_AREA(__t, __static)					\
> __DEFINE_EKPROBE_ALLOC_OPS(__t, __name)					\
> static inline __t *ek_alloc_##__name(void)				\
> {									\
> ...
> 
> In .h file(s):
> DEFINE_EKPROBE_ALLOC_OPS(struct early_kprobe_slot, early_kprobe, extern)
> 
> In .c file:
> DEFINE_EKPROBE_AREA(__t, )
> 
> What do you think?
>
Looks like rocket science;-)

[RFC PATCH 00/11] Early kprobe: enable kprobes at very early

[Wang Nan]

This patch series shows early kprobe, a mechanism allows users to track
events at very early. It should be useful for optimization of system
booting. This can also be used by BSP developers to hook their platform
specific procedures at kernel booting stages after setup_arch().

This patch series provides X86 and ARM support for early kprobes. The ARM
portion is based on my OPTPROBES for ARM 32 patches (ARM: kprobes: OPTPROBES
and other improvements), which have not been accepted yet.

Kprobes is very useful for tracking events. However, it can only be used
after system fully initialized. When debugging kernel booting stage, for
example, checking memory consumption during booting, analyzing boot
phase processes creation and optimization of booting speed, specific
tools must be created. Sometimes we have to modify kernel code.

Early kprobes is my idea on it. By utilizing OPTPROBES which converts probed
instructions into branches instead of breakpoints, kprobe can be used even
before setup of exception handlers. By adding cmdline options, one can insert
kprobes to track kernel booting stage without code modification. 

BSP developers can also benefit from it. For example, when booting an
SoC equipped with unstoppable watchdog like IMP706, wathdog writting
code must be inserted into different places to avoid watchdog resetting
system before watchdogd is pulled up (especially during memory
initialization, which is the most time-consuming portion of booting).
With early kprobe, BSP developers are able to put such code at their
private directory without disturbing arch-independent code.

In this patch series, early kprobes simply print messagees when the
probed instructions are hit. My futher plan is to connect 'ekprobe='
cmdline parameters to '/sys/kernel/debug/tracing/kprobe_events', allows
installing kprobe events from kernel cmdline, and dump early kprobe
messages into ring buffer without print them out.

Patch 1 - 4 are architecture dependent code, allow text modification
before kprobes_initialized is setup, and alloc resources statically from
vmlinux.lds. Currently only x86 and ARM are supported.

Patch 5 - 8 define required flags and macros.

Patch 9 is the core logic of early kprobes. When register_kprobe() is
called before kprobes_initialized, it marks the probed kprobes as
'KPROBE_FLAG_EARLY' and allocs resources from slots which is reserved
during linking. After kprobe is fully initialized, it converts early
kprobes to normal kprobes.

Patch 10 enables cmdline option 'ekprobe=', allows setup probe at
cmdline. However, currently the kprobe handler is only a simple printk.

Patch 11 introduces required Kconfig options to actually enable early
kprobes.

Usage of early kprobe is as follow:

Booting kernel with cmdline 'ekprobe=', like:

... rdinit=/sbin/init ekprobe=0xc00f3c2c ekprobe=__free_pages ...

During boot, kernel will print trace using printk:

 ...
 Hit early kprobe at __alloc_pages_nodemask+0x4
 Hit early kprobe at __free_pages+0x0
 Hit early kprobe at __alloc_pages_nodemask+0x4
 Hit early kprobe at __free_pages+0x0
 Hit early kprobe at __free_pages+0x0
 Hit early kprobe at __alloc_pages_nodemask+0x4
 ...

After fully initialized, early kprobes will be converted to normal
kprobes, and can be turned-off using:

 echo 0 > /sys/kernel/debug/kprobes/enabled

And reenabled using:

 echo 1 > /sys/kernel/debug/kprobes/enabled

Also, optimization can be turned off using:

 echo 0 > /proc/sys/debug/kprobes-optimization

There's no way to remove specific early kprobe now. I'd like to convert
early kprobes into kprobe events in futher patches, and then they can be
totally removed through event interface.

Wang Nan (11):
  ARM: kprobes: directly modify code if kprobe is not initialized.
  ARM: kprobes: introduce early kprobes related code area.
  x86: kprobes: directly modify code if kprobe is not initialized.
  x86: kprobes: introduce early kprobes related code area.
  kprobes: Add an KPROBE_FLAG_EARLY for early kprobe.
  kprobes: makes kprobes_initialized globally visable.
  kprobes: introduces macros for allocing early kprobe resources.
  kprobes: allows __alloc_insn_slot() from early kprobes slots.
  kprobes: core logic of eraly kprobes.
  kprobes: enable 'ekprobe=' cmdline option for early kprobes.
  kprobes: add CONFIG_EARLY_KPROBES option.

 arch/Kconfig                      |  12 ++
 arch/arm/include/asm/kprobes.h    |  29 ++++-
 arch/arm/kernel/vmlinux.lds.S     |   2 +
 arch/arm/probes/kprobes/opt-arm.c |  11 +-
 arch/x86/include/asm/insn.h       |   7 +-
 arch/x86/include/asm/kprobes.h    |  44 +++++--
 arch/x86/kernel/kprobes/opt.c     |   7 +-
 arch/x86/kernel/vmlinux.lds.S     |   2 +
 include/linux/kprobes.h           | 109 ++++++++++++++++++
 kernel/kprobes.c                  | 237 ++++++++++++++++++++++++++++++++++++--
 10 files changed, 437 insertions(+), 23 deletions(-)

-- 
1.8.4

[RFC PATCH 09/11] kprobes: core logic of eraly kprobes.

[Wang Nan]

This patch is the main logic of early kprobe.

If register_kprobe() is called before kprobes_initialized, an early
kprobe is allocated. Try to utilize existing OPTPROBE mechanism to
replace the target instruction by a branch instead of breakpoint,
because interrupt handlers may not been initialized yet.

All resources required by early kprobes are allocated statically.
CONFIG_NR_EARLY_KPROBES_SLOTS is used to control number of possible
early kprobes.

Signed-off-by: Wang Nan <wangnan0@huawei.com>
---
 include/linux/kprobes.h |   4 ++
 kernel/kprobes.c        | 151 ++++++++++++++++++++++++++++++++++++++++++++++--
 2 files changed, 149 insertions(+), 6 deletions(-)

diff --git a/include/linux/kprobes.h b/include/linux/kprobes.h
index 27a27ed..a54947d 100644
--- a/include/linux/kprobes.h
+++ b/include/linux/kprobes.h
@@ -434,6 +434,10 @@ extern int proc_kprobes_optimization_handler(struct ctl_table *table,
 					     size_t *length, loff_t *ppos);
 #endif
 
+struct early_kprobe_slot {
+	struct optimized_kprobe op;
+};
+
 #endif /* CONFIG_OPTPROBES */
 #ifdef CONFIG_KPROBES_ON_FTRACE
 extern void kprobe_ftrace_handler(unsigned long ip, unsigned long parent_ip,
diff --git a/kernel/kprobes.c b/kernel/kprobes.c
index 1882bfa..9c3ea9b 100644
--- a/kernel/kprobes.c
+++ b/kernel/kprobes.c
@@ -71,6 +71,10 @@ int kprobes_initialized;
 static struct hlist_head kprobe_table[KPROBE_TABLE_SIZE];
 static struct hlist_head kretprobe_inst_table[KPROBE_TABLE_SIZE];
 
+#ifdef CONFIG_EARLY_KPROBES
+static HLIST_HEAD(early_kprobe_hlist);
+#endif
+
 /* NOTE: change this value only with kprobe_mutex held */
 static bool kprobes_all_disarmed;
 
@@ -320,7 +324,12 @@ struct kprobe *get_kprobe(void *addr)
 	struct hlist_head *head;
 	struct kprobe *p;
 
-	head = &kprobe_table[hash_ptr(addr, KPROBE_HASH_BITS)];
+#ifdef CONFIG_EARLY_KPROBES
+	if (unlikely(!kprobes_initialized))
+		head = &early_kprobe_hlist;
+	else
+#endif
+		head = &kprobe_table[hash_ptr(addr, KPROBE_HASH_BITS)];
 	hlist_for_each_entry_rcu(p, head, hlist) {
 		if (p->addr == addr)
 			return p;
@@ -377,14 +386,18 @@ void opt_pre_handler(struct kprobe *p, struct pt_regs *regs)
 NOKPROBE_SYMBOL(opt_pre_handler);
 
 /* Free optimized instructions and optimized_kprobe */
+static int ek_free_early_kprobe(struct early_kprobe_slot *slot);
 static void free_aggr_kprobe(struct kprobe *p)
 {
 	struct optimized_kprobe *op;
+	struct early_kprobe_slot *ep;
 
 	op = container_of(p, struct optimized_kprobe, kp);
 	arch_remove_optimized_kprobe(op);
 	arch_remove_kprobe(p);
-	kfree(op);
+	ep = container_of(op, struct early_kprobe_slot, op);
+	if (likely(!ek_free_early_kprobe(ep)))
+		kfree(op);
 }
 
 /* Return true(!0) if the kprobe is ready for optimization. */
@@ -601,9 +614,15 @@ static void optimize_kprobe(struct kprobe *p)
 	struct optimized_kprobe *op;
 
 	/* Check if the kprobe is disabled or not ready for optimization. */
-	if (!kprobe_optready(p) || !kprobes_allow_optimization ||
-	    (kprobe_disabled(p) || kprobes_all_disarmed))
-		return;
+	if (unlikely(!kprobes_initialized)) {
+		BUG_ON(!(p->flags & KPROBE_FLAG_EARLY));
+		if (!kprobe_optready(p) || kprobe_disabled(p))
+			return;
+	} else {
+		if (!kprobe_optready(p) || !kprobes_allow_optimization ||
+		    (kprobe_disabled(p) || kprobes_all_disarmed))
+			return;
+	}
 
 	/* Both of break_handler and post_handler are not supported. */
 	if (p->break_handler || p->post_handler)
@@ -625,7 +644,10 @@ static void optimize_kprobe(struct kprobe *p)
 		list_del_init(&op->list);
 	else {
 		list_add(&op->list, &optimizing_list);
-		kick_kprobe_optimizer();
+		if (unlikely(!kprobes_initialized))
+			arch_optimize_kprobes(&optimizing_list);
+		else
+			kick_kprobe_optimizer();
 	}
 }
 
@@ -1491,6 +1513,8 @@ out:
 	return ret;
 }
 
+static int register_early_kprobe(struct kprobe *p);
+
 int register_kprobe(struct kprobe *p)
 {
 	int ret;
@@ -1504,6 +1528,14 @@ int register_kprobe(struct kprobe *p)
 		return PTR_ERR(addr);
 	p->addr = addr;
 
+	if (unlikely(!kprobes_initialized)) {
+		p->flags |= KPROBE_FLAG_EARLY;
+		return register_early_kprobe(p);
+	}
+
+	WARN(p->flags & KPROBE_FLAG_EARLY,
+		"register early kprobe after kprobes initialized\n");
+
 	ret = check_kprobe_rereg(p);
 	if (ret)
 		return ret;
@@ -2136,6 +2168,8 @@ static struct notifier_block kprobe_module_nb = {
 extern unsigned long __start_kprobe_blacklist[];
 extern unsigned long __stop_kprobe_blacklist[];
 
+static void convert_early_kprobes(void);
+
 static int __init init_kprobes(void)
 {
 	int i, err = 0;
@@ -2184,6 +2218,7 @@ static int __init init_kprobes(void)
 	if (!err)
 		err = register_module_notifier(&kprobe_module_nb);
 
+	convert_early_kprobes();
 	kprobes_initialized = (err == 0);
 
 	if (!err)
@@ -2477,3 +2512,107 @@ module_init(init_kprobes);
 
 /* defined in arch/.../kernel/kprobes.c */
 EXPORT_SYMBOL_GPL(jprobe_return);
+
+#ifdef CONFIG_EARLY_KPROBES
+DEFINE_EKPROBE_ALLOC_OPS(struct early_kprobe_slot, early_kprobe, static);
+
+static int register_early_kprobe(struct kprobe *p)
+{
+	struct early_kprobe_slot *slot;
+	int err;
+
+	if (p->break_handler || p->post_handler)
+		return -EINVAL;
+	if (p->flags & KPROBE_FLAG_DISABLED)
+		return -EINVAL;
+
+	slot = ek_alloc_early_kprobe();
+	if (!slot) {
+		pr_err("No enough early kprobe slots.\n");
+		return -ENOMEM;
+	}
+
+	p->flags &= KPROBE_FLAG_DISABLED;
+	p->flags |= KPROBE_FLAG_EARLY;
+	p->nmissed = 0;
+
+	err = arch_prepare_kprobe(p);
+	if (err) {
+		pr_err("arch_prepare_kprobe failed\n");
+		goto free_slot;
+	}
+
+	INIT_LIST_HEAD(&p->list);
+	INIT_HLIST_NODE(&p->hlist);
+	INIT_LIST_HEAD(&slot->op.list);
+	slot->op.kp.addr = p->addr;
+	slot->op.kp.flags = p->flags | KPROBE_FLAG_EARLY;
+
+	err = arch_prepare_optimized_kprobe(&slot->op, p);
+	if (err) {
+		pr_err("Failed to prepare optimized kprobe.\n");
+		goto remove_optimized;
+	}
+
+	if (!arch_prepared_optinsn(&slot->op.optinsn)) {
+		pr_err("Failed to prepare optinsn.\n");
+		err = -ENOMEM;
+		goto remove_optimized;
+	}
+
+	hlist_add_head_rcu(&p->hlist, &early_kprobe_hlist);
+	init_aggr_kprobe(&slot->op.kp, p);
+	optimize_kprobe(&slot->op.kp);
+	return 0;
+
+remove_optimized:
+	arch_remove_optimized_kprobe(&slot->op);
+free_slot:
+	ek_free_early_kprobe(slot);
+	return err;
+}
+
+static void
+convert_early_kprobe(struct kprobe *kp)
+{
+	struct module *probed_mod;
+	int err;
+
+	BUG_ON(!kprobe_aggrprobe(kp));
+
+	err = check_kprobe_address_safe(kp, &probed_mod);
+	if (err)
+		panic("Insert kprobe at %p is not safe!", kp->addr);
+
+	/*
+	 * FIXME:
+	 * convert kprobe to ftrace if CONFIG_KPROBES_ON_FTRACE is on
+	 * and kp is on ftrace location.
+	 */
+
+	mutex_lock(&kprobe_mutex);
+	hlist_del_rcu(&kp->hlist);
+
+	INIT_HLIST_NODE(&kp->hlist);
+	hlist_add_head_rcu(&kp->hlist,
+		       &kprobe_table[hash_ptr(kp->addr, KPROBE_HASH_BITS)]);
+	mutex_unlock(&kprobe_mutex);
+
+	if (probed_mod)
+		module_put(probed_mod);
+}
+
+static void
+convert_early_kprobes(void)
+{
+	struct kprobe *p;
+	struct hlist_node *tmp;
+
+	hlist_for_each_entry_safe(p, tmp, &early_kprobe_hlist, hlist)
+		convert_early_kprobe(p);
+};
+#else
+static int register_early_kprobe(struct kprobe *p) { return -ENOSYS; }
+static int ek_free_early_kprobe(struct early_kprobe_slot *slot) { return 0; }
+static void convert_early_kprobes(void) {};
+#endif
-- 
1.8.4