Index: lib/Transforms/Instrumentation/PoisonChecking.cpp =================================================================== --- lib/Transforms/Instrumentation/PoisonChecking.cpp +++ lib/Transforms/Instrumentation/PoisonChecking.cpp @@ -182,6 +182,81 @@ }; } +/// Generate checks which evaluate to true if we can tell that the given +/// pointer is out of bounds for the allocation on which it is based. +static void generateAddressBoundsChecks(IRBuilder<> &B, + Value *Ptr, const DataLayout& DL, + SmallVector &Checks) { + assert(Ptr->getType()->isPointerTy()); + Value *Obj = GetUnderlyingObject(Ptr, DL); + if (!Obj) + return; + // CAUTION: At this point we know that Obj is *some* pointer w/in + // Allocation A, but we do NOT know that A.start == Obj. As such, there + // may be inbounds addresses between the unknown A.start and Obj. We also do + // not know if Obj <= I.getPointerOperand(). + + // Even if we know the distance between Obj and A.end, we still don't know + // the offset of Obj w/in A. + uint64_t SizeInBytes; + const bool GenUpperCheck = getObjectSize(Obj, SizeInBytes, DL, nullptr); + + // Is this known to the be the start of some allocation? If we know that Obj + // is actually a start an an allocation, than any address below that must be + // out of bounds. + // TODO: expand this and integrate w/MemoryBuiltins.h + bool isKnownAllocationStart = isa(Obj); + + const bool GenLowerCheck = isKnownAllocationStart; + if (!GenUpperCheck && !GenLowerCheck) + return; + + auto *I8PtrTy = B.getInt8PtrTy(Ptr->getType()->getPointerAddressSpace()); + auto *Addr = B.CreateBitCast(Ptr, I8PtrTy); + auto *Base = B.CreateBitCast(Obj, I8PtrTy, "lower.limit"); + + if (GenUpperCheck) { + auto *UpperLimit = B.CreateGEP(Base, B.getInt64(SizeInBytes), + "upper.limit"); + Checks.push_back(B.CreateICmp(ICmpInst::ICMP_UGT, Addr, UpperLimit)); + } + if (GenLowerCheck) + Checks.push_back(B.CreateICmp(ICmpInst::ICMP_ULT, Addr, Base)); +} + +static void generatePoisonChecksForInboundsGEP(IRBuilder<> &B, + GetElementPtrInst& GEP, + SmallVector &Checks) { + assert(GEP.isInBounds()); + if (GEP.getType()->isVectorTy()) + return; + + auto &DL = GEP.getModule()->getDataLayout(); + Type *I8PtrTy = B.getInt8PtrTy(GEP.getType()->getPointerAddressSpace()); + Value *Base = B.CreateBitCast(GEP.getPointerOperand(), I8PtrTy, "base.i8"); + // First, check that the base pointer is in bounds for the allocation. If it + // isn't, an inbounds gep unconditionally produces UB. + generateAddressBoundsChecks(B, Base, DL, Checks); + + // Second, check that the result of the GEP is inbounds for the allocation. + auto *NewGEP = cast(GEP.clone()); + NewGEP->setIsInBounds(false); + NewGEP->insertBefore(&GEP); + Value *Addr = B.CreateBitCast(NewGEP, I8PtrTy, "addr.i8"); + generateAddressBoundsChecks(B, Addr, DL, Checks); + + // Third, check that GEP >= GEP.base for non-negative offsets. This catches + // the case where a) we can't find the underlying allocation above, or b) we + // wrapped all the way around and ended up back in bounds of the same + // allocation (and no allocation can wrap around, thus poison!). + bool IsNonNegativeOffset = true; + for (unsigned i = 1; i < GEP.getNumOperands() && IsNonNegativeOffset; i++) + IsNonNegativeOffset &= isKnownNonNegative(GEP.getOperand(i), DL); + + if (IsNonNegativeOffset) + Checks.push_back(B.CreateICmp(ICmpInst::ICMP_ULT, Addr, Base)); +} + static Value* generatePoisonChecks(Instruction &I) { IRBuilder<> B(&I); SmallVector Checks; @@ -216,6 +291,13 @@ Checks.push_back(Check); break; } + case Instruction::GetElementPtr: { + auto &GEP = cast(I); + if (!GEP.isInBounds()) + break; + generatePoisonChecksForInboundsGEP(B, GEP, Checks); + break; + } }; return buildOrChain(B, Checks); } Index: test/Instrumentation/PoisonChecking/basic-flag-validation.ll =================================================================== --- test/Instrumentation/PoisonChecking/basic-flag-validation.ll +++ test/Instrumentation/PoisonChecking/basic-flag-validation.ll @@ -320,3 +320,112 @@ ret <4 x i32> %res } + +define void @gep_inbounds_generic(i8* %base, i32 %n) { +; CHECK-LABEL: @gep_inbounds_generic( +; CHECK-NEXT: [[TMP1:%.*]] = getelementptr i8, i8* [[BASE:%.*]], i32 [[N:%.*]] +; CHECK-NEXT: [[P:%.*]] = getelementptr inbounds i8, i8* [[BASE]], i32 [[N]] +; CHECK-NEXT: store i8 0, i8* [[P]] +; CHECK-NEXT: ret void +; + %p = getelementptr inbounds i8, i8* %base, i32 %n + store i8 0, i8* %p + ret void +} + +define void @gep_inbounds_positive_offset(i8* %base) { +; CHECK-LABEL: @gep_inbounds_positive_offset( +; CHECK-NEXT: [[TMP1:%.*]] = getelementptr i8, i8* [[BASE:%.*]], i32 10 +; CHECK-NEXT: [[TMP2:%.*]] = icmp ult i8* [[TMP1]], [[BASE]] +; CHECK-NEXT: [[P:%.*]] = getelementptr inbounds i8, i8* [[BASE]], i32 10 +; CHECK-NEXT: [[TMP3:%.*]] = xor i1 [[TMP2]], true +; CHECK-NEXT: call void @__poison_checker_assert(i1 [[TMP3]]) +; CHECK-NEXT: store i8 0, i8* [[P]] +; CHECK-NEXT: ret void +; + %p = getelementptr inbounds i8, i8* %base, i32 10 + store i8 0, i8* %p + ret void +} + +define void @gep_inbounds_hidden_negative_offset(i8* %base) { +; CHECK-LABEL: @gep_inbounds_hidden_negative_offset( +; CHECK-NEXT: [[TMP1:%.*]] = getelementptr i8, i8* [[BASE:%.*]], i32 -20 +; CHECK-NEXT: [[P1:%.*]] = getelementptr inbounds i8, i8* [[BASE]], i32 -20 +; CHECK-NEXT: [[TMP2:%.*]] = getelementptr i8, i8* [[P1]], i32 10 +; CHECK-NEXT: [[TMP3:%.*]] = icmp ult i8* [[TMP2]], [[P1]] +; CHECK-NEXT: [[P:%.*]] = getelementptr inbounds i8, i8* [[P1]], i32 10 +; CHECK-NEXT: [[TMP4:%.*]] = xor i1 [[TMP3]], true +; CHECK-NEXT: call void @__poison_checker_assert(i1 [[TMP4]]) +; CHECK-NEXT: store i8 0, i8* [[P]] +; CHECK-NEXT: ret void +; + %p1 = getelementptr inbounds i8, i8* %base, i32 -20 + %p = getelementptr inbounds i8, i8* %p1, i32 10 + store i8 0, i8* %p + ret void +} + + +define void @gep_inbounds_known_base_and_size(i32 %n) { +; CHECK-LABEL: @gep_inbounds_known_base_and_size( +; CHECK-NEXT: [[ALLOCA:%.*]] = alloca [200 x i8] +; CHECK-NEXT: [[BASE:%.*]] = bitcast [200 x i8]* [[ALLOCA]] to i8* +; CHECK-NEXT: [[LOWER_LIMIT:%.*]] = bitcast [200 x i8]* [[ALLOCA]] to i8* +; CHECK-NEXT: [[UPPER_LIMIT:%.*]] = getelementptr i8, i8* [[LOWER_LIMIT]], i64 200 +; CHECK-NEXT: [[TMP1:%.*]] = icmp ugt i8* [[BASE]], [[UPPER_LIMIT]] +; CHECK-NEXT: [[TMP2:%.*]] = icmp ult i8* [[BASE]], [[LOWER_LIMIT]] +; CHECK-NEXT: [[TMP3:%.*]] = getelementptr i8, i8* [[BASE]], i32 [[N:%.*]] +; CHECK-NEXT: [[LOWER_LIMIT1:%.*]] = bitcast [200 x i8]* [[ALLOCA]] to i8* +; CHECK-NEXT: [[UPPER_LIMIT2:%.*]] = getelementptr i8, i8* [[LOWER_LIMIT1]], i64 200 +; CHECK-NEXT: [[TMP4:%.*]] = icmp ugt i8* [[TMP3]], [[UPPER_LIMIT2]] +; CHECK-NEXT: [[TMP5:%.*]] = icmp ult i8* [[TMP3]], [[LOWER_LIMIT1]] +; CHECK-NEXT: [[TMP6:%.*]] = or i1 [[TMP1]], [[TMP2]] +; CHECK-NEXT: [[TMP7:%.*]] = or i1 [[TMP6]], [[TMP4]] +; CHECK-NEXT: [[TMP8:%.*]] = or i1 [[TMP7]], [[TMP5]] +; CHECK-NEXT: [[P:%.*]] = getelementptr inbounds i8, i8* [[BASE]], i32 [[N]] +; CHECK-NEXT: [[TMP9:%.*]] = xor i1 [[TMP8]], true +; CHECK-NEXT: call void @__poison_checker_assert(i1 [[TMP9]]) +; CHECK-NEXT: store i8 0, i8* [[P]] +; CHECK-NEXT: ret void +; + %alloca = alloca [200 x i8] + %base = bitcast [200 x i8]* %alloca to i8* + %p = getelementptr inbounds i8, i8* %base, i32 %n + store i8 0, i8* %p + ret void +} + +define void @gep_inbounds_known_base_and_size_out_of_bounds_origin(i32 %n) { +; CHECK-LABEL: @gep_inbounds_known_base_and_size_out_of_bounds_origin( +; CHECK-NEXT: [[ALLOCA:%.*]] = alloca [200 x i8] +; CHECK-NEXT: [[BASE:%.*]] = bitcast [200 x i8]* [[ALLOCA]] to i8* +; CHECK-NEXT: [[P1:%.*]] = getelementptr i8, i8* [[BASE]], i32 202 +; CHECK-NEXT: [[LOWER_LIMIT:%.*]] = bitcast [200 x i8]* [[ALLOCA]] to i8* +; CHECK-NEXT: [[UPPER_LIMIT:%.*]] = getelementptr i8, i8* [[LOWER_LIMIT]], i64 200 +; CHECK-NEXT: [[TMP1:%.*]] = icmp ugt i8* [[P1]], [[UPPER_LIMIT]] +; CHECK-NEXT: [[TMP2:%.*]] = icmp ult i8* [[P1]], [[LOWER_LIMIT]] +; CHECK-NEXT: [[TMP3:%.*]] = getelementptr i8, i8* [[P1]], i32 [[N:%.*]] +; CHECK-NEXT: [[LOWER_LIMIT1:%.*]] = bitcast [200 x i8]* [[ALLOCA]] to i8* +; CHECK-NEXT: [[UPPER_LIMIT2:%.*]] = getelementptr i8, i8* [[LOWER_LIMIT1]], i64 200 +; CHECK-NEXT: [[TMP4:%.*]] = icmp ugt i8* [[TMP3]], [[UPPER_LIMIT2]] +; CHECK-NEXT: [[TMP5:%.*]] = icmp ult i8* [[TMP3]], [[LOWER_LIMIT1]] +; CHECK-NEXT: [[TMP6:%.*]] = or i1 [[TMP1]], [[TMP2]] +; CHECK-NEXT: [[TMP7:%.*]] = or i1 [[TMP6]], [[TMP4]] +; CHECK-NEXT: [[TMP8:%.*]] = or i1 [[TMP7]], [[TMP5]] +; CHECK-NEXT: [[P:%.*]] = getelementptr inbounds i8, i8* [[P1]], i32 [[N]] +; CHECK-NEXT: [[TMP9:%.*]] = xor i1 [[TMP8]], true +; CHECK-NEXT: call void @__poison_checker_assert(i1 [[TMP9]]) +; CHECK-NEXT: store i8 0, i8* [[P]] +; CHECK-NEXT: ret void +; + %alloca = alloca [200 x i8] + %base = bitcast [200 x i8]* %alloca to i8* + %p1 = getelementptr i8, i8* %base, i32 202 + %p = getelementptr inbounds i8, i8* %p1, i32 %n + store i8 0, i8* %p + ret void +} + + +