add updated olsrd fixes and optimizations from sven-ola
[openwrt/svn-archive/archive.git] / net / olsrd / patches / 140-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