From f8416810aad4cba6f622c6b3f9352abdd54cd01e Mon Sep 17 00:00:00 2001 From: Paul Jakma Date: Tue, 13 Apr 2010 22:42:33 +0100 Subject: 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. --- lib/table.c | 14 ++++++++------ 1 file 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)]; } -- cgit v1.2.1