NFSACL protocol extension for NFSv3

Add a quicksort from glibc as a kernel library function, and switch xfs over to using it. The implementations are equivalent. The nfsacl protocol also requires a sort function, so it makes more sense in the common code.

Signed-off-by Andreas Gruenbacher <[email protected]>

Acked-by Olaf Kirch <[email protected]>

Index: linux-2.6.11-rc2/include/linux/kernel.h
===================================================================

include/linux/kernel.h +2 -0

@@ -93,6 +93,8 @@ extern int sscanf(const char *, const ch
 	__attribute__ ((format (scanf,2,3)));
 extern int vsscanf(const char *, const char *, va_list);
 
+extern void qsort(void *, size_t, size_t, int (*)(const void *,const void *));
+
 extern int get_option(char **str, int *pint);
 extern char *get_options(const char *str, int nints, int *ints);
 extern unsigned long long memparse(char *ptr, char **retptr);

Index: linux-2.6.11-rc2/lib/Kconfig
===================================================================

lib/Kconfig +3 -0

@@ -30,6 +30,9 @@ config LIBCRC32C
 	  require M here.  See Castagnoli93.
 	  Module will be libcrc32c.
 
+config QSORT
+	bool "Quick Sort"
+
 #
 # compression support is select'ed if needed
 #

Index: linux-2.6.11-rc2/lib/Makefile
===================================================================

lib/Makefile +1 -0

@@ -25,6 +25,7 @@ obj-$(CONFIG_CRC_CCITT)	+= crc-ccitt.o
 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/

Index: linux-2.6.11-rc2/lib/qsort.c
===================================================================

lib/qsort.c new file +249 -0

@@ -0,0 +1,249 @@
+/* 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: linux-2.6.11-rc2/fs/xfs/support/qsort.c
===================================================================

fs/xfs/support/qsort.c deleted +0 -155

@@ -1,155 +0,0 @@
-/*
- * Copyright (c) 1992, 1993
- *	The Regents of the University of California.  All rights reserved.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- * 1. Redistributions of source code must retain the above copyright
- *    notice, this list of conditions and the following disclaimer.
- * 2. Redistributions in binary form must reproduce the above copyright
- *    notice, this list of conditions and the following disclaimer in the
- *    documentation and/or other materials provided with the distribution.
- * 3. Neither the name of the University nor the names of its contributors
- *    may be used to endorse or promote products derived from this software
- *    without specific prior written permission.
- *
- * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
- * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
- * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
- * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
- * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
- * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
- * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
- * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
- * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
- * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
- * SUCH DAMAGE.
- */
-
-#include <linux/kernel.h>
-#include <linux/string.h>
-
-/*
- * Qsort routine from Bentley & McIlroy's "Engineering a Sort Function".
- */
-#define swapcode(TYPE, parmi, parmj, n) { 		\
-	long i = (n) / sizeof (TYPE); 			\
-	register TYPE *pi = (TYPE *) (parmi); 		\
-	register TYPE *pj = (TYPE *) (parmj); 		\
-	do { 						\
-		register TYPE	t = *pi;		\
-		*pi++ = *pj;				\
-		*pj++ = t;				\
-        } while (--i > 0);				\
-}
-
-#define SWAPINIT(a, es) swaptype = ((char *)a - (char *)0) % sizeof(long) || \
-	es % sizeof(long) ? 2 : es == sizeof(long)? 0 : 1;
-
-static __inline void
-swapfunc(char *a, char *b, int n, int swaptype)
-{
-	if (swaptype <= 1)
-		swapcode(long, a, b, n)
-	else
-		swapcode(char, a, b, n)
-}
-
-#define swap(a, b)					\
-	if (swaptype == 0) {				\
-		long t = *(long *)(a);			\
-		*(long *)(a) = *(long *)(b);		\
-		*(long *)(b) = t;			\
-	} else						\
-		swapfunc(a, b, es, swaptype)
-
-#define vecswap(a, b, n) 	if ((n) > 0) swapfunc(a, b, n, swaptype)
-
-static __inline char *
-med3(char *a, char *b, char *c, int (*cmp)(const void *, const void *))
-{
-	return cmp(a, b) < 0 ?
-	       (cmp(b, c) < 0 ? b : (cmp(a, c) < 0 ? c : a ))
-              :(cmp(b, c) > 0 ? b : (cmp(a, c) < 0 ? a : c ));
-}
-
-void
-qsort(void *aa, size_t n, size_t es, int (*cmp)(const void *, const void *))
-{
-	char *pa, *pb, *pc, *pd, *pl, *pm, *pn;
-	int d, r, swaptype, swap_cnt;
-	register char *a = aa;
-
-loop:	SWAPINIT(a, es);
-	swap_cnt = 0;
-	if (n < 7) {
-		for (pm = (char *)a + es; pm < (char *) a + n * es; pm += es)
-			for (pl = pm; pl > (char *) a && cmp(pl - es, pl) > 0;
-			     pl -= es)
-				swap(pl, pl - es);
-		return;
-	}
-	pm = (char *)a + (n / 2) * es;
-	if (n > 7) {
-		pl = (char *)a;
-		pn = (char *)a + (n - 1) * es;
-		if (n > 40) {
-			d = (n / 8) * es;
-			pl = med3(pl, pl + d, pl + 2 * d, cmp);
-			pm = med3(pm - d, pm, pm + d, cmp);
-			pn = med3(pn - 2 * d, pn - d, pn, cmp);
-		}
-		pm = med3(pl, pm, pn, cmp);
-	}
-	swap(a, pm);
-	pa = pb = (char *)a + es;
-
-	pc = pd = (char *)a + (n - 1) * es;
-	for (;;) {
-		while (pb <= pc && (r = cmp(pb, a)) <= 0) {
-			if (r == 0) {
-				swap_cnt = 1;
-				swap(pa, pb);
-				pa += es;
-			}
-			pb += es;
-		}
-		while (pb <= pc && (r = cmp(pc, a)) >= 0) {
-			if (r == 0) {
-				swap_cnt = 1;
-				swap(pc, pd);
-				pd -= es;
-			}
-			pc -= es;
-		}
-		if (pb > pc)
-			break;
-		swap(pb, pc);
-		swap_cnt = 1;
-		pb += es;
-		pc -= es;
-	}
-	if (swap_cnt == 0) {  /* Switch to insertion sort */
-		for (pm = (char *) a + es; pm < (char *) a + n * es; pm += es)
-			for (pl = pm; pl > (char *) a && cmp(pl - es, pl) > 0;
-			     pl -= es)
-				swap(pl, pl - es);
-		return;
-	}
-
-	pn = (char *)a + n * es;
-	r = min(pa - (char *)a, pb - pa);
-	vecswap(a, pb - r, r);
-	r = min((long)(pd - pc), (long)(pn - pd - es));
-	vecswap(pb, pn - r, r);
-	if ((r = pb - pa) > es)
-		qsort(a, r / es, es, cmp);
-	if ((r = pd - pc) > es) {
-		/* Iterate rather than recurse to save stack space */
-		a = pn - r;
-		n = r / es;
-		goto loop;
-	}
-/*		qsort(pn - r, r / es, es, cmp);*/
-}

