[Clang] Static analyzer (with assertions) crashes when dealing with `std::call_once`

[ziqingluo-90]

A minimal example (https://godbolt.org/z/o99n7db3e):

#include <mutex>

class T {
    public: 
    T () {}
};

bool check() {
  static std::once_flag flag;
  auto fun = [](T S)->void{};
  std::call_once(flag, fun, T());

}

I think the issue is in fact in BodyFarm instead of CSA, so please help me to CC more appropriate community members and add proper tags if possible.

CSA uses BodyFarm to create the definition of std::call_once.

/// Create a fake body for std::call_once.
/// Emulates the following function body:
///
/// \code
/// typedef struct once_flag_s {
///   unsigned long __state = 0;
/// } once_flag;
/// template<class Callable>
/// void call_once(once_flag& o, Callable func) {
///   if (!o.__state) {
///     func();
///   }
///   o.__state = 1;
/// }
/// \endcode

When BodyFarm crafts the definition, it needs to create an lvalue-to-rvalue conversion on the parameter of type C++ class T.

   Expr *ParamExpr = M.makeDeclRefExpr(PDecl);
    if (!CallbackFunctionType->getParamType(ParamIdx - 2)->isReferenceType()) {
      QualType PTy = PDecl->getType().getNonReferenceType();
      ParamExpr = M.makeLvalueToRvalue(ParamExpr, PTy);
    }

However, in ImplicitCastExpr::Create:

  // Per C++ [conv.lval]p3, lvalue-to-rvalue conversions on class and
  // std::nullptr_t have special semantics not captured by CK_LValueToRValue.
  assert((Kind != CK_LValueToRValue ||
          !(T->isNullPtrType() || T->getAsCXXRecordDecl())) &&
         "invalid type for lvalue-to-rvalue conversion");

[llvmbot]

@llvm/issue-subscribers-clang-static-analyzer

Author: Ziqing Luo (ziqingluo-90)

A minimal example (https://godbolt.org/z/o99n7db3e): ``` #include <mutex>

class T {
public:
T () {}
};

bool check() {
static std::once_flag flag;
auto fun = [](T S)->void{};
std::call_once(flag, fun, T());

}

I think the issue is in fact in BodyFarm instead of CSA, so please help me to CC more appropriate community members and add proper tags if possible.

CSA uses `BodyFarm` to create the definition of `std::call_once`.  

/// Create a fake body for std::call_once.
/// Emulates the following function body:
///
/// \code
/// typedef struct once_flag_s {
/// unsigned long __state = 0;
/// } once_flag;
/// template<class Callable>
/// void call_once(once_flag& o, Callable func) {
/// if (!o.__state) {
/// func();
/// }
/// o.__state = 1;
/// }
/// \endcode

When `BodyFarm` crafts the definition, it needs to create an lvalue-to-rvalue conversion on the parameter of type C++ class `T`.

Expr *ParamExpr = M.makeDeclRefExpr(PDecl);
if (!CallbackFunctionType->getParamType(ParamIdx - 2)->isReferenceType()) {
QualType PTy = PDecl->getType().getNonReferenceType();
ParamExpr = M.makeLvalueToRvalue(ParamExpr, PTy);
}

However,  in `ImplicitCastExpr::Create`:

// Per C++ [conv.lval]p3, lvalue-to-rvalue conversions on class and
// std::nullptr_t have special semantics not captured by CK_LValueToRValue.
assert((Kind != CK_LValueToRValue ||
!(T->isNullPtrType() || T->getAsCXXRecordDecl())) &&
"invalid type for lvalue-to-rvalue conversion");

</details>

[ziqingluo-90]

CC: @haoNoQ @steakhal @Xazax-hun @NagyDonat @isuckatcs

[haoNoQ]

The body farm for std::call_once turned out to be much more difficult than we expected.

We've originally farmed its non-standard progenitor dispatch_once and its body farm had been fairly trivial, along the lines of Mike's naive implementation:

void dispatch_once(dispatch_once_t *predicate, dispatch_block_t block) {
    if(!*predicate) {
        block();
        *predicate = 1;
    }
}

This synthetic body is obviously incorrect for the reasons Mike lays out later in his awesome blog post, but that's the whole point. Our analysis is sequential and we don't simulate multi-threading, so we could go with a much simpler fake "implementation" that's exactly equivalent to the real thing for our purposes.

Body farms are written directly in terms of the AST, not source code. But that wasn't a problem for a basic AST like this. If you spent enough time with Clang AST, you can take a reasonable guess what the AST of this code would look like.

---

Now, enter std::call_once, the standardization of dispatch_once in the C++ standard library. Because it accepts lambdas instead of blocks, its prototype naturally looks like this:

template <class Callable, class ...Args>
void call_once(std::once_flag &flag, Callable &&f, Args &&...args);

Instead of a basic plain C if-statement, we're now dealing with a variadic template over all possible combinations of function and lambda types that it can accept. Additionally, we need to deal with all kinds of lvalue and rvalue references, and std::once_flag is no longer a primitive type, it's a class.

In order to generate a body farm for this monstrosity, you need to write the uninstantiated template code, then instantiate it, recursively for each argument. Correctly substitute all the anonymous lambda types, replace the unresolved function calls with operator()() calls, resolve all the types.

By hand.

George has heroically handled some of the most basic cases. But to this day it's a miracle that anything works at all. Nobody should be expected to imperatively write this AST by hand. It might be that we could reuse some fancy Sema functions somewhere in the middle, but it's an incredibly tedious task either way, and the resulting code would always be extremely fragile to AST changes in the compiler proper.

---

So in conclusion, the best way to deal with these crashes is probably to outright refuse to produce the synthetic AST on all unusual codepaths, and then wait for a better way to define analysis-time models for such functions. Which would be:

• either through evalCall() a-la standard-library-function-checker,
• or by implementing a way to load body farm ASTs directly from source code.

The former might actually be quite realistic these days, you might want to take a look at how its summary language has evolved over the years.

The latter may actually be quite feasible with the help of ASTImporter, and this could be a very nice long-term solution for the problem of body farms. Even if we assume that ASTImporter is too incorrect in the general case, in the body farm case we have a lot of control over what we feed into it. So if we stick to the code that's known to work correctly, we could make a lot of progress.

P.S. @ziqingluo-90 I'm pretty sure I've seen these before, you might be able to dupe it.

[steakhal]

• either through evalCall() a-la standard-library-function-checker,

• or by implementing a way to load body farm ASTs directly from source code.

The problem I see currently with the 1st approach is that there is no way a checker can currently change the control-flow. In other words, to transfer control to a a different function, like in this case to the function object parameter. This need emerges from time-to-time, and I don't know of an easy way of fixing this.
It's in general accepted that the ExplodedGraph should look and feel the same with or without enabling checkers. In other words, the paths a checker sinks should not change even if we disable the checker. Now, if we allow checkers to change the control-flow, that would bring some complication - similar to what we already have with eval::Calls but there at least the control flow either follows what's spelled or it's an oopaque call.

We could have some API to allow checkers to influence control flow, but the directions there are much less clear to me right now.

Reflecting on the 2nd option, about using ASTImporter, I'm also skeptical. Probably even more so.
Unless somebody contains it somehow for crashes and mutations, there is a high risk of crashing a whole analysis just because we tried to bodyfarm a function body. I'd say, if we could trust the stability of ASTImporter then it would be a much better backend for body farming though.

[ziqingluo-90]

I'm leaning more towards the long-term solution with ASTImporter, if it becomes stable enough and will be maintained by someone.
That way, modeling library functions would be easy and would not require specific knowledge of clang static analyzer.

[haoNoQ]

I don't think ASTImporter will ever become fully correct and stable. IIUC it's solving a fundamentally unsolvable problem. So this approach is more about identifying code that it can import reliably regardless of the original TU's contents. There could be a lot of "low-hanging fruit" functions that you can model this way but I don't recommend delving too deep into it with the expectation that it'll solve all your problems.

Also note that the BodyFarm/ASTImporter approach is only good when your synthetic code is simpler than the original code. Which may be true for functions such as call_once() as it allows us to bypass all the atomicity/threading-related code. But in the general case that's not true, and there are some ridiculous outliers for which a simplified model is actually way worse than nothing (consider the original motivation for the standard library functions checker).

In other words, the problem with synthetic bodies is that we're going to model them through inlining, and inlining isn't even a good way to do interprocedural analysis. Inlining causes branches. Branches cause false positives (#61669). Branches inside inlined function calls cause even more false positives (cf. "inlined defensive checks").

So if you want to treat the function as mostly branchless (which is true for the vast majority of functions), you probably want to do something evalCall()-based instead.

[ziqingluo-90]

CC @malavikasamak for visibility