Backport from Henning Rogge: first prototype of new duplicate detection algorithm
authorSven-Ola Tuecke <sven-ola@gmx.de>
Sat, 22 Nov 2008 08:24:32 +0000 (09:24 +0100)
committerSven-Ola Tuecke <sven-ola@gmx.de>
Sat, 22 Nov 2008 08:24:32 +0000 (09:24 +0100)
12 files changed:
lib/nameservice/src/nameservice.c
lib/tas/src/plugin.c
src/duplicate_set.c
src/duplicate_set.h
src/hna_set.c
src/ipc_frontend.c
src/mid_set.c
src/olsr.c
src/parser.c
src/parser.h
src/process_package.c
src/tc_set.c

index 08ce959..6a6a733 100644 (file)
@@ -459,7 +459,7 @@ name_init (void)
   my_services = remove_nonvalid_names_from_list (my_services, NAME_SERVICE);
 
   /* register functions with olsrd */
-  olsr_parser_add_function (&olsr_parser, PARSER_TYPE, 1);
+  olsr_parser_add_function (&olsr_parser, PARSER_TYPE);
 
   /* periodic message generation */
   msg_gen_timer =
@@ -761,10 +761,6 @@ olsr_parser (union olsr_message *m, struct interface *in_if
     }
 
   update_name_entry (&originator, namemessage, size, vtime);
-
-  /* Forward the message if nessecary
-   * default_fwd does all the work for us! */
-  olsr_forward_message (m, ipaddr);
 }
 
 /**
index f7afda4..419066e 100644 (file)
@@ -398,8 +398,6 @@ parserFunc (union olsr_message *msg, struct interface *inInt
     }
 
   httpAddTasMessage (service, string, rawIpAddrToString (orig, ipAddrLen));
-
-  olsr_forward_message (msg, neighIntAddr);
 }
 
 void
@@ -496,7 +494,7 @@ olsrd_plugin_init (void)
   olsr_start_timer (OLSR_TAS_SERVICE_INT, 0, OLSR_TIMER_PERIODIC,
                     &serviceFunc, NULL, 0);
 
-  olsr_parser_add_function (parserFunc, MESSAGE_TYPE, 1);
+  olsr_parser_add_function (parserFunc, MESSAGE_TYPE);
 
   return 0;
 }
index 1e47478..b77cac5 100644 (file)
@@ -76,6 +76,8 @@ olsr_create_duplicate_entry (void *ip, olsr_u16_t seqnr)
       entry->seqnr = seqnr;
       entry->too_low_counter = 0;
       entry->avl.key = &entry->ip;
+      entry->forwardedArray = 0;
+      entry->processedArray = 0;
     }
   return entry;
 }
@@ -97,14 +99,15 @@ olsr_cleanup_duplicate_entry (void __attribute__ ((unused)) * unused)
 }
 
 int
-olsr_shall_process_message (void *ip, olsr_u16_t seqnr)
+olsr_message_is_duplicate (void *ip, olsr_u16_t seqnr, olsr_bool forwarding)
 {
   struct dup_entry *entry;
   int diff;
   void *mainIp;
   clock_t valid_until;
-
+  u_int32_t *array;
   struct ipaddr_str buf;
+
   // get main address
   mainIp = mid_lookup_main_addr (ip);
   if (mainIp == NULL)
@@ -123,7 +126,7 @@ olsr_shall_process_message (void *ip, olsr_u16_t seqnr)
           avl_insert (&duplicate_set, &entry->avl, 0);
           entry->valid_until = valid_until;
         }
-      return 1;                 // okay, we process this package
+      return OLSR_FALSE;        // okay, we process this package
     }
 
   diff = (int) seqnr - (int) (entry->seqnr);
@@ -140,6 +143,7 @@ olsr_shall_process_message (void *ip, olsr_u16_t seqnr)
       diff -= (1 << 16);
     }
 
+  array = forwarding ? &entry->forwardedArray : &entry->processedArray;
   if (diff < -31)
     {
       entry->too_low_counter++;
@@ -149,12 +153,12 @@ olsr_shall_process_message (void *ip, olsr_u16_t seqnr)
         {
           entry->too_low_counter = 0;
           entry->seqnr = seqnr;
-          entry->array = 1;
-          return 1;
+          *array = 1;
+          return OLSR_FALSE;    /* start with a new sequence number, so NO duplicate */
         }
       OLSR_PRINTF (9, "blocked %x from %s\n", seqnr,
                    olsr_ip_to_string (&buf, mainIp));
