1From 867a65f49b59b4127b27cfe40249c7965e7316b7 Mon Sep 17 00:00:00 2001
 2From: Rich Felker <dalias@aerifal.cx>
 3Date: Thu, 9 Apr 2026 23:40:53 -0400
 4Subject: [PATCH] qsort: hard-preclude oob array writes independent of any
 5 invariants
 6
 7while the root cause of CVE-2026-40200 was a faulty ctz primitive, the
 8fallout of the bug would have been limited to erroneous sorting or
 9infinite loop if not for the stores to a stack-based array that
10depended on trusting invariants in order not to go out of bounds.
11
12increase the size of the array to a power of two so that we can mask
13indices into it to force them into range. in the absence of any
14further bug, the masking is a no-op, but it does not have any
15measurable performance cost, and it makes spatial memory safety
16trivial to prove (and for readers not familiar with the algorithms to
17trust).
18---
19 src/stdlib/qsort.c | 20 +++++++++++++-------
20 1 file changed, 13 insertions(+), 7 deletions(-)
21
22diff --git a/src/stdlib/qsort.c b/src/stdlib/qsort.c
23index 13219ab3..e4bce9f7 100644
24--- a/src/stdlib/qsort.c
25+++ b/src/stdlib/qsort.c
26@@ -89,10 +89,16 @@ static inline void shr(size_t p[2], int n)
27 	p[1] >>= n;
28 }
29 
30+/* power-of-two length for working array so that we can mask indices and
31+ * not depend on any invariant of the algorithm for spatial memory safety.
32+ * the original size was just 14*sizeof(size_t)+1 */
33+#define AR_LEN  (16 * sizeof(size_t))
34+#define AR_MASK (AR_LEN - 1)
35+
36 static void sift(unsigned char *head, size_t width, cmpfun cmp, void *arg, int pshift, size_t lp[])
37 {
38 	unsigned char *rt, *lf;
39-	unsigned char *ar[14 * sizeof(size_t) + 1];
40+	unsigned char *ar[AR_LEN];
41 	int i = 1;
42 
43 	ar[0] = head;
44@@ -104,16 +110,16 @@ static void sift(unsigned char *head, size_t width, cmpfun cmp, void *arg, int p
45 			break;
46 		}
47 		if(cmp(lf, rt, arg) >= 0) {
48-			ar[i++] = lf;
49+			ar[i++ & AR_MASK] = lf;
50 			head = lf;
51 			pshift -= 1;
52 		} else {
53-			ar[i++] = rt;
54+			ar[i++ & AR_MASK] = rt;
55 			head = rt;
56 			pshift -= 2;
57 		}
58 	}
59-	cycle(width, ar, i);
60+	cycle(width, ar, i & AR_MASK);
61 }
62 
63 static void trinkle(unsigned char *head, size_t width, cmpfun cmp, void *arg, size_t pp[2], int pshift, int trusty, size_t lp[])
64@@ -121,7 +127,7 @@ static void trinkle(unsigned char *head, size_t width, cmpfun cmp, void *arg, si
65 	unsigned char *stepson,
66 	              *rt, *lf;
67 	size_t p[2];
68-	unsigned char *ar[14 * sizeof(size_t) + 1];
69+	unsigned char *ar[AR_LEN];
70 	int i = 1;
71 	int trail;
72 
73@@ -142,7 +148,7 @@ static void trinkle(unsigned char *head, size_t width, cmpfun cmp, void *arg, si
74 			}
75 		}
76 
77-		ar[i++] = stepson;
78+		ar[i++ & AR_MASK] = stepson;
79 		head = stepson;
80 		trail = pntz(p);
81 		shr(p, trail);
82@@ -150,7 +156,7 @@ static void trinkle(unsigned char *head, size_t width, cmpfun cmp, void *arg, si
83 		trusty = 0;
84 	}
85 	if(!trusty) {
86-		cycle(width, ar, i);
87+		cycle(width, ar, i & AR_MASK);
88 		sift(head, width, cmp, arg, pshift, lp);
89 	}
90 }
91-- 
922.49.0
93