Index: linux-2.6.11-rc2/fs/xfs/Makefile
===================================================================

fs/xfs/Makefile +0 -1

@@ -142,7 +142,6 @@ xfs-y				+= $(addprefix linux-2.6/, \
 xfs-y				+= $(addprefix support/, \
 				   debug.o \
 				   move.o \
-				   qsort.o \
 				   uuid.o)
 
 xfs-$(CONFIG_XFS_TRACE)		+= support/ktrace.o

Index: linux-2.6.11-rc2/fs/xfs/support/qsort.h
===================================================================

fs/xfs/support/qsort.h deleted +0 -41

@@ -1,41 +0,0 @@
-/*
- * Copyright (c) 2000-2002 Silicon Graphics, Inc.  All Rights Reserved.
- *
- * This program is free software; you can redistribute it and/or modify it
- * under the terms of version 2 of the GNU General Public License as
- * published by the Free Software Foundation.
- *
- * This program is distributed in the hope that it would be useful, but
- * WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
- *
- * Further, this software is distributed without any warranty that it is
- * free of the rightful claim of any third person regarding infringement
- * or the like.  Any license provided herein, whether implied or
- * otherwise, applies only to this software file.  Patent licenses, if
- * any, provided herein do not apply to combinations of this program with
- * other software, or any other product whatsoever.
- *
- * You should have received a copy of the GNU General Public License along
- * with this program; if not, write the Free Software Foundation, Inc., 59
- * Temple Place - Suite 330, Boston MA 02111-1307, USA.
- *
- * Contact information: Silicon Graphics, Inc., 1600 Amphitheatre Pkwy,
- * Mountain View, CA  94043, or:
- *
- * http://www.sgi.com
- *
- * For further information regarding this notice, see:
- *
- * http://oss.sgi.com/projects/GenInfo/SGIGPLNoticeExplan/
- */
-
-#ifndef QSORT_H
-#define QSORT_H
-
-extern void qsort (void *const pbase,
-		    size_t total_elems,
-		    size_t size,
-		    int (*cmp)(const void *, const void *));
-
-#endif

Index: linux-2.6.11-rc2/fs/xfs/linux-2.6/xfs_linux.h
===================================================================

fs/xfs/linux-2.6/xfs_linux.h +0 -1

@@ -64,7 +64,6 @@
 #include <sema.h>
 #include <time.h>
 
-#include <support/qsort.h>
 #include <support/ktrace.h>
 #include <support/debug.h>
 #include <support/move.h>

Index: linux-2.6.11-rc2/fs/Kconfig
===================================================================

fs/Kconfig +1 -1

@@ -306,6 +306,7 @@ config FS_POSIX_ACL
 
 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
 
--

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

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

Hi,

I was just reading over the patch, and had a quick question/comment upon the SWAP macro defined below. I think it's possible to do a tiny bit better (better, of course, being subjective), as follows:

#define SWAP(a, b, size)			\
    do {					\
	register size_t __size = (size);	\
	register char * __a = (a), * __b = (b);	\
	do {					\
	    *__a ^= *__b;			\
	    *__b ^= *__a;			\
	    *__a ^= *__b;			\
	    __a++;				\
	    __b++;				\
	} while ((--__size) > 0);		\
    } while (0)

What do you think? :)

