[ubsan] Use the object pointer's type info for devirtualized calls

[vsk]

Summary

ubsan reports a false positive 'invalid member call' diagnostic on the
following example (PR30478):

struct Base1 {
  virtual int f1() { return 1; }
};

struct Base2 {
  virtual int f1() { return 2; }
};

struct Derived2 final : Base1, Base2 {
  int f1() override { return 3; }
};

int t1() {
  Derived2 d;
  return static_cast<Base2 *>(&d)->f1();
}

Adding the "final" attribute to a most-derived class allows clang to
devirtualize member calls into an instance of that class. We should pass
along the type info of the object pointer to avoid the FP. In this case,
that means passing along the type info for 'Derived2' instead of 'Base2'
when checking the dynamic type of 'static_cast<Base2 *>(&d2)'.

[rjmccall]

lib/CodeGen/CodeGenFunction.h

379

Please find some way to do this that doesn't require adding new tracking state like this. It should be quite easy to pass down that a call was devirtualized.

[vsk]

• Remove the set of blacklisted object pointers; pass down a flag which indicates whether or not the member call check should be skipped.

[rjmccall]

Wait, can you talk me through the bug here? Why is final-based devirtualization here different from, say, user-directed devirtualization via a qualified method name?

It sounds to me from your description that you're not sure why this is happening. If this indeed only triggers in the presence of multiple inheritance, it might just be the case that you're doing your object-extents analysis starting from the wrong offset.

[vsk]

Thanks for your feedback so far, and sorry for the delayed response.

In D25448#570014, @rjmccall wrote:

Wait, can you talk me through the bug here?

Derived inherits from Base1 and Base2. We upcast an instance of Derived to Base2, then call a method (f1). Clang figures out that the method has to be Derived::f1. Next, clang passes in a pointer to the vtable pointer for Base1, along with the typeinfo for Base2, into the sanitizer runtime. This confuses the runtime, which reports that the dynamic type of the object is "Base1", and that this does not match the expected type ("Base2").

With the 'final' keyword:

%6 = ptrtoint <2 x i32 (...)**>* %1 to i64
call void @__ubsan_handle_dynamic_type_cache_miss(@1 (TypeInfo for Base2), i64 %6, ...)

Without the 'final' keyword:

%6 = bitcast <2 x i32 (...)**>* %1 to %class.Derived*
%7 = getelementptr inbounds %class.Derived, %class.Derived* %6, i64 0, i32 1
%8 = ptrtoint %class.Base2* %7 to i64, !nosanitize !5
call void @__ubsan_handle_dynamic_type_cache_miss(@1 (TypeInfo for Base2), i64 %8, ...)

Why is final-based devirtualization here different from, say, user-directed devirtualization via a qualified method name?

I'm not sure. I tested this by removing the 'final' specifier from 'Derived' and calling:

obj.Derived::f1()

In this case, clang passes the correct typeinfo (for Derived) in to the runtime.

It sounds to me from your description that you're not sure why this is happening. If this indeed only triggers in the presence of multiple inheritance, it might just be the case that you're doing your object-extents analysis starting from the wrong offset.

It looks like I just haven't done a good job of explaining the issue. The bug really does seem to be that clang isn't passing the right information to the ubsan runtime. However, I'm not sure what the right fix is. Do we disable sanitization in cases where we expect FP's, do we try harder to pass in the right vptr (in this case, the vptr for Base2) into the runtime, or do we try harder to pass in the right typeinfo (in this case, the typeinfo for Derived)?

[rjmccall]

In D25448#571941, @vsk wrote:

Thanks for your feedback so far, and sorry for the delayed response.

In D25448#570014, @rjmccall wrote:

Wait, can you talk me through the bug here?

Derived inherits from Base1 and Base2. We upcast an instance of Derived to Base2, then call a method (f1). Clang figures out that the method has to be Derived::f1. Next, clang passes in a pointer to the vtable pointer for Base1, along with the typeinfo for Base2, into the sanitizer runtime. This confuses the runtime, which reports that the dynamic type of the object is "Base1", and that this does not match the expected type ("Base2").

