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