From: Michael Tremer Date: Thu, 28 Dec 2017 16:55:33 +0000 (+0000) Subject: Allow creating networks in memory X-Git-Tag: 0.9.0~162 X-Git-Url: http://git.ipfire.org/?p=people%2Fms%2Flibloc.git;a=commitdiff_plain;h=3b5f4af2cd45de45599774740290a081cd3d220d Allow creating networks in memory Signed-off-by: Michael Tremer --- diff --git a/Makefile.am b/Makefile.am index 7d48831..00763a8 100644 --- a/Makefile.am +++ b/Makefile.am @@ -50,6 +50,7 @@ src_libloc_la_SOURCES =\ src/as.h \ src/database.c \ src/database.h \ + src/network.c \ src/stringpool.c \ src/stringpool.h \ src/writer.c @@ -77,13 +78,15 @@ TESTS = \ src/test-libloc \ src/test-stringpool \ src/test-database \ - src/test-as + src/test-as \ + src/test-network check_PROGRAMS = \ src/test-libloc \ src/test-stringpool \ src/test-database \ - src/test-as + src/test-as \ + src/test-network src_test_libloc_SOURCES = \ src/test-libloc.c @@ -97,6 +100,12 @@ src_test_as_SOURCES = \ src_test_as_LDADD = \ src/libloc.la +src_test_network_SOURCES = \ + src/test-network.c + +src_test_network_LDADD = \ + src/libloc.la + src_test_stringpool_SOURCES = \ src/test-stringpool.c diff --git a/src/.gitignore b/src/.gitignore index 8c2a12c..0ac749b 100644 --- a/src/.gitignore +++ b/src/.gitignore @@ -8,4 +8,5 @@ libloc.pc test-as test-libloc test-database +test-network test-stringpool diff --git a/src/libloc.sym b/src/libloc.sym index 6934102..47e8f69 100644 --- a/src/libloc.sym +++ b/src/libloc.sym @@ -19,6 +19,19 @@ global: loc_database_ref; loc_database_unref; + # Network + loc_network_get_country_code; + loc_network_new; + loc_network_new_from_string; + loc_network_set_country_code; + loc_network_unref; + + # Network Tree + loc_network_tree_add_network; + loc_network_tree_dump; + loc_network_tree_new; + loc_network_tree_unref; + # String Pool loc_stringpool_add; loc_stringpool_dump; @@ -30,6 +43,7 @@ global: # Writer loc_writer_add_as; + loc_writer_add_network; loc_writer_get_description; loc_writer_get_vendor; loc_writer_new; diff --git a/src/loc/format.h b/src/loc/format.h index 4a49628..c4690d5 100644 --- a/src/loc/format.h +++ b/src/loc/format.h @@ -50,6 +50,22 @@ struct loc_database_header_v0 { uint32_t pool_length; }; +struct loc_database_network_v0 { + uint32_t zero; + uint32_t one; +}; + +struct loc_database_network_node_v0 { + // The start address will be encoded in the tree + uint8_t prefix; + + // The country this network is located in + char country_code[2]; + + // ASN + uint32_t asn; +}; + struct loc_database_as_v0 { // The AS number uint32_t number; diff --git a/src/loc/network.h b/src/loc/network.h new file mode 100644 index 0000000..cb95f1a --- /dev/null +++ b/src/loc/network.h @@ -0,0 +1,42 @@ +/* + libloc - A library to determine the location of someone on the Internet + + Copyright (C) 2017 IPFire Development Team + + This library is free software; you can redistribute it and/or + modify it under the terms of the GNU Lesser General Public + License as published by the Free Software Foundation; either + version 2.1 of the License, or (at your option) any later version. + + This library is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + Lesser General Public License for more details. +*/ + +#ifndef LIBLOC_NETWORK_H +#define LIBLOC_NETWORK_H + +#include + +#include + +struct loc_network; +int loc_network_new(struct loc_ctx* ctx, struct loc_network** network, + struct in6_addr start_address, unsigned int prefix); +int loc_network_new_from_string(struct loc_ctx* ctx, struct loc_network** network, + const char* address_string); +struct loc_network* loc_network_ref(struct loc_network* network); +struct loc_network* loc_network_unref(struct loc_network* network); +char* loc_network_str(struct loc_network* network); + +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); + +struct loc_network_tree; +int loc_network_tree_new(struct loc_ctx* ctx, struct loc_network_tree** tree); +struct loc_network_tree* loc_network_tree_unref(struct loc_network_tree* tree); +int loc_network_tree_dump(struct loc_network_tree* tree); +int loc_network_tree_add_network(struct loc_network_tree* tree, struct loc_network* network); + +#endif diff --git a/src/loc/writer.h b/src/loc/writer.h index f433ac8..82923d0 100644 --- a/src/loc/writer.h +++ b/src/loc/writer.h @@ -20,6 +20,7 @@ #include #include +#include #include "as.h" @@ -36,6 +37,7 @@ const char* loc_writer_get_description(struct loc_writer* writer); int loc_writer_set_description(struct loc_writer* writer, const char* description); int loc_writer_add_as(struct loc_writer* writer, struct loc_as** as, uint32_t number); +int loc_writer_add_network(struct loc_writer* writer, struct loc_network** network, const char* string); int loc_writer_write(struct loc_writer* writer, FILE* f); diff --git a/src/network.c b/src/network.c new file mode 100644 index 0000000..bf11f2a --- /dev/null +++ b/src/network.c @@ -0,0 +1,347 @@ +/* + libloc - A library to determine the location of someone on the Internet + + Copyright (C) 2017 IPFire Development Team + + This library is free software; you can redistribute it and/or + modify it under the terms of the GNU Lesser General Public + License as published by the Free Software Foundation; either + version 2.1 of the License, or (at your option) any later version. + + This library is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + Lesser General Public License for more details. +*/ + +#include +#include +#include +#include +#include + +#include +#include + +#include "libloc-private.h" +#include "as.h" + +struct loc_network { + struct loc_ctx* ctx; + int refcount; + + struct in6_addr start_address; + unsigned int prefix; + + char country_code[3]; + + struct loc_as* as; +}; + +LOC_EXPORT int loc_network_new(struct loc_ctx* ctx, struct loc_network** network, + struct in6_addr start_address, unsigned int prefix) { + // Address cannot be unspecified + if (IN6_IS_ADDR_UNSPECIFIED(&start_address)) { + DEBUG(ctx, "Start address is unspecified\n"); + return -EINVAL; + } + + // Address cannot be loopback + if (IN6_IS_ADDR_LOOPBACK(&start_address)) { + DEBUG(ctx, "Start address is loopback address\n"); + return -EINVAL; + } + + // Address cannot be link-local + if (IN6_IS_ADDR_LINKLOCAL(&start_address)) { + DEBUG(ctx, "Start address cannot be link-local\n"); + return -EINVAL; + } + + // Address cannot be site-local + if (IN6_IS_ADDR_SITELOCAL(&start_address)) { + DEBUG(ctx, "Start address cannot be site-local\n"); + return -EINVAL; + } + + struct loc_network* n = calloc(1, sizeof(*n)); + if (!n) + return -ENOMEM; + + n->ctx = loc_ref(ctx); + n->refcount = 1; + + n->start_address = start_address; + n->prefix = prefix; + + DEBUG(n->ctx, "Network allocated at %p\n", n); + *network = n; + return 0; +} + +LOC_EXPORT int loc_network_new_from_string(struct loc_ctx* ctx, struct loc_network** network, + const char* address_string) { + struct in6_addr start_address; + char* prefix_string; + + // Make a copy of the string to work on it + char* buffer = strdup(address_string); + address_string = prefix_string = buffer; + + // Split address and prefix + address_string = strsep(&prefix_string, "/"); + + // Convert prefix to integer + unsigned int prefix = strtol(prefix_string, NULL, 10); + + // Parse the address + int r = inet_pton(AF_INET6, address_string, &start_address); + + // Free temporary buffer + free(buffer); + + if (r == 1) { + r = loc_network_new(ctx, network, start_address, prefix); + } + + return r; +} + +LOC_EXPORT struct loc_network* loc_network_ref(struct loc_network* network) { + network->refcount++; + + return network; +} + +static void loc_network_free(struct loc_network* network) { + DEBUG(network->ctx, "Releasing network at %p\n", network); + + if (network->as) + loc_as_unref(network->as); + + loc_unref(network->ctx); + free(network); +} + +LOC_EXPORT struct loc_network* loc_network_unref(struct loc_network* network) { + if (--network->refcount > 0) + return network; + + loc_network_free(network); + return NULL; +} + +LOC_EXPORT char* loc_network_str(struct loc_network* network) { + const size_t l = INET6_ADDRSTRLEN + 3; + + char* string = malloc(l); + if (!string) + return NULL; + + const char* ret = inet_ntop(AF_INET6, &network->start_address, string, l); + if (!ret) { + ERROR(network->ctx, "Could not convert network to string: %s\n", strerror(errno)); + + free(string); + return NULL; + } + + // Append prefix + sprintf(string + strlen(string), "/%u", network->prefix); + + return string; +} + +LOC_EXPORT const char* loc_network_get_country_code(struct loc_network* network) { + return network->country_code; +} + +LOC_EXPORT int loc_network_set_country_code(struct loc_network* network, const char* country_code) { + // Country codes must be two characters + if (strlen(country_code) != 2) + return -EINVAL; + + for (unsigned int i = 0; i < 3; i++) { + network->country_code[i] = country_code[i]; + } + + return 0; +} + +struct loc_network_tree { + struct loc_ctx* ctx; + int refcount; + + struct loc_network_tree_node* root; +}; + +struct loc_network_tree_node { + struct loc_network_tree_node* zero; + struct loc_network_tree_node* one; + + struct loc_network* network; +}; + +LOC_EXPORT int loc_network_tree_new(struct loc_ctx* ctx, struct loc_network_tree** tree) { + struct loc_network_tree* t = calloc(1, sizeof(*t)); + if (!t) + return -ENOMEM; + + t->ctx = loc_ref(ctx); + t->refcount = 1; + + // Create the root node + t->root = calloc(1, sizeof(*t->root)); + + DEBUG(t->ctx, "Network tree allocated at %p\n", t); + *tree = t; + return 0; +} + +static int loc_network_tree_node_new(struct loc_network_tree_node** node) { + struct loc_network_tree_node* n = calloc(1, sizeof(*n)); + if (!n) + return -ENOMEM; + + n->zero = n->one = NULL; + + *node = n; + return 0; +} + +static struct loc_network_tree_node* loc_network_tree_get_node(struct loc_network_tree_node* node, int path) { + struct loc_network_tree_node** n; + + if (path) + n = &node->one; + else + n = &node->zero; + + // If the desired node doesn't exist, yet, we will create it + if (*n == NULL) { + int r = loc_network_tree_node_new(n); + if (r) + return NULL; + } + + return *n; +} + +static struct loc_network_tree_node* loc_network_tree_get_path(struct loc_network_tree* tree, const struct in6_addr* address) { + struct loc_network_tree_node* node = tree->root; + + for (unsigned int i = 127; i > 0; i--) { + // Check if the ith bit is one or zero + node = loc_network_tree_get_node(node, ((address->s6_addr32[i / 32] & (1 << (i % 32))) == 0)); + } + + return node; +} + +static int __loc_network_tree_walk(struct loc_ctx* ctx, struct loc_network_tree_node* node, + int(*filter_callback)(struct loc_network* network), int(*callback)(struct loc_network* network)) { + int r; + + // Finding a network ends the walk here + if (node->network) { + if (filter_callback) { + int f = filter_callback(node->network); + if (f < 0) + return f; + + // Skip network if filter function returns value greater than zero + if (f > 0) + return 0; + } + + r = callback(node->network); + if (r) + return r; + } + + // Walk down on the left side of the tree first + if (node->zero) { + r = __loc_network_tree_walk(ctx, node->zero, filter_callback, callback); + if (r) + return r; + } + + // Then walk on the other side + if (node->one) { + r = __loc_network_tree_walk(ctx, node->one, filter_callback, callback); + if (r) + return r; + } + + return 0; +} + +static void loc_network_tree_free_subtree(struct loc_network_tree_node* node) { + if (node->network) + loc_network_unref(node->network); + + if (node->zero) + loc_network_tree_free_subtree(node->zero); + + if (node->one) + loc_network_tree_free_subtree(node->one); + + free(node); +} + +static void loc_network_tree_free(struct loc_network_tree* tree) { + DEBUG(tree->ctx, "Releasing network tree at %p\n", tree); + + loc_network_tree_free_subtree(tree->root); + + loc_unref(tree->ctx); + free(tree); +} + +LOC_EXPORT struct loc_network_tree* loc_network_tree_unref(struct loc_network_tree* tree) { + if (--tree->refcount > 0) + return tree; + + loc_network_tree_free(tree); + return NULL; +} + +int __loc_network_tree_dump(struct loc_network* network) { + DEBUG(network->ctx, "Dumping network at %p\n", network); + + char* s = loc_network_str(network); + if (!s) + return 1; + + INFO(network->ctx, "%s\n", s); + free(s); + + return 0; +} + +LOC_EXPORT int loc_network_tree_dump(struct loc_network_tree* tree) { + DEBUG(tree->ctx, "Dumping network tree at %p\n", tree); + + return __loc_network_tree_walk(tree->ctx, tree->root, NULL, __loc_network_tree_dump); +} + +LOC_EXPORT int loc_network_tree_add_network(struct loc_network_tree* tree, struct loc_network* network) { + DEBUG(tree->ctx, "Adding network %p to tree %p\n", network, tree); + + struct loc_network_tree_node* node = loc_network_tree_get_path(tree, &network->start_address); + if (!node) { + ERROR(tree->ctx, "Could not find a node\n"); + return -ENOMEM; + } + + // Check if node has not been set before + if (node->network) { + DEBUG(tree->ctx, "There is already a network at this path\n"); + return 1; + } + + // Point node to the network + node->network = loc_network_ref(network); + + return 0; +} diff --git a/src/test-network.c b/src/test-network.c new file mode 100644 index 0000000..b64c004 --- /dev/null +++ b/src/test-network.c @@ -0,0 +1,73 @@ +/* + libloc - A library to determine the location of someone on the Internet + + Copyright (C) 2017 IPFire Development Team + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 2 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. +*/ + +#include +#include +#include +#include + +#include +#include + +int main(int argc, char** argv) { + int err; + + struct loc_ctx* ctx; + err = loc_new(&ctx); + if (err < 0) + exit(EXIT_FAILURE); + + struct loc_network_tree* tree; + err = loc_network_tree_new(ctx, &tree); + if (err) { + fprintf(stderr, "Could not create the network tree\n"); + exit(EXIT_FAILURE); + } + + // Create a network + struct loc_network* network1; + err = loc_network_new_from_string(ctx, &network1, "2001:db8::/32"); + if (err) { + fprintf(stderr, "Could not create the network\n"); + exit(EXIT_FAILURE); + } + + err = loc_network_set_country_code(network1, "XX"); + if (err) { + fprintf(stderr, "Could not set country code\n"); + exit(EXIT_FAILURE); + } + + // Adding network to the tree + err = loc_network_tree_add_network(tree, network1); + if (err) { + fprintf(stderr, "Could not add network to the tree\n"); + exit(EXIT_FAILURE); + } + + // Dump the tree + err = loc_network_tree_dump(tree); + if (err) { + fprintf(stderr, "Error dumping tree: %d\n", err); + exit(EXIT_FAILURE); + } + + loc_network_unref(network1); + loc_network_tree_unref(tree); + loc_unref(ctx); + + return EXIT_SUCCESS; +} diff --git a/src/writer.c b/src/writer.c index da6959a..1e3e360 100644 --- a/src/writer.c +++ b/src/writer.c @@ -22,6 +22,7 @@ #include #include +#include #include #include "libloc-private.h" @@ -37,6 +38,8 @@ struct loc_writer { struct loc_as** as; size_t as_count; + + struct loc_network_tree* networks; }; LOC_EXPORT int loc_writer_new(struct loc_ctx* ctx, struct loc_writer** writer) { @@ -53,6 +56,13 @@ LOC_EXPORT int loc_writer_new(struct loc_ctx* ctx, struct loc_writer** writer) { return r; } + // Initialize the network tree + r = loc_network_tree_new(ctx, &w->networks); + if (r) { + loc_writer_unref(w); + return r; + } + *writer = w; return 0; } @@ -71,6 +81,10 @@ static void loc_writer_free(struct loc_writer* writer) { loc_as_unref(writer->as[i]); } + // Release network tree + if (writer->networks) + loc_network_tree_unref(writer->networks); + // Unref the string pool loc_stringpool_unref(writer->pool); @@ -141,6 +155,18 @@ LOC_EXPORT int loc_writer_add_as(struct loc_writer* writer, struct loc_as** as, return 0; } +LOC_EXPORT int loc_writer_add_network(struct loc_writer* writer, struct loc_network** network, const char* string) { + int r; + + // Create a new network object + r = loc_network_new_from_string(writer->ctx, network, string); + if (r) + return r; + + // Add it to the local tree + return loc_network_tree_add_network(writer->networks, *network); +} + static void make_magic(struct loc_writer* writer, struct loc_database_magic* magic) { // Copy magic bytes for (unsigned int i = 0; i < strlen(LOC_DATABASE_MAGIC); i++)