summaryrefslogtreecommitdiff
path: root/lib
diff options
context:
space:
mode:
authorPaul Jakma <paul@quagga.net>2010-04-13 22:42:33 +0100
committerPaul Jakma <paul@quagga.net>2010-12-08 17:06:12 +0000
commitf8416810aad4cba6f622c6b3f9352abdd54cd01e (patch)
tree7ca0d68cd44ea6c0b4d838f6526b3ccadcb836f9 /lib
parentd358344759d85a965bbd767f4a994695f99b842e (diff)
lib: Fix bug in prefix trie lookup
* lib/table.c: (route_node_match) fix overshoot that was causing this function to go 1 bit too far and thus reading past end of prefix. (route_node_lookup) be defensive - don't assume others will clean up leaves when removing info.
Diffstat (limited to 'lib')
-rw-r--r--lib/table.c14
1 files changed, 8 insertions, 6 deletions
diff --git a/lib/table.c b/lib/table.c
index 04df3af5..e40e6707 100644
--- a/lib/table.c
+++ b/lib/table.c
@@ -209,6 +209,10 @@ route_node_match (const struct route_table *table, const struct prefix *p)
{
if (node->info)
matched = node;
+
+ if (node->p.prefixlen == p->prefixlen)
+ break;
+
node = node->link[prefix_bit(&p->u.prefix, node->p.prefixlen)];
}
@@ -260,8 +264,8 @@ route_node_lookup (struct route_table *table, struct prefix *p)
while (node && node->p.prefixlen <= p->prefixlen &&
prefix_match (&node->p, p))
{
- if (node->p.prefixlen == p->prefixlen && node->info)
- return route_lock_node (node);
+ if (node->p.prefixlen == p->prefixlen)
+ return node->info ? route_lock_node (node) : NULL;
node = node->link[prefix_bit(&p->u.prefix, node->p.prefixlen)];
}
@@ -283,10 +287,8 @@ route_node_get (struct route_table *table, struct prefix *p)
prefix_match (&node->p, p))
{
if (node->p.prefixlen == p->prefixlen)
- {
- route_lock_node (node);
- return node;
- }
+ return route_lock_node (node);
+
match = node;
node = node->link[prefix_bit(&p->u.prefix, node->p.prefixlen)];
}