net/lwip/rttree.c

/* LWIP service - rttree.c - generic routing tree data structure */
/*
 * This module implements the Net/3 binary radix (Patricia) tree as described
 * in TCP/IP Illustrated Vol.2, with a few important changes.  First and
 * foremost, we make the assumption that all address masks are "normal", i.e.,
 * they can be expressed in terms of a "prefix length" or "bit count", meaning
 * that the first so many bits of the mask are set and the remaining bits are
 * all clear.  Based on this assumption, we store routing entries not just in
 * leaf nodes, but rather in a node at the bit count of the routing entry's
 * mask; this node may then also have children.  As a result, instead of "leaf"
 * and "internal" nodes, this module instead uses "data" and "link" nodes:
 *
 * - Data nodes are nodes with an associated routing entry.  The data node
 *   structure is always the first field of its corresponding routing entry
 *   structure.  Data nodes may have zero, one, or two children.  Its children
 *   are always a refinement of the address mask in the routing entry.
 * - Link nodes are nodes with no associated routing entry.  They always have
 *   exactly two children.  As with BSD's "internal" nodes: since the tree
 *   needs no more than one link node per routing entry, each routing entry
 *   structure contains a link node, which may be used anywhere in the tree.
 *
 * The result of this approach is that we do not use a linked list for each
 * leaf, since entries with the same address and different masks are not stored
 * as part of the same leaf node.  There is however still one case where a
 * linked list would be necessary: the coexistence of a full-mask network entry
 * and a host entry (net/32 vs host for IPv4, net/128 vs host for IPv6).  Since
 * this tree implementation is not used for ARP/ND6 (host) entries, the need to
 * support that case is not as high, and so it is currently not supported.  It
 * can be added later if needed.  In that case, the prototype of only
 * rttree_find_exact() will have to be changed, since rttree_add() already
 * supports the difference by passing a full mask vs passing no mask at all.
 *
 * There are other differences with the BSD implementation, and certainly also
 * more opportunities for improving performance.  For now, the implementation
 * should be good enough for its intended purpose.
 */

#include "lwip.h"
#include "rttree.h"

#define RTTREE_BITS_TO_BYTE(bits)	((bits) >> 3)
#define RTTREE_BITS_TO_SHIFT(bits)	(7 - ((bits) & 7))
#define RTTREE_BITS_TO_BYTES(bits)	(RTTREE_BITS_TO_BYTE((bits) + 7))

/*
 * The given node is being added to the given routing tree, and just had its
 * bit count assigned.  Precompute any additional fields used for fast address
 * access on the node.
 */
static void
rttree_precompute(struct rttree * tree __unused, struct rttree_node * node)
{

	node->rtn_byte = RTTREE_BITS_TO_BYTE(node->rtn_bits);
	node->rtn_shift = RTTREE_BITS_TO_SHIFT(node->rtn_bits);
}

/*
 * For an operation on the routing tree 'tree', test whether the bit 'bit' is
 * set or clear in 'addr'.  Return 1 if the address has the bit set, 0 if it
 * does not.
 */
static unsigned int
rttree_test(const struct rttree * tree __unused, const void * addr,
	unsigned int bit)
{
	unsigned int byte, shift;

	byte = RTTREE_BITS_TO_BYTE(bit);
	shift = RTTREE_BITS_TO_SHIFT(bit);

	return (((const uint8_t *)addr)[byte] >> shift) & 1;
}

/*
 * For an operation on the routing tree 'tree', test whether a particular bit
 * as identified by the routing node 'node' is set or clear in 'address',
 * effectively computing the side (left or right) to take when descending down
 * the tree.  Return 1 if the address has the bit set, 0 if it does not.
 */
static inline unsigned int
rttree_side(const struct rttree * tree, const struct rttree_node * node,
	const void * addr)
{

	return (((const uint8_t *)addr)[node->rtn_byte] >>
	    node->rtn_shift) & 1;
}

/*
 * Check for the routing tree 'tree' whether the routing entry 'entry' matches
 * the address 'addr' exactly.  Return TRUE or FALSE depending on the outcome.
 * This function must be called only on entries that have already been
 * determined to span the full bit width.
 */
