Signed-off-by: Marek Lindner lindner_marek@yahoo.de --- Makefile | 2 +- README | 34 +- bisect.c | 1596 ---------------------------------------------------------- bisect.h | 97 ---- bisect_iv.c | 1596 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ bisect_iv.h | 97 ++++ main.c | 10 +- man/batctl.8 | 14 +- 8 files changed, 1722 insertions(+), 1724 deletions(-) delete mode 100644 bisect.c delete mode 100644 bisect.h create mode 100644 bisect_iv.c create mode 100644 bisect_iv.h

diff --git a/Makefile b/Makefile index 72cecde..efe57c1 100755 --- a/Makefile +++ b/Makefile @@ -20,7 +20,7 @@

# batctl build BINARY_NAME = batctl -OBJ = main.o bat-hosts.o functions.o sys.o debug.o ping.o traceroute.o tcpdump.o list-batman.o hash.o vis.o debugfs.o bisect.o ioctl.o +OBJ = main.o bat-hosts.o functions.o sys.o debug.o ping.o traceroute.o tcpdump.o list-batman.o hash.o vis.o debugfs.o bisect_iv.o ioctl.o MANPAGE = man/batctl.8

# batctl flags and options diff --git a/README b/README index a2b0266..03d36c4 100644 --- a/README +++ b/README @@ -167,22 +167,20 @@ $ batctl tcpdump mesh0 01:51:43.600999 BAT wyoming: OGM via neigh kansas, seqno 6722, tq 245, ttl 49, v 9, flags [.D.], length 28 01:51:44.381064 BAT kansas: OGM via neigh kansas, seqno 6720, tq 255, ttl 50, v 9, flags [..I], length 28

-batctl bisect -============= - -Analyzes the logfiles to build a small internal database of all sent sequence -numbers and routing table changes. This database can be used to search for -routing loops (default action), to trace OGMs of a host (use "-t" to -specify the mac address or bat-host name) throughout the network or to -display routing tables of the nodes (use "-r" to specify the mac address or -bat-host name). You can name a specific sequence number or a range using the -"-s" option to limit the output's range. Furthermore you can filter the -output by specifying an originator (use "-o" to specify the mac address or -bat-host name) to only see data connected to this originator. If "-n" was -given batctl will not replace the mac addresses with bat-host names in the -output. - -Usage: batctl bisect [parameters] <file1> <file2> .. <fileN> +batctl bisect_iv +================ + +Analyzes the B.A.T.M.A.N. IV logfiles to build a small internal database of all sent sequence +numbers and routing table changes. This database can be used to search for routing loops +(default action), to trace OGMs of a host (use "-t" to specify the mac address or +bat-host name) throughout the network or to display routing tables of the nodes (use "-r" to +specify the mac address or bat-host name). You can name a specific sequence number or a range +using the "-s" option to limit the output's range. Furthermore you can filter the output by +specifying an originator (use "-o" to specify the mac address or bat-host name) to only see +data connected to this originator. If "-n" was given batctl will not replace the mac +addresses with bat-host names in the output. + +Usage: batctl bisect_iv [parameters] <file1> <file2> .. <fileN> parameters: -h print this help -l run a loop detection of given mac address or bat-host (default) @@ -193,7 +191,7 @@ parameters:

Examples:

