diff options
| author | Florian Weimer <fweimer@redhat.com> | 2023-11-21 16:45:35 +0100 |
|---|---|---|
| committer | Florian Weimer <fweimer@redhat.com> | 2023-11-21 16:46:18 +0100 |
| commit | 64e4acf24da15c11cb83f933947df3b2e8a700cd (patch) | |
| tree | b3d8e27747379f2b9e4007740f706a63225387f5 /stdlib/qsort.c | |
| parent | 55364e1f7dfab372f0710513c4d1c967c4965f71 (diff) | |
| download | glibc-64e4acf24da15c11cb83f933947df3b2e8a700cd.tar.xz glibc-64e4acf24da15c11cb83f933947df3b2e8a700cd.zip | |
stdlib: The qsort implementation needs to use heapsort in more cases
The existing logic avoided internal stack overflow. To avoid
a denial-of-service condition with adversarial input, it is necessary
to fall over to heapsort if tail-recursing deeply, too, which does
not result in a deep stack of pending partitions.
The new test stdlib/tst-qsort5 is based on Douglas McIlroy's paper
on this subject.
Reviewed-by: Adhemerval Zanella <adhemerval.zanella@linaro.org>
Diffstat (limited to 'stdlib/qsort.c')
| -rw-r--r-- | stdlib/qsort.c | 17 |
1 files changed, 13 insertions, 4 deletions
diff --git a/stdlib/qsort.c b/stdlib/qsort.c index a2f9e916ef..be01fb5598 100644 --- a/stdlib/qsort.c +++ b/stdlib/qsort.c @@ -389,14 +389,23 @@ __qsort_r (void *const pbase, size_t total_elems, size_t size, { if ((size_t) (hi - left_ptr) <= max_thresh) /* Ignore both small partitions. */ - top = pop (top, &lo, &hi, &depth); + { + top = pop (top, &lo, &hi, &depth); + --depth; + } else - /* Ignore small left partition. */ - lo = left_ptr; + { + /* Ignore small left partition. */ + lo = left_ptr; + --depth; + } } else if ((size_t) (hi - left_ptr) <= max_thresh) /* Ignore small right partition. */ - hi = right_ptr; + { + hi = right_ptr; + --depth; + } else if ((right_ptr - lo) > (hi - left_ptr)) { /* Push larger left partition indices. */ |