[PATCH 0/8] lib/sort: Add generic sort to lib/

[PATCH 0/8] lib/sort: Add generic sort to lib/

[Matt Mackall]

This patch series introduces a generic heapsort function, sort(), in
lib/. It also replaces the uses of the recently introduced qsort()
code from glibc and then removes that code. A few other open-coded
sort routines are updated as well. I plan to clean up some other
effervescent sort routines in the near future.

[PATCH 1/8] lib/sort: Heapsort implementation of sort()

[Matt Mackall]

This patch adds a generic array sorting library routine. This is meant
to replace qsort, which has two problem areas for kernel use.

The first issue is quadratic worst-case performance. While quicksort
worst-case datasets are rarely encountered in normal scenarios, it is
in fact quite easy to construct worst cases for almost all quicksort
algorithms given source or access to an element comparison callback.
This could allow attackers to cause sorts that would otherwise take
less than a millisecond to take seconds and sorts that should take
less than a second to take weeks or months. Fixing this problem
requires randomizing pivot selection with a secure random number
generator, which is rather expensive.

The second is that quicksort's recursion tracking requires either
nontrivial amounts of stack space or dynamic memory allocation and out
of memory error handling.

By comparison, heapsort has both O(n log n) average and worst-case
performance and practically no extra storage requirements. This
version runs within 70-90% of the average performance of optimized
quicksort so it should be an acceptable replacement wherever quicksort
would be used in the kernel.

Note that this function has an extra parameter for passing in an
optimized swapping function. This is worth 10% or more over the
typical byte-by-byte exchange functions.

Benchmarks:

qsort:     glibc variant            1189 bytes (+ 256/1024 stack)
qsort_3f:  my simplified variant     459 bytes (+ 256/1024 stack)
heapsort:  the version below         346 bytes
shellsort: an optimized shellsort    196 bytes

                         P4 1.8GHz        Opteron 1.4GHz (32-bit)
size   algorithm      cycles relative        cycles relative
100:
           qsort:      38682 100.00%	      27631 100.00%
        qsort_3f:      36277 106.63%	      22406 123.32%
        heapsort:      43574  88.77%	      30301  91.19%
       shellsort:      39087  98.97%	      25139 109.91%
200:									    
           qsort:      86468 100.00%	      61148 100.00%
        qsort_3f:      78918 109.57%	      48959 124.90%
        heapsort:      98040  88.20%	      68235  89.61%
       shellsort:      95688  90.36%	      62279  98.18%
400:									    
           qsort:     187720 100.00%	     131313 100.00%
        qsort_3f:     174905 107.33%	     107954 121.64%
        heapsort:     223896  83.84%	     154241  85.13%
       shellsort:     223037  84.17%	     148990  88.14%
800:									    
           qsort:     407060 100.00%	     287460 100.00%
        qsort_3f:     385106 105.70%	     239131 120.21%
        heapsort:     484662  83.99%	     340099  84.52%
       shellsort:     537110  75.79%	     354755  81.03%
1600:									    
           qsort:     879596 100.00%	     621331 100.00%
        qsort_3f:     861568 102.09%	     522013 119.03%
        heapsort:    1079750  81.46%	     746677  83.21%
       shellsort:    1234243  71.27%	     820782  75.70%
3200:									    
           qsort:    1903902 100.00%	    1342126 100.00%
        qsort_3f:    1908816  99.74%	    1131496 118.62%
        heapsort:    2515493  75.69%	    1630333  82.32%
       shellsort:    2985339  63.78%	    1964794  68.31%
6400:									    
           qsort:    4046370 100.00%	    2909215 100.00%
        qsort_3f:    4164468  97.16%	    2468393 117.86%
        heapsort:    5150659  78.56%	    3533585  82.33%
       shellsort:    6650225  60.85%	    4429849  65.67%
12800:									    
           qsort:    8729730 100.00%	    6185097 100.00%
        qsort_3f:    8776885  99.46%	    5288826 116.95%
        heapsort:   11064224  78.90%	    7603061  81.35%
       shellsort:   15487905  56.36%	   10305163  60.02%
25600:									    
           qsort:   18357770 100.00%	   13172205 100.00%
        qsort_3f:   18687842  98.23%	   11337115 116.19%
        heapsort:   24121241  76.11%	   16612122  79.29%
       shellsort:   35552814  51.64%	   24106987  54.64%
51200:									    
           qsort:   38658883 100.00%	   28008505 100.00%
        qsort_3f:   39498463  97.87%	   24339675 115.07%
        heapsort:   50553552  76.47%	   37013828  75.67%
       shellsort:   82602416  46.80%	   56201889  49.84%
102400:									    
           qsort:   81197794 100.00%	   58918933 100.00%
        qsort_3f:   84257930  96.37%	   51986219 113.34%
        heapsort:  110540577  73.46%	   81419675  72.36%
       shellsort:  191303132  42.44%	  129786472  45.40%


Signed-off-by: Matt Mackall <mpm@selenic.com>

Index: mm2/lib/Makefile
===================================================================
--- mm2.orig/lib/Makefile	2005-01-30 21:26:28.000000000 -0800
+++ mm2/lib/Makefile	2005-01-30 22:37:49.000000000 -0800
@@ -6,7 +6,7 @@
 	 bust_spinlocks.o rbtree.o radix-tree.o dump_stack.o \
 	 kobject.o kref.o idr.o div64.o parser.o int_sqrt.o \
 	 bitmap.o extable.o kobject_uevent.o prio_tree.o \
-	 sha1.o halfmd4.o
+	 sha1.o halfmd4.o sort.o
 
 ifeq ($(CONFIG_DEBUG_KOBJECT),y)
 CFLAGS_kobject.o += -DDEBUG
Index: mm2/include/linux/sort.h
===================================================================
--- /dev/null	1970-01-01 00:00:00.000000000 +0000
+++ mm2/include/linux/sort.h	2005-01-30 22:06:37.000000000 -0800
@@ -0,0 +1,8 @@
+#ifndef _LINUX_SORT_H
+#define _LINUX_SORT_H
+
+void sort(void *base, size_t num, size_t size,
+	  int (*cmp)(const void *, const void *),
+	  void (*swap)(void *, void *, int));
+
+#endif
Index: mm2/lib/sort.c
===================================================================
--- /dev/null	1970-01-01 00:00:00.000000000 +0000
+++ mm2/lib/sort.c	2005-01-30 22:37:28.000000000 -0800
@@ -0,0 +1,121 @@
+/*
+ * A fast, small, non-recursive O(nlog n) sort for the Linux kernel
+ *
+ * Jan 23 2005  Matt Mackall <mpm@selenic.com>
+ */
+
+#include <linux/kernel.h>
+#include <linux/module.h>
+
+void u32_swap(void *a, void *b, int size)
+{
+	u32 t = *(u32 *)a;
+	*(u32 *)a = *(u32 *)b;
+	*(u32 *)b = t;
+}
+
+void generic_swap(void *a, void *b, int size)
+{
+	char t;
+
+	do {
+		t = *(char *)a;
+		*(char *)a++ = *(char *)b;
+		*(char *)b++ = t;
+	} while (--size > 0);
+}
+
+/*
+ * sort - sort an array of elements
+ * @base: pointer to data to sort
+ * @num: number of elements
+ * @size: size of each element
+ * @cmp: pointer to comparison function
+ * @swap: pointer to swap function or NULL
+ *
+ * This function does a heapsort on the given array. You may provide a
+ * swap function optimized to your element type.
+ *
+ * Sorting time is O(n log n) both on average and worst-case. While
+ * qsort is about 20% faster on average, it suffers from exploitable
+ * O(n*n) worst-case behavior and extra memory requirements that make
+ * it less suitable for kernel use.
+ */
+
+void sort(void *base, size_t num, size_t size,
+	  int (*cmp)(const void *, const void *),
+	  void (*swap)(void *, void *, int size))
+{
+	/* pre-scale counters for performance */
+	int i = (num/2 - 1) * size, n = num * size, c, r;
+
+	if (!swap)
+		swap = (size == 4 ? u32_swap : generic_swap);
+
+	/* heapify */
+	for ( ; i >= 0; i -= size) {
+		for (r = i; r * 2 < n; r  = c) {
+			c = r * 2;
+			if (c < n - size && cmp(base + c, base + c + size) < 0)
+				c += size;
+			if (cmp(base + r, base + c) >= 0)
+				break;
+			swap(base + r, base + c, size);
+		}
+	}
+
+	/* sort */
+	for (i = n - size; i >= 0; i -= size) {
+		swap(base, base + i, size);
+		for (r = 0; r * 2 < i; r = c) {
+			c = r * 2;
+			if (c < i - size && cmp(base + c, base + c + size) < 0)
+				c += size;
+			if (cmp(base + r, base + c) >= 0)
+				break;
+			swap(base + r, base + c, size);
+		}
+	}
+}
+
+EXPORT_SYMBOL_GPL(sort);
+
+MODULE_LICENSE("GPL");
+
+#if 1
+/* a simple boot-time regression test */
+
+int cmpint(const void *a, const void *b)
+{
+	return *(int *)a - *(int *)b;
+}
+
+static int sort_test(void)
+{
+	int *a, i, r = 0;
+
+	a = kmalloc(1000 * sizeof(int), GFP_KERNEL);
+	BUG_ON(!a);
+
+	printk("testing sort()\n");
+
+	for (i = 0; i < 1000; i++) {
+		r = (r * 725861) % 6599;
+		a[i] = r;
+	}
+
+	sort(a, 1000, sizeof(int), cmpint, 0);
+
+	for (i = 0; i < 999; i++)
+		if (a[i] > a[i+1]) {
+			printk("sort() failed!\n");
+			break;
+		}
+
+	kfree(a);
+
+	return 0;
+}
+
+module_init(sort_test);
+#endif

[PATCH 2/8] lib/sort: Replace qsort in XFS

[Matt Mackall]

Point XFS qsort at lib/sort in a way that makes it happy.

Signed-off-by: Matt Mackall <mpm@selenic.com>