AFAIK, XOR is quite expensive on IA32 when compared to simple MOV operatings. Also, since the original patch uses 3 MOVs to perform the swapping, and your version uses 3 XOR operations, I don't see any gains.

Quoted 5 lines · Felipe Alfaro Solana

AFAIK, XOR is quite expensive on IA32 when compared to simple MOV operatings. Also, since the original patch uses 3 MOVs to perform the swapping, and your version uses 3 XOR operations, I don't see any gains.

Both are one cycle latency for register<->register on all x86 cores I've looked at. What makes you think differently?

-Andi (who thinks the glibc qsort is vast overkill for kernel purposes where there are only small data sets and it would be better to use a simpler one optimized for code size)

How about a shell sort? if the data is mostly sorted shell sort beats qsort lots of times, and since the data sets are often small in-kernel, shell sorts O(n^2) behaviour won't harm it too much, shell sort is also faster if the data is already completely sorted. Shell sort is certainly not the simplest algorithm around, but I think (without having done any tests) that it would probably do pretty well for in-kernel use... Then again, I've known to be wrong :)

Quoted 7 lines

How about a shell sort? if the data is mostly sorted shell sort beats qsort lots of times, and since the data sets are often small in-kernel, shell sorts O(n^2) behaviour won't harm it too much, shell sort is also faster if the data is already completely sorted. Shell sort is certainly not the simplest algorithm around, but I think (without having done any tests) that it would probably do pretty well for in-kernel use... Then again, I've known to be wrong :)

I like shell sort for small data sets too. And I agree it would be appropiate for the kernel.

Quoted 8 lines · Andi Kleen

Quoted 7 lines

How about a shell sort? if the data is mostly sorted shell sort beats qsort lots of times, and since the data sets are often small in-kernel, shell sorts O(n^2) behaviour won't harm it too much, shell sort is also faster if the data is already completely sorted. Shell sort is certainly not the simplest algorithm around, but I think (without having done any tests) that it would probably do pretty well for in-kernel use... Then again, I've known to be wrong :)

Quoted 3 lines

I like shell sort for small data sets too. And I agree it would be appropiate for the kernel.

Even with large data sets that are mostly unsorted shell sorts performance is close to qsort, and there's an optimization that gives it O(n^(3/2)) runtime (IIRC),

and another nice property is that it's iterative so it
doesn't eat up stack space (as oposed to qsort which is recursive and eats stack like ****)...

Yeah, I think shell sort would be good for the kernel.

To be precise, one needs ~(log N) of stack space for qsort, and frankly, one should use something like the shell (or should I say Shell?)

sort for sorting
small sets of elements in qsort as well.

On Sun, 23 Jan 2005, Andi Kleen wrote:
Even with large data sets that are mostly unsorted shell sorts performance is close to qsort, and there's an optimization that gives it O(n^(3/2)) runtime (IIRC), and another nice property is that it's iterative so it doesn't eat up stack space (as oposed to qsort which is recursive and eats stack like ****)...

Quoted 9 lines

Quoted 8 lines

How about a shell sort? if the data is mostly sorted shell sort beats qsort lots of times, and since the data sets are often small in-kernel, shell sorts O(n^2) behaviour won't harm it too much, shell sort is also faster if the data is already completely sorted. Shell sort is certainly not the simplest algorithm around, but I think (without having done any tests) that it would probably do pretty well for in-kernel use... Then again, I've known to be wrong :)

Quoted 3 lines

I like shell sort for small data sets too. And I agree it would be appropiate for the kernel.

