*~
*.dot
.*.d
+*.pdf
# files in this directory
/tags
# should be searched for input files as well. Possible values are YES and NO.
# If left blank NO is used.
-RECURSIVE = YES
+RECURSIVE = NO
# The EXCLUDE tag can be used to specify files and/or directories that should be
# excluded from the INPUT source files. This way you can easily exclude a
# Note that relative paths are relative to the directory from which doxygen is
# run.
-EXCLUDE = malloc.c doc/ benchmarks/ test/
+EXCLUDE = malloc.c
# The EXCLUDE_SYMLINKS tag can be used to select whether or not files or
# directories that are symbolic links (a Unix file system feature) are excluded
%.o: %.cc
$(CXX) -MMD -MF .$@.d -fPIC -c $< $(CPPFLAGS)
+%.pdf: %.dot
+ dot -Tpdf $< -o $@
+
-include $(OBJECTS:%=.%.d)
PHONY += clean
clean:
- rm -f *.o *.so .*.d
+ rm -f *.o *.so .*.d *.pdf *.dot
$(MAKE) -C $(TESTS_DIR) clean
PHONY += mrclean
fi
$(MAKE) -C $(BENCH_DIR)
+PHONY += pdfs
+pdfs: $(patsubst %.dot,%.pdf,$(wildcard *.dot))
+
.PHONY: $(PHONY)
location(loc),
value(value),
reads_from(NULL),
+ reads_from_promise(NULL),
last_fence_release(NULL),
node(NULL),
seq_number(ACTION_INITIAL_CLOCK),
void ModelAction::set_read_from(const ModelAction *act)
{
reads_from = act;
+ reads_from_promise = NULL;
if (act && act->is_uninitialized())
model->assert_bug("May read from uninitialized atomic\n");
}
+/**
+ * Set this action's read-from promise
+ * @param promise The promise to read from
+ */
+void ModelAction::set_read_from_promise(const Promise *promise)
+{
+ ASSERT(is_read());
+ reads_from_promise = promise;
+ reads_from = NULL;
+}
+
/**
* Synchronize the current thread with the thread corresponding to the
* ModelAction parameter.
}
uint64_t valuetoprint;
- if (type == ATOMIC_READ && reads_from != NULL)
+ if (is_read() && reads_from)
valuetoprint = reads_from->value;
+ else if (is_read() && reads_from_promise)
+ valuetoprint = reads_from_promise->get_value();
else
valuetoprint = value;
model_print("\n");
}
-/** @brief Print nicely-formatted info about this ModelAction */
+/** @brief Get a (likely) unique hash for this ModelAction */
unsigned int ModelAction::hash() const
{
unsigned int hash = (unsigned int)this->type;
class ClockVector;
class Thread;
+class Promise;
using std::memory_order;
using std::memory_order_relaxed;
modelclock_t get_seq_number() const { return seq_number; }
uint64_t get_value() const { return value; }
const ModelAction * get_reads_from() const { return reads_from; }
+ const Promise * get_reads_from_promise() const { return reads_from_promise; }
Node * get_node() const;
void set_node(Node *n) { node = n; }
void set_read_from(const ModelAction *act);
+ void set_read_from_promise(const Promise *promise);
/** Store the most recent fence-release from the same thread
* @param fence The fence-release that occured prior to this */
bool get_sleep_flag() { return sleep_flag; }
unsigned int hash() const;
+ bool equals(const ModelAction *x) const { return this == x; }
+ bool equals(const Promise *x) const { return false; }
MEMALLOC
private:
/** The action that this action reads from. Only valid for reads */
const ModelAction *reads_from;
+ /** The promise that this action reads from. Only valid for reads */
+ const Promise *reads_from_promise;
+
/** The last fence release from the same thread */
const ModelAction *last_fence_release;
CycleGraph::CycleGraph() :
discovered(new HashTable<const CycleNode *, const CycleNode *, uintptr_t, 4, model_malloc, model_calloc, model_free>(16)),
hasCycles(false),
- oldCycles(false),
- hasRMWViolation(false),
- oldRMWViolation(false)
+ oldCycles(false)
{
}
#endif
}
+/**
+ * Add a CycleNode to the graph, corresponding to a Promise
+ * @param promise The Promise that should be added
+ * @param node The CycleNode that corresponds to the Promise
+ */
+void CycleGraph::putNode(const Promise *promise, CycleNode *node)
+{
+ const ModelAction *reader = promise->get_action();
+ readerToPromiseNode.put(reader, node);
+#if SUPPORT_MOD_ORDER_DUMP
+ nodeList.push_back(node);
+#endif
+}
+
+/**
+ * @brief Remove the Promise node from the graph
+ * @param promise The promise to remove from the graph
+ */
+void CycleGraph::erasePromiseNode(const Promise *promise)
+{
+ const ModelAction *reader = promise->get_action();
+ readerToPromiseNode.put(reader, NULL);
+#if SUPPORT_MOD_ORDER_DUMP
+ /* Remove the promise node from nodeList */
+ CycleNode *node = getNode_noCreate(promise);
+ for (unsigned int i = 0; i < nodeList.size(); )
+ if (nodeList[i] == node)
+ nodeList.erase(nodeList.begin() + i);
+ else
+ i++;
+#endif
+}
+
+/** @return The corresponding CycleNode, if exists; otherwise NULL */
+CycleNode * CycleGraph::getNode_noCreate(const ModelAction *act) const
+{
+ return actionToNode.get(act);
+}
+
+/** @return The corresponding CycleNode, if exists; otherwise NULL */
+CycleNode * CycleGraph::getNode_noCreate(const Promise *promise) const
+{
+ return readerToPromiseNode.get(promise->get_action());
+}
+
/**
* @brief Returns the CycleNode corresponding to a given ModelAction
+ *
+ * Gets (or creates, if none exist) a CycleNode corresponding to a ModelAction
+ *
* @param action The ModelAction to find a node for
* @return The CycleNode paired with this action
*/
CycleNode * CycleGraph::getNode(const ModelAction *action)
{
- CycleNode *node = actionToNode.get(action);
+ CycleNode *node = getNode_noCreate(action);
if (node == NULL) {
node = new CycleNode(action);
putNode(action, node);
}
/**
- * Adds an edge between two ModelActions. The ModelAction @a to is ordered
- * after the ModelAction @a from.
- * @param to The edge points to this ModelAction
- * @param from The edge comes from this ModelAction
+ * @brief Returns a CycleNode corresponding to a promise
+ *
+ * Gets (or creates, if none exist) a CycleNode corresponding to a promised
+ * value.
+ *
+ * @param promise The Promise generated by a reader
+ * @return The CycleNode corresponding to the Promise
*/
-void CycleGraph::addEdge(const ModelAction *from, const ModelAction *to)
+CycleNode * CycleGraph::getNode(const Promise *promise)
{
- ASSERT(from);
- ASSERT(to);
+ CycleNode *node = getNode_noCreate(promise);
+ if (node == NULL) {
+ node = new CycleNode(promise);
+ putNode(promise, node);
+ }
+ return node;
+}
- CycleNode *fromnode = getNode(from);
- CycleNode *tonode = getNode(to);
+/**
+ * @return false if the resolution results in a cycle; true otherwise
+ */
+bool CycleGraph::resolvePromise(ModelAction *reader, ModelAction *writer,
+ promise_list_t *mustResolve)
+{
+ CycleNode *promise_node = readerToPromiseNode.get(reader);
+ CycleNode *w_node = actionToNode.get(writer);
+ ASSERT(promise_node);
+
+ if (w_node)
+ return mergeNodes(w_node, promise_node, mustResolve);
+ /* No existing write-node; just convert the promise-node */
+ promise_node->resolvePromise(writer);
+ erasePromiseNode(promise_node->getPromise());
+ putNode(writer, promise_node);
+ return true;
+}
+
+/**
+ * @brief Merge two CycleNodes that represent the same write
+ *
+ * Note that this operation cannot be rolled back.
+ *
+ * @param w_node The write ModelAction node with which to merge
+ * @param p_node The Promise node to merge. Will be destroyed after this
+ * function.
+ * @param mustMerge Return (pass-by-reference) any additional Promises that
+ * must also be merged with w_node
+ *
+ * @return false if the merge results in a cycle; true otherwise
+ */
+bool CycleGraph::mergeNodes(CycleNode *w_node, CycleNode *p_node,
+ promise_list_t *mustMerge)
+{
+ ASSERT(!w_node->is_promise());
+ ASSERT(p_node->is_promise());
+
+ const Promise *promise = p_node->getPromise();
+ if (!promise->is_compatible(w_node->getAction())) {
+ hasCycles = true;
+ return false;
+ }
+
+ /* Transfer the RMW */
+ CycleNode *promise_rmw = p_node->getRMW();
+ if (promise_rmw && promise_rmw != w_node->getRMW() && w_node->setRMW(promise_rmw)) {
+ hasCycles = true;
+ return false;
+ }
+
+ /* Transfer back edges to w_node */
+ while (p_node->getNumBackEdges() > 0) {
+ CycleNode *back = p_node->removeBackEdge();
+ if (back == w_node)
+ continue;
+ if (back->is_promise()) {
+ if (checkReachable(w_node, back)) {
+ /* Edge would create cycle; merge instead */
+ mustMerge->push_back(back->getPromise());
+ if (!mergeNodes(w_node, back, mustMerge))
+ return false;
+ } else
+ back->addEdge(w_node);
+ } else
+ addNodeEdge(back, w_node);
+ }
+
+ /* Transfer forward edges to w_node */
+ while (p_node->getNumEdges() > 0) {
+ CycleNode *forward = p_node->removeEdge();
+ if (forward == w_node)
+ continue;
+ if (forward->is_promise()) {
+ if (checkReachable(forward, w_node)) {
+ mustMerge->push_back(forward->getPromise());
+ if (!mergeNodes(w_node, forward, mustMerge))
+ return false;
+ } else
+ w_node->addEdge(forward);
+ } else
+ addNodeEdge(w_node, forward);
+ }
+
+ erasePromiseNode(promise);
+ /* Not deleting p_node, to maintain consistency if mergeNodes() fails */
+
+ return !hasCycles;
+}
+
+/**
+ * Adds an edge between two CycleNodes.
+ * @param fromnode The edge comes from this CycleNode
+ * @param tonode The edge points to this CycleNode
+ * @return True, if new edge(s) are added; otherwise false
+ */
+bool CycleGraph::addNodeEdge(CycleNode *fromnode, CycleNode *tonode)
+{
+ bool added;
if (!hasCycles)
hasCycles = checkReachable(tonode, fromnode);
- if (fromnode->addEdge(tonode))
+ if ((added = fromnode->addEdge(tonode)))
rollbackvector.push_back(fromnode);
-
- CycleNode *rmwnode = fromnode->getRMW();
-
/*
* If the fromnode has a rmwnode that is not the tonode, we should add
* an edge between its rmwnode and the tonode
- *
- * If tonode is also a rmw, don't do this check as the execution is
- * doomed and we'll catch the problem elsewhere, but we want to allow
- * for the possibility of sending to's write value to rmwnode
*/
- if (rmwnode != NULL && !to->is_rmw()) {
+ CycleNode *rmwnode = fromnode->getRMW();
+ if (rmwnode && rmwnode != tonode) {
if (!hasCycles)
hasCycles = checkReachable(tonode, rmwnode);
- if (rmwnode->addEdge(tonode))
+ if (rmwnode->addEdge(tonode)) {
rollbackvector.push_back(rmwnode);
+ added = true;
+ }
}
+ return added;
}
-/** Handles special case of a RMW action. The ModelAction rmw reads
- * from the ModelAction from. The key differences are: (1) no write
- * can occur in between the rmw and the from action. Only one RMW
- * action can read from a given write.
+/**
+ * @brief Add an edge between a write and the RMW which reads from it
+ *
+ * Handles special case of a RMW action, where the ModelAction rmw reads from
+ * the ModelAction/Promise from. The key differences are:
+ * (1) no write can occur in between the rmw and the from action.
+ * (2) Only one RMW action can read from a given write.
+ *
+ * @param from The edge comes from this ModelAction/Promise
+ * @param rmw The edge points to this ModelAction; this action must read from
+ * the ModelAction/Promise from
*/
-void CycleGraph::addRMWEdge(const ModelAction *from, const ModelAction *rmw)
+template <typename T>
+void CycleGraph::addRMWEdge(const T *from, const ModelAction *rmw)
{
ASSERT(from);
ASSERT(rmw);
CycleNode *rmwnode = getNode(rmw);
/* Two RMW actions cannot read from the same write. */
- if (fromnode->setRMW(rmwnode)) {
- hasRMWViolation = true;
- } else {
+ if (fromnode->setRMW(rmwnode))
+ hasCycles = true;
+ else
rmwrollbackvector.push_back(fromnode);
- }
/* Transfer all outgoing edges from the from node to the rmw node */
/* This process should not add a cycle because either:
}
}
- if (!hasCycles)
- hasCycles = checkReachable(rmwnode, fromnode);
+ addNodeEdge(fromnode, rmwnode);
+}
+/* Instantiate two forms of CycleGraph::addRMWEdge */
+template void CycleGraph::addRMWEdge(const ModelAction *from, const ModelAction *rmw);
+template void CycleGraph::addRMWEdge(const Promise *from, const ModelAction *rmw);
- if (fromnode->addEdge(rmwnode))
- rollbackvector.push_back(fromnode);
+/**
+ * @brief Adds an edge between objects
+ *
+ * This function will add an edge between any two objects which can be
+ * associated with a CycleNode. That is, if they have a CycleGraph::getNode
+ * implementation.
+ *
+ * The object to is ordered after the object from.
+ *
+ * @param to The edge points to this object, of type T
+ * @param from The edge comes from this object, of type U
+ * @return True, if new edge(s) are added; otherwise false
+ */
+template <typename T, typename U>
+bool CycleGraph::addEdge(const T *from, const U *to)
+{
+ ASSERT(from);
+ ASSERT(to);
+
+ CycleNode *fromnode = getNode(from);
+ CycleNode *tonode = getNode(to);
+
+ return addNodeEdge(fromnode, tonode);
}
+/* Instantiate four forms of CycleGraph::addEdge */
+template bool CycleGraph::addEdge(const ModelAction *from, const ModelAction *to);
+template bool CycleGraph::addEdge(const ModelAction *from, const Promise *to);
+template bool CycleGraph::addEdge(const Promise *from, const ModelAction *to);
+template bool CycleGraph::addEdge(const Promise *from, const Promise *to);
#if SUPPORT_MOD_ORDER_DUMP
+
+static void print_node(const CycleNode *node, FILE *file, int label)
+{
+ modelclock_t idx;
+ if (node->is_promise()) {
+ const Promise *promise = node->getPromise();
+ idx = promise->get_action()->get_seq_number();
+ fprintf(file, "P%u", idx);
+ if (label) {
+ int first = 1;
+ fprintf(file, " [label=\"P%u, T", idx);
+ for (unsigned int i = 0 ; i < model->get_num_threads(); i++)
+ if (promise->thread_is_available(int_to_id(i))) {
+ fprintf(file, "%s%u", first ? "": ",", i);
+ first = 0;
+ }
+ fprintf(file, "\"]");
+ }
+ } else {
+ const ModelAction *act = node->getAction();
+ idx = act->get_seq_number();
+ fprintf(file, "N%u", idx);
+ if (label)
+ fprintf(file, " [label=\"N%u, T%u\"]", idx, act->get_tid());
+ }
+}
+
void CycleGraph::dumpNodes(FILE *file) const
{
for (unsigned int i = 0; i < nodeList.size(); i++) {
- CycleNode *cn = nodeList[i];
- const ModelAction *action = cn->getAction();
- fprintf(file, "N%u [label=\"%u, T%u\"];\n", action->get_seq_number(), action->get_seq_number(), action->get_tid());
- if (cn->getRMW() != NULL) {
- fprintf(file, "N%u -> N%u[style=dotted];\n", action->get_seq_number(), cn->getRMW()->getAction()->get_seq_number());
+ CycleNode *n = nodeList[i];
+ print_node(n, file, 1);
+ fprintf(file, ";\n");
+ if (n->getRMW() != NULL) {
+ print_node(n, file, 0);
+ fprintf(file, " -> ");
+ print_node(n->getRMW(), file, 0);
+ fprintf(file, "[style=dotted];\n");
}
- for (unsigned int j = 0; j < cn->getNumEdges(); j++) {
- CycleNode *dst = cn->getEdge(j);
- const ModelAction *dstaction = dst->getAction();
- fprintf(file, "N%u -> N%u;\n", action->get_seq_number(), dstaction->get_seq_number());
+ for (unsigned int j = 0; j < n->getNumEdges(); j++) {
+ print_node(n, file, 0);
+ fprintf(file, " -> ");
+ print_node(n->getEdge(j), file, 0);
+ fprintf(file, ";\n");
}
}
}
}
#endif
-/**
- * Checks whether one ModelAction can reach another.
- * @param from The ModelAction from which to begin exploration
- * @param to The ModelAction to reach
- * @return True, @a from can reach @a to; otherwise, false
- */
-bool CycleGraph::checkReachable(const ModelAction *from, const ModelAction *to) const
-{
- CycleNode *fromnode = actionToNode.get(from);
- CycleNode *tonode = actionToNode.get(to);
-
- if (!fromnode || !tonode)
- return false;
-
- return checkReachable(fromnode, tonode);
-}
-
/**
* Checks whether one CycleNode can reach another.
* @param from The CycleNode from which to begin exploration
return false;
}
+/**
+ * Checks whether one ModelAction/Promise can reach another ModelAction/Promise
+ * @param from The ModelAction or Promise from which to begin exploration
+ * @param to The ModelAction or Promise to reach
+ * @return True, @a from can reach @a to; otherwise, false
+ */
+template <typename T, typename U>
+bool CycleGraph::checkReachable(const T *from, const U *to) const
+{
+ CycleNode *fromnode = getNode_noCreate(from);
+ CycleNode *tonode = getNode_noCreate(to);
+
+ if (!fromnode || !tonode)
+ return false;
+
+ return checkReachable(fromnode, tonode);
+}
+/* Instantiate three forms of CycleGraph::checkReachable */
+template bool CycleGraph::checkReachable(const ModelAction *from,
+ const ModelAction *to) const;
+template bool CycleGraph::checkReachable(const ModelAction *from,
+ const Promise *to) const;
+template bool CycleGraph::checkReachable(const Promise *from,
+ const ModelAction *to) const;
+
+/** @return True, if the promise has failed; false otherwise */
bool CycleGraph::checkPromise(const ModelAction *fromact, Promise *promise) const
{
std::vector< CycleNode *, ModelAlloc<CycleNode *> > queue;
CycleNode *node = queue.back();
queue.pop_back();
- if (promise->increment_threads(node->getAction()->get_tid())) {
+ if (node->getPromise() == promise)
+ return true;
+ if (!node->is_promise() &&
+ promise->eliminate_thread(node->getAction()->get_tid()))
return true;
- }
for (unsigned int i = 0; i < node->getNumEdges(); i++) {
CycleNode *next = node->getEdge(i);
void CycleGraph::startChanges()
{
- ASSERT(rollbackvector.size() == 0);
- ASSERT(rmwrollbackvector.size() == 0);
+ ASSERT(rollbackvector.empty());
+ ASSERT(rmwrollbackvector.empty());
ASSERT(oldCycles == hasCycles);
- ASSERT(oldRMWViolation == hasRMWViolation);
}
/** Commit changes to the cyclegraph. */
void CycleGraph::commitChanges()
{
- rollbackvector.resize(0);
- rmwrollbackvector.resize(0);
+ rollbackvector.clear();
+ rmwrollbackvector.clear();
oldCycles = hasCycles;
- oldRMWViolation = hasRMWViolation;
}
/** Rollback changes to the previous commit. */
void CycleGraph::rollbackChanges()
{
- for (unsigned int i = 0; i < rollbackvector.size(); i++) {
- rollbackvector[i]->popEdge();
- }
+ for (unsigned int i = 0; i < rollbackvector.size(); i++)
+ rollbackvector[i]->removeEdge();
- for (unsigned int i = 0; i < rmwrollbackvector.size(); i++) {
+ for (unsigned int i = 0; i < rmwrollbackvector.size(); i++)
rmwrollbackvector[i]->clearRMW();
- }
hasCycles = oldCycles;
- hasRMWViolation = oldRMWViolation;
- rollbackvector.resize(0);
- rmwrollbackvector.resize(0);
+ rollbackvector.clear();
+ rmwrollbackvector.clear();
}
/** @returns whether a CycleGraph contains cycles. */
return hasCycles;
}
-bool CycleGraph::checkForRMWViolation() const
-{
- return hasRMWViolation;
-}
-
/**
* @brief Constructor for a CycleNode
* @param act The ModelAction for this node
*/
CycleNode::CycleNode(const ModelAction *act) :
action(act),
+ promise(NULL),
+ hasRMW(NULL)
+{
+}
+
+/**
+ * @brief Constructor for a Promise CycleNode
+ * @param promise The Promise which was generated
+ */
+CycleNode::CycleNode(const Promise *promise) :
+ action(NULL),
+ promise(promise),
hasRMW(NULL)
{
}
return back_edges.size();
}
+/**
+ * @brief Remove an element from a vector
+ * @param v The vector
+ * @param n The element to remove
+ * @return True if the element was found; false otherwise
+ */
+template <typename T>
+static bool vector_remove_node(std::vector<T, SnapshotAlloc<T> >& v, const T n)
+{
+ for (unsigned int i = 0; i < v.size(); i++) {
+ if (v[i] == n) {
+ v.erase(v.begin() + i);
+ return true;
+ }
+ }
+ return false;
+}
+
+/**
+ * @brief Remove a (forward) edge from this CycleNode
+ * @return The CycleNode which was popped, if one exists; otherwise NULL
+ */
+CycleNode * CycleNode::removeEdge()
+{
+ if (edges.empty())
+ return NULL;
+
+ CycleNode *ret = edges.back();
+ edges.pop_back();
+ vector_remove_node(ret->back_edges, this);
+ return ret;
+}
+
+/**
+ * @brief Remove a (back) edge from this CycleNode
+ * @return The CycleNode which was popped, if one exists; otherwise NULL
+ */
+CycleNode * CycleNode::removeBackEdge()
+{
+ if (back_edges.empty())
+ return NULL;
+
+ CycleNode *ret = back_edges.back();
+ back_edges.pop_back();
+ vector_remove_node(ret->edges, this);
+ return ret;
+}
+
/**
* Adds an edge from this CycleNode to another CycleNode.
* @param node The node to which we add a directed edge
hasRMW = node;
return false;
}
+
+/**
+ * Convert a Promise CycleNode into a concrete-valued CycleNode. Should only be
+ * used when there's no existing ModelAction CycleNode for this write.
+ *
+ * @param writer The ModelAction which wrote the future value represented by
+ * this CycleNode
+ */
+void CycleNode::resolvePromise(const ModelAction *writer)
+{
+ ASSERT(is_promise());
+ ASSERT(promise->is_compatible(writer));
+ action = writer;
+ promise = NULL;
+ ASSERT(!is_promise());
+}
class CycleNode;
class ModelAction;
+typedef std::vector< const Promise *, ModelAlloc<const Promise *> > promise_list_t;
+
/** @brief A graph of Model Actions for tracking cycles. */
class CycleGraph {
public:
CycleGraph();
~CycleGraph();
- void addEdge(const ModelAction *from, const ModelAction *to);
+
+ template <typename T, typename U>
+ bool addEdge(const T *from, const U *to);
+
+ template <typename T>
+ void addRMWEdge(const T *from, const ModelAction *rmw);
+
bool checkForCycles() const;
- bool checkForRMWViolation() const;
- void addRMWEdge(const ModelAction *from, const ModelAction *rmw);
bool checkPromise(const ModelAction *from, Promise *p) const;
- bool checkReachable(const ModelAction *from, const ModelAction *to) const;
+
+ template <typename T, typename U>
+ bool checkReachable(const T *from, const U *to) const;
+
void startChanges();
void commitChanges();
void rollbackChanges();
void dumpGraphToFile(const char *filename) const;
#endif
+ bool resolvePromise(ModelAction *reader, ModelAction *writer,
+ promise_list_t *mustResolve);
+
SNAPSHOTALLOC
private:
+ bool addNodeEdge(CycleNode *fromnode, CycleNode *tonode);
void putNode(const ModelAction *act, CycleNode *node);
- CycleNode * getNode(const ModelAction *);
+ void putNode(const Promise *promise, CycleNode *node);
+ void erasePromiseNode(const Promise *promise);
+ CycleNode * getNode(const ModelAction *act);
+ CycleNode * getNode(const Promise *promise);
+ CycleNode * getNode_noCreate(const ModelAction *act) const;
+ CycleNode * getNode_noCreate(const Promise *promise) const;
+ bool mergeNodes(CycleNode *node1, CycleNode *node2,
+ promise_list_t *mustMerge);
+
HashTable<const CycleNode *, const CycleNode *, uintptr_t, 4, model_malloc, model_calloc, model_free> *discovered;
/** @brief A table for mapping ModelActions to CycleNodes */
HashTable<const ModelAction *, CycleNode *, uintptr_t, 4> actionToNode;
+ /** @brief A table for mapping reader ModelActions to Promise
+ * CycleNodes */
+ HashTable<const ModelAction *, CycleNode *, uintptr_t, 4> readerToPromiseNode;
+
#if SUPPORT_MOD_ORDER_DUMP
std::vector<CycleNode *> nodeList;
#endif
bool hasCycles;
bool oldCycles;
- bool hasRMWViolation;
- bool oldRMWViolation;
-
std::vector< CycleNode *, SnapshotAlloc<CycleNode *> > rollbackvector;
std::vector< CycleNode *, SnapshotAlloc<CycleNode *> > rmwrollbackvector;
};
-/** @brief A node within a CycleGraph; corresponds to one ModelAction */
+/**
+ * @brief A node within a CycleGraph; corresponds either to one ModelAction or
+ * to a promised future value
+ */
class CycleNode {
public:
CycleNode(const ModelAction *act);
+ CycleNode(const Promise *promise);
bool addEdge(CycleNode *node);
CycleNode * getEdge(unsigned int i) const;
unsigned int getNumEdges() const;
CycleNode * getBackEdge(unsigned int i) const;
unsigned int getNumBackEdges() const;
+ CycleNode * removeEdge();
+ CycleNode * removeBackEdge();
+
bool setRMW(CycleNode *);
CycleNode * getRMW() const;
+ void clearRMW() { hasRMW = NULL; }
const ModelAction * getAction() const { return action; }
-
- void popEdge() {
- edges.pop_back();
- }
- void clearRMW() {
- hasRMW = NULL;
- }
+ const Promise * getPromise() const { return promise; }
+ bool is_promise() const { return !action; }
+ void resolvePromise(const ModelAction *writer);
SNAPSHOTALLOC
private:
/** @brief The ModelAction that this node represents */
const ModelAction *action;
+ /** @brief The promise represented by this node; only valid when action
+ * is NULL */
+ const Promise *promise;
+
/** @brief The edges leading out from this node */
std::vector< CycleNode *, SnapshotAlloc<CycleNode *> > edges;
stats(),
failed_promise(false),
too_many_reads(false),
+ no_valid_reads(false),
bad_synchronization(false),
asserted(false)
{ }
struct execution_stats stats;
bool failed_promise;
bool too_many_reads;
+ bool no_valid_reads;
/** @brief Incorrectly-ordered synchronization was made */
bool bad_synchronization;
bool asserted;
Node *node = prev->get_node()->get_parent();
int low_tid, high_tid;
- if (node->is_enabled(t)) {
+ if (node->enabled_status(t->get_id()) == THREAD_ENABLED) {
low_tid = id_to_int(act->get_tid());
high_tid = low_tid + 1;
} else {
r_status = r_modification_order(curr, reads_from);
}
-
if (!second_part_of_rmw && is_infeasible() && (curr->get_node()->increment_read_from() || curr->get_node()->increment_future_value())) {
mo_graph->rollbackChanges();
priv->too_many_reads = false;
read_from(curr, reads_from);
mo_graph->commitChanges();
- mo_check_promises(curr->get_tid(), reads_from);
+ mo_check_promises(curr, true);
updated |= r_status;
} else if (!second_part_of_rmw) {
/* Read from future value */
- value = curr->get_node()->get_future_value();
- modelclock_t expiration = curr->get_node()->get_future_value_expiration();
- curr->set_read_from(NULL);
- Promise *valuepromise = new Promise(curr, value, expiration);
- promises->push_back(valuepromise);
+ struct future_value fv = curr->get_node()->get_future_value();
+ Promise *promise = new Promise(curr, fv);
+ value = fv.value;
+ curr->set_read_from_promise(promise);
+ promises->push_back(promise);
+ mo_graph->startChanges();
+ updated = r_modification_order(curr, promise);
+ mo_graph->commitChanges();
}
get_thread(curr)->set_return_value(value);
return updated;
void ModelChecker::add_future_value(const ModelAction *writer, ModelAction *reader)
{
/* Do more ambitious checks now that mo is more complete */
- if (mo_may_allow(writer, reader) &&
- reader->get_node()->add_future_value(writer->get_value(),
- writer->get_seq_number() + params.maxfuturedelay))
- set_latest_backtrack(reader);
+ if (mo_may_allow(writer, reader)) {
+ Node *node = reader->get_node();
+
+ /* Find an ancestor thread which exists at the time of the reader */
+ Thread *write_thread = get_thread(writer);
+ while (id_to_int(write_thread->get_id()) >= node->get_num_threads())
+ write_thread = write_thread->get_parent();
+
+ struct future_value fv = {
+ writer->get_value(),
+ writer->get_seq_number() + params.maxfuturedelay,
+ write_thread->get_id(),
+ };
+ if (node->add_future_value(fv))
+ set_latest_backtrack(reader);
+ }
}
/**
}
mo_graph->commitChanges();
- mo_check_promises(curr->get_tid(), curr);
+ mo_check_promises(curr, false);
get_thread(curr)->set_return_value(VALUE_NONE);
return updated_mod_order || updated_promises;
case THREAD_CREATE: {
Thread *th = curr->get_thread_operand();
th->set_creation(curr);
+ /* Promises can be satisfied by children */
+ for (unsigned int i = 0; i < promises->size(); i++) {
+ Promise *promise = (*promises)[i];
+ if (promise->thread_is_available(curr->get_tid()))
+ promise->add_thread(th->get_id());
+ }
break;
}
case THREAD_JOIN: {
scheduler->wake(get_thread(act));
}
th->complete();
+ /* Completed thread can't satisfy promises */
+ for (unsigned int i = 0; i < promises->size(); i++) {
+ Promise *promise = (*promises)[i];
+ if (promise->thread_is_available(th->get_id()))
+ if (promise->eliminate_thread(th->get_id()))
+ priv->failed_promise = true;
+ }
updated = true; /* trigger rel-seq checks */
break;
}
if (act->is_read()) {
const ModelAction *rf = act->get_reads_from();
- if (rf != NULL && r_modification_order(act, rf))
- updated = true;
+ const Promise *promise = act->get_reads_from_promise();
+ if (rf) {
+ if (r_modification_order(act, rf))
+ updated = true;
+ } else if (promise) {
+ if (r_modification_order(act, promise))
+ updated = true;
+ }
}
if (act->is_write()) {
if (w_modification_order(act))
{
char buf[100];
char *ptr = buf;
- if (mo_graph->checkForRMWViolation())
- ptr += sprintf(ptr, "[RMW atomicity]");
if (mo_graph->checkForCycles())
ptr += sprintf(ptr, "[mo cycle]");
if (priv->failed_promise)
ptr += sprintf(ptr, "[failed promise]");
if (priv->too_many_reads)
ptr += sprintf(ptr, "[too many reads]");
+ if (priv->no_valid_reads)
+ ptr += sprintf(ptr, "[no valid reads-from]");
if (priv->bad_synchronization)
ptr += sprintf(ptr, "[bad sw ordering]");
if (promises_expired())
*/
bool ModelChecker::is_infeasible() const
{
- return mo_graph->checkForRMWViolation() || is_infeasible_ignoreRMW();
-}
-
-/**
- * Check If the current partial trace is infeasible, while ignoring
- * infeasibility related to 2 RMW's reading from the same store. It does not
- * check end-of-execution feasibility.
- * @see ModelChecker::is_infeasible
- * @return whether the current partial trace is infeasible, ignoring multiple
- * RMWs reading from the same store.
- * */
-bool ModelChecker::is_infeasible_ignoreRMW() const
-{
- return mo_graph->checkForCycles() || priv->failed_promise ||
- priv->too_many_reads || priv->bad_synchronization ||
+ return mo_graph->checkForCycles() ||
+ priv->no_valid_reads ||
+ priv->failed_promise ||
+ priv->too_many_reads ||
+ priv->bad_synchronization ||
promises_expired();
}
ModelAction * ModelChecker::process_rmw(ModelAction *act) {
ModelAction *lastread = get_last_action(act->get_tid());
lastread->process_rmw(act);
- if (act->is_rmw() && lastread->get_reads_from() != NULL) {
- mo_graph->addRMWEdge(lastread->get_reads_from(), lastread);
+ if (act->is_rmw()) {
+ if (lastread->get_reads_from())
+ mo_graph->addRMWEdge(lastread->get_reads_from(), lastread);
+ else
+ mo_graph->addRMWEdge(lastread->get_reads_from_promise(), lastread);
mo_graph->commitChanges();
}
return lastread;
continue;
/* Test to see whether this is a feasible write to read from */
- mo_graph->startChanges();
- r_modification_order(curr, write);
- bool feasiblereadfrom = !is_infeasible();
- mo_graph->rollbackChanges();
+ /** NOTE: all members of read-from set should be
+ * feasible, so we no longer check it here **/
- if (!feasiblereadfrom)
- continue;
rit = ritcopy;
bool feasiblewrite = true;
* read.
*
* Basic idea is the following: Go through each other thread and find
- * the lastest action that happened before our read. Two cases:
+ * the last action that happened before our read. Two cases:
*
* (1) The action is a write => that write must either occur before
* the write we read from or be the write we read from.
* must occur before the write we read from or be the same write.
*
* @param curr The current action. Must be a read.
- * @param rf The action that curr reads from. Must be a write.
+ * @param rf The ModelAction or Promise that curr reads from. Must be a write.
* @return True if modification order edges were added; false otherwise
*/
-bool ModelChecker::r_modification_order(ModelAction *curr, const ModelAction *rf)
+template <typename rf_type>
+bool ModelChecker::r_modification_order(ModelAction *curr, const rf_type *rf)
{
std::vector<action_list_t> *thrd_lists = get_safe_ptr_vect_action(obj_thrd_map, curr->get_location());
unsigned int i;
for (rit = list->rbegin(); rit != list->rend(); rit++) {
ModelAction *act = *rit;
- if (act->is_write() && act != rf && act != curr) {
+ if (act->is_write() && !act->equals(rf) && act != curr) {
/* C++, Section 29.3 statement 5 */
if (curr->is_seqcst() && last_sc_fence_thread_local &&
*act < *last_sc_fence_thread_local) {
- mo_graph->addEdge(act, rf);
- added = true;
+ added = mo_graph->addEdge(act, rf) || added;
break;
}
/* C++, Section 29.3 statement 4 */
else if (act->is_seqcst() && last_sc_fence_local &&
*act < *last_sc_fence_local) {
- mo_graph->addEdge(act, rf);
- added = true;
+ added = mo_graph->addEdge(act, rf) || added;
break;
}
/* C++, Section 29.3 statement 6 */
else if (last_sc_fence_thread_before &&
*act < *last_sc_fence_thread_before) {
- mo_graph->addEdge(act, rf);
- added = true;
+ added = mo_graph->addEdge(act, rf) || added;
break;
}
}
*/
if (act->happens_before(curr) && act != curr) {
if (act->is_write()) {
- if (rf != act) {
- mo_graph->addEdge(act, rf);
- added = true;
+ if (!act->equals(rf)) {
+ added = mo_graph->addEdge(act, rf) || added;
}
} else {
const ModelAction *prevreadfrom = act->get_reads_from();
if (prevreadfrom == NULL)
continue;
- if (rf != prevreadfrom) {
- mo_graph->addEdge(prevreadfrom, rf);
- added = true;
+ if (!prevreadfrom->equals(rf)) {
+ added = mo_graph->addEdge(prevreadfrom, rf) || added;
}
}
break;
}
}
- return added;
-}
-
-/** This method fixes up the modification order when we resolve a
- * promises. The basic problem is that actions that occur after the
- * read curr could not property add items to the modification order
- * for our read.
- *
- * So for each thread, we find the earliest item that happens after
- * the read curr. This is the item we have to fix up with additional
- * constraints. If that action is write, we add a MO edge between
- * the Action rf and that action. If the action is a read, we add a
- * MO edge between the Action rf, and whatever the read accessed.
- *
- * @param curr is the read ModelAction that we are fixing up MO edges for.
- * @param rf is the write ModelAction that curr reads from.
- *
- */
-void ModelChecker::post_r_modification_order(ModelAction *curr, const ModelAction *rf)
-{
- std::vector<action_list_t> *thrd_lists = get_safe_ptr_vect_action(obj_thrd_map, curr->get_location());
- unsigned int i;
- ASSERT(curr->is_read());
-
- /* Iterate over all threads */
- for (i = 0; i < thrd_lists->size(); i++) {
- /* Iterate over actions in thread, starting from most recent */
- action_list_t *list = &(*thrd_lists)[i];
- action_list_t::reverse_iterator rit;
- ModelAction *lastact = NULL;
-
- /* Find last action that happens after curr that is either not curr or a rmw */
- for (rit = list->rbegin(); rit != list->rend(); rit++) {
- ModelAction *act = *rit;
- if (curr->happens_before(act) && (curr != act || curr->is_rmw())) {
- lastact = act;
- } else
- break;
- }
+ /*
+ * All compatible, thread-exclusive promises must be ordered after any
+ * concrete loads from the same thread
+ */
+ for (unsigned int i = 0; i < promises->size(); i++)
+ if ((*promises)[i]->is_compatible_exclusive(curr))
+ added = mo_graph->addEdge(rf, (*promises)[i]) || added;
- /* Include at most one act per-thread that "happens before" curr */
- if (lastact != NULL) {
- if (lastact == curr) {
- //Case 1: The resolved read is a RMW, and we need to make sure
- //that the write portion of the RMW mod order after rf
-
- mo_graph->addEdge(rf, lastact);
- } else if (lastact->is_read()) {
- //Case 2: The resolved read is a normal read and the next
- //operation is a read, and we need to make sure the value read
- //is mod ordered after rf
-
- const ModelAction *postreadfrom = lastact->get_reads_from();
- if (postreadfrom != NULL && rf != postreadfrom)
- mo_graph->addEdge(rf, postreadfrom);
- } else {
- //Case 3: The resolved read is a normal read and the next
- //operation is a write, and we need to make sure that the
- //write is mod ordered after rf
- if (lastact != rf)
- mo_graph->addEdge(rf, lastact);
- }
- break;
- }
- }
+ return added;
}
/**
so we are initialized. */
ModelAction *last_seq_cst = get_last_seq_cst_write(curr);
if (last_seq_cst != NULL) {
- mo_graph->addEdge(last_seq_cst, curr);
- added = true;
+ added = mo_graph->addEdge(last_seq_cst, curr) || added;
}
}
/* C++, Section 29.3 statement 7 */
if (last_sc_fence_thread_before && act->is_write() &&
*act < *last_sc_fence_thread_before) {
- mo_graph->addEdge(act, curr);
- added = true;
+ added = mo_graph->addEdge(act, curr) || added;
break;
}
* readfrom(act) --mo--> act
*/
if (act->is_write())
- mo_graph->addEdge(act, curr);
+ added = mo_graph->addEdge(act, curr) || added;
else if (act->is_read()) {
//if previous read accessed a null, just keep going
if (act->get_reads_from() == NULL)
continue;
- mo_graph->addEdge(act->get_reads_from(), curr);
+ added = mo_graph->addEdge(act->get_reads_from(), curr) || added;
}
- added = true;
break;
} else if (act->is_read() && !act->could_synchronize_with(curr) &&
!act->same_thread(curr)) {
*/
if (thin_air_constraint_may_allow(curr, act)) {
- if (!is_infeasible() ||
- (curr->is_rmw() && act->is_rmw() && curr->get_reads_from() == act->get_reads_from() && !is_infeasible_ignoreRMW())) {
+ if (!is_infeasible())
futurevalues->push_back(PendingFutureValue(curr, act));
- }
+ else if (curr->is_rmw() && act->is_rmw() && curr->get_reads_from() && curr->get_reads_from() == act->get_reads_from())
+ add_future_value(curr, act);
}
}
}
}
+ /*
+ * All compatible, thread-exclusive promises must be ordered after any
+ * concrete stores to the same thread, or else they can be merged with
+ * this store later
+ */
+ for (unsigned int i = 0; i < promises->size(); i++)
+ if ((*promises)[i]->is_compatible_exclusive(curr))
+ added = mo_graph->addEdge(curr, (*promises)[i]) || added;
+
return added;
}
*/
bool ModelChecker::resolve_promises(ModelAction *write)
{
- bool resolved = false;
- std::vector< thread_id_t, ModelAlloc<thread_id_t> > threads_to_check;
+ bool haveResolved = false;
+ std::vector< ModelAction *, ModelAlloc<ModelAction *> > actions_to_check;
+ promise_list_t mustResolve, resolved;
for (unsigned int i = 0, promise_index = 0; promise_index < promises->size(); i++) {
Promise *promise = (*promises)[promise_index];
if (write->get_node()->get_promise(i)) {
ModelAction *read = promise->get_action();
- if (read->is_rmw()) {
- mo_graph->addRMWEdge(write, read);
- }
read_from(read, write);
- //First fix up the modification order for actions that happened
- //before the read
- r_modification_order(read, write);
- //Next fix up the modification order for actions that happened
- //after the read.
- post_r_modification_order(read, write);
//Make sure the promise's value matches the write's value
- ASSERT(promise->get_value() == write->get_value());
- delete(promise);
+ ASSERT(promise->is_compatible(write));
+ mo_graph->resolvePromise(read, write, &mustResolve);
+ resolved.push_back(promise);
promises->erase(promises->begin() + promise_index);
- threads_to_check.push_back(read->get_tid());
+ actions_to_check.push_back(read);
- resolved = true;
+ haveResolved = true;
} else
promise_index++;
}
+ for (unsigned int i = 0; i < mustResolve.size(); i++) {
+ if (std::find(resolved.begin(), resolved.end(), mustResolve[i])
+ == resolved.end())
+ priv->failed_promise = true;
+ }
+ for (unsigned int i = 0; i < resolved.size(); i++)
+ delete resolved[i];
//Check whether reading these writes has made threads unable to
//resolve promises
- for (unsigned int i = 0; i < threads_to_check.size(); i++)
- mo_check_promises(threads_to_check[i], write);
+ for (unsigned int i = 0; i < actions_to_check.size(); i++) {
+ ModelAction *read = actions_to_check[i];
+ mo_check_promises(read, true);
+ }
- return resolved;
+ return haveResolved;
}
/**
const ModelAction *act = promise->get_action();
if ((old_cv == NULL || !old_cv->synchronized_since(act)) &&
merge_cv->synchronized_since(act)) {
- if (promise->increment_threads(tid)) {
+ if (promise->eliminate_thread(tid)) {
//Promise has failed
priv->failed_promise = true;
return;
}
}
-void ModelChecker::check_promises_thread_disabled() {
+void ModelChecker::check_promises_thread_disabled()
+{
for (unsigned int i = 0; i < promises->size(); i++) {
Promise *promise = (*promises)[i];
- if (promise->check_promise()) {
+ if (promise->has_failed()) {
priv->failed_promise = true;
return;
}
}
}
-/** Checks promises in response to addition to modification order for threads.
- * Definitions:
- * pthread is the thread that performed the read that created the promise
- *
- * pread is the read that created the promise
- *
- * pwrite is either the first write to same location as pread by
- * pthread that is sequenced after pread or the value read by the
- * first read to the same lcoation as pread by pthread that is
- * sequenced after pread..
- *
- * 1. If tid=pthread, then we check what other threads are reachable
- * through the mode order starting with pwrite. Those threads cannot
- * perform a write that will resolve the promise due to modification
- * order constraints.
- *
- * 2. If the tid is not pthread, we check whether pwrite can reach the
- * action write through the modification order. If so, that thread
- * cannot perform a future write that will resolve the promise due to
- * modificatin order constraints.
+/**
+ * @brief Checks promises in response to addition to modification order for
+ * threads.
*
- * @param tid The thread that either read from the model action
- * write, or actually did the model action write.
+ * We test whether threads are still available for satisfying promises after an
+ * addition to our modification order constraints. Those that are unavailable
+ * are "eliminated". Once all threads are eliminated from satisfying a promise,
+ * that promise has failed.
*
- * @param write The ModelAction representing the relevant write.
+ * @param act The ModelAction which updated the modification order
+ * @param is_read_check Should be true if act is a read and we must check for
+ * updates to the store from which it read (there is a distinction here for
+ * RMW's, which are both a load and a store)
*/
-void ModelChecker::mo_check_promises(thread_id_t tid, const ModelAction *write)
+void ModelChecker::mo_check_promises(const ModelAction *act, bool is_read_check)
{
- void *location = write->get_location();
+ const ModelAction *write = is_read_check ? act->get_reads_from() : act;
+
for (unsigned int i = 0; i < promises->size(); i++) {
Promise *promise = (*promises)[i];
- const ModelAction *act = promise->get_action();
+ const ModelAction *pread = promise->get_action();
- //Is this promise on the same location?
- if (act->get_location() != location)
+ // Is this promise on the same location?
+ if (!pread->same_var(write))
continue;
- //same thread as the promise
- if (act->get_tid() == tid) {
-
- //do we have a pwrite for the promise, if not, set it
- if (promise->get_write() == NULL) {
- promise->set_write(write);
- //The pwrite cannot happen before the promise
- if (write->happens_before(act) && (write != act)) {
- priv->failed_promise = true;
- return;
- }
- }
- if (mo_graph->checkPromise(write, promise)) {
- priv->failed_promise = true;
- return;
- }
+ if (pread->happens_before(act) && mo_graph->checkPromise(write, promise)) {
+ priv->failed_promise = true;
+ return;
}
- //Don't do any lookups twice for the same thread
- if (promise->has_sync_thread(tid))
+ // Don't do any lookups twice for the same thread
+ if (!promise->thread_is_available(act->get_tid()))
continue;
- if (promise->get_write() && mo_graph->checkReachable(promise->get_write(), write)) {
- if (promise->increment_threads(tid)) {
+ if (mo_graph->checkReachable(promise, write)) {
+ if (mo_graph->checkPromise(write, promise)) {
priv->failed_promise = true;
return;
}
else if (curr->get_sleep_flag() && !curr->is_seqcst() && !sleep_can_read_from(curr, act))
allow_read = false;
- if (allow_read)
- curr->get_node()->add_read_from(act);
+ if (allow_read) {
+ /* Only add feasible reads */
+ mo_graph->startChanges();
+ r_modification_order(curr, act);
+ if (!is_infeasible())
+ curr->get_node()->add_read_from(act);
+ mo_graph->rollbackChanges();
+ }
/* Include at most one act per-thread that "happens before" curr */
if (act->happens_before(curr))
break;
}
}
+ /* We may find no valid may-read-from only if the execution is doomed */
+ if (!curr->get_node()->get_read_from_size()) {
+ priv->no_valid_reads = true;
+ set_assert();
+ }
if (DBG_ENABLED()) {
model_print("Reached read action:\n");
for (action_list_t::iterator it = action_trace->begin(); it != action_trace->end(); it++) {
ModelAction *action = *it;
if (action->is_read()) {
- fprintf(file, "N%u [label=\"%u, T%u\"];\n", action->get_seq_number(), action->get_seq_number(), action->get_tid());
+ fprintf(file, "N%u [label=\"N%u, T%u\"];\n", action->get_seq_number(), action->get_seq_number(), action->get_tid());
if (action->get_reads_from() != NULL)
fprintf(file, "N%u -> N%u[label=\"rf\", color=red];\n", action->get_seq_number(), action->get_reads_from()->get_seq_number());
}
void ModelChecker::print_summary() const
{
#if SUPPORT_MOD_ORDER_DUMP
- scheduler->print();
char buffername[100];
sprintf(buffername, "exec%04u", stats.num_total);
mo_graph->dumpGraphToFile(buffername);
* @param act The ModelAction
* @return A Thread reference
*/
-Thread * ModelChecker::get_thread(ModelAction *act) const
+Thread * ModelChecker::get_thread(const ModelAction *act) const
{
return get_thread(act->get_tid());
}
void add_thread(Thread *t);
void remove_thread(Thread *t);
Thread * get_thread(thread_id_t tid) const;
- Thread * get_thread(ModelAction *act) const;
+ Thread * get_thread(const ModelAction *act) const;
bool is_enabled(Thread *t) const;
bool is_enabled(thread_id_t tid) const;
ClockVector * get_cv(thread_id_t tid) const;
ModelAction * get_parent_action(thread_id_t tid) const;
void check_promises_thread_disabled();
- void mo_check_promises(thread_id_t tid, const ModelAction *write);
+ void mo_check_promises(const ModelAction *act, bool is_read_check);
void check_promises(thread_id_t tid, ClockVector *old_cv, ClockVector *merge_cv);
bool isfeasibleprefix() const;
ModelAction * get_last_unlock(ModelAction *curr) const;
void build_reads_from_past(ModelAction *curr);
ModelAction * process_rmw(ModelAction *curr);
- void post_r_modification_order(ModelAction *curr, const ModelAction *rf);
- bool r_modification_order(ModelAction *curr, const ModelAction *rf);
+
+ template <typename rf_type>
+ bool r_modification_order(ModelAction *curr, const rf_type *rf);
+
bool w_modification_order(ModelAction *curr);
void get_release_seq_heads(ModelAction *acquire, ModelAction *read, rel_heads_list_t *release_heads);
bool release_seq_heads(const ModelAction *rf, rel_heads_list_t *release_heads, struct release_seq *pending) const;
void print_infeasibility(const char *prefix) const;
bool is_feasible_prefix_ignore_relseq() const;
- bool is_infeasible_ignoreRMW() const;
bool is_infeasible() const;
bool is_deadlocked() const;
bool is_complete_execution() const;
+#define __STDC_FORMAT_MACROS
+#include <inttypes.h>
+
#include <string.h>
#include "nodestack.h"
#include "common.h"
#include "model.h"
#include "threads-model.h"
+#include "modeltypes.h"
/**
* @brief Node constructor
}
/** Prints debugging info for the ModelAction associated with this Node */
-void Node::print()
+void Node::print() const
{
action->print();
- model_print(" backtrack: %s\n", backtrack_empty() ? "empty" : "non-empty");
- model_print(" future values: %s\n", future_value_empty() ? "empty" : "non-empty");
- model_print(" read-from: %s\n", read_from_empty() ? "empty" : "non-empty");
+ model_print(" backtrack: %s", backtrack_empty() ? "empty" : "non-empty ");
+ for (int i = 0; i < (int)backtrack.size(); i++)
+ if (backtrack[i] == true)
+ model_print("[%d]", i);
+ model_print("\n");
+ model_print(" future values: %s", future_value_empty() ? "empty" : "non-empty ");
+ for (int i = future_index + 1; i < (int)future_values.size(); i++)
+ model_print("[%#" PRIx64 "]", future_values[i].value);
+ model_print("\n");
+
+ model_print(" read-from: %s", read_from_empty() ? "empty" : "non-empty ");
+ for (int i = read_from_index + 1; i < (int)may_read_from.size(); i++)
+ model_print("[%d]", may_read_from[i]->get_seq_number());
+ model_print("\n");
+
model_print(" promises: %s\n", promise_empty() ? "empty" : "non-empty");
model_print(" misc: %s\n", misc_empty() ? "empty" : "non-empty");
model_print(" rel seq break: %s\n", relseq_break_empty() ? "empty" : "non-empty");
//sending our value to two rmws... not going to work..try next combination
continue;
}
- promises[i] = (promises[i] & PROMISE_RMW) |PROMISE_FULFILLED;
+ promises[i] = (promises[i] & PROMISE_RMW) | PROMISE_FULFILLED;
while (i > 0) {
i--;
if ((promises[i] & PROMISE_MASK) == PROMISE_FULFILLED)
for (int i = promises.size() - 1; i >= 0; i--) {
if (promises[i] == PROMISE_UNFULFILLED)
return false;
- if (!fulfilledrmw && ((promises[i]&PROMISE_MASK) == PROMISE_UNFULFILLED))
+ if (!fulfilledrmw && ((promises[i] & PROMISE_MASK) == PROMISE_UNFULFILLED))
return false;
- if (promises[i] == (PROMISE_FULFILLED|PROMISE_RMW))
+ if (promises[i] == (PROMISE_FULFILLED | PROMISE_RMW))
fulfilledrmw = true;
}
return true;
}
-
void Node::set_misc_max(int i)
{
misc_max = i;
return (misc_index + 1) >= misc_max;
}
-
/**
* Adds a value from a weakly ordered future write to backtrack to. This
* operation may "fail" if the future value has already been run (within some
* @param value is the value to backtrack to.
* @return True if the future value was successully added; false otherwise
*/
-bool Node::add_future_value(uint64_t value, modelclock_t expiration)
+bool Node::add_future_value(struct future_value& fv)
{
+ uint64_t value = fv.value;
+ modelclock_t expiration = fv.expiration;
+ thread_id_t tid = fv.tid;
int idx = -1; /* Highest index where value is found */
for (unsigned int i = 0; i < future_values.size(); i++) {
- if (future_values[i].value == value) {
+ if (future_values[i].value == value && future_values[i].tid == tid) {
if (expiration <= future_values[i].expiration)
return false;
idx = i;
(int)future_values.size() >= model->params.maxfuturevalues)
return false;
- struct future_value newfv = {value, expiration};
- future_values.push_back(newfv);
+ future_values.push_back(fv);
return true;
}
}
/**
- * Gets the next 'future_value' value from this Node. Only valid for a node
- * where this->action is a 'read'.
+ * Gets the next 'future_value' from this Node. Only valid for a node where
+ * this->action is a 'read'.
* @return The first element in future_values
*/
-uint64_t Node::get_future_value() const
+struct future_value Node::get_future_value() const
{
ASSERT(future_index >= 0 && future_index < ((int)future_values.size()));
- return future_values[future_index].value;
+ return future_values[future_index];
}
-modelclock_t Node::get_future_value_expiration() const
-{
- ASSERT(future_index >= 0 && future_index < ((int)future_values.size()));
- return future_values[future_index].expiration;
-}
-
-
int Node::get_read_from_size() const
{
return may_read_from.size();
#ifndef __NODESTACK_H__
#define __NODESTACK_H__
-#include <list>
#include <vector>
#include <cstddef>
#include <inttypes.h>
#include "mymemory.h"
-#include "modeltypes.h"
#include "schedule.h"
+#include "promise.h"
class ModelAction;
class Thread;
typedef int promise_t;
-struct future_value {
- uint64_t value;
- modelclock_t expiration;
-};
-
struct fairness_info {
unsigned int enabled_count;
unsigned int turns;
bool priority;
};
-
/**
* @brief A single node in a NodeStack
*
* occurred previously in the stack. */
Node * get_parent() const { return parent; }
- bool add_future_value(uint64_t value, modelclock_t expiration);
- uint64_t get_future_value() const;
- modelclock_t get_future_value_expiration() const;
+ bool add_future_value(struct future_value& fv);
+ struct future_value get_future_value() const;
bool increment_future_value();
bool future_value_empty() const;
bool increment_relseq_break();
bool relseq_break_empty() const;
- void print();
+ void print() const;
void print_may_read_from();
MEMALLOC
+#define __STDC_FORMAT_MACROS
+#include <inttypes.h>
+
#include "promise.h"
#include "model.h"
#include "schedule.h"
-bool Promise::increment_threads(thread_id_t tid) {
- unsigned int id=id_to_int(tid);
- if ( id >= synced_thread.size() ) {
- synced_thread.resize(id+1, false);
- }
- if (synced_thread[id])
+/**
+ * Eliminate a thread which no longer can satisfy this promise. Once all
+ * enabled threads have been eliminated, this promise is unresolvable.
+ *
+ * @param tid The thread ID of the thread to eliminate
+ * @return True, if this elimination has invalidated the promise; false
+ * otherwise
+ */
+bool Promise::eliminate_thread(thread_id_t tid)
+{
+ unsigned int id = id_to_int(tid);
+ if (!thread_is_available(tid))
return false;
-
- synced_thread[id]=true;
- unsigned int sync_size=synced_thread.size();
- int promise_tid=id_to_int(read->get_tid());
- for(unsigned int i=1;i<model->get_num_threads();i++) {
- if ((i >= sync_size || !synced_thread[i]) && ( (int)i != promise_tid ) && model->is_enabled(int_to_id(i))) {
- return false;
- }
- }
- return true;
+
+ available_thread[id] = false;
+ num_available_threads--;
+ return has_failed();
}
-bool Promise::check_promise() {
- unsigned int sync_size=synced_thread.size();
- for(unsigned int i=1;i<model->get_num_threads();i++) {
- if ((i >= sync_size || !synced_thread[i]) && model->is_enabled(int_to_id(i))) {
- return false;
- }
+/**
+ * Add a thread which may resolve this promise
+ *
+ * @param tid The thread ID
+ */
+void Promise::add_thread(thread_id_t tid)
+{
+ unsigned int id = id_to_int(tid);
+ if (id >= available_thread.size())
+ available_thread.resize(id + 1, false);
+ if (!available_thread[id]) {
+ available_thread[id] = true;
+ num_available_threads++;
}
- return true;
+}
+
+/**
+ * Check if a thread is available for resolving this promise. That is, the
+ * thread must have been previously marked for resolving this promise, and it
+ * cannot have been eliminated due to synchronization, etc.
+ *
+ * @param tid Thread ID of the thread to check
+ * @return True if the thread is available; false otherwise
+ */
+bool Promise::thread_is_available(thread_id_t tid) const
+{
+ unsigned int id = id_to_int(tid);
+ if (id >= available_thread.size())
+ return false;
+ return available_thread[id];
+}
+
+/** @brief Print debug info about the Promise */
+void Promise::print() const
+{
+ model_print("Promised value %#" PRIx64 ", read from thread %d, available threads to resolve: ", value, id_to_int(read->get_tid()));
+ for (unsigned int i = 0; i < available_thread.size(); i++)
+ if (available_thread[i])
+ model_print("[%d]", i);
+ model_print("\n");
+}
+
+/**
+ * Check if this promise has failed. A promise can fail when all threads which
+ * could possibly satisfy the promise have been eliminated.
+ *
+ * @return True, if this promise has failed; false otherwise
+ */
+bool Promise::has_failed() const
+{
+ return num_available_threads == 0;
+}
+
+/**
+ * @brief Check if an action's thread and location are compatible for resolving
+ * this promise
+ * @param act The action to check against
+ * @return True if we are compatible; false otherwise
+ */
+bool Promise::is_compatible(const ModelAction *act) const
+{
+ return thread_is_available(act->get_tid()) && read->same_var(act);
+}
+
+/**
+ * @brief Check if an action's thread and location are compatible for resolving
+ * this promise, and that the promise is thread-exclusive
+ * @param act The action to check against
+ * @return True if we are compatible and exclusive; false otherwise
+ */
+bool Promise::is_compatible_exclusive(const ModelAction *act) const
+{
+ return get_num_available_threads() == 1 && is_compatible(act);
}
#include "threads-model.h"
#include "model.h"
+#include "modeltypes.h"
+
+struct future_value {
+ uint64_t value;
+ modelclock_t expiration;
+ thread_id_t tid;
+};
class Promise {
public:
- Promise(ModelAction *act, uint64_t value, modelclock_t expiration) :
- value(value), expiration(expiration), read(act), write(NULL)
+ Promise(ModelAction *read, struct future_value fv) :
+ num_available_threads(0),
+ value(fv.value),
+ expiration(fv.expiration),
+ read(read),
+ write(NULL)
{
- increment_threads(act->get_tid());
+ add_thread(fv.tid);
+ eliminate_thread(read->get_tid());
}
modelclock_t get_expiration() const { return expiration; }
ModelAction * get_action() const { return read; }
- bool increment_threads(thread_id_t tid);
-
- bool has_sync_thread(thread_id_t tid) {
- unsigned int id = id_to_int(tid);
- if (id >= synced_thread.size())
- return false;
- return synced_thread[id];
- }
-
- bool check_promise();
+ bool eliminate_thread(thread_id_t tid);
+ void add_thread(thread_id_t tid);
+ bool thread_is_available(thread_id_t tid) const;
+ bool has_failed() const;
uint64_t get_value() const { return value; }
void set_write(const ModelAction *act) { write = act; }
- const ModelAction * get_write() { return write; }
+ const ModelAction * get_write() const { return write; }
+ int get_num_available_threads() const { return num_available_threads; }
+ bool is_compatible(const ModelAction *act) const;
+ bool is_compatible_exclusive(const ModelAction *act) const;
+
+ void print() const;
SNAPSHOTALLOC
private:
- std::vector<bool> synced_thread;
+ /** @brief Thread ID(s) for thread(s) that potentially can satisfy this
+ * promise */
+ std::vector< bool, SnapshotAlloc<bool> > available_thread;
+
+ int num_available_threads;
+
const uint64_t value;
const modelclock_t expiration;
+
+ /** @brief The action which reads a promised value */
ModelAction * const read;
- const ModelAction * write;
+
+ const ModelAction *write;
};
#endif
#include "model.h"
#include "nodestack.h"
+/**
+ * Format an "enabled_type_t" for printing
+ * @param e The type to format
+ * @param str The output character array
+ */
+static void enabled_type_to_string(enabled_type_t e, char *str)
+{
+ const char *res;
+ switch (e) {
+ case THREAD_DISABLED:
+ res = "disabled";
+ break;
+ case THREAD_ENABLED:
+ res = "enabled";
+ break;
+ case THREAD_SLEEP_SET:
+ res = "sleep";
+ break;
+ default:
+ ASSERT(0);
+ res = NULL;
+ break;
+ }
+ strcpy(str, res);
+}
+
/** Constructor */
Scheduler::Scheduler() :
enabled(NULL),
break;
}
if (curr_thread_index == old_curr_thread) {
- print();
+ if (DBG_ENABLED())
+ print();
return NULL;
}
}
}
current = t;
- print();
+ if (DBG_ENABLED())
+ print();
return t;
}
*/
void Scheduler::print() const
{
- if (current)
- DEBUG("Current thread: %d\n", id_to_int(current->get_id()));
- else
- DEBUG("No current thread\n");
+ int curr_id = current ? id_to_int(current->get_id()) : -1;
+
+ model_print("Scheduler: ");
+ for (int i = 0; i < enabled_len; i++) {
+ char str[20];
+ enabled_type_to_string(enabled[i], str);
+ model_print("[%i: %s%s]", i, i == curr_id ? "current, " : "", str);
+ }
+ model_print("\n");
}
#ifndef __SCHEDULE_H__
#define __SCHEDULE_H__
-#include <list>
#include "mymemory.h"
+#include "modeltypes.h"
/* Forward declaration */
class Thread;
-include ../common.mk
+BASE = ..
-CPPFLAGS += -I.. -I../include
+include $(BASE)/common.mk
+
+CPPFLAGS += -I$(BASE) -I$(BASE)/include
SRCS = $(wildcard *.c)
CPSRCS = $(wildcard *.cc)
OBJS = $(patsubst %.c,%.o,$(SRCS)) $(patsubst %.cc,%.o,$(CPSRCS))
-all: $(OBJS)
+all: $(OBJS) litmus-tests
+
+litmus-tests::
+ $(MAKE) -C litmus
%.o: %.c
- $(CC) -o $@ $< $(CPPFLAGS) -L.. -l$(LIB_NAME)
+ $(CC) -o $@ $< $(CPPFLAGS) -L$(BASE) -l$(LIB_NAME)
%.o: %.cc
- $(CXX) -o $@ $< $(CPPFLAGS) -L.. -l$(LIB_NAME)
+ $(CXX) -o $@ $< $(CPPFLAGS) -L$(BASE) -l$(LIB_NAME)
clean::
rm -f *.o
+ $(MAKE) -C litmus clean
--- /dev/null
+BASE = ../..
+
+include $(BASE)/common.mk
+
+CPPFLAGS += -I$(BASE) -I$(BASE)/include
+
+SRCS = $(wildcard *.c)
+CPSRCS = $(wildcard *.cc)
+OBJS = $(patsubst %.c,%.o,$(SRCS)) $(patsubst %.cc,%.o,$(CPSRCS))
+
+all: $(OBJS)
+
+%.o: %.c
+ $(CC) -o $@ $< $(CPPFLAGS) -L$(BASE) -l$(LIB_NAME)
+
+%.o: %.cc
+ $(CXX) -o $@ $< $(CPPFLAGS) -L$(BASE) -l$(LIB_NAME)
+
+clean::
+ rm -f *.o
--- /dev/null
+#include <stdio.h>
+#include <threads.h>
+#include <atomic>
+
+std::atomic_int x;
+std::atomic_int y;
+
+std::memory_order store_mo = std::memory_order_release;
+std::memory_order load_mo = std::memory_order_acquire;
+
+static void a(void *obj)
+{
+ x.store(1, store_mo);
+}
+
+static void b(void *obj)
+{
+ y.store(1, store_mo);
+}
+
+static void c(void *obj)
+{
+ printf("x1: %d\n", x.load(load_mo));
+ printf("y1: %d\n", y.load(load_mo));
+}
+
+static void d(void *obj)
+{
+ printf("y2: %d\n", y.load(load_mo));
+ printf("x2: %d\n", x.load(load_mo));
+}
+
+int user_main(int argc, char **argv)
+{
+ thrd_t t1, t2, t3, t4;
+
+ /* Command-line argument 's' enables seq_cst test */
+ if (argc > 1 && *argv[1] == 's')
+ store_mo = load_mo = std::memory_order_seq_cst;
+
+ atomic_init(&x, 0);
+ atomic_init(&y, 0);
+
+ printf("Main thread: creating 4 threads\n");
+ thrd_create(&t1, (thrd_start_t)&a, NULL);
+ thrd_create(&t2, (thrd_start_t)&b, NULL);
+ thrd_create(&t3, (thrd_start_t)&c, NULL);
+ thrd_create(&t4, (thrd_start_t)&d, NULL);
+
+ thrd_join(t1);
+ thrd_join(t2);
+ thrd_join(t3);
+ thrd_join(t4);
+ printf("Main thread is finished\n");
+
+ return 0;
+}
--- /dev/null
+#include <stdio.h>
+#include <threads.h>
+#include <atomic>
+
+std::atomic_int x;
+std::atomic_int y;
+
+static void a(void *obj)
+{
+ printf("x: %d\n", x.load(std::memory_order_relaxed));
+ y.store(1, std::memory_order_relaxed);
+}
+
+static void b(void *obj)
+{
+ printf("y: %d\n", y.load(std::memory_order_relaxed));
+ x.store(1, std::memory_order_relaxed);
+}
+
+int user_main(int argc, char **argv)
+{
+ thrd_t t1, t2;
+
+ atomic_init(&x, 0);
+ atomic_init(&y, 0);
+
+ printf("Main thread: creating 2 threads\n");
+ thrd_create(&t1, (thrd_start_t)&a, NULL);
+ thrd_create(&t2, (thrd_start_t)&b, NULL);
+
+ thrd_join(t1);
+ thrd_join(t2);
+ printf("Main thread is finished\n");
+
+ return 0;
+}
--- /dev/null
+#include <stdio.h>
+#include <threads.h>
+#include <atomic>
+
+std::atomic_int x;
+std::atomic_int y;
+
+static void a(void *obj)
+{
+ x.store(1, std::memory_order_relaxed);
+ y.store(1, std::memory_order_relaxed);
+}
+
+static void b(void *obj)
+{
+ printf("y1: %d\n", y.load(std::memory_order_relaxed));
+ printf("x1: %d\n", x.load(std::memory_order_relaxed));
+}
+
+static void c(void *obj)
+{
+ printf("x2: %d\n", x.load(std::memory_order_relaxed));
+ printf("y2: %d\n", y.load(std::memory_order_relaxed));
+}
+
+int user_main(int argc, char **argv)
+{
+ thrd_t t1, t2, t3;
+
+ atomic_init(&x, 0);
+ atomic_init(&y, 0);
+
+ printf("Main thread: creating 3 threads\n");
+ thrd_create(&t1, (thrd_start_t)&a, NULL);
+ thrd_create(&t2, (thrd_start_t)&b, NULL);
+ thrd_create(&t3, (thrd_start_t)&c, NULL);
+
+ thrd_join(t1);
+ thrd_join(t2);
+ thrd_join(t3);
+ printf("Main thread is finished\n");
+
+ return 0;
+}
--- /dev/null
+#include <stdlib.h>
+#include <stdio.h>
+#include <threads.h>
+#include <atomic>
+
+std::atomic_int x;
+std::atomic_int y;
+std::atomic_int z;
+
+static int N = 1;
+
+static void a(void *obj)
+{
+ for (int i = 0; i < N; i++) {
+ x.store(2 * i + 1, std::memory_order_release);
+ y.store(i + 1, std::memory_order_release);
+ z.store(i + 1, std::memory_order_release);
+ x.store(2 * i + 2, std::memory_order_release);
+ }
+}
+
+static void b(void *obj)
+{
+ printf("x: %d\n", x.load(std::memory_order_acquire));
+ printf("y: %d\n", y.load(std::memory_order_acquire));
+ printf("z: %d\n", z.load(std::memory_order_acquire));
+ printf("x: %d\n", x.load(std::memory_order_acquire));
+}
+
+int user_main(int argc, char **argv)
+{
+ thrd_t t1, t2;
+
+ if (argc > 1)
+ N = atoi(argv[1]);
+
+ printf("N: %d\n", N);
+
+ atomic_init(&x, 0);
+ atomic_init(&y, 0);
+ atomic_init(&z, 0);
+
+ printf("Main thread: creating 2 threads\n");
+ thrd_create(&t1, (thrd_start_t)&a, NULL);
+ thrd_create(&t2, (thrd_start_t)&b, NULL);
+
+ thrd_join(t1);
+ thrd_join(t2);
+ printf("Main thread is finished\n");
+
+ return 0;
+}
--- /dev/null
+#include <stdio.h>
+#include <threads.h>
+#include <atomic>
+
+std::atomic_int x;
+std::atomic_int y;
+
+static void a(void *obj)
+{
+ x.store(1, std::memory_order_relaxed);
+ printf("y: %d\n", y.load(std::memory_order_relaxed));
+}
+
+static void b(void *obj)
+{
+ y.store(1, std::memory_order_relaxed);
+ printf("x: %d\n", x.load(std::memory_order_relaxed));
+}
+
+int user_main(int argc, char **argv)
+{
+ thrd_t t1, t2;
+
+ atomic_init(&x, 0);
+ atomic_init(&y, 0);
+
+ printf("Main thread: creating 2 threads\n");
+ thrd_create(&t1, (thrd_start_t)&a, NULL);
+ thrd_create(&t2, (thrd_start_t)&b, NULL);
+
+ thrd_join(t1);
+ thrd_join(t2);
+ printf("Main thread is finished\n");
+
+ return 0;
+}
--- /dev/null
+#include <stdlib.h>
+#include <stdio.h>
+#include <threads.h>
+#include <atomic>
+
+static int N = 2;
+
+std::atomic_int *x;
+
+static void a(void *obj)
+{
+ int idx = *((int *)obj);
+
+ if (idx > 0)
+ x[idx - 1].load(std::memory_order_relaxed);
+
+ if (idx < N)
+ x[idx].store(1, std::memory_order_relaxed);
+ else
+ x[0].load(std::memory_order_relaxed);
+}
+
+int user_main(int argc, char **argv)
+{
+ thrd_t *threads;
+ int *indexes;
+
+ if (argc > 1)
+ N = atoi(argv[1]);
+ if (N < 2) {
+ printf("Error: must have N >= 2\n");
+ return 1;
+ }
+ printf("N: %d\n", N);
+
+ threads = (thrd_t *)malloc((N + 1) * sizeof(thrd_t));
+ x = (std::atomic_int *)malloc(N * sizeof(std::atomic_int));
+ indexes = (int *)malloc((N + 1) * sizeof(int));
+
+ for (int i = 0; i < N + 1; i++)
+ indexes[i] = i;
+
+ for (int i = 0; i < N; i++)
+ atomic_init(&x[i], 0);
+
+ for (int i = 0; i < N + 1; i++)
+ thrd_create(&threads[i], (thrd_start_t)&a, (void *)&indexes[i]);
+
+ for (int i = 0; i < N + 1; i++)
+ thrd_join(threads[i]);
+
+ return 0;
+}
+#include <stdlib.h>
#include <stdio.h>
#include <threads.h>
#include <stdatomic.h>
#include "librace.h"
atomic_int x;
+static int N = 2;
static void a(void *obj)
{
- atomic_fetch_add_explicit(&x, 1, memory_order_relaxed);
- atomic_fetch_add_explicit(&x, 1, memory_order_relaxed);
+ int i;
+ for (i = 0; i < N; i++)
+ atomic_fetch_add_explicit(&x, 1, memory_order_relaxed);
}
int user_main(int argc, char **argv)
{
thrd_t t1, t2;
+ if (argc > 1)
+ N = atoi(argv[1]);
+
atomic_init(&x, 0);
thrd_create(&t1, (thrd_start_t)&a, NULL);
thrd_create(&t2, (thrd_start_t)&a, NULL);
projects / c11tester.git / commitdiff