Mercurial > hg > freeDiameter
diff extensions/acl_wl/aw_tree.c @ 161:645ff1487c23
Draft for ACL white-list extension
author | Sebastien Decugis <sdecugis@nict.go.jp> |
---|---|
date | Mon, 25 Jan 2010 19:07:29 +0900 |
parents | |
children | 79768bf7d208 |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/extensions/acl_wl/aw_tree.c Mon Jan 25 19:07:29 2010 +0900 @@ -0,0 +1,412 @@ +/********************************************************************************************************* +* Software License Agreement (BSD License) * +* Author: Sebastien Decugis <sdecugis@nict.go.jp> * +* * +* Copyright (c) 2009, WIDE Project and NICT * +* All rights reserved. * +* * +* Redistribution and use of this software in source and binary forms, with or without modification, are * +* permitted provided that the following conditions are met: * +* * +* * Redistributions of source code must retain the above * +* copyright notice, this list of conditions and the * +* following disclaimer. * +* * +* * Redistributions in binary form must reproduce the above * +* copyright notice, this list of conditions and the * +* following disclaimer in the documentation and/or other * +* materials provided with the distribution. * +* * +* * Neither the name of the WIDE Project or NICT nor the * +* names of its contributors may be used to endorse or * +* promote products derived from this software without * +* specific prior written permission of WIDE Project and * +* NICT. * +* * +* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED * +* WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A * +* PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR * +* ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT * +* LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS * +* INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR * +* TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF * +* ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. * +*********************************************************************************************************/ + +#include "acl_wl.h" + +/* The configuration simply contains the allowed fqdn and/or domains (*.example.net) + * It is represented similarly to the DNS tree: + * (root)--___ + * / \ \ + * tld1 tld2 (tld3...) + * / | + * label1 label2 + * / \ + * lbl21 lbl22 + * / \ + * lbl211 * + * + * This tree would whitelist: + * - label1.tld1 + * - lbl211.lbl21.label2.tld2 + * - *.lbl22.label2.tld2 + * + * The functions to add and search the tree are in aw_tree.c. + * + */ + +/* Maximum depth of the tree. We set a static size to avoid dynamic allocations. We report an error if this is not sufficient. */ +#define AW_TREE_MAXDEPTH 10 + +/* An element of the tree */ +struct tree_item { + struct fd_list chain; /* Link to elements at the same level. Ordered alphabetically. */ + struct fd_list children; /* Sentinel for the subtree. */ + char * str; /* the \0 terminated label, or NULL if it is a generic container ("*") */ + int flags; /* PI_SEC_* flags */ + int leaf; /* true if this item can be a leaf of the tree */ +}; + +/* The root of the tree */ +static struct fd_list tree_root = FD_LIST_INITIALIZER(tree_root); + +/* Note: we don't need to lock, since we add only when parsing the conf, and then read only */ + + +/* The parsed name */ +struct split_name { + struct { + char * str; /* start of this label */ + size_t len; /* length of this label. It does not include the final "." or "\0" */ + } label[AW_TREE_MAXDEPTH]; + int last_lbl; /* idx of last label defined */ +}; + +/* The following function explodes a name into a split_name structure */ +static int parse_name(char * name, struct split_name * result) +{ + int i, l, prev_offset; + char * c; + + TRACE_ENTRY("%p %p", name, result); + + /* First, initialize the result array */ + memset(result, 0, sizeof(struct split_name)); + result->label[0].str = name; + l = 0; prev_offset = 0; + + for (i=0; name[i] != '\0'; i++) { + if (name[i]=='.') { + l++; + CHECK_PARAMS( l < AW_TREE_MAXDEPTH ); + + /* The previous label is complete, write its size */ + result->label[l - 1].len = i - prev_offset; + prev_offset = i + 1; + + /* Write the start of the new label */ + result->label[l].str = name + i + 1; + } + } + + /* Finally, write the size of the last label */ + result->label[l].len = i - prev_offset; + + result->last_lbl = l; + +#if 0 + fd_log_debug("Parsed name %s as:\n", name); + for (i=0; i<=l; i++) + fd_log_debug(" str[%d] len: %d, v:%.*s\n", i, result->label[i].len, result->label[i].len, result->label[i].str); +#endif /* 0 */ + return 0; +} + +/* Create a new tree_item structure */ +static struct tree_item * new_ti(char * str, size_t len, int flags, int leaf) +{ + struct tree_item * ti; + char * s = NULL; + + TRACE_ENTRY("%p %d %x", str, len, flags); + + if (str) { + CHECK_MALLOC_DO(s = malloc(len + 1), return NULL); + memcpy(s, str, len); + s[len] = '\0'; + } + + CHECK_MALLOC_DO( ti = malloc(sizeof(struct tree_item)), {free(s); return NULL; } ); + memset(ti, 0, sizeof(struct tree_item)); + + fd_list_init(&ti->chain, ti); + fd_list_init(&ti->children, ti); + ti->str = s; + ti->flags = flags; + ti->leaf = leaf; + + return ti; +} + +/* Recursively delete a subtree */ +static void delete_tree(struct fd_list * senti) +{ + while (!FD_IS_LIST_EMPTY(senti)) { + struct tree_item * ti = (struct tree_item *)(senti->next); + + /* Delete recursively its children first */ + delete_tree(&ti->children); + + /* Now, unlink from the sentinel list */ + fd_list_unlink(&ti->chain); + + /* destroy this tree item */ + free(ti->str); + free(ti); + } +} + +/* Top-level destroy function */ +void aw_tree_destroy(void) +{ + delete_tree(&tree_root); +} + +/* Display the content of a subtree */ +static void tree_dump(struct fd_list * sub, int indent) +{ + struct fd_list * li; + for (li = sub->next; li != sub; li = li->next) { + struct tree_item * ti = (struct tree_item *)li; + fd_log_debug("%*s%s", indent * 2, "", ti->str?:"*"); + if (ti->leaf) + fd_log_debug(" (flag:%x)", ti->flags); + fd_log_debug("\n"); + tree_dump(&ti->children, indent + 1); + } +} + +/* Top-level function */ +void aw_tree_dump(void) +{ + fd_log_debug("[acl_wl] tree dump:\n(root)\n"); + tree_dump(&tree_root, 1); + fd_log_debug("[acl_wl] end of dump\n"); +} + +/* Function to add a new entry in the tree */ +int aw_tree_add(char * name, int flags) +{ + struct split_name sn; + struct tree_item * ti; + struct fd_list * li, *senti; + int lbl, found; + + TRACE_ENTRY("%p %x", name, flags); + CHECK_PARAMS(name && *name); + + CHECK_FCT_DO( parse_name(name, &sn), + { + fd_log_debug("The name '%s' contains too many labels, try a generic (*) or recompile with bigger AW_TREE_MAXDEPTH value (cur: %d)\n", name, AW_TREE_MAXDEPTH); + return EINVAL; + } ); + + senti = &tree_root; + + for (lbl = sn.last_lbl; lbl > 0; lbl--) { + /* Check if the list is empty, we can directly create the new entry */ + if (FD_IS_LIST_EMPTY(senti)) { + CHECK_MALLOC( ti = new_ti(sn.label[lbl].str, sn.label[lbl].len, 0, 0 /* flags are only set in the terminals */) ); + /* Insert this label in the sentinel sublist */ + fd_list_insert_after(senti, &ti->chain); + /* Update the sentinel */ + senti = &ti->children; + /* loop to the next label */ + continue; + } + + /* Check if we have a '*' element already that overlapses */ + ti = (struct tree_item *)(senti->next); + if (ti->str == NULL) { + fd_log_debug("[acl_wl] Warning: entry '%s' is superseeded by a generic entry at level %d, ignoring.\n", name, lbl); + return 0; + } + + /* Search this label in the ordered list */ + found = 0; + for (li = senti->next; li != senti; li=li->next) { + int cmp, len; + ti = (struct tree_item *)li; + + cmp = strncasecmp(ti->str, sn.label[lbl].str, sn.label[lbl].len); + if (cmp > 0) + break; /* the new label must be inserted before li */ + if (cmp < 0) + continue; + + /* Check the lengths */ + len = strlen(ti->str); + if (len > sn.label[lbl].len) + break; /* the new label must be inserted before li */ + if (len < sn.label[lbl].len) + continue; + + /* We already had this label */ + found = 1; + senti = &ti->children; + break; + } + + if (found) + continue; + + /* Otherwise, we have to create a new ti, and add it before li */ + CHECK_MALLOC( ti = new_ti(sn.label[lbl].str, sn.label[lbl].len, 0, 0 /* flags are only set in the terminals */) ); + /* Insert this label in the sentinel sublist */ + fd_list_insert_before(li, &ti->chain); + /* Update the sentinel */ + senti = &ti->children; + } + + ti = NULL; + li = senti; + + /* At this point, senti points to the list where we are supposed to insert our last label. */ + if (sn.label[0].str[0] == '*') { + if (!FD_IS_LIST_EMPTY(senti)) { + fd_log_debug("[acl_wl] Warning: entry '%s' overwrites previous more detailed entries, these are deleted.\n", name); + delete_tree(senti); + } + + /* Create the new entry */ + CHECK_MALLOC( ti = new_ti(NULL, 0, flags, 1) ); + } else { + if (!FD_IS_LIST_EMPTY(senti)) { + /* Check we don't have a '*' entry already */ + ti = (struct tree_item *)(senti->next); + if (ti->str == NULL) { + fd_log_debug("[acl_wl] Warning: entry '%s' is superseeded by a generic entry at level 0, ignoring.\n", name); + return 0; + } + + /* Search the place for the new label */ + for (li = senti->next; li != senti; li=li->next) { + int cmp, len; + ti = (struct tree_item *)li; + + cmp = strncasecmp(ti->str, sn.label[0].str, sn.label[0].len); + if (cmp > 0) + break; /* the new label must be inserted before li */ + if (cmp < 0) + continue; + + /* Check the lengths */ + len = strlen(ti->str); + if (len > sn.label[0].len) + break; /* the new label must be inserted before li */ + if (len < sn.label[0].len) + continue; + + /* We already had this label */ + if (ti->leaf) { + fd_log_debug("[acl_wl] Warning: entry '%s' is duplicated, merging the flags.\n", name); + ti->flags |= flags; + return 0; + } else { + /* Just mark this entry as a valid leaf also */ + ti->leaf = 1; + ti->flags = flags; + return 0; + } + } + } + + /* Create the new entry */ + CHECK_MALLOC( ti = new_ti(sn.label[0].str, sn.label[0].len, flags, 1) ); + } + + /* The new label is "ti", it is inserted before "li" */ + fd_list_insert_before(li, &ti->chain); + + /* Done! */ + return 0; +} + +/* Search in the tree. On return, *result = -1: not found; >=0: found with PI_SEC_* flags */ +int aw_tree_lookup(char * name, int * result) +{ + struct split_name sn; + int lbl, found; + struct tree_item * ti; + struct fd_list * senti, *li; + + TRACE_ENTRY("%p %p", name, result); + CHECK_PARAMS(name && result); + + /* Initialize */ + *result = -1; + + /* Parse the name into labels */ + CHECK_FCT_DO( parse_name(name, &sn), + { + TRACE_DEBUG(INFO, "Too many labels in this name, it cannot be found in the tree, skipping."); + return 0; + } ); + + senti = &tree_root; + + for (lbl = sn.last_lbl; lbl >= 0; lbl--) { + /* Check if the list is empty, we can directly return */ + if (FD_IS_LIST_EMPTY(senti)) { + /* The item is not found */ + return 0; + } + + /* Check if we have a '*' element */ + ti = (struct tree_item *)(senti->next); + if (ti->str == NULL) { + TRACE_DEBUG(FULL, "[acl_wl] %s matched at level %d with a generic entry.", name, lbl); + *result = ti->flags; + return 0; + } + + /* Search this label in the ordered list */ + found = 0; + for (li = senti->next; li != senti; li=li->next) { + int cmp, len; + ti = (struct tree_item *)li; + + cmp = strncasecmp(ti->str, sn.label[lbl].str, sn.label[lbl].len); + if (cmp > 0) + return 0; /* the label was not found */ + if (cmp < 0) + continue; + + /* Check the lengths */ + len = strlen(ti->str); + if (len > sn.label[lbl].len) + return 0; /* the label was not found */ + if (len < sn.label[lbl].len) + continue; + + /* We found the label */ + found = 1; + senti = &ti->children; + break; + } + + if (!found) + return 0; /* label not found */ + + /* otherwise, continue, sentinel has been updated */ + } + + /* At the end, ti points to the correct leaf */ + if (!ti->leaf) + return 0; + + TRACE_DEBUG(FULL, "[acl_wl] %s matched exactly.", name); + *result = ti->flags; + return 0; +}