Even with large data sets that are mostly unsorted shell sorts performance is close to qsort, and there's an optimization that gives it O(n^(3/2)) runtime (IIRC), and another nice property is that it's iterative so it doesn't eat up stack space (as oposed to qsort which is recursive and eats stack like ****)...
Yeah, I think shell sort would be good for the kernel.

In klibc, I use combsort:

/*
* qsort.c
*
* This is actually combsort. It's an O(n log n) algorithm with
* simplicity/small code size being its main virtue. */

#include <stddef.h>
#include <string.h>

static inline size_t newgap(size_t gap)
{
gap = (gap*10)/13;
if ( gap == 9 || gap == 10 )

    gap = 11;

if ( gap < 1 )

    gap = 1;

return gap;
}

void qsort(void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *))
{
size_t gap = nmemb;
size_t i, j;
char *p1, *p2;
int swapped;

  do {
    gap = newgap(gap);
    swapped = 0;

    for ( i = 0, p1 = base ; i < nmemb-gap ; i++, p1 += size ) {
      j = i+gap;
      if ( compar(p1, p2 = (char *)base+j*size) > 0 ) {
        memswap(p1, p2, size);
        swapped = 1;
      }
    }

} while ( gap > 1 || swapped );
}

AFAICS, this is just a badly implemented Shellsort (the 10/13 increment sequence starting with the number of elements is probably not very good, besides swapping stuff is inefficient (just juggling like Shellsort does gives you almost a third less copies)).

Have you found a proof for the O(n log n) claim?

Quoted 7 lines

How about a shell sort? if the data is mostly sorted shell sort beats qsort lots of times, and since the data sets are often small in-kernel, shell sorts O(n^2) behaviour won't harm it too much, shell sort is also faster if the data is already completely sorted. Shell sort is certainly not the simplest algorithm around, but I think (without having done any tests) that it would probably do pretty well for in-kernel use... Then again, I've known to be wrong :)

I like shell sort for small data sets too. And I agree it would be appropiate for the kernel.

FWIW, we already have a Shell sort for the ngroups stuff in kernel/sys.c:groups_sort() that could be made generic.

Quoted 2 lines

FWIW, we already have a Shell sort for the ngroups stuff in kernel/sys.c:groups_sort() that could be made generic.

Sounds like a good plan. Any takers?

It would slow down the groups case (unless we leave the specialized version in). Gcc doesn't inline a cmp function pointer, and a C preprocessor templatized version would be really ugly. A variant with of this routine with qsort like interface should be good enough for nfsacl and xfs though.

group initialization is not time critical, it typically only happens at login. Also it's doubleful you'll even be able to measure the difference.

Quoted 2 lines

group initialization is not time critical, it typically only happens at login. Also it's doubleful you'll even be able to measure the difference.

nfsd updates its group list for every request it processes, so you don't want to make that too slow.

So here's an iconoclastic question or two:

Why can't clients sort the list in userland, before they call down to
the kernel?

Quoted 4 lines

So here's an iconoclastic question or two:

Why can't clients sort the list in userland, before they call down to
the kernel?

Tell that to Sun Microsystems.

ty den 25.01.2005 Klokka 17:53 (+0100) skreiv Andreas Gruenbacher:

Quoted 7 lines · Trond Myklebust

Quoted 4 lines

So here's an iconoclastic question or two:

Why can't clients sort the list in userland, before they call down to
the kernel?

Tell that to Sun Microsystems.

Whatever Sun chooses to do or not do changes nothing to the question of why our client would want to do a quicksort in the kernel.

Quoted 2 lines

Whatever Sun chooses to do or not do changes nothing to the question of why our client would want to do a quicksort in the kernel.

Well, it determines what we must accept, both on the server side and the client side.

ty den 25.01.2005 Klokka 18:16 (+0100) skreiv Andreas Gruenbacher:

Quoted 3 lines

Quoted 2 lines

Whatever Sun chooses to do or not do changes nothing to the question of why our client would want to do a quicksort in the kernel.

Quoted 2 lines

Well, it determines what we must accept, both on the server side and the client side.

I can see why you might want it on the server side, but I repeat: why does the client need to do this in the kernel? The client code should not be overriding the server when it comes to what is acceptable or not acceptable. That's just wrong...

I can also see that if the server _must_ have a sorted list, then doing a sort on the client is a good thing since it will cut down on the work that said server will need to do, and so it will scale better with the number of clients (though note that, conversely, this server will scale poorly with the Sun clients or others if they do not sort the lists).

I'm asking 'cos if the client doesn't need this code, then it seems to me you can move helper routines like the quicksort and posix checking routines into the nfsd module rather than having to keeping it in the VFS (unless you foresee that other modules will want to use the same routines???).

