2 * The olsr.org Optimized Link-State Routing daemon(olsrd)
3 * Copyright (c) 2004, Andreas Tønnesen(andreto@olsr.org)
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
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
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.
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.
33 * Visit http://www.olsr.org for more information.
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.
39 * $Id: mid_set.c,v 1.12 2005/01/22 00:09:18 kattemat Exp $
43 #include "two_hop_neighbor_table.h"
46 #include "scheduler.h"
47 #include "neighbor_table.h"
51 * Initialize the MID set
60 olsr_printf(5, "MID: init\n");
62 /* Since the holdingtime is assumed to be rather large for
63 * MID entries, the timeoutfunction is only ran once every second
65 olsr_register_scheduler_event(&olsr_time_out_mid_set, NULL, 1, 0, NULL);
67 for(index=0;index<HASHSIZE;index++)
69 mid_set[index].next = &mid_set[index];
70 mid_set[index].prev = &mid_set[index];
72 reverse_mid_set[index].next = &reverse_mid_set[index];
73 reverse_mid_set[index].prev = &reverse_mid_set[index];
81 *Insert a new interface alias to the interface association set.
82 *If the main interface of the association is not yet registered
83 *in the set a new entry is created.
85 *@param m_addr the main address of the node
86 *@param alias the alias address to insert
92 insert_mid_tuple(union olsr_ip_addr *m_addr, struct mid_address *alias, float vtime)
94 struct mid_entry *tmp;
95 struct mid_address *tmp_adr;
96 olsr_u32_t hash, alias_hash;
98 hash = olsr_hashing(m_addr);
99 alias_hash = olsr_hashing(&alias->alias);
101 /* Check for registered entry */
102 for(tmp = mid_set[hash].next;
103 tmp != &mid_set[hash];
106 if(COMP_IP(&tmp->main_addr, m_addr))
110 /*If the address was registered*/
111 if(tmp != &mid_set[hash])
113 tmp_adr = tmp->aliases;
114 tmp->aliases = alias;
115 alias->main_entry = tmp;
116 QUEUE_ELEM(reverse_mid_set[alias_hash], alias);
117 alias->next_alias = tmp_adr;
118 tmp->ass_timer = GET_TIMESTAMP(vtime*1000);
123 tmp = olsr_malloc(sizeof(struct mid_entry), "MID new alias");
125 tmp->aliases = alias;
126 alias->main_entry = tmp;
127 QUEUE_ELEM(reverse_mid_set[alias_hash], alias);
128 COPY_IP(&tmp->main_addr, m_addr);
129 tmp->ass_timer = GET_TIMESTAMP(vtime*1000);
131 QUEUE_ELEM(mid_set[hash], tmp);
137 * Delete possible duplicate entries in 2 hop set
138 * and delete duplicate neighbor entries. Redirect
139 * link entries to the correct neighbor entry.
141 *THIS OPTIMIZATION IS NOT SPECIFIED IN RFC3626
148 struct neighbor_2_entry *tmp_2_neighbor;
149 struct neighbor_entry *tmp_neigh, *real_neigh;
151 /* Delete possible 2 hop neighbor */
152 if((tmp_2_neighbor = olsr_lookup_two_hop_neighbor_table_mid(&tmp_adr->alias)) != NULL)
154 olsr_printf(1, "Deleting 2 hop node from MID: %s to ", olsr_ip_to_string(&tmp_adr->alias));
155 olsr_printf(1, "%s\n", olsr_ip_to_string(m_addr));
157 olsr_delete_two_hop_neighbor_table(tmp_2_neighbor);
159 changes_neighborhood = OLSR_TRUE;
162 /* Delete a possible neighbor entry */
163 if(((tmp_neigh = olsr_lookup_neighbor_table_alias(&tmp_adr->alias)) != NULL)
164 && ((real_neigh = olsr_lookup_neighbor_table_alias(m_addr)) != NULL))
167 olsr_printf(1, "[MID]Deleting bogus neighbor entry %s real ", olsr_ip_to_string(&tmp_adr->alias));
168 olsr_printf(1, "%s\n", olsr_ip_to_string(m_addr));
170 replace_neighbor_link_set(tmp_neigh, real_neigh);
173 DEQUEUE_ELEM(tmp_neigh);
177 changes_neighborhood = OLSR_TRUE;
180 tmp_adr = tmp_adr->next_alias;
188 *Insert an alias address for a node.
189 *If the main address is not registered
190 *then a new entry is created.
192 *@param main_add the main address of the node
193 *@param alias the alias address to insert
194 *@param seq the sequence number to register a new node with
199 insert_mid_alias(union olsr_ip_addr *main_add, union olsr_ip_addr *alias, float vtime)
201 struct mid_address *adr;
203 adr = olsr_malloc(sizeof(struct mid_address), "Insert MID alias");
205 olsr_printf(1, "Inserting alias %s for ", olsr_ip_to_string(alias));
206 olsr_printf(1, "%s\n", olsr_ip_to_string(main_add));
208 COPY_IP(&adr->alias, alias);
209 adr->next_alias = NULL;
211 insert_mid_tuple(main_add, adr, vtime);
214 *Recalculate topology
216 changes_neighborhood = OLSR_TRUE;
217 changes_topology = OLSR_TRUE;
226 *Lookup the main address for a alias address
228 *@param adr the alias address to check
230 *@return the main address registered on the alias
231 *or NULL if not found
234 mid_lookup_main_addr(union olsr_ip_addr *adr)
237 struct mid_address *tmp_list;
239 #warning MID SET NOW HAS REVERSE INDEXING!
240 hash = olsr_hashing(adr);
241 /*Traverse MID list*/
242 for(tmp_list = reverse_mid_set[hash].next;
243 tmp_list != &reverse_mid_set[hash];
244 tmp_list = tmp_list->next)
246 if(COMP_IP(&tmp_list->alias, adr))
247 return &tmp_list->main_entry->main_addr;
257 *Find all aliases for an address.
259 *@param adr the main address to search for
261 *@return a linked list of addresses structs
264 mid_lookup_aliases(union olsr_ip_addr *adr)
266 struct mid_entry *tmp_list;
269 //olsr_printf(1, "MID: lookup entry...");
271 hash = olsr_hashing(adr);
273 /* Check all registered nodes...*/
274 for(tmp_list = mid_set[hash].next;
275 tmp_list != &mid_set[hash];
276 tmp_list = tmp_list->next)
278 if(COMP_IP(&tmp_list->main_addr, adr))
279 return tmp_list->aliases;
288 *Update the timer for an entry
290 *@param adr the main address of the entry
292 *@return 1 if the node was updated, 0 if not
295 olsr_update_mid_table(union olsr_ip_addr *adr, float vtime)
297 struct mid_entry *tmp_list = mid_set;
300 olsr_printf(3, "MID: update %s\n", olsr_ip_to_string(adr));
301 hash = olsr_hashing(adr);
303 /* Check all registered nodes...*/
304 for(tmp_list = mid_set[hash].next;
305 tmp_list != &mid_set[hash];
306 tmp_list = tmp_list->next)
309 if(COMP_IP(&tmp_list->main_addr, adr))
311 //printf("Updating timer for node %s\n",ip_to_string(&tmp_list->main_addr));
312 tmp_list->ass_timer = GET_TIMESTAMP(vtime*1000);
323 *Find timed out entries and delete them
328 olsr_time_out_mid_set(void *foo)
333 for(index=0;index<HASHSIZE;index++)
335 struct mid_entry *tmp_list = mid_set[index].next;
336 /*Traverse MID list*/
337 while(tmp_list != &mid_set[index])
339 /*Check if the entry is timed out*/
340 if(TIMED_OUT(tmp_list->ass_timer))
342 struct mid_entry *entry_to_delete = tmp_list;
343 tmp_list = tmp_list->next;
345 olsr_printf(1, "MID info for %s timed out.. deleting it\n",
346 olsr_ip_to_string(&entry_to_delete->main_addr));
349 mid_delete_node(entry_to_delete);
352 tmp_list = tmp_list->next;
363 *@param entry the entry to delete
368 mid_delete_node(struct mid_entry *entry)
370 struct mid_address *aliases;
373 aliases = entry->aliases;
376 struct mid_address *tmp_aliases = aliases;
377 aliases = aliases->next_alias;
378 DEQUEUE_ELEM(tmp_aliases);
390 *Print all multiple interface info
391 *For debuging purposes
399 olsr_printf(1, "mid set: %02d:%02d:%02d.%06lu\n",nowtm->tm_hour, nowtm->tm_min, nowtm->tm_sec, now.tv_usec);
401 for(index=0;index<HASHSIZE;index++)
403 struct mid_entry *tmp_list = mid_set[index].next;
404 /*Traverse MID list*/
405 for(tmp_list = mid_set[index].next;
406 tmp_list != &mid_set[index];
407 tmp_list = tmp_list->next)
409 struct mid_address *tmp_addr = tmp_list->aliases;
411 olsr_printf(1, "%s: ", olsr_ip_to_string(&tmp_list->main_addr));
414 olsr_printf(1, " %s ", olsr_ip_to_string(&tmp_addr->alias));
415 tmp_addr = tmp_addr->next_alias;
417 olsr_printf(1, "\n");