#include <loc/compat.h>
#include <loc/country.h>
#include <loc/network.h>
+#include <loc/network-list.h>
#include <loc/private.h>
struct loc_network {
return network->family;
}
+LOC_EXPORT unsigned int loc_network_prefix(struct loc_network* network) {
+ switch (network->family) {
+ case AF_INET6:
+ return network->prefix;
+
+ case AF_INET:
+ return network->prefix - 96;
+ }
+
+ return 0;
+}
+
static char* loc_network_format_address(struct loc_network* network, const struct in6_addr* address) {
const size_t length = INET6_ADDRSTRLEN;
return string;
}
+LOC_EXPORT const struct in6_addr* loc_network_get_first_address(struct loc_network* network) {
+ return &network->first_address;
+}
+
LOC_EXPORT char* loc_network_format_first_address(struct loc_network* network) {
return loc_network_format_address(network, &network->first_address);
}
+LOC_EXPORT const struct in6_addr* loc_network_get_last_address(struct loc_network* network) {
+ return &network->last_address;
+}
+
LOC_EXPORT char* loc_network_format_last_address(struct loc_network* network) {
return loc_network_format_address(network, &network->last_address);
}
LOC_EXPORT int loc_network_match_address(struct loc_network* network, const struct in6_addr* address) {
// Address must be larger than the start address
if (in6_addr_cmp(&network->first_address, address) > 0)
- return 1;
+ return 0;
// Address must be smaller than the last address
if (in6_addr_cmp(&network->last_address, address) < 0)
- return 1;
+ return 0;
// The address is inside this network
- return 0;
+ return 1;
}
LOC_EXPORT const char* loc_network_get_country_code(struct loc_network* network) {
return loc_network_has_flag(network, flag);
}
-LOC_EXPORT int loc_network_eq(struct loc_network* self, struct loc_network* other) {
- // Family must be the same
- if (self->family != other->family)
- return 0;
-
- // The start address must be the same
- if (in6_addr_cmp(&self->first_address, &other->first_address) != 0)
- return 0;
-
- // The prefix length must be the same
- if (self->prefix != other->prefix)
- return 0;
-
- return 1;
-}
-
-static int loc_network_gt(struct loc_network* self, struct loc_network* other) {
- // Families must match
- if (self->family != other->family)
- return -1;
-
+LOC_EXPORT int loc_network_cmp(struct loc_network* self, struct loc_network* other) {
+ // Compare address
int r = in6_addr_cmp(&self->first_address, &other->first_address);
+ if (r)
+ return r;
- switch (r) {
- // Smaller
- case -1:
- return 0;
-
- // Larger
- case 1:
- return 1;
-
- default:
- break;
- }
-
+ // Compare prefix
if (self->prefix > other->prefix)
return 1;
+ else if (self->prefix < other->prefix)
+ return -1;
- // Dunno
+ // Both networks are equal
return 0;
}
LOC_EXPORT int loc_network_overlaps(struct loc_network* self, struct loc_network* other) {
- if (loc_network_match_address(self, &other->first_address) == 0)
+ // Either of the start addresses must be in the other subnet
+ if (loc_network_match_address(self, &other->first_address))
return 1;
- if (loc_network_match_address(self, &other->last_address) == 0)
+ if (loc_network_match_address(other, &self->first_address))
return 1;
- if (loc_network_match_address(other, &self->first_address) == 0)
+ // Or either of the end addresses is in the other subnet
+ if (loc_network_match_address(self, &other->last_address))
return 1;
- if (loc_network_match_address(other, &self->last_address) == 0)
+ if (loc_network_match_address(other, &self->last_address))
return 1;
return 0;
}
-LOC_EXPORT int loc_network_is_subnet_of(struct loc_network* self, struct loc_network* other) {
+LOC_EXPORT int loc_network_is_subnet(struct loc_network* self, struct loc_network* other) {
+ // The prefix must be smaller (this avoids the more complex comparisons later)
+ if (self->prefix > other->prefix)
+ return 0;
+
// If the start address of the other network is smaller than this network,
// it cannot be a subnet.
- if (in6_addr_cmp(&self->first_address, &other->first_address) < 0)
+ if (in6_addr_cmp(&self->first_address, &other->first_address) > 0)
return 0;
// If the end address of the other network is greater than this network,
// it cannot be a subnet.
- if (in6_addr_cmp(&self->last_address, &other->last_address) > 0)
+ if (in6_addr_cmp(&self->last_address, &other->last_address) < 0)
return 0;
return 1;
}
-LOC_EXPORT struct loc_network_list* loc_network_subnets(struct loc_network* network) {
- struct loc_network_list* list;
+LOC_EXPORT int loc_network_subnets(struct loc_network* network,
+ struct loc_network** subnet1, struct loc_network** subnet2) {
+ int r;
+ *subnet1 = NULL;
+ *subnet2 = NULL;
// New prefix length
unsigned int prefix = network->prefix + 1;
// Check if the new prefix is valid
if (valid_prefix(&network->first_address, prefix))
- return NULL;
-
- // Create a new list with the result
- int r = loc_network_list_new(network->ctx, &list);
- if (r) {
- ERROR(network->ctx, "Could not create network list: %d\n", r);
- return NULL;
- }
-
- struct loc_network* subnet1 = NULL;
- struct loc_network* subnet2 = NULL;
+ return -1;
// Create the first half of the network
- r = loc_network_new(network->ctx, &subnet1, &network->first_address, prefix);
+ r = loc_network_new(network->ctx, subnet1, &network->first_address, prefix);
if (r)
- goto ERROR;
+ return r;
// The next subnet starts after the first one
- struct in6_addr first_address = address_increment(&subnet1->last_address);
+ struct in6_addr first_address = address_increment(&(*subnet1)->last_address);
// Create the second half of the network
- r = loc_network_new(network->ctx, &subnet2, &first_address, prefix);
+ r = loc_network_new(network->ctx, subnet2, &first_address, prefix);
if (r)
- goto ERROR;
+ return r;
- // Push the both onto the stack (in reverse order)
- r = loc_network_list_push(list, subnet2);
- if (r)
- goto ERROR;
+ // Copy country code
+ const char* country_code = loc_network_get_country_code(network);
+ if (country_code) {
+ loc_network_set_country_code(*subnet1, country_code);
+ loc_network_set_country_code(*subnet2, country_code);
+ }
- r = loc_network_list_push(list, subnet1);
+ // Copy ASN
+ uint32_t asn = loc_network_get_asn(network);
+ if (asn) {
+ loc_network_set_asn(*subnet1, asn);
+ loc_network_set_asn(*subnet2, asn);
+ }
+
+ // Copy flags
+ loc_network_set_flag(*subnet1, network->flags);
+ loc_network_set_flag(*subnet2, network->flags);
+
+ return 0;
+}
+
+static int __loc_network_exclude(struct loc_network* network,
+ struct loc_network* other, struct loc_network_list* list) {
+ struct loc_network* subnet1 = NULL;
+ struct loc_network* subnet2 = NULL;
+
+ int r = loc_network_subnets(network, &subnet1, &subnet2);
if (r)
goto ERROR;
- loc_network_unref(subnet1);
- loc_network_unref(subnet2);
+ if (loc_network_cmp(other, subnet1) == 0) {
+ r = loc_network_list_push(list, subnet2);
+ if (r)
+ goto ERROR;
- return list;
+ } else if (loc_network_cmp(other, subnet2) == 0) {
+ r = loc_network_list_push(list, subnet1);
+ if (r)
+ goto ERROR;
+
+ } else if (loc_network_is_subnet(subnet1, other)) {
+ r = loc_network_list_push(list, subnet2);
+ if (r)
+ goto ERROR;
+
+ r = __loc_network_exclude(subnet1, other, list);
+ if (r)
+ goto ERROR;
+
+ } else if (loc_network_is_subnet(subnet2, other)) {
+ r = loc_network_list_push(list, subnet1);
+ if (r)
+ goto ERROR;
+
+ r = __loc_network_exclude(subnet2, other, list);
+ if (r)
+ goto ERROR;
+
+ } else {
+ ERROR(network->ctx, "We should never get here\n");
+ r = 1;
+ goto ERROR;
+ }
ERROR:
if (subnet1)
if (subnet2)
loc_network_unref(subnet2);
- if (list)
- loc_network_list_unref(list);
+ return r;
+}
- return NULL;
+static int __loc_network_exclude_to_list(struct loc_network* self,
+ struct loc_network* other, struct loc_network_list* list) {
+ // Other must be a subnet of self
+ if (!loc_network_is_subnet(self, other)) {
+ DEBUG(self->ctx, "Network %p is not contained in network %p\n", other, self);
+
+ // Exit silently
+ return 0;
+ }
+
+ // We cannot perform this operation if both networks equal
+ if (loc_network_cmp(self, other) == 0) {
+ DEBUG(self->ctx, "Networks %p and %p are equal\n", self, other);
+
+ // Exit silently
+ return 0;
+ }
+
+ return __loc_network_exclude(self, other, list);
}
LOC_EXPORT struct loc_network_list* loc_network_exclude(
free(n2);
#endif
- // Family must match
- if (self->family != other->family) {
- DEBUG(self->ctx, "Family mismatch\n");
+ // Create a new list with the result
+ int r = loc_network_list_new(self->ctx, &list);
+ if (r) {
+ ERROR(self->ctx, "Could not create network list: %d\n", r);
return NULL;
}
- // Other must be a subnet of self
- if (!loc_network_is_subnet_of(other, self)) {
- DEBUG(self->ctx, "Network %p is not contained in network %p\n", other, self);
+ r = __loc_network_exclude_to_list(self, other, list);
+ if (r) {
+ loc_network_list_unref(list);
return NULL;
}
- // We cannot perform this operation if both networks equal
- if (loc_network_eq(self, other)) {
- DEBUG(self->ctx, "Networks %p and %p are equal\n", self, other);
+ // Return the result
+ return list;
+}
+
+LOC_EXPORT struct loc_network_list* loc_network_exclude_list(
+ struct loc_network* network, struct loc_network_list* list) {
+ struct loc_network_list* to_check;
+ // Create a new list with all networks to look at
+ int r = loc_network_list_new(network->ctx, &to_check);
+ if (r)
return NULL;
+
+ struct loc_network* subnet = NULL;
+ struct loc_network_list* subnets = NULL;
+
+ for (unsigned int i = 0; i < loc_network_list_size(list); i++) {
+ subnet = loc_network_list_get(list, i);
+
+ // Find all excluded networks
+ if (!loc_network_list_contains(to_check, subnet)) {
+ r = __loc_network_exclude_to_list(network, subnet, to_check);
+ if (r) {
+ loc_network_list_unref(to_check);
+ loc_network_unref(subnet);
+
+ return NULL;
+ }
+ }
+
+ // Cleanup
+ loc_network_unref(subnet);
}
- // Create a new list with the result
- int r = loc_network_list_new(self->ctx, &list);
+ r = loc_network_list_new(network->ctx, &subnets);
if (r) {
- ERROR(self->ctx, "Could not create network list: %d\n", r);
+ loc_network_list_unref(to_check);
return NULL;
}
- struct loc_network_list* subnets = loc_network_subnets(self);
+ off_t smallest_subnet = 0;
- struct loc_network* subnet1 = NULL;
- struct loc_network* subnet2 = NULL;
+ while (!loc_network_list_empty(to_check)) {
+ struct loc_network* subnet_to_check = loc_network_list_pop_first(to_check);
- while (subnets) {
- // Fetch both subnets
- subnet1 = loc_network_list_get(subnets, 0);
- subnet2 = loc_network_list_get(subnets, 1);
+ // Check whether the subnet to check is part of the input list
+ if (loc_network_list_contains(list, subnet_to_check)) {
+ loc_network_unref(subnet_to_check);
+ continue;
+ }
- // Free list
- loc_network_list_unref(subnets);
- subnets = NULL;
+ // Marks whether this subnet passed all checks
+ int passed = 1;
- if (loc_network_eq(other, subnet1)) {
- r = loc_network_list_push(list, subnet2);
- if (r)
- goto ERROR;
+ for (unsigned int i = smallest_subnet; i < loc_network_list_size(list); i++) {
+ subnet = loc_network_list_get(list, i);
- } else if (loc_network_eq(other, subnet2)) {
- r = loc_network_list_push(list, subnet1);
- if (r)
- goto ERROR;
+ // Drop this subnet if is a subnet of another subnet
+ if (loc_network_is_subnet(subnet, subnet_to_check)) {
+ passed = 0;
+ loc_network_unref(subnet);
+ break;
+ }
- } else if (loc_network_is_subnet_of(other, subnet1)) {
- r = loc_network_list_push(list, subnet2);
- if (r)
- goto ERROR;
+ // Break it down if it overlaps
+ if (loc_network_overlaps(subnet, subnet_to_check)) {
+ passed = 0;
- subnets = loc_network_subnets(subnet1);
+ __loc_network_exclude_to_list(subnet_to_check, subnet, to_check);
- } else if (loc_network_is_subnet_of(other, subnet2)) {
- r = loc_network_list_push(list, subnet1);
- if (r)
- goto ERROR;
+ loc_network_unref(subnet);
+ break;
+ }
- subnets = loc_network_subnets(subnet2);
+ // If the subnet is strictly greater, we do not need to continue the search
+ r = loc_network_cmp(subnet, subnet_to_check);
+ if (r > 0) {
+ loc_network_unref(subnet);
+ break;
+
+ // If it is strictly smaller, we can continue the search from here next
+ // time because all networks that are to be checked can only be larger
+ // than this one.
+ } else if (r < 0) {
+ smallest_subnet = i;
+ }
- } else {
- ERROR(self->ctx, "We should never get here\n");
- goto ERROR;
+ loc_network_unref(subnet);
}
- loc_network_unref(subnet1);
- loc_network_unref(subnet2);
- }
-
-#ifdef ENABLE_DEBUG
- loc_network_list_dump(list);
-#endif
-
- // Return the result
- return list;
-
-ERROR:
- if (subnet1)
- loc_network_unref(subnet1);
+ if (passed) {
+ r = loc_network_list_push(subnets, subnet_to_check);
+ }
- if (subnet2)
- loc_network_unref(subnet2);
+ loc_network_unref(subnet_to_check);
+ }
- if (list)
- loc_network_list_unref(list);
+ loc_network_list_unref(to_check);
- return NULL;
+ return subnets;
}
LOC_EXPORT int loc_network_to_database_v1(struct loc_network* network, struct loc_database_network_v1* dbobj) {
struct loc_network* network;
};
-LOC_EXPORT int loc_network_tree_new(struct loc_ctx* ctx, struct loc_network_tree** tree) {
+int loc_network_tree_new(struct loc_ctx* ctx, struct loc_network_tree** tree) {
struct loc_network_tree* t = calloc(1, sizeof(*t));
if (!t)
return -ENOMEM;
return 0;
}
-LOC_EXPORT struct loc_network_tree_node* loc_network_tree_get_root(struct loc_network_tree* tree) {
+struct loc_network_tree_node* loc_network_tree_get_root(struct loc_network_tree* tree) {
return loc_network_tree_node_ref(tree->root);
}
return 0;
}
-LOC_EXPORT int loc_network_tree_walk(struct loc_network_tree* tree,
+int loc_network_tree_walk(struct loc_network_tree* tree,
int(*filter_callback)(struct loc_network* network, void* data),
int(*callback)(struct loc_network* network, void* data), void* data) {
return __loc_network_tree_walk(tree->ctx, tree->root, filter_callback, callback, data);
free(tree);
}
-LOC_EXPORT struct loc_network_tree* loc_network_tree_unref(struct loc_network_tree* tree) {
+struct loc_network_tree* loc_network_tree_unref(struct loc_network_tree* tree) {
if (--tree->refcount > 0)
return tree;
return 0;
}
-LOC_EXPORT int loc_network_tree_dump(struct loc_network_tree* tree) {
+int loc_network_tree_dump(struct loc_network_tree* tree) {
DEBUG(tree->ctx, "Dumping network tree at %p\n", tree);
return loc_network_tree_walk(tree, NULL, __loc_network_tree_dump, NULL);
}
-LOC_EXPORT int loc_network_tree_add_network(struct loc_network_tree* tree, struct loc_network* network) {
+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,
return 0;
}
-LOC_EXPORT size_t loc_network_tree_count_networks(struct loc_network_tree* tree) {
+size_t loc_network_tree_count_networks(struct loc_network_tree* tree) {
size_t counter = 0;
int r = loc_network_tree_walk(tree, NULL, __loc_network_tree_count, &counter);
return counter;
}
-LOC_EXPORT size_t loc_network_tree_count_nodes(struct loc_network_tree* tree) {
+size_t loc_network_tree_count_nodes(struct loc_network_tree* tree) {
return __loc_network_tree_count_nodes(tree->root);
}
-LOC_EXPORT int loc_network_tree_node_new(struct loc_ctx* ctx, struct loc_network_tree_node** node) {
+int loc_network_tree_node_new(struct loc_ctx* ctx, struct loc_network_tree_node** node) {
struct loc_network_tree_node* n = calloc(1, sizeof(*n));
if (!n)
return -ENOMEM;
return 0;
}
-LOC_EXPORT struct loc_network_tree_node* loc_network_tree_node_ref(struct loc_network_tree_node* node) {
+struct loc_network_tree_node* loc_network_tree_node_ref(struct loc_network_tree_node* node) {
if (node)
node->refcount++;
free(node);
}
-LOC_EXPORT struct loc_network_tree_node* loc_network_tree_node_unref(struct loc_network_tree_node* node) {
+struct loc_network_tree_node* loc_network_tree_node_unref(struct loc_network_tree_node* node) {
if (!node)
return NULL;
return NULL;
}
-LOC_EXPORT struct loc_network_tree_node* loc_network_tree_node_get(struct loc_network_tree_node* node, unsigned int index) {
+struct loc_network_tree_node* loc_network_tree_node_get(struct loc_network_tree_node* node, unsigned int index) {
if (index == 0)
node = node->zero;
else
return loc_network_tree_node_ref(node);
}
-LOC_EXPORT int loc_network_tree_node_is_leaf(struct loc_network_tree_node* node) {
+int loc_network_tree_node_is_leaf(struct loc_network_tree_node* node) {
return (!!node->network);
}
-LOC_EXPORT struct loc_network* loc_network_tree_node_get_network(struct loc_network_tree_node* node) {
+struct loc_network* loc_network_tree_node_get_network(struct loc_network_tree_node* node) {
return loc_network_ref(node->network);
}
-
-// List
-
-struct loc_network_list {
- struct loc_ctx* ctx;
- int refcount;
-
- struct loc_network* list[1024];
- size_t size;
- size_t max_size;
-};
-
-LOC_EXPORT int loc_network_list_new(struct loc_ctx* ctx,
- struct loc_network_list** list) {
- struct loc_network_list* l = calloc(1, sizeof(*l));
- if (!l)
- return -ENOMEM;
-
- l->ctx = loc_ref(ctx);
- l->refcount = 1;
-
- // Do not allow this list to grow larger than this
- l->max_size = 1024;
-
- DEBUG(l->ctx, "Network list allocated at %p\n", l);
- *list = l;
- return 0;
-}
-
-LOC_EXPORT struct loc_network_list* loc_network_list_ref(struct loc_network_list* list) {
- list->refcount++;
-
- return list;
-}
-
-static void loc_network_list_free(struct loc_network_list* list) {
- DEBUG(list->ctx, "Releasing network list at %p\n", list);
-
- for (unsigned int i = 0; i < list->size; i++)
- loc_network_unref(list->list[i]);
-
- loc_unref(list->ctx);
- free(list);
-}
-
-LOC_EXPORT struct loc_network_list* loc_network_list_unref(struct loc_network_list* list) {
- if (!list)
- return NULL;
-
- if (--list->refcount > 0)
- return list;
-
- loc_network_list_free(list);
- return NULL;
-}
-
-LOC_EXPORT size_t loc_network_list_size(struct loc_network_list* list) {
- return list->size;
-}
-
-LOC_EXPORT int loc_network_list_empty(struct loc_network_list* list) {
- return list->size == 0;
-}
-
-LOC_EXPORT void loc_network_list_clear(struct loc_network_list* list) {
- for (unsigned int i = 0; i < list->size; i++)
- loc_network_unref(list->list[i]);
-
- list->size = 0;
-}
-
-LOC_EXPORT void loc_network_list_dump(struct loc_network_list* list) {
- struct loc_network* network;
- char* s;
-
- for (unsigned int i = 0; i < list->size; i++) {
- network = list->list[i];
-
- s = loc_network_str(network);
-
- INFO(list->ctx, "%s\n", s);
- free(s);
- }
-}
-
-LOC_EXPORT struct loc_network* loc_network_list_get(struct loc_network_list* list, size_t index) {
- // Check index
- if (index >= list->size)
- return NULL;
-
- return loc_network_ref(list->list[index]);
-}
-
-LOC_EXPORT int loc_network_list_push(struct loc_network_list* list, struct loc_network* network) {
- // Do not add networks that are already on the list
- if (loc_network_list_contains(list, network))
- return 0;
-
- // Check if we have space left
- if (list->size == list->max_size)
- return -ENOMEM;
-
- list->list[list->size++] = loc_network_ref(network);
-
- return 0;
-}
-
-LOC_EXPORT struct loc_network* loc_network_list_pop(struct loc_network_list* list) {
- // Return nothing when empty
- if (loc_network_list_empty(list))
- return NULL;
-
- return list->list[--list->size];
-}
-
-LOC_EXPORT int loc_network_list_contains(struct loc_network_list* list, struct loc_network* network) {
- for (unsigned int i = 0; i < list->size; i++) {
- if (loc_network_eq(list->list[i], network))
- return 1;
- }
-
- return 0;
-}
-
-static void loc_network_list_swap(struct loc_network_list* list, unsigned int i1, unsigned int i2) {
- // Do nothing for invalid indices
- if (i1 >= list->size || i2 >= list->size)
- return;
-
- struct loc_network* network1 = list->list[i1];
- struct loc_network* network2 = list->list[i2];
-
- list->list[i1] = network2;
- list->list[i2] = network1;
-}
-
-LOC_EXPORT void loc_network_list_reverse(struct loc_network_list* list) {
- unsigned int i = 0;
- unsigned int j = list->size - 1;
-
- while (i < j) {
- loc_network_list_swap(list, i++, j--);
- }
-}
-
-LOC_EXPORT void loc_network_list_sort(struct loc_network_list* list) {
- unsigned int n = list->size;
- int swapped;
-
- do {
- swapped = 0;
-
- for (unsigned int i = 1; i < n; i++) {
- if (loc_network_gt(list->list[i-1], list->list[i]) > 0) {
- loc_network_list_swap(list, i-1, i);
- swapped = 1;
- }
- }
-
- n--;
- } while (swapped);
-}
-
-LOC_EXPORT int loc_network_list_merge(
- struct loc_network_list* self, struct loc_network_list* other) {
- int r;
-
- for (unsigned int i = 0; i < other->size; i++) {
- r = loc_network_list_push(self, other->list[i]);
- if (r)
- return r;
- }
-
- return 0;
-}