path: root/src/libutil/radix.c

/*-
 * Copyright 2016 Vsevolod Stakhov
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *   http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
#include "config.h"
#include "radix.h"
#include "rspamd.h"
#include "mem_pool.h"
#include "btrie.h"

#define msg_err_radix(...) rspamd_default_log_function(G_LOG_LEVEL_CRITICAL,         \
													   "radix", tree->pool->tag.uid, \
													   G_STRFUNC,                    \
													   __VA_ARGS__)
#define msg_warn_radix(...) rspamd_default_log_function(G_LOG_LEVEL_WARNING,          \
														"radix", tree->pool->tag.uid, \
														G_STRFUNC,                    \
														__VA_ARGS__)
#define msg_info_radix(...) rspamd_default_log_function(G_LOG_LEVEL_INFO,             \
														"radix", tree->pool->tag.uid, \
														G_STRFUNC,                    \
														__VA_ARGS__)
#define msg_debug_radix(...) rspamd_conditional_debug_fast(NULL, NULL,                                        \
														   rspamd_radix_log_id, "radix", tree->pool->tag.uid, \
														   G_STRFUNC,                                         \
														   __VA_ARGS__)

INIT_LOG_MODULE(radix)

struct radix_tree_compressed {
	rspamd_mempool_t *pool;
	struct btrie *tree;
	const gchar *name;
	size_t size;
	guint duplicates;
	gboolean own_pool;
};

uintptr_t
radix_find_compressed(radix_compressed_t *tree, const guint8 *key, gsize keylen)
{
	gconstpointer ret;

	g_assert(tree != NULL);

	ret = btrie_lookup(tree->tree, key, keylen * NBBY);

	if (ret == NULL) {
		return RADIX_NO_VALUE;
	}

	return (uintptr_t) ret;
}


uintptr_t
radix_insert_compressed(radix_compressed_t *tree,
						guint8 *key, gsize keylen,
						gsize masklen,
						uintptr_t value)
{
	static const guint max_duplicates = 32;
	guint keybits = keylen * NBBY;
	uintptr_t old;
	gchar ip_str[INET6_ADDRSTRLEN + 1];
	int ret;

	g_assert(tree != NULL);
	g_assert(keybits >= masklen);

	msg_debug_radix("%s: want insert value %p with mask %z, key: %*xs",
					tree->name, (gpointer) value, keybits - masklen, (int) keylen, key);

	old = radix_find_compressed(tree, key, keylen);

	ret = btrie_add_prefix(tree->tree, key, keybits - masklen,
						   (gconstpointer) value);

	if (ret != BTRIE_OKAY) {
		tree->duplicates++;

		if (tree->duplicates == max_duplicates) {
			msg_err_radix("%s: maximum duplicates limit reached: %d, "
						  "suppress further errors",
						  tree->name, max_duplicates);
		}
		else if (tree->duplicates < max_duplicates) {
			memset(ip_str, 0, sizeof(ip_str));

			if (keybits == 32) {
				msg_err_radix("%s: cannot insert %p, key: %s/%d, duplicate value",
							  tree->name,
							  (gpointer) value,
							  inet_ntop(AF_INET, key, ip_str, sizeof(ip_str) - 1),
							  (gint) (keybits - masklen));
			}
			else if (keybits == 128) {
				msg_err_radix("%s: cannot insert %p, key: [%s]/%d, duplicate value",
							  tree->name,
							  (gpointer) value,
							  inet_ntop(AF_INET6, key, ip_str, sizeof(ip_str) - 1),
							  (gint) (keybits - masklen));
			}
			else {
				msg_err_radix("%s: cannot insert %p with mask %z, key: %*xs, duplicate value",
							  tree->name,
							  (gpointer) value,
							  keybits - masklen,
							  (int) keylen, key);
			}
		}
	}
	else {
		tree->size++;
	}

	return old;
}


radix_compressed_t *
radix_create_compressed(const gchar *tree_name)
{
	radix_compressed_t *tree;

	tree = g_malloc(sizeof(*tree));
	if (tree == NULL) {
		return NULL;
	}

	tree->pool = rspamd_mempool_new(rspamd_mempool_suggest_size(), NULL, 0);
	tree->size = 0;
	tree->duplicates = 0;
	tree->tree = btrie_init(tree->pool);
	tree->own_pool = TRUE;
	tree->name = tree_name;

	return tree;
}

radix_compressed_t *
radix_create_compressed_with_pool(rspamd_mempool_t *pool, const gchar *tree_name)
{
	radix_compressed_t *tree;

	tree = rspamd_mempool_alloc(pool, sizeof(*tree));
	tree->pool = pool;
	tree->size = 0;
	tree->duplicates = 0;
	tree->tree = btrie_init(tree->pool);
	tree->own_pool = FALSE;
	tree->name = tree_name;

	return tree;
}

void radix_destroy_compressed(radix_compressed_t *tree)
{
	if (tree) {
		if (tree->own_pool) {
			rspamd_mempool_delete(tree->pool);
			g_free(tree);
		}
	}
}

uintptr_t
radix_find_compressed_addr(radix_compressed_t *tree,
						   const rspamd_inet_addr_t *addr)
{
	const guchar *key;
	guint klen = 0;
	guchar buf[16];

	if (addr == NULL) {
		return RADIX_NO_VALUE;
	}

	key = rspamd_inet_address_get_hash_key(addr, &klen);

	if (key && klen) {
		if (klen == 4) {
			/* Map to ipv6 */
			memset(buf, 0, 10);
			buf[10] = 0xffu;
			buf[11] = 0xffu;
			memcpy(buf + 12, key, klen);

			key = buf;
			klen = sizeof(buf);
		}

		return radix_find_compressed(tree, key, klen);
	}

	return RADIX_NO_VALUE;
}