Index: mm2/fs/xfs/linux-2.6/xfs_linux.h
===================================================================
--- mm2.orig/fs/xfs/linux-2.6/xfs_linux.h	2005-01-30 14:22:38.000000000 -0800
+++ mm2/fs/xfs/linux-2.6/xfs_linux.h	2005-01-30 20:15:45.000000000 -0800
@@ -87,6 +87,7 @@
 #include <linux/list.h>
 #include <linux/proc_fs.h>
 #include <linux/version.h>
+#include <linux/sort.h>
 
 #include <asm/page.h>
 #include <asm/div64.h>
@@ -367,4 +368,12 @@
 	return(x * y);
 }
 
+
+#define qsort xfs_sort
+static inline void xfs_sort(void *a, size_t n, size_t s,
+			int (*cmp)(const void *,const void *))
+{
+	sort(a, n, s, cmp, 0);
+}
+
 #endif /* __XFS_LINUX__ */
Index: mm2/fs/xfs/Kconfig
===================================================================
--- mm2.orig/fs/xfs/Kconfig	2005-01-30 14:22:38.000000000 -0800
+++ mm2/fs/xfs/Kconfig	2005-01-30 20:34:54.000000000 -0800
@@ -2,7 +2,6 @@
 
 config XFS_FS
 	tristate "XFS filesystem support"
-	select QSORT
 	help
 	  XFS is a high performance journaling filesystem which originated
 	  on the SGI IRIX platform.  It is completely multi-threaded, can

[PATCH 3/8] lib/sort: Replace qsort in NFS ACL code

[Matt Mackall]

Switch NFS ACLs to lib/sort

Index: mm2/fs/nfsacl.c
===================================================================
--- mm2.orig/fs/nfsacl.c	2005-01-30 21:26:27.000000000 -0800
+++ mm2/fs/nfsacl.c	2005-01-30 22:06:43.000000000 -0800
@@ -25,6 +25,7 @@
 #include <linux/sunrpc/xdr.h>
 #include <linux/nfsacl.h>
 #include <linux/nfs3.h>
+#include <linux/sort.h>
 
 MODULE_LICENSE("GPL");
 
@@ -163,9 +164,10 @@
 	return 0;
 }
 
-static int
-cmp_acl_entry(const struct posix_acl_entry *a, const struct posix_acl_entry *b)
+static int cmp_acl_entry(const void *x, const void *y)
 {
+	const struct posix_acl_entry *a = x, *b = y;
+
 	if (a->e_tag != b->e_tag)
 		return a->e_tag - b->e_tag;
 	else if (a->e_id > b->e_id)
@@ -188,8 +190,8 @@
 	if (!acl)
 		return 0;
 
-	qsort(acl->a_entries, acl->a_count, sizeof(struct posix_acl_entry),
-	      (int(*)(const void *,const void *))cmp_acl_entry);
+	sort(acl->a_entries, acl->a_count, sizeof(struct posix_acl_entry),
+	     cmp_acl_entry, 0);
 
 	/* Clear undefined identifier fields and find the ACL_GROUP_OBJ
 	   and ACL_MASK entries. */
Index: mm2/fs/Kconfig
===================================================================
--- mm2.orig/fs/Kconfig	2005-01-30 21:32:26.000000000 -0800
+++ mm2/fs/Kconfig	2005-01-30 22:07:10.000000000 -0800
@@ -1428,7 +1428,6 @@
 config NFS_ACL
 	bool "NFS_ACL protocol extension"
 	depends on NFS_V3
-	select QSORT
 	select FS_POSIX_ACL
 	help
 	  Implement the NFS_ACL protocol extension for manipulating POSIX
@@ -1513,7 +1512,6 @@
 config NFSD_ACL
 	bool "NFS_ACL protocol extension"
 	depends on NFSD_V3
-	select QSORT
 	help
 	  Implement the NFS_ACL protocol extension for manipulating POSIX
 	  Access Control Lists on exported file systems.  The clients must

[PATCH 4/8] lib/sort: Kill qsort()

[Matt Mackall]

Remove qsort() before anyone gets too attached to it.

Signed-off-by: Matt Mackall <mpm@selenic.com>

Index: mm2/lib/qsort.c
===================================================================
--- mm2.orig/lib/qsort.c	2005-01-30 20:33:19.000000000 -0800
+++ /dev/null	1970-01-01 00:00:00.000000000 +0000
@@ -1,249 +0,0 @@
-/* Copyright (C) 1991, 1992, 1996, 1997, 1999 Free Software Foundation, Inc.
-   This file is part of the GNU C Library.
-   Written by Douglas C. Schmidt (schmidt@ics.uci.edu).
-
-   The GNU C Library is free software; you can redistribute it and/or
-   modify it under the terms of the GNU Lesser General Public
-   License as published by the Free Software Foundation; either
-   version 2.1 of the License, or (at your option) any later version.
-
-   The GNU C Library is distributed in the hope that it will be useful,
-   but WITHOUT ANY WARRANTY; without even the implied warranty of
-   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
-   Lesser General Public License for more details.
-
-   You should have received a copy of the GNU Lesser General Public
-   License along with the GNU C Library; if not, write to the Free
-   Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
-   02111-1307 USA.  */
-
-/* If you consider tuning this algorithm, you should consult first:
-   Engineering a sort function; Jon Bentley and M. Douglas McIlroy;
-   Software - Practice and Experience; Vol. 23 (11), 1249-1265, 1993.  */
-
-# include <linux/module.h>
-# include <linux/slab.h>
-# include <linux/string.h>
-
-MODULE_LICENSE("GPL");
-
-/* Byte-wise swap two items of size SIZE. */
-#define SWAP(a, b, size)						      \
-  do									      \
-    {									      \
-      register size_t __size = (size);					      \
-      register char *__a = (a), *__b = (b);				      \
-      do								      \
-	{								      \
-	  char __tmp = *__a;						      \
-	  *__a++ = *__b;						      \
-	  *__b++ = __tmp;						      \
-	} while (--__size > 0);						      \
-    } while (0)
-
-/* Discontinue quicksort algorithm when partition gets below this size.
-   This particular magic number was chosen to work best on a Sun 4/260. */
-#define MAX_THRESH 4
-
-/* Stack node declarations used to store unfulfilled partition obligations. */
-typedef struct
-  {
-    char *lo;
-    char *hi;
-  } stack_node;
-
-/* The next 5 #defines implement a very fast in-line stack abstraction. */
-/* The stack needs log (total_elements) entries (we could even subtract
-   log(MAX_THRESH)).  Since total_elements has type size_t, we get as
-   upper bound for log (total_elements):
-   bits per byte (CHAR_BIT) * sizeof(size_t).  */
-#define CHAR_BIT 8
-#define STACK_SIZE	(CHAR_BIT * sizeof(size_t))
-#define PUSH(low, high)	((void) ((top->lo = (low)), (top->hi = (high)), ++top))
-#define	POP(low, high)	((void) (--top, (low = top->lo), (high = top->hi)))
-#define	STACK_NOT_EMPTY	(stack < top)
-
-
-/* Order size using quicksort.  This implementation incorporates
-   four optimizations discussed in Sedgewick:
-
-   1. Non-recursive, using an explicit stack of pointer that store the
-      next array partition to sort.  To save time, this maximum amount
-      of space required to store an array of SIZE_MAX is allocated on the
-      stack.  Assuming a 32-bit (64 bit) integer for size_t, this needs
-      only 32 * sizeof(stack_node) == 256 bytes (for 64 bit: 1024 bytes).
-      Pretty cheap, actually.
-
-   2. Chose the pivot element using a median-of-three decision tree.
-      This reduces the probability of selecting a bad pivot value and
-      eliminates certain extraneous comparisons.
-
-   3. Only quicksorts TOTAL_ELEMS / MAX_THRESH partitions, leaving
-      insertion sort to order the MAX_THRESH items within each partition.
-      This is a big win, since insertion sort is faster for small, mostly
-      sorted array segments.
-
-   4. The larger of the two sub-partitions is always pushed onto the
-      stack first, with the algorithm then concentrating on the
-      smaller partition.  This *guarantees* no more than log (total_elems)
-      stack size is needed (actually O(1) in this case)!  */
-
-void
-qsort(void *const pbase, size_t total_elems, size_t size,
-      int(*cmp)(const void *,const void *))
-{
-  register char *base_ptr = (char *) pbase;
-
-  const size_t max_thresh = MAX_THRESH * size;
-
-  if (total_elems == 0)
-    /* Avoid lossage with unsigned arithmetic below.  */
-    return;
-
-  if (total_elems > MAX_THRESH)
-    {
-      char *lo = base_ptr;
-      char *hi = &lo[size * (total_elems - 1)];
-      stack_node stack[STACK_SIZE];
-      stack_node *top = stack + 1;
-
-      while (STACK_NOT_EMPTY)
-        {
-          char *left_ptr;
-          char *right_ptr;
-
-	  /* Select median value from among LO, MID, and HI. Rearrange
-	     LO and HI so the three values are sorted. This lowers the
-	     probability of picking a pathological pivot value and
-	     skips a comparison for both the LEFT_PTR and RIGHT_PTR in
-	     the while loops. */
-
-	  char *mid = lo + size * ((hi - lo) / size >> 1);
-
-	  if ((*cmp) ((void *) mid, (void *) lo) < 0)
-	    SWAP (mid, lo, size);
-	  if ((*cmp) ((void *) hi, (void *) mid) < 0)
-	    SWAP (mid, hi, size);
-	  else
-	    goto jump_over;
-	  if ((*cmp) ((void *) mid, (void *) lo) < 0)
-	    SWAP (mid, lo, size);
-	jump_over:;
-
-	  left_ptr  = lo + size;
-	  right_ptr = hi - size;
-
-	  /* Here's the famous ``collapse the walls'' section of quicksort.
-	     Gotta like those tight inner loops!  They are the main reason
-	     that this algorithm runs much faster than others. */
-	  do
-	    {
-	      while ((*cmp) ((void *) left_ptr, (void *) mid) < 0)
-		left_ptr += size;
-
-	      while ((*cmp) ((void *) mid, (void *) right_ptr) < 0)
-		right_ptr -= size;
-
-	      if (left_ptr < right_ptr)
-		{
-		  SWAP (left_ptr, right_ptr, size);
-		  if (mid == left_ptr)
-		    mid = right_ptr;
-		  else if (mid == right_ptr)
-		    mid = left_ptr;
-		  left_ptr += size;
-		  right_ptr -= size;
-		}
-	      else if (left_ptr == right_ptr)
-		{
-		  left_ptr += size;
-		  right_ptr -= size;
-		  break;
-		}
-	    }
-	  while (left_ptr <= right_ptr);
-
-          /* Set up pointers for next iteration.  First determine whether
-             left and right partitions are below the threshold size.  If so,
-             ignore one or both.  Otherwise, push the larger partition's
-             bounds on the stack and continue sorting the smaller one. */
-
-          if ((size_t) (right_ptr - lo) <= max_thresh)
-            {
-              if ((size_t) (hi - left_ptr) <= max_thresh)
-		/* Ignore both small partitions. */
-                POP (lo, hi);
-              else
-		/* Ignore small left partition. */
-                lo = left_ptr;
-            }
-          else if ((size_t) (hi - left_ptr) <= max_thresh)
-	    /* Ignore small right partition. */
-            hi = right_ptr;
-          else if ((right_ptr - lo) > (hi - left_ptr))
-            {
-	      /* Push larger left partition indices. */
-              PUSH (lo, right_ptr);
-              lo = left_ptr;
-            }
-          else
-            {
-	      /* Push larger right partition indices. */
-              PUSH (left_ptr, hi);
-              hi = right_ptr;
-            }
-        }
-    }
-
-  /* Once the BASE_PTR array is partially sorted by quicksort the rest
-     is completely sorted using insertion sort, since this is efficient
-     for partitions below MAX_THRESH size. BASE_PTR points to the beginning
-     of the array to sort, and END_PTR points at the very last element in
-     the array (*not* one beyond it!). */
-
-  {
-    char *end_ptr = &base_ptr[size * (total_elems - 1)];
-    char *tmp_ptr = base_ptr;
-    char *thresh = min(end_ptr, base_ptr + max_thresh);
-    register char *run_ptr;
-
-    /* Find smallest element in first threshold and place it at the
-       array's beginning.  This is the smallest array element,
-       and the operation speeds up insertion sort's inner loop. */
-
-    for (run_ptr = tmp_ptr + size; run_ptr <= thresh; run_ptr += size)
-      if ((*cmp) ((void *) run_ptr, (void *) tmp_ptr) < 0)
-        tmp_ptr = run_ptr;
-
-    if (tmp_ptr != base_ptr)
-      SWAP (tmp_ptr, base_ptr, size);
-
-    /* Insertion sort, running from left-hand-side up to right-hand-side.  */
-
-    run_ptr = base_ptr + size;
-    while ((run_ptr += size) <= end_ptr)
-      {
-	tmp_ptr = run_ptr - size;
-	while ((*cmp) ((void *) run_ptr, (void *) tmp_ptr) < 0)
-	  tmp_ptr -= size;
-
-	tmp_ptr += size;
-        if (tmp_ptr != run_ptr)
-          {
-            char *trav;
-
-	    trav = run_ptr + size;
-	    while (--trav >= run_ptr)
-              {
-                char c = *trav;
-                char *hi, *lo;
-
-                for (hi = lo = trav; (lo -= size) >= tmp_ptr; hi = lo)
-                  *hi = *lo;
-                *hi = c;
-              }
-          }
-      }
-  }
-}
-EXPORT_SYMBOL(qsort);
Index: mm2/lib/Kconfig
===================================================================
--- mm2.orig/lib/Kconfig	2005-01-30 20:33:19.000000000 -0800
+++ mm2/lib/Kconfig	2005-01-30 20:36:12.000000000 -0800
@@ -30,9 +30,6 @@
 	  require M here.  See Castagnoli93.
 	  Module will be libcrc32c.
 
-config QSORT
-	bool "Quick Sort"
-
 #
 # compression support is select'ed if needed
 #
Index: mm2/lib/Makefile
===================================================================
--- mm2.orig/lib/Makefile	2005-01-30 20:33:19.000000000 -0800
+++ mm2/lib/Makefile	2005-01-30 20:36:12.000000000 -0800
@@ -26,7 +26,6 @@
 obj-$(CONFIG_CRC32)	+= crc32.o
 obj-$(CONFIG_LIBCRC32C)	+= libcrc32c.o
 obj-$(CONFIG_GENERIC_IOMAP) += iomap.o
-obj-$(CONFIG_QSORT)	+= qsort.o
 
 obj-$(CONFIG_ZLIB_INFLATE) += zlib_inflate/
 obj-$(CONFIG_ZLIB_DEFLATE) += zlib_deflate/

[PATCH 5/8] lib/sort: Replace open-coded O(pids**2) bubblesort in cpusets

[Matt Mackall]

Eep. cpuset uses bubble sort on a data set that's potentially O(#
processes). Switch to lib/sort.

