2 * The olsr.org Optimized Link-State Routing daemon(olsrd)
3 * Copyright (c) 2004, Andreas Tønnesen(andreto@olsr.org)
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
10 * * Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
12 * * Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in
14 * the documentation and/or other materials provided with the
16 * * Neither the name of olsr.org, olsrd nor the names of its
17 * contributors may be used to endorse or promote products derived
18 * from this software without specific prior written permission.
20 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
21 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
22 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
23 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
24 * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
25 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
26 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
27 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
28 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
29 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
30 * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
31 * POSSIBILITY OF SUCH DAMAGE.
33 * Visit http://www.olsr.org for more information.
35 * If you find this software useful feel free to make a donation
36 * to the project. For more information see the website or contact
37 * the copyright holders.
39 * $Id: neighbor_table.c,v 1.23 2005/01/17 20:18:21 kattemat Exp $
45 #include "two_hop_neighbor_table.h"
49 #include "scheduler.h"
51 #include "mpr_selector_set.h"
54 olsr_init_neighbor_table()
58 olsr_register_timeout_function(&olsr_time_out_neighborhood_tables);
60 for(i = 0; i < HASHSIZE; i++)
62 neighbortable[i].next = &neighbortable[i];
63 neighbortable[i].prev = &neighbortable[i];
69 *Delete a two hop neighbor from a neighbors two
72 *@param neighbor the neighbor to delete the two hop
74 *@param address the IP address of the two hop neighbor
77 *@return positive if entry deleted
80 olsr_delete_neighbor_2_pointer(struct neighbor_entry *neighbor, union olsr_ip_addr *address)
83 struct neighbor_2_list_entry *entry;
85 entry = neighbor->neighbor_2_list.next;
87 while(entry != &neighbor->neighbor_2_list)
90 if(COMP_IP(&entry->neighbor_2->neighbor_2_addr, address))
105 *Check if a two hop neighbor is reachable via a given
108 *@param neighbor neighbor-entry to check via
109 *@param neighbor_main_address the addres of the two hop neighbor
112 *@return a pointer to the neighbor_2_list_entry struct
113 *representing the two hop neighbor if found. NULL if not found.
115 struct neighbor_2_list_entry *
116 olsr_lookup_my_neighbors(struct neighbor_entry *neighbor, union olsr_ip_addr *neighbor_main_address)
119 struct neighbor_2_list_entry *entry;
121 for(entry = neighbor->neighbor_2_list.next;
122 entry != &neighbor->neighbor_2_list;
126 if(COMP_IP(&entry->neighbor_2->neighbor_2_addr, neighbor_main_address))
136 *Delete a neighbr table entry.
138 *Remember: Deleting a neighbor entry results
139 *the deletion of its 2 hop neighbors list!!!
140 *@param neighbor the neighbor entry to delete
146 olsr_delete_neighbor_table(union olsr_ip_addr *neighbor_addr)
148 struct neighbor_2_list_entry *two_hop_list, *two_hop_to_delete;
150 struct neighbor_entry *entry;
152 //printf("inserting neighbor\n");
154 hash = olsr_hashing(neighbor_addr);
156 entry = neighbortable[hash].next;
159 * Find neighbor entry
161 while(entry != &neighbortable[hash])
163 if(COMP_IP(&entry->neighbor_main_addr, neighbor_addr))
169 if(entry == &neighbortable[hash])
173 two_hop_list = entry->neighbor_2_list.next;
175 while(two_hop_list != &entry->neighbor_2_list)
177 struct neighbor_2_entry *two_hop_entry;
179 two_hop_entry = two_hop_list->neighbor_2;
181 two_hop_entry->neighbor_2_pointer--;
183 olsr_delete_neighbor_pointer(two_hop_entry, &entry->neighbor_main_addr);
185 /* Delete entry if it has no more one hop neighbors pointing to it */
186 if(two_hop_entry->neighbor_2_pointer < 1)
188 DEQUEUE_ELEM(two_hop_entry);
194 two_hop_to_delete = two_hop_list;
195 two_hop_list = two_hop_list->next;
197 free(two_hop_to_delete);
207 changes_neighborhood = OLSR_TRUE;
215 *Insert a neighbor entry in the neighbor table
217 *@param main_addr the main address of the new node
219 *@return 0 if neighbor already exists 1 if inserted
221 struct neighbor_entry *
222 olsr_insert_neighbor_table(union olsr_ip_addr *main_addr)
225 struct neighbor_entry *new_neigh;
227 hash = olsr_hashing(main_addr);
229 /* Check if entry exists */
231 for(new_neigh = neighbortable[hash].next;
232 new_neigh != &neighbortable[hash];
233 new_neigh = new_neigh->next)
235 if(COMP_IP(&new_neigh->neighbor_main_addr, main_addr))
239 //printf("inserting neighbor\n");
241 new_neigh = olsr_malloc(sizeof(struct neighbor_entry), "New neighbor entry");
243 /* Set address, willingness and status */
244 COPY_IP(&new_neigh->neighbor_main_addr, main_addr);
245 new_neigh->willingness = WILL_NEVER;
246 new_neigh->status = NOT_SYM;
248 new_neigh->neighbor_2_list.next = &new_neigh->neighbor_2_list;
249 new_neigh->neighbor_2_list.prev = &new_neigh->neighbor_2_list;
251 new_neigh->linkcount = 0;
252 new_neigh->is_mpr = OLSR_FALSE;
253 new_neigh->was_mpr = OLSR_FALSE;
256 QUEUE_ELEM(neighbortable[hash], new_neigh);
264 *Lookup a neighbor entry in the neighbortable based on an address.
266 *@param dst the IP address of the neighbor to look up
268 *@return a pointer to the neighbor struct registered on the given
269 *address. NULL if not found.
271 struct neighbor_entry *
272 olsr_lookup_neighbor_table(union olsr_ip_addr *dst)
274 struct neighbor_entry *entry;
276 //struct addresses *adr;
277 union olsr_ip_addr *tmp_ip;
280 *Find main address of node
282 if((tmp_ip = mid_lookup_main_addr(dst)) != NULL)
285 hash = olsr_hashing(dst);
288 //printf("\nLookup %s\n", olsr_ip_to_string(dst));
289 for(entry = neighbortable[hash].next;
290 entry != &neighbortable[hash];
293 //printf("Checking %s\n", olsr_ip_to_string(&neighbor_table_tmp->neighbor_main_addr));
294 if(COMP_IP(&entry->neighbor_main_addr, dst))
298 //printf("NOPE\n\n");
306 *Lookup a neighbor entry in the neighbortable based on an address.
308 *@param dst the IP address of the neighbor to look up
310 *@return a pointer to the neighbor struct registered on the given
311 *address. NULL if not found.
313 struct neighbor_entry *
314 olsr_lookup_neighbor_table_alias(union olsr_ip_addr *dst)
316 struct neighbor_entry *entry;
318 //struct addresses *adr;
320 hash = olsr_hashing(dst);
323 //printf("\nLookup %s\n", olsr_ip_to_string(dst));
324 for(entry = neighbortable[hash].next;
325 entry != &neighbortable[hash];
328 //printf("Checking %s\n", olsr_ip_to_string(&neighbor_table_tmp->neighbor_main_addr));
329 if(COMP_IP(&entry->neighbor_main_addr, dst))
333 //printf("NOPE\n\n");
342 update_neighbor_status(struct neighbor_entry *entry, int link)
345 * Update neighbor entry
350 /* N_status is set to SYM */
351 if(entry->status == NOT_SYM)
353 struct neighbor_2_entry *two_hop_neighbor;
355 /* Delete posible 2 hop entry on this neighbor */
356 if((two_hop_neighbor = olsr_lookup_two_hop_neighbor_table(&entry->neighbor_main_addr))!=NULL)
358 olsr_delete_two_hop_neighbor_table(two_hop_neighbor);
361 changes_neighborhood = OLSR_TRUE;
362 changes_topology = OLSR_TRUE;
363 if(olsr_cnf->tc_redundancy > 1)
370 if(entry->status == SYM)
372 changes_neighborhood = OLSR_TRUE;
373 changes_topology = OLSR_TRUE;
374 if(olsr_cnf->tc_redundancy > 1)
377 /* else N_status is set to NOT_SYM */
378 entry->status = NOT_SYM;
379 /* remove neighbor from routing list */
382 return entry->status;
388 *Times out the entries in the two hop neighbor table and
389 *deletes those who have exceeded their time to live since
396 olsr_time_out_two_hop_neighbors(struct neighbor_entry *neighbor)
398 struct neighbor_2_list_entry *two_hop_list;
400 two_hop_list = neighbor->neighbor_2_list.next;
402 while(two_hop_list != &neighbor->neighbor_2_list)
404 if(TIMED_OUT(two_hop_list->neighbor_2_timer))
406 struct neighbor_2_list_entry *two_hop_to_delete;
407 struct neighbor_2_entry *two_hop_entry = two_hop_list->neighbor_2;
409 two_hop_entry->neighbor_2_pointer--;
410 olsr_delete_neighbor_pointer(two_hop_entry, &neighbor->neighbor_main_addr);
412 if(two_hop_entry->neighbor_2_pointer < 1)
414 DEQUEUE_ELEM(two_hop_entry);
415 free((void *)two_hop_entry);
418 two_hop_to_delete = two_hop_list;
419 two_hop_list = two_hop_list->next;
422 DEQUEUE_ELEM(two_hop_to_delete);
424 free(two_hop_to_delete);
426 /* This flag is set to OLSR_TRUE to recalculate the MPR set and the routing table*/
427 changes_neighborhood = OLSR_TRUE;
428 changes_topology = OLSR_TRUE;
432 two_hop_list = two_hop_list->next;
442 olsr_time_out_neighborhood_tables()
446 for(index=0;index<HASHSIZE;index++)
448 struct neighbor_entry *entry = neighbortable[index].next;
450 while(entry != &neighbortable[index])
452 olsr_time_out_two_hop_neighbors(entry);
463 *Prints the registered neighbors and two hop neighbors
469 olsr_print_neighbor_table()
474 olsr_printf(1, "\n--- %02d:%02d:%02d.%02d ------------------------------------------------ NEIGHBORS\n\n",
480 if (olsr_cnf->ip_version == AF_INET)
482 olsr_printf(1, "IP address LQ NLQ SYM MPR MPRS will\n");
483 fstr = "%-15s %5.3f %5.3f %s %s %s %d\n";
488 olsr_printf(1, "IP address LQ NLQ SYM MPR MPRS will\n");
489 fstr = "%-39s %5.3f %5.3f %s %s %s %d\n";
492 for (i = 0; i < HASHSIZE; i++)
494 struct neighbor_entry *neigh;
495 for(neigh = neighbortable[i].next; neigh != &neighbortable[i];
498 struct link_entry *link = olsr_neighbor_best_link(&neigh->neighbor_main_addr);
499 double best_lq = link->neigh_link_quality;
500 double inv_best_lq = link->loss_link_quality;
502 olsr_printf(1, fstr, olsr_ip_to_string(&neigh->neighbor_main_addr),
503 inv_best_lq, best_lq,
504 (neigh->status == SYM) ? "YES " : "NO ",
505 neigh->is_mpr ? "YES " : "NO ",
506 olsr_lookup_mprs_set(&neigh->neighbor_main_addr) == NULL ? "NO " : "YES ",