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_graph_walker.h"
7 :
8 : #include "base/logging.h"
9 : #include "base/task_trigger.h"
10 : #include "db/db_graph.h"
11 : #include "db/db_table.h"
12 : #include "ifmap/ifmap_client.h"
13 : #include "ifmap/ifmap_exporter.h"
14 : #include "ifmap/ifmap_link.h"
15 : #include "ifmap/ifmap_log.h"
16 : #include "ifmap/ifmap_table.h"
17 : #include "ifmap/ifmap_server.h"
18 : #include "ifmap/ifmap_log_types.h"
19 : #include "ifmap/ifmap_update.h"
20 : #include "ifmap/ifmap_util.h"
21 : #include "schema/vnc_cfg_types.h"
22 :
23 : class GraphPropagateFilter : public DBGraph::VisitorFilter {
24 : public:
25 126 : GraphPropagateFilter(IFMapExporter *exporter,
26 : const IFMapTypenameWhiteList *type_filter,
27 : const BitSet &bitset)
28 252 : : exporter_(exporter),
29 126 : type_filter_(type_filter),
30 126 : bset_(bitset) {
31 126 : }
32 :
33 462 : bool VertexFilter(const DBGraphVertex *vertex) const {
34 462 : return type_filter_->VertexFilter(vertex);
35 : }
36 :
37 454 : bool EdgeFilter(const DBGraphVertex *source, const DBGraphVertex *target,
38 : const DBGraphEdge *edge) const {
39 454 : const IFMapNode *tgt = static_cast<const IFMapNode *>(target);
40 454 : const IFMapNodeState *state = NodeStateLookup(tgt);
41 454 : if (state != NULL && state->interest().Contains(bset_)) {
42 118 : return false;
43 : }
44 :
45 336 : return true;
46 : }
47 :
48 454 : const IFMapNodeState *NodeStateLookup(const IFMapNode *node) const {
49 454 : const DBTable *table = node->table();
50 : const DBState *state =
51 454 : node->GetState(table, exporter_->TableListenerId(table));
52 454 : return static_cast<const IFMapNodeState *>(state);
53 : }
54 :
55 462 : DBGraph::VisitorFilter::AllowedEdgeRetVal AllowedEdges(
56 : const DBGraphVertex *vertex) const {
57 462 : return type_filter_->AllowedEdges(vertex);
58 : }
59 : private:
60 : IFMapExporter *exporter_;
61 : const IFMapTypenameWhiteList *type_filter_;
62 : const BitSet &bset_;
63 : };
64 :
65 57 : IFMapGraphWalker::IFMapGraphWalker(DBGraph *graph, IFMapExporter *exporter)
66 57 : : graph_(graph),
67 57 : exporter_(exporter),
68 114 : link_delete_walk_trigger_(new TaskTrigger(
69 30 : [this](){ return LinkDeleteWalk(); },
70 114 : TaskScheduler::GetInstance()->GetTaskId("db::IFMapTable"), 0)),
71 57 : walk_client_index_(BitSet::npos) {
72 57 : traversal_white_list_.reset(new IFMapTypenameWhiteList());
73 57 : AddNodesToWhitelist();
74 57 : }
75 :
76 57 : IFMapGraphWalker::~IFMapGraphWalker() {
77 57 : }
78 :
79 454 : void IFMapGraphWalker::NotifyEdge(DBGraphEdge *edge, const BitSet &bset) {
80 454 : DBTable *table = exporter_->link_table();
81 454 : table->Change(edge);
82 454 : }
83 :
84 462 : void IFMapGraphWalker::JoinVertex(DBGraphVertex *vertex, const BitSet &bset) {
85 462 : IFMapNode *node = static_cast<IFMapNode *>(vertex);
86 462 : IFMapNodeState *state = exporter_->NodeStateLocate(node);
87 462 : IFMAP_DEBUG(JoinVertex, vertex->ToString(), state->interest().ToString(),
88 : bset.ToString());
89 462 : exporter_->StateInterestOr(state, bset);
90 462 : node->table()->Change(node);
91 462 : }
92 :
93 126 : void IFMapGraphWalker::ProcessLinkAdd(IFMapNode *lnode, IFMapNode *rnode,
94 : const BitSet &bset) {
95 126 : GraphPropagateFilter filter(exporter_, traversal_white_list_.get(), bset);
96 126 : graph_->Visit(rnode,
97 462 : [this, &bset](DBGraphVertex *v) { JoinVertex(v, bset); },
98 454 : [this, &bset](DBGraphEdge *e) { NotifyEdge(e, bset); },
99 : filter);
100 126 : }
101 :
102 208 : void IFMapGraphWalker::LinkAdd(IFMapLink *link, IFMapNode *lnode, const BitSet &lhs,
103 : IFMapNode *rnode, const BitSet &rhs) {
104 208 : IFMAP_DEBUG(LinkOper, "LinkAdd", lnode->ToString(), rnode->ToString(),
105 : lhs.ToString(), rhs.ToString());
106 :
107 : // Ensure that nodes are passed are indeed nodes and not links.
108 208 : assert(dynamic_cast<IFMapNode *>(lnode));
109 208 : assert(dynamic_cast<IFMapNode *>(rnode));
110 :
111 208 : assert(!dynamic_cast<IFMapLink *>(lnode));
112 208 : assert(!dynamic_cast<IFMapLink *>(rnode));
113 :
114 364 : if (!lhs.empty() && !rhs.Contains(lhs) &&
115 490 : traversal_white_list_->VertexFilter(rnode) &&
116 126 : traversal_white_list_->EdgeFilter(lnode, rnode, link)) {
117 126 : ProcessLinkAdd(lnode, rnode, lhs);
118 : }
119 416 : if (!rhs.empty() && !lhs.Contains(rhs) &&
120 502 : traversal_white_list_->VertexFilter(lnode) &&
121 86 : traversal_white_list_->EdgeFilter(rnode, lnode, link)) {
122 0 : ProcessLinkAdd(rnode, lnode, rhs);
123 : }
124 208 : }
125 :
126 55 : void IFMapGraphWalker::LinkRemove(const BitSet &bset) {
127 55 : OrLinkDeleteClients(bset); // link_delete_clients_ | bset
128 55 : link_delete_walk_trigger_->Set();
129 55 : }
130 :
131 : // Check if the neighbor or link to neighbor should be filtered. Returns true
132 : // if rnode or link to rnode should be filtered.
133 176 : bool IFMapGraphWalker::FilterNeighbor(IFMapNode *lnode, IFMapLink *link) {
134 176 : IFMapNode *rnode = link->left();
135 176 : if (rnode == lnode)
136 174 : rnode = link->right();
137 350 : if (!traversal_white_list_->VertexFilter(rnode) ||
138 174 : !traversal_white_list_->EdgeFilter(lnode, NULL, link)) {
139 2 : return true;
140 : }
141 174 : return false;
142 : }
143 :
144 12 : void IFMapGraphWalker::RecomputeInterest(DBGraphVertex *vertex, int bit) {
145 12 : IFMapNode *node = static_cast<IFMapNode *>(vertex);
146 12 : IFMapNodeState *state = exporter_->NodeStateLocate(node);
147 12 : state->nmask_set(bit);
148 12 : UpdateNewReachableNodesTracker(bit, state);
149 12 : }
150 :
151 30 : bool IFMapGraphWalker::LinkDeleteWalk() {
152 30 : if (link_delete_clients_.empty()) {
153 10 : walk_client_index_ = BitSet::npos;
154 10 : return true;
155 : }
156 :
157 20 : IFMapServer *server = exporter_->server();
158 : size_t i;
159 :
160 : // Get the index of the client we want to start with.
161 20 : if (walk_client_index_ == BitSet::npos) {
162 20 : i = link_delete_clients_.find_first();
163 : } else {
164 : // walk_client_index_ was the last client that we finished processing.
165 0 : i = link_delete_clients_.find_next(walk_client_index_);
166 : }
167 20 : int count = 0;
168 20 : BitSet done_set;
169 20 : while (i != BitSet::npos) {
170 20 : IFMapClient *client = server->GetClient(i);
171 20 : assert(client);
172 20 : AddNewReachableNodesTracker(client->index());
173 :
174 20 : IFMapTable *table = IFMapTable::FindTable(server->database(),
175 : "virtual-router");
176 20 : IFMapNode *node = table->FindNode(client->identifier());
177 20 : if ((node != NULL) && node->IsVertexValid()) {
178 6 : graph_->Visit(node,
179 12 : [this, i](DBGraphVertex *v) { RecomputeInterest(v, i); },
180 6 : 0, *traversal_white_list_.get());
181 : }
182 20 : done_set.set(i);
183 20 : if (++count == kMaxLinkDeleteWalks) {
184 : // client 'i' has been processed. If 'i' is the last bit set, we
185 : // will return true below. Else we will return false and there
186 : // is atleast one more bit left to process.
187 20 : break;
188 : }
189 :
190 0 : i = link_delete_clients_.find_next(i);
191 : }
192 : // Remove the subset of clients that we have finished processing.
193 20 : ResetLinkDeleteClients(done_set);
194 :
195 20 : LinkDeleteWalkBatchEnd(done_set);
196 :
197 20 : if (link_delete_clients_.empty()) {
198 20 : walk_client_index_ = BitSet::npos;
199 20 : return true;
200 : } else {
201 0 : walk_client_index_ = i;
202 0 : return false;
203 : }
204 20 : }
205 :
206 55 : void IFMapGraphWalker::OrLinkDeleteClients(const BitSet &bset) {
207 55 : link_delete_clients_.Set(bset); // link_delete_clients_ | bset
208 55 : }
209 :
210 26 : void IFMapGraphWalker::ResetLinkDeleteClients(const BitSet &bset) {
211 26 : link_delete_clients_.Reset(bset);
212 26 : }
213 :
214 68 : void IFMapGraphWalker::CleanupInterest(int client_index, IFMapNode *node,
215 : IFMapNodeState *state) {
216 68 : BitSet rm_mask;
217 68 : rm_mask.set(client_index);
218 :
219 : // interest = interest - rm_mask + nmask
220 :
221 68 : if (!state->interest().empty() && !state->nmask().empty()) {
222 12 : IFMAP_DEBUG(CleanupInterest, node->ToString(),
223 : state->interest().ToString(), rm_mask.ToString(),
224 : state->nmask().ToString());
225 : }
226 68 : BitSet ninterest;
227 68 : ninterest.BuildComplement(state->interest(), rm_mask);
228 68 : ninterest |= state->nmask();
229 68 : state->nmask_clear();
230 68 : if (state->interest() == ninterest) {
231 12 : return;
232 : }
233 :
234 56 : exporter_->StateInterestSet(state, ninterest);
235 56 : node->table()->Change(node);
236 :
237 : // Mark all dependent links as potentially modified.
238 56 : for (IFMapNodeState::iterator iter = state->begin();
239 178 : iter != state->end(); ++iter) {
240 122 : DBTable *table = exporter_->link_table();
241 122 : table->Change(iter.operator->());
242 : }
243 80 : }
244 :
245 : // Cleanup all the graph nodes that were reachable before this link delete.
246 : // After this link delete, these nodes may still be reachable. But, its
247 : // also possible that the link delete has made them unreachable.
248 20 : void IFMapGraphWalker::OldReachableNodesCleanupInterest(int client_index) {
249 20 : IFMapState *state = NULL;
250 20 : IFMapNode *node = NULL;
251 20 : IFMapExporter::Cs_citer iter = exporter_->ClientConfigTrackerBegin(
252 : IFMapExporter::INTEREST, client_index);
253 20 : IFMapExporter::Cs_citer end_iter = exporter_->ClientConfigTrackerEnd(
254 : IFMapExporter::INTEREST, client_index);
255 :
256 130 : while (iter != end_iter) {
257 110 : state = *iter;
258 : // Get the iterator to the next element before calling
259 : // CleanupInterest() since the state might be removed from the
260 : // client's config-tracker, thereby invalidating the iterator of the
261 : // container we are iterating over.
262 110 : ++iter;
263 110 : if (state->IsNode()) {
264 68 : node = state->GetIFMapNode();
265 68 : assert(node);
266 68 : IFMapNodeState *nstate = exporter_->NodeStateLookup(node);
267 68 : assert(state == nstate);
268 68 : CleanupInterest(client_index, node, nstate);
269 : }
270 : }
271 20 : }
272 :
273 : // Cleanup all the graph nodes that were not reachable before the link delete
274 : // but are reachable now. Note, we store nodes in new_reachable_nodes_tracker_
275 : // only if we visited them during the graph-walk via RecomputeInterest() and if
276 : // their interest bit was not set i.e. they were not reachable before we
277 : // started the walk.
278 20 : void IFMapGraphWalker::NewReachableNodesCleanupInterest(int client_index) {
279 20 : IFMapState *state = NULL;
280 20 : IFMapNode *node = NULL;
281 20 : ReachableNodesSet *rnset = new_reachable_nodes_tracker_.at(client_index);
282 :
283 20 : for (Rns_citer iter = rnset->begin(); iter != rnset->end(); ++iter) {
284 0 : state = *iter;
285 0 : assert(state->IsNode());
286 0 : node = state->GetIFMapNode();
287 0 : assert(node);
288 0 : IFMapNodeState *nstate = exporter_->NodeStateLookup(node);
289 0 : assert(state == nstate);
290 0 : CleanupInterest(client_index, node, nstate);
291 : }
292 20 : DeleteNewReachableNodesTracker(client_index);
293 20 : }
294 :
295 20 : void IFMapGraphWalker::LinkDeleteWalkBatchEnd(const BitSet &done_set) {
296 40 : for (size_t i = done_set.find_first(); i != BitSet::npos;
297 20 : i = done_set.find_next(i)) {
298 : // Examine all the nodes that were reachable before the link delete.
299 20 : OldReachableNodesCleanupInterest(i);
300 : // Examine all the nodes that were not reachable before the link
301 : // delete but are now reachable.
302 20 : NewReachableNodesCleanupInterest(i);
303 : }
304 20 : }
305 :
306 20 : void IFMapGraphWalker::AddNewReachableNodesTracker(int client_index) {
307 20 : if (client_index >= (int)new_reachable_nodes_tracker_.size()) {
308 20 : new_reachable_nodes_tracker_.resize(client_index + 1, NULL);
309 : }
310 20 : assert(new_reachable_nodes_tracker_[client_index] == NULL);
311 20 : ReachableNodesSet *rnset = new ReachableNodesSet();
312 20 : new_reachable_nodes_tracker_[client_index] = rnset;
313 20 : }
314 :
315 20 : void IFMapGraphWalker::DeleteNewReachableNodesTracker(int client_index) {
316 20 : ReachableNodesSet *rnset = new_reachable_nodes_tracker_.at(client_index);
317 20 : assert(rnset);
318 20 : delete rnset;
319 20 : new_reachable_nodes_tracker_[client_index] = NULL;
320 20 : }
321 :
322 : // Keep track of this node if it was unreachable earlier.
323 12 : void IFMapGraphWalker::UpdateNewReachableNodesTracker(int client_index,
324 : IFMapState *state) {
325 12 : ReachableNodesSet *rnset = new_reachable_nodes_tracker_.at(client_index);
326 12 : assert(rnset);
327 : // If the interest is not set, the node was not reachable earlier but is
328 : // reachable now.
329 12 : if (!state->interest().test(client_index)) {
330 0 : rnset->insert(state);
331 : }
332 12 : }
333 :
334 0 : const IFMapTypenameWhiteList &IFMapGraphWalker::get_traversal_white_list()
335 : const {
336 0 : return *traversal_white_list_.get();
337 : }
338 :
339 : // The nodes listed below and the nodes in
340 : // IFMapGraphTraversalFilterCalculator::CreateNodeBlackList() are mutually
341 : // exclusive
342 57 : void IFMapGraphWalker::AddNodesToWhitelist() {
343 57 : traversal_white_list_->include_vertex = {
344 : {"virtual-router", {
345 : "physical-router-virtual-router",
346 : "virtual-router-virtual-machine",
347 : "virtual-router-network-ipam",
348 : "global-system-config-virtual-router",
349 : "provider-attachment-virtual-router",
350 : "virtual-router-virtual-machine-interface",
351 : "virtual-router-sub-cluster",
352 : }},
353 : {"virtual-router-network-ipam", {
354 : "virtual-router-network-ipam",
355 : }},
356 : {"virtual-machine", {
357 : "virtual-machine-service-instance",
358 : "virtual-machine-interface-virtual-machine",
359 : "virtual-machine-tag",
360 : }},
361 : {"control-node-zone", {}},
362 : {"sub-cluster", {
363 : "bgp-router-sub-cluster",
364 : }},
365 : {"bgp-router", {
366 : "instance-bgp-router",
367 : "physical-router-bgp-router",
368 : "bgp-router-control-node-zone",
369 : }},
370 : {"bgp-as-a-service", {
371 : "bgpaas-bgp-router",
372 : "bgpaas-health-check",
373 : "bgpaas-control-node-zone",
374 : }},
375 : {"bgpaas-control-node-zone", {
376 : "bgpaas-control-node-zone",
377 : }},
378 : {"global-system-config", {
379 : "global-system-config-global-vrouter-config",
380 : "global-system-config-global-qos-config",
381 : "global-system-config-bgp-router",
382 : "qos-config-global-system-config",
383 : }},
384 : {"provider-attachment", {}},
385 : {"service-instance", {
386 : "service-instance-service-template",
387 : "service-instance-port-tuple",
388 : }},
389 : {"global-vrouter-config", {
390 : "application-policy-set-global-vrouter-config",
391 : "global-vrouter-config-security-logging-object",
392 : }},
393 : {"virtual-machine-interface", {
394 : "virtual-machine-virtual-machine-interface",
395 : "virtual-machine-interface-sub-interface",
396 : "instance-ip-virtual-machine-interface",
397 : "virtual-machine-interface-virtual-network",
398 : "virtual-machine-interface-security-group",
399 : "floating-ip-virtual-machine-interface",
400 : "alias-ip-virtual-machine-interface",
401 : "customer-attachment-virtual-machine-interface",
402 : "virtual-machine-interface-routing-instance",
403 : "virtual-machine-interface-route-table",
404 : "subnet-virtual-machine-interface",
405 : "service-port-health-check",
406 : "bgpaas-virtual-machine-interface",
407 : "virtual-machine-interface-qos-config",
408 : "virtual-machine-interface-bridge-domain",
409 : "virtual-machine-interface-security-logging-object",
410 : "project-virtual-machine-interface",
411 : "port-tuple-interface",
412 : "virtual-machine-interface-tag",
413 : "virtual-machine-interface-bgp-router",
414 : }},
415 : {"virtual-machine-interface-bridge-domain", {
416 : "virtual-machine-interface-bridge-domain",
417 : }},
418 : {"security-group", {
419 : "security-group-access-control-list",
420 : }},
421 : {"physical-router", {
422 : "physical-router-physical-interface",
423 : "physical-router-logical-interface",
424 : "physical-router-virtual-network",
425 : }},
426 : {"service-template", {
427 : "domain-service-template",
428 : }},
429 : {"instance-ip", {
430 : "instance-ip-virtual-network",
431 : }},
432 : {"virtual-network", {
433 : "virtual-network-floating-ip-pool",
434 : "virtual-network-alias-ip-pool",
435 : "virtual-network-network-ipam",
436 : "virtual-network-access-control-list",
437 : "virtual-network-routing-instance",
438 : "virtual-network-qos-config",
439 : "virtual-network-bridge-domain",
440 : "virtual-network-security-logging-object",
441 : "virtual-network-tag",
442 : "virtual-network-provider-network",
443 : "virtual-network-multicast-policy",
444 : "vn-health-check",
445 : "host-based-service-virtual-network",
446 : "logical-router-virtual-network",
447 : }},
448 : {"floating-ip", {
449 : "floating-ip-pool-floating-ip",
450 : "instance-ip-floating-ip",
451 : }},
452 : {"alias-ip", {
453 : "alias-ip-pool-alias-ip",
454 : }},
455 : {"customer-attachment", {}},
456 : {"virtual-machine-interface-routing-instance", {
457 : "virtual-machine-interface-routing-instance",
458 : }},
459 : {"physical-interface", {
460 : "physical-interface-logical-interface",
461 : "virtual-port-group-physical-interface",
462 : }},
463 : {"virtual-port-group-physical-interface", {
464 : "virtual-port-group-physical-interface",
465 : }},
466 : {"virtual-port-group", {
467 : "virtual-port-group-virtual-machine-interface",
468 : "virtual-port-group-physical-interface",
469 : }},
470 : {"domain", {
471 : "domain-namespace",
472 : "domain-virtual-DNS",
473 : }},
474 : {"floating-ip-pool", {
475 : "virtual-network-floating-ip-pool",
476 : }},
477 : {"alias-ip-pool", {
478 : "virtual-network-alias-ip-pool",
479 : }},
480 : {"logical-interface", {
481 : "logical-interface-virtual-machine-interface",
482 : }},
483 : {"logical-router-virtual-network", {
484 : "logical-router-virtual-network",
485 : }},
486 : {"logical-router", {
487 : "logical-router-virtual-network",
488 : "logical-router-interface",
489 : }},
490 : {"virtual-network-network-ipam", {
491 : "virtual-network-network-ipam",
492 : }},
493 : {"access-control-list", {}},
494 : {"routing-instance", {}},
495 : {"namespace", {}},
496 : {"virtual-DNS", {
497 : "virtual-DNS-virtual-DNS-record",
498 : }},
499 : {"network-ipam", {
500 : "network-ipam-virtual-DNS",
501 : }},
502 : {"virtual-DNS-record", {}},
503 : {"interface-route-table", {}},
504 : {"subnet", {}},
505 : {"service-health-check", {}},
506 : {"qos-config", {}},
507 : {"qos-queue", {}},
508 : {"forwarding-class", {
509 : "forwarding-class-qos-queue",
510 : }},
511 : {"global-qos-config", {
512 : "global-qos-config-forwarding-class",
513 : "global-qos-config-qos-queue",
514 : "global-qos-config-qos-config",
515 : }},
516 : {"bridge-domain", {}},
517 : {"security-logging-object", {
518 : "virtual-network-security-logging-object",
519 : "virtual-machine-interface-security-logging-object",
520 : "global-vrouter-config-security-logging-object",
521 : "security-logging-object-network-policy",
522 : "security-logging-object-security-group",
523 : }},
524 : {"tag", {
525 : "application-policy-set-tag",
526 : }},
527 : {"application-policy-set", {
528 : "application-policy-set-firewall-policy",
529 : "policy-management-application-policy-set",
530 : }},
531 : {"application-policy-set-firewall-policy", {
532 : "application-policy-set-firewall-policy",
533 : }},
534 : {"firewall-policy", {
535 : "firewall-policy-firewall-rule",
536 : "firewall-policy-security-logging-object",
537 : }},
538 : {"firewall-policy-firewall-rule", {
539 : "firewall-policy-firewall-rule",
540 : }},
541 : {"firewall-policy-security-logging-object", {
542 : "firewall-policy-security-logging-object",
543 : }},
544 : {"firewall-rule", {
545 : "firewall-rule-tag",
546 : "firewall-rule-service-group",
547 : "firewall-rule-address-group",
548 : "firewall-rule-security-logging-object",
549 : }},
550 : {"firewall-rule-security-logging-object", {
551 : "firewall-rule-security-logging-object",
552 : }},
553 : {"service-group", {}},
554 : {"address-group", {
555 : "address-group-tag",
556 : }},
557 : {"host-based-service", {
558 : "host-based-service-virtual-network",
559 : }},
560 : {"host-based-service-virtual-network", {
561 : "virtual-network",
562 : }},
563 : {"project", {
564 : "project-tag",
565 : "project-logical-router",
566 : "project-host-based-service",
567 : }},
568 : {"port-tuple", {
569 : "service-instance-port-tuple",
570 : "port-tuple-interface",
571 : }},
572 : {"policy-management", {}},
573 : {"multicast-policy", {
574 : "virtual-network-multicast-policy",
575 : }},
576 10488 : };
577 57 : }
578 :
|
