rfnoc: graph: Optimize property propagation algorithm

This introduces the concept of a resolution context, because the
property propagation algorithm needs to behave differently when called
during an initialization step (e.g. when the graph is committed), or
when the user changes a property on one of the nodes after it was
committed.

The algorithm is modified as follows:

- When called during an initialization step, then all nodes get resolved
  at least once. If nodes added new properties, then all nodes get
  touched again until the max number of iterations is reached.
- When called because a node modified one of its properties, then that
  node is always resolved first. From there, all other nodes are
  resolved in topological order. However, the algorithm immediately
  terminates as soon as there are no more dirty nodes.
- When called because a node modified one of its properties, but the
  graph is currently not in a committed state, then that node will do
  a local property resolution.

4 files changed, 66 insertions, 27 deletions

diff --git a/host/lib/include/uhdlib/rfnoc/graph.hpp b/host/lib/include/uhdlib/rfnoc/graph.hpp
index 5b735b624..286f2303f 100644
--- a/host/lib/include/uhdlib/rfnoc/graph.hpp
+++ b/host/lib/include/uhdlib/rfnoc/graph.hpp
@@ -10,6 +10,7 @@
 #include <uhd/rfnoc/actions.hpp>
 #include <uhd/rfnoc/graph_edge.hpp>
 #include <uhd/rfnoc/node.hpp>
+#include <uhdlib/rfnoc/resolve_context.hpp>
 #include <boost/graph/adjacency_list.hpp>
 #include <deque>
 #include <memory>
@@ -146,7 +147,8 @@ private:
      *************************************************************************/
     /*! Implementation of the property propagation algorithm
      */
-    void resolve_all_properties();
+    void resolve_all_properties(uhd::rfnoc::resolve_context context,
+        rfnoc_graph_t::vertex_descriptor initial_node);
 
     /**************************************************************************
      * Action API
diff --git a/host/lib/include/uhdlib/rfnoc/resolve_context.hpp b/host/lib/include/uhdlib/rfnoc/resolve_context.hpp
new file mode 100644
index 000000000..29a2e5f6f
--- /dev/null
+++ b/host/lib/include/uhdlib/rfnoc/resolve_context.hpp
@@ -0,0 +1,26 @@
+//
+//
+// Copyright 2019 Ettus Research, a National Instruments Company
+//
+// SPDX-License-Identifier: GPL-3.0-or-later
+//
+
+#ifndef INCLUDED_UHD_RFNOC_RESOLVE_CONTEXT_HPP
+#define INCLUDED_UHD_RFNOC_RESOLVE_CONTEXT_HPP
+
+namespace uhd { namespace rfnoc {
+
+/*! Describe situations out of which property propagation is called
+ */
+enum class resolve_context {
+    //! Property propagation was called during an initialization process (e.g.,
+    // the graph was committed)
+    INIT,
+    //! Property propagation was called because a property on a node was
+    // updated
+    NODE_PROP
+};
+
+}} // namespace uhd::rfnoc
+
+#endif /* INCLUDED_UHD_RFNOC_RESOLVE_CONTEXT_HPP */
diff --git a/host/lib/rfnoc/graph.cpp b/host/lib/rfnoc/graph.cpp
index 6c849b61f..7be0c0035 100644
--- a/host/lib/rfnoc/graph.cpp
+++ b/host/lib/rfnoc/graph.cpp
@@ -116,11 +116,20 @@ void graph_t::connect(node_ref_t src_node, node_ref_t dst_node, graph_edge_t edg
     edge_info.src_blockid = src_node->get_unique_id();
     edge_info.dst_blockid = dst_node->get_unique_id();
 
+    // Add nodes to graph, if not already in there:
+    _add_node(src_node);
+    _add_node(dst_node);
+    // Find vertex descriptors
+    auto src_vertex_desc = _node_map.at(src_node);
+    auto dst_vertex_desc = _node_map.at(dst_node);
+
     // Set resolver callbacks:
-    node_accessor.set_resolve_all_callback(
-        src_node, [this]() { this->resolve_all_properties(); });
-    node_accessor.set_resolve_all_callback(
-        dst_node, [this]() { this->resolve_all_properties(); });
+    node_accessor.set_resolve_all_callback(src_node, [this, src_vertex_desc]() {
+        this->resolve_all_properties(resolve_context::NODE_PROP, src_vertex_desc);
+    });
+    node_accessor.set_resolve_all_callback(dst_node, [this, dst_vertex_desc]() {
+        this->resolve_all_properties(resolve_context::NODE_PROP, dst_vertex_desc);
+    });
     // Set post action callbacks:
     node_accessor.set_post_action_callback(
         src_node, [this, src_node](const res_source_info& src, action_info::sptr action) {
@@ -131,13 +140,6 @@ void graph_t::connect(node_ref_t src_node, node_ref_t dst_node, graph_edge_t edg
             this->enqueue_action(dst_node, src, action);
         });
 
-    // Add nodes to graph, if not already in there:
-    _add_node(src_node);
-    _add_node(dst_node);
-    // Find vertex descriptors
-    auto src_vertex_desc = _node_map.at(src_node);
-    auto dst_vertex_desc = _node_map.at(dst_node);
-
     // Check if connection exists
     // This can be optimized: Edges can appear in both out_edges and in_edges,
     // and we could skip double-checking them.
@@ -181,7 +183,7 @@ void graph_t::commit()
     }
     if (_release_count == 0) {
         _check_topology();
-        resolve_all_properties();
+        resolve_all_properties(resolve_context::INIT, *boost::vertices(_graph).first);
     }
 }
 