-      return 0;
+      return OLSR_TRUE;         /* duplicate ! */
     }
 
   entry->too_low_counter = 0;
@@ -162,30 +166,30 @@ olsr_shall_process_message (void *ip, olsr_u16_t seqnr)
     {
       olsr_u32_t bitmask = 1 << ((olsr_u32_t) (-diff));
 
-      if ((entry->array & bitmask) != 0)
+      if (((*array) & bitmask) != 0)
         {
           OLSR_PRINTF (9, "blocked %x (diff=%d,mask=%08x) from %s\n", seqnr,
-                       diff, entry->array, olsr_ip_to_string (&buf, mainIp));
-          return 0;
+                       diff, *array, olsr_ip_to_string (&buf, mainIp));
+          return OLSR_TRUE;     /* duplicate ! */
         }
-      entry->array |= bitmask;
+      *array |= bitmask;
       OLSR_PRINTF (9, "processed %x from %s\n", seqnr,
                    olsr_ip_to_string (&buf, mainIp));
-      return 1;
+      return OLSR_FALSE;        /* no duplicate */
     }
   else if (diff < 32)
     {
-      entry->array <<= (olsr_u32_t) diff;
+      *array <<= (olsr_u32_t) diff;
     }
   else
     {
-      entry->array = 0;
+      *array = 0;
     }
-  entry->array |= 1;
+  *array |= 1;
   entry->seqnr = seqnr;
   OLSR_PRINTF (9, "processed %x from %s\n", seqnr,
                olsr_ip_to_string (&buf, mainIp));
-  return 1;
+  return OLSR_FALSE;            /* no duplicate */
 }
 
 void
@@ -207,7 +211,8 @@ olsr_print_duplicate_table (void)
     OLSR_PRINTF (1, "%-*s %08x %s\n", ipwidth,
                  olsr_ip_to_string (&addrbuf,
                                     (union olsr_ip_addr *) (entry->avl.key)),
-                 entry->array, olsr_clock_string (entry->valid_until));
+                 entry->processedArray,
+                 olsr_clock_string (entry->valid_until));
   } OLSR_FOR_ALL_DUP_ENTRIES_END (entry);
 #endif
 }
index 4920583..3a9115f 100644 (file)
@@ -56,7 +56,7 @@ struct dup_entry
   union olsr_ip_addr ip;
   olsr_u16_t seqnr;
   olsr_u16_t too_low_counter;
-  olsr_u32_t array;
+  olsr_u32_t processedArray, forwardedArray;
   clock_t valid_until;
 };
 
@@ -64,7 +64,8 @@ AVLNODE2STRUCT (duptree2dupentry, struct dup_entry, avl);
 
 void olsr_init_duplicate_set (void);
 struct dup_entry *olsr_create_duplicate_entry (void *ip, olsr_u16_t seqnr);
-int olsr_shall_process_message (void *ip, olsr_u16_t seqnr);
+int olsr_message_is_duplicate (void *ip, olsr_u16_t seqnr,
+                               olsr_bool forwarding);
 void olsr_print_duplicate_table (void);
 
 #define OLSR_FOR_ALL_DUP_ENTRIES(dup) \
index 43c7495..163f183 100644 (file)
@@ -482,7 +482,6 @@ olsr_input_hna (union olsr_message *m, struct interface *in_if
         }
     }
 #endif
-  olsr_forward_message (m, from_addr);
 }
 
 /*
index 285f493..15e536d 100644 (file)
@@ -86,7 +86,7 @@ ipc_init (void)
   int yes = 1;
 
   /* Add parser function */
-  olsr_parser_add_function (&frontend_msgparser, PROMISCUOUS, 0);
+  olsr_parser_add_function (&frontend_msgparser, PROMISCUOUS);
 
   /* get an internet domain socket */
   if ((ipc_sock = socket (AF_INET, SOCK_STREAM, 0)) == -1)
index 959e318..ce023f1 100644 (file)
@@ -645,8 +645,6 @@ olsr_input_mid (union olsr_message *m, struct interface *in_if
     }
 
   olsr_prune_aliases (&message.mid_origaddr, message.mid_addr);
-
-  olsr_forward_message (m, from_addr);
   olsr_free_mid_packet (&message);
 }
 
