[analyzer] MPIChecker: MPI_Waitall should respect count arg

[danix800]

Summary

MPI_Waitall should respect count arg (ConcreteInt only)

Depends on https://reviews.llvm.org/D158707

[steakhal]

Let me try to summarize some of the variables:

So, given an invocation like MPI_Waitall(C, Requests, Statues):

• MR is lval(Requests)
• ElementCount is the number of elements Requests consist of.
• ArrSize is basically ElementCount but an APSInt.
• MROffset is the offset and allocated region of the Requests region.
• Index is ConcreteInt(0, ..., ArrSize)
• Count is C, which is likely a ConcreteInt.

Please note that I have no idea what this checker does.

clang/lib/StaticAnalyzer/Checkers/MPI-Checker/MPIChecker.cpp

46–48

If these hunks are not closely related to the issue you intend to fix in this PR, I'd suggesst submitting it separately. That is a common API, and we wouldn't need tests for such defensive checks, as they rarely trigger.

205–208

How can ElemSizeInChar be zero?
If it can be zero, could you demonstrate it by a test?

209–210

What implies that MR->getAsOffset() succeeds, and also what implies that the Offset within that is not symbolic?
Also, how can you use this without also using the result region?
Without using that you don't know what is the anchor point, from which this offset represent anything.
ATM I believe the code assumes that MR->getRegion() equals to SuperRegion, which might not be always the case.
This could materialize a problem when you construct the element region later.

209–224

It's suspicious to me to compare stuff in the symbolic domain, such as Idx >= Count here.
And let me elaborate on why I think so.

I'd assume that the first argument of MPI_Waitall is usually just a number literal, thus it's gonna be a ConcreteInt, so now we have Count.
The Index you just created, obviously is just a ConcreteInt.
After this, we could simply unwrap them and do the comparison without doing it in the symbolic domain.

---

As a sidenote, State->assume(*CountReached, true) would return a state in two cases:

1. We can prove that the assumption holds.
2. We cannot disprove the assumption, thus it might hold, so we assume it holds.

This is probably not what you wanted in the first place, but it's probably irrelelevant anyway.

212

In C for example, we might not have a Boot type AFAIK.
Usually, we use SVB.getConditionType() in such cases.

217–219

My guess is that we only care about if MROffset is a concrete int, thus we could also just do this assidion in regular c++ and just transfer the result into the symbolic domain.

222

I believe you have a variable ASTCtx that you could use.

clang/test/Analysis/mpichecker-crash-gh64647.cpp

5–13 ↗

(On Diff #553352)

Unless you have a compelling reason creating this file, I'd suggest to append this to the end of the test/Analysis/mpichecker.cpp, and just leave a comment there like // GithHub Issue 64647.

On a side note, do we need this to be recursive? Is this the minimal case to reproduce the issue?

clang/test/Analysis/mpichecker.cpp

286–288

This loop here implicitly depends on the fact that we only unroll loops 4 times.
I'd prefer a simpler test where we don't even have a loop.

[danix800]

1. Move out complicated computation into separate function;
2. Only check ConreteInt request count.

[danix800]

In D158813#4616816, @steakhal wrote:

Let me try to summarize some of the variables:

So, given an invocation like MPI_Waitall(C, Requests, Statues):

• MR is lval(Requests)
• ElementCount is the number of elements Requests consist of.
• ArrSize is basically ElementCount but an APSInt.
• MROffset is the offset and allocated region of the Requests region.
• Index is ConcreteInt(0, ..., ArrSize)
• Count is C, which is likely a ConcreteInt.

Please note that I have no idea what this checker does.

It's really messy. I tried to refactor and clarify intentions with better naming. Thanks for the summary.

[danix800]

clang/lib/StaticAnalyzer/Checkers/MPI-Checker/MPIChecker.cpp

46–48

Moved (together with the extra testcase file) into https://reviews.llvm.org/D158858.

Checking ExplodedNode against nullptr is a convention in almost all checkers. It surely can be null (quite often).

MPIChecker is one of the only two checkers that forget to do this checking and crashed as reported by #64647

[danix800]

clang/lib/StaticAnalyzer/Checkers/MPI-Checker/MPIChecker.cpp

205–208

Type in the wild does not have to be of non-zero size. MPI vendors might choose whatever implementation as they want.
We are doing division so non-zero checking is necessary.

https://reviews.llvm.org/D158707 added a few general testcases for zero-sized type processing on dynamic extent.

[danix800]

clang/lib/StaticAnalyzer/Checkers/MPI-Checker/MPIChecker.cpp

209–210

I'll restrict the checker to handle non-symbolic offset only.

clang/test/Analysis/mpichecker.cpp

286–288

I'll unroll this loop.

[danix800]

clang/lib/StaticAnalyzer/Checkers/MPI-Checker/MPIChecker.cpp

209–224

I'll restrict this checker to handle ConcreteInt count only.

212

Thanks for this tip.

[danix800]

Ping~, could anyone have a look at this revision please? Thanks!

[steakhal]

I don't have time this week, sorry.
Maybe others can take this over.
@donat.nagy could you please have a look?

[donat.nagy]

I reviewed this change and collected my suggestions in comments.

In general, I feel that the code added by this commit is "sloppy" in the sense that it's designed for the common case and would behave unpredictably in unusual situations. This is a fault of the toolbox provided by the analyzer: in a saner world, you could freely combine the API functions (as you did) and expect that they would "just work" together; but in reality every function has its quirks and limitations, so the developer must understand the details of the implementation.

clang/lib/StaticAnalyzer/Checkers/MPI-Checker/MPIChecker.cpp

146

Use long long (or int64_t, ssize_t, whatever you prefer) instead of NonLoc here because it's easier to handle them (and you don't work with symbolic offsets anyway).

