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