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        8199 : IFMapDependencyTracker::IFMapDependencyTracker(
      18        8199 :     DB *db, DBGraph *graph, ChangeObserver observer)
      19        8199 :         : database_(db), graph_(graph), observer_(observer) {
      20        8199 : }
      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      196562 : void IFMapDependencyTracker::NodeEvent(IFMapNode *node, bool add_node_event) {
      30      196562 :     if (add_node_event)
      31      190949 :         AddChangeEvent(node);
      32      196562 :     if (IsInterestingEvent(node, "self")) {
      33      145995 :         node_list_.push_back(
      34      291990 :             make_pair(node->table()->Typename(), node->name()));
      35             :     }
      36      196562 : }
      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      190949 : void IFMapDependencyTracker::NodeEvent(IFMapNode *node) {
      46      190949 :     NodeEvent(node, true);
      47      190949 : }
      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      251716 : bool IFMapDependencyTracker::LinkEvent(const string metadata,
      56             :     IFMapNode *left, IFMapNode *right) {
      57      251716 :     bool interest = false;
      58             : 
      59      251716 :     if ((left != NULL) && IsInterestingEvent(left, metadata)) {
      60      108284 :         const char *type_left = left->table()->Typename();
      61      108284 :         edge_list_.push_back(
      62      216568 :             EdgeDescriptor(metadata, type_left, left->name()));
      63      108284 :         interest = true;
      64             :     }
      65      251716 :     if ((right != NULL) && IsInterestingEvent(right, metadata)) {
      66       76794 :         const char *type_right = right->table()->Typename();
      67       76794 :         edge_list_.push_back(
      68      153588 :             EdgeDescriptor(metadata, type_right, right->name()));
      69       76794 :         interest = true;
      70             :     }
      71             : 
      72      251716 :     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       69347 : void IFMapDependencyTracker::PropagateChanges() {
      81       69347 :     InEdgeSet in_edges;
      82             : 
      83       69347 :     for (NodeList::iterator iter = node_list_.begin();
      84      215342 :          iter != node_list_.end(); ++iter) {
      85             :         IFMapTable *table =
      86      145995 :             IFMapTable::FindTable(database_, iter->first);
      87      145995 :         if (table == NULL) {
      88           0 :             continue;
      89             :         }
      90      145995 :         IFMapNode *node = table->FindNode(iter->second);
      91      145995 :         if ((node == NULL) || node->IsDeleted()) {
      92           6 :             continue;
      93             :         }
      94      145989 :         PropagateNode(node, &in_edges);
      95             :     }
      96             : 
      97       69347 :     for (EdgeDescriptorList::iterator iter = edge_list_.begin();
      98      254425 :          iter != edge_list_.end(); ++iter) {
      99      185078 :         const EdgeDescriptor &edge = *iter;
     100             :         IFMapTable *table =
     101      185078 :             IFMapTable::FindTable(database_, edge.id_type);
     102      185078 :         if (table == NULL) {
     103           0 :             continue;
     104             :         }
     105      185078 :         IFMapNode *node = table->FindNode(edge.id_name);
     106      185078 :         if ((node == NULL) || node->IsDeleted()) {
     107           3 :             continue;
     108             :         }
     109      185075 :         PropagateEdge(node, edge.metadata, &in_edges);
     110             :     }
     111       69347 : }
     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       69347 : void IFMapDependencyTracker::Clear() {
     119       69347 :     node_list_.clear();
     120       69347 :     edge_list_.clear();
     121       69347 : }
     122             : 
     123             : //
     124             : // Get the PropagateList for the given identifier type and metadata.
     125             : //
     126             : const IFMapDependencyTracker::PropagateList *
     127     1052279 : IFMapDependencyTracker::GetPropagateList(
     128             :     const string &type, const string &metadata) const {
     129             : 
     130     1052279 :     NodeEventPolicy::const_iterator ploc = policy_.find(type);
     131     1052279 :     if (ploc == policy_.end()) {
     132      159315 :         return NULL;
     133             :     }
     134      892964 :     ReactionMap::const_iterator rloc = ploc->second.find(metadata);
     135      892964 :     if (rloc == ploc->second.end()) {
     136       66810 :         return NULL;
     137             :     }
     138      826154 :     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      659551 : bool IFMapDependencyTracker::IsInterestingEvent(
     147             :     const IFMapNode *node, const string &metadata) const {
     148      659551 :     if (node->IsDeleted()) {
     149      102353 :         return false;
     150             :     }
     151      557198 :     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      145989 : void IFMapDependencyTracker::PropagateNode(
     160             :     IFMapNode *node, InEdgeSet *in_edges) {
     161             : 
     162             :     const PropagateList *plist =
     163      145989 :         GetPropagateList(node->table()->Typename(), "self");
     164      145989 :     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      145989 :     for (DBGraphVertex::edge_iterator iter =
     169      145989 :          node->edge_list_begin(graph_);
     170      355164 :          iter != node->edge_list_end(graph_); ++iter) {
     171      209175 :         IFMapLink *link = static_cast<IFMapLink *>(iter.operator->());
     172      209175 :         IFMapNode *target = static_cast<IFMapNode *>(iter.target());
     173      209175 :         if (plist->find(link->metadata()) == plist->end()) {
     174      119515 :             continue;
     175             :         }
     176       89660 :         PropagateEdge(target, link->metadata(), in_edges);
     177             :     }
     178      145989 : }
     179             : 
     180             : //
     181             : // Propagate changes for an edge on the EdgeDescriptorList.
     182             : //
     183      349092 : void IFMapDependencyTracker::PropagateEdge(
     184             :     IFMapNode *node, const string &metadata, InEdgeSet *in_edges) {
     185      349092 :     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      349092 :         GetPropagateList(node->table()->Typename(), metadata);
     191      349092 :     assert(plist);
     192             : 
     193             :     // Skip if this edge in already in the InEdgeSet i.e. it's a duplicate.
     194      349092 :     if (in_edges->count(make_pair(node, metadata)) > 0) {
     195      137736 :         return;
     196             :     }
     197             : 
     198             :     // Add entry to InEdgeSet for loop prevention.
     199      211356 :     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      211356 :     PropagateList::const_iterator self = plist->find("self");
     204      211356 :     if (self != plist->end()) {
     205      141226 :         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      211356 :     for (DBGraphVertex::edge_iterator iter =
     211      211356 :          node->edge_list_begin(graph_);
     212     1084506 :          iter != node->edge_list_end(graph_); ++iter) {
     213      873150 :         IFMapLink *link = static_cast<IFMapLink *>(iter.operator->());
     214      873150 :         if (plist->find(link->metadata()) == plist->end()) {
     215      798793 :             continue;
     216             :         }
     217       74357 :         IFMapNode *target = static_cast<IFMapNode *>(iter.target());
     218       74357 :         PropagateEdge(target, link->metadata(), in_edges);
     219             :     }
     220             : }
     221             : 
     222             : //
     223             : // Add the IFMapNode to the change list.
     224             : //
     225      332175 : void IFMapDependencyTracker::AddChangeEvent(IFMapNode *node) {
     226      332175 :     observer_(node);
     227      332175 : }
     228             :