174

What happens here in the case when TypeSizeInChars.isZero() holds?

I see that you used a ternary operator to avoid division by zero; but do you get a meaningful and valid offset value in the case when MPI_Request has zero size and you use TypeSizeInBits == 8?

I understand that the divisior does not matter in the case when RequestRegionOffset.getOffset() is zero; but if I understand it correctly this offset value can be nonzero even in the case when MPI_Request has zero size. (Under the hood it calls MemRegion::getAsOffset() which may include the offset of e.g. a data member of an object.)

209–210

ATM I believe the code assumes that MR->getRegion() equals to SuperRegion, which might not be always the case.

This remark of @steakhal highlights a problem which is still present in your code: when you calculate SuperRegion you strip a single ElementRegion layer; while the offset that you get via getDynamicElementCountWithOffset() is calculated from MemRegion::getAsOffset() which can strip multiple ElementRegion, FieldRegion etc. layers.

Unfortunately the memory region API of Clang Static Analyzer is very inconsistent and quirky; you must dig deep into the implementation to understand the exact meaning of these function calls.

For example, if you have a data type like

struct ReqStruct {
    int custom_info;
    MPI_Request reqs[8];
} rs;

then the SuperRegion will refer to the immediate parent of the ElementRegion (which is presumably the FieldRegion corresponding to reqs); but the offset value is measured from the start of the VarRegion corresponding to the variable rs (and includes sizeof(int) + potential padding due to the presence of custom_info).

I think the correct solution would measure the offset from the start of the array of MPI_Request objects; because if you measure it from the start of the struct, then you may encounter serious issues, e.g. there is no guarantee that the offset will be divisible by the size of MPI_Request.

Unfortunately this would mean that you cannot rely on the logic of getDynamicElementCountWithOffset(); and I don't see a clear way to generalize that library function to limit the number/type of region layers that it strips.

Here I don't see a clear way forward, as the two potential solutions are a deep rewrite that complicates the library code and a creating a locally tweaked duplicate of the library logic -- and these both have serious drawbacks.

213

Paranoid remark: if these count values are both very large (e.g. negative numbers converted to size_t), then this loop could hang for a long time and/or exhaust the memory. Consider adding a hard limit on the number of iterations.

215–217

If you represent RegionOffset as a long long, you can replace this complicated evalBinOp with a simple SVB.makeArrayIndex(i + RegionOffset);.

Note: @steakhal already suggested this improvement in the earlier remark

My guess is that we only care about if MROffset is a concrete int, thus we could also just do this assidion in regular c++ and just transfer the result into the symbolic domain.

which referred to an older variant of your patch.

clang/test/Analysis/mpichecker.cpp

276–280

Please add a dummy field above the other fields to verify that the offsets are handled correctly. For example, char request_name[99]; would be sufficiently large to highlight errors.

This change could be applied in other tests as well.

clang/lib/StaticAnalyzer/Checkers/MPI-Checker/MPIChecker.cpp

if (!isa<TypedRegion>(MR) || (ER && !isa<TypedRegion>(ER->getSuperRegion())))
     return;
 
   ProgramStateRef State = Ctx.getState();
   const Request *const Req = State->get<RequestMap>(MR);
 
   // double nonblocking detected
   if (Req && Req->CurrentState == Request::State::Nonblocking) {
     ExplodedNode *ErrorNode = Ctx.generateNonFatalErrorNode();
     BReporter.reportDoubleNonblocking(PreCallEvent, *Req, MR, ErrorNode,
                                       Ctx.getBugReporter());
     Ctx.addTransition(ErrorNode->getState(), ErrorNode);
   }
   // no error
   else {
     State = State->set<RequestMap>(MR, Request::State::Nonblocking);
     Ctx.addTransition(State);
   }
 }
 
