3 * The olsr.org Optimized Link-State Routing daemon(olsrd)
4 * Copyright (c) 2004, Andreas Tonnesen(andreto@olsr.org)
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
11 * * Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * * Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in
15 * the documentation and/or other materials provided with the
17 * * Neither the name of olsr.org, olsrd nor the names of its
18 * contributors may be used to endorse or promote products derived
19 * from this software without specific prior written permission.
21 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
24 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
25 * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
26 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
27 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
28 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
29 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
30 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
31 * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
32 * POSSIBILITY OF SUCH DAMAGE.
34 * Visit http://www.olsr.org for more information.
36 * If you find this software useful feel free to make a donation
37 * to the project. For more information see the website or contact
38 * the copyright holders.
42 #include "process_package.h"
45 #include "lq_packet.h"
46 #include "hysteresis.h"
47 #include "two_hop_neighbor_table.h"
49 #include "mpr_selector_set.h"
53 #include "duplicate_set.h"
54 #include "scheduler.h"
56 #include "lq_plugin.h"
61 static void process_message_neighbors(struct neighbor_entry *, const struct hello_message *);
63 static void linking_this_2_entries(struct neighbor_entry *, struct neighbor_2_entry *, olsr_reltime);
65 static bool lookup_mpr_status(const struct hello_message *, const struct interface *);
68 *Processes an list of neighbors from an incoming HELLO message.
69 *@param neighbor the neighbor who sent the message.
70 *@param message the HELLO message
74 process_message_neighbors(struct neighbor_entry *neighbor, const struct hello_message *message)
76 struct hello_neighbor *message_neighbors;
78 for (message_neighbors = message->neighbors; message_neighbors != NULL; message_neighbors = message_neighbors->next) {
79 union olsr_ip_addr *neigh_addr;
80 struct neighbor_2_entry *two_hop_neighbor;
84 *so that we don't add ourselves to the
88 if (if_ifwithaddr(&message_neighbors->address) != NULL)
91 /* Get the main address */
92 neigh_addr = mid_lookup_main_addr(&message_neighbors->address);
94 if (neigh_addr != NULL) {
95 message_neighbors->address = *neigh_addr;
98 if (((message_neighbors->status == SYM_NEIGH) || (message_neighbors->status == MPR_NEIGH))) {
99 struct neighbor_2_list_entry *two_hop_neighbor_yet = olsr_lookup_my_neighbors(neighbor, &message_neighbors->address);
101 if (two_hop_neighbor_yet != NULL) {
102 /* Updating the holding time for this neighbor */
103 olsr_set_timer(&two_hop_neighbor_yet->nbr2_list_timer, message->vtime, OLSR_NBR2_LIST_JITTER, OLSR_TIMER_ONESHOT,
104 &olsr_expire_nbr2_list, two_hop_neighbor_yet, 0);
105 two_hop_neighbor = two_hop_neighbor_yet->neighbor_2;
108 * For link quality OLSR, reset the path link quality here.
109 * The path link quality will be calculated in the second pass, below.
110 * Keep the saved_path_link_quality for reference.
113 if (olsr_cnf->lq_level > 0) {
115 * loop through the one-hop neighbors that see this
119 struct neighbor_list_entry *walker;
121 for (walker = two_hop_neighbor->neighbor_2_nblist.next; walker != &two_hop_neighbor->neighbor_2_nblist;
122 walker = walker->next) {
124 * have we found the one-hop neighbor that sent the
125 * HELLO message that we're current processing?
128 if (walker->neighbor == neighbor) {
129 walker->path_linkcost = LINK_COST_BROKEN;
134 two_hop_neighbor = olsr_lookup_two_hop_neighbor_table(&message_neighbors->address);
135 if (two_hop_neighbor == NULL) {
136 changes_neighborhood = true;
137 changes_topology = true;
139 two_hop_neighbor = olsr_malloc(sizeof(struct neighbor_2_entry), "Process HELLO");
141 two_hop_neighbor->neighbor_2_nblist.next = &two_hop_neighbor->neighbor_2_nblist;
143 two_hop_neighbor->neighbor_2_nblist.prev = &two_hop_neighbor->neighbor_2_nblist;
145 two_hop_neighbor->neighbor_2_pointer = 0;
147 two_hop_neighbor->neighbor_2_addr = message_neighbors->address;
149 olsr_insert_two_hop_neighbor_table(two_hop_neighbor);
151 linking_this_2_entries(neighbor, two_hop_neighbor, message->vtime);
154 linking to this two_hop_neighbor entry
156 changes_neighborhood = true;
157 changes_topology = true;
159 linking_this_2_entries(neighbor, two_hop_neighbor, message->vtime);
165 /* Separate, second pass for link quality OLSR */
166 /* Separate, second and third pass for link quality OLSR */
168 if (olsr_cnf->lq_level > 0) {
169 olsr_linkcost first_hop_pathcost;
170 struct link_entry *lnk = get_best_link_to_neighbor(&neighbor->neighbor_main_addr);
175 /* calculate first hop path quality */
176 first_hop_pathcost = lnk->linkcost;
178 * Second pass for link quality OLSR: calculate the best 2-hop
179 * path costs to all the 2-hop neighbors indicated in the
180 * HELLO message. Since the same 2-hop neighbor may be listed
181 * more than once in the same HELLO message (each at a possibly
182 * different quality) we want to select only the best one, not just
183 * the last one listed in the HELLO message.
186 for (message_neighbors = message->neighbors; message_neighbors != NULL; message_neighbors = message_neighbors->next) {
187 if (if_ifwithaddr(&message_neighbors->address) != NULL)
190 if (((message_neighbors->status == SYM_NEIGH) || (message_neighbors->status == MPR_NEIGH))) {
191 struct neighbor_list_entry *walker;
192 struct neighbor_2_entry *two_hop_neighbor;
193 struct neighbor_2_list_entry *two_hop_neighbor_yet = olsr_lookup_my_neighbors(neighbor,
194 &message_neighbors->address);
196 if (!two_hop_neighbor_yet)
199 two_hop_neighbor = two_hop_neighbor_yet->neighbor_2;
202 * loop through the one-hop neighbors that see this
206 for (walker = two_hop_neighbor->neighbor_2_nblist.next; walker != &two_hop_neighbor->neighbor_2_nblist;
207 walker = walker->next) {
209 * have we found the one-hop neighbor that sent the
210 * HELLO message that we're current processing?
213 if (walker->neighbor == neighbor) {
214 olsr_linkcost new_second_hop_linkcost, new_path_linkcost;
216 // the link cost between the 1-hop neighbour and the
219 new_second_hop_linkcost = message_neighbors->cost;
221 // the total cost for the route
222 // "us --- 1-hop --- 2-hop"
224 new_path_linkcost = first_hop_pathcost + new_second_hop_linkcost;
226 // Only copy the link quality if it is better than what we have
227 // for this 2-hop neighbor
228 if (new_path_linkcost < walker->path_linkcost) {
229 walker->second_hop_linkcost = new_second_hop_linkcost;
230 walker->path_linkcost = new_path_linkcost;
232 walker->saved_path_linkcost = new_path_linkcost;
234 changes_neighborhood = true;
235 changes_topology = true;
245 *Links a one-hop neighbor with a 2-hop neighbor.
247 *@param neighbor the 1-hop neighbor
248 *@param two_hop_neighbor the 2-hop neighbor
249 *@param vtime the validity time
252 linking_this_2_entries(struct neighbor_entry *neighbor, struct neighbor_2_entry *two_hop_neighbor, olsr_reltime vtime)
254 struct neighbor_list_entry *list_of_1_neighbors = olsr_malloc(sizeof(struct neighbor_list_entry), "Link entries 1");
255 struct neighbor_2_list_entry *list_of_2_neighbors = olsr_malloc(sizeof(struct neighbor_2_list_entry), "Link entries 2");
257 list_of_1_neighbors->neighbor = neighbor;
259 list_of_1_neighbors->path_linkcost = LINK_COST_BROKEN;
260 list_of_1_neighbors->saved_path_linkcost = LINK_COST_BROKEN;
261 list_of_1_neighbors->second_hop_linkcost = LINK_COST_BROKEN;
264 two_hop_neighbor->neighbor_2_nblist.next->prev = list_of_1_neighbors;
265 list_of_1_neighbors->next = two_hop_neighbor->neighbor_2_nblist.next;
267 two_hop_neighbor->neighbor_2_nblist.next = list_of_1_neighbors;
268 list_of_1_neighbors->prev = &two_hop_neighbor->neighbor_2_nblist;
269 list_of_2_neighbors->neighbor_2 = two_hop_neighbor;
270 list_of_2_neighbors->nbr2_nbr = neighbor; /* XXX refcount */
272 olsr_change_timer(list_of_2_neighbors->nbr2_list_timer, vtime, OLSR_NBR2_LIST_JITTER, OLSR_TIMER_ONESHOT);
275 neighbor->neighbor_2_list.next->prev = list_of_2_neighbors;
276 list_of_2_neighbors->next = neighbor->neighbor_2_list.next;
277 neighbor->neighbor_2_list.next = list_of_2_neighbors;
278 list_of_2_neighbors->prev = &neighbor->neighbor_2_list;
280 /*increment the pointer counter */
281 two_hop_neighbor->neighbor_2_pointer++;
285 * Check if a hello message states this node as a MPR.
287 * @param message the message to check
288 * @param in_if the incoming interface
290 *@return 1 if we are selected as MPR 0 if not
293 lookup_mpr_status(const struct hello_message *message, const struct interface *in_if)
295 struct hello_neighbor *neighbors;
297 for (neighbors = message->neighbors; neighbors; neighbors = neighbors->next) {
298 if ( neighbors->link != UNSPEC_LINK
299 && (olsr_cnf->ip_version == AF_INET
300 ? ip4equal(&neighbors->address.v4, &in_if->ip_addr.v4)
301 : ip6equal(&neighbors->address.v6, &in_if->int6_addr.sin6_addr))) {
303 if (neighbors->link == SYM_LINK && neighbors->status == MPR_NEIGH) {
314 deserialize_hello(struct hello_message *hello, const void *ser)
316 const unsigned char *curr, *limit;
319 struct ipaddr_str buf;
321 memset (hello, 0, sizeof(*hello));
324 pkt_get_u8(&curr, &type);
325 if (type != HELLO_MESSAGE && type != LQ_HELLO_MESSAGE) {
326 /* No need to do anything more */
329 pkt_get_reltime(&curr, &hello->vtime);
330 pkt_get_u16(&curr, &size);
331 pkt_get_ipaddress(&curr, &hello->source_addr);
333 pkt_get_u8(&curr, &hello->ttl);
334 pkt_get_u8(&curr, &hello->hop_count);
335 pkt_get_u16(&curr, &hello->packet_seq_number);
336 pkt_ignore_u16(&curr);
338 pkt_get_reltime(&curr, &hello->htime);
339 pkt_get_u8(&curr, &hello->willingness);
341 hello->neighbors = NULL;
343 limit = ((const unsigned char *)ser) + size;
344 while (curr < limit) {
345 const unsigned char *limit2 = curr;
349 pkt_get_u8(&curr, &link_code);
350 pkt_ignore_u8(&curr);
351 pkt_get_u16(&curr, &size2);
354 while (curr < limit2) {
355 struct hello_neighbor *neigh = olsr_malloc_hello_neighbor("HELLO deserialization");
356 pkt_get_ipaddress(&curr, &neigh->address);
357 if (type == LQ_HELLO_MESSAGE) {
358 olsr_deserialize_hello_lq_pair(&curr, neigh);
360 neigh->link = EXTRACT_LINK(link_code);
361 neigh->status = EXTRACT_STATUS(link_code);
363 neigh->next = hello->neighbors;
364 hello->neighbors = neigh;
371 olsr_input_hello(union olsr_message * ser, struct interface * inif, union olsr_ip_addr * from)
373 struct hello_message hello;
378 if (deserialize_hello(&hello, ser) != 0) {
381 olsr_hello_tap(&hello, inif, from);
383 /* Do not forward hello messages */
388 *Initializing the parser functions we are using
391 olsr_init_package_process(void)
393 if (olsr_cnf->lq_level == 0) {
394 olsr_parser_add_function(&olsr_input_hello, HELLO_MESSAGE);
395 olsr_parser_add_function(&olsr_input_tc, TC_MESSAGE);
397 olsr_parser_add_function(&olsr_input_hello, LQ_HELLO_MESSAGE);
398 olsr_parser_add_function(&olsr_input_tc, LQ_TC_MESSAGE);
401 olsr_parser_add_function(&olsr_input_mid, MID_MESSAGE);
402 olsr_parser_add_function(&olsr_input_hna, HNA_MESSAGE);
406 olsr_hello_tap(struct hello_message *message, struct interface *in_if, const union olsr_ip_addr *from_addr)
408 struct neighbor_entry *neighbor;
413 struct link_entry *lnk = update_link_entry(&in_if->ip_addr, from_addr, message, in_if);
415 /*check alias message->source_addr*/
416 if (!ipequal(&message->source_addr,from_addr)){
417 /*new alias of new neighbour are thrown in the mid table to speed up routing*/
418 if (olsr_validate_address(from_addr)) {
419 union olsr_ip_addr * main_addr = mid_lookup_main_addr(from_addr);
420 if ((main_addr==NULL)||(ipequal(&message->source_addr, main_addr))){
421 /*struct ipaddr_str srcbuf, origbuf;
422 olsr_syslog(OLSR_LOG_INFO, "got hello from unknown alias ip of direct neighbour: ip: %s main-ip: %s",
423 olsr_ip_to_string(&origbuf,&message->source_addr),
424 olsr_ip_to_string(&srcbuf,from_addr));*/
425 insert_mid_alias(&message->source_addr, from_addr, message->vtime);
429 struct ipaddr_str srcbuf, origbuf;
430 olsr_syslog(OLSR_LOG_INFO, "got hello with invalid from and originator address pair (%s, %s) Duplicate Ips?\n",
431 olsr_ip_to_string(&origbuf,&message->source_addr),
432 olsr_ip_to_string(&srcbuf,from_addr));
437 if (olsr_cnf->lq_level > 0) {
438 struct hello_neighbor *walker;
439 /* just in case our neighbor has changed its HELLO interval */
440 olsr_update_packet_loss_hello_int(lnk, message->htime);
442 /* find the input interface in the list of neighbor interfaces */
443 for (walker = message->neighbors; walker != NULL; walker = walker->next) {
444 if (ipequal(&walker->address, &in_if->ip_addr)) {
446 * memorize our neighbour's idea of the link quality, so that we
447 * know the link quality in both directions
449 olsr_memorize_foreign_hello_lq(lnk, walker->link != UNSPEC_LINK ? walker : NULL);
453 /* update packet loss for link quality calculation */
454 olsr_received_hello_handler(lnk);
457 neighbor = lnk->neighbor;
462 if (olsr_cnf->use_hysteresis) {
463 /* Update HELLO timeout */
464 /* printf("MESSAGE HTIME: %f\n", message->htime); */
465 olsr_update_hysteresis_hello(lnk, message->htime);
468 /* Check if we are chosen as MPR */
469 if (lookup_mpr_status(message, in_if))
470 /* source_addr is always the main addr of a node! */
471 olsr_update_mprs_set(&message->source_addr, message->vtime);
473 /* Check willingness */
474 if (neighbor->willingness != message->willingness) {
475 struct ipaddr_str buf;
476 OLSR_PRINTF(1, "Willingness for %s changed from %d to %d - UPDATING\n", olsr_ip_to_string(&buf, &neighbor->neighbor_main_addr),
477 neighbor->willingness, message->willingness);
479 *If willingness changed - recalculate
481 neighbor->willingness = message->willingness;
482 changes_neighborhood = true;
483 changes_topology = true;
486 /* Don't register neighbors of neighbors that announces WILL_NEVER */
487 if (neighbor->willingness != WILL_NEVER)
488 process_message_neighbors(neighbor, message);
490 /* Process changes immediately in case of MPR updates */
491 olsr_process_changes();
493 olsr_free_hello_packet(message);
501 * indent-tabs-mode: nil