When we add an edge between 'rmwnode' and 'tonode', we are trying to
ensure RMW atomicity. But 'rmwnode' may itself be read by another RMW
(or, in fact, a chain). So we must follow this chain down before
propagating the atomicity edge.
Also, we have the potential to run into the same problem in
addRMWEdge(), except that in that function, we assume that the RMW is
newly-explored and so does not yet have an outgoing RMW edge. This adds
an ASSERT() to check this property.
*/
bool CycleGraph::addNodeEdge(CycleNode *fromnode, CycleNode *tonode)
{
*/
bool CycleGraph::addNodeEdge(CycleNode *fromnode, CycleNode *tonode)
{
- bool added;
-
- if ((added = fromnode->addEdge(tonode))) {
+ if (fromnode->addEdge(tonode)) {
rollbackvector.push_back(fromnode);
if (!hasCycles)
hasCycles = checkReachable(tonode, fromnode);
rollbackvector.push_back(fromnode);
if (!hasCycles)
hasCycles = checkReachable(tonode, fromnode);
+ } else
+ return false; /* No new edge */
- * If the fromnode has a rmwnode that is not the tonode, we should add
- * an edge between its rmwnode and the tonode
+ * If the fromnode has a rmwnode that is not the tonode, we should
+ * follow its RMW chain to add an edge at the end, unless we encounter
+ * tonode along the way
*/
CycleNode *rmwnode = fromnode->getRMW();
*/
CycleNode *rmwnode = fromnode->getRMW();
- if (rmwnode && rmwnode != tonode) {
- if (rmwnode->addEdge(tonode)) {
- if (!hasCycles)
- hasCycles = checkReachable(tonode, rmwnode);
+ if (rmwnode) {
+ while (rmwnode != tonode && rmwnode->getRMW())
+ rmwnode = rmwnode->getRMW();
- rollbackvector.push_back(rmwnode);
- added = true;
+ if (rmwnode != tonode) {
+ if (rmwnode->addEdge(tonode)) {
+ if (!hasCycles)
+ hasCycles = checkReachable(tonode, rmwnode);
+
+ rollbackvector.push_back(rmwnode);
+ }
CycleNode *fromnode = getNode(from);
CycleNode *rmwnode = getNode(rmw);
CycleNode *fromnode = getNode(from);
CycleNode *rmwnode = getNode(rmw);
+ /* We assume that this RMW has no RMW reading from it yet */
+ ASSERT(!rmwnode->getRMW());
+
/* Two RMW actions cannot read from the same write. */
if (fromnode->setRMW(rmwnode))
hasCycles = true;
/* Two RMW actions cannot read from the same write. */
if (fromnode->setRMW(rmwnode))
hasCycles = true;