Keep statistics of logged warnings
[oonf.git] / src-plugins / nhdp / mpr / neighbor-graph-flooding.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 "nhdp/nhdp.h"
47 #include "nhdp/nhdp_db.h"
48 #include "nhdp/nhdp_domain.h"
49 #include "nhdp/nhdp_interfaces.h"
50
51 #include "common/common_types.h"
52 #include "common/autobuf.h"
53 #include "common/avl.h"
54 #include "common/avl_comp.h"
55 #include "common/container_of.h"
56 #include "config/cfg_schema.h"
57 #include "core/oonf_logging.h"
58 #include "subsystems/oonf_class.h"
59 #include "subsystems/oonf_rfc5444.h"
60
61 #include "mpr/mpr_internal.h"
62 #include "mpr/neighbor-graph-flooding.h"
63 #include "mpr/neighbor-graph.h"
64 #include "mpr/mpr.h"
65
66 /* FIXME remove unneeded includes */
67
68 static uint32_t _calculate_d1_x(const struct nhdp_domain *domain, struct n1_node *x);
69 static uint32_t _calculate_d2_x_y(const struct nhdp_domain *domain,
70     struct n1_node *x, struct addr_node *y);
71 static uint32_t _calculate_d_x_y(const struct nhdp_domain *domain,
72     struct neighbor_graph *graph, struct n1_node *x, struct addr_node *y);
73 #if 0
74 static uint32_t _calculate_d1_of_y(struct mpr_flooding_data *data, struct addr_node *y);
75 #endif
76 static uint32_t _calculate_d1_x_of_n2_addr(const struct nhdp_domain *domain,
77     struct neighbor_graph *graph, struct addr_node *addr);
78 static void _calculate_n1(const struct nhdp_domain *domain, struct mpr_flooding_data *data);
79 static void _calculate_n2(const struct nhdp_domain *domain, struct mpr_flooding_data *data);
80
81 static bool _is_allowed_link_tuple(const struct nhdp_domain *domain,
82     struct nhdp_interface *current_interface, struct nhdp_link *lnk);
83 static uint32_t _get_willingness_n1(const struct nhdp_domain *, struct n1_node *node);
84
85 static struct neighbor_graph_interface _api_interface = {
86   .is_allowed_link_tuple     = _is_allowed_link_tuple,
87   .calculate_d1_x_of_n2_addr = _calculate_d1_x_of_n2_addr,
88   .calculate_d_x_y           = _calculate_d_x_y,
89   .calculate_d2_x_y          = _calculate_d2_x_y,
90   .get_willingness_n1        = _get_willingness_n1,
91 };
92
93 /**
94  * Check if a given tuple is "reachable" according to section 18.4
95  * @param mpr_data
96  * @param link
97  * @return 
98  */
99 static bool
100 _is_reachable_link_tuple(const struct nhdp_domain *domain,
101     struct nhdp_interface *current_interface, struct nhdp_link *lnk) {
102   struct nhdp_link_domaindata *linkdata;
103
104   linkdata = nhdp_domain_get_linkdata(domain, lnk);
105   if (lnk->local_if == current_interface
106       && linkdata->metric.out <= RFC7181_METRIC_MAX
107       && lnk->status == NHDP_LINK_SYMMETRIC) {
108     return true;
109   }
110   return false;
111 }
112
113 /**
114  * Check if a link tuple is "allowed" according to section 18.4
115  * @param mpr_data
116  * @param link
117  * @return 
118  */
119 static bool
120 _is_allowed_link_tuple(const struct nhdp_domain *domain,
121     struct nhdp_interface *current_interface, struct nhdp_link *lnk) {
122   if (_is_reachable_link_tuple(domain, current_interface, lnk)
123       && lnk->neigh->flooding_willingness > RFC7181_WILLINGNESS_NEVER) {
124     return true;
125   }
126   return false;
127 }
128
129 static bool
130 _is_allowed_2hop_tuple(const struct nhdp_domain *domain,
131     struct nhdp_interface *current_interface, struct nhdp_l2hop *two_hop) {
132   struct nhdp_l2hop_domaindata *twohopdata;
133
134   twohopdata = nhdp_domain_get_l2hopdata(domain, two_hop);
135   if (two_hop->link->local_if == current_interface
136       && twohopdata->metric.out <= RFC7181_METRIC_MAX) {
137     return true;
138   }
139   return false;
140 }
141
142 static uint32_t
143 _calculate_d1_x(const struct nhdp_domain *domain, struct n1_node *x) {
144   struct nhdp_link_domaindata *linkdata;
145
146   linkdata = nhdp_domain_get_linkdata(domain, x->link);
147   return linkdata->metric.out;
148 }
149
150 static uint32_t
151 _calculate_d2_x_y(const struct nhdp_domain *domain,
152     struct n1_node *x, struct addr_node *y) {
153   struct nhdp_l2hop *tmp_l2hop;
154   struct nhdp_l2hop_domaindata *twohopdata;
155
156   /* find the corresponding 2-hop entry, if it exists */
157   tmp_l2hop = avl_find_element(&x->link->_2hop,
158       &y->addr, tmp_l2hop, _link_node);
159   if (tmp_l2hop) {
160     twohopdata = nhdp_domain_get_l2hopdata(domain, tmp_l2hop);
161     return twohopdata->metric.out;
162   }
163   return RFC7181_METRIC_INFINITE;
164 }
165
166 static uint32_t
167 _calculate_d_x_y(const struct nhdp_domain *domain,
168     struct neighbor_graph *graph, struct n1_node *x, struct addr_node *y) {
169   uint32_t cost, cost1, cost2, idx;
170 #ifdef OONF_LOG_DEBUG_INFO
171   struct netaddr_str nbuf1, nbuf2;
172 #endif
173   
174   idx = x->table_offset + y->table_offset;
175   assert(graph->d_x_y_cache);
176   cost = graph->d_x_y_cache[idx];
177   if (!cost) {
178     cost1 = _calculate_d1_x(domain, x);
179     cost2 = _calculate_d2_x_y(domain, x, y);
180     if (cost1 > RFC7181_METRIC_MAX || cost2 > RFC7181_METRIC_MAX) {
181       cost = RFC7181_METRIC_INFINITE_PATH;
182     }
183     else {
184       cost = cost1 + cost2;
185     }
186     graph->d_x_y_cache[idx] = cost;
187     OONF_DEBUG(LOG_MPR, "d_x_y(%s,%s)=%u (%u,%u)",
188                netaddr_to_string(&nbuf1, &x->addr),
189                netaddr_to_string(&nbuf2, &y->addr),
190                cost,
191                x->table_offset, y->table_offset);
192   }
193   else {
194     OONF_DEBUG(LOG_MPR, "d_x_y(%s,%s)=%u cached(%u,%u)",
195          netaddr_to_string(&nbuf1, &x->addr),
196          netaddr_to_string(&nbuf2, &y->addr),
197          cost,
198          x->table_offset, y->table_offset);
199   }
200   return cost;
201 }
202
203 /**
204  * Calculate d1(x) according to section 18.2 (draft 19)
205  * @param mpr_data
206  * @param addr
207  * @return 
208  */
209 uint32_t
210 _calculate_d1_x_of_n2_addr(const struct nhdp_domain *domain,
211     struct neighbor_graph *graph, struct addr_node *addr) {
212   struct n1_node *node_n1;
213   struct nhdp_naddr *naddr;
214   struct nhdp_link_domaindata *linkdata;
215
216   // FIXME Implementation correct?!?!
217
218   avl_for_each_element(&graph->set_n1, node_n1, _avl_node) {
219     /* check if the address provided corresponds to this node */
220     naddr = avl_find_element(&node_n1->neigh->_neigh_addresses,
221         &addr->addr, naddr, _neigh_node);
222     if (naddr) {
223       linkdata = nhdp_domain_get_linkdata(domain, node_n1->link);
224       return linkdata->metric.out;
225     }
226   }
227
228   return RFC7181_METRIC_INFINITE;
229 }
230
231 /**
232  * Calculate N1
233  * @param interf
234  */
235 static void
236 _calculate_n1(const struct nhdp_domain *domain, struct mpr_flooding_data *data) {
237   struct nhdp_link *lnk;
238
239   OONF_DEBUG(LOG_MPR, "Calculate N1 (flooding) for interface %s",
240       nhdp_interface_get_name(data->current_interface));
241
242   list_for_each_element(nhdp_db_get_link_list(), lnk, _global_node) {
243     // Reset temporary selection state 
244     lnk->neigh->selection_is_mpr = false;
245     
246     if (_is_allowed_link_tuple(domain, data->current_interface, lnk)) {
247       mpr_add_n1_node_to_set(&data->neigh_graph.set_n1, lnk->neigh, lnk, 0);
248     }
249   }
250 }
251
252 /**
253  * Calculate N2
254  * 
255  * For every neighbor in N1, N2 contains a unique entry for every neighbor
256  * 2-hop neighbor address. The same address may be reachable via multiple
257  * 1-hop neighbors, but is only represented once in N2.
258  * 
259  * Note that N1 is generated per-interface, so we don't need to deal with 
260  * multiple links to the same N1 member.
261  * 
262  * @param set_n1 N1 Set
263  * @return 
264  */
265 static void
266 _calculate_n2(const struct nhdp_domain *domain, struct mpr_flooding_data *data) {
267   struct n1_node *n1_neigh;
268   struct nhdp_l2hop *twohop;
269
270   OONF_DEBUG(LOG_MPR, "Calculate N2 for flooding MPRs");
271
272   /* iterate over all two-hop neighbor addresses of N1 members */
273   avl_for_each_element(&data->neigh_graph.set_n1, n1_neigh, _avl_node) {
274     avl_for_each_element(&n1_neigh->link->_2hop, twohop, _link_node) {
275       if (_is_allowed_2hop_tuple(domain, data->current_interface, twohop)) {
276         mpr_add_addr_node_to_set(&data->neigh_graph.set_n2,
277             twohop->twohop_addr, 0);
278       }
279     }
280   }
281 }
282
283 /**
284  * Returns the flooding/routing willingness of an N1 neighbor
285  * @param not used
286  * @param node
287  * @return 
288  */
289 static uint32_t
290 _get_willingness_n1(const struct nhdp_domain *domain __attribute__((unused)),
291     struct n1_node *node) {
292   return node->neigh->flooding_willingness;
293 }
294
295 void
296 mpr_calculate_neighbor_graph_flooding(const struct nhdp_domain *domain, struct mpr_flooding_data *data) {
297   OONF_DEBUG(LOG_MPR, "Calculate neighbor graph for flooding MPRs");
298
299   mpr_init_neighbor_graph(&data->neigh_graph, &_api_interface);
300   _calculate_n1(domain, data);
301   _calculate_n2(domain, data);
302 }