25e309f5fddc8b35e3adb6508fc35b5990a3650c
[olsrd.git] / src / process_package.c
1 /*
2  * OLSR ad-hoc routing table management protocol
3  * Copyright (C) 2003 Andreas T√łnnesen (andreto@ifi.uio.no)
4  *
5  * This file is part of the olsr.org OLSR daemon.
6  *
7  * olsr.org is free software; you can redistribute it and/or modify
8  * it under the terms of the GNU General Public License as published by
9  * the Free Software Foundation; either version 2 of the License, or
10  * (at your option) any later version.
11  *
12  * olsr.org is distributed in the hope that it will be useful,
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15  * GNU General Public License for more details.
16  *
17  * You should have received a copy of the GNU General Public License
18  * along with olsr.org; if not, write to the Free Software
19  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
20  * 
21  * 
22  * $Id: process_package.c,v 1.15 2004/11/07 18:48:54 kattemat Exp $
23  *
24  */
25
26
27 #include "defs.h"
28 #include "process_package.h"
29 #include "hysteresis.h"
30 #include "two_hop_neighbor_table.h"
31 #include "tc_set.h"
32 #include "mpr_selector_set.h"
33 #include "mid_set.h"
34 #include "olsr.h"
35 #include "parser.h"
36 #include "duplicate_set.h"
37 #include "rebuild_packet.h"
38
39 #ifdef linux 
40 #include "linux/tunnel.h"
41 #endif
42
43
44 /**
45  *Initializing the parser functions we are using
46  */
47 void
48 olsr_init_package_process()
49 {
50 #if !defined USE_LINK_QUALITY
51   olsr_parser_add_function(&olsr_process_received_hello, HELLO_MESSAGE, 1);
52   olsr_parser_add_function(&olsr_process_received_tc, TC_MESSAGE, 1);
53 #else
54   olsr_parser_add_function(&olsr_input_lq_hello, LQ_HELLO_MESSAGE, 1);
55   olsr_parser_add_function(&olsr_input_lq_tc, LQ_TC_MESSAGE, 1);
56 #endif
57   olsr_parser_add_function(&olsr_process_received_mid, MID_MESSAGE, 1);
58   olsr_parser_add_function(&olsr_process_received_hna, HNA_MESSAGE, 1);
59 }
60
61 void
62 olsr_hello_tap(struct hello_message *message, struct interface *in_if,
63                union olsr_ip_addr *from_addr)
64 {
65   struct link_entry         *link;
66   struct neighbor_entry     *neighbor;
67 #if defined USE_LINK_QUALITY
68   struct hello_neighbor *walker;
69 #endif
70
71   /*
72    * Update link status
73    */
74   link = update_link_entry(&in_if->ip_addr, from_addr, message, in_if);
75
76 #if defined USE_LINK_QUALITY
77   // just in case our neighbor has changed its HELLO interval
78
79   olsr_update_packet_loss_hello_int(link, message->htime);
80
81   // find the input interface in the list of neighbor interfaces
82
83   for (walker = message->neighbors; walker != NULL; walker = walker->next)
84     if (COMP_IP(&walker->address, &in_if->ip_addr))
85       break;
86
87   // memorize our neighbour's idea of the link quality, so that we
88   // know the link quality in both directions
89
90   if (walker != NULL)
91     link->neigh_link_quality = walker->link_quality;
92
93   else
94     link->neigh_link_quality = 0.0;
95 #endif
96   
97   neighbor = link->neighbor;
98
99   /*
100    * Hysteresis
101    */
102   if(olsr_cnf->use_hysteresis)
103     {
104       /* Update HELLO timeout */
105       //printf("MESSAGE HTIME: %f\n", message->htime);
106       olsr_update_hysteresis_hello(link, message->htime);
107     }
108
109   /* Check if we are chosen as MPR */
110   if(olsr_lookup_mpr_status(message, in_if))
111     /* source_addr is always the main addr of a node! */
112     olsr_update_mprs_set(&message->source_addr, (float)message->vtime);
113
114
115
116   /* Check willingness */
117   if(neighbor->willingness != message->willingness)
118     {
119       olsr_printf(1, "Willingness for %s changed from %d to %d - UPDATING\n", 
120                   olsr_ip_to_string(&neighbor->neighbor_main_addr),
121                   neighbor->willingness,
122                   message->willingness);
123       /*
124        *If willingness changed - recalculate
125        */
126       neighbor->willingness = message->willingness;
127       changes_neighborhood = OLSR_TRUE;
128       changes_topology = OLSR_TRUE;
129     }
130
131
132   /* Don't register neighbors of neighbors that announces WILL_NEVER */
133   if(neighbor->willingness != WILL_NEVER)
134     olsr_process_message_neighbors(neighbor, message);
135
136   /* Process changes immedeatly in case of MPR updates */
137   olsr_process_changes();
138
139   olsr_destroy_hello_message(message);
140
141   return;
142 }
143
144 /**
145  *Processes a received HELLO message. 
146  *
147  *@param m the incoming OLSR message
148  *@return 0 on sucess
149  */
150
151 void
152 olsr_process_received_hello(union olsr_message *m, struct interface *in_if, union olsr_ip_addr *from_addr)
153 {
154   struct hello_message      message;
155
156   hello_chgestruct(&message, m);
157
158   olsr_hello_tap(&message, in_if, from_addr);
159 }
160
161 void
162 olsr_tc_tap(struct tc_message *message, struct interface *in_if,
163             union olsr_ip_addr *from_addr, union olsr_message *m)
164 {
165   struct tc_mpr_addr              *mpr;
166   struct tc_entry                 *tc_last;
167
168   if(!olsr_check_dup_table_proc(&message->originator, 
169                                 message->packet_seq_number))
170     {
171       goto forward;
172     }
173
174   olsr_printf(3, "Processing TC from %s\n",
175               olsr_ip_to_string(&message->originator));
176
177   /*
178    *      If the sender interface (NB: not originator) of this message
179    *      is not in the symmetric 1-hop neighborhood of this node, the
180    *      message MUST be discarded.
181    */
182
183   if(check_neighbor_link(from_addr) != SYM_LINK)
184     {
185       olsr_printf(2, "Received TC from NON SYM neighbor %s\n",
186                   olsr_ip_to_string(from_addr));
187       olsr_destroy_tc_message(message);
188       return;
189     }
190
191   if(olsr_cnf->debug_level > 2)
192     {
193       mpr = message->multipoint_relay_selector_address;
194       olsr_printf(3, "mpr_selector_list:[");
195
196       while(mpr!=NULL)
197         {
198           olsr_printf(3, "%s:", olsr_ip_to_string(&mpr->address));
199           mpr=mpr->next;
200         }
201
202       olsr_printf(3, "]\n");
203     }
204
205   tc_last = olsr_lookup_tc_entry(&message->originator);
206    
207   if(tc_last != NULL)
208     {
209       /* Update entry */
210
211       /* Delete destinations with lower ANSN */
212       if(olsr_tc_delete_mprs(tc_last, message))
213         changes_topology = OLSR_TRUE; 
214
215       /* Update destinations */
216       if(olsr_tc_update_mprs(tc_last, message))
217         changes_topology = OLSR_TRUE;
218
219       /* Delete possible empty TC entry */
220       if(changes_topology)
221         olsr_tc_delete_entry_if_empty(tc_last);
222     }
223
224   else
225     {
226       /*if message is empty then skip it */
227       if(message->multipoint_relay_selector_address != NULL)
228         {
229           /* New entry */
230           tc_last = olsr_add_tc_entry(&message->originator);      
231           
232           /* Update destinations */
233           olsr_tc_update_mprs(tc_last, message);
234           
235           changes_topology = OLSR_TRUE;
236         }
237       else
238         {
239           olsr_printf(3, "Dropping empty TC from %s\n",
240                       olsr_ip_to_string(&message->originator)); 
241         }
242     }
243
244   /* Process changes */
245   //olsr_process_changes();
246
247  forward:
248
249   olsr_forward_message(m, 
250                        &message->originator, 
251                        message->packet_seq_number, 
252                        in_if,
253                        from_addr);
254
255   olsr_destroy_tc_message(message);
256
257   return;
258 }
259
260 /**
261  *Process a received TopologyControl message
262  *
263  *
264  *@param m the incoming OLSR message
265  *@return 0 on success
266  */
267 void
268 olsr_process_received_tc(union olsr_message *m, struct interface *in_if, union olsr_ip_addr *from_addr)
269
270   struct tc_message               message;
271
272   tc_chgestruct(&message, m, from_addr);
273
274   olsr_tc_tap(&message, in_if, from_addr, m);
275 }
276
277
278
279
280
281
282 /**
283  *Process a received(and parsed) MID message
284  *For every address check if there is a topology node
285  *registered with it and update its addresses.
286  *
287  *@param m the OLSR message received.
288  *@return 1 on success
289  */
290
291 void
292 olsr_process_received_mid(union olsr_message *m, struct interface *in_if, union olsr_ip_addr *from_addr)
293 {
294   struct mid_alias *tmp_adr;
295   struct mid_message message;
296
297
298   mid_chgestruct(&message, m);
299
300   /*
301   if(COMP_IP(&message.mid_origaddr, &main_addr))
302     {
303       goto forward;  
304     }
305   */
306
307   if(!olsr_check_dup_table_proc(&message.mid_origaddr, 
308                                 message.mid_seqno))
309     {
310       goto forward;
311     }
312   
313   olsr_printf(5, "Processing MID from %s...\n", olsr_ip_to_string(&message.mid_origaddr));
314
315   tmp_adr = message.mid_addr;
316
317
318   /*
319    *      If the sender interface (NB: not originator) of this message
320    *      is not in the symmetric 1-hop neighborhood of this node, the
321    *      message MUST be discarded.
322    */
323
324   if(check_neighbor_link(from_addr) != SYM_LINK)
325     {
326       olsr_printf(2, "Received MID from NON SYM neighbor %s\n", olsr_ip_to_string(from_addr));
327       olsr_destroy_mid_message(&message);
328       return;
329     }
330
331
332
333   /* Update the timeout of the MID */
334   olsr_update_mid_table(&message.mid_origaddr, (float)message.vtime);
335
336   while(tmp_adr)
337     {
338       if(!mid_lookup_main_addr(&tmp_adr->alias_addr))
339         {
340           olsr_printf(1, "MID new: (%s, ", olsr_ip_to_string(&message.mid_origaddr));
341           olsr_printf(1, "%s)\n", olsr_ip_to_string(&tmp_adr->alias_addr));
342           insert_mid_alias(&message.mid_origaddr, &tmp_adr->alias_addr, (float)message.vtime);
343         }
344
345
346       tmp_adr = tmp_adr->next;
347     } 
348   
349   /*Update topology if neccesary*/
350   //olsr_process_changes();
351
352  forward:
353   
354   olsr_forward_message(m, 
355                        &message.mid_origaddr, 
356                        message.mid_seqno, 
357                        in_if,
358                        from_addr);
359   olsr_destroy_mid_message(&message);
360
361   return;
362 }
363
364
365
366
367
368 /**
369  *Process incoming HNA message.
370  *Forwards the message if that is to be done.
371  *
372  *@param m the incoming OLSR message
373  *the OLSR message.
374  *@return 1 on success
375  */
376
377 void
378 olsr_process_received_hna(union olsr_message *m, struct interface *in_if, union olsr_ip_addr *from_addr)
379 {
380   struct hna_net_addr  *hna_tmp;
381   struct  hna_message message;
382
383   //printf("Processing HNA\n");
384
385   hna_chgestruct(&message, m);
386   
387
388   /* Process message */   
389   /*
390   if(COMP_IP(&message.originator, &main_addr)) 
391     {
392       goto forward;
393     }
394   */
395
396   if(!olsr_check_dup_table_proc(&message.originator, 
397                                 message.packet_seq_number))
398     {
399       goto forward;
400     }
401
402
403
404
405   hna_tmp = message.hna_net;
406
407
408
409   /*
410    *      If the sender interface (NB: not originator) of this message
411    *      is not in the symmetric 1-hop neighborhood of this node, the
412    *      message MUST be discarded.
413    */
414
415
416   if(check_neighbor_link(from_addr) != SYM_LINK)
417     {
418       olsr_printf(2, "Received HNA from NON SYM neighbor %s\n", olsr_ip_to_string(from_addr));
419       olsr_destroy_hna_message(&message);
420       return;
421     }
422
423   while(hna_tmp)
424     {
425 #ifdef linux
426       /*
427        * Set up tunnel to Internet gateway
428        */
429       if((use_tunnel) && (olsr_cnf->ip_version == AF_INET) && (hna_tmp->net.v4 == 0))
430         {
431           if(inet_tnl_added || gw_tunnel)
432             {
433               hna_tmp = hna_tmp->next;
434               continue;
435             }
436           
437           olsr_printf(1, "Internet gateway discovered! Setting up tunnel:\n");
438
439           /* Set up tunnel endpoint */
440           set_up_source_tnl(&main_addr, &message.originator, in_if->if_index); 
441         }
442       else
443 #endif
444         {
445           olsr_update_hna_entry(&message.originator, &hna_tmp->net, &hna_tmp->netmask, (float)message.vtime); 
446         }
447       
448       hna_tmp = hna_tmp->next;
449     }
450   
451   /*Update topology if neccesary*/
452   //olsr_process_changes();
453
454  forward:
455   olsr_forward_message(m, 
456                        &message.originator, 
457                        message.packet_seq_number, 
458                        in_if,
459                        from_addr);
460   olsr_destroy_hna_message(&message);
461
462   return;
463 }
464
465
466
467
468
469
470
471 /**
472  *Processes an list of neighbors from an incoming HELLO message.
473  *@param neighbor the neighbor who sendt the message.
474  *@param message the HELLO message
475  *@return nada
476  */
477 void
478 olsr_process_message_neighbors(struct neighbor_entry *neighbor,
479                                struct hello_message *message)
480 {
481   struct hello_neighbor        *message_neighbors;
482   struct neighbor_2_list_entry *two_hop_neighbor_yet;
483   struct neighbor_2_entry      *two_hop_neighbor;
484   union olsr_ip_addr           *neigh_addr;
485
486 #if defined USE_LINK_QUALITY
487   struct neighbor_list_entry *walker;
488   double link_quality =
489     olsr_neighbor_best_link_quality(&neighbor->neighbor_main_addr);
490 #endif
491
492   for(message_neighbors = message->neighbors;
493       message_neighbors != NULL;
494       message_neighbors = message_neighbors->next)
495     {
496       /*
497        *check all interfaces
498        *so that we don't add ourselves to the
499        *2 hop list
500        *IMPORTANT!
501        */
502       if(if_ifwithaddr(&message_neighbors->address) != NULL)
503         continue;
504
505       /* Get the main address */
506
507       neigh_addr = mid_lookup_main_addr(&message_neighbors->address);
508
509       if (neigh_addr != NULL)
510         COPY_IP(&message_neighbors->address, neigh_addr);
511       
512       if(((message_neighbors->status == SYM_NEIGH) ||
513           (message_neighbors->status == MPR_NEIGH)))
514         {
515           //printf("\tProcessing %s\n", olsr_ip_to_string(&message_neighbors->address));
516           //printf("\tMain addr: %s\n", olsr_ip_to_string(neigh_addr));
517           
518           two_hop_neighbor_yet =
519             olsr_lookup_my_neighbors(neighbor,
520                                      &message_neighbors->address);
521
522           if (two_hop_neighbor_yet != NULL)
523             {
524               /* Updating the holding time for this neighbor */
525               olsr_get_timestamp((olsr_u32_t)message->vtime * 1000,
526                                  &two_hop_neighbor_yet->neighbor_2_timer);
527
528               two_hop_neighbor = two_hop_neighbor_yet->neighbor_2;
529             }
530           else
531             {
532               two_hop_neighbor =
533                 olsr_lookup_two_hop_neighbor_table(&message_neighbors->address);
534               if (two_hop_neighbor == NULL)
535                 {
536                   //printf("Adding 2 hop neighbor %s\n\n", olsr_ip_to_string(&message_neighbors->address)); 
537
538                   changes_neighborhood = OLSR_TRUE;
539                   changes_topology = OLSR_TRUE;
540
541                   two_hop_neighbor =
542                     olsr_malloc(sizeof(struct neighbor_2_entry),
543                                 "Process HELLO");
544                   
545                   two_hop_neighbor->neighbor_2_nblist.next =
546                     &two_hop_neighbor->neighbor_2_nblist;
547
548                   two_hop_neighbor->neighbor_2_nblist.prev =
549                     &two_hop_neighbor->neighbor_2_nblist;
550
551                   two_hop_neighbor->neighbor_2_pointer = 0;
552                   
553                   COPY_IP(&two_hop_neighbor->neighbor_2_addr,
554                           &message_neighbors->address);
555
556                   olsr_insert_two_hop_neighbor_table(two_hop_neighbor);
557
558                   olsr_linking_this_2_entries(neighbor, two_hop_neighbor,
559                                               (float)message->vtime);
560                 }
561               else
562                 {
563                   /*
564                     linking to this two_hop_neighbor entry
565                   */    
566                   changes_neighborhood = OLSR_TRUE;
567                   changes_topology = OLSR_TRUE;
568                   
569                   olsr_linking_this_2_entries(neighbor, two_hop_neighbor,
570                                               (float)message->vtime); 
571                 }
572             }
573 #if defined USE_LINK_QUALITY
574           // loop through the one-hop neighbors that see this
575           // two hop neighbour
576
577           for (walker = two_hop_neighbor->neighbor_2_nblist.next;
578                walker != &two_hop_neighbor->neighbor_2_nblist;
579                walker = walker->next)
580             {
581               // have we found the one-hop neighbor that sent the
582               // HELLO message that we're current processing?
583
584               if (walker->neighbor == neighbor)
585                 {
586                   // total link quality = link quality between us
587                   // and our one-hop neighbor x link quality between
588                   // our one-hop neighbor and the two-hop neighbor
589
590                   walker->full_link_quality =
591                     link_quality *
592                     message_neighbors->link_quality *
593                     message_neighbors->neigh_link_quality;
594                 }
595             }
596 #endif
597         }
598     }
599 }
600
601
602
603
604
605
606
607
608 /**
609  *Links a one-hop neighbor with a 2-hop neighbor.
610  *
611  *@param neighbor the 1-hop neighbor
612  *@param two_hop_neighbor the 2-hop neighbor
613  *@return nada
614  */
615 void
616 olsr_linking_this_2_entries(struct neighbor_entry *neighbor,struct neighbor_2_entry *two_hop_neighbor, float vtime)
617 {
618   struct neighbor_list_entry    *list_of_1_neighbors;
619   struct neighbor_2_list_entry  *list_of_2_neighbors;
620
621   list_of_1_neighbors = olsr_malloc(sizeof(struct neighbor_list_entry), "Link entries 1");
622
623   list_of_2_neighbors = olsr_malloc(sizeof(struct neighbor_2_list_entry), "Link entries 2");
624
625   list_of_1_neighbors->neighbor = neighbor;
626
627 #if defined USE_LINK_QUALITY
628   list_of_1_neighbors->full_link_quality = 0.0;
629 #endif
630
631   /* Queue */
632   two_hop_neighbor->neighbor_2_nblist.next->prev = list_of_1_neighbors;
633   list_of_1_neighbors->next = two_hop_neighbor->neighbor_2_nblist.next;
634   two_hop_neighbor->neighbor_2_nblist.next = list_of_1_neighbors;
635   list_of_1_neighbors->prev = &two_hop_neighbor->neighbor_2_nblist;
636
637
638   list_of_2_neighbors->neighbor_2 = two_hop_neighbor;
639   
640   olsr_get_timestamp((olsr_u32_t) vtime*1000, &list_of_2_neighbors->neighbor_2_timer);
641
642   /* Queue */
643   neighbor->neighbor_2_list.next->prev = list_of_2_neighbors;
644   list_of_2_neighbors->next = neighbor->neighbor_2_list.next;
645   neighbor->neighbor_2_list.next = list_of_2_neighbors;
646   list_of_2_neighbors->prev = &neighbor->neighbor_2_list;
647   
648   /*increment the pointer counter*/
649   two_hop_neighbor->neighbor_2_pointer++;
650 }
651
652
653
654
655
656
657 /**
658  *Check if a hello message states this node as a MPR.
659  *
660  *@param message the message to check
661  *@param n_link the buffer to put the link status in
662  *@param n_status the buffer to put the status in
663  *
664  *@return 1 if we are selected as MPR 0 if not
665  */
666 int
667 olsr_lookup_mpr_status(struct hello_message *message, struct interface *in_if)
668 {
669   
670   struct hello_neighbor  *neighbors;
671
672   neighbors=message->neighbors;
673   
674   while(neighbors!=NULL)
675     {  
676       //printf("(linkstatus)Checking %s ",olsr_ip_to_string(&neighbors->address));
677       //printf("against %s\n",olsr_ip_to_string(&main_addr));
678
679
680     if(olsr_cnf->ip_version == AF_INET)
681       { 
682         /* IPv4 */  
683         if(COMP_IP(&neighbors->address, &in_if->ip_addr))
684           {
685             //printf("ok");
686             if((neighbors->link == SYM_LINK) && (neighbors->status == MPR_NEIGH))
687               return 1;
688             
689             return 0;
690           }
691       }
692     else
693       { 
694         /* IPv6 */  
695         if(COMP_IP(&neighbors->address, &in_if->int6_addr.sin6_addr))
696           {
697             //printf("ok");
698             if((neighbors->link == SYM_LINK) && (neighbors->status == MPR_NEIGH))
699               return 1;
700             
701             return 0;
702           }
703       }
704  
705       neighbors = neighbors->next; 
706     }
707
708   /* Not found */
709   return 0;
710 }