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