src/network.c

   1 /*
   2         libloc - A library to determine the location of someone on the Internet
   3
   4         Copyright (C) 2017 IPFire Development Team <info@ipfire.org>
   5
   6         This library is free software; you can redistribute it and/or
   7         modify it under the terms of the GNU Lesser General Public
   8         License as published by the Free Software Foundation; either
   9         version 2.1 of the License, or (at your option) any later version.
  10
  11         This library is distributed in the hope that it will be useful,
  12         but WITHOUT ANY WARRANTY; without even the implied warranty of
  13         MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14         Lesser General Public License for more details.
  15 */
  16
  17 #include <arpa/inet.h>
  18 #include <assert.h>
  19 #include <endian.h>
  20 #include <errno.h>
  21 #include <stdio.h>
  22 #include <stdlib.h>
  23 #include <string.h>
  24
  25 #include <loc/libloc.h>
  26 #include <loc/network.h>
  27 #include <loc/private.h>
  28
  29 struct loc_network {
  30         struct loc_ctx* ctx;
  31         int refcount;
  32
  33         struct in6_addr start_address;
  34         unsigned int prefix;
  35
  36         char country_code[3];
  37         uint32_t asn;
  38 };
  39
  40 static int valid_prefix(struct in6_addr* address, unsigned int prefix) {
  41         // The prefix cannot be larger than 128 bits
  42         if (prefix > 128)
  43                 return 1;
  44
  45         // And the prefix cannot be zero
  46         if (prefix == 0)
  47                 return 1;
  48
  49         // For IPv4-mapped addresses the prefix has to be 96 or lager
  50         if (IN6_IS_ADDR_V4MAPPED(address) && prefix <= 96)
  51                 return 1;
  52
  53         return 0;
  54 }
  55
  56 LOC_EXPORT int loc_network_new(struct loc_ctx* ctx, struct loc_network** network,
  57                 struct in6_addr start_address, unsigned int prefix) {
  58         // Address cannot be unspecified
  59         if (IN6_IS_ADDR_UNSPECIFIED(&start_address)) {
  60                 DEBUG(ctx, "Start address is unspecified\n");
  61                 return -EINVAL;
  62         }
  63
  64         // Address cannot be loopback
  65         if (IN6_IS_ADDR_LOOPBACK(&start_address)) {
  66                 DEBUG(ctx, "Start address is loopback address\n");
  67                 return -EINVAL;
  68         }
  69
  70         // Address cannot be link-local
  71         if (IN6_IS_ADDR_LINKLOCAL(&start_address)) {
  72                 DEBUG(ctx, "Start address cannot be link-local\n");
  73                 return -EINVAL;
  74         }
  75
  76         // Address cannot be site-local
  77         if (IN6_IS_ADDR_SITELOCAL(&start_address)) {
  78                 DEBUG(ctx, "Start address cannot be site-local\n");
  79                 return -EINVAL;
  80         }
  81
  82         // Validate the prefix
  83         if (valid_prefix(&start_address, prefix) != 0) {
  84                 DEBUG(ctx, "Invalid prefix: %u\n", prefix);
  85                 return -EINVAL;
  86         }
  87
  88         struct loc_network* n = calloc(1, sizeof(*n));
  89         if (!n)
  90                 return -ENOMEM;
  91
  92         n->ctx = loc_ref(ctx);
  93         n->refcount = 1;
  94
  95         n->start_address = start_address;
  96         n->prefix = prefix;
  97
  98         DEBUG(n->ctx, "Network allocated at %p\n", n);
  99         *network = n;
 100         return 0;
 101 }
 102
 103 static int loc_network_address_family(struct loc_network* network) {
 104         if (IN6_IS_ADDR_V4MAPPED(&network->start_address))
 105                 return AF_INET;
 106
 107         return AF_INET6;
 108 }
 109
 110 static int parse_address(struct loc_ctx* ctx, const char* string, struct in6_addr* address) {
 111         DEBUG(ctx, "Paring IP address %s\n", string);
 112
 113         // Try parsing this as an IPv6 address
 114         int r = inet_pton(AF_INET6, string, address);
 115
 116         // If inet_pton returns one it has been successful
 117         if (r == 1) {
 118                 DEBUG(ctx, "%s is an IPv6 address\n", string);
 119                 return 0;
 120         }
 121
 122         // Try parsing this as an IPv4 address
 123         struct in_addr ipv4_address;
 124         r = inet_pton(AF_INET, string, &ipv4_address);
 125         if (r == 1) {
 126                 DEBUG(ctx, "%s is an IPv4 address\n", string);
 127
 128                 // Convert to IPv6-mapped address
 129                 address->s6_addr32[0] = htonl(0x0000);
 130                 address->s6_addr32[1] = htonl(0x0000);
 131                 address->s6_addr32[2] = htonl(0xffff);
 132                 address->s6_addr32[3] = ipv4_address.s_addr;
 133
 134                 return 0;
 135         }
 136
 137         DEBUG(ctx, "%s is not an valid IP address\n", string);
 138         return 1;
 139 }
 140
 141 LOC_EXPORT int loc_network_new_from_string(struct loc_ctx* ctx, struct loc_network** network,
 142                 const char* address_string) {
 143         struct in6_addr start_address;
 144         unsigned int prefix = 0;
 145         char* prefix_string;
 146         int r = 1;
 147
 148         // Make a copy of the string to work on it
 149         char* buffer = strdup(address_string);
 150         address_string = prefix_string = buffer;
 151
 152         // Split address and prefix
 153         address_string = strsep(&prefix_string, "/");
 154
 155         // Did we find a prefix?
 156         if (prefix_string) {
 157                 // Convert prefix to integer
 158                 prefix = strtol(prefix_string, NULL, 10);
 159
 160                 if (prefix) {
 161                         // Parse the address
 162                         r = parse_address(ctx, address_string, &start_address);
 163
 164                         // Map the prefix to IPv6 if needed
 165                         if (IN6_IS_ADDR_V4MAPPED(&start_address))
 166                                 prefix += 96;
 167                 }
 168         }
 169
 170         // Free temporary buffer
 171         free(buffer);
 172
 173         if (r == 0) {
 174                 r = loc_network_new(ctx, network, start_address, prefix);
 175         }
 176
 177         return r;
 178 }
 179
 180 LOC_EXPORT struct loc_network* loc_network_ref(struct loc_network* network) {
 181         network->refcount++;
 182
 183         return network;
 184 }
 185
 186 static void loc_network_free(struct loc_network* network) {
 187         DEBUG(network->ctx, "Releasing network at %p\n", network);
 188
 189         loc_unref(network->ctx);
 190         free(network);
 191 }
 192
 193 LOC_EXPORT struct loc_network* loc_network_unref(struct loc_network* network) {
 194         if (--network->refcount > 0)
 195                 return network;
 196
 197         loc_network_free(network);
 198         return NULL;
 199 }
 200
 201 static int format_ipv6_address(struct loc_network* network, char* string, size_t length) {
 202         const char* ret = inet_ntop(AF_INET6, &network->start_address, string, length);
 203         if (!ret)
 204                 return -1;
 205
 206         return 0;
 207 }
 208
 209 static int format_ipv4_address(struct loc_network* network, char* string, size_t length) {
 210         struct in_addr ipv4_address;
 211         ipv4_address.s_addr = network->start_address.s6_addr32[3];
 212
 213         const char* ret = inet_ntop(AF_INET, &ipv4_address, string, length);
 214         if (!ret)
 215                 return -1;
 216
 217         return 0;
 218 }
 219
 220 LOC_EXPORT char* loc_network_str(struct loc_network* network) {
 221         int r;
 222         const size_t length = INET6_ADDRSTRLEN + 4;
 223
 224         char* string = malloc(length);
 225         if (!string)
 226                 return NULL;
 227
 228         unsigned int prefix = network->prefix;
 229
 230         int family = loc_network_address_family(network);
 231         switch (family) {
 232                 case AF_INET6:
 233                         r = format_ipv6_address(network, string, length);
 234                         break;
 235
 236                 case AF_INET:
 237                         r = format_ipv4_address(network, string, length);
 238                         prefix -= 96;
 239                         break;
 240
 241                 default:
 242                         r = -1;
 243                         break;
 244         }
 245
 246         if (r) {
 247                 ERROR(network->ctx, "Could not convert network to string: %s\n", strerror(errno));
 248                 free(string);
 249
 250                 return NULL;
 251         }
 252
 253         // Append prefix
 254         sprintf(string + strlen(string), "/%u", prefix);
 255
 256         return string;
 257 }
 258
 259 LOC_EXPORT const char* loc_network_get_country_code(struct loc_network* network) {
 260         return network->country_code;
 261 }
 262
 263 LOC_EXPORT int loc_network_set_country_code(struct loc_network* network, const char* country_code) {
 264         // Country codes must be two characters
 265         if (strlen(country_code) != 2)
 266                 return -EINVAL;
 267
 268         for (unsigned int i = 0; i < 3; i++) {
 269                 network->country_code[i] = country_code[i];
 270         }
 271
 272         return 0;
 273 }
 274
 275 LOC_EXPORT uint32_t loc_network_get_asn(struct loc_network* network) {
 276         return network->asn;
 277 }
 278
 279 LOC_EXPORT int loc_network_set_asn(struct loc_network* network, uint32_t asn) {
 280         network->asn = asn;
 281
 282         return 0;
 283 }
 284
 285 LOC_EXPORT int loc_network_to_database_v0(struct loc_network* network, struct loc_database_network_v0* dbobj) {
 286         dbobj->prefix = htobe16(network->prefix);
 287
 288         // Add country code
 289         for (unsigned int i = 0; i < 2; i++) {
 290                 dbobj->country_code[i] = network->country_code ? network->country_code[i] : '\0';
 291         }
 292
 293         // Add ASN
 294         dbobj->asn = htobe32(network->asn);
 295
 296         return 0;
 297 }
 298
 299 struct loc_network_tree {
 300         struct loc_ctx* ctx;
 301         int refcount;
 302
 303         struct loc_network_tree_node* root;
 304 };
 305
 306 struct loc_network_tree_node {
 307         struct loc_network_tree_node* zero;
 308         struct loc_network_tree_node* one;
 309
 310         struct loc_network* network;
 311 };
 312
 313 LOC_EXPORT int loc_network_tree_new(struct loc_ctx* ctx, struct loc_network_tree** tree) {
 314         struct loc_network_tree* t = calloc(1, sizeof(*t));
 315         if (!t)
 316                 return -ENOMEM;
 317
 318         t->ctx = loc_ref(ctx);
 319         t->refcount = 1;
 320
 321         // Create the root node
 322         t->root = calloc(1, sizeof(*t->root));
 323
 324         DEBUG(t->ctx, "Network tree allocated at %p\n", t);
 325         *tree = t;
 326         return 0;
 327 }
 328
 329 static int loc_network_tree_node_new(struct loc_network_tree_node** node) {
 330         struct loc_network_tree_node* n = calloc(1, sizeof(*n));
 331         if (!n)
 332                 return -ENOMEM;
 333
 334         n->zero = n->one = NULL;
 335
 336         *node = n;
 337         return 0;
 338 }
 339
 340 static struct loc_network_tree_node* loc_network_tree_get_node(struct loc_network_tree_node* node, int path) {
 341         struct loc_network_tree_node** n;
 342
 343         if (path)
 344                 n = &node->one;
 345         else
 346                 n = &node->zero;
 347
 348         // If the desired node doesn't exist, yet, we will create it
 349         if (*n == NULL) {
 350                 int r = loc_network_tree_node_new(n);
 351                 if (r)
 352                         return NULL;
 353         }
 354
 355         return *n;
 356 }
 357
 358 static struct loc_network_tree_node* loc_network_tree_get_path(struct loc_network_tree* tree, const struct in6_addr* address) {
 359         struct loc_network_tree_node* node = tree->root;
 360
 361         for (unsigned int i = 127; i > 0; i--) {
 362                 // Check if the ith bit is one or zero
 363                 node = loc_network_tree_get_node(node, ((address->s6_addr32[i / 32] & (1 << (i % 32))) == 0));
 364         }
 365
 366         return node;
 367 }
 368
 369 static int __loc_network_tree_walk(struct loc_ctx* ctx, struct loc_network_tree_node* node,
 370                 int(*filter_callback)(struct loc_network* network, void* data),
 371                 int(*callback)(struct loc_network* network, void* data), void* data) {
 372         int r;
 373
 374         // Finding a network ends the walk here
 375         if (node->network) {
 376                 if (filter_callback) {
 377                         int f = filter_callback(node->network, data);
 378                         if (f < 0)
 379                                 return f;
 380
 381                         // Skip network if filter function returns value greater than zero
 382                         if (f > 0)
 383                                 return 0;
 384                 }
 385
 386                 r = callback(node->network, data);
 387                 if (r)
 388                         return r;
 389         }
 390
 391         // Walk down on the left side of the tree first
 392         if (node->zero) {
 393                 r = __loc_network_tree_walk(ctx, node->zero, filter_callback, callback, data);
 394                 if (r)
 395                         return r;
 396         }
 397
 398         // Then walk on the other side
 399         if (node->one) {
 400                 r = __loc_network_tree_walk(ctx, node->one, filter_callback, callback, data);
 401                 if (r)
 402                         return r;
 403         }
 404
 405         return 0;
 406 }
 407
 408 LOC_EXPORT int loc_network_tree_walk(struct loc_network_tree* tree,
 409                 int(*filter_callback)(struct loc_network* network, void* data),
 410                 int(*callback)(struct loc_network* network, void* data), void* data) {
 411         return __loc_network_tree_walk(tree->ctx, tree->root, filter_callback, callback, data);
 412 }
 413
 414 static void loc_network_tree_free_subtree(struct loc_network_tree_node* node) {
 415         if (node->network)
 416                 loc_network_unref(node->network);
 417
 418         if (node->zero)
 419                 loc_network_tree_free_subtree(node->zero);
 420
 421         if (node->one)
 422                 loc_network_tree_free_subtree(node->one);
 423
 424         free(node);
 425 }
 426
 427 static void loc_network_tree_free(struct loc_network_tree* tree) {
 428         DEBUG(tree->ctx, "Releasing network tree at %p\n", tree);
 429
 430         loc_network_tree_free_subtree(tree->root);
 431
 432         loc_unref(tree->ctx);
 433         free(tree);
 434 }
 435
 436 LOC_EXPORT struct loc_network_tree* loc_network_tree_unref(struct loc_network_tree* tree) {
 437         if (--tree->refcount > 0)
 438                 return tree;
 439
 440         loc_network_tree_free(tree);
 441         return NULL;
 442 }
 443
 444 int __loc_network_tree_dump(struct loc_network* network, void* data) {
 445         DEBUG(network->ctx, "Dumping network at %p\n", network);
 446
 447         char* s = loc_network_str(network);
 448         if (!s)
 449                 return 1;
 450
 451         INFO(network->ctx, "%s\n", s);
 452         free(s);
 453
 454         return 0;
 455 }
 456
 457 LOC_EXPORT int loc_network_tree_dump(struct loc_network_tree* tree) {
 458         DEBUG(tree->ctx, "Dumping network tree at %p\n", tree);
 459
 460         return loc_network_tree_walk(tree, NULL, __loc_network_tree_dump, NULL);
 461 }
 462
 463 LOC_EXPORT int loc_network_tree_add_network(struct loc_network_tree* tree, struct loc_network* network) {
 464         DEBUG(tree->ctx, "Adding network %p to tree %p\n", network, tree);
 465
 466         struct loc_network_tree_node* node = loc_network_tree_get_path(tree, &network->start_address);
 467         if (!node) {
 468                 ERROR(tree->ctx, "Could not find a node\n");
 469                 return -ENOMEM;
 470         }
 471
 472         // Check if node has not been set before
 473         if (node->network) {
 474                 DEBUG(tree->ctx, "There is already a network at this path\n");
 475                 return 1;
 476         }
 477
 478         // Point node to the network
 479         node->network = loc_network_ref(network);
 480
 481         return 0;
 482 }
 483
 484 static int __loc_network_tree_count(struct loc_network* network, void* data) {
 485         size_t* counter = (size_t*)data;
 486
 487         // Increase the counter for each network
 488         counter++;
 489
 490         return 0;
 491 }
 492
 493 LOC_EXPORT size_t loc_network_tree_count_networks(struct loc_network_tree* tree) {
 494         size_t counter = 0;
 495
 496         int r = loc_network_tree_walk(tree, NULL, __loc_network_tree_count, &counter);
 497         if (r)
 498                 return r;
 499
 500         return counter;
 501 }