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