Ah, I see now what you mean. The setxattr syscall only accepts well-formed acls (that is, sorted plus a few other restrictions), and user-space is expected to take care of that. In turn, getxattr returns only well-formed acls. We could lift that guarantee specifically for nfs, but I don't think it would be a good idea.

Entry order in POSIX acls doesn't convey a meaning by the way.

The server must have sorted lists.

ty den 25.01.2005 Klokka 19:12 (+0100) skreiv Andreas Gruenbacher:

Quoted 5 lines

Ah, I see now what you mean. The setxattr syscall only accepts well-formed acls (that is, sorted plus a few other restrictions), and user-space is expected to take care of that. In turn, getxattr returns only well-formed acls. We could lift that guarantee specifically for nfs, but I don't think it would be a good idea.

Note that if you really want to add a qsort to the kernel you might as well drop the setxattr sorting requirement too. If the kernel can qsort for getxattr, then might as well do it for the case of setxattr too.

Quoted 1 line

Entry order in POSIX acls doesn't convey a meaning by the way.

Precisely. Are there really any existing programs out there that are using the raw xattr output and making assumptions about entry order?

Quoted 1 line

The server must have sorted lists.

So, I realize that the on-disk format is already defined, but looking at routines like posix_acl_permission(), it looks like the only order the kernel (at least) actually cares about is that of the "e_tag" field. Unless I missed something, nothing there cares about the order of the "e_id" fields.

Given that you only have 6 possible values there, it seems a shame in hindsight that we didn't choose to just use a 6 bucket hashtable (the value of e_id being the hash value), and leave the order of the e_id fields undefined. 8-(

Quoted 5 lines · Felipe Alfaro Solana

AFAIK, XOR is quite expensive on IA32 when compared to simple MOV operatings. Also, since the original patch uses 3 MOVs to perform the swapping, and your version uses 3 XOR operations, I don't see any gains.

Both are one cycle latency for register<->register on all x86 cores I've looked at. What makes you think differently?

-Andi (who thinks the glibc qsort is vast overkill for kernel purposes where there are only small data sets and it would be better to use a simpler one optimized for code size)

On Sun, Jan 23, 2005 at 03:39:34AM +0100, Andi Kleen wrote:

c) the three-way median selection does help avoid worst-case O(n^2) behavior, which might potentially be triggerable by users in places like XFS where this is used

Quoted 5 lines · Matt Mackall

On Sun, Jan 23, 2005 at 03:39:34AM +0100, Andi Kleen wrote:

c) the three-way median selection does help avoid worst-case O(n^2) behavior, which might potentially be triggerable by users in places like XFS where this is used

XFS's needs are simple - we're just sorting dirents within a single directory block or smaller, and sorting EA lists/ACLs - all of which are small arrays, so a qsort optimised for small arrays suits XFS well.

Take care not to put any arrays on the
stack though, else the CONFIG_4KSTACKS punters won't be happy.

On Sun, Jan 23, 2005 at 03:39:34AM +0100, Andi Kleen wrote:

Quoted 3 lines

-Andi (who thinks the glibc qsort is vast overkill for kernel purposes where there are only small data sets and it would be better to use a simpler one optimized for code size)

Mostly agreed. Except:

a) the glibc version is not actually all that optimized
b) it's nice that it's not recursive
c) the three-way median selection does help avoid worst-case O(n^2) behavior, which might potentially be triggerable by users in places like XFS where this is used

I'll probably whip up a simpler version tomorrow or Monday and do some size/space benchmarking. I've been meaning to contribute a qsort for doubly-linked lists I've got lying around as well.

Quoted 1 line · Matt Mackall

On Sun, Jan 23, 2005 at 03:39:34AM +0100, Andi Kleen wrote:

[...]

Quoted 11 lines

Quoted 3 lines

-Andi (who thinks the glibc qsort is vast overkill for kernel purposes where there are only small data sets and it would be better to use a simpler one optimized for code size)

Mostly agreed. Except:

a) the glibc version is not actually all that optimized
b) it's nice that it's not recursive
c) the three-way median selection does help avoid worst-case O(n^2) behavior, which might potentially be triggerable by users in places like XFS where this is used

Shellsort is much simpler, and not much slower for small datasets. Plus no extra space for stacks.

Quoted 3 lines

I'll probably whip up a simpler version tomorrow or Monday and do some size/space benchmarking. I've been meaning to contribute a qsort for doubly-linked lists I've got lying around as well.

Qsort is OK as long as you have direct access to each element. In case of lists, it is better to just use mergesort.

Quoted 5 lines · Felipe Alfaro Solana

