To explain the situation, I construct a similar setup, but simplify the issue significantly to demonstrate what the problem is, why the patch really solves the problem, and what the real solution is.

Suppose that we have a structure defined in the following manner and a function that is used to find a substring in a larger string. (Now, don't start complaining that I should use `strstr(3)`

instead. It is true, but this is just an example and the real fulltext search does a lot more than this.)

typedef struct match { unsigned int beg; unsigned int end; } match; match find_substr(char const *str, char const *substr);The

`match`

structure hold the positions of the beginning and the end of the substring found, and since the position is guaranteed to be positive, it is declared as `unsigned`

.Inside the fulltext search code, we have something that looks like this, which is used to decide if this is the beginning of a word or just something that is inside a word:

if (... && !isalnum(p0[m[1].beg - 1])) { /* Do something if the character before the first one that matched is not a word character. */ }Now, when running on a 64-bit machine... and under certain circumstances... MySQL BUG#11392 was triggered. After some investigations, the following patch was committed which proved to solve the problem (I've highlighted the changed part of the line):

- if (... && !isalnum(Everybody who's a little familiar with C knows thatp0[m[1].beg - 1])) { + if (... && !isalnum(*(p0 + m[1].beg - 1))) {

`ptr[expr]`

is just another way to write `*(ptr + expr)`

, so this could should not really change anything at all and could therefore not fix the bug. Right?Wrong.

The expression `ptr[expr]`

is equivalent to the expression `*(ptr + (expr))`

, and please note the additional parentheses around the expression. This seems to be quite obvious, but please bear with me for a little while more.

The special quirk on the compiler of this 64-bit machine is that pointers are of size 8 (bytes), while `sizeof(unsigned int)`

is **4**. (I can't know for sure why the compiler is implemented this way, but my guess is that it is so that each of the sizes 1, 2, 4, and 8 (bytes) can be represented with a basic type in C89. Remember that `long long`

does not exist in C89.)

While doing the searching, the start position of the match ended up at (unsigned) zero. For machines where the size of a pointer is the same as the size of an `unsigned int`

(and where negative integers are represented using two-complement numbers, but as far as I know that is ubiquitous), `p0[0U-1] == *(p0 + (0U - 1)) == *(p0 + UINT_MAX) == p0[-1]`

, so all is well (in this case, `*(p0 - 1)`

was a valid memory location).

However, for this 64 bit machine where the pointers are 64 bits instead of 32 while the `unsigned int`

is 32 bits, the addition before the patch ends up very far away into the array (in this case far out of the allocated memory), so there were a segmentation fault. However, for the patched code we have `*(p0 + 0U - 1) == *((p0 + 0U) - 1) == *(p0 - 1)`

, so it works even on this machine with this compiler.

So, the basic problem is that an unsigned integral type is used to index the array, and that integral type is smaller than the size of the pointer. In that case, it is important in what order the computations are made. Since the natural approach is to use array index notation, we need to find a type for `beg`

that is good for this use on any machine, so what to pick? We need a signed integral type, since we need to ensure that -1 really becomes -1 and does not cause a wraparound as unsigned arithmetics do. We also need it to be large enough to move backwards and forwards from any position in an object to any other position in an object.

The immediate candidate for this is `ptrdiff_t`

, which is supposed to be able to represent the difference between two pointers. So what does the standard say regarding this? Well... not much actually. From 7.1.7 (the TC3 draft is available as ISO/IEC 9899:TC3 on

```
````ptrdiff_t`

[...] is the signed integer type of the result of subtracting two pointers

So that seems to be all well and good, however, from 6.5.6 §9, we have (emphasis is mine):
When two pointers are subtracted [...] the result is the difference of the subscripts of the two array elements. The size of the result is implementation-defined, and its type (a signed integer type) isSo, in essence, the type`ptrdiff_t`

defined in the`<stddef.h>`

; header.If the result is not representable in an object of that type, the behavior is undefined.In other words, if the expressions P and Q point to, respectively, the i-th and j-th elements of an array object, the expression (P)-(Q) has the value i-j provided the value fits in an object of type`ptrdiff_t`

.

`ptrdiff_t`

is a signed integral type that *might*be able to represent the difference between two pointer, so we cannot rely on

`ptrdiff_t`

.
This leaves `size_t`

, which is an unsigned integral type large enough to hold the size of *any*object. Now, it seems strange that I advocate using an unsigned type when I pointed out a problem with it above, but the problem is that the

*wraparound*caused by using an unsigned integer that is smaller than the pointer size caused the problem. So, if

`sizeof(X*) == sizeof(size_t)`

, all will work as expected.
Now, as usual when it comes to standard issues, there are some caveats. For machines with segmented memory (like 80486, but there are others), the compilers have different of memory types and hence different kinds of pointers. For example `__far`

,`__near`

, and `__huge`

. So, to illustrate the problem, we assume we have a 16-bit machine with 8-bit segment number and the pointers are `__far`

pointers, i.e., each pointer is the address within the segment plus a segment address. This means that `sizeof(void*) == 3`

. For this memory model, it is usually the case that any object defined has to fit within a single segment and may not border two segments. This means that `sizeof(size_t) == 2`

. Since `sizeof(size_t)`

is less than `sizeof(void*)`

, we have the same problem again.

So, what is the moral of the story? Well... if you need to have a type to represent an index into an array, use `size_t`

and make sure that `sizeof(size_t) == sizeof(void*)`

.

If `sizeof(size_t) < sizeof(void*)`

, you have three (not necessarily exclusive) options:

- Scream and curse
- Pick a signed integral type strictly larger than
`size_t`

. It will be horribly inefficient, but it will work - Make sure that any expression used for array indexing
*never*become negative by expanding the array indexing manually as was done in the patch above.

## No comments:

Post a Comment