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