info: java: update workspace
[olsrd.git] / src / neighbor_table.c
1 /*
2  * The olsr.org Optimized Link-State Routing daemon (olsrd)
3  *
4  * (c) by the OLSR project
5  *
6  * See our Git repository to find out who worked on this file
7  * and thus is a copyright holder on it.
8  *
9  * All rights reserved.
10  *
11  * Redistribution and use in source and binary forms, with or without
12  * modification, are permitted provided that the following conditions
13  * are met:
14  *
15  * * Redistributions of source code must retain the above copyright
16  *   notice, this list of conditions and the following disclaimer.
17  * * Redistributions in binary form must reproduce the above copyright
18  *   notice, this list of conditions and the following disclaimer in
19  *   the documentation and/or other materials provided with the
20  *   distribution.
21  * * Neither the name of olsr.org, olsrd nor the names of its
22  *   contributors may be used to endorse or promote products derived
23  *   from this software without specific prior written permission.
24  *
25  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
26  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
27  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
28  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
29  * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
30  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
31  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
32  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
33  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
34  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
35  * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
36  * POSSIBILITY OF SUCH DAMAGE.
37  *
38  * Visit http://www.olsr.org for more information.
39  *
40  * If you find this software useful feel free to make a donation
41  * to the project. For more information see the website or contact
42  * the copyright holders.
43  *
44  */
45
46 #include "ipcalc.h"
47 #include "defs.h"
48 #include "two_hop_neighbor_table.h"
49 #include "mid_set.h"
50 #include "mpr.h"
51 #include "neighbor_table.h"
52 #include "olsr.h"
53 #include "scheduler.h"
54 #include "link_set.h"
55 #include "mpr_selector_set.h"
56 #include "net_olsr.h"
57
58 struct neighbor_entry neighbortable[HASHSIZE];
59
60 void
61 olsr_init_neighbor_table(void)
62 {
63   int i;
64
65   for (i = 0; i < HASHSIZE; i++) {
66     neighbortable[i].next = &neighbortable[i];
67     neighbortable[i].prev = &neighbortable[i];
68   }
69 }
70
71 /**
72  * Unlink, delete and free a nbr2_list entry.
73  */
74 static void
75 olsr_del_nbr2_list(struct neighbor_2_list_entry *nbr2_list)
76 {
77   struct neighbor_2_entry *nbr2;
78
79   nbr2 = nbr2_list->neighbor_2;
80
81   if (nbr2->neighbor_2_pointer < 1) {
82     DEQUEUE_ELEM(nbr2);
83     free(nbr2);
84   }
85
86   /*
87    * Kill running timers.
88    */
89   olsr_stop_timer(nbr2_list->nbr2_list_timer);
90   nbr2_list->nbr2_list_timer = NULL;
91
92   /* Dequeue */
93   DEQUEUE_ELEM(nbr2_list);
94
95   free(nbr2_list);
96
97   /* Set flags to recalculate the MPR set and the routing table */
98   changes_neighborhood = true;
99   changes_topology = true;
100 }
101
102 /**
103  * Delete a two hop neighbor from a neighbors two hop neighbor list.
104  *
105  * @param neighbor the neighbor to delete the two hop neighbor from.
106  * @param neigh2 the IP address of the two hop neighbor to delete.
107  *
108  * @return positive if entry deleted
109  */
110 int
111 olsr_delete_neighbor_2_pointer(struct neighbor_entry *neighbor, struct neighbor_2_entry *neigh2)
112 {
113   struct neighbor_2_list_entry *nbr2_list;
114
115   nbr2_list = neighbor->neighbor_2_list.next;
116
117   while (nbr2_list != &neighbor->neighbor_2_list) {
118     if (nbr2_list->neighbor_2 == neigh2) {
119       olsr_del_nbr2_list(nbr2_list);
120       return 1;
121     }
122     nbr2_list = nbr2_list->next;
123   }
124   return 0;
125 }
126
127 /**
128  *Check if a two hop neighbor is reachable via a given
129  *neighbor.
130  *
131  *@param neighbor neighbor-entry to check via
132  *@param neighbor_main_address the addres of the two hop neighbor
133  *to find.
134  *
135  *@return a pointer to the neighbor_2_list_entry struct
136  *representing the two hop neighbor if found. NULL if not found.
137  */
138 struct neighbor_2_list_entry *
139 olsr_lookup_my_neighbors(const struct neighbor_entry *neighbor, const union olsr_ip_addr *neighbor_main_address)
140 {
141   struct neighbor_2_list_entry *entry;
142
143   for (entry = neighbor->neighbor_2_list.next; entry != &neighbor->neighbor_2_list; entry = entry->next) {
144
145     if (ipequal(&entry->neighbor_2->neighbor_2_addr, neighbor_main_address))
146       return entry;
147
148   }
149   return NULL;
150 }
151
152 /**
153  * Update a neighbours main_addr inlcuding hash
154 */
155
156 void
157 olsr_update_neighbor_main_addr(struct neighbor_entry *entry, const union olsr_ip_addr *new_main_addr)
158 {
159   /*remove from old pos*/
160   DEQUEUE_ELEM(entry);
161
162   /*update main addr*/
163   entry->neighbor_main_addr = *new_main_addr;
164
165   /*insert it again*/
166   QUEUE_ELEM(neighbortable[olsr_ip_hashing(new_main_addr)], entry);
167
168 }
169
170 /**
171  *Delete a neighbr table entry.
172  *
173  *Remember: Deleting a neighbor entry results
174  *the deletion of its 2 hop neighbors list!!!
175  *@param neighbor_addr the neighbor entry to delete
176  *
177  *@return always 1
178  */
179
180 int
181 olsr_delete_neighbor_table(const union olsr_ip_addr *neighbor_addr)
182 {
183   struct neighbor_2_list_entry *two_hop_list, *two_hop_to_delete;
184   uint32_t hash;
185   struct neighbor_entry *entry;
186
187   //printf("inserting neighbor\n");
188
189   hash = olsr_ip_hashing(neighbor_addr);
190
191   entry = neighbortable[hash].next;
192
193   /*
194    * Find neighbor entry
195    */
196   while (entry != &neighbortable[hash]) {
197     if (ipequal(&entry->neighbor_main_addr, neighbor_addr))
198       break;
199
200     entry = entry->next;
201   }
202
203   if (entry == &neighbortable[hash])
204     return 0;
205
206   two_hop_list = entry->neighbor_2_list.next;
207
208   while (two_hop_list != &entry->neighbor_2_list) {
209     two_hop_to_delete = two_hop_list;
210     two_hop_list = two_hop_list->next;
211
212     two_hop_to_delete->neighbor_2->neighbor_2_pointer--;
213     olsr_delete_neighbor_pointer(two_hop_to_delete->neighbor_2, entry);
214
215     olsr_del_nbr2_list(two_hop_to_delete);
216   }
217
218   /* Dequeue */
219   DEQUEUE_ELEM(entry);
220
221   free(entry);
222
223   changes_neighborhood = true;
224   signal_link_changes(true);
225   return 1;
226
227 }
228
229 /**
230  *Insert a neighbor entry in the neighbor table
231  *
232  *@param main_addr the main address of the new node
233  *
234  *@return 0 if neighbor already exists 1 if inserted
235  */
236 struct neighbor_entry *
237 olsr_insert_neighbor_table(const union olsr_ip_addr *main_addr)
238 {
239   uint32_t hash;
240   struct neighbor_entry *new_neigh;
241
242   hash = olsr_ip_hashing(main_addr);
243
244   /* Check if entry exists */
245
246   for (new_neigh = neighbortable[hash].next; new_neigh != &neighbortable[hash]; new_neigh = new_neigh->next) {
247     if (ipequal(&new_neigh->neighbor_main_addr, main_addr))
248       return new_neigh;
249   }
250
251   //printf("inserting neighbor\n");
252
253   new_neigh = olsr_malloc(sizeof(struct neighbor_entry), "New neighbor entry");
254
255   /* Set address, willingness and status */
256   new_neigh->neighbor_main_addr = *main_addr;
257   new_neigh->willingness = WILL_NEVER;
258   new_neigh->status = NOT_SYM;
259
260   new_neigh->neighbor_2_list.next = &new_neigh->neighbor_2_list;
261   new_neigh->neighbor_2_list.prev = &new_neigh->neighbor_2_list;
262
263   new_neigh->linkcount = 0;
264   new_neigh->is_mpr = false;
265   new_neigh->was_mpr = false;
266
267   /* Queue */
268   QUEUE_ELEM(neighbortable[hash], new_neigh);
269
270   return new_neigh;
271 }
272
273 /**
274  *Lookup a neighbor entry in the neighbortable based on an address.
275  *
276  *@param dst the IP address of the neighbor to look up
277  *
278  *@return a pointer to the neighbor struct registered on the given
279  *address. NULL if not found.
280  */
281 struct neighbor_entry *
282 olsr_lookup_neighbor_table(const union olsr_ip_addr *dst)
283 {
284   /*
285    *Find main address of node
286    */
287   union olsr_ip_addr *tmp_ip = mid_lookup_main_addr(dst);
288   if (tmp_ip != NULL)
289     dst = tmp_ip;
290   return olsr_lookup_neighbor_table_alias(dst);
291 }
292
293 /**
294  *Lookup a neighbor entry in the neighbortable based on an address.
295  *
296  *@param dst the IP address of the neighbor to look up
297  *
298  *@return a pointer to the neighbor struct registered on the given
299  *address. NULL if not found.
300  */
301 struct neighbor_entry *
302 olsr_lookup_neighbor_table_alias(const union olsr_ip_addr *dst)
303 {
304   struct neighbor_entry *entry;
305   uint32_t hash = olsr_ip_hashing(dst);
306
307   //printf("\nLookup %s\n", olsr_ip_to_string(&buf, dst));
308   for (entry = neighbortable[hash].next; entry != &neighbortable[hash]; entry = entry->next) {
309     //printf("Checking %s\n", olsr_ip_to_string(&buf, &entry->neighbor_main_addr));
310     if (ipequal(&entry->neighbor_main_addr, dst))
311       return entry;
312
313   }
314   //printf("NOPE\n\n");
315
316   return NULL;
317
318 }
319
320 int
321 update_neighbor_status(struct neighbor_entry *entry, int lnk)
322 {
323   /*
324    * Update neighbor entry
325    */
326
327   if (lnk == SYM_LINK) {
328     /* N_status is set to SYM */
329     if (entry->status == NOT_SYM) {
330       struct neighbor_2_entry *two_hop_neighbor;
331
332       /* Delete posible 2 hop entry on this neighbor */
333       if ((two_hop_neighbor = olsr_lookup_two_hop_neighbor_table(&entry->neighbor_main_addr)) != NULL) {
334         olsr_delete_two_hop_neighbor_table(two_hop_neighbor);
335       }
336
337       changes_neighborhood = true;
338       changes_topology = true;
339       if (olsr_cnf->tc_redundancy > 1)
340         signal_link_changes(true);
341     }
342     entry->status = SYM;
343   } else {
344     if (entry->status == SYM) {
345       changes_neighborhood = true;
346       changes_topology = true;
347       if (olsr_cnf->tc_redundancy > 1)
348         signal_link_changes(true);
349     }
350     /* else N_status is set to NOT_SYM */
351     entry->status = NOT_SYM;
352     /* remove neighbor from routing list */
353   }
354
355   return entry->status;
356 }
357
358 /**
359  * Callback for the nbr2_list timer.
360  */
361 void
362 olsr_expire_nbr2_list(void *context)
363 {
364   struct neighbor_2_list_entry *nbr2_list;
365   struct neighbor_entry *nbr;
366   struct neighbor_2_entry *nbr2;
367
368   nbr2_list = (struct neighbor_2_list_entry *)context;
369   nbr2_list->nbr2_list_timer = NULL;
370
371   nbr = nbr2_list->nbr2_nbr;
372   nbr2 = nbr2_list->neighbor_2;
373
374   nbr2->neighbor_2_pointer--;
375   olsr_delete_neighbor_pointer(nbr2, nbr);
376
377   olsr_del_nbr2_list(nbr2_list);
378 }
379
380 /**
381  *Prints the registered neighbors and two hop neighbors
382  *to STDOUT.
383  *
384  *@return nada
385  */
386 #ifndef NODEBUG
387 void
388 olsr_print_neighbor_table(void)
389 {
390   /* The whole function doesn't do anything else. */
391   const int iplen = olsr_cnf->ip_version == AF_INET ? (INET_ADDRSTRLEN - 1) : (INET6_ADDRSTRLEN - 1);
392   int idx;
393
394   OLSR_PRINTF(1,
395               "\n--- %s ------------------------------------------------ NEIGHBORS\n\n"
396               "%*s\tHyst\tLQ\tETX\tSYM   MPR   MPRS  will\n", olsr_wallclock_string(),
397               iplen, "IP address");
398
399   for (idx = 0; idx < HASHSIZE; idx++) {
400     struct neighbor_entry *neigh;
401     for (neigh = neighbortable[idx].next; neigh != &neighbortable[idx]; neigh = neigh->next) {
402       struct link_entry *lnk = get_best_link_to_neighbor(&neigh->neighbor_main_addr);
403       if (lnk) {
404         struct ipaddr_str buf;
405         struct lqtextbuffer lqbuffer1, lqbuffer2;
406
407         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),
408                     (double)lnk->L_link_quality,
409                     get_link_entry_text(lnk, '/', &lqbuffer1),
410                     get_linkcost_text(lnk->linkcost,false, &lqbuffer2),
411                     neigh->status == SYM ? "YES " : "NO  ",
412                     neigh->is_mpr ? "YES " : "NO  ",
413                     olsr_lookup_mprs_set(&neigh->neighbor_main_addr) == NULL ? "NO  " : "YES ",
414                     neigh->willingness);
415       }
416     }
417   }
418 }
419 #endif /* NODEBUG */
420
421 /*
422  * Local Variables:
423  * c-basic-offset: 2
424  * indent-tabs-mode: nil
425  * End:
426  */