← Back to branch summary

~ubuntu-branches/ubuntu/raring/clamav/raring-updates

« back to all changes in this revision

Viewing changes to libclamav/c++/PointerTracking.cpp

  • Committer: Bazaar Package Importer
  • Author(s): Scott Kitterman
  • Date: 2011-06-18 11:56:34 UTC
  • mfrom: (0.35.21 sid)
  • Revision ID: james.westby@ubuntu.com-20110618115634-u2lovivet0qx34d0
Tags: 0.97.1+dfsg-1ubuntu1
* Merge from debian unstable.  Remaining changes:
  - Drop build-dep on electric-fence (in Universe)
  - Add apparmor profiles for clamd and freshclam along with maintainer
    script changes

Show diffs side-by-side

added added

removed removed

Lines of Context:
libclamav/c++/PointerTracking.cpp
 
1
//===- PointerTracking.cpp - Pointer Bounds Tracking ------------*- C++ -*-===//
 
2
//
 
3
//                     The LLVM Compiler Infrastructure
 
4
//
 
5
// This file is distributed under the University of Illinois Open Source
 
6
// License. See LICENSE.TXT for details.
 
7
//
 
8
//===----------------------------------------------------------------------===//
 
9
//
 
10
// This file implements tracking of pointer bounds.
 
11
//
 
12
//===----------------------------------------------------------------------===//
 
13
 
 
14
/* this shouldn't be part of win32 proj at all, but its easier to exclude here
 
15
 * */
 
16
#ifndef _WIN32
 
17
 
 
18
#include "llvm/Analysis/ConstantFolding.h"
 
19
#include "llvm/Analysis/Dominators.h"
 
20
#include "llvm/Analysis/LoopInfo.h"
 
21
#include "llvm/Analysis/MemoryBuiltins.h"
 
22
#include "llvm/Analysis/ValueTracking.h"
 
23
#include "PointerTracking.h"
 
24
#include "llvm/Analysis/ScalarEvolution.h"
 
25
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
 
26
#include "llvm/Constants.h"
 
27
#include "llvm/Module.h"
 
28
#include "llvm/Value.h"
 
29
#include "llvm/Support/CallSite.h"
 
30
#include "llvm/Support/InstIterator.h"
 
31
#include "llvm/Support/raw_ostream.h"
 
32
#include "llvm/Target/TargetData.h"
 
33
using namespace llvm;
 
34
namespace llvm {
 
35
    void initializePointerTrackingPass(llvm::PassRegistry&);
 
36
};
 
37
INITIALIZE_PASS(PointerTracking, "pointertracking",
 
38
                "Track pointer bounds", false, true);
 
39
char PointerTracking::ID = 0;
 
40
PointerTracking::PointerTracking() : FunctionPass(ID) {
 
41
    initializePointerTrackingPass(*PassRegistry::getPassRegistry());
 
42
}
 
43
 
 
44
bool PointerTracking::runOnFunction(Function &F) {
 
45
  predCache.clear();
 
46
  assert(analyzing.empty());
 
47
  FF = &F;
 
48
  TD = getAnalysisIfAvailable<TargetData>();
 
49
  SE = &getAnalysis<ScalarEvolution>();
 
50
  LI = &getAnalysis<LoopInfo>();
 
51
  DT = &getAnalysis<DominatorTree>();
 
52
  return false;
 
53
}
 
54
 
 
55
void PointerTracking::getAnalysisUsage(AnalysisUsage &AU) const {
 
56
  AU.addRequiredTransitive<DominatorTree>();
 
57
  AU.addRequiredTransitive<LoopInfo>();
 
58
  AU.addRequiredTransitive<ScalarEvolution>();
 
59
  AU.setPreservesAll();
 
60
}
 
