libc: Drop incorrect qsort optimization

As pointed out in the PR and the article linked below, the switch to
insertion sort in the BSD qsort code is based on a misunderstanding of
Knuth's TAOCP and

libc: Drop incorrect qsort optimization

As pointed out in the PR and the article linked below, the switch to
insertion sort in the BSD qsort code is based on a misunderstanding of
Knuth's TAOCP and is actually a pessimization. As demonstrated by the
added test, it is trivially easy to construct pathological input which
results in quadratic runtime. Without that misguided optimization, the
same input runs in nearly linearithmic time.

https://www.raygard.net/2022/02/26/Re-engineering-a-qsort-part-3

PR: 287089
MFC after: 1 week
Reviewed by: imp
Differential Revision: https://reviews.freebsd.org/D51907

show more ...

lib: Remove ancient SCCS tags.

Remove ancient SCCS tags from the tree, automated scripting, with two
minor fixup to keep things compiling. All the common forms in the tree
were removed with a perl s

lib: Remove ancient SCCS tags.

Remove ancient SCCS tags from the tree, automated scripting, with two
minor fixup to keep things compiling. All the common forms in the tree
were removed with a perl script.

Sponsored by: Netflix

show more ...

libc: Purge unneeded cdefs.h

These sys/cdefs.h are not needed. Purge them. They are mostly left-over
from the $FreeBSD$ removal. A few in libc are still required for macros
that cdefs.h defines. Kee

libc: Purge unneeded cdefs.h

These sys/cdefs.h are not needed. Purge them. They are mostly left-over
from the $FreeBSD$ removal. A few in libc are still required for macros
that cdefs.h defines. Keep those.

Sponsored by: Netflix
Differential Revision: https://reviews.freebsd.org/D42385

show more ...

Remove $FreeBSD$: one-line .c pattern

Remove /^[\s*]*__FBSDID\("\$FreeBSD\$"\);?\s*\n/

libc: Sorting is not needed when there are less than two elements

If there are less than two elements avoid executing the first
sorting loop. No functional change intended.

Reviewed by: kib@
MFC af

libc: Sorting is not needed when there are less than two elements

If there are less than two elements avoid executing the first
sorting loop. No functional change intended.

Reviewed by: kib@
MFC after: 1 week
Sponsored by: NVIDIA Networking
Differential Revision: https://reviews.freebsd.org/D39691

show more ...

libc: Add missing object size check to qsort_s(3)

When sorting, both the C11 standard (ISO/IEC 9899:2011, K.3.6.3.2) and
the ISO/IEC JTC1 SC22 WG14 N1172 standard, does not define objects of
zero si

libc: Add missing object size check to qsort_s(3)

When sorting, both the C11 standard (ISO/IEC 9899:2011, K.3.6.3.2) and
the ISO/IEC JTC1 SC22 WG14 N1172 standard, does not define objects of
zero size as undefined behaviour. However Microsoft's cpp-docs does.

Add proper checks for this. Found while working on bsort(3).

Reviewed by: kib@ and emaste@
MFC after: 1 week
Sponsored by: NVIDIA Networking
Differential Revision: https://reviews.freebsd.org/D39687

show more ...

Alter the prototype of qsort_r(3) to match POSIX, which adopted the
glibc-based interface.

Unfortunately, the glibc maintainers, despite knowing the existence
of the FreeBSD qsort_r(3) interface in

Alter the prototype of qsort_r(3) to match POSIX, which adopted the
glibc-based interface.

Unfortunately, the glibc maintainers, despite knowing the existence
of the FreeBSD qsort_r(3) interface in 2004 and refused to add the
same interface to glibc based on grounds of the lack of standardization
and portability concerns, has decided it was a good idea to introduce
their own qsort_r(3) interface in 2007 as a GNU extension with a
slightly different and incompatible interface.

With the adoption of their interface as POSIX standard, let's switch
to the same prototype, there is no need to remain incompatible.

C++ and C applications written for the historical FreeBSD interface
get source level compatibility when building in C++ mode, or when
building with a C compiler with C11 generics support, provided that
the caller passes a fifth parameter of qsort_r() that exactly matches
the historical FreeBSD comparator function pointer type and does not
redefine the historical qsort_r(3) prototype in their source code.

Symbol versioning is used to keep old binaries working.

