0
#include <vector>

struct Node;

std::vector<Node> heap;

struct Node {
    int x, c;

    explicit Node(int x): x(x), c(0) {}

    void update() {
        if(x > 0) {
            if(c == 0) {
                c = heap.size();
                heap.emplace_back(x / 2);
            }
            heap[c].update();
        }
    }
};

int main() {
    heap.emplace_back(100);
    heap.back().update();
}

Consider the above code. When compiled with g++ -fsanitize=address (gcc version 10.2.0 (Ubuntu 10.2.0-5ubuntu1~20.04)) and then ran, I get AddressSanitizer: heap-use-after-free. After some googling it appears that this error happens when I try to access a pointer that has previously been freed. Examining ASan's output shows that the object was freed by vector.emplace_back. I believe that this is a result of the vector resizing itself, supported by the fact that heap.reserve(1000) makes the code run fine.

I then tried replacing emplace_back with push_back, producing similar results. However, replacing the recursion with a loop works fine.

int main() {
    heap.emplace_back(100);
    int prevc = 0;
    while(true) {
        int x = heap[prevc].x, c = 0;
        if(x > 0) {
            if(c == 0) {
                c = heap.size();
                heap.emplace_back(x / 2);
            }
            prevc = c;
        }else {
            break;
        }
    }
}

After further examination, it appears that the exception is being thrown after the first call of update(). Furthermore, accessing heap[0] and heap[1] is fine, but accessing heap[c] fails.

Now I am quite confused. I can't find any undefined behavior, nor can I see any reason for vector internal resizing to cause me to not be able to access an element. Moreover, I'm not sure why this fails with recursion only. What am I doing wrong?

skittles1412
  • 121
  • 5
  • 1
    Add a destructor to `Node` that prints when it's called (maybe along with `c`). You'll be surprised. – Stephen Newell Apr 07 '21 at 22:21
  • Ain't `vector` resizes a ? – user4581301 Apr 07 '21 at 22:25
  • Handy reading: [Iterator invalidation rules](https://stackoverflow.com/questions/6438086/iterator-invalidation-rules) – user4581301 Apr 07 '21 at 22:28
  • @StephenNewell When printing `x` in the destructor, only 100 gets printed. I believe the exception is thrown after the first call of `update()`. I'll edit this along with more information into the question. – skittles1412 Apr 07 '21 at 22:40
  • 1
    When you call `update` on a node in `heap` remember that `this` refers to a node in `heap` and when `heap.emplace_back(x / 2);` resizes `heap`, `this` is kinda ed. That means using `c` in `heap[c].update();` is going to be quite an adventure. – user4581301 Apr 07 '21 at 22:40
  • @user4581301 Ah, I believe that is the issue. Replacing `heap[c].update()` with a statement accessing `c` also throws an exception. Thanks for your help! – skittles1412 Apr 07 '21 at 22:44
  • When you have a good solution, assuming you don't just use your non-recursive version, self answer. I'd have answered myself, but I'm pretty sure the right answer is non-recursive. – user4581301 Apr 07 '21 at 22:48
  • I was going to use this in my answer. I'll drop it here because this is what @StephenNewell was suggesting in his comment above: https://ideone.com/Lk6d02 . You can see evil stuff like *Destroying 0x55676c529e70* followed by *calling update for 0x55676c529e70. c = 0*, which is clearly invalid because the object is dead. Eventually you get one where `this` got re-used and `c` is insane. – user4581301 Apr 07 '21 at 22:55

1 Answers1

2

As user4581301 pointed out in the comments, the issue actually isn't accessing an element in the vector but rather accessing c, which fails because this had been deleted by heap resizing.

In my particular case I wanted to write a binary tree without pointers, so recursion is necessary. Ironically the reasoning behind this was to avoid pointer pitfalls, but that backfired miserably. For future reference, I've found four possible solutions:

  1. heap.reserve() to a large enough value that heap will never resize itself.
  2. Simulate a vector with an array and a pointer to the index of the last element (basically option 1, but possibly faster)
  3. Add something like Node self = *this; and access all attributes through self. Note: doing Node *self = this; won't work, as self will get invalidated along with this.
  4. Just use pointers; they exist for a reason.
skittles1412
  • 121
  • 5
  • A note on point 3. I'm not sure this is 100% legal. Remember the program is still in a method with an invalid `this`. A quick look at the Standard didn't find anything that explicitly states this is valid or not, but you've guaranteed that `this` won't be used and should be safe in practice. – user4581301 Apr 07 '21 at 23:29