1 //===-- MergeHandler.h --------------------------------------------*- C++ -*-===// 2 // 3 // The KLEE Symbolic Virtual Machine 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 10 /** 11 * @file MergeHandler.h 12 * @brief Implementation of the region based merging 13 * 14 * ## Basic usage: 15 * 16 * @code{.cpp} 17 * klee_open_merge(); 18 * 19 * code containing branches etc. 20 * 21 * klee_close_merge(); 22 * @endcode 23 * 24 * Will lead to all states that forked from the state that executed the 25 * klee_open_merge() being merged in the klee_close_merge(). This allows for 26 * fine-grained regions to be specified for merging. 27 * 28 * # Implementation Structure 29 * 30 * The main part of the new functionality is implemented in the class 31 * klee::MergeHandler. The Special Function Handler generates an instance of 32 * this class every time a state runs into a klee_open_merge() call. 33 * 34 * This instance is appended to a `std::vector<klee::ref<klee::MergeHandler>>` 35 * in the ExecutionState that passed the merge open point. This stack is also 36 * copied during forks. We use a stack instead of a single instance to support 37 * nested merge regions. 38 * 39 * Once a state runs into a `klee_close_merge()`, the Special Function Handler 40 * notifies the top klee::MergeHandler in the state's stack, pauses the state 41 * from scheduling, and tries to merge it with all other states that already 42 * arrived at the same close merge point. This top instance is then popped from 43 * the stack, resulting in a decrease of the ref count of the 44 * klee::MergeHandler. 45 * 46 * Since the only references to this MergeHandler are in the stacks of 47 * the ExecutionStates currently in the merging region, once the ref count 48 * reaches zero, every state which ran into the same `klee_open_merge()` is now 49 * paused and waiting to be merged. The destructor of the MergeHandler 50 * then continues the scheduling of the corresponding paused states. 51 * 52 * # Non-blocking State Merging 53 * 54 * This feature adds functionality to the BoundedMergingSearcher that will 55 * prioritize (e.g., immediately schedule) states running inside a bounded-merge 56 * region once a state has reached a corresponding klee_close_merge() call. The 57 * goal is to quickly gather all states inside the merging region in order to 58 * release the waiting states. However, states that are running for more than 59 * twice the mean number of instructions compared to the states that are already 60 * waiting, will not be prioritized anymore. 61 * 62 * Once no more states are available for prioritizing, but there are states 63 * waiting to be released, these states (which have already been merged as good as 64 * possible) will be continued without waiting for the remaining states. When a 65 * remaining state now enters a close-merge point, it will again wait for the 66 * other states, or until the 'timeout' is reached. 67 */ 68 69 #ifndef KLEE_MERGEHANDLER_H 70 #define KLEE_MERGEHANDLER_H 71 72 #include "klee/ADT/Ref.h" 73 74 #include "llvm/Support/CommandLine.h" 75 76 #include <map> 77 #include <stdint.h> 78 #include <vector> 79 80 namespace llvm { 81 class Instruction; 82 } 83 84 namespace klee { 85 extern llvm::cl::opt<bool> UseMerge; 86 87 extern llvm::cl::opt<bool> DebugLogMerge; 88 89 extern llvm::cl::opt<bool> DebugLogIncompleteMerge; 90 91 class Executor; 92 class ExecutionState; 93 94 /// @brief Represents one `klee_open_merge()` call. 95 /// Handles merging of states that branched from it 96 class MergeHandler { 97 private: 98 Executor *executor; 99 100 /// @brief The instruction count when the state ran into the klee_open_merge 101 uint64_t openInstruction; 102 103 /// @brief The average number of instructions between the open and close merge of each 104 /// state that has finished so far 105 double closedMean; 106 107 /// @brief Number of states that are tracked by this MergeHandler, that ran 108 /// into a relevant klee_close_merge 109 unsigned closedStateCount; 110 111 /// @brief Get distance of state from the openInstruction 112 unsigned getInstructionDistance(ExecutionState *es); 113 114 /// @brief States that ran through the klee_open_merge, but not yet into a 115 /// corresponding klee_close_merge 116 std::vector<ExecutionState *> openStates; 117 118 /// @brief Mapping the different 'klee_close_merge' calls to the states that ran into 119 /// them 120 std::map<llvm::Instruction *, std::vector<ExecutionState *> > 121 reachedCloseMerge; 122 123 public: 124 125 /// @brief Called when a state runs into a 'klee_close_merge()' call 126 void addClosedState(ExecutionState *es, llvm::Instruction *mp); 127 128 /// @brief Return state that should be prioritized to complete this merge 129 ExecutionState *getPrioritizeState(); 130 131 /// @brief Add state to the 'openStates' vector 132 void addOpenState(ExecutionState *es); 133 134 /// @brief Remove state from the 'openStates' vector 135 void removeOpenState(ExecutionState *es); 136 137 /// @brief True, if any states have run into 'klee_close_merge()' and have 138 /// not been released yet 139 bool hasMergedStates(); 140 141 /// @brief Immediately release the merged states that have run into a 142 /// 'klee_merge_close()' 143 void releaseStates(); 144 145 // Return the mean time it takes for a state to get from klee_open_merge to 146 // klee_close_merge 147 double getMean(); 148 149 /// @brief Required by klee::ref-managed objects 150 class ReferenceCounter _refCount; 151 152 MergeHandler(Executor *_executor, ExecutionState *es); 153 ~MergeHandler(); 154 }; 155 } 156 157 #endif /* KLEE_MERGEHANDLER_H */ 158