commits May 2010

commits@lists.open-mesh.org

1 participants
83 discussions

r1664 - branches/batctl-0.2.x
by postmaster＠open-mesh.net 21 May '10

21 May '10

Author: marek Date: 2010-05-21 06:43:57 +0200 (Fri, 21 May 2010) New Revision: 1664 Modified: branches/batctl-0.2.x/Makefile branches/batctl-0.2.x/ping.c Log: batctl: Correct mdev calculation in ping subcommand Fixes the calculation of the mean absolute deviation (mdev) of the roundtrip times. mdev was previously calculated by computing the difference of maximum and minimum round trip times. The calculation is now done using the same formula as in the iputils ping program. Signed-off-by: Daniel Seither <post(a)tiwoc.de> Acked-by: Sven Eckelmann <sven.eckelmann(a)gmx.de> Modified: branches/batctl-0.2.x/Makefile =================================================================== --- branches/batctl-0.2.x/Makefile 2010-05-21 04:17:54 UTC (rev 1663) +++ branches/batctl-0.2.x/Makefile 2010-05-21 04:43:57 UTC (rev 1664) @@ -28,7 +28,7 @@ CC = gcc CFLAGS += -pedantic -Wall -W -g3 -std=gnu99 -Os -fno-strict-aliasing EXTRA_CFLAGS = -DREVISION_VERSION=$(REVISION_VERSION) -LDFLAGS += +LDFLAGS += -lm SBINDIR = $(INSTALL_PREFIX)/usr/sbin Modified: branches/batctl-0.2.x/ping.c =================================================================== --- branches/batctl-0.2.x/ping.c 2010-05-21 04:17:54 UTC (rev 1663) +++ branches/batctl-0.2.x/ping.c 2010-05-21 04:43:57 UTC (rev 1664) @@ -1,4 +1,4 @@ -/* +/* * Copyright (C) 2007-2010 B.A.T.M.A.N. contributors: * * Andreas Langer <a.langer(a)q-dsl.de>, Marek Lindner <lindner_marek(a)yahoo.de> @@ -29,6 +29,7 @@ #include <signal.h> #include <fcntl.h> #include <string.h> +#include <math.h> #include "main.h" #include "ping.h" @@ -75,7 +76,7 @@ unsigned int seq_counter = 0, packets_out = 0, packets_in = 0, packets_loss; char *dst_string, *mac_string; double time_delta; - float min = 0.0, max = 0.0, avg = 0.0; + float min = 0.0, max = 0.0, avg = 0.0, mdev = 0.0; while ((optchar = getopt(argc, argv, "hc:i:t:")) != -1) { switch (optchar) { @@ -213,6 +214,7 @@ if (time_delta > max) max = time_delta; avg += time_delta; + mdev += time_delta * time_delta; packets_in++; break; case DESTINATION_UNREACHABLE: @@ -242,11 +244,24 @@ else packets_loss = ((packets_out - packets_in) * 100) / packets_out; + if (packets_in) { + avg /= packets_in; + mdev /= packets_in; + mdev = mdev - avg * avg; + if (mdev > 0.0) + mdev = sqrt(mdev); + else + mdev = 0.0; + } else { + avg = 0.0; + mdev = 0.0; + } + printf("--- %s ping statistics ---\n", dst_string); printf("%u packets transmitted, %u received, %u%% packet loss\n", packets_out, packets_in, packets_loss); printf("rtt min/avg/max/mdev = %.3f/%.3f/%.3f/%.3f ms\n", - min, (packets_in ? (avg / packets_in) : 0.000), max, (max - min)); + min, avg, max, mdev); ret = EXIT_SUCCESS;

1 0

r1663 - trunk/batctl
by postmaster＠open-mesh.net 21 May '10

21 May '10

Author: marek Date: 2010-05-21 06:17:54 +0200 (Fri, 21 May 2010) New Revision: 1663 Modified: trunk/batctl/Makefile trunk/batctl/ping.c Log: batctl: Correct mdev calculation in ping subcommand Fixes the calculation of the mean absolute deviation (mdev) of the roundtrip times. mdev was previously calculated by computing the difference of maximum and minimum round trip times. The calculation is now done using the same formula as in the iputils ping program. Signed-off-by: Daniel Seither <post(a)tiwoc.de> Acked-by: Sven Eckelmann <sven.eckelmann(a)gmx.de> Modified: trunk/batctl/Makefile =================================================================== --- trunk/batctl/Makefile 2010-05-21 04:17:53 UTC (rev 1662) +++ trunk/batctl/Makefile 2010-05-21 04:17:54 UTC (rev 1663) @@ -28,7 +28,7 @@ CC = gcc CFLAGS += -pedantic -Wall -W -g3 -std=gnu99 -Os -fno-strict-aliasing EXTRA_CFLAGS = -DREVISION_VERSION=$(REVISION_VERSION) -LDFLAGS += +LDFLAGS += -lm SBINDIR = $(INSTALL_PREFIX)/usr/sbin Modified: trunk/batctl/ping.c =================================================================== --- trunk/batctl/ping.c 2010-05-21 04:17:53 UTC (rev 1662) +++ trunk/batctl/ping.c 2010-05-21 04:17:54 UTC (rev 1663) @@ -29,6 +29,7 @@ #include <signal.h> #include <fcntl.h> #include <string.h> +#include <math.h> #include "main.h" #include "ping.h" @@ -76,7 +77,7 @@ unsigned int seq_counter = 0, packets_out = 0, packets_in = 0, packets_loss; char *dst_string, *mac_string, *rr_string; double time_delta; - float min = 0.0, max = 0.0, avg = 0.0; + float min = 0.0, max = 0.0, avg = 0.0, mdev = 0.0; uint8_t last_rr_cur = 0, last_rr[BAT_RR_LEN][ETH_ALEN]; size_t packet_len; @@ -260,6 +261,7 @@ if (time_delta > max) max = time_delta; avg += time_delta; + mdev += time_delta * time_delta; packets_in++; break; case DESTINATION_UNREACHABLE: @@ -289,11 +291,24 @@ else packets_loss = ((packets_out - packets_in) * 100) / packets_out; + if (packets_in) { + avg /= packets_in; + mdev /= packets_in; + mdev = mdev - avg * avg; + if (mdev > 0.0) + mdev = sqrt(mdev); + else + mdev = 0.0; + } else { + avg = 0.0; + mdev = 0.0; + } + printf("--- %s ping statistics ---\n", dst_string); printf("%u packets transmitted, %u received, %u%% packet loss\n", packets_out, packets_in, packets_loss); printf("rtt min/avg/max/mdev = %.3f/%.3f/%.3f/%.3f ms\n", - min, (packets_in ? (avg / packets_in) : 0.000), max, (max - min)); + min, avg, max, mdev); ret = EXIT_SUCCESS;

1 0

r1662 - trunk/batctl
by postmaster＠open-mesh.net 21 May '10

21 May '10

Author: marek Date: 2010-05-21 06:17:53 +0200 (Fri, 21 May 2010) New Revision: 1662 Modified: trunk/batctl/tcpdump.c Log: batctl: adjust tcpdump to expanded ogm seqno Signed-off-by: Marek Lindner <lindner_marek(a)yahoo.de> Modified: trunk/batctl/tcpdump.c =================================================================== --- trunk/batctl/tcpdump.c 2010-05-21 04:17:52 UTC (rev 1661) +++ trunk/batctl/tcpdump.c 2010-05-21 04:17:53 UTC (rev 1662) @@ -264,9 +264,9 @@ printf("BAT %s: ", get_name_by_macaddr((struct ether_addr *)batman_packet->orig, read_opt)); - printf("OGM via neigh %s, seqno %d, tq %3d, ttl %2d, v %d, flags [%c%c%c], length %zu\n", + printf("OGM via neigh %s, seqno %u, tq %3d, ttl %2d, v %d, flags [%c%c%c], length %zu\n", get_name_by_macaddr((struct ether_addr *)ether_header->ether_shost, read_opt), - ntohs(batman_packet->seqno), batman_packet->tq, + ntohl(batman_packet->seqno), batman_packet->tq, batman_packet->ttl, batman_packet->version, (batman_packet->flags & DIRECTLINK ? 'D' : '.'), (batman_packet->flags & VIS_SERVER ? 'V' : '.'),

1 0

r1661 - trunk/batman-adv-kernelland
by postmaster＠open-mesh.net 21 May '10

21 May '10

Author: marek Date: 2010-05-21 06:17:52 +0200 (Fri, 21 May 2010) New Revision: 1661 Modified: trunk/batman-adv-kernelland/compat.h Log: batman-adv: fix endless loop on older kernels Older kernels (>2.6.23) do not provide the cancel_delayed_work_sync() function and were redefined to cancel_rearming_delayed_work() which caused an endless loop, since it waited for the workqueue to re-arm itself. The batman-adv packet queue would not re-arm itself, hence it blocked the whole module / kernel in a busy loop. Signed-off-by: Marek Lindner <lindner_marek(a)yahoo.de> Acked-by: Sven Eckelmann <sven.eckelmann(a)gmx.de> Modified: trunk/batman-adv-kernelland/compat.h =================================================================== --- trunk/batman-adv-kernelland/compat.h 2010-05-21 04:17:51 UTC (rev 1660) +++ trunk/batman-adv-kernelland/compat.h 2010-05-21 04:17:52 UTC (rev 1661) @@ -70,7 +70,7 @@ return 0; } -#define cancel_delayed_work_sync(wq) cancel_rearming_delayed_work(wq) +#define cancel_delayed_work_sync(wq) cancel_delayed_work(wq) #endif /* < KERNEL_VERSION(2, 6, 23) */

