embeddedartistry / embeddedartistry/libc

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

Open
#181 1 comment 0 reactions 0 assignees View on GitHub
Dominant language
C
Stars
661
Forks
78
PR merge metrics
No merged PRs in 30d

Description

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.

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.