From 39a55353998bb8b854e0ad4ad4a31357aaf69b25 Mon Sep 17 00:00:00 2001 From: Michael Tremer Date: Tue, 30 Jan 2018 22:30:46 +0000 Subject: [PATCH] database: Encode prefix length into tree To keep the tree smaller and to not have too many sparse nodes in it that waste a lot of memory, we encode the prefix now into the tree as depth. Signed-off-by: Michael Tremer --- src/database.c | 42 ++++++++++++++++++++++++++++-------------- src/loc/format.h | 5 +++-- src/loc/network.h | 2 +- src/network.c | 13 ++++++------- src/writer.c | 10 +++++----- 5 files changed, 43 insertions(+), 29 deletions(-) diff --git a/src/database.c b/src/database.c index a74888c..619d379 100644 --- a/src/database.c +++ b/src/database.c @@ -409,7 +409,8 @@ LOC_EXPORT int loc_database_get_as(struct loc_database* db, struct loc_as** as, } // Returns the network at position pos -static int loc_database_fetch_network(struct loc_database* db, struct loc_network** network, struct in6_addr* address, off_t 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; @@ -418,7 +419,8 @@ static int loc_database_fetch_network(struct loc_database* db, struct loc_networ int r; switch (db->version) { case 0: - r = loc_network_new_from_database_v0(db->ctx, network, address, db->networks_v0 + pos); + r = loc_network_new_from_database_v0(db->ctx, network, + address, prefix, db->networks_v0 + pos); break; default: @@ -435,20 +437,26 @@ static int loc_database_fetch_network(struct loc_database* db, struct loc_networ } static int __loc_database_node_is_leaf(const struct loc_database_network_node_v0* node) { - return (node->zero == htobe32(0xffffffff)); + 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, + struct loc_network** network, struct in6_addr* network_address, unsigned int prefix, const struct loc_database_network_node_v0* node) { - DEBUG(db->ctx, "Handling leaf node at %jd\n", node - db->network_nodes_v0); + 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, be32toh(node->one)); + network_address, prefix, network_index); if (r) return r; + char* s = loc_network_str(*network); + DEBUG(db->ctx, "Got network %s\n", s); + free(s); + // Check if the given IP address is inside the network r = loc_network_match_address(*network, address); if (r) { @@ -467,13 +475,16 @@ static int __loc_database_lookup_handle_leaf(struct loc_database* db, const stru 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) { - // If the node is a leaf node, we end here - if (__loc_database_node_is_leaf(node)) - return __loc_database_lookup_handle_leaf(db, address, network, network_address, node); - 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); @@ -515,13 +526,16 @@ static int __loc_database_lookup_max(struct loc_database* db, const struct in6_a 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) { - // If the node is a leaf node, we end here - if (__loc_database_node_is_leaf(node)) - return __loc_database_lookup_handle_leaf(db, address, network, network_address, node); - 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; + } + // Follow the path int bit = in6_addr_get_bit(address, level); in6_addr_set_bit(network_address, level, bit); diff --git a/src/loc/format.h b/src/loc/format.h index 8309d1c..c590a64 100644 --- a/src/loc/format.h +++ b/src/loc/format.h @@ -67,11 +67,12 @@ struct loc_database_header_v0 { struct loc_database_network_node_v0 { uint32_t zero; uint32_t one; + + uint32_t network; }; struct loc_database_network_v0 { - // The start address will be encoded in the tree - uint8_t prefix; + // The start address and prefix will be encoded in the tree // The country this network is located in char country_code[2]; diff --git a/src/loc/network.h b/src/loc/network.h index 0b57ae2..2e1abcb 100644 --- a/src/loc/network.h +++ b/src/loc/network.h @@ -42,7 +42,7 @@ int loc_network_set_asn(struct loc_network* network, uint32_t asn); int loc_network_to_database_v0(struct loc_network* network, struct loc_database_network_v0* dbobj); int loc_network_new_from_database_v0(struct loc_ctx* ctx, struct loc_network** network, - struct in6_addr* address, const struct loc_database_network_v0* dbobj); + struct in6_addr* address, unsigned int prefix, const struct loc_database_network_v0* dbobj); struct loc_network_tree; int loc_network_tree_new(struct loc_ctx* ctx, struct loc_network_tree** tree); diff --git a/src/network.c b/src/network.c index d960153..45afd40 100644 --- a/src/network.c +++ b/src/network.c @@ -316,8 +316,6 @@ LOC_EXPORT int loc_network_set_asn(struct loc_network* network, uint32_t asn) { } LOC_EXPORT int loc_network_to_database_v0(struct loc_network* network, struct loc_database_network_v0* dbobj) { - dbobj->prefix = network->prefix; - // Add country code for (unsigned int i = 0; i < 2; i++) { dbobj->country_code[i] = network->country_code ? network->country_code[i] : '\0'; @@ -330,8 +328,8 @@ LOC_EXPORT int loc_network_to_database_v0(struct loc_network* network, struct lo } LOC_EXPORT int loc_network_new_from_database_v0(struct loc_ctx* ctx, struct loc_network** network, - struct in6_addr* address, const struct loc_database_network_v0* dbobj) { - int r = loc_network_new(ctx, network, address, dbobj->prefix); + struct in6_addr* address, unsigned int prefix, const struct loc_database_network_v0* dbobj) { + int r = loc_network_new(ctx, network, address, prefix); if (r) return r; @@ -413,10 +411,10 @@ static struct loc_network_tree_node* loc_network_tree_get_node(struct loc_networ return *n; } -static struct loc_network_tree_node* loc_network_tree_get_path(struct loc_network_tree* tree, const struct in6_addr* address) { +static struct loc_network_tree_node* loc_network_tree_get_path(struct loc_network_tree* tree, const struct in6_addr* address, unsigned int prefix) { struct loc_network_tree_node* node = tree->root; - for (unsigned int i = 0; i < 128; i++) { + for (unsigned int i = 0; i < prefix; i++) { // Check if the ith bit is one or zero node = loc_network_tree_get_node(node, in6_addr_get_bit(address, i)); } @@ -508,7 +506,8 @@ LOC_EXPORT int loc_network_tree_dump(struct loc_network_tree* tree) { 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); + struct loc_network_tree_node* node = loc_network_tree_get_path(tree, + &network->start_address, network->prefix); if (!node) { ERROR(tree->ctx, "Could not find a node\n"); return -ENOMEM; diff --git a/src/writer.c b/src/writer.c index 12a2c52..eb2b2e6 100644 --- a/src/writer.c +++ b/src/writer.c @@ -349,6 +349,9 @@ static int loc_database_write_networks(struct loc_writer* writer, } // Prepare what we are writing to disk + db_node.zero = htobe32(node->index_zero); + db_node.one = htobe32(node->index_one); + if (loc_network_tree_node_is_leaf(node->node)) { struct loc_network* network = loc_network_tree_node_get_network(node->node); @@ -356,13 +359,10 @@ static int loc_database_write_networks(struct loc_writer* writer, struct network* nw = make_network(network); TAILQ_INSERT_TAIL(&networks, nw, networks); - db_node.zero = htobe32(0xffffffff); - db_node.one = htobe32(network_index++); - + db_node.network = htobe32(network_index++); loc_network_unref(network); } else { - db_node.zero = htobe32(node->index_zero); - db_node.one = htobe32(node->index_one); + db_node.network = htobe32(0xffffffff); } // Write the current node -- 2.39.2