static inline int
rttree_equals(const struct rttree * tree, const struct rttree_entry * entry,
	const void * addr)
{
	unsigned int bits;

	bits = tree->rtt_bits;

	assert(bits == entry->rte_data.rtn_bits);

	return !memcmp(entry->rte_addr, addr, RTTREE_BITS_TO_BYTE(bits));
}

/*
 * Check for the routing tree 'tree' whether the routing entry 'entry' matches
 * the address 'addr'.  Return TRUE if the address is matched by the entry's
 * address and mask, or FALSE if not.
 */
static inline int
rttree_match(const struct rttree * tree, const struct rttree_entry * entry,
	const void * addr)
{
	const uint8_t *aptr, *aptr2, *mptr;
	unsigned int bits, bytes;

	if ((bits = entry->rte_data.rtn_bits) == 0)
		return TRUE;

	if ((mptr = (const uint8_t *)entry->rte_mask) == NULL)
		return rttree_equals(tree, entry, addr);

	aptr = (const uint8_t *)addr;
	aptr2 = (const uint8_t *)entry->rte_addr;

	for (bytes = RTTREE_BITS_TO_BYTES(bits); bytes > 0; bytes--) {
		if ((*aptr & *mptr) != *aptr2)
			return FALSE;

		aptr++;
		aptr2++;
		mptr++;
	}

	return TRUE;
}

/*
 * Find the first bit that differs between the two given addresses.  Return the
 * bit number if found, or the full bit width if the addresses are equal.
 */
static unsigned int
rttree_diff(const struct rttree * tree, const void * addr, const void * addr2)
{
	const uint8_t *aptr, *aptr2;
	unsigned int bit, i;
	uint8_t b;

	aptr = (const uint8_t *)addr;
	aptr2 = (const uint8_t *)addr2;

	for (bit = 0; bit < tree->rtt_bits; bit += NBBY, aptr++, aptr2++) {
		if ((b = *aptr ^ *aptr2) != 0) {
			for (i = 0; i < NBBY; i++)
				if (b & (1 << (NBBY - i - 1)))
					break;
			return bit + i;
		}
	}

	return bit;
}

/*
 * Add a link node to the free list of the given routing tree, marking it as
 * free in the process.
 */
static void
rttree_add_free(struct rttree * tree, struct rttree_node * node)
{

	node->rtn_child[0] = NULL;
	if ((node->rtn_child[1] = tree->rtt_free) != NULL)
		node->rtn_child[1]->rtn_child[0] = node;
	tree->rtt_free = node;
	node->rtn_parent = NULL;
	node->rtn_type = RTNT_FREE;
}

/*
 * Remove the given free link node from the free list.  The caller must already
 * have verified that the node is on the free list, and has to change the node
 * type as appropriate afterward.
 */
static void
rttree_del_free(struct rttree * tree, struct rttree_node * node)
{

	assert(node->rtn_type == RTNT_FREE);

	if (node->rtn_child[0] != NULL)
		node->rtn_child[0]->rtn_child[1] = node->rtn_child[1];
	else
		tree->rtt_free = node->rtn_child[1];
	if (node->rtn_child[1] != NULL)
		node->rtn_child[1]->rtn_child[0] = node->rtn_child[0];
}

/*
 * Obtain, remove, and return a free link node from the free list.  This
 * function must be called only when it is already known that the free list is
 * not empty.  The caller has to change the node type as appropriate afterward.
 */
static struct rttree_node *
rttree_get_free(struct rttree * tree)
{
	struct rttree_node * node;

	node = tree->rtt_free;
	assert(node != NULL);
	assert(node->rtn_type == RTNT_FREE);

	rttree_del_free(tree, node);

	return node;
}

/*
 * Initialize the given routing tree, with the given address bit width.
 */
void
rttree_init(struct rttree * tree, unsigned int bits)
{

	tree->rtt_root = NULL;
	tree->rtt_free = NULL;
	tree->rtt_bits = bits;
}

/*
 * Look up the most narrow routing tree entry that matches the given address.
 * Return the entry on success, or NULL if no matching entry is found.
 */
