Fixed crash when changing IPv6 addresses
[olsrd.git] / src / link_set.c
1 /*
2  * The olsr.org Optimized Link-State Routing daemon(olsrd)
3  * Copyright (c) 2004, Andreas T√łnnesen(andreto@olsr.org)
4  * All rights reserved.
5  *
6  * Redistribution and use in source and binary forms, with or without 
7  * modification, are permitted provided that the following conditions 
8  * are met:
9  *
10  * * Redistributions of source code must retain the above copyright 
11  *   notice, this list of conditions and the following disclaimer.
12  * * Redistributions in binary form must reproduce the above copyright 
13  *   notice, this list of conditions and the following disclaimer in 
14  *   the documentation and/or other materials provided with the 
15  *   distribution.
16  * * Neither the name of olsr.org, olsrd nor the names of its 
17  *   contributors may be used to endorse or promote products derived 
18  *   from this software without specific prior written permission.
19  *
20  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 
21  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 
22  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 
23  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 
24  * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, 
25  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, 
26  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 
27  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER 
28  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 
29  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN 
30  * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 
31  * POSSIBILITY OF SUCH DAMAGE.
32  *
33  * Visit http://www.olsr.org for more information.
34  *
35  * If you find this software useful feel free to make a donation
36  * to the project. For more information see the website or contact
37  * the copyright holders.
38  *
39  * $Id: link_set.c,v 1.57 2005/04/22 11:48:04 kattemat Exp $
40  */
41
42
43 /*
44  * Link sensing database for the OLSR routing daemon
45  */
46
47 #include "defs.h"
48 #include "link_set.h"
49 #include "hysteresis.h"
50 #include "mid_set.h"
51 #include "mpr.h"
52 #include "neighbor_table.h"
53 #include "olsr.h"
54 #include "scheduler.h"
55 #include "lq_route.h"
56
57 static clock_t hold_time_neighbor;
58
59 static struct link_entry *link_set;
60
61 static int
62 check_link_status(struct hello_message *message, struct interface *in_if);
63
64 static void
65 olsr_time_out_hysteresis(void);
66
67 static void olsr_time_out_packet_loss(void);
68
69 static struct link_entry *
70 add_new_entry(union olsr_ip_addr *, union olsr_ip_addr *, union olsr_ip_addr *, double, double);
71
72 static void
73 olsr_time_out_link_set(void);
74
75 static int
76 get_neighbor_status(union olsr_ip_addr *);
77
78
79 clock_t 
80 get_hold_time_neighbor()
81 {
82   return hold_time_neighbor;
83 }
84
85 struct link_entry *
86 get_link_set()
87 {
88   return link_set;
89 }
90
91 void
92 olsr_init_link_set()
93 {
94
95   /* Timers */
96   hold_time_neighbor = (NEIGHB_HOLD_TIME*1000) / system_tick_divider;
97
98   olsr_register_timeout_function(&olsr_time_out_link_set);
99   if(olsr_cnf->use_hysteresis)
100     {
101       olsr_register_timeout_function(&olsr_time_out_hysteresis);
102     }
103
104   if (olsr_cnf->lq_level > 0)
105     {
106       olsr_register_timeout_function(&olsr_time_out_packet_loss);
107     }
108 }
109
110
111
112 /**
113  * Get the status of a link. The status is based upon different
114  * timeouts in the link entry.
115  *
116  *@param remote address of the remote interface
117  *
118  *@return the link status of the link
119  */
120 int
121 lookup_link_status(struct link_entry *entry)
122 {
123
124   if(entry == NULL || link_set == NULL)
125     return UNSPEC_LINK;
126
127   /*
128    * Hysteresis
129    */
130   if(olsr_cnf->use_hysteresis)
131     {
132       /*
133         if L_LOST_LINK_time is not expired, the link is advertised
134         with a link type of LOST_LINK.
135       */
136
137       if(!TIMED_OUT(entry->L_LOST_LINK_time))
138         return LOST_LINK;
139       /*
140         otherwise, if L_LOST_LINK_time is expired and L_link_pending
141         is set to "true", the link SHOULD NOT be advertised at all;
142       */
143       if(entry->L_link_pending == 1)
144         {
145 #ifdef DEBUG
146           OLSR_PRINTF(3, "HYST[%s]: Setting to HIDE\n", olsr_ip_to_string(&entry->neighbor_iface_addr))
147 #endif
148           return HIDE_LINK;
149         }
150       /*
151         otherwise, if L_LOST_LINK_time is expired and L_link_pending
152         is set to "false", the link is advertised as described
153         previously in section 6.
154       */
155     }
156
157   if(!TIMED_OUT(entry->SYM_time))
158     return SYM_LINK;
159
160   if(!TIMED_OUT(entry->ASYM_time))
161     return ASYM_LINK;
162
163   return LOST_LINK;
164
165
166 }
167
168
169
170
171
172
173 /**
174  *Find the "best" link status to a
175  *neighbor
176  *
177  *@param address the address to check for
178  *
179  *@return SYM_LINK if a symmetric link exists 0 if not
180  */
181 static int
182 get_neighbor_status(union olsr_ip_addr *address)
183 {
184   union olsr_ip_addr *main_addr;
185   struct interface   *ifs;
186
187   //printf("GET_NEIGHBOR_STATUS\n");
188
189   /* Find main address */
190   if(!(main_addr = mid_lookup_main_addr(address)))
191     main_addr = address;
192
193   //printf("\tmain: %s\n", olsr_ip_to_string(main_addr));
194
195   /* Loop trough local interfaces to check all possebilities */
196   for(ifs = ifnet; ifs != NULL; ifs = ifs->int_next)
197     {
198       struct mid_address   *aliases;
199       struct link_entry  *link;
200
201       //printf("\tChecking %s->", olsr_ip_to_string(&ifs->ip_addr));
202       //printf("%s : ", olsr_ip_to_string(main_addr)); 
203       if((link = lookup_link_entry(main_addr, &ifs->ip_addr)) != NULL)
204         {
205           //printf("%d\n", lookup_link_status(link));
206           if(lookup_link_status(link) == SYM_LINK)
207             return SYM_LINK;
208         }
209       /* Get aliases */
210       for(aliases = mid_lookup_aliases(main_addr);
211           aliases != NULL;
212           aliases = aliases->next_alias)
213         {
214           //printf("\tChecking %s->", olsr_ip_to_string(&ifs->ip_addr));
215           //printf("%s : ", olsr_ip_to_string(&aliases->address)); 
216           if((link = lookup_link_entry(&aliases->alias, &ifs->ip_addr)) != NULL)
217             {
218               //printf("%d\n", lookup_link_status(link));
219
220               if(lookup_link_status(link) == SYM_LINK)
221                 return SYM_LINK;
222             }
223         }
224     }
225   
226   return 0;
227 }
228
229 /**
230  * Find best link to a neighbor
231  */
232
233 struct link_entry *
234 get_best_link_to_neighbor(union olsr_ip_addr *remote)
235 {
236   union olsr_ip_addr *main_addr;
237   struct link_entry *walker, *good_link, *backup_link;
238   int curr_metric = MAX_IF_METRIC;
239   float curr_lq = -1.0;
240   
241   // main address lookup
242
243   main_addr = mid_lookup_main_addr(remote);
244
245   // "remote" *already is* the main address
246
247   if (main_addr == NULL)
248     main_addr = remote;
249
250   // we haven't selected any links, yet
251
252   good_link = NULL;
253   backup_link = NULL;
254
255   // loop through all links that we have
256
257   for (walker = link_set; walker != NULL; walker = walker->next)
258   {
259     // if this is not a link to the neighour in question, skip
260
261     if (!COMP_IP(&walker->neighbor->neighbor_main_addr, main_addr))
262       continue;
263
264     // handle the non-LQ case
265
266     if (olsr_cnf->lq_level == 0)
267     {
268       struct interface *tmp_if;
269
270       // find the interface for the link - we select the link with the
271       // best local interface metric
272
273       tmp_if = if_ifwithaddr(&walker->local_iface_addr);
274
275       if(!tmp_if)
276         continue;
277
278       // is this interface better than anything we had before?
279
280       if ((tmp_if->int_metric < curr_metric) ||
281           // use the requested remote interface address as a tie-breaker
282           ((tmp_if->int_metric == curr_metric) && 
283            COMP_IP(&walker->local_iface_addr, remote)))
284       {
285         // memorize the interface's metric
286
287         curr_metric = tmp_if->int_metric;
288
289         // prefer symmetric links over asymmetric links
290
291         if (lookup_link_status(walker) == SYM_LINK)
292           good_link = walker;
293
294         else
295           backup_link = walker;
296       }
297     }
298
299     // handle the LQ case
300
301     else
302     {
303       float tmp_lq;
304
305       // calculate the bi-directional link quality - we select the link
306       // with the best link quality
307
308       tmp_lq = walker->loss_link_quality * walker->neigh_link_quality;
309
310       // is this link better than anything we had before?
311               
312       if((tmp_lq > curr_lq) ||
313          // use the requested remote interface address as a tie-breaker
314          ((tmp_lq == curr_lq) && COMP_IP(&walker->local_iface_addr, remote)))
315       {
316         // memorize the link quality
317
318         curr_lq = tmp_lq;
319
320         // prefer symmetric links over asymmetric links
321
322         if(lookup_link_status(walker) == SYM_LINK)
323           good_link = walker;
324
325         else
326           backup_link = walker;
327       }
328     }
329   }
330
331   // if we haven't found any symmetric links, try to return an
332   // asymmetric link
333
334   return good_link ? good_link : backup_link;
335 }
336
337 static void set_loss_link_multiplier(struct link_entry *entry)
338 {
339   struct interface *inter;
340   struct olsr_if *cfg_inter;
341   struct olsr_lq_mult *mult;
342   float val = -1.0;
343   union olsr_ip_addr null_addr;
344
345   // find the interface for the link
346
347   inter = if_ifwithaddr(&entry->local_iface_addr);
348
349   // find the interface configuration for the interface
350
351   for (cfg_inter = olsr_cnf->interfaces; cfg_inter != NULL;
352        cfg_inter = cfg_inter->next)
353     if (cfg_inter->interf == inter)
354       break;
355
356   // create a null address for comparison
357
358   memset(&null_addr, 0, sizeof (union olsr_ip_addr));
359
360   // loop through the multiplier entries
361
362   for (mult = cfg_inter->cnf->lq_mult; mult != NULL; mult = mult->next)
363   {
364     // use the default multiplier only if there isn't any entry that
365     // has a matching IP address
366
367     if ((COMP_IP(&mult->addr, &null_addr) && val < 0.0) ||
368         COMP_IP(&mult->addr, &entry->neighbor_iface_addr))
369       val = mult->val;
370   }
371
372   // if we have not found an entry, then use the default multiplier
373
374   if (val < 0)
375     val = 1.0;
376
377   // store the multiplier
378
379   entry->loss_link_multiplier = val;
380 }
381
382 /**
383  *Nothing mysterious here.
384  *Adding a new link entry to the link set.
385  *
386  *@param local the local IP address
387  *@param remote the remote IP address
388  *@param remote_main teh remote nodes main address
389  *@param vtime the validity time of the entry
390  *@param htime the HELLO interval of the remote node
391  */
392
393 static struct link_entry *
394 add_new_entry(union olsr_ip_addr *local, union olsr_ip_addr *remote, union olsr_ip_addr *remote_main, double vtime, double htime)
395 {
396   struct link_entry *tmp_link_set, *new_link;
397   struct neighbor_entry *neighbor;
398
399   tmp_link_set = link_set;
400
401   while(tmp_link_set)
402     {
403       if(COMP_IP(remote, &tmp_link_set->neighbor_iface_addr) &&
404          COMP_IP(local, &tmp_link_set->local_iface_addr))
405         return tmp_link_set;
406       tmp_link_set = tmp_link_set->next;
407     }
408
409   /*
410    * if there exists no link tuple with
411    * L_neighbor_iface_addr == Source Address
412    */
413
414 #ifdef DEBUG
415   OLSR_PRINTF(3, "Adding %s to link set\n", olsr_ip_to_string(remote))
416 #endif
417
418   /* a new tuple is created with... */
419
420   new_link = olsr_malloc(sizeof(struct link_entry), "new link entry");
421
422   memset(new_link, 0 , sizeof(struct link_entry));
423   /*
424    * L_local_iface_addr = Address of the interface
425    * which received the HELLO message
426    */
427   //printf("\tLocal IF: %s\n", olsr_ip_to_string(local));
428   COPY_IP(&new_link->local_iface_addr, local);
429   /* L_neighbor_iface_addr = Source Address */
430   COPY_IP(&new_link->neighbor_iface_addr, remote);
431
432   /* L_SYM_time            = current time - 1 (expired) */
433   new_link->SYM_time = now_times - 1;
434
435   /* L_time = current time + validity time */
436   new_link->time = GET_TIMESTAMP(vtime*1000);
437
438   new_link->prev_status = ASYM_LINK;
439
440   /* HYSTERESIS */
441   if(olsr_cnf->use_hysteresis)
442     {
443       new_link->L_link_pending = 1;
444       new_link->L_LOST_LINK_time = GET_TIMESTAMP(vtime*1000);
445       new_link->hello_timeout = GET_TIMESTAMP(htime*1500);
446       new_link->last_htime = htime;
447       new_link->olsr_seqno = 0;
448       new_link->olsr_seqno_valid = OLSR_FALSE;
449     }
450
451   new_link->L_link_quality = 0.0;
452
453   if (olsr_cnf->lq_level > 0)
454     {
455       new_link->loss_hello_int = htime;
456
457       new_link->loss_timeout = GET_TIMESTAMP(htime * 1500.0);
458
459       new_link->loss_seqno = 0;
460       new_link->loss_seqno_valid = 0;
461       new_link->loss_missed_hellos = 0;
462
463       new_link->lost_packets = 0;
464       new_link->total_packets = 0;
465
466       new_link->loss_window_size = olsr_cnf->lq_wsize;
467       new_link->loss_index = 0;
468
469       memset(new_link->loss_bitmap, 0, sizeof (new_link->loss_bitmap));
470
471       set_loss_link_multiplier(new_link);
472     }
473
474   new_link->loss_link_quality = 0.0;
475   new_link->neigh_link_quality = 0.0;
476
477   new_link->saved_loss_link_quality = 0.0;
478   new_link->saved_neigh_link_quality = 0.0;
479
480   /* Add to queue */
481   new_link->next = link_set;
482   link_set = new_link;
483
484
485   /*
486    * Create the neighbor entry
487    */
488
489   /* Neighbor MUST exist! */
490   if(NULL == (neighbor = olsr_lookup_neighbor_table(remote_main)))
491     {
492       neighbor = olsr_insert_neighbor_table(remote_main);
493 #ifdef DEBUG
494       OLSR_PRINTF(3, "ADDING NEW NEIGHBOR ENTRY %s FROM LINK SET\n", olsr_ip_to_string(remote_main))
495 #endif
496     }
497
498   /* Copy the main address - make sure this is done every time
499    * as neighbors might change main address */
500   COPY_IP(&neighbor->neighbor_main_addr, remote_main);
501
502   neighbor->linkcount++;
503
504
505   new_link->neighbor = neighbor;
506
507   if(!COMP_IP(remote, remote_main))
508     {
509       /* Add MID alias if not already registered */
510       /* This is kind of sketchy... and not specified
511        * in the RFC. We can only guess a vtime.
512        * We'll go for one that is hopefully long
513        * enough in most cases. 20 seconds
514        */
515       OLSR_PRINTF(1, "Adding MID alias main %s ", olsr_ip_to_string(remote_main))
516       OLSR_PRINTF(1, "-> %s based on HELLO\n\n", olsr_ip_to_string(remote))
517       insert_mid_alias(remote_main, remote, 20.0);
518     }
519
520   return link_set;
521 }
522
523
524 /**
525  *Lookup the status of a link.
526  *
527  *@param int_addr address of the remote interface
528  *
529  *@return 1 of the link is symmertic 0 if not
530  */
531
532 int
533 check_neighbor_link(union olsr_ip_addr *int_addr)
534 {
535   struct link_entry *tmp_link_set;
536
537   tmp_link_set = link_set;
538
539   while(tmp_link_set)
540     {
541       if(COMP_IP(int_addr, &tmp_link_set->neighbor_iface_addr))
542         return lookup_link_status(tmp_link_set);
543       tmp_link_set = tmp_link_set->next;
544     }
545   return UNSPEC_LINK;
546 }
547
548
549 /**
550  *Lookup a link entry
551  *
552  *@param remote the remote interface address
553  *@param local the local interface address
554  *
555  *@return the link entry if found, NULL if not
556  */
557 struct link_entry *
558 lookup_link_entry(union olsr_ip_addr *remote, union olsr_ip_addr *local)
559 {
560   struct link_entry *tmp_link_set;
561
562   tmp_link_set = link_set;
563
564   while(tmp_link_set)
565     {
566       if(COMP_IP(remote, &tmp_link_set->neighbor_iface_addr) &&
567          COMP_IP(local, &tmp_link_set->local_iface_addr))
568         return tmp_link_set;
569       tmp_link_set = tmp_link_set->next;
570     }
571   return NULL;
572
573 }
574
575
576
577
578
579
580
581 /**
582  *Update a link entry. This is the "main entrypoint" in
583  *the link-sensing. This function is calles from the HELLO
584  *parser function.
585  *It makes sure a entry is updated or created.
586  *
587  *@param local the local IP address
588  *@param remote the remote IP address
589  *@param message the HELLO message
590  *@param in_if the interface on which this HELLO was received
591  *
592  *@return the link_entry struct describing this link entry
593  */
594 struct link_entry *
595 update_link_entry(union olsr_ip_addr *local, 
596                   union olsr_ip_addr *remote, 
597                   struct hello_message *message, 
598                   struct interface *in_if)
599 {
600   struct link_entry *entry;
601
602   /* Add if not registered */
603   entry = add_new_entry(local, remote, &message->source_addr, message->vtime, message->htime);
604
605   /* Update ASYM_time */
606   //printf("Vtime is %f\n", message->vtime);
607   /* L_ASYM_time = current time + validity time */
608   entry->ASYM_time = GET_TIMESTAMP(message->vtime*1000);
609   
610   entry->prev_status = check_link_status(message, in_if);
611   
612   //printf("Status %d\n", status);
613   
614   switch(entry->prev_status)
615     {
616     case(LOST_LINK):
617       /* L_SYM_time = current time - 1 (i.e., expired) */
618       entry->SYM_time = now_times - 1;
619
620       break;
621     case(SYM_LINK):
622     case(ASYM_LINK):
623       /* L_SYM_time = current time + validity time */
624       //printf("updating SYM time for %s\n", olsr_ip_to_string(remote));
625       entry->SYM_time = GET_TIMESTAMP(message->vtime*1000);
626
627       /* L_time = L_SYM_time + NEIGHB_HOLD_TIME */
628       entry->time = entry->SYM_time + hold_time_neighbor;
629
630       break;
631     default:;
632     }
633
634   /* L_time = max(L_time, L_ASYM_time) */
635   if(entry->time < entry->ASYM_time)
636     entry->time = entry->ASYM_time;
637
638
639   /*
640   printf("Updating link LOCAL: %s ", olsr_ip_to_string(local));
641   printf("REMOTE: %s\n", olsr_ip_to_string(remote));
642   printf("VTIME: %f ", message->vtime);
643   printf("STATUS: %d\n", status);
644   */
645
646   /* Update hysteresis values */
647   if(olsr_cnf->use_hysteresis)
648     olsr_process_hysteresis(entry);
649
650   /* Update neighbor */
651   update_neighbor_status(entry->neighbor, get_neighbor_status(remote));
652
653   return entry;  
654 }
655
656
657 /**
658  * Fuction that updates all registered pointers to
659  * one neighbor entry with another pointer
660  * Used by MID updates.
661  *
662  *@old the pointer to replace
663  *@new the pointer to use instead of "old"
664  *
665  *@return the number of entries updated
666  */
667 int
668 replace_neighbor_link_set(struct neighbor_entry *old,
669                           struct neighbor_entry *new)
670 {
671   struct link_entry *tmp_link_set;
672   int retval;
673
674   retval = 0;
675
676   if(link_set == NULL)
677     return retval;
678       
679   tmp_link_set = link_set;
680
681   while(tmp_link_set)
682     {
683
684       if(tmp_link_set->neighbor == old)
685         {
686           tmp_link_set->neighbor = new;
687           retval++;
688         }
689       tmp_link_set = tmp_link_set->next;
690     }
691
692   return retval;
693
694 }
695
696
697 /**
698  *Checks the link status to a neighbor by
699  *looking in a received HELLO message.
700  *
701  *@param message the HELLO message to check
702  *
703  *@return the link status
704  */
705 static int
706 check_link_status(struct hello_message *message, struct interface *in_if)
707 {
708   struct hello_neighbor  *neighbors;
709
710   neighbors = message->neighbors;
711   
712   while(neighbors!=NULL)
713     {
714       if(COMP_IP(&neighbors->address, &in_if->ip_addr))
715         {
716           //printf("ok");
717           return neighbors->link;
718         }
719
720       neighbors = neighbors->next; 
721     }
722
723
724   return UNSPEC_LINK;
725 }
726
727
728 /**
729  *Time out the link set. In other words, the link
730  *set is traversed and all non-valid entries are
731  *deleted.
732  *
733  */
734 static void
735 olsr_time_out_link_set()
736 {
737
738   struct link_entry *tmp_link_set, *last_link_entry;
739
740   if(link_set == NULL)
741     return;
742       
743   tmp_link_set = link_set;
744   last_link_entry = NULL;
745
746   while(tmp_link_set)
747     {
748
749       if(TIMED_OUT(tmp_link_set->time))
750         {
751           if(last_link_entry != NULL)
752             {
753               last_link_entry->next = tmp_link_set->next;
754
755               /* Delete neighbor entry */
756               if(tmp_link_set->neighbor->linkcount == 1)
757                 olsr_delete_neighbor_table(&tmp_link_set->neighbor->neighbor_main_addr);
758               else
759                 tmp_link_set->neighbor->linkcount--;
760
761               //olsr_delete_neighbor_if_no_link(&tmp_link_set->neighbor->neighbor_main_addr);
762               changes_neighborhood = OLSR_TRUE;
763
764               free(tmp_link_set);
765               tmp_link_set = last_link_entry;
766             }
767           else
768             {
769               link_set = tmp_link_set->next; /* CHANGED */
770
771               /* Delete neighbor entry */
772               if(tmp_link_set->neighbor->linkcount == 1)
773                 olsr_delete_neighbor_table(&tmp_link_set->neighbor->neighbor_main_addr);
774               else
775                 tmp_link_set->neighbor->linkcount--;
776
777               changes_neighborhood = OLSR_TRUE;
778
779               free(tmp_link_set);
780               tmp_link_set = link_set;
781               continue;
782             }       
783         }
784       else if((tmp_link_set->prev_status == SYM_LINK) &&
785               TIMED_OUT(tmp_link_set->SYM_time))
786         {
787           tmp_link_set->prev_status = lookup_link_status(tmp_link_set);
788           update_neighbor_status(tmp_link_set->neighbor, 
789                                  get_neighbor_status(&tmp_link_set->neighbor_iface_addr));
790           changes_neighborhood = OLSR_TRUE;
791         }
792       
793       last_link_entry = tmp_link_set;
794       tmp_link_set = tmp_link_set->next;
795     }
796
797   return;
798 }
799
800
801
802
803 /**
804  *Updates links that we have not received
805  *HELLO from in expected time according to 
806  *hysteresis.
807  *
808  *@return nada
809  */
810 static void
811 olsr_time_out_hysteresis()
812 {
813   struct link_entry *tmp_link_set;
814
815   if(link_set == NULL)
816     return;
817
818   tmp_link_set = link_set;
819
820   while(tmp_link_set)
821     {
822       if(TIMED_OUT(tmp_link_set->hello_timeout))
823         {
824           tmp_link_set->L_link_quality = olsr_hyst_calc_instability(tmp_link_set->L_link_quality);
825           OLSR_PRINTF(1, "HYST[%s] HELLO timeout %0.3f\n", olsr_ip_to_string(&tmp_link_set->neighbor_iface_addr), tmp_link_set->L_link_quality)
826           /* Update hello_timeout - NO SLACK THIS TIME */
827           tmp_link_set->hello_timeout = GET_TIMESTAMP(tmp_link_set->last_htime*1000);
828           /* Recalculate status */
829           /* Update hysteresis values */
830           olsr_process_hysteresis(tmp_link_set);
831           
832           /* update neighbor status */
833
834
835           /* Update neighbor */
836           update_neighbor_status(tmp_link_set->neighbor, 
837                                  get_neighbor_status(&tmp_link_set->neighbor_iface_addr));
838
839           /* Update seqno - not mentioned in the RFC... kind of a hack.. */
840           tmp_link_set->olsr_seqno++;
841         }
842       tmp_link_set = tmp_link_set->next;
843     }
844
845   return;
846 }
847
848 void olsr_print_link_set(void)
849 {
850   struct link_entry *walker;
851   char *fstr;
852
853   OLSR_PRINTF(1, "\n--- %02d:%02d:%02d.%02d ---------------------------------------------------- LINKS\n\n",
854               nowtm->tm_hour,
855               nowtm->tm_min,
856               nowtm->tm_sec,
857               (int)now.tv_usec/10000)
858
859   if (olsr_cnf->ip_version == AF_INET)
860   {
861     OLSR_PRINTF(1, "IP address       hyst   LQ     lost   total  NLQ    ETX\n")
862     fstr = "%-15s  %5.3f  %5.3f  %-3d    %-3d    %5.3f  %.2f\n";
863   }
864
865   else
866   {
867     OLSR_PRINTF(1, "IP address                               hyst   LQ     lost   total  NLQ    ETX\n")
868     fstr = "%-39s  %5.3f  %5.3f  %-3d    %-3d    %5.3f  %.2f\n";
869   }
870
871   for (walker = link_set; walker != NULL; walker = walker->next)
872   {
873     float etx;
874
875     if (walker->loss_link_quality < MIN_LINK_QUALITY ||
876         walker->neigh_link_quality < MIN_LINK_QUALITY)
877       etx = 0.0;
878
879     else
880       etx = 1.0 / (walker->loss_link_quality * walker->neigh_link_quality);
881
882     OLSR_PRINTF(1, fstr, olsr_ip_to_string(&walker->neighbor_iface_addr),
883                 walker->L_link_quality, walker->loss_link_quality,
884                 walker->lost_packets, walker->total_packets,
885                 walker->neigh_link_quality, etx)
886   }
887 }
888
889 static void update_packet_loss_worker(struct link_entry *entry, int lost)
890 {
891   unsigned char mask = 1 << (entry->loss_index & 7);
892   int index = entry->loss_index >> 3;
893   double rel_lq, saved_lq;
894
895   if (lost == 0)
896     {
897       // packet not lost
898
899       if ((entry->loss_bitmap[index] & mask) != 0)
900         {
901           // but the packet that we replace was lost
902           // => decrement packet loss
903
904           entry->loss_bitmap[index] &= ~mask;
905           entry->lost_packets--;
906         }
907     }
908
909   else
910     {
911       // packet lost
912
913       if ((entry->loss_bitmap[index] & mask) == 0)
914         {
915           // but the packet that we replace was not lost
916           // => increment packet loss
917
918           entry->loss_bitmap[index] |= mask;
919           entry->lost_packets++;
920         }
921     }
922
923   // move to the next packet
924
925   entry->loss_index++;
926
927   // wrap around at the end of the packet loss window
928
929   if (entry->loss_index >= entry->loss_window_size)
930     entry->loss_index = 0;
931
932   // count the total number of handled packets up to the window size
933
934   if (entry->total_packets < entry->loss_window_size)
935     entry->total_packets++;
936
937   // the current reference link quality
938
939   saved_lq = entry->saved_loss_link_quality;
940
941   if (saved_lq == 0.0)
942     saved_lq = -1.0;
943
944   // calculate the new link quality
945   //
946   // start slowly: receive the first packet => link quality = 1 / n
947   //               (n = window size)
948
949   entry->loss_link_quality =
950     (float)(entry->total_packets - entry->lost_packets) /
951     (float)(entry->loss_window_size);
952
953   // multiply the calculated link quality with the user-specified multiplier
954
955   entry->loss_link_quality *= entry->loss_link_multiplier;
956
957   // if the link quality has changed by more than 10 percent,
958   // print the new link quality table
959
960   rel_lq = entry->loss_link_quality / saved_lq;
961
962   if (rel_lq > 1.1 || rel_lq < 0.9)
963     {
964       entry->saved_loss_link_quality = entry->loss_link_quality;
965
966       changes_neighborhood = OLSR_TRUE;
967       changes_topology = OLSR_TRUE;
968
969       // create a new ANSN
970
971       // XXX - we should check whether we actually
972       // announce this neighbour
973
974       changes = OLSR_TRUE;
975     }
976 }
977
978 void olsr_update_packet_loss_hello_int(struct link_entry *entry,
979                                        double loss_hello_int)
980 {
981   // called for every LQ HELLO message - update the timeout
982   // with the htime value from the message
983
984   entry->loss_hello_int = loss_hello_int;
985 }
986
987 void olsr_update_packet_loss(union olsr_ip_addr *rem, union olsr_ip_addr *loc,
988                              olsr_u16_t seqno)
989 {
990   struct link_entry *entry;
991
992   // called for every OLSR packet
993
994   entry = lookup_link_entry(rem, loc);
995
996   // it's the very first LQ HELLO message - we do not yet have a link
997
998   if (entry == NULL)
999     return;
1000     
1001   // a) have we seen a packet before, i.e. is the sequence number valid?
1002
1003   // b) heuristically detect a restart (= sequence number reset)
1004   //    of our neighbor
1005
1006   if (entry->loss_seqno_valid != 0 && 
1007       (unsigned short)(seqno - entry->loss_seqno) < 100)
1008     {
1009       // loop through all lost packets
1010
1011       while (entry->loss_seqno != seqno)
1012         {
1013           // have we already considered all lost LQ HELLO messages?
1014
1015           if (entry->loss_missed_hellos == 0)
1016             update_packet_loss_worker(entry, 1);
1017
1018           // if not, then decrement the number of lost LQ HELLOs
1019
1020           else
1021             entry->loss_missed_hellos--;
1022
1023           entry->loss_seqno++;
1024         }
1025     }
1026
1027   // we have received a packet, otherwise this function would not
1028   // have been called
1029
1030   update_packet_loss_worker(entry, 0);
1031
1032   // (re-)initialize
1033
1034   entry->loss_missed_hellos = 0;
1035   entry->loss_seqno = seqno + 1;
1036
1037   // we now have a valid serial number for sure
1038
1039   entry->loss_seqno_valid = 1;
1040
1041   // timeout for the first lost packet is 1.5 x htime
1042
1043   entry->loss_timeout = GET_TIMESTAMP(entry->loss_hello_int * 1500.0);
1044 }
1045
1046 static void olsr_time_out_packet_loss()
1047 {
1048   struct link_entry *walker;
1049
1050   // loop through all links
1051
1052   for (walker = link_set; walker != NULL; walker = walker->next)
1053     {
1054       // find a link that has not seen any packets for a very long
1055       // time (first time: 1.5 x htime, subsequently: 1.0 x htime)
1056
1057       if (!TIMED_OUT(walker->loss_timeout))
1058         continue;
1059       
1060       // count the lost packet
1061
1062       update_packet_loss_worker(walker, 1);
1063
1064       // memorize that we've counted the packet, so that we do not
1065       // count it a second time later
1066
1067       walker->loss_missed_hellos++;
1068
1069       // next timeout in 1.0 x htime
1070
1071       walker->loss_timeout = GET_TIMESTAMP(walker->loss_hello_int * 1000.0);
1072     }
1073 }