MFC: never
Relnotes: yes
Reviewed by: cem, imp, hps, pauamma
Differential revision: https://reviews.freebsd.org/D17083

show more ...

qsort.c: prevent undefined behavior

Mark Milliard has detected a case of undefined behavior with the LLVM
UBSAN. The mandoc program called qsort with a==NULL and n==0, which is
allowed by the POSIX

qsort.c: prevent undefined behavior

Mark Milliard has detected a case of undefined behavior with the LLVM
UBSAN. The mandoc program called qsort with a==NULL and n==0, which is
allowed by the POSIX standard. The qsort() in FreeBSD did not attempt
to perform any accesses using the passed pointer for n==0, but it did
add an offset to the pointer value, which is undefined behavior in
case of a NULL pointer. This operation has no adverse effects on any
achitecture supported by FreeBSD, but could be caught in more strict
environments.

After some discussion in the freebsd-current mail list, it was
concluded that the case of a==NULL and n!=0 should still be caught by
UBSAN (or cause a program abort due to an illegal access) in order to
not hide errors in programs incorrectly invoking qsort().

Only the the case of a==NULL and n==0 should be fixed to not perform
the undefined operation on a NULL pointer.

This commit makes qsort() exit before reaching the point of
potentially undefined behvior for the case n==0, but does not test
the value of a, since the result will not depend on whether this
pointer is NULL or an actual pointer to an array if n==0.

The issue found by Mark Milliard in the whatis command has been
reported to the upstream (OpenBSD) and has already been patched
there.

MFC after: 1 week

show more ...

libc qsort(3): Eliminate ambiguous sign comparison

The left side of the MIN() expression is the (signed) result of pointer
subtraction (ptrdiff_t). The right hand side is the also the (signed)
resu

libc qsort(3): Eliminate ambiguous sign comparison

The left side of the MIN() expression is the (signed) result of pointer
subtraction (ptrdiff_t). The right hand side is the also the (signed)
result of pointer subtraction, additionally subtracting the element size
('es'), which is unsigned size_t. This coerces the right-hand
expression into an unsigned value. MIN(signed, unsigned) triggers
-Wsign-compare.

Sorting elements of size greater than SSIZE_MAX is nonsensical, so we
can instead treat the element size as ssize_t, leaving the right-hand
result the same signedness as the left.

Reviewed by: arichardson, kib
Differential Revision: https://reviews.freebsd.org/D31292

show more ...

libc/qsort: Don't allow interposing recursive calls

This causes problems when using ASAN with a runtime older than 12.0 since
the intercept does not expect qsort() to call itself using an interposab

libc/qsort: Don't allow interposing recursive calls

This causes problems when using ASAN with a runtime older than 12.0 since
the intercept does not expect qsort() to call itself using an interposable
function call. This results in infinite recursion and stack exhaustion
when a binary compiled with -fsanitize=address calls qsort.
See also https://bugs.llvm.org/show_bug.cgi?id=46832 and
https://reviews.llvm.org/D84509 (ASAN runtime patch).

To prevent this problem, this patch uses a static helper function
for the actual qsort() implementation. This prevents interposition and
allows for direct calls. As a nice side-effect, we can also move the
qsort_s checks to the top-level function and out of the recursive calls.

Reviewed By: kib
Differential Revision: https://reviews.freebsd.org/D28133

show more ...

Merge ^/head r356848 through r356919.

Add qsort_s(3). Apart from the constraints, it also makes it easier
to port software written for Linux variant of qsort_r(3).

Reviewed by: kib, arichardson
MFC after: 2 weeks
Relnotes: yes
Sponsore

Add qsort_s(3). Apart from the constraints, it also makes it easier
to port software written for Linux variant of qsort_r(3).

Reviewed by: kib, arichardson
MFC after: 2 weeks
Relnotes: yes
Sponsored by: DARPA
Differential Revision: https://reviews.freebsd.org/D23174

show more ...

libc: Drop incorrect qsort optimization

As pointed out in the PR and the article linked below, the switch to
insertion sort in the BSD qsort code is based on a misunderstanding of
Knuth's TAOCP and

libc: Drop incorrect qsort optimization

