Rename "subsystems" directory to "base"
[oonf.git] / src / nhdp / mpr / neighbor-graph.c
1
2 /*
3  * The olsr.org Optimized Link-State Routing daemon version 2 (olsrd2)
4  * Copyright (c) 2004-2015, the olsr.org team - see HISTORY file
5  * All rights reserved.
6  *
7  * Redistribution and use in source and binary forms, with or without
8  * modification, are permitted provided that the following conditions
9  * are met:
10  *
11  * * Redistributions of source code must retain the above copyright
12  *   notice, this list of conditions and the following disclaimer.
13  * * Redistributions in binary form must reproduce the above copyright
14  *   notice, this list of conditions and the following disclaimer in
15  *   the documentation and/or other materials provided with the
16  *   distribution.
17  * * Neither the name of olsr.org, olsrd nor the names of its
18  *   contributors may be used to endorse or promote products derived
19  *   from this software without specific prior written permission.
20  *
21  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
24  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
25  * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
26  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
27  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
28  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
29  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
30  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
31  * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
32  * POSSIBILITY OF SUCH DAMAGE.
33  *
34  * Visit http://www.olsr.org for more information.
35  *
36  * If you find this software useful feel free to make a donation
37  * to the project. For more information see the website or contact
38  * the copyright holders.
39  *
40  */
41
42 /**
43  * @file
44  */
45
46 #include <oonf/nhdp/nhdp/nhdp.h>
47 #include <oonf/nhdp/nhdp/nhdp_db.h>
48 #include <oonf/nhdp/nhdp/nhdp_domain.h>
49 #include <oonf/nhdp/nhdp/nhdp_interfaces.h>
50 #include <stdio.h>
51
52 #include <oonf/libcommon/autobuf.h>
53 #include <oonf/libcommon/avl.h>
54 #include <oonf/libcommon/avl_comp.h>
55 #include <oonf/oonf.h>
56 #include <oonf/libcommon/container_of.h>
57 #include <oonf/libconfig/cfg_schema.h>
58 #include <oonf/libcore/oonf_cfg.h>
59 #include <oonf/libcore/oonf_logging.h>
60 #include <oonf/base/oonf_class.h>
61 #include <oonf/base/oonf_rfc5444.h>
62
63 #include <oonf/nhdp/mpr/mpr.h>
64 #include <oonf/nhdp/mpr/mpr_internal.h>
65 #include <oonf/nhdp/mpr/neighbor-graph-flooding.h>
66 #include <oonf/nhdp/mpr/neighbor-graph.h>
67
68 /* FIXME remove unneeded includes */
69
70 void
71 mpr_add_n1_node_to_set(struct avl_tree *set, struct nhdp_neighbor *neigh, struct nhdp_link *lnk, uint32_t offset) {
72   struct n1_node *tmp_n1_neigh;
73   tmp_n1_neigh = avl_find_element(set, &neigh->originator, tmp_n1_neigh, _avl_node);
74   if (tmp_n1_neigh) {
75     return;
76   }
77   tmp_n1_neigh = calloc(1, sizeof(struct n1_node));
78   tmp_n1_neigh->addr = neigh->originator;
79   tmp_n1_neigh->_avl_node.key = &tmp_n1_neigh->addr;
80   tmp_n1_neigh->neigh = neigh;
81   tmp_n1_neigh->link = lnk;
82   tmp_n1_neigh->table_offset = offset;
83   avl_insert(set, &tmp_n1_neigh->_avl_node);
84 }
85
86 void
87 mpr_add_addr_node_to_set(struct avl_tree *set, const struct netaddr addr, uint32_t offset) {
88   struct addr_node *tmp_node;
89
90   tmp_node = avl_find_element(set, &addr, tmp_node, _avl_node);
91   if (tmp_node) {
92     return;
93   }
94   tmp_node = calloc(1, sizeof(struct addr_node));
95   tmp_node->addr = addr;
96   tmp_node->_avl_node.key = &tmp_node->addr;
97   tmp_node->table_offset = offset;
98   avl_insert(set, &tmp_node->_avl_node);
99 }
100
101 /**
102  * Initialize the MPR data set
103  * @param graph neighbor graph instance
104  * @param methods callback for handling graph
105  */
106 void
107 mpr_init_neighbor_graph(struct neighbor_graph *graph, struct neighbor_graph_interface *methods) {
108   avl_init(&graph->set_n, avl_comp_netaddr, false);
109   avl_init(&graph->set_n1, avl_comp_netaddr, false);
110   avl_init(&graph->set_n2, avl_comp_netaddr, false);
111   avl_init(&graph->set_mpr, avl_comp_netaddr, false);
112   avl_init(&graph->set_mpr_candidates, avl_comp_netaddr, false);
113   graph->methods = methods;
114 }
115
116 /**
117  * Clear a set of addresses
118  * @param set AVL set to clear
119  */
120 void
121 mpr_clear_addr_set(struct avl_tree *set) {
122   struct addr_node *current_node, *node_it;
123
124   avl_for_each_element_safe(set, current_node, _avl_node, node_it) {
125     avl_remove(set, &current_node->_avl_node);
126     free(current_node);
127   }
128 }
129
130 /**
131  * Clear set of N1 nodes
132  * @param set AVL set to clear
133  */
134 void
135 mpr_clear_n1_set(struct avl_tree *set) {
136   struct n1_node *current_node, *node_it;
137
138   avl_for_each_element_safe(set, current_node, _avl_node, node_it) {
139     avl_remove(set, &current_node->_avl_node);
140     free(current_node);
141   }
142 }
143
144 /**
145  * Clear the MPR data set
146  * @param graph neighbor graph instance
147  */
148 void
149 mpr_clear_neighbor_graph(struct neighbor_graph *graph) {
150   mpr_clear_addr_set(&graph->set_n);
151   mpr_clear_addr_set(&graph->set_n2);
152   mpr_clear_n1_set(&graph->set_n1);
153   mpr_clear_n1_set(&graph->set_mpr);
154   mpr_clear_n1_set(&graph->set_mpr_candidates);
155
156   free(graph->d_x_y_cache);
157   graph->d_x_y_cache = NULL;
158 }
159
160 /**
161  * Check if a node was selected as an MPR
162  * @param graph neighbor graph instance
163  * @param addr network address to check
164  * @return true if mpr, false otherwise
165  */
166 bool
167 mpr_is_mpr(struct neighbor_graph *graph, struct netaddr *addr) {
168   struct n1_node *tmp_mpr_node;
169
170   tmp_mpr_node = avl_find_element(&graph->set_mpr, addr, tmp_mpr_node, _avl_node);
171   return tmp_mpr_node != NULL;
172 }
173
174 uint32_t
175 mpr_calculate_minimal_d_z_y(const struct nhdp_domain *domain, struct neighbor_graph *graph, struct addr_node *y) {
176   struct n1_node *z_node;
177   uint32_t d_z_y, min_d_z_y;
178 #ifdef OONF_LOG_DEBUG_INFO
179   struct n1_node *remember;
180   struct netaddr_str nbuf1, nbuf2;
181 #endif
182   if (y->min_d_z_y) {
183     return y->min_d_z_y;
184   }
185
186   min_d_z_y = RFC7181_METRIC_INFINITE_PATH;
187 #ifdef OONF_LOG_DEBUG_INFO
188   remember = NULL;
189 #endif
190   avl_for_each_element(&graph->set_n1, z_node, _avl_node) {
191     d_z_y = graph->methods->calculate_d_x_y(domain, graph, z_node, y);
192     if (d_z_y < min_d_z_y) {
193       min_d_z_y = d_z_y;
194 #ifdef OONF_LOG_DEBUG_INFO
195       remember = z_node;
196 #endif
197     }
198   }
199
200 #ifdef OONF_LOG_DEBUG_INFO
201   if (remember) {
202     OONF_DEBUG(LOG_MPR, "minimal d_z_y(%s) = %s (cost %u)", netaddr_to_string(&nbuf1, &y->addr),
203       netaddr_to_string(&nbuf2, &remember->addr), min_d_z_y);
204   }
205   else {
206     OONF_DEBUG(LOG_MPR, "minimal d_z_y(%s) = infinite", netaddr_to_string(&nbuf1, &y->addr));
207   }
208 #endif
209   y->min_d_z_y = min_d_z_y;
210   return min_d_z_y;
211 }
212
213 /**
214  * Print a set of addresses
215  * @param set AVL set to print
216  */
217 void
218 mpr_print_addr_set(struct avl_tree *set) {
219   struct addr_node *current_node;
220 #ifdef OONF_LOG_DEBUG_INFO
221   struct netaddr_str buf1;
222 #endif
223
224   avl_for_each_element(set, current_node, _avl_node) {
225     OONF_DEBUG(LOG_MPR, "%s", netaddr_to_string(&buf1, &current_node->addr));
226   }
227 }
228
229 void
230 mpr_print_n1_set(struct nhdp_domain *domain __attribute__((unused)), struct avl_tree *set) {
231   struct n1_node *current_node;
232 #ifdef OONF_LOG_DEBUG_INFO
233   struct nhdp_neighbor_domaindata *neighbordata;
234   struct netaddr_str buf1;
235 #endif
236
237   avl_for_each_element(set, current_node, _avl_node) {
238 #ifdef OONF_LOG_DEBUG_INFO
239     neighbordata = nhdp_domain_get_neighbordata(domain, current_node->neigh);
240
241     OONF_DEBUG(LOG_MPR, "%s in: %u out: %u", netaddr_to_string(&buf1, &current_node->addr), neighbordata->metric.in,
242       neighbordata->metric.out);
243 #endif
244   }
245 }
246
247 /**
248  * Print the MPR data sets
249  * @param graph neighbor graph instance
250  */
251 void
252 mpr_print_sets(struct nhdp_domain *domain, struct neighbor_graph *graph) {
253   OONF_DEBUG(LOG_MPR, "Set N");
254   mpr_print_addr_set(&graph->set_n);
255
256   OONF_DEBUG(LOG_MPR, "Set N1");
257   mpr_print_n1_set(domain, &graph->set_n1);
258
259   OONF_DEBUG(LOG_MPR, "Set N2");
260   mpr_print_addr_set(&graph->set_n2);
261
262   OONF_DEBUG(LOG_MPR, "Set MPR");
263   mpr_print_n1_set(domain, &graph->set_mpr);
264 }
265
266 /**
267  * Calculate d(y,S) according to section 18.2 (draft 19)
268  * @param domain NHDP domain
269  * @param graph neighbor graph instance
270  * @param y graph node Y
271  * @param subset_s subset of graph
272  * @return metric cost
273  */
274 uint32_t
275 mpr_calculate_d_of_y_s(
276   const struct nhdp_domain *domain, struct neighbor_graph *graph, struct addr_node *y, struct avl_tree *subset_s) {
277   uint32_t d_x_y, min_cost;
278   struct n1_node *node_n1;
279
280 #ifdef OONF_LOG_DEBUG_INFO
281   struct netaddr_str buf1;
282 #endif
283
284   /* determine the minimum cost to y over all possible intermediate hops */
285   min_cost = graph->methods->calculate_d1_x_of_n2_addr(domain, graph, y);
286   if (min_cost > RFC7181_METRIC_MAX) {
287     min_cost = RFC7181_METRIC_INFINITE_PATH;
288   }
289   OONF_DEBUG(LOG_MPR, "mpr_calculate_d_of_y_s(%s)", netaddr_to_string(&buf1, &y->addr));
290   OONF_DEBUG(LOG_MPR, "initial cost = %u", min_cost);
291   avl_for_each_element(subset_s, node_n1, _avl_node) {
292     d_x_y = graph->methods->calculate_d_x_y(domain, graph, node_n1, y);
293     OONF_DEBUG(LOG_MPR, "cost via %s would be = %u", netaddr_to_string(&buf1, &node_n1->addr), d_x_y);
294     if (d_x_y < min_cost) {
295       min_cost = d_x_y;
296     }
297   }
298
299   return min_cost;
300 }