Signed-off-by: Matt Mackall <mpm@selenic.com>

Index: tq/kernel/cpuset.c
===================================================================
--- tq.orig/kernel/cpuset.c	2005-01-29 16:13:53.000000000 -0800
+++ tq/kernel/cpuset.c	2005-01-30 13:26:48.000000000 -0800
@@ -47,6 +47,7 @@
 #include <linux/string.h>
 #include <linux/time.h>
 #include <linux/backing-dev.h>
+#include <linux/sort.h>
 
 #include <asm/uaccess.h>
 #include <asm/atomic.h>
@@ -1055,21 +1056,9 @@
 	return n;
 }
 
-/*
- * In place bubble sort pidarray of npids pid_t's.
- */
-static inline void pid_array_sort(pid_t *pidarray, int npids)
+static int cmppid(const void *a, const void *b)
 {
-	int i, j;
-
-	for (i = 0; i < npids - 1; i++) {
-		for (j = 0; j < npids - 1 - i; j++)
-			if (pidarray[j + 1] < pidarray[j]) {
-				pid_t tmp = pidarray[j];
-				pidarray[j] = pidarray[j + 1];
-				pidarray[j + 1] = tmp;
-			}
-	}
+	return *(pid_t *)a - *(pid_t *)b;
 }
 
 /*
@@ -1114,7 +1103,7 @@
 		goto err1;
 
 	npids = pid_array_load(pidarray, npids, cs);
-	pid_array_sort(pidarray, npids);
+	sort(pidarray, npids, sizeof(pid_t), cmppid, 0);
 
 	/* Call pid_array_to_buf() twice, first just to get bufsz */
 	ctr->bufsz = pid_array_to_buf(&c, sizeof(c), pidarray, npids) + 1;

[PATCH 6/8] lib/sort: Replace insertion sort in exception tables

[Matt Mackall]

Replace exception table insertion sort with lib/sort

Signed-off-by: Matt Mackall <mpm@selenic.com>

Index: mm2/lib/extable.c
===================================================================
--- mm2.orig/lib/extable.c	2005-01-30 20:33:18.000000000 -0800
+++ mm2/lib/extable.c	2005-01-30 20:40:53.000000000 -0800
@@ -13,6 +13,7 @@
 #include <linux/config.h>
 #include <linux/module.h>
 #include <linux/init.h>
+#include <linux/sort.h>
 #include <asm/uaccess.h>
 
 extern struct exception_table_entry __start___ex_table[];
@@ -25,26 +26,17 @@
  * This is used both for the kernel exception table and for
  * the exception tables of modules that get loaded.
  */
+static int cmp_ex(const void *a, const void *b)
+{
+	const struct exception_table_entry *x = a, *y = b;
+	return x->insn - y->insn;
+}
+
 void sort_extable(struct exception_table_entry *start,
 		  struct exception_table_entry *finish)
 {
-	struct exception_table_entry el, *p, *q;
-
-	/* insertion sort */
-	for (p = start + 1; p < finish; ++p) {
-		/* start .. p-1 is sorted */
-		if (p[0].insn < p[-1].insn) {
-			/* move element p down to its right place */
-			el = *p;
-			q = p;
-			do {
-				/* el comes before q[-1], move q[-1] up one */
-				q[0] = q[-1];
-				--q;
-			} while (q > start && el.insn < q[-1].insn);
-			*q = el;
-		}
-	}
+	sort(start, finish - start, sizeof(struct exception_table_entry),
+	     cmp_ex, 0);
 }
 #endif
 

[PATCH 7/8] lib/sort: Replace insertion sort in IA64 exception tables

[Matt Mackall]

Switch IA64 exception tables to lib/sort.

Signed-off-by: Matt Mackall <mpm@selenic.com>

Index: tq/arch/ia64/mm/extable.c
===================================================================
--- tq.orig/arch/ia64/mm/extable.c	2005-01-25 09:20:53.000000000 -0800
+++ tq/arch/ia64/mm/extable.c	2005-01-30 13:56:18.000000000 -0800
@@ -6,29 +6,24 @@
  */
 
 #include <linux/config.h>
+#include <linux/sort.h>
 
 #include <asm/uaccess.h>
 #include <asm/module.h>
 
-static inline int
-compare_entries (struct exception_table_entry *l, struct exception_table_entry *r)
+static int cmp_ex(const void *a, const void *b)
 {
+	const struct exception_table_entry *l = a, *r = b;
 	u64 lip = (u64) &l->addr + l->addr;
 	u64 rip = (u64) &r->addr + r->addr;
 
-	if (lip < rip)
-		return -1;
-	if (lip == rip)
-		return 0;
-	else
-		return 1;
+	return lip - rip;
 }
 
-static inline void
-swap_entries (struct exception_table_entry *l, struct exception_table_entry *r)
+static void swap_ex(void *a, void *b)
 {
+	struct exception_table_entry *l = a, *r = b, tmp;
 	u64 delta = (u64) r - (u64) l;
-	struct exception_table_entry tmp;
 
 	tmp = *l;
 	l->addr = r->addr + delta;
@@ -38,23 +33,20 @@
 }
 
 /*
- * Sort the exception table.  It's usually already sorted, but there may be unordered
- * entries due to multiple text sections (such as the .init text section).  Note that the
- * exception-table-entries contain location-relative addresses, which requires a bit of
- * care during sorting to avoid overflows in the offset members (e.g., it would not be
- * safe to make a temporary copy of an exception-table entry on the stack, because the
- * stack may be more than 2GB away from the exception-table).
+ * Sort the exception table. It's usually already sorted, but there
+ * may be unordered entries due to multiple text sections (such as the
+ * .init text section). Note that the exception-table-entries contain
+ * location-relative addresses, which requires a bit of care during
+ * sorting to avoid overflows in the offset members (e.g., it would
+ * not be safe to make a temporary copy of an exception-table entry on
+ * the stack, because the stack may be more than 2GB away from the
+ * exception-table).
  */
