7 #include "concretepredicate.h"
10 #include "execution.h"
11 #include "newfuzzer.h"
13 /** @brief Constructor */
14 ModelHistory::ModelHistory() :
15 func_counter(1), /* function id starts with 1 */
20 /* The following are snapshot data structures */
21 write_history = new HashTable<void *, value_set_t *, uintptr_t, 4>();
22 loc_func_nodes_map = new HashTable<void *, SnapList<FuncNode *> *, uintptr_t, 0>();
23 loc_wr_func_nodes_map = new HashTable<void *, SnapList<FuncNode *> *, uintptr_t, 0>();
24 loc_waiting_writes_map = new HashTable<void *, SnapVector<ConcretePredicate *> *, uintptr_t, 0>();
25 thrd_waiting_write = new SnapVector<ConcretePredicate *>();
26 func_inst_act_maps = new HashTable<uint32_t, SnapVector<inst_act_map_t *> *, int, 0>();
29 void ModelHistory::enter_function(const uint32_t func_id, thread_id_t tid)
31 //model_print("thread %d entering func %d\n", tid, func_id);
32 ModelExecution * execution = model->get_execution();
33 uint id = id_to_int(tid);
34 SnapVector<func_id_list_t> * thrd_func_list = execution->get_thrd_func_list();
35 SnapVector< SnapList<action_list_t *> *> *
36 thrd_func_act_lists = execution->get_thrd_func_act_lists();
37 SnapVector<uint32_t> * thrd_last_entered_func = execution->get_thrd_last_entered_func();
39 if ( thrd_func_list->size() <= id ) {
40 uint oldsize = thrd_func_list->size();
41 thrd_func_list->resize( id + 1 );
42 thrd_func_act_lists->resize( id + 1 );
44 for (uint i = oldsize; i < id + 1; i++) {
45 // push 0 as a dummy function id to a void seg fault
46 new (&(*thrd_func_list)[i]) func_id_list_t();
47 (*thrd_func_list)[i].push_back(0);
49 (*thrd_func_act_lists)[i] = new SnapList<action_list_t *>();
50 thrd_last_entered_func->push_back(0);
54 SnapList<action_list_t *> * func_act_lists = (*thrd_func_act_lists)[id];
55 func_act_lists->push_back( new action_list_t() );
57 uint32_t last_entered_func_id = (*thrd_last_entered_func)[id];
58 (*thrd_last_entered_func)[id] = func_id;
59 (*thrd_func_list)[id].push_back(func_id);
61 if ( func_nodes.size() <= func_id )
62 resize_func_nodes( func_id + 1 );
64 FuncNode * func_node = func_nodes[func_id];
65 func_node->init_predicate_tree_position(tid);
66 func_node->init_inst_act_map(tid);
68 /* Add edges between FuncNodes */
69 if (last_entered_func_id != 0) {
70 FuncNode * last_func_node = func_nodes[last_entered_func_id];
71 last_func_node->add_out_edge(func_node);
75 /* @param func_id a non-zero value */
76 void ModelHistory::exit_function(const uint32_t func_id, thread_id_t tid)
78 ModelExecution * execution = model->get_execution();
79 uint32_t id = id_to_int(tid);
80 SnapVector<func_id_list_t> * thrd_func_list = execution->get_thrd_func_list();
81 SnapVector< SnapList<action_list_t *> *> *
82 thrd_func_act_lists = execution->get_thrd_func_act_lists();
84 SnapList<action_list_t *> * func_act_lists = (*thrd_func_act_lists)[id];
85 uint32_t last_func_id = (*thrd_func_list)[id].back();
87 if (last_func_id == func_id) {
88 FuncNode * func_node = func_nodes[func_id];
89 func_node->set_predicate_tree_position(tid, NULL);
90 func_node->reset_inst_act_map(tid);
92 action_list_t * curr_act_list = func_act_lists->back();
94 /* defer the processing of curr_act_list until the function has exits a few times
95 * (currently twice) so that more information can be gathered to infer nullity predicates.
97 func_node->incr_exit_count();
98 if (func_node->get_exit_count() >= 2) {
99 SnapList<action_list_t *> * action_list_buffer = func_node->get_action_list_buffer();
100 while (action_list_buffer->size() > 0) {
101 action_list_t * act_list = action_list_buffer->back();
102 action_list_buffer->pop_back();
103 func_node->update_tree(act_list);
106 func_node->update_tree(curr_act_list);
108 func_node->get_action_list_buffer()->push_front(curr_act_list);
110 (*thrd_func_list)[id].pop_back();
111 func_act_lists->pop_back();
113 model_print("trying to exit with a wrong function id\n");
114 model_print("--- last_func: %d, func_id: %d\n", last_func_id, func_id);
116 //model_print("thread %d exiting func %d\n", tid, func_id);
119 void ModelHistory::resize_func_nodes(uint32_t new_size)
121 uint32_t old_size = func_nodes.size();
123 if ( old_size < new_size )
124 func_nodes.resize(new_size);
126 for (uint32_t id = old_size; id < new_size; id++) {
127 const char * func_name = func_map_rev[id];
128 FuncNode * func_node = new FuncNode(this);
129 func_node->set_func_id(id);
130 func_node->set_func_name(func_name);
131 func_nodes[id] = func_node;
135 void ModelHistory::process_action(ModelAction *act, thread_id_t tid)
137 ModelExecution * execution = model->get_execution();
138 /* Return if thread i has not entered any function or has exited
139 from all functions */
140 SnapVector<func_id_list_t> * thrd_func_list = execution->get_thrd_func_list();
141 SnapVector< SnapList<action_list_t *> *> *
142 thrd_func_act_lists = execution->get_thrd_func_act_lists();
144 uint32_t id = id_to_int(tid);
145 if ( thrd_func_list->size() <= id )
148 /* Get the function id that thread i is currently in */
149 uint32_t func_id = (*thrd_func_list)[id].back();
150 SnapList<action_list_t *> * func_act_lists = (*thrd_func_act_lists)[id];
152 if (act->is_write()) {
153 void * location = act->get_location();
154 uint64_t value = act->get_write_value();
155 update_write_history(location, value);
157 /* Update FuncNodes that may read from this location */
158 SnapList<FuncNode *> * func_nodes = loc_func_nodes_map->get(location);
159 if (func_nodes != NULL) {
160 sllnode<FuncNode *> * it = func_nodes->begin();
161 for (; it != NULL; it = it->getNext()) {
162 FuncNode * func_node = it->getVal();
163 func_node->add_to_val_loc_map(value, location);
167 check_waiting_write(act);
170 /* The following does not care about actions without a position */
171 if (func_id == 0 || act->get_position() == NULL)
174 action_list_t * curr_act_list = func_act_lists->back();
175 ASSERT(curr_act_list != NULL);
177 if (skip_action(act, curr_act_list))
180 FuncNode * func_node = func_nodes[func_id];
182 /* Add to curr_inst_list */
183 curr_act_list->push_back(act);
184 func_node->add_inst(act);
186 if (act->is_read()) {
187 func_node->update_inst_act_map(tid, act);
189 // Update predicate tree position
190 Fuzzer * fuzzer = execution->getFuzzer();
191 Predicate * selected_branch = fuzzer->get_selected_child_branch(tid);
192 func_node->set_predicate_tree_position(tid, selected_branch);
196 /* Return the FuncNode given its func_id */
197 FuncNode * ModelHistory::get_func_node(uint32_t func_id)
202 // This node has not been added to func_nodes
203 if (func_nodes.size() <= func_id)
206 return func_nodes[func_id];
209 /* Return the current FuncNode when given a thread id */
210 FuncNode * ModelHistory::get_curr_func_node(thread_id_t tid)
212 int thread_id = id_to_int(tid);
213 SnapVector<func_id_list_t> * thrd_func_list = model->get_execution()->get_thrd_func_list();
214 uint32_t func_id = (*thrd_func_list)[thread_id].back();
217 return func_nodes[func_id];
223 void ModelHistory::update_write_history(void * location, uint64_t write_val)
225 value_set_t * write_set = write_history->get(location);
227 if (write_set == NULL) {
228 write_set = new value_set_t();
229 write_history->put(location, write_set);
232 write_set->add(write_val);
235 void ModelHistory::update_loc_func_nodes_map(void * location, FuncNode * node)
237 SnapList<FuncNode *> * func_node_list = loc_func_nodes_map->get(location);
238 if (func_node_list == NULL) {
239 func_node_list = new SnapList<FuncNode *>();
240 loc_func_nodes_map->put(location, func_node_list);
243 func_node_list->push_back(node);
246 void ModelHistory::update_loc_wr_func_nodes_map(void * location, FuncNode * node)
248 SnapList<FuncNode *> * func_node_list = loc_wr_func_nodes_map->get(location);
249 if (func_node_list == NULL) {
250 func_node_list = new SnapList<FuncNode *>();
251 loc_func_nodes_map->put(location, func_node_list);
254 func_node_list->push_back(node);
257 /* When a thread is paused by Fuzzer, keep track of the condition it is waiting for */
258 void ModelHistory::add_waiting_write(ConcretePredicate * concrete)
260 void * location = concrete->get_location();
261 SnapVector<ConcretePredicate *> * waiting_conditions = loc_waiting_writes_map->get(location);
262 if (waiting_conditions == NULL) {
263 waiting_conditions = new SnapVector<ConcretePredicate *>();
264 loc_waiting_writes_map->put(location, waiting_conditions);
267 /* waiting_conditions should not have duplications */
268 waiting_conditions->push_back(concrete);
270 int thread_id = id_to_int(concrete->get_tid());
271 if (thrd_waiting_write->size() <= (uint) thread_id) {
272 thrd_waiting_write->resize(thread_id + 1);
275 (*thrd_waiting_write)[thread_id] = concrete;
278 void ModelHistory::remove_waiting_write(thread_id_t tid)
280 ConcretePredicate * concrete = (*thrd_waiting_write)[ id_to_int(tid) ];
281 void * location = concrete->get_location();
282 SnapVector<ConcretePredicate *> * concrete_preds = loc_waiting_writes_map->get(location);
284 for (uint i = 0; i < concrete_preds->size(); i++) {
285 ConcretePredicate * current = (*concrete_preds)[i];
286 if (concrete == current) {
287 (*concrete_preds)[i] = concrete_preds->back();
288 concrete_preds->pop_back();
293 int thread_id = id_to_int( concrete->get_tid() );
294 (*thrd_waiting_write)[thread_id] = NULL;
298 /* Check if any other thread is waiting for this write action. If so, "notify" them */
299 void ModelHistory::check_waiting_write(ModelAction * write_act)
301 void * location = write_act->get_location();
302 uint64_t value = write_act->get_write_value();
303 SnapVector<ConcretePredicate *> * concrete_preds = loc_waiting_writes_map->get(location);
304 SnapVector<ConcretePredicate *> to_remove = SnapVector<ConcretePredicate *>();
305 if (concrete_preds == NULL)
309 while (index < concrete_preds->size()) {
310 ConcretePredicate * concrete_pred = (*concrete_preds)[index];
311 SnapVector<struct concrete_pred_expr> * concrete_exprs = concrete_pred->getExpressions();
312 bool satisfy_predicate = true;
313 /* Check if the written value satisfies every predicate expression */
314 for (uint i = 0; i < concrete_exprs->size(); i++) {
315 struct concrete_pred_expr concrete = (*concrete_exprs)[i];
317 switch (concrete.token) {
319 equality = (value == concrete.value);
322 equality = ((void*)value == NULL);
325 model_print("unknown predicate token");
329 if (equality != concrete.equality) {
330 satisfy_predicate = false;
335 if (satisfy_predicate) {
336 to_remove.push_back(concrete_pred);
342 for (uint i = 0; i < to_remove.size(); i++) {
343 ConcretePredicate * concrete_pred = to_remove[i];
345 /* Wake up threads */
346 thread_id_t tid = concrete_pred->get_tid();
347 Thread * thread = model->get_thread(tid);
349 model_print("** thread %d is woken up\n", thread->get_id());
350 model->get_execution()->getFuzzer()->notify_paused_thread(thread);
354 SnapVector<inst_act_map_t *> * ModelHistory::getThrdInstActMap(uint32_t func_id)
356 ASSERT(func_id != 0);
358 SnapVector<inst_act_map_t *> * maps = func_inst_act_maps->get(func_id);
360 maps = new SnapVector<inst_act_map_t *>();
361 func_inst_act_maps->put(func_id, maps);
367 bool ModelHistory::skip_action(ModelAction * act, SnapList<ModelAction *> * curr_act_list)
369 bool second_part_of_rmw = act->is_rmwc() || act->is_rmw();
370 modelclock_t curr_seq_number = act->get_seq_number();
372 /* Skip actions that are second part of a read modify write */
373 if (second_part_of_rmw)
376 /* Skip actions with the same sequence number */
377 if (curr_act_list->size() != 0) {
378 ModelAction * last_act = curr_act_list->back();
379 if (last_act->get_seq_number() == curr_seq_number)
383 /* Skip actions that are paused by fuzzer (sequence number is 0) */
384 if (curr_seq_number == 0)
390 /* Reallocate some snapshotted memories when new executions start */
391 void ModelHistory::set_new_exec_flag()
393 for (uint i = 1; i < func_nodes.size(); i++) {
394 FuncNode * func_node = func_nodes[i];
395 func_node->set_new_exec_flag();
399 void ModelHistory::dump_func_node_graph()
401 model_print("digraph func_node_graph {\n");
402 for (uint i = 1; i < func_nodes.size(); i++) {
403 FuncNode * node = func_nodes[i];
404 ModelList<FuncNode *> * out_edges = node->get_out_edges();
406 model_print("\"%p\" [label=\"%s\"]\n", node, node->get_func_name());
407 mllnode<FuncNode *> * it;
408 for (it = out_edges->begin(); it != NULL; it = it->getNext()) {
409 FuncNode * other = it->getVal();
410 model_print("\"%p\" -> \"%p\"\n", node, other);
416 void ModelHistory::print_func_node()
418 /* function id starts with 1 */
419 for (uint32_t i = 1; i < func_nodes.size(); i++) {
420 FuncNode * func_node = func_nodes[i];
422 func_inst_list_mt * entry_insts = func_node->get_entry_insts();
423 model_print("function %s has entry actions\n", func_node->get_func_name());
425 mllnode<FuncInst*>* it;
426 for (it = entry_insts->begin();it != NULL;it=it->getNext()) {
427 FuncInst *inst = it->getVal();
428 model_print("type: %d, at: %s\n", inst->get_type(), inst->get_position());