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