A pointer to the vtable pointer for Base1 is a pointer to a Derived. You have a multiple inheritance bug, or really a general inheritance bug. It's being covered up in the case of single, non-virtual inheritance because that's the case in which a pointer to a base-class object is the same as a pointer to the derived class object.

When the devirtualizer sees what's formally a call to a method on Base2, and it decides that it can instead treat it as a call to a method on Derived, it has to adjust the 'this' pointer to point to a Derived. (I don't know off-hand whether it does this by retroactively adjusting the pointer or whether it just avoids adjusting it in the first place.) When it does this, it should also be changing its notion of what class the pointer points to.

With the 'final' keyword:

%6 = ptrtoint <2 x i32 (...)**>* %1 to i64
call void @__ubsan_handle_dynamic_type_cache_miss(@1 (TypeInfo for Base2), i64 %6, ...)

Without the 'final' keyword:

%6 = bitcast <2 x i32 (...)**>* %1 to %class.Derived*
%7 = getelementptr inbounds %class.Derived, %class.Derived* %6, i64 0, i32 1
%8 = ptrtoint %class.Base2* %7 to i64, !nosanitize !5
call void @__ubsan_handle_dynamic_type_cache_miss(@1 (TypeInfo for Base2), i64 %8, ...)

Why is final-based devirtualization here different from, say, user-directed devirtualization via a qualified method name?

I'm not sure. I tested this by removing the 'final' specifier from 'Derived' and calling:

obj.Derived::f1()

In this case, clang passes the correct typeinfo (for Derived) in to the runtime.

It sounds to me from your description that you're not sure why this is happening. If this indeed only triggers in the presence of multiple inheritance, it might just be the case that you're doing your object-extents analysis starting from the wrong offset.

It looks like I just haven't done a good job of explaining the issue. The bug really does seem to be that clang isn't passing the right information to the ubsan runtime. However, I'm not sure what the right fix is. Do we disable sanitization in cases where we expect FP's, do we try harder to pass in the right vptr (in this case, the vptr for Base2) into the runtime, or do we try harder to pass in the right typeinfo (in this case, the typeinfo for Derived)?

[vsk]

Patch update: Pass along the type info of the derived class to the ubsan runtime when we devirtualize a method call. This squashes the FP. I tested this with 'check-ubsan' in addition to adding a lit test.

A pointer to the vtable pointer for Base1 is a pointer to a Derived. You have a multiple inheritance bug, or really a general inheritance bug. It's being covered up in the case of single, non-virtual inheritance because that's the case in which a pointer to a base-class object is the same as a pointer to the derived class object.

I imagine that it would be difficult to extend the runtime to handle this case. I.e, given a pointer to vtable pointer for Base1 and the type info for Base2, recognize that we may _actually_ be looking at an instance of Derived, and therefore claim that the types match. I wonder if that would result in a false negative in this case:

Base1 b1;
reinterpret_cast<Base2 *>(b1)->method_from_base2_only()

We are currently able to diagnose this.

... it should also be changing its notion of what class the pointer points to.

I'm taking this to mean that we should pass along the type information for 'Derived'. This is also what @rsmith suggests.

[vsk]

• Remove some default arguments left over from an older revision of this patch.
• Simplify the test.

[rjmccall]

In D25448#572245, @vsk wrote:

Patch update: Pass along the type info of the derived class to the ubsan runtime when we devirtualize a method call. This squashes the FP. I tested this with 'check-ubsan' in addition to adding a lit test.

A pointer to the vtable pointer for Base1 is a pointer to a Derived. You have a multiple inheritance bug, or really a general inheritance bug. It's being covered up in the case of single, non-virtual inheritance because that's the case in which a pointer to a base-class object is the same as a pointer to the derived class object.

I imagine that it would be difficult to extend the runtime to handle this case. I.e, given a pointer to vtable pointer for Base1 and the type info for Base2, recognize that we may _actually_ be looking at an instance of Derived, and therefore claim that the types match.

I don't know how the runtime parts of this check are implemented. It is certainly true that an object that is a Base1 might also be a Base2 due to multiple inheritance. But given a pointer that's statically typed to be a Base2, I believe you want to be checking not "am I pointing at an object whose dynamic type derives from Base2" but "am I pointing *at the Base2 subobject* of an object whose dynamic type derives from Base1", which is a very different check and doesn't necessarily require the same runtime complexity (or might need more, depending on what you're doing).