61
 
 
62
bool PointerTracking::doInitialization(Module &M) {
 
63
  const Type *PTy = Type::getInt8PtrTy(M.getContext());
 
64
 
 
65
  // Find calloc(i64, i64) or calloc(i32, i32).
 
66
  callocFunc = M.getFunction("calloc");
 
67
  if (callocFunc) {
 
68
    const FunctionType *Ty = callocFunc->getFunctionType();
 
69
 
 
70
    std::vector<const Type*> args, args2;
 
71
    args.push_back(Type::getInt64Ty(M.getContext()));
 
72
    args.push_back(Type::getInt64Ty(M.getContext()));
 
73
    args2.push_back(Type::getInt32Ty(M.getContext()));
 
74
    args2.push_back(Type::getInt32Ty(M.getContext()));
 
75
    const FunctionType *Calloc1Type =
 
76
      FunctionType::get(PTy, args, false);
 
77
    const FunctionType *Calloc2Type =
 
78
      FunctionType::get(PTy, args2, false);
 
79
    if (Ty != Calloc1Type && Ty != Calloc2Type)
 
80
      callocFunc = 0; // Give up
 
81
  }
 
82
 
 
83
  // Find realloc(i8*, i64) or realloc(i8*, i32).
 
84
  reallocFunc = M.getFunction("realloc");
 
85
  if (reallocFunc) {
 
86
    const FunctionType *Ty = reallocFunc->getFunctionType();
 
87
    std::vector<const Type*> args, args2;
 
88
    args.push_back(PTy);
 
89
    args.push_back(Type::getInt64Ty(M.getContext()));
 
90
    args2.push_back(PTy);
 
91
    args2.push_back(Type::getInt32Ty(M.getContext()));
 
92
 
 
93
    const FunctionType *Realloc1Type =
 
94
      FunctionType::get(PTy, args, false);
 
95
    const FunctionType *Realloc2Type =
 
96
      FunctionType::get(PTy, args2, false);
 
97
    if (Ty != Realloc1Type && Ty != Realloc2Type)
 
98
      reallocFunc = 0; // Give up
 
99
  }
 
100
  return false;
 
101
}
 
102
 
 
103
// Calculates the number of elements allocated for pointer P,
 
104
// the type of the element is stored in Ty.
 
105
const SCEV *PointerTracking::computeAllocationCount(Value *P,
 
106
                                                    const Type *&Ty) const {
 
107
  Value *V = P->stripPointerCasts();
 
108
  if (AllocaInst *AI = dyn_cast<AllocaInst>(V)) {
 
109
    Value *arraySize = AI->getArraySize();
 
110
    Ty = AI->getAllocatedType();
 
111
    // arraySize elements of type Ty.
 
112
    return SE->getSCEV(arraySize);
 
113
  }
 
114
 
 
115
  if (CallInst *CI = extractMallocCall(V)) {
 
116
    Value *arraySize = getMallocArraySize(CI, TD);
 
117
    const Type* AllocTy = getMallocAllocatedType(CI);
 
118
    if (!AllocTy || !arraySize) return SE->getCouldNotCompute();
 
119
    Ty = AllocTy;
 
120
    // arraySize elements of type Ty.
 
121
    return SE->getSCEV(arraySize);
 
122
  }
 
123
 
 
124
  if (GlobalVariable *GV = dyn_cast<GlobalVariable>(V)) {
 
125
    if (GV->hasDefinitiveInitializer()) {
 
126
      Constant *C = GV->getInitializer();
 
127
      if (const ArrayType *ATy = dyn_cast<ArrayType>(C->getType())) {
 
128
        Ty = ATy->getElementType();
 
129
        return SE->getConstant(Type::getInt32Ty(P->getContext()),
 
130
                               ATy->getNumElements());
 
131
      }
 
132
    }
 
133
    Ty = GV->getType();
 
134
    return SE->getConstant(Type::getInt32Ty(P->getContext()), 1);
 
135
    //TODO: implement more tracking for globals
 
136
  }
 
137
 
 
138
  if (CallInst *CI = dyn_cast<CallInst>(V)) {
 
139
    CallSite CS(CI);
 
140
    Function *F = dyn_cast<Function>(CS.getCalledValue()->stripPointerCasts());
 
141
    const Loop *L = LI->getLoopFor(CI->getParent());
 
142
    if (F == callocFunc) {
 
143
      Ty = Type::getInt8Ty(P->getContext());
 
144
      // calloc allocates arg0*arg1 bytes.
 
145
      return SE->getSCEVAtScope(SE->getMulExpr(SE->getSCEV(CS.getArgument(0)),
 
146
                                               SE->getSCEV(CS.getArgument(1))),
 
147
                                L);
 
148
    } else if (F == reallocFunc) {
 
149
      Ty = Type::getInt8Ty(P->getContext());
 
150
      // realloc allocates arg1 bytes.
 
151
      return SE->getSCEVAtScope(CS.getArgument(1), L);
 
152
    }
 
153
  }
 
154
 
 
155
  return SE->getCouldNotCompute();
 
156
}
 