index 3fa971d..e963582 100644 (file)
@@ -318,12 +318,12 @@ olsr_forward_message (union olsr_message *m, union olsr_ip_addr *from_addr)
    */
   if (AF_INET == olsr_cnf->ip_version)
     {
-      if (2 > m->v4.ttl || 255 < (int) m->v4.hopcnt + (int) m->v4.ttl)
+      if (m->v4.ttl < 2 || 255 < (int) m->v4.hopcnt + (int) m->v4.ttl)
         return 0;
     }
   else
     {
-      if (2 > m->v6.ttl || 255 < (int) m->v6.hopcnt + (int) m->v6.ttl)
+      if (m->v6.ttl < 2 || 255 < (int) m->v6.hopcnt + (int) m->v6.ttl)
         return 0;
     }
 
@@ -350,6 +350,22 @@ olsr_forward_message (union olsr_message *m, union olsr_ip_addr *from_addr)
       return 0;
     }
 
+  /* check if we already forwarded this message */
+  if (AF_INET == olsr_cnf->ip_version)
+    {
+      if (olsr_message_is_duplicate (from_addr, m->v4.seqno, OLSR_TRUE))
+        {
+          return 0;             /* it's a duplicate, forget about it */
+        }
+    }
+  else
+    {
+      if (olsr_message_is_duplicate (from_addr, m->v6.seqno, OLSR_TRUE))
+        {
+          return 0;             /* it's a duplicate, forget about it */
+        }
+    }
+
   /* Treat TTL hopcnt */
   if (olsr_cnf->ip_version == AF_INET)
     {
index ce4eaf8..6617ff3 100644 (file)
@@ -100,8 +100,7 @@ olsr_init_parser (void)
 }
 
 void
