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        8198 : IFMapDependencyTracker::IFMapDependencyTracker(
      18        8198 :     DB *db, DBGraph *graph, ChangeObserver observer)
      19        8198 :         : database_(db), graph_(graph), observer_(observer) {
      20        8198 : }
      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      197667 : void IFMapDependencyTracker::NodeEvent(IFMapNode *node, bool add_node_event) {
      30      197667 :     if (add_node_event)
      31      192036 :         AddChangeEvent(node);
      32      197667 :     if (IsInterestingEvent(node, "self")) {
      33      146195 :         node_list_.push_back(
      34      292390 :             make_pair(node->table()->Typename(), node->name()));
      35             :     }
      36      197667 : }
      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      192036 : void IFMapDependencyTracker::NodeEvent(IFMapNode *node) {
      46      192036 :     NodeEvent(node, true);
      47      192036 : }
      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      253769 : bool IFMapDependencyTracker::LinkEvent(const string metadata,
      56             :     IFMapNode *left, IFMapNode *right) {
      57      253769 :     bool interest = false;
      58             : 
      59      253769 :     if ((left != NULL) && IsInterestingEvent(left, metadata)) {
      60      110032 :         const char *type_left = left->table()->Typename();
      61      110032 :         edge_list_.push_back(
      62      220064 :             EdgeDescriptor(metadata, type_left, left->name()));
      63      110032 :         interest = true;
      64             :     }
      65      253769 :     if ((right != NULL) && IsInterestingEvent(right, metadata)) {
      66       78338 :         const char *type_right = right->table()->Typename();
      67       78338 :         edge_list_.push_back(
      68      156676 :             EdgeDescriptor(metadata, type_right, right->name()));
      69       78338 :         interest = true;
      70             :     }
      71             : 
      72      253769 :     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       70095 : void IFMapDependencyTracker::PropagateChanges() {
      81       70095 :     InEdgeSet in_edges;
      82             : 
      83       70095 :     for (NodeList::iterator iter = node_list_.begin();
      84      216290 :          iter != node_list_.end(); ++iter) {
      85             :         IFMapTable *table =
      86      146195 :             IFMapTable::FindTable(database_, iter->first);
      87      146195 :         if (table == NULL) {
      88           0 :             continue;
      89             :         }
      90      146195 :         IFMapNode *node = table->FindNode(iter->second);
      91      146195 :         if ((node == NULL) || node->IsDeleted()) {
      92           4 :             continue;
      93             :         }
      94      146191 :         PropagateNode(node, &in_edges);
      95             :     }
      96             : 
      97       70095 :     for (EdgeDescriptorList::iterator iter = edge_list_.begin();
      98      258465 :          iter != edge_list_.end(); ++iter) {
      99      188370 :         const EdgeDescriptor &edge = *iter;
     100             :         IFMapTable *table =
     101      188370 :             IFMapTable::FindTable(database_, edge.id_type);
     102      188370 :         if (table == NULL) {
     103           0 :             continue;
     104             :         }
     105      188370 :         IFMapNode *node = table->FindNode(edge.id_name);
     106      188370 :         if ((node == NULL) || node->IsDeleted()) {
     107           3 :             continue;
     108             :         }
     109      188367 :         PropagateEdge(node, edge.metadata, &in_edges);
     110             :     }
     111       70095 : }
     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       70095 : void IFMapDependencyTracker::Clear() {
     119       70095 :     node_list_.clear();
     120       70095 :     edge_list_.clear();
     121       70095 : }
     122             : 
     123             : //
     124             : // Get the PropagateList for the given identifier type and metadata.
     125             : //
     126             : const IFMapDependencyTracker::PropagateList *
     127     1069755 : IFMapDependencyTracker::GetPropagateList(
     128             :     const string &type, const string &metadata) const {
     129             : 
     130     1069755 :     NodeEventPolicy::const_iterator ploc = policy_.find(type);
     131     1069755 :     if (ploc == policy_.end()) {
     132      159317 :         return NULL;
     133             :     }
     134      910438 :     ReactionMap::const_iterator rloc = ploc->second.find(metadata);
     135      910438 :     if (rloc == ploc->second.end()) {
     136       67257 :         return NULL;
     137             :     }
     138      843181 :     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      664739 : bool IFMapDependencyTracker::IsInterestingEvent(
     147             :     const IFMapNode *node, const string &metadata) const {
     148      664739 :     if (node->IsDeleted()) {
     149      103600 :         return false;
     150             :     }
     151      561139 :     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      146191 : void IFMapDependencyTracker::PropagateNode(
     160             :     IFMapNode *node, InEdgeSet *in_edges) {
     161             : 
     162             :     const PropagateList *plist =
     163      146191 :         GetPropagateList(node->table()->Typename(), "self");
     164      146191 :     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      146191 :     for (DBGraphVertex::edge_iterator iter =
     169      146191 :          node->edge_list_begin(graph_);
     170      358850 :          iter != node->edge_list_end(graph_); ++iter) {
     171      212659 :         IFMapLink *link = static_cast<IFMapLink *>(iter.operator->());
     172      212659 :         IFMapNode *target = static_cast<IFMapNode *>(iter.target());
     173      212659 :         if (plist->find(link->metadata()) == plist->end()) {
     174      118129 :             continue;
     175             :         }
     176       94530 :         PropagateEdge(target, link->metadata(), in_edges);
     177             :     }
     178      146191 : }
     179             : 
     180             : //
     181             : // Propagate changes for an edge on the EdgeDescriptorList.
     182             : //
     183      362425 : void IFMapDependencyTracker::PropagateEdge(
     184             :     IFMapNode *node, const string &metadata, InEdgeSet *in_edges) {
     185      362425 :     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      362425 :         GetPropagateList(node->table()->Typename(), metadata);
     191      362425 :     assert(plist);
     192             : 
     193             :     // Skip if this edge in already in the InEdgeSet i.e. it's a duplicate.
     194      362425 :     if (in_edges->count(make_pair(node, metadata)) > 0) {
     195      144043 :         return;
     196             :     }
     197             : 
     198             :     // Add entry to InEdgeSet for loop prevention.
     199      218382 :     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      218382 :     PropagateList::const_iterator self = plist->find("self");
     204      218382 :     if (self != plist->end()) {
     205      144760 :         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      218382 :     for (DBGraphVertex::edge_iterator iter =
     211      218382 :          node->edge_list_begin(graph_);
     212     1112941 :          iter != node->edge_list_end(graph_); ++iter) {
     213      894559 :         IFMapLink *link = static_cast<IFMapLink *>(iter.operator->());
     214      894559 :         if (plist->find(link->metadata()) == plist->end()) {
     215      815031 :             continue;
     216             :         }
     217       79528 :         IFMapNode *target = static_cast<IFMapNode *>(iter.target());
     218       79528 :         PropagateEdge(target, link->metadata(), in_edges);
     219             :     }
     220             : }
     221             : 
     222             : //
     223             : // Add the IFMapNode to the change list.
     224             : //
     225      336796 : void IFMapDependencyTracker::AddChangeEvent(IFMapNode *node) {
     226      336796 :     observer_(node);
     227      336796 : }
     228             :