AFAIK, XOR is quite expensive on IA32 when compared to simple MOV operatings. Also, since the original patch uses 3 MOVs to perform the swapping, and your version uses 3 XOR operations, I don't see any gains.

Both are one cycle latency for register<->register on all x86 cores I've looked at. What makes you think differently?

Quoted 7 lines · Andi Kleen

Quoted 5 lines · Felipe Alfaro Solana

AFAIK, XOR is quite expensive on IA32 when compared to simple MOV operatings. Also, since the original patch uses 3 MOVs to perform the swapping, and your version uses 3 XOR operations, I don't see any gains.

Quoted 2 lines

Both are one cycle latency for register<->register on all x86 cores I've looked at. What makes you think differently?

I thought XOR was more expensie. Anyways, I still don't see any advantage in replacing 3 MOVs with 3 XORs.

Quoted 9 lines · Felipe Alfaro Solana

Quoted 7 lines · Andi Kleen

Quoted 5 lines · Felipe Alfaro Solana

AFAIK, XOR is quite expensive on IA32 when compared to simple MOV operatings. Also, since the original patch uses 3 MOVs to perform the swapping, and your version uses 3 XOR operations, I don't see any gains.

Quoted 5 lines

Quoted 2 lines

Both are one cycle latency for register<->register on all x86 cores I've looked at. What makes you think differently?

I thought XOR was more expensie. Anyways, I still don't see any advantage in replacing 3 MOVs with 3 XORs.

Again, no temporaries needed.

But I benched it and it was quite a bit slower.

--
Mathematics is the supreme nostalgia of our time.

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

Quoted 20 lines · vlobanov

Hi,

I was just reading over the patch, and had a quick question/comment upon
the SWAP macro defined below. I think it's possible to do a tiny bit better (better, of course, being subjective), as follows:

#define SWAP(a, b, size)			\
   do {					\
	register size_t __size = (size);	\
	register char * __a = (a), * __b = (b);	\
	do {					\
	    *__a ^= *__b;			\
	    *__b ^= *__a;			\
	    *__a ^= *__b;			\
	    __a++;				\
	    __b++;				\
	} while ((--__size) > 0);		\
   } while (0)

Quoted 1 line

What do you think? :)

AFAIK, XOR is quite expensive on IA32 when compared to simple MOV operatings. Also, since the original patch uses 3 MOVs to perform the swapping, and your version uses 3 XOR operations, I don't see any gains.

Am I missing something?

Quoted 13 lines · vlobanov

#define SWAP(a, b, size)			\
   do {					\
	register size_t __size = (size);	\
	register char * __a = (a), * __b = (b);	\
	do {					\
	    *__a ^= *__b;			\
	    *__b ^= *__a;			\
	    *__a ^= *__b;			\
	    __a++;				\
	    __b++;				\
	} while ((--__size) > 0);		\
   } while (0)

Quoted 1 line

What do you think? :)

AFAIK, XOR is quite expensive on IA32 when compared to simple MOV operatings. Also, since the original patch uses 3 MOVs to perform the swapping, and your version uses 3 XOR operations, I don't see any gains.

#define SWAP(a, b, size)			\
    do {					\
	register size_t __size = (size);	\
	register char * __a = (a), * __b = (b);	\
	do {					\
	    *__a ^= *__b;			\
	    *__b ^= *__a;			\
	    *__a ^= *__b;			\
	    __a++;				\
	    __b++;				\
	} while ((--__size) > 0);		\
    } while (0)

What do you think? :)

since you took the glibc one.. the glibc authors have repeatedly asked if glibc code that goes into the kernel will be export_symbol_gpl only due to their view of the gpl and lgpl

Add a quicksort from glibc as a kernel library function, and switch xfs over to using it. The implementations are equivalent. The nfsacl protocol also requires a sort function, so it makes more sense in the common code.

Quoted 4 lines · Andreas Gruenbacher

Add a quicksort from glibc as a kernel library function, and switch xfs over to using it. The implementations are equivalent. The nfsacl protocol also requires a sort function, so it makes more sense in the common code.

Please update this to kernel formatting standards and try to modernize it a bit.

So the stack is going to be either 256 or 1024 bytes. Seems like we ought to kmalloc it.

Yes, indeed. Though I think even here, we'd prefer to use kmalloc because gcc generates suboptimal code for variable-sized stack vars.

Quoted 2 lines · Matt Mackall

Yes, indeed. Though I think even here, we'd prefer to use kmalloc because gcc generates suboptimal code for variable-sized stack vars.

That's ridiculous. kmalloc isn't even close to whatever suboptimal code gcc might produce here. Also I'm not convinced that gcc generates bad code in the first place. The code I get makes perfect sense.