-void
-sort_extable (struct exception_table_entry *start, struct exception_table_entry *finish)
+void sort_extable (struct exception_table_entry *start,
+		   struct exception_table_entry *finish)
 {
-	struct exception_table_entry *p, *q;
-
- 	/* insertion sort */
-	for (p = start + 1; p < finish; ++p)
-		/* start .. p-1 is sorted; push p down to it's proper place */
-		for (q = p; q > start && compare_entries(&q[0], &q[-1]) < 0; --q)
-			swap_entries(&q[0], &q[-1]);
+	sort(start, finish - start, sizeof(struct exception_table_entry),
+	     cmp_ex, swap_ex);
 }
 
 const struct exception_table_entry *

[PATCH 8/8] lib/sort: Use generic sort on x86_64

[Matt Mackall]

x86_64 wasn't doing anything special in its sort_extable. Use the
generic lib/extable sort.

Signed-off-by: Matt Mackall <mpm@selenic.com>

Index: tq/arch/x86_64/mm/extable.c
===================================================================
--- tq.orig/arch/x86_64/mm/extable.c	2004-04-03 19:38:16.000000000 -0800
+++ tq/arch/x86_64/mm/extable.c	2005-01-30 14:01:16.000000000 -0800
@@ -33,26 +33,3 @@
         }
         return NULL;
 }
-
-/* When an exception handler is in an non standard section (like __init)
-   the fixup table can end up unordered. Fix that here. */
-void sort_extable(struct exception_table_entry *start,
-		  struct exception_table_entry *finish)
-{
-	struct exception_table_entry *e;
-	int change;
-
-	/* The input is near completely presorted, which makes bubble sort the
-	   best (and simplest) sort algorithm. */
-	do {
-		change = 0;
-		for (e = start+1; e < finish; e++) {
-			if (e->insn < e[-1].insn) {
-				struct exception_table_entry tmp = e[-1];
-				e[-1] = e[0];
-				e[0] = tmp;
-				change = 1;
-			}
-		}
-	} while (change != 0);
-}
Index: tq/include/asm-x86_64/uaccess.h
===================================================================
--- tq.orig/include/asm-x86_64/uaccess.h	2005-01-25 09:30:00.000000000 -0800
+++ tq/include/asm-x86_64/uaccess.h	2005-01-30 14:02:17.000000000 -0800
@@ -73,6 +73,7 @@
 	unsigned long insn, fixup;
 };
 
