Line data    Source code

       1             : /*
       2             :  * Copyright (c) 2013 Juniper Networks, Inc. All rights reserved.
       3             :  * Copyright Contributors to the OpenSDN project
       4             :  */
       5             : #ifndef IFMAP_IFMAP_DEPENDENCY_TRACKER_H__
       6             : #define IFMAP_IFMAP_DEPENDENCY_TRACKER_H__
       7             : 
       8             : #include <list>
       9             : #include <map>
      10             : #include <set>
      11             : #include <string>
      12             : #include <vector>
      13             : 
      14             : #include <boost/function.hpp>
      15             : 
      16             : class DB;
      17             : class DBGraph;
      18             : class IFMapNode;
      19             : 
      20             : //
      21             : // The DependencyTracker recursively evaluates dependencies as specified via a
      22             : // policy and pushes additional ConfigDeltas to the ChangeList.  This takes
      23             : // the burden of dependency tracking away from the consumers and automates it
      24             : // instead of being individually hand coded for each type of object.
      25             : //
      26             : // Elements are added onto the change list when they need to be reevaluated as
      27             : // a result of add/delete/change of other nodes and/or edges in the graph. The
      28             : // change list list is ultimately processed by the client
      29             : // (e.g. BgpConfigManager).
      30             : //
      31             : // The NodeEventPolicy is defined as a list of identifier types and associated
      32             : // ReactionMaps.
      33             : //
      34             : // A ReactionMap in turn is a mapping from a metadata type to a PropagateList,
      35             : // with the semantics that an add or delete of a edge of that type triggers a
      36             : // propagation across all edges with a type in the PropagateList. The keyword
      37             : // self is used instead of a metadata type to denote that the trigger is any
      38             : // change in the properties of the node itself. Note that the type of the node
      39             : // will always be the identifier type with which the ReactionMap is associated.
      40             : //
      41             : // A PropagateList is list of metadata types that need to be processed when
      42             : // propagating a change for a node or edge. They keyword self is used in this
      43             : // list to denote that the node associated with the edge should itself also be
      44             : // put on the ChangeList.
      45             : //
      46             : // The DependencyTracker is notified of Node and Link events by the listener.
      47             : // A Node event is considered interesting i.e. worthy of further propagation,
      48             : // if there's an entry for self in the ReactionMap for the identifier type.
      49             : //
      50             : // A Link is broken broken down into 2 unidirectional Edges.  An Edge consists
      51             : // of a Node and the associated metadata for the Link.  An Edge is considered
      52             : // interesting if there's an entry for the metadata in the ReactionMap for the
      53             : // Node's identifier type.
      54             : //
      55             : // A list of interesting Nodes and Edges is constructed based on Node and Link
      56             : // events as described above. Eventually, the DependencyTracker evaluates all
      57             : // the Nodes and Edges and recursively applies the NodeEventPolicy and builds
      58             : // up the change list of Nodes that needs to be processed by the client
      59             : // (e.g. BgpConfigManager).
      60             : // When applying the PropagateList, if the keyword self is present in the list
      61             : // the Node itself is added to the change list.  In any case, the rest of the
      62             : // metadata elements in the list are used to further propagate the changes.
      63             : //
      64             : // The NodeList and EdgeDescriptorList are both maintained using string names
      65             : // for the id type, id name and metadata.  Thus the DependencyTracker doesn't
      66             : // take any references on the IFMapNode objects. If an IFMapNode gets deleted
      67             : // before the changes in the NodeList and EdgeDescriptorList are propagated,
      68             : // we simply ignore the relevant nodes and edges when propagating the changes.
      69             : //
      70             : // Node and Link events are processed in the context of the db::DBTable task.
      71             : // The propagation of the NodeList and EdgeDescriptorList happens in context
      72             : // of the client task (e.g. bgp::Config) when the its requesst the ChangeList.
      73             : //
      74             : // CONCURRENCY: Not thread-safe. The class assumes that the caller ensures
      75             : // that only a single method can run at a time.
      76             : //
      77             : class IFMapDependencyTracker {
      78             : public:
      79             :     struct EdgeDescriptor {
      80      190288 :         EdgeDescriptor(const std::string &meta, const std::string &type,
      81             :             const std::string &name)
      82      190288 :             : metadata(meta), id_type(type), id_name(name) {
      83      190288 :         }
      84             :         std::string metadata;
      85             :         std::string id_type;
      86             :         std::string id_name;
      87             :     };
      88             :     typedef std::list<EdgeDescriptor> EdgeDescriptorList;
      89             :     typedef std::list<std::pair<std::string, std::string> > NodeList;
      90             : 
      91             :     // identifier type -> (incoming metadata, outgoing metadata list)
      92             :     typedef std::set<std::string> PropagateList;
      93             :     typedef std::map<std::string, PropagateList> ReactionMap;
      94             :     typedef std::map<std::string, ReactionMap> NodeEventPolicy;
      95             : 
      96             :     typedef boost::function<void(IFMapNode *node)> ChangeObserver;
      97             :     IFMapDependencyTracker(DB *db, DBGraph *graph, ChangeObserver observer);
      98             : 
      99       16184 :     NodeEventPolicy *policy_map() { return &policy_; }
     100             : 
     101             :     void NodeEvent(IFMapNode *node);
     102             :     void NodeEvent(IFMapNode *node, bool add_node_event);
     103             :     bool LinkEvent(const std::string metadata,
     104             :         IFMapNode *left, IFMapNode *right);
     105             :     void PropagateChanges();
     106             :     void Clear();
     107             : 
     108         108 :     const NodeList &node_list() const { return node_list_; }
     109         114 :     const EdgeDescriptorList& edge_list() const { return edge_list_; }
     110             : 
     111             : private:
     112             :     typedef std::set<std::pair<IFMapNode *, std::string> > InEdgeSet;
     113             : 
     114             :     const PropagateList *GetPropagateList(const std::string &type,
     115             :         const std::string &metadata) const;
     116             :     bool IsInterestingEvent(const IFMapNode *node,
     117             :         const std::string &metadata) const;
     118             : 
     119             :     void PropagateNode(IFMapNode *node, InEdgeSet *in_edges);
     120             :     void PropagateEdge(IFMapNode *node, const std::string &metadata,
     121             :         InEdgeSet *in_edges);
     122             :     void AddChangeEvent(IFMapNode *node);
     123             : 
     124             :     DB *database_;
     125             :     DBGraph *graph_;
     126             :     ChangeObserver observer_;
     127             :     NodeEventPolicy policy_;
     128             :     EdgeDescriptorList edge_list_;
     129             :     NodeList node_list_;
     130             : };
     131             : 
     132             : #endif