Re: [patch] kprobes: optimize branch placement

From: Ingo Molnar
Date: Sat Sep 16 2006 - 16:53:55 EST


* Ingo Molnar <mingo@xxxxxxx> wrote:

> the patch below brings the overhead down to 420 cycles:
>
> sys_getpid() kprobes-speedup: 737 cycles [ 0.341 usecs ]

the patch below reduces the kprobes overhead to 305 cycles. The current
performance table is:

sys_getpid() unmodified latency: 317 cycles [ 0.146 usecs ] 0
sys_getpid() djprobes latency: 380 cycles [ 0.176 usecs ] +63
sys_getpid() kprobes latency: 815 cycles [ 0.377 usecs ] +498
sys_getpid() kprobes-speedup: 740 cycles [ 0.342 usecs ] +423
sys_getpid() kprobes-speedup2: 737 cycles [ 0.341 usecs ] +420
sys_getpid() kprobes-speedup3: 622 cycles [ 0.287 usecs ] +305

the 3 speedups i did today eliminated 63% of the kprobes overhead in
this test.

this too shows that there's lots of performance potential even in
INT3-based kprobes.

Ingo

--------------->
Subject: [patch] kprobes: move from struct_hlist to struct_list
From: Ingo Molnar <mingo@xxxxxxx>

kprobes is using hlists for no good reason: the hash-table is 64 entries
so there's no significant RAM footprint difference. hlists are more
complicated to handle though and cause runtime overhead and cacheline
inefficiencies.

Signed-off-by: Ingo Molnar <mingo@xxxxxxx>

---
arch/i386/kernel/kprobes.c | 7 +--
include/linux/djprobe.h | 3 -
include/linux/kprobes.h | 15 +++----
init/main.c | 3 +
kernel/djprobe.c | 23 ++++++----
kernel/kprobes.c | 96 +++++++++++++++++++++------------------------
6 files changed, 75 insertions(+), 72 deletions(-)

