lkml.org 
[lkml]   [2006]   [Sep]   [16]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    Patch in this message
    /
    Date
    From
    SubjectRe: [patch] kprobes: optimize branch placement

    * Ingo Molnar <mingo@elte.hu> 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@elte.hu>

    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@elte.hu>

    ---
    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@vger.kernel.org
    More majordomo info at http://vger.kernel.org/majordomo-info.html
    Please read the FAQ at http://www.tux.org/lkml/
    \
     
     \ /
      Last update: 2006-09-16 22:57    [W:0.049 / U:61.808 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site