WARNING - OLD ARCHIVES

This is an archived copy of the Xen.org mailing list, which we have preserved to ensure that existing links to archives are not broken. The live archive, which contains the latest emails, can be found at http://lists.xen.org/
   
 
 
Xen 
 
Home Products Support Community News
 
   
 

xen-devel

[Xen-devel] [PATCH 1/3] make sort() generally available

To: "xen-devel@xxxxxxxxxxxxxxxxxxx" <xen-devel@xxxxxxxxxxxxxxxxxxx>
Subject: [Xen-devel] [PATCH 1/3] make sort() generally available
From: "Jan Beulich" <JBeulich@xxxxxxxxxx>
Date: Thu, 23 Dec 2010 12:57:14 +0000
Delivery-date: Thu, 23 Dec 2010 04:59:29 -0800
Envelope-to: www-data@xxxxxxxxxxxxxxxxxxx
List-help: <mailto:xen-devel-request@lists.xensource.com?subject=help>
List-id: Xen developer discussion <xen-devel.lists.xensource.com>
List-post: <mailto:xen-devel@lists.xensource.com>
List-subscribe: <http://lists.xensource.com/mailman/listinfo/xen-devel>, <mailto:xen-devel-request@lists.xensource.com?subject=subscribe>
List-unsubscribe: <http://lists.xensource.com/mailman/listinfo/xen-devel>, <mailto:xen-devel-request@lists.xensource.com?subject=unsubscribe>
Sender: xen-devel-bounces@xxxxxxxxxxxxxxxxxxx
Rather than having this general library function only on ia64, move it
into common code, to be used by x86 exception table sorting too.

Signed-off-by: Jan Beulich <jbeulich@xxxxxxxxxx>

--- 2010-12-23.orig/xen/arch/ia64/linux-xen/Makefile
+++ 2010-12-23/xen/arch/ia64/linux-xen/Makefile
@@ -12,7 +12,6 @@ obj-y += sal.o
 obj-y += setup.o
 obj-y += smpboot.o
 obj-y += smp.o
-obj-y += sort.o
 obj-y += time.o
 obj-y += tlb.o
 obj-y += unaligned.o
--- 2010-12-23.orig/xen/arch/ia64/linux-xen/README.origin
+++ 2010-12-23/xen/arch/ia64/linux-xen/README.origin
@@ -21,7 +21,6 @@ sal.c                 -> linux/arch/ia64/kernel/sal.c
 setup.c                        -> linux/arch/ia64/kernel/setup.c
 smp.c                  -> linux/arch/ia64/kernel/smp.c
 smpboot.c              -> linux/arch/ia64/kernel/smpboot.c
-sort.c                 -> linux/lib/sort.c
 time.c                 -> linux/arch/ia64/kernel/time.c
 tlb.c                  -> linux/arch/ia64/mm/tlb.c
 unaligned.c            -> linux/arch/ia64/kernel/unaligned.c
--- 2010-12-23.orig/xen/arch/ia64/linux-xen/sort.c
+++ /dev/null
@@ -1,122 +0,0 @@
-/*
- * A fast, small, non-recursive O(nlog n) sort for the Linux kernel
- *
- * Jan 23 2005  Matt Mackall <mpm@xxxxxxxxxxx>
- */
-
-#include <linux/kernel.h>
-#include <linux/module.h>
-#ifdef XEN
-#include <linux/types.h>
-#endif
-
-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) * 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(sort);
-
-#if 0
-/* 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 = 1;
-
-       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, NULL);
-
-       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
--- 2010-12-23.orig/xen/common/Makefile
+++ 2010-12-23/xen/common/Makefile
@@ -22,6 +22,7 @@ obj-y += sched_arinc653.o
 obj-y += schedule.o
 obj-y += shutdown.o
 obj-y += softirq.o
+obj-y += sort.o
 obj-y += spinlock.o
 obj-y += stop_machine.o
 obj-y += string.o
--- /dev/null
+++ 2010-12-23/xen/common/sort.c
@@ -0,0 +1,78 @@
+/*
+ * A fast, small, non-recursive O(nlog n) sort for the Linux kernel
+ *
+ * Jan 23 2005  Matt Mackall <mpm@xxxxxxxxxxx>
+ */
+
+#include <xen/types.h>
+
+static void u32_swap(void *a, void *b, int size)
+{
+       u32 t = *(u32 *)a;
+       *(u32 *)a = *(u32 *)b;
+       *(u32 *)b = t;
+}
+
+static 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 = (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);
+               }
+       }
+}
--- 2010-12-23.orig/xen/include/asm-ia64/linux/README.origin
+++ 2010-12-23/xen/include/asm-ia64/linux/README.origin
@@ -16,7 +16,6 @@ notifier.h            -> linux/include/linux/notif
 percpu.h               -> linux/include/linux/percpu.h
 preempt.h              -> linux/include/linux/preempt.h
 seqlock.h              -> linux/include/linux/seqlock.h
-sort.h                 -> linux/include/linux/sort.h
 stddef.h               -> linux/include/linux/stddef.h
 thread_info.h          -> linux/include/linux/thread_info.h
 time.h                 -> linux/include/linux/time.h
--- 2010-12-23.orig/xen/include/asm-ia64/linux/sort.h
+++ /dev/null
@@ -1,10 +0,0 @@
-#ifndef _LINUX_SORT_H
-#define _LINUX_SORT_H
-
-#include <linux/types.h>
-
-void sort(void *base, size_t num, size_t size,
-         int (*cmp)(const void *, const void *),
-         void (*swap)(void *, void *, int));
-
-#endif
--- /dev/null
+++ 2010-12-23/xen/include/xen/sort.h
@@ -0,0 +1,10 @@
+#ifndef __SORT_H__
+#define __SORT_H__
+
+#include <xen/types.h>
+
+void sort(void *base, size_t num, size_t size,
+         int (*cmp)(const void *, const void *),
+         void (*swap)(void *, void *, int));
+
+#endif /* __SORT_H__ */


Attachment: sort-generic.patch
Description: Text document

_______________________________________________
Xen-devel mailing list
Xen-devel@xxxxxxxxxxxxxxxxxxx
http://lists.xensource.com/xen-devel
<Prev in Thread] Current Thread [Next in Thread>
  • [Xen-devel] [PATCH 1/3] make sort() generally available, Jan Beulich <=