Pointer arithmetic across subobject boundaries

2020-06-30 05:17发布

Does the following code (which performs pointer arithmetic across subobject boundaries) have well-defined behavior for types T for which it compiles (which, in C++11, does not not necessarily have to be POD) or any subset thereof?

#include <cassert>
#include <cstddef>

template<typename T>
struct Base
{
    // ensure alignment
    union
    {
        T initial;
        char begin;
    };
};

template<typename T, size_t N>
struct Derived : public Base<T>
{
    T rest[N - 1];
    char end;
};

int main()
{
    Derived<float, 10> d;
    assert(&d.rest[9] - &d.initial == 10);
    assert(&d.end - &d.begin == sizeof(float) * 10);
    return 0;
}

LLVM uses a variation of the above technique in the implementation of an internal vector type which is optimized to initially use the stack for small arrays but switches to a heap-allocated buffer once over initial capacity. (The reason for doing it this way is not clear from this example but is apparently to reduce template code bloat; this is clearer if you look through the code.)

NOTE: Before anyone complains, this is not exactly what they are doing and it might be that their approach is more standards-compliant than what I have given here, but I wanted to ask about the general case.

Obviously, it works in practice, but I'm curious if anything in the standard guarantees for that to be the case. I'm inclined to say no, given N3242/expr.add:

When two pointers to elements of the same array object are subtracted, the result is the difference of the subscripts of the two array elements...Moreover, if the expression P points either to an element of an array object or one past the last element of an array object, and the expression Q points to the last element of the same array object, the expression ((Q)+1)-(P) has the same value as ((Q)-(P))+1 and as -((P)-((Q)+1)), and has the value zero if the expression P points one past the last element of the array object, even though the expression (Q)+1 does not point to an element of the array object. ...Unless both pointers point to elements of the same array object, or one past the last element of the array object, the behavior is undefined.

But theoretically, the middle part of the above quote, combined with class layout and alignment guarantees, might allow the following (minor) adjustment to be valid:

#include <cassert>
#include <cstddef>

template<typename T>
struct Base
{
    T initial[1];
};

template<typename T, size_t N>
struct Derived : public Base<T>
{
    T rest[N - 1];
};

int main()
{
    Derived<float, 10> d;
    assert(&d.rest[9] - &d.rest[0] == 9);
    assert(&d.rest[0] == &d.initial[1]);
    assert(&d.rest[0] - &d.initial[0] == 1);
    return 0;
}

which combined with various other provisions concerning union layout, convertibility to and from char *, etc., might arguably make the original code valid as well. (The main problem is the lack of transitivity in the definition of pointer arithmetic given above.)

Anyone know for sure? N3242/expr.add seems to make clear that pointers must belong to the same "array object" for it to be defined, but it could hypothetically be the case that other guarantees in the standard, when combined together, might require a definition anyway in this case in order to remain logically self-consistent. (I'm not betting on it, but I would it's at least conceivable.)

EDIT: @MatthieuM raises the objection that this class is not standard-layout and therefore might not be guaranteed to contain no padding between the base subobject and the first member of the derived, even if both are aligned to alignof(T). I'm not sure how true that is, but that opens up the following variant questions:

  • Would this be guaranteed to work if the inheritance were removed?

  • Would &d.end - &d.begin >= sizeof(float) * 10 be guaranteed even if &d.end - &d.begin == sizeof(float) * 10 were not?

LAST EDIT @ArneMertz argues for a very close reading of N3242/expr.add (yes, I know I'm reading a draft, but it's close enough), but does the standard really imply that the following has undefined behavior then if the swap line is removed? (same class definitions as above)

int main()
{
    Derived<float, 10> d;
    bool aligned;
    float * p = &d.initial[0], * q = &d.rest[0];

    ++p;
    if((aligned = (p == q)))
    {
        std::swap(p, q); // does it matter if this line is removed?
        *++p = 1.0;
    }

    assert(!aligned || d.rest[1] == 1.0);

    return 0;
}

Also, if == is not strong enough, what if we take advantage of the fact that std::less forms a total order over pointers, and change the conditional above to:

    if((aligned = (!std::less<float *>()(p, q) && !std::less<float *>()(q, p))))