struct rttree_entry *
rttree_lookup_match(struct rttree * tree, const void * addr)
{
	struct rttree_entry *entry, *best;
	struct rttree_node *node;
	unsigned int side;

	/*
	 * The current implementation is "forward-tracking", testing all
	 * potentially matching entries while descending into the tree and
	 * remembering the "best" (narrowest matching) entry.  The assumption
	 * here is that most lookups will end up returning the default route or
	 * another broad route, and thus quickly fail a narrower match and bail
	 * out early.  This assumption is in part motivated by the fact that
	 * our routing trees do not store link-layer (ARP/ND6) entries.  If
	 * desired, the implementation can easily be rewritten to do
	 * backtracking instead.
	 */
	best = NULL;

	for (node = tree->rtt_root; node != NULL;
	    node = node->rtn_child[side]) {
		if (node->rtn_type == RTNT_DATA) {
			entry = (struct rttree_entry *)node;

			if (!rttree_match(tree, entry, addr))
				break;

			best = entry;
		}

		side = rttree_side(tree, node, addr);
	}

	return best;
}

/*
 * Look up a routing entry that is an exact match for the given (full) address.
 * Return the entry if it was found, or NULL otherwise.
 */
struct rttree_entry *
rttree_lookup_host(struct rttree * tree, const void * addr)
{
	struct rttree_entry *entry;
	struct rttree_node *node;
	unsigned int side;

	for (node = tree->rtt_root; node != NULL;
	    node = node->rtn_child[side]) {
		if (node->rtn_type == RTNT_DATA &&
		    node->rtn_bits == tree->rtt_bits) {
			entry = (struct rttree_entry *)node;

			if (rttree_equals(tree, entry, addr))
				return entry;

			break;
		}

		side = rttree_side(tree, node, addr);
	}

	return NULL;
}

/*
 * Look up a routing entry that is an exact match for the given address and
 * prefix length.  Return the entry if found, or NULL otherwise.
 */
struct rttree_entry *
rttree_lookup_exact(struct rttree * tree, const void * addr,
	unsigned int prefix)
{
	struct rttree_entry *entry;
	struct rttree_node *node;
	unsigned int side;

	for (node = tree->rtt_root; node != NULL && node->rtn_bits <= prefix;
	    node = node->rtn_child[side]) {
		if (node->rtn_type == RTNT_DATA) {
			entry = (struct rttree_entry *)node;

			if (!rttree_match(tree, entry, addr))
				return NULL;

			if (node->rtn_bits == prefix)
				return entry;
		}

		side = rttree_side(tree, node, addr);
	}

	return NULL;
}

/*
 * Enumerate entries in the routing tree.  If 'last' is NULL, return the first
 * entry.  Otherwise, return the next entry starting from 'last'.  In both
 * cases, if no (more) entries are present in the tree, return NULL.  The order
 * of the returned entries is stable across tree modifications and the function
 * may be called multiple times on the same entry.  More specifically, it is
 * safe to continue enumeration from a previous entry after deleting its
 * successor from the tree.
 */
struct rttree_entry *
rttree_enum(struct rttree * tree, struct rttree_entry * last)
{
	struct rttree_node *node, *parent;

	/*
	 * For the first query, we may have to return the tree root right away.
	 * For subsequent queries, we have to move ahead by at least one node.
	 */
	if (last == NULL) {
		if ((node = tree->rtt_root) == NULL)
			return NULL;

		if (node->rtn_type == RTNT_DATA)
			return (struct rttree_entry *)node;
	} else
		node = &last->rte_data;

	/* A basic iterative pre-order binary-tree depth-first search. */
	do {
		assert(node != NULL);

		/* Can we descend further, either left or right? */
		if (node->rtn_child[0] != NULL)
			node = node->rtn_child[0];
		else if (node->rtn_child[1] != NULL)
			node = node->rtn_child[1];
		else {
			/*
			 * No.  Go back up the tree, until we can go right
			 * where we went left before.. or run out of tree.
			 */
			for (;; node = parent) {
				if ((parent = node->rtn_parent) == NULL)
					return NULL;

				if (parent->rtn_child[0] == node &&
				    parent->rtn_child[1] != NULL) {
					node = parent->rtn_child[1];

					break;
				}
			}
		}

		/* Skip link nodes. */
	} while (node->rtn_type != RTNT_DATA);

	return (struct rttree_entry *)node;
}

