[clang] SourceManager: fix at SourceManager::getFileIDLoaded for the case of invalid SLockEntry

[ivanmurashko]

Summary

There is a fix for the search procedure at SourceManager::getFileIDLoaded. It might return an invalid (not loaded) entry. That might cause clang/clangd crashes. At my case the scenario was the following:

• SourceManager::getFileIDLoaded returned an invalid file id for a non loaded entry and incorrectly set SourceManager::LastFileIDLookup to the value
• getSLocEntry returned SourceManager::FakeSLocEntryForRecovery introduced at D89748.
• The result entry is not tested at SourceManager::isOffsetInFileIDand as result the call return SLocOffset < getSLocEntryByID(FID.ID+1).getOffset(); returned true value because FID.ID+1 pointed to a non-fake entry
• The tested offset was marked as one that belonged to the fake SLockEntry

Such behaviour might cause a weird clangd crash when preamble contains some header files that were removed just after the preamble created. Unfortunately it's not so easy to reproduce the crash in the form of a LIT test thus I provided the fix only.

Test Plan:

ninja check-clang

[ivanmurashko]

rebase

[aaron.ballman]

Thanks for working on this!

I think the same is true for SourceManager::isInFileID() as well, right? (Or any other place that calls getSLocEntry() and doesn't check whether the entry is invalid, which also seems to happen a fair amount in SourceManager.cpp.)

Given that this code is on the hot path, should it be the caller's responsibility to have already validated the FileID that's passed in so that the fake entry can never be returned? If not and we really do need the extra branch here (and potentially elsewhere), I'd like to see how this impacts compile time performance on something like http://llvm-compile-time-tracker.com/ to know what we're signing up for.

[ivanmurashko]

Fix for wrong LastFileIDLookup assignment

[ivanmurashko]

In D130847#3690977, @aaron.ballman wrote:

Given that this code is on the hot path, should it be the caller's responsibility to have already validated the FileID that's passed in so that the fake entry can never be returned?

That is a good point. The crash that I am trying to fix uses incorrectly assigned SourceManager::LastFileIDLookup, see SourceManager::getFileID. It's worth avoiding the incorrect cache value assignment. I could determine the place at the code where the assignment was made and updated the patch accordingly.

@aaron.ballman, could you look at the update. Is it reasonable?

Note: the change introduces a check that similar to one made previously for the rest of the search procedure

clang/include/clang/Basic/SourceManager.h

1112–1113 ↗

(On Diff #448885)

nit: There is the place when isOffsetInFileID produces a wrong result at my case

[ivanmurashko]

clang/lib/Basic/SourceManager.cpp

901

FYI: the same check is used for the rest of the search procedure

[aaron.ballman]

These changes look reasonable, but I verified that the precommit CI failures are valid -- it looks like this change broke a test somehow; perhaps a caller was relying on the old behavior and needs to be reworked?

[ivanmurashko]

In D130847#3693668, @aaron.ballman wrote:

These changes look reasonable, but I verified that the precommit CI failures are valid -- it looks like this change broke a test somehow; perhaps a caller was relying on the old behavior and needs to be reworked?

Ah, I have to verify and fix it.

[ivanmurashko]

rebase

[aaron.ballman]

Precommit CI is still failing and I verified locally that the failure is with this patch (instead of some transient issue with precommit CI).

[ivanmurashko]

stop search if we could not load an entry

[ivanmurashko]

In D130847#3693668, @aaron.ballman wrote:

These changes look reasonable, but I verified that the precommit CI failures are valid -- it looks like this change broke a test somehow; perhaps a caller was relying on the old behavior and needs to be reworked?

I fixed the problem. It seems to be reasonable to abort the search procedure at the case of invalid SLockEntries. That also compatible with existent tests.
I updated the patch title and summary as well.

@aaron.ballman , could you look at it?

[aaron.ballman]

clang/lib/Basic/SourceManager.cpp

882–883

This looks incorrect to me -- I don't think an offset of 0 is invalid. I think a better way to do this is:

bool Invalid;
const SrcMgr::SLocEntry &E = getLoadedSLocEntry(I, &Invalid);
if (Invalid)
  return FileID(); // Invalid entry.

[ivanmurashko]

clang/lib/Basic/SourceManager.cpp

882–883

That's reasonable, do we want to update other places at the function as well (line 903 for instance)?

[aaron.ballman]

clang/lib/Basic/SourceManager.cpp

882–883

Assuming my idea works the way I think it will, yes, I think that's a good idea. :-)

[ivanmurashko]

Use Invalid flag to detect invalid SLocEntry

[aaron.ballman]

LGTM, thank you!

[ivanmurashko]

Rebase

clang/lib/Basic/SourceManager.cpp

FileID SourceManager::getFileIDLoaded(SourceLocation::UIntTy SLocOffset) const {
   if (LastID >= 0 || getLoadedSLocEntryByID(LastID).getOffset() < SLocOffset)
     I = 0;
   else
     I = (-LastID - 2) + 1;
 
   unsigned NumProbes;
   for (NumProbes = 0; NumProbes < 8; ++NumProbes, ++I) {
     // Make sure the entry is loaded!
     const SrcMgr::SLocEntry &E = getLoadedSLocEntry(I);
-    if (E.getOffset() <= SLocOffset) {
+    if (E.getOffset() != 0 && E.getOffset() <= SLocOffset) {
       FileID Res = FileID::get(-int(I) - 2);
       LastFileIDLookup = Res;
       NumLinearScans += NumProbes + 1;
       return Res;
     }
   }
 
   // Linear scan failed. Do the binary search. Note the reverse sorting of the
   // table: GreaterIndex is the one where the offset is greater, which is
   // actually a lower index!
   unsigned GreaterIndex = I;
   unsigned LessIndex = LoadedSLocEntryTable.size();
   NumProbes = 0;
   while (true) {
     ++NumProbes;
     unsigned MiddleIndex = (LessIndex - GreaterIndex) / 2 + GreaterIndex;
     const SrcMgr::SLocEntry &E = getLoadedSLocEntry(MiddleIndex);
     if (E.getOffset() == 0)
       return FileID(); // invalid entry.
 
     ++NumProbes;
 
     if (E.getOffset() > SLocOffset) {
       if (GreaterIndex == MiddleIndex) {
         assert(0 && "binary search missed the entry");
         return FileID();