Line data    Source code

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