qsort_r

[David Holland]

(Cc: tech-kern because of kheapsort())

My irritation with not being able to pass a data pointer through
qsort() boiled over just now. Apparently Linux and/or GNU has a
qsort_r() that supports this; so, following is a patch that gives us
a compatible qsort_r() plus mergesort_r(), and heapsort_r().

I have done it by having the original, non-_r functions provide a
thunk for the comparison function, as this is least invasive. If we
think this is too expensive, an alternative is generating a union of
function pointers and making tests at the call sites; another option
is to duplicate the code (hopefully with cpp rather than C&P) but that
seems like a bad plan. Note that the thunks use an extra struct to
hold the function pointer; this is to satisfy C standards pedantry
about void pointers vs. function pointers, and if we decide not to
care it could be simplified.

This patch was supposed to have all the necessary support widgetry,
like namespace.h changes, but there's at least one more thing not in
it: MLINKS for the new functions and corresponding setlist
changes. If I've forgotten anything else, let me know.

heapsort() is used in one place in the kernel as kheapsort(), which
takes an extra argument so that the heapsort code itself doesn't have
to know how to malloc in the kernel. I have done the following:
- add kheapsort_r()
- change the signature of plain kheapsort() to move the extra
argument to a place it is less likely to cause confusion with the
userdata argument;
- update the caller for the signature change;
but I have not changed the caller to call kheapsort_r instead. Based
on the code, this should probably be done later as like many sort
calls it's using a global for context. At this point the plain
kheapsort can be removed.

------

