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