diff options
author | Ondřej Surý <ondrej@sury.org> | 2011-11-02 22:44:12 +0100 |
---|---|---|
committer | Ondřej Surý <ondrej@sury.org> | 2011-11-02 22:44:12 +0100 |
commit | c8d5977bb546dae9ed59d81556639c49badd8121 (patch) | |
tree | 4c86750db26c1c3502b60f2cd78ca9611cfa01d6 /src/common | |
download | knot-upstream/0.8.0_pre1.tar.gz |
Imported Upstream version 0.8.0~pre1upstream/0.8.0_pre1
Diffstat (limited to 'src/common')
51 files changed, 9487 insertions, 0 deletions
diff --git a/src/common/WELL1024a.c b/src/common/WELL1024a.c new file mode 100644 index 0000000..dddf75e --- /dev/null +++ b/src/common/WELL1024a.c @@ -0,0 +1,116 @@ +/* ***************************************************************************** */ +/* Copyright: Francois Panneton and Pierre L'Ecuyer, University of Montreal */ +/* Makoto Matsumoto, Hiroshima University */ +/* Notice: This code can be used freely for personal, academic, */ +/* or non-commercial purposes. For commercial purposes, */ +/* please contact P. L'Ecuyer at: lecuyer@iro.UMontreal.ca */ +/* ***************************************************************************** */ + +#include <pthread.h> +#include <string.h> +#include <stdlib.h> +#include <time.h> +#include <stdio.h> + +#include "WELL1024a.h" + +#define W 32 +#define M1 3 +#define M2 24 +#define M3 10 + +#define MAT0POS(t,v) (v^(v>>t)) +#define MAT0NEG(t,v) (v^(v<<(-(t)))) +#define Identity(v) (v) + +#define V0(s) (s)->state[(s)->i ] +#define VM1(s) (s)->state[((s)->i+M1) & 0x0000001fU] +#define VM2(s) (s)->state[((s)->i+M2) & 0x0000001fU] +#define VM3(s) (s)->state[((s)->i+M3) & 0x0000001fU] +#define VRm1(s) (s)->state[((s)->i+31) & 0x0000001fU] +#define newV0(s) (s)->state[((s)->i+31) & 0x0000001fU] +#define newV1(s) (s)->state[(s)->i ] + +#define FACT 2.32830643653869628906e-10 + +rngstate_t* InitWELLRNG1024a (unsigned *init) { + + rngstate_t *s = malloc(sizeof(rngstate_t)); + if (s == 0) { + return 0; + } + + s->i = 0; + for (int j = 0; j < WELL1024_WIDTH; j++) + s->state[j] = init[j]; + return s; +} + +double WELLRNG1024a (rngstate_t* s) { + unsigned z0 = VRm1(s); + unsigned z1 = Identity(V0(s)) ^ MAT0POS (8, VM1(s)); + unsigned z2 = MAT0NEG (-19, VM2(s)) ^ MAT0NEG(-14,VM3(s)); + newV1(s) = z1 ^ z2; + newV0(s) = MAT0NEG (-11,z0) ^ MAT0NEG(-7,z1) ^ MAT0NEG(-13,z2) ; + s->i = (s->i + 31) & 0x0000001fU; + return ((double) s->state[s->i] * FACT); +} + +/*! \brief TLS unique key for each thread seed. */ +static pthread_key_t tls_prng_key; +static pthread_once_t tls_prng_once = PTHREAD_ONCE_INIT; + +static void tls_prng_deinit(void *ptr) +{ + free(ptr); +} + +static void tls_prng_deinit_main() +{ + tls_prng_deinit(pthread_getspecific(tls_prng_key)); +} + +static void tls_prng_init() +{ + (void) pthread_key_create(&tls_prng_key, tls_prng_deinit); + atexit(tls_prng_deinit_main); // Main thread cleanup +} + +double tls_rand() +{ + /* Setup PRNG state for current thread. */ + (void)pthread_once(&tls_prng_once, tls_prng_init); + + /* Create PRNG state if not exists. */ + rngstate_t* s = pthread_getspecific(tls_prng_key); + if (!s) { + /* Initialize seed from system PRNG generator. */ + unsigned init[WELL1024_WIDTH]; + FILE *fp = fopen("/dev/urandom", "r"); + for (unsigned i = 0; i < WELL1024_WIDTH; ++i) { + int rc = fread(&init[i], sizeof(unsigned), 1, fp); + rc = rc; + } + fclose(fp); + + /* Initialize PRNG state. */ + s = InitWELLRNG1024a(init); + (void)pthread_setspecific(tls_prng_key, s); + } + + return WELLRNG1024a(s); +} + +void tls_seed_set(unsigned init[WELL1024_WIDTH]) +{ + /* Initialize new PRNG state if not exists. */ + rngstate_t* s = pthread_getspecific(tls_prng_key); + if (!s) { + s = InitWELLRNG1024a(init); + (void)pthread_setspecific(tls_prng_key, s); + } else { + /* Reset PRNG state if exists. */ + memcpy(s->state, init, sizeof(unsigned) * WELL1024_WIDTH); + s->i = 0; + } +} diff --git a/src/common/WELL1024a.h b/src/common/WELL1024a.h new file mode 100644 index 0000000..04bf1a1 --- /dev/null +++ b/src/common/WELL1024a.h @@ -0,0 +1,32 @@ +/* ***************************************************************************** */ +/* Copyright: Francois Panneton and Pierre L'Ecuyer, University of Montreal */ +/* Makoto Matsumoto, Hiroshima University */ +/* Notice: This code can be used freely for personal, academic, */ +/* or non-commercial purposes. For commercial purposes, */ +/* please contact P. L'Ecuyer at: lecuyer@iro.UMontreal.ca */ +/* ***************************************************************************** */ + +#define WELL1024_WIDTH 32 /* 128 bytes */ + +typedef struct { + unsigned i; + unsigned state[WELL1024_WIDTH]; +} rngstate_t; + +rngstate_t* InitWELLRNG1024a (unsigned *init); +double WELLRNG1024a (rngstate_t* s); + +/*! + * \brief Get pseudorandom number from PRNG initialized in thread-local storage. + * + * No need for initialization, TLS will take care of it. + * + * \retval Pseudorandom number. + */ +double tls_rand(); + +/*! + * \brief Set PRNG seed in thread-local storage to requested value. + * + */ +void tls_seed_set(unsigned init[WELL1024_WIDTH]); diff --git a/src/common/acl.c b/src/common/acl.c new file mode 100644 index 0000000..e73c4dd --- /dev/null +++ b/src/common/acl.c @@ -0,0 +1,185 @@ +/* Copyright (C) 2011 CZ.NIC, z.s.p.o. <knot-dns@labs.nic.cz> + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. + */ + +#include <string.h> +#include <stdlib.h> + +#include "common/acl.h" + +static int acl_compare(void *k1, void *k2) +{ + sockaddr_t* a1 = (sockaddr_t *)k1; + sockaddr_t* a2 = (sockaddr_t *)k2; + + /* Check different length, IPv4 goes first. */ + int ldiff = a1->len - a2->len; + if (ldiff != 0) { + return ldiff < 0 ? -1 : 1; + } + + /* Compare integers if IPv4. */ + if (a1->len == sizeof(struct sockaddr_in)) { + + /* Allow if k1 == INADDR_ANY. */ + if (a1->addr4.sin_addr.s_addr == 0) { + return 0; + } + + /* Compare address. */ + ldiff = a1->addr4.sin_addr.s_addr - a2->addr4.sin_addr.s_addr; + if (ldiff != 0) { + return ldiff < 0 ? -1 : 1; + } + + /* Port = 0 means any port match. */ + if (a1->addr4.sin_port == 0) { + return 0; + } + + /* Compare ports on address match. */ + ldiff = ntohs(a1->addr4.sin_port) - ntohs(a2->addr4.sin_port); + if (ldiff != 0) { + return ldiff < 0 ? -1 : 1; + } + return 0; + } + + /* IPv6 matching. */ +#ifndef DISABLE_IPV6 + if (a1->len == sizeof(struct sockaddr_in6)) { + + /* Compare address. */ + /*! \todo Maybe use memcmp()? */ + ldiff = 0; + const unsigned int *a6 = (const unsigned int *)&a1->addr6.sin6_addr; + const unsigned int *b6 = (const unsigned int *)&a2->addr6.sin6_addr; + for (int i = 0; i < (sizeof(struct in6_addr)/ sizeof(int)) ; ++i) { + ldiff = a6[i] - b6[i]; + if (ldiff < 0) { + return -1; + } + if (ldiff > 0) { + return 1; + } + } + + /* Port = 0 means any port match. */ + if (a1->addr6.sin6_port == 0) { + return 0; + } + + /* Compare ports on address match. */ + ldiff = ntohs(a1->addr6.sin6_port) - ntohs(a2->addr6.sin6_port); + if (ldiff != 0) { + return ldiff < 0 ? -1 : 1; + } + return 0; + } +#endif + + return 0; +} + +acl_t *acl_new(acl_rule_t default_rule, const char *name) +{ + /* Trailing '\0' for NULL name. */ + size_t name_len = 1; + if (name) { + name_len += strlen(name); + } else { + name = ""; + } + + /* Allocate memory for ACL. */ + acl_t* acl = malloc(sizeof(acl_t) + name_len); + if (!acl) { + return 0; + } + + /* Initialize skip list. */ + acl->rules = skip_create_list(acl_compare); + if (!acl->rules) { + free(acl); + return 0; + } + + /* Initialize. */ + memcpy(&acl->name, name, name_len); + acl->default_rule = default_rule; + return acl; +} + +void acl_delete(acl_t **acl) +{ + if ((acl == NULL) || (*acl == NULL)) { + return; + } + + /* Truncate rules. */ + if (acl_truncate(*acl) != ACL_ACCEPT) { + return; + } + + /* Free ACL. */ + free(*acl); + *acl = 0; +} + +int acl_create(acl_t *acl, const sockaddr_t* addr, acl_rule_t rule) +{ + if (!acl || !addr || rule < 0) { + return ACL_ERROR; + } + + /* Insert into skip list. */ + sockaddr_t *key = malloc(sizeof(sockaddr_t)); + memcpy(key, addr, sizeof(sockaddr_t)); + + skip_insert(acl->rules, key, (void*)((ssize_t)rule + 1), 0); + + return ACL_ACCEPT; +} + +int acl_match(acl_t *acl, sockaddr_t* addr) +{ + if (!acl || !addr) { + return ACL_ERROR; + } + + /* Return default rule if not found. + * Conversion to the same length integer is made, + * but we can be sure, that the value range is within <-1,1>. + */ + ssize_t val = ((ssize_t)skip_find(acl->rules, addr)) - 1; + if (val < 0) { + return acl->default_rule; + } + + /* Return stored rule if found. */ + return (int)val; +} + +int acl_truncate(acl_t *acl) +{ + if (acl == NULL) { + return ACL_ERROR; + } + + /* Destroy all rules. */ + skip_destroy_list(&acl->rules, free, 0); + + return ACL_ACCEPT; +} diff --git a/src/common/acl.h b/src/common/acl.h new file mode 100644 index 0000000..c79db7f --- /dev/null +++ b/src/common/acl.h @@ -0,0 +1,138 @@ +/* Copyright (C) 2011 CZ.NIC, z.s.p.o. <knot-dns@labs.nic.cz> + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. + */ +/*! + * \file acl.h + * + * \author Marek Vavrusa <marek.vavrusa@nic.cz> + * + * \brief Access control lists. + * + * An access control list is a named structure + * for efficient IP address and port matching. + * + * \addtogroup common_lib + * @{ + */ + +#ifndef _KNOTD_ACL_H_ +#define _KNOTD_ACL_H_ + +#include "common/skip-list.h" +#include "common/sockaddr.h" + +/*! \brief ACL rules types. */ +typedef enum acl_rule_t { + ACL_ERROR = -1, + ACL_DENY = 0, + ACL_ACCEPT = 1 +} acl_rule_t; + +/*! \brief ACL structure. */ +typedef struct acl_t { + acl_rule_t default_rule; + skip_list_t *rules; + const char name[]; +} acl_t; + +/*! + * \brief Create a new ACL. + * + * \param default_rule Default rule for address matching. + * \param name ACL symbolic name (or NULL). + * + * \retval New ACL instance when successful. + * \retval NULL on errors. + */ +acl_t *acl_new(acl_rule_t default_rule, const char *name); + +/*! + * \brief Delete ACL structure. + * + * \param acl Pointer to ACL instance. + */ +void acl_delete(acl_t **acl); + +/*! + * \brief Create new ACL rule. + * + * \todo Support address subnets. + * + * \param acl Pointer to ACL instance. + * \param addr IP address (will be duplicated). + * \param rule Rule. + * + * \retval ACL_ACCEPT if successful. + * \retval ACP_ERROR on error. + */ +int acl_create(acl_t *acl, const sockaddr_t* addr, acl_rule_t rule); + +/*! + * \brief Match address against ACL. + * + * \param acl Pointer to ACL instance. + * \param addr IP address. + * + * \retval ACL_ACCEPT if the address is accepted. + * \retval ACL_DENY if the address is not accepted. + * \retval ACP_ERROR on error. + */ +int acl_match(acl_t *acl, sockaddr_t* addr); + +/*! + * \brief Truncate ACL. + * + * All but the default rule will be dropped. + * + * \param acl Pointer to ACL instance. + * + * \retval ACL_ACCEPT if successful. + * \retval ACP_ERROR on error. + */ +int acl_truncate(acl_t *acl); + +/*! + * \brief Return ACL name. + * + * \param acl Pointer to ACL instance. + * + * \retval ACL name. + */ +static inline const char* acl_name(acl_t *acl) { + if (!acl) { + return 0; + } + + return acl->name; +} + +/*! + * \brief Return ACL rules. + * + * \param acl Pointer to ACL instance. + * + * \retval ACL rules skip-list. + */ +static inline skip_list_t* acl_rules(acl_t *acl) { + if (!acl) { + return 0; + } + + return acl->rules; +} + +#endif /* _KNOTD_ACL_H_ */ + +/*! @} */ diff --git a/src/common/base32.c b/src/common/base32.c new file mode 100644 index 0000000..43b86c1 --- /dev/null +++ b/src/common/base32.c @@ -0,0 +1,539 @@ +/* base32.c -- Encode binary data using printable characters. + Copyright (C) 1999, 2000, 2001, 2004, 2005, 2006, 2010 Free Software + Foundation, Inc. + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 2, or (at your option) + any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program; if not, write to the Free Software Foundation, + Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ + +/* Adapted from base64.{h,c} by Ondřej Surý. base64.{h,c} was written + * by Simon Josefsson. Partially adapted from GNU MailUtils + * (mailbox/filter_trans.c, as of 2004-11-28). Improved by review + * from Paul Eggert, Bruno Haible, and Stepan Kasal. + * + * See also RFC 4648 <http://www.ietf.org/rfc/rfc4648.txt>. + * + * Be careful with error checking. Here is how you would typically + * use these functions: + * + * bool ok = base32_decode_alloc (in, inlen, &out, &outlen); + * if (!ok) + * FAIL: input was not valid base32 + * if (out == NULL) + * FAIL: memory allocation error + * OK: data in OUT/OUTLEN + * + * size_t outlen = base32_encode_alloc (in, inlen, &out); + * if (out == NULL && outlen == 0 && inlen != 0) + * FAIL: input too long + * if (out == NULL) + * FAIL: memory allocation error + * OK: data in OUT/OUTLEN. + * + */ + +/* Get prototype. */ +#include "base32.h" + +/* Get malloc. */ +#include <stdlib.h> + +/* Get UCHAR_MAX. */ +#include <limits.h> + +/* C89 compliant way to cast 'char' to 'unsigned char'. */ +static inline unsigned char to_uchar(char ch) +{ + return ch; +} + +/* Base32 encode IN array of size INLEN into OUT array of size OUTLEN. + If OUTLEN is less than BASE32_LENGTH(INLEN), write as many bytes as + possible. If OUTLEN is larger than BASE32_LENGTH(INLEN), also zero + terminate the output buffer. */ +void base32_encode(const char *in, size_t inlen, char *out, size_t outlen) +{ + static const char b32str[32] = + "ABCDEFGHIJKLMNOPQRSTUVWXYZ234567"; + + while (inlen && outlen) { + *out++ = b32str[(to_uchar(in[0]) >> 3) & 0x1f]; + if (!--outlen) { + break; + } + *out++ = b32str[((to_uchar(in[0]) << 2) + + (--inlen ? to_uchar(in[1]) >> 6 : 0)) + & 0x1f]; + if (!--outlen) { + break; + } + *out++ =(inlen + ? b32str[(to_uchar(in[1]) >> 1) & 0x1f] + : '='); + if (!--outlen) { + break; + } + *out++ = (inlen + ? b32str[((to_uchar(in[1]) << 4) + + (--inlen ? to_uchar(in[2]) >> 4 : 0)) + & 0x1f] + : '='); + if (!--outlen) { + break; + } + *out++ = (inlen + ? b32str[((to_uchar(in[2]) << 1) + + (--inlen ? to_uchar(in[3]) >> 7 : 0)) + & 0x1f] + : '='); + if (!--outlen) { + break; + } + *out++ = (inlen + ? b32str[(to_uchar(in[3]) >> 2) & 0x1f] + : '='); + if (!--outlen) + { + break; + } + *out++ = (inlen + ? b32str[((to_uchar(in[3]) << 3) + + (--inlen ? to_uchar(in[4]) >> 5 : 0)) + & 0x1f] + : '='); + if (!--outlen) { + break; + } + *out++ = inlen ? b32str[to_uchar(in[4]) & 0x1f] : '='; + if (!--outlen) { + break; + } + if (inlen) { + inlen--; + } + if (inlen) { + in += 5; + } + } + + if (outlen) { + *out = '\0'; + } +} + +/* Allocate a buffer and store zero terminated base32 encoded data + from array IN of size INLEN, returning BASE32_LENGTH(INLEN), i.e., + the length of the encoded data, excluding the terminating zero. On + return, the OUT variable will hold a pointer to newly allocated + memory that must be deallocated by the caller. If output string + length would overflow, 0 is returned and OUT is set to NULL. If + memory allocation failed, OUT is set to NULL, and the return value + indicates length of the requested memory block, i.e., + BASE32_LENGTH(inlen) + 1. */ +size_t base32_encode_alloc(const char *in, size_t inlen, char **out) +{ + size_t outlen = 1 + BASE32_LENGTH (inlen); + + /* Check for overflow in outlen computation. + * + * If there is no overflow, outlen >= inlen. + * + * If the operation (inlen + 2) overflows then it yields at most +1, so + * outlen is 0. + * + * If the multiplication overflows, we lose at least half of the + * correct value, so the result is < ((inlen + 2) / 3) * 2, which is + * less than (inlen + 2) * 0.66667, which is less than inlen as soon as + * (inlen > 4). + */ + if (inlen > outlen) + { + *out = NULL; + return 0; + } + + *out = malloc(outlen); + if (!*out) { + return outlen; + } + + base32_encode(in, inlen, *out, outlen); + + return outlen - 1; +} + +/* With this approach this file works independent of the charset used + (think EBCDIC). However, it does assume that the characters in the + Base32 alphabet (A-Z2-7) are encoded in 0..255. POSIX + 1003.1-2001 require that char and unsigned char are 8-bit + quantities, though, taking care of that problem. But this may be a + potential problem on non-POSIX C99 platforms. + + IBM C V6 for AIX mishandles "#define B32(x) ...'x'...", so use "_" + as the formal parameter rather than "x". */ +#define B32(_) \ + ((_) == 'A' ? 0 \ + : (_) == 'B' ? 1 \ + : (_) == 'C' ? 2 \ + : (_) == 'D' ? 3 \ + : (_) == 'E' ? 4 \ + : (_) == 'F' ? 5 \ + : (_) == 'G' ? 6 \ + : (_) == 'H' ? 7 \ + : (_) == 'I' ? 8 \ + : (_) == 'J' ? 9 \ + : (_) == 'K' ? 10 \ + : (_) == 'L' ? 11 \ + : (_) == 'M' ? 12 \ + : (_) == 'N' ? 13 \ + : (_) == 'O' ? 14 \ + : (_) == 'P' ? 15 \ + : (_) == 'Q' ? 16 \ + : (_) == 'R' ? 17 \ + : (_) == 'S' ? 18 \ + : (_) == 'T' ? 19 \ + : (_) == 'U' ? 20 \ + : (_) == 'V' ? 21 \ + : (_) == 'W' ? 22 \ + : (_) == 'X' ? 23 \ + : (_) == 'Y' ? 24 \ + : (_) == 'Z' ? 25 \ + : (_) == '2' ? 26 \ + : (_) == '3' ? 27 \ + : (_) == '4' ? 28 \ + : (_) == '5' ? 29 \ + : (_) == '6' ? 30 \ + : (_) == '7' ? 31 \ + : -1) + +static const signed char b32[0x100] = { + B32 (0), B32 (1), B32 (2), B32 (3), + B32 (4), B32 (5), B32 (6), B32 (7), + B32 (8), B32 (9), B32 (10), B32 (11), + B32 (12), B32 (13), B32 (14), B32 (15), + B32 (16), B32 (17), B32 (18), B32 (19), + B32 (20), B32 (21), B32 (22), B32 (23), + B32 (24), B32 (25), B32 (26), B32 (27), + B32 (28), B32 (29), B32 (30), B32 (31), + B32 (32), B32 (33), B32 (34), B32 (35), + B32 (36), B32 (37), B32 (38), B32 (39), + B32 (40), B32 (41), B32 (42), B32 (43), + B32 (44), B32 (45), B32 (46), B32 (47), + B32 (48), B32 (49), B32 (50), B32 (51), + B32 (52), B32 (53), B32 (54), B32 (55), + B32 (56), B32 (57), B32 (58), B32 (59), + B32 (60), B32 (61), B32 (62), B32 (63), + B32 (64), B32 (65), B32 (66), B32 (67), + B32 (68), B32 (69), B32 (70), B32 (71), + B32 (72), B32 (73), B32 (74), B32 (75), + B32 (76), B32 (77), B32 (78), B32 (79), + B32 (80), B32 (81), B32 (82), B32 (83), + B32 (84), B32 (85), B32 (86), B32 (87), + B32 (88), B32 (89), B32 (90), B32 (91), + B32 (92), B32 (93), B32 (94), B32 (95), + B32 (96), B32 (97), B32 (98), B32 (99), + B32 (100), B32 (101), B32 (102), B32 (103), + B32 (104), B32 (105), B32 (106), B32 (107), + B32 (108), B32 (109), B32 (110), B32 (111), + B32 (112), B32 (113), B32 (114), B32 (115), + B32 (116), B32 (117), B32 (118), B32 (119), + B32 (120), B32 (121), B32 (122), B32 (123), + B32 (124), B32 (125), B32 (126), B32 (127), + B32 (128), B32 (129), B32 (130), B32 (131), + B32 (132), B32 (133), B32 (134), B32 (135), + B32 (136), B32 (137), B32 (138), B32 (139), + B32 (140), B32 (141), B32 (142), B32 (143), + B32 (144), B32 (145), B32 (146), B32 (147), + B32 (148), B32 (149), B32 (150), B32 (151), + B32 (152), B32 (153), B32 (154), B32 (155), + B32 (156), B32 (157), B32 (158), B32 (159), + B32 (160), B32 (161), B32 (162), B32 (163), + B32 (164), B32 (165), B32 (166), B32 (167), + B32 (168), B32 (169), B32 (170), B32 (171), + B32 (172), B32 (173), B32 (174), B32 (175), + B32 (176), B32 (177), B32 (178), B32 (179), + B32 (180), B32 (181), B32 (182), B32 (183), + B32 (184), B32 (185), B32 (186), B32 (187), + B32 (188), B32 (189), B32 (190), B32 (191), + B32 (192), B32 (193), B32 (194), B32 (195), + B32 (196), B32 (197), B32 (198), B32 (199), + B32 (200), B32 (201), B32 (202), B32 (203), + B32 (204), B32 (205), B32 (206), B32 (207), + B32 (208), B32 (209), B32 (210), B32 (211), + B32 (212), B32 (213), B32 (214), B32 (215), + B32 (216), B32 (217), B32 (218), B32 (219), + B32 (220), B32 (221), B32 (222), B32 (223), + B32 (224), B32 (225), B32 (226), B32 (227), + B32 (228), B32 (229), B32 (230), B32 (231), + B32 (232), B32 (233), B32 (234), B32 (235), + B32 (236), B32 (237), B32 (238), B32 (239), + B32 (240), B32 (241), B32 (242), B32 (243), + B32 (244), B32 (245), B32 (246), B32 (247), + B32 (248), B32 (249), B32 (250), B32 (251), + B32 (252), B32 (253), B32 (254), B32 (255) +}; + +#if UCHAR_MAX == 255 +#define uchar_in_range(c) true +#else +#define uchar_in_range(c) ((c) <= 255) +#endif + +/* Return true if CH is a character from the Base32 alphabet, and + false otherwise. Note that '=' is padding and not considered to be + part of the alphabet. */ +bool isbase32(char ch) +{ + return uchar_in_range(to_uchar(ch)) && 0 <= b32[to_uchar(ch)]; +} + +/* Decode base32 encoded input array IN of length INLEN to output + array OUT that can hold *OUTLEN bytes. Return true if decoding was + successful, i.e. if the input was valid base32 data, false + otherwise. If *OUTLEN is too small, as many bytes as possible will + be written to OUT. On return, *OUTLEN holds the length of decoded + bytes in OUT. Note that as soon as any non-alphabet characters are + encountered, decoding is stopped and false is returned. This means + that, when applicable, you must remove any line terminators that is + part of the data stream before calling this function. */ +bool base32_decode(const char *in, size_t inlen, char *out, size_t *outlen) +{ + size_t outleft = *outlen; + + while (inlen >= 2) { + if (!isbase32(in[0]) || !isbase32(in[1])) { + break; + } + + if (outleft) { + *out++ = ((b32[to_uchar(in[0])] << 3) + | (b32[to_uchar(in[1])] >> 2)); + outleft--; + } + + if (inlen == 2) { + break; + } + + if (in[2] == '=') { + if (inlen != 8) { + break; + } + + if ((in[3] != '=') || + (in[4] != '=') || + (in[5] != '=') || + (in[6] != '=') || + (in[7] != '=')) { + break; + } + } else { + if (!isbase32(in[2]) || !isbase32(in[3])) { + break; + } + + if (outleft) { + *out++ = ((b32[to_uchar(in[1])] << 6) + | ((b32[to_uchar(in[2])] << 1) & 0x3E) + | (b32[to_uchar(in[3])] >> 4)); + outleft--; + } + + if (inlen == 4) { + break; + } + + if (in[4] == '=') { + if (inlen != 8) { + break; + } + + if ((in[5] != '=') || + (in[6] != '=') || + (in[7] != '=')) { + break; + } + } else { + if (!isbase32 (in[3]) || !isbase32(in[4])) { + break; + } + + if (outleft) { + *out++ = ((b32[to_uchar(in[3])] << 4) + | (b32[to_uchar(in[4])] >> 1)); + outleft--; + } + + if (inlen == 5) { + break; + } + + if (in[5] == '=') { + if (inlen != 8) { + break; + } + + if ((in[6] != '=') + || (in[7] != '=')) { + break; + } + } else { + if (!isbase32 (in[5]) + || !isbase32 (in[6])) { + break; + } + + if (outleft) { + *out++ = ((b32[to_uchar(in[4])] + << 7) + | (b32[to_uchar(in[5])] << 2) + | (b32[to_uchar(in[6])] + >> 3)); + outleft--; + } + + if (inlen == 7) { + break; + } + + if (in[7] == '=') { + if (inlen != 8) { + break; + } + } else { + if (!isbase32 (in[7])) { + break; + } + + if (outleft) { + *out++ = + ((b32[to_uchar(in[6])] + << 5) | (b32[ + to_uchar(in[7])])); + outleft--; + } + } + } + } + } + + in += 8; + inlen -= 8; + } + + *outlen -= outleft; + + if (inlen != 0) { + return false; + } + + return true; +} + +/* Allocate an output buffer in *OUT, and decode the base32 encoded + data stored in IN of size INLEN to the *OUT buffer. On return, the + size of the decoded data is stored in *OUTLEN. OUTLEN may be NULL, + if the caller is not interested in the decoded length. *OUT may be + NULL to indicate an out of memory error, in which case *OUTLEN + contains the size of the memory block needed. The function returns + true on successful decoding and memory allocation errors. (Use the + *OUT and *OUTLEN parameters to differentiate between successful + decoding and memory error.) The function returns false if the + input was invalid, in which case *OUT is NULL and *OUTLEN is + undefined. */ +bool base32_decode_alloc(const char *in, size_t inlen, char **out, + size_t *outlen) +{ + /* This may allocate a few bytes too much, depending on input, + but it's not worth the extra CPU time to compute the exact amount. + The exact amount is 5 * inlen / 8, minus 1 if the input ends + with "=" and minus another 1 if the input ends with "==", etc. + Dividing before multiplying avoids the possibility of overflow. */ + size_t needlen = 5 * (inlen / 8) + 4; + + *out = malloc(needlen); + if (!*out) { + return true; + } + + if (!base32_decode(in, inlen, *out, &needlen)) { + free (*out); + *out = NULL; + return false; + } + + if (outlen) { + *outlen = needlen; + } + + return true; +} + +#ifdef MAIN + +#include <stddef.h> +#include <stdbool.h> +#include <string.h> +#include <stdio.h> +#include "base32.h" + +int main(int argc, char **argv) { + int i = 1; + size_t inlen, outlen, argvlen; + char *out; + char *in; + bool ok; + + while (argc > 1) { + argv++; argc--; + argvlen = strlen(*argv); + + outlen = base32_encode_alloc(*argv, argvlen, &out); + + if (out == NULL && outlen == 0 && inlen != 0) { + fprintf(stderr, "ERROR(encode): input too long: %zd\n", + outlen); + return 1; + } + + if (out == NULL) { + fprintf(stderr, "ERROR(encode): memory allocation error" + "\n"); + return 1; + } + + ok = base32_decode_alloc(out, outlen, &in, &inlen); + + if (!ok) { + fprintf(stderr, "ERROR(decode): input was not valid " + "base32: `%s'\n", out); + return 1; + } + + if (in == NULL) { + fprintf(stderr, "ERROR(decode): memory allocation " + "error\n"); + } + + if ((inlen != argvlen) || + strcmp(*argv, in) != 0) { + fprintf(stderr, "ERROR(encode/decode): input `%s' and " + "output `%s'\n", *argv, in); + return 1; + } + printf("INPUT: `%s'\nENCODE: `%s'\nDECODE: `%s'\n", *argv, out, + in); + } +} + +#endif diff --git a/src/common/base32.h b/src/common/base32.h new file mode 100644 index 0000000..45df9fa --- /dev/null +++ b/src/common/base32.h @@ -0,0 +1,121 @@ +/* base32.h -- Encode binary data using printable characters. + Copyright (C) 2004, 2005, 2006, 2010 Free Software Foundation, Inc. + Written by Ondřej Surý & Simon Josefsson. + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 2, or (at your option) + any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program; if not, write to the Free Software Foundation, + Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ + +#ifndef _BASE32_H_ +#define _BASE32_H_ + +/* Get size_t. */ +#include <stddef.h> + +/* Get bool. */ +#include <stdbool.h> + +/*! + * \brief Counts the size of the Base32-encoded output for given input length. + * + * \note This uses that the expression (n+(k-1))/k means the smallest + * integer >= n/k, i.e., the ceiling of n/k. + */ +#define BASE32_LENGTH(inlen) ((((inlen) + 4) / 5) * 8) + +/*! + * \brief Checks if the given character belongs to the Base32 alphabet. + * + * \param ch Character to check. + * + * \retval true if \a ch belongs to the Base32 alphabet. + * \retval false otherwise. + */ +extern bool isbase32(char ch); + +/*! + * \brief Encodes the given character array using Base32 encoding. + * + * If \a outlen is less than BASE32_LENGTH(\a inlen), the function writes as + * many bytes as possible to the output buffer. If \a outlen is more than + * BASE32_LENGTH(\a inlen), the output will be zero-terminated. + * + * \param in Input array of characters. + * \param inlen Length of the input array. + * \param out Output buffer. + * \param outlen Size of the output buffer. + */ +extern void base32_encode(const char *in, size_t inlen, char *out, + size_t outlen); + +/*! + * \brief Encodes the given character array using Base32 encoding and allocates + * space for the output. + * + * \param in Input array of characters. + * \param inlen Length of the input array. + * \param out Output buffer. + * + * \return Size of the allocated output buffer (0 if failed). + */ +extern size_t base32_encode_alloc(const char *in, size_t inlen, char **out); + +/*! + * \brief Decodes the given character array in Base32 encoding. + * + * If \a *outlen is too small, as many bytes as possible will be written to + * \a out. On return, \a *outlen holds the length of decoded bytes in \a out. + * + * \note As soon as any non-alphabet characters are encountered, decoding is + * stopped and false is returned. This means that, when applicable, you + * must remove any line terminators that is part of the data stream before + * calling this function. + * + * \param in Input array of characters. + * \param inlen Length of the input array. + * \param out Output buffer. + * \param outlen Size of the output buffer. + * + * \retval true if decoding was successful, i.e. if the input was valid base32 + * data. + * \retval false otherwise. + */ +extern bool base32_decode(const char *in, size_t inlen, char *out, + size_t *outlen); + +/*! + * \brief Allocate an output buffer and decode the base32 encoded data to it. + * + * On return, the size of the decoded data is stored in \a *outlen. \a outlen + * may be NULL, if the caller is not interested in the decoded length. \a *out + * may be NULL to indicate an out of memory error, in which case \a *outlen + * contains the size of the memory block needed. + * + * \param in Input array of characters. + * \param inlen Length of the input array. + * \param out Output buffer. \a *out may be NULL to indicate an out of memory + * error in which case \a *outlen contains the size of the memory + * block needed + * \param outlen Size of the output buffer. May be NULL, if the caller is not + * interested in the decoded length + * + * \retval true on successful decoding and memory allocation errors. (Use the + * \a *out and \a *outlen parameters to differentiate between + * successful decoding and memory error.) + * \retval false if the input was invalid, in which case \a *out is NULL and + * \a *outlen is undefined. + */ +extern bool base32_decode_alloc(const char *in, size_t inlen, char **out, + size_t *outlen); + +#endif /* _BASE32_H_ */ diff --git a/src/common/base32hex.c b/src/common/base32hex.c new file mode 100644 index 0000000..cd2d2ce --- /dev/null +++ b/src/common/base32hex.c @@ -0,0 +1,562 @@ +/* base32hex.c -- Encode binary data using printable characters. + Copyright (C) 1999, 2000, 2001, 2004, 2005, 2006, 2010 Free Software + Foundation, Inc. + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 2, or (at your option) + any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program; if not, write to the Free Software Foundation, + Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ + +/* Adapted from base32.{h,c}. base32.{h,c} was adapted from + * base64.{h,c} by Ondřej Surý. base64.{h,c} was written by Simon + * Josefsson. Partially adapted from GNU MailUtils + * (mailbox/filter_trans.c, as of 2004-11-28). Improved by review + * from Paul Eggert, Bruno Haible, and Stepan Kasal. + * + * See also RFC 4648 <http://www.ietf.org/rfc/rfc4648.txt>. + * + * Be careful with error checking. Here is how you would typically + * use these functions: + * + * bool ok = base32hex_decode_alloc (in, inlen, &out, &outlen); + * if (!ok) + * FAIL: input was not valid base32hex + * if (out == NULL) + * FAIL: memory allocation error + * OK: data in OUT/OUTLEN + * + * size_t outlen = base32hex_encode_alloc (in, inlen, &out); + * if (out == NULL && outlen == 0 && inlen != 0) + * FAIL: input too long + * if (out == NULL) + * FAIL: memory allocation error + * OK: data in OUT/OUTLEN. + * + */ + +/* Get prototype. */ +#include "base32hex.h" + +/* Get malloc. */ +#include <stdlib.h> + +/* Get UCHAR_MAX. */ +#include <limits.h> + +/* C89 compliant way to cast 'char' to 'unsigned char'. */ +static inline unsigned char to_uchar(char ch) +{ + return ch; +} + +/* Base32hex encode IN array of size INLEN into OUT array of size OUTLEN. + If OUTLEN is less than BASE32HEX_LENGTH(INLEN), write as many bytes as + possible. If OUTLEN is larger than BASE32HEX_LENGTH(INLEN), also zero + terminate the output buffer. */ +void base32hex_encode(const char *in, size_t inlen, char *out, size_t outlen) +{ + static const char b32str[32] = + "0123456789ABCDEFGHIJKLMNOPQRSTUV"; + + while (inlen && outlen) { + *out++ = b32str[(to_uchar(in[0]) >> 3) & 0x1f]; + if (!--outlen) { + break; + } + *out++ = b32str[((to_uchar(in[0]) << 2) + + (--inlen ? to_uchar(in[1]) >> 6 : 0)) + & 0x1f]; + if (!--outlen) { + break; + } + *out++ =(inlen + ? b32str[(to_uchar(in[1]) >> 1) & 0x1f] + : '='); + if (!--outlen) { + break; + } + *out++ = (inlen + ? b32str[((to_uchar(in[1]) << 4) + + (--inlen ? to_uchar(in[2]) >> 4 : 0)) + & 0x1f] + : '='); + if (!--outlen) { + break; + } + *out++ = (inlen + ? b32str[((to_uchar(in[2]) << 1) + + (--inlen ? to_uchar(in[3]) >> 7 : 0)) + & 0x1f] + : '='); + if (!--outlen) { + break; + } + *out++ = (inlen + ? b32str[(to_uchar(in[3]) >> 2) & 0x1f] + : '='); + if (!--outlen) + { + break; + } + *out++ = (inlen + ? b32str[((to_uchar(in[3]) << 3) + + (--inlen ? to_uchar(in[4]) >> 5 : 0)) + & 0x1f] + : '='); + if (!--outlen) { + break; + } + *out++ = inlen ? b32str[to_uchar(in[4]) & 0x1f] : '='; + if (!--outlen) { + break; + } + if (inlen) { + inlen--; + } + if (inlen) { + in += 5; + } + } + + if (outlen) { + *out = '\0'; + } +} + +/* Allocate a buffer and store zero terminated base32hex encoded data + from array IN of size INLEN, returning BASE32HEX_LENGTH(INLEN), i.e., + the length of the encoded data, excluding the terminating zero. On + return, the OUT variable will hold a pointer to newly allocated + memory that must be deallocated by the caller. If output string + length would overflow, 0 is returned and OUT is set to NULL. If + memory allocation failed, OUT is set to NULL, and the return value + indicates length of the requested memory block, i.e., + BASE32HEX_LENGTH(inlen) + 1. */ +size_t base32hex_encode_alloc(const char *in, size_t inlen, char **out) +{ + size_t outlen = 1 + BASE32HEX_LENGTH (inlen); + + /* Check for overflow in outlen computation. + * + * If there is no overflow, outlen >= inlen. + * + * If the operation (inlen + 2) overflows then it yields at most +1, so + * outlen is 0. + * + * If the multiplication overflows, we lose at least half of the + * correct value, so the result is < ((inlen + 2) / 3) * 2, which is + * less than (inlen + 2) * 0.66667, which is less than inlen as soon as + * (inlen > 4). + */ + if (inlen > outlen) + { + *out = NULL; + return 0; + } + + *out = malloc(outlen); + if (!*out) { + return outlen; + } + + base32hex_encode(in, inlen, *out, outlen); + + return outlen - 1; +} + +/* With this approach this file works independent of the charset used + (think EBCDIC). However, it does assume that the characters in the + Base32hex alphabet (A-Z2-7) are encoded in 0..255. POSIX + 1003.1-2001 require that char and unsigned char are 8-bit + quantities, though, taking care of that problem. But this may be a + potential problem on non-POSIX C99 platforms. + + IBM C V6 for AIX mishandles "#define B32(x) ...'x'...", so use "_" + as the formal parameter rather than "x". */ +#define B32(_) \ + ((_) == '0' ? 0 \ + : (_) == '1' ? 1 \ + : (_) == '2' ? 2 \ + : (_) == '3' ? 3 \ + : (_) == '4' ? 4 \ + : (_) == '5' ? 5 \ + : (_) == '6' ? 6 \ + : (_) == '7' ? 7 \ + : (_) == '8' ? 8 \ + : (_) == '9' ? 9 \ + : (_) == 'A' ? 10 \ + : (_) == 'B' ? 11 \ + : (_) == 'C' ? 12 \ + : (_) == 'D' ? 13 \ + : (_) == 'E' ? 14 \ + : (_) == 'F' ? 15 \ + : (_) == 'G' ? 16 \ + : (_) == 'H' ? 17 \ + : (_) == 'I' ? 18 \ + : (_) == 'J' ? 19 \ + : (_) == 'K' ? 20 \ + : (_) == 'L' ? 21 \ + : (_) == 'M' ? 22 \ + : (_) == 'N' ? 23 \ + : (_) == 'O' ? 24 \ + : (_) == 'P' ? 25 \ + : (_) == 'Q' ? 26 \ + : (_) == 'R' ? 27 \ + : (_) == 'S' ? 28 \ + : (_) == 'T' ? 29 \ + : (_) == 'U' ? 30 \ + : (_) == 'V' ? 31 \ + : (_) == 'a' ? 10 \ + : (_) == 'b' ? 11 \ + : (_) == 'c' ? 12 \ + : (_) == 'd' ? 13 \ + : (_) == 'e' ? 14 \ + : (_) == 'f' ? 15 \ + : (_) == 'g' ? 16 \ + : (_) == 'h' ? 17 \ + : (_) == 'i' ? 18 \ + : (_) == 'j' ? 19 \ + : (_) == 'k' ? 20 \ + : (_) == 'l' ? 21 \ + : (_) == 'm' ? 22 \ + : (_) == 'n' ? 23 \ + : (_) == 'o' ? 24 \ + : (_) == 'p' ? 25 \ + : (_) == 'q' ? 26 \ + : (_) == 'r' ? 27 \ + : (_) == 's' ? 28 \ + : (_) == 't' ? 29 \ + : (_) == 'u' ? 30 \ + : (_) == 'v' ? 31 \ + : -1) + +static const signed char b32[0x100] = { + B32 (0), B32 (1), B32 (2), B32 (3), + B32 (4), B32 (5), B32 (6), B32 (7), + B32 (8), B32 (9), B32 (10), B32 (11), + B32 (12), B32 (13), B32 (14), B32 (15), + B32 (16), B32 (17), B32 (18), B32 (19), + B32 (20), B32 (21), B32 (22), B32 (23), + B32 (24), B32 (25), B32 (26), B32 (27), + B32 (28), B32 (29), B32 (30), B32 (31), + B32 (32), B32 (33), B32 (34), B32 (35), + B32 (36), B32 (37), B32 (38), B32 (39), + B32 (40), B32 (41), B32 (42), B32 (43), + B32 (44), B32 (45), B32 (46), B32 (47), + B32 (48), B32 (49), B32 (50), B32 (51), + B32 (52), B32 (53), B32 (54), B32 (55), + B32 (56), B32 (57), B32 (58), B32 (59), + B32 (60), B32 (61), B32 (62), B32 (63), + B32 (64), B32 (65), B32 (66), B32 (67), + B32 (68), B32 (69), B32 (70), B32 (71), + B32 (72), B32 (73), B32 (74), B32 (75), + B32 (76), B32 (77), B32 (78), B32 (79), + B32 (80), B32 (81), B32 (82), B32 (83), + B32 (84), B32 (85), B32 (86), B32 (87), + B32 (88), B32 (89), B32 (90), B32 (91), + B32 (92), B32 (93), B32 (94), B32 (95), + B32 (96), B32 (97), B32 (98), B32 (99), + B32 (100), B32 (101), B32 (102), B32 (103), + B32 (104), B32 (105), B32 (106), B32 (107), + B32 (108), B32 (109), B32 (110), B32 (111), + B32 (112), B32 (113), B32 (114), B32 (115), + B32 (116), B32 (117), B32 (118), B32 (119), + B32 (120), B32 (121), B32 (122), B32 (123), + B32 (124), B32 (125), B32 (126), B32 (127), + B32 (128), B32 (129), B32 (130), B32 (131), + B32 (132), B32 (133), B32 (134), B32 (135), + B32 (136), B32 (137), B32 (138), B32 (139), + B32 (140), B32 (141), B32 (142), B32 (143), + B32 (144), B32 (145), B32 (146), B32 (147), + B32 (148), B32 (149), B32 (150), B32 (151), + B32 (152), B32 (153), B32 (154), B32 (155), + B32 (156), B32 (157), B32 (158), B32 (159), + B32 (160), B32 (161), B32 (162), B32 (163), + B32 (164), B32 (165), B32 (166), B32 (167), + B32 (168), B32 (169), B32 (170), B32 (171), + B32 (172), B32 (173), B32 (174), B32 (175), + B32 (176), B32 (177), B32 (178), B32 (179), + B32 (180), B32 (181), B32 (182), B32 (183), + B32 (184), B32 (185), B32 (186), B32 (187), + B32 (188), B32 (189), B32 (190), B32 (191), + B32 (192), B32 (193), B32 (194), B32 (195), + B32 (196), B32 (197), B32 (198), B32 (199), + B32 (200), B32 (201), B32 (202), B32 (203), + B32 (204), B32 (205), B32 (206), B32 (207), + B32 (208), B32 (209), B32 (210), B32 (211), + B32 (212), B32 (213), B32 (214), B32 (215), + B32 (216), B32 (217), B32 (218), B32 (219), + B32 (220), B32 (221), B32 (222), B32 (223), + B32 (224), B32 (225), B32 (226), B32 (227), + B32 (228), B32 (229), B32 (230), B32 (231), + B32 (232), B32 (233), B32 (234), B32 (235), + B32 (236), B32 (237), B32 (238), B32 (239), + B32 (240), B32 (241), B32 (242), B32 (243), + B32 (244), B32 (245), B32 (246), B32 (247), + B32 (248), B32 (249), B32 (250), B32 (251), + B32 (252), B32 (253), B32 (254), B32 (255) +}; + +#if UCHAR_MAX == 255 +#define uchar_in_range(c) true +#else +#define uchar_in_range(c) ((c) <= 255) +#endif + +/* Return true if CH is a character from the Base32hex alphabet, and + false otherwise. Note that '=' is padding and not considered to be + part of the alphabet. */ +bool isbase32hex(char ch) +{ + return uchar_in_range(to_uchar(ch)) && 0 <= b32[to_uchar(ch)]; +} + +/* Decode base32hex encoded input array IN of length INLEN to output + array OUT that can hold *OUTLEN bytes. Return true if decoding was + successful, i.e. if the input was valid base32hex data, false + otherwise. If *OUTLEN is too small, as many bytes as possible will + be written to OUT. On return, *OUTLEN holds the length of decoded + bytes in OUT. Note that as soon as any non-alphabet characters are + encountered, decoding is stopped and false is returned. This means + that, when applicable, you must remove any line terminators that is + part of the data stream before calling this function. */ +bool base32hex_decode(const char *in, size_t inlen, char *out, size_t *outlen) +{ + size_t outleft = *outlen; + + while (inlen >= 2) { + if (!isbase32hex(in[0]) || !isbase32hex(in[1])) { + break; + } + + if (outleft) { + *out++ = ((b32[to_uchar(in[0])] << 3) + | (b32[to_uchar(in[1])] >> 2)); + outleft--; + } + + if (inlen == 2) { + break; + } + + if (in[2] == '=') { + if (inlen != 8) { + break; + } + + if ((in[3] != '=') || + (in[4] != '=') || + (in[5] != '=') || + (in[6] != '=') || + (in[7] != '=')) { + break; + } + } else { + if (!isbase32hex(in[2]) || !isbase32hex(in[3])) { + break; + } + + if (outleft) { + *out++ = ((b32[to_uchar(in[1])] << 6) + | ((b32[to_uchar(in[2])] << 1) & 0x3E) + | (b32[to_uchar(in[3])] >> 4)); + outleft--; + } + + if (inlen == 4) { + break; + } + + if (in[4] == '=') { + if (inlen != 8) { + break; + } + + if ((in[5] != '=') || + (in[6] != '=') || + (in[7] != '=')) { + break; + } + } else { + if (!isbase32hex (in[3]) || !isbase32hex(in[4])) { + break; + } + + if (outleft) { + *out++ = ((b32[to_uchar(in[3])] << 4) + | (b32[to_uchar(in[4])] >> 1)); + outleft--; + } + + if (inlen == 5) { + break; + } + + if (in[5] == '=') { + if (inlen != 8) { + break; + } + + if ((in[6] != '=') + || (in[7] != '=')) { + break; + } + } else { + if (!isbase32hex (in[5]) + || !isbase32hex (in[6])) { + break; + } + + if (outleft) { + *out++ = ((b32[to_uchar(in[4])] + << 7) + | (b32[to_uchar(in[5])] << 2) + | (b32[to_uchar(in[6])] + >> 3)); + outleft--; + } + + if (inlen == 7) { + break; + } + + if (in[7] == '=') { + if (inlen != 8) { + break; + } + } else { + if (!isbase32hex (in[7])) { + break; + } + + if (outleft) { + *out++ = + ((b32[to_uchar(in[6])] + << 5) | (b32[ + to_uchar(in[7])])); + outleft--; + } + } + } + } + } + + in += 8; + inlen -= 8; + } + + *outlen -= outleft; + + if (inlen != 0) { + return false; + } + + return true; +} + +/* Allocate an output buffer in *OUT, and decode the base32hex encoded + data stored in IN of size INLEN to the *OUT buffer. On return, the + size of the decoded data is stored in *OUTLEN. OUTLEN may be NULL, + if the caller is not interested in the decoded length. *OUT may be + NULL to indicate an out of memory error, in which case *OUTLEN + contains the size of the memory block needed. The function returns + true on successful decoding and memory allocation errors. (Use the + *OUT and *OUTLEN parameters to differentiate between successful + decoding and memory error.) The function returns false if the + input was invalid, in which case *OUT is NULL and *OUTLEN is + undefined. */ +bool base32hex_decode_alloc(const char *in, size_t inlen, char **out, + size_t *outlen) +{ + /* This may allocate a few bytes too much, depending on input, + but it's not worth the extra CPU time to compute the exact amount. + The exact amount is 5 * inlen / 8, minus 1 if the input ends + with "=" and minus another 1 if the input ends with "==", etc. + Dividing before multiplying avoids the possibility of overflow. */ + size_t needlen = 5 * (inlen / 8) + 4; + + *out = malloc(needlen); + if (!*out) { + return true; + } + + if (!base32hex_decode(in, inlen, *out, &needlen)) { + free (*out); + *out = NULL; + return false; + } + + if (outlen) { + *outlen = needlen; + } + + return true; +} + +#ifdef MAIN + +#include <stddef.h> +#include <stdbool.h> +#include <string.h> +#include <stdio.h> +#include "base32hex.h" + +int main(int argc, char **argv) { + int i = 1; + size_t inlen, outlen, argvlen; + char *out; + char *in; + bool ok; + + while (argc > 1) { + argv++; argc--; + argvlen = strlen(*argv); + + outlen = base32hex_encode_alloc(*argv, argvlen, &out); + + if (out == NULL && outlen == 0 && inlen != 0) { + fprintf(stderr, "ERROR(encode): input too long: %zd\n", + outlen); + return 1; + } + + if (out == NULL) { + fprintf(stderr, "ERROR(encode): memory allocation error" + "\n"); + return 1; + } + + ok = base32hex_decode_alloc(out, outlen, &in, &inlen); + + if (!ok) { + fprintf(stderr, "ERROR(decode): input was not valid " + "base32hex: `%s'\n", out); + return 1; + } + + if (in == NULL) { + fprintf(stderr, "ERROR(decode): memory allocation " + "error\n"); + } + + if ((inlen != argvlen) || + strcmp(*argv, in) != 0) { + fprintf(stderr, "ERROR(encode/decode): input `%s' and " + "output `%s'\n", *argv, in); + return 1; + } + printf("INPUT: `%s'\nENCODE: `%s'\nDECODE: `%s'\n", *argv, out, + in); + } +} + +#endif diff --git a/src/common/base32hex.h b/src/common/base32hex.h new file mode 100644 index 0000000..9ac4fa8 --- /dev/null +++ b/src/common/base32hex.h @@ -0,0 +1,124 @@ +/* base32hex.h -- Encode binary data using printable characters. + Copyright (C) 2004, 2005, 2006, 2010 Free Software Foundation, Inc. + Written by Ondřej Surý & Simon Josefsson. + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 2, or (at your option) + any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program; if not, write to the Free Software Foundation, + Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ + +#ifndef _BASE32HEX_H_ +#define _BASE32HEX_H_ + +/* Get size_t. */ +#include <stddef.h> + +/* Get bool. */ +#include <stdbool.h> + +/*! + * \brief Counts the size of the Base32Hex-encoded output for given input + * length. + * + * \note This uses that the expression (n+(k-1))/k means the smallest + * integer >= n/k, i.e., the ceiling of n/k. + */ +#define BASE32HEX_LENGTH(inlen) ((((inlen) + 4) / 5) * 8) + +/*! + * \brief Checks if the given character belongs to the Base32Hex alphabet. + * + * \param ch Character to check. + * + * \retval true if \a ch belongs to the Base32Hex alphabet. + * \retval false otherwise. + */ +extern bool isbase32hex(char ch); + +/*! + * \brief Encodes the given character array using Base32 encoding with extended + * hex alphabet. + * + * If \a outlen is less than BASE32HEX_LENGTH(\a inlen), the function writes as + * many bytes as possible to the output buffer. If \a outlen is more than + * BASE32HEX_LENGTH(\a inlen), the output will be zero-terminated. + * + * \param in Input array of characters. + * \param inlen Length of the input array. + * \param out Output buffer. + * \param outlen Size of the output buffer. + */ +extern void base32hex_encode(const char *in, size_t inlen, char *out, + size_t outlen); + +/*! + * \brief Encodes the given character array using Base32 encoding with extended + * hex alphabet and allocates space for the output. + * + * \param in Input array of characters. + * \param inlen Length of the input array. + * \param out Output buffer. + * + * \return Size of the allocated output buffer (0 if failed). + */ +extern size_t base32hex_encode_alloc(const char *in, size_t inlen, char **out); + +/*! + * \brief Decodes the given character array in Base32 encoding with extended + * hex alphabet. + * + * If \a *outlen is too small, as many bytes as possible will be written to + * \a out. On return, \a *outlen holds the length of decoded bytes in \a out. + * + * \note As soon as any non-alphabet characters are encountered, decoding is + * stopped and false is returned. This means that, when applicable, you + * must remove any line terminators that is part of the data stream before + * calling this function. + * + * \param in Input array of characters. + * \param inlen Length of the input array. + * \param out Output buffer. + * \param outlen Size of the output buffer. + * + * \retval true if decoding was successful, i.e. if the input was valid + * base32hex data. + * \retval false otherwise. + */ +extern bool base32hex_decode(const char *in, size_t inlen, char *out, + size_t *outlen); + +/*! + * \brief Allocate an output buffer and decode the base32hex encoded data to it. + * + * On return, the size of the decoded data is stored in \a *outlen. \a outlen + * may be NULL, if the caller is not interested in the decoded length. \a *out + * may be NULL to indicate an out of memory error, in which case \a *outlen + * contains the size of the memory block needed. + * + * \param in Input array of characters. + * \param inlen Length of the input array. + * \param out Output buffer. \a *out may be NULL to indicate an out of memory + * error in which case \a *outlen contains the size of the memory + * block needed + * \param outlen Size of the output buffer. May be NULL, if the caller is not + * interested in the decoded length + * + * \retval true on successful decoding and memory allocation errors. (Use the + * \a *out and \a *outlen parameters to differentiate between + * successful decoding and memory error.) + * \retval false if the input was invalid, in which case \a *out is NULL and + * \a *outlen is undefined. + */ +extern bool base32hex_decode_alloc(const char *in, size_t inlen, char **out, + size_t *outlen); + +#endif /* _BASE32HEX_H_ */ diff --git a/src/common/crc.c b/src/common/crc.c new file mode 100644 index 0000000..33bf903 --- /dev/null +++ b/src/common/crc.c @@ -0,0 +1,155 @@ +/* + Copyright (c) 2006-2011, Thomas Pircher <tehpeh@gmx.net> + + Permission is hereby granted, free of charge, to any person obtaining a copy + of this software and associated documentation files (the "Software"), to deal + in the Software without restriction, including without limitation the rights + to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + copies of the Software, and to permit persons to whom the Software is + furnished to do so, subject to the following conditions: + + The above copyright notice and this permission notice shall be included in + all copies or substantial portions of the Software. + + THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN + THE SOFTWARE. + */ + +/** + * \file crc.c + * Functions and types for CRC checks. + * + * Generated on Fri May 6 11:25:47 2011, + * by pycrc v0.7.7, http://www.tty1.net/pycrc/ + * using the configuration: + * Width = 32 + * Poly = 0x04c11db7 + * XorIn = 0xffffffff + * ReflectIn = True + * XorOut = 0xffffffff + * ReflectOut = True + * Algorithm = table-driven + *****************************************************************************/ +#include "crc.h" +#include <stdint.h> +#include <stdlib.h> + +/** + * Static table used for the table_driven implementation. + *****************************************************************************/ +static const crc_t crc_table[256] = { + 0x00000000, 0x77073096, 0xee0e612c, 0x990951ba, + 0x076dc419, 0x706af48f, 0xe963a535, 0x9e6495a3, + 0x0edb8832, 0x79dcb8a4, 0xe0d5e91e, 0x97d2d988, + 0x09b64c2b, 0x7eb17cbd, 0xe7b82d07, 0x90bf1d91, + 0x1db71064, 0x6ab020f2, 0xf3b97148, 0x84be41de, + 0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7, + 0x136c9856, 0x646ba8c0, 0xfd62f97a, 0x8a65c9ec, + 0x14015c4f, 0x63066cd9, 0xfa0f3d63, 0x8d080df5, + 0x3b6e20c8, 0x4c69105e, 0xd56041e4, 0xa2677172, + 0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b, + 0x35b5a8fa, 0x42b2986c, 0xdbbbc9d6, 0xacbcf940, + 0x32d86ce3, 0x45df5c75, 0xdcd60dcf, 0xabd13d59, + 0x26d930ac, 0x51de003a, 0xc8d75180, 0xbfd06116, + 0x21b4f4b5, 0x56b3c423, 0xcfba9599, 0xb8bda50f, + 0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924, + 0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d, + 0x76dc4190, 0x01db7106, 0x98d220bc, 0xefd5102a, + 0x71b18589, 0x06b6b51f, 0x9fbfe4a5, 0xe8b8d433, + 0x7807c9a2, 0x0f00f934, 0x9609a88e, 0xe10e9818, + 0x7f6a0dbb, 0x086d3d2d, 0x91646c97, 0xe6635c01, + 0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e, + 0x6c0695ed, 0x1b01a57b, 0x8208f4c1, 0xf50fc457, + 0x65b0d9c6, 0x12b7e950, 0x8bbeb8ea, 0xfcb9887c, + 0x62dd1ddf, 0x15da2d49, 0x8cd37cf3, 0xfbd44c65, + 0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2, + 0x4adfa541, 0x3dd895d7, 0xa4d1c46d, 0xd3d6f4fb, + 0x4369e96a, 0x346ed9fc, 0xad678846, 0xda60b8d0, + 0x44042d73, 0x33031de5, 0xaa0a4c5f, 0xdd0d7cc9, + 0x5005713c, 0x270241aa, 0xbe0b1010, 0xc90c2086, + 0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f, + 0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4, + 0x59b33d17, 0x2eb40d81, 0xb7bd5c3b, 0xc0ba6cad, + 0xedb88320, 0x9abfb3b6, 0x03b6e20c, 0x74b1d29a, + 0xead54739, 0x9dd277af, 0x04db2615, 0x73dc1683, + 0xe3630b12, 0x94643b84, 0x0d6d6a3e, 0x7a6a5aa8, + 0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1, + 0xf00f9344, 0x8708a3d2, 0x1e01f268, 0x6906c2fe, + 0xf762575d, 0x806567cb, 0x196c3671, 0x6e6b06e7, + 0xfed41b76, 0x89d32be0, 0x10da7a5a, 0x67dd4acc, + 0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5, + 0xd6d6a3e8, 0xa1d1937e, 0x38d8c2c4, 0x4fdff252, + 0xd1bb67f1, 0xa6bc5767, 0x3fb506dd, 0x48b2364b, + 0xd80d2bda, 0xaf0a1b4c, 0x36034af6, 0x41047a60, + 0xdf60efc3, 0xa867df55, 0x316e8eef, 0x4669be79, + 0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236, + 0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f, + 0xc5ba3bbe, 0xb2bd0b28, 0x2bb45a92, 0x5cb36a04, + 0xc2d7ffa7, 0xb5d0cf31, 0x2cd99e8b, 0x5bdeae1d, + 0x9b64c2b0, 0xec63f226, 0x756aa39c, 0x026d930a, + 0x9c0906a9, 0xeb0e363f, 0x72076785, 0x05005713, + 0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38, + 0x92d28e9b, 0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21, + 0x86d3d2d4, 0xf1d4e242, 0x68ddb3f8, 0x1fda836e, + 0x81be16cd, 0xf6b9265b, 0x6fb077e1, 0x18b74777, + 0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c, + 0x8f659eff, 0xf862ae69, 0x616bffd3, 0x166ccf45, + 0xa00ae278, 0xd70dd2ee, 0x4e048354, 0x3903b3c2, + 0xa7672661, 0xd06016f7, 0x4969474d, 0x3e6e77db, + 0xaed16a4a, 0xd9d65adc, 0x40df0b66, 0x37d83bf0, + 0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9, + 0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6, + 0xbad03605, 0xcdd70693, 0x54de5729, 0x23d967bf, + 0xb3667a2e, 0xc4614ab8, 0x5d681b02, 0x2a6f2b94, + 0xb40bbe37, 0xc30c8ea1, 0x5a05df1b, 0x2d02ef8d +}; + +/** + * Reflect all bits of a \a data word of \a data_len bytes. + * + * \param data The data word to be reflected. + * \param data_len The width of \a data expressed in number of bits. + * \return The reflected data. + *****************************************************************************/ +crc_t crc_reflect(crc_t data, size_t data_len) +{ + unsigned int i; + crc_t ret; + + ret = data & 0x01; + for (i = 1; i < data_len; i++) { + data >>= 1; + ret = (ret << 1) | (data & 0x01); + } + return ret; +} + + +/** + * Update the crc value with new data. + * + * \param crc The current crc value. + * \param data Pointer to a buffer of \a data_len bytes. + * \param data_len Number of bytes in the \a data buffer. + * \return The updated crc value. + *****************************************************************************/ +crc_t crc_update(crc_t crc, const unsigned char *data, size_t data_len) +{ + unsigned int tbl_idx; + + while (data_len--) { + tbl_idx = (crc ^ *data) & 0xff; + crc = (crc_table[tbl_idx] ^ (crc >> 8)) & 0xffffffff; + + data++; + } + return crc & 0xffffffff; +} + + + diff --git a/src/common/crc.h b/src/common/crc.h new file mode 100644 index 0000000..41971a9 --- /dev/null +++ b/src/common/crc.h @@ -0,0 +1,110 @@ +/* + Copyright (c) 2006-2011, Thomas Pircher <tehpeh@gmx.net> + + Permission is hereby granted, free of charge, to any person obtaining a copy + of this software and associated documentation files (the "Software"), to deal + in the Software without restriction, including without limitation the rights + to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + copies of the Software, and to permit persons to whom the Software is + furnished to do so, subject to the following conditions: + + The above copyright notice and this permission notice shall be included in + all copies or substantial portions of the Software. + + THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN + THE SOFTWARE. + */ +/** + * \file crc.h + * Functions and types for CRC checks. + * + * Generated on Fri May 6 11:25:43 2011, + * by pycrc v0.7.7, http://www.tty1.net/pycrc/ + * using the configuration: + * Width = 32 + * Poly = 0x04c11db7 + * XorIn = 0xffffffff + * ReflectIn = True + * XorOut = 0xffffffff + * ReflectOut = True + * Algorithm = table-driven + *****************************************************************************/ +#ifndef __CRC_H__ +#define __CRC_H__ + +#include <stdint.h> +#include <stdlib.h> + +#ifdef __cplusplus +extern "C" { +#endif + + +/** + * The definition of the used algorithm. + *****************************************************************************/ +#define CRC_ALGO_TABLE_DRIVEN 1 + + +/** + * The type of the CRC values. + * + * This type must be big enough to contain at least 32 bits. + *****************************************************************************/ +typedef uint32_t crc_t; + + +/** + * Reflect all bits of a \a data word of \a data_len bytes. + * + * \param data The data word to be reflected. + * \param data_len The width of \a data expressed in number of bits. + * \return The reflected data. + *****************************************************************************/ +crc_t crc_reflect(crc_t data, size_t data_len); + + +/** + * Calculate the initial crc value. + * + * \return The initial crc value. + *****************************************************************************/ +static inline crc_t crc_init(void) +{ + return 0xffffffff; +} + + +/** + * Update the crc value with new data. + * + * \param crc The current crc value. + * \param data Pointer to a buffer of \a data_len bytes. + * \param data_len Number of bytes in the \a data buffer. + * \return The updated crc value. + *****************************************************************************/ +crc_t crc_update(crc_t crc, const unsigned char *data, size_t data_len); + + +/** + * Calculate the final crc value. + * + * \param crc The current crc value. + * \return The final crc value. + *****************************************************************************/ +static inline crc_t crc_finalize(crc_t crc) +{ + return crc ^ 0xffffffff; +} + + +#ifdef __cplusplus +} /* closing brace for extern "C" */ +#endif + +#endif /* __CRC_H__ */ diff --git a/src/common/dynamic-array.c b/src/common/dynamic-array.c new file mode 100644 index 0000000..1e2efac --- /dev/null +++ b/src/common/dynamic-array.c @@ -0,0 +1,224 @@ +/* Copyright (C) 2011 CZ.NIC, z.s.p.o. <knot-dns@labs.nic.cz> + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. + */ + +#include <config.h> +#include <pthread.h> +#include <assert.h> +#include <stdio.h> + +#include <urcu.h> + +//#include "common.h" +#include "common/dynamic-array.h" + +#ifndef ERR_ALLOC_FAILED +#define ERR_ALLOC_FAILED fprintf(stderr, "Allocation failed at %s:%d\n", \ + __FILE__, __LINE__) +#endif + +//#define DA_DEBUG + +#ifndef dbg_da +#ifdef DA_DEBUG +#define dbg_da(msg...) fprintf(stderr, msg) +#else +#define dbg_da(msg...) +#endif +#endif + +/*----------------------------------------------------------------------------*/ +/* Private functions */ +/*----------------------------------------------------------------------------*/ + +enum da_resize_type { + DA_LARGER, DA_SMALLER +}; + +typedef enum da_resize_type da_resize_type_t; + +/*----------------------------------------------------------------------------*/ +/*! + * \retval 1 On success. + * \retval -1 On failure. + */ +static int da_resize(da_array_t *array, da_resize_type_t type) +{ + dbg_da("da_resize(): array pointer: %p, items pointer: %p\n", array, + array->items); + + unsigned new_size = ((type == DA_LARGER) + ? (array->allocated *= 2) + : (array->allocated /= 2)); + + void *new_items = malloc(new_size * array->item_size); + if (new_items == NULL) { + ERR_ALLOC_FAILED; + return -1; + } + + dbg_da("Place for new items: %p\n", new_items); + + // copy the contents from the old array to the new + memcpy(new_items, array->items, array->count * array->item_size); + + // do RCU update + void *old_items = rcu_xchg_pointer(&array->items, new_items); + array->allocated = new_size; + + dbg_da("Old items pointer: %p\n", old_items); + + // wait for readers to finish + synchronize_rcu(); + // deallocate the old array + dbg_da("RCU synchronized, deallocating old items array at address %p." + "\n", old_items); + free(old_items); + + return 1; +} + +/*----------------------------------------------------------------------------*/ +/* Public functions */ +/*----------------------------------------------------------------------------*/ + +da_array_t *da_create(unsigned count, size_t item_size) +{ + da_array_t *a = (da_array_t *)malloc(sizeof(da_array_t)); + if (a == NULL) { + ERR_ALLOC_FAILED; + return NULL; + } + da_initialize(a, count, item_size); + return a; +} + +/*----------------------------------------------------------------------------*/ + +int da_initialize(da_array_t *array, unsigned count, size_t item_size) +{ + assert(array != NULL); + pthread_mutex_init(&array->mtx, NULL); + pthread_mutex_lock(&array->mtx); + + array->items = malloc(count * item_size); + if (array->items == NULL) { + array->allocated = 0; + array->count = 0; + ERR_ALLOC_FAILED; + return -1; + } + + array->allocated = count; + array->count = 0; + array->item_size = item_size; + memset(array->items, 0, count * item_size); + + pthread_mutex_unlock(&array->mtx); + return 0; +} + +/*----------------------------------------------------------------------------*/ + +int da_reserve(da_array_t *array, unsigned count) +{ + pthread_mutex_lock(&array->mtx); + unsigned res = 0; + + assert(array->allocated >= array->count); + if ((array->allocated - array->count) >= count) { + dbg_da("Enough place in the array, no resize needed.\n"); + res = 0; + } else { + dbg_da("Resizing array.\n"); + res = da_resize(array, DA_LARGER); + } + pthread_mutex_unlock(&array->mtx); + + return res; +} + +/*----------------------------------------------------------------------------*/ + +int da_occupy(da_array_t *array, unsigned count) +{ + pthread_mutex_lock(&array->mtx); + unsigned res = 0; + assert(array->allocated >= array->count); + + if ((array->allocated - array->count) < count) { + dbg_da("Not enough place to occupy.\n"); + res = -1; + } else { + array->count += count; + } + + pthread_mutex_unlock(&array->mtx); + return res; +} + +/*----------------------------------------------------------------------------*/ + +unsigned da_try_reserve(const da_array_t *array, unsigned count) +{ + assert(array->allocated >= array->count); + if ((array->allocated - array->count) >= count) { + return 0; + } + + return 1; +} + +/*----------------------------------------------------------------------------*/ + +void da_release(da_array_t *array, unsigned count) +{ + pthread_mutex_lock(&array->mtx); + + assert(array->allocated >= array->count); + assert(array->count >= count); + dbg_da("Decreasing count of items in array.\n"); + array->count -= count; + + pthread_mutex_unlock(&array->mtx); +} + +/*----------------------------------------------------------------------------*/ + +void da_destroy(da_array_t *array) +{ + pthread_mutex_lock(&array->mtx); + void *old_items = rcu_dereference(array->items); + rcu_set_pointer(&array->items, NULL); + pthread_mutex_unlock(&array->mtx); + + synchronize_rcu(); + free(old_items); + pthread_mutex_destroy(&array->mtx); +} + +/*----------------------------------------------------------------------------*/ + +void *da_get_items(const da_array_t *array) +{ + return array->items; +} + +/*----------------------------------------------------------------------------*/ + +unsigned da_get_count(const da_array_t *array) +{ + return array->count; +} diff --git a/src/common/dynamic-array.h b/src/common/dynamic-array.h new file mode 100644 index 0000000..77a5d13 --- /dev/null +++ b/src/common/dynamic-array.h @@ -0,0 +1,156 @@ +/* Copyright (C) 2011 CZ.NIC, z.s.p.o. <knot-dns@labs.nic.cz> + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. + */ +/*! + * \file dynamic-array.h + * + * \author Lubos Slovak <lubos.slovak@nic.cz> + * + * \brief Safe dynamic array implementation. + * + * \todo Somehow check if the array is initialized and do not use otherwise. + * Maybe some magic, or so. + * \todo This structure is too slow because of the mutex. + * + * \addtogroup common_lib + * @{ + */ + +#ifndef _KNOTD_COMMON_DYNAMIC_ARRAY_H_ +#define _KNOTD_COMMON_DYNAMIC_ARRAY_H_ + +#include <string.h> +#include <pthread.h> + +/*----------------------------------------------------------------------------*/ +/*! + * \brief Dynamic array structure. + * + * Before using the dynamic array, it must be initialized using da_initialize(). + * When getting individual items always use da_get_items() to obtain pointer to + * the actual array. + * + * Items in the array cannot be dereferenced (it uses void * for storing the + * the items). It is needed to type-cast the item array (obtained by calling + * da_get_items()) to a proper type before dereferencing. + * + * When adding items, first reserve enough space for them by callling + * da_reserve() and subsequently tell the array about the inserted items by + * calling da_occupy(). When removing, the array must be told about the fact + * by calling da_release(). + * + * For getting the actual number of items in array use da_get_count(). + * + * When the array is no more needed, the da_destroy() function must be called + * before deallocating the structure. + */ +struct da_array { + /*! \brief The actual array. The items can't be dereferenced directly.*/ + void *items; + + /*! + * \brief Size of the stored items in bytes (used in counting of space + * needed. + */ + size_t item_size; + + /*! + * \brief Size of allocated space in number of items that can be stored. + */ + unsigned allocated; + + /*! \brief Number of items actually stored in the array. */ + unsigned count; + + /*! \brief Mutex. */ + pthread_mutex_t mtx; +}; + +typedef struct da_array da_array_t; + +/*----------------------------------------------------------------------------*/ +/*! + * \brief Creates and initializes the dynamic array. + * + * Initialization comprises of allocating place for \a count items of size + * \a item_size and setting the items to zeros. + * + * \retval 0 if successful. + * \retval -1 if not successful. + */ +da_array_t *da_create(unsigned count, size_t item_size); + +/*! + * \brief Initializes the dynamic array. + * + * Initialization comprises of allocating place for \a count items of size + * \a item_size and setting the items to zeros. + * + * \retval 0 if successful. + * \retval -1 if not successful. + */ +int da_initialize(da_array_t *array, unsigned count, size_t item_size); + +/*! + * \brief Reserves space for \a count more items. + * + * \retval 0 if successful and resizing was not necessary. + * \retval 1 if successful and the array was enlarged. + * \retval -1 if not successful - resizing was needed but could not be done. + */ +int da_reserve(da_array_t *array, unsigned count); + +/*! + * \brief Increases the number of items in array by \a count. + * + * \retval 0 If successful. + * \retval -1 If not successful (not enough allocated space, i.e. must run + * da_reserve()). + */ +int da_occupy(da_array_t *array, unsigned count); + +/*! + * \brief Tries to reserve space for \a count more items. + * + * \retval 0 if successful and resizing is not necessary. + * \retval 1 if successful but the array will need to be resized. + */ +unsigned da_try_reserve(const da_array_t *array, unsigned count); + +/*! + * \brief Releases space taken by \a count items. + */ +void da_release(da_array_t *array, unsigned count); + +/*! + * \brief Poperly deallocates the array. + */ +void da_destroy(da_array_t *array); + +/*! + * \brief Returns the array of items as a void *. + */ +void *da_get_items(const da_array_t *array); + +/*! + * \brief Returns count of items in the array. + */ +unsigned da_get_count(const da_array_t *array); + +/*----------------------------------------------------------------------------*/ + +#endif /* _KNOTD_COMMON_DYNAMIC_ARRAY_H_ */ + +/*! @} */ diff --git a/src/common/errors.c b/src/common/errors.c new file mode 100644 index 0000000..f1e650d --- /dev/null +++ b/src/common/errors.c @@ -0,0 +1,74 @@ +/* Copyright (C) 2011 CZ.NIC, z.s.p.o. <knot-dns@labs.nic.cz> + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. + */ + +#include <stdarg.h> +#include <stdio.h> +#include <stdlib.h> + +#include "common/errors.h" + +/*! + * \brief Looks up the given id in the lookup table. + * + * \param table Lookup table. + * \param id ID to look up. + * + * \return Item in the lookup table with the given id or NULL if no such is + * present. + */ +static const error_table_t *error_lookup_by_id(const error_table_t *table, + int id) +{ + while (table->name != 0) { + if (table->id == id) { + return table; + } + table++; + } + + return 0; +} + +const char *error_to_str(const error_table_t *table, int code) +{ + const error_table_t *msg = error_lookup_by_id(table, code); + if (msg != 0) { + return msg->name; + } else { + return "Unknown error."; + } +} + +int _map_errno(int fallback_value, int arg0, ...) +{ + /* Iterate all variable-length arguments. */ + va_list ap; + va_start(ap, arg0); + + /* KNOTD_ERROR serves as a sentinel. */ + for (int c = arg0; c != 0; c = va_arg(ap, int)) { + + /* Error code matches with mapped. */ + if (c == errno) { + /* Return negative value of the code. */ + return -abs(c); + } + } + va_end(ap); + + /* Fallback error code. */ + return fallback_value; +} diff --git a/src/common/errors.h b/src/common/errors.h new file mode 100644 index 0000000..a2773ac --- /dev/null +++ b/src/common/errors.h @@ -0,0 +1,80 @@ +/* Copyright (C) 2011 CZ.NIC, z.s.p.o. <knot-dns@labs.nic.cz> + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. + */ +/*! + * \file errors.h + * + * \author Lubos Slovak <lubos.slovak@nic.cz> + * \author Marek Vavrusa <marek.vavrusa@nic.cz> + * + * \brief Error codes and function for getting error message. + * + * \addtogroup common_lib + * @{ + */ + +#ifndef _KNOTD_COMMON_ERROR_H_ +#define _KNOTD_COMMON_ERROR_H_ + +#include <errno.h> + +/*! \brief Error lookup table. */ +typedef struct error_table_t { + int id; + const char *name; +} error_table_t; + +/*! + * \brief Returns error message for the given error code. + * + * \param table Table of error messages to use. + * \param code Error code. + * + * \return String containing the error message. + */ +const char *error_to_str(const error_table_t *table, int code); + +/*! + * \brief Safe errno mapper that automatically appends sentinel value. + * + * \see _map_errno() + * + * \param fallback_value Fallback error value (used if the code could not be + * mapped. + * \param err POSIX errno. + * \param ... List of handled codes. + * + * \return Mapped error code. + */ +#define map_errno(fallback_value, err...) _map_errno(fallback_value, err, 0) + +/*! + * \brief Returns a mapped POSIX errcode. + * + * \warning Last error must be 0, it serves as a sentinel value. + * Use map_errno() instead. + * + * \param fallback_value Fallback error value (used if the code could not be + * mapped. + * \param arg0 First mandatory argument. + * \param ... List of handled codes. + * + * \return Mapped error code. + */ +int _map_errno(int fallback_value, int arg0, ...); + +#endif /* _KNOTD_COMMON_ERROR_H_ */ + +/*! @} */ diff --git a/src/common/evqueue.c b/src/common/evqueue.c new file mode 100644 index 0000000..ca3027f --- /dev/null +++ b/src/common/evqueue.c @@ -0,0 +1,130 @@ +/* Copyright (C) 2011 CZ.NIC, z.s.p.o. <knot-dns@labs.nic.cz> + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. + */ + +#include <string.h> +#include <stdlib.h> +#include <unistd.h> + +#include "common/evqueue.h" + +/*! \brief Singleton application-wide event queue. */ +evqueue_t *s_evqueue = 0; + +evqueue_t *evqueue_new() +{ + evqueue_t* q = malloc(sizeof(evqueue_t)); + + /* Initialize fds. */ + if (pipe(q->fds) < 0) { + free(q); + q = 0; + } + + return q; +} + +void evqueue_free(evqueue_t **q) +{ + /* Check. */ + if (!q) { + return; + } + + /* Invalidate pointer to queue. */ + evqueue_t *eq = *q; + *q = 0; + + /* Deinitialize. */ + close(eq->fds[EVQUEUE_READFD]); + close(eq->fds[EVQUEUE_WRITEFD]); + free(eq); +} + +int evqueue_poll(evqueue_t *q, const struct timespec *ts, + const sigset_t *sigmask) +{ + /* Check. */ + if (!q) { + return -1; + } + + /* Prepare fd set. */ + fd_set rfds; + FD_ZERO(&rfds); + FD_SET(q->fds[EVQUEUE_READFD], &rfds); + + /* Wait for events. */ + int ret = pselect(q->fds[EVQUEUE_READFD] + 1, &rfds, 0, 0, ts, sigmask); + if (ret < 0) { + return -1; + } + + return ret; +} + +int evqueue_read(evqueue_t *q, void *dst, size_t len) +{ + if (!q || !dst || len == 0) { + return -1; + } + + return read(q->fds[EVQUEUE_READFD], dst, len); +} + +int evqueue_write(evqueue_t *q, const void *src, size_t len) +{ + if (!q || !src || len == 0) { + return -1; + } + + return write(q->fds[EVQUEUE_WRITEFD], src, len); +} + +int evqueue_get(evqueue_t *q, event_t *ev) +{ + /* Check. */ + if (!q || !ev) { + return -1; + } + + /* Read data. */ + int ret = evqueue_read(q, ev, sizeof(event_t)); + if (ret != sizeof(event_t)) { + return -1; + } + + /* Set parent. */ + ev->parent = q; + + return 0; +} + +int evqueue_add(evqueue_t *q, const event_t *ev) +{ + /* Check. */ + if (!q || !ev) { + return -1; + } + + /* Write data. */ + int ret = evqueue_write(q, ev, sizeof(event_t)); + if (ret != sizeof(event_t)) { + return -1; + } + + return 0; +} + diff --git a/src/common/evqueue.h b/src/common/evqueue.h new file mode 100644 index 0000000..ffb3860 --- /dev/null +++ b/src/common/evqueue.h @@ -0,0 +1,200 @@ +/* Copyright (C) 2011 CZ.NIC, z.s.p.o. <knot-dns@labs.nic.cz> + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. + */ +/*! + * \file evqueue.h + * + * \author Marek Vavrusa <marek.vavrusa@nic.cz> + * + * \brief Event queue. + * + * \addtogroup common_lib + * @{ + */ + +#ifndef _KNOTD_COMMON_EVQUEUE_H_ +#define _KNOTD_COMMON_EVQUEUE_H_ + +#include <pthread.h> +#include <signal.h> // sigset_t +#include <time.h> +#include <sys/time.h> + +//#include "knot/common.h" +#include "common/lists.h" + +struct event_t; + +/*! + * \brief Event callback. + * + * Pointer to whole event structure is passed to the callback. + * Callback should return 0 on success and negative integer on error. + * + * Example callback: + * \code + * int print_callback(event_t *t) { + * return printf("Callback: %s\n", t->data); + * } + * \endcode + */ +typedef int (*event_cb_t)(struct event_t *); + +/*! + * \brief Event structure. + */ +typedef struct event_t { + node n; /*!< Node for event queue. */ + int type; /*!< Event type. */ + struct timeval tv; /*!< Event scheduled time. */ + void *data; /*!< Usable data ptr. */ + event_cb_t cb; /*!< Event callback. */ + void *parent; /*!< Pointer to parent (evqueue, scheduler...) */ +} event_t; + +/*! + * \brief Event queue constants. + */ +enum { + EVQUEUE_READFD = 0, + EVQUEUE_WRITEFD = 1 +}; + +/*! + * \brief Event queue structure. + */ +typedef struct { + int fds[2]; /*!< Read and Write fds. */ +} evqueue_t; + +/*! + * \brief Create new event queue. + * + * Event queue is thread-safe and POSIX signal-safe. + * It uses piped fds for queueing and pselect(2) to + * wait for events. + * + * \retval New instance on success. + * \retval NULL on error. + */ +evqueue_t *evqueue_new(); + +/*! + * \brief Deinitialize and free event queue. + * + * \param q Pointer to queue instance. + * \note *q is set to 0. + */ +void evqueue_free(evqueue_t **q); + +/*! + * \brief Poll for new events. + * + * Unblocked signals during polling are specified + * in a sigmask. + * + * \param q Event queue. + * \param ts Timeout (or NULL for infinite). + * \param sigmask Bitmask of signals to receive (or NULL). + * + * \retval Number of polled events on success. + * \retval -1 On error or signal interrupt. + */ +int evqueue_poll(evqueue_t *q, const struct timespec *ts, const sigset_t *sigmask); + +/*! + * \brief Return evqueue pollable fd. + * + * \param q Event queue. + * + * \retval File descriptor available for polling. + * \retval -1 On error. + */ +static inline int evqueue_pollfd(evqueue_t *q) { + return q->fds[EVQUEUE_READFD]; +} + +/*! + * \brief Read data from event queue. + * + * This function is useful for sending custom + * events or other data types through the event queue. + * + * \param q Event queue. + * \param dst Destination buffer. + * \param len Number of bytes to read. + * + * \retval Number of read bytes on success. + * \retval -1 on error, \see read(2). + */ +int evqueue_read(evqueue_t *q, void *dst, size_t len); + +/*! + * \brief Write data to event queue. + * + * This function is useful for sending custom + * events or other data types through the event queue. + * + * \param q Event queue. + * \param src Source buffer. + * \param len Number of bytes to write. + * + * \retval Number of written bytes on success. + * \retval -1 on error, \see write(2). + */ +int evqueue_write(evqueue_t *q, const void *src, size_t len); + +/*! + * \brief Read event from event queue. + * + * \param q Event queue. + * \param ev Event structure for writing. + * + * \retval 0 on success. + * \retval -1 on error. + */ +int evqueue_get(evqueue_t *q, event_t *ev); + +/*! + * \brief Add event to queue. + * + * \param q Event queue. + * \param ev Event structure to read. + * + * \retval 0 on success. + * \retval -1 on error. + */ +int evqueue_add(evqueue_t *q, const event_t *ev); + +/* Singleton event queue pointer. */ +extern evqueue_t *s_evqueue; + +/*! + * \brief Event queue singleton. + */ +static inline evqueue_t *evqueue() { + return s_evqueue; +} + +/*! + * \brief Set event queue singleton. + */ +static inline void evqueue_set(evqueue_t *q) { + s_evqueue = q; +} + +#endif /* _KNOTD_COMMON_EVQUEUE_H_ */ + +/*! @} */ diff --git a/src/common/evsched.c b/src/common/evsched.c new file mode 100644 index 0000000..4e56028 --- /dev/null +++ b/src/common/evsched.c @@ -0,0 +1,309 @@ +/* Copyright (C) 2011 CZ.NIC, z.s.p.o. <knot-dns@labs.nic.cz> + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. + */ + +#include <sys/time.h> +#include <stdlib.h> +#include <stdio.h> + +#include "common/evsched.h" + +/*! + * \brief Set event timer to T (now) + dt miliseconds. + */ +static void evsched_settimer(event_t *e, uint32_t dt) +{ + if (!e) { + return; + } + + /* Get absolute time T. */ + gettimeofday(&e->tv, 0); + + /* Add number of seconds. */ + e->tv.tv_sec += dt / 1000; + + /* Add the number of microseconds. */ + e->tv.tv_usec += (dt % 1000) * 1000; + + /* Check for overflow. */ + while (e->tv.tv_usec > 999999) { + e->tv.tv_sec += 1; + e->tv.tv_usec -= 1 * 1000 * 1000; + } +} + +/*! \brief Singleton application-wide event scheduler. */ +evsched_t *s_evsched = 0; + +evsched_t *evsched_new() +{ + evsched_t *s = malloc(sizeof(evsched_t)); + if (!s) { + return 0; + } + + /* Initialize event calendar. */ + pthread_mutex_init(&s->rl, 0); + pthread_mutex_init(&s->mx, 0); + pthread_cond_init(&s->notify, 0); + pthread_mutex_init(&s->cache.lock, 0); + slab_cache_init(&s->cache.alloc, sizeof(event_t)); + init_list(&s->calendar); + return s; +} + +void evsched_delete(evsched_t **s) +{ + if (!s) { + return; + } + if (!*s) { + return; + } + + /* Deinitialize event calendar. */ + pthread_mutex_destroy(&(*s)->rl); + pthread_mutex_destroy(&(*s)->mx); + pthread_cond_destroy(&(*s)->notify); + node *n = 0, *nxt = 0; + WALK_LIST_DELSAFE(n, nxt, (*s)->calendar) { + evsched_event_free((*s), (event_t*)n); + } + + /* Free allocator. */ + slab_cache_destroy(&(*s)->cache.alloc); + pthread_mutex_destroy(&(*s)->cache.lock); + + /* Free scheduler. */ + free(*s); + *s = 0; +} + +event_t *evsched_event_new(evsched_t *s, int type) +{ + if (!s) { + return 0; + } + + /* Allocate. */ + pthread_mutex_lock(&s->cache.lock); + event_t *e = slab_cache_alloc(&s->cache.alloc); + pthread_mutex_unlock(&s->cache.lock); + + /* Initialize. */ + memset(e, 0, sizeof(event_t)); + e->type = type; + return e; +} + +void evsched_event_free(evsched_t *s, event_t *ev) +{ + if (!s || !ev) { + return; + } + + pthread_mutex_lock(&s->cache.lock); + slab_free(ev); + pthread_mutex_unlock(&s->cache.lock); +} + +event_t* evsched_next(evsched_t *s) +{ + /* Check. */ + if (!s) { + return 0; + } + + /* Lock calendar. */ + pthread_mutex_lock(&s->mx); + + while(1) { + + /* Check event queue. */ + if (!EMPTY_LIST(s->calendar)) { + + /* Get current time. */ + struct timeval dt; + gettimeofday(&dt, 0); + + /* Get next event. */ + event_t *next_ev = HEAD(s->calendar); + + /* Immediately return. */ + if (timercmp(&dt, &next_ev->tv, >=)) { + rem_node(&next_ev->n); + pthread_mutex_unlock(&s->mx); + pthread_mutex_lock(&s->rl); + s->current = next_ev; + return next_ev; + } + + /* Wait for next event or interrupt. Unlock calendar. */ + struct timespec ts; + ts.tv_sec = next_ev->tv.tv_sec; + ts.tv_nsec = next_ev->tv.tv_usec * 1000L; + pthread_cond_timedwait(&s->notify, &s->mx, &ts); + } else { + /* Block until an event is scheduled. Unlock calendar.*/ + pthread_cond_wait(&s->notify, &s->mx); + } + } + + /* Unlock calendar, this shouldn't happen. */ + pthread_mutex_unlock(&s->mx); + return 0; + +} + +int evsched_event_finished(evsched_t *s) +{ + if (!s) { + return -1; + } + + /* Mark as finished. */ + if (s->current) { + s->current = 0; + pthread_mutex_unlock(&s->rl); + return 0; + } + + /* Finished event is not current. */ + return -1; +} + +int evsched_schedule(evsched_t *s, event_t *ev, uint32_t dt) +{ + if (!s || !ev || dt < 0) { + return -1; + } + + /* Update event timer. */ + evsched_settimer(ev, dt); + + /* Lock calendar. */ + pthread_mutex_lock(&s->mx); + + /* Schedule event. */ + node *n = 0, *prev = 0; + if (!EMPTY_LIST(s->calendar)) { + WALK_LIST(n, s->calendar) { + event_t* cur = (event_t *)n; + if (timercmp(&cur->tv, &ev->tv, <)) { + prev = n; + } else { + break; + } + } + } + + /* Append to list. */ + ev->parent = s; + if (prev) { + insert_node(&ev->n, prev); + } else { + add_head(&s->calendar, &ev->n); + } + + + /* Unlock calendar. */ + pthread_cond_signal(&s->notify); + pthread_mutex_unlock(&s->mx); + + return 0; +} + +event_t* evsched_schedule_cb(evsched_t *s, event_cb_t cb, void *data, uint32_t dt) +{ + if (!s) { + return 0; + } + + /* Create event. */ + event_t *e = evsched_event_new(s, EVSCHED_CB); + if (!e) { + return 0; + } + e->cb = cb; + e->data = data; + + /* Schedule. */ + if (evsched_schedule(s, e, dt) != 0) { + evsched_event_free(s, e); + e = 0; + } + + return e; +} + +event_t* evsched_schedule_term(evsched_t *s, uint32_t dt) +{ + if (!s) { + return 0; + } + + /* Create event. */ + event_t *e = evsched_event_new(s, EVSCHED_TERM); + if (!e) { + return 0; + } + + /* Schedule. */ + if (evsched_schedule(s, e, dt) != 0) { + evsched_event_free(s, e); + e = 0; + } + + return e; +} + +int evsched_cancel(evsched_t *s, event_t *ev) +{ + if (!s || !ev) { + return -1; + } + + /* Lock calendar. */ + pthread_mutex_lock(&s->mx); + + /* Make sure not running. */ + pthread_mutex_lock(&s->rl); + + /* Find in list. */ + event_t *n = 0; + int found = 0; + WALK_LIST(n, s->calendar) { + if (n == ev) { + found = 1; + break; + } + } + + /* Remove from list. */ + if (found) { + rem_node(&ev->n); + } + + /* Enable running events. */ + pthread_mutex_unlock(&s->rl); + + /* Unlock calendar. */ + pthread_cond_signal(&s->notify); + pthread_mutex_unlock(&s->mx); + + return 0; +} + diff --git a/src/common/evsched.h b/src/common/evsched.h new file mode 100644 index 0000000..2a682e1 --- /dev/null +++ b/src/common/evsched.h @@ -0,0 +1,240 @@ +/* Copyright (C) 2011 CZ.NIC, z.s.p.o. <knot-dns@labs.nic.cz> + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. + */ +/*! + * \file evsched.h + * + * \author Marek Vavrusa <marek.vavrusa@nic.cz> + * + * \brief Event scheduler. + * + * Scheduler works with the same event_t type as event queue. + * It is also thread-safe so the scheduler can run in a separate thread + * while events can be enqueued from different threads. + * + * Guideline is, that the scheduler run loop should exit with + * a special event type EVSCHED_TERM. + * + * Example usage: + * \code + * evsched_t *s = evsched_new(); + * + * // Schedule myfunc() after 1000ms + * evsched_schedule_cb(s, myfunc, data, 1000) + * + * // Schedule termination event after 1500ms + * evsched_schedule_term(s, 1500); + * + * // Event scheduler main loop + * while (1) { + * // Wait for next scheduled event + * event_t *ev = evsched_next(); + * + * // Break on termination event + * if (ev->type == EVSCHED_TERM) { + * evsched_event_free(s, ev); + * break; + * } + * + * // Execute and discard event + * if (ev->cb) { + * ev->cb(ev); + * } + * evsched_event_free(s, ev); // Free executed event + * } + * + * // Delete event scheduler + * evsched_delete(s); + * \endcode + * + * \addtogroup common_lib + * @{ + */ + +#ifndef _KNOTD_COMMON_EVSCHED_H_ +#define _KNOTD_COMMON_EVSCHED_H_ + +#include <pthread.h> +#include "common/slab/slab.h" +#include "common/lists.h" +#include "common/evqueue.h" + +/*! + * \brief Scheduler event types. + */ +typedef enum evsched_ev_t { + EVSCHED_NOOP = 0, /*!< No-op action, skip. */ + EVSCHED_CB, /*!< Callback action. */ + EVSCHED_TERM /*!< Terminal action, stop event scheduler. */ +} evsched_ev_t; + +/*! + * \brief Event scheduler structure. + * + * Keeps list of scheduled events. Events are executed in their scheduled + * time and kept in an ordered list (queue). + * Scheduler is terminated with a special EVSCHED_TERM event type. + */ +typedef struct { + pthread_mutex_t rl; /*!< Event running lock. */ + event_t *current; /*!< Current running event. */ + pthread_mutex_t mx; /*!< Event queue locking. */ + pthread_cond_t notify; /*!< Event queue notification. */ + list calendar; /*!< Event calendar. */ + struct { + slab_cache_t alloc; /*!< Events SLAB cache. */ + pthread_mutex_t lock; /*!< Events cache spin lock. */ + } cache; +} evsched_t; + +/*! + * \brief Create new event scheduler instance. + * + * \retval New instance on success. + * \retval NULL on error. + */ +evsched_t *evsched_new(); + +/*! + * \brief Deinitialize and free event scheduler instance. + * + * \param s Pointer to event scheduler instance. + * \note *sched is set to 0. + */ +void evsched_delete(evsched_t **s); + +/*! + * \brief Create an empty event. + * + * \param s Pointer to event scheduler instance. + * \param type Event type. + * \retval New instance on success. + * \retval NULL on error. + */ +event_t *evsched_event_new(evsched_t *s, int type); + +/*! + * \brief Dispose event instance. + * + * \param s Pointer to event scheduler instance. + * \param ev Event instance. + */ +void evsched_event_free(evsched_t *s, event_t *ev); + +/*! + * \brief Fetch next-event. + * + * Scheduler may block until a next event is available. + * Send scheduler an EVSCHED_NOOP or EVSCHED_TERM event to unblock it. + * + * \warning Returned event must be marked as finished, or deadlock occurs. + * + * \param s Event scheduler. + * + * \retval Scheduled event. + * \retval NULL on error. + */ +event_t* evsched_next(evsched_t *s); + +/*! + * \brief Mark running event as finished. + * + * Need to call this after each event returned by evsched_next() is finished. + * + * \param s Event scheduler. + * + * \retval 0 if successful. + * \retval -1 on errors. + */ +int evsched_event_finished(evsched_t *s); + +/*! + * \brief Schedule an event. + * + * \param s Event scheduler. + * \param ev Prepared event. + * \param dt Time difference in milliseconds from now (dt is relative). + * + * \retval 0 on success. + * \retval <0 on error. + */ +int evsched_schedule(evsched_t *s, event_t *ev, uint32_t dt); + +/*! + * \brief Schedule callback event. + * + * Execute callback after dt miliseconds has passed. + * + * \param s Event scheduler. + * \param cb Callback handler. + * \param data Data for callback. + * \param dt Time difference in milliseconds from now (dt is relative). + * + * \retval Event instance on success. + * \retval NULL on error. + */ +event_t* evsched_schedule_cb(evsched_t *s, event_cb_t cb, void *data, uint32_t dt); + +/*! + * \brief Schedule termination event. + * + * Special action for scheduler termination. + * + * \param s Event scheduler. + * \param dt Time difference in milliseconds from now (dt is relative). + * + * \retval Event instance on success. + * \retval NULL on error. + */ +event_t* evsched_schedule_term(evsched_t *s, uint32_t dt); + +/*! + * \brief Cancel a scheduled event. + * + * \warning May block until current running event is finished (as it cannot + * interrupt running event). + * + * \warning Never cancel event in it's callback. As it never finishes, + * it deadlocks. + * + * \param s Event scheduler. + * \param ev Scheduled event. + * + * \retval 0 on success. + * \retval <0 on error. + */ +int evsched_cancel(evsched_t *s, event_t *ev); + +/* Singleton event scheduler pointer. */ +extern evsched_t *s_evsched; + +/*! + * \brief Event scheduler singleton. + */ +static inline evsched_t *evsched() { + return s_evsched; +} + +/*! + * \brief Set event scheduler singleton. + */ +static inline void evsched_set(evsched_t *s) { + s_evsched = s; +} + + +#endif /* _KNOTD_COMMON_EVSCHED_H_ */ + +/*! @} */ diff --git a/src/common/fdset.c b/src/common/fdset.c new file mode 100644 index 0000000..8c070ad --- /dev/null +++ b/src/common/fdset.c @@ -0,0 +1,80 @@ +/* Copyright (C) 2011 CZ.NIC, z.s.p.o. <knot-dns@labs.nic.cz> + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. + */ + +#ifndef _GNU_SOURCE +#define _GNU_SOURCE /* Required for RTLD_DEFAULT. */ +#endif + +#include <dlfcn.h> +#include <string.h> +#include <stdio.h> +#include "common/fdset.h" +#include <config.h> + +struct fdset_backend_t _fdset_backend = { +}; + +/*! \brief Set backend implementation. */ +static void fdset_set_backend(struct fdset_backend_t *backend) { + memcpy(&_fdset_backend, backend, sizeof(struct fdset_backend_t)); +} + +/* Linux epoll API. */ +#ifdef HAVE_EPOLL_WAIT + #include "common/fdset_epoll.h" +#endif /* HAVE_EPOLL_WAIT */ + +/* BSD kqueue API */ +#ifdef HAVE_KQUEUE + #include "common/fdset_kqueue.h" +#endif /* HAVE_KQUEUE */ + +/* POSIX poll API */ +#ifdef HAVE_POLL + #include "common/fdset_poll.h" +#endif /* HAVE_POLL */ + +/*! \brief Bootstrap polling subsystem (it is called automatically). */ +void __attribute__ ((constructor)) fdset_init() +{ + /* Preference: epoll */ +#ifdef HAVE_EPOLL_WAIT + if (dlsym(RTLD_DEFAULT, "epoll_wait") != 0) { + fdset_set_backend(&FDSET_EPOLL); + return; + } +#endif + + /* Preference: kqueue */ +#ifdef HAVE_KQUEUE + if (dlsym(RTLD_DEFAULT, "kqueue") != 0) { + fdset_set_backend(&FDSET_KQUEUE); + return; + } +#endif + + /* Fallback: poll */ +#ifdef HAVE_POLL + if (dlsym(RTLD_DEFAULT, "poll") != 0) { + fdset_set_backend(&FDSET_POLL); + return; + } +#endif + + /* This shouldn't happen. */ + fprintf(stderr, "fdset: fatal error - no valid fdset backend found\n"); + return; +} diff --git a/src/common/fdset.h b/src/common/fdset.h new file mode 100644 index 0000000..10196bf --- /dev/null +++ b/src/common/fdset.h @@ -0,0 +1,196 @@ +/* Copyright (C) 2011 CZ.NIC, z.s.p.o. <knot-dns@labs.nic.cz> + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. + */ +/*! + * \file fdset.h + * + * \author Marek Vavrusa <marek.vavrusa@nic.cz> + * + * \brief Wrapper for native I/O multiplexing. + * + * Selects best implementation according to config. + * - select() + * - poll() \todo + * - epoll() + * - kqueue() + * + * \addtogroup common_lib + * @{ + */ + +#ifndef _KNOTD_FDSET_H_ +#define _KNOTD_FDSET_H_ + +#include <stddef.h> + +/*! \brief Opaque pointer to implementation-specific fdset data. */ +typedef struct fdset_t fdset_t; + +/*! \brief Unified event types. */ +enum fdset_event_t { + OS_EV_READ = 1 << 0, /*!< Readable event. */ + OS_EV_WRITE = 1 << 1, /*!< Writeable event. */ + OS_EV_ERROR = 1 << 2 /*!< Error event. */ +}; + +/*! \brief File descriptor set iterator. */ +typedef struct fdset_it_t { + int fd; /*!< Current file descriptor. */ + int events; /*!< Returned events. */ + size_t pos; /* Internal usage. */ +} fdset_it_t; + +/*! + * \brief File descriptor set implementation backend. + * \notice Functions documentation following. + * \internal + */ +struct fdset_backend_t +{ + fdset_t* (*fdset_new)(); + int (*fdset_destroy)(fdset_t*); + int (*fdset_add)(fdset_t*, int, int); + int (*fdset_remove)(fdset_t*, int); + int (*fdset_wait)(fdset_t*); + int (*fdset_begin)(fdset_t*, fdset_it_t*); + int (*fdset_end)(fdset_t*, fdset_it_t*); + int (*fdset_next)(fdset_t*, fdset_it_t*); + const char* (*fdset_method)(); +}; + +/*! + * \brief Selected backend. + * \internal + */ +extern struct fdset_backend_t _fdset_backend; + +/*! + * \brief Create new fdset. + * + * FDSET implementation depends on system. + * + * \retval Pointer to initialized FDSET structure if successful. + * \retval NULL on error. + */ +static inline fdset_t *fdset_new() { + return _fdset_backend.fdset_new(); +} + +/*! + * \brief Destroy FDSET. + * + * \retval 0 if successful. + * \retval -1 on error. + */ +static inline int fdset_destroy(fdset_t * fdset) { + return _fdset_backend.fdset_destroy(fdset); +} + +/*! + * \brief Add file descriptor to watched set. + * + * \param fdset Target set. + * \param fd Added file descriptor. + * \param events Mask of watched events. + * + * \retval 0 if successful. + * \retval -1 on errors. + */ +static inline int fdset_add(fdset_t *fdset, int fd, int events) { + return _fdset_backend.fdset_add(fdset, fd, events); +} + + +/*! + * \brief Remove file descriptor from watched set. + * + * \param fdset Target set. + * \param fd File descriptor to be removed. + * + * \retval 0 if successful. + * \retval -1 on errors. + */ +static inline int fdset_remove(fdset_t *fdset, int fd) { + return _fdset_backend.fdset_remove(fdset, fd); +} + +/*! + * \brief Poll set for new events. + * + * \param fdset Target set. + * + * \retval Number of events if successful. + * \retval -1 on errors. + * + * \todo Timeout. + */ +static inline int fdset_wait(fdset_t *fdset) { + return _fdset_backend.fdset_wait(fdset); +} + +/*! + * \brief Set event iterator to the beginning of last polled events. + * + * \param fdset Target set. + * \param it Event iterator. + * + * \retval 0 if successful. + * \retval -1 on errors. + */ +static inline int fdset_begin(fdset_t *fdset, fdset_it_t *it) { + return _fdset_backend.fdset_begin(fdset, it); +} + +/*! + * \brief Set event iterator to the end of last polled events. + * + * \param fdset Target set. + * \param it Event iterator. + * + * \retval 0 if successful. + * \retval -1 on errors. + */ +static inline int fdset_end(fdset_t *fdset, fdset_it_t *it) { + return _fdset_backend.fdset_end(fdset, it); +} + +/*! + * \brief Set event iterator to the next event. + * + * Event iterator fd will be set to -1 if next event doesn't exist. + * + * \param fdset Target set. + * \param it Event iterator. + * + * \retval 0 if successful. + * \retval -1 on errors. + */ +static inline int fdset_next(fdset_t *fdset, fdset_it_t *it) { + return _fdset_backend.fdset_next(fdset, it); +} + +/*! + * \brief Returned name of underlying poll method. + * + * \retval Name if successful. + * \retval NULL if no method was loaded (shouldn't happen). + */ +static inline const char* fdset_method() { + return _fdset_backend.fdset_method(); +} + +#endif /* _KNOTD_FDSET_H_ */ + +/*! @} */ diff --git a/src/common/fdset_epoll.c b/src/common/fdset_epoll.c new file mode 100644 index 0000000..cb2e3e1 --- /dev/null +++ b/src/common/fdset_epoll.c @@ -0,0 +1,216 @@ +/* Copyright (C) 2011 CZ.NIC, z.s.p.o. <knot-dns@labs.nic.cz> + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. + */ + +#include <config.h> + +#ifdef HAVE_EPOLL_WAIT + +#include <sys/epoll.h> +#include <string.h> +#include <stdlib.h> +#include <unistd.h> + +#include "fdset_epoll.h" + +#define OS_FDS_CHUNKSIZE 8 /*!< Number of pollfd structs in a chunk. */ +#define OS_FDS_KEEPCHUNKS 32 /*!< Will attempt to free memory when reached. */ + +struct fdset_t { + int epfd; + struct epoll_event *events; + size_t nfds; + size_t reserved; + size_t polled; +}; + +fdset_t *fdset_epoll_new() +{ + fdset_t *set = malloc(sizeof(fdset_t)); + if (!set) { + return 0; + } + + /* Blank memory. */ + memset(set, 0, sizeof(fdset_t)); + + /* Create epoll fd. */ + set->epfd = epoll_create(OS_FDS_CHUNKSIZE); + + return set; +} + +int fdset_epoll_destroy(fdset_t * fdset) +{ + if(!fdset) { + return -1; + } + + /* Teardown epoll. */ + close(fdset->epfd); + + /* OK if NULL. */ + free(fdset->events); + free(fdset); + return 0; +} + +int fdset_epoll_add(fdset_t *fdset, int fd, int events) +{ + if (!fdset || fd < 0 || events <= 0) { + return -1; + } + + /* Realloc needed. */ + if (fdset->nfds == fdset->reserved) { + const size_t chunk = OS_FDS_CHUNKSIZE; + const size_t nsize = (fdset->reserved + chunk) * + sizeof(struct epoll_event); + struct epoll_event *events_n = malloc(nsize); + if (!events_n) { + return -1; + } + + /* Clear and copy old fdset data. */ + memset(events_n, 0, nsize); + memcpy(events_n, fdset->events, + fdset->nfds * sizeof(struct epoll_event)); + free(fdset->events); + fdset->events = events_n; + fdset->reserved += chunk; + } + + /* Add to epoll set. */ + struct epoll_event ev; + memset(&ev, 0, sizeof(struct epoll_event)); + ev.events = EPOLLIN; /*! \todo MAP events. */ + ev.data.fd = fd; + if (epoll_ctl(fdset->epfd, EPOLL_CTL_ADD, fd, &ev) < 0) { + return -1; + } + + ++fdset->nfds; + return 0; +} + +int fdset_epoll_remove(fdset_t *fdset, int fd) +{ + if (!fdset || fd < 0) { + return -1; + } + + /* Attempt to remove from set. */ + struct epoll_event ev; + memset(&ev, 0, sizeof(struct epoll_event)); + if (epoll_ctl(fdset->epfd, EPOLL_CTL_DEL, fd, &ev) < 0) { + return -1; + } + + /* Overwrite current item. */ + --fdset->nfds; + + /*! \todo Return memory if overallocated (nfds is far lower than reserved). */ + return 0; +} + +int fdset_epoll_wait(fdset_t *fdset) +{ + if (!fdset || fdset->nfds < 1 || !fdset->events) { + return -1; + } + + /* Poll new events. */ + fdset->polled = 0; + int nfds = epoll_wait(fdset->epfd, fdset->events, fdset->nfds, -1); + + /* Check. */ + if (nfds < 0) { + return -1; + } + + /* Events array is ordered from 0 to nfds. */ + fdset->polled = nfds; + return nfds; +} + +int fdset_epoll_begin(fdset_t *fdset, fdset_it_t *it) +{ + if (!fdset || !it) { + return -1; + } + + /* Find first. */ + it->pos = 0; + return fdset_next(fdset, it); +} + +int fdset_epoll_end(fdset_t *fdset, fdset_it_t *it) +{ + if (!fdset || !it || fdset->nfds < 1) { + return -1; + } + + /* Check for polled events. */ + if (fdset->polled < 1) { + it->fd = -1; + it->pos = 0; + return -1; + } + + /* No end found, ends on the beginning. */ + size_t nid = fdset->polled - 1; + it->fd = fdset->events[nid].data.fd; + it->pos = nid; + it->events = 0; /*! \todo Map events. */ + return -1; +} + +int fdset_epoll_next(fdset_t *fdset, fdset_it_t *it) +{ + if (!fdset || !it || fdset->nfds < 1) { + return -1; + } + + /* Check boundaries. */ + if (it->pos >= fdset->polled) { + return -1; + } + + /* Select next. */ + size_t nid = it->pos++; + it->fd = fdset->events[nid].data.fd; + it->events = 0; /*! \todo Map events. */ + return 0; +} + +const char* fdset_epoll_method() +{ + return "epoll"; +} + +/* Package APIs. */ +struct fdset_backend_t FDSET_EPOLL = { + .fdset_new = fdset_epoll_new, + .fdset_destroy = fdset_epoll_destroy, + .fdset_add = fdset_epoll_add, + .fdset_remove = fdset_epoll_remove, + .fdset_wait = fdset_epoll_wait, + .fdset_begin = fdset_epoll_begin, + .fdset_end = fdset_epoll_end, + .fdset_next = fdset_epoll_next, + .fdset_method = fdset_epoll_method +}; + +#endif diff --git a/src/common/fdset_epoll.h b/src/common/fdset_epoll.h new file mode 100644 index 0000000..551394d --- /dev/null +++ b/src/common/fdset_epoll.h @@ -0,0 +1,133 @@ +/* Copyright (C) 2011 CZ.NIC, z.s.p.o. <knot-dns@labs.nic.cz> + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. + */ +/*! + * \file fdset_epoll.h + * + * \author Marek Vavrusa <marek.vavrusa@nic.cz> + * + * \brief Wrapper for epoll I/O multiplexing. + * + * \addtogroup common_lib + * @{ + */ + +#ifndef _KNOTD_FDSET_EPOLL_H_ +#define _KNOTD_FDSET_EPOLL_H_ + +#include "fdset.h" + +/*! + * \brief Create new fdset. + * + * Linux epoll() backend. + * + * \retval Pointer to initialized FDSET structure if successful. + * \retval NULL on error. + */ +fdset_t *fdset_epoll_new(); + +/*! + * \brief Destroy FDSET. + * + * \retval 0 if successful. + * \retval -1 on error. + */ +int fdset_epoll_destroy(fdset_t * fdset); + +/*! + * \brief Add file descriptor to watched set. + * + * \param fdset Target set. + * \param fd Added file descriptor. + * \param events Mask of watched events. + * + * \retval 0 if successful. + * \retval -1 on errors. + */ +int fdset_epoll_add(fdset_t *fdset, int fd, int events); + +/*! + * \brief Remove file descriptor from watched set. + * + * \param fdset Target set. + * \param fd File descriptor to be removed. + * + * \retval 0 if successful. + * \retval -1 on errors. + */ +int fdset_epoll_remove(fdset_t *fdset, int fd); + +/*! + * \brief Poll set for new events. + * + * \param fdset Target set. + * + * \retval Number of events if successful. + * \retval -1 on errors. + * + * \todo Timeout. + */ +int fdset_epoll_wait(fdset_t *fdset); + +/*! + * \brief Set event iterator to the beginning of last polled events. + * + * \param fdset Target set. + * \param it Event iterator. + * + * \retval 0 if successful. + * \retval -1 on errors. + */ +int fdset_epoll_begin(fdset_t *fdset, fdset_it_t *it); + +/*! + * \brief Set event iterator to the end of last polled events. + * + * \param fdset Target set. + * \param it Event iterator. + * + * \retval 0 if successful. + * \retval -1 on errors. + */ +int fdset_epoll_end(fdset_t *fdset, fdset_it_t *it); + +/*! + * \brief Set event iterator to the next event. + * + * Event iterator fd will be set to -1 if next event doesn't exist. + * + * \param fdset Target set. + * \param it Event iterator. + * + * \retval 0 if successful. + * \retval -1 on errors. + */ +int fdset_epoll_next(fdset_t *fdset, fdset_it_t *it); + +/*! + * \brief Returned name of epoll method. + * + * \retval Name if successful. + * \retval NULL if no method was loaded (shouldn't happen). + */ +const char* fdset_epoll_method(); + +/*! \brief Exported API. */ +extern struct fdset_backend_t FDSET_EPOLL; + +#endif /* _KNOTD_FDSET_EPOLL_H_ */ + +/*! @} */ diff --git a/src/common/fdset_kqueue.c b/src/common/fdset_kqueue.c new file mode 100644 index 0000000..c7199ae --- /dev/null +++ b/src/common/fdset_kqueue.c @@ -0,0 +1,251 @@ +/* Copyright (C) 2011 CZ.NIC, z.s.p.o. <knot-dns@labs.nic.cz> + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. + */ + +#include <config.h> + +#ifdef HAVE_KQUEUE + +#include <stdint.h> +#include <string.h> +#include <stdlib.h> +#include <unistd.h> +#include <sys/event.h> +#include <sys/time.h> + +#include "fdset_kqueue.h" + +#define OS_FDS_CHUNKSIZE 8 /*!< Number of pollfd structs in a chunk. */ +#define OS_FDS_KEEPCHUNKS 32 /*!< Will attempt to free memory when reached. */ + +struct fdset_t { + int kq; + struct kevent *events; + struct kevent *revents; + size_t nfds; + size_t reserved; + size_t polled; +}; + +fdset_t *fdset_kqueue_new() +{ + fdset_t *set = malloc(sizeof(fdset_t)); + if (!set) { + return 0; + } + + /* Blank memory. */ + memset(set, 0, sizeof(fdset_t)); + + /* Create kqueue fd. */ + set->kq = kqueue(); + if (set->kq < 0) { + free(set); + set = 0; + } + + return set; +} + +int fdset_kqueue_destroy(fdset_t * fdset) +{ + if(!fdset) { + return -1; + } + + /* Teardown kqueue. */ + close(fdset->kq); + + /* OK if NULL. */ + free(fdset->revents); + free(fdset->events); + free(fdset); + return 0; +} + +int fdset_kqueue_realloc(void **old, size_t oldsize, size_t nsize) +{ + void *nmem = malloc(nsize); + if (!nmem) { + return -1; + } + + /* Clear and copy old fdset data. */ + memset(nmem, 0, nsize); + if (oldsize > 0) { + memcpy(nmem, *old, oldsize); + free(*old); + } + + *old = nmem; + return 0; +} + +int fdset_kqueue_add(fdset_t *fdset, int fd, int events) +{ + if (!fdset || fd < 0 || events <= 0) { + return -1; + } + + /* Realloc needed. */ + if (fdset->nfds == fdset->reserved) { + const size_t chunk = OS_FDS_CHUNKSIZE; + const size_t nsize = (fdset->reserved + chunk) * + sizeof(struct kevent); + const size_t oldsize = fdset->nfds * sizeof(struct kevent); + + if (fdset_kqueue_realloc(&fdset->events, oldsize, nsize) < 0) { + return -1; + } + + if (fdset_kqueue_realloc(&fdset->revents, oldsize, nsize) < 0) { + return -1; + } + + } + + /* Add to kqueue set. */ + int evfilt = EVFILT_READ; /*! \todo Map events. */ + EV_SET(&fdset->events[fdset->nfds], fd, evfilt, + EV_ADD|EV_ENABLE, 0, 0, 0); + + ++fdset->nfds; + return 0; +} + +int fdset_kqueue_remove(fdset_t *fdset, int fd) +{ + if (!fdset || fd < 0) { + return -1; + } + + /* Find in set. */ + int pos = -1; + for (int i = 0; i < fdset->nfds; ++i) { + if (fdset->events[i].ident == fd) { + pos = i; + break; + } + } + + if (pos < 0) { + return -1; + } + + /* Remove filters. */ + EV_SET(&fdset->events[pos], fd, EVFILT_READ, + EV_DISABLE|EV_DELETE, 0, 0, 0); + + /* Attempt to remove from set. */ + size_t remaining = ((fdset->nfds - pos) - 1) * sizeof(struct kevent); + memmove(fdset->events + pos, fdset->events + (pos + 1), remaining); + + /* Overwrite current item. */ + --fdset->nfds; + + /*! \todo Return memory if overallocated (nfds is far lower than reserved). */ + return 0; +} + +int fdset_kqueue_wait(fdset_t *fdset) +{ + if (!fdset || fdset->nfds < 1 || !fdset->events) { + return -1; + } + + /* Poll new events. */ + fdset->polled = 0; + int nfds = kevent(fdset->kq, fdset->events, fdset->nfds, + fdset->revents, fdset->nfds, 0); + + /* Check. */ + if (nfds < 0) { + return -1; + } + + /* Events array is ordered from 0 to nfds. */ + fdset->polled = nfds; + return nfds; +} + +int fdset_kqueue_begin(fdset_t *fdset, fdset_it_t *it) +{ + if (!fdset || !it) { + return -1; + } + + /* Find first. */ + it->pos = 0; + return fdset_next(fdset, it); +} + +int fdset_kqueue_end(fdset_t *fdset, fdset_it_t *it) +{ + if (!fdset || !it || fdset->nfds < 1) { + return -1; + } + + /* Check for polled events. */ + if (fdset->polled < 1) { + it->fd = -1; + it->pos = 0; + return -1; + } + + /* No end found, ends on the beginning. */ + size_t nid = fdset->polled - 1; + it->fd = fdset->revents[nid].ident; + it->pos = nid; + it->events = 0; /*! \todo Map events. */ + return -1; +} + +int fdset_kqueue_next(fdset_t *fdset, fdset_it_t *it) +{ + if (!fdset || !it || fdset->nfds < 1) { + return -1; + } + + /* Check boundaries. */ + if (it->pos >= fdset->polled) { + return -1; + } + + /* Select next. */ + size_t nid = it->pos++; + it->fd = fdset->revents[nid].ident; + it->events = 0; /*! \todo Map events. */ + return 0; +} + +const char* fdset_kqueue_method() +{ + return "kqueue"; +} + +/* Package APIs. */ +struct fdset_backend_t FDSET_KQUEUE = { + .fdset_new = fdset_kqueue_new, + .fdset_destroy = fdset_kqueue_destroy, + .fdset_add = fdset_kqueue_add, + .fdset_remove = fdset_kqueue_remove, + .fdset_wait = fdset_kqueue_wait, + .fdset_begin = fdset_kqueue_begin, + .fdset_end = fdset_kqueue_end, + .fdset_next = fdset_kqueue_next, + .fdset_method = fdset_kqueue_method +}; + +#endif diff --git a/src/common/fdset_kqueue.h b/src/common/fdset_kqueue.h new file mode 100644 index 0000000..f64482f --- /dev/null +++ b/src/common/fdset_kqueue.h @@ -0,0 +1,133 @@ +/* Copyright (C) 2011 CZ.NIC, z.s.p.o. <knot-dns@labs.nic.cz> + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. + */ +/*! + * \file fdset_kqueue.h + * + * \author Marek Vavrusa <marek.vavrusa@nic.cz> + * + * \brief Wrapper for kqueue I/O multiplexing. + * + * \addtogroup common_lib + * @{ + */ + +#ifndef _KNOTD_FDSET_KQUEUE_H_ +#define _KNOTD_FDSET_KQUEUE_H_ + +#include "fdset.h" + +/*! + * \brief Create new fdset. + * + * BSD kqueue() backend. + * + * \retval Pointer to initialized FDSET structure if successful. + * \retval NULL on error. + */ +fdset_t *fdset_kqueue_new(); + +/*! + * \brief Destroy FDSET. + * + * \retval 0 if successful. + * \retval -1 on error. + */ +int fdset_kqueue_destroy(fdset_t * fdset); + +/*! + * \brief Add file descriptor to watched set. + * + * \param fdset Target set. + * \param fd Added file descriptor. + * \param events Mask of watched events. + * + * \retval 0 if successful. + * \retval -1 on errors. + */ +int fdset_kqueue_add(fdset_t *fdset, int fd, int events); + +/*! + * \brief Remove file descriptor from watched set. + * + * \param fdset Target set. + * \param fd File descriptor to be removed. + * + * \retval 0 if successful. + * \retval -1 on errors. + */ +int fdset_kqueue_remove(fdset_t *fdset, int fd); + +/*! + * \brief Poll set for new events. + * + * \param fdset Target set. + * + * \retval Number of events if successful. + * \retval -1 on errors. + * + * \todo Timeout. + */ +int fdset_kqueue_wait(fdset_t *fdset); + +/*! + * \brief Set event iterator to the beginning of last polled events. + * + * \param fdset Target set. + * \param it Event iterator. + * + * \retval 0 if successful. + * \retval -1 on errors. + */ +int fdset_kqueue_begin(fdset_t *fdset, fdset_it_t *it); + +/*! + * \brief Set event iterator to the end of last polled events. + * + * \param fdset Target set. + * \param it Event iterator. + * + * \retval 0 if successful. + * \retval -1 on errors. + */ +int fdset_kqueue_end(fdset_t *fdset, fdset_it_t *it); + +/*! + * \brief Set event iterator to the next event. + * + * Event iterator fd will be set to -1 if next event doesn't exist. + * + * \param fdset Target set. + * \param it Event iterator. + * + * \retval 0 if successful. + * \retval -1 on errors. + */ +int fdset_kqueue_next(fdset_t *fdset, fdset_it_t *it); + +/*! + * \brief Returned name of kqueue method. + * + * \retval Name if successful. + * \retval NULL if no method was loaded (shouldn't happen). + */ +const char* fdset_kqueue_method(); + +/*! \brief Exported API. */ +extern struct fdset_backend_t FDSET_KQUEUE; + +#endif /* _KNOTD_FDSET_KQUEUE_H_ */ + +/*! @} */ diff --git a/src/common/fdset_poll.c b/src/common/fdset_poll.c new file mode 100644 index 0000000..8682eaf --- /dev/null +++ b/src/common/fdset_poll.c @@ -0,0 +1,230 @@ +/* Copyright (C) 2011 CZ.NIC, z.s.p.o. <knot-dns@labs.nic.cz> + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. + */ + +#include <config.h> + +#ifdef HAVE_POLL + +#include <stdlib.h> +#include <string.h> +#include <sys/poll.h> +#include <stddef.h> + +#include "common/fdset_poll.h" + +#define OS_FDS_CHUNKSIZE 8 /*!< Number of pollfd structs in a chunk. */ +#define OS_FDS_KEEPCHUNKS 32 /*!< Will attempt to free memory when reached. */ + +struct fdset_t { + struct pollfd *fds; + nfds_t nfds; + size_t reserved; + size_t polled; + size_t begin; +}; + +fdset_t *fdset_poll_new() +{ + fdset_t *set = malloc(sizeof(fdset_t)); + if (!set) { + return 0; + } + + /* Blank memory. */ + memset(set, 0, sizeof(fdset_t)); + return set; +} + +int fdset_poll_destroy(fdset_t * fdset) +{ + if(!fdset) { + return -1; + } + + /*! \todo No teardown required I guess. */ + + /* OK if NULL. */ + free(fdset->fds); + free(fdset); + return 0; +} + +int fdset_poll_add(fdset_t *fdset, int fd, int events) +{ + if (!fdset || fd < 0 || events <= 0) { + return -1; + } + + /* Realloc needed. */ + if (fdset->nfds == fdset->reserved) { + const size_t chunk = OS_FDS_CHUNKSIZE; + const size_t nsize = sizeof(struct pollfd) * (fdset->reserved + chunk); + struct pollfd *fds_n = malloc(nsize); + if (!fds_n) { + return -1; + } + + /* Clear and copy old fdset data. */ + memset(fds_n, 0, nsize); + memcpy(fds_n, fdset->fds, fdset->nfds * sizeof(struct pollfd)); + free(fdset->fds); + fdset->fds = fds_n; + fdset->reserved += chunk; + } + + /* Append. */ + int nid = fdset->nfds++; + fdset->fds[nid].fd = fd; + fdset->fds[nid].events = POLLIN; /*! \todo Map events to POLL events. */ + return 0; +} + +int fdset_poll_remove(fdset_t *fdset, int fd) +{ + if (!fdset || fd < 0) { + return -1; + } + + /* Find file descriptor. */ + unsigned found = 0; + size_t pos = 0; + for (size_t i = 0; i < fdset->nfds; ++i) { + if (fdset->fds[i].fd == fd) { + found = 1; + pos = i; + break; + } + } + + /* Check. */ + if (!found) { + return -1; + } + + /* Overwrite current item. */ + size_t remaining = ((fdset->nfds - pos) - 1) * sizeof(struct pollfd); + memmove(fdset->fds + pos, fdset->fds + (pos + 1), remaining); + --fdset->nfds; + + /*! \todo Return memory if overallocated (nfds is far lower than reserved). */ + /*! \todo Maybe >64 free chunks is excess? */ + return 0; +} + +int fdset_poll_wait(fdset_t *fdset) +{ + if (!fdset || fdset->nfds < 1 || !fdset->fds) { + return -1; + } + + /* Initialize pointers. */ + fdset->polled = 0; + fdset->begin = 0; + + /* Poll for events. */ + int ret = poll(fdset->fds, fdset->nfds, -1); + if (ret < 0) { + return -1; + } + + /* Set pointers for iterating. */ + fdset->polled = ret; + fdset->begin = 0; + return ret; +} + +int fdset_poll_begin(fdset_t *fdset, fdset_it_t *it) +{ + if (!fdset || !it) { + return -1; + } + + /* Find first. */ + it->pos = 0; + return fdset_next(fdset, it); +} + +int fdset_poll_end(fdset_t *fdset, fdset_it_t *it) +{ + if (!fdset || !it || fdset->nfds < 1) { + return -1; + } + + /* Check for polled events. */ + if (fdset->polled < 1) { + it->fd = -1; + it->pos = 0; + return -1; + } + + /* Trace last matching item from the end. */ + struct pollfd* pfd = fdset->fds + fdset->nfds - 1; + while (pfd != fdset->fds) { + if (pfd->events & pfd->revents) { + it->fd = pfd->fd; + it->pos = pfd - fdset->fds; + return 0; + } + } + + /* No end found, ends on the beginning. */ + it->fd = -1; + it->pos = 0; + return -1; +} + +int fdset_poll_next(fdset_t *fdset, fdset_it_t *it) +{ + if (!fdset || !it || fdset->nfds < 1) { + return -1; + } + + /* Find next with matching flags. */ + for (; it->pos < fdset->nfds; ++it->pos) { + struct pollfd* pfd = fdset->fds + it->pos; + if (pfd->events & pfd->revents) { + it->fd = pfd->fd; + it->events = pfd->revents; /*! \todo MAP events. */ + ++it->pos; /* Next will start after current. */ + return 0; + } + } + + /* No matching event found. */ + it->fd = -1; + it->pos = 0; + return -1; +} + +const char* fdset_poll_method() +{ + return "poll"; +} + +/* Package APIs. */ +struct fdset_backend_t FDSET_POLL = { + .fdset_new = fdset_poll_new, + .fdset_destroy = fdset_poll_destroy, + .fdset_add = fdset_poll_add, + .fdset_remove = fdset_poll_remove, + .fdset_wait = fdset_poll_wait, + .fdset_begin = fdset_poll_begin, + .fdset_end = fdset_poll_end, + .fdset_next = fdset_poll_next, + .fdset_method = fdset_poll_method +}; + +#endif diff --git a/src/common/fdset_poll.h b/src/common/fdset_poll.h new file mode 100644 index 0000000..d72b5bb --- /dev/null +++ b/src/common/fdset_poll.h @@ -0,0 +1,133 @@ +/* Copyright (C) 2011 CZ.NIC, z.s.p.o. <knot-dns@labs.nic.cz> + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. + */ +/*! + * \file fdset_poll.h + * + * \author Marek Vavrusa <marek.vavrusa@nic.cz> + * + * \brief Wrapper for poll I/O multiplexing. + * + * \addtogroup common_lib + * @{ + */ + +#ifndef _KNOTD_FDSET_POLL_H_ +#define _KNOTD_FDSET_POLL_H_ + +#include "fdset.h" + +/*! + * \brief Create new fdset. + * + * POSIX poll() backend. + * + * \retval Pointer to initialized FDSET structure if successful. + * \retval NULL on error. + */ +fdset_t *fdset_poll_new(); + +/*! + * \brief Destroy FDSET. + * + * \retval 0 if successful. + * \retval -1 on error. + */ +int fdset_poll_destroy(fdset_t * fdset); + +/*! + * \brief Add file descriptor to watched set. + * + * \param fdset Target set. + * \param fd Added file descriptor. + * \param events Mask of watched events. + * + * \retval 0 if successful. + * \retval -1 on errors. + */ +int fdset_poll_add(fdset_t *fdset, int fd, int events); + +/*! + * \brief Remove file descriptor from watched set. + * + * \param fdset Target set. + * \param fd File descriptor to be removed. + * + * \retval 0 if successful. + * \retval -1 on errors. + */ +int fdset_poll_remove(fdset_t *fdset, int fd); + +/*! + * \brief Poll set for new events. + * + * \param fdset Target set. + * + * \retval Number of events if successful. + * \retval -1 on errors. + * + * \todo Timeout. + */ +int fdset_poll_wait(fdset_t *fdset); + +/*! + * \brief Set event iterator to the beginning of last polled events. + * + * \param fdset Target set. + * \param it Event iterator. + * + * \retval 0 if successful. + * \retval -1 on errors. + */ +int fdset_poll_begin(fdset_t *fdset, fdset_it_t *it); + +/*! + * \brief Set event iterator to the end of last polled events. + * + * \param fdset Target set. + * \param it Event iterator. + * + * \retval 0 if successful. + * \retval -1 on errors. + */ +int fdset_poll_end(fdset_t *fdset, fdset_it_t *it); + +/*! + * \brief Set event iterator to the next event. + * + * Event iterator fd will be set to -1 if next event doesn't exist. + * + * \param fdset Target set. + * \param it Event iterator. + * + * \retval 0 if successful. + * \retval -1 on errors. + */ +int fdset_poll_next(fdset_t *fdset, fdset_it_t *it); + +/*! + * \brief Returned name of poll method. + * + * \retval Name if successful. + * \retval NULL if no method was loaded (shouldn't happen). + */ +const char* fdset_poll_method(); + +/*! \brief Exported API. */ +extern struct fdset_backend_t FDSET_POLL; + +#endif /* _KNOTD_FDSET_POLL_H_ */ + +/*! @} */ diff --git a/src/common/general-tree.c b/src/common/general-tree.c new file mode 100644 index 0000000..202b31a --- /dev/null +++ b/src/common/general-tree.c @@ -0,0 +1,215 @@ +/* Copyright (C) 2011 CZ.NIC, z.s.p.o. <knot-dns@labs.nic.cz> + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. + */ + +#include <stdlib.h> +#include <stdio.h> +#include <string.h> +#include <assert.h> +#include "common/general-tree.h" +#include "common/errors.h" + +MOD_TREE_DEFINE(general_tree_node, avl); + +static void gen_rem_func(struct general_tree_node *n1) +{ + free(n1); +} + +general_tree_t *gen_tree_new(int (*comp_func)(void *, void *)) +{ + general_tree_t *ret = malloc(sizeof(general_tree_t)); + if (ret == NULL) { + return NULL; + } + ret->tree = malloc(sizeof(general_avl_tree_t)); + if (ret->tree == NULL) { + free(ret); + return NULL; + } + MOD_TREE_INIT(ret->tree, comp_func); + return ret; +} + +int gen_tree_add(general_tree_t *tree, + void *node, int (*mrg_func)(void **n1, void **n2)) +{ + struct general_tree_node *tree_node = + malloc(sizeof(struct general_tree_node)); + if (tree_node == NULL) { + return -1; + } + memset(tree_node, 0, sizeof(struct general_tree_node)); + tree_node->data = node; + int merged = 0; + MOD_TREE_INSERT(tree->tree, general_tree_node, avl, + tree_node, mrg_func, &merged); + if (merged) { + free(tree_node); + } + return merged; +} + +void gen_tree_remove(general_tree_t *tree, + void *what) +{ + struct general_tree_node tree_node; + tree_node.data = what; + MOD_TREE_REMOVE(tree->tree, general_tree_node, avl, &tree_node, + gen_rem_func); +} + +void *gen_tree_find(general_tree_t *tree, + void *what) +{ + struct general_tree_node tree_node; + tree_node.data = what; + struct general_tree_node *found_node = + MOD_TREE_FIND(tree->tree, general_tree_node, avl, &tree_node); + if (found_node) { + return found_node->data; + } else { + return NULL; + } +} + +int gen_tree_find_less_or_equal(general_tree_t *tree, + void *what, + void **found) +{ + if (tree == NULL || tree->tree == NULL) { + return -1; + } + + /* Check if tree is empty. */ + if (tree->tree->th_root == NULL) { + *found = NULL; + return 0; + } + + struct general_tree_node *f = NULL, *prev = NULL; + struct general_tree_node tree_node; + tree_node.data = what; + int exact_match = + MOD_TREE_FIND_LESS_EQUAL(tree->tree, general_tree_node, avl, + &tree_node, &f, &prev); + if (exact_match < 0) { + *found = NULL; + exact_match = 0; + } else if (exact_match == 0) { + assert(prev != NULL); + *found = prev->data; + } else { + assert(f != NULL); + *found = f->data; + } +// *found = (exact_match > 0) ? f->data : prev->data; + return exact_match; +} + +void gen_tree_apply_inorder(general_tree_t *tree, + void (*app_func) + (void *node, void *data), void *data) +{ + MOD_TREE_FORWARD_APPLY(tree->tree, general_tree_node, avl, + app_func, data); +} + +void gen_tree_destroy(general_tree_t **tree, + void (*dest_func)(void *node, void *data), void *data) +{ +// gen_tree_apply_inorder(*tree, print_node, NULL); + MOD_TREE_DESTROY((*tree)->tree, general_tree_node, avl, dest_func, + gen_rem_func, data); + free((*tree)->tree); + free(*tree); + *tree = NULL; +} + +void gen_tree_clear(general_tree_t *tree) +{ + MOD_TREE_DESTROY(tree->tree, general_tree_node, avl, NULL, + gen_rem_func, NULL); +} + +//static void add_node_to_tree(void *n, void *data) +//{ +// general_tree_t *tree = (general_tree_t *)data; +// gen_tree_add(tree, n, NULL); +//} + +static int gen_tree_copy_node(const struct general_tree_node *from, + struct general_tree_node **to) +{ + if (from == NULL) { + return 0; + } + + *to = malloc(sizeof(struct general_tree_node)); + if (*to == NULL) { + return -1; + } + memset(*to, 0, sizeof(struct general_tree_node)); + + (*to)->data = from->data; + (*to)->avl.avl_height = from->avl.avl_height; + + int ret = gen_tree_copy_node(from->avl.avl_left, + &(*to)->avl.avl_left); + if (ret != 0) { + return ret; + } + + ret = gen_tree_copy_node(from->avl.avl_right, + &(*to)->avl.avl_right); + if (ret != 0) { + /*! \todo Partially cleaunp tree! */ + (*to)->avl.avl_left = NULL; + return ret; + } + + return 0; +} + +general_tree_t *gen_tree_shallow_copy(general_tree_t *tree) +{ + general_tree_t *new_tree = malloc(sizeof(general_tree_t)); + if (new_tree == NULL) { + return NULL; + } + new_tree->tree = malloc(sizeof(general_avl_tree_t)); + if (new_tree->tree == NULL) { + free(new_tree); + return NULL; + } + + MOD_TREE_INIT(new_tree->tree, tree->tree->th_cmp); + assert(new_tree->tree->th_cmp == tree->tree->th_cmp); + +// gen_tree_apply_inorder(tree, add_node_to_tree, new_tree); + + if (gen_tree_copy_node(tree->tree->th_root, + &new_tree->tree->th_root) != 0) { + return NULL; + } + + /* CLEANUP */ +// gen_tree_apply_inorder(tree, print_node, NULL); +// printf("--------------------------\n"); +// gen_tree_apply_inorder(new_tree, print_node, NULL); + + return new_tree; +} + diff --git a/src/common/general-tree.h b/src/common/general-tree.h new file mode 100644 index 0000000..552638a --- /dev/null +++ b/src/common/general-tree.h @@ -0,0 +1,73 @@ +/* Copyright (C) 2011 CZ.NIC, z.s.p.o. <knot-dns@labs.nic.cz> + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. + */ + +#ifndef _KNOTD_COMMON_GENERAL_TREE_H_ +#define _KNOTD_COMMON_GENERAL_TREE_H_ + +#include "common/modified_tree.h" + +typedef MOD_TREE_HEAD(tree, general_tree_node) general_avl_tree_t; + +/* Define tree with void * nodes */ +struct general_tree_node { + MOD_TREE_ENTRY(general_tree_node) avl; +// int (*cmp_func)(void *n1, +// void *n2); +// int (*mrg_func)(void **n1, +// void **n2); +// void (*app_func)(void *n, +// void *data); + void *data; +}; + +struct general_tree { +// int (*cmp_func)(void *n1, +// void *n2); +// int (*mrg_func)(void **n1, +// void **n2); + general_avl_tree_t *tree; +}; + +typedef struct general_tree general_tree_t; + +general_tree_t *gen_tree_new(int (*cmp_func)(void *p1, void *p2)); + +int gen_tree_add(general_tree_t *tree, + void *node, + int (*mrg_func)(void **n1, void **n2)); + +void *gen_tree_find(general_tree_t *tree, + void *what); + +void gen_tree_remove(general_tree_t *tree, + void *what); + +void gen_tree_apply_inorder(general_tree_t *tree, + void (*app_func)(void *node, void *data), + void *data); + +void gen_tree_destroy(general_tree_t **tree, + void (*dest_func)(void *node, void *data), void *data); + +void gen_tree_clear(general_tree_t *tree); + +int gen_tree_find_less_or_equal(general_tree_t *tree, + void *what, + void **found); + +general_tree_t *gen_tree_shallow_copy(general_tree_t *tree); + +#endif // _KNOTD_COMMON_GENERAL_TREE_H_ diff --git a/src/common/latency.c b/src/common/latency.c new file mode 100644 index 0000000..a563f58 --- /dev/null +++ b/src/common/latency.c @@ -0,0 +1,197 @@ +/* Copyright (C) 2011 CZ.NIC, z.s.p.o. <knot-dns@labs.nic.cz> + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. + */ + +#ifdef PROF_LATENCY + +#include <sys/resource.h> +#include <sys/socket.h> +#include <string.h> +#include <stdlib.h> +#include <stdio.h> +#include <unistd.h> +#include <pthread.h> + + +/*! \brief Profiler statistics. */ +typedef struct pstat_t { + double M; /*!< \brief Mean value. */ + unsigned long min, max; /*!< \brief Minimum, maximum. */ + unsigned long total; /*!< \brief Total profiled time. */ + unsigned long count; /*!< \brief Number of profiled calls. */ +} pstat_t; + +/*! \brief Function call profile. */ +typedef struct profile_t { + const char* call; + pstat_t stat; +} profile_t; + +/*! \brief Observed function call codes. */ +enum pcall_code_t { + PF_RECVFROM = 0, + PF_SENDTO, + PF_PTHREAD_MUTEX_LOCK, + PF_PTHREAD_MUTEX_UNLOCK, + PF_CALL_SIZE +} pcall_code_t; + +/*! \brief Table of observed function calls. */ +static profile_t table[] = { + { "recvfrom", {0} }, + { "sendto", {0} }, + { "pthread_mutex_lock", {0} }, + { "pthread_mutex_unlock", {0} }, + { "NULL", {0} } +}; + + +/*! \brief Add value to statistics. */ +static inline void add_stat(pstat_t *stat, unsigned long val) { + + if (val < stat->min) { + stat->min = val; + } + if (val > stat->max) { + stat->max = val; + } + + stat->total += val; + + double Mprev = stat->M, M = stat->M; + M += (val - M)/((double)stat->count + 1); + stat->M = M; + //S += (val - M)*(x[i] - Mprev); + + ++stat->count; +} + +/*! \brief Call profiler table initialization (automatically called on load). */ +void __attribute__ ((constructor)) profiler_init() +{ + for (int i = 0; i < PF_CALL_SIZE; ++i) { + pstat_t* stat = &table[i].stat; + stat->M = 0; + stat->max = 0; + stat->min = (unsigned long)~0; + stat->total = 0; + stat->count = 0; + } +} + +/*! \brief Call profiler table evaluation (automatically called on exit). */ +void __attribute__ ((destructor)) profiler_deinit() +{ + + /* Get resource usage. */ + struct rusage usage; + if (getrusage(RUSAGE_SELF, &usage) < 0) { + memset(&usage, 0, sizeof(struct rusage)); + } + + fprintf(stderr, "\nStatistics:"); + fprintf(stderr, "\n==================\n"); + + fprintf(stderr, "User time: %.03lf ms\nSystem time: %.03lf ms\n", + usage.ru_utime.tv_sec * (double) 1000.0 + + usage.ru_utime.tv_usec / (double)1000.0, + usage.ru_stime.tv_sec * (double) 1000.0 + + usage.ru_stime.tv_usec / (double)1000.0); + fprintf(stderr, "Voluntary context switches: %lu\nInvoluntary context switches: %lu\n", + usage.ru_nvcsw, + usage.ru_nivcsw); + fprintf(stderr, "==================\n"); + fprintf(stderr, "\n"); + + /* Callers statistics. */ + for (int i = 0; i < PF_CALL_SIZE; ++i) { + pstat_t* stat = &table[i].stat; + fprintf(stderr, "%s: M=%lf min=%lu,max=%lu (total=%lu, %lu times) (usec)\n", + table[i].call, stat->M, stat->min, stat->max, stat->total, + stat->count); + } + +} + +ssize_t pf_recvfrom(int socket, void *buf, size_t len, int flags, + struct sockaddr *from, socklen_t *fromlen, + const char* caller, const char* file, int line) +{ + unsigned long elapsed = 0; + int ret = 0; + perf_begin(); + ret = recvfrom(socket, buf, len, flags, from, fromlen); + perf_end(elapsed); + + /* Discard wakeup delays, count statistics otherwise. */ + if (elapsed < 200000) { + add_stat(&table[PF_RECVFROM].stat, elapsed); + } + return ret; +} + +ssize_t pf_sendto(int socket, const void *buf, size_t len, int flags, + const struct sockaddr *to, socklen_t tolen, + const char* caller, const char* file, int line) +{ + unsigned long elapsed = 0; + int ret = 0; + perf_begin(); + ret = sendto(socket, buf, len, flags, to, tolen); + perf_end(elapsed); + + /* Discard wakeup delays, count statistics otherwise. */ + if (elapsed < 200000) { + add_stat(&table[PF_SENDTO].stat, elapsed); + } + return ret; +} + +/* Pthreads */ +int pf_pthread_mutex_lock(pthread_mutex_t *mutex, + const char* caller, const char* file, int line) +{ + unsigned long elapsed = 0; + int ret = 0; + perf_begin(); + ret = pthread_mutex_lock(mutex); + perf_end(elapsed); + + /* Discard wakeup delays, count statistics otherwise. */ + if (elapsed < 200000) { + add_stat(&table[PF_PTHREAD_MUTEX_LOCK].stat, elapsed); + } + + return ret; +} + +int pf_pthread_mutex_unlock(pthread_mutex_t *mutex, + const char* caller, const char* file, int line) +{ + unsigned long elapsed = 0; + int ret = 0; + perf_begin(); + ret = pthread_mutex_unlock(mutex); + perf_end(elapsed); + + /* Discard wakeup delays, count statistics otherwise. */ + if (elapsed < 200000) { + add_stat(&table[PF_PTHREAD_MUTEX_UNLOCK].stat, elapsed); + } + + return ret; +} + +#endif // PROF_LATENCY diff --git a/src/common/latency.h b/src/common/latency.h new file mode 100644 index 0000000..d965c56 --- /dev/null +++ b/src/common/latency.h @@ -0,0 +1,115 @@ +/* Copyright (C) 2011 CZ.NIC, z.s.p.o. <knot-dns@labs.nic.cz> + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. + */ +/*! + * \file latency.h + * + * \author Marek Vavrusa <marek.vavrusa@nic.cz> + * + * \brief Utilities for latency profiling. + * + * Selected calls latency profiler is enabled with PROF_LATENCY define. + * You can roughly profile own code with perf_begin() and perf_end() macros. + * + * \addtogroup common_lib + * @{ + */ + +#ifndef _KNOTD_COMMON_LATENCY_H_ +#define _KNOTD_COMMON_LATENCY_H_ + +/* Optional. */ +#ifdef PROF_LATENCY + +/* Do not include from latency.c */ +#include <sys/time.h> +#include <sys/socket.h> +#include <pthread.h> + +/* Profiler tools */ + +/*! \brief Time profile begin macro. */ +#define perf_begin() \ +do { \ + struct timeval __begin; \ + gettimeofday(&__begin, 0) + +/*! \brief Time profile end macro + * \param d Will contain the number of microseconds passed from perf_begin(). + */ +#define perf_end(d) \ + struct timeval __end; \ + gettimeofday(&__end, 0); \ + unsigned long __us = (__end.tv_sec - __begin.tv_sec) * 1000L * 1000L; \ + __us += (__end.tv_usec - __begin.tv_usec); \ + (d) = __us; \ +} while(0) + +/* Prototypes. */ + +/*! \brief Profiled recvfrom(). */ +ssize_t pf_recvfrom(int socket, void *buf, size_t len, int flags, + struct sockaddr *from, socklen_t *fromlen, + const char* caller, const char* file, int line); + +/*! \brief Profiled sendto(). */ +ssize_t pf_sendto(int socket, const void *buf, size_t len, int flags, + const struct sockaddr *to, socklen_t tolen, + const char* caller, const char* file, int line); + +/*! \brief Profiled pthread_mutex_lock(). */ +int pf_pthread_mutex_lock(pthread_mutex_t *mutex, + const char* caller, const char* file, int line); + +/*! \brief Profiled pthread_mutex_unlock(). */ +int pf_pthread_mutex_unlock(pthread_mutex_t *mutex, + const char* caller, const char* file, int line); + +/* + * Sockets. + */ + +/*! \brief Rerouted recvfrom(). */ +#define recvfrom(s, buf, len, flags, from, fromlen) \ + pf_recvfrom((s), (buf), (len), (flags), (from), (fromlen), \ + __FUNCTION__, __FILE__, __LINE__) + +/*! \brief Rerouted sendto(). */ +#define sendto(s, buf, len, flags, to, tolen) \ + pf_sendto((s), (buf), (len), (flags), (to), (tolen), \ + __FUNCTION__, __FILE__, __LINE__) + +/* + * Pthreads. + */ + +/*! \brief Rerouted pthread_mutex_lock(). */ +#define pthread_mutex_lock(m) \ + pf_pthread_mutex_lock(m, __FUNCTION__, __FILE__, __LINE__) + +/*! \brief Rerouted pthread_mutex_unlock(). */ +#define pthread_mutex_unlock(m) \ + pf_pthread_mutex_unlock(m, __FUNCTION__, __FILE__, __LINE__) + +#else // PROF_LATENCY + +/* Profiler tools */ +#define perf_begin() +#define perf_end(d) + +#endif // PROF_LATENCY +#endif // _KNOTD_COMMON_LATENCY_H_ + +/*! @} */ diff --git a/src/common/libtap/README b/src/common/libtap/README new file mode 100644 index 0000000..d57b81d --- /dev/null +++ b/src/common/libtap/README @@ -0,0 +1,231 @@ +NAME +==== + +libtap - Write tests in C + +SYNOPSIS +======== + + #include <tap.h> + + int foo () {return 3;} + char *bar () {return "fnord";} + + int main () { + plan(5); + ok(foo() == 3); + is(bar(), "eek"); + ok(foo() <= 8732, "foo <= %d", 8732); + like(bar(), "f(yes|no)r*[a-f]$", "is like"); + cmp_ok(foo(), ">=", 10, "foo is greater than ten"); + return exit_status(); + } + +results in: + + 1..5 + ok 1 + not ok 2 + # Failed test at synopsis.c line 9. + # got: 'fnord' + # expected: 'eek' + ok 3 - foo <= 8732 + ok 4 - is like + not ok 5 - foo is greater than ten + # Failed test 'foo is greater than ten' + # at synopsis.c line 12. + # 3 + # >= + # 10 + # Looks like you failed 2 tests of 5 run. + +DESCRIPTION +=========== + +tap is an easy to read and easy to write way of creating tests for your +software. This library creates functions that can be used to generate it for +your C programs. It is mostly based on the Test::More Perl module. + +FUNCTIONS +========= + +- plan(tests) +- plan(NO_PLAN) + + Use this to start a series of tests. When you know how many tests there + will be, you can put a number as a number of tests you expect to run. If + you do not know how many tests there will be, you can use plan(NO_PLAN) + or not call this function. When you pass it a number of tests to run, a + message similar to the following will appear in the output: + + 1..5 + +- ok(test) +- ok(test, fmt, ...) + + Specify a test. the test can be any statement returning a true or false + value. You may optionally pass a format string describing the test. + + ok(r = reader_new("Of Mice and Men"), "create a new reader"); + ok(reader_go_to_page(r, 55), "can turn the page"); + ok(r->page == 55, "page turned to the right one"); + + Should print out: + + ok 1 - create a new reader + ok 2 - can turn the page + ok 3 - page turned to the right one + + On failure, a diagnostic message will be printed out. + + not ok 3 - page turned to the right one + # Failed test 'page turned to the right one' + # at reader.c line 13. + +- is(got, expected) +- is(got, expected, fmt, ...) +- isnt(got, expected) +- isnt(got, expected, fmt, ...) + + Tests that the string you got is what you expected. with isnt, it is the + reverse. + + is("this", "that", "this is that"); + + prints: + + not ok 1 - this is that + # Failed test 'this is that' + # at is.c line 6. + # got: 'this' + # expected: 'that' + +- cmp_ok(a, op, b) +- cmp_ok(a, op, b, fmt, ...) + + Compares two ints with any binary operator that doesn't require an lvalue. + This is nice to use since it provides a better error message than an + equivalent ok. + + cmp_ok(420, ">", 666); + + prints: + + not ok 1 + # Failed test at cmpok.c line 5. + # 420 + # > + # 666 + +- like(got, expected) +- like(got, expected, fmt, ...) +- unlike(got, expected) +- unlike(got, expected, fmt, ...) + + Tests that the string you got matches the expected extended POSIX regex. + unlike is the reverse. These macros are the equivalent of a skip on + Windows. + + like("stranger", "^s.(r).*\\1$", "matches the regex"); + + prints: + + ok 1 - matches the regex + +- pass() +- pass(fmt, ...) +- fail() +- fail(fmt, ...) + + Speciy that a test succeeded or failed. Use these when the statement is + longer than you can fit into the argument given to an ok() test. + +- dies_ok(code) +- dies_ok(code, fmt, ...) +- lives_ok(code) +- lives_ok(code, fmt, ...) + + Tests whether the given code causes your program to exit. The code gets + passed to a macro that will test it in a forked process. If the code + succeeds it will be executed in the parent process. You can test things + like passing a function a null pointer and make sure it doesnt + dereference it and crash. + + dies_ok({abort();}, "abort does close your program"); + dies_ok({int x = 0/0;}, "divide by zero crash"); + lives ok({pow(3.0, 5.0)}, "nothing wrong with taking 3**5"); + + On Windows, these macros are the equivalent of a skip. + +- exit_status() + + Summarizes the tests that occurred. If there was no plan, it will print + out the number of tests as. + + 1..5 + + It will also print a diagnostic message about how many + failures there were. + + # Looks like you failed 2 tests of 3 run. + + If all planned tests were successful, it will return 0. If any test fails, + it will return the number of failed tests (including ones that were + missing). If they all passed, but there were missing tests, it will return + 255. + +- note(fmt, ...) +- diag(fmt, ...) + + print out a message to the tap output. note prints to stdout and diag + prints to stderr. Each line is preceeded by a "# " so that you know its a + diagnostic message. + + note("This is\na note\nto describe\nsomething."); + + prints: + + # This is + # a note + # to describe + # something + + ok() and these functions return ints so you can use them like: + + ok(1) && note("yo!"); + ok(0) || diag("I have no idea what just happened"); + +- skip(test, n) +- skip(test, n, fmt, ...) +- endskip + + Skip a series of n tests if test is true. You may give a reason why you are + skipping them or not. The (possibly) skipped tests must occur between the + skip and endskip macros. + + skip(TRUE, 2); + ok(1); + ok(0); + endskip; + + prints: + + ok 1 # skip + ok 2 # skip + +- todo() +- todo(fmt, ...) +- endtodo + + Specifies a series of tests that you expect to fail because they are not + yet implemented. + + todo() + ok(0); + endtodo; + + prints: + + not ok 1 # TODO + # Failed (TODO) test at todo.c line 7 + diff --git a/src/common/libtap/tap.c b/src/common/libtap/tap.c new file mode 100644 index 0000000..61e0528 --- /dev/null +++ b/src/common/libtap/tap.c @@ -0,0 +1,313 @@ +/* Copyright (C) 2011 CZ.NIC, z.s.p.o. <knot-dns@labs.nic.cz> + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. + */ + +#include <config.h> +#include <stdio.h> +#include <stdlib.h> +#include <stdarg.h> +#include <string.h> + +//#include "common.h" +#include "tap.h" + +static int expected_tests = NO_PLAN; +static int failed_tests; +static int current_test; +static char *todo_mesg; + +void +plan (int tests) { + expected_tests = tests; + if (tests != NO_PLAN) + printf("1..%d\n", tests); +} + +static char * +vstrdupf (const char *fmt, va_list args) { + char *str; + int size; + va_list args2; + va_copy(args2, args); + if (!fmt) + fmt = ""; + size = vsnprintf(NULL, 0, fmt, args2) + 2; + str = malloc(size); + vsprintf(str, fmt, args); + va_end(args2); + return str; +} + +int +vok_at_loc (const char *file, int line, int test, const char *fmt, + va_list args) +{ + char *name = vstrdupf(fmt, args); + printf("%sok %d", test ? "" : "not ", ++current_test); + if (*name) + printf(" - %s", name); + if (todo_mesg) { + printf(" # TODO"); + if (*todo_mesg) + printf(" %s", todo_mesg); + } + printf("\n"); + if (!test) { + if (*name) + diag(" Failed%s test '%s'\n at %s line %d.", + todo_mesg ? " (TODO)" : "", name, file, line); + else + diag(" Failed%s test at %s line %d.", + todo_mesg ? " (TODO)" : "", file, line); + if (!todo_mesg) + failed_tests++; + } + free(name); + return test; +} + +int +ok_at_loc (const char *file, int line, int test, const char *fmt, ...) { + va_list args; + va_start(args, fmt); + vok_at_loc(file, line, test, fmt, args); + va_end(args); + return test; +} + +static int +mystrcmp (const char *a, const char *b) { + return a == b ? 0 : !a ? -1 : !b ? 1 : strcmp(a, b); +} + +#define eq(a, b) (!mystrcmp(a, b)) +#define ne(a, b) (mystrcmp(a, b)) + +int +is_at_loc (const char *file, int line, const char *got, const char *expected, + const char *fmt, ...) +{ + int test = eq(got, expected); + va_list args; + va_start(args, fmt); + vok_at_loc(file, line, test, fmt, args); + va_end(args); + if (!test) { + diag(" got: '%s'", got); + diag(" expected: '%s'", expected); + } + return test; +} + +int +isnt_at_loc (const char *file, int line, const char *got, const char *expected, + const char *fmt, ...) +{ + int test = ne(got, expected); + va_list args; + va_start(args, fmt); + vok_at_loc(file, line, test, fmt, args); + va_end(args); + if (!test) { + diag(" got: '%s'", got); + diag(" expected: anything else"); + } + return test; +} + +int +cmp_ok_at_loc (const char *file, int line, int a, const char *op, int b, + const char *fmt, ...) +{ + int test = eq(op, "||") ? a || b + : eq(op, "&&") ? a && b + : eq(op, "|") ? a | b + : eq(op, "^") ? a ^ b + : eq(op, "&") ? a & b + : eq(op, "==") ? a == b + : eq(op, "!=") ? a != b + : eq(op, "<") ? a < b + : eq(op, ">") ? a > b + : eq(op, "<=") ? a <= b + : eq(op, ">=") ? a >= b + : eq(op, "<<") ? a << b + : eq(op, ">>") ? a >> b + : eq(op, "+") ? a + b + : eq(op, "-") ? a - b + : eq(op, "*") ? a * b + : eq(op, "/") ? a / b + : eq(op, "%") ? a % b + : diag("unrecognized operator '%s'", op); + va_list args; + va_start(args, fmt); + vok_at_loc(file, line, test, fmt, args); + va_end(args); + if (!test) { + diag(" %d", a); + diag(" %s", op); + diag(" %d", b); + } + return test; +} + +static void +vdiag_to_fh (FILE *fh, const char *fmt, va_list args) { + char *mesg, *line; + int i; + if (!fmt) + return; + mesg = vstrdupf(fmt, args); + line = mesg; + for (i = 0; *line; i++) { + char c = mesg[i]; + if (!c || c == '\n') { + mesg[i] = '\0'; + fprintf(fh, "# %s\n", line); + if (!c) break; + mesg[i] = c; + line = &mesg[i+1]; + } + } + free(mesg); + return; +} + +int +diag (const char *fmt, ...) { + va_list args; + va_start(args, fmt); + vdiag_to_fh(stderr, fmt, args); + va_end(args); + return 0; +} + +int +note (const char *fmt, ...) { + va_list args; + va_start(args, fmt); + vdiag_to_fh(stdout, fmt, args); + va_end(args); + return 0; +} + +int +exit_status () { + int retval = 0; + if (expected_tests == NO_PLAN) { + printf("1..%d\n", current_test); + } + else if (current_test != expected_tests) { + diag("Looks like you planned %d test%s but ran %d.", + expected_tests, expected_tests > 1 ? "s" : "", current_test); + retval = 255; + } + if (failed_tests) { + diag("Looks like you failed %d test%s of %d run.", + failed_tests, failed_tests > 1 ? "s" : "", current_test); + if (expected_tests == NO_PLAN) + retval = failed_tests; + else + retval = expected_tests - current_test + failed_tests; + } + return retval; +} + +void +skippy (int n, const char *fmt, ...) { + char *why; + va_list args; + va_start(args, fmt); + why = vstrdupf(fmt, args); + va_end(args); + while (n --> 0) { + printf("ok %d ", ++current_test); + note("skip %s\n", why); + } + free(why); +} + +void +ctodo (int ignore, const char *fmt, ...) { + va_list args; + va_start(args, fmt); + todo_mesg = vstrdupf(fmt, args); + va_end(args); +} + +void +cendtodo () { + free(todo_mesg); + todo_mesg = NULL; +} + +#ifndef _WIN32 +#include <sys/mman.h> +#include <regex.h> + +#ifndef MAP_ANONYMOUS +#define MAP_ANONYMOUS MAP_ANON +#endif + +/* Create a shared memory int to keep track of whether a piece of code executed +dies. to be used in the dies_ok and lives_ok macros */ +int +tap_test_died (int status) { + static int *test_died = NULL; + int prev; + if (!test_died) { + test_died = mmap(0, sizeof (int), PROT_READ | PROT_WRITE, + MAP_SHARED | MAP_ANONYMOUS, -1, 0); + *test_died = 0; + } + prev = *test_died; + *test_died = status; + return prev; +} + +int +like_at_loc (int for_match, const char *file, int line, const char *got, + const char *expected, const char *fmt, ...) +{ + int test; + regex_t re; + int err = regcomp(&re, expected, REG_EXTENDED); + if (err) { + char errbuf[256]; + regerror(err, &re, errbuf, sizeof errbuf); + fprintf(stderr, "Unable to compile regex '%s': %s at %s line %d\n", + expected, errbuf, file, line); + exit(255); + } + err = regexec(&re, got, 0, NULL, 0); + regfree(&re); + test = for_match ? !err : err; + va_list args; + va_start(args, fmt); + vok_at_loc(file, line, test, fmt, args); + va_end(args); + if (!test) { + if (for_match) { + diag(" '%s'", got); + diag(" doesn't match: '%s'", expected); + } + else { + diag(" '%s'", got); + diag(" matches: '%s'", expected); + } + } + return test; +} +#endif + diff --git a/src/common/libtap/tap.h b/src/common/libtap/tap.h new file mode 100644 index 0000000..2e89b90 --- /dev/null +++ b/src/common/libtap/tap.h @@ -0,0 +1,101 @@ +/* Copyright (C) 2011 CZ.NIC, z.s.p.o. <knot-dns@labs.nic.cz> + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. + */ + +#ifndef __TAP_H__ +#define __TAP_H__ + +#include <stdio.h> +#include <stdlib.h> +#include <stdarg.h> + +#define NO_PLAN -1 +#define ok(...) ok_at_loc(__FILE__, __LINE__, __VA_ARGS__, NULL) +#define pass(...) ok(1, ## __VA_ARGS__) +#define fail(...) ok(0, ## __VA_ARGS__) +#define is(...) is_at_loc(__FILE__, __LINE__, __VA_ARGS__, NULL) +#define isnt(...) isnt_at_loc(__FILE__, __LINE__, __VA_ARGS__, NULL) +#define cmp_ok(...) cmp_ok_at_loc(__FILE__, __LINE__, __VA_ARGS__, NULL) + +int vok_at_loc (const char *file, int line, int test, const char *fmt, + va_list args); +void plan (int tests); +int ok_at_loc (const char *file, int line, int test, const char *fmt, + ...); +int diag (const char *fmt, ...); +int note (const char *fmt, ...); +int exit_status (void); +void skippy (int n, const char *fmt, ...); +void ctodo (int ignore, const char *fmt, ...); +void cendtodo (void); +int is_at_loc (const char *file, int line, const char *got, + const char *expected, const char *fmt, ...); +int isnt_at_loc (const char *file, int line, const char *got, + const char *expected, const char *fmt, ...); +int cmp_ok_at_loc (const char *file, int line, int a, const char *op, + int b, const char *fmt, ...); + +#ifdef _WIN32 +#define like(...) skippy(1, "like is not implemented on MSWin32") +#define unlike(...) like() +#else +#define like(...) like_at_loc(1, __FILE__, __LINE__, __VA_ARGS__, NULL) +#define unlike(...) like_at_loc(0, __FILE__, __LINE__, __VA_ARGS__, NULL) +int like_at_loc (int for_match, const char *file, int line, + const char *got, const char *expected, + const char *fmt, ...); +#endif + +#define skip(test, ...) do {if (test) {skippy(__VA_ARGS__, NULL); break;} +#define endskip } while (0) + +#define todo(...) ctodo(0, ## __VA_ARGS__, NULL) +#define endtodo cendtodo() + +#define dies_ok(code, ...) dies_ok_common(code, 1, ## __VA_ARGS__) +#define lives_ok(code, ...) dies_ok_common(code, 0, ## __VA_ARGS__) + +#ifdef _WIN32 +#define dies_ok_common(...) \ + skippy(1, "Death detection is not supported on MSWin32") +#else +#include <unistd.h> +#include <sys/types.h> +#include <sys/wait.h> +int tap_test_died (int status); +#define dies_ok_common(code, for_death, ...) \ + do { \ + tap_test_died(1); \ + int cpid = fork(); \ + switch (cpid) { \ + case -1: \ + perror("fork error"); \ + exit(EXIT_FAILURE); \ + case 0: /* child */ \ + close(1); close(2); \ + code \ + tap_test_died(0); \ + exit(EXIT_SUCCESS); \ + } \ + if (waitpid(cpid, NULL, 0) < 0) { \ + perror("waitpid error"); \ + exit(EXIT_FAILURE); \ + } \ + int it_died = tap_test_died(0); \ + if (!it_died) {code} \ + ok(for_death ? it_died : !it_died, ## __VA_ARGS__); \ + } while (0) +#endif +#endif diff --git a/src/common/libtap/tap_unit.h b/src/common/libtap/tap_unit.h new file mode 100644 index 0000000..c248fde --- /dev/null +++ b/src/common/libtap/tap_unit.h @@ -0,0 +1,94 @@ +/* Copyright (C) 2011 CZ.NIC, z.s.p.o. <knot-dns@labs.nic.cz> + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. + */ +/*! + * \file tap_unit.h + * \author Marek Vavrusa <marek.vavusa@nic.cz> + * + * \brief libtap test unit. + * + * Contains description of a single test unit API. + * + * Export unit_api in each module header file, + * and set function pointer to according test routines. + * + * <b>Example code for myunit.h</b> + * \code + * #ifndef MYUNIT_TEST_H + * #define MYUNIT_TEST_H + * + * // Export unittest symbol + * unit_api mymodule; + * + * #endif // MYUNIT_TEST_H + * \endcode + * + * <b>Example code for myunit.c</b> + * \code + * #include "myunit.h" + * + * // Function to return unit test count + * int myunit_count(int argc, char *argv[]) { + * return 1; // Number of tests in this unit + * } + * + * // Function to perform tests + * int myunit_run(int argc, char *argv[]) { + * // 1. test + * ok(1 == 1, "test OK"); + * return 0; + * } + * + * // Declare module API + * unit_api mymodule = { + * "My module", + * &myunit_count, + * &myunit_run + * }; + * \endcode + * + * To incorporate test, add it to unit tests main(). + * + * See https://github.com/zorgnax/libtap for libtap API reference. + * + * \addtogroup tests + * @{ + */ + +#ifndef _TAP_UNIT_H_ +#define _TAP_UNIT_H_ + +#include "common/libtap/tap.h" + +/*! \brief Pointer to function for unit_api. */ +typedef int(unitapi_f)(int, char*[]); + + +/*! + * \brief Basic Unit APIs. + * + * Each unit should have one global variable with + * an initialized instance of unit_api. + */ +typedef struct { + const char *name; /*!< Test unit name. */ + unitapi_f *count; /*!< Function to calculate number of tests. */ + unitapi_f *run; /*!< Function to run unit tests. */ +} unit_api; + +#endif // _TAP_UNIT_H_ + +/*! @} */ + diff --git a/src/common/lists.c b/src/common/lists.c new file mode 100644 index 0000000..9a93733 --- /dev/null +++ b/src/common/lists.c @@ -0,0 +1,160 @@ +/* + * BIRD Library -- Linked Lists + * + * (c) 1998 Martin Mares <mj@ucw.cz> + * + * Can be freely distributed and used under the terms of the GNU GPL. + */ + +/** + * DOC: Linked lists + * + * The BIRD library provides a set of functions for operating on linked + * lists. The lists are internally represented as standard doubly linked + * lists with synthetic head and tail which makes all the basic operations + * run in constant time and contain no extra end-of-list checks. Each list + * is described by a &list structure, nodes can have any format as long + * as they start with a &node structure. If you want your nodes to belong + * to multiple lists at once, you can embed multiple &node structures in them + * and use the SKIP_BACK() macro to calculate a pointer to the start of the + * structure from a &node pointer, but beware of obscurity. + * + * There also exist safe linked lists (&slist, &snode and all functions + * being prefixed with |s_|) which support asynchronous walking very + * similar to that used in the &fib structure. + */ + +#define _BIRD_LISTS_C_ + +#include <stdlib.h> +#include <string.h> +#include "common/lists.h" + +/** + * add_tail - append a node to a list + * @l: linked list + * @n: list node + * + * add_tail() takes a node @n and appends it at the end of the list @l. + */ +LIST_INLINE void +add_tail(list *l, node *n) +{ + node *z = l->tail; + + n->next = (node *) &l->null; + n->prev = z; + z->next = n; + l->tail = n; +} + +/** + * add_head - prepend a node to a list + * @l: linked list + * @n: list node + * + * add_head() takes a node @n and prepends it at the start of the list @l. + */ +LIST_INLINE void +add_head(list *l, node *n) +{ + node *z = l->head; + + n->next = z; + n->prev = (node *) &l->head; + z->prev = n; + l->head = n; +} + +/** + * insert_node - insert a node to a list + * @n: a new list node + * @after: a node of a list + * + * Inserts a node @n to a linked list after an already inserted + * node @after. + */ +LIST_INLINE void +insert_node(node *n, node *after) +{ + node *z = after->next; + + n->next = z; + n->prev = after; + after->next = n; + z->prev = n; +} + +/** + * rem_node - remove a node from a list + * @n: node to be removed + * + * Removes a node @n from the list it's linked in. + */ +LIST_INLINE void +rem_node(node *n) +{ + node *z = n->prev; + node *x = n->next; + + z->next = x; + x->prev = z; + n->prev = 0; + n->next = 0; +} + +/** + * init_list - create an empty list + * @l: list + * + * init_list() takes a &list structure and initializes its + * fields, so that it represents an empty list. + */ +LIST_INLINE void +init_list(list *l) +{ + l->head = (node *) &l->null; + l->null = NULL; + l->tail = (node *) &l->head; +} + +/** + * add_tail_list - concatenate two lists + * @to: destination list + * @l: source list + * + * This function appends all elements of the list @l to + * the list @to in constant time. + */ +LIST_INLINE void +add_tail_list(list *to, list *l) +{ + node *p = to->tail; + node *q = l->head; + + p->next = q; + q->prev = p; + q = l->tail; + q->next = (node *) &to->null; + to->tail = q; +} + +/** + * list_dup - duplicate list + * @to: destination list + * @l: source list + * + * This function duplicates all elements of the list @l to + * the list @to in linear time. + * + * This function only works with a homogenous item size. + */ +void list_dup(list *dst, list *src, size_t itemsz) +{ + node *n = 0; + WALK_LIST(n, *src) { + node *i = malloc(itemsz); + memcpy(i, n, itemsz); + add_tail(dst, i); + } +} diff --git a/src/common/lists.h b/src/common/lists.h new file mode 100644 index 0000000..972ea49 --- /dev/null +++ b/src/common/lists.h @@ -0,0 +1,103 @@ +/* Copyright (C) 2011 CZ.NIC, z.s.p.o. <knot-dns@labs.nic.cz> + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. + */ +/* + * BIRD Library -- Linked Lists + * + * (c) 1998 Martin Mares <mj@ucw.cz> + * + * Can be freely distributed and used under the terms of the GNU GPL. + */ + +#ifndef _BIRD_LISTS_H_ +#define _BIRD_LISTS_H_ + +/* + * I admit the list structure is very tricky and also somewhat awkward, + * but it's both efficient and easy to manipulate once one understands the + * basic trick: The list head always contains two synthetic nodes which are + * always present in the list: the head and the tail. But as the `next' + * entry of the tail and the `prev' entry of the head are both NULL, the + * nodes can overlap each other: + * + * head head_node.next + * null head_node.prev tail_node.next + * tail tail_node.prev + */ + +#include <string.h> // size_t + +typedef struct node { + struct node *next, *prev; +} node; + +typedef struct list { /* In fact two overlayed nodes */ + struct node *head, *null, *tail; +} list; + +#define NODE (node *) +#define HEAD(list) ((void *)((list).head)) +#define TAIL(list) ((void *)((list).tail)) +#define WALK_LIST(n,list) for(n=HEAD(list);(NODE (n))->next; \ + n=(void *)((NODE (n))->next)) +#define WALK_LIST_DELSAFE(n,nxt,list) \ + for(n=HEAD(list); (nxt=(void *)((NODE (n))->next)); n=(void *) nxt) +/* WALK_LIST_FIRST supposes that called code removes each processed node */ +#define WALK_LIST_FIRST(n,list) \ + while(n=HEAD(list), (NODE (n))->next) +#define WALK_LIST_BACKWARDS(n,list) for(n=TAIL(list);(NODE (n))->prev; \ + n=(void *)((NODE (n))->prev)) +#define WALK_LIST_BACKWARDS_DELSAFE(n,prv,list) \ + for(n=TAIL(list); prv=(void *)((NODE (n))->prev); n=(void *) prv) + +#define EMPTY_LIST(list) (!(list).head->next) + +/*! \brief Free every node in the list. */ +#define WALK_LIST_FREE(list) \ + do { \ + node *n=0,*nxt=0; \ + WALK_LIST_DELSAFE(n,nxt,list) { \ + free(n); \ + } \ + } while(0) + +void add_tail(list *, node *); +void add_head(list *, node *); +void rem_node(node *); +void add_tail_list(list *, list *); +void init_list(list *); +void insert_node(node *, node *); +void list_dup(list *dst, list *src, size_t itemsz); + +/*! + * \brief List item for string lists. + */ +typedef struct strnode_t { + node n; + char *str; +} strnode_t; + +/*! \todo This is broken atm. +#ifndef _BIRD_LISTS_C_ +#define LIST_INLINE extern inline +#include "knot/lib/lists.c" +#undef LIST_INLINE +#else +#define LIST_INLINE +#endif +*/ +#define LIST_INLINE + +#endif diff --git a/src/common/modified_tree.h b/src/common/modified_tree.h new file mode 100644 index 0000000..4c3e325 --- /dev/null +++ b/src/common/modified_tree.h @@ -0,0 +1,292 @@ +/* tree.h -- AVL trees (in the spirit of BSD's 'queue.h') -*- C -*- */ + +/* Copyright (c) 2005 Ian Piumarta + * + * All rights reserved. + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the 'Software'), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, and/or sell copies of the + * Software, and to permit persons to whom the Software is furnished to do so, + * provided that the above copyright notice(s) and this permission notice appear + * in all copies of the Software and that both the above copyright notice(s) and + * this permission notice appear in supporting documentation. + * + * THE SOFTWARE IS PROVIDED 'AS IS'. USE ENTIRELY AT YOUR OWN RISK. + */ + +/* This file defines an AVL balanced binary tree [Georgii M. Adelson-Velskii and + * Evgenii M. Landis, 'An algorithm for the organization of information', + * Doklady Akademii Nauk SSSR, 146:263-266, 1962 (Russian). Also in Myron + * J. Ricci (trans.), Soviet Math, 3:1259-1263, 1962 (English)]. + * + * An AVL tree is headed by pointers to the root node and to a function defining + * the ordering relation between nodes. Each node contains an arbitrary payload + * plus three fields per tree entry: the depth of the subtree for which it forms + * the root and two pointers to child nodes (singly-linked for minimum space, at + * the expense of direct access to the parent node given a pointer to one of the + * children). The tree is rebalanced after every insertion or removal. The + * tree may be traversed in two directions: forward (in-order left-to-right) and + * reverse (in-order, right-to-left). + * + * Because of the recursive nature of many of the operations on trees it is + * necessary to define a number of helper functions for each type of tree node. + * The macro TREE_DEFINE(node_tag, entry_name) defines these functions with + * unique names according to the node_tag. This macro should be invoked, + * thereby defining the necessary functions, once per node tag in the program. + * + * For details on the use of these macros, see the tree(3) manual page. + */ + +#ifndef _modified_tree_h +#define _modified_tree_h + + +#define MOD_TREE_DELTA_MAX 1 + +#define MOD_TREE_ENTRY(type) \ + struct { \ + struct type *avl_left; \ + struct type *avl_right; \ + int avl_height; \ + } + +#define MOD_TREE_HEAD(name, type) \ + struct name { \ + struct type *th_root; \ + int (*th_cmp)(void *lhs, void *rhs); \ + } + +#define MOD_TREE_INITIALIZER(cmp) { 0, cmp} + +#define MOD_TREE_DELTA(self, field) \ + (( (((self)->field.avl_left) ? (self)->field.avl_left->field.avl_height : 0)) \ + - (((self)->field.avl_right) ? (self)->field.avl_right->field.avl_height : 0)) + +/* Recursion prevents the following from being defined as macros. */ + +#define MOD_TREE_DEFINE(node, field) \ + \ + struct node *MOD_TREE_BALANCE_##node##_##field(struct node *); \ + \ + struct node *MOD_TREE_ROTL_##node##_##field(struct node *self) \ + { \ + struct node *r= self->field.avl_right; \ + self->field.avl_right= r->field.avl_left; \ + r->field.avl_left= MOD_TREE_BALANCE_##node##_##field(self); \ + return MOD_TREE_BALANCE_##node##_##field(r); \ + } \ + \ + struct node *MOD_TREE_ROTR_##node##_##field(struct node *self) \ + { \ + struct node *l= self->field.avl_left; \ + self->field.avl_left= l->field.avl_right; \ + l->field.avl_right= MOD_TREE_BALANCE_##node##_##field(self); \ + return MOD_TREE_BALANCE_##node##_##field(l); \ + } \ + \ + struct node *MOD_TREE_BALANCE_##node##_##field(struct node *self) \ + { \ + int delta= MOD_TREE_DELTA(self, field); \ + \ + if (delta < -MOD_TREE_DELTA_MAX) \ + { \ + if (MOD_TREE_DELTA(self->field.avl_right, field) > 0) \ + self->field.avl_right= MOD_TREE_ROTR_##node##_##field(self->field.avl_right); \ + return MOD_TREE_ROTL_##node##_##field(self); \ + } \ + else if (delta > MOD_TREE_DELTA_MAX) \ + { \ + if (MOD_TREE_DELTA(self->field.avl_left, field) < 0) \ + self->field.avl_left= MOD_TREE_ROTL_##node##_##field(self->field.avl_left); \ + return MOD_TREE_ROTR_##node##_##field(self); \ + } \ + self->field.avl_height= 0; \ + if (self->field.avl_left && (self->field.avl_left->field.avl_height > self->field.avl_height)) \ + self->field.avl_height= self->field.avl_left->field.avl_height; \ + if (self->field.avl_right && (self->field.avl_right->field.avl_height > self->field.avl_height)) \ + self->field.avl_height= self->field.avl_right->field.avl_height; \ + self->field.avl_height += 1; \ + return self; \ + } \ + \ + struct node *MOD_TREE_INSERT_##node##_##field \ + (struct node *self, struct node *elm, int (*compare)(void *lhs, void *rhs), int (*merge)(void **lhs, void **rhs), int *merged)\ + { \ + if (!self) { \ + *merged = 0; \ + return elm; } \ + int cmp = compare(elm->data, self->data); \ + if (cmp < 0) \ + self->field.avl_left= MOD_TREE_INSERT_##node##_##field(self->field.avl_left, elm, compare, merge, merged); \ + else if (cmp > 0) \ + self->field.avl_right= MOD_TREE_INSERT_##node##_##field(self->field.avl_right, elm, compare, merge, merged); \ + else if (merge) { \ + merge(&(elm->data), &(self->data)); \ + *merged = 1; } \ + else \ + self->field.avl_right= MOD_TREE_INSERT_##node##_##field(self->field.avl_right, elm, compare, merge, merged); \ + return MOD_TREE_BALANCE_##node##_##field(self); \ + } \ + \ + struct node *MOD_TREE_FIND_##node##_##field \ + (struct node *self, struct node *elm, int (*compare)(void *lhs, void *rhs)) \ + { \ + if (!compare) \ + return 0; \ + if (!self) \ + return 0; \ + if (compare(elm->data, self->data) == 0) \ + return self; \ + if (compare(elm->data, self->data) < 0) \ + return MOD_TREE_FIND_##node##_##field(self->field.avl_left, elm, compare); \ + else \ + return MOD_TREE_FIND_##node##_##field(self->field.avl_right, elm, compare); \ + } \ + \ + int MOD_TREE_FIND_LESS_EQUAL_##node##_##field \ + (struct node *self, struct node *elm, int (*compare)(void *lhs, void *rhs), struct node **found, struct node **prev) \ + { \ + if (!self) \ + return 0; \ + if (compare(elm->data, self->data) == 0) { \ + *found = self; \ + return 1; \ + } \ + if (compare(elm->data, self->data) < 0) { \ + int ret = MOD_TREE_FIND_LESS_EQUAL_##node##_##field(self->field.avl_left, elm, compare, found, prev); \ + if (ret == 0 && *prev == NULL) { \ + *prev = self; \ + ret = -1; \ + } \ + return ret; \ + } else { \ + *found = self; \ + *prev = self; \ + return MOD_TREE_FIND_LESS_EQUAL_##node##_##field(self->field.avl_right, elm, compare, found, prev); \ + } \ + } \ + \ + struct node *MOD_TREE_MOVE_RIGHT_##node##_##field(struct node *self, struct node *rhs) \ + { \ + if (!self) \ + return rhs; \ + self->field.avl_right= MOD_TREE_MOVE_RIGHT_##node##_##field(self->field.avl_right, rhs); \ + return MOD_TREE_BALANCE_##node##_##field(self); \ + } \ + \ + struct node *MOD_TREE_REMOVE_##node##_##field \ + (struct node *self, struct node *elm, int (*compare)(void *lhs, void *rhs), void (*del)(struct node *lhs)) \ + { \ + if (!self) return 0; \ + \ + if (compare(elm->data, self->data) == 0) \ + { \ + struct node *tmp= MOD_TREE_MOVE_RIGHT_##node##_##field(self->field.avl_left, self->field.avl_right); \ + self->field.avl_left= 0; \ + self->field.avl_right= 0; \ + del(self); \ + return tmp; \ + } \ + if (compare(elm->data, self->data) < 0) \ + self->field.avl_left= MOD_TREE_REMOVE_##node##_##field(self->field.avl_left, elm, compare, del); \ + else \ + self->field.avl_right= MOD_TREE_REMOVE_##node##_##field(self->field.avl_right, elm, compare, del); \ + return MOD_TREE_BALANCE_##node##_##field(self); \ + } \ + \ + void MOD_TREE_FORWARD_APPLY_ALL_##node##_##field \ + (struct node *self, void (*function)(void *node, void *data), void *data) \ + { \ + if (self) \ + { \ + MOD_TREE_FORWARD_APPLY_ALL_##node##_##field(self->field.avl_left, function, data); \ + function(self->data, data); \ + MOD_TREE_FORWARD_APPLY_ALL_##node##_##field(self->field.avl_right, function, data); \ + } \ + } \ + \ + void MOD_TREE_REVERSE_APPLY_ALL_##node##_##field \ + (struct node *self, void (*function)(struct node *node, void *data), void *data) \ + { \ + if (self) \ + { \ + MOD_TREE_REVERSE_APPLY_ALL_##node##_##field(self->field.avl_right, function, data); \ + function(self, data); \ + MOD_TREE_REVERSE_APPLY_ALL_##node##_##field(self->field.avl_left, function, data); \ + } \ + } \ + \ + void MOD_TREE_POST_ORDER_APPLY_ALL_##node##_##field \ + (struct node *self, void (*function)(struct node *node, void *data), void *data) \ + { \ + if (self) \ + { \ + MOD_TREE_POST_ORDER_APPLY_ALL_##node##_##field(self->field.avl_left, function, data); \ + MOD_TREE_POST_ORDER_APPLY_ALL_##node##_##field(self->field.avl_right, function, data); \ + function(self, data); \ + } \ + } \ + \ +void MOD_TREE_DESTROY_ALL_##node##_##field \ + (struct node *self, void (*function)(void *node, void *data), void(*dest)(struct node *node), void *data) \ +{ \ + if (self) \ + { \ + MOD_TREE_DESTROY_ALL_##node##_##field(self->field.avl_left, function, dest, data); \ + MOD_TREE_DESTROY_ALL_##node##_##field(self->field.avl_right, function, dest, data); \ + if (function != NULL) \ + function(self->data, data); \ + dest(self); \ + } \ +} \ + \ + void MOD_TREE_REVERSE_APPLY_POST_ALL_##node##_##field \ + (struct node *self, void (*function)(struct node *node, void *data), void *data) \ + { \ + if (self) \ + { \ + MOD_TREE_REVERSE_APPLY_POST_ALL_##node##_##field(self->field.avl_right, function, data); \ + MOD_TREE_REVERSE_APPLY_POST_ALL_##node##_##field(self->field.avl_left, function, data); \ + function(self, data); \ + } \ +} + +#define MOD_TREE_INSERT(head, node, field, elm, merge, merged) \ + ((head)->th_root= MOD_TREE_INSERT_##node##_##field((head)->th_root, (elm), (head)->th_cmp, merge, merged)) + +#define MOD_TREE_FIND(head, node, field, elm) \ + (MOD_TREE_FIND_##node##_##field((head)->th_root, (elm), (head)->th_cmp)) + +#define MOD_TREE_FIND_LESS_EQUAL(head, node, field, elm, found, prev) \ + (MOD_TREE_FIND_LESS_EQUAL_##node##_##field((head)->th_root, (elm), (head)->th_cmp, found, prev)) + +#define MOD_TREE_REMOVE(head, node, field, elm, rem) \ + ((head)->th_root= MOD_TREE_REMOVE_##node##_##field((head)->th_root, (elm), (head)->th_cmp, (rem))) + +#define MOD_TREE_DEPTH(head, field) \ + ((head)->th_root->field.avl_height) + +#define MOD_TREE_FORWARD_APPLY(head, node, field, function, data) \ + MOD_TREE_FORWARD_APPLY_ALL_##node##_##field((head)->th_root, function, data) + +#define MOD_TREE_REVERSE_APPLY(head, node, field, function, data) \ + MOD_TREE_REVERSE_APPLY_ALL_##node##_##field((head)->th_root, function, data) + +#define MOD_TREE_POST_ORDER_APPLY(head, node, field, function, data) \ + MOD_TREE_POST_ORDER_APPLY_ALL_##node##_##field((head)->th_root, function, data) + +#define MOD_TREE_DESTROY(head, node, field, function, dest, data) \ + MOD_TREE_DESTROY_ALL_##node##_##field((head)->th_root, function, dest, data) + +#define MOD_TREE_REVERSE_APPLY_POST(head, node, field, function, data) \ + MOD_TREE_REVERSE_APPLY_POST_ALL_##node##_##field((head)->th_root, function, data) + +#define MOD_TREE_INIT(head, cmp) do { \ + (head)->th_root= 0; \ + (head)->th_cmp= (cmp); \ + } while (0) + + +#endif /* __MOD_TREE_h */ diff --git a/src/common/print.c b/src/common/print.c new file mode 100644 index 0000000..9764568 --- /dev/null +++ b/src/common/print.c @@ -0,0 +1,57 @@ +/* Copyright (C) 2011 CZ.NIC, z.s.p.o. <knot-dns@labs.nic.cz> + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. + */ + +#include <config.h> +#include <stdio.h> + +#include "print.h" + +void hex_printf(const char *data, int length, printf_t print_handler) +{ + int ptr = 0; + for (; ptr < length; ptr++) { + print_handler("0x%02x ", (unsigned char)*(data + ptr)); + } + print_handler("\n"); +} + +void hex_print(const char *data, int length) +{ + hex_printf(data, length, &printf); +} + +void bit_printf(const char *data, int length, printf_t print_handler) +{ + unsigned char mask = 0x01; + int ptr = 0; + int bit = 0; + for (; ptr < length; ptr++) { + for (bit = 7; bit >= 0; bit--) { + if ((mask << bit) & (unsigned char)*(data + ptr)) { + print_handler("1"); + } else { + print_handler("0"); + } + } + print_handler(" "); + } + print_handler("\n"); +} + +void bit_print(const char *data, int length) +{ + bit_printf(data, length, &printf); +} diff --git a/src/common/print.h b/src/common/print.h new file mode 100644 index 0000000..482f55e --- /dev/null +++ b/src/common/print.h @@ -0,0 +1,72 @@ +/* Copyright (C) 2011 CZ.NIC, z.s.p.o. <knot-dns@labs.nic.cz> + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. + */ +/*! + * \file print.h + * + * \author Marek Vavrusa <marek.vavrusa@nic.cz> + * + * \brief Custom printing functions. + * + * Downloaded hex_print, bit_print from http://www.digitalpeer.com/id/print + * Updated with generic printf handler. + * + * \addtogroup common_lib + * @{ + */ + +#ifndef _KNOTD_COMMON_PRINT_H_ +#define _KNOTD_COMMON_PRINT_H_ + +typedef int (*printf_t)(const char *fmt, ...); + +/*! + * \brief Prints the given data as hexadecimal characters. + * + * \param data Data to print. + * \param length Size of the \a data array. + */ +void hex_print(const char *data, int length); + +/*! + * \brief Prints the given data as hexadecimal characters using the given + * handler. + * + * \param data Data to print. + * \param length Size of the \a data array. + * \param print_handler Handler for printing. + */ +void hex_printf(const char *data, int length, printf_t print_handler); + +/*! + * \brief Prints the given data as a bitmap. + * + * \param data Data to print. + * \param length Size of the \a data array. + */ +void bit_print(const char *data, int length); + +/*! + * \brief Prints the given data as a bitmap using the given handler. + * + * \param data Data to print. + * \param length Size of the \a data array. + * \param print_handler Handler for printing. + */ +void bit_printf(const char *data, int length, printf_t print_handler); + +#endif /* _KNOTD_COMMON_PRINT_H_ */ + +/*! @} */ diff --git a/src/common/ref.c b/src/common/ref.c new file mode 100644 index 0000000..3b9c033 --- /dev/null +++ b/src/common/ref.c @@ -0,0 +1,44 @@ +/* Copyright (C) 2011 CZ.NIC, z.s.p.o. <knot-dns@labs.nic.cz> + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. + */ + +#include <stdio.h> + +#include "ref.h" + +void ref_init(ref_t *p, ref_destructor_t dtor) +{ + if (p) { + p->count = 0; + p->dtor = dtor; + } +} + +void ref_retain(ref_t *p) +{ + if (p) { + __sync_add_and_fetch(&p->count, 1); + } +} + +void ref_release(ref_t *p) +{ + if (p) { + int rc = __sync_sub_and_fetch(&p->count, 1); + if (rc == 0 && p->dtor) { + p->dtor(p); + } + } +} diff --git a/src/common/ref.h b/src/common/ref.h new file mode 100644 index 0000000..13a7037 --- /dev/null +++ b/src/common/ref.h @@ -0,0 +1,90 @@ +/* Copyright (C) 2011 CZ.NIC, z.s.p.o. <knot-dns@labs.nic.cz> + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. + */ +/*! + * \file ref.h + * + * \author Marek Vavrusa <marek.vavrusa@nic.cz> + * + * \brief Atomic reference counting structures. + * + * Reference counting allows implicit sharing of objects + * between threads with custom destructor functions. + * + * \addtogroup common_lib + * @{ + */ + +#ifndef _KNOTD_REF_H_ +#define _KNOTD_REF_H_ + +#include <stddef.h> + +struct ref_t; + +/*! \brief Prototype for object destructor callback. */ +typedef void (*ref_destructor_t)(struct ref_t * p); + +/*! + * \brief Structure for reference counting. + * + * Size equals to two sizes of pointer size. + * Structure may be embedded to the structures which + * we want to use for reference counting. + * + * \code + * struct mystruct { + * ref_t ref; + * int mydata; + * char *mystr; + * } + * \endcode + */ +typedef struct ref_t { + size_t count; /*! \brief Reference counter. */ + ref_destructor_t dtor; /*! \brief Object destructor function. */ +} ref_t; + +/*! + * \brief Initialize reference counter. + * + * Set reference counter to 0 and initialize destructor callback. + * + * \param p Reference-counted object. + * \param dtor Destructor function. + */ +void ref_init(ref_t *p, ref_destructor_t dtor); + +/*! + * \brief Mark object as used by the caller. + * + * Reference counter will be incremented. + * + * \param p Reference-counted object. + */ +void ref_retain(ref_t *p); + +/*! + * \brief Marks object as unused by the caller. + * + * Reference counter will be decremented. + * + * \param p Reference-counted object. + */ +void ref_release(ref_t *p); + +#endif /* _KNOTD_REF_H_ */ + +/*! @} */ diff --git a/src/common/skip-list.c b/src/common/skip-list.c new file mode 100644 index 0000000..79e9429 --- /dev/null +++ b/src/common/skip-list.c @@ -0,0 +1,437 @@ +/* Copyright (c) 2010 the authors listed at the following URL, and/or +the authors of referenced articles or incorporated external code: +http://en.literateprograms.org/Skip_list_(C)?action=history&offset=20080313195128 + +Permission is hereby granted, free of charge, to any person obtaining +a copy of this software and associated documentation files (the +"Software"), to deal in the Software without restriction, including +without limitation the rights to use, copy, modify, merge, publish, +distribute, sublicense, and/or sell copies of the Software, and to +permit persons to whom the Software is furnished to do so, subject to +the following conditions: + +The above copyright notice and this permission notice shall be +included in all copies or substantial portions of the Software. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, +EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF +MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. +IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY +CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, +TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE +SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. + +Retrieved from: http://en.literateprograms.org/Skip_list_(C)?oldid=12811 +*/ + +/* + * Modifications by Lubos Slovak, 2010-2011 + */ + +#include <config.h> +#include <stdio.h> +#include <stdlib.h> +#include <time.h> +#include <string.h> +#include <assert.h> + +//#include "common.h" +#include "common/skip-list.h" + +#define ERR_ALLOC_FAILED fprintf(stderr, "Allocation failed at %s:%d\n", \ + __FILE__, __LINE__) + +/*----------------------------------------------------------------------------*/ + +static const float P = 0.5; + +/*! + * \brief Maximum level of a node, i.e. maximum number of skip list levels. + */ +static const int MAX_LEVEL = 6; + +/*----------------------------------------------------------------------------*/ +/* Private functions */ +/*----------------------------------------------------------------------------*/ +/*! + * \brief Generates random real number between 0 and 1. + */ +static float frand() +{ + unsigned seed = (unsigned)time(0); + return (float) rand_r(&seed) / RAND_MAX; +} + +/*----------------------------------------------------------------------------*/ +/*! + * \brief Returns random level between 0 and MAX_LEVEL. + */ +static int skip_random_level() +{ + static int first = 1; + int lvl = 0; + + if (first) { + first = 0; + } + + while (frand() < P && lvl < MAX_LEVEL) { + lvl++; + } + + return lvl; +} + +/*----------------------------------------------------------------------------*/ +/*! + * \brief Creates a new skip list node with the given key and value. + * + * \param level Level of the skip list node. + * \param key Key of the new node. + * \param value Value to be stored in the node. + * + * \return Pointer to the newly created node or NULL if not successful. + */ +static skip_node_t *skip_make_node(int level, void *key, void *value) +{ + skip_node_t *sn = (skip_node_t *)malloc(sizeof(skip_node_t)); + if (sn == NULL) { + ERR_ALLOC_FAILED; + return NULL; + } + + sn->forward = (skip_node_t **)calloc(level + 1, sizeof(skip_node_t *)); + if (sn->forward == NULL) { + ERR_ALLOC_FAILED; + free(sn); + return NULL; + } + sn->key = key; + sn->value = value; + return sn; +} + +/*----------------------------------------------------------------------------*/ +/*! + * \brief Properly deallocates the given skip list node, and optionally destroys + * its key and value. + * + * \param node Skip list node to be deleted. + * \param destroy_key Function for properly destroying the key. If set tu NULL, + * the object at which the key points will not be destroyed. + * \param destroy_value Function for properly destroying the key. If set tu + * NULL, the object at which the value points will not be + * destroyed. + */ +static void skip_delete_node(skip_node_t **node, void (*destroy_key)(void *), + void (*destroy_value)(void *)) +{ + if (destroy_key != NULL) { + destroy_key((*node)->key); + } + if (destroy_value != NULL) { + destroy_value((*node)->value); + } + + free((*node)->forward); + free(*node); + + node = NULL; +} + +/*----------------------------------------------------------------------------*/ +/* Public functions */ +/*----------------------------------------------------------------------------*/ + +skip_list_t *skip_create_list(int (*compare_keys)(void *, void *)) +{ + assert(compare_keys != NULL); + + skip_list_t *ss = (skip_list_t *)malloc(sizeof(skip_list_t)); + if (ss == NULL) { + ERR_ALLOC_FAILED; + return NULL; + } + + ss->head = skip_make_node(MAX_LEVEL, NULL, NULL); + if (ss->head == NULL) { + ERR_ALLOC_FAILED; + free(ss); + return NULL; + } + + ss->level = 0; + ss->compare_keys = compare_keys; + + return ss; +} + +/*----------------------------------------------------------------------------*/ + +void skip_destroy_list(skip_list_t **list, void (*destroy_key)(void *), + void (*destroy_value)(void *)) +{ + assert((*list) != NULL); + assert((*list)->head != NULL); + + skip_node_t *x; + + while ((*list)->head->forward[0] != NULL) { + x = (*list)->head->forward[0]; + for (int i = 0; i <= (*list)->level; i++) { + if ((*list)->head->forward[i] != x) { + break; + } + (*list)->head->forward[i] = x->forward[i]; + } + + // delete the item + skip_delete_node(&x, destroy_key, destroy_value); + + while ((*list)->level > 0 + && (*list)->head->forward[(*list)->level] == NULL) { + (*list)->level--; + } + } + + // free the head + skip_delete_node(&(*list)->head, NULL, NULL); + + free(*list); + *list = NULL; +} + +/*----------------------------------------------------------------------------*/ + +void *skip_find(const skip_list_t *list, void *key) +{ + assert(list != NULL); + assert(list->head != NULL); + assert(list->compare_keys != NULL); + + int i; + skip_node_t *x = list->head; + for (i = list->level; i >= 0; i--) { + while (x->forward[i] != NULL + && list->compare_keys(x->forward[i]->key, key) == -1) { + x = x->forward[i]; + } + } + x = x->forward[0]; + + if (x != NULL && list->compare_keys(x->key, key) == 0) { + return x->value; + } + return NULL; +} + +/*----------------------------------------------------------------------------*/ + +void *skip_find_less_or_equal(const skip_list_t *list, void *key) +{ + assert(list != NULL); + assert(list->head != NULL); + assert(list->compare_keys != NULL); + + int i; + skip_node_t *x = list->head; + for (i = list->level; i >= 0; i--) { + while (x->forward[i] != NULL + && list->compare_keys(x->forward[i]->key, key) <= 0) { + x = x->forward[i]; + } + } + + return x->value; +} + +/*----------------------------------------------------------------------------*/ + +int skip_insert(skip_list_t *list, void *key, void *value, + int (*merge_values)(void **, void **)) +{ + assert(list != NULL); + assert(list->head != NULL); + assert(list->compare_keys != NULL); + + int i; + skip_node_t *x = list->head; + skip_node_t *update[MAX_LEVEL + 1]; + memset(update, 0, MAX_LEVEL + 1); + + for (i = list->level; i >= 0; i--) { + while (x->forward[i] != NULL + && list->compare_keys(x->forward[i]->key, key) == -1) { + x = x->forward[i]; + } + update[i] = x; + } + x = x->forward[0]; + + if (x == NULL || list->compare_keys(x->key, key) != 0) { + int lvl = skip_random_level(); + + if (lvl > list->level) { + for (i = list->level + 1; i <= lvl; i++) { + update[i] = list->head; + } + list->level = lvl; + } + + x = skip_make_node(lvl, key, value); + if (x == NULL) { + ERR_ALLOC_FAILED; + return -1; + } + + for (i = 0; i <= lvl; i++) { + x->forward[i] = update[i]->forward[i]; + update[i]->forward[i] = x; + } + + return 0; + } else { // already in the list + if (merge_values != NULL) { // if merge function provided, merge + return (merge_values(&x->value, &value) == 0) ? 2 : -2; + } else { + return 1; + } + } +} + +/*----------------------------------------------------------------------------*/ + +int skip_remove(skip_list_t *list, void *key, void (*destroy_key)(void *), + void (*destroy_value)(void *)) +{ + assert(list != NULL); + assert(list->head != NULL); + assert(list->compare_keys != NULL); + + int i; + skip_node_t *x = list->head; + skip_node_t *update[MAX_LEVEL + 1]; + memset(update, 0, MAX_LEVEL + 1); + + for (i = list->level; i >= 0; i--) { + while (x->forward[i] != NULL + && list->compare_keys(x->forward[i]->key, key) == -1) { + x = x->forward[i]; + } + update[i] = x; + } + x = x->forward[0]; + + if (x != NULL && list->compare_keys(x->key, key) == 0) { + for (i = 0; i <= list->level; i++) { + if (update[i]->forward[i] != x) { + break; + } + update[i]->forward[i] = x->forward[i]; + } + + // delete the item + skip_delete_node(&x, destroy_key, destroy_value); + + while (list->level > 0 + && list->head->forward[list->level] == NULL) { + list->level--; + } + return 0; + } else { + return -1; + } +} + +/*----------------------------------------------------------------------------*/ + +int skip_is_empty(const skip_list_t *list) +{ + if (!list) { + return 1; + } + + return (list->head->forward[0] == NULL); +} + +/*----------------------------------------------------------------------------*/ + +const skip_node_t *skip_first(const skip_list_t *list) +{ + if (!list) { + return NULL; + } + + return list->head->forward[0]; +} + +/*----------------------------------------------------------------------------*/ + +const skip_node_t *skip_next(const skip_node_t *node) +{ + return node->forward[0]; +} + +/*----------------------------------------------------------------------------*/ + +void skip_print_list(const skip_list_t *list, + void (*print_item)(void *, void *)) +{ + assert(list != NULL); + assert(list->head != NULL); + assert(list->compare_keys != NULL); + assert(print_item != NULL); + + skip_node_t *x = list->head->forward[0]; + while (x != NULL) { + print_item(x->key, x->value); + x = x->forward[0]; + } +} + +/*----------------------------------------------------------------------------*/ + +skip_list_t *skip_copy_list(const skip_list_t *list) +{ + skip_list_t *ss = (skip_list_t *)malloc(sizeof(skip_list_t)); + if (ss == NULL) { + ERR_ALLOC_FAILED; + return NULL; + } + + ss->head = skip_make_node(list->level, NULL, NULL); + if (ss->head == NULL) { + ERR_ALLOC_FAILED; + free(ss); + return NULL; + } + + ss->level = list->level; + ss->compare_keys = list->compare_keys; + + skip_node_t *x = list->head->forward[0]; + skip_node_t *prev = list->head; + skip_node_t *new_prev = ss->head; + while (x != NULL) { + //print_item(x->key, x->value); + + // create new node + skip_node_t *n = skip_make_node(list->level, x->key, x->value); + if (n == NULL) { + skip_destroy_list(&ss, NULL, NULL); + return NULL; + } + // set forward pointers from the previous node + for (int i = 0; i <= list->level; ++i) { + if (prev->forward[i] == x) { + new_prev->forward[i] = n; + } + } + + prev = x; + x = x->forward[0]; + new_prev = n; + } + + return ss; +} diff --git a/src/common/skip-list.h b/src/common/skip-list.h new file mode 100644 index 0000000..784f366 --- /dev/null +++ b/src/common/skip-list.h @@ -0,0 +1,215 @@ +/*! + * \file skip-list.h + * + * \author Copyright (c) 2010 the authors listed at the following URL, and/or + * the authors of referenced articles or incorporated external code: + * http://en.literateprograms.org/Skip_list_(C)?action=history&offset=20080313195128 + * \author Lubos Slovak <lubos.slovak@nic.cz> + * + * \brief Generic skip-list implementation. + * + * Original retrieved from http://en.literateprograms.org/Skip_list_(C)?oldid=12811 + * Modifications by Lubos Slovak, 2010 + * + * \addtogroup common_lib + * @{ + */ + +/* Copyright (c) 2010 the authors listed at the following URL, and/or +the authors of referenced articles or incorporated external code: +http://en.literateprograms.org/Skip_list_(C)?action=history&offset=20080313195128 + +Permission is hereby granted, free of charge, to any person obtaining +a copy of this software and associated documentation files (the +"Software"), to deal in the Software without restriction, including +without limitation the rights to use, copy, modify, merge, publish, +distribute, sublicense, and/or sell copies of the Software, and to +permit persons to whom the Software is furnished to do so, subject to +the following conditions: + +The above copyright notice and this permission notice shall be +included in all copies or substantial portions of the Software. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, +EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF +MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. +IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY +CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, +TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE +SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. + +Retrieved from: http://en.literateprograms.org/Skip_list_(C)?oldid=12811 +*/ + +#ifndef _KNOTD_COMMON_SKIP_LIST_H_ +#define _KNOTD_COMMON_SKIP_LIST_H_ + +/*----------------------------------------------------------------------------*/ +/*! + * \brief Skip list node. + */ +struct skip_node { + void *key; /*!< Key of the node. Used for ordering. */ + + void *value; /*!< Value stored in the node. */ + + /*! \brief Pointers to next item on various levels. */ + struct skip_node **forward; +}; + +typedef struct skip_node skip_node_t; + +/*! + * \brief Skip list. + * + * \todo Implement quasi-randomization. + */ +struct skip_list { + /*! \brief Head of the list (with no actual key and value stored). */ + skip_node_t *head; + + /*! \brief Actual maximum level of the list. */ + int level; + + /*! \brief Function for comparing two skip list item's keys. */ + int (*compare_keys)(void *, void *); +}; + +typedef struct skip_list skip_list_t; + +/*----------------------------------------------------------------------------*/ +/*! + * \brief Creates a new generic skip list. + * + * \param compare_keys Function for comparing the keys. + * \todo What should compare_keys exactly return? + * + * \return Pointer to the newly created skip list if successful. NULL otherwise. + */ +skip_list_t *skip_create_list(int (*compare_keys)(void *, void *)); + +/*! + * \brief Properly destroys the list, possibly also with the keys and values. + * + * \param list Skip list to be destroyed. + * \param destroy_key Function for properly destroying the key. If set tu NULL, + * the object at which the key points will not be destroyed. + * \param destroy_value Function for properly destroying the key. If set tu + * NULL, the object at which the value points will not be + * destroyed. + */ +void skip_destroy_list(skip_list_t **list, void (*destroy_key)(void *), + void (*destroy_value)(void *)); + +/*! + * \brief Inserts a new key-value pair into the skip list. + * + * The \a merge_values function should merge the second value to the first + * value. It must not delete the first value. The second value also should not + * be deleted (as this is concern of the caller). + * + * \param list The skip list to insert to. + * \param key Key of the item to be inserted. Used for ordering. + * \param value Value of the item to be inserted. + * \param merge_values Function for merging the saved values. Optional. If set + * to NULL, the skip list will not merge values when + * attempting to insert item with key already present in the + * list. + * \todo What are the function parameters and what should it + * return as integer? + * + * \retval 0 If successful and the key was not yet present in the list. + * \retval 1 If the key was already present and the new value was ignored + * (because no merging function was provided). + * \retval 2 If successful, the key was already present and the values were + * merged. + * \retval -1 If an error occured and the key was not present in the list. + * \retval -2 If the key is already present in the list and merging was + * unsuccessful. + */ +int skip_insert(skip_list_t *list, void *key, void *value, + int (*merge_values)(void **, void **)); + +/*! + * \brief Removes an item with the given key from the list and optionally + * deletes the item's key and value. + * + * \param list Skip list to delete from. + * \param key Key of the item to be deleted. + * \param destroy_key Function for properly destroying the key. If set tu NULL, + * the object at which the key points will not be destroyed. + * \param destroy_value Function for properly destroying the key. If set tu + * NULL, the object at which the value points will not be + * destroyed. + * + * \retval 0 If successful. + * \retval -1 If the item was not present in the list. + */ +int skip_remove(skip_list_t *list, void *key, void (*destroy_key)(void *), + void (*destroy_value)(void *)); + +/*! + * \brief Tries to find item with the given key in the list. + * + * \param list Skip list to search in. + * \param key Key of the item to be found. + * + * \return Value stored in the item with key \a key, or NULL if the key was not + * found. + */ +void *skip_find(const skip_list_t *list, void *key); + +/*! + * \brief Returns item with largest key smaller or equal than \a key. + * + * \param list Skip list to search in. + * \param key Key of the item to be found. + * + * \return Value stored in the item with largest key smaller or equal than \a + * key, or NULL if the key was not found. + */ +void *skip_find_less_or_equal(const skip_list_t *list, void *key); + +/*! + * \brief Checks if the skip list is empty. + * + * \param list Skip list to check. + * + * \retval 1 if empty. + * \retval 0 if non-empty. + */ +int skip_is_empty(const skip_list_t *list); + +/*! + * \brief Returns the first item in the skip list. + */ +const skip_node_t *skip_first(const skip_list_t *list); + +/*! + * \brief Returns the next item in the skip list. + */ +const skip_node_t *skip_next(const skip_node_t *node); + +/*! + * \brief Prints the whole list using the given print function. + * + * \param list Skip list to be printed. + * \param print_item Function for printing the key-value pair. + */ +void skip_print_list(const skip_list_t *list, + void (*print_item)(void *, void *)); + +/*! + * \brief Copies the skip list. + * + * \param list Skip list to be copied. + * + * \return Copy of \a list. + * + * \todo Test!!! + */ +skip_list_t *skip_copy_list(const skip_list_t *list); + +#endif /* _KNOTD_COMMON_SKIP_LIST_H_ */ + +/*! @} */ diff --git a/src/common/slab/alloc-common.h b/src/common/slab/alloc-common.h new file mode 100644 index 0000000..32878ab --- /dev/null +++ b/src/common/slab/alloc-common.h @@ -0,0 +1,61 @@ +/* Copyright (C) 2011 CZ.NIC, z.s.p.o. <knot-dns@labs.nic.cz> + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. + */ +/*! + * \file alloc-common.h + * + * \author Lubos Slovak <lubos.slovak@nic.cz> + * + * \brief Common macros for alloc. + * + * \addtogroup alloc + * @{ + */ + +#ifndef _KNOTD_COMMON_ALLOC_COMMON_H_ +#define _KNOTD_COMMON_ALLOC_COMMON_H_ + +#include <stdio.h> + +//#define MEM_DEBUG +//#define MEM_NOSLAB +//#define MEM_POISON +#define MEM_SLAB_CAP 5 // Cap slab_cache empty slab count (undefined = inf) +#define MEM_COLORING // Slab cache coloring +//#define MEM_SLAB_DEPOT // Use slab depot for slab caching (not thread-safe) + +/* Eliminate compiler warning with unused parameters. */ +#ifndef UNUSED +#define UNUSED(param) (void)(param) +#endif + +/* Optimisation macros. */ +#ifndef likely +#define likely(x) __builtin_expect((x),1) +#endif +#ifndef unlikely +#define unlikely(x) __builtin_expect((x),0) +#endif + +#ifdef MEM_DEBUG +#define dbg_mem(msg...) fprintf(stderr, msg) +#else +#define dbg_mem(msg...) +#endif + + +#endif /* _KNOTD_COMMON_ALLOC_COMMON_H_ */ + +/*! @} */ diff --git a/src/common/slab/malloc.c b/src/common/slab/malloc.c new file mode 100644 index 0000000..ec5a68d --- /dev/null +++ b/src/common/slab/malloc.c @@ -0,0 +1,60 @@ +/* Copyright (C) 2011 CZ.NIC, z.s.p.o. <knot-dns@labs.nic.cz> + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. + */ + +#include <config.h> +/* + * Skip unit if not debugging memory. + */ +#include <stdlib.h> +#include <stdio.h> +#include <string.h> +#include <sys/resource.h> + +#include "common/slab/alloc-common.h" + +#ifdef MEM_DEBUG +/* + * ((destructor)) attribute executes this function after main(). + * \see http://gcc.gnu.org/onlinedocs/gcc/Function-Attributes.html + */ +void __attribute__ ((destructor)) usage_dump() +#else +void usage_dump() +#endif +{ + /* Get resource usage. */ + struct rusage usage; + if (getrusage(RUSAGE_SELF, &usage) < 0) { + memset(&usage, 0, sizeof(struct rusage)); + } + + fprintf(stderr, "\nMemory statistics:"); + fprintf(stderr, "\n==================\n"); + + fprintf(stderr, "User time: %.03lf ms\nSystem time: %.03lf ms\n", + usage.ru_utime.tv_sec * (double) 1000.0 + + usage.ru_utime.tv_usec / (double)1000.0, + usage.ru_stime.tv_sec * (double) 1000.0 + + usage.ru_stime.tv_usec / (double)1000.0); + fprintf(stderr, "Major page faults: %lu (required I/O)\nMinor page faults: %lu\n", + usage.ru_majflt, usage.ru_minflt); + fprintf(stderr, "Number of swaps: %lu\n", + usage.ru_nswap); + fprintf(stderr, "Voluntary context switches: %lu\nInvoluntary context switches: %lu\n", + usage.ru_nvcsw, + usage.ru_nivcsw); + fprintf(stderr, "==================\n"); +} diff --git a/src/common/slab/malloc.h b/src/common/slab/malloc.h new file mode 100644 index 0000000..8ca9f58 --- /dev/null +++ b/src/common/slab/malloc.h @@ -0,0 +1,43 @@ +/* Copyright (C) 2011 CZ.NIC, z.s.p.o. <knot-dns@labs.nic.cz> + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. + */ +/*! + * \file malloc.h + * + * \author Marek Vavrusa <marek.vavrusa@nic.cz> + * + * \brief Memory allocation related functions. + * + * \addtogroup alloc + * @{ + */ + +#ifndef _KNOTD_COMMON_MALLOC_H_ +#define _KNOTD_COMMON_MALLOC_H_ + +#include <stdlib.h> + +/*! \brief Print usage statistics. + * + * \note This function has destructor attribute set if MEM_DEBUG is enabled. + * + * \warning Not all printed statistics are available on every OS, + * consult manual page for getrusage(2). + */ +void usage_dump(); + +#endif // _KNOTD_COMMON_MALLOC_H_ + +/*! @} */ diff --git a/src/common/slab/slab.c b/src/common/slab/slab.c new file mode 100644 index 0000000..ccdf7ca --- /dev/null +++ b/src/common/slab/slab.c @@ -0,0 +1,732 @@ +/* Copyright (C) 2011 CZ.NIC, z.s.p.o. <knot-dns@labs.nic.cz> + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. + */ + +#include <config.h> +#include <stdio.h> +#include <unistd.h> +#include <string.h> +#include <assert.h> +#include <stdlib.h> +#include <sys/mman.h> + +#include "common/slab/alloc-common.h" +#include "common/slab/slab.h" + +/* + * Magic constants. + */ +#define SLAB_MAGIC 0x51 /*!< "Sl" magic byte (slab type). */ +#define LOBJ_MAGIC 0x0B /*!< "Ob" magic byte (object type). */ +#define POISON_DWORD 0xdeadbeef /*!< Memory boundary guard magic. */ +#define SLAB_MINCOLOR 64 /*!< Minimum space reserved for cache coloring. */ +#define SLAB_HEADER sizeof(slab_t) /*!< Slab header size. */ +#define ALIGN_PTRSZ __attribute__ ((__aligned__(sizeof(void*)))) + +/*! \brief Fast cache id lookup table. + * + * Provides O(1) lookup. + * Filled with interesting values from default + * or on-demand. + */ +unsigned ALIGN_PTRSZ SLAB_CACHE_LUT[SLAB_SIZE] = { + [24] = SLAB_GP_COUNT + 1, + [800] = SLAB_GP_COUNT + 2 +}; + +/*! \brief Find the next highest power of 2. */ +static inline unsigned get_next_pow2(unsigned v) +{ + // Next highest power of 2 + --v; + v |= v >> 1; v |= v >> 2; + v |= v >> 4; v |= v >> 8; + v |= v >> 16; + ++v; + + return v; +} + +/*! \brief Return binary logarithm of a number, which is a power of 2. */ +static inline unsigned fastlog2(unsigned v) +{ + // Works if we know the size is a power of 2 + register unsigned int r = (v & 0xAAAAAAAA) != 0; + r |= ((v & 0xFFFF0000) != 0) << 4; + r |= ((v & 0xFF00FF00) != 0) << 3; + r |= ((v & 0xF0F0F0F0) != 0) << 2; + r |= ((v & 0xCCCCCCCC) != 0) << 1; + return r; +} + +/*! + * \brief Fast hashing function. + * + * Finds the next highest power of 2 and returns binary logarithm. + * Values are stored in LUT cache for future access. + */ +static unsigned slab_cache_id(unsigned size) +{ + // Assert cache id of the smallest bufsize is 0 + if(size <= SLAB_MIN_BUFLEN) { + return 0; + } + + // Check LUT + unsigned id = 0; + if ((id = SLAB_CACHE_LUT[size])) { + return id; + } else { + + // Compute binary logarithm + // Next highest power of 2 + id = fastlog2(get_next_pow2(size)); + + // Shift cacheid of SLAB_MIN_BUFLEN to 0 + id -= SLAB_EXP_OFFSET; + + // Store + SLAB_CACHE_LUT[size] = id; + } + + return id; +} + +/* + * Slab run-time constants. + */ + +size_t SLAB_MASK = 0; /*!< \brief Slab address mask (for computing offsets). */ +static unsigned SLAB_LOGSIZE = 0; /*!< \brief Binary logarithm of slab size. */ + +/*! + * Depot is a caching sub-allocator of slabs. + * It mitigates performance impact of sequentially allocating and freeing + * from a slab with just a few slab items by caching N slabs before returning + * them to the system. + * + * \todo With wider use, locking or RCU will be necessary. + */ +#ifdef MEM_SLAB_DEPOT +static slab_depot_t _depot_g; /*! \brief Global slab depot. */ +#endif // MEM_SLAB_DEPOT + +/*! + * \brief Allocate a slab of given bufsize from depot. + * + * \retval Reserved memory for slab on success. + * \retval NULL on errors. + */ +static void* slab_depot_alloc(size_t bufsize) +{ + void *page = 0; +#ifdef MEM_SLAB_DEPOT + if (_depot_g.available) { + for (int i = _depot_g.available - 1; i > -1 ; --i) { + if(_depot_g.cache[i]->bufsize == bufsize) { + page = _depot_g.cache[i]; + _depot_g.cache[i] = _depot_g.cache[--_depot_g.available]; + return page; + } + } + page = _depot_g.cache[--_depot_g.available]; + } else { + if(posix_memalign(&page, SLAB_SIZE, SLAB_SIZE) == 0) { + ((slab_t*)page)->bufsize = 0; + } else { + page = 0; + } + + } +#else // MEM_SLAB_DEPOT + if(posix_memalign(&page, SLAB_SIZE, SLAB_SIZE) == 0) { + ((slab_t*)page)->bufsize = 0; + } else { + page = 0; + } +#endif // MEM_SLAB_DEPOT + + return page; +} + +/*! + * \brief Return a slab to the depot. + * + * \note If the depot is full, slab gets immediately freed. + */ +static inline void slab_depot_free(void* slab) +{ +#ifdef MEM_SLAB_DEPOT + if (_depot_g.available < SLAB_DEPOT_SIZE) { + _depot_g.cache[_depot_g.available++] = slab; + } else { + free(slab); + } +#else // MEM_SLAB_DEPOT + free(slab); +#endif // MEM_SLAB_DEPOT +} + +/*! \brief Initialize slab depot. */ +static void slab_depot_init() +{ +#ifdef MEM_SLAB_DEPOT + _depot_g.available = 0; +#endif // MEM_SLAB_DEPOT +} + +/*! \brief Destroy slab depot. */ +static void slab_depot_destroy() +{ +#ifdef MEM_SLAB_DEPOT + while(_depot_g.available) { + free(_depot_g.cache[--_depot_g.available]); + } +#endif // MEM_SLAB_DEPOT +} + +/* + * Initializers. + */ + +/*! \brief Initializes slab subsystem (it is called automatically). */ +void __attribute__ ((constructor)) slab_init() +{ + // Fetch page size + SLAB_LOGSIZE = fastlog2(SLAB_SIZE); + + // Compute slab page mask + SLAB_MASK = 0; + for (int i = 0; i < SLAB_LOGSIZE; ++i) { + SLAB_MASK |= 1 << i; + } + SLAB_MASK = ~SLAB_MASK; + + // Initialize depot + slab_depot_init(); +} + +/*! \brief Deinitializes slab subsystem (it is called automatically). */ +void __attribute__ ((destructor)) slab_deinit() +{ + // Deinitialize global allocator + if (SLAB_LOGSIZE) { + slab_depot_destroy(); + SLAB_LOGSIZE = SLAB_MASK = 0; + } +} + +/* + * Cache helper functions. + */ + +/* \notice Not used right now. +static void slab_dump(slab_t* slab) { + + printf("%s: buffers (bufsize=%zuB, %u/%u free): \n", + __func__, slab->cache->bufsize, slab->bufs_free, + slab->bufs_count); + + void** buf = slab->head; + int i = 0, n = 0; + while(buf != 0) { + size_t diff = (size_t)((char*)buf - (char*)slab->base); + printf("-> %lu", diff / slab->cache->bufsize); + buf = (void**)(*buf); + if (++i == 10) { + printf("\n"); + i = 0; + } + ++n; + } + + printf("\n"); +} +*/ + +/*! + * \brief Free all slabs from a slab cache. + * \return Number of freed slabs. + */ +static inline int slab_cache_free_slabs(slab_t* slab) +{ + int count = 0; + while (slab) { + slab_t* next = slab->next; + slab_destroy(&slab); + ++count; + slab = next; + + } + return count; +} + +/* + * Slab helper functions. + */ + +/*! \brief Return number of slabs in a linked list. */ +static inline unsigned slab_list_walk(slab_t* slab) +{ + unsigned count = 0; + while(slab) { + slab = slab->next; + ++count; + } + return count; +} + +/*! \brief Remove slab from a linked list. */ +static void slab_list_remove(slab_t* slab) +{ + // Disconnect from list + if (slab->prev) { + slab->prev->next = slab->next; + } + if(slab->next) { + slab->next->prev = slab->prev; + } + + // Disconnect from cache + slab_cache_t* cache = slab->cache; + { + if (cache->slabs_free == slab) { + cache->slabs_free = slab->next; + } else if (cache->slabs_full == slab) { + cache->slabs_full = slab->next; + } + } +} + +/*! \brief Insert slab into a linked list. */ +static void slab_list_insert(slab_t** list, slab_t* item) +{ + // If list exists, push to the top + item->prev = 0; + item->next = *list; + if(*list) { + (*list)->prev = item; + } + *list = item; +} + +/*! \brief Move slab from one linked list to another. */ +static inline void slab_list_move(slab_t** target, slab_t* slab) +{ + slab_list_remove(slab); + slab_list_insert(target, slab); +} + +/* + * API functions. + */ + +slab_t* slab_create(slab_cache_t* cache) +{ + const size_t size = SLAB_SIZE; + + slab_t* slab = slab_depot_alloc(cache->bufsize); + + if (unlikely(slab < 0)) { + dbg_mem("%s: failed to allocate aligned memory block\n", + __func__); + return 0; + } + + /* Initialize slab. */ + slab->magic = SLAB_MAGIC; + slab->cache = cache; + slab_list_insert(&cache->slabs_free, slab); +#ifdef MEM_SLAB_CAP + ++cache->empty; +#endif + + /* Already initialized? */ + if (slab->bufsize == cache->bufsize) { + return slab; + } else { + slab->bufsize = cache->bufsize; + } + + /* Ensure the item size can hold at least a size of ptr. */ + size_t item_size = slab->bufsize; + if (unlikely(item_size < SLAB_MIN_BUFLEN)) { + item_size = SLAB_MIN_BUFLEN; + } + + /* Ensure at least some space for coloring */ + size_t data_size = size - sizeof(slab_t); +#ifdef MEM_COLORING + size_t free_space = data_size % item_size; + if (unlikely(free_space < SLAB_MINCOLOR)) { + free_space = SLAB_MINCOLOR; + } + + + /// unsigned short color = __sync_fetch_and_add(&cache->color, 1); + unsigned short color = (cache->color += sizeof(void*)); + color = color % free_space; +#else + const unsigned short color = 0; +#endif + + /* Calculate useable data size */ + data_size -= color; + slab->bufs_count = data_size / item_size; + slab->bufs_free = slab->bufs_count; + + // Save first item as next free + slab->base = (char*)slab + sizeof(slab_t) + color; + slab->head = (void**)slab->base; + + // Create freelist, skip last member, which is set to NULL + char* item = (char*)slab->head; + for(unsigned i = 0; i < slab->bufs_count - 1; ++i) { + *((void**)item) = item + item_size; + item += item_size; + } + + // Set last buf to NULL (tail) + *((void**)item) = (void*)0; + + // Ensure the last item has a NULL next + dbg_mem("%s: created slab (%p, %p) (%zu B)\n", + __func__, slab, slab + size, size); + return slab; +} + +void slab_destroy(slab_t** slab) +{ + /* Disconnect from the list */ + slab_list_remove(*slab); + + /* Free slab */ + slab_depot_free(*slab); + + /* Invalidate pointer. */ + dbg_mem("%s: deleted slab %p\n", __func__, *slab); + *slab = 0; +} + +void* slab_alloc(slab_t* slab) +{ + // Fetch first free item + void **item = 0; + { + if((item = slab->head)) { + slab->head = (void**)*item; + --slab->bufs_free; + } else { + // No more free items + return 0; + } + } + +#ifdef MEM_DEBUG + // Increment statistics + __sync_add_and_fetch(&slab->cache->stat_allocs, 1); +#endif + + // Move to full? + if (unlikely(slab->bufs_free == 0)) { + slab_list_move(&slab->cache->slabs_full, slab); + } else { +#ifdef MEM_SLAB_CAP + // Mark not empty? + if (unlikely(slab->bufs_free == slab->bufs_count - 1)) { + --slab->cache->empty; + } +#endif + } + + return item; +} + +void slab_free(void* ptr) +{ + // Null pointer check + if (unlikely(!ptr)) { + return; + } + + // Get slab start address + slab_t* slab = slab_from_ptr(ptr); + assert(slab); + + // Check if it exists in directory + if (slab->magic == SLAB_MAGIC) { + + // Return buf to slab + *((void**)ptr) = (void*)slab->head; + slab->head = (void**)ptr; + ++slab->bufs_free; + +#ifdef MEM_DEBUG + // Increment statistics + __sync_add_and_fetch(&slab->cache->stat_frees, 1); +#endif + + // Return to partial + if(unlikely(slab->bufs_free == 1)) { + slab_list_move(&slab->cache->slabs_free, slab); + } else { +#ifdef MEM_SLAB_CAP + // Recycle if empty + if(unlikely(slab_isempty(slab))) { + if(slab->cache->empty == MEM_SLAB_CAP) { + slab_destroy(&slab); + } else { + ++slab->cache->empty; + } + } +#endif + } + + } else { + + // Pointer is not a slab + // Presuming it's a large block + slab_obj_t* bs = (slab_obj_t*)ptr - 1; + +#ifdef MEM_POISON + // Remove memory barrier + mprotect(ptr + bs->size, sizeof(int), PROT_READ|PROT_WRITE); +#endif + + // Unmap + dbg_mem("%s: unmapping large block of %zu bytes at %p\n", + __func__, bs->size, ptr); + free(bs); + } +} + +int slab_cache_init(slab_cache_t* cache, size_t bufsize) +{ + if (unlikely(!bufsize)) { + return -1; + } + + cache->empty = 0; + cache->bufsize = bufsize; + cache->slabs_free = cache->slabs_full = 0; + cache->color = 0; + + /* Initialize stats */ + cache->stat_allocs = cache->stat_frees = 0; + + dbg_mem("%s: created cache of size %zu\n", + __func__, bufsize); + + return 0; +} + +void slab_cache_destroy(slab_cache_t* cache) { + + // Free slabs + unsigned free_s = slab_cache_free_slabs(cache->slabs_free); + unsigned full_s = slab_cache_free_slabs(cache->slabs_full); +#ifndef MEM_DEBUG + UNUSED(free_s); + UNUSED(full_s); +#else + dbg_mem("%s: %u empty/partial, %u full caches\n", + __func__, free_s, full_s); +#endif + + // Invalidate cache + cache->bufsize = 0; + cache->slabs_free = cache->slabs_full = 0; +} + +void* slab_cache_alloc(slab_cache_t* cache) +{ + slab_t* slab = cache->slabs_free; + if(!cache->slabs_free) { + slab = slab_create(cache); + if (slab == NULL) { + return NULL; + } + } + + + return slab_alloc(slab); +} + +int slab_cache_reap(slab_cache_t* cache) +{ + // For now, just free empty slabs + slab_t* slab = cache->slabs_free; + int count = 0; + while (slab) { + slab_t* next = slab->next; + if (slab_isempty(slab)) { + slab_destroy(&slab); + ++count; + } + slab = next; + + } + + cache->empty = 0; + return count; +} + +int slab_alloc_init(slab_alloc_t* alloc) +{ + // Invalidate + memset(alloc, 0, sizeof(slab_alloc_t)); + + // Initialize descriptors cache + slab_cache_init(&alloc->descriptors, sizeof(slab_cache_t)); + + return 0; +} + +void slab_alloc_destroy(slab_alloc_t* alloc) +{ + // Destroy all caches + for (unsigned i = 0; i < SLAB_CACHE_COUNT; ++i) { + if (alloc->caches[i] != 0) { + slab_cache_destroy(alloc->caches[i]); + } + } + + // Destroy cache for descriptors + slab_cache_destroy(&alloc->descriptors); +} + +void* slab_alloc_alloc(slab_alloc_t* alloc, size_t size) +{ + // Invalid size check + if (unlikely(!size)) { + return 0; + } + +#ifdef MEM_POISON + // Reserve memory for poison + size += sizeof(int); +#endif + // Directly map large block + if (unlikely(size > SLAB_SIZE/2)) { + + // Map block + size += sizeof(slab_obj_t); + slab_obj_t* p = 0; + p = malloc(size); + + dbg_mem("%s: mapping large block of %zu bytes at %p\n", + __func__, size, p + 1); + + /* Initialize. */ + p->magic = LOBJ_MAGIC; + p->size = size - sizeof(slab_obj_t); + +#ifdef MEM_POISON + // Reduce real size + p->size -= sizeof(int); + + // Memory barrier + int* pb = (int*)((char*)p + size - sizeof(int)); + *pb = POISON_DWORD; + mprotect(pb, sizeof(int), PROT_NONE); +#endif + + return p + 1; + } + + // Get cache id from size + unsigned cache_id = slab_cache_id(size); + + // Check if associated cache exists + if (unlikely(alloc->caches[cache_id] == 0)) { + + // Assert minimum cache size + if (unlikely(size < SLAB_MIN_BUFLEN)) { + size = SLAB_MIN_BUFLEN; + } + + // Calculate cache bufsize + size_t bufsize = size; + if (cache_id < SLAB_GP_COUNT) { + bufsize = get_next_pow2(size); + } + + // Create cache + dbg_mem("%s: creating cache of %zuB (req. %zuB) (id=%u)\n", + __func__, bufsize, size, cache_id); + + slab_cache_t* cache = slab_cache_alloc(&alloc->descriptors); + slab_cache_init(cache, bufsize); + alloc->caches[cache_id] = cache; + } + + // Allocate from cache + void* mem = slab_cache_alloc(alloc->caches[cache_id]); + +#ifdef MEM_POISON + // Memory barrier + /*! \todo Broken, need to store the barrier byte size. */ + //int* pb = (int*)((char*)mem + size - sizeof(int)); + //mprotect(pb, sizeof(int), PROT_NONE); +#endif + return mem; +} + +void *slab_alloc_realloc(slab_alloc_t* alloc, void *ptr, size_t size) +{ + // realloc(0) equals to free(ptr) + if (!size) { + slab_free(ptr); + return 0; + } + + // Allocate new buf + void *nptr = slab_alloc_alloc(alloc, size); + assert(nptr); + + // Copy memory if present + if (ptr) { + slab_t* slab = slab_from_ptr(ptr); + memcpy(nptr, ptr, slab->cache->bufsize); + + // Free old buf + slab_free(ptr); + } + + return nptr; +} + +void slab_alloc_stats(slab_alloc_t* alloc) +{ +#ifdef MEM_DEBUG + printf("Cache usage:\n"); + for (int i = 0; i < SLAB_CACHE_COUNT; ++i) { + + if (!alloc->caches[i]) + continue; + + slab_cache_t* cache = alloc->caches[i]; + unsigned free_s = slab_list_walk(cache->slabs_free); + unsigned full_s = slab_list_walk(cache->slabs_full); + printf("%4zu: allocs=%lu frees=%lu " + "(%u empty+partial, %u full)\n", + cache->bufsize, cache->stat_allocs, + cache->stat_frees, free_s, full_s); + } +#else + printf("Cache usage: not available, enable MEM_DEBUG and recompile.\n"); +#endif +} + diff --git a/src/common/slab/slab.h b/src/common/slab/slab.h new file mode 100644 index 0000000..d64188e --- /dev/null +++ b/src/common/slab/slab.h @@ -0,0 +1,353 @@ +/* Copyright (C) 2011 CZ.NIC, z.s.p.o. <knot-dns@labs.nic.cz> + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. + */ +/*! + * \file slab.h + * + * \author Marek Vavrusa <marek.vavusa@nic.cz> + * + * \brief SLAB allocator. + * + * SLAB cache works with either custom SLAB sizes and + * Next-Highest-Power-Of-2 sizes. + * + * Slab size is a multiple of PAGE_SIZE and uses + * system allocator for larger blocks. + * + * Allocated SLABs are PAGE_SIZE aligned for a fast O(1) + * address-from-item lookup. This results in nearly none memory + * overhead for a very small blocks (<64B), but it requires the + * underlying allocator to be effective in allocating page size aligned memory + * as well. The major disadvantage is that each Slab must be aligned to it's + * size as opposed to boundary tags. + * + * Slab implements simple coloring mechanism to improve + * cache line utilisation. + * + * \ref SLAB_SIZE is a fixed size of a slab. As a rule of thumb, the slab is + * effective when the maximum allocated block size is below 1/4 of a SLAB_SIZE. + * f.e. 16kB SLAB is most effective up to 4kB block size. + * + * \ref MEM_POISON flag enables checking read/writes after the allocated memory + * and segmentation fault. This poses a significant time and space overhead. + * Enable only when debugging. + * + * \ref MEM_SLAB_CAP defines a maximum limit of a number of empty slabs that a cache + * can keep at a time. This results in a slight performance regression, + * but actively recycles unuse memory. + * + * \ref MEM_DEPOT_COUNT defines how many recycled slabs will be cached for a later + * use instead of returning them immediately to the OS. This significantly + * reduces a number of syscalls in some cases. + * f.e. 16 means 16 * SLAB_SIZE cache, for 16kB slabs = 256kB cache + * + * \ref MEM_COLORING enables simple cache coloring. This is generally a useful + * feature since all slabs are page size aligned and + * (depending on architecture) this slightly improves performance + * and cacheline usage at the cost of a minimum of 64 bytes per slab of + * overhead. Undefine MEM_COLORING in common.h to disable coloring. + * + * Optimal usage for a specific behavior (similar allocation sizes): + * \code + * slab_cache_t cache; + * slab_cache_init(&cache, N); // Initialize, N means cache chunk size + * ... + * void* mem = slab_cache_alloc(&cache); // Allocate N bytes + * ... + * slab_free(mem); // Recycle memory + * ... + * slab_cache_destroy(&cache); // Deinitialize cache + * \endcode + * + * + * \todo Allocate slab headers elsewhere and use just first sizeof(void*) bytes + * in each slab as a pointer to slab header. This could improve the + * performance. + * + * \note Slab allocation is not thread safe for performance reasons. + * + * \addtogroup alloc + * @{ + */ + +#ifndef _KNOTD_COMMON_SLAB_H_ +#define _KNOTD_COMMON_SLAB_H_ + +#include <pthread.h> +#include <stdint.h> + +/* Constants. */ +#define SLAB_SIZE (4096*4) //!< Slab size (16K blocks) +#define SLAB_MIN_BUFLEN 8 //!< Minimal allocation block size is 8B. +#define SLAB_EXP_OFFSET 3 //!< Minimal allocation size is 8B = 2^3, exp is 3. +#define SLAB_GP_COUNT 10 //!< General-purpose caches count. +#define SLAB_US_COUNT 10 //!< User-specified caches count. +#define SLAB_DEPOT_SIZE 16 //!< N slabs cached = N*SLAB_SIZE kB cap +#define SLAB_CACHE_COUNT (SLAB_GP_COUNT + SLAB_US_COUNT) //!< Slab cache count. +struct slab_cache_t; + +/* Macros. */ + +/*! \brief Return slab base address from pointer. */ +#define slab_from_ptr(p) ((void*)((size_t)(p) & SLAB_MASK)) + +/*! \brief Return true if slab is empty. */ +#define slab_isempty(s) ((s)->bufs_free == (s)->bufs_count) + +/*! + * \brief Slab descriptor. + * + * Slab is a block of memory used for an allocation of + * smaller objects (bufs) later on. + * Each slab is currently aligned to page size to easily + * determine slab address from buf pointer. + * + * \warning Do not use slab_t directly as it cannot grow, see slab_cache_t. + */ +typedef struct slab_t { + char magic; /*!< Identifies memory block type. */ + unsigned short bufsize; /*!< Slab bufsize. */ + struct slab_cache_t *cache; /*!< Owner cache. */ + struct slab_t *prev, *next; /*!< Neighbours in slab lists. */ + unsigned bufs_count; /*!< Number of bufs in slab. */ + unsigned bufs_free; /*!< Number of available bufs. */ + void **head; /*!< Pointer to first available buf. */ + char* base; /*!< Base address for bufs. */ +} slab_t; + +/*! + * \brief Slab depot. + * + * To mitigate slab initialization costs, depot keeps a finite number of + * stacked slabs before returning them to the system. + */ +typedef struct slab_depot_t { + size_t available; /*!< Number of available pages. */ + slab_t* cache[SLAB_DEPOT_SIZE]; /*!< Stack of free slabs. */ +} slab_depot_t; + +/*! + * \brief Large object descriptor. + * + * Large object differs from slab with magic byte and + * contains object size. + * + * Magic needs to be first to overlap with slab_t magic byte. + */ +typedef struct slab_obj_t { + char magic; /*!< Identifies memory block type. */ + size_t size; /*!< Object size. */ +} slab_obj_t; + +/*! + * \brief Slab cache descriptor. + * + * Slab cache is a list of 0..n slabs with the same buf size. + * It is responsible for slab state keeping. + * + * Once a slab is created, it is moved to free list. + * When it is full, it is moved to full list. + * Once a buf from full slab is freed, the slab is moved to + * free list again (there may be some hysteresis for mitigating + * a sequential alloc/free). + * + * Allocation of new slabs is on-demand, empty slabs are reused if possible. + * + * \note Slab implementation is different from Bonwick (Usenix 2001) + * http://www.usenix.org/event/usenix01/bonwick.html + * as it doesn't feature empty and partial list. + * This is due to fact, that user space allocator rarely + * needs to count free slabs. There is no way the OS could + * notify the application, that the memory is scarce. + * A slight performance increased is measured in benchmark. + * + * \note Statistics are only available if MEM_DEBUG is enabled. + */ +typedef struct slab_cache_t { + unsigned short color; /*!< Current cache color. */ + unsigned short empty; /*!< Number of empty slabs. */ + size_t bufsize; /*!< Cache object (buf) size. */ + slab_t *slabs_free; /*!< List of free slabs. */ + slab_t *slabs_full; /*!< List of full slabs. */ + + /* Statistics. */ + unsigned long stat_allocs; /*!< Allocation count. */ + unsigned long stat_frees; /*!< Free count. */ +} slab_cache_t; + +/*! + * \brief Slab allocator descriptor. + * + * \note For a number of slab caches, consult SLAB_GP_COUNT + * and a number of specific records in SLAB_CACHE_LUT lookup table. + * + * \warning It is currently not advised to use this general purpose allocator, + * as it usually doesn't yield an expected performance for higher + * bookkeeping costs and it also depends on the allocation behavior + * as well. Look for slab_cache for a specialized use in most cases. + */ +typedef struct slab_alloc_t { + slab_cache_t descriptors; /*!< Slab cache for cache descriptors. */ + slab_cache_t* caches[SLAB_CACHE_COUNT]; /*!< Number of slab caches. */ +} slab_alloc_t; + +/*! + * \brief Create a slab of predefined size. + * + * At the moment, slabs are equal to page size and page size aligned. + * This enables quick and efficient buf to slab lookup by pointer arithmetic. + * + * Slab uses simple coloring scheme with and the memory block is always + * sizeof(void*) aligned. + * + * \param cache Parent cache. + * \retval Slab instance on success. + * \retval NULL on error. + */ +slab_t* slab_create(slab_cache_t* cache); + +/*! + * \brief Destroy slab instance. + * + * Slab is disconnected from any list and freed. + * Dereferenced slab parameter is set to NULL. + * + * \param slab Pointer to given slab. + */ +void slab_destroy(slab_t** slab); + +/*! + * \brief Allocate a buf from slab. + * + * Returns a pointer to allocated memory or NULL on error. + * + * \param slab Given slab instance. + * \retval Pointer to allocated memory. + * \retval NULL on error. + */ +void* slab_alloc(slab_t* slab); + +/*! + * \brief Recycle memory. + * + * Given memory is returned to owner slab. + * Memory content may be rewritten. + * + * \param ptr Returned memory. + */ +void slab_free(void* ptr); + +/*! + * \brief Create a slab cache. + * + * Create a slab cache with no allocated slabs. + * Slabs are allocated on-demand. + * + * \param cache Pointer to uninitialized cache. + * \param bufsize Single item size for later allocs. + * \retval 0 on success. + * \retval -1 on error; + */ +int slab_cache_init(slab_cache_t* cache, size_t bufsize); + +/*! + * \brief Destroy a slab cache. + * + * Destroy a slab cache and all associated slabs. + * + * \param cache Pointer to slab cache. + */ +void slab_cache_destroy(slab_cache_t* cache); + +/*! + * \brief Allocate from the cache. + * + * It tries to use partially free caches first, + * empty caches second and allocates a new cache + * as a last resort. + * + * \param cache Given slab cache. + * \retval Pointer to allocated memory. + * \retval NULL on error. + */ +void* slab_cache_alloc(slab_cache_t* cache); + +/*! + * \brief Free unused slabs from cache. + * + * \param cache Given slab cache. + * \return Number of freed slabs. + */ +int slab_cache_reap(slab_cache_t* cache); + +/*! + * \brief Create a general purpose slab allocator. + * + * \note Please consult struct slab_alloc_t for performance hints. + * + * \retval 0 on success. + * \retval -1 on error. + */ +int slab_alloc_init(slab_alloc_t* alloc); + +/*! + * \brief Delete slab allocator. + * + * This destroys all associated caches and frees memory. + * + * \param alloc Given allocator instance. + */ +void slab_alloc_destroy(slab_alloc_t* alloc); + +/*! + * \brief Allocate a block of memory. + * + * Returns a block of allocated memory. + * + * \note At least SLAB_MIN_BUFSIZE bytes is allocated. + * + * \note Please consult struct slab_alloc_t for performance hints. + * + * \param alloc Allocator instance. + * \param size Requested block size. + * \retval Pointer to allocated memory. + * \retval NULL on error. + */ +void* slab_alloc_alloc(slab_alloc_t* alloc, size_t size); + +/*! + * \brief Reallocate data from one slab to another. + * + * \param alloc Allocator instance. + * \param ptr Pointer to allocated memory. + * \param size Requested memory block size. + * \retval Pointer to newly allocated memory. + * \retval NULL on error. + * + * \todo Realloc could be probably implement more effectively. + */ +void *slab_alloc_realloc(slab_alloc_t* alloc, void *ptr, size_t size); + +/*! + * + * \brief Dump allocator stats. + * + * \param alloc Allocator instance. + */ +void slab_alloc_stats(slab_alloc_t* alloc); + +#endif /* _KNOTD_COMMON_SLAB_H_ */ + +/*! @} */ diff --git a/src/common/sockaddr.c b/src/common/sockaddr.c new file mode 100644 index 0000000..cd3a4b9 --- /dev/null +++ b/src/common/sockaddr.c @@ -0,0 +1,174 @@ +/* Copyright (C) 2011 CZ.NIC, z.s.p.o. <knot-dns@labs.nic.cz> + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. + */ + +#include <stdlib.h> +#include <string.h> +#include <sys/types.h> +#include <sys/socket.h> +#include <arpa/inet.h> + +#include "common/sockaddr.h" + +int sockaddr_init(sockaddr_t *addr, int af) +{ + /* Reset pointer. */ + memset(addr, 0, sizeof(sockaddr_t)); + addr->family = -1; + + /* Initialize address size. */ + switch(af) { + case AF_INET: + addr->len = sizeof(struct sockaddr_in); + break; +#ifndef DISABLE_IPV6 + case AF_INET6: + addr->len = sizeof(struct sockaddr_in6); + break; +#endif + default: + return -1; + } + + /* Update pointer. */ + addr->family = af; + return sockaddr_update(addr); +} + +int sockaddr_update(sockaddr_t *addr) +{ + /* Update internal pointer. */ + switch(addr->len) { + case sizeof(struct sockaddr_in): + addr->ptr = (struct sockaddr*)&addr->addr4; + break; +#ifndef DISABLE_IPV6 + case sizeof(struct sockaddr_in6): + addr->ptr = (struct sockaddr*)&addr->addr6; + break; +#endif + default: + return -1; + } + + return 0; +} + +int sockaddr_set(sockaddr_t *dst, int family, const char* addr, int port) +{ + if (!dst || !addr || port < 0) { + return -1; + } + + /* Initialize. */ + dst->family = -1; + dst->ptr = 0; + dst->len = 0; + sockaddr_init(dst, family); + + /* Initialize depending on address family. */ + void *paddr = 0; + switch(family) { + case AF_INET: + dst->addr4.sin_family = family; + dst->addr4.sin_port = htons(port); + paddr = &dst->addr4.sin_addr; + dst->addr4.sin_addr.s_addr = INADDR_ANY; + break; +#ifndef DISABLE_IPV6 + case AF_INET6: + dst->addr6.sin6_family = family; + dst->addr6.sin6_port = htons(port); + paddr = &dst->addr6.sin6_addr; + memcpy(&dst->addr6.sin6_addr, + &in6addr_any, sizeof(in6addr_any)); + break; +#endif + default: + return -1; + } + + /* Convert address. */ + return inet_pton(family, addr, paddr); +} + +int sockaddr_tostr(sockaddr_t *addr, char *dst, size_t size) +{ + if (!addr || !dst || size == 0) { + return -1; + } + + /* Minimum length. */ + size_t minlen = INET_ADDRSTRLEN; + + /* Check unsupported IPv6. */ +#ifdef DISABLE_IPV6 + if (addr->family == AF_INET6) { + return -1; + } +#else + minlen = INET6_ADDRSTRLEN; +#endif + + /* Check minimum length. */ + if (size < minlen) { + return -1; + } + + /* Convert. */ +#ifdef DISABLE_IPV6 + dst[0] = '\0'; +#else + /* Load IPv6 addr if default. */ + if (addr->family == AF_INET6) { + inet_ntop(addr->family, &addr->addr6.sin6_addr, + dst, size); + } +#endif + /* Load IPv4 if set. */ + if (addr->family == AF_INET) { + inet_ntop(addr->family, &addr->addr4.sin_addr, + dst, size); + } + + return 0; +} + +int sockaddr_portnum(sockaddr_t *addr) +{ + if (!addr) { + return -1; + } + + switch(addr->family) { + + /* IPv4 */ + case AF_INET: + return ntohs(addr->addr4.sin_port); + break; + + /* IPv6 */ +#ifndef DISABLE_IPV6 + case AF_INET6: + return ntohs(addr->addr6.sin6_port); + break; +#endif + + /* N/A */ + default: + return -1; + break; + } +} diff --git a/src/common/sockaddr.h b/src/common/sockaddr.h new file mode 100644 index 0000000..51ba779 --- /dev/null +++ b/src/common/sockaddr.h @@ -0,0 +1,120 @@ +/* Copyright (C) 2011 CZ.NIC, z.s.p.o. <knot-dns@labs.nic.cz> + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. + */ +/*! + * \file sockaddr.h + * + * \author Marek Vavrusa <marek.vavrusa@nic.cz> + * + * \brief Socket address abstraction layer. + * + * \addtogroup common_lib + * @{ + */ + +#ifndef _KNOTD_SOCKADDR_H_ +#define _KNOTD_SOCKADDR_H_ + +/* BSD IPv6 */ +#ifndef __POSIX_VISIBLE +#define __POSIX_VISIBLE = 200112 +#endif + +#include <netinet/in.h> +#include <arpa/inet.h> + +/*! \brief Universal socket address. */ +typedef struct sockaddr_t { + int family; /*!< Address family. */ + struct sockaddr* ptr; /*!< Pointer to used sockaddr. */ + socklen_t len; /*!< Length of used sockaddr. */ + union { + struct sockaddr_in addr4; /*!< IPv4 sockaddr. */ +#ifndef DISABLE_IPV6 + struct sockaddr_in6 addr6; /*!< IPv6 sockaddr. */ +#endif + }; +} sockaddr_t; + +/*! \brief Maximum address length in string format. */ +#ifdef DISABLE_IPV6 +#define SOCKADDR_STRLEN INET_ADDRSTRLEN +#else +#define SOCKADDR_STRLEN INET6_ADDRSTRLEN +#endif + +/*! + * \brief Initialize address structure. + * + * Members ptr and len will be initialized to correct address family. + * + * \param addr Socket address structure. + * \param af Requested address family. + * + * \retval 0 on success. + * \retval -1 on unsupported address family (probably INET6). + */ +int sockaddr_init(sockaddr_t *addr, int af); + +/*! + * \brief Update internal pointers according to length. + * + * \param addr Socket address structure. + * + * \retval 0 on success. + * \retval -1 on invalid size. + */ +int sockaddr_update(sockaddr_t *addr); + +/*! + * \brief Set address and port. + * + * \param dst Target address structure. + * \param family Address family. + * \param addr IP address in string format. + * \param port Port. + * + * \retval 0 if addr is not valid address in string format. + * \retval positive value in case of success. + * \retval -1 on error. + * \see inet_pton(3) + */ +int sockaddr_set(sockaddr_t *dst, int family, const char* addr, int port); + +/*! + * \brief Return string representation of socket address. + * + * \param addr Socket address structure. + * \param dst Destination for string representation. + * \param size Maximum number of written bytes. + * + * \retval 0 on success. + * \retval -1 on invalid parameters. + */ +int sockaddr_tostr(sockaddr_t *addr, char *dst, size_t size); + +/*! + * \brief Return port number from address. + * + * \param addr Socket address structure. + * + * \retval Port number on success. + * \retval -1 on errors. + */ +int sockaddr_portnum(sockaddr_t *addr); + +#endif /* _KNOTD_SOCKADDR_H_ */ + +/*! @} */ diff --git a/src/common/tree.h b/src/common/tree.h new file mode 100644 index 0000000..efea65b --- /dev/null +++ b/src/common/tree.h @@ -0,0 +1,268 @@ +/* tree.h -- AVL trees (in the spirit of BSD's 'queue.h') -*- C -*- */ + +/* Copyright (c) 2005 Ian Piumarta + * + * All rights reserved. + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the 'Software'), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, and/or sell copies of the + * Software, and to permit persons to whom the Software is furnished to do so, + * provided that the above copyright notice(s) and this permission notice appear + * in all copies of the Software and that both the above copyright notice(s) and + * this permission notice appear in supporting documentation. + * + * THE SOFTWARE IS PROVIDED 'AS IS'. USE ENTIRELY AT YOUR OWN RISK. + */ + +/* This file defines an AVL balanced binary tree [Georgii M. Adelson-Velskii and + * Evgenii M. Landis, 'An algorithm for the organization of information', + * Doklady Akademii Nauk SSSR, 146:263-266, 1962 (Russian). Also in Myron + * J. Ricci (trans.), Soviet Math, 3:1259-1263, 1962 (English)]. + * + * An AVL tree is headed by pointers to the root node and to a function defining + * the ordering relation between nodes. Each node contains an arbitrary payload + * plus three fields per tree entry: the depth of the subtree for which it forms + * the root and two pointers to child nodes (singly-linked for minimum space, at + * the expense of direct access to the parent node given a pointer to one of the + * children). The tree is rebalanced after every insertion or removal. The + * tree may be traversed in two directions: forward (in-order left-to-right) and + * reverse (in-order, right-to-left). + * + * Because of the recursive nature of many of the operations on trees it is + * necessary to define a number of helper functions for each type of tree node. + * The macro TREE_DEFINE(node_tag, entry_name) defines these functions with + * unique names according to the node_tag. This macro should be invoked, + * thereby defining the necessary functions, once per node tag in the program. + * + * For details on the use of these macros, see the tree(3) manual page. + */ + +/* Downloaded from http://piumarta.com/software/tree/ */ + +#ifndef __tree_h +#define __tree_h + + +#define TREE_DELTA_MAX 1 + +#define TREE_ENTRY(type) \ + struct { \ + struct type *avl_left; \ + struct type *avl_right; \ + int avl_height; \ + } + +#define TREE_HEAD(name, type) \ + struct name { \ + struct type *th_root; \ + int (*th_cmp)(struct type *lhs, struct type *rhs); \ + } + +#define TREE_INITIALIZER(cmp) { 0, cmp } + +#define TREE_DELTA(self, field) \ + (( (((self)->field.avl_left) ? (self)->field.avl_left->field.avl_height : 0)) \ + - (((self)->field.avl_right) ? (self)->field.avl_right->field.avl_height : 0)) + +/* Recursion prevents the following from being defined as macros. */ + +#define TREE_DEFINE(node, field) \ + \ + struct node *TREE_BALANCE_##node##_##field(struct node *); \ + \ + struct node *TREE_ROTL_##node##_##field(struct node *self) \ + { \ + struct node *r= self->field.avl_right; \ + self->field.avl_right= r->field.avl_left; \ + r->field.avl_left= TREE_BALANCE_##node##_##field(self); \ + return TREE_BALANCE_##node##_##field(r); \ + } \ + \ + struct node *TREE_ROTR_##node##_##field(struct node *self) \ + { \ + struct node *l= self->field.avl_left; \ + self->field.avl_left= l->field.avl_right; \ + l->field.avl_right= TREE_BALANCE_##node##_##field(self); \ + return TREE_BALANCE_##node##_##field(l); \ + } \ + \ + struct node *TREE_BALANCE_##node##_##field(struct node *self) \ + { \ + int delta= TREE_DELTA(self, field); \ + \ + if (delta < -TREE_DELTA_MAX) \ + { \ + if (TREE_DELTA(self->field.avl_right, field) > 0) \ + self->field.avl_right= TREE_ROTR_##node##_##field(self->field.avl_right); \ + return TREE_ROTL_##node##_##field(self); \ + } \ + else if (delta > TREE_DELTA_MAX) \ + { \ + if (TREE_DELTA(self->field.avl_left, field) < 0) \ + self->field.avl_left= TREE_ROTL_##node##_##field(self->field.avl_left); \ + return TREE_ROTR_##node##_##field(self); \ + } \ + self->field.avl_height= 0; \ + if (self->field.avl_left && (self->field.avl_left->field.avl_height > self->field.avl_height)) \ + self->field.avl_height= self->field.avl_left->field.avl_height; \ + if (self->field.avl_right && (self->field.avl_right->field.avl_height > self->field.avl_height)) \ + self->field.avl_height= self->field.avl_right->field.avl_height; \ + self->field.avl_height += 1; \ + return self; \ + } \ + \ + struct node *TREE_INSERT_##node##_##field \ + (struct node *self, struct node *elm, int (*compare)(struct node *lhs, struct node *rhs)) \ + { \ + if (!self) \ + return elm; \ + if (compare(elm, self) < 0) \ + self->field.avl_left= TREE_INSERT_##node##_##field(self->field.avl_left, elm, compare); \ + else \ + self->field.avl_right= TREE_INSERT_##node##_##field(self->field.avl_right, elm, compare); \ + return TREE_BALANCE_##node##_##field(self); \ + } \ + \ + struct node *TREE_FIND_##node##_##field \ + (struct node *self, struct node *elm, int (*compare)(struct node *lhs, struct node *rhs)) \ + { \ + if (!self) \ + return 0; \ + if (compare(elm, self) == 0) \ + return self; \ + if (compare(elm, self) < 0) \ + return TREE_FIND_##node##_##field(self->field.avl_left, elm, compare); \ + else \ + return TREE_FIND_##node##_##field(self->field.avl_right, elm, compare); \ + } \ + \ + int TREE_FIND_LESS_EQUAL_##node##_##field \ + (struct node *self, struct node *elm, int (*compare)(struct node *lhs, struct node *rhs), struct node **found, struct node **prev) \ + { \ + if (!self) \ + return 0; \ + if (compare(elm, self) == 0) { \ + *found = self; \ + return 1; \ + } \ + if (compare(elm, self) < 0) { \ + int ret = TREE_FIND_LESS_EQUAL_##node##_##field(self->field.avl_left, elm, compare, found, prev); \ + if (ret == 0 && *prev == NULL) { \ + *prev = self; \ + ret = -1; \ + } \ + return ret; \ + } else { \ + *found = self; \ + *prev = self; \ + return TREE_FIND_LESS_EQUAL_##node##_##field(self->field.avl_right, elm, compare, found, prev); \ + } \ + } \ + \ + struct node *TREE_MOVE_RIGHT_##node##_##field(struct node *self, struct node *rhs) \ + { \ + if (!self) \ + return rhs; \ + self->field.avl_right= TREE_MOVE_RIGHT_##node##_##field(self->field.avl_right, rhs); \ + return TREE_BALANCE_##node##_##field(self); \ + } \ + \ + struct node *TREE_REMOVE_##node##_##field \ + (struct node *self, struct node *elm, int (*compare)(struct node *lhs, struct node *rhs)) \ + { \ + if (!self) return 0; \ + \ + if (compare(elm, self) == 0) \ + { \ + struct node *tmp= TREE_MOVE_RIGHT_##node##_##field(self->field.avl_left, self->field.avl_right); \ + self->field.avl_left= 0; \ + self->field.avl_right= 0; \ + return tmp; \ + } \ + if (compare(elm, self) < 0) \ + self->field.avl_left= TREE_REMOVE_##node##_##field(self->field.avl_left, elm, compare); \ + else \ + self->field.avl_right= TREE_REMOVE_##node##_##field(self->field.avl_right, elm, compare); \ + return TREE_BALANCE_##node##_##field(self); \ + } \ + \ + void TREE_FORWARD_APPLY_ALL_##node##_##field \ + (struct node *self, void (*function)(struct node *node, void *data), void *data) \ + { \ + if (self) \ + { \ + TREE_FORWARD_APPLY_ALL_##node##_##field(self->field.avl_left, function, data); \ + function(self, data); \ + TREE_FORWARD_APPLY_ALL_##node##_##field(self->field.avl_right, function, data); \ + } \ + } \ + \ + void TREE_REVERSE_APPLY_ALL_##node##_##field \ + (struct node *self, void (*function)(struct node *node, void *data), void *data) \ + { \ + if (self) \ + { \ + TREE_REVERSE_APPLY_ALL_##node##_##field(self->field.avl_right, function, data); \ + function(self, data); \ + TREE_REVERSE_APPLY_ALL_##node##_##field(self->field.avl_left, function, data); \ + } \ + } \ + \ + void TREE_POST_ORDER_APPLY_ALL_##node##_##field \ + (struct node *self, void (*function)(struct node *node, void *data), void *data) \ + { \ + if (self) \ + { \ + TREE_POST_ORDER_APPLY_ALL_##node##_##field(self->field.avl_left, function, data); \ + TREE_POST_ORDER_APPLY_ALL_##node##_##field(self->field.avl_right, function, data); \ + function(self, data); \ + } \ + } \ + \ + void TREE_REVERSE_APPLY_POST_ALL_##node##_##field \ + (struct node *self, void (*function)(struct node *node, void *data), void *data) \ + { \ + if (self) \ + { \ + TREE_REVERSE_APPLY_POST_ALL_##node##_##field(self->field.avl_right, function, data); \ + TREE_REVERSE_APPLY_POST_ALL_##node##_##field(self->field.avl_left, function, data); \ + function(self, data); \ + } \ +} + +#define TREE_INSERT(head, node, field, elm) \ + ((head)->th_root= TREE_INSERT_##node##_##field((head)->th_root, (elm), (head)->th_cmp)) + +#define TREE_FIND(head, node, field, elm) \ + (TREE_FIND_##node##_##field((head)->th_root, (elm), (head)->th_cmp)) + +#define TREE_FIND_LESS_EQUAL(head, node, field, elm, found, prev) \ + (TREE_FIND_LESS_EQUAL_##node##_##field((head)->th_root, (elm), (head)->th_cmp, found, prev)) + +#define TREE_REMOVE(head, node, field, elm) \ + ((head)->th_root= TREE_REMOVE_##node##_##field((head)->th_root, (elm), (head)->th_cmp)) + +#define TREE_DEPTH(head, field) \ + ((head)->th_root->field.avl_height) + +#define TREE_FORWARD_APPLY(head, node, field, function, data) \ + TREE_FORWARD_APPLY_ALL_##node##_##field((head)->th_root, function, data) + +#define TREE_REVERSE_APPLY(head, node, field, function, data) \ + TREE_REVERSE_APPLY_ALL_##node##_##field((head)->th_root, function, data) + +#define TREE_POST_ORDER_APPLY(head, node, field, function, data) \ + TREE_POST_ORDER_APPLY_ALL_##node##_##field((head)->th_root, function, data) + +#define TREE_REVERSE_APPLY_POST(head, node, field, function, data) \ + TREE_REVERSE_APPLY_POST_ALL_##node##_##field((head)->th_root, function, data) + +#define TREE_INIT(head, cmp) do { \ + (head)->th_root= 0; \ + (head)->th_cmp= (cmp); \ + } while (0) + + +#endif /* __tree_h */ |