+#define ARCH_HAS_SEARCH_EXTABLE
 
 /*
  * These are the main single-value transfer routines.  They automatically

Re: [PATCH 5/8] lib/sort: Replace open-coded O(pids**2) bubblesort in cpusets

[Paul Jackson]

Matt wrote:
> Eep. cpuset uses bubble sort on a data set that's potentially O(#
> processes). Switch to lib/sort.
> 
> Signed-off-by: Matt Mackall <mpm@selenic.com>

Acked-by: Paul Jackson <pj@sgi.com>

Ack'ing in principle -- the lib/sort patch itself still hasn't
arrived in my email inbox, so I can only trust that it does what
one would expect.  Assuming it does, then this cpuset patch seems
fine.

Thanks, Matt.

-- 
                  I won't rest till it's the best ...
                  Programmer, Linux Scalability
                  Paul Jackson <pj@sgi.com> 1.650.933.1373, 1.925.600.0401

Re: [PATCH 2/8] lib/sort: Replace qsort in XFS

[Chris Wedgwood]

On Mon, Jan 31, 2005 at 01:34:59AM -0600, Matt Mackall wrote:

> +#define qsort xfs_sort
> +static inline void xfs_sort(void *a, size_t n, size_t s,
> +			int (*cmp)(const void *,const void *))
> +{
> +	sort(a, n, s, cmp, 0);
> +}
> +

why not just:

#define qsort(a, n, s, cmp)	sort(a, n, s, cmp, NULL)



On Mon, Jan 31, 2005 at 01:35:00AM -0600, Matt Mackall wrote:

> Switch NFS ACLs to lib/sort

> +	sort(acl->a_entries, acl->a_count, sizeof(struct posix_acl_entry),
> +	     cmp_acl_entry, 0);

There was a thread about stlye and I though the concensurs for null
pointers weas to use NULL and not 0?



On Mon, Jan 31, 2005 at 01:35:00AM -0600, Matt Mackall wrote:

> Eep. cpuset uses bubble sort on a data set that's potentially O(#
> processes). Switch to lib/sort.

> +	sort(pidarray, npids, sizeof(pid_t), cmppid, 0);

and there?



On Mon, Jan 31, 2005 at 01:35:00AM -0600, Matt Mackall wrote:

> Replace exception table insertion sort with lib/sort

> +	sort(start, finish - start, sizeof(struct exception_table_entry),
> +	     cmp_ex, 0);

and there?

Re: [PATCH 2/8] lib/sort: Replace qsort in XFS

[Randy.Dunlap]

Chris Wedgwood wrote:
> On Mon, Jan 31, 2005 at 01:34:59AM -0600, Matt Mackall wrote:
> 
> 
>>+#define qsort xfs_sort
>>+static inline void xfs_sort(void *a, size_t n, size_t s,
>>+			int (*cmp)(const void *,const void *))
>>+{
>>+	sort(a, n, s, cmp, 0);
>>+}
>>+
> 
> 
> why not just:
> 
> #define qsort(a, n, s, cmp)	sort(a, n, s, cmp, NULL)
> 
> 
> 
> On Mon, Jan 31, 2005 at 01:35:00AM -0600, Matt Mackall wrote:
> 
> 
>>Switch NFS ACLs to lib/sort
> 
> 
>>+	sort(acl->a_entries, acl->a_count, sizeof(struct posix_acl_entry),
>>+	     cmp_acl_entry, 0);
> 
> 
> There was a thread about stlye and I though the concensurs for null
> pointers weas to use NULL and not 0?

Yes, otherwise sparse complains... and maybe Linus  :)


> On Mon, Jan 31, 2005 at 01:35:00AM -0600, Matt Mackall wrote:
> 
> 
>>Eep. cpuset uses bubble sort on a data set that's potentially O(#
>>processes). Switch to lib/sort.
> 
> 
>>+	sort(pidarray, npids, sizeof(pid_t), cmppid, 0);
> 
> 
> and there?
> 
> 
> 
> On Mon, Jan 31, 2005 at 01:35:00AM -0600, Matt Mackall wrote:
> 
> 
>>Replace exception table insertion sort with lib/sort
> 
> 
>>+	sort(start, finish - start, sizeof(struct exception_table_entry),
>>+	     cmp_ex, 0);
> 
> 
> and there?


-- 
~Randy

Re: [PATCH 2/8] lib/sort: Replace qsort in XFS

[Zan Lynx]

[-- Attachment #1: Type: text/plain, Size: 1252 bytes --]

On Tue, 2005-02-01 at 14:22 -0800, Randy.Dunlap wrote:
> Chris Wedgwood wrote:
> > On Mon, Jan 31, 2005 at 01:34:59AM -0600, Matt Mackall wrote:
> > 
> > 
> >>+#define qsort xfs_sort
> >>+static inline void xfs_sort(void *a, size_t n, size_t s,
> >>+			int (*cmp)(const void *,const void *))
> >>+{
> >>+	sort(a, n, s, cmp, 0);
> >>+}
> >>+
> > 
> > 
> > why not just:
> > 
> > #define qsort(a, n, s, cmp)	sort(a, n, s, cmp, NULL)
> > 
> > 
> > 
> > On Mon, Jan 31, 2005 at 01:35:00AM -0600, Matt Mackall wrote:
> > 
> > 
> >>Switch NFS ACLs to lib/sort
> > 
> > 
> >>+	sort(acl->a_entries, acl->a_count, sizeof(struct posix_acl_entry),
> >>+	     cmp_acl_entry, 0);
> > 
> > 
> > There was a thread about stlye and I though the concensurs for null
> > pointers weas to use NULL and not 0?
> 
> Yes, otherwise sparse complains... and maybe Linus  :)

And you get in the habit of using 0 instead of NULL and before you know
it you've used it in a variable argument list for a GTK library call on
an AMD64 system and corrupted the stack. :-)

(The compiler can't convert 0 to a pointer if it doesn't know that it's
supposed to be one.  Variable argument lists are evil that way.)

-- 
Zan Lynx <zlynx@acm.org>

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [PATCH 2/8] lib/sort: Replace qsort in XFS

[Herbert Xu]

Zan Lynx <zlynx@acm.org> wrote:
> 
> And you get in the habit of using 0 instead of NULL and before you know
> it you've used it in a variable argument list for a GTK library call on
> an AMD64 system and corrupted the stack. :-)

Using NULL without a cast is equally broken in a variadic context.
Sure it doesn't break on AMD64 but it'll break on platforms where
NULL pointers of different types have different representations.
-- 
Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Re: [PATCH 2/8] lib/sort: Replace qsort in XFS

[Matt Mackall]

On Tue, Feb 01, 2005 at 02:29:15PM -0800, Chris Wedgwood wrote:
> On Mon, Jan 31, 2005 at 01:34:59AM -0600, Matt Mackall wrote:
> 
> > +#define qsort xfs_sort
> > +static inline void xfs_sort(void *a, size_t n, size_t s,
> > +			int (*cmp)(const void *,const void *))
> > +{
> > +	sort(a, n, s, cmp, 0);
> > +}
> > +
> 
> why not just:
> 
> #define qsort(a, n, s, cmp)	sort(a, n, s, cmp, NULL)

Side-effect avoidance habit, not applicable here.

> On Mon, Jan 31, 2005 at 01:35:00AM -0600, Matt Mackall wrote:
> 
> > Switch NFS ACLs to lib/sort
> 
> > +	sort(acl->a_entries, acl->a_count, sizeof(struct posix_acl_entry),
> > +	     cmp_acl_entry, 0);
> 
> There was a thread about stlye and I though the concensurs for null
> pointers weas to use NULL and not 0?

Was it? Grumble. Ok, I'll fix these up.

-- 
Mathematics is the supreme nostalgia of our time.

Re: [PATCH 1/8] lib/sort: Heapsort implementation of sort()

[Andreas Gruenbacher]

Hello,

On Mon, 2005-01-31 at 08:34, Matt Mackall wrote:
> This patch adds a generic array sorting library routine. This is meant
> to replace qsort, which has two problem areas for kernel use.

looks reasonable.

> Note that this function has an extra parameter for passing in an
> optimized swapping function. This is worth 10% or more over the
> typical byte-by-byte exchange functions.

I would appreciate a version without the swap callback. The optimized
version of swap should use the machine word size instead of u32. How
about this approach instead, if you think we must really optimize
swapping?

static inline void swap(void *a, void *b, int size)
{
        if (size % sizeof(long)) {
                char t;
                do {
                        t = *(char *)a;
                        *(char *)a++ = *(char *)b;
                        *(char *)b++ = t;
                } while (--size > 0);
        } else {
                long t;
                do {
                        t = *(long *)a;
                        *(long *)a = *(long *)b;
                        *(long *)b = t;
                        size -= sizeof(long);
                } while (size > sizeof(long));
        }
}

static inline
void __sort(void *base, size_t num, size_t size,
          int (*cmp)(const void *, const void *))
{
...
}

void sort(void *base, size_t num, size_t size,
          int (*cmp)(const void *, const void *)) {
        if (size == sizeof(long)) {
                __sort(base, num, size, cmp);
        } else {
                __sort(base, num, size, cmp);
        }
}

The code size doubles, but it's still hardly an issue. gcc will refuse
to inline things fully without __attribute((allways_inline)). (Note that
__builtin_constant_p doesn't work for inline functions; else we could do
better.)


Cheers,
-- 
Andreas Gruenbacher <agruen@suse.de>
SUSE Labs, SUSE LINUX GMBH

Re: [PATCH 1/8] lib/sort: Heapsort implementation of sort()

[Paulo Marques]

Andreas Gruenbacher wrote:
> [...]
> 
> static inline void swap(void *a, void *b, int size)
> {
>         if (size % sizeof(long)) {
>                 char t;
>                 do {
>                         t = *(char *)a;
>                         *(char *)a++ = *(char *)b;
>                         *(char *)b++ = t;
>                 } while (--size > 0);
>         } else {
>                 long t;
>                 do {
>                         t = *(long *)a;
>                         *(long *)a = *(long *)b;
>                         *(long *)b = t;
>                         size -= sizeof(long);
>                 } while (size > sizeof(long));

You forgot to increment a and b, and this should be "while (size);", no?

>         }
> }

Or better yet,

static inline void swap(void *a, void *b, int size)
{
	long tl;
         char t;

	while (size >= sizeof(long)) {
                 tl = *(long *)a;
                 *(long *)a = *(long *)b;
                 *(long *)b = tl;
		a += sizeof(long);
		b += sizeof(long);
                 size -= sizeof(long);
	}
	while (size) {
                 t = *(char *)a;
                 *(char *)a++ = *(char *)b;
                 *(char *)b++ = t;
		size--;
         }
}

This works better if the size is not a multiple of sizeof(long), but is 
bigger than a long.

However it seems that this should be put in a generic library function...

-- 
Paulo Marques - www.grupopie.com

All that is necessary for the triumph of evil is that good men do nothing.
Edmund Burke (1729 - 1797)

Re: [PATCH 1/8] lib/sort: Heapsort implementation of sort()

[Andreas Gruenbacher]

On Mon, 2005-01-31 at 18:30, Paulo Marques wrote:
> Andreas Gruenbacher wrote:
> > [...]
> > 
> > static inline void swap(void *a, void *b, int size)
> > {
> >         if (size % sizeof(long)) {
> >                 char t;
> >                 do {
> >                         t = *(char *)a;
> >                         *(char *)a++ = *(char *)b;
> >                         *(char *)b++ = t;
> >                 } while (--size > 0);
> >         } else {
> >                 long t;
> >                 do {
> >                         t = *(long *)a;
> >                         *(long *)a = *(long *)b;
> >                         *(long *)b = t;
> >                         size -= sizeof(long);
> >                 } while (size > sizeof(long));
> 
> You forgot to increment a and b, and this should be "while (size);", no?

Correct, yes.

> Or better yet,
> 
> static inline void swap(void *a, void *b, int size)
> {
> 	long tl;
>          char t;
> 
> 	while (size >= sizeof(long)) {
>                  tl = *(long *)a;
>                  *(long *)a = *(long *)b;
>                  *(long *)b = tl;
> 		a += sizeof(long);
> 		b += sizeof(long);
>                  size -= sizeof(long);
> 	}
> 	while (size) {
>                  t = *(char *)a;
>                  *(char *)a++ = *(char *)b;
>                  *(char *)b++ = t;
> 		size--;
>          }
> }
> 
> This works better if the size is not a multiple of sizeof(long), but is 
> bigger than a long.

In case size is not a multiple of sizeof(long) here, you'll have
unaligned memory accesses most of the time anyway, so it probably
doesn't really matter.

Thanks,
-- 
Andreas Gruenbacher <agruen@suse.de>
SUSE Labs, SUSE LINUX GMBH

Re: [PATCH 1/8] lib/sort: Heapsort implementation of sort()

[linux-os]

On Tue, 1 Feb 2005, Andreas Gruenbacher wrote:

> On Mon, 2005-01-31 at 18:30, Paulo Marques wrote:
>> Andreas Gruenbacher wrote:
>>> [...]
>>>
>>> static inline void swap(void *a, void *b, int size)
>>> {
>>>         if (size % sizeof(long)) {
>>>                 char t;
>>>                 do {
>>>                         t = *(char *)a;
>>>                         *(char *)a++ = *(char *)b;
>>>                         *(char *)b++ = t;
>>>                 } while (--size > 0);
>>>         } else {
>>>                 long t;
>>>                 do {
>>>                         t = *(long *)a;
>>>                         *(long *)a = *(long *)b;
>>>                         *(long *)b = t;
>>>                         size -= sizeof(long);
>>>                 } while (size > sizeof(long));
>>
>> You forgot to increment a and b, and this should be "while (size);", no?
>
> Correct, yes.
>
>> Or better yet,
>>
>> static inline void swap(void *a, void *b, int size)
>> {
>> 	long tl;
>>          char t;
>>
>> 	while (size >= sizeof(long)) {
>>                  tl = *(long *)a;
>>                  *(long *)a = *(long *)b;
>>                  *(long *)b = tl;
>> 		a += sizeof(long);
>> 		b += sizeof(long);
>>                  size -= sizeof(long);
>> 	}
>> 	while (size) {
>>                  t = *(char *)a;
>>                  *(char *)a++ = *(char *)b;
>>                  *(char *)b++ = t;
>> 		size--;
>>          }
>> }
>>
>> This works better if the size is not a multiple of sizeof(long), but is
>> bigger than a long.
>
> In case size is not a multiple of sizeof(long) here, you'll have
> unaligned memory accesses most of the time anyway, so it probably
> doesn't really matter.
>
> Thanks,
> -- 
> Andreas Gruenbacher <agruen@suse.de>
> SUSE Labs, SUSE LINUX GMBH

This uses an GNU-ISM where you are doing pointer arithmetic
on a pointer-to-void. NotGood(tm) this is an example of
where there is absolutely no rationale whatsoever for
writing such code.


Cheers,
Dick Johnson
Penguin : Linux version 2.6.10 on an i686 machine (5537.79 BogoMips).
  Notice : All mail here is now cached for review by Dictator Bush.
                  98.36% of all statistics are fiction.

Re: [PATCH 1/8] lib/sort: Heapsort implementation of sort()

[linux-os]

On Tue, 1 Feb 2005, linux-os wrote:

> On Tue, 1 Feb 2005, Andreas Gruenbacher wrote:
>
>> On Mon, 2005-01-31 at 18:30, Paulo Marques wrote:
>>> Andreas Gruenbacher wrote:
>>>> [...]
>>>> 
>>>> static inline void swap(void *a, void *b, int size)
>>>> {
>>>>         if (size % sizeof(long)) {
>>>>                 char t;
>>>>                 do {
>>>>                         t = *(char *)a;
>>>>                         *(char *)a++ = *(char *)b;
>>>>                         *(char *)b++ = t;
>>>>                 } while (--size > 0);
>>>>         } else {
>>>>                 long t;
>>>>                 do {
>>>>                         t = *(long *)a;
>>>>                         *(long *)a = *(long *)b;
>>>>                         *(long *)b = t;
>>>>                         size -= sizeof(long);
>>>>                 } while (size > sizeof(long));
>>> 
>>> You forgot to increment a and b, and this should be "while (size);", no?
>> 
>> Correct, yes.
>> 
>>> Or better yet,
>>> 
>>> static inline void swap(void *a, void *b, int size)
>>> {
>>> 	long tl;
>>>          char t;
>>> 
>>> 	while (size >= sizeof(long)) {
>>>                  tl = *(long *)a;
>>>                  *(long *)a = *(long *)b;
>>>                  *(long *)b = tl;
>>> 		a += sizeof(long);
>>> 		b += sizeof(long);
>>>                  size -= sizeof(long);
>>> 	}
>>> 	while (size) {
>>>                  t = *(char *)a;
>>>                  *(char *)a++ = *(char *)b;
>>>                  *(char *)b++ = t;
>>> 		size--;
>>>          }
>>> }
>>> 
>>> This works better if the size is not a multiple of sizeof(long), but is
>>> bigger than a long.
>> 
>> In case size is not a multiple of sizeof(long) here, you'll have
>> unaligned memory accesses most of the time anyway, so it probably
>> doesn't really matter.
>> 
>> Thanks,
>> -- 
>> Andreas Gruenbacher <agruen@suse.de>
>> SUSE Labs, SUSE LINUX GMBH
>
> This uses an GNU-ISM where you are doing pointer arithmetic
> on a pointer-to-void. NotGood(tm) this is an example of
> where there is absolutely no rationale whatsoever for
> writing such code.
>

Here is swap with no games. Plus it handles the case where
sizeof(long) is not the same as sizeof(int).


void swap(void *a, void *b, size_t len)
{
     while(len >= sizeof(long))
     {
         long one, two;
         long *p0 = a;
         long *p1 = b;
         one = *p0;
         two = *p1;
         *p1++ = one;
         *p0++ = two;
         len -= sizeof(long);
     }
     while(len >= sizeof(int))	// Compiler may even ignore
     {
         int one, two;
         int *p0 = a;
         int *p1 = b;
         one = *p0;
         two = *p1;
         *p1++ = one;
         *p0++ = two;
         len -= sizeof(int);
     }
     while(len--)
     {
         char one, two;
         char *p0 = a;
         char *p1 = b;
         one = *p0;
         two = *p1;
         *p1++ = one;
         *p0++ = two;
     }
}

//----------------------------------------------


And here is the output. You can make it in-line of you want,
but you really need to make in ANSI first.


 	.file	"xxx.c"
 	.text
 	.p2align 2,,3
.globl swap
 	.type	swap, @function
swap:
 	pushl	%ebp
 	movl	%esp, %ebp
 	movl	16(%ebp), %ecx
 	pushl	%esi
 	cmpl	$3, %ecx
 	pushl	%ebx
 	movl	8(%ebp), %esi
 	movl	12(%ebp), %ebx
 	jbe	.L17
 	.p2align 2,,3
.L5:
 	subl	$4, %ecx
 	movl	(%esi), %eax
 	movl	(%ebx), %edx
 	cmpl	$3, %ecx
 	movl	%eax, (%ebx)
 	movl	%edx, (%esi)
 	ja	.L5
.L17:
 	decl	%ecx
 	cmpl	$-1, %ecx
 	je	.L19
 	.p2align 2,,3
.L13:
 	decl	%ecx
 	movb	(%esi), %al
 	movb	(%ebx), %dl
 	cmpl	$-1, %ecx
 	movb	%al, (%ebx)
 	movb	%dl, (%esi)
 	jne	.L13
.L19:
 	popl	%ebx
 	popl	%esi
 	leave
 	ret
 	.size	swap, .-swap
 	.section	.note.GNU-stack,"",@progbits
 	.ident	"GCC: (GNU) 3.3.3 20040412 (Red Hat Linux 3.3.3-7)"

A lot of folks don't realilize that adding a new program-unit
after a conditional expression doesn't necessarily add any code.
In this case, it simply tells the compiler what we want to do.

Cheers,
Dick Johnson
Penguin : Linux version 2.6.10 on an i686 machine (5537.79 BogoMips).
  Notice : All mail here is now cached for review by Dictator Bush.
                  98.36% of all statistics are fiction.

Re: [PATCH 1/8] lib/sort: Heapsort implementation of sort()

[Andreas Gruenbacher]

On Tue, 2005-02-01 at 19:11, linux-os wrote:
> This uses an GNU-ISM where you are doing pointer arithmetic
> on a pointer-to-void. NotGood(tm) [...]

That's perfectly fine inside the kernel.

-- Andreas.

Re: [PATCH 1/8] lib/sort: Heapsort implementation of sort()

[Matt Mackall]

On Mon, Jan 31, 2005 at 06:16:23PM +0100, Andreas Gruenbacher wrote:
> Hello,
> 
> On Mon, 2005-01-31 at 08:34, Matt Mackall wrote:
> > This patch adds a generic array sorting library routine. This is meant
> > to replace qsort, which has two problem areas for kernel use.
> 
> looks reasonable.
> 
> > Note that this function has an extra parameter for passing in an
> > optimized swapping function. This is worth 10% or more over the
> > typical byte-by-byte exchange functions.
> 
> I would appreciate a version without the swap callback.

Why? To eliminate an argument?

> The optimized version of swap should use the machine word size
> instead of u32.

That occurred to me, but most instances I found in my audit were using
u32 rather than long.

> How about this approach instead, if you think we
> must really optimize swapping?
>
> static inline void swap(void *a, void *b, int size)
> {
>         if (size % sizeof(long)) {
>                 char t;
>                 do {
>                         t = *(char *)a;
>                         *(char *)a++ = *(char *)b;
>                         *(char *)b++ = t;
>                 } while (--size > 0);
>         } else {
>                 long t;
>                 do {
>                         t = *(long *)a;
>                         *(long *)a = *(long *)b;
>                         *(long *)b = t;
>                         size -= sizeof(long);
>                 } while (size > sizeof(long));
>         }
> }

This makes things worse. Sort isn't inlined, so we don't know size
until we're called and then we're branching in the innermost loop and
growing the code footprint to boot. Function pointer wins in my
benchmarks.

Note that there are callers like IA64 extable that want a custom swap already:

- * stack may be more than 2GB away from the exception-table).
+ * Sort the exception table. It's usually already sorted, but there
+ * may be unordered entries due to multiple text sections (such as the
+ * .init text section). Note that the exception-table-entries contain
+ * location-relative addresses, which requires a bit of care during
+ * sorting to avoid overflows in the offset members (e.g., it would
+ * not be safe to make a temporary copy of an exception-table entry on
+ * the stack, because the stack may be more than 2GB away from the
+ * exception-table).
  */