But anyway, the pointer you're passing does not point to the Base2 subobject anymore, which is clearly a frontend bug, not a runtime bug.

I wonder if that would result in a false negative in this case:

Base1 b1;
reinterpret_cast<Base2 *>(b1)->method_from_base2_only()

We are currently able to diagnose this.

I can't imagine what on earth you would do in the runtime that would have a false-negative problem here without basically disabling the check, but let's leave that aside.

... it should also be changing its notion of what class the pointer points to.

I'm taking this to mean that we should pass along the type information for 'Derived'. This is also what @rsmith suggests.

Yes, this is what you should do. Your runtime logic is, somehow, checking whether the memory contains an object of some type that you know statically. Devirt is potentially changing where your pointer points and thus also changing the expected static type of the memory you're pointing to. Properly responding to that change will not only fix the logic here, it will strengthen your check so that you also detect the bug here:

Base1 p;
Derived *badp = static_cast<Derived*>(&p);
static_cast<Base1*>(badp)->method_that_is_final_in_derived();

[rjmccall]

lib/CodeGen/CGExprCXX.cpp

31

Shouldn't MD just be the devirtualized method? That should avoid the need to pass down something different for the devirt case here.

[vsk]

Thanks for the feedback!

Patch update:

• Pass in the right CalleeDecl to EmitCXXMemberOrOperatorCall. This lets us drop the unnecessary 'DevirtualizedClassTy' optional parameter.
• Extend the test case with John's example (devirt for methods marked 'final'). Since this hasn't yet been implemented in clang, make the checks depend on the relevant bug (PR13127).

Tested with check-ubsan and check-clang.

[rjmccall]

Looks great, thanks.

lib/CodeGen/CGExprCXX.cpp

 #include "clang/CodeGen/CGFunctionInfo.h"
 #include "clang/Frontend/CodeGenOptions.h"
 #include "llvm/IR/CallSite.h"
 #include "llvm/IR/Intrinsics.h"
 
 using namespace clang;
 using namespace CodeGen;
 
