16ffc206441937ffe3b9ff0ee7433ad5868f7953
[olsrd.git] / src / process_package.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 "process_package.h"
43 #include "ipcalc.h"
44 #include "defs.h"
45 #include "lq_packet.h"
46 #include "hysteresis.h"
47 #include "two_hop_neighbor_table.h"
48 #include "tc_set.h"
49 #include "mpr_selector_set.h"
50 #include "mid_set.h"
51 #include "olsr.h"
52 #include "parser.h"
53 #include "duplicate_set.h"
54 #include "scheduler.h"
55 #include "net_olsr.h"
56 #include "lq_plugin.h"
57 #include "log.h"
58
59 #include <stddef.h>
60
61 static void process_message_neighbors(struct neighbor_entry *, const struct hello_message *);
62
63 static void linking_this_2_entries(struct neighbor_entry *, struct neighbor_2_entry *, olsr_reltime);
64
65 static bool lookup_mpr_status(const struct hello_message *, const struct interface *);
66
67 /**
68  *Processes an list of neighbors from an incoming HELLO message.
69  *@param neighbor the neighbor who sent the message.
70  *@param message the HELLO message
71  *@return nada
72  */
73 static void
74 process_message_neighbors(struct neighbor_entry *neighbor, const struct hello_message *message)
75 {
76   struct hello_neighbor *message_neighbors;
77
78   for (message_neighbors = message->neighbors; message_neighbors != NULL; message_neighbors = message_neighbors->next) {
79     union olsr_ip_addr *neigh_addr;
80     struct neighbor_2_entry *two_hop_neighbor;
81
82     /*
83      *check all interfaces
84      *so that we don't add ourselves to the
85      *2 hop list
86      *IMPORTANT!
87      */
88     if (if_ifwithaddr(&message_neighbors->address) != NULL)
89       continue;
90
91     /* Get the main address */
92     neigh_addr = mid_lookup_main_addr(&message_neighbors->address);
93
94     if (neigh_addr != NULL) {
95       message_neighbors->address = *neigh_addr;
96     }
97
98     if (((message_neighbors->status == SYM_NEIGH) || (message_neighbors->status == MPR_NEIGH))) {
99       struct neighbor_2_list_entry *two_hop_neighbor_yet = olsr_lookup_my_neighbors(neighbor, &message_neighbors->address);
100
101       if (two_hop_neighbor_yet != NULL) {
102         /* Updating the holding time for this neighbor */
103         olsr_set_timer(&two_hop_neighbor_yet->nbr2_list_timer, message->vtime, OLSR_NBR2_LIST_JITTER, OLSR_TIMER_ONESHOT,
104                        &olsr_expire_nbr2_list, two_hop_neighbor_yet, 0);
105         two_hop_neighbor = two_hop_neighbor_yet->neighbor_2;
106
107         /*
108          * For link quality OLSR, reset the path link quality here.
109          * The path link quality will be calculated in the second pass, below.
110          * Keep the saved_path_link_quality for reference.
111          */
112
113         if (olsr_cnf->lq_level > 0) {
114           /*
115            * loop through the one-hop neighbors that see this
116            * 'two_hop_neighbor'
117            */
118
119           struct neighbor_list_entry *walker;
120
121           for (walker = two_hop_neighbor->neighbor_2_nblist.next; walker != &two_hop_neighbor->neighbor_2_nblist;
122                walker = walker->next) {
123             /*
124              * have we found the one-hop neighbor that sent the
125              * HELLO message that we're current processing?
126              */
127
128             if (walker->neighbor == neighbor) {
129               walker->path_linkcost = LINK_COST_BROKEN;
130             }
131           }
132         }
133       } else {
134         two_hop_neighbor = olsr_lookup_two_hop_neighbor_table(&message_neighbors->address);
135         if (two_hop_neighbor == NULL) {
136           changes_neighborhood = true;
137           changes_topology = true;
138
139           two_hop_neighbor = olsr_malloc(sizeof(struct neighbor_2_entry), "Process HELLO");
140
141           two_hop_neighbor->neighbor_2_nblist.next = &two_hop_neighbor->neighbor_2_nblist;
142
143           two_hop_neighbor->neighbor_2_nblist.prev = &two_hop_neighbor->neighbor_2_nblist;
144
145           two_hop_neighbor->neighbor_2_pointer = 0;
146
147           two_hop_neighbor->neighbor_2_addr = message_neighbors->address;
148
149           olsr_insert_two_hop_neighbor_table(two_hop_neighbor);
150
151           linking_this_2_entries(neighbor, two_hop_neighbor, message->vtime);
152         } else {
153           /*
154              linking to this two_hop_neighbor entry
155            */
156           changes_neighborhood = true;
157           changes_topology = true;
158
159           linking_this_2_entries(neighbor, two_hop_neighbor, message->vtime);
160         }
161       }
162     }
163   }
164
165   /* Separate, second pass for link quality OLSR */
166   /* Separate, second and third pass for link quality OLSR */
167
168   if (olsr_cnf->lq_level > 0) {
169     olsr_linkcost first_hop_pathcost;
170     struct link_entry *lnk = get_best_link_to_neighbor(&neighbor->neighbor_main_addr);
171
172     if (!lnk)
173       return;
174
175     /* calculate first hop path quality */
176     first_hop_pathcost = lnk->linkcost;
177     /*
178      *  Second pass for link quality OLSR: calculate the best 2-hop
179      * path costs to all the 2-hop neighbors indicated in the
180      * HELLO message. Since the same 2-hop neighbor may be listed
181      * more than once in the same HELLO message (each at a possibly
182      * different quality) we want to select only the best one, not just
183      * the last one listed in the HELLO message.
184      */
185
186     for (message_neighbors = message->neighbors; message_neighbors != NULL; message_neighbors = message_neighbors->next) {
187       if (if_ifwithaddr(&message_neighbors->address) != NULL)
188         continue;
189
190       if (((message_neighbors->status == SYM_NEIGH) || (message_neighbors->status == MPR_NEIGH))) {
191         struct neighbor_list_entry *walker;
192         struct neighbor_2_entry *two_hop_neighbor;
193         struct neighbor_2_list_entry *two_hop_neighbor_yet = olsr_lookup_my_neighbors(neighbor,
194                                                                                       &message_neighbors->address);
195
196         if (!two_hop_neighbor_yet)
197           continue;
198
199         two_hop_neighbor = two_hop_neighbor_yet->neighbor_2;
200
201         /*
202          *  loop through the one-hop neighbors that see this
203          * 'two_hop_neighbor'
204          */
205
206         for (walker = two_hop_neighbor->neighbor_2_nblist.next; walker != &two_hop_neighbor->neighbor_2_nblist;
207              walker = walker->next) {
208           /*
209            * have we found the one-hop neighbor that sent the
210            * HELLO message that we're current processing?
211            */
212
213           if (walker->neighbor == neighbor) {
214             olsr_linkcost new_second_hop_linkcost, new_path_linkcost;
215
216             // the link cost between the 1-hop neighbour and the
217             // 2-hop neighbour
218
219             new_second_hop_linkcost = message_neighbors->cost;
220
221             // the total cost for the route
222             // "us --- 1-hop --- 2-hop"
223
224             new_path_linkcost = first_hop_pathcost + new_second_hop_linkcost;
225
226             // Only copy the link quality if it is better than what we have
227             // for this 2-hop neighbor
228             if (new_path_linkcost < walker->path_linkcost) {
229               walker->second_hop_linkcost = new_second_hop_linkcost;
230               walker->path_linkcost = new_path_linkcost;
231
232               walker->saved_path_linkcost = new_path_linkcost;
233
234               if (olsr_cnf->lq_dlimit > 0) {
235                 changes_neighborhood = true;
236                 changes_topology = true;
237               }
238
239               else
240                 OLSR_PRINTF(3, "Skipping Dijkstra (3)\n");
241             }
242           }
243         }
244       }
245     }
246   }
247 }
248
249 /**
250  *Links a one-hop neighbor with a 2-hop neighbor.
251  *
252  *@param neighbor the 1-hop neighbor
253  *@param two_hop_neighbor the 2-hop neighbor
254  *@return nada
255  */
256 static void
257 linking_this_2_entries(struct neighbor_entry *neighbor, struct neighbor_2_entry *two_hop_neighbor, olsr_reltime vtime)
258 {
259   struct neighbor_list_entry *list_of_1_neighbors = olsr_malloc(sizeof(struct neighbor_list_entry), "Link entries 1");
260   struct neighbor_2_list_entry *list_of_2_neighbors = olsr_malloc(sizeof(struct neighbor_2_list_entry), "Link entries 2");
261
262   list_of_1_neighbors->neighbor = neighbor;
263
264   list_of_1_neighbors->path_linkcost = LINK_COST_BROKEN;
265   list_of_1_neighbors->saved_path_linkcost = LINK_COST_BROKEN;
266   list_of_1_neighbors->second_hop_linkcost = LINK_COST_BROKEN;
267
268   /* Queue */
269   two_hop_neighbor->neighbor_2_nblist.next->prev = list_of_1_neighbors;
270   list_of_1_neighbors->next = two_hop_neighbor->neighbor_2_nblist.next;
271
272   two_hop_neighbor->neighbor_2_nblist.next = list_of_1_neighbors;
273   list_of_1_neighbors->prev = &two_hop_neighbor->neighbor_2_nblist;
274   list_of_2_neighbors->neighbor_2 = two_hop_neighbor;
275   list_of_2_neighbors->nbr2_nbr = neighbor;     /* XXX refcount */
276
277   olsr_change_timer(list_of_2_neighbors->nbr2_list_timer, vtime, OLSR_NBR2_LIST_JITTER, OLSR_TIMER_ONESHOT);
278
279   /* Queue */
280   neighbor->neighbor_2_list.next->prev = list_of_2_neighbors;
281   list_of_2_neighbors->next = neighbor->neighbor_2_list.next;
282   neighbor->neighbor_2_list.next = list_of_2_neighbors;
283   list_of_2_neighbors->prev = &neighbor->neighbor_2_list;
284
285   /*increment the pointer counter */
286   two_hop_neighbor->neighbor_2_pointer++;
287 }
288
289 /**
290  * Check if a hello message states this node as a MPR.
291  *
292  * @param message the message to check
293  * @param n_link the buffer to put the link status in
294  *
295  *@return 1 if we are selected as MPR 0 if not
296  */
297 static bool
298 lookup_mpr_status(const struct hello_message *message, const struct interface *in_if)
299 {
300   struct hello_neighbor *neighbors;
301
302   for (neighbors = message->neighbors; neighbors; neighbors = neighbors->next) {
303     if ( neighbors->link != UNSPEC_LINK
304         && (olsr_cnf->ip_version == AF_INET
305             ? ip4equal(&neighbors->address.v4, &in_if->ip_addr.v4)
306             : ip6equal(&neighbors->address.v6, &in_if->int6_addr.sin6_addr))) {
307
308       if (neighbors->link == SYM_LINK && neighbors->status == MPR_NEIGH) {
309         return true;
310       }
311       break;
312     }
313   }
314   /* Not found */
315   return false;
316 }
317
318 static int
319 deserialize_hello(struct hello_message *hello, const void *ser)
320 {
321   const unsigned char *curr, *limit;
322   uint8_t type;
323   uint16_t size;
324   struct ipaddr_str buf;
325
326   memset (hello, 0, sizeof(*hello));
327
328   curr = ser;
329   pkt_get_u8(&curr, &type);
330   if (type != HELLO_MESSAGE && type != LQ_HELLO_MESSAGE) {
331     /* No need to do anything more */
332     return 1;
333   }
334   pkt_get_reltime(&curr, &hello->vtime);
335   pkt_get_u16(&curr, &size);
336   pkt_get_ipaddress(&curr, &hello->source_addr);
337
338   pkt_get_u8(&curr, &hello->ttl);
339   pkt_get_u8(&curr, &hello->hop_count);
340   pkt_get_u16(&curr, &hello->packet_seq_number);
341   pkt_ignore_u16(&curr);
342
343   pkt_get_reltime(&curr, &hello->htime);
344   pkt_get_u8(&curr, &hello->willingness);
345
346   hello->neighbors = NULL;
347
348   limit = ((const unsigned char *)ser) + size;
349   while (curr < limit) {
350     const unsigned char *limit2 = curr;
351     uint8_t link_code;
352     uint16_t size2;
353
354     pkt_get_u8(&curr, &link_code);
355     pkt_ignore_u8(&curr);
356     pkt_get_u16(&curr, &size2);
357
358     limit2 += size2;
359     while (curr < limit2) {
360       struct hello_neighbor *neigh = olsr_malloc_hello_neighbor("HELLO deserialization");
361       pkt_get_ipaddress(&curr, &neigh->address);
362       if (type == LQ_HELLO_MESSAGE) {
363         olsr_deserialize_hello_lq_pair(&curr, neigh);
364       }
365       neigh->link = EXTRACT_LINK(link_code);
366       neigh->status = EXTRACT_STATUS(link_code);
367
368       neigh->next = hello->neighbors;
369       hello->neighbors = neigh;
370     }
371   }
372   return 0;
373 }
374
375 bool
376 olsr_input_hello(union olsr_message * ser, struct interface * inif, union olsr_ip_addr * from)
377 {
378   struct hello_message hello;
379
380   if (ser == NULL) {
381     return false;
382   }
383   if (deserialize_hello(&hello, ser) != 0) {
384     return false;
385   }
386   olsr_hello_tap(&hello, inif, from);
387
388   /* Do not forward hello messages */
389   return false;
390 }
391
392 /**
393  *Initializing the parser functions we are using
394  */
395 void
396 olsr_init_package_process(void)
397 {
398   if (olsr_cnf->lq_level == 0) {
399     olsr_parser_add_function(&olsr_input_hello, HELLO_MESSAGE);
400     olsr_parser_add_function(&olsr_input_tc, TC_MESSAGE);
401   } else {
402     olsr_parser_add_function(&olsr_input_hello, LQ_HELLO_MESSAGE);
403     olsr_parser_add_function(&olsr_input_tc, LQ_TC_MESSAGE);
404   }
405
406   olsr_parser_add_function(&olsr_input_mid, MID_MESSAGE);
407   olsr_parser_add_function(&olsr_input_hna, HNA_MESSAGE);
408 }
409
410 void
411 olsr_hello_tap(struct hello_message *message, struct interface *in_if, const union olsr_ip_addr *from_addr)
412 {
413   struct neighbor_entry *neighbor;
414
415   /*
416    * Update link status
417    */
418   struct link_entry *lnk = update_link_entry(&in_if->ip_addr, from_addr, message, in_if);
419
420   if (olsr_cnf->lq_level > 0) {
421     struct hello_neighbor *walker;
422     /* just in case our neighbor has changed its HELLO interval */
423     olsr_update_packet_loss_hello_int(lnk, message->htime);
424
425     /* find the input interface in the list of neighbor interfaces */
426     for (walker = message->neighbors; walker != NULL; walker = walker->next) {
427       if (walker->link != UNSPEC_LINK
428           && ipequal(&walker->address, &in_if->ip_addr)) {
429         break;
430       }
431     }
432
433     /*
434      * memorize our neighbour's idea of the link quality, so that we
435      * know the link quality in both directions
436      *
437      * walker is NULL if there the current interface was not included in
438      * the message (or was included as an UNSPEC_LINK)
439      */
440     olsr_memorize_foreign_hello_lq(lnk, walker);
441
442     /* update packet loss for link quality calculation */
443     olsr_received_hello_handler(lnk);
444   }
445
446   neighbor = lnk->neighbor;
447
448   /*
449    * Hysteresis
450    */
451   if (olsr_cnf->use_hysteresis) {
452     /* Update HELLO timeout */
453     /* printf("MESSAGE HTIME: %f\n", message->htime); */
454     olsr_update_hysteresis_hello(lnk, message->htime);
455   }
456
457   /* Check if we are chosen as MPR */
458   if (lookup_mpr_status(message, in_if))
459     /* source_addr is always the main addr of a node! */
460     olsr_update_mprs_set(&message->source_addr, message->vtime);
461
462   /* Check willingness */
463   if (neighbor->willingness != message->willingness) {
464     struct ipaddr_str buf;
465     OLSR_PRINTF(1, "Willingness for %s changed from %d to %d - UPDATING\n", olsr_ip_to_string(&buf, &neighbor->neighbor_main_addr),
466                 neighbor->willingness, message->willingness);
467     /*
468      *If willingness changed - recalculate
469      */
470     neighbor->willingness = message->willingness;
471     changes_neighborhood = true;
472     changes_topology = true;
473   }
474
475   /* Don't register neighbors of neighbors that announces WILL_NEVER */
476   if (neighbor->willingness != WILL_NEVER)
477     process_message_neighbors(neighbor, message);
478
479   /* Process changes immedeatly in case of MPR updates */
480   olsr_process_changes();
481
482   olsr_free_hello_packet(message);
483
484   return;
485 }
486
487 /*
488  * Local Variables:
489  * c-basic-offset: 2
490  * indent-tabs-mode: nil
491  * End:
492  */