From e245a809296dad1ea22956f015751cc172a44ad2 Mon Sep 17 00:00:00 2001 From: Sander Vrijders Date: Mon, 25 Sep 2017 14:26:26 +0200 Subject: ipcpd: normal: Return list as routing table This returns a list as routing table instead of a pointer to a pointer to a pointer, which simplifies the looping through the routing table and makes it more extensible for future additions. --- src/ipcpd/normal/pol/graph.c | 114 ++++++++++++++++++---------- src/ipcpd/normal/pol/graph.h | 19 +++-- src/ipcpd/normal/pol/link_state.c | 40 ++++++---- src/ipcpd/normal/pol/tests/graph_test.c | 130 ++++++++++++++++++++------------ 4 files changed, 197 insertions(+), 106 deletions(-) (limited to 'src') diff --git a/src/ipcpd/normal/pol/graph.c b/src/ipcpd/normal/pol/graph.c index 9901fbaa..80a7de6f 100644 --- a/src/ipcpd/normal/pol/graph.c +++ b/src/ipcpd/normal/pol/graph.c @@ -438,40 +438,64 @@ static struct vertex ** dijkstra(struct graph * graph, return prev; } -ssize_t graph_routing_table(struct graph * graph, - uint64_t s_addr, - struct routing_table *** table) +static void free_routing_table(struct list_head * table) { - struct vertex ** prevs; - struct list_head * p = NULL; - int i = 0; - int index = 0; - int j = 0; - int k = 0; - struct vertex * prev; - struct vertex * nhop; - struct vertex * v; + struct list_head * h; + struct list_head * p; + struct list_head * q; + struct list_head * i; + + list_for_each_safe(p, h, table) { + struct routing_table * t = + list_entry(p, struct routing_table, next); + list_for_each_safe(q, i, &t->nhops) { + struct nhop * n = + list_entry(q, struct nhop, next); + list_del(&n->next); + free(n); + } + list_del(&t->next); + free(t); + } +} + +void graph_free_routing_table(struct graph * graph, + struct list_head * table) +{ + assert(table); + + pthread_mutex_lock(&graph->lock); + + free_routing_table(table); + + pthread_mutex_unlock(&graph->lock); +} + +int graph_routing_table(struct graph * graph, + uint64_t s_addr, + struct list_head * table) +{ + struct vertex ** prevs; + struct list_head * p; + int i = 0; + int index = 0; + struct vertex * prev; + struct vertex * nhop; + struct vertex * v; + struct routing_table * t; + struct nhop * n; pthread_mutex_lock(&graph->lock); /* We need at least 2 vertices for a table */ - if (graph->nr_vertices < 2) { - pthread_mutex_unlock(&graph->lock); - return -1; - } + if (graph->nr_vertices < 2) + goto fail_vertices; prevs = dijkstra(graph, s_addr); - if (prevs == NULL) { - pthread_mutex_unlock(&graph->lock); - return -1; - } + if (prevs == NULL) + goto fail_vertices; - *table = malloc(sizeof(**table) * (graph->nr_vertices - 1)); - if (*table == NULL) { - pthread_mutex_unlock(&graph->lock); - free(prevs); - return -1; - } + list_head_init(table); /* * Now loop through the list of predecessors @@ -495,19 +519,22 @@ ssize_t graph_routing_table(struct graph * graph, index = get_vertex_index(graph, prev); } - (*table)[j] = malloc(sizeof(***table)); - if ((*table)[j] == NULL) { - pthread_mutex_unlock(&graph->lock); - for (k = 0; k < j; ++k) - free((*table)[k]); - free(*table); - free(prevs); - return -1; - } + t = malloc(sizeof(*t)); + if (t == NULL) + goto fail_t; + + list_head_init(&t->nhops); + + n = malloc(sizeof(*n)); + if (n == NULL) + goto fail_n; + + t->dst = v->addr; + n->nhop = nhop->addr; + + list_add(&n->next, &t->nhops); + list_add(&t->next, table); - (*table)[j]->dst = v->addr; - (*table)[j]->nhop = nhop->addr; - j++; i++; } @@ -515,5 +542,14 @@ ssize_t graph_routing_table(struct graph * graph, free(prevs); - return j; + return 0; + + fail_n: + free(t); + fail_t: + free_routing_table(table); + free(prevs); + fail_vertices: + pthread_mutex_unlock(&graph->lock); + return -1; } diff --git a/src/ipcpd/normal/pol/graph.h b/src/ipcpd/normal/pol/graph.h index 8d092524..7340ecb9 100644 --- a/src/ipcpd/normal/pol/graph.h +++ b/src/ipcpd/normal/pol/graph.h @@ -28,9 +28,15 @@ #include +struct nhop { + struct list_head next; + uint64_t nhop; +}; + struct routing_table { - uint64_t dst; - uint64_t nhop; + struct list_head next; + uint64_t dst; + struct list_head nhops; }; struct graph * graph_create(void); @@ -46,8 +52,11 @@ int graph_del_edge(struct graph * graph, uint64_t s_addr, uint64_t d_addr); -ssize_t graph_routing_table(struct graph * graph, - uint64_t s_addr, - struct routing_table *** table); +int graph_routing_table(struct graph * graph, + uint64_t s_addr, + struct list_head * table); + +void graph_free_routing_table(struct graph * graph, + struct list_head * table); #endif /* OUROBOROS_IPCPD_NORMAL_GRAPH_H */ diff --git a/src/ipcpd/normal/pol/link_state.c b/src/ipcpd/normal/pol/link_state.c index 26370682..ca837cc1 100644 --- a/src/ipcpd/normal/pol/link_state.c +++ b/src/ipcpd/normal/pol/link_state.c @@ -378,19 +378,18 @@ static int nbr_to_fd(uint64_t addr) static void * calculate_pff(void * o) { - struct routing_i * instance; - struct routing_table ** table; - ssize_t n_table; - int i; - int fd; + struct routing_i * instance; + int i; + int fd; + struct list_head table; + struct list_head * p; + struct list_head * q; + int fds[1024]; instance = (struct routing_i *) o; while (true) { - table = NULL; - n_table = graph_routing_table(ls.graph, - ipcpi.dt_addr, &table); - if (n_table < 0) { + if (graph_routing_table(ls.graph, ipcpi.dt_addr, &table)) { sleep(RECALC_TIME); continue; } @@ -399,17 +398,28 @@ static void * calculate_pff(void * o) pff_flush(instance->pff); - for (i = 0; i < n_table; i++) { - fd = nbr_to_fd(table[i]->nhop); - if (fd == -1) - continue; + list_for_each(p, &table) { + struct routing_table * t = + list_entry(p, struct routing_table, next); + + list_for_each(q, &t->nhops) { + struct nhop * n = + list_entry(q, struct nhop, next); + + fd = nbr_to_fd(n->nhop); + if (fd == -1) + continue; - pff_add(instance->pff, table[i]->dst, &fd, 1); + fds[i++] = fd; + } + + pff_add(instance->pff, t->dst, fds, i); } pff_unlock(instance->pff); - freepp(struct routing_table, table, n_table); + graph_free_routing_table(ls.graph, &table); + sleep(RECALC_TIME); } diff --git a/src/ipcpd/normal/pol/tests/graph_test.c b/src/ipcpd/normal/pol/tests/graph_test.c index 87574187..0baba6fc 100644 --- a/src/ipcpd/normal/pol/tests/graph_test.c +++ b/src/ipcpd/normal/pol/tests/graph_test.c @@ -30,80 +30,108 @@ #include "graph.c" -struct graph * graph; -struct routing_table ** table; -ssize_t n_table; -qosspec_t qs; +struct graph * graph; +struct list_head table; +qosspec_t qs; int graph_test_entries(int entries) { - n_table = graph_routing_table(graph, 1, &table); + struct list_head * p; + int i = 0; - if (n_table != entries) { + if (graph_routing_table(graph, 1, &table)) { + printf("Failed to get routing table.\n"); + return -1; + } + + list_for_each(p, &table) { + i++; + } + + if (i != entries) { printf("Wrong number of entries.\n"); - freepp(struct routing_table, table, n_table); + graph_free_routing_table(graph, &table); return -1; } - freepp(struct routing_table, table, n_table); + graph_free_routing_table(graph, &table); return 0; } int graph_test_double_link(void) { - n_table = graph_routing_table(graph, 1, &table); - if (n_table < 0 || table == NULL) { + struct list_head * p; + int i = 0; + + if (graph_routing_table(graph, 1, &table)) { printf("Failed to get routing table.\n"); return -1; } - if (n_table != 2) { - printf("Wrong number of entries.\n"); - freepp(struct routing_table, table, n_table); - return -1; + list_for_each(p, &table) { + i++; } - if ((table[0]->dst != 2 && table[0]->nhop != 2) || - (table[0]->dst != 3 && table[0]->nhop != 2)) { - printf("Wrong routing entry.\n"); - freepp(struct routing_table, table, n_table); + if (i != 2) { + printf("Wrong number of entries.\n"); + graph_free_routing_table(graph, &table); return -1; } - if ((table[1]->dst != 2 && table[1]->nhop != 2) || - (table[0]->dst != 3 && table[0]->nhop != 2)) { - printf("Wrong routing entry.\n"); - freepp(struct routing_table, table, n_table); - return -1; + list_for_each(p, &table) { + struct routing_table * t = + list_entry(p, struct routing_table, next); + struct nhop * n = + list_first_entry(&t->nhops, struct nhop, next); + + if ((t->dst != 2 && n->nhop != 2) || + (t->dst != 3 && n->nhop != 2)) { + printf("Wrong routing entry.\n"); + graph_free_routing_table(graph, &table); + return -1; + } } - freepp(struct routing_table, table, n_table); + graph_free_routing_table(graph, &table); return 0; } int graph_test_single_link(void) { - n_table = graph_routing_table(graph, 1, &table); - if (n_table < 0 || table == NULL) { + struct list_head * p; + int i = 0; + + if (graph_routing_table(graph, 1, &table)) { printf("Failed to get routing table.\n"); return -1; } - if (n_table != 1) { + list_for_each(p, &table) { + i++; + } + + if (i != 1) { printf("Wrong number of entries.\n"); - freepp(struct routing_table, table, n_table); + graph_free_routing_table(graph, &table); return -1; } - if (table[0]->dst != 2 && table[0]->nhop != 2) { - printf("Wrong routing entry.\n"); - freepp(struct routing_table, table, n_table); - return -1; + list_for_each(p, &table) { + struct routing_table * t = + list_entry(p, struct routing_table, next); + struct nhop * n = + list_first_entry(&t->nhops, struct nhop, next); + + if (t->dst != 2 && n->nhop != 2) { + printf("Wrong routing entry.\n"); + graph_free_routing_table(graph, &table); + return -1; + } } - freepp(struct routing_table, table, n_table); + graph_free_routing_table(graph, &table); return 0; } @@ -111,9 +139,9 @@ int graph_test_single_link(void) int graph_test(int argc, char ** argv) { - int i; - int nhop; - int dst; + int nhop; + int dst; + struct list_head * p; (void) argc; (void) argv; @@ -192,50 +220,58 @@ int graph_test(int argc, return -1; } - n_table = graph_routing_table(graph, 1, &table); + if (graph_routing_table(graph, 1, &table)) { + printf("Failed to get routing table.\n"); + return -1; + } + + list_for_each(p, &table) { + struct routing_table * t = + list_entry(p, struct routing_table, next); + struct nhop * n = + list_first_entry(&t->nhops, struct nhop, next); - for (i = 0; i < 6; i++) { - nhop = table[i]->nhop; - dst = table[i]->dst; + dst = t->dst; + nhop = n->nhop; if (dst == 3 && nhop != 3) { printf("Wrong entry."); - freepp(struct routing_table, table, n_table); + graph_free_routing_table(graph, &table); return -1; } if (dst == 2 && nhop != 2) { printf("Wrong entry."); - freepp(struct routing_table, table, n_table); + graph_free_routing_table(graph, &table); return -1; } if (dst == 6 && nhop != 2) { printf("Wrong entry."); - freepp(struct routing_table, table, n_table); + graph_free_routing_table(graph, &table); return -1; } if (dst == 4 && nhop != 3) { printf("Wrong entry."); - freepp(struct routing_table, table, n_table); + graph_free_routing_table(graph, &table); return -1; } if (dst == 5 && nhop != 3) { printf("Wrong entry."); - freepp(struct routing_table, table, n_table); + graph_free_routing_table(graph, &table); return -1; } if (dst == 7 && nhop != 3) { printf("Wrong entry."); - freepp(struct routing_table, table, n_table); + graph_free_routing_table(graph, &table); return -1; } } - freepp(struct routing_table, table, n_table); + graph_free_routing_table(graph, &table); return 0; } -- cgit v1.2.3 From 52bf8c03179fe63724cb632e7f38f8867b564c26 Mon Sep 17 00:00:00 2001 From: Sander Vrijders Date: Mon, 25 Sep 2017 14:51:23 +0200 Subject: ipcpd: normal: Simplify internal graph functions This simplifies several internal graph functions by passing an array of bools instead of an array of vertices. --- src/ipcpd/normal/pol/graph.c | 64 ++++++++++++++++++-------------------------- 1 file changed, 26 insertions(+), 38 deletions(-) (limited to 'src') diff --git a/src/ipcpd/normal/pol/graph.c b/src/ipcpd/normal/pol/graph.c index 80a7de6f..422977cd 100644 --- a/src/ipcpd/normal/pol/graph.c +++ b/src/ipcpd/normal/pol/graph.c @@ -119,6 +119,7 @@ static struct vertex * add_vertex(struct graph * graph, list_head_init(&vertex->edges); vertex->addr = addr; + /* Keep them ordered on address. */ list_for_each(p, &graph->vertices) { struct vertex * v = list_entry(p, struct vertex, next); if (v->addr > addr) @@ -319,59 +320,48 @@ int graph_del_edge(struct graph * graph, return 0; } -static int get_min_vertex(struct vertex ** vertices, - int nr_vertices, +static int get_min_vertex(struct graph * graph, int * dist, + bool * used, struct vertex ** v) { - int min = INT_MAX; - int index = -1; - int i; + int min = INT_MAX; + int index = -1; + int i = 0; + struct list_head * p = NULL; *v = NULL; - for (i = 0; i < nr_vertices; i++) { - if (vertices[i] == NULL) + list_for_each(p, &graph->vertices) { + if (used[i] == true) { + i++; continue; + } if (dist[i] < min) { - *v = vertices[i]; min = dist[i]; index = i; + *v = list_entry(p, struct vertex, next); } + + i++; } if (index != -1) - vertices[index] = NULL; + used[index] = true; return index; } -static int get_vertex_number(struct vertex ** vertices, - int nr_vertices, - struct vertex * v) +static int get_vertex_number(struct graph * graph, + struct vertex * v) { - int i; - - for (i = 0; i < nr_vertices; i++) { - if (vertices[i] == v) - return i; - } - - return -1; -} - -static int get_vertex_index(struct graph * graph, - struct vertex * v) - -{ - struct list_head * p = NULL; - struct vertex * vertex; int i = 0; + struct list_head * p = NULL; list_for_each(p, &graph->vertices) { - vertex = list_entry(p, struct vertex, next); + struct vertex * vertex = list_entry(p, struct vertex, next); if (vertex == v) return i; i++; @@ -384,7 +374,7 @@ static struct vertex ** dijkstra(struct graph * graph, uint64_t src) { int dist[graph->nr_vertices]; - struct vertex * vertices[graph->nr_vertices]; + bool used[graph->nr_vertices]; struct list_head * p = NULL; int i = 0; int j = 0; @@ -400,24 +390,22 @@ static struct vertex ** dijkstra(struct graph * graph, /* Init the data structures */ list_for_each(p, &graph->vertices) { v = list_entry(p, struct vertex, next); - vertices[i] = v; if (v->addr == src) dist[i] = 0; else dist[i] = INT_MAX; prev[i] = NULL; + used[i] = false; i++; } /* Perform actual Dijkstra */ - i = get_min_vertex(vertices, graph->nr_vertices, dist, &v); + i = get_min_vertex(graph, dist, used, &v); while (v != NULL) { list_for_each(p, &v->edges) { e = list_entry(p, struct edge, next); - j = get_vertex_number(vertices, - graph->nr_vertices, - e->nb); + j = get_vertex_number(graph, e->nb); if (j == -1) continue; @@ -432,7 +420,7 @@ static struct vertex ** dijkstra(struct graph * graph, prev[j] = v; } } - i = get_min_vertex(vertices, graph->nr_vertices, dist, &v); + i = get_min_vertex(graph, dist, used, &v); } return prev; @@ -512,11 +500,11 @@ int graph_routing_table(struct graph * graph, continue; } - index = get_vertex_index(graph, prev); + index = get_vertex_number(graph, prev); while (prevs[index] != NULL) { nhop = prev; prev = prevs[index]; - index = get_vertex_index(graph, prev); + index = get_vertex_number(graph, prev); } t = malloc(sizeof(*t)); -- cgit v1.2.3 From 3074adc1615517150568d396d629175932a08a52 Mon Sep 17 00:00:00 2001 From: Sander Vrijders Date: Mon, 25 Sep 2017 15:12:43 +0200 Subject: ipcpd: normal: Simplify Dijkstra implementation This simplifies the Dijkstra implementation by immediately setting the correct next hop during Dijkstra instead of looping through the list of predecessors afterwards. --- src/ipcpd/normal/pol/graph.c | 42 +++++++++++++++++------------------------- 1 file changed, 17 insertions(+), 25 deletions(-) (limited to 'src') diff --git a/src/ipcpd/normal/pol/graph.c b/src/ipcpd/normal/pol/graph.c index 422977cd..1a6ad2b3 100644 --- a/src/ipcpd/normal/pol/graph.c +++ b/src/ipcpd/normal/pol/graph.c @@ -381,10 +381,10 @@ static struct vertex ** dijkstra(struct graph * graph, struct vertex * v = NULL; struct edge * e = NULL; int alt; - struct vertex ** prev; + struct vertex ** nhop; - prev = malloc(sizeof(*prev) * graph->nr_vertices); - if (prev == NULL) + nhop = malloc(sizeof(*nhop) * graph->nr_vertices); + if (nhop == NULL) return NULL; /* Init the data structures */ @@ -394,7 +394,8 @@ static struct vertex ** dijkstra(struct graph * graph, dist[i] = 0; else dist[i] = INT_MAX; - prev[i] = NULL; + + nhop[i] = NULL; used[i] = false; i++; } @@ -417,13 +418,16 @@ static struct vertex ** dijkstra(struct graph * graph, alt = dist[i] + 1; if (alt < dist[j]) { dist[j] = alt; - prev[j] = v; + if (v->addr == src) + nhop[j] = e->nb; + else + nhop[j] = nhop[i]; } } i = get_min_vertex(graph, dist, used, &v); } - return prev; + return nhop; } static void free_routing_table(struct list_head * table) @@ -463,12 +467,9 @@ int graph_routing_table(struct graph * graph, uint64_t s_addr, struct list_head * table) { - struct vertex ** prevs; + struct vertex ** nhops; struct list_head * p; int i = 0; - int index = 0; - struct vertex * prev; - struct vertex * nhop; struct vertex * v; struct routing_table * t; struct nhop * n; @@ -479,8 +480,8 @@ int graph_routing_table(struct graph * graph, if (graph->nr_vertices < 2) goto fail_vertices; - prevs = dijkstra(graph, s_addr); - if (prevs == NULL) + nhops = dijkstra(graph, s_addr); + if (nhops == NULL) goto fail_vertices; list_head_init(table); @@ -491,22 +492,13 @@ int graph_routing_table(struct graph * graph, */ list_for_each(p, &graph->vertices) { v = list_entry(p, struct vertex, next); - prev = prevs[i]; - nhop = v; /* This is the src */ - if (prev == NULL) { + if (nhops[i] == NULL) { i++; continue; } - index = get_vertex_number(graph, prev); - while (prevs[index] != NULL) { - nhop = prev; - prev = prevs[index]; - index = get_vertex_number(graph, prev); - } - t = malloc(sizeof(*t)); if (t == NULL) goto fail_t; @@ -518,7 +510,7 @@ int graph_routing_table(struct graph * graph, goto fail_n; t->dst = v->addr; - n->nhop = nhop->addr; + n->nhop = nhops[i]->addr; list_add(&n->next, &t->nhops); list_add(&t->next, table); @@ -528,7 +520,7 @@ int graph_routing_table(struct graph * graph, pthread_mutex_unlock(&graph->lock); - free(prevs); + free(nhops); return 0; @@ -536,7 +528,7 @@ int graph_routing_table(struct graph * graph, free(t); fail_t: free_routing_table(table); - free(prevs); + free(nhops); fail_vertices: pthread_mutex_unlock(&graph->lock); return -1; -- cgit v1.2.3 From 0847da715c82d49b01758d88ecca496eba2c8d34 Mon Sep 17 00:00:00 2001 From: Sander Vrijders Date: Mon, 25 Sep 2017 15:31:20 +0200 Subject: ipcpd: normal: Keep index in vertex struct This keeps the index in the vertex struct so that is more easily available during Dijkstra. --- src/ipcpd/normal/pol/graph.c | 49 ++++++++++++++++++--------------------- src/ipcpd/normal/pol/link_state.c | 2 +- 2 files changed, 24 insertions(+), 27 deletions(-) (limited to 'src') diff --git a/src/ipcpd/normal/pol/graph.c b/src/ipcpd/normal/pol/graph.c index 1a6ad2b3..27c5cfca 100644 --- a/src/ipcpd/normal/pol/graph.c +++ b/src/ipcpd/normal/pol/graph.c @@ -46,6 +46,7 @@ struct vertex { struct list_head next; uint64_t addr; struct list_head edges; + int index; }; struct graph { @@ -110,6 +111,7 @@ static struct vertex * add_vertex(struct graph * graph, { struct vertex * vertex; struct list_head * p; + int i = 0; vertex = malloc(sizeof(*vertex)); if (vertex == NULL) @@ -124,10 +126,20 @@ static struct vertex * add_vertex(struct graph * graph, struct vertex * v = list_entry(p, struct vertex, next); if (v->addr > addr) break; + i++; } + vertex->index = i; + list_add_tail(&vertex->next, p); + /* Increase the index of the vertices to the right. */ + list_for_each(p, &graph->vertices) { + struct vertex * v = list_entry(p, struct vertex, next); + if (v->addr > addr) + v->index++; + } + graph->nr_vertices++; return vertex; @@ -141,6 +153,13 @@ static void del_vertex(struct graph * graph, list_del(&vertex->next); + /* Decrease the index of the vertices to the right. */ + list_for_each(p, &graph->vertices) { + struct vertex * v = list_entry(p, struct vertex, next); + if (v->addr > vertex->addr) + v->index--; + } + list_for_each_safe(p, n, &vertex->edges) { struct edge * e = list_entry(p, struct edge, next); del_edge(e); @@ -353,23 +372,6 @@ static int get_min_vertex(struct graph * graph, return index; } -static int get_vertex_number(struct graph * graph, - struct vertex * v) - -{ - int i = 0; - struct list_head * p = NULL; - - list_for_each(p, &graph->vertices) { - struct vertex * vertex = list_entry(p, struct vertex, next); - if (vertex == v) - return i; - i++; - } - - return -1; -} - static struct vertex ** dijkstra(struct graph * graph, uint64_t src) { @@ -377,7 +379,6 @@ static struct vertex ** dijkstra(struct graph * graph, bool used[graph->nr_vertices]; struct list_head * p = NULL; int i = 0; - int j = 0; struct vertex * v = NULL; struct edge * e = NULL; int alt; @@ -406,22 +407,18 @@ static struct vertex ** dijkstra(struct graph * graph, list_for_each(p, &v->edges) { e = list_entry(p, struct edge, next); - j = get_vertex_number(graph, e->nb); - if (j == -1) - continue; - /* * NOTE: Current weight is just hop count. * Method could be extended to use a different * weight for a different QoS cube. */ alt = dist[i] + 1; - if (alt < dist[j]) { - dist[j] = alt; + if (alt < dist[e->nb->index]) { + dist[e->nb->index] = alt; if (v->addr == src) - nhop[j] = e->nb; + nhop[e->nb->index] = e->nb; else - nhop[j] = nhop[i]; + nhop[e->nb->index] = nhop[i]; } } i = get_min_vertex(graph, dist, used, &v); diff --git a/src/ipcpd/normal/pol/link_state.c b/src/ipcpd/normal/pol/link_state.c index ca837cc1..d45dae15 100644 --- a/src/ipcpd/normal/pol/link_state.c +++ b/src/ipcpd/normal/pol/link_state.c @@ -379,7 +379,7 @@ static int nbr_to_fd(uint64_t addr) static void * calculate_pff(void * o) { struct routing_i * instance; - int i; + int i = 0; int fd; struct list_head table; struct list_head * p; -- cgit v1.2.3 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(-) (limited to 'src') 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