Merge branch 'master' into mpr_rework
[oonf.git] / src-plugins / nhdp / mpr / mpr.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 <errno.h>
47 #include <stdio.h>
48
49 #include "common/common_types.h"
50 #include "common/autobuf.h"
51 #include "common/avl.h"
52 #include "common/avl_comp.h"
53 #include "common/container_of.h"
54 #include "config/cfg_schema.h"
55 #include "core/oonf_logging.h"
56 #include "core/oonf_subsystem.h"
57 #include "subsystems/oonf_class.h"
58 #include "subsystems/oonf_rfc5444.h"
59 #include "subsystems/oonf_timer.h"
60
61 #include "nhdp/nhdp.h"
62 #include "nhdp/nhdp_db.h"
63 #include "nhdp/nhdp_domain.h"
64 #include "nhdp/nhdp_interfaces.h"
65
66 #include "mpr/mpr.h"
67
68 #include "neighbor-graph-flooding.h"
69 #include "neighbor-graph-routing.h"
70 #include "selection-rfc7181.h"
71
72 /* FIXME remove unneeded includes */
73
74 /* prototypes */
75 static void _early_cfg_init(void);
76 static int _init(void);
77 static void _cleanup(void);
78 static void _cb_update_mpr(struct nhdp_domain *);
79
80 static const char *_dependencies[] = {
81   OONF_CLASS_SUBSYSTEM,
82   OONF_TIMER_SUBSYSTEM,
83   OONF_NHDP_SUBSYSTEM,
84 };
85 static struct oonf_subsystem _nhdp_mpr_subsystem = {
86   .name = OONF_MPR_SUBSYSTEM,
87   .dependencies = _dependencies,
88   .dependencies_count = ARRAYSIZE(_dependencies),
89   .descr = "RFC7181 Appendix B MPR Plugin",
90   .author = "Jonathan Kirchhoff",
91
92   .early_cfg_init = _early_cfg_init,
93   .init = _init,
94   .cleanup = _cleanup,
95 };
96 DECLARE_OONF_PLUGIN(_nhdp_mpr_subsystem);
97
98 static struct nhdp_domain_mpr _mpr_handler = {
99   .name = OONF_MPR_SUBSYSTEM,
100   .update_mpr = _cb_update_mpr,
101 };
102
103 enum oonf_log_source LOG_MPR;
104
105 static void
106 _early_cfg_init(void) {
107   LOG_MPR = _nhdp_mpr_subsystem.logging;
108 }
109
110 /**
111  * Initialize plugin
112  * @return -1 if an error happened, 0 otherwise
113  */
114 static int
115 _init(void) {
116   if (nhdp_domain_mpr_add(&_mpr_handler)) {
117     return -1;
118   }
119   return 0;
120 }
121
122 /**
123  * Cleanup plugin
124  */
125 static void
126 _cleanup(void) {
127 }
128
129 /**
130  * Updates the current routing MPR selection in the NHDP database
131  * @param current_mpr_data
132  */
133 static void
134 _update_nhdp_routing(struct neighbor_graph *graph) {
135   struct nhdp_link *lnk;
136   struct n1_node *current_mpr_node;
137 #ifdef OONF_LOG_DEBUG_INFO
138   struct netaddr_str buf1;
139 #endif
140
141   OONF_DEBUG(LOG_MPR, "Updating ROUTING MPRs");
142   
143   list_for_each_element(nhdp_db_get_link_list(), lnk, _global_node) {
144     lnk->neigh->_domaindata[0].neigh_is_mpr = false;
145     current_mpr_node = avl_find_element(&graph->set_mpr,
146         &lnk->neigh->originator,
147         current_mpr_node, _avl_node);
148     if (current_mpr_node != NULL) {
149       OONF_DEBUG(LOG_MPR, "Processing MPR node %s",
150           netaddr_to_string(&buf1, &current_mpr_node->addr));
151       lnk->neigh->_domaindata[0].neigh_is_mpr = true;
152     }
153   }
154 }
155
156 /**
157  * Updates the current flooding MPR selection in the NHDP database
158  * @param current_mpr_data
159  */
160 static void
161 _update_nhdp_flooding(struct neighbor_graph *graph) {
162   struct nhdp_link *current_link;
163   struct n1_node *current_mpr_node;
164 #ifdef OONF_LOG_DEBUG_INFO
165   struct netaddr_str buf1;
166 #endif
167
168   OONF_DEBUG(LOG_MPR, "Updating FLOODING MPRs");
169
170   list_for_each_element(nhdp_db_get_link_list(), current_link, _global_node) {
171     current_mpr_node = avl_find_element(&graph->set_mpr,
172         &current_link->neigh->originator,
173         current_mpr_node, _avl_node);
174     if (current_mpr_node != NULL) {
175       OONF_DEBUG(LOG_MPR, "Processing MPR node %s",
176           netaddr_to_string(&buf1, &current_mpr_node->addr));
177       current_link->neigh->neigh_is_flooding_mpr = true;
178     }
179   }
180 }
181
182 /**
183  * Updates the current flooding MPR selection in the NHDP database
184  * @param current_mpr_data
185  */
186 static void
187 _clear_nhdp_flooding(void) {
188   struct nhdp_link *current_link;
189
190   OONF_DEBUG(LOG_MPR, "Clear FLOODING MPRs");
191
192   list_for_each_element(nhdp_db_get_link_list(), current_link, _global_node) {
193     current_link->neigh->neigh_is_flooding_mpr = false;
194   }
195 }
196
197 static void
198 _update_flooding_mpr(struct nhdp_domain *domain) {
199   struct mpr_flooding_data flooding_data;
200
201   memset(&flooding_data, 0, sizeof(flooding_data));
202   
203   /* FIXME Currently, the flooding set is calculated incrementally (i.e. 
204    in a coordinated way as suggested by RFC 7181; however, this should
205    be configurable (and other selection algorithms might not be compatible
206    with this approach).
207    */
208   /* FIXME How to support the coordination flooding and routing MPRs 
209    * selection? */
210   /* calculate flooding MPRs */
211
212   OONF_DEBUG(LOG_MPR, "Recalculating flooding MPR");
213
214   _clear_nhdp_flooding();
215   avl_for_each_element(nhdp_interface_get_tree(), flooding_data.current_interface, _node) {
216     OONF_DEBUG(LOG_MPR, "Calculating flooding MPRs for interface %s",
217         nhdp_interface_get_name(flooding_data.current_interface));
218     
219     mpr_calculate_neighbor_graph_flooding(domain, &flooding_data);
220     mpr_calculate_mpr_rfc7181(domain, &flooding_data.neigh_graph);
221     mpr_print_sets(&flooding_data.neigh_graph);
222     _update_nhdp_flooding(&flooding_data.neigh_graph);
223   }
224
225   /* free memory */
226   mpr_clear_neighbor_graph(&flooding_data.neigh_graph);
227
228   OONF_DEBUG(LOG_MPR, "Finished recalculating MPRs");
229 }
230
231 static void
232 _update_routing_mpr(struct nhdp_domain *domain) {
233   struct neighbor_graph routing_graph;
234
235   OONF_DEBUG(LOG_MPR, "Recalculating MPR for domain %u", domain->ext);
236
237   memset(&routing_graph, 0, sizeof(routing_graph));
238   mpr_calculate_neighbor_graph_routing(domain, &routing_graph);
239   mpr_calculate_mpr_rfc7181(domain, &routing_graph);
240   mpr_print_sets(&routing_graph);
241   _update_nhdp_routing(&routing_graph);
242   mpr_clear_neighbor_graph(&routing_graph);
243
244   OONF_DEBUG(LOG_MPR, "Finished recalculating MPRs");
245 }
246
247 /**
248  * Callback triggered when an MPR update is required
249  * @param domain NHDP domain
250  */
251 static void
252 _cb_update_mpr(struct nhdp_domain *domain) {
253   if (domain->mpr != &_mpr_handler) {
254     OONF_WARN(LOG_MPR,
255         "Wrong MPR handler called for domain extension %u", domain->ext);
256     return;
257   }
258
259   /* calculate MPRs */
260   if (domain == nhdp_domain_get_flooding_domain()) {
261     _update_flooding_mpr(domain);
262   }
263   else {
264     _update_routing_mpr(domain);
265   }
266 }
267
268 #if 0
269
270 /**
271  * Validate the MPR set according to section 18.3 (draft 19)
272  * @param current_mpr_data
273  * @return 
274  */
275 void
276 _validate_mpr_set(struct common_data *mpr_data) {
277   struct n1_node *node_n1;
278   struct addr_node *n2_addr;
279   uint32_t d_y_n1, d_y_mpr;
280
281   OONF_DEBUG(LOG_MPR, "Validating MPR set");
282
283   /* 
284    * First property: If x in N1 has W(x) = WILL_ALWAYS then x is in M. 
285    */
286   avl_for_each_element(&mpr_data->set_n1, node_n1,
287       _avl_node) {
288     if (node_n1->neigh->flooding_willingness
289         == RFC5444_WILLINGNESS_ALWAYS) {
290       assert(_is_mpr(mpr_data, &node_n1->addr));
291     }
292   }
293
294   /*
295    * Second property: For any y in N2 that does not have a defined d1(y), 
296    * there is at least one element in M that is also in N1(y). This is 
297    * equivalent to the requirement that d(y, M) is defined.
298    */
299   avl_for_each_element(&mpr_data->set_n2, n2_addr, _avl_node) {
300     assert(_calculate_d_of_y_s(mpr_data, n2_addr, &mpr_data->set_mpr)
301         != RFC5444_METRIC_INFINITE);
302   }
303
304   /*
305    * Third property: For any y in N2, d(y,M) = d(y, N1).
306    */
307   avl_for_each_element(&mpr_data->set_n2, n2_addr, _avl_node) {
308     d_y_n1 = _calculate_d_of_y_s(mpr_data, n2_addr, &mpr_data->set_n1);
309     d_y_mpr = _calculate_d_of_y_s(mpr_data, n2_addr, &mpr_data->set_mpr);
310     assert(d_y_n1 == d_y_mpr);
311   }
312 }
313
314
315 #endif