Author: marek Date: 2009-11-04 23:12:40 +0000 (Wed, 04 Nov 2009) New Revision: 1461
Modified: trunk/batctl/bisect.c trunk/batctl/bisect.h Log: [batctl] bisect - fix wrongly detected routing loops
Modified: trunk/batctl/bisect.c =================================================================== --- trunk/batctl/bisect.c 2009-11-04 23:12:34 UTC (rev 1460) +++ trunk/batctl/bisect.c 2009-11-04 23:12:40 UTC (rev 1461) @@ -251,6 +251,7 @@ 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); @@ -606,8 +607,8 @@
list_for_each_entry(seqno_event, &orig_event->event_list, list) { if (seqno_event->seqno > seqno) + break;
- break; if (seqno_event->rt_hist) rt_hist = seqno_event->rt_hist; } @@ -696,9 +697,15 @@ { struct orig_event *orig_event; struct rt_hist *rt_hist, *rt_hist_tmp; - char curr_loop_magic[LOOP_MAGIC_LEN]; - int res; + char curr_loop_magic[LOOP_MAGIC_LEN], loop_check = 0; + int res, 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); @@ -712,20 +719,8 @@ memset(curr_loop_magic, 0, LOOP_MAGIC_LEN); snprintf(curr_loop_magic, LOOP_MAGIC_LEN, "%s%s%i%i", src_node->name, dst_node->name, - seqno_min, seqno_rand); + seqno_min_tmp, seqno_rand);
- /* we are running in a loop */ - if (memcmp(curr_loop_magic, curr_node->loop_magic2, LOOP_MAGIC_LEN) == 0) { - rt_hist = get_rt_hist_by_node_seqno(src_node, dst_node, seqno_max); - - if (rt_hist) - print_rt_path_at_seqno(src_node, dst_node, rt_hist->next_hop, - seqno_max, seqno_rand, read_opt); - goto out; - } - - memcpy(curr_node->loop_magic2, curr_loop_magic, sizeof(curr_node->loop_magic)); - orig_event = orig_event_get_by_ptr(curr_node, dst_node); if (!orig_event) goto out; @@ -737,20 +732,36 @@ continue; }
- if ((seqno_min != -1) && (rt_hist->seqno_event->seqno < seqno_min)) + 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;
- /* printf("validate route after change (seqno %i) of next hop: %s\n", + /* 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(rt_hist->next_hop->name, read_opt));*/ + get_name_by_macstr(curr_node->name, read_opt)); */
res = find_rt_table_change(src_node, dst_node, rt_hist->next_hop, - seqno_min, rt_hist->seqno_event->seqno, - seqno_rand, read_opt); + 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; @@ -768,14 +779,42 @@ rt_hist->seqno_event->seqno, seqno_rand, read_opt); }
- rt_hist = get_rt_hist_by_seqno(orig_event, seqno_max - 1); + /** + * 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, seqno_max, seqno_rand, read_opt); + seqno_min_tmp, seqno_max, seqno_rand, read_opt);
out: return -1; +loop: + return -2; }
static void loop_detection(char *loop_orig, int seqno_min, int seqno_max, char *filter_orig, int read_opt) @@ -784,7 +823,7 @@ struct orig_event *orig_event; struct hash_it_t *hashit = NULL; struct rt_hist *rt_hist, *prev_rt_hist; - int last_seqno = -1, seqno_count = 0; + int last_seqno = -1, seqno_count = 0, res; char check_orig[NAME_LEN];
printf("\nAnalyzing routing tables "); @@ -880,19 +919,25 @@ goto validate_path; }
- /*printf("\n=> checking orig %s in seqno range of: %i - %i ", + 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));*/ + get_name_by_macstr(prev_rt_hist->next_hop->name, read_opt)); */
- find_rt_table_change(bat_node, rt_hist->seqno_event->orig, prev_rt_hist->next_hop, - prev_rt_hist->seqno_event->seqno + 1, rt_hist->seqno_event->seqno, - seqno_count, read_opt); + 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);
- continue; + if (res != -2) + continue; }
validate_path:
Modified: trunk/batctl/bisect.h =================================================================== --- trunk/batctl/bisect.h 2009-11-04 23:12:34 UTC (rev 1460) +++ trunk/batctl/bisect.h 2009-11-04 23:12:40 UTC (rev 1461) @@ -60,6 +60,7 @@ struct seqno_event *seqno_event; struct bat_node *next_hop; char flags; + char loop_magic[LOOP_MAGIC_LEN]; };
struct rt_entry {