database: Encode prefix length into tree
authorMichael Tremer <michael.tremer@ipfire.org>
Tue, 30 Jan 2018 22:30:46 +0000 (22:30 +0000)
committerMichael Tremer <michael.tremer@ipfire.org>
Tue, 30 Jan 2018 22:30:46 +0000 (22:30 +0000)
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 <michael.tremer@ipfire.org>
src/database.c
src/loc/format.h
src/loc/network.h
src/network.c
src/writer.c

index a74888c..619d379 100644 (file)
@@ -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);
index 8309d1c..c590a64 100644 (file)
@@ -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];
index 0b57ae2..2e1abcb 100644 (file)
@@ -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);
index d960153..45afd40 100644 (file)
@@ -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;
index 12a2c52..eb2b2e6 100644 (file)
@@ -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