ff9041570fdeded05a699e6c0ba1f927bed0de48
[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 = OLSR_TRUE;
97   changes_topology = OLSR_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, union olsr_ip_addr *address)
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 (ipequal(&nbr2_list->neighbor_2->neighbor_2_addr, address)) {
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  *Delete a neighbr table entry.
152  *
153  *Remember: Deleting a neighbor entry results
154  *the deletion of its 2 hop neighbors list!!!
155  *@param neighbor the neighbor entry to delete
156  *
157  *@return nada
158  */
159
160 int
161 olsr_delete_neighbor_table(const union olsr_ip_addr *neighbor_addr)
162 {
163   struct neighbor_2_list_entry *two_hop_list, *two_hop_to_delete;
164   olsr_u32_t hash;
165   struct neighbor_entry *entry;
166
167   //printf("inserting neighbor\n");
168
169   hash = olsr_ip_hashing(neighbor_addr);
170
171   entry = neighbortable[hash].next;
172
173   /*
174    * Find neighbor entry
175    */
176   while (entry != &neighbortable[hash]) {
177     if (ipequal(&entry->neighbor_main_addr, neighbor_addr))
178       break;
179
180     entry = entry->next;
181   }
182
183   if (entry == &neighbortable[hash])
184     return 0;
185
186   two_hop_list = entry->neighbor_2_list.next;
187
188   while (two_hop_list != &entry->neighbor_2_list) {
189     two_hop_to_delete = two_hop_list;
190     two_hop_list = two_hop_list->next;
191
192     two_hop_to_delete->neighbor_2->neighbor_2_pointer--;
193     olsr_delete_neighbor_pointer(two_hop_to_delete->neighbor_2, &entry->neighbor_main_addr);
194
195     olsr_del_nbr2_list(two_hop_to_delete);
196   }
197
198   /* Dequeue */
199   DEQUEUE_ELEM(entry);
200
201   free(entry);
202
203   changes_neighborhood = OLSR_TRUE;
204   return 1;
205
206 }
207
208 /**
209  *Insert a neighbor entry in the neighbor table
210  *
211  *@param main_addr the main address of the new node
212  *
213  *@return 0 if neighbor already exists 1 if inserted
214  */
215 struct neighbor_entry *
216 olsr_insert_neighbor_table(const union olsr_ip_addr *main_addr)
217 {
218   olsr_u32_t hash;
219   struct neighbor_entry *new_neigh;
220
221   hash = olsr_ip_hashing(main_addr);
222
223   /* Check if entry exists */
224
225   for (new_neigh = neighbortable[hash].next; new_neigh != &neighbortable[hash]; new_neigh = new_neigh->next) {
226     if (ipequal(&new_neigh->neighbor_main_addr, main_addr))
227       return new_neigh;
228   }
229
230   //printf("inserting neighbor\n");
231
232   new_neigh = olsr_malloc(sizeof(struct neighbor_entry), "New neighbor entry");
233
234   /* Set address, willingness and status */
235   new_neigh->neighbor_main_addr = *main_addr;
236   new_neigh->willingness = WILL_NEVER;
237   new_neigh->status = NOT_SYM;
238
239   new_neigh->neighbor_2_list.next = &new_neigh->neighbor_2_list;
240   new_neigh->neighbor_2_list.prev = &new_neigh->neighbor_2_list;
241
242   new_neigh->linkcount = 0;
243   new_neigh->is_mpr = OLSR_FALSE;
244   new_neigh->was_mpr = OLSR_FALSE;
245
246   /* Queue */
247   QUEUE_ELEM(neighbortable[hash], new_neigh);
248
249   return new_neigh;
250 }
251
252 /**
253  *Lookup a neighbor entry in the neighbortable based on an address.
254  *
255  *@param dst the IP address of the neighbor to look up
256  *
257  *@return a pointer to the neighbor struct registered on the given
258  *address. NULL if not found.
259  */
260 struct neighbor_entry *
261 olsr_lookup_neighbor_table(const union olsr_ip_addr *dst)
262 {
263   /*
264    *Find main address of node
265    */
266   union olsr_ip_addr *tmp_ip = mid_lookup_main_addr(dst);
267   if (tmp_ip != NULL)
268     dst = tmp_ip;
269   return olsr_lookup_neighbor_table_alias(dst);
270 }
271
272 /**
273  *Lookup a neighbor entry in the neighbortable based on an address.
274  *
275  *@param dst the IP address of the neighbor to look up
276  *
277  *@return a pointer to the neighbor struct registered on the given
278  *address. NULL if not found.
279  */
280 struct neighbor_entry *
281 olsr_lookup_neighbor_table_alias(const union olsr_ip_addr *dst)
282 {
283   struct neighbor_entry *entry;
284   olsr_u32_t hash = olsr_ip_hashing(dst);
285
286   //printf("\nLookup %s\n", olsr_ip_to_string(&buf, dst));
287   for (entry = neighbortable[hash].next; entry != &neighbortable[hash]; entry = entry->next) {
288     //printf("Checking %s\n", olsr_ip_to_string(&buf, &entry->neighbor_main_addr));
289     if (ipequal(&entry->neighbor_main_addr, dst))
290       return entry;
291
292   }
293   //printf("NOPE\n\n");
294
295   return NULL;
296
297 }
298
299 int
300 update_neighbor_status(struct neighbor_entry *entry, int lnk)
301 {
302   /*
303    * Update neighbor entry
304    */
305
306   if (lnk == SYM_LINK) {
307     /* N_status is set to SYM */
308     if (entry->status == NOT_SYM) {
309       struct neighbor_2_entry *two_hop_neighbor;
310
311       /* Delete posible 2 hop entry on this neighbor */
312       if ((two_hop_neighbor = olsr_lookup_two_hop_neighbor_table(&entry->neighbor_main_addr)) != NULL) {
313         olsr_delete_two_hop_neighbor_table(two_hop_neighbor);
314       }
315
316       changes_neighborhood = OLSR_TRUE;
317       changes_topology = OLSR_TRUE;
318       if (olsr_cnf->tc_redundancy > 1)
319         signal_link_changes(OLSR_TRUE);
320     }
321     entry->status = SYM;
322   } else {
323     if (entry->status == SYM) {
324       changes_neighborhood = OLSR_TRUE;
325       changes_topology = OLSR_TRUE;
326       if (olsr_cnf->tc_redundancy > 1)
327         signal_link_changes(OLSR_TRUE);
328     }
329     /* else N_status is set to NOT_SYM */
330     entry->status = NOT_SYM;
331     /* remove neighbor from routing list */
332   }
333
334   return entry->status;
335 }
336
337 /**
338  * Callback for the nbr2_list timer.
339  */
340 void
341 olsr_expire_nbr2_list(void *context)
342 {
343   struct neighbor_2_list_entry *nbr2_list;
344   struct neighbor_entry *nbr;
345   struct neighbor_2_entry *nbr2;
346
347   nbr2_list = (struct neighbor_2_list_entry *)context;
348   nbr2_list->nbr2_list_timer = NULL;
349
350   nbr = nbr2_list->nbr2_nbr;
351   nbr2 = nbr2_list->neighbor_2;
352
353   nbr2->neighbor_2_pointer--;
354   olsr_delete_neighbor_pointer(nbr2, &nbr->neighbor_main_addr);
355
356   olsr_del_nbr2_list(nbr2_list);
357 }
358
359 /**
360  *Prints the registered neighbors and two hop neighbors
361  *to STDOUT.
362  *
363  *@return nada
364  */
365 void
366 olsr_print_neighbor_table(void)
367 {
368 #ifdef NODEBUG
369   /* The whole function doesn't do anything else. */
370 #ifndef NODEBUG
371   const int iplen = olsr_cnf->ip_version == AF_INET ? 15 : 39;
372 #endif
373   int idx;
374   OLSR_PRINTF(1,
375               "\n--- %02d:%02d:%02d.%02d ------------------------------------------------ NEIGHBORS\n\n"
376               "%*s  LQ     NLQ    SYM   MPR   MPRS  will\n", nowtm->tm_hour,
377               nowtm->tm_min, nowtm->tm_sec, (int)now.tv_usec / 10000, iplen, "IP address");
378
379   for (idx = 0; idx < HASHSIZE; idx++) {
380     struct neighbor_entry *neigh;
381     for (neigh = neighbortable[idx].next; neigh != &neighbortable[idx]; neigh = neigh->next) {
382       struct link_entry *lnk = get_best_link_to_neighbor(&neigh->neighbor_main_addr);
383       if (lnk) {
384         struct ipaddr_str buf;
385         OLSR_PRINTF(1, "%-*s  %5.3f  %5.3f  %s  %s  %s  %d\n", iplen,
386                     olsr_ip_to_string(&buf,
387                                       &neigh->neighbor_main_addr),
388                     lnk->loss_link_quality, lnk->neigh_link_quality,
389                     neigh->status == SYM ? "YES " : "NO  ",
390                     neigh->is_mpr ? "YES " : "NO  ",
391                     olsr_lookup_mprs_set(&neigh->neighbor_main_addr) == NULL ? "NO  " : "YES ", neigh->willingness);
392       }
393     }
394   }
395 #endif
396 }
397
398 /*
399  * Local Variables:
400  * c-basic-offset: 2
401  * indent-tabs-mode: nil
402  * End:
403  */