[RFC] 2.5.8 sort kernel tables

[RFC] 2.5.8 sort kernel tables

[Keith Owens]

The use of __init and __exit sections breaks the assumption that tables
such as __ex_table are sorted, it has already broken the dbe table in
mips on 2.5.  This patch against 2.5.8 adds a generic sort routine and
sorts the i386 exception table.

This sorting needs to be extended to several other tables, to all
architectures, to modutils (insmod loads some of these tables for
modules) and back ported to 2.4.  Before I spend the rest of the time,
any objections?

ndex: 8.1/init/main.c
--- 8.1/init/main.c Mon, 15 Apr 2002 13:28:23 +1000 kaos (linux-2.5/w/d/29_main.c 1.16 444)
+++ 8.1(w)/init/main.c Thu, 18 Apr 2002 19:36:40 +1000 kaos (linux-2.5/w/d/29_main.c 1.16 444)
@@ -257,6 +257,56 @@ static void __init parse_options(char *l
 	envp_init[envs+1] = NULL;
 }
 
+/* Quick and dirty bubble sort to ensure that certain kernel tables really are
+ * sorted.  Various kernel tables, in particular the exception entries, are
+ * assumed to be in ascending order.  These tables are built by the linker from
+ * sections in each object.  The linker is not a problem, it appends entries to
+ * the tables as each object is added to vmlinux.  However the use of __init and
+ * __exit in objects can break the ordering, within each object the entries are
+ * in order, the linker appends them in order but the entries are not in order
+ * across objects.
+ *
+ * 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.
+ */
+
+void __init sort_table(void *table, size_t entry_size, size_t entries, size_t key_size, size_t key_offset)
+{
+	char *a, *b;
+	int i, j, changed = 1;
+	char save[entry_size];
+	a = (char *)table;
+	if (key_size != 4 && key_size != 8) {
+		printk(KERN_ERR "sort_table key_size %d is incorrect\n", key_size);
+		return;
+	}
+	for (i = 0; i < entries && changed; a += entry_size, ++i) {
+		changed = 0;
+		b = a + entry_size;
+		for (j = i + 1; j < entries; b += entry_size, ++j) {
+			if (key_size == 4) {
+				if (*((__u32 *)(b+key_offset-entry_size)) >
+				    *((__u32 *)(b+key_offset))) {
+					memcpy(save, b, entry_size);
+					memcpy(b, b-entry_size, entry_size);
+					memcpy(b-entry_size, save, entry_size);
+					changed = 1;
+				}
+			}
+			else {
+				if (*((__u64 *)(b+key_offset-entry_size)) >
+				    *((__u64 *)(b+key_offset))) {
+					memcpy(save, b, entry_size);
+					memcpy(b, b-entry_size, entry_size);
+					memcpy(b-entry_size, save, entry_size);
+					changed = 1;
+				}
+			}
+		}
+	}
+}
 
 extern void setup_arch(char **);
 extern void cpu_idle(void);
