/* 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);

}

}