-$ batctl bisect log/* -l uml3 +$ batctl bisect_iv log/* -l uml3 Analyzing routing tables of originator: uml3 [all sequence numbers]

Checking host: uml3 @@ -211,7 +209,7 @@ Path towards uml9 (seqno 12 via neigh uml4): -> uml4 -> uml5 -> uml6 -> uml7 -> Path towards uml9 (seqno 21 via neigh uml5): -> uml5 -> uml6 -> uml7 -> uml8 -> uml9. Path towards uml9 (seqno 22 via neigh uml4): -> uml4 -> uml5 -> uml6 -> uml7 -> uml8 -> uml9.

-$ ./batctl bisect -t uml3 log/* +$ ./batctl bisect_iv -t uml3 log/* Sequence number flow of originator: uml3 [all sequence numbers] [...] +=> uml3 (seqno 19) diff --git a/bisect.c b/bisect.c deleted file mode 100644 index 8bc9c65..0000000 --- a/bisect.c +++ /dev/null @@ -1,1596 +0,0 @@ -/* - * Copyright (C) 2009-2012 B.A.T.M.A.N. contributors: - * - * Marek Lindner lindner_marek@yahoo.de - * - * This program is free software; you can redistribute it and/or - * modify it under the terms of version 2 of the GNU General Public - * License as published by the Free Software Foundation. - * - * This program is distributed in the hope that it will be useful, but - * WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU - * General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software - * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA - * 02110-1301, USA - * - */ - -#include <stdio.h> -#include <stdlib.h> -#include <stdint.h> -#include <unistd.h> -#include <string.h> -#include <errno.h> - -#include "main.h" -#include "bisect.h" -#include "bat-hosts.h" -#include "hash.h" -#include "functions.h" - -static struct hashtable_t *node_hash = NULL; -static struct bat_node *curr_bat_node = NULL; - -static void bisect_usage(void) -{ - printf("Usage: batctl bisect [parameters] <file1> <file2> .. <fileN>\n"); - printf("parameters:\n"); - printf(" \t -h print this help\n"); - printf(" \t -l run a loop detection of given mac address or bat-host (default)\n"); - printf(" \t -n don't convert addresses to bat-host names\n"); - printf(" \t -o only display orig events that affect given mac address or bat-host\n"); - printf(" \t -r print routing tables of given mac address or bat-host\n"); - printf(" \t -s seqno range to limit the output\n"); - printf(" \t -t trace seqnos of given mac address or bat-host\n"); -} - -static int compare_name(void *data1, void *data2) -{ - return (memcmp(data1, data2, NAME_LEN) == 0 ? 1 : 0); -} - -static int choose_name(void *data, int32_t size) -{ - unsigned char *key= data; - uint32_t hash = 0, m_size = NAME_LEN - 1; - size_t i; - - for (i = 0; i < m_size; i++) { - hash += key[i]; - hash += (hash << 10); - hash ^= (hash >> 6); - } - - hash += (hash << 3); - hash ^= (hash >> 11); - hash += (hash << 15); - - return (hash % size); -} - -static struct bat_node *node_get(char *name) -{ - struct bat_node *bat_node; - - if (!name) - return NULL; - - bat_node = (struct bat_node *)hash_find(node_hash, name); - if (bat_node) - goto out; - - bat_node = malloc(sizeof(struct bat_node)); - if (!bat_node) { - fprintf(stderr, "Could not allocate memory for data structure (out of mem?) - skipping"); - return NULL; - } - - strncpy(bat_node->name, name, NAME_LEN); - 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(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) { - list_del((struct list_head *)&bat_node->rt_table_list, &rt_table->list, &bat_node->rt_table_list); - - free(rt_table->entries); - free(rt_table); - } - - free(bat_node); -} - -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 = -1; - - if (!curr_bat_node) { - fprintf(stderr, "Routing table change without preceding OGM - skipping"); - goto err; - } - - if (!orig) { - fprintf(stderr, "Invalid originator found - skipping"); - goto err; - } - - if ((rt_flag != RT_FLAG_DELETE) && (!next_hop)) { - fprintf(stderr, "Invalid next hop found - skipping"); - goto err; - } - - if ((rt_flag == RT_FLAG_UPDATE) && (!old_next_hop)) { - fprintf(stderr, "Invalid old next hop found - skipping"); - goto err; - } - - next_hop_node = node_get(next_hop); - 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 preceding 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; - memset(rt_hist->loop_magic, 0, sizeof(rt_hist->loop_magic)); - - 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); - - switch (rt_flag) { - case RT_FLAG_ADD: - if (prev_rt_table) - rt_table->num_entries = prev_rt_table->num_entries + 1; - break; - case RT_FLAG_UPDATE: - if (prev_rt_table) { - rt_table->num_entries = prev_rt_table->num_entries + 1; - - /* if we had that route already we just change the entry */ - for (i = 0; i < prev_rt_table->num_entries; i++) { - if (compare_name(orig, prev_rt_table->entries[i].orig)) { - rt_table->num_entries = prev_rt_table->num_entries; - break; - } - } - } - break; - case RT_FLAG_DELETE: - if (prev_rt_table) { - rt_table->num_entries = prev_rt_table->num_entries + 1; - - /* if we had that route already we just change the entry */ - for (i = 0; i < prev_rt_table->num_entries; i++) { - if (compare_name(orig, prev_rt_table->entries[i].orig)) { - rt_table->num_entries = prev_rt_table->num_entries; - break; - } - } - - if (rt_table->num_entries != prev_rt_table->num_entries) { - fprintf(stderr, - "Found a delete entry of orig '%s' but no existing record - skipping", - orig); - goto rt_hist_free; - } - - /** - * we need to create a special seqno event as a timer instead - * of an OGM triggered that event - */ - 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 rt_hist_free; - } - - INIT_LIST_HEAD(&seqno_event->list); - 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_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 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 rt_hist_free; - } - - if (prev_rt_table) { - for (i = 0; i < prev_rt_table->num_entries; i++) { - /* if we have a previously deleted item don't copy it over */ - if (prev_rt_table->entries[i].flags == RT_FLAG_DELETE) { - rt_table->num_entries--; - continue; - } - - /** - * if we delete one item the entries are not in sync anymore, - * therefore we need to counters: one for the old and one for - * the new routing table - */ - j++; - - 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) - rt_table->entries[j].next_hop = next_hop_node; - rt_table->entries[j].flags = rt_flag; - continue; - } - - rt_table->entries[j].flags = 0; - } - } - - if ((rt_table->num_entries == 1) || (rt_table->num_entries != j + 1)) { - i = rt_table->num_entries; - strncpy(rt_table->entries[i - 1].orig, orig, NAME_LEN); - rt_table->entries[i - 1].next_hop = next_hop_node; - 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); - 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: - return 0; -} - -static int seqno_event_new(char *iface_addr, char *orig, char *prev_sender, char *neigh, long long 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) { - fprintf(stderr, "Invalid interface address found - skipping"); - goto err; - } - - if (!orig) { - fprintf(stderr, "Invalid originator found - skipping"); - goto err; - } - - if (!neigh) { - fprintf(stderr, "Invalid neighbor found - skipping"); - goto err; - } - - if ((seqno < 0) || (seqno > UINT32_MAX)) { - fprintf(stderr, "Invalid sequence number found (%lli) - skipping", seqno); - goto err; - } - - if ((tq < 0) || (tq > UINT8_MAX)) { - fprintf(stderr, "Invalid tq value found (%i) - skipping", tq); - goto err; - } - - if ((ttl < 0) || (ttl > UINT8_MAX)) { - fprintf(stderr, "Invalid ttl value found (%i) - skipping", ttl); - goto err; - } - - curr_bat_node = node_get(iface_addr); - if (!curr_bat_node) - goto err; - - orig_node = node_get(orig); - if (!orig_node) - goto err; - - neigh_node = node_get(neigh); - if (!neigh_node) - goto err; - - prev_sender_node = node_get(prev_sender); - 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"); - goto err; - } - - INIT_LIST_HEAD(&seqno_event->list); - seqno_event->orig = orig_node; - seqno_event->neigh = neigh_node; - seqno_event->prev_sender = prev_sender_node; - seqno_event->seqno = seqno; - seqno_event->tq = tq; - seqno_event->ttl = ttl; - seqno_event->rt_hist = NULL; - list_add_tail(&seqno_event->list, &orig_event->event_list); - - return 1; - -err: - return 0; -} - -static int parse_log_file(char *file_path) -{ - FILE *fd; - char line_buff[MAX_LINE], *start_ptr, *start_ptr_safe, *tok_ptr; - char *neigh, *iface_addr, *orig, *prev_sender, rt_flag; - int line_count = 0, tq, ttl, i, res, max; - long long seqno; - - fd = fopen(file_path, "r"); - - if (!fd) { - fprintf(stderr, "Error - could not open file '%s': %s\n", file_path, strerror(errno)); - return 0; - } - - while (fgets(line_buff, sizeof(line_buff), fd) != NULL) { - /* ignore the timestamp at the beginning of each line */ - start_ptr = line_buff + 13; - line_count++; - - if (strstr(start_ptr, "Received BATMAN packet via NB")) { - strtok_r(start_ptr, " ", &start_ptr_safe); - neigh = iface_addr = orig = prev_sender = NULL; - seqno = tq = ttl = -1; - - for (i = 0; i < 21; i++) { - tok_ptr = strtok_r(NULL, " ", &start_ptr_safe); - if (!tok_ptr) - break; - - switch (i) { - case 4: - neigh = tok_ptr; - neigh[strlen(neigh) - 1] = 0; - break; - case 7: - iface_addr = tok_ptr + 1; - iface_addr[strlen(iface_addr) - 1] = 0; - break; - case 10: - orig = tok_ptr; - orig[strlen(orig) - 1] = 0; - break; - case 14: - prev_sender = tok_ptr; - prev_sender[strlen(prev_sender) - 1] = 0; - break; - case 16: - seqno = strtoll(tok_ptr, NULL, 10); - break; - case 18: - tq = strtol(tok_ptr, NULL, 10); - break; - case 20: - ttl = strtol(tok_ptr, NULL, 10); - break; - } - } - - if (ttl == -1) { - fprintf(stderr, "Broken 'received packet' line found - skipping [file: %s, line: %i]\n", file_path, line_count); - continue; - } - -// fprintf(stderr, "received packet (line %i): neigh: '%s', iface_addr: '%s', orig: '%s', prev_sender: '%s', seqno: %i, tq: %i, ttl: %i\n", line_count, neigh, iface_addr, orig, prev_sender, seqno, tq, ttl); - - res = seqno_event_new(iface_addr, orig, prev_sender, neigh, seqno, tq, ttl); - if (res < 1) - fprintf(stderr, " [file: %s, line: %i]\n", file_path, line_count); - - } else if (strstr(start_ptr, "Adding route towards") || - strstr(start_ptr, "Changing route towards") || - strstr(start_ptr, "Deleting route towards")) { - - rt_flag = RT_FLAG_UPDATE; - max = 12; - - if (strstr(start_ptr, "Adding route towards")) { - rt_flag = RT_FLAG_ADD; - max = 5; - } else if (strstr(start_ptr, "Deleting route towards")) { - rt_flag = RT_FLAG_DELETE; - max = 3; - } - - strtok_r(start_ptr, " ", &start_ptr_safe); - orig = neigh = prev_sender = NULL; - - for (i = 0; i < max; i++) { - tok_ptr = strtok_r(NULL, " ", &start_ptr_safe); - if (!tok_ptr) - break; - - switch (i) { - case 2: - orig = tok_ptr; - if (rt_flag == RT_FLAG_DELETE) - orig[strlen(orig) - 1] = 0; - break; - case 4: - if (rt_flag == RT_FLAG_ADD) { - neigh = tok_ptr; - neigh[strlen(neigh) - 2] = 0; - } - break; - case 5: - neigh = tok_ptr; - break; - case 9: - prev_sender = tok_ptr; - prev_sender[strlen(prev_sender) - 2] = 0; - break; - } - } - -// 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)) || - ((rt_flag == RT_FLAG_DELETE) && (!orig))) { - fprintf(stderr, "Broken '%s route' line found - skipping [file: %s, line: %i]\n", - (rt_flag == RT_FLAG_UPDATE ? "changing" : - (rt_flag == RT_FLAG_ADD ? "adding" : "deleting")), - file_path, line_count); - continue; - } - - res = routing_table_new(orig, neigh, prev_sender, rt_flag); - if (res < 1) - fprintf(stderr, " [file: %s, line: %i]\n", file_path, line_count); - } - } - -// printf("File '%s' parsed (lines: %i)\n", file_path, line_count); - fclose(fd); - curr_bat_node = NULL; - return 1; -} - -static struct rt_hist *get_rt_hist_by_seqno(struct orig_event *orig_event, long long seqno) -{ - 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, long long 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, long long seqno, long long 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]; - - memset(curr_loop_magic, 0, LOOP_MAGIC_LEN); - snprintf(curr_loop_magic, LOOP_MAGIC_LEN, "%s%s%lli%lli", src_node->name, - dst_node->name, seqno, seqno_rand); - - printf("Path towards %s (seqno %lli ", - 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) { - printf(" -> %s%s", - get_name_by_macstr(next_hop_tmp->name, read_opt), - (dst_node == next_hop_tmp ? "." : "")); - - /* 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(&orig_event->event_list)) - goto out; - - /* same here */ - if (list_empty(&orig_event->rt_hist_list)) - goto out; - - /* we are running in a loop */ - if (memcmp(curr_loop_magic, next_hop_tmp->loop_magic, LOOP_MAGIC_LEN) == 0) { - printf(" aborted due to loop!"); - goto out; - } - - memcpy(next_hop_tmp->loop_magic, curr_loop_magic, sizeof(next_hop_tmp->loop_magic)); - - rt_hist = get_rt_hist_by_seqno(orig_event, seqno); - - /* no more routing data - what can we do ? */ - if (!rt_hist) - break; - - next_hop_tmp = rt_hist->next_hop; - } - -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, long long seqno_min, long long seqno_max, - long long 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], loop_check = 0; - int res; - long long seqno_tmp, seqno_min_tmp = seqno_min; - - /* printf("%i: curr_node: %s ", bla, - get_name_by_macstr(curr_node->name, read_opt)); - - printf("dst_node: %s [%i - %i]\n", - get_name_by_macstr(dst_node->name, read_opt), seqno_min, seqno_max); */ - - /* 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%lli%lli", - src_node->name, dst_node->name, - seqno_min_tmp, seqno_rand); - - 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; - } - - if ((seqno_min_tmp != -1) && (rt_hist->seqno_event->seqno < seqno_min_tmp)) - continue; - - if ((seqno_max != -1) && (rt_hist->seqno_event->seqno >= seqno_max)) - continue; - - /* we are running in a loop */ - if (memcmp(curr_loop_magic, rt_hist->loop_magic, LOOP_MAGIC_LEN) == 0) { - rt_hist_tmp = get_rt_hist_by_node_seqno(src_node, dst_node, - rt_hist->seqno_event->seqno); - - if (rt_hist_tmp) - print_rt_path_at_seqno(src_node, dst_node, rt_hist_tmp->next_hop, - rt_hist->seqno_event->seqno, seqno_rand, read_opt); - goto loop; - } - - memcpy(rt_hist->loop_magic, curr_loop_magic, sizeof(rt_hist->loop_magic)); - loop_check = 1; - - /* printf("validate route after change (seqno %i) at node: %s\n", - rt_hist->seqno_event->seqno, - get_name_by_macstr(curr_node->name, read_opt)); */ - - res = find_rt_table_change(src_node, dst_node, rt_hist->next_hop, - seqno_min_tmp, rt_hist->seqno_event->seqno, - seqno_rand, read_opt); - - seqno_min_tmp = rt_hist->seqno_event->seqno + 1; - - /* 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); - } - - /** - * if we have no routing table changes within the seqno range - * the loop detection above won't be triggered - **/ - if (!loop_check) { - if (memcmp(curr_loop_magic, curr_node->loop_magic2, LOOP_MAGIC_LEN) == 0) { - rt_hist_tmp = get_rt_hist_by_node_seqno(src_node, dst_node, seqno_min); - - if (rt_hist_tmp) - print_rt_path_at_seqno(src_node, dst_node, rt_hist_tmp->next_hop, - seqno_min, seqno_rand, read_opt); - - /* no need to print the path twice */ - if (seqno_min == seqno_max) - goto out; - else - goto loop; - } - - memcpy(curr_node->loop_magic2, curr_loop_magic, sizeof(curr_node->loop_magic2)); - } - - seqno_tmp = seqno_max - 1; - if (seqno_min == seqno_max) - seqno_tmp = seqno_max; - - rt_hist = get_rt_hist_by_seqno(orig_event, seqno_tmp); - - if (rt_hist) - return find_rt_table_change(src_node, dst_node, rt_hist->next_hop, - seqno_min_tmp, seqno_max, seqno_rand, read_opt); - -out: - return -1; -loop: - return -2; -} - -static void loop_detection(char *loop_orig, long long seqno_min, long long seqno_max, char *filter_orig, int read_opt) -{ - struct bat_node *bat_node; - struct orig_event *orig_event; - struct hash_it_t *hashit = NULL; - struct rt_hist *rt_hist, *prev_rt_hist; - long long last_seqno = -1, seqno_count = 0; - int res; - 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 (!compare_name(loop_orig, check_orig)) - printf("of originator: %s ", - get_name_by_macstr(loop_orig, read_opt)); - - if ((seqno_min == -1) && (seqno_max == -1)) - printf("[all sequence numbers]"); - else if (seqno_min == seqno_max) - printf("[sequence number: %lli]", seqno_min); - else - printf("[sequence number range: %lli-%lli]", seqno_min, seqno_max); - - if (!compare_name(filter_orig, check_orig)) - printf(" [filter originator: %s]", - get_name_by_macstr(filter_orig, read_opt)); - - printf("\n"); - - while (NULL != (hashit = hash_iterate(node_hash, hashit))) { - bat_node = hashit->bucket->data; - - if (!compare_name(loop_orig, check_orig) && - !compare_name(loop_orig, bat_node->name)) - continue; - - printf("\nChecking host: %s\n", - get_name_by_macstr(bat_node->name, read_opt)); - - list_for_each_entry(orig_event, &bat_node->orig_event_list, list) { - if (bat_node == orig_event->orig_node) - continue; - - if (!compare_name(filter_orig, check_orig) && - !compare_name(filter_orig, orig_event->orig_node->name)) - continue; - - /* 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; - } - - /* 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; - } - - 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; - - if ((seqno_min != -1) && (rt_hist->seqno_event->seqno < seqno_min)) - continue; - - if ((seqno_max != -1) && (rt_hist->seqno_event->seqno > seqno_max)) - continue; - - /** - * 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 (%lli) than previously received seqno (%lli) 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; - } - - if (rt_hist->seqno_event->seqno == prev_rt_hist->seqno_event->seqno + 1) - 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)); */ - - res = 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); - - if (res != -2) - 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); - } - } - } -} - -static void seqno_trace_print_neigh(struct seqno_trace_neigh *seqno_trace_neigh, - struct seqno_event *seqno_event_parent, - int num_sisters, char *head, int read_opt) -{ - char new_head[MAX_LINE]; - int i; - - printf("%s%s- %s [tq: %i, ttl: %i", head, - (strlen(head) == 1 ? "" : num_sisters == 0 ? "\" : "|"), - get_name_by_macstr(seqno_trace_neigh->bat_node->name, read_opt), - seqno_trace_neigh->seqno_event->tq, - seqno_trace_neigh->seqno_event->ttl); - - printf(", neigh: %s", get_name_by_macstr(seqno_trace_neigh->seqno_event->neigh->name, read_opt)); - printf(", prev_sender: %s]", get_name_by_macstr(seqno_trace_neigh->seqno_event->prev_sender->name, read_opt)); - - if ((seqno_event_parent) && - (seqno_trace_neigh->seqno_event->tq > seqno_event_parent->tq)) - printf(" TQ UP!\n"); - else - printf("\n"); - - 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 ? " " : "| ")); - - 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); - } -} - -static void seqno_trace_print(struct list_head_first *trace_list, char *trace_orig, - long long seqno_min, long long seqno_max, char *filter_orig, int read_opt) -{ - struct seqno_trace *seqno_trace; - char head[MAX_LINE], check_orig[NAME_LEN]; - int i; - - /* if no option was given filter_orig is empty */ - memset(check_orig, 0, NAME_LEN); - - printf("Sequence number flow of originator: %s ", - get_name_by_macstr(trace_orig, read_opt)); - - if ((seqno_min == -1) && (seqno_max == -1)) - printf("[all sequence numbers]"); - else if (seqno_min == seqno_max) - printf("[sequence number: %lli]", seqno_min); - else - printf("[sequence number range: %lli-%lli]", seqno_min, seqno_max); - - if (!compare_name(filter_orig, check_orig)) - printf(" [filter originator: %s]", - get_name_by_macstr(filter_orig, read_opt)); - - printf("\n"); - - list_for_each_entry(seqno_trace, trace_list, list) { - if (!seqno_trace->print) - continue; - - printf("+=> %s (seqno %lli)\n", - get_name_by_macstr(trace_orig, read_opt), - seqno_trace->seqno); - - - for (i = 0; i < seqno_trace->seqno_trace_neigh.num_neighbors; i++) { - - snprintf(head, sizeof(head), "%c", - (seqno_trace->seqno_trace_neigh.num_neighbors == i + 1 ? '\' : '|')); - - seqno_trace_print_neigh(seqno_trace->seqno_trace_neigh.seqno_trace_neigh[i], - NULL, - seqno_trace->seqno_trace_neigh.num_neighbors - i - 1, - head, read_opt); - } - - printf("\n"); - } -} - -static int _seqno_trace_neigh_add(struct seqno_trace_neigh *seqno_trace_mom, - struct seqno_trace_neigh *seqno_trace_child) -{ - struct seqno_trace_neigh *data_ptr; - - data_ptr = malloc((seqno_trace_mom->num_neighbors + 1) * sizeof(struct seqno_trace_neigh *)); - if (!data_ptr) - return 0; - - if (seqno_trace_mom->num_neighbors > 0) { - memcpy(data_ptr, seqno_trace_mom->seqno_trace_neigh, - seqno_trace_mom->num_neighbors * sizeof(struct seqno_trace_neigh *)); - free(seqno_trace_mom->seqno_trace_neigh); - } - - seqno_trace_mom->num_neighbors++; - seqno_trace_mom->seqno_trace_neigh = (void *)data_ptr; - seqno_trace_mom->seqno_trace_neigh[seqno_trace_mom->num_neighbors - 1] = seqno_trace_child; - return 1; -} - -static struct seqno_trace_neigh *seqno_trace_neigh_add(struct seqno_trace_neigh *seqno_trace_neigh, - struct bat_node *bat_node, struct seqno_event *seqno_event) -{ - struct seqno_trace_neigh *seqno_trace_neigh_new; - int res; - - seqno_trace_neigh_new = malloc(sizeof(struct seqno_trace_neigh)); - if (!seqno_trace_neigh_new) - goto err; - - seqno_trace_neigh_new->bat_node = bat_node; - seqno_trace_neigh_new->seqno_event = seqno_event; - seqno_trace_neigh_new->num_neighbors = 0; - - res = _seqno_trace_neigh_add(seqno_trace_neigh, seqno_trace_neigh_new); - - if (res < 1) - goto free_neigh; - - return seqno_trace_neigh_new; - -free_neigh: - free(seqno_trace_neigh_new); -err: - return NULL; -} - -static struct seqno_trace_neigh *seqno_trace_find_neigh(struct bat_node *neigh, struct bat_node *prev_sender, - struct seqno_trace_neigh *seqno_trace_neigh) -{ - struct seqno_trace_neigh *seqno_trace_neigh_tmp, *seqno_trace_neigh_ret; - int i; - - for (i = 0; i < seqno_trace_neigh->num_neighbors; i++) { - seqno_trace_neigh_tmp = seqno_trace_neigh->seqno_trace_neigh[i]; - - if ((neigh == seqno_trace_neigh_tmp->bat_node) && - (prev_sender == seqno_trace_neigh_tmp->seqno_event->neigh)) - return seqno_trace_neigh_tmp; - - seqno_trace_neigh_ret = seqno_trace_find_neigh(neigh, prev_sender, seqno_trace_neigh_tmp); - - if (seqno_trace_neigh_ret) - return seqno_trace_neigh_ret; - } - - return NULL; -} - -static void seqno_trace_neigh_free(struct seqno_trace_neigh *seqno_trace_neigh) -{ - int i; - - for (i = 0; i < seqno_trace_neigh->num_neighbors; i++) - seqno_trace_neigh_free(seqno_trace_neigh->seqno_trace_neigh[i]); - - if (seqno_trace_neigh->num_neighbors > 0) - free(seqno_trace_neigh->seqno_trace_neigh); - - free(seqno_trace_neigh); -} - -static int seqno_trace_fix_leaf(struct seqno_trace_neigh *seqno_trace_mom, - struct seqno_trace_neigh *seqno_trace_old_mom, - struct seqno_trace_neigh *seqno_trace_child) -{ - struct seqno_trace_neigh **data_ptr, *seqno_trace_neigh; - int i, j = 0; - - data_ptr = malloc((seqno_trace_old_mom->num_neighbors - 1) * sizeof(struct seqno_trace_neigh *)); - if (!data_ptr) - return 0; - - /* copy all children except the child that is going to move */ - for (i = 0; i < seqno_trace_old_mom->num_neighbors; i++) { - seqno_trace_neigh = seqno_trace_old_mom->seqno_trace_neigh[i]; - - if (seqno_trace_neigh != seqno_trace_child) { - data_ptr[j] = seqno_trace_neigh; - j++; - } - } - - seqno_trace_old_mom->num_neighbors--; - free(seqno_trace_old_mom->seqno_trace_neigh); - seqno_trace_old_mom->seqno_trace_neigh = data_ptr; - - return _seqno_trace_neigh_add(seqno_trace_mom, seqno_trace_child); -} - -static int seqno_trace_check_leaves(struct seqno_trace *seqno_trace, struct seqno_trace_neigh *seqno_trace_neigh_new) -{ - struct seqno_trace_neigh *seqno_trace_neigh_tmp; - int i, res; - - for (i = 0; i < seqno_trace->seqno_trace_neigh.num_neighbors; i++) { - seqno_trace_neigh_tmp = seqno_trace->seqno_trace_neigh.seqno_trace_neigh[i]; - - if ((seqno_trace_neigh_tmp->seqno_event->neigh == seqno_trace_neigh_new->bat_node) && - (seqno_trace_neigh_tmp->seqno_event->prev_sender == seqno_trace_neigh_new->seqno_event->neigh)) { - res = seqno_trace_fix_leaf(seqno_trace_neigh_new, &seqno_trace->seqno_trace_neigh, seqno_trace_neigh_tmp); - - if (res < 1) - return res; - - /* restart checking procedure because we just changed the array we are working on */ - return seqno_trace_check_leaves(seqno_trace, seqno_trace_neigh_new); - } - } - - return 1; -} - -static struct seqno_trace *seqno_trace_new(struct seqno_event *seqno_event) -{ - struct seqno_trace *seqno_trace; - - seqno_trace = malloc(sizeof(struct seqno_trace)); - if (!seqno_trace) { - fprintf(stderr, "Could not allocate memory for seqno tracing data (out of mem?)\n"); - return NULL; - } - - INIT_LIST_HEAD(&seqno_trace->list); - seqno_trace->seqno = seqno_event->seqno; - seqno_trace->print = 0; - - seqno_trace->seqno_trace_neigh.num_neighbors = 0; - - return seqno_trace; -} - -static void seqno_trace_free(struct seqno_trace *seqno_trace) -{ - int i; - - for (i = 0; i < seqno_trace->seqno_trace_neigh.num_neighbors; i++) - seqno_trace_neigh_free(seqno_trace->seqno_trace_neigh.seqno_trace_neigh[i]); - - free(seqno_trace); -} - -static int seqno_trace_add(struct list_head_first *trace_list, struct bat_node *bat_node, - struct seqno_event *seqno_event, char print_trace) -{ - struct seqno_trace *seqno_trace = NULL, *seqno_trace_tmp = NULL, *seqno_trace_prev = NULL; - struct seqno_trace_neigh *seqno_trace_neigh; - - list_for_each_entry(seqno_trace_tmp, trace_list, list) { - if (seqno_trace_tmp->seqno == seqno_event->seqno) { - seqno_trace = seqno_trace_tmp; - break; - } - - if (seqno_trace_tmp->seqno > seqno_event->seqno) - break; - - seqno_trace_prev = seqno_trace_tmp; - } - - if (!seqno_trace) { - seqno_trace = seqno_trace_new(seqno_event); - if (!seqno_trace) - goto err; - - if ((list_empty(trace_list)) || - (seqno_event->seqno > ((struct seqno_trace *)trace_list->prev)->seqno)) - list_add_tail(&seqno_trace->list, trace_list); - else if (seqno_event->seqno < ((struct seqno_trace *)trace_list->next)->seqno) - list_add_before((struct list_head *)trace_list, trace_list->next, &seqno_trace->list); - else - list_add_before(&seqno_trace_prev->list, &seqno_trace_tmp->list, &seqno_trace->list); - } - - if (print_trace) - seqno_trace->print = print_trace; - - seqno_trace_neigh = seqno_trace_find_neigh(seqno_event->neigh, - seqno_event->prev_sender, - &seqno_trace->seqno_trace_neigh); - - /* no neighbor found to hook up to - adding new root node */ - if (!seqno_trace_neigh) - seqno_trace_neigh = seqno_trace_neigh_add(&seqno_trace->seqno_trace_neigh, - bat_node, seqno_event); - else - seqno_trace_neigh = seqno_trace_neigh_add(seqno_trace_neigh, bat_node, seqno_event); - - if (seqno_trace_neigh) - seqno_trace_check_leaves(seqno_trace, seqno_trace_neigh); - - return 1; - -err: - return 0; -} - -static void trace_seqnos(char *trace_orig, long long seqno_min, long long seqno_max, char *filter_orig, 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; - struct seqno_trace *seqno_trace, *seqno_trace_tmp; - char check_orig[NAME_LEN], print_trace; - int res; - - /* if no option was given filter_orig is empty */ - memset(check_orig, 0, NAME_LEN); - INIT_LIST_HEAD_FIRST(trace_list); - - while (NULL != (hashit = hash_iterate(node_hash, hashit))) { - bat_node = hashit->bucket->data; - - list_for_each_entry(orig_event, &bat_node->orig_event_list, list) { - - /* we might have no log file from this node */ - if (list_empty(&orig_event->event_list)) - 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 (!compare_name(trace_orig, seqno_event->orig->name)) - continue; - - if ((seqno_min != -1) && (seqno_event->seqno < seqno_min)) - continue; - - if ((seqno_max != -1) && (seqno_event->seqno > seqno_max)) - continue; - - /* if no filter option was given all seqno traces are to be printed */ - print_trace = compare_name(filter_orig, check_orig); - - if (!compare_name(filter_orig, check_orig) && - compare_name(filter_orig, bat_node->name)) - print_trace = 1; - - res = seqno_trace_add(&trace_list, bat_node, seqno_event, print_trace); - - if (res < 1) - goto out; - } - } - } - - seqno_trace_print(&trace_list, trace_orig, seqno_min, seqno_max, filter_orig, read_opt); - -out: - list_for_each_entry_safe(seqno_trace, seqno_trace_tmp, &trace_list, list) { - list_del((struct list_head *)&trace_list, &seqno_trace->list, &trace_list); - seqno_trace_free(seqno_trace); - } - - return; -} - -static void print_rt_tables(char *rt_orig, long long seqno_min, long long seqno_max, char *filter_orig, int read_opt) -{ - struct bat_node *bat_node; - struct rt_table *rt_table; - struct seqno_event *seqno_event; - char check_orig[NAME_LEN]; - int i; - - /* if no option was given filter_orig is empty */ - memset(check_orig, 0, NAME_LEN); - - printf("Routing tables of originator: %s ", - get_name_by_macstr(rt_orig, read_opt)); - - if ((seqno_min == -1) && (seqno_max == -1)) - printf("[all sequence numbers]"); - else if (seqno_min == seqno_max) - printf("[sequence number: %lli]", seqno_min); - else - printf("[sequence number range: %lli-%lli]", seqno_min, seqno_max); - - if (!compare_name(filter_orig, check_orig)) - printf(" [filter originator: %s]", - get_name_by_macstr(filter_orig, read_opt)); - - printf("\n"); - - bat_node = node_get(rt_orig); - if (!bat_node) - goto out; - - /* we might have no log file from this node */ - if (list_empty(&bat_node->rt_table_list)) - goto out; - - list_for_each_entry(rt_table, &bat_node->rt_table_list, list) { - seqno_event = rt_table->rt_hist->seqno_event; - - if (!compare_name(filter_orig, check_orig) && - !compare_name(filter_orig, seqno_event->orig->name)) - continue; - - if ((seqno_min != -1) && (seqno_event->seqno < seqno_min)) - continue; - - if ((seqno_max != -1) && (seqno_event->seqno > seqno_max)) - continue; - - if (seqno_event->seqno > -1) { - printf("rt change triggered by OGM from: %s (tq: %i, ttl: %i, seqno %lli", - get_name_by_macstr(seqno_event->orig->name, read_opt), - seqno_event->tq, seqno_event->ttl, seqno_event->seqno); - printf(", neigh: %s", - get_name_by_macstr(seqno_event->neigh->name, read_opt)); - printf(", prev_sender: %s)\n", - get_name_by_macstr(seqno_event->prev_sender->name, read_opt)); - } else { - printf("rt change triggered by originator timeout: \n"); - } - - for (i = 0; i < rt_table->num_entries; i++) { - printf("%s %s via next hop", - (rt_table->entries[i].flags ? " *" : " "), - get_name_by_macstr(rt_table->entries[i].orig, read_opt)); - printf(" %s", - get_name_by_macstr(rt_table->entries[i].next_hop->name, read_opt)); - - switch (rt_table->entries[i].flags) { - case RT_FLAG_ADD: - printf(" (route added)\n"); - break; - case RT_FLAG_UPDATE: - printf(" (next hop changed)\n"); - break; - case RT_FLAG_DELETE: - printf(" (route deleted)\n"); - break; - default: - printf("\n"); - break; - } - } - - printf("\n"); - } - -out: - return; -} - -static int get_orig_addr(char *orig_name, char *orig_addr) -{ - struct bat_host *bat_host; - struct ether_addr *orig_mac; - char *orig_name_tmp = orig_name; - - bat_host = bat_hosts_find_by_name(orig_name_tmp); - - if (bat_host) { - orig_name_tmp = ether_ntoa_long((struct ether_addr *)&bat_host->mac_addr); - goto copy_name; - } - - orig_mac = ether_aton(orig_name_tmp); - - if (!orig_mac) { - printf("Error - the originator is not a mac address or bat-host name: %s\n", orig_name); - goto err; - } - - /** - * convert the given mac address to the long format to - * make sure we can find it - */ - orig_name_tmp = ether_ntoa_long(orig_mac); - -copy_name: - strncpy(orig_addr, orig_name_tmp, NAME_LEN); - return 1; - -err: - return 0; -} - -int bisect(int argc, char **argv) -{ - int ret = EXIT_FAILURE, res, optchar, found_args = 1; - int read_opt = USE_BAT_HOSTS, num_parsed_files; - long long tmp_seqno, seqno_max = -1, seqno_min = -1; - char *trace_orig_ptr = NULL, *rt_orig_ptr = NULL, *loop_orig_ptr = NULL; - char orig[NAME_LEN], filter_orig[NAME_LEN], *dash_ptr, *filter_orig_ptr = NULL; - - memset(orig, 0, NAME_LEN); - memset(filter_orig, 0, NAME_LEN); - - while ((optchar = getopt(argc, argv, "hl:no:r:s:t:")) != -1) { - switch (optchar) { - case 'h': - bisect_usage(); - return EXIT_SUCCESS; - case 'l': - loop_orig_ptr = optarg; - found_args += ((*((char*)(optarg - 1)) == optchar ) ? 1 : 2); - break; - case 'n': - read_opt &= ~USE_BAT_HOSTS; - found_args += 1; - break; - case 'o': - filter_orig_ptr = optarg; - found_args += ((*((char*)(optarg - 1)) == optchar ) ? 1 : 2); - break; - case 'r': - rt_orig_ptr = optarg; - found_args += ((*((char*)(optarg - 1)) == optchar ) ? 1 : 2); - break; - case 's': - dash_ptr = strchr(optarg, '-'); - if (dash_ptr) - *dash_ptr = 0; - - tmp_seqno = strtol(optarg, NULL , 10); - if ((tmp_seqno >= 0) && (tmp_seqno <= UINT32_MAX)) - seqno_min = tmp_seqno; - else - fprintf(stderr, "Warning - given sequence number is out of range: %lli\n", tmp_seqno); - - if (dash_ptr) { - tmp_seqno = strtol(dash_ptr + 1, NULL , 10); - if ((tmp_seqno >= 0) && (tmp_seqno <= UINT32_MAX)) - seqno_max = tmp_seqno; - else - fprintf(stderr, "Warning - given sequence number is out of range: %lli\n", tmp_seqno); - - *dash_ptr = '-'; - } - - found_args += ((*((char*)(optarg - 1)) == optchar ) ? 1 : 2); - break; - case 't': - trace_orig_ptr = optarg; - found_args += ((*((char*)(optarg - 1)) == optchar ) ? 1 : 2); - break; - default: - bisect_usage(); - return EXIT_FAILURE; - } - } - - if (argc <= found_args + 1) { - printf("Error - need at least 2 log files to compare\n"); - bisect_usage(); - goto err; - } - - node_hash = hash_new(64, compare_name, choose_name); - - if (!node_hash) { - printf("Error - could not create node hash table\n"); - goto err; - } - - bat_hosts_init(read_opt); - num_parsed_files = 0; - - if ((rt_orig_ptr) && (trace_orig_ptr)) { - printf("Error - the 'print routing table' option can't be used together with the the 'trace seqno' option\n"); - goto err; - } else if ((loop_orig_ptr) && (trace_orig_ptr)) { - printf("Error - the 'loop detection' option can't be used together with the the 'trace seqno' option\n"); - goto err; - } else if ((loop_orig_ptr) && (rt_orig_ptr)) { - printf("Error - the 'loop detection' option can't be used together with the the 'print routing table' option\n"); - goto err; - } else if (rt_orig_ptr) { - res = get_orig_addr(rt_orig_ptr, orig); - - if (res < 1) - goto err; - } else if (trace_orig_ptr) { - res = get_orig_addr(trace_orig_ptr, orig); - - if (res < 1) - goto err; - } else if (loop_orig_ptr) { - res = get_orig_addr(loop_orig_ptr, orig); - - if (res < 1) - goto err; - } - - /* we search a specific seqno - no range */ - if ((seqno_min > 0) && (seqno_max == -1)) - seqno_max = seqno_min; - - if (seqno_min > seqno_max) { - printf("Error - the sequence range minimum (%lli) should be smaller than the maximum (%lli)\n", - seqno_min, seqno_max); - goto err; - } - - if (filter_orig_ptr) { - res = get_orig_addr(filter_orig_ptr, filter_orig); - - if (res < 1) - goto err; - } - - while (argc > found_args) { - res = parse_log_file(argv[found_args]); - - if (res > 0) - num_parsed_files++; - - found_args++; - } - - if (num_parsed_files < 2) { - printf("Error - need at least 2 log files to compare\n"); - goto err; - } - - if (trace_orig_ptr) - trace_seqnos(orig, seqno_min, seqno_max, filter_orig, read_opt); - else if (rt_orig_ptr) - print_rt_tables(orig, seqno_min, seqno_max, filter_orig, read_opt); - else - loop_detection(orig, seqno_min, seqno_max, filter_orig, read_opt); - - ret = EXIT_SUCCESS; - -err: - if (node_hash) - hash_delete(node_hash, node_free); - bat_hosts_free(); - return ret; -} diff --git a/bisect.h b/bisect.h deleted file mode 100644 index 7c43708..0000000 --- a/bisect.h +++ /dev/null @@ -1,97 +0,0 @@ -/* - * Copyright (C) 2009-2012 B.A.T.M.A.N. contributors: - * - * Marek Lindner lindner_marek@yahoo.de - * - * This program is free software; you can redistribute it and/or - * modify it under the terms of version 2 of the GNU General Public - * License as published by the Free Software Foundation. - * - * This program is distributed in the hope that it will be useful, but - * WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU - * General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software - * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA - * 02110-1301, USA - * - */ - -#include "list-batman.h" - -#define NAME_LEN 18 -#define MAX_LINE 256 -#define LOOP_MAGIC_LEN ((2 * NAME_LEN) + (2 * sizeof(int)) - 2) - -#define RT_FLAG_ADD 1 -#define RT_FLAG_UPDATE 2 -#define RT_FLAG_DELETE 3 - -int bisect(int argc, char **argv); - - - -struct bat_node { - char name[NAME_LEN]; - 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; - char loop_magic[LOOP_MAGIC_LEN]; -}; - -struct rt_entry { - char orig[NAME_LEN]; - struct bat_node *next_hop; - char flags; -}; - -struct seqno_event { - struct list_head list; - struct bat_node *orig; - struct bat_node *neigh; - struct bat_node *prev_sender; - long long seqno; - int tq; - int ttl; - struct rt_hist *rt_hist; -}; - -struct seqno_trace_neigh { - struct bat_node *bat_node; - struct seqno_event *seqno_event; - int num_neighbors; - struct seqno_trace_neigh **seqno_trace_neigh; -}; - -struct seqno_trace { - struct list_head list; - long long seqno; - char print; - struct seqno_trace_neigh seqno_trace_neigh; -}; diff --git a/bisect_iv.c b/bisect_iv.c new file mode 100644 index 0000000..c4c06c2 --- /dev/null +++ b/bisect_iv.c @@ -0,0 +1,1596 @@ +/* + * Copyright (C) 2009-2012 B.A.T.M.A.N. contributors: + * + * Marek Lindner lindner_marek@yahoo.de + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of version 2 of the GNU General Public + * License as published by the Free Software Foundation. + * + * This program is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA + * 02110-1301, USA + * + */ + +#include <stdio.h> +#include <stdlib.h> +#include <stdint.h> +#include <unistd.h> +#include <string.h> +#include <errno.h> + +#include "main.h" +#include "bisect_iv.h" +#include "bat-hosts.h" +#include "hash.h" +#include "functions.h" + +static struct hashtable_t *node_hash = NULL; +static struct bat_node *curr_bat_node = NULL; + +static void bisect_iv_usage(void) +{ + printf("Usage: batctl bisect_iv [parameters] <file1> <file2> .. <fileN>\n"); + printf("parameters:\n"); + printf(" \t -h print this help\n"); + printf(" \t -l run a loop detection of given mac address or bat-host (default)\n"); + printf(" \t -n don't convert addresses to bat-host names\n"); + printf(" \t -o only display orig events that affect given mac address or bat-host\n"); + printf(" \t -r print routing tables of given mac address or bat-host\n"); + printf(" \t -s seqno range to limit the output\n"); + printf(" \t -t trace seqnos of given mac address or bat-host\n"); +} + +static int compare_name(void *data1, void *data2) +{ + return (memcmp(data1, data2, NAME_LEN) == 0 ? 1 : 0); +} + +static int choose_name(void *data, int32_t size) +{ + unsigned char *key= data; + uint32_t hash = 0, m_size = NAME_LEN - 1; + size_t i; + + for (i = 0; i < m_size; i++) { + hash += key[i]; + hash += (hash << 10); + hash ^= (hash >> 6); + } + + hash += (hash << 3); + hash ^= (hash >> 11); + hash += (hash << 15); + + return (hash % size); +} + +static struct bat_node *node_get(char *name) +{ + struct bat_node *bat_node; + + if (!name) + return NULL; + + bat_node = (struct bat_node *)hash_find(node_hash, name); + if (bat_node) + goto out; + + bat_node = malloc(sizeof(struct bat_node)); + if (!bat_node) { + fprintf(stderr, "Could not allocate memory for data structure (out of mem?) - skipping"); + return NULL; + } + + strncpy(bat_node->name, name, NAME_LEN); + 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(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) { + list_del((struct list_head *)&bat_node->rt_table_list, &rt_table->list, &bat_node->rt_table_list); + + free(rt_table->entries); + free(rt_table); + } + + free(bat_node); +} + +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 = -1; + + if (!curr_bat_node) { + fprintf(stderr, "Routing table change without preceding OGM - skipping"); + goto err; + } + + if (!orig) { + fprintf(stderr, "Invalid originator found - skipping"); + goto err; + } + + if ((rt_flag != RT_FLAG_DELETE) && (!next_hop)) { + fprintf(stderr, "Invalid next hop found - skipping"); + goto err; + } + + if ((rt_flag == RT_FLAG_UPDATE) && (!old_next_hop)) { + fprintf(stderr, "Invalid old next hop found - skipping"); + goto err; + } + + next_hop_node = node_get(next_hop); + 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 preceding 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; + memset(rt_hist->loop_magic, 0, sizeof(rt_hist->loop_magic)); + + 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); + + switch (rt_flag) { + case RT_FLAG_ADD: + if (prev_rt_table) + rt_table->num_entries = prev_rt_table->num_entries + 1; + break; + case RT_FLAG_UPDATE: + if (prev_rt_table) { + rt_table->num_entries = prev_rt_table->num_entries + 1; + + /* if we had that route already we just change the entry */ + for (i = 0; i < prev_rt_table->num_entries; i++) { + if (compare_name(orig, prev_rt_table->entries[i].orig)) { + rt_table->num_entries = prev_rt_table->num_entries; + break; + } + } + } + break; + case RT_FLAG_DELETE: + if (prev_rt_table) { + rt_table->num_entries = prev_rt_table->num_entries + 1; + + /* if we had that route already we just change the entry */ + for (i = 0; i < prev_rt_table->num_entries; i++) { + if (compare_name(orig, prev_rt_table->entries[i].orig)) { + rt_table->num_entries = prev_rt_table->num_entries; + break; + } + } + + if (rt_table->num_entries != prev_rt_table->num_entries) { + fprintf(stderr, + "Found a delete entry of orig '%s' but no existing record - skipping", + orig); + goto rt_hist_free; + } + + /** + * we need to create a special seqno event as a timer instead + * of an OGM triggered that event + */ + 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 rt_hist_free; + } + + INIT_LIST_HEAD(&seqno_event->list); + 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_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 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 rt_hist_free; + } + + if (prev_rt_table) { + for (i = 0; i < prev_rt_table->num_entries; i++) { + /* if we have a previously deleted item don't copy it over */ + if (prev_rt_table->entries[i].flags == RT_FLAG_DELETE) { + rt_table->num_entries--; + continue; + } + + /** + * if we delete one item the entries are not in sync anymore, + * therefore we need to counters: one for the old and one for + * the new routing table + */ + j++; + + 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) + rt_table->entries[j].next_hop = next_hop_node; + rt_table->entries[j].flags = rt_flag; + continue; + } + + rt_table->entries[j].flags = 0; + } + } + + if ((rt_table->num_entries == 1) || (rt_table->num_entries != j + 1)) { + i = rt_table->num_entries; + strncpy(rt_table->entries[i - 1].orig, orig, NAME_LEN); + rt_table->entries[i - 1].next_hop = next_hop_node; + 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); + 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: + return 0; +} + +static int seqno_event_new(char *iface_addr, char *orig, char *prev_sender, char *neigh, long long 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) { + fprintf(stderr, "Invalid interface address found - skipping"); + goto err; + } + + if (!orig) { + fprintf(stderr, "Invalid originator found - skipping"); + goto err; + } + + if (!neigh) { + fprintf(stderr, "Invalid neighbor found - skipping"); + goto err; + } + + if ((seqno < 0) || (seqno > UINT32_MAX)) { + fprintf(stderr, "Invalid sequence number found (%lli) - skipping", seqno); + goto err; + } + + if ((tq < 0) || (tq > UINT8_MAX)) { + fprintf(stderr, "Invalid tq value found (%i) - skipping", tq); + goto err; + } + + if ((ttl < 0) || (ttl > UINT8_MAX)) { + fprintf(stderr, "Invalid ttl value found (%i) - skipping", ttl); + goto err; + } + + curr_bat_node = node_get(iface_addr); + if (!curr_bat_node) + goto err; + + orig_node = node_get(orig); + if (!orig_node) + goto err; + + neigh_node = node_get(neigh); + if (!neigh_node) + goto err; + + prev_sender_node = node_get(prev_sender); + 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"); + goto err; + } + + INIT_LIST_HEAD(&seqno_event->list); + seqno_event->orig = orig_node; + seqno_event->neigh = neigh_node; + seqno_event->prev_sender = prev_sender_node; + seqno_event->seqno = seqno; + seqno_event->tq = tq; + seqno_event->ttl = ttl; + seqno_event->rt_hist = NULL; + list_add_tail(&seqno_event->list, &orig_event->event_list); + + return 1; + +err: + return 0; +} + +static int parse_log_file(char *file_path) +{ + FILE *fd; + char line_buff[MAX_LINE], *start_ptr, *start_ptr_safe, *tok_ptr; + char *neigh, *iface_addr, *orig, *prev_sender, rt_flag; + int line_count = 0, tq, ttl, i, res, max; + long long seqno; + + fd = fopen(file_path, "r"); + + if (!fd) { + fprintf(stderr, "Error - could not open file '%s': %s\n", file_path, strerror(errno)); + return 0; + } + + while (fgets(line_buff, sizeof(line_buff), fd) != NULL) { + /* ignore the timestamp at the beginning of each line */ + start_ptr = line_buff + 13; + line_count++; + + if (strstr(start_ptr, "Received BATMAN packet via NB")) { + strtok_r(start_ptr, " ", &start_ptr_safe); + neigh = iface_addr = orig = prev_sender = NULL; + seqno = tq = ttl = -1; + + for (i = 0; i < 21; i++) { + tok_ptr = strtok_r(NULL, " ", &start_ptr_safe); + if (!tok_ptr) + break; + + switch (i) { + case 4: + neigh = tok_ptr; + neigh[strlen(neigh) - 1] = 0; + break; + case 7: + iface_addr = tok_ptr + 1; + iface_addr[strlen(iface_addr) - 1] = 0; + break; + case 10: + orig = tok_ptr; + orig[strlen(orig) - 1] = 0; + break; + case 14: + prev_sender = tok_ptr; + prev_sender[strlen(prev_sender) - 1] = 0; + break; + case 16: + seqno = strtoll(tok_ptr, NULL, 10); + break; + case 18: + tq = strtol(tok_ptr, NULL, 10); + break; + case 20: + ttl = strtol(tok_ptr, NULL, 10); + break; + } + } + + if (ttl == -1) { + fprintf(stderr, "Broken 'received packet' line found - skipping [file: %s, line: %i]\n", file_path, line_count); + continue; + } + +// fprintf(stderr, "received packet (line %i): neigh: '%s', iface_addr: '%s', orig: '%s', prev_sender: '%s', seqno: %i, tq: %i, ttl: %i\n", line_count, neigh, iface_addr, orig, prev_sender, seqno, tq, ttl); + + res = seqno_event_new(iface_addr, orig, prev_sender, neigh, seqno, tq, ttl); + if (res < 1) + fprintf(stderr, " [file: %s, line: %i]\n", file_path, line_count); + + } else if (strstr(start_ptr, "Adding route towards") || + strstr(start_ptr, "Changing route towards") || + strstr(start_ptr, "Deleting route towards")) { + + rt_flag = RT_FLAG_UPDATE; + max = 12; + + if (strstr(start_ptr, "Adding route towards")) { + rt_flag = RT_FLAG_ADD; + max = 5; + } else if (strstr(start_ptr, "Deleting route towards")) { + rt_flag = RT_FLAG_DELETE; + max = 3; + } + + strtok_r(start_ptr, " ", &start_ptr_safe); + orig = neigh = prev_sender = NULL; + + for (i = 0; i < max; i++) { + tok_ptr = strtok_r(NULL, " ", &start_ptr_safe); + if (!tok_ptr) + break; + + switch (i) { + case 2: + orig = tok_ptr; + if (rt_flag == RT_FLAG_DELETE) + orig[strlen(orig) - 1] = 0; + break; + case 4: + if (rt_flag == RT_FLAG_ADD) { + neigh = tok_ptr; + neigh[strlen(neigh) - 2] = 0; + } + break; + case 5: + neigh = tok_ptr; + break; + case 9: + prev_sender = tok_ptr; + prev_sender[strlen(prev_sender) - 2] = 0; + break; + } + } + +// 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)) || + ((rt_flag == RT_FLAG_DELETE) && (!orig))) { + fprintf(stderr, "Broken '%s route' line found - skipping [file: %s, line: %i]\n", + (rt_flag == RT_FLAG_UPDATE ? "changing" : + (rt_flag == RT_FLAG_ADD ? "adding" : "deleting")), + file_path, line_count); + continue; + } + + res = routing_table_new(orig, neigh, prev_sender, rt_flag); + if (res < 1) + fprintf(stderr, " [file: %s, line: %i]\n", file_path, line_count); + } + } + +// printf("File '%s' parsed (lines: %i)\n", file_path, line_count); + fclose(fd); + curr_bat_node = NULL; + return 1; +} + +static struct rt_hist *get_rt_hist_by_seqno(struct orig_event *orig_event, long long seqno) +{ + 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, long long 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, long long seqno, long long 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]; + + memset(curr_loop_magic, 0, LOOP_MAGIC_LEN); + snprintf(curr_loop_magic, LOOP_MAGIC_LEN, "%s%s%lli%lli", src_node->name, + dst_node->name, seqno, seqno_rand); + + printf("Path towards %s (seqno %lli ", + 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) { + printf(" -> %s%s", + get_name_by_macstr(next_hop_tmp->name, read_opt), + (dst_node == next_hop_tmp ? "." : "")); + + /* 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(&orig_event->event_list)) + goto out; + + /* same here */ + if (list_empty(&orig_event->rt_hist_list)) + goto out; + + /* we are running in a loop */ + if (memcmp(curr_loop_magic, next_hop_tmp->loop_magic, LOOP_MAGIC_LEN) == 0) { + printf(" aborted due to loop!"); + goto out; + } + + memcpy(next_hop_tmp->loop_magic, curr_loop_magic, sizeof(next_hop_tmp->loop_magic)); + + rt_hist = get_rt_hist_by_seqno(orig_event, seqno); + + /* no more routing data - what can we do ? */ + if (!rt_hist) + break; + + next_hop_tmp = rt_hist->next_hop; + } + +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, long long seqno_min, long long seqno_max, + long long 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], loop_check = 0; + int res; + long long seqno_tmp, seqno_min_tmp = seqno_min; + + /* printf("%i: curr_node: %s ", bla, + get_name_by_macstr(curr_node->name, read_opt)); + + printf("dst_node: %s [%i - %i]\n", + get_name_by_macstr(dst_node->name, read_opt), seqno_min, seqno_max); */ + + /* 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%lli%lli", + src_node->name, dst_node->name, + seqno_min_tmp, seqno_rand); + + 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; + } + + if ((seqno_min_tmp != -1) && (rt_hist->seqno_event->seqno < seqno_min_tmp)) + continue; + + if ((seqno_max != -1) && (rt_hist->seqno_event->seqno >= seqno_max)) + continue; + + /* we are running in a loop */ + if (memcmp(curr_loop_magic, rt_hist->loop_magic, LOOP_MAGIC_LEN) == 0) { + rt_hist_tmp = get_rt_hist_by_node_seqno(src_node, dst_node, + rt_hist->seqno_event->seqno); + + if (rt_hist_tmp) + print_rt_path_at_seqno(src_node, dst_node, rt_hist_tmp->next_hop, + rt_hist->seqno_event->seqno, seqno_rand, read_opt); + goto loop; + } + + memcpy(rt_hist->loop_magic, curr_loop_magic, sizeof(rt_hist->loop_magic)); + loop_check = 1; + + /* printf("validate route after change (seqno %i) at node: %s\n", + rt_hist->seqno_event->seqno, + get_name_by_macstr(curr_node->name, read_opt)); */ + + res = find_rt_table_change(src_node, dst_node, rt_hist->next_hop, + seqno_min_tmp, rt_hist->seqno_event->seqno, + seqno_rand, read_opt); + + seqno_min_tmp = rt_hist->seqno_event->seqno + 1; + + /* 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); + } + + /** + * if we have no routing table changes within the seqno range + * the loop detection above won't be triggered + **/ + if (!loop_check) { + if (memcmp(curr_loop_magic, curr_node->loop_magic2, LOOP_MAGIC_LEN) == 0) { + rt_hist_tmp = get_rt_hist_by_node_seqno(src_node, dst_node, seqno_min); + + if (rt_hist_tmp) + print_rt_path_at_seqno(src_node, dst_node, rt_hist_tmp->next_hop, + seqno_min, seqno_rand, read_opt); + + /* no need to print the path twice */ + if (seqno_min == seqno_max) + goto out; + else + goto loop; + } + + memcpy(curr_node->loop_magic2, curr_loop_magic, sizeof(curr_node->loop_magic2)); + } + + seqno_tmp = seqno_max - 1; + if (seqno_min == seqno_max) + seqno_tmp = seqno_max; + + rt_hist = get_rt_hist_by_seqno(orig_event, seqno_tmp); + + if (rt_hist) + return find_rt_table_change(src_node, dst_node, rt_hist->next_hop, + seqno_min_tmp, seqno_max, seqno_rand, read_opt); + +out: + return -1; +loop: + return -2; +} + +static void loop_detection(char *loop_orig, long long seqno_min, long long seqno_max, char *filter_orig, int read_opt) +{ + struct bat_node *bat_node; + struct orig_event *orig_event; + struct hash_it_t *hashit = NULL; + struct rt_hist *rt_hist, *prev_rt_hist; + long long last_seqno = -1, seqno_count = 0; + int res; + 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 (!compare_name(loop_orig, check_orig)) + printf("of originator: %s ", + get_name_by_macstr(loop_orig, read_opt)); + + if ((seqno_min == -1) && (seqno_max == -1)) + printf("[all sequence numbers]"); + else if (seqno_min == seqno_max) + printf("[sequence number: %lli]", seqno_min); + else + printf("[sequence number range: %lli-%lli]", seqno_min, seqno_max); + + if (!compare_name(filter_orig, check_orig)) + printf(" [filter originator: %s]", + get_name_by_macstr(filter_orig, read_opt)); + + printf("\n"); + + while (NULL != (hashit = hash_iterate(node_hash, hashit))) { + bat_node = hashit->bucket->data; + + if (!compare_name(loop_orig, check_orig) && + !compare_name(loop_orig, bat_node->name)) + continue; + + printf("\nChecking host: %s\n", + get_name_by_macstr(bat_node->name, read_opt)); + + list_for_each_entry(orig_event, &bat_node->orig_event_list, list) { + if (bat_node == orig_event->orig_node) + continue; + + if (!compare_name(filter_orig, check_orig) && + !compare_name(filter_orig, orig_event->orig_node->name)) + continue; + + /* 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; + } + + /* 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; + } + + 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; + + if ((seqno_min != -1) && (rt_hist->seqno_event->seqno < seqno_min)) + continue; + + if ((seqno_max != -1) && (rt_hist->seqno_event->seqno > seqno_max)) + continue; + + /** + * 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 (%lli) than previously received seqno (%lli) 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; + } + + if (rt_hist->seqno_event->seqno == prev_rt_hist->seqno_event->seqno + 1) + 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)); */ + + res = 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); + + if (res != -2) + 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); + } + } + } +} + +static void seqno_trace_print_neigh(struct seqno_trace_neigh *seqno_trace_neigh, + struct seqno_event *seqno_event_parent, + int num_sisters, char *head, int read_opt) +{ + char new_head[MAX_LINE]; + int i; + + printf("%s%s- %s [tq: %i, ttl: %i", head, + (strlen(head) == 1 ? "" : num_sisters == 0 ? "\" : "|"), + get_name_by_macstr(seqno_trace_neigh->bat_node->name, read_opt), + seqno_trace_neigh->seqno_event->tq, + seqno_trace_neigh->seqno_event->ttl); + + printf(", neigh: %s", get_name_by_macstr(seqno_trace_neigh->seqno_event->neigh->name, read_opt)); + printf(", prev_sender: %s]", get_name_by_macstr(seqno_trace_neigh->seqno_event->prev_sender->name, read_opt)); + + if ((seqno_event_parent) && + (seqno_trace_neigh->seqno_event->tq > seqno_event_parent->tq)) + printf(" TQ UP!\n"); + else + printf("\n"); + + 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 ? " " : "| ")); + + 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); + } +} + +static void seqno_trace_print(struct list_head_first *trace_list, char *trace_orig, + long long seqno_min, long long seqno_max, char *filter_orig, int read_opt) +{ + struct seqno_trace *seqno_trace; + char head[MAX_LINE], check_orig[NAME_LEN]; + int i; + + /* if no option was given filter_orig is empty */ + memset(check_orig, 0, NAME_LEN); + + printf("Sequence number flow of originator: %s ", + get_name_by_macstr(trace_orig, read_opt)); + + if ((seqno_min == -1) && (seqno_max == -1)) + printf("[all sequence numbers]"); + else if (seqno_min == seqno_max) + printf("[sequence number: %lli]", seqno_min); + else + printf("[sequence number range: %lli-%lli]", seqno_min, seqno_max); + + if (!compare_name(filter_orig, check_orig)) + printf(" [filter originator: %s]", + get_name_by_macstr(filter_orig, read_opt)); + + printf("\n"); + + list_for_each_entry(seqno_trace, trace_list, list) { + if (!seqno_trace->print) + continue; + + printf("+=> %s (seqno %lli)\n", + get_name_by_macstr(trace_orig, read_opt), + seqno_trace->seqno); + + + for (i = 0; i < seqno_trace->seqno_trace_neigh.num_neighbors; i++) { + + snprintf(head, sizeof(head), "%c", + (seqno_trace->seqno_trace_neigh.num_neighbors == i + 1 ? '\' : '|')); + + seqno_trace_print_neigh(seqno_trace->seqno_trace_neigh.seqno_trace_neigh[i], + NULL, + seqno_trace->seqno_trace_neigh.num_neighbors - i - 1, + head, read_opt); + } + + printf("\n"); + } +} + +static int _seqno_trace_neigh_add(struct seqno_trace_neigh *seqno_trace_mom, + struct seqno_trace_neigh *seqno_trace_child) +{ + struct seqno_trace_neigh *data_ptr; + + data_ptr = malloc((seqno_trace_mom->num_neighbors + 1) * sizeof(struct seqno_trace_neigh *)); + if (!data_ptr) + return 0; + + if (seqno_trace_mom->num_neighbors > 0) { + memcpy(data_ptr, seqno_trace_mom->seqno_trace_neigh, + seqno_trace_mom->num_neighbors * sizeof(struct seqno_trace_neigh *)); + free(seqno_trace_mom->seqno_trace_neigh); + } + + seqno_trace_mom->num_neighbors++; + seqno_trace_mom->seqno_trace_neigh = (void *)data_ptr; + seqno_trace_mom->seqno_trace_neigh[seqno_trace_mom->num_neighbors - 1] = seqno_trace_child; + return 1; +} + +static struct seqno_trace_neigh *seqno_trace_neigh_add(struct seqno_trace_neigh *seqno_trace_neigh, + struct bat_node *bat_node, struct seqno_event *seqno_event) +{ + struct seqno_trace_neigh *seqno_trace_neigh_new; + int res; + + seqno_trace_neigh_new = malloc(sizeof(struct seqno_trace_neigh)); + if (!seqno_trace_neigh_new) + goto err; + + seqno_trace_neigh_new->bat_node = bat_node; + seqno_trace_neigh_new->seqno_event = seqno_event; + seqno_trace_neigh_new->num_neighbors = 0; + + res = _seqno_trace_neigh_add(seqno_trace_neigh, seqno_trace_neigh_new); + + if (res < 1) + goto free_neigh; + + return seqno_trace_neigh_new; + +free_neigh: + free(seqno_trace_neigh_new); +err: + return NULL; +} + +static struct seqno_trace_neigh *seqno_trace_find_neigh(struct bat_node *neigh, struct bat_node *prev_sender, + struct seqno_trace_neigh *seqno_trace_neigh) +{ + struct seqno_trace_neigh *seqno_trace_neigh_tmp, *seqno_trace_neigh_ret; + int i; + + for (i = 0; i < seqno_trace_neigh->num_neighbors; i++) { + seqno_trace_neigh_tmp = seqno_trace_neigh->seqno_trace_neigh[i]; + + if ((neigh == seqno_trace_neigh_tmp->bat_node) && + (prev_sender == seqno_trace_neigh_tmp->seqno_event->neigh)) + return seqno_trace_neigh_tmp; + + seqno_trace_neigh_ret = seqno_trace_find_neigh(neigh, prev_sender, seqno_trace_neigh_tmp); + + if (seqno_trace_neigh_ret) + return seqno_trace_neigh_ret; + } + + return NULL; +} + +static void seqno_trace_neigh_free(struct seqno_trace_neigh *seqno_trace_neigh) +{ + int i; + + for (i = 0; i < seqno_trace_neigh->num_neighbors; i++) + seqno_trace_neigh_free(seqno_trace_neigh->seqno_trace_neigh[i]); + + if (seqno_trace_neigh->num_neighbors > 0) + free(seqno_trace_neigh->seqno_trace_neigh); + + free(seqno_trace_neigh); +} + +static int seqno_trace_fix_leaf(struct seqno_trace_neigh *seqno_trace_mom, + struct seqno_trace_neigh *seqno_trace_old_mom, + struct seqno_trace_neigh *seqno_trace_child) +{ + struct seqno_trace_neigh **data_ptr, *seqno_trace_neigh; + int i, j = 0; + + data_ptr = malloc((seqno_trace_old_mom->num_neighbors - 1) * sizeof(struct seqno_trace_neigh *)); + if (!data_ptr) + return 0; + + /* copy all children except the child that is going to move */ + for (i = 0; i < seqno_trace_old_mom->num_neighbors; i++) { + seqno_trace_neigh = seqno_trace_old_mom->seqno_trace_neigh[i]; + + if (seqno_trace_neigh != seqno_trace_child) { + data_ptr[j] = seqno_trace_neigh; + j++; + } + } + + seqno_trace_old_mom->num_neighbors--; + free(seqno_trace_old_mom->seqno_trace_neigh); + seqno_trace_old_mom->seqno_trace_neigh = data_ptr; + + return _seqno_trace_neigh_add(seqno_trace_mom, seqno_trace_child); +} + +static int seqno_trace_check_leaves(struct seqno_trace *seqno_trace, struct seqno_trace_neigh *seqno_trace_neigh_new) +{ + struct seqno_trace_neigh *seqno_trace_neigh_tmp; + int i, res; + + for (i = 0; i < seqno_trace->seqno_trace_neigh.num_neighbors; i++) { + seqno_trace_neigh_tmp = seqno_trace->seqno_trace_neigh.seqno_trace_neigh[i]; + + if ((seqno_trace_neigh_tmp->seqno_event->neigh == seqno_trace_neigh_new->bat_node) && + (seqno_trace_neigh_tmp->seqno_event->prev_sender == seqno_trace_neigh_new->seqno_event->neigh)) { + res = seqno_trace_fix_leaf(seqno_trace_neigh_new, &seqno_trace->seqno_trace_neigh, seqno_trace_neigh_tmp); + + if (res < 1) + return res; + + /* restart checking procedure because we just changed the array we are working on */ + return seqno_trace_check_leaves(seqno_trace, seqno_trace_neigh_new); + } + } + + return 1; +} + +static struct seqno_trace *seqno_trace_new(struct seqno_event *seqno_event) +{ + struct seqno_trace *seqno_trace; + + seqno_trace = malloc(sizeof(struct seqno_trace)); + if (!seqno_trace) { + fprintf(stderr, "Could not allocate memory for seqno tracing data (out of mem?)\n"); + return NULL; + } + + INIT_LIST_HEAD(&seqno_trace->list); + seqno_trace->seqno = seqno_event->seqno; + seqno_trace->print = 0; + + seqno_trace->seqno_trace_neigh.num_neighbors = 0; + + return seqno_trace; +} + +static void seqno_trace_free(struct seqno_trace *seqno_trace) +{ + int i; + + for (i = 0; i < seqno_trace->seqno_trace_neigh.num_neighbors; i++) + seqno_trace_neigh_free(seqno_trace->seqno_trace_neigh.seqno_trace_neigh[i]); + + free(seqno_trace); +} + +static int seqno_trace_add(struct list_head_first *trace_list, struct bat_node *bat_node, + struct seqno_event *seqno_event, char print_trace) +{ + struct seqno_trace *seqno_trace = NULL, *seqno_trace_tmp = NULL, *seqno_trace_prev = NULL; + struct seqno_trace_neigh *seqno_trace_neigh; + + list_for_each_entry(seqno_trace_tmp, trace_list, list) { + if (seqno_trace_tmp->seqno == seqno_event->seqno) { + seqno_trace = seqno_trace_tmp; + break; + } + + if (seqno_trace_tmp->seqno > seqno_event->seqno) + break; + + seqno_trace_prev = seqno_trace_tmp; + } + + if (!seqno_trace) { + seqno_trace = seqno_trace_new(seqno_event); + if (!seqno_trace) + goto err; + + if ((list_empty(trace_list)) || + (seqno_event->seqno > ((struct seqno_trace *)trace_list->prev)->seqno)) + list_add_tail(&seqno_trace->list, trace_list); + else if (seqno_event->seqno < ((struct seqno_trace *)trace_list->next)->seqno) + list_add_before((struct list_head *)trace_list, trace_list->next, &seqno_trace->list); + else + list_add_before(&seqno_trace_prev->list, &seqno_trace_tmp->list, &seqno_trace->list); + } + + if (print_trace) + seqno_trace->print = print_trace; + + seqno_trace_neigh = seqno_trace_find_neigh(seqno_event->neigh, + seqno_event->prev_sender, + &seqno_trace->seqno_trace_neigh); + + /* no neighbor found to hook up to - adding new root node */ + if (!seqno_trace_neigh) + seqno_trace_neigh = seqno_trace_neigh_add(&seqno_trace->seqno_trace_neigh, + bat_node, seqno_event); + else + seqno_trace_neigh = seqno_trace_neigh_add(seqno_trace_neigh, bat_node, seqno_event); + + if (seqno_trace_neigh) + seqno_trace_check_leaves(seqno_trace, seqno_trace_neigh); + + return 1; + +err: + return 0; +} + +static void trace_seqnos(char *trace_orig, long long seqno_min, long long seqno_max, char *filter_orig, 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; + struct seqno_trace *seqno_trace, *seqno_trace_tmp; + char check_orig[NAME_LEN], print_trace; + int res; + + /* if no option was given filter_orig is empty */ + memset(check_orig, 0, NAME_LEN); + INIT_LIST_HEAD_FIRST(trace_list); + + while (NULL != (hashit = hash_iterate(node_hash, hashit))) { + bat_node = hashit->bucket->data; + + list_for_each_entry(orig_event, &bat_node->orig_event_list, list) { + + /* we might have no log file from this node */ + if (list_empty(&orig_event->event_list)) + 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 (!compare_name(trace_orig, seqno_event->orig->name)) + continue; + + if ((seqno_min != -1) && (seqno_event->seqno < seqno_min)) + continue; + + if ((seqno_max != -1) && (seqno_event->seqno > seqno_max)) + continue; + + /* if no filter option was given all seqno traces are to be printed */ + print_trace = compare_name(filter_orig, check_orig); + + if (!compare_name(filter_orig, check_orig) && + compare_name(filter_orig, bat_node->name)) + print_trace = 1; + + res = seqno_trace_add(&trace_list, bat_node, seqno_event, print_trace); + + if (res < 1) + goto out; + } + } + } + + seqno_trace_print(&trace_list, trace_orig, seqno_min, seqno_max, filter_orig, read_opt); + +out: + list_for_each_entry_safe(seqno_trace, seqno_trace_tmp, &trace_list, list) { + list_del((struct list_head *)&trace_list, &seqno_trace->list, &trace_list); + seqno_trace_free(seqno_trace); + } + + return; +} + +static void print_rt_tables(char *rt_orig, long long seqno_min, long long seqno_max, char *filter_orig, int read_opt) +{ + struct bat_node *bat_node; + struct rt_table *rt_table; + struct seqno_event *seqno_event; + char check_orig[NAME_LEN]; + int i; + + /* if no option was given filter_orig is empty */ + memset(check_orig, 0, NAME_LEN); + + printf("Routing tables of originator: %s ", + get_name_by_macstr(rt_orig, read_opt)); + + if ((seqno_min == -1) && (seqno_max == -1)) + printf("[all sequence numbers]"); + else if (seqno_min == seqno_max) + printf("[sequence number: %lli]", seqno_min); + else + printf("[sequence number range: %lli-%lli]", seqno_min, seqno_max); + + if (!compare_name(filter_orig, check_orig)) + printf(" [filter originator: %s]", + get_name_by_macstr(filter_orig, read_opt)); + + printf("\n"); + + bat_node = node_get(rt_orig); + if (!bat_node) + goto out; + + /* we might have no log file from this node */ + if (list_empty(&bat_node->rt_table_list)) + goto out; + + list_for_each_entry(rt_table, &bat_node->rt_table_list, list) { + seqno_event = rt_table->rt_hist->seqno_event; + + if (!compare_name(filter_orig, check_orig) && + !compare_name(filter_orig, seqno_event->orig->name)) + continue; + + if ((seqno_min != -1) && (seqno_event->seqno < seqno_min)) + continue; + + if ((seqno_max != -1) && (seqno_event->seqno > seqno_max)) + continue; + + if (seqno_event->seqno > -1) { + printf("rt change triggered by OGM from: %s (tq: %i, ttl: %i, seqno %lli", + get_name_by_macstr(seqno_event->orig->name, read_opt), + seqno_event->tq, seqno_event->ttl, seqno_event->seqno); + printf(", neigh: %s", + get_name_by_macstr(seqno_event->neigh->name, read_opt)); + printf(", prev_sender: %s)\n", + get_name_by_macstr(seqno_event->prev_sender->name, read_opt)); + } else { + printf("rt change triggered by originator timeout: \n"); + } + + for (i = 0; i < rt_table->num_entries; i++) { + printf("%s %s via next hop", + (rt_table->entries[i].flags ? " *" : " "), + get_name_by_macstr(rt_table->entries[i].orig, read_opt)); + printf(" %s", + get_name_by_macstr(rt_table->entries[i].next_hop->name, read_opt)); + + switch (rt_table->entries[i].flags) { + case RT_FLAG_ADD: + printf(" (route added)\n"); + break; + case RT_FLAG_UPDATE: + printf(" (next hop changed)\n"); + break; + case RT_FLAG_DELETE: + printf(" (route deleted)\n"); + break; + default: + printf("\n"); + break; + } + } + + printf("\n"); + } + +out: + return; +} + +static int get_orig_addr(char *orig_name, char *orig_addr) +{ + struct bat_host *bat_host; + struct ether_addr *orig_mac; + char *orig_name_tmp = orig_name; + + bat_host = bat_hosts_find_by_name(orig_name_tmp); + + if (bat_host) { + orig_name_tmp = ether_ntoa_long((struct ether_addr *)&bat_host->mac_addr); + goto copy_name; + } + + orig_mac = ether_aton(orig_name_tmp); + + if (!orig_mac) { + printf("Error - the originator is not a mac address or bat-host name: %s\n", orig_name); + goto err; + } + + /** + * convert the given mac address to the long format to + * make sure we can find it + */ + orig_name_tmp = ether_ntoa_long(orig_mac); + +copy_name: + strncpy(orig_addr, orig_name_tmp, NAME_LEN); + return 1; + +err: + return 0; +} + +int bisect_iv(int argc, char **argv) +{ + int ret = EXIT_FAILURE, res, optchar, found_args = 1; + int read_opt = USE_BAT_HOSTS, num_parsed_files; + long long tmp_seqno, seqno_max = -1, seqno_min = -1; + char *trace_orig_ptr = NULL, *rt_orig_ptr = NULL, *loop_orig_ptr = NULL; + char orig[NAME_LEN], filter_orig[NAME_LEN], *dash_ptr, *filter_orig_ptr = NULL; + + memset(orig, 0, NAME_LEN); + memset(filter_orig, 0, NAME_LEN); + + while ((optchar = getopt(argc, argv, "hl:no:r:s:t:")) != -1) { + switch (optchar) { + case 'h': + bisect_iv_usage(); + return EXIT_SUCCESS; + case 'l': + loop_orig_ptr = optarg; + found_args += ((*((char*)(optarg - 1)) == optchar ) ? 1 : 2); + break; + case 'n': + read_opt &= ~USE_BAT_HOSTS; + found_args += 1; + break; + case 'o': + filter_orig_ptr = optarg; + found_args += ((*((char*)(optarg - 1)) == optchar ) ? 1 : 2); + break; + case 'r': + rt_orig_ptr = optarg; + found_args += ((*((char*)(optarg - 1)) == optchar ) ? 1 : 2); + break; + case 's': + dash_ptr = strchr(optarg, '-'); + if (dash_ptr) + *dash_ptr = 0; + + tmp_seqno = strtol(optarg, NULL , 10); + if ((tmp_seqno >= 0) && (tmp_seqno <= UINT32_MAX)) + seqno_min = tmp_seqno; + else + fprintf(stderr, "Warning - given sequence number is out of range: %lli\n", tmp_seqno); + + if (dash_ptr) { + tmp_seqno = strtol(dash_ptr + 1, NULL , 10); + if ((tmp_seqno >= 0) && (tmp_seqno <= UINT32_MAX)) + seqno_max = tmp_seqno; + else + fprintf(stderr, "Warning - given sequence number is out of range: %lli\n", tmp_seqno); + + *dash_ptr = '-'; + } + + found_args += ((*((char*)(optarg - 1)) == optchar ) ? 1 : 2); + break; + case 't': + trace_orig_ptr = optarg; + found_args += ((*((char*)(optarg - 1)) == optchar ) ? 1 : 2); + break; + default: + bisect_iv_usage(); + return EXIT_FAILURE; + } + } + + if (argc <= found_args + 1) { + printf("Error - need at least 2 log files to compare\n"); + bisect_iv_usage(); + goto err; + } + + node_hash = hash_new(64, compare_name, choose_name); + + if (!node_hash) { + printf("Error - could not create node hash table\n"); + goto err; + } + + bat_hosts_init(read_opt); + num_parsed_files = 0; + + if ((rt_orig_ptr) && (trace_orig_ptr)) { + printf("Error - the 'print routing table' option can't be used together with the the 'trace seqno' option\n"); + goto err; + } else if ((loop_orig_ptr) && (trace_orig_ptr)) { + printf("Error - the 'loop detection' option can't be used together with the the 'trace seqno' option\n"); + goto err; + } else if ((loop_orig_ptr) && (rt_orig_ptr)) { + printf("Error - the 'loop detection' option can't be used together with the the 'print routing table' option\n"); + goto err; + } else if (rt_orig_ptr) { + res = get_orig_addr(rt_orig_ptr, orig); + + if (res < 1) + goto err; + } else if (trace_orig_ptr) { + res = get_orig_addr(trace_orig_ptr, orig); + + if (res < 1) + goto err; + } else if (loop_orig_ptr) { + res = get_orig_addr(loop_orig_ptr, orig); + + if (res < 1) + goto err; + } + + /* we search a specific seqno - no range */ + if ((seqno_min > 0) && (seqno_max == -1)) + seqno_max = seqno_min; + + if (seqno_min > seqno_max) { + printf("Error - the sequence range minimum (%lli) should be smaller than the maximum (%lli)\n", + seqno_min, seqno_max); + goto err; + } + + if (filter_orig_ptr) { + res = get_orig_addr(filter_orig_ptr, filter_orig); + + if (res < 1) + goto err; + } + + while (argc > found_args) { + res = parse_log_file(argv[found_args]); + + if (res > 0) + num_parsed_files++; + + found_args++; + } + + if (num_parsed_files < 2) { + printf("Error - need at least 2 log files to compare\n"); + goto err; + } + + if (trace_orig_ptr) + trace_seqnos(orig, seqno_min, seqno_max, filter_orig, read_opt); + else if (rt_orig_ptr) + print_rt_tables(orig, seqno_min, seqno_max, filter_orig, read_opt); + else + loop_detection(orig, seqno_min, seqno_max, filter_orig, read_opt); + + ret = EXIT_SUCCESS; + +err: + if (node_hash) + hash_delete(node_hash, node_free); + bat_hosts_free(); + return ret; +} diff --git a/bisect_iv.h b/bisect_iv.h new file mode 100644 index 0000000..d6f2bc9 --- /dev/null +++ b/bisect_iv.h @@ -0,0 +1,97 @@ +/* + * Copyright (C) 2009-2012 B.A.T.M.A.N. contributors: + * + * Marek Lindner lindner_marek@yahoo.de + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of version 2 of the GNU General Public + * License as published by the Free Software Foundation. + * + * This program is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA + * 02110-1301, USA + * + */ + +#include "list-batman.h" + +#define NAME_LEN 18 +#define MAX_LINE 256 +#define LOOP_MAGIC_LEN ((2 * NAME_LEN) + (2 * sizeof(int)) - 2) + +#define RT_FLAG_ADD 1 +#define RT_FLAG_UPDATE 2 +#define RT_FLAG_DELETE 3 + +int bisect_iv(int argc, char **argv); + + + +struct bat_node { + char name[NAME_LEN]; + 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; + char loop_magic[LOOP_MAGIC_LEN]; +}; + +struct rt_entry { + char orig[NAME_LEN]; + struct bat_node *next_hop; + char flags; +}; + +struct seqno_event { + struct list_head list; + struct bat_node *orig; + struct bat_node *neigh; + struct bat_node *prev_sender; + long long seqno; + int tq; + int ttl; + struct rt_hist *rt_hist; +}; + +struct seqno_trace_neigh { + struct bat_node *bat_node; + struct seqno_event *seqno_event; + int num_neighbors; + struct seqno_trace_neigh **seqno_trace_neigh; +}; + +struct seqno_trace { + struct list_head list; + long long seqno; + char print; + struct seqno_trace_neigh seqno_trace_neigh; +}; diff --git a/main.c b/main.c index 1086f8e..390736d 100644 --- a/main.c +++ b/main.c @@ -34,7 +34,7 @@ #include "ping.h" #include "traceroute.h" #include "tcpdump.h" -#include "bisect.h" +#include "bisect_iv.h" #include "vis.h" #include "ioctl.h" #include "functions.h" @@ -85,7 +85,7 @@ void print_usage(void) printf(" \tping|p <destination> \tping another batman adv host via layer 2\n"); printf(" \ttraceroute|tr <destination> \ttraceroute another batman adv host via layer 2\n"); printf(" \ttcpdump|td <interface> \ttcpdump layer 2 traffic on the given interface\n"); - printf(" \tbisect <file1> .. <fileN>\tanalyze given log files for routing stability\n"); + printf(" \tbisect_iv <file1> .. <fileN>\tanalyze given batman iv log files for routing stability\n"); }

