heap-use-after-free when declaring a variable as a reference

Question

The pasted code below returns a heap-use-after-free error. When I remove the reference symbol '&' on the line with coord &c = q.front(); q.pop();, the error is resolved.

From what I understand, the C++ garbage collector deletes the coord I retrieved from q.front() when there are no more references to it. Though it seems here that the c in coord &c is removed from the heap immediately after it is popped from the queue, and attempting to access c in the next line causes the error.

However, this does not happen every time, so I'm wondering why this is occurring.

    class Solution {
    public:
        int numIslands(vector<vector<char>>& grid) {
            if(grid.size() == 0) return 0;
            typedef pair<int,int> coord;
            queue<coord> q;
            const int m = grid.size();
            const int n = grid[0].size();
            int i_in[] = {0,0,1,-1};
            int j_in[] = {1,-1,0,0};
            int ans = 0;
            for(int i = 0; i < m; ++i)
            {
                for(int j = 0; j < n; ++j)
                {
                    if(grid[i][j] == '1')
                    {
                        ++ans;
                        q.push(coord(i,j));
                        while(q.size() > 0)
                        {
                            coord &c = q.front(); q.pop();
                            grid[c.first][c.second] = '*';
                            for(int k = 0; k < 4; ++k)
                            {
                                int newi = c.first + i_in[k];
                                int newj = c.second + j_in[k];
                                if(newi >= 0 && newi < m &&
                                   newj >= 0 && newj < n && 
                                   grid[newi][newj] == '1')
                                {
                                    q.push(coord(newi, newj));
                                }
                            }
                        }
                    }
                }
            }
            return ans;
        }
    };

`coord &c = q.front(); q.pop();` may be the cause. That looks suspicious to me. I mean pop removes the front item but you have a reference to it. — drescherjm, Jul 12 '20 at 02:50
***When I remove the reference symbol '&' on the line with coord &c = q.front(); q.pop();, the error is resolved.*** That is the correct solution. Standard `c++` has no garbage collector. — drescherjm, Jul 12 '20 at 02:57

score 3 · Accepted Answer · edited Sep 13 '20 at 19:26

coord &c = q.front();

^^^ This line sets c to refer to the pair<int,int> that is currently at the front of the queue.

q.pop();

^^^ This line removes the item at the front of the queue, destroying it in the process). So after this line returns, your c reference is pointing to an invalid object, which means that trying to use c will invoke undefined behavior.

However, this does not happen every time, so I'm wondering why this is occurring.

What's occurring is undefined behavior, which is invoked when you try to use a dangling-reference. The interesting thing about undefined behavior is that "things seem to work okay" is a valid result, as is literally anything else that happens -- because once you've invoked undefined behavior, all bets are off, the compiler writers are free of any obligations to make the program work correctly from thereon, and the world is broken.

To fix the problem, you can either remove the ampersand (as you did), so that there is no reference, and therefore no chance of a dangling-reference problem (because you've copied the queue's pair<int,int> object into a local variable instead); or alternatively you could move your call to q.pop() down to the end of your while-loop, so that it occurs only after all of your uses of the c reference have already executed.

heap-use-after-free when declaring a variable as a reference

1 Answers1