diff options
-rw-r--r-- | radix-trie.c | 32 | ||||
-rwxr-xr-x | tests/afl-radix/generate | bin | 0 -> 17696 bytes | |||
-rw-r--r-- | tests/afl-radix/generate_in.c | 51 | ||||
-rw-r--r-- | tests/afl-radix/in/1 | bin | 0 -> 80 bytes | |||
-rw-r--r-- | tests/afl-radix/ip_util.h | 125 | ||||
-rwxr-xr-x | tests/afl-radix/main | bin | 0 -> 148696 bytes | |||
-rw-r--r-- | tests/afl-radix/main.c | 67 | ||||
l--------- | tests/afl-radix/radix-trie.c | 1 | ||||
l--------- | tests/afl-radix/radix-trie.h | 1 |
9 files changed, 269 insertions, 8 deletions
diff --git a/radix-trie.c b/radix-trie.c index 8eb2316..9200c35 100644 --- a/radix-trie.c +++ b/radix-trie.c @@ -349,10 +349,10 @@ static int insert_v6(struct radix_node **root, const struct in6_addr *ip, return ret; } -static int remove_node(struct radix_node *trie, const uint8_t *key, +static int remove_node(struct radix_node **trie, const uint8_t *key, uint8_t bits, uint8_t cidr, uint64_t count) { - struct radix_node **node = ≜ + struct radix_node **node = trie; while (*node && common_bits(*node, key, bits) < cidr) { if (CHOOSE_NODE(*node, key) == (*node)->bit[0]) @@ -360,6 +360,8 @@ static int remove_node(struct radix_node *trie, const uint8_t *key, else (*node)->right += count; + debug("Loop: common_bits: %u, cidr: %u\n", + common_bits(*node, key, bits), cidr); node = &CHOOSE_NODE(*node, key); } @@ -454,7 +456,7 @@ static int ipp_addpool(struct ip_pool *ipp, struct radix_pool **pool, return 0; } -static int ipp_removepool(struct radix_node *trie, struct radix_pool **pool, +static int ipp_removepool(struct radix_node **trie, struct radix_pool **pool, uint8_t bits, const uint8_t *key) { struct radix_pool *tmp; @@ -471,7 +473,19 @@ static int ipp_removepool(struct radix_node *trie, struct radix_pool **pool, node = (*pool)->node; cidr = node->cidr; - taken = ((1ULL << (bits - cidr)) - (node->left + node->right)); + taken = ((bits - cidr) < 64 ? 1ULL << (bits - cidr) : 0) - + (node->left + node->right); + + debug("Available pools: "); + struct radix_pool *tp = *pool; + while (tp->next) { + printf("%y/%u -> ", tp->node->bits, tp->node->cidr); + tp = tp->next; + } + printf("NULL\n"); + + debug("left: %ju, right: %ju\n", node->left, node->right); + debug("remove_node(%p, (key), %u, %u, %ju)\n", trie, bits, cidr, taken); BUG_ON(remove_node(trie, key, bits, cidr, taken)); tmp = *pool; @@ -495,6 +509,8 @@ void node_to_str(struct radix_node *node, char *buf, uint8_t bits) return; } + // TODO: + /* uint8_t key[4] __aligned(__alignof(uint32_t)); */ if (bits == 32) { swap_endian((uint8_t *)&v4addr.s_addr, node->bits, bits); inet_ntop(AF_INET, &v4addr, out, sizeof out); @@ -621,7 +637,7 @@ int ipp_del_v4(struct ip_pool *pool, const struct in_addr *ip, uint8_t cidr) return -1; swap_endian(key, (const uint8_t *)ip, 32); - ret = remove_node(pool->ip4_root, key, 32, cidr, 1ULL << (32 - cidr)); + ret = remove_node(&pool->ip4_root, key, 32, cidr, 1ULL << (32 - cidr)); return ret; } @@ -635,7 +651,7 @@ int ipp_del_v6(struct ip_pool *pool, const struct in6_addr *ip, uint8_t cidr) return -1; swap_endian(key, (const uint8_t *)ip, 128); - ret = remove_node(pool->ip6_root, key, 128, cidr, 1ULL << (128 - cidr)); + ret = remove_node(&pool->ip6_root, key, 128, cidr, 1ULL << (128 - cidr)); if (!ret) { ++pool->totall_ipv6; if (pool->totall_ipv6 == 0) @@ -680,7 +696,7 @@ int ipp_removepool_v4(struct ip_pool *pool, const struct in_addr *ip) int cidr; swap_endian(key, (const uint8_t *)ip, 32); - cidr = ipp_removepool(pool->ip4_root, &pool->ip4_pool, 32, key); + cidr = ipp_removepool(&pool->ip4_root, &pool->ip4_pool, 32, key); if (cidr < 0) return -1; @@ -696,7 +712,7 @@ int ipp_removepool_v6(struct ip_pool *pool, const struct in6_addr *ip) int cidr; swap_endian(key, (const uint8_t *)ip, 128); - cidr = ipp_removepool(pool->ip4_root, &pool->ip6_pool, 128, key); + cidr = ipp_removepool(&pool->ip6_root, &pool->ip6_pool, 128, key); if (cidr < 0) return -1; diff --git a/tests/afl-radix/generate b/tests/afl-radix/generate Binary files differnew file mode 100755 index 0000000..d4cfc7d --- /dev/null +++ b/tests/afl-radix/generate diff --git a/tests/afl-radix/generate_in.c b/tests/afl-radix/generate_in.c new file mode 100644 index 0000000..684cd48 --- /dev/null +++ b/tests/afl-radix/generate_in.c @@ -0,0 +1,51 @@ +#include <fcntl.h> +#include <sys/stat.h> +#include <sys/types.h> +#include <unistd.h> + +#include "dbg.h" +#include "ip_util.h" + +int main(void) +{ + char buf[4096]; + int fd = open("in/1", O_CREAT | O_WRONLY); + int i = 0; + + buf[i++] = 'a'; + buf[i++] = 0x01; + buf[i++] = 28; + memcpy(buf + i, ip4_from("192.168.4.0"), 4); + i += 4; + memset(buf + i, 0x0, 12); + i += 12; + buf[i++] = '\n'; + + buf[i++] = 'a'; + buf[i++] = 0x02; + buf[i++] = 124; + memcpy(buf + i, ip6_from("2001:db8:1234::"), 16); + i += 16; + buf[i++] = '\n'; + + buf[i++] = 'b'; + buf[i++] = 0x01; + buf[i++] = 0; + memcpy(buf + i, ip4_from("192.168.4.0"), 4); + i += 4; + memset(buf + i, 0x0, 12); + i += 12; + buf[i++] = '\n'; + + buf[i++] = 'b'; + buf[i++] = 0x02; + buf[i++] = 0; + memcpy(buf + i, ip6_from("2001:db8:1234::"), 16); + i += 16; + buf[i++] = '\n'; + + if (write(fd, buf, i) < i) + fatal("write()"); + + return 0; +} diff --git a/tests/afl-radix/in/1 b/tests/afl-radix/in/1 Binary files differnew file mode 100644 index 0000000..b6720b4 --- /dev/null +++ b/tests/afl-radix/in/1 diff --git a/tests/afl-radix/ip_util.h b/tests/afl-radix/ip_util.h new file mode 100644 index 0000000..5550610 --- /dev/null +++ b/tests/afl-radix/ip_util.h @@ -0,0 +1,125 @@ +#ifndef __IP_UTIL_H__ +#define __IP_UTIL_H__ + +#include <arpa/inet.h> +#include <printf.h> +#include <stddef.h> +#include <stdint.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +#pragma GCC diagnostic ignored "-Wformat" +#pragma GCC diagnostic ignored "-Wformat-extra-args" + +static int __printf_arginfo(const struct printf_info *info, size_t n, + int *argtypes, int *sz) +{ + if (n > 0) + argtypes[0] = PA_POINTER; + + return 1; +} + +static int __printf_output_b(FILE *stream, const struct printf_info *info, + const void *const *args) +{ + uint64_t value = 0; + char buf[8 * sizeof(uintmax_t) + 1] = { 0 }; + + if (info->width == 0 || info->width % 8 != 0) + return -1; + + memcpy(&value, *(unsigned char **)(args[0]), info->width / 8); + + for (int i = 0; i < info->width; ++i) + buf[info->width - 1 - i] = '0' + ((value >> i) & 0x1); + + return fprintf(stream, "%s", buf); +} + +static int __printf_output_y(FILE *stream, const struct printf_info *info, + const void *const *args) +{ + char buf[INET_ADDRSTRLEN]; + struct in_addr ip; + + if (!*(unsigned char **)(args[0])) + return fprintf(stream, "(nil)", buf); + + memcpy(&ip, *(unsigned char **)(args[0]), sizeof ip); + + inet_ntop(AF_INET, &ip.s_addr, buf, sizeof buf); + + return fprintf(stream, "%s", buf); +} + +static int __printf_output_Y(FILE *stream, const struct printf_info *info, + const void *const *args) +{ + char buf[INET6_ADDRSTRLEN]; + struct in6_addr ip; + + if (!*(unsigned char **)(args[0])) + return fprintf(stream, "(nil)", buf); + + memcpy(&ip, *(unsigned char **)(args[0]), sizeof ip); + + inet_ntop(AF_INET6, &ip.s6_addr, buf, sizeof buf); + + return fprintf(stream, "%s", buf); +} + +static void __attribute__((constructor)) __custom_printf_init() +{ + register_printf_specifier('b', __printf_output_b, __printf_arginfo); + register_printf_specifier('y', __printf_output_y, __printf_arginfo); + register_printf_specifier('Y', __printf_output_Y, __printf_arginfo); +} + +struct ip_from { + unsigned char ip[16]; + struct ip_from *next; +}; + +static struct ip_from *start = NULL; +static struct ip_from *end = NULL; + +static unsigned char *ip_from(uint8_t bits, char *ip_str) +{ + struct ip_from *res = malloc(sizeof *res); + + inet_pton(bits == 32 ? AF_INET : AF_INET6, ip_str, &res->ip); + + if (!end) + start = end = res; + else + end->next = res; + + end = res; + res->next = NULL; + + return res->ip; +} + +static struct in_addr *ip4_from(char *ip_str) +{ + return (struct in_addr *)ip_from(32, ip_str); +} + +static struct in6_addr *ip6_from(char *ip_str) +{ + return (struct in6_addr *)ip_from(128, ip_str); +} + +static void __attribute__((destructor)) __free_ip_froms() +{ + struct ip_from *cur = start, *next; + while (cur) { + next = cur->next; + free(cur); + cur = next; + } +} + +#endif diff --git a/tests/afl-radix/main b/tests/afl-radix/main Binary files differnew file mode 100755 index 0000000..ac80c8a --- /dev/null +++ b/tests/afl-radix/main diff --git a/tests/afl-radix/main.c b/tests/afl-radix/main.c new file mode 100644 index 0000000..af09cee --- /dev/null +++ b/tests/afl-radix/main.c @@ -0,0 +1,67 @@ +#define _POSIX_C_SOURCE 200809L + +#include <arpa/inet.h> +#include <errno.h> +#include <stdio.h> + +#include "dbg.h" +#include "radix-trie.h" +#include "ip_util.h" + +int main(int argc, char **argv) +{ + struct ip_pool pool; + char *line = NULL; + ssize_t len; + struct in_addr *ipv4; + struct in6_addr *ipv6; + + ipp_init(&pool); + + while ((len = getline(&line, &(size_t){ 0 }, stdin)) > 0) { + if (len != 20 || (line[1] != 0x01 && line[1] != 0x02)) { + free(line); + line = NULL; + continue; + } + + if (line[1] == 0x01) + ipv4 = (struct in_addr *)&line[3]; + else if (line[1] == 0x02) + ipv6 = (struct in6_addr *)&line[3]; + + switch (line[0]) { + case 'a': + if (line[1] == 0x01) { + debug("ipp_addpool_v4(%y, %u)\n", ipv4, + line[2]); + ipp_addpool_v4(&pool, ipv4, line[2]); + } else { + debug("ipp_addpool_v6(%Y, %u)\n", ipv6, + line[2]); + ipp_addpool_v6(&pool, ipv6, line[2]); + } + break; + case 'b': + if (line[1] == 0x01) { + debug("ipp_removepool_v4(%y)\n", ipv4); + ipp_removepool_v4(&pool, ipv4); + } else { + debug("ipp_removepool_v6(%Y)\n", ipv6); + ipp_removepool_v6(&pool, ipv6); + } + break; + } + + free(line); + line = NULL; + } + + free(line); + ipp_free(&pool); + + if (len == -1 && errno) + fatal("getline()"); + + return 0; +} diff --git a/tests/afl-radix/radix-trie.c b/tests/afl-radix/radix-trie.c new file mode 120000 index 0000000..b3bfb6e --- /dev/null +++ b/tests/afl-radix/radix-trie.c @@ -0,0 +1 @@ +../../radix-trie.c
\ No newline at end of file diff --git a/tests/afl-radix/radix-trie.h b/tests/afl-radix/radix-trie.h new file mode 120000 index 0000000..72f15ac --- /dev/null +++ b/tests/afl-radix/radix-trie.h @@ -0,0 +1 @@ +../../radix-trie.h
\ No newline at end of file |