Rename "subsystems" directory to "base"
[oonf.git] / src / 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 <oonf/libcommon/autobuf.h>
50 #include <oonf/libcommon/avl.h>
51 #include <oonf/libcommon/avl_comp.h>
52 #include <oonf/oonf.h>
53 #include <oonf/libcommon/container_of.h>
54 #include <oonf/libconfig/cfg_schema.h>
55 #include <oonf/libcore/oonf_logging.h>
56 #include <oonf/libcore/oonf_subsystem.h>
57 #include <oonf/base/oonf_class.h>
58 #include <oonf/base/oonf_rfc5444.h>
59
60 #include <oonf/nhdp/nhdp/nhdp.h>
61 #include <oonf/nhdp/nhdp/nhdp_db.h>
62 #include <oonf/nhdp/nhdp/nhdp_domain.h>
63 #include <oonf/nhdp/nhdp/nhdp_interfaces.h>
64
65 #include <oonf/nhdp/mpr/mpr.h>
66
67 #include <oonf/nhdp/mpr/neighbor-graph-flooding.h>
68 #include <oonf/nhdp/mpr/neighbor-graph-routing.h>
69 #include <oonf/nhdp/mpr/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(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_routing_mpr = _cb_update_routing_mpr,
105   .update_flooding_mpr = _cb_update_flooding_mpr,
106 };
107
108 /* logging sources for NHDP subsystem */
109 enum oonf_log_source LOG_MPR;
110
111 /**
112  * Initialize additional logging sources for NHDP
113  */
114 static void
115 _early_cfg_init(void) {
116   LOG_MPR = _nhdp_mpr_subsystem.logging;
117 }
118
119 /**
120  * Initialize plugin
121  * @return -1 if an error happened, 0 otherwise
122  */
123 static int
124 _init(void) {
125   if (nhdp_domain_mpr_add(&_mpr_handler)) {
126     return -1;
127   }
128   return 0;
129 }
130
131 /**
132  * Cleanup plugin
133  */
134 static void
135 _cleanup(void) {}
136
137 /**
138  * Updates the current routing MPR selection in the NHDP database
139  * @param graph MPR neighbor graph instance
140  */
141 static void
142 _update_nhdp_routing(struct nhdp_domain *domain, struct neighbor_graph *graph) {
143   struct n1_node *current_mpr_node;
144   struct nhdp_link *lnk;
145   struct nhdp_neighbor_domaindata *neighbordata;
146
147   list_for_each_element(nhdp_db_get_link_list(), lnk, _global_node) {
148     neighbordata = nhdp_domain_get_neighbordata(domain, lnk->neigh);
149     neighbordata->neigh_is_mpr = false;
150     current_mpr_node = avl_find_element(&graph->set_mpr, &lnk->neigh->originator, current_mpr_node, _avl_node);
151
152     neighbordata->neigh_is_mpr = current_mpr_node != NULL;
153   }
154 }
155
156 /**
157  * Updates the current flooding MPR selection in the NHDP database
158  * @param nhdp_if nhdp interface to update
159  * @param graph MPR neighbor graph instance
160  */
161 static void
162 _update_nhdp_flooding(struct nhdp_interface *nhdp_if, struct neighbor_graph *graph) {
163   struct nhdp_link *current_link;
164   struct n1_node *current_mpr_node;
165
166   list_for_each_element(&nhdp_if->_links, current_link, _if_node) {
167     current_mpr_node = avl_find_element(&graph->set_mpr, &current_link->neigh->originator, current_mpr_node, _avl_node);
168
169     current_link->neigh_is_flooding_mpr = current_mpr_node != NULL;
170   }
171 }
172
173 /**
174  * Updates the current flooding MPR selection in the NHDP database
175  */
176 static void
177 _clear_nhdp_flooding(void) {
178   struct nhdp_link *current_link;
179
180   //  OONF_DEBUG(LOG_MPR, "Updating FLOODING MPRs");
181
182   list_for_each_element(nhdp_db_get_link_list(), current_link, _global_node) {
183     current_link->neigh_is_flooding_mpr = false;
184   }
185 }
186
187 /**
188  * Update the flooding MPR settings
189  */
190 static void
191 _cb_update_flooding_mpr(struct nhdp_domain *domain) {
192   struct mpr_flooding_data flooding_data;
193
194   memset(&flooding_data, 0, sizeof(flooding_data));
195
196   _clear_nhdp_flooding();
197   avl_for_each_element(nhdp_interface_get_tree(), flooding_data.current_interface, _node) {
198     OONF_DEBUG(LOG_MPR, "*** Calculate flooding MPRs for interface %s ***",
199       nhdp_interface_get_name(flooding_data.current_interface));
200
201     mpr_calculate_neighbor_graph_flooding(domain, &flooding_data);
202     mpr_calculate_mpr_rfc7181(domain, &flooding_data.neigh_graph);
203     mpr_print_sets(domain, &flooding_data.neigh_graph);
204 #ifndef NDEBUG
205     _validate_mpr_set(domain, &flooding_data.neigh_graph);
206 #endif
207     _update_nhdp_flooding(flooding_data.current_interface, &flooding_data.neigh_graph);
208     mpr_clear_neighbor_graph(&flooding_data.neigh_graph);
209   }
210 }
211
212 /**
213  * Update the routing MPR settings for all domains
214  */
215 static void
216 _cb_update_routing_mpr(struct nhdp_domain *domain) {
217   struct neighbor_graph routing_graph;
218
219   if (domain->mpr != &_mpr_handler) {
220     /* we are not the routing MPR for this domain */
221     return;
222   }
223   OONF_DEBUG(LOG_MPR, "*** Calculate routing MPRs for domain %u ***", domain->index);
224
225   memset(&routing_graph, 0, sizeof(routing_graph));
226   mpr_calculate_neighbor_graph_routing(domain, &routing_graph);
227   mpr_calculate_mpr_rfc7181(domain, &routing_graph);
228   mpr_print_sets(domain, &routing_graph);
229 #ifndef NDEBUG
230   _validate_mpr_set(domain, &routing_graph);
231 #endif
232   _update_nhdp_routing(domain, &routing_graph);
233   mpr_clear_neighbor_graph(&routing_graph);
234 }
235
236 #ifndef NDEBUG
237
238 /**
239  * Validate the MPR set according to section 18.3 (draft 19)
240  * @param domain NHDP domaine
241  * @param graph MPR neighbor graph instance
242  */
243 static void
244 _validate_mpr_set(const struct nhdp_domain *domain, struct neighbor_graph *graph) {
245   struct n1_node *node_n1;
246   struct addr_node *n2_addr;
247   uint32_t d_y_n1;
248   uint32_t d_y_mpr;
249
250   OONF_DEBUG(LOG_MPR, "Validating MPR set");
251
252   /*
253    * First property: If x in N1 has W(x) = WILL_ALWAYS then x is in M.
254    */
255   avl_for_each_element(&graph->set_n1, node_n1, _avl_node) {
256     if (domain == nhdp_domain_get_flooding_domain()) {
257       if (node_n1->link->flooding_willingness == RFC7181_WILLINGNESS_ALWAYS) {
258         OONF_ASSERT(mpr_is_mpr(graph, &node_n1->addr), LOG_MPR, "WILLINGNESS_ALWAYS Node is no MPR");
259       }
260     }
261     else {
262       struct nhdp_neighbor_domaindata *neighdata;
263
264       neighdata = nhdp_domain_get_neighbordata(domain, node_n1->neigh);
265       if (neighdata->willingness == RFC7181_WILLINGNESS_ALWAYS) {
266         OONF_ASSERT(mpr_is_mpr(graph, &node_n1->addr), LOG_MPR, "WILLINGNESS_ALWAYS Node is no MPR");
267       }
268     }
269   }
270
271   avl_for_each_element(&graph->set_n2, n2_addr, _avl_node) {
272     d_y_n1 = mpr_calculate_d_of_y_s(domain, graph, n2_addr, &graph->set_n1);
273     d_y_mpr = mpr_calculate_d_of_y_s(domain, graph, n2_addr, &graph->set_mpr);
274
275     OONF_DEBUG(LOG_MPR, "d_y_n1 = %u", d_y_n1);
276     OONF_DEBUG(LOG_MPR, "d_y_mpr = %u", d_y_mpr);
277
278     /*
279      * Second property: For any y in N2 that does not have a defined d1(y),
280      * there is at least one element in M that is also in N1(y). This is
281      * equivalent to the requirement that d(y, M) is defined.
282      */
283     OONF_ASSERT(d_y_mpr < RFC7181_METRIC_INFINITE_PATH, LOG_MPR, "d_y path length %u is more than infinite", d_y_mpr);
284
285     /*
286      * Third property: For any y in N2, d(y,M) = d(y, N1).
287      */
288     OONF_ASSERT(d_y_mpr == d_y_n1, LOG_MPR, "d_y_path length %u should be %u", d_y_mpr, d_y_n1);
289   }
290 }
291 #endif