* [PATCH] module: Use binary search in lookup_symbol() @ 2011-05-03 20:42 Alessio Igor Bogani 2011-05-04 15:34 ` Dirk Behme 2011-05-16 15:36 ` Dirk Behme 0 siblings, 2 replies; 30+ messages in thread From: Alessio Igor Bogani @ 2011-05-03 20:42 UTC (permalink / raw) To: Rusty Russell Cc: Tim Abbott, Anders Kaseorg, Tim Bird, LKML, Linux Embedded, Jason Wessel, Alessio Igor Bogani This work was supported by a hardware donation from the CE Linux Forum. Signed-off-by: Alessio Igor Bogani <abogani@kernel.org> --- 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 ^ permalink raw reply related [flat|nested] 30+ messages in thread
* Re: [PATCH] module: Use binary search in lookup_symbol() 2011-05-03 20:42 [PATCH] module: Use binary search in lookup_symbol() Alessio Igor Bogani @ 2011-05-04 15:34 ` Dirk Behme 2011-05-04 17:30 ` Alessio Igor Bogani 2011-05-16 15:36 ` Dirk Behme 1 sibling, 1 reply; 30+ messages in thread From: Dirk Behme @ 2011-05-04 15:34 UTC (permalink / raw) To: Alessio Igor Bogani Cc: Rusty Russell, Tim Abbott, Anders Kaseorg, Tim Bird, LKML, Linux Embedded, Jason Wessel 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<abogani@kernel.org> > --- > 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 ^ permalink raw reply [flat|nested] 30+ messages in thread
* Re: [PATCH] module: Use binary search in lookup_symbol() 2011-05-04 15:34 ` Dirk Behme @ 2011-05-04 17:30 ` Alessio Igor Bogani 0 siblings, 0 replies; 30+ messages in thread From: Alessio Igor Bogani @ 2011-05-04 17:30 UTC (permalink / raw) To: Dirk Behme Cc: Rusty Russell, Tim Abbott, Anders Kaseorg, Tim Bird, LKML, Linux Embedded, Jason Wessel Dear Mr. Behme, 2011/5/4 Dirk Behme <dirk.behme@googlemail.com>: [...] > 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 ^ permalink raw reply [flat|nested] 30+ messages in thread
* Re: [PATCH] module: Use binary search in lookup_symbol() 2011-05-03 20:42 [PATCH] module: Use binary search in lookup_symbol() Alessio Igor Bogani 2011-05-04 15:34 ` Dirk Behme @ 2011-05-16 15:36 ` Dirk Behme 2011-05-16 18:02 ` Anders Kaseorg 1 sibling, 1 reply; 30+ messages in thread From: Dirk Behme @ 2011-05-16 15:36 UTC (permalink / raw) To: Alessio Igor Bogani Cc: Rusty Russell, Tim Abbott, Anders Kaseorg, Tim Bird, LKML, Linux Embedded, Jason Wessel 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<abogani@kernel.org> > --- > 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 ^ permalink raw reply [flat|nested] 30+ messages in thread
* Re: [PATCH] module: Use binary search in lookup_symbol() 2011-05-16 15:36 ` Dirk Behme @ 2011-05-16 18:02 ` Anders Kaseorg 2011-05-16 20:23 ` Alessio Igor Bogani 0 siblings, 1 reply; 30+ messages in thread From: Anders Kaseorg @ 2011-05-16 18:02 UTC (permalink / raw) To: Dirk Behme Cc: Alessio Igor Bogani, Rusty Russell, Tim Abbott, Tim Bird, LKML, Linux Embedded, Jason Wessel On Mon, May 16, 2011 at 11:36, Dirk Behme <dirk.behme@googlemail.com> 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 ^ permalink raw reply [flat|nested] 30+ messages in thread
* [PATCH] module: Use binary search in lookup_symbol() 2011-05-16 18:02 ` Anders Kaseorg @ 2011-05-16 20:23 ` Alessio Igor Bogani 2011-05-16 21:01 ` Joe Perches 2011-05-17 3:52 ` Rusty Russell 0 siblings, 2 replies; 30+ messages in thread From: Alessio Igor Bogani @ 2011-05-16 20:23 UTC (permalink / raw) To: Rusty Russell Cc: Anders Kaseorg, Tim Abbott, Tim Bird, LKML, Linux Embedded, Jason Wessel, Dirk Behme, Alessio Igor Bogani This work was supported by a hardware donation from the CE Linux Forum. Signed-off-by: Alessio Igor Bogani <abogani@kernel.org> --- 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 ^ permalink raw reply related [flat|nested] 30+ messages in thread
* Re: [PATCH] module: Use binary search in lookup_symbol() 2011-05-16 20:23 ` Alessio Igor Bogani @ 2011-05-16 21:01 ` Joe Perches 2011-05-16 21:08 ` Joe Perches 2011-05-17 3:52 ` Rusty Russell 1 sibling, 1 reply; 30+ messages in thread From: Joe Perches @ 2011-05-16 21:01 UTC (permalink / raw) To: Alessio Igor Bogani Cc: Rusty Russell, Anders Kaseorg, Tim Abbott, Tim Bird, LKML, Linux Embedded, Jason Wessel, Dirk Behme 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 <abogani@kernel.org> > --- > 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? ^ permalink raw reply [flat|nested] 30+ messages in thread
* Re: [PATCH] module: Use binary search in lookup_symbol() 2011-05-16 21:01 ` Joe Perches @ 2011-05-16 21:08 ` Joe Perches 0 siblings, 0 replies; 30+ messages in thread From: Joe Perches @ 2011-05-16 21:08 UTC (permalink / raw) To: Alessio Igor Bogani Cc: Rusty Russell, Anders Kaseorg, Tim Abbott, Tim Bird, LKML, Linux Embedded, Jason Wessel, Dirk Behme 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 <abogani@kernel.org> > > 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. ^ permalink raw reply [flat|nested] 30+ messages in thread
* Re: [PATCH] module: Use binary search in lookup_symbol() 2011-05-16 20:23 ` Alessio Igor Bogani 2011-05-16 21:01 ` Joe Perches @ 2011-05-17 3:52 ` Rusty Russell 2011-05-17 19:18 ` Dirk Behme 1 sibling, 1 reply; 30+ messages in thread From: Rusty Russell @ 2011-05-17 3:52 UTC (permalink / raw) To: Alessio Igor Bogani Cc: Anders Kaseorg, Tim Abbott, Tim Bird, LKML, Linux Embedded, Jason Wessel, Dirk Behme, Alessio Igor Bogani On Mon, 16 May 2011 22:23:40 +0200, Alessio Igor Bogani <abogani@kernel.org> wrote: > This work was supported by a hardware donation from the CE Linux Forum. > > Signed-off-by: Alessio Igor Bogani <abogani@kernel.org> > --- > 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. ^ permalink raw reply [flat|nested] 30+ messages in thread
* Re: [PATCH] module: Use binary search in lookup_symbol() 2011-05-17 3:52 ` Rusty Russell @ 2011-05-17 19:18 ` Dirk Behme 2011-05-17 19:41 ` Alessio Igor Bogani 2011-05-18 1:10 ` Rusty Russell 0 siblings, 2 replies; 30+ messages in thread From: Dirk Behme @ 2011-05-17 19:18 UTC (permalink / raw) To: Rusty Russell Cc: Alessio Igor Bogani, Anders Kaseorg, Tim Abbott, Tim Bird, LKML, Linux Embedded, Jason Wessel On 17.05.2011 05:52, Rusty Russell wrote: > On Mon, 16 May 2011 22:23:40 +0200, Alessio Igor Bogani<abogani@kernel.org> wrote: >> This work was supported by a hardware donation from the CE Linux Forum. >> >> Signed-off-by: Alessio Igor Bogani<abogani@kernel.org> >> --- >> 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 ^ permalink raw reply [flat|nested] 30+ messages in thread
* Re: [PATCH] module: Use binary search in lookup_symbol() 2011-05-17 19:18 ` Dirk Behme @ 2011-05-17 19:41 ` Alessio Igor Bogani 2011-05-17 20:56 ` Alessio Igor Bogani 2011-05-18 1:10 ` Rusty Russell 1 sibling, 1 reply; 30+ messages in thread From: Alessio Igor Bogani @ 2011-05-17 19:41 UTC (permalink / raw) To: Dirk Behme Cc: Rusty Russell, Anders Kaseorg, Tim Abbott, Tim Bird, LKML, Linux Embedded, Jason Wessel Dear Mr. Behme, 2011/5/17 Dirk Behme <dirk.behme@googlemail.com>: [...] > 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 ^ permalink raw reply [flat|nested] 30+ messages in thread
* [PATCH] module: Use binary search in lookup_symbol() 2011-05-17 19:41 ` Alessio Igor Bogani @ 2011-05-17 20:56 ` Alessio Igor Bogani 2011-05-17 23:22 ` Greg KH 2011-05-18 15:26 ` Dirk Behme 0 siblings, 2 replies; 30+ messages in thread From: Alessio Igor Bogani @ 2011-05-17 20:56 UTC (permalink / raw) To: Rusty Russell Cc: Anders Kaseorg, Tim Abbott, Tim Bird, LKML, Linux Embedded, Jason Wessel, Dirk Behme, Alessio Igor Bogani This work was supported by a hardware donation from the CE Linux Forum. Signed-off-by: Alessio Igor Bogani <abogani@kernel.org> --- 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 ^ permalink raw reply related [flat|nested] 30+ messages in thread
* Re: [PATCH] module: Use binary search in lookup_symbol() 2011-05-17 20:56 ` Alessio Igor Bogani @ 2011-05-17 23:22 ` Greg KH 2011-05-17 23:33 ` Tim Bird 2011-05-18 1:07 ` Rusty Russell 2011-05-18 15:26 ` Dirk Behme 1 sibling, 2 replies; 30+ messages in thread From: Greg KH @ 2011-05-17 23:22 UTC (permalink / raw) To: Alessio Igor Bogani Cc: Rusty Russell, Anders Kaseorg, Tim Abbott, Tim Bird, LKML, Linux Embedded, Jason Wessel, Dirk Behme 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 <abogani@kernel.org> > --- 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 ^ permalink raw reply [flat|nested] 30+ messages in thread
* Re: [PATCH] module: Use binary search in lookup_symbol() 2011-05-17 23:22 ` Greg KH @ 2011-05-17 23:33 ` Tim Bird 2011-05-18 7:54 ` Christoph Hellwig 2011-05-18 18:55 ` Alessio Igor Bogani 2011-05-18 1:07 ` Rusty Russell 1 sibling, 2 replies; 30+ messages in thread From: Tim Bird @ 2011-05-17 23:33 UTC (permalink / raw) To: Greg KH Cc: Alessio Igor Bogani, Rusty Russell, Anders Kaseorg, Tim Abbott, LKML, Linux Embedded, Jason Wessel, Dirk Behme 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 <abogani@kernel.org> >> --- > > 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 ============================= ^ permalink raw reply [flat|nested] 30+ messages in thread
* Re: [PATCH] module: Use binary search in lookup_symbol() 2011-05-17 23:33 ` Tim Bird @ 2011-05-18 7:54 ` Christoph Hellwig 2011-05-18 17:00 ` Tim Bird 2011-05-18 18:55 ` Alessio Igor Bogani 1 sibling, 1 reply; 30+ messages in thread From: Christoph Hellwig @ 2011-05-18 7:54 UTC (permalink / raw) To: Tim Bird Cc: Greg KH, Alessio Igor Bogani, Rusty Russell, Anders Kaseorg, Tim Abbott, LKML, Linux Embedded, Jason Wessel, Dirk Behme 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? ^ permalink raw reply [flat|nested] 30+ messages in thread
* Re: [PATCH] module: Use binary search in lookup_symbol() 2011-05-18 7:54 ` Christoph Hellwig @ 2011-05-18 17:00 ` Tim Bird 2011-05-18 19:21 ` Greg KH 0 siblings, 1 reply; 30+ messages in thread From: Tim Bird @ 2011-05-18 17:00 UTC (permalink / raw) To: Christoph Hellwig Cc: Greg KH, Alessio Igor Bogani, Rusty Russell, Anders Kaseorg, Tim Abbott, LKML, Linux Embedded, Jason Wessel, Dirk Behme 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 ============================= ^ permalink raw reply [flat|nested] 30+ messages in thread
* Re: [PATCH] module: Use binary search in lookup_symbol() 2011-05-18 17:00 ` Tim Bird @ 2011-05-18 19:21 ` Greg KH 2011-05-18 21:10 ` module boot time (was Re: [PATCH] module: Use binary search in lookup_symbol()) Tim Bird 0 siblings, 1 reply; 30+ messages in thread From: Greg KH @ 2011-05-18 19:21 UTC (permalink / raw) To: Tim Bird Cc: Christoph Hellwig, Alessio Igor Bogani, Rusty Russell, Anders Kaseorg, Tim Abbott, LKML, Linux Embedded, Jason Wessel, Dirk Behme 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 ^ permalink raw reply [flat|nested] 30+ messages in thread
* module boot time (was Re: [PATCH] module: Use binary search in lookup_symbol()) 2011-05-18 19:21 ` Greg KH @ 2011-05-18 21:10 ` Tim Bird 2011-05-18 21:34 ` Greg KH 0 siblings, 1 reply; 30+ messages in thread From: Tim Bird @ 2011-05-18 21:10 UTC (permalink / raw) To: Greg KH Cc: Christoph Hellwig, Alessio Igor Bogani, Rusty Russell, Anders Kaseorg, Tim Abbott, LKML, Linux Embedded, Jason Wessel, Dirk Behme 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 ============================= ^ permalink raw reply [flat|nested] 30+ messages in thread
* Re: module boot time (was Re: [PATCH] module: Use binary search in lookup_symbol()) 2011-05-18 21:10 ` module boot time (was Re: [PATCH] module: Use binary search in lookup_symbol()) Tim Bird @ 2011-05-18 21:34 ` Greg KH 2011-05-19 19:56 ` Jeff Mahoney 0 siblings, 1 reply; 30+ messages in thread From: Greg KH @ 2011-05-18 21:34 UTC (permalink / raw) To: Tim Bird, Jeff Mahoney Cc: Christoph Hellwig, Alessio Igor Bogani, Rusty Russell, Anders Kaseorg, Tim Abbott, LKML, Linux Embedded, Jason Wessel, Dirk Behme 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 ^ permalink raw reply [flat|nested] 30+ messages in thread
* Re: module boot time (was Re: [PATCH] module: Use binary search in lookup_symbol()) 2011-05-18 21:34 ` Greg KH @ 2011-05-19 19:56 ` Jeff Mahoney 2011-05-20 21:29 ` Tim Bird 0 siblings, 1 reply; 30+ messages in thread From: Jeff Mahoney @ 2011-05-19 19:56 UTC (permalink / raw) To: Greg KH Cc: Tim Bird, Christoph Hellwig, Alessio Igor Bogani, Rusty Russell, Anders Kaseorg, Tim Abbott, LKML, Linux Embedded, Jason Wessel, Dirk Behme -----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----- ^ permalink raw reply [flat|nested] 30+ messages in thread
* Re: module boot time (was Re: [PATCH] module: Use binary search in lookup_symbol()) 2011-05-19 19:56 ` Jeff Mahoney @ 2011-05-20 21:29 ` Tim Bird 2011-05-21 14:23 ` Jeff Mahoney 0 siblings, 1 reply; 30+ messages in thread From: Tim Bird @ 2011-05-20 21:29 UTC (permalink / raw) To: Jeff Mahoney; +Cc: Greg KH, LKML, Linux Embedded 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 <tim.bird@am.sony.com> 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 <tim.bird@am.sony.com> 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 ============================= ^ permalink raw reply related [flat|nested] 30+ messages in thread
* Re: module boot time (was Re: [PATCH] module: Use binary search in lookup_symbol()) 2011-05-20 21:29 ` Tim Bird @ 2011-05-21 14:23 ` Jeff Mahoney 0 siblings, 0 replies; 30+ messages in thread From: Jeff Mahoney @ 2011-05-21 14:23 UTC (permalink / raw) To: Tim Bird; +Cc: Greg KH, LKML, Linux Embedded -----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----- ^ permalink raw reply [flat|nested] 30+ messages in thread
* (no subject) 2011-05-17 23:33 ` Tim Bird 2011-05-18 7:54 ` Christoph Hellwig @ 2011-05-18 18:55 ` Alessio Igor Bogani 2011-05-18 19:22 ` your mail Greg KH 1 sibling, 1 reply; 30+ messages in thread From: Alessio Igor Bogani @ 2011-05-18 18:55 UTC (permalink / raw) To: Greg KH, Rusty Russell, Tim Bird, Christoph Hellwig Cc: Anders Kaseorg, Tim Abbott, LKML, Linux Embedded, Jason Wessel, Dirk Behme, Alessio Igor Bogani Dear Mr. Bird, Dear Mr. Kroah-Hartman, Sorry for my very bad English. 2011/5/18 Tim Bird <tim.bird@am.sony.com>: [...] > 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 <abogani@kernel.org> --- 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 ^ permalink raw reply related [flat|nested] 30+ messages in thread
* Re: your mail 2011-05-18 18:55 ` Alessio Igor Bogani @ 2011-05-18 19:22 ` Greg KH 2011-05-18 20:35 ` Alessio Igor Bogani 0 siblings, 1 reply; 30+ messages in thread From: Greg KH @ 2011-05-18 19:22 UTC (permalink / raw) To: Alessio Igor Bogani Cc: Rusty Russell, Tim Bird, Christoph Hellwig, Anders Kaseorg, Tim Abbott, LKML, Linux Embedded, Jason Wessel, Dirk Behme 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 <tim.bird@am.sony.com>: > [...] > > 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 <abogani@kernel.org> Much better, I have no objection to this at all. Acked-by: Greg Kroah-Hartman <gregkh@suse.de> Care to resend it without all the stuff above so someone (Rusty I guess) can apply it? thanks, greg k-h ^ permalink raw reply [flat|nested] 30+ messages in thread
* Re: your mail 2011-05-18 19:22 ` your mail Greg KH @ 2011-05-18 20:35 ` Alessio Igor Bogani 2011-05-18 20:35 ` [PATCH] module: Use binary search in lookup_symbol() Alessio Igor Bogani 0 siblings, 1 reply; 30+ messages in thread From: Alessio Igor Bogani @ 2011-05-18 20:35 UTC (permalink / raw) To: Greg KH Cc: Rusty Russell, Tim Bird, Christoph Hellwig, Anders Kaseorg, Tim Abbott, LKML, Linux Embedded, Jason Wessel, Dirk Behme Dear Mr. Kroah-Hartman, 2011/5/18 Greg KH <greg@kroah.com>: [...] > 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 ^ permalink raw reply [flat|nested] 30+ messages in thread
* [PATCH] module: Use binary search in lookup_symbol() 2011-05-18 20:35 ` Alessio Igor Bogani @ 2011-05-18 20:35 ` Alessio Igor Bogani 0 siblings, 0 replies; 30+ messages in thread From: Alessio Igor Bogani @ 2011-05-18 20:35 UTC (permalink / raw) To: Rusty Russell Cc: Greg KH, Anders Kaseorg, Tim Abbott, Tim Bird, LKML, Linux Embedded, Jason Wessel, Dirk Behme, Christoph Hellwig, Alessio Igor Bogani 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 <abogani@kernel.org> Acked-by: Greg Kroah-Hartman <gregkh@suse.de> --- 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 ^ permalink raw reply related [flat|nested] 30+ messages in thread
* Re: [PATCH] module: Use binary search in lookup_symbol() 2011-05-17 23:22 ` Greg KH 2011-05-17 23:33 ` Tim Bird @ 2011-05-18 1:07 ` Rusty Russell 1 sibling, 0 replies; 30+ messages in thread From: Rusty Russell @ 2011-05-18 1:07 UTC (permalink / raw) To: Greg KH, Alessio Igor Bogani Cc: Anders Kaseorg, Tim Abbott, Tim Bird, LKML, Linux Embedded, Jason Wessel, Dirk Behme On Tue, 17 May 2011 16:22:41 -0700, Greg KH <greg@kroah.com> 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 <abogani@kernel.org> > > --- > > 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. ^ permalink raw reply [flat|nested] 30+ messages in thread
* Re: [PATCH] module: Use binary search in lookup_symbol() 2011-05-17 20:56 ` Alessio Igor Bogani 2011-05-17 23:22 ` Greg KH @ 2011-05-18 15:26 ` Dirk Behme 2011-05-19 7:26 ` Rusty Russell 1 sibling, 1 reply; 30+ messages in thread From: Dirk Behme @ 2011-05-18 15:26 UTC (permalink / raw) To: Alessio Igor Bogani Cc: Rusty Russell, Anders Kaseorg, Tim Abbott, Tim Bird, LKML, Linux Embedded, Jason Wessel 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<abogani@kernel.org> > --- > 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 ^ permalink raw reply [flat|nested] 30+ messages in thread
* Re: [PATCH] module: Use binary search in lookup_symbol() 2011-05-18 15:26 ` Dirk Behme @ 2011-05-19 7:26 ` Rusty Russell 0 siblings, 0 replies; 30+ messages in thread From: Rusty Russell @ 2011-05-19 7:26 UTC (permalink / raw) To: Dirk Behme, Alessio Igor Bogani Cc: Anders Kaseorg, Tim Abbott, Tim Bird, LKML, Linux Embedded, Jason Wessel On Wed, 18 May 2011 17:26:56 +0200, Dirk Behme <dirk.behme@googlemail.com> 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. ^ permalink raw reply [flat|nested] 30+ messages in thread
* Re: [PATCH] module: Use binary search in lookup_symbol() 2011-05-17 19:18 ` Dirk Behme 2011-05-17 19:41 ` Alessio Igor Bogani @ 2011-05-18 1:10 ` Rusty Russell 1 sibling, 0 replies; 30+ messages in thread From: Rusty Russell @ 2011-05-18 1:10 UTC (permalink / raw) To: Dirk Behme Cc: Alessio Igor Bogani, Anders Kaseorg, Tim Abbott, Tim Bird, LKML, Linux Embedded, Jason Wessel On Tue, 17 May 2011 21:18:26 +0200, Dirk Behme <dirk.behme@googlemail.com> wrote: > On 17.05.2011 05:52, Rusty Russell wrote: > > On Mon, 16 May 2011 22:23:40 +0200, Alessio Igor Bogani<abogani@kernel.org> wrote: > >> This work was supported by a hardware donation from the CE Linux Forum. > >> > >> Signed-off-by: Alessio Igor Bogani<abogani@kernel.org> > >> --- > >> 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. ^ permalink raw reply [flat|nested] 30+ messages in thread
end of thread, other threads:[~2011-05-21 14:23 UTC | newest] Thread overview: 30+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2011-05-03 20:42 [PATCH] module: Use binary search in lookup_symbol() Alessio Igor Bogani 2011-05-04 15:34 ` Dirk Behme 2011-05-04 17:30 ` Alessio Igor Bogani 2011-05-16 15:36 ` Dirk Behme 2011-05-16 18:02 ` Anders Kaseorg 2011-05-16 20:23 ` Alessio Igor Bogani 2011-05-16 21:01 ` Joe Perches 2011-05-16 21:08 ` Joe Perches 2011-05-17 3:52 ` Rusty Russell 2011-05-17 19:18 ` Dirk Behme 2011-05-17 19:41 ` Alessio Igor Bogani 2011-05-17 20:56 ` Alessio Igor Bogani 2011-05-17 23:22 ` Greg KH 2011-05-17 23:33 ` Tim Bird 2011-05-18 7:54 ` Christoph Hellwig 2011-05-18 17:00 ` Tim Bird 2011-05-18 19:21 ` Greg KH 2011-05-18 21:10 ` module boot time (was Re: [PATCH] module: Use binary search in lookup_symbol()) Tim Bird 2011-05-18 21:34 ` Greg KH 2011-05-19 19:56 ` Jeff Mahoney 2011-05-20 21:29 ` Tim Bird 2011-05-21 14:23 ` Jeff Mahoney 2011-05-18 18:55 ` Alessio Igor Bogani 2011-05-18 19:22 ` your mail Greg KH 2011-05-18 20:35 ` Alessio Igor Bogani 2011-05-18 20:35 ` [PATCH] module: Use binary search in lookup_symbol() Alessio Igor Bogani 2011-05-18 1:07 ` Rusty Russell 2011-05-18 15:26 ` Dirk Behme 2011-05-19 7:26 ` Rusty Russell 2011-05-18 1:10 ` Rusty Russell
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for NNTP newsgroup(s).