There are a bunch of other potential users that sort parallel arrays
a[] and b[] with keys in a[] that want this too.

-- 
Mathematics is the supreme nostalgia of our time.

Re: [PATCH 1/8] lib/sort: Heapsort implementation of sort()

[Andreas Gruenbacher]

On Mon, 2005-01-31 at 20:30, Matt Mackall wrote:
> On Mon, Jan 31, 2005 at 06:16:23PM +0100, Andreas Gruenbacher wrote:
> > Hello,
> > 
> > On Mon, 2005-01-31 at 08:34, Matt Mackall wrote:
> > > This patch adds a generic array sorting library routine. This is meant
> > > to replace qsort, which has two problem areas for kernel use.
> > 
> > looks reasonable.
> > 
> > > Note that this function has an extra parameter for passing in an
> > > optimized swapping function. This is worth 10% or more over the
> > > typical byte-by-byte exchange functions.
> > 
> > I would appreciate a version without the swap callback.
> 
> Why? To eliminate an argument?

Yes, because a custom swap routine isn't very useful generally. It's
over-engineered IMHO.

> > The optimized version of swap should use the machine word size
> > instead of u32.
> 
> That occurred to me, but most instances I found in my audit were using
> u32 rather than long.

Alright, that may be the case.

> > How about this approach instead, if you think we
> > must really optimize swapping?
> >
> > static inline void swap(void *a, void *b, int size)
> > {
> >         if (size % sizeof(long)) {
> >                 char t;
> >                 do {
> >                         t = *(char *)a;
> >                         *(char *)a++ = *(char *)b;
> >                         *(char *)b++ = t;
> >                 } while (--size > 0);
> >         } else {
> >                 long t;
> >                 do {
> >                         t = *(long *)a;
> >                         *(long *)a = *(long *)b;
> >                         *(long *)b = t;
> >                         size -= sizeof(long);
> >                 } while (size > sizeof(long));
> >         }
> > }
> 
> This makes things worse. Sort isn't inlined, so we don't know size
> until we're called and then we're branching in the innermost loop

Well, the example code I referred to had an inlined __sort, and the size
== sizeof(long) case ended up being perfectly optimized. It bloats the
code somewhat though, but it's still tiny.

> and growing the code footprint to boot.

You mean the object footprint? I don't care much whether we use some 350
bytes more or not.

> Function pointer wins in my benchmarks.

I had a slowdown in the low percentage range when doing bytewise swap
instead of wordwise swap as well, but function pointers were about as
fast as wordwise swap. So no significant gain.

> Note that there are callers like IA64 extable that want a custom swap already:
> 
> - * stack may be more than 2GB away from the exception-table).
> + * Sort the exception table. It's usually already sorted, but there
> + * may be unordered entries due to multiple text sections (such as the
> + * .init text section). Note that the exception-table-entries contain
> + * location-relative addresses, which requires a bit of care during
> + * sorting to avoid overflows in the offset members (e.g., it would
> + * not be safe to make a temporary copy of an exception-table entry on
> + * the stack, because the stack may be more than 2GB away from the
> + * exception-table).
>   */

We could either leave the current insertion sort in place in
arch/ia64/mm/extable.c, or transform the exception table into sortable
form first, as in the below mock-up.

+       /* Exception-table-entries contain location-relative addresses. Convert
+          to addresses relative to START before sorting, and convert back to
+          location-relative addresses afterwards. This allows us to use the
+          general-purpose sort function. */
+       for (p = start+1; p < finish; p++) {
+               int n = (void *)p - (void *)start;
+               p->addr += n;
+               p->cont += n;
+       }
+       sort(start, finish - start, sizeof(struct exception_table_entry),
+            compare_entries);
+       for (p = start+1; p < finish; p++) {
+               int n = (void *)p - (void *)start;
+               p->addr -= n;
+               p->cont -= n;
+       }

Switching to the generic sort probably isn't worth it in this case.

> There are a bunch of other potential users that sort parallel arrays
> a[] and b[] with keys in a[] that want this too.

Where?

Thanks,
-- 
Andreas Gruenbacher <agruen@suse.de>
SUSE Labs, SUSE LINUX GMBH

Re: [PATCH 1/8] lib/sort: Heapsort implementation of sort()

[Horst von Brand]

Andreas Gruenbacher <agruen@suse.de> said:

[...]

> Yes, because a custom swap routine isn't very useful generally. It's
> over-engineered IMHO.

It shouldn't swap, but juggle elements around like so:

    t --------------->+
    ^                 |
    |                 v
    x <-- x <-- x <-- x

Sure, this needs a temporary element, but reduces the data copying to
around 1/3 (1 swap == 3 copies, this makes a bit more than 1 copy for each
element moved). This is probably much more important than
microoptimizations in swap.

