glibc.git/manual/search.texi, branch master Unnamed repository; edit this file 'description' to name the repository. Implement C23 const-preserving standard library macros 2025-11-20T19:31:04+00:00 Joseph Myers josmyers@redhat.com 2025-11-20T19:30:27+00:00 cd748a63ab1a7ae846175c532a3daab341c62690 C23 makes various standard library functions, that return a pointer into an input array, into macros that return a pointer to const when the relevant argument passed to the macro is a pointer to const. (The requirement is for macros, with the existing function types applying when macro expansion is suppressed. When a null pointer constant is passed, such as integer 0, that's the same as a pointer to non-const.) Implement this feature. This only applies to C, not C++, since such macros are not an appropriate way of doing this for C++ and all the affected functions other than bsearch have overloads to implement an equivalent feature for C++ anyway. Nothing is done to apply such a change to any non-C23 functions with the same property of returning a pointer into an input array. The feature is also disabled when _LIBC is defined, since there are various places in glibc that either redefine these identifiers as macros, or define the functions themselves, and would need changing to work in the presence of these macro definitions. A natural question is whether we should in fact change those places and not disable the macro definitions for _LIBC. If so, we'd need a solution for the places in glibc that define the macro *before* including the relevant header (in order in effect to disable the header declaration of the function by renaming that declaration). One testcase has #undef added to avoid conflicting with this feature and another has const added; -Wno-discarded-qualifiers is added for building zic (but could be removed once there's a new upstream tzcode release that's const-safe with this C23 change and glibc has updated to code from that new release). Probably other places in glibc proper would need const added if we remove the _LIBC conditionals. Another question would be whether some GCC extension should be added to support this feature better with macros that only expand each argument once (as well as reducing duplication of diagnostics for bad usages such as non-pointer and pointer-to-volatile-qualfied arguments). Tested for x86_64. 
C23 makes various standard library functions, that return a pointer
into an input array, into macros that return a pointer to const when
the relevant argument passed to the macro is a pointer to const.  (The
requirement is for macros, with the existing function types applying
when macro expansion is suppressed.  When a null pointer constant is
passed, such as integer 0, that's the same as a pointer to non-const.)

Implement this feature.  This only applies to C, not C++, since such
macros are not an appropriate way of doing this for C++ and all the
affected functions other than bsearch have overloads to implement an
equivalent feature for C++ anyway.  Nothing is done to apply such a
change to any non-C23 functions with the same property of returning a
pointer into an input array.

The feature is also disabled when _LIBC is defined, since there are
various places in glibc that either redefine these identifiers as
macros, or define the functions themselves, and would need changing to
work in the presence of these macro definitions.  A natural question
is whether we should in fact change those places and not disable the
macro definitions for _LIBC.  If so, we'd need a solution for the
places in glibc that define the macro *before* including the relevant
header (in order in effect to disable the header declaration of the
function by renaming that declaration).

One testcase has #undef added to avoid conflicting with this feature
and another has const added; -Wno-discarded-qualifiers is added for
building zic (but could be removed once there's a new upstream tzcode
release that's const-safe with this C23 change and glibc has updated
to code from that new release).  Probably other places in glibc proper
would need const added if we remove the _LIBC conditionals.

Another question would be whether some GCC extension should be added
to support this feature better with macros that only expand each
argument once (as well as reducing duplication of diagnostics for bad
usages such as non-pointer and pointer-to-volatile-qualfied
arguments).

Tested for x86_64.
Fix bsearch, qsort doc to match POSIX better 2024-04-06T17:10:32+00:00 Paul Eggert eggert@cs.ucla.edu 2024-04-06T15:44:01+00:00 57581acd9559217e859fdac693145ce6399f4d70 * manual/search.texi (Array Search Function): Correct the statement about lfind’s mean runtime: it is proportional to a number (not that number), and this is true only if random elements are searched for. Relax the constraint on bsearch’s array argument: POSIX says it need not be sorted, only partially sorted. Say that the first arg passed to bsearch’s comparison function is the key, and the second arg is an array element, as POSIX requires. For bsearch and qsort, say that the comparison function should not alter the array, as POSIX requires. For qsort, say that the comparison function must define a total order, as POSIX requires, that it should not depend on element addresses, that the original array index can be used for stable sorts, and that if qsort still works if memory allocation fails. Be more consistent in calling the array elements “elements” rather than “objects”. Co-authored-by: Zack Weinberg <zack@owlfolio.org> 
* manual/search.texi (Array Search Function):
Correct the statement about lfind’s mean runtime:
it is proportional to a number (not that number),
and this is true only if random elements are searched for.
Relax the constraint on bsearch’s array argument:
POSIX says it need not be sorted, only partially sorted.
Say that the first arg passed to bsearch’s comparison function
is the key, and the second arg is an array element, as
POSIX requires.  For bsearch and qsort, say that the
comparison function should not alter the array, as POSIX
requires.  For qsort, say that the comparison function
must define a total order, as POSIX requires, that
it should not depend on element addresses, that
the original array index can be used for stable sorts,
and that if qsort still works if memory allocation fails.
Be more consistent in calling the array elements
“elements” rather than “objects”.

Co-authored-by: Zack Weinberg <zack@owlfolio.org>
stdlib: fix qsort example in manual 2024-02-02T01:54:21+00:00 Paul Eggert eggert@cs.ucla.edu 2024-02-01T19:52:46+00:00 e7b90e6e605cf236d4bd79e4930cd6a46f9932c7 * manual/search.texi (Comparison Functions, Array Sort Function): Sort an array of long ints, not doubles, to avoid hassles with NaNs. Reviewed-by: Siddhesh Poyarekar <siddhesh@sourceware.org> 
* manual/search.texi (Comparison Functions, Array Sort Function):
Sort an array of long ints, not doubles, to avoid hassles
with NaNs.

Reviewed-by: Siddhesh Poyarekar <siddhesh@sourceware.org>
stdlib: Reinstate stable mergesort implementation on qsort 2024-01-15T18:58:35+00:00 Adhemerval Zanella adhemerval.zanella@linaro.org 2024-01-15T14:07:21+00:00 709fbd3ec3595f2d1076b4fec09a739327459288 The mergesort removal from qsort implementation (commit 03bf8357e8) had the side-effect of making sorting nonstable. Although neither POSIX nor C standard specify that qsort should be stable, it seems that it has become an instance of Hyrum's law where multiple programs expect it. Also, the resulting introsort implementation is not faster than the previous mergesort (which makes the change even less appealing). This patch restores the previous mergesort implementation, with the exception of machinery that checks the resulting allocation against the _SC_PHYS_PAGES (it only adds complexity and the heuristic not always make sense depending on the system configuration and load). The alloca usage was replaced with a fixed-size buffer. For the fallback mechanism, the implementation uses heapsort. It is simpler than quicksort, and it does not suffer from adversarial inputs. With memory overcommit, it should be rarely triggered. The drawback is mergesort requires O(n) extra space, and since it is allocated with malloc the function is AS-signal-unsafe. It should be feasible to change it to use mmap, although I am not sure how urgent it is. The heapsort is also nonstable, so programs that require a stable sort would still be subject to this latent issue. The tst-qsort5 is removed since it will not create quicksort adversarial inputs with the current qsort_r implementation. Checked on x86_64-linux-gnu and aarch64-linux-gnu. Reviewed-by: Florian Weimer <fweimer@redhat.com> 
The mergesort removal from qsort implementation (commit 03bf8357e8)
had the side-effect of making sorting nonstable.  Although neither
POSIX nor C standard specify that qsort should be stable, it seems
that it has become an instance of Hyrum's law where multiple programs
expect it.

Also, the resulting introsort implementation is not faster than
the previous mergesort (which makes the change even less appealing).

This patch restores the previous mergesort implementation, with the
exception of machinery that checks the resulting allocation against
the _SC_PHYS_PAGES (it only adds complexity and the heuristic not
always make sense depending on the system configuration and load).
The alloca usage was replaced with a fixed-size buffer.

For the fallback mechanism, the implementation uses heapsort.  It is
simpler than quicksort, and it does not suffer from adversarial
inputs.  With memory overcommit, it should be rarely triggered.

The drawback is mergesort requires O(n) extra space, and since it is
allocated with malloc the function is AS-signal-unsafe.  It should be
feasible to change it to use mmap, although I am not sure how urgent
it is.  The heapsort is also nonstable, so programs that require a
stable sort would still be subject to this latent issue.

The tst-qsort5 is removed since it will not create quicksort adversarial
inputs with the current qsort_r implementation.

Checked on x86_64-linux-gnu and aarch64-linux-gnu.
Reviewed-by: Florian Weimer <fweimer@redhat.com>
stdlib: Remove use of mergesort on qsort (BZ 21719) 2023-10-31T17:18:05+00:00 Adhemerval Zanella adhemerval.zanella@linaro.org 2023-10-03T12:22:50+00:00 03bf8357e8291857a435afcc3048e0b697b6cc04 This patch removes the mergesort optimization on qsort implementation and uses the introsort instead. The mergesort implementation has some issues: - It is as-safe only for certain types sizes (if total size is less than 1 KB with large element sizes also forcing memory allocation) which contradicts the function documentation. Although not required by the C standard, it is preferable and doable to have an O(1) space implementation. - The malloc for certain element size and element number adds arbitrary latency (might even be worse if malloc is interposed). - To avoid trigger swap from memory allocation the implementation relies on system information that might be virtualized (for instance VMs with overcommit memory) which might lead to potentially use of swap even if system advertise more memory than actually has. The check also have the downside of issuing syscalls where none is expected (although only once per execution). - The mergesort is suboptimal on an already sorted array (BZ#21719). The introsort implementation is already optimized to use constant extra space (due to the limit of total number of elements from maximum VM size) and thus can be used to avoid the malloc usage issues. Resulting performance is slower due the usage of qsort, specially in the worst-case scenario (partialy or sorted arrays) and due the fact mergesort uses a slight improved swap operations. This change also renders the BZ#21719 fix unrequired (since it is meant to fix the sorted input performance degradation for mergesort). The manual is also updated to indicate the function is now async-cancel safe. Checked on x86_64-linux-gnu. Reviewed-by: Noah Goldstein <goldstein.w.n@gmail.com> 
This patch removes the mergesort optimization on qsort implementation
and uses the introsort instead.  The mergesort implementation has some
issues:

  - It is as-safe only for certain types sizes (if total size is less
    than 1 KB with large element sizes also forcing memory allocation)
    which contradicts the function documentation.  Although not required
    by the C standard, it is preferable and doable to have an O(1) space
    implementation.

  - The malloc for certain element size and element number adds
    arbitrary latency (might even be worse if malloc is interposed).

  - To avoid trigger swap from memory allocation the implementation
    relies on system information that might be virtualized (for instance
    VMs with overcommit memory) which might lead to potentially use of
    swap even if system advertise more memory than actually has.  The
    check also have the downside of issuing syscalls where none is
    expected (although only once per execution).

  - The mergesort is suboptimal on an already sorted array (BZ#21719).

The introsort implementation is already optimized to use constant extra
space (due to the limit of total number of elements from maximum VM
size) and thus can be used to avoid the malloc usage issues.

Resulting performance is slower due the usage of qsort, specially in the
worst-case scenario (partialy or sorted arrays) and due the fact
mergesort uses a slight improved swap operations.

This change also renders the BZ#21719 fix unrequired (since it is meant
to fix the sorted input performance degradation for mergesort).  The
manual is also updated to indicate the function is now async-cancel
safe.

Checked on x86_64-linux-gnu.
Reviewed-by: Noah Goldstein <goldstein.w.n@gmail.com>
manual: Correct description of ENTRY [BZ #17183] 2021-02-04T14:22:12+00:00 Florian Weimer fweimer@redhat.com 2021-02-04T14:02:38+00:00 2d8a22cdecca225068f56bcfee862696d5b4a83b The struct tag is actually entry (not ENTRY). The data member has type void *, and it can point to binary data. Only the key member is required to be a null-terminated string. Reviewed-by: Arjun Shankar <arjun@redhat.com> 
The struct tag is actually entry (not ENTRY).  The data member has
type void *, and it can point to binary data.  Only the key member is
required to be a null-terminated string.

Reviewed-by: Arjun Shankar <arjun@redhat.com>
manual: Adjust twalk_r documentation. 2019-05-14T19:56:56+00:00 Carlos O'Donell carlos@redhat.com 2019-05-14T19:33:02+00:00 6807f47b81bcae3874277f5480683ebeb7dfcf89 Reviewed-by: Florian Weimer <fweimer@redhat.com> 
Reviewed-by: Florian Weimer <fweimer@redhat.com>
misc: Add twalk_r function 2019-05-02T09:42:51+00:00 Florian Weimer fweimer@redhat.com 2019-05-02T09:42:51+00:00 7b807a35a8dc63f9742cecf0fc3db46c30e28b0d The twalk function is very difficult to use in a multi-threaded program because there is no way to pass external state to the iterator function. Reviewed-by: Carlos O'Donell <carlos@redhat.com> Reviewed-by: Adhemerval Zanella <adhemerval.zanella@linaro.org> 
The twalk function is very difficult to use in a multi-threaded
program because there is no way to pass external state to the
iterator function.

Reviewed-by: Carlos O'Donell <carlos@redhat.com>
Reviewed-by: Adhemerval Zanella <adhemerval.zanella@linaro.org>
manual: Use @code{errno} instead of @var{errno} [BZ #24063] 2019-01-07T10:42:04+00:00 Florian Weimer fweimer@redhat.com 2019-01-07T10:42:04+00:00 010fe2317732b009e096cba9df14d5a56ec28de9 @var is intended for placeholders (such as function parameters). Actual variables need to use @code because @var causes upper-case output, resulting in a different C identifier. 
@var is intended for placeholders (such as function parameters).
Actual variables need to use @code because @var causes upper-case
output, resulting in a different C identifier.
manual: Replace summary.awk with summary.pl. 2017-06-16T04:26:20+00:00 Rical Jasan ricaljasan@pacific.net 2017-06-16T04:12:39+00:00 d08a7e4cbe43d5e4e4b14dea950fea623d96c1a1 The Summary is now generated from @standards, and syntax-checking is performed. If invalid @standards syntax is detected, summary.pl will fail, reporting all errors. Failure and error reporting is disabled for now, however, since much of the manual is still incomplete wrt. header and standards annotations. Note that the sorting order of the Summary has changed; summary.pl respects the locale, like summary.awk did, but the use of LC_ALL=C is introduced in the Makefile. Other notable deviations are improved detection of the annotated elements' names, which are used for sorting, and improved detection of the @node used to reference into the manual. The most noticeable difference in the rendered Summary is that entries may now contain multiple lines, one for each header and standard combination. summary.pl accepts a `--help' option, which details the expected syntax of @standards. If errors are reported, the user is directed to this feature for further information. * manual/Makefile: Generate summary.texi with summary.pl. Force use of the C locale. Update Perl dependency comment. * manual/header.texi: Update reference to summary.awk. * manual/macros.texi: Refer authors to `summary.pl --help'. * manual/summary.awk: Remove file. * manual/summary.pl: New file. Generate summary.texi, and check for @standards-related syntax errors. * manual/argp.texi: Convert header and standards @comments to @standards. * manual/arith.texi: Likewise. * manual/charset.texi: Likewise. * manual/conf.texi: Likewise. * manual/creature.texi: Likewise. * manual/crypt.texi: Likewise. * manual/ctype.texi: Likewise. * manual/debug.texi: Likewise. * manual/errno.texi: Likewise. * manual/filesys.texi: Likewise. * manual/getopt.texi: Likewise. * manual/job.texi: Likewise. * manual/lang.texi: Likewise. * manual/llio.texi: Likewise. * manual/locale.texi: Likewise. * manual/math.texi: Likewise. * manual/memory.texi: Likewise. * manual/message.texi: Likewise. * manual/pattern.texi: Likewise. * manual/pipe.texi: Likewise. * manual/process.texi: Likewise. * manual/resource.texi: Likewise. * manual/search.texi: Likewise. * manual/setjmp.texi: Likewise. * manual/signal.texi: Likewise. * manual/socket.texi: Likewise. * manual/startup.texi: Likewise. * manual/stdio.texi: Likewise. * manual/string.texi: Likewise. * manual/sysinfo.texi: Likewise. * manual/syslog.texi: Likewise. * manual/terminal.texi: Likewise. * manual/threads.texi: Likewise. * manual/time.texi: Likewise. * manual/users.texi: Likewise. 
The Summary is now generated from @standards, and syntax-checking is
performed.  If invalid @standards syntax is detected, summary.pl will
fail, reporting all errors.  Failure and error reporting is disabled
for now, however, since much of the manual is still incomplete
wrt. header and standards annotations.

Note that the sorting order of the Summary has changed; summary.pl
respects the locale, like summary.awk did, but the use of LC_ALL=C is
introduced in the Makefile.  Other notable deviations are improved
detection of the annotated elements' names, which are used for
sorting, and improved detection of the @node used to reference into
the manual.  The most noticeable difference in the rendered Summary is
that entries may now contain multiple lines, one for each header and
standard combination.

summary.pl accepts a `--help' option, which details the expected
syntax of @standards.  If errors are reported, the user is directed to
this feature for further information.

	* manual/Makefile: Generate summary.texi with summary.pl.
	Force use of the C locale.  Update Perl dependency comment.
	* manual/header.texi: Update reference to summary.awk.
	* manual/macros.texi: Refer authors to `summary.pl --help'.
	* manual/summary.awk: Remove file.
	* manual/summary.pl: New file.  Generate summary.texi, and
	check for @standards-related syntax errors.
	* manual/argp.texi: Convert header and standards @comments to
	@standards.
	* manual/arith.texi: Likewise.
	* manual/charset.texi: Likewise.
	* manual/conf.texi: Likewise.
	* manual/creature.texi: Likewise.
	* manual/crypt.texi: Likewise.
	* manual/ctype.texi: Likewise.
	* manual/debug.texi: Likewise.
	* manual/errno.texi: Likewise.
	* manual/filesys.texi: Likewise.
	* manual/getopt.texi: Likewise.
	* manual/job.texi: Likewise.
	* manual/lang.texi: Likewise.
	* manual/llio.texi: Likewise.
	* manual/locale.texi: Likewise.
	* manual/math.texi: Likewise.
	* manual/memory.texi: Likewise.
	* manual/message.texi: Likewise.
	* manual/pattern.texi: Likewise.
	* manual/pipe.texi: Likewise.
	* manual/process.texi: Likewise.
	* manual/resource.texi: Likewise.
	* manual/search.texi: Likewise.
	* manual/setjmp.texi: Likewise.
	* manual/signal.texi: Likewise.
	* manual/socket.texi: Likewise.
	* manual/startup.texi: Likewise.
	* manual/stdio.texi: Likewise.
	* manual/string.texi: Likewise.
	* manual/sysinfo.texi: Likewise.
	* manual/syslog.texi: Likewise.
	* manual/terminal.texi: Likewise.
	* manual/threads.texi: Likewise.
	* manual/time.texi: Likewise.
	* manual/users.texi: Likewise.