Why does using an STL std::vector as a __block variable cause memory corruption?

Question

After some time and effort I have tracked down a memory smashing bug in my code to this function. I stopped the memory smashing by replacing the two __block vector<int> variables with the combination of stack-allocated arrays to provide the storage and a {klist|dlist}Ptr variables to allow code inside the block to access the arrays (seen in the commended-out code below). This makes me fairly confident that it is indeed the use of __block vector<int> that is problematic.

void
traceTree(Matrix<double> Z, double s[3], int k, unsigned int depth)
{
    int m = Z.size(1) + 1;
    __block vector<int> klist(m, 0);
    // int klist[m]; int * klistPtr = klist;
    // klist[0] = k;
    __block vector<int> dlist(1, depth);
    // int dlist[depth]; int * dlistPtr = dlist;
    // dlist[0] = depth;
    __block int topk = 0;
    int currk = 0;

    void (^ subtree)(int i) = ^(int i) {
        if (i > m) {                // If it's not a leaf...
            topk += 1;
            klist[topk] = i - m;
            dlist[topk] = depth - 1;
        }
    };

    while (currk <= topk) {
        k = klist[currk];
        depth = dlist[currk];
        s[0] += Z[{2,k}];            // Sum of the edge lengths so far
        s[1] += Z[{2,k}] * Z[{2,k}]; // ... and the sum of the squares
        s[2] += 1;                   // ... and the count of the edges
        if (depth > 0) {
            subtree(Z[{0,k}]);       // Consider left subtree
            subtree(Z[{1,k}]);       // Consider right subtree
        }
        currk += 1;
    }
}

[I should point out, this is a purely iterative algorithm; there's no recursion. The block exists only to avoid duplicating the code needed to handle left and right subtrees.]

The obvious question is, why are the STL vector objects causing memory corruption here? They are not even doing any dynamic resizing… Is it simply not supported to use a C++ object as a __block variable?

Answer 1

Unless it's a typo, I see your initialization of dlist being different from the array: vector<int> dlist(1, depth); makes a vector of length 1, not depth. This may possibly cause going out of bounds.

You can always guard against accessing vector elements out of bounds by using dlist.at(currk) instead of dlist[currk], for both reading and writing.

Answer 2

C++ objects are allowed as __block variables (though personally I would recommend lambdas if you're writing C++; there's not much reason IMO to use blocks in pure C++ like this).

__block C++ variables are copied using the copy constructor (see C++ Objects in Block Programming Topics). It's possible you're overflowing your stack due to too many copies of large stack variables if this goes very deep (that would match your "memory corruption" symptom).

But again, I'd recommend lambdas rather than blocks for C++; see @sellibitze's answer at How do Clang 'blocks' work? for some more discussion.