* Re: Expose regulator:set_consumer_device_supply()?
From: Mark Brown @ 2011-04-26 8:34 UTC (permalink / raw)
To: Bill Gatliff; +Cc: linux-embedded, lrg, linux-kerne
In-Reply-To: <BANLkTikQSus=o3=TVdEPBfnP6HZJvxt4Vw@mail.gmail.com>
On Mon, Apr 25, 2011 at 09:25:22PM -0500, Bill Gatliff wrote:
> This would also imply the ability to register a regulator with no
> consumers listed, as they would be added later when i2c, etc. devices
> were registered.
This is already possible, not all consumers are visible to software
anyway.
^ permalink raw reply
* Re: Expose regulator:set_consumer_device_supply()?
From: Mark Brown @ 2011-04-26 8:33 UTC (permalink / raw)
To: Bill Gatliff; +Cc: linux-embedded, linux-kernel
In-Reply-To: <BANLkTi=dCHXEtv+=+sRaDp_Pt3zQy5o7ug@mail.gmail.com>
On Mon, Apr 25, 2011 at 09:16:55PM -0500, Bill Gatliff wrote:
> Guys:
Please always:
- CC maintainers on mails (in this case myself and Liam).
- CC the relevant list (in this case linux-kernel).
> In a nutshell, I have a lot of i2c chips, each of which is powered by
> its own voltage regulator. Among other things, I'm trying to write
> the i2c drivers so that they are as platform-agnostic as possible,
> because I intend for these drivers to be reused on future platforms
> with different voltage regulator layouts. On future platforms
> regulators might be shared with multiple i2c chips, for example.
OK, this is absolutely normal for the regulator API.
> What I'm hoping for is i2c driver code that asks for a regulator based
> on the name of the pin to which the regulator is connected. So
> instead of doing this:
> ... I can do this:
>
> i2c_chip_probe(i2c_client *this, ...)
> {
> ...
> /* ask for the regulator connected to our VDD pin */
> reg = regulator_get(this, "VDD");
> ...
> }
This is exactly what you're supposed to do with the regulator API now.
If you're not doing that the consumer driver is buggy and should be
fixed, it should be written without reference to the board it is running
on.
> The problem with i2c devices is that if you register them with
> i2c_register_board_info(), you don't have a device pointer that you
> can associate a regulator with. So you have to register the regulator
> after the i2c chip gets registered, which means doing it in the i2c
> chip's probe method. Ugly, and it won't work when regulators are
> shared between devices.
You can specify the device by either dev_name() or a dev pointer. You
can use dev_name() at any time without the device having been
instantiated, it would be unusal to use a struct device.
> Any reason why we couldn't expose set_consumer_device_supply(), so
> that I can add a device as a regulator consumer after a regulator is
> already registered?
This would facilitate abuse of the API, we already have enough problems
with people trying to pass regulators as platform data.
^ permalink raw reply
* Re: Expose regulator:set_consumer_device_supply()?
From: Bill Gatliff @ 2011-04-26 2:25 UTC (permalink / raw)
To: linux-embedded; +Cc: lrg, broonie
In-Reply-To: <BANLkTi=dCHXEtv+=+sRaDp_Pt3zQy5o7ug@mail.gmail.com>
Guys:
On Mon, Apr 25, 2011 at 9:16 PM, Bill Gatliff <bgat@billgatliff.com> wrote:
> A much cleaner way might be to pass a struct regulator_dev pointer in
> the i2c chip's platform data, and then use something similar to
> set_consumer_device_supply() to add the i2c chip's "VDD" pin as a
> consumer of the regulator. Or maybe that function exactly.
This would also imply the ability to register a regulator with no
consumers listed, as they would be added later when i2c, etc. devices
were registered.
b.g.
--
Bill Gatliff
bgat@billgatliff.com
^ permalink raw reply
* Expose regulator:set_consumer_device_supply()?
From: Bill Gatliff @ 2011-04-26 2:16 UTC (permalink / raw)
To: linux-embedded
Guys:
I have been looking at incorporating use of the voltage regulator
framework into one of my platforms, and have come across a problem
that I'm not quite sure how to solve.
In a nutshell, I have a lot of i2c chips, each of which is powered by
its own voltage regulator. Among other things, I'm trying to write
the i2c drivers so that they are as platform-agnostic as possible,
because I intend for these drivers to be reused on future platforms
with different voltage regulator layouts. On future platforms
regulators might be shared with multiple i2c chips, for example.
What I'm hoping for is i2c driver code that asks for a regulator based
on the name of the pin to which the regulator is connected. So
instead of doing this:
i2c_chip_probe(i2c_client *this, ...)
{
...
/* request the name of a regulator that will change
* when the platform changes; ugh */
reg = regulator_get(NULL, "VREG_U11");
...
}
... I can do this:
i2c_chip_probe(i2c_client *this, ...)
{
...
/* ask for the regulator connected to our VDD pin */
reg = regulator_get(this, "VDD");
...
}
The problem with i2c devices is that if you register them with
i2c_register_board_info(), you don't have a device pointer that you
can associate a regulator with. So you have to register the regulator
after the i2c chip gets registered, which means doing it in the i2c
chip's probe method. Ugly, and it won't work when regulators are
shared between devices.
A much cleaner way might be to pass a struct regulator_dev pointer in
the i2c chip's platform data, and then use something similar to
set_consumer_device_supply() to add the i2c chip's "VDD" pin as a
consumer of the regulator. Or maybe that function exactly.
Any reason why we couldn't expose set_consumer_device_supply(), so
that I can add a device as a regulator consumer after a regulator is
already registered?
Curious,
b.g.
--
Bill Gatliff
bgat@billgatliff.com
^ permalink raw reply
* Re: [PATCH] extra/1 Allow setting the maximum KBUS message size
From: Tony Ibbs @ 2011-04-19 19:33 UTC (permalink / raw)
To: Mark Brown
Cc: Jonathan Corbet, Grant Likely, lkml, Linux-embedded,
Tibs at Kynesim, Richard Watts, James Chapman
In-Reply-To: <20110418140110.GD9462@sirena.org.uk>
On 18 Apr 2011, at 15:01, Mark Brown wrote:
> On Fri, Apr 15, 2011 at 04:46:08PM -0600, Jonathan Corbet wrote:
>
>> That means getting more people to look at the patch, which could be hard.
>> The problem is that, if you wait, they'll only squeal when the code is
>> close to going in, and you could find yourself set back a long way. A
>> good first step might be to CC Andrew Morton on your next posting.
>
> One other thing that it'd be good to see is a contrast and compare with
> other similar things like the Android binder that are floating around.
I'm aiming to write a smallish example of using KBUS for something not
entirely boring, and that will hopefully work as a starting point for
comparisons. Unfortunately (for this purpose, anyway), the next couple
of weekends (including four days of public holiday!) are taken up with
other things, so it will be a little while.
That will probably be an appropriate thing to CC Andrew Morton.
Comparative examples of how to do something similar with other means may
take longer, of course.
Thanks,
Tibs
^ permalink raw reply
* Re: [PATCH 4/4] module: Use the binary search for symbols resolution
From: Wanlong Gao @ 2011-04-19 12:46 UTC (permalink / raw)
To: Rusty Russell
Cc: Alessio Igor Bogani, Tim Abbott, Anders Kaseorg, Jason Wessel,
Tim Bird, LKML, Linux Embedded
In-Reply-To: <87aafmo4mi.fsf@rustcorp.com.au>
2011-4-19 19:35, Rusty Russell wroted:
> On Tue, 19 Apr 2011 09:44:20 +0800, Wanlong Gao<wanlong.gao@gmail.com> wrote:
>> 2011-4-19 9:37, Rusty Russell wroted:
>>> On Sat, 16 Apr 2011 22:32:08 +0800, Wanlong Gao<wanlong.gao@gmail.com> wrote:
>>>>> + sym = bsearch(fsa->name, syms->start, syms->stop - syms->start,
>>>> As the bsearch func, why not change the syms->stop to syms->end ?
>>>> Hmm..Just a stupid suggestion.
>>>
>>>
>>> The names are derived from the linker symbols for end of sections, which
>>> is __stop_<sectionname>.
>>>
>>> Cheers,
>>> Rusty.
>> As this , why not change the bsearch's "end" to "stop", too ? It will be
>> more readable.
>
> I'm confused. bsearch uses a count, not an end pointer...
>
> Rusty.
Hmm...I see, I see . I made a mistake on this func .
Thanks for your explanation.
Best regards
^ permalink raw reply
* Re: [PATCH 4/4] module: Use the binary search for symbols resolution
From: Rusty Russell @ 2011-04-19 11:35 UTC (permalink / raw)
To: Wanlong Gao
Cc: Alessio Igor Bogani, Tim Abbott, Anders Kaseorg, Jason Wessel,
Tim Bird, LKML, Linux Embedded
In-Reply-To: <4DACE8F4.2050807@gmail.com>
On Tue, 19 Apr 2011 09:44:20 +0800, Wanlong Gao <wanlong.gao@gmail.com> wrote:
> 2011-4-19 9:37, Rusty Russell wroted:
> > On Sat, 16 Apr 2011 22:32:08 +0800, Wanlong Gao<wanlong.gao@gmail.com> wrote:
> >>> + sym = bsearch(fsa->name, syms->start, syms->stop - syms->start,
> >> As the bsearch func, why not change the syms->stop to syms->end ?
> >> Hmm..Just a stupid suggestion.
> >
> >
> > The names are derived from the linker symbols for end of sections, which
> > is __stop_<sectionname>.
> >
> > Cheers,
> > Rusty.
> As this , why not change the bsearch's "end" to "stop", too ? It will be
> more readable.
I'm confused. bsearch uses a count, not an end pointer...
Rusty.
^ permalink raw reply
* Re: [PATCH 4/4] module: Use the binary search for symbols resolution
From: Wanlong Gao @ 2011-04-19 1:44 UTC (permalink / raw)
To: Rusty Russell
Cc: Alessio Igor Bogani, Tim Abbott, Anders Kaseorg, Jason Wessel,
Tim Bird, LKML, Linux Embedded
In-Reply-To: <87liz73tso.fsf@rustcorp.com.au>
2011-4-19 9:37, Rusty Russell wroted:
> On Sat, 16 Apr 2011 22:32:08 +0800, Wanlong Gao<wanlong.gao@gmail.com> wrote:
>>> + sym = bsearch(fsa->name, syms->start, syms->stop - syms->start,
>> As the bsearch func, why not change the syms->stop to syms->end ?
>> Hmm..Just a stupid suggestion.
>
>
> The names are derived from the linker symbols for end of sections, which
> is __stop_<sectionname>.
>
> Cheers,
> Rusty.
As this , why not change the bsearch's "end" to "stop", too ? It will be
more readable.
Thanks
Wanlong
^ permalink raw reply
* Re: [PATCH 4/4] module: Use the binary search for symbols resolution
From: Rusty Russell @ 2011-04-19 1:37 UTC (permalink / raw)
To: wanlong.gao, Alessio Igor Bogani
Cc: Tim Abbott, Anders Kaseorg, Jason Wessel, Tim Bird, LKML,
Linux Embedded
In-Reply-To: <BANLkTik9oekjUH6YXTda1P_dM231nEHQqA@mail.gmail.com>
On Sat, 16 Apr 2011 22:32:08 +0800, Wanlong Gao <wanlong.gao@gmail.com> wrote:
> > + sym = bsearch(fsa->name, syms->start, syms->stop - syms->start,
> As the bsearch func, why not change the syms->stop to syms->end ?
> Hmm..Just a stupid suggestion.
The names are derived from the linker symbols for end of sections, which
is __stop_<sectionname>.
Cheers,
Rusty.
^ permalink raw reply
* Re: [PATCH 1/4] module: Restructure each_symbol() code
From: Rusty Russell @ 2011-04-19 1:31 UTC (permalink / raw)
To: Alessio Igor Bogani, Tim Abbott, Anders Kaseorg, Jason Wessel,
Tim Bird
Cc: LKML, Linux Embedded, Alessio Igor Bogani
In-Reply-To: <1302960373-5309-2-git-send-email-abogani@kernel.org>
On Sat, 16 Apr 2011 15:26:10 +0200, Alessio Igor Bogani <abogani@kernel.org> wrote:
> Restructure code to better integrate future improvements.
I like all the rest, but I find the function names here a bit confusing.
How about using this (untested!) patch instead?
Thanks!
Rusty.
---
Subject: module: each_symbol_section instead of each_symbol
Instead of having a callback function for each symbol in the kernel,
have a callback for each array of symbols.
This eases the logic when we move to sorted symbols and binary search.
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
diff --git a/include/linux/module.h b/include/linux/module.h
--- a/include/linux/module.h
+++ b/include/linux/module.h
@@ -477,8 +477,9 @@ const struct kernel_symbol *find_symbol(
bool warn);
/* Walk the exported symbol table */
-bool each_symbol(bool (*fn)(const struct symsearch *arr, struct module *owner,
- unsigned int symnum, void *data), void *data);
+bool each_symbol_section(bool (*fn)(const struct symsearch *arr,
+ struct module *owner,
+ void *data), void *data);
/* Returns 0 and fills in value, defined and namebuf, or -ERANGE if
symnum out of range. */
diff --git a/kernel/module.c b/kernel/module.c
--- a/kernel/module.c
+++ b/kernel/module.c
@@ -240,23 +240,24 @@ static bool each_symbol_in_section(const
struct module *owner,
bool (*fn)(const struct symsearch *syms,
struct module *owner,
- unsigned int symnum, void *data),
+ void *data),
void *data)
{
- unsigned int i, j;
+ unsigned int j;
for (j = 0; j < arrsize; j++) {
- for (i = 0; i < arr[j].stop - arr[j].start; i++)
- if (fn(&arr[j], owner, i, data))
- return true;
+ if (fn(&arr[j], owner, data))
+ return true;
}
return false;
}
/* Returns true as soon as fn returns true, otherwise false. */
-bool each_symbol(bool (*fn)(const struct symsearch *arr, struct module *owner,
- unsigned int symnum, void *data), void *data)
+bool each_symbol_section(bool (*fn)(const struct symsearch *arr,
+ struct module *owner,
+ void *data),
+ void *data)
{
struct module *mod;
static const struct symsearch arr[] = {
@@ -309,7 +310,7 @@ bool each_symbol(bool (*fn)(const struct
}
return false;
}
-EXPORT_SYMBOL_GPL(each_symbol);
+EXPORT_SYMBOL_GPL(each_symbol_section);
struct find_symbol_arg {
/* Input */
@@ -323,9 +324,9 @@ struct find_symbol_arg {
const struct kernel_symbol *sym;
};
-static bool find_symbol_in_section(const struct symsearch *syms,
- struct module *owner,
- unsigned int symnum, void *data)
+static bool test_symbol_for_find(const struct symsearch *syms,
+ struct module *owner,
+ unsigned int symnum, void *data)
{
struct find_symbol_arg *fsa = data;
@@ -365,6 +366,19 @@ static bool find_symbol_in_section(const
return true;
}
+static bool find_symbol_in_section(const struct symsearch *syms,
+ struct module *owner,
+ void *data)
+{
+ unsigned int i;
+
+ for (i = 0; i < syms->stop - syms->start; i++) {
+ if (test_symbol_for_find(syms, owner, i, data))
+ return true;
+ }
+ return false;
+}
+
/* Find a symbol and return it, along with, (optional) crc and
* (optional) module which owns it. Needs preempt disabled or module_mutex. */
const struct kernel_symbol *find_symbol(const char *name,
@@ -379,7 +393,7 @@ const struct kernel_symbol *find_symbol(
fsa.gplok = gplok;
fsa.warn = warn;
- if (each_symbol(find_symbol_in_section, &fsa)) {
+ if (each_symbol_section(find_symbol_in_section, &fsa)) {
if (owner)
*owner = fsa.owner;
if (crc)
^ permalink raw reply
* Re: [PATCH] extra/1 Allow setting the maximum KBUS message size
From: Mark Brown @ 2011-04-18 14:01 UTC (permalink / raw)
To: Jonathan Corbet
Cc: Tony Ibbs, Grant Likely, lkml, Linux-embedded, Tibs at Kynesim,
Richard Watts
In-Reply-To: <20110415164608.489d82bf@bike.lwn.net>
On Fri, Apr 15, 2011 at 04:46:08PM -0600, Jonathan Corbet wrote:
> That means getting more people to look at the patch, which could be hard.
> The problem is that, if you wait, they'll only squeal when the code is
> close to going in, and you could find yourself set back a long way. A
> good first step might be to CC Andrew Morton on your next posting.
One other thing that it'd be good to see is a contrast and compare with
other similar things like the Android binder that are floating around.
^ permalink raw reply
* Re: [PATCH 4/4] module: Use the binary search for symbols resolution
From: Wanlong Gao @ 2011-04-16 14:32 UTC (permalink / raw)
To: Alessio Igor Bogani
Cc: Rusty Russell, Tim Abbott, Anders Kaseorg, Jason Wessel, Tim Bird,
LKML, Linux Embedded
In-Reply-To: <1302960373-5309-5-git-send-email-abogani@kernel.org>
On 4/16/11, Alessio Igor Bogani <abogani@kernel.org> wrote:
> Takes advantage of the order and locates symbols using binary search.
>
> 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 | 23 ++++++++++++++++-------
> 1 files changed, 16 insertions(+), 7 deletions(-)
>
> diff --git a/kernel/module.c b/kernel/module.c
> index b438b25..74a57c1 100644
> --- a/kernel/module.c
> +++ b/kernel/module.c
> @@ -57,6 +57,7 @@
> #include <linux/kmemleak.h>
> #include <linux/jump_label.h>
> #include <linux/pfn.h>
> +#include <linux/bsearch.h>
>
> #define CREATE_TRACE_POINTS
> #include <trace/events/module.h>
> @@ -351,22 +352,30 @@ struct find_symbol_arg {
> const struct kernel_symbol *sym;
> };
>
> +static int cmp_name(const void *va, const void *vb)
> +{
> + const char *a;
> + const struct kernel_symbol *b;
> + a = va; b = vb;
> + return strcmp(a, b->name);
> +}
> +
> static bool find_symbol_in_symsearch(const struct symsearch *syms,
> struct module *owner,
> void *data)
> {
> struct find_symbol_arg *fsa = data;
> + struct kernel_symbol *sym;
> unsigned int symnum;
> - int result;
>
> - for (symnum = 0; symnum < syms->stop - syms->start; symnum++) {
> - result = strcmp(fsa->name, syms->start[symnum].name);
> - if (result == 0)
> - break;
> - }
> - if (symnum >= syms->stop - syms->start)
> + sym = bsearch(fsa->name, syms->start, syms->stop - syms->start,
As the bsearch func, why not change the syms->stop to syms->end ?
Hmm..Just a stupid suggestion.
Thanks
> + sizeof(struct kernel_symbol), cmp_name);
> +
> + if (sym == NULL)
> return false;
>
> + symnum = sym - syms->start;
> +
> if (!fsa->gplok) {
> if (syms->licence == GPL_ONLY)
> return false;
> --
> 1.7.4.1
>
> --
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at http://www.tux.org/lkml/
>
^ permalink raw reply
* Re: [PATCH 4/4] module: Use the binary search for symbols resolution
From: Wanlong Gao @ 2011-04-16 14:08 UTC (permalink / raw)
To: Alessio Igor Bogani
Cc: Rusty Russell, Tim Abbott, Anders Kaseorg, Jason Wessel, Tim Bird,
LKML, Linux Embedded
In-Reply-To: <1302960373-5309-5-git-send-email-abogani@kernel.org>
On 4/16/11, Alessio Igor Bogani <abogani@kernel.org> wrote:
> Takes advantage of the order and locates symbols using binary search.
>
> 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 | 23 ++++++++++++++++-------
> 1 files changed, 16 insertions(+), 7 deletions(-)
>
> diff --git a/kernel/module.c b/kernel/module.c
> index b438b25..74a57c1 100644
> --- a/kernel/module.c
> +++ b/kernel/module.c
> @@ -57,6 +57,7 @@
> #include <linux/kmemleak.h>
> #include <linux/jump_label.h>
> #include <linux/pfn.h>
> +#include <linux/bsearch.h>
>
> #define CREATE_TRACE_POINTS
> #include <trace/events/module.h>
> @@ -351,22 +352,30 @@ struct find_symbol_arg {
> const struct kernel_symbol *sym;
> };
>
> +static int cmp_name(const void *va, const void *vb)
> +{
> + const char *a;
> + const struct kernel_symbol *b;
> + a = va; b = vb;
> + return strcmp(a, b->name);
> +}
> +
> static bool find_symbol_in_symsearch(const struct symsearch *syms,
> struct module *owner,
> void *data)
> {
> struct find_symbol_arg *fsa = data;
> + struct kernel_symbol *sym;
> unsigned int symnum;
> - int result;
>
> - for (symnum = 0; symnum < syms->stop - syms->start; symnum++) {
> - result = strcmp(fsa->name, syms->start[symnum].name);
> - if (result == 0)
> - break;
> - }
> - if (symnum >= syms->stop - syms->start)
> + sym = bsearch(fsa->name, syms->start, syms->stop - syms->start,
> + sizeof(struct kernel_symbol), cmp_name);
> +
> + if (sym == NULL)
> return false;
>
> + symnum = sym - syms->start;
> +
> if (!fsa->gplok) {
> if (syms->licence == GPL_ONLY)
> return false;
> --
> 1.7.4.1
>
> --
It seems like a great work .
Thanks
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at http://www.tux.org/lkml/
>
^ permalink raw reply
* [PATCH 4/4] module: Use the binary search for symbols resolution
From: Alessio Igor Bogani @ 2011-04-16 13:26 UTC (permalink / raw)
To: Rusty Russell, Tim Abbott, Anders Kaseorg, Jason Wessel, Tim Bird
Cc: LKML, Linux Embedded, Alessio Igor Bogani
In-Reply-To: <1302960373-5309-1-git-send-email-abogani@kernel.org>
Takes advantage of the order and locates symbols using binary search.
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 | 23 ++++++++++++++++-------
1 files changed, 16 insertions(+), 7 deletions(-)
diff --git a/kernel/module.c b/kernel/module.c
index b438b25..74a57c1 100644
--- a/kernel/module.c
+++ b/kernel/module.c
@@ -57,6 +57,7 @@
#include <linux/kmemleak.h>
#include <linux/jump_label.h>
#include <linux/pfn.h>
+#include <linux/bsearch.h>
#define CREATE_TRACE_POINTS
#include <trace/events/module.h>
@@ -351,22 +352,30 @@ struct find_symbol_arg {
const struct kernel_symbol *sym;
};
+static int cmp_name(const void *va, const void *vb)
+{
+ const char *a;
+ const struct kernel_symbol *b;
+ a = va; b = vb;
+ return strcmp(a, b->name);
+}
+
static bool find_symbol_in_symsearch(const struct symsearch *syms,
struct module *owner,
void *data)
{
struct find_symbol_arg *fsa = data;
+ struct kernel_symbol *sym;
unsigned int symnum;
- int result;
- for (symnum = 0; symnum < syms->stop - syms->start; symnum++) {
- result = strcmp(fsa->name, syms->start[symnum].name);
- if (result == 0)
- break;
- }
- if (symnum >= syms->stop - syms->start)
+ sym = bsearch(fsa->name, syms->start, syms->stop - syms->start,
+ sizeof(struct kernel_symbol), cmp_name);
+
+ if (sym == NULL)
return false;
+ symnum = sym - syms->start;
+
if (!fsa->gplok) {
if (syms->licence == GPL_ONLY)
return false;
--
1.7.4.1
^ permalink raw reply related
* [PATCH 3/4] lib: Add generic binary search function to the kernel.
From: Alessio Igor Bogani @ 2011-04-16 13:26 UTC (permalink / raw)
To: Rusty Russell, Tim Abbott, Anders Kaseorg, Jason Wessel, Tim Bird
Cc: LKML, Linux Embedded, Alessio Igor Bogani
In-Reply-To: <1302960373-5309-1-git-send-email-abogani@kernel.org>
From: Tim Abbott <tabbott@ksplice.com>
There a large number hand-coded binary searches in the kernel (run
"git grep search | grep binary" to find many of them). Since in my
experience, hand-coding binary searches can be error-prone, it seems
worth cleaning this up by providing a generic binary search function.
This generic binary search implementation comes from Ksplice. It has
the same basic API as the C library bsearch() function. Ksplice uses
it in half a dozen places with 4 different comparison functions, and I
think our code is substantially cleaner because of this.
Signed-off-by: Tim Abbott <tabbott@ksplice.com>
Extra-bikeshedding-by: Alan Jenkins <alan-jenkins@tuffmail.co.uk>
Extra-bikeshedding-by: André Goddard Rosa <andre.goddard@gmail.com>
Extra-bikeshedding-by: Rusty Russell <rusty@rustcorp.com.au>
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
Signed-off-by: Alessio Igor Bogani <abogani@kernel.org>
---
include/linux/bsearch.h | 9 ++++++++
lib/Makefile | 3 +-
lib/bsearch.c | 53 +++++++++++++++++++++++++++++++++++++++++++++++
3 files changed, 64 insertions(+), 1 deletions(-)
create mode 100644 include/linux/bsearch.h
create mode 100644 lib/bsearch.c
diff --git a/include/linux/bsearch.h b/include/linux/bsearch.h
new file mode 100644
index 0000000..90b1aa8
--- /dev/null
+++ b/include/linux/bsearch.h
@@ -0,0 +1,9 @@
+#ifndef _LINUX_BSEARCH_H
+#define _LINUX_BSEARCH_H
+
+#include <linux/types.h>
+
+void *bsearch(const void *key, const void *base, size_t num, size_t size,
+ int (*cmp)(const void *key, const void *elt));
+
+#endif /* _LINUX_BSEARCH_H */
diff --git a/lib/Makefile b/lib/Makefile
index ef0f285..4b49a24 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -21,7 +21,8 @@ lib-y += kobject.o kref.o klist.o
obj-y += bcd.o div64.o sort.o parser.o halfmd4.o debug_locks.o random32.o \
bust_spinlocks.o hexdump.o kasprintf.o bitmap.o scatterlist.o \
- string_helpers.o gcd.o lcm.o list_sort.o uuid.o flex_array.o
+ string_helpers.o gcd.o lcm.o list_sort.o uuid.o flex_array.o \
+ bsearch.o
obj-y += kstrtox.o
obj-$(CONFIG_TEST_KSTRTOX) += test-kstrtox.o
diff --git a/lib/bsearch.c b/lib/bsearch.c
new file mode 100644
index 0000000..5b54758
--- /dev/null
+++ b/lib/bsearch.c
@@ -0,0 +1,53 @@
+/*
+ * A generic implementation of binary search for the Linux kernel
+ *
+ * Copyright (C) 2008-2009 Ksplice, Inc.
+ * Author: Tim Abbott <tabbott@ksplice.com>
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License as
+ * published by the Free Software Foundation; version 2.
+ */
+
+#include <linux/module.h>
+#include <linux/bsearch.h>
+
+/*
+ * bsearch - binary search an array of elements
+ * @key: pointer to item being searched for
+ * @base: pointer to first element to search
+ * @num: number of elements
+ * @size: size of each element
+ * @cmp: pointer to comparison function
+ *
+ * This function does a binary search on the given array. The
+ * contents of the array should already be in ascending sorted order
+ * under the provided comparison function.
+ *
+ * Note that the key need not have the same type as the elements in
+ * the array, e.g. key could be a string and the comparison function
+ * could compare the string with the struct's name field. However, if
+ * the key and elements in the array are of the same type, you can use
+ * the same comparison function for both sort() and bsearch().
+ */
+void *bsearch(const void *key, const void *base, size_t num, size_t size,
+ int (*cmp)(const void *key, const void *elt))
+{
+ size_t start = 0, end = num;
+ int result;
+
+ while (start < end) {
+ size_t mid = start + (end - start) / 2;
+
+ result = cmp(key, base + mid * size);
+ if (result < 0)
+ end = mid;
+ else if (result > 0)
+ start = mid + 1;
+ else
+ return (void *)base + mid * size;
+ }
+
+ return NULL;
+}
+EXPORT_SYMBOL(bsearch);
--
1.7.4.1
^ permalink raw reply related
* [PATCH 2/4] module: Sort exported symbols
From: Alessio Igor Bogani @ 2011-04-16 13:26 UTC (permalink / raw)
To: Rusty Russell, Tim Abbott, Anders Kaseorg, Jason Wessel, Tim Bird
Cc: LKML, Linux Embedded, Alessio Igor Bogani
In-Reply-To: <1302960373-5309-1-git-send-email-abogani@kernel.org>
This patch places every exported symbol in its own section
(i.e. "___ksymtab__printk"). Thus the linker will use its SORT() directive
to sort and finally merge all symbol in the right and final section
(i.e. "__ksymtab").
This work was supported by a hardware donation from the CE Linux Forum.
Signed-off-by: Alessio Igor Bogani <abogani@kernel.org>
---
include/asm-generic/vmlinux.lds.h | 20 ++++++++++----------
include/linux/module.h | 4 ++--
scripts/module-common.lds | 11 +++++++++++
3 files changed, 23 insertions(+), 12 deletions(-)
diff --git a/include/asm-generic/vmlinux.lds.h b/include/asm-generic/vmlinux.lds.h
index bd297a2..349e356 100644
--- a/include/asm-generic/vmlinux.lds.h
+++ b/include/asm-generic/vmlinux.lds.h
@@ -274,70 +274,70 @@
/* Kernel symbol table: Normal symbols */ \
__ksymtab : AT(ADDR(__ksymtab) - LOAD_OFFSET) { \
VMLINUX_SYMBOL(__start___ksymtab) = .; \
- *(__ksymtab) \
+ *(SORT(___ksymtab__*)) \
VMLINUX_SYMBOL(__stop___ksymtab) = .; \
} \
\
/* Kernel symbol table: GPL-only symbols */ \
__ksymtab_gpl : AT(ADDR(__ksymtab_gpl) - LOAD_OFFSET) { \
VMLINUX_SYMBOL(__start___ksymtab_gpl) = .; \
- *(__ksymtab_gpl) \
+ *(SORT(___ksymtab_gpl__*)) \
VMLINUX_SYMBOL(__stop___ksymtab_gpl) = .; \
} \
\
/* Kernel symbol table: Normal unused symbols */ \
__ksymtab_unused : AT(ADDR(__ksymtab_unused) - LOAD_OFFSET) { \
VMLINUX_SYMBOL(__start___ksymtab_unused) = .; \
- *(__ksymtab_unused) \
+ *(SORT(___ksymtab_unused__*)) \
VMLINUX_SYMBOL(__stop___ksymtab_unused) = .; \
} \
\
/* Kernel symbol table: GPL-only unused symbols */ \
__ksymtab_unused_gpl : AT(ADDR(__ksymtab_unused_gpl) - LOAD_OFFSET) { \
VMLINUX_SYMBOL(__start___ksymtab_unused_gpl) = .; \
- *(__ksymtab_unused_gpl) \
+ *(SORT(___ksymtab_unused_gpl__*)) \
VMLINUX_SYMBOL(__stop___ksymtab_unused_gpl) = .; \
} \
\
/* Kernel symbol table: GPL-future-only symbols */ \
__ksymtab_gpl_future : AT(ADDR(__ksymtab_gpl_future) - LOAD_OFFSET) { \
VMLINUX_SYMBOL(__start___ksymtab_gpl_future) = .; \
- *(__ksymtab_gpl_future) \
+ *(SORT(___ksymtab_gpl_future__*)) \
VMLINUX_SYMBOL(__stop___ksymtab_gpl_future) = .; \
} \
\
/* Kernel symbol table: Normal symbols */ \
__kcrctab : AT(ADDR(__kcrctab) - LOAD_OFFSET) { \
VMLINUX_SYMBOL(__start___kcrctab) = .; \
- *(__kcrctab) \
+ *(SORT(___kcrctab__*)) \
VMLINUX_SYMBOL(__stop___kcrctab) = .; \
} \
\
/* Kernel symbol table: GPL-only symbols */ \
__kcrctab_gpl : AT(ADDR(__kcrctab_gpl) - LOAD_OFFSET) { \
VMLINUX_SYMBOL(__start___kcrctab_gpl) = .; \
- *(__kcrctab_gpl) \
+ *(SORT(___kcrctab_gpl__*)) \
VMLINUX_SYMBOL(__stop___kcrctab_gpl) = .; \
} \
\
/* Kernel symbol table: Normal unused symbols */ \
__kcrctab_unused : AT(ADDR(__kcrctab_unused) - LOAD_OFFSET) { \
VMLINUX_SYMBOL(__start___kcrctab_unused) = .; \
- *(__kcrctab_unused) \
+ *(SORT(___kcrctab_unused__*)) \
VMLINUX_SYMBOL(__stop___kcrctab_unused) = .; \
} \
\
/* Kernel symbol table: GPL-only unused symbols */ \
__kcrctab_unused_gpl : AT(ADDR(__kcrctab_unused_gpl) - LOAD_OFFSET) { \
VMLINUX_SYMBOL(__start___kcrctab_unused_gpl) = .; \
- *(__kcrctab_unused_gpl) \
+ *(SORT(___kcrctab_unused_gpl__*)) \
VMLINUX_SYMBOL(__stop___kcrctab_unused_gpl) = .; \
} \
\
/* Kernel symbol table: GPL-future-only symbols */ \
__kcrctab_gpl_future : AT(ADDR(__kcrctab_gpl_future) - LOAD_OFFSET) { \
VMLINUX_SYMBOL(__start___kcrctab_gpl_future) = .; \
- *(__kcrctab_gpl_future) \
+ *(SORT(___kcrctab_gpl_future__*)) \
VMLINUX_SYMBOL(__stop___kcrctab_gpl_future) = .; \
} \
\
diff --git a/include/linux/module.h b/include/linux/module.h
index 5de4204..cfb9563 100644
--- a/include/linux/module.h
+++ b/include/linux/module.h
@@ -223,7 +223,7 @@ struct module_use {
extern void *__crc_##sym __attribute__((weak)); \
static const unsigned long __kcrctab_##sym \
__used \
- __attribute__((section("__kcrctab" sec), unused)) \
+ __attribute__((section("___kcrctab" sec "__"#sym), unused)) \
= (unsigned long) &__crc_##sym;
#else
#define __CRC_SYMBOL(sym, sec)
@@ -238,7 +238,7 @@ struct module_use {
= MODULE_SYMBOL_PREFIX #sym; \
static const struct kernel_symbol __ksymtab_##sym \
__used \
- __attribute__((section("__ksymtab" sec), unused)) \
+ __attribute__((section("___ksymtab" sec "__"#sym), unused)) \
= { (unsigned long)&sym, __kstrtab_##sym }
#define EXPORT_SYMBOL(sym) \
diff --git a/scripts/module-common.lds b/scripts/module-common.lds
index 47a1f9a..055a8d5 100644
--- a/scripts/module-common.lds
+++ b/scripts/module-common.lds
@@ -5,4 +5,15 @@
*/
SECTIONS {
/DISCARD/ : { *(.discard) }
+
+ __ksymtab : { *(SORT(___ksymtab__*)) }
+ __ksymtab_gpl : { *(SORT(___ksymtab_gpl__*)) }
+ __ksymtab_unused : { *(SORT(___ksymtab_unused__*)) }
+ __ksymtab_unused_gpl : { *(SORT(___ksymtab_unused_gpl__*)) }
+ __ksymtab_gpl_future : { *(SORT(___ksymtab_gpl_future__*)) }
+ __kcrctab : { *(SORT(___kcrctab__*)) }
+ __kcrctab_gpl : { *(SORT(___kcrctab_gpl__*)) }
+ __kcrctab_unused : { *(SORT(___kcrctab_unused__*)) }
+ __kcrctab_unused_gpl : { *(SORT(___kcrctab_unused_gpl__*)) }
+ __kcrctab_gpl_future : { *(SORT(___kcrctab_gpl_future__*)) }
}
--
1.7.4.1
^ permalink raw reply related
* [PATCH 1/4] module: Restructure each_symbol() code
From: Alessio Igor Bogani @ 2011-04-16 13:26 UTC (permalink / raw)
To: Rusty Russell, Tim Abbott, Anders Kaseorg, Jason Wessel, Tim Bird
Cc: LKML, Linux Embedded, Alessio Igor Bogani
In-Reply-To: <1302960373-5309-1-git-send-email-abogani@kernel.org>
Restructure code to better integrate future improvements.
This work was supported by a hardware donation from the CE Linux Forum.
Signed-off-by: Alessio Igor Bogani <abogani@kernel.org>
Signed-off-by: Anders Kaseorg <andersk@ksplice.com>
---
kernel/module.c | 75 ++++++++++++++++++++++++++++++++++++++++--------------
1 files changed, 55 insertions(+), 20 deletions(-)
diff --git a/kernel/module.c b/kernel/module.c
index d5938a5..b438b25 100644
--- a/kernel/module.c
+++ b/kernel/module.c
@@ -235,28 +235,28 @@ extern const unsigned long __start___kcrctab_unused_gpl[];
#define symversion(base, idx) ((base != NULL) ? ((base) + (idx)) : NULL)
#endif
-static bool each_symbol_in_section(const struct symsearch *arr,
- unsigned int arrsize,
- struct module *owner,
- bool (*fn)(const struct symsearch *syms,
- struct module *owner,
- unsigned int symnum, void *data),
- void *data)
+static bool each_symsearch_in_section(const struct symsearch *arr,
+ unsigned int arrsize,
+ struct module *owner,
+ bool (*fn)(const struct symsearch *syms,
+ struct module *owner,
+ void *data),
+ void *data)
{
- unsigned int i, j;
+ unsigned int j;
for (j = 0; j < arrsize; j++) {
- for (i = 0; i < arr[j].stop - arr[j].start; i++)
- if (fn(&arr[j], owner, i, data))
- return true;
+ if (fn(&arr[j], owner, data))
+ return true;
}
return false;
}
/* Returns true as soon as fn returns true, otherwise false. */
-bool each_symbol(bool (*fn)(const struct symsearch *arr, struct module *owner,
- unsigned int symnum, void *data), void *data)
+static bool each_symsearch(bool (*fn)(const struct symsearch *syms,
+ struct module *owner, void *data),
+ void *data)
{
struct module *mod;
static const struct symsearch arr[] = {
@@ -278,7 +278,7 @@ bool each_symbol(bool (*fn)(const struct symsearch *arr, struct module *owner,
#endif
};
- if (each_symbol_in_section(arr, ARRAY_SIZE(arr), NULL, fn, data))
+ if (each_symsearch_in_section(arr, ARRAY_SIZE(arr), NULL, fn, data))
return true;
list_for_each_entry_rcu(mod, &modules, list) {
@@ -304,11 +304,39 @@ bool each_symbol(bool (*fn)(const struct symsearch *arr, struct module *owner,
#endif
};
- if (each_symbol_in_section(arr, ARRAY_SIZE(arr), mod, fn, data))
+ if (each_symsearch_in_section(arr, ARRAY_SIZE(arr), mod, fn,
+ data))
return true;
}
return false;
}
+
+struct each_symbol_arg {
+ bool (*fn)(const struct symsearch *arr, struct module *owner,
+ unsigned int symnum, void *data);
+ void *data;
+};
+
+static bool each_symbol_in_symsearch(const struct symsearch *syms,
+ struct module *owner, void *data)
+{
+ struct each_symbol_arg *esa = data;
+ unsigned int i;
+
+ for (i = 0; i < syms->stop - syms->start; i++) {
+ if (esa->fn(syms, owner, i, esa->data))
+ return true;
+ }
+ return false;
+}
+
+/* Returns true as soon as fn returns true, otherwise false. */
+bool each_symbol(bool (*fn)(const struct symsearch *arr, struct module *owner,
+ unsigned int symnum, void *data), void *data)
+{
+ struct each_symbol_arg esa = {fn, data};
+ return each_symsearch(each_symbol_in_symsearch, &esa);
+}
EXPORT_SYMBOL_GPL(each_symbol);
struct find_symbol_arg {
@@ -323,13 +351,20 @@ struct find_symbol_arg {
const struct kernel_symbol *sym;
};
-static bool find_symbol_in_section(const struct symsearch *syms,
- struct module *owner,
- unsigned int symnum, void *data)
+static bool find_symbol_in_symsearch(const struct symsearch *syms,
+ struct module *owner,
+ void *data)
{
struct find_symbol_arg *fsa = data;
+ unsigned int symnum;
+ int result;
- if (strcmp(syms->start[symnum].name, fsa->name) != 0)
+ for (symnum = 0; symnum < syms->stop - syms->start; symnum++) {
+ result = strcmp(fsa->name, syms->start[symnum].name);
+ if (result == 0)
+ break;
+ }
+ if (symnum >= syms->stop - syms->start)
return false;
if (!fsa->gplok) {
@@ -379,7 +414,7 @@ const struct kernel_symbol *find_symbol(const char *name,
fsa.gplok = gplok;
fsa.warn = warn;
- if (each_symbol(find_symbol_in_section, &fsa)) {
+ if (each_symsearch(find_symbol_in_symsearch, &fsa)) {
if (owner)
*owner = fsa.owner;
if (crc)
--
1.7.4.1
^ permalink raw reply related
* [PATCH 0/4] Speed up the symbols' resolution process V4
From: Alessio Igor Bogani @ 2011-04-16 13:26 UTC (permalink / raw)
To: Rusty Russell, Tim Abbott, Anders Kaseorg, Jason Wessel, Tim Bird
Cc: LKML, Linux Embedded, Alessio Igor Bogani
The intent of this patch is to speed up the symbols resolution process.
This objective is achieved by sorting all ksymtab* and kcrctab* symbols
(those which reside both in the kernel and in the modules) and thus use the
fast binary search.
To avoid adding lots of code for symbols sorting I rely on the linker which can
easily do the job thanks to a little trick. The trick isn't really beautiful to
see but permits minimal changes to the code and build process. Indeed the patch
is very simple and short.
In the first place I changed the code for place every symbol in a different
section (for example: "___ksymtab" sec "__" #sym) at compile time (this the
above mentioned trick!). Thus I request to the linker to sort and merge all
these sections into the appropriate ones (for example: "__ksymtab") at link
time using the linker scripts. Once all symbols are sorted we can use binary
search instead of the linear one.
I'm fairly sure that this is a good speed improvement even though I haven't
made any comprehensive benchmarking (but follow a simple one). In any case
I would be very happy to receive suggestions about how made it. Collaterally,
the boot time should be reduced also (proportionally to the number of modules
and symbols nvolved at boot stage).
I hope that you find that interesting!
This work was supported by a hardware donation from the CE Linux Forum.
Thanks to Ian Lance Taylor for help about how the linker works.
Changes since V3:
*) Please ignore this version completely
Changes since V2:
*) Fix a bug in each_symbol() semantics by Anders Kaseorg
*) Split the work in three patches as requested by Rusty Russell
*) Add a generic binary search implementation made by Tim Abbott
*) Remove CONFIG_SYMBOLS_BSEARCH kernel option
Changes since V1:
*) Merge all patches into only one
*) Remove few useless things
*) Introduce CONFIG_SYMBOLS_BSEARCH kernel option
Alessio Igor Bogani (3):
module: Restructure each_symbol() code
module: Sort exported symbols
module: Use the binary search for symbols resolution
Tim Abbott (1):
lib: Add generic binary search function to the kernel.
include/asm-generic/vmlinux.lds.h | 20 ++++----
include/linux/bsearch.h | 9 ++++
include/linux/module.h | 4 +-
kernel/module.c | 84 ++++++++++++++++++++++++++++---------
lib/Makefile | 3 +-
lib/bsearch.c | 53 +++++++++++++++++++++++
scripts/module-common.lds | 11 +++++
7 files changed, 151 insertions(+), 33 deletions(-)
create mode 100644 include/linux/bsearch.h
create mode 100644 lib/bsearch.c
--
1.7.4.1
^ permalink raw reply
* Re: [PATCH] extra/1 Allow setting the maximum KBUS message size
From: Jonathan Corbet @ 2011-04-15 22:46 UTC (permalink / raw)
To: Tony Ibbs
Cc: Grant Likely, lkml, Linux-embedded, Tibs at Kynesim,
Richard Watts
In-Reply-To: <32934D05-E7A7-4A2C-92EF-96A0580F2234@tonyibbs.co.uk>
On Fri, 15 Apr 2011 22:34:53 +0100
Tony Ibbs <tibs@tonyibbs.co.uk> wrote:
> This patch provides mechanisms for setting an absolute maximum message
> size at compile time, and a per-device maximum at runtime.
It seems like a good step in the right direction. Do you really need to
add a bunch more configuration options, though? It seems like a
reasonable default and a way to change it (sysfs file, maybe) might be
better. Is there a way to cap the total memory used by the kbus subsystem?
The kzalloc() fixes seem like a good idea too, BUT: I honestly think that
the item at the top of your list, if you want to merge this code, must be
to get the user-space API more widely reviewed and accepted. It could, I
think, be a big sticking point, and it's something you want to try to
address sooner rather than later.
That means getting more people to look at the patch, which could be hard.
The problem is that, if you wait, they'll only squeal when the code is
close to going in, and you could find yourself set back a long way. A
good first step might be to CC Andrew Morton on your next posting.
Thanks,
jon
^ permalink raw reply
* [PATCH] extra/1 Allow setting the maximum KBUS message size
From: Tony Ibbs @ 2011-04-15 21:34 UTC (permalink / raw)
To: Jonathan Corbet
Cc: Grant Likely, lkml, Linux-embedded, Tibs at Kynesim,
Richard Watts
In-Reply-To: <DBA665CD-BE12-4DC8-9B3F-4170BED789BD@tonyibbs.co.uk>
On 22 Mar 2011, at 19:36, Jonathan Corbet wrote:
> - Does anything bound the size of a message fed into the kernel with
> write()? I couldn't find it. It seems like an application could
> consume arbitrary amounts of kernel memory.
This patch provides mechanisms for setting an absolute maximum message
size at compile time, and a per-device maximum at runtime.
The patch is relative to the results of the previous set of patches - I
assume this is better than resubmitting all of them for what is a
relatively small change.
> - It would be good to use the kernel's dynamic debugging and tracing
> facilities rather than rolling your own.
>
> - There's lots of kmalloc()/memset() pairs that could be kzalloc().
I shall address these next, although I'm afraid it may be a few days.
Thanks, by the way, for the timely LWN article on the dynamic debugging
interface.
Signed-off-by: Tony Ibbs <tibs@tonyibbs.co.uk>
---
Documentation/Kbus.txt | 15 ++++++++++-
include/linux/kbus_defns.h | 14 ++++++++++-
ipc/Kconfig | 32 ++++++++++++++++++++++++-
ipc/kbus_internal.h | 11 ++++++++
ipc/kbus_main.c | 57 ++++++++++++++++++++++++++++++++++++++++++++
5 files changed, 126 insertions(+), 3 deletions(-)
diff --git a/Documentation/Kbus.txt b/Documentation/Kbus.txt
index 7cf723fd6..16828b9 100644
--- a/Documentation/Kbus.txt
+++ b/Documentation/Kbus.txt
@@ -1058,6 +1058,18 @@ header file (``kbus_defns.h``). They are:
Both Python and C bindings provide a useful function to
extract the ``is_bind``, ``binder`` and ``name`` values from
the data.
+:MAXMSGSIZE: Set the maximum size of a KBUS message for this KBUS device,
+ and return the value that is set. This is the size of the
+ largest message that may be written to a KBUS Ksock. Trying
+ to write a longer message will result in an -EMSGSIZE error.
+ An attempt to set this value of 0 will just return the current
+ maximum size. Otherwise, the size requested may not be less
+ than 100, or more than the kernel configuration value
+ KBUS_ABS_MAX_MESSAGE_SIZE. The default maximum size is set by
+ the kernel configuration value KBUS_DEF_MAX_MESSAGE_SIZE, and
+ is typically 1024. The size being tested is that returned by
+ the KBUS_ENTIRE_MESSAGE_LEN macro - i.e., the size of an
+ equivalent "entire" message.
/proc/kbus/bindings
-------------------
@@ -1158,7 +1170,8 @@ as values inside the IOError exception.
:EINVAL: Something went wrong (generic error).
:EMSGSIZE: On attempting to write a message: Data was written after
the end of the message (i.e., after the final end guard
- of the message).
+ of the message), or an attempt was made to write a message
+ that is too long (see the MAXMSGSIZE ioctl).
:ENAMETOOLONG: On attempting to bind, unbind or send a message: The message
name is too long.
:ENOENT: On attempting to open a Ksock: There is no such device
diff --git a/include/linux/kbus_defns.h b/include/linux/kbus_defns.h
index 82779a6..29f6f99 100644
--- a/include/linux/kbus_defns.h
+++ b/include/linux/kbus_defns.h
@@ -655,9 +655,21 @@ struct kbus_replier_bind_event_data {
* of the specified values)
*/
#define KBUS_IOC_REPORTREPLIERBINDS _IOWR(KBUS_IOC_MAGIC, 17, char *)
+/*
+ * MAXMSGSIZE - set the maximum size of a KBUS message for this KBUS device.
+ * This may not be set to less than 100, or more than
+ * CONFIG_KBUS_ABS_MAX_MESSAGE_SIZE.
+ * arg (in): __u32, the requested maximum message size, or 0 to just
+ * request what the current limit is, 1 to request the absolute
+ * maximum size.
+ * arg (out): __u32, the maximum essage size after this call has
+ * succeeded
+ * retval: 0 for success, negative for failure
+ */
+#define KBUS_IOC_MAXMSGSIZE _IOWR(KBUS_IOC_MAGIC, 18, char *)
/* If adding another IOCTL, remember to increment the next number! */
-#define KBUS_IOC_MAXNR 17
+#define KBUS_IOC_MAXNR 18
#if !__KERNEL__ && defined(__cplusplus)
}
diff --git a/ipc/Kconfig b/ipc/Kconfig
index 808d742..603b2f6 100644
--- a/ipc/Kconfig
+++ b/ipc/Kconfig
@@ -113,5 +113,35 @@ config KBUS_MAX_UNSENT_UNBIND_MESSAGES
If unsure, choose the default.
-endif # KBUS
+config KBUS_ABS_MAX_MESSAGE_SIZE
+ int "Absolute maximum KBUS mesage size"
+ default 1024
+ range 100 2147483647
+ ---help---
+ This sets the absolute maximum size of an individual KBUS message,
+ that is, the size of the largest KBUS message that may be written
+ to a KBUS device node.
+
+ It is not possible to set the maximum message size greater than
+ this value using the KBUS_IOC_MAXMSGSIZE ioctl.
+ The size is measured as by the KBUS_ENTIRE_MSG_LEN macro, and
+ includes the message header (80 bytes on a 32-bit system).
+
+config KBUS_DEF_MAX_MESSAGE_SIZE
+ int "Default maximum KBUS mesage size"
+ default 1024
+ range 100 KBUS_ABS_MAX_MESSAGE_SIZE
+ ---help---
+ This sets the default maximum size of an individual KBUS message,
+ that is, the size of the largest KBUS message that may be written
+ to a KBUS device node.
+
+ It may be altered at runtime, for a particular KBUS device, with
+ the KBUS_IOC_MAXMSGSIZE ioctl, up to a limit of
+ KBUS_ABS_MAX_MESSAGE_SIZE.
+
+ The size is measured as by the KBUS_ENTIRE_MSG_LEN macro, and
+ includes the message header (80 bytes on a 32-bit system).
+
+endif # KBUS
diff --git a/ipc/kbus_internal.h b/ipc/kbus_internal.h
index a24fcaf..51d512c 100644
--- a/ipc/kbus_internal.h
+++ b/ipc/kbus_internal.h
@@ -86,6 +86,14 @@
#define CONFIG_KBUS_DEF_NUM_DEVICES 1
#endif
+#ifndef CONFIG_KBUS_ABS_MAX_MESSAGE_SIZE
+#define CONFIG_KBUS_ABS_MAX_MESSAGE_SIZE 1024
+#endif
+
+#ifndef CONFIG_KBUS_DEF_MAX_MESSAGE_SIZE
+#define CONFIG_KBUS_DEF_MAX_MESSAGE_SIZE 1024
+#endif
+
/*
* Our initial array sizes could arguably be made configurable
* for tuning, if we discover this is useful
@@ -685,6 +693,9 @@ struct kbus_dev {
struct list_head unsent_unbind_msg_list;
u32 unsent_unbind_msg_count;
int unsent_unbind_is_tragic;
+
+ /* The maximum message size that may be written to this device */
+ u32 max_message_size;
};
/*
diff --git a/ipc/kbus_main.c b/ipc/kbus_main.c
index e99bfca..64f863a 100644
--- a/ipc/kbus_main.c
+++ b/ipc/kbus_main.c
@@ -615,6 +615,8 @@ static int kbus_check_message_written(struct kbus_dev *dev,
struct kbus_message_header *user_msg =
(struct kbus_message_header *)&this->user_msg;
+ int msg_size;
+
if (this == NULL) {
dev_err(dev->dev, "pid %u [%s]"
" Tried to check NULL message\n",
@@ -683,6 +685,15 @@ static int kbus_check_message_written(struct kbus_dev *dev,
current->pid, current->comm);
return -EINVAL;
}
+
+ msg_size = KBUS_ENTIRE_MSG_LEN(user_msg->name_len, user_msg->data_len);
+ if (msg_size > dev->max_message_size) {
+ dev_err(dev->dev, "pid %u [%s]"
+ "Message size is %d, more than the maximum %d\n",
+ current->pid, current->comm,
+ msg_size, dev->max_message_size);
+ return -EMSGSIZE;
+ }
return 0;
}
@@ -4150,6 +4161,39 @@ static int kbus_set_report_binds(struct kbus_private_data *priv,
return __put_user(old_value, (u32 __user *) arg);
}
+static int kbus_maxmsgsize(struct kbus_private_data *priv,
+ unsigned long arg)
+{
+ int retval = 0;
+ u32 requested_max;
+
+ retval = __get_user(requested_max, (u32 __user *) arg);
+ if (retval)
+ return retval;
+
+ kbus_maybe_dbg(priv->dev, "%u MAXMSGSIZE requests %u (was %u)\n",
+ priv->id, requested_max, priv->dev->max_message_size);
+
+ dev_dbg(priv->dev->dev, " abs max %d, def max %d\n",
+ CONFIG_KBUS_ABS_MAX_MESSAGE_SIZE,
+ CONFIG_KBUS_DEF_MAX_MESSAGE_SIZE);
+
+ /* A value of 0 is a query for the current length */
+ /* A value of 1 is a query for the absolute maximum */
+ if (requested_max == 0)
+ return __put_user(priv->dev->max_message_size,
+ (u32 __user *) arg);
+ else if (requested_max == 1)
+ return __put_user(CONFIG_KBUS_ABS_MAX_MESSAGE_SIZE,
+ (u32 __user *) arg);
+ else if (requested_max < 100 ||
+ requested_max > CONFIG_KBUS_ABS_MAX_MESSAGE_SIZE)
+ return -EINVAL;
+
+ priv->dev->max_message_size = requested_max;
+ return __put_user(priv->dev->max_message_size, (u32 __user *) arg);
+}
+
static long kbus_ioctl(struct file *filp, unsigned int cmd, unsigned long arg)
{
int err = 0;
@@ -4357,6 +4401,18 @@ static long kbus_ioctl(struct file *filp, unsigned int cmd, unsigned long arg)
retval = kbus_set_report_binds(priv, dev, arg);
break;
+ case KBUS_IOC_MAXMSGSIZE:
+ /*
+ * Set (and/or query) maximum message size
+ *
+ * arg in: 0 or 1 (for query of current maximum or absolute
+ * maximu) or maximum size wanted
+ * arg out: maximum size allowed
+ * return: 0 means OK, otherwise not OK
+ */
+ retval = kbus_maxmsgsize(priv, arg);
+ break;
+
default:
/* *Should* be redundant, if we got our range checks right */
retval = -ENOTTY;
@@ -4545,6 +4601,7 @@ static int kbus_setup_new_device(int which)
new->index = which;
new->verbose = KBUS_DEFAULT_VERBOSE_SETTING;
+ new->max_message_size = CONFIG_KBUS_DEF_MAX_MESSAGE_SIZE;
new->dev = device_create(kbus_class_p, NULL,
this_devno, NULL, "kbus%d", which);
--
1.7.4.1
^ permalink raw reply related
* [PATCH 4/4] module: Use the binary search for symbols resolution
From: Alessio Igor Bogani @ 2011-04-15 15:24 UTC (permalink / raw)
To: Rusty Russell, Tim Abbott, Anders Kaseorg, Jason Wessel, Tim Bird
Cc: LKML, Linux Embedded, Alessio Igor Bogani
In-Reply-To: <1302881097-563-1-git-send-email-abogani@kernel.org>
Takes advantage of the order and locates symbols using binary search.
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 | 12 ++++++++----
1 files changed, 8 insertions(+), 4 deletions(-)
diff --git a/kernel/module.c b/kernel/module.c
index 8845a0b..731173c 100644
--- a/kernel/module.c
+++ b/kernel/module.c
@@ -57,6 +57,7 @@
#include <linux/kmemleak.h>
#include <linux/jump_label.h>
#include <linux/pfn.h>
+#include <linux/bsearch.h>
#define CREATE_TRACE_POINTS
#include <trace/events/module.h>
@@ -244,12 +245,15 @@ static bool each_symbol_in_section(const struct symsearch *arr,
unsigned int symnum, void *data),
void *data)
{
- unsigned int i, j;
+ unsigned int j;
+ const struct kernel_symbol *sym, *start;
+ size_t size = sizeof(struct kernel_symbol);
for (j = 0; j < arrsize; j++) {
- for (i = 0; i < arr[j].stop - arr[j].start; i++)
- if (cmp(data, &arr[j].start[i]) == 0)
- return fn(&arr[j], owner, i, data);
+ start = arr[j].start;
+ sym = bsearch(data, start, arr[j].stop - arr[j].start, size, cmp);
+ if (sym != NULL)
+ return fn(&arr[j], owner, sym - start, data);
}
return false;
--
1.7.0.4
^ permalink raw reply related
* [PATCH 3/4] lib: Add generic binary search function to the kernel.
From: Alessio Igor Bogani @ 2011-04-15 15:24 UTC (permalink / raw)
To: Rusty Russell, Tim Abbott, Anders Kaseorg, Jason Wessel, Tim Bird
Cc: LKML, Linux Embedded, Tim Abbott, Rusty Russell,
Alessio Igor Bogani
In-Reply-To: <1302881097-563-1-git-send-email-abogani@kernel.org>
From: Tim Abbott <tabbott@ksplice.com>
There a large number hand-coded binary searches in the kernel (run
"git grep search | grep binary" to find many of them). Since in my
experience, hand-coding binary searches can be error-prone, it seems
worth cleaning this up by providing a generic binary search function.
This generic binary search implementation comes from Ksplice. It has
the same basic API as the C library bsearch() function. Ksplice uses
it in half a dozen places with 4 different comparison functions, and I
think our code is substantially cleaner because of this.
Signed-off-by: Tim Abbott <tabbott@ksplice.com>
Extra-bikeshedding-by: Alan Jenkins <alan-jenkins@tuffmail.co.uk>
Extra-bikeshedding-by: André Goddard Rosa <andre.goddard@gmail.com>
Extra-bikeshedding-by: Rusty Russell <rusty@rustcorp.com.au>
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
Signed-off-by: Alessio Igor Bogani <abogani@kernel.org>
---
include/linux/bsearch.h | 9 ++++++++
lib/Makefile | 3 +-
lib/bsearch.c | 53 +++++++++++++++++++++++++++++++++++++++++++++++
3 files changed, 64 insertions(+), 1 deletions(-)
create mode 100644 include/linux/bsearch.h
create mode 100644 lib/bsearch.c
diff --git a/include/linux/bsearch.h b/include/linux/bsearch.h
new file mode 100644
index 0000000..90b1aa8
--- /dev/null
+++ b/include/linux/bsearch.h
@@ -0,0 +1,9 @@
+#ifndef _LINUX_BSEARCH_H
+#define _LINUX_BSEARCH_H
+
+#include <linux/types.h>
+
+void *bsearch(const void *key, const void *base, size_t num, size_t size,
+ int (*cmp)(const void *key, const void *elt));
+
+#endif /* _LINUX_BSEARCH_H */
diff --git a/lib/Makefile b/lib/Makefile
index ef0f285..4b49a24 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -21,7 +21,8 @@ lib-y += kobject.o kref.o klist.o
obj-y += bcd.o div64.o sort.o parser.o halfmd4.o debug_locks.o random32.o \
bust_spinlocks.o hexdump.o kasprintf.o bitmap.o scatterlist.o \
- string_helpers.o gcd.o lcm.o list_sort.o uuid.o flex_array.o
+ string_helpers.o gcd.o lcm.o list_sort.o uuid.o flex_array.o \
+ bsearch.o
obj-y += kstrtox.o
obj-$(CONFIG_TEST_KSTRTOX) += test-kstrtox.o
diff --git a/lib/bsearch.c b/lib/bsearch.c
new file mode 100644
index 0000000..5b54758
--- /dev/null
+++ b/lib/bsearch.c
@@ -0,0 +1,53 @@
+/*
+ * A generic implementation of binary search for the Linux kernel
+ *
+ * Copyright (C) 2008-2009 Ksplice, Inc.
+ * Author: Tim Abbott <tabbott@ksplice.com>
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License as
+ * published by the Free Software Foundation; version 2.
+ */
+
+#include <linux/module.h>
+#include <linux/bsearch.h>
+
+/*
+ * bsearch - binary search an array of elements
+ * @key: pointer to item being searched for
+ * @base: pointer to first element to search
+ * @num: number of elements
+ * @size: size of each element
+ * @cmp: pointer to comparison function
+ *
+ * This function does a binary search on the given array. The
+ * contents of the array should already be in ascending sorted order
+ * under the provided comparison function.
+ *
+ * Note that the key need not have the same type as the elements in
+ * the array, e.g. key could be a string and the comparison function
+ * could compare the string with the struct's name field. However, if
+ * the key and elements in the array are of the same type, you can use
+ * the same comparison function for both sort() and bsearch().
+ */
+void *bsearch(const void *key, const void *base, size_t num, size_t size,
+ int (*cmp)(const void *key, const void *elt))
+{
+ size_t start = 0, end = num;
+ int result;
+
+ while (start < end) {
+ size_t mid = start + (end - start) / 2;
+
+ result = cmp(key, base + mid * size);
+ if (result < 0)
+ end = mid;
+ else if (result > 0)
+ start = mid + 1;
+ else
+ return (void *)base + mid * size;
+ }
+
+ return NULL;
+}
+EXPORT_SYMBOL(bsearch);
--
1.7.0.4
^ permalink raw reply related
* [PATCH 2/4] module: Sort exported symbols
From: Alessio Igor Bogani @ 2011-04-15 15:24 UTC (permalink / raw)
To: Rusty Russell, Tim Abbott, Anders Kaseorg, Jason Wessel, Tim Bird
Cc: LKML, Linux Embedded, Alessio Igor Bogani
In-Reply-To: <1302881097-563-1-git-send-email-abogani@kernel.org>
This patch places every exported symbol in its own section
(i.e. "___ksymtab__printk"). Thus the linker will use its SORT() directive
to sort and finally merge all symbol in the right and final section
(i.e. "__ksymtab").
This work was supported by a hardware donation from the CE Linux Forum.
Signed-off-by: Alessio Igor Bogani <abogani@kernel.org>
---
include/asm-generic/vmlinux.lds.h | 20 ++++++++++----------
include/linux/module.h | 4 ++--
scripts/module-common.lds | 11 +++++++++++
3 files changed, 23 insertions(+), 12 deletions(-)
diff --git a/include/asm-generic/vmlinux.lds.h b/include/asm-generic/vmlinux.lds.h
index bd297a2..349e356 100644
--- a/include/asm-generic/vmlinux.lds.h
+++ b/include/asm-generic/vmlinux.lds.h
@@ -274,70 +274,70 @@
/* Kernel symbol table: Normal symbols */ \
__ksymtab : AT(ADDR(__ksymtab) - LOAD_OFFSET) { \
VMLINUX_SYMBOL(__start___ksymtab) = .; \
- *(__ksymtab) \
+ *(SORT(___ksymtab__*)) \
VMLINUX_SYMBOL(__stop___ksymtab) = .; \
} \
\
/* Kernel symbol table: GPL-only symbols */ \
__ksymtab_gpl : AT(ADDR(__ksymtab_gpl) - LOAD_OFFSET) { \
VMLINUX_SYMBOL(__start___ksymtab_gpl) = .; \
- *(__ksymtab_gpl) \
+ *(SORT(___ksymtab_gpl__*)) \
VMLINUX_SYMBOL(__stop___ksymtab_gpl) = .; \
} \
\
/* Kernel symbol table: Normal unused symbols */ \
__ksymtab_unused : AT(ADDR(__ksymtab_unused) - LOAD_OFFSET) { \
VMLINUX_SYMBOL(__start___ksymtab_unused) = .; \
- *(__ksymtab_unused) \
+ *(SORT(___ksymtab_unused__*)) \
VMLINUX_SYMBOL(__stop___ksymtab_unused) = .; \
} \
\
/* Kernel symbol table: GPL-only unused symbols */ \
__ksymtab_unused_gpl : AT(ADDR(__ksymtab_unused_gpl) - LOAD_OFFSET) { \
VMLINUX_SYMBOL(__start___ksymtab_unused_gpl) = .; \
- *(__ksymtab_unused_gpl) \
+ *(SORT(___ksymtab_unused_gpl__*)) \
VMLINUX_SYMBOL(__stop___ksymtab_unused_gpl) = .; \
} \
\
/* Kernel symbol table: GPL-future-only symbols */ \
__ksymtab_gpl_future : AT(ADDR(__ksymtab_gpl_future) - LOAD_OFFSET) { \
VMLINUX_SYMBOL(__start___ksymtab_gpl_future) = .; \
- *(__ksymtab_gpl_future) \
+ *(SORT(___ksymtab_gpl_future__*)) \
VMLINUX_SYMBOL(__stop___ksymtab_gpl_future) = .; \
} \
\
/* Kernel symbol table: Normal symbols */ \
__kcrctab : AT(ADDR(__kcrctab) - LOAD_OFFSET) { \
VMLINUX_SYMBOL(__start___kcrctab) = .; \
- *(__kcrctab) \
+ *(SORT(___kcrctab__*)) \
VMLINUX_SYMBOL(__stop___kcrctab) = .; \
} \
\
/* Kernel symbol table: GPL-only symbols */ \
__kcrctab_gpl : AT(ADDR(__kcrctab_gpl) - LOAD_OFFSET) { \
VMLINUX_SYMBOL(__start___kcrctab_gpl) = .; \
- *(__kcrctab_gpl) \
+ *(SORT(___kcrctab_gpl__*)) \
VMLINUX_SYMBOL(__stop___kcrctab_gpl) = .; \
} \
\
/* Kernel symbol table: Normal unused symbols */ \
__kcrctab_unused : AT(ADDR(__kcrctab_unused) - LOAD_OFFSET) { \
VMLINUX_SYMBOL(__start___kcrctab_unused) = .; \
- *(__kcrctab_unused) \
+ *(SORT(___kcrctab_unused__*)) \
VMLINUX_SYMBOL(__stop___kcrctab_unused) = .; \
} \
\
/* Kernel symbol table: GPL-only unused symbols */ \
__kcrctab_unused_gpl : AT(ADDR(__kcrctab_unused_gpl) - LOAD_OFFSET) { \
VMLINUX_SYMBOL(__start___kcrctab_unused_gpl) = .; \
- *(__kcrctab_unused_gpl) \
+ *(SORT(___kcrctab_unused_gpl__*)) \
VMLINUX_SYMBOL(__stop___kcrctab_unused_gpl) = .; \
} \
\
/* Kernel symbol table: GPL-future-only symbols */ \
__kcrctab_gpl_future : AT(ADDR(__kcrctab_gpl_future) - LOAD_OFFSET) { \
VMLINUX_SYMBOL(__start___kcrctab_gpl_future) = .; \
- *(__kcrctab_gpl_future) \
+ *(SORT(___kcrctab_gpl_future__*)) \
VMLINUX_SYMBOL(__stop___kcrctab_gpl_future) = .; \
} \
\
diff --git a/include/linux/module.h b/include/linux/module.h
index b62f0a2..853f566 100644
--- a/include/linux/module.h
+++ b/include/linux/module.h
@@ -223,7 +223,7 @@ struct module_use {
extern void *__crc_##sym __attribute__((weak)); \
static const unsigned long __kcrctab_##sym \
__used \
- __attribute__((section("__kcrctab" sec), unused)) \
+ __attribute__((section("___kcrctab" sec "__"#sym), unused)) \
= (unsigned long) &__crc_##sym;
#else
#define __CRC_SYMBOL(sym, sec)
@@ -238,7 +238,7 @@ struct module_use {
= MODULE_SYMBOL_PREFIX #sym; \
static const struct kernel_symbol __ksymtab_##sym \
__used \
- __attribute__((section("__ksymtab" sec), unused)) \
+ __attribute__((section("___ksymtab" sec "__"#sym), unused)) \
= { (unsigned long)&sym, __kstrtab_##sym }
#define EXPORT_SYMBOL(sym) \
diff --git a/scripts/module-common.lds b/scripts/module-common.lds
index 47a1f9a..055a8d5 100644
--- a/scripts/module-common.lds
+++ b/scripts/module-common.lds
@@ -5,4 +5,15 @@
*/
SECTIONS {
/DISCARD/ : { *(.discard) }
+
+ __ksymtab : { *(SORT(___ksymtab__*)) }
+ __ksymtab_gpl : { *(SORT(___ksymtab_gpl__*)) }
+ __ksymtab_unused : { *(SORT(___ksymtab_unused__*)) }
+ __ksymtab_unused_gpl : { *(SORT(___ksymtab_unused_gpl__*)) }
+ __ksymtab_gpl_future : { *(SORT(___ksymtab_gpl_future__*)) }
+ __kcrctab : { *(SORT(___kcrctab__*)) }
+ __kcrctab_gpl : { *(SORT(___kcrctab_gpl__*)) }
+ __kcrctab_unused : { *(SORT(___kcrctab_unused__*)) }
+ __kcrctab_unused_gpl : { *(SORT(___kcrctab_unused_gpl__*)) }
+ __kcrctab_gpl_future : { *(SORT(___kcrctab_gpl_future__*)) }
}
--
1.7.0.4
^ permalink raw reply related
* [PATCH 1/4] module: Split the find_symbol_in_section function
From: Alessio Igor Bogani @ 2011-04-15 15:24 UTC (permalink / raw)
To: Rusty Russell, Tim Abbott, Anders Kaseorg, Jason Wessel, Tim Bird
Cc: LKML, Linux Embedded, Alessio Igor Bogani
In-Reply-To: <1302881097-563-1-git-send-email-abogani@kernel.org>
Split the find_symbol_in_section() in two: the first one
(that is compare_symbol_in_section()) for compare values during the search and
the second one (that is found_symbol_in_section()) executed when values will be
found. Rename each_symbol() in search_symbol() to let its' users notice
the change.
This work was supported by a hardware donation from the CE Linux Forum.
Signed-off-by: Alessio Igor Bogani <abogani@kernel.org>
---
include/linux/module.h | 3 ++-
kernel/module.c | 29 ++++++++++++++++++-----------
2 files changed, 20 insertions(+), 12 deletions(-)
diff --git a/include/linux/module.h b/include/linux/module.h
index 5de4204..b62f0a2 100644
--- a/include/linux/module.h
+++ b/include/linux/module.h
@@ -475,7 +475,8 @@ const struct kernel_symbol *find_symbol(const char *name,
bool warn);
/* Walk the exported symbol table */
-bool each_symbol(bool (*fn)(const struct symsearch *arr, struct module *owner,
+bool search_symbol(int (*cmp) (const void *va, const void *vb),
+ bool (*fn)(const struct symsearch *arr, struct module *owner,
unsigned int symnum, void *data), void *data);
/* Returns 0 and fills in value, defined and namebuf, or -ERANGE if
diff --git a/kernel/module.c b/kernel/module.c
index d5938a5..8845a0b 100644
--- a/kernel/module.c
+++ b/kernel/module.c
@@ -238,6 +238,7 @@ extern const unsigned long __start___kcrctab_unused_gpl[];
static bool each_symbol_in_section(const struct symsearch *arr,
unsigned int arrsize,
struct module *owner,
+ int (*cmp) (const void *va, const void *vb),
bool (*fn)(const struct symsearch *syms,
struct module *owner,
unsigned int symnum, void *data),
@@ -247,15 +248,16 @@ static bool each_symbol_in_section(const struct symsearch *arr,
for (j = 0; j < arrsize; j++) {
for (i = 0; i < arr[j].stop - arr[j].start; i++)
- if (fn(&arr[j], owner, i, data))
- return true;
+ if (cmp(data, &arr[j].start[i]) == 0)
+ return fn(&arr[j], owner, i, data);
}
return false;
}
/* Returns true as soon as fn returns true, otherwise false. */
-bool each_symbol(bool (*fn)(const struct symsearch *arr, struct module *owner,
+bool search_symbol(int (*cmp) (const void *va, const void *data),
+ bool (*fn)(const struct symsearch *arr, struct module *owner,
unsigned int symnum, void *data), void *data)
{
struct module *mod;
@@ -278,7 +280,7 @@ bool each_symbol(bool (*fn)(const struct symsearch *arr, struct module *owner,
#endif
};
- if (each_symbol_in_section(arr, ARRAY_SIZE(arr), NULL, fn, data))
+ if (each_symbol_in_section(arr, ARRAY_SIZE(arr), NULL, cmp, fn, data))
return true;
list_for_each_entry_rcu(mod, &modules, list) {
@@ -304,12 +306,12 @@ bool each_symbol(bool (*fn)(const struct symsearch *arr, struct module *owner,
#endif
};
- if (each_symbol_in_section(arr, ARRAY_SIZE(arr), mod, fn, data))
+ if (each_symbol_in_section(arr, ARRAY_SIZE(arr), mod, cmp, fn, data))
return true;
}
return false;
}
-EXPORT_SYMBOL_GPL(each_symbol);
+EXPORT_SYMBOL_GPL(search_symbol);
struct find_symbol_arg {
/* Input */
@@ -323,15 +325,20 @@ struct find_symbol_arg {
const struct kernel_symbol *sym;
};
-static bool find_symbol_in_section(const struct symsearch *syms,
+static int compare_symbol_in_section(const void *va, const void *vb)
+{
+ const struct find_symbol_arg *a;
+ const struct kernel_symbol *b;
+ a = va; b = vb;
+ return strcmp(a->name, b->name);
+}
+
+static bool found_symbol_in_section(const struct symsearch *syms,
struct module *owner,
unsigned int symnum, void *data)
{
struct find_symbol_arg *fsa = data;
- if (strcmp(syms->start[symnum].name, fsa->name) != 0)
- return false;
-
if (!fsa->gplok) {
if (syms->licence == GPL_ONLY)
return false;
@@ -379,7 +386,7 @@ const struct kernel_symbol *find_symbol(const char *name,
fsa.gplok = gplok;
fsa.warn = warn;
- if (each_symbol(find_symbol_in_section, &fsa)) {
+ if (search_symbol(compare_symbol_in_section, found_symbol_in_section, &fsa)) {
if (owner)
*owner = fsa.owner;
if (crc)
--
1.7.0.4
^ permalink raw reply related
* [PATCH 0/4] Speed up the symbols' resolution process V3
From: Alessio Igor Bogani @ 2011-04-15 15:24 UTC (permalink / raw)
To: Rusty Russell, Tim Abbott, Anders Kaseorg, Jason Wessel, Tim Bird
Cc: LKML, Linux Embedded, Alessio Igor Bogani
The intent of this patch is to speed up the symbols resolution process.
This objective is achieved by sorting all ksymtab* and kcrctab* symbols
(those which reside both in the kernel and in the modules) and thus use the
fast binary search.
To avoid adding lots of code for symbols sorting I rely on the linker which can
easily do the job thanks to a little trick. The trick isn't really beautiful to
see but permits minimal changes to the code and build process. Indeed the patch
is very simple and short.
In the first place I changed the code for place every symbol in a different
section (for example: "___ksymtab" sec "__" #sym) at compile time (this the
above mentioned trick!). Thus I request to the linker to sort and merge all
these sections into the appropriate ones (for example: "__ksymtab") at link
time using the linker scripts. Once all symbols are sorted we can use binary
search instead of the linear one.
I'm fairly sure that this is a good speed improvement even though I haven't
made any comprehensive benchmarking (but follow a simple one). In any case
I would be very happy to receive suggestions about how made it. Collaterally,
the boot time should be reduced also (proportionally to the number of modules
and symbols nvolved at boot stage).
I hope that you find that interesting!
This work was supported by a hardware donation from the CE Linux Forum.
Thanks to Ian Lance Taylor for help about how the linker works.
Changes since V2:
*) Fix a bug in each_symbol() semantics by Anders Kaseorg
*) Split the work in three patches as requested by Rusty Russell
*) Add a generic binary search implementation made by Tim Abbott
*) Remove CONFIG_SYMBOLS_BSEARCH kernel option
Changes since V1:
*) Merge all patches into only one
*) Remove few useless things
*) Introduce CONFIG_SYMBOLS_BSEARCH kernel option
Alessio Igor Bogani (3):
module: Split the find_symbol_in_section function
module: Sort exported symbols
module: Use the binary search for symbols resolution
Tim Abbott (1):
lib: Add generic binary search function to the kernel.
include/asm-generic/vmlinux.lds.h | 20 +++++++-------
include/linux/bsearch.h | 9 ++++++
include/linux/module.h | 7 +++--
kernel/module.c | 37 ++++++++++++++++---------
lib/Makefile | 3 +-
lib/bsearch.c | 53 +++++++++++++++++++++++++++++++++++++
scripts/module-common.lds | 11 +++++++
7 files changed, 113 insertions(+), 27 deletions(-)
create mode 100644 include/linux/bsearch.h
create mode 100644 lib/bsearch.c
^ permalink raw reply
page: next (older) | prev (newer) | latest
- recent:[subjects (threaded)|topics (new)|topics (active)]
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox