Keep statistics of logged warnings
[oonf.git] / src-plugins / nhdp / nhdp / nhdp_db.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 "common/common_types.h"
47 #include "common/avl.h"
48 #include "common/avl_comp.h"
49 #include "common/list.h"
50 #include "common/netaddr.h"
51
52 #include "core/oonf_logging.h"
53 #include "subsystems/oonf_class.h"
54 #include "subsystems/oonf_timer.h"
55
56 #include "nhdp/nhdp_internal.h"
57 #include "nhdp/nhdp_hysteresis.h"
58 #include "nhdp/nhdp_interfaces.h"
59 #include "nhdp/nhdp_domain.h"
60 #include "nhdp/nhdp_db.h"
61
62 /* Prototypes of local functions */
63 static void _link_status_now_symmetric(struct nhdp_link *lnk);
64 static void _link_status_not_symmetric_anymore(struct nhdp_link *lnk);
65 int _nhdp_db_link_calculate_status(struct nhdp_link *lnk);
66
67 static void _cb_link_vtime(struct oonf_timer_instance *);
68 static void _cb_link_heard(struct oonf_timer_instance *);
69 static void _cb_link_symtime(struct oonf_timer_instance *);
70 static void _cb_l2hop_vtime(struct oonf_timer_instance *);
71 static void _cb_naddr_vtime(struct oonf_timer_instance *);
72
73 /* Link status names */
74 static const char *_LINK_PENDING   = "pending";
75 static const char *_LINK_HEARD     = "heard";
76 static const char *_LINK_SYMMETRIC = "symmetric";
77 static const char *_LINK_LOST      = "lost";
78
79 /* memory and timer classes necessary for NHDP */
80 static struct oonf_class _neigh_info = {
81   .name = NHDP_CLASS_NEIGHBOR,
82   .size = sizeof(struct nhdp_neighbor),
83 };
84
85 static struct oonf_class _link_info = {
86   .name = NHDP_CLASS_LINK,
87   .size = sizeof(struct nhdp_link),
88 };
89
90 static struct oonf_class _laddr_info = {
91   .name = NHDP_CLASS_LINK_ADDRESS,
92   .size = sizeof(struct nhdp_laddr),
93 };
94
95 static struct oonf_class _l2hop_info = {
96   .name = NHDP_CLASS_LINK_2HOP,
97   .size = sizeof(struct nhdp_l2hop),
98 };
99
100 static struct oonf_class _naddr_info = {
101   .name = NHDP_CLASS_NEIGHBOR_ADDRESS,
102   .size = sizeof(struct nhdp_naddr),
103 };
104
105 static struct oonf_timer_class _link_vtime_info = {
106   .name = "NHDP link vtime",
107   .callback = _cb_link_vtime,
108 };
109
110 static struct oonf_timer_class _link_heard_info = {
111   .name = "NHDP link heard-time",
112   .callback = _cb_link_heard,
113 };
114
115 static struct oonf_timer_class _link_symtime_info = {
116   .name = "NHDP link symtime",
117   .callback = _cb_link_symtime,
118 };
119
120 static struct oonf_timer_class _naddr_vtime_info = {
121   .name = "NHDP neighbor address vtime",
122   .callback = _cb_naddr_vtime,
123 };
124
125 static struct oonf_timer_class _l2hop_vtime_info = {
126   .name = "NHDP 2hop vtime",
127   .callback = _cb_l2hop_vtime,
128 };
129
130 /* global tree of neighbor addresses */
131 static struct avl_tree _naddr_tree;
132
133 /* list of neighbors */
134 static struct list_entity _neigh_list;
135
136 /* tree of neighbors with originator addresses */
137 static struct avl_tree _neigh_originator_tree;
138
139 /* list of links (to neighbors) */
140 static struct list_entity _link_list;
141
142 /* id that will be increased every times the symmetric neighbor set changes */
143 static uint32_t _neighbor_set_id = 0;
144
145 /**
146  * Initialize NHDP databases
147  */
148 void
149 nhdp_db_init(void) {
150   avl_init(&_naddr_tree, avl_comp_netaddr, false);
151   list_init_head(&_neigh_list);
152   avl_init(&_neigh_originator_tree, avl_comp_netaddr, false);
153   list_init_head(&_link_list);
154
155   oonf_class_add(&_neigh_info);
156   oonf_class_add(&_naddr_info);
157   oonf_class_add(&_link_info);
158   oonf_class_add(&_laddr_info);
159   oonf_class_add(&_l2hop_info);
160
161   oonf_timer_add(&_naddr_vtime_info);
162   oonf_timer_add(&_link_vtime_info);
163   oonf_timer_add(&_link_heard_info);
164   oonf_timer_add(&_link_symtime_info);
165   oonf_timer_add(&_l2hop_vtime_info);
166 }
167
168 /**
169  * Cleanup NHDP databases
170  */
171 void
172 nhdp_db_cleanup(void) {
173   struct nhdp_neighbor *neigh, *n_it;
174
175   /* remove all neighbors */
176   list_for_each_element_safe(&_neigh_list, neigh, _global_node, n_it) {
177     nhdp_db_neighbor_remove(neigh);
178   }
179
180   /* cleanup all timers */
181   oonf_timer_remove(&_l2hop_vtime_info);
182   oonf_timer_remove(&_link_symtime_info);
183   oonf_timer_remove(&_link_heard_info);
184   oonf_timer_remove(&_link_vtime_info);
185   oonf_timer_remove(&_naddr_vtime_info);
186
187   /* cleanup all memory cookies */
188   oonf_class_remove(&_l2hop_info);
189   oonf_class_remove(&_laddr_info);
190   oonf_class_remove(&_link_info);
191   oonf_class_remove(&_naddr_info);
192   oonf_class_remove(&_neigh_info);
193 }
194
195 /**
196  * @return new NHDP neighbor without links and addresses,
197  *  NULL if out of memory
198  */
199 struct nhdp_neighbor *
200 nhdp_db_neighbor_add(void) {
201   struct nhdp_neighbor *neigh;
202
203   neigh = oonf_class_malloc(&_neigh_info);
204   if (neigh == NULL) {
205     return NULL;
206   }
207
208   OONF_DEBUG(LOG_NHDP, "New Neighbor: 0x%0zx", (size_t)neigh);
209
210   /* initialize trees and lists */
211   avl_init(&neigh->_neigh_addresses, avl_comp_netaddr, false);
212   avl_init(&neigh->_link_addresses, avl_comp_netaddr, true);
213   list_init_head(&neigh->_links);
214
215   /* hook into global neighbor list */
216   list_add_tail(&_neigh_list, &neigh->_global_node);
217
218   /* initialize originator node */
219   neigh->_originator_node.key = &neigh->originator;
220
221   /* initialize domain data */
222   nhdp_domain_init_neighbor(neigh);
223
224   /* trigger event */
225   oonf_class_event(&_neigh_info, neigh, OONF_OBJECT_ADDED);
226   return neigh;
227 }
228
229 /**
230  * Remove NHDP neighbor including links and addresses from db
231  * @param neigh nhdp neighbor to be removed
232  */
233 void
234 nhdp_db_neighbor_remove(struct nhdp_neighbor *neigh) {
235   struct nhdp_naddr *naddr, *na_it;
236   struct nhdp_link *lnk, *l_it;
237 #ifdef OONF_LOG_DEBUG_INFO
238   struct netaddr_str nbuf;
239 #endif
240
241   OONF_DEBUG(LOG_NHDP, "Remove Neighbor: 0x%0zx (%s)",
242       (size_t)neigh, netaddr_to_string(&nbuf, &neigh->originator));
243
244   /* trigger event */
245   oonf_class_event(&_neigh_info, neigh, OONF_OBJECT_REMOVED);
246
247   /* disconnect from other IP version */
248   nhdp_db_neigbor_disconnect_dualstack(neigh);
249
250   /* remove all links */
251   list_for_each_element_safe(&neigh->_links, lnk, _neigh_node, l_it) {
252     nhdp_db_link_remove(lnk);
253   }
254
255   /* remove all neighbor addresses */
256   avl_for_each_element_safe(&neigh->_neigh_addresses, naddr, _neigh_node, na_it) {
257     nhdp_db_neighbor_addr_remove(naddr);
258   }
259
260   /* remove from originator tree if necessary */
261   if (netaddr_get_address_family(&neigh->originator) != AF_UNSPEC) {
262     avl_remove(&_neigh_originator_tree, &neigh->_originator_node);
263   }
264
265   /* remove from global list and free memory */
266   list_remove(&neigh->_global_node);
267   oonf_class_free(&_neigh_info, neigh);
268 }
269
270 /**
271  * Set a NHDP neighbor to unsymmetric
272  * @param neigh nhdp neighbor
273  */
274 void
275 nhdp_db_neighbor_set_unsymmetric(struct nhdp_neighbor *neigh) {
276   struct nhdp_link *lnk;
277
278   list_for_each_element(&neigh->_links, lnk, _neigh_node) {
279     nhdp_db_link_set_unsymmetric(lnk);
280   }
281
282   /* trigger event */
283   oonf_class_event(&_neigh_info, neigh, OONF_OBJECT_CHANGED);
284 }
285
286 /**
287  * Join the links and addresses of two NHDP neighbors
288  * @param dst target neighbor which gets all the links and addresses
289  * @param src source neighbor which will be removed afterwards
290  */
291 void
292 nhdp_db_neighbor_join(struct nhdp_neighbor *dst, struct nhdp_neighbor *src) {
293   struct nhdp_naddr *naddr, *na_it;
294   struct nhdp_link *lnk, *l_it;
295   struct nhdp_laddr *laddr, *la_it;
296
297   if (dst == src) {
298     return;
299   }
300
301   /* fix symmetric link count */
302   dst->symmetric += src->symmetric;
303
304   /* move links */
305   list_for_each_element_safe(&src->_links, lnk, _neigh_node, l_it) {
306     /* more addresses to new neighbor */
307     avl_for_each_element_safe(&lnk->_addresses, laddr, _neigh_node, la_it) {
308       avl_remove(&src->_link_addresses, &laddr->_neigh_node);
309       avl_insert(&dst->_link_addresses, &laddr->_neigh_node);
310     }
311
312     /* move interface based originator */
313     if (netaddr_get_address_family(&src->originator) != AF_UNSPEC) {
314       avl_remove(&lnk->local_if->_link_originators, &lnk->_originator_node);
315     }
316     lnk->_originator_node.key = &dst->originator;
317     if (netaddr_get_address_family(&dst->originator) != AF_UNSPEC) {
318       avl_insert(&lnk->local_if->_link_originators, &lnk->_originator_node);
319     }
320
321     /* move link to new neighbor */
322     list_remove(&lnk->_neigh_node);
323     list_add_tail(&dst->_links, &lnk->_neigh_node);
324     lnk->neigh = dst;
325   }
326
327   /* move neighbor addresses to target */
328   avl_for_each_element_safe(&src->_neigh_addresses, naddr, _neigh_node, na_it) {
329     /* move address to new neighbor */
330     avl_remove(&src->_neigh_addresses, &naddr->_neigh_node);
331     avl_insert(&dst->_neigh_addresses, &naddr->_neigh_node);
332     naddr->neigh = dst;
333   }
334
335   nhdp_db_neighbor_remove(src);
336 }
337
338 /**
339  * Adds an address to a nhdp neighbor
340  * @param neigh nhdp neighbor
341  * @param addr network address
342  * @return pointer to neighbor address, NULL if out of memory
343  */
344 struct nhdp_naddr *
345 nhdp_db_neighbor_addr_add(struct nhdp_neighbor *neigh,
346     const struct netaddr *addr) {
347   struct nhdp_naddr *naddr;
348
349   naddr = oonf_class_malloc(&_naddr_info);
350   if (naddr == NULL) {
351     return NULL;
352   }
353
354   /* initialize key */
355   memcpy(&naddr->neigh_addr, addr, sizeof(naddr->neigh_addr));
356   naddr->_neigh_node.key = &naddr->neigh_addr;
357   naddr->_global_node.key = &naddr->neigh_addr;
358
359   /* initialize backward link */
360   naddr->neigh = neigh;
361
362   /* initialize timer for lost addresses */
363   naddr->_lost_vtime.class = &_naddr_vtime_info;
364
365   /* add to trees */
366   avl_insert(&_naddr_tree, &naddr->_global_node);
367   avl_insert(&neigh->_neigh_addresses, &naddr->_neigh_node);
368
369   /* trigger event */
370   oonf_class_event(&_naddr_info, naddr, OONF_OBJECT_ADDED);
371
372   return naddr;
373 }
374
375 /**
376  * Removes a nhdp neighbor address from its neighbor
377  * @param naddr neighbor address
378  */
379 void
380 nhdp_db_neighbor_addr_remove(struct nhdp_naddr *naddr) {
381   /* trigger event */
382   oonf_class_event(&_naddr_info, naddr, OONF_OBJECT_REMOVED);
383
384   /* remove from trees */
385   avl_remove(&_naddr_tree, &naddr->_global_node);
386   avl_remove(&naddr->neigh->_neigh_addresses, &naddr->_neigh_node);
387
388   /* stop timer */
389   oonf_timer_stop(&naddr->_lost_vtime);
390
391   /* free memory */
392   oonf_class_free(&_naddr_info, naddr);
393 }
394
395 /**
396  * Moves a nhdp neighbor address to a different neighbor
397  * @param neigh
398  * @param naddr
399  */
400 void
401 nhdp_db_neighbor_addr_move(struct nhdp_neighbor *neigh, struct nhdp_naddr *naddr) {
402   /* remove from old neighbor */
403   avl_remove(&naddr->neigh->_neigh_addresses, &naddr->_neigh_node);
404
405   /* add to new neighbor */
406   avl_insert(&neigh->_neigh_addresses, &naddr->_neigh_node);
407
408   /* set new backlink */
409   naddr->neigh = neigh;
410 }
411
412 /**
413  * Sets a new originator address for an NHDP neighbor
414  * @param neigh nhdp neighbor
415  * @param originator originator address, might be type AF_UNSPEC
416  */
417 void
418 nhdp_db_neighbor_set_originator(struct nhdp_neighbor *neigh,
419     const struct netaddr *originator) {
420   struct nhdp_neighbor *neigh2;
421   struct nhdp_link *lnk;
422
423   if (memcmp(&neigh->originator, originator, sizeof(*originator)) == 0) {
424     /* same originator, nothing to do */
425     return;
426   }
427
428   if (netaddr_get_address_family(&neigh->originator) != AF_UNSPEC) {
429     /* different originator, remove from tree */
430     avl_remove(&_neigh_originator_tree, &neigh->_originator_node);
431
432     list_for_each_element(&neigh->_links, lnk, _neigh_node) {
433       /* remove links from interface specific tree */
434       avl_remove(&lnk->local_if->_link_originators, &lnk->_originator_node);
435     }
436   }
437
438   neigh2 = nhdp_db_neighbor_get_by_originator(originator);
439   if (neigh2) {
440     /* different neighbor has this originator, invalidate it */
441     avl_remove(&_neigh_originator_tree, &neigh2->_originator_node);
442
443     list_for_each_element(&neigh2->_links, lnk, _neigh_node) {
444       /* remove links from interface specific tree */
445       avl_remove(&lnk->local_if->_link_originators, &lnk->_originator_node);
446     }
447
448     netaddr_invalidate(&neigh2->originator);
449   }
450
451   /* copy originator address into neighbor */
452   memcpy(&neigh->originator, originator, sizeof(*originator));
453
454   if (netaddr_get_address_family(originator) != AF_UNSPEC) {
455     /* add to tree if new originator is valid */
456     avl_insert(&_neigh_originator_tree, &neigh->_originator_node);
457
458     list_for_each_element(&neigh->_links, lnk, _neigh_node) {
459       /* remove links from interface specific tree */
460       avl_insert(&lnk->local_if->_link_originators, &lnk->_originator_node);
461     }
462   }
463
464   /* inform everyone */
465   oonf_class_event(&_neigh_info, neigh, OONF_OBJECT_CHANGED);
466
467   /* overwrite "old originator" */
468   memcpy(&neigh->_old_originator, originator, sizeof(*originator));
469 }
470
471 /**
472  * Connect two neighbors as representations of the same node,
473  * @param n_ipv4 ipv4 neighbor
474  * @param n_ipv6 ipv6 neighbor
475  */
476 void
477 nhdp_db_neighbor_connect_dualstack(
478     struct nhdp_neighbor *n_ipv4, struct nhdp_neighbor *n_ipv6) {
479
480   if (n_ipv4->dualstack_partner != n_ipv6) {
481     nhdp_db_neigbor_disconnect_dualstack(n_ipv4);
482     n_ipv4->dualstack_partner = n_ipv6;
483   }
484
485   if (n_ipv6->dualstack_partner != n_ipv4) {
486     nhdp_db_neigbor_disconnect_dualstack(n_ipv6);
487     n_ipv6->dualstack_partner = n_ipv4;
488   }
489 }
490
491 /**
492  * Disconnects the pointers of a dualstack pair of neighbors
493  * @param neigh one of the connected neighbors
494  */
495 void
496 nhdp_db_neigbor_disconnect_dualstack(struct nhdp_neighbor *neigh) {
497   if (neigh->dualstack_partner) {
498     neigh->dualstack_partner->dualstack_partner = NULL;
499     neigh->dualstack_partner = NULL;
500   }
501 }
502
503 /**
504  * @return set id of symmetric neighbors, will be increased for
505  *   every change.
506  */
507 uint32_t
508 nhdp_db_neighbor_get_set_id(void) {
509   return _neighbor_set_id;
510 }
511
512 /**
513  * Insert a new link into a nhdp neighbors database
514  * @param neigh neighbor which will get the new link
515  * @param local_if local interface through which the link was heard
516  * @return new nhdp link, NULL if out of memory
517  */
518 struct nhdp_link *
519 nhdp_db_link_add(struct nhdp_neighbor *neigh, struct nhdp_interface *local_if) {
520   struct nhdp_link *lnk;
521
522   lnk = oonf_class_malloc(&_link_info);
523   if (lnk == NULL) {
524     return NULL;
525   }
526
527   /* hook into interface */
528   nhdp_interface_add_link(local_if, lnk);
529
530   /* hook into neighbor */
531   list_add_tail(&neigh->_links, &lnk->_neigh_node);
532   lnk->neigh = neigh;
533
534   /* hook into global list */
535   list_add_tail(&_link_list, &lnk->_global_node);
536
537   /* init local trees */
538   avl_init(&lnk->_addresses, avl_comp_netaddr, false);
539   avl_init(&lnk->_2hop, avl_comp_netaddr, false);
540
541   /* init timers */
542   lnk->sym_time.class = &_link_symtime_info;
543   lnk->heard_time.class = &_link_heard_info;
544   lnk->vtime.class = &_link_vtime_info;
545
546   /* add to originator tree if set */
547   lnk->_originator_node.key = &neigh->originator;
548   if (netaddr_get_address_family(&neigh->originator) != AF_UNSPEC) {
549     avl_insert(&local_if->_link_originators, &lnk->_originator_node);
550   }
551
552   lnk->last_status_change = oonf_clock_getNow();
553
554   /* initialize link domain data */
555   nhdp_domain_init_link(lnk);
556
557   /* trigger event */
558   oonf_class_event(&_link_info, lnk, OONF_OBJECT_ADDED);
559
560   return lnk;
561 }
562
563 /**
564  * Remove a nhdp link from database
565  * @param lnk nhdp link to be removed
566  */
567 void
568 nhdp_db_link_set_unsymmetric(struct nhdp_link *lnk) {
569   struct nhdp_l2hop *twohop, *th_it;
570
571   if (lnk->status == NHDP_LINK_SYMMETRIC) {
572     _link_status_not_symmetric_anymore(lnk);
573   }
574
575   /* stop link timers */
576   oonf_timer_stop(&lnk->sym_time);
577
578   /* remove all 2hop addresses */
579   avl_for_each_element_safe(&lnk->_2hop, twohop, _link_node, th_it) {
580     nhdp_db_link_2hop_remove(twohop);
581   }
582
583   /* link status was changed */
584   lnk->last_status_change = oonf_clock_getNow();
585
586   /* trigger event */
587   oonf_class_event(&_link_info, lnk, OONF_OBJECT_CHANGED);
588 }
589
590 /**
591  * Remove a link from the nhdp database
592  * @param lnk nhdp link
593  */
594 void
595 nhdp_db_link_remove(struct nhdp_link *lnk) {
596   struct nhdp_laddr *laddr, *la_it;
597   struct nhdp_l2hop *twohop, *th_it;
598
599   /* trigger event */
600   oonf_class_event(&_link_info, lnk, OONF_OBJECT_REMOVED);
601
602   oonf_timer_stop(&lnk->sym_time);
603   oonf_timer_stop(&lnk->heard_time);
604   oonf_timer_stop(&lnk->vtime);
605
606   /* disconnect dualstack */
607   if (nhdp_db_link_is_dualstack(lnk)) {
608     nhdp_db_link_disconnect_dualstack(lnk);
609   }
610
611   if (netaddr_get_address_family(&lnk->neigh->originator) != AF_UNSPEC) {
612     avl_remove(&lnk->local_if->_link_originators, &lnk->_originator_node);
613   }
614
615   /* detach all addresses */
616   avl_for_each_element_safe(&lnk->_addresses, laddr, _link_node, la_it) {
617     nhdp_db_link_addr_remove(laddr);
618   }
619
620   /* remove all 2hop addresses */
621   avl_for_each_element_safe(&lnk->_2hop, twohop, _link_node, th_it) {
622     nhdp_db_link_2hop_remove(twohop);
623   }
624
625   /* unlink */
626   nhdp_interface_remove_link(lnk);
627   list_remove(&lnk->_neigh_node);
628
629   /* remove from global list */
630   list_remove(&lnk->_global_node);
631
632   /* free memory */
633   oonf_class_free(&_link_info, lnk);
634 }
635
636 /**
637  * Add a network address as a link address to a nhdp link
638  * @param lnk nhpd link
639  * @param addr network address
640  * @return nhdp link address, NULL if out of memory
641  */
642 struct nhdp_laddr *
643 nhdp_db_link_addr_add(struct nhdp_link *lnk, const struct netaddr *addr) {
644   struct nhdp_laddr *laddr;
645
646   laddr = oonf_class_malloc(&_laddr_info);
647   if (laddr == NULL) {
648     return NULL;
649   }
650
651   /* initialize key */
652   memcpy(&laddr->link_addr, addr, sizeof(laddr->link_addr));
653   laddr->_link_node.key = &laddr->link_addr;
654   laddr->_neigh_node.key = &laddr->link_addr;
655   laddr->_if_node.key = &laddr->link_addr;
656
657   /* initialize back link */
658   laddr->link = lnk;
659
660   /* add to trees */
661   avl_insert(&lnk->_addresses, &laddr->_link_node);
662   avl_insert(&lnk->neigh->_link_addresses, &laddr->_neigh_node);
663   nhdp_interface_add_laddr(laddr);
664
665   /* trigger event */
666   oonf_class_event(&_laddr_info, laddr, OONF_OBJECT_ADDED);
667
668   return laddr;
669 }
670
671 /**
672  * Removes a nhdp link address from its link
673  * @param laddr nhdp link address
674  */
675 void
676 nhdp_db_link_addr_remove(struct nhdp_laddr *laddr) {
677   /* trigger event */
678   oonf_class_event(&_laddr_info, laddr, OONF_OBJECT_REMOVED);
679
680   /* remove from trees */
681   nhdp_interface_remove_laddr(laddr);
682   avl_remove(&laddr->link->_addresses, &laddr->_link_node);
683   avl_remove(&laddr->link->neigh->_link_addresses, &laddr->_neigh_node);
684
685   /* free memory */
686   oonf_class_free(&_laddr_info, laddr);
687 }
688
689 /**
690  * Moves a nhdp link address to a different link
691  * @param lnk
692  * @param laddr
693  */
694 void
695 nhdp_db_link_addr_move(struct nhdp_link *lnk, struct nhdp_laddr *laddr) {
696   /* remove from old link */
697   avl_remove(&laddr->link->_addresses, &laddr->_link_node);
698
699   /* add to new neighbor */
700   avl_insert(&lnk->_addresses, &laddr->_link_node);
701
702   if (laddr->link->neigh != lnk->neigh) {
703     /* remove from old neighbor */
704     avl_remove(&laddr->link->neigh->_link_addresses, &laddr->_neigh_node);
705
706     /* add to new neighbor */
707     avl_insert(&lnk->neigh->_link_addresses, &laddr->_neigh_node);
708   }
709   /* set new backlink */
710   laddr->link = lnk;
711 }
712
713 /**
714  * Adds a network address as a 2-hop neighbor to a nhdp link
715  * @param lnk nhdp link
716  * @param addr network address
717  * @return nhdp link two-hop neighbor
718  */
719 struct nhdp_l2hop *
720 nhdp_db_link_2hop_add(struct nhdp_link *lnk, const struct netaddr *addr) {
721   struct nhdp_l2hop *l2hop;
722
723   l2hop = oonf_class_malloc(&_l2hop_info);
724   if (l2hop == NULL) {
725     return NULL;
726   }
727
728   /* initialize key */
729   memcpy(&l2hop->twohop_addr, addr, sizeof(l2hop->twohop_addr));
730   l2hop->_link_node.key = &l2hop->twohop_addr;
731
732   /* initialize back link */
733   l2hop->link = lnk;
734
735   /* initialize validity timer */
736   l2hop->_vtime.class = &_l2hop_vtime_info;
737
738   /* add to link tree */
739   avl_insert(&lnk->_2hop, &l2hop->_link_node);
740
741   /* add to interface tree */
742   nhdp_interface_add_l2hop(lnk->local_if, l2hop);
743
744   /* initialize metrics */
745   nhdp_domain_init_l2hop(l2hop);
746
747   /* trigger event */
748   oonf_class_event(&_l2hop_info, l2hop, OONF_OBJECT_ADDED);
749
750   return l2hop;
751 }
752
753 /**
754  * Removes a two-hop address from a nhdp link
755  * @param l2hop nhdp two-hop link address
756  */
757 void
758 nhdp_db_link_2hop_remove(struct nhdp_l2hop *l2hop) {
759   /* trigger event */
760   oonf_class_event(&_l2hop_info, l2hop, OONF_OBJECT_REMOVED);
761
762   /* remove from link tree */
763   avl_remove(&l2hop->link->_2hop, &l2hop->_link_node);
764
765   /* remove from interface tree */
766   nhdp_interface_remove_l2hop(l2hop);
767
768   /* stop validity timer */
769   oonf_timer_stop(&l2hop->_vtime);
770
771   /* free memory */
772   oonf_class_free(&_l2hop_info, l2hop);
773 }
774
775 /**
776  * Connect two links as representations of the same node,
777  * @param l_ipv4 ipv4 link
778  * @param l_ipv6 ipv6 link
779  */
780 void
781 nhdp_db_link_connect_dualstack(
782     struct nhdp_link *l_ipv4, struct nhdp_link *l_ipv6) {
783
784   if (l_ipv4->dualstack_partner != l_ipv6) {
785     nhdp_db_link_disconnect_dualstack(l_ipv4);
786     l_ipv4->dualstack_partner = l_ipv6;
787   }
788
789   if (l_ipv6->dualstack_partner != l_ipv4) {
790     nhdp_db_link_disconnect_dualstack(l_ipv6);
791     l_ipv6->dualstack_partner = l_ipv4;
792   }
793 }
794
795 /**
796  * Disconnects the pointers of a dualstack pair of links
797  * @param lnk one of the connected links
798  */
799 void
800 nhdp_db_link_disconnect_dualstack(struct nhdp_link *lnk) {
801   if (lnk->dualstack_partner) {
802     lnk->dualstack_partner->dualstack_partner = NULL;
803     lnk->dualstack_partner = NULL;
804   }
805 }
806
807 /**
808  * Recalculate the status of a nhdp link and update database
809  * if link changed between symmetric and non-symmetric
810  * @param lnk nhdp link with (potential) new status
811  */
812 void
813 nhdp_db_link_update_status(struct nhdp_link *lnk) {
814   enum nhdp_link_status old_status;
815   bool was_symmetric;
816
817   old_status = lnk->status;
818   was_symmetric = lnk->status == NHDP_LINK_SYMMETRIC;
819
820   /* update link status */
821   lnk->status = _nhdp_db_link_calculate_status(lnk);
822
823   /* handle database changes */
824   if (was_symmetric && lnk->status != NHDP_LINK_SYMMETRIC) {
825     _link_status_not_symmetric_anymore(lnk);
826   }
827   if (!was_symmetric && lnk->status == NHDP_LINK_SYMMETRIC) {
828     _link_status_now_symmetric(lnk);
829   }
830
831   /* trigger ip flooding interface settings recalculation */
832   if (was_symmetric != (lnk->status == NHDP_LINK_SYMMETRIC)) {
833     nhdp_interface_update_status(lnk->local_if);
834   }
835
836   if (old_status != lnk->status) {
837     /* link status was changed */
838     lnk->last_status_change = oonf_clock_getNow();
839
840     /* trigger change event */
841     oonf_class_event(&_link_info, lnk, OONF_OBJECT_CHANGED);
842   }
843 }
844
845 /**
846  * @param lnk nhdp link
847  * @return name of link status
848  */
849 const char *
850 nhdp_db_link_status_to_string(struct nhdp_link *lnk) {
851   switch (lnk->status) {
852     case NHDP_LINK_PENDING:
853       return _LINK_PENDING;
854     case NHDP_LINK_HEARD:
855       return _LINK_HEARD;
856     case NHDP_LINK_SYMMETRIC:
857       return _LINK_SYMMETRIC;
858     default:
859       return _LINK_LOST;
860   }
861 }
862
863 /**
864  * get global list of nhdp neighbors
865  * @return neighbor list
866  */
867 struct list_entity *
868 nhdp_db_get_neigh_list(void) {
869   return &_neigh_list;
870 }
871
872 /**
873  * get global list of nhdp links
874  * @return link list
875  */
876 struct list_entity *
877 nhdp_db_get_link_list(void) {
878   return &_link_list;
879 }
880
881 /**
882  * get global tree of nhdp neighbor addresses
883  * @return neighbor address tree
884  */
885 struct avl_tree *
886 nhdp_db_get_naddr_tree(void) {
887   return &_naddr_tree;
888 }
889
890 /**
891  * get global tree of nhdp originators
892  * @return originator tree
893  */
894 struct avl_tree *
895 nhdp_db_get_neigh_originator_tree(void) {
896   return &_neigh_originator_tree;
897 }
898
899 /**
900  * Helper function to calculate NHDP link status
901  * @param lnk nhdp link
902  * @return link status
903  */
904 int
905 _nhdp_db_link_calculate_status(struct nhdp_link *lnk) {
906   const struct netaddr *local_originator;
907   const struct os_interface *localif;
908   int af_type;
909
910   af_type = netaddr_get_address_family(&lnk->if_addr);
911   local_originator = nhdp_get_originator(af_type);
912   localif = nhdp_interface_get_if_listener(lnk->local_if)->data;
913
914   /* check for originator collision */
915   if (!netaddr_is_unspec(local_originator)
916       && (netaddr_cmp(local_originator, &lnk->if_addr) == 0
917           || netaddr_cmp(local_originator, &lnk->neigh->originator) == 0)) {
918     return NHDP_LINK_PENDING;
919   }
920
921   /* check for interface address collision */
922   if (nhdp_interface_addr_if_get(lnk->local_if, &lnk->if_addr)) {
923     return NHDP_LINK_PENDING;
924   }
925
926   /* check for MAC collision */
927   if (netaddr_cmp(&localif->mac, &lnk->remote_mac) == 0) {
928     return NHDP_LINK_PENDING;
929   }
930
931   /* calculate link status as described in RFC 6130 */
932   if (nhdp_hysteresis_is_pending(lnk))
933     return NHDP_LINK_PENDING;
934   if (nhdp_hysteresis_is_lost(lnk))
935     return RFC6130_LINKSTATUS_LOST;
936   if (oonf_timer_is_active(&lnk->sym_time))
937     return RFC6130_LINKSTATUS_SYMMETRIC;
938   if (oonf_timer_is_active(&lnk->heard_time))
939     return RFC6130_LINKSTATUS_HEARD;
940   return RFC6130_LINKSTATUS_LOST;
941 }
942
943 /**
944  * Helper function that handles the case of a link becoming symmetric
945  * @param lnk nhdp link
946  */
947 static void
948 _link_status_now_symmetric(struct nhdp_link *lnk) {
949   struct nhdp_naddr *naddr;
950
951   lnk->neigh->symmetric++;
952
953   if (lnk->neigh->symmetric == 1) {
954     avl_for_each_element(&lnk->neigh->_neigh_addresses, naddr, _neigh_node) {
955       nhdp_db_neighbor_addr_not_lost(naddr);
956     }
957     _neighbor_set_id++;
958   }
959 }
960
961 /**
962  * Helper function that handles the case of a link becoming asymmetric
963  * @param lnk nhdp link
964  */
965 static void
966 _link_status_not_symmetric_anymore(struct nhdp_link *lnk) {
967   struct nhdp_l2hop *twohop, *twohop_it;
968   struct nhdp_naddr *naddr, *na_it;
969
970   /* remove all 2hop neighbors */
971   avl_for_each_element_safe(&lnk->_2hop, twohop, _link_node, twohop_it) {
972     nhdp_db_link_2hop_remove(twohop);
973   }
974
975   lnk->neigh->symmetric--;
976   if (lnk->neigh->symmetric == 0) {
977     /* mark all neighbor addresses as lost */
978     avl_for_each_element_safe(&lnk->neigh->_neigh_addresses, naddr, _neigh_node, na_it) {
979       nhdp_db_neighbor_addr_set_lost(naddr, lnk->local_if->n_hold_time);
980     }
981
982     _neighbor_set_id++;
983   }
984 }
985
986 /**
987  * Callback triggered when link validity timer fires
988  * @param ptr timer instance that fired
989  */
990 static void
991 _cb_link_vtime(struct oonf_timer_instance *ptr) {
992   struct nhdp_link *lnk;
993   struct nhdp_neighbor *neigh;
994
995   lnk = container_of(ptr, struct nhdp_link, vtime);
996   OONF_DEBUG(LOG_NHDP, "Link vtime fired: 0x%0zx", (size_t)ptr);
997
998   neigh = lnk->neigh;
999
1000   if (lnk->status == NHDP_LINK_SYMMETRIC) {
1001     _link_status_not_symmetric_anymore(lnk);
1002   }
1003
1004   /* remove link from database */
1005   nhdp_db_link_remove(lnk);
1006
1007   /* check if neighbor still has links */
1008   if (list_is_empty(&neigh->_links)) {
1009     nhdp_db_neighbor_remove(neigh);
1010     nhdp_domain_neighborhood_changed();
1011   }
1012   else {
1013     nhdp_domain_neighbor_changed(neigh);
1014   }
1015 }
1016
1017 /**
1018  * Callback triggered when link heard timer fires
1019  * @param ptr timer instance that fired
1020  */
1021 static void
1022 _cb_link_heard(struct oonf_timer_instance *ptr) {
1023   struct nhdp_link *lnk;
1024
1025   lnk = container_of(ptr, struct nhdp_link, heard_time);
1026   OONF_DEBUG(LOG_NHDP, "Link heard fired: 0x%0zx", (size_t)lnk);
1027   nhdp_db_link_update_status(lnk);
1028 }
1029
1030 /**
1031  * Callback triggered when link symmetric timer fires
1032  * @param ptr timer instance that fired
1033  */
1034 static void
1035 _cb_link_symtime(struct oonf_timer_instance *ptr) {
1036   struct nhdp_link *lnk;
1037
1038   lnk = container_of(ptr, struct nhdp_link, sym_time);
1039   OONF_DEBUG(LOG_NHDP, "Link Symtime fired: 0x%0zx", (size_t)lnk);
1040   nhdp_db_link_update_status(lnk);
1041   nhdp_domain_neighbor_changed(lnk->neigh);
1042 }
1043
1044 /**
1045  * Callback triggered when nhdp address validity timer fires
1046  * @param ptr timer instance that fired
1047  */
1048 static void
1049 _cb_naddr_vtime(struct oonf_timer_instance *ptr) {
1050   struct nhdp_naddr *naddr;
1051
1052   naddr = container_of(ptr, struct nhdp_naddr, _lost_vtime);
1053   OONF_DEBUG(LOG_NHDP, "Neighbor Address Lost fired: 0x%0zx", (size_t)ptr);
1054
1055   nhdp_db_neighbor_addr_remove(naddr);
1056 }
1057
1058 /**
1059  * Callback triggered when 2hop valitidy timer fires
1060  * @param ptr timer instance that fired
1061  */
1062 static void
1063 _cb_l2hop_vtime(struct oonf_timer_instance *ptr) {
1064   struct nhdp_l2hop *l2hop;
1065   struct nhdp_neighbor *neigh;
1066
1067   l2hop = container_of(ptr, struct nhdp_l2hop, _vtime);
1068   neigh = l2hop->link->neigh;
1069
1070   OONF_DEBUG(LOG_NHDP, "2Hop vtime fired: 0x%0zx", (size_t)ptr);
1071   nhdp_db_link_2hop_remove(l2hop);
1072   nhdp_domain_neighbor_changed(neigh);
1073 }