Page MenuHomePhabricator

[SCCIterator] Fix use-after-free
Needs ReviewPublic

Authored by loladiro on Jan 10 2020, 11:43 AM.

Details

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 <vchuravy@mit.edu>

Event Timeline

loladiro created this revision.Jan 10 2020, 11:43 AM
Herald added a project: Restricted Project. · View Herald TranscriptJan 10 2020, 11:43 AM

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);

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.

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! :)

What's the status here?

@loladiro either rebase or abandon this?