struct loc_ctx* ctx;
int refcount;
- struct in6_addr start_address;
+ int family;
+ struct in6_addr first_address;
+ struct in6_addr last_address;
unsigned int prefix;
char country_code[3];
return bitmask;
}
-static struct in6_addr make_start_address(const struct in6_addr* address, unsigned int prefix) {
+static struct in6_addr make_first_address(const struct in6_addr* address, const struct in6_addr* bitmask) {
struct in6_addr a;
- struct in6_addr bitmask = prefix_to_bitmask(prefix);
// Perform bitwise AND
for (unsigned int i = 0; i < 4; i++)
- a.s6_addr32[i] = address->s6_addr32[i] & bitmask.s6_addr32[i];
+ a.s6_addr32[i] = address->s6_addr32[i] & bitmask->s6_addr32[i];
return a;
}
-static struct in6_addr make_last_address(const struct in6_addr* address, unsigned int prefix) {
+static struct in6_addr make_last_address(const struct in6_addr* address, const struct in6_addr* bitmask) {
struct in6_addr a;
- struct in6_addr bitmask = prefix_to_bitmask(prefix);
// Perform bitwise OR
for (unsigned int i = 0; i < 4; i++)
- a.s6_addr32[i] = address->s6_addr32[i] | ~bitmask.s6_addr32[i];
+ a.s6_addr32[i] = address->s6_addr32[i] | ~bitmask->s6_addr32[i];
+
+ return a;
+}
+
+static struct in6_addr address_increment(const struct in6_addr* address) {
+ struct in6_addr a = *address;
+
+ for (int octet = 15; octet >= 0; octet--) {
+ if (a.s6_addr[octet] < 255) {
+ a.s6_addr[octet]++;
+ break;
+ } else {
+ a.s6_addr[octet] = 0;
+ }
+ }
return a;
}
n->ctx = loc_ref(ctx);
n->refcount = 1;
- // Store the first address in the network
- n->start_address = make_start_address(address, prefix);
+ // Store the prefix
n->prefix = prefix;
+ // Convert the prefix into a bitmask
+ struct in6_addr bitmask = prefix_to_bitmask(n->prefix);
+
+ // Store the first and last address in the network
+ n->first_address = make_first_address(address, &bitmask);
+ n->last_address = make_last_address(&n->first_address, &bitmask);
+
+ // Set family
+ if (IN6_IS_ADDR_V4MAPPED(&n->first_address))
+ n->family = AF_INET;
+ else
+ n->family = AF_INET6;
+
DEBUG(n->ctx, "Network allocated at %p\n", n);
*network = n;
return 0;
}
-static int loc_network_address_family(struct loc_network* network) {
- if (IN6_IS_ADDR_V4MAPPED(&network->start_address))
- return AF_INET;
-
- return AF_INET6;
-}
-
LOC_EXPORT int loc_network_new_from_string(struct loc_ctx* ctx, struct loc_network** network,
const char* address_string) {
- struct in6_addr start_address;
- unsigned int prefix = 0;
+ struct in6_addr first_address;
char* prefix_string;
- int r = 1;
+ unsigned int prefix = 128;
+ int r = -EINVAL;
+
+ DEBUG(ctx, "Attempting to parse network %s\n", address_string);
// Make a copy of the string to work on it
char* buffer = strdup(address_string);
// Split address and prefix
address_string = strsep(&prefix_string, "/");
- // Did we find a prefix?
+ DEBUG(ctx, " Split into address = %s, prefix = %s\n", address_string, prefix_string);
+
+ // Parse the address
+ r = loc_parse_address(ctx, address_string, &first_address);
+ if (r) {
+ DEBUG(ctx, "The address could not be parsed\n");
+ goto FAIL;
+ }
+
+ // If a prefix was given, we will try to parse it
if (prefix_string) {
// Convert prefix to integer
prefix = strtol(prefix_string, NULL, 10);
- if (prefix) {
- // Parse the address
- r = loc_parse_address(ctx, address_string, &start_address);
-
- // Map the prefix to IPv6 if needed
- if (IN6_IS_ADDR_V4MAPPED(&start_address))
- prefix += 96;
+ if (!prefix) {
+ DEBUG(ctx, "The prefix was not parsable: %s\n", prefix_string);
+ goto FAIL;
}
+
+ // Map the prefix to IPv6 if needed
+ if (IN6_IS_ADDR_V4MAPPED(&first_address))
+ prefix += 96;
}
+FAIL:
// Free temporary buffer
free(buffer);
- if (r == 0) {
- r = loc_network_new(ctx, network, &start_address, prefix);
- }
+ // Exit if the parsing was unsuccessful
+ if (r)
+ return r;
- return r;
+ // Create a new network
+ return loc_network_new(ctx, network, &first_address, prefix);
}
LOC_EXPORT struct loc_network* loc_network_ref(struct loc_network* network) {
unsigned int prefix = network->prefix;
- int family = loc_network_address_family(network);
- switch (family) {
+ switch (network->family) {
case AF_INET6:
- r = format_ipv6_address(&network->start_address, string, length);
+ r = format_ipv6_address(&network->first_address, string, length);
break;
case AF_INET:
- r = format_ipv4_address(&network->start_address, string, length);
+ r = format_ipv4_address(&network->first_address, string, length);
prefix -= 96;
break;
return string;
}
+LOC_EXPORT int loc_network_address_family(struct loc_network* network) {
+ return network->family;
+}
+
+static char* loc_network_format_address(struct loc_network* network, const struct in6_addr* address) {
+ const size_t length = INET6_ADDRSTRLEN;
+
+ char* string = malloc(length);
+ if (!string)
+ return NULL;
+
+ int r = 0;
+
+ switch (network->family) {
+ case AF_INET6:
+ r = format_ipv6_address(address, string, length);
+ break;
+
+ case AF_INET:
+ r = format_ipv4_address(address, string, length);
+ break;
+
+ default:
+ r = -1;
+ break;
+ }
+
+ if (r) {
+ ERROR(network->ctx, "Could not format IP address to string: %s\n", strerror(errno));
+ free(string);
+
+ return NULL;
+ }
+
+ return string;
+}
+
+LOC_EXPORT char* loc_network_format_first_address(struct loc_network* network) {
+ return loc_network_format_address(network, &network->first_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->start_address, address) > 0)
+ if (in6_addr_cmp(&network->first_address, address) > 0)
return 1;
- // Determine the last address in this network
- struct in6_addr last_address = make_last_address(&network->start_address, network->prefix);
-
// Address must be smaller than the last address
- if (in6_addr_cmp(address, &last_address) > 0)
+ if (in6_addr_cmp(&network->last_address, address) < 0)
return 1;
// The address is inside this network
return loc_network_has_flag(network, flag);
}
-LOC_EXPORT int loc_network_to_database_v0(struct loc_network* network, struct loc_database_network_v0* dbobj) {
+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;
+
+ int r = in6_addr_cmp(&self->first_address, &other->first_address);
+
+ switch (r) {
+ // Smaller
+ case -1:
+ return 0;
+
+ // Larger
+ case 1:
+ return 1;
+
+ default:
+ break;
+ }
+
+ if (self->prefix > other->prefix)
+ return 1;
+
+ // Dunno
+ 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)
+ return 1;
+
+ if (loc_network_match_address(self, &other->last_address) == 0)
+ return 1;
+
+ if (loc_network_match_address(other, &self->first_address) == 0)
+ return 1;
+
+ if (loc_network_match_address(other, &self->last_address) == 0)
+ return 1;
+
+ return 0;
+}
+
+LOC_EXPORT int loc_network_is_subnet(struct loc_network* self, struct loc_network* other) {
+ // 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)
+ 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)
+ return 0;
+
+ return 1;
+}
+
+// XXX DEPRECATED - I find this too difficult to use
+LOC_EXPORT int loc_network_is_subnet_of(struct loc_network* self, struct loc_network* other) {
+ // 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)
+ 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)
+ return 0;
+
+ return 1;
+}
+
+LOC_EXPORT struct loc_network_list* loc_network_subnets(struct loc_network* network) {
+ struct loc_network_list* list;
+
+ // 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;
+
+ // Create the first half of the network
+ r = loc_network_new(network->ctx, &subnet1, &network->first_address, prefix);
+ if (r)
+ goto ERROR;
+
+ // The next subnet starts after the first one
+ 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);
+ if (r)
+ goto ERROR;
+
+ // Push the both onto the stack (in reverse order)
+ r = loc_network_list_push(list, subnet2);
+ if (r)
+ goto ERROR;
+
+ r = loc_network_list_push(list, subnet1);
+ 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);
+ }
+
+ // Copy ASN
+ uint32_t asn = loc_network_get_asn(network);
+ if (asn) {
+ loc_network_set_asn(subnet1, asn);
+ loc_network_set_asn(subnet2, asn);
+ }
+
+ loc_network_unref(subnet1);
+ loc_network_unref(subnet2);
+
+ return list;
+
+ERROR:
+ if (subnet1)
+ loc_network_unref(subnet1);
+
+ if (subnet2)
+ loc_network_unref(subnet2);
+
+ if (list)
+ loc_network_list_unref(list);
+
+ return NULL;
+}
+
+LOC_EXPORT struct loc_network_list* loc_network_exclude(
+ struct loc_network* self, struct loc_network* other) {
+ struct loc_network_list* list;
+
+#ifdef ENABLE_DEBUG
+ char* n1 = loc_network_str(self);
+ char* n2 = loc_network_str(other);
+
+ DEBUG(self->ctx, "Returning %s excluding %s...\n", n1, n2);
+
+ free(n1);
+ free(n2);
+#endif
+
+ // Family must match
+ if (self->family != other->family) {
+ DEBUG(self->ctx, "Family mismatch\n");
+
+ 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);
+
+ 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 NULL;
+ }
+
+ // 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;
+ }
+
+ struct loc_network_list* subnets = loc_network_subnets(self);
+
+ struct loc_network* subnet1 = NULL;
+ struct loc_network* subnet2 = NULL;
+
+ while (subnets) {
+ // Fetch both subnets
+ subnet1 = loc_network_list_get(subnets, 0);
+ subnet2 = loc_network_list_get(subnets, 1);
+
+ // Free list
+ loc_network_list_unref(subnets);
+ subnets = NULL;
+
+ if (loc_network_eq(other, subnet1)) {
+ r = loc_network_list_push(list, subnet2);
+ if (r)
+ goto ERROR;
+
+ } else if (loc_network_eq(other, subnet2)) {
+ r = loc_network_list_push(list, subnet1);
+ if (r)
+ goto ERROR;
+
+ } else if (loc_network_is_subnet_of(other, subnet1)) {
+ r = loc_network_list_push(list, subnet2);
+ if (r)
+ goto ERROR;
+
+ subnets = loc_network_subnets(subnet1);
+
+ } else if (loc_network_is_subnet_of(other, subnet2)) {
+ r = loc_network_list_push(list, subnet1);
+ if (r)
+ goto ERROR;
+
+ subnets = loc_network_subnets(subnet2);
+
+ } else {
+ ERROR(self->ctx, "We should never get here\n");
+ goto ERROR;
+ }
+
+ 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 (subnet2)
+ loc_network_unref(subnet2);
+
+ if (list)
+ loc_network_list_unref(list);
+
+ return NULL;
+}
+
+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
+ struct loc_network_list* excluded = loc_network_exclude(network, subnet);
+ if (excluded) {
+ // Add them all to the "to check" list
+ loc_network_list_merge(to_check, excluded);
+ loc_network_list_unref(excluded);
+ }
+
+ // Cleanup
+ loc_network_unref(subnet);
+ }
+
+ r = loc_network_list_new(network->ctx, &subnets);
+ if (r) {
+ loc_network_list_unref(to_check);
+ return NULL;
+ }
+
+ while (!loc_network_list_empty(to_check)) {
+ struct loc_network* subnet_to_check = loc_network_list_pop(to_check);
+
+ // Marks whether this subnet passed all checks
+ int passed = 1;
+
+ for (unsigned int i = 0; i < loc_network_list_size(list); i++) {
+ subnet = loc_network_list_get(list, i);
+
+ // Drop this subnet if is is already in list
+ if (loc_network_eq(subnet_to_check, subnet)) {
+ passed = 0;
+ loc_network_unref(subnet);
+ break;
+ }
+
+ // Drop this subnet if is a subnet of another subnet
+ if (loc_network_is_subnet_of(subnet, subnet_to_check)) {
+ passed = 0;
+ loc_network_unref(subnet);
+ break;
+ }
+
+ // Break it down if it overlaps
+ if (loc_network_overlaps(subnet_to_check, subnet)) {
+ passed = 0;
+
+ struct loc_network_list* excluded = loc_network_exclude(subnet_to_check, subnet);
+ if (excluded) {
+ loc_network_list_merge(to_check, excluded);
+ loc_network_list_unref(excluded);
+ }
+
+ loc_network_unref(subnet);
+ break;
+ }
+
+ loc_network_unref(subnet);
+ }
+
+ if (passed) {
+ r = loc_network_list_push(subnets, subnet_to_check);
+ }
+
+ loc_network_unref(subnet_to_check);
+ }
+
+ loc_network_list_unref(to_check);
+
+ return subnets;
+}
+
+LOC_EXPORT int loc_network_to_database_v1(struct loc_network* network, struct loc_database_network_v1* dbobj) {
// Add country code
loc_country_code_copy(dbobj->country_code, network->country_code);
return 0;
}
-LOC_EXPORT int loc_network_new_from_database_v0(struct loc_ctx* ctx, struct loc_network** network,
- struct in6_addr* address, unsigned int prefix, const struct loc_database_network_v0* dbobj) {
+LOC_EXPORT int loc_network_new_from_database_v1(struct loc_ctx* ctx, struct loc_network** network,
+ struct in6_addr* address, unsigned int prefix, const struct loc_database_network_v1* dbobj) {
char country_code[3] = "\0\0";
int r = loc_network_new(ctx, network, address, prefix);
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, network->prefix);
+ &network->first_address, network->prefix);
if (!node) {
ERROR(tree->ctx, "Could not find a node\n");
return -ENOMEM;
LOC_EXPORT 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) {
+ ERROR(list->ctx, "%p: Could not push network onto the stack: Stack full\n", list);
+ return -ENOMEM;
+ }
+
+ DEBUG(list->ctx, "%p: Pushing network %p onto stack\n", list, network);
+
+ 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)) {
+ DEBUG(list->ctx, "%p: Popped empty stack\n", list);
+ return NULL;
+ }
+
+ struct loc_network* network = list->list[--list->size];
+
+ DEBUG(list->ctx, "%p: Popping network %p from stack\n", list, network);
+
+ return network;
+}
+
+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;
+}
projects / people / ms / libloc.git / blobdiff