rename neighbor and neighbor2_list entry, preparation for neighbor refactoring
[olsrd.git] / src / neighbor_table.c
1
2 /*
3  * The olsr.org Optimized Link-State Routing daemon(olsrd)
4  * Copyright (c) 2004-2009, the olsr.org team - see HISTORY file
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 #include "olsr_logging.h"
54
55 #include <stdlib.h>
56
57
58 struct nbr_entry neighbortable[HASHSIZE];
59
60 /* Some cookies for stats keeping */
61 struct olsr_cookie_info *nbr2_list_timer_cookie = NULL;
62
63 void
64 olsr_init_neighbor_table(void)
65 {
66   int i;
67
68   OLSR_INFO(LOG_NEIGHTABLE, "Initialize neighbor table...\n");
69
70   for (i = 0; i < HASHSIZE; i++) {
71     neighbortable[i].next = &neighbortable[i];
72     neighbortable[i].prev = &neighbortable[i];
73   }
74
75   nbr2_list_timer_cookie = olsr_alloc_cookie("2-Hop Neighbor List", OLSR_COOKIE_TYPE_TIMER);
76
77 }
78
79 /**
80  * Unlink, delete and free a nbr2_list entry.
81  */
82 static void
83 olsr_del_nbr2_list(struct nbr2_list_entry *nbr2_list)
84 {
85   struct neighbor_2_entry *nbr2;
86
87   nbr2 = nbr2_list->neighbor_2;
88
89   if (nbr2->neighbor_2_pointer < 1) {
90     DEQUEUE_ELEM(nbr2);
91     free(nbr2);
92   }
93
94   /*
95    * Kill running timers.
96    */
97   olsr_stop_timer(nbr2_list->nbr2_list_timer);
98   nbr2_list->nbr2_list_timer = NULL;
99
100   /* Dequeue */
101   DEQUEUE_ELEM(nbr2_list);
102
103   free(nbr2_list);
104
105   /* Set flags to recalculate the MPR set and the routing table */
106   changes_neighborhood = true;
107   changes_topology = true;
108 }
109
110 /**
111  * Delete a two hop neighbor from a neighbors two hop neighbor list.
112  *
113  * @param neighbor the neighbor to delete the two hop neighbor from.
114  * @param address the IP address of the two hop neighbor to delete.
115  *
116  * @return positive if entry deleted
117  */
118 int
119 olsr_delete_neighbor_2_pointer(struct nbr_entry *neighbor, struct neighbor_2_entry *neigh2)
120 {
121   struct nbr2_list_entry *nbr2_list;
122
123   nbr2_list = neighbor->neighbor_2_list.next;
124
125   while (nbr2_list != &neighbor->neighbor_2_list) {
126     if (nbr2_list->neighbor_2 == neigh2) {
127       olsr_del_nbr2_list(nbr2_list);
128       return 1;
129     }
130     nbr2_list = nbr2_list->next;
131   }
132   return 0;
133 }
134
135
136 /**
137  *Check if a two hop neighbor is reachable via a given
138  *neighbor.
139  *
140  *@param neighbor neighbor-entry to check via
141  *@param neighbor_main_address the addres of the two hop neighbor
142  *to find.
143  *
144  *@return a pointer to the nbr2_list_entry struct
145  *representing the two hop neighbor if found. NULL if not found.
146  */
147 struct nbr2_list_entry *
148 olsr_lookup_my_neighbors(const struct nbr_entry *neighbor, const union olsr_ip_addr *neighbor_main_address)
149 {
150   struct nbr2_list_entry *entry;
151
152   for (entry = neighbor->neighbor_2_list.next; entry != &neighbor->neighbor_2_list; entry = entry->next) {
153
154     if (olsr_ipcmp(&entry->neighbor_2->neighbor_2_addr, neighbor_main_address) == 0)
155       return entry;
156
157   }
158   return NULL;
159 }
160
161
162
163 /**
164  *Delete a neighbr table entry.
165  *
166  *Remember: Deleting a neighbor entry results
167  *the deletion of its 2 hop neighbors list!!!
168  *@param neighbor the neighbor entry to delete
169  *
170  *@return nada
171  */
172
173 int
174 olsr_delete_neighbor_table(const union olsr_ip_addr *neighbor_addr)
175 {
176   struct nbr2_list_entry *two_hop_list, *two_hop_to_delete;
177   uint32_t hash;
178   struct nbr_entry *entry;
179
180 #if !defined REMOVE_LOG_DEBUG
181   struct ipaddr_str buf;
182 #endif
183   OLSR_DEBUG(LOG_NEIGHTABLE, "delete neighbor: %s\n", olsr_ip_to_string(&buf, neighbor_addr));
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 (olsr_ipcmp(&entry->neighbor_main_addr, neighbor_addr) == 0)
194       break;
195
196     entry = entry->next;
197   }
198
199   if (entry == &neighbortable[hash])
200     return 0;
201
202
203   two_hop_list = entry->neighbor_2_list.next;
204
205   while (two_hop_list != &entry->neighbor_2_list) {
206     two_hop_to_delete = two_hop_list;
207     two_hop_list = two_hop_list->next;
208
209     two_hop_to_delete->neighbor_2->neighbor_2_pointer--;
210     olsr_delete_neighbor_pointer(two_hop_to_delete->neighbor_2, entry);
211
212     olsr_del_nbr2_list(two_hop_to_delete);
213   }
214
215
216   /* Dequeue */
217   DEQUEUE_ELEM(entry);
218
219   free(entry);
220
221   changes_neighborhood = true;
222   return 1;
223
224 }
225
226
227
228 /**
229  *Insert a neighbor entry in the neighbor table
230  *
231  *@param main_addr the main address of the new node
232  *
233  *@return 0 if neighbor already exists 1 if inserted
234  */
235 struct nbr_entry *
236 olsr_insert_neighbor_table(const union olsr_ip_addr *main_addr)
237 {
238   uint32_t hash;
239   struct nbr_entry *new_neigh;
240 #if !defined REMOVE_LOG_DEBUG
241   struct ipaddr_str buf;
242 #endif
243
244   hash = olsr_ip_hashing(main_addr);
245
246   /* Check if entry exists */
247
248   for (new_neigh = neighbortable[hash].next; new_neigh != &neighbortable[hash]; new_neigh = new_neigh->next) {
249     if (olsr_ipcmp(&new_neigh->neighbor_main_addr, main_addr) == 0)
250       return new_neigh;
251   }
252
253   OLSR_DEBUG(LOG_NEIGHTABLE, "delete neighbor: %s\n", olsr_ip_to_string(&buf, main_addr));
254
255   new_neigh = olsr_malloc(sizeof(struct nbr_entry), "New neighbor entry");
256
257   /* Set address, willingness and status */
258   new_neigh->neighbor_main_addr = *main_addr;
259   new_neigh->willingness = WILL_NEVER;
260   new_neigh->status = NOT_SYM;
261
262   new_neigh->neighbor_2_list.next = &new_neigh->neighbor_2_list;
263   new_neigh->neighbor_2_list.prev = &new_neigh->neighbor_2_list;
264
265   new_neigh->linkcount = 0;
266   new_neigh->is_mpr = false;
267   new_neigh->was_mpr = false;
268
269   /* Queue */
270   QUEUE_ELEM(neighbortable[hash], new_neigh);
271
272   return new_neigh;
273 }
274
275
276
277 /**
278  *Lookup a neighbor entry in the neighbortable based on an address.
279  *
280  *@param dst the IP address of the neighbor to look up
281  *
282  *@return a pointer to the neighbor struct registered on the given
283  *address. NULL if not found.
284  */
285 struct nbr_entry *
286 olsr_lookup_neighbor_table(const union olsr_ip_addr *dst)
287 {
288   /*
289    *Find main address of node
290    */
291   union olsr_ip_addr *tmp_ip = olsr_lookup_main_addr_by_alias(dst);
292   if (tmp_ip != NULL)
293     dst = tmp_ip;
294   return olsr_lookup_neighbor_table_alias(dst);
295 }
296
297
298 /**
299  *Lookup a neighbor entry in the neighbortable based on an address.
300  *
301  *@param dst the IP address of the neighbor to look up
302  *
303  *@return a pointer to the neighbor struct registered on the given
304  *address. NULL if not found.
305  */
306 struct nbr_entry *
307 olsr_lookup_neighbor_table_alias(const union olsr_ip_addr *dst)
308 {
309   struct nbr_entry *entry;
310   uint32_t hash = olsr_ip_hashing(dst);
311
312   for (entry = neighbortable[hash].next; entry != &neighbortable[hash]; entry = entry->next) {
313     if (olsr_ipcmp(&entry->neighbor_main_addr, dst) == 0)
314       return entry;
315   }
316
317   return NULL;
318
319 }
320
321
322
323 int
324 update_neighbor_status(struct nbr_entry *entry, int lnk)
325 {
326   /*
327    * Update neighbor entry
328    */
329
330   if (lnk == SYM_LINK) {
331     /* N_status is set to SYM */
332     if (entry->status == NOT_SYM) {
333       struct neighbor_2_entry *two_hop_neighbor;
334
335       /* Delete posible 2 hop entry on this neighbor */
336       if ((two_hop_neighbor = olsr_lookup_two_hop_neighbor_table(&entry->neighbor_main_addr)) != NULL) {
337         olsr_delete_two_hop_neighbor_table(two_hop_neighbor);
338       }
339
340       changes_neighborhood = true;
341       changes_topology = true;
342       if (olsr_cnf->tc_redundancy > 1)
343         signal_link_changes(true);
344     }
345     entry->status = SYM;
346   } else {
347     if (entry->status == SYM) {
348       changes_neighborhood = true;
349       changes_topology = true;
350       if (olsr_cnf->tc_redundancy > 1)
351         signal_link_changes(true);
352     }
353     /* else N_status is set to NOT_SYM */
354     entry->status = NOT_SYM;
355     /* remove neighbor from routing list */
356   }
357
358   return entry->status;
359 }
360
361
362 /**
363  * Callback for the nbr2_list timer.
364  */
365 void
366 olsr_expire_nbr2_list(void *context)
367 {
368   struct nbr2_list_entry *nbr2_list;
369   struct nbr_entry *nbr;
370   struct neighbor_2_entry *nbr2;
371
372   nbr2_list = (struct nbr2_list_entry *)context;
373   nbr2_list->nbr2_list_timer = NULL;
374
375   nbr = nbr2_list->nbr2_nbr;
376   nbr2 = nbr2_list->neighbor_2;
377
378   nbr2->neighbor_2_pointer--;
379   olsr_delete_neighbor_pointer(nbr2, nbr);
380
381   olsr_del_nbr2_list(nbr2_list);
382 }
383
384
385 /**
386  *Prints the registered neighbors and two hop neighbors
387  *to STDOUT.
388  *
389  *@return nada
390  */
391 void
392 olsr_print_neighbor_table(void)
393 {
394 #if !defined REMOVE_LOG_INFO
395   /* The whole function doesn't do anything else. */
396   const int ipwidth = olsr_cnf->ip_version == AF_INET ? 15 : 39;
397   int idx;
398   OLSR_INFO(LOG_NEIGHTABLE, "\n--- %s ------------------------------------------------ NEIGHBORS\n\n"
399             "%*s  LQ    SYM   MPR   MPRS  will\n", olsr_wallclock_string(), ipwidth, "IP address");
400
401   for (idx = 0; idx < HASHSIZE; idx++) {
402     struct nbr_entry *neigh;
403     for (neigh = neighbortable[idx].next; neigh != &neighbortable[idx]; neigh = neigh->next) {
404       struct link_entry *lnk = get_best_link_to_neighbor(&neigh->neighbor_main_addr);
405       if (lnk) {
406         struct ipaddr_str buf;
407         OLSR_INFO_NH(LOG_NEIGHTABLE, "%-*s  %s  %s  %s  %d\n",
408                      ipwidth, olsr_ip_to_string(&buf, &neigh->neighbor_main_addr),
409                      neigh->status == SYM ? "YES " : "NO  ",
410                      neigh->is_mpr ? "YES " : "NO  ",
411                      olsr_lookup_mprs_set(&neigh->neighbor_main_addr) == NULL ? "NO  " : "YES ", neigh->willingness);
412       }
413     }
414   }
415 #endif
416 }
417
418 /*
419  * Local Variables:
420  * c-basic-offset: 2
421  * indent-tabs-mode: nil
422  * End:
423  */