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