lib/sort: Add generic sort to lib/

Replace exception table insertion sort with lib/sort

Index: mm2/lib/extable.c
===================================================================
@@ -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
 

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

Index: tq/kernel/cpuset.c
===================================================================
@@ -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;

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

Index: tq/arch/x86_64/mm/extable.c
===================================================================
@@ -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
===================================================================
@@ -73,6 +73,7 @@
 	unsigned long insn, fixup;
 };
 
+#define ARCH_HAS_SEARCH_EXTABLE
 
 /*
  * These are the main single-value transfer routines.  They automatically

Switch IA64 exception tables to lib/sort.

Index: tq/arch/ia64/mm/extable.c
===================================================================
@@ -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 *

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.

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

Index: mm2/fs/xfs/linux-2.6/xfs_linux.h
===================================================================
@@ -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
===================================================================
@@ -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

Switch NFS ACLs to lib/sort

Index: mm2/fs/nfsacl.c
===================================================================
@@ -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
===================================================================
@@ -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

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%

Index: mm2/lib/Makefile
===================================================================
@@ -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
===================================================================
@@ -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

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

Index: mm2/lib/qsort.c
===================================================================
@@ -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 ([email protected]).
-
-   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
===================================================================
@@ -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
===================================================================
@@ -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/

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 <[email protected]> 1.650.933.1373, 1.925.600.0401

Hello,

looks reasonable.

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 <[email protected]>
SUSE Labs, SUSE LINUX GMBH

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)

Why? To eliminate an argument?

That occurred to me, but most instances I found in my audit were using u32 rather than 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.

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

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

Alright, that may be the case.

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.

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

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.

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.

Where?

Thanks,

Andreas Gruenbacher <[email protected]>
SUSE Labs, SUSE LINUX GMBH

Correct, yes.

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 <[email protected]>
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.

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.

That's perfectly fine inside the kernel.

-- Andreas.

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

~Randy

Side-effect avoidance habit, not applicable here.

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

Mathematics is the supreme nostalgia of our time.

Andreas Gruenbacher <[email protected]> said:

[...]

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

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 <[email protected]>

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~} <[email protected]>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

What if a/b aren't aligned?

Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <[email protected]>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

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 <[email protected]>
SUSE Labs, SUSE LINUX GMBH

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));
       }
}

Matt,

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 <[email protected]>
SUSE Labs, SUSE LINUX PRODUCTS GMBH

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.

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

Famous last words ;)

Thanks,

Andreas Gruenbacher <[email protected]>
SUSE Labs, SUSE LINUX PRODUCTS GMBH

/*
* A fast, small, non-recursive O(nlog n) sort for the Linux kernel *
* Jan 23 2005 Matt Mackall <[email protected]>
*/

#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;
}

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 <[email protected]>
SUSE Labs, SUSE LINUX PRODUCTS GMBH

Just for the record: This fixed it.

Thanks,

Andreas Gruenbacher <[email protected]>
SUSE Labs, SUSE LINUX GMBH

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

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

diff -Nur linux-2.6.11-rc4-mm1.orig/include/linux/sort.h linux-2.6.11-rc4-mm1/include/linux/sort.h
@@ -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
@@ -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;

Argh. Yes, you're right. This probably deserves a comment since it's been gotten wrong twice. I'll add something..

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.

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.