My tuned heapsort for doubles is:

/*
 * heapsort.c: Heap sort
 */

#include "sort.h"

void
sort(double a[], int n)

{
  double tmp;
  int i, j, k;
    
  /* Make heap */
  for(i = n / 2 - 1; i >= 0; i--) {
    /* downheap(a, i, n); */
    j = i;
    tmp = a[j];
    for(;;) {
      k = 2 * j + 1;
      if(k >= n)
	break;
      if(k + 1 < n && a[k + 1] > a[k])
	k++;
      if(tmp > a[k])
	break;
      a[j] = a[k];
      j = k;
    }
    a[j] = tmp;
  }
    
  /* Sort */
  for(i = n - 1; i >= 1; i--) {
    /* downheap(a, 1, i); swap(a[1], a[n]); */
    j = 0;
    tmp = a[j];
    for(;;) {
      k = 2 * j + 1;
      if(k > i)
	break;
      if(k + 1 <= i && a[k + 1] > a[k])
	k++;
      if(tmp > a[k])
	break;
      a[j] = a[k];
      j = k;
    }
    a[j] = tmp;

    tmp = a[0]; a[0] = a[i]; a[i] = tmp;
  }
}

Hack on it as you wish.
-- 
Dr. Horst H. von Brand                   User #22616 counter.li.org
Departamento de Informatica                     Fono: +56 32 654431
Universidad Tecnica Federico Santa Maria              +56 32 654239
Casilla 110-V, Valparaiso, Chile                Fax:  +56 32 797513

Re: [PATCH 1/8] lib/sort: Heapsort implementation of sort()

[Herbert Xu]

Andreas Gruenbacher <agruen@suse.de> wrote:
> 
> static inline void swap(void *a, void *b, int size)
> {
>        if (size % sizeof(long)) {
>                char t;
>                do {
>                        t = *(char *)a;
>                        *(char *)a++ = *(char *)b;
>                        *(char *)b++ = t;
>                } while (--size > 0);
>        } else {
>                long t;
>                do {
>                        t = *(long *)a;
>                        *(long *)a = *(long *)b;
>                        *(long *)b = t;
>                        size -= sizeof(long);
>                } while (size > sizeof(long));
>        }
> }

What if a/b aren't aligned?
-- 
Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Re: [PATCH 1/8] lib/sort: Heapsort implementation of sort()

[Andreas Gruenbacher]

On Wed, 2005-02-02 at 11:50, Herbert Xu wrote:
> Andreas Gruenbacher <agruen@suse.de> wrote:
> > 
> > static inline void swap(void *a, void *b, int size)
> > {
> >        if (size % sizeof(long)) {
> >                char t;
> >                do {
> >                        t = *(char *)a;
> >                        *(char *)a++ = *(char *)b;
> >                        *(char *)b++ = t;
> >                } while (--size > 0);
> >        } else {
> >                long t;
> >                do {
> >                        t = *(long *)a;
> >                        *(long *)a = *(long *)b;
> >                        *(long *)b = t;
> >                        size -= sizeof(long);
> >                } while (size > sizeof(long));
> >        }
> > }
> 
> What if a/b aren't aligned?

That would be the case if the entire array was unaligned, or (size %
sizeof(long)) != 0. If people sort arrays that are unaligned even though
the element size is a multiple of sizeof(long) (or sizeof(u32) as Matt
proposes), they are just begging for bad performance. Otherwise, we're
doing byte-wise swap anyway.

-- 
Andreas Gruenbacher <agruen@suse.de>
SUSE Labs, SUSE LINUX GMBH

Re: [PATCH 1/8] lib/sort: Heapsort implementation of sort()

[Junio C Hamano]

>>>>> "AG" == Andreas Gruenbacher <agruen@suse.de> writes:

AG> On Wed, 2005-02-02 at 11:50, Herbert Xu wrote:
>> What if a/b aren't aligned?

AG> If people sort arrays that are unaligned even though the
AG> element size is a multiple of sizeof(long) (or sizeof(u32)
AG> as Matt proposes), they are just begging for bad
AG> performance.

If the user of your sort routine is dealing with an array of
this shape:

    struct { char e[8]; } a[]

the alignment for the normal access (e.g. a[ix].e[iy]) would not
matter and they are not begging for bad performance, are they?
It is only this swap routine, which is internal to the
implementation of sort, that is begging for it, methinks.  

Is unaligned access inside of the kernel get fixed up on all
architectures?  If not, this would not just be a performance
issue but becomes a correctness issue.

How about something like this to be a bit more defensive:

static inline void swap(void *a, void *b, int size)
{
       if (((unsigned long)a | (unsigned long)b | size) % sizeof(long)) {
	       char t;
	       do {
		       t = *(char *)a;
		       *(char *)a++ = *(char *)b;
		       *(char *)b++ = t;
	       } while (--size > 0);
       } else {
	       long t;
	       do {
		       t = *(long *)a;
		       *(long *)a = *(long *)b;
		       *(long *)b = t;
		       size -= sizeof(long);
	       } while (size > sizeof(long));
       }
}

Re: [PATCH 1/8] lib/sort: Heapsort implementation of sort()

[Horst von Brand]

Matt Mackall <mpm@selenic.com> said:
> This patch adds a generic array sorting library routine. This is meant
> to replace qsort, which has two problem areas for kernel use.

Another problem is the GPL license. It will certainly be wanted from
non-GPL (e.g., binary) modules. Please just EXPORT_SYMBOL it.
-- 
Dr. Horst H. von Brand                   User #22616 counter.li.org
Departamento de Informatica                     Fono: +56 32 654431
Universidad Tecnica Federico Santa Maria              +56 32 654239
Casilla 110-V, Valparaiso, Chile                Fax:  +56 32 797513

Re: [PATCH 1/8] lib/sort: Heapsort implementation of sort()

[Andreas Gruenbacher]

Matt,

On Monday 31 January 2005 08:34, Matt Mackall wrote:
> This patch adds a generic array sorting library routine. This is meant
> to replace qsort, which has two problem areas for kernel use.

the sort function is broken. When sorting the integer array {1, 2, 3, 4, 5}, 
I'm getting {2, 3, 4, 5, 1} as a result. Can you please have a look?

Thanks,
-- 
Andreas Gruenbacher <agruen@suse.de>
SUSE Labs, SUSE LINUX PRODUCTS GMBH

Re: [PATCH 1/8] lib/sort: Heapsort implementation of sort()

[Matt Mackall]

On Sun, Feb 27, 2005 at 02:17:51PM +0100, Andreas Gruenbacher wrote:
> Matt,
> 
> On Monday 31 January 2005 08:34, Matt Mackall wrote:
> > This patch adds a generic array sorting library routine. This is meant
> > to replace qsort, which has two problem areas for kernel use.
> 
> the sort function is broken. When sorting the integer array {1, 2, 3, 4, 5}, 
> I'm getting {2, 3, 4, 5, 1} as a result. Can you please have a look?

Which kernel? There was an off-by-one for odd array sizes in the
original posted version that was quickly spotted:

http://www.kernel.org/pub/linux/kernel/people/akpm/patches/2.6/2.6.11-rc4/2.6.11-rc4-mm1/broken-out/sort-fix.patch

I've since tested all sizes 1 - 1000 with 100 random arrays each, so
I'm fairly confident it's now fixed.

-- 
Mathematics is the supreme nostalgia of our time.

Re: [PATCH 1/8] lib/sort: Heapsort implementation of sort()

[Andreas Gruenbacher]

[-- Attachment #1: Type: text/plain, Size: 1064 bytes --]

On Sunday 27 February 2005 22:25, Matt Mackall wrote:
> On Sun, Feb 27, 2005 at 02:17:51PM +0100, Andreas Gruenbacher wrote:
> > Matt,
> >
> > On Monday 31 January 2005 08:34, Matt Mackall wrote:
> > > This patch adds a generic array sorting library routine. This is meant
> > > to replace qsort, which has two problem areas for kernel use.
> >
> > the sort function is broken. When sorting the integer array {1, 2, 3, 4,
> > 5}, I'm getting {2, 3, 4, 5, 1} as a result. Can you please have a look?
>
> Which kernel? There was an off-by-one for odd array sizes in the
> original posted version that was quickly spotted:
>
> http://www.kernel.org/pub/linux/kernel/people/akpm/patches/2.6/2.6.11-rc4/2
>.6.11-rc4-mm1/broken-out/sort-fix.patch

Okay, I didn't notice the off-by-one fix. It's still broken though; see the 
attached user-space test.

> I've since tested all sizes 1 - 1000 with 100 random arrays each, so
> I'm fairly confident it's now fixed.

Famous last words ;)

Thanks,
-- 
Andreas Gruenbacher <agruen@suse.de>
SUSE Labs, SUSE LINUX PRODUCTS GMBH