if (FuncClassifier->isMPI_Wait(CE.getCalleeIdentifier())) {
     return CE.getArgSVal(0).getAsRegion();
   } else if (FuncClassifier->isMPI_Waitall(CE.getCalleeIdentifier())) {
     return CE.getArgSVal(1).getAsRegion();
   } else {
     return (const MemRegion *)nullptr;
   }
 }
 
+static std::optional<std::pair<NonLoc, llvm::APSInt>>
+getRequestRegionOffsetAndCount(const MemRegion *const MR, const CallEvent &CE) {
+  if (CE.getNumArgs() < 2)
+    return std::nullopt;
+
+  ProgramStateRef State = CE.getState();
+  SValBuilder &SVB = State->getStateManager().getSValBuilder();
+  ASTContext &ASTCtx = SVB.getContext();
+
+  QualType RequestTy = CE.getArgExpr(1)->getType()->getPointeeType();
+  auto RequestRegionCount =
+      getDynamicElementCountWithOffset(State, CE.getArgSVal(1), RequestTy)
+          .getAs<nonloc::ConcreteInt>();
+  if (!RequestRegionCount)
+    return std::nullopt;
+
+  CharUnits TypeSizeInChars = ASTCtx.getTypeSizeInChars(RequestTy);
+
+  // MPI_Request as a handle does not have to be of non-zero size.
+  int64_t TypeSizeInBits =
+      (TypeSizeInChars.isZero() ? 1 : TypeSizeInChars.getQuantity()) *
+      ASTCtx.getCharWidth();
+
+  RegionOffset RequestRegionOffset = MR->getAsOffset();
+  if (RequestRegionOffset.hasSymbolicOffset())
+    return std::nullopt;
+
+  return std::make_pair(
+      SVB.makeArrayIndex(RequestRegionOffset.getOffset() / TypeSizeInBits),
+      RequestRegionCount->getValue());
+}
+
 void MPIChecker::allRegionsUsedByWait(
     llvm::SmallVector<const MemRegion *, 2> &ReqRegions,
     const MemRegion *const MR, const CallEvent &CE, CheckerContext &Ctx) const {
 
   MemRegionManager &RegionManager = MR->getMemRegionManager();
 
   if (FuncClassifier->isMPI_Waitall(CE.getCalleeIdentifier())) {
     const SubRegion *SuperRegion{nullptr};
     if (const ElementRegion *const ER = MR->getAs<ElementRegion>()) {
       SuperRegion = cast<SubRegion>(ER->getSuperRegion());
     }
 
     // A single request is passed to MPI_Waitall.
     if (!SuperRegion) {
       ReqRegions.push_back(MR);
       return;
     }
 
-    DefinedOrUnknownSVal ElementCount = getDynamicElementCount(
-        Ctx.getState(), SuperRegion, Ctx.getSValBuilder(),
-        CE.getArgExpr(1)->getType()->getPointeeType());
-    const llvm::APSInt &ArrSize =
-        ElementCount.castAs<nonloc::ConcreteInt>().getValue();
+    auto RequestRegionOffsetAndCount = getRequestRegionOffsetAndCount(MR, CE);
+    if (!RequestRegionOffsetAndCount)
+      return;
+
+    auto [RegionOffset, RegionCount] = *RequestRegionOffsetAndCount;
 
-    for (size_t i = 0; i < ArrSize; ++i) {
-      const NonLoc Idx = Ctx.getSValBuilder().makeArrayIndex(i);
+    QualType MPIReqTy = CE.getArgExpr(1)->getType()->getPointeeType();
+    SValBuilder &SVB = Ctx.getSValBuilder();
 
-      const ElementRegion *const ER = RegionManager.getElementRegion(
-          CE.getArgExpr(1)->getType()->getPointeeType(), Idx, SuperRegion,
+    auto RequestedCountSVal = CE.getArgSVal(0).getAs<nonloc::ConcreteInt>();
+    if (!RequestedCountSVal)
+      return;
+
+    const llvm::APSInt &RequestedCount = RequestedCountSVal->getValue();
+    // TODO: i >= RegionCount is an OOB UB, we could report it here but a better
+    // approach is adding this constraint as a summary into generic checker like
+    // StdCLibraryFunctions
+    for (size_t i = 0; i < RegionCount && i < RequestedCount; ++i) {
+      auto RegionIndex =
+          SVB.evalBinOp(Ctx.getState(), BO_Add, SVB.makeArrayIndex(i),
+                        RegionOffset, SVB.getArrayIndexType())
+              .getAs<NonLoc>();
+      if (RegionIndex) {
+        const ElementRegion *const RequestRegion =
+            RegionManager.getElementRegion(MPIReqTy, *RegionIndex, SuperRegion,
                                            Ctx.getASTContext());
-
-      ReqRegions.push_back(ER->getAs<MemRegion>());
+        ReqRegions.push_back(RequestRegion);
+      }
     }
   } else if (FuncClassifier->isMPI_Wait(CE.getCalleeIdentifier())) {
     ReqRegions.push_back(MR);
   }
 }
 
 } // end of namespace: mpi
 } // end of namespace: ento
 } // end of namespace: clang

