FreeBSD source tree https://cgit-dev.freebsd.org/src/atom?h=release%2F13.1.0 2022-03-04T19:47:02Z 2022-03-04T19:47:02Z Stefan Eßer se@FreeBSD.org 2022-01-13T10:09:38Z urn:sha1:19b00621b65fc4092417d33e12b471413f07228c 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. (cherry picked from commit d106f982a54cd299671ccad58bc456138a22ae7b) 2021-03-17T09:46:58Z Alex Richardson arichardson@FreeBSD.org 2021-02-18T10:12:29Z urn:sha1:8dc9d6a7b09f28458c1ad2848abdeb3f944c3132 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 (cherry picked from commit cbcfe28f9d5f975f97b7fb4a0d72bc9780eb0c46) 2020-01-20T11:40:07Z Edward Tomasz Napierala trasz@FreeBSD.org 2020-01-20T11:40:07Z urn:sha1:0d2fabfc0439acfdb5d369feb2961e1b91faa39e 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 2018-06-10T17:54:44Z Konstantin Belousov kib@FreeBSD.org 2018-06-10T17:54:44Z urn:sha1:6609261660989cac8bbb8acbf94d4e80d8c59c70 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 2017-11-20T19:49:47Z Pedro F. Giffuni pfg@FreeBSD.org 2017-11-20T19:49:47Z urn:sha1:8a16b7a18f5d0b031f09832fd7752fba717e2a97 Mainly focus on files that use BSD 3-Clause license. The Software Package Data Exchange (SPDX) group provides a specification to make it easier for automated tools to detect and summarize well known opensource licenses. We are gradually adopting the specification, noting that the tags are considered only advisory and do not, in any way, superceed or replace the license texts. Special thanks to Wind River for providing access to "The Duke of Highlander" tool: an older (2014) run over FreeBSD tree was useful as a starting point. 2017-05-19T04:59:12Z Xin LI delphij@FreeBSD.org 2017-05-19T04:59:12Z urn:sha1:ca1578f0c013f6e0e88142ffa647724d64a66fb3 always perform recursion on the left partition, then use a tail call to handle the right partition. In the worst case this could require O(N) levels of recursions. Reduce the possible recursion level to log2(N) by always recursing on the smaller partition instead. Obtained from: PostgreSQL 9d6077abf9d6efd992a59f05ef5aba981ea32096 2017-05-19T04:44:14Z Xin LI delphij@FreeBSD.org 2017-05-19T04:44:14Z urn:sha1:a3f893fc61cd2f4f6e8a065ab579dc94490dce18 Inspired by: OpenBSD src/lib/libc/stdlib/qsort.c,v 1.11 2015-09-20T20:24:28Z Craig Rodrigues rodrigc@FreeBSD.org 2015-09-20T20:24:28Z urn:sha1:f98e0c9dd831748338a7856c0e98678ea8181d19 2015-03-05T17:17:11Z Pedro F. Giffuni pfg@FreeBSD.org 2015-03-05T17:17:11Z urn:sha1:2eaea119b836b317143216ca21a3a87a987175a5 Basically spaces vs. tabs. No functional change. 2015-03-05T17:00:39Z Pedro F. Giffuni pfg@FreeBSD.org 2015-03-05T17:00:39Z urn:sha1:9382fabf1f68297c14b37fbec3614c0c94274524 Implement a small enhancement to the original qsort implementation: If the data is 32 bit aligned we can side-step the long type version and use int instead. The change brings a modest but significant improvement in 32 bit workloads. Relnotes: yes PR: 135718 Taken from: ache