/** @brief Constructor */
ModelExecution::ModelExecution(ModelChecker *m,
- struct model_params *params,
+ const struct model_params *params,
Scheduler *scheduler,
NodeStack *node_stack) :
model(m),
scheduler(scheduler),
action_trace(),
thread_map(2), /* We'll always need at least 2 threads */
- obj_map(new HashTable<const void *, action_list_t *, uintptr_t, 4>()),
+ obj_map(),
condvar_waiters_map(),
obj_thrd_map(),
promises(),
model_thread = new Thread(get_next_id());
add_thread(model_thread);
scheduler->register_engine(this);
+ node_stack->register_engine(this);
}
/** @brief Destructor */
for (unsigned int i = 0; i < get_num_threads(); i++)
delete get_thread(int_to_id(i));
- delete obj_map;
-
for (unsigned int i = 0; i < promises.size(); i++)
delete promises[i];
return blocking_threads;
}
+/**
+ * @brief Check if we are yield-blocked
+ *
+ * A program can be "yield-blocked" if all threads are ready to execute a
+ * yield.
+ *
+ * @return True if the program is yield-blocked; false otherwise
+ */
+bool ModelExecution::is_yieldblocked() const
+{
+ if (!params->yieldblock)
+ return false;
+
+ for (unsigned int i = 0; i < get_num_threads(); i++) {
+ thread_id_t tid = int_to_id(i);
+ Thread *t = get_thread(tid);
+ if (t->get_pending() && t->get_pending()->is_yield())
+ return true;
+ }
+ return false;
+}
+
/**
* Check if this is a complete execution. That is, have all thread completed
* execution (rather than exiting because sleep sets have forced a redundant
*/
bool ModelExecution::is_complete_execution() const
{
+ if (is_yieldblocked())
+ return false;
for (unsigned int i = 0; i < get_num_threads(); i++)
if (is_enabled(int_to_id(i)))
return false;
ModelAction * ModelExecution::get_last_conflict(ModelAction *act) const
{
switch (act->get_type()) {
- /* case ATOMIC_FENCE: fences don't directly cause backtracking */
+ case ATOMIC_FENCE:
+ /* Only seq-cst fences can (directly) cause backtracking */
+ if (!act->is_seqcst())
+ break;
case ATOMIC_READ:
case ATOMIC_WRITE:
case ATOMIC_RMW: {
ModelAction *ret = NULL;
/* linear search: from most recent to oldest */
- action_list_t *list = get_safe_ptr_action(obj_map, act->get_location());
+ action_list_t *list = obj_map.get(act->get_location());
action_list_t::reverse_iterator rit;
for (rit = list->rbegin(); rit != list->rend(); rit++) {
ModelAction *prev = *rit;
+ if (prev == act)
+ continue;
if (prev->could_synchronize_with(act)) {
ret = prev;
break;
case ATOMIC_LOCK:
case ATOMIC_TRYLOCK: {
/* linear search: from most recent to oldest */
- action_list_t *list = get_safe_ptr_action(obj_map, act->get_location());
+ action_list_t *list = obj_map.get(act->get_location());
action_list_t::reverse_iterator rit;
for (rit = list->rbegin(); rit != list->rend(); rit++) {
ModelAction *prev = *rit;
}
case ATOMIC_UNLOCK: {
/* linear search: from most recent to oldest */
- action_list_t *list = get_safe_ptr_action(obj_map, act->get_location());
+ action_list_t *list = obj_map.get(act->get_location());
action_list_t::reverse_iterator rit;
for (rit = list->rbegin(); rit != list->rend(); rit++) {
ModelAction *prev = *rit;
}
case ATOMIC_WAIT: {
/* linear search: from most recent to oldest */
- action_list_t *list = get_safe_ptr_action(obj_map, act->get_location());
+ action_list_t *list = obj_map.get(act->get_location());
action_list_t::reverse_iterator rit;
for (rit = list->rbegin(); rit != list->rend(); rit++) {
ModelAction *prev = *rit;
case ATOMIC_NOTIFY_ALL:
case ATOMIC_NOTIFY_ONE: {
/* linear search: from most recent to oldest */
- action_list_t *list = get_safe_ptr_action(obj_map, act->get_location());
+ action_list_t *list = obj_map.get(act->get_location());
action_list_t::reverse_iterator rit;
for (rit = list->rbegin(); rit != list->rend(); rit++) {
ModelAction *prev = *rit;
/**
* @brief Check whether a model action is enabled.
*
- * Checks whether a lock or join operation would be successful (i.e., is the
- * lock already locked, or is the joined thread already complete). If not, put
- * the action in a waiter list.
+ * Checks whether an operation would be successful (i.e., is a lock already
+ * locked, or is the joined thread already complete).
+ *
+ * For yield-blocking, yields are never enabled.
*
* @param curr is the ModelAction to check whether it is enabled.
* @return a bool that indicates whether the action is enabled.
thread_blocking_check_promises(blocking, get_thread(curr));
return false;
}
+ } else if (params->yieldblock && curr->is_yield()) {
+ return false;
}
return true;
*
* @param curr The current action to process
* @return The ModelAction that is actually executed; may be different than
- * curr; may be NULL, if the current action is not enabled to run
+ * curr
*/
ModelAction * ModelExecution::check_current_action(ModelAction *curr)
{
int tid = id_to_int(act->get_tid());
ModelAction *uninit = NULL;
int uninit_id = -1;
- action_list_t *list = get_safe_ptr_action(obj_map, act->get_location());
+ action_list_t *list = get_safe_ptr_action(&obj_map, act->get_location());
if (list->empty() && act->is_atomic_var()) {
uninit = get_uninitialized_action(act);
uninit_id = id_to_int(uninit->get_tid());
if (act->is_wait()) {
void *mutex_loc = (void *) act->get_value();
- get_safe_ptr_action(obj_map, mutex_loc)->push_back(act);
+ get_safe_ptr_action(&obj_map, mutex_loc)->push_back(act);
SnapVector<action_list_t> *vec = get_safe_ptr_vect_action(&obj_thrd_map, mutex_loc);
if (tid >= (int)vec->size())
ModelAction * ModelExecution::get_last_seq_cst_write(ModelAction *curr) const
{
void *location = curr->get_location();
- action_list_t *list = get_safe_ptr_action(obj_map, location);
+ action_list_t *list = obj_map.get(location);
/* Find: max({i in dom(S) | seq_cst(t_i) && isWrite(t_i) && samevar(t_i, t)}) */
action_list_t::reverse_iterator rit;
for (rit = list->rbegin(); (*rit) != curr; rit++)
ModelAction * ModelExecution::get_last_seq_cst_fence(thread_id_t tid, const ModelAction *before_fence) const
{
/* All fences should have location FENCE_LOCATION */
- action_list_t *list = get_safe_ptr_action(obj_map, FENCE_LOCATION);
+ action_list_t *list = obj_map.get(FENCE_LOCATION);
+
+ if (!list)
+ return NULL;
+
action_list_t::reverse_iterator rit = list->rbegin();
if (before_fence) {
ModelAction * ModelExecution::get_last_unlock(ModelAction *curr) const
{
void *location = curr->get_location();
- action_list_t *list = get_safe_ptr_action(obj_map, location);
+ action_list_t *list = obj_map.get(location);
/* Find: max({i in dom(S) | isUnlock(t_i) && samevar(t_i, t)}) */
action_list_t::reverse_iterator rit;
for (rit = list->rbegin(); rit != list->rend(); rit++)
mo_graph->dumpNodes(file);
ModelAction **thread_array = (ModelAction **)model_calloc(1, sizeof(ModelAction *) * get_num_threads());
- for (action_list_t::iterator it = action_trace.begin(); it != action_trace.end(); it++) {
+ for (action_list_t::const_iterator it = action_trace.begin(); it != action_trace.end(); it++) {
ModelAction *act = *it;
if (act->is_read()) {
mo_graph->dot_print_node(file, act);
model_print("Execution %d:", get_execution_number());
if (isfeasibleprefix()) {
+ if (is_yieldblocked())
+ model_print(" YIELD BLOCKED");
if (scheduler->all_threads_sleeping())
model_print(" SLEEP-SET REDUNDANT");
model_print("\n");
{
while (!pending_rel_seqs.empty() &&
is_feasible_prefix_ignore_relseq() &&
- !unrealizedraces.empty()) {
+ haveUnrealizedRaces()) {
model_print("*** WARNING: release sequence fixup action "
"(%zu pending release seuqence(s)) ***\n",
pending_rel_seqs.size());
projects / model-checker.git / blobdiff