clang/test/Analysis/mpichecker.cpp

void nestedRequest() {
   MPI_Ireduce(MPI_IN_PLACE, &buf, 1, MPI_DOUBLE, MPI_SUM, 0, MPI_COMM_WORLD,
               &rs.req[1]);
   MPI_Ireduce(MPI_IN_PLACE, &buf, 1, MPI_DOUBLE, MPI_SUM, 0, MPI_COMM_WORLD,
               &rs.req2);
   MPI_Waitall(2, rs.req, MPI_STATUSES_IGNORE);
   MPI_Wait(&rs.req2, MPI_STATUS_IGNORE);
 } // no error
 
+void nestedRequestWithCount() {
+  typedef struct {
+    MPI_Request req[3];
+    MPI_Request req2;
+  } ReqStruct;
+
+  ReqStruct rs;
+  int rank = 0;
+  double buf = 0;
+  MPI_Comm_rank(MPI_COMM_WORLD, &rank);
+
+  MPI_Ireduce(MPI_IN_PLACE, &buf, 1, MPI_DOUBLE, MPI_SUM, 0, MPI_COMM_WORLD,
+              &rs.req[0]);
+  MPI_Ireduce(MPI_IN_PLACE, &buf, 1, MPI_DOUBLE, MPI_SUM, 0, MPI_COMM_WORLD,
+              &rs.req[1]);
+  MPI_Ireduce(MPI_IN_PLACE, &buf, 1, MPI_DOUBLE, MPI_SUM, 0, MPI_COMM_WORLD,
+              &rs.req[2]);
+  MPI_Ireduce(MPI_IN_PLACE, &buf, 1, MPI_DOUBLE, MPI_SUM, 0, MPI_COMM_WORLD,
+              &rs.req2);
+  MPI_Waitall(2, rs.req, MPI_STATUSES_IGNORE);
+  MPI_Waitall(1, rs.req + 2, MPI_STATUSES_IGNORE);
+  MPI_Wait(&rs.req2, MPI_STATUS_IGNORE);
+} // no error
+
+void nestedRequestWithCountMissingNonBlockingWait() {
+  typedef struct {
+    MPI_Request req[3];
+    MPI_Request req2;
+  } ReqStruct;
+
+  ReqStruct rs;
+  int rank = 0;
+  double buf = 0;
+  MPI_Comm_rank(MPI_COMM_WORLD, &rank);
+
+  MPI_Ireduce(MPI_IN_PLACE, &buf, 1, MPI_DOUBLE, MPI_SUM, 0, MPI_COMM_WORLD,
+              &rs.req[0]);
+  MPI_Ireduce(MPI_IN_PLACE, &buf, 1, MPI_DOUBLE, MPI_SUM, 0, MPI_COMM_WORLD,
+              &rs.req[1]);
+  MPI_Ireduce(MPI_IN_PLACE, &buf, 1, MPI_DOUBLE, MPI_SUM, 0, MPI_COMM_WORLD,
+              &rs.req[2]);
+  MPI_Ireduce(MPI_IN_PLACE, &buf, 1, MPI_DOUBLE, MPI_SUM, 0, MPI_COMM_WORLD,
+              &rs.req2);
+  MPI_Waitall(1, rs.req, MPI_STATUSES_IGNORE);
+  // MPI_Waitall(1, rs.req + 1, MPI_STATUSES_IGNORE);
+  MPI_Waitall(1, rs.req + 2, MPI_STATUSES_IGNORE);
+  MPI_Wait(&rs.req2, MPI_STATUS_IGNORE);
+} // expected-warning{{Request 'rs.req[1]' has no matching wait.}}
+
 void singleRequestInWaitall() {
   MPI_Request r;
   int rank = 0;
   double buf = 0;
   MPI_Comm_rank(MPI_COMM_WORLD, &rank);
 
   MPI_Ireduce(MPI_IN_PLACE, &buf, 1, MPI_DOUBLE, MPI_SUM, 0, MPI_COMM_WORLD,
               &r);