2 * The olsr.org Optimized Link-State Routing daemon (olsrd)
4 * (c) by the OLSR project
6 * See our Git repository to find out who worked on this file
7 * and thus is a copyright holder on it.
11 * Redistribution and use in source and binary forms, with or without
12 * modification, are permitted provided that the following conditions
15 * * Redistributions of source code must retain the above copyright
16 * notice, this list of conditions and the following disclaimer.
17 * * Redistributions in binary form must reproduce the above copyright
18 * notice, this list of conditions and the following disclaimer in
19 * the documentation and/or other materials provided with the
21 * * Neither the name of olsr.org, olsrd nor the names of its
22 * contributors may be used to endorse or promote products derived
23 * from this software without specific prior written permission.
25 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
26 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
27 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
28 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
29 * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
30 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
31 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
32 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
33 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
34 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
35 * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
36 * POSSIBILITY OF SUCH DAMAGE.
38 * Visit http://www.olsr.org for more information.
40 * If you find this software useful feel free to make a donation
41 * to the project. For more information see the website or contact
42 * the copyright holders.
46 #include "process_package.h"
49 #include "lq_packet.h"
50 #include "hysteresis.h"
51 #include "two_hop_neighbor_table.h"
53 #include "mpr_selector_set.h"
57 #include "duplicate_set.h"
58 #include "scheduler.h"
60 #include "lq_plugin.h"
66 static void process_message_neighbors(struct neighbor_entry *, const struct hello_message *);
68 static void linking_this_2_entries(struct neighbor_entry *, struct neighbor_2_entry *, olsr_reltime);
70 static bool lookup_mpr_status(const struct hello_message *, const struct interface_olsr *);
73 *Processes an list of neighbors from an incoming HELLO message.
74 *@param neighbor the neighbor who sent the message.
75 *@param message the HELLO message
79 process_message_neighbors(struct neighbor_entry *neighbor, const struct hello_message *message)
81 struct hello_neighbor *message_neighbors;
83 for (message_neighbors = message->neighbors; message_neighbors != NULL; message_neighbors = message_neighbors->next) {
84 union olsr_ip_addr *neigh_addr;
85 struct neighbor_2_entry *two_hop_neighbor;
89 *so that we don't add ourselves to the
93 if (if_ifwithaddr(&message_neighbors->address) != NULL)
96 /* Get the main address */
97 neigh_addr = mid_lookup_main_addr(&message_neighbors->address);
99 if (neigh_addr != NULL) {
100 message_neighbors->address = *neigh_addr;
103 if (((message_neighbors->status == SYM_NEIGH) || (message_neighbors->status == MPR_NEIGH))) {
104 struct neighbor_2_list_entry *two_hop_neighbor_yet = olsr_lookup_my_neighbors(neighbor, &message_neighbors->address);
106 if (two_hop_neighbor_yet != NULL) {
107 /* Updating the holding time for this neighbor */
108 olsr_set_timer(&two_hop_neighbor_yet->nbr2_list_timer, message->vtime, OLSR_NBR2_LIST_JITTER, OLSR_TIMER_ONESHOT,
109 &olsr_expire_nbr2_list, two_hop_neighbor_yet, 0);
110 two_hop_neighbor = two_hop_neighbor_yet->neighbor_2;
113 * For link quality OLSR, reset the path link quality here.
114 * The path link quality will be calculated in the second pass, below.
115 * Keep the saved_path_link_quality for reference.
118 if (olsr_cnf->lq_level > 0) {
120 * loop through the one-hop neighbors that see this
124 struct neighbor_list_entry *walker;
126 for (walker = two_hop_neighbor->neighbor_2_nblist.next; walker != &two_hop_neighbor->neighbor_2_nblist;
127 walker = walker->next) {
129 * have we found the one-hop neighbor that sent the
130 * HELLO message that we're current processing?
133 if (walker->neighbor == neighbor) {
134 walker->path_linkcost = LINK_COST_BROKEN;
139 two_hop_neighbor = olsr_lookup_two_hop_neighbor_table(&message_neighbors->address);
140 if (two_hop_neighbor == NULL) {
141 changes_neighborhood = true;
142 changes_topology = true;
144 two_hop_neighbor = olsr_malloc(sizeof(struct neighbor_2_entry), "Process HELLO");
146 two_hop_neighbor->neighbor_2_nblist.next = &two_hop_neighbor->neighbor_2_nblist;
148 two_hop_neighbor->neighbor_2_nblist.prev = &two_hop_neighbor->neighbor_2_nblist;
150 two_hop_neighbor->neighbor_2_pointer = 0;
152 two_hop_neighbor->neighbor_2_addr = message_neighbors->address;
154 olsr_insert_two_hop_neighbor_table(two_hop_neighbor);
156 linking_this_2_entries(neighbor, two_hop_neighbor, message->vtime);
159 linking to this two_hop_neighbor entry
161 changes_neighborhood = true;
162 changes_topology = true;
164 linking_this_2_entries(neighbor, two_hop_neighbor, message->vtime);
170 /* Separate, second pass for link quality OLSR */
171 /* Separate, second and third pass for link quality OLSR */
173 if (olsr_cnf->lq_level > 0) {
174 olsr_linkcost first_hop_pathcost;
175 struct link_entry *lnk = get_best_link_to_neighbor(&neighbor->neighbor_main_addr);
180 /* calculate first hop path quality */
181 first_hop_pathcost = lnk->linkcost;
183 * Second pass for link quality OLSR: calculate the best 2-hop
184 * path costs to all the 2-hop neighbors indicated in the
185 * HELLO message. Since the same 2-hop neighbor may be listed
186 * more than once in the same HELLO message (each at a possibly
187 * different quality) we want to select only the best one, not just
188 * the last one listed in the HELLO message.
191 for (message_neighbors = message->neighbors; message_neighbors != NULL; message_neighbors = message_neighbors->next) {
192 if (if_ifwithaddr(&message_neighbors->address) != NULL)
195 if (((message_neighbors->status == SYM_NEIGH) || (message_neighbors->status == MPR_NEIGH))) {
196 struct neighbor_list_entry *walker;
197 struct neighbor_2_entry *two_hop_neighbor;
198 struct neighbor_2_list_entry *two_hop_neighbor_yet = olsr_lookup_my_neighbors(neighbor,
199 &message_neighbors->address);
201 if (!two_hop_neighbor_yet)
204 two_hop_neighbor = two_hop_neighbor_yet->neighbor_2;
207 * loop through the one-hop neighbors that see this
211 for (walker = two_hop_neighbor->neighbor_2_nblist.next; walker != &two_hop_neighbor->neighbor_2_nblist;
212 walker = walker->next) {
214 * have we found the one-hop neighbor that sent the
215 * HELLO message that we're current processing?
218 if (walker->neighbor == neighbor) {
219 olsr_linkcost new_second_hop_linkcost, new_path_linkcost;
221 // the link cost between the 1-hop neighbour and the
224 new_second_hop_linkcost = message_neighbors->cost;
226 // the total cost for the route
227 // "us --- 1-hop --- 2-hop"
229 new_path_linkcost = first_hop_pathcost + new_second_hop_linkcost;
231 // Only copy the link quality if it is better than what we have
232 // for this 2-hop neighbor
233 if (new_path_linkcost < walker->path_linkcost) {
234 walker->second_hop_linkcost = new_second_hop_linkcost;
235 walker->path_linkcost = new_path_linkcost;
237 walker->saved_path_linkcost = new_path_linkcost;
239 changes_neighborhood = true;
240 changes_topology = true;
250 *Links a one-hop neighbor with a 2-hop neighbor.
252 *@param neighbor the 1-hop neighbor
253 *@param two_hop_neighbor the 2-hop neighbor
254 *@param vtime the validity time
257 linking_this_2_entries(struct neighbor_entry *neighbor, struct neighbor_2_entry *two_hop_neighbor, olsr_reltime vtime)
259 struct neighbor_list_entry *list_of_1_neighbors = olsr_malloc(sizeof(struct neighbor_list_entry), "Link entries 1");
260 struct neighbor_2_list_entry *list_of_2_neighbors = olsr_malloc(sizeof(struct neighbor_2_list_entry), "Link entries 2");
262 list_of_1_neighbors->neighbor = neighbor;
264 list_of_1_neighbors->path_linkcost = LINK_COST_BROKEN;
265 list_of_1_neighbors->saved_path_linkcost = LINK_COST_BROKEN;
266 list_of_1_neighbors->second_hop_linkcost = LINK_COST_BROKEN;
269 two_hop_neighbor->neighbor_2_nblist.next->prev = list_of_1_neighbors;
270 list_of_1_neighbors->next = two_hop_neighbor->neighbor_2_nblist.next;
272 two_hop_neighbor->neighbor_2_nblist.next = list_of_1_neighbors;
273 list_of_1_neighbors->prev = &two_hop_neighbor->neighbor_2_nblist;
274 list_of_2_neighbors->neighbor_2 = two_hop_neighbor;
275 list_of_2_neighbors->nbr2_nbr = neighbor; /* XXX refcount */
277 olsr_change_timer(list_of_2_neighbors->nbr2_list_timer, vtime, OLSR_NBR2_LIST_JITTER, OLSR_TIMER_ONESHOT);
280 neighbor->neighbor_2_list.next->prev = list_of_2_neighbors;
281 list_of_2_neighbors->next = neighbor->neighbor_2_list.next;
282 neighbor->neighbor_2_list.next = list_of_2_neighbors;
283 list_of_2_neighbors->prev = &neighbor->neighbor_2_list;
285 /*increment the pointer counter */
286 two_hop_neighbor->neighbor_2_pointer++;
290 * Check if a hello message states this node as a MPR.
292 * @param message the message to check
293 * @param in_if the incoming interface
295 *@return 1 if we are selected as MPR 0 if not
298 lookup_mpr_status(const struct hello_message *message, const struct interface_olsr *in_if)
300 struct hello_neighbor *neighbors;
302 for (neighbors = message->neighbors; neighbors; neighbors = neighbors->next) {
303 if ( neighbors->link != UNSPEC_LINK
304 && (olsr_cnf->ip_version == AF_INET
305 ? ip4equal(&neighbors->address.v4, &in_if->ip_addr.v4)
306 : ip6equal(&neighbors->address.v6, &in_if->int6_addr.sin6_addr))) {
308 if (neighbors->link == SYM_LINK && neighbors->status == MPR_NEIGH) {
319 deserialize_hello(struct hello_message *hello, const void *ser)
321 static const int LINK_ORDER[] = HELLO_LINK_ORDER_ARRAY;
322 const unsigned char *curr, *limit;
325 struct ipaddr_str buf;
326 const unsigned char *curr_saved;
328 struct hello_neighbor *neigh_unspec_first_prev = NULL;
329 struct hello_neighbor *neigh_unspec_first = NULL;
331 assert(LINK_ORDER[0] == UNSPEC_LINK);
333 memset (hello, 0, sizeof(*hello));
336 pkt_get_u8(&curr, &type);
337 if (type != HELLO_MESSAGE && type != LQ_HELLO_MESSAGE) {
338 /* No need to do anything more */
341 pkt_get_reltime(&curr, &hello->vtime);
342 pkt_get_u16(&curr, &size);
343 pkt_get_ipaddress(&curr, &hello->source_addr);
345 pkt_get_u8(&curr, &hello->ttl);
346 pkt_get_u8(&curr, &hello->hop_count);
347 pkt_get_u16(&curr, &hello->packet_seq_number);
348 pkt_ignore_u16(&curr);
350 pkt_get_reltime(&curr, &hello->htime);
351 pkt_get_u8(&curr, &hello->willingness);
353 hello->neighbors = NULL;
355 limit = ((const unsigned char *)ser) + size;
359 for (idx = 0; idx < (sizeof(LINK_ORDER) / sizeof(LINK_ORDER[0])); idx++) {
362 while (curr < limit) {
363 const unsigned char *limit2 = curr;
367 pkt_get_u8(&curr, &link_code);
368 pkt_ignore_u8(&curr);
369 pkt_get_u16(&curr, &size2);
373 if (EXTRACT_LINK(link_code) != LINK_ORDER[idx]) {
378 while (curr < limit2) {
379 struct hello_neighbor *neigh = olsr_malloc_hello_neighbor("HELLO deserialization");
380 pkt_get_ipaddress(&curr, &neigh->address);
381 if (type == LQ_HELLO_MESSAGE) {
382 olsr_deserialize_hello_lq_pair(&curr, neigh);
384 neigh->link = EXTRACT_LINK(link_code);
385 neigh->status = EXTRACT_STATUS(link_code);
387 neigh->next = hello->neighbors;
388 hello->neighbors = neigh;
390 if (neigh->link == UNSPEC_LINK) {
391 neigh_unspec_first = neigh;
392 } else if (!neigh_unspec_first_prev) {
393 neigh_unspec_first_prev = neigh;
399 if (neigh_unspec_first_prev && neigh_unspec_first) {
400 struct hello_neighbor *neigh;
401 for (neigh = hello->neighbors; neigh && (neigh != neigh_unspec_first); neigh = neigh->next) {
402 struct hello_neighbor *neigh_cull;
403 struct hello_neighbor *neigh_cull_prev;
404 struct hello_neighbor *neigh_cull_next;
406 for (neigh_cull_prev = neigh_unspec_first_prev, neigh_cull = neigh_unspec_first;
408 neigh_cull = neigh_cull_next) {
409 neigh_cull_next = neigh_cull->next;
411 if (!ipequal(&neigh_cull->address, &neigh->address)) {
412 neigh_cull_prev = neigh_cull;
416 if (neigh_cull == neigh_unspec_first) {
417 neigh_unspec_first = neigh_cull_next;
420 neigh_cull_prev->next = neigh_cull_next;
430 olsr_input_hello(union olsr_message * ser, struct interface_olsr * inif, union olsr_ip_addr * from)
432 struct hello_message hello;
437 if (deserialize_hello(&hello, ser) != 0) {
440 olsr_hello_tap(&hello, inif, from);
442 /* Do not forward hello messages */
447 *Initializing the parser functions we are using
450 olsr_init_package_process(void)
452 if (olsr_cnf->lq_level == 0) {
453 olsr_parser_add_function(&olsr_input_hello, HELLO_MESSAGE);
454 olsr_parser_add_function(&olsr_input_tc, TC_MESSAGE);
456 olsr_parser_add_function(&olsr_input_hello, LQ_HELLO_MESSAGE);
457 olsr_parser_add_function(&olsr_input_tc, LQ_TC_MESSAGE);
460 olsr_parser_add_function(&olsr_input_mid, MID_MESSAGE);
461 olsr_parser_add_function(&olsr_input_hna, HNA_MESSAGE);
465 olsr_hello_tap(struct hello_message *message, struct interface_olsr *in_if, const union olsr_ip_addr *from_addr)
467 struct neighbor_entry *neighbor;
472 struct link_entry *lnk = update_link_entry(&in_if->ip_addr, from_addr, message, in_if);
474 /*check alias message->source_addr*/
475 if (!ipequal(&message->source_addr,from_addr)){
476 /*new alias of new neighbour are thrown in the mid table to speed up routing*/
477 if (olsr_validate_address(from_addr)) {
478 union olsr_ip_addr * main_addr = mid_lookup_main_addr(from_addr);
479 if ((main_addr==NULL)||(ipequal(&message->source_addr, main_addr))){
480 /*struct ipaddr_str srcbuf, origbuf;
481 olsr_syslog(OLSR_LOG_INFO, "got hello from unknown alias ip of direct neighbour: ip: %s main-ip: %s",
482 olsr_ip_to_string(&origbuf,&message->source_addr),
483 olsr_ip_to_string(&srcbuf,from_addr));*/
484 insert_mid_alias(&message->source_addr, from_addr, message->vtime);
488 struct ipaddr_str srcbuf, origbuf;
489 olsr_syslog(OLSR_LOG_INFO, "got hello with invalid from and originator address pair (%s, %s) Duplicate Ips?\n",
490 olsr_ip_to_string(&origbuf,&message->source_addr),
491 olsr_ip_to_string(&srcbuf,from_addr));
496 if (olsr_cnf->lq_level > 0) {
497 struct hello_neighbor *walker;
498 /* just in case our neighbor has changed its HELLO interval */
499 olsr_update_packet_loss_hello_int(lnk, message->htime);
501 /* find the input interface in the list of neighbor interfaces */
502 for (walker = message->neighbors; walker != NULL; walker = walker->next) {
503 if (ipequal(&walker->address, &in_if->ip_addr)) {
505 * memorize our neighbour's idea of the link quality, so that we
506 * know the link quality in both directions
508 olsr_memorize_foreign_hello_lq(lnk, walker->link != UNSPEC_LINK ? walker : NULL);
512 /* update packet loss for link quality calculation */
513 olsr_received_hello_handler(lnk);
516 neighbor = lnk->neighbor;
521 if (olsr_cnf->use_hysteresis) {
522 /* Update HELLO timeout */
523 /* printf("MESSAGE HTIME: %f\n", message->htime); */
524 olsr_update_hysteresis_hello(lnk, message->htime);
527 /* Check if we are chosen as MPR */
528 if (lookup_mpr_status(message, in_if))
529 /* source_addr is always the main addr of a node! */
530 olsr_update_mprs_set(&message->source_addr, message->vtime);
532 /* Check willingness */
533 if (neighbor->willingness != message->willingness) {
534 struct ipaddr_str buf;
535 OLSR_PRINTF(1, "Willingness for %s changed from %d to %d - UPDATING\n", olsr_ip_to_string(&buf, &neighbor->neighbor_main_addr),
536 neighbor->willingness, message->willingness);
538 *If willingness changed - recalculate
540 neighbor->willingness = message->willingness;
541 changes_neighborhood = true;
542 changes_topology = true;
545 /* Don't register neighbors of neighbors that announces WILL_NEVER */
546 if (neighbor->willingness != WILL_NEVER)
547 process_message_neighbors(neighbor, message);
549 /* Process changes immediately in case of MPR updates */
550 olsr_process_changes();
552 olsr_free_hello_packet(message);
560 * indent-tabs-mode: nil