bisect_iv.c 44.2 KB
Newer Older
1
// SPDX-License-Identifier: GPL-2.0
2
/* Copyright (C) 2009-2019  B.A.T.M.A.N. contributors:
3
 *
4
 * Marek Lindner <mareklindner@neomailbox.ch>
5
 *
6
 * License-Filename: LICENSES/preferred/GPL-2.0
7 8
 */

9
#include <stdint.h>
10 11 12 13
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <errno.h>
14 15 16
#include <unistd.h>
#include <stddef.h>
#include <netinet/ether.h>
17

18
#include "bisect_iv.h"
19 20
#include "bat-hosts.h"
#include "hash.h"
21
#include "main.h"
22 23 24 25 26
#include "functions.h"

static struct hashtable_t *node_hash = NULL;
static struct bat_node *curr_bat_node = NULL;

27
static void bisect_iv_usage(void)
28
{
29 30 31 32 33 34 35 36 37
	fprintf(stderr, "Usage: batctl bisect_iv [parameters] <file1> <file2> .. <fileN>\n");
	fprintf(stderr, "parameters:\n");
	fprintf(stderr, " \t -h print this help\n");
	fprintf(stderr, " \t -l run a loop detection of given mac address or bat-host (default)\n");
	fprintf(stderr, " \t -n don't convert addresses to bat-host names\n");
	fprintf(stderr, " \t -o only display orig events that affect given mac address or bat-host\n");
	fprintf(stderr, " \t -r print routing tables of given mac address or bat-host\n");
	fprintf(stderr, " \t -s seqno range to limit the output\n");
	fprintf(stderr, " \t -t trace seqnos of given mac address or bat-host\n");
38 39
}

40
static int compare_name(void *data1, void *data2)
41
{
42
	return (memcmp(data1, data2, NAME_LEN) == 0 ? 1 : 0);
43 44
}

45
static int choose_name(void *data, int32_t size)
46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67
{
	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;

68 69 70
	if (!name)
		return NULL;

71 72 73 74 75 76 77 78 79 80 81
	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);
82
	bat_node->name[NAME_LEN - 1] = '\0';
83 84
	INIT_LIST_HEAD(&bat_node->orig_event_list);
	INIT_LIST_HEAD(&bat_node->rt_table_list);
85
	memset(bat_node->loop_magic, 0, sizeof(bat_node->loop_magic));
86
	memset(bat_node->loop_magic2, 0, sizeof(bat_node->loop_magic2));
87 88 89 90 91 92
	hash_add(node_hash, bat_node);

out:
	return bat_node;
}

93 94 95 96 97 98 99 100 101 102
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;
	}

103 104
	INIT_LIST_HEAD(&orig_event->event_list);
	INIT_LIST_HEAD(&orig_event->rt_hist_list);
105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145
	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);
}

146 147
static void node_free(void *data)
{
148
	struct orig_event *orig_event, *orig_event_tmp;
149 150
	struct seqno_event *seqno_event, *seqno_event_tmp;
	struct rt_table *rt_table, *rt_table_tmp;
151
	struct rt_hist *rt_hist, *rt_hist_tmp;
152 153
	struct bat_node *bat_node = (struct bat_node *)data;

154 155
	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) {
156
			list_del(&seqno_event->list);
157 158 159 160
			free(seqno_event);
		}

		list_for_each_entry_safe(rt_hist, rt_hist_tmp, &orig_event->rt_hist_list, list) {
161
			list_del(&rt_hist->list);
162 163 164
			free(rt_hist);
		}

165
		list_del(&orig_event->list);
166
		free(orig_event);
167 168 169
	}

	list_for_each_entry_safe(rt_table, rt_table_tmp, &bat_node->rt_table_list, list) {
170
		list_del(&rt_table->list);
171 172

		free(rt_table->entries);
173 174 175 176 177 178
		free(rt_table);
	}

	free(bat_node);
}

