From Sven-Ola Tuecke <sven-ola@gmx.de>: add support for fixedpoint math
[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  */
40
41
42 /*
43  * Link sensing database for the OLSR routing daemon
44  */
45
46 #include "defs.h"
47 #include "link_set.h"
48 #include "hysteresis.h"
49 #include "mid_set.h"
50 #include "mpr.h"
51 #include "neighbor_table.h"
52 #include "olsr.h"
53 #include "scheduler.h"
54 #include "lq_route.h"
55 #include "net_olsr.h"
56 #include "ipcalc.h"
57
58
59 static clock_t hold_time_neighbor;
60
61 struct link_entry *link_set;
62
63
64 static int
65 check_link_status(const struct hello_message *message, const struct interface *in_if);
66
67 static void
68 olsr_time_out_hysteresis(void);
69
70 static void olsr_time_out_packet_loss(void);
71
72 static struct link_entry *
73 add_link_entry(const union olsr_ip_addr *, const union olsr_ip_addr *, const union olsr_ip_addr *, double, double, const struct interface *);
74
75 static void
76 olsr_time_out_link_set(void);
77
78 static int
79 get_neighbor_status(const union olsr_ip_addr *);
80
81
82 clock_t 
83 get_hold_time_neighbor(void)
84 {
85   return hold_time_neighbor;
86 }
87
88 struct link_entry *
89 get_link_set(void)
90 {
91   return link_set;
92 }
93
94 void
95 olsr_init_link_set(void)
96 {
97
98   /* Timers */
99   hold_time_neighbor = (NEIGHB_HOLD_TIME*1000) / olsr_cnf->system_tick_divider;
100
101   olsr_register_timeout_function(&olsr_time_out_link_set, OLSR_TRUE);
102   if(olsr_cnf->use_hysteresis)
103     {
104       olsr_register_timeout_function(&olsr_time_out_hysteresis, OLSR_TRUE);
105     }
106
107   if (olsr_cnf->lq_level > 0)
108     {
109       olsr_register_timeout_function(&olsr_time_out_packet_loss, OLSR_TRUE);
110     }
111 }
112
113
114
115 /**
116  * Get the status of a link. The status is based upon different
117  * timeouts in the link entry.
118  *
119  *@param remote address of the remote interface
120  *
121  *@return the link status of the link
122  */
123 int
124 lookup_link_status(const struct link_entry *entry)
125 {
126
127   if(entry == NULL || link_set == NULL)
128     return UNSPEC_LINK;
129
130   /*
131    * Hysteresis
132    */
133   if(olsr_cnf->use_hysteresis)
134     {
135       /*
136         if L_LOST_LINK_time is not expired, the link is advertised
137         with a link type of LOST_LINK.
138       */
139
140       if(!TIMED_OUT(entry->L_LOST_LINK_time))
141         return LOST_LINK;
142       /*
143         otherwise, if L_LOST_LINK_time is expired and L_link_pending
144         is set to "true", the link SHOULD NOT be advertised at all;
145       */
146       if(entry->L_link_pending == 1)
147         {
148 #ifndef NODEBUG
149           struct ipaddr_str buf;
150           OLSR_PRINTF(3, "HYST[%s]: Setting to HIDE\n", olsr_ip_to_string(&buf, &entry->neighbor_iface_addr));
151 #endif
152           return HIDE_LINK;
153         }
154       /*
155         otherwise, if L_LOST_LINK_time is expired and L_link_pending
156         is set to "false", the link is advertised as described
157         previously in section 6.
158       */
159     }
160
161   if(!TIMED_OUT(entry->SYM_time))
162     return SYM_LINK;
163
164   if(!TIMED_OUT(entry->ASYM_time))
165     return ASYM_LINK;
166
167   return LOST_LINK;
168
169
170 }
171
172
173
174
175
176
177 /**
178  *Find the "best" link status to a
179  *neighbor
180  *
181  *@param address the address to check for
182  *
183  *@return SYM_LINK if a symmetric link exists 0 if not
184  */
185 static int
186 get_neighbor_status(const union olsr_ip_addr *address)
187 {
188   const union olsr_ip_addr *main_addr;
189   struct interface   *ifs;
190
191   //printf("GET_NEIGHBOR_STATUS\n");
192
193   /* Find main address */
194   if(!(main_addr = mid_lookup_main_addr(address)))
195     main_addr = address;
196
197   //printf("\tmain: %s\n", olsr_ip_to_string(main_addr));
198
199   /* Loop trough local interfaces to check all possebilities */
200   for(ifs = ifnet; ifs != NULL; ifs = ifs->int_next)
201     {
202       struct mid_address   *aliases;
203       struct link_entry  *lnk = lookup_link_entry(main_addr, NULL, ifs);
204
205       //printf("\tChecking %s->", olsr_ip_to_string(&ifs->ip_addr));
206       //printf("%s : ", olsr_ip_to_string(main_addr)); 
207       if(lnk != NULL)
208         {
209           //printf("%d\n", lookup_link_status(link));
210           if(lookup_link_status(lnk) == SYM_LINK)
211             return SYM_LINK;
212         }
213       /* Get aliases */
214       for(aliases = mid_lookup_aliases(main_addr);
215           aliases != NULL;
216           aliases = aliases->next_alias)
217         {
218           //printf("\tChecking %s->", olsr_ip_to_string(&ifs->ip_addr));
219           //printf("%s : ", olsr_ip_to_string(&aliases->address)); 
220             lnk = lookup_link_entry(&aliases->alias, NULL, ifs);
221             if(lnk != NULL)
222             {
223               //printf("%d\n", lookup_link_status(link));
224
225               if(lookup_link_status(lnk) == SYM_LINK)
226                 return SYM_LINK;
227             }
228         }
229     }
230   
231   return 0;
232 }
233
234 /**
235  * Find best link to a neighbor
236  */
237
238 struct link_entry *
239 get_best_link_to_neighbor(const union olsr_ip_addr *remote)
240 {
241   const union olsr_ip_addr *main_addr;
242   struct link_entry *walker, *good_link, *backup_link;
243   int curr_metric = MAX_IF_METRIC;
244 #ifdef USE_FPM
245   fpm curr_lq = ftofpm(-1.0);
246 #else
247   float curr_lq = -1.0;
248 #endif
249   
250   // main address lookup
251
252   main_addr = mid_lookup_main_addr(remote);
253
254   // "remote" *already is* the main address
255
256   if (main_addr == NULL)
257     main_addr = remote;
258
259   // we haven't selected any links, yet
260
261   good_link = NULL;
262   backup_link = NULL;
263
264   // loop through all links that we have
265
266   for (walker = link_set; walker != NULL; walker = walker->next)
267   {
268     // if this is not a link to the neighour in question, skip
269
270     if (!ipequal(&walker->neighbor->neighbor_main_addr, main_addr))
271       continue;
272
273     // handle the non-LQ, RFC-compliant case
274
275     if (olsr_cnf->lq_level == 0)
276     {
277       struct interface *tmp_if;
278
279       // find the interface for the link - we select the link with the
280       // best local interface metric
281       tmp_if = walker->if_name ? if_ifwithname(walker->if_name) :
282               if_ifwithaddr(&walker->local_iface_addr);
283
284       if(!tmp_if)
285         continue;
286
287       // is this interface better than anything we had before?
288
289       if ((tmp_if->int_metric < curr_metric) ||
290           // use the requested remote interface address as a tie-breaker
291           ((tmp_if->int_metric == curr_metric) && 
292            ipequal(&walker->local_iface_addr, remote)))
293       {
294         // memorize the interface's metric
295
296         curr_metric = tmp_if->int_metric;
297
298         // prefer symmetric links over asymmetric links
299
300         if (lookup_link_status(walker) == SYM_LINK)
301           good_link = walker;
302
303         else
304           backup_link = walker;
305       }
306     }
307
308     // handle the LQ, non-RFC compliant case
309
310     else
311     {
312 #ifdef USE_FPM
313       fpm tmp_lq;
314 #else
315       float tmp_lq;
316 #endif
317
318       // calculate the bi-directional link quality - we select the link
319       // with the best link quality
320
321 #ifdef USE_FPM
322       tmp_lq = fpmmul(walker->loss_link_quality, walker->neigh_link_quality);
323 #else
324       tmp_lq = walker->loss_link_quality * walker->neigh_link_quality;
325 #endif
326
327       // is this link better than anything we had before?
328               
329       if((tmp_lq > curr_lq) ||
330          // use the requested remote interface address as a tie-breaker
331          ((tmp_lq == curr_lq) && ipequal(&walker->local_iface_addr, remote)))
332       {
333         // memorize the link quality
334
335         curr_lq = tmp_lq;
336
337         // prefer symmetric links over asymmetric links
338
339         if(lookup_link_status(walker) == SYM_LINK)
340           good_link = walker;
341
342         else
343           backup_link = walker;
344       }
345     }
346   }
347
348   // if we haven't found any symmetric links, try to return an
349   // asymmetric link
350
351   return good_link ? good_link : backup_link;
352 }
353
354 static void set_loss_link_multiplier(struct link_entry *entry)
355 {
356   struct interface *inter;
357   struct olsr_if *cfg_inter;
358   struct olsr_lq_mult *mult;
359 #ifdef USE_FPM
360   fpm val = itofpm(-1);
361 #else
362   float val = -1.0;
363 #endif
364   union olsr_ip_addr null_addr;
365
366   // find the interface for the link
367
368   inter = if_ifwithaddr(&entry->local_iface_addr);
369
370   // find the interface configuration for the interface
371
372   for (cfg_inter = olsr_cnf->interfaces; cfg_inter != NULL;
373        cfg_inter = cfg_inter->next)
374     if (cfg_inter->interf == inter)
375       break;
376
377   // create a null address for comparison
378
379   memset(&null_addr, 0, sizeof (union olsr_ip_addr));
380
381   // loop through the multiplier entries
382
383   for (mult = cfg_inter->cnf->lq_mult; mult != NULL; mult = mult->next)
384   {
385     // use the default multiplier only if there isn't any entry that
386     // has a matching IP address
387
388 #ifdef USE_FPM
389     if ((ipequal(&mult->addr, &null_addr) && val < itofpm(0)) ||
390 #else
391     if ((ipequal(&mult->addr, &null_addr) && val < 0.0) ||
392 #endif
393         ipequal(&mult->addr, &entry->neighbor_iface_addr))
394 #ifdef USE_FPM
395       val = ftofpm(mult->val);
396 #else
397       val = mult->val;
398 #endif
399   }
400
401   // if we have not found an entry, then use the default multiplier
402
403 #ifdef USE_FPM
404   if (val < itofpm(0))
405     val = itofpm(1);
406 #else
407   if (val < 0)
408     val = 1.0;
409 #endif
410
411   // store the multiplier
412
413   entry->loss_link_multiplier = val;
414 }
415
416 /**
417  *Delete all interface link entries
418  *
419  *@param interface ip address
420  */
421
422 void
423 del_if_link_entries(const union olsr_ip_addr *int_addr)
424 {
425   struct link_entry *tmp_link_set, *last_link_entry;
426
427   if(link_set == NULL)
428     return;
429
430   tmp_link_set = link_set;
431   last_link_entry = NULL;
432
433   while(tmp_link_set)
434     {
435
436       if(ipequal(int_addr, &tmp_link_set->local_iface_addr))
437         {
438           if(last_link_entry != NULL)
439             {
440               last_link_entry->next = tmp_link_set->next;
441
442               /* Delete neighbor entry */
443               if(tmp_link_set->neighbor->linkcount == 1)
444                 olsr_delete_neighbor_table(&tmp_link_set->neighbor->neighbor_main_addr);
445               else
446                 tmp_link_set->neighbor->linkcount--;
447
448               //olsr_delete_neighbor_if_no_link(&tmp_link_set->neighbor->neighbor_main_addr);
449               changes_neighborhood = OLSR_TRUE;
450
451               free(tmp_link_set);
452               tmp_link_set = last_link_entry;
453             }
454           else
455             {
456               link_set = tmp_link_set->next; /* CHANGED */
457
458               /* Delete neighbor entry */
459               if(tmp_link_set->neighbor->linkcount == 1)
460                 olsr_delete_neighbor_table(&tmp_link_set->neighbor->neighbor_main_addr);
461               else
462                 tmp_link_set->neighbor->linkcount--;
463
464               changes_neighborhood = OLSR_TRUE;
465
466               free(tmp_link_set);
467               tmp_link_set = link_set;
468               continue;
469             }
470         }
471
472       last_link_entry = tmp_link_set;
473       tmp_link_set = tmp_link_set->next;
474     }
475
476   return;
477 }
478
479 /**
480  *Nothing mysterious here.
481  *Adding a new link entry to the link set.
482  *
483  *@param local the local IP address
484  *@param remote the remote IP address
485  *@param remote_main the remote nodes main address
486  *@param vtime the validity time of the entry
487  *@param htime the HELLO interval of the remote node
488  *@param local_if the local interface
489  */
490
491 static struct link_entry *
492 add_link_entry(const union olsr_ip_addr *local,
493                const union olsr_ip_addr *remote,
494                const union olsr_ip_addr *remote_main,
495                double vtime,
496                double htime,
497                const struct interface *local_if)
498 {
499   struct link_entry *new_link;
500   struct neighbor_entry *neighbor;
501   struct link_entry *tmp_link_set = lookup_link_entry(remote, remote_main, local_if);
502   if (tmp_link_set) {
503     return tmp_link_set;
504   }
505   /*
506    * if there exists no link tuple with
507    * L_neighbor_iface_addr == Source Address
508    */
509
510 #ifdef DEBUG
511   {
512 #ifndef NODEBUG
513     struct ipaddr_str localbuf, rembuf;
514 #endif
515     OLSR_PRINTF(1, "Adding %s=>%s to link set\n", olsr_ip_to_string(&localbuf, local), olsr_ip_to_string(&rembuf, remote));
516   }
517 #endif
518
519   /* a new tuple is created with... */
520
521   new_link = olsr_malloc(sizeof(struct link_entry), "new link entry");
522
523   memset(new_link, 0 , sizeof(struct link_entry));
524   
525   /* copy if_name, if it is defined */
526   if (local_if->int_name)
527     {
528       new_link->if_name = olsr_malloc(strlen(local_if->int_name)+1, "target of if_name in new link entry");
529       strcpy(new_link->if_name, local_if->int_name);
530     } else 
531       new_link->if_name = NULL;
532
533   /* shortcut to interface. XXX refcount */
534   new_link->inter = local_if;
535
536   /*
537    * L_local_iface_addr = Address of the interface
538    * which received the HELLO message
539    */
540   //printf("\tLocal IF: %s\n", olsr_ip_to_string(local));
541   new_link->local_iface_addr = *local;
542   /* L_neighbor_iface_addr = Source Address */
543   new_link->neighbor_iface_addr = *remote;
544
545   /* L_SYM_time            = current time - 1 (expired) */
546   new_link->SYM_time = now_times - 1;
547
548   /* L_time = current time + validity time */
549   new_link->time = GET_TIMESTAMP(vtime*1000);
550
551   new_link->prev_status = ASYM_LINK;
552
553   /* HYSTERESIS */
554   if(olsr_cnf->use_hysteresis)
555     {
556       new_link->L_link_pending = 1;
557       new_link->L_LOST_LINK_time = GET_TIMESTAMP(vtime*1000);
558       new_link->hello_timeout = GET_TIMESTAMP(htime*1500);
559       new_link->last_htime = htime;
560       new_link->olsr_seqno = 0;
561       new_link->olsr_seqno_valid = OLSR_FALSE;
562     }
563
564 #ifdef USE_FPM
565   new_link->L_link_quality = itofpm(0);
566 #else
567   new_link->L_link_quality = 0.0;
568 #endif
569
570   if (olsr_cnf->lq_level > 0)
571     {
572       new_link->loss_hello_int = htime;
573
574       new_link->loss_timeout = GET_TIMESTAMP(htime * 1500.0);
575
576       new_link->loss_seqno = 0;
577       new_link->loss_seqno_valid = 0;
578       new_link->loss_missed_hellos = 0;
579
580       new_link->lost_packets = 0;
581       new_link->total_packets = 0;
582
583       new_link->loss_index = 0;
584
585       memset(new_link->loss_bitmap, 0, sizeof (new_link->loss_bitmap));
586
587       set_loss_link_multiplier(new_link);
588     }
589
590 #ifdef USE_FPM
591   new_link->loss_link_quality = itofpm(0);
592   new_link->neigh_link_quality = itofpm(0);
593
594   new_link->loss_link_quality2 = itofpm(0);
595   new_link->neigh_link_quality2 = itofpm(0);
596
597   new_link->saved_loss_link_quality = itofpm(0);
598   new_link->saved_neigh_link_quality = itofpm(0);
599 #else
600   new_link->loss_link_quality = 0.0;
601   new_link->neigh_link_quality = 0.0;
602
603   new_link->loss_link_quality2 = 0.0;
604   new_link->neigh_link_quality2 = 0.0;
605
606   new_link->saved_loss_link_quality = 0.0;
607   new_link->saved_neigh_link_quality = 0.0;
608 #endif
609
610   /* Add to queue */
611   new_link->next = link_set;
612   link_set = new_link;
613
614
615   /*
616    * Create the neighbor entry
617    */
618
619   /* Neighbor MUST exist! */
620   neighbor = olsr_lookup_neighbor_table(remote_main);
621   if(neighbor == NULL)
622     {
623 #ifdef DEBUG
624 #ifndef NODEBUG
625       struct ipaddr_str buf;
626 #endif
627       OLSR_PRINTF(3, "ADDING NEW NEIGHBOR ENTRY %s FROM LINK SET\n", olsr_ip_to_string(&buf, remote_main));
628 #endif
629       neighbor = olsr_insert_neighbor_table(remote_main);
630     }
631
632   neighbor->linkcount++;
633   new_link->neighbor = neighbor;
634   if(!ipequal(remote, remote_main))
635     {
636       /* Add MID alias if not already registered */
637       /* This is kind of sketchy... and not specified
638        * in the RFC. We can only guess a vtime.
639        * We'll go for one that is hopefully long
640        * enough in most cases. 10 seconds
641        */
642
643     /* Erik Tromp - commented out. It is not RFC-compliant. Also, MID aliases
644      * that are not explicitly declared by a node will be removed as soon as
645      * the olsr_prune_aliases(...) function is called.
646      *
647      * OLSR_PRINTF(1, "Adding MID alias main %s ", olsr_ip_to_string(remote_main));
648      * OLSR_PRINTF(1, "-> %s based on HELLO\n\n", olsr_ip_to_string(remote));
649      * insert_mid_alias(remote_main, remote, MID_ALIAS_HACK_VTIME);
650      */
651     }
652
653   return link_set;
654 }
655
656
657 /**
658  *Lookup the status of a link.
659  *
660  *@param int_addr address of the remote interface
661  *
662  *@return 1 of the link is symmertic 0 if not
663  */
664
665 int
666 check_neighbor_link(const union olsr_ip_addr *int_addr)
667 {
668   struct link_entry *tmp_link_set;
669
670   tmp_link_set = link_set;
671
672   while(tmp_link_set)
673     {
674       if(ipequal(int_addr, &tmp_link_set->neighbor_iface_addr))
675         return lookup_link_status(tmp_link_set);
676       tmp_link_set = tmp_link_set->next;
677     }
678   return UNSPEC_LINK;
679 }
680
681
682 /**
683  *Lookup a link entry
684  *
685  *@param remote the remote interface address
686  *@param remote_main the remote nodes main address
687  *@param local the local interface address
688  *
689  *@return the link entry if found, NULL if not
690  */
691 struct link_entry *
692 lookup_link_entry(const union olsr_ip_addr *remote, const union olsr_ip_addr *remote_main, const struct interface *local)
693 {
694   struct link_entry *tmp_link_set;
695
696   tmp_link_set = link_set;
697
698   while(tmp_link_set)
699     {
700       if(ipequal(remote, &tmp_link_set->neighbor_iface_addr) &&
701          (tmp_link_set->if_name
702           ? !strcmp(tmp_link_set->if_name, local->int_name)
703           : ipequal(&local->ip_addr, &tmp_link_set->local_iface_addr)
704           ) &&
705          /* check the remote-main address only if there is one given */
706          (remote_main == NULL || ipequal(remote_main, &tmp_link_set->neighbor->neighbor_main_addr))
707          )
708         return tmp_link_set;
709       tmp_link_set = tmp_link_set->next;
710     }
711   return NULL;
712
713 }
714
715
716
717
718
719
720
721 /**
722  *Update a link entry. This is the "main entrypoint" in
723  *the link-sensing. This function is called from the HELLO
724  *parser function.
725  *It makes sure a entry is updated or created.
726  *
727  *@param local the local IP address
728  *@param remote the remote IP address
729  *@param message the HELLO message
730  *@param in_if the interface on which this HELLO was received
731  *
732  *@return the link_entry struct describing this link entry
733  */
734 struct link_entry *
735 update_link_entry(const union olsr_ip_addr *local, 
736                   const union olsr_ip_addr *remote, 
737                   const struct hello_message *message, 
738                   const struct interface *in_if)
739 {
740   struct link_entry *entry;
741
742   /* Add if not registered */
743   entry = add_link_entry(local, remote, &message->source_addr, message->vtime, message->htime, in_if);
744
745   /* Update ASYM_time */
746   //printf("Vtime is %f\n", message->vtime);
747   /* L_ASYM_time = current time + validity time */
748   entry->vtime = message->vtime;
749   entry->ASYM_time = GET_TIMESTAMP(message->vtime*1000);
750   
751   entry->prev_status = check_link_status(message, in_if);
752   
753   //printf("Status %d\n", status);
754   
755   switch(entry->prev_status)
756     {
757     case(LOST_LINK):
758       /* L_SYM_time = current time - 1 (i.e., expired) */
759       entry->SYM_time = now_times - 1;
760
761       break;
762     case(SYM_LINK):
763     case(ASYM_LINK):
764       /* L_SYM_time = current time + validity time */
765       //printf("updating SYM time for %s\n", olsr_ip_to_string(remote));
766       entry->SYM_time = GET_TIMESTAMP(message->vtime*1000);
767
768       /* L_time = L_SYM_time + NEIGHB_HOLD_TIME */
769       entry->time = entry->SYM_time + hold_time_neighbor;
770
771       break;
772     default:;
773     }
774
775   /* L_time = max(L_time, L_ASYM_time) */
776   if(entry->time < entry->ASYM_time)
777     entry->time = entry->ASYM_time;
778
779
780   /*
781   printf("Updating link LOCAL: %s ", olsr_ip_to_string(local));
782   printf("REMOTE: %s\n", olsr_ip_to_string(remote));
783   printf("VTIME: %f ", message->vtime);
784   printf("STATUS: %d\n", status);
785   */
786
787   /* Update hysteresis values */
788   if(olsr_cnf->use_hysteresis)
789     olsr_process_hysteresis(entry);
790
791   /* Update neighbor */
792   update_neighbor_status(entry->neighbor, get_neighbor_status(remote));
793
794   return entry;  
795 }
796
797
798 /**
799  * Fuction that updates all registered pointers to
800  * one neighbor entry with another pointer
801  * Used by MID updates.
802  *
803  *@old the pointer to replace
804  *@new the pointer to use instead of "old"
805  *
806  *@return the number of entries updated
807  */
808 int
809 replace_neighbor_link_set(const struct neighbor_entry *old,
810                           struct neighbor_entry *new)
811 {
812   struct link_entry *tmp_link_set;
813   int retval;
814
815   retval = 0;
816
817   if(link_set == NULL)
818     return retval;
819       
820   tmp_link_set = link_set;
821
822   while(tmp_link_set)
823     {
824
825       if(tmp_link_set->neighbor == old)
826         {
827           tmp_link_set->neighbor = new;
828           retval++;
829         }
830       tmp_link_set = tmp_link_set->next;
831     }
832
833   return retval;
834
835 }
836
837
838 /**
839  *Checks the link status to a neighbor by
840  *looking in a received HELLO message.
841  *
842  *@param message the HELLO message to check
843  *
844  *@return the link status
845  */
846 static int
847 check_link_status(const struct hello_message *message, const struct interface *in_if)
848 {
849   int ret = UNSPEC_LINK;
850   struct hello_neighbor  *neighbors;
851
852   neighbors = message->neighbors;
853   
854   while(neighbors!=NULL)
855     {
856       /*
857        * Note: If a neigh has 2 cards we can reach, the neigh
858        * will send a Hello with the same IP mentined twice
859        */
860       if(ipequal(&neighbors->address, &in_if->ip_addr))
861         {
862           //printf("ok");
863           ret = neighbors->link;
864           if (SYM_LINK == ret) break;
865         }
866
867       neighbors = neighbors->next; 
868     }
869
870
871   return ret;
872 }
873
874
875 /**
876  *Time out the link set. In other words, the link
877  *set is traversed and all non-valid entries are
878  *deleted.
879  *
880  */
881 static void
882 olsr_time_out_link_set(void)
883 {
884
885   struct link_entry *tmp_link_set, *last_link_entry;
886
887   if(link_set == NULL)
888     return;
889       
890   tmp_link_set = link_set;
891   last_link_entry = NULL;
892
893   while(tmp_link_set)
894     {
895
896       if(TIMED_OUT(tmp_link_set->time))
897         {
898           if(last_link_entry != NULL)
899             {
900               last_link_entry->next = tmp_link_set->next;
901
902               /* Delete neighbor entry */
903               if(tmp_link_set->neighbor->linkcount == 1)
904                 olsr_delete_neighbor_table(&tmp_link_set->neighbor->neighbor_main_addr);
905               else
906                 tmp_link_set->neighbor->linkcount--;
907
908               //olsr_delete_neighbor_if_no_link(&tmp_link_set->neighbor->neighbor_main_addr);
909               changes_neighborhood = OLSR_TRUE;
910               free(tmp_link_set->if_name);
911               free(tmp_link_set);
912               tmp_link_set = last_link_entry;
913             }
914           else
915             {
916               link_set = tmp_link_set->next; /* CHANGED */
917
918               /* Delete neighbor entry */
919               if(tmp_link_set->neighbor->linkcount == 1)
920                 olsr_delete_neighbor_table(&tmp_link_set->neighbor->neighbor_main_addr);
921               else
922                 tmp_link_set->neighbor->linkcount--;
923
924               changes_neighborhood = OLSR_TRUE;
925
926               free(tmp_link_set->if_name);
927               free(tmp_link_set);
928               tmp_link_set = link_set;
929               continue;
930             }       
931         }
932       else if((tmp_link_set->prev_status == SYM_LINK) &&
933               TIMED_OUT(tmp_link_set->SYM_time))
934         {
935           tmp_link_set->prev_status = lookup_link_status(tmp_link_set);
936           update_neighbor_status(tmp_link_set->neighbor, 
937                                  get_neighbor_status(&tmp_link_set->neighbor_iface_addr));
938           changes_neighborhood = OLSR_TRUE;
939         }
940       
941       last_link_entry = tmp_link_set;
942       tmp_link_set = tmp_link_set->next;
943     }
944
945   return;
946 }
947
948
949
950
951 /**
952  *Updates links that we have not received
953  *HELLO from in expected time according to 
954  *hysteresis.
955  *
956  *@return nada
957  */
958 static void
959 olsr_time_out_hysteresis(void)
960 {
961   struct link_entry *tmp_link_set;
962
963   if(link_set == NULL)
964     return;
965
966   tmp_link_set = link_set;
967
968   while(tmp_link_set)
969     {
970       if(TIMED_OUT(tmp_link_set->hello_timeout))
971         {
972 #ifndef NODEBUG
973           struct ipaddr_str buf;
974 #endif
975           tmp_link_set->L_link_quality = olsr_hyst_calc_instability(tmp_link_set->L_link_quality);
976           OLSR_PRINTF(1, "HYST[%s] HELLO timeout %s\n",
977                       olsr_ip_to_string(&buf, &tmp_link_set->neighbor_iface_addr),
978                       olsr_etx_to_string(tmp_link_set->L_link_quality));
979           /* Update hello_timeout - NO SLACK THIS TIME */
980           tmp_link_set->hello_timeout = GET_TIMESTAMP(tmp_link_set->last_htime*1000);
981           /* Recalculate status */
982           /* Update hysteresis values */
983           olsr_process_hysteresis(tmp_link_set);
984           
985           /* update neighbor status */
986
987
988           /* Update neighbor */
989           update_neighbor_status(tmp_link_set->neighbor, 
990                                  get_neighbor_status(&tmp_link_set->neighbor_iface_addr));
991
992           /* Update seqno - not mentioned in the RFC... kind of a hack.. */
993           tmp_link_set->olsr_seqno++;
994         }
995       tmp_link_set = tmp_link_set->next;
996     }
997
998   return;
999 }
1000
1001 void olsr_print_link_set(void)
1002 {
1003 #ifndef NODEBUG
1004   /* The whole function makes no sense without it. */
1005   struct link_entry *walker;
1006   const int addrsize = olsr_cnf->ip_version == AF_INET ? 15 : 39;
1007
1008   OLSR_PRINTF(0, "\n--- %02d:%02d:%02d.%02d ---------------------------------------------------- LINKS\n\n",
1009               nowtm->tm_hour,
1010               nowtm->tm_min,
1011               nowtm->tm_sec,
1012               (int)now.tv_usec/10000U);
1013   OLSR_PRINTF(1, "%-*s  %-6s %-6s %-6s %-6s %-6s %s\n", addrsize, "IP address", "hyst", "LQ", "lost", "total","NLQ", "ETX");
1014
1015   for (walker = link_set; walker != NULL; walker = walker->next)
1016   {
1017     struct ipaddr_str buf;
1018 #ifdef USE_FPM
1019     fpm etx;
1020
1021     if (walker->loss_link_quality < MIN_LINK_QUALITY || walker->neigh_link_quality < MIN_LINK_QUALITY)
1022       etx = itofpm(0);
1023     else
1024       etx = fpmdiv(itofpm(1), fpmmul(walker->loss_link_quality, walker->neigh_link_quality));
1025 #else
1026     float etx;
1027
1028     if (walker->loss_link_quality < MIN_LINK_QUALITY || walker->neigh_link_quality < MIN_LINK_QUALITY)
1029       etx = 0.0;
1030     else
1031       etx = 1.0 / (walker->loss_link_quality * walker->neigh_link_quality);
1032 #endif
1033
1034     OLSR_PRINTF(1, "%-*s  %s  %s  %-3d    %-3d    %s  %s\n",
1035                 addrsize, olsr_ip_to_string(&buf, &walker->neighbor_iface_addr),
1036                 olsr_etx_to_string(walker->L_link_quality),
1037                 olsr_etx_to_string(walker->loss_link_quality),
1038                 walker->lost_packets,
1039                 walker->total_packets,
1040                 olsr_etx_to_string(walker->neigh_link_quality),
1041                 olsr_etx_to_string(etx));
1042   }
1043 #endif
1044 }
1045
1046 static void update_packet_loss_worker(struct link_entry *entry, int lost)
1047 {
1048   unsigned char mask = 1 << (entry->loss_index & 7);
1049   const int idx = entry->loss_index >> 3;
1050 #ifdef USE_FPM
1051   fpm rel_lq, saved_lq;
1052 #else
1053   double rel_lq, saved_lq;
1054 #endif
1055
1056   if (lost == 0)
1057     {
1058       // packet not lost
1059
1060       if ((entry->loss_bitmap[idx] & mask) != 0)
1061         {
1062           // but the packet that we replace was lost
1063           // => decrement packet loss
1064
1065           entry->loss_bitmap[idx] &= ~mask;
1066           entry->lost_packets--;
1067         }
1068     }
1069
1070   else
1071     {
1072       // packet lost
1073
1074       if ((entry->loss_bitmap[idx] & mask) == 0)
1075         {
1076           // but the packet that we replace was not lost
1077           // => increment packet loss
1078
1079           entry->loss_bitmap[idx] |= mask;
1080           entry->lost_packets++;
1081         }
1082     }
1083
1084   // move to the next packet
1085
1086   entry->loss_index++;
1087
1088   // wrap around at the end of the packet loss window
1089
1090   if (entry->loss_index >= olsr_cnf->lq_wsize)
1091     entry->loss_index = 0;
1092
1093   // count the total number of handled packets up to the window size
1094
1095   if (entry->total_packets < olsr_cnf->lq_wsize)
1096     entry->total_packets++;
1097
1098   // the current reference link quality
1099
1100   saved_lq = entry->saved_loss_link_quality;
1101
1102 #ifdef USE_FPM
1103   if (saved_lq == itofpm(0))
1104     saved_lq = itofpm(-1);
1105 #else
1106   if (saved_lq == 0.0)
1107     saved_lq = -1.0;
1108 #endif
1109
1110   // calculate the new link quality
1111   //
1112   // start slowly: receive the first packet => link quality = 1 / n
1113   //               (n = window size)
1114 #ifdef USE_FPM
1115   entry->loss_link_quality = fpmdiv(
1116     itofpm(entry->total_packets - entry->lost_packets),
1117     olsr_cnf->lq_wsize < (2 * 4) ? itofpm(olsr_cnf->lq_wsize):
1118     fpmidiv(fpmimul(4,fpmadd(fpmmuli(fpmsub(fpmidiv(itofpm(olsr_cnf->lq_wsize),4),
1119                                             itofpm(1)),(int)entry->total_packets),
1120                              itofpm(olsr_cnf->lq_wsize))),
1121             (olsr_32_t)olsr_cnf->lq_wsize));
1122 #else
1123   entry->loss_link_quality =
1124     (float)(entry->total_packets - entry->lost_packets) /
1125     (float)(olsr_cnf->lq_wsize < (2 * 4) ? olsr_cnf->lq_wsize: 
1126     4 * (((float)olsr_cnf->lq_wsize / 4 - 1) * entry->total_packets + olsr_cnf->lq_wsize) / olsr_cnf->lq_wsize);
1127 #endif
1128     
1129   // multiply the calculated link quality with the user-specified multiplier
1130
1131 #ifdef USE_FPM
1132   entry->loss_link_quality = fpmmul(entry->loss_link_quality, entry->loss_link_multiplier);
1133 #else
1134   entry->loss_link_quality *= entry->loss_link_multiplier;
1135 #endif
1136
1137   // if the link quality has changed by more than 10 percent,
1138   // print the new link quality table
1139
1140 #ifdef USE_FPM
1141   rel_lq = fpmdiv(entry->loss_link_quality, saved_lq);
1142 #else
1143   rel_lq = entry->loss_link_quality / saved_lq;
1144 #endif
1145
1146   if (rel_lq > CEIL_LQDIFF || rel_lq < FLOOR_LQDIFF)
1147     {
1148       entry->saved_loss_link_quality = entry->loss_link_quality;
1149
1150       if (olsr_cnf->lq_dlimit > 0)
1151       {
1152         changes_neighborhood = OLSR_TRUE;
1153         changes_topology = OLSR_TRUE;
1154       }
1155
1156       else
1157         OLSR_PRINTF(3, "Skipping Dijkstra (1)\n");
1158
1159       // create a new ANSN
1160
1161       // XXX - we should check whether we actually
1162       // announce this neighbour
1163
1164       signal_link_changes(OLSR_TRUE);
1165     }
1166 }
1167
1168 void olsr_update_packet_loss_hello_int(struct link_entry *entry,
1169                                        double loss_hello_int)
1170 {
1171   // called for every LQ HELLO message - update the timeout
1172   // with the htime value from the message
1173
1174   entry->loss_hello_int = loss_hello_int;
1175 }
1176
1177 void olsr_update_packet_loss(const union olsr_ip_addr *rem, const struct interface *loc,
1178                              olsr_u16_t seqno)
1179 {
1180   struct link_entry *entry;
1181
1182   // called for every OLSR packet
1183
1184   entry = lookup_link_entry(rem, NULL, loc);
1185
1186   // it's the very first LQ HELLO message - we do not yet have a link
1187
1188   if (entry == NULL)
1189     return;
1190     
1191   // a) have we seen a packet before, i.e. is the sequence number valid?
1192
1193   // b) heuristically detect a restart (= sequence number reset)
1194   //    of our neighbor
1195
1196   if (entry->loss_seqno_valid != 0 && 
1197       (unsigned short)(seqno - entry->loss_seqno) < 100)
1198     {
1199       // loop through all lost packets
1200
1201       while (entry->loss_seqno != seqno)
1202         {
1203           // have we already considered all lost LQ HELLO messages?
1204
1205           if (entry->loss_missed_hellos == 0)
1206             update_packet_loss_worker(entry, 1);
1207
1208           // if not, then decrement the number of lost LQ HELLOs
1209
1210           else
1211             entry->loss_missed_hellos--;
1212
1213           entry->loss_seqno++;
1214         }
1215     }
1216
1217   // we have received a packet, otherwise this function would not
1218   // have been called
1219
1220   update_packet_loss_worker(entry, 0);
1221
1222   // (re-)initialize
1223
1224   entry->loss_missed_hellos = 0;
1225   entry->loss_seqno = seqno + 1;
1226
1227   // we now have a valid serial number for sure
1228
1229   entry->loss_seqno_valid = 1;
1230
1231   // timeout for the first lost packet is 1.5 x htime
1232
1233   entry->loss_timeout = GET_TIMESTAMP(entry->loss_hello_int * 1500.0);
1234 }
1235
1236 static void olsr_time_out_packet_loss(void)
1237 {
1238   struct link_entry *walker;
1239
1240   // loop through all links
1241
1242   for (walker = link_set; walker != NULL; walker = walker->next)
1243     {
1244       // find a link that has not seen any packets for a very long
1245       // time (first time: 1.5 x htime, subsequently: 1.0 x htime)
1246
1247       if (!TIMED_OUT(walker->loss_timeout))
1248         continue;
1249       
1250       // count the lost packet
1251
1252       update_packet_loss_worker(walker, 1);
1253
1254       // memorize that we've counted the packet, so that we do not
1255       // count it a second time later
1256
1257       walker->loss_missed_hellos++;
1258
1259       // next timeout in 1.0 x htime
1260
1261       walker->loss_timeout = GET_TIMESTAMP(walker->loss_hello_int * 1000.0);
1262     }
1263 }
1264
1265 void olsr_update_dijkstra_link_qualities(void)
1266 {
1267   struct link_entry *walker;
1268
1269   for (walker = link_set; walker != NULL; walker = walker->next)
1270   {
1271     walker->loss_link_quality2 = walker->loss_link_quality;
1272     walker->neigh_link_quality2 = walker->neigh_link_quality;
1273   }
1274 }
1275
1276 #ifdef USE_FPM
1277 fpm
1278 #else
1279 float
1280 #endif
1281 olsr_calc_link_etx(const struct link_entry *link)
1282 {
1283   return link->loss_link_quality < MIN_LINK_QUALITY ||
1284          link->neigh_link_quality < MIN_LINK_QUALITY
1285 #ifdef USE_FPM
1286              ? itofpm(0)
1287              : fpmdiv(itofpm(1), fpmmul(link->loss_link_quality, link->neigh_link_quality));
1288 #else
1289              ? 0.0
1290              : 1.0 / (link->loss_link_quality * link->neigh_link_quality);
1291 #endif
1292 }