As pointed out in the PR and the article linked below, the switch to
insertion sort in the BSD qsort code is based on a misunderstanding of
Knuth's TAOCP and is actually a pessimization. As demonstrated by the
added test, it is trivially easy to construct pathological input which
results in quadratic runtime. Without that misguided optimization, the
same input runs in nearly linearithmic time.

https://www.raygard.net/2022/02/26/Re-engineering-a-qsort-part-3

PR: 287089
MFC after: 1 week
Reviewed by: imp
Differential Revision: https://reviews.freebsd.org/D51907

show more ...

lib: Remove ancient SCCS tags.

Remove ancient SCCS tags from the tree, automated scripting, with two
minor fixup to keep things compiling. All the common forms in the tree
were removed with a perl s

lib: Remove ancient SCCS tags.

Remove ancient SCCS tags from the tree, automated scripting, with two
minor fixup to keep things compiling. All the common forms in the tree
were removed with a perl script.

Sponsored by: Netflix

show more ...

libc: Purge unneeded cdefs.h

These sys/cdefs.h are not needed. Purge them. They are mostly left-over
from the $FreeBSD$ removal. A few in libc are still required for macros
that cdefs.h defines. Kee

libc: Purge unneeded cdefs.h

These sys/cdefs.h are not needed. Purge them. They are mostly left-over
from the $FreeBSD$ removal. A few in libc are still required for macros
that cdefs.h defines. Keep those.

Sponsored by: Netflix
Differential Revision: https://reviews.freebsd.org/D42385

show more ...

Remove $FreeBSD$: one-line .c pattern

Remove /^[\s*]*__FBSDID\("\$FreeBSD\$"\);?\s*\n/

libc: Sorting is not needed when there are less than two elements

If there are less than two elements avoid executing the first
sorting loop. No functional change intended.

Reviewed by: kib@
MFC af

libc: Sorting is not needed when there are less than two elements

If there are less than two elements avoid executing the first
sorting loop. No functional change intended.

Reviewed by: kib@
MFC after: 1 week
Sponsored by: NVIDIA Networking
Differential Revision: https://reviews.freebsd.org/D39691

show more ...

libc: Add missing object size check to qsort_s(3)

When sorting, both the C11 standard (ISO/IEC 9899:2011, K.3.6.3.2) and
the ISO/IEC JTC1 SC22 WG14 N1172 standard, does not define objects of
zero si

libc: Add missing object size check to qsort_s(3)

When sorting, both the C11 standard (ISO/IEC 9899:2011, K.3.6.3.2) and
the ISO/IEC JTC1 SC22 WG14 N1172 standard, does not define objects of
zero size as undefined behaviour. However Microsoft's cpp-docs does.

Add proper checks for this. Found while working on bsort(3).

Reviewed by: kib@ and emaste@
MFC after: 1 week
Sponsored by: NVIDIA Networking
Differential Revision: https://reviews.freebsd.org/D39687

show more ...

Alter the prototype of qsort_r(3) to match POSIX, which adopted the
glibc-based interface.

Unfortunately, the glibc maintainers, despite knowing the existence
of the FreeBSD qsort_r(3) interface in

Alter the prototype of qsort_r(3) to match POSIX, which adopted the
glibc-based interface.

Unfortunately, the glibc maintainers, despite knowing the existence
of the FreeBSD qsort_r(3) interface in 2004 and refused to add the
same interface to glibc based on grounds of the lack of standardization
and portability concerns, has decided it was a good idea to introduce
their own qsort_r(3) interface in 2007 as a GNU extension with a
slightly different and incompatible interface.

With the adoption of their interface as POSIX standard, let's switch
to the same prototype, there is no need to remain incompatible.

C++ and C applications written for the historical FreeBSD interface
get source level compatibility when building in C++ mode, or when
building with a C compiler with C11 generics support, provided that
the caller passes a fifth parameter of qsort_r() that exactly matches
the historical FreeBSD comparator function pointer type and does not
redefine the historical qsort_r(3) prototype in their source code.

Symbol versioning is used to keep old binaries working.

MFC: never
Relnotes: yes
Reviewed by: cem, imp, hps, pauamma
Differential revision: https://reviews.freebsd.org/D17083

show more ...

qsort.c: prevent undefined behavior

Mark Milliard has detected a case of undefined behavior with the LLVM
UBSAN. The mandoc program called qsort with a==NULL and n==0, which is
allowed by the POSIX

