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 LOC_EXPORT int loc_network_new(struct loc_ctx* ctx, struct loc_network** network,
  41                 struct in6_addr start_address, unsigned int prefix) {
  42         // Address cannot be unspecified
  43         if (IN6_IS_ADDR_UNSPECIFIED(&start_address)) {
  44                 DEBUG(ctx, "Start address is unspecified\n");
  45                 return -EINVAL;
  46         }
  47
  48         // Address cannot be loopback
  49         if (IN6_IS_ADDR_LOOPBACK(&start_address)) {
  50                 DEBUG(ctx, "Start address is loopback address\n");
  51                 return -EINVAL;
  52         }
  53
  54         // Address cannot be link-local
  55         if (IN6_IS_ADDR_LINKLOCAL(&start_address)) {
  56                 DEBUG(ctx, "Start address cannot be link-local\n");
  57                 return -EINVAL;
  58         }
  59
  60         // Address cannot be site-local
  61         if (IN6_IS_ADDR_SITELOCAL(&start_address)) {
  62                 DEBUG(ctx, "Start address cannot be site-local\n");
  63                 return -EINVAL;
  64         }
  65
  66         struct loc_network* n = calloc(1, sizeof(*n));
  67         if (!n)
  68                 return -ENOMEM;
  69
  70         n->ctx = loc_ref(ctx);
  71         n->refcount = 1;
  72
  73         n->start_address = start_address;
  74         n->prefix = prefix;
  75
  76         DEBUG(n->ctx, "Network allocated at %p\n", n);
  77         *network = n;
  78         return 0;
  79 }
  80
  81 LOC_EXPORT int loc_network_new_from_string(struct loc_ctx* ctx, struct loc_network** network,
  82                 const char* address_string) {
  83         struct in6_addr start_address;
  84         char* prefix_string;
  85
  86         // Make a copy of the string to work on it
  87         char* buffer = strdup(address_string);
  88         address_string = prefix_string = buffer;
  89
  90         // Split address and prefix
  91         address_string = strsep(&prefix_string, "/");
  92
  93         // Convert prefix to integer
  94         unsigned int prefix = strtol(prefix_string, NULL, 10);
  95
  96         // Parse the address
  97         int r = inet_pton(AF_INET6, address_string, &start_address);
  98
  99         // Free temporary buffer
 100         free(buffer);
 101
 102         if (r == 1) {
 103                 r = loc_network_new(ctx, network, start_address, prefix);
 104         }
 105
 106         return r;
 107 }
 108
 109 LOC_EXPORT struct loc_network* loc_network_ref(struct loc_network* network) {
 110         network->refcount++;
 111
 112         return network;
 113 }
 114
 115 static void loc_network_free(struct loc_network* network) {
 116         DEBUG(network->ctx, "Releasing network at %p\n", network);
 117
 118         loc_unref(network->ctx);
 119         free(network);
 120 }
 121
 122 LOC_EXPORT struct loc_network* loc_network_unref(struct loc_network* network) {
 123         if (--network->refcount > 0)
 124                 return network;
 125
 126         loc_network_free(network);
 127         return NULL;
 128 }
 129
 130 LOC_EXPORT char* loc_network_str(struct loc_network* network) {
 131         const size_t l = INET6_ADDRSTRLEN + 3;
 132
 133         char* string = malloc(l);
 134         if (!string)
 135                 return NULL;
 136
 137         const char* ret = inet_ntop(AF_INET6, &network->start_address, string, l);
 138         if (!ret) {
 139                 ERROR(network->ctx, "Could not convert network to string: %s\n", strerror(errno));
 140
 141                 free(string);
 142                 return NULL;
 143         }
 144
 145         // Append prefix
 146         sprintf(string + strlen(string), "/%u", network->prefix);
 147
 148         return string;
 149 }
 150
 151 LOC_EXPORT const char* loc_network_get_country_code(struct loc_network* network) {
 152         return network->country_code;
 153 }
 154
 155 LOC_EXPORT int loc_network_set_country_code(struct loc_network* network, const char* country_code) {
 156         // Country codes must be two characters
 157         if (strlen(country_code) != 2)
 158                 return -EINVAL;
 159
 160         for (unsigned int i = 0; i < 3; i++) {
 161                 network->country_code[i] = country_code[i];
 162         }
 163
 164         return 0;
 165 }
 166
 167 LOC_EXPORT uint32_t loc_network_get_asn(struct loc_network* network) {
 168         return network->asn;
 169 }
 170
 171 LOC_EXPORT int loc_network_set_asn(struct loc_network* network, uint32_t asn) {
 172         network->asn = asn;
 173
 174         return 0;
 175 }
 176
 177 LOC_EXPORT int loc_network_to_database_v0(struct loc_network* network, struct loc_database_network_v0* dbobj) {
 178         dbobj->prefix = htobe16(network->prefix);
 179
 180         // Add country code
 181         for (unsigned int i = 0; i < 2; i++) {
 182                 dbobj->country_code[i] = network->country_code ? network->country_code[i] : '\0';
 183         }
 184
 185         // Add ASN
 186         dbobj->asn = htobe32(network->asn);
 187
 188         return 0;
 189 }
 190
 191 struct loc_network_tree {
 192         struct loc_ctx* ctx;
 193         int refcount;
 194
 195         struct loc_network_tree_node* root;
 196 };
 197
 198 struct loc_network_tree_node {
 199         struct loc_network_tree_node* zero;
 200         struct loc_network_tree_node* one;
 201
 202         struct loc_network* network;
 203 };
 204
 205 LOC_EXPORT int loc_network_tree_new(struct loc_ctx* ctx, struct loc_network_tree** tree) {
 206         struct loc_network_tree* t = calloc(1, sizeof(*t));
 207         if (!t)
 208                 return -ENOMEM;
 209
 210         t->ctx = loc_ref(ctx);
 211         t->refcount = 1;
 212
 213         // Create the root node
 214         t->root = calloc(1, sizeof(*t->root));
 215
 216         DEBUG(t->ctx, "Network tree allocated at %p\n", t);
 217         *tree = t;
 218         return 0;
 219 }
 220
 221 static int loc_network_tree_node_new(struct loc_network_tree_node** node) {
 222         struct loc_network_tree_node* n = calloc(1, sizeof(*n));
 223         if (!n)
 224                 return -ENOMEM;
 225
 226         n->zero = n->one = NULL;
 227
 228         *node = n;
 229         return 0;
 230 }
 231
 232 static struct loc_network_tree_node* loc_network_tree_get_node(struct loc_network_tree_node* node, int path) {
 233         struct loc_network_tree_node** n;
 234
 235         if (path)
 236                 n = &node->one;
 237         else
 238                 n = &node->zero;
 239
 240         // If the desired node doesn't exist, yet, we will create it
 241         if (*n == NULL) {
 242                 int r = loc_network_tree_node_new(n);
 243                 if (r)
 244                         return NULL;
 245         }
 246
 247         return *n;
 248 }
 249
 250 static struct loc_network_tree_node* loc_network_tree_get_path(struct loc_network_tree* tree, const struct in6_addr* address) {
 251         struct loc_network_tree_node* node = tree->root;
 252
 253         for (unsigned int i = 127; i > 0; i--) {
 254                 // Check if the ith bit is one or zero
 255                 node = loc_network_tree_get_node(node, ((address->s6_addr32[i / 32] & (1 << (i % 32))) == 0));
 256         }
 257
 258         return node;
 259 }
 260
 261 static int __loc_network_tree_walk(struct loc_ctx* ctx, struct loc_network_tree_node* node,
 262                 int(*filter_callback)(struct loc_network* network, void* data),
 263                 int(*callback)(struct loc_network* network, void* data), void* data) {
 264         int r;
 265
 266         // Finding a network ends the walk here
 267         if (node->network) {
 268                 if (filter_callback) {
 269                         int f = filter_callback(node->network, data);
 270                         if (f < 0)
 271                                 return f;
 272
 273                         // Skip network if filter function returns value greater than zero
 274                         if (f > 0)
 275                                 return 0;
 276                 }
 277
 278                 r = callback(node->network, data);
 279                 if (r)
 280                         return r;
 281         }
 282
 283         // Walk down on the left side of the tree first
 284         if (node->zero) {
 285                 r = __loc_network_tree_walk(ctx, node->zero, filter_callback, callback, data);
 286                 if (r)
 287                         return r;
 288         }
 289
 290         // Then walk on the other side
 291         if (node->one) {
 292                 r = __loc_network_tree_walk(ctx, node->one, filter_callback, callback, data);
 293                 if (r)
 294                         return r;
 295         }
 296
 297         return 0;
 298 }
 299
 300 LOC_EXPORT int loc_network_tree_walk(struct loc_network_tree* tree,
 301                 int(*filter_callback)(struct loc_network* network, void* data),
 302                 int(*callback)(struct loc_network* network, void* data), void* data) {
 303         return __loc_network_tree_walk(tree->ctx, tree->root, filter_callback, callback, data);
 304 }
 305
 306 static void loc_network_tree_free_subtree(struct loc_network_tree_node* node) {
 307         if (node->network)
 308                 loc_network_unref(node->network);
 309
 310         if (node->zero)
 311                 loc_network_tree_free_subtree(node->zero);
 312
 313         if (node->one)
 314                 loc_network_tree_free_subtree(node->one);
 315
 316         free(node);
 317 }
 318
 319 static void loc_network_tree_free(struct loc_network_tree* tree) {
 320         DEBUG(tree->ctx, "Releasing network tree at %p\n", tree);
 321
 322         loc_network_tree_free_subtree(tree->root);
 323
 324         loc_unref(tree->ctx);
 325         free(tree);
 326 }
 327
 328 LOC_EXPORT struct loc_network_tree* loc_network_tree_unref(struct loc_network_tree* tree) {
 329         if (--tree->refcount > 0)
 330                 return tree;
 331
 332         loc_network_tree_free(tree);
 333         return NULL;
 334 }
 335
 336 int __loc_network_tree_dump(struct loc_network* network, void* data) {
 337         DEBUG(network->ctx, "Dumping network at %p\n", network);
 338
 339         char* s = loc_network_str(network);
 340         if (!s)
 341                 return 1;
 342
 343         INFO(network->ctx, "%s\n", s);
 344         free(s);
 345
 346         return 0;
 347 }
 348
 349 LOC_EXPORT int loc_network_tree_dump(struct loc_network_tree* tree) {
 350         DEBUG(tree->ctx, "Dumping network tree at %p\n", tree);
 351
 352         return loc_network_tree_walk(tree, NULL, __loc_network_tree_dump, NULL);
 353 }
 354
 355 LOC_EXPORT int loc_network_tree_add_network(struct loc_network_tree* tree, struct loc_network* network) {
 356         DEBUG(tree->ctx, "Adding network %p to tree %p\n", network, tree);
 357
 358         struct loc_network_tree_node* node = loc_network_tree_get_path(tree, &network->start_address);
 359         if (!node) {
 360                 ERROR(tree->ctx, "Could not find a node\n");
 361                 return -ENOMEM;
 362         }
 363
 364         // Check if node has not been set before
 365         if (node->network) {
 366                 DEBUG(tree->ctx, "There is already a network at this path\n");
 367                 return 1;
 368         }
 369
 370         // Point node to the network
 371         node->network = loc_network_ref(network);
 372
 373         return 0;
 374 }
 375
 376 static int __loc_network_tree_count(struct loc_network* network, void* data) {
 377         size_t* counter = (size_t*)data;
 378
 379         // Increase the counter for each network
 380         counter++;
 381
 382         return 0;
 383 }
 384
 385 LOC_EXPORT size_t loc_network_tree_count_networks(struct loc_network_tree* tree) {
 386         size_t counter = 0;
 387
 388         int r = loc_network_tree_walk(tree, NULL, __loc_network_tree_count, &counter);
 389         if (r)
 390                 return r;
 391
 392         return counter;
 393 }