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