This work was supported by a hardware donation from the CE Linux Forum.
Signed-off-by: Alessio Igor Bogani <[email protected]>
---
kernel/module.c | 6 ++----
1 files changed, 2 insertions(+), 4 deletions(-)
diff --git a/kernel/module.c b/kernel/module.c
index 6a34337..a1f841e 100644
--- a/kernel/module.c
+++ b/kernel/module.c
@@ -2055,10 +2055,8 @@ static const struct kernel_symbol *lookup_symbol(const char *name,
const struct kernel_symbol *stop)
{
const struct kernel_symbol *ks = start;
- for (; ks < stop; ks++)
- if (strcmp(ks->name, name) == 0)
- return ks;
- return NULL;
+ return bsearch(ks->name, start, stop - start,
+ sizeof(struct kernel_symbol), cmp_name);
}
static int is_exported(const char *name, unsigned long value,
--
1.7.4.1
On 03.05.2011 22:42, Alessio Igor Bogani wrote:
> This work was supported by a hardware donation from the CE Linux Forum.
>
> Signed-off-by: Alessio Igor Bogani<[email protected]>
> ---
> kernel/module.c | 6 ++----
> 1 files changed, 2 insertions(+), 4 deletions(-)
>
> diff --git a/kernel/module.c b/kernel/module.c
> index 6a34337..a1f841e 100644
> --- a/kernel/module.c
> +++ b/kernel/module.c
> @@ -2055,10 +2055,8 @@ static const struct kernel_symbol *lookup_symbol(const char *name,
> const struct kernel_symbol *stop)
> {
> const struct kernel_symbol *ks = start;
> - for (; ks< stop; ks++)
> - if (strcmp(ks->name, name) == 0)
> - return ks;
> - return NULL;
> + return bsearch(ks->name, start, stop - start,
> + sizeof(struct kernel_symbol), cmp_name);
> }
>
> static int is_exported(const char *name, unsigned long value,
How is this patch related to patch 4/4
http://marc.info/?l=linux-kernel&m=130296062420328&w=1
of the recently sent patch set? Is it a replacement? Or an add on to
this (i.e. patch #5)?
Many thanks
Dirk
Dear Mr. Behme,
2011/5/4 Dirk Behme <[email protected]>:
[...]
> How is this patch related to patch 4/4
>
> http://marc.info/?l=linux-kernel&m=130296062420328&w=1
>
> of the recently sent patch set? Is it a replacement? Or an add on to this
> (i.e. patch #5)?
Sorry it's my fault: This patch is an add on to that patch set.
Ciao,
Alessio
On 03.05.2011 22:42, Alessio Igor Bogani wrote:
> This work was supported by a hardware donation from the CE Linux Forum.
>
> Signed-off-by: Alessio Igor Bogani<[email protected]>
> ---
> kernel/module.c | 6 ++----
> 1 files changed, 2 insertions(+), 4 deletions(-)
>
> diff --git a/kernel/module.c b/kernel/module.c
> index 6a34337..a1f841e 100644
> --- a/kernel/module.c
> +++ b/kernel/module.c
> @@ -2055,10 +2055,8 @@ static const struct kernel_symbol *lookup_symbol(const char *name,
> const struct kernel_symbol *stop)
> {
> const struct kernel_symbol *ks = start;
> - for (; ks< stop; ks++)
> - if (strcmp(ks->name, name) == 0)
> - return ks;
> - return NULL;
> + return bsearch(ks->name, start, stop - start,
> + sizeof(struct kernel_symbol), cmp_name);
> }
Back porting this patch to a 2.6.34.9 based ARM system fails with an
Oops at 0x00000004. Debugging shows that both start and stop are 0 in
this case resulting in ks->name accessing 0x00000004. The original
code checked for this by 'ks < stop' in the for loop.
So the first idea was that the code should be
if(k < stop)
return bsearch();
else
return NULL;
Then, thinking again, results in the question if the first argument of
bsearch() shouldn't be 'name' rather than 'ks->name'? Then it would be
the job of cmp_name() to check for start == stop == 0? I.e.
return bsearch(name, ...);
?
Best regards
Dirk
On Mon, May 16, 2011 at 11:36, Dirk Behme <[email protected]> wrote:
> Then, thinking again, results in the question if the first argument of
> bsearch() shouldn't be 'name' rather than 'ks->name'?
Yes, it should be.
> Then it would be the job of cmp_name() to check for start == stop == 0?
Actually bsearch already handles this case correctly (it will make no
calls to cmp_name and return NULL), so nothing needs to specially
check for it.
Anders
This work was supported by a hardware donation from the CE Linux Forum.
Signed-off-by: Alessio Igor Bogani <[email protected]>
---
kernel/module.c | 6 ++----
1 files changed, 2 insertions(+), 4 deletions(-)
diff --git a/kernel/module.c b/kernel/module.c
index 6a34337..54355c5 100644
--- a/kernel/module.c
+++ b/kernel/module.c
@@ -2055,10 +2055,8 @@ static const struct kernel_symbol *lookup_symbol(const char *name,
const struct kernel_symbol *stop)
{
const struct kernel_symbol *ks = start;
- for (; ks < stop; ks++)
- if (strcmp(ks->name, name) == 0)
- return ks;
- return NULL;
+ return bsearch(name, start, stop - start,
+ sizeof(struct kernel_symbol), cmp_name);
}
static int is_exported(const char *name, unsigned long value,
--
1.7.4.1
On Mon, 2011-05-16 at 22:23 +0200, Alessio Igor Bogani wrote:
> This work was supported by a hardware donation from the CE Linux Forum.
>
> Signed-off-by: Alessio Igor Bogani <[email protected]>
> ---
> kernel/module.c | 6 ++----
> 1 files changed, 2 insertions(+), 4 deletions(-)
>
> diff --git a/kernel/module.c b/kernel/module.c
> index 6a34337..54355c5 100644
> --- a/kernel/module.c
> +++ b/kernel/module.c
> @@ -2055,10 +2055,8 @@ static const struct kernel_symbol *lookup_symbol(const char *name,
> const struct kernel_symbol *stop)
> {
> const struct kernel_symbol *ks = start;
> - for (; ks < stop; ks++)
> - if (strcmp(ks->name, name) == 0)
> - return ks;
> - return NULL;
> + return bsearch(name, start, stop - start,
> + sizeof(struct kernel_symbol), cmp_name);
> }
>
> static int is_exported(const char *name, unsigned long value,
ks isn't used anymore.
why cmp_name and not strcmp?
On Mon, 2011-05-16 at 14:01 -0700, Joe Perches wrote:
> On Mon, 2011-05-16 at 22:23 +0200, Alessio Igor Bogani wrote:
> > Signed-off-by: Alessio Igor Bogani <[email protected]>
> > diff --git a/kernel/module.c b/kernel/module.c
> > @@ -2055,10 +2055,8 @@ static const struct kernel_symbol *lookup_symbol(const char *name,
> > const struct kernel_symbol *stop)
> > {
> > const struct kernel_symbol *ks = start;
> > - for (; ks < stop; ks++)
> > - if (strcmp(ks->name, name) == 0)
> > - return ks;
> > - return NULL;
> > + return bsearch(name, start, stop - start,
> > + sizeof(struct kernel_symbol), cmp_name);
[]
> why cmp_name and not strcmp?
Nevermind, cmp_name is obviously correct.
On Mon, 16 May 2011 22:23:40 +0200, Alessio Igor Bogani <[email protected]> wrote:
> This work was supported by a hardware donation from the CE Linux Forum.
>
> Signed-off-by: Alessio Igor Bogani <[email protected]>
> ---
> kernel/module.c | 6 ++----
> 1 files changed, 2 insertions(+), 4 deletions(-)
>
> diff --git a/kernel/module.c b/kernel/module.c
> index 6a34337..54355c5 100644
> --- a/kernel/module.c
> +++ b/kernel/module.c
> @@ -2055,10 +2055,8 @@ static const struct kernel_symbol *lookup_symbol(const char *name,
> const struct kernel_symbol *stop)
> {
> const struct kernel_symbol *ks = start;
> - for (; ks < stop; ks++)
> - if (strcmp(ks->name, name) == 0)
> - return ks;
> - return NULL;
> + return bsearch(name, start, stop - start,
> + sizeof(struct kernel_symbol), cmp_name);
> }
>
> static int is_exported(const char *name, unsigned long value,
Applied.
Thanks!
Rusty.
On 17.05.2011 05:52, Rusty Russell wrote:
> On Mon, 16 May 2011 22:23:40 +0200, Alessio Igor Bogani<[email protected]> wrote:
>> This work was supported by a hardware donation from the CE Linux Forum.
>>
>> Signed-off-by: Alessio Igor Bogani<[email protected]>
>> ---
>> kernel/module.c | 6 ++----
>> 1 files changed, 2 insertions(+), 4 deletions(-)
>>
>> diff --git a/kernel/module.c b/kernel/module.c
>> index 6a34337..54355c5 100644
>> --- a/kernel/module.c
>> +++ b/kernel/module.c
>> @@ -2055,10 +2055,8 @@ static const struct kernel_symbol *lookup_symbol(const char *name,
>> const struct kernel_symbol *stop)
>> {
>> const struct kernel_symbol *ks = start;
>> - for (; ks< stop; ks++)
>> - if (strcmp(ks->name, name) == 0)
>> - return ks;
>> - return NULL;
>> + return bsearch(name, start, stop - start,
>> + sizeof(struct kernel_symbol), cmp_name);
>> }
>>
>> static int is_exported(const char *name, unsigned long value,
>
> Applied.
Sorry, but where have you applied it?
With the version above we should get a warning
kernel/module.c: In function 'lookup_symbol':
kernel/module.c:1809: warning: unused variable 'ks'
?
Best regards
Dirk
Dear Mr. Behme,
2011/5/17 Dirk Behme <[email protected]>:
[...]
> With the version above we should get a warning
>
> kernel/module.c: In function 'lookup_symbol':
> kernel/module.c:1809: warning: unused variable 'ks'
Sorry It's my fault. I'll provide a right version in few hours.
Ciao,
Alessio
This work was supported by a hardware donation from the CE Linux Forum.
Signed-off-by: Alessio Igor Bogani <[email protected]>
---
kernel/module.c | 7 ++-----
1 files changed, 2 insertions(+), 5 deletions(-)
diff --git a/kernel/module.c b/kernel/module.c
index 1e2b657..795bdc7 100644
--- a/kernel/module.c
+++ b/kernel/module.c
@@ -2055,11 +2055,8 @@ static const struct kernel_symbol *lookup_symbol(const char *name,
const struct kernel_symbol *start,
const struct kernel_symbol *stop)
{
- const struct kernel_symbol *ks = start;
- for (; ks < stop; ks++)
- if (strcmp(ks->name, name) == 0)
- return ks;
- return NULL;
+ return bsearch(name, start, stop - start,
+ sizeof(struct kernel_symbol), cmp_name);
}
static int is_exported(const char *name, unsigned long value,
--
1.7.4.1
On Tue, May 17, 2011 at 10:56:03PM +0200, Alessio Igor Bogani wrote:
> This work was supported by a hardware donation from the CE Linux Forum.
>
> Signed-off-by: Alessio Igor Bogani <[email protected]>
> ---
That's nice, but _why_ do this change? What does it buy us?
Please explain why you make a change, not just who sponsored the change,
that's not very interesting to developers.
thanks,
greg k-h
On 05/17/2011 04:22 PM, Greg KH wrote:
> On Tue, May 17, 2011 at 10:56:03PM +0200, Alessio Igor Bogani wrote:
>> This work was supported by a hardware donation from the CE Linux Forum.
>>
>> Signed-off-by: Alessio Igor Bogani <[email protected]>
>> ---
>
> That's nice, but _why_ do this change? What does it buy us?
>
> Please explain why you make a change, not just who sponsored the change,
> that's not very interesting to developers.
Just a note here on the attribution...
Alessio - you can remove the "hardware donation from CELF" line
after the first submission or so. It doesn't need to be on
every submission of the patch set, and it doesn't need to go into
the commit message for the patch set. We only want it associated
with the patch set somewhere Google-able (like LKML).
That said, I can answer Greg's question. This is to speed up
the symbol resolution on module loading. The last numbers I
saw showed a reduction of about 15-20% for the module load
time, for large-ish modules. Of course this is highly dependent
on the size of the modules, what they do at load time, and how many
symbols are looked up to link them into the kernel.
Alessio - do you have any timings you can share for the speedup?
-- Tim
=============================
Tim Bird
Architecture Group Chair, CE Workgroup of the Linux Foundation
Senior Staff Engineer, Sony Network Entertainment
=============================
On Tue, 17 May 2011 16:22:41 -0700, Greg KH <[email protected]> wrote:
> On Tue, May 17, 2011 at 10:56:03PM +0200, Alessio Igor Bogani wrote:
> > This work was supported by a hardware donation from the CE Linux Forum.
> >
> > Signed-off-by: Alessio Igor Bogani <[email protected]>
> > ---
>
> That's nice, but _why_ do this change? What does it buy us?
>
> Please explain why you make a change, not just who sponsored the change,
> that's not very interesting to developers.
I was going to let this pass, but since Greg flagged it...
It's sufficient given the context (it's the tail end of a series of
patches), but it's preferable to allude to the other patches in a case
like this. For example:
Now we have sorted symbols, we can use binary search for
kallsyms lookups as well.
(1) "Now we have sorted symbols" indicates to the reader that this has
just recently become possible.
(2) "as well." indicates that this was not the main justification for
sorting the symbols.
Ideally you would add some numbers, like so:
On my machine 'cat /proc/kallsyms' only takes 0.02 seconds, but
this halves it to 0.01 seconds.
(That's my results under kvm, which is a poor way to do timing, but you
get the idea).
Thanks,
Rusty.
On Tue, 17 May 2011 21:18:26 +0200, Dirk Behme <[email protected]> wrote:
> On 17.05.2011 05:52, Rusty Russell wrote:
> > On Mon, 16 May 2011 22:23:40 +0200, Alessio Igor Bogani<[email protected]> wrote:
> >> This work was supported by a hardware donation from the CE Linux Forum.
> >>
> >> Signed-off-by: Alessio Igor Bogani<[email protected]>
> >> ---
> >> kernel/module.c | 6 ++----
> >> 1 files changed, 2 insertions(+), 4 deletions(-)
> >>
> >> diff --git a/kernel/module.c b/kernel/module.c
> >> index 6a34337..54355c5 100644
> >> --- a/kernel/module.c
> >> +++ b/kernel/module.c
> >> @@ -2055,10 +2055,8 @@ static const struct kernel_symbol *lookup_symbol(const char *name,
> >> const struct kernel_symbol *stop)
> >> {
> >> const struct kernel_symbol *ks = start;
> >> - for (; ks< stop; ks++)
> >> - if (strcmp(ks->name, name) == 0)
> >> - return ks;
> >> - return NULL;
> >> + return bsearch(name, start, stop - start,
> >> + sizeof(struct kernel_symbol), cmp_name);
> >> }
> >>
> >> static int is_exported(const char *name, unsigned long value,
> >
> > Applied.
>
> Sorry, but where have you applied it?
The -rr tree which goes to linux-next.
> With the version above we should get a warning
>
> kernel/module.c: In function 'lookup_symbol':
> kernel/module.c:1809: warning: unused variable 'ks'
Yep, fixed that up too, thanks.
Cheers,
Rusty.
On Tue, May 17, 2011 at 04:33:07PM -0700, Tim Bird wrote:
> That said, I can answer Greg's question. This is to speed up
> the symbol resolution on module loading. The last numbers I
> saw showed a reduction of about 15-20% for the module load
> time, for large-ish modules. Of course this is highly dependent
> on the size of the modules, what they do at load time, and how many
> symbols are looked up to link them into the kernel.
How large are these very large modules, and what are good examples for
that? And why do people overly care for the load time?
On 17.05.2011 22:56, Alessio Igor Bogani wrote:
> This work was supported by a hardware donation from the CE Linux Forum.
>
> Signed-off-by: Alessio Igor Bogani<[email protected]>
> ---
> kernel/module.c | 7 ++-----
> 1 files changed, 2 insertions(+), 5 deletions(-)
>
> diff --git a/kernel/module.c b/kernel/module.c
> index 1e2b657..795bdc7 100644
> --- a/kernel/module.c
> +++ b/kernel/module.c
> @@ -2055,11 +2055,8 @@ static const struct kernel_symbol *lookup_symbol(const char *name,
> const struct kernel_symbol *start,
> const struct kernel_symbol *stop)
> {
> - const struct kernel_symbol *ks = start;
> - for (; ks< stop; ks++)
> - if (strcmp(ks->name, name) == 0)
> - return ks;
> - return NULL;
> + return bsearch(name, start, stop - start,
> + sizeof(struct kernel_symbol), cmp_name);
> }
>
> static int is_exported(const char *name, unsigned long value,
The old version with the warning is in linux-next now
http://git.kernel.org/?p=linux/kernel/git/next/linux-next.git;a=commitdiff;h=903996de9b35213aaa4162c24351a2cb2931d9ac
Best regards
Dirk
On 05/18/2011 12:54 AM, Christoph Hellwig wrote:
> On Tue, May 17, 2011 at 04:33:07PM -0700, Tim Bird wrote:
>> That said, I can answer Greg's question. This is to speed up
>> the symbol resolution on module loading. The last numbers I
>> saw showed a reduction of about 15-20% for the module load
>> time, for large-ish modules. Of course this is highly dependent
>> on the size of the modules, what they do at load time, and how many
>> symbols are looked up to link them into the kernel.
>
> How large are these very large modules, and what are good examples for
> that?
usbcore seems to be a large-ish module whose
load time is improved by this. More details follow:
I don't know the exact modules, but Alan Jenkins reported a .3
second reduction in overall boot time, on a EEE PC, presumably
running a stock Linux distribution, and loading 41 modules.
See http://lkml.org/lkml/2009/11/3/93
Carmelo Amoroso reported some good performance gains
in this presentation:
http://elinux.org/images/1/18/C_AMOROSO_Fast_lkm_loader_ELC-E_2009.pdf
(See slide 22).
He doesn't report the overall time savings, and
he was using a different method (hash tables as opposed to
binary search), but I believe the results are comparable
to what the binary search enhancement provides.
The biggest offenders in his testing were usbcore,
ehci_hcd and ohci_hcd.
> And why do people overly care for the load time?
To reduce overall boot time.
-- Tim
=============================
Tim Bird
Architecture Group Chair, CE Workgroup of the Linux Foundation
Senior Staff Engineer, Sony Network Entertainment
=============================
Dear Mr. Bird, Dear Mr. Kroah-Hartman,
Sorry for my very bad English.
2011/5/18 Tim Bird <[email protected]>:
[...]
> Alessio - do you have any timings you can share for the speedup?
You can find a little benchmark using ftrace at end of this email:
https://lkml.org/lkml/2011/4/5/341
> On 05/17/2011 04:22 PM, Greg KH wrote:
>> On Tue, May 17, 2011 at 10:56:03PM +0200, Alessio Igor Bogani wrote:
>>> This work was supported by a hardware donation from the CE Linux Forum.
[...]
>> Please explain why you make a change, not just who sponsored the change,
>> that's not very interesting to developers.
You are right. I apologize.
This patch is a missing piece (not essential it is only a further little
optimization) of this little patchset:
https://lkml.org/lkml/2011/4/16/48
Unfortunately I forgot to include this patch in the series (my first error)
then I avoided explaining the changes because I had thought that those were
already enough explained in the cover-letter of the patchset (my second error).
Sorry for my mistakes.
Is this better?
Subject: [PATCH] module: Use binary search in lookup_symbol()
The function is_exported() with its helper function lookup_symbol() are used to
verify if a provided symbol is effectively exported by the kernel or by the
modules. Now that both have their symbols sorted we can replace a linear search
with a binary search which provide a considerably speed-up.
This work was supported by a hardware donation from the CE Linux Forum.
Signed-off-by: Alessio Igor Bogani <[email protected]>
---
kernel/module.c | 7 ++-----
1 files changed, 2 insertions(+), 5 deletions(-)
diff --git a/kernel/module.c b/kernel/module.c
index 1e2b657..795bdc7 100644
--- a/kernel/module.c
+++ b/kernel/module.c
@@ -2055,11 +2055,8 @@ static const struct kernel_symbol *lookup_symbol(const char *name,
const struct kernel_symbol *start,
const struct kernel_symbol *stop)
{
- const struct kernel_symbol *ks = start;
- for (; ks < stop; ks++)
- if (strcmp(ks->name, name) == 0)
- return ks;
- return NULL;
+ return bsearch(name, start, stop - start,
+ sizeof(struct kernel_symbol), cmp_name);
}
static int is_exported(const char *name, unsigned long value,
--
Thank you very much!
Ciao,
Alessio
On Wed, May 18, 2011 at 10:00:12AM -0700, Tim Bird wrote:
> On 05/18/2011 12:54 AM, Christoph Hellwig wrote:
> > On Tue, May 17, 2011 at 04:33:07PM -0700, Tim Bird wrote:
> >> That said, I can answer Greg's question. This is to speed up
> >> the symbol resolution on module loading. The last numbers I
> >> saw showed a reduction of about 15-20% for the module load
> >> time, for large-ish modules. Of course this is highly dependent
> >> on the size of the modules, what they do at load time, and how many
> >> symbols are looked up to link them into the kernel.
> >
> > How large are these very large modules, and what are good examples for
> > that?
>
> usbcore seems to be a large-ish module whose
> load time is improved by this. More details follow:
Then add the module to the kernel image, that's what a lot of distros do
now to solve this issue.
> I don't know the exact modules, but Alan Jenkins reported a .3
> second reduction in overall boot time, on a EEE PC, presumably
> running a stock Linux distribution, and loading 41 modules.
>
> See http://lkml.org/lkml/2009/11/3/93
That's good to know.
> Carmelo Amoroso reported some good performance gains
> in this presentation:
> http://elinux.org/images/1/18/C_AMOROSO_Fast_lkm_loader_ELC-E_2009.pdf
> (See slide 22).
>
> He doesn't report the overall time savings, and
> he was using a different method (hash tables as opposed to
> binary search), but I believe the results are comparable
> to what the binary search enhancement provides.
>
> The biggest offenders in his testing were usbcore,
> ehci_hcd and ohci_hcd.
Why those? The size of them, or something else? They don't seem to
have very many symbols they need to look up compared to anything else
that I can tell.
Is something else going on here due to the serialization of the USB
drivers themselves?
> > And why do people overly care for the load time?
>
> To reduce overall boot time.
To reduce it even more, build the modules into the kernel :)
I'm not saying I object to this patch, I just want a whole lot more
information in it when submitted as currently there was no justification
for the change at all.
thanks,
greg k-h
On Wed, May 18, 2011 at 08:55:25PM +0200, Alessio Igor Bogani wrote:
> Dear Mr. Bird, Dear Mr. Kroah-Hartman,
>
> Sorry for my very bad English.
>
> 2011/5/18 Tim Bird <[email protected]>:
> [...]
> > Alessio - do you have any timings you can share for the speedup?
>
> You can find a little benchmark using ftrace at end of this email:
> https://lkml.org/lkml/2011/4/5/341
>
> > On 05/17/2011 04:22 PM, Greg KH wrote:
> >> On Tue, May 17, 2011 at 10:56:03PM +0200, Alessio Igor Bogani wrote:
> >>> This work was supported by a hardware donation from the CE Linux Forum.
> [...]
> >> Please explain why you make a change, not just who sponsored the change,
> >> that's not very interesting to developers.
>
> You are right. I apologize.
>
> This patch is a missing piece (not essential it is only a further little
> optimization) of this little patchset:
> https://lkml.org/lkml/2011/4/16/48
>
> Unfortunately I forgot to include this patch in the series (my first error)
> then I avoided explaining the changes because I had thought that those were
> already enough explained in the cover-letter of the patchset (my second error).
>
> Sorry for my mistakes.
>
> Is this better?
>
> Subject: [PATCH] module: Use binary search in lookup_symbol()
>
> The function is_exported() with its helper function lookup_symbol() are used to
> verify if a provided symbol is effectively exported by the kernel or by the
> modules. Now that both have their symbols sorted we can replace a linear search
> with a binary search which provide a considerably speed-up.
>
> This work was supported by a hardware donation from the CE Linux Forum.
>
> Signed-off-by: Alessio Igor Bogani <[email protected]>
Much better, I have no objection to this at all.
Acked-by: Greg Kroah-Hartman <[email protected]>
Care to resend it without all the stuff above so someone (Rusty I guess)
can apply it?
thanks,
greg k-h
Dear Mr. Kroah-Hartman,
2011/5/18 Greg KH <[email protected]>:
[...]
> Care to resend it without all the stuff above so someone (Rusty I guess)
> can apply it?
Sure! It'll follow in few minutes.
Thank you very much!
Ciao,
Alessio
The function is_exported() with its helper function lookup_symbol() are used to
verify if a provided symbol is effectively exported by the kernel or by the
modules. Now that both have their symbols sorted we can replace a linear search
with a binary search which provide a considerably speed-up.
This work was supported by a hardware donation from the CE Linux Forum.
Signed-off-by: Alessio Igor Bogani <[email protected]>
Acked-by: Greg Kroah-Hartman <[email protected]>
---
kernel/module.c | 7 ++-----
1 files changed, 2 insertions(+), 5 deletions(-)
diff --git a/kernel/module.c b/kernel/module.c
index 1e2b657..795bdc7 100644
--- a/kernel/module.c
+++ b/kernel/module.c
@@ -2055,11 +2055,8 @@ static const struct kernel_symbol *lookup_symbol(const char *name,
const struct kernel_symbol *start,
const struct kernel_symbol *stop)
{
- const struct kernel_symbol *ks = start;
- for (; ks < stop; ks++)
- if (strcmp(ks->name, name) == 0)
- return ks;
- return NULL;
+ return bsearch(name, start, stop - start,
+ sizeof(struct kernel_symbol), cmp_name);
}
static int is_exported(const char *name, unsigned long value,
--
1.7.4.1
On 05/18/2011 12:21 PM, Greg KH wrote:
> On Wed, May 18, 2011 at 10:00:12AM -0700, Tim Bird wrote:
>> Carmelo Amoroso reported some good performance gains
>> in this presentation:
>> http://elinux.org/images/1/18/C_AMOROSO_Fast_lkm_loader_ELC-E_2009.pdf
>> (See slide 22).
>>
>> He doesn't report the overall time savings, and
>> he was using a different method (hash tables as opposed to
>> binary search), but I believe the results are comparable
>> to what the binary search enhancement provides.
>>
>> The biggest offenders in his testing were usbcore,
>> ehci_hcd and ohci_hcd.
>
> Why those? The size of them, or something else? They don't seem to
> have very many symbols they need to look up compared to anything else
> that I can tell.
>
> Is something else going on here due to the serialization of the USB
> drivers themselves?
I don't think there's anything wrong with these, compared to
other kernel modules. I just think they stood out (probably
because of size) from the other modules in the small set that
Carmelo tested. In his tests, usbcore was the largest module
by an order of magnitude.
>>> And why do people overly care for the load time?
>>
>> To reduce overall boot time.
>
> To reduce it even more, build the modules into the kernel :)
That's what I do most of the time. For some projects,
it is useful to build certain things as modules so you can
defer initializing them until later in the boot sequence.
You can get some critical user-space tasks running, then
come back later to initialize USB and other drivers.
On cameras, it's not uncommon to want to get to user
space in the first 500 milliseconds.
Sony has some code which allows us to both statically link
drivers and defer their initialization, but it's kind of
kludgy and requires modifying the module declarations
for the code you want to defer. Let me know if you think
this is worth doing an RFC about.
-- Tim
=============================
Tim Bird
Architecture Group Chair, CE Workgroup of the Linux Foundation
Senior Staff Engineer, Sony Network Entertainment
=============================
On Wed, May 18, 2011 at 02:10:15PM -0700, Tim Bird wrote:
> >>> And why do people overly care for the load time?
> >>
> >> To reduce overall boot time.
> >
> > To reduce it even more, build the modules into the kernel :)
>
> That's what I do most of the time. For some projects,
> it is useful to build certain things as modules so you can
> defer initializing them until later in the boot sequence.
> You can get some critical user-space tasks running, then
> come back later to initialize USB and other drivers.
> On cameras, it's not uncommon to want to get to user
> space in the first 500 milliseconds.
That's common even on desktops and servers, and using the bootchart code
in the kernel helps find those bottlenecks.
> Sony has some code which allows us to both statically link
> drivers and defer their initialization, but it's kind of
> kludgy and requires modifying the module declarations
> for the code you want to defer. Let me know if you think
> this is worth doing an RFC about.
I don't think that's worth it, there has been talk, and some initial
code, about adding kernel modules to the kernel image itself, which
would solve a lot of the i/o time of loading modules, and solves some
other boot speed problems. That work was done by Jeff Mahoney, but I
think he ran into some "interesting" linker issues and had to shelve it
due to a lack of time :(
thanks,
greg k-h
On Wed, 18 May 2011 17:26:56 +0200, Dirk Behme <[email protected]> wrote:
> The old version with the warning is in linux-next now
>
> http://git.kernel.org/?p=linux/kernel/git/next/linux-next.git;a=commitdiff;h=903996de9b35213aaa4162c24351a2cb2931d9ac
Yep, I switched to the new one after sfr's pull.
Then I switched to the enhanced-comments one just now, but if Linus was
quick to pull he'll have the undercommented version rather than the
overcommented one.
Cheers,
Rusty.
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
On 05/18/2011 05:34 PM, Greg KH wrote:
> On Wed, May 18, 2011 at 02:10:15PM -0700, Tim Bird wrote:
>>>>> And why do people overly care for the load time?
>>>>
>>>> To reduce overall boot time.
>>>
>>> To reduce it even more, build the modules into the kernel :)
>>
>> That's what I do most of the time. For some projects,
>> it is useful to build certain things as modules so you can
>> defer initializing them until later in the boot sequence.
>> You can get some critical user-space tasks running, then
>> come back later to initialize USB and other drivers.
>> On cameras, it's not uncommon to want to get to user
>> space in the first 500 milliseconds.
>
> That's common even on desktops and servers, and using the bootchart code
> in the kernel helps find those bottlenecks.
>
>> Sony has some code which allows us to both statically link
>> drivers and defer their initialization, but it's kind of
>> kludgy and requires modifying the module declarations
>> for the code you want to defer. Let me know if you think
>> this is worth doing an RFC about.
>
> I don't think that's worth it, there has been talk, and some initial
> code, about adding kernel modules to the kernel image itself, which
> would solve a lot of the i/o time of loading modules, and solves some
> other boot speed problems. That work was done by Jeff Mahoney, but I
> think he ran into some "interesting" linker issues and had to shelve it
> due to a lack of time :(
I had a few attempts at this before I had to move on to other things. I
haven't gotten a chance to take another look.
I had two approaches:
1) Statically link in modules post-build. This actually worked but had
some large caveats. The first was that an un-relocated image (vmlinux.o)
was needed in order to make it work and a ~ 200 MB footprint to gain a
fairly small win in boot time didn't seem like a good tradeoff. The
other issue was more important and is what made me abandon this
approach: If the entire image is re-linked then the debuginfo package
that we as a distributor offer but don't typically install becomes
invalid. Our support teams would not be too thrilled with the idea of
crash dumps that can't be used.
2) Build a "megamodule" that is loaded like an initramfs but is already
internally linked and requires no additional userspace. I got the
megamodule creation working but didn't get the loading aspect of it done
yet.
In both cases, I added the regular initcall sections to the modules in
addition to the module sections so they'd be loaded in the order they
would have been if they were actually statically linked.
I hadn't thought about it until now and it may not actually work, but it
could be possible to use the megamodule approach *and* link it into a
static vmlinux image as an appended section that's optionally used.
- -Jeff
- --
Jeff Mahoney
SUSE Labs
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.17 (GNU/Linux)
Comment: Using GnuPG with SUSE - http://enigmail.mozdev.org/
iEYEARECAAYFAk3Vde8ACgkQLPWxlyuTD7LxPgCeIuBHX+KnedsMzBz3H8JrwsGG
etgAn0J5tEwjnTFuIWFLdhzR9QHpSmq5
=Jtc/
-----END PGP SIGNATURE-----
On 05/19/2011 12:56 PM, Jeff Mahoney wrote:
> On 05/18/2011 05:34 PM, Greg KH wrote:
>> I don't think that's worth it, there has been talk, and some initial
>> code, about adding kernel modules to the kernel image itself, which
>> would solve a lot of the i/o time of loading modules, and solves some
>> other boot speed problems. That work was done by Jeff Mahoney, but I
>> think he ran into some "interesting" linker issues and had to shelve it
>> due to a lack of time :(
>
> I had a few attempts at this before I had to move on to other things. I
> haven't gotten a chance to take another look.
>
> I had two approaches:
>
> 1) Statically link in modules post-build. This actually worked but had
> some large caveats. The first was that an un-relocated image (vmlinux.o)
> was needed in order to make it work and a ~ 200 MB footprint to gain a
> fairly small win in boot time didn't seem like a good tradeoff. The
> other issue was more important and is what made me abandon this
> approach: If the entire image is re-linked then the debuginfo package
> that we as a distributor offer but don't typically install becomes
> invalid. Our support teams would not be too thrilled with the idea of
> crash dumps that can't be used.
>
> 2) Build a "megamodule" that is loaded like an initramfs but is already
> internally linked and requires no additional userspace. I got the
> megamodule creation working but didn't get the loading aspect of it done
> yet.
>
> In both cases, I added the regular initcall sections to the modules in
> addition to the module sections so they'd be loaded in the order they
> would have been if they were actually statically linked.
>
> I hadn't thought about it until now and it may not actually work, but it
> could be possible to use the megamodule approach *and* link it into a
> static vmlinux image as an appended section that's optionally used.
What was the use case for this? My use case is that I want
to use all the modules compiled into the kernel, but I don't
want to run some modules' initcalls until well after kernel
and user-space startup.
My solution is very simple - create a new initcall macro for
the initcalls I want to defer, along with a new 'deferred' initcall
section where the function entries can be accumulated. Then,
I avoid freeing init memory at standard initcall time. Once
the main user-space has initialized, it echos to a /proc file
to cause the deferred initcalls to be called, and the init memory
to be freed.
I'm attaching the patch below, because it's short enough to
see what's going on without a lot of digging.
This method eliminates the linking cost for module loading,
saves the memory overhead of the ELF module format, and gives
me control over when the deferred modules will be initialized.
The big downside is that you have to manually change the definition
for the initcall from 'module_init' to 'deferred_module_init'
for the modules you want to defer. Maybe there's a simple way
to control this with a kernel config? That would make this a pretty
nice, generic, system for deferring module initialization, IMHO.
If your use case is that you want all the modules present, but
want to initialize only some of them later, then maybe a list of
module names could be passed into the /proc interface, and the
routine could selectively initialize the deferred modules.
Patch (for 2.6.27 I believe) follows. This is for discussion
only, I wouldn't expect it to apply to mainline.
commit 1fab0d6a932d000780cd232b7d10ebfbe69f477c
Author: Tim Bird <[email protected]>
Date: Fri Sep 12 11:31:52 2008 -0700
Add deferred_module_init
This allows statically linked modules to be initialized sometime after
the initial bootstrap. To do this, change the module_init() macro
to deferred_module_init(), for those init routines you want to defer.
Signed-off-by: Tim Bird <[email protected]>
diff --git a/arch/x86/kernel/vmlinux_32.lds.S b/arch/x86/kernel/vmlinux_32.lds.S
index a9b8560..f5bdfc4 100644
--- a/arch/x86/kernel/vmlinux_32.lds.S
+++ b/arch/x86/kernel/vmlinux_32.lds.S
@@ -140,11 +140,21 @@ SECTIONS
*(.con_initcall.init)
__con_initcall_end = .;
}
+ .deferred_initcall.init : AT(ADDR(.deferred_initcall.init) - LOAD_OFFSET) {
+ __def_initcall_start = .;
+ *(.deferred_initcall.init)
+ __def_initcall_end = .;
+ }
.x86_cpu_dev.init : AT(ADDR(.x86_cpu_dev.init) - LOAD_OFFSET) {
__x86_cpu_dev_start = .;
*(.x86_cpu_dev.init)
__x86_cpu_dev_end = .;
}
+ .x86cpuvendor.init : AT(ADDR(.x86cpuvendor.init) - LOAD_OFFSET) {
+ __x86cpuvendor_start = .;
+ *(.x86cpuvendor.init)
+ __x86cpuvendor_end = .;
+ }
SECURITY_INIT
. = ALIGN(4);
.altinstructions : AT(ADDR(.altinstructions) - LOAD_OFFSET) {
diff --git a/fs/proc/proc_misc.c b/fs/proc/proc_misc.c
index 59ea42e..a247a8e 100644
--- a/fs/proc/proc_misc.c
+++ b/fs/proc/proc_misc.c
@@ -703,6 +703,22 @@ static int execdomains_read_proc(char *page, char **start, off_t off,
return proc_calc_metrics(page, start, off, count, eof, len);
}
+extern void do_deferred_initcalls(void);
+
+static int deferred_initcalls_read_proc(char *page, char **start, off_t off,
+ int count, int *eof, void *data)
+{
+ static int deferred_initcalls_done = 0;
+ int len;
+
+ len = sprintf(page, "%d\n", deferred_initcalls_done);
+ if (! deferred_initcalls_done) {
+ do_deferred_initcalls();
+ deferred_initcalls_done = 1;
+ }
+ return proc_calc_metrics(page, start, off, count, eof, len);
+}
+
#ifdef CONFIG_PROC_PAGE_MONITOR
#define KPMSIZE sizeof(u64)
#define KPMMASK (KPMSIZE - 1)
@@ -855,6 +871,7 @@ void __init proc_misc_init(void)
{"filesystems", filesystems_read_proc},
{"cmdline", cmdline_read_proc},
{"execdomains", execdomains_read_proc},
+ {"deferred_initcalls", deferred_initcalls_read_proc},
{NULL,}
};
for (p = simple_ones; p->name; p++)
diff --git a/include/linux/init.h b/include/linux/init.h
index ad63824..ef61767 100644
--- a/include/linux/init.h
+++ b/include/linux/init.h
@@ -200,6 +200,7 @@ extern void (*late_time_init)(void);
#define device_initcall_sync(fn) __define_initcall("6s",fn,6s)
#define late_initcall(fn) __define_initcall("7",fn,7)
#define late_initcall_sync(fn) __define_initcall("7s",fn,7s)
+//#define deferred_initcall(fn) __define_initcall("8",fn,8)
#define __initcall(fn) device_initcall(fn)
@@ -214,6 +215,10 @@ extern void (*late_time_init)(void);
static initcall_t __initcall_##fn \
__used __section(.security_initcall.init) = fn
+#define deferred_initcall(fn) \
+ static initcall_t __initcall_##fn \
+ __used __section(.deferred_initcall.init) = fn
+
struct obs_kernel_param {
const char *str;
int (*setup_func)(char *);
@@ -254,6 +259,7 @@ void __init parse_early_param(void);
* be one per module.
*/
#define module_init(x) __initcall(x);
+#define deferred_module_init(x) deferred_initcall(x);
/**
* module_exit() - driver exit entry point
diff --git a/init/main.c b/init/main.c
index 27f6bf6..e4bbdb2 100644
--- a/init/main.c
+++ b/init/main.c
@@ -789,12 +789,40 @@ static void run_init_process(char *init_filename)
kernel_execve(init_filename, argv_init, envp_init);
}
+extern initcall_t __def_initcall_start[], __def_initcall_end[];
+
+/* call deferred init routines */
+void do_deferred_initcalls(void)
+{
+ initcall_t *call;
+ static int already_run=0;
+
+ if (already_run) {
+ printk("do_deferred_initcalls() has already run\n");
+ return;
+ }
+
+ already_run=1;
+
+ printk("Running do_deferred_initcalls()\n");
+
+ lock_kernel(); /* make environment similar to early boot */
+
+ for(call = __def_initcall_start; call < __def_initcall_end; call++)
+ do_one_initcall(*call);
+
+ flush_scheduled_work();
+
+ free_initmem();
+ unlock_kernel();
+}
+
/* This is a non __init function. Force it to be noinline otherwise gcc
* makes it inline to init() and it becomes part of init.text section
*/
static int noinline init_post(void)
{
- free_initmem();
+ //free_initmem();
unlock_kernel();
mark_rodata_ro();
system_state = SYSTEM_RUNNING;
=============================
Tim Bird
Architecture Group Chair, CE Workgroup of the Linux Foundation
Senior Staff Engineer, Sony Network Entertainment
=============================
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
On 05/20/2011 05:29 PM, Tim Bird wrote:
> On 05/19/2011 12:56 PM, Jeff Mahoney wrote:
>> On 05/18/2011 05:34 PM, Greg KH wrote:
>>> I don't think that's worth it, there has been talk, and some initial
>>> code, about adding kernel modules to the kernel image itself, which
>>> would solve a lot of the i/o time of loading modules, and solves some
>>> other boot speed problems. That work was done by Jeff Mahoney, but I
>>> think he ran into some "interesting" linker issues and had to shelve it
>>> due to a lack of time :(
>>
>> I had a few attempts at this before I had to move on to other things. I
>> haven't gotten a chance to take another look.
>>
>> I had two approaches:
>>
>> 1) Statically link in modules post-build. This actually worked but had
>> some large caveats. The first was that an un-relocated image (vmlinux.o)
>> was needed in order to make it work and a ~ 200 MB footprint to gain a
>> fairly small win in boot time didn't seem like a good tradeoff. The
>> other issue was more important and is what made me abandon this
>> approach: If the entire image is re-linked then the debuginfo package
>> that we as a distributor offer but don't typically install becomes
>> invalid. Our support teams would not be too thrilled with the idea of
>> crash dumps that can't be used.
>>
>> 2) Build a "megamodule" that is loaded like an initramfs but is already
>> internally linked and requires no additional userspace. I got the
>> megamodule creation working but didn't get the loading aspect of it done
>> yet.
>>
>> In both cases, I added the regular initcall sections to the modules in
>> addition to the module sections so they'd be loaded in the order they
>> would have been if they were actually statically linked.
>>
>> I hadn't thought about it until now and it may not actually work, but it
>> could be possible to use the megamodule approach *and* link it into a
>> static vmlinux image as an appended section that's optionally used.
>
>
> What was the use case for this? My use case is that I want
> to use all the modules compiled into the kernel, but I don't
> want to run some modules' initcalls until well after kernel
> and user-space startup.
>
> My solution is very simple - create a new initcall macro for
> the initcalls I want to defer, along with a new 'deferred' initcall
> section where the function entries can be accumulated. Then,
> I avoid freeing init memory at standard initcall time. Once
> the main user-space has initialized, it echos to a /proc file
> to cause the deferred initcalls to be called, and the init memory
> to be freed.
>
> I'm attaching the patch below, because it's short enough to
> see what's going on without a lot of digging.
>
> This method eliminates the linking cost for module loading,
> saves the memory overhead of the ELF module format, and gives
> me control over when the deferred modules will be initialized.
> The big downside is that you have to manually change the definition
> for the initcall from 'module_init' to 'deferred_module_init'
> for the modules you want to defer. Maybe there's a simple way
> to control this with a kernel config? That would make this a pretty
> nice, generic, system for deferring module initialization, IMHO.
>
> If your use case is that you want all the modules present, but
> want to initialize only some of them later, then maybe a list of
> module names could be passed into the /proc interface, and the
> routine could selectively initialize the deferred modules.
Yep, it seems like we were going after different use cases. Mine was to
eliminate the initramfs except where userspace portions of it are needed.
We improved the boot time of the openSUSE kernel by statically linking
the most popular drivers into the kernel. I'm not a fan of that approach
for a generic distribution kernel but you can't argue with the numbers.
In the ideal case, the initcalls would happen in the same order they
would if they were statically linked in. Wed get the boot speed of a
static kernel with the flexibility advantages of shipping modules.
Your approach might ultimately dovetail nicely into that but since I
didn't have the time to get something functional, I don't have numbers
of my own.
- -Jeff
- --
Jeff Mahoney
SuSE Labs
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.16 (GNU/Linux)
Comment: Using GnuPG with SUSE - http://enigmail.mozdev.org/
iEYEARECAAYFAk3XyvYACgkQLPWxlyuTD7LlYwCgmQv86e0lxu6e5mfvwcevAIDb
7nwAn1jb6694mQ+vkcVD0bDsrKvQXOV1
=Q5xL
-----END PGP SIGNATURE-----