]>
Commit | Line | Data |
---|---|---|
fe8277ed MT |
1 | /* |
2 | libloc - A library to determine the location of someone on the Internet | |
3 | ||
4 | Copyright (C) 2024 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 <stddef.h> | |
18 | #include <stdlib.h> | |
19 | #include <errno.h> | |
20 | ||
21 | #include <libloc/libloc.h> | |
22 | #include <libloc/address.h> | |
23 | #include <libloc/network-tree.h> | |
24 | #include <libloc/private.h> | |
25 | ||
26 | struct loc_network_tree { | |
27 | struct loc_ctx* ctx; | |
28 | int refcount; | |
29 | ||
30 | struct loc_network_tree_node* root; | |
31 | }; | |
32 | ||
33 | struct loc_network_tree_node { | |
34 | struct loc_ctx* ctx; | |
35 | int refcount; | |
36 | ||
37 | struct loc_network_tree_node* zero; | |
38 | struct loc_network_tree_node* one; | |
39 | ||
40 | struct loc_network* network; | |
41 | ||
42 | // Set if deleted | |
43 | int deleted:1; | |
44 | }; | |
45 | ||
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)); | |
48 | if (!t) | |
49 | return 1; | |
50 | ||
51 | t->ctx = loc_ref(ctx); | |
52 | t->refcount = 1; | |
53 | ||
54 | // Create the root node | |
55 | int r = loc_network_tree_node_new(ctx, &t->root); | |
56 | if (r) { | |
57 | loc_network_tree_unref(t); | |
58 | return r; | |
59 | } | |
60 | ||
61 | DEBUG(t->ctx, "Network tree allocated at %p\n", t); | |
62 | *tree = t; | |
63 | return 0; | |
64 | } | |
65 | ||
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); | |
68 | } | |
69 | ||
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; | |
72 | int r; | |
73 | ||
74 | switch (path) { | |
75 | case 0: | |
76 | n = &node->zero; | |
77 | break; | |
78 | ||
79 | case 1: | |
80 | n = &node->one; | |
81 | break; | |
82 | ||
83 | default: | |
84 | errno = EINVAL; | |
85 | return NULL; | |
86 | } | |
87 | ||
88 | // If the node existed, but has been deleted, we undelete it | |
89 | if (*n && (*n)->deleted) { | |
90 | (*n)->deleted = 0; | |
91 | ||
92 | // If the desired node doesn't exist, yet, we will create it | |
93 | } else if (!*n) { | |
94 | r = loc_network_tree_node_new(node->ctx, n); | |
95 | if (r) | |
96 | return NULL; | |
97 | } | |
98 | ||
99 | return *n; | |
100 | } | |
101 | ||
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; | |
104 | ||
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)); | |
108 | } | |
109 | ||
110 | return node; | |
111 | } | |
112 | ||
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) { | |
116 | int r; | |
117 | ||
118 | // If the node has been deleted, don't process it | |
119 | if (node->deleted) | |
120 | return 0; | |
121 | ||
122 | // Finding a network ends the walk here | |
123 | if (node->network) { | |
124 | if (filter_callback) { | |
125 | int f = filter_callback(node->network, data); | |
126 | if (f < 0) | |
127 | return f; | |
128 | ||
129 | // Skip network if filter function returns value greater than zero | |
130 | if (f > 0) | |
131 | return 0; | |
132 | } | |
133 | ||
134 | r = callback(node->network, data); | |
135 | if (r) | |
136 | return r; | |
137 | } | |
138 | ||
139 | // Walk down on the left side of the tree first | |
140 | if (node->zero) { | |
141 | r = __loc_network_tree_walk(ctx, node->zero, filter_callback, callback, data); | |
142 | if (r) | |
143 | return r; | |
144 | } | |
145 | ||
146 | // Then walk on the other side | |
147 | if (node->one) { | |
148 | r = __loc_network_tree_walk(ctx, node->one, filter_callback, callback, data); | |
149 | if (r) | |
150 | return r; | |
151 | } | |
152 | ||
153 | return 0; | |
154 | } | |
155 | ||
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); | |
160 | } | |
161 | ||
162 | static void loc_network_tree_free(struct loc_network_tree* tree) { | |
163 | DEBUG(tree->ctx, "Releasing network tree at %p\n", tree); | |
164 | ||
165 | loc_network_tree_node_unref(tree->root); | |
166 | ||
167 | loc_unref(tree->ctx); | |
168 | free(tree); | |
169 | } | |
170 | ||
171 | struct loc_network_tree* loc_network_tree_unref(struct loc_network_tree* tree) { | |
172 | if (--tree->refcount > 0) | |
173 | return tree; | |
174 | ||
175 | loc_network_tree_free(tree); | |
176 | return NULL; | |
177 | } | |
178 | ||
179 | static int __loc_network_tree_dump(struct loc_network* network, void* data) { | |
180 | struct loc_ctx* ctx = data; | |
181 | ||
182 | DEBUG(ctx, "Dumping network at %p\n", network); | |
183 | ||
184 | const char* s = loc_network_str(network); | |
185 | if (!s) | |
186 | return 1; | |
187 | ||
188 | INFO(ctx, "%s\n", s); | |
189 | ||
190 | return 0; | |
191 | } | |
192 | ||
193 | int loc_network_tree_dump(struct loc_network_tree* tree) { | |
194 | DEBUG(tree->ctx, "Dumping network tree at %p\n", tree); | |
195 | ||
196 | return loc_network_tree_walk(tree, NULL, __loc_network_tree_dump, tree->ctx); | |
197 | } | |
198 | ||
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); | |
201 | ||
202 | const struct in6_addr* first_address = loc_network_get_first_address(network); | |
a92139f1 | 203 | const unsigned int prefix = loc_network_raw_prefix(network); |
fe8277ed MT |
204 | |
205 | struct loc_network_tree_node* node = loc_network_tree_get_path(tree, first_address, prefix); | |
206 | if (!node) { | |
207 | ERROR(tree->ctx, "Could not find a node\n"); | |
208 | return -ENOMEM; | |
209 | } | |
210 | ||
211 | // Check if node has not been set before | |
212 | if (node->network) { | |
213 | DEBUG(tree->ctx, "There is already a network at this path: %s\n", | |
214 | loc_network_str(node->network)); | |
215 | return -EBUSY; | |
216 | } | |
217 | ||
218 | // Point node to the network | |
219 | node->network = loc_network_ref(network); | |
220 | ||
221 | return 0; | |
222 | } | |
223 | ||
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; | |
227 | ||
228 | DEBUG(tree->ctx, "Deleting network %s from tree...\n", loc_network_str(network)); | |
229 | ||
230 | const struct in6_addr* first_address = loc_network_get_first_address(network); | |
a92139f1 | 231 | const unsigned int prefix = loc_network_raw_prefix(network); |
fe8277ed MT |
232 | |
233 | node = loc_network_tree_get_path(tree, first_address, prefix); | |
234 | if (!node) { | |
235 | ERROR(tree->ctx, "Network was not found in tree %s\n", loc_network_str(network)); | |
236 | return 1; | |
237 | } | |
238 | ||
239 | // Drop the network | |
240 | if (node->network) { | |
241 | loc_network_unref(node->network); | |
242 | node->network = NULL; | |
243 | } | |
244 | ||
245 | // Mark the node as deleted if it was a leaf | |
246 | if (!node->zero && !node->one) | |
247 | node->deleted = 1; | |
248 | ||
249 | return 0; | |
250 | } | |
251 | ||
252 | static size_t __loc_network_tree_count_nodes(struct loc_network_tree_node* node) { | |
253 | size_t counter = 1; | |
254 | ||
255 | // Don't count deleted nodes | |
256 | if (node->deleted) | |
257 | return 0; | |
258 | ||
259 | if (node->zero) | |
260 | counter += __loc_network_tree_count_nodes(node->zero); | |
261 | ||
262 | if (node->one) | |
263 | counter += __loc_network_tree_count_nodes(node->one); | |
264 | ||
265 | return counter; | |
266 | } | |
267 | ||
268 | size_t loc_network_tree_count_nodes(struct loc_network_tree* tree) { | |
269 | return __loc_network_tree_count_nodes(tree->root); | |
270 | } | |
271 | ||
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)); | |
274 | if (!n) | |
275 | return -ENOMEM; | |
276 | ||
277 | n->ctx = loc_ref(ctx); | |
278 | n->refcount = 1; | |
279 | ||
280 | n->zero = n->one = NULL; | |
281 | ||
282 | DEBUG(n->ctx, "Network node allocated at %p\n", n); | |
283 | *node = n; | |
284 | return 0; | |
285 | } | |
286 | ||
287 | struct loc_network_tree_node* loc_network_tree_node_ref(struct loc_network_tree_node* node) { | |
288 | if (node) | |
289 | node->refcount++; | |
290 | ||
291 | return node; | |
292 | } | |
293 | ||
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); | |
296 | ||
297 | if (node->network) | |
298 | loc_network_unref(node->network); | |
299 | ||
300 | if (node->zero) | |
301 | loc_network_tree_node_unref(node->zero); | |
302 | ||
303 | if (node->one) | |
304 | loc_network_tree_node_unref(node->one); | |
305 | ||
306 | loc_unref(node->ctx); | |
307 | free(node); | |
308 | } | |
309 | ||
310 | struct loc_network_tree_node* loc_network_tree_node_unref(struct loc_network_tree_node* node) { | |
311 | if (--node->refcount > 0) | |
312 | return node; | |
313 | ||
314 | loc_network_tree_node_free(node); | |
315 | return NULL; | |
316 | } | |
317 | ||
318 | struct loc_network_tree_node* loc_network_tree_node_get(struct loc_network_tree_node* node, unsigned int index) { | |
319 | if (index == 0) | |
320 | node = node->zero; | |
321 | else | |
322 | node = node->one; | |
323 | ||
324 | if (!node) | |
325 | return NULL; | |
326 | ||
327 | return loc_network_tree_node_ref(node); | |
328 | } | |
329 | ||
330 | int loc_network_tree_node_is_leaf(struct loc_network_tree_node* node) { | |
331 | return (!!node->network); | |
332 | } | |
333 | ||
334 | struct loc_network* loc_network_tree_node_get_network(struct loc_network_tree_node* node) { | |
335 | return loc_network_ref(node->network); | |
336 | } | |
337 | ||
338 | /* | |
339 | Merge the tree! | |
340 | */ | |
341 | ||
342 | struct loc_network_tree_merge_ctx { | |
343 | struct loc_network_tree* tree; | |
344 | struct loc_network_list* networks; | |
345 | unsigned int merged; | |
346 | }; | |
347 | ||
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; | |
352 | int r; | |
353 | ||
354 | // How many networks do we have? | |
355 | size_t i = loc_network_list_size(ctx->networks); | |
356 | ||
357 | // If the list is empty, just add the network | |
358 | if (i == 0) | |
359 | return loc_network_list_push(ctx->networks, network); | |
360 | ||
361 | while (i--) { | |
362 | // Fetch the last network of the list | |
363 | n = loc_network_list_get(ctx->networks, i); | |
364 | ||
365 | // Try to merge the two networks | |
366 | r = loc_network_merge(&m, n, network); | |
367 | if (r) | |
368 | goto ERROR; | |
369 | ||
370 | // Did we get a result? | |
371 | if (m) { | |
372 | DEBUG(ctx->tree->ctx, "Merged networks %s + %s -> %s\n", | |
373 | loc_network_str(n), loc_network_str(network), loc_network_str(m)); | |
374 | ||
375 | // Add the new network | |
376 | r = loc_network_tree_add_network(ctx->tree, m); | |
377 | switch (r) { | |
378 | case 0: | |
379 | break; | |
380 | ||
381 | // There might already be a network | |
382 | case -EBUSY: | |
383 | r = 0; | |
384 | goto ERROR; | |
385 | ||
386 | default: | |
387 | goto ERROR; | |
388 | } | |
389 | ||
390 | // Remove the merge networks | |
391 | r = loc_network_tree_delete_network(ctx->tree, network); | |
392 | if (r) | |
393 | goto ERROR; | |
394 | ||
395 | r = loc_network_tree_delete_network(ctx->tree, n); | |
396 | if (r) | |
397 | goto ERROR; | |
398 | ||
399 | // Add the new network to the stack | |
400 | r = loc_network_list_push(ctx->networks, m); | |
401 | if (r) | |
402 | goto ERROR; | |
403 | ||
404 | // Remove the previous network from the stack | |
405 | r = loc_network_list_remove(ctx->networks, n); | |
406 | if (r) | |
407 | goto ERROR; | |
408 | ||
409 | // Count merges | |
410 | ctx->merged++; | |
411 | ||
412 | // Try merging the new network with others | |
413 | r = loc_network_tree_merge_step(m, data); | |
414 | if (r) | |
415 | goto ERROR; | |
416 | ||
417 | loc_network_unref(m); | |
418 | m = NULL; | |
419 | ||
420 | // Once we have found a merge, we are done | |
421 | break; | |
422 | ||
423 | // If we could not merge the two networks, we add the current one | |
424 | } else { | |
425 | r = loc_network_list_push(ctx->networks, network); | |
426 | if (r) | |
427 | goto ERROR; | |
428 | } | |
429 | ||
430 | loc_network_unref(n); | |
431 | n = NULL; | |
432 | } | |
433 | ||
434 | const unsigned int prefix = loc_network_prefix(network); | |
435 | ||
436 | // Remove any networks that we cannot merge | |
437 | loc_network_list_remove_with_prefix_smaller_than(ctx->networks, prefix); | |
438 | ||
439 | ERROR: | |
440 | if (m) | |
441 | loc_network_unref(m); | |
442 | if (n) | |
443 | loc_network_unref(n); | |
444 | ||
445 | return r; | |
446 | } | |
447 | ||
448 | static int loc_network_tree_merge(struct loc_network_tree* tree) { | |
449 | struct loc_network_tree_merge_ctx ctx = { | |
450 | .tree = tree, | |
451 | .networks = NULL, | |
452 | .merged = 0, | |
453 | }; | |
454 | int r; | |
455 | ||
456 | // Create a new list | |
457 | r = loc_network_list_new(tree->ctx, &ctx.networks); | |
458 | if (r) | |
459 | goto ERROR; | |
460 | ||
461 | // Walk through the entire tree | |
462 | r = loc_network_tree_walk(tree, NULL, loc_network_tree_merge_step, &ctx); | |
463 | if (r) | |
464 | goto ERROR; | |
465 | ||
466 | DEBUG(tree->ctx, "%u network(s) have been merged\n", ctx.merged); | |
467 | ||
468 | ERROR: | |
469 | if (ctx.networks) | |
470 | loc_network_list_unref(ctx.networks); | |
471 | ||
472 | return r; | |
473 | } | |
474 | ||
475 | /* | |
476 | Deduplicate the tree | |
477 | */ | |
478 | ||
479 | struct loc_network_tree_dedup_ctx { | |
480 | struct loc_network_tree* tree; | |
481 | struct loc_network_list* stack; | |
578fda4e MT |
482 | unsigned int* removed; |
483 | int family; | |
fe8277ed MT |
484 | }; |
485 | ||
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; | |
489 | int r; | |
490 | ||
e5e53b59 | 491 | // Walk through all networks on the stack... |
fe8277ed MT |
492 | for (int i = loc_network_list_size(ctx->stack) - 1; i >= 0; i--) { |
493 | n = loc_network_list_get(ctx->stack, i); | |
494 | ||
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); | |
500 | if (r) | |
9153d1e7 | 501 | goto END; |
fe8277ed MT |
502 | |
503 | // Count | |
578fda4e | 504 | (*ctx->removed)++; |
fe8277ed MT |
505 | |
506 | // Once we removed the subnet, we are done | |
507 | goto END; | |
508 | } | |
509 | ||
510 | // Once we found a subnet, we are done | |
511 | break; | |
512 | } | |
9153d1e7 | 513 | |
e5e53b59 MT |
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); | |
517 | if (r) | |
518 | goto END; | |
519 | ||
9153d1e7 MT |
520 | loc_network_unref(n); |
521 | n = NULL; | |
fe8277ed MT |
522 | } |
523 | ||
524 | // If network did not get removed, we push it into the stack | |
525 | r = loc_network_list_push(ctx->stack, network); | |
526 | if (r) | |
527 | return r; | |
528 | ||
529 | END: | |
530 | if (n) | |
531 | loc_network_unref(n); | |
532 | ||
533 | return r; | |
534 | } | |
535 | ||
578fda4e MT |
536 | static int loc_network_tree_dedup_filter(struct loc_network* network, void* data) { |
537 | const struct loc_network_tree_dedup_ctx* ctx = data; | |
538 | ||
539 | // Match address family | |
540 | return ctx->family == loc_network_address_family(network); | |
541 | } | |
542 | ||
543 | static int loc_network_tree_dedup_one(struct loc_network_tree* tree, | |
544 | const int family, unsigned int* removed) { | |
fe8277ed MT |
545 | struct loc_network_tree_dedup_ctx ctx = { |
546 | .tree = tree, | |
547 | .stack = NULL, | |
578fda4e MT |
548 | .removed = removed, |
549 | .family = family, | |
fe8277ed MT |
550 | }; |
551 | int r; | |
552 | ||
553 | r = loc_network_list_new(tree->ctx, &ctx.stack); | |
554 | if (r) | |
555 | return r; | |
556 | ||
557 | // Walk through the entire tree | |
578fda4e MT |
558 | r = loc_network_tree_walk(tree, |
559 | loc_network_tree_dedup_filter, loc_network_tree_dedup_step, &ctx); | |
fe8277ed MT |
560 | if (r) |
561 | goto ERROR; | |
562 | ||
fe8277ed MT |
563 | ERROR: |
564 | if (ctx.stack) | |
565 | loc_network_list_unref(ctx.stack); | |
566 | ||
567 | return r; | |
568 | } | |
569 | ||
578fda4e MT |
570 | static int loc_network_tree_dedup(struct loc_network_tree* tree) { |
571 | unsigned int removed = 0; | |
572 | int r; | |
573 | ||
574 | r = loc_network_tree_dedup_one(tree, AF_INET6, &removed); | |
575 | if (r) | |
576 | return r; | |
577 | ||
578 | r = loc_network_tree_dedup_one(tree, AF_INET, &removed); | |
579 | if (r) | |
580 | return r; | |
581 | ||
582 | DEBUG(tree->ctx, "%u network(s) have been removed\n", removed); | |
583 | ||
584 | return 0; | |
585 | } | |
586 | ||
fe8277ed MT |
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; | |
590 | int r0 = 1; | |
591 | int r1 = 1; | |
592 | ||
593 | // Return for nodes that have already been deleted | |
594 | if (n->deleted) | |
595 | goto DELETE; | |
596 | ||
597 | // Delete zero | |
598 | if (n->zero) { | |
599 | r0 = loc_network_tree_delete_node(tree, &n->zero); | |
600 | if (r0 < 0) | |
601 | return r0; | |
602 | } | |
603 | ||
604 | // Delete one | |
605 | if (n->one) { | |
606 | r1 = loc_network_tree_delete_node(tree, &n->one); | |
607 | if (r1 < 0) | |
608 | return r1; | |
609 | } | |
610 | ||
611 | // Don't delete this node if we are a leaf | |
612 | if (n->network) | |
613 | return 0; | |
614 | ||
615 | // Don't delete this node if has child nodes that we need | |
616 | if (!r0 || !r1) | |
617 | return 0; | |
618 | ||
619 | // Don't delete root | |
620 | if (tree->root == n) | |
621 | return 0; | |
622 | ||
623 | DELETE: | |
624 | // It is now safe to delete the node | |
625 | loc_network_tree_node_unref(n); | |
626 | *node = NULL; | |
627 | ||
628 | return 1; | |
629 | } | |
630 | ||
631 | static int loc_network_tree_delete_nodes(struct loc_network_tree* tree) { | |
632 | int r; | |
633 | ||
634 | r = loc_network_tree_delete_node(tree, &tree->root); | |
635 | if (r < 0) | |
636 | return r; | |
637 | ||
638 | return 0; | |
639 | } | |
640 | ||
641 | int loc_network_tree_cleanup(struct loc_network_tree* tree) { | |
642 | int r; | |
643 | ||
644 | // Deduplicate the tree | |
645 | r = loc_network_tree_dedup(tree); | |
646 | if (r) | |
647 | return r; | |
648 | ||
649 | // Merge networks | |
650 | r = loc_network_tree_merge(tree); | |
651 | if (r) { | |
652 | ERROR(tree->ctx, "Could not merge networks: %m\n"); | |
653 | return r; | |
654 | } | |
655 | ||
656 | // Delete any unneeded nodes | |
657 | r = loc_network_tree_delete_nodes(tree); | |
658 | if (r) | |
659 | return r; | |
660 | ||
661 | return 0; | |
662 | } |