src/tc_set.c

   1 /*
   2  * The olsr.org Optimized Link-State Routing daemon(olsrd)
   3  * Copyright (c) 2004, Andreas Tønnesen(andreto@olsr.org)
   4  * All rights reserved.
   5  *
   6  * Redistribution and use in source and binary forms, with or without
   7  * modification, are permitted provided that the following conditions
   8  * are met:
   9  *
  10  * * Redistributions of source code must retain the above copyright
  11  *   notice, this list of conditions and the following disclaimer.
  12  * * Redistributions in binary form must reproduce the above copyright
  13  *   notice, this list of conditions and the following disclaimer in
  14  *   the documentation and/or other materials provided with the
  15  *   distribution.
  16  * * Neither the name of olsr.org, olsrd nor the names of its
  17  *   contributors may be used to endorse or promote products derived
  18  *   from this software without specific prior written permission.
  19  *
  20  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  21  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  22  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  23  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
  24  * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
  25  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
  26  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  27  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  28  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  29  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
  30  * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  31  * POSSIBILITY OF SUCH DAMAGE.
  32  *
  33  * Visit http://www.olsr.org for more information.
  34  *
  35  * If you find this software useful feel free to make a donation
  36  * to the project. For more information see the website or contact
  37  * the copyright holders.
  38  *
  39  * $Id: tc_set.c,v 1.17 2004/12/04 17:06:57 tlopatic Exp $
  40  */
  41
  42
  43 #include "tc_set.h"
  44 #include "olsr.h"
  45 #include "scheduler.h"
  46 #include "lq_route.h"
  47
  48 /**
  49  * Initialize the topology set
  50  *
  51  */
  52
  53 int
  54 olsr_init_tc()
  55 {
  56   int index;
  57
  58   /* Set timer to zero */
  59   send_empty_tc.tv_sec = 0;
  60   send_empty_tc.tv_usec = 0;
  61
  62   changes = OLSR_FALSE;
  63
  64   olsr_printf(5, "TC: init topo\n");
  65
  66   olsr_register_timeout_function(&olsr_time_out_tc_set);
  67
  68   for(index=0;index<HASHSIZE;index++)
  69     {
  70       tc_table[index].next = &tc_table[index];
  71       tc_table[index].prev = &tc_table[index];
  72     }
  73
  74   return 1;
  75 }
  76
  77
  78 /**
  79  *Delete a TC entry if it has no associated
  80  *destinations
  81  *
  82  *@param entry the TC entry to check and possibly delete
  83  *
  84  *@return 1 if entry deleted 0 if not
  85  */
  86
  87 int
  88 olsr_tc_delete_entry_if_empty(struct tc_entry *entry)
  89 {
  90
  91   //olsr_printf(1, "TC: del entry if empty\n");
  92
  93   if(entry->destinations.next == &entry->destinations)
  94     {
  95       /* dequeue */
  96       DEQUEUE_ELEM(entry);
  97       //entry->prev->next = entry->next;
  98       //entry->next->prev = entry->prev;
  99       olsr_printf(1, "TC-SET: Deleting empty entry %s ->\n", olsr_ip_to_string(&entry->T_last_addr));
 100       free(entry);
 101       return 1;
 102     }
 103   return 0;
 104 }
 105
 106
 107
 108 /**
 109  * Look up a entry from the TC tabe based
 110  * on address
 111  *
 112  *@param adr the address to look for
 113  *
 114  *@return the entry found or NULL
 115  */
 116
 117 struct tc_entry *
 118 olsr_lookup_tc_entry(union olsr_ip_addr *adr)
 119 {
 120   struct tc_entry *entries;
 121   olsr_u32_t hash;
 122
 123   //olsr_printf(1, "TC: lookup entry\n");
 124
 125   hash = olsr_hashing(adr);
 126
 127   for(entries = tc_table[hash].next;
 128       entries != &tc_table[hash];
 129       entries = entries->next)
 130     {
 131       //printf("TC lookup checking: %s\n", olsr_ip_to_string(&entries->T_last_addr));
 132       if(COMP_IP(adr, &entries->T_last_addr))
 133         return entries;
 134     }
 135
 136   return NULL;
 137 }
 138
 139
 140 /**
 141  *Add a new tc_entry to the tc set
 142  *
 143  *@param (last)adr address of the entry
 144  *
 145  *@return a pointer to the created entry
 146  */
 147
 148 struct tc_entry *
 149 olsr_add_tc_entry(union olsr_ip_addr *adr)
 150 {
 151   struct tc_entry *new_entry;
 152   olsr_u32_t hash;
 153
 154   olsr_printf(1, "TC: adding entry %s\n", olsr_ip_to_string(adr));
 155
 156   hash = olsr_hashing(adr);
 157
 158   new_entry = olsr_malloc(sizeof(struct tc_entry), "New TC entry");
 159
 160   /* Fill entry */
 161   COPY_IP(&new_entry->T_last_addr, adr);
 162   new_entry->destinations.next = &new_entry->destinations;
 163   new_entry->destinations.prev = &new_entry->destinations;
 164
 165   /* Queue entry */
 166   QUEUE_ELEM(tc_table[hash], new_entry);
 167   /*
 168   new_entry->next = tc_table[hash].next;
 169   new_entry->prev = tc_table[hash].next->prev;
 170   tc_table[hash].next->prev = new_entry;
 171   tc_table[hash].next = new_entry;
 172   */
 173
 174   return new_entry;
 175 }
 176
 177
 178 /**
 179  *Delete all destinations that have a
 180  *lower ANSN than the one in the message
 181  *
 182  *@param entry the entry to delete destenations from
 183  *@param msg the message to fetch the ANSN from
 184  *
 185  *@return 1 if any destinations were deleted 0 if not
 186  */
 187
 188 int
 189 olsr_tc_delete_mprs(struct tc_entry *entry, struct tc_message *msg)
 190 {
 191   struct topo_dst *tmp_dsts, *dst_to_del;
 192   int retval;
 193
 194   //olsr_printf(5, "TC: deleting MPRS\n");
 195
 196   tmp_dsts = entry->destinations.next;
 197   retval = 0;
 198
 199   while(tmp_dsts != &entry->destinations)
 200     {
 201       if(SEQNO_GREATER_THAN(msg->ansn, tmp_dsts->T_seq))
 202         {
 203           /* Delete entry */
 204           dst_to_del = tmp_dsts;
 205           tmp_dsts = tmp_dsts->next;
 206
 207           /* dequeue */
 208           DEQUEUE_ELEM(dst_to_del);
 209
 210           free(dst_to_del);
 211           retval = 1;
 212         }
 213       else
 214         tmp_dsts = tmp_dsts->next;
 215
 216     }
 217
 218   return retval;
 219 }
 220
 221
 222 /**
 223  *Update the destinations registered on an entry.
 224  *Creates new dest-entries if not registered.
 225  *Bases update on a receivied TC message
 226  *
 227  *@param entry the TC entry to check
 228  *@msg the TC message to update by
 229  *
 230  *@return 1 if entries are added 0 if not
 231  */
 232
 233 int
 234 olsr_tc_update_mprs(struct tc_entry *entry, struct tc_message *msg)
 235 {
 236   struct tc_mpr_addr *mprs;
 237   struct topo_dst *new_topo_dst, *existing_dst;
 238   int retval;
 239
 240   //olsr_printf(1, "TC: update MPRS\n");
 241
 242   retval = 0;
 243
 244
 245   mprs = msg->multipoint_relay_selector_address;
 246
 247   /* Add all the MPRs */
 248
 249   while(mprs != NULL)
 250     {
 251       existing_dst = olsr_tc_lookup_dst(entry, &mprs->address);
 252
 253       if(existing_dst == NULL)
 254         {
 255           /* New entry */
 256           new_topo_dst = olsr_malloc(sizeof(struct topo_dst), "add TC destination");
 257
 258           COPY_IP(&new_topo_dst->T_dest_addr, &mprs->address);
 259           olsr_get_timestamp((olsr_u32_t) msg->vtime*1000, &new_topo_dst->T_time);
 260           new_topo_dst->T_seq = msg->ansn;
 261
 262           if (olsr_cnf->lq_level > 0)
 263             {
 264               new_topo_dst->link_quality = mprs->neigh_link_quality;
 265               new_topo_dst->inverse_link_quality = mprs->link_quality;
 266
 267               new_topo_dst->saved_link_quality = new_topo_dst->link_quality;
 268               new_topo_dst->saved_inverse_link_quality =
 269                 new_topo_dst->inverse_link_quality;
 270             }
 271
 272           /* Add to queue */
 273           new_topo_dst->prev = &entry->destinations;
 274           new_topo_dst->next = entry->destinations.next;
 275           entry->destinations.next->prev = new_topo_dst;
 276           entry->destinations.next = new_topo_dst;
 277
 278           retval = 1;
 279         }
 280       else
 281         {
 282           /* Update entry */
 283           olsr_get_timestamp((olsr_u32_t) msg->vtime*1000, &existing_dst->T_time);
 284           existing_dst->T_seq = msg->ansn;
 285
 286           if (olsr_cnf->lq_level > 0)
 287             {
 288               double saved_lq, rel_lq;
 289
 290               saved_lq = existing_dst->saved_link_quality;
 291
 292               if (saved_lq == 0.0)
 293                 saved_lq = -1.0;
 294
 295               existing_dst->link_quality = mprs->neigh_link_quality;
 296
 297               rel_lq = existing_dst->link_quality / saved_lq;
 298
 299               if (rel_lq > 1.1 || rel_lq < 0.9)
 300                 {
 301                   existing_dst->saved_link_quality =
 302                     existing_dst->link_quality;
 303
 304                   retval = 1;
 305                 }
 306
 307               saved_lq = existing_dst->saved_inverse_link_quality;
 308
 309               if (saved_lq == 0.0)
 310                 saved_lq = -1.0;
 311
 312               existing_dst->inverse_link_quality = mprs->link_quality;
 313
 314               rel_lq = existing_dst->inverse_link_quality / saved_lq;
 315
 316               if (rel_lq > 1.1 || rel_lq < 0.9)
 317                 {
 318                   existing_dst->saved_inverse_link_quality =
 319                     existing_dst->inverse_link_quality;
 320
 321                   retval = 1;
 322                 }
 323             }
 324         }
 325
 326       mprs = mprs->next;
 327     }
 328
 329   return retval;
 330 }
 331
 332
 333
 334 /**
 335  *Lookup a destination in a TC entry
 336  *
 337  *@param entry the entry to check
 338  *@param dst_addr the destination address to check for
 339  *
 340  *@return a pointer to the topo_dst found - or NULL
 341  */
 342 struct topo_dst *
 343 olsr_tc_lookup_dst(struct tc_entry *entry, union olsr_ip_addr *dst_addr)
 344 {
 345   struct topo_dst *dsts;
 346
 347   //olsr_printf(1, "TC: lookup dst\n");
 348
 349   for(dsts = entry->destinations.next;
 350       dsts != &entry->destinations;
 351       dsts = dsts->next)
 352     {
 353       if(COMP_IP(dst_addr, &dsts->T_dest_addr))
 354         return dsts;
 355     }
 356   return NULL;
 357 }
 358
 359
 360
 361
 362
 363
 364 /**
 365  * Time out entries
 366  *
 367  *@return nada
 368  */
 369
 370 void
 371 olsr_time_out_tc_set()
 372 {
 373   int index, deleted;
 374   struct tc_entry *entry, *entry2;
 375   struct topo_dst *dst_entry, *dst_to_delete;
 376
 377
 378   for(index=0;index<HASHSIZE;index++)
 379     {
 380       /* For all TC entries */
 381       entry = tc_table[index].next;
 382       while(entry != &tc_table[index])
 383         {
 384           //printf("INDEX: %d\n", index);
 385           /* For all destination entries of that TC entry */
 386           deleted = 0;
 387           dst_entry = entry->destinations.next;
 388           while(dst_entry != &entry->destinations)
 389             {
 390               /* If timed out - delete */
 391               if(TIMED_OUT(&dst_entry->T_time))
 392                 {
 393                   deleted = 1;
 394                   /* Dequeue */
 395                   DEQUEUE_ELEM(dst_entry);
 396                   //dst_entry->prev->next = dst_entry->next;
 397                   //dst_entry->next->prev = dst_entry->prev;
 398
 399                   dst_to_delete = dst_entry;
 400
 401                   dst_entry = dst_entry->next;
 402
 403                   /* Delete */
 404                   free(dst_to_delete);
 405
 406                   changes_topology = OLSR_TRUE;
 407
 408                 }
 409               else
 410                 dst_entry = dst_entry->next;
 411             }
 412           /* Delete entry if no destinations */
 413           entry2 = entry;
 414           entry = entry->next;
 415           if(deleted)
 416             olsr_tc_delete_entry_if_empty(entry2);
 417         }
 418     }
 419
 420   return;
 421 }
 422
 423
 424 /**
 425  *Print the topology table to stdout
 426  */
 427 int
 428 olsr_print_tc_table()
 429 {
 430   int i;
 431   struct tc_entry *entry;
 432   struct topo_dst *dst_entry;
 433   char *fstr;
 434   float etx;
 435
 436   olsr_printf(2, "\n--- %02d:%02d:%02d.%02d ------------------------------------------------- TOPOLOGY\n\n",
 437               nowtm->tm_hour,
 438               nowtm->tm_min,
 439               nowtm->tm_sec,
 440               now.tv_usec / 10000);
 441
 442   if (olsr_cnf->ip_version == AF_INET)
 443   {
 444     olsr_printf(1, "Source IP addr   Dest IP addr     LQ     ILQ    ETX\n");
 445     fstr = "%-15s  %-15s  %5.3f  %5.3f  %.2f\n";
 446   }
 447
 448   else
 449   {
 450     olsr_printf(1, "Source IP addr                Dest IP addr                    LQ     ILQ    ETX\n");
 451     fstr = "%-30s%-30s  %5.3f  %5.3f  %.2f\n";
 452   }
 453
 454   for (i = 0; i < HASHSIZE; i++)
 455   {
 456     entry = tc_table[i].next;
 457
 458     while (entry != &tc_table[i])
 459     {
 460       dst_entry = entry->destinations.next;
 461
 462       while(dst_entry != &entry->destinations)
 463       {
 464         if (dst_entry->link_quality < MIN_LINK_QUALITY ||
 465             dst_entry->inverse_link_quality < MIN_LINK_QUALITY)
 466           etx = 0.0;
 467
 468         else
 469           etx = 1.0 / (dst_entry->link_quality *
 470                        dst_entry->inverse_link_quality);
 471
 472         olsr_printf(1, fstr, olsr_ip_to_string(&entry->T_last_addr),
 473                     olsr_ip_to_string(&dst_entry->T_dest_addr),
 474                     dst_entry->link_quality, dst_entry->inverse_link_quality,
 475                     etx);
 476
 477         dst_entry = dst_entry->next;
 478       }
 479
 480       entry = entry->next;
 481     }
 482   }
 483
 484   return 1;
 485 }