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