[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <FUC_C812_6fwFLOvPjay7WqPu4cxybgR0DlOp2YYyLzyM3hw8Zizhfe6Z6H9L7A8omf6CgT8pzzenDWAmES3t16uTOI338fejYLjplHCudA=@proton.me>
Date: Sat, 25 Apr 2026 07:01:49 +0000
From: David Sparks <sparks05@...ton.me>
To: "dalias@...ifal.cx" <dalias@...ifal.cx>
Cc: "musl@...ts.openwall.com" <musl@...ts.openwall.com>, "mailto.luca.kellermann@...il.com" <mailto.luca.kellermann@...il.com>, David Sparks <sparks05@...ton.me>
Subject: Re: Some additional qsort patches
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.
Ugh.
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.
