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 */
19 write_history(), // snapshot data structure
20 loc_func_nodes_map(), // shapshot data structure
21 loc_wr_func_nodes_map(), // shapshot data structure
22 thrd_last_entered_func(), // snapshot data structure
23 loc_waiting_writes_map(), // snapshot data structure
24 thrd_waiting_write() // snapshot data structure
27 void ModelHistory::enter_function(const uint32_t func_id, thread_id_t tid)
29 //model_print("thread %d entering func %d\n", tid, func_id);
30 uint id = id_to_int(tid);
31 SnapVector<func_id_list_t> * thrd_func_list = model->get_execution()->get_thrd_func_list();
32 SnapVector< SnapList<action_list_t *> *> *
33 thrd_func_act_lists = model->get_execution()->get_thrd_func_act_lists();
35 if ( thrd_func_list->size() <= id ) {
36 uint oldsize = thrd_func_list->size();
37 thrd_func_list->resize( id + 1 );
38 thrd_func_act_lists->resize( id + 1 );
40 for (uint i = oldsize; i < id + 1; i++) {
41 new (&(*thrd_func_list)[i]) func_id_list_t();
42 // push 0 as a dummy function id to a void seg fault
43 (*thrd_func_list)[i].push_back(0);
45 (*thrd_func_act_lists)[i] = new SnapList<action_list_t *>();
49 while ( thrd_last_entered_func.size() <= id ) {
50 thrd_last_entered_func.push_back(0); // 0 is a dummy function id
53 SnapList<action_list_t *> * func_act_lists = (*thrd_func_act_lists)[id];
54 func_act_lists->push_back( new action_list_t() );
56 uint32_t last_entered_func_id = thrd_last_entered_func[id];
57 thrd_last_entered_func[id] = func_id;
58 (*thrd_func_list)[id].push_back(func_id);
60 if ( func_nodes.size() <= func_id )
61 resize_func_nodes( func_id + 1 );
63 FuncNode * func_node = func_nodes[func_id];
64 func_node->init_predicate_tree_position(tid);
65 func_node->init_inst_act_map(tid);
67 /* Add edges between FuncNodes */
68 if (last_entered_func_id != 0) {
69 FuncNode * last_func_node = func_nodes[last_entered_func_id];
70 last_func_node->add_out_edge(func_node);
74 /* @param func_id a non-zero value */
75 void ModelHistory::exit_function(const uint32_t func_id, thread_id_t tid)
77 uint32_t id = id_to_int(tid);
78 SnapVector<func_id_list_t> * thrd_func_list = model->get_execution()->get_thrd_func_list();
79 SnapVector< SnapList<action_list_t *> *> *
80 thrd_func_act_lists = model->get_execution()->get_thrd_func_act_lists();
82 SnapList<action_list_t *> * func_act_lists = (*thrd_func_act_lists)[id];
83 uint32_t last_func_id = (*thrd_func_list)[id].back();
85 if (last_func_id == func_id) {
86 FuncNode * func_node = func_nodes[func_id];
87 func_node->set_predicate_tree_position(tid, NULL);
88 func_node->reset_inst_act_map(tid);
90 action_list_t * curr_act_list = func_act_lists->back();
92 /* defer the processing of curr_act_list until the function has exits a few times
93 * (currently twice) so that more information can be gathered to infer nullity predicates.
95 func_node->incr_exit_count();
96 if (func_node->get_exit_count() >= 2) {
97 SnapList<action_list_t *> * action_list_buffer = func_node->get_action_list_buffer();
98 while (action_list_buffer->size() > 0) {
99 action_list_t * act_list = action_list_buffer->back();
100 action_list_buffer->pop_back();
101 func_node->update_tree(act_list);
104 func_node->update_tree(curr_act_list);
106 func_node->get_action_list_buffer()->push_front(curr_act_list);
108 (*thrd_func_list)[id].pop_back();
109 func_act_lists->pop_back();
111 model_print("trying to exit with a wrong function id\n");
112 model_print("--- last_func: %d, func_id: %d\n", last_func_id, func_id);
114 //model_print("thread %d exiting func %d\n", tid, func_id);
117 void ModelHistory::resize_func_nodes(uint32_t new_size)
119 uint32_t old_size = func_nodes.size();
121 if ( old_size < new_size )
122 func_nodes.resize(new_size);
124 for (uint32_t id = old_size; id < new_size; id++) {
125 const char * func_name = func_map_rev[id];
126 FuncNode * func_node = new FuncNode(this);
127 func_node->set_func_id(id);
128 func_node->set_func_name(func_name);
129 func_nodes[id] = func_node;
133 void ModelHistory::process_action(ModelAction *act, thread_id_t tid)
135 /* return if thread i has not entered any function or has exited
136 from all functions */
137 SnapVector<func_id_list_t> * thrd_func_list = model->get_execution()->get_thrd_func_list();
138 SnapVector< SnapList<action_list_t *> *> *
139 thrd_func_act_lists = model->get_execution()->get_thrd_func_act_lists();
141 uint32_t id = id_to_int(tid);
142 if ( thrd_func_list->size() <= id )
145 /* get the function id that thread i is currently in */
146 uint32_t func_id = (*thrd_func_list)[id].back();
147 SnapList<action_list_t *> * func_act_lists = (*thrd_func_act_lists)[id];
149 if (act->is_write()) {
150 void * location = act->get_location();
151 uint64_t value = act->get_write_value();
152 update_write_history(location, value);
154 /* Update FuncNodes that may read from this location */
155 SnapList<FuncNode *> * func_nodes = loc_func_nodes_map.get(location);
156 if (func_nodes != NULL) {
157 sllnode<FuncNode *> * it = func_nodes->begin();
158 for (; it != NULL; it = it->getNext()) {
159 FuncNode * func_node = it->getVal();
160 func_node->add_to_val_loc_map(value, location);
164 check_waiting_write(act);
167 /* the following does not care about actions without a position */
168 if (func_id == 0 || act->get_position() == NULL)
171 bool second_part_of_rmw = act->is_rmwc() || act->is_rmw();
173 action_list_t * curr_act_list = func_act_lists->back();
174 ASSERT(curr_act_list != NULL);
176 modelclock_t curr_seq_number = act->get_seq_number();
177 /* Skip actions that are second part of a read modify write or actions with the same sequence number */
178 if (curr_act_list->size() != 0) {
179 ModelAction * last_act = curr_act_list->back();
180 if (second_part_of_rmw || last_act->get_seq_number() == curr_seq_number)
184 /* skip actions that are paused by fuzzer (sequence number is 0) */
185 if (curr_seq_number == 0)
188 FuncNode * func_node = func_nodes[func_id];
190 /* add to curr_inst_list */
191 curr_act_list->push_back(act);
192 func_node->add_inst(act);
194 if (act->is_read()) {
195 func_node->update_inst_act_map(tid, act);
197 // Update predicate tree position
198 Fuzzer * fuzzer = model->get_execution()->getFuzzer();
199 Predicate * selected_branch = fuzzer->get_selected_child_branch(tid);
200 func_node->set_predicate_tree_position(tid, selected_branch);
204 /* Return the FuncNode given its func_id */
205 FuncNode * ModelHistory::get_func_node(uint32_t func_id)
207 if (func_nodes.size() <= func_id) // this node has not been added to func_nodes
210 return func_nodes[func_id];
213 /* Return the current FuncNode when given a thread id */
214 FuncNode * ModelHistory::get_curr_func_node(thread_id_t tid)
216 int thread_id = id_to_int(tid);
217 SnapVector<func_id_list_t> * thrd_func_list = model->get_execution()->get_thrd_func_list();
218 uint32_t func_id = (*thrd_func_list)[thread_id].back();
219 FuncNode * func_node = func_nodes[func_id];
224 void ModelHistory::update_write_history(void * location, uint64_t write_val)
226 value_set_t * write_set = write_history.get(location);
228 if (write_set == NULL) {
229 write_set = new value_set_t();
230 write_history.put(location, write_set);
233 write_set->add(write_val);
236 void ModelHistory::update_loc_func_nodes_map(void * location, FuncNode * node)
238 SnapList<FuncNode *> * func_node_list = loc_func_nodes_map.get(location);
239 if (func_node_list == NULL) {
240 func_node_list = new SnapList<FuncNode *>();
241 loc_func_nodes_map.put(location, func_node_list);
244 func_node_list->push_back(node);
247 void ModelHistory::update_loc_wr_func_nodes_map(void * location, FuncNode * node)
249 SnapList<FuncNode *> * func_node_list = loc_wr_func_nodes_map.get(location);
250 if (func_node_list == NULL) {
251 func_node_list = new SnapList<FuncNode *>();
252 loc_func_nodes_map.put(location, func_node_list);
255 func_node_list->push_back(node);
258 /* When a thread is paused by Fuzzer, keep track of the condition it is waiting for */
259 void ModelHistory::add_waiting_write(ConcretePredicate * concrete)
261 void * location = concrete->get_location();
262 SnapVector<ConcretePredicate *> * waiting_conditions = loc_waiting_writes_map.get(location);
263 if (waiting_conditions == NULL) {
264 waiting_conditions = new SnapVector<ConcretePredicate *>();
265 loc_waiting_writes_map.put(location, waiting_conditions);
268 /* waiting_conditions should not have duplications */
269 waiting_conditions->push_back(concrete);
271 int thread_id = id_to_int(concrete->get_tid());
272 int oldsize = thrd_waiting_write.size();
274 if (oldsize <= thread_id) {
275 for (int i = oldsize; i < thread_id + 1; i++)
276 thrd_waiting_write.resize(thread_id + 1);
279 thrd_waiting_write[thread_id] = concrete;
282 void ModelHistory::remove_waiting_write(thread_id_t tid)
284 ConcretePredicate * concrete = thrd_waiting_write[ id_to_int(tid) ];
285 void * location = concrete->get_location();
286 SnapVector<ConcretePredicate *> * concrete_preds = loc_waiting_writes_map.get(location);
288 for (uint i = 0; i < concrete_preds->size(); i++) {
289 ConcretePredicate * current = (*concrete_preds)[i];
290 if (concrete == current) {
291 (*concrete_preds)[i] = concrete_preds->back();
292 concrete_preds->pop_back();
297 int thread_id = id_to_int( concrete->get_tid() );
298 thrd_waiting_write[thread_id] = NULL;
302 /* Check if any other thread is waiting for this write action. If so, wake them up */
303 void ModelHistory::check_waiting_write(ModelAction * write_act)
305 void * location = write_act->get_location();
306 uint64_t value = write_act->get_write_value();
307 SnapVector<ConcretePredicate *> * concrete_preds = loc_waiting_writes_map.get(location);
308 SnapVector<ConcretePredicate *> to_remove = SnapVector<ConcretePredicate *>();
309 if (concrete_preds == NULL)
313 while (index < concrete_preds->size()) {
314 ConcretePredicate * concrete_pred = (*concrete_preds)[index];
315 SnapVector<struct concrete_pred_expr> * concrete_exprs = concrete_pred->getExpressions();
316 bool satisfy_predicate = true;
317 /* Check if the written value satisfies every predicate expression */
318 for (uint i = 0; i < concrete_exprs->size(); i++) {
319 struct concrete_pred_expr concrete = (*concrete_exprs)[i];
321 switch (concrete.token) {
323 equality = (value == concrete.value);
326 equality = ((void*)value == NULL);
329 model_print("unknown predicate token");
333 if (equality != concrete.equality) {
334 satisfy_predicate = false;
339 if (satisfy_predicate) {
340 to_remove.push_back(concrete_pred);
346 for (uint i = 0; i < to_remove.size(); i++) {
347 ConcretePredicate * concrete_pred = to_remove[i];
349 /* Wake up threads */
350 thread_id_t tid = concrete_pred->get_tid();
351 Thread * thread = model->get_thread(tid);
353 model_print("** thread %d is woken up\n", thread->get_id());
354 model->get_execution()->getFuzzer()->notify_paused_thread(thread);
358 /* Reallocate some snapshotted memories when new executions start */
359 void ModelHistory::set_new_exec_flag()
361 for (uint i = 1; i < func_nodes.size(); i++) {
362 FuncNode * func_node = func_nodes[i];
363 func_node->set_new_exec_flag();
367 void ModelHistory::dump_func_node_graph()
369 model_print("digraph func_node_graph {\n");
370 for (uint i = 1; i < func_nodes.size(); i++) {
371 FuncNode * node = func_nodes[i];
372 ModelList<FuncNode *> * out_edges = node->get_out_edges();
374 model_print("\"%p\" [label=\"%s\"]\n", node, node->get_func_name());
375 mllnode<FuncNode *> * it;
376 for (it = out_edges->begin(); it != NULL; it = it->getNext()) {
377 FuncNode * other = it->getVal();
378 model_print("\"%p\" -> \"%p\"\n", node, other);
384 void ModelHistory::print_func_node()
386 /* function id starts with 1 */
387 for (uint32_t i = 1; i < func_nodes.size(); i++) {
388 FuncNode * func_node = func_nodes[i];
390 func_inst_list_mt * entry_insts = func_node->get_entry_insts();
391 model_print("function %s has entry actions\n", func_node->get_func_name());
393 mllnode<FuncInst*>* it;
394 for (it = entry_insts->begin();it != NULL;it=it->getNext()) {
395 FuncInst *inst = it->getVal();
396 model_print("type: %d, at: %s\n", inst->get_type(), inst->get_position());