stdlib: Add another workaround to the insertion sort phase of qsort
Checks
Context |
Check |
Description |
redhat-pt-bot/TryBot-apply_patch |
success
|
Patch applied to master at the time it was sent
|
redhat-pt-bot/TryBot-32bit |
success
|
Build for i686
|
linaro-tcwg-bot/tcwg_glibc_build--master-arm |
success
|
Testing passed
|
linaro-tcwg-bot/tcwg_glibc_build--master-aarch64 |
success
|
Testing passed
|
linaro-tcwg-bot/tcwg_glibc_check--master-arm |
success
|
Testing passed
|
linaro-tcwg-bot/tcwg_glibc_check--master-aarch64 |
success
|
Testing passed
|
Commit Message
If the comparison function returns negative values incorrectly, it was
possible that we decrement tmp_ptr past the start of the array.
Improves commit e4d8117b82065dc72e8df80097360e7c05a349b9 ("stdlib:
Avoid another self-comparison in qsort").
---
stdlib/qsort.c | 13 +++++++++++--
1 file changed, 11 insertions(+), 2 deletions(-)
base-commit: 472894d2cfee5751b44c0aaa71ed87df81c8e62e
Comments
On Nov 23 2023, Florian Weimer wrote:
> + while (run_ptr != tmp_ptr
> + && cmp (run_ptr, tmp_ptr, arg) < 0
> + && run_ptr != base_ptr)
Why do you check run_ptr != base_ptr after calling cmp?
* Andreas Schwab:
> On Nov 23 2023, Florian Weimer wrote:
>
>> + while (run_ptr != tmp_ptr
>> + && cmp (run_ptr, tmp_ptr, arg) < 0
>> + && run_ptr != base_ptr)
>
> Why do you check run_ptr != base_ptr after calling cmp?
I was thinking that it might prevent us from evaluating the condition in
some cases. Does this lead to a bug? Sorry, I'm having a bad day.
Thanks,
Florian
On Nov 23 2023, Florian Weimer wrote:
> * Andreas Schwab:
>
>> On Nov 23 2023, Florian Weimer wrote:
>>
>>> + while (run_ptr != tmp_ptr
>>> + && cmp (run_ptr, tmp_ptr, arg) < 0
>>> + && run_ptr != base_ptr)
>>
>> Why do you check run_ptr != base_ptr after calling cmp?
>
> I was thinking that it might prevent us from evaluating the condition in
> some cases.
I would expect that the call would be more expensive than the
comparison.
* Andreas Schwab:
> On Nov 23 2023, Florian Weimer wrote:
>
>> * Andreas Schwab:
>>
>>> On Nov 23 2023, Florian Weimer wrote:
>>>
>>>> + while (run_ptr != tmp_ptr
>>>> + && cmp (run_ptr, tmp_ptr, arg) < 0
>>>> + && run_ptr != base_ptr)
>>>
>>> Why do you check run_ptr != base_ptr after calling cmp?
>>
>> I was thinking that it might prevent us from evaluating the condition in
>> some cases.
>
> I would expect that the call would be more expensive than the
> comparison.
If I moved it before the cmp call, wouldn't it happen on each loop
iteration? And with the current version, the comparison is only made on
the final iteration.
Thanks,
Florian
* Florian Weimer:
> * Andreas Schwab:
>
>> On Nov 23 2023, Florian Weimer wrote:
>>
>>> * Andreas Schwab:
>>>
>>>> On Nov 23 2023, Florian Weimer wrote:
>>>>
>>>>> + while (run_ptr != tmp_ptr
>>>>> + && cmp (run_ptr, tmp_ptr, arg) < 0
>>>>> + && run_ptr != base_ptr)
>>>>
>>>> Why do you check run_ptr != base_ptr after calling cmp?
>>>
>>> I was thinking that it might prevent us from evaluating the condition in
>>> some cases.
>>
>> I would expect that the call would be more expensive than the
>> comparison.
>
> If I moved it before the cmp call, wouldn't it happen on each loop
> iteration? And with the current version, the comparison is only made on
> the final iteration.
I was really confused when I wrote this. Fred reviewed the patch and
explained it to me. I'll send a new version.
Thanks,
Florian
@@ -238,8 +238,17 @@ insertion_sort_qsort_partitions (void *const pbase, size_t total_elems,
while ((run_ptr += size) <= end_ptr)
{
tmp_ptr = run_ptr - size;
- while (run_ptr != tmp_ptr && cmp (run_ptr, tmp_ptr, arg) < 0)
- tmp_ptr -= size;
+ /* The initial pointer comparison avoids a call to cmp if the
+ pointer arguments are identical (the call returns zero with a
+ correctly implemented comparison function). The final
+ pointer comparison cannot be reached because the element at
+ base_ptr is the smallest element, but it prevents the loop
+ from running beyond the start of the array with a broken
+ comparison function. */
+ while (run_ptr != tmp_ptr
+ && cmp (run_ptr, tmp_ptr, arg) < 0
+ && run_ptr != base_ptr)
+ tmp_ptr -= size;
tmp_ptr += size;
if (tmp_ptr != run_ptr)