From 6238a59a571b6cab4e791d039f410928cc0e4c3f Mon Sep 17 00:00:00 2001 From: Daniel Borkmann Date: Mon, 28 Jan 2013 17:35:51 +0100 Subject: [PATCH] patricia, trie: minor: do some cleanups Signed-off-by: Daniel Borkmann --- patricia.c | 83 +++++++++++++++++++++++++++++++++++++++----------------------- patricia.h | 2 -- trie.c | 5 +--- 3 files changed, 53 insertions(+), 37 deletions(-) diff --git a/patricia.c b/patricia.c index c56cea71..b58fa63e 100644 --- a/patricia.c +++ b/patricia.c @@ -17,13 +17,15 @@ #include "built_in.h" #include "xmalloc.h" -static unsigned char mbit[] = {0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01}; +static const unsigned char mbit[] = { 0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01 }; static inline int testbit(char *str, size_t slen, int bitplace) { int maskptr; + if ((maskptr = bitplace >> 3) > slen) return 0; + return (str[maskptr] & mbit[bitplace & 7]); } @@ -31,46 +33,53 @@ static inline int testbit_max(char *str, int bitplace, int maxbitplace) { if (bitplace >= maxbitplace) return 0; + return (str[bitplace >> 3] & mbit[bitplace & 7]); } static int where_the_bit_differ(char *str1, size_t l1, char *str2, size_t l2) { int p = 0, bitloc; + while (str1[p] == str2[p]) p++; + bitloc = p * 8; - while (testbit(str1, l1, bitloc) == - testbit(str2, l2, bitloc)) + + while (testbit(str1, l1, bitloc) == testbit(str2, l2, bitloc)) bitloc++; + return bitloc; } static struct patricia_node *new_node(void) { struct patricia_node *n = xzmalloc(sizeof(*n)); + n->l = n->r = NULL; + return n; } static void free_node(struct patricia_node *n) { - if (n->key) - xfree(n->key); - if (n->addr) - xfree(n->addr); + free(n->key); + free(n->addr); xfree(n); } void ptree_display(struct patricia_node *node, int level) { int i; + for (i = 0; i < level; ++i) printf("-"); + if (node->l == NULL && node->r == NULL) printf("leaf: (%s -> %d)\n", (char *) node->key, node->value.data); else { printf("thres: %d\n", node->value.thres_bit); + if (node->l != NULL) ptree_display(node->l, level + 1); if (node->r != NULL) @@ -83,6 +92,7 @@ void ptree_get_key(int data, struct patricia_node *node, { if (!node) return; + if (node->l == NULL && node->r == NULL) { if (node->value.data == data) (*wanted) = node; @@ -99,6 +109,7 @@ void ptree_get_key_addr(struct sockaddr_storage *addr, size_t alen, { if (!node) return; + if (node->l == NULL && node->r == NULL) { if (!memcmp(node->addr, addr, node->alen)) (*wanted) = node; @@ -110,22 +121,22 @@ void ptree_get_key_addr(struct sockaddr_storage *addr, size_t alen, } } -static int ptree_search_data_r(struct patricia_node *node, char *str, - size_t slen, struct sockaddr_storage *addr, - size_t *alen, int maxbitplace) +static int ptree_search_data_r(struct patricia_node *node, char *str, size_t slen, + struct sockaddr_storage *addr, size_t *alen, int maxbitplace) { if (node->l == NULL && node->r == NULL) { if (node->addr && addr) memcpy(addr, node->addr, node->alen); + (*alen) = node->alen; + return node->value.data; } + if (testbit_max(str, node->value.thres_bit, maxbitplace) != 0) - return ptree_search_data_r(node->r, str, slen, addr, - alen, maxbitplace); + return ptree_search_data_r(node->r, str, slen, addr, alen, maxbitplace); else - return ptree_search_data_r(node->l, str, slen, addr, - alen, maxbitplace); + return ptree_search_data_r(node->l, str, slen, addr, alen, maxbitplace); } static int *ptree_search_data_r_p(struct patricia_node *node, char *str, @@ -133,6 +144,7 @@ static int *ptree_search_data_r_p(struct patricia_node *node, char *str, { if (node->l == NULL && node->r == NULL) return &(node->value.data); + if (testbit_max(str, node->value.thres_bit, maxbitplace) != 0) return ptree_search_data_r_p(node->r, str, slen, maxbitplace); else @@ -147,17 +159,18 @@ static int ptree_search_data_r_x(struct patricia_node *node, char *str, if (node->klen == slen && !memcmp(str, node->key, node->klen)) { if (node->addr && addr) memcpy(addr, node->addr, node->alen); + (*alen) = node->alen; + return node->value.data; } else return -ENOENT; } + if (testbit_max(str, node->value.thres_bit, maxbitplace) != 0) - return ptree_search_data_r_x(node->r, str, slen, addr, - alen, maxbitplace); + return ptree_search_data_r_x(node->r, str, slen, addr, alen, maxbitplace); else - return ptree_search_data_r_x(node->l, str, slen, addr, - alen, maxbitplace); + return ptree_search_data_r_x(node->l, str, slen, addr, alen, maxbitplace); } int ptree_search_data_nearest(void *str, size_t sstr, struct sockaddr_storage *addr, @@ -165,6 +178,7 @@ int ptree_search_data_nearest(void *str, size_t sstr, struct sockaddr_storage *a { if (!root) return -ENOENT; + return ptree_search_data_r(root, str, sstr, addr, alen, sstr * 8); } @@ -179,6 +193,7 @@ int ptree_search_data_exact(void *str, size_t sstr, struct sockaddr_storage *add { if (!root) return -ENOENT; + return ptree_search_data_r_x(root, str, sstr, addr, alen, sstr * 8); } @@ -187,6 +202,7 @@ static struct patricia_node *ptree_make_root_node(char *str, size_t sstr, size_t alen) { struct patricia_node *n = new_node(); + n->value.data = data; n->key = xmemdupz(str, sstr); n->klen = sstr; @@ -195,6 +211,7 @@ static struct patricia_node *ptree_make_root_node(char *str, size_t sstr, else n->addr = NULL; n->alen = alen; + return n; } @@ -203,14 +220,15 @@ static void ptree_add_entry_at(char *str, size_t slen, int bitloc, int data, struct patricia_node **parentlink) { struct patricia_node *node = (*parentlink); - if (node->value.thres_bit > bitloc || - (node->l == NULL && node->r == NULL)) { + + if (node->value.thres_bit > bitloc || (node->l == NULL && node->r == NULL)) { struct patricia_node *newleaf, *newbranch; newleaf = new_node(); newleaf->value.data = data; newleaf->key = xmemdupz(str, slen); newleaf->klen = slen; + if (addr) newleaf->addr = xmemdupz(addr, alen); else @@ -220,6 +238,7 @@ static void ptree_add_entry_at(char *str, size_t slen, int bitloc, int data, newbranch = new_node(); newbranch->value.thres_bit = bitloc; (*parentlink) = newbranch; + if (testbit(str, slen, bitloc) ==0) { newbranch->l = newleaf; newbranch->r = node; @@ -227,14 +246,11 @@ static void ptree_add_entry_at(char *str, size_t slen, int bitloc, int data, newbranch->l = node; newbranch->r = newleaf; } - return; } else { if (testbit(str, slen, node->value.thres_bit) != 0) - ptree_add_entry_at(str, slen, bitloc, data, - addr, alen, &(node->r)); + ptree_add_entry_at(str, slen, bitloc, data, addr, alen, &(node->r)); else - ptree_add_entry_at(str, slen, bitloc, data, - addr, alen, &(node->l)); + ptree_add_entry_at(str, slen, bitloc, data, addr, alen, &(node->l)); } } @@ -249,6 +265,7 @@ int ptree_add_entry(void *str, size_t sstr, int data, struct sockaddr_storage *a else { ptr = ptree_search_data_nearest_ptr(str, sstr, (*root)); n = container_of(ptr, struct patricia_node, value.data); + if (n->klen == sstr && !memcmp(str, n->key, n->klen)) { /* Make sure if entry exists, that we also have the * same data, otherwise, we drop the packet */ @@ -262,8 +279,10 @@ int ptree_add_entry(void *str, size_t sstr, int data, struct sockaddr_storage *a if (memcmp(n->addr, addr, alen)) malicious = 1; } + return malicious; } + bitloc = where_the_bit_differ(str, sstr, n->key, n->klen); ptree_add_entry_at(str, sstr, bitloc, data, addr, alen, root); } @@ -289,7 +308,9 @@ static void ptree_remove_entry_r(struct patricia_node *now, free_node(now); return; } + b = (up->r == now) ? up->l : up->r; + if (up2 == NULL) { *root = b; free_node(now); @@ -300,16 +321,14 @@ static void ptree_remove_entry_r(struct patricia_node *now, up2->l = b; else up2->r = b; + free_node(now); free_node(up); - return; } else { if (testbit_max(str, now->value.thres_bit, maxbitplace) != 0) - ptree_remove_entry_r(now->r, now, up, str, slen, - maxbitplace, root); + ptree_remove_entry_r(now->r, now, up, str, slen, maxbitplace, root); else - ptree_remove_entry_r(now->l, now, up, str, slen, - maxbitplace, root); + ptree_remove_entry_r(now->l, now, up, str, slen, maxbitplace, root); } } @@ -317,6 +336,7 @@ void ptree_del_entry(void *str, size_t sstr, struct patricia_node **root) { if (!(*root)) return; + ptree_remove_entry_r(*root, NULL, NULL, str, sstr, sstr * 8, root); } @@ -324,10 +344,11 @@ void ptree_free(struct patricia_node *node) { if (!node) return; + if (node->l) ptree_free(node->l); if (node->r) ptree_free(node->r); + free_node(node); } - diff --git a/patricia.h b/patricia.h index 0e3bc5f7..d5685475 100644 --- a/patricia.h +++ b/patricia.h @@ -47,6 +47,4 @@ extern void ptree_get_key_addr(struct sockaddr_storage *addr, size_t alen, extern void ptree_display(struct patricia_node *node, int level); extern void ptree_free(struct patricia_node *root); -#define ptree_maybe_add_entry ptree_add_entry - #endif /* PATRICIA_H */ diff --git a/trie.c b/trie.c index 85277a89..a74d710a 100644 --- a/trie.c +++ b/trie.c @@ -38,7 +38,6 @@ void trie_addr_lookup(char *buff, size_t len, int ipv4, int *fd, return; } - /* Always happens on the dst address */ rwlock_rd_lock(&tree_lock); (*fd) = ptree_search_data_exact(data, dlen, addr, alen, tree); rwlock_unlock(&tree_lock); @@ -60,9 +59,8 @@ int trie_addr_maybe_update(char *buff, size_t len, int ipv4, int fd, (!ipv4 && ((struct ipv6hdr *) buff)->version != 6))) return -1; - /* Always happens on the src address */ rwlock_wr_lock(&tree_lock); - ret = ptree_maybe_add_entry(data, dlen, fd, addr, alen, &tree); + ret = ptree_add_entry(data, dlen, fd, addr, alen, &tree); rwlock_unlock(&tree_lock); return ret; @@ -116,6 +114,5 @@ void trie_cleanup(void) rwlock_wr_lock(&tree_lock); ptree_free(tree); rwlock_unlock(&tree_lock); - rwlock_destroy(&tree_lock); } -- 2.11.4.GIT