int main(int argc, char **argv) @@ -131,7 +131,7 @@ int main(int argc, char **argv)

/* TODO: remove this generic check here and move it into the individual functions */ /* check if user is root */ - if ((strcmp(argv[1], "bisect") != 0) && ((getuid()) || (getgid()))) { + if ((strncmp(argv[1], "bisect", strlen("bisect")) != 0) && ((getuid()) || (getgid()))) { fprintf(stderr, "Error - you must be root to run '%s' !\n", argv[0]); exit(EXIT_FAILURE); } @@ -172,9 +172,9 @@ int main(int argc, char **argv)

ret = ioctl_statistics_get(mesh_iface);

- } else if ((strcmp(argv[1], "bisect") == 0)) { + } else if ((strcmp(argv[1], "bisect_iv") == 0)) {

- ret = bisect(argc - 1, argv + 1); + ret = bisect_iv(argc - 1, argv + 1);

} else {

diff --git a/man/batctl.8 b/man/batctl.8 index f904719..ab02e9a 100644 --- a/man/batctl.8 +++ b/man/batctl.8 @@ -250,13 +250,13 @@ except specified). The following packet types are available: Example: batctl td <interface> -p 129 -> only display batman ogm packets and non batman packets .RE .br -.IP "\fBbisect\fP [\fB-l MAC\fP][\fB-t MAC\fP][\fB-r MAC\fP][\fB-s min\fP [\fB- max\fP]][\fB-o MAC\fP][\fB-n\fP] \fBlogfile1\fP [\fBlogfile2\fP ... \fBlogfileN\fP]" -Analyses the logfiles to build a small internal database of all sent sequence numbers and routing table changes. This -database can then be analyzed in a number of different ways. With "-l" the database can be used to search for routing -loops. Use "-t" to trace OGMs of a host throughout the network. Use "-r" to display routing tables of the nodes. The -option "-s" can be used to limit the output to a range of sequence numbers, between min and max, or to one specific -sequence number, min. Furthermore using "-o" you can filter the output to a specified originator. If "-n" is given -batctl will not replace the MAC addresses with bat-host names in the output. +.IP "\fBbisect_iv\fP [\fB-l MAC\fP][\fB-t MAC\fP][\fB-r MAC\fP][\fB-s min\fP [\fB- max\fP]][\fB-o MAC\fP][\fB-n\fP] \fBlogfile1\fP [\fBlogfile2\fP ... \fBlogfileN\fP]" +Analyses the B.A.T.M.A.N. IV logfiles to build a small internal database of all sent sequence numbers and routing table +changes. This database can then be analyzed in a number of different ways. With "-l" the database can be used to search +for routing loops. Use "-t" to trace OGMs of a host throughout the network. Use "-r" to display routing tables of the +nodes. The option "-s" can be used to limit the output to a range of sequence numbers, between min and max, or to one +specific sequence number, min. Furthermore using "-o" you can filter the output to a specified originator. If "-n" is +given batctl will not replace the MAC addresses with bat-host names in the output. .br .SH FILES .TP