X-Git-Url: http://git.ipfire.org/?a=blobdiff_plain;f=src%2Fdatabase.c;h=ec8aae933383c6a0f54ef7e5225e979219351b20;hb=9086d2b1db0eb01996dda2a4b50a058cb190e1c9;hp=f2450aab1b294a706b2f2ea3954ca69382ed41dc;hpb=a7431f1aba0f8dba2005e8374acf8f14d397b74a;p=people%2Fms%2Flibloc.git diff --git a/src/database.c b/src/database.c index f2450aa..ec8aae9 100644 --- a/src/database.c +++ b/src/database.c @@ -14,8 +14,11 @@ Lesser General Public License for more details. */ +#include +#include #include #include +#include #include #include #include @@ -27,12 +30,12 @@ #include #include +#include +#include #include - -#include "libloc-private.h" -#include "as.h" -#include "database.h" -#include "stringpool.h" +#include +#include +#include struct loc_database { struct loc_ctx* ctx; @@ -42,14 +45,35 @@ struct loc_database { time_t created_at; off_t vendor; off_t description; + off_t license; // ASes in the database struct loc_database_as_v0* as_v0; size_t as_count; + // Network tree + struct loc_database_network_node_v0* network_nodes_v0; + size_t network_nodes_count; + + // Networks + struct loc_database_network_v0* networks_v0; + size_t networks_count; + struct loc_stringpool* pool; }; +struct loc_database_enumerator { + struct loc_ctx* ctx; + struct loc_database* db; + int refcount; + + // Search string + char* string; + + // Index of the AS we are looking at + unsigned int as_index; +}; + static int loc_database_read_magic(struct loc_database* db, FILE* f) { struct loc_database_magic magic; @@ -81,7 +105,10 @@ static int loc_database_read_magic(struct loc_database* db, FILE* f) { } static int loc_database_read_as_section_v0(struct loc_database* db, - FILE* f, off_t as_offset, size_t as_length) { + FILE* f, const struct loc_database_header_v0* header) { + off_t as_offset = be32toh(header->as_offset); + size_t as_length = be32toh(header->as_length); + DEBUG(db->ctx, "Reading AS section from %jd (%zu bytes)\n", as_offset, as_length); if (as_length > 0) { @@ -99,6 +126,52 @@ static int loc_database_read_as_section_v0(struct loc_database* db, return 0; } +static int loc_database_read_network_nodes_section_v0(struct loc_database* db, + FILE* f, const struct loc_database_header_v0* header) { + off_t network_nodes_offset = be32toh(header->network_tree_offset); + size_t network_nodes_length = be32toh(header->network_tree_length); + + DEBUG(db->ctx, "Reading network nodes section from %jd (%zu bytes)\n", + network_nodes_offset, network_nodes_length); + + if (network_nodes_length > 0) { + db->network_nodes_v0 = mmap(NULL, network_nodes_length, PROT_READ, + MAP_SHARED, fileno(f), network_nodes_offset); + + if (db->network_nodes_v0 == MAP_FAILED) + return -errno; + } + + db->network_nodes_count = network_nodes_length / sizeof(*db->network_nodes_v0); + + INFO(db->ctx, "Read %zu network nodes from the database\n", db->network_nodes_count); + + return 0; +} + +static int loc_database_read_networks_section_v0(struct loc_database* db, + FILE* f, const struct loc_database_header_v0* header) { + off_t networks_offset = be32toh(header->network_data_offset); + size_t networks_length = be32toh(header->network_data_length); + + DEBUG(db->ctx, "Reading networks section from %jd (%zu bytes)\n", + networks_offset, networks_length); + + if (networks_length > 0) { + db->networks_v0 = mmap(NULL, networks_length, PROT_READ, + MAP_SHARED, fileno(f), networks_offset); + + if (db->networks_v0 == MAP_FAILED) + return -errno; + } + + db->networks_count = networks_length / sizeof(*db->networks_v0); + + INFO(db->ctx, "Read %zu networks from the database\n", db->networks_count); + + return 0; +} + static int loc_database_read_header_v0(struct loc_database* db, FILE* f) { struct loc_database_header_v0 header; @@ -114,6 +187,7 @@ static int loc_database_read_header_v0(struct loc_database* db, FILE* f) { db->created_at = be64toh(header.created_at); db->vendor = be32toh(header.vendor); db->description = be32toh(header.description); + db->license = be32toh(header.license); // Open pool off_t pool_offset = be32toh(header.pool_offset); @@ -125,10 +199,17 @@ static int loc_database_read_header_v0(struct loc_database* db, FILE* f) { return r; // AS section - off_t as_offset = be32toh(header.as_offset); - size_t as_length = be32toh(header.as_length); + r = loc_database_read_as_section_v0(db, f, &header); + if (r) + return r; - r = loc_database_read_as_section_v0(db, f, as_offset, as_length); + // Network Nodes + r = loc_database_read_network_nodes_section_v0(db, f, &header); + if (r) + return r; + + // Networks + r = loc_database_read_networks_section_v0(db, f, &header); if (r) return r; @@ -200,15 +281,31 @@ LOC_EXPORT struct loc_database* loc_database_ref(struct loc_database* db) { } static void loc_database_free(struct loc_database* db) { + int r; + DEBUG(db->ctx, "Releasing database %p\n", db); // Removing all ASes if (db->as_v0) { - int r = munmap(db->as_v0, db->as_count * sizeof(*db->as_v0)); + r = munmap(db->as_v0, db->as_count * sizeof(*db->as_v0)); if (r) ERROR(db->ctx, "Could not unmap AS section: %s\n", strerror(errno)); } + // Remove mapped network sections + if (db->networks_v0) { + r = munmap(db->networks_v0, db->networks_count * sizeof(*db->networks_v0)); + if (r) + ERROR(db->ctx, "Could not unmap networks section: %s\n", strerror(errno)); + } + + // Remove mapped network nodes section + if (db->network_nodes_v0) { + r = munmap(db->network_nodes_v0, db->network_nodes_count * sizeof(*db->network_nodes_v0)); + if (r) + ERROR(db->ctx, "Could not unmap network nodes section: %s\n", strerror(errno)); + } + loc_stringpool_unref(db->pool); loc_unref(db->ctx); @@ -235,6 +332,10 @@ LOC_EXPORT const char* loc_database_get_description(struct loc_database* db) { return loc_stringpool_get(db->pool, db->description); } +LOC_EXPORT const char* loc_database_get_license(struct loc_database* db) { + return loc_stringpool_get(db->pool, db->license); +} + LOC_EXPORT size_t loc_database_count_as(struct loc_database* db) { return db->as_count; } @@ -306,3 +407,284 @@ LOC_EXPORT int loc_database_get_as(struct loc_database* db, struct loc_as** as, return 1; } + +// Returns the network at position pos +static int loc_database_fetch_network(struct loc_database* db, struct loc_network** network, + struct in6_addr* address, unsigned int prefix, off_t pos) { + if ((size_t)pos >= db->networks_count) + return -EINVAL; + + DEBUG(db->ctx, "Fetching network at position %jd\n", pos); + + int r; + switch (db->version) { + case 0: + r = loc_network_new_from_database_v0(db->ctx, network, + address, prefix, db->networks_v0 + pos); + break; + + default: + return -1; + } + + if (r == 0) { + char* string = loc_network_str(*network); + DEBUG(db->ctx, "Got network %s\n", string); + free(string); + } + + return r; +} + +static int __loc_database_node_is_leaf(const struct loc_database_network_node_v0* node) { + return (node->network != htobe32(0xffffffff)); +} + +static int __loc_database_lookup_handle_leaf(struct loc_database* db, const struct in6_addr* address, + struct loc_network** network, struct in6_addr* network_address, unsigned int prefix, + const struct loc_database_network_node_v0* node) { + off_t network_index = be32toh(node->network); + + DEBUG(db->ctx, "Handling leaf node at %jd (%jd)\n", node - db->network_nodes_v0, network_index); + + // Fetch the network + int r = loc_database_fetch_network(db, network, + network_address, prefix, network_index); + if (r) { + ERROR(db->ctx, "Could not fetch network %jd from database\n", network_index); + return r; + } + + // Check if the given IP address is inside the network + r = loc_network_match_address(*network, address); + if (r) { + DEBUG(db->ctx, "Searched address is not part of the network\n"); + + loc_network_unref(*network); + *network = NULL; + return 1; + } + + // A network was found and the IP address matches + return 0; +} + +// Returns the highest result available +static int __loc_database_lookup_max(struct loc_database* db, const struct in6_addr* address, + struct loc_network** network, struct in6_addr* network_address, + const struct loc_database_network_node_v0* node, unsigned int level) { + int r; + off_t node_index; + + // If the node is a leaf node, we end here + if (__loc_database_node_is_leaf(node)) { + r = __loc_database_lookup_handle_leaf(db, address, network, network_address, level, node); + if (r <= 0) + return r; + } + + // Try to go down the ones path first + if (node->one) { + node_index = be32toh(node->one); + in6_addr_set_bit(network_address, level, 1); + + // Check boundaries + if (node_index > 0 && (size_t)node_index <= db->network_nodes_count) { + r = __loc_database_lookup_max(db, address, network, network_address, + db->network_nodes_v0 + node_index, level + 1); + + // Abort when match was found or error + if (r <= 0) + return r; + } + } + + // ... and if that fails, we try to go down one step on a zero + // branch and then try the ones again... + if (node->zero) { + node_index = be32toh(node->zero); + in6_addr_set_bit(network_address, level, 0); + + // Check boundaries + if (node_index > 0 && (size_t)node_index <= db->network_nodes_count) { + r = __loc_database_lookup_max(db, address, network, network_address, + db->network_nodes_v0 + node_index, level + 1); + + // Abort when match was found or error + if (r <= 0) + return r; + } + } + + // End of path + return 1; +} + +// Searches for an exact match along the path +static int __loc_database_lookup(struct loc_database* db, const struct in6_addr* address, + struct loc_network** network, struct in6_addr* network_address, + const struct loc_database_network_node_v0* node, unsigned int level) { + int r; + off_t node_index; + + // Follow the path + int bit = in6_addr_get_bit(address, level); + in6_addr_set_bit(network_address, level, bit); + + if (bit == 0) + node_index = be32toh(node->zero); + else + node_index = be32toh(node->one); + + // If the node index is zero, the tree ends here + // and we cannot descend any further + if (node_index > 0) { + // Check boundaries + if ((size_t)node_index >= db->network_nodes_count) + return -EINVAL; + + // Move on to the next node + r = __loc_database_lookup(db, address, network, network_address, + db->network_nodes_v0 + node_index, level + 1); + + // End here if a result was found + if (r == 0) + return r; + + // Raise any errors + else if (r < 0) + return r; + } + + // If this node has a leaf, we will check if it matches + if (__loc_database_node_is_leaf(node)) { + r = __loc_database_lookup_handle_leaf(db, address, network, network_address, level, node); + if (r <= 0) + return r; + } + + DEBUG(db->ctx, "Could not find an exact match at %u\n", level); + + // If nothing was found, we have to search for an inexact match + return __loc_database_lookup_max(db, address, network, network_address, node, level); +} + +LOC_EXPORT int loc_database_lookup(struct loc_database* db, + struct in6_addr* address, struct loc_network** network) { + struct in6_addr network_address; + memset(&network_address, 0, sizeof(network_address)); + + *network = NULL; + + // Save start time + clock_t start = clock(); + + int r = __loc_database_lookup(db, address, network, &network_address, + db->network_nodes_v0, 0); + + clock_t end = clock(); + + // Log how fast this has been + DEBUG(db->ctx, "Executed network search in %.8fs\n", + (double)(end - start) / CLOCKS_PER_SEC); + + return r; +} + +LOC_EXPORT int loc_database_lookup_from_string(struct loc_database* db, + const char* string, struct loc_network** network) { + struct in6_addr address; + + int r = loc_parse_address(db->ctx, string, &address); + if (r) + return r; + + return loc_database_lookup(db, &address, network); +} + +// Enumerator + +LOC_EXPORT int loc_database_enumerator_new(struct loc_database_enumerator** enumerator, struct loc_database* db) { + struct loc_database_enumerator* e = calloc(1, sizeof(*e)); + if (!e) + return -ENOMEM; + + // Reference context + e->ctx = loc_ref(db->ctx); + e->db = loc_database_ref(db); + e->refcount = 1; + + DEBUG(e->ctx, "Database enumerator object allocated at %p\n", e); + + *enumerator = e; + return 0; +} + +LOC_EXPORT struct loc_database_enumerator* loc_database_enumerator_ref(struct loc_database_enumerator* enumerator) { + enumerator->refcount++; + + return enumerator; +} + +static void loc_database_enumerator_free(struct loc_database_enumerator* enumerator) { + DEBUG(enumerator->ctx, "Releasing database enumerator %p\n", enumerator); + + // Release all references + loc_database_unref(enumerator->db); + loc_unref(enumerator->ctx); + + if (enumerator->string) + free(enumerator->string); + + free(enumerator); +} + +LOC_EXPORT struct loc_database_enumerator* loc_database_enumerator_unref(struct loc_database_enumerator* enumerator) { + if (!enumerator) + return NULL; + + if (--enumerator->refcount > 0) + return enumerator; + + loc_database_enumerator_free(enumerator); + return NULL; +} + +LOC_EXPORT int loc_database_enumerator_set_string(struct loc_database_enumerator* enumerator, const char* string) { + enumerator->string = strdup(string); + + // Make the string lowercase + for (char *p = enumerator->string; *p; p++) + *p = tolower(*p); + + return 0; +} + +LOC_EXPORT struct loc_as* loc_database_enumerator_next_as(struct loc_database_enumerator* enumerator) { + struct loc_database* db = enumerator->db; + struct loc_as* as; + + while (enumerator->as_index < db->as_count) { + // Fetch the next AS + int r = loc_database_fetch_as(db, &as, enumerator->as_index++); + if (r) + return NULL; + + r = loc_as_match_string(as, enumerator->string); + if (r == 0) { + DEBUG(enumerator->ctx, "AS%d (%s) matches %s\n", + loc_as_get_number(as), loc_as_get_name(as), enumerator->string); + + return as; + } + + // No match + loc_as_unref(as); + } + + // Reset the index + enumerator->as_index = 0; + + // We have searched through all of them + return NULL; +}