applied fixes from Sven-Ola:
authorBernd Petrovitsch <bernd@firmix.at>
Sat, 10 Feb 2007 17:36:51 +0000 (17:36 +0000)
committerBernd Petrovitsch <bernd@firmix.at>
Sat, 10 Feb 2007 17:36:51 +0000 (17:36 +0000)
- he corrected a copy-paste error made by me. Thanks.
- he killed the parts disabled by DISABLE_SVEN_OLA

lib/quagga/Makefile
src/lq_avl.c
src/lq_avl.h
src/lq_list.c
src/lq_list.h
src/lq_packet.c
src/lq_route.c
src/net_olsr.c

index c357e36..3f14ed5 100644 (file)
@@ -35,7 +35,7 @@
 # to the project. For more information see the website or contact
 # the copyright holders.
 #
-# $Id: Makefile,v 1.2 2007/02/04 21:21:16 bernd67 Exp $
+# $Id: Makefile,v 1.3 2007/02/10 17:36:51 bernd67 Exp $
 
 OLSRD_PLUGIN = true
 PLUGIN_NAME =  olsrd_quagga
@@ -55,7 +55,7 @@ include $(TOPDIR)/Makefile.inc
 ifneq ($(OS),linux)
 
 default_target install clean: 
-       @echo "*** TAS Plugin only supported on Linux, sorry!"
+       @echo "*** Quagga Plugin only supported on Linux, sorry!"
 
 else
 
index b537c54..524a62b 100755 (executable)
@@ -1,6 +1,7 @@
 /*
  * The olsr.org Optimized Link-State Routing daemon(olsrd)
  * Copyright (c) 2004, Thomas Lopatic (thomas@lopatic.de)
+ * IPv4 performance optimization (c) 2006, sven-ola(gmx.de)
  * All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without 
  * to the project. For more information see the website or contact
  * the copyright holders.
  *
- * $Id: lq_avl.c,v 1.2 2007/01/31 12:36:50 bernd67 Exp $
+ * $Id: lq_avl.c,v 1.3 2007/02/10 17:36:51 bernd67 Exp $
  */
 
 #include <stddef.h>
-#ifndef DISABLE_SVEN_OLA
 #include <time.h>
-#endif
 
 #include "lq_avl.h"
 
@@ -55,7 +54,6 @@ void avl_init(struct avl_tree *tree, int (*comp)(void *, void *))
   tree->comp = comp;
 }
 
-#ifndef DISABLE_SVEN_OLA
 static struct avl_node *avl_find_rec_ipv4(struct avl_node *node, void *key)
 {
   if (*(unsigned int *)key < *(unsigned int *)node->key) {
@@ -70,18 +68,16 @@ static struct avl_node *avl_find_rec_ipv4(struct avl_node *node, void *key)
   }
   return node;
 }
-#endif
 
 static struct avl_node *avl_find_rec(struct avl_node *node, void *key,
                                      int (*comp)(void *, void *))
 {
   int diff;
 
-#ifndef DISABLE_SVEN_OLA
   if (0 == comp) {
     return avl_find_rec_ipv4(node, key);
   }
-#endif
+
   diff = (*comp)(key, node->key);
 
   if (diff < 0)
@@ -112,15 +108,14 @@ struct avl_node *avl_find(struct avl_tree *tree, void *key)
 
   node = avl_find_rec(tree->root, key, tree->comp);
 
-#ifndef DISABLE_SVEN_OLA
   if (0 == tree->comp) {
-    if (0 != svenola_avl_comp_ipv4(node->key, key))
+    if (0 != inline_avl_comp_ipv4(node->key, key))
+      return NULL;
+  }
+  else {
+    if ((*tree->comp)(node->key, key) != 0)
       return NULL;
   }
-  else
-#endif
-  if ((*tree->comp)(node->key, key) != 0)
-    return NULL;
 
   return node;
 }
@@ -260,13 +255,12 @@ int avl_insert(struct avl_tree *tree, struct avl_node *new)
 
   node = avl_find_rec(tree->root, new->key, tree->comp);
 
-#ifndef DISABLE_SVEN_OLA
   if (0 == tree->comp) {
-    diff = svenola_avl_comp_ipv4(new->key, node->key);
+    diff = inline_avl_comp_ipv4(new->key, node->key);
+  }
+  else {
+    diff = (*tree->comp)(new->key, node->key);
   }