157
 
 
158
Value *PointerTracking::computeAllocationCountValue(Value *P, const Type *&Ty) const 
 
159
{
 
160
  Value *V = P->stripPointerCasts();
 
161
  if (AllocaInst *AI = dyn_cast<AllocaInst>(V)) {
 
162
    Ty = AI->getAllocatedType();
 
163
    // arraySize elements of type Ty.
 
164
    return AI->getArraySize();
 
165
  }
 
166
 
 
167
  if (CallInst *CI = extractMallocCall(V)) {
 
168
    Ty = getMallocAllocatedType(CI);
 
169
    if (!Ty)
 
170
      return 0;
 
171
    Value *arraySize = getMallocArraySize(CI, TD);
 
172
    if (!arraySize) {
 
173
      Ty = Type::getInt8Ty(P->getContext());
 
174
      return CI->getArgOperand(0);
 
175
    }
 
176
    // arraySize elements of type Ty.
 
177
    return arraySize;
 
178
  }
 
179
 
 
180
  if (GlobalVariable *GV = dyn_cast<GlobalVariable>(V)) {
 
181
    if (GV->hasDefinitiveInitializer()) {
 
182
      Constant *C = GV->getInitializer();
 
183
      if (const ArrayType *ATy = dyn_cast<ArrayType>(C->getType())) {
 
184
        Ty = ATy->getElementType();
 
185
        return ConstantInt::get(Type::getInt32Ty(P->getContext()),
 
186
                               ATy->getNumElements());
 
187
      }
 
188
    }
 
189
    Ty = cast<PointerType>(GV->getType())->getElementType();
 
190
    return ConstantInt::get(Type::getInt32Ty(P->getContext()), 1);
 
191
    //TODO: implement more tracking for globals
 
192
  }
 
193
 
 
194
  if (CallInst *CI = dyn_cast<CallInst>(V)) {
 
195
    CallSite CS(CI);
 
196
    Function *F = dyn_cast<Function>(CS.getCalledValue()->stripPointerCasts());
 
197
    if (F == reallocFunc) {
 
198
      Ty = Type::getInt8Ty(P->getContext());
 
199
      // realloc allocates arg1 bytes.
 
200
      return CS.getArgument(1);
 
201
    }
 
202
  }
 
203
 
 
204
  return 0;
 
205
}
 
206
 
 
207
// Calculates the number of elements of type Ty allocated for P.
 
208
const SCEV *PointerTracking::computeAllocationCountForType(Value *P,
 
209
                                                           const Type *Ty)
 
210
  const {
 
211
    const Type *elementTy;
 
212
    const SCEV *Count = computeAllocationCount(P, elementTy);
 
213
    if (isa<SCEVCouldNotCompute>(Count))
 
214
      return Count;
 
215
    if (elementTy == Ty)
 
216
      return Count;
 
217
 
 
218
    if (!TD) // need TargetData from this point forward
 
219
      return SE->getCouldNotCompute();
 
220
 
 
221
    uint64_t elementSize = TD->getTypeAllocSize(elementTy);
 
222
    uint64_t wantSize = TD->getTypeAllocSize(Ty);
 
223
    if (elementSize == wantSize)
 
224
      return Count;
 
225
    if (elementSize % wantSize) //fractional counts not possible
 
226
      return SE->getCouldNotCompute();
 
227
    return SE->getMulExpr(Count, SE->getConstant(Count->getType(),
 
228
                                                 elementSize/wantSize));
 
229
}
 
230
 
 
231
const SCEV *PointerTracking::getAllocationElementCount(Value *V) const {
 
232
  // We only deal with pointers.
 
233
  const PointerType *PTy = cast<PointerType>(V->getType());
 
234
  return computeAllocationCountForType(V, PTy->getElementType());
 
235
}
 
