src/process_package.c

   1 /*
   2  * The olsr.org Optimized Link-State Routing daemon (olsrd)
   3  *
   4  * (c) by the OLSR project
   5  *
   6  * See our Git repository to find out who worked on this file
   7  * and thus is a copyright holder on it.
   8  *
   9  * All rights reserved.
  10  *
  11  * Redistribution and use in source and binary forms, with or without
  12  * modification, are permitted provided that the following conditions
  13  * are met:
  14  *
  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
  20  *   distribution.
  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.
  24  *
  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.
  37  *
  38  * Visit http://www.olsr.org for more information.
  39  *
  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.
  43  *
  44  */
  45
  46 #include "process_package.h"
  47 #include "ipcalc.h"
  48 #include "defs.h"
  49 #include "lq_packet.h"
  50 #include "hysteresis.h"
  51 #include "two_hop_neighbor_table.h"
  52 #include "tc_set.h"
  53 #include "mpr_selector_set.h"
  54 #include "mid_set.h"
  55 #include "olsr.h"
  56 #include "parser.h"
  57 #include "duplicate_set.h"
  58 #include "scheduler.h"
  59 #include "net_olsr.h"
  60 #include "lq_plugin.h"
  61 #include "log.h"
  62
  63 #include <assert.h>
  64 #include <stddef.h>
  65
  66 static void process_message_neighbors(struct neighbor_entry *, const struct hello_message *);
  67
  68 static void linking_this_2_entries(struct neighbor_entry *, struct neighbor_2_entry *, olsr_reltime);
  69
  70 static bool lookup_mpr_status(const struct hello_message *, const struct interface_olsr *);
  71
  72 /**
  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
  76  *@return nada
  77  */
  78 static void
  79 process_message_neighbors(struct neighbor_entry *neighbor, const struct hello_message *message)
  80 {
  81   struct hello_neighbor *message_neighbors;
  82
  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;
  86
  87     /*
  88      *check all interfaces
  89      *so that we don't add ourselves to the
  90      *2 hop list
  91      *IMPORTANT!
  92      */
  93     if (if_ifwithaddr(&message_neighbors->address) != NULL)
  94       continue;
  95
  96     /* Get the main address */
  97     neigh_addr = mid_lookup_main_addr(&message_neighbors->address);
  98
  99     if (neigh_addr != NULL) {
 100       message_neighbors->address = *neigh_addr;
 101     }
 102
 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);
 105
 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;
 111
 112         /*
 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.
 116          */
 117
 118         if (olsr_cnf->lq_level > 0) {
 119           /*
 120            * loop through the one-hop neighbors that see this
 121            * 'two_hop_neighbor'
 122            */
 123
 124           struct neighbor_list_entry *walker;
 125
 126           for (walker = two_hop_neighbor->neighbor_2_nblist.next; walker != &two_hop_neighbor->neighbor_2_nblist;
 127                walker = walker->next) {
 128             /*
 129              * have we found the one-hop neighbor that sent the
 130              * HELLO message that we're current processing?
 131              */
 132
 133             if (walker->neighbor == neighbor) {
 134               walker->path_linkcost = LINK_COST_BROKEN;
 135             }
 136           }
 137         }
 138       } else {
 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;
 143
 144           two_hop_neighbor = olsr_malloc(sizeof(struct neighbor_2_entry), "Process HELLO");
 145
 146           two_hop_neighbor->neighbor_2_nblist.next = &two_hop_neighbor->neighbor_2_nblist;
 147
 148           two_hop_neighbor->neighbor_2_nblist.prev = &two_hop_neighbor->neighbor_2_nblist;
 149
 150           two_hop_neighbor->neighbor_2_pointer = 0;
 151
 152           two_hop_neighbor->neighbor_2_addr = message_neighbors->address;
 153
 154           olsr_insert_two_hop_neighbor_table(two_hop_neighbor);
 155
 156           linking_this_2_entries(neighbor, two_hop_neighbor, message->vtime);
 157         } else {
 158           /*
 159              linking to this two_hop_neighbor entry
 160            */
 161           changes_neighborhood = true;
 162           changes_topology = true;
 163
 164           linking_this_2_entries(neighbor, two_hop_neighbor, message->vtime);
 165         }
 166       }
 167     }
 168   }
 169
 170   /* Separate, second pass for link quality OLSR */
 171   /* Separate, second and third pass for link quality OLSR */
 172
 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);
 176
 177     if (!lnk)
 178       return;
 179
 180     /* calculate first hop path quality */
 181     first_hop_pathcost = lnk->linkcost;
 182     /*
 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.
 189      */
 190
 191     for (message_neighbors = message->neighbors; message_neighbors != NULL; message_neighbors = message_neighbors->next) {
 192       if (if_ifwithaddr(&message_neighbors->address) != NULL)
 193         continue;
 194
 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);
 200
 201         if (!two_hop_neighbor_yet)
 202           continue;
 203
 204         two_hop_neighbor = two_hop_neighbor_yet->neighbor_2;
 205
 206         /*
 207          *  loop through the one-hop neighbors that see this
 208          * 'two_hop_neighbor'
 209          */
 210
 211         for (walker = two_hop_neighbor->neighbor_2_nblist.next; walker != &two_hop_neighbor->neighbor_2_nblist;
 212              walker = walker->next) {
 213           /*
 214            * have we found the one-hop neighbor that sent the
 215            * HELLO message that we're current processing?
 216            */
 217
 218           if (walker->neighbor == neighbor) {
 219             olsr_linkcost new_second_hop_linkcost, new_path_linkcost;
 220
 221             // the link cost between the 1-hop neighbour and the
 222             // 2-hop neighbour
 223
 224             new_second_hop_linkcost = message_neighbors->cost;
 225
 226             // the total cost for the route
 227             // "us --- 1-hop --- 2-hop"
 228
 229             new_path_linkcost = first_hop_pathcost + new_second_hop_linkcost;
 230
 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;
 236
 237               walker->saved_path_linkcost = new_path_linkcost;
 238
 239               changes_neighborhood = true;
 240               changes_topology = true;
 241             }
 242           }
 243         }
 244       }
 245     }
 246   }
 247 }
 248
 249 /**
 250  *Links a one-hop neighbor with a 2-hop neighbor.
 251  *
 252  *@param neighbor the 1-hop neighbor
 253  *@param two_hop_neighbor the 2-hop neighbor
 254  *@param vtime the validity time
 255  */
 256 static void
 257 linking_this_2_entries(struct neighbor_entry *neighbor, struct neighbor_2_entry *two_hop_neighbor, olsr_reltime vtime)
 258 {
 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");
 261
 262   list_of_1_neighbors->neighbor = neighbor;
 263
 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;
 267
 268   /* Queue */
 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;
 271
 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 */
 276
 277   olsr_change_timer(list_of_2_neighbors->nbr2_list_timer, vtime, OLSR_NBR2_LIST_JITTER, OLSR_TIMER_ONESHOT);
 278
 279   /* Queue */
 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;
 284
 285   /*increment the pointer counter */
 286   two_hop_neighbor->neighbor_2_pointer++;
 287 }
 288
 289 /**
 290  * Check if a hello message states this node as a MPR.
 291  *
 292  * @param message the message to check
 293  * @param in_if the incoming interface
 294  *
 295  *@return 1 if we are selected as MPR 0 if not
 296  */
 297 static bool
 298 lookup_mpr_status(const struct hello_message *message, const struct interface_olsr *in_if)
 299 {
 300   struct hello_neighbor *neighbors;
 301
 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))) {
 307
 308       if (neighbors->link == SYM_LINK && neighbors->status == MPR_NEIGH) {
 309         return true;
 310       }
 311       break;
 312     }
 313   }
 314   /* Not found */
 315   return false;
 316 }
 317
 318 static int
 319 deserialize_hello(struct hello_message *hello, const void *ser)
 320 {
 321   static const int LINK_ORDER[] = HELLO_LINK_ORDER_ARRAY;
 322   const unsigned char *curr, *limit;
 323   uint8_t type;
 324   uint16_t size;
 325   struct ipaddr_str buf;
 326   const unsigned char *curr_saved;
 327   unsigned int idx;
 328   struct hello_neighbor *neigh_unspec_first_prev = NULL;
 329   struct hello_neighbor *neigh_unspec_first = NULL;
 330
 331   assert(LINK_ORDER[0] == UNSPEC_LINK);
 332
 333   memset (hello, 0, sizeof(*hello));
 334
 335   curr = ser;
 336   pkt_get_u8(&curr, &type);
 337   if (type != HELLO_MESSAGE && type != LQ_HELLO_MESSAGE) {
 338     /* No need to do anything more */
 339     return 1;
 340   }
 341   pkt_get_reltime(&curr, &hello->vtime);
 342   pkt_get_u16(&curr, &size);
 343   pkt_get_ipaddress(&curr, &hello->source_addr);
 344
 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);
 349
 350   pkt_get_reltime(&curr, &hello->htime);
 351   pkt_get_u8(&curr, &hello->willingness);
 352
 353   hello->neighbors = NULL;
 354
 355   limit = ((const unsigned char *)ser) + size;
 356
 357   curr_saved = curr;
 358
 359   for (idx = 0; idx < (sizeof(LINK_ORDER) / sizeof(LINK_ORDER[0])); idx++) {
 360     curr = curr_saved;
 361
 362     while (curr < limit) {
 363       const unsigned char *limit2 = curr;
 364       uint8_t link_code;
 365       uint16_t size2;
 366
 367       pkt_get_u8(&curr, &link_code);
 368       pkt_ignore_u8(&curr);
 369       pkt_get_u16(&curr, &size2);
 370
 371       limit2 += size2;
 372
 373       if (EXTRACT_LINK(link_code) != LINK_ORDER[idx]) {
 374         curr = limit2;
 375         continue;
 376       }
 377
 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);
 383         }
 384         neigh->link = EXTRACT_LINK(link_code);
 385         neigh->status = EXTRACT_STATUS(link_code);
 386
 387         neigh->next = hello->neighbors;
 388         hello->neighbors = neigh;
 389
 390         if (neigh->link == UNSPEC_LINK) {
 391           neigh_unspec_first = neigh;
 392         } else if (!neigh_unspec_first_prev) {
 393           neigh_unspec_first_prev = neigh;
 394         }
 395       }
 396     }
 397   }
 398
 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;
 405
 406       for (neigh_cull_prev = neigh_unspec_first_prev, neigh_cull = neigh_unspec_first;
 407            neigh_cull;
 408            neigh_cull = neigh_cull_next) {
 409         neigh_cull_next = neigh_cull->next;
 410
 411         if (!ipequal(&neigh_cull->address, &neigh->address)) {
 412           neigh_cull_prev = neigh_cull;
 413           continue;
 414         }
 415
 416         if (neigh_cull == neigh_unspec_first) {
 417           neigh_unspec_first = neigh_cull_next;
 418         }
 419
 420         neigh_cull_prev->next = neigh_cull_next;
 421         free(neigh_cull);
 422       }
 423     }
 424   }
 425
 426   return 0;
 427 }
 428
 429 bool
 430 olsr_input_hello(union olsr_message * ser, struct interface_olsr * inif, union olsr_ip_addr * from)
 431 {
 432   struct hello_message hello;
 433
 434   if (ser == NULL) {
 435     return false;
 436   }
 437   if (deserialize_hello(&hello, ser) != 0) {
 438     return false;
 439   }
 440   olsr_hello_tap(&hello, inif, from);
 441
 442   /* Do not forward hello messages */
 443   return false;
 444 }
 445
 446 /**
 447  *Initializing the parser functions we are using
 448  */
 449 void
 450 olsr_init_package_process(void)
 451 {
 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);
 455   } else {
 456     olsr_parser_add_function(&olsr_input_hello, LQ_HELLO_MESSAGE);
 457     olsr_parser_add_function(&olsr_input_tc, LQ_TC_MESSAGE);
 458   }
 459
 460   olsr_parser_add_function(&olsr_input_mid, MID_MESSAGE);
 461   olsr_parser_add_function(&olsr_input_hna, HNA_MESSAGE);
 462 }
 463
 464 void
 465 olsr_hello_tap(struct hello_message *message, struct interface_olsr *in_if, const union olsr_ip_addr *from_addr)
 466 {
 467   struct neighbor_entry *neighbor;
 468
 469   /*
 470    * Update link status
 471    */
 472   struct link_entry *lnk = update_link_entry(&in_if->ip_addr, from_addr, message, in_if);
 473
 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);
 485       }
 486       else
 487       {
 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));
 492       }
 493     }
 494   }
 495
 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);
 500
 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)) {
 504         /*
 505          * memorize our neighbour's idea of the link quality, so that we
 506          * know the link quality in both directions
 507          */
 508         olsr_memorize_foreign_hello_lq(lnk, walker->link != UNSPEC_LINK ? walker : NULL);
 509         break;
 510       }
 511     }
 512     /* update packet loss for link quality calculation */
 513     olsr_received_hello_handler(lnk);
 514   }
 515
 516   neighbor = lnk->neighbor;
 517
 518   /*
 519    * Hysteresis
 520    */
 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);
 525   }
 526
 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);
 531
 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);
 537     /*
 538      *If willingness changed - recalculate
 539      */
 540     neighbor->willingness = message->willingness;
 541     changes_neighborhood = true;
 542     changes_topology = true;
 543   }
 544
 545   /* Don't register neighbors of neighbors that announces WILL_NEVER */
 546   if (neighbor->willingness != WILL_NEVER)
 547     process_message_neighbors(neighbor, message);
 548
 549   /* Process changes immediately in case of MPR updates */
 550   olsr_process_changes();
 551
 552   olsr_free_hello_packet(message);
 553
 554   return;
 555 }
 556
 557 /*
 558  * Local Variables:
 559  * c-basic-offset: 2
 560  * indent-tabs-mode: nil
 561  * End:
 562  */