b6f8e92a2595608ea754e1f128bdf9580b2203de
[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.19 2004/12/19 12:20:00 kattemat 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           memset(new_topo_dst, 0, sizeof(struct topo_dst));
259
260           COPY_IP(&new_topo_dst->T_dest_addr, &mprs->address);
261           olsr_get_timestamp((olsr_u32_t) msg->vtime*1000, &new_topo_dst->T_time);
262           new_topo_dst->T_seq = msg->ansn;
263
264           if (olsr_cnf->lq_level > 0)
265             {
266               new_topo_dst->link_quality = mprs->neigh_link_quality;
267               new_topo_dst->inverse_link_quality = mprs->link_quality;
268
269               new_topo_dst->saved_link_quality = new_topo_dst->link_quality;
270               new_topo_dst->saved_inverse_link_quality =
271                 new_topo_dst->inverse_link_quality;
272             }
273
274           /* Add to queue */
275           new_topo_dst->prev = &entry->destinations;
276           new_topo_dst->next = entry->destinations.next;
277           entry->destinations.next->prev = new_topo_dst;
278           entry->destinations.next = new_topo_dst;
279
280           retval = 1;
281         }
282       else
283         {
284           /* Update entry */
285           olsr_get_timestamp((olsr_u32_t) msg->vtime*1000, &existing_dst->T_time);
286           existing_dst->T_seq = msg->ansn;
287
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         }
327
328       mprs = mprs->next;
329     }
330
331   return retval;
332 }
333
334
335
336 /**
337  *Lookup a destination in a TC entry
338  *
339  *@param entry the entry to check
340  *@param dst_addr the destination address to check for
341  *
342  *@return a pointer to the topo_dst found - or NULL
343  */
344 struct topo_dst *
345 olsr_tc_lookup_dst(struct tc_entry *entry, union olsr_ip_addr *dst_addr)
346 {
347   struct topo_dst *dsts;
348   
349   //olsr_printf(1, "TC: lookup dst\n");
350
351   for(dsts = entry->destinations.next; 
352       dsts != &entry->destinations; 
353       dsts = dsts->next)
354     {
355       if(COMP_IP(dst_addr, &dsts->T_dest_addr))
356         return dsts;
357     }
358   return NULL;
359 }
360
361
362
363
364
365
366 /**
367  * Time out entries
368  *
369  *@return nada
370  */
371
372 void
373 olsr_time_out_tc_set()
374 {
375   int index, deleted;
376   struct tc_entry *entry, *entry2;
377   struct topo_dst *dst_entry, *dst_to_delete;
378
379
380   for(index=0;index<HASHSIZE;index++)
381     {
382       /* For all TC entries */
383       entry = tc_table[index].next;
384       while(entry != &tc_table[index])
385         {
386           //printf("INDEX: %d\n", index);
387           /* For all destination entries of that TC entry */
388           deleted = 0;
389           dst_entry = entry->destinations.next;
390           while(dst_entry != &entry->destinations)
391             {
392               /* If timed out - delete */
393               if(TIMED_OUT(&dst_entry->T_time))
394                 {
395                   deleted = 1;
396                   /* Dequeue */
397                   DEQUEUE_ELEM(dst_entry);
398                   //dst_entry->prev->next = dst_entry->next;
399                   //dst_entry->next->prev = dst_entry->prev;
400
401                   dst_to_delete = dst_entry;
402
403                   dst_entry = dst_entry->next;
404
405                   /* Delete */
406                   free(dst_to_delete);
407
408                   changes_topology = OLSR_TRUE;
409
410                 }
411               else
412                 dst_entry = dst_entry->next;
413             }
414           /* Delete entry if no destinations */
415           entry2 = entry;
416           entry = entry->next;
417           if(deleted)
418             olsr_tc_delete_entry_if_empty(entry2);
419         }
420     }
421
422   return;
423 }
424
425
426 /**
427  *Print the topology table to stdout
428  */
429 int
430 olsr_print_tc_table()
431 {
432   int i;
433   struct tc_entry *entry;
434   struct topo_dst *dst_entry;
435   char *fstr;
436   float etx;
437   
438   olsr_printf(1, "\n--- %02d:%02d:%02d.%02d ------------------------------------------------- TOPOLOGY\n\n",
439               nowtm->tm_hour,
440               nowtm->tm_min,
441               nowtm->tm_sec,
442               now.tv_usec / 10000);
443
444   if (olsr_cnf->ip_version == AF_INET)
445   {
446     olsr_printf(1, "Source IP addr   Dest IP addr     LQ     ILQ    ETX\n");
447     fstr = "%-15s  %-15s  %5.3f  %5.3f  %.2f\n";
448   }
449
450   else
451   {
452     olsr_printf(1, "Source IP addr                Dest IP addr                    LQ     ILQ    ETX\n");
453     fstr = "%-30s%-30s  %5.3f  %5.3f  %.2f\n";
454   }
455
456   for (i = 0; i < HASHSIZE; i++)
457   {
458     entry = tc_table[i].next;
459
460     while (entry != &tc_table[i])
461     {
462       dst_entry = entry->destinations.next;
463
464       while(dst_entry != &entry->destinations)
465       {
466         if (dst_entry->link_quality < MIN_LINK_QUALITY ||
467             dst_entry->inverse_link_quality < MIN_LINK_QUALITY)
468           etx = 0.0;
469
470         else
471           etx = 1.0 / (dst_entry->link_quality *
472                        dst_entry->inverse_link_quality);
473
474         olsr_printf(1, fstr, olsr_ip_to_string(&entry->T_last_addr),
475                     olsr_ip_to_string(&dst_entry->T_dest_addr),
476                     dst_entry->link_quality, dst_entry->inverse_link_quality,
477                     etx);
478
479         dst_entry = dst_entry->next;
480       }
481
482       entry = entry->next;
483     }
484   }
485
486   return 1;
487 }