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