From 8404a2a181180ec25ee1e38bf3c645ab3beaff43 Mon Sep 17 00:00:00 2001 From: "Alan T. DeKok" Date: Thu, 4 Jan 2018 11:52:44 -0500 Subject: [PATCH] added patricia trie implementation, with tests --- Makefile | 2 +- src/lib/util/#notes# | 1 + src/lib/util/#prefix# | 74 + src/lib/util/.#notes | 1 + src/lib/util/.#prefix | 1 + src/lib/util/all.mk | 1 + src/lib/util/trie.c | 2884 ++++++++++++++++++++++++++++ src/lib/util/trie.mk | 6 + src/tests/all.mk | 2 +- src/tests/certs/tmp/.gitignore | 13 + src/tests/certs/tmp/Makefile | 161 ++ src/tests/certs/tmp/README | 225 +++ src/tests/certs/tmp/bootstrap | 82 + src/tests/certs/tmp/ca.cnf | 62 + src/tests/certs/tmp/client.cnf | 66 + src/tests/certs/tmp/ocsp.cnf | 61 + src/tests/certs/tmp/server.cnf | 63 + src/tests/certs/tmp/xpextensions | 24 + src/tests/eapol_test/fast-pac | Bin 0 -> 657 bytes src/tests/foo | 22 + src/tests/keywords/parallel-module | 12 + src/tests/trie/.gitignore | 1 + src/tests/trie/all.mk | 2 + src/tests/trie/input.txt | 228 +++ src/tests/trie/test.mk | 31 + src/tests/trie/trie.mk | 17 + 26 files changed, 4040 insertions(+), 2 deletions(-) create mode 100644 src/lib/util/#notes# create mode 100644 src/lib/util/#prefix# create mode 120000 src/lib/util/.#notes create mode 120000 src/lib/util/.#prefix create mode 100644 src/lib/util/trie.c create mode 100644 src/lib/util/trie.mk create mode 100644 src/tests/certs/tmp/.gitignore create mode 100644 src/tests/certs/tmp/Makefile create mode 100644 src/tests/certs/tmp/README create mode 100755 src/tests/certs/tmp/bootstrap create mode 100644 src/tests/certs/tmp/ca.cnf create mode 100644 src/tests/certs/tmp/client.cnf create mode 100644 src/tests/certs/tmp/ocsp.cnf create mode 100644 src/tests/certs/tmp/server.cnf create mode 100644 src/tests/certs/tmp/xpextensions create mode 100644 src/tests/eapol_test/fast-pac create mode 100644 src/tests/foo create mode 100644 src/tests/keywords/parallel-module create mode 100644 src/tests/trie/.gitignore create mode 100644 src/tests/trie/all.mk create mode 100644 src/tests/trie/input.txt create mode 100644 src/tests/trie/test.mk create mode 100644 src/tests/trie/trie.mk diff --git a/Makefile b/Makefile index c2db9d1f657..706fc72ae59 100644 --- a/Makefile +++ b/Makefile @@ -72,7 +72,7 @@ $(BUILD_DIR)/tests/radiusd-c: raddb/test.conf ${BUILD_DIR}/bin/radiusd $(GENERAT @echo "ok" @touch $@ -test: ${BUILD_DIR}/bin/radiusd ${BUILD_DIR}/bin/radclient tests.unit tests.xlat tests.keywords tests.auth tests.modules $(BUILD_DIR)/tests/radiusd-c tests.eap | build.raddb +test: ${BUILD_DIR}/bin/radiusd ${BUILD_DIR}/bin/radclient tests.trie tests.unit tests.xlat tests.keywords tests.auth tests.modules $(BUILD_DIR)/tests/radiusd-c tests.eap | build.raddb @$(MAKE) -C src/tests tests # Tests specifically for Travis. We do a LOT more than just diff --git a/src/lib/util/#notes# b/src/lib/util/#notes# new file mode 100644 index 00000000000..48d84575793 --- /dev/null +++ b/src/lib/util/#notes# @@ -0,0 +1 @@ +lcp takes end_bit, not keylen any more diff --git a/src/lib/util/#prefix# b/src/lib/util/#prefix# new file mode 100644 index 00000000000..49059fa9e6d --- /dev/null +++ b/src/lib/util/#prefix# @@ -0,0 +1,74 @@ +/** Convert node->entry[chunk] into a path + */ +static void fr_trie_path_add_prefix(void **entry, fr_trie_node_t *node, uint16_t chunk, size_t start_bit) +{ + uint16_t base, mask; + size_t end_bit; + fr_trie_path_t *path; + + base = chunk; + mask = (1 << node->size) - 1; + + /* + * Convert this chunk to a + * fr_trie_path_t, and return that up the + * trie. + */ + if (IS_DATA(node->entry[chunk])) { + uint8_t key[2]; + + /* + * Get start/end bits for the key. + */ + start_bit &= 0x07; + end_bit = start_bit + node->size; + assert(end_bit < 16); + + /* + * Shift the chunk into position + * + * @todo - shift in the top bits, too??? + */ + chunk <<= (16 - start_bit - node->size); + key[0] = chunk >> 8; + key[1] = chunk & 0xff; + + path = fr_trie_path_alloc(talloc_parent(node), key, start_bit, end_bit, node->entry[chunk]); + if (!path) return; + + talloc_free(node); + *entry = path; + return; + } + + /* + * Extend the child fr_trie_path_t with + * this chunk, and return that back up + * the trie. + */ + if (IS_PATH(node->entry[chunk])) { + path = GET_PATH(node->entry[chunk]); + + assert(start_bit == path->start_bit); + + if (BYTEOF(start_bit) == BYTEOF(start_bit + node->size)) { + fprintf(stderr, "EXTEND PATH SAME BYTE AFTER COLLAPSE %zd %zd, %zd, %zd\n", + start_bit, node->size, path->start_bit, path->length); + // path->start_bit -= node->size + // move path over + // ensure that the higher bits are what we need + + } else { + fprintf(stderr, "EXTEND PATH DIFF BYTE AFTER COLLAPSE\n"); + } + } + +} + + +#if 0 + if (!IS_NODE(node->entry[chunk])) { + fr_trie_path_add_prefix(entry, node, chunk, start_bit); + return data; + } +#endif diff --git a/src/lib/util/.#notes b/src/lib/util/.#notes new file mode 120000 index 00000000000..af4a750e82b --- /dev/null +++ b/src/lib/util/.#notes @@ -0,0 +1 @@ +alandekok@Thor.local.448 \ No newline at end of file diff --git a/src/lib/util/.#prefix b/src/lib/util/.#prefix new file mode 120000 index 00000000000..af4a750e82b --- /dev/null +++ b/src/lib/util/.#prefix @@ -0,0 +1 @@ +alandekok@Thor.local.448 \ No newline at end of file diff --git a/src/lib/util/all.mk b/src/lib/util/all.mk index 298e0e6827c..6fd9973567a 100644 --- a/src/lib/util/all.mk +++ b/src/lib/util/all.mk @@ -44,6 +44,7 @@ SOURCES := base64.c \ socket.c \ talloc.c \ token.c \ + trie.c \ udpfromto.c \ udp.c \ value.c \ diff --git a/src/lib/util/trie.c b/src/lib/util/trie.c new file mode 100644 index 00000000000..944b5fc209c --- /dev/null +++ b/src/lib/util/trie.c @@ -0,0 +1,2884 @@ +/* + * trie.c Path-compressed tries + * + * Version: $Id$ + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. + * + * This library 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 + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, write to the Free Software + * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA + * + * Copyright 2017 Alan DeKok + */ + +RCSID("$Id$") + + +#include +#include +#include +#ifdef TESTING +#include +#else +#define assert(_x) +#endif +#include +#include +#include + +/* + * This file implements path-compressed, level-compressed + * patricia tries. The original research paper is: + * + * https://www.nada.kth.se/~snilsson/publications/Dynamic-trie-compression-implementation/ + * + * The functionality has been extended to include intermediate + * nodes which consume 0 bits, but which user context data. + * These intermediate nodes allow for "longest prefix" matching. + * For example, in networking, you can have a routing table entry + * with 0/0 leading to one destination, and 10/8 leading to a + * different one. Looking up an address in the 10/8 network will + * return the 10/8 destination. Looking up any other address + * will return the default destination. + * + * In addition, we desire the ability to add and delete nodes + * dynamically. In the example given above, this means that + * after deleting 10/8, the trie should contain only the 0/0 + * network and associated destination. + * + * As of yet, it does not do level compression. This can be + * added without (hopefully) too much work + * + * This code could be extended to do packet matching, through the + * inclusion of "don't care" paths. e.g. parsing an IP header, + * where the src/dst IP addresses are 32-bit "don't care" fields. + * + * It could also be extended via "count" paths, where the path + * holds a count that is used in another part of the trie. For + * example, in RADIUS. The attribute encoding is one byte + * attribute, one byte length, followed by "length - 2" bytes of + * data. At that point though, you might as well just use Ragel. + */ + +/** Enable path compression (or not) + * + * With path compression, long sequences of bits are stored as a + * path, e.g. "abcdef". Without path compression, we would have to + * create a large number of intermediate 2^N-way nodes, all of which + * would have only one edge. + */ +#define WITH_PATH_COMPRESSION + +/** Internal sanity checks for debugging. + * + * Tries are complex. So we have verification routines for every + * type of node. These routines are called from within the trie + * manipulation functions. If the trie manipulation has a bug, the + * verification routines are likely to catch some of the more + * egregious issues. + */ +#ifdef TESTING +#define WITH_TRIE_VERIFY +#endif + +#ifndef WITH_TRIE_VERIFY +#define fr_trie_node_verify(_x) +#define fr_trie_verify(_x) +#ifdef WITH_PATH_COMPRESSION +#define fr_trie_path_verify(_x) +#endif +#endif + +// @todo - do level compression +// stop merging nodes if a key ends at the top of the level +// otherwise merge so we have at least 2^4 way fan-out, but no more than 2^8 +// that should be a decent trade-off between memory and speed + +// @todo - generalized function to normalize the trie. + +// @todo - add tests to run with / without path compression + +// @todo add "depth" for test, which shows how many nodes deep the trie is + +// @todo add "nodes" for test, which shows how many nodes are in the trie + +// @todo - make this configurable in fr_trie_t, and pass fr_trei_t to +// all internal function. +#define DEFAULT_SIZE (4) + +/* + * Macros to swap one for the other. + */ +#define BITSOF(_x) ((_x) * 8) +#define BYTEOF(_x) ((_x) >> 3) +#define BYTES(_x) (((_x) + 0x07) >> 3) + +// @todo - put this into fr_trie_t, and pass ft to all functions... +static int node_number = 0; + +/** A data structure which holds a path-compressed key. + * + */ +typedef struct fr_trie_path_t { + int number; //!< for debug printing + uint8_t const *key; //!< path information. + int length; //!< length of the path in bits + int start_bit; //!< bit where the path starts + int end_bit; //!< bit where the path ends + void *trie; //!< trie / user ctx associated with this entry +} fr_trie_path_t; + +/** A data structure which holds a 2^N way key + * + */ +typedef struct fr_trie_node_t { + int number; //!< for debug printing + int size; //!< as power of 2. i.e. 2^1=2, 2^2=4, 2^3=8, etc. + int used; //!< number of used entries + void *entry[]; //!< array entries +} fr_trie_node_t; + +/** A data structure which holds user ctx data + * + */ +typedef struct fr_trie_user_t { + int number; //!< for debug printing + void *data; //!< user ctx if we have a match here + void *trie; //!< subtree if the key continues past this point +} fr_trie_user_t; + + +/** The main trie data structure. + * + */ +struct fr_trie_t { + int number; //!< for walking back up the trie + int default_size; //!< for trie nodes + void *trie; //!< the first node +}; + + +/* + * We pack multiple types of nodes into one pointer for + * simplicity. + */ +#define IS_NODE(_x) ((((uintptr_t) _x) & 0x03) == 0x00) + +#define IS_USER(_x) ((((uintptr_t) _x) & 0x03) == 0x01) +#define GET_USER(_x) ((fr_trie_user_t *) (((uintptr_t) _x) & ~(uintptr_t) 0x03)) +#define PUT_USER(_x) ((void *) (((uintptr_t) _x) | 0x01)) + +#ifdef WITH_PATH_COMPRESSION +#define IS_PATH(_x) ((((uintptr_t) _x) & 0x03) == 0x03) +#define GET_PATH(_x) ((fr_trie_path_t *) (((uintptr_t) _x) & ~(uintptr_t) 0x03)) +#define PUT_PATH(_x) ((void *) (((uintptr_t) _x) | 0x03)) + +static void *fr_trie_path_merge_paths(TALLOC_CTX *ctx, fr_trie_path_t *path1, fr_trie_path_t *path2, int depth) CC_HINT(nonnull); +static int fr_trie_merge(TALLOC_CTX *ctx, void **out, void *a, void *b, int depth); +#endif + +static int fr_trie_key_insert(TALLOC_CTX *ctx, void **trie_p, uint8_t const *key, int start_bit, int end_bit, void *trie) CC_HINT(nonnull); + +static void reparent(TALLOC_CTX *ctx, void *trie) +{ + /* + * Ensure that things are parented correctly, so that + * freeing nodes works. + */ + if (IS_USER(trie)) { + (void) talloc_steal(ctx, GET_USER(trie)); + return; + + } +#ifdef WITH_PATH_COMPRESSION + if (IS_PATH(trie)) { + (void) talloc_steal(ctx, GET_PATH(trie)); + return; + } +#endif + + assert(IS_NODE(trie)); + (void) talloc_steal(ctx, trie); + +} + +/** Allocate a 2^N way node + * + * @param ctx the talloc context, should be the parent node that points to this one. + * @param size the number of bits this node will consume + * @return + * - NULL on error + * - fr_trie_node_t* on success + */ +static fr_trie_node_t *fr_trie_node_alloc(TALLOC_CTX *ctx, int size) +{ + size_t node_size; + fr_trie_node_t *node; + + if (!size || (size > 8)) { + fprintf(stderr, "FAILED %d - %d\n", __LINE__, (int) size); + return NULL; + } + + node_size = sizeof(fr_trie_node_t) + (sizeof(node->entry[0]) * (1 << size)); + node = talloc_zero_size(ctx, node_size); + if (!node) return NULL; + + (void) talloc_set_name_const(node, "fr_trie_node_t"); + + node->size = size; + node->number = node_number++; + + return node; +} + + +#ifdef WITH_TRIE_VERIFY +static void *trie_parent(void *trie) +{ + /* + * Ensure that things are parented correctly, so that + * freeing nodes works. + */ + if (IS_USER(trie)) { + return talloc_parent(GET_USER(trie)); + + } +#ifdef WITH_PATH_COMPRESSION + if (IS_PATH(trie)) { + return talloc_parent(GET_PATH(trie)); + } +#endif + + assert(IS_NODE(trie)); + return talloc_parent(trie); +} + + +/** Verifies that a node is correct, without recursion + * + */ +static void fr_trie_node_verify(fr_trie_node_t const *node) +{ + int i, used; + + (void) talloc_get_type_abort(node, fr_trie_node_t); + + assert(node->size > 0); + assert(node->size <= 8); + assert(node->used >= 0); + assert(node->used <= (1 << node->size)); + + used = 0; + for (i = 0; i < (1 << node->size); i++) { + if (!node->entry[i]) continue; + + used++; + } + + assert(used == node->used); +} + +#ifdef WITH_PATH_COMPRESSION +/** Verifies that a path is correct, without recursion + * + */ +static void fr_trie_path_verify(fr_trie_path_t const *path) +{ + void *parent; + + (void) talloc_get_type_abort(path, fr_trie_path_t); + + assert(path->start_bit >= 0); + assert(path->start_bit < 8); + assert(path->length > 0); + assert(path->length < (1 << 20)); + assert(path->end_bit > 0); + assert(path->length < (1 << 20)); + assert((path->start_bit + path->length) == path->end_bit); + + assert(path->key != NULL); + assert(talloc_parent(path->key) == path); + + if ((path->start_bit == 0) && (path->length >= 8)) { + assert(path->key[0] > ' '); + assert(path->key[0] < 0x7f); + } + + /* + * This is only for testing... + */ + if (BYTEOF(path->end_bit) > 2) { + int i; + + for (i = 1; i < BYTEOF(path->end_bit); i++) { + assert(path->key[i] > ' '); + assert(path->key[i] < 0x7f); + } + } + + parent = trie_parent(path->trie); + assert(parent == path); +} + +#endif /* WITH_PATH_COMPRESSION */ + + +/** Verifies that an entrie trie is correct, with recursion + * + */ +static void fr_trie_verify(void *trie) +{ + int i; + fr_trie_node_t *node; + void *parent; + + if (IS_USER(trie)) return; + +#ifdef WITH_PATH_COMPRESSION + if (IS_PATH(trie)) { + fr_trie_path_t *path = GET_PATH(trie); + + fr_trie_path_verify(path); + + parent = trie_parent(path->trie); + assert(parent == path); + fr_trie_verify(path->trie); + return; + } +#endif + + node = trie; + fr_trie_node_verify(node); + + for (i = 0; i < (1 << node->size); i++) { + if (!node->entry[i]) continue; + + parent = trie_parent(node->entry[i]); + + assert(parent == node); + fr_trie_verify(node->entry[i]); + } +} +#endif /* WITH_TRIE_VERIFY */ + + +/* + * Table of how many leading bits there are in KEY1^KEY2. + */ +static uint8_t xor2lcp[256] = { + 8, 7, 6, 6, + 5, 5, 5, 5, /* 4x 5 */ + 4, 4, 4, 4, /* 8x 4 */ + 4, 4, 4, 4, + 3, 3, 3, 3, /* 16x 3 */ + 3, 3, 3, 3, + 3, 3, 3, 3, + 3, 3, 3, 3, + 2, 2, 2, 2, /* 32x 2 */ + 2, 2, 2, 2, + 2, 2, 2, 2, + 2, 2, 2, 2, + 2, 2, 2, 2, + 2, 2, 2, 2, + 2, 2, 2, 2, + 2, 2, 2, 2, + 1, 1, 1, 1, /* 64x 1 */ + 1, 1, 1, 1, + 1, 1, 1, 1, + 1, 1, 1, 1, + 1, 1, 1, 1, + 1, 1, 1, 1, + 1, 1, 1, 1, + 1, 1, 1, 1, + 1, 1, 1, 1, + 1, 1, 1, 1, + 1, 1, 1, 1, + 1, 1, 1, 1, + 1, 1, 1, 1, + 1, 1, 1, 1, + 1, 1, 1, 1, + 1, 1, 1, 1, + 0, 0, 0, 0, /* 128x 0 */ + 0, 0, 0, 0, + 0, 0, 0, 0, + 0, 0, 0, 0, + 0, 0, 0, 0, + 0, 0, 0, 0, + 0, 0, 0, 0, + 0, 0, 0, 0, + 0, 0, 0, 0, + 0, 0, 0, 0, + 0, 0, 0, 0, + 0, 0, 0, 0, + 0, 0, 0, 0, + 0, 0, 0, 0, + 0, 0, 0, 0, + 0, 0, 0, 0, +}; + + +/* + * This table is used to set the "end bit" for LCP. We OR in this + * value into the XOR of the two keys, and then look up the resulting + * value in the xor2lcp[] table above. Setting the last bit to 1 + * ensures that the LCP lookup is no more than (end_bit - start_bit) + */ +static uint8_t lcp_end_bit[9] = { + 0, /* can't exist */ + 0x40, + 0x20, + 0x10, + 0x08, + 0x04, + 0x02, + 0x01, + 0x00 +}; + + +/** Get the longest prefix of the two keys. + * + */ +static int fr_trie_path_lcp(uint8_t const *key1, int keylen1, uint8_t const *key2, int keylen2, int start_bit) +{ + uint8_t xor; + int i, bytes, lcp, end_bit, recheck; + int s2, e2; + int start_byte, end_byte; + + if (!keylen1 || !keylen2) return 0; + assert((start_bit & 0x07) == start_bit); + + end_bit = keylen1; + if (end_bit > keylen2) end_bit = keylen2; + end_bit += start_bit; + + /* + * Compare bits in the first byte + */ + lcp = 0; + if ((start_bit != 0) || (end_bit <= 8)) { + if (end_bit <= 8) { + e2 = end_bit; + } else { + e2 = 8; + } + + s2 = start_bit; + assert(s2 <= e2); + + xor = key1[0] ^ key2[0]; + + /* + * Push the bits into the high bits, + * and set the lowest bit which is possible + * for the LCP. + */ + xor <<= s2; + xor |= lcp_end_bit[e2 - s2]; + + lcp = xor2lcp[xor]; + + /* + * We haven't found any common prefix, we're done. + */ + if (!lcp) return 0; + + /* + * We only have one byte, and we've checked that. + * Return the longest prefix. + */ + if (end_bit <= 8) { + goto done; + } + + /* + * Skip the first byte, we've already checked it. + */ + start_byte = 1; + } else { + start_byte = 0; + } + + /* + * If the key ends on a byte boundary, check the last + * byte. Othewise, check all but the last byte. We will + * do a separate bit check for the last byte. + */ + end_byte = BYTEOF(end_bit); + assert(start_byte <= end_byte); + + bytes = 0; + + /* + * Compare the keys byte by byte. + */ + recheck = -1; + for (i = start_byte; i < end_byte; i++) { + if (key1[i] == key2[i]) { + bytes++; + continue; + } + + recheck = i; + break; + } + + lcp += 8 * bytes; + + /* + * Do we need to recheck the last byte? + */ + if (recheck < 0) { + /* + * Nope. We're done. + */ + if ((end_bit & 0x07) == 0) goto done; + + recheck = BYTEOF(end_bit); + } + + /* + * We recheck starting at the recheck byte, and + * continuing to the end of the keys. + */ + s2 = recheck * 8; + e2 = end_bit; + + /* + * If there are more than 8 bits to check, max out at the + * bits in this byte (8). Otherwise, just check the + * remaining bits in this byte. + */ + if ((e2 - s2) > 8) { + s2 = 0; + e2 = 8; + } else { + assert(end_bit > s2); + e2 = end_bit - s2; + s2 = 0; + } + + xor = key1[recheck] ^ key2[recheck]; + xor <<= s2; + xor |= lcp_end_bit[e2 - s2]; + lcp += xor2lcp[xor]; + +done: + assert(lcp <= keylen1); + assert(lcp <= keylen2); + return lcp; +} + + +#ifdef WITH_PATH_COMPRESSION +/** Allocate an fr_trie_path_t + * + */ +static CC_HINT(nonnull) fr_trie_path_t *fr_trie_path_alloc(TALLOC_CTX *ctx, uint8_t const *key, int start_bit, int end_bit, void *trie) +{ + fr_trie_path_t *path; + uint8_t *p; + + assert(end_bit < (1 << 16)); + assert(end_bit > 0); + assert(start_bit < end_bit); + assert(!IS_PATH(trie)); + + path = talloc_zero_size(ctx, sizeof(*path)); + if (!path) return NULL; + + (void) talloc_set_name_const(path, "fr_trie_path_t"); + + path->start_bit = start_bit & 0x07; + path->length = end_bit - start_bit; + path->end_bit = path->start_bit + path->length; + assert(path->length > 0); + path->number = node_number++; + + path->key = p = talloc_memdup(path, key + BYTEOF(start_bit), BYTES(path->end_bit)); + if (!path->key) { + talloc_free(path); + return NULL; + } + + /* + * Mask off the lower bits in the last byte. + * + * 0 == High bit is used, so we have to mask off the lower 7 bits. + * 7 == low bit is used, so we don't need to mask anything off + */ + if ((path->end_bit & 0x07) != 0) { + uint8_t mask; + int bits; + + bits = path->end_bit & 0x07; /* bits used 1..7 */ + bits = 8 - bits; /* bits to clear 7..1 */ + mask = (1 << bits) - 1; /* bits to clear are now all 1s */ + + p[BYTEOF(path->end_bit)] &= ~mask; /* zero out the low bits */ + } + + /* + * Skip this for some cases. + */ + if (IS_USER(trie) && (GET_USER(trie) == NULL)) return path; + + /* + * Ensure that things are parented correctly, so that + * freeing nodes works. + */ + reparent(path, trie); + path->trie = trie; + + fr_trie_path_verify(path); + + return path; +} + +//#define HEX_DUMP + +#ifdef HEX_DUMP +static void hex_dump(FILE *fp, char const *msg, uint8_t const *key, int start_bit, int end_bit) +{ + int i; + + fprintf(fp, "%s\ts=%zd e=%zd\t\t", msg, start_bit, end_bit); + + for (i = 0; i < BYTES(end_bit); i++) { + fprintf(fp, "%02x ", key[i]); + } + fprintf(fp, "\n"); +} +#endif + + +/** Insert an fr_trie_path_t into an fr_trie_node_t; + * + * Note that it may split the input node if the path->length is + * smaller than node->size + */ +static int fr_trie_path_merge(TALLOC_CTX *ctx, fr_trie_node_t **node_p, fr_trie_path_t *path, int depth) +{ + fr_trie_node_t *node = *node_p; + + fr_trie_path_verify(path); + + /* + * Split the node here and do all kinds of magic + */ + if (node->size > path->length) { + fr_trie_node_t *small; + void *out; + + small = fr_trie_node_alloc(ctx, path->length); + if (!small) return -1; + + if (fr_trie_merge(ctx, &out, small, PUT_PATH(path), depth) < 0) { + talloc_free(small); + return -1; + } + + assert(out == small); + fr_trie_node_verify(small); + + if (fr_trie_merge(ctx, &out, small, node, depth) < 0) { + talloc_free(small); + return -1; + } + + assert(out == small); + fr_trie_node_verify(small); + *node_p = small; + + return 0; + } + + if (fr_trie_key_insert(ctx, (void **) node_p, path->key, path->start_bit, path->end_bit, path->trie) < 0) { + return -1; + } + + fr_trie_node_verify(node); + + talloc_free(path); + return 0; +} + + +/** Merge two keys which have no common prefix. + * + * This function allocates an fr_trie_node_t which is large enough, but not too large. + * And then merges the two paths into it. + */ +static fr_trie_node_t *fr_trie_path_merge_disjoint(TALLOC_CTX *ctx, fr_trie_path_t *path1, fr_trie_path_t *path2, int depth) +{ + int size; + fr_trie_node_t *node; + fr_trie_path_t *td_short, *td_long; + + fr_trie_path_verify(path1); + fr_trie_path_verify(path2); + + assert(path1->start_bit == path2->start_bit); + + /* + * Figure out which is the shorter of the two paths. + */ + if (path1->length < path2->length) { + td_short = path1; + td_long = path2; + } else { + td_short = path2; + td_long = path1; + } + + /* + * @todo - pass in ft->default_size, so we know what the + * default size is. + */ + size = DEFAULT_SIZE; + if (size > td_short->length) size = td_short->length; + assert(size > 0); + assert(size <= 8); + + node = fr_trie_node_alloc(ctx, size); + if (!node) { + fprintf(stderr, "FAILED %d\n", __LINE__); + return NULL; + } + + /* + * Fill the new node with the short key + */ + if (fr_trie_path_merge(ctx, &node, td_short, depth) < 0) { + fprintf(stderr, "FAILED %d\n", __LINE__); + talloc_free(node); + talloc_free(td_short); + return NULL; + } + + fr_trie_node_verify(node); + + /* + * And then insert the longer of the two keys + */ + if (fr_trie_path_merge(ctx, &node, td_long, depth) < 0) { + fprintf(stderr, "FAILED %d\n", __LINE__); + talloc_free(node); + talloc_free(td_long); + return NULL; + } + + fr_trie_node_verify(node); + + return node; +} + + +/** Merge two paths + * + * @param ctx the talloc ctx + * @param path1 path from the existing tree. + * @param path2 path from the insert. MUST end in user ctx. + * @return + * - NULL on error. path1 and path2 are left alone. + * - new trie on success. path1 and path2 are freed + */ +static void *fr_trie_path_merge_paths(TALLOC_CTX *ctx, fr_trie_path_t *path1, fr_trie_path_t *path2, int depth) +{ + int prefix_len; + fr_trie_node_t *node; + fr_trie_path_t *suffix1, *suffix2, *prefix; + + fr_trie_path_verify(path1); + fr_trie_path_verify(path2); + + assert(path2->length > 0); + assert(path1->start_bit == path2->start_bit); + + /* + * path1 is from the existing trie. path2 is the path we're trying to insert. + */ + assert(IS_USER(path2->trie)); + + (void) talloc_get_type_abort(path1, fr_trie_path_t); + + prefix_len = fr_trie_path_lcp(path1->key, path1->length, path2->key, path2->length, path1->start_bit); + if (!prefix_len) { + return fr_trie_path_merge_disjoint(ctx, path1, path2, depth); + } + + prefix = fr_trie_path_alloc(ctx, path1->key, path1->start_bit, prefix_len + path1->start_bit, PUT_USER(NULL)); + if (!prefix) { + return NULL; + } + + // @fixme - call key_insert instead of merge??? + + /* + * There is a prefix. Pull it off and create the child + * nodes. + */ + if (prefix_len < path1->length) { + suffix1 = fr_trie_path_alloc(ctx, path1->key, path1->start_bit + prefix_len, path1->end_bit, path1->trie); + if (!suffix1) return NULL; + } else { + suffix1 = NULL; + } + + if (prefix_len < path2->length) { + suffix2 = fr_trie_path_alloc(ctx, path2->key, path2->start_bit + prefix_len, path2->end_bit, path2->trie); + if (!suffix2) { + talloc_free(suffix1); + return NULL; + } + } else { + suffix2 = NULL; + } + + /* + * Both paths are the same length. Skip over them + * entirely, and merge the two subtries. + */ + if (!suffix1 && !suffix2) { + /* + * We can insert, but we can't over-write an entry. + */ + if (IS_USER(path1->trie)) { + fprintf(stderr, "FAILED %d prefix %zd\n", __LINE__, prefix_len); + return NULL; + } + + if (fr_trie_merge(prefix, &prefix->trie, path1->trie, path2->trie, depth + prefix_len) < 0) { + return NULL; + } + + goto done; + } + + if (!suffix1) { + assert(!IS_PATH(path1->trie)); + + if (fr_trie_merge(prefix, &prefix->trie, path1->trie, PUT_PATH(suffix2), depth + prefix->length) < 0) { + talloc_free(prefix); + talloc_free(suffix2); + return NULL; + } + goto done; + + } else if (!suffix2) { + if (fr_trie_merge(prefix, &prefix->trie, PUT_PATH(suffix1), path2->trie, depth + prefix->length) < 0) { + talloc_free(prefix); + talloc_free(suffix1); + return NULL; + } + goto done; + + } else { + node = fr_trie_path_merge_disjoint(prefix, suffix1, suffix2, depth + prefix->length); + if (!node) { + talloc_free(prefix); + talloc_free(suffix1); + talloc_free(suffix2); + return NULL; + } + + (void) talloc_get_type_abort(node, fr_trie_node_t); + } + + fr_trie_node_verify(node); + + reparent(prefix, node); + prefix->trie = node; + +done: + talloc_free(path1); + talloc_free(path2); + + fr_trie_path_verify(prefix); + + return PUT_PATH(prefix); +} + +/** Concatenate two paths together + * + * This function is used to ensure normal form. I.e. we can't have a + * path directly follow another path. Instead, we just concatenate + * them into one longer path. + */ +static int fr_trie_path_concatenate(fr_trie_path_t *path, + uint8_t const *key1, int start_bit1, int keylen1, + uint8_t const *key2, int start_bit2, int keylen2) +{ + uint8_t *p, *q; + + assert(((start_bit1 + keylen1) & 0x07) == start_bit2); + + p = talloc_array(path, uint8_t, BYTES(start_bit1 + keylen1 + keylen2)); + if (!p) return -1; + + memcpy(p, key1, BYTES(start_bit1 + keylen1)); + + if (start_bit2 == 0) { + memcpy(p + BYTES(start_bit1 + keylen1), key2, BYTES(keylen2)); + + } else { + uint8_t *out; + uint8_t mask; + int bytes2; + + out = p + BYTEOF(start_bit1 + keylen1); + + mask = ((1 << (8 - start_bit2)) - 1); + out[0] &= ~mask; + out[0] |= (key2[0] & mask); + + bytes2 = BYTES(start_bit2 + keylen2); + if (bytes2 > 1) { + memcpy(out + 1, key2 + 1, bytes2 - 1); + } + } + + memcpy(&q, &path->key, sizeof(q)); + talloc_free(q); + path->key = p; + + path->start_bit = start_bit1; + path->length = keylen1 + keylen2; + path->end_bit = path->start_bit + path->length; + + return 0; +} + + +/** Add a prefix to a given trie + * + * @param ctx the talloc ctx + * @param trie the trie which is the suffix + * @param size the number of bits in 'input' + * @param input the input bits which will be turned into a path / prefix + * @param start_bit The start bit in 'input' where the data is located. + */ +static void *fr_trie_path_prefix_add(TALLOC_CTX *ctx, void *trie, int size, uint16_t input, int start_bit) +{ + fr_trie_path_t *path; + int bits_used; + uint16_t chunk = input; + uint8_t buffer[2]; + + bits_used = start_bit & 0x07; + + chunk <<= (16 - size - bits_used); + buffer[0] = chunk >> 8; + buffer[1] = chunk & 0xff; + + if (!IS_PATH(trie)) { + path = fr_trie_path_alloc(ctx, buffer, bits_used, bits_used + size, trie); + if (!path) return NULL; + + if (IS_NODE(trie)) (void) talloc_steal(path, trie); + + fr_trie_path_verify(path); + return PUT_PATH(path); + } + + assert(IS_PATH(trie)); + path = GET_PATH(trie); + + fr_trie_path_verify(path); + + (void) fr_trie_path_concatenate(path, buffer, bits_used, size, path->key, path->start_bit, path->length); + + return PUT_PATH(talloc_steal(ctx, path)); +} +#endif /* WITH_PATH_COMPRESSION */ + + +/** Return a chunk of a key (in the low bits) for use in 2^N node de-indexing + * + */ +static uint16_t get_chunk(uint8_t const *key, int num_bits, int start_bit, int end_bit) +{ + uint16_t chunk; + + assert(num_bits > 0); + assert(num_bits <= 8); + assert(start_bit < end_bit); + + /* + * Load the byte + */ + chunk = key[BYTEOF(start_bit)]; + chunk <<= 8; + + if ((start_bit + 8) < end_bit) { + chunk |= key[BYTEOF(start_bit) + 1]; + } + + /* + * Shift out the bits at the start, that we don't + * want. + */ + chunk <<= (start_bit & 0x07); + + /* + * The bits we want are now all in the high bits + * of "chunk". But we only want some of them. + * + * Shift the chunk so that the bits we want are now in + * the low bits. + */ + chunk >>= 8 + (8 - num_bits); + + return chunk; +} + + +#ifdef WITH_PATH_COMPRESSION +/** A generic merge routine + * + * @param ctx the talloc ctx + * @param out where the output trie is stored + * @param a first mangled trie + * @param b second mangled trie + * @param depth bit depth where the trie starts + */ +static int fr_trie_merge(TALLOC_CTX *ctx, void **out, void *a, void *b, int depth) +{ + if (!a && !b) { + *out = NULL; + return 0; + } + + if (!a) { + reparent(ctx, b); + *out = b; + return 0; + } + + if (!b) { + reparent(ctx, a); + *out = a; + return 0; + } + + if (IS_USER(a) && IS_USER(b)) { + printf("FAIL %d\n", __LINE__); + return -1; + } + + /* + * Don't matter what 'b' is. Just recurse to merge it + * in. + */ + if (IS_USER(a)) { + fr_trie_user_t *user = GET_USER(a); + + if (fr_trie_merge(user, &user->trie, user->trie, b, depth) < 0) { + return -1; + } + + reparent(ctx, a); + *out = a; + return 0; + } + + if (IS_USER(b)) { + fr_trie_user_t *user = GET_USER(b); + + if (fr_trie_merge(user, &user->trie, user->trie, a, depth) < 0) { + return -1; + } + + reparent(ctx, b); + *out = b; + return 0; + } + +#ifdef WITH_PATH_COMPRESSION + if (IS_PATH(a) && IS_PATH(b)) { + /* + * Do LCP and split it off. + */ + *out = fr_trie_path_merge_paths(ctx, GET_PATH(a), GET_PATH(b), depth); + if (!*out) { + printf("FAIL %d\n", __LINE__); + return -1; + } + return 0; + } + + if (IS_PATH(a) && IS_NODE(b)) { + fr_trie_path_t *path = GET_PATH(a); + fr_trie_node_t *node = b; + + /* + * @todo - if (path->length >= node->size) + * get_chunk(path), and call ourselves + * recursively. + */ + + if (fr_trie_path_merge(ctx, &node, path, depth) < 0) { + printf("FAIL %d\n", __LINE__); + return -1; + } + + reparent(ctx, node); + *out = node; + return 0; + } + + if (IS_PATH(b) && IS_NODE(a)) { + fr_trie_path_t *path = GET_PATH(b); + fr_trie_node_t *node = a; + + if (fr_trie_path_merge(ctx, &node, path, depth) < 0) { + printf("FAIL %d\n", __LINE__); + return -1; + } + + reparent(ctx, node); + *out = node; + return 0; + } +#endif + + if (IS_NODE(a) && IS_NODE(b)) { + int i, bits; + fr_trie_node_t *node1 = a; + fr_trie_node_t *node2 = b; + + fr_trie_node_verify(node1); + fr_trie_node_verify(node2); + + if (node1->size == node2->size) { + for (i = 0; i < (1 << node1->size); i++) { + if (!node1->entry[i] && !node2->entry[i]) continue; + + if (fr_trie_merge(node1, &node1->entry[i], node1->entry[i], + node2->entry[i], depth) < 0) { + return -1; + } + } + + talloc_free(node2); + fr_trie_node_verify(node1); + + reparent(ctx, node1); + *out = node1; + return 0; + } + + /* + * Ensure that node1 is the smaller node. + */ + if (node1->size > node2->size) { + fr_trie_node_t *tmp = node1; + node1 = node2; + node2 = tmp; + } + + /* + * Loop over the smaller node, merging in the + * results from the larger node. + */ + bits = node2->size - node1->size; + + for (i = 0; i < (1 << node1->size); i++) { + uint16_t j; + + assert(bits < 8); + + for (j = 0; j < (1 << bits); j++) { + void *trie; + + /* + * If the entry in the larger + * node is empty, we don't need + * to do anything here. + */ + if (!node2->entry[(i << bits) + j]) continue; + + /* + * Convert the entry in node2 + * into a path + trailing + * information. + */ + trie = fr_trie_path_prefix_add(node1, node2->entry[(i << bits) | j], + bits, j, depth); + assert(trie != NULL); + + if (fr_trie_merge(node1, &node1->entry[i], + node1->entry[i], trie, depth) < 0) { + return -1; + } + } + } + + talloc_free(node2); + + reparent(ctx, node1); + *out = node1; + return 0; + } + + assert(0 == 1); + + return -1; +} +#endif + + +/** Match a key in a trie and return user ctx, if any + * + * The key may be LONGER than entries in the trie. In which case the + * closest match is returned. + * + * @param trie the trie + * @param key the key + * @param start_bit the start bit + * @param end_bit the end bit + * @param exact do we return an exact match, or the shortest one. + * @return + * - NULL on not found + * - void* user ctx on found + * + * @todo - change this into fr_trie_walk(), and have it return trie* + * the caller can then turn that into user data + */ +static void *fr_trie_key_match(void *trie, uint8_t const *key, int start_bit, int end_bit, bool exact) +{ + uint16_t chunk; + void *data; + fr_trie_node_t *node; + fr_trie_user_t *user; + + /* + * Nothing is "no match". + */ + if (!trie) return NULL; + + /* + * User ctx data. + */ + if (IS_USER(trie)) { + user = GET_USER(trie); + + /* + * We've reached the end of the input. Return + * the user ctx data. + */ + if (start_bit == end_bit) { + return user->data; + } + + /* + * Keep matching. If we have something, return + * that. + */ + data = fr_trie_key_match(user->trie, key, start_bit, end_bit, exact); + if (data) return data; + + /* + * We didn't find anything deeper in the trie, + * AND we require an exact match. That's a + * failure. + */ + if (exact) return NULL; + + /* + * Return the inexact match. + */ + return user->data; + } + +#ifdef WITH_PATH_COMPRESSION + /* + * Check the path, by checking the longest common prefix + * of it and the input key. + */ + if (IS_PATH(trie)) { + int lcp; + fr_trie_path_t *path; + + path = GET_PATH(trie); + + /* + * Nothing to match, we're done. + */ + if (!key || (start_bit == end_bit)) return NULL; + + lcp = fr_trie_path_lcp(path->key, path->length, + key + BYTEOF(start_bit), end_bit - start_bit, path->start_bit); + + /* + * Too short: not a match. + */ + if (lcp < path->length) return NULL; + + return fr_trie_key_match(path->trie, key, start_bit + path->length, end_bit, exact); + } +#endif + + node = trie; + fr_trie_node_verify(node); + + /* + * The key ends in the middle of this node. That's not a + * match. + */ + if ((start_bit + node->size) > end_bit) return NULL; + + chunk = get_chunk(key, node->size, start_bit, end_bit); + + /* + * No entry? That's not a match. + */ + if (!node->entry[chunk]) return NULL; + + return fr_trie_key_match(node->entry[chunk], key, start_bit + node->size, end_bit, exact); +} + + +/** Insert a binary key into the trie + * + * The key must have at least ((start_bit + keylen) >> 3) bytes + * + * @param ctx the talloc ctx + * @param trie_p pointer to the trie to insert into + * @param key the binary key + * @param start_bit the start bit + * @param end_bit the end bit + * @param subtrie the subtrie to insert after the key + * @return + * - <0 on error + * - 0 on success + */ +static int fr_trie_key_insert(TALLOC_CTX *ctx, void **trie_p, uint8_t const *key, int start_bit, int end_bit, void *subtrie) +{ + int incr; + int rcode, next; + uint16_t chunk; + void *trie = *trie_p; +#ifdef WITH_PATH_COMPRESSION + fr_trie_path_t *path; +#endif + fr_trie_node_t *node; + + if (!trie) { + int size; + +#ifdef WITH_PATH_COMPRESSION + /* + * If we have key, just create a path. + */ + if (start_bit < end_bit) { + path = fr_trie_path_alloc(ctx, key, start_bit, end_bit, subtrie); + if (!path) return -1; + + *trie_p = PUT_PATH(path); + return 0; + } +#endif + + if (start_bit == end_bit) { + reparent(ctx, subtrie); + *trie_p = subtrie; + return 0; + } + + /* + * Avoid splitting the main node immediately + * after creating it. + */ + size = end_bit - start_bit; + if (size > DEFAULT_SIZE) size = DEFAULT_SIZE; + + node = fr_trie_node_alloc(ctx, size); + if (!node) return -1; + *trie_p = node; +// goto insert_node; + assert(0 == 1); + } + + /* + * We've run out of bits. The trie we're inserting MUST + * be a user one, otherwise we don't know what to do... + */ + if (start_bit == end_bit) { + fr_trie_user_t *user; + + /* + * Can't insert a user ctx over top of a user + * ctx. + */ + if (IS_USER(trie) && IS_USER(subtrie)) { + fprintf(stderr, "FAIL %d\n", __LINE__); + return -1; + } + + /* + * We're inserting a trie after a user ctx, that + * should be fine. It already has the correct + * parent. + */ + if (IS_USER(trie)) { + user = GET_USER(trie); + + return fr_trie_merge(user, &user->trie, user->trie, subtrie, start_bit); + } + + /* + * Insert this key BEFORE anything else in the + * trie. + */ + user = GET_USER(subtrie); + + /* + * Nothing after this user ctx. Just mash the + * current node after it, and reparent everything + * appropriately. + */ + if (!user->trie) { + reparent(ctx, subtrie); + *trie_p = subtrie; + + reparent(user, trie); + user->trie = trie; + return 0; + } + + /* + * Merge the two subtries. + */ + if (fr_trie_merge(user, &user->trie, user->trie, trie, start_bit) < 0) { + return -1; + } + + reparent(ctx, subtrie); + *trie_p = subtrie; + return 0; + } + + if (IS_USER(trie)) { + fr_trie_user_t *user = GET_USER(trie); + + return fr_trie_key_insert(user, &user->trie, key, start_bit, end_bit, subtrie); + } + +#ifdef WITH_PATH_COMPRESSION + /* + * The trie is a path. Create a path from the key, and + * merge it into the previous path. + */ + if (IS_PATH(trie)) { + int lcp; + fr_trie_path_t *path2; + + path = GET_PATH(trie); + + assert((start_bit & 0x07) == path->start_bit); + + lcp = fr_trie_path_lcp(path->key, path->length, + key + BYTEOF(start_bit), + end_bit - start_bit, + path->start_bit); + if (lcp == path->length) { + assert(!IS_PATH(path->trie)); + + return fr_trie_key_insert(path, &path->trie, + key, start_bit + lcp, end_bit, subtrie); + } + + /* + * Create a prefix, and merge + */ + path2 = fr_trie_path_alloc(ctx, key, start_bit, end_bit, subtrie); + if (!path2) return -1; + + trie = fr_trie_path_merge_paths(ctx, path, path2, start_bit); + if (!trie) { + printf("FAIL %d\n", __LINE__); + talloc_free(path2); + return -1; + } + + *trie_p = trie; + return 0; + } +#endif + + assert(IS_NODE(trie)); + node = trie; + fr_trie_node_verify(node); + + next = start_bit + node->size; + + /* + * The key stops in the middle of this node. + * + * Create a new node of the appropriate size. + * Add the subtrie to it at the appropriate + * offset. Then merge the current node into the + * new one. + */ + if (next > end_bit) { + fr_trie_node_t *node2; + int size = end_bit - start_bit; + + node2 = fr_trie_node_alloc(node, size); + if (!node2) { + assert(0 == 1); + fprintf(stderr, "FAILED %d\n", __LINE__); + return -1; + } + + chunk = get_chunk(key, size, start_bit, end_bit); + reparent(node2, subtrie); + node2->entry[chunk] = subtrie; + node2->used = 1; + + if (fr_trie_merge(ctx, trie_p, node2, node, start_bit) < 0) { + fprintf(stderr, "FAILED %d\n", __LINE__); + return -1; + } + + // @todo - normalize trie_p? + + return 0; + } + + chunk = get_chunk(key, node->size, start_bit, end_bit); + assert(chunk < (1 << node->size)); + + incr = (node->entry[chunk] == NULL); + + rcode = fr_trie_key_insert(node, &node->entry[chunk], key, next, end_bit, subtrie); + if (rcode < 0) return rcode; + + assert(node->entry[chunk] != NULL); + node->used += incr; + + return 0; +} + +/** Remove a key in a trie and return the removed user ctx, if any + * + * The key length MUST match the entries in the trie. + * + * @param ft the trie + * @param[in,out] + * @param key the key + * @param start_bit the start bit + * @param end_bit the end bit + * @return + * - NULL on no matching key + * - void* user ctx for the removed key + * + * We delete the nodes as we going down the stack, and then collapse + * empty nodes going back up the stack. + */ +static void *fr_trie_key_remove(TALLOC_CTX *ctx, void **entry, uint8_t const *key, int start_bit, int end_bit) +{ + void *data; + + if (IS_USER(*entry)) { + fr_trie_user_t *user; + + user = GET_USER(*entry); + + /* + * Still have bits to eat, go get them. + */ + if (start_bit < end_bit) { + return fr_trie_key_remove(user, &user->trie, key, start_bit, end_bit); + } + + if (user->trie) reparent(ctx, user->trie); + + *entry = user->trie; + data = user->data; + talloc_free(user); + return data; + } + + if (IS_NODE(*entry)) { + uint16_t chunk; + fr_trie_node_t *node = *entry; + + fr_trie_node_verify(node); + + /* + * The key is too short for this trie. + */ + if ((start_bit + node->size) > end_bit) { + fprintf(stderr, "FAIL %d %zd + %zd = %zd, vs %zd\n", __LINE__, + start_bit, node->size, start_bit + node->size, end_bit); + return NULL; + } + + chunk = get_chunk(key, node->size, start_bit, end_bit); + + /* + * This entry is empty, fail. + */ + if (!node->entry[chunk]) { + fprintf(stderr, "FAIL %d\n", __LINE__); + return NULL; + } + + fr_trie_node_verify(node); + + /* + * Recursively remove the key. If that fails, + * return. + */ + data = fr_trie_key_remove(node, &node->entry[chunk], key, start_bit + node->size, end_bit); + if (!data) { + fprintf(stderr, "FAIL %d\n", __LINE__); + return NULL; + } + + /* + * The key was removed, but this entry still + * points to a non-empty trie. See if we need to + * collapse it. + */ + if (node->entry[chunk]) { +#ifdef WITH_PATH_COMPRESSION + if (node->used == 1) { + goto collapse_chunk; + } +#endif + return data; + } + + /* + * One fewer entry is used. If there are still + * used entries or a default, just return the + * user ctx. + */ + node->used--; + + /* + * @todo - reverse level compression? if the + * node size is larger than the default, and less + * than half of the entries are used, split node + * into a smaller node, which points to children. + */ + + /* + * Only one entry? Try to convert the node into + * a path. + */ +#ifdef WITH_PATH_COMPRESSION + if (node->used == 1) { + bool found; + int i; + void *trie; + + found = false; + for (i = 0; i < (1 << node->size); i++) { + if (node->entry[i]) { + found = true; + chunk = i; + break; + } + } + + assert(found); + +collapse_chunk: + /* + * Convert the node to a PATH. + */ + trie = fr_trie_path_prefix_add(talloc_parent(node), node->entry[chunk], + node->size, chunk, start_bit); + if (trie != NULL) { + talloc_free(node); + *entry = trie; + } + return data; + } +#endif + + if (node->used) { + fr_trie_node_verify(node); + return data; + } + + /* + * Our node is completely empty. Free ourselves, + * and tell our parent that we're empty. + */ + talloc_free(node); + *entry = NULL; + return data; + } + +#ifdef WITH_PATH_COMPRESSION + if (IS_PATH(*entry)) { + int lcp; + fr_trie_path_t *path = GET_PATH(*entry); + + fr_trie_path_verify(path); + + /* + * Find out how much of the key matches this path + * entry. + * + * If it's only a partial match, we fail. + */ + lcp = fr_trie_path_lcp(path->key, path->length, + key + BYTEOF(start_bit), + (end_bit - start_bit), + path->start_bit); + if (lcp < path->length) { + printf("FAIL %d\n", __LINE__); + return NULL; + } + + fr_trie_path_verify(path); + + /* + * Remove the path recursively. If not, we fail. + */ + data = fr_trie_key_remove(path, &path->trie, key, start_bit + path->length, end_bit); + if (!data) { + fprintf(stderr, "FAIL %d\n", __LINE__); + return NULL; + } + + /* + * This path points to a path. Concatenate the + * two of them together. + */ + if (IS_PATH(path->trie)) { + fr_trie_path_t *suffix = GET_PATH(path->trie); + + fr_trie_path_verify(suffix); + + if (fr_trie_path_concatenate(path, path->key, path->start_bit, path->length, + suffix->key, suffix->start_bit, suffix->length) == 0) { + reparent(path, suffix->trie); + path->trie = suffix->trie; + + talloc_free(suffix); + fr_trie_path_verify(path); + } + } + + /* + * This path points to a non-empty trie, leave + * it. + */ + if (path->trie) { + fr_trie_path_verify(path); + return data; + } + + talloc_free(path); + *entry = NULL; + return data; + } +#endif + + return NULL; +} + + + +/** Allocate a trie + * + * @param ctx The talloc ctx + * @return + * - NULL on error + * - fr_trie_node_t on success + */ +fr_trie_t *fr_trie_alloc(TALLOC_CTX *ctx) +{ + fr_trie_t *ft; + + ft = talloc_zero(ctx, fr_trie_t); + if (!ft) return NULL; + +#if 0 + /* + * Allocate the first node with an 8-way fanout. + */ + ft->trie = fr_trie_node_alloc(ft, 8); + if (!ft->trie) { + talloc_free(ft); + return NULL; + } +#endif + + return ft; +} + +/** Insert a key and user ctx into a trie + * + * @param ft the trie + * @param key the key + * @param keylen key length in bits + * @param data user ctx information to associated with the key + * @return + * - <0 on error + * - 0 on success + */ +int fr_trie_insert(fr_trie_t *ft, void const *key, size_t keylen, void *data) +{ + fr_trie_user_t *user; + + if (keylen > (1 << 16)) return -1; + + /* + * Do a lookup before insertion. If we tried to insert + * the key with new nodes and then discovered a conflict, + * we would not be able to undo the process. This check + * ensures that the insertion can modify the trie in + * place without worry. + */ + if (ft->trie && + (fr_trie_key_match(ft->trie, key, 0, keylen, true) != NULL)) { + fprintf(stderr, "FAILED %d\n", __LINE__); + return -1; + } + + user = talloc_zero_size(ft, sizeof(*user)); + if (!user) return -1; + + user->data = data; + user->number = node_number++; + + if (fr_trie_key_insert(ft, &ft->trie, key, 0, keylen, PUT_USER(user)) < 0) { + talloc_free(user); + return -1; + } + + return 0; +} + + +/** Remove a key and return the associated user ctx + * + * The key must match EXACTLY. This is not a prefix match. + * + * @param ft the trie + * @param key the key + * @param keylen key length in bits + * @return + * - NULL on not found + * - user ctx data on success + */ +void *fr_trie_remove(fr_trie_t *ft, void const *key, size_t keylen) +{ + if (keylen > (1 << 16)) return NULL; + + if (!ft->trie) return NULL; + + return fr_trie_key_remove(ft, (void **) &ft->trie, key, 0, (int) keylen); +} + +/** Lookup a key in a trie and return user ctx, if any + * + * The key may be LONGER than entries in the trie. In which case the + * closest match is returned. + * + * @param ft the trie + * @param key the key bytes + * @param keylen length in bits of the key + * @return + * - NULL on not found + * - void* user ctx on found + */ +void *fr_trie_lookup(fr_trie_t *ft, void const *key, size_t keylen) +{ + if (keylen > (1 << 16)) return NULL; + + if (!ft->trie) return NULL; + + return fr_trie_key_match(ft->trie, key, 0, keylen, false); +} + +typedef struct fr_trie_callback_t fr_trie_callback_t; + +typedef int (*fr_trie_key_walk_t)(void *trie, fr_trie_callback_t *cb, int depth, bool more); + +struct fr_trie_callback_t { + fr_trie_t *ft; + + uint8_t *start; + uint8_t const *end; + + void *ctx; + + fr_trie_key_walk_t callback; + fr_trie_walk_t user_callback; +}; + +static int fr_trie_key_walk(void *trie, fr_trie_callback_t *cb, int depth, bool more) +{ + int i, used; + uint16_t base, mask; + int bytes, bits_used; + uint8_t *out; + fr_trie_node_t *node; + + /* + * Do the callback before anything else. + */ + if (cb->callback(trie, cb, depth, more) < 0) return -1; + + /* + * Nothing more to do, retun. + */ + if (!trie) { + assert(depth == 0); + return 0; + } + + /* + * User ctx data. Recurse (if necessary) for any + * subtrie. + */ + if (IS_USER(trie)) { + fr_trie_user_t *user = GET_USER(trie); + + if (!user->trie) return 0; + + return fr_trie_key_walk(user->trie, cb, depth, more); + } + + bytes = BYTES(depth); + + /* + * Bits used in the last byte. + */ + bits_used = depth & 0x07; + + /* + * Where we're writing the output string. + */ + out = cb->start + BYTEOF(depth); + + /* + * Mask out the low bits. They may have been written to + * in a previous invocation of the function. + */ + base = out[0]; + mask = ~((1 << (8 - bits_used)) - 1); + base &= mask; + + // @todo - check end against cb->end so we don't have buffer overflows... + +#ifdef WITH_PATH_COMPRESSION + /* + * Copy the path over. By bytes if possible, otherwise + * by bits. + */ + if (IS_PATH(trie)) { + fr_trie_path_t *path; + + path = GET_PATH(trie); + + fr_trie_path_verify(path); + + if (path->start_bit == 0) { + assert((depth & 0x07) == 0); + memcpy(out, path->key, BYTES(path->length)); + + } else { + out[0] = base | path->key[0]; + + if (BYTES(path->end_bit) > 0) { + memcpy(out + 1, path->key + 1, BYTES(path->end_bit) - 1); + } + } + + return fr_trie_key_walk(path->trie, cb, depth + path->length, more); + } +#endif + + node = trie; + fr_trie_node_verify(node); + + /* + * Number of bytes we will have in the output buffer. + */ + bytes = BYTES(depth + node->size); + base <<= 8; + used = 0; + + for (i = 0; i < (1 << node->size); i++) { + uint16_t chunk; + + /* + * Nothing on this terminal node, skip it. + */ + if (!node->entry[i]) continue; + + /* + * "base" has the top "bits_used" bits used, with + * the bits from the output buffer. + * + * "chunk" has the lower "node->size" bits used with + * the bits for this entry. + * + * Shift "chunk" left. OR them together, and + * store them in the output buffer. + */ + chunk = i; /* node->size bits are used here */ + chunk <<= (16 - node->size - bits_used); + chunk |= base; + + out[0] = chunk >> 8; + out[1] = chunk & 0xff; + + used++; + + if (fr_trie_key_walk(node->entry[i], cb, depth + node->size, + more || (used < node->used)) < 0) { + return -1; + } + } + + return 0; +} + +#ifdef TESTING +/** Dump a trie edge in canonical form. + * + */ +static void fr_trie_dump_edge(FILE *fp, void *trie) +{ + if (IS_USER(trie)) { + fr_trie_user_t *user = GET_USER(trie); + + fprintf(fp, "NODE-%d\n", user->number); + return; + } + + if (IS_NODE(trie)) { + fr_trie_node_t *node = trie; + + fprintf(fp, "NODE-%d\n", node->number); + return; + } + +#ifdef WITH_PATH_COMPRESSION + if (IS_PATH(trie)) { + fr_trie_path_t *path = GET_PATH(trie); + + fprintf(fp, "NODE-%d\n", path->number); + fr_trie_path_verify(path); + return; + } +#endif +} + + +/** Dump the trie nodes + * + */ +static int fr_trie_dump_cb(void *trie, fr_trie_callback_t *cb, int keylen, UNUSED bool more) +{ + int i, bytes; + FILE *fp = cb->ctx; + fr_trie_node_t *node; + + if (!trie) return 0; + + bytes = BYTES(keylen); + + if (IS_USER(trie)) { + fr_trie_user_t *user = GET_USER(trie); + + fprintf(fp, "{ NODE-%d\n", user->number); + fprintf(fp, "\ttype\tUSER\n"); + fprintf(fp, "\tkey\t{%d}%.*s\n", keylen, bytes, cb->start); + + fprintf(fp, "\tdata\t\"%s\"\n", (char const *) user->data); + if (!user->trie) { + fprintf(fp, "}\n\n"); + return 0; + } + + fprintf(fp, "\tnext\t"); + fr_trie_dump_edge(fp, user->trie); + fprintf(fp, "}\n\n"); + return 0; + } + +#ifdef WITH_PATH_COMPRESSION + if (IS_PATH(trie)) { + fr_trie_path_t *path = GET_PATH(trie); + fprintf(fp, "{ NODE-%d\n", path->number); + fprintf(fp, "\ttype\tPATH\n"); + fprintf(fp, "\tkey\t{%d}%.*s\n", keylen, bytes, cb->start); + + fprintf(fp, "\tstart\t%d\n", (int) path->start_bit); + fprintf(fp, "\tend\t%d\n", (int) path->end_bit); + fprintf(fp, "\tlength\t%d\n", (int) path->length); + fprintf(fp, "\tpath\t"); + + for (i = 0; i < BYTES(path->end_bit); i++) { + fprintf(fp, "%02x", path->key[i]); + } + fprintf(fp, "\n"); + + fr_trie_path_verify(path); + + fprintf(fp, "\tnext\t"); + fr_trie_dump_edge(fp, path->trie); + + fprintf(fp, "}\n\n"); + return 0; + } +#endif + + + node = trie; + fr_trie_node_verify(node); + + fprintf(fp, "{ NODE-%d\n", node->number); + fprintf(fp, "\ttype\tTRIE\n"); + fprintf(fp, "\tkey\t{%d}%.*s\n", keylen, bytes, cb->start); + + fprintf(fp, "\tbits\t%d\n", node->size); + fprintf(fp, "\tused\t%d\n", node->used); + + for (i = 0; i < (1 << node->size); i++) { + if (!node->entry[i]) continue; + + fprintf(fp, "\t%02x\t", (int) i); + fr_trie_dump_edge(fp, node->entry[i]); + } + fprintf(fp, "}\n\n"); + + return 0; +} + +/** Print the strings accepted by a trie to a file + * + */ +static int fr_trie_print_cb(void *trie, fr_trie_callback_t *cb, int keylen, UNUSED bool more) +{ + int bytes; + FILE *fp = cb->ctx; + fr_trie_user_t *user; + + if (!trie || !IS_USER(trie)) { + return 0; + } + + bytes = BYTES(keylen); + user = GET_USER(trie); + + if ((keylen & 0x07) != 0) { + fprintf(fp, "{%d}%.*s\t%s\n", keylen, bytes, cb->start, (char const *) user->data); + } else { + fprintf(fp, "%.*s\t%s\n", bytes, cb->start, (char const *) user->data); + } + + return 0; +} +#endif /* TESTING */ + + +/** Implement the user-visible side of the walk callback. + * + */ +static int fr_trie_user_cb(void *trie, fr_trie_callback_t *cb, int keylen, UNUSED bool more) +{ + fr_trie_user_t *user; + + if (!trie || !IS_USER(trie)) return 0; + + user = GET_USER(trie); + + if (cb->user_callback(cb->ctx, cb->start, keylen, user->data) < 0) { + return -1; + } + + return 0; +} + +int fr_trie_walk(fr_trie_t *ft, void *ctx, fr_trie_walk_t callback) +{ + fr_trie_callback_t my_cb; + uint8_t buffer[8192]; + + my_cb.ft = ft; + my_cb.start = buffer; + my_cb.end = buffer + sizeof(buffer); + my_cb.callback = fr_trie_user_cb; + my_cb.user_callback = callback; + my_cb.ctx = ctx; + + /* + * Call the internal walk function to do the work. + */ + return fr_trie_key_walk(ft->trie, &my_cb, 0, false); +} + +#ifdef TESTING +static bool print_lineno = false; + +typedef struct fr_trie_sprint_ctx_t { + char *start; + char *buffer; + size_t buflen; +} fr_trie_sprint_ctx_t; + + +/** Print the strings accepted by a trie to one line + * + * @todo - add a 'more' flag... + */ +static int fr_trie_sprint_cb(void *trie, fr_trie_callback_t *cb, int keylen, bool more) +{ + int bytes, len; + fr_trie_sprint_ctx_t *ctx; + fr_trie_user_t *user; + + ctx = cb->ctx; + + if (!trie) { + len = snprintf(ctx->buffer, ctx->buflen, "{}"); + goto done; + } + + if (!IS_USER(trie)) return 0; + + bytes = BYTES(keylen); + user = GET_USER(trie); + + if (!user->trie && !more) { + len = snprintf(ctx->buffer, ctx->buflen, "%.*s=%s", + bytes, cb->start, (char const *) user->data); + } else { + len = snprintf(ctx->buffer, ctx->buflen, "%.*s=%s,", + bytes, cb->start, (char const *) user->data); + } + +done: + ctx->buffer += len; + ctx->buflen -= len; + + return 0; +} + + +/** Parse a string into bits + key + * + * The format is one of: + * + * - string such as "abcdef" + * - string prefixed with a bit length, {4}a + */ +static int arg2key(char *arg, char **key, int *length) +{ + char *p; + int bits, size; + + if (*arg != '{') { + *key = arg; + *length = BITSOF(strlen(arg)); + return 0; + } + + p = strchr(arg, '}'); + if (!p) { + fprintf(stderr, "Failed to find end '}' for {bits}\n"); + return -1; + } + + bits = BITSOF(strlen(p + 1)); + if (!bits) { + fprintf(stderr, "No key found in in '%s'\n", arg); + return -1; + } + + size = atoi(arg + 1); /* ignore end character... */ + if (size > bits) { + fprintf(stderr, "Length '%d' is longer than bits in key %s", + size, p + 1); + } + + *key = p + 1; + *length = size; + + return 0; +} + +/** Our TALLOC_CTX for the data we put into the trie. + * + * Most people don't need to do this, they can just insert their own + * data. + */ +static void *data_ctx = NULL; + +/** Insert a key + data into a trie. + * + */ +static int command_insert(fr_trie_t *ft, UNUSED int argc, char **argv, UNUSED char *out, UNUSED size_t outlen) +{ + int bits; + void *answer, *data; + char *key; + + if (arg2key(argv[0], &key, &bits) < 0) { + return -1; + } + + /* + * This has to stick around in between command + * invocations. + */ + data = talloc_strdup(data_ctx, argv[1]); + if (!data) { + fprintf(stderr, "OOM\n"); + return -1; + } + + if (fr_trie_insert(ft, key, bits, data) < 0) { + fprintf(stderr, "Failed inserting key %s=%s\n", key, argv[1]); + return -1; + } + + answer = fr_trie_key_match(ft->trie, (uint8_t *) key, 0, bits, true); + if (!answer) { + fprintf(stderr, "Could not match key %s\n", key); + return -1; + } + + if (answer != data) { + fprintf(stderr, "Inserted %s, but looked up %s\n", argv[1], answer); + return -1; + } + + return 0; +} + +/** Verify a trie recursively + * + * For sanity reasons, this command runs but doesn't do anything if + * the code is built with no trie verification. + */ +static int command_verify(fr_trie_t *ft, UNUSED int argc, UNUSED char **argv, UNUSED char *out, UNUSED size_t outlen) +{ +#ifdef WITH_TRIE_VERIFY + fr_trie_verify(ft->trie); +#else + assert(ft != NULL); +#endif + return 0; +} + +/** Print the keys accepted by a trie + * + * The strings are printed to stdout. + * + * @todo - allow printing to a file. + */ +static int command_keys(fr_trie_t *ft, UNUSED int argc, UNUSED char **argv, char *out, size_t outlen) +{ + fr_trie_callback_t my_cb; + + my_cb.ft = ft; + my_cb.start = (uint8_t *) out; + my_cb.end = (uint8_t *) (out + outlen); + my_cb.callback = fr_trie_print_cb; + my_cb.user_callback = NULL; + my_cb.ctx = stdout; + + /* + * Call the internal walk function to do the work. + */ + return fr_trie_key_walk(ft->trie, &my_cb, 0, false); +} + + +/** Dump the trie in internal format + * + * The information is printed to stdout. + * + * For sanity reasons, this command runs but doesn't do anything if + * the code is built with no trie dumping. + * + * @todo - allow printing to a file. + */ +static int command_dump(fr_trie_t *ft, UNUSED int argc, UNUSED char **argv, UNUSED char *out, UNUSED size_t outlen) +{ + fr_trie_callback_t my_cb; + + my_cb.ft = ft; + my_cb.start = (uint8_t *) out; + my_cb.end = (uint8_t *) (out + outlen); + my_cb.callback = fr_trie_dump_cb; + my_cb.user_callback = NULL; + my_cb.ctx = stdout; + + /* + * Call the internal walk function to do the work. + */ + return fr_trie_key_walk(ft->trie, &my_cb, 0, false); + + return 0; +} + + +/** Clear the entire trie without caring what's in it. + * + */ +static int command_clear(fr_trie_t *ft, UNUSED int argc, UNUSED char **argv, UNUSED char *out, UNUSED size_t outlen) +{ + if (!ft->trie) return 0; + + if (IS_USER(ft->trie)) { + talloc_free(GET_USER(ft->trie)); + } +#ifdef WITH_PATH_COMPRESSION + else if (IS_PATH(ft->trie)) { + talloc_free(GET_PATH(ft->trie)); + } +#endif + else { + talloc_free(ft->trie); + } + + ft->trie = NULL; + + /* + * Clean up our internal data ctx, too. + */ + talloc_free(data_ctx); + data_ctx = talloc_init("data_ctx"); + + return 0; +} + + +/** Turn on line number debugging. + * + * @todo - add general "debug" functionality. + */ +static int command_lineno(UNUSED fr_trie_t *ft, UNUSED int argc, char **argv, UNUSED char *out, UNUSED size_t outlen) +{ + if (strcmp(argv[0], "true") == 0) { + print_lineno = true; + } else { + print_lineno = false; + } + + return 0; +} + + +/** Match an exact key + length + * + * Normally, the "lookup" returns the longest prefix match, so that + * *long* key lookups can return *short* matches. + * + * In some cases, we want to know if an exact key is in the trie. + * For those cases, we use this function. + */ +static int command_match(fr_trie_t *ft, UNUSED int argc, char **argv, char *out, size_t outlen) +{ + int bits; + void *answer; + char *key; + + if (arg2key(argv[0], &key, &bits) < 0) { + return -1; + } + + answer = fr_trie_key_match(ft->trie, (uint8_t *) key, 0, bits, true); + if (!answer) { + strlcpy(out, "{}", outlen); + return 0; + } + + strlcpy(out, answer, outlen); + + return 0; +} + + +/** Look up a key and return user ctx data. + * + * This is done by longest prefix match, not exact match. + */ +static int command_lookup(fr_trie_t *ft, UNUSED int argc, char **argv, char *out, size_t outlen) +{ + int bits; + void *answer; + char *key; + + if (arg2key(argv[0], &key, &bits) < 0) { + return -1; + } + + answer = fr_trie_lookup(ft, key, bits); + if (!answer) { + strlcpy(out, "{}", outlen); + return 0; + } + + strlcpy(out, answer, outlen); + + return 0; +} + + +/** Remove a key from the trie. + * + * The key has to match exactly. + */ +static int command_remove(fr_trie_t *ft, UNUSED int argc, char **argv, char *out, size_t outlen) +{ + int bits; + void *answer; + char *key; + + if (arg2key(argv[0], &key, &bits) < 0) { + return -1; + } + + answer = fr_trie_remove(ft, key, bits); + if (!answer) { + fprintf(stderr, "Could not remove key %s\n", key); + return -1; + } + + strlcpy(out, answer, outlen); + + talloc_free(answer); + + /* + * We now try to find an exact match. i.e. we don't want + * to find a shorter prefix. + */ + answer = fr_trie_key_match(ft->trie, (uint8_t *) key, 0, bits, true); + if (answer) { + fprintf(stderr, "Still in trie after 'remove' for key %s, found data %s\n", key, (char const *) answer); + return -1; + } + + return 0; +} + + +/** Print a trie to a string + * + * The trie is printed one one line. If the trie contains keys which + * are not on a byte boundary, well... too bad. It gets printed + * terribly. + */ +static int command_print(fr_trie_t *ft, UNUSED int argc, UNUSED char **argv, char *out, size_t outlen) +{ + fr_trie_callback_t my_cb; + fr_trie_sprint_ctx_t my_sprint; + uint8_t buffer[8192]; /* working buffer */ + + /* + * Where the output data goes. + */ + my_sprint.start = out; + my_sprint.buffer = out; + my_sprint.buflen = outlen; + + /* + * Where the keys are built. + */ + my_cb.ft = ft; + my_cb.start = buffer; + my_cb.end = buffer + sizeof(buffer); + my_cb.callback = fr_trie_sprint_cb; + my_cb.user_callback = NULL; + my_cb.ctx = &my_sprint; + + /* + * Call the internal walk function to do the work. + */ + return fr_trie_key_walk(ft->trie, &my_cb, 0, false); +} + + +/** Do insert / lookup / remove all at once. + * + * Sometimes it's more useful to do insert / lookup / remove for + * simple keys. + */ +static int command_path(fr_trie_t *ft, UNUSED int argc, char **argv, char *out, size_t outlen) +{ + void *data; + void *answer; + + data = talloc_strdup(ft, argv[1]); /* has to be malloc'd data, sorry */ + if (!data) { + fprintf(stderr, "OOM\n"); + return -1; + } + + if (fr_trie_insert(ft, argv[0], BITSOF(strlen(argv[0])), data) < 0) { + fprintf(stderr, "Could not insert key %s=%s\n", argv[0], argv[1]); + return -1; + } + + answer = fr_trie_lookup(ft, argv[0], BITSOF(strlen(argv[0]))); + if (!answer) { + fprintf(stderr, "Could not look up key %s\n", argv[0]); + return -1; + } + + if (answer != data) { + fprintf(stderr, "Expected to find %s, got %s\n", argv[1], answer); + return -1; + } + + /* + * Call the command 'print' to print out the key. + */ + (void) command_print(ft, argc, argv, out, outlen); + + answer = fr_trie_remove(ft, (uint8_t const *) argv[0], BITSOF(strlen(argv[0]))); + if (!answer) { + fprintf(stderr, "Could not remove key %s\n", argv[0]); + return -1; + } + + if (answer != data) { + fprintf(stderr, "Expected to remove %s, got %s\n", argv[1], answer); + return -1; + } + + talloc_free(answer); + + return 0; +} + + +/** Return the longest common prefix of two bit strings. + * + * This function doesn't use argv2key because that makes the input + * look confusing. And, we want to be able to specify a common start + * bit. + */ +static int command_lcp(UNUSED fr_trie_t *ft, UNUSED int argc, char **argv, char *out, size_t outlen) +{ + int lcp; + int keylen1, keylen2; + int start_bit; + uint8_t const *key1, *key2; + + if (argc == 2) { + key1 = (uint8_t const *) argv[0]; + keylen1 = BITSOF(strlen(argv[0])); + + key2 = (uint8_t const *) argv[1]; + keylen2 = BITSOF(strlen(argv[1])); + start_bit = 0; + + } else if (argc == 5) { + key1 = (uint8_t const *) argv[0]; + keylen1 = atoi(argv[1]); + if ((keylen1 < 0) || (keylen1 > (int) BITSOF(strlen(argv[0])))) { + fprintf(stderr, "length of key1 %s is larger than string length %ld\n", + argv[1], BITSOF(strlen(argv[0]))); + return -1; + } + + key2 = (uint8_t const *) argv[2]; + keylen2 = atoi(argv[3]); + if ((keylen2 < 0) || (keylen2 > (int) BITSOF(strlen(argv[2])))) { + fprintf(stderr, "length of key2 %s is larger than string length %ld\n", + argv[3], BITSOF(strlen(argv[2]))); + return -1; + } + + start_bit = atoi(argv[4]); + if ((start_bit < 0) || (start_bit > 7)) { + fprintf(stderr, "start_bit has invalid value %s\n", argv[4]); + return -1; + } + + } else { + fprintf(stderr, "Invalid number of arguments\n"); + return -1; + } + + lcp = fr_trie_path_lcp(key1, keylen1, key2, keylen2, start_bit); + + snprintf(out, outlen, "%d", lcp); + return 0; +} + + +/** A function to parse a trie command line. + * + */ +typedef int (*fr_trie_function_t)(fr_trie_t *ft, int argc, char **argv, char *out, size_t outlen); + +/** Data structure which holds the trie command name, function, etc. + * + */ +typedef struct fr_trie_command_t { + char const *name; + fr_trie_function_t function; + int min_argc; + int max_argc; + bool output; +} fr_trie_command_t; + + +/** The trie commands for debugging. + * + */ +static fr_trie_command_t commands[] = { + { "lcp", command_lcp, 2, 5, true }, + { "path", command_path, 2, 2, true }, + { "insert", command_insert, 2, 2, false }, + { "match", command_match, 1, 1, true }, + { "lookup", command_lookup, 1, 1, true }, + { "remove", command_remove, 1, 1, true }, + { "print", command_print, 0, 0, true }, + { "dump", command_dump, 0, 0, false }, + { "keys", command_keys, 0, 0, false }, + { "verify", command_verify, 0, 0, false }, + { "lineno", command_lineno, 1, 1, false }, + { "clear", command_clear, 0, 0, false }, + { NULL, NULL, 0, 0} +}; + +#define MAX_ARGC (16) + +int main(int argc, char **argv) +{ + int lineno = 0; + int rcode = 0; + fr_trie_t *ft; + FILE *fp; + int my_argc; + char *my_argv[MAX_ARGC]; + char buffer[8192]; + char output[8192]; + + if (argc < 2) { + fprintf(stderr, "Please specify filename\n"); + exit(1); + } + + fp = fopen(argv[1], "r"); + if (!fp) { + fprintf(stderr, "Failed opening %s: %s\n", argv[1], strerror(errno)); + exit(1); + } + + /* + * Tell us if we leaked memory. + */ + talloc_enable_leak_report_full(); + + data_ctx = talloc_init("data_ctx"); + + ft = fr_trie_alloc(NULL); + if (!ft) { + fprintf(stderr, "Failed creating trie\n"); + exit(1); + } + + while (fgets(buffer, sizeof(buffer), fp) != NULL) { + int i, cmd; + char *p; + + lineno++; + + /* + * Remove comments. + */ + for (p = buffer; *p != '\0'; p++) { + if (*p == '#') { + *p = '\0'; + break; + } + } + + /* + * Skip leading whitespace. + */ + p = buffer; + while (isspace((int) *p)) p++; + + /* + * Skip (now) blank lines. + */ + if (!*p) continue; + + my_argc = fr_dict_str_to_argv(p, my_argv, MAX_ARGC); + + cmd = -1; + for (i = 0; commands[i].name != NULL; i++) { + if (strcmp(my_argv[0], commands[i].name) != 0) continue; + + cmd = i; + break; + } + + if (cmd < 0) { + fprintf(stderr, "Unknown command '%s' at line %d\n", + my_argv[0], lineno); + rcode = 1; + break; + } + + /* + * argv[0] is the command. + * argv[argc-1] is the output. + */ + if (((commands[cmd].min_argc + 1 + commands[cmd].output) > my_argc) || + ((commands[cmd].max_argc + 1 + commands[cmd].output) < my_argc)) { + fprintf(stderr, "Invalid number of arguments to %s at line %d. Expected %d, got %d\n", + my_argv[0], lineno, commands[cmd].min_argc + 1, my_argc - 1); + exit(1); + } + + if (print_lineno) { + printf("%d ", lineno); + fflush(stdout); + } + + if (commands[cmd].function(ft, my_argc - 1 - commands[cmd].output, &my_argv[1], output, sizeof(output)) < 0) { + fprintf(stderr, "Failed running %s at line %d\n", + my_argv[0], lineno); + exit(1); + } + + if (!commands[cmd].output) continue; + + if (strcmp(output, my_argv[my_argc - 1]) != 0) { + fprintf(stderr, "Failed running %s at line %d: Expected '%s' got '%s'\n", + my_argv[0], lineno, my_argv[my_argc - 1], output); + exit(1); + } + } + + fclose(fp); + + talloc_free(ft); + talloc_free(data_ctx); + + return rcode; +} +#endif diff --git a/src/lib/util/trie.mk b/src/lib/util/trie.mk new file mode 100644 index 00000000000..60bb56169f9 --- /dev/null +++ b/src/lib/util/trie.mk @@ -0,0 +1,6 @@ +TARGET := trie + +SRC_CFLAGS := -DTESTING +SOURCES := trie.c +TGT_LDLIBS := $(LIBS) +TGT_PREREQS := libfreeradius-util.a diff --git a/src/tests/all.mk b/src/tests/all.mk index a5ec8d7a235..dea00389f60 100644 --- a/src/tests/all.mk +++ b/src/tests/all.mk @@ -1,4 +1,4 @@ -SUBMAKEFILES := rbmonkey.mk eapol_test/all.mk dict/all.mk unit/all.mk map/all.mk xlat/all.mk keywords/all.mk util/all.mk auth/all.mk modules/all.mk daemon/all.mk +SUBMAKEFILES := rbmonkey.mk eapol_test/all.mk dict/all.mk trie/all.mk unit/all.mk map/all.mk xlat/all.mk keywords/all.mk util/all.mk auth/all.mk modules/all.mk daemon/all.mk # # Include all of the autoconf definitions into the Make variable space diff --git a/src/tests/certs/tmp/.gitignore b/src/tests/certs/tmp/.gitignore new file mode 100644 index 00000000000..73955078fe1 --- /dev/null +++ b/src/tests/certs/tmp/.gitignore @@ -0,0 +1,13 @@ +*.pem +*.key +*.crt +*.csr +*.p12 +*.old +*.attr +ca.der +dh +index.txt +random +serial +passwords.mk diff --git a/src/tests/certs/tmp/Makefile b/src/tests/certs/tmp/Makefile new file mode 100644 index 00000000000..202e4dba6d9 --- /dev/null +++ b/src/tests/certs/tmp/Makefile @@ -0,0 +1,161 @@ +###################################################################### +# +# Make file to be installed in /etc/raddb/certs to enable +# the easy creation of certificates. +# +# See the README file in this directory for more information. +# +# $Id$ +# +###################################################################### + +DH_KEY_SIZE = 2048 + +# +# Set the passwords +# +-include passwords.mk + +###################################################################### +# +# Make the necessary files, but not client certificates. +# +###################################################################### +.PHONY: all +all: index.txt serial dh server ca client ocsp + +.PHONY: client +client: client.pem + +.PHONY: ca +ca: ca.der + +.PHONY: server +server: server.pem server.vrfy + +.PHONY: ocsp +ocsp: ocsp.pem ocsp.vrfy + +.PHONY: verify +verify: server.vrfy client.vrfy + +passwords.mk: server.cnf ca.cnf client.cnf ocsp.cnf + @echo "PASSWORD_SERVER = '$(shell grep output_password server.cnf | sed 's/.*=//;s/^ *//')'" > $@ + @echo "PASSWORD_CA = '$(shell grep output_password ca.cnf | sed 's/.*=//;s/^ *//')'" >> $@ + @echo "PASSWORD_CLIENT = '$(shell grep output_password client.cnf | sed 's/.*=//;s/^ *//')'" >> $@ + @echo "PASSWORD_OCSP = '$(shell grep output_password ocsp.cnf | sed 's/.*=//;s/^ *//')'" >> $@ + @echo "USER_NAME = '$(shell grep emailAddress client.cnf | grep '@' | sed 's/.*=//;s/^ *//')'" >> $@ + @echo "CA_DEFAULT_DAYS = '$(shell grep default_days ca.cnf | sed 's/.*=//;s/^ *//')'" >> $@ + +###################################################################### +# +# Diffie-Hellman parameters +# +###################################################################### +dh: + openssl dhparam -outform PEM -out dh -2 $(DH_KEY_SIZE) + +###################################################################### +# +# Create a new self-signed CA certificate +# +###################################################################### +ca.key ca.pem: ca.cnf + @[ -f index.txt ] || $(MAKE) index.txt + @[ -f serial ] || $(MAKE) serial + openssl req -new -x509 -keyout ca.key -out ca.pem -config ./ca.cnf -days $(CA_DEFAULT_DAYS) + +ca.der: ca.pem + openssl x509 -inform PEM -outform DER -in ca.pem -out ca.der + +###################################################################### +# +# Create a new server certificate, signed by the above CA. +# +###################################################################### +server.csr server.key: server.cnf + openssl req -new -out server.csr -keyout server.key -config ./server.cnf + +server.crt: server.csr ca.key ca.pem + openssl ca -batch -keyfile ca.key -cert ca.pem -in server.csr -key $(PASSWORD_CA) -out server.crt -config ./server.cnf + +server.p12: server.crt + openssl pkcs12 -export -in server.crt -inkey server.key -out server.p12 -passin pass:$(PASSWORD_SERVER) -passout pass:$(PASSWORD_SERVER) + +server.pem: server.p12 + openssl pkcs12 -in server.p12 -out server.pem -passin pass:$(PASSWORD_SERVER) -passout pass:$(PASSWORD_SERVER) + +.PHONY: server.vrfy +server.vrfy: ca.pem + @openssl verify -CAfile ca.pem server.pem + +###################################################################### +# +# Create a new ocsp certificate, signed by the above CA. +# +###################################################################### +ocsp.csr ocsp.key: ocsp.cnf + openssl req -new -out ocsp.csr -keyout ocsp.key -config ./ocsp.cnf + +ocsp.crt: ocsp.csr ca.key ca.pem + openssl ca -batch -keyfile ca.key -cert ca.pem -in ocsp.csr -key $(PASSWORD_CA) -out ocsp.crt -config ./ocsp.cnf + +ocsp.p12: ocsp.crt + openssl pkcs12 -export -in ocsp.crt -inkey ocsp.key -out ocsp.p12 -passin pass:$(PASSWORD_OCSP) -passout pass:$(PASSWORD_OCSP) + +ocsp.pem: ocsp.p12 + openssl pkcs12 -in ocsp.p12 -out ocsp.pem -passin pass:$(PASSWORD_OCSP) -passout pass:$(PASSWORD_OCSP) + +.PHONY: ocsp.vrfy +ocsp.vrfy: ca.pem + @openssl verify -CAfile ca.pem ocsp.pem + +###################################################################### +# +# Create a new client certificate, signed by the the above CA. +# +###################################################################### +client.csr client.key: client.cnf + openssl req -new -out client.csr -keyout client.key -config ./client.cnf + +client.crt: client.csr ca.pem ca.key + openssl ca -batch -keyfile ca.key -cert ca.pem -in client.csr -key $(PASSWORD_CA) -out client.crt -config ./client.cnf + +client.p12: client.crt + openssl pkcs12 -export -in client.crt -inkey client.key -out client.p12 -passin pass:$(PASSWORD_CLIENT) -passout pass:$(PASSWORD_CLIENT) + +client.pem: client.p12 + openssl pkcs12 -in client.p12 -out client.pem -passin pass:$(PASSWORD_CLIENT) -passout pass:$(PASSWORD_CLIENT) + cp client.pem $(USER_NAME).pem + +.PHONY: client.vrfy +client.vrfy: ca.pem client.pem + c_rehash . + openssl verify -CApath . client.pem + +###################################################################### +# +# Miscellaneous rules. +# +###################################################################### +index.txt: + @touch index.txt + +serial: + @echo '01' > serial + +print: + openssl x509 -text -in server.crt + +printca: + openssl x509 -text -in ca.pem + +clean: + @rm -f *~ *old client.csr client.key client.crt client.p12 client.pem + +# +# Make a target that people won't run too often. +# +distclean: + rm -f *~ dh *.csr *.crt *.p12 *.der *.pem *.key index.txt* \ + serial* *\.0 *\.1 diff --git a/src/tests/certs/tmp/README b/src/tests/certs/tmp/README new file mode 100644 index 00000000000..4d5be1052d4 --- /dev/null +++ b/src/tests/certs/tmp/README @@ -0,0 +1,225 @@ + This directory contains scripts to create the server certificates. +To make a set of default (i.e. test) certificates, simply type: + +$ ./bootstrap + + The "openssl" command will be run against the sample configuration +files included here, and will make a self-signed certificate authority +(i.e. root CA), and a server certificate. This "root CA" should be +installed on any client machine needing to do EAP-TLS, PEAP, or +EAP-TTLS. + + The Microsoft "XP Extensions" will be automatically included in the +server certificate. Without those extensions Windows clients will +refuse to authenticate to FreeRADIUS. + + The root CA and the "XP Extensions" file also contain a crlDistributionPoints +attribute. The latest release of Windows Phone needs this to be present +for the handset to validate the RADIUS server certificate. The RADIUS +server must have the URI defined but the CA need not have...however it +is best practice for a CA to have a revocation URI. Note that whilst +the Windows Mobile client cannot actually use the CRL when doing 802.1X +it is recommended that the URI be an actual working URL and contain a +revocation format file as there may be other OS behaviour at play and +future OSes that may do something with that URI. + + In general, you should use self-signed certificates for 802.1x (EAP) +authentication. When you list root CAs from other organisations in +the "ca_file", you permit them to masquerade as you, to authenticate +your users, and to issue client certificates for EAP-TLS. + + If FreeRADIUS was configured to use OpenSSL, then simply starting +the server in root in debugging mode should also create test +certificates, i.e.: + +$ radiusd -X + + That will cause the EAP-TLS module to run the "bootstrap" script in +this directory. The script will be executed only once, the first time +the server has been installed on a particular machine. This bootstrap +script SHOULD be run on installation of any pre-built binary package +for your OS. In any case, the script will ensure that it is not run +twice, and that it does not over-write any existing certificates. + + If you already have CA and server certificates, rename (or delete) +this directory, and create a new "certs" directory containing your +certificates. Note that the "make install" command will NOT +over-write your existing "raddb/certs" directory, which means that the +"bootstrap" command will not be run. + + + NEW INSTALLATIONS OF FREERADIUS + + + We suggest that new installations use the test certificates for +initial tests, and then create real certificates to use for normal +user authentication. See the instructions below for how to create the +various certificates. The old test certificates can be deleted by +running the following command: + +$ rm -f *.pem *.der *.csr *.crt *.key *.p12 serial* index.txt* + + Then, follow the instructions below for creating real certificates. + + Once the final certificates have been created, you can delete the +"bootstrap" command from this directory, and delete the +"make_cert_command" configuration from the "tls" sub-section of +eap.conf. + + If you do not want to enable EAP-TLS, PEAP, or EAP-TTLS, then delete +the relevant sub-sections from the "eap.conf" file. + + + MAKING A ROOT CERTIFICATE + + +$ vi ca.cnf + + Edit the "input_password" and "output_password" fields to be the + password for the CA certificate. + + Edit the [certificate_authority] section to have the correct values + for your country, state, etc. + +$ make ca.pem + + This step creates the CA certificate. + +$ make ca.der + + This step creates the DER format of the self-signed certificate, + which is can be imported into Windows. + + + MAKING A SERVER CERTIFICATE + + +$ vi server.cnf + + Edit the "input_password" and "output_password" fields to be the + password for the server certificate. + + Edit the [server] section to have the correct values for your + country, state, etc. Be sure that the commonName field here is + different from the commonName for the CA certificate. + +$ make server.pem + + This step creates the server certificate. + + If you have an existing certificate authority, and wish to create a + certificate signing request for the server certificate, edit + server.cnf as above, and type the following command. + +$ make server.csr + + You will have to ensure that the certificate contains the XP + extensions needed by Microsoft clients. + + + MAKING A CLIENT CERTIFICATE + + + Client certificates are used by EAP-TLS, and optionally by EAP-TTLS +and PEAP. The following steps outline how to create a client +certificate that is signed by the server certificate created above. +You will have to have the password for the server certificate in the +"input_password" and "output_password" fields of the server.cnf file. + + +$ vi client.cnf + + Edit the "input_password" and "output_password" fields to be the + password for the client certificate. You will have to give these + passwords to the end user who will be using the certificates. + + Edit the [client] section to have the correct values for your + country, state, etc. Be sure that the commonName field here is + the User-Name that will be used for logins! + +$ make client.pem + + The users certificate will be in "emailAddress.pem", + i.e. "user@example.com.pem". + + To create another client certificate, just repeat the steps for + making a client certificate, being sure to enter a different login + name for "commonName", and a different password. + + + PERFORMANCE + + + EAP performance for EAP-TLS, TTLS, and PEAP is dominated by SSL + calculations. That is, a normal system can handle PAP + authentication at a rate of 10k packets/s. However, SSL involves + RSA calculations, which are very expensive. To benchmark your system, + do: + +$ openssl speed rsa + + or + +$ openssl speed rsa2048 + + to test 2048 bit keys. + + That number is also the number of authentications/s that can be done + for EAP-TLS (or TTLS, or PEAP). + + + COMPATIBILITY + +The certificates created using this method are known to be compatible +with ALL operating systems. Some common issues are: + + - Windows requires certain OIDs in the certificates. If it doesn't + see them, it will stop doing EAP. The most visible effect is + that the client starts EAP, gets a few Access-Challenge packets, + and then a little while later re-starts EAP. If this happens, see + the FAQ, and the comments in raddb/eap.conf for how to fix it. + + - Windows requires the root certificates to be on the client PC. + If it doesn't have them, you will see the same issue as above. + + - Windows XP post SP2 has a bug where it has problems with + certificate chains. i.e. if the server certificate is an + intermediate one, and not a root one, then authentication will + silently fail, as above. + + - Some versions of Windows CE cannot handle 4K RSA certificates. + They will (again) silently fail, as above. + + - In none of these cases will Windows give the end user any + reasonable error message describing what went wrong. This leads + people to blame the RADIUS server. That blame is misplaced. + + - Certificate chains of more than 64K bytes are known to not work. + This is a problem in FreeRADIUS. However, most clients cannot + handle 64K certificate chains. Most Access Points will shut down + the EAP session after about 50 round trips, while 64K certificate + chains will take about 60 round trips. So don't use large + certificate chains. They will only work after everyone upgrade + everything in the network. + + - All other operating systems are known to work with EAP and + FreeRADIUS. This includes Linux, *BSD, Mac OS X, Solaris, + Symbian, along with all known embedded systems, phones, WiFi + devices, etc. + + - Someone needs to ask Microsoft to please stop making life hard for + their customers. + + + SECURITY CONSIDERATIONS + +The default certificate configuration files uses MD5 for message +digests, to maintain compatibility with network equipment that +supports only this algorithm. + +MD5 has known weaknesses and is discouraged in favour of SHA1 (see +http://www.kb.cert.org/vuls/id/836068 for details). If your network +equipment supports the SHA1 signature algorithm, we recommend that you +change the "ca.cnf", "server.cnf", and "client.cnf" files to specify +the use of SHA1 for the certificates. To do this, change the +'default_md' entry in those files from 'md5' to 'sha1'. diff --git a/src/tests/certs/tmp/bootstrap b/src/tests/certs/tmp/bootstrap new file mode 100755 index 00000000000..0f719aafd4c --- /dev/null +++ b/src/tests/certs/tmp/bootstrap @@ -0,0 +1,82 @@ +#!/bin/sh +# +# This is a wrapper script to create default certificates when the +# server first starts in debugging mode. Once the certificates have been +# created, this file should be deleted. +# +# Ideally, this program should be run as part of the installation of any +# binary package. The installation should also ensure that the permissions +# and owners are correct for the files generated by this script. +# +# $Id$ +# +umask 027 +cd `dirname $0` + +make -h > /dev/null 2>&1 + +# +# If we have a working "make", then use it. Otherwise, run the commands +# manually. +# +if [ "$?" = "0" ]; then + make all + exit $? +fi + +# +# The following commands were created by running "make -n", and edited +# to remove the trailing backslash, and to add "exit 1" after the commands. +# +# Don't edit the following text. Instead, edit the Makefile, and +# re-generate these commands. +# +if [ ! -f dh ]; then + openssl dhparam -out dh 2048 || exit 1 + if [ -e /dev/urandom ] ; then + ln -sf /dev/urandom random + else + date > ./random; + fi +fi + +if [ ! -f server.key ]; then + openssl req -new -out server.csr -keyout server.key -config ./server.cnf || exit 1 +fi + +if [ ! -f ca.key ]; then + openssl req -new -x509 -keyout ca.key -out ca.pem -days `grep default_days ca.cnf | sed 's/.*=//;s/^ *//'` -config ./ca.cnf || exit 1 +fi + +if [ ! -f index.txt ]; then + touch index.txt +fi + +if [ ! -f serial ]; then + echo '01' > serial +fi + +if [ ! -f server.crt ]; then + openssl ca -batch -keyfile ca.key -cert ca.pem -in server.csr -key `grep output_password ca.cnf | sed 's/.*=//;s/^ *//'` -out server.crt -extensions xpserver_ext -extfile xpextensions -config ./server.cnf || exit 1 +fi + +if [ ! -f server.p12 ]; then + openssl pkcs12 -export -in server.crt -inkey server.key -out server.p12 -passin pass:`grep output_password server.cnf | sed 's/.*=//;s/^ *//'` -passout pass:`grep output_password server.cnf | sed 's/.*=//;s/^ *//'` || exit 1 +fi + +if [ ! -f server.pem ]; then + openssl pkcs12 -in server.p12 -out server.pem -passin pass:`grep output_password server.cnf | sed 's/.*=//;s/^ *//'` -passout pass:`grep output_password server.cnf | sed 's/.*=//;s/^ *//'` || exit 1 + openssl verify -CAfile ca.pem server.pem || exit 1 +fi + +if [ ! -f ca.der ]; then + openssl x509 -inform PEM -outform DER -in ca.pem -out ca.der || exit 1 +fi + +if [ ! -f client.key ]; then + openssl req -new -out client.csr -keyout client.key -config ./client.cnf +fi + +if [ ! -f client.crt ]; then + openssl ca -batch -keyfile ca.key -cert ca.pem -in client.csr -key `grep output_password ca.cnf | sed 's/.*=//;s/^ *//'` -out client.crt -extensions xpclient_ext -extfile xpextensions -config ./client.cnf +fi diff --git a/src/tests/certs/tmp/ca.cnf b/src/tests/certs/tmp/ca.cnf new file mode 100644 index 00000000000..14fa982ba44 --- /dev/null +++ b/src/tests/certs/tmp/ca.cnf @@ -0,0 +1,62 @@ +[ ca ] +default_ca = CA_default + +[ CA_default ] +dir = ./ +certs = $dir +crl_dir = $dir/crl +database = $dir/index.txt +new_certs_dir = $dir +certificate = $dir/ca.pem +serial = $dir/serial +crl = $dir/crl.pem +private_key = $dir/ca.key +RANDFILE = $dir/.rand +name_opt = ca_default +cert_opt = ca_default +default_days = 365 +default_crl_days = 30 +default_md = sha256 +preserve = no +policy = policy_match +unique_subject = no + +[ policy_match ] +countryName = match +stateOrProvinceName = match +organizationName = match +organizationalUnitName = optional +commonName = supplied +emailAddress = optional + +[ policy_anything ] +countryName = optional +stateOrProvinceName = optional +localityName = optional +organizationName = optional +organizationalUnitName = optional +commonName = supplied +emailAddress = optional + +[ req ] +prompt = no +distinguished_name = certificate_authority +default_bits = 2048 +input_password = whatever +output_password = whatever +x509_extensions = v3_ca + +[ certificate_authority ] +countryName = FR +stateOrProvinceName = Radius +localityName = Somewhere +organizationName = Example Inc +emailAddress = admin@example.org +commonName = "Example Certificate Authority" + +[ v3_ca ] +subjectKeyIdentifier = hash +authorityKeyIdentifier = keyid:always,issuer:always +basicConstraints = critical,CA:true +crlDistributionPoints = URI:http://www.example.com/example_ca.crl + diff --git a/src/tests/certs/tmp/client.cnf b/src/tests/certs/tmp/client.cnf new file mode 100644 index 00000000000..ee9dbf0edd1 --- /dev/null +++ b/src/tests/certs/tmp/client.cnf @@ -0,0 +1,66 @@ +[ ca ] +default_ca = CA_default + +[ CA_default ] +dir = ./ +certs = $dir +crl_dir = $dir/crl +database = $dir/index.txt +new_certs_dir = $dir +certificate = $dir/ca.pem +serial = $dir/serial +crl = $dir/crl.pem +private_key = $dir/ca.key +RANDFILE = $dir/.rand +name_opt = ca_default +cert_opt = ca_default +default_days = 365 +default_crl_days = 30 +default_md = sha256 +preserve = no +policy = policy_match +unique_subject = no +x509_extensions = v3_client + +[ policy_match ] +countryName = match +stateOrProvinceName = match +organizationName = match +organizationalUnitName = optional +commonName = supplied +emailAddress = optional + +[ policy_anything ] +countryName = optional +stateOrProvinceName = optional +localityName = optional +organizationName = optional +organizationalUnitName = optional +commonName = optional +subjectAltName = supplied +emailAddress = optional + +[ req ] +prompt = no +distinguished_name = client +default_bits = 2048 +input_password = whatever +output_password = whatever + +[ client ] +countryName = FR +stateOrProvinceName = Radius +localityName = Somewhere +organizationName = Example Inc +emailAddress = user.example@example.org +commonName = Example user + +# Should be the user's NAI as per RFC 5216 (EAP-TLS) +subjectAltName = user@example.org + +[ v3_client ] +basicConstraints = CA:FALSE +keyUsage = nonRepudiation, digitalSignature, keyEncipherment +extendedKeyUsage = 1.3.6.1.5.5.7.3.2 +crlDistributionPoints = URI:http://www.example.com/example_ca.crl +authorityInfoAccess = OCSP;URI:http://www.example.org/ocsp diff --git a/src/tests/certs/tmp/ocsp.cnf b/src/tests/certs/tmp/ocsp.cnf new file mode 100644 index 00000000000..ba8d3535718 --- /dev/null +++ b/src/tests/certs/tmp/ocsp.cnf @@ -0,0 +1,61 @@ +[ ca ] +default_ca = CA_default + +[ CA_default ] +dir = ./ +certs = $dir +crl_dir = $dir/crl +database = $dir/index.txt +new_certs_dir = $dir +certificate = $dir/server.pem +serial = $dir/serial +crl = $dir/crl.pem +private_key = $dir/server.key +RANDFILE = $dir/.rand +name_opt = ca_default +cert_opt = ca_default +default_days = 365 +default_crl_days = 30 +default_md = sha256 +preserve = no +policy = policy_match +unique_subject = no +x509_extensions = v3_ocsp + +[ policy_match ] +countryName = match +stateOrProvinceName = match +organizationName = match +organizationalUnitName = optional +commonName = supplied +emailAddress = optional + +[ policy_anything ] +countryName = optional +stateOrProvinceName = optional +localityName = optional +organizationName = optional +organizationalUnitName = optional +commonName = supplied +emailAddress = optional + +[ req ] +prompt = no +distinguished_name = server +default_bits = 2048 +input_password = whatever +output_password = whatever + +[ server ] +countryName = FR +stateOrProvinceName = Radius +localityName = Somewhere +organizationName = Example Inc +emailAddress = admin@example.org +commonName = "Example OCSP Responder Certificate" +subjectAltName = ocsp.example.org + +[ v3_ocsp ] +basicConstraints = CA:FALSE +keyUsage = nonRepudiation, digitalSignature, keyEncipherment +extendedKeyUsage = OCSPSigning diff --git a/src/tests/certs/tmp/server.cnf b/src/tests/certs/tmp/server.cnf new file mode 100644 index 00000000000..ad80810393d --- /dev/null +++ b/src/tests/certs/tmp/server.cnf @@ -0,0 +1,63 @@ +[ ca ] +default_ca = CA_default + +[ CA_default ] +dir = ./ +certs = $dir +crl_dir = $dir/crl +database = $dir/index.txt +new_certs_dir = $dir +certificate = $dir/server.pem +serial = $dir/serial +crl = $dir/crl.pem +private_key = $dir/server.key +RANDFILE = $dir/.rand +name_opt = ca_default +cert_opt = ca_default +default_days = 365 +default_crl_days = 30 +default_md = sha256 +preserve = no +policy = policy_match +unique_subject = no +x509_extensions = v3_radius + +[ policy_match ] +countryName = match +stateOrProvinceName = match +organizationName = match +organizationalUnitName = optional +commonName = supplied +emailAddress = optional + +[ policy_anything ] +countryName = optional +stateOrProvinceName = optional +localityName = optional +organizationName = optional +organizationalUnitName = optional +commonName = supplied +emailAddress = optional + +[ req ] +prompt = no +distinguished_name = server +default_bits = 2048 +input_password = whatever +output_password = whatever + +[ server ] +countryName = FR +stateOrProvinceName = Radius +localityName = Somewhere +organizationName = Example Inc +emailAddress = admin@example.org +commonName = "Example Server Certificate" +subjectAltName = radius.example.org + +[ v3_radius ] +basicConstraints = CA:FALSE +keyUsage = nonRepudiation, digitalSignature, keyEncipherment +extendedKeyUsage = 1.3.6.1.5.5.7.3.1 +crlDistributionPoints = URI:http://www.example.com/example_ca.crl +authorityInfoAccess = OCSP;URI:http://www.example.org/ocsp diff --git a/src/tests/certs/tmp/xpextensions b/src/tests/certs/tmp/xpextensions new file mode 100644 index 00000000000..deb834f094e --- /dev/null +++ b/src/tests/certs/tmp/xpextensions @@ -0,0 +1,24 @@ +# +# File containing the OIDs required for Windows. +# +# http://support.microsoft.com/kb/814394/en-us +# +[ xpclient_ext ] +extendedKeyUsage = 1.3.6.1.5.5.7.3.2 +crlDistributionPoints = URI:http://www.example.com/example_ca.crl + +[ xpserver_ext ] +extendedKeyUsage = 1.3.6.1.5.5.7.3.1 +crlDistributionPoints = URI:http://www.example.com/example_ca.crl + +# +# Add this to the PKCS#7 keybag attributes holding the client's private key +# for machine authentication. +# +# the presence of this OID tells Windows XP that the cert is intended +# for use by the computer itself, and not by an end-user. +# +# The other solution is to use Microsoft's web certificate server +# to generate these certs. +# +# 1.3.6.1.4.1.311.17.2 diff --git a/src/tests/eapol_test/fast-pac b/src/tests/eapol_test/fast-pac new file mode 100644 index 0000000000000000000000000000000000000000..acebc3b137838cc66b8fde65c87615e611e29864 GIT binary patch literal 657 zc-p0q&1xMn428R%r5(tGhGmwkUYYCWCD>+Np3+3pYH-S&QrF~Py ziWm98U)K=QRAUC@Ms*PbtOXK^dQOIh#iMmu3cJ!`qBSYy!~r4J%77iQlkgXQblH2%ycd&l`UbZIYDcjYgR~$ zH>Ze1j@}}egA*bWS`ni;Lqy?>nX}KxOEdL_TsB9g>_!? zWuDtpJg(5&?~A1vxJb@j10cLLW%n!q3Hm+}QTO~?bzX&EK^;15)9uxp|9g4$yZQfx V|B0H;Kh7&A;&*?k;rip%@Dps#qT>Jn literal 0 Hc-jL100001 diff --git a/src/tests/foo b/src/tests/foo new file mode 100644 index 00000000000..125bb2a6940 --- /dev/null +++ b/src/tests/foo @@ -0,0 +1,22 @@ +array +escape +foreach-isolation +if-regex-empty +if-regex-match +if-regex-match-comp +if-regex-match-named +if-regex-multivalue +ipprefix +map-xlat +redundant-redundant +switch-value-error +switch-value-error2 +truncation +unit_test_module.conf +unknown +update-hex +update-index +update-xlat +urlquote +xlat-attr +xlat-explode diff --git a/src/tests/keywords/parallel-module b/src/tests/keywords/parallel-module new file mode 100644 index 00000000000..bfbe42eb28b --- /dev/null +++ b/src/tests/keywords/parallel-module @@ -0,0 +1,12 @@ +# +# PRE: parallel +# +parallel { + ok + ok + ok + return + ok +} + +success diff --git a/src/tests/trie/.gitignore b/src/tests/trie/.gitignore new file mode 100644 index 00000000000..25974e3d69a --- /dev/null +++ b/src/tests/trie/.gitignore @@ -0,0 +1 @@ +trie.c diff --git a/src/tests/trie/all.mk b/src/tests/trie/all.mk new file mode 100644 index 00000000000..2c44b4fa5ce --- /dev/null +++ b/src/tests/trie/all.mk @@ -0,0 +1,2 @@ +SUBMAKEFILES := trie.mk test.mk + diff --git a/src/tests/trie/input.txt b/src/tests/trie/input.txt new file mode 100644 index 00000000000..673c82dc475 --- /dev/null +++ b/src/tests/trie/input.txt @@ -0,0 +1,228 @@ +lcp a b 6 +lcp a a 8 +lcp a A 2 +lcp a C 2 +lcp aa ab 14 +lcp aaa aab 22 +lcp aaa aaab 24 +lcp aaaaaaa aaaaaab 54 +lcp a aaa 8 +lcp aaa a 8 + +# +# LCP with offsets +# +# Note that 'length' is length beginning from 'start' +# +# string length string length start result +lcp a 8 b 8 0 6 +lcp a 4 b 4 4 2 +lcp a 3 b 3 5 1 +lcp a 8 A 8 0 2 +lcp a 2 A 2 0 2 +lcp a 4 A 4 0 2 +lcp a 1 A 1 0 1 + +lcp aaa 24 aab 24 4 18 + +# +# Insert a path and user data +# Look up the key, and ensure that the user data matches +# print the whole trie +# remove the path we inserted +# ensure that the trie is empty +# +path aaa 1 aaa=1 +path a 2 a=2 +path bbbb 1 bbbb=1 + +# +# Insert a key, followed by user data. +# The key doesn't have to be alphabetical, it can be anything. +# The user data doesn't have to be a numeric. +# But doing so makes things easier. +# +insert aaa 1 +print aaa=1 +lookup aaa 1 +remove aaa 1 +print {} + +# +# Insert disjoint keys. +# +insert a 1 +insert b 2 + +print a=1,b=2 +lookup a 1 +lookup b 2 + +remove a 1 +print b=2 +lookup b 2 +remove b 2 +print {} + +# +# "lookup" is "find longest match" +# "match" is "find exact match" +# +insert a 1 +insert aa 2 +print a=1,aa=2 +lookup c {} # isn't in the trie +lookup ab 1 # gets shortest match +match ab {} # exact match doesn't exist + +remove a 1 +print aa=2 +remove aa 2 +print {} + + + +insert aaab 1 +insert aaac 2 +insert b 3 +insert c 4 +print aaab=1,aaac=2,b=3,c=4 +remove c 4 +print aaab=1,aaac=2,b=3 +remove aaab 1 +print aaac=2,b=3 + +remove aaac 2 +print b=3 +remove b 3 +print {} + +insert a 1 +remove a 1 +insert a 1 +verify + +insert ab 2 +print a=1,ab=2 +remove ab 2 +insert ab 2 +verify + +insert aaabb 3 +remove aaabb 3 +insert aaabb 3 +verify + +insert aabcd 4 +remove aabcd 4 +insert aabcd 4 +verify + +insert ad 5 +remove ad 5 +insert ad 5 +verify + +print a=1,aaabb=3,aabcd=4,ab=2,ad=5 +insert abd 6 +match abd 6 +print a=1,aaabb=3,aabcd=4,ab=2,abd=6,ad=5 +verify +remove abd 6 +verify +insert abd 6 +verify + +insert b 7 +remove b 7 +insert b 7 + +insert c 8 +remove c 8 +insert c 8 + +match ab 2 +match aabcd 4 +match aaabb 3 +remove b 7 +remove a 1 +match c 8 +remove ab 2 +remove aaabb 3 +remove c 8 + +match ad 5 + +print aabcd=4,abd=6,ad=5 +remove ad 5 + +print aabcd=4,abd=6 +#dump + +remove abd 6 + +remove aabcd 4 + +lookup abd {} +print {} + +insert a 1 +insert aa 2 +insert aaa 3 +lookup aaa 3 +lookup aa 2 +lookup a 1 +lookup b {} +lookup ab 1 + +insert bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb 5 +print a=1,aa=2,aaa=3,bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb=5 +clear +print {} + +# +# Tests for node splitting +# +insert a 1 +insert b 2 +insert c 3 +insert d 4 + +# +# Insert with short bits +# +# {6} means "use only 6 bits of the following key" +# +insert {6}a 5 + +# +# Upper 6 bits of 'a' are 0x60, or ` +# +print `=5,a=1,b=2,c=3,d=4 + +match {6}a 5 +match {7}a {} # exact match isn't available +lookup {7}a 5 # but shortest prefix match is available +lookup a 1 # this is an exact match +lookup aa 1 # this is a longest prefix match +lookup {1}a {} # nothing matches yet +match a 1 +insert {0}a 0 +lookup {0}a 0 +lookup {1}a 0 +lookup {2}a 0 +remove {0}a 0 + +remove a 1 +print `=5,b=2,c=3,d=4 + +remove {6}a 5 +print b=2,c=3,d=4 +remove b 2 +remove c 3 +remove d 4 +print {} + +insert a 1 +insert ab 2 +print a=1,ab=2 diff --git a/src/tests/trie/test.mk b/src/tests/trie/test.mk new file mode 100644 index 00000000000..412cf2f243e --- /dev/null +++ b/src/tests/trie/test.mk @@ -0,0 +1,31 @@ +# +# Get the test files. +# +TRIE_FILES := $(subst $(DIR)/,,$(wildcard $(DIR)/*.txt)) + +# +# Create the output directory +# +.PHONY: $(BUILD_DIR)/tests/trie +$(BUILD_DIR)/tests/trie: + ${Q}mkdir -p $@ + +$(BUILD_DIR)/tests/trie/%: $(DIR)/% $(TESTBINDIR)/trie | $(BUILD_DIR)/tests/trie + @echo TRIE-TEST $(dir $@) + @$(TESTBINDIR)/trie $^ > $@ + +# +# Get all of the unit test output files +# +TESTS.TRIE_FILES := $(addprefix $(BUILD_DIR)/tests/trie/,$(TRIE_FILES)) + +# +# Depend on the output files, and create the directory first. +# +tests.trie: $(TESTS.TRIE_FILES) + +$(TESTS.TRIE_FILES): $(TESTS.UNIT_FILES) + +.PHONY: clean.tests.trie +clean.tests.trie: + ${Q}rm -rf $(BUILD_DIR)/tests/trie/ diff --git a/src/tests/trie/trie.mk b/src/tests/trie/trie.mk new file mode 100644 index 00000000000..abd29c95708 --- /dev/null +++ b/src/tests/trie/trie.mk @@ -0,0 +1,17 @@ +TARGET := trie + +SRC_CFLAGS := -DTESTING +SOURCES := trie.c +TGT_LDLIBS := $(LIBS) +TGT_PREREQS := libfreeradius-util.a + +# +# The build system maps one source file to one object file. So in +# order to build a test binary, we need to create a new source file. +# +# We could move the test code into a "trie.c" file in this directory. +# But it's useful for the test code to access internal functions / +# definitions in the trie library. +# +src/tests/trie/trie.c: ${top_srcdir}/src/lib/util/trie.c + @[-e $@ ] || ln -s $^ $(dir $@) -- 2.47.3