fd0d940eddcf4763fdb96ddfe3a0be15bcdfc03c
[olsrd.git] / src / neighbor_table.c
1
2 /*
3  * The olsr.org Optimized Link-State Routing daemon(olsrd)
4  * Copyright (c) 2004-2009, 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 #include "ipcalc.h"
43 #include "defs.h"
44 #include "mid_set.h"
45 #include "neighbor_table.h"
46 #include "olsr.h"
47 #include "scheduler.h"
48 #include "link_set.h"
49 #include "net_olsr.h"
50 #include "olsr_logging.h"
51
52 #include <assert.h>
53 #include <stdlib.h>
54
55 /* Root of the one hop and two hop neighbor trees */
56 struct avl_tree nbr_tree;
57 struct avl_tree nbr2_tree;
58
59 /* memory management */
60 static struct olsr_memcookie_info *nbr2_mem_cookie = NULL;
61 static struct olsr_memcookie_info *nbr_mem_cookie = NULL;
62 static struct olsr_memcookie_info *nbr_connector_mem_cookie = NULL;
63
64 /* neighbor connection validity timer */
65 static struct olsr_timer_info *nbr_connector_timer_info = NULL;
66
67 static void olsr_expire_nbr_con(void *);
68 static void internal_delete_nbr_con(struct nbr_con *connector);
69
70 /*
71  * Init neighbor tables.
72  */
73 void
74 olsr_init_neighbor_table(void)
75 {
76   OLSR_INFO(LOG_NEIGHTABLE, "Initializing neighbor tree.\n");
77   avl_init(&nbr_tree, avl_comp_default, false, NULL);
78   avl_init(&nbr2_tree, avl_comp_default, false, NULL);
79
80   nbr_connector_timer_info = olsr_alloc_timerinfo("Neighbor connector", &olsr_expire_nbr_con, false);
81   nbr_connector_mem_cookie = olsr_memcookie_add("Neighbor connector", sizeof(struct nbr_con));
82
83   nbr_mem_cookie = olsr_memcookie_add("1-Hop Neighbor", sizeof(struct nbr_entry));
84
85   nbr2_mem_cookie = olsr_memcookie_add("2-Hop Neighbor", sizeof(struct nbr2_entry));
86 }
87
88 /**
89  * Insert a neighbor entry in the neighbor table.
90  *
91  * @param addr the main address of the new node
92  * @return pointer to an already existting (or new created) neighbor entry
93  */
94 struct nbr_entry *
95 olsr_add_nbr_entry(const union olsr_ip_addr *addr)
96 {
97 #if !defined REMOVE_LOG_DEBUG
98   struct ipaddr_str buf;
99 #endif
100   struct nbr_entry *nbr;
101
102   /*
103    * Check if neighbor entry exists.
104    */
105   nbr = olsr_lookup_nbr_entry(addr, true);
106   if (nbr) {
107     return nbr;
108   }
109
110   OLSR_DEBUG(LOG_NEIGHTABLE, "Add 1-hop neighbor: %s\n", olsr_ip_to_string(&buf, addr));
111
112   nbr = olsr_memcookie_malloc(nbr_mem_cookie);
113
114   /* Set address, willingness and status */
115   nbr->nbr_addr = *addr;
116   nbr->willingness = WILL_NEVER;
117   nbr->is_sym = false;
118
119   /* Init subtree for nbr2 connectors */
120   avl_init(&nbr->con_tree, avl_comp_default, false, NULL);
121
122   nbr->linkcount = 0;
123   nbr->is_mpr = false;
124   nbr->was_mpr = false;
125
126   /* add tc_edge if necessary */
127   assert(tc_myself);
128   nbr->tc_edge = olsr_lookup_tc_edge(tc_myself, addr);
129   if (nbr->tc_edge == NULL) {
130     nbr->tc_edge = olsr_add_tc_edge_entry(tc_myself, addr, 0);
131   }
132
133   /* and connect it to this neighbor */
134   nbr->tc_edge->neighbor = nbr;
135
136   /* Add to the global neighbor tree */
137   nbr->nbr_node.key = &nbr->nbr_addr;
138   avl_insert(&nbr_tree, &nbr->nbr_node);
139
140   return nbr;
141 }
142
143 /**
144  * Delete a neighbor table entry.
145  *
146  * Remember: Deleting a neighbor entry results the deletion of its 2 hop neighbors list!!!
147  * @param addr the neighbor entry to delete
148  */
149 void
150 olsr_delete_nbr_entry(struct nbr_entry *nbr)
151 {
152   struct nbr_con *connector, *iterator;
153 #if !defined REMOVE_LOG_DEBUG
154   struct ipaddr_str buf;
155 #endif
156
157   OLSR_DEBUG(LOG_NEIGHTABLE, "Delete 1-hop neighbor: %s\n", olsr_ip_to_string(&buf, &nbr->nbr_addr));
158
159   /*
160    * Remove all references pointing to this neighbor.
161    */
162   OLSR_FOR_ALL_NBR_CON_ENTRIES(nbr, connector, iterator) {
163     olsr_delete_nbr_con(connector);
164   }
165
166   /* remove corresponding tc_edge if not already removed by olsr_delete_all_tc_entries() */
167   if (nbr->tc_edge) {
168     /* first clear the connection to this neighbor */
169     nbr->tc_edge->neighbor = NULL;
170
171     /* now try to kill the edge */
172     olsr_delete_tc_edge_entry(nbr->tc_edge);
173   }
174
175   /* Remove from global neighbor tree */
176   avl_delete(&nbr_tree, &nbr->nbr_node);
177
178   olsr_memcookie_free(nbr_mem_cookie, nbr);
179
180   changes_neighborhood = true;
181   changes_topology = true;
182 }
183
184 /**
185  * Lookup a neighbor entry in the neighbortable based on an address.
186  * Unalias the passed in address before.
187  *
188  * @param addr the IP address of the neighbor to look up
189  *
190  * @return a pointer to the neighbor struct registered on the given
191  * address. NULL if not found.
192  */
193 struct nbr_entry *
194 olsr_lookup_nbr_entry(const union olsr_ip_addr *addr, bool lookupalias)
195 {
196   const union olsr_ip_addr *main_addr = NULL;
197   struct nbr_entry *nbr;
198
199   /*
200    * Find main address of node
201    */
202   if (lookupalias) {
203     main_addr = olsr_lookup_main_addr_by_alias(addr);
204   }
205   if (main_addr == NULL) {
206     main_addr = addr;
207   }
208
209   nbr = avl_find_element(&nbr_tree, addr, nbr, nbr_node);
210   return nbr;
211 }
212
213 void olsr_update_nbr_status(struct nbr_entry *entry) {
214 #if !defined REMOVE_LOG_DEBUG
215   struct ipaddr_str buf;
216 #endif
217   struct link_entry *link;
218
219   /* look for best symmetric link */
220   link = get_best_link_to_neighbor(entry);
221
222   /*
223    * Update neighbor entry
224    */
225   if (link && lookup_link_status(link) == SYM_LINK) {
226     /* N_status is set to SYM */
227     if (!entry->is_sym) {
228       struct nbr2_entry *two_hop_neighbor;
229
230       /* Delete posible 2 hop entry on this neighbor */
231       if ((two_hop_neighbor = olsr_lookup_nbr2_entry(&entry->nbr_addr, true)) != NULL) {
232         olsr_delete_nbr2_entry(two_hop_neighbor);
233       }
234
235       changes_neighborhood = true;
236       changes_topology = true;
237       if (olsr_cnf->tc_redundancy > 1 || entry->is_mpr) {
238         signal_link_changes(true);
239       }
240     }
241     entry->is_sym = true;
242     OLSR_DEBUG(LOG_NEIGHTABLE, "Neighbor %s is now symmetric\n", olsr_ip_to_string(&buf, &entry->nbr_addr));
243   } else {
244     if (entry->is_sym) {
245       changes_neighborhood = true;
246       if (olsr_cnf->tc_redundancy > 1 || entry->is_mpr) {
247         signal_link_changes(true);
248         changes_topology = true;
249       }
250     }
251     /* else N_status is set to NOT_SYM */
252     entry->is_sym = false;
253
254     OLSR_DEBUG(LOG_NEIGHTABLE, "Neighbor %s is now non-symmetric\n", olsr_ip_to_string(&buf, &entry->nbr_addr));
255   }
256 }
257
258 /**
259  * Insert a new entry to the two hop neighbor table.
260  *
261  * @param addr the entry to insert
262  * @return nada
263  */
264 struct nbr2_entry *
265 olsr_add_nbr2_entry(const union olsr_ip_addr *addr) {
266 #if !defined REMOVE_LOG_DEBUG
267   struct ipaddr_str buf;
268 #endif
269   struct nbr2_entry *nbr2;
270
271   /*
272    * Check first if the entry exists.
273    */
274   nbr2 = olsr_lookup_nbr2_entry(addr, true);
275   if (nbr2) {
276     return nbr2;
277   }
278
279   OLSR_DEBUG(LOG_2NEIGH, "Adding 2 hop neighbor %s\n", olsr_ip_to_string(&buf, addr));
280
281   nbr2 = olsr_memcookie_malloc(nbr2_mem_cookie);
282
283   /* Init neighbor connector subtree */
284   avl_init(&nbr2->con_tree, avl_comp_default, false, NULL);
285
286   nbr2->nbr2_addr = *addr;
287
288   /* Add to global neighbor 2 tree */
289   nbr2->nbr2_node.key = &nbr2->nbr2_addr;
290   avl_insert(&nbr2_tree, &nbr2->nbr2_node);
291
292   return nbr2;
293 }
294
295 /**
296  * Delete an entry from the two hop neighbor table.
297  *
298  * @param nbr2 the two hop neighbor to delete.
299  */
300 void
301 olsr_delete_nbr2_entry(struct nbr2_entry *nbr2) {
302   struct nbr_con *connector, *iterator;
303
304 #if !defined REMOVE_LOG_DEBUG
305   struct ipaddr_str buf;
306 #endif
307
308   OLSR_DEBUG(LOG_NEIGHTABLE, "Delete 2-hop neighbor: %s\n", olsr_ip_to_string(&buf, &nbr2->nbr2_addr));
309
310   /*
311    * Remove all references pointing to this two hop neighbor.
312    */
313   OLSR_FOR_ALL_NBR2_CON_ENTRIES(nbr2, connector, iterator) {
314     internal_delete_nbr_con(connector);
315   }
316
317   /* Remove from global neighbor tree */
318   avl_delete(&nbr2_tree, &nbr2->nbr2_node);
319
320   olsr_memcookie_free(nbr2_mem_cookie, nbr2);
321   changes_neighborhood = true;
322 }
323
324 struct nbr2_entry *
325 olsr_lookup_nbr2_entry(const union olsr_ip_addr *addr, bool lookupalias) {
326   const union olsr_ip_addr *main_addr = NULL;
327   struct nbr2_entry *entry;
328
329   /*
330    * Find main address of node
331    */
332   if (lookupalias) {
333     main_addr = olsr_lookup_main_addr_by_alias(addr);
334   }
335   if (main_addr == NULL) {
336     main_addr = addr;
337   }
338
339   entry = avl_find_element(&nbr2_tree, addr, entry, nbr2_node);
340   return entry;
341 }
342
343 /**
344  * Links a one-hop neighbor with a 2-hop neighbor.
345  *
346  * @param nbr  the 1-hop neighbor
347  * @param nbr2 the 2-hop neighbor
348  * @param vtime validity time of the 2hop neighbor
349  */
350 struct nbr_con *
351 olsr_link_nbr_nbr2(struct nbr_entry *nbr, const union olsr_ip_addr *nbr2_addr, uint32_t vtime) {
352   struct nbr_con *connector;
353   struct nbr2_entry *nbr2;
354
355   /*
356    * Check if connector entry exists.
357    */
358   connector = olsr_lookup_nbr_con_entry(nbr, nbr2_addr);
359   if (connector) {
360     olsr_change_timer(connector->nbr2_con_timer, vtime, OLSR_NBR2_LIST_JITTER);
361     return connector;
362   }
363
364   /*
365    * Generate a fresh one.
366    */
367   nbr2 = olsr_add_nbr2_entry(nbr2_addr);
368
369   connector = olsr_memcookie_malloc(nbr_connector_mem_cookie);
370
371   connector->nbr = nbr;
372   connector->nbr2 = nbr2;
373   connector->nbr_tree_node.key = &nbr2->nbr2_addr;
374   connector->nbr2_tree_node.key = &nbr->nbr_addr;
375
376   avl_insert(&nbr->con_tree, &connector->nbr_tree_node);
377   avl_insert(&nbr2->con_tree, &connector->nbr2_tree_node);
378
379   connector->path_linkcost = LINK_COST_BROKEN;
380
381   connector->nbr2_con_timer = olsr_start_timer(vtime, OLSR_NBR2_LIST_JITTER,
382       connector, nbr_connector_timer_info);
383
384   return connector;
385 }
386
387 /**
388  * Deletes a nbr-connector without deleting the 2-hop neighbor
389  * @param connector the connector between neighbors
390  */
391 static void
392 internal_delete_nbr_con(struct nbr_con *connector) {
393   olsr_stop_timer(connector->nbr2_con_timer);
394   connector->nbr2_con_timer = NULL;
395
396   avl_delete(&connector->nbr->con_tree, &connector->nbr_tree_node);
397   avl_delete(&connector->nbr2->con_tree, &connector->nbr2_tree_node);
398
399   olsr_memcookie_free(nbr_connector_mem_cookie, connector);
400 }
401
402 /**
403  * Unlinks an one-hop and a 2-hop neighbor.
404  *
405  * @param connector the connector between the neighbors
406  */
407 void
408 olsr_delete_nbr_con(struct nbr_con *connector) {
409   struct nbr2_entry *nbr2;
410
411   nbr2 = connector->nbr2;
412
413   internal_delete_nbr_con(connector);
414
415   if (nbr2->con_tree.count == 0) {
416     olsr_delete_nbr2_entry(nbr2);
417   }
418 }
419
420 /**
421  * Looks up the connection object of an one-hop neighbor to a
422  * 2-hop neighbor ip address.
423  *
424  * @param nbr the one-hop neighbor
425  * @param nbr2_addr the ip of the 2-hop neighbor
426  * @return nbr_con, or NULL if not found
427  */
428 struct nbr_con *
429 olsr_lookup_nbr_con_entry(struct nbr_entry *nbr, const union olsr_ip_addr *nbr2_addr) {
430   struct nbr_con *con;
431   con = avl_find_element(&nbr->con_tree, nbr2_addr, con, nbr_tree_node);
432   return con;
433 }
434
435 /**
436  * Looks up the connection object of an 2-hop neighbor to an
437  * one-hop neighbor ip address.
438  *
439  * @param nbr2 the 2-hop neighbor
440  * @param nbr_addr the ip of the one-hop neighbor
441  * @return nbr_con, or NULL if not found
442  */
443 struct nbr_con *
444 olsr_lookup_nbr2_con_entry(struct nbr2_entry *nbr2, const union olsr_ip_addr *nbr_addr) {
445   struct nbr_con *con;
446   con = avl_find_element(&nbr2->con_tree, nbr_addr, con, nbr2_tree_node);
447   return con;
448 }
449
450 /*
451  * Wrapper for the timer callback.
452  */
453 static void
454 olsr_expire_nbr_con(void *context) {
455   struct nbr_con *connector;
456
457   connector = context;
458   connector->nbr2_con_timer = NULL;
459
460   olsr_delete_nbr_con(connector);
461 }
462
463
464 /**
465  * Print the registered neighbors and two hop neighbors to STDOUT.
466  *
467  * @return nada
468  */
469 void
470 olsr_print_neighbor_table(void)
471 {
472 #if !defined REMOVE_LOG_INFO
473   /* The whole function doesn't do anything else. */
474
475   const int ipwidth = olsr_cnf->ip_version == AF_INET ? INET_ADDRSTRLEN : INET6_ADDRSTRLEN;
476   struct nbr_entry *nbr, *nbr_iterator;
477   struct link_entry *lnk;
478   struct ipaddr_str buf, buf2;
479   struct nbr2_entry *nbr2, *nbr2_iterator;
480   struct nbr_con *connector, *con_iterator;
481   char lqbuffer[LQTEXT_MAXLENGTH];
482   bool first;
483
484   OLSR_INFO(LOG_NEIGHTABLE, "\n--- %s ------------------------------------------------ NEIGHBORS\n\n"
485             "%-*s\tSYM\tMPR\tMPRS\twill\n", olsr_wallclock_string(), ipwidth, "IP address");
486
487   OLSR_FOR_ALL_NBR_ENTRIES(nbr, nbr_iterator) {
488
489     lnk = get_best_link_to_neighbor_ip(&nbr->nbr_addr);
490     if (!lnk) {
491       continue;
492     }
493
494     OLSR_INFO_NH(LOG_NEIGHTABLE, "%-*s\t%s\t%s\t%s\t%d\n",
495                  ipwidth, olsr_ip_to_string(&buf, &nbr->nbr_addr),
496                  nbr->is_sym ? "YES" : "NO",
497                  nbr->is_mpr ? "YES" : "NO",
498                  nbr->mprs_count == 0  ? "NO  " : "YES ",
499                  nbr->willingness);
500   }
501
502   OLSR_INFO(LOG_2NEIGH, "\n--- %s ----------------------- TWO-HOP NEIGHBORS\n\n"
503             "IP addr (2-hop)  IP addr (1-hop)  Total cost\n", olsr_wallclock_string());
504
505   OLSR_FOR_ALL_NBR2_ENTRIES(nbr2, nbr2_iterator) {
506     first = true;
507     OLSR_FOR_ALL_NBR2_CON_ENTRIES(nbr2, connector, con_iterator) {
508       OLSR_INFO_NH(LOG_2NEIGH, "%-*s  %-*s  %s\n",
509                    ipwidth, first ? olsr_ip_to_string(&buf, &nbr2->nbr2_addr) : "",
510                    ipwidth, olsr_ip_to_string(&buf2, &connector->nbr->nbr_addr),
511                    olsr_get_linkcost_text(connector->path_linkcost, false, lqbuffer, sizeof(lqbuffer)));
512
513       first = false;
514     }
515   }
516
517 #endif
518 }
519
520 /*
521  * Local Variables:
522  * c-basic-offset: 2
523  * indent-tabs-mode: nil
524  * End:
525  */