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