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