@@ -210,8 +212,11 @@ std::vector<graph_t::graph_edge_t> graph_t::enumerate_edges()
 /******************************************************************************
  * Private methods to be called by friends
  *****************************************************************************/
-void graph_t::resolve_all_properties()
+void graph_t::resolve_all_properties(
+    resolve_context context, rfnoc_graph_t::vertex_descriptor initial_node)
 {
+    node_accessor_t node_accessor{};
+
     if (boost::num_vertices(_graph) == 0) {
         return;
     }
@@ -221,9 +226,16 @@ void graph_t::resolve_all_properties()
     // running.
     std::lock_guard<std::recursive_mutex> l(_release_mutex);
     if (_release_count) {
+        node_ref_t current_node = boost::get(vertex_property_t(), _graph, initial_node);
+        UHD_LOG_TRACE(LOG_ID,
+            "Only resolving node " << current_node->get_unique_id()
+                                   << ", graph is not committed!");
+        // On current node, call local resolution.
+        node_accessor.resolve_props(current_node);
+        // Now mark all properties on this node as clean
+        node_accessor.clean_props(current_node);
         return;
     }
-    node_accessor_t node_accessor{};
 
     // First, find the node on which we'll start.
     auto initial_dirty_nodes = _find_dirty_nodes();
@@ -237,14 +249,6 @@ void graph_t::resolve_all_properties()
             UHD_LOG_WARNING(LOG_ID, "Dirty: " << node->get_unique_id());
         }
     }
-    if (initial_dirty_nodes.empty()) {
-        UHD_LOG_DEBUG(LOG_ID,
-            "In resolve_all_properties(): No dirty properties found. Starting on "
-            "arbitrary node.");
-        initial_dirty_nodes.push_back(*boost::vertices(_graph).first);
-    }
-    UHD_ASSERT_THROW(!initial_dirty_nodes.empty());
-    auto initial_node = initial_dirty_nodes.front();
 
     // Now get all nodes in topologically sorted order, and the appropriate
     // iterators.
@@ -286,6 +290,14 @@ void graph_t::resolve_all_properties()
         // Now mark all properties on this node as clean
         node_accessor.clean_props(current_node);
 
+        // If the property resolution was triggered by a node updating one of
+        // its properties, we can stop anytime there are no more dirty nodes.
+        if (context == resolve_context::NODE_PROP && _find_dirty_nodes().empty()) {
+            UHD_LOG_TRACE(LOG_ID,
+                "Terminating graph resolution early during iteration " << num_iterations);
+            break;
+        }
+
         // The rest of the code in this loop is to figure out who's the next
         // node. First, increment (or decrement) iterator:
         if (forward_dir) {
@@ -312,7 +324,7 @@ void graph_t::resolve_all_properties()
         // we've gone full circle (one full iteration).
         if (forward_dir && (*node_it == initial_node)) {
             num_iterations++;
-            if (num_iterations == MAX_NUM_ITERATIONS) {
+            if (num_iterations == MAX_NUM_ITERATIONS || _find_dirty_nodes().empty()) {
                 UHD_LOG_TRACE(LOG_ID,
                     "Terminating graph resolution after iteration " << num_iterations);
                 break;
diff --git a/host/tests/rfnoc_propprop_test.cpp b/host/tests/rfnoc_propprop_test.cpp
index 8942a59f0..2b8cd635c 100644
--- a/host/tests/rfnoc_propprop_test.cpp
+++ b/host/tests/rfnoc_propprop_test.cpp
@@ -324,11 +324,10 @@ BOOST_AUTO_TEST_CASE(test_graph_ro_prop)
     graph.commit();
 
     const size_t rx_rssi_resolver_count = mock_rx_radio.rssi_resolver_count;
+    UHD_LOG_INFO("TEST", "Now testing mock RSSI resolver/get prop");
     UHD_LOG_DEBUG("TEST", "RX RSSI: " << mock_rx_radio.get_property<double>("rssi"));
     // The next value must match the value in graph.cpp
-    constexpr size_t MAX_NUM_ITERATIONS = 2;
-    BOOST_CHECK_EQUAL(
-        rx_rssi_resolver_count + MAX_NUM_ITERATIONS, mock_rx_radio.rssi_resolver_count);
+    BOOST_CHECK_EQUAL(rx_rssi_resolver_count + 1, mock_rx_radio.rssi_resolver_count);
 }
 
 BOOST_AUTO_TEST_CASE(test_graph_double_connect)