Index: include/stdlib.h
===================================================================
RCS file: /cvsroot/src/include/stdlib.h,v
retrieving revision 1.106
diff -u -p -r1.106 stdlib.h
--- include/stdlib.h 26 Apr 2013 18:07:43 -0000 1.106
+++ include/stdlib.h 8 Dec 2013 22:13:22 -0000
@@ -299,9 +299,16 @@ int getenv_r(const char *, char *, size

void cfree(void *);

-int heapsort(void *, size_t, size_t, int (*)(const void *, const void *));
+int heapsort(void *, size_t, size_t,
+ int (*)(const void *, const void *));
+int heapsort_r(void *, size_t, size_t,
+ int (*)(const void *, const void *, void *), void *);
int mergesort(void *, size_t, size_t,
int (*)(const void *, const void *));
+int mergesort_r(void *, size_t, size_t,
+ int (*)(const void *, const void *, void *), void *);
+void qsort_r(void *, size_t, size_t,
+ int (*)(const void *, const void *, void *), void *);
int radixsort(const unsigned char **, int, const unsigned char *,
unsigned);
int sradixsort(const unsigned char **, int, const unsigned char *,
Index: common/lib/libc/stdlib/heapsort.c
===================================================================
RCS file: /cvsroot/src/common/lib/libc/stdlib/heapsort.c,v
retrieving revision 1.3
diff -u -p -r1.3 heapsort.c
--- common/lib/libc/stdlib/heapsort.c 17 Nov 2008 10:21:30 -0000 1.3
+++ common/lib/libc/stdlib/heapsort.c 8 Dec 2013 22:13:23 -0000
@@ -69,6 +69,7 @@ __RCSID("$NetBSD: heapsort.c,v 1.3 2008/

#ifdef __weak_alias
__weak_alias(heapsort,_heapsort)
+__weak_alias(heapsort_r,_heapsort_r)
#endif
#endif /* _KERNEL || _STANDALONE */

@@ -109,12 +110,12 @@ __weak_alias(heapsort,_heapsort)
for (par_i = initval; (child_i = par_i * 2) <= nmemb; \
par_i = child_i) { \
child = base + child_i * size; \
- if (child_i < nmemb && compar(child, child + size) < 0) { \
+ if (child_i < nmemb && compar(child, child + size, data) < 0) {\
child += size; \
++child_i; \
} \
par = base + par_i * size; \
- if (compar(child, par) <= 0) \
+ if (compar(child, par, data) <= 0) \
break; \
SWAP(par, child, count, size, tmp); \
} \
@@ -140,7 +141,7 @@ __weak_alias(heapsort,_heapsort)
#define SELECT(par_i, child_i, nmemb, par, child, size, k, count, tmp1, tmp2) { \
for (par_i = 1; (child_i = par_i * 2) <= nmemb; par_i = child_i) { \
child = base + child_i * size; \
- if (child_i < nmemb && compar(child, child + size) < 0) { \
+ if (child_i < nmemb && compar(child, child + size, data) < 0) {\
child += size; \
++child_i; \
} \
@@ -152,7 +153,7 @@ __weak_alias(heapsort,_heapsort)
par_i = child_i / 2; \
child = base + child_i * size; \
par = base + par_i * size; \
- if (child_i == 1 || compar(k, par) < 0) { \
+ if (child_i == 1 || compar(k, par, data) < 0) { \
COPY(child, k, count, size, tmp1, tmp2); \
break; \
} \
@@ -169,12 +170,12 @@ __weak_alias(heapsort,_heapsort)
*/
#if defined(_KERNEL) || defined(_STANDALONE)
int
-kheapsort(void *vbase, size_t nmemb, size_t size,
- int (*compar)(const void *, const void *), void *k)
+kheapsort_r(void *vbase, size_t nmemb, size_t size, void *k,
+ int (*compar)(const void *, const void *, void *), void *data)
#else
int
-heapsort(void *vbase, size_t nmemb, size_t size,
- int (*compar)(const void *, const void *))
+heapsort_r(void *vbase, size_t nmemb, size_t size,
+ int (*compar)(const void *, const void *, void *), void *data)
#endif
{
size_t cnt, i, j, l;
@@ -227,3 +228,40 @@ heapsort(void *vbase, size_t nmemb, size
#endif
return (0);
}
+
+////////////////////////////////////////////////////////////
+// original heapsort()
+
+struct __heapsort {
+ int (*cmp)(const void *, const void *);
+};
+
+static int
+__heapsort_cmp(const void *a, const void *b, void *data)
+{
+ struct __heapsort *hs = data;
+
+ return hs->cmp(a, b);
+}
+
+#if defined(_KERNEL) || defined(_STANDALONE)
+int
+kheapsort(void *vbase, size_t nmemb, size_t size, void *k,
+ int (*compar)(const void *, const void *))
+{
+ struct __heapsort hs;
+
+ hs.cmp = compar;
+ return kheapsort_r(vbase, nmemb, size, k, __heapsort_cmp, &hs);
+}
+#else
+int
+heapsort(void *vbase, size_t nmemb, size_t size,
+ int (*compar)(const void *, const void *))
+{
+ struct __heapsort hs;
+
+ hs.cmp = compar;
+ return heapsort_r(vbase, nmemb, size, __heapsort_cmp, &hs);
+}
+#endif
Index: sys/kern/kern_ksyms.c
===================================================================
RCS file: /cvsroot/src/sys/kern/kern_ksyms.c,v
retrieving revision 1.70
diff -u -p -r1.70 kern_ksyms.c
--- sys/kern/kern_ksyms.c 7 Apr 2013 00:49:45 -0000 1.70
+++ sys/kern/kern_ksyms.c 8 Dec 2013 22:13:23 -0000
@@ -385,7 +385,7 @@ addsymtab(const char *name, void *symsta
tab->sd_symsize = n * sizeof(Elf_Sym);
tab->sd_nglob = nglob;
addsymtab_strstart = str;
- if (kheapsort(nsym, n, sizeof(Elf_Sym), addsymtab_compar, &ts) != 0)
+ if (kheapsort(nsym, n, sizeof(Elf_Sym), &ts, addsymtab_compar) != 0)
panic("addsymtab");

#ifdef KDTRACE_HOOKS
Index: lib/libc/include/namespace.h
===================================================================
RCS file: /cvsroot/src/lib/libc/include/namespace.h,v
retrieving revision 1.169
diff -u -p -r1.169 namespace.h
--- lib/libc/include/namespace.h 28 Aug 2013 17:47:07 -0000 1.169
+++ lib/libc/include/namespace.h 8 Dec 2013 22:13:31 -0000
@@ -387,6 +387,7 @@
#define gmtime_r _gmtime_r
#define group_from_gid _group_from_gid
#define heapsort _heapsort
+#define heapsort_r _heapsort_r
#define herror _herror
#define hes_error _hes_error
#define hes_free _hes_free
@@ -467,6 +468,7 @@
#define lseek _lseek
#define membar_producer _membar_producer
#define mergesort _mergesort
+#define mergesort_r _mergesort_r
#define mi_vector_hash _mi_vector_hash
#define mkstemp _mkstemp
#define mktime_z _mktime_z
@@ -527,6 +529,7 @@
#define pwrite _pwrite
#define qabs _qabs
#define qdiv _qdiv
+#define qsort_r _qsort_r
#define radixsort _radixsort
#define random _random
#define randomid _randomid
Index: lib/libc/stdlib/merge.c
===================================================================
RCS file: /cvsroot/src/lib/libc/stdlib/merge.c,v
retrieving revision 1.14
diff -u -p -r1.14 merge.c
--- lib/libc/stdlib/merge.c 13 Mar 2012 21:13:48 -0000 1.14
+++ lib/libc/stdlib/merge.c 8 Dec 2013 22:13:32 -0000
@@ -65,12 +65,13 @@ __RCSID("$NetBSD: merge.c,v 1.14 2012/03

#ifdef __weak_alias
__weak_alias(mergesort,_mergesort)
+__weak_alias(mergesort_r,_mergesort_r)
#endif

static void setup(u_char *, u_char *, size_t, size_t,
- int (*)(const void *, const void *));
+ int (*)(const void *, const void *, void *), void *);
static void insertionsort(u_char *, size_t, size_t,
- int (*)(const void *, const void *));
+ int (*)(const void *, const void *, void *), void *);

#define ISIZE sizeof(int)
#define PSIZE sizeof(u_char *)
@@ -108,8 +109,8 @@ static void insertionsort(u_char *, size
* Arguments are as for qsort.
*/
int
-mergesort(void *base, size_t nmemb, size_t size,
- int (*cmp)(const void *, const void *))
+mergesort_r(void *base, size_t nmemb, size_t size,
+ int (*cmp)(const void *, const void *, void *), void *data)
{
size_t i;
int sense;
@@ -137,7 +138,7 @@ mergesort(void *base, size_t nmemb, size
return (-1);

list1 = base;
- setup(list1, list2, nmemb, size, cmp);
+ setup(list1, list2, nmemb, size, cmp, data);
last = list2 + nmemb * size;
i = big = 0;
while (*EVAL(list2) != last) {
@@ -151,7 +152,7 @@ mergesort(void *base, size_t nmemb, size
p2 = *EVAL(p2);
l2 = list1 + (p2 - list2);
while (f1 < l1 && f2 < l2) {
- if ((*cmp)(f1, f2) <= 0) {
+ if ((*cmp)(f1, f2, data) <= 0) {
q = f2;
b = f1, t = l1;
sense = -1;
@@ -164,7 +165,7 @@ mergesort(void *base, size_t nmemb, size
#if 0
LINEAR:
#endif
- while ((b += size) < t && cmp(q, b) >sense)
+ while ((b += size) < t && cmp(q, b, data)>sense)
if (++i == 6) {
big = 1;
goto EXPONENTIAL;
@@ -173,12 +174,12 @@ LINEAR:
EXPONENTIAL: for (i = size; ; i <<= 1)
if ((p = (b + i)) >= t) {
if ((p = t - size) > b &&
- (*cmp)(q, p) <= sense)
+ (*cmp)(q, p, data) <= sense)
t = p;
else
b = p;
break;
- } else if ((*cmp)(q, p) <= sense) {
+ } else if ((*cmp)(q, p, data) <= sense) {
t = p;
if (i == size)
big = 0;
@@ -190,7 +191,7 @@ SLOWCASE:
#endif
while (t > b+size) {
i = (((t - b) / size) >> 1) * size;
- if ((*cmp)(q, p = b + i) <= sense)
+ if ((*cmp)(q, p = b + i, data) <= sense)
t = p;
else
b = p;
@@ -199,7 +200,8 @@ SLOWCASE:
FASTCASE: while (i > size)
if ((*cmp)(q,
p = b +
- (i = (unsigned int) i >> 1)) <= sense)
+ (i = (unsigned int) i >> 1),
+ data) <= sense)
t = p;
else
b = p;
@@ -279,7 +281,7 @@ COPY: b = t;
/* XXX: shouldn't this function be static? - lukem 990810 */
void
setup(u_char *list1, u_char *list2, size_t n, size_t size,
- int (*cmp)(const void *, const void *))
+ int (*cmp)(const void *, const void *, void *), void *data)
{
int length, tmp, sense;
u_char *f1, *f2, *s, *l2, *last, *p2;
@@ -291,7 +293,7 @@ setup(u_char *list1, u_char *list2, size

size2 = size*2;
if (n <= 5) {
- insertionsort(list1, n, size, cmp);
+ insertionsort(list1, n, size, cmp, data);
*EVAL(list2) = list2 + n*size;
return;
}
@@ -300,19 +302,19 @@ setup(u_char *list1, u_char *list2, size
* for simplicity.
*/
i = 4 + (n & 1);
- insertionsort(list1 + (n - i) * size, i, size, cmp);
+ insertionsort(list1 + (n - i) * size, i, size, cmp, data);
last = list1 + size * (n - i);
*EVAL(list2 + (last - list1)) = list2 + n * size;

#ifdef NATURAL
p2 = list2;
f1 = list1;
- sense = (cmp(f1, f1 + size) > 0);
+ sense = (cmp(f1, f1 + size, data) > 0);
for (; f1 < last; sense = !sense) {
length = 2;
/* Find pairs with same sense. */
for (f2 = f1 + size2; f2 < last; f2 += size2) {
- if ((cmp(f2, f2+ size) > 0) != sense)
+ if ((cmp(f2, f2 + size, data) > 0) != sense)
break;
length += 2;
}
@@ -325,7 +327,7 @@ setup(u_char *list1, u_char *list2, size
} else { /* Natural merge */
l2 = f2;
for (f2 = f1 + size2; f2 < l2; f2 += size2) {
- if ((cmp(f2-size, f2) > 0) != sense) {
+ if ((cmp(f2-size, f2, data) > 0) != sense) {
p2 = *EVAL(p2) = f2 - list1 + list2;
if (sense > 0)
reverse(f1, f2 - size);
@@ -335,7 +337,7 @@ setup(u_char *list1, u_char *list2, size
if (sense > 0)
reverse(f1, f2 - size);
f1 = f2;
- if (f2 < last || cmp(f2 - size, f2) > 0)
+ if (f2 < last || cmp(f2 - size, f2, data) > 0)
p2 = *EVAL(p2) = f2 - list1 + list2;
else
p2 = *EVAL(p2) = list2 + n*size;
@@ -344,7 +346,7 @@ setup(u_char *list1, u_char *list2, size
#else /* pairwise merge only. */
for (f1 = list1, p2 = list2; f1 < last; f1 += size2) {
p2 = *EVAL(p2) = p2 + size2;
- if (cmp (f1, f1 + size) > 0)
+ if (cmp (f1, f1 + size, data) > 0)
swap(f1, f1 + size);
}
#endif /* NATURAL */
@@ -356,7 +358,7 @@ setup(u_char *list1, u_char *list2, size
*/
static void
insertionsort(u_char *a, size_t n, size_t size,
- int (*cmp)(const void *, const void *))
+ int (*cmp)(const void *, const void *, void *), void *data)
{
u_char *ai, *s, *t, *u, tmp;
size_t i;
@@ -367,8 +369,33 @@ insertionsort(u_char *a, size_t n, size_
for (ai = a+size; --n >= 1; ai += size)
for (t = ai; t > a; t -= size) {
u = t - size;
- if (cmp(u, t) <= 0)
+ if (cmp(u, t, data) <= 0)
break;
swap(u, t);
}
}
+
+////////////////////////////////////////////////////////////
+// original mergesort()
+
+struct __mergesort {
+ int (*cmp)(const void *, const void *);
+};
+
+static int
+__mergesort_cmp(const void *a, const void *b, void *data)
+{
+ struct __mergesort *ms = data;
+
+ return ms->cmp(a, b);
+}
+
+int
+mergesort(void *base, size_t nmemb, size_t size,
+ int (*cmp)(const void *, const void *))
+{
+ struct __mergesort ms;
+
+ ms.cmp = cmp;
+ return mergesort_r(base, nmemb, size, __mergesort_cmp, &ms);
+}
Index: lib/libc/stdlib/qsort.3
===================================================================
RCS file: /cvsroot/src/lib/libc/stdlib/qsort.3,v
retrieving revision 1.13
diff -u -p -r1.13 qsort.3
--- lib/libc/stdlib/qsort.3 7 Aug 2003 16:43:42 -0000 1.13
+++ lib/libc/stdlib/qsort.3 8 Dec 2013 22:13:33 -0000
@@ -33,13 +33,16 @@
.\"
.\" from: @(#)qsort.3 8.1 (Berkeley) 6/4/93
.\"
-.Dd June 4, 1993
+.Dd December 8, 2013
.Dt QSORT 3
.Os
.Sh NAME
.Nm qsort ,
.Nm heapsort ,
-.Nm mergesort
+.Nm mergesort ,
+.Nm qsort_r ,
+.Nm heapsort_r ,
+.Nm mergesort_r
.Nd sort functions
.Sh LIBRARY
.Lb libc
@@ -51,6 +54,11 @@
.Fn heapsort "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *)"
.Ft int
.Fn mergesort "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *)"
+.Ft void
+.Fn qsort_r "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *, void *)" "void *userdata"
+.Fn heapsort_r "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *, void *)" "void *userdata"
+.Ft int
+.Fn mergesort_r "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *, void *)" "void *userdata"
.Sh DESCRIPTION
The
.Fn qsort
@@ -147,24 +155,47 @@ is faster than
.Fn heapsort .
Memory availability and pre-existing order in the data can make this
untrue.
+.Pp
+The
+.Fn qsort_r ,
+.Fn heapsort_r ,
+and
+.Fn mergesort_r
+functions are the same as
+.Fn qsort ,
+.Fn heapsort ,
+and
+.Fn mergesort
+respectively except that they accept an additional argument
+.Fa userdata
+which is passed through as an additional argument (the third and last)
+of the comparison function.
.Sh RETURN VALUES
The
.Fn qsort
-function
-returns no value.
+and
+.Fn qsort_r
+functions
+return no value.
.Pp
Upon successful completion,
-.Fn heapsort
-and
+.Fn heapsort ,
.Fn mergesort
+.Fn heapsort_r ,
+and
+.Fn mergesort_r
return 0.
Otherwise, they return \-1 and the global variable
.Va errno
is set to indicate the error.
.Sh ERRORS
The
-.Fn heapsort
-function succeeds unless:
+.Fn heapsort ,
+.Fn mergesort
+.Fn heapsort_r ,
+and
+.Fn heapsort_r
+functions succeed unless:
.Bl -tag -width Er
.It Bq Er EINVAL
The
@@ -174,6 +205,8 @@ the
.Fa size
argument to
.Fn mergesort
+or
+.Fn mergesort_r
is less than
.Dq "sizeof(void *) / 2" .
.It Bq Er ENOMEM
@@ -236,3 +269,11 @@ The
function
conforms to
.St -ansiC .
+.Sh HISTORY
+The
+.Fn qsort_r ,
+.Fn heapsort_r ,
+and
+.Fn mergesort_r
+functions were added in
+.Nx 7.0 .
Index: lib/libc/stdlib/qsort.c
===================================================================
RCS file: /cvsroot/src/lib/libc/stdlib/qsort.c,v
retrieving revision 1.22
diff -u -p -r1.22 qsort.c
--- lib/libc/stdlib/qsort.c 26 May 2012 21:47:05 -0000 1.22
+++ lib/libc/stdlib/qsort.c 8 Dec 2013 22:13:33 -0000
@@ -44,8 +44,15 @@ __RCSID("$NetBSD: qsort.c,v 1.22 2012/05
#include <errno.h>
#include <stdlib.h>

+#ifdef __weak_alias
+__weak_alias(qsort_r,_qsort_r)
+#endif
+
+////////////////////////////////////////////////////////////
+// qsort_r
+
static inline char *med3(char *, char *, char *,
- int (*)(const void *, const void *));
+ int (*)(const void *, const void *, void *), void *);
static inline void swapfunc(char *, char *, size_t, int);

#define min(a, b) (a) < (b) ? a : b
@@ -89,17 +96,17 @@ swapfunc(char *a, char *b, size_t n, int

static inline char *
med3(char *a, char *b, char *c,
- int (*cmp)(const void *, const void *))
+ int (*cmp)(const void *, const void *, void *), void *data)
{

- 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 ));
+ return cmp(a, b, data) < 0 ?
+ (cmp(b, c, data) < 0 ? b : (cmp(a, c, data) < 0 ? c : a ))
+ :(cmp(b, c, data) > 0 ? b : (cmp(a, c, data) < 0 ? a : c ));
}

void
-qsort(void *a, size_t n, size_t es,
- int (*cmp)(const void *, const void *))
+qsort_r(void *a, size_t n, size_t es,
+ int (*cmp)(const void *, const void *, void *), void *data)
{
char *pa, *pb, *pc, *pd, *pl, *pm, *pn;
size_t d, r;
@@ -111,7 +118,8 @@ qsort(void *a, size_t n, size_t es,
loop: SWAPINIT(a, es);
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;
+ for (pl = pm;
+ pl > (char *) a && cmp(pl - es, pl, data) > 0;
pl -= es)
swap(pl, pl - es);
return;
@@ -122,25 +130,25 @@ loop: SWAPINIT(a, es);
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);
+ pl = med3(pl, pl + d, pl + 2 * d, cmp, data);
+ pm = med3(pm - d, pm, pm + d, cmp, data);
+ pn = med3(pn - 2 * d, pn - d, pn, cmp, data);
}
- pm = med3(pl, pm, pn, cmp);
+ pm = med3(pl, pm, pn, cmp, data);
}
swap(a, pm);
pa = pb = (char *) a + es;

pc = pd = (char *) a + (n - 1) * es;
for (;;) {
- while (pb <= pc && (cmp_result = cmp(pb, a)) <= 0) {
+ while (pb <= pc && (cmp_result = cmp(pb, a, data)) <= 0) {
if (cmp_result == 0) {
swap(pa, pb);
pa += es;
}
pb += es;
}
- while (pb <= pc && (cmp_result = cmp(pc, a)) >= 0) {
+ while (pb <= pc && (cmp_result = cmp(pc, a, data)) >= 0) {
if (cmp_result == 0) {
swap(pc, pd);
pd -= es;
@@ -160,12 +168,37 @@ loop: SWAPINIT(a, es);
r = min((size_t)(pd - pc), pn - pd - es);
vecswap(pb, pn - r, r);
if ((r = pb - pa) > es)
- qsort(a, r / es, es, cmp);
+ qsort_r(a, r / es, es, cmp, data);
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);*/
+/* qsort_r(pn - r, r / es, es, cmp);*/
+}
+
+////////////////////////////////////////////////////////////
+// original qsort()
+
+struct __qsort {
+ int (*cmp)(const void *, const void *);
+};
+
+static int
+__qsort_cmp(const void *a, const void *b, void *data)
+{
+ struct __qsort *qs = data;
+
+ return qs->cmp(a, b);
+}
+
+void
+qsort(void *a, size_t n, size_t es,
+ int (*cmp)(const void *, const void *))
+{
+ struct __qsort qs;
+
+ qs.cmp = cmp;
+ qsort_r(a, n, es, __qsort_cmp, &qs);
}
Index: sys/lib/libkern/libkern.h
===================================================================
RCS file: /cvsroot/src/sys/lib/libkern/libkern.h,v
retrieving revision 1.108
diff -u -p -r1.108 libkern.h
--- sys/lib/libkern/libkern.h 28 Aug 2013 16:20:38 -0000 1.108
+++ sys/lib/libkern/libkern.h 8 Dec 2013 22:13:33 -0000
@@ -337,8 +337,10 @@ unsigned long long strtoull(const char *
uintmax_t strtoumax(const char *, char **, int);
int snprintb(char *, size_t, const char *, uint64_t);
int snprintb_m(char *, size_t, const char *, uint64_t, size_t);
-int kheapsort(void *, size_t, size_t, int (*)(const void *, const void *),
- void *);
+int kheapsort(void *, size_t, size_t, void *,
+ int (*)(const void *, const void *));
+int kheapsort_r(void *, size_t, size_t, void *,
+ int (*)(const void *, const void *, void *), void *);
uint32_t crc32(uint32_t, const uint8_t *, size_t);
unsigned int popcount(unsigned int) __constfunc;
unsigned int popcountl(unsigned long) __constfunc;

[Joerg Sonnenberger]

Post by David Holland
I have done it by having the original, non-_r functions provide a
thunk for the comparison function, as this is least invasive. If we
think this is too expensive, an alternative is generating a union of
function pointers and making tests at the call sites; another option
is to duplicate the code (hopefully with cpp rather than C&P) but that
seems like a bad plan.

I'd prefer to not have another indirect call. The only difference
is the definition and expanding a CMP macro differently?

Joerg

[David Holland]

Post by Joerg Sonnenberger

Post by David Holland
I have done it by having the original, non-_r functions provide a
thunk for the comparison function, as this is least invasive. If we
think this is too expensive, an alternative is generating a union of
function pointers and making tests at the call sites; another option
is to duplicate the code (hopefully with cpp rather than C&P) but that
seems like a bad plan.

I'd prefer to not have another indirect call. The only difference
is the definition and expanding a CMP macro differently?

Yes. But I'd rather not duplicate the code...

[David Holland]

Post by David Holland

Post by Joerg Sonnenberger

Post by David Holland
I have done it by having the original, non-_r functions provide a
thunk for the comparison function, as this is least invasive. If we
think this is too expensive, an alternative is generating a union of
function pointers and making tests at the call sites; another option
is to duplicate the code (hopefully with cpp rather than C&P) but that
seems like a bad plan.

I'd prefer to not have another indirect call. The only difference
is the definition and expanding a CMP macro differently?

Yes. But I'd rather not duplicate the code...

So, to ground this a bit, the realistic options are:

starting from this (various details elided):

void
sort(void *p, size_t n, size_t sz, int (*cmp)(const void *, const void *))
{
...
r = cmp(a, b);
...
}


(1) thunks [what's in my current patch]

void
sort_r(void *p, size_t n, size_t sz,
int (*cmp)(const void *, const void *, void *), void *data)
{
...
r = cmp(a, b, data);
...
}

struct sort {
int (*cmp)(const void *, const void *);
};

static int
thunk(const void *a, const void *b, void *data)
{
return ((struct sort *)data)->cmp(a, b)
}

void
sort(void *p, size_t n, size_t sz, int (*cmp)(const void *, const void *))
{
struct sort x = { .cmp = cmp };
sort_r(p, n, sz, thunk, &x);
}

pros:
+ already written
+ noninvasive
+ reasonably tidy
+ does not duplicate the output code
cons:
- extra indirect calls


(2) union of function pointers

union sort {
int (*cmp)(const void *, const void *);
int (*cmp_r)(const void *, const void *, void *);
};

static void
sort_internal(void *p, size_t n, size_t sz, bool is_r, union sort cmpu,
void *data)
{
...
r = is_r ? cmpu.cmp(a, b) : cmpu.cmp_r(a, b, data);
...
}

void
sort(void *p, size_t n, size_t sz, int (*cmp)(const void *, const void *))
{
union sort cmpu = { .cmp = cmp };
sort_internal(p, n, sz, true, cmpu, NULL);
}

void
sort_r(void *p, size_t n, size_t sz,
int (*cmp_r)(const void *, const void *, void *), void *data)
{
union sort cmpu = { .cmp_r = cmp };
sort_internal(p, n, sz, true, cmpu, data);
}

pros:
+ not excessively invasive
+ no indirect calls
+ does not duplicate the output code
+ most likely to have unnecessary logic removed by the compiler
cons:
+ a bit ugly


(3) cloning the code with cpp

--- in sort.c ---

#ifdef MAKE_ME_REENTRANT
#define SORT sort_r
#define EXTRA , void *data
#define CMP(a, b) cmp(a, b, data)
#else
#define SORT sort
#define EXTRA
#define CMP(a, b) cmp(a, b)
#endif

void
SORT(void *p, size_t n, size_t sz,
int (*cmp)(const void *, const void * EXTRA) EXTRA)
{
...
r = CMP(a, b);
...
}

--- in sort_r.c ---

#define MAKE_ME_REENTRANT
#include sort.c


pros:
+ noninvasive
+ no runtime overhead
cons:
+ ugly
+ duplicates the output code


Of these I think if we're concerned about the overhead of the thunks
in #1, #2 is the best bet.

While with normal calling conventions sort can end up being identical
object code to sort_r, as various people have noted, I think this kind
of optimization is best left to the compiler. With #2, the compiler
has a fighting chance of being able to do this. (I haven't checked;
I'd be moderately, but not greatly, surprised if any of the compilers
we have do.)

[David Holland]

Post by David Holland
(2) union of function pointers
r = is_r ? cmpu.cmp(a, b) : cmpu.cmp_r(a, b, data);

this test is backwards.

Post by David Holland
void
sort(void *p, size_t n, size_t sz, int (*cmp)(const void *, const void *))
{
union sort cmpu = { .cmp = cmp };
sort_internal(p, n, sz, true, cmpu, NULL);

^^^^
and that should be "false".

sigh. pseudocode...

[David Laight]

Post by Joerg Sonnenberger

Post by David Holland
I have done it by having the original, non-_r functions provide a
thunk for the comparison function, as this is least invasive. If we
think this is too expensive, an alternative is generating a union of
function pointers and making tests at the call sites; another option
is to duplicate the code (hopefully with cpp rather than C&P) but that
seems like a bad plan.

I'd prefer to not have another indirect call. The only difference
is the definition and expanding a CMP macro differently?

Is just casting the function pointers safe in C (well in NetBSD)?
(with the calling conventions that Unix effectively requires)

Can anything slightly less nasty be done with varags functions?

David

[David Holland]

Post by David Laight

Post by Joerg Sonnenberger

Post by David Holland
I have done it by having the original, non-_r functions provide a
thunk for the comparison function, as this is least invasive. If we
think this is too expensive, an alternative is generating a union of
function pointers and making tests at the call sites; another option
is to duplicate the code (hopefully with cpp rather than C&P) but that
seems like a bad plan.

I'd prefer to not have another indirect call. The only difference
is the definition and expanding a CMP macro differently?

Is just casting the function pointers safe in C (well in NetBSD)?
(with the calling conventions that Unix effectively requires)

No. Well, it is, but it's explicitly illegal C and I don't think we
should do it.

Post by David Laight
Can anything slightly less nasty be done with varags functions?

Don't immediately see how...

[David Laight]

Post by David Holland

Post by David Laight

Post by Joerg Sonnenberger

Post by David Holland
I have done it by having the original, non-_r functions provide a
thunk for the comparison function, as this is least invasive. If we
think this is too expensive, an alternative is generating a union of
function pointers and making tests at the call sites; another option
is to duplicate the code (hopefully with cpp rather than C&P) but that
seems like a bad plan.

I'd prefer to not have another indirect call. The only difference
is the definition and expanding a CMP macro differently?

Is just casting the function pointers safe in C (well in NetBSD)?
(with the calling conventions that Unix effectively requires)

No. Well, it is, but it's explicitly illegal C and I don't think we
should do it.

Actually given that these functions are in libc, their interface
is defined by the architecture's function call ABI, not by the C language.

Consider what you would do if you wrote an asm wrapper for qsort(a,b)
in terms of an asm qsort_r(a,b,d)?

For ABI where the the first 3 arguments are passed in registers
(eg: amd64, sparc, sparc64) and for ABI where arguments are stacked
and cleared by the caller (eg i386) I don't you'd consider doing anything
other than putting an extra label on the same code.

There might be ABI where the this isn't true - in which case the
'thunk' is an option, but I don't think NetBSD has one.

FWIW I think Linux is moving to an alternate ppc64 ABI that doesn't
use 'fat pointers'.

David

[Mouse]

Post by David Laight
Is just casting the function pointers safe in C

No. As soon as you call through a pointer to the wrong type you're off
in nasal demon territory. (Loosely put; I'd have to look up the exact
wording - there is a little wiggle room, but, if I've understood the
subject of the discussion correctly, not enough.)

Post by David Laight
(well in NetBSD)? (with the calling conventions that Unix
effectively requires)

How does "Unix" (to the extent that there is a single such thing)
restrict the compiler-and-machine's calling conventions?

If you can find me a description of what NetBSD assumes beyond what C
promises, I can have a stab at answering that question. (I know a few
of the things, such as "there is an exactly-8-bit type", but I feel
fairly sure I don't know them all; I'm even now still discovering such
things occasionally.)

/~\ The ASCII Mouse
\ / Ribbon Campaign
X Against HTML ***@rodents-montreal.org
/ \ Email! 7D C8 61 52 5D E7 2D 39 4E F1 31 3E E8 B3 27 4B

[David Holland]

Post by Mouse
If you can find me a description of what NetBSD assumes beyond what C
promises, I can have a stab at answering that question. (I know a few
of the things, such as "there is an exactly-8-bit type", but I feel
fairly sure I don't know them all; I'm even now still discovering such
things occasionally.)

I don't think we have such a list. In practice though it's defined by
what properties all "normal" architectures share, filtered by which of
these properties gcc reliably allows to show through to the source
level. This is a moving target; for example, not all that long ago you
could rely on signed shifts to behave properly, but nowadays you
can't.

Historically the C standard was understood to provide certain wiggle
room for the architecture and other wiggle room for the compiler, such
that people writing MD code could reasonably assume that properties of
their architecture would be reflected through by the compiler. The gcc
guys have repeatedly demonstrated that they have no use for this model,
no interest in preserving such properties, and are willing to break
them arbitrarily. In this environment I don't think it's a good idea
to make any assumptions at all about things the C standard doesn't
guarantee.

(Also, as far as 8-bit types, while POSIX promises that char is 8 bits
wide, there's still from time to time loose talk about doing a port to
a 36-bit machine, where char would presumably be 9 bits. I think doing
this and making it work this would be good for the general quality of
the code base and I'd rather not introduce unnecessary complications.)

The one exception to all this that I can think of is that we don't
care about platforms where int is 16 bits wide. Or 18, either.

[Mouse]

Post by David Holland

Post by Mouse
If you can find me a description of what NetBSD assumes beyond what
C promises, [...]

I don't think we have such a list.

I didn't think so either, but wasn't nearly sure enough to assume there
wasn't one.

Post by David Holland
[...]. In this environment I don't think it's a good idea to make
any assumptions at all about things the C standard doesn't guarantee.

Then there are a lot of things that need fixing; the one I'm most aware
of is the assumption that all-bits-0 is a nil pointer. (This most
often shows up in the use of calloc, bzero, etc on space that includes
a pointer and then assuming the pointer is nil; see, for example, the
example code in 5.2's getaddrinfo(3) manpage.)

Post by David Holland
(Also, as far as 8-bit types, while POSIX promises that char is 8
bits wide, [...]

Exactly 8 bits, or at least 8 bits? C promises it's at least 8 bits;
that isn't one of the things I had heard that POSIX said anything
about.

Post by David Holland
[...] there's still from time to time loose talk about doing a port
to a 36-bit machine, where char would presumably be 9 bits. I think
doing this and making it work this would be good for the general
quality of the code base and I'd rather not introduce unnecessary
complications.)

I agree. (I've often thought it would be nice to have a checkout
compiler that went out of its way to break as many as possible of the
usual assumptions that are "true everywhere" but that C does not
actually promise....)

Post by David Holland
The one exception to all this that I can think of is that we don't
care about platforms where int is 16 bits wide. Or 18, either.

Or anything else less than 32, I suspect. I would even hazard a guess
that there's code in the tree that assumes int is exactly 32 bits,
though code assuming long is also 32 has most probably been eradicated
by now.

/~\ The ASCII Mouse
\ / Ribbon Campaign
X Against HTML ***@rodents-montreal.org
/ \ Email! 7D C8 61 52 5D E7 2D 39 4E F1 31 3E E8 B3 27 4B

[David Holland]

Post by Mouse

Post by David Holland
[...]. In this environment I don't think it's a good idea to make
any assumptions at all about things the C standard doesn't guarantee.

Then there are a lot of things that need fixing; the one I'm most aware
of is the assumption that all-bits-0 is a nil pointer. (This most
often shows up in the use of calloc, bzero, etc on space that includes
a pointer and then assuming the pointer is nil; see, for example, the
example code in 5.2's getaddrinfo(3) manpage.)

Yes. I think the official stance on that is to worry about it when a
real platform appears where it matters. Myself, I don't write such
code (either for pointers or floats) -- in most cases it is clearer to
initialize explicitly and it's not hard for the compiler to turn a
bunch of explicit initializations into a bzero call if it thinks
that's better. The one family of cases where this isn't so clear is
kernel things where in some cases you get zeroed pages that you know
are zeroed and it's stupid and slow to write more zeros over them
unnecessarily.

Post by Mouse

Post by David Holland
(Also, as far as 8-bit types, while POSIX promises that char is 8
bits wide, [...]

Exactly 8 bits, or at least 8 bits? C promises it's at least 8 bits;
that isn't one of the things I had heard that POSIX said anything
about.

POSIX says that CHAR_BIT is 8.

Post by Mouse

Post by David Holland
[...] there's still from time to time loose talk about doing a port
to a 36-bit machine, where char would presumably be 9 bits. I think
doing this and making it work this would be good for the general
quality of the code base and I'd rather not introduce unnecessary
complications.)

I agree. (I've often thought it would be nice to have a checkout
compiler that went out of its way to break as many as possible of the
usual assumptions that are "true everywhere" but that C does not
actually promise....)

Many people think that, but nobody's really done it, as it's a bit of
a large project. Go for it :-)

Post by Mouse

Post by David Holland
The one exception to all this that I can think of is that we don't
care about platforms where int is 16 bits wide. Or 18, either.

Or anything else less than 32, I suspect. I would even hazard a guess
that there's code in the tree that assumes int is exactly 32 bits,

Yeah probably. It's a big tree and there aren't really adequate
checking tools for this.

Post by Mouse
though code assuming long is also 32 has most probably been eradicated
by now.

Most of that's even gone from pkgsrc at this point. I've been hunting
it down.

[Mouse]

Post by Mouse

[...] I don't think it's a good idea to make any assumptions at all
about things the C standard doesn't guarantee.

Then there are a lot of things that need fixing; the one I'm most
aware of is the assumption that all-bits-0 is a nil pointer.

Yes. I think the official stance on that is to worry about it when a
real platform appears where it matters.

So, rather than start fixing it now, at leisure, a big scramble when it
actually becomes important is preferable? Well, I suppose it's their
collective neck - or, rather, their project's.

The one family of cases where this isn't so clear is kernel things
where in some cases you get zeroed pages that you know are zeroed and
it's stupid and slow to write more zeros over them unnecessarily.

Also possible in userland, though less commonly.

Post by Mouse
(I've often thought it would be nice to have a checkout compiler
that went out of its way to break as many as possible of the usual
assumptions that are "true everywhere" but that C does not actually
promise....)

Many people think that, but nobody's really done it, as it's a bit of
a large project. Go for it :-)

Heh. Yeah, perhaps some one of these years I'll find the spare time to
start seriously hacking compilers.

Post by Mouse
I would even hazard a guess that there's code in the tree that
assumes int is exactly 32 bits,

Yeah probably. It's a big tree and there aren't really adequate
checking tools for this.

Checkout compiler! NetBSD/pdp10! :-)

/~\ The ASCII Mouse
\ / Ribbon Campaign
X Against HTML ***@rodents-montreal.org
/ \ Email! 7D C8 61 52 5D E7 2D 39 4E F1 31 3E E8 B3 27 4B

[David Holland]

Post by Mouse

Post by Mouse
Then there are a lot of things that need fixing; the one I'm most
aware of is the assumption that all-bits-0 is a nil pointer.

Yes. I think the official stance on that is to worry about it when a
real platform appears where it matters.

So, rather than start fixing it now, at leisure, a big scramble when it
actually becomes important is preferable? Well, I suppose it's their
collective neck - or, rather, their project's.

Well... what is a plausible scenario where this becomes important? In
what situation is someone going to try to change this convention, or
more accurately, in what situation is someone going to try to change
this convention in a way that makes it time-critical to fix problems
that arise, such that necks become involved?

The only cases I can think of are deliberately working this issue out
with suitable tools, and porting to some vintage machine where you
can't for some reason use 0 as the null pointer representation.
Neither is exactly an urgent situation.

No new machine will ever have this property because there's too much
existing code that would break and there's no plausible reason to
bother.

Similarly, for all-bits-0 floats, no new machine is going to use
anything but IEEE floats.

Post by Mouse

The one family of cases where this isn't so clear is kernel things
where in some cases you get zeroed pages that you know are zeroed and
it's stupid and slow to write more zeros over them unnecessarily.

Also possible in userland, though less commonly.

Vanishingly rarely; I suppose calloc can avoid rezeroing when it gets
fresh pages from the kernel, but does any calloc actually *do* that
rather than just calling malloc and bzero?

Post by Mouse

Post by Mouse
(I've often thought it would be nice to have a checkout compiler
that went out of its way to break as many as possible of the usual
assumptions that are "true everywhere" but that C does not actually
promise....)

Many people think that, but nobody's really done it, as it's a bit of
a large project. Go for it :-)

Heh. Yeah, perhaps some one of these years I'll find the spare time to
start seriously hacking compilers.

If you keep worrying about how porky gcc is, sooner or later you'll
get irritated enough to write your own...

Post by Mouse

Post by Mouse
I would even hazard a guess that there's code in the tree that
assumes int is exactly 32 bits,

Yeah probably. It's a big tree and there aren't really adequate
checking tools for this.

Checkout compiler! NetBSD/pdp10! :-)

One of the reasons I proposed/started on "mint" was to enable checks
for stuff like this. But I haven't really put any time into it yet...

[Mouse]

Post by David Holland
No new machine will ever have this property because there's too much
existing code that would break and there's no plausible reason to
bother.
Similarly, for all-bits-0 floats, no new machine is going to use
anything but IEEE floats.

If you really believe those, there's no point in carrying this part of
the thread any farther. I find each of them ludicrously implausible;
"ever" is way too long a time, and "nothing will use anything but IEEE
floats" is about as certain as "everything is little-endian". Indeed,
I suspect C is piling up trouble for itself by mandating binary (when
(not "if") a non-binary computer arises, it makes C that much more
likely to be abandoned than adapted).

The only question in my mind is how far off these changes are. I'm
reasonably sure none of them will hit the mass market within the next
decade or so, but that's about all I'm confident of.

Post by David Holland
If you keep worrying about how porky gcc is, sooner or later you'll
get irritated enough to write your own...

True. That it will ever happen, though, depends on a bunch of
assumptions which are looking less and less plausible these years.

/~\ The ASCII Mouse
\ / Ribbon Campaign
X Against HTML ***@rodents-montreal.org
/ \ Email! 7D C8 61 52 5D E7 2D 39 4E F1 31 3E E8 B3 27 4B

[Robert Elz]

Date: Mon, 9 Dec 2013 00:59:49 -0500 (EST)
From: Mouse <***@Rodents-Montreal.ORG>
Message-ID: <***@Chip.Rodents-Montreal.ORG>

| see, for example, the
| example code in 5.2's getaddrinfo(3) manpage.)

I assume you mean ....
memset(&hints, 0, sizeof(hints));

That one is perfectly fine, in any C, the values of the pointer
fields of hints are irrelevant, they're never used (we may wonder
at the interface design that used a struct addrinfo for this purpose,
but that's beyond fixing now). Only the int fields of the hints struct
have any defined use - the others "must be zero or the null pointer."
(It doesn't say that the pointer fields must be the null pointer, and
other fields must be zero, though that would be a sane implementation,
just that the other fields must each be 0, or be the null pointer,
the memset() makes them all be 0 - which conforms with the requirements.)


| I agree. (I've often thought it would be nice to have a checkout
| compiler that went out of its way to break as many as possible of the
| usual assumptions that are "true everywhere" but that C does not
| actually promise....)

Of academic use only - in the real world economics (that existing code,
however badly written, that works today, must also work on future systems,
or no-one will buy them) puts all kinds of limitations on what hardware
designers are able to do, other than for very special purpose uses,
which NetBSD is never going to care about.

What the C standards people, and then the gcc implementors, are doing is
apalling - changing (or even just tightening) the spec to allow for
processor designs that once existed, but will never be seen again, or
that allow optimisations to make code run raster, when what needs optimisation
most is programmer effort, if we have programmers fighting against arcane
language rules that compiler implementors have used to make some code
segment run a few seconds faster, rather than doing the "obvious" intended
operation, then everyone suffers, and "but the rules say we can do that,
and you shouldn't have assumed that we wouldn't" are no consolation at all.

I'm all for additions/corrections/... that aid writing more correct, and
more portable code - that's always a good thing. But changes that force
the writing of any of that, rather than simply promote it, are evil.

C used to be a great language, precisely because it didn't get in the
way, and make programmers much more productive. These days, much of
that has gone, and it is becoming just another obstruction to getting
work actually done.

kre

[Mouse]

Post by Robert Elz

see, for example, the example code in 5.2's getaddrinfo(3) manpage.)

I assume you mean ....
memset(&hints, 0, sizeof(hints));

Yes.

Post by Robert Elz
That one is perfectly fine, in any C, the values of the pointer
fields of hints are irrelevant,

According to the manpage, their values are relevant:

All other elements of the addrinfo structure passed via hints must be
zero or the null pointer.

Post by Robert Elz
(It doesn't say that the pointer fields must be the null pointer, and
other fields must be zero, though that would be a sane
implementation, just that the other fields must each be 0, or be the
null pointer, the memset() makes them all be 0 - which conforms with
the requirements.)

I would disagree that "all zero bits" is a reasonable choice for what
it means for a pointer to "be zero", unless all zero bits happens to be
the implementation's choice for a nil pointer. It's a C interface; I
have trouble interpreting "be zero" as anything but "hold a value which
compares equal to zero", which for pointers means a nil pointer.

In any case, it's hardly the only example of that assumption; it's just
the first one that came to mind.

Post by Robert Elz
Of academic use only - [...]
I'm all for additions/corrections/... that aid writing more correct,
and more portable code - that's always a good thing.

That's exactly what such a checkout compiler would be for. Indeed, to
be really useful it would need to have some kind of controls for
exactly which assumptions it breaks, so that, for example, you could
tell it to make nil pointers all-0-bits but break the assumption that
int has no padding bits in it.

/~\ The ASCII Mouse
\ / Ribbon Campaign
X Against HTML ***@rodents-montreal.org
/ \ Email! 7D C8 61 52 5D E7 2D 39 4E F1 31 3E E8 B3 27 4B

[Robert Elz]

Date: Mon, 9 Dec 2013 02:37:30 -0500 (EST)
From: Mouse <***@Rodents-Montreal.ORG>
Message-ID: <***@Chip.Rodents-Montreal.ORG>

| According to the manpage, their values are relevant:

Just in case someday someone ever thinks of a use for them.
Very unlikely. But in any case, since the doc explicitly shows
init by memset(..,0,..), and that's what everyone does, the
implementation would need to keep that working, even if it ever
happened that the null pointer was not all 0 bits (and personally,
I'm not going to every worry about that happening - it won't.)

| In any case, it's hardly the only example of that assumption; it's just
| the first one that came to mind.

Yes, there are certainly plenty of cases where structs are cleared
(by calloc, or explicit memset) and then it's assumed that any pointers
in them are NULL.

That's the kind of economic imperative that I referred to - any implementation
that makes that code fail (however legal it might be according to the
rules of C) will simply be ignored in the world - if hardware/software
manufacturers (including us who give stuff away for free) want it to be
used, we have to make stuff that the users are happy with - and "all my
working code fails on this system" isn't going to cut it.

| That's exactly what such a checkout compiler would be for.

I have no problem at all with tools that check/validate assumptions.

It is the changes (including places where it can be argued that there
was no explicit specification previously) from accepted practice over the
past (almost) 40 years to the C language spec that I don't like.

Had all this been done in 1980, it might have made sense, by 1990, the
ship had already sailed, it was already too late for anyone to even consider
changing any of the basic (written or unwritten) assumptions about how
hardware works. Pretending it is even remotely possible that arithmetic
might go back to 1's complement, or anything other than 0 bits will ever
be the null pointer, or even that memory won't be byte addressable (for
whatever size byte ends up being in use, but it is almost inconceivable
anything other than 8 bits will ever be supported) is just insane. Making
programmers work harder, just in case their code happens to want to run
on such a nonexistent computer is ludicrous. That stuff is all extinct.

kre

[Alan Barrett]

Post by Mouse

Post by David Laight
Is just casting the function pointers safe in C

No. As soon as you call through a pointer to the wrong type
you're off in nasal demon territory. (Loosely put; I'd have to
look up the exact wording - there is a little wiggle room, but,
if I've understood the subject of the discussion correctly, not
enough.)

You can't call through a function pointer of the wrong type, but
you can cast from one type to another. I think that's enough,
provided that void * is large enough to be converted to and from a
function pointer.

Post by Mouse
If you can find me a description of what NetBSD assumes beyond
what C promises, I can have a stab at answering that question.

There is no such list. That's a bug in NetBSD's documentation.

--apb (Alan Barrett)

[Mouse]

Post by Mouse

Post by David Laight
Is just casting the function pointers safe in C

No. As soon as you call through a pointer to the wrong type you're
off in nasal demon territory.

You can't call through a function pointer of the wrong type, but you
can cast from one type to another.

True. I wrote that with more context than the above quote gives. I
was responding to something I might flesh out as "Is just casting the
function pointers enough to make [the thing under discussion] safe in
C?".

I think that's enough,

Maybe. It's possible I misunderstood something; I didn't go through
the whole patch in detail. But C99 does promise that....

[#8] A pointer to a function of one type may be converted to
a pointer to a function of another type and back again; the
result shall compare equal to the original pointer. If a
converted pointer is used to call a function whose type is
not compatible with the pointed-to type, the behavior is
undefined.

(6.3.2.3 in the version I have).

provided that void * is large enough to be converted to and from a
function pointer.

I actually don't see anything that promises that a pointer to a
function type may be converted to a pointer to void, nor back again
(except, in each direction, when the original pointer is nil), much
less promising anything about the results if it is done. But I haven't
read over the whole thing recently enough to be sure there isn't such a
promise hiding somewhere.

/~\ The ASCII Mouse
\ / Ribbon Campaign
X Against HTML ***@rodents-montreal.org
/ \ Email! 7D C8 61 52 5D E7 2D 39 4E F1 31 3E E8 B3 27 4B

[Alan Barrett]

Post by Mouse
I actually don't see anything that promises that a pointer to a
function type may be converted to a pointer to void, nor back
again (except, in each direction, when the original pointer is
nil), much less promising anything about the results if it is
done. But I haven't read over the whole thing recently enough
to be sure there isn't such a promise hiding somewhere.

Sorry, I did not express myself clearly enough. C does not
promise that function pointers can be converted to or from void*
pointers, but I believe that all existing NetBSD implementations
do allow such conversions.

--apb (Alan Barrett)

[matthew green]

Post by Alan Barrett

Post by Mouse
I actually don't see anything that promises that a pointer to a
function type may be converted to a pointer to void, nor back
again (except, in each direction, when the original pointer is
nil), much less promising anything about the results if it is
done. But I haven't read over the whole thing recently enough
to be sure there isn't such a promise hiding somewhere.

Sorry, I did not express myself clearly enough. C does not
promise that function pointers can be converted to or from void*
pointers, but I believe that all existing NetBSD implementations
do allow such conversions.

if you include the powerpc64 port in the list of existing
netbsd implementations, then we do have one.. or at least
sort of. i don't recall the details, but they're not just
simple pointers you jump to, and the descriptors take up
more space than a normal pointer.


.mrg.

[Valery Ushakov]

Post by matthew green

Post by Alan Barrett

Post by Mouse
I actually don't see anything that promises that a pointer to a
function type may be converted to a pointer to void, nor back
again (except, in each direction, when the original pointer is
nil), much less promising anything about the results if it is
done. But I haven't read over the whole thing recently enough
to be sure there isn't such a promise hiding somewhere.

Sorry, I did not express myself clearly enough. C does not
promise that function pointers can be converted to or from void*
pointers, but I believe that all existing NetBSD implementations
do allow such conversions.

if you include the powerpc64 port in the list of existing
netbsd implementations, then we do have one.. or at least
sort of. i don't recall the details, but they're not just
simple pointers you jump to, and the descriptors take up
more space than a normal pointer.

Itanium has fat function pointers - they point to a struct of code
address plus gp register value.

-uwe

[Steffen "Daode" Nurpmeso]

Sneaking in because of a reason..

|> On Mon, 09 Dec 2013, Mouse wrote:
|>> I actually don't see anything that promises that a pointer to a
|>> function type may be converted to a pointer to void, nor back
|>> again (except, in each direction, when the original pointer is
|>
|> Sorry, I did not express myself clearly enough. C does not
|> promise that function pointers can be converted to or from void*
|> pointers, but I believe that all existing NetBSD implementations

Rich Felker corrected my worldview and correctly pointed out that
POSIX actually does add an additional constraint in [1]:

Note that conversion from a void * pointer to a function pointer
as in:

fptr = (int (*)(int))dlsym(handle, "my_function");

is not defined by the ISO C standard. This standard requires this
conversion to work correctly on conforming implementations.

[1] <http://pubs.opengroup.org/onlinepubs/9699919799/functions/dlsym.html>

--steffen

[Christos Zoulas]

Post by David Holland
(Cc: tech-kern because of kheapsort())
My irritation with not being able to pass a data pointer through
qsort() boiled over just now. Apparently Linux and/or GNU has a
qsort_r() that supports this; so, following is a patch that gives us
a compatible qsort_r() plus mergesort_r(), and heapsort_r().
I have done it by having the original, non-_r functions provide a
thunk for the comparison function, as this is least invasive. If we
think this is too expensive, an alternative is generating a union of
function pointers and making tests at the call sites; another option
is to duplicate the code (hopefully with cpp rather than C&P) but that
seems like a bad plan. Note that the thunks use an extra struct to
hold the function pointer; this is to satisfy C standards pedantry
about void pointers vs. function pointers, and if we decide not to
care it could be simplified.
This patch was supposed to have all the necessary support widgetry,
like namespace.h changes, but there's at least one more thing not in
it: MLINKS for the new functions and corresponding setlist
changes. If I've forgotten anything else, let me know.
heapsort() is used in one place in the kernel as kheapsort(), which
takes an extra argument so that the heapsort code itself doesn't have
- add kheapsort_r()
- change the signature of plain kheapsort() to move the extra
argument to a place it is less likely to cause confusion with the
userdata argument;
- update the caller for the signature change;
but I have not changed the caller to call kheapsort_r instead. Based
on the code, this should probably be done later as like many sort
calls it's using a global for context. At this point the plain
kheapsort can be removed.

LGTM.

christos

[David Laight]

Post by David Holland
I have done it by having the original, non-_r functions provide a
thunk for the comparison function, as this is least invasive. If we
think this is too expensive, an alternative is generating a union of
function pointers and making tests at the call sites; another option
is to duplicate the code (hopefully with cpp rather than C&P) but that
seems like a bad plan. Note that the thunks use an extra struct to
hold the function pointer; this is to satisfy C standards pedantry
about void pointers vs. function pointers, and if we decide not to
care it could be simplified.

On most architectures I think just:
__weak_alias(heapsort_r,heapsort)
__weak_alias(heapsort_r,_heapsort)
will work.

David

[Alan Barrett]

Post by David Holland
My irritation with not being able to pass a data pointer through
qsort() boiled over just now. Apparently Linux and/or GNU
has a qsort_r() that supports this; so, following is a patch
that gives us a compatible qsort_r() plus mergesort_r(), and
heapsort_r().

Apparently FreeBSD [1] and GNU [2] have incompatible versions
of qsort_r, passing the extra 'thunk' or 'data' argument in a
different position.

[1]: FreeBSD qsort_r <http://www.manpagez.com/man/3/qsort_r/>
[2]: Linux qsort_r <http://man7.org/linux/man-pages/man3/qsort.3.html>

If we have to pick one, let's pick the FreeBSD version.

Post by David Holland
I have done it by having the original, non-_r functions
provide a thunk for the comparison function, as this is least
invasive. If we think this is too expensive, an alternative is
generating a union of function pointers and making tests at the
call sites; another option is to duplicate the code (hopefully
with cpp rather than C&P) but that seems like a bad plan.

I'd probably duplicate the code via CPP, to trade time for space,
but your way is fine.

Post by David Holland
Note that the thunks use an extra struct to hold the function
pointer; this is to satisfy C standards pedantry about void
pointers vs. function pointers, and if we decide not to care it
could be simplified.

That adds more run-time overhead. Could you make it conditional
on whether it's really necessary? All existing NetBSD platforms
can convert back and forth between void * and function pointers
without any trouble.

--apb (Alan Barrett)

[David Holland]

Post by David Holland
My irritation with not being able to pass a data pointer through
qsort() boiled over just now. Apparently Linux and/or GNU has a
qsort_r() that supports this; so, following is a patch that gives
us a compatible qsort_r() plus mergesort_r(), and heapsort_r().

Apparently FreeBSD [1] and GNU [2] have incompatible versions of
qsort_r, passing the extra 'thunk' or 'data' argument in a
different position.
[1]: FreeBSD qsort_r <http://www.manpagez.com/man/3/qsort_r/>
[2]: Linux qsort_r <http://man7.org/linux/man-pages/man3/qsort.3.html>
If we have to pick one, let's pick the FreeBSD version.

Given that it's just left vs. right side, the only technical reason to
favor one over the other is that the right-side one (the Linux one)
allows sharing the same object code for both versions, at least on
common platforms, as discussed elsewhere in this thread.

Also, all else being equal the Linux one de facto has greater market
penetration.

So I think picking the Linux one is a marginally better choice.

Post by David Holland
Note that the thunks use an extra struct to hold the function
pointer; this is to satisfy C standards pedantry about void
pointers vs. function pointers, and if we decide not to care it
could be simplified.

That adds more run-time overhead. Could you make it conditional on
whether it's really necessary? All existing NetBSD platforms can
convert back and forth between void * and function pointers without
any trouble.

I think switching approaches (as in the other post I just made) is
probably a better idea, because it also gets rid of this issue.

[Christos Zoulas]

Post by Alan Barrett

Post by David Holland
My irritation with not being able to pass a data pointer through
qsort() boiled over just now. Apparently Linux and/or GNU
has a qsort_r() that supports this; so, following is a patch
that gives us a compatible qsort_r() plus mergesort_r(), and
heapsort_r().

Apparently FreeBSD [1] and GNU [2] have incompatible versions
of qsort_r, passing the extra 'thunk' or 'data' argument in a
different position.
[1]: FreeBSD qsort_r <http://www.manpagez.com/man/3/qsort_r/>
[2]: Linux qsort_r <http://man7.org/linux/man-pages/man3/qsort.3.html>
If we have to pick one, let's pick the FreeBSD version.

Actually let's not (fortunately dh@ chose the right one).
We should pick the linux one:

http://sourceware.org/ml/libc-alpha/2008-12/msg00007.html

christos