rfnoc: Add property propagation, Boost.Graph storage

- Adds a detail::graph_t class, which handles the propagation
- Adds methods to node_t to aid with propagation
- Adds unit tests
- Adds dynamic property forwarding:
  Nodes are now able to forward properties they don't know about by
  providing a forwarding policy. A good example is the FIFO block which
  simply forwards most properties verbatim.

- node: Temporarily disabling consistency check at init

2 files changed, 274 insertions, 2 deletions

diff --git a/host/lib/include/uhdlib/rfnoc/graph.hpp b/host/lib/include/uhdlib/rfnoc/graph.hpp
new file mode 100644
index 000000000..f9fb7ac41
--- /dev/null
+++ b/host/lib/include/uhdlib/rfnoc/graph.hpp
@@ -0,0 +1,271 @@
+//
+// Copyright 2019 Ettus Research, a National Instruments Brand
+//
+// SPDX-License-Identifier: GPL-3.0-or-later
+//
+
+#ifndef INCLUDED_LIBUHD_GRAPH_HPP
+#define INCLUDED_LIBUHD_GRAPH_HPP
+
+#include <uhd/rfnoc/node.hpp>
+#include <boost/graph/adjacency_list.hpp>
+#include <tuple>
+#include <memory>
+
+namespace uhd { namespace rfnoc {
+
+/*! A container that holds information about a graph edge
+ */
+struct graph_edge_t
+{
+    enum edge_t {
+        STATIC, ///< A static connection between two blocks in the FPGA
+        DYNAMIC, ///< A user (dynamic) connection between two blocks in the FPGA
+        RX_STREAM, ///< A connection from an FPGA block to a software RX streamer
+        TX_STREAM ///< A connection from a software TX streamer and an FPGA block
+    };
+
+    graph_edge_t() = default;
+
+    graph_edge_t(const size_t src_port_,
+        const size_t dst_port_,
+        const edge_t edge_,
+        const bool ppa)
+        : src_port(src_port_)
+        , dst_port(dst_port_)
+        , edge(edge_)
+        , property_propagation_active(ppa)
+    {
+    }
+
+    //! The block ID of the source block for this edge
+    std::string src_blockid;
+    //! The port number of the source block for this edge
+    size_t src_port = 0;
+    //! The block ID of the destination block for this edge
+    std::string dst_blockid;
+    //! The port number of the destination block for this edge
+    size_t dst_port = 0;
+    //! The type of edge
+    edge_t edge = DYNAMIC;
+    //! When true, the framework will use this edge for property propagation
+    bool property_propagation_active = true;
+
+    bool operator==(const graph_edge_t& rhs) const
+    {
+        return std::tie(src_blockid,
+                   src_port,
+                   dst_blockid,
+                   dst_port,
+                   edge,
+                   property_propagation_active)
+               == std::tie(rhs.src_blockid,
+                      rhs.src_port,
+                      rhs.dst_blockid,
+                      rhs.dst_port,
+                      rhs.edge,
+                      rhs.property_propagation_active);
+    }
+};
+
+
+namespace detail {
+
+//! Container for the logical graph within an uhd::rfnoc_graph
+class graph_t
+{
+public:
+    using uptr = std::unique_ptr<graph_t>;
+    //! A shorthand for a pointer to a node
+    using node_ref_t = uhd::rfnoc::node_t*;
+
+    using graph_edge_t = uhd::rfnoc::graph_edge_t;
+
+    /*! Add a connection to the graph
+     *
+     * After this function returns, the nodes will be considered connected
+     * along the ports specified in \p edge_info.
+     *
+     * \param src_node A reference to the source node
+     * \param dst_node A reference to the destination node
+     * \param edge_info Information about the type of edge
+     */
+    void connect(node_ref_t src_node, node_ref_t dst_node, graph_edge_t edge_info);
+
+    //void disconnect(node_ref_t src_node,
+        //node_ref_t dst_node,
+        //const size_t src_port,
+        //const size_t dst_port);
+        //
+
+    /*! Run initial checks for graph
+     *
+     * This method can be called anytime, but it's intended to be called when
+     * the graph has been committed. It will run checks on the graph and run a
+     * property propagation.
+     *
+     * \throws uhd::resolve_error if the properties fail to resolve.
+     */
+    void initialize();
+
+
+private:
+    friend class graph_accessor_t;
+
+    /**************************************************************************
+     * Graph-related types
+     *************************************************************************/
+    // Naming conventions:
+    // - 'vertex' and 'node' are generally ambiguous in a graph context, but
+    //   we'll use vertex for BGL related items, and node for RFNoC nodes
+    // - We may use CamelCase occasionally if it fits the BGL examples and/or
+    //   reference designs, in case someone needs to learn BGL to understand
+    //   this code
+
+    struct vertex_property_t
+    {
+        enum { num = 4000 };
+        typedef boost::vertex_property_tag kind;
+    };
+    using RfnocVertexProperty = boost::property<vertex_property_t, node_ref_t>;
+
+    struct edge_property_t
+    {
+        enum { num = 4001 };
+        typedef boost::edge_property_tag kind;
+    };
+    using RfnocEdgeProperty = boost::property<edge_property_t, graph_edge_t>;
+
+    /*! The type of the BGL graph we're using
+     *
+     * - It is bidirectional because we need to access both in_edges and
+     *   out_edges
+     * - All container types are according to the BGL manual recommendations for
+     *   this kind of graph
+     */
+    using rfnoc_graph_t = boost::adjacency_list<boost::vecS,
+        boost::vecS,
+        boost::bidirectionalS,
+        RfnocVertexProperty,
+        RfnocEdgeProperty>;
+
+    using vertex_list_t = std::list<rfnoc_graph_t::vertex_descriptor>;
+
+    template <bool forward_edges_only = true>
+    struct ForwardBackwardEdgePredicate
+    {
+        ForwardBackwardEdgePredicate() {} // Default ctor is required
+        ForwardBackwardEdgePredicate(rfnoc_graph_t& graph) : _graph(&graph) {}
+
+        template <typename Edge>
+        bool operator()(const Edge& e) const
+        {
+            graph_edge_t edge_info = boost::get(edge_property_t(), *_graph, e);
+            return edge_info.property_propagation_active == forward_edges_only;
+        }
+
+    private:
+        // Don't make any attribute const, because default assignment operator
+        // is also required
+        rfnoc_graph_t* _graph;
+    };
+
+    using ForwardEdgePredicate = ForwardBackwardEdgePredicate<true>;
+    using BackEdgePredicate = ForwardBackwardEdgePredicate<false>;
+
+    //! Vertex predicate, only selects nodes with dirty props
+    struct DirtyNodePredicate;
+
+    //! Vertex predicate, returns specific existing nodes
+    struct FindNodePredicate;
+
+    /**************************************************************************
+     * Other private types
+     *************************************************************************/
+    using node_map_t = std::map<node_ref_t, rfnoc_graph_t::vertex_descriptor>;
+
+    /**************************************************************************
+     * The Algorithm
+     *************************************************************************/
+    /*! Implementation of the property propagation algorithm
+     */
+    void resolve_all_properties();
+
+    /**************************************************************************
+     * Private graph helpers
+     *************************************************************************/
+    template <typename VertexContainerType>
+    std::vector<node_ref_t> _vertices_to_nodes(VertexContainerType&& vertex_container)
+    {
+        std::vector<node_ref_t> result{};
+        result.reserve(vertex_container.size());
+        for (const auto& vertex_descriptor : vertex_container) {
+            result.push_back(boost::get(vertex_property_t(), _graph, vertex_descriptor));
+        }
+        return result;
+    }
+
+    /*! Returns a list of all nodes that have dirty properties.
+     */
+    vertex_list_t _find_dirty_nodes();
+
+    /*! Returns nodes in topologically sorted order
+     *
+     *
+     * \throws uhd::runtime_error if the graph was not sortable
+     */
+    vertex_list_t _get_topo_sorted_nodes();
+
+    /*! Add a node, but only if it's not already in the graph.
+     *
+     * If it's already there, do nothing.
+     */
+    void _add_node(node_ref_t node);
+
+    /*! Find the neighbouring node for \p origin based on \p port_info
+     *
+     * This function will check port_info to identify the port number and the
+     * direction (input or output) from \p port_info. It will then return a
+     * reference to the node that is attached to the node \p origin if such a
+     * node exists, and the edge info.
+     *
+     * If port_info.type == res_source_info::INPUT_EDGE, then port_info.instance
+     * will equal the return value's dst_port value.
+     *
+     * \returns A valid reference to the neighbouring node, or nullptr if no
+     *          such node exists, and the corresponding edge info.
+     */
+    std::pair<node_ref_t, graph_edge_t> _find_neighbour(
+        rfnoc_graph_t::vertex_descriptor origin, res_source_info port_info);
+
+    /*! Forward all edge properties from this node (\p origin) to the
+     * neighbouring ones
+     *
+     */
+    void _forward_edge_props(rfnoc_graph_t::vertex_descriptor origin);
+
+    /*! Check that the edge properties on both sides of the edge are equal
+     *
+     * \returns false if edge properties are not consistent
+     */
+    bool _assert_edge_props_consistent(rfnoc_graph_t::edge_descriptor edge);
+
+    /**************************************************************************
+     * Attributes
+     *************************************************************************/
+    //! Storage for the actual graph
+    rfnoc_graph_t _graph;
+
+    //! Map to do a lookup node_ref_t -> vertex descriptor.
+    //
+    // This is technically redundant, but helps us check quickly and easily if
+    // a node is already in the graph, and to yank out the appropriate node
+    // descriptor without having to traverse the graph. The rfnoc_graph_t is not
+    // efficient for lookups of vertices.
+    node_map_t _node_map;
+};
+
+
+}}} /* namespace uhd::rfnoc::detail */
+
+#endif /* INCLUDED_LIBUHD_GRAPH_HPP */
diff --git a/host/lib/include/uhdlib/rfnoc/node_accessor.hpp b/host/lib/include/uhdlib/rfnoc/node_accessor.hpp
index 26e6a5607..554cc8f4f 100644
--- a/host/lib/include/uhdlib/rfnoc/node_accessor.hpp
+++ b/host/lib/include/uhdlib/rfnoc/node_accessor.hpp
@@ -72,9 +72,10 @@ public:
      *
      * See node_t::forward_edge_property() for details.
      */
-    void forward_edge_property(node_t* dst_node, property_base_t* incoming_prop)
+    void forward_edge_property(
+        node_t* dst_node, const size_t dst_port, property_base_t* incoming_prop)
     {
-        dst_node->forward_edge_property(incoming_prop);
+        dst_node->forward_edge_property(incoming_prop, dst_port);
     }
 };