ASan: heap-use-after-free after vector.emplace(push)_back in a recursive function

  address-sanitizer, c++, vector
#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;
        }
    }
}

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?

Source: Windows Questions C++

LEAVE A COMMENT