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