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