General cleanups in header files
[olsrd.git] / src / duplicate_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: duplicate_set.c,v 1.10 2005/02/20 18:52:18 kattemat Exp $
40  */
41
42
43
44 #include "defs.h"
45 #include "duplicate_set.h"
46 #include "olsr.h"
47 #include "scheduler.h"
48
49 /* The duplicate table */
50 static struct dup_entry dup_set[HASHSIZE];
51
52 static float dup_hold_time = DUP_HOLD_TIME;
53
54 /**
55  *Initialize the duplicate table entrys
56  *
57  *@return nada
58  */
59 void
60 olsr_init_duplicate_table()
61 {
62   int i;
63
64   olsr_printf(3, "Initializing duplicatetable - hashsize %d\n", HASHSIZE);
65
66   /* Since the holdingtime is rather large for duplicate
67    * entries the timeoutfunction is only ran every 2 seconds
68    */
69   olsr_register_scheduler_event(&olsr_time_out_duplicate_table, NULL, 2, 0, NULL);
70   
71   for(i = 0; i < HASHSIZE; i++)
72     {
73       dup_set[i].next = &dup_set[i];
74       dup_set[i].prev = &dup_set[i];
75     }
76 }
77
78
79 /**
80  *Add an entry to the duplicate set. The set is not checked
81  *for duplicate entries.
82  *
83  *@param originator IP address of the sender of the message
84  *@param seqno seqno of the message
85  *
86  *@return positive on success
87  */
88 struct dup_entry *
89 olsr_add_dup_entry(union olsr_ip_addr *originator, olsr_u16_t seqno)
90 {
91   olsr_u32_t hash;
92   struct dup_entry *new_dup_entry;
93
94
95   /* Hash the senders address */
96   hash = olsr_hashing(originator);
97
98   new_dup_entry = olsr_malloc(sizeof(struct dup_entry), "New dup entry");
99
100   /* Address */
101   COPY_IP(&new_dup_entry->addr, originator);
102   /* Seqno */
103   new_dup_entry->seqno = seqno;
104   /* Set timer */
105   new_dup_entry->timer = GET_TIMESTAMP(dup_hold_time*1000);
106   /* Interfaces */
107   new_dup_entry->ifaces = NULL;
108   /* Forwarded */
109   new_dup_entry->forwarded = 0;
110
111   /* Insert into set */
112   QUEUE_ELEM(dup_set[hash], new_dup_entry);
113   /*
114   dup_set[hash].next->prev = new_dup_entry;
115   new_dup_entry->next = dup_set[hash].next;
116   dup_set[hash].next = new_dup_entry;
117   new_dup_entry->prev = &dup_set[hash];
118   */
119   return new_dup_entry;
120 }
121
122
123 /**
124  * Check wether or not a message should be processed
125  *
126  */
127 int
128 olsr_check_dup_table_proc(union olsr_ip_addr *originator, olsr_u16_t seqno)
129 {
130   olsr_u32_t hash;
131   struct dup_entry *tmp_dup_table;
132
133   /* Hash the senders address */
134   hash = olsr_hashing(originator);
135
136   /* Check for entry */
137   for(tmp_dup_table = dup_set[hash].next;
138       tmp_dup_table != &dup_set[hash];
139       tmp_dup_table = tmp_dup_table->next)
140     {
141       if(COMP_IP(&tmp_dup_table->addr, originator) &&
142          (tmp_dup_table->seqno == seqno))
143         {
144           return 0;
145         }
146     }
147
148   return 1;
149 }
150
151
152
153 /**
154  * Check wether or not a message should be forwarded
155  *
156  */
157 int
158 olsr_check_dup_table_fwd(union olsr_ip_addr *originator, 
159                      olsr_u16_t seqno,
160                      union olsr_ip_addr *int_addr)
161 {
162   olsr_u32_t hash;
163   struct dup_entry *tmp_dup_table;
164
165   /* Hash the senders address */
166   hash = olsr_hashing(originator);
167
168   /* Check for entry */
169   for(tmp_dup_table = dup_set[hash].next;
170       tmp_dup_table != &dup_set[hash];
171       tmp_dup_table = tmp_dup_table->next)
172     {
173       if(COMP_IP(&tmp_dup_table->addr, originator) &&
174          (tmp_dup_table->seqno == seqno))
175         {
176           struct dup_iface *tmp_dup_iface;
177           /* Check retransmitted */
178           if(tmp_dup_table->forwarded)
179             return 0;
180           /* Check for interface */
181           tmp_dup_iface = tmp_dup_table->ifaces;
182           while(tmp_dup_iface)
183             {
184               if(COMP_IP(&tmp_dup_iface->addr, int_addr))
185                 return 0;
186               
187               tmp_dup_iface = tmp_dup_iface->next;
188             }
189         }
190     }
191   
192
193   return 1;
194 }
195
196
197
198
199 /**
200  *Delete and dequeue a duplicate entry
201  *
202  *@param entry the entry to delete
203  *
204  */
205 void
206 olsr_del_dup_entry(struct dup_entry *entry)
207 {
208   struct dup_iface *tmp_iface, *del_iface;
209
210   tmp_iface = entry->ifaces;
211
212   /* Free interfaces */
213   while(tmp_iface)
214     {
215       del_iface = tmp_iface;
216       tmp_iface = tmp_iface->next;
217       free(del_iface);
218     }
219
220   /* Dequeue */
221   DEQUEUE_ELEM(entry);
222   free(entry);
223 }
224
225
226
227 void
228 olsr_time_out_duplicate_table(void *foo)
229 {
230   int i;
231
232   for(i = 0; i < HASHSIZE; i++)
233     {      
234       struct dup_entry *tmp_dup_table;
235       tmp_dup_table = dup_set[i].next;
236
237       while(tmp_dup_table != &dup_set[i])
238         {
239           if(TIMED_OUT(tmp_dup_table->timer))
240             {
241               struct dup_entry *entry_to_delete = tmp_dup_table;
242 #ifdef DEBUG
243               olsr_printf(5, "DUP TIMEOUT[%s] s: %d\n", 
244                           olsr_ip_to_string(&tmp_dup_table->addr),
245                           tmp_dup_table->seqno);
246 #endif
247               tmp_dup_table = tmp_dup_table->next;
248               olsr_del_dup_entry(entry_to_delete);
249             }
250           else
251             {
252               tmp_dup_table = tmp_dup_table->next;
253             }
254         }
255     }
256 }
257
258
259
260
261 int
262 olsr_update_dup_entry(union olsr_ip_addr *originator, 
263                       olsr_u16_t seqno, 
264                       union olsr_ip_addr *iface)
265 {
266   olsr_u32_t hash;
267   struct dup_entry *tmp_dup_table;
268   struct dup_iface *new_iface;
269
270   /* Hash the senders address */
271   hash = olsr_hashing(originator);
272
273
274   /* Check for entry */
275   for(tmp_dup_table = dup_set[hash].next;
276       tmp_dup_table != &dup_set[hash];
277       tmp_dup_table = tmp_dup_table->next)
278     {
279       if(COMP_IP(&tmp_dup_table->addr, originator) &&
280          (tmp_dup_table->seqno == seqno))
281         {
282           break;
283         }
284     }
285
286   if(tmp_dup_table == &dup_set[hash])
287     /* Did not find entry - create it */
288     tmp_dup_table = olsr_add_dup_entry(originator, seqno);
289   
290   /* 0 for now */
291   tmp_dup_table->forwarded = 0;
292   
293   new_iface = olsr_malloc(sizeof(struct dup_iface), "New dup iface");
294
295   COPY_IP(&new_iface->addr, iface);
296   new_iface->next = tmp_dup_table->ifaces;
297   tmp_dup_table->ifaces = new_iface;
298   
299   /* Set timer */
300   tmp_dup_table->timer = GET_TIMESTAMP(dup_hold_time*1000);
301   
302   return 1;
303 }
304
305
306
307
308 int
309 olsr_set_dup_forward(union olsr_ip_addr *originator, 
310                      olsr_u16_t seqno)
311 {
312   olsr_u32_t hash;
313   struct dup_entry *tmp_dup_table;
314
315   /* Hash the senders address */
316   hash = olsr_hashing(originator);
317
318   /* Check for entry */
319   for(tmp_dup_table = dup_set[hash].next;
320       tmp_dup_table != &dup_set[hash];
321       tmp_dup_table = tmp_dup_table->next)
322     {
323       if(COMP_IP(&tmp_dup_table->addr, originator) &&
324          (tmp_dup_table->seqno == seqno))
325         {
326           break;
327         }
328     }
329
330   if(tmp_dup_table == &dup_set[hash])
331     /* Did not find entry !! */
332     return 0;
333   
334 #ifdef DEBUG
335   olsr_printf(3, "Setting DUP %s/%d forwarded\n", olsr_ip_to_string(&tmp_dup_table->addr), seqno);
336 #endif
337
338   /* Set forwarded */
339   tmp_dup_table->forwarded = 1;
340   
341   /* Set timer */
342   tmp_dup_table->timer = GET_TIMESTAMP(dup_hold_time*1000);
343   
344   return 1;
345 }
346
347
348
349
350
351
352
353 void
354 olsr_print_duplicate_table()
355 {
356   int i;
357
358   printf("\nDUP TABLE:\n");
359
360   for(i = 0; i < HASHSIZE; i++)
361     {      
362       struct dup_entry *tmp_dup_table = dup_set[i].next;
363       
364       //printf("Timeout %d %d\n", i, j);
365       while(tmp_dup_table != &dup_set[i])
366         {
367           printf("[%s] s: %d\n", 
368                  olsr_ip_to_string(&tmp_dup_table->addr),
369                  tmp_dup_table->seqno);
370           tmp_dup_table = tmp_dup_table->next;
371         }
372     }
373 printf("\n");
374
375 }