| Message ID | 877cm8esws.fsf@oldenburg.str.redhat.com |
|---|---|
| State | New |
| Headers | show |
| Series | stdlib: Add another workaround to the insertion sort phase of qsort | expand |
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
diff --git a/stdlib/qsort.c b/stdlib/qsort.c index be01fb5598..6f28abbc7f 100644 --- a/stdlib/qsort.c +++ b/stdlib/qsort.c @@ -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)
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