heapsort and heapsort_r: Undefined behavior due to out of bounds pointer arithmetic

[smcpeak]

The heapsort and heapsort_r functions both contain this code:

/*
 * Items are numbered from 1 to nmemb, so offset from size bytes
 * below the starting address.
 */
base = (char*)vbase - size;

Here, vbase is a pointer to the start of the array to sort and size is the element size. The purpose of the arithmetic is to allow base to be treated as a 1-indexed array rather than 0-indexed. But this conflicts with C11 6.5.6/8:

When an expression that has integer type is added to or subtracted from a pointer, the
result has the type of the pointer operand. If the pointer operand points to an element of
an array object, and the array is large enough, the result points to an element offset from
the original element such that the difference of the subscripts of the resulting and original
array elements equals the integer expression. [...] If both the pointer
operand and the result point to elements of the same array object, or one past the last
element of the array object, the evaluation shall not produce an overflow; otherwise, the
behavior is undefined.

Here, the result does not point to the array object (nor one past the end) because it would point to a location size bytes before the first element, hence the behavior is undefined. (For completeness: a caller could fix this by allocating extra space at the start of the array. But, for example, the tests in test/stdlib/heapsort.c do not do so.)

I am not aware of any practical adverse consequence of this. I found it because I'm building a tool to enforce some of the C pointer rules, and am applying it to this C library. The tool has a mechanism to work around specific instances, so this isn't a problem for that effort. I'm just filing this to notify you of the issue and for my own record-keeping. I won't be offended if you close it as irrelevant, although I am not advising that (or any) course of action.

[phillipjohnston]

I'm happy to hear about any and all such instances. Part of my goal back-in-the-day when I started this library was cleaning up long-used libc code that was worrying.