Re: [RFC] 2.5.8 sort kernel tables

[Keith Owens]

On Thu, 18 Apr 2002 12:21:05 +0200, 
Matthias Andree <[e-mail]> wrote:
>On Thu, 18 Apr 2002, Keith Owens wrote:
>
>> + * Do not assume that the table from the linker is correct, sort it at boot
>> + * time.  Since 90%+ of the entries will be sorted, a bubble sort is good
>> + * enough, it only runs once per table per boot.  The sort only does binary
>> + * keys and only sorts in ascending order.
>
>Any real-world figures on how long this sort process would take on big
>tables on some sparc or i586 class box? (Just trying to figure if bubble
>is really adequate. It is if the table is indeed essentially sorted with
>only like 10 reversed neighbours or if it's short.)

The tables are almost sorted already.  It is just the occasional entry
that is out of order, e.g.

foo.o
  .text uses copy_to_user
  .text.init uses copy_to_user
bar.o
  .text users copy_to_user
baz.o
  .text users copy_to_user

Only the .text.init exception entry will be out of order, it will
require two passes over the table to sort it.  In the simplest case
there will be no out of order entries and one pass does the job.  The
number of out of order entries is a function of how much init and exit
code does special processing, not a lot.