/*
 * Set the node 'node' to be part of tree 'tree', with type 'type' (either
 * RTNT_DATA or RTNT_LINK) and a bit count of 'prefix'.  The node is set to be
 * a child of 'parent' on side 'side', unless 'parent' is NULL in which case
 * the node is set to be the topmost node in the tree (and 'side' is ignored).
 * The node's children are set to 'left' and 'right'; for each, if not NULL,
 * its parent is set to 'node'.
 */
static void
rttree_set(struct rttree * tree, struct rttree_node * node, int type,
	unsigned int prefix, struct rttree_node * parent, int side,
	struct rttree_node * left, struct rttree_node * right)
{

	assert(type == RTNT_DATA || type == RTNT_LINK);
	assert(prefix <= tree->rtt_bits);
	assert(side == 0 || side == 1);

	node->rtn_type = type;
	node->rtn_bits = prefix;

	/* With rtn_bits assigned, precompute any derived fields. */
	rttree_precompute(tree, node);

	if ((node->rtn_parent = parent) != NULL)
		parent->rtn_child[side] = node;
	else
		tree->rtt_root = node;

	if ((node->rtn_child[0] = left) != NULL)
		left->rtn_parent = node;
	if ((node->rtn_child[1] = right) != NULL)
		right->rtn_parent = node;
}

/*
 * In the routing tree 'tree', replace old node 'onode' with new node 'node',
 * setting the type of the latter to 'type'.  The tree is updated accordingly,
 * but it is left up to the caller to deal with the old node as appropriate.
 */
static void
rttree_replace(struct rttree * tree, struct rttree_node * onode,
	struct rttree_node * node, int type)
{
	struct rttree_node *parent;
	unsigned int side;

	/*
	 * Replacing one data node with another data node is not something that
	 * is currently being done, even if it would work.
	 */
	assert(onode->rtn_type != RTNT_DATA || node->rtn_type != RTNT_DATA);
	assert(onode->rtn_child[0] != NULL);
	assert(onode->rtn_child[1] != NULL);

	parent = onode->rtn_parent;

	side = (parent != NULL && parent->rtn_child[1] == onode);

	rttree_set(tree, node, type, onode->rtn_bits, parent, side,
	    onode->rtn_child[0], onode->rtn_child[1]);
}

/*
 * Add a new routing entry 'entry' to the routing tree 'tree'.  The entry
 * object will be initialized as a result.  The address to add is given as
 * 'addr', and the address mask as 'mask'.  Both those pointers must be point
 * to memory that is as long-lived as the routing entry; this is typically
 * accomplished by storing them in a larger object that embeds 'entry'.
 * However, 'mask' may be NULL, signifying a host type entry with an implied
 * full mask.  If not NULL, the given mask must be normalized, i.e., it must
 * consist of a run of zero or more 1-bits followed by a remainder of only
 * 0-bits.  The number of 1-bits must also be given as a bit count 'prefix',
 * even if 'mask' is NULL.  The address must be normalized to its mask: no bits
 * starting from bit 'prefix' must be set in 'addr'.  Return OK if adding the
 * routing entry succeeded, or EEXIST if an entry already exists for the
 * combination of that address and mask.  If the caller has already verified
 * with rttree_lookup_exact() that no such entry exists, the call will succeed.
 */