1 0

r1660 - trunk/batman-adv-kernelland
by postmaster＠open-mesh.net 21 May '10

21 May '10

Author: marek Date: 2010-05-21 06:17:51 +0200 (Fri, 21 May 2010) New Revision: 1660 Modified: trunk/batman-adv-kernelland/send.c Log: batman-adv: fix rogue packets on shutdown On module shutdown batman-adv would purge the internal packet queue by sending all remaining packets which could confuse other nodes. Now, the packets are silently discarded. Signed-off-by: Marek Lindner <lindner_marek(a)yahoo.de> Modified: trunk/batman-adv-kernelland/send.c =================================================================== --- trunk/batman-adv-kernelland/send.c 2010-05-17 08:32:46 UTC (rev 1659) +++ trunk/batman-adv-kernelland/send.c 2010-05-21 04:17:51 UTC (rev 1660) @@ -460,6 +460,9 @@ hlist_del(&forw_packet->list); spin_unlock_irqrestore(&forw_bcast_list_lock, flags); + if (atomic_read(&module_state) == MODULE_DEACTIVATING) + goto out; + /* rebroadcast packet */ rcu_read_lock(); list_for_each_entry_rcu(batman_if, &if_list, list) { @@ -473,15 +476,15 @@ forw_packet->num_packets++; - /* if we still have some more bcasts to send and we are not shutting - * down */ - if ((forw_packet->num_packets < 3) && - (atomic_read(&module_state) != MODULE_DEACTIVATING)) + /* if we still have some more bcasts to send */ + if (forw_packet->num_packets < 3) { _add_bcast_packet_to_list(forw_packet, ((5 * HZ) / 1000)); - else { - forw_packet_free(forw_packet); - atomic_inc(&bat_priv->bcast_queue_left); + return; } + +out: + forw_packet_free(forw_packet); + atomic_inc(&bat_priv->bcast_queue_left); } void send_outstanding_bat_packet(struct work_struct *work) @@ -498,6 +501,9 @@ hlist_del(&forw_packet->list); spin_unlock_irqrestore(&forw_bat_list_lock, flags); + if (atomic_read(&module_state) == MODULE_DEACTIVATING) + goto out; + send_packet(forw_packet); /** @@ -505,10 +511,10 @@ * to determine the queues wake up time unless we are * shutting down */ - if ((forw_packet->own) && - (atomic_read(&module_state) != MODULE_DEACTIVATING)) + if (forw_packet->own) schedule_own_packet(forw_packet->if_incoming); +out: /* don't count own packet */ if (!forw_packet->own) atomic_inc(&bat_priv->batman_queue_left);

1 0

r1659 - trunk/batman-adv-kernelland
by postmaster＠open-mesh.net 17 May '10

17 May '10

Author: marek Date: 2010-05-17 10:32:46 +0200 (Mon, 17 May 2010) New Revision: 1659 Modified: trunk/batman-adv-kernelland/hard-interface.c Log: batman-adv: remove all rcu head initializations Remove all rcu head inits. We don't care about the RCU head state before passing it to call_rcu() anyway. Only leave the "on_stack" variants so debugobjects can keep track of objects on stack. Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers(a)efficios.com> Signed-off-by: Paul E. McKenney <paulmck(a)linux.vnet.ibm.com> Cc: Andrew Lunn <andrew(a)lunn.ch> Cc: Simon Wunderlich <siwu(a)hrz.tu-chemnitz.de> Cc: Marek Lindner <lindner_marek(a)yahoo.de> Cc: Sven Eckelmann <sven.eckelmann(a)gmx.de> Signed-off-by: Greg Kroah-Hartman <gregkh(a)suse.de> Signed-off-by: Sven Eckelmann <sven.eckelmann(a)gmx.de> Modified: trunk/batman-adv-kernelland/hard-interface.c =================================================================== --- trunk/batman-adv-kernelland/hard-interface.c 2010-05-17 08:18:55 UTC (rev 1658) +++ trunk/batman-adv-kernelland/hard-interface.c 2010-05-17 08:32:46 UTC (rev 1659) @@ -341,7 +341,6 @@ batman_if->if_num = -1; batman_if->net_dev = net_dev; batman_if->if_status = IF_NOT_IN_USE; - INIT_RCU_HEAD(&batman_if->rcu); INIT_LIST_HEAD(&batman_if->list); check_known_mac_addr(batman_if->net_dev->dev_addr);

1 0

r1658 - trunk/batctl
by postmaster＠open-mesh.net 17 May '10

17 May '10

Author: marek Date: 2010-05-17 10:18:55 +0200 (Mon, 17 May 2010) New Revision: 1658 Modified: trunk/batctl/tcpdump.c Log: batctl: adjust tcpdump to expanded bcast seqno Signed-off-by: Marek Lindner <lindner_marek(a)yahoo.de> Modified: trunk/batctl/tcpdump.c =================================================================== --- trunk/batctl/tcpdump.c 2010-05-17 08:18:51 UTC (rev 1657) +++ trunk/batctl/tcpdump.c 2010-05-17 08:18:55 UTC (rev 1658) @@ -376,9 +376,9 @@ printf("BAT %s: ", get_name_by_macaddr((struct ether_addr *)ether_header->ether_shost, read_opt)); - printf("BCAST, orig %s, seqno %hu, ", + printf("BCAST, orig %s, seqno %u, ", get_name_by_macaddr((struct ether_addr *)bcast_packet->orig, read_opt), - ntohs(bcast_packet->seqno)); + ntohl(bcast_packet->seqno)); ether_header = (struct ether_header *)(packet_buff + sizeof(struct ether_header) + sizeof(struct bcast_packet));

1 0

r1657 - trunk/batman-adv-kernelland
by postmaster＠open-mesh.net 17 May '10

17 May '10

Author: marek Date: 2010-05-17 10:18:51 +0200 (Mon, 17 May 2010) New Revision: 1657 Modified: trunk/batman-adv-kernelland/translation-table.c Log: batman-adv: remove superfluous hint to "translation table" Signed-off-by: Marek Lindner <lindner_marek(a)yahoo.de> Modified: trunk/batman-adv-kernelland/translation-table.c =================================================================== --- trunk/batman-adv-kernelland/translation-table.c 2010-05-17 03:20:36 UTC (rev 1656) +++ trunk/batman-adv-kernelland/translation-table.c 2010-05-17 08:18:51 UTC (rev 1657) @@ -400,8 +400,7 @@ } hdr_len = sprintf(buff, - "Globally announced HNAs received via the mesh %s " - "(translation table):\n", + "Globally announced HNAs received via the mesh %s\n", net_dev->name); if (off < hdr_len)