gint rspamd_radix_add_iplist(const gchar *list, const gchar *separators,
							 radix_compressed_t *tree, gconstpointer value,
							 gboolean resolve, const gchar *tree_name)
{
	gchar *token, *ipnet, *err_str, **strv, **cur, *brace;
	union {
		struct in_addr ina;
		struct in6_addr ina6;
		guchar buf[16];
	} addr_buf;
	guint k = G_MAXINT;
	gint af;
	gint res = 0, r;
	struct addrinfo hints, *ai_res, *cur_ai;

	/* Split string if there are multiple items inside a single string */
	strv = g_strsplit_set(list, separators, 0);
	cur = strv;
	while (*cur) {
		af = AF_UNSPEC;
		if (**cur == '\0') {
			cur++;
			continue;
		}

		/* Extract ipnet */
		ipnet = g_strstrip(*cur);
		token = strsep(&ipnet, "/");

		if (ipnet != NULL) {
			errno = 0;
			/* Get mask */
			k = strtoul(ipnet, &err_str, 10);
			if (errno != 0) {
				msg_warn_radix(
					"%s: invalid netmask, error detected on symbol: %s, error: %s",
					tree_name,
					err_str,
					strerror(errno));
				k = G_MAXINT;
			}
		}

		/* Check IP */
		if (token[0] == '[') {
			/* Braced IPv6 */
			brace = strrchr(token, ']');

			if (brace != NULL) {
				token++;
				*brace = '\0';

				if (inet_pton(AF_INET6, token, &addr_buf.ina6) == 1) {
					af = AF_INET6;
				}
				else {
					msg_warn_radix("invalid IP address: %s", token);

					cur++;
					continue;
				}
			}
			else {
				msg_warn_radix("invalid IP address: %s", token);

				cur++;
				continue;
			}
		}
		else {
			if (inet_pton(AF_INET, token, &addr_buf.ina) == 1) {
				af = AF_INET;
			}
			else if (inet_pton(AF_INET6, token, &addr_buf.ina6) == 1) {
				af = AF_INET6;
			}
			else {

				if (resolve) {
					memset(&hints, 0, sizeof(hints));
					hints.ai_socktype = SOCK_STREAM; /* Type of the socket */
					hints.ai_flags = AI_NUMERICSERV;
					hints.ai_family = AF_UNSPEC;

					if ((r = getaddrinfo(token, NULL, &hints, &ai_res)) == 0) {
						for (cur_ai = ai_res; cur_ai != NULL;
							 cur_ai = cur_ai->ai_next) {

							if (cur_ai->ai_family == AF_INET) {
								struct sockaddr_in *sin;

								sin = (struct sockaddr_in *) cur_ai->ai_addr;
								if (k > 32) {
									k = 32;
								}

								/* Convert to IPv4 mapped IPv6 */
								memset(addr_buf.buf, 0, 10);
								addr_buf.buf[10] = 0xffu;
								addr_buf.buf[11] = 0xffu;
								memcpy(addr_buf.buf + 12,
									   &sin->sin_addr, 4);

								k += 96;

								radix_insert_compressed(tree,
														addr_buf.buf,
														sizeof(addr_buf.buf),
														128 - k, (uintptr_t) value);
								res++;
							}
							else if (cur_ai->ai_family == AF_INET6) {
								struct sockaddr_in6 *sin6;

								sin6 = (struct sockaddr_in6 *) cur_ai->ai_addr;
								if (k > 128) {
									k = 128;
								}

								memcpy(addr_buf.buf, &sin6->sin6_addr,
									   sizeof(sin6->sin6_addr));
								radix_insert_compressed(tree,
														addr_buf.buf,
														sizeof(addr_buf.buf),
														128 - k, (uintptr_t) value);
								res++;
							}
						}

						freeaddrinfo(ai_res);
					}
					else {
						msg_warn_radix("getaddrinfo failed for %s: %s", token,
									   gai_strerror(r));
					}

					cur++;
					continue;
				}
				else {
					msg_warn_radix("invalid IP address: %s", token);

					cur++;
					continue;
				}
			}
		}

		if (af == AF_INET) {
			if (k > 32) {
				k = 32;
			}

			/* Move to the last part of the address */
			memmove(addr_buf.buf + 12, &addr_buf.ina, 4);
			memset(addr_buf.buf, 0, 10);
			addr_buf.buf[10] = 0xffu;
			addr_buf.buf[11] = 0xffu;
			k += 96;
			radix_insert_compressed(tree, addr_buf.buf, sizeof(addr_buf.buf),
									128 - k, (uintptr_t) value);
			res++;
		}
		else if (af == AF_INET6) {
			if (k > 128) {
				k = 128;
			}

			radix_insert_compressed(tree, addr_buf.buf, sizeof(addr_buf),
									128 - k, (uintptr_t) value);
			res++;
		}
		cur++;
	}

	g_strfreev(strv);

	return res;
}

gboolean
radix_add_generic_iplist(const gchar *ip_list, radix_compressed_t **tree,
						 gboolean resolve, const gchar *tree_name)
{
	static const char fill_ptr[] = "1";

	if (*tree == NULL) {
		*tree = radix_create_compressed(tree_name);
	}

	return (rspamd_radix_add_iplist(ip_list, ",; ", *tree,
									fill_ptr, resolve, tree_name) > 0);
}


gsize radix_get_size(radix_compressed_t *tree)
{
	if (tree != NULL) {
		return tree->size;
	}

	return 0;
}


rspamd_mempool_t *
radix_get_pool(radix_compressed_t *tree)
{

	if (tree != NULL) {
		return tree->pool;
	}

	return NULL;
}

const gchar *
radix_get_info(radix_compressed_t *tree)
{
	if (tree == NULL) {
		return NULL;
	}

	return btrie_stats(tree->tree, tree->duplicates);
}