Signed-off-by Andreas Gruenbacher <[email protected]>

Acked-by Olaf Kirch <[email protected]>

This patch introduces an implementation of qsort to lib/.

Quoted 2 lines · Matt Mackall

This patch introduces an implementation of qsort to lib/.

It screws me over right proper. Can we stick with Andreas's known-working patch for now, and do the sorting stuff as a separate, later activity?

It would involve:

- Removal of the old sort code

- Introduction of the new sort code

- Migration of the NFS ACL code, XFS and group code over to the new implementation.

Here are some benchmarks of cycle count averages for 10 runs on the same random datasets, interrupts disabled. Percentages are performance relative to the glibc algorithm. A bunch of other variants dropped for brevity.

vanlig tekstdokument vedlegg (patches.suse)
The issuer of an RPC call should be able to tell the difference between an I/O error and program unavailable / program version unavailable / procedure unavailable. Return -ENOSYS for unavailable RPCs instead of -EIO.

Only issue a program unavailable warning for program numbers other than the one for nfsacl: Clients with nfsacl support are quite common already; no need to clutter the syslog.

Signed-off-by Andreas Gruenbacher <[email protected]>

Signed-off-by Olaf Kirch <[email protected]>

Index: linux-2.6.11-rc2/include/linux/nfs.h
===================================================================

include/linux/nfs.h +1 -0

@@ -11,6 +11,7 @@
 #include <linux/string.h>
 
 #define NFS_PROGRAM	100003
+#define NFSACL_PROGRAM	100227
 #define NFS_PORT	2049
 #define NFS_MAXDATA	8192
 #define NFS_MAXPATHLEN	1024

Index: linux-2.6.11-rc2/net/sunrpc/clnt.c
===================================================================

net/sunrpc/clnt.c +13 -8

@@ -988,10 +988,12 @@ call_verify(struct rpc_task *task)
 				break;
 			case RPC_MISMATCH:
 				printk(KERN_WARNING "%s: RPC call version mismatch!\n", __FUNCTION__);
-				goto out_eio;
+				error = -ENOSYS;
+				goto out_err;
 			default:
 				printk(KERN_WARNING "%s: RPC call rejected, unknown error: %x\n", __FUNCTION__, n);
-				goto out_eio;
+				error = -ENOSYS;
+				goto out_err;
 		}
 		if (--len < 0)
 			goto out_overflow;

@@ -1041,23 +1043,28 @@ call_verify(struct rpc_task *task)
 	case RPC_SUCCESS:
 		return p;
 	case RPC_PROG_UNAVAIL:
-		printk(KERN_WARNING "RPC: call_verify: program %u is unsupported by server %s\n",
+		if (task->tk_client->cl_prog != NFSACL_PROGRAM) {
+			printk(KERN_WARNING "RPC: call_verify: program %u is unsupported by server %s\n",
 				(unsigned int)task->tk_client->cl_prog,
 				task->tk_client->cl_server);
-		goto out_eio;
+		}
+		error = -ENOSYS;
+		goto out_err;
 	case RPC_PROG_MISMATCH:
 		printk(KERN_WARNING "RPC: call_verify: program %u, version %u unsupported by server %s\n",
 				(unsigned int)task->tk_client->cl_prog,
 				(unsigned int)task->tk_client->cl_vers,
 				task->tk_client->cl_server);
-		goto out_eio;
+		error = -ENOSYS;
+		goto out_err;
 	case RPC_PROC_UNAVAIL:
 		printk(KERN_WARNING "RPC: call_verify: proc %p unsupported by program %u, version %u on server %s\n",
 				task->tk_msg.rpc_proc,
 				task->tk_client->cl_prog,
 				task->tk_client->cl_vers,
 				task->tk_client->cl_server);
-		goto out_eio;
+		error = -ENOSYS;
+		goto out_err;
 	case RPC_GARBAGE_ARGS:
 		dprintk("RPC: %4d %s: server saw garbage\n", task->tk_pid, __FUNCTION__);
 		break;			/* retry */

@@ -1075,7 +1082,6 @@ out_retry:
 		return NULL;
 	}
 	printk(KERN_WARNING "RPC %s: retry failed, exit EIO\n", __FUNCTION__);
-out_eio:
 	error = -EIO;
 out_err:
 	rpc_exit(task, error);
 
--

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

No hacks in sunrpc, please: i.e. get rid of that NFSACL_PROGRAM exception...
If you want to kill those warnings, please just convert them to dprintks().

Also, why are you converting "unknown error" into ENOSYS?

Finally, it might make sense to distinguish between "program" and "procedure" errors. How about converting that RPC_PROC_UNAVAIL error into EOPNOTSUPP (like we already do in the NFS layer itself).

