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 199518 : void IFMapDependencyTracker::NodeEvent(IFMapNode *node, bool add_node_event) { 31 199518 : if (add_node_event) 32 193662 : AddChangeEvent(node); 33 199518 : if (IsInterestingEvent(node, "self")) { 34 147344 : node_list_.push_back( 35 294688 : make_pair(node->table()->Typename(), node->name())); 36 : } 37 199518 : } 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 193662 : void IFMapDependencyTracker::NodeEvent(IFMapNode *node) { 47 193662 : NodeEvent(node, true); 48 193662 : } 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 255633 : bool IFMapDependencyTracker::LinkEvent(const string metadata, 57 : IFMapNode *left, IFMapNode *right) { 58 255633 : bool interest = false; 59 : 60 255633 : if ((left != NULL) && IsInterestingEvent(left, metadata)) { 61 110749 : const char *type_left = left->table()->Typename(); 62 110749 : edge_list_.push_back( 63 221498 : EdgeDescriptor(metadata, type_left, left->name())); 64 110749 : interest = true; 65 : } 66 255633 : if ((right != NULL) && IsInterestingEvent(right, metadata)) { 67 79010 : const char *type_right = right->table()->Typename(); 68 79010 : edge_list_.push_back( 69 158020 : EdgeDescriptor(metadata, type_right, right->name())); 70 79010 : interest = true; 71 : } 72 : 73 255633 : 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 71443 : void IFMapDependencyTracker::PropagateChanges() { 82 71443 : InEdgeSet in_edges; 83 : 84 71443 : for (NodeList::iterator iter = node_list_.begin(); 85 218787 : iter != node_list_.end(); ++iter) { 86 : IFMapTable *table = 87 147344 : IFMapTable::FindTable(database_, iter->first); 88 147344 : if (table == NULL) { 89 0 : continue; 90 : } 91 147344 : IFMapNode *node = table->FindNode(iter->second); 92 147344 : if ((node == NULL) || node->IsDeleted()) { 93 4 : continue; 94 : } 95 147340 : PropagateNode(node, &in_edges); 96 : } 97 : 98 71443 : for (EdgeDescriptorList::iterator iter = edge_list_.begin(); 99 261202 : iter != edge_list_.end(); ++iter) { 100 189759 : const EdgeDescriptor &edge = *iter; 101 : IFMapTable *table = 102 189759 : IFMapTable::FindTable(database_, edge.id_type); 103 189759 : if (table == NULL) { 104 0 : continue; 105 : } 106 189759 : IFMapNode *node = table->FindNode(edge.id_name); 107 189759 : if ((node == NULL) || node->IsDeleted()) { 108 3 : continue; 109 : } 110 189756 : PropagateEdge(node, edge.metadata, &in_edges); 111 : } 112 71443 : } 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 71443 : void IFMapDependencyTracker::Clear() { 120 71443 : node_list_.clear(); 121 71443 : edge_list_.clear(); 122 71443 : } 123 : 124 : // 125 : // Get the PropagateList for the given identifier type and metadata. 126 : // 127 : const IFMapDependencyTracker::PropagateList * 128 1074376 : IFMapDependencyTracker::GetPropagateList( 129 : const string &type, const string &metadata) const { 130 : 131 1074376 : NodeEventPolicy::const_iterator ploc = policy_.find(type); 132 1074376 : if (ploc == policy_.end()) { 133 159334 : return NULL; 134 : } 135 915042 : ReactionMap::const_iterator rloc = ploc->second.find(metadata); 136 915042 : if (rloc == ploc->second.end()) { 137 68389 : return NULL; 138 : } 139 846653 : 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 670308 : bool IFMapDependencyTracker::IsInterestingEvent( 148 : const IFMapNode *node, const string &metadata) const { 149 670308 : if (node->IsDeleted()) { 150 105482 : return false; 151 : } 152 564826 : 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 147340 : void IFMapDependencyTracker::PropagateNode( 161 : IFMapNode *node, InEdgeSet *in_edges) { 162 : 163 : const PropagateList *plist = 164 147340 : GetPropagateList(node->table()->Typename(), "self"); 165 147340 : 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 147340 : for (DBGraphVertex::edge_iterator iter = 170 147340 : node->edge_list_begin(graph_); 171 359690 : iter != node->edge_list_end(graph_); ++iter) { 172 212350 : IFMapLink *link = static_cast<IFMapLink *>(iter.operator->()); 173 212350 : IFMapNode *target = static_cast<IFMapNode *>(iter.target()); 174 212350 : if (plist->find(link->metadata()) == plist->end()) { 175 118631 : continue; 176 : } 177 93719 : PropagateEdge(target, link->metadata(), in_edges); 178 : } 179 147340 : } 180 : 181 : // 182 : // Propagate changes for an edge on the EdgeDescriptorList. 183 : // 184 362210 : void IFMapDependencyTracker::PropagateEdge( 185 : IFMapNode *node, const string &metadata, InEdgeSet *in_edges) { 186 362210 : 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 362210 : GetPropagateList(node->table()->Typename(), metadata); 192 362210 : assert(plist); 193 : 194 : // Skip if this edge in already in the InEdgeSet i.e. it's a duplicate. 195 362210 : if (in_edges->count(make_pair(node, metadata)) > 0) { 196 143957 : return; 197 : } 198 : 199 : // Add entry to InEdgeSet for loop prevention. 200 218253 : 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 218253 : PropagateList::const_iterator self = plist->find("self"); 205 218253 : if (self != plist->end()) { 206 144613 : 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 218253 : for (DBGraphVertex::edge_iterator iter = 212 218253 : node->edge_list_begin(graph_); 213 1109083 : iter != node->edge_list_end(graph_); ++iter) { 214 890830 : IFMapLink *link = static_cast<IFMapLink *>(iter.operator->()); 215 890830 : if (plist->find(link->metadata()) == plist->end()) { 216 812095 : continue; 217 : } 218 78735 : IFMapNode *target = static_cast<IFMapNode *>(iter.target()); 219 78735 : PropagateEdge(target, link->metadata(), in_edges); 220 : } 221 : } 222 : 223 : // 224 : // Add the IFMapNode to the change list. 225 : // 226 338275 : void IFMapDependencyTracker::AddChangeEvent(IFMapNode *node) { 227 338275 : observer_(node); 228 338275 : } 229 :