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.
Replace exception table insertion sort with lib/sort
Signed-off-by: Matt Mackall <[email protected]>
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
Switch IA64 exception tables to lib/sort.
Signed-off-by: Matt Mackall <[email protected]>
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 *
Remove qsort() before anyone gets too attached to it.
Signed-off-by: Matt Mackall <[email protected]>
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 ([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
===================================================================
--- 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/
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 <[email protected]>
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 <[email protected]>
+ */
+
+#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
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
Point XFS qsort at lib/sort in a way that makes it happy.
Signed-off-by: Matt Mackall <[email protected]>
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
x86_64 wasn't doing anything special in its sort_extable. Use the
generic lib/extable sort.
Signed-off-by: Matt Mackall <[email protected]>
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
Eep. cpuset uses bubble sort on a data set that's potentially O(#
processes). Switch to lib/sort.
Signed-off-by: Matt Mackall <[email protected]>
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;
On Mon, 31 Jan 2005 01:34:59 -0600, 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.
> --- /dev/null
> +++ mm2/include/linux/sort.h
> @@ -0,0 +1,8 @@
> +void sort(void *base, size_t num, size_t size,
> + int (*cmp)(const void *, const void *),
> + void (*swap)(void *, void *, int));
extern void sort(...) ?
Alexey
P. S.: Andrew's email ends with ".org".
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 <[email protected]>
Acked-by: Paul Jackson <[email protected]>
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
On Mon, Jan 31, 2005 at 01:52:57PM +0200, Alexey Dobriyan wrote:
> On Mon, 31 Jan 2005 01:34:59 -0600, 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.
>
> > --- /dev/null
> > +++ mm2/include/linux/sort.h
> > @@ -0,0 +1,8 @@
>
> > +void sort(void *base, size_t num, size_t size,
> > + int (*cmp)(const void *, const void *),
> > + void (*swap)(void *, void *, int));
>
> extern void sort(...) ?
Extern is 100% redundant on function declarations.
> P. S.: Andrew's email ends with ".org".
I should not mail off patches just before going to sleep.
--
Mathematics is the supreme nostalgia of our time.
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 <[email protected]>
SUSE Labs, SUSE LINUX GMBH
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 - http://www.grupopie.com
All that is necessary for the triumph of evil is that good men do nothing.
Edmund Burke (1729 - 1797)
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.
Matt Mackall <[email protected]> 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
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 <[email protected]>
SUSE Labs, SUSE LINUX GMBH
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 <[email protected]>
SUSE Labs, SUSE LINUX GMBH
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 <[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.
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 <[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.
>
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.
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.
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?
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
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.
Andreas Gruenbacher <[email protected]> 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
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 <[email protected]>
Zan Lynx <[email protected]> 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~} <[email protected]>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt
Andreas Gruenbacher <[email protected]> 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~} <[email protected]>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt
On Wed, 2005-02-02 at 11:50, Herbert Xu wrote:
> Andreas Gruenbacher <[email protected]> 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 <[email protected]>
SUSE Labs, SUSE LINUX GMBH
>>>>> "AG" == Andreas Gruenbacher <[email protected]> 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));
}
}
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 <[email protected]>
SUSE Labs, SUSE LINUX PRODUCTS GMBH
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.
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 <[email protected]>
SUSE Labs, SUSE LINUX PRODUCTS GMBH
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 <[email protected]>
SUSE Labs, SUSE LINUX PRODUCTS GMBH
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 <[email protected]>
SUSE Labs, SUSE LINUX GMBH
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 <[email protected]>
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;
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.
Matt Mackall <[email protected]> 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.