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 // First call when we have not seen any networks, yet
492 if (loc_network_list_empty(ctx
->stack
))
493 return loc_network_list_push(ctx
->stack
, network
);
495 const unsigned int prefix
= loc_network_prefix(network
);
497 // Remove any networks that are not interesting
498 loc_network_list_remove_with_prefix_smaller_than(ctx
->stack
, prefix
);
500 for (int i
= loc_network_list_size(ctx
->stack
) - 1; i
>= 0; i
--) {
501 n
= loc_network_list_get(ctx
->stack
, i
);
503 // Is network a subnet?
504 if (loc_network_is_subnet(n
, network
)) {
505 // Do all properties match?
506 if (loc_network_properties_cmp(n
, network
) == 0) {
507 r
= loc_network_tree_delete_network(ctx
->tree
, network
);
514 // Once we removed the subnet, we are done
518 // Once we found a subnet, we are done
523 // If network did not get removed, we push it into the stack
524 r
= loc_network_list_push(ctx
->stack
, network
);
530 loc_network_unref(n
);
535 static int loc_network_tree_dedup_filter(struct loc_network
* network
, void* data
) {
536 const struct loc_network_tree_dedup_ctx
* ctx
= data
;
538 // Match address family
539 return ctx
->family
== loc_network_address_family(network
);
542 static int loc_network_tree_dedup_one(struct loc_network_tree
* tree
,
543 const int family
, unsigned int* removed
) {
544 struct loc_network_tree_dedup_ctx ctx
= {
552 r
= loc_network_list_new(tree
->ctx
, &ctx
.stack
);
556 // Walk through the entire tree
557 r
= loc_network_tree_walk(tree
,
558 loc_network_tree_dedup_filter
, loc_network_tree_dedup_step
, &ctx
);
564 loc_network_list_unref(ctx
.stack
);
569 static int loc_network_tree_dedup(struct loc_network_tree
* tree
) {
570 unsigned int removed
= 0;
573 r
= loc_network_tree_dedup_one(tree
, AF_INET6
, &removed
);
577 r
= loc_network_tree_dedup_one(tree
, AF_INET
, &removed
);
581 DEBUG(tree
->ctx
, "%u network(s) have been removed\n", removed
);
586 static int loc_network_tree_delete_node(struct loc_network_tree
* tree
,
587 struct loc_network_tree_node
** node
) {
588 struct loc_network_tree_node
* n
= *node
;
592 // Return for nodes that have already been deleted
598 r0
= loc_network_tree_delete_node(tree
, &n
->zero
);
605 r1
= loc_network_tree_delete_node(tree
, &n
->one
);
610 // Don't delete this node if we are a leaf
614 // Don't delete this node if has child nodes that we need
623 // It is now safe to delete the node
624 loc_network_tree_node_unref(n
);
630 static int loc_network_tree_delete_nodes(struct loc_network_tree
* tree
) {
633 r
= loc_network_tree_delete_node(tree
, &tree
->root
);
640 int loc_network_tree_cleanup(struct loc_network_tree
* tree
) {
643 // Deduplicate the tree
644 r
= loc_network_tree_dedup(tree
);
649 r
= loc_network_tree_merge(tree
);
651 ERROR(tree
->ctx
, "Could not merge networks: %m\n");
655 // Delete any unneeded nodes
656 r
= loc_network_tree_delete_nodes(tree
);