[-- Attachment #2: sort.c --]
[-- Type: text/x-csrc, Size: 2121 bytes --]

/*
 * A fast, small, non-recursive O(nlog n) sort for the Linux kernel
 *
 * Jan 23 2005  Matt Mackall <mpm@selenic.com>
 */

#include <stdlib.h>
#include <stdio.h>

void generic_swap(void *a, void *b, int size)
{
	char t;

	do {
		t = *(char *)a;
		*(char *)a++ = *(char *)b;
		*(char *)b++ = t;
	} while (--size > 0);
}

/*
 * sort - sort an array of elements
 * @base: pointer to data to sort
 * @num: number of elements
 * @size: size of each element
 * @cmp: pointer to comparison function
 * @swap: pointer to swap function or NULL
 *
 * This function does a heapsort on the given array. You may provide a
 * swap function optimized to your element type.
 *
 * Sorting time is O(n log n) both on average and worst-case. While
 * qsort is about 20% faster on average, it suffers from exploitable
 * O(n*n) worst-case behavior and extra memory requirements that make
 * it less suitable for kernel use.
 */

void sort(void *base, size_t num, size_t size,
	  int (*cmp)(const void *, const void *),
	  void (*swap)(void *, void *, int size))
{
	/* pre-scale counters for performance */
	int i = (num/2) * size, n = num * size, c, r;

	if (!swap)
		swap = generic_swap;

	/* heapify */
	for ( ; i >= 0; i -= size) {
		for (r = i; r * 2 < n; r  = c) {
			c = r * 2;
			if (c < n - size && cmp(base + c, base + c + size) < 0)
				c += size;
			if (cmp(base + r, base + c) >= 0)
				break;
			swap(base + r, base + c, size);
		}
	}

	/* sort */
	for (i = n - size; i >= 0; i -= size) {
		swap(base, base + i, size);
		for (r = 0; r * 2 < i; r = c) {
			c = r * 2;
			if (c < i - size && cmp(base + c, base + c + size) < 0)
				c += size;
			if (cmp(base + r, base + c) >= 0)
				break;
			swap(base + r, base + c, size);
		}
	}
}

int cmp(const int *a, const int *b)
{
	return b - a;
}

int main(void)
{
	int a[] = { 1, 2, 3, 4, 5 };
	size_t n;

	for (n = 0; n < sizeof(a)/sizeof(a[0]); n++)
		printf("%d ", a[n]);
	puts("");
	sort(a, sizeof(a)/sizeof(a[0]), sizeof(a[0]),
	     (int (*)(const void *, const void *))cmp, NULL);
	for (n = 0; n < sizeof(a)/sizeof(a[0]); n++)
		printf("%d ", a[n]);
	puts("");

	return 0;
}

Re: [PATCH 1/8] lib/sort: Heapsort implementation of sort()

[Andreas Gruenbacher]

On Sunday 27 February 2005 22:53, Andreas Gruenbacher wrote:
> Okay, I didn't notice the off-by-one fix. It's still broken though; see the
> attached user-space test.

Found it. I didn't have the off-by-one fix and the bug triggered; then the 
test case had a useless comparison function:

int cmp(const int *a, const int *b)
{
        return b - a;
}

Works fine now.

Thanks,
-- 
Andreas Gruenbacher <agruen@suse.de>
SUSE Labs, SUSE LINUX PRODUCTS GMBH

Re: [PATCH 1/8] lib/sort: Heapsort implementation of sort()

[Andreas Gruenbacher]

On Sun, 2005-02-27 at 22:25, Matt Mackall wrote:
> On Sun, Feb 27, 2005 at 02:17:51PM +0100, Andreas Gruenbacher wrote:
> > Matt,
> > 
> > On Monday 31 January 2005 08:34, Matt Mackall wrote:
> > > This patch adds a generic array sorting library routine. This is meant
> > > to replace qsort, which has two problem areas for kernel use.
> > 
> > the sort function is broken. When sorting the integer array {1, 2, 3, 4, 5}, 
> > I'm getting {2, 3, 4, 5, 1} as a result. Can you please have a look?
> 
> Which kernel? There was an off-by-one for odd array sizes in the
> original posted version that was quickly spotted:
> 
> http://www.kernel.org/pub/linux/kernel/people/akpm/patches/2.6/2.6.11-rc4/2.6.11-rc4-mm1/broken-out/sort-fix.patch

Just for the record: This fixed it.

Thanks,
-- 
Andreas Gruenbacher <agruen@suse.de>
SUSE Labs, SUSE LINUX GMBH

Re: [PATCH 1/8] lib/sort: Heapsort implementation of sort()

[Christophe Saout]

[-- Attachment #1: Type: text/plain, Size: 3473 bytes --]

Am Sonntag, den 27.02.2005, 13:25 -0800 schrieb Matt Mackall:

> Which kernel? There was an off-by-one for odd array sizes in the
> original posted version that was quickly spotted:
> 
> http://www.kernel.org/pub/linux/kernel/people/akpm/patches/2.6/2.6.11-rc4/2.6.11-rc4-mm1/broken-out/sort-fix.patch
> 
> I've since tested all sizes 1 - 1000 with 100 random arrays each, so
> I'm fairly confident it's now fixed.

-	int i = (num/2 - 1) * size, n = num * size, c, r;
+	int i = (num/2) * size, n = num * size, c, r;

What's probably meant is: ((num - 1)/2) * size

`i' must cover half of the array or a little bit more (not less, in case
of odd numbers). `i' (before my patch) is the highest address to start
with, so that's why it should be ((num + 1)/2 - 1) * size or simpler:
((num - 1)/2) * size

Anyway, I was wondering, is there a specific reason you are not using
size_t for the offset variables? size is a size_t and the only purpose
of the variables i, n, c and r is to be compared or added to the start
pointer (also I think it's just ugly to cast size_t down to an int).

On system where int is 32 bit but pointers are 64 bit the compiler might
need to extend to adjust the size of the operands for the address
calculation. Right?

Since size_t is unsigned I also had to modify the two loops since I
can't check for any of the variables becoming negative. Tested with all
kinds of array sizes.

Signed-off-by: Christophe Saout <christophe@saout.de>

diff -Nur linux-2.6.11-rc4-mm1.orig/include/linux/sort.h linux-2.6.11-rc4-mm1/include/linux/sort.h
--- linux-2.6.11-rc4-mm1.orig/include/linux/sort.h	2005-03-01 19:45:11.000000000 +0100
+++ linux-2.6.11-rc4-mm1/include/linux/sort.h	2005-03-01 19:47:13.456097896 +0100
@@ -5,6 +5,6 @@
 
 void sort(void *base, size_t num, size_t size,
 	  int (*cmp)(const void *, const void *),
-	  void (*swap)(void *, void *, int));
+	  void (*swap)(void *, void *, size_t));
 
 #endif
diff -Nur linux-2.6.11-rc4-mm1.orig/lib/sort.c linux-2.6.11-rc4-mm1/lib/sort.c
--- linux-2.6.11-rc4-mm1.orig/lib/sort.c	2005-03-01 19:46:05.000000000 +0100
+++ linux-2.6.11-rc4-mm1/lib/sort.c	2005-03-01 19:47:55.688677568 +0100
@@ -7,14 +7,14 @@
 #include <linux/kernel.h>
 #include <linux/module.h>
 
-void u32_swap(void *a, void *b, int size)
+void u32_swap(void *a, void *b, size_t size)
 {
 	u32 t = *(u32 *)a;
 	*(u32 *)a = *(u32 *)b;
 	*(u32 *)b = t;
 }
 
-void generic_swap(void *a, void *b, int size)
+void generic_swap(void *a, void *b, size_t size)
 {
 	char t;
 
@@ -44,17 +44,19 @@
 
 void sort(void *base, size_t num, size_t size,
 	  int (*cmp)(const void *, const void *),
-	  void (*swap)(void *, void *, int size))
+	  void (*swap)(void *, void *, size_t size))
 {
 	/* pre-scale counters for performance */
-	int i = (num/2) * size, n = num * size, c, r;
+	size_t i = ((num + 1)/2) * size, n = num * size, c, r;
 
 	if (!swap)
 		swap = (size == 4 ? u32_swap : generic_swap);
 
 	/* heapify */
-	for ( ; i >= 0; i -= size) {
-		for (r = i; r * 2 < n; r  = c) {
+	while(i > 0) {
+		i -= size;
+
+		for (r = i; r * 2 < n; r = c) {
 			c = r * 2;
 			if (c < n - size && cmp(base + c, base + c + size) < 0)
 				c += size;
@@ -65,7 +67,9 @@
 	}
 
 	/* sort */
-	for (i = n - size; i >= 0; i -= size) {
+	for (i = n; i > 0;) {
+		i -= size;
+
 		swap(base, base + i, size);
 		for (r = 0; r * 2 < i; r = c) {
 			c = r * 2;


[-- Attachment #2: Dies ist ein digital signierter Nachrichtenteil --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [PATCH 1/8] lib/sort: Heapsort implementation of sort()

[Matt Mackall]

On Tue, Mar 01, 2005 at 08:06:22PM +0100, Christophe Saout wrote:
> Am Sonntag, den 27.02.2005, 13:25 -0800 schrieb Matt Mackall:
> 
> > Which kernel? There was an off-by-one for odd array sizes in the
> > original posted version that was quickly spotted:
> > 
> > http://www.kernel.org/pub/linux/kernel/people/akpm/patches/2.6/2.6.11-rc4/2.6.11-rc4-mm1/broken-out/sort-fix.patch
> > 
> > I've since tested all sizes 1 - 1000 with 100 random arrays each, so
> > I'm fairly confident it's now fixed.
> 
> -	int i = (num/2 - 1) * size, n = num * size, c, r;
> +	int i = (num/2) * size, n = num * size, c, r;
> 
> What's probably meant is: ((num - 1)/2) * size
> 
> `i' must cover half of the array or a little bit more (not less, in case
> of odd numbers). `i' (before my patch) is the highest address to start
> with, so that's why it should be ((num + 1)/2 - 1) * size or simpler:
> ((num - 1)/2) * size

Argh. Yes, you're right. This probably deserves a comment since it's
been gotten wrong twice. I'll add something..
 
> Anyway, I was wondering, is there a specific reason you are not using
> size_t for the offset variables? size is a size_t and the only purpose
> of the variables i, n, c and r is to be compared or added to the start
> pointer (also I think it's just ugly to cast size_t down to an int).
> 
> On system where int is 32 bit but pointers are 64 bit the compiler might
> need to extend to adjust the size of the operands for the address
> calculation. Right?
> 
> Since size_t is unsigned I also had to modify the two loops since I
> can't check for any of the variables becoming negative. Tested with all
> kinds of array sizes.

This is good, but I suspect you'll have Andrew pulling his hair out as
I'll then have to go adjust all the callers and this is already a huge
mess because of the ACL bits from Andreas. As the current code
correctly (but slightly suboptimally) sorts any array size less than a
2G, I think it's safe to hold off on this for a bit. I'll queue this
up for after the sort and ACL stuff gets merged.

-- 
Mathematics is the supreme nostalgia of our time.

Re: [PATCH 1/8] lib/sort: Heapsort implementation of sort()

[Andrew Morton]

Matt Mackall <mpm@selenic.com> wrote:
>
> I'll queue this
> up for after the sort and ACL stuff gets merged.

Whew!

I don't know how long the ACL changes will take to get merged up - is up to
Trond and he had quite a lot of rather robust comments on the first
iteration.