Predator  [unstable] git snapshot
symstate.hh
Go to the documentation of this file.
1 /*
2  * Copyright (C) 2009-2010 Kamil Dudka <kdudka@redhat.com>
3  *
4  * This file is part of predator.
5  *
6  * predator is free software: you can redistribute it and/or modify
7  * it under the terms of the GNU General Public License as published by
8  * the Free Software Foundation, either version 3 of the License, or
9  * any later version.
10  *
11  * predator is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14  * GNU General Public License for more details.
15  *
16  * You should have received a copy of the GNU General Public License
17  * along with predator. If not, see <http://www.gnu.org/licenses/>.
18  */
19 
20 #ifndef H_GUARD_SYM_STATE_H
21 #define H_GUARD_SYM_STATE_H
22 
23 /**
24  * @file symstate.hh
25  * @todo update dox
26  */
27 
28 #include <set>
29 #include <vector>
30 
31 #include "symheap.hh"
32 
33 namespace CodeStorage {
34  class Block;
35 }
36 
37 class SymState {
38  private:
39  typedef std::vector<SymHeap *> TList;
40 
41  public:
42  typedef TList::const_iterator const_iterator;
43  typedef TList::iterator iterator;
44 
45  public:
46  SymState() { }
47  virtual ~SymState();
48 
49  SymState(const SymState &);
50  SymState& operator=(const SymState &);
51 
52  virtual void clear();
53 
54  virtual void swap(SymState &other) {
55  heaps_.swap(other.heaps_);
56  }
57 
58  /**
59  * look for the given symbolic heap, return its index if found, -1
60  * otherwise
61  */
62  virtual int lookup(const SymHeap &heap) const = 0;
63 
64  /// insert given SymHeap object into the state
65  virtual bool insert(const SymHeap &sh, bool allowThreeWay = true);
66 
67  /// return count of object stored in the container
68  size_t size() const { return heaps_.size(); }
69 
70  /// return nth SymHeap object, 0 <= nth < size()
71  const SymHeap& operator[](int nth) const {
72  return *heaps_[nth];
73  }
74 
75  /// return STL-like iterator to go through the container
76  const_iterator begin() const { return heaps_.begin(); }
77 
78  /// return STL-like iterator to go through the container
79  const_iterator end() const { return heaps_.end(); }
80 
81  /// @copydoc begin() const
82  iterator begin() { return heaps_.begin(); }
83 
84  /// @copydoc begin() const
85  iterator end() { return heaps_.end(); }
86 
87  protected:
88  /// insert @b new SymHeap that @ must be guaranteed to be not yet in
89  virtual void insertNew(const SymHeap &sh);
90 
91  virtual void eraseExisting(int nth) {
92  delete heaps_[nth];
93  heaps_.erase(heaps_.begin() + nth);
94  }
95 
96  virtual void swapExisting(int nth, SymHeap &sh) {
97  SymHeap &existing = *heaps_.at(nth);
98  existing.swap(sh);
99  }
100 
101  virtual void rotateExisting(const int idxA, const int idxB);
102 
103  void updateTraceOf(const int idx, Trace::Node *tr);
104 
105  /// lookup/insert optimization in SymCallCache implementation
106  friend class PerFncCache;
107 
108  private:
110 };
111 
112 class SymHeapList: public SymState {
113  public:
115 
116  SymHeapList(const SymState &ref):
117  // safe to slice the base, as we have no data anyway
118  SymState(ref)
119  {
120  }
121 
123  // safe to slice the base, as we have no data anyway
124  *static_cast<SymState *>(this) = ref;
125 
126  return *this;
127  }
128 
129  virtual int lookup(const SymHeap &) const {
130  return /* not found */ -1;
131  }
132 };
133 
134 /**
135  * symbolic state represented as a union of SymHeap objects (aka disjuncts)
136  *
137  * During the symbolic execution (see SymExec) we keep such a state per each
138  * basic block of the function just being processed. The result of a
139  * symbolically executed function is then the SymState taken from the basic
140  * block containing CL_INSN_RET as soon as the fix-point calculation has
141  * terminated.
142  */
143 class SymHeapUnion: public SymState {
144  public:
145  virtual int lookup(const SymHeap &sh) const;
146 };
147 
149  public:
150  virtual bool insert(const SymHeap &sh, bool allowThreeWay = true);
151 
152  private:
153  void packState(unsigned idx, bool allowThreeWay);
154 };
155 
156 /**
157  * Extension of SymStateWithJoin, which distinguishes among already processed
158  * symbolic heaps and symbolic heaps scheduled for processing. Newly inserted
159  * symbolic heaps are always marked as scheduled. They can be marked as done
160  * later, using the setDone() method.
161  */
163  public:
165  cntPending_(0)
166  {
167  }
168 
169  /// import of SymState rewrites the base and invalidates all flags
171  static_cast<SymState &>(*this) = huni;
172  done_.clear();
173  done_.resize(huni.size(), false);
174  cntPending_ = huni.size();
175  return *this;
176  }
177 
178  virtual void clear() {
180  done_.clear();
181  cntPending_ = 0;
182  }
183 
184  /// @attention always reinitializes the markers
185  virtual void swap(SymState &);
186 
187  /// return count of heaps pending for execution
188  int cntPending() const {
189  return cntPending_;
190  }
191 
192  protected:
193  virtual void insertNew(const SymHeap &sh) {
195 
196  // schedule the just inserted SymHeap for processing
197  done_.push_back(false);
198  ++cntPending_;
199  }
200 
201  virtual void eraseExisting(int nth) {
203 
204  if (!done_[nth])
205  --cntPending_;
206 
207  done_.erase(done_.begin() + nth);
208  }
209 
210  virtual void swapExisting(int nth, SymHeap &sh) {
212 
213  if (!done_.at(nth))
214  return;
215 
216  // an already processed heap has been generalized, we need to
217  // schedule it for precessing once again
218  done_[nth] = false;
219  ++cntPending_;
220  }
221 
222  virtual void rotateExisting(const int idxA, const int idxB);
223 
224  friend class SymStateMap;
225 
226  public:
227  /// check if the nth symbolic heap has been already processed
228  bool isDone(int nth) const {
229  return done_.at(nth);
230  }
231 
232  /// mark the nth symbolic heap as processed
233  void setDone(int nth) {
234  if (!done_.at(nth))
235  --cntPending_;
236 
237  done_[nth] = true;
238  }
239 
240  private:
241  typedef std::vector<bool> TDone;
242 
245 };
246 
248  public:
250 
251  /// return count of heaps pending for execution in the specified blcok
252  virtual int cntPending(const CodeStorage::Block *) const = 0;
253 };
254 
255 /**
256  * higher-level container that maintains a SymStateMarked object per each basic
257  * block. It's used by SymExecEngine and PathTracer classes.
258  */
260  public:
261  typedef std::vector<const CodeStorage::Block *> TContBlock;
262 
263  SymStateMap();
264  virtual ~SymStateMap();
265 
266  /// state lookup, basically equal to std::map semantic
268 
269  /**
270  * managed insertion of the state that keeps track of the relation among
271  * source and destination basic blocks
272  * @param dst @b destination basic block (where the insertion occurs)
273  * @param sh an instance of symbolic heap that should be inserted
274  * @param allowThreeWay if true, three-way join is allowed
275  */
276  bool insert(const CodeStorage::Block *dst,
277  const SymHeap &sh,
278  const bool allowThreeWay = true
279  );
280 
281  /// true if the specified block has ever joined/entailed any given state
282  bool anyReuseHappened(const CodeStorage::Block *) const;
283 
284  virtual int cntPending(const CodeStorage::Block *) const;
285 
286  private:
287  /// object copying is @b not allowed
288  SymStateMap(const SymStateMap &);
289 
290  /// object copying is @b not allowed
292 
293  private:
294  struct Private;
295  Private *d;
296 };
297 
299  public:
300  virtual ~IStatsProvider() { }
301  virtual void printStats() const = 0;
302 };
303 
305  public:
306  typedef const CodeStorage::Block *TBlock;
307  typedef std::set<TBlock> TBlockSet;
308  typedef std::vector<TBlock> TBlockList;
309 
310  public:
313  ~BlockScheduler();
314 
315  const TBlockSet& todo() const;
316 
317  TBlockList done() const;
318 
319  unsigned cntWaiting() const;
320 
321  bool schedule(const TBlock bb);
322 
323  bool getNext(TBlock *dst);
324 
325  virtual void printStats() const;
326 
327  private:
328  // not implemented
330 
331  struct Private;
332  Private *d;
333 };
334 
335 #endif /* H_GUARD_SYM_STATE_H */