src/network-list.c

   1 /*
   2         libloc - A library to determine the location of someone on the Internet
   3
   4         Copyright (C) 2020 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 <errno.h>
  18 #include <stdlib.h>
  19 #include <time.h>
  20
  21 #include <libloc/address.h>
  22 #include <libloc/libloc.h>
  23 #include <libloc/network.h>
  24 #include <libloc/private.h>
  25
  26 struct loc_network_list {
  27         struct loc_ctx* ctx;
  28         int refcount;
  29
  30         struct loc_network** elements;
  31         size_t elements_size;
  32
  33         size_t size;
  34 };
  35
  36 static int loc_network_list_grow(struct loc_network_list* list, size_t size) {
  37         DEBUG(list->ctx, "Growing network list %p by %zu to %zu\n",
  38                 list, size, list->elements_size + size);
  39
  40         struct loc_network** elements = reallocarray(list->elements,
  41                         list->elements_size + size, sizeof(*list->elements));
  42         if (!elements)
  43                 return -errno;
  44
  45         list->elements = elements;
  46         list->elements_size += size;
  47
  48         return 0;
  49 }
  50
  51 LOC_EXPORT int loc_network_list_new(struct loc_ctx* ctx,
  52                 struct loc_network_list** list) {
  53         struct loc_network_list* l = calloc(1, sizeof(*l));
  54         if (!l)
  55                 return -ENOMEM;
  56
  57         l->ctx = loc_ref(ctx);
  58         l->refcount = 1;
  59
  60         DEBUG(l->ctx, "Network list allocated at %p\n", l);
  61         *list = l;
  62         return 0;
  63 }
  64
  65 LOC_EXPORT struct loc_network_list* loc_network_list_ref(struct loc_network_list* list) {
  66         list->refcount++;
  67
  68         return list;
  69 }
  70
  71 static void loc_network_list_free(struct loc_network_list* list) {
  72         DEBUG(list->ctx, "Releasing network list at %p\n", list);
  73
  74         // Remove all content
  75         loc_network_list_clear(list);
  76
  77         loc_unref(list->ctx);
  78         free(list);
  79 }
  80
  81 LOC_EXPORT struct loc_network_list* loc_network_list_unref(struct loc_network_list* list) {
  82         if (!list)
  83                 return NULL;
  84
  85         if (--list->refcount > 0)
  86                 return list;
  87
  88         loc_network_list_free(list);
  89         return NULL;
  90 }
  91
  92 LOC_EXPORT size_t loc_network_list_size(struct loc_network_list* list) {
  93         return list->size;
  94 }
  95
  96 LOC_EXPORT int loc_network_list_empty(struct loc_network_list* list) {
  97         return list->size == 0;
  98 }
  99
 100 LOC_EXPORT void loc_network_list_clear(struct loc_network_list* list) {
 101         if (!list->elements)
 102                 return;
 103
 104         for (unsigned int i = 0; i < list->size; i++)
 105                 loc_network_unref(list->elements[i]);
 106
 107         free(list->elements);
 108         list->elements = NULL;
 109         list->elements_size = 0;
 110
 111         list->size = 0;
 112 }
 113
 114 LOC_EXPORT void loc_network_list_dump(struct loc_network_list* list) {
 115         struct loc_network* network;
 116         char* s;
 117
 118         for (unsigned int i = 0; i < list->size; i++) {
 119                 network = list->elements[i];
 120
 121                 s = loc_network_str(network);
 122
 123                 INFO(list->ctx, "%4d: %s\n", i, s);
 124                 free(s);
 125         }
 126 }
 127
 128 LOC_EXPORT struct loc_network* loc_network_list_get(struct loc_network_list* list, size_t index) {
 129         // Check index
 130         if (index >= list->size)
 131                 return NULL;
 132
 133         return loc_network_ref(list->elements[index]);
 134 }
 135
 136 static off_t loc_network_list_find(struct loc_network_list* list,
 137                 struct loc_network* network, int* found) {
 138         // Insert at the beginning for an empty list
 139         if (loc_network_list_empty(list))
 140                 return 0;
 141
 142         off_t lo = 0;
 143         off_t hi = list->size - 1;
 144         int result;
 145
 146         // Since we are working on an ordered list, there is often a good chance that
 147         // the network we are looking for is at the end or has to go to the end.
 148         if (hi >= 0) {
 149                 result = loc_network_cmp(network, list->elements[hi]);
 150
 151                 // Match, so we are done
 152                 if (result == 0) {
 153                         *found = 1;
 154
 155                         return hi;
 156
 157                 // This needs to be added after the last one
 158                 } else if (result > 0) {
 159                         *found = 0;
 160
 161                         return hi + 1;
 162                 }
 163         }
 164
 165 #ifdef ENABLE_DEBUG
 166         // Save start time
 167         clock_t start = clock();
 168 #endif
 169
 170         off_t i = 0;
 171
 172         while (lo <= hi) {
 173                 i = (lo + hi) / 2;
 174
 175                 // Check if this is a match
 176                 result = loc_network_cmp(network, list->elements[i]);
 177
 178                 if (result == 0) {
 179                         *found = 1;
 180
 181 #ifdef ENABLE_DEBUG
 182                         clock_t end = clock();
 183
 184                         // Log how fast this has been
 185                         DEBUG(list->ctx, "Found network in %.4fms at %jd\n",
 186                                 (double)(end - start) / CLOCKS_PER_SEC * 1000, (intmax_t)i);
 187 #endif
 188
 189                         return i;
 190                 }
 191
 192                 if (result > 0) {
 193                         lo = i + 1;
 194                         i++;
 195                 } else {
 196                         hi = i - 1;
 197                 }
 198         }
 199
 200         *found = 0;
 201
 202 #ifdef ENABLE_DEBUG
 203         clock_t end = clock();
 204
 205         // Log how fast this has been
 206         DEBUG(list->ctx, "Did not find network in %.4fms (last i = %jd)\n",
 207                 (double)(end - start) / CLOCKS_PER_SEC * 1000, (intmax_t)i);
 208 #endif
 209
 210         return i;
 211 }
 212
 213 LOC_EXPORT int loc_network_list_push(struct loc_network_list* list, struct loc_network* network) {
 214         int found = 0;
 215
 216         off_t index = loc_network_list_find(list, network, &found);
 217
 218         // The network has been found on the list. Nothing to do.
 219         if (found)
 220                 return 0;
 221
 222         DEBUG(list->ctx, "%p: Inserting network %p at index %jd\n",
 223                 list, network, (intmax_t)index);
 224
 225         // Check if we have space left
 226         if (list->size >= list->elements_size) {
 227                 int r = loc_network_list_grow(list, 64);
 228                 if (r)
 229                         return r;
 230         }
 231
 232         // The list is now larger
 233         list->size++;
 234
 235         // Move all elements out of the way
 236         for (unsigned int i = list->size - 1; i > index; i--)
 237                 list->elements[i] = list->elements[i - 1];
 238
 239         // Add the new element at the right place
 240         list->elements[index] = loc_network_ref(network);
 241
 242         return 0;
 243 }
 244
 245 LOC_EXPORT struct loc_network* loc_network_list_pop(struct loc_network_list* list) {
 246         // Return nothing when empty
 247         if (loc_network_list_empty(list)) {
 248                 DEBUG(list->ctx, "%p: Popped empty stack\n", list);
 249                 return NULL;
 250         }
 251
 252         struct loc_network* network = list->elements[--list->size];
 253
 254         DEBUG(list->ctx, "%p: Popping network %p from stack\n", list, network);
 255
 256         return network;
 257 }
 258
 259 LOC_EXPORT struct loc_network* loc_network_list_pop_first(struct loc_network_list* list) {
 260         // Return nothing when empty
 261         if (loc_network_list_empty(list)) {
 262                 DEBUG(list->ctx, "%p: Popped empty stack\n", list);
 263                 return NULL;
 264         }
 265
 266         struct loc_network* network = list->elements[0];
 267
 268         // Move all elements to the top of the stack
 269         for (unsigned int i = 0; i < list->size - 1; i++) {
 270                 list->elements[i] = list->elements[i+1];
 271         }
 272
 273         // The list is shorter now
 274         --list->size;
 275
 276         DEBUG(list->ctx, "%p: Popping network %p from stack\n", list, network);
 277
 278         return network;
 279 }
 280
 281 LOC_EXPORT int loc_network_list_contains(struct loc_network_list* list, struct loc_network* network) {
 282         int found = 0;
 283
 284         loc_network_list_find(list, network, &found);
 285
 286         return found;
 287 }
 288
 289 LOC_EXPORT int loc_network_list_merge(
 290                 struct loc_network_list* self, struct loc_network_list* other) {
 291         int r;
 292
 293         for (unsigned int i = 0; i < other->size; i++) {
 294                 r = loc_network_list_push(self, other->elements[i]);
 295                 if (r)
 296                         return r;
 297         }
 298
 299         return 0;
 300 }
 301
 302 int loc_network_list_summarize(struct loc_ctx* ctx,
 303                 const struct in6_addr* first, const struct in6_addr* last, struct loc_network_list** list) {
 304         int r;
 305
 306         if (!list) {
 307                 errno = EINVAL;
 308                 return 1;
 309         }
 310
 311         const int family1 = loc_address_family(first);
 312         const int family2 = loc_address_family(last);
 313
 314         // Check if address families match
 315         if (family1 != family2) {
 316                 ERROR(ctx, "Address families do not match\n");
 317                 errno = EINVAL;
 318                 return 1;
 319         }
 320
 321         // Check if the last address is larger than the first address
 322         if (loc_address_cmp(first, last) >= 0) {
 323                 ERROR(ctx, "The first address must be smaller than the last address\n");
 324                 errno = EINVAL;
 325                 return 1;
 326         }
 327
 328         struct loc_network* network = NULL;
 329         struct in6_addr start = *first;
 330
 331         const int family_bit_length = loc_address_family_bit_length(family1);
 332
 333         while (loc_address_cmp(&start, last) <= 0) {
 334                 struct in6_addr num;
 335                 int bits1;
 336
 337                 // Find the number of trailing zeroes of the start address
 338                 if (loc_address_all_zeroes(&start))
 339                         bits1 = family_bit_length;
 340                 else {
 341                         bits1 = loc_address_count_trailing_zero_bits(&start);
 342                         if (bits1 > family_bit_length)
 343                                 bits1 = family_bit_length;
 344                 }
 345
 346                 // Subtract the start address from the last address and add one
 347                 // (i.e. how many addresses are in this network?)
 348                 r = loc_address_sub(&num, last, &start);
 349                 if (r)
 350                         return r;
 351
 352                 loc_address_increment(&num);
 353
 354                 // How many bits do we need to represent this address?
 355                 int bits2 = loc_address_bit_length(&num) - 1;
 356
 357                 // Select the smaller one
 358                 int bits = (bits1 > bits2) ? bits2 : bits1;
 359
 360                 // Create a network
 361                 r = loc_network_new(ctx, &network, &start, family_bit_length - bits);
 362                 if (r)
 363                         return r;
 364
 365 #ifdef ENABLE_DEBUG
 366                 char* n = loc_network_str(network);
 367                 if (n) {
 368                         DEBUG(ctx, "Found network %s\n", n);
 369                         free(n);
 370                 }
 371 #endif
 372
 373                 // Push network on the list
 374                 r = loc_network_list_push(*list, network);
 375                 if (r) {
 376                         loc_network_unref(network);
 377                         return r;
 378                 }
 379
 380                 // The next network starts right after this one
 381                 start = *loc_network_get_last_address(network);
 382                 loc_address_increment(&start);
 383         }
 384
 385         return 0;
 386 }