src/duplicate_set.c

   1 /*
   2  * The olsr.org Optimized Link-State Routing daemon(olsrd)
   3  * Copyright (c) 2008 Henning Rogge <rogge@fgan.de>
   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  */
  40
  41 #include "duplicate_set.h"
  42 #include "ipcalc.h"
  43 #include "common/avl.h"
  44 #include "olsr.h"
  45 #include "mid_set.h"
  46 #include "scheduler.h"
  47 #include "mantissa.h"
  48
  49 static void olsr_cleanup_duplicate_entry(void *unused);
  50
  51 struct avl_tree duplicate_set;
  52 struct timer_entry *duplicate_cleanup_timer;
  53
  54
  55 void olsr_init_duplicate_set(void) {
  56   avl_init(&duplicate_set, olsr_cnf->ip_version == AF_INET ? &avl_comp_ipv4 : &avl_comp_ipv6);
  57
  58   olsr_set_timer(&duplicate_cleanup_timer, DUPLICATE_CLEANUP_INTERVAL,
  59      DUPLICATE_CLEANUP_JITTER, OLSR_TIMER_PERIODIC,
  60      &olsr_cleanup_duplicate_entry, NULL, 0);
  61 }
  62
  63 struct dup_entry *olsr_create_duplicate_entry(void *ip, olsr_u16_t seqnr) {
  64   struct dup_entry *entry;
  65   entry = olsr_malloc(sizeof(struct dup_entry), "New duplicate entry");
  66   if (entry != NULL) {
  67     memcpy (&entry->ip, ip, olsr_cnf->ip_version == AF_INET ? sizeof(entry->ip.v4) : sizeof(entry->ip.v6));
  68     entry->seqnr = seqnr;
  69     entry->too_low_counter = 0;
  70     entry->avl.key = &entry->ip;
  71   }
  72   return entry;
  73 }
  74
  75 static void olsr_cleanup_duplicate_entry(void __attribute__ ((unused)) *unused) {
  76   struct dup_entry *entry;
  77
  78   OLSR_FOR_ALL_DUP_ENTRIES(entry) {
  79     if (TIMED_OUT(entry->valid_until)) {
  80       avl_delete(&duplicate_set, &entry->avl);
  81       free (entry);
  82     }
  83   } OLSR_FOR_ALL_DUP_ENTRIES_END(entry);
  84 }
  85
  86 int olsr_shall_process_message(void *ip, olsr_u16_t seqnr) {
  87   struct dup_entry *entry;
  88   int diff;
  89   void *mainIp;
  90   clock_t valid_until;
  91
  92   struct ipaddr_str buf;
  93   // get main address
  94   mainIp = mid_lookup_main_addr(ip);
  95   if (mainIp == NULL) {
  96     mainIp = ip;
  97   }
  98
  99   valid_until = GET_TIMESTAMP(DUPLICATE_VTIME);
 100
 101   entry = (struct dup_entry *)avl_find(&duplicate_set, ip);
 102   if (entry == NULL) {
 103     entry = olsr_create_duplicate_entry(ip, seqnr);
 104     if (entry != NULL) {
 105       avl_insert(&duplicate_set, &entry->avl, 0);
 106       entry->valid_until = valid_until;
 107     }
 108     return 1; // okay, we process this package
 109   }
 110
 111   diff = (int)seqnr - (int)(entry->seqnr);
 112
 113   // update timestamp
 114   if (valid_until > entry->valid_until) {
 115     entry->valid_until = valid_until;
 116   }
 117
 118   // overflow ?
 119   if (diff > (1<<15)) {
 120     diff -= (1<<16);
 121   }
 122
 123   if (diff < -31) {
 124     entry->too_low_counter ++;
 125
 126     // client did restart with a lower number ?
 127     if (entry->too_low_counter > 16) {
 128       entry->too_low_counter = 0;
 129       entry->seqnr = seqnr;
 130       entry->array = 1;
 131       return 1;
 132     }
 133     OLSR_PRINTF(9, "blocked %x from %s\n", seqnr, olsr_ip_to_string(&buf, mainIp));
 134     return 0;
 135   }
 136
 137   entry->too_low_counter = 0;
 138   if (diff <= 0) {
 139     olsr_u32_t bitmask = 1 << ((olsr_u32_t) (-diff));
 140
 141     if ((entry->array & bitmask) != 0) {
 142       OLSR_PRINTF(9, "blocked %x (diff=%d,mask=%08x) from %s\n", seqnr, diff, entry->array, olsr_ip_to_string(&buf, mainIp));
 143       return 0;
 144     }
 145     entry->array |= bitmask;
 146     OLSR_PRINTF(9, "processed %x from %s\n", seqnr, olsr_ip_to_string(&buf, mainIp));
 147     return 1;
 148   }
 149   else if (diff < 32) {
 150     entry->array <<= (olsr_u32_t)diff;
 151   }
 152   else {
 153     entry->array = 0;
 154   }
 155   entry->array |= 1;
 156   entry->seqnr = seqnr;
 157   OLSR_PRINTF(9, "processed %x from %s\n", seqnr, olsr_ip_to_string(&buf, mainIp));
 158   return 1;
 159 }
 160
 161 void olsr_print_duplicate_table(void) {
 162 #ifndef NODEBUG
 163   /* The whole function makes no sense without it. */
 164   struct dup_entry *entry;
 165   const int ipwidth = olsr_cnf->ip_version == AF_INET ? 15 : 30;
 166   struct ipaddr_str addrbuf;
 167
 168   OLSR_PRINTF(1,
 169         "\n--- %s ------------------------------------------------- DUPLICATE SET\n\n"
 170         "%-*s %8s %s\n", olsr_wallclock_string(), ipwidth,
 171         "Node IP", "DupArray", "VTime");
 172
 173   OLSR_FOR_ALL_DUP_ENTRIES(entry) {
 174     OLSR_PRINTF(1, "%-*s %08x %s\n",
 175         ipwidth, olsr_ip_to_string(&addrbuf, (union olsr_ip_addr *)(entry->avl.key)),
 176         entry->array,
 177         olsr_clock_string(entry->valid_until));
 178   } OLSR_FOR_ALL_DUP_ENTRIES_END(entry);
 179 #endif
 180 }