From e3f696c13851bef313183e59ef7dbc77f67359fd Mon Sep 17 00:00:00 2001 From: Michael Tremer Date: Thu, 3 Oct 2019 15:13:03 +0000 Subject: [PATCH] Implement search through the network tree This could not be implemented as a usual DFS since we cannot simply have a recursive solution here and need to be able to break the search at any time. However, it needs to be tracked where in the graph we are when we are walking through it to extract the informaton encoded into the edges. This is now solved by using a stack that keeps that information as we walk through the graph. This solution uses O(1) in memory since the stack can not be larger than 256 nodes (the maximum path length should be 128). Signed-off-by: Michael Tremer --- src/database.c | 134 +++++++++++++++++++++++++++++++++++++++++++++ src/libloc.sym | 2 + src/loc/database.h | 1 + src/loc/network.h | 1 + src/network.c | 9 +++ 5 files changed, 147 insertions(+) diff --git a/src/database.c b/src/database.c index e8ec9b7..671854e 100644 --- a/src/database.c +++ b/src/database.c @@ -62,6 +62,14 @@ struct loc_database { struct loc_stringpool* pool; }; +#define MAX_STACK_DEPTH 256 + +struct loc_node_stack { + off_t offset; + int i; // Is this node 0 or 1? + int depth; +}; + struct loc_database_enumerator { struct loc_ctx* ctx; struct loc_database* db; @@ -73,6 +81,12 @@ struct loc_database_enumerator { // Index of the AS we are looking at unsigned int as_index; + + // Network state + struct in6_addr network_address; + struct loc_node_stack network_stack[MAX_STACK_DEPTH]; + int network_stack_depth; + unsigned int* networks_visited; }; static int loc_database_read_magic(struct loc_database* db, FILE* f) { @@ -565,6 +579,11 @@ LOC_EXPORT int loc_database_enumerator_new(struct loc_database_enumerator** enum e->db = loc_database_ref(db); e->refcount = 1; + // Initialise graph search + //e->network_stack[++e->network_stack_depth] = 0; + e->network_stack_depth = 1; + e->networks_visited = calloc(db->network_nodes_count, sizeof(*e->networks_visited)); + DEBUG(e->ctx, "Database enumerator object allocated at %p\n", e); *enumerator = e; @@ -657,3 +676,118 @@ LOC_EXPORT struct loc_as* loc_database_enumerator_next_as(struct loc_database_en // We have searched through all of them return NULL; } + +static int loc_database_enumerator_stack_push_node( + struct loc_database_enumerator* e, off_t offset, int i, int depth) { + // Do not add empty nodes + if (!offset) + return 0; + + // Check if there is any space left on the stack + if (e->network_stack_depth >= MAX_STACK_DEPTH) { + ERROR(e->ctx, "Maximum stack size reached: %d\n", e->network_stack_depth); + return -1; + } + + // Increase stack size + int s = ++e->network_stack_depth; + + DEBUG(e->ctx, "Added node %jd to stack (%d)\n", offset, depth); + + e->network_stack[s].offset = offset; + e->network_stack[s].i = i; + e->network_stack[s].depth = depth; + + return 0; +} + +static int loc_database_enumerator_network_depth_first_search( + struct loc_database_enumerator* e, struct loc_network** network) { + // Reset network + *network = NULL; + int r; + + DEBUG(e->ctx, "Called with a stack of %u nodes\n", e->network_stack_depth); + + // Perform DFS + while (e->network_stack_depth > 0) { + DEBUG(e->ctx, "Stack depth: %u\n", e->network_stack_depth); + + // Get object from top of the stack + struct loc_node_stack* node = &e->network_stack[e->network_stack_depth]; + + // Remove the node from the stack if we have already visited it + if (e->networks_visited[node->offset]) { + e->network_stack_depth--; + continue; + } + + in6_addr_set_bit(&e->network_address, + (node->depth > 0) ? node->depth - 1 : 0, node->i); + + //for (unsigned int i = stack->depth + 1; i < 128; i++) + // in6_addr_set_bit(&e->network_address, i, 0); + + DEBUG(e->ctx, "Looking at node %jd\n", node->offset); + e->networks_visited[node->offset]++; + + // Pop node from top of the stack + struct loc_database_network_node_v0* n = + e->db->network_nodes_v0 + node->offset; + + // Add edges to stack + r = loc_database_enumerator_stack_push_node(e, + be32toh(n->one), 1, node->depth + 1); + + if (r) + return r; + + r = loc_database_enumerator_stack_push_node(e, + be32toh(n->zero), 0, node->depth + 1); + + if (r) + return r; + + // Check if this node is a leaf and has a network object + if (__loc_database_node_is_leaf(n)) { + off_t network_index = be32toh(n->network); + + DEBUG(e->ctx, "Node has a network at %jd\n", network_index); + + // Fetch the network object + r = loc_database_fetch_network(e->db, network, + &e->network_address, node->depth, network_index); + + // Break on any errors + if (r) + return r; + + // Check if we are interested in this network + + // Skip if the country code does not match + if (e->country_code && !loc_network_match_country_code(*network, e->country_code)) { + loc_network_unref(*network); + continue; + } + + return 0; + } + } + + // Reached the end of the search + // TODO cleanup + + return 0; +} + +LOC_EXPORT struct loc_network* loc_database_enumerator_next_network( + struct loc_database_enumerator* enumerator) { + struct loc_network* network = NULL; + + int r = loc_database_enumerator_network_depth_first_search(enumerator, &network); + if (r) { + return NULL; + } + + return network; +} diff --git a/src/libloc.sym b/src/libloc.sym index 7faa9c0..017faf3 100644 --- a/src/libloc.sym +++ b/src/libloc.sym @@ -53,6 +53,7 @@ global: # Database Enumerator loc_database_enumerator_new; loc_database_enumerator_next_as; + loc_database_enumerator_next_network; loc_database_enumerator_ref; loc_database_enumerator_set_country_code; loc_database_enumerator_set_string; @@ -61,6 +62,7 @@ global: # Network loc_network_get_asn; loc_network_get_country_code; + loc_network_match_country_code; loc_network_new; loc_network_new_from_string; loc_network_ref; diff --git a/src/loc/database.h b/src/loc/database.h index 7cb8020..d0579ab 100644 --- a/src/loc/database.h +++ b/src/loc/database.h @@ -51,5 +51,6 @@ struct loc_database_enumerator* loc_database_enumerator_unref(struct loc_databas int loc_database_enumerator_set_string(struct loc_database_enumerator* enumerator, const char* string); int loc_database_enumerator_set_country_code(struct loc_database_enumerator* enumerator, const char* country_code); struct loc_as* loc_database_enumerator_next_as(struct loc_database_enumerator* enumerator); +struct loc_network* loc_database_enumerator_next_network(struct loc_database_enumerator* enumerator); #endif diff --git a/src/loc/network.h b/src/loc/network.h index 2e1abcb..63f4bfa 100644 --- a/src/loc/network.h +++ b/src/loc/network.h @@ -34,6 +34,7 @@ int loc_network_match_address(struct loc_network* network, const struct in6_addr const char* loc_network_get_country_code(struct loc_network* network); int loc_network_set_country_code(struct loc_network* network, const char* country_code); +int loc_network_match_country_code(struct loc_network* network, const char* country_code); uint32_t loc_network_get_asn(struct loc_network* network); int loc_network_set_asn(struct loc_network* network, uint32_t asn); diff --git a/src/network.c b/src/network.c index 24179f5..b8bc0f7 100644 --- a/src/network.c +++ b/src/network.c @@ -305,6 +305,15 @@ LOC_EXPORT int loc_network_set_country_code(struct loc_network* network, const c return 0; } +LOC_EXPORT int loc_network_match_country_code(struct loc_network* network, const char* country_code) { + // Country codes must be two characters + if (strlen(country_code) != 2) + return -EINVAL; + + return (network->country_code[0] == country_code[0]) + && (network->country_code[1] == country_code[1]); +} + LOC_EXPORT uint32_t loc_network_get_asn(struct loc_network* network) { return network->asn; } -- 2.39.2