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