179
static int routing_table_new(char *orig, char *next_hop, char *old_next_hop, char rt_flag)
180 181
{
	struct bat_node *next_hop_node;
182
	struct orig_event *orig_event;
183 184
	struct seqno_event *seqno_event;
	struct rt_table *rt_table, *prev_rt_table = NULL;
185
	struct rt_hist *rt_hist;
186
	int i, j = -1;
187 188

	if (!curr_bat_node) {
189
		fprintf(stderr, "Routing table change without preceding OGM - skipping");
190 191 192 193 194 195 196 197
		goto err;
	}

	if (!orig) {
		fprintf(stderr, "Invalid originator found - skipping");
		goto err;
	}

198
	if ((rt_flag != RT_FLAG_DELETE) && (!next_hop)) {
199 200 201 202
		fprintf(stderr, "Invalid next hop found - skipping");
		goto err;
	}

203
	if ((rt_flag == RT_FLAG_UPDATE) && (!old_next_hop)) {
204 205 206 207 208
		fprintf(stderr, "Invalid old next hop found - skipping");
		goto err;
	}

	next_hop_node = node_get(next_hop);
209
	if ((rt_flag != RT_FLAG_DELETE) && (!next_hop_node))
210 211
		goto err;

212 213 214 215 216
	orig_event = orig_event_get_by_name(curr_bat_node, orig);
	if (!orig_event)
		goto err;

	if (list_empty(&orig_event->event_list)) {
217
		fprintf(stderr, "Routing table change without any preceding OGM of that originator - skipping");
218 219 220 221 222 223 224 225
		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;
	}

226 227 228 229 230 231
	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;
	}

232 233 234 235 236 237 238 239 240 241 242
	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;
	}

	rt_table->num_entries = 1;

	rt_hist->prev_rt_hist = NULL;
	rt_hist->next_hop = next_hop_node;
	rt_hist->flags = rt_flag;
243
	memset(rt_hist->loop_magic, 0, sizeof(rt_hist->loop_magic));
244 245 246

	if (!(list_empty(&orig_event->rt_hist_list)))
		rt_hist->prev_rt_hist = (struct rt_hist *)(orig_event->rt_hist_list.prev);
247

248
	if (!(list_empty(&curr_bat_node->rt_table_list)))
249 250
		prev_rt_table = (struct rt_table *)(curr_bat_node->rt_table_list.prev);

251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282
	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,
283
				        "Found a delete entry of orig '%s' but no existing record - skipping",
284
				        orig);
285
				goto rt_hist_free;
