2 libloc - A library to determine the location of someone on the Internet
4 Copyright (C) 2024 IPFire Development Team <info@ipfire.org>
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.
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.
21 #include <libloc/libloc.h>
22 #include <libloc/address.h>
23 #include <libloc/network-tree.h>
24 #include <libloc/private.h>
26 struct loc_network_tree
{
30 struct loc_network_tree_node
* root
;
33 struct loc_network_tree_node
{
37 struct loc_network_tree_node
* zero
;
38 struct loc_network_tree_node
* one
;
40 struct loc_network
* network
;
46 int loc_network_tree_new(struct loc_ctx
* ctx
, struct loc_network_tree
** tree
) {
47 struct loc_network_tree
* t
= calloc(1, sizeof(*t
));
51 t
->ctx
= loc_ref(ctx
);
54 // Create the root node
55 int r
= loc_network_tree_node_new(ctx
, &t
->root
);
57 loc_network_tree_unref(t
);
61 DEBUG(t
->ctx
, "Network tree allocated at %p\n", t
);
66 struct loc_network_tree_node
* loc_network_tree_get_root(struct loc_network_tree
* tree
) {
67 return loc_network_tree_node_ref(tree
->root
);
70 static struct loc_network_tree_node
* loc_network_tree_get_node(struct loc_network_tree_node
* node
, int path
) {
71 struct loc_network_tree_node
** n
= NULL
;
88 // If the node existed, but has been deleted, we undelete it
89 if (*n
&& (*n
)->deleted
) {
92 // If the desired node doesn't exist, yet, we will create it
94 r
= loc_network_tree_node_new(node
->ctx
, n
);
102 static struct loc_network_tree_node
* loc_network_tree_get_path(struct loc_network_tree
* tree
, const struct in6_addr
* address
, unsigned int prefix
) {
103 struct loc_network_tree_node
* node
= tree
->root
;
105 for (unsigned int i
= 0; i
< prefix
; i
++) {
106 // Check if the ith bit is one or zero
107 node
= loc_network_tree_get_node(node
, loc_address_get_bit(address
, i
));
113 static int __loc_network_tree_walk(struct loc_ctx
* ctx
, struct loc_network_tree_node
* node
,
114 int(*filter_callback
)(struct loc_network
* network
, void* data
),
115 int(*callback
)(struct loc_network
* network
, void* data
), void* data
) {
118 // If the node has been deleted, don't process it
122 // Finding a network ends the walk here
124 if (filter_callback
) {
125 int f
= filter_callback(node
->network
, data
);
129 // Skip network if filter function returns value greater than zero
134 r
= callback(node
->network
, data
);
139 // Walk down on the left side of the tree first
141 r
= __loc_network_tree_walk(ctx
, node
->zero
, filter_callback
, callback
, data
);
146 // Then walk on the other side
148 r
= __loc_network_tree_walk(ctx
, node
->one
, filter_callback
, callback
, data
);
156 int loc_network_tree_walk(struct loc_network_tree
* tree
,
157 int(*filter_callback
)(struct loc_network
* network
, void* data
),
158 int(*callback
)(struct loc_network
* network
, void* data
), void* data
) {
159 return __loc_network_tree_walk(tree
->ctx
, tree
->root
, filter_callback
, callback
, data
);
162 static void loc_network_tree_free(struct loc_network_tree
* tree
) {
163 DEBUG(tree
->ctx
, "Releasing network tree at %p\n", tree
);
165 loc_network_tree_node_unref(tree
->root
);
167 loc_unref(tree
->ctx
);
171 struct loc_network_tree
* loc_network_tree_unref(struct loc_network_tree
* tree
) {
172 if (--tree
->refcount
> 0)
175 loc_network_tree_free(tree
);
179 static int __loc_network_tree_dump(struct loc_network
* network
, void* data
) {
180 struct loc_ctx
* ctx
= data
;
182 DEBUG(ctx
, "Dumping network at %p\n", network
);
184 const char* s
= loc_network_str(network
);
188 INFO(ctx
, "%s\n", s
);
193 int loc_network_tree_dump(struct loc_network_tree
* tree
) {
194 DEBUG(tree
->ctx
, "Dumping network tree at %p\n", tree
);
196 return loc_network_tree_walk(tree
, NULL
, __loc_network_tree_dump
, tree
->ctx
);
199 int loc_network_tree_add_network(struct loc_network_tree
* tree
, struct loc_network
* network
) {
200 DEBUG(tree
->ctx
, "Adding network %p to tree %p\n", network
, tree
);
202 const struct in6_addr
* first_address
= loc_network_get_first_address(network
);
203 const unsigned int prefix
= loc_network_raw_prefix(network
);
205 struct loc_network_tree_node
* node
= loc_network_tree_get_path(tree
, first_address
, prefix
);
207 ERROR(tree
->ctx
, "Could not find a node\n");
211 // Check if node has not been set before
213 DEBUG(tree
->ctx
, "There is already a network at this path: %s\n",
214 loc_network_str(node
->network
));
218 // Point node to the network
219 node
->network
= loc_network_ref(network
);
224 static int loc_network_tree_delete_network(
225 struct loc_network_tree
* tree
, struct loc_network
* network
) {
226 struct loc_network_tree_node
* node
= NULL
;
228 DEBUG(tree
->ctx
, "Deleting network %s from tree...\n", loc_network_str(network
));
230 const struct in6_addr
* first_address
= loc_network_get_first_address(network
);
231 const unsigned int prefix
= loc_network_raw_prefix(network
);
233 node
= loc_network_tree_get_path(tree
, first_address
, prefix
);
235 ERROR(tree
->ctx
, "Network was not found in tree %s\n", loc_network_str(network
));
241 loc_network_unref(node
->network
);
242 node
->network
= NULL
;
245 // Mark the node as deleted if it was a leaf
246 if (!node
->zero
&& !node
->one
)
252 static size_t __loc_network_tree_count_nodes(struct loc_network_tree_node
* node
) {
255 // Don't count deleted nodes
260 counter
+= __loc_network_tree_count_nodes(node
->zero
);
263 counter
+= __loc_network_tree_count_nodes(node
->one
);
268 size_t loc_network_tree_count_nodes(struct loc_network_tree
* tree
) {
269 return __loc_network_tree_count_nodes(tree
->root
);
272 int loc_network_tree_node_new(struct loc_ctx
* ctx
, struct loc_network_tree_node
** node
) {
273 struct loc_network_tree_node
* n
= calloc(1, sizeof(*n
));
277 n
->ctx
= loc_ref(ctx
);
280 n
->zero
= n
->one
= NULL
;
282 DEBUG(n
->ctx
, "Network node allocated at %p\n", n
);
287 struct loc_network_tree_node
* loc_network_tree_node_ref(struct loc_network_tree_node
* node
) {
294 static void loc_network_tree_node_free(struct loc_network_tree_node
* node
) {
295 DEBUG(node
->ctx
, "Releasing network node at %p\n", node
);
298 loc_network_unref(node
->network
);
301 loc_network_tree_node_unref(node
->zero
);
304 loc_network_tree_node_unref(node
->one
);
306 loc_unref(node
->ctx
);
310 struct loc_network_tree_node
* loc_network_tree_node_unref(struct loc_network_tree_node
* node
) {
311 if (--node
->refcount
> 0)
314 loc_network_tree_node_free(node
);
318 struct loc_network_tree_node
* loc_network_tree_node_get(struct loc_network_tree_node
* node
, unsigned int index
) {
327 return loc_network_tree_node_ref(node
);
330 int loc_network_tree_node_is_leaf(struct loc_network_tree_node
* node
) {
331 return (!!node
->network
);
334 struct loc_network
* loc_network_tree_node_get_network(struct loc_network_tree_node
* node
) {
335 return loc_network_ref(node
->network
);
342 struct loc_network_tree_merge_ctx
{
343 struct loc_network_tree
* tree
;
344 struct loc_network_list
* networks
;
348 static int loc_network_tree_merge_step(struct loc_network
* network
, void* data
) {
349 struct loc_network_tree_merge_ctx
* ctx
= (struct loc_network_tree_merge_ctx
*)data
;
350 struct loc_network
* n
= NULL
;
351 struct loc_network
* m
= NULL
;
354 // How many networks do we have?
355 size_t i
= loc_network_list_size(ctx
->networks
);
357 // If the list is empty, just add the network
359 return loc_network_list_push(ctx
->networks
, network
);
362 // Fetch the last network of the list
363 n
= loc_network_list_get(ctx
->networks
, i
);
365 // Try to merge the two networks
366 r
= loc_network_merge(&m
, n
, network
);
370 // Did we get a result?
372 DEBUG(ctx
->tree
->ctx
, "Merged networks %s + %s -> %s\n",
373 loc_network_str(n
), loc_network_str(network
), loc_network_str(m
));
375 // Add the new network
376 r
= loc_network_tree_add_network(ctx
->tree
, m
);
381 // There might already be a network
390 // Remove the merge networks
391 r
= loc_network_tree_delete_network(ctx
->tree
, network
);
395 r
= loc_network_tree_delete_network(ctx
->tree
, n
);
399 // Add the new network to the stack
400 r
= loc_network_list_push(ctx
->networks
, m
);
404 // Remove the previous network from the stack
405 r
= loc_network_list_remove(ctx
->networks
, n
);
412 // Try merging the new network with others
413 r
= loc_network_tree_merge_step(m
, data
);
417 loc_network_unref(m
);
420 // Once we have found a merge, we are done
423 // If we could not merge the two networks, we add the current one
425 r
= loc_network_list_push(ctx
->networks
, network
);
430 loc_network_unref(n
);
434 const unsigned int prefix
= loc_network_prefix(network
);
436 // Remove any networks that we cannot merge
437 loc_network_list_remove_with_prefix_smaller_than(ctx
->networks
, prefix
);
441 loc_network_unref(m
);
443 loc_network_unref(n
);
448 static int loc_network_tree_merge(struct loc_network_tree
* tree
) {
449 struct loc_network_tree_merge_ctx ctx
= {
457 r
= loc_network_list_new(tree
->ctx
, &ctx
.networks
);
461 // Walk through the entire tree
462 r
= loc_network_tree_walk(tree
, NULL
, loc_network_tree_merge_step
, &ctx
);
466 DEBUG(tree
->ctx
, "%u network(s) have been merged\n", ctx
.merged
);
470 loc_network_list_unref(ctx
.networks
);
479 struct loc_network_tree_dedup_ctx
{
480 struct loc_network_tree
* tree
;
481 struct loc_network_list
* stack
;
482 unsigned int* removed
;
486 static int loc_network_tree_dedup_step(struct loc_network
* network
, void* data
) {
487 struct loc_network_tree_dedup_ctx
* ctx
= (struct loc_network_tree_dedup_ctx
*)data
;
488 struct loc_network
* n
= NULL
;
491 // Walk through all networks on the stack...
492 for (int i
= loc_network_list_size(ctx
->stack
) - 1; i
>= 0; i
--) {
493 n
= loc_network_list_get(ctx
->stack
, i
);
495 // Is network a subnet?
496 if (loc_network_is_subnet(n
, network
)) {
497 // Do all properties match?
498 if (loc_network_properties_cmp(n
, network
) == 0) {
499 r
= loc_network_tree_delete_network(ctx
->tree
, network
);
506 // Once we removed the subnet, we are done
510 // Once we found a subnet, we are done
514 // If the network wasn't a subnet, we can remove it,
515 // because we won't ever see a subnet again.
516 r
= loc_network_list_remove(ctx
->stack
, n
);
520 loc_network_unref(n
);
524 // If network did not get removed, we push it into the stack
525 r
= loc_network_list_push(ctx
->stack
, network
);
531 loc_network_unref(n
);
536 static int loc_network_tree_dedup_filter(struct loc_network
* network
, void* data
) {
537 const struct loc_network_tree_dedup_ctx
* ctx
= data
;
539 // Match address family
540 return ctx
->family
== loc_network_address_family(network
);
543 static int loc_network_tree_dedup_one(struct loc_network_tree
* tree
,
544 const int family
, unsigned int* removed
) {
545 struct loc_network_tree_dedup_ctx ctx
= {
553 r
= loc_network_list_new(tree
->ctx
, &ctx
.stack
);
557 // Walk through the entire tree
558 r
= loc_network_tree_walk(tree
,
559 loc_network_tree_dedup_filter
, loc_network_tree_dedup_step
, &ctx
);
565 loc_network_list_unref(ctx
.stack
);
570 static int loc_network_tree_dedup(struct loc_network_tree
* tree
) {
571 unsigned int removed
= 0;
574 r
= loc_network_tree_dedup_one(tree
, AF_INET6
, &removed
);
578 r
= loc_network_tree_dedup_one(tree
, AF_INET
, &removed
);
582 DEBUG(tree
->ctx
, "%u network(s) have been removed\n", removed
);
587 static int loc_network_tree_delete_node(struct loc_network_tree
* tree
,
588 struct loc_network_tree_node
** node
) {
589 struct loc_network_tree_node
* n
= *node
;
593 // Return for nodes that have already been deleted
599 r0
= loc_network_tree_delete_node(tree
, &n
->zero
);
606 r1
= loc_network_tree_delete_node(tree
, &n
->one
);
611 // Don't delete this node if we are a leaf
615 // Don't delete this node if has child nodes that we need
624 // It is now safe to delete the node
625 loc_network_tree_node_unref(n
);
631 static int loc_network_tree_delete_nodes(struct loc_network_tree
* tree
) {
634 r
= loc_network_tree_delete_node(tree
, &tree
->root
);
641 int loc_network_tree_cleanup(struct loc_network_tree
* tree
) {
644 // Deduplicate the tree
645 r
= loc_network_tree_dedup(tree
);
650 r
= loc_network_tree_merge(tree
);
652 ERROR(tree
->ctx
, "Could not merge networks: %m\n");
656 // Delete any unneeded nodes
657 r
= loc_network_tree_delete_nodes(tree
);