Line data    Source code

       1             : /*
       2             :  * Copyright (c) 2013 Juniper Networks, Inc. All rights reserved.
       3             :  */
       4             : 
       5             : #include "ifmap/ifmap_dependency_tracker.h"
       6             : 
       7             : #include <sstream>
       8             : #include <boost/assign/list_of.hpp>
       9             : 
      10             : #include "ifmap/ifmap_link.h"
      11             : #include "ifmap/ifmap_node.h"
      12             : #include "ifmap/ifmap_table.h"
      13             : 
      14             : using namespace boost::assign;
      15             : using namespace std;
      16             : 
      17        8197 : IFMapDependencyTracker::IFMapDependencyTracker(
      18        8197 :     DB *db, DBGraph *graph, ChangeObserver observer)
      19        8197 :         : database_(db), graph_(graph), observer_(observer) {
      20        8197 : }
      21             : 
      22             : //
      23             : // Add an IFMapNode to the NodeList for further propagation if it's an
      24             : // interesting node. It's interesting if there's an entry for self in the
      25             : // ReactionMap.
      26             : //
      27             : // Node event is added based on "add_node_event" flag
      28             : //
      29      196251 : void IFMapDependencyTracker::NodeEvent(IFMapNode *node, bool add_node_event) {
      30      196251 :     if (add_node_event)
      31      190636 :         AddChangeEvent(node);
      32      196251 :     if (IsInterestingEvent(node, "self")) {
      33      145679 :         node_list_.push_back(
      34      291358 :             make_pair(node->table()->Typename(), node->name()));
      35             :     }
      36      196251 : }
      37             : 
      38             : //
      39             : // Add an IFMapNode to the NodeList for further propagation if it's an
      40             : // interesting node. It's interesting if there's an entry for self in the
      41             : // ReactionMap.
      42             : //
      43             : // The node is always added to the ChangeList even if it's not interesting.
      44             : //
      45      190636 : void IFMapDependencyTracker::NodeEvent(IFMapNode *node) {
      46      190636 :     NodeEvent(node, true);
      47      190636 : }
      48             : 
      49             : //
      50             : // Check both the edges corresponding to the IFMapLink and add them to the
      51             : // EdgeDescriptorList if interesting. An edge is considered interesting if
      52             : // there's an entry for the metadata in the ReactionMap for the IFMapNode's
      53             : // identifier type.
      54             : //
      55      251708 : bool IFMapDependencyTracker::LinkEvent(const string metadata,
      56             :     IFMapNode *left, IFMapNode *right) {
      57      251708 :     bool interest = false;
      58             : 
      59      251708 :     if ((left != NULL) && IsInterestingEvent(left, metadata)) {
      60      108356 :         const char *type_left = left->table()->Typename();
      61      108356 :         edge_list_.push_back(
      62      216712 :             EdgeDescriptor(metadata, type_left, left->name()));
      63      108356 :         interest = true;
      64             :     }
      65      251708 :     if ((right != NULL) && IsInterestingEvent(right, metadata)) {
      66       76804 :         const char *type_right = right->table()->Typename();
      67       76804 :         edge_list_.push_back(
      68      153608 :             EdgeDescriptor(metadata, type_right, right->name()));
      69       76804 :         interest = true;
      70             :     }
      71             : 
      72      251708 :     return interest;
      73             : }
      74             : 
      75             : //
      76             : // Walk the NodeList and EdgeDescriptorList and evaluate the NodeEventPolicy
      77             : // to build up the change list. The InEdgeSet is used to avoid evaluating the
      78             : // same EdgeDescriptor more than once, hence avoiding any loops in the graph.
      79             : //
      80       69345 : void IFMapDependencyTracker::PropagateChanges() {
      81       69345 :     InEdgeSet in_edges;
      82             : 
      83       69345 :     for (NodeList::iterator iter = node_list_.begin();
      84      215024 :          iter != node_list_.end(); ++iter) {
      85             :         IFMapTable *table =
      86      145679 :             IFMapTable::FindTable(database_, iter->first);
      87      145679 :         if (table == NULL) {
      88           0 :             continue;
      89             :         }
      90      145679 :         IFMapNode *node = table->FindNode(iter->second);
      91      145679 :         if ((node == NULL) || node->IsDeleted()) {
      92           3 :             continue;
      93             :         }
      94      145676 :         PropagateNode(node, &in_edges);
      95             :     }
      96             : 
      97       69345 :     for (EdgeDescriptorList::iterator iter = edge_list_.begin();
      98      254505 :          iter != edge_list_.end(); ++iter) {
      99      185160 :         const EdgeDescriptor &edge = *iter;
     100             :         IFMapTable *table =
     101      185160 :             IFMapTable::FindTable(database_, edge.id_type);
     102      185160 :         if (table == NULL) {
     103           0 :             continue;
     104             :         }
     105      185160 :         IFMapNode *node = table->FindNode(edge.id_name);
     106      185160 :         if ((node == NULL) || node->IsDeleted()) {
     107           3 :             continue;
     108             :         }
     109      185157 :         PropagateEdge(node, edge.metadata, &in_edges);
     110             :     }
     111       69345 : }
     112             : 
     113             : //
     114             : // Clear all intermediate state used during propagation. This is called after
     115             : // we're done propagating all accumulated node and edge triggers to the change
     116             : // list.
     117             : //
     118       69345 : void IFMapDependencyTracker::Clear() {
     119       69345 :     node_list_.clear();
     120       69345 :     edge_list_.clear();
     121       69345 : }
     122             : 
     123             : //
     124             : // Get the PropagateList for the given identifier type and metadata.
     125             : //
     126             : const IFMapDependencyTracker::PropagateList *
     127     1051960 : IFMapDependencyTracker::GetPropagateList(
     128             :     const string &type, const string &metadata) const {
     129             : 
     130     1051960 :     NodeEventPolicy::const_iterator ploc = policy_.find(type);
     131     1051960 :     if (ploc == policy_.end()) {
     132      159324 :         return NULL;
     133             :     }
     134      892636 :     ReactionMap::const_iterator rloc = ploc->second.find(metadata);
     135      892636 :     if (rloc == ploc->second.end()) {
     136       66806 :         return NULL;
     137             :     }
     138      825830 :     return &rloc->second;
     139             : }
     140             : 
     141             : //
     142             : // Determine if the event specified by the node and metadata is interesting.
     143             : // It's interesting if the NodeEventPolicy has non-empty propagate list for
     144             : // the event.
     145             : //
     146      659265 : bool IFMapDependencyTracker::IsInterestingEvent(
     147             :     const IFMapNode *node, const string &metadata) const {
     148      659265 :     if (node->IsDeleted()) {
     149      102296 :         return false;
     150             :     }
     151      556969 :     return GetPropagateList(node->table()->Typename(), metadata) != NULL;
     152             : }
     153             : 
     154             : //
     155             : // Propagate changes for a IFMapNode on the NodeList.  The fact that it's on
     156             : // the NodeList means that the node must have been deemed interesting and so
     157             : // it's PropagateList must be non-empty.
     158             : //
     159      145676 : void IFMapDependencyTracker::PropagateNode(
     160             :     IFMapNode *node, InEdgeSet *in_edges) {
     161             : 
     162             :     const PropagateList *plist =
     163      145676 :         GetPropagateList(node->table()->Typename(), "self");
     164      145676 :     assert(plist);
     165             : 
     166             :     // Iterate through the edges of node. If the metadata for an edge is in
     167             :     // the PropagateList, we need to propagate changes for the edge itself.
     168      145676 :     for (DBGraphVertex::edge_iterator iter =
     169      145676 :          node->edge_list_begin(graph_);
     170      354583 :          iter != node->edge_list_end(graph_); ++iter) {
     171      208907 :         IFMapLink *link = static_cast<IFMapLink *>(iter.operator->());
     172      208907 :         IFMapNode *target = static_cast<IFMapNode *>(iter.target());
     173      208907 :         if (plist->find(link->metadata()) == plist->end()) {
     174      119292 :             continue;
     175             :         }
     176       89615 :         PropagateEdge(target, link->metadata(), in_edges);
     177             :     }
     178      145676 : }
     179             : 
     180             : //
     181             : // Propagate changes for an edge on the EdgeDescriptorList.
     182             : //
     183      349315 : void IFMapDependencyTracker::PropagateEdge(
     184             :     IFMapNode *node, const string &metadata, InEdgeSet *in_edges) {
     185      349315 :     assert(!node->IsDeleted());
     186             : 
     187             :     // Make a bidirectional check i.e. policy terms that apply to the two
     188             :     // edges for a link must be symmetrical.
     189             :     const PropagateList *plist =
     190      349315 :         GetPropagateList(node->table()->Typename(), metadata);
     191      349315 :     assert(plist);
     192             : 
     193             :     // Skip if this edge in already in the InEdgeSet i.e. it's a duplicate.
     194      349315 :     if (in_edges->count(make_pair(node, metadata)) > 0) {
     195      137890 :         return;
     196             :     }
     197             : 
     198             :     // Add entry to InEdgeSet for loop prevention.
     199      211425 :     in_edges->insert(make_pair(node, metadata));
     200             : 
     201             :     // Add the node corresponding to this edge to the change list if there's
     202             :     // an entry for self in the PropagateList.
     203      211425 :     PropagateList::const_iterator self = plist->find("self");
     204      211425 :     if (self != plist->end()) {
     205      141199 :         AddChangeEvent(node);
     206             :     }
     207             : 
     208             :     // Iterate through the edges of node. If the metadata for an edge is in
     209             :     // the PropagateList, we need to propagate changes for the edge itself.
     210      211425 :     for (DBGraphVertex::edge_iterator iter =
     211      211425 :          node->edge_list_begin(graph_);
     212     1084873 :          iter != node->edge_list_end(graph_); ++iter) {
     213      873448 :         IFMapLink *link = static_cast<IFMapLink *>(iter.operator->());
     214      873448 :         if (plist->find(link->metadata()) == plist->end()) {
     215      798905 :             continue;
     216             :         }
     217       74543 :         IFMapNode *target = static_cast<IFMapNode *>(iter.target());
     218       74543 :         PropagateEdge(target, link->metadata(), in_edges);
     219             :     }
     220             : }
     221             : 
     222             : //
     223             : // Add the IFMapNode to the change list.
     224             : //
     225      331835 : void IFMapDependencyTracker::AddChangeEvent(IFMapNode *node) {
     226      331835 :     observer_(node);
     227      331835 : }
     228             :