286 287 288 289 290 291 292 293 294
			}

			/**
			 * 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");
295
				goto rt_hist_free;
296
			}
297

298
			seqno_event->orig = node_get(orig);
299 300 301 302 303
			seqno_event->neigh = NULL;
			seqno_event->prev_sender = NULL;
			seqno_event->seqno = -1;
			seqno_event->tq = -1;
			seqno_event->ttl = -1;
304 305
			seqno_event->rt_hist = NULL;
			list_add_tail(&seqno_event->list, &orig_event->event_list);
306
		}
307 308 309
		break;
	default:
		fprintf(stderr, "Unknown rt_flag received: %i - skipping", rt_flag);
310
		goto rt_hist_free;
311 312 313 314 315
	}

	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");
316
		goto rt_hist_free;
317 318
	}

319 320 321 322 323 324 325 326 327 328 329 330 331 332 333
	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++;

334 335 336
			memcpy((char *)&rt_table->entries[j],
			       (char *)&prev_rt_table->entries[i],
			       sizeof(struct rt_entry));
337 338 339 340 341 342 343 344 345 346 347

			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;
		}
	}
348

349
	if ((rt_table->num_entries == 1) || (rt_table->num_entries != j + 1)) {
350 351
		i = rt_table->num_entries;
		strncpy(rt_table->entries[i - 1].orig, orig, NAME_LEN);
352
		rt_table->entries[i - 1].orig[NAME_LEN - 1] = '\0';
353
		rt_table->entries[i - 1].next_hop = next_hop_node;
354
		rt_table->entries[i - 1].flags = rt_flag;
355 356
	}

357 358 359 360
	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;
361
	list_add_tail(&rt_table->list, &curr_bat_node->rt_table_list);
362
	list_add_tail(&rt_hist->list, &orig_event->rt_hist_list);
363 364 365

	return 1;

366 367
rt_hist_free:
	free(rt_hist);
368 369 370 371 372 373
table_free:
	free(rt_table);
err:
	return 0;
}

374
static int seqno_event_new(char *iface_addr, char *orig, char *prev_sender, char *neigh, long long seqno, int tq, int ttl)
375
{
376
	struct bat_node *orig_node, *neigh_node, *prev_sender_node;
377
	struct orig_event *orig_event;
378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394
	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;
	}

395 396
	if ((seqno < 0) || (seqno > UINT32_MAX)) {
		fprintf(stderr, "Invalid sequence number found (%lli) - skipping", seqno);
397 398 399
		goto err;
	}

400
	if ((tq < 0) || (tq > UINT8_MAX)) {
401 402 403 404
		fprintf(stderr, "Invalid tq value found (%i) - skipping", tq);
		goto err;
	}

405
	if ((ttl < 0) || (ttl > UINT8_MAX)) {
406 407 408 409
		fprintf(stderr, "Invalid ttl value found (%i) - skipping", ttl);
		goto err;
	}

410 411 412 413 414 415 416 417 418 419 420 421
	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;

422 423
	prev_sender_node = node_get(prev_sender);
	if (!prev_sender_node)
424 425
		goto err;

426 427 428 429
	orig_event = orig_event_get_by_ptr(curr_bat_node, orig_node);
	if (!orig_event)
		goto err;

430 431 432 433 434 435 436 437
	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;
	}

	seqno_event->orig = orig_node;
	seqno_event->neigh = neigh_node;
438
	seqno_event->prev_sender = prev_sender_node;
439 440
	seqno_event->seqno = seqno;
	seqno_event->tq = tq;
441
	seqno_event->ttl = ttl;
442 443
	seqno_event->rt_hist = NULL;
	list_add_tail(&seqno_event->list, &orig_event->event_list);
444 445 446 447 448 449 450 451 452 453

	return 1;

err:
	return 0;
}

static int parse_log_file(char *file_path)
{
	FILE *fd;
454
	char line_buff[MAX_LINE], *start_ptr, *start_ptr_safe, *tok_ptr;
455
	char *neigh, *iface_addr, *orig, *prev_sender, rt_flag;
456 457
	int line_count = 0, tq, ttl, i, res, max;
	long long seqno;
458 459 460 461 462 463 464 465 466 467 468 469 470 471

	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")) {
472
			strtok_r(start_ptr, " ", &start_ptr_safe);
473
			neigh = iface_addr = orig = prev_sender = NULL;
474
			seqno = tq = ttl = -1;
475

476
			for (i = 0; i < 21; i++) {
477
				tok_ptr = strtok_r(NULL, " ", &start_ptr_safe);
478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493
				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;
494
				case 14:
495 496
					prev_sender = tok_ptr;
					prev_sender[strlen(prev_sender) - 1] = 0;
497
					break;
498
				case 16:
499
					seqno = strtoll(tok_ptr, NULL, 10);
500 501 502 503
					break;
				case 18:
					tq = strtol(tok_ptr, NULL, 10);
					break;
504 505 506
				case 20:
					ttl = strtol(tok_ptr, NULL, 10);
					break;
507 508 509
				}
			}

510
			if (ttl ==  -1) {
511 512 513 514
				fprintf(stderr, "Broken 'received packet' line found - skipping [file: %s, line: %i]\n", file_path, line_count);
				continue;
			}

515
// 			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);
516

517
			res = seqno_event_new(iface_addr, orig, prev_sender, neigh, seqno, tq, ttl);
518 519 520
			if (res < 1)
				fprintf(stderr, " [file: %s, line: %i]\n", file_path, line_count);

521 522 523 524 525 526 527 528 529 530 531 532 533 534 535
		} 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;
			}

536
			strtok_r(start_ptr, " ", &start_ptr_safe);
537
			orig = neigh = prev_sender = NULL;
538

539
			for (i = 0; i < max; i++) {
540
				tok_ptr = strtok_r(NULL, " ", &start_ptr_safe);
541 542 543 544 545 546
				if (!tok_ptr)
					break;

				switch (i) {
				case 2:
					orig = tok_ptr;
547 548 549 550 551 552 553 554
					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;
					}
555 556 557 558 559
					break;
				case 5:
					neigh = tok_ptr;
					break;
				case 9:
560 561
					prev_sender = tok_ptr;
					prev_sender[strlen(prev_sender) - 2] = 0;
562 563 564 565
					break;
				}
			}

566 567
// 			printf("route (file: %s, line %i): orig: '%s', neigh: '%s', prev_sender: '%s'\n",
// 			       file_path, line_count, orig, neigh, prev_sender);
568 569 570 571 572 573 574 575

			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);
576 577 578
				continue;
			}

579
			res = routing_table_new(orig, neigh, prev_sender, rt_flag);
580 581 582 583 584
			if (res < 1)
				fprintf(stderr, " [file: %s, line: %i]\n", file_path, line_count);
		}
	}

585
// 	printf("File '%s' parsed (lines: %i)\n", file_path, line_count);
586
	fclose(fd);
587
	curr_bat_node = NULL;
588 589 590
	return 1;
}

591
static struct rt_hist *get_rt_hist_by_seqno(struct orig_event *orig_event, long long seqno)
592
{
593 594 595 596 597 598
	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;
599

600 601 602 603 604 605 606
		if (seqno_event->rt_hist)
			rt_hist = seqno_event->rt_hist;
	}

	return rt_hist;
}

607
static struct rt_hist *get_rt_hist_by_node_seqno(struct bat_node *bat_node, struct bat_node *orig_node, long long seqno)
608 609 610 611 612 613 614 615 616 617 618 619 620
{
	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,
621
                            struct bat_node *next_hop, long long seqno, long long seqno_rand, int read_opt)
622 623 624 625
{
	struct bat_node *next_hop_tmp;
	struct orig_event *orig_event;
	struct rt_hist *rt_hist;
626 627
	char curr_loop_magic[LOOP_MAGIC_LEN];

628
	snprintf(curr_loop_magic, sizeof(curr_loop_magic), "%s%s%lli%lli", src_node->name,
629 630
	         dst_node->name, seqno, seqno_rand);

631
	printf("Path towards %s (seqno %lli ",
632 633 634
	       get_name_by_macstr(dst_node->name, read_opt), seqno);

	printf("via neigh %s):", get_name_by_macstr(next_hop->name, read_opt));
635

636
	next_hop_tmp = next_hop;
637

638
	while (1) {
639 640 641 642 643 644 645
		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;
646

647 648 649
		orig_event = orig_event_get_by_ptr(next_hop_tmp, dst_node);
		if (!orig_event)
			goto out;
650 651

		/* no more data - path seems[tm] fine */
