[analyzer][ctu] Avoid parsing invocation list again and again during on-demand parsing of CTU

[OikawaKirie]

Summary

During CTU, the *on-demand parsing* will read and parse the invocation list to know how to compile the file being imported. However, it seems that the invocation list will be parsed again if a previous parsing has failed. Then, parse again and fail again. This patch tries to overcome the problem by storing the error code during the first parsing, and re-create the stored error during the later parsings.

[steakhal]

Awesome! Seems good to me. Though I've got limited experience on CTU stuff.
It would be nice to have tests, but it seems pretty hard to come up with one for this. Given that this is just a 'performance' issue, I'm fine with it.
Somehow try to check if this resolved your original concern.

clang/include/clang/CrossTU/CrossTranslationUnit.h

41

What about success?
That way it would resonate well with the return's success();

clang/lib/CrossTU/CrossTranslationUnit.cpp

694

Shouldn't be small enough to pass-by-value?

[martong]

Thank you for this patch!

Could you please provide a lit test that ignites the over and over parsing behaviour? I think you need to create two files and the second one should contain parser error(s).

clang/include/clang/CrossTU/CrossTranslationUnit.h

257

I think it would be more consistent to make this an llvm::Error. I.e. we would store the result of the whole lazyInitInvocationList in this member variable. And as such, a better name could be PreviousResult. And this could be an Optional to indicate that we have never called lazyInitInvocationList before.
This means we would check in lazyInitInvocationList whether the PreviousResult is set and if yes is it an error. And if both conditions are true then return with the stashed error.

clang/lib/CrossTU/CrossTranslationUnit.cpp

674

The if here is superfluous because the condition must be true always, otherwise we would have an InvocationList, wouldn't we?

Or we can have this condition, but then the if (InvocatioList) is not needed.

[balazske]

clang/lib/CrossTU/CrossTranslationUnit.cpp

674

This looks correct: We have an InvocationList if it is usable as result (initialized and no error). Otherwise there is an error or it is the first time the function is called. The second if checks for this condition.

[balazske]

clang/include/clang/CrossTU/CrossTranslationUnit.h

257

The current solution looks good, probably it is more convenient to store the result in a llvm::Error.

[OikawaKirie]

Add a regression test case by mocking the open function. When this function is called with the file name of the invocation list, the mocked open function will reject the open operation and dump a log. And we will then check how many times are the invocation list opened. (Thanks to the ideas by steakhal in another patch of mocking a library function :-).)

Identifiers renamed as suggested.

Unfortunately, we cannot store and copy a llvm::Error object. Therefore, the new version still uses the error code to store the previous parsing results.

[steakhal]

Overall, it looks promising. But I don't quite get this test.
There is no invocation yaml in the temp directory. So, you are probably not testing the right thing.
You wanted to test if the invocation yaml exists, and could be opened but the parsing fails.
You should demonstrate that when a parsing error happens, the error code has recoded and it won't try to reparse the invocation yaml again and again.

[OikawaKirie]

In D101763#2741536, @steakhal wrote:

Overall, it looks promising. But I don't quite get this test.
There is no invocation yaml in the temp directory. So, you are probably not testing the right thing.
You wanted to test if the invocation yaml exists, and could be opened but the parsing fails.
You should demonstrate that when a parsing error happens, the error code has recoded and it won't try to reparse the invocation yaml again and again.

The main idea of the test case is that the mocked open function will dump a log every time when the invocation list file is opened to be read. If a second open operation is detected in the log, it means the list is parsed again.

As the behavior of missing the invocation list file or failing to parse it are the same (both returns the error), the previous version checks whether function open will be called again after a file-not-found error.
In this update, I use an empty invocation list to really trigger an invocation_list_empty error and check whether the invocation list file will be read again via function open.
Compared with the previous version, opening the invocation list will not be manually failed, and a real parsing error is triggered instead.

[steakhal]

Okay, so you 'just' want an indication for the given open call. What about using strace?
strace -e trace=openat %clang_cc1 ... 2>&1 | grep '"invocations.yaml"' | FileCheck %s

This way the given test file could contain the contents of the importer.c.

[OikawaKirie]

• Update the test case as suggested.
• Add a case branch for the index_error_code::success error code in function IndexErrorCategory::message to silent the compiler warnings.

[OikawaKirie]

Replace wc -l with count.

Sorry for the spam.

[steakhal]

I would rather match on the complete line (except the file descriptor ofc).

By inspecting the output that is piped to the count, I have a suspicion:

openat(AT_FDCWD, "invocations.yaml", O_RDONLY|O_CLOEXEC) = -1 ENOENT (No such file or directory)

