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