plugin: dot_draw: readme: make it clear, that it only opens an IPv4-socket, so a...
[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               changes_neighborhood = true;
235               changes_topology = true;
236             }
237           }
238         }
239       }
240     }
241   }
242 }
243
244 /**
245  *Links a one-hop neighbor with a 2-hop neighbor.
246  *
247  *@param neighbor the 1-hop neighbor
248  *@param two_hop_neighbor the 2-hop neighbor
249  *@param vtime the validity time
250  */
251 static void
252 linking_this_2_entries(struct neighbor_entry *neighbor, struct neighbor_2_entry *two_hop_neighbor, olsr_reltime vtime)
253 {
254   struct neighbor_list_entry *list_of_1_neighbors = olsr_malloc(sizeof(struct neighbor_list_entry), "Link entries 1");
255   struct neighbor_2_list_entry *list_of_2_neighbors = olsr_malloc(sizeof(struct neighbor_2_list_entry), "Link entries 2");
256
257   list_of_1_neighbors->neighbor = neighbor;
258
259   list_of_1_neighbors->path_linkcost = LINK_COST_BROKEN;
260   list_of_1_neighbors->saved_path_linkcost = LINK_COST_BROKEN;
261   list_of_1_neighbors->second_hop_linkcost = LINK_COST_BROKEN;
262
263   /* Queue */
264   two_hop_neighbor->neighbor_2_nblist.next->prev = list_of_1_neighbors;
265   list_of_1_neighbors->next = two_hop_neighbor->neighbor_2_nblist.next;
266
267   two_hop_neighbor->neighbor_2_nblist.next = list_of_1_neighbors;
268   list_of_1_neighbors->prev = &two_hop_neighbor->neighbor_2_nblist;
269   list_of_2_neighbors->neighbor_2 = two_hop_neighbor;
270   list_of_2_neighbors->nbr2_nbr = neighbor;     /* XXX refcount */
271
272   olsr_change_timer(list_of_2_neighbors->nbr2_list_timer, vtime, OLSR_NBR2_LIST_JITTER, OLSR_TIMER_ONESHOT);
273
274   /* Queue */
275   neighbor->neighbor_2_list.next->prev = list_of_2_neighbors;
276   list_of_2_neighbors->next = neighbor->neighbor_2_list.next;
277   neighbor->neighbor_2_list.next = list_of_2_neighbors;
278   list_of_2_neighbors->prev = &neighbor->neighbor_2_list;
279
280   /*increment the pointer counter */
281   two_hop_neighbor->neighbor_2_pointer++;
282 }
283
284 /**
285  * Check if a hello message states this node as a MPR.
286  *
287  * @param message the message to check
288  * @param in_if the incoming interface
289  *
290  *@return 1 if we are selected as MPR 0 if not
291  */
292 static bool
293 lookup_mpr_status(const struct hello_message *message, const struct interface *in_if)
294 {
295   struct hello_neighbor *neighbors;
296
297   for (neighbors = message->neighbors; neighbors; neighbors = neighbors->next) {
298     if ( neighbors->link != UNSPEC_LINK
299         && (olsr_cnf->ip_version == AF_INET
300             ? ip4equal(&neighbors->address.v4, &in_if->ip_addr.v4)
301             : ip6equal(&neighbors->address.v6, &in_if->int6_addr.sin6_addr))) {
302
303       if (neighbors->link == SYM_LINK && neighbors->status == MPR_NEIGH) {
304         return true;
305       }
306       break;
307     }
308   }
309   /* Not found */
310   return false;
311 }
312
313 static int
314 deserialize_hello(struct hello_message *hello, const void *ser)
315 {
316   const unsigned char *curr, *limit;
317   uint8_t type;
318   uint16_t size;
319   struct ipaddr_str buf;
320
321   memset (hello, 0, sizeof(*hello));
322
323   curr = ser;
324   pkt_get_u8(&curr, &type);
325   if (type != HELLO_MESSAGE && type != LQ_HELLO_MESSAGE) {
326     /* No need to do anything more */
327     return 1;
328   }
329   pkt_get_reltime(&curr, &hello->vtime);
330   pkt_get_u16(&curr, &size);
331   pkt_get_ipaddress(&curr, &hello->source_addr);
332
333   pkt_get_u8(&curr, &hello->ttl);
334   pkt_get_u8(&curr, &hello->hop_count);
335   pkt_get_u16(&curr, &hello->packet_seq_number);
336   pkt_ignore_u16(&curr);
337
338   pkt_get_reltime(&curr, &hello->htime);
339   pkt_get_u8(&curr, &hello->willingness);
340
341   hello->neighbors = NULL;
342
343   limit = ((const unsigned char *)ser) + size;
344   while (curr < limit) {
345     const unsigned char *limit2 = curr;
346     uint8_t link_code;
347     uint16_t size2;
348
349     pkt_get_u8(&curr, &link_code);
350     pkt_ignore_u8(&curr);
351     pkt_get_u16(&curr, &size2);
352
353     limit2 += size2;
354     while (curr < limit2) {
355       struct hello_neighbor *neigh = olsr_malloc_hello_neighbor("HELLO deserialization");
356       pkt_get_ipaddress(&curr, &neigh->address);
357       if (type == LQ_HELLO_MESSAGE) {
358         olsr_deserialize_hello_lq_pair(&curr, neigh);
359       }
360       neigh->link = EXTRACT_LINK(link_code);
361       neigh->status = EXTRACT_STATUS(link_code);
362
363       neigh->next = hello->neighbors;
364       hello->neighbors = neigh;
365     }
366   }
367   return 0;
368 }
369
370 bool
371 olsr_input_hello(union olsr_message * ser, struct interface * inif, union olsr_ip_addr * from)
372 {
373   struct hello_message hello;
374
375   if (ser == NULL) {
376     return false;
377   }
378   if (deserialize_hello(&hello, ser) != 0) {
379     return false;
380   }
381   olsr_hello_tap(&hello, inif, from);
382
383   /* Do not forward hello messages */
384   return false;
385 }
386
387 /**
388  *Initializing the parser functions we are using
389  */
390 void
391 olsr_init_package_process(void)
392 {
393   if (olsr_cnf->lq_level == 0) {
394     olsr_parser_add_function(&olsr_input_hello, HELLO_MESSAGE);
395     olsr_parser_add_function(&olsr_input_tc, TC_MESSAGE);
396   } else {
397     olsr_parser_add_function(&olsr_input_hello, LQ_HELLO_MESSAGE);
398     olsr_parser_add_function(&olsr_input_tc, LQ_TC_MESSAGE);
399   }
400
401   olsr_parser_add_function(&olsr_input_mid, MID_MESSAGE);
402   olsr_parser_add_function(&olsr_input_hna, HNA_MESSAGE);
403 }
404
405 void
406 olsr_hello_tap(struct hello_message *message, struct interface *in_if, const union olsr_ip_addr *from_addr)
407 {
408   struct neighbor_entry *neighbor;
409
410   /*
411    * Update link status
412    */
413   struct link_entry *lnk = update_link_entry(&in_if->ip_addr, from_addr, message, in_if);
414
415   /*check alias message->source_addr*/
416   if (!ipequal(&message->source_addr,from_addr)){
417     /*new alias of new neighbour are thrown in the mid table to speed up routing*/
418     if (olsr_validate_address(from_addr)) {
419       union olsr_ip_addr * main_addr = mid_lookup_main_addr(from_addr);
420       if ((main_addr==NULL)||(ipequal(&message->source_addr, main_addr))){
421         /*struct ipaddr_str srcbuf, origbuf;
422         olsr_syslog(OLSR_LOG_INFO, "got hello from unknown alias ip of direct neighbour: ip: %s main-ip: %s",
423                     olsr_ip_to_string(&origbuf,&message->source_addr),
424                     olsr_ip_to_string(&srcbuf,from_addr));*/
425         insert_mid_alias(&message->source_addr, from_addr, message->vtime);
426       }
427       else
428       {
429         struct ipaddr_str srcbuf, origbuf;
430         olsr_syslog(OLSR_LOG_INFO, "got hello with invalid from and originator address pair (%s, %s) Duplicate Ips?\n",
431                     olsr_ip_to_string(&origbuf,&message->source_addr),
432                     olsr_ip_to_string(&srcbuf,from_addr));
433       }
434     }
435   }
436
437   if (olsr_cnf->lq_level > 0) {
438     struct hello_neighbor *walker;
439     /* just in case our neighbor has changed its HELLO interval */
440     olsr_update_packet_loss_hello_int(lnk, message->htime);
441
442     /* find the input interface in the list of neighbor interfaces */
443     for (walker = message->neighbors; walker != NULL; walker = walker->next) {
444       if (walker->link != UNSPEC_LINK
445           && ipequal(&walker->address, &in_if->ip_addr)) {
446         break;
447       }
448     }
449
450     /*
451      * memorize our neighbour's idea of the link quality, so that we
452      * know the link quality in both directions
453      *
454      * walker is NULL if there the current interface was not included in
455      * the message (or was included as an UNSPEC_LINK)
456      */
457     olsr_memorize_foreign_hello_lq(lnk, walker);
458
459     /* update packet loss for link quality calculation */
460     olsr_received_hello_handler(lnk);
461   }
462
463   neighbor = lnk->neighbor;
464
465   /*
466    * Hysteresis
467    */
468   if (olsr_cnf->use_hysteresis) {
469     /* Update HELLO timeout */
470     /* printf("MESSAGE HTIME: %f\n", message->htime); */
471     olsr_update_hysteresis_hello(lnk, message->htime);
472   }
473
474   /* Check if we are chosen as MPR */
475   if (lookup_mpr_status(message, in_if))
476     /* source_addr is always the main addr of a node! */
477     olsr_update_mprs_set(&message->source_addr, message->vtime);
478
479   /* Check willingness */
480   if (neighbor->willingness != message->willingness) {
481     struct ipaddr_str buf;
482     OLSR_PRINTF(1, "Willingness for %s changed from %d to %d - UPDATING\n", olsr_ip_to_string(&buf, &neighbor->neighbor_main_addr),
483                 neighbor->willingness, message->willingness);
484     /*
485      *If willingness changed - recalculate
486      */
487     neighbor->willingness = message->willingness;
488     changes_neighborhood = true;
489     changes_topology = true;
490   }
491
492   /* Don't register neighbors of neighbors that announces WILL_NEVER */
493   if (neighbor->willingness != WILL_NEVER)
494     process_message_neighbors(neighbor, message);
495
496   /* Process changes immedeatly in case of MPR updates */
497   olsr_process_changes();
498
499   olsr_free_hello_packet(message);
500
501   return;
502 }
503
504 /*
505  * Local Variables:
506  * c-basic-offset: 2
507  * indent-tabs-mode: nil
508  * End:
509  */