It should have found it! It exists, but ill-formed. @martong what did we misconfigure?

My guess is that ctu-invocation-list is not using the ctu-dir. It should be a different bug though.
To workaround this issue, simply use an absolute path for the invocation yaml.

What about this?

// RUN ... 2>&1 | grep 'invocations\.yaml' | FileCheck %s
void foo() {
  // It finds the invocation yaml, then it tries to parse it which expected to fail.
  bar();
  // CHECK: openat(AT_FDCWD, "{{[^"]+}}invocations.yaml", O_RDONLY|O_CLOEXEC) = {{[0-9]+}}

  // We should remember that the parsing failed, we shouldn't try to reopen and parse the yaml again.
  bar();
  // CHECK-NOT: openat(AT_FDCWD, "{{[^"]+}}invocations.yaml", O_RDONLY|O_CLOEXEC) = {{[0-9]+}}
}

This way we are sure that the file opened (it resulted in a non-negative file descriptor) and opened only once!

[OikawaKirie]

In D101763#2743984, @steakhal wrote:

By inspecting the output that is piped to the count, I have a suspicion:

openat(AT_FDCWD, "invocations.yaml", O_RDONLY|O_CLOEXEC) = -1 ENOENT (No such file or directory)

According to the output of the failed test, it seems that CTU is not working during the test case execution (Expected 1 lines, got 0.). Otherwise, it should be matched by grep.
There seems to be something wrong with the test case, although it works well in my environment.

My guess is that ctu-invocation-list is not using the ctu-dir. It should be a different bug though.
To workaround this issue, simply use an absolute path for the invocation yaml.

It seems that you are correct, I will fix this problem later.
I can just cd to the ctu-dir before running CSA as a workaround. Just as the author of on-demand parsing did (refer to clang/test/Analysis/ctu-on-demand-parsing.c).

// CHECK: openat(AT_FDCWD, "{{[^"]+}}invocations.yaml", O_RDONLY|O_CLOEXEC) = {{[0-9]+}}

I am not quite sure whether we need to verify the flags (AT_FDCWD, O_RDONLY and O_CLOEXEC) as well. Therefore, I removed them in this update.

[steakhal]

I would love to see PreviousParsingResult combined with InvocationList using a llvm::Error. I'm pretty sure it can be done.
Regardless, I think it's already better than it was.

[OikawaKirie]

In D101763#2741629, @steakhal wrote:

Okay, so you 'just' want an indication for the given open call. What about using strace?
strace -e trace=openat %clang_cc1 ... 2>&1 | grep '"invocations.yaml"' | FileCheck %s