@@ -343,6 +393,7 @@ asmlinkage void __init start_kernel(void
  */
 	lock_kernel();
 	printk(linux_banner);
+	sort_arch_tables();
 	setup_arch(&command_line);
 	setup_per_cpu_areas();
 	printk("Kernel command line: %s\n", saved_command_line);
Index: 8.1/arch/i386/mm/extable.c
--- 8.1/arch/i386/mm/extable.c Sat, 24 Nov 2001 05:28:08 +1100 kaos (linux-2.5/b/b/41_extable.c 1.1 444)
+++ 8.1(w)/arch/i386/mm/extable.c Thu, 18 Apr 2002 19:37:50 +1000 kaos (linux-2.5/b/b/41_extable.c 1.1 444)
@@ -31,6 +31,14 @@ search_one_table(const struct exception_
         return 0;
 }
 
+void __init sort_arch_tables(void)
+{
+	sort_table((void *) __start___ex_table, sizeof(*__start___ex_table),
+			__stop___ex_table - __start___ex_table,
+			sizeof(__start___ex_table->insn),
+			offsetof(typeof(*__start___ex_table), insn));
+}
+
 extern spinlock_t modlist_lock;
 
 unsigned long
Index: 8.1/include/linux/kernel.h
--- 8.1/include/linux/kernel.h Sat, 09 Feb 2002 15:37:49 +1100 kaos (linux-2.5/v/d/17_kernel.h 1.4 444)
+++ 8.1(w)/include/linux/kernel.h Thu, 18 Apr 2002 18:38:26 +1000 kaos (linux-2.5/v/d/17_kernel.h 1.4 444)
@@ -95,6 +95,9 @@ extern const char *print_tainted(void);
 #define TAINT_FORCED_MODULE		(1<<1)
 #define TAINT_UNSAFE_SMP		(1<<2)
 
+extern void sort_arch_tables(void);
+extern void sort_table(void *table, size_t entry_size, size_t entries, size_t key_size, size_t key_offset);
+
 #if DEBUG
 #define pr_debug(fmt,arg...) \
 	printk(KERN_DEBUG fmt,##arg)

Re: [RFC] 2.5.8 sort kernel tables

[Matthias Andree]

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.)

Re: [RFC] 2.5.8 sort kernel tables

[Keith Owens]

On Thu, 18 Apr 2002 12:21:05 +0200, 
Matthias Andree <matthias.andree@stud.uni-dortmund.de> 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.

Re: [RFC] 2.5.8 sort kernel tables

[Alan Cox]

> 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.)

If the table is 90% ordered an insertion sort searching from tail is even
more efficient for the general case and just as simple. Its still arguing
about milliseconds 8)

Re: [RFC] 2.5.8 sort kernel tables

[Paul Mackerras]

Keith Owens writes:

