aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorThomas Gschwantner <tharre3@gmail.com>2019-08-08 01:17:34 +0200
committerThomas Gschwantner <tharre3@gmail.com>2019-08-08 01:17:34 +0200
commit5ecf7a6d09daa450505d82abb23c35bbf2645a7d (patch)
tree221c3442ff003dbd84e3874481ea55e54d72128d
parentWIP: radix-trie: add ipp_removepool_v4/6 (diff)
downloadwg-dynamic-tg/radix-trie.tar.xz
wg-dynamic-tg/radix-trie.zip
WIP: testing codetg/radix-trie
-rw-r--r--radix-trie.c32
-rwxr-xr-xtests/afl-radix/generatebin0 -> 17696 bytes
-rw-r--r--tests/afl-radix/generate_in.c51
-rw-r--r--tests/afl-radix/in/1bin0 -> 80 bytes
-rw-r--r--tests/afl-radix/ip_util.h125
-rwxr-xr-xtests/afl-radix/mainbin0 -> 148696 bytes
-rw-r--r--tests/afl-radix/main.c67
l---------tests/afl-radix/radix-trie.c1
l---------tests/afl-radix/radix-trie.h1
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 = &trie;
+ 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
new file mode 100755
index 0000000..d4cfc7d
--- /dev/null
+++ b/tests/afl-radix/generate
Binary files differ
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
new file mode 100644
index 0000000..b6720b4
--- /dev/null
+++ b/tests/afl-radix/in/1
Binary files differ
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
new file mode 100755
index 0000000..ac80c8a
--- /dev/null
+++ b/tests/afl-radix/main
Binary files differ
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