-  else
-#endif
-  diff = (*tree->comp)(new->key, node->key);
 
   if (diff == 0)
     return -1;
index f68e161..acc6f74 100755 (executable)
@@ -1,6 +1,7 @@
 /*
  * The olsr.org Optimized Link-State Routing daemon(olsrd)
  * Copyright (c) 2004, Thomas Lopatic (thomas@lopatic.de)
+ * IPv4 performance optimization (c) 2006, sven-ola(gmx.de)
  * All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without 
@@ -36,7 +37,7 @@
  * to the project. For more information see the website or contact
  * the copyright holders.
  *
- * $Id: lq_avl.h,v 1.3 2007/01/31 12:36:50 bernd67 Exp $
+ * $Id: lq_avl.h,v 1.4 2007/02/10 17:36:51 bernd67 Exp $
  */
 
 #ifndef _LQ_AVL_H
@@ -62,9 +63,8 @@ void avl_init(struct avl_tree *, int (*)(void *, void *));
 struct avl_node *avl_find(struct avl_tree *, void *);
 int avl_insert(struct avl_tree *, struct avl_node *);
 
-#ifndef DISABLE_SVEN_OLA
-#define svenola_avl_comp_ipv4(ip1, ip2) \
+#define inline_avl_comp_ipv4(ip1, ip2) \
   (*(unsigned int *)ip1 == *(unsigned int *)ip2 ? 0 : \
   *(unsigned int *)ip1 < *(unsigned int *)ip2 ? -1 : +1)
-#endif
+
 #endif
index 9fa4799..37496f6 100644 (file)
@@ -1,6 +1,7 @@
 /*
  * The olsr.org Optimized Link-State Routing daemon(olsrd)
  * Copyright (c) 2004, Thomas Lopatic (thomas@lopatic.de)
+ * IPv4 performance optimization (c) 2006, sven-ola(gmx.de)
  * All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without 
@@ -36,7 +37,7 @@
  * to the project. For more information see the website or contact
  * the copyright holders.
  *
- * $Id: lq_list.c,v 1.4 2007/01/31 12:36:50 bernd67 Exp $
+ * $Id: lq_list.c,v 1.5 2007/02/10 17:36:51 bernd67 Exp $
  */
 
 #include <stdlib.h>
@@ -48,28 +49,6 @@ void list_init(struct list *list)
   list->tail = NULL;
 }
 