int
rttree_add(struct rttree * tree, struct rttree_entry * entry,
	const void * addr, const void * mask, unsigned int prefix)
{
	struct rttree_node *node, *parent, *link;
	struct rttree_entry *other_entry;
	unsigned int bit, side, side2;
	int match;

	assert(mask != NULL || prefix == tree->rtt_bits);

	/*
	 * We start by determining the path, bit count, and method of the
	 * addition.  We do this with a lookup on the address, for the full
	 * address width--that is, not limited to the given prefix length.  As
	 * a result, at some point we will find either a NULL pointer, or a
	 * data node with a width that is at least as large as the given prefix
	 * length.  The NULL case is easy: we EXTEND the tree with our new
	 * entry wherever we ran into the NULL pointer.
	 *
	 * If instead we find a sufficiently wide data node, then we see if it
	 * is a match for the new address.  If so, our new data node should
	 * either be INSERTed between two nodes along the path taken so far, or
	 * REPLACE a link node along that path with the new data node.  If it
	 * it is not a match, then the action to take depends on whether the
	 * first differing bit falls within the given prefix length: if so, we
	 * have to BRANCH along the path, using a link node allocated for that
	 * differing bit; if not, we should use INSERT or REPLACE after all.
	 *
	 * As the only exceptional case, we might in fact find an entry for the
	 * exact same address and prefix length as what is being added.  In the
	 * current design of the routing tree, this is always a failure case.
	 */
	parent = NULL;
	side = 0;
	other_entry = NULL;

	for (node = tree->rtt_root; node != NULL;
	    node = node->rtn_child[side]) {
		if (node->rtn_type == RTNT_DATA) {
			other_entry = (struct rttree_entry *)node;

			bit = rttree_diff(tree, other_entry->rte_addr, addr);

			match = (bit >= node->rtn_bits);

			/* Test whether the exact entry already exists. */
			if (match && node->rtn_bits == prefix)
				return EEXIST;

			/*
			 * Test the INSERT/REPLACE and BRANCH cases.  Note that
			 * this condition is in a terse, optimized form that
			 * does not map directly to the two different cases.
			 */
			if (!match || node->rtn_bits > prefix) {
				if (bit > prefix)
					bit = prefix;
				break;
			}
		}

		parent = node;
		side = rttree_side(tree, node, addr);
	}

	/*
	 * At this point, addition is going to succeed no matter what.  Start
	 * by initializing part of 'entry'.  In particular, add the given
	 * entry's link node to the list of free link nodes, because the common
	 * case is that we end up not using it.  If we do, we will just take it
	 * off again right away.  The entry's data node will be initialized as
	 * part of the addition process below.
	 */
	entry->rte_addr = addr;
	entry->rte_mask = mask;

	rttree_add_free(tree, &entry->rte_link);

	/*
	 * First deal with the EXTEND case.  In that case we already know the
	 * intended parent and the side (left/right) for the addition.
	 */
	if (node == NULL) {
		assert(parent == NULL || parent->rtn_bits < prefix);
		assert(parent == NULL || parent->rtn_child[side] == NULL);

		rttree_set(tree, &entry->rte_data, RTNT_DATA, prefix, parent,
		    side, NULL /*left*/, NULL /*right*/);

		return OK;
	}

	/*
	 * For the other three cases, we now have to walk back along the path
	 * we have taken so far in order to find the correct insertion point.
	 */
	while (parent != NULL && parent->rtn_bits >= bit) {
		node = parent;

		parent = node->rtn_parent;
	}

	if (bit == prefix && node->rtn_bits == bit) {
		/*
		 * The REPLACE case.  Replace the link node 'node' with our new
		 * entry.  Afterwards, mark the link node as free.
		 */
		assert(node->rtn_type != RTNT_DATA);

		rttree_replace(tree, node, &entry->rte_data, RTNT_DATA);

		rttree_add_free(tree, node);
	} else if (bit == prefix) {
		/*
		 * The INSERT case.  Insert the data node between 'parent' and
		 * 'node'.  Note that 'parent' may be NULL.  We need to use the
		 * address we found earlier, as 'other_entry', to determine
		 * whether we should add 'node' to the left or right of the
		 * inserted data node.
		 */
		assert(node->rtn_bits > bit);
		assert(parent == NULL || parent->rtn_bits < bit);
		assert(other_entry != NULL);

		side = (parent != NULL && parent->rtn_child[1] == node);

		side2 = rttree_test(tree, other_entry->rte_addr, bit);

		rttree_set(tree, &entry->rte_data, RTNT_DATA, prefix, parent,
		    side, (!side2) ? node : NULL, (side2) ? node : NULL);
	} else {
		/*
		 * The BRANCH case.  In this case, it is impossible that we
		 * find a link node with a bit count equal to the first
		 * differing bit between the address we found and the address
		 * we want to insert: if such a node existed, we would have
		 * descended down its other child during the initial lookup.
		 *
		 * Interpose a link node between 'parent' and 'current' for bit
		 * 'bit', with its other child set to point to 'entry'.  Again,
		 * we need to perform an additional bit test here, because even
		 * though we know that the address we found during the lookup
		 * differs from the given address at bit 'bit', we do not know
		 * the value of either bit yet.
		 */
		assert(bit < prefix);
		assert(node->rtn_bits > bit);
		assert(parent == NULL || parent->rtn_bits < bit);

		link = rttree_get_free(tree);

		side = (parent != NULL && parent->rtn_child[1] == node);

		side2 = rttree_test(tree, addr, bit);

		/* Use NULL for the data node we are about to add. */
		rttree_set(tree, link, RTNT_LINK, bit, parent, side,
		    (side2) ? node : NULL, (!side2) ? node : NULL);

		/* This addition will replace the NULL pointer again. */
		rttree_set(tree, &entry->rte_data, RTNT_DATA, prefix, link,
		    side2, NULL /*left*/, NULL /*right*/);
	}

	return OK;
}