236
 
 
237
const SCEV *PointerTracking::getAllocationSizeInBytes(Value *V) const {
 
238
  return computeAllocationCountForType(V, Type::getInt8Ty(V->getContext()));
 
239
}
 
240
 
 
241
// Helper for isLoopGuardedBy that checks the swapped and inverted predicate too
 
242
enum SolverResult PointerTracking::isLoopGuardedBy(const Loop *L,
 
243
                                                   Predicate Pred,
 
244
                                                   const SCEV *A,
 
245
                                                   const SCEV *B) const {
 
246
  if (SE->isLoopEntryGuardedByCond(L, Pred, A, B))
 
247
    return AlwaysTrue;
 
248
  Pred = ICmpInst::getSwappedPredicate(Pred);
 
249
  if (SE->isLoopEntryGuardedByCond(L, Pred, B, A))
 
250
    return AlwaysTrue;
 
251
 
 
252
  Pred = ICmpInst::getInversePredicate(Pred);
 
253
  if (SE->isLoopEntryGuardedByCond(L, Pred, B, A))
 
254
    return AlwaysFalse;
 
255
  Pred = ICmpInst::getSwappedPredicate(Pred);
 
256
  if (SE->isLoopEntryGuardedByCond(L, Pred, A, B))
 
257
    return AlwaysTrue;
 
258
  return Unknown;
 
259
}
 
260
 
 
261
enum SolverResult PointerTracking::checkLimits(const SCEV *Offset,
 
262
                                               const SCEV *Limit,
 
263
                                               BasicBlock *BB)
 
264
{
 
265
  //FIXME: merge implementation
 
266
  return Unknown;
 
267
}
 
268
 
 
269
void PointerTracking::getPointerOffset(Value *Pointer, Value *&Base,
 
270
                                       const SCEV *&Limit,
 
271
                                       const SCEV *&Offset) const
 
272
{
 
273
    Pointer = Pointer->stripPointerCasts();
 
274
    Base = GetUnderlyingObject(Pointer, TD);
 
275
    Limit = getAllocationSizeInBytes(Base);
 
276
    if (isa<SCEVCouldNotCompute>(Limit)) {
 
277
      Base = 0;
 
278
      Offset = Limit;
 
279
      return;
 
280
    }
 
281
 
 
282
    Offset = SE->getMinusSCEV(SE->getSCEV(Pointer), SE->getSCEV(Base));
 
283
    if (isa<SCEVCouldNotCompute>(Offset)) {
 
284
      Base = 0;
 
285
      Limit = Offset;
 
286
    }
 
287
}
 
288
 
 
289
void PointerTracking::print(raw_ostream &OS, const Module* M) const {
 
290
  // Calling some PT methods may cause caches to be updated, however
 
291
  // this should be safe for the same reason its safe for SCEV.
 
292
  PointerTracking &PT = *const_cast<PointerTracking*>(this);
 
293
  for (inst_iterator I=inst_begin(*FF), E=inst_end(*FF); I != E; ++I) {
 
294
    if (!I->getType()->isPointerTy())
 
295
      continue;
 
296
    Value *Base;
 
297
    const SCEV *Limit, *Offset;
 
298
    getPointerOffset(&*I, Base, Limit, Offset);
 
299
    if (!Base)
 
300
      continue;
 
301
 
 
302
    if (Base == &*I) {
 
303
      const SCEV *S = getAllocationElementCount(Base);
 
304
      OS << *Base << " ==> " << *S << " elements, ";
 
305
      OS << *Limit << " bytes allocated\n";
 
306
      continue;
 
307
    }
 
308
    OS << &*I << " -- base: " << *Base;
 
309
    OS << " offset: " << *Offset;
 
310
 
 
311
    enum SolverResult res = PT.checkLimits(Offset, Limit, I->getParent());
 
312
    switch (res) {
 
313
    case AlwaysTrue:
 
314
      OS << " always safe\n";
 
315
      break;
 
316
    case AlwaysFalse:
 
317
      OS << " always unsafe\n";
 
318
      break;
 
319
    case Unknown:
 
320
      OS << " <<unknown>>\n";
 
321
      break;
 
322
    }
 
323
  }
 
324
}
 
325
#endif