diff options
Diffstat (limited to 'src/ipcpd/unicast/routing')
| -rw-r--r-- | src/ipcpd/unicast/routing/graph.c | 84 | ||||
| -rw-r--r-- | src/ipcpd/unicast/routing/graph.h | 2 | ||||
| -rw-r--r-- | src/ipcpd/unicast/routing/link-state.c | 88 | ||||
| -rw-r--r-- | src/ipcpd/unicast/routing/link-state.h | 2 | ||||
| -rw-r--r-- | src/ipcpd/unicast/routing/ops.h | 2 | ||||
| -rw-r--r-- | src/ipcpd/unicast/routing/pol.h | 2 | ||||
| -rw-r--r-- | src/ipcpd/unicast/routing/tests/CMakeLists.txt | 38 | ||||
| -rw-r--r-- | src/ipcpd/unicast/routing/tests/graph_test.c | 2 |
8 files changed, 96 insertions, 124 deletions
diff --git a/src/ipcpd/unicast/routing/graph.c b/src/ipcpd/unicast/routing/graph.c index 32442dad..0226c762 100644 --- a/src/ipcpd/unicast/routing/graph.c +++ b/src/ipcpd/unicast/routing/graph.c @@ -1,5 +1,5 @@ /* - * Ouroboros - Copyright (C) 2016 - 2024 + * Ouroboros - Copyright (C) 2016 - 2026 * * Undirected graph structure * @@ -57,10 +57,7 @@ struct edge { }; struct graph { - struct { - struct list_head list; - size_t len; - } vertices; + struct llist vertices; pthread_mutex_t lock; }; @@ -88,7 +85,7 @@ static struct vertex * find_vertex_by_addr(struct graph * graph, assert(graph); - list_for_each(p, &graph->vertices.list) { + llist_for_each(p, &graph->vertices) { struct vertex * e = list_entry(p, struct vertex, next); if (e->addr == addr) return e; @@ -142,7 +139,7 @@ static struct vertex * add_vertex(struct graph * graph, vertex->addr = addr; /* Keep them ordered on address. */ - list_for_each(p, &graph->vertices.list) { + llist_for_each(p, &graph->vertices) { struct vertex * v = list_entry(p, struct vertex, next); if (v->addr > addr) break; @@ -151,7 +148,7 @@ static struct vertex * add_vertex(struct graph * graph, vertex->index = i; - list_add_tail(&vertex->next, p); + llist_add_tail_at(&vertex->next, p, &graph->vertices); /* Increase the index of the vertices to the right. */ list_for_each(p, &vertex->next) { @@ -160,37 +157,41 @@ static struct vertex * add_vertex(struct graph * graph, v->index++; } - ++graph->vertices.len; - return vertex; } +static void free_edges(struct list_head * edges) +{ + struct list_head * p; + struct list_head * h; + + list_for_each_safe(p, h, edges) { + struct edge * e = list_entry(p, struct edge, next); + list_del(&e->next); + free(e); + } +} + static void del_vertex(struct graph * graph, struct vertex * vertex) { struct list_head * p; - struct list_head * h; assert(graph != NULL); assert(vertex != NULL); - list_del(&vertex->next); + llist_del(&vertex->next, &graph->vertices); /* Decrease the index of the vertices to the right. */ - list_for_each(p, &graph->vertices.list) { + llist_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, h, &vertex->edges) { - struct edge * e = list_entry(p, struct edge, next); - del_edge(e); - } + free_edges(&vertex->edges); free(vertex); - - --graph->vertices.len; } struct graph * graph_create(void) @@ -206,8 +207,7 @@ struct graph * graph_create(void) return NULL; } - graph->vertices.len = 0; - list_head_init(&graph->vertices.list); + llist_init(&graph->vertices); return graph; } @@ -221,7 +221,7 @@ void graph_destroy(struct graph * graph) pthread_mutex_lock(&graph->lock); - list_for_each_safe(p, n, &graph->vertices.list) { + llist_for_each_safe(p, n, &graph->vertices) { struct vertex * e = list_entry(p, struct vertex, next); del_vertex(graph, e); } @@ -230,7 +230,7 @@ void graph_destroy(struct graph * graph) pthread_mutex_destroy(&graph->lock); - assert(graph->vertices.len == 0); + assert(llist_is_empty(&graph->vertices)); free(graph); } @@ -371,7 +371,7 @@ static int get_min_vertex(struct graph * graph, *v = NULL; - list_for_each(p, &graph->vertices.list) { + llist_for_each(p, &graph->vertices) { if (!used[i] && dist[i] < min) { min = dist[i]; index = i; @@ -420,7 +420,7 @@ static int dijkstra(struct graph * graph, memset(*nhops, 0, sizeof(**nhops) * graph->vertices.len); memset(*dist, 0, sizeof(**dist) * graph->vertices.len); - list_for_each(p, &graph->vertices.list) { + llist_for_each(p, &graph->vertices) { v = list_entry(p, struct vertex, next); (*dist)[i++] = (v->addr == src) ? 0 : INT_MAX; } @@ -526,7 +526,7 @@ static int graph_routing_table_simple(struct graph * graph, list_head_init(table); /* Now construct the routing table from the nhops. */ - list_for_each(p, &graph->vertices.list) { + llist_for_each(p, &graph->vertices) { v = list_entry(p, struct vertex, next); /* This is the src */ @@ -624,7 +624,7 @@ static int graph_routing_table_lfa(struct graph * graph, addrs[j] = -1; } - list_for_each(p, &graph->vertices.list) { + llist_for_each(p, &graph->vertices) { v = list_entry(p, struct vertex, next); if (v->addr != s_addr) @@ -650,7 +650,7 @@ static int graph_routing_table_lfa(struct graph * graph, } /* Loop though all nodes to see if we have a LFA for them. */ - list_for_each(p, &graph->vertices.list) { + llist_for_each(p, &graph->vertices) { v = list_entry(p, struct vertex, next); if (v->addr == s_addr) @@ -695,7 +695,6 @@ static int graph_routing_table_ecmp(struct graph * graph, { struct vertex ** nhops; struct list_head * p; - struct list_head * h; size_t i; struct vertex * v; struct vertex * src_v; @@ -735,16 +734,15 @@ static int graph_routing_table_ecmp(struct graph * graph, free(nhops); - list_for_each(h, &graph->vertices.list) { - v = list_entry(h, struct vertex, next); - if (tmp_dist[v->index] + 1 == (*dist)[v->index]) { + for (i = 0; i < graph->vertices.len; ++i) { + if (tmp_dist[i] + 1 == (*dist)[i]) { n = malloc(sizeof(*n)); if (n == NULL) { free(tmp_dist); goto fail_src_v; } n->nhop = e->nb->addr; - list_add_tail(&n->next, &forwarding[v->index]); + list_add_tail(&n->next, &forwarding[i]); } } @@ -753,38 +751,34 @@ static int graph_routing_table_ecmp(struct graph * graph, list_head_init(table); i = 0; - list_for_each(p, &graph->vertices.list) { + llist_for_each(p, &graph->vertices) { v = list_entry(p, struct vertex, next); - if (v->addr == s_addr) { + if (v->addr == s_addr || list_is_empty(&forwarding[i])) { ++i; continue; } t = malloc(sizeof(*t)); if (t == NULL) - goto fail_t; + goto fail_malloc; t->dst = v->addr; list_head_init(&t->nhops); - if (&forwarding[i] != forwarding[i].nxt) { - t->nhops.nxt = forwarding[i].nxt; - t->nhops.prv = forwarding[i].prv; - forwarding[i].prv->nxt = &t->nhops; - forwarding[i].nxt->prv = &t->nhops; - } + t->nhops.nxt = forwarding[i].nxt; + t->nhops.prv = forwarding[i].prv; + forwarding[i].prv->nxt = &t->nhops; + forwarding[i].nxt->prv = &t->nhops; list_add(&t->next, table); ++i; } - free(*dist); - *dist = NULL; free(forwarding); return 0; - fail_t: + fail_malloc: free_routing_table(table); fail_src_v: free(*dist); diff --git a/src/ipcpd/unicast/routing/graph.h b/src/ipcpd/unicast/routing/graph.h index 8190cc6c..f3766771 100644 --- a/src/ipcpd/unicast/routing/graph.h +++ b/src/ipcpd/unicast/routing/graph.h @@ -1,5 +1,5 @@ /* - * Ouroboros - Copyright (C) 2016 - 2024 + * Ouroboros - Copyright (C) 2016 - 2026 * * Undirected graph structure * diff --git a/src/ipcpd/unicast/routing/link-state.c b/src/ipcpd/unicast/routing/link-state.c index e5edf539..051dd98d 100644 --- a/src/ipcpd/unicast/routing/link-state.c +++ b/src/ipcpd/unicast/routing/link-state.c @@ -1,5 +1,5 @@ /* - * Ouroboros - Copyright (C) 2016 - 2024 + * Ouroboros - Copyright (C) 2016 - 2026 * * Link state routing policy * @@ -56,7 +56,7 @@ #include <string.h> #define LS_ENTRY_SIZE 104 -#define LSDB "lsdb" +#define lsdb "lsdb" #ifndef CLOCK_REALTIME_COARSE #define CLOCK_REALTIME_COARSE CLOCK_REALTIME @@ -121,16 +121,8 @@ struct { struct graph * graph; struct { - struct { - struct list_head list; - size_t len; - } nbs; - - struct { - struct list_head list; - size_t len; - } db; - + struct llist nbs; + struct llist db; pthread_rwlock_t lock; }; @@ -189,7 +181,7 @@ static struct adjacency * get_adj(const char * path) assert(path); - list_for_each(p, &ls.db.list) { + llist_for_each(p, &ls.db) { struct adjacency * a = list_entry(p, struct adjacency, next); sprintf(entry, LINK_FMT, LINK_VAL(a->src, a->dst)); if (strcmp(entry, path) == 0) @@ -245,7 +237,7 @@ static int lsdb_rib_read(const char * path, pthread_rwlock_rdlock(&ls.lock); - if (ls.db.len + ls.nbs.len == 0) + if (llist_is_empty(&ls.db) && llist_is_empty(&ls.nbs)) goto fail; a = get_adj(entry); @@ -274,7 +266,7 @@ static int lsdb_rib_readdir(char *** buf) pthread_rwlock_rdlock(&ls.lock); - if (ls.db.len + ls.nbs.len == 0) { + if (llist_is_empty(&ls.db) && llist_is_empty(&ls.nbs)) { *buf = NULL; goto no_entries; } @@ -284,7 +276,7 @@ static int lsdb_rib_readdir(char *** buf) if (*buf == NULL) goto fail_entries; - list_for_each(p, &ls.nbs.list) { + llist_for_each(p, &ls.nbs) { struct nb * nb = list_entry(p, struct nb, next); char * str = (nb->type == NB_DT ? ".dt " : ".mgmt "); sprintf(entry, "%s" ADDR_FMT32 , str, ADDR_VAL32(&nb->addr)); @@ -295,7 +287,7 @@ static int lsdb_rib_readdir(char *** buf) strcpy((*buf)[idx++], entry); } - list_for_each(p, &ls.db.list) { + llist_for_each(p, &ls.db) { struct adjacency * a = list_entry(p, struct adjacency, next); sprintf(entry, LINK_FMT, LINK_VAL(a->src, a->dst)); (*buf)[idx] = malloc(strlen(entry) + 1); @@ -333,7 +325,7 @@ static int lsdb_add_nb(uint64_t addr, pthread_rwlock_wrlock(&ls.lock); - list_for_each(p, &ls.nbs.list) { + llist_for_each(p, &ls.nbs) { struct nb * el = list_entry(p, struct nb, next); if (addr > el->addr) break; @@ -360,9 +352,7 @@ static int lsdb_add_nb(uint64_t addr, nb->fd = fd; nb->type = type; - list_add_tail(&nb->next, p); - - ++ls.nbs.len; + llist_add_tail_at(&nb->next, p, &ls.nbs); log_dbg("Type %s neighbor " ADDR_FMT32 " added.", nb->type == NB_DT ? "dt" : "mgmt", ADDR_VAL32(&addr)); @@ -380,13 +370,12 @@ static int lsdb_del_nb(uint64_t addr, pthread_rwlock_wrlock(&ls.lock); - list_for_each_safe(p, h, &ls.nbs.list) { + llist_for_each_safe(p, h, &ls.nbs) { struct nb * nb = list_entry(p, struct nb, next); if (nb->addr != addr || nb->fd != fd) continue; - list_del(&nb->next); - --ls.nbs.len; + llist_del(&nb->next, &ls.nbs); pthread_rwlock_unlock(&ls.lock); log_dbg("Type %s neighbor " ADDR_FMT32 " deleted.", nb->type == NB_DT ? "dt" : "mgmt", ADDR_VAL32(&addr)); @@ -406,7 +395,7 @@ static int nbr_to_fd(uint64_t addr) pthread_rwlock_rdlock(&ls.lock); - list_for_each(p, &ls.nbs.list) { + llist_for_each(p, &ls.nbs) { struct nb * nb = list_entry(p, struct nb, next); if (nb->addr == addr && nb->type == NB_DT) { fd = nb->fd; @@ -494,7 +483,7 @@ static int lsdb_add_link(uint64_t src, pthread_rwlock_wrlock(&ls.lock); - list_for_each(p, &ls.db.list) { + llist_for_each(p, &ls.db) { struct adjacency * a = list_entry(p, struct adjacency, next); if (a->dst == dst && a->src == src) { if (a->seqno < seqno) { @@ -521,9 +510,7 @@ static int lsdb_add_link(uint64_t src, adj->seqno = seqno; adj->stamp = now.tv_sec; - list_add_tail(&adj->next, p); - - ls.db.len++; + llist_add_tail_at(&adj->next, p, &ls.db); if (graph_update_edge(ls.graph, src, dst, *qs)) log_warn("Failed to add edge to graph."); @@ -543,15 +530,13 @@ static int lsdb_del_link(uint64_t src, pthread_rwlock_wrlock(&ls.lock); - list_for_each_safe(p, h, &ls.db.list) { + llist_for_each_safe(p, h, &ls.db) { struct adjacency * a = list_entry(p, struct adjacency, next); if (a->dst == dst && a->src == src) { - list_del(&a->next); + llist_del(&a->next, &ls.db); if (graph_del_edge(ls.graph, src, dst)) log_warn("Failed to delete edge from graph."); - ls.db.len--; - pthread_rwlock_unlock(&ls.lock); set_pff_modified(false); free(a); @@ -599,7 +584,7 @@ static void send_lsm(uint64_t src, lsm.s_addr = hton64(src); lsm.seqno = hton64(seqno); - list_for_each(p, &ls.nbs.list) { + llist_for_each(p, &ls.nbs) { struct nb * nb = list_entry(p, struct nb, next); if (nb->type != NB_MGMT) continue; @@ -628,7 +613,7 @@ static void lsdb_replicate(int fd) /* Lock the lsdb, copy the lsms and send outside of lock. */ pthread_rwlock_rdlock(&ls.lock); - list_for_each(p, &ls.db.list) { + llist_for_each(p, &ls.db) { struct adjacency * adj; struct adjacency * cpy; adj = list_entry(p, struct adjacency, next); @@ -675,11 +660,11 @@ static void * lsupdate(void * o) pthread_cleanup_push(__cleanup_rwlock_unlock, &ls.lock); - list_for_each_safe(p, h, &ls.db.list) { + llist_for_each_safe(p, h, &ls.db) { struct adjacency * adj; adj = list_entry(p, struct adjacency, next); if (now.tv_sec > adj->stamp + ls.conf.t_timeo) { - list_del(&adj->next); + llist_del(&adj->next, &ls.db); log_dbg(LINK_FMT " timed out.", LINK_VAL(adj->src, adj->dst)); if (graph_del_edge(ls.graph, adj->src, @@ -746,7 +731,7 @@ static void forward_lsm(uint8_t * buf, pthread_cleanup_push(__cleanup_rwlock_unlock, &ls.lock); - list_for_each(p, &ls.nbs.list) { + llist_for_each(p, &ls.nbs) { struct nb * nb = list_entry(p, struct nb, next); if (nb->type != NB_MGMT || nb->fd == in_fd) continue; @@ -874,19 +859,19 @@ static void handle_event(void * self, pthread_cleanup_pop(true); if (lsdb_add_nb(c->conn_info.addr, c->flow_info.fd, NB_DT)) - log_dbg("Failed to add neighbor to LSDB."); + log_dbg("Failed to add neighbor to lsdb."); if (lsdb_add_link(ls.addr, c->conn_info.addr, 0, &qs)) - log_dbg("Failed to add new adjacency to LSDB."); + log_dbg("Failed to add new adjacency to lsdb."); break; case NOTIFY_DT_CONN_DEL: flow_event(c->flow_info.fd, false); if (lsdb_del_nb(c->conn_info.addr, c->flow_info.fd)) - log_dbg("Failed to delete neighbor from LSDB."); + log_dbg("Failed to delete neighbor from lsdb."); if (lsdb_del_link(ls.addr, c->conn_info.addr)) - log_dbg("Local link was not in LSDB."); + log_dbg("Local link was not in lsdb."); break; case NOTIFY_DT_CONN_QOS: log_dbg("QoS changes currently unsupported."); @@ -902,14 +887,14 @@ static void handle_event(void * self, fccntl(c->flow_info.fd, FLOWSFLAGS, flags | FLOWFRNOPART); fset_add(ls.mgmt_set, c->flow_info.fd); if (lsdb_add_nb(c->conn_info.addr, c->flow_info.fd, NB_MGMT)) - log_warn("Failed to add mgmt neighbor to LSDB."); + log_warn("Failed to add mgmt neighbor to lsdb."); /* replicate the entire lsdb */ lsdb_replicate(c->flow_info.fd); break; case NOTIFY_MGMT_CONN_DEL: fset_del(ls.mgmt_set, c->flow_info.fd); if (lsdb_del_nb(c->conn_info.addr, c->flow_info.fd)) - log_warn("Failed to delete mgmt neighbor from LSDB."); + log_warn("Failed to delete mgmt neighbor from lsdb."); break; default: break; @@ -1090,16 +1075,13 @@ int link_state_init(struct ls_config * conf, goto fail_fset_create; } - list_head_init(&ls.db.list); - list_head_init(&ls.nbs.list); + llist_init(&ls.db); + llist_init(&ls.nbs); list_head_init(&ls.instances.list); - if (rib_reg(LSDB, &r_ops)) + if (rib_reg(lsdb, &r_ops)) goto fail_rib_reg; - ls.db.len = 0; - ls.nbs.len = 0; - return 0; fail_rib_reg: @@ -1121,7 +1103,7 @@ void link_state_fini(void) struct list_head * p; struct list_head * h; - rib_unreg(LSDB); + rib_unreg(lsdb); fset_destroy(ls.mgmt_set); @@ -1131,9 +1113,9 @@ void link_state_fini(void) pthread_rwlock_wrlock(&ls.lock); - list_for_each_safe(p, h, &ls.db.list) { + llist_for_each_safe(p, h, &ls.db) { struct adjacency * a = list_entry(p, struct adjacency, next); - list_del(&a->next); + llist_del(&a->next, &ls.db); free(a); } diff --git a/src/ipcpd/unicast/routing/link-state.h b/src/ipcpd/unicast/routing/link-state.h index 69eb6781..38e19065 100644 --- a/src/ipcpd/unicast/routing/link-state.h +++ b/src/ipcpd/unicast/routing/link-state.h @@ -1,5 +1,5 @@ /* - * Ouroboros - Copyright (C) 2016 - 2024 + * Ouroboros - Copyright (C) 2016 - 2026 * * Link state routing policy * diff --git a/src/ipcpd/unicast/routing/ops.h b/src/ipcpd/unicast/routing/ops.h index 4bf75c80..b19c5176 100644 --- a/src/ipcpd/unicast/routing/ops.h +++ b/src/ipcpd/unicast/routing/ops.h @@ -1,5 +1,5 @@ /* - * Ouroboros - Copyright (C) 2016 - 2024 + * Ouroboros - Copyright (C) 2016 - 2026 * * Routing policy ops * diff --git a/src/ipcpd/unicast/routing/pol.h b/src/ipcpd/unicast/routing/pol.h index b6a6f150..545f5df2 100644 --- a/src/ipcpd/unicast/routing/pol.h +++ b/src/ipcpd/unicast/routing/pol.h @@ -1,5 +1,5 @@ /* - * Ouroboros - Copyright (C) 2016 - 2024 + * Ouroboros - Copyright (C) 2016 - 2026 * * Routing policies * diff --git a/src/ipcpd/unicast/routing/tests/CMakeLists.txt b/src/ipcpd/unicast/routing/tests/CMakeLists.txt index b5011474..be2de72c 100644 --- a/src/ipcpd/unicast/routing/tests/CMakeLists.txt +++ b/src/ipcpd/unicast/routing/tests/CMakeLists.txt @@ -3,36 +3,32 @@ get_filename_component(CURRENT_SOURCE_PARENT_DIR get_filename_component(CURRENT_BINARY_PARENT_DIR ${CMAKE_CURRENT_BINARY_DIR} DIRECTORY) -include_directories(${CMAKE_CURRENT_SOURCE_DIR}) -include_directories(${CMAKE_CURRENT_BINARY_DIR}) - -include_directories(${CURRENT_SOURCE_PARENT_DIR}) -include_directories(${CURRENT_BINARY_PARENT_DIR}) - -include_directories(${CMAKE_SOURCE_DIR}/include) -include_directories(${CMAKE_BINARY_DIR}/include) - get_filename_component(PARENT_PATH ${CMAKE_CURRENT_SOURCE_DIR} DIRECTORY) get_filename_component(PARENT_DIR ${PARENT_PATH} NAME) +compute_test_prefix() + create_test_sourcelist(${PARENT_DIR}_tests test_suite.c # Add new tests here graph_test.c ) add_executable(${PARENT_DIR}_test ${${PARENT_DIR}_tests}) -target_link_libraries(${PARENT_DIR}_test ouroboros-common) -add_dependencies(check ${PARENT_DIR}_test) +target_include_directories(${PARENT_DIR}_test PRIVATE + ${CMAKE_CURRENT_SOURCE_DIR} + ${CMAKE_CURRENT_BINARY_DIR} + ${CURRENT_SOURCE_PARENT_DIR} + ${CURRENT_BINARY_PARENT_DIR} + ${CMAKE_SOURCE_DIR}/include + ${CMAKE_BINARY_DIR}/include + ${CMAKE_SOURCE_DIR}/src/ipcpd + ${CMAKE_BINARY_DIR}/src/ipcpd +) + +disable_test_logging_for_target(${PARENT_DIR}_test) +target_link_libraries(${PARENT_DIR}_test PRIVATE ouroboros-common) -set(tests_to_run ${${PARENT_DIR}_tests}) -if(CMAKE_VERSION VERSION_LESS "3.29.0") - remove(tests_to_run test_suite.c) -else () - list(POP_FRONT tests_to_run) -endif() +add_dependencies(build_tests ${PARENT_DIR}_test) -foreach (test ${tests_to_run}) - get_filename_component(test_name ${test} NAME_WE) - add_test(${test_name} ${C_TEST_PATH}/${PARENT_DIR}_test ${test_name}) -endforeach (test) +ouroboros_register_tests(TARGET ${PARENT_DIR}_test TESTS ${${PARENT_DIR}_tests}) diff --git a/src/ipcpd/unicast/routing/tests/graph_test.c b/src/ipcpd/unicast/routing/tests/graph_test.c index d805640c..40a744ff 100644 --- a/src/ipcpd/unicast/routing/tests/graph_test.c +++ b/src/ipcpd/unicast/routing/tests/graph_test.c @@ -1,5 +1,5 @@ /* - * Ouroboros - Copyright (C) 2016 - 2024 + * Ouroboros - Copyright (C) 2016 - 2026 * * Test of the graph structure * |
