* Re: [PATCH -tip 3/3] kprobes: cleanup: use list instead of hlist for insn_pages
2009-06-30 21:08 ` [PATCH -tip 3/3] kprobes: cleanup: use list instead of hlist for insn_pages Masami Hiramatsu
@ 2009-06-30 21:25 ` Ingo Molnar
2009-06-30 21:47 ` Masami Hiramatsu
2009-06-30 23:27 ` [tip:tracing/core] kprobes: Clean up insn_pages by using list instead of hlist tip-bot for Masami Hiramatsu
2009-07-01 8:47 ` tip-bot for Masami Hiramatsu
2 siblings, 1 reply; 14+ messages in thread
From: Ingo Molnar @ 2009-06-30 21:25 UTC (permalink / raw)
To: Masami Hiramatsu
Cc: Ananth N Mavinakayanahalli, lkml, systemtap, DLE, Jim Keniston
* Masami Hiramatsu <mhiramat@redhat.com> wrote:
> Use struct list instead of struct hlist for managing insn_pages,
> because insn_pages doesn't use hash table.
> struct kprobe_insn_page {
> - struct hlist_node hlist;
> + struct list_head list;
Hm, you know that this increases the size of kprobe_insn_page by 4/8
bytes, right?
hlists are not just used for hashes - but also when we want a more
compact / smaller list head.
How many kprobe_insn_page's can be allocated in the system,
maximally?
Ingo
^ permalink raw reply [flat|nested] 14+ messages in thread* Re: [PATCH -tip 3/3] kprobes: cleanup: use list instead of hlist for insn_pages
2009-06-30 21:25 ` Ingo Molnar
@ 2009-06-30 21:47 ` Masami Hiramatsu
2009-06-30 21:50 ` Ingo Molnar
0 siblings, 1 reply; 14+ messages in thread
From: Masami Hiramatsu @ 2009-06-30 21:47 UTC (permalink / raw)
To: Ingo Molnar
Cc: Ananth N Mavinakayanahalli, lkml, systemtap, DLE, Jim Keniston
Ingo Molnar wrote:
> * Masami Hiramatsu <mhiramat@redhat.com> wrote:
>
>> Use struct list instead of struct hlist for managing insn_pages,
>> because insn_pages doesn't use hash table.
>
>> struct kprobe_insn_page {
>> - struct hlist_node hlist;
>> + struct list_head list;
>
> Hm, you know that this increases the size of kprobe_insn_page by 4/8
> bytes, right?
Sure, that will increase size.
> hlists are not just used for hashes - but also when we want a more
> compact / smaller list head.
Oh, I thought hlists are used for hash tables...
>
> How many kprobe_insn_page's can be allocated in the system,
> maximally?
It's depends on how many probes you will use, but logically,
1 kprobe_insn_pages is allocated per 4096/16 = 256 probes.
So, if you use 25,600 probes on your system, memory
consumption will increase 400/800 bytes.
Thank you,
--
Masami Hiramatsu
Software Engineer
Hitachi Computer Products (America), Inc.
Software Solutions Division
e-mail: mhiramat@redhat.com
^ permalink raw reply [flat|nested] 14+ messages in thread* Re: [PATCH -tip 3/3] kprobes: cleanup: use list instead of hlist for insn_pages
2009-06-30 21:47 ` Masami Hiramatsu
@ 2009-06-30 21:50 ` Ingo Molnar
2009-06-30 23:12 ` Masami Hiramatsu
0 siblings, 1 reply; 14+ messages in thread
From: Ingo Molnar @ 2009-06-30 21:50 UTC (permalink / raw)
To: Masami Hiramatsu
Cc: Ananth N Mavinakayanahalli, lkml, systemtap, DLE, Jim Keniston
* Masami Hiramatsu <mhiramat@redhat.com> wrote:
> Ingo Molnar wrote:
> > * Masami Hiramatsu <mhiramat@redhat.com> wrote:
> >
> >> Use struct list instead of struct hlist for managing insn_pages,
> >> because insn_pages doesn't use hash table.
> >
> >> struct kprobe_insn_page {
> >> - struct hlist_node hlist;
> >> + struct list_head list;
> >
> > Hm, you know that this increases the size of kprobe_insn_page by 4/8
> > bytes, right?
>
> Sure, that will increase size.
>
> > hlists are not just used for hashes - but also when we want a more
> > compact / smaller list head.
>
> Oh, I thought hlists are used for hash tables...
... because they are smaller, hence the hash table of list
heads becomes twice as dense as with list_head.
But otherwise it's an (almost) equivalent primitive to list_head,
with a slightly higher runtime cost versus better RAM footprint.
> > How many kprobe_insn_page's can be allocated in the system,
> > maximally?
>
> It's depends on how many probes you will use, but logically, 1
> kprobe_insn_pages is allocated per 4096/16 = 256 probes. So, if
> you use 25,600 probes on your system, memory consumption will
> increase 400/800 bytes.
it's your call really - just wanted to react on the 'because it
should be used for hash tables' comment in the changelog.
Ingo
^ permalink raw reply [flat|nested] 14+ messages in thread* Re: [PATCH -tip 3/3] kprobes: cleanup: use list instead of hlist for insn_pages
2009-06-30 21:50 ` Ingo Molnar
@ 2009-06-30 23:12 ` Masami Hiramatsu
2009-06-30 23:18 ` Ingo Molnar
0 siblings, 1 reply; 14+ messages in thread
From: Masami Hiramatsu @ 2009-06-30 23:12 UTC (permalink / raw)
To: Ingo Molnar
Cc: Ananth N Mavinakayanahalli, lkml, systemtap, DLE, Jim Keniston
Ingo Molnar wrote:
> * Masami Hiramatsu <mhiramat@redhat.com> wrote:
>
>> Ingo Molnar wrote:
>>> * Masami Hiramatsu <mhiramat@redhat.com> wrote:
>>>
>>>> Use struct list instead of struct hlist for managing insn_pages,
>>>> because insn_pages doesn't use hash table.
>>>> struct kprobe_insn_page {
>>>> - struct hlist_node hlist;
>>>> + struct list_head list;
>>> Hm, you know that this increases the size of kprobe_insn_page by 4/8
>>> bytes, right?
>> Sure, that will increase size.
>>
>>> hlists are not just used for hashes - but also when we want a more
>>> compact / smaller list head.
>> Oh, I thought hlists are used for hash tables...
>
> ... because they are smaller, hence the hash table of list
> heads becomes twice as dense as with list_head.
>
> But otherwise it's an (almost) equivalent primitive to list_head,
> with a slightly higher runtime cost versus better RAM footprint.
>
>>> How many kprobe_insn_page's can be allocated in the system,
>>> maximally?
>> It's depends on how many probes you will use, but logically, 1
>> kprobe_insn_pages is allocated per 4096/16 = 256 probes. So, if
>> you use 25,600 probes on your system, memory consumption will
>> increase 400/800 bytes.
>
> it's your call really - just wanted to react on the 'because it
> should be used for hash tables' comment in the changelog.
Hi Ingo,
Would I might be misunderstood?
struct list_head {
struct list_head *next, *prev;
};
struct hlist_node {
struct hlist_node *next, **pprev;
};
Both of list_head and hlist_node are the same size...
--
Masami Hiramatsu
Software Engineer
Hitachi Computer Products (America), Inc.
Software Solutions Division
e-mail: mhiramat@redhat.com
^ permalink raw reply [flat|nested] 14+ messages in thread* Re: [PATCH -tip 3/3] kprobes: cleanup: use list instead of hlist for insn_pages
2009-06-30 23:12 ` Masami Hiramatsu
@ 2009-06-30 23:18 ` Ingo Molnar
0 siblings, 0 replies; 14+ messages in thread
From: Ingo Molnar @ 2009-06-30 23:18 UTC (permalink / raw)
To: Masami Hiramatsu
Cc: Ananth N Mavinakayanahalli, lkml, systemtap, DLE, Jim Keniston
* Masami Hiramatsu <mhiramat@redhat.com> wrote:
> Ingo Molnar wrote:
> > * Masami Hiramatsu <mhiramat@redhat.com> wrote:
> >
> >> Ingo Molnar wrote:
> >>> * Masami Hiramatsu <mhiramat@redhat.com> wrote:
> >>>
> >>>> Use struct list instead of struct hlist for managing insn_pages,
> >>>> because insn_pages doesn't use hash table.
> >>>> struct kprobe_insn_page {
> >>>> - struct hlist_node hlist;
> >>>> + struct list_head list;
> >>> Hm, you know that this increases the size of kprobe_insn_page by 4/8
> >>> bytes, right?
> >> Sure, that will increase size.
> >>
> >>> hlists are not just used for hashes - but also when we want a more
> >>> compact / smaller list head.
> >> Oh, I thought hlists are used for hash tables...
> >
> > ... because they are smaller, hence the hash table of list
> > heads becomes twice as dense as with list_head.
> >
> > But otherwise it's an (almost) equivalent primitive to list_head,
> > with a slightly higher runtime cost versus better RAM footprint.
> >
> >>> How many kprobe_insn_page's can be allocated in the system,
> >>> maximally?
> >> It's depends on how many probes you will use, but logically, 1
> >> kprobe_insn_pages is allocated per 4096/16 = 256 probes. So, if
> >> you use 25,600 probes on your system, memory consumption will
> >> increase 400/800 bytes.
> >
> > it's your call really - just wanted to react on the 'because it
> > should be used for hash tables' comment in the changelog.
>
> Hi Ingo,
>
> Would I might be misunderstood?
>
> struct list_head {
> struct list_head *next, *prev;
> };
>
> struct hlist_node {
> struct hlist_node *next, **pprev;
> };
>
> Both of list_head and hlist_node are the same size...
ahhh ... a light goes up: i read it as hlist_head, while it's
hlist_node.
You are right, hlist_node is a needless complication so your cleanup
is correct.
Ingo
^ permalink raw reply [flat|nested] 14+ messages in thread
* [tip:tracing/core] kprobes: Clean up insn_pages by using list instead of hlist
2009-06-30 21:08 ` [PATCH -tip 3/3] kprobes: cleanup: use list instead of hlist for insn_pages Masami Hiramatsu
2009-06-30 21:25 ` Ingo Molnar
@ 2009-06-30 23:27 ` tip-bot for Masami Hiramatsu
2009-07-01 8:47 ` tip-bot for Masami Hiramatsu
2 siblings, 0 replies; 14+ messages in thread
From: tip-bot for Masami Hiramatsu @ 2009-06-30 23:27 UTC (permalink / raw)
To: linux-tip-commits
Cc: linux-kernel, ananth, hpa, mingo, jkenisto, tglx, mhiramat, mingo
Commit-ID: aa621943d0058eb1c9a67c2d6bc9951d20335e87
Gitweb: http://git.kernel.org/tip/aa621943d0058eb1c9a67c2d6bc9951d20335e87
Author: Masami Hiramatsu <mhiramat@redhat.com>
AuthorDate: Tue, 30 Jun 2009 17:08:14 -0400
Committer: Ingo Molnar <mingo@elte.hu>
CommitDate: Wed, 1 Jul 2009 01:19:17 +0200
kprobes: Clean up insn_pages by using list instead of hlist
Use struct list instead of struct hlist for managing
insn_pages, because insn_pages doesn't use hash table.
Signed-off-by: Masami Hiramatsu <mhiramat@redhat.com>
Acked-by: Ananth N Mavinakayanahalli <ananth@in.ibm.com>
Cc: Ananth N Mavinakayanahalli <ananth@in.ibm.com>
Cc: Jim Keniston <jkenisto@us.ibm.com>
Cc: Ananth N Mavinakayanahalli <ananth@in.ibm.com>
LKML-Reference: <20090630210814.17851.64651.stgit@localhost.localdomain>
Signed-off-by: Ingo Molnar <mingo@elte.hu>
---
kernel/kprobes.c | 30 +++++++++++-------------------
1 files changed, 11 insertions(+), 19 deletions(-)
diff --git a/kernel/kprobes.c b/kernel/kprobes.c
index 16b5739..6fe9dc6 100644
--- a/kernel/kprobes.c
+++ b/kernel/kprobes.c
@@ -103,7 +103,7 @@ static struct kprobe_blackpoint kprobe_blacklist[] = {
#define INSNS_PER_PAGE (PAGE_SIZE/(MAX_INSN_SIZE * sizeof(kprobe_opcode_t)))
struct kprobe_insn_page {
- struct hlist_node hlist;
+ struct list_head list;
kprobe_opcode_t *insns; /* Page of instruction slots */
char slot_used[INSNS_PER_PAGE];
int nused;
@@ -117,7 +117,7 @@ enum kprobe_slot_state {
};
static DEFINE_MUTEX(kprobe_insn_mutex); /* Protects kprobe_insn_pages */
-static struct hlist_head kprobe_insn_pages;
+static LIST_HEAD(kprobe_insn_pages);
static int kprobe_garbage_slots;
static int collect_garbage_slots(void);
@@ -152,10 +152,9 @@ loop_end:
static kprobe_opcode_t __kprobes *__get_insn_slot(void)
{
struct kprobe_insn_page *kip;
- struct hlist_node *pos;
retry:
- hlist_for_each_entry(kip, pos, &kprobe_insn_pages, hlist) {
+ list_for_each_entry(kip, &kprobe_insn_pages, list) {
if (kip->nused < INSNS_PER_PAGE) {
int i;
for (i = 0; i < INSNS_PER_PAGE; i++) {
@@ -189,8 +188,8 @@ static kprobe_opcode_t __kprobes *__get_insn_slot(void)
kfree(kip);
return NULL;
}
- INIT_HLIST_NODE(&kip->hlist);
- hlist_add_head(&kip->hlist, &kprobe_insn_pages);
+ INIT_LIST_HEAD(&kip->list);
+ list_add(&kip->list, &kprobe_insn_pages);
memset(kip->slot_used, SLOT_CLEAN, INSNS_PER_PAGE);
kip->slot_used[0] = SLOT_USED;
kip->nused = 1;
@@ -219,12 +218,8 @@ static int __kprobes collect_one_slot(struct kprobe_insn_page *kip, int idx)
* so as not to have to set it up again the
* next time somebody inserts a probe.
*/
- hlist_del(&kip->hlist);
- if (hlist_empty(&kprobe_insn_pages)) {
- INIT_HLIST_NODE(&kip->hlist);
- hlist_add_head(&kip->hlist,
- &kprobe_insn_pages);
- } else {
+ if (!list_is_singular(&kprobe_insn_pages)) {
+ list_del(&kip->list);
module_free(NULL, kip->insns);
kfree(kip);
}
@@ -235,14 +230,13 @@ static int __kprobes collect_one_slot(struct kprobe_insn_page *kip, int idx)
static int __kprobes collect_garbage_slots(void)
{
- struct kprobe_insn_page *kip;
- struct hlist_node *pos, *next;
+ struct kprobe_insn_page *kip, *next;
/* Ensure no-one is preepmted on the garbages */
if (check_safety())
return -EAGAIN;
- hlist_for_each_entry_safe(kip, pos, next, &kprobe_insn_pages, hlist) {
+ list_for_each_entry_safe(kip, next, &kprobe_insn_pages, list) {
int i;
if (kip->ngarbage == 0)
continue;
@@ -260,19 +254,17 @@ static int __kprobes collect_garbage_slots(void)
void __kprobes free_insn_slot(kprobe_opcode_t * slot, int dirty)
{
struct kprobe_insn_page *kip;
- struct hlist_node *pos;
mutex_lock(&kprobe_insn_mutex);
- hlist_for_each_entry(kip, pos, &kprobe_insn_pages, hlist) {
+ list_for_each_entry(kip, &kprobe_insn_pages, list) {
if (kip->insns <= slot &&
slot < kip->insns + (INSNS_PER_PAGE * MAX_INSN_SIZE)) {
int i = (slot - kip->insns) / MAX_INSN_SIZE;
if (dirty) {
kip->slot_used[i] = SLOT_DIRTY;
kip->ngarbage++;
- } else {
+ } else
collect_one_slot(kip, i);
- }
break;
}
}
^ permalink raw reply related [flat|nested] 14+ messages in thread* [tip:tracing/core] kprobes: Clean up insn_pages by using list instead of hlist
2009-06-30 21:08 ` [PATCH -tip 3/3] kprobes: cleanup: use list instead of hlist for insn_pages Masami Hiramatsu
2009-06-30 21:25 ` Ingo Molnar
2009-06-30 23:27 ` [tip:tracing/core] kprobes: Clean up insn_pages by using list instead of hlist tip-bot for Masami Hiramatsu
@ 2009-07-01 8:47 ` tip-bot for Masami Hiramatsu
2 siblings, 0 replies; 14+ messages in thread
From: tip-bot for Masami Hiramatsu @ 2009-07-01 8:47 UTC (permalink / raw)
To: linux-tip-commits
Cc: linux-kernel, ananth, hpa, mingo, jkenisto, tglx, mhiramat, mingo
Commit-ID: c5cb5a2d8d7dc872cf1504091ad0e59fe5ff7cb5
Gitweb: http://git.kernel.org/tip/c5cb5a2d8d7dc872cf1504091ad0e59fe5ff7cb5
Author: Masami Hiramatsu <mhiramat@redhat.com>
AuthorDate: Tue, 30 Jun 2009 17:08:14 -0400
Committer: Ingo Molnar <mingo@elte.hu>
CommitDate: Wed, 1 Jul 2009 10:43:41 +0200
kprobes: Clean up insn_pages by using list instead of hlist
Use struct list instead of struct hlist for managing
insn_pages, because insn_pages doesn't use hash table.
Signed-off-by: Masami Hiramatsu <mhiramat@redhat.com>
Acked-by: Ananth N Mavinakayanahalli <ananth@in.ibm.com>
Cc: Ananth N Mavinakayanahalli <ananth@in.ibm.com>
Cc: Jim Keniston <jkenisto@us.ibm.com>
Cc: Ananth N Mavinakayanahalli <ananth@in.ibm.com>
LKML-Reference: <20090630210814.17851.64651.stgit@localhost.localdomain>
Signed-off-by: Ingo Molnar <mingo@elte.hu>
---
kernel/kprobes.c | 30 +++++++++++-------------------
1 files changed, 11 insertions(+), 19 deletions(-)
diff --git a/kernel/kprobes.c b/kernel/kprobes.c
index 16b5739..6fe9dc6 100644
--- a/kernel/kprobes.c
+++ b/kernel/kprobes.c
@@ -103,7 +103,7 @@ static struct kprobe_blackpoint kprobe_blacklist[] = {
#define INSNS_PER_PAGE (PAGE_SIZE/(MAX_INSN_SIZE * sizeof(kprobe_opcode_t)))
struct kprobe_insn_page {
- struct hlist_node hlist;
+ struct list_head list;
kprobe_opcode_t *insns; /* Page of instruction slots */
char slot_used[INSNS_PER_PAGE];
int nused;
@@ -117,7 +117,7 @@ enum kprobe_slot_state {
};
static DEFINE_MUTEX(kprobe_insn_mutex); /* Protects kprobe_insn_pages */
-static struct hlist_head kprobe_insn_pages;
+static LIST_HEAD(kprobe_insn_pages);
static int kprobe_garbage_slots;
static int collect_garbage_slots(void);
@@ -152,10 +152,9 @@ loop_end:
static kprobe_opcode_t __kprobes *__get_insn_slot(void)
{
struct kprobe_insn_page *kip;
- struct hlist_node *pos;
retry:
- hlist_for_each_entry(kip, pos, &kprobe_insn_pages, hlist) {
+ list_for_each_entry(kip, &kprobe_insn_pages, list) {
if (kip->nused < INSNS_PER_PAGE) {
int i;
for (i = 0; i < INSNS_PER_PAGE; i++) {
@@ -189,8 +188,8 @@ static kprobe_opcode_t __kprobes *__get_insn_slot(void)
kfree(kip);
return NULL;
}
- INIT_HLIST_NODE(&kip->hlist);
- hlist_add_head(&kip->hlist, &kprobe_insn_pages);
+ INIT_LIST_HEAD(&kip->list);
+ list_add(&kip->list, &kprobe_insn_pages);
memset(kip->slot_used, SLOT_CLEAN, INSNS_PER_PAGE);
kip->slot_used[0] = SLOT_USED;
kip->nused = 1;
@@ -219,12 +218,8 @@ static int __kprobes collect_one_slot(struct kprobe_insn_page *kip, int idx)
* so as not to have to set it up again the
* next time somebody inserts a probe.
*/
- hlist_del(&kip->hlist);
- if (hlist_empty(&kprobe_insn_pages)) {
- INIT_HLIST_NODE(&kip->hlist);
- hlist_add_head(&kip->hlist,
- &kprobe_insn_pages);
- } else {
+ if (!list_is_singular(&kprobe_insn_pages)) {
+ list_del(&kip->list);
module_free(NULL, kip->insns);
kfree(kip);
}
@@ -235,14 +230,13 @@ static int __kprobes collect_one_slot(struct kprobe_insn_page *kip, int idx)
static int __kprobes collect_garbage_slots(void)
{
- struct kprobe_insn_page *kip;
- struct hlist_node *pos, *next;
+ struct kprobe_insn_page *kip, *next;
/* Ensure no-one is preepmted on the garbages */
if (check_safety())
return -EAGAIN;
- hlist_for_each_entry_safe(kip, pos, next, &kprobe_insn_pages, hlist) {
+ list_for_each_entry_safe(kip, next, &kprobe_insn_pages, list) {
int i;
if (kip->ngarbage == 0)
continue;
@@ -260,19 +254,17 @@ static int __kprobes collect_garbage_slots(void)
void __kprobes free_insn_slot(kprobe_opcode_t * slot, int dirty)
{
struct kprobe_insn_page *kip;
- struct hlist_node *pos;
mutex_lock(&kprobe_insn_mutex);
- hlist_for_each_entry(kip, pos, &kprobe_insn_pages, hlist) {
+ list_for_each_entry(kip, &kprobe_insn_pages, list) {
if (kip->insns <= slot &&
slot < kip->insns + (INSNS_PER_PAGE * MAX_INSN_SIZE)) {
int i = (slot - kip->insns) / MAX_INSN_SIZE;
if (dirty) {
kip->slot_used[i] = SLOT_DIRTY;
kip->ngarbage++;
- } else {
+ } else
collect_one_slot(kip, i);
- }
break;
}
}
^ permalink raw reply related [flat|nested] 14+ messages in thread