[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <20260425112446.GR1827@brightrain.aerifal.cx>
Date: Sat, 25 Apr 2026 07:24:46 -0400
From: "dalias@...ifal.cx" <dalias@...ifal.cx>
To: David Sparks <sparks05@...ton.me>
Cc: "musl@...ts.openwall.com" <musl@...ts.openwall.com>,
"mailto.luca.kellermann@...il.com" <mailto.luca.kellermann@...il.com>
Subject: Re: Some additional qsort patches
On Sat, Apr 25, 2026 at 07:01:49AM +0000, David Sparks wrote:
> On Sunday, April 19th, 2026 at 02:38, dalias@...ifal.cx <dalias@...ifal.cx> wrote:
>
> > On Wed, Apr 15, 2026 at 01:05:45AM +0000, David Sparks wrote:
> >> 2b) Implement a do_sift() helper which takes the root compare
> >> as an argument and can be used by both sift() and
> >> trinkle(). (This has the potential to take an ar[] array
> >> as well and merge the cycle() operations.)
> >
> > This maybe sounds better, but I'd probably have to see it to
> > understand what you mean.
>
> I got this working, but not cleaned up or benchmarked, when
> I ran into a problem. Using a single call to cycle() requires
> a larger ar[] array, and the recently added index masking doesn't
> like that.
>
> Suppose I have a 32-bit address space, and sort over 2^31 maliciously
> chosen bytes.
>
> In particular, suppose I have a heap consisting of L(43) + L(41)
> + L(39) + ... + L(3) + L(1) (0x539d4bb9 + 0x1ff0186f + 0x0c32fd95
> + ... + 6 + 1 = 0x874a7eed = 2,269,806,317 element), and I add one
> more element which will trinkle and sift all the way down to position 0.
>
> That's 22 stepchild steps, plus 42 left child steps inside the L(43)
> tree. And the ar[] array needs two more entries for the new root,
> once at the beginning and once at the end. This totals 66, which
> will not fit into AR_MASK+1 = 4*sizeof(size_t) = 64 entries.
>
> Now, this does require sorting a maliciously arranged array of over
> 2 billion bytes. The pattern isn't trivial, because we can only sort
> bytes and can't do a simple increasing sequence with a 0 at the end.
>
> But it's just barely technically possible.
>
> (The corresponding 64-bit issue can't happen, because you can't
> get over 2^63 bytes of usable memory, and the sort would take
> longer than your lifetime even if it could.)
>
>
> The obvious fix is to slightly enlarge the ar[] array, but that
> breaks the power-of-2 masking. I could also ignore it as a
> "never going to really happen" issue. Note that 65 elements in
> the ar[] array *will* work, as the first and last head pointers
> will overlap due to masking.
I think you're mixing something up. AR_MASK is not a bitmask of
positions that needs a bit per possible position. It's just a mask of
the entire range of valid indices to perform a modulo operation and
guarantee that, even in the event of wrong logic somewhere, we never
access outside the array.
If you need 66 entries, the length would just need to be increased to
128 entries (next largest power of 2).
Rich
Powered by blists - more mailing lists
Confused about mailing lists and their use?
Read about mailing lists on Wikipedia
and check out these
guidelines on proper formatting of your messages.