652
		if (list_empty(&orig_event->event_list))
653 654 655
			goto out;

		/* same here */
656
		if (list_empty(&orig_event->rt_hist_list))
657
			goto out;
658 659

		/* we are running in a loop */
660
		if (memcmp(curr_loop_magic, next_hop_tmp->loop_magic, LOOP_MAGIC_LEN) == 0) {
661
			printf("   aborted due to loop!");
662 663 664
			goto out;
		}

665
		memcpy(next_hop_tmp->loop_magic, curr_loop_magic, sizeof(next_hop_tmp->loop_magic));
666

667
		rt_hist = get_rt_hist_by_seqno(orig_event, seqno);
668

669 670 671
		/* no more routing data - what can we do ? */
		if (!rt_hist)
			break;
672

673 674
		next_hop_tmp = rt_hist->next_hop;
	}
675

676 677 678 679
out:
	printf("\n");
	return 1;
}
680

681
static int find_rt_table_change(struct bat_node *src_node, struct bat_node *dst_node,
682 683
                                struct bat_node *curr_node, long long seqno_min, long long seqno_max,
                                long long seqno_rand, int read_opt)
684 685 686
{
	struct orig_event *orig_event;
	struct rt_hist *rt_hist, *rt_hist_tmp;
687
	char curr_loop_magic[LOOP_MAGIC_LEN], loop_check = 0;
688 689
	int res;
	long long seqno_tmp, seqno_min_tmp = seqno_min;
690 691 692 693 694 695

	/* 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); */
696

697 698 699 700 701 702 703 704 705 706
	/* 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;
	}

707
	snprintf(curr_loop_magic, sizeof(curr_loop_magic), "%s%s%lli%lli",
708
	         src_node->name, dst_node->name,
709
	         seqno_min_tmp, seqno_rand);
710 711 712 713 714 715 716 717 718 719

	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;
720
		}
721

722
		if ((seqno_min_tmp != -1) && (rt_hist->seqno_event->seqno < seqno_min_tmp))
723 724 725 726 727
			continue;

		if ((seqno_max != -1) && (rt_hist->seqno_event->seqno >= seqno_max))
			continue;

728 729 730 731 732 733 734 735 736 737 738 739 740 741 742
		/* 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",
743
		       rt_hist->seqno_event->seqno,
744
		       get_name_by_macstr(curr_node->name, read_opt)); */
745 746

		res = find_rt_table_change(src_node, dst_node, rt_hist->next_hop,
747 748 749 750
		                           seqno_min_tmp, rt_hist->seqno_event->seqno,
		                           seqno_rand, read_opt);

		seqno_min_tmp = rt_hist->seqno_event->seqno + 1;
751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766

		/* 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);
767 768
	}

769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795
	/**
	 * 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);
796 797 798

	if (rt_hist)
		return find_rt_table_change(src_node, dst_node, rt_hist->next_hop,
799
		                            seqno_min_tmp, seqno_max, seqno_rand, read_opt);
800

801
out:
802
	return -1;
803 804
loop:
	return -2;
805 806
}

807
static void loop_detection(char *loop_orig, long long seqno_min, long long seqno_max, char *filter_orig, int read_opt)
808 809
{
	struct bat_node *bat_node;
810
	struct orig_event *orig_event;
811
	struct hash_it_t *hashit = NULL;
812
	struct rt_hist *rt_hist, *prev_rt_hist;
813 814
	long long last_seqno = -1, seqno_count = 0;
	int res;
815
	char check_orig[NAME_LEN];
816

817 818 819 820
	printf("\nAnalyzing routing tables ");

	/* if no option was given loop_orig is empty */
	memset(check_orig, 0, NAME_LEN);
821
	if (!compare_name(loop_orig, check_orig))
822 823 824 825
		printf("of originator: %s ",
		       get_name_by_macstr(loop_orig, read_opt));

	if ((seqno_min == -1) && (seqno_max == -1))
826
		printf("[all sequence numbers]");
827
	else if (seqno_min == seqno_max)
828
		printf("[sequence number: %lli]", seqno_min);
829
	else
830
		printf("[sequence number range: %lli-%lli]", seqno_min, seqno_max);
831 832 833 834 835 836

	if (!compare_name(filter_orig, check_orig))
		printf(" [filter originator: %s]",
		       get_name_by_macstr(filter_orig, read_opt));

	printf("\n");
837 838 839 840

	while (NULL != (hashit = hash_iterate(node_hash, hashit))) {
		bat_node = hashit->bucket->data;

841 842
		if (!compare_name(loop_orig, check_orig) &&
		    !compare_name(loop_orig, bat_node->name))
843 844
			continue;

845
		printf("\nChecking host: %s\n",
846
		       get_name_by_macstr(bat_node->name, read_opt));
847

848 849
		list_for_each_entry(orig_event, &bat_node->orig_event_list, list) {
			if (bat_node == orig_event->orig_node)
850 851
				continue;

852 853 854 855
			if (!compare_name(filter_orig, check_orig) &&
			    !compare_name(filter_orig, orig_event->orig_node->name))
				continue;

856 857 858 859
			/* 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));
860
				continue;
861
			}
862

863 864 865 866
			/* 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));
867
				continue;
868
			}
869

870 871 872 873
			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;
874

875 876 877 878 879 880 881 882 883 884 885 886 887 888
				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;
889

890
				last_seqno = rt_hist->seqno_event->seqno;
891

892 893 894 895 896 897 898 899 900 901 902 903
				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,
904
						        "Smaller seqno (%lli) than previously received seqno (%lli) of orig %s triggered routing table change - skipping recursive check\n",
905 906 907 908 909
						        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;
					}

910 911 912 913
					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 ",
914 915 916 917 918
						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",
919
						get_name_by_macstr(prev_rt_hist->next_hop->name, read_opt)); */
920

921 922 923 924 925
					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);
926

927 928
					if (res != -2)
						continue;
929 930 931 932 933
				}

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);
934 935 936 937 938
			}
		}
	}
}

