40802ff007056b22ac203361ba6bf868f4f663ef
[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_cookie_info *nbr2_mem_cookie = NULL;
61 static struct olsr_cookie_info *nbr_mem_cookie = NULL;
62 static struct olsr_cookie_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_create_memcookie("Neighbor connector", sizeof(struct nbr_con));
82
83   nbr_mem_cookie = olsr_create_memcookie("1-Hop Neighbor", sizeof(struct nbr_entry));
84
85   nbr2_mem_cookie = olsr_create_memcookie("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_cookie_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;
153   struct list_iterator 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_cookie_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_cookie_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;
304   struct list_iterator iterator;
305
306 #if !defined REMOVE_LOG_DEBUG
307   struct ipaddr_str buf;
308 #endif
309
310   OLSR_DEBUG(LOG_NEIGHTABLE, "Delete 2-hop neighbor: %s\n", olsr_ip_to_string(&buf, &nbr2->nbr2_addr));
311
312   /*
313    * Remove all references pointing to this two hop neighbor.
314    */
315   OLSR_FOR_ALL_NBR2_CON_ENTRIES(nbr2, connector, iterator) {
316     internal_delete_nbr_con(connector);
317   }
318
319   /* Remove from global neighbor tree */
320   avl_delete(&nbr2_tree, &nbr2->nbr2_node);
321
322   olsr_cookie_free(nbr2_mem_cookie, nbr2);
323   changes_neighborhood = true;
324 }
325
326 struct nbr2_entry *
327 olsr_lookup_nbr2_entry(const union olsr_ip_addr *addr, bool lookupalias) {
328   const union olsr_ip_addr *main_addr = NULL;
329   struct nbr2_entry *entry;
330
331   /*
332    * Find main address of node
333    */
334   if (lookupalias) {
335     main_addr = olsr_lookup_main_addr_by_alias(addr);
336   }
337   if (main_addr == NULL) {
338     main_addr = addr;
339   }
340
341   entry = avl_find_element(&nbr2_tree, addr, entry, nbr2_node);
342   return entry;
343 }
344
345 /**
346  * Links a one-hop neighbor with a 2-hop neighbor.
347  *
348  * @param nbr  the 1-hop neighbor
349  * @param nbr2 the 2-hop neighbor
350  * @param vtime validity time of the 2hop neighbor
351  */
352 struct nbr_con *
353 olsr_link_nbr_nbr2(struct nbr_entry *nbr, const union olsr_ip_addr *nbr2_addr, uint32_t vtime) {
354   struct nbr_con *connector;
355   struct nbr2_entry *nbr2;
356
357   /*
358    * Check if connector entry exists.
359    */
360   connector = olsr_lookup_nbr_con_entry(nbr, nbr2_addr);
361   if (connector) {
362     olsr_change_timer(connector->nbr2_con_timer, vtime, OLSR_NBR2_LIST_JITTER);
363     return connector;
364   }
365
366   /*
367    * Generate a fresh one.
368    */
369   nbr2 = olsr_add_nbr2_entry(nbr2_addr);
370
371   connector = olsr_cookie_malloc(nbr_connector_mem_cookie);
372
373   connector->nbr = nbr;
374   connector->nbr2 = nbr2;
375   connector->nbr_tree_node.key = &nbr2->nbr2_addr;
376   connector->nbr2_tree_node.key = &nbr->nbr_addr;
377
378   avl_insert(&nbr->con_tree, &connector->nbr_tree_node);
379   avl_insert(&nbr2->con_tree, &connector->nbr2_tree_node);
380
381   connector->path_linkcost = LINK_COST_BROKEN;
382
383   connector->nbr2_con_timer = olsr_start_timer(vtime, OLSR_NBR2_LIST_JITTER,
384       connector, nbr_connector_timer_info);
385
386   return connector;
387 }
388
389 /**
390  * Deletes a nbr-connector without deleting the 2-hop neighbor
391  * @param connector the connector between neighbors
392  */
393 static void
394 internal_delete_nbr_con(struct nbr_con *connector) {
395   olsr_stop_timer(connector->nbr2_con_timer);
396   connector->nbr2_con_timer = NULL;
397
398   avl_delete(&connector->nbr->con_tree, &connector->nbr_tree_node);
399   avl_delete(&connector->nbr2->con_tree, &connector->nbr2_tree_node);
400
401   olsr_cookie_free(nbr_connector_mem_cookie, connector);
402 }
403
404 /**
405  * Unlinks an one-hop and a 2-hop neighbor.
406  *
407  * @param connector the connector between the neighbors
408  */
409 void
410 olsr_delete_nbr_con(struct nbr_con *connector) {
411   struct nbr2_entry *nbr2;
412
413   nbr2 = connector->nbr2;
414
415   internal_delete_nbr_con(connector);
416
417   if (nbr2->con_tree.count == 0) {
418     olsr_delete_nbr2_entry(nbr2);
419   }
420 }
421
422 /**
423  * Looks up the connection object of an one-hop neighbor to a
424  * 2-hop neighbor ip address.
425  *
426  * @param nbr the one-hop neighbor
427  * @param nbr2_addr the ip of the 2-hop neighbor
428  * @return nbr_con, or NULL if not found
429  */
430 struct nbr_con *
431 olsr_lookup_nbr_con_entry(struct nbr_entry *nbr, const union olsr_ip_addr *nbr2_addr) {
432   struct nbr_con *con;
433   con = avl_find_element(&nbr->con_tree, nbr2_addr, con, nbr_tree_node);
434   return con;
435 }
436
437 /**
438  * Looks up the connection object of an 2-hop neighbor to an
439  * one-hop neighbor ip address.
440  *
441  * @param nbr2 the 2-hop neighbor
442  * @param nbr_addr the ip of the one-hop neighbor
443  * @return nbr_con, or NULL if not found
444  */
445 struct nbr_con *
446 olsr_lookup_nbr2_con_entry(struct nbr2_entry *nbr2, const union olsr_ip_addr *nbr_addr) {
447   struct nbr_con *con;
448   con = avl_find_element(&nbr2->con_tree, nbr_addr, con, nbr2_tree_node);
449   return con;
450 }
451
452 /*
453  * Wrapper for the timer callback.
454  */
455 static void
456 olsr_expire_nbr_con(void *context) {
457   struct nbr_con *connector;
458
459   connector = context;
460   connector->nbr2_con_timer = NULL;
461
462   olsr_delete_nbr_con(connector);
463 }
464
465
466 /**
467  * Print the registered neighbors and two hop neighbors to STDOUT.
468  *
469  * @return nada
470  */
471 void
472 olsr_print_neighbor_table(void)
473 {
474 #if !defined REMOVE_LOG_INFO
475   /* The whole function doesn't do anything else. */
476
477   const int ipwidth = olsr_cnf->ip_version == AF_INET ? INET_ADDRSTRLEN : INET6_ADDRSTRLEN;
478   struct nbr_entry *nbr;
479   struct link_entry *lnk;
480   struct ipaddr_str buf, buf2;
481   struct nbr2_entry *nbr2;
482   struct nbr_con *connector;
483   struct list_iterator iterator, iterator2;
484   char lqbuffer[LQTEXT_MAXLENGTH];
485   bool first;
486
487   OLSR_INFO(LOG_NEIGHTABLE, "\n--- %s ------------------------------------------------ NEIGHBORS\n\n"
488             "%-*s\tSYM\tMPR\tMPRS\twill\n", olsr_wallclock_string(), ipwidth, "IP address");
489
490   OLSR_FOR_ALL_NBR_ENTRIES(nbr, iterator) {
491
492     lnk = get_best_link_to_neighbor_ip(&nbr->nbr_addr);
493     if (!lnk) {
494       continue;
495     }
496
497     OLSR_INFO_NH(LOG_NEIGHTABLE, "%-*s\t%s\t%s\t%s\t%d\n",
498                  ipwidth, olsr_ip_to_string(&buf, &nbr->nbr_addr),
499                  nbr->is_sym ? "YES" : "NO",
500                  nbr->is_mpr ? "YES" : "NO",
501                  nbr->mprs_count == 0  ? "NO  " : "YES ",
502                  nbr->willingness);
503   }
504
505   OLSR_INFO(LOG_2NEIGH, "\n--- %s ----------------------- TWO-HOP NEIGHBORS\n\n"
506             "IP addr (2-hop)  IP addr (1-hop)  Total cost\n", olsr_wallclock_string());
507
508   OLSR_FOR_ALL_NBR2_ENTRIES(nbr2, iterator) {
509     first = true;
510     OLSR_FOR_ALL_NBR2_CON_ENTRIES(nbr2, connector, iterator2) {
511       OLSR_INFO_NH(LOG_2NEIGH, "%-*s  %-*s  %s\n",
512                    ipwidth, first ? olsr_ip_to_string(&buf, &nbr2->nbr2_addr) : "",
513                    ipwidth, olsr_ip_to_string(&buf2, &connector->nbr->nbr_addr),
514                    olsr_get_linkcost_text(connector->path_linkcost, false, lqbuffer, sizeof(lqbuffer)));
515
516       first = false;
517     }
518   }
519
520 #endif
521 }
522
523 /*
524  * Local Variables:
525  * c-basic-offset: 2
526  * indent-tabs-mode: nil
527  * End:
528  */