vanlig tekstdokument vedlegg (patches.suse)
Add xdr_encode_array2 and xdr_decode_array2 functions for encoding end decoding arrays with arbitrary entries, such as acl entries. The goal here is to do this without allocating a contiguous temporary buffer.

lau den 22.01.2005 Klokka 21:34 (+0100) skreiv Andreas Gruenbacher:

Quoted 5 lines

vanlig tekstdokument vedlegg (patches.suse)
Add xdr_encode_array2 and xdr_decode_array2 functions for encoding end decoding arrays with arbitrary entries, such as acl entries. The goal here is to do this without allocating a contiguous temporary buffer.

net/sunrpc/xdr.c:1024:3: warning: mixing declarations and code net/sunrpc/xdr.c:967:16: warning: bad constant expression

Please don't use these gcc extensions in the kernel.

net/sunrpc/xdr.c:1024:3: warning: mixing declarations and code
...
Please don't use these gcc extensions in the kernel.

Cheers,
Trond

vanlig tekstdokument vedlegg (patches.suse)
With the noacl mount option, nfs clients stop using the ACCESS RPC which they usually use to get an access decision from the server. Instead, they make the decision based on the file ownership and file mode permission bits.

lau den 22.01.2005 Klokka 21:34 (+0100) skreiv Andreas Gruenbacher:

Quoted 5 lines

vanlig tekstdokument vedlegg (patches.suse)
With the noacl mount option, nfs clients stop using the ACCESS RPC which they usually use to get an access decision from the server. Instead, they make the decision based on the file ownership and file mode permission bits.

I still hate that name "noacl".

Solaris nfsacl workaround

lau den 22.01.2005 Klokka 21:34 (+0100) skreiv Andreas Gruenbacher:

Quoted 1 line

Solaris nfsacl workaround

NACK. No hacks.

That's the second time I see you refusing an interoperability patch without bothering to say what would be acceptable. Do we need a fork between knfsd-pure and knfsd-actually-works-in-the-real-world or what?

ty den 15.02.2005 Klokka 21:35 (+0100) skreiv Olivier Galibert:

Quoted 3 lines

That's the second time I see you refusing an interoperability patch without bothering to say what would be acceptable. Do we need a fork between knfsd-pure and knfsd-actually-works-in-the-real-world or what?

You appear to be under the misguided impression that if a patch is reviewed, and rejected, then somehow the responsibility for resolving your problem (and cleaning up the code) falls to the reviewer.

I'm not aware of any such rule.

Resolving the problem and/or cleaning the code, no. Telling what kind of patch would be acceptable is your responsability, yes.

on den 16.02.2005 Klokka 00:02 (+0100) skreiv Olivier Galibert:

Quoted 2 lines

Resolving the problem and/or cleaning the code, no. Telling what kind of patch would be acceptable is your responsability, yes.

Read the patch, read the earlier patch [2/13] in which the same hack appeared in the client code, and see my response. I'm sure Andreas knows exactly what was meant by the comment and why.

lau den 22.01.2005 Klokka 21:34 (+0100) skreiv Andreas Gruenbacher:

Quoted 1 line

Solaris nfsacl workaround

NACK. No hacks.

Quoted 4 lines

lau den 22.01.2005 Klokka 21:34 (+0100) skreiv Andreas Gruenbacher:

Quoted 1 line

Solaris nfsacl workaround

NACK. No hacks.

Well, I'm not in the position to fix Solaris. It would be possible to implement NFSACL for NFSv2 (Solaris has it), but I doubt that we need it. Your NACK probably means we'll have to carry it around as a vendor patch.

I am, however, surprised when you say that Solaris has problems with this. The PROG_MISMATCH error does also tell the client the minimum and maximum supported version, so if all is working well, then it recognize that we support version 3 only. It seems wierd that they should then choose to treat that as an mount failure.

vanlig tekstdokument vedlegg (patches.suse)
This adds acl support fo nfs clients via the NFSACL protocol extension, by implementing the getxattr, listxattr, setxattr, and removexattr iops for the system.posix_acl_access and system.posix_acl_default attributes. This patch implements a dumb version that uses no caching (and thus adds some overhead). (Another patch in this patchset adds caching as well.)

I suggest you rather do the same thing we're doing for the NFSv4 acls, and provide an nfsv3-specific struct inode_operations that points to nfsv3-specific {get,set,list}xattr functions.

Quoted 3 lines

I suggest you rather do the same thing we're doing for the NFSv4 acls, and provide an nfsv3-specific struct inode_operations that points to nfsv3-specific {get,set,list}xattr functions.

Okay, that requires iops for file, dir, and others. How about the attached patch?