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