[SCCIterator] Fix use-after-free

[loladiro]

Summary

The line at issue is the following:

nodeVisitNumbers[New] = nodeVisitNumbers[Old];

If we write this as:

unsigned &OldRef = nodeVisitNumbers[Old];
unsigned &NewRef = nodeVisitNumbers[New];
unsigned OldVal = OldRef;
NewRef = OldVal;

the issue becomes obvious: The call to nodeVisitNumbers[New] may
invalidate the reference from the nodeVisitNumbers[Old], causing
the subsequent reference to value conversion to read free'ed memory.
The rewritten evaluation order is valid, because there are no sequence
points among the LHS and RHS value expressions, so either evaluation
order is acceptable. However, as described one of them results in a
use-after-free. However, the resulting crash is highly compiler and
runtime dependent (since the use happens immediately after the free,
there's only an issue if the memory gets freed or re-used by a
different thread).

An obvious fix is just to manually sequence the operations. However,
I would be concerned that this issue could be re-introduced later
by somebody assuming that removing the intermediate variable is NFC.
Instead, switch the access to use the iterator interface. This has
two advantages:

1. When LLVM is build with debug checks, iterator access is validated, to catch these kind of issues.
2. We save ourselves a bucket lookup, because we can re-use the iterator for erasure, increasing performance.

We believe this issue to be the root cause behind https://bugs.llvm.org/show_bug.cgi?id=34480.

Co-authored-by: Valentin Churavy <[e-mail]>

[wristow]

Independently, we came across this same problem, and I proposed a patch at D72469 (which has been committed) that is essentially the simple fix that is described above:

unsigned &OldRef = nodeVisitNumbers[Old];
unsigned &NewRef = nodeVisitNumbers[New];
unsigned OldVal = OldRef;
NewRef = OldVal;

Regarding the point raised here about this simpler solution:

An obvious fix is just to manually sequence the operations. However,
I would be concerned that this issue could be re-introduced later
by somebody assuming that removing the intermediate variable is NFC.

First, I'm certainly not opposed to replacing the simpler solution with the iterator interface approach.

Second, I also was concerned that it may appear that someone may mistakenly think that removing the temporary would be safe, so in my change, I included a comment explaining the reason for the temporary. For reference here, the committed change (along with the comment) is:

// Do the assignment in two steps, in case 'New' is not yet in the map, and
// inserting it causes the map to grow.
auto tempVal = nodeVisitNumbers[Old];
nodeVisitNumbers[New] = tempVal;
nodeVisitNumbers.erase(Old);

[loladiro]

Jinx ;) This took quite some tracking down on our side - too bad we didn't wait a couple of weeks. I do still like the iterator interface better, since it checks against exactly this kind of issue in debug mode. It also avoids the second lookup for the erase. I'll rebase this on top of master.

[wristow]

Jinx ;) This took quite some tracking down on our side - too bad we didn't wait a couple of weeks.

Ah, the luck of timing...

I do still like the iterator interface better, since it checks against exactly this kind of issue in debug mode. It also avoids the second lookup for the erase. I'll rebase this on top of master.

As I said earlier, I'm not opposed to replacing my solution with the iterator interface approach. I won't be offended if you do that! :)

[lebedev.ri]

What's the status here?

[lebedev.ri]

@loladiro either rebase or abandon this?

[lebedev.ri]

In D72529#1972325, @lebedev.ri wrote:

@loladiro either rebase or abandon this?

llvm/include/llvm/ADT/SCCIterator.h

public:
   ///
   /// If the SCC has more than one node, this is trivially true.  If not, it may
   /// still contain a loop if the node has an edge back to itself.
   bool hasLoop() const;
 
   /// This informs the \c scc_iterator that the specified \c Old node
   /// has been deleted, and \c New is to be used in its place.
   void ReplaceNode(NodeRef Old, NodeRef New) {
-    assert(nodeVisitNumbers.count(Old) && "Old not in scc_iterator?");
-    nodeVisitNumbers[New] = nodeVisitNumbers[Old];
-    nodeVisitNumbers.erase(Old);
+    auto it = nodeVisitNumbers.find(Old);
+    assert(it != nodeVisitNumbers.end() && "Old not in scc_iterator?");
+    unsigned OldVisitNumber = it->second;
+    nodeVisitNumbers.erase(it);
+    nodeVisitNumbers[New] = OldVisitNumber;
   }
 };
 
 template <class GraphT, class GT>
 void scc_iterator<GraphT, GT>::DFSVisitOne(NodeRef N) {
   ++visitNum;
   nodeVisitNumbers[N] = visitNum;
   SCCNodeStack.push_back(N);