939
static void seqno_trace_print_neigh(struct seqno_trace_neigh *seqno_trace_neigh,
940
			            struct seqno_event *seqno_event_parent,
941 942 943 944 945
			            int num_sisters, char *head, int read_opt)
{
	char new_head[MAX_LINE];
	int i;

946
	printf("%s%s- %s [tq: %i, ttl: %i", head,
947 948 949 950 951 952
	               (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));
953 954 955 956 957 958 959
	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");
960 961 962

	for (i = 0; i < seqno_trace_neigh->num_neighbors; i++) {
		snprintf(new_head, sizeof(new_head), "%s%s",
963 964 965
		         (strlen(head) > 1 ? head : num_sisters == 0 ? " " : head),
		         (strlen(head) == 1 ? "   " :
		         num_sisters == 0 ? "    " : "|   "));
966

967
		seqno_trace_print_neigh(seqno_trace_neigh->seqno_trace_neigh[i], seqno_trace_neigh->seqno_event,
968 969 970 971
		                        seqno_trace_neigh->num_neighbors - i - 1, new_head, read_opt);
	}
}

972
static void seqno_trace_print(struct list_head *trace_list, char *trace_orig,
973
                              long long seqno_min, long long seqno_max, char *filter_orig, int read_opt)
974 975
{
	struct seqno_trace *seqno_trace;
976
	char head[MAX_LINE], check_orig[NAME_LEN];
977 978
	int i;

979 980 981
	/* if no option was given filter_orig is empty */
	memset(check_orig, 0, NAME_LEN);

982 983 984 985
	printf("Sequence number flow of originator: %s ",
	       get_name_by_macstr(trace_orig, read_opt));

	if ((seqno_min == -1) && (seqno_max == -1))
986
		printf("[all sequence numbers]");
987
	else if (seqno_min == seqno_max)
988
		printf("[sequence number: %lli]", seqno_min);
989
	else
990
		printf("[sequence number range: %lli-%lli]", seqno_min, seqno_max);
991 992 993 994 995 996

	if (!compare_name(filter_orig, check_orig))
		printf(" [filter originator: %s]",
		       get_name_by_macstr(filter_orig, read_opt));

	printf("\n");
997 998

	list_for_each_entry(seqno_trace, trace_list, list) {
999 1000 1001
		if (!seqno_trace->print)
			continue;

1002
		printf("+=> %s (seqno %lli)\n",
1003 1004 1005 1006 1007 1008 1009 1010 1011 1012
		       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],
1013
			                        NULL,
1014 1015 1016 1017 1018 1019 1020 1021 1022 1023 1024
			                        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)
{
1025
	struct seqno_trace_neigh **data_ptr;
1026 1027 1028 1029 1030 1031 1032 1033 1034 1035 1036 1037

	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++;
1038
	seqno_trace_mom->seqno_trace_neigh = data_ptr;
1039 1040 1041 1042 1043 1044 1045 1046 1047 1048 1049 1050 1051 1052 1053 1054 1055 1056 1057 1058 1059 1060 1061 1062 1063 1064 1065 1066 1067 1068 1069
	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;
}

1070
static struct seqno_trace_neigh *seqno_trace_find_neigh(struct bat_node *neigh, struct bat_node *prev_sender,
1071 1072 1073 1074 1075 1076 1077 1078 1079
				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) &&
1080
		    (prev_sender == seqno_trace_neigh_tmp->seqno_event->neigh))