/*
 * Remove a particular node 'node' from the routing tree 'tree'.  The given
 * node must have zero or one children.  As integrity check only, if 'nonempty'
 * is set, the node must have one child.  If the node has one child, that child
 * will be linked to the node's parent (or the tree root), thus cutting the
 * node itself out of the tree.  If the node has zero children, the
 * corresponding slot in its parent (or the tree root) will be cleared.  The
 * function will return a pointer to the parent node if it too qualifies for
 * removal afterwards, or NULL if no further removal action needs to be taken.
 */
static struct rttree_node *
rttree_remove(struct rttree * tree, struct rttree_node * node,
	int nonempty __unused)
{
	struct rttree_node *parent, *child;
	unsigned int side;

	if ((child = node->rtn_child[0]) == NULL)
		child = node->rtn_child[1];

	assert(child != NULL || !nonempty);

	if ((parent = node->rtn_parent) != NULL) {
		side = (parent->rtn_child[1] == node);

		parent->rtn_child[side] = child;

		if (child != NULL)
			child->rtn_parent = parent;
		else if (parent->rtn_type == RTNT_LINK)
			return parent;
	} else {
		tree->rtt_root = child;

		if (child != NULL)
			child->rtn_parent = NULL;
	}

	return NULL;
}

/*
 * Delete the routing entry 'entry' from the routing tree 'tree'.  The entry
 * must have been added before.  This function always succeeds.
 */
void
rttree_delete(struct rttree * tree, struct rttree_entry * entry)
{
	struct rttree_node *node, *link;

	/*
	 * Remove the data node from the tree.  If the data node also has two
	 * children, we have to replace it with a link node.  Otherwise, we
	 * have to remove it and, if it has no children at all, possibly remove
	 * its parent as well.
	 */
	node = &entry->rte_data;

	assert(node->rtn_type == RTNT_DATA);

	if (node->rtn_child[0] != NULL && node->rtn_child[1] != NULL) {
		/*
		 * The link node we allocate here may actually be the entry's
		 * own link node.  We do not make an exception for that case
		 * here, as we have to deal with the entry's link node being in
		 * use a bit further down anyway.
		 */
		link = rttree_get_free(tree);

		rttree_replace(tree, node, link, RTNT_LINK);
	} else {
		/*
		 * Remove the data node from the tree.  If the node has no
		 * children, its removal may leave a link node with one child.
		 * That would be its original parent.  That node must then also
		 * be removed from the tree, and freed up.
		 */
		link = rttree_remove(tree, node, FALSE /*nonempty*/);

		if (link != NULL) {
			(void)rttree_remove(tree, link, TRUE /*nonempty*/);

			rttree_add_free(tree, link);
		}
	}

	/*
	 * Remove the entry's link node from either the tree or the free list,
	 * depending on the type currently assigned to it.  If it has to be
	 * removed from the tree, it must be replaced with another link node.
	 * There will always be enough link nodes available for this to work.
	 */
	node = &entry->rte_link;

	if (node->rtn_type == RTNT_LINK) {
		link = rttree_get_free(tree);

		rttree_replace(tree, node, link, RTNT_LINK);
	} else {
		assert(node->rtn_type == RTNT_FREE);

		rttree_del_free(tree, node);
	}
}