From 5d01c511fc1c31fdeee6bb515be0ca300854ba21 Mon Sep 17 00:00:00 2001 From: Sander Vrijders Date: Mon, 25 Sep 2017 17:36:18 +0200 Subject: ipcpd: normal: Add refcount to graph edges This adds a refcount to the graph edges so that it is only included in the calculation if both sides announced it. --- src/ipcpd/normal/pol/graph.c | 34 ++++++++++++++++++++------------ src/ipcpd/normal/pol/link_state.c | 6 +++--- src/ipcpd/normal/pol/tests/graph_test.c | 35 +++++++++++++++++++++++++++------ 3 files changed, 53 insertions(+), 22 deletions(-) diff --git a/src/ipcpd/normal/pol/graph.c b/src/ipcpd/normal/pol/graph.c index 27c5cfca..9e723737 100644 --- a/src/ipcpd/normal/pol/graph.c +++ b/src/ipcpd/normal/pol/graph.c @@ -40,6 +40,7 @@ struct edge { struct list_head next; struct vertex * nb; qosspec_t qs; + int announced; }; struct vertex { @@ -94,6 +95,7 @@ static struct edge * add_edge(struct vertex * vertex, list_head_init(&edge->next); edge->nb = nb; + edge->announced = 0; list_add(&edge->next, &vertex->edges); @@ -251,7 +253,7 @@ int graph_update_edge(struct graph * graph, e = add_edge(v, nb); if (e == NULL) { if (list_is_empty(&v->edges)) - del_vertex(graph, v); + del_vertex(graph, v); if (list_is_empty(&nb->edges)) del_vertex(graph, nb); pthread_mutex_unlock(&graph->lock); @@ -260,13 +262,15 @@ int graph_update_edge(struct graph * graph, } } + e->announced++; e->qs = qs; nb_e = find_edge_by_addr(nb, s_addr); if (nb_e == NULL) { nb_e = add_edge(nb, v); if (nb_e == NULL) { - del_edge(e); + if (--e->announced == 0) + del_edge(e); if (list_is_empty(&v->edges)) del_vertex(graph, v); if (list_is_empty(&nb->edges)) @@ -277,6 +281,7 @@ int graph_update_edge(struct graph * graph, } } + nb_e->announced++; nb_e->qs = qs; pthread_mutex_unlock(&graph->lock); @@ -300,33 +305,35 @@ int graph_del_edge(struct graph * graph, v = find_vertex_by_addr(graph, s_addr); if (v == NULL) { pthread_mutex_unlock(&graph->lock); - log_err("No such vertex."); + log_err("No such source vertex."); return -1; } nb = find_vertex_by_addr(graph, d_addr); if (nb == NULL) { pthread_mutex_unlock(&graph->lock); - log_err("No such vertex."); + log_err("No such destination vertex."); return -1; } e = find_edge_by_addr(v, d_addr); if (e == NULL) { pthread_mutex_unlock(&graph->lock); - log_err("No such edge."); + log_err("No such source edge."); return -1; } nb_e = find_edge_by_addr(nb, s_addr); if (nb_e == NULL) { pthread_mutex_unlock(&graph->lock); - log_err("No such edge."); + log_err("No such destination edge."); return -1; } - del_edge(e); - del_edge(nb_e); + if (--e->announced == 0) + del_edge(e); + if (--nb_e->announced == 0) + del_edge(nb_e); /* Removing vertex if it was the last edge */ if (list_is_empty(&v->edges)) @@ -407,6 +414,10 @@ static struct vertex ** dijkstra(struct graph * graph, list_for_each(p, &v->edges) { e = list_entry(p, struct edge, next); + /* Only include it if both sides announced it. */ + if (e->announced != 2) + continue; + /* * NOTE: Current weight is just hop count. * Method could be extended to use a different @@ -483,10 +494,7 @@ int graph_routing_table(struct graph * graph, list_head_init(table); - /* - * Now loop through the list of predecessors - * to construct the routing table - */ + /* Now construct the routing table from the nhops. */ list_for_each(p, &graph->vertices) { v = list_entry(p, struct vertex, next); @@ -507,7 +515,7 @@ int graph_routing_table(struct graph * graph, goto fail_n; t->dst = v->addr; - n->nhop = nhops[i]->addr; + n->nhop = nhops[i]->addr; list_add(&n->next, &t->nhops); list_add(&t->next, table); diff --git a/src/ipcpd/normal/pol/link_state.c b/src/ipcpd/normal/pol/link_state.c index d45dae15..51d317bc 100644 --- a/src/ipcpd/normal/pol/link_state.c +++ b/src/ipcpd/normal/pol/link_state.c @@ -379,12 +379,11 @@ static int nbr_to_fd(uint64_t addr) static void * calculate_pff(void * o) { struct routing_i * instance; - int i = 0; int fd; struct list_head table; struct list_head * p; struct list_head * q; - int fds[1024]; + int fds[AP_MAX_FLOWS]; instance = (struct routing_i *) o; @@ -399,6 +398,7 @@ static void * calculate_pff(void * o) pff_flush(instance->pff); list_for_each(p, &table) { + int i = 0; struct routing_table * t = list_entry(p, struct routing_table, next); @@ -475,7 +475,7 @@ static void * lsupdate(void * o) adj->src, adj->dst); if (graph_del_edge(ls.graph, adj->src, adj->dst)) - log_dbg("Failed to delete edge."); + log_err("Failed to del edge."); free(adj); continue; } diff --git a/src/ipcpd/normal/pol/tests/graph_test.c b/src/ipcpd/normal/pol/tests/graph_test.c index 0baba6fc..42cf3f06 100644 --- a/src/ipcpd/normal/pol/tests/graph_test.c +++ b/src/ipcpd/normal/pol/tests/graph_test.c @@ -44,9 +44,8 @@ int graph_test_entries(int entries) return -1; } - list_for_each(p, &table) { + list_for_each(p, &table) i++; - } if (i != entries) { printf("Wrong number of entries.\n"); @@ -69,9 +68,8 @@ int graph_test_double_link(void) return -1; } - list_for_each(p, &table) { + list_for_each(p, &table) i++; - } if (i != 2) { printf("Wrong number of entries.\n"); @@ -108,9 +106,8 @@ int graph_test_single_link(void) return -1; } - list_for_each(p, &table) { + list_for_each(p, &table) i++; - } if (i != 1) { printf("Wrong number of entries.\n"); @@ -168,6 +165,12 @@ int graph_test(int argc, return -1; } + if (graph_update_edge(graph, 2, 1, qs)) { + printf("Failed to add edge.\n"); + graph_destroy(graph); + return -1; + } + if (graph_test_single_link()) { graph_destroy(graph); return -1; @@ -179,6 +182,13 @@ int graph_test(int argc, return -1; } + if (graph_update_edge(graph, 3, 2, qs)) { + printf("Failed to add edge.\n"); + graph_destroy(graph); + return -1; + } + + if (graph_test_double_link()) { graph_destroy(graph); return -1; @@ -190,13 +200,21 @@ int graph_test(int argc, return -1; } + if (graph_del_edge(graph, 3, 2)) { + printf("Failed to delete edge.\n"); + graph_destroy(graph); + return -1; + } + if (graph_test_single_link()) { graph_destroy(graph); return -1; } graph_update_edge(graph, 2, 3, qs); + graph_update_edge(graph, 3, 2, qs); graph_update_edge(graph, 1, 3, qs); + graph_update_edge(graph, 3, 1, qs); if (graph_test_entries(2)) { graph_destroy(graph); @@ -204,7 +222,9 @@ int graph_test(int argc, } graph_update_edge(graph, 3, 4, qs); + graph_update_edge(graph, 4, 3, qs); graph_update_edge(graph, 4, 5, qs); + graph_update_edge(graph, 5, 4, qs); if (graph_test_entries(4)) { graph_destroy(graph); @@ -212,8 +232,11 @@ int graph_test(int argc, } graph_update_edge(graph, 2, 6, qs); + graph_update_edge(graph, 6, 2, qs); graph_update_edge(graph, 6, 7, qs); + graph_update_edge(graph, 7, 6, qs); graph_update_edge(graph, 3, 7, qs); + graph_update_edge(graph, 7, 3, qs); if (graph_test_entries(6)) { graph_destroy(graph); -- cgit v1.2.3