I do not know why the test case always fails on the build server, it runs perfectly on my computer. : (
Do any reviewers have any ideas?

[OikawaKirie]

Monitor function open together with openat to fix the failure in the test case.
As some distros actually call function open rather than forward to function openat, both functions should be monitored by strace.

But I am still worrying about whether function open will call openat and vice versa. If this circumstance is possible, the test case may still fail.
Although, I have not found any pieces of evidence for such invocations.

[steakhal]

In D101763#2745802, @OikawaKirie wrote:

I do not know why the test case always fails on the build server, it runs perfectly on my computer. : (

I've locally run your patch and seemed good to me, I regret not having a look at the actual build bot.

In D101763#2745900, @OikawaKirie wrote:

Monitor function open together with openat to fix the failure in the test case.
As some distros actually call function open rather than forward to function openat, both functions should be monitored by strace.

But I am still worrying about whether function open will call openat and vice versa. If this circumstance is possible, the test case may still fail.
Although, I have not found any pieces of evidence for such invocations.

Uh, that's a fair point. Now, I'm also worried xD
To be fair, I don't have any better idea testing this without overwhelming effort.
If anything goes wrong, we can simply revert this change. This is 'just' a performance fix.

[OikawaKirie]

FileCheck error: '<stdin>' is empty.

It fails again on the build bot, another dead end. Maybe I need a Debian server to reproduce the problem encountered in the test case.

In D101763#2745918, @steakhal wrote:

In D101763#2745802, @OikawaKirie wrote:

I do not know why the test case always fails on the build server, it runs perfectly on my computer. : (

I've locally run your patch and seemed good to me, I regret not having a look at the actual build bot.

I have tried the test case on a Ubuntu 20.04 server with kernel 5.4.0 and gcc 9.3.0, as well as a CentOS 7 server with kernel 3.10.0 and gcc 7.1.0. Both of them work well.

In D101763#2745900, @OikawaKirie wrote:

Monitor function open together with openat to fix the failure in the test case.
As some distros actually call function open rather than forward to function openat, both functions should be monitored by strace.

But I am still worrying about whether function open will call openat and vice versa. If this circumstance is possible, the test case may still fail.
Although, I have not found any pieces of evidence for such invocations.

Uh, that's a fair point. Now, I'm also worried xD
To be fair, I don't have any better idea testing this without overwhelming effort.
If anything goes wrong, we can simply revert this change. This is 'just' a performance fix.

I will try to reproduce and fix the problem of the test case next week. If I cannot find other ways to overcome the problem by the next weekend, we can have a try on landing this patch.

[martong]

First of all, thank you for the patch!
We had a meeting with my colleges (@steakhal, @gamesh411) and we agreed in the following. This is indeed an issue and the fix is okay. About the test, we'd like to ask if you could create a small test lib with its own 'open' function that would simply call the system's open and would print 'open'. And then with LD_PREOLOAD you could use that lib in the lit test. (If that approach is not working for some reason then we may just mark the test with XFAIL.)

[OikawaKirie]

In D101763#2768549, @martong wrote:

First of all, thank you for the patch!
We had a meeting with my colleges (@steakhal, @gamesh411) and we agreed in the following. This is indeed an issue and the fix is okay. About the test, we'd like to ask if you could create a small test lib with its own 'open' function that would simply call the system's open and would print 'open'. And then with LD_PREOLOAD you could use that lib in the lit test. (If that approach is not working for some reason then we may just mark the test with XFAIL.)

Updated as suggested based on a previous submit https://reviews.llvm.org/D101763?id=343346. An empty invocation list is used to trigger a parsing failure, and name invocations.yaml is used as the file name for logging and checking.

[steakhal]

Could you please reupload your diff to retrigger the bots?
I'd like to make sure that everything passes, even the tests that do not belong to you.
Unfortunately, I don't know any better way of retriggering the pre-merge checks - I don't have permission to manually retrigger builds.

[OikawaKirie]

Re-submit the patch to re-build the code.

[OikawaKirie]

Re-submit the patch to re-build the code.

Sorry for the spam of submitting an incomplete diff which triggers a patch apply failure.

[steakhal]

It seems like everything passes. Yeey, good job!
Shall I commit this tomorrow on your behalf?

[OikawaKirie]

In D101763#2777821, @steakhal wrote:

It seems like everything passes. Yeey, good job!
Shall I commit this tomorrow on your behalf?

I do not have commit access to the code base. It would be appreciated if you could commit it on my behalf (Ella Ma <[e-mail]>).
Thanks to all reviewers again for your suggestions.

[steakhal]

I've decided to land this without the test.
Thank you for your contribution.

clang/include/clang/CrossTU/CrossTranslationUnit.h

 class FunctionDecl;
 class VarDecl;
 class NamedDecl;
 class TranslationUnitDecl;
 
 namespace cross_tu {
 
 enum class index_error_code {
+  success = 0,
   unspecified = 1,
   missing_index_file,
   invalid_index_format,
   multiple_definitions,
   missing_definition,
   failed_import,
   failed_to_get_external_ast,
   failed_to_generate_usr,
private:
     StringRef CTUDir;
     /// The path to the file containing the invocation list, which is in YAML
     /// format, and contains a mapping from source files to compiler invocations
     /// that produce the AST used for analysis.
     StringRef InvocationListFilePath;
     /// In case of on-demand parsing, the invocations for parsing the source
     /// files is stored.
     llvm::Optional<InvocationListTy> InvocationList;
+    index_error_code PreviousParsingResult = index_error_code::success;
   };
 
   /// Maintain number of AST loads and check for reaching the load limit.
   class ASTLoadGuard {
   public:
     ASTLoadGuard(unsigned Limit) : Limit(Limit) {}
 
     /// Indicates, whether a new load operation is permitted, it is within the

clang/lib/CrossTU/CrossTranslationUnit.cpp

 
 // FIXME: This class is will be removed after the transition to llvm::Error.
 class IndexErrorCategory : public std::error_category {
 public:
   const char *name() const noexcept override { return "clang.index"; }
 
   std::string message(int Condition) const override {
     switch (static_cast<index_error_code>(Condition)) {
+    case index_error_code::success:
+      // There should not be a success error. Jump to unreachable directly.
+      // Add this case to make the compiler stop complaining.
+      break;
     case index_error_code::unspecified:
       return "An unknown error has occurred.";
     case index_error_code::missing_index_file:
       return "The index file is missing.";
     case index_error_code::invalid_index_format:
       return "Invalid index file format.";
     case index_error_code::multiple_definitions:
       return "Multiple definitions in the index file.";
parseInvocationList(StringRef FileContent, llvm::sys::path::Style PathStyle) {
 
   return InvocationList;
 }
 
 llvm::Error CrossTranslationUnitContext::ASTLoader::lazyInitInvocationList() {
   /// Lazily initialize the invocation list member used for on-demand parsing.
   if (InvocationList)
     return llvm::Error::success();
+  if (index_error_code::success != PreviousParsingResult)
+    return llvm::make_error<IndexError>(PreviousParsingResult);
 
   llvm::ErrorOr<std::unique_ptr<llvm::MemoryBuffer>> FileContent =
       llvm::MemoryBuffer::getFile(InvocationListFilePath);
-  if (!FileContent)
-    return llvm::make_error<IndexError>(
-        index_error_code::invocation_list_file_not_found);
+  if (!FileContent) {
+    PreviousParsingResult = index_error_code::invocation_list_file_not_found;
+    return llvm::make_error<IndexError>(PreviousParsingResult);
+  }
   std::unique_ptr<llvm::MemoryBuffer> ContentBuffer = std::move(*FileContent);
   assert(ContentBuffer && "If no error was produced after loading, the pointer "
                           "should not be nullptr.");
 
   llvm::Expected<InvocationListTy> ExpectedInvocationList =
       parseInvocationList(ContentBuffer->getBuffer(), PathStyle);
 
-  if (!ExpectedInvocationList)
-    return ExpectedInvocationList.takeError();
+  // Handle the error to store the code for next call to this function.
+  if (!ExpectedInvocationList) {
+    llvm::handleAllErrors(
+        ExpectedInvocationList.takeError(),
+        [&](const IndexError &E) { PreviousParsingResult = E.getCode(); });
+    return llvm::make_error<IndexError>(PreviousParsingResult);
+  }
 
   InvocationList = *ExpectedInvocationList;
 
   return llvm::Error::success();
 }
 
 template <typename T>
 llvm::Expected<const T *>

clang/test/Analysis/ctu-on-demand-parsing-multiple-invocation-list-parsing.cpp

+// RUN: rm -rf %t
+// RUN: mkdir -p %t
+
+// RUN: %host_cxx %s -fPIC -shared -o %t/mock_open.so
+
+// RUN: echo "void bar(); void foo() { bar(); bar(); }" > %t/trigger.c
+// RUN: echo "void bar() {}" > %t/importee.c
+// RUN: echo '[{"directory":"%t", "command":"cc -c %t/importee.c", "file": "%t/importee.c"}]' > %t/compile_commands.json
+// RUN: %clang_extdef_map -p %t "%t/importee.c" > %t/externalDefMap.txt
+
+// Add an empty invocation list to make the on-demand parsing fail and load it again.
+// RUN: echo '' > %t/invocations.yaml
+
+// RUN: cd %t && \
+// RUN: LD_PRELOAD=%t/mock_open.so \
+// RUN: %clang_cc1 -fsyntax-only -analyze \
+// RUN:   -analyzer-checker=core \
+// RUN:   -analyzer-config experimental-enable-naive-ctu-analysis=true \
+// RUN:   -analyzer-config ctu-dir=. \
+// RUN:   -analyzer-config ctu-invocation-list=invocations.yaml \
+// RUN:   %t/trigger.c | FileCheck %s
+
+// REQUIRES: shell, system-linux
+
+// CHECK: {{Opening file invocations.yaml: 1}}
+// CHECK-NOT: {{Opening file invocations.yaml: 2}}
+
+#define _GNU_SOURCE 1
+#include <dlfcn.h>
+#include <fcntl.h>
+
+#include <cassert>
+#include <cstdarg>
+#include <iostream>
+using namespace std;
+
+extern "C" int open(const char *name, int flag, ...) {
+  // Log how many times the invocation list is opened.
+  if ("invocations.yaml" == string(name)) {
+    static unsigned N = 0;
+    cout << "Opening file invocations.yaml: " << ++N << endl;
+  }
+
+  // The original open function will be called to open the files.
+  using open_t = int (*)(const char *, int, mode_t);
+  static open_t o_open = nullptr;
+  if (!o_open)
+    o_open = reinterpret_cast<open_t>(dlsym(RTLD_NEXT, "open"));
+  assert(o_open && "Cannot find function `open'.");
+
+  va_list vl;
+  va_start(vl, flag);
+  auto mode = va_arg(vl, mode_t);
+  va_end(vl);
+  return o_open(name, flag, mode);
+}