-static RequiredArgs
-commonEmitCXXMemberOrOperatorCall(CodeGenFunction &CGF, const CXXMethodDecl *MD,
-                                  llvm::Value *This, llvm::Value *ImplicitParam,
-                                  QualType ImplicitParamTy, const CallExpr *CE,
-                                  CallArgList &Args, CallArgList *RtlArgs) {
+static RequiredArgs commonEmitCXXMemberOrOperatorCall(
+    CodeGenFunction &CGF, const CXXMethodDecl *MD, llvm::Value *This,
+    llvm::Value *ImplicitParam, QualType ImplicitParamTy, const CallExpr *CE,
+    CallArgList &Args, CallArgList *RtlArgs,
+    llvm::Optional<QualType> DevirtualizedClassTy) {
   assert(CE == nullptr || isa<CXXMemberCallExpr>(CE) ||
          isa<CXXOperatorCallExpr>(CE));
   assert(MD->isInstance() &&
          "Trying to emit a member or operator call expr on a static method!");
   ASTContext &C = CGF.getContext();
 
   // C++11 [class.mfct.non-static]p2:
   //   If a non-static member function of a class X is called for an object that
   //   is not of type X, or of a type derived from X, the behavior is undefined.
   SourceLocation CallLoc;
   if (CE)
     CallLoc = CE->getExprLoc();
+  QualType Ty = DevirtualizedClassTy.hasValue()
+                    ? DevirtualizedClassTy.getValue()
+                    : C.getRecordType(MD->getParent());
   CGF.EmitTypeCheck(isa<CXXConstructorDecl>(MD)
                         ? CodeGenFunction::TCK_ConstructorCall
                         : CodeGenFunction::TCK_MemberCall,
-                    CallLoc, This, C.getRecordType(MD->getParent()));
+                    CallLoc, This, Ty,
+                    /*Alignment=*/CharUnits::Zero(), /*SkipNullCheck=*/false);
 
   // Push the this ptr.
   const CXXRecordDecl *RD =
       CGF.CGM.getCXXABI().getThisArgumentTypeForMethod(MD);
   Args.add(RValue::get(This),
            RD ? C.getPointerType(C.getTypeDeclType(RD)) : C.VoidPtrTy);
 
   // If there is an implicit parameter (e.g. VTT), emit it.
assert(
         "No CallExpr specified for function with non-zero number of arguments");
   }
   return required;
 }
 
 RValue CodeGenFunction::EmitCXXMemberOrOperatorCall(
     const CXXMethodDecl *MD, llvm::Value *Callee, ReturnValueSlot ReturnValue,
     llvm::Value *This, llvm::Value *ImplicitParam, QualType ImplicitParamTy,
-    const CallExpr *CE, CallArgList *RtlArgs) {
+    const CallExpr *CE, CallArgList *RtlArgs,
+    llvm::Optional<QualType> DevirtualizedClassTy) {
   const FunctionProtoType *FPT = MD->getType()->castAs<FunctionProtoType>();
   CallArgList Args;
   RequiredArgs required = commonEmitCXXMemberOrOperatorCall(
-      *this, MD, This, ImplicitParam, ImplicitParamTy, CE, Args, RtlArgs);
+      *this, MD, This, ImplicitParam, ImplicitParamTy, CE, Args, RtlArgs,
+      DevirtualizedClassTy);
   return EmitCall(CGM.getTypes().arrangeCXXMethodCall(Args, FPT, required),
                   Callee, ReturnValue, Args, MD);
 }
 
 RValue CodeGenFunction::EmitCXXDestructorCall(
     const CXXDestructorDecl *DD, llvm::Value *Callee, llvm::Value *This,
     llvm::Value *ImplicitParam, QualType ImplicitParamTy, const CallExpr *CE,
     StructorType Type) {
   CallArgList Args;
   commonEmitCXXMemberOrOperatorCall(*this, DD, This, ImplicitParam,
-                                    ImplicitParamTy, CE, Args, nullptr);
+                                    ImplicitParamTy, CE, Args, nullptr,
+                                    llvm::None);
   return EmitCall(CGM.getTypes().arrangeCXXStructorDeclaration(DD, Type),
                   Callee, ReturnValueSlot(), Args, DD);
 }
 
 static CXXRecordDecl *getCXXRecord(const Expr *E) {
   QualType T = E->getType();
   if (const PointerType *PTy = T->getAs<PointerType>())
     T = PTy->getPointeeType();
RValue CodeGenFunction::EmitCXXMemberOrOperatorMemberCallExpr(
     bool HasQualifier, NestedNameSpecifier *Qualifier, bool IsArrow,
     const Expr *Base) {
   assert(isa<CXXMemberCallExpr>(CE) || isa<CXXOperatorCallExpr>(CE));
 
   // Compute the object pointer.
   bool CanUseVirtualCall = MD->isVirtual() && !HasQualifier;
 
   const CXXMethodDecl *DevirtualizedMethod = nullptr;
+  llvm::Optional<QualType> DevirtualizedClassTy = llvm::None;
   if (CanUseVirtualCall && CanDevirtualizeMemberFunctionCall(Base, MD)) {
     const CXXRecordDecl *BestDynamicDecl = Base->getBestDynamicClassType();
     DevirtualizedMethod = MD->getCorrespondingMethodInClass(BestDynamicDecl);
     assert(DevirtualizedMethod);
     const CXXRecordDecl *DevirtualizedClass = DevirtualizedMethod->getParent();
     const Expr *Inner = Base->ignoreParenBaseCasts();
     if (DevirtualizedMethod->getReturnType().getCanonicalType() !=
         MD->getReturnType().getCanonicalType())
       // If the return types are not the same, this might be a case where more
       // code needs to run to compensate for it. For example, the derived
       // method might return a type that inherits form from the return
       // type of MD and has a prefix.
       // For now we just avoid devirtualizing these covariant cases.
       DevirtualizedMethod = nullptr;
-    else if (getCXXRecord(Inner) == DevirtualizedClass)
+    else if (getCXXRecord(Inner) == DevirtualizedClass) {
       // If the class of the Inner expression is where the dynamic method
       // is defined, build the this pointer from it.
       Base = Inner;
-    else if (getCXXRecord(Base) != DevirtualizedClass) {
+      DevirtualizedClassTy = QualType(BestDynamicDecl->getTypeForDecl(),
+                                      Base->getType().getLocalFastQualifiers());
+    } else if (getCXXRecord(Base) != DevirtualizedClass) {
       // If the method is defined in a class that is not the best dynamic
       // one or the one of the full expression, we would have to build
       // a derived-to-base cast to compute the correct this pointer, but
       // we don't have support for that yet, so do a virtual call.
       DevirtualizedMethod = nullptr;
     }
   }
 
if (UseVirtualCall) {
             CGM.getAddrOfCXXStructor(Dtor, StructorType::Complete, FInfo, Ty);
       else {
         const CXXDestructorDecl *DDtor =
           cast<CXXDestructorDecl>(DevirtualizedMethod);
         Callee = CGM.GetAddrOfFunction(GlobalDecl(DDtor, Dtor_Complete), Ty);
       }
       EmitCXXMemberOrOperatorCall(MD, Callee, ReturnValue, This.getPointer(),
                                   /*ImplicitParam=*/nullptr, QualType(), CE,
-                                  nullptr);
+                                  nullptr, DevirtualizedClassTy);
     }
     return RValue::get(nullptr);
   }
   
   if (const CXXConstructorDecl *Ctor = dyn_cast<CXXConstructorDecl>(MD)) {
     Callee = CGM.GetAddrOfFunction(GlobalDecl(Ctor, Ctor_Complete), Ty);
   } else if (UseVirtualCall) {
     Callee = CGM.getCXXABI().getVirtualFunctionPointer(*this, MD, This, Ty,
RValue CodeGenFunction::EmitCXXMemberOrOperatorMemberCallExpr(
 
   if (MD->isVirtual()) {
     This = CGM.getCXXABI().adjustThisArgumentForVirtualFunctionCall(
         *this, CalleeDecl, This, UseVirtualCall);
   }
 
   return EmitCXXMemberOrOperatorCall(MD, Callee, ReturnValue, This.getPointer(),
                                      /*ImplicitParam=*/nullptr, QualType(), CE,
-                                     RtlArgs);
+                                     RtlArgs, DevirtualizedClassTy);
 }
 
 RValue
 CodeGenFunction::EmitCXXMemberPointerCallExpr(const CXXMemberCallExpr *E,
                                               ReturnValueSlot ReturnValue) {
   const BinaryOperator *BO =
       cast<BinaryOperator>(E->getCallee()->IgnoreParens());
   const Expr *BaseExpr = BO->getLHS();

lib/CodeGen/CodeGenFunction.h

   llvm::Value *BuildAppleKextVirtualCall(const CXXMethodDecl *MD, 
                                          NestedNameSpecifier *Qual,
                                          llvm::Type *Ty);
   
   llvm::Value *BuildAppleKextVirtualDestructorCall(const CXXDestructorDecl *DD,
                                                    CXXDtorType Type, 
                                                    const CXXRecordDecl *RD);
 
-  RValue
-  EmitCXXMemberOrOperatorCall(const CXXMethodDecl *MD, llvm::Value *Callee,
-                              ReturnValueSlot ReturnValue, llvm::Value *This,
-                              llvm::Value *ImplicitParam,
-                              QualType ImplicitParamTy, const CallExpr *E,
-                              CallArgList *RtlArgs);
+  RValue EmitCXXMemberOrOperatorCall(
+      const CXXMethodDecl *MD, llvm::Value *Callee, ReturnValueSlot ReturnValue,
+      llvm::Value *This, llvm::Value *ImplicitParam, QualType ImplicitParamTy,
+      const CallExpr *E, CallArgList *RtlArgs,
+      llvm::Optional<QualType> DevirtualizedClassTy = llvm::None);
   RValue EmitCXXDestructorCall(const CXXDestructorDecl *DD, llvm::Value *Callee,
                                llvm::Value *This, llvm::Value *ImplicitParam,
                                QualType ImplicitParamTy, const CallExpr *E,
                                StructorType Type);
   RValue EmitCXXMemberCallExpr(const CXXMemberCallExpr *E,
                                ReturnValueSlot ReturnValue);
   RValue EmitCXXMemberOrOperatorMemberCallExpr(const CallExpr *CE,
                                                const CXXMethodDecl *MD,

test/CodeGenCXX/ubsan-devirtualized-calls.cpp

+// RUN: %clang_cc1 -std=c++11 -triple %itanium_abi_triple -emit-llvm -fsanitize=vptr %s -o - | FileCheck %s
+
+struct Base1 {
+  virtual int f1() { return 1; }
+};
+
+struct Base2 {
+  virtual int f1() { return 2; }
+};
+
+struct Derived1 final : Base1 {
+  int f1() override { return 3; }
+};
+
+struct Derived2 final : Base1, Base2 {
+  int f1() override { return 3; }
+};
+
+// CHECK: [[UBSAN_TI_DERIVED1:@[0-9]+]] = private unnamed_addr global {{.*}} i8* bitcast ({ i8*, i8*, i8* }* @_ZTI8Derived1 to i8*
+// CHECK: [[UBSAN_TI_DERIVED2_1:@[0-9]+]] = private unnamed_addr global {{.*}} i8* bitcast ({ i8*, i8*, i32, i32, i8*, i64, i8*, i64 }* @_ZTI8Derived2 to i8*
+// CHECK: [[UBSAN_TI_DERIVED2_2:@[0-9]+]] = private unnamed_addr global {{.*}} i8* bitcast ({ i8*, i8*, i32, i32, i8*, i64, i8*, i64 }* @_ZTI8Derived2 to i8*
+// CHECK: [[UBSAN_TI_DERIVED2_3:@[0-9]+]] = private unnamed_addr global {{.*}} i8* bitcast ({ i8*, i8*, i32, i32, i8*, i64, i8*, i64 }* @_ZTI8Derived2 to i8*
+
+// CHECK-LABEL: define i32 @_Z2t1v
+int t1() {
+  Derived1 d1;
+  return static_cast<Base1 *>(&d1)->f1();
+  // CHECK: handler.dynamic_type_cache_miss:
+  // CHECK-NEXT: %[[D1:[0-9]+]] = ptrtoint %struct.Derived1* %d1 to i64, !nosanitize
+  // CHECK-NEXT: call void @{{[_a-z]+}}({{.*}} [[UBSAN_TI_DERIVED1]] {{.*}}, i64 %[[D1]]
+}
+
+// CHECK-LABEL: define i32 @_Z2t2v
+int t2() {
+  Derived2 d2;
+  return static_cast<Base1 *>(&d2)->f1();
+  // CHECK: handler.dynamic_type_cache_miss:
+  // CHECK-NEXT: %[[D2_1:[0-9]+]] = ptrtoint %struct.Derived2* %d2 to i64, !nosanitize
+  // CHECK-NEXT: call void @{{[_a-z]+}}({{.*}} [[UBSAN_TI_DERIVED2_1]] {{.*}}, i64 %[[D2_1]]
+}
+
+// CHECK-LABEL: define i32 @_Z2t3v
+int t3() {
+  Derived2 d2;
+  return static_cast<Base2 *>(&d2)->f1();
+  // CHECK: handler.dynamic_type_cache_miss:
+  // CHECK-NEXT: %[[D2_2:[0-9]+]] = ptrtoint %struct.Derived2* %d2 to i64, !nosanitize
+  // CHECK-NEXT: call void @{{[_a-z]+}}({{.*}} [[UBSAN_TI_DERIVED2_2]] {{.*}}, i64 %[[D2_2]]
+}
+
+// CHECK-LABEL: define i32 @_Z2t4v
+int t4() {
+  Derived2 d2;
+  return d2.Derived2::f1();
+  // CHECK: handler.dynamic_type_cache_miss:
+  // CHECK-NEXT: %[[D2_3:[0-9]+]] = ptrtoint %struct.Derived2* %d2 to i64, !nosanitize
+  // CHECK-NEXT: call void @{{[_a-z]+}}({{.*}} [[UBSAN_TI_DERIVED2_3]] {{.*}}, i64 %[[D2_3]]
+}