Line data    Source code

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