-olsr_parser_add_function (parse_function * function, olsr_u32_t type,
-                          int forwarding)
+olsr_parser_add_function (parse_function * function, olsr_u32_t type)
 {
   struct parse_function_entry *new_entry;
 
@@ -113,7 +112,6 @@ olsr_parser_add_function (parse_function * function, olsr_u32_t type,
 
   new_entry->function = function;
   new_entry->type = type;
-  new_entry->caller_forwarding = forwarding;
 
   /* Queue */
   new_entry->next = parse_functions;
@@ -125,8 +123,7 @@ olsr_parser_add_function (parse_function * function, olsr_u32_t type,
 }
 
 int
-olsr_parser_remove_function (parse_function * function, olsr_u32_t type,
-                             int forwarding)
+olsr_parser_remove_function (parse_function * function, olsr_u32_t type)
 {
   struct parse_function_entry *entry, *prev;
 
@@ -135,8 +132,7 @@ olsr_parser_remove_function (parse_function * function, olsr_u32_t type,
 
   while (entry)
     {
-      if ((entry->function == function) && (entry->type == type)
-          && (entry->caller_forwarding == forwarding))
+      if ((entry->function == function) && (entry->type == type))
         {
           if (entry == parse_functions)
             {
@@ -277,13 +273,12 @@ parse_packet (struct olsr *olsr, int size, struct interface *in_if,
 {
   union olsr_message *m = (union olsr_message *) olsr->olsr_msg;
   struct unknown_message unkpacket;
-  int count;
   int msgsize;
   int processed;
   struct parse_function_entry *entry;
   struct packetparser_function_entry *packetparser;
-
-  count = size - ((char *) m - (char *) olsr);
+  olsr_bool isDuplicate;
+  int count = size - ((char *) m - (char *) olsr);
 
   if (count < MIN_PACKET_SIZE (olsr_cnf->ip_version))
     return;
@@ -435,44 +430,39 @@ parse_packet (struct olsr *olsr, int size, struct interface *in_if,
         }
 
       /* check for message duplicates */
+      isDuplicate = OLSR_FALSE;
       if (olsr_cnf->ip_version == AF_INET)
         {
           /* IPv4 */
-          if (olsr_shall_process_message
-              (&m->v4.originator, ntohs (m->v4.seqno)) == 0)
-            {
-              continue;
-            }
+          isDuplicate =
+            olsr_message_is_duplicate (&m->v4.originator, ntohs (m->v4.seqno),
+                                       OLSR_FALSE);
         }
       else
         {
           /* IPv6 */
-          if (olsr_shall_process_message
-              (&m->v6.originator, ntohs (m->v6.seqno)) == 0)
-            {
-              continue;
-            }
+          isDuplicate =
+            olsr_message_is_duplicate (&m->v6.originator, ntohs (m->v6.seqno),
+                                       OLSR_FALSE);
         }
 
       //printf("MESSAGETYPE: %d\n", m->v4.olsr_msgtype);
-
-      entry = parse_functions;
-
-      while (entry)
+      if (!isDuplicate)
         {
-          /* Should be the same for IPv4 and IPv6 */
-
-          /* Promiscuous or exact match */
-          if ((entry->type == PROMISCUOUS)
-              || (entry->type == m->v4.olsr_msgtype))
+          processed = 0;
+          for (entry = parse_functions; entry != NULL; entry = entry->next)
             {
-              entry->function (m, in_if, from_addr);
-              if (entry->caller_forwarding)
-                processed = 1;
+              /* Should be the same for IPv4 and IPv6 */
+
+              /* Promiscuous or exact match */
+              if ((entry->type == PROMISCUOUS)
+                  || (entry->type == m->v4.olsr_msgtype))
+                {
+                  entry->function (m, in_if, from_addr);
+                  processed = 1;
+                }
             }
-          entry = entry->next;
         }
-
       /* UNKNOWN PACKETTYPE */
       if (processed == 0)
         {
@@ -484,17 +474,12 @@ parse_packet (struct olsr *olsr, int size, struct interface *in_if,
                                                                     &unkpacket.
                                                                     originator));
 
-          /* Forward message */
-          if (!ipequal (&unkpacket.originator, &olsr_cnf->main_addr))
-            {
-              /* Forward */
-              olsr_forward_message (m, from_addr);
-            }
-
           /* Cancel loop here, otherwise olsrd just hangs forever at this point */
           break;
         }
 
+      /* now call function to check for forwarding */
+      olsr_forward_message (m, from_addr);
     }                           /* for olsr_msg */
 }
 
index 1430c15..58b2dc0 100644 (file)
@@ -52,7 +52,6 @@ typedef void parse_function (union olsr_message *, struct interface *,
 struct parse_function_entry
 {
   olsr_u32_t type;              /* If set to PROMISCUOUS all messages will be received */
-  int caller_forwarding;        /* If set to 0 this entry is not registered as forwarding packets */
   parse_function *function;
   struct parse_function_entry *next;
 };
@@ -84,9 +83,9 @@ void olsr_input (int);
 
 void olsr_input_hostemu (int);
 
-void olsr_parser_add_function (parse_function, olsr_u32_t, int);
+void olsr_parser_add_function (parse_function, olsr_u32_t);
 
-int olsr_parser_remove_function (parse_function, olsr_u32_t, int);
+int olsr_parser_remove_function (parse_function, olsr_u32_t);
 
 void olsr_preprocessor_add_function (preprocessor_function);
 
index 3f858f8..904c01f 100644 (file)
@@ -468,17 +468,17 @@ olsr_init_package_process (void)
 {
   if (olsr_cnf->lq_level == 0)
     {
-      olsr_parser_add_function (&olsr_input_hello, HELLO_MESSAGE, 1);
-      olsr_parser_add_function (&olsr_input_tc, TC_MESSAGE, 1);
+      olsr_parser_add_function (&olsr_input_hello, HELLO_MESSAGE);
+      olsr_parser_add_function (&olsr_input_tc, TC_MESSAGE);
     }
   else
     {
-      olsr_parser_add_function (&olsr_input_hello, LQ_HELLO_MESSAGE, 1);
-      olsr_parser_add_function (&olsr_input_tc, LQ_TC_MESSAGE, 1);
+      olsr_parser_add_function (&olsr_input_hello, LQ_HELLO_MESSAGE);
+      olsr_parser_add_function (&olsr_input_tc, LQ_TC_MESSAGE);
     }
 
-  olsr_parser_add_function (&olsr_input_mid, MID_MESSAGE, 1);
-  olsr_parser_add_function (&olsr_input_hna, HNA_MESSAGE, 1);
+  olsr_parser_add_function (&olsr_input_mid, MID_MESSAGE);
+  olsr_parser_add_function (&olsr_input_hna, HNA_MESSAGE);
 }
 
 void
index 87ac174..cc72e7b 100644 (file)
@@ -1036,12 +1036,6 @@ olsr_input_tc (union olsr_message *msg, struct interface *input_if
                       &olsr_expire_tc_edge_gc, tc,
                       tc_edge_gc_timer_cookie->ci_id);
     }
-
-  /*
-   * Last, flood the message to our other neighbors.
-   */
-  olsr_forward_message (msg, from_addr);
-  return;
 }
 
 /*