1081 1082
			return seqno_trace_neigh_tmp;

1083
		seqno_trace_neigh_ret = seqno_trace_find_neigh(neigh, prev_sender, seqno_trace_neigh_tmp);
1084 1085 1086 1087 1088 1089 1090 1091 1092 1093 1094 1095 1096 1097 1098 1099 1100 1101 1102 1103 1104 1105 1106 1107 1108 1109 1110 1111 1112 1113 1114 1115 1116 1117 1118 1119 1120 1121 1122 1123 1124 1125 1126 1127 1128 1129 1130 1131 1132 1133 1134 1135 1136 1137 1138 1139 1140 1141

		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) &&
1142
		    (seqno_trace_neigh_tmp->seqno_event->prev_sender == seqno_trace_neigh_new->seqno_event->neigh)) {
1143 1144 1145 1146 1147 1148 1149 1150 1151 1152 1153 1154 1155 1156 1157 1158 1159 1160 1161 1162 1163 1164 1165 1166
			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;
	}

	seqno_trace->seqno = seqno_event->seqno;
1167
	seqno_trace->print = 0;
1168 1169 1170 1171 1172 1173 1174 1175 1176 1177 1178 1179 1180 1181 1182 1183

	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);
}

1184
static int seqno_trace_add(struct list_head *trace_list, struct bat_node *bat_node,
1185
		           struct seqno_event *seqno_event, char print_trace)
