neighbors: signal link changes when deleting a neighbor
[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_2_entry *nbr2;
74
75   nbr2 = nbr2_list->neighbor_2;
76
77   if (nbr2->neighbor_2_pointer < 1) {
78     DEQUEUE_ELEM(nbr2);
79     free(nbr2);
80   }
81
82   /*
83    * Kill running timers.
84    */
85   olsr_stop_timer(nbr2_list->nbr2_list_timer);
86   nbr2_list->nbr2_list_timer = NULL;
87
88   /* Dequeue */
89   DEQUEUE_ELEM(nbr2_list);
90
91   free(nbr2_list);
92
93   /* Set flags to recalculate the MPR set and the routing table */
94   changes_neighborhood = true;
95   changes_topology = true;
96 }
97
98 /**
99  * Delete a two hop neighbor from a neighbors two hop neighbor list.
100  *
101  * @param neighbor the neighbor to delete the two hop neighbor from.
102  * @param neigh2 the IP address of the two hop neighbor to delete.
103  *
104  * @return positive if entry deleted
105  */
106 int
107 olsr_delete_neighbor_2_pointer(struct neighbor_entry *neighbor, struct neighbor_2_entry *neigh2)
108 {
109   struct neighbor_2_list_entry *nbr2_list;
110
111   nbr2_list = neighbor->neighbor_2_list.next;
112
113   while (nbr2_list != &neighbor->neighbor_2_list) {
114     if (nbr2_list->neighbor_2 == neigh2) {
115       olsr_del_nbr2_list(nbr2_list);
116       return 1;
117     }
118     nbr2_list = nbr2_list->next;
119   }
120   return 0;
121 }
122
123 /**
124  *Check if a two hop neighbor is reachable via a given
125  *neighbor.
126  *
127  *@param neighbor neighbor-entry to check via
128  *@param neighbor_main_address the addres of the two hop neighbor
129  *to find.
130  *
131  *@return a pointer to the neighbor_2_list_entry struct
132  *representing the two hop neighbor if found. NULL if not found.
133  */
134 struct neighbor_2_list_entry *
135 olsr_lookup_my_neighbors(const struct neighbor_entry *neighbor, const union olsr_ip_addr *neighbor_main_address)
136 {
137   struct neighbor_2_list_entry *entry;
138
139   for (entry = neighbor->neighbor_2_list.next; entry != &neighbor->neighbor_2_list; entry = entry->next) {
140
141     if (ipequal(&entry->neighbor_2->neighbor_2_addr, neighbor_main_address))
142       return entry;
143
144   }
145   return NULL;
146 }
147
148 /**
149  * Update a neighbours main_addr inlcuding hash
150 */
151
152 void
153 olsr_update_neighbor_main_addr(struct neighbor_entry *entry, const union olsr_ip_addr *new_main_addr)
154 {
155   /*remove from old pos*/
156   DEQUEUE_ELEM(entry);
157
158   /*update main addr*/
159   entry->neighbor_main_addr = *new_main_addr;
160
161   /*insert it again*/
162   QUEUE_ELEM(neighbortable[olsr_ip_hashing(new_main_addr)], entry);
163
164 }
165
166 /**
167  *Delete a neighbr table entry.
168  *
169  *Remember: Deleting a neighbor entry results
170  *the deletion of its 2 hop neighbors list!!!
171  *@param neighbor_addr the neighbor entry to delete
172  *
173  *@return always 1
174  */
175
176 int
177 olsr_delete_neighbor_table(const union olsr_ip_addr *neighbor_addr)
178 {
179   struct neighbor_2_list_entry *two_hop_list, *two_hop_to_delete;
180   uint32_t hash;
181   struct neighbor_entry *entry;
182
183   //printf("inserting neighbor\n");
184
185   hash = olsr_ip_hashing(neighbor_addr);
186
187   entry = neighbortable[hash].next;
188
189   /*
190    * Find neighbor entry
191    */
192   while (entry != &neighbortable[hash]) {
193     if (ipequal(&entry->neighbor_main_addr, neighbor_addr))
194       break;
195
196     entry = entry->next;
197   }
198
199   if (entry == &neighbortable[hash])
200     return 0;
201
202   two_hop_list = entry->neighbor_2_list.next;
203
204   while (two_hop_list != &entry->neighbor_2_list) {
205     two_hop_to_delete = two_hop_list;
206     two_hop_list = two_hop_list->next;
207
208     two_hop_to_delete->neighbor_2->neighbor_2_pointer--;
209     olsr_delete_neighbor_pointer(two_hop_to_delete->neighbor_2, entry);
210
211     olsr_del_nbr2_list(two_hop_to_delete);
212   }
213
214   /* Dequeue */
215   DEQUEUE_ELEM(entry);
216
217   free(entry);
218
219   changes_neighborhood = true;
220   signal_link_changes(true);
221   return 1;
222
223 }
224
225 /**
226  *Insert a neighbor entry in the neighbor table
227  *
228  *@param main_addr the main address of the new node
229  *
230  *@return 0 if neighbor already exists 1 if inserted
231  */
232 struct neighbor_entry *
233 olsr_insert_neighbor_table(const union olsr_ip_addr *main_addr)
234 {
235   uint32_t hash;
236   struct neighbor_entry *new_neigh;
237
238   hash = olsr_ip_hashing(main_addr);
239
240   /* Check if entry exists */
241
242   for (new_neigh = neighbortable[hash].next; new_neigh != &neighbortable[hash]; new_neigh = new_neigh->next) {
243     if (ipequal(&new_neigh->neighbor_main_addr, main_addr))
244       return new_neigh;
245   }
246
247   //printf("inserting neighbor\n");
248
249   new_neigh = olsr_malloc(sizeof(struct neighbor_entry), "New neighbor entry");
250
251   /* Set address, willingness and status */
252   new_neigh->neighbor_main_addr = *main_addr;
253   new_neigh->willingness = WILL_NEVER;
254   new_neigh->status = NOT_SYM;
255
256   new_neigh->neighbor_2_list.next = &new_neigh->neighbor_2_list;
257   new_neigh->neighbor_2_list.prev = &new_neigh->neighbor_2_list;
258
259   new_neigh->linkcount = 0;
260   new_neigh->is_mpr = false;
261   new_neigh->was_mpr = false;
262
263   /* Queue */
264   QUEUE_ELEM(neighbortable[hash], new_neigh);
265
266   return new_neigh;
267 }
268
269 /**
270  *Lookup a neighbor entry in the neighbortable based on an address.
271  *
272  *@param dst the IP address of the neighbor to look up
273  *
274  *@return a pointer to the neighbor struct registered on the given
275  *address. NULL if not found.
276  */
277 struct neighbor_entry *
278 olsr_lookup_neighbor_table(const union olsr_ip_addr *dst)
279 {
280   /*
281    *Find main address of node
282    */
283   union olsr_ip_addr *tmp_ip = mid_lookup_main_addr(dst);
284   if (tmp_ip != NULL)
285     dst = tmp_ip;
286   return olsr_lookup_neighbor_table_alias(dst);
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_alias(const union olsr_ip_addr *dst)
299 {
300   struct neighbor_entry *entry;
301   uint32_t hash = olsr_ip_hashing(dst);
302
303   //printf("\nLookup %s\n", olsr_ip_to_string(&buf, dst));
304   for (entry = neighbortable[hash].next; entry != &neighbortable[hash]; entry = entry->next) {
305     //printf("Checking %s\n", olsr_ip_to_string(&buf, &entry->neighbor_main_addr));
306     if (ipequal(&entry->neighbor_main_addr, dst))
307       return entry;
308
309   }
310   //printf("NOPE\n\n");
311
312   return NULL;
313
314 }
315
316 int
317 update_neighbor_status(struct neighbor_entry *entry, int lnk)
318 {
319   /*
320    * Update neighbor entry
321    */
322
323   if (lnk == SYM_LINK) {
324     /* N_status is set to SYM */
325     if (entry->status == NOT_SYM) {
326       struct neighbor_2_entry *two_hop_neighbor;
327
328       /* Delete posible 2 hop entry on this neighbor */
329       if ((two_hop_neighbor = olsr_lookup_two_hop_neighbor_table(&entry->neighbor_main_addr)) != NULL) {
330         olsr_delete_two_hop_neighbor_table(two_hop_neighbor);
331       }
332
333       changes_neighborhood = true;
334       changes_topology = true;
335       if (olsr_cnf->tc_redundancy > 1)
336         signal_link_changes(true);
337     }
338     entry->status = SYM;
339   } else {
340     if (entry->status == SYM) {
341       changes_neighborhood = true;
342       changes_topology = true;
343       if (olsr_cnf->tc_redundancy > 1)
344         signal_link_changes(true);
345     }
346     /* else N_status is set to NOT_SYM */
347     entry->status = NOT_SYM;
348     /* remove neighbor from routing list */
349   }
350
351   return entry->status;
352 }
353
354 /**
355  * Callback for the nbr2_list timer.
356  */
357 void
358 olsr_expire_nbr2_list(void *context)
359 {
360   struct neighbor_2_list_entry *nbr2_list;
361   struct neighbor_entry *nbr;
362   struct neighbor_2_entry *nbr2;
363
364   nbr2_list = (struct neighbor_2_list_entry *)context;
365   nbr2_list->nbr2_list_timer = NULL;
366
367   nbr = nbr2_list->nbr2_nbr;
368   nbr2 = nbr2_list->neighbor_2;
369
370   nbr2->neighbor_2_pointer--;
371   olsr_delete_neighbor_pointer(nbr2, nbr);
372
373   olsr_del_nbr2_list(nbr2_list);
374 }
375
376 /**
377  *Prints the registered neighbors and two hop neighbors
378  *to STDOUT.
379  *
380  *@return nada
381  */
382 #ifndef NODEBUG
383 void
384 olsr_print_neighbor_table(void)
385 {
386   /* The whole function doesn't do anything else. */
387   const int iplen = olsr_cnf->ip_version == AF_INET ? (INET_ADDRSTRLEN - 1) : (INET6_ADDRSTRLEN - 1);
388   int idx;
389
390   OLSR_PRINTF(1,
391               "\n--- %s ------------------------------------------------ NEIGHBORS\n\n"
392               "%*s\tHyst\tLQ\tETX\tSYM   MPR   MPRS  will\n", olsr_wallclock_string(),
393               iplen, "IP address");
394
395   for (idx = 0; idx < HASHSIZE; idx++) {
396     struct neighbor_entry *neigh;
397     for (neigh = neighbortable[idx].next; neigh != &neighbortable[idx]; neigh = neigh->next) {
398       struct link_entry *lnk = get_best_link_to_neighbor(&neigh->neighbor_main_addr);
399       if (lnk) {
400         struct ipaddr_str buf;
401         struct lqtextbuffer lqbuffer1, lqbuffer2;
402
403         OLSR_PRINTF(1, "%-*s\t%5.3f\t%s\t%s\t%s  %s  %s  %d\n", iplen, olsr_ip_to_string(&buf, &neigh->neighbor_main_addr),
404                     (double)lnk->L_link_quality,
405                     get_link_entry_text(lnk, '/', &lqbuffer1),
406                     get_linkcost_text(lnk->linkcost,false, &lqbuffer2),
407                     neigh->status == SYM ? "YES " : "NO  ",
408                     neigh->is_mpr ? "YES " : "NO  ",
409                     olsr_lookup_mprs_set(&neigh->neighbor_main_addr) == NULL ? "NO  " : "YES ",
410                     neigh->willingness);
411       }
412     }
413   }
414 }
415 #endif /* NODEBUG */
416
417 /*
418  * Local Variables:
419  * c-basic-offset: 2
420  * indent-tabs-mode: nil
421  * End:
422  */