c223201ec0305d0343f569e6f67c37ad46f86023
[olsrd.git] / src / neighbor_table.c
1
2 /*
3  * The olsr.org Optimized Link-State Routing daemon(olsrd)
4  * Copyright (c) 2004, Andreas Tonnesen(andreto@olsr.org)
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 "two_hop_neighbor_table.h"
45 #include "mid_set.h"
46 #include "mpr.h"
47 #include "neighbor_table.h"
48 #include "olsr.h"
49 #include "scheduler.h"
50 #include "link_set.h"
51 #include "mpr_selector_set.h"
52 #include "net_olsr.h"
53
54 struct neighbor_entry neighbortable[HASHSIZE];
55
56 void
57 olsr_init_neighbor_table(void)
58 {
59   int i;
60
61   for (i = 0; i < HASHSIZE; i++) {
62     neighbortable[i].next = &neighbortable[i];
63     neighbortable[i].prev = &neighbortable[i];
64   }
65 }
66
67 /**
68  * Unlink, delete and free a nbr2_list entry.
69  */
70 static void
71 olsr_del_nbr2_list(struct neighbor_2_list_entry *nbr2_list)
72 {
73   struct neighbor_entry *nbr;
74   struct neighbor_2_entry *nbr2;
75
76   nbr = nbr2_list->nbr2_nbr;
77   nbr2 = nbr2_list->neighbor_2;
78
79   if (nbr2->neighbor_2_pointer < 1) {
80     DEQUEUE_ELEM(nbr2);
81     free(nbr2);
82   }
83
84   /*
85    * Kill running timers.
86    */
87   olsr_stop_timer(nbr2_list->nbr2_list_timer);
88   nbr2_list->nbr2_list_timer = NULL;
89
90   /* Dequeue */
91   DEQUEUE_ELEM(nbr2_list);
92
93   free(nbr2_list);
94
95   /* Set flags to recalculate the MPR set and the routing table */
96   changes_neighborhood = true;
97   changes_topology = true;
98 }
99
100 /**
101  * Delete a two hop neighbor from a neighbors two hop neighbor list.
102  *
103  * @param neighbor the neighbor to delete the two hop neighbor from.
104  * @param address the IP address of the two hop neighbor to delete.
105  *
106  * @return positive if entry deleted
107  */
108 int
109 olsr_delete_neighbor_2_pointer(struct neighbor_entry *neighbor, struct neighbor_2_entry *neigh2)
110 {
111   struct neighbor_2_list_entry *nbr2_list;
112
113   nbr2_list = neighbor->neighbor_2_list.next;
114
115   while (nbr2_list != &neighbor->neighbor_2_list) {
116     if (nbr2_list->neighbor_2 == neigh2) {
117       olsr_del_nbr2_list(nbr2_list);
118       return 1;
119     }
120     nbr2_list = nbr2_list->next;
121   }
122   return 0;
123 }
124
125 /**
126  *Check if a two hop neighbor is reachable via a given
127  *neighbor.
128  *
129  *@param neighbor neighbor-entry to check via
130  *@param neighbor_main_address the addres of the two hop neighbor
131  *to find.
132  *
133  *@return a pointer to the neighbor_2_list_entry struct
134  *representing the two hop neighbor if found. NULL if not found.
135  */
136 struct neighbor_2_list_entry *
137 olsr_lookup_my_neighbors(const struct neighbor_entry *neighbor, const union olsr_ip_addr *neighbor_main_address)
138 {
139   struct neighbor_2_list_entry *entry;
140
141   for (entry = neighbor->neighbor_2_list.next; entry != &neighbor->neighbor_2_list; entry = entry->next) {
142
143     if (ipequal(&entry->neighbor_2->neighbor_2_addr, neighbor_main_address))
144       return entry;
145
146   }
147   return NULL;
148 }
149
150 /**
151  * Update a neighbours main_addr inlcuding hash
152 */
153
154 int 
155 olsr_update_neighbor_main_addr(struct neighbor_entry *entry, const union olsr_ip_addr *new_main_addr)
156 {
157   /*uint32_t hash = olsr_ip_hashing(&neigh->neighbor_main_addr);
158   
159   struct neighbor_entry *entry;
160
161   entry = neighbortable[hash].next;
162
163   while (entry != &neighbortable[hash]) {
164     if (ipequal(&entry->neighbor_main_addr, &neigh->neighbor_main_addr))
165       break;
166
167     entry = entry->next;
168   }
169
170   if (entry == &neighbortable[hash])
171     return 0;
172
173   if (entry == neigh) printf("bullshit\n");
174   else printf("updating neighbor has!\n");*/
175
176   //remove from old pos
177   DEQUEUE_ELEM(entry);
178
179   //update entry
180   entry->neighbor_main_addr = *new_main_addr;
181
182   //insert it again
183   QUEUE_ELEM(neighbortable[olsr_ip_hashing(new_main_addr)], entry);
184
185 }
186
187 /**
188  *Delete a neighbr table entry.
189  *
190  *Remember: Deleting a neighbor entry results
191  *the deletion of its 2 hop neighbors list!!!
192  *@param neighbor the neighbor entry to delete
193  *
194  *@return nada
195  */
196
197 int
198 olsr_delete_neighbor_table(const union olsr_ip_addr *neighbor_addr)
199 {
200   struct neighbor_2_list_entry *two_hop_list, *two_hop_to_delete;
201   uint32_t hash;
202   struct neighbor_entry *entry;
203
204   //printf("inserting neighbor\n");
205
206   hash = olsr_ip_hashing(neighbor_addr);
207
208   entry = neighbortable[hash].next;
209
210   /*
211    * Find neighbor entry
212    */
213   while (entry != &neighbortable[hash]) {
214     if (ipequal(&entry->neighbor_main_addr, neighbor_addr))
215       break;
216
217     entry = entry->next;
218   }
219
220   if (entry == &neighbortable[hash])
221     return 0;
222
223   two_hop_list = entry->neighbor_2_list.next;
224
225   while (two_hop_list != &entry->neighbor_2_list) {
226     two_hop_to_delete = two_hop_list;
227     two_hop_list = two_hop_list->next;
228
229     two_hop_to_delete->neighbor_2->neighbor_2_pointer--;
230     olsr_delete_neighbor_pointer(two_hop_to_delete->neighbor_2, entry);
231
232     olsr_del_nbr2_list(two_hop_to_delete);
233   }
234
235   /* Dequeue */
236   DEQUEUE_ELEM(entry);
237
238   free(entry);
239
240   changes_neighborhood = true;
241   return 1;
242
243 }
244
245 /**
246  *Insert a neighbor entry in the neighbor table
247  *
248  *@param main_addr the main address of the new node
249  *
250  *@return 0 if neighbor already exists 1 if inserted
251  */
252 struct neighbor_entry *
253 olsr_insert_neighbor_table(const union olsr_ip_addr *main_addr)
254 {
255   uint32_t hash;
256   struct neighbor_entry *new_neigh;
257
258   hash = olsr_ip_hashing(main_addr);
259
260   /* Check if entry exists */
261
262   for (new_neigh = neighbortable[hash].next; new_neigh != &neighbortable[hash]; new_neigh = new_neigh->next) {
263     if (ipequal(&new_neigh->neighbor_main_addr, main_addr))
264       return new_neigh;
265   }
266
267   //printf("inserting neighbor\n");
268
269   new_neigh = olsr_malloc(sizeof(struct neighbor_entry), "New neighbor entry");
270
271   /* Set address, willingness and status */
272   new_neigh->neighbor_main_addr = *main_addr;
273   new_neigh->willingness = WILL_NEVER;
274   new_neigh->status = NOT_SYM;
275
276   new_neigh->neighbor_2_list.next = &new_neigh->neighbor_2_list;
277   new_neigh->neighbor_2_list.prev = &new_neigh->neighbor_2_list;
278
279   new_neigh->linkcount = 0;
280   new_neigh->is_mpr = false;
281   new_neigh->was_mpr = false;
282
283   /* Queue */
284   QUEUE_ELEM(neighbortable[hash], new_neigh);
285
286   return new_neigh;
287 }
288
289 /**
290  *Lookup a neighbor entry in the neighbortable based on an address.
291  *
292  *@param dst the IP address of the neighbor to look up
293  *
294  *@return a pointer to the neighbor struct registered on the given
295  *address. NULL if not found.
296  */
297 struct neighbor_entry *
298 olsr_lookup_neighbor_table(const union olsr_ip_addr *dst)
299 {
300   /*
301    *Find main address of node
302    */
303   union olsr_ip_addr *tmp_ip = mid_lookup_main_addr(dst);
304   if (tmp_ip != NULL)
305     dst = tmp_ip;
306   return olsr_lookup_neighbor_table_alias(dst);
307 }
308
309 /**
310  *Lookup a neighbor entry in the neighbortable based on an address.
311  *
312  *@param dst the IP address of the neighbor to look up
313  *
314  *@return a pointer to the neighbor struct registered on the given
315  *address. NULL if not found.
316  */
317 struct neighbor_entry *
318 olsr_lookup_neighbor_table_alias(const union olsr_ip_addr *dst)
319 {
320   struct neighbor_entry *entry;
321   uint32_t hash = olsr_ip_hashing(dst);
322
323   //printf("\nLookup %s\n", olsr_ip_to_string(&buf, dst));
324   for (entry = neighbortable[hash].next; entry != &neighbortable[hash]; entry = entry->next) {
325     //printf("Checking %s\n", olsr_ip_to_string(&buf, &entry->neighbor_main_addr));
326     if (ipequal(&entry->neighbor_main_addr, dst))
327       return entry;
328
329   }
330   //printf("NOPE\n\n");
331
332   return NULL;
333
334 }
335
336 //check if all neighbour entries are findable in neighbour table
337 bool
338 olsr_lookup_neighbor_table_check(void)
339 {
340   struct ipaddr_str buf1;
341   struct neighbor_entry *entry;
342   printf("\n checking neighbour table: ");
343   /* Neighbors */
344   OLSR_FOR_ALL_NBR_ENTRIES(entry) {
345     printf("%s, ",olsr_ip_to_string(&buf1, &entry->neighbor_main_addr));
346     if (olsr_lookup_neighbor_table_alias(&entry->neighbor_main_addr)==NULL) {
347       struct neighbor_2_list_entry *two_hop_list, *two_hop_to_delete;
348       printf("-> entry has wrong hash!");
349       return true;
350     }
351   }
352   OLSR_FOR_ALL_NBR_ENTRIES_END(neigh);
353   return false;
354 }
355
356
357 int
358 update_neighbor_status(struct neighbor_entry *entry, int lnk)
359 {
360   /*
361    * Update neighbor entry
362    */
363
364   if (lnk == SYM_LINK) {
365     /* N_status is set to SYM */
366     if (entry->status == NOT_SYM) {
367       struct neighbor_2_entry *two_hop_neighbor;
368
369       /* Delete posible 2 hop entry on this neighbor */
370       if ((two_hop_neighbor = olsr_lookup_two_hop_neighbor_table(&entry->neighbor_main_addr)) != NULL) {
371         olsr_delete_two_hop_neighbor_table(two_hop_neighbor);
372       }
373
374       changes_neighborhood = true;
375       changes_topology = true;
376       if (olsr_cnf->tc_redundancy > 1)
377         signal_link_changes(true);
378     }
379     entry->status = SYM;
380   } else {
381     if (entry->status == SYM) {
382       changes_neighborhood = true;
383       changes_topology = true;
384       if (olsr_cnf->tc_redundancy > 1)
385         signal_link_changes(true);
386     }
387     /* else N_status is set to NOT_SYM */
388     entry->status = NOT_SYM;
389     /* remove neighbor from routing list */
390   }
391
392   return entry->status;
393 }
394
395 /**
396  * Callback for the nbr2_list timer.
397  */
398 void
399 olsr_expire_nbr2_list(void *context)
400 {
401   struct neighbor_2_list_entry *nbr2_list;
402   struct neighbor_entry *nbr;
403   struct neighbor_2_entry *nbr2;
404
405   nbr2_list = (struct neighbor_2_list_entry *)context;
406   nbr2_list->nbr2_list_timer = NULL;
407
408   nbr = nbr2_list->nbr2_nbr;
409   nbr2 = nbr2_list->neighbor_2;
410
411   nbr2->neighbor_2_pointer--;
412   olsr_delete_neighbor_pointer(nbr2, nbr);
413
414   olsr_del_nbr2_list(nbr2_list);
415 }
416
417 /**
418  *Prints the registered neighbors and two hop neighbors
419  *to STDOUT.
420  *
421  *@return nada
422  */
423 void
424 olsr_print_neighbor_table(void)
425 {
426 #ifdef NODEBUG
427   /* The whole function doesn't do anything else. */
428 #ifndef NODEBUG
429   const int iplen = olsr_cnf->ip_version == AF_INET ? 15 : 39;
430 #endif
431   int idx;
432   OLSR_PRINTF(1,
433               "\n--- %02d:%02d:%02d.%02d ------------------------------------------------ NEIGHBORS\n\n"
434               "%*s  LQ     NLQ    SYM   MPR   MPRS  will\n", nowtm->tm_hour, nowtm->tm_min, nowtm->tm_sec, (int)now.tv_usec / 10000,
435               iplen, "IP address");
436
437   for (idx = 0; idx < HASHSIZE; idx++) {
438     struct neighbor_entry *neigh;
439     for (neigh = neighbortable[idx].next; neigh != &neighbortable[idx]; neigh = neigh->next) {
440       struct link_entry *lnk = get_best_link_to_neighbor(&neigh->neighbor_main_addr);
441       if (lnk) {
442         struct ipaddr_str buf;
443         OLSR_PRINTF(1, "%-*s  %5.3f  %5.3f  %s  %s  %s  %d\n", iplen, olsr_ip_to_string(&buf, &neigh->neighbor_main_addr),
444                     lnk->loss_link_quality, lnk->neigh_link_quality, neigh->status == SYM ? "YES " : "NO  ",
445                     neigh->is_mpr ? "YES " : "NO  ", olsr_lookup_mprs_set(&neigh->neighbor_main_addr) == NULL ? "NO  " : "YES ",
446                     neigh->willingness);
447       }
448     }
449   }
450 #endif
451 }
452
453 /*
454  * Local Variables:
455  * c-basic-offset: 2
456  * indent-tabs-mode: nil
457  * End:
458  */