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