src/lq_packet.c

   1
   2 /*
   3  * The olsr.org Optimized Link-State Routing daemon(olsrd)
   4  * Copyright (c) 2004-2009, the olsr.org team - see HISTORY file
   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 "ipcalc.h"
  43 #include "olsr_protocol.h"
  44 #include "defs.h"
  45 #include "lq_packet.h"
  46 #include "interfaces.h"
  47 #include "link_set.h"
  48 #include "neighbor_table.h"
  49 #include "mid_set.h"
  50 #include "olsr_time.h"
  51 #include "process_package.h"    // XXX - remove
  52 #include "olsr.h"
  53 #include "build_msg.h"
  54 #include "net_olsr.h"
  55 #include "lq_plugin.h"
  56 #include "olsr_logging.h"
  57
  58 #include <stdlib.h>
  59
  60 bool lq_tc_pending = false;
  61
  62 static unsigned char msg_buffer[MAXMESSAGESIZE - OLSR_HEADERSIZE];
  63
  64 static uint16_t local_ansn_number = 0;
  65
  66 uint16_t get_local_ansn_number(bool increase) {
  67   if (increase)
  68     local_ansn_number++;
  69   return local_ansn_number;
  70 }
  71
  72
  73 static void
  74 create_lq_hello(struct lq_hello_message *lq_hello, struct interface *outif)
  75 {
  76   struct link_entry *walker;
  77
  78   // initialize the static fields
  79
  80   lq_hello->comm.type = olsr_get_Hello_MessageId();
  81   lq_hello->comm.vtime = me_to_reltime(outif->valtimes.hello);
  82   lq_hello->comm.size = 0;
  83
  84   lq_hello->comm.orig = olsr_cnf->router_id;
  85
  86   lq_hello->comm.ttl = 1;
  87   lq_hello->comm.hops = 0;
  88
  89   lq_hello->htime = outif->hello_etime;
  90   lq_hello->will = olsr_cnf->willingness;
  91
  92   lq_hello->neigh = NULL;
  93
  94   // loop through the link set
  95
  96   OLSR_FOR_ALL_LINK_ENTRIES(walker) {
  97
  98     // allocate a neighbour entry
  99     struct lq_hello_neighbor *neigh = olsr_malloc_lq_hello_neighbor();
 100
 101     // a) this neighbor interface IS NOT visible via the output interface
 102     if (olsr_ipcmp(&walker->local_iface_addr, &outif->ip_addr) != 0)
 103       neigh->link_type = UNSPEC_LINK;
 104
 105     // b) this neighbor interface IS visible via the output interface
 106
 107     else
 108       neigh->link_type = lookup_link_status(walker);
 109
 110     // set the entry's link quality
 111     olsr_copy_hello_lq(neigh, walker);
 112
 113     // set the entry's neighbour type
 114
 115     if (walker->neighbor->is_mpr)
 116       neigh->neigh_type = MPR_NEIGH;
 117
 118     else if (walker->neighbor->is_sym)
 119       neigh->neigh_type = SYM_NEIGH;
 120
 121     else
 122       neigh->neigh_type = NOT_NEIGH;
 123
 124     // set the entry's neighbour interface address
 125
 126     neigh->addr = walker->neighbor_iface_addr;
 127
 128     // queue the neighbour entry
 129     neigh->next = lq_hello->neigh;
 130     lq_hello->neigh = neigh;
 131
 132   }
 133   OLSR_FOR_ALL_LINK_ENTRIES_END(walker);
 134 }
 135
 136 void
 137 destroy_lq_hello(struct lq_hello_message *lq_hello)
 138 {
 139   struct lq_hello_neighbor *walker, *aux;
 140
 141   // loop through the queued neighbour entries and free them
 142
 143   for (walker = lq_hello->neigh; walker != NULL; walker = aux) {
 144     aux = walker->next;
 145     olsr_free_lq_hello_neighbor(walker);
 146   }
 147
 148   lq_hello->neigh = NULL;
 149 }
 150
 151 static void
 152 create_lq_tc(struct lq_tc_message *lq_tc, struct interface *outif)
 153 {
 154   struct link_entry *lnk;
 155   struct nbr_entry *walker;
 156   struct tc_mpr_addr *neigh;
 157   static int ttl_list[] = { 2, 8, 2, 16, 2, 8, 2, MAX_TTL };
 158
 159   // remember that we have generated an LQ TC message; this is
 160   // checked in net_output()
 161
 162   lq_tc_pending = true;
 163
 164   // initialize the static fields
 165
 166   lq_tc->comm.type = olsr_get_TC_MessageId();
 167   lq_tc->comm.vtime = me_to_reltime(outif->valtimes.tc);
 168   lq_tc->comm.size = 0;
 169
 170   lq_tc->comm.orig = olsr_cnf->router_id;
 171
 172   if (olsr_cnf->lq_fish > 0) {
 173     if (outif->ttl_index >= (int)(ARRAYSIZE(ttl_list)))
 174       outif->ttl_index = 0;
 175
 176     lq_tc->comm.ttl = (0 <= outif->ttl_index ? ttl_list[outif->ttl_index] : MAX_TTL);
 177     outif->ttl_index++;
 178
 179     OLSR_DEBUG(LOG_PACKET_CREATION, "Creating LQ TC with TTL %d.\n", lq_tc->comm.ttl);
 180   }
 181
 182   else
 183     lq_tc->comm.ttl = MAX_TTL;
 184
 185   lq_tc->comm.hops = 0;
 186
 187   lq_tc->from = olsr_cnf->router_id;
 188
 189   lq_tc->ansn = get_local_ansn_number(false);
 190
 191   lq_tc->neigh = NULL;
 192
 193   OLSR_FOR_ALL_NBR_ENTRIES(walker) {
 194
 195     /*
 196      * TC redundancy 2
 197      *
 198      * Only consider symmetric neighbours.
 199      */
 200     if (!walker->is_sym) {
 201       continue;
 202     }
 203
 204     /*
 205      * TC redundancy 1
 206      *
 207      * Only consider MPRs and MPR selectors
 208      */
 209     if (olsr_cnf->tc_redundancy == 1 && !walker->is_mpr && walker->mprs_count == 0) {
 210       continue;
 211     }
 212
 213     /*
 214      * TC redundancy 0
 215      *
 216      * Only consider MPR selectors
 217      */
 218     if (olsr_cnf->tc_redundancy == 0 && walker->mprs_count == 0) {
 219       continue;
 220     }
 221
 222     /* Set the entry's link quality */
 223     lnk = get_best_link_to_neighbor(&walker->nbr_addr);
 224     if (!lnk) {
 225       continue;                 // no link ?
 226     }
 227
 228     if (lnk->linkcost >= LINK_COST_BROKEN) {
 229       continue;                 // don't advertise links with very low LQ
 230     }
 231
 232     /* Allocate a neighbour entry. */
 233     neigh = olsr_malloc_tc_mpr_addr();
 234
 235     /* Set the entry's main address. */
 236     neigh->address = walker->nbr_addr;
 237
 238     if (lnk) {
 239       olsr_copylq_link_entry_2_tc_mpr_addr(neigh, lnk);
 240     }
 241
 242     /* Queue the neighbour entry. */
 243
 244     // TODO: ugly hack until neighbor table is ported to avl tree
 245
 246     if (lq_tc->neigh == NULL || avl_comp_default(&lq_tc->neigh->address, &neigh->address) > 0) {
 247       neigh->next = lq_tc->neigh;
 248       lq_tc->neigh = neigh;
 249     } else {
 250       struct tc_mpr_addr *last = lq_tc->neigh, *n = last->next;
 251
 252       while (n) {
 253         if (avl_comp_default(&n->address, &neigh->address) > 0) {
 254           break;
 255         }
 256         last = n;
 257         n = n->next;
 258       }
 259       neigh->next = n;
 260       last->next = neigh;
 261     }
 262
 263     // neigh->next = lq_tc->neigh;
 264     // lq_tc->neigh = neigh;
 265
 266   }
 267   OLSR_FOR_ALL_NBR_ENTRIES_END(walker);
 268 }
 269
 270 static void
 271 destroy_lq_tc(struct lq_tc_message *lq_tc)
 272 {
 273   struct tc_mpr_addr *walker, *aux;
 274
 275   // loop through the queued neighbour entries and free them
 276
 277   for (walker = lq_tc->neigh; walker != NULL; walker = aux) {
 278     aux = walker->next;
 279     olsr_free_tc_mpr_addr(walker);
 280   }
 281 }
 282
 283 static int
 284 common_size(void)
 285 {
 286   // return the size of the header shared by all OLSR messages
 287
 288   return (olsr_cnf->ip_version == AF_INET) ? sizeof(struct olsr_header_v4) : sizeof(struct olsr_header_v6);
 289 }
 290
 291 static void
 292 serialize_common(struct olsr_common *comm)
 293 {
 294   if (olsr_cnf->ip_version == AF_INET) {
 295     // serialize an IPv4 OLSR message header
 296     struct olsr_header_v4 *olsr_head_v4 = (struct olsr_header_v4 *)msg_buffer;
 297
 298     olsr_head_v4->type = comm->type;
 299     olsr_head_v4->vtime = reltime_to_me(comm->vtime);
 300     olsr_head_v4->size = htons(comm->size);
 301
 302     olsr_head_v4->orig = comm->orig.v4.s_addr;
 303
 304     olsr_head_v4->ttl = comm->ttl;
 305     olsr_head_v4->hops = comm->hops;
 306     olsr_head_v4->seqno = htons(get_msg_seqno());
 307   } else {
 308     // serialize an IPv6 OLSR message header
 309     struct olsr_header_v6 *olsr_head_v6 = (struct olsr_header_v6 *)msg_buffer;
 310
 311     olsr_head_v6->type = comm->type;
 312     olsr_head_v6->vtime = reltime_to_me(comm->vtime);
 313     olsr_head_v6->size = htons(comm->size);
 314
 315     memcpy(&olsr_head_v6->orig, &comm->orig.v6.s6_addr, sizeof(olsr_head_v6->orig));
 316
 317     olsr_head_v6->ttl = comm->ttl;
 318     olsr_head_v6->hops = comm->hops;
 319     olsr_head_v6->seqno = htons(get_msg_seqno());
 320   }
 321 }
 322
 323 static void
 324 serialize_lq_hello(struct lq_hello_message *lq_hello, struct interface *outif)
 325 {
 326   static const int LINK_ORDER[] = { SYM_LINK, UNSPEC_LINK, ASYM_LINK, LOST_LINK };
 327   int rem, size, req, expected_size = 0;
 328   struct lq_hello_info_header *info_head;
 329   struct lq_hello_neighbor *neigh;
 330   unsigned char *buff;
 331   bool is_first;
 332   int i;
 333
 334   // leave space for the OLSR header
 335   int off = common_size();
 336
 337   // initialize the LQ_HELLO header
 338
 339   struct lq_hello_header *head = (struct lq_hello_header *)(msg_buffer + off);
 340
 341   head->reserved = 0;
 342   head->htime = reltime_to_me(lq_hello->htime);
 343   head->will = lq_hello->will;
 344
 345   // 'off' is the offset of the byte following the LQ_HELLO header
 346
 347   off += sizeof(struct lq_hello_header);
 348
 349   // our work buffer starts at 'off'...
 350
 351   buff = msg_buffer + off;
 352
 353   // ... that's why we start with a 'size' of 0 and subtract 'off' from
 354   // the remaining bytes in the output buffer
 355
 356   size = 0;
 357   rem = net_outbuffer_bytes_left(outif) - off;
 358
 359   /*
 360    * Initially, we want to put the complete lq_hello into the message.
 361    * For this flush the output buffer (if there are some bytes in).
 362    * This is a hack/fix, which prevents message fragementation resulting
 363    * in instable links. The ugly lq/genmsg code should be reworked anyhow.
 364    */
 365   if (0 < net_output_pending(outif)) {
 366     for (i = 0; i <= MAX_NEIGH; i++) {
 367       unsigned int j;
 368       for (j = 0; j < ARRAYSIZE(LINK_ORDER); j++) {
 369         is_first = true;
 370         for (neigh = lq_hello->neigh; neigh != NULL; neigh = neigh->next) {
 371           if (0 == i && 0 == j)
 372             expected_size += olsr_cnf->ipsize + 4;
 373           if (neigh->neigh_type == i && neigh->link_type == LINK_ORDER[j]) {
 374             if (is_first) {
 375               expected_size += sizeof(struct lq_hello_info_header);
 376               is_first = false;
 377             }
 378           }
 379         }
 380       }
 381     }
 382   }
 383
 384   if (rem < expected_size) {
 385     net_output(outif);
 386     rem = net_outbuffer_bytes_left(outif) - off;
 387   }
 388
 389   info_head = NULL;
 390
 391   // iterate through all neighbor types ('i') and all link types ('j')
 392
 393   for (i = 0; i <= MAX_NEIGH; i++) {
 394     unsigned int j;
 395     for (j = 0; j < ARRAYSIZE(LINK_ORDER); j++) {
 396       is_first = true;
 397
 398       // loop through neighbors
 399
 400       for (neigh = lq_hello->neigh; neigh != NULL; neigh = neigh->next) {
 401         if (neigh->neigh_type != i || neigh->link_type != LINK_ORDER[j])
 402           continue;
 403
 404         // we need space for an IP address plus link quality
 405         // information
 406
 407         req = olsr_cnf->ipsize + 4;
 408
 409         // no, we also need space for an info header, as this is the
 410         // first neighbor with the current neighor type and link type
 411
 412         if (is_first)
 413           req += sizeof(struct lq_hello_info_header);
 414
 415         // we do not have enough space left
 416
 417         // force signed comparison
 418
 419         if ((int)(size + req) > rem) {
 420           // finalize the OLSR header
 421
 422           lq_hello->comm.size = size + off;
 423
 424           serialize_common(&lq_hello->comm);
 425
 426           // finalize the info header
 427
 428           info_head->size = ntohs(buff + size - (unsigned char *)info_head);
 429
 430           // output packet
 431
 432           net_outbuffer_push(outif, msg_buffer, size + off);
 433
 434           net_output(outif);
 435
 436           // move to the beginning of the buffer
 437
 438           size = 0;
 439           rem = net_outbuffer_bytes_left(outif) - off;
 440
 441           // we need a new info header
 442
 443           is_first = true;
 444         }
 445         // create a new info header
 446
 447         if (is_first) {
 448           info_head = (struct lq_hello_info_header *)(buff + size);
 449           size += sizeof(struct lq_hello_info_header);
 450
 451           info_head->reserved = 0;
 452           info_head->link_code = CREATE_LINK_CODE(i, LINK_ORDER[j]);
 453         }
 454         // add the current neighbor's IP address
 455
 456         genipcopy(buff + size, &neigh->addr);
 457         size += olsr_cnf->ipsize;
 458
 459         // add the corresponding link quality
 460         size += olsr_serialize_hello_lq_pair(&buff[size], neigh);
 461
 462         is_first = false;
 463       }
 464
 465       // finalize the info header, if there are any neighbors with the
 466       // current neighbor type and link type
 467
 468       if (!is_first)
 469         info_head->size = ntohs(buff + size - (unsigned char *)info_head);
 470     }
 471   }
 472
 473   // finalize the OLSR header
 474
 475   lq_hello->comm.size = size + off;
 476
 477   serialize_common((struct olsr_common *)lq_hello);
 478
 479   // move the message to the output buffer
 480
 481   net_outbuffer_push(outif, msg_buffer, size + off);
 482 }
 483
 484 static uint8_t
 485 calculate_border_flag(void *lower_border, void *higher_border)
 486 {
 487   uint8_t *lower = lower_border;
 488   uint8_t *higher = higher_border;
 489   uint8_t bitmask;
 490   uint8_t part, bitpos;
 491
 492   for (part = 0; part < olsr_cnf->ipsize; part++) {
 493     if (lower[part] != higher[part]) {
 494       break;
 495     }
 496   }
 497
 498   if (part == olsr_cnf->ipsize) {       // same IPs ?
 499     return 0;
 500   }
 501   // look for first bit of difference
 502   bitmask = 0xfe;
 503   for (bitpos = 0; bitpos < 8; bitpos++, bitmask <<= 1) {
 504     if ((lower[part] & bitmask) == (higher[part] & bitmask)) {
 505       break;
 506     }
 507   }
 508
 509   bitpos += 8 * (olsr_cnf->ipsize - part - 1);
 510   return bitpos + 1;
 511 }
 512
 513 static void
 514 serialize_lq_tc(struct lq_tc_message *lq_tc, struct interface *outif)
 515 {
 516   int off, rem, size, expected_size = 0;
 517   struct lq_tc_header *head;
 518   struct tc_mpr_addr *neigh;
 519   unsigned char *buff;
 520
 521   union olsr_ip_addr *last_ip = NULL;
 522   uint8_t left_border_flag = 0xff;
 523
 524   // leave space for the OLSR header
 525
 526   off = common_size();
 527
 528   // initialize the LQ_TC header
 529
 530   head = (struct lq_tc_header *)(msg_buffer + off);
 531
 532   head->ansn = htons(lq_tc->ansn);
 533   head->lower_border = 0;
 534   head->upper_border = 0;
 535
 536   // 'off' is the offset of the byte following the LQ_TC header
 537
 538   off += sizeof(struct lq_tc_header);
 539
 540   // our work buffer starts at 'off'...
 541
 542   buff = msg_buffer + off;
 543
 544   // ... that's why we start with a 'size' of 0 and subtract 'off' from
 545   // the remaining bytes in the output buffer
 546
 547   size = 0;
 548   rem = net_outbuffer_bytes_left(outif) - off;
 549
 550   /*
 551    * Initially, we want to put the complete lq_tc into the message.
 552    * For this flush the output buffer (if there are some bytes in).
 553    * This is a hack/fix, which prevents message fragementation resulting
 554    * in instable links. The ugly lq/genmsg code should be reworked anyhow.
 555    */
 556   if (0 < net_output_pending(outif)) {
 557     for (neigh = lq_tc->neigh; neigh != NULL; neigh = neigh->next) {
 558       // TODO sizeof_tc_lq function required
 559       expected_size += olsr_cnf->ipsize + 4;
 560     }
 561   }
 562
 563   if (rem < expected_size) {
 564     net_output(outif);
 565     rem = net_outbuffer_bytes_left(outif) - off;
 566   }
 567   // loop through neighbors
 568
 569   for (neigh = lq_tc->neigh; neigh != NULL; neigh = neigh->next) {
 570     // we need space for an IP address plus link quality
 571     // information
 572
 573     // force signed comparison
 574
 575     // TODO sizeof_tc_lq function required
 576     if ((int)(size + olsr_cnf->ipsize + 4) > rem) {
 577       head->lower_border = left_border_flag;
 578       head->upper_border = calculate_border_flag(last_ip, &neigh->address);
 579       left_border_flag = head->upper_border;
 580
 581       // finalize the OLSR header
 582
 583       lq_tc->comm.size = size + off;
 584
 585       serialize_common((struct olsr_common *)lq_tc);
 586
 587       // output packet
 588
 589       net_outbuffer_push(outif, msg_buffer, size + off);
 590
 591       net_output(outif);
 592
 593       // move to the beginning of the buffer
 594
 595       size = 0;
 596       rem = net_outbuffer_bytes_left(outif) - off;
 597     }
 598     // add the current neighbor's IP address
 599     genipcopy(buff + size, &neigh->address);
 600
 601     // remember last ip
 602     last_ip = (union olsr_ip_addr *)(buff + size);
 603
 604     size += olsr_cnf->ipsize;
 605
 606     // add the corresponding link quality
 607     size += olsr_serialize_tc_lq_pair(&buff[size], neigh);
 608   }
 609
 610   // finalize the OLSR header
 611
 612   head->lower_border = left_border_flag;
 613   head->upper_border = 0xff;
 614   lq_tc->comm.size = size + off;
 615
 616   serialize_common((struct olsr_common *)lq_tc);
 617
 618   net_outbuffer_push(outif, msg_buffer, size + off);
 619 }
 620
 621 void
 622 olsr_output_lq_hello(void *para)
 623 {
 624   struct lq_hello_message lq_hello;
 625   struct interface *outif = para;
 626
 627   if (outif == NULL) {
 628     return;
 629   }
 630   // create LQ_HELLO in internal format
 631   create_lq_hello(&lq_hello, outif);
 632
 633   // convert internal format into transmission format, send it
 634   serialize_lq_hello(&lq_hello, outif);
 635
 636   // destroy internal format
 637   destroy_lq_hello(&lq_hello);
 638
 639   if (net_output_pending(outif)) {
 640     if (outif->immediate_send_tc) {
 641       set_buffer_timer(outif);
 642     } else {
 643       net_output(outif);
 644     }
 645   }
 646 }
 647
 648 /**
 649  * Callback for TC generation timer.
 650  */
 651 void
 652 olsr_output_lq_tc(void *ctx)
 653 {
 654   struct lq_tc_message lq_tc;
 655   struct interface *outif = ctx;
 656
 657   if (outif == NULL) {
 658     return;
 659   }
 660
 661   /* create LQ_TC in internal format */
 662   create_lq_tc(&lq_tc, outif);
 663
 664   /* empty message ? */
 665   if (!lq_tc.neigh) {
 666     return;
 667   }
 668
 669   /* convert internal format into transmission format, send it */
 670   serialize_lq_tc(&lq_tc, outif);
 671
 672   /* destroy internal format */
 673   destroy_lq_tc(&lq_tc);
 674
 675   if (net_output_pending(outif)) {
 676     if (!outif->immediate_send_tc) {
 677       set_buffer_timer(outif);
 678     } else {
 679       net_output(outif);
 680     }
 681   }
 682 }
 683
 684 /*
 685  * Local Variables:
 686  * c-basic-offset: 2
 687  * indent-tabs-mode: nil
 688  * End:
 689  */