1186 1187 1188 1189 1190 1191 1192 1193 1194 1195 1196 1197 1198 1199 1200 1201 1202 1203 1204 1205 1206 1207
{
	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)) ||
1208
		    (seqno_event->seqno > list_last_entry(trace_list, struct seqno_trace, list)->seqno))
1209
			list_add_tail(&seqno_trace->list, trace_list);
1210 1211
		else if (seqno_event->seqno < list_first_entry(trace_list, struct seqno_trace, list)->seqno)
			list_add(&seqno_trace->list, trace_list);
1212
		else
1213
			list_add_behind(&seqno_trace->list, &seqno_trace_prev->list);
1214 1215
	}

1216 1217 1218
	if (print_trace)
		seqno_trace->print = print_trace;

1219
	seqno_trace_neigh = seqno_trace_find_neigh(seqno_event->neigh,
1220
				                   seqno_event->prev_sender,
1221 1222 1223 1224 1225 1226 1227 1228 1229 1230 1231 1232 1233 1234 1235 1236 1237 1238
				                   &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;
}

1239
static void trace_seqnos(char *trace_orig, long long seqno_min, long long seqno_max, char *filter_orig, int read_opt)
1240 1241
{
	struct bat_node *bat_node;
1242
	struct orig_event *orig_event;
1243 1244
	struct seqno_event *seqno_event;
	struct hash_it_t *hashit = NULL;
1245
	struct list_head trace_list;
1246
	struct seqno_trace *seqno_trace, *seqno_trace_tmp;
1247
	char check_orig[NAME_LEN], print_trace;
1248 1249
	int res;

1250 1251
	/* if no option was given filter_orig is empty */
	memset(check_orig, 0, NAME_LEN);
1252
	INIT_LIST_HEAD(&trace_list);
1253 1254 1255 1256

	while (NULL != (hashit = hash_iterate(node_hash, hashit))) {
		bat_node = hashit->bucket->data;

1257
		list_for_each_entry(orig_event, &bat_node->orig_event_list, list) {
1258

1259 1260
			/* we might have no log file from this node */
			if (list_empty(&orig_event->event_list))
1261 1262
				continue;

1263 1264 1265 1266
			list_for_each_entry(seqno_event, &orig_event->event_list, list) {
				/* special seqno that indicates an originator timeout */
				if (seqno_event->seqno == -1)
					continue;
1267

1268 1269
				if (!compare_name(trace_orig, seqno_event->orig->name))
					continue;
1270

1271 1272
				if ((seqno_min != -1) && (seqno_event->seqno < seqno_min))
					continue;
1273

1274 1275
				if ((seqno_max != -1) && (seqno_event->seqno > seqno_max))
					continue;
1276

1277 1278 1279 1280 1281 1282 1283 1284
				/* 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);
1285

1286 1287
				if (res < 1) {
					hash_iterate_free(hashit);
1288
					goto out;
1289
				}
1290
			}
1291 1292 1293
		}
	}

1294
	seqno_trace_print(&trace_list, trace_orig, seqno_min, seqno_max, filter_orig, read_opt);
1295 1296 1297

out:
	list_for_each_entry_safe(seqno_trace, seqno_trace_tmp, &trace_list, list) {
1298
		list_del(&seqno_trace->list);
1299 1300 1301 1302 1303 1304
		seqno_trace_free(seqno_trace);
	}

	return;
}

1305
static void print_rt_tables(char *rt_orig, long long seqno_min, long long seqno_max, char *filter_orig, int read_opt)
1306 1307
{
	struct bat_node *bat_node;
1308
	struct rt_table *rt_table;
1309
	struct seqno_event *seqno_event;
1310
	char check_orig[NAME_LEN];
1311
	int i;
1312

1313 1314 1315
	/* if no option was given filter_orig is empty */
	memset(check_orig, 0, NAME_LEN);

1316 1317 1318 1319
	printf("Routing tables of originator: %s ",
	       get_name_by_macstr(rt_orig, read_opt));

	if ((seqno_min == -1) && (seqno_max == -1))
1320
		printf("[all sequence numbers]");
1321
	else if (seqno_min == seqno_max)
1322
		printf("[sequence number: %lli]", seqno_min);
1323
	else
1324
		printf("[sequence number range: %lli-%lli]", seqno_min, seqno_max);
1325 1326 1327 1328 1329 1330

	if (!compare_name(filter_orig, check_orig))
		printf(" [filter originator: %s]",
		       get_name_by_macstr(filter_orig, read_opt));

	printf("\n");
1331 1332 1333 1334 1335 1336 1337 1338 1339

	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;

1340 1341
	list_for_each_entry(rt_table, &bat_node->rt_table_list, list) {
		seqno_event = rt_table->rt_hist->seqno_event;
1342

1343 1344 1345 1346
		if (!compare_name(filter_orig, check_orig) &&
		    !compare_name(filter_orig, seqno_event->orig->name))
			continue;

1347 1348 1349 1350 1351 1352
		if ((seqno_min != -1) && (seqno_event->seqno < seqno_min))
			continue;

		if ((seqno_max != -1) && (seqno_event->seqno > seqno_max))
			continue;

1353
		if (seqno_event->seqno > -1) {
1354
			printf("rt change triggered by OGM from: %s (tq: %i, ttl: %i, seqno %lli",
1355 1356 1357 1358 1359 1360 1361 1362 1363
			       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");
		}
1364

1365
		for (i = 0; i < rt_table->num_entries; i++) {
1366
			printf("%s %s via next hop",
1367 1368
			       (rt_table->entries[i].flags ? "   *" : "    "),
			       get_name_by_macstr(rt_table->entries[i].orig, read_opt));
1369
			printf(" %s",
1370
			       get_name_by_macstr(rt_table->entries[i].next_hop->name, read_opt));
1371

1372
			switch (rt_table->entries[i].flags) {
1373 1374 1375 1376 1377 1378 1379 1380 1381 1382 1383 1384 1385
			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;
			}
1386 1387 1388 1389 1390 1391 1392 1393 1394 1395
		}

		printf("\n");
	}

out:
	return;
}

static int get_orig_addr(char *orig_name, char *orig_addr)
1396
{
1397
	struct bat_host *bat_host;
1398 1399 1400 1401 1402 1403 1404 1405 1406 1407 1408 1409 1410
	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) {
1411
		fprintf(stderr, "Error - the originator is not a mac address or bat-host name: %s\n", orig_name);
1412 1413 1414 1415 1416 1417 1418 1419 1420 1421 1422
		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);
1423
	orig_addr[NAME_LEN - 1] = '\0';
1424 1425 1426 1427 1428 1429
	return 1;

err:
	return 0;
}

1430
static int bisect_iv(struct state *state __maybe_unused, int argc, char **argv)
1431
{
1432 1433
	int ret = EXIT_FAILURE, res, optchar, found_args = 1;
	int read_opt = USE_BAT_HOSTS, num_parsed_files;
1434
	long long tmp_seqno, seqno_max = -1, seqno_min = -1;
1435
	char *trace_orig_ptr = NULL, *rt_orig_ptr = NULL, *loop_orig_ptr = NULL;
1436
	char orig[NAME_LEN], filter_orig[NAME_LEN], *dash_ptr, *filter_orig_ptr = NULL;
1437

1438
	memset(orig, 0, NAME_LEN);
1439
	memset(filter_orig, 0, NAME_LEN);
1440

1441
	while ((optchar = getopt(argc, argv, "hl:no:r:s:t:")) != -1) {
1442 1443
		switch (optchar) {
		case 'h':
1444
			bisect_iv_usage();
1445
			return EXIT_SUCCESS;
1446 1447 1448 1449
		case 'l':
			loop_orig_ptr = optarg;
			found_args += ((*((char*)(optarg - 1)) == optchar ) ? 1 : 2);
			break;
1450 1451 1452 1453
		case 'n':
			read_opt &= ~USE_BAT_HOSTS;
			found_args += 1;
			break;
1454 1455 1456 1457
		case 'o':
			filter_orig_ptr = optarg;
			found_args += ((*((char*)(optarg - 1)) == optchar ) ? 1 : 2);
			break;
1458 1459 1460 1461
		case 'r':
			rt_orig_ptr = optarg;
			found_args += ((*((char*)(optarg - 1)) == optchar ) ? 1 : 2);
			break;