Menu
▾
▴
[Scstudio-commits] SF.net SVN: scstudio:[105] trunk
|
From: <ba...@us...> - 2008-08-03 17:56:47
|
Revision: 105
http://scstudio.svn.sourceforge.net/scstudio/?rev=105&view=rev
Author: babicaj
Date: 2008-08-03 17:56:44 +0000 (Sun, 03 Aug 2008)
Log Message:
-----------
DeadlockChecker bug found and corrected, dynamic attribute setting improved to test presence of attribute
Modified Paths:
--------------
trunk/Makefile
trunk/src/check/deadlock_checker.cpp
trunk/src/check/deadlock_checker.h
trunk/src/data/msc.h
Modified: trunk/Makefile
===================================================================
--- trunk/Makefile 2008-08-01 20:39:02 UTC (rev 104)
+++ trunk/Makefile 2008-08-03 17:56:44 UTC (rev 105)
@@ -99,6 +99,20 @@
.PHONY : depend
# Convenience name for target.
+CMakeFiles/deadlock_checker_test.dir/rule:
+ $(MAKE) -f CMakeFiles/Makefile2 CMakeFiles/deadlock_checker_test.dir/rule
+.PHONY : CMakeFiles/deadlock_checker_test.dir/rule
+
+# Convenience name for target.
+deadlock_checker_test: CMakeFiles/deadlock_checker_test.dir/rule
+.PHONY : deadlock_checker_test
+
+# fast build rule for target.
+deadlock_checker_test/fast:
+ $(MAKE) -f CMakeFiles/deadlock_checker_test.dir/build.make CMakeFiles/deadlock_checker_test.dir/build
+.PHONY : deadlock_checker_test/fast
+
+# Convenience name for target.
CMakeFiles/fifo_checker_test.dir/rule:
$(MAKE) -f CMakeFiles/Makefile2 CMakeFiles/fifo_checker_test.dir/rule
.PHONY : CMakeFiles/fifo_checker_test.dir/rule
@@ -127,6 +141,21 @@
.PHONY : livelock_checker_test/fast
# target to build an object file
+deadlock_checker_test.o:
+ $(MAKE) -f CMakeFiles/deadlock_checker_test.dir/build.make CMakeFiles/deadlock_checker_test.dir/deadlock_checker_test.o
+.PHONY : deadlock_checker_test.o
+
+# target to preprocess a source file
+deadlock_checker_test.i:
+ $(MAKE) -f CMakeFiles/deadlock_checker_test.dir/build.make CMakeFiles/deadlock_checker_test.dir/deadlock_checker_test.i
+.PHONY : deadlock_checker_test.i
+
+# target to generate assembly for a file
+deadlock_checker_test.s:
+ $(MAKE) -f CMakeFiles/deadlock_checker_test.dir/build.make CMakeFiles/deadlock_checker_test.dir/deadlock_checker_test.s
+.PHONY : deadlock_checker_test.s
+
+# target to build an object file
fifo_checker_test.o:
$(MAKE) -f CMakeFiles/fifo_checker_test.dir/build.make CMakeFiles/fifo_checker_test.dir/fifo_checker_test.o
.PHONY : fifo_checker_test.o
@@ -162,10 +191,14 @@
@echo "... all (the default if no target is provided)"
@echo "... clean"
@echo "... depend"
+ @echo "... deadlock_checker_test"
@echo "... edit_cache"
@echo "... fifo_checker_test"
@echo "... livelock_checker_test"
@echo "... rebuild_cache"
+ @echo "... deadlock_checker_test.o"
+ @echo "... deadlock_checker_test.i"
+ @echo "... deadlock_checker_test.s"
@echo "... fifo_checker_test.o"
@echo "... fifo_checker_test.i"
@echo "... fifo_checker_test.s"
Modified: trunk/src/check/deadlock_checker.cpp
===================================================================
--- trunk/src/check/deadlock_checker.cpp 2008-08-01 20:39:02 UTC (rev 104)
+++ trunk/src/check/deadlock_checker.cpp 2008-08-03 17:56:44 UTC (rev 105)
@@ -20,26 +20,99 @@
DeadlockCheckerPtr DeadlockChecker::m_instance;
+void DeadlockListener::on_white_node_found(InnerNode* node)
+{
+ //set depth attribute
+ m_current_depth++;
+ get_depth(node) = m_current_depth;
+ if (dynamic_cast<ReferenceNode*> (node))
+ {
+ m_reference_depth.push(m_current_depth);
+ }
+ //set deadlock free attribute
+ bool& deadlock_free = get_deadlock_free(node);
+ if (node->is_end_node())
+ {
+ mark_deadlock_free(node);
+ }
+}
+
+void DeadlockListener::on_node_finished(InnerNode* node)
+{
+ if (dynamic_cast<ReferenceNode*> (node))
+ {
+ bool& deadlock_free = get_deadlock_free(node);
+ if (!deadlock_free)
+ {
+ throw DeadlockException();
+ }
+ //this node is no more on traversing stack
+ m_reference_depth.pop();
+ }
+ m_current_depth--;
+}
+
+void DeadlockListener::on_gray_node_found(InnerNode* node)
+{
+ //m_reference_depth can be empty
+ if (!m_reference_depth.empty())
+ {
+ //depth of node is surely set (in on_white_node_found())
+ size_t node_depth = get_depth(node);
+ size_t top_reference_depth = m_reference_depth.top();
+ //there is some ReferenceNode on path from node to previous white InnerNode
+ if (top_reference_depth >= m_current_depth)
+ {
+ mark_deadlock_free(node);
+ }
+ }
+}
+
+void DeadlockListener::mark_deadlock_free(InnerNode* node)
+{
+ bool& deadlock_free = get_deadlock_free(node);
+ deadlock_free = true;
+ InnerNodePSet::const_iterator n;
+ const InnerNodePSet& preds = node->get_predecessors();
+ for (n = preds.begin(); n != preds.end(); n++)
+ {
+ if (!get_deadlock_free(*n))
+ {
+ mark_deadlock_free(*n);
+ }
+ }
+}
+
+void DeadlockListener::cleanup_attributes()
+{
+ while (!m_modified.empty())
+ {
+ m_modified.back()->remove_attribute<bool>(m_deadlock_free_attribute);
+ m_modified.back()->remove_attribute<size_t> (m_depth_attribute);
+ m_modified.pop_back();
+ }
+}
+
HMscPtr DeadlockChecker::create_counter_example(const InnerNodePListList& path)
{
InnerNodePListList::const_iterator hmscs_it;
HMscPtr result;
- for(hmscs_it=path.begin();hmscs_it!=path.end();hmscs_it++)
+ for (hmscs_it = path.begin(); hmscs_it != path.end(); hmscs_it++)
{
HMscPtr current_hmsc;
InnerNode* last_node = NULL;
InnerNodePList::const_iterator nodes_it;
- for(nodes_it=hmscs_it->begin();nodes_it!=hmscs_it->end();nodes_it++)
+ for (nodes_it = hmscs_it->begin(); nodes_it != hmscs_it->end(); nodes_it++)
{
- if(last_node==NULL)
+ if (last_node == NULL)
{
- if(dynamic_cast<ReferenceNode*>(*nodes_it)!=NULL)
- last_node = new ReferenceNode((ReferenceNode*)*nodes_it);
+ if (dynamic_cast<ReferenceNode*> (*nodes_it) != NULL)
+ last_node = new ReferenceNode((ReferenceNode*) * nodes_it);
else
- last_node = new ConnectionNode((ConnectionNode*)*nodes_it);
+ last_node = new ConnectionNode((ConnectionNode*) * nodes_it);
current_hmsc = new HMsc((*nodes_it)->get_owner());
current_hmsc->get_start()->add_successor(last_node);
- if(!result.get())
+ if (!result.get())
result = current_hmsc;
}
else
@@ -59,11 +132,13 @@
DeadlockListener listener;
DFSHMscTraverser traverser;
traverser.add_white_node_found_listener(&listener);
+ traverser.add_gray_node_found_listener(&listener);
+ traverser.add_node_finished_listener(&listener);
try
{
traverser.traverse(hmsc);
}
- catch(DeadlockException& e)
+ catch (DeadlockException& e)
{
p = create_counter_example(traverser.get_reached_nodes());
traverser.cleanup_traversing_attributes();
Modified: trunk/src/check/deadlock_checker.h
===================================================================
--- trunk/src/check/deadlock_checker.h 2008-08-01 20:39:02 UTC (rev 104)
+++ trunk/src/check/deadlock_checker.h 2008-08-03 17:56:44 UTC (rev 105)
@@ -40,17 +40,58 @@
}
};
-class DeadlockListener:public WhiteRefNodeFoundListener
+class DeadlockListener:
+public WhiteNodeFoundListener,
+public GrayNodeFoundListener,
+public NodeFinishedListener
{
+protected:
+
+ /**
+ * Depth of last found white InnerNode in Depth First Search tree
+ */
+ size_t m_current_depth;
+
+ /**
+ * Depths of founded ReferenceNodes
+ */
+ std::stack<size_t> m_reference_depth;
+
+ std::string m_deadlock_free_attribute;
+
+ std::string m_depth_attribute;
+
+ InnerNodePList m_modified;
+
+ bool& get_deadlock_free(InnerNode* node);
+
+ size_t& get_depth(InnerNode* node);
+
public:
- void on_white_node_found(ReferenceNode* node)
+ DeadlockListener(
+ const std::string& deadlock_free_attribute ="dl:deadlock_free",
+ const std::string& depth_attribute ="dl:depth")
{
- if(!node->is_end_node() && !node->has_successors())
- {
- throw DeadlockException();
- }
+ m_current_depth = 0;
+ m_deadlock_free_attribute = deadlock_free_attribute;
+ m_depth_attribute = depth_attribute;
}
+
+ void on_white_node_found(InnerNode* node);
+
+ void on_node_finished(InnerNode* node);
+
+ void on_gray_node_found(InnerNode* node);
+
+ void mark_deadlock_free(InnerNode* node);
+
+ void cleanup_attributes();
+
+ ~DeadlockListener()
+ {
+ cleanup_attributes();
+ }
};
class DeadlockChecker: public HMscChecker
Modified: trunk/src/data/msc.h
===================================================================
--- trunk/src/data/msc.h 2008-08-01 20:39:02 UTC (rev 104)
+++ trunk/src/data/msc.h 2008-08-03 17:56:44 UTC (rev 105)
@@ -195,6 +195,39 @@
}
/**
+ * Returns dynamic attribute of MscElement.
+ *
+ * If attribute is not set, value of def is copied into its value and is
+ * returned. T is type of attribute.
+ *
+ * Keep in mind that this method hasn't got constant complexity but O(log n)
+ * where n=number of dynamic attributes set to this element.
+ *
+ * @param name - attribute name
+ * @param def - default value of attribute
+ * @param status - set to true if attribute was just created, to false
+ * otherwise
+ */
+ template<class T>
+ T& get_attribute(const std::string& name, const T& def, bool& status)
+ {
+ AttributePMap::iterator i = m_attributes.find(name);
+ T* a;
+ if(i!=m_attributes.end())
+ {
+ a = static_cast<T*>(i->second);
+ status = false;
+ }else{
+ //insert attribute with default value
+ a = new T;
+ *a = def;
+ m_attributes[name] = a;
+ status = true;
+ }
+ return *a;
+ }
+
+ /**
* Sets dynamic attribute of MscElement.
*
* Value of def is copied as value of this attribute. T is type of attribute.
@@ -552,6 +585,12 @@
* @warning counted_ptrs mustn't be used because of possible cyclic dependency
*/
InnerNodePSet m_predecessors;
+
+ /**
+ * EndNode which this ReferenceNode is connected to,
+ * undefined if there isn't any such connection.
+ */
+ EndNodePtr m_end;
InnerNode(InnerNode* original=NULL):HMscNode(original)
{
@@ -615,6 +654,37 @@
return m_successors.size()!=0;
}
+ /**
+ * Getter for m_end.
+ */
+ EndNodePtr get_end()
+ {
+ return m_end;
+ }
+
+ EndNodePtr set_end()
+ {
+ EndNodePtr end(new EndNode);
+ end->set_owner(m_owner);
+ return m_end = end;
+ }
+
+ /**
+ * Setter for m_end
+ */
+ EndNodePtr set_end(EndNodePtr end)
+ {
+ return m_end = end;
+ }
+
+ /**
+ * Returns true iff m_end is defined.
+ */
+ bool is_end_node()
+ {
+ return m_end.get();
+ }
+
friend class HMsc;
};
@@ -631,12 +701,6 @@
* MSC which is contained in this node.
*/
MscPtr m_msc;
-
- /**
- * EndNode which this ReferenceNode is connected to,
- * undefined if there isn't any such connection.
- */
- EndNodePtr m_end;
public:
@@ -651,31 +715,8 @@
{
}
- /**
- * Getter for m_end.
- */
- EndNodePtr get_end()
- {
- return m_end;
- }
- EndNodePtr set_end()
- {
- EndNodePtr end(new EndNode);
- end->set_owner(m_owner);
- return m_end = end;
- }
-
/**
- * Setter for m_end
- */
- EndNodePtr set_end(EndNodePtr end)
- {
- return m_end = end;
- }
-
-
- /**
* Getter for m_msc.
*/
MscPtr get_msc()
@@ -725,14 +766,6 @@
return p;
}
- /**
- * Returns true iff m_end is defined.
- */
- bool is_end_node()
- {
- return m_end.get();
- }
-
};
/**
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