1 0

r1656 - in trunk/batman-experimental: . lib/bmx_gsf_map
by postmaster＠open-mesh.net 17 May '10

17 May '10

Author: axel Date: 2010-05-17 05:20:36 +0200 (Mon, 17 May 2010) New Revision: 1656 Modified: trunk/batman-experimental/avl.c trunk/batman-experimental/avl.h trunk/batman-experimental/batman.c trunk/batman-experimental/hna.c trunk/batman-experimental/lib/bmx_gsf_map/gsf_map.c trunk/batman-experimental/originator.c Log: avl.ch, hna.c batman.c originator.c gsf_map.c allow crawling upwards an avl tree, modify some avl_..() functions... Modified: trunk/batman-experimental/avl.c =================================================================== --- trunk/batman-experimental/avl.c 2010-05-17 03:10:17 UTC (rev 1655) +++ trunk/batman-experimental/avl.c 2010-05-17 03:20:36 UTC (rev 1656) @@ -20,13 +20,14 @@ /* * avl code inspired by: * http://eternallyconfuzzled.com/tuts/datastructures/jsw_tut_avl.aspx - * where Julienne Walker said ( 28. 2. 2010 12:55): + * where Julienne Walker said (web page from 28. 2. 2010 12:55): * ...Once again, all of the code in this tutorial is in the public domain. * You can do whatever you want with it, but I assume no responsibility * for any damages from improper use. ;-) */ + #include <stdio.h> #include <string.h> #include <stdlib.h> @@ -38,61 +39,70 @@ #include "avl.h" -void *avl_find( struct avl_tree *tree, void *key ) + +struct avl_node *avl_find( struct avl_tree *tree, void *key ) { - - struct avl_node *it = tree->root; + struct avl_node *an = tree->root; int cmp; // Search for a dead path or a matching entry - while ( it && ( cmp = memcmp(it->key, key, tree->key_size) ) ) - it = it->link[ cmp < 0 ]; + while ( an && ( cmp = memcmp(an->key, key, tree->key_size) ) ) + an = an->link[ cmp < 0 ]; - - return it ? it->key : NULL; + return an; } +struct avl_node *avl_next(struct avl_tree *tree, void *key) +{ + struct avl_node *an = tree->root; + struct avl_node *best = NULL; + int cmp; -void *avl_next(struct avl_tree *tree, void *key) + while (an) { + + cmp = (memcmp(an->key, key, tree->key_size) <= 0); + + if (an->link[cmp]) { + best = cmp ? best : an; + an = an->link[cmp]; + } else { + return cmp ? best : an; + } + + } + return NULL; +} + +struct avl_node *avl_iterate(struct avl_tree *tree, struct avl_node *an ) { - struct avl_node *it = tree->root; - void *best = NULL; - if ( !it ) - return NULL; + if ( !an || an->link[1] ) { - while (it) { + an = an ? an->link[1] : tree->root; - if ( memcmp(it->key, key, tree->key_size) <= 0 ) { + while ( an && an->link[0] ) + an = an->link[0]; - if (it->link[1]) { - it = it->link[1]; - continue; - } else { - return best; - } + return an; + } - } else { + struct avl_node *prev = an; - if (it->link[0]) { - best = it->key; - it = it->link[0]; - continue; - } else { - return it->key; - } + while ((an = an->up)) { - } + if ( an->link[0] == prev ) + return an; + prev = an; } - paranoia( -500177, 1 ); return NULL; } + static struct avl_node *avl_create_node(void *key) { struct avl_node *an = debugMalloc(sizeof (struct avl_node), 327); @@ -106,13 +116,22 @@ static struct avl_node *avl_rotate_single(struct avl_node *root, int dir) { - struct avl_node *save = root->link[!dir]; + struct avl_node *save; int rlh, rrh, slh; /* Rotate */ - root->link[!dir] = save->link[dir]; + save = root->link[!dir]; + + root->link[!dir] = save->link[dir]; + + if (root->link[!dir]) + root->link[!dir]->up = root; + save->link[dir] = root; + if ( root ) + root->up = save; + /* Update balance factors */ rlh = avl_height(root->link[0]); rrh = avl_height(root->link[1]); @@ -127,12 +146,16 @@ static struct avl_node *avl_rotate_double(struct avl_node *root, int dir) { root->link[!dir] = avl_rotate_single(root->link[!dir], !dir); + + if (root->link[!dir]) + root->link[!dir]->up = root; + return avl_rotate_single(root, dir); } void avl_insert(struct avl_tree *tree, void *key) { - + if (tree->root) { struct avl_node *it = tree->root; @@ -143,7 +166,8 @@ /* Search for an empty link, save the path */ for (;;) { /* Push direction and node onto stack */ - upd[top] = memcmp(it->key, key, tree->key_size) < 0; +// upd[top] = memcmp(it->key, key, tree->key_size) < 0; + upd[top] = memcmp(it->key, key, tree->key_size) <= 0; up[top++] = it; if (it->link[upd[top - 1]] == NULL) @@ -154,6 +178,7 @@ /* Insert a new node at the bottom of the tree */ it->link[upd[top - 1]] = avl_create_node(key); + it->link[upd[top - 1]]->up = it; paranoia(-500178, (it->link[upd[top - 1]] == NULL)); @@ -178,11 +203,15 @@ up[top] = avl_rotate_double(up[top], !upd[top]); /* Fix parent */ - if (top != 0) + if (top != 0) { up[top - 1]->link[upd[top - 1]] = up[top]; - else + up[top]->up = up[top - 1]; + } else { tree->root = up[0]; + up[0]->up = NULL; + } + done = 1; } @@ -193,7 +222,7 @@ up[top]->balance = max + 1; } - + } else { tree->root = avl_create_node(key); @@ -206,7 +235,7 @@ -void avl_remove(struct avl_tree *tree, void *key) +void *avl_remove(struct avl_tree *tree, void *key) { struct avl_node *it = tree->root; struct avl_node *up[AVL_MAX_HEIGHT]; @@ -214,29 +243,38 @@ paranoia(-500182, !it); // paranoia if not found - while ((cmp = memcmp(it->key, key, tree->key_size))) { +// while ((cmp = memcmp(it->key, key, tree->key_size)) ) { + while ((cmp = memcmp(it->key, key, tree->key_size)) || (it->link[0] && !memcmp(it->link[0]->key, key, tree->key_size))) { // Push direction and node onto stack upd[top] = (cmp < 0); up[top] = it; + top++; - it = it->link[(cmp < 0)]; - top++; - paranoia(-500180, !it); // paranoia if not found + if (!(it = it->link[(cmp < 0)])) + return NULL; + } + // remember and return the found key. It might have been another one than intended + key = it->key; + // Remove the node: if (!(it->link[0] && it->link[1])) { // at least one child is NULL: - + // Which child is not null? int dir = !(it->link[0]); /* Fix parent */ - if (top) + if (top) { up[top - 1]->link[upd[top - 1]] = it->link[dir]; - else + if (it->link[dir]) + it->link[dir]->up = up[top - 1]; + } else { tree->root = it->link[dir]; - + if (tree->root) + tree->root->up = NULL; + } debugFree(it, 1327); } else { // both childs NOT NULL: @@ -262,6 +300,9 @@ // Unlink successor and fix parent up[top - 1]->link[ (up[top - 1] == it) ] = heir->link[1]; + if ( heir->link[1]) + heir->link[1]->up = up[top - 1]; + debugFree(heir, 2327); } @@ -306,11 +347,292 @@ up[top] = avl_rotate_double(up[top], upd[top]); // Fix parent: - if (top) + if (top) { up[top - 1]->link[upd[top - 1]] = up[top]; - else + up[top]->up = up[top - 1]; + } else { tree->root = up[0]; + tree->root->up = NULL; + } } + return key; + } +#ifdef AVL_DEBUG + +struct avl_node *_avl_iter_down(int dir, struct avl_node *an, struct avl_iterator *it ) { + + for (; an; it->top++) { + /* Push direction and node onto stack */ + it->up[it->top] = an; + it->upd[it->top] = dir; + + an = an->link[dir]; + } + it->top--; + return it->up[it->top]; +} + +struct avl_node *avl_iter(struct avl_tree *tree, struct avl_iterator *it ) { + + struct avl_node *an = tree->root; + if ( !an ) + return NULL; + + if (!it->up[0]) { + // Get initial element and fill stack: + // go left... + it->top=0; + return _avl_iter_down( 0/*left*/, an, it ); + } + + if ((an = it->up[(it->top)]->link[1])) { + //go one right, then left... + it->upd[it->top] = 1; + it->top++; + return _avl_iter_down(0, an, it); + } + + while (it->top > 0 && it->upd[(it->top) - 1] == 1 /*was: down right*/) { + //so go one back up (up-left = opposite of down right) + it->top--; + } + + if (it->top > 0 && it->upd[(it->top) - 1] == 0 /*was: down left*/) { + //so go one back up (up-right = opposite of down left)): + it->top--; + return it->up[it->top]; + } + + it->up[0] = NULL; + return NULL; +} + +void avl_debug( struct avl_tree *tree ) { + + #define AVL_DBG_COL_CHARS 6 + + int i,j; + + int depth_min = 0; + + struct avl_node *an; + for (an = tree->root; an; an = an->link[0]) + depth_min++; + + int depth_max = depth_min+2; + int width = 1<<depth_max; + + char * dbg_mem = malloc( depth_max * width * AVL_DBG_COL_CHARS + 1); + memset( dbg_mem, ' ', depth_max * width * AVL_DBG_COL_CHARS + 1 ); + + for( i=1; i<=depth_max; i++ ) + dbg_mem[(i*width*AVL_DBG_COL_CHARS)-1] = '\n'; + + dbg_mem[ depth_max * width * AVL_DBG_COL_CHARS ] = 0; + + struct avl_iterator it; + memset ( &it, 0, sizeof( struct avl_iterator ) ); + + while( (an = avl_iter( tree, &it )) ) { + + j = (width - 1) * AVL_DBG_COL_CHARS / 2; + + for (i = 0; i < it.top; i++) { + + int k = ((width - 1) * AVL_DBG_COL_CHARS ); + int l = 4<<i; + int m = ( it.upd[i]?1:-1); + + j = j + (m * k / l); + } + +// dbg_mem[((i * width * AVL_DBG_COL_CHARS) + j)] = 'x'; + + snprintf(&dbg_mem[((i * width * AVL_DBG_COL_CHARS) + j)], AVL_DBG_COL_CHARS, + "%3d/%1d", ((int*) (an->key))[0], ((int*) (an->key))[1]); + + dbg_mem[((i * width * AVL_DBG_COL_CHARS) + j + (AVL_DBG_COL_CHARS-1))] = ' '; + + + printf("%3d/%1d ", ((int*) (an->key))[0], ((int*) (an->key))[1]); + } + + + dbg_mem[ depth_max * width * AVL_DBG_COL_CHARS ] = 0; + + printf("\n-----\n%s\n-----\n", dbg_mem ); + +} +#endif + + +#ifdef AVL_TEST +static void avl_test() +{ + + + struct avl_node *an = NULL; + AVL_TREE(t, sizeof (int)); + + int i; + + struct p { + int i; + int v; + }; + struct p * p; + + + for (i = 0; i <= 19; i++) { + p = debugMalloc(sizeof ( struct p), 999); + p->i = i; + p->v = 0; + avl_insert(&t, p); + } + + + for (i = 19; i >= 10; i--) { + p = avl_remove(&t, &i); + printf(" removed %d/%d\n", p->i, p->v ); + debugFree( p, 1999 ); + } + + for (i = 9; i >= 0; i--) { + p = debugMalloc(sizeof ( struct p), 999); + p->i = i; + p->v = 1; + avl_insert(&t, p); + } + + for (i = 5; i <= 15; i++) { + p = debugMalloc(sizeof ( struct p), 999); + p->i = i; + p->v = 2; + avl_insert(&t, p); + } + + for (i = 3; i <= 9; i++) { + p = debugMalloc(sizeof ( struct p), 999); + p->i = 2; + p->v = i; + avl_insert(&t, p); + } + + printf("\navl_iterate():\n"); + i=0; + an = NULL; + while( (an = avl_iterate( &t, an ) ) ) { + p = ((struct p*)(an->key)); + if ( i > p->i) + printf("\nERROR %d > %d \n", i, p->i); + i = p->i; + printf( "%3d/%1d ", p->i, p->v ); + } + printf("\n"); + +#ifdef AVL_DEBUG + printf("avl_debug():\n"); + avl_debug( &t ); +#endif + + + for (i = 9; i >= 3; i--) { + int v = 2; + if ((p = avl_remove(&t, &v)) ) { + printf(" removed %d/%d\n", p->i, p->v); + debugFree(p, 1999); + } + } + + + for (i = 9; i >= 0; i--) { + if ( (p = avl_remove(&t, &i) ) ) { + printf(" removed %d/%d\n", p->i, p->v); + debugFree(p, 1999); + } + } + + for (i = 0; i <= 19; i++) { + if ((p = avl_remove(&t, &i))) { + printf(" removed %d/%d\n", p->i, p->v); + debugFree(p, 1999); + } else { + printf(" failed rm %d\n", i); + } + } + + + + + + + +/* for (i = 20; i >= 0; i--) { + + p = debugMalloc(sizeof ( struct p), 999); + p->i = i; + p->v = 5; + avl_insert(&t, p); + } +*/ + + i = 0; + + printf("\n"); + + + printf("\navl_next():\n"); + + int32_t j = 0; + while( (an = avl_next( &t, &j )) ) { + p = ((struct p*)(an->key)); + j = p->i; + if ( i > p->i) + printf("\nERROR %d > %d \n", i, p->i); + + i = p->i; + + printf( "N%4d/%1d ", p->i, p->v ); + + if ( i%10 == 0 ) + printf("\n"); + + } + + + printf("\navl_iterate():\n"); + i=0; + while( (an = avl_iterate( &t, an ) ) ) { + p = ((struct p*)(an->key)); + if ( i > p->i) + printf("\nERROR %d > %d \n", i, p->i); + i = p->i; + printf( "%3d/%1d ", p->i, p->v ); + } + printf("\n"); + +#ifdef AVL_DEBUG + printf("avl_debug():\n"); + avl_debug( &t ); +#endif + + + + while( t.root ) { + p = (struct p*)t.root->key; + p = avl_remove( &t, p ); + printf(" removed %d/%d\n", p->i, p->v ); + debugFree( p, 1999 ); + + } + + printf("\n"); + + cleanup_all(CLEANUP_SUCCESS); + + +} +#endif Modified: trunk/batman-experimental/avl.h =================================================================== --- trunk/batman-experimental/avl.h 2010-05-17 03:10:17 UTC (rev 1655) +++ trunk/batman-experimental/avl.h 2010-05-17 03:20:36 UTC (rev 1656) @@ -18,24 +18,26 @@ */ /* - * avl code based on: + * avl code inspired by: * http://eternallyconfuzzled.com/tuts/datastructures/jsw_tut_avl.aspx - * where Julienne Walker said ( 28. 2. 2010 12:55): + * where Julienne Walker said (web page from 28. 2. 2010 12:55): * ...Once again, all of the code in this tutorial is in the public domain. * You can do whatever you want with it, but I assume no responsibility * for any damages from improper use. ;-) */ - #ifndef _AVL_H #define _AVL_H #include <stdint.h> +#define AVL_MAX_HEIGHT 128 + struct avl_node { void *key; int balance; - struct avl_node * link[2]; + struct avl_node * up; + struct avl_node * link[2]; }; struct avl_tree { @@ -47,17 +49,27 @@ #define AVL_INIT_TREE(tree, size) do { tree.root = NULL; tree.key_size = (size); } while (0) #define AVL_TREE(tree, size) struct avl_tree (tree) = { (size), NULL } - -#define AVL_MAX_HEIGHT 128 - #define avl_height(p) ((p) == NULL ? -1 : (p)->balance) #define avl_max(a,b) ((a) > (b) ? (a) : (b)) -void *avl_find( struct avl_tree *tree, void *key ); -void *avl_next( struct avl_tree *tree, void *key ); + +struct avl_node *avl_find( struct avl_tree *tree, void *key ); +struct avl_node *avl_next( struct avl_tree *tree, void *key ); +struct avl_node *avl_iterate(struct avl_tree *tree, struct avl_node *it ); + void avl_insert(struct avl_tree *tree, void *key); -void avl_remove(struct avl_tree *tree, void *key); +void *avl_remove(struct avl_tree *tree, void *key); +#ifdef AVL_DEBUG +struct avl_iterator { + struct avl_node * up[AVL_MAX_HEIGHT]; + int upd[AVL_MAX_HEIGHT]; + int top; +}; +struct avl_node *avl_iter(struct avl_tree *tree, struct avl_iterator *it ); +void avl_debug( struct avl_tree *tree ); +#endif -#endif \ No newline at end of file + +#endif Modified: trunk/batman-experimental/batman.c =================================================================== --- trunk/batman-experimental/batman.c 2010-05-17 03:10:17 UTC (rev 1655) +++ trunk/batman-experimental/batman.c 2010-05-17 03:20:36 UTC (rev 1656) @@ -554,6 +554,7 @@ int dbg_ogm_out = 0; static char dbg_ogm_str[MAX_DBG_STR_SIZE + 1]; // TBD: must be checked for overflow when struct orig_node *on; + struct avl_node *an; uint16_t srv_count = 0; if ( cmd != OPT_APPLY ) @@ -563,7 +564,7 @@ uint32_t orig_ip = 0; - while ((on = (struct orig_node*) avl_next(&orig_avl, &orig_ip))) { + while ((on = (struct orig_node*) ((an = avl_next(&orig_avl, &orig_ip)) ? an->key : NULL))) { orig_ip = on->orig; Modified: trunk/batman-experimental/hna.c =================================================================== --- trunk/batman-experimental/hna.c 2010-05-17 03:10:17 UTC (rev 1655) +++ trunk/batman-experimental/hna.c 2010-05-17 03:20:36 UTC (rev 1656) @@ -47,8 +47,8 @@ // an hna entry for the given hna address, anetmask, and atype static struct hna_node *get_hna_node( struct hna_key *hk, uint8_t create ) { - struct hna_node *hn; - hn = ((struct hna_node *)avl_find( &hna_avl, hk )); + struct avl_node *an = avl_find( &hna_avl, hk ); + struct hna_node *hn = an ? (struct hna_node*) an->key : NULL; if ( hn ) { @@ -198,7 +198,8 @@ uint16_t array_len = 0; struct hna_key hk = {0,{0,0}}; - while ( (hn = avl_next( &hna_avl, &hk))) { + struct avl_node *an; + while ((hn = ((an = avl_next(&hna_avl, &hk)) ? an->key : NULL))) { hk = hn->key; if ( hn->status == HNA_HASH_NODE_MYONE ) { @@ -386,6 +387,7 @@ struct hna_key key; struct hna_node *hn; struct orig_node *orig_node; + struct avl_node *an; if ( cmd == OPT_APPLY ) { @@ -393,7 +395,7 @@ uint32_t orig_ip = 0; - while ((orig_node = (struct orig_node*) avl_next(&orig_avl, &orig_ip))) { + while ((orig_node = (struct orig_node*) ((an = avl_next(&orig_avl, &orig_ip)) ? an->key : NULL))) { orig_ip = orig_node->orig; Modified: trunk/batman-experimental/lib/bmx_gsf_map/gsf_map.c =================================================================== --- trunk/batman-experimental/lib/bmx_gsf_map/gsf_map.c 2010-05-17 03:10:17 UTC (rev 1655) +++ trunk/batman-experimental/lib/bmx_gsf_map/gsf_map.c 2010-05-17 03:20:36 UTC (rev 1656) @@ -145,13 +145,14 @@ if ( cmd == OPT_APPLY && cn ) { struct orig_node *orig_node; + struct avl_node *an; uint32_t count=0; dbg_printf( cn, "\nall_nodes = {\n" " '%s' : {\n", ipStr(primary_addr) ); uint32_t orig_ip = 0; - while ((orig_node = (struct orig_node*) avl_next(&orig_avl, &orig_ip))) { + while ((orig_node = (struct orig_node*) ((an=avl_next(&orig_avl, &orig_ip)) ? an->key : NULL ))) { orig_ip = orig_node->orig; Modified: trunk/batman-experimental/originator.c =================================================================== --- trunk/batman-experimental/originator.c 2010-05-17 03:10:17 UTC (rev 1655) +++ trunk/batman-experimental/originator.c 2010-05-17 03:20:36 UTC (rev 1656) @@ -922,11 +922,11 @@ static int8_t validate_considered_order( struct orig_node *orig_node, SQ_TYPE seqno, uint32_t neigh, struct batman_if *iif ) { - - struct neigh_node *nn; struct neigh_node_key key = {neigh, iif}; + struct avl_node *an = avl_find( &orig_node->neigh_avl, &key ); + struct neigh_node *nn = an ? (struct neigh_node*) an->key : NULL; - if ( (nn = (struct neigh_node*)avl_find( &orig_node->neigh_avl, &key )) ) { + if (nn) { paranoia( -500198, (nn->nnkey_addr != neigh || nn->nnkey_iif != iif ) ); @@ -960,8 +960,10 @@ struct orig_node *get_orig_node( uint32_t addr, uint8_t create ) { prof_start( PROF_get_orig_node ); - struct orig_node *orig_node = ((struct orig_node *)avl_find( &orig_avl, &addr)); + struct avl_node *an = avl_find( &orig_avl, &addr); + struct orig_node *orig_node = an ? (struct orig_node *) an->key : NULL; + if ( !create ) { prof_stop( PROF_get_orig_node ); return orig_node; @@ -1017,6 +1019,7 @@ prof_start( PROF_purge_originator ); struct list_head *neigh_pos, *neigh_temp, *neigh_prev; struct orig_node *orig_node = NULL; + struct avl_node *an; struct neigh_node *neigh_node; static char neigh_str[ADDR_STR_LEN]; @@ -1027,7 +1030,7 @@ /* for all origins... */ uint32_t orig_ip = 0; - while ( (orig_node = (struct orig_node*)avl_next( &orig_avl, &orig_ip ) ) ) { + while ((orig_node = (struct orig_node*) ((an = avl_next(&orig_avl, &orig_ip)) ? an->key : NULL))) { orig_ip = orig_node->orig; @@ -1512,6 +1515,7 @@ int32_t opt_show_origs ( uint8_t cmd, uint8_t _save, struct opt_type *opt, struct opt_parent *patch, struct ctrl_node *cn ) { struct orig_node *orig_node; + struct avl_node *an; uint16_t batman_count = 0; int dbg_ogm_out = 0, rq, tq, rtq; @@ -1530,7 +1534,7 @@ "knownSince lsqn(diff) lvld pws ~ogi cpu hop\n"); uint32_t orig_ip = 0; - while ((orig_node = (struct orig_node*) avl_next(&orig_avl, &orig_ip))) { + while ((orig_node = (struct orig_node*) ((an = avl_next(&orig_avl, &orig_ip)) ? an->key : NULL))) { orig_ip = orig_node->orig; @@ -1612,9 +1616,9 @@ uint32_t orig_ip = 0; struct link_node * ln; - - while ((ln = (struct link_node*) avl_next(&link_avl, &orig_ip))) { + while ((ln = (struct link_node*) ((an = avl_next(&link_avl, &orig_ip)) ? an->key : NULL))) { + orig_ip = ln->orig_addr; /* @@ -1683,7 +1687,7 @@ uint32_t orig_ip = 0; - while ((orig_node = (struct orig_node*) avl_next(&orig_avl, &orig_ip))) { + while ((orig_node = (struct orig_node*) ((an = avl_next(&orig_avl, &orig_ip)) ? an->key : NULL))) { orig_ip = orig_node->orig;

