Author: marek
Date: 2009-10-25 00:13:51 +0000 (Sun, 25 Oct 2009)
New Revision: 1456
Modified:
trunk/batctl/Makefile
trunk/batctl/bisect.c
trunk/batctl/bisect.h
Log:
[batctl] add recursive check for routing loops
Modified: trunk/batctl/Makefile
===================================================================
--- trunk/batctl/Makefile 2009-10-25 00:13:47 UTC (rev 1455)
+++ trunk/batctl/Makefile 2009-10-25 00:13:51 UTC (rev 1456)
@@ -26,7 +26,7 @@
endif
CC = gcc
-CFLAGS += -pedantic -Wall -W -O1 -g3 -std=gnu99
+CFLAGS += -pedantic -Wall -W -g3 -std=gnu99
EXTRA_CFLAGS = -DREVISION_VERSION=$(REVISION_VERSION)
LDFLAGS +=
Modified: trunk/batctl/bisect.c
===================================================================
--- trunk/batctl/bisect.c 2009-10-25 00:13:47 UTC (rev 1455)
+++ trunk/batctl/bisect.c 2009-10-25 00:13:51 UTC (rev 1456)
@@ -87,24 +87,91 @@
}
strncpy(bat_node->name, name, NAME_LEN);
- INIT_LIST_HEAD_FIRST(bat_node->event_list);
+ INIT_LIST_HEAD_FIRST(bat_node->orig_event_list);
INIT_LIST_HEAD_FIRST(bat_node->rt_table_list);
memset(bat_node->loop_magic, 0, sizeof(bat_node->loop_magic));
+ memset(bat_node->loop_magic2, 0, sizeof(bat_node->loop_magic2));
hash_add(node_hash, bat_node);
out:
return bat_node;
}
+static struct orig_event *orig_event_new(struct bat_node *bat_node, struct bat_node *orig_node)
+{
+ struct orig_event *orig_event;
+
+ orig_event = malloc(sizeof(struct orig_event));
+ if (!orig_event) {
+ fprintf(stderr, "Could not allocate memory for orig event structure (out of mem?) - skipping");
+ return NULL;
+ }
+
+ INIT_LIST_HEAD(&orig_event->list);
+ INIT_LIST_HEAD_FIRST(orig_event->event_list);
+ INIT_LIST_HEAD_FIRST(orig_event->rt_hist_list);
+ orig_event->orig_node = orig_node;
+ list_add_tail(&orig_event->list, &bat_node->orig_event_list);
+
+ return orig_event;
+}
+
+static struct orig_event *orig_event_get_by_name(struct bat_node *bat_node, char *orig)
+{
+ struct bat_node *orig_node;
+ struct orig_event *orig_event;
+
+ if (!bat_node)
+ return NULL;
+
+ list_for_each_entry(orig_event, &bat_node->orig_event_list, list) {
+ if (compare_name(orig_event->orig_node->name, orig))
+ return orig_event;
+ }
+
+ orig_node = node_get(orig);
+ if (!orig_node)
+ return NULL;
+
+ return orig_event_new(bat_node, orig_node);
+}
+
+static struct orig_event *orig_event_get_by_ptr(struct bat_node *bat_node, struct bat_node *orig_node)
+{
+ struct orig_event *orig_event;
+
+ if (!bat_node)
+ return NULL;
+
+ list_for_each_entry(orig_event, &bat_node->orig_event_list, list) {
+ if (orig_event->orig_node == orig_node)
+ return orig_event;
+ }
+
+ return orig_event_new(bat_node, orig_node);
+}
+
static void node_free(void *data)
{
+ struct orig_event *orig_event, *orig_event_tmp;
struct seqno_event *seqno_event, *seqno_event_tmp;
struct rt_table *rt_table, *rt_table_tmp;
+ struct rt_hist *rt_hist, *rt_hist_tmp;
struct bat_node *bat_node = (struct bat_node *)data;
- list_for_each_entry_safe(seqno_event, seqno_event_tmp, &bat_node->event_list, list) {
- list_del((struct list_head *)&bat_node->event_list, &seqno_event->list, &bat_node->event_list);
- free(seqno_event);
+ list_for_each_entry_safe(orig_event, orig_event_tmp, &bat_node->orig_event_list, list) {
+ list_for_each_entry_safe(seqno_event, seqno_event_tmp, &orig_event->event_list, list) {
+ list_del((struct list_head *)&orig_event->event_list, &seqno_event->list, &orig_event->event_list);
+ free(seqno_event);
+ }
+
+ list_for_each_entry_safe(rt_hist, rt_hist_tmp, &orig_event->rt_hist_list, list) {
+ list_del((struct list_head *)&orig_event->rt_hist_list, &rt_hist->list, &orig_event->rt_hist_list);
+ free(rt_hist);
+ }
+
+ list_del((struct list_head *)&bat_node->orig_event_list, &orig_event->list, &bat_node->orig_event_list);
+ free(orig_event);
}
list_for_each_entry_safe(rt_table, rt_table_tmp, &bat_node->rt_table_list, list) {
@@ -120,8 +187,10 @@
static int routing_table_new(char *orig, char *next_hop, char *old_next_hop, char rt_flag)
{
struct bat_node *next_hop_node;
+ struct orig_event *orig_event;
struct seqno_event *seqno_event;
struct rt_table *rt_table, *prev_rt_table = NULL;
+ struct rt_hist *rt_hist;
int i, j;
if (!curr_bat_node) {
@@ -148,19 +217,46 @@
if ((rt_flag != RT_FLAG_DELETE) && (!next_hop_node))
goto err;
+ orig_event = orig_event_get_by_name(curr_bat_node, orig);
+ if (!orig_event)
+ goto err;
+
+ if (list_empty(&orig_event->event_list)) {
+ fprintf(stderr, "Routing table change without any preceeding OGM of that originator - skipping");
+ goto err;
+ }
+
+ if (!compare_name(((struct seqno_event *)(orig_event->event_list.prev))->orig->name, orig)) {
+ fprintf(stderr, "Routing table change does not match with last received OGM - skipping");
+ goto err;
+ }
+
rt_table = malloc(sizeof(struct rt_table));
if (!rt_table) {
fprintf(stderr, "Could not allocate memory for routing table (out of mem?) - skipping");
goto err;
}
+ rt_hist = malloc(sizeof(struct rt_hist));
+ if (!rt_hist) {
+ fprintf(stderr, "Could not allocate memory for routing history (out of mem?) - skipping");
+ goto table_free;
+ }
+
INIT_LIST_HEAD(&rt_table->list);
+ rt_table->num_entries = 1;
+ INIT_LIST_HEAD(&rt_hist->list);
+ rt_hist->prev_rt_hist = NULL;
+ rt_hist->next_hop = next_hop_node;
+ rt_hist->flags = rt_flag;
+
+ if (!(list_empty(&orig_event->rt_hist_list)))
+ rt_hist->prev_rt_hist = (struct rt_hist *)(orig_event->rt_hist_list.prev);
+
if (!(list_empty(&curr_bat_node->rt_table_list)))
prev_rt_table = (struct rt_table *)(curr_bat_node->rt_table_list.prev);
- rt_table->num_entries = 1;
-
switch (rt_flag) {
case RT_FLAG_ADD:
if (prev_rt_table)
@@ -193,9 +289,9 @@
if (rt_table->num_entries != prev_rt_table->num_entries) {
fprintf(stderr,
- "Found a delete entry of orig '%s' but no previous existing record - skipping",
+ "Found a delete entry of orig '%s' but no existing record - skipping",
orig);
- goto table_free;
+ goto rt_hist_free;
}
/**
@@ -205,29 +301,29 @@
seqno_event = malloc(sizeof(struct seqno_event));
if (!seqno_event) {
fprintf(stderr, "Could not allocate memory for delete seqno event (out of mem?) - skipping");
- goto table_free;
+ goto rt_hist_free;
}
INIT_LIST_HEAD(&seqno_event->list);
- seqno_event->orig = NULL;
+ seqno_event->orig = node_get(orig);
seqno_event->neigh = NULL;
seqno_event->prev_sender = NULL;
seqno_event->seqno = -1;
seqno_event->tq = -1;
seqno_event->ttl = -1;
- seqno_event->rt_table = NULL;
- list_add_tail(&seqno_event->list, &curr_bat_node->event_list);
+ seqno_event->rt_hist = NULL;
+ list_add_tail(&seqno_event->list, &orig_event->event_list);
}
break;
default:
fprintf(stderr, "Unknown rt_flag received: %i - skipping", rt_flag);
- goto table_free;
+ goto rt_hist_free;
}
rt_table->entries = malloc(sizeof(struct rt_entry) * rt_table->num_entries);
if (!rt_table->entries) {
fprintf(stderr, "Could not allocate memory for routing table entries (out of mem?) - skipping");
- goto table_free;
+ goto rt_hist_free;
}
if (prev_rt_table) {
@@ -246,7 +342,9 @@
*/
j++;
- memcpy((char *)&rt_table->entries[j], (char *)&prev_rt_table->entries[i], sizeof(struct rt_entry));
+ memcpy((char *)&rt_table->entries[j],
+ (char *)&prev_rt_table->entries[i],
+ sizeof(struct rt_entry));
if (compare_name(orig, rt_table->entries[j].orig)) {
if (rt_flag != RT_FLAG_DELETE)
@@ -266,11 +364,17 @@
rt_table->entries[i - 1].flags = rt_flag;
}
+ rt_table->rt_hist = rt_hist;
+ rt_hist->seqno_event = (struct seqno_event *)(orig_event->event_list.prev);
+ rt_hist->seqno_event->rt_hist = rt_hist;
+ rt_hist->rt_table = rt_table;
list_add_tail(&rt_table->list, &curr_bat_node->rt_table_list);
- ((struct seqno_event *)(curr_bat_node->event_list.prev))->rt_table = rt_table;
+ list_add_tail(&rt_hist->list, &orig_event->rt_hist_list);
return 1;
+rt_hist_free:
+ free(rt_hist);
table_free:
free(rt_table);
err:
@@ -280,6 +384,7 @@
static int seqno_event_new(char *iface_addr, char *orig, char *prev_sender, char *neigh, int seqno, int tq, int ttl)
{
struct bat_node *orig_node, *neigh_node, *prev_sender_node;
+ struct orig_event *orig_event;
struct seqno_event *seqno_event;
if (!iface_addr) {
@@ -328,6 +433,10 @@
if (!prev_sender_node)
goto err;
+ orig_event = orig_event_get_by_ptr(curr_bat_node, orig_node);
+ if (!orig_event)
+ goto err;
+
seqno_event = malloc(sizeof(struct seqno_event));
if (!seqno_event) {
fprintf(stderr, "Could not allocate memory for seqno event (out of mem?) - skipping");
@@ -341,8 +450,8 @@
seqno_event->seqno = seqno;
seqno_event->tq = tq;
seqno_event->ttl = ttl;
- seqno_event->rt_table = NULL;
- list_add_tail(&seqno_event->list, &curr_bat_node->event_list);
+ seqno_event->rt_hist = NULL;
+ list_add_tail(&seqno_event->list, &orig_event->event_list);
return 1;
@@ -464,8 +573,8 @@
}
}
-// printf("route (line %i): orig: '%s', neigh: '%s', prev_sender: '%s'\n",
-// line_count, orig, neigh, prev_sender);
+// printf("route (file: %s, line %i): orig: '%s', neigh: '%s', prev_sender: '%s'\n",
+// file_path, line_count, orig, neigh, prev_sender);
if (((rt_flag == RT_FLAG_ADD) && (!neigh)) ||
((rt_flag == RT_FLAG_UPDATE) && (!prev_sender)) ||
@@ -485,102 +594,203 @@
// printf("File '%s' parsed (lines: %i)\n", file_path, line_count);
fclose(fd);
+ curr_bat_node = NULL;
return 1;
}
-static int validate_path(struct bat_node *bat_node, struct seqno_event *seqno_event,
- struct rt_entry *rt_entry, int seqno_count, int read_opt)
+static struct rt_hist *get_rt_hist_by_seqno(struct orig_event *orig_event, int seqno)
{
- struct bat_node *next_hop_node;
- struct seqno_event *seqno_event_tmp;
- struct rt_table *rt_table_tmp;
- struct rt_entry *rt_entry_tmp = rt_entry;
+ struct seqno_event *seqno_event;
+ struct rt_hist *rt_hist = NULL;
+
+ list_for_each_entry(seqno_event, &orig_event->event_list, list) {
+ if (seqno_event->seqno > seqno)
+
+ break;
+ if (seqno_event->rt_hist)
+ rt_hist = seqno_event->rt_hist;
+ }
+
+ return rt_hist;
+}
+
+static struct rt_hist *get_rt_hist_by_node_seqno(struct bat_node *bat_node, struct bat_node *orig_node, int seqno)
+{
+ struct orig_event *orig_event;
+ struct rt_hist *rt_hist;
+
+ orig_event = orig_event_get_by_ptr(bat_node, orig_node);
+ if (!orig_event)
+ return NULL;
+
+ rt_hist = get_rt_hist_by_seqno(orig_event, seqno);
+ return rt_hist;
+}
+
+static int print_rt_path_at_seqno(struct bat_node *src_node, struct bat_node *dst_node,
+ struct bat_node *next_hop, int seqno, int seqno_rand, int read_opt)
+{
+ struct bat_node *next_hop_tmp;
+ struct orig_event *orig_event;
+ struct rt_hist *rt_hist;
char curr_loop_magic[LOOP_MAGIC_LEN];
- int i;
- snprintf(curr_loop_magic, LOOP_MAGIC_LEN, "%s%s%i%i",
- bat_node->name, rt_entry->orig,
- seqno_event->seqno, seqno_count);
+ memset(curr_loop_magic, 0, LOOP_MAGIC_LEN);
+ snprintf(curr_loop_magic, LOOP_MAGIC_LEN, "%s%s%i%i", src_node->name,
+ dst_node->name, seqno, seqno_rand);
- printf("Path towards %s (seqno %i):",
- get_name_by_macstr(rt_entry->orig, read_opt),
- seqno_event->seqno);
+ printf("Path towards %s (seqno %i ",
+ get_name_by_macstr(dst_node->name, read_opt), seqno);
+ printf("via neigh %s):", get_name_by_macstr(next_hop->name, read_opt));
+
+ next_hop_tmp = next_hop;
+
while (1) {
- next_hop_node = rt_entry_tmp->next_hop;
+ printf(" -> %s%s",
+ get_name_by_macstr(next_hop_tmp->name, read_opt),
+ (dst_node == next_hop_tmp ? "." : ""));
- printf(" -> %s",
- get_name_by_macstr(next_hop_node->name, read_opt));
+ /* destination reached */
+ if (dst_node == next_hop_tmp)
+ break;
+ orig_event = orig_event_get_by_ptr(next_hop_tmp, dst_node);
+ if (!orig_event)
+ goto out;
+
/* no more data - path seems[tm] fine */
- if (list_empty(&next_hop_node->event_list))
+ if (list_empty(&orig_event->event_list))
goto out;
/* same here */
- if (list_empty(&next_hop_node->rt_table_list))
+ if (list_empty(&orig_event->rt_hist_list))
continue;
- rt_table_tmp = NULL;
- rt_entry_tmp = NULL;
-
/* we are running in a loop */
- if (memcmp(curr_loop_magic, next_hop_node->loop_magic, LOOP_MAGIC_LEN) == 0) {
+ if (memcmp(curr_loop_magic, next_hop_tmp->loop_magic, LOOP_MAGIC_LEN) == 0) {
printf(" aborted due to loop!");
goto out;
}
- memcpy(next_hop_node->loop_magic, curr_loop_magic, sizeof(next_hop_node->loop_magic));
+ memcpy(next_hop_tmp->loop_magic, curr_loop_magic, sizeof(next_hop_tmp->loop_magic));
- list_for_each_entry(seqno_event_tmp, &next_hop_node->event_list, list) {
- if (seqno_event_tmp->rt_table)
- rt_table_tmp = seqno_event_tmp->rt_table;
+ rt_hist = get_rt_hist_by_seqno(orig_event, seqno);
- if ((seqno_event_tmp->seqno == seqno_event->seqno) &&
- (seqno_event_tmp->orig == seqno_event->orig))
- break;
- }
+ /* no more routing data - what can we do ? */
+ if (!rt_hist)
+ break;
- /* no routing data so far - what can we do ? */
- if (!rt_table_tmp)
- goto out;
+ next_hop_tmp = rt_hist->next_hop;
+ }
- /* search the following next hop */
- for (i = 0; i < rt_table_tmp->num_entries; i++) {
- if (compare_name(rt_table_tmp->entries[i].orig, rt_entry->orig)) {
- rt_entry_tmp = (struct rt_entry *)&rt_table_tmp->entries[i];
- break;
- }
+out:
+ printf("\n");
+ return 1;
+}
+
+static int find_rt_table_change(struct bat_node *src_node, struct bat_node *dst_node,
+ struct bat_node *curr_node, int seqno_min, int seqno_max,
+ int seqno_rand, int read_opt)
+{
+ struct orig_event *orig_event;
+ struct rt_hist *rt_hist, *rt_hist_tmp;
+ char curr_loop_magic[LOOP_MAGIC_LEN];
+ int res;
+
+ /* recursion ends here */
+ if (curr_node == dst_node) {
+ rt_hist = get_rt_hist_by_node_seqno(src_node, dst_node, seqno_max);
+
+ if (rt_hist)
+ print_rt_path_at_seqno(src_node, dst_node, rt_hist->next_hop,
+ seqno_max, seqno_rand, read_opt);
+ return 0;
+ }
+
+ memset(curr_loop_magic, 0, LOOP_MAGIC_LEN);
+ snprintf(curr_loop_magic, LOOP_MAGIC_LEN, "%s%s%i%i",
+ src_node->name, dst_node->name,
+ seqno_min, seqno_rand);
+
+ /* we are running in a loop */
+ if (memcmp(curr_loop_magic, curr_node->loop_magic2, LOOP_MAGIC_LEN) == 0) {
+ rt_hist = get_rt_hist_by_node_seqno(src_node, dst_node, seqno_max);
+
+ if (rt_hist)
+ print_rt_path_at_seqno(src_node, dst_node, rt_hist->next_hop,
+ seqno_max, seqno_rand, read_opt);
+ goto out;
+ }
+
+ memcpy(curr_node->loop_magic2, curr_loop_magic, sizeof(curr_node->loop_magic));
+
+ orig_event = orig_event_get_by_ptr(curr_node, dst_node);
+ if (!orig_event)
+ goto out;
+
+ list_for_each_entry(rt_hist, &orig_event->rt_hist_list, list) {
+ /* special seqno that indicates an originator timeout */
+ if (rt_hist->seqno_event->seqno == -1) {
+ printf("Woot - originator timeout ??\n");
+ continue;
}
- /* no routing entry of orig ?? */
- if (!rt_entry_tmp)
- goto out;
+ if ((seqno_min != -1) && (rt_hist->seqno_event->seqno < seqno_min))
+ continue;
- if (compare_name(rt_entry->orig, rt_entry_tmp->next_hop->name)) {
- printf(" -> %s.",
- get_name_by_macstr(rt_entry_tmp->next_hop->name, read_opt));
- break;
- }
+ if ((seqno_max != -1) && (rt_hist->seqno_event->seqno >= seqno_max))
+ continue;
+
+ /* printf("validate route after change (seqno %i) of next hop: %s\n",
+ rt_hist->seqno_event->seqno,
+ get_name_by_macstr(rt_hist->next_hop->name, read_opt));*/
+
+ res = find_rt_table_change(src_node, dst_node, rt_hist->next_hop,
+ seqno_min, rt_hist->seqno_event->seqno,
+ seqno_rand, read_opt);
+
+ /* find_rt_table_change() did not run into a loop and printed the path */
+ if (res == 0)
+ continue;
+
+ /**
+ * retrieve routing table towards dst at that point and
+ * print the routing path
+ **/
+ rt_hist_tmp = get_rt_hist_by_node_seqno(src_node, dst_node, rt_hist->seqno_event->seqno);
+
+ if (!rt_hist_tmp)
+ continue;
+
+ print_rt_path_at_seqno(src_node, dst_node, rt_hist_tmp->next_hop,
+ rt_hist->seqno_event->seqno, seqno_rand, read_opt);
}
+ rt_hist = get_rt_hist_by_seqno(orig_event, seqno_max - 1);
+
+ if (rt_hist)
+ return find_rt_table_change(src_node, dst_node, rt_hist->next_hop,
+ seqno_min, seqno_max, seqno_rand, read_opt);
+
out:
- printf("\n");
- return 1;
+ return -1;
}
static void loop_detection(char *loop_orig, int seqno_min, int seqno_max, int read_opt)
{
struct bat_node *bat_node;
- struct seqno_event *seqno_event;
+ struct orig_event *orig_event;
struct hash_it_t *hashit = NULL;
- int i, last_seqno = -1, seqno_count = 0;
+ struct rt_hist *rt_hist, *prev_rt_hist;
+ int last_seqno = -1, seqno_count = 0;
char check_orig[NAME_LEN];
printf("\nAnalyzing routing tables ");
/* if no option was given loop_orig is empty */
memset(check_orig, 0, NAME_LEN);
- if (memcmp(loop_orig, check_orig, NAME_LEN))
+ if (!compare_name(loop_orig, check_orig))
printf("of originator: %s ",
get_name_by_macstr(loop_orig, read_opt));
@@ -594,60 +804,89 @@
while (NULL != (hashit = hash_iterate(node_hash, hashit))) {
bat_node = hashit->bucket->data;
- if (memcmp(loop_orig, check_orig, NAME_LEN) &&
- memcmp(loop_orig, bat_node->name, NAME_LEN) != 0)
+ if (!compare_name(loop_orig, check_orig) &&
+ !compare_name(loop_orig, bat_node->name))
continue;
- /* we might have no log file from this node */
- if (list_empty(&bat_node->event_list)) {
- fprintf(stderr, "\nNo seqno data from node '%s' - skipping\n",
- get_name_by_macstr(bat_node->name, read_opt));
- continue;
- }
-
- /* or routing tables */
- if (list_empty(&bat_node->rt_table_list)) {
- fprintf(stderr, "\nNo routing tables from node '%s' - skipping\n",
- get_name_by_macstr(bat_node->name, read_opt));
- continue;
- }
-
printf("\nChecking host: %s\n",
get_name_by_macstr(bat_node->name, read_opt));
- list_for_each_entry(seqno_event, &bat_node->event_list, list) {
- /**
- * this received packet did not trigger a routing
- * table change and is considered harmless
- */
- if (!seqno_event->rt_table)
+ list_for_each_entry(orig_event, &bat_node->orig_event_list, list) {
+ if (bat_node == orig_event->orig_node)
continue;
- if ((seqno_min != -1) && (seqno_event->seqno < seqno_min))
+ /* we might have no log file from this node */
+ if (list_empty(&orig_event->event_list)) {
+ fprintf(stderr, "No seqno data of originator '%s' - skipping\n",
+ get_name_by_macstr(orig_event->orig_node->name, read_opt));
continue;
+ }
- if ((seqno_max != -1) && (seqno_event->seqno > seqno_max))
+ /* or routing tables */
+ if (list_empty(&orig_event->rt_hist_list)) {
+ fprintf(stderr, "No routing history of originator '%s' - skipping\n",
+ get_name_by_macstr(orig_event->orig_node->name, read_opt));
continue;
+ }
- /* special seqno that indicates an originator timeout */
- if (seqno_event->seqno == -1)
- continue;
+ list_for_each_entry(rt_hist, &orig_event->rt_hist_list, list) {
+ /* special seqno that indicates an originator timeout */
+ if (rt_hist->seqno_event->seqno == -1)
+ continue;
- /**
- * sometime we change the routing table more than once
- * with the same seqno
- */
- if (last_seqno == seqno_event->seqno)
- seqno_count++;
- else
- seqno_count = 0;
+ if ((seqno_min != -1) && (rt_hist->seqno_event->seqno < seqno_min))
+ continue;
- last_seqno = seqno_event->seqno;
+ if ((seqno_max != -1) && (rt_hist->seqno_event->seqno > seqno_max))
+ continue;
- for (i = 0; i < seqno_event->rt_table->num_entries; i++) {
- validate_path(bat_node, seqno_event,
- (struct rt_entry *)&seqno_event->rt_table->entries[i],
- seqno_count, read_opt);
+ /**
+ * sometime we change the routing table more than once
+ * with the same seqno
+ */
+ if (last_seqno == rt_hist->seqno_event->seqno)
+ seqno_count++;
+ else
+ seqno_count = 0;
+
+ last_seqno = rt_hist->seqno_event->seqno;
+
+ if (rt_hist->flags == RT_FLAG_DELETE) {
+ printf("Path towards %s deleted (originator timeout)\n",
+ get_name_by_macstr(rt_hist->seqno_event->orig->name, read_opt));
+ continue;
+ }
+
+ prev_rt_hist = rt_hist->prev_rt_hist;
+
+ if ((prev_rt_hist) &&
+ (rt_hist->seqno_event->seqno != prev_rt_hist->seqno_event->seqno)) {
+ if (rt_hist->seqno_event->seqno < prev_rt_hist->seqno_event->seqno) {
+ fprintf(stderr,
+ "Smaller seqno (%i) than previously received seqno (%i) of orig %s triggered routing table change - skipping recursive check\n",
+ rt_hist->seqno_event->seqno, prev_rt_hist->seqno_event->seqno,
+ get_name_by_macstr(rt_hist->seqno_event->orig->name, read_opt));
+ goto validate_path;
+ }
+
+ /*printf("\n=> checking orig %s in seqno range of: %i - %i ",
+ get_name_by_macstr(rt_hist->seqno_event->orig->name, read_opt),
+ prev_rt_hist->seqno_event->seqno + 1,
+ rt_hist->seqno_event->seqno);
+
+ printf("(prev nexthop: %s)\n",
+ get_name_by_macstr(prev_rt_hist->next_hop->name, read_opt));*/
+
+ find_rt_table_change(bat_node, rt_hist->seqno_event->orig, prev_rt_hist->next_hop,
+ prev_rt_hist->seqno_event->seqno + 1, rt_hist->seqno_event->seqno,
+ seqno_count, read_opt);
+
+ continue;
+ }
+
+validate_path:
+ print_rt_path_at_seqno(bat_node, rt_hist->seqno_event->orig, rt_hist->next_hop,
+ rt_hist->seqno_event->seqno, seqno_count, read_opt);
}
}
}
@@ -677,9 +916,9 @@
for (i = 0; i < seqno_trace_neigh->num_neighbors; i++) {
snprintf(new_head, sizeof(new_head), "%s%s",
- (strlen(head) > 1 ? head : num_sisters == 0 ? " " : head),
- (strlen(head) == 1 ? " " :
- num_sisters == 0 ? " " : "| "));
+ (strlen(head) > 1 ? head : num_sisters == 0 ? " " : head),
+ (strlen(head) == 1 ? " " :
+ num_sisters == 0 ? " " : "| "));
seqno_trace_print_neigh(seqno_trace_neigh->seqno_trace_neigh[i], seqno_trace_neigh->seqno_event,
seqno_trace_neigh->num_neighbors - i - 1, new_head, read_opt);
@@ -941,6 +1180,7 @@
static void trace_seqnos(char *trace_orig, int seqno_min, int seqno_max, int read_opt)
{
struct bat_node *bat_node;
+ struct orig_event *orig_event;
struct seqno_event *seqno_event;
struct hash_it_t *hashit = NULL;
struct list_head_first trace_list;
@@ -952,28 +1192,31 @@
while (NULL != (hashit = hash_iterate(node_hash, hashit))) {
bat_node = hashit->bucket->data;
- /* we might have no log file from this node */
- if (list_empty(&bat_node->event_list))
- continue;
+ list_for_each_entry(orig_event, &bat_node->orig_event_list, list) {
- list_for_each_entry(seqno_event, &bat_node->event_list, list) {
- /* special seqno that indicates an originator timeout */
- if (seqno_event->seqno == -1)
+ /* we might have no log file from this node */
+ if (list_empty(&orig_event->event_list))
continue;
- if (!compare_name(trace_orig, seqno_event->orig->name))
- continue;
+ list_for_each_entry(seqno_event, &orig_event->event_list, list) {
+ /* special seqno that indicates an originator timeout */
+ if (seqno_event->seqno == -1)
+ continue;
- if ((seqno_min != -1) && (seqno_event->seqno < seqno_min))
- continue;
+ if (!compare_name(trace_orig, seqno_event->orig->name))
+ continue;
- if ((seqno_max != -1) && (seqno_event->seqno > seqno_max))
- continue;
+ if ((seqno_min != -1) && (seqno_event->seqno < seqno_min))
+ continue;
- res = seqno_trace_add(&trace_list, bat_node, seqno_event);
+ if ((seqno_max != -1) && (seqno_event->seqno > seqno_max))
+ continue;
- if (res < 1)
- goto out;
+ res = seqno_trace_add(&trace_list, bat_node, seqno_event);
+
+ if (res < 1)
+ goto out;
+ }
}
}
@@ -991,6 +1234,7 @@
static void print_rt_tables(char *rt_orig, int seqno_min, int seqno_max, int read_opt)
{
struct bat_node *bat_node;
+ struct rt_table *rt_table;
struct seqno_event *seqno_event;
int i;
@@ -1009,16 +1253,11 @@
goto out;
/* we might have no log file from this node */
- if (list_empty(&bat_node->event_list))
- goto out;
-
- /* or routing tables */
if (list_empty(&bat_node->rt_table_list))
goto out;
- list_for_each_entry(seqno_event, &bat_node->event_list, list) {
- if (!seqno_event->rt_table)
- continue;
+ list_for_each_entry(rt_table, &bat_node->rt_table_list, list) {
+ seqno_event = rt_table->rt_hist->seqno_event;
if ((seqno_min != -1) && (seqno_event->seqno < seqno_min))
continue;
@@ -1026,7 +1265,7 @@
if ((seqno_max != -1) && (seqno_event->seqno > seqno_max))
continue;
- if (seqno_event->orig) {
+ if (seqno_event->seqno > -1) {
printf("rt change triggered by OGM from: %s (tq: %i, ttl: %i, seqno %i",
get_name_by_macstr(seqno_event->orig->name, read_opt),
seqno_event->tq, seqno_event->ttl, seqno_event->seqno);
@@ -1038,14 +1277,14 @@
printf("rt change triggered by originator timeout: \n");
}
- for (i = 0; i < seqno_event->rt_table->num_entries; i++) {
+ for (i = 0; i < rt_table->num_entries; i++) {
printf("%s %s via next hop",
- (seqno_event->rt_table->entries[i].flags ? " *" : " "),
- get_name_by_macstr(seqno_event->rt_table->entries[i].orig, read_opt));
+ (rt_table->entries[i].flags ? " *" : " "),
+ get_name_by_macstr(rt_table->entries[i].orig, read_opt));
printf(" %s",
- get_name_by_macstr(seqno_event->rt_table->entries[i].next_hop->name, read_opt));
+ get_name_by_macstr(rt_table->entries[i].next_hop->name, read_opt));
- switch (seqno_event->rt_table->entries[i].flags) {
+ switch (rt_table->entries[i].flags) {
case RT_FLAG_ADD:
printf(" (route added)\n");
break;
Modified: trunk/batctl/bisect.h
===================================================================
--- trunk/batctl/bisect.h 2009-10-25 00:13:47 UTC (rev 1455)
+++ trunk/batctl/bisect.h 2009-10-25 00:13:51 UTC (rev 1456)
@@ -29,19 +29,39 @@
int bisect(int argc, char **argv);
+
+
struct bat_node {
char name[NAME_LEN];
- struct list_head_first event_list;
+ struct list_head_first orig_event_list;
struct list_head_first rt_table_list;
char loop_magic[LOOP_MAGIC_LEN];
+ char loop_magic2[LOOP_MAGIC_LEN];
};
+struct orig_event {
+ struct list_head list;
+ struct bat_node *orig_node;
+ struct list_head_first event_list;
+ struct list_head_first rt_hist_list;
+};
+
struct rt_table {
struct list_head list;
int num_entries;
struct rt_entry *entries;
+ struct rt_hist *rt_hist;
};
+struct rt_hist {
+ struct list_head list;
+ struct rt_table *rt_table;
+ struct rt_hist *prev_rt_hist;
+ struct seqno_event *seqno_event;
+ struct bat_node *next_hop;
+ char flags;
+};
+
struct rt_entry {
char orig[NAME_LEN];
struct bat_node *next_hop;
@@ -56,7 +76,7 @@
int seqno;
int tq;
int ttl;
- struct rt_table *rt_table;
+ struct rt_hist *rt_hist;
};
struct seqno_trace_neigh {
