diff options
Diffstat (limited to '')
| -rw-r--r-- | rtrlib/pfx/trie/trie-pfx.c | 645 | ||||
| -rw-r--r-- | rtrlib/pfx/trie/trie-pfx.h | 73 | ||||
| -rw-r--r-- | rtrlib/pfx/trie/trie.c | 235 | ||||
| -rw-r--r-- | rtrlib/pfx/trie/trie_private.h | 98 |
4 files changed, 1051 insertions, 0 deletions
diff --git a/rtrlib/pfx/trie/trie-pfx.c b/rtrlib/pfx/trie/trie-pfx.c new file mode 100644 index 0000000..ffb2416 --- /dev/null +++ b/rtrlib/pfx/trie/trie-pfx.c @@ -0,0 +1,645 @@ +/* + * This file is part of RTRlib. + * + * This file is subject to the terms and conditions of the MIT license. + * See the file LICENSE in the top level directory for more details. + * + * Website: http://rtrlib.realmv6.org/ + */ + +#include "trie-pfx.h" + +#include "rtrlib/lib/alloc_utils_private.h" +#include "rtrlib/lib/ip_private.h" +#include "rtrlib/pfx/pfx_private.h" +#include "rtrlib/pfx/trie/trie_private.h" +#include "rtrlib/rtrlib_export_private.h" + +#include <assert.h> +#include <pthread.h> +#include <stdbool.h> +#include <stdlib.h> + +struct data_elem { + uint32_t asn; + uint8_t max_len; + const struct rtr_socket *socket; +}; + +struct node_data { + unsigned int len; + struct data_elem *ary; +}; + +struct copy_cb_args { + struct pfx_table *pfx_table; + const struct rtr_socket *socket; + bool error; +}; + +struct notify_diff_cb_args { + struct pfx_table *old_table; + struct pfx_table *new_table; + const struct rtr_socket *socket; + pfx_update_fp pfx_update_fp; + bool added; +}; + +static struct trie_node *pfx_table_get_root(const struct pfx_table *pfx_table, const enum lrtr_ip_version ver); +static int pfx_table_del_elem(struct node_data *data, const unsigned int index); +static int pfx_table_create_node(struct trie_node **node, const struct pfx_record *record); +static int pfx_table_append_elem(struct node_data *data, const struct pfx_record *record); +static struct data_elem *pfx_table_find_elem(const struct node_data *data, const struct pfx_record *record, + unsigned int *index); +static bool pfx_table_elem_matches(struct node_data *data, const uint32_t asn, const uint8_t prefix_len); +static void pfx_table_notify_clients(struct pfx_table *pfx_table, const struct pfx_record *record, const bool added); +static int pfx_table_remove_id(struct pfx_table *pfx_table, struct trie_node **root, struct trie_node *node, + const struct rtr_socket *socket, const unsigned int level); +static int pfx_table_node2pfx_record(struct trie_node *node, struct pfx_record records[], const unsigned int ary_len); +static void pfx_table_free_reason(struct pfx_record **reason, unsigned int *reason_len); + +void pfx_table_notify_clients(struct pfx_table *pfx_table, const struct pfx_record *record, const bool added) +{ + if (pfx_table->update_fp) + pfx_table->update_fp(pfx_table, *record, added); +} + +RTRLIB_EXPORT void pfx_table_init(struct pfx_table *pfx_table, pfx_update_fp update_fp) +{ + pfx_table->ipv4 = NULL; + pfx_table->ipv6 = NULL; + pfx_table->update_fp = update_fp; + pthread_rwlock_init(&(pfx_table->lock), NULL); +} + +void pfx_table_free_without_notify(struct pfx_table *pfx_table) +{ + pfx_table->update_fp = NULL; + pfx_table_free(pfx_table); +} + +RTRLIB_EXPORT void pfx_table_free(struct pfx_table *pfx_table) +{ + for (int i = 0; i < 2; i++) { + struct trie_node *root = (i == 0 ? pfx_table->ipv4 : pfx_table->ipv6); + + if (root) { + struct trie_node *rm_node; + + pthread_rwlock_wrlock(&(pfx_table->lock)); + do { + struct node_data *data = (struct node_data *)(root->data); + + for (unsigned int j = 0; j < data->len; j++) { + struct pfx_record record = {data->ary[j].asn, (root->prefix), root->len, + data->ary[j].max_len, data->ary[j].socket}; + pfx_table_notify_clients(pfx_table, &record, false); + } + rm_node = (trie_remove(root, &(root->prefix), root->len, 0)); + assert(rm_node); + lrtr_free(((struct node_data *)rm_node->data)->ary); + lrtr_free(rm_node->data); + lrtr_free(rm_node); + } while (rm_node != root); + if (i == 0) + pfx_table->ipv4 = NULL; + else + pfx_table->ipv6 = NULL; + + pthread_rwlock_unlock(&(pfx_table->lock)); + } + } + pthread_rwlock_destroy(&(pfx_table->lock)); +} + +int pfx_table_append_elem(struct node_data *data, const struct pfx_record *record) +{ + struct data_elem *tmp = lrtr_realloc(data->ary, sizeof(struct data_elem) * ((data->len) + 1)); + + if (!tmp) + return PFX_ERROR; + data->len++; + data->ary = tmp; + data->ary[data->len - 1].asn = record->asn; + data->ary[data->len - 1].max_len = record->max_len; + data->ary[data->len - 1].socket = record->socket; + return PFX_SUCCESS; +} + +int pfx_table_create_node(struct trie_node **node, const struct pfx_record *record) +{ + int err; + + *node = lrtr_malloc(sizeof(struct trie_node)); + if (!*node) + return PFX_ERROR; + + (*node)->prefix = record->prefix; + (*node)->len = record->min_len; + (*node)->lchild = NULL; + (*node)->rchild = NULL; + (*node)->parent = NULL; + + (*node)->data = lrtr_malloc(sizeof(struct node_data)); + if (!(*node)->data) { + err = PFX_ERROR; + goto free_node; + } + + ((struct node_data *)(*node)->data)->len = 0; + ((struct node_data *)(*node)->data)->ary = NULL; + + err = pfx_table_append_elem(((struct node_data *)(*node)->data), record); + if (err) + goto free_node_data; + + return PFX_SUCCESS; + +free_node_data: + lrtr_free((*node)->data); +free_node: + lrtr_free(*node); + + return err; +} + +struct data_elem *pfx_table_find_elem(const struct node_data *data, const struct pfx_record *record, + unsigned int *index) +{ + for (unsigned int i = 0; i < data->len; i++) { + if (data->ary[i].asn == record->asn && data->ary[i].max_len == record->max_len && + data->ary[i].socket == record->socket) { + if (index) + *index = i; + return &(data->ary[i]); + } + } + return NULL; +} + +// returns pfx_table->ipv4 if record version is LRTR_IPV4 else pfx_table->ipv6 +inline struct trie_node *pfx_table_get_root(const struct pfx_table *pfx_table, const enum lrtr_ip_version ver) +{ + return ver == LRTR_IPV4 ? pfx_table->ipv4 : pfx_table->ipv6; +} + +int pfx_table_del_elem(struct node_data *data, const unsigned int index) +{ + struct data_elem *tmp; + struct data_elem deleted_elem = data->ary[index]; + + // if index is not the last elem in the list, move all other elems backwards in the array + if (index != data->len - 1) { + for (unsigned int i = index; i < data->len - 1; i++) + data->ary[i] = data->ary[i + 1]; + } + + data->len--; + if (!data->len) { + lrtr_free(data->ary); + data->ary = NULL; + return PFX_SUCCESS; + } + + tmp = lrtr_realloc(data->ary, sizeof(struct data_elem) * data->len); + if (!tmp) { + data->ary[data->len] = deleted_elem; + data->len++; + return PFX_ERROR; + } + + data->ary = tmp; + + return PFX_SUCCESS; +} + +RTRLIB_EXPORT int pfx_table_add(struct pfx_table *pfx_table, const struct pfx_record *record) +{ + pthread_rwlock_wrlock(&(pfx_table->lock)); + + struct trie_node *root = pfx_table_get_root(pfx_table, record->prefix.ver); + unsigned int lvl = 0; + + if (root) { + bool found; + struct trie_node *node = trie_lookup_exact(root, &(record->prefix), record->min_len, &lvl, &found); + + if (found) { // node with prefix exists + if (pfx_table_find_elem(node->data, record, NULL)) { + pthread_rwlock_unlock(&pfx_table->lock); + return PFX_DUPLICATE_RECORD; + } + // append record to note_data array + int rtval = pfx_table_append_elem(node->data, record); + + pthread_rwlock_unlock(&pfx_table->lock); + if (rtval == PFX_SUCCESS) + pfx_table_notify_clients(pfx_table, record, true); + return rtval; + } + + // no node with same prefix and prefix_len found + struct trie_node *new_node = NULL; + + if (pfx_table_create_node(&new_node, record) == PFX_ERROR) { + pthread_rwlock_unlock(&pfx_table->lock); + return PFX_ERROR; + } + trie_insert(node, new_node, lvl); + pthread_rwlock_unlock(&pfx_table->lock); + pfx_table_notify_clients(pfx_table, record, true); + return PFX_SUCCESS; + } + + // tree is empty, record will be the root_node + struct trie_node *new_node = NULL; + + if (pfx_table_create_node(&new_node, record) == PFX_ERROR) { + pthread_rwlock_unlock(&pfx_table->lock); + return PFX_ERROR; + } + if (record->prefix.ver == LRTR_IPV4) + pfx_table->ipv4 = new_node; + else + pfx_table->ipv6 = new_node; + + pthread_rwlock_unlock(&pfx_table->lock); + pfx_table_notify_clients(pfx_table, record, true); + return PFX_SUCCESS; +} + +RTRLIB_EXPORT int pfx_table_remove(struct pfx_table *pfx_table, const struct pfx_record *record) +{ + pthread_rwlock_wrlock(&(pfx_table->lock)); + struct trie_node *root = pfx_table_get_root(pfx_table, record->prefix.ver); + + unsigned int lvl = 0; // tree depth were node was found + bool found; + struct trie_node *node = trie_lookup_exact(root, &(record->prefix), record->min_len, &lvl, &found); + + if (!found) { + pthread_rwlock_unlock(&pfx_table->lock); + return PFX_RECORD_NOT_FOUND; + } + + unsigned int index; + struct data_elem *elem = pfx_table_find_elem(node->data, record, &index); + + if (!elem) { + pthread_rwlock_unlock(&pfx_table->lock); + return PFX_RECORD_NOT_FOUND; + } + + struct node_data *ndata = (struct node_data *)node->data; + + if (pfx_table_del_elem(ndata, index) == PFX_ERROR) { + pthread_rwlock_unlock(&pfx_table->lock); + return PFX_ERROR; + } + + if (ndata->len == 0) { + node = trie_remove(node, &(record->prefix), record->min_len, lvl); + assert(node); + + if (node == root) { + if (record->prefix.ver == LRTR_IPV4) + pfx_table->ipv4 = NULL; + else + pfx_table->ipv6 = NULL; + } + assert(((struct node_data *)node->data)->len == 0); + lrtr_free(node->data); + lrtr_free(node); + } + pthread_rwlock_unlock(&pfx_table->lock); + + pfx_table_notify_clients(pfx_table, record, false); + + return PFX_SUCCESS; +} + +bool pfx_table_elem_matches(struct node_data *data, const uint32_t asn, const uint8_t prefix_len) +{ + for (unsigned int i = 0; i < data->len; i++) { + if (data->ary[i].asn != 0 && data->ary[i].asn == asn && prefix_len <= data->ary[i].max_len) + return true; + } + return false; +} + +int pfx_table_node2pfx_record(struct trie_node *node, struct pfx_record *records, const unsigned int ary_len) +{ + struct node_data *data = node->data; + + if (ary_len < data->len) + return PFX_ERROR; + + for (unsigned int i = 0; i < data->len; i++) { + records[i].asn = data->ary[i].asn; + records[i].prefix = node->prefix; + records[i].min_len = node->len; + records[i].max_len = data->ary[i].max_len; + records[i].socket = data->ary[i].socket; + } + return data->len; +} + +inline void pfx_table_free_reason(struct pfx_record **reason, unsigned int *reason_len) +{ + if (reason) { + lrtr_free(*reason); + *reason = NULL; + } + if (reason_len) + *reason_len = 0; +} + +RTRLIB_EXPORT int pfx_table_validate_r(struct pfx_table *pfx_table, struct pfx_record **reason, + unsigned int *reason_len, const uint32_t asn, const struct lrtr_ip_addr *prefix, + const uint8_t prefix_len, enum pfxv_state *result) +{ + // assert(reason_len == NULL || *reason_len == 0); + // assert(reason == NULL || *reason == NULL); + + pthread_rwlock_rdlock(&(pfx_table->lock)); + struct trie_node *root = pfx_table_get_root(pfx_table, prefix->ver); + + if (!root) { + pthread_rwlock_unlock(&pfx_table->lock); + *result = BGP_PFXV_STATE_NOT_FOUND; + pfx_table_free_reason(reason, reason_len); + return PFX_SUCCESS; + } + + unsigned int lvl = 0; + struct trie_node *node = trie_lookup(root, prefix, prefix_len, &lvl); + + if (!node) { + pthread_rwlock_unlock(&pfx_table->lock); + *result = BGP_PFXV_STATE_NOT_FOUND; + pfx_table_free_reason(reason, reason_len); + return PFX_SUCCESS; + } + + if (reason_len && reason) { + *reason_len = ((struct node_data *)node->data)->len; + *reason = lrtr_realloc(*reason, *reason_len * sizeof(struct pfx_record)); + if (!*reason) { + pthread_rwlock_unlock(&pfx_table->lock); + pfx_table_free_reason(reason, reason_len); + return PFX_ERROR; + } + if (pfx_table_node2pfx_record(node, *reason, *reason_len) == PFX_ERROR) { + pthread_rwlock_unlock(&pfx_table->lock); + pfx_table_free_reason(reason, reason_len); + return PFX_ERROR; + } + } + + while (!pfx_table_elem_matches(node->data, asn, prefix_len)) { + if (lrtr_ip_addr_is_zero(lrtr_ip_addr_get_bits( + prefix, lvl++, + 1))) //post-incr lvl, trie_lookup is performed on child_nodes => parent lvl + 1 + node = trie_lookup(node->lchild, prefix, prefix_len, &lvl); + else + node = trie_lookup(node->rchild, prefix, prefix_len, &lvl); + + if (!node) { + pthread_rwlock_unlock(&pfx_table->lock); + *result = BGP_PFXV_STATE_INVALID; + return PFX_SUCCESS; + } + + if (reason_len && reason) { + unsigned int r_len_old = *reason_len; + *reason_len += ((struct node_data *)node->data)->len; + *reason = lrtr_realloc(*reason, *reason_len * sizeof(struct pfx_record)); + struct pfx_record *start = *reason + r_len_old; + + if (!*reason) { + pthread_rwlock_unlock(&pfx_table->lock); + pfx_table_free_reason(reason, reason_len); + return PFX_ERROR; + } + if (pfx_table_node2pfx_record(node, start, ((struct node_data *)node->data)->len) == + PFX_ERROR) { + pthread_rwlock_unlock(&pfx_table->lock); + pfx_table_free_reason(reason, reason_len); + return PFX_ERROR; + } + } + } + + pthread_rwlock_unlock(&pfx_table->lock); + *result = BGP_PFXV_STATE_VALID; + return PFX_SUCCESS; +} + +RTRLIB_EXPORT int pfx_table_validate(struct pfx_table *pfx_table, const uint32_t asn, const struct lrtr_ip_addr *prefix, + const uint8_t prefix_len, enum pfxv_state *result) +{ + return pfx_table_validate_r(pfx_table, NULL, NULL, asn, prefix, prefix_len, result); +} + +RTRLIB_EXPORT int pfx_table_src_remove(struct pfx_table *pfx_table, const struct rtr_socket *socket) +{ + for (unsigned int i = 0; i < 2; i++) { + struct trie_node **root = (i == 0 ? &(pfx_table->ipv4) : &(pfx_table->ipv6)); + + pthread_rwlock_wrlock(&(pfx_table->lock)); + if (*root) { + int rtval = pfx_table_remove_id(pfx_table, root, *root, socket, 0); + + if (rtval == PFX_ERROR) { + pthread_rwlock_unlock(&pfx_table->lock); + return PFX_ERROR; + } + } + pthread_rwlock_unlock(&pfx_table->lock); + } + return PFX_SUCCESS; +} + +int pfx_table_remove_id(struct pfx_table *pfx_table, struct trie_node **root, struct trie_node *node, + const struct rtr_socket *socket, const unsigned int level) +{ + assert(node); + assert(root); + assert(*root); + bool check_node = true; + + while (check_node) { + // data from removed node are replaced from data from child nodes (if children exists), + // same node must be checked again if it was replaced with previous child node data + struct node_data *data = node->data; + + for (unsigned int i = 0; i < data->len; i++) { + while (data->len > i && data->ary[i].socket == socket) { + struct pfx_record record = {data->ary[i].asn, node->prefix, node->len, + data->ary[i].max_len, data->ary[i].socket}; + if (pfx_table_del_elem(data, i) == PFX_ERROR) + return PFX_ERROR; + pfx_table_notify_clients(pfx_table, &record, false); + } + } + if (data->len == 0) { + struct trie_node *rm_node = trie_remove(node, &(node->prefix), node->len, level); + + assert(rm_node); + assert(((struct node_data *)rm_node->data)->len == 0); + lrtr_free(((struct node_data *)rm_node->data)); + lrtr_free(rm_node); + + if (rm_node == *root) { + *root = NULL; + return PFX_SUCCESS; + } else if (rm_node == node) { + return PFX_SUCCESS; + } + } else { + check_node = false; + } + } + + if (node->lchild) { + if (pfx_table_remove_id(pfx_table, root, node->lchild, socket, level + 1) == PFX_ERROR) + return PFX_ERROR; + } + if (node->rchild) + return pfx_table_remove_id(pfx_table, root, node->rchild, socket, level + 1); + return PFX_SUCCESS; +} + +static void pfx_table_for_each_rec(struct trie_node *n, pfx_for_each_fp fp, void *data) +{ + struct pfx_record pfxr; + struct node_data *nd; + + assert(n); + assert(fp); + + nd = (struct node_data *)n->data; + assert(nd); + + if (n->lchild) + pfx_table_for_each_rec(n->lchild, fp, data); + + for (unsigned int i = 0; i < nd->len; i++) { + pfxr.asn = nd->ary[i].asn; + pfxr.prefix = n->prefix; + pfxr.min_len = n->len; + pfxr.max_len = nd->ary[i].max_len; + pfxr.socket = nd->ary[i].socket; + fp(&pfxr, data); + } + + if (n->rchild) + pfx_table_for_each_rec(n->rchild, fp, data); +} + +RTRLIB_EXPORT void pfx_table_for_each_ipv4_record(struct pfx_table *pfx_table, pfx_for_each_fp fp, void *data) +{ + assert(pfx_table); + + if (!pfx_table->ipv4) + return; + + pthread_rwlock_rdlock(&(pfx_table->lock)); + pfx_table_for_each_rec(pfx_table->ipv4, fp, data); + pthread_rwlock_unlock(&pfx_table->lock); +} + +RTRLIB_EXPORT void pfx_table_for_each_ipv6_record(struct pfx_table *pfx_table, pfx_for_each_fp fp, void *data) +{ + assert(pfx_table); + + if (!pfx_table->ipv6) + return; + + pthread_rwlock_rdlock(&(pfx_table->lock)); + pfx_table_for_each_rec(pfx_table->ipv6, fp, data); + pthread_rwlock_unlock(&pfx_table->lock); +} + +static void pfx_table_copy_cb(const struct pfx_record *record, void *data) +{ + struct copy_cb_args *args = data; + + if (record->socket != args->socket) { + if (pfx_table_add(args->pfx_table, record) != PFX_SUCCESS) + args->error = true; + } +} + +int pfx_table_copy_except_socket(struct pfx_table *src_table, struct pfx_table *dst_table, + const struct rtr_socket *socket) +{ + struct copy_cb_args args = {dst_table, socket, false}; + + pfx_table_for_each_ipv4_record(src_table, pfx_table_copy_cb, &args); + if (args.error) + return PFX_ERROR; + + pfx_table_for_each_ipv6_record(src_table, pfx_table_copy_cb, &args); + if (args.error) + return PFX_ERROR; + + return PFX_SUCCESS; +} + +void pfx_table_swap(struct pfx_table *a, struct pfx_table *b) +{ + struct trie_node *ipv4_tmp; + struct trie_node *ipv6_tmp; + + pthread_rwlock_wrlock(&(a->lock)); + pthread_rwlock_wrlock(&(b->lock)); + + ipv4_tmp = a->ipv4; + ipv6_tmp = a->ipv6; + + a->ipv4 = b->ipv4; + a->ipv6 = b->ipv6; + + b->ipv4 = ipv4_tmp; + b->ipv6 = ipv6_tmp; + + pthread_rwlock_unlock(&(b->lock)); + pthread_rwlock_unlock(&(a->lock)); +} + +static void pfx_table_notify_diff_cb(const struct pfx_record *record, void *data) +{ + struct notify_diff_cb_args *args = data; + + if (args->socket == record->socket && args->added) { + if (pfx_table_remove(args->old_table, record) != PFX_SUCCESS) + pfx_table_notify_clients(args->new_table, record, args->added); + } else if (args->socket == record->socket && !args->added) { + pfx_table_notify_clients(args->new_table, record, args->added); + } +} + +void pfx_table_notify_diff(struct pfx_table *new_table, struct pfx_table *old_table, const struct rtr_socket *socket) +{ + pfx_update_fp old_table_fp; + struct notify_diff_cb_args args = {old_table, new_table, socket, new_table->update_fp, true}; + + // Disable update callback for old_table table + old_table_fp = old_table->update_fp; + old_table->update_fp = NULL; + + // Iterate new_table and try to delete every prefix from the given socket in old_table + // If the prefix could not be removed it was added in new_table and the update cb must be called + pfx_table_for_each_ipv4_record(new_table, pfx_table_notify_diff_cb, &args); + pfx_table_for_each_ipv6_record(new_table, pfx_table_notify_diff_cb, &args); + + // Iterate over old_table table and search and remove remaining prefixes from the socket + // issue a remove notification for every one of them, because they are not present in new_table. + args.added = false; + pfx_table_for_each_ipv4_record(old_table, pfx_table_notify_diff_cb, &args); + pfx_table_for_each_ipv6_record(old_table, pfx_table_notify_diff_cb, &args); + + // Restore original state of old_tables update_fp + old_table->update_fp = old_table_fp; +} diff --git a/rtrlib/pfx/trie/trie-pfx.h b/rtrlib/pfx/trie/trie-pfx.h new file mode 100644 index 0000000..7a8f69a --- /dev/null +++ b/rtrlib/pfx/trie/trie-pfx.h @@ -0,0 +1,73 @@ +/* + * This file is part of RTRlib. + * + * This file is subject to the terms and conditions of the MIT license. + * See the file LICENSE in the top level directory for more details. + * + * Website: http://rtrlib.realmv6.org/ + */ + +/** + * @defgroup mod_trie_pfx_h Trie + * @ingroup mod_pfx_h + * @brief An implementation of a \ref mod_pfx_h "pfx_table" data structure + * using a shortest prefix first tree (trie) for storing @ref pfx_record "pfx_records". + * @details This implementation uses two separate lpfs-trees, one for IPv4 + * validation records and one for IPv6 records.\n + * See \ref mod_pfx_h "pfx_table" for a list of supported operations of + * this data structure.\n + * + * @{ + */ + +#ifndef RTR_TRIE_PFX +#define RTR_TRIE_PFX + +#include "rtrlib/lib/ip.h" + +#include <pthread.h> +#include <stdbool.h> +#include <stdint.h> + +struct pfx_table; + +/** + * @brief pfx_record. + * @param asn Origin AS number. + * @param prefix IP prefix. + * @param min_len Minimum prefix length. + * @param max_len Maximum prefix length. + * @param socket The rtr_socket that received this record. + */ +struct pfx_record { + uint32_t asn; + struct lrtr_ip_addr prefix; + uint8_t min_len; + uint8_t max_len; + const struct rtr_socket *socket; +}; + +/** + * @brief A function pointer that is called if an record was added to the pfx_table or was removed from the pfx_table. + * @param pfx_table which was updated. + * @param record pfx_record that was modified. + * @param added True if the record was added, false if the record was removed. + */ +typedef void (*pfx_update_fp)(struct pfx_table *pfx_table, const struct pfx_record record, const bool added); + +/** + * @brief pfx_table. + * @param ipv4 + * @param ipv6 + * @param update_fp + * @param lock + */ +struct pfx_table { + struct trie_node *ipv4; + struct trie_node *ipv6; + pfx_update_fp update_fp; + pthread_rwlock_t lock; +}; + +#endif +/** @} */ diff --git a/rtrlib/pfx/trie/trie.c b/rtrlib/pfx/trie/trie.c new file mode 100644 index 0000000..b359892 --- /dev/null +++ b/rtrlib/pfx/trie/trie.c @@ -0,0 +1,235 @@ +/* + * This file is part of RTRlib. + * + * This file is subject to the terms and conditions of the MIT license. + * See the file LICENSE in the top level directory for more details. + * + * Website: http://rtrlib.realmv6.org/ + */ + +#include "trie_private.h" + +#include "rtrlib/lib/alloc_utils_private.h" +#include "rtrlib/lib/ip_private.h" + +#include <assert.h> +#include <stdlib.h> + +static void swap_nodes(struct trie_node *a, struct trie_node *b) +{ + struct trie_node tmp; + + tmp.prefix = a->prefix; + tmp.len = a->len; + tmp.data = a->data; + + a->prefix = b->prefix; + a->len = b->len; + a->data = b->data; + + b->prefix = tmp.prefix; + b->len = tmp.len; + b->data = tmp.data; +} + +enum child_node_rel { LEFT, RIGHT }; + +static void add_child_node(struct trie_node *parent, struct trie_node *child, enum child_node_rel rel) +{ + assert(rel == LEFT || rel == RIGHT); + + if (rel == LEFT) + parent->lchild = child; + else + parent->rchild = child; + + child->parent = parent; +} + +static inline bool is_left_child(const struct lrtr_ip_addr *addr, unsigned int lvl) +{ + /* A node must be inserted as left child if bit <lvl> of the IP address + * is 0 otherwise as right child + */ + return lrtr_ip_addr_is_zero(lrtr_ip_addr_get_bits(addr, lvl, 1)); +} + +void trie_insert(struct trie_node *root, struct trie_node *new, const unsigned int lvl) +{ + if (new->len < root->len) + swap_nodes(root, new); + + if (is_left_child(&new->prefix, lvl)) { + if (!root->lchild) + return add_child_node(root, new, LEFT); + + return trie_insert(root->lchild, new, lvl + 1); + } + + if (!root->rchild) + return add_child_node(root, new, RIGHT); + + trie_insert(root->rchild, new, lvl + 1); +} + +struct trie_node *trie_lookup(const struct trie_node *root, const struct lrtr_ip_addr *prefix, const uint8_t mask_len, + unsigned int *lvl) +{ + while (root) { + if (root->len <= mask_len && lrtr_ip_addr_equal(lrtr_ip_addr_get_bits(&root->prefix, 0, root->len), + lrtr_ip_addr_get_bits(prefix, 0, root->len))) + return (struct trie_node *)root; + + if (is_left_child(prefix, *lvl)) + root = root->lchild; + else + root = root->rchild; + + (*lvl)++; + } + return NULL; +} + +struct trie_node *trie_lookup_exact(struct trie_node *root_node, const struct lrtr_ip_addr *prefix, + const uint8_t mask_len, unsigned int *lvl, bool *found) +{ + *found = false; + + while (root_node) { + if (*lvl > 0 && root_node->len > mask_len) { + (*lvl)--; + return root_node->parent; + } + + if (root_node->len == mask_len && lrtr_ip_addr_equal(root_node->prefix, *prefix)) { + *found = true; + return root_node; + } + + if (is_left_child(prefix, *lvl)) { + if (!root_node->lchild) + return root_node; + root_node = root_node->lchild; + } else { + if (!root_node->rchild) + return root_node; + root_node = root_node->rchild; + } + + (*lvl)++; + } + return NULL; +} + +static void deref_node(struct trie_node *n) +{ + if (!n->parent) + return; + + if (n->parent->lchild == n) { + n->parent->lchild = NULL; + return; + } + + n->parent->rchild = NULL; +} + +static inline bool prefix_is_same(const struct trie_node *n, const struct lrtr_ip_addr *p, uint8_t mask_len) +{ + return n->len == mask_len && lrtr_ip_addr_equal(n->prefix, *p); +} + +static void replace_node_data(struct trie_node *a, struct trie_node *b) +{ + a->prefix = b->prefix; + a->len = b->len; + a->data = b->data; +} + +struct trie_node *trie_remove(struct trie_node *root, const struct lrtr_ip_addr *prefix, const uint8_t mask_len, + const unsigned int lvl) +{ + /* If the node has no children we can simply remove it + * If the node has children, we swap the node with the child that + * has the smaller prefix length and drop the child. + */ + if (prefix_is_same(root, prefix, mask_len)) { + void *tmp; + + if (trie_is_leaf(root)) { + deref_node(root); + return root; + } + + /* swap with the left child and drop the child */ + if (root->lchild && (!root->rchild || root->lchild->len < root->rchild->len)) { + tmp = root->data; + replace_node_data(root, root->lchild); + root->lchild->data = tmp; + + return trie_remove(root->lchild, &root->lchild->prefix, root->lchild->len, lvl + 1); + } + + /* swap with the right child and drop the child */ + tmp = root->data; + replace_node_data(root, root->rchild); + root->rchild->data = tmp; + + return trie_remove(root->rchild, &root->rchild->prefix, root->rchild->len, lvl + 1); + } + + if (is_left_child(prefix, lvl)) { + if (!root->lchild) + return NULL; + return trie_remove(root->lchild, prefix, mask_len, lvl + 1); + } + + if (!root->rchild) + return NULL; + return trie_remove(root->rchild, prefix, mask_len, lvl + 1); +} + +static int append_node_to_array(struct trie_node ***ary, unsigned int *len, struct trie_node *n) +{ + struct trie_node **new; + + new = lrtr_realloc(*ary, *len * sizeof(n)); + if (!new) + return -1; + + *ary = new; + (*ary)[*len - 1] = n; + return 0; +} + +int trie_get_children(const struct trie_node *root_node, struct trie_node ***array, unsigned int *len) +{ + if (root_node->lchild) { + *len += 1; + if (append_node_to_array(array, len, root_node->lchild)) + goto err; + + if (trie_get_children(root_node->lchild, array, len) == -1) + goto err; + } + + if (root_node->rchild) { + *len += 1; + if (append_node_to_array(array, len, root_node->rchild)) + goto err; + + if (trie_get_children(root_node->rchild, array, len) == -1) + goto err; + } + + return 0; + +err: + lrtr_free(*array); + return -1; +} + +inline bool trie_is_leaf(const struct trie_node *node) +{ + return !node->lchild && !node->rchild; +} diff --git a/rtrlib/pfx/trie/trie_private.h b/rtrlib/pfx/trie/trie_private.h new file mode 100644 index 0000000..8003ced --- /dev/null +++ b/rtrlib/pfx/trie/trie_private.h @@ -0,0 +1,98 @@ +/* + * This file is part of RTRlib. + * + * This file is subject to the terms and conditions of the MIT license. + * See the file LICENSE in the top level directory for more details. + * + * Website: http://rtrlib.realmv6.org/ + */ + +#ifndef RTR_TRIE_PRIVATE +#define RTR_TRIE_PRIVATE + +#include "rtrlib/lib/ip_private.h" + +#include <inttypes.h> + +/** + * @brief trie_node + * @param prefix + * @param rchild + * @param lchild + * @param parent + * @param data + * @param len number of elements in data array + */ +struct trie_node { + struct lrtr_ip_addr prefix; + struct trie_node *rchild; + struct trie_node *lchild; + struct trie_node *parent; + void *data; + uint8_t len; +}; + +/** + * @brief Inserts new_node in the tree. + * @param[in] root Root node of the tree for the inserting process. + * @param[in] new_node Node that will be inserted. + * @param[in] level Level of the the root node in the tree. + */ +void trie_insert(struct trie_node *root, struct trie_node *new_node, const unsigned int level); + +/** + * @brief Searches for a matching node matching the passed ip + * prefix and prefix length. If multiple matching nodes exist, the one + * with the shortest prefix is returned. + * @param[in] root_node Node were the lookup process starts. + * @param[in] lrtr_ip_addr IP-Prefix. + * @param[in] mask_len Length of the network mask of the prefix. + * @param[in,out] level of the the node root in the tree. Is set to the level of + * the node that is returned. + * @returns The trie_node with the short prefix in the tree matching the + * passed ip prefix and prefix length. + * @returns NULL if no node that matches the passed prefix and prefix length + * could be found. + */ +struct trie_node *trie_lookup(const struct trie_node *root_node, const struct lrtr_ip_addr *prefix, + const uint8_t mask_len, unsigned int *level); + +/** + * @brief Search for a node with the same prefix and prefix length. + * @param[in] root_node Node were the lookup process starts. + * @param[in] lrtr_ip_addr IP-Prefix. + * @param[in] mask_len Length of the network mask of the prefix. + * @param[in,out] level of the the node root in the tree. Is set to the level of + * the node that is returned. + * @param[in] found Is true if a node which matches could be found else found is + * set to false. + * @return A node which matches the passed parameter (found==true). + * @return The parent of the node where the lookup operation + * stopped (found==false). + * @return NULL if root_node is NULL. + */ +struct trie_node *trie_lookup_exact(struct trie_node *root_node, const struct lrtr_ip_addr *prefix, + const uint8_t mask_len, unsigned int *level, bool *found); + +/** + * @brief Removes the node with the passed IP prefix and mask_len from the tree. + * @param[in] root Node were the inserting process starts. + * @param[in] prefix Prefix that will removed from the tree. + * @param[in] mask_len Length of the network mask of the prefix. + * @param[in] level Level of the root node in the tree. + * @returns Node that was removed from the tree. The caller has to free it. + * @returns NULL If the Prefix couldn't be found in the tree. + */ +struct trie_node *trie_remove(struct trie_node *root_node, const struct lrtr_ip_addr *prefix, const uint8_t mask_len, + const unsigned int level); + +/** + * @brief Detects if a node is a leaf in the tree. + * @param[in] node + * @returns true if node is a leaf. + * @returns false if node isn't a leaf. + */ +bool trie_is_leaf(const struct trie_node *node); + +int trie_get_children(const struct trie_node *root_node, struct trie_node ***array, unsigned int *len); +#endif |