A question sort_main_extable()

A question sort_main_extable()

[Peter Teoh]

Inside start_kernel() there is a call to sort_main_extable().

void sort_extable(struct exception_table_entry *start,
                 struct exception_table_entry *finish)
{
       sort(start, finish - start, sizeof(struct exception_table_entry),
            cmp_ex, NULL);
}

With reference to
http://tuxology.net/2008/07/08/benchmarking-boot-latency-on-x86/, I
think it can help bootup latency (how much I got no number) if the
sorting is done post-compilation time, instead of dynamically
everytime the system bootup.  (perhaps at the stage of modposting,
when all the vmlinux, kernel modules objects have been generated, so
extracting out the exceptions strings is possible?)  Is this a
possible optimization?

Sam, can it be done?

Thanks.


-- 
Regards,
Peter Teoh

Re: A question sort_main_extable()

[Arjan van de Ven]

On Fri, 21 Nov 2008 13:42:56 +0800
"Peter Teoh" <htmldeveloper@gmail.com> wrote:

> Inside start_kernel() there is a call to sort_main_extable().
> 
> void sort_extable(struct exception_table_entry *start,
>                  struct exception_table_entry *finish)
> {
>        sort(start, finish - start, sizeof(struct
> exception_table_entry), cmp_ex, NULL);
> }
> 
> With reference to
> http://tuxology.net/2008/07/08/benchmarking-boot-latency-on-x86/, I
> think it can help bootup latency (how much I got no number) if the
> sorting is done post-compilation time, instead of dynamically
> everytime the system bootup.  (perhaps at the stage of modposting,
> when all the vmlinux, kernel modules objects have been generated, so
> extracting out the exceptions strings is possible?)  Is this a
> possible optimization?

we used to do this but it was a pain and extremely fragile. Runtime
sorting makes it very robust at least.

The sort is really quick though; I've spent a lot of time on boot time
and this guy never showed up for me.



-- 
Arjan van de Ven 	Intel Open Source Technology Centre
For development, discussion and tips for power savings, 
visit http://www.lesswatts.org

Re: A question sort_main_extable()

[Peter Teoh]

Thanks Arjan.

On Fri, Nov 21, 2008 at 1:47 PM, Arjan van de Ven <arjan@infradead.org> wrote:
> On Fri, 21 Nov 2008 13:42:56 +0800
> "Peter Teoh" <htmldeveloper@gmail.com> wrote:
>
>> Inside start_kernel() there is a call to sort_main_extable().
>>
>> void sort_extable(struct exception_table_entry *start,
>>                  struct exception_table_entry *finish)
>> {
>>        sort(start, finish - start, sizeof(struct
>> exception_table_entry), cmp_ex, NULL);
>> }
>>

Sorting is one problem, possibly it is partially pre-ordered.

Another problem is memory usage.   Do you or anyone know the amount of
memory used?   In MS windows, there is an article dedicated to
explaining why bootup is quick - one of the contributing factor is
saving memory for only the necessary stuff.   Exception strings, being
rarely needed to be used, will not be loaded into memory until it is
really necessary.   At kernel compilation time, compiler will
intelligently collate all the strings together, and pushed it right to
the end of the kernel binary, avoiding unnecessary loading.   But then
it is a different architecture - as Windows allow swap-in of kernel
image during kernel runtime, unlike that of Linux Kernel - no swap-in
of kernel image at kernel runtime is allowed.

So I guessed there is no way to avoid loading in these exception
strings, even though it is really not needed......unless these can be
pushed out to a specialized kernel module, and used udevd to
dynamically load the module when needed?   Unless the size of memory
saved is substantial enough (how do you calculate that?), I don't
think it is justifiable to take these heavier path whenever strings
are needed.

-- 
Regards,
Peter Teoh

Re: A question sort_main_extable()

[Andi Kleen]

Arjan van de Ven <arjan@infradead.org> writes:
>
> we used to do this but it was a pain and extremely fragile. Runtime
> sorting makes it very robust at least.

It's not only extremly fragile, but just broken with out of line
section which gcc also generates these days.

>
> The sort is really quick though; I've spent a lot of time on boot time
> and this guy never showed up for me.

If you really wanted to speed it up you could actually just switch
over to a bubble sort. It's typically the best algorithm for nearly
already sorted input data, which this is.

But then as you say it's not worth it.

-Andi

-- 
ak@linux.intel.com