1 0

r1655 - trunk/batman-experimental
by postmaster＠open-mesh.net 17 May '10

17 May '10

Author: axel Date: 2010-05-17 05:10:17 +0200 (Mon, 17 May 2010) New Revision: 1655 Modified: trunk/batman-experimental/metrics.c Log: metrics.c fix: don't paranoia (only warn) due to casual ogm duplications Modified: trunk/batman-experimental/metrics.c =================================================================== --- trunk/batman-experimental/metrics.c 2010-05-04 07:31:55 UTC (rev 1654) +++ trunk/batman-experimental/metrics.c 2010-05-17 03:10:17 UTC (rev 1655) @@ -35,50 +35,7 @@ } -/* -//static -void update_metric( uint8_t probe, SQ_TYPE sq_upd, struct sq_record *sqr, uint8_t ws ) { - uint32_t m_weight = ws/2; - SQ_TYPE offset = sq_upd - sqr->wa_clr_sqn; - uint32_t old_wa_val = sqr->wa_val; - - if ( offset >= ws ) { - - if ( old_wa_val ) { - dbgf_all( DBGT_WARN, "(offset:%d=SQN:%d-clrSQN:%d) > ws:%d probe %d, old_wa_val %d ", - offset, sq_upd, sqr->wa_clr_sqn, ws, probe, sqr->wa_val ); - } - - sqr->wa_unscaled = 0; - - } else { - - SQ_TYPE i; - for ( i=0; i < offset; i++ ) - sqr->wa_unscaled -= ( sqr->wa_unscaled / m_weight ); - - } - - sqr->wa_clr_sqn = sq_upd; - - if ( probe && sqr->wa_set_sqn != sq_upd ) { - - sqr->wa_unscaled += ( (probe * WA_SCALE_FACTOR) / m_weight ); - - sqr->wa_set_sqn = sq_upd; - } - - sqr->wa_val = sqr->wa_unscaled/WA_SCALE_FACTOR; - - - dbgf_ext( DBGT_INFO, "probe %d, SQN %d, old_wa_val %d, new_wa_val %d", probe, sq_upd, old_wa_val, sqr->wa_val ); - -} -*/ - - - void update_lounged_metric(uint8_t probe, uint8_t lounge_size, SQ_TYPE sqn_incm, SQ_TYPE sqn_max, struct sq_record *sqr, uint8_t ws) { SQ_TYPE sq_upd; @@ -111,13 +68,21 @@ if ( probe /* && sqr->wa_set_sqn != sq_upd */ ) { - paranoia( -500197, (sqr->wa_set_sqn == sq_upd) /*check validate_considered_order()*/ ); + // paranoia( -500197, (sqr->wa_set_sqn == sq_upd) /*check validate_considered_order()*/ ); - sqr->wa_unscaled += ( (probe * WA_SCALE_FACTOR) / m_weight ); + if ( sqr->wa_set_sqn != sq_upd ) { + sqr->wa_unscaled += ((probe * WA_SCALE_FACTOR) / m_weight); - sqr->wa_set_sqn = sq_upd; - } + sqr->wa_set_sqn = sq_upd; + } else { + dbg_mute( 20, DBGL_SYS, DBGT_ERR, + "update_lounged_metric() probe %d ls %d sqn_in %d sqn_max %d ws %d", + probe, lounge_size, sqn_incm, sqn_max, ws ); + + } + } + sqr->wa_val = sqr->wa_unscaled/WA_SCALE_FACTOR;

1 0

← Newer
1
2
3
4
5
6
7
8
9
Older →

2024

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

2013

2012

2011

2010

2009

commits May 2010