diff options
Diffstat (limited to 'src/knot/zone/zone-tree.c')
| -rw-r--r-- | src/knot/zone/zone-tree.c | 512 |
1 files changed, 512 insertions, 0 deletions
diff --git a/src/knot/zone/zone-tree.c b/src/knot/zone/zone-tree.c new file mode 100644 index 0000000..87dde18 --- /dev/null +++ b/src/knot/zone/zone-tree.c @@ -0,0 +1,512 @@ +/* Copyright (C) 2022 CZ.NIC, z.s.p.o. <knot-dns@labs.nic.cz> + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <https://www.gnu.org/licenses/>. + */ + +#include <assert.h> +#include <stdlib.h> + +#include "knot/zone/zone-tree.h" +#include "libknot/consts.h" +#include "libknot/errcode.h" +#include "libknot/packet/wire.h" + +typedef struct { + zone_tree_apply_cb_t func; + void *data; + int binode_second; +} zone_tree_func_t; + +static int tree_apply_cb(trie_val_t *node, void *data) +{ + zone_tree_func_t *f = (zone_tree_func_t *)data; + zone_node_t *n = (zone_node_t *)(*node) + f->binode_second; + assert(!f->binode_second || (n->flags & NODE_FLAGS_SECOND)); + return f->func(n, f->data); +} + +zone_tree_t *zone_tree_create(bool use_binodes) +{ + zone_tree_t *t = calloc(1, sizeof(*t)); + if (t != NULL) { + if (use_binodes) { + t->flags = ZONE_TREE_USE_BINODES; + } + t->trie = trie_create(NULL); + if (t->trie == NULL) { + free(t); + t = NULL; + } + } + return t; +} + +zone_tree_t *zone_tree_cow(zone_tree_t *from) +{ + zone_tree_t *to = calloc(1, sizeof(*to)); + if (to == NULL) { + return to; + } + to->flags = from->flags ^ ZONE_TREE_BINO_SECOND; + from->cow = trie_cow(from->trie, NULL, NULL); + to->cow = from->cow; + to->trie = trie_cow_new(to->cow); + if (to->trie == NULL) { + free(to); + to = NULL; + } + return to; +} + +static trie_val_t nocopy(const trie_val_t val, _unused_ knot_mm_t *mm) +{ + return val; +} + +zone_tree_t *zone_tree_shallow_copy(zone_tree_t *from) +{ + zone_tree_t *to = calloc(1, sizeof(*to)); + if (to == NULL) { + return to; + } + to->flags = from->flags; + to->trie = trie_dup(from->trie, nocopy, NULL); + if (to->trie == NULL) { + free(to); + to = NULL; + } + return to; +} + +int zone_tree_insert(zone_tree_t *tree, zone_node_t **node) +{ + if (tree == NULL || node == NULL || *node == NULL) { + return KNOT_EINVAL; + } + + assert((*node)->owner); + knot_dname_storage_t lf_storage; + uint8_t *lf = knot_dname_lf((*node)->owner, lf_storage); + assert(lf); + + if (tree->cow != NULL) { + *trie_get_cow(tree->cow, lf + 1, *lf) = binode_first(*node); + } else { + *trie_get_ins(tree->trie, lf + 1, *lf) = binode_first(*node); + } + + *node = zone_tree_fix_get(*node, tree); + + return KNOT_EOK; +} + +int zone_tree_insert_with_parents(zone_tree_t *tree, zone_node_t *node, bool without_parents) +{ + int ret = KNOT_EOK; + do { + ret = zone_tree_insert(tree, &node); + node = node->parent; + } while (node != NULL && ret == KNOT_EOK && !without_parents); + return ret; +} + +zone_node_t *zone_tree_get(zone_tree_t *tree, const knot_dname_t *owner) +{ + if (owner == NULL) { + return NULL; + } + + if (zone_tree_is_empty(tree)) { + return NULL; + } + + knot_dname_storage_t lf_storage; + uint8_t *lf = knot_dname_lf(owner, lf_storage); + assert(lf); + + trie_val_t *val = trie_get_try(tree->trie, lf + 1, *lf); + if (val == NULL) { + return NULL; + } + + return zone_tree_fix_get(*val, tree); +} + +int zone_tree_get_less_or_equal(zone_tree_t *tree, + const knot_dname_t *owner, + zone_node_t **found, + zone_node_t **previous) +{ + if (owner == NULL || found == NULL || previous == NULL) { + return KNOT_EINVAL; + } + + if (zone_tree_is_empty(tree)) { + return KNOT_ENONODE; + } + + knot_dname_storage_t lf_storage; + uint8_t *lf = knot_dname_lf(owner, lf_storage); + assert(lf); + + trie_val_t *fval = NULL; + int ret = trie_get_leq(tree->trie, lf + 1, *lf, &fval); + if (fval != NULL) { + *found = zone_tree_fix_get(*fval, tree); + } + + int exact_match = 0; + if (ret == KNOT_EOK) { + if (fval != NULL) { + *previous = node_prev(*found); + } + exact_match = 1; + } else if (ret == 1) { + *previous = *found; + *found = NULL; + } else { + /* Previous should be the rightmost node. + * For regular zone it is the node left of apex, but for some + * cases like NSEC3, there is no such sort of thing (name wise). + */ + /*! \todo We could store rightmost node in zonetree probably. */ + zone_tree_it_t it = { 0 }; + ret = zone_tree_it_begin(tree, &it); + if (ret != KNOT_EOK) { + return ret; + } + *previous = zone_tree_it_val(&it); /* leftmost */ + assert(*previous != NULL); // cppcheck + *previous = zone_tree_fix_get(*previous, tree); + *previous = node_prev(*previous); /* rightmost */ + *found = NULL; + zone_tree_it_free(&it); + } + + return exact_match; +} + +/*! \brief Removes node with the given owner from the zone tree. */ +void zone_tree_remove_node(zone_tree_t *tree, const knot_dname_t *owner) +{ + if (zone_tree_is_empty(tree) || owner == NULL) { + return; + } + + knot_dname_storage_t lf_storage; + uint8_t *lf = knot_dname_lf(owner, lf_storage); + assert(lf); + + trie_val_t *rval = trie_get_try(tree->trie, lf + 1, *lf); + if (rval != NULL) { + if (tree->cow != NULL) { + trie_del_cow(tree->cow, lf + 1, *lf, NULL); + } else { + trie_del(tree->trie, lf + 1, *lf, NULL); + } + } +} + +int zone_tree_add_node(zone_tree_t *tree, zone_node_t *apex, const knot_dname_t *dname, + zone_tree_new_node_cb_t new_cb, void *new_cb_ctx, zone_node_t **new_node) +{ + int in_bailiwick = knot_dname_in_bailiwick(dname, apex->owner); + if (in_bailiwick == 0) { + *new_node = apex; + return KNOT_EOK; + } else if (in_bailiwick < 0) { + return KNOT_EOUTOFZONE; + } + + *new_node = zone_tree_get(tree, dname); + if (*new_node == NULL) { + *new_node = new_cb(dname, new_cb_ctx); + if (*new_node == NULL) { + return KNOT_ENOMEM; + } + int ret = zone_tree_insert(tree, new_node); + assert(!((*new_node)->flags & NODE_FLAGS_DELETED)); + if (ret != KNOT_EOK) { + return ret; + } + zone_node_t *parent = NULL; + ret = zone_tree_add_node(tree, apex, knot_wire_next_label(dname, NULL), new_cb, new_cb_ctx, &parent); + if (ret != KNOT_EOK) { + return ret; + } + (*new_node)->parent = parent; + if (parent != NULL) { + parent->children++; + if (knot_dname_is_wildcard(dname)) { + parent->flags |= NODE_FLAGS_WILDCARD_CHILD; + } + } + } + return KNOT_EOK; +} + +int zone_tree_del_node(zone_tree_t *tree, zone_node_t *node, bool free_deleted) +{ + zone_node_t *parent = node_parent(node); + bool wildcard = knot_dname_is_wildcard(node->owner); + + node->parent = NULL; + node->flags |= NODE_FLAGS_DELETED; + zone_tree_remove_node(tree, node->owner); + + if (free_deleted) { + node_free(node, NULL); + } + + int ret = KNOT_EOK; + if (ret == KNOT_EOK && parent != NULL) { + parent->children--; + if (wildcard) { + parent->flags &= ~NODE_FLAGS_WILDCARD_CHILD; + } + if (parent->children == 0 && parent->rrset_count == 0 && + !(parent->flags & NODE_FLAGS_APEX)) { + ret = zone_tree_del_node(tree, parent, free_deleted); + } + } + return ret; +} + +int zone_tree_apply(zone_tree_t *tree, zone_tree_apply_cb_t function, void *data) +{ + if (function == NULL) { + return KNOT_EINVAL; + } + + if (zone_tree_is_empty(tree)) { + return KNOT_EOK; + } + + zone_tree_func_t f = { + .func = function, + .data = data, + .binode_second = ((tree->flags & ZONE_TREE_BINO_SECOND) ? 1 : 0), + }; + + return trie_apply(tree->trie, tree_apply_cb, &f); +} + +int zone_tree_sub_apply(zone_tree_t *tree, const knot_dname_t *sub_root, + bool excl_root, zone_tree_apply_cb_t function, void *data) +{ + zone_tree_it_t it = { 0 }; + int ret = zone_tree_it_sub_begin(tree, sub_root, &it); + if (excl_root && ret == KNOT_EOK && !zone_tree_it_finished(&it)) { + zone_tree_it_next(&it); + } + while (ret == KNOT_EOK && !zone_tree_it_finished(&it)) { + ret = function(zone_tree_it_val(&it), data); + zone_tree_it_next(&it); + } + zone_tree_it_free(&it); + return ret; +} + +int zone_tree_it_begin(zone_tree_t *tree, zone_tree_it_t *it) +{ + return zone_tree_it_double_begin(tree, NULL, it); +} + +int zone_tree_it_sub_begin(zone_tree_t *tree, const knot_dname_t *sub_root, + zone_tree_it_t *it) +{ + if (tree == NULL || sub_root == NULL) { + return KNOT_EINVAL; + } + int ret = zone_tree_it_begin(tree, it); + if (ret != KNOT_EOK) { + return ret; + } + it->sub_root = knot_dname_copy(sub_root, NULL); + knot_dname_storage_t lf_storage; + uint8_t *lf = knot_dname_lf(sub_root, lf_storage); + ret = trie_it_get_leq(it->it, lf + 1, *lf); + if ((ret != KNOT_EOK && ret != KNOT_ENOENT) || it->sub_root == NULL) { + zone_tree_it_free(it); + return ret == KNOT_EOK ? KNOT_ENOMEM : ret; + } + return KNOT_EOK; +} + +int zone_tree_it_double_begin(zone_tree_t *first, zone_tree_t *second, zone_tree_it_t *it) +{ + if (it->tree == NULL) { + it->it = trie_it_begin(first->trie); + if (it->it == NULL) { + return KNOT_ENOMEM; + } + if (trie_it_finished(it->it) && second != NULL) { // first tree is empty + trie_it_free(it->it); + it->it = trie_it_begin(second->trie); + it->tree = second; + it->next_tree = NULL; + } else { + it->tree = first; + it->next_tree = second; + } + it->binode_second = ((it->tree->flags & ZONE_TREE_BINO_SECOND) ? 1 : 0); + } + return KNOT_EOK; +} + +static bool sub_done(zone_tree_it_t *it) +{ + return it->sub_root != NULL && + knot_dname_in_bailiwick(zone_tree_it_val(it)->owner, it->sub_root) < 0; +} + +bool zone_tree_it_finished(zone_tree_it_t *it) +{ + return it->it == NULL || it->tree == NULL || trie_it_finished(it->it) || sub_done(it); +} + +zone_node_t *zone_tree_it_val(zone_tree_it_t *it) +{ + zone_node_t *node = (zone_node_t *)(*trie_it_val(it->it)) + it->binode_second; + assert(!it->binode_second || (node->flags & NODE_FLAGS_SECOND)); + return node; +} + +void zone_tree_it_del(zone_tree_it_t *it) +{ + trie_it_del(it->it); +} + +void zone_tree_it_next(zone_tree_it_t *it) +{ + trie_it_next(it->it); + if (it->next_tree != NULL && trie_it_finished(it->it)) { + trie_it_free(it->it); + it->tree = it->next_tree; + it->binode_second = ((it->tree->flags & ZONE_TREE_BINO_SECOND) ? 1 : 0); + it->next_tree = NULL; + it->it = trie_it_begin(it->tree->trie); + assert(it->sub_root == NULL); + } +} + +void zone_tree_it_free(zone_tree_it_t *it) +{ + trie_it_free(it->it); + knot_dname_free(it->sub_root, NULL); + memset(it, 0, sizeof(*it)); +} + +int zone_tree_delsafe_it_begin(zone_tree_t *tree, zone_tree_delsafe_it_t *it, bool include_deleted) +{ + it->incl_del = include_deleted; + it->total = zone_tree_count(tree); + if (it->total == 0) { + it->current = 0; + it->nodes = NULL; + return KNOT_EOK; + } + it->nodes = malloc(it->total * sizeof(*it->nodes)); + if (it->nodes == NULL) { + return KNOT_ENOMEM; + } + it->current = 0; + + zone_tree_it_t tmp = { 0 }; + int ret = zone_tree_it_begin(tree, &tmp); + if (ret != KNOT_EOK) { + return ret; + } + while (!zone_tree_it_finished(&tmp)) { + it->nodes[it->current++] = zone_tree_it_val(&tmp); + zone_tree_it_next(&tmp); + } + zone_tree_it_free(&tmp); + assert(it->total == it->current); + + zone_tree_delsafe_it_restart(it); + + return KNOT_EOK; +} + +bool zone_tree_delsafe_it_finished(zone_tree_delsafe_it_t *it) +{ + return (it->current >= it->total); +} + +void zone_tree_delsafe_it_restart(zone_tree_delsafe_it_t *it) +{ + it->current = 0; + + while (!it->incl_del && !zone_tree_delsafe_it_finished(it) && + (zone_tree_delsafe_it_val(it)->flags & NODE_FLAGS_DELETED)) { + it->current++; + } +} + +zone_node_t *zone_tree_delsafe_it_val(zone_tree_delsafe_it_t *it) +{ + return it->nodes[it->current]; +} + +void zone_tree_delsafe_it_next(zone_tree_delsafe_it_t *it) +{ + do { + it->current++; + } while (!it->incl_del && !zone_tree_delsafe_it_finished(it) && + (zone_tree_delsafe_it_val(it)->flags & NODE_FLAGS_DELETED)); +} + +void zone_tree_delsafe_it_free(zone_tree_delsafe_it_t *it) +{ + free(it->nodes); + memset(it, 0, sizeof(*it)); +} + +static int merge_cb(zone_node_t *node, void *ctx) +{ + return zone_tree_insert(ctx, &node); +} + +int zone_tree_merge(zone_tree_t *into, zone_tree_t *what) +{ + return zone_tree_apply(what, merge_cb, into); +} + +static int binode_unify_cb(zone_node_t *node, void *ctx) +{ + binode_unify(node, *(bool *)ctx, NULL); + return KNOT_EOK; +} + +void zone_trees_unify_binodes(zone_tree_t *nodes, zone_tree_t *nsec3_nodes, bool free_deleted) +{ + if (nodes != NULL) { + zone_tree_apply(nodes, binode_unify_cb, &free_deleted); + } + if (nsec3_nodes != NULL) { + zone_tree_apply(nsec3_nodes, binode_unify_cb, &free_deleted); + } +} + +void zone_tree_free(zone_tree_t **tree) +{ + if (tree == NULL || *tree == NULL) { + return; + } + + trie_free((*tree)->trie); + free(*tree); + *tree = NULL; +} |