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
 117         for (unsigned int i = 0; i < list->size; i++) {
 118                 network = list->elements[i];
 119
 120                 INFO(list->ctx, "%4d: %s\n",
 121                         i, loc_network_str(network));
 122         }
 123 }
 124
 125 LOC_EXPORT struct loc_network* loc_network_list_get(struct loc_network_list* list, size_t index) {
 126         // Check index
 127         if (index >= list->size)
 128                 return NULL;
 129
 130         return loc_network_ref(list->elements[index]);
 131 }
 132
 133 static off_t loc_network_list_find(struct loc_network_list* list,
 134                 struct loc_network* network, int* found) {
 135         // Insert at the beginning for an empty list
 136         if (loc_network_list_empty(list))
 137                 return 0;
 138
 139         off_t lo = 0;
 140         off_t hi = list->size - 1;
 141         int result;
 142
 143         // Since we are working on an ordered list, there is often a good chance that
 144         // the network we are looking for is at the end or has to go to the end.
 145         if (hi >= 0) {
 146                 result = loc_network_cmp(network, list->elements[hi]);
 147
 148                 // Match, so we are done
 149                 if (result == 0) {
 150                         *found = 1;
 151
 152                         return hi;
 153
 154                 // This needs to be added after the last one
 155                 } else if (result > 0) {
 156                         *found = 0;
 157
 158                         return hi + 1;
 159                 }
 160         }
 161
 162 #ifdef ENABLE_DEBUG
 163         // Save start time
 164         clock_t start = clock();
 165 #endif
 166
 167         off_t i = 0;
 168
 169         while (lo <= hi) {
 170                 i = (lo + hi) / 2;
 171
 172                 // Check if this is a match
 173                 result = loc_network_cmp(network, list->elements[i]);
 174
 175                 if (result == 0) {
 176                         *found = 1;
 177
 178 #ifdef ENABLE_DEBUG
 179                         clock_t end = clock();
 180
 181                         // Log how fast this has been
 182                         DEBUG(list->ctx, "Found network in %.4fms at %jd\n",
 183                                 (double)(end - start) / CLOCKS_PER_SEC * 1000, (intmax_t)i);
 184 #endif
 185
 186                         return i;
 187                 }
 188
 189                 if (result > 0) {
 190                         lo = i + 1;
 191                         i++;
 192                 } else {
 193                         hi = i - 1;
 194                 }
 195         }
 196
 197         *found = 0;
 198
 199 #ifdef ENABLE_DEBUG
 200         clock_t end = clock();
 201
 202         // Log how fast this has been
 203         DEBUG(list->ctx, "Did not find network in %.4fms (last i = %jd)\n",
 204                 (double)(end - start) / CLOCKS_PER_SEC * 1000, (intmax_t)i);
 205 #endif
 206
 207         return i;
 208 }
 209
 210 LOC_EXPORT int loc_network_list_push(struct loc_network_list* list, struct loc_network* network) {
 211         int found = 0;
 212
 213         off_t index = loc_network_list_find(list, network, &found);
 214
 215         // The network has been found on the list. Nothing to do.
 216         if (found)
 217                 return 0;
 218
 219         DEBUG(list->ctx, "%p: Inserting network %p at index %jd\n",
 220                 list, network, (intmax_t)index);
 221
 222         // Check if we have space left
 223         if (list->size >= list->elements_size) {
 224                 int r = loc_network_list_grow(list, 64);
 225                 if (r)
 226                         return r;
 227         }
 228
 229         // The list is now larger
 230         list->size++;
 231
 232         // Move all elements out of the way
 233         for (unsigned int i = list->size - 1; i > index; i--)
 234                 list->elements[i] = list->elements[i - 1];
 235
 236         // Add the new element at the right place
 237         list->elements[index] = loc_network_ref(network);
 238
 239         return 0;
 240 }
 241
 242 LOC_EXPORT struct loc_network* loc_network_list_pop(struct loc_network_list* list) {
 243         // Return nothing when empty
 244         if (loc_network_list_empty(list)) {
 245                 DEBUG(list->ctx, "%p: Popped empty stack\n", list);
 246                 return NULL;
 247         }
 248
 249         struct loc_network* network = list->elements[--list->size];
 250
 251         DEBUG(list->ctx, "%p: Popping network %p from stack\n", list, network);
 252
 253         return network;
 254 }
 255
 256 LOC_EXPORT struct loc_network* loc_network_list_pop_first(struct loc_network_list* list) {
 257         // Return nothing when empty
 258         if (loc_network_list_empty(list)) {
 259                 DEBUG(list->ctx, "%p: Popped empty stack\n", list);
 260                 return NULL;
 261         }
 262
 263         struct loc_network* network = list->elements[0];
 264
 265         // Move all elements to the top of the stack
 266         for (unsigned int i = 0; i < list->size - 1; i++) {
 267                 list->elements[i] = list->elements[i+1];
 268         }
 269
 270         // The list is shorter now
 271         --list->size;
 272
 273         DEBUG(list->ctx, "%p: Popping network %p from stack\n", list, network);
 274
 275         return network;
 276 }
 277
 278 LOC_EXPORT int loc_network_list_contains(struct loc_network_list* list, struct loc_network* network) {
 279         int found = 0;
 280
 281         loc_network_list_find(list, network, &found);
 282
 283         return found;
 284 }
 285
 286 LOC_EXPORT int loc_network_list_merge(
 287                 struct loc_network_list* self, struct loc_network_list* other) {
 288         int r;
 289
 290         for (unsigned int i = 0; i < other->size; i++) {
 291                 r = loc_network_list_push(self, other->elements[i]);
 292                 if (r)
 293                         return r;
 294         }
 295
 296         return 0;
 297 }
 298
 299 int loc_network_list_summarize(struct loc_ctx* ctx,
 300                 const struct in6_addr* first, const struct in6_addr* last, struct loc_network_list** list) {
 301         int r;
 302
 303         if (!list) {
 304                 errno = EINVAL;
 305                 return 1;
 306         }
 307
 308         DEBUG(ctx, "Summarizing %s - %s\n", loc_address_str(first), loc_address_str(last));
 309
 310         const int family1 = loc_address_family(first);
 311         const int family2 = loc_address_family(last);
 312
 313         // Check if address families match
 314         if (family1 != family2) {
 315                 ERROR(ctx, "Address families do not match\n");
 316                 errno = EINVAL;
 317                 return 1;
 318         }
 319
 320         // Check if the last address is larger than the first address
 321         if (loc_address_cmp(first, last) >= 0) {
 322                 ERROR(ctx, "The first address must be smaller than the last address\n");
 323                 errno = EINVAL;
 324                 return 1;
 325         }
 326
 327         struct loc_network* network = NULL;
 328         struct in6_addr start = *first;
 329
 330         const int family_bit_length = loc_address_family_bit_length(family1);
 331
 332         while (loc_address_cmp(&start, last) <= 0) {
 333                 struct in6_addr num;
 334                 int bits1;
 335
 336                 // Find the number of trailing zeroes of the start address
 337                 if (loc_address_all_zeroes(&start))
 338                         bits1 = family_bit_length;
 339                 else {
 340                         bits1 = loc_address_count_trailing_zero_bits(&start);
 341                         if (bits1 > family_bit_length)
 342                                 bits1 = family_bit_length;
 343                 }
 344
 345                 // Subtract the start address from the last address and add one
 346                 // (i.e. how many addresses are in this network?)
 347                 r = loc_address_sub(&num, last, &start);
 348                 if (r)
 349                         return r;
 350
 351                 loc_address_increment(&num);
 352
 353                 // How many bits do we need to represent this address?
 354                 int bits2 = loc_address_bit_length(&num) - 1;
 355
 356                 // Select the smaller one
 357                 int bits = (bits1 > bits2) ? bits2 : bits1;
 358
 359                 printf("prefix = %d, bits1 = %d, bits2 = %d\n", family_bit_length, bits1, bits2);
 360
 361                 // Create a network
 362                 r = loc_network_new(ctx, &network, &start, family_bit_length - bits);
 363                 if (r)
 364                         return r;
 365
 366                 DEBUG(ctx, "Found network %s\n", loc_network_str(network));
 367
 368                 // Push network on the list
 369                 r = loc_network_list_push(*list, network);
 370                 if (r) {
 371                         loc_network_unref(network);
 372                         return r;
 373                 }
 374
 375                 // The next network starts right after this one
 376                 start = *loc_network_get_last_address(network);
 377
 378                 // If we have reached the end of possible IP addresses, we stop
 379                 if (loc_address_all_ones(&start))
 380                         break;
 381
 382                 loc_address_increment(&start);
 383         }
 384
 385         return 0;
 386 }