Is code that assumes that two equal pointers point to the same array object really broken according to a strict reading of the standard?

EDIT Sorry, just want to add one more example, to eliminate the standard layout issue:

#include <cassert>
#include <cstddef>
#include <utility>
#include <functional>

// standard layout
struct Base
{
    float initial[1];
    float rest[9];
};

int main()
{
    Base b;
    bool aligned;
    float * p = &b.initial[0], * q = &b.rest[0];

    ++p;
    if((aligned = (p == q)))
    {
        std::swap(p, q); // does it matter if this line is removed?
        *++p = 1.0;
        q = &b.rest[1];
        // std::swap(p, q); // does it matter if this line is added?
        p -= 2; // is this UB?
    }
    assert(!aligned || b.rest[1] == 1.0);
    assert(p == &b.initial[0]);

    return 0;
}

1条回答
贪生不怕死
2楼-- · 2020-06-30 05:21

Updated: This answer at first missed some information and thus lead to wrong conclusions.

In your examples, initial and rest are clearly distinct (array) objects, so comparing pointers to initial (or its elements) with pointers to rest (or its elements) is

  • UB, if you use the difference of the pointers. (§5.7,6)
  • unspecified, if you use relational operators (§5.9,2)
  • well defined for == (So the second snipped is good, see below)

First snippet:

Building the difference in the first snippet is undefined behavior, for the quote you provided (§5.7,6):

Unless both pointers point to elements of the same array object, or one past the last element of the array object, the behavior is undefined.

To clarify the UB parts of the first example code:

//first example
int main()
{
    Derived<float, 10> d;
    assert(&d.rest[9] - &d.initial == 10);            //!!! UB !!!
    assert(&d.end - &d.begin == sizeof(float) * 10);  //!!! UB !!! (*)
    return 0;
}

The line marked with (*) is interesting: d.begin and d.end are not elements of the same array and therefore the operation results in UB. This is despite the fact you may reinterpret_cast<char*>(&d) and have both their addresses in the resulting array. But since that array is a representation of all of d, it's not to be seen as an access to parts of d. So while that operation probably will just work and give the expected result on any implementation one can dream of, it still is UB - as a matter of definition.

Second snippet:

This is actually well defined behavior, but implementation defined result:

int main()
{
    Derived<float, 10> d;
    assert(&d.rest[9] - &d.rest[0] == 9);
    assert(&d.rest[0] == &d.initial[1]);         //(!)
    assert(&d.initial[1] - &d.initial[0] == 1);
    return 0;
}

The line marked with (!) is not ub, but its result is implementation defined, since padding, alignment and the mentioned instumentation might play a role. But if that assertion would hold, you could use the two object parts like one array.

You would know that rest[0] would lay immediately after initial[0] in memory. At first sight, you could not easily use the equality:

  • initial[1] would point one-past-the-end of initial, dereferencing it is UB.
  • rest[-1] is clearly out of bounds.

But enters §3.9.2,3:

If an object of type T is located at an address A, a pointer of type cv T* whose value is the address A is said to point to that object, regardless of how the value was obtained. [ Note: For instance, the address one past the end of an array (5.7) would be considered to point to an unrelated object of the array’s element type that might be located at that address.

So provided that &initial[1] == &rest[0], it will be binary the same as if there was only one array, and all will be ok.

You could iterate over both arrays, since you could apply some "pointer context switch" at the boundaries. So to your last snippet: the swap is not needed!

However, there are some caveats: rest[-1] is UB, and so would be initial[2], because of §5.7,5:

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.

(emphasis mine). So how do these two fit together?

  • "Good path": &initial[1] is ok, and since &initial[1] == &rest[0] you can take that address and go on to increment the pointer to access the other elements of rest, because of §3.9.2,3
  • "Bad path": initial[2] is *(initial + 2), but since §5.7,5, initial +2 is already UB and you never get to use §3.9.2,3 here.

Together: you have to stop by at the boundary, take a short break to check that the addresses are equal and then you can move on.

查看更多
登录 后发表回答