Index: linux/arch/i386/kernel/kprobes.c
===================================================================
--- linux.orig/arch/i386/kernel/kprobes.c
+++ linux/arch/i386/kernel/kprobes.c
@@ -354,9 +354,8 @@ no_kprobe:
*/
fastcall void *__kprobes trampoline_handler(struct pt_regs *regs)
{
- struct kretprobe_instance *ri = NULL;
- struct hlist_head *head;
- struct hlist_node *node, *tmp;
+ struct kretprobe_instance *ri = NULL, *tmp;
+ struct list_head *head;
unsigned long flags, orig_ret_address = 0;
unsigned long trampoline_address =(unsigned long)&kretprobe_trampoline;

@@ -376,7 +375,7 @@ fastcall void *__kprobes trampoline_hand
* real return address, and all the rest will point to
* kretprobe_trampoline
*/
- hlist_for_each_entry_safe(ri, node, tmp, head, hlist) {
+ list_for_each_entry_safe(ri, tmp, head, hlist) {
if (ri->task != current)
/* another task is sharing our hash bucket */
continue;
Index: linux/include/linux/djprobe.h
===================================================================
--- linux.orig/include/linux/djprobe.h
+++ linux/include/linux/djprobe.h
@@ -36,7 +36,7 @@ struct djprobe_instance {
struct list_head plist; /* list of djprobes for multiprobe support */
struct arch_djprobe_stub stub;
struct kprobe kp;
- struct hlist_node hlist; /* list of djprobe_instances */
+ struct list_head hlist; /* list of djprobe_instances */
};
#define DJPI_EMPTY(djpi) (list_empty(&djpi->plist))

@@ -65,6 +65,7 @@ extern int djprobe_pre_handler(struct kp
extern void arch_install_djprobe_instance(struct djprobe_instance *djpi);
extern void arch_uninstall_djprobe_instance(struct djprobe_instance *djpi);
struct djprobe_instance * __get_djprobe_instance(void *addr, int size);
+extern int init_djprobe(void);

int register_djprobe(struct djprobe *p, void *addr, int size);
void unregister_djprobe(struct djprobe *p);
Index: linux/include/linux/kprobes.h
===================================================================
--- linux.orig/include/linux/kprobes.h
+++ linux/include/linux/kprobes.h
@@ -39,7 +39,7 @@
#include <linux/mutex.h>

struct kprobe_insn_page_list {
- struct hlist_head list;
+ struct list_head list;
int insn_size; /* size of an instruction slot */
};

@@ -69,7 +69,7 @@ typedef int (*kretprobe_handler_t) (stru
struct pt_regs *);

struct kprobe {
- struct hlist_node hlist;
+ struct list_head hlist;

/* list of kprobes for multi-handler support */
struct list_head list;
@@ -145,13 +145,13 @@ struct kretprobe {
kretprobe_handler_t handler;
int maxactive;
int nmissed;
- struct hlist_head free_instances;
- struct hlist_head used_instances;
+ struct list_head free_instances;
+ struct list_head used_instances;
};

struct kretprobe_instance {
- struct hlist_node uflist; /* either on free list or used list */
- struct hlist_node hlist;
+ struct list_head uflist; /* either on free list or used list */
+ struct list_head hlist;
struct kretprobe *rp;
kprobe_opcode_t *ret_addr;
struct task_struct *task;
@@ -163,6 +163,7 @@ extern int arch_prepare_kprobe(struct kp
extern void arch_arm_kprobe(struct kprobe *p);
extern void arch_disarm_kprobe(struct kprobe *p);
extern int arch_init_kprobes(void);
+extern int init_kprobes(void);
extern void show_registers(struct pt_regs *regs);
extern kprobe_opcode_t *get_insn_slot(void);
extern void free_insn_slot(kprobe_opcode_t *slot);
@@ -175,7 +176,7 @@ extern int in_kprobes_functions(unsigned

/* Get the kprobe at this addr (if any) - called with preemption disabled */
struct kprobe *get_kprobe(void *addr);
-struct hlist_head * kretprobe_inst_table_head(struct task_struct *tsk);
+struct list_head * kretprobe_inst_table_head(struct task_struct *tsk);

/* kprobe_running() will just return the current_kprobe on this CPU */
static inline struct kprobe *kprobe_running(void)
Index: linux/init/main.c
===================================================================
--- linux.orig/init/main.c
+++ linux/init/main.c
@@ -530,6 +530,9 @@ asmlinkage void __init start_kernel(void
if (efi_enabled)
efi_enter_virtual_mode();
#endif
+#ifdef CONFIG_KPROBES
+ init_kprobes();
+#endif
fork_init(num_physpages);
proc_caches_init();
buffer_init();
Index: linux/kernel/djprobe.c
===================================================================
--- linux.orig/kernel/djprobe.c
+++ linux/kernel/djprobe.c
@@ -47,7 +47,7 @@
#define DJPROBE_TABLE_MASK (DJPROBE_TABLE_SIZE - 1)

/* djprobe instance hash table */
-static struct hlist_head djprobe_inst_table[DJPROBE_TABLE_SIZE];
+static struct list_head djprobe_inst_table[DJPROBE_TABLE_SIZE];

#define hash_djprobe(key) \
(((unsigned long)(key) >> DJPROBE_BLOCK_BITS) & DJPROBE_TABLE_MASK)
@@ -59,12 +59,12 @@ static atomic_t djprobe_count = ATOMIC_I

/* Instruction pages for djprobe's stub code */
static struct kprobe_insn_page_list djprobe_insn_pages = {
- HLIST_HEAD_INIT, 0
+ LIST_HEAD_INIT(djprobe_insn_pages.list), 0
};

static inline void __free_djprobe_instance(struct djprobe_instance *djpi)
{
- hlist_del(&djpi->hlist);
+ list_del(&djpi->hlist);
if (djpi->kp.addr) {
unregister_kprobe(&(djpi->kp));
}
@@ -100,8 +100,8 @@ static inline
djpi->kp.pre_handler = djprobe_pre_handler;
arch_prepare_djprobe_instance(djpi, size);

- INIT_HLIST_NODE(&djpi->hlist);
- hlist_add_head(&djpi->hlist, &djprobe_inst_table[hash_djprobe(addr)]);
+ INIT_LIST_HEAD(&djpi->hlist);
+ list_add(&djpi->hlist, &djprobe_inst_table[hash_djprobe(addr)]);
out:
return djpi;
}
@@ -110,13 +110,12 @@ struct djprobe_instance *__kprobes __get
int size)
{
struct djprobe_instance *djpi;
- struct hlist_node *node;
unsigned long idx, eidx;

idx = hash_djprobe(addr - ARCH_STUB_INSN_MAX);
eidx = ((hash_djprobe(addr + size) + 1) & DJPROBE_TABLE_MASK);
do {
- hlist_for_each_entry(djpi, node, &djprobe_inst_table[idx],
+ list_for_each_entry(djpi, &djprobe_inst_table[idx],
hlist) {
if (((long)addr <
(long)djpi->kp.addr + DJPI_ARCH_SIZE(djpi))
@@ -234,13 +233,17 @@ void __kprobes unregister_djprobe(struct
up(&djprobe_mutex);
}

-static int __init init_djprobe(void)
+int __init init_djprobe(void)
{
+ int i;
+
+ for (i = 0; i < DJPROBE_TABLE_SIZE; i++)
+ INIT_LIST_HEAD(&djprobe_inst_table[i]);
+
djprobe_insn_pages.insn_size = ARCH_STUB_SIZE;
+
return 0;
}

-__initcall(init_djprobe);
-
EXPORT_SYMBOL_GPL(register_djprobe);
EXPORT_SYMBOL_GPL(unregister_djprobe);
Index: linux/kernel/kprobes.c
===================================================================
--- linux.orig/kernel/kprobes.c
+++ linux/kernel/kprobes.c
@@ -46,8 +46,8 @@
#define KPROBE_HASH_BITS 6
#define KPROBE_TABLE_SIZE (1 << KPROBE_HASH_BITS)

-static struct hlist_head kprobe_table[KPROBE_TABLE_SIZE];
-static struct hlist_head kretprobe_inst_table[KPROBE_TABLE_SIZE];
+static struct list_head kprobe_table[KPROBE_TABLE_SIZE];
+static struct list_head kretprobe_inst_table[KPROBE_TABLE_SIZE];

DEFINE_MUTEX(kprobe_mutex); /* Protects kprobe_table */
DEFINE_SPINLOCK(kretprobe_lock); /* Protects kretprobe_inst_table */
@@ -63,14 +63,14 @@ static DEFINE_PER_CPU(struct kprobe *, k
#define INSNS_PER_PAGE(size) (PAGE_SIZE/(size * sizeof(kprobe_opcode_t)))

struct kprobe_insn_page {
- struct hlist_node hlist;
+ struct list_head hlist;
kprobe_opcode_t *insns; /* Page of instruction slots */
int nused;
char slot_used[1];
};

static struct kprobe_insn_page_list kprobe_insn_pages = {
- HLIST_HEAD_INIT, MAX_INSN_SIZE
+ LIST_HEAD_INIT(kprobe_insn_pages.list), MAX_INSN_SIZE
};

/**
@@ -81,10 +81,10 @@ kprobe_opcode_t
__kprobes * __get_insn_slot(struct kprobe_insn_page_list *pages)
{
struct kprobe_insn_page *kip;
- struct hlist_node *pos;
+ struct list_head *pos;
int ninsns = INSNS_PER_PAGE(pages->insn_size);

- hlist_for_each(pos, &pages->list) {
+ list_for_each(pos, &pages->list) {
kip = hlist_entry(pos, struct kprobe_insn_page, hlist);
if (kip->nused < ninsns) {
int i;
@@ -118,8 +118,8 @@ kprobe_opcode_t
kfree(kip);
return NULL;
}
- INIT_HLIST_NODE(&kip->hlist);
- hlist_add_head(&kip->hlist, &pages->list);
+ INIT_LIST_HEAD(&kip->hlist);
+ list_add(&kip->hlist, &pages->list);
memset(kip->slot_used, 0, ninsns);
kip->slot_used[0] = 1;
kip->nused = 1;
@@ -130,10 +130,10 @@ void __kprobes __free_insn_slot(struct k
kprobe_opcode_t * slot)
{
struct kprobe_insn_page *kip;
- struct hlist_node *pos;
+ struct list_head *pos;
int ninsns = INSNS_PER_PAGE(pages->insn_size);

- hlist_for_each(pos, &pages->list) {
+ list_for_each(pos, &pages->list) {
kip = hlist_entry(pos, struct kprobe_insn_page, hlist);
if (kip->insns <= slot &&
slot < kip->insns + (ninsns * pages->insn_size)) {
@@ -147,10 +147,10 @@ void __kprobes __free_insn_slot(struct k
* so as not to have to set it up again the
* next time somebody inserts a probe.
*/
- hlist_del(&kip->hlist);
- if (hlist_empty(&pages->list)) {
- INIT_HLIST_NODE(&kip->hlist);
- hlist_add_head(&kip->hlist,
+ list_del(&kip->hlist);
+ if (list_empty(&pages->list)) {
+ INIT_LIST_HEAD(&kip->hlist);
+ list_add(&kip->hlist,
&pages->list);
} else {
module_free(NULL, kip->insns);
@@ -192,12 +192,11 @@ static inline void reset_kprobe_instance
*/
struct kprobe __kprobes *get_kprobe(void *addr)
{
- struct hlist_head *head;
- struct hlist_node *node;
+ struct list_head *head;
struct kprobe *p;

head = &kprobe_table[hash_ptr(addr, KPROBE_HASH_BITS)];
- hlist_for_each_entry_rcu(p, node, head, hlist) {
+ list_for_each_entry_rcu(p, head, hlist) {
if (p->addr == addr)
return p;
}
@@ -283,9 +282,9 @@ void __kprobes kprobes_inc_nmissed_count
/* Called with kretprobe_lock held */
struct kretprobe_instance __kprobes *get_free_rp_inst(struct kretprobe *rp)
{
- struct hlist_node *node;
struct kretprobe_instance *ri;
- hlist_for_each_entry(ri, node, &rp->free_instances, uflist)
+
+ list_for_each_entry(ri, &rp->free_instances, uflist)
return ri;
return NULL;
}
@@ -294,9 +293,9 @@ struct kretprobe_instance __kprobes *get
static struct kretprobe_instance __kprobes *get_used_rp_inst(struct kretprobe
*rp)
{
- struct hlist_node *node;
struct kretprobe_instance *ri;
- hlist_for_each_entry(ri, node, &rp->used_instances, uflist)
+
+ list_for_each_entry(ri, &rp->used_instances, uflist)
return ri;
return NULL;
}
@@ -308,35 +307,35 @@ void __kprobes add_rp_inst(struct kretpr
* Remove rp inst off the free list -
* Add it back when probed function returns
*/
- hlist_del(&ri->uflist);
+ list_del(&ri->uflist);

/* Add rp inst onto table */
- INIT_HLIST_NODE(&ri->hlist);
- hlist_add_head(&ri->hlist,
+ INIT_LIST_HEAD(&ri->hlist);
+ list_add(&ri->hlist,
&kretprobe_inst_table[hash_ptr(ri->task, KPROBE_HASH_BITS)]);

/* Also add this rp inst to the used list. */
- INIT_HLIST_NODE(&ri->uflist);
- hlist_add_head(&ri->uflist, &ri->rp->used_instances);
+ INIT_LIST_HEAD(&ri->uflist);
+ list_add(&ri->uflist, &ri->rp->used_instances);
}

/* Called with kretprobe_lock held */
void __kprobes recycle_rp_inst(struct kretprobe_instance *ri)
{
/* remove rp inst off the rprobe_inst_table */
- hlist_del(&ri->hlist);
+ list_del(&ri->hlist);
if (ri->rp) {
/* remove rp inst off the used list */
- hlist_del(&ri->uflist);
+ list_del(&ri->uflist);
/* put rp inst back onto the free list */
- INIT_HLIST_NODE(&ri->uflist);
- hlist_add_head(&ri->uflist, &ri->rp->free_instances);
+ INIT_LIST_HEAD(&ri->uflist);
+ list_add(&ri->uflist, &ri->rp->free_instances);
} else
/* Unregistering */
kfree(ri);
}

-struct hlist_head __kprobes *kretprobe_inst_table_head(struct task_struct *tsk)
+struct list_head __kprobes *kretprobe_inst_table_head(struct task_struct *tsk)
{
return &kretprobe_inst_table[hash_ptr(tsk, KPROBE_HASH_BITS)];
}
@@ -349,14 +348,13 @@ struct hlist_head __kprobes *kretprobe_i
*/
void __kprobes kprobe_flush_task(struct task_struct *tk)
{
- struct kretprobe_instance *ri;
- struct hlist_head *head;
- struct hlist_node *node, *tmp;
+ struct kretprobe_instance *ri, *tmp;
+ struct list_head *head;
unsigned long flags = 0;

spin_lock_irqsave(&kretprobe_lock, flags);
head = kretprobe_inst_table_head(tk);
- hlist_for_each_entry_safe(ri, node, tmp, head, hlist) {
+ list_for_each_entry_safe(ri, tmp, head, hlist) {
if (ri->task == tk)
recycle_rp_inst(ri);
}
@@ -367,7 +365,7 @@ static inline void free_rp_inst(struct k
{
struct kretprobe_instance *ri;
while ((ri = get_free_rp_inst(rp)) != NULL) {
- hlist_del(&ri->uflist);
+ list_del(&ri->uflist);
kfree(ri);
}
}
@@ -416,7 +414,7 @@ static inline void add_aggr_kprobe(struc
INIT_LIST_HEAD(&ap->list);
list_add_rcu(&p->list, &ap->list);

- hlist_replace_rcu(&p->hlist, &ap->hlist);
+ list_replace_rcu(&p->hlist, &ap->hlist);
}

/*
@@ -499,8 +497,8 @@ static int __kprobes __register_kprobe(s
if ((ret = arch_prepare_kprobe(p)) != 0)
goto out;

- INIT_HLIST_NODE(&p->hlist);
- hlist_add_head_rcu(&p->hlist,
+ INIT_LIST_HEAD(&p->hlist);
+ list_add_rcu(&p->hlist,
&kprobe_table[hash_ptr(p->addr, KPROBE_HASH_BITS)]);

arch_arm_kprobe(p);
@@ -551,7 +549,7 @@ valid_p:
(p->list.prev == &old_p->list))) {
/* Only probe on the hash list */
arch_disarm_kprobe(p);
- hlist_del_rcu(&old_p->hlist);
+ list_del_rcu(&old_p->hlist);
cleanup_p = 1;
} else {
list_del_rcu(&p->list);
@@ -632,16 +630,16 @@ int __kprobes register_kretprobe(struct
rp->maxactive = NR_CPUS;
#endif
}
- INIT_HLIST_HEAD(&rp->used_instances);
- INIT_HLIST_HEAD(&rp->free_instances);
+ INIT_LIST_HEAD(&rp->used_instances);
+ INIT_LIST_HEAD(&rp->free_instances);
for (i = 0; i < rp->maxactive; i++) {
inst = kmalloc(sizeof(struct kretprobe_instance), GFP_KERNEL);
if (inst == NULL) {
free_rp_inst(rp);
return -ENOMEM;
}
- INIT_HLIST_NODE(&inst->uflist);
- hlist_add_head(&inst->uflist, &rp->free_instances);
+ INIT_LIST_HEAD(&inst->uflist);
+ list_add(&inst->uflist, &rp->free_instances);
}

rp->nmissed = 0;
@@ -671,21 +669,21 @@ void __kprobes unregister_kretprobe(stru
spin_lock_irqsave(&kretprobe_lock, flags);
while ((ri = get_used_rp_inst(rp)) != NULL) {
ri->rp = NULL;
- hlist_del(&ri->uflist);
+ list_del(&ri->uflist);
}
spin_unlock_irqrestore(&kretprobe_lock, flags);
free_rp_inst(rp);
}

-static int __init init_kprobes(void)
+int __init init_kprobes(void)
{
int i, err = 0;

/* FIXME allocate the probe table, currently defined statically */
/* initialize all list heads */
for (i = 0; i < KPROBE_TABLE_SIZE; i++) {
- INIT_HLIST_HEAD(&kprobe_table[i]);
- INIT_HLIST_HEAD(&kretprobe_inst_table[i]);
+ INIT_LIST_HEAD(&kprobe_table[i]);
+ INIT_LIST_HEAD(&kretprobe_inst_table[i]);
}

err = arch_init_kprobes();
@@ -695,8 +693,6 @@ static int __init init_kprobes(void)
return err;
}

-__initcall(init_kprobes);
-
EXPORT_SYMBOL_GPL(register_kprobe);
EXPORT_SYMBOL_GPL(unregister_kprobe);
EXPORT_SYMBOL_GPL(register_jprobe);
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/