net/olsrd/patches/190-olsrd-optimize.patch

   1 diff -Nur olsrd-0.4.10.orig/src/duplicate_set.c olsrd-0.4.10/src/duplicate_set.c
   2 --- olsrd-0.4.10.orig/src/duplicate_set.c       2005-02-27 19:39:43.000000000 +0100
   3 +++ olsrd-0.4.10/src/duplicate_set.c    2006-11-12 09:33:49.000000000 +0100
   4 @@ -93,7 +93,7 @@
   5
   6
   7    /* Hash the senders address */
   8 -  hash = olsr_hashing(originator);
   9 +  hash = HASHMASK & seqno;
  10
  11    new_dup_entry = olsr_malloc(sizeof(struct dup_entry), "New dup entry");
  12
  13 @@ -131,7 +131,7 @@
  14    struct dup_entry *tmp_dup_table;
  15
  16    /* Hash the senders address */
  17 -  hash = olsr_hashing(originator);
  18 +  hash = HASHMASK & seqno;
  19
  20    /* Check for entry */
  21    for(tmp_dup_table = dup_set[hash].next;
  22 @@ -163,7 +163,7 @@
  23    struct dup_entry *tmp_dup_table;
  24
  25    /* Hash the senders address */
  26 -  hash = olsr_hashing(originator);
  27 +  hash = HASHMASK & seqno;
  28
  29    /* Check for entry */
  30    for(tmp_dup_table = dup_set[hash].next;
  31 @@ -268,7 +268,7 @@
  32    struct dup_iface *new_iface;
  33
  34    /* Hash the senders address */
  35 -  hash = olsr_hashing(originator);
  36 +  hash = HASHMASK & seqno;
  37
  38
  39    /* Check for entry */
  40 @@ -313,7 +313,7 @@
  41    struct dup_entry *tmp_dup_table;
  42
  43    /* Hash the senders address */
  44 -  hash = olsr_hashing(originator);
  45 +  hash = HASHMASK & seqno;
  46
  47    /* Check for entry */
  48    for(tmp_dup_table = dup_set[hash].next;
  49 diff -Nur olsrd-0.4.10.orig/src/hashing.c olsrd-0.4.10/src/hashing.c
  50 --- olsrd-0.4.10.orig/src/hashing.c     2005-02-20 19:52:18.000000000 +0100
  51 +++ olsrd-0.4.10/src/hashing.c  2006-11-12 09:33:49.000000000 +0100
  52 @@ -58,7 +58,7 @@
  53
  54    if(olsr_cnf->ip_version == AF_INET)
  55      /* IPv4 */
  56 -    hash = (ntohl(address->v4));
  57 +    hash = address->v4x[0] ^ address->v4x[1] ^ address->v4x[2] ^ address->v4x[3];
  58    else
  59      {
  60        /* IPv6 */
  61 diff -Nur olsrd-0.4.10.orig/src/hashing.h olsrd-0.4.10/src/hashing.h
  62 --- olsrd-0.4.10.orig/src/hashing.h     2005-02-20 19:52:18.000000000 +0100
  63 +++ olsrd-0.4.10/src/hashing.h  2006-11-12 09:33:49.000000000 +0100
  64 @@ -43,7 +43,7 @@
  65  #ifndef _OLSR_HASHING
  66  #define _OLSR_HASHING
  67
  68 -#define        HASHSIZE        32
  69 +#define        HASHSIZE        128
  70  #define        HASHMASK        (HASHSIZE - 1)
  71
  72  #include "olsr_types.h"
  73 diff -Nur olsrd-0.4.10.orig/src/lq_avl.c olsrd-0.4.10/src/lq_avl.c
  74 --- olsrd-0.4.10.orig/src/lq_avl.c      2005-01-22 15:30:57.000000000 +0100
  75 +++ olsrd-0.4.10/src/lq_avl.c   2006-11-12 09:33:49.000000000 +0100
  76 @@ -40,6 +40,9 @@
  77   */
  78
  79  #include <stddef.h>
  80 +#ifndef DISABLE_SVEN_OLA
  81 +#include <time.h>
  82 +#endif
  83
  84  #include "lq_avl.h"
  85
  86 @@ -52,11 +55,33 @@
  87    tree->comp = comp;
  88  }
  89
  90 +#ifndef DISABLE_SVEN_OLA
  91 +static struct avl_node *avl_find_rec_ipv4(struct avl_node *node, void *key)
  92 +{
  93 +  if (*(unsigned int *)key < *(unsigned int *)node->key) {
  94 +    if (node->left != NULL) {
  95 +      return avl_find_rec_ipv4(node->left, key);
  96 +    }
  97 +  }
  98 +  else if (*(unsigned int *)key > *(unsigned int *)node->key) {
  99 +    if (node->right != NULL) {
 100 +      return avl_find_rec_ipv4(node->right, key);
 101 +    }
 102 +  }
 103 +  return node;
 104 +}
 105 +#endif
 106 +
 107  static struct avl_node *avl_find_rec(struct avl_node *node, void *key,
 108                                       int (*comp)(void *, void *))
 109  {
 110    int diff;
 111
 112 +#ifndef DISABLE_SVEN_OLA
 113 +  if (0 == comp) {
 114 +    return avl_find_rec_ipv4(node, key);
 115 +  }
 116 +#endif
 117    diff = (*comp)(key, node->key);
 118
 119    if (diff < 0)
 120 @@ -87,6 +112,13 @@
 121
 122    node = avl_find_rec(tree->root, key, tree->comp);
 123
 124 +#ifndef DISABLE_SVEN_OLA
 125 +  if (0 == tree->comp) {
 126 +    if (0 != svenola_avl_comp_ipv4(node->key, key))
 127 +      return NULL;
 128 +  }
 129 +  else
 130 +#endif
 131    if ((*tree->comp)(node->key, key) != 0)
 132      return NULL;
 133
 134 @@ -228,6 +260,12 @@
 135
 136    node = avl_find_rec(tree->root, new->key, tree->comp);
 137
 138 +#ifndef DISABLE_SVEN_OLA
 139 +  if (0 == tree->comp) {
 140 +    diff = svenola_avl_comp_ipv4(new->key, node->key);
 141 +  }
 142 +  else
 143 +#endif
 144    diff = (*tree->comp)(new->key, node->key);
 145
 146    if (diff == 0)
 147 diff -Nur olsrd-0.4.10.orig/src/lq_avl.h olsrd-0.4.10/src/lq_avl.h
 148 --- olsrd-0.4.10.orig/src/lq_avl.h      2005-02-20 19:52:18.000000000 +0100
 149 +++ olsrd-0.4.10/src/lq_avl.h   2006-11-12 09:33:49.000000000 +0100
 150 @@ -62,4 +62,9 @@
 151  struct avl_node *avl_find(struct avl_tree *, void *);
 152  int avl_insert(struct avl_tree *, struct avl_node *);
 153
 154 +#ifndef DISABLE_SVEN_OLA
 155 +#define svenola_avl_comp_ipv4(ip1, ip2) \
 156 +  (*(unsigned int *)ip1 == *(unsigned int *)ip2 ? 0 : \
 157 +  *(unsigned int *)ip1 < *(unsigned int *)ip2 ? -1 : +1)
 158 +#endif
 159  #endif
 160 diff -Nur olsrd-0.4.10.orig/src/lq_list.c olsrd-0.4.10/src/lq_list.c
 161 --- olsrd-0.4.10.orig/src/lq_list.c     2004-12-04 18:06:57.000000000 +0100
 162 +++ olsrd-0.4.10/src/lq_list.c  2006-11-12 09:33:49.000000000 +0100
 163 @@ -48,6 +48,7 @@
 164    list->tail = NULL;
 165  }
 166
 167 +#ifdef DISABLE_SVEN_OLA
 168  struct list_node *list_get_head(struct list *list)
 169  {
 170    return list->head;
 171 @@ -67,6 +68,7 @@
 172  {
 173    return node->prev;
 174  }
 175 +#endif
 176
 177  void list_add_head(struct list *list, struct list_node *node)
 178  {
 179 diff -Nur olsrd-0.4.10.orig/src/lq_list.h olsrd-0.4.10/src/lq_list.h
 180 --- olsrd-0.4.10.orig/src/lq_list.h     2005-02-20 19:52:18.000000000 +0100
 181 +++ olsrd-0.4.10/src/lq_list.h  2006-11-12 09:33:49.000000000 +0100
 182 @@ -58,11 +58,18 @@
 183
 184  void list_init(struct list *list);
 185
 186 +#ifndef DISABLE_SVEN_OLA
 187 +#define list_get_head(node) (node)->head
 188 +#define list_get_tail(node) (node)->tail
 189 +#define list_get_next(node) (node)->next
 190 +#define list_get_prev(node) (node)->prev
 191 +#else
 192  struct list_node *list_get_head(struct list *list);
 193  struct list_node *list_get_tail(struct list *list);
 194
 195  struct list_node *list_get_next(struct list_node *node);
 196  struct list_node *list_get_prev(struct list_node *node);
 197 +#endif
 198
 199  void list_add_head(struct list *list, struct list_node *node);
 200  void list_add_tail(struct list *list, struct list_node *node);
 201 diff -Nur olsrd-0.4.10.orig/src/lq_route.c olsrd-0.4.10/src/lq_route.c
 202 --- olsrd-0.4.10.orig/src/lq_route.c    2005-11-29 19:37:58.000000000 +0100
 203 +++ olsrd-0.4.10/src/lq_route.c 2006-11-12 09:34:46.000000000 +0100
 204 @@ -205,6 +205,16 @@
 205
 206    // add the vertex to the list, if it's not us
 207
 208 +#ifndef DISABLE_SVEN_OLA
 209 +  if (0 == comp) {
 210 +    if (svenola_avl_comp_ipv4(&main_addr, node->key) != 0)
 211 +    {
 212 +      vert->node.data = vert;
 213 +      list_add_tail(vertex_list, &vert->node);
 214 +    }
 215 +  }
 216 +  else
 217 +#endif
 218    if ((*comp)(&main_addr, node->key) != 0)
 219    {
 220      vert->node.data = vert;
 221 @@ -266,6 +276,154 @@
 222  }
 223
 224  // XXX - bad complexity
 225 +#define SVEN_OPT
 226 +#undef SVEN_OPT_DBG
 227 +
 228 +/*
 229 + * The function extract_best() is most expensive (>50% CPU in profiling).
 230 + * It is called in two modes: while doing Dijkstra route calculation and
 231 + * while searching for a direct route/hna. The latter can be optimized
 232 + * because the stored verices do not change from call to call and it is
 233 + * more sufficient to have them sorted/popped from a list rather than
 234 + * searching the complete list by every call. Sven-Ola@gmx.de, 11/2006
 235 + */
 236 +
 237 +#ifdef SVEN_OPT
 238 +static struct dijk_vertex **etx_cache = 0;
 239 +static int etx_cache_count;
 240 +static int etx_cache_get;
 241 +static int etx_cache_saved = 0;
 242 +
 243 +static int etx_cache_compare(const void *a, const void *b)
 244 +{
 245 +  // Oh jeah. I love this macro assembler :)
 246 +
 247 +  if ((*(struct dijk_vertex **)a)->path_etx > (*(struct dijk_vertex **)b)->path_etx) return 1;
 248 +  if ((*(struct dijk_vertex **)a)->path_etx < (*(struct dijk_vertex **)b)->path_etx) return -1;
 249 +
 250 +  // This is for debugging only: etx==etx then compare pointers
 251 +  // to make it possible to compare to the original search algo.
 252 +  if (*(struct dijk_vertex **)a > *(struct dijk_vertex **)b) return 1;
 253 +  if (*(struct dijk_vertex **)a < *(struct dijk_vertex **)b) return -1;
 254 +
 255 +  return 0;
 256 +}
 257 +
 258 +static struct dijk_vertex *extract_best_route(struct list *vertex_list)
 259 +{
 260 +#ifdef SVEN_OPT_DBG
 261 +  float best_etx = INFINITE_ETX + 1.0;
 262 +#endif
 263 +  struct list_node *node;
 264 +  struct dijk_vertex *vert;
 265 +  struct dijk_vertex *res = NULL;
 266 +
 267 +#ifdef SVEN_OPT_DBG
 268 +  node = list_get_head(vertex_list);
 269 +
 270 +  // loop through all vertices
 271 +
 272 +  while (node != NULL)
 273 +  {
 274 +    vert = node->data;
 275 +
 276 +    // see whether the current vertex is better than what we have
 277 +
 278 +    if (!vert->done && vert->path_etx < best_etx)
 279 +    {
 280 +      best_etx = vert->path_etx;
 281 +      res = vert;
 282 +    }
 283 +    else if (!vert->done && vert->path_etx == best_etx && vert < res)
 284 +    {
 285 +      // Otherwise order is undefined if etx==etx and debug will complain
 286 +      best_etx = vert->path_etx;
 287 +      res = vert;
 288 +    }
 289 +
 290 +    node = list_get_next(node);
 291 +  }
 292 +#endif
 293 +  if (NULL == etx_cache)
 294 +  {
 295 +    int count = 0;
 296 +    node = list_get_head(vertex_list);
 297 +    while (node != NULL)
 298 +    {
 299 +      vert = node->data;
 300 +      if (!vert->done && vert->path_etx < INFINITE_ETX) count++;
 301 +      node = list_get_next(node);
 302 +    }
 303 +    if (0 < count)
 304 +    {
 305 +      etx_cache = olsr_malloc(sizeof(etx_cache[0]) * count, "ETX Cache");
 306 +#ifdef SVEN_OPT_DBG
 307 +      printf("count=%d, Malloc(%d)=%p\n", count, sizeof(etx_cache[0]) * count, etx_cache);
 308 +#endif
 309 +      node = list_get_head(vertex_list);
 310 +      etx_cache_count = 0;
 311 +      etx_cache_get = 0;
 312 +      while (node != NULL)
 313 +      {
 314 +        vert = node->data;
 315 +        if (!vert->done && vert->path_etx < INFINITE_ETX)
 316 +        {
 317 +          etx_cache[etx_cache_count] = vert;
 318 +          etx_cache_count++;
 319 +        }
 320 +        node = list_get_next(node);
 321 +      }
 322 +#ifdef SVEN_OPT_DBG
 323 +      printf("qsort(etx_cache_count=%d)\n", etx_cache_count);
 324 +#endif
 325 +      qsort(etx_cache, etx_cache_count, sizeof(etx_cache[0]), etx_cache_compare);
 326 +#ifdef SVEN_OPT_DBG
 327 +      if (0 < etx_cache_count)
 328 +      {
 329 +        int i = 0;
 330 +        while(i < etx_cache_count && i < 10)
 331 +        {
 332 +          printf("%d: %p=%f\n", i, etx_cache[i], etx_cache[i]->path_etx);
 333 +          i++;
 334 +        }
 335 +      }
 336 +#endif
 337 +    }
 338 +  }
 339 +
 340 +#ifdef SVEN_OPT_DBG
 341 +  if (NULL != etx_cache)
 342 +  {
 343 +    struct dijk_vertex *rescache = NULL;
 344 +    if (etx_cache_get < etx_cache_count)
 345 +    {
 346 +      rescache = etx_cache[etx_cache_get++];
 347 +    }
 348 +    if (res != rescache)
 349 +    {
 350 +      printf("miss: etx_cache_get=%d, res=%p,%f != rescache=%p,%f\n",
 351 +        etx_cache_get, res, (NULL != res ? res->path_etx : -1), rescache, (NULL != rescache ? rescache->path_etx : -1));
 352 +    }
 353 +    else
 354 +    {
 355 +      etx_cache_saved++;
 356 +    }
 357 +  }
 358 +#else
 359 +  if (NULL != etx_cache && etx_cache_get < etx_cache_count)
 360 +  {
 361 +    res = etx_cache[etx_cache_get++];
 362 +  }
 363 +#endif
 364 +
 365 +  // if we've found a vertex, remove it from the set
 366 +
 367 +  if (res != NULL)
 368 +    res->done = OLSR_TRUE;
 369 +
 370 +  return res;
 371 +}
 372 +#endif // SVEN_OPT
 373
 374  static struct dijk_vertex *extract_best(struct list *vertex_list)
 375  {
 376 @@ -371,7 +529,11 @@
 377    struct interface *inter;
 378
 379    if (ipsize == 4)
 380 +#ifndef DISABLE_SVEN_OLA
 381 +    avl_comp = 0;
 382 +#else
 383      avl_comp = avl_comp_ipv4;
 384 +#endif
 385
 386    else
 387      avl_comp = avl_comp_ipv6;
 388 @@ -614,13 +776,27 @@
 389
 390    // add HNA routes - the set of unprocessed network nodes contains
 391    // all reachable network nodes
 392 +#ifdef SVEN_OPT
 393 +#ifdef SVEN_OPT_DBG
 394 +  printf("free etx_cache, saved compares=%d, etx_cache=%p\n", etx_cache_saved, etx_cache);
 395 +  etx_cache_saved = 0;
 396 +#endif
 397 +  if (NULL != etx_cache) {
 398 +    free(etx_cache);
 399 +    etx_cache = NULL;
 400 +  }
 401 +#endif
 402
 403    for (;;)
 404    {
 405      // extract the network node with the best ETX and remove it
 406      // from the set of unprocessed network nodes
 407
 408 +#ifdef SVEN_OPT
 409 +    vert = extract_best_route(&vertex_list);
 410 +#else
 411      vert = extract_best(&vertex_list);
 412 +#endif
 413
 414      // no more nodes left
 415
 416 diff -Nur olsrd-0.4.10.orig/src/olsr_types.h olsrd-0.4.10/src/olsr_types.h
 417 --- olsrd-0.4.10.orig/src/olsr_types.h  2005-05-15 14:57:24.000000000 +0200
 418 +++ olsrd-0.4.10/src/olsr_types.h       2006-11-12 09:33:49.000000000 +0100
 419 @@ -93,6 +93,7 @@
 420  union olsr_ip_addr
 421  {
 422    olsr_u32_t v4;
 423 +  olsr_u8_t v4x[4];
 424    struct in6_addr v6;
 425  };
 426