diff options
Diffstat (limited to 'src/libknot/zone')
| -rw-r--r-- | src/libknot/zone/dname-table.c | 310 | ||||
| -rw-r--r-- | src/libknot/zone/dname-table.h | 168 | ||||
| -rw-r--r-- | src/libknot/zone/node.c | 906 | ||||
| -rw-r--r-- | src/libknot/zone/node.h | 436 | ||||
| -rw-r--r-- | src/libknot/zone/zone-contents.c | 2396 | ||||
| -rw-r--r-- | src/libknot/zone/zone-contents.h | 556 | ||||
| -rw-r--r-- | src/libknot/zone/zone-tree.c | 470 | ||||
| -rw-r--r-- | src/libknot/zone/zone-tree.h | 300 | ||||
| -rw-r--r-- | src/libknot/zone/zone.c | 246 | ||||
| -rw-r--r-- | src/libknot/zone/zone.h | 157 | ||||
| -rw-r--r-- | src/libknot/zone/zonedb.c | 389 | ||||
| -rw-r--r-- | src/libknot/zone/zonedb.h | 145 |
12 files changed, 6479 insertions, 0 deletions
diff --git a/src/libknot/zone/dname-table.c b/src/libknot/zone/dname-table.c new file mode 100644 index 0000000..c41b4bd --- /dev/null +++ b/src/libknot/zone/dname-table.c @@ -0,0 +1,310 @@ +/* Copyright (C) 2011 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 <http://www.gnu.org/licenses/>. + */ + +#include <assert.h> +#include <string.h> +#include <stdlib.h> +#include <stdio.h> +#include <stddef.h> + +#include "zone/dname-table.h" +#include "util/error.h" + +/*!< Tree functions. */ +TREE_DEFINE(dname_table_node, avl); + +struct knot_dname_table_fnc_data { + void (*func)(knot_dname_t *dname, void *data); + void *data; +}; + +static void knot_dname_table_apply(struct dname_table_node *node, void *data) +{ + assert(data != NULL); + assert(node != NULL); + struct knot_dname_table_fnc_data *d = + (struct knot_dname_table_fnc_data *)data; + d->func(node->dname, d->data); +} + +/*! + * \brief Comparison function to be used with tree. + * + * \param n1 First dname to be compared. + * \param n2 Second dname to be compared. + * + * \return strncmp of dname's wireformats. + */ +static int compare_dname_table_nodes(struct dname_table_node *n1, + struct dname_table_node *n2) +{ + assert(n1 && n2); + return (strncmp((char *)n1->dname->name, (char *)n2->dname->name, + (n1->dname->size < n2->dname->size) ? + (n1->dname->size):(n2->dname->size))); +} + +/*! + * \brief Deletes tree node along with its domain name. + * + * \param node Node to be deleted. + * \param data If <> 0, dname in the node will be freed as well. + */ +static void delete_dname_table_node(struct dname_table_node *node, void *data) +{ + if ((ssize_t)data == 1) { + knot_dname_release(node->dname); + } else if ((ssize_t)data == 2) { + knot_dname_free(&node->dname); + } + + /*!< \todo it would be nice to set pointers to NULL. */ + free(node); +} + +static void knot_dname_table_delete_subtree(struct dname_table_node *root) +{ + if (root == NULL) { + return; + } + + knot_dname_table_delete_subtree(root->avl.avl_left); + knot_dname_table_delete_subtree(root->avl.avl_right); + free(root); +} + +static int knot_dname_table_copy_node(const struct dname_table_node *from, + struct dname_table_node **to) +{ + if (from == NULL) { + return KNOT_EOK; + } + + *to = (struct dname_table_node *) + malloc(sizeof(struct dname_table_node)); + if (*to == NULL) { + return KNOT_ENOMEM; + } + memset(*to, 0, sizeof(struct dname_table_node)); + + (*to)->dname = from->dname; + knot_dname_retain((*to)->dname); + (*to)->avl.avl_height = from->avl.avl_height; + + int ret = knot_dname_table_copy_node(from->avl.avl_left, + &(*to)->avl.avl_left); + if (ret != KNOT_EOK) { + return ret; + } + + ret = knot_dname_table_copy_node(from->avl.avl_right, + &(*to)->avl.avl_right); + if (ret != KNOT_EOK) { + knot_dname_table_delete_subtree((*to)->avl.avl_left); + (*to)->avl.avl_left = NULL; + return ret; + } + + return KNOT_EOK; +} + +knot_dname_table_t *knot_dname_table_new() +{ + knot_dname_table_t *ret = malloc(sizeof(knot_dname_table_t)); + CHECK_ALLOC_LOG(ret, NULL); + + ret->tree = malloc(sizeof(table_tree_t)); + if (ret->tree == NULL) { + ERR_ALLOC_FAILED; + free(ret); + return NULL; + } + + TREE_INIT(ret->tree, compare_dname_table_nodes); + + ret->id_counter = 1; + + return ret; +} + +knot_dname_t *knot_dname_table_find_dname(const knot_dname_table_t *table, + knot_dname_t *dname) +{ + if (table == NULL || dname == NULL) { + return NULL; + } + + struct dname_table_node *node = NULL; + struct dname_table_node sought; + sought.dname = dname; + + node = TREE_FIND(table->tree, dname_table_node, avl, &sought); + + if (node == NULL) { + return NULL; + } else { + /* Increase reference counter. */ + knot_dname_retain(node->dname); + + return node->dname; + } +} + +int knot_dname_table_add_dname(knot_dname_table_t *table, + knot_dname_t *dname) +{ + if (dname == NULL || table == NULL) { + return KNOT_EBADARG; + } + + /* Node for insertion has to be created */ + struct dname_table_node *node = + malloc(sizeof(struct dname_table_node)); + CHECK_ALLOC_LOG(node, KNOT_ENOMEM); + + // convert the dname to lowercase + knot_dname_to_lower(dname); + + node->dname = dname; + node->avl.avl_height = 0; + node->avl.avl_left = NULL; + node->avl.avl_right = NULL; + + node->dname->id = table->id_counter++; + assert(node->dname->id != 0); + + /* Increase reference counter. */ + knot_dname_retain(dname); + + TREE_INSERT(table->tree, dname_table_node, avl, node); + return KNOT_EOK; +} + +int knot_dname_table_add_dname_check(knot_dname_table_t *table, + knot_dname_t **dname) +{ + knot_dname_t *found_dname = NULL; + + if (table == NULL || dname == NULL || *dname == NULL) { + return KNOT_EBADARG; + } + + /* Fetch dname, need to release it later. */ + found_dname = knot_dname_table_find_dname(table ,*dname); + + if (!found_dname) { + /* Store reference in table. */ + return knot_dname_table_add_dname(table, *dname); + } else { + /*! \todo Remove the check for equality. */ + if (found_dname != *dname) { + /* Replace dname with found. */ + knot_dname_release(*dname); + *dname = found_dname; + return 1; /*! \todo Error code? */ + + } else { + + /* If the dname is already in the table, there is already + * a reference to it. + */ + knot_dname_release(found_dname); + } + } + + return KNOT_EOK; +} + +int knot_dname_table_shallow_copy(knot_dname_table_t *from, + knot_dname_table_t *to) +{ + to->id_counter = from->id_counter; + + if (to->tree == NULL) { + to->tree = malloc(sizeof(table_tree_t)); + if (to->tree == NULL) { + ERR_ALLOC_FAILED; + return KNOT_ENOMEM; + } + + TREE_INIT(to->tree, compare_dname_table_nodes); + } + + return knot_dname_table_copy_node(from->tree->th_root, + &to->tree->th_root); +} + +void knot_dname_table_free(knot_dname_table_t **table) +{ + if (table == NULL || *table == NULL) { + return; + } + + /* Walk the tree and free each node, but not the dnames. */ + TREE_POST_ORDER_APPLY((*table)->tree, dname_table_node, avl, + delete_dname_table_node, 0); + + free((*table)->tree); + + free(*table); + *table = NULL; +} + +void knot_dname_table_deep_free(knot_dname_table_t **table) +{ + if (table == NULL || *table == NULL) { + return; + } + + /* Walk the tree and free each node, but free the dnames. */ + TREE_POST_ORDER_APPLY((*table)->tree, dname_table_node, avl, + delete_dname_table_node, (void *) 1); + + free((*table)->tree); + + free(*table); + *table = NULL; +} + +void knot_dname_table_destroy(knot_dname_table_t **table) +{ + if (table == NULL || *table == NULL) { + return; + } + + /* Walk the tree and free each node, but free the dnames. */ + TREE_POST_ORDER_APPLY((*table)->tree, dname_table_node, avl, + delete_dname_table_node, (void *) 2); + + free((*table)->tree); + + free(*table); + *table = NULL; +} + +void knot_dname_table_tree_inorder_apply(const knot_dname_table_t *table, + void (*applied_function)(knot_dname_t *node, + void *data), + void *data) +{ + struct knot_dname_table_fnc_data d; + d.data = data; + d.func = applied_function; + + TREE_FORWARD_APPLY(table->tree, dname_table_node, avl, + knot_dname_table_apply, &d); +} + diff --git a/src/libknot/zone/dname-table.h b/src/libknot/zone/dname-table.h new file mode 100644 index 0000000..dd86eaf --- /dev/null +++ b/src/libknot/zone/dname-table.h @@ -0,0 +1,168 @@ +/*! + * \file dname-table.h + * + * \author Jan Kadlec <jan.kadlec.@nic.cz> + * + * \brief Structures representing dname table and functions for + * manipulating these structures. + * + * \addtogroup libknot + * @{ + */ +/* Copyright (C) 2011 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 <http://www.gnu.org/licenses/>. + */ + +#ifndef _KNOT_DNAME_TABLE_H_ +#define _KNOT_DNAME_TABLE_H_ + +#include <config.h> + +#include "common/tree.h" + +#include "dname.h" +#include "common.h" + + +/*! + * \brief Structure encapsulating + */ +struct dname_table_node { + knot_dname_t *dname; /*!< Dname stored in node. */ + TREE_ENTRY(dname_table_node) avl; /*!< Tree variables. */ +}; + +/*! + * \brief Tree structure. + */ +typedef TREE_HEAD(avl, dname_table_node) table_tree_t; + +/*! + * \brief Structure holding tree together with dname ID counter. + */ +struct knot_dname_table { + unsigned int id_counter; /*!< ID counter (starts from 1) */ + table_tree_t *tree; /*!< AVL tree */ +}; + +typedef struct knot_dname_table knot_dname_table_t; + +/*! + * \brief Creates new empty domain name table. + * + * \retval Created table on success. + * \retval NULL on memory error. + */ +knot_dname_table_t *knot_dname_table_new(); + +/*! + * \brief Finds name in the domain name table. + * + * \note Reference count to dname will be incremented, caller is responsible + * for releasing it. + * + * \param table Domain name table to be searched. + * \param dname Dname to be searched. + * + * \retval Pointer to found dname when dname is present in the table. + * \retval NULL when dname is not present. + */ +knot_dname_t *knot_dname_table_find_dname(const knot_dname_table_t *table, + knot_dname_t *dname); + +/*! + * \brief Adds domain name to domain name table. + * + * \param table Domain name table to be added to. + * \param dname Domain name to be added. + * + * \warning Function does not check for duplicates! + * + * \note This function encapsulates dname in a structure and saves it to a tree. + * + * \retval KNOT_EOK on success. + * \retval KNOT_ENOMEM when memory runs out. + */ +int knot_dname_table_add_dname(knot_dname_table_t *table, + knot_dname_t *dname); + +/*! + * \brief Adds domain name to domain name table and checks for duplicates. + * + * \param table Domain name table to be added to. + * \param dname Domain name to be added. + * + * \note This function encapsulates dname in a structure and saves it to a tree. + * \note If a duplicate is found, \a dname is replaced by the name from table. + * + * \retval KNOT_EOK on success. + * \retval KNOT_ENOMEM when memory runs out. + */ +int knot_dname_table_add_dname_check(knot_dname_table_t *table, + knot_dname_t **dname); + +/*! + * \brief Creates a shallow copy of the domain name table. + * + * Expects an existing knot_dname_table_t structure to be passed via \a to, + * and fills it with the same data (domain names) as the original. Actual + * tree nodes are created, but domain names are not copied (just referenced). + * + * \param from Original domain name table. + * \param to Copy of the domain name table. + */ +int knot_dname_table_shallow_copy(knot_dname_table_t *from, + knot_dname_table_t *to); + +/*! + * \brief Frees dname table without its nodes. Sets pointer to NULL. + * + * \param table Table to be freed. + */ +void knot_dname_table_free(knot_dname_table_t **table); + +/*! + * \brief Frees dname table and all its nodes (and release dnames in the nodes) + * Sets pointer to NULL. + * + * \param table Table to be freed. + */ +void knot_dname_table_deep_free(knot_dname_table_t **table); + +/*! + * \brief Frees dname table and all its nodes (including dnames in the nodes) + * Sets pointer to NULL. + * + * \param table Table to be freed. + */ +void knot_dname_table_destroy(knot_dname_table_t **table); + +/*! + * \brief Encapsulation of domain name table tree traversal function. + * + * \param table Table containing tree to be traversed. + * \param applied_function Function to be used to process nodes. + * \param data Data to be passed to processing function. + */ +void knot_dname_table_tree_inorder_apply(const knot_dname_table_t *table, + void (*applied_function)(knot_dname_t *dname, + void *data), + void *data); + + +#endif // _KNOT_DNAME_TABLE_H_ + +/*! @} */ + diff --git a/src/libknot/zone/node.c b/src/libknot/zone/node.c new file mode 100644 index 0000000..1d2f938 --- /dev/null +++ b/src/libknot/zone/node.c @@ -0,0 +1,906 @@ +/* Copyright (C) 2011 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 <http://www.gnu.org/licenses/>. + */ + +#include <config.h> +#include <stdlib.h> +#include <assert.h> +#include <stdio.h> + +#include <urcu.h> + +#include "common.h" +#include "zone/node.h" +#include "rrset.h" +#include "util/error.h" +#include "common/skip-list.h" +#include "common/tree.h" +#include "util/debug.h" + +/*----------------------------------------------------------------------------*/ +/* Non-API functions */ +/*----------------------------------------------------------------------------*/ +/*! + * \brief Returns the delegation point flag + * + * \param flags Flags to retrieve the flag from. + * + * \return A byte with only the delegation point flag set if it was set in + * \a flags. + */ +static inline uint8_t knot_node_flags_get_deleg(uint8_t flags) +{ + return flags & KNOT_NODE_FLAGS_DELEG; +} + +/*----------------------------------------------------------------------------*/ +/*! + * \brief Sets the delegation point flag. + * + * \param flags Flags to set the flag in. + */ +static inline void knot_node_flags_set_deleg(uint8_t *flags) +{ + *flags |= KNOT_NODE_FLAGS_DELEG; +} + +/*----------------------------------------------------------------------------*/ +/*! + * \brief Returns the non-authoritative node flag + * + * \param flags Flags to retrieve the flag from. + * + * \return A byte with only the non-authoritative node flag set if it was set in + * \a flags. + */ +static inline uint8_t knot_node_flags_get_nonauth(uint8_t flags) +{ + return flags & KNOT_NODE_FLAGS_NONAUTH; +} + +/*----------------------------------------------------------------------------*/ +/*! + * \brief Sets the non-authoritative node flag. + * + * \param flags Flags to set the flag in. + */ +static inline void knot_node_flags_set_nonauth(uint8_t *flags) +{ + *flags |= KNOT_NODE_FLAGS_NONAUTH; +} + +/*----------------------------------------------------------------------------*/ +/*! + * \brief Returns the old node flag + * + * \param flags Flags to retrieve the flag from. + * + * \return A byte with only the old node flag set if it was set in \a flags. + */ +static inline uint8_t knot_node_flags_get_old(uint8_t flags) +{ + return flags & KNOT_NODE_FLAGS_OLD; +} + +/*----------------------------------------------------------------------------*/ +/*! + * \brief Sets the old node flag. + * + * \param flags Flags to set the flag in. + */ +static inline void knot_node_flags_set_new(uint8_t *flags) +{ + *flags |= KNOT_NODE_FLAGS_NEW; +} + +/*----------------------------------------------------------------------------*/ +/*! + * \brief Returns the new node flag + * + * \param flags Flags to retrieve the flag from. + * + * \return A byte with only the new node flag set if it was set in \a flags. + */ +static inline uint8_t knot_node_flags_get_new(uint8_t flags) +{ + return flags & KNOT_NODE_FLAGS_NEW; +} + +/*----------------------------------------------------------------------------*/ +/*! + * \brief Sets the new node flag. + * + * \param flags Flags to set the flag in. + */ +static inline void knot_node_flags_set_old(uint8_t *flags) +{ + *flags |= KNOT_NODE_FLAGS_OLD; +} + +/*----------------------------------------------------------------------------*/ + +static inline void knot_node_flags_clear_new(uint8_t *flags) +{ + *flags &= ~KNOT_NODE_FLAGS_NEW; +} + +/*----------------------------------------------------------------------------*/ + +static inline void knot_node_flags_clear_old(uint8_t *flags) +{ + *flags &= ~KNOT_NODE_FLAGS_OLD; +} + +/*----------------------------------------------------------------------------*/ +/*! + * \brief Compares the two keys as RR types. + * + * \note This function may be used in data structures requiring generic + * comparation function. + * + * \param key1 First RR type. + * \param key2 Second RR type. + * + * \retval 0 if \a key1 is equal to \a key2. + * \retval < 0 if \a key1 is lower than \a key2. + * \retval > 0 if \a key1 is higher than \a key2. + */ +static int compare_rrset_types(void *rr1, void *rr2) +{ + knot_rrset_t *rrset1 = (knot_rrset_t *)rr1; + knot_rrset_t *rrset2 = (knot_rrset_t *)rr2; + return ((rrset1->type > rrset2->type) ? 1 : + (rrset1->type == rrset2->type) ? 0 : -1); +} + +/*----------------------------------------------------------------------------*/ + +static int knot_node_zone_gen_is_new(const knot_node_t *node) +{ + assert(node->zone != NULL); + knot_zone_contents_t *cont = rcu_dereference(node->zone->contents); + assert(cont != NULL); + return knot_zone_contents_gen_is_new(cont); +} + +/*----------------------------------------------------------------------------*/ + +static int knot_node_zone_gen_is_old(const knot_node_t *node) +{ + assert(node->zone != NULL); + knot_zone_contents_t *cont = rcu_dereference(node->zone->contents); + assert(cont != NULL); + return knot_zone_contents_gen_is_old(cont); +} + +/*----------------------------------------------------------------------------*/ +/* API functions */ +/*----------------------------------------------------------------------------*/ + +knot_node_t *knot_node_new(knot_dname_t *owner, knot_node_t *parent, + uint8_t flags) +{ + knot_node_t *ret = (knot_node_t *)calloc(1, sizeof(knot_node_t)); + if (ret == NULL) { + ERR_ALLOC_FAILED; + return NULL; + } + + /* Store reference to owner. */ + knot_dname_retain(owner); + ret->owner = owner; + knot_node_set_parent(ret, parent); + ret->rrset_tree = gen_tree_new(compare_rrset_types); + ret->flags = flags; + + assert(ret->children == 0); + + return ret; +} + +/*----------------------------------------------------------------------------*/ + +int knot_node_add_rrset(knot_node_t *node, knot_rrset_t *rrset, + int merge) +{ + int ret = 0; + + if ((ret = (gen_tree_add(node->rrset_tree, rrset, + (merge) ? knot_rrset_merge : NULL))) < 0) { + dbg_node("Failed to add rrset to node->rrset_tree.\n"); + return KNOT_ERROR; + } + + if (ret >= 0) { + node->rrset_count += (ret > 0 ? 0 : 1); + return ret; + } else { + return KNOT_ERROR; + } +} + +/*----------------------------------------------------------------------------*/ + +const knot_rrset_t *knot_node_rrset(const knot_node_t *node, + uint16_t type) +{ + assert(node != NULL); + assert(node->rrset_tree != NULL); + knot_rrset_t rrset; + rrset.type = type; + return (const knot_rrset_t *)gen_tree_find(node->rrset_tree, &rrset); +} + +/*----------------------------------------------------------------------------*/ + +knot_rrset_t *knot_node_get_rrset(knot_node_t *node, uint16_t type) +{ + knot_rrset_t rrset; + rrset.type = type; + return (knot_rrset_t *)gen_tree_find(node->rrset_tree, &rrset); +} + +/*----------------------------------------------------------------------------*/ + +knot_rrset_t *knot_node_remove_rrset(knot_node_t *node, uint16_t type) +{ + knot_rrset_t dummy_rrset; + dummy_rrset.type = type; + knot_rrset_t *rrset = + (knot_rrset_t *)gen_tree_find(node->rrset_tree, &dummy_rrset); + if (rrset != NULL) { + gen_tree_remove(node->rrset_tree, rrset); + node->rrset_count--; + } + return rrset; +} + +/*----------------------------------------------------------------------------*/ + +void knot_node_remove_all_rrsets(knot_node_t *node) +{ + // remove RRSets but do not delete them + gen_tree_clear(node->rrset_tree); + node->rrset_count = 0; + +} + +/*----------------------------------------------------------------------------*/ + +short knot_node_rrset_count(const knot_node_t *node) +{ + return node->rrset_count; +} + +/*----------------------------------------------------------------------------*/ + +struct knot_node_save_rrset_arg { + knot_rrset_t **array; + size_t count; +}; + +static void save_rrset_to_array(void *node, void *data) +{ + knot_rrset_t *rrset = (knot_rrset_t *)node; + struct knot_node_save_rrset_arg *args = + (struct knot_node_save_rrset_arg *)data; + args->array[args->count++] = rrset; +} + +knot_rrset_t **knot_node_get_rrsets(const knot_node_t *node) +{ +// knot_node_dump(node, 1); + if (node->rrset_count == 0) { + return NULL; + } + knot_rrset_t **rrsets = (knot_rrset_t **)malloc( + node->rrset_count * sizeof(knot_rrset_t *)); + CHECK_ALLOC_LOG(rrsets, NULL); + struct knot_node_save_rrset_arg args; + args.array = rrsets; + args.count = 0; + + gen_tree_apply_inorder(node->rrset_tree, save_rrset_to_array, + &args); + + assert(args.count == node->rrset_count); + + return rrsets; +} + +/*----------------------------------------------------------------------------*/ + +const knot_rrset_t **knot_node_rrsets(const knot_node_t *node) +{ + //knot_node_dump((knot_node_t *)node, (void*)1); + if (node->rrset_count == 0) { + return NULL; + } + + knot_rrset_t **rrsets = (knot_rrset_t **)malloc( + node->rrset_count * sizeof(knot_rrset_t *)); + CHECK_ALLOC_LOG(rrsets, NULL); + struct knot_node_save_rrset_arg args; + args.array = rrsets; + args.count = 0; + + gen_tree_apply_inorder(node->rrset_tree, save_rrset_to_array, + &args); + + assert(args.count == node->rrset_count); + assert(args.count); + + return (const knot_rrset_t **)rrsets; + +} + +/*----------------------------------------------------------------------------*/ + +const knot_node_t *knot_node_parent(const knot_node_t *node, + int check_version) +{ +// assert(!check_version +// || (node->zone != NULL && node->zone->contents != NULL)); + + knot_node_t *parent = node->parent; + + if (check_version && node->zone != NULL) { + int new_gen = knot_node_zone_gen_is_new(node); +// short ver = knot_node_zone_generation(node); + + /*! \todo Remove, this will not be true during the reference + * fixing. + */ +// assert(new_gen || parent == NULL +// || !knot_node_is_new(parent)); + + if (new_gen && parent != NULL) { + // we want the new node + assert(node->parent->new_node != NULL); + parent = parent->new_node; + } + } + + return parent; +} + +/*----------------------------------------------------------------------------*/ + +void knot_node_set_parent(knot_node_t *node, knot_node_t *parent) +{ + // decrease number of children of previous parent + if (node->parent != NULL) { + --parent->children; + } + // set the parent + node->parent = parent; + + // increase the count of children of the new parent + if (parent != NULL) { + ++parent->children; + } +} + +/*----------------------------------------------------------------------------*/ + +unsigned int knot_node_children(const knot_node_t *node) +{ + return node->children; +} + +/*----------------------------------------------------------------------------*/ + +const knot_node_t *knot_node_previous(const knot_node_t *node, + int check_version) +{ + return knot_node_get_previous(node, check_version); +} + +/*----------------------------------------------------------------------------*/ + +knot_node_t *knot_node_get_previous(const knot_node_t *node, + int check_version) +{ + assert(!check_version + || (node->zone != NULL && node->zone->contents != NULL)); + + knot_node_t *prev = node->prev; + + if (check_version && prev != NULL) { + int new_gen = knot_node_zone_gen_is_new(node); + int old_gen = knot_node_zone_gen_is_old(node); +// short ver = knot_node_zone_generation(node); + + if (old_gen) { // we want old node + while (knot_node_is_new(prev)) { + prev = prev->prev; + } + assert(!knot_node_is_new(prev)); + } else if (new_gen) { // we want new node + while (knot_node_is_old(prev)) { + if (prev->new_node) { + prev = prev->new_node; + } else { + prev = prev; + } + } + assert(knot_node_is_new(prev)); + } + } + + return prev; +} + +/*----------------------------------------------------------------------------*/ + +void knot_node_set_previous(knot_node_t *node, knot_node_t *prev) +{ + node->prev = prev; + if (prev != NULL) { + // set the prev pointer of the next node to the given node + if (prev->next != NULL) { + assert(prev->next->prev == prev); + prev->next->prev = node; + } + node->next = prev->next; + prev->next = node; + } +} + +/*----------------------------------------------------------------------------*/ + +const knot_node_t *knot_node_nsec3_node(const knot_node_t *node, + int check_version) +{ + knot_node_t *nsec3_node = node->nsec3_node; + if (nsec3_node == NULL) { + return NULL; + } + + if (check_version) { + int new_gen = knot_node_zone_gen_is_new(node); + int old_gen = knot_node_zone_gen_is_old(node); +// short ver = knot_node_zone_generation(node); + assert(new_gen || !knot_node_is_new(nsec3_node)); + if (old_gen && knot_node_is_new(nsec3_node)) { + return NULL; + } else if (new_gen && knot_node_is_old(nsec3_node)) { + nsec3_node = nsec3_node->new_node; + } + } + + return nsec3_node; +} + +/*----------------------------------------------------------------------------*/ + +void knot_node_set_nsec3_node(knot_node_t *node, knot_node_t *nsec3_node) +{ + node->nsec3_node = nsec3_node; + if (nsec3_node != NULL) { + nsec3_node->nsec3_referer = node; + } +} + +/*----------------------------------------------------------------------------*/ + +const knot_dname_t *knot_node_owner(const knot_node_t *node) +{ + return node->owner; +} + +/*----------------------------------------------------------------------------*/ + +knot_dname_t *knot_node_get_owner(const knot_node_t *node) +{ + return node->owner; +} + +/*----------------------------------------------------------------------------*/ + +void knot_node_set_owner(knot_node_t *node, knot_dname_t* owner) +{ + if (node) { + /* Retain new owner and release old owner. */ + knot_dname_retain(owner); + knot_dname_release(node->owner); + node->owner = owner; + } +} + +/*----------------------------------------------------------------------------*/ + +const knot_node_t *knot_node_wildcard_child(const knot_node_t *node, + int check_version) +{ + knot_node_t *w = node->wildcard_child; + + if (check_version && w != 0) { + int new_gen = knot_node_zone_gen_is_new(node); + int old_gen = knot_node_zone_gen_is_old(node); +// short ver = knot_node_zone_generation(node); + + if (old_gen && knot_node_is_new(w)) { + return NULL; + } else if (new_gen && knot_node_is_old(w)) { + assert(w->new_node != NULL); + w = w->new_node; + } + } + + return w; +} + +/*----------------------------------------------------------------------------*/ + +void knot_node_set_wildcard_child(knot_node_t *node, + knot_node_t *wildcard_child) +{ + node->wildcard_child = wildcard_child; +// assert(wildcard_child->parent == node); +} + +/*----------------------------------------------------------------------------*/ + +const knot_node_t *knot_node_current(const knot_node_t *node) +{ + if (node == NULL || node->zone == NULL + || knot_zone_contents(node->zone) == NULL) { + return node; + } + + int new_gen = knot_node_zone_gen_is_new(node); + int old_gen = knot_node_zone_gen_is_old(node); +// short ver = knot_node_zone_generation(node); + + if (old_gen && knot_node_is_new(node)) { + return NULL; + } else if (new_gen && knot_node_is_old(node)) { + assert(node->new_node != NULL); + return node->new_node; + } + return node; +} + +/*----------------------------------------------------------------------------*/ + +knot_node_t *knot_node_get_current(knot_node_t *node) +{ + if (node == NULL || node->zone == NULL + || knot_zone_contents(node->zone) == NULL) { + return node; + } + + int new_gen = knot_node_zone_gen_is_new(node); + int old_gen = knot_node_zone_gen_is_old(node); +// short ver = knot_node_zone_generation(node); + + if (old_gen && knot_node_is_new(node)) { + return NULL; + } else if (new_gen && knot_node_is_old(node)) { + assert(node->new_node != NULL); + return node->new_node; + } + + assert((old_gen && knot_node_is_old(node)) + || (new_gen && knot_node_is_new(node)) + || (!old_gen && !new_gen)); + + return node; +} + +/*----------------------------------------------------------------------------*/ + +const knot_node_t *knot_node_new_node(const knot_node_t *node) +{ + return node->new_node; +} + +/*----------------------------------------------------------------------------*/ + +knot_node_t *knot_node_get_new_node(const knot_node_t *node) +{ + return node->new_node; +} + +/*----------------------------------------------------------------------------*/ + +void knot_node_set_new_node(knot_node_t *node, + knot_node_t *new_node) +{ + node->new_node = new_node; +} + +/*----------------------------------------------------------------------------*/ + +void knot_node_set_zone(knot_node_t *node, knot_zone_t *zone) +{ + node->zone = zone; +} + +/*----------------------------------------------------------------------------*/ + +void knot_node_update_ref(knot_node_t **ref) +{ + if (*ref != NULL && knot_node_is_old(*ref)) { + *ref = (*ref)->new_node; + } +} + +/*----------------------------------------------------------------------------*/ + +void knot_node_update_refs(knot_node_t *node) +{ + /* CLEANUP */ + /* OMG! */ + // reference to previous node + knot_node_update_ref(&node->prev); +// if (node->prev && knot_node_is_old(node->prev)) { +// assert(node->prev->new_node != NULL); +// node->prev = node->prev->new_node; +// } + + // reference to next node + knot_node_update_ref(&node->next); +// if (node->next && knot_node_is_old(node->next)) { +// assert(node->next->new_node != NULL); +// node->next = node->next->new_node; +// } + + // reference to parent +// if (node->parent && knot_node_is_old(node->parent)) { +// assert(node->parent->new_node != NULL); +// // do not use the API function to set parent, so that children count +// // is not changed +// //knot_node_set_parent(node, node->parent->new_node); +// node->parent = node->parent->new_node; +// } + knot_node_update_ref(&node->parent); + + // reference to wildcard child + knot_node_update_ref(&node->wildcard_child); +// if (node->wildcard_child && knot_node_is_old(node->wildcard_child)) { +// assert(node->wildcard_child->new_node != NULL); +// node->wildcard_child = node->wildcard_child->new_node; +// } + + // reference to NSEC3 node + knot_node_update_ref(&node->nsec3_node); +// if (node->nsec3_node && knot_node_is_old(node->nsec3_node)) { +// assert(node->nsec3_node->new_node != NULL); +// node->nsec3_node = node->nsec3_node->new_node; +// } + + // reference to NSEC3 referrer + knot_node_update_ref(&node->nsec3_referer); +// if (node->nsec3_referer && knot_node_is_old(node->nsec3_referer)) { +// assert(node->nsec3_referer->new_node != NULL); +// node->nsec3_referer = node->nsec3_referer->new_node; +// } +} + +/*----------------------------------------------------------------------------*/ + +void knot_node_set_deleg_point(knot_node_t *node) +{ + knot_node_flags_set_deleg(&node->flags); +} + +/*----------------------------------------------------------------------------*/ + +int knot_node_is_deleg_point(const knot_node_t *node) +{ + return knot_node_flags_get_deleg(node->flags); +} + +/*----------------------------------------------------------------------------*/ + +void knot_node_set_non_auth(knot_node_t *node) +{ + knot_node_flags_set_nonauth(&node->flags); +} + +/*----------------------------------------------------------------------------*/ + +int knot_node_is_non_auth(const knot_node_t *node) +{ + return knot_node_flags_get_nonauth(node->flags); +} + +/*----------------------------------------------------------------------------*/ + +int knot_node_is_auth(const knot_node_t *node) +{ + return (node->flags == 0); +} + +/*----------------------------------------------------------------------------*/ + +int knot_node_is_new(const knot_node_t *node) +{ + return knot_node_flags_get_new(node->flags); +} + +/*----------------------------------------------------------------------------*/ + +int knot_node_is_old(const knot_node_t *node) +{ + return knot_node_flags_get_old(node->flags); +} + +/*----------------------------------------------------------------------------*/ + +void knot_node_set_new(knot_node_t *node) +{ + knot_node_flags_set_new(&node->flags); +} + +/*----------------------------------------------------------------------------*/ + +void knot_node_set_old(knot_node_t *node) +{ + knot_node_flags_set_old(&node->flags); +} + +/*----------------------------------------------------------------------------*/ + +void knot_node_clear_new(knot_node_t *node) +{ + knot_node_flags_clear_new(&node->flags); +} + +/*----------------------------------------------------------------------------*/ + +void knot_node_clear_old(knot_node_t *node) +{ + knot_node_flags_clear_old(&node->flags); +} + +/*----------------------------------------------------------------------------*/ + +static void knot_node_free_rrsets_from_tree(void *item, void *data) +{ + if (item == NULL) { + return; + } + + knot_rrset_t *rrset = (knot_rrset_t *)(item); + knot_rrset_deep_free(&rrset, 0, 1, *((int *)data)); +} + +/*----------------------------------------------------------------------------*/ + +void knot_node_free_rrsets(knot_node_t *node, int free_rdata_dnames) +{ + /* CLEANUP */ +// knot_rrset_t **rrsets = knot_node_get_rrsets(node); +// for (int i = 0; i < node->rrset_count; i++) { +// knot_rrset_deep_free(&(rrsets[i]), 0, 1, free_rdata_dnames); +// } + +// free(rrsets); + + char *name = knot_dname_to_str(node->owner); + free(name); + + gen_tree_destroy(&node->rrset_tree, knot_node_free_rrsets_from_tree, + (void *)&free_rdata_dnames); +} + +/*----------------------------------------------------------------------------*/ + +void knot_node_free(knot_node_t **node, int free_owner, int fix_refs) +{ + if (node == NULL || *node == NULL) { + return; + } + + dbg_node("Freeing node.\n"); + if ((*node)->rrset_tree != NULL) { + dbg_node("Freeing RRSets.\n"); + gen_tree_destroy(&(*node)->rrset_tree, NULL, NULL); + } + + /*! \todo Always release owner? */ + //if (free_owner) { + dbg_node("Releasing owner.\n"); + knot_dname_release((*node)->owner); + //} + + // check nodes referencing this node and fix the references + + if (fix_refs) { + // previous node + dbg_node("Checking previous.\n"); + if ((*node)->prev && (*node)->prev->next == (*node)) { + (*node)->prev->next = (*node)->next; + } + + dbg_node("Checking next.\n"); + if ((*node)->next && (*node)->next->prev == (*node)) { + (*node)->next->prev = (*node)->prev; + } + + // NSEC3 node + dbg_node("Checking NSEC3.\n"); + if ((*node)->nsec3_node + && (*node)->nsec3_node->nsec3_referer == (*node)) { + (*node)->nsec3_node->nsec3_referer = NULL; + } + + dbg_node("Checking NSEC3 ref.\n"); + if ((*node)->nsec3_referer + && (*node)->nsec3_referer->nsec3_node == (*node)) { + (*node)->nsec3_referer->nsec3_node = NULL; + } + + // wildcard child node + dbg_node("Checking parent's wildcard child.\n"); + if ((*node)->parent + && (*node)->parent->wildcard_child == (*node)) { + (*node)->parent->wildcard_child = NULL; + } + + // fix parent's children count + if ((*node)->parent) { + --(*node)->parent->children; + } + } + + free(*node); + *node = NULL; + + dbg_node("Done.\n"); +} + +/*----------------------------------------------------------------------------*/ + +int knot_node_compare(knot_node_t *node1, knot_node_t *node2) +{ + return knot_dname_compare(node1->owner, node2->owner); +} + +/*----------------------------------------------------------------------------*/ + +int knot_node_shallow_copy(const knot_node_t *from, knot_node_t **to) +{ + // create new node + *to = knot_node_new(from->owner, from->parent, from->flags); + if (*to == NULL) { + return KNOT_ENOMEM; + } + + /* Free old rrset_tree, as it will be replaced by shallow copy. */ + gen_tree_destroy(&(*to)->rrset_tree, 0, 0); + + // copy references + // do not use the API function to set parent, so that children count + // is not changed + memcpy(*to, from, sizeof(knot_node_t)); + + // copy RRSets + // copy the skip list with the old references + /* CLEANUP */ + (*to)->rrset_tree = gen_tree_shallow_copy(from->rrset_tree); +// assert((*to)->rrset_tree != from->rrset_tree); +// (*to)->rrsets = skip_copy_list(from->rrsets); + if ((*to)->rrset_tree == NULL) { + free(*to); + *to = NULL; + return KNOT_ENOMEM; + } + + return KNOT_EOK; +} diff --git a/src/libknot/zone/node.h b/src/libknot/zone/node.h new file mode 100644 index 0000000..fcb612d --- /dev/null +++ b/src/libknot/zone/node.h @@ -0,0 +1,436 @@ +/*! + * \file node.h + * + * \author Lubos Slovak <lubos.slovak@nic.cz> + * + * \brief Structure representing one node in domain name tree and API for + * manipulating it. + * + * \addtogroup libknot + * @{ + */ +/* Copyright (C) 2011 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 <http://www.gnu.org/licenses/>. + */ + +#ifndef _KNOT_NODE_H_ +#define _KNOT_NODE_H_ + +#include "dname.h" +#include "common/skip-list.h" +#include "rrset.h" +#include "common/tree.h" +#include "common/general-tree.h" + +struct knot_zone; + +/*----------------------------------------------------------------------------*/ +/*! + * \brief Structure representing one node in a domain name tree, i.e. one domain + * name in a zone. + * + * RRSets are ordered by type and stored in a skip-list to allow fast lookup. + */ +struct knot_node { + knot_dname_t *owner; /*!< Domain name being the owner of this node. */ + struct knot_node *parent; /*!< Parent node in the name hierarchy. */ + + /*! \brief Type-ordered list of RRSets belonging to this node. */ + general_tree_t *rrset_tree; + + unsigned short rrset_count; /*!< Number of RRSets stored in the node. */ + + /*! \brief Wildcard node being the direct descendant of this node. */ + struct knot_node *wildcard_child; + + /*! + * \brief Previous node in canonical order. + * + * Only authoritative nodes or delegation points are referenced by this, + * as only they may contain NSEC records needed for authenticating + * negative answers. + */ + struct knot_node *prev; + + struct knot_node *next; + + /*! + * \brief NSEC3 node corresponding to this node. + * + * Such NSEC3 node has owner in form of the hashed domain name of this + * node prepended as a single label to the zone name. + */ + struct knot_node *nsec3_node; + + struct knot_node *nsec3_referer; + + /*! + * \brief Various flags. + * + * Currently only two: + * 0x01 - node is a delegation point + * 0x02 - node is non-authoritative (under a delegation point) + * 0x80 - node is old and will be removed (during update) + * 0x40 - node is new, should not be used while zone is old + */ + uint8_t flags; + + struct knot_node *new_node; + + unsigned int children; + + /*! + * \brief Generation of node to be used. + * + * If set to 0, the old node will be used. Otherwise new nodes will + * be used. This applies when getting some referenced node. + + */ +// short **generation; + + struct knot_zone *zone; +}; + +typedef struct knot_node knot_node_t; + +/*----------------------------------------------------------------------------*/ +/*! \brief Flags used to mark nodes with some property. */ +typedef enum { + /*! \brief Node is a delegation point (i.e. marking a zone cut). */ + KNOT_NODE_FLAGS_DELEG = (uint8_t)0x01, + /*! \brief Node is not authoritative (i.e. below a zone cut). */ + KNOT_NODE_FLAGS_NONAUTH = (uint8_t)0x02, + /*! \brief Node is old and will be removed (during update). */ + KNOT_NODE_FLAGS_OLD = (uint8_t)0x80, + /*! \brief Node is new and should not be used while zoen is old. */ + KNOT_NODE_FLAGS_NEW = (uint8_t)0x40 +} knot_node_flags_t; + +/*----------------------------------------------------------------------------*/ +/*! + * \brief Creates and initializes new node structure. + * + * \todo Owner reference counter will be increased. + * + * \param owner Owner of the created node. + * \param parent Parent of the created node. + * \param flags Document me. + * + * \todo Document missing parameters. + * + * \return Newly created node or NULL if an error occured. + */ +knot_node_t *knot_node_new(knot_dname_t *owner, knot_node_t *parent, + uint8_t flags); + +/*! + * \brief Adds an RRSet to the node. + * + * \param node Node to add the RRSet to. + * \param rrset RRSet to add. + * + * \retval KNOT_EOK on success. + * \retval KNOT_ERROR if the RRSet could not be inserted. + */ +int knot_node_add_rrset(knot_node_t *node, knot_rrset_t *rrset, + int merge); + +/*! + * \brief Returns the RRSet of the given type from the node. + * + * \param node Node to get the RRSet from. + * \param type Type of the RRSet to retrieve. + * + * \return RRSet from node \a node having type \a type, or NULL if no such + * RRSet exists in this node. + */ +const knot_rrset_t *knot_node_rrset(const knot_node_t *node, + uint16_t type); + +/*! + * \brief Returns the RRSet of the given type from the node (non-const version). + * + * \param node Node to get the RRSet from. + * \param type Type of the RRSet to retrieve. + * + * \return RRSet from node \a node having type \a type, or NULL if no such + * RRSet exists in this node. + */ +knot_rrset_t *knot_node_get_rrset(knot_node_t *node, uint16_t type); + +knot_rrset_t *knot_node_remove_rrset(knot_node_t *node, uint16_t type); + +void knot_node_remove_all_rrsets(knot_node_t *node); + +/*! + * \brief Returns number of RRSets in the node. + * + * \param node Node to get the RRSet count from. + * + * \return Number of RRSets in \a node. + */ +short knot_node_rrset_count(const knot_node_t *node); + +/*! + * \brief Returns all RRSets from the node. + * + * \param node Node to get the RRSets from. + * + * \return Newly allocated array of RRSets or NULL if an error occured. + */ +knot_rrset_t **knot_node_get_rrsets(const knot_node_t *node); + +/*! + * \brief Returns all RRSets from the node. + * + * \note This function is identical to knot_node_get_rrsets(), only it returns + * non-modifiable data. + * + * \param node Node to get the RRSets from. + * + * \return Newly allocated array of RRSets or NULL if an error occured. + */ +const knot_rrset_t **knot_node_rrsets(const knot_node_t *node); + +/*! + * \brief Returns the parent of the node. + * + * \param node Node to get the parent of. + * + * \return Parent node of the given node or NULL if no parent has been set (e.g. + * node in a zone apex has no parent). + */ +const knot_node_t *knot_node_parent(const knot_node_t *node, + int check_version); + +/*! + * \brief Sets the parent of the node. + * + * \param node Node to set the parent of. + * \param parent Parent to set to the node. + */ +void knot_node_set_parent(knot_node_t *node, knot_node_t *parent); + +unsigned int knot_node_children(const knot_node_t *node); + +/*! + * \brief Returns the previous authoritative node or delegation point in + * canonical order or the first node in zone. + * + * \param node Node to get the previous node of. + * + * \return Previous authoritative node or delegation point in canonical order or + * the first node in zone if \a node is the last node in zone. + * \retval NULL if previous node is not set. + */ +const knot_node_t *knot_node_previous(const knot_node_t *node, + int check_version); + +/*! + * \brief Returns the previous authoritative node or delegation point in + * canonical order or the first node in zone. + * + * \note This function is identical to knot_node_previous() except that it + * returns non-const node. + * + * \param node Node to get the previous node of. + * + * \return Previous authoritative node or delegation point in canonical order or + * the first node in zone if \a node is the last node in zone. + * \retval NULL if previous node is not set. + */ +knot_node_t *knot_node_get_previous(const knot_node_t *node, + int check_version); + +/*! + * \brief Sets the previous node of the given node. + * + * \param node Node to set the previous node to. + * \param prev Previous node to set. + */ +void knot_node_set_previous(knot_node_t *node, knot_node_t *prev); + +/*! + * \brief Returns the NSEC3 node corresponding to the given node. + * + * \param node Node to get the NSEC3 node for. + * + * \return NSEC3 node corresponding to \a node (i.e. node with owner name + * created by concatenating the hash of owner domain name of \a node + * and the name of the zone \a node belongs to). + * \retval NULL if the NSEC3 node is not set. + */ +const knot_node_t *knot_node_nsec3_node(const knot_node_t *node, + int check_version); + +/*! + * \brief Sets the corresponding NSEC3 node of the given node. + * + * \param node Node to set the NSEC3 node to. + * \param nsec3_node NSEC3 node to set. + */ +void knot_node_set_nsec3_node(knot_node_t *node, knot_node_t *nsec3_node); + +/*! + * \brief Returns the owner of the node. + * + * \param node Node to get the owner of. + * + * \return Owner of the given node. + */ +const knot_dname_t *knot_node_owner(const knot_node_t *node); + +/*! + * \todo Document me. + */ +knot_dname_t *knot_node_get_owner(const knot_node_t *node); + +/*! + * \brief Set node owner to specified dname. + * + * Previous owner will be replaced if exist. + * + * \param node Specified node. + * \param owner New owner dname. + */ +void knot_node_set_owner(knot_node_t *node, knot_dname_t* owner); + +/*! + * \brief Returns the wildcard child of the node. + * + * \param node Node to get the owner of. + * + * \return Wildcard child of the given node or NULL if it has none. + */ +const knot_node_t *knot_node_wildcard_child(const knot_node_t *node, + int check_version); + +/*! + * \brief Sets the wildcard child of the node. + * + * \param node Node to set the wildcard child of. + * \param wildcard_child Wildcard child of the node. + */ +void knot_node_set_wildcard_child(knot_node_t *node, + knot_node_t *wildcard_child); + +const knot_node_t *knot_node_current(const knot_node_t *node); + +knot_node_t *knot_node_get_current(knot_node_t *node); + +const knot_node_t *knot_node_new_node(const knot_node_t *node); + +knot_node_t *knot_node_get_new_node(const knot_node_t *node); + +void knot_node_set_new_node(knot_node_t *node, + knot_node_t *new_node); + +void knot_node_set_zone(knot_node_t *node, struct knot_zone *zone); + +void knot_node_update_ref(knot_node_t **ref); + +void knot_node_update_refs(knot_node_t *node); + +/*! + * \brief Mark the node as a delegation point. + * + * \param node Node to mark as a delegation point. + */ +void knot_node_set_deleg_point(knot_node_t *node); + +/*! + * \brief Checks if the node is a delegation point. + * + * \param node Node to check. + * + * \retval <> 0 if \a node is marked as delegation point. + * \retval 0 otherwise. + */ +int knot_node_is_deleg_point(const knot_node_t *node); + +/*! + * \brief Mark the node as non-authoritative. + * + * \param node Node to mark as non-authoritative. + */ +void knot_node_set_non_auth(knot_node_t *node); + +/*! + * \brief Checks if the node is non-authoritative. + * + * \param node Node to check. + * + * \retval <> 0 if \a node is marked as non-authoritative. + * \retval 0 otherwise. + */ +int knot_node_is_non_auth(const knot_node_t *node); + +int knot_node_is_auth(const knot_node_t *node); + +int knot_node_is_new(const knot_node_t *node); + +int knot_node_is_old(const knot_node_t *node); + +void knot_node_set_new(knot_node_t *node); + +void knot_node_set_old(knot_node_t *node); + +void knot_node_clear_new(knot_node_t *node); + +void knot_node_clear_old(knot_node_t *node); + +/*! + * \brief Destroys the RRSets within the node structure. + * + * \param node Node to be destroyed. + * \param free_rdata_dnames Set to <> 0 if you want to delete ALL domain names + * present in RDATA. Set to 0 otherwise. (See + * knot_rdata_deep_free().) + */ +void knot_node_free_rrsets(knot_node_t *node, int free_rdata_dnames); + +/*! + * \brief Destroys the node structure. + * + * Does not destroy the RRSets within the node. + * Also sets the given pointer to NULL. + * + * \param node Node to be destroyed. + * \param free_owner Set to 0 if you do not want the owner domain name to be + * destroyed also. Set to <> 0 otherwise. + * \param fix_refs + * + * \todo Document missing parameters. + */ +void knot_node_free(knot_node_t **node, int free_owner, int fix_refs); + +/*! + * \brief Compares two nodes according to their owner. + * + * \param node1 First node. + * \param node2 Second node. + * + * \retval < 0 if \a node1 goes before \a node2 according to canonical order + * of their owner names. + * \retval 0 if they are equal. + * \retval > 0 if \a node1 goes after \a node2. + */ +int knot_node_compare(knot_node_t *node1, knot_node_t *node2); + +int knot_node_shallow_copy(const knot_node_t *from, knot_node_t **to); + +#endif /* _KNOT_NODE_H_ */ + +/*! @} */ diff --git a/src/libknot/zone/zone-contents.c b/src/libknot/zone/zone-contents.c new file mode 100644 index 0000000..d550728 --- /dev/null +++ b/src/libknot/zone/zone-contents.c @@ -0,0 +1,2396 @@ +/* Copyright (C) 2011 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 <http://www.gnu.org/licenses/>. + */ + +#include <assert.h> + +#include "zone/zone-contents.h" +#include "util/error.h" +#include "util/debug.h" +#include "common/base32hex.h" +#include "consts.h" + +/*----------------------------------------------------------------------------*/ +/* Non-API functions */ +/*----------------------------------------------------------------------------*/ + +typedef struct { + void (*func)(knot_node_t *, void *); + void *data; +} knot_zone_tree_func_t; + +typedef struct { + knot_node_t *first_node; + knot_zone_contents_t *zone; + knot_node_t *previous_node; + int check_ver; +} knot_zone_adjust_arg_t; + +/*----------------------------------------------------------------------------*/ + +static void knot_zone_tree_apply(knot_zone_tree_node_t *node, + void *data) +{ + if (node == NULL || data == NULL) { + return; + } + + knot_zone_tree_func_t *f = (knot_zone_tree_func_t *)data; + f->func(node->node, f->data); +} + +/*----------------------------------------------------------------------------*/ + +/*! + * \brief Checks if the given node can be inserted into the given zone. + * + * Checks if both the arguments are non-NULL and if the owner of the node + * belongs to the zone (i.e. is a subdomain of the zone apex). + * + * \param zone Zone to which the node is going to be inserted. + * \param node Node to check. + * + * \retval KNOT_EOK if both arguments are non-NULL and the node belongs to the + * zone. + * \retval KNOT_EBADARG if either of the arguments is NULL. + * \retval KNOT_EBADZONE if the node does not belong to the zone. + */ +static int knot_zone_contents_check_node( + const knot_zone_contents_t *contents, const knot_node_t *node) +{ + if (contents == NULL || node == NULL) { + return KNOT_EBADARG; + } + + // assert or just check?? + assert(contents->apex != NULL); + + if (!knot_dname_is_subdomain(node->owner, + knot_node_owner(contents->apex))) { +dbg_zone_exec( + char *node_owner = knot_dname_to_str(knot_node_owner(node)); + char *apex_owner = knot_dname_to_str(contents->apex->owner); + dbg_zone("zone: Trying to insert foreign node to a " + "zone. Node owner: %s, zone apex: %s\n", + node_owner, apex_owner); + free(node_owner); + free(apex_owner); +); + return KNOT_EBADZONE; + } + return KNOT_EOK; +} + +/*----------------------------------------------------------------------------*/ +/*! + * \brief Destroys all RRSets in a node. + * + * This function is designed to be used in the tree-iterating functions. + * + * \param node Node to destroy RRSets from. + * \param data Unused parameter. + */ +static void knot_zone_contents_destroy_node_rrsets_from_tree( + knot_zone_tree_node_t *tnode, void *data) +{ + assert(tnode != NULL); + assert(tnode->node != NULL); + + int free_rdata_dnames = (int)((intptr_t)data); + knot_node_free_rrsets(tnode->node, free_rdata_dnames); +} + +/*----------------------------------------------------------------------------*/ +/*! + * \brief Destroys node owner. + * + * This function is designed to be used in the tree-iterating functions. + * + * \param node Node to destroy the owner of. + * \param data Unused parameter. + */ +static void knot_zone_contents_destroy_node_owner_from_tree( + knot_zone_tree_node_t *tnode, void *data) +{ + assert(tnode != NULL); + assert(tnode->node != NULL); + + UNUSED(data); + /*!< \todo change completely! */ + knot_node_free(&tnode->node, 0, 0); +} + +/*! + * \brief Finds and sets wildcard child for given node's owner. + * + * \param zone Current zone. + * \param node Node to be used. + */ +static void find_and_set_wildcard_child(knot_zone_contents_t *zone, + knot_node_t *node) +{ + knot_dname_t *chopped = knot_dname_left_chop(node->owner); + assert(chopped); + knot_node_t *wildcard_parent; + wildcard_parent = + knot_zone_contents_get_node(zone, chopped); + + knot_dname_free(&chopped); + + assert(wildcard_parent); /* it *has* to be there */ + + knot_node_set_wildcard_child(wildcard_parent, node); +} + +/*----------------------------------------------------------------------------*/ +/*! + * \brief Adjusts one RDATA item by replacing domain name by one present in the + * zone. + * + * This function tries to find the domain name in the zone. If the name is not + * in the zone, it does nothing. If it is there, it destroys the domain name + * stored in the RDATA item and replaces it by pointer to the domain name from + * the zone. + * + * \warning Call this function only with RDATA items which store domain names, + * otherwise the behaviour is undefined. + * + * \param rdata RDATA where the item is located. + * \param zone Zone to which the RDATA belongs. + * \param pos Position of the RDATA item in the RDATA. + */ +static void knot_zone_contents_adjust_rdata_item(knot_rdata_t *rdata, + knot_zone_contents_t *zone, + knot_node_t *node, + int pos) +{ + return; + const knot_rdata_item_t *dname_item + = knot_rdata_item(rdata, pos); + + assert(dname_item); + + if (dname_item != NULL) { + knot_dname_t *dname = dname_item->dname; + const knot_node_t *n = NULL; + const knot_node_t *closest_encloser = NULL; + const knot_node_t *prev = NULL; + + if (knot_dname_is_wildcard(dname)) { + find_and_set_wildcard_child(zone, node); + } + + int ret = knot_zone_contents_find_dname(zone, dname, &n, + &closest_encloser, &prev); + + // n = knot_zone_find_node(zone, dname); + + if (ret == KNOT_EBADARG || ret == KNOT_EBADZONE) { + // TODO: do some cleanup if needed + return; + } + + assert(ret != KNOT_ZONE_NAME_FOUND + || n == closest_encloser); + + if (ret != KNOT_ZONE_NAME_FOUND + && (closest_encloser != NULL)) { + dbg_zone("Saving closest encloser to RDATA.\n"); + // save pointer to the closest encloser + knot_rdata_item_t *item = + knot_rdata_get_item(rdata, pos); + assert(item->dname != NULL); + assert(item->dname->node == NULL); + //skip_insert(list, (void *)item->dname, + // (void *)closest_encloser->owner, NULL); + item->dname->node = closest_encloser->owner->node; + } + } +} + +/*----------------------------------------------------------------------------*/ +/*! + * \brief Adjusts all RDATA in the given RRSet by replacing domain names by ones + * present in the zone. + * + * This function selects the RDATA items containing a domain name (according to + * RR type descriptor of the RRSet's type and adjusts the item using + * knot_zone_adjust_rdata_item(). + * + * \param rrset RRSet to adjust RDATA in. + * \param zone Zone to which the RRSet belongs. + */ +static void knot_zone_contents_adjust_rdata_in_rrset(knot_rrset_t *rrset, + knot_zone_contents_t *zone, + knot_node_t *node) +{ + uint16_t type = knot_rrset_type(rrset); + + knot_rrtype_descriptor_t *desc = + knot_rrtype_descriptor_by_type(type); + assert(desc); + + knot_rdata_t *rdata_first = knot_rrset_get_rdata(rrset); + knot_rdata_t *rdata = rdata_first; + + if (rdata == NULL) { + return; + } + + while (rdata->next != rdata_first) { + for (int i = 0; i < rdata->count; ++i) { + if (desc->wireformat[i] + == KNOT_RDATA_WF_COMPRESSED_DNAME + || desc->wireformat[i] + == KNOT_RDATA_WF_UNCOMPRESSED_DNAME + || desc->wireformat[i] + == KNOT_RDATA_WF_LITERAL_DNAME) { + dbg_zone("Adjusting domain name at " + "position %d of RDATA of record with owner " + "%s and type %s.\n", + i, rrset->owner->name, + knot_rrtype_to_string(type)); + + knot_zone_contents_adjust_rdata_item(rdata, + zone, + node, + i); + } + } + rdata = rdata->next; + } + + for (int i = 0; i < rdata->count; ++i) { + if (desc->wireformat[i] + == KNOT_RDATA_WF_COMPRESSED_DNAME + || desc->wireformat[i] + == KNOT_RDATA_WF_UNCOMPRESSED_DNAME + || desc->wireformat[i] + == KNOT_RDATA_WF_LITERAL_DNAME) { + dbg_zone("Adjusting domain name at " + "position %d of RDATA of record with owner " + "%s and type %s.\n", + i, rrset->owner->name, + knot_rrtype_to_string(type)); + + knot_zone_contents_adjust_rdata_item(rdata, zone, + node, i); + } + } + +} + +/*----------------------------------------------------------------------------*/ +/*! + * \brief Adjusts all RRSets in the given node by replacing domain names in + * RDATA by ones present in the zone. + * + * This function just calls knot_zone_adjust_rdata_in_rrset() for all RRSets + * in the node (including all RRSIG RRSets). + * + * \param node Zone node to adjust the RRSets in. + * \param zone Zone to which the node belongs. + */ +static void knot_zone_contents_adjust_rrsets(knot_node_t *node, + knot_zone_contents_t *zone) +{ + //return; + knot_rrset_t **rrsets = knot_node_get_rrsets(node); + short count = knot_node_rrset_count(node); + + assert(count == 0 || rrsets != NULL); + + for (int r = 0; r < count; ++r) { + assert(rrsets[r] != NULL); + dbg_zone("Adjusting next RRSet.\n"); + knot_zone_contents_adjust_rdata_in_rrset(rrsets[r], zone, + node); + knot_rrset_t *rrsigs = rrsets[r]->rrsigs; + if (rrsigs != NULL) { + dbg_zone("Adjusting next RRSIGs.\n"); + knot_zone_contents_adjust_rdata_in_rrset(rrsigs, + zone, + node); + } + } + + free(rrsets); +} + +/*----------------------------------------------------------------------------*/ +/*! + * \brief Adjusts zone node for faster query processing. + * + * - Adjusts RRSets in the node (see knot_zone_adjust_rrsets()). + * - Marks the node as delegation point or non-authoritative (below a zone cut) + * if applicable. + * - Stores reference to corresponding NSEC3 node if applicable. + * + * \param node Zone node to adjust. + * \param zone Zone the node belongs to. + */ +static void knot_zone_contents_adjust_node(knot_node_t *node, + knot_zone_contents_t *zone, + int check_ver) +{ + +dbg_zone_exec( + char *name = knot_dname_to_str(node->owner); + dbg_zone("----- Adjusting node %s -----\n", name); + free(name); +); + + // adjust domain names in RDATA + knot_zone_contents_adjust_rrsets(node, zone); + +dbg_zone_exec( + if (knot_node_parent(node, 1)) { + char *name = knot_dname_to_str(knot_node_owner( + knot_node_parent(node, check_ver))); + dbg_zone("Parent: %s\n", name); + dbg_zone("Parent is delegation point: %s\n", + knot_node_is_deleg_point(knot_node_parent(node, check_ver)) + ? "yes" : "no"); + dbg_zone("Parent is non-authoritative: %s\n", + knot_node_is_non_auth(knot_node_parent(node, check_ver)) + ? "yes" : "no"); + free(name); + } else { + dbg_zone("No parent!\n"); + } +); + // delegation point / non-authoritative node + if (knot_node_parent(node, check_ver) + && (knot_node_is_deleg_point(knot_node_parent(node, check_ver)) + || knot_node_is_non_auth(knot_node_parent(node, check_ver)))) { + knot_node_set_non_auth(node); + } else if (knot_node_rrset(node, KNOT_RRTYPE_NS) != NULL + && node != zone->apex) { + knot_node_set_deleg_point(node); + } + + // authorative node? +// if (!knot_node_is_non_auth(node)) { + zone->node_count++; +// } + + // assure that owner has proper node + if (knot_dname_node(knot_node_owner(node), 0) == NULL) { + knot_dname_set_node(knot_node_get_owner(node), node); + knot_dname_set_node(knot_node_get_owner(node), node); + } + + // NSEC3 node (only if NSEC3 tree is not empty) + const knot_node_t *prev; + const knot_node_t *nsec3; + int match = knot_zone_contents_find_nsec3_for_name(zone, + knot_node_owner(node), + &nsec3, &prev, check_ver); + if (match != KNOT_ZONE_NAME_FOUND) { + nsec3 = NULL; + } + + knot_node_set_nsec3_node(node, (knot_node_t *)nsec3); + + dbg_zone("Set flags to the node: \n"); + dbg_zone("Delegation point: %s\n", + knot_node_is_deleg_point(node) ? "yes" : "no"); + dbg_zone("Non-authoritative: %s\n", + knot_node_is_non_auth(node) ? "yes" : "no"); +} + +/*----------------------------------------------------------------------------*/ +/*! + * \brief Adjusts zone node for faster query processing. + * + * This function is just a wrapper over knot_zone_adjust_node() to be used + * in tree-traversing functions. + * + * \param node Zone node to adjust. + * \param data Zone the node belongs to. + */ +static void knot_zone_contents_adjust_node_in_tree( + knot_zone_tree_node_t *tnode, void *data) +{ + assert(data != NULL); + assert(tnode != NULL); + assert(tnode->node != NULL); + + knot_zone_adjust_arg_t *args = (knot_zone_adjust_arg_t *)data; + knot_node_t *node = tnode->node; + knot_node_set_previous(node, args->previous_node); + args->previous_node = node; + if (args->first_node == NULL) { + args->first_node = node; + } + knot_zone_contents_t *zone = args->zone; + + knot_zone_contents_adjust_node(node, zone, args->check_ver); +} + +/*----------------------------------------------------------------------------*/ +/*! + * \brief Adjusts NSEC3 node for faster query processing. + * + * This function is just a wrapper over knot_zone_adjust_nsec3_node() to be + * used in tree-traversing functions. + * + * \param node Zone node to adjust. + * \param data Zone the node belongs to. + */ +static void knot_zone_contents_adjust_nsec3_node_in_tree( + knot_zone_tree_node_t *tnode, void *data) +{ + assert(data != NULL); + assert(tnode != NULL); + assert(tnode->node != NULL); + + knot_zone_adjust_arg_t *args = (knot_zone_adjust_arg_t *)data; + knot_node_t *node = tnode->node; + knot_node_set_previous(node, args->previous_node); + args->previous_node = node; + if (args->first_node == NULL) { + args->first_node = node; + } + + /* Not needed anymore. */ +// knot_zone_contents_t *zone = args->zone; +// knot_zone_contents_adjust_nsec3_node(node, zone, 1); +} + +/*----------------------------------------------------------------------------*/ +/*! + * \brief Creates a NSEC3 hashed name for the given domain name. + * + * \note The zone's NSEC3PARAM record must be parsed prior to calling this + * function (see knot_zone_load_nsec3param()). + * + * \param zone Zone from which to take the NSEC3 parameters. + * \param name Domain name to hash. + * \param nsec3_name Hashed name. + * + * \retval KNOT_EOK + * \retval KNOT_ENSEC3PAR + * \retval KNOT_ECRYPTO + * \retval KNOT_ERROR if an error occured while creating a new domain name + * from the hash or concatenating it with the zone name. + */ +static int knot_zone_contents_nsec3_name(const knot_zone_contents_t *zone, + const knot_dname_t *name, + knot_dname_t **nsec3_name) +{ + assert(nsec3_name != NULL); + + *nsec3_name = NULL; + + const knot_nsec3_params_t *nsec3_params = + knot_zone_contents_nsec3params(zone); + + if (nsec3_params == NULL) { +dbg_zone_exec( + char *n = knot_dname_to_str(zone->apex->owner); + dbg_zone("No NSEC3PARAM for zone %s.\n", n); + free(n); +); + return KNOT_ENSEC3PAR; + } + + uint8_t *hashed_name = NULL; + size_t hash_size = 0; + +dbg_zone_exec( + char *n = knot_dname_to_str(name); + dbg_zone("Hashing name %s.\n", n); + free(n); +); + + int res = knot_nsec3_sha1(nsec3_params, knot_dname_name(name), + knot_dname_size(name), &hashed_name, + &hash_size); + + if (res != 0) { + char *n = knot_dname_to_str(name); + dbg_zone("Error while hashing name %s.\n", n); + free(n); + return KNOT_ECRYPTO; + } + + dbg_zone("Hash: "); + dbg_zone_hex((char *)hashed_name, hash_size); + dbg_zone("\n"); + + char *name_b32 = NULL; + size_t size = base32hex_encode_alloc((char *)hashed_name, hash_size, + &name_b32); + + if (size == 0) { + char *n = knot_dname_to_str(name); + dbg_zone("Error while encoding hashed name %s to " + "base32.\n", n); + free(n); + if (name_b32 != NULL) { + free(name_b32); + } + return KNOT_ECRYPTO; + } + + assert(name_b32 != NULL); + free(hashed_name); + + dbg_zone("Base32-encoded hash: %s\n", name_b32); + + /* Will be returned to caller, make sure it is released after use. */ + *nsec3_name = knot_dname_new_from_str(name_b32, size, NULL); + + free(name_b32); + + if (*nsec3_name == NULL) { + dbg_zone("Error while creating domain name for hashed" + " name.\n"); + return KNOT_ERROR; + } + + assert(zone->apex->owner != NULL); + knot_dname_t *ret = knot_dname_cat(*nsec3_name, zone->apex->owner); + + if (ret == NULL) { + dbg_zone("Error while creating NSEC3 domain name for " + "hashed name.\n"); + knot_dname_release(*nsec3_name); + return KNOT_ERROR; + } + + assert(ret == *nsec3_name); + + return KNOT_EOK; +} + +/*----------------------------------------------------------------------------*/ +/*! + * \brief Tries to find the given domain name in the zone tree. + * + * \param zone Zone to search in. + * \param name Domain name to find. + * \param node Found node. + * \param previous Previous node in canonical order (i.e. the one directly + * preceding \a name in canonical order, regardless if the name + * is in the zone or not). + * + * \retval <> 0 if the domain name was found. In such case \a node holds the + * zone node with \a name as its owner. \a previous is set + * properly. + * \retval 0 if the domain name was not found. \a node may hold any (or none) + * node. \a previous is set properly. + */ +static int knot_zone_contents_find_in_tree(knot_zone_tree_t *tree, + const knot_dname_t *name, + knot_node_t **node, + knot_node_t **previous) +{ + assert(tree != NULL); + assert(name != NULL); + assert(node != NULL); + assert(previous != NULL); + + knot_node_t *found = NULL, *prev = NULL; +// knot_node_t *found2 = NULL, *prev2 = NULL; + + int exact_match = knot_zone_tree_get_less_or_equal( + tree, name, &found, &prev, 1); + +// assert(prev != NULL); + assert(exact_match >= 0); + *node = found; + *previous = prev; + +// if (prev == NULL) { +// // either the returned node is the root of the tree, or it is +// // the leftmost node in the tree; in both cases node was found +// // set the previous node of the found node +// assert(exact_match); +// assert(found != NULL); +// *previous = knot_node_get_previous(found, 1); +// } else { +// // otherwise check if the previous node is not an empty +// // non-terminal +// *previous = (knot_node_rrset_count(prev) == 0) +// ? knot_node_get_previous(prev, 1) +// : prev; +// } + + return exact_match; +} + +/*----------------------------------------------------------------------------*/ + +static void knot_zone_contents_node_to_hash(knot_zone_tree_node_t *tnode, + void *data) +{ + assert(tnode != NULL && tnode->node != NULL + && tnode->node->owner != NULL && data != NULL); + + knot_node_t *node = tnode->node; + + knot_zone_contents_t *zone = (knot_zone_contents_t *)data; + /* + * By the original approach, only authoritative nodes and delegation + * points should be added to the hash table, but currently, all nodes + * are being added when the zone is created (don't know why actually:), + * so we will do no distinction here neither. + */ + +#ifdef USE_HASH_TABLE +//dbg_zone_exec( +// char *name = knot_dname_to_str(node->owner); +// dbg_zone("Adding node with owner %s to hash table.\n", name); +// free(name); +//); + //assert(zone->table != NULL); + // add the node also to the hash table if authoritative, or deleg. point + if (zone->table != NULL + && ck_insert_item(zone->table, + (const char *)node->owner->name, + node->owner->size, (void *)node) != 0) { + dbg_zone("Error inserting node into hash table!\n"); + } +#endif +} + +/*----------------------------------------------------------------------------*/ + +static int knot_zone_contents_dnames_from_rdata_to_table( + knot_dname_table_t *table, knot_rdata_t *rdata, + knot_rrtype_descriptor_t *d) +{ + unsigned int count = knot_rdata_item_count(rdata); + int rc = 0; + assert(count <= d->length); + // for each RDATA item + for (unsigned int j = 0; j < count; ++j) { + if (d->wireformat[j] + == KNOT_RDATA_WF_COMPRESSED_DNAME + || d->wireformat[j] + == KNOT_RDATA_WF_UNCOMPRESSED_DNAME + || d->wireformat[j] + == KNOT_RDATA_WF_LITERAL_DNAME) { + dbg_zone("Saving dname from " + "rdata to dname table" + ".\n"); + rc = knot_dname_table_add_dname_check(table, + &knot_rdata_get_item(rdata, j)->dname); + if (rc < 0) { + dbg_zone("Error: %s\n", + knot_strerror(rc)); + return rc; + } + } + } + + dbg_zone("RDATA OK.\n"); + return KNOT_EOK; +} + +/*----------------------------------------------------------------------------*/ + +static int knot_zone_contents_dnames_from_rrset_to_table( + knot_dname_table_t *table, knot_rrset_t *rrset, int replace_owner, + knot_dname_t *owner) +{ + assert(table != NULL && rrset != NULL && owner != NULL); + + if (replace_owner) { + // discard the old owner and replace it with the new + knot_rrset_set_owner(rrset, owner); + } + dbg_zone("RRSet owner: %p\n", rrset->owner); + + knot_rrtype_descriptor_t *desc = knot_rrtype_descriptor_by_type( + knot_rrset_type(rrset)); + if (desc == NULL) { + // not recognized RR type, ignore + dbg_zone("RRSet type not recognized.\n"); + return KNOT_EOK; + } + // for each RDATA in RRSet + knot_rdata_t *rdata = knot_rrset_get_rdata(rrset); + while (rdata != NULL) { + int rc = knot_zone_contents_dnames_from_rdata_to_table(table, + rdata, desc); + if (rc != KNOT_EOK) { + return rc; + } + + rdata = knot_rrset_rdata_get_next(rrset, rdata); + } + + dbg_zone("RRSet OK.\n"); + return KNOT_EOK; +} + +/*----------------------------------------------------------------------------*/ + +static int knot_zone_contents_dnames_from_node_to_table( + knot_dname_table_t *table, knot_node_t *node) +{ + /* + * Assuming that all the RRSets have the same owner as the node. + */ + + // insert owner + char *name = knot_dname_to_str(node->owner); + dbg_zone("Node owner before inserting to dname table: %p.\n", + node->owner); + dbg_zone("Node owner before inserting to dname table: %s.\n", + name); + free(name); + //knot_dname_t *old_owner = node->owner; + int rc = knot_dname_table_add_dname_check(table, &node->owner); + if (rc < 0) { + dbg_zone("Failed to add dname to dname table.\n"); + return rc; + } + int replace_owner = (rc > 0); + dbg_zone("Node owner after inserting to dname table: %p.\n", + node->owner); + name = knot_dname_to_str(node->owner); + dbg_zone("Node owner after inserting to dname table: %s.\n", + name); + free(name); + + knot_rrset_t **rrsets = knot_node_get_rrsets(node); + // for each RRSet + for (int i = 0; i < knot_node_rrset_count(node); ++i) { + dbg_zone("Inserting RRSets from node to table.\n"); + rc = knot_zone_contents_dnames_from_rrset_to_table(table, + rrsets[i], replace_owner, node->owner); + if (rc != KNOT_EOK) { + return rc; + } + } + + free(rrsets); + + dbg_zone("Node OK\n"); + return KNOT_EOK; +} + +/*----------------------------------------------------------------------------*/ +/* API functions */ +/*----------------------------------------------------------------------------*/ + +knot_zone_contents_t *knot_zone_contents_new(knot_node_t *apex, + uint node_count, + int use_domain_table, + struct knot_zone *zone) +{ + knot_zone_contents_t *contents = (knot_zone_contents_t *) + calloc(1, sizeof(knot_zone_contents_t)); + if (contents == NULL) { + ERR_ALLOC_FAILED; + return NULL; + } + +// printf("created cont: %p (%s)\n", +// contents, knot_dname_to_str(apex->owner)); + + contents->apex = apex; + contents->zone = zone; + knot_node_set_zone(apex, zone); + + dbg_zone("Creating tree for normal nodes.\n"); + contents->nodes = malloc(sizeof(knot_zone_tree_t)); + if (contents->nodes == NULL) { + ERR_ALLOC_FAILED; + goto cleanup; + } + + dbg_zone("Creating tree for NSEC3 nodes.\n"); + contents->nsec3_nodes = malloc(sizeof(knot_zone_tree_t)); + if (contents->nsec3_nodes == NULL) { + ERR_ALLOC_FAILED; + goto cleanup; + } + + if (use_domain_table) { + dbg_zone("Creating domain name table.\n"); + contents->dname_table = knot_dname_table_new(); + if (contents->dname_table == NULL) { + ERR_ALLOC_FAILED; + goto cleanup; + } + } else { + contents->dname_table = NULL; + } + + contents->node_count = node_count; + + /* Initialize NSEC3 params */ + dbg_zone("Initializing NSEC3 parameters.\n"); + contents->nsec3_params.algorithm = 0; + contents->nsec3_params.flags = 0; + contents->nsec3_params.iterations = 0; + contents->nsec3_params.salt_length = 0; + contents->nsec3_params.salt = NULL; + + dbg_zone("Initializing zone trees.\n"); + if (knot_zone_tree_init(contents->nodes) != KNOT_EOK + || knot_zone_tree_init(contents->nsec3_nodes) != KNOT_EOK) { + goto cleanup; + } + + dbg_zone("Inserting apex into the zone tree.\n"); + if (knot_zone_tree_insert(contents->nodes, apex) != KNOT_EOK) { + dbg_zone("Failed to insert apex to the zone tree.\n"); + goto cleanup; + } + +#ifdef USE_HASH_TABLE + if (contents->node_count > 0) { + dbg_zone("Creating hash table.\n"); + contents->table = ck_create_table(contents->node_count); + if (contents->table == NULL) { + goto cleanup; + } + + // insert the apex into the hash table + dbg_zone("Inserting apex into the hash table.\n"); + if (ck_insert_item(contents->table, + (const char *)knot_dname_name( + knot_node_owner(apex)), + knot_dname_size(knot_node_owner(apex)), + (void *)apex) != 0) { + ck_destroy_table(&contents->table, NULL, 0); + goto cleanup; + } + } else { + contents->table = NULL; + } +#endif + + // insert names from the apex to the domain table + if (use_domain_table) { + dbg_zone("Inserting names from apex to table.\n"); + int rc = knot_zone_contents_dnames_from_node_to_table( + contents->dname_table, apex); + if (rc != KNOT_EOK) { + ck_destroy_table(&contents->table, NULL, 0); + goto cleanup; + } + } + + return contents; + +cleanup: + dbg_zone("Cleaning up.\n"); + free(contents->dname_table); + free(contents->nodes); + free(contents->nsec3_nodes); + free(contents); + return NULL; +} + +/*----------------------------------------------------------------------------*/ + +//short knot_zone_contents_generation(const knot_zone_contents_t *zone) +//{ +// return zone->generation; +//} + +/*----------------------------------------------------------------------------*/ + +int knot_zone_contents_gen_is_old(const knot_zone_contents_t *contents) +{ + return (contents->generation == 0); +} + +/*----------------------------------------------------------------------------*/ + +int knot_zone_contents_gen_is_new(const knot_zone_contents_t *contents) +{ + return (contents->generation == 1); +} + +/*----------------------------------------------------------------------------*/ + +int knot_zone_contents_gen_is_finished(const knot_zone_contents_t *contents) +{ + return (contents->generation == -1); +} + +/*----------------------------------------------------------------------------*/ + +//void knot_zone_contents_switch_generation(knot_zone_contents_t *zone) +//{ +// zone->generation = 1 - zone->generation; +//} + +/*----------------------------------------------------------------------------*/ + +void knot_zone_contents_set_gen_old(knot_zone_contents_t *contents) +{ + contents->generation = 0; +} + +/*----------------------------------------------------------------------------*/ + +void knot_zone_contents_set_gen_new(knot_zone_contents_t *contents) +{ + contents->generation = 1; +} + +/*----------------------------------------------------------------------------*/ + +void knot_zone_contents_set_gen_new_finished(knot_zone_contents_t *contents) +{ + contents->generation = -1; +} + +/*----------------------------------------------------------------------------*/ + +uint16_t knot_zone_contents_class(const knot_zone_contents_t *contents) +{ + if (contents == NULL || contents->apex == NULL + || knot_node_rrset(contents->apex, KNOT_RRTYPE_SOA) == NULL) { + return KNOT_EBADARG; + } + + return knot_rrset_class(knot_node_rrset(contents->apex, + KNOT_RRTYPE_SOA)); +} + +/*----------------------------------------------------------------------------*/ + +int knot_zone_contents_add_node(knot_zone_contents_t *zone, + knot_node_t *node, int create_parents, + uint8_t flags, int use_domain_table) +{ + if (zone == NULL || node == NULL) { + return KNOT_EBADARG; + } + + int ret = 0; + if ((ret = knot_zone_contents_check_node(zone, node)) != 0) { + return ret; + } + + ret = knot_zone_tree_insert(zone->nodes, node); + if (ret != KNOT_EOK) { + dbg_zone("Failed to insert node into zone tree.\n"); + return ret; + } + +#ifdef USE_HASH_TABLE + char *name = knot_dname_to_str(node->owner); +// dbg_zone("Adding node with owner %s to hash table.\n", name); + free(name); + //assert(zone->table != NULL); + // add the node also to the hash table if authoritative, or deleg. point + if (zone->table != NULL + && ck_insert_item(zone->table, + (const char *)node->owner->name, + node->owner->size, (void *)node) != 0) { + dbg_zone("Error inserting node into hash table!\n"); + /*! \todo Remove the node from the tree. */ + return KNOT_EHASH; + } +#endif + assert(knot_zone_contents_find_node(zone, node->owner)); + + if (use_domain_table) { + ret = knot_zone_contents_dnames_from_node_to_table( + zone->dname_table, node); + if (ret != KNOT_EOK) { + /*! \todo Remove node from the tree and hash table.*/ + dbg_zone("Failed to add dnames into table.\n"); + return ret; + } + } + + knot_node_set_zone(node, zone->zone); + + if (!create_parents) { + return KNOT_EOK; + } + + dbg_zone("Creating parents of the node.\n"); + + knot_dname_t *chopped = + knot_dname_left_chop(knot_node_owner(node)); + if (knot_dname_compare(knot_node_owner(zone->apex), chopped) == 0) { + dbg_zone("Zone apex is the parent.\n"); + knot_node_set_parent(node, zone->apex); + } else { + knot_node_t *next_node; + while ((next_node + = knot_zone_contents_get_node(zone, chopped)) == NULL) { + /* Adding new dname to zone + add to table. */ + dbg_zone("Creating new node.\n"); + next_node = knot_node_new(chopped, NULL, flags); + if (next_node == NULL) { + /* Directly discard. */ + knot_dname_free(&chopped); + return KNOT_ENOMEM; + } + if (use_domain_table) { + ret = + knot_zone_contents_dnames_from_node_to_table( + zone->dname_table, next_node); + if (ret != KNOT_EOK) { + /*! \todo Will next_node leak? */ + knot_dname_release(chopped); + return ret; + } + } + + if (next_node->owner != chopped) { + /* Node owner was in RDATA */ + chopped = next_node->owner; + } + + assert(knot_zone_contents_find_node(zone, chopped) + == NULL); + assert(knot_node_owner(next_node) == chopped); + + dbg_zone("Inserting new node to zone tree.\n"); +// TREE_INSERT(zone->tree, knot_node, avl, next_node); + + ret = knot_zone_tree_insert(zone->nodes, + next_node); + if (ret != KNOT_EOK) { + dbg_zone("Failed to insert new node " + "to zone tree.\n"); + /*! \todo Delete the node?? */ + /* Directly discard. */ + knot_dname_release(chopped); + return ret; + } + +#ifdef USE_HASH_TABLE +dbg_zone_exec( + char *name = knot_dname_to_str( + knot_node_owner(next_node)); + dbg_zone("Adding new node with owner %s to " + "hash table.\n", name); + free(name); +); + + if (zone->table != NULL + && ck_insert_item(zone->table, + (const char *)knot_dname_name( + knot_node_owner(next_node)), + knot_dname_size(knot_node_owner(next_node)), + (void *)next_node) != 0) { + dbg_zone("Error inserting node into " + "hash table!\n"); + /*! \todo Delete the node?? */ + /* Directly discard. */ + knot_dname_release(chopped); + return KNOT_EHASH; + } + + // set parent + knot_node_set_parent(node, next_node); + + // set zone + knot_node_set_zone(next_node, zone->zone); + + // check if the node is not wildcard child of the parent + if (knot_dname_is_wildcard( + knot_node_owner(node))) { + knot_node_set_wildcard_child(next_node, node); + } +#endif + dbg_zone("Next parent.\n"); + node = next_node; + knot_dname_t *chopped_last = chopped; + chopped = knot_dname_left_chop(chopped); + + /* Release last chop, reference is already stored + * in next_node. + */ + knot_dname_release(chopped_last); + + } + // set the found parent (in the zone) as the parent of the last + // inserted node + assert(knot_node_parent(node, 0) == NULL); + knot_node_set_parent(node, next_node); + + dbg_zone("Created all parents.\n"); + } + + /* Directly discard. */ + /*! \todo This may be double-release. */ + knot_dname_release(chopped); + + return KNOT_EOK; +} + +/*----------------------------------------------------------------------------*/ + +int knot_zone_contents_add_rrset(knot_zone_contents_t *zone, + knot_rrset_t *rrset, knot_node_t **node, + knot_rrset_dupl_handling_t dupl, + int use_domain_table) +{ + if (zone == NULL || rrset == NULL || zone->apex == NULL + || zone->apex->owner == NULL || node == NULL) { + return KNOT_EBADARG; + } + + // check if the RRSet belongs to the zone + if (knot_dname_compare(knot_rrset_owner(rrset), + zone->apex->owner) != 0 + && !knot_dname_is_subdomain(knot_rrset_owner(rrset), + zone->apex->owner)) { + return KNOT_EBADZONE; + } + + if ((*node) == NULL + && (*node = knot_zone_contents_get_node(zone, + knot_rrset_owner(rrset))) == NULL) { + return KNOT_ENONODE; + } + + assert(*node != NULL); + + // add all domain names from the RRSet to domain name table + int rc; + + /*! \todo REMOVE RRSET */ + rc = knot_node_add_rrset(*node, rrset, + dupl == KNOT_RRSET_DUPL_MERGE); + if (rc < 0) { + dbg_zone("Failed to add RRSet to node.\n"); + return rc; + } + + int ret = rc; + + if (use_domain_table) { + dbg_zone("Saving RRSet to table.\n"); + rc = knot_zone_contents_dnames_from_rrset_to_table( + zone->dname_table, rrset, 0, (*node)->owner); + if (rc != KNOT_EOK) { + dbg_zone("Error saving domain names from " + "RRSIGs to the domain name table.\n " + "The zone may be in an inconsistent " + "state.\n"); + // WARNING: the zone is not in consistent state now - + // there may be domain names in it that are not inserted + // into the domain table + return rc; + } + } + + // replace RRSet's owner with the node's owner (that is already in the + // table) + /*! \todo Do even if domain table is not used?? */ + if (ret == KNOT_EOK && rrset->owner != (*node)->owner) { + knot_rrset_set_owner(rrset, (*node)->owner); + } + + dbg_zone("RRSet OK.\n"); + return ret; +} + +/*----------------------------------------------------------------------------*/ + +int knot_zone_contents_add_rrsigs(knot_zone_contents_t *zone, + knot_rrset_t *rrsigs, + knot_rrset_t **rrset, + knot_node_t **node, + knot_rrset_dupl_handling_t dupl, + int use_domain_table) +{ + if (zone == NULL || rrsigs == NULL || rrset == NULL || node == NULL + || zone->apex == NULL || zone->apex->owner == NULL) { +dbg_zone_exec( + dbg_zone("Parameters: zone=%p, rrsigs=%p, rrset=%p, " + "node=%p\n", zone, rrsigs, rrset, node); + if (zone != NULL) { + dbg_zone("zone->apex=%p\n", zone->apex); + if (zone->apex != NULL) { + dbg_zone("zone->apex->owner=%p\n", + zone->apex->owner); + } + } +); + return KNOT_EBADARG; + } + + // check if the RRSet belongs to the zone + if (*rrset != NULL + && knot_dname_compare(knot_rrset_owner(*rrset), + zone->apex->owner) != 0 + && !knot_dname_is_subdomain(knot_rrset_owner(*rrset), + zone->apex->owner)) { + return KNOT_EBADZONE; + } + + // check if the RRSIGs belong to the RRSet + if (*rrset != NULL + && (knot_dname_compare(knot_rrset_owner(rrsigs), + knot_rrset_owner(*rrset)) != 0)) { + dbg_zone("RRSIGs does not belong to the given RRSet.\n"); + return KNOT_EBADARG; + } + + // if no RRSet given, try to find the right RRSet + if (*rrset == NULL) { + // even no node given + // find proper node + knot_node_t *(*get_node)(const knot_zone_contents_t *, + const knot_dname_t *) + = (knot_rdata_rrsig_type_covered( + knot_rrset_rdata(rrsigs)) == KNOT_RRTYPE_NSEC3) + ? knot_zone_contents_get_nsec3_node + : knot_zone_contents_get_node; + + if (*node == NULL + && (*node = get_node( + zone, knot_rrset_owner(rrsigs))) == NULL) { + dbg_zone("Failed to find node for RRSIGs.\n"); + return KNOT_ENONODE; + } + + assert(*node != NULL); + + // find the RRSet in the node + // take only the first RDATA from the RRSIGs + dbg_zone("Finding RRSet for type %s\n", + knot_rrtype_to_string( + knot_rdata_rrsig_type_covered( + knot_rrset_rdata(rrsigs)))); + *rrset = knot_node_get_rrset( + *node, knot_rdata_rrsig_type_covered( + knot_rrset_rdata(rrsigs))); + if (*rrset == NULL) { + dbg_zone("Failed to find RRSet for RRSIGs.\n"); + return KNOT_ENORRSET; + } + } + + assert(*rrset != NULL); + + // add all domain names from the RRSet to domain name table + int rc; + int ret = KNOT_EOK; + + rc = knot_rrset_add_rrsigs(*rrset, rrsigs, dupl); + if (rc < 0) { + dbg_dname("Failed to add RRSIGs to RRSet.\n"); + return rc; + } else if (rc > 0) { + assert(dupl == KNOT_RRSET_DUPL_MERGE); + ret = 1; + } + + if (use_domain_table) { + dbg_zone("Saving RRSIG RRSet to table.\n"); + rc = knot_zone_contents_dnames_from_rrset_to_table( + zone->dname_table, rrsigs, 0, (*rrset)->owner); + if (rc != KNOT_EOK) { + dbg_zone("Error saving domain names from " + "RRSIGs to the domain name table.\n " + "The zone may be in an inconsistent " + "state.\n"); + // WARNING: the zone is not in consistent state now - + // there may be domain names in it that are not inserted + // into the domain table + return rc; + } + } + + // replace RRSet's owner with the node's owner (that is already in the + // table) + if ((*rrset)->owner != (*rrset)->rrsigs->owner) { + knot_rrset_set_owner((*rrset)->rrsigs, (*rrset)->owner); + } + + dbg_zone("RRSIGs OK\n"); + return ret; +} + +/*----------------------------------------------------------------------------*/ + +int knot_zone_contents_add_nsec3_node(knot_zone_contents_t *zone, + knot_node_t *node, int create_parents, + uint8_t flags, int use_domain_table) +{ + UNUSED(create_parents); + UNUSED(flags); + + if (zone == NULL || node == NULL) { + return KNOT_EBADARG; + } + + int ret = 0; + if ((ret = knot_zone_contents_check_node(zone, node)) != 0) { + return ret; + } + + // how to know if this is successfull?? +// TREE_INSERT(zone->nsec3_nodes, knot_node, avl, node); + knot_zone_tree_insert(zone->nsec3_nodes, node); + + if (use_domain_table) { + ret = knot_zone_contents_dnames_from_node_to_table( + zone->dname_table, node); + if (ret != KNOT_EOK) { + /*! \todo Remove the node from the tree. */ + dbg_zone("Failed to add dnames into table.\n"); + return ret; + } + } + + // no parents to be created, the only parent is the zone apex + // set the apex as the parent of the node + knot_node_set_parent(node, zone->apex); + + // set the zone to the node + knot_node_set_zone(node, zone->zone); + + // cannot be wildcard child, so nothing to be done + + return KNOT_EOK; +} + +/*----------------------------------------------------------------------------*/ + +int knot_zone_contents_add_nsec3_rrset(knot_zone_contents_t *zone, + knot_rrset_t *rrset, + knot_node_t **node, + knot_rrset_dupl_handling_t dupl, + int use_domain_table) +{ + if (zone == NULL || rrset == NULL || zone->apex == NULL + || zone->apex->owner == NULL || node == NULL) { + return KNOT_EBADARG; + } + + // check if the RRSet belongs to the zone + if (knot_dname_compare(knot_rrset_owner(rrset), + zone->apex->owner) != 0 + && !knot_dname_is_subdomain(knot_rrset_owner(rrset), + zone->apex->owner)) { + return KNOT_EBADZONE; + } + + if ((*node) == NULL + && (*node = knot_zone_contents_get_nsec3_node( + zone, knot_rrset_owner(rrset))) == NULL) { + return KNOT_ENONODE; + } + + assert(*node != NULL); + + // add all domain names from the RRSet to domain name table + int rc; + + /*! \todo REMOVE RRSET */ + rc = knot_node_add_rrset(*node, rrset, + dupl == KNOT_RRSET_DUPL_MERGE); + if (rc < 0) { + return rc; + } + + int ret = rc; + + if (use_domain_table) { + dbg_zone("Saving NSEC3 RRSet to table.\n"); + rc = knot_zone_contents_dnames_from_rrset_to_table( + zone->dname_table, rrset, 0, (*node)->owner); + if (rc != KNOT_EOK) { + dbg_zone("Error saving domain names from " + "RRSIGs to the domain name table.\n " + "The zone may be in an inconsistent " + "state.\n"); + // WARNING: the zone is not in consistent state now - + // there may be domain names in it that are not inserted + // into the domain table + return rc; + } + } + + // replace RRSet's owner with the node's owner (that is already in the + // table) + /*! \todo Do even if domain table is not used? */ + if (rrset->owner != (*node)->owner) { + knot_rrset_set_owner(rrset, (*node)->owner); + } + + dbg_zone("NSEC3 OK\n"); + return ret; +} + +/*----------------------------------------------------------------------------*/ + +int knot_zone_contents_remove_node(knot_zone_contents_t *contents, + const knot_node_t *node, knot_zone_tree_node_t **removed_tree, + ck_hash_table_item_t **removed_hash) +{ + if (contents == NULL || node == NULL) { + return KNOT_EBADARG; + } + + const knot_dname_t *owner = knot_node_owner(node); + + // 1) remove the node from hash table + *removed_hash = NULL; + *removed_hash = ck_remove_item(contents->table, + (const char *)knot_dname_name(owner), + knot_dname_size(owner)); +// int ret = ck_detete_item(contents->table, +// (const char *)knot_dname_name(owner), +// knot_dname_size(owner), NULL, 0); + if (*removed_hash == NULL) { + return KNOT_ENONODE; + } + + // 2) remove the node from the zone tree + *removed_tree = NULL; + int ret = knot_zone_tree_remove(contents->nodes, owner, removed_tree); + if (ret != KNOT_EOK) { + return KNOT_ENONODE; + } + + return KNOT_EOK; +} + +/*----------------------------------------------------------------------------*/ + +int knot_zone_contents_remove_nsec3_node(knot_zone_contents_t *contents, + const knot_node_t *node, knot_zone_tree_node_t **removed) +{ + if (contents == NULL || node == NULL) { + return KNOT_EBADARG; + } + + const knot_dname_t *owner = knot_node_owner(node); + + // remove the node from the zone tree + *removed = NULL; + int ret = knot_zone_tree_remove(contents->nsec3_nodes, owner, removed); + if (ret != KNOT_EOK) { + return KNOT_ENONODE; + } + + return KNOT_EOK; +} + +/*----------------------------------------------------------------------------*/ + +int knot_zone_contents_create_and_fill_hash_table( + knot_zone_contents_t *zone) +{ + if (zone == NULL || zone->apex == NULL || zone->apex->owner == NULL) { + return KNOT_EBADARG; + } + /* + * 1) Create hash table. + */ +#ifdef USE_HASH_TABLE + if (zone->node_count > 0) { + zone->table = ck_create_table(zone->node_count); + if (zone->table == NULL) { + return KNOT_ENOMEM; + } + + // insert the apex into the hash table + if (ck_insert_item(zone->table, + (const char *)zone->apex->owner->name, + zone->apex->owner->size, + (void *)zone->apex) != 0) { + return KNOT_EHASH; + } + } else { + zone->table = NULL; + return KNOT_EOK; // OK? + } + + /* + * 2) Fill in the hash table. + * + * In this point, the nodes in the zone must be adjusted, so that only + * relevant nodes (authoritative and delegation points are inserted. + * + * TODO: how to know if this was successful?? + */ + /*! \todo Replace by zone tree. */ + int ret = knot_zone_tree_forward_apply_inorder(zone->nodes, + knot_zone_contents_node_to_hash, zone); + if (ret != KNOT_EOK) { + dbg_zone("Failed to insert nodes to hash table.\n"); + return ret; + } + +#endif + return KNOT_EOK; +} + +/*----------------------------------------------------------------------------*/ + +knot_node_t *knot_zone_contents_get_node(const knot_zone_contents_t *zone, + const knot_dname_t *name) +{ + if (zone == NULL || name == NULL) { + return NULL; + } + + // create dummy node to use for lookup +// knot_node_t *tmp = knot_node_new((knot_dname_t *)name, NULL); +// knot_node_t *n = TREE_FIND(zone->tree, knot_node, avl, tmp); +// knot_node_free(&tmp, 0); + + knot_node_t *n; + int ret = knot_zone_tree_get(zone->nodes, name, &n); + if (ret != KNOT_EOK) { + dbg_zone("Failed to find name in the zone tree.\n"); + return NULL; + } + + return n; +} + +/*----------------------------------------------------------------------------*/ + +knot_node_t *knot_zone_contents_get_nsec3_node( + const knot_zone_contents_t *zone, const knot_dname_t *name) +{ + if (zone == NULL || name == NULL) { + return NULL; + } + + // create dummy node to use for lookup +// knot_node_t *tmp = knot_node_new((knot_dname_t *)name, NULL); +// knot_node_t *n = TREE_FIND(zone->nsec3_nodes, knot_node, avl, tmp); +// knot_node_free(&tmp, 0); + knot_node_t *n; + int ret = knot_zone_tree_get(zone->nsec3_nodes, name, &n); + + if (ret != KNOT_EOK) { + dbg_zone("Failed to find NSEC3 name in the zone tree." + "\n"); + return NULL; + } + + return n; +} + +/*----------------------------------------------------------------------------*/ + +const knot_node_t *knot_zone_contents_find_node( + const knot_zone_contents_t *zone,const knot_dname_t *name) +{ + return knot_zone_contents_get_node(zone, name); +} + +/*----------------------------------------------------------------------------*/ + +int knot_zone_contents_find_dname(const knot_zone_contents_t *zone, + const knot_dname_t *name, + const knot_node_t **node, + const knot_node_t **closest_encloser, + const knot_node_t **previous) +{ + if (zone == NULL || name == NULL || node == NULL + || closest_encloser == NULL || previous == NULL + || zone->apex == NULL || zone->apex->owner == NULL) { + return KNOT_EBADARG; + } + +dbg_zone_exec( + char *name_str = knot_dname_to_str(name); + char *zone_str = knot_dname_to_str(zone->apex->owner); + dbg_zone("Searching for name %s in zone %s...\n", + name_str, zone_str); + free(name_str); + free(zone_str); +); + + if (knot_dname_compare(name, zone->apex->owner) == 0) { + *node = zone->apex; + *closest_encloser = *node; + return KNOT_ZONE_NAME_FOUND; + } + + if (!knot_dname_is_subdomain(name, zone->apex->owner)) { + *node = NULL; + *closest_encloser = NULL; + return KNOT_EBADZONE; + } + + knot_node_t *found = NULL, *prev = NULL; + + int exact_match = knot_zone_contents_find_in_tree(zone->nodes, name, + &found, &prev); + assert(exact_match >= 0); + *node = found; + *previous = prev; + +dbg_zone_exec( + char *name_str = (*node) ? knot_dname_to_str((*node)->owner) + : "(nil)"; + char *name_str2 = (*previous != NULL) + ? knot_dname_to_str((*previous)->owner) + : "(nil)"; + dbg_zone("Search function returned %d, node %s and prev: %s\n", + exact_match, name_str, name_str2); + + if (*node) { + free(name_str); + } + if (*previous != NULL) { + free(name_str2); + } +); + + *closest_encloser = *node; + + // there must be at least one node with domain name less or equal to + // the searched name if the name belongs to the zone (the root) + if (*node == NULL) { + return KNOT_EBADZONE; + } + + // TODO: this could be replaced by saving pointer to closest encloser + // in node + + if (!exact_match) { + int matched_labels = knot_dname_matched_labels( + knot_node_owner((*closest_encloser)), name); + while (matched_labels < knot_dname_label_count( + knot_node_owner((*closest_encloser)))) { + (*closest_encloser) = + knot_node_parent((*closest_encloser), 1); + assert(*closest_encloser); + } + } +dbg_zone_exec( + char *n = knot_dname_to_str(knot_node_owner((*closest_encloser))); + dbg_zone("Closest encloser: %s\n", n); + free(n); +); + + dbg_zone("find_dname() returning %d\n", exact_match); + + return (exact_match) + ? KNOT_ZONE_NAME_FOUND + : KNOT_ZONE_NAME_NOT_FOUND; +} + +/*----------------------------------------------------------------------------*/ + +knot_node_t *knot_zone_contents_get_previous( + const knot_zone_contents_t *zone, const knot_dname_t *name) +{ + if (zone == NULL || name == NULL) { + return NULL; + } + + knot_node_t *found = NULL, *prev = NULL; + + int exact_match = knot_zone_contents_find_in_tree(zone->nodes, name, + &found, &prev); + assert(exact_match >= 0); + assert(prev != NULL); + + return prev; +} + +/*----------------------------------------------------------------------------*/ + +const knot_node_t *knot_zone_contents_find_previous( + const knot_zone_contents_t *zone, const knot_dname_t *name) +{ + return knot_zone_contents_get_previous(zone, name); +} + +/*----------------------------------------------------------------------------*/ + +knot_node_t *knot_zone_contents_get_previous_nsec3( + const knot_zone_contents_t *zone, const knot_dname_t *name) +{ + if (zone == NULL || name == NULL) { + return NULL; + } + + knot_node_t *found = NULL, *prev = NULL; + + int exact_match = knot_zone_contents_find_in_tree(zone->nsec3_nodes, + name, &found, &prev); + assert(exact_match >= 0); + assert(prev != NULL); + + return prev; +} + +/*----------------------------------------------------------------------------*/ + +const knot_node_t *knot_zone_contents_find_previous_nsec3( + const knot_zone_contents_t *zone, const knot_dname_t *name) +{ + return knot_zone_contents_get_previous(zone, name); +} + +/*----------------------------------------------------------------------------*/ + +static void knot_zone_contents_left_chop(char *name, size_t *size) +{ + short label_size = name[0]; + + memmove(name, name + label_size + 1, *size -label_size - 1); + *size = *size - label_size - 1; +} + +/*----------------------------------------------------------------------------*/ +#ifdef USE_HASH_TABLE +int knot_zone_contents_find_dname_hash(const knot_zone_contents_t *zone, + const knot_dname_t *name, + const knot_node_t **node, + const knot_node_t **closest_encloser) +{ + if (zone == NULL || name == NULL || node == NULL + || closest_encloser == NULL) { + return KNOT_EBADARG; + } + +dbg_zone_exec( + char *name_str = knot_dname_to_str(name); + char *zone_str = knot_dname_to_str(zone->apex->owner); + dbg_zone("Searching for name %s in zone %s...\n", + name_str, zone_str); + free(name_str); + free(zone_str); +); + + if (knot_dname_compare(name, zone->apex->owner) == 0) { + *node = zone->apex; + *closest_encloser = *node; + return KNOT_ZONE_NAME_FOUND; + } + + if (!knot_dname_is_subdomain(name, zone->apex->owner)) { + *node = NULL; + *closest_encloser = NULL; + return KNOT_EBADZONE; + } + + // temporary name used for hashing + char name_tmp[KNOT_MAX_DNAME_LENGTH]; + size_t name_size = name->size; + if (knot_dname_to_lower_copy(name, name_tmp, KNOT_MAX_DNAME_LENGTH) + != KNOT_EOK) { + return KNOT_ERROR; + } + + const ck_hash_table_item_t *item = ck_find_item(zone->table, + name_tmp, name_size); + + if (item != NULL) { + *node = (const knot_node_t *)item->value; + *closest_encloser = *node; + + dbg_zone("Found node in hash table: %p (owner %p, " + "labels: %d)\n", *node, (*node)->owner, + knot_dname_label_count((*node)->owner)); + assert(*node != NULL); + assert(*closest_encloser != NULL); + return KNOT_ZONE_NAME_FOUND; + } + + *node = NULL; + + // chop leftmost labels until some node is found + // copy the name for chopping + /* Local allocation, will be discarded. */ + //knot_dname_t *name_copy = knot_dname_deep_copy(name); +dbg_zone_exec( + //char *n = knot_dname_to_str(name_copy); + dbg_zone("Finding closest encloser..\nStarting with: %.*s\n", + (int)name_size, name_tmp); + //free(n); +); + + while (item == NULL) { + //knot_dname_left_chop_no_copy(name_copy); + knot_zone_contents_left_chop(name_tmp, &name_size); +dbg_zone_exec( + //char *n = knot_dname_to_str(name_copy); + dbg_zone("Chopped leftmost label: %.*s\n", + (int)name_size, name_tmp); + //free(n); +); + // not satisfied in root zone!! + //assert(name_copy->label_count > 0); + assert(name_size > 0); + + item = ck_find_item(zone->table, name_tmp, name_size); + } + + /* Directly discard. */ + //knot_dname_free(&name_copy); + + assert(item != NULL); + *closest_encloser = (const knot_node_t *)item->value; + + return KNOT_ZONE_NAME_NOT_FOUND; +} +#endif +/*----------------------------------------------------------------------------*/ + +const knot_node_t *knot_zone_contents_find_nsec3_node( + const knot_zone_contents_t *zone, const knot_dname_t *name) +{ + return knot_zone_contents_get_nsec3_node(zone, name); +} + +/*----------------------------------------------------------------------------*/ + +int knot_zone_contents_find_nsec3_for_name(const knot_zone_contents_t *zone, + const knot_dname_t *name, + const knot_node_t **nsec3_node, + const knot_node_t **nsec3_previous, + int check_ver) +{ + if (zone == NULL || name == NULL + || nsec3_node == NULL || nsec3_previous == NULL) { + return KNOT_EBADARG; + } + + knot_dname_t *nsec3_name = NULL; + int ret = knot_zone_contents_nsec3_name(zone, name, &nsec3_name); + + if (ret != KNOT_EOK) { + return ret; + } + +dbg_zone_exec( + char *n = knot_dname_to_str(nsec3_name); + dbg_zone("NSEC3 node name: %s.\n", n); + free(n); +); + + const knot_node_t *found = NULL, *prev = NULL; + + // create dummy node to use for lookup + int exact_match = knot_zone_tree_find_less_or_equal( + zone->nsec3_nodes, nsec3_name, &found, &prev, check_ver); + assert(exact_match >= 0); + + knot_dname_release(nsec3_name); + +dbg_zone_exec( + if (found) { + char *n = knot_dname_to_str(found->owner); + dbg_zone("Found NSEC3 node: %s.\n", n); + free(n); + } else { + dbg_zone("Found no NSEC3 node.\n"); + } + + if (prev) { + assert(prev->owner); + char *n = knot_dname_to_str(prev->owner); + dbg_zone("Found previous NSEC3 node: %s.\n", n); + free(n); + } else { + dbg_zone("Found no previous NSEC3 node.\n"); + } +); + *nsec3_node = found; + + if (prev == NULL) { + // either the returned node is the root of the tree, or it is + // the leftmost node in the tree; in both cases node was found + // set the previous node of the found node + assert(exact_match); + assert(*nsec3_node != NULL); + *nsec3_previous = knot_node_previous(*nsec3_node, check_ver); + } else { + *nsec3_previous = prev; + } + + dbg_zone("find_nsec3_for_name() returning %d\n", exact_match); + + return (exact_match) + ? KNOT_ZONE_NAME_FOUND + : KNOT_ZONE_NAME_NOT_FOUND; +} + +/*----------------------------------------------------------------------------*/ + +const knot_node_t *knot_zone_contents_apex( + const knot_zone_contents_t *zone) +{ + if (zone == NULL) { + return NULL; + } + + return zone->apex; +} + +/*----------------------------------------------------------------------------*/ + +knot_node_t *knot_zone_contents_get_apex(const knot_zone_contents_t *zone) +{ + if (zone == NULL) { + return NULL; + } + + return zone->apex; +} + +/*----------------------------------------------------------------------------*/ + +//knot_dname_t *knot_zone_contents_name(const knot_zone_contents_t *zone) +//{ +// if (zone == NULL) { +// return NULL; +// } + +// return zone->name; +//} + +/*----------------------------------------------------------------------------*/ + +int knot_zone_contents_adjust(knot_zone_contents_t *zone, int check_ver) +{ + if (zone == NULL) { + return KNOT_EBADARG; + } + + // load NSEC3PARAM (needed on adjusting function) + knot_zone_contents_load_nsec3param(zone); + + knot_zone_adjust_arg_t adjust_arg; + adjust_arg.zone = zone; + adjust_arg.first_node = NULL; + adjust_arg.previous_node = NULL; + adjust_arg.check_ver = check_ver; + + dbg_zone("Adjusting normal nodes.\n"); + int ret = knot_zone_tree_forward_apply_inorder(zone->nodes, + knot_zone_contents_adjust_node_in_tree, + &adjust_arg); + if (ret != KNOT_EOK) { + return ret; + } + dbg_zone("Done.\n"); + + assert(zone->apex == adjust_arg.first_node); + knot_node_set_previous(zone->apex, adjust_arg.previous_node); + + adjust_arg.first_node = NULL; + adjust_arg.previous_node = NULL; + + dbg_zone("Adjusting NSEC3 nodes.\n"); + ret = knot_zone_tree_forward_apply_inorder( + zone->nsec3_nodes, + knot_zone_contents_adjust_nsec3_node_in_tree, + &adjust_arg); + + dbg_zone("Done.\n"); + if (adjust_arg.first_node) { + knot_node_set_previous(adjust_arg.first_node, + adjust_arg.previous_node); + } + + return ret; +} + +/*----------------------------------------------------------------------------*/ + +int knot_zone_contents_load_nsec3param(knot_zone_contents_t *zone) +{ + if (zone == NULL || zone->apex == NULL) { + return KNOT_EBADARG; + } + + const knot_rrset_t *rrset = knot_node_rrset(zone->apex, + KNOT_RRTYPE_NSEC3PARAM); + + if (rrset != NULL) { + knot_nsec3_params_from_wire(&zone->nsec3_params, rrset); + } else { + memset(&zone->nsec3_params, 0, sizeof(knot_nsec3_params_t)); + } + + return KNOT_EOK; +} + +/*----------------------------------------------------------------------------*/ + +int knot_zone_contents_nsec3_enabled(const knot_zone_contents_t *zone) +{ + if (zone == NULL) { + return KNOT_EBADARG; + } + + //return (zone->nsec3_params.algorithm != 0); + return (zone->nsec3_nodes->th_root != NULL); +} + +/*----------------------------------------------------------------------------*/ + +const knot_nsec3_params_t *knot_zone_contents_nsec3params( + const knot_zone_contents_t *zone) +{ + if (zone == NULL) { + return NULL; + } + + if (knot_zone_contents_nsec3_enabled(zone)) { + return &zone->nsec3_params; + } else { + return NULL; + } +} + +/*----------------------------------------------------------------------------*/ + +int knot_zone_contents_tree_apply_postorder(knot_zone_contents_t *zone, + void (*function)(knot_node_t *node, void *data), + void *data) +{ + if (zone == NULL) { + return KNOT_EBADARG; + } + + knot_zone_tree_func_t f; + f.func = function; + f.data = data; + + return knot_zone_tree_forward_apply_postorder(zone->nodes, + knot_zone_tree_apply, &f); +} + +/*----------------------------------------------------------------------------*/ + +int knot_zone_contents_tree_apply_inorder(knot_zone_contents_t *zone, + void (*function)(knot_node_t *node, void *data), + void *data) +{ + if (zone == NULL) { + return KNOT_EBADARG; + } + + knot_zone_tree_func_t f; + f.func = function; + f.data = data; + + return knot_zone_tree_forward_apply_inorder(zone->nodes, + knot_zone_tree_apply, &f); +} + +/*----------------------------------------------------------------------------*/ + +int knot_zone_contents_tree_apply_inorder_reverse( + knot_zone_contents_t *zone, + void (*function)(knot_node_t *node, void *data), void *data) +{ + if (zone == NULL) { + return KNOT_EBADARG; + } + + knot_zone_tree_func_t f; + f.func = function; + f.data = data; + + return knot_zone_tree_reverse_apply_inorder(zone->nodes, + knot_zone_tree_apply, &f); +} + +/*----------------------------------------------------------------------------*/ + +int knot_zone_contents_nsec3_apply_postorder(knot_zone_contents_t *zone, + void (*function)(knot_node_t *node, void *data), + void *data) +{ + if (zone == NULL) { + return KNOT_EBADARG; + } + + knot_zone_tree_func_t f; + f.func = function; + f.data = data; + + return knot_zone_tree_forward_apply_postorder( + zone->nsec3_nodes, knot_zone_tree_apply, &f); +} + +/*----------------------------------------------------------------------------*/ + +int knot_zone_contents_nsec3_apply_inorder(knot_zone_contents_t *zone, + void (*function)(knot_node_t *node, void *data), + void *data) +{ + if (zone == NULL) { + return KNOT_EBADARG; + } + + knot_zone_tree_func_t f; + f.func = function; + f.data = data; + + return knot_zone_tree_forward_apply_inorder( + zone->nsec3_nodes, knot_zone_tree_apply, &f); +} + +/*----------------------------------------------------------------------------*/ + +int knot_zone_contents_nsec3_apply_inorder_reverse( + knot_zone_contents_t *zone, + void (*function)(knot_node_t *node, void *data), void *data) +{ + if (zone == NULL) { + return KNOT_EBADARG; + } + + knot_zone_tree_func_t f; + f.func = function; + f.data = data; + + return knot_zone_tree_reverse_apply_inorder( + zone->nsec3_nodes, knot_zone_tree_apply, &f); +} + +/*----------------------------------------------------------------------------*/ + +knot_zone_tree_t *knot_zone_contents_get_nodes( + knot_zone_contents_t *contents) +{ + return contents->nodes; +} + +/*----------------------------------------------------------------------------*/ + +knot_zone_tree_t *knot_zone_contents_get_nsec3_nodes( + knot_zone_contents_t *contents) +{ + return contents->nsec3_nodes; +} + +/*----------------------------------------------------------------------------*/ + +ck_hash_table_t *knot_zone_contents_get_hash_table( + knot_zone_contents_t *contents) +{ + return contents->table; +} + +/*----------------------------------------------------------------------------*/ + +int knot_zone_contents_dname_table_apply(knot_zone_contents_t *contents, + void (*function)(knot_dname_t *, + void *), + void *data) +{ + if (contents == NULL || function == NULL) { + return KNOT_EBADARG; + } + + knot_dname_table_tree_inorder_apply(contents->dname_table, + function, data); + + return KNOT_EOK; +} + +/*----------------------------------------------------------------------------*/ + +int knot_zone_contents_shallow_copy(const knot_zone_contents_t *from, + knot_zone_contents_t **to) +{ + if (from == NULL || to == NULL) { + return KNOT_EBADARG; + } + + /* Copy to same destination as source. */ + if (from == *to) { + return KNOT_EBADARG; + } + + int ret = KNOT_EOK; + + knot_zone_contents_t *contents = (knot_zone_contents_t *)calloc( + 1, sizeof(knot_zone_contents_t)); + if (contents == NULL) { + ERR_ALLOC_FAILED; + return KNOT_ENOMEM; + } + + contents->apex = from->apex; + + contents->nodes = malloc(sizeof(knot_zone_tree_t)); + if (contents->nodes == NULL) { + ERR_ALLOC_FAILED; + ret = KNOT_ENOMEM; + goto cleanup; + } + + contents->nsec3_nodes = malloc(sizeof(knot_zone_tree_t)); + if (contents->nsec3_nodes == NULL) { + ERR_ALLOC_FAILED; + ret = KNOT_ENOMEM; + goto cleanup; + } + + if (from->dname_table != NULL) { + contents->dname_table = knot_dname_table_new(); + if (contents->dname_table == NULL) { + ERR_ALLOC_FAILED; + ret = KNOT_ENOMEM; + goto cleanup; + } + if ((ret = knot_dname_table_shallow_copy(from->dname_table, + contents->dname_table)) != KNOT_EOK) { + goto cleanup; + } + } else { + contents->dname_table = NULL; + } + + contents->node_count = from->node_count; + contents->generation = from->generation; + + contents->zone = from->zone; + + /* Initialize NSEC3 params */ + memcpy(&contents->nsec3_params, &from->nsec3_params, + sizeof(knot_nsec3_params_t)); + + if ((ret = knot_zone_tree_shallow_copy(from->nodes, + contents->nodes)) != KNOT_EOK + || (ret = knot_zone_tree_shallow_copy(from->nsec3_nodes, + contents->nsec3_nodes)) != KNOT_EOK) { + goto cleanup; + } + +#ifdef USE_HASH_TABLE + if (from->table != NULL) { +// ret = ck_copy_table(from->table, &contents->table); + ret = ck_shallow_copy(from->table, &contents->table); + if (ret != 0) { + dbg_zone("knot_zone_contents_shallow_copy: " + "hash table copied\n"); + ret = KNOT_ERROR; + goto cleanup; + } + } +#endif + + dbg_zone("knot_zone_contents_shallow_copy: " + "finished OK\n"); + + *to = contents; + return KNOT_EOK; + +cleanup: + knot_zone_tree_free(&contents->nodes); + knot_zone_tree_free(&contents->nsec3_nodes); + free(contents->dname_table); + free(contents); + return ret; +} + +/*----------------------------------------------------------------------------*/ + +void knot_zone_contents_free(knot_zone_contents_t **contents) +{ + if (contents == NULL || *contents == NULL) { + return; + } + + // free the zone tree, but only the structure + knot_zone_tree_free(&(*contents)->nodes); + knot_zone_tree_free(&(*contents)->nsec3_nodes); + +#ifdef USE_HASH_TABLE + if ((*contents)->table != NULL) { + ck_destroy_table(&(*contents)->table, NULL, 0); + } +#endif + knot_nsec3_params_free(&(*contents)->nsec3_params); + + knot_dname_table_free(&(*contents)->dname_table); + + free(*contents); + *contents = NULL; +} + +/*----------------------------------------------------------------------------*/ + +void knot_zone_contents_deep_free(knot_zone_contents_t **contents, + int destroy_dname_table) +{ + if (contents == NULL || *contents == NULL) { + return; + } + + if ((*contents) != NULL) { + +#ifdef USE_HASH_TABLE + if ((*contents)->table != NULL) { + ck_destroy_table(&(*contents)->table, NULL, 0); + } +#endif + /* has to go through zone twice, rdata may contain references to + node owners earlier in the zone which may be already freed */ + /* NSEC3 tree is deleted first as it may contain references to + the normal tree. */ + + knot_zone_tree_reverse_apply_postorder( + (*contents)->nsec3_nodes, + knot_zone_contents_destroy_node_rrsets_from_tree, + (void*)1); + + knot_zone_tree_reverse_apply_postorder( + (*contents)->nsec3_nodes, + knot_zone_contents_destroy_node_owner_from_tree, 0); + + knot_zone_tree_reverse_apply_postorder( + (*contents)->nodes, + knot_zone_contents_destroy_node_rrsets_from_tree, + (void*)1); + + knot_zone_tree_reverse_apply_postorder( + (*contents)->nodes, + knot_zone_contents_destroy_node_owner_from_tree, 0); + + // free the zone tree, but only the structure + // (nodes are already destroyed) + dbg_zone("Destroying zone tree.\n"); + knot_zone_tree_free(&(*contents)->nodes); + dbg_zone("Destroying NSEC3 zone tree.\n"); + knot_zone_tree_free(&(*contents)->nsec3_nodes); + + knot_nsec3_params_free(&(*contents)->nsec3_params); + + if (destroy_dname_table) { + /* + * Hack, used in zcompile - destroys the table using + * dname_free() instead of dname_retain(). + */ + knot_dname_table_destroy(&(*contents)->dname_table); + } else { + knot_dname_table_deep_free(&(*contents)->dname_table); + } + } + + free((*contents)); + *contents = NULL; +} + diff --git a/src/libknot/zone/zone-contents.h b/src/libknot/zone/zone-contents.h new file mode 100644 index 0000000..2856f76 --- /dev/null +++ b/src/libknot/zone/zone-contents.h @@ -0,0 +1,556 @@ +/*! + * \file zone-contents.h + * + * \author Lubos Slovak <lubos.slovak@nic.cz> + * + * \brief Zone contents structure and API for manipulating it. + * + * \addtogroup libknot + * @{ + */ +/* Copyright (C) 2011 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 <http://www.gnu.org/licenses/>. + */ + +#ifndef _KNOT_ZONE_CONTENTS_H_ +#define _KNOT_ZONE_CONTENTS_H_ + +//#include <time.h> + +#include "zone/node.h" +#include "dname.h" +#include "nsec3.h" +#include "zone/dname-table.h" +#include "common/tree.h" +#include "hash/cuckoo-hash-table.h" + +#include "zone-tree.h" + +struct knot_zone; + +/*----------------------------------------------------------------------------*/ + +typedef struct knot_zone_contents_t { + knot_node_t *apex; /*!< Apex node of the zone (holding SOA) */ + + ck_hash_table_t *table; /*!< Hash table for holding zone nodes. */ + knot_zone_tree_t *nodes; + knot_zone_tree_t *nsec3_nodes; + + /*! + * \todo Unify the use of this field - authoritative nodes vs. all. + */ + uint node_count; + + knot_dname_table_t *dname_table; + + knot_nsec3_params_t nsec3_params; + + /*! \brief Generation of the zone during update. + * + * Possible values: + * - 0 - Original version of the zone. Old nodes should be used. + * - 1 - New (updated) zone. New nodes should be used. + * - -1 - New (updated) zone, but exactly the stored nodes should be + * used, no matter their generation. + */ + short generation; + + struct knot_zone *zone; +} knot_zone_contents_t; + +/*----------------------------------------------------------------------------*/ + +knot_zone_contents_t *knot_zone_contents_new(knot_node_t *apex, + uint node_count, + int use_domain_table, + struct knot_zone *zone); + +time_t knot_zone_contents_version(const knot_zone_contents_t *contents); + +void knot_zone_contents_set_version(knot_zone_contents_t *contents, + time_t version); + +//short knot_zone_contents_generation(const knot_zone_contents_t *contents); + +int knot_zone_contents_gen_is_old(const knot_zone_contents_t *contents); +int knot_zone_contents_gen_is_new(const knot_zone_contents_t *contents); +int knot_zone_contents_gen_is_finished(const knot_zone_contents_t *contents); + +//void knot_zone_contents_switch_generation(knot_zone_contents_t *contents); + +void knot_zone_contents_set_gen_old(knot_zone_contents_t *contents); +void knot_zone_contents_set_gen_new(knot_zone_contents_t *contents); +void knot_zone_contents_set_gen_new_finished(knot_zone_contents_t *contents); + +uint16_t knot_zone_contents_class(const knot_zone_contents_t *contents); + +/*! + * \brief Adds a node to the given zone. + * + * Checks if the node belongs to the zone, i.e. if its owner is a subdomain of + * the zone's apex. It thus also forbids adding node with the same name as the + * zone apex. + * + * \warning This function may destroy domain names saved in the node, that + * are already present in the zone. + * + * \param zone Zone to add the node into. + * \param node Node to add into the zone. + * + * \retval KNOT_EOK + * \retval KNOT_EBADARG + * \retval KNOT_EBADZONE + * \retval KNOT_EHASH + */ +int knot_zone_contents_add_node(knot_zone_contents_t *contents, + knot_node_t *node, int create_parents, + uint8_t flags, int use_domain_table); + +/*! + * \brief Adds a RRSet to the given zone. + * + * Checks if the RRSet belongs to the zone, i.e. if its owner is a subdomain of + * the zone's apex. The RRSet is inserted only if the node is given, or if + * a node where the RRSet should belong is found in the zone. + * + * \warning The function does not check if the node is already inserted in the + * zone, just assumes that it is. + * \warning This function may destroy domain names saved in the RRSet, that + * are already present in the zone. + * + * \param zone Zone to add the node into. + * \param rrset RRSet to add into the zone. + * \param node Node the RRSet should be inserted into. (Should be a node of the + * given zone.) If set to NULL, the function will find proper node + * and set it to this parameter. + * + * \retval KNOT_EOK + * \retval KNOT_EBADARG + * \retval KNOT_EBADZONE + */ +int knot_zone_contents_add_rrset(knot_zone_contents_t *contents, + knot_rrset_t *rrset, + knot_node_t **node, + knot_rrset_dupl_handling_t dupl, + int use_domain_table); + +int knot_zone_contents_add_rrsigs(knot_zone_contents_t *contents, + knot_rrset_t *rrsigs, + knot_rrset_t **rrset, knot_node_t **node, + knot_rrset_dupl_handling_t dupl, + int use_domain_table); + +/*! + * \brief Adds a node holding NSEC3 records to the given zone. + * + * Checks if the node belongs to the zone, i.e. if its owner is a subdomain of + * the zone's apex. It does not check if the node really contains any NSEC3 + * records, nor if the name is a hash (as there is actually no way of + * determining this). + * + * \param zone Zone to add the node into. + * \param node Node to add into the zone. + * + * \retval KNOT_EOK + * \retval KNOT_EBADARG + * \retval KNOT_EBADZONE + */ +int knot_zone_contents_add_nsec3_node(knot_zone_contents_t *contents, + knot_node_t *node, int create_parents, + uint8_t flags, int use_domain_table); + +int knot_zone_contents_add_nsec3_rrset(knot_zone_contents_t *contents, + knot_rrset_t *rrset, + knot_node_t **node, + knot_rrset_dupl_handling_t dupl, + int use_domain_table); + +int knot_zone_contents_remove_node(knot_zone_contents_t *contents, + const knot_node_t *node, knot_zone_tree_node_t **removed_tree, + ck_hash_table_item_t **removed_hash); + +//knot_zone_tree_node_t *knot_zone_contents_remove_node( +// knot_zone_contents_t *contents, const knot_node_t *node); + +int knot_zone_contents_remove_nsec3_node(knot_zone_contents_t *contents, + const knot_node_t *node, knot_zone_tree_node_t **removed); + +/*! + * \warning Always call knot_zone_adjust_dnames() prior to calling this + * function. Otherwise the node count would not be set. + * + * \note Currently, all nodes (even non-authoritative) are inserted into the + * hash table. + */ +int knot_zone_contents_create_and_fill_hash_table( + knot_zone_contents_t *contents); + +/*! + * \brief Tries to find a node with the specified name in the zone. + * + * \param zone Zone where the name should be searched for. + * \param name Name to find. + * + * \return Corresponding node if found, NULL otherwise. + */ +knot_node_t *knot_zone_contents_get_node( + const knot_zone_contents_t *contents, const knot_dname_t *name); + +/*! + * \brief Tries to find a node with the specified name among the NSEC3 nodes + * of the zone. + * + * \param zone Zone where the name should be searched for. + * \param name Name to find. + * + * \return Corresponding node if found, NULL otherwise. + */ +knot_node_t *knot_zone_contents_get_nsec3_node( + const knot_zone_contents_t *contents, const knot_dname_t *name); + +/*! + * \brief Tries to find a node with the specified name in the zone. + * + * \note This function is identical to knot_zone_contents_get_node(), only it returns + * constant reference. + * + * \param zone Zone where the name should be searched for. + * \param name Name to find. + * + * \return Corresponding node if found, NULL otherwise. + */ +const knot_node_t *knot_zone_contents_find_node( + const knot_zone_contents_t *contents, const knot_dname_t *name); + +/*! + * \brief Tries to find domain name in the given zone using AVL tree. + * + * \param[in] zone Zone to search for the name. + * \param[in] name Domain name to search for. + * \param[out] node The found node (if it was found, otherwise it may contain + * arbitrary node). + * \param[out] closest_encloser Closest encloser of the given name in the zone. + * \param[out] previous Previous domain name in canonical order. + * + * \retval KNOT_ZONE_NAME_FOUND if node with owner \a name was found. + * \retval KNOT_ZONE_NAME_NOT_FOUND if it was not found. + * \retval KNOT_EBADARG + * \retval KNOT_EBADZONE + */ +int knot_zone_contents_find_dname(const knot_zone_contents_t *contents, + const knot_dname_t *name, + const knot_node_t **node, + const knot_node_t **closest_encloser, + const knot_node_t **previous); + +/*! + * \brief Finds previous name in canonical order to the given name in the zone. + * + * \param zone Zone to search for the name. + * \param name Domain name to find the previous domain name of. + * + * \return Previous node in canonical order, or NULL if some parameter is wrong. + */ +const knot_node_t *knot_zone_contents_find_previous( + const knot_zone_contents_t *contents, const knot_dname_t *name); + +knot_node_t *knot_zone_contents_get_previous( + const knot_zone_contents_t *contents, const knot_dname_t *name); + +const knot_node_t *knot_zone_contents_find_previous_nsec3( + const knot_zone_contents_t *contents, const knot_dname_t *name); + +knot_node_t *knot_zone_contents_get_previous_nsec3( + const knot_zone_contents_t *contents, const knot_dname_t *name); + +#ifdef USE_HASH_TABLE +/*! + * \brief Tries to find domain name in the given zone using the hash table. + * + * \param[in] zone Zone to search for the name. + * \param[in] name Domain name to search for. + * \param[out] node The found node (if it was found, otherwise it may contain + * arbitrary node). + * \param[out] closest_encloser Closest encloser of the given name in the zone. + * \param[out] previous Previous domain name in canonical order. + * + * \retval KNOT_ZONE_NAME_FOUND if node with owner \a name was found. + * \retval KNOT_ZONE_NAME_NOT_FOUND if it was not found. + * \retval KNOT_EBADARG + * \retval KNOT_EBADZONE + */ +int knot_zone_contents_find_dname_hash(const knot_zone_contents_t *contents, + const knot_dname_t *name, + const knot_node_t **node, + const knot_node_t **closest_encloser); +#endif + +/*! + * \brief Tries to find a node with the specified name among the NSEC3 nodes + * of the zone. + * + * \note This function is identical to knot_zone_contents_get_nsec3_node(), only it + * returns constant reference. + * + * \param zone Zone where the name should be searched for. + * \param name Name to find. + * + * \return Corresponding node if found, NULL otherwise. + */ +const knot_node_t *knot_zone_contents_find_nsec3_node( + const knot_zone_contents_t *contents, const knot_dname_t *name); + +/*! + * \brief Finds NSEC3 node and previous NSEC3 node in canonical order, + * corresponding to the given domain name. + * + * This functions creates a NSEC3 hash of \a name and tries to find NSEC3 node + * with the hashed domain name as owner. + * + * \param[in] zone Zone to search in. + * \param[in] name Domain name to get the corresponding NSEC3 nodes for. + * \param[out] nsec3_node NSEC3 node corresponding to \a name (if found, + * otherwise this may be an arbitrary NSEC3 node). + * \param[out] nsec3_previous The NSEC3 node immediately preceding hashed domain + * name corresponding to \a name in canonical order. + * + * \retval KNOT_ZONE_NAME_FOUND if the corresponding NSEC3 node was found. + * \retval KNOT_ZONE_NAME_NOT_FOUND if it was not found. + * \retval KNOT_EBADARG + * \retval KNOT_ENSEC3PAR + * \retval KNOT_ECRYPTO + * \retval KNOT_ERROR + */ +int knot_zone_contents_find_nsec3_for_name( + const knot_zone_contents_t *contents, + const knot_dname_t *name, + const knot_node_t **nsec3_node, + const knot_node_t **nsec3_previous, + int check_ver); +/*! + * \brief Returns the apex node of the zone. + * + * \param zone Zone to get the apex of. + * + * \return Zone apex node. + */ +const knot_node_t *knot_zone_contents_apex( + const knot_zone_contents_t *contents); + +knot_node_t *knot_zone_contents_get_apex( + const knot_zone_contents_t *contents); + +//knot_dname_t *knot_zone_contents_name( +// const knot_zone_contents_t *contents); + +/*! + * \brief Optimizes zone by replacing domain names in RDATA with references to + * domain names present in zone (as node owners). + * + * \param zone Zone to adjust domain names in. + */ +int knot_zone_contents_adjust(knot_zone_contents_t *contents, int check_ver); + +/*! + * \brief Parses the NSEC3PARAM record stored in the zone. + * + * This function properly fills in the nsec3_params field of the zone structure + * according to data stored in the NSEC3PARAM record. This is necessary to do + * before any NSEC3 operations on the zone are requested, otherwise they will + * fail (error KNOT_ENSEC3PAR). + * + * \note If there is no NSEC3PARAM record in the zone, this function clears + * the nsec3_params field of the zone structure (fills it with zeros). + * + * \param zone Zone to get the NSEC3PARAM record from. + */ +int knot_zone_contents_load_nsec3param(knot_zone_contents_t *contents); + +/*! + * \brief Checks if the zone uses NSEC3. + * + * This function will return 0 if the NSEC3PARAM record was not parse prior to + * calling it. + * + * \param zone Zone to check. + * + * \retval <> 0 if the zone uses NSEC3. + * \retval 0 if it does not. + * + * \see knot_zone_contents_load_nsec3param() + */ +int knot_zone_contents_nsec3_enabled(const knot_zone_contents_t *contents); + +/*! + * \brief Returns the parsed NSEC3PARAM record of the zone. + * + * \note You must parse the NSEC3PARAM record prior to calling this function + * (knot_zone_contents_load_nsec3param()). + * + * \param zone Zone to get the NSEC3PARAM record from. + * + * \return Parsed NSEC3PARAM from the zone or NULL if the zone does not use + * NSEC3 or the record was not parsed before. + * + * \see knot_zone_contents_load_nsec3param() + */ +const knot_nsec3_params_t *knot_zone_contents_nsec3params( + const knot_zone_contents_t *contents); + +/*! + * \brief Applies the given function to each regular node in the zone. + * + * This function uses post-order depth-first forward traversal, i.e. the + * function is first recursively applied to subtrees and then to the root. + * + * \param zone Nodes of this zone will be used as parameters for the function. + * \param function Function to be applied to each node of the zone. + * \param data Arbitrary data to be passed to the function. + */ +int knot_zone_contents_tree_apply_postorder(knot_zone_contents_t *contents, + void (*function)(knot_node_t *node, void *data), + void *data); + +/*! + * \brief Applies the given function to each regular node in the zone. + * + * This function uses in-order depth-first forward traversal, i.e. the function + * is first recursively applied to left subtree, then to the root and then to + * the right subtree. + * + * \note This implies that the zone is stored in a binary tree. Is there a way + * to make this traversal independent on the underlying structure? + * + * \param zone Nodes of this zone will be used as parameters for the function. + * \param function Function to be applied to each node of the zone. + * \param data Arbitrary data to be passed to the function. + */ +int knot_zone_contents_tree_apply_inorder(knot_zone_contents_t *contents, + void (*function)(knot_node_t *node, void *data), + void *data); + +/*! + * \brief Applies the given function to each regular node in the zone. + * + * This function uses in-order depth-first reverse traversal, i.e. the function + * is first recursively applied to right subtree, then to the root and then to + * the left subtree. + * + * \note This implies that the zone is stored in a binary tree. Is there a way + * to make this traversal independent on the underlying structure? + * + * \param zone Nodes of this zone will be used as parameters for the function. + * \param function Function to be applied to each node of the zone. + * \param data Arbitrary data to be passed to the function. + */ +int knot_zone_contents_tree_apply_inorder_reverse( + knot_zone_contents_t *contents, + void (*function)(knot_node_t *node, void *data), void *data); + +/*! + * \brief Applies the given function to each NSEC3 node in the zone. + * + * This function uses post-order depth-first forward traversal, i.e. the + * function is first recursively applied to subtrees and then to the root. + * + * \param zone NSEC3 nodes of this zone will be used as parameters for the + * function. + * \param function Function to be applied to each node of the zone. + * \param data Arbitrary data to be passed to the function. + */ +int knot_zone_contents_nsec3_apply_postorder(knot_zone_contents_t *contents, + void (*function)(knot_node_t *node, void *data), + void *data); + +/*! + * \brief Applies the given function to each NSEC3 node in the zone. + * + * This function uses in-order depth-first forward traversal, i.e. the function + * is first recursively applied to left subtree, then to the root and then to + * the right subtree. + * + * \note This implies that the zone is stored in a binary tree. Is there a way + * to make this traversal independent on the underlying structure? + * + * \param zone NSEC3 nodes of this zone will be used as parameters for the + * function. + * \param function Function to be applied to each node of the zone. + * \param data Arbitrary data to be passed to the function. + */ +int knot_zone_contents_nsec3_apply_inorder(knot_zone_contents_t *contents, + void (*function)(knot_node_t *node, void *data), + void *data); + +/*! + * \brief Applies the given function to each NSEC3 node in the zone. + * + * This function uses in-order depth-first reverse traversal, i.e. the function + * is first recursively applied to right subtree, then to the root and then to + * the left subtree. + * + * \note This implies that the zone is stored in a binary tree. Is there a way + * to make this traversal independent on the underlying structure? + * + * \param zone NSEC3 nodes of this zone will be used as parameters for the + * function. + * \param function Function to be applied to each node of the zone. + * \param data Arbitrary data to be passed to the function. + */ +int knot_zone_contents_nsec3_apply_inorder_reverse( + knot_zone_contents_t *contents, + void (*function)(knot_node_t *node, void *data), void *data); + +knot_zone_tree_t *knot_zone_contents_get_nodes( + knot_zone_contents_t *contents); + +knot_zone_tree_t *knot_zone_contents_get_nsec3_nodes( + knot_zone_contents_t *contents); + +ck_hash_table_t *knot_zone_contents_get_hash_table( + knot_zone_contents_t *contents); + +int knot_zone_contents_dname_table_apply(knot_zone_contents_t *contents, + void (*function)(knot_dname_t *, + void *), + void *data); + +/*! + * \brief Creates a shallow copy of the zone (no stored data are copied). + * + * This function creates a new zone structure in \a to, creates new trees for + * regular nodes and for NSEC3 nodes, creates new hash table and a new domain + * table. It also fills these structures with the exact same data as the + * original zone is - no copying of stored data is done, just pointers are + * copied. + * + * \param from Original zone. + * \param to Copy of the zone. + * + * \retval KNOT_EOK + * \retval KNOT_EBADARG + * \retval KNOT_ENOMEM + */ +int knot_zone_contents_shallow_copy(const knot_zone_contents_t *from, + knot_zone_contents_t **to); + +void knot_zone_contents_free(knot_zone_contents_t **contents); + +void knot_zone_contents_deep_free(knot_zone_contents_t **contents, + int destroy_dname_table); + +#endif + +/*! @} */ diff --git a/src/libknot/zone/zone-tree.c b/src/libknot/zone/zone-tree.c new file mode 100644 index 0000000..cdf128e --- /dev/null +++ b/src/libknot/zone/zone-tree.c @@ -0,0 +1,470 @@ +/* Copyright (C) 2011 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 <http://www.gnu.org/licenses/>. + */ + +#include <assert.h> +#include <stdlib.h> +#include <stdio.h> + +#include "zone-tree.h" +#include "zone/node.h" +#include "util/error.h" + +/*----------------------------------------------------------------------------*/ +/* Non-API functions */ +/*----------------------------------------------------------------------------*/ + +// AVL tree functions +TREE_DEFINE(knot_zone_tree_node, avl); + +/*----------------------------------------------------------------------------*/ + +static int knot_zone_tree_node_compare(knot_zone_tree_node_t *node1, + knot_zone_tree_node_t *node2) +{ + assert(node1 != NULL); + assert(node2 != NULL); + assert(node1->node != NULL); + assert(node2->node != NULL); + assert(knot_node_owner(node1->node) != NULL); + assert(knot_node_owner(node2->node) != NULL); + + return knot_node_compare(node1->node, node2->node); +} + +/*----------------------------------------------------------------------------*/ + +static void knot_zone_tree_delete_subtree(knot_zone_tree_node_t *root) +{ + if (root == NULL) { + return; + } + + knot_zone_tree_delete_subtree(root->avl.avl_left); + knot_zone_tree_delete_subtree(root->avl.avl_right); + free(root); +} + +/*----------------------------------------------------------------------------*/ + +static int knot_zone_tree_copy_node(knot_zone_tree_node_t *from, + knot_zone_tree_node_t **to) +{ + if (from == NULL) { + *to = NULL; + return KNOT_EOK; + } + + *to = (knot_zone_tree_node_t *) + malloc(sizeof(knot_zone_tree_node_t)); + if (*to == NULL) { + return KNOT_ENOMEM; + } + + (*to)->node = from->node; + (*to)->avl.avl_height = from->avl.avl_height; + + int ret = knot_zone_tree_copy_node(from->avl.avl_left, + &(*to)->avl.avl_left); + if (ret != KNOT_EOK) { + return ret; + } + + ret = knot_zone_tree_copy_node(from->avl.avl_right, + &(*to)->avl.avl_right); + if (ret != KNOT_EOK) { + knot_zone_tree_delete_subtree((*to)->avl.avl_left); + (*to)->avl.avl_left = NULL; + return ret; + } + + return KNOT_EOK; +} + +/*----------------------------------------------------------------------------*/ + +static void knot_zone_tree_free_node(knot_zone_tree_node_t *node, + int free_data, int free_owner) +{ + if (node == NULL) { + return; + } + + knot_zone_tree_free_node(node->avl.avl_left, free_data, free_owner); + + knot_zone_tree_free_node(node->avl.avl_right, free_data, free_owner); + + if (free_data) { + knot_node_free(&node->node, free_owner, 0); + } + + free(node); +} + +/*----------------------------------------------------------------------------*/ +/* API functions */ +/*----------------------------------------------------------------------------*/ + +int knot_zone_tree_init(knot_zone_tree_t *tree) +{ + if (tree == NULL) { + return KNOT_EBADARG; + } + + TREE_INIT(tree, knot_zone_tree_node_compare); + return KNOT_EOK; +} + +/*----------------------------------------------------------------------------*/ + +int knot_zone_tree_insert(knot_zone_tree_t *tree, knot_node_t *node) +{ + if (tree == NULL || node == NULL) { + return KNOT_EBADARG; + } + + knot_zone_tree_node_t *znode = (knot_zone_tree_node_t *)malloc( + sizeof(knot_zone_tree_node_t)); + if (znode == NULL) { + return KNOT_ENOMEM; + } + + znode->node = node; + znode->avl.avl_left = NULL; + znode->avl.avl_right = NULL; + znode->avl.avl_height = 0; + + /*! \todo How to know if this was successful? */ + TREE_INSERT(tree, knot_zone_tree_node, avl, znode); + + return KNOT_EOK; +} + +/*----------------------------------------------------------------------------*/ + +int knot_zone_tree_find(knot_zone_tree_t *tree, const knot_dname_t *owner, + const knot_node_t **found) +{ + if (tree == NULL || owner == NULL || found == NULL) { + return KNOT_EBADARG; + } + + knot_node_t *f = NULL; + int ret = knot_zone_tree_get(tree, owner, &f); + *found = f; + return ret; +} + +/*----------------------------------------------------------------------------*/ + +int knot_zone_tree_get(knot_zone_tree_t *tree, const knot_dname_t *owner, + knot_node_t **found) +{ + if (tree == NULL || owner == NULL) { + return KNOT_EBADARG; + } + + *found = NULL; + + // create dummy node to use for lookup + knot_zone_tree_node_t *tmp = (knot_zone_tree_node_t *)malloc( + sizeof(knot_zone_tree_node_t)); + if (tmp == NULL) { + return KNOT_ENOMEM; + } + + // create dummy data node to use for lookup + knot_node_t *tmp_data = knot_node_new( + (knot_dname_t *)owner, NULL, 0); + if (tmp_data == NULL) { + free(tmp); + return KNOT_ENOMEM; + } + tmp->node = tmp_data; + + knot_zone_tree_node_t *n = TREE_FIND(tree, knot_zone_tree_node, avl, + tmp); + + knot_node_free(&tmp_data, 0, 0); + free(tmp); + + if (n != NULL) { + *found = n->node; + } + + return KNOT_EOK; +} + +/*----------------------------------------------------------------------------*/ + +int knot_zone_tree_find_less_or_equal(knot_zone_tree_t *tree, + const knot_dname_t *owner, + const knot_node_t **found, + const knot_node_t **previous, + int check_version) +{ + if (tree == NULL || owner == NULL || found == NULL || previous == NULL) { + return KNOT_EBADARG; + } + + knot_node_t *f, *p; + int ret = knot_zone_tree_get_less_or_equal(tree, owner, &f, &p, check_version); + + *found = f; + *previous = p; + + return ret; +} + +/*----------------------------------------------------------------------------*/ + +int knot_zone_tree_get_less_or_equal(knot_zone_tree_t *tree, + const knot_dname_t *owner, + knot_node_t **found, + knot_node_t **previous, + int check_version) +{ + if (tree == NULL || owner == NULL || found == NULL + || previous == NULL) { + return KNOT_EBADARG; + } + + knot_zone_tree_node_t *f = NULL, *prev = NULL; + + // create dummy node to use for lookup + knot_zone_tree_node_t *tmp = (knot_zone_tree_node_t *)malloc( + sizeof(knot_zone_tree_node_t)); + if (tmp == NULL) { + return KNOT_ENOMEM; + } + + // create dummy data node to use for lookup + knot_node_t *tmp_data = knot_node_new( + (knot_dname_t *)owner, NULL, 0); + if (tmp_data == NULL) { + free(tmp); + return KNOT_ENOMEM; + } + tmp->node = tmp_data; + + int exact_match = TREE_FIND_LESS_EQUAL( + tree, knot_zone_tree_node, avl, tmp, &f, &prev); + + knot_node_free(&tmp_data, 0, 0); + free(tmp); + + *found = (exact_match > 0) ? f->node : NULL; + + if (exact_match < 0) { + // previous is not really previous but should be the leftmost + // node in the tree; take it's previous + assert(prev != NULL); + *previous = knot_node_get_previous(prev->node, check_version); + exact_match = 0; + } else if (prev == NULL) { + if (!exact_match) { + printf("Searched for owner %s in zone tree.\n", + knot_dname_to_str(owner)); + printf("Exact match: %d\n", exact_match); + printf("Found node: %p: %s.\n", f, (f) + ? knot_dname_to_str(knot_node_owner(f->node)) + : "none"); + printf("Previous node: %p: %s.\n", prev, (prev) + ? knot_dname_to_str(knot_node_owner(prev->node)) + : "none"); + } + + // either the returned node is the root of the tree, or + // it is the leftmost node in the tree; in both cases + // node was found set the previous node of the found + // node + assert(exact_match > 0); + assert(f != NULL); + *previous = knot_node_get_previous(f->node, check_version); + } else { + // otherwise check if the previous node is not an empty + // non-terminal + /*! \todo Here we assume that the 'prev' pointer always points + * to an empty non-terminal. + */ + *previous = (knot_node_rrset_count(prev->node) == 0) + ? knot_node_get_previous(prev->node, check_version) + : prev->node; + } + + assert(exact_match >= 0); + + return exact_match; +} + +/*----------------------------------------------------------------------------*/ + +int knot_zone_tree_remove(knot_zone_tree_t *tree, + const knot_dname_t *owner, + knot_zone_tree_node_t **removed) +{ + if (tree == NULL || owner == NULL || removed == NULL) { + return KNOT_EBADARG; + } + + // create dummy node to use for lookup + knot_zone_tree_node_t *tmp = (knot_zone_tree_node_t *)malloc( + sizeof(knot_zone_tree_node_t)); + if (tmp == NULL) { + return KNOT_ENOMEM; + } + + // create dummy data node to use for lookup + knot_node_t *tmp_data = knot_node_new( + (knot_dname_t *)owner, NULL, 0); + if (tmp_data == NULL) { + free(tmp); + return KNOT_ENOMEM; + } + tmp->node = tmp_data; + + // we must first find the node, so that it may be destroyed + knot_zone_tree_node_t *n = TREE_FIND(tree, knot_zone_tree_node, avl, + tmp); + + /*! \todo How to know if this was successful? */ + TREE_REMOVE(tree, knot_zone_tree_node, avl, tmp); + + knot_node_free(&tmp_data, 0, 0); + free(tmp); + +// *removed = (n) ? n->node : NULL; +// free(n); + *removed = n; + + return KNOT_EOK; +} + +/*----------------------------------------------------------------------------*/ + +int knot_zone_tree_forward_apply_inorder(knot_zone_tree_t *tree, + void (*function)( + knot_zone_tree_node_t *node, + void *data), + void *data) +{ + if (tree == NULL || function == NULL) { + return KNOT_EBADARG; + } + + TREE_FORWARD_APPLY(tree, knot_zone_tree_node, avl, + function, data); + + return KNOT_EOK; +} + +/*----------------------------------------------------------------------------*/ + +int knot_zone_tree_forward_apply_postorder(knot_zone_tree_t *tree, + void (*function)( + knot_zone_tree_node_t *node, + void *data), + void *data) +{ + if (tree == NULL || function == NULL) { + return KNOT_EBADARG; + } + + TREE_POST_ORDER_APPLY(tree, knot_zone_tree_node, avl, + function, data); + + return KNOT_EOK; +} + +/*----------------------------------------------------------------------------*/ + +int knot_zone_tree_reverse_apply_inorder(knot_zone_tree_t *tree, + void (*function)( + knot_zone_tree_node_t *node, + void *data), + void *data) +{ + if (tree == NULL || function == NULL) { + return KNOT_EBADARG; + } + + TREE_REVERSE_APPLY(tree, knot_zone_tree_node, avl, + function, data); + + return KNOT_EOK; +} + +/*----------------------------------------------------------------------------*/ + +int knot_zone_tree_reverse_apply_postorder(knot_zone_tree_t *tree, + void (*function)( + knot_zone_tree_node_t *node, + void *data), + void *data) +{ + if (tree == NULL || function == NULL) { + return KNOT_EBADARG; + } + + TREE_REVERSE_APPLY_POST(tree, knot_zone_tree_node, avl, + function, data); + + return KNOT_EOK; +} + +/*----------------------------------------------------------------------------*/ + +int knot_zone_tree_shallow_copy(knot_zone_tree_t *from, + knot_zone_tree_t *to) +{ + if (to == NULL || from == NULL) { + return KNOT_EBADARG; + } + /* + * This function will copy the tree by hand, so that the nodes + * do not have to be inserted the normal way. It should be substantially + * faster. + */ + + to->th_cmp = from->th_cmp; + + return knot_zone_tree_copy_node(from->th_root, &to->th_root); +} + +/*----------------------------------------------------------------------------*/ + +void knot_zone_tree_free(knot_zone_tree_t **tree) +{ + if (tree == NULL || *tree == NULL) { + return; + } + knot_zone_tree_free_node((*tree)->th_root, 0, 0); + free(*tree); + *tree = NULL; +} + +/*----------------------------------------------------------------------------*/ + +void knot_zone_tree_deep_free(knot_zone_tree_t **tree, int free_owners) +{ + if (tree == NULL || *tree == NULL) { + return; + } + knot_zone_tree_free_node((*tree)->th_root, 1, free_owners); + free(*tree); + *tree = NULL; +} + +/*----------------------------------------------------------------------------*/ diff --git a/src/libknot/zone/zone-tree.h b/src/libknot/zone/zone-tree.h new file mode 100644 index 0000000..0971749 --- /dev/null +++ b/src/libknot/zone/zone-tree.h @@ -0,0 +1,300 @@ +/*! + * \file zone-tree.h + * + * \author Lubos Slovak <lubos.slovak@nic.cz> + * + * \brief Zone tree structure and API for manipulating it. + * + * Implemented as AVL tree. + * + * \addtogroup libknot + * @{ + */ +/* Copyright (C) 2011 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 <http://www.gnu.org/licenses/>. + */ + +#ifndef _KNOT_ZONE_TREE_H_ +#define _KNOT_ZONE_TREE_H_ + +#include "common/tree.h" +#include "zone/node.h" + +/*----------------------------------------------------------------------------*/ + +typedef struct knot_zone_tree_node { + /*! \brief Structure for connecting this node to an AVL tree. */ + TREE_ENTRY(knot_zone_tree_node) avl; + /*! \brief Zone tree data. */ + knot_node_t *node; + /*! \brief Owner of the node. */ +// knot_dname_t *owner; +} knot_zone_tree_node_t; + +/*----------------------------------------------------------------------------*/ + +typedef TREE_HEAD(knot_zone_tree, knot_zone_tree_node) knot_zone_tree_t; + +/*----------------------------------------------------------------------------*/ +/*! + * \brief Initializes the zone tree. + * + * Does not allocate the structure. Must be called before any use of the tree. + * + * \param tree Zone tree structure to initialize. + * + * \retval KNOT_EOK + * \retval KNOT_EBADARG + */ +int knot_zone_tree_init(knot_zone_tree_t *tree); + +/*! + * \brief Inserts the given node into the zone tree. + * + * \param tree Zone tree to insert the node into. + * \param node Node to insert. + * + * \retval KNOT_EOK + * \retval KNOT_EBADARG + * \retval KNOT_ENOMEM + */ +int knot_zone_tree_insert(knot_zone_tree_t *tree, knot_node_t *node); + +/*! + * \brief Finds node with the given owner in the zone tree. + * + * \param tree Zone tree to search in. + * \param owner Owner of the node to find. + * + * \retval KNOT_EOK + * \retval KNOT_EBADARG + * \retval KNOT_ENOMEM + */ +int knot_zone_tree_find(knot_zone_tree_t *tree, + const knot_dname_t *owner, + const knot_node_t **found); + +/*! + * \brief Finds node with the given owner in the zone tree. + * + * \note This function is identical to knot_zone_tree_find() except that it + * returns non-const node. + * + * \param tree Zone tree to search in. + * \param owner Owner of the node to find. + * + * \retval KNOT_EOK + * \retval KNOT_EBADARG + * \retval KNOT_ENOMEM + */ +int knot_zone_tree_get(knot_zone_tree_t *tree, + const knot_dname_t *owner, + knot_node_t **found); + +/*! + * \brief Tries to find the given domain name in the zone tree and returns the + * associated node and previous node in canonical order. + * + * \param zone Zone to search in. + * \param owner Owner of the node to find. + * \param found Found node. + * \param previous Previous node in canonical order (i.e. the one directly + * preceding \a owner in canonical order, regardless if the name + * is in the zone or not). + * + * \retval > 0 if the domain name was found. In such case \a found holds the + * zone node with \a owner as its owner. + * \a previous is set properly. + * \retval 0 if the domain name was not found. \a found may hold any (or none) + * node. \a previous is set properly. + * \retval KNOT_EBADARG + * \retval KNOT_ENOMEM + */ +int knot_zone_tree_find_less_or_equal(knot_zone_tree_t *tree, + const knot_dname_t *owner, + const knot_node_t **found, + const knot_node_t **previous, + int check_version); + +/*! + * \brief Tries to find the given domain name in the zone tree and returns the + * associated node and previous node in canonical order. + * + * \note This function is identical to knot_zone_tree_find_less_or_equal() + * except that it returns non-const nodes. + * + * \param zone Zone to search in. + * \param owner Owner of the node to find. + * \param found Found node. + * \param previous Previous node in canonical order (i.e. the one directly + * preceding \a owner in canonical order, regardless if the name + * is in the zone or not). + * + * \retval > 0 if the domain name was found. In such case \a found holds the + * zone node with \a owner as its owner. + * \a previous is set properly. + * \retval 0 if the domain name was not found. \a found may hold any (or none) + * node. \a previous is set properly. + * \retval KNOT_EBADARG + * \retval KNOT_ENOMEM + */ +int knot_zone_tree_get_less_or_equal(knot_zone_tree_t *tree, + const knot_dname_t *owner, + knot_node_t **found, + knot_node_t **previous, + int check_version); + +/*! + * \brief Removes node with the given owner from the zone tree and returns it. + * + * \param tree Zone tree to remove the node from. + * \param owner Owner of the node to find. + * \param removed The removed node. + * + * \retval The removed node. + */ +int knot_zone_tree_remove(knot_zone_tree_t *tree, + const knot_dname_t *owner, + knot_zone_tree_node_t **removed); + +/*! + * \brief Applies the given function to each node in the zone. + * + * This function uses in-order depth-first forward traversal, i.e. the function + * is first recursively applied to left subtree, then to the root and then to + * the right subtree. + * + * \note This implies that the zone is stored in a binary tree. Is there a way + * to make this traversal independent on the underlying structure? + * + * \param tree Zone tree to apply the function to. + * \param function Function to be applied to each node of the zone. + * \param data Arbitrary data to be passed to the function. + * + * \retval KNOT_EOK + * \retval KNOT_EBADARG + */ +int knot_zone_tree_forward_apply_inorder(knot_zone_tree_t *tree, + void (*function)( + knot_zone_tree_node_t *node, + void *data), + void *data); + +/*! + * \brief Applies the given function to each node in the zone. + * + * This function uses post-order depth-first forward traversal, i.e. the + * function is first recursively applied to subtrees and then to the root. + * + * \note This implies that the zone is stored in a binary tree. Is there a way + * to make this traversal independent on the underlying structure? + * + * \param tree Zone tree to apply the function to. + * \param function Function to be applied to each node of the zone. + * \param data Arbitrary data to be passed to the function. + * + * \retval KNOT_EOK + * \retval KNOT_EBADARG + */ +int knot_zone_tree_forward_apply_postorder(knot_zone_tree_t *tree, + void (*function)( + knot_zone_tree_node_t *node, + void *data), + void *data); + +/*! + * \brief Applies the given function to each node in the zone. + * + * This function uses in-order depth-first reverse traversal, i.e. the function + * is first recursively applied to right subtree, then to the root and then to + * the left subtree. + * + * \note This implies that the zone is stored in a binary tree. Is there a way + * to make this traversal independent on the underlying structure? + * + * \param tree Zone tree to apply the function to. + * \param function Function to be applied to each node of the zone. + * \param data Arbitrary data to be passed to the function. + * + * \retval KNOT_EOK + * \retval KNOT_EBADARG + */ +int knot_zone_tree_reverse_apply_inorder(knot_zone_tree_t *tree, + void (*function)( + knot_zone_tree_node_t *node, + void *data), + void *data); + +/*! + * \brief Applies the given function to each node in the zone. + * + * This function uses post-order depth-first reverse traversal, i.e. the + * function is first recursively applied to right subtree, then to the + * left subtree and then to the root. + * + * \note This implies that the zone is stored in a binary tree. Is there a way + * to make this traversal independent on the underlying structure? + * + * \param tree Zone tree to apply the function to. + * \param function Function to be applied to each node of the zone. + * \param data Arbitrary data to be passed to the function. + * + * \retval KNOT_EOK + * \retval KNOT_EBADARG + */ +int knot_zone_tree_reverse_apply_postorder(knot_zone_tree_t *tree, + void (*function)( + knot_zone_tree_node_t *node, + void *data), + void *data); + +/*! + * \brief Copies the whole zone tree structure (but not the data contained + * within). + * + * \warning This function does not check if the target zone tree is empty, + * it just replaces the root pointer. + * + * \param from Original zone tree. + * \param to Zone tree to copy the original one into. + * + * \retval KNOT_EOK + * \retval KNOT_ENOMEM + */ +int knot_zone_tree_shallow_copy(knot_zone_tree_t *from, + knot_zone_tree_t *to); + +/*! + * \brief Destroys the zone tree, not touching the saved data. + * + * \param tree Zone tree to be destroyed. + */ +void knot_zone_tree_free(knot_zone_tree_t **tree); + +/*! + * \brief Destroys the zone tree, together with the saved data. + * + * \param tree Zone tree to be destroyed. + * \param free_owners Set to <> 0 if owners of the nodes should be destroyed + * as well. Set to 0 otherwise. + */ +void knot_zone_tree_deep_free(knot_zone_tree_t **tree, int free_owners); + +/*----------------------------------------------------------------------------*/ + +#endif // _KNOT_ZONE_TREE_H_ + +/*! @} */ + diff --git a/src/libknot/zone/zone.c b/src/libknot/zone/zone.c new file mode 100644 index 0000000..9de1a53 --- /dev/null +++ b/src/libknot/zone/zone.c @@ -0,0 +1,246 @@ +/* Copyright (C) 2011 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 <http://www.gnu.org/licenses/>. + */ + +#include <config.h> +#include <stdlib.h> +#include <assert.h> +#include <string.h> + +#include <urcu.h> + +#include "common.h" +#include "zone/zone.h" +#include "zone/node.h" +#include "dname.h" +#include "consts.h" +#include "util/descriptor.h" +#include "nsec3.h" +#include "util/error.h" +#include "util/debug.h" +#include "util/utils.h" +#include "common/tree.h" +#include "common/base32hex.h" +#include "hash/cuckoo-hash-table.h" +#include "zone/zone-contents.h" + +/*----------------------------------------------------------------------------*/ +/* API functions */ +/*----------------------------------------------------------------------------*/ + +knot_zone_t *knot_zone_new_empty(knot_dname_t *name) +{ + if (!name) { + return 0; + } + + dbg_zone("Creating new zone!\n"); + + knot_zone_t *zone = malloc(sizeof(knot_zone_t)); + if (zone == NULL) { + ERR_ALLOC_FAILED; + return NULL; + } + memset(zone, 0, sizeof(knot_zone_t)); + + // save the zone name + dbg_zone("Setting zone name.\n"); + zone->name = name; + return zone; +} + +/*----------------------------------------------------------------------------*/ + +knot_zone_t *knot_zone_new(knot_node_t *apex, uint node_count, + int use_domain_table) +{ + knot_zone_t *zone = knot_zone_new_empty( + knot_dname_deep_copy(knot_node_owner(apex))); + if (zone == NULL) { + return NULL; + } + + dbg_zone("Creating zone contents.\n"); + zone->contents = knot_zone_contents_new(apex, node_count, + use_domain_table, zone); + if (zone->contents == NULL) { + knot_dname_release(zone->name); + free(zone); + return NULL; + } + + zone->contents->zone = zone; + + return zone; +} + +/*----------------------------------------------------------------------------*/ + +knot_zone_contents_t *knot_zone_get_contents( + const knot_zone_t *zone) +{ + if (zone == NULL) { + return NULL; + } + + return rcu_dereference(zone->contents); +} + +/*----------------------------------------------------------------------------*/ + +const knot_zone_contents_t *knot_zone_contents( + const knot_zone_t *zone) +{ + if (zone == NULL) { + return NULL; + } + + return rcu_dereference(zone->contents); +} + +/*----------------------------------------------------------------------------*/ + +time_t knot_zone_version(const knot_zone_t *zone) +{ + if (zone == NULL) { + return KNOT_EBADARG; + } + + return zone->version; +} + +/*----------------------------------------------------------------------------*/ + +void knot_zone_set_version(knot_zone_t *zone, time_t version) +{ + if (zone == NULL) { + return; + } + + zone->version = version; +} + +/*----------------------------------------------------------------------------*/ + +short knot_zone_is_master(const knot_zone_t *zone) +{ + return zone->master; +} + +/*----------------------------------------------------------------------------*/ + +void knot_zone_set_master(knot_zone_t *zone, short master) +{ + zone->master = master; +} + +/*----------------------------------------------------------------------------*/ + +const void *knot_zone_data(const knot_zone_t *zone) +{ + return zone->data; +} + +/*----------------------------------------------------------------------------*/ + +void knot_zone_set_data(knot_zone_t *zone, void *data) +{ + zone->data = data; +} + +/*----------------------------------------------------------------------------*/ + +const knot_dname_t *knot_zone_name(const knot_zone_t *zone) +{ + return zone->name; +} + +/*----------------------------------------------------------------------------*/ + +knot_zone_contents_t *knot_zone_switch_contents(knot_zone_t *zone, + knot_zone_contents_t *new_contents) +{ + if (zone == NULL) { + return NULL; + } + + knot_zone_contents_t *old_contents = + rcu_xchg_pointer(&zone->contents, new_contents); + return old_contents; +} + +/*----------------------------------------------------------------------------*/ + +void knot_zone_free(knot_zone_t **zone) +{ + if (zone == NULL || *zone == NULL) { + return; + } + + dbg_zone("zone_free().\n"); + + if ((*zone)->contents + && !knot_zone_contents_gen_is_old((*zone)->contents)) { + // zone is in the middle of an update, report + dbg_zone("Destroying zone that is in the middle of an " + "update.\n"); + } + + knot_dname_release((*zone)->name); + + /* Call zone data destructor if exists. */ + if ((*zone)->dtor) { + (*zone)->dtor(*zone); + } + + knot_zone_contents_free(&(*zone)->contents); + free(*zone); + *zone = NULL; + + dbg_zone("Done.\n"); +} + +/*----------------------------------------------------------------------------*/ + +void knot_zone_deep_free(knot_zone_t **zone, int destroy_dname_table) +{ + if (zone == NULL || *zone == NULL) { + return; + } + + if ((*zone)->contents + && !knot_zone_contents_gen_is_old((*zone)->contents)) { + // zone is in the middle of an update, report + dbg_zone("Destroying zone that is in the middle of an " + "update.\n"); + } + +dbg_zone_exec( + char *name = knot_dname_to_str((*zone)->name); + dbg_zone("Destroying zone %p, name: %s.\n", *zone, name); + free(name); +); + + knot_dname_release((*zone)->name); + + /* Call zone data destructor if exists. */ + if ((*zone)->dtor) { + (*zone)->dtor(*zone); + } + + knot_zone_contents_deep_free(&(*zone)->contents, destroy_dname_table); + free(*zone); + *zone = NULL; +} diff --git a/src/libknot/zone/zone.h b/src/libknot/zone/zone.h new file mode 100644 index 0000000..331ef1f --- /dev/null +++ b/src/libknot/zone/zone.h @@ -0,0 +1,157 @@ +/*! + * \file zone.h + * + * \author Lubos Slovak <lubos.slovak@nic.cz> + * + * \brief Zone structure and API for manipulating it. + * + * \addtogroup libknot + * @{ + */ +/* Copyright (C) 2011 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 <http://www.gnu.org/licenses/>. + */ + +#ifndef _KNOT_ZONE_H_ +#define _KNOT_ZONE_H_ + +#include <time.h> + +#include "zone/node.h" +#include "dname.h" +#include "nsec3.h" +#include "zone/dname-table.h" +#include "common/tree.h" +#include "hash/cuckoo-hash-table.h" + +#include "zone-tree.h" + +#include "zone/zone-contents.h" + +/*----------------------------------------------------------------------------*/ + +//typedef TREE_HEAD(avl_tree, knot_node) avl_tree_t; +//struct event_t; + +/*----------------------------------------------------------------------------*/ +/*! + * \brief Return values for search functions. + * + * Used in knot_zone_find_dname() and knot_zone_find_dname_hash(). + */ +enum knot_zone_retvals { + KNOT_ZONE_NAME_FOUND = 1, + KNOT_ZONE_NAME_NOT_FOUND = 0 +}; + +typedef enum knot_zone_retvals knot_zone_retvals_t; + +/*----------------------------------------------------------------------------*/ + +/*! + * \brief Structure for holding DNS zone. + * + * \warning Make sure not to insert the same nodes using both the normal and + * NSEC3 functions. Although this will be successfull, it will produce + * double-free errors when destroying the zone. + */ +struct knot_zone { + knot_dname_t *name; + + knot_zone_contents_t *contents; + + time_t version; + + /*! \todo Set when loading zone. */ + short master; + + void *data; /*!< Pointer to generic zone-related data. */ + int (*dtor)(struct knot_zone *); /*!< Data destructor. */ +}; + +typedef struct knot_zone knot_zone_t; + +/*----------------------------------------------------------------------------*/ + +/*! + * \brief Creates new empty DNS zone. + * + * \notice Zone will be created without contents. + * + * \param name Zone owner. + * + * \return The initialized zone structure or NULL if an error occured. + */ +knot_zone_t *knot_zone_new_empty(knot_dname_t *name); + +/*! + * \brief Creates new DNS zone. + * + * \param apex Node representing the zone apex. + * \param node_count Number of authorative nodes in the zone. + * + * \return The initialized zone structure or NULL if an error occured. + */ +knot_zone_t *knot_zone_new(knot_node_t *apex, uint node_count, + int use_domain_table); + +knot_zone_contents_t *knot_zone_get_contents( + const knot_zone_t *zone); + +const knot_zone_contents_t *knot_zone_contents( + const knot_zone_t *zone); + + +time_t knot_zone_version(const knot_zone_t *zone); + +void knot_zone_set_version(knot_zone_t *zone, time_t version); + +short knot_zone_is_master(const knot_zone_t *zone); + +void knot_zone_set_master(knot_zone_t *zone, short master); + +const void *knot_zone_data(const knot_zone_t *zone); + +void knot_zone_set_data(knot_zone_t *zone, void *data); + +const knot_dname_t *knot_zone_name(const knot_zone_t *zone); + +knot_zone_contents_t *knot_zone_switch_contents(knot_zone_t *zone, + knot_zone_contents_t *new_contents); + +/*! + * \brief Correctly deallocates the zone structure, without deleting its nodes. + * + * Also sets the given pointer to NULL. + * + * \param zone Zone to be freed. + */ +void knot_zone_free(knot_zone_t **zone); + +/*! + * \brief Correctly deallocates the zone structure and all nodes within. + * + * Also sets the given pointer to NULL. + * + * \param zone Zone to be freed. + * \param free_rdata_dnames Set to <> 0 if you want to delete ALL domain names + * present in RDATA. Set to 0 otherwise. (See + * knot_rdata_deep_free().) + */ +void knot_zone_deep_free(knot_zone_t **zone, int destroy_dname_table); + +#endif + +/*! @} */ diff --git a/src/libknot/zone/zonedb.c b/src/libknot/zone/zonedb.c new file mode 100644 index 0000000..8f07d45 --- /dev/null +++ b/src/libknot/zone/zonedb.c @@ -0,0 +1,389 @@ +/* Copyright (C) 2011 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 <http://www.gnu.org/licenses/>. + */ + +#include <config.h> +#include <stdlib.h> +#include <assert.h> + +#include <urcu.h> + +#include "common.h" +#include "zone/zone.h" +#include "zone/zonedb.h" +#include "dname.h" +#include "zone/node.h" +#include "util/error.h" +#include "util/debug.h" +#include "common/general-tree.h" + +/*----------------------------------------------------------------------------*/ +/* Non-API functions */ +/*----------------------------------------------------------------------------*/ +/*! + * \brief Compares the two arguments interpreted as zone names (domain names). + * + * Use this function with generic data structures (such as the skip list). + * + * \param d1 First zone name. + * \param d2 Second zone name. + * + * \retval 0 if the two zone names are equal. + * \retval < 0 if \a d1 is before \a d2 in canonical order. + * \retval > 0 if \a d1 is after \a d2 in canonical order. + */ +static int knot_zonedb_compare_zone_names(void *p1, void *p2) +{ + const knot_zone_t *zone1 = (const knot_zone_t *)p1; + const knot_zone_t *zone2 = (const knot_zone_t *)p2; + + int ret = knot_dname_compare(zone1->name, zone2->name); + +dbg_zonedb_exec( + char *name1 = knot_dname_to_str(zone1->name); + char *name2 = knot_dname_to_str(zone2->name); + dbg_zonedb("Compared names %s and %s, result: %d.\n", + name1, name2, ret); + free(name1); + free(name2); +); + + return (ret); +} + +/*----------------------------------------------------------------------------*/ + +//static int knot_zonedb_replace_zone_in_list(void **list_item, void **new_zone) +//{ +// assert(list_item != NULL); +// assert(*list_item != NULL); +// assert(new_zone != NULL); +// assert(*new_zone != NULL); + +// dbg_zonedb("Replacing list item %p with new zone %p\n", +// *list_item, *new_zone); + +// *list_item = *new_zone; + +// return 0; +//} + +/*----------------------------------------------------------------------------*/ +/* API functions */ +/*----------------------------------------------------------------------------*/ + +knot_zonedb_t *knot_zonedb_new() +{ + knot_zonedb_t *db = + (knot_zonedb_t *)malloc(sizeof(knot_zonedb_t)); + CHECK_ALLOC_LOG(db, NULL); + + db->zone_tree = gen_tree_new(knot_zonedb_compare_zone_names); + if (db->zone_tree == NULL) { + free(db); + return NULL; + } + + db->zone_count = 0; + + return db; +} + +/*----------------------------------------------------------------------------*/ + +int knot_zonedb_add_zone(knot_zonedb_t *db, knot_zone_t *zone) +{ + if (db == NULL || zone == NULL) { + return KNOT_EBADARG; + } +dbg_zonedb_exec( + char *name = knot_dname_to_str(zone->name); + dbg_zonedb("Inserting zone %s into zone db.\n", name); + free(name); +); + + int ret = KNOT_EOK; + if (knot_zone_contents(zone)) { + ret = knot_zone_contents_load_nsec3param( + knot_zone_get_contents(zone)); + if (ret != KNOT_EOK) { + return ret; + } + } + + ret = gen_tree_add(db->zone_tree, zone, NULL); + + if (ret == 0) { + db->zone_count++; + } + + return (ret != 0) ? KNOT_EZONEIN : KNOT_EOK; +} + +/*----------------------------------------------------------------------------*/ + +knot_zone_t *knot_zonedb_remove_zone(knot_zonedb_t *db, + const knot_dname_t *zone_name) +{ + knot_zone_t dummy_zone; + memset(&dummy_zone, 0, sizeof(knot_zone_t)); + dummy_zone.name = (knot_dname_t *)zone_name; + + // add some lock to avoid multiple removals + knot_zone_t *z = (knot_zone_t *)gen_tree_find(db->zone_tree, + &dummy_zone); + + if (z == NULL) { + return NULL; + } + + // remove the zone from the skip list, but do not destroy it + gen_tree_remove(db->zone_tree, &dummy_zone); + +// if (destroy_zone) { +// // properly destroy the zone and all its contents +// knot_zone_deep_free(&z, 0); +// } + + db->zone_count--; + + //return KNOT_EOK; + return z; +} + +/*----------------------------------------------------------------------------*/ + +//knot_zone_t *knot_zonedb_replace_zone(knot_zonedb_t *db, +// knot_zone_t *zone) +//{ +// knot_zone_t *z = knot_zonedb_find_zone(db, +// knot_node_owner(knot_zone_apex(zone))); +// if (z == NULL) { +// return NULL; +// } + +// /*! \todo The replace should be atomic!!! */ + +// dbg_zonedb("Found zone: %p\n", z); + +// int ret = skip_remove(db->zones, +// (void *)knot_node_owner(knot_zone_apex(zone)), +// NULL, NULL); +// if (ret != 0) { +// return NULL; +// } + +// dbg_zonedb("Removed zone, return value: %d\n", ret); +// dbg_zonedb("Old zone: %p\n", z); + +// ret = skip_insert(db->zones, +// (void *)knot_node_owner(knot_zone_apex(zone)), +// (void *)zone, NULL); + +// dbg_zonedb("Inserted zone, return value: %d\n", ret); + +// if (ret != 0) { +// // return the removed zone back +// skip_insert(db->zones, +// (void *)knot_node_owner(knot_zone_apex(z)), +// (void *)z, NULL); +// /*! \todo There may be problems and the zone may remain +// removed. */ +// return NULL; +// } + +// return z; +//} + +/*----------------------------------------------------------------------------*/ + +knot_zone_t *knot_zonedb_find_zone(const knot_zonedb_t *db, + const knot_dname_t *zone_name) +{ + knot_zone_t dummy_zone; + dummy_zone.name = (knot_dname_t *)zone_name; + return (knot_zone_t *)gen_tree_find(db->zone_tree, &dummy_zone); +} + +/*----------------------------------------------------------------------------*/ + +const knot_zone_t *knot_zonedb_find_zone_for_name(knot_zonedb_t *db, + const knot_dname_t *dname) +{ + if (db == NULL || dname == NULL) { + return NULL; + } + + knot_zone_t dummy_zone; + dummy_zone.name = (knot_dname_t *)dname; + void *found = NULL; + int exact_match = gen_tree_find_less_or_equal(db->zone_tree, + &dummy_zone, + &found); + UNUSED(exact_match); + + knot_zone_t *zone = (found) ? (knot_zone_t *)found : NULL; + +dbg_zonedb_exec( + char *name = knot_dname_to_str(dname); + dbg_zonedb("Found zone for name %s: %p\n", name, zone); + free(name); +); + if (zone != NULL && zone->contents != NULL + && knot_dname_compare(zone->contents->apex->owner, dname) != 0 + && !knot_dname_is_subdomain(dname, zone->contents->apex->owner)) { + zone = NULL; + } + + return zone; +} + +/*----------------------------------------------------------------------------*/ + +knot_zone_contents_t *knot_zonedb_expire_zone(knot_zonedb_t *db, + const knot_dname_t *zone_name) +{ + if (db == NULL || zone_name == NULL) { + return NULL; + } + + // Remove the contents from the zone, but keep the zone in the zonedb. + + knot_zone_t *zone = knot_zonedb_find_zone(db, zone_name); + if (zone == NULL) { + return NULL; + } + + return knot_zone_switch_contents(zone, NULL); +} + +/*----------------------------------------------------------------------------*/ + +knot_zonedb_t *knot_zonedb_copy(const knot_zonedb_t *db) +{ + knot_zonedb_t *db_new = + (knot_zonedb_t *)malloc(sizeof(knot_zonedb_t)); + CHECK_ALLOC_LOG(db_new, NULL); + + db_new->zone_tree = gen_tree_shallow_copy(db->zone_tree); + if (db_new->zone_tree == NULL) { + free(db_new); + return NULL; + } + + return db_new; +} + +size_t knot_zonedb_zone_count(const knot_zonedb_t *db) +{ + return db->zone_count; +} + +struct knot_zone_db_tree_arg { + const knot_zone_t **zones; + size_t count; +}; + +static void save_zone_to_array(void *node, void *data) +{ + knot_zone_t *zone = (knot_zone_t *)node; + struct knot_zone_db_tree_arg *args = + (struct knot_zone_db_tree_arg *)data; + assert(data); + args->zones[args->count++] = zone; +} + +const knot_zone_t **knot_zonedb_zones(const knot_zonedb_t *db) +{ + struct knot_zone_db_tree_arg args; + args.zones = malloc(sizeof(knot_zone_t) * db->zone_count); + args.count = 0; + CHECK_ALLOC_LOG(args.zones, NULL); + + gen_tree_apply_inorder(db->zone_tree, save_zone_to_array, + &args); + assert(db->zone_count == args.count); + + return args.zones; +} + +/*----------------------------------------------------------------------------*/ + +void knot_zonedb_free(knot_zonedb_t **db) +{ + gen_tree_destroy(&((*db)->zone_tree), NULL ,NULL); + free(*db); + *db = NULL; +} + +/*----------------------------------------------------------------------------*/ + +static void delete_zone_from_db(void *node, void *data) +{ + UNUSED(data); + knot_zone_t *zone = (knot_zone_t *)node; + assert(zone); + synchronize_rcu(); + knot_zone_deep_free(&zone, 0); +} + +void knot_zonedb_deep_free(knot_zonedb_t **db) +{ + dbg_zonedb("Deleting zone db (%p).\n", *db); +// dbg_zonedb("Is it empty (%p)? %s\n", +// (*db)->zones, skip_is_empty((*db)->zones) ? "yes" : "no"); + +//dbg_zonedb_exec( +// int i = 1; +// char *name = NULL; +// while (zn != NULL) { +// dbg_zonedb("%d. zone: %p, key: %p\n", i, zn->value, +// zn->key); +// assert(zn->key == ((knot_zone_t *)zn->value)->apex->owner); +// name = knot_dname_to_str((knot_dname_t *)zn->key); +// dbg_zonedb(" zone name: %s\n", name); +// free(name); + +// zn = skip_next(zn); +// } + +// zn = skip_first((*db)->zones); +//); + +// while (zn != NULL) { +// zone = (knot_zone_t *)zn->value; +// assert(zone != NULL); + +// // remove the zone from the database +// skip_remove((*db)->zones, zn->key, NULL, NULL); +// // wait for all readers to finish +// synchronize_rcu; +// // destroy the zone +// knot_zone_deep_free(&zone, 0); + +// zn = skip_first((*db)->zones); +// } + +// assert(skip_is_empty((*db)->zones)); + +// skip_destroy_list(&(*db)->zones, NULL, NULL); + gen_tree_destroy(&((*db)->zone_tree), delete_zone_from_db, NULL); + assert((*db)->zone_tree == NULL); + free(*db); + *db = NULL; +} + +/*----------------------------------------------------------------------------*/ + diff --git a/src/libknot/zone/zonedb.h b/src/libknot/zone/zonedb.h new file mode 100644 index 0000000..d5a4992 --- /dev/null +++ b/src/libknot/zone/zonedb.h @@ -0,0 +1,145 @@ +/*! + * \file zonedb.h + * + * \author Lubos Slovak <lubos.slovak@nic.cz> + * + * \brief Zone database structure and API for manipulating it. + * + * Zone database groups several zones and provides functions for finding + * suitable zone for a domain name, for searching in a particular zone, etc. + * + * \addtogroup libknot + * @{ + */ +/* Copyright (C) 2011 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 <http://www.gnu.org/licenses/>. + */ + +#ifndef _KNOT_ZONEDB_H_ +#define _KNOT_ZONEDB_H_ + +#include "common/general-tree.h" +#include "zone/zone.h" +#include "zone/node.h" +#include "dname.h" + +/*! + * \brief Zone database structure. Contains all zones managed by the server. + */ +struct knot_zonedb { + general_tree_t *zone_tree; /*!< AVL tree of zones. */ + size_t zone_count; +}; + +typedef struct knot_zonedb knot_zonedb_t; + +/*----------------------------------------------------------------------------*/ + +/*! + * \brief Allocates and initializes the zone database structure. + * + * \return Pointer to the created zone database structure or NULL if an error + * occured. + */ +knot_zonedb_t *knot_zonedb_new(); + +/*! + * \brief Adds new zone to the database. + * + * \param db Zone database to store the zone. + * \param zone Parsed zone. + * + * \retval KNOT_EOK + * \retval KNOT_EZONEIN + */ +int knot_zonedb_add_zone(knot_zonedb_t *db, knot_zone_t *zone); + +/*! + * \brief Removes the given zone from the database if it exists. + * + * \note Assumes that the zone was adjusted using knot_zone_adjust_dnames(). + * If it was not, it may leak some memory due to checks used in + * knot_rdata_deep_free(). + * + * \param db Zone database to remove from. + * \param zone_name Name of the zone to be removed. + * \param destroy_zone Set to <> 0 if you do want the function to destroy the + * zone after removing from zone database. Set to 0 + * otherwise. + * + * \retval KNOT_EOK + * \retval KNOT_ENOZONE + */ +knot_zone_t * knot_zonedb_remove_zone(knot_zonedb_t *db, + const knot_dname_t *zone_name); + +//knot_zone_t *knot_zonedb_replace_zone(knot_zonedb_t *db, +// knot_zone_t *zone); + +/*! + * \brief Finds zone exactly matching the given zone name. + * + * \param db Zone database to search in. + * \param zone_name Domain name representing the zone name. + * + * \return Zone with \a zone_name being the owner of the zone apex or NULL if + * not found. + */ +knot_zone_t *knot_zonedb_find_zone(const knot_zonedb_t *db, + const knot_dname_t *zone_name); + + +/*! + * \brief Finds zone the given domain name should belong to. + * + * \param db Zone database to search in. + * \param dname Domain name to find zone for. + * + * \retval Zone in which the domain name should be present or NULL if no such + * zone is found. + */ +const knot_zone_t *knot_zonedb_find_zone_for_name(knot_zonedb_t *db, + const knot_dname_t *dname); + +knot_zone_contents_t *knot_zonedb_expire_zone(knot_zonedb_t *db, + const knot_dname_t *zone_name); + +size_t knot_zonedb_zone_count(const knot_zonedb_t *db); +const knot_zone_t **knot_zonedb_zones(const knot_zonedb_t *db); + +/*! + * \brief Destroys and deallocates the zone database structure (but not the + * zones within). + * + * \param db Zone database to be destroyed. + */ +void knot_zonedb_free(knot_zonedb_t **db); + +/*! + * \brief Destroys and deallocates the whole zone database including the zones. + * + * \note Assumes that the zone was adjusted using knot_zone_adjust_dnames(). + * If it was not, it may leak some memory due to checks used in + * knot_rdata_deep_free(). + * + * \param db Zone database to be destroyed. + */ +void knot_zonedb_deep_free(knot_zonedb_t **db); + +/*----------------------------------------------------------------------------*/ + +#endif /* _KNOT_ZONEDB_H_ */ + +/*! @} */ |