src/process_package.c

   1
   2 /*
   3  * The olsr.org Optimized Link-State Routing daemon(olsrd)
   4  * Copyright (c) 2004, Andreas Tonnesen(andreto@olsr.org)
   5  * All rights reserved.
   6  *
   7  * Redistribution and use in source and binary forms, with or without
   8  * modification, are permitted provided that the following conditions
   9  * are met:
  10  *
  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
  16  *   distribution.
  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.
  20  *
  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.
  33  *
  34  * Visit http://www.olsr.org for more information.
  35  *
  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.
  39  *
  40  */
  41
  42 #include "process_package.h"
  43 #include "ipcalc.h"
  44 #include "defs.h"
  45 #include "lq_packet.h"
  46 #include "hysteresis.h"
  47 #include "two_hop_neighbor_table.h"
  48 #include "tc_set.h"
  49 #include "mpr_selector_set.h"
  50 #include "mid_set.h"
  51 #include "olsr.h"
  52 #include "parser.h"
  53 #include "duplicate_set.h"
  54 #include "scheduler.h"
  55 #include "net_olsr.h"
  56 #include "lq_plugin.h"
  57 #include "log.h"
  58
  59 #include <stddef.h>
  60
  61 static void process_message_neighbors(struct neighbor_entry *, const struct hello_message *);
  62
  63 static void linking_this_2_entries(struct neighbor_entry *, struct neighbor_2_entry *, olsr_reltime);
  64
  65 static bool lookup_mpr_status(const struct hello_message *, const struct interface *);
  66
  67 /**
  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
  71  *@return nada
  72  */
  73 static void
  74 process_message_neighbors(struct neighbor_entry *neighbor, const struct hello_message *message)
  75 {
  76   struct hello_neighbor *message_neighbors;
  77
  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;
  81
  82     /*
  83      *check all interfaces
  84      *so that we don't add ourselves to the
  85      *2 hop list
  86      *IMPORTANT!
  87      */
  88     if (if_ifwithaddr(&message_neighbors->address) != NULL)
  89       continue;
  90
  91     /* Get the main address */
  92     neigh_addr = mid_lookup_main_addr(&message_neighbors->address);
  93
  94     if (neigh_addr != NULL) {
  95       message_neighbors->address = *neigh_addr;
  96     }
  97
  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);
 100
 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;
 106
 107         /*
 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.
 111          */
 112
 113         if (olsr_cnf->lq_level > 0) {
 114           /*
 115            * loop through the one-hop neighbors that see this
 116            * 'two_hop_neighbor'
 117            */
 118
 119           struct neighbor_list_entry *walker;
 120
 121           for (walker = two_hop_neighbor->neighbor_2_nblist.next; walker != &two_hop_neighbor->neighbor_2_nblist;
 122                walker = walker->next) {
 123             /*
 124              * have we found the one-hop neighbor that sent the
 125              * HELLO message that we're current processing?
 126              */
 127
 128             if (walker->neighbor == neighbor) {
 129               walker->path_linkcost = LINK_COST_BROKEN;
 130             }
 131           }
 132         }
 133       } else {
 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;
 138
 139           two_hop_neighbor = olsr_malloc(sizeof(struct neighbor_2_entry), "Process HELLO");
 140
 141           two_hop_neighbor->neighbor_2_nblist.next = &two_hop_neighbor->neighbor_2_nblist;
 142
 143           two_hop_neighbor->neighbor_2_nblist.prev = &two_hop_neighbor->neighbor_2_nblist;
 144
 145           two_hop_neighbor->neighbor_2_pointer = 0;
 146
 147           two_hop_neighbor->neighbor_2_addr = message_neighbors->address;
 148
 149           olsr_insert_two_hop_neighbor_table(two_hop_neighbor);
 150
 151           linking_this_2_entries(neighbor, two_hop_neighbor, message->vtime);
 152         } else {
 153           /*
 154              linking to this two_hop_neighbor entry
 155            */
 156           changes_neighborhood = true;
 157           changes_topology = true;
 158
 159           linking_this_2_entries(neighbor, two_hop_neighbor, message->vtime);
 160         }
 161       }
 162     }
 163   }
 164
 165   /* Separate, second pass for link quality OLSR */
 166   /* Separate, second and third pass for link quality OLSR */
 167
 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);
 171
 172     if (!lnk)
 173       return;
 174
 175     /* calculate first hop path quality */
 176     first_hop_pathcost = lnk->linkcost;
 177     /*
 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.
 184      */
 185
 186     for (message_neighbors = message->neighbors; message_neighbors != NULL; message_neighbors = message_neighbors->next) {
 187       if (if_ifwithaddr(&message_neighbors->address) != NULL)
 188         continue;
 189
 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);
 195
 196         if (!two_hop_neighbor_yet)
 197           continue;
 198
 199         two_hop_neighbor = two_hop_neighbor_yet->neighbor_2;
 200
 201         /*
 202          *  loop through the one-hop neighbors that see this
 203          * 'two_hop_neighbor'
 204          */
 205
 206         for (walker = two_hop_neighbor->neighbor_2_nblist.next; walker != &two_hop_neighbor->neighbor_2_nblist;
 207              walker = walker->next) {
 208           /*
 209            * have we found the one-hop neighbor that sent the
 210            * HELLO message that we're current processing?
 211            */
 212
 213           if (walker->neighbor == neighbor) {
 214             olsr_linkcost new_second_hop_linkcost, new_path_linkcost;
 215
 216             // the link cost between the 1-hop neighbour and the
 217             // 2-hop neighbour
 218
 219             new_second_hop_linkcost = message_neighbors->cost;
 220
 221             // the total cost for the route
 222             // "us --- 1-hop --- 2-hop"
 223
 224             new_path_linkcost = first_hop_pathcost + new_second_hop_linkcost;
 225
 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;
 231
 232               walker->saved_path_linkcost = new_path_linkcost;
 233
 234               changes_neighborhood = true;
 235               changes_topology = true;
 236             }
 237           }
 238         }
 239       }
 240     }
 241   }
 242 }
 243
 244 /**
 245  *Links a one-hop neighbor with a 2-hop neighbor.
 246  *
 247  *@param neighbor the 1-hop neighbor
 248  *@param two_hop_neighbor the 2-hop neighbor
 249  *@param vtime the validity time
 250  */
 251 static void
 252 linking_this_2_entries(struct neighbor_entry *neighbor, struct neighbor_2_entry *two_hop_neighbor, olsr_reltime vtime)
 253 {
 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");
 256
 257   list_of_1_neighbors->neighbor = neighbor;
 258
 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;
 262
 263   /* Queue */
 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;
 266
 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 */
 271
 272   olsr_change_timer(list_of_2_neighbors->nbr2_list_timer, vtime, OLSR_NBR2_LIST_JITTER, OLSR_TIMER_ONESHOT);
 273
 274   /* Queue */
 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;
 279
 280   /*increment the pointer counter */
 281   two_hop_neighbor->neighbor_2_pointer++;
 282 }
 283
 284 /**
 285  * Check if a hello message states this node as a MPR.
 286  *
 287  * @param message the message to check
 288  * @param in_if the incoming interface
 289  *
 290  *@return 1 if we are selected as MPR 0 if not
 291  */
 292 static bool
 293 lookup_mpr_status(const struct hello_message *message, const struct interface *in_if)
 294 {
 295   struct hello_neighbor *neighbors;
 296
 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))) {
 302
 303       if (neighbors->link == SYM_LINK && neighbors->status == MPR_NEIGH) {
 304         return true;
 305       }
 306       break;
 307     }
 308   }
 309   /* Not found */
 310   return false;
 311 }
 312
 313 static int
 314 deserialize_hello(struct hello_message *hello, const void *ser)
 315 {
 316   const unsigned char *curr, *limit;
 317   uint8_t type;
 318   uint16_t size;
 319   struct ipaddr_str buf;
 320
 321   memset (hello, 0, sizeof(*hello));
 322
 323   curr = ser;
 324   pkt_get_u8(&curr, &type);
 325   if (type != HELLO_MESSAGE && type != LQ_HELLO_MESSAGE) {
 326     /* No need to do anything more */
 327     return 1;
 328   }
 329   pkt_get_reltime(&curr, &hello->vtime);
 330   pkt_get_u16(&curr, &size);
 331   pkt_get_ipaddress(&curr, &hello->source_addr);
 332
 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);
 337
 338   pkt_get_reltime(&curr, &hello->htime);
 339   pkt_get_u8(&curr, &hello->willingness);
 340
 341   hello->neighbors = NULL;
 342
 343   limit = ((const unsigned char *)ser) + size;
 344   while (curr < limit) {
 345     const unsigned char *limit2 = curr;
 346     uint8_t link_code;
 347     uint16_t size2;
 348
 349     pkt_get_u8(&curr, &link_code);
 350     pkt_ignore_u8(&curr);
 351     pkt_get_u16(&curr, &size2);
 352
 353     limit2 += 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);
 359       }
 360       neigh->link = EXTRACT_LINK(link_code);
 361       neigh->status = EXTRACT_STATUS(link_code);
 362
 363       neigh->next = hello->neighbors;
 364       hello->neighbors = neigh;
 365     }
 366   }
 367   return 0;
 368 }
 369
 370 bool
 371 olsr_input_hello(union olsr_message * ser, struct interface * inif, union olsr_ip_addr * from)
 372 {
 373   struct hello_message hello;
 374
 375   if (ser == NULL) {
 376     return false;
 377   }
 378   if (deserialize_hello(&hello, ser) != 0) {
 379     return false;
 380   }
 381   olsr_hello_tap(&hello, inif, from);
 382
 383   /* Do not forward hello messages */
 384   return false;
 385 }
 386
 387 /**
 388  *Initializing the parser functions we are using
 389  */
 390 void
 391 olsr_init_package_process(void)
 392 {
 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);
 396   } else {
 397     olsr_parser_add_function(&olsr_input_hello, LQ_HELLO_MESSAGE);
 398     olsr_parser_add_function(&olsr_input_tc, LQ_TC_MESSAGE);
 399   }
 400
 401   olsr_parser_add_function(&olsr_input_mid, MID_MESSAGE);
 402   olsr_parser_add_function(&olsr_input_hna, HNA_MESSAGE);
 403 }
 404
 405 void
 406 olsr_hello_tap(struct hello_message *message, struct interface *in_if, const union olsr_ip_addr *from_addr)
 407 {
 408   struct neighbor_entry *neighbor;
 409
 410   /*
 411    * Update link status
 412    */
 413   struct link_entry *lnk = update_link_entry(&in_if->ip_addr, from_addr, message, in_if);
 414
 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);
 426       }
 427       else
 428       {
 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));
 433       }
 434     }
 435   }
 436
 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);
 441
 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)) {
 445         /*
 446          * memorize our neighbour's idea of the link quality, so that we
 447          * know the link quality in both directions
 448          */
 449         olsr_memorize_foreign_hello_lq(lnk, walker->link != UNSPEC_LINK ? walker : NULL);
 450         break;
 451       }
 452     }
 453     /* update packet loss for link quality calculation */
 454     olsr_received_hello_handler(lnk);
 455   }
 456
 457   neighbor = lnk->neighbor;
 458
 459   /*
 460    * Hysteresis
 461    */
 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);
 466   }
 467
 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);
 472
 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);
 478     /*
 479      *If willingness changed - recalculate
 480      */
 481     neighbor->willingness = message->willingness;
 482     changes_neighborhood = true;
 483     changes_topology = true;
 484   }
 485
 486   /* Don't register neighbors of neighbors that announces WILL_NEVER */
 487   if (neighbor->willingness != WILL_NEVER)
 488     process_message_neighbors(neighbor, message);
 489
 490   /* Process changes immediately in case of MPR updates */
 491   olsr_process_changes();
 492
 493   olsr_free_hello_packet(message);
 494
 495   return;
 496 }
 497
 498 /*
 499  * Local Variables:
 500  * c-basic-offset: 2
 501  * indent-tabs-mode: nil
 502  * End:
 503  */