diff options
Diffstat (limited to 'lib/table.c')
| -rw-r--r-- | lib/table.c | 796 |
1 files changed, 796 insertions, 0 deletions
diff --git a/lib/table.c b/lib/table.c new file mode 100644 index 0000000..6c4c6c7 --- /dev/null +++ b/lib/table.c @@ -0,0 +1,796 @@ +/* + * Routing Table functions. + * Copyright (C) 1998 Kunihiro Ishiguro + * + * This file is part of GNU Zebra. + * + * GNU Zebra 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 2, or (at your option) any + * later version. + * + * GNU Zebra 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; see the file COPYING; if not, write to the Free Software + * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA + */ + +#define FRR_COMPILING_TABLE_C + +#include <zebra.h> + +#include "prefix.h" +#include "table.h" +#include "memory.h" +#include "sockunion.h" +#include "libfrr_trace.h" + +DEFINE_MTYPE_STATIC(LIB, ROUTE_TABLE, "Route table"); +DEFINE_MTYPE(LIB, ROUTE_NODE, "Route node"); + +static void route_table_free(struct route_table *); + +static int route_table_hash_cmp(const struct route_node *a, + const struct route_node *b) +{ + return prefix_cmp(&a->p, &b->p); +} + +DECLARE_HASH(rn_hash_node, struct route_node, nodehash, route_table_hash_cmp, + prefix_hash_key); +/* + * route_table_init_with_delegate + */ +struct route_table * +route_table_init_with_delegate(route_table_delegate_t *delegate) +{ + struct route_table *rt; + + rt = XCALLOC(MTYPE_ROUTE_TABLE, sizeof(struct route_table)); + rt->delegate = delegate; + rn_hash_node_init(&rt->hash); + return rt; +} + +void route_table_finish(struct route_table *rt) +{ + route_table_free(rt); +} + +/* Allocate new route node. */ +static struct route_node *route_node_new(struct route_table *table) +{ + return table->delegate->create_node(table->delegate, table); +} + +/* Allocate new route node with prefix set. */ +static struct route_node *route_node_set(struct route_table *table, + const struct prefix *prefix) +{ + struct route_node *node; + + node = route_node_new(table); + + prefix_copy(&node->p, prefix); + node->table = table; + + rn_hash_node_add(&node->table->hash, node); + + return node; +} + +/* Free route node. */ +static void route_node_free(struct route_table *table, struct route_node *node) +{ + if (table->cleanup) + table->cleanup(table, node); + table->delegate->destroy_node(table->delegate, table, node); +} + +/* Free route table. */ +static void route_table_free(struct route_table *rt) +{ + struct route_node *tmp_node; + struct route_node *node; + + if (rt == NULL) + return; + + node = rt->top; + + /* Bulk deletion of nodes remaining in this table. This function is not + called until workers have completed their dependency on this table. + A final route_unlock_node() will not be called for these nodes. */ + while (node) { + if (node->l_left) { + node = node->l_left; + continue; + } + + if (node->l_right) { + node = node->l_right; + continue; + } + + tmp_node = node; + node = node->parent; + + tmp_node->table->count--; + tmp_node->lock = + 0; /* to cause assert if unlocked after this */ + rn_hash_node_del(&rt->hash, tmp_node); + route_node_free(rt, tmp_node); + + if (node != NULL) { + if (node->l_left == tmp_node) + node->l_left = NULL; + else + node->l_right = NULL; + } else { + break; + } + } + + assert(rt->count == 0); + + rn_hash_node_fini(&rt->hash); + XFREE(MTYPE_ROUTE_TABLE, rt); + return; +} + +/* Utility mask array. */ +static const uint8_t maskbit[] = {0x00, 0x80, 0xc0, 0xe0, 0xf0, + 0xf8, 0xfc, 0xfe, 0xff}; + +/* Common prefix route genaration. */ +static void route_common(const struct prefix *n, const struct prefix *p, + struct prefix *new) +{ + int i; + uint8_t diff; + uint8_t mask; + const uint8_t *np; + const uint8_t *pp; + uint8_t *newp; + + if (n->family == AF_FLOWSPEC) + return prefix_copy(new, p); + np = (const uint8_t *)&n->u.prefix; + pp = (const uint8_t *)&p->u.prefix; + + newp = &new->u.prefix; + + for (i = 0; i < p->prefixlen / 8; i++) { + if (np[i] == pp[i]) + newp[i] = np[i]; + else + break; + } + + new->prefixlen = i * 8; + + if (new->prefixlen != p->prefixlen) { + diff = np[i] ^ pp[i]; + mask = 0x80; + while (new->prefixlen < p->prefixlen && !(mask & diff)) { + mask >>= 1; + new->prefixlen++; + } + newp[i] = np[i] & maskbit[new->prefixlen % 8]; + } +} + +static void set_link(struct route_node *node, struct route_node *new) +{ + unsigned int bit = prefix_bit(&new->p.u.prefix, node->p.prefixlen); + + node->link[bit] = new; + new->parent = node; +} + +/* Find matched prefix. */ +struct route_node *route_node_match(struct route_table *table, + union prefixconstptr pu) +{ + const struct prefix *p = pu.p; + struct route_node *node; + struct route_node *matched; + + matched = NULL; + node = table->top; + + /* Walk down tree. If there is matched route then store it to + matched. */ + while (node && node->p.prefixlen <= p->prefixlen + && prefix_match(&node->p, p)) { + if (node->info) + matched = node; + + if (node->p.prefixlen == p->prefixlen) + break; + + node = node->link[prefix_bit(&p->u.prefix, node->p.prefixlen)]; + } + + /* If matched route found, return it. */ + if (matched) + return route_lock_node(matched); + + return NULL; +} + +struct route_node *route_node_match_ipv4(struct route_table *table, + const struct in_addr *addr) +{ + struct prefix_ipv4 p; + + memset(&p, 0, sizeof(p)); + p.family = AF_INET; + p.prefixlen = IPV4_MAX_BITLEN; + p.prefix = *addr; + + return route_node_match(table, (struct prefix *)&p); +} + +struct route_node *route_node_match_ipv6(struct route_table *table, + const struct in6_addr *addr) +{ + struct prefix_ipv6 p; + + memset(&p, 0, sizeof(p)); + p.family = AF_INET6; + p.prefixlen = IPV6_MAX_BITLEN; + p.prefix = *addr; + + return route_node_match(table, &p); +} + +/* Lookup same prefix node. Return NULL when we can't find route. */ +struct route_node *route_node_lookup(struct route_table *table, + union prefixconstptr pu) +{ + struct route_node rn, *node; + prefix_copy(&rn.p, pu.p); + apply_mask(&rn.p); + + node = rn_hash_node_find(&table->hash, &rn); + return (node && node->info) ? route_lock_node(node) : NULL; +} + +/* Lookup same prefix node. Return NULL when we can't find route. */ +struct route_node *route_node_lookup_maynull(struct route_table *table, + union prefixconstptr pu) +{ + struct route_node rn, *node; + prefix_copy(&rn.p, pu.p); + apply_mask(&rn.p); + + node = rn_hash_node_find(&table->hash, &rn); + return node ? route_lock_node(node) : NULL; +} + +/* Add node to routing table. */ +struct route_node *route_node_get(struct route_table *table, + union prefixconstptr pu) +{ + if (frrtrace_enabled(frr_libfrr, route_node_get)) { + char buf[PREFIX2STR_BUFFER]; + prefix2str(pu, buf, sizeof(buf)); + frrtrace(2, frr_libfrr, route_node_get, table, buf); + } + + struct route_node search; + struct prefix *p = &search.p; + + prefix_copy(p, pu.p); + apply_mask(p); + + struct route_node *new; + struct route_node *node; + struct route_node *match; + uint16_t prefixlen = p->prefixlen; + const uint8_t *prefix = &p->u.prefix; + + node = rn_hash_node_find(&table->hash, &search); + if (node && node->info) + return route_lock_node(node); + + match = NULL; + node = table->top; + while (node && node->p.prefixlen <= prefixlen + && prefix_match(&node->p, p)) { + if (node->p.prefixlen == prefixlen) + return route_lock_node(node); + + match = node; + node = node->link[prefix_bit(prefix, node->p.prefixlen)]; + } + + if (node == NULL) { + new = route_node_set(table, p); + if (match) + set_link(match, new); + else + table->top = new; + } else { + new = route_node_new(table); + route_common(&node->p, p, &new->p); + new->p.family = p->family; + new->table = table; + set_link(new, node); + rn_hash_node_add(&table->hash, new); + + if (match) + set_link(match, new); + else + table->top = new; + + if (new->p.prefixlen != p->prefixlen) { + match = new; + new = route_node_set(table, p); + set_link(match, new); + table->count++; + } + } + table->count++; + route_lock_node(new); + + return new; +} + +/* Delete node from the routing table. */ +void route_node_delete(struct route_node *node) +{ + struct route_node *child; + struct route_node *parent; + + assert(node->lock == 0); + assert(node->info == NULL); + + if (node->l_left && node->l_right) + return; + + if (node->l_left) + child = node->l_left; + else + child = node->l_right; + + parent = node->parent; + + if (child) + child->parent = parent; + + if (parent) { + if (parent->l_left == node) + parent->l_left = child; + else + parent->l_right = child; + } else + node->table->top = child; + + node->table->count--; + + rn_hash_node_del(&node->table->hash, node); + + /* WARNING: FRAGILE CODE! + * route_node_free may have the side effect of free'ing the entire + * table. + * this is permitted only if table->count got decremented to zero above, + * because in that case parent will also be NULL, so that we won't try + * to + * delete a now-stale parent below. + * + * cf. srcdest_srcnode_destroy() in zebra/zebra_rib.c */ + + route_node_free(node->table, node); + + /* If parent node is stub then delete it also. */ + if (parent && parent->lock == 0) + route_node_delete(parent); +} + +/* Get first node and lock it. This function is useful when one wants + to lookup all the node exist in the routing table. */ +struct route_node *route_top(struct route_table *table) +{ + /* If there is no node in the routing table return NULL. */ + if (table->top == NULL) + return NULL; + + /* Lock the top node and return it. */ + route_lock_node(table->top); + return table->top; +} + +/* Unlock current node and lock next node then return it. */ +struct route_node *route_next(struct route_node *node) +{ + struct route_node *next; + struct route_node *start; + + /* Node may be deleted from route_unlock_node so we have to preserve + next node's pointer. */ + + if (node->l_left) { + next = node->l_left; + route_lock_node(next); + route_unlock_node(node); + return next; + } + if (node->l_right) { + next = node->l_right; + route_lock_node(next); + route_unlock_node(node); + return next; + } + + start = node; + while (node->parent) { + if (node->parent->l_left == node && node->parent->l_right) { + next = node->parent->l_right; + route_lock_node(next); + route_unlock_node(start); + return next; + } + node = node->parent; + } + route_unlock_node(start); + return NULL; +} + +/* Unlock current node and lock next node until limit. */ +struct route_node *route_next_until(struct route_node *node, + const struct route_node *limit) +{ + struct route_node *next; + struct route_node *start; + + /* Node may be deleted from route_unlock_node so we have to preserve + next node's pointer. */ + + if (node->l_left) { + next = node->l_left; + route_lock_node(next); + route_unlock_node(node); + return next; + } + if (node->l_right) { + next = node->l_right; + route_lock_node(next); + route_unlock_node(node); + return next; + } + + start = node; + while (node->parent && node != limit) { + if (node->parent->l_left == node && node->parent->l_right) { + next = node->parent->l_right; + route_lock_node(next); + route_unlock_node(start); + return next; + } + node = node->parent; + } + route_unlock_node(start); + return NULL; +} + +unsigned long route_table_count(struct route_table *table) +{ + return table->count; +} + +/** + * route_node_create + * + * Default function for creating a route node. + */ +struct route_node *route_node_create(route_table_delegate_t *delegate, + struct route_table *table) +{ + struct route_node *node; + node = XCALLOC(MTYPE_ROUTE_NODE, sizeof(struct route_node)); + return node; +} + +/** + * route_node_destroy + * + * Default function for destroying a route node. + */ +void route_node_destroy(route_table_delegate_t *delegate, + struct route_table *table, struct route_node *node) +{ + XFREE(MTYPE_ROUTE_NODE, node); +} + +/* + * Default delegate. + */ +static route_table_delegate_t default_delegate = { + .create_node = route_node_create, + .destroy_node = route_node_destroy}; + +route_table_delegate_t *route_table_get_default_delegate(void) +{ + return &default_delegate; +} + +/* + * route_table_init + */ +struct route_table *route_table_init(void) +{ + return route_table_init_with_delegate(&default_delegate); +} + +/** + * route_table_prefix_iter_cmp + * + * Compare two prefixes according to the order in which they appear in + * an iteration over a tree. + * + * @return -1 if p1 occurs before p2 (p1 < p2) + * 0 if the prefixes are identical (p1 == p2) + * +1 if p1 occurs after p2 (p1 > p2) + */ +int route_table_prefix_iter_cmp(const struct prefix *p1, + const struct prefix *p2) +{ + struct prefix common_space; + struct prefix *common = &common_space; + + if (p1->prefixlen <= p2->prefixlen) { + if (prefix_match(p1, p2)) { + + /* + * p1 contains p2, or is equal to it. + */ + return (p1->prefixlen == p2->prefixlen) ? 0 : -1; + } + } else { + + /* + * Check if p2 contains p1. + */ + if (prefix_match(p2, p1)) + return 1; + } + + route_common(p1, p2, common); + assert(common->prefixlen < p1->prefixlen); + assert(common->prefixlen < p2->prefixlen); + + /* + * Both prefixes are longer than the common prefix. + * + * We need to check the bit after the common prefixlen to determine + * which one comes later. + */ + if (prefix_bit(&p1->u.prefix, common->prefixlen)) { + + /* + * We branch to the right to get to p1 from the common prefix. + */ + assert(!prefix_bit(&p2->u.prefix, common->prefixlen)); + return 1; + } + + /* + * We branch to the right to get to p2 from the common prefix. + */ + assert(prefix_bit(&p2->u.prefix, common->prefixlen)); + return -1; +} + +/* + * route_get_subtree_next + * + * Helper function that returns the first node that follows the nodes + * in the sub-tree under 'node' in iteration order. + */ +static struct route_node *route_get_subtree_next(struct route_node *node) +{ + while (node->parent) { + if (node->parent->l_left == node && node->parent->l_right) + return node->parent->l_right; + + node = node->parent; + } + + return NULL; +} + +/** + * route_table_get_next_internal + * + * Helper function to find the node that occurs after the given prefix in + * order of iteration. + * + * @see route_table_get_next + */ +static struct route_node * +route_table_get_next_internal(struct route_table *table, + const struct prefix *p) +{ + struct route_node *node, *tmp_node; + int cmp; + + node = table->top; + + while (node) { + int match; + + if (node->p.prefixlen < p->prefixlen) + match = prefix_match(&node->p, p); + else + match = prefix_match(p, &node->p); + + if (match) { + if (node->p.prefixlen == p->prefixlen) { + + /* + * The prefix p exists in the tree, just return + * the next + * node. + */ + route_lock_node(node); + node = route_next(node); + if (node) + route_unlock_node(node); + + return (node); + } + + if (node->p.prefixlen > p->prefixlen) { + + /* + * Node is in the subtree of p, and hence + * greater than p. + */ + return node; + } + + /* + * p is in the sub-tree under node. + */ + tmp_node = node->link[prefix_bit(&p->u.prefix, + node->p.prefixlen)]; + + if (tmp_node) { + node = tmp_node; + continue; + } + + /* + * There are no nodes in the direction where p should + * be. If + * node has a right child, then it must be greater than + * p. + */ + if (node->l_right) + return node->l_right; + + /* + * No more children to follow, go upwards looking for + * the next + * node. + */ + return route_get_subtree_next(node); + } + + /* + * Neither node prefix nor 'p' contains the other. + */ + cmp = route_table_prefix_iter_cmp(&node->p, p); + if (cmp > 0) { + + /* + * Node follows p in iteration order. Return it. + */ + return node; + } + + assert(cmp < 0); + + /* + * Node and the subtree under it come before prefix p in + * iteration order. Prefix p and its sub-tree are not present in + * the tree. Go upwards and find the first node that follows the + * subtree. That node will also succeed p. + */ + return route_get_subtree_next(node); + } + + return NULL; +} + +/** + * route_table_get_next + * + * Find the node that occurs after the given prefix in order of + * iteration. + */ +struct route_node *route_table_get_next(struct route_table *table, + union prefixconstptr pu) +{ + const struct prefix *p = pu.p; + struct route_node *node; + + node = route_table_get_next_internal(table, p); + if (node) { + assert(route_table_prefix_iter_cmp(&node->p, p) > 0); + route_lock_node(node); + } + return node; +} + +/* + * route_table_iter_init + */ +void route_table_iter_init(route_table_iter_t *iter, struct route_table *table) +{ + memset(iter, 0, sizeof(*iter)); + iter->state = RT_ITER_STATE_INIT; + iter->table = table; +} + +/* + * route_table_iter_pause + * + * Pause an iteration over the table. This allows the iteration to be + * resumed point after arbitrary additions/deletions from the table. + * An iteration can be resumed by just calling route_table_iter_next() + * on the iterator. + */ +void route_table_iter_pause(route_table_iter_t *iter) +{ + switch (iter->state) { + + case RT_ITER_STATE_INIT: + case RT_ITER_STATE_PAUSED: + case RT_ITER_STATE_DONE: + return; + + case RT_ITER_STATE_ITERATING: + + /* + * Save the prefix that we are currently at. The next call to + * route_table_iter_next() will return the node after this + * prefix + * in the tree. + */ + prefix_copy(&iter->pause_prefix, &iter->current->p); + route_unlock_node(iter->current); + iter->current = NULL; + iter->state = RT_ITER_STATE_PAUSED; + return; + + default: + assert(0); + } +} + +/* + * route_table_iter_cleanup + * + * Release any resources held by the iterator. + */ +void route_table_iter_cleanup(route_table_iter_t *iter) +{ + if (iter->state == RT_ITER_STATE_ITERATING) { + route_unlock_node(iter->current); + iter->current = NULL; + } + assert(!iter->current); + + /* + * Set the state to RT_ITER_STATE_DONE to make any + * route_table_iter_next() calls on this iterator return NULL. + */ + iter->state = RT_ITER_STATE_DONE; +} |