qsort.c: prevent undefined behavior

Mark Milliard has detected a case of undefined behavior with the LLVM
UBSAN. The mandoc program called qsort with a==NULL and n==0, which is
allowed by the POSIX standard. The qsort() in FreeBSD did not attempt
to perform any accesses using the passed pointer for n==0, but it did
add an offset to the pointer value, which is undefined behavior in
case of a NULL pointer. This operation has no adverse effects on any
achitecture supported by FreeBSD, but could be caught in more strict
environments.

After some discussion in the freebsd-current mail list, it was
concluded that the case of a==NULL and n!=0 should still be caught by
UBSAN (or cause a program abort due to an illegal access) in order to
not hide errors in programs incorrectly invoking qsort().

Only the the case of a==NULL and n==0 should be fixed to not perform
the undefined operation on a NULL pointer.

This commit makes qsort() exit before reaching the point of
potentially undefined behvior for the case n==0, but does not test
the value of a, since the result will not depend on whether this
pointer is NULL or an actual pointer to an array if n==0.

The issue found by Mark Milliard in the whatis command has been
reported to the upstream (OpenBSD) and has already been patched
there.

MFC after: 1 week

show more ...

libc qsort(3): Eliminate ambiguous sign comparison

The left side of the MIN() expression is the (signed) result of pointer
subtraction (ptrdiff_t). The right hand side is the also the (signed)
resu

libc qsort(3): Eliminate ambiguous sign comparison

The left side of the MIN() expression is the (signed) result of pointer
subtraction (ptrdiff_t). The right hand side is the also the (signed)
result of pointer subtraction, additionally subtracting the element size
('es'), which is unsigned size_t. This coerces the right-hand
expression into an unsigned value. MIN(signed, unsigned) triggers
-Wsign-compare.

Sorting elements of size greater than SSIZE_MAX is nonsensical, so we
can instead treat the element size as ssize_t, leaving the right-hand
result the same signedness as the left.

Reviewed by: arichardson, kib
Differential Revision: https://reviews.freebsd.org/D31292

show more ...

libc/qsort: Don't allow interposing recursive calls

This causes problems when using ASAN with a runtime older than 12.0 since
the intercept does not expect qsort() to call itself using an interposab

libc/qsort: Don't allow interposing recursive calls

This causes problems when using ASAN with a runtime older than 12.0 since
the intercept does not expect qsort() to call itself using an interposable
function call. This results in infinite recursion and stack exhaustion
when a binary compiled with -fsanitize=address calls qsort.
See also https://bugs.llvm.org/show_bug.cgi?id=46832 and
https://reviews.llvm.org/D84509 (ASAN runtime patch).

To prevent this problem, this patch uses a static helper function
for the actual qsort() implementation. This prevents interposition and
allows for direct calls. As a nice side-effect, we can also move the
qsort_s checks to the top-level function and out of the recursive calls.

Reviewed By: kib
Differential Revision: https://reviews.freebsd.org/D28133

show more ...

Merge ^/head r356848 through r356919.

Add qsort_s(3). Apart from the constraints, it also makes it easier
to port software written for Linux variant of qsort_r(3).

Reviewed by: kib, arichardson
MFC after: 2 weeks
Relnotes: yes
Sponsore

Add qsort_s(3). Apart from the constraints, it also makes it easier
to port software written for Linux variant of qsort_r(3).

Reviewed by: kib, arichardson
MFC after: 2 weeks
Relnotes: yes
Sponsored by: DARPA
Differential Revision: https://reviews.freebsd.org/D23174

show more ...

libc qsort(3): stop aliasing.

Qsort swap code aliases the sorted array elements to ints and longs in
order to do swap by machine words. Unfortunately this breaks with the
full code optimization, e.

libc qsort(3): stop aliasing.

Qsort swap code aliases the sorted array elements to ints and longs in
order to do swap by machine words. Unfortunately this breaks with the
full code optimization, e.g. LTO.

See https://gcc.gnu.org/bugzilla/show_bug.cgi?id=83201 which seems to
reference code directly copied from libc/stdlib/qsort.c.

PR: 228780
Reported by: mliska@suse.cz
Reviewed by: brooks
Sponsored by: The FreeBSD Foundation
MFC after: 2 weeks
Differential revision: https://reviews.freebsd.org/D15714

show more ...