info: java: update workspace
[olsrd.git] / src / process_package.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 "process_package.h"
47 #include "ipcalc.h"
48 #include "defs.h"
49 #include "lq_packet.h"
50 #include "hysteresis.h"
51 #include "two_hop_neighbor_table.h"
52 #include "tc_set.h"
53 #include "mpr_selector_set.h"
54 #include "mid_set.h"
55 #include "olsr.h"
56 #include "parser.h"
57 #include "duplicate_set.h"
58 #include "scheduler.h"
59 #include "net_olsr.h"
60 #include "lq_plugin.h"
61 #include "log.h"
62
63 #include <assert.h>
64 #include <stddef.h>
65
66 static void process_message_neighbors(struct neighbor_entry *, const struct hello_message *);
67
68 static void linking_this_2_entries(struct neighbor_entry *, struct neighbor_2_entry *, olsr_reltime);
69
70 static bool lookup_mpr_status(const struct hello_message *, const struct interface_olsr *);
71
72 /**
73  *Processes an list of neighbors from an incoming HELLO message.
74  *@param neighbor the neighbor who sent the message.
75  *@param message the HELLO message
76  *@return nada
77  */
78 static void
79 process_message_neighbors(struct neighbor_entry *neighbor, const struct hello_message *message)
80 {
81   struct hello_neighbor *message_neighbors;
82
83   for (message_neighbors = message->neighbors; message_neighbors != NULL; message_neighbors = message_neighbors->next) {
84     union olsr_ip_addr *neigh_addr;
85     struct neighbor_2_entry *two_hop_neighbor;
86
87     /*
88      *check all interfaces
89      *so that we don't add ourselves to the
90      *2 hop list
91      *IMPORTANT!
92      */
93     if (if_ifwithaddr(&message_neighbors->address) != NULL)
94       continue;
95
96     /* Get the main address */
97     neigh_addr = mid_lookup_main_addr(&message_neighbors->address);
98
99     if (neigh_addr != NULL) {
100       message_neighbors->address = *neigh_addr;
101     }
102
103     if (((message_neighbors->status == SYM_NEIGH) || (message_neighbors->status == MPR_NEIGH))) {
104       struct neighbor_2_list_entry *two_hop_neighbor_yet = olsr_lookup_my_neighbors(neighbor, &message_neighbors->address);
105
106       if (two_hop_neighbor_yet != NULL) {
107         /* Updating the holding time for this neighbor */
108         olsr_set_timer(&two_hop_neighbor_yet->nbr2_list_timer, message->vtime, OLSR_NBR2_LIST_JITTER, OLSR_TIMER_ONESHOT,
109                        &olsr_expire_nbr2_list, two_hop_neighbor_yet, 0);
110         two_hop_neighbor = two_hop_neighbor_yet->neighbor_2;
111
112         /*
113          * For link quality OLSR, reset the path link quality here.
114          * The path link quality will be calculated in the second pass, below.
115          * Keep the saved_path_link_quality for reference.
116          */
117
118         if (olsr_cnf->lq_level > 0) {
119           /*
120            * loop through the one-hop neighbors that see this
121            * 'two_hop_neighbor'
122            */
123
124           struct neighbor_list_entry *walker;
125
126           for (walker = two_hop_neighbor->neighbor_2_nblist.next; walker != &two_hop_neighbor->neighbor_2_nblist;
127                walker = walker->next) {
128             /*
129              * have we found the one-hop neighbor that sent the
130              * HELLO message that we're current processing?
131              */
132
133             if (walker->neighbor == neighbor) {
134               walker->path_linkcost = LINK_COST_BROKEN;
135             }
136           }
137         }
138       } else {
139         two_hop_neighbor = olsr_lookup_two_hop_neighbor_table(&message_neighbors->address);
140         if (two_hop_neighbor == NULL) {
141           changes_neighborhood = true;
142           changes_topology = true;
143
144           two_hop_neighbor = olsr_malloc(sizeof(struct neighbor_2_entry), "Process HELLO");
145
146           two_hop_neighbor->neighbor_2_nblist.next = &two_hop_neighbor->neighbor_2_nblist;
147
148           two_hop_neighbor->neighbor_2_nblist.prev = &two_hop_neighbor->neighbor_2_nblist;
149
150           two_hop_neighbor->neighbor_2_pointer = 0;
151
152           two_hop_neighbor->neighbor_2_addr = message_neighbors->address;
153
154           olsr_insert_two_hop_neighbor_table(two_hop_neighbor);
155
156           linking_this_2_entries(neighbor, two_hop_neighbor, message->vtime);
157         } else {
158           /*
159              linking to this two_hop_neighbor entry
160            */
161           changes_neighborhood = true;
162           changes_topology = true;
163
164           linking_this_2_entries(neighbor, two_hop_neighbor, message->vtime);
165         }
166       }
167     }
168   }
169
170   /* Separate, second pass for link quality OLSR */
171   /* Separate, second and third pass for link quality OLSR */
172
173   if (olsr_cnf->lq_level > 0) {
174     olsr_linkcost first_hop_pathcost;
175     struct link_entry *lnk = get_best_link_to_neighbor(&neighbor->neighbor_main_addr);
176
177     if (!lnk)
178       return;
179
180     /* calculate first hop path quality */
181     first_hop_pathcost = lnk->linkcost;
182     /*
183      *  Second pass for link quality OLSR: calculate the best 2-hop
184      * path costs to all the 2-hop neighbors indicated in the
185      * HELLO message. Since the same 2-hop neighbor may be listed
186      * more than once in the same HELLO message (each at a possibly
187      * different quality) we want to select only the best one, not just
188      * the last one listed in the HELLO message.
189      */
190
191     for (message_neighbors = message->neighbors; message_neighbors != NULL; message_neighbors = message_neighbors->next) {
192       if (if_ifwithaddr(&message_neighbors->address) != NULL)
193         continue;
194
195       if (((message_neighbors->status == SYM_NEIGH) || (message_neighbors->status == MPR_NEIGH))) {
196         struct neighbor_list_entry *walker;
197         struct neighbor_2_entry *two_hop_neighbor;
198         struct neighbor_2_list_entry *two_hop_neighbor_yet = olsr_lookup_my_neighbors(neighbor,
199                                                                                       &message_neighbors->address);
200
201         if (!two_hop_neighbor_yet)
202           continue;
203
204         two_hop_neighbor = two_hop_neighbor_yet->neighbor_2;
205
206         /*
207          *  loop through the one-hop neighbors that see this
208          * 'two_hop_neighbor'
209          */
210
211         for (walker = two_hop_neighbor->neighbor_2_nblist.next; walker != &two_hop_neighbor->neighbor_2_nblist;
212              walker = walker->next) {
213           /*
214            * have we found the one-hop neighbor that sent the
215            * HELLO message that we're current processing?
216            */
217
218           if (walker->neighbor == neighbor) {
219             olsr_linkcost new_second_hop_linkcost, new_path_linkcost;
220
221             // the link cost between the 1-hop neighbour and the
222             // 2-hop neighbour
223
224             new_second_hop_linkcost = message_neighbors->cost;
225
226             // the total cost for the route
227             // "us --- 1-hop --- 2-hop"
228
229             new_path_linkcost = first_hop_pathcost + new_second_hop_linkcost;
230
231             // Only copy the link quality if it is better than what we have
232             // for this 2-hop neighbor
233             if (new_path_linkcost < walker->path_linkcost) {
234               walker->second_hop_linkcost = new_second_hop_linkcost;
235               walker->path_linkcost = new_path_linkcost;
236
237               walker->saved_path_linkcost = new_path_linkcost;
238
239               changes_neighborhood = true;
240               changes_topology = true;
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  *@param vtime the validity time
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 in_if the incoming interface
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_olsr *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   static const int LINK_ORDER[] = HELLO_LINK_ORDER_ARRAY;
322   const unsigned char *curr, *limit;
323   uint8_t type;
324   uint16_t size;
325   struct ipaddr_str buf;
326   const unsigned char *curr_saved;
327   unsigned int idx;
328   struct hello_neighbor *neigh_unspec_first_prev = NULL;
329   struct hello_neighbor *neigh_unspec_first = NULL;
330
331   assert(LINK_ORDER[0] == UNSPEC_LINK);
332
333   memset (hello, 0, sizeof(*hello));
334
335   curr = ser;
336   pkt_get_u8(&curr, &type);
337   if (type != HELLO_MESSAGE && type != LQ_HELLO_MESSAGE) {
338     /* No need to do anything more */
339     return 1;
340   }
341   pkt_get_reltime(&curr, &hello->vtime);
342   pkt_get_u16(&curr, &size);
343   pkt_get_ipaddress(&curr, &hello->source_addr);
344
345   pkt_get_u8(&curr, &hello->ttl);
346   pkt_get_u8(&curr, &hello->hop_count);
347   pkt_get_u16(&curr, &hello->packet_seq_number);
348   pkt_ignore_u16(&curr);
349
350   pkt_get_reltime(&curr, &hello->htime);
351   pkt_get_u8(&curr, &hello->willingness);
352
353   hello->neighbors = NULL;
354
355   limit = ((const unsigned char *)ser) + size;
356
357   curr_saved = curr;
358
359   for (idx = 0; idx < (sizeof(LINK_ORDER) / sizeof(LINK_ORDER[0])); idx++) {
360     curr = curr_saved;
361
362     while (curr < limit) {
363       const unsigned char *limit2 = curr;
364       uint8_t link_code;
365       uint16_t size2;
366
367       pkt_get_u8(&curr, &link_code);
368       pkt_ignore_u8(&curr);
369       pkt_get_u16(&curr, &size2);
370
371       limit2 += size2;
372
373       if (EXTRACT_LINK(link_code) != LINK_ORDER[idx]) {
374         curr = limit2;
375         continue;
376       }
377
378       while (curr < limit2) {
379         struct hello_neighbor *neigh = olsr_malloc_hello_neighbor("HELLO deserialization");
380         pkt_get_ipaddress(&curr, &neigh->address);
381         if (type == LQ_HELLO_MESSAGE) {
382           olsr_deserialize_hello_lq_pair(&curr, neigh);
383         }
384         neigh->link = EXTRACT_LINK(link_code);
385         neigh->status = EXTRACT_STATUS(link_code);
386
387         neigh->next = hello->neighbors;
388         hello->neighbors = neigh;
389
390         if (neigh->link == UNSPEC_LINK) {
391           neigh_unspec_first = neigh;
392         } else if (!neigh_unspec_first_prev) {
393           neigh_unspec_first_prev = neigh;
394         }
395       }
396     }
397   }
398
399   if (neigh_unspec_first_prev && neigh_unspec_first) {
400     struct hello_neighbor *neigh;
401     for (neigh = hello->neighbors; neigh && (neigh != neigh_unspec_first); neigh = neigh->next) {
402       struct hello_neighbor *neigh_cull;
403       struct hello_neighbor *neigh_cull_prev;
404       struct hello_neighbor *neigh_cull_next;
405
406       for (neigh_cull_prev = neigh_unspec_first_prev, neigh_cull = neigh_unspec_first;
407            neigh_cull;
408            neigh_cull = neigh_cull_next) {
409         neigh_cull_next = neigh_cull->next;
410
411         if (!ipequal(&neigh_cull->address, &neigh->address)) {
412           neigh_cull_prev = neigh_cull;
413           continue;
414         }
415
416         if (neigh_cull == neigh_unspec_first) {
417           neigh_unspec_first = neigh_cull_next;
418         }
419
420         neigh_cull_prev->next = neigh_cull_next;
421         free(neigh_cull);
422       }
423     }
424   }
425
426   return 0;
427 }
428
429 bool
430 olsr_input_hello(union olsr_message * ser, struct interface_olsr * inif, union olsr_ip_addr * from)
431 {
432   struct hello_message hello;
433
434   if (ser == NULL) {
435     return false;
436   }
437   if (deserialize_hello(&hello, ser) != 0) {
438     return false;
439   }
440   olsr_hello_tap(&hello, inif, from);
441
442   /* Do not forward hello messages */
443   return false;
444 }
445
446 /**
447  *Initializing the parser functions we are using
448  */
449 void
450 olsr_init_package_process(void)
451 {
452   if (olsr_cnf->lq_level == 0) {
453     olsr_parser_add_function(&olsr_input_hello, HELLO_MESSAGE);
454     olsr_parser_add_function(&olsr_input_tc, TC_MESSAGE);
455   } else {
456     olsr_parser_add_function(&olsr_input_hello, LQ_HELLO_MESSAGE);
457     olsr_parser_add_function(&olsr_input_tc, LQ_TC_MESSAGE);
458   }
459
460   olsr_parser_add_function(&olsr_input_mid, MID_MESSAGE);
461   olsr_parser_add_function(&olsr_input_hna, HNA_MESSAGE);
462 }
463
464 void
465 olsr_hello_tap(struct hello_message *message, struct interface_olsr *in_if, const union olsr_ip_addr *from_addr)
466 {
467   struct neighbor_entry *neighbor;
468
469   /*
470    * Update link status
471    */
472   struct link_entry *lnk = update_link_entry(&in_if->ip_addr, from_addr, message, in_if);
473
474   /*check alias message->source_addr*/
475   if (!ipequal(&message->source_addr,from_addr)){
476     /*new alias of new neighbour are thrown in the mid table to speed up routing*/
477     if (olsr_validate_address(from_addr)) {
478       union olsr_ip_addr * main_addr = mid_lookup_main_addr(from_addr);
479       if ((main_addr==NULL)||(ipequal(&message->source_addr, main_addr))){
480         /*struct ipaddr_str srcbuf, origbuf;
481         olsr_syslog(OLSR_LOG_INFO, "got hello from unknown alias ip of direct neighbour: ip: %s main-ip: %s",
482                     olsr_ip_to_string(&origbuf,&message->source_addr),
483                     olsr_ip_to_string(&srcbuf,from_addr));*/
484         insert_mid_alias(&message->source_addr, from_addr, message->vtime);
485       }
486       else
487       {
488         struct ipaddr_str srcbuf, origbuf;
489         olsr_syslog(OLSR_LOG_INFO, "got hello with invalid from and originator address pair (%s, %s) Duplicate Ips?\n",
490                     olsr_ip_to_string(&origbuf,&message->source_addr),
491                     olsr_ip_to_string(&srcbuf,from_addr));
492       }
493     }
494   }
495
496   if (olsr_cnf->lq_level > 0) {
497     struct hello_neighbor *walker;
498     /* just in case our neighbor has changed its HELLO interval */
499     olsr_update_packet_loss_hello_int(lnk, message->htime);
500
501     /* find the input interface in the list of neighbor interfaces */
502     for (walker = message->neighbors; walker != NULL; walker = walker->next) {
503       if (ipequal(&walker->address, &in_if->ip_addr)) {
504         /*
505          * memorize our neighbour's idea of the link quality, so that we
506          * know the link quality in both directions
507          */
508         olsr_memorize_foreign_hello_lq(lnk, walker->link != UNSPEC_LINK ? walker : NULL);
509         break;
510       }
511     }
512     /* update packet loss for link quality calculation */
513     olsr_received_hello_handler(lnk);
514   }
515
516   neighbor = lnk->neighbor;
517
518   /*
519    * Hysteresis
520    */
521   if (olsr_cnf->use_hysteresis) {
522     /* Update HELLO timeout */
523     /* printf("MESSAGE HTIME: %f\n", message->htime); */
524     olsr_update_hysteresis_hello(lnk, message->htime);
525   }
526
527   /* Check if we are chosen as MPR */
528   if (lookup_mpr_status(message, in_if))
529     /* source_addr is always the main addr of a node! */
530     olsr_update_mprs_set(&message->source_addr, message->vtime);
531
532   /* Check willingness */
533   if (neighbor->willingness != message->willingness) {
534     struct ipaddr_str buf;
535     OLSR_PRINTF(1, "Willingness for %s changed from %d to %d - UPDATING\n", olsr_ip_to_string(&buf, &neighbor->neighbor_main_addr),
536                 neighbor->willingness, message->willingness);
537     /*
538      *If willingness changed - recalculate
539      */
540     neighbor->willingness = message->willingness;
541     changes_neighborhood = true;
542     changes_topology = true;
543   }
544
545   /* Don't register neighbors of neighbors that announces WILL_NEVER */
546   if (neighbor->willingness != WILL_NEVER)
547     process_message_neighbors(neighbor, message);
548
549   /* Process changes immediately in case of MPR updates */
550   olsr_process_changes();
551
552   olsr_free_hello_packet(message);
553
554   return;
555 }
556
557 /*
558  * Local Variables:
559  * c-basic-offset: 2
560  * indent-tabs-mode: nil
561  * End:
562  */