check for UB in qsort() and bsearch()

3 files changed, 38 insertions, 4 deletions

diff --git a/src/stdlib/_stdlib.h b/src/stdlib/_stdlib.h
index 769f220b..14953e6f 100644
--- a/src/stdlib/_stdlib.h
+++ b/src/stdlib/_stdlib.h
@@ -5,6 +5,32 @@
 #include <limits.h>
 #include "_safety.h"
 
+#ifdef NEED_COMPAR
+#ifdef NDEBUG
+#define SAFE_COMPAR(__comp, __p1, __p2, __sz, __fn) __comp(__p1, __p2)
+#else
+static unsigned __hash(const void *p, size_t size) {
+	unsigned int h = 0;
+	const unsigned char *s = p;
+	for (size_t i = 0; i < size; i++) {
+		h <<= CHAR_BIT;
+		h |= s[i];
+	}
+	return h;
+}
+static int __safe_compar(int (*compar)(const void *, const void *), const void *p1, const void *p2, size_t size, const char *fn) {
+	unsigned int h1 = __hash(p1, size);
+	unsigned int h2 = __hash(p2, size);
+	int ret = compar(p1, p2);
+	if (h1 != __hash(p1, size) || h2 != __hash(p2, size)) {
+		__undefined("In call to %s(): Comparison function modifies parameters", fn);
+	}
+	return ret;
+}
+#define SAFE_COMPAR(__comp, __p1, __p2, __sz, __fn) __safe_compar(__comp, __p1, __p2, __sz, __fn)
+#endif
+#endif
+
 #define _rand(_n) \
 	(((_n) = (_n) * 1103515245 + 12345) ? (_n) / UINT_MAX % RAND_MAX : 0)
 
diff --git a/src/stdlib/bsearch.c b/src/stdlib/bsearch.c
index c710406e..a096cf16 100644
--- a/src/stdlib/bsearch.c
+++ b/src/stdlib/bsearch.c
@@ -1,4 +1,5 @@
 #include <stdlib.h>
+#define NEED_COMPAR
 #include "_stdlib.h"
 
 /** binary search **/
@@ -14,13 +15,20 @@ void * bsearch(const void * key, const void * base, size_t nmemb, size_t size, i
 	SIGNAL_SAFE(0);
 	ASSERT_NONNULL(key);
 	ASSERT_NONNULL(base);
-	/* overlap can't be detected because the size of key can't be known */
+	/* assume that key exists in base, don't check for overlap */
 
 	/* TODO: ensure everything is in order to start with */
+	#ifndef NDEBUG
+	for (size_t i = 0; nmemb != 0 && i < nmemb - 1; i++) {
+		if (SAFE_COMPAR(compar, addr + (i * size), addr + ((i + 1) * size), size, "bsearch") > 0) {
+			__undefined("In call to bsearch(): Base array is not sorted");
+		}
+	}
+	#endif
 
 	while (ret == NULL) {
 		/* TODO: ensure compar doesn't modify things */
-		int comp = compar(key, addr + (i * size));
+		int comp = SAFE_COMPAR(compar, key, addr + (i * size), size, "bsearch");
 		if (comp == 0) {
 			return (void*)(addr + (i * size));
 		} else if (comp > 0) {
diff --git a/src/stdlib/qsort.c b/src/stdlib/qsort.c
index 346dba88..5d30cb3b 100644
--- a/src/stdlib/qsort.c
+++ b/src/stdlib/qsort.c
@@ -1,4 +1,5 @@
 #include <stdlib.h>
+#define NEED_COMPAR
 #include "_stdlib.h"
 
 /** sort an array **/
@@ -24,8 +25,7 @@ static void __qsort(char *base, size_t size, size_t lo, size_t hi, int (*compar)
 	}
 
 	for (j = lo; j < hi; j++) {
-		/* TODO: ensure compar() doesn't modify things */
-		if (compar(base + (size * j), base + (size * hi)) < 0) {
+		if (SAFE_COMPAR(compar, base + (size * j), base + (size * hi), size, "qsort") < 0) {
 			__swap(base, size, i, j);
 			i++;
 		}