This is an archive of the discontinued LLVM Phabricator instance.

[X86] Fix for ballooning compile times due to Load Value Injection (LVI) mitigations
ClosedPublic

Authored by sconstab on Jul 23 2020, 3:52 PM.

Details

Summary

Fix for the issue raised in https://github.com/rust-lang/rust/issues/74632.

The current heuristic for inserting LFENCEs uses a quadratic-time algorithm. This can apparently cause substantial compilation slowdowns for building Rust projects, where functions > 5000 LoC are apparently common.

The updated heuristic in this patch implements a linear-time algorithm. On a set of benchmarks, the slowdown factor for the generated code was comparable (2.55x geo mean for the quadratic-time heuristic, vs. 2.58x for the linear-time heuristic). Both heuristics offer the same security properties, namely, mitigating LVI.

This patch also includes some formatting fixes.

Diff Detail

Event Timeline

sconstab created this revision.Jul 23 2020, 3:52 PM
Herald added a project: Restricted Project. · View Herald TranscriptJul 23 2020, 3:52 PM

Glad that we could make this simpler without making the resulting code much slower!

llvm/lib/Target/X86/X86LoadValueInjectionLoadHardening.cpp
684–686

nit: I spent some time trying to figure out how these are "implied" by the requirement and I don't think they are. Let's update the comment to make it clear we're describing one approach that happens to meet the requirement at a sweet spot of simplicity and speed.

703–706

Two things:

  1. What's the intuition for aggregating with "max" here rather than, say, summing the weights?
  1. It seems like we should be taking CutEdges into account somehow here. If we've already decided to cut an expensive edge, the *incremental* cost of cutting it again is zero and we shouldn't be including it here.
710

EdgeSet has |= for union, maybe that would be better here

sconstab updated this revision to Diff 280575.Jul 24 2020, 1:24 PM
sconstab marked 3 inline comments as done.

Addressed comments by @mattdr

llvm/lib/Target/X86/X86LoadValueInjectionLoadHardening.cpp
703–706

Thanks for pointing this out. I don't know why my intuition led me to use std::max. The minimum multi-cut algorithm would, in essence, also be adding the weights. And I think you're also correct that edges that have already been cut can be treated as having cost 0.

I implemented these changes, and measured (1) a small decrease in the number of LFENCEs inserted, (2) no significant performance difference, and (3) no exposed LVI vulnerabilities.

710

|= is not overloaded for an array-like container on the RHS. Unless you think that EdgesToCut should also be a BitVector?

mattdr accepted this revision.Jul 24 2020, 4:07 PM
mattdr added inline comments.
llvm/lib/Target/X86/X86LoadValueInjectionLoadHardening.cpp
704–705

I think this is clearer as:

if (!CutEdges.contains(*EgressEdge))
  EgressCutCost += EgressEdge->getValue();

likewise for the loop over IngressEdges.

710

Ah, my mistake -- one too many autos for me to trace through. This is fine.

This revision is now accepted and ready to land.Jul 24 2020, 4:07 PM
sconstab updated this revision to Diff 280618.Jul 24 2020, 4:32 PM

Addressed @mattdr 's lone comment on style.

sconstab updated this revision to Diff 280966.Jul 27 2020, 10:30 AM

Made one further optimization.

At line 669, I added a check that will only invoke elimMitigatedEdgesAndNodes() if the current function already has LFENCEs that may mitigate some gadgets. If the function does not have any LFENCEs, then elimMitigatedEdgesAndNodes() will not transform the gadget graph because (a) there are no fences to eliminate, and (b) the new heuristic only performs *one* round of cuts *after* elimMitigatedEdgesAndNodes() runs.

sconstab requested review of this revision.Jul 27 2020, 10:30 AM
mattdr added inline comments.Jul 27 2020, 11:51 AM
llvm/lib/Target/X86/X86LoadValueInjectionLoadHardening.cpp
674–675

Can we add this as an early-exit case in trimMitigatedEdges instead?

680–681

Seems like this early-exit case should not have been guarded by the if.

sconstab updated this revision to Diff 281041.Jul 27 2020, 1:20 PM
sconstab marked 2 inline comments as done.
sconstab added inline comments.
llvm/lib/Target/X86/X86LoadValueInjectionLoadHardening.cpp
674–675

That would negatively impact the hardenLoadsWithPlugin() flow that may need to trimMitigatedEdges() even if Graph->NumFences == 0.

mattdr accepted this revision.Jul 27 2020, 1:29 PM
This revision is now accepted and ready to land.Jul 27 2020, 1:29 PM
craig.topper added inline comments.Jul 27 2020, 2:26 PM
llvm/lib/Target/X86/X86LoadValueInjectionLoadHardening.cpp
663–670

I'm not a big fan of calling a pointer a "Ref". It makes me think its a reference but you have to dereference it. Do we gain much from omitting the '*' where this is used?

712

I think llvm::for_each is discouraged in this case by the statement here https://llvm.org/docs/CodingStandards.html#use-range-based-for-loops-wherever-possible

sconstab updated this revision to Diff 281064.Jul 27 2020, 3:28 PM
sconstab marked 2 inline comments as done.

Addressed @craig.topper 's comments, and also changed some autos to Edge/Node wherever possible to improve readability.

@sconstab Do you need someone to commit this?