> The use of __init and __exit sections breaks the assumption that tables
> such as __ex_table are sorted, it has already broken the dbe table in
> mips on 2.5.  This patch against 2.5.8 adds a generic sort routine and
> sorts the i386 exception table.
> 
> This sorting needs to be extended to several other tables, to all
> architectures, to modutils (insmod loads some of these tables for

We already sort the kernel exception table on PPC using an insertion
sort.  We have chrp, pmac, prep sections as well as init, which is why
we had to do that.

BTW, do you have any valid examples of use of copy_to/from_user or
get/put_user in an init section?

Regards,
Paul.

Re: [RFC] 2.5.8 sort kernel tables

[Keith Owens]

On Thu, 18 Apr 2002 23:02:11 +1000 (EST), 
Paul Mackerras <paulus@samba.org> wrote:
>We already sort the kernel exception table on PPC using an insertion
>sort.  We have chrp, pmac, prep sections as well as init, which is why
>we had to do that.

Good, I will pinch that code and use it on all architectures.

>BTW, do you have any valid examples of use of copy_to/from_user or
>get/put_user in an init section?

No, I was using those functions as an example.  The problem is
__ex_table, there is other code that uses __ex_table besides
copy_to_user.  It is quite legal for an arch setup routine to use a
.fixup/__ex_table wrapper around code that might fail on some platforms
and to have that setup routine marked __init.

For example, arm #defines get8_unaligned_check which uses __ex_table.
__get_qspan_pci_config in ppc also uses __ex_table.  Use of any of
these macros (and others) in an __init section will generate unsorted
tables.  One table has already broken because of out of order text
sections.  Other tables may be broken, depending on what __init code an
architecture uses.

The real nasty is that we do not know if the table is broken until an
exception table entry is used and we fail to find an entry because the
table is not sorted.  Some exception table entries will work, others
will not, but there is no mechanism to test if the table is valid, we
blindly assume that it is.  It is far safer to sort the tables at boot
time than to hope that they are always sorted.

Re: [RFC] 2.5.8 sort kernel tables

[Russell King]

On Fri, Apr 19, 2002 at 01:38:59AM +1000, Keith Owens wrote:
> For example, arm #defines get8_unaligned_check which uses __ex_table.

This doesn't cause your issue though.  Its only used from code built into
the kernel .text segment, never from any other segment.  It isn't a
#define in some random header file that may end up in the .init segment
either.

So this instance doesn't fit your problem.

-- 
Russell King (rmk@arm.linux.org.uk)                The developer of ARM Linux
             http://www.arm.linux.org.uk/personal/aboutme.html

Re: [RFC] 2.5.8 sort kernel tables

[Keith Owens]

On Thu, 18 Apr 2002 16:52:29 +0100, 
Russell King <rmk@arm.linux.org.uk> wrote:
>On Fri, Apr 19, 2002 at 01:38:59AM +1000, Keith Owens wrote:
>> For example, arm #defines get8_unaligned_check which uses __ex_table.
>
>This doesn't cause your issue though.  Its only used from code built into
>the kernel .text segment, never from any other segment.  It isn't a
>#define in some random header file that may end up in the .init segment
>either.

You are missing the point.  There are several macros that use
__ex_table.  Unless it can be guaranteed that no current or future use
of *any* of those macros will be in an __init section then we must not
assume that the exception table is sorted.

Exception table is not the only one that is assumed to be sorted,
get8_unaligned_check is not the only macro that uses __ex_table.  Both
are examples of tables and code where we assume, but do not validate, a
sorted table.

Re: [RFC] 2.5.8 sort kernel tables

[William Lee Irwin III]

On Thu, Apr 18, 2002 at 07:46:26PM +1000, Keith Owens wrote:
> The use of __init and __exit sections breaks the assumption that tables
> such as __ex_table are sorted, it has already broken the dbe table in
> mips on 2.5.  This patch against 2.5.8 adds a generic sort routine and
> sorts the i386 exception table.
> This sorting needs to be extended to several other tables, to all
> architectures, to modutils (insmod loads some of these tables for
> modules) and back ported to 2.4.  Before I spend the rest of the time,
> any objections?

It doesn't have to be an O(n lg(n)) method but could you use something
besides bubblesort? Insertion sort, selection sort, etc. are just as
easy and they don't have the horrific stigma of being "the worst sorting
algorithm ever" etc.


Thanks,
Bill

Re: [RFC] 2.5.8 sort kernel tables

[Kai Henningsen]

wli@holomorphy.com (William Lee Irwin III)  wrote on 18.04.02 in <20020418135931.GU21206@holomorphy.com>:

> On Thu, Apr 18, 2002 at 07:46:26PM +1000, Keith Owens wrote:
> > The use of __init and __exit sections breaks the assumption that tables
> > such as __ex_table are sorted, it has already broken the dbe table in
> > mips on 2.5.  This patch against 2.5.8 adds a generic sort routine and
> > sorts the i386 exception table.
> > This sorting needs to be extended to several other tables, to all
> > architectures, to modutils (insmod loads some of these tables for
> > modules) and back ported to 2.4.  Before I spend the rest of the time,
> > any objections?
>
> It doesn't have to be an O(n lg(n)) method but could you use something
> besides bubblesort? Insertion sort, selection sort, etc. are just as
> easy and they don't have the horrific stigma of being "the worst sorting
> algorithm ever" etc.

Surely the worst (working) sort is randomsort? (Check if sorted. If not,  
pick two entries at random, exchange, retry.)

MfG Kai

Re: [RFC] 2.5.8 sort kernel tables

[William Lee Irwin III]

wli@holomorphy.com (William Lee Irwin III)  wrote on 18.04.02 in <20020418135931.GU21206@holomorphy.com>:
>> It doesn't have to be an O(n lg(n)) method but could you use something
>> besides bubblesort? Insertion sort, selection sort, etc. are just as
>> easy and they don't have the horrific stigma of being "the worst sorting
>> algorithm ever" etc.

On Thu, Apr 18, 2002 at 08:16:00PM +0200, Kai Henningsen wrote:
> Surely the worst (working) sort is randomsort? (Check if sorted. If not,  
> pick two entries at random, exchange, retry.)

Perhaps I should have qualified it with "plausible" or something. The
intent is clear regardless.

Cheers,
Bill

Re: [RFC] 2.5.8 sort kernel tables

[David Weinehall]

On Thu, Apr 18, 2002 at 08:16:00PM +0200, Kai Henningsen wrote:
> wli@holomorphy.com (William Lee Irwin III)  wrote on 18.04.02 in <20020418135931.GU21206@holomorphy.com>:
> 
> > On Thu, Apr 18, 2002 at 07:46:26PM +1000, Keith Owens wrote:
> > > The use of __init and __exit sections breaks the assumption that tables
> > > such as __ex_table are sorted, it has already broken the dbe table in
> > > mips on 2.5.  This patch against 2.5.8 adds a generic sort routine and
> > > sorts the i386 exception table.
> > > This sorting needs to be extended to several other tables, to all
> > > architectures, to modutils (insmod loads some of these tables for
> > > modules) and back ported to 2.4.  Before I spend the rest of the time,
> > > any objections?
> >
> > It doesn't have to be an O(n lg(n)) method but could you use something
> > besides bubblesort? Insertion sort, selection sort, etc. are just as
> > easy and they don't have the horrific stigma of being "the worst sorting
> > algorithm ever" etc.
> 
> Surely the worst (working) sort is randomsort? (Check if sorted. If not,  
> pick two entries at random, exchange, retry.)

I've always been a fan of bit-decay sort.

while (!sorted(data))
	;


/David
  _                                                                 _
 // David Weinehall <tao@acc.umu.se> /> Northern lights wander      \\
//  Maintainer of the v2.0 kernel   //  Dance across the winter sky //
\>  http://www.acc.umu.se/~tao/    </   Full colour fire           </

Re: [RFC] 2.5.8 sort kernel tables

[Oliver Xymoron]

On Thu, 18 Apr 2002, William Lee Irwin III wrote:

> On Thu, Apr 18, 2002 at 07:46:26PM +1000, Keith Owens wrote:
> > The use of __init and __exit sections breaks the assumption that tables
> > such as __ex_table are sorted, it has already broken the dbe table in
> > mips on 2.5.  This patch against 2.5.8 adds a generic sort routine and
> > sorts the i386 exception table.
> > This sorting needs to be extended to several other tables, to all
> > architectures, to modutils (insmod loads some of these tables for
> > modules) and back ported to 2.4.  Before I spend the rest of the time,
> > any objections?
>
> It doesn't have to be an O(n lg(n)) method but could you use something
> besides bubblesort? Insertion sort, selection sort, etc. are just as
> easy and they don't have the horrific stigma of being "the worst sorting
> algorithm ever" etc.

Combsort is a trivial modification of bubblesort that's O(n log(n)).

 http://cs.clackamas.cc.or.us/molatore/cs260Spr01/combsort.htm

Though we should probably just stick a simple qsort in the library
somewhere.

--
 "Love the dolphins," she advised him. "Write by W.A.S.T.E.."

Re: [RFC] 2.5.8 sort kernel tables

[Matt]

On Thu, Apr 18, 2002 at 03:20:17PM -0500, Oliver Xymoron wrote:
> On Thu, 18 Apr 2002, William Lee Irwin III wrote:

>> On Thu, Apr 18, 2002 at 07:46:26PM +1000, Keith Owens wrote:

>>> The use of __init and __exit sections breaks the assumption that
>>> tables such as __ex_table are sorted, it has already broken the
>>> dbe table in mips on 2.5.  This patch against 2.5.8 adds a generic
>>> sort routine and sorts the i386 exception table.  This sorting
>>> needs to be extended to several other tables, to all
>>> architectures, to modutils (insmod loads some of these tables for
>>> modules) and back ported to 2.4.  Before I spend the rest of the
>>> time, any objections?

>> It doesn't have to be an O(n lg(n)) method but could you use
>> something besides bubblesort? Insertion sort, selection sort,
>> etc. are just as easy and they don't have the horrific stigma of
>> being "the worst sorting algorithm ever" etc.

> Combsort is a trivial modification of bubblesort that's O(n log(n)).

>  http://cs.clackamas.cc.or.us/molatore/cs260Spr01/combsort.htm

> Though we should probably just stick a simple qsort in the library
> somewhere.

but isn't qsort's worst case behaviour for an already sorted list? i
cant remember how bad it is but i thought it was like O(n^2) for worst
case, ie just as bad as bubble sort..

	matt

Re: [RFC] 2.5.8 sort kernel tables

[Jamie Lokier]

Oliver Xymoron wrote:
> Combsort is a trivial modification of bubblesort that's O(n log(n)).
> 
>  http://cs.clackamas.cc.or.us/molatore/cs260Spr01/combsort.htm

Cute.  Combsort is very closely related to Shellsort, which is tiny,
fast and old (c.1959), yet its time complexity is still not well
understood:

   http://www.cs.princeton.edu/~rs/shell/shell.c
   http://www.cs.princeton.edu/~rs/shell/

The above paper mentions a variant of Shellsort which uses a "h-bubble"
operation.  Beware!  That does probabilistic sorting, which means
"nearly always sorts, with high probability"!

I think that Combsort is equivalent to that variant of Shellsort, with
larger constant factors in its time complexity (because bubbling is
slower than insertion), and it effectively degrades to Bubblesort in the
event that the probabilistic h-bubble Shellsort fails to sort.

There are a couple of improvements to h-bubble Shellsort mentioned in
the paper which may be faster.

enjoy,
-- Jamie

Re: [RFC] 2.5.8 sort kernel tables

[Jamie Lokier]

Oliver Xymoron wrote:
> Though we should probably just stick a simple qsort in the library
> somewhere.

Since we're comparing sort algorithms, I am quite fond of Heapsort.
Simple, no recursion or stack, and worst case O(n log n).  It's not
especially fast, but the worst case behaviour is nice:

/* This function is a classic in-place heapsort.  It sorts the array
   `nums' of integers, which has `count' elements. */

void my_heapsort (int count, int * nums)
{
	int i;
	for (i = 1; i < count; i++) {
		int j = i, tmp = nums [j];
		while (j > 0 && tmp > nums [(j-1)/2]) {
			nums [j] = nums [(j-1)/2];
			j = (j-1)/2;
		}
		nums [j] = tmp;
	}
	for (i = count - 1; i > 0; i--) {
		int j = 0, k = 1, tmp = nums [i];
		nums [i] = nums [0];
		while (k < i && (tmp < nums [k]
				 || (k+1 < i && tmp < nums [k+1]))) {
			k += (k+1 < i && nums [k+1] > nums [k]);
			nums [j] = nums [k];
			j = k;
			k = 2*j+1;
		}
		nums [j] = tmp;
	}
}

cheers,
-- Jamie

Re: [RFC] 2.5.8 sort kernel tables

[Oliver Xymoron]

On Fri, 19 Apr 2002, Jamie Lokier wrote:

> Oliver Xymoron wrote:
> > Though we should probably just stick a simple qsort in the library
> > somewhere.
>
> Since we're comparing sort algorithms, I am quite fond of Heapsort.
> Simple, no recursion or stack, and worst case O(n log n).  It's not
> especially fast, but the worst case behaviour is nice:
>
> /* This function is a classic in-place heapsort.  It sorts the array
>    `nums' of integers, which has `count' elements. */

Make this generic by passing in compare and swap functions and stick it in
lib. Heapsort is indeed a better candidate for a kernel algorithm than the
simpler qsorts because of the constrained worst case. If I remember
correctly, heapsort performs about as well as combsort in my testing -
within a constant factor of two of qsort's best case.

> void my_heapsort (int count, int * nums)
> {
> 	int i;
> 	for (i = 1; i < count; i++) {
> 		int j = i, tmp = nums [j];
> 		while (j > 0 && tmp > nums [(j-1)/2]) {
> 			nums [j] = nums [(j-1)/2];
> 			j = (j-1)/2;
> 		}
> 		nums [j] = tmp;
> 	}
> 	for (i = count - 1; i > 0; i--) {
> 		int j = 0, k = 1, tmp = nums [i];
> 		nums [i] = nums [0];
> 		while (k < i && (tmp < nums [k]
> 				 || (k+1 < i && tmp < nums [k+1]))) {
> 			k += (k+1 < i && nums [k+1] > nums [k]);
> 			nums [j] = nums [k];
> 			j = k;
> 			k = 2*j+1;
> 		}
> 		nums [j] = tmp;
> 	}
> }
>
> cheers,
> -- Jamie
>

-- 
 "Love the dolphins," she advised him. "Write by W.A.S.T.E.."

Re: [RFC] 2.5.8 sort kernel tables

[Tobias Wollgam]

> On Fri, 19 Apr 2002, Jamie Lokier wrote:
> > Since we're comparing sort algorithms, I am quite fond of Heapsort.
> > Simple, no recursion or stack, and worst case O(n log n).  It's not
> > especially fast, but the worst case behaviour is nice:

There exist a variation of heapsort called clever heapsort  (or 
bottom-up heapsort) that is a little bit faster for big arrays.

I don't know if it will be useful for the kernel. How big are the 
arrays?

Greetings,

	Tobias


-- 
Tobias Wollgam * Softwaredevelopment * Business Unit Information 
MATERNA GmbH Information & Communications
Vosskuhle 37 * 44141 Dortmund  
http://www.materna.de

Re: [RFC] 2.5.8 sort kernel tables

[Andi Kleen]

Paul Mackerras <paulus@samba.org> writes:
> 
> BTW, do you have any valid examples of use of copy_to/from_user or
> get/put_user in an init section?

i386 uses the exception tables to check at startup for the old i386 bug of 
pages not being  write protected when writing from supervisor mode. That 
function is __init.

-Andi

Re: [RFC] 2.5.8 sort kernel tables

[Keith Owens]

On 18 Apr 2002 19:51:43 +0200, 
Andi Kleen <ak@suse.de> wrote:
>Paul Mackerras <paulus@samba.org> writes:
>> 
>> BTW, do you have any valid examples of use of copy_to/from_user or
>> get/put_user in an init section?
>
>i386 uses the exception tables to check at startup for the old i386 bug of 
>pages not being  write protected when writing from supervisor mode. That 
>function is __init.

It used to be, somebody realised that it did not work and took it out
of __init.  With sorted tables it can be moved back.

/*
 * This function cannot be __init, since exceptions don't work in that
 * section.
 */
static int do_test_wp_bit(unsigned long vaddr);

That fixes the symptom, not the cause.  It is better to sort the tables
at boot time than to find each bit of code that might break the tables
and change the code.

RE: [RFC] 2.5.8 sort kernel tables

[Randal, Phil]

This variation on Quicksort seems superior...  Must look at the libc
sources someday to see how it does it...

http://www.neubert.net/Flapaper/9802n.htm

For small arrays, Insertion Sort has the least overhead.

Cheers,

Phil

P.S. A google for quickersort yields loads of interesting references.

---------------------------------------------
Phil Randal
Network Engineer
Herefordshire Council
Hereford, UK 

> -----Original Message-----
> From: Matt [mailto:matt@progsoc.uts.edu.au]
> Sent: 19 April 2002 06:00
> To: linux-kernel@vger.kernel.org
> Subject: Re: [RFC] 2.5.8 sort kernel tables
> 
> 
> On Thu, Apr 18, 2002 at 03:20:17PM -0500, Oliver Xymoron wrote:
> > On Thu, 18 Apr 2002, William Lee Irwin III wrote:
> 
> >> On Thu, Apr 18, 2002 at 07:46:26PM +1000, Keith Owens wrote:
> 
> >>> The use of __init and __exit sections breaks the assumption that
> >>> tables such as __ex_table are sorted, it has already broken the
> >>> dbe table in mips on 2.5.  This patch against 2.5.8 adds a generic
> >>> sort routine and sorts the i386 exception table.  This sorting
> >>> needs to be extended to several other tables, to all
> >>> architectures, to modutils (insmod loads some of these tables for
> >>> modules) and back ported to 2.4.  Before I spend the rest of the
> >>> time, any objections?
> 
> >> It doesn't have to be an O(n lg(n)) method but could you use
> >> something besides bubblesort? Insertion sort, selection sort,
> >> etc. are just as easy and they don't have the horrific stigma of
> >> being "the worst sorting algorithm ever" etc.
> 
> > Combsort is a trivial modification of bubblesort that's O(n log(n)).
> 
> >  http://cs.clackamas.cc.or.us/molatore/cs260Spr01/combsort.htm
> 
> > Though we should probably just stick a simple qsort in the library
> > somewhere.
> 
> but isn't qsort's worst case behaviour for an already sorted list? i
> cant remember how bad it is but i thought it was like O(n^2) for worst
> case, ie just as bad as bubble sort..
> 
> 	matt
> -
> 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/
> 

Re: [RFC] 2.5.8 sort kernel tables

[Keith Owens]

On Fri, 19 Apr 2002 12:38:05 +0100, 
"Randal, Phil" <prandal@herefordshire.gov.uk> wrote:
>This variation on Quicksort seems superior...  Must look at the libc
>sources someday to see how it does it...
>http://www.neubert.net/Flapaper/9802n.htm

It requires extra storage which is unacceptable.  The kernel tables
must be sorted before any code that might take an exception is used.
The sort must be done very early, before kernel memory management is
setup.  In addition, the kernel stack has a limited size.

If the extra data size depends on the number of elements to be sorted
(flashsort1 needs 0.1n extra data) then it cannot be used for this
task.  Sooner or later the extra data size will blow the limited kernel
storage at boot time.  For this task, the sort must use a small and
fixed amount of extra storage.

You realize that we have probably spent more time discussing the sort
algorithm than can be saved by rewriting the sort?  The sort is invoked
once per boot on tables that are almost sorted already, any savings
will be in milliseconds and do not justify the extra programming
effort.  I will use arch/ppc/mm/extable.c::sort_ex_table() instead of
bubble, anything beyond that is a waste of programming time.

Re: [RFC] 2.5.8 sort kernel tables

[Alan Cox]

> It requires extra storage which is unacceptable.  The kernel tables
> must be sorted before any code that might take an exception is used.
> The sort must be done very early, before kernel memory management is
> setup.  In addition, the kernel stack has a limited size.

Why not sort them after linking and before you boot the kernel. This sounds
like a job for libbfd after link. I hadn't realised you planned to do the 
sort every boot

Alan

Re: [RFC] 2.5.8 sort kernel tables

[Keith Owens]

On Sat, 20 Apr 2002 09:50:53 +0100 (BST), 
Alan Cox <alan@lxorguk.ukuu.org.uk> wrote:
>> It requires extra storage which is unacceptable.  The kernel tables
>> must be sorted before any code that might take an exception is used.
>> The sort must be done very early, before kernel memory management is
>> setup.  In addition, the kernel stack has a limited size.
>
>Why not sort them after linking and before you boot the kernel. This sounds
>like a job for libbfd after link. I hadn't realised you planned to do the 
>sort every boot

I considered that option but decided it was easier to sort the tables
at boot time.

Which tables to sort, where they are, the size of each entry, the size
and offset of the key in each table are all arch specific.  The top
level makefile would have to make tmp_vmlinux then ask each arch
Makefile to do whatever it needed to convert tmp_vmlinux to vmlinux,
using a target specific program.

IA64 used to sort its unwind table at boot (ld was buggy at the time)
and the overhead was not noticable.  PPC already sorts at boot time, I
doubt that they notice it.  Either option would work but IMHO sorting
at boot time is easier to code and maintain.