Merge branch 'master' into mpr_rework
[oonf.git] / src-plugins / nhdp / nhdp / nhdp_db.h
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 #ifndef NHDP_DB_H_
47 #define NHDP_DB_H_
48
49 struct nhdp_neighbor;
50 struct nhdp_link;
51 struct nhdp_l2hop;
52 struct nhdp_laddr;
53
54 #include "common/common_types.h"
55 #include "common/avl.h"
56 #include "common/list.h"
57 #include "common/netaddr.h"
58 #include "subsystems/oonf_rfc5444.h"
59 #include "subsystems/oonf_timer.h"
60
61 #include "nhdp/nhdp.h"
62
63 /*! memory class for NHDP links */
64 #define NHDP_CLASS_LINK             "nhdp_link"
65
66 /*! memory class for NHDP link address */
67 #define NHDP_CLASS_LINK_ADDRESS     "nhdp_laddr"
68
69 /*! memory class for NHDP 2hop link */
70 #define NHDP_CLASS_LINK_2HOP        "nhdp_l2hop"
71
72 /*! memory class for NHDP neighbor */
73 #define NHDP_CLASS_NEIGHBOR         "nhdp_neighbor"
74
75 /*! memory class for NHDP neighbor address */
76 #define NHDP_CLASS_NEIGHBOR_ADDRESS "nhdp_naddr"
77
78 /**
79  * link status of NHDP neighbors
80  */
81 enum nhdp_link_status {
82   /*! link is pending */
83   NHDP_LINK_PENDING   = -1,
84
85   /*! link is lost */
86   NHDP_LINK_LOST      = RFC6130_LINKSTATUS_LOST,
87
88   /*! link is symmetric */
89   NHDP_LINK_SYMMETRIC = RFC6130_LINKSTATUS_SYMMETRIC,
90
91   /*! link has been heard */
92   NHDP_LINK_HEARD     = RFC6130_LINKSTATUS_HEARD,
93 };
94
95 /**
96  * NHDP db constants
97  */
98 enum {
99   /*! maximum text length of link status */
100   NHDP_LINK_STATUS_TXTLENGTH = 10
101 };
102
103 /**
104  * Represents a NHDP link metric pair
105  */
106 struct nhdp_metric {
107   /*! incoming link metric cost */
108   uint32_t in;
109
110   /*! outgoing link metric cost */
111   uint32_t out;
112 };
113
114 /**
115  * Data for one NHDP domain of a link
116  */
117 struct nhdp_link_domaindata {
118   /*! incoming and outgoing metric cost */
119   struct nhdp_metric metric;
120
121   /*! time when this metric value was changed */
122   uint64_t last_metric_change;
123 };
124
125 /**
126  * Data for one NHDP domain of a neighbor
127  */
128 struct nhdp_neighbor_domaindata {
129   /*! incoming and outgoing metric cost */
130   struct nhdp_metric metric;
131
132   /*! pointer to the best link available to the neighbor */
133   struct nhdp_link *best_out_link;
134
135   /*! outgoing link metric of the best link */
136   uint32_t best_out_link_metric;
137
138   /*! interface index for the best link available to the neighbor */
139   unsigned best_link_ifindex;
140
141   /*! true if the local router has been selected as a MPR by the neighbor */
142   bool local_is_mpr;
143
144   /*! true if the neighbor has been selected as a MPR by this router */
145   bool neigh_is_mpr;
146
147   /*! true if the neighbor was a MPR of this router before the MPR recalculation */
148   bool _neigh_was_mpr;
149
150   /*! Routing willingness of neighbor */
151   uint8_t willingness;
152 };
153
154 /**
155  * Data for one NHDP domain of a 2-hop neighbor
156  */
157 struct nhdp_l2hop_domaindata {
158   /*! incoming and outgoing metric */
159   struct nhdp_metric metric;
160
161   /*! metric used for last MPR calculation */
162   uint32_t _last_used_outgoing_metric;
163 };
164
165 /**
166  * nhdl_link represents a link by a specific local interface to one interface
167  * of a one-hop neighbor.
168  */
169 struct nhdp_link {
170   /*! last received validity time */
171   uint64_t vtime_value;
172
173   /*! last received interval time */
174   uint64_t itime_value;
175
176   /*! timer that fires if this link is not symmetric anymore */
177   struct oonf_timer_instance sym_time;
178
179   /*! timer that fires if the last received neighbor HELLO timed out */
180   struct oonf_timer_instance heard_time;
181
182   /*! timer that fires when the link has to be removed from the database */
183   struct oonf_timer_instance vtime;
184
185   /*! last status of the linked, used to detect status changes */
186   enum nhdp_link_status last_status;
187
188   /*! cached status of the linked */
189   enum nhdp_link_status status;
190
191   /*! pointer to local interface for this link */
192   struct nhdp_interface *local_if;
193
194   /*! pointer to other (dualstack) representation of this link */
195   struct nhdp_link *dualstack_partner;
196
197   /*! pointer to neighbor entry of the other side of the link */
198   struct nhdp_neighbor *neigh;
199
200   /*! interface address used for NHDP of remote link end */
201   struct netaddr if_addr;
202
203   /*! mac address of remote link end */
204   struct netaddr remote_mac;
205
206   /*! timestamp when the current link status was set */
207   uint64_t last_status_change;
208
209   /*! true if the local router has been selected as a MPR by the neighbor */
210   bool local_is_flooding_mpr;
211
212   /*! true if the neighbor has been selected as a MPR by this router */
213   bool neigh_is_flooding_mpr;
214
215   /*! Willingness of neighbor for flooding data */
216   uint8_t flooding_willingness;
217
218   /*! true if the neighbor has been selected as a MPR by this router */
219   bool _neigh_was_flooding_mpr;
220
221   /*! internal field for NHDP processing */
222   int _process_count;
223
224   /*! tree of local addresses of the other side of the link */
225   struct avl_tree _addresses;
226
227   /*! tree of two-hop addresses reachable through the other side of the link */
228   struct avl_tree _2hop;
229
230   /*! member entry for global list of nhdp links */
231   struct list_entity _global_node;
232
233   /*! member entry for nhdp links of local interface */
234   struct list_entity _if_node;
235
236   /*! member entry for nhdp links of neighbor node */
237   struct list_entity _neigh_node;
238
239   /*! optional member node for interface tree of originators */
240   struct avl_node _originator_node;
241
242   /*! Array of link metrics */
243   struct nhdp_link_domaindata _domaindata[NHDP_MAXIMUM_DOMAINS];
244 };
245
246 /**
247  * nhdp_laddr represents an interface address of a link
248  */
249 struct nhdp_laddr {
250   /*! links interface address */
251   struct netaddr link_addr;
252
253   /*! link entry for address */
254   struct nhdp_link *link;
255
256   /*! internal variable for NHDP processing */
257   bool _might_be_removed;
258
259   /*! member entry for addresses of neighbor link */
260   struct avl_node _link_node;
261
262   /*! member entry for addresss of neighbor */
263   struct avl_node _neigh_node;
264
265   /*! member entry for interface tree of link addresses */
266   struct avl_node _if_node;
267 };
268
269 /**
270  * nhdp_l2hop represents an address of a two-hop neighbor
271  */
272 struct nhdp_l2hop {
273   /*! address of two-hop neighbor */
274   struct netaddr twohop_addr;
275
276   /*! true if neighbor is on the same interface as the link */
277   bool same_interface;
278
279   /*! link entry for two-hop address */
280   struct nhdp_link *link;
281
282   /*! validity time for this address */
283   struct oonf_timer_instance _vtime;
284
285   /*! member entry for two-hop addresses of neighbor link */
286   struct avl_node _link_node;
287
288   /*! member entry for interface list of two-hop addresses */
289   struct avl_node _if_node;
290
291   /*! Array of link metrics */
292   struct nhdp_l2hop_domaindata _domaindata[NHDP_MAXIMUM_DOMAINS];
293 };
294
295 /**
296  * nhdp_neighbor represents a neighbor node (with one or multiple interfaces
297  */
298 struct nhdp_neighbor {
299   /*! originator address of this node, might by type AF_UNSPEC */
300   struct netaddr originator;
301
302   /*! number of links to this neighbor which are symmetric */
303   int symmetric;
304
305   /*! pointer to other (dualstack) representation of this neighbor */
306   struct nhdp_neighbor *dualstack_partner;
307
308   /*! internal field for NHDP processing */
309   int _process_count;
310
311   /*! true if the neighbor has been selected as an MPR during selection algorithm */
312   bool selection_is_mpr;
313
314   /*!
315    * originator address of this node before it was changed.
316    * Mostly used in CHANGE events
317    */
318   struct netaddr _old_originator;
319
320   /*! list of links for this neighbor */
321   struct list_entity _links;
322
323   /*! tree of addresses of this neighbor */
324   struct avl_tree _neigh_addresses;
325
326   /*! tree of addresses of this neighbors links */
327   struct avl_tree _link_addresses;
328
329   /*! member entry for global list of neighbors */
330   struct list_entity _global_node;
331
332   /*! optional member node for global tree of originators */
333   struct avl_node _originator_node;
334
335   /*! Array of link metrics */
336   struct nhdp_neighbor_domaindata _domaindata[NHDP_MAXIMUM_DOMAINS];
337 };
338
339 /**
340  * nhdp_naddr represents an address of a known 1-hop neighbor
341  * or a former (lost) address which will be removed soon
342  */
343 struct nhdp_naddr {
344   /*! neighbor interface address */
345   struct netaddr neigh_addr;
346
347   /*! backlink to neighbor */
348   struct nhdp_neighbor *neigh;
349
350   /*! link address usage counter */
351   int laddr_count;
352
353   /*! validity time for this address when its lost */
354   struct oonf_timer_instance _lost_vtime;
355
356   /*! member entry for neighbor address tree */
357   struct avl_node _neigh_node;
358
359   /*! member entry for global neighbor address tree */
360   struct avl_node _global_node;
361
362   /**
363    * temporary variables for NHDP Hello processing
364    * true if address is part of the local interface
365    */
366   bool _this_if;
367
368   /**
369    * temporary variables for NHDP Hello processing
370    * true if address is considered for removal
371    */
372   bool _might_be_removed;
373 };
374
375 void nhdp_db_init(void);
376 void nhdp_db_cleanup(void);
377
378 EXPORT struct nhdp_neighbor *nhdp_db_neighbor_add(void);
379 EXPORT void nhdp_db_neighbor_remove(struct nhdp_neighbor *);
380 EXPORT void nhdp_db_neighbor_set_unsymmetric(struct nhdp_neighbor *neigh);
381 EXPORT void nhdp_db_neighbor_join(struct nhdp_neighbor *, struct nhdp_neighbor *);
382 EXPORT struct nhdp_naddr *nhdp_db_neighbor_addr_add(struct nhdp_neighbor *, const struct netaddr *);
383 EXPORT void nhdp_db_neighbor_addr_remove(struct nhdp_naddr *);
384 EXPORT void nhdp_db_neighbor_addr_move(struct nhdp_neighbor *, struct nhdp_naddr *);
385 EXPORT void nhdp_db_neighbor_set_originator(struct nhdp_neighbor *, const struct netaddr *);
386 EXPORT void nhdp_db_neighbor_connect_dualstack(struct nhdp_neighbor *, struct nhdp_neighbor *);
387 EXPORT void nhdp_db_neigbor_disconnect_dualstack(struct nhdp_neighbor *neigh);
388 EXPORT uint32_t nhdp_db_neighbor_get_set_id(void);
389
390 EXPORT struct nhdp_link *nhdp_db_link_add(struct nhdp_neighbor *ipv4, struct nhdp_interface *ipv6);
391 EXPORT void nhdp_db_link_remove(struct nhdp_link *);
392 EXPORT void nhdp_db_link_set_unsymmetric(struct nhdp_link *lnk);
393 EXPORT struct nhdp_laddr *nhdp_db_link_addr_add(struct nhdp_link *, const struct netaddr*);
394 EXPORT void nhdp_db_link_addr_remove(struct nhdp_laddr *);
395 EXPORT void nhdp_db_link_addr_move(struct nhdp_link *, struct nhdp_laddr *);
396 EXPORT struct nhdp_l2hop *nhdp_db_link_2hop_add(
397     struct nhdp_link *, const struct netaddr *);
398 EXPORT void nhdp_db_link_2hop_remove(struct nhdp_l2hop *);
399 EXPORT void nhdp_db_link_connect_dualstack(struct nhdp_link *ipv4, struct nhdp_link *ipv6);
400 EXPORT void nhdp_db_link_disconnect_dualstack(struct nhdp_link *lnk);
401
402 EXPORT int _nhdp_db_link_calculate_status(struct nhdp_link *lnk);
403 EXPORT void nhdp_db_link_update_status(struct nhdp_link *);
404
405 EXPORT const char *nhdp_db_link_status_to_string(struct nhdp_link *);
406
407 EXPORT struct list_entity *nhdp_db_get_neigh_list(void);
408 EXPORT struct list_entity *nhdp_db_get_link_list(void);
409 EXPORT struct avl_tree *nhdp_db_get_naddr_tree(void);
410 EXPORT struct avl_tree *nhdp_db_get_neigh_originator_tree(void);
411
412 /**
413  * @param addr network address
414  * @return corresponding neighbor address object, NULL if not found
415  */
416 static INLINE struct nhdp_naddr *
417 nhdp_db_neighbor_addr_get(const struct netaddr *addr) {
418   struct nhdp_naddr *naddr;
419   return avl_find_element(nhdp_db_get_naddr_tree(), addr, naddr, _global_node);
420 }
421
422 /**
423  * @param originator originator address
424  * @return corresponding nhdp neighbor, NULL if not found
425  */
426 static INLINE struct nhdp_neighbor *
427 nhdp_db_neighbor_get_by_originator(const struct netaddr *originator) {
428   struct nhdp_neighbor *neigh;
429   return avl_find_element(nhdp_db_get_neigh_originator_tree(), originator, neigh, _originator_node);
430 }
431
432 /**
433  * @param lnk nhdp link
434  * @param addr network address
435  * @return corresponding link address object, NULL if not found
436  */
437 static INLINE struct nhdp_laddr *
438 nhdp_db_link_addr_get(const struct nhdp_link *lnk, const struct netaddr *addr) {
439   struct nhdp_laddr *laddr;
440   return avl_find_element(&lnk->_addresses, addr, laddr, _link_node);
441 }
442
443 /**
444  * @param lnk nhdp link
445  * @param addr network address
446  * @return corresponding link two-hop neighbor address, NULL If not found
447  */
448 static INLINE struct nhdp_l2hop *
449 ndhp_db_link_2hop_get(const struct nhdp_link *lnk, const struct netaddr *addr) {
450   struct nhdp_l2hop *l2hop;
451   return avl_find_element(&lnk->_2hop, addr, l2hop, _link_node);
452 }
453
454 /**
455  * Sets the validity time of a nhdp link
456  * @param lnk pointer to nhdp link
457  * @param vtime validity time in milliseconds
458  */
459 static INLINE void
460 nhdp_db_link_set_vtime(
461     struct nhdp_link *lnk, uint64_t vtime) {
462   oonf_timer_set(&lnk->vtime, vtime);
463 }
464
465 /**
466  * Sets the time until a NHDP link is not considered heard anymore
467  * @param lnk pointer to nhdp link
468  * @param htime heard time in milliseconds
469  */
470 static INLINE void
471 nhdp_db_link_set_heardtime(
472     struct nhdp_link *lnk, uint64_t htime) {
473   oonf_timer_set(&lnk->heard_time, htime);
474 }
475
476 /**
477  * Sets the time until a NHDP link is not considered symmetric anymore
478  * @param lnk pointer to nhdp link
479  * @param stime symmetric time in milliseconds
480  */
481 static INLINE void
482 nhdp_db_link_set_symtime(
483     struct nhdp_link *lnk, uint64_t stime) {
484   oonf_timer_set(&lnk->sym_time, stime);
485   nhdp_db_link_update_status(lnk);
486 }
487
488 /**
489  * Set the validity time of a two-hop neighbor
490  * @param l2hop nhdp link two-hop neighbor
491  * @param vtime new validity time
492  */
493 static INLINE void
494 nhdp_db_link_2hop_set_vtime(
495     struct nhdp_l2hop *l2hop, uint64_t vtime) {
496   oonf_timer_set(&l2hop->_vtime, vtime);
497 }
498
499 /**
500  * Define a neighbor address as lost
501  * @param naddr nhdp neighbor address
502  * @param vtime time until lost address gets purged from the database
503  */
504 static INLINE void
505 nhdp_db_neighbor_addr_set_lost(struct nhdp_naddr *naddr, uint64_t vtime) {
506   oonf_timer_set(&naddr->_lost_vtime, vtime);
507 }
508
509 /**
510  * Define a neighbor address as not lost anymore
511  * @param naddr nhdp neighbor address
512  */
513 static INLINE void
514 nhdp_db_neighbor_addr_not_lost(struct nhdp_naddr *naddr) {
515   oonf_timer_stop(&naddr->_lost_vtime);
516 }
517
518 /**
519  * @param naddr nhdp neighbor address
520  * @return true if address is lost, false otherwise
521  */
522 static INLINE bool
523 nhdp_db_neighbor_addr_is_lost(const struct nhdp_naddr *naddr) {
524   return oonf_timer_is_active(&naddr->_lost_vtime);
525 }
526
527 /**
528  * @param lnk pointer to NHDP link
529  * @return true if link is part of a dualstack link
530  */
531 static INLINE bool
532 nhdp_db_link_is_dualstack(const struct nhdp_link *lnk) {
533   return lnk->dualstack_partner != NULL;
534 }
535
536 /**
537  * @param lnk pointer to NHDP link
538  * @param af_type address family type
539  * @return true if link is part of a dualstack link with the specified
540  *   address family
541  */
542 static INLINE bool
543 nhdp_db_link_is_dualstack_type(const struct nhdp_link *lnk, int af_type) {
544   return nhdp_db_link_is_dualstack(lnk)
545       && netaddr_get_address_family(&lnk->neigh->originator) == af_type;
546 }
547
548 /**
549  * @param lnk pointer to NHDP link
550  * @return true if link is the IPv4 part of a dualstack link
551  */
552 static INLINE bool
553 nhdp_db_link_is_ipv4_dualstack(const struct nhdp_link *lnk) {
554   return nhdp_db_link_is_dualstack_type(lnk, AF_INET);
555 }
556
557 /**
558  * @param lnk pointer to NHDP link
559  * @return true if link is the IPv6 part of a dualstack link
560  */
561 static INLINE bool
562 nhdp_db_link_is_ipv6_dualstack(const struct nhdp_link *lnk) {
563   return nhdp_db_link_is_dualstack_type(lnk, AF_INET6);
564 }
565
566 /**
567  * @param neigh pointer to NHDP neighbor
568  * @param af_type address family type
569  * @return true if neighbor is part of a dualstack neighbor with the
570  *   specified address family
571  */
572 static INLINE bool
573 nhdp_db_neighbor_is_dualstack_type(const struct nhdp_neighbor *neigh, int af_type) {
574   return neigh->dualstack_partner != NULL
575       && netaddr_get_address_family(&neigh->originator) == af_type;
576 }
577
578 /**
579  * @param neigh pointer to NHDP neighbor
580  * @return true if neighbor is the IPv4 part of a dualstack neighbor
581  */
582 static INLINE bool
583 nhdp_db_neighbor_is_ipv4_dualstack(const struct nhdp_neighbor *neigh) {
584   return nhdp_db_neighbor_is_dualstack_type(neigh, AF_INET);
585 }
586
587 /**
588  * @param neigh pointer to NHDP neighbor
589  * @return true if neighbor is the IPv6 part of a dualstack neighbor
590  */
591 static INLINE bool
592 nhdp_db_neighbor_is_ipv6_dualstack(const struct nhdp_neighbor *neigh) {
593   return nhdp_db_neighbor_is_dualstack_type(neigh, AF_INET6);
594 }
595
596 static INLINE bool
597 nhdp_db_2hop_is_lost(const struct nhdp_l2hop *l2hop) {
598   return oonf_timer_is_active(&l2hop->_vtime);
599 }
600 #endif /* NHDP_DB_H_ */