X-Git-Url: http://git.ipfire.org/?p=people%2Fms%2Flibloc.git;a=blobdiff_plain;f=src%2Fdatabase.c;h=fe5e6dc6e0ebcb86a56b5629dc982ff5bc879ff1;hp=3a4f8b8bb13a81dd4099bdb78b3b89edd6b9b173;hb=273948cfa02a1bacf906f1b4dc296f81b7d8441e;hpb=0e974d4b392023e2f38e8ab8cfe5977b0fb439b4 diff --git a/src/database.c b/src/database.c index 3a4f8b8..fe5e6dc 100644 --- a/src/database.c +++ b/src/database.c @@ -15,7 +15,10 @@ */ #include +#include +#include #include +#include #include #include #include @@ -27,35 +30,55 @@ #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; int refcount; - FILE* file; unsigned int version; 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; }; -static int loc_database_read_magic(struct loc_database* db) { +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; // Read from file - size_t bytes_read = fread(&magic, 1, sizeof(magic), db->file); + size_t bytes_read = fread(&magic, 1, sizeof(magic), f); // Check if we have been able to read enough data if (bytes_read < sizeof(magic)) { @@ -69,7 +92,7 @@ static int loc_database_read_magic(struct loc_database* db) { DEBUG(db->ctx, "Magic value matches\n"); // Parse version - db->version = ntohs(magic.version); + db->version = be16toh(magic.version); DEBUG(db->ctx, "Database version is %u\n", db->version); return 0; @@ -82,12 +105,15 @@ static int loc_database_read_magic(struct loc_database* db) { } static int loc_database_read_as_section_v0(struct loc_database* db, - 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) { db->as_v0 = mmap(NULL, as_length, PROT_READ, - MAP_SHARED, fileno(db->file), as_offset); + MAP_SHARED, fileno(f), as_offset); if (db->as_v0 == MAP_FAILED) return -errno; @@ -100,11 +126,57 @@ static int loc_database_read_as_section_v0(struct loc_database* db, return 0; } -static int loc_database_read_header_v0(struct loc_database* db) { +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; // Read from file - size_t size = fread(&header, 1, sizeof(header), db->file); + size_t size = fread(&header, 1, sizeof(header), f); if (size < sizeof(header)) { ERROR(db->ctx, "Could not read enough data for header\n"); @@ -113,33 +185,41 @@ static int loc_database_read_header_v0(struct loc_database* db) { // Copy over data db->created_at = be64toh(header.created_at); - db->vendor = ntohl(header.vendor); - db->description = ntohl(header.description); + db->vendor = be32toh(header.vendor); + db->description = be32toh(header.description); + db->license = be32toh(header.license); // Open pool - off_t pool_offset = ntohl(header.pool_offset); - size_t pool_length = ntohl(header.pool_length); + off_t pool_offset = be32toh(header.pool_offset); + size_t pool_length = be32toh(header.pool_length); int r = loc_stringpool_open(db->ctx, &db->pool, - db->file, pool_length, pool_offset); + f, pool_length, pool_offset); if (r) return r; // AS section - off_t as_offset = ntohl(header.as_offset); - size_t as_length = ntohl(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, 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; return 0; } -static int loc_database_read_header(struct loc_database* db) { +static int loc_database_read_header(struct loc_database* db, FILE* f) { switch (db->version) { case 0: - return loc_database_read_header_v0(db); + return loc_database_read_header_v0(db, f); default: ERROR(db->ctx, "Incompatible database version: %u\n", db->version); @@ -147,16 +227,32 @@ static int loc_database_read_header(struct loc_database* db) { } } -static FILE* copy_file_pointer(FILE* f) { - int fd = fileno(f); +static int loc_database_read(struct loc_database* db, FILE* f) { + clock_t start = clock(); + + // Read magic bytes + int r = loc_database_read_magic(db, f); + if (r) + return r; + + // Read the header + r = loc_database_read_header(db, f); + if (r) + return r; + + clock_t end = clock(); - // Make a copy - fd = dup(fd); + INFO(db->ctx, "Opened database in %.8fs\n", + (double)(end - start) / CLOCKS_PER_SEC); - return fdopen(fd, "r"); + return 0; } LOC_EXPORT int loc_database_new(struct loc_ctx* ctx, struct loc_database** database, FILE* f) { + // Fail on invalid file handle + if (!f) + return -EINVAL; + struct loc_database* db = calloc(1, sizeof(*db)); if (!db) return -ENOMEM; @@ -167,30 +263,15 @@ LOC_EXPORT int loc_database_new(struct loc_ctx* ctx, struct loc_database** datab DEBUG(db->ctx, "Database object allocated at %p\n", db); - // Copy the file pointer and work on that so we don't care if - // the calling function closes the file - db->file = copy_file_pointer(f); - if (!db->file) - goto FAIL; - - // Read magic bytes - int r = loc_database_read_magic(db); - if (r) - return r; - - // Read the header - r = loc_database_read_header(db); - if (r) + int r = loc_database_read(db, f); + if (r) { + loc_database_unref(db); return r; + } *database = db; return 0; - -FAIL: - loc_database_unref(db); - - return -errno; } LOC_EXPORT struct loc_database* loc_database_ref(struct loc_database* db) { @@ -200,20 +281,32 @@ 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)); } - loc_stringpool_unref(db->pool); + // 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)); + } - // Close file - if (db->file) - fclose(db->file); + // 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); free(db); @@ -239,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; } @@ -272,6 +369,9 @@ LOC_EXPORT int loc_database_get_as(struct loc_database* db, struct loc_as** as, off_t lo = 0; off_t hi = db->as_count - 1; + // Save start time + clock_t start = clock(); + while (lo <= hi) { off_t i = (lo + hi) / 2; @@ -282,8 +382,15 @@ LOC_EXPORT int loc_database_get_as(struct loc_database* db, struct loc_as** as, // Check if this is a match uint32_t as_number = loc_as_get_number(*as); - if (as_number == number) + if (as_number == number) { + clock_t end = clock(); + + // Log how fast this has been + DEBUG(db->ctx, "Found AS%u in %.8fs\n", as_number, + (double)(end - start) / CLOCKS_PER_SEC); + return 0; + } // If it wasn't, we release the AS and // adjust our search pointers @@ -298,5 +405,236 @@ LOC_EXPORT int loc_database_get_as(struct loc_database* db, struct loc_as** as, // Nothing found *as = NULL; + 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; } + +// 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; + + DEBUG(db->ctx, "No match found below level %u\n", level); + } else { + DEBUG(db->ctx, "Tree ended at level %u\n", level); + } + + // 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; + } + + return 1; +} + +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 == 1) { + 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; +}