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 <michael.tremer@ipfire.org>

diff --git a/src/database.c b/src/database.c
index a74888cf763b3163a2dad971b18adc9744fa436e..619d3793094d1e61e9aef68fa87e8275aa91ca90 100644 (file)
--- 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
 }
 
 // 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;
 
        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:
        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:
                        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) {
 }
 
 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,
 }
 
 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) {
                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,
 
        // 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;
 
        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) {
        // 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) {
 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;
 
        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);
        // 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) {
 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;
 
        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);
        // 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 8309d1cf66858e29ece8b9d989466c18a3cdcfc4..c590a6447aa594f4639eaa3d355f29d50147f223 100644 (file)
--- 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;
 struct loc_database_network_node_v0 {
        uint32_t zero;
        uint32_t one;

+
+       uint32_t network;

 };
 
 struct loc_database_network_v0 {
 };
 
 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];
 
        // The country this network is located in
        char country_code[2];

diff --git a/src/loc/network.h b/src/loc/network.h
index 0b57ae2a4156b6908a40d8cf8fecf1a3ab7b22ea..2e1abcbb4659c78694099eb8b1bf1f0b6103be36 100644 (file)
--- 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,
 
 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);
 
 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 d960153170030aa554484041db0ee146ec4f8cc1..45afd4058f9819dca4a2aaf5e28cc3ca1c50e242 100644 (file)
--- 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) {
 }
 
 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';
        // 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,
 }
 
 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;
 
        if (r)
                return r;
 


@@ -413,10 +411,10 @@ static struct loc_network_tree_node* loc_network_tree_get_node(struct loc_networ
        return *n;
 }
 
        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;
 
        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));
        }
                // 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);
 
 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;
        if (!node) {
                ERROR(tree->ctx, "Could not find a node\n");
                return -ENOMEM;

diff --git a/src/writer.c b/src/writer.c
index 12a2c52ea5636f084483e0bb4fe33bdf8ed8e14f..eb2b2e6dcc5e1bd46733d41f2c665688ff0d8e5b 100644 (file)
--- 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
                }
 
                // 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);
 
                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);
 
                        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 {
                        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
                }
 
                // Write the current node