Removed USE_LINK_QUALITY #ifdefs. The link quality code is now always
[olsrd.git] / src / tc_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: tc_set.c,v 1.17 2004/12/04 17:06:57 tlopatic Exp $
40  */
41
42
43 #include "tc_set.h"
44 #include "olsr.h"
45 #include "scheduler.h"
46 #include "lq_route.h"
47
48 /**
49  * Initialize the topology set
50  *
51  */
52
53 int
54 olsr_init_tc()
55 {
56   int index;
57   
58   /* Set timer to zero */
59   send_empty_tc.tv_sec = 0;
60   send_empty_tc.tv_usec = 0;
61
62   changes = OLSR_FALSE;
63
64   olsr_printf(5, "TC: init topo\n");
65
66   olsr_register_timeout_function(&olsr_time_out_tc_set);
67
68   for(index=0;index<HASHSIZE;index++)
69     {
70       tc_table[index].next = &tc_table[index];
71       tc_table[index].prev = &tc_table[index];
72     }
73
74   return 1;
75 }
76
77
78 /**
79  *Delete a TC entry if it has no associated
80  *destinations
81  *
82  *@param entry the TC entry to check and possibly delete
83  *
84  *@return 1 if entry deleted 0 if not
85  */
86
87 int
88 olsr_tc_delete_entry_if_empty(struct tc_entry *entry)
89 {
90
91   //olsr_printf(1, "TC: del entry if empty\n");
92
93   if(entry->destinations.next == &entry->destinations)
94     {
95       /* dequeue */
96       DEQUEUE_ELEM(entry);
97       //entry->prev->next = entry->next;
98       //entry->next->prev = entry->prev;
99       olsr_printf(1, "TC-SET: Deleting empty entry %s ->\n", olsr_ip_to_string(&entry->T_last_addr));
100       free(entry);
101       return 1;
102     }
103   return 0;
104 }
105
106
107
108 /**
109  * Look up a entry from the TC tabe based
110  * on address
111  *
112  *@param adr the address to look for
113  *
114  *@return the entry found or NULL
115  */
116
117 struct tc_entry *
118 olsr_lookup_tc_entry(union olsr_ip_addr *adr)
119 {
120   struct tc_entry *entries;
121   olsr_u32_t hash;
122
123   //olsr_printf(1, "TC: lookup entry\n");
124
125   hash = olsr_hashing(adr);
126
127   for(entries = tc_table[hash].next; 
128       entries != &tc_table[hash]; 
129       entries = entries->next)
130     {
131       //printf("TC lookup checking: %s\n", olsr_ip_to_string(&entries->T_last_addr));
132       if(COMP_IP(adr, &entries->T_last_addr))
133         return entries;
134     }
135
136   return NULL;
137 }
138
139
140 /**
141  *Add a new tc_entry to the tc set
142  *
143  *@param (last)adr address of the entry
144  *
145  *@return a pointer to the created entry
146  */
147
148 struct tc_entry *
149 olsr_add_tc_entry(union olsr_ip_addr *adr)
150 {
151   struct tc_entry *new_entry;
152   olsr_u32_t hash;
153
154   olsr_printf(1, "TC: adding entry %s\n", olsr_ip_to_string(adr));
155
156   hash = olsr_hashing(adr);
157
158   new_entry = olsr_malloc(sizeof(struct tc_entry), "New TC entry");
159
160   /* Fill entry */
161   COPY_IP(&new_entry->T_last_addr, adr);
162   new_entry->destinations.next = &new_entry->destinations;
163   new_entry->destinations.prev = &new_entry->destinations;
164
165   /* Queue entry */
166   QUEUE_ELEM(tc_table[hash], new_entry);
167   /*
168   new_entry->next = tc_table[hash].next;
169   new_entry->prev = tc_table[hash].next->prev;
170   tc_table[hash].next->prev = new_entry;
171   tc_table[hash].next = new_entry;
172   */
173
174   return new_entry;
175 }
176
177
178 /**
179  *Delete all destinations that have a
180  *lower ANSN than the one in the message
181  *
182  *@param entry the entry to delete destenations from
183  *@param msg the message to fetch the ANSN from
184  *
185  *@return 1 if any destinations were deleted 0 if not
186  */
187
188 int
189 olsr_tc_delete_mprs(struct tc_entry *entry, struct tc_message *msg)
190 {
191   struct topo_dst *tmp_dsts, *dst_to_del;
192   int retval;
193
194   //olsr_printf(5, "TC: deleting MPRS\n");
195
196   tmp_dsts = entry->destinations.next;
197   retval = 0;
198
199   while(tmp_dsts != &entry->destinations)
200     {
201       if(SEQNO_GREATER_THAN(msg->ansn, tmp_dsts->T_seq))
202         {
203           /* Delete entry */
204           dst_to_del = tmp_dsts;
205           tmp_dsts = tmp_dsts->next;
206
207           /* dequeue */
208           DEQUEUE_ELEM(dst_to_del);
209
210           free(dst_to_del);
211           retval = 1;
212         }
213       else
214         tmp_dsts = tmp_dsts->next;
215
216     }
217
218   return retval;
219 }
220
221
222 /**
223  *Update the destinations registered on an entry.
224  *Creates new dest-entries if not registered.
225  *Bases update on a receivied TC message
226  *
227  *@param entry the TC entry to check
228  *@msg the TC message to update by
229  *
230  *@return 1 if entries are added 0 if not
231  */
232
233 int
234 olsr_tc_update_mprs(struct tc_entry *entry, struct tc_message *msg)
235 {
236   struct tc_mpr_addr *mprs;
237   struct topo_dst *new_topo_dst, *existing_dst;
238   int retval;
239
240   //olsr_printf(1, "TC: update MPRS\n");
241
242   retval = 0;
243
244
245   mprs = msg->multipoint_relay_selector_address;
246   
247   /* Add all the MPRs */
248
249   while(mprs != NULL)
250     {
251       existing_dst = olsr_tc_lookup_dst(entry, &mprs->address);
252
253       if(existing_dst == NULL)
254         {
255           /* New entry */
256           new_topo_dst = olsr_malloc(sizeof(struct topo_dst), "add TC destination");
257
258           COPY_IP(&new_topo_dst->T_dest_addr, &mprs->address);
259           olsr_get_timestamp((olsr_u32_t) msg->vtime*1000, &new_topo_dst->T_time);
260           new_topo_dst->T_seq = msg->ansn;
261
262           if (olsr_cnf->lq_level > 0)
263             {
264               new_topo_dst->link_quality = mprs->neigh_link_quality;
265               new_topo_dst->inverse_link_quality = mprs->link_quality;
266
267               new_topo_dst->saved_link_quality = new_topo_dst->link_quality;
268               new_topo_dst->saved_inverse_link_quality =
269                 new_topo_dst->inverse_link_quality;
270             }
271
272           /* Add to queue */
273           new_topo_dst->prev = &entry->destinations;
274           new_topo_dst->next = entry->destinations.next;
275           entry->destinations.next->prev = new_topo_dst;
276           entry->destinations.next = new_topo_dst;
277
278           retval = 1;
279         }
280       else
281         {
282           /* Update entry */
283           olsr_get_timestamp((olsr_u32_t) msg->vtime*1000, &existing_dst->T_time);
284           existing_dst->T_seq = msg->ansn;
285
286           if (olsr_cnf->lq_level > 0)
287             {
288               double saved_lq, rel_lq;
289
290               saved_lq = existing_dst->saved_link_quality;
291
292               if (saved_lq == 0.0)
293                 saved_lq = -1.0;
294
295               existing_dst->link_quality = mprs->neigh_link_quality;
296
297               rel_lq = existing_dst->link_quality / saved_lq;
298
299               if (rel_lq > 1.1 || rel_lq < 0.9)
300                 {
301                   existing_dst->saved_link_quality =
302                     existing_dst->link_quality;
303
304                   retval = 1;
305                 }
306
307               saved_lq = existing_dst->saved_inverse_link_quality;
308
309               if (saved_lq == 0.0)
310                 saved_lq = -1.0;
311
312               existing_dst->inverse_link_quality = mprs->link_quality;
313
314               rel_lq = existing_dst->inverse_link_quality / saved_lq;
315
316               if (rel_lq > 1.1 || rel_lq < 0.9)
317                 {
318                   existing_dst->saved_inverse_link_quality =
319                     existing_dst->inverse_link_quality;
320
321                   retval = 1;
322                 }
323             }
324         }
325
326       mprs = mprs->next;
327     }
328
329   return retval;
330 }
331
332
333
334 /**
335  *Lookup a destination in a TC entry
336  *
337  *@param entry the entry to check
338  *@param dst_addr the destination address to check for
339  *
340  *@return a pointer to the topo_dst found - or NULL
341  */
342 struct topo_dst *
343 olsr_tc_lookup_dst(struct tc_entry *entry, union olsr_ip_addr *dst_addr)
344 {
345   struct topo_dst *dsts;
346   
347   //olsr_printf(1, "TC: lookup dst\n");
348
349   for(dsts = entry->destinations.next; 
350       dsts != &entry->destinations; 
351       dsts = dsts->next)
352     {
353       if(COMP_IP(dst_addr, &dsts->T_dest_addr))
354         return dsts;
355     }
356   return NULL;
357 }
358
359
360
361
362
363
364 /**
365  * Time out entries
366  *
367  *@return nada
368  */
369
370 void
371 olsr_time_out_tc_set()
372 {
373   int index, deleted;
374   struct tc_entry *entry, *entry2;
375   struct topo_dst *dst_entry, *dst_to_delete;
376
377
378   for(index=0;index<HASHSIZE;index++)
379     {
380       /* For all TC entries */
381       entry = tc_table[index].next;
382       while(entry != &tc_table[index])
383         {
384           //printf("INDEX: %d\n", index);
385           /* For all destination entries of that TC entry */
386           deleted = 0;
387           dst_entry = entry->destinations.next;
388           while(dst_entry != &entry->destinations)
389             {
390               /* If timed out - delete */
391               if(TIMED_OUT(&dst_entry->T_time))
392                 {
393                   deleted = 1;
394                   /* Dequeue */
395                   DEQUEUE_ELEM(dst_entry);
396                   //dst_entry->prev->next = dst_entry->next;
397                   //dst_entry->next->prev = dst_entry->prev;
398
399                   dst_to_delete = dst_entry;
400
401                   dst_entry = dst_entry->next;
402
403                   /* Delete */
404                   free(dst_to_delete);
405
406                   changes_topology = OLSR_TRUE;
407
408                 }
409               else
410                 dst_entry = dst_entry->next;
411             }
412           /* Delete entry if no destinations */
413           entry2 = entry;
414           entry = entry->next;
415           if(deleted)
416             olsr_tc_delete_entry_if_empty(entry2);
417         }
418     }
419
420   return;
421 }
422
423
424 /**
425  *Print the topology table to stdout
426  */
427 int
428 olsr_print_tc_table()
429 {
430   int i;
431   struct tc_entry *entry;
432   struct topo_dst *dst_entry;
433   char *fstr;
434   float etx;
435   
436   olsr_printf(2, "\n--- %02d:%02d:%02d.%02d ------------------------------------------------- TOPOLOGY\n\n",
437               nowtm->tm_hour,
438               nowtm->tm_min,
439               nowtm->tm_sec,
440               now.tv_usec / 10000);
441
442   if (olsr_cnf->ip_version == AF_INET)
443   {
444     olsr_printf(1, "Source IP addr   Dest IP addr     LQ     ILQ    ETX\n");
445     fstr = "%-15s  %-15s  %5.3f  %5.3f  %.2f\n";
446   }
447
448   else
449   {
450     olsr_printf(1, "Source IP addr                Dest IP addr                    LQ     ILQ    ETX\n");
451     fstr = "%-30s%-30s  %5.3f  %5.3f  %.2f\n";
452   }
453
454   for (i = 0; i < HASHSIZE; i++)
455   {
456     entry = tc_table[i].next;
457
458     while (entry != &tc_table[i])
459     {
460       dst_entry = entry->destinations.next;
461
462       while(dst_entry != &entry->destinations)
463       {
464         if (dst_entry->link_quality < MIN_LINK_QUALITY ||
465             dst_entry->inverse_link_quality < MIN_LINK_QUALITY)
466           etx = 0.0;
467
468         else
469           etx = 1.0 / (dst_entry->link_quality *
470                        dst_entry->inverse_link_quality);
471
472         olsr_printf(1, fstr, olsr_ip_to_string(&entry->T_last_addr),
473                     olsr_ip_to_string(&dst_entry->T_dest_addr),
474                     dst_entry->link_quality, dst_entry->inverse_link_quality,
475                     etx);
476
477         dst_entry = dst_entry->next;
478       }
479
480       entry = entry->next;
481     }
482   }
483
484   return 1;
485 }