-#ifdef DISABLE_SVEN_OLA
-struct list_node *list_get_head(struct list *list)
-{
-  return list->head;
-}
-
-struct list_node *list_get_tail(struct list *list)
-{
-  return list->tail;
-}
-
-struct list_node *list_get_next(struct list_node *node)
-{
-  return node->next;
-}
-
-struct list_node *list_get_prev(struct list_node *node)
-{
-  return node->prev;
-}
-#endif
-
 void list_add_head(struct list *list, struct list_node *node)
 {
   if (list->head != NULL)
index e7aa285..383c8a8 100644 (file)
@@ -1,6 +1,7 @@
 /*
  * The olsr.org Optimized Link-State Routing daemon(olsrd)
  * Copyright (c) 2004, Thomas Lopatic (thomas@lopatic.de)
+ * IPv4 performance optimization (c) 2006, sven-ola(gmx.de)
  * All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without 
@@ -36,7 +37,7 @@
  * to the project. For more information see the website or contact
  * the copyright holders.
  *
- * $Id: lq_list.h,v 1.4 2007/01/31 12:36:50 bernd67 Exp $
+ * $Id: lq_list.h,v 1.5 2007/02/10 17:36:51 bernd67 Exp $
  */
 
 #ifndef _LQ_LIST_H
@@ -58,18 +59,10 @@ struct list
 
 void list_init(struct list *list);
 
-#ifndef DISABLE_SVEN_OLA
-#define list_get_head(node) (node)->head
-#define list_get_tail(node) (node)->tail
-#define list_get_next(node) (node)->next
-#define list_get_prev(node) (node)->prev
-#else
-struct list_node *list_get_head(struct list *list);
-struct list_node *list_get_tail(struct list *list);
-
-struct list_node *list_get_next(struct list_node *node);
-struct list_node *list_get_prev(struct list_node *node);
-#endif
+#define list_get_head(node) ((node)->head)
+#define list_get_tail(node) ((node)->tail)
+#define list_get_next(node) ((node)->next)
+#define list_get_prev(node) ((node)->prev)
 
 void list_add_head(struct list *list, struct list_node *node);
 void list_add_tail(struct list *list, struct list_node *node);
index ae145d2..60957ff 100644 (file)
@@ -2,6 +2,7 @@
  * The olsr.org Optimized Link-State Routing daemon(olsrd)
  * Copyright (c) 2003, Andreas T√łnnesen (andreto@olsr.org)
  *               2004, Thomas Lopatic (thomas@lopatic.de)
+ *               2006, for some fixups, sven-ola(gmx.de)
  * All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without 
@@ -37,7 +38,7 @@
  * to the project. For more information see the website or contact
  * the copyright holders.
  *
- * $Id: lq_packet.c,v 1.22 2007/01/31 12:36:50 bernd67 Exp $
+ * $Id: lq_packet.c,v 1.23 2007/02/10 17:36:51 bernd67 Exp $
  */
 
 #include "olsr_protocol.h"
@@ -167,7 +168,7 @@ create_lq_tc(struct lq_tc_message *lq_tc, struct interface *outif)
 
   if (olsr_cnf->lq_fish > 0)
   {
-    // SVEN_OLA: Too lazy to find the different iface inits. This will do it too.
+    // Sven-Ola: Too lazy to find the different iface inits. This will do it too.
     if (outif->ttl_index >= (int)(sizeof(ttl_list) / sizeof(ttl_list[0])))
       outif->ttl_index = 0;
     
@@ -800,7 +801,7 @@ process_lq_hello(struct lq_hello_message *lq_hello, struct interface *inif,
   struct lq_hello_neighbor *neigh;
   struct hello_neighbor *new_neigh;
 
-  // SVEN_OLA: Check the message source addr
+  // Sven-Ola: Check the message source addr
   if(!olsr_validate_address(&lq_hello->comm.orig))
     {
       return;
@@ -826,7 +827,7 @@ process_lq_hello(struct lq_hello_message *lq_hello, struct interface *inif,
 
   for (neigh = lq_hello->neigh; neigh != NULL; neigh = neigh->next)
     {
-      // SVEN_OLA: Also check the neighbours
+      // Sven-Ola: Also check the neighbours
       if(!olsr_validate_address(&neigh->addr)) continue;
       
       // allocate HELLO neighbour
@@ -860,7 +861,7 @@ process_lq_tc(struct lq_tc_message *lq_tc, struct interface *inif,
   struct lq_tc_neighbor *neigh;
   struct tc_mpr_addr *new_neigh;
 
-  // SVEN_OLA: Check the message source addr
+  // Sven-Ola: Check the message source addr
   if(!olsr_validate_address(&lq_tc->from)||!olsr_validate_address(&lq_tc->comm.orig))
     {
       return;
@@ -886,7 +887,7 @@ process_lq_tc(struct lq_tc_message *lq_tc, struct interface *inif,
 
   for (neigh = lq_tc->neigh; neigh != NULL; neigh = neigh->next)
     {
-      // SVEN_OLA: Also check the neighbours
+      // Sven-Ola: Also check the neighbours
       if(!olsr_validate_address(&neigh->main)) continue;
       
       // allocate TC neighbour
index 708e3ee..5ef9080 100644 (file)
@@ -1,6 +1,7 @@
 /*
  * The olsr.org Optimized Link-State Routing daemon(olsrd)
  * Copyright (c) 2004, Thomas Lopatic (thomas@lopatic.de)
+ * IPv4 performance optimization (c) 2006, sven-ola(gmx.de)
  * All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without 
@@ -36,7 +37,7 @@
  * to the project. For more information see the website or contact
  * the copyright holders.
  *
- * $Id: lq_route.c,v 1.43 2007/01/31 12:36:50 bernd67 Exp $
+ * $Id: lq_route.c,v 1.44 2007/02/10 17:36:51 bernd67 Exp $
  */
 
 #include "defs.h"
@@ -77,19 +78,6 @@ static int avl_comp_ipv6(void *ip1, void *ip2)
   return memcmp(ip1, ip2, olsr_cnf->ipsize);
 }
 
-#ifdef DISABLE_SVEN_OLA
-static int avl_comp_ipv4(void *ip1, void *ip2)
-{
-  if (*(unsigned int *)ip1 < *(unsigned int *)ip2)
-    return -1;
-
-  if (*(unsigned int *)ip1 == *(unsigned int *)ip2)
-    return 0;
-
-  return 1;
-}
-#endif
-
 static int (*avl_comp)(void *, void *);
 
 static void add_vertex(struct avl_tree *vertex_tree, union olsr_ip_addr *addr,
@@ -206,20 +194,19 @@ static void create_vertex_list_rec(struct list *vertex_list,
     create_vertex_list_rec(vertex_list, node->left, comp);
 
   // add the vertex to the list, if it's not us
-#ifndef DISABLE_SVEN_OLA
   if (NULL == comp) {
-    if (svenola_avl_comp_ipv4(&olsr_cnf->main_addr, node->key) != 0)
+    if (inline_avl_comp_ipv4(&olsr_cnf->main_addr, node->key) != 0)
     {
       vert->node.data = vert;
       list_add_tail(vertex_list, &vert->node);
     }
   }
-  else
-#endif
-  if ((*comp)(&olsr_cnf->main_addr, node->key) != 0)
-  {
-    vert->node.data = vert;
-    list_add_tail(vertex_list, &vert->node);
+  else {
+    if ((*comp)(&olsr_cnf->main_addr, node->key) != 0)
+    {
+      vert->node.data = vert;
+      list_add_tail(vertex_list, &vert->node);
+    }
   }
 
   if (node->right != NULL)
@@ -277,8 +264,7 @@ static void free_everything(struct list *vertex_list)
 }
 
 // XXX - bad complexity
-#define SVEN_OPT
-#undef SVEN_OPT_DBG
+#define SVEN_OLA_OPTIMIZE
 
 /*
  * The function extract_best() is most expensive (>50% CPU in profiling).
@@ -287,15 +273,16 @@ static void free_everything(struct list *vertex_list)
  * because the stored verices do not change from call to call and it is
  * more sufficient to have them sorted/popped from a list rather than 
  * searching the complete list by every call. Sven-Ola@gmx.de, 11/2006
+ * 
+ * The SVEN_OLA_OPTIMIZE changes work in our berlin environment. However,
+ * they may introduce bugs, e.g. they are untested for IPv6. For this 
+ * reason, the source still contains the ifdef SVEN_OLA_OPIMIZE.
  */
  
-#ifdef SVEN_OPT
+#ifdef SVEN_OLA_OPTIMIZE
 static struct dijk_vertex **etx_cache = 0;
 static int etx_cache_count;
 static int etx_cache_get;
-#ifdef SVEN_OPT_DBG
-static int etx_cache_saved = 0;
-#endif
 
 static int etx_cache_compare(const void *a, const void *b)
 {
@@ -314,39 +301,10 @@ static int etx_cache_compare(const void *a, const void *b)
 
 static struct dijk_vertex *extract_best_route(struct list *vertex_list)
 {
-#ifdef SVEN_OPT_DBG
-  float best_etx = INFINITE_ETX + 1.0;
-#endif
   struct list_node *node;
   struct dijk_vertex *vert;
   struct dijk_vertex *res = NULL;
 
-#ifdef SVEN_OPT_DBG
-  node = list_get_head(vertex_list);
-
-  // loop through all vertices
-  
-  while (node != NULL)
-  {
-    vert = node->data;
-
-    // see whether the current vertex is better than what we have
-
-    if (!vert->done && vert->path_etx < best_etx)
-    {
-      best_etx = vert->path_etx;
-      res = vert;
-    }
-    else if (!vert->done && vert->path_etx == best_etx && vert < res)
-    {
-      // Otherwise order is undefined if etx==etx and debug will complain
-      best_etx = vert->path_etx;
-      res = vert;
-    }
-
-    node = list_get_next(node);
-  }
-#endif
   if (NULL == etx_cache)
   {
     int count = 0;
@@ -360,9 +318,6 @@ static struct dijk_vertex *extract_best_route(struct list *vertex_list)
     if (0 < count)
     {
       etx_cache = olsr_malloc(sizeof(etx_cache[0]) * count, "ETX Cache");
-#ifdef SVEN_OPT_DBG
-      printf("count=%d, Malloc(%d)=%p\n", count, sizeof(etx_cache[0]) * count, etx_cache);
-#endif
       node = list_get_head(vertex_list);
       etx_cache_count = 0;
       etx_cache_get = 0;
@@ -376,48 +331,14 @@ static struct dijk_vertex *extract_best_route(struct list *vertex_list)
         }
         node = list_get_next(node);
       }
-#ifdef SVEN_OPT_DBG
-      printf("qsort(etx_cache_count=%d)\n", etx_cache_count);
-#endif
       qsort(etx_cache, etx_cache_count, sizeof(etx_cache[0]), etx_cache_compare);
-#ifdef SVEN_OPT_DBG
-      if (0 < etx_cache_count)
-      {
-        int i = 0; 
-        while(i < etx_cache_count && i < 10)
-        {
-          printf("%d: %p=%f\n", i, etx_cache[i], etx_cache[i]->path_etx);
-          i++;
-        }
-      }
-#endif
     }
   }
 
-#ifdef SVEN_OPT_DBG
-  if (NULL != etx_cache)
-  {
-    struct dijk_vertex *rescache = NULL;
-    if (etx_cache_get < etx_cache_count)
-    {
-      rescache = etx_cache[etx_cache_get++];
-    }
-    if (res != rescache)
-    {
-      printf("miss: etx_cache_get=%d, res=%p,%f != rescache=%p,%f\n",
-        etx_cache_get, res, (NULL != res ? res->path_etx : -1), rescache, (NULL != rescache ? rescache->path_etx : -1));
-    }
-    else
-    {
-      etx_cache_saved++;
-    }
-  }
-#else
   if (NULL != etx_cache && etx_cache_get < etx_cache_count)
   {
     res = etx_cache[etx_cache_get++];
   }
-#endif
 
   // if we've found a vertex, remove it from the set
 
@@ -426,7 +347,7 @@ static struct dijk_vertex *extract_best_route(struct list *vertex_list)
 
   return res;
 }
-#endif // SVEN_OPT
+#endif // SVEN_OLA_OPTIMIZE
 
 static struct dijk_vertex *extract_best(struct list *vertex_list)
 {
@@ -532,11 +453,7 @@ void olsr_calculate_lq_routing_table(void)
   struct interface *inter;
 
   if (olsr_cnf->ipsize == 4)
-#ifndef DISABLE_SVEN_OLA
     avl_comp = 0;
-#else
-    avl_comp = avl_comp_ipv4;
-#endif
   else
     avl_comp = avl_comp_ipv6;
 
@@ -778,11 +695,7 @@ void olsr_calculate_lq_routing_table(void)
 
   // add HNA routes - the set of unprocessed network nodes contains
   // all reachable network nodes
-#ifdef SVEN_OPT
-#ifdef SVEN_OPT_DBG
-  printf("free etx_cache, saved compares=%d, etx_cache=%p\n", etx_cache_saved, etx_cache);
-  etx_cache_saved = 0;
-#endif
+#ifdef SVEN_OLA_OPTIMIZE
   if (NULL != etx_cache) {
     free(etx_cache);
     etx_cache = NULL;
@@ -794,7 +707,7 @@ void olsr_calculate_lq_routing_table(void)
     // extract the network node with the best ETX and remove it
     // from the set of unprocessed network nodes
 
-#ifdef SVEN_OPT
+#ifdef SVEN_OLA_OPTIMIZE
     vert = extract_best_route(&vertex_list);
 #else
     vert = extract_best(&vertex_list);
index 6b5e172..98c1e5d 100644 (file)
@@ -36,7 +36,7 @@
  * to the project. For more information see the website or contact
  * the copyright holders.
  *
- * $Id: net_olsr.c,v 1.17 2006/11/15 23:07:59 bernd67 Exp $
+ * $Id: net_olsr.c,v 1.18 2007/02/10 17:36:51 bernd67 Exp $
  */
 
 #include "net_olsr.h"
@@ -89,7 +89,6 @@ static struct deny_address_entry *deny_entries;
 static const char * const deny_ipv4_defaults[] =
   {
     "0.0.0.0",
-    //SVEN_OLA: This address is not plausible too
     "127.0.0.1",
     NULL
   };