1 files changed, 334 insertions, 213 deletions

diff --git a/lib/dns/acl.c b/lib/dns/acl.c
index 5a379108..6bb169c7 100644
--- a/lib/dns/acl.c
+++ b/lib/dns/acl.c
@@ -15,18 +15,25 @@
  * PERFORMANCE OF THIS SOFTWARE.
  */
 
-/* $Id: acl.c,v 1.32 2007/06/19 23:47:16 tbox Exp $ */
+/* $Id: acl.c,v 1.35 2007/09/19 03:03:29 marka Exp $ */
 
 /*! \file */
 
 #include <config.h>
 
 #include <isc/mem.h>
+#include <isc/once.h>
 #include <isc/string.h>
 #include <isc/util.h>
 
 #include <dns/acl.h>
+#include <dns/iptable.h>
 
+/*
+ * Create a new ACL, including an IP table and an array with room
+ * for 'n' ACL elements.  The elements are uninitialized and the
+ * length is 0.
+ */
 isc_result_t
 dns_acl_create(isc_mem_t *mctx, int n, dns_acl_t **target) {
 	isc_result_t result;
@@ -43,11 +50,19 @@ dns_acl_create(isc_mem_t *mctx, int n, dns_acl_t **target) {
 		return (ISC_R_NOMEMORY);
 	acl->mctx = mctx;
 	acl->name = NULL;
+
 	result = isc_refcount_init(&acl->refcount, 1);
 	if (result != ISC_R_SUCCESS) {
 		isc_mem_put(mctx, acl, sizeof(*acl));
 		return (result);
 	}
+
+        result = dns_iptable_create(mctx, &acl->iptable);
+	if (result != ISC_R_SUCCESS) {
+		isc_mem_put(mctx, acl, sizeof(*acl));
+		return (result);
+	}
+        
 	acl->elements = NULL;
 	acl->alloc = 0;
 	acl->length = 0;
@@ -73,111 +88,237 @@ dns_acl_create(isc_mem_t *mctx, int n, dns_acl_t **target) {
 	return (result);
 }
 
-isc_result_t
-dns_acl_appendelement(dns_acl_t *acl, const dns_aclelement_t *elt) {
-	if (acl->length + 1 > acl->alloc) {
-		/*
-		 * Resize the ACL.
-		 */
-		unsigned int newalloc;
-		void *newmem;
-
-		newalloc = acl->alloc * 2;
-		if (newalloc < 4)
-			newalloc = 4;
-		newmem = isc_mem_get(acl->mctx,
-				     newalloc * sizeof(dns_aclelement_t));
-		if (newmem == NULL)
-			return (ISC_R_NOMEMORY);
-		memcpy(newmem, acl->elements,
-		       acl->length * sizeof(dns_aclelement_t));
-		isc_mem_put(acl->mctx, acl->elements,
-			    acl->alloc * sizeof(dns_aclelement_t));
-		acl->elements = newmem;
-		acl->alloc = newalloc;
-	}
-	/*
-	 * Append the new element.
-	 */
-	acl->elements[acl->length++] = *elt;
-
-	return (ISC_R_SUCCESS);
-}
-
+/*
+ * Create a new ACL and initialize it with the value "any" or "none",
+ * depending on the value of the "neg" parameter.
+ * "any" is a positive iptable entry with bit length 0.
+ * "none" is the same as "!any".
+ */
 static isc_result_t
 dns_acl_anyornone(isc_mem_t *mctx, isc_boolean_t neg, dns_acl_t **target) {
 	isc_result_t result;
 	dns_acl_t *acl = NULL;
-	result = dns_acl_create(mctx, 1, &acl);
+	result = dns_acl_create(mctx, 0, &acl);
 	if (result != ISC_R_SUCCESS)
 		return (result);
-	acl->elements[0].negative = neg;
-	acl->elements[0].type = dns_aclelementtype_any;
-	acl->length = 1;
+        dns_iptable_addprefix(acl->iptable, NULL, 0, ISC_TF(!neg));
 	*target = acl;
 	return (result);
 }
 
+/*
+ * Create a new ACL that matches everything.
+ */
 isc_result_t
 dns_acl_any(isc_mem_t *mctx, dns_acl_t **target) {
 	return (dns_acl_anyornone(mctx, ISC_FALSE, target));
 }
 
+/*
+ * Create a new ACL that matches nothing.
+ */
 isc_result_t
 dns_acl_none(isc_mem_t *mctx, dns_acl_t **target) {
 	return (dns_acl_anyornone(mctx, ISC_TRUE, target));
 }
 
+/*
+ * If pos is ISC_TRUE, test whether acl is set to "{ any; }"
+ * If pos is ISC_FALSE, test whether acl is set to "{ none; }"
+ */
+static isc_boolean_t
+dns_acl_isanyornone(dns_acl_t *acl, isc_boolean_t pos)
+{
+        /* Should never happen but let's be safe */
+        if (acl == NULL ||
+            acl->iptable == NULL ||
+            acl->iptable->radix == NULL ||
+            acl->iptable->radix->head == NULL ||
+            acl->iptable->radix->head->prefix == NULL)
+                return (ISC_FALSE);
+
+	if (acl->length != 0 && acl->node_count != 1)
+		return (ISC_FALSE);
+
+	if (acl->iptable->radix->head->prefix->bitlen == 0 &&
+	    *(isc_boolean_t *) (acl->iptable->radix->head->data) == pos)
+		return (ISC_TRUE);
+
+	return (ISC_FALSE); /* All others */
+}
+
+/*
+ * Test whether acl is set to "{ any; }"
+ */
+isc_boolean_t
+dns_acl_isany(dns_acl_t *acl)
+{
+        return (dns_acl_isanyornone(acl, ISC_TRUE));
+}
+
+/*
+ * Test whether acl is set to "{ none; }"
+ */
+isc_boolean_t
+dns_acl_isnone(dns_acl_t *acl)
+{
+        return (dns_acl_isanyornone(acl, ISC_FALSE));
+}
+
+/*
+ * Determine whether a given address or signer matches a given ACL.
+ * For a match with a positive ACL element or iptable radix entry, 
+ * return with a positive value in match; for a match with a negated ACL
+ * element or radix entry, return with a negative value in match.
+ */
 isc_result_t
 dns_acl_match(const isc_netaddr_t *reqaddr,
 	      const dns_name_t *reqsigner,
 	      const dns_acl_t *acl,
 	      const dns_aclenv_t *env,
 	      int *match,
-	      dns_aclelement_t const**matchelt)
+	      const dns_aclelement_t **matchelt)
 {
+	isc_uint16_t bitlen;
+	isc_prefix_t pfx;
+	isc_radix_node_t *node;
+        const isc_netaddr_t *addr;
+        isc_netaddr_t v4addr;
+	isc_result_t result;
+        int match_num = -1;
 	unsigned int i;
 
 	REQUIRE(reqaddr != NULL);
 	REQUIRE(matchelt == NULL || *matchelt == NULL);
-	
+
+	if (env == NULL || env->match_mapped == ISC_FALSE ||
+	    reqaddr->family != AF_INET6 ||
+	    !IN6_IS_ADDR_V4MAPPED(&reqaddr->type.in6))
+                addr = reqaddr;
+	else {
+		isc_netaddr_fromv4mapped(&v4addr, reqaddr);
+		addr = &v4addr;
+	}
+
+	/* Always match with host addresses. */
+	bitlen = reqaddr->family == AF_INET6 ? 128 : 32;
+	NETADDR_TO_PREFIX_T(addr, pfx, bitlen);
+
+	/* Assume no match. */
+	*match = 0;
+
+	/* Search radix. */
+	result = isc_radix_search(acl->iptable->radix, &node, &pfx);
+
+	/* Found a match. */
+	if (result == ISC_R_SUCCESS && node != NULL) {
+		match_num = node->node_num;
+                if (*(isc_boolean_t *) node->data == ISC_TRUE)
+                        *match = match_num;
+                else
+                        *match = -match_num;
+        }
+
+        /* Now search non-radix elements for a match with a lower node_num. */
 	for (i = 0; i < acl->length; i++) {
 		dns_aclelement_t *e = &acl->elements[i];
 
 		if (dns_aclelement_match(reqaddr, reqsigner,
 					 e, env, matchelt)) {
-			*match = e->negative ? -((int)i+1) : ((int)i+1);
+                        if (match_num == -1 || e->node_num < match_num) {
+                                if (e->negative)
+			                *match = -e->node_num;
+                                else
+			                *match = e->node_num;
+                        }
 			return (ISC_R_SUCCESS);
 		}
 	}
-	/* No match. */
-	*match = 0;
+
 	return (ISC_R_SUCCESS);
 }
 
+/*
+ * Merge the contents of one ACL into another.  Call dns_iptable_merge()
+ * for the IP tables, then concatenate the element arrays.
+ *
+ * If pos is set to false, then the nested ACL is to be negated.  This
+ * means reverse the sense of each *positive* element or IP table node,
+ * but leave negatives alone, so as to prevent a double-negative causing
+ * an unexpected postive match in the parent ACL.
+ */
 isc_result_t
-dns_acl_elementmatch(const dns_acl_t *acl,
-		     const dns_aclelement_t *elt,
-		     const dns_aclelement_t **matchelt)
+dns_acl_merge(dns_acl_t *dest, dns_acl_t *source, isc_boolean_t pos)
 {
-	unsigned int i;
-
-	REQUIRE(elt != NULL);
-	REQUIRE(matchelt == NULL || *matchelt == NULL);
-	
-	for (i = 0; i < acl->length; i++) {
-		dns_aclelement_t *e = &acl->elements[i];
-
-		if (dns_aclelement_equal(e, elt) == ISC_TRUE) {
-			if (matchelt != NULL)
-				*matchelt = e;
-			return (ISC_R_SUCCESS);
-		}
-	}
-
-	return (ISC_R_NOTFOUND);
+	isc_result_t result;
+        unsigned int newalloc, nelem, i;
+        int max_node = 0, nodes;
+
+        /* Resize the element array if needed. */
+        if (dest->length + source->length > dest->alloc) {
+                void *newmem;
+
+                newalloc = dest->alloc + source->alloc;
+                if (newalloc < 4)
+                        newalloc = 4;
+
+                newmem = isc_mem_get(dest->mctx,
+                                     newalloc * sizeof(dns_aclelement_t));
+                if (newmem == NULL)
+                        return (ISC_R_NOMEMORY);
+
+                /* Copy in the original elements */
+                memcpy(newmem, dest->elements,
+                       dest->length * sizeof(dns_aclelement_t));
+
+                /* Release the memory for the old elements array */
+                isc_mem_put(dest->mctx, dest->elements,
+                            dest->alloc * sizeof(dns_aclelement_t));
+                dest->elements = newmem;
+                dest->alloc = newalloc;
+        }
+
+        /*
+         * Now copy in the new elements, increasing their node_num
+         * values so as to keep the new ACL consistent.  If we're
+         * negating, then negate positive elements, but keep negative
+         * elements the same for security reasons.
+         */
+        nelem = dest->length;
+        memcpy(&dest->elements[nelem], source->elements,
+               (source->length * sizeof(dns_aclelement_t)));
+        for (i = 0; i < source->length; i++) {
+                dest->elements[nelem + i].node_num = 
+                        source->elements[i].node_num + dest->node_count;
+                if (source->elements[i].node_num > max_node)
+                        max_node = source->elements[i].node_num;
+                if (!pos && source->elements[i].negative == ISC_FALSE)
+                        dest->elements[nelem + i].negative = ISC_TRUE;
+        }
+
+        /*
+         * Merge the iptables.  Make sure the destination ACL's
+         * node_count value is set correctly afterward.
+         */
+        nodes = max_node + dest->node_count;
+        result = dns_iptable_merge(dest->iptable, source->iptable, pos);
+        if (result != ISC_R_SUCCESS)
+                return (result);
+        if (nodes > dest->node_count)
+                dest->node_count = nodes;
+
+        return (ISC_R_SUCCESS);
 }
 
+/*
+ * Like dns_acl_match, but matches against the single ACL element 'e'
+ * rather than a complete ACL, and returns ISC_TRUE iff it matched.
+ *
+ * To determine whether the match was prositive or negative, the 
+ * caller should examine e->negative.  Since the element 'e' may be
+ * a reference to a named ACL or a nested ACL, a matching element
+ * returned through 'matchelt' is not necessarily 'e' itself.
+ */
 isc_boolean_t
 dns_aclelement_match(const isc_netaddr_t *reqaddr,
 		     const dns_name_t *reqsigner,
@@ -186,90 +327,66 @@ dns_aclelement_match(const isc_netaddr_t *reqaddr,
 		     const dns_aclelement_t **matchelt)
 {
 	dns_acl_t *inner = NULL;
-	const isc_netaddr_t *addr;
-	isc_netaddr_t v4addr;
 	int indirectmatch;
 	isc_result_t result;
 
-	switch (e->type) {
-	case dns_aclelementtype_ipprefix:
-		if (env == NULL ||
-		    env->match_mapped == ISC_FALSE ||
-		    reqaddr->family != AF_INET6 ||
-		    !IN6_IS_ADDR_V4MAPPED(&reqaddr->type.in6))
-			addr = reqaddr;
-		else {
-			isc_netaddr_fromv4mapped(&v4addr, reqaddr);
-			addr = &v4addr;
-		}
-
-		if (isc_netaddr_eqprefix(addr,
-					 &e->u.ip_prefix.address, 
-					 e->u.ip_prefix.prefixlen))
-			goto matched;
-		break;
-		
-	case dns_aclelementtype_keyname:
+        switch (e->type) {
+	    case dns_aclelementtype_keyname:
 		if (reqsigner != NULL &&
-		    dns_name_equal(reqsigner, &e->u.keyname))
-			goto matched;
-		break;
-		
-	case dns_aclelementtype_nestedacl:
-		inner = e->u.nestedacl;
-	nested:
-		result = dns_acl_match(reqaddr, reqsigner,
-				       inner,
-				       env,
-				       &indirectmatch, matchelt);
-		INSIST(result == ISC_R_SUCCESS);
-
-		/*
-		 * Treat negative matches in indirect ACLs as
-		 * "no match".
-		 * That way, a negated indirect ACL will never become 
-		 * a surprise positive match through double negation.
-		 * XXXDCL this should be documented.
-		 */
-		if (indirectmatch > 0)
-			goto matchelt_set;
-		
-		/*
-		 * A negative indirect match may have set *matchelt,
-		 * but we don't want it set when we return.
-		 */
-		if (matchelt != NULL)
-			*matchelt = NULL;
-		break;
+		    dns_name_equal(reqsigner, &e->keyname)) {
+		        if (matchelt != NULL)
+		        	*matchelt = e;
+		        return (ISC_TRUE);
+                } else {
+                        return (ISC_FALSE);
+                }
+
+	    case dns_aclelementtype_nestedacl:
+                inner = e->nestedacl;
+                break;
+
+            case dns_aclelementtype_localhost:
+                if (env == NULL || env->localhost == NULL)
+                        return (ISC_FALSE);
+                inner = env->localhost;
+                break;
+
+            case dns_aclelementtype_localnets:
+                if (env == NULL || env->localnets == NULL)
+                        return (ISC_FALSE);
+                inner = env->localnets;
+                break;
+
+            default:
+                /* Should be impossible */
+                INSIST(0);
+        }
 		
-	case dns_aclelementtype_any:
-	matched:
-		if (matchelt != NULL)
-			*matchelt = e;
-	matchelt_set:
-		return (ISC_TRUE);
-			
-	case dns_aclelementtype_localhost:
-		if (env != NULL && env->localhost != NULL) {
-			inner = env->localhost;
-			goto nested;
-		} else {
-			break;
-		}
+        result = dns_acl_match(reqaddr, reqsigner, inner, env,
+                               &indirectmatch, matchelt);
+        INSIST(result == ISC_R_SUCCESS);
+
+        /*
+         * Treat negative matches in indirect ACLs as "no match".
+         * That way, a negated indirect ACL will never become a
+         * surprise positive match through double negation.
+         * XXXDCL this should be documented.
+         */
+
+        if (indirectmatch > 0) {
+                if (matchelt != NULL)
+                        *matchelt = e;
+                return (ISC_TRUE);
+        }
 		
-	case dns_aclelementtype_localnets:
-		if (env != NULL && env->localnets != NULL) {
-			inner = env->localnets;
-			goto nested;
-		} else {
-			break;
-		}
-		
-	default:
-		INSIST(0);
-		break;
-	}
+        /*
+         * A negative indirect match may have set *matchelt, but we don't
+         * want it set when we return.
+         */
 
+        if (matchelt != NULL)
+                *matchelt = NULL;
+		
 	return (ISC_FALSE);
 }	
 
@@ -285,15 +402,10 @@ destroy(dns_acl_t *dacl) {
 	unsigned int i;
 	for (i = 0; i < dacl->length; i++) {
 		dns_aclelement_t *de = &dacl->elements[i];
-		switch (de->type) {
-		case dns_aclelementtype_keyname:
-			dns_name_free(&de->u.keyname, dacl->mctx);
-			break;
-		case dns_aclelementtype_nestedacl:
-			dns_acl_detach(&de->u.nestedacl);
-			break;
-		default:
-			break;
+		if (de->type == dns_aclelementtype_keyname) {
+			dns_name_free(&de->keyname, dacl->mctx);
+		} else if (de->type == dns_aclelementtype_nestedacl) {
+			dns_acl_detach(&de->nestedacl);
 		}
 	}
 	if (dacl->elements != NULL)
@@ -301,6 +413,8 @@ destroy(dns_acl_t *dacl) {
 			    dacl->alloc * sizeof(dns_aclelement_t));
 	if (dacl->name != NULL)
 		isc_mem_free(dacl->mctx, dacl->name);
+        if (dacl->iptable != NULL)
+                dns_iptable_detach(&dacl->iptable);
 	isc_refcount_destroy(&dacl->refcount);
 	dacl->magic = 0;
 	isc_mem_put(dacl->mctx, dacl, sizeof(*dacl));
@@ -317,69 +431,79 @@ dns_acl_detach(dns_acl_t **aclp) {
 	*aclp = NULL;
 }
 
-isc_boolean_t
-dns_aclelement_equal(const dns_aclelement_t *ea, const dns_aclelement_t *eb) {
-	if (ea->type != eb->type)
-		return (ISC_FALSE);
-	switch (ea->type) {
-	case dns_aclelementtype_ipprefix:
-		if (ea->u.ip_prefix.prefixlen !=
-		    eb->u.ip_prefix.prefixlen)
-			return (ISC_FALSE);
-		return (isc_netaddr_eqprefix(&ea->u.ip_prefix.address,
-					     &eb->u.ip_prefix.address,
-					     ea->u.ip_prefix.prefixlen));
-	case dns_aclelementtype_keyname:
-		return (dns_name_equal(&ea->u.keyname, &eb->u.keyname));
-	case dns_aclelementtype_nestedacl:
-		return (dns_acl_equal(ea->u.nestedacl, eb->u.nestedacl));
-	case dns_aclelementtype_localhost:
-	case dns_aclelementtype_localnets:
-	case dns_aclelementtype_any:
-		return (ISC_TRUE);
-	default:
-		INSIST(0);
-		return (ISC_FALSE);
-	}
-}
 
-isc_boolean_t
-dns_acl_equal(const dns_acl_t *a, const dns_acl_t *b) {
-	unsigned int i;
-	if (a == b)
-		return (ISC_TRUE);
-	if (a->length != b->length)
-		return (ISC_FALSE);
-	for (i = 0; i < a->length; i++) {
-		if (! dns_aclelement_equal(&a->elements[i],
-					   &b->elements[i]))
-			return (ISC_FALSE);
-	}
-	return (ISC_TRUE);
+static isc_once_t	insecure_prefix_once = ISC_ONCE_INIT;
+static isc_mutex_t	insecure_prefix_lock;
+static isc_boolean_t	insecure_prefix_found;
+
+static void
+initialize_action(void) {
+        RUNTIME_CHECK(isc_mutex_init(&insecure_prefix_lock) == ISC_R_SUCCESS);
 }
 
-static isc_boolean_t
-is_loopback(const dns_aclipprefix_t *p) {
-	switch (p->address.family) {
-	case AF_INET:
-		if (p->prefixlen == 32 &&
-		    htonl(p->address.type.in.s_addr) == INADDR_LOOPBACK)
-			return (ISC_TRUE);
+/*
+ * Called via isc_radix_walk() to find IP table nodes that are
+ * insecure.
+ */
+static void
+is_insecure(isc_prefix_t *prefix, void *data) {
+	isc_boolean_t secure = * (isc_boolean_t *)data;
+
+        /* Negated entries are always secure */
+        if (!secure) {
+                return; 
+        }
+
+        /* If loopback prefix found, return */
+	switch (prefix->family) {
+	    case AF_INET:
+		if (prefix->bitlen == 32 &&
+		    htonl(prefix->add.sin.s_addr) == INADDR_LOOPBACK)
+                        return;
 		break;
-	case AF_INET6:
-		if (p->prefixlen == 128 &&
-		    IN6_IS_ADDR_LOOPBACK(&p->address.type.in6))
-			return (ISC_TRUE);
+	    case AF_INET6:
+		if (prefix->bitlen == 128 &&
+		    IN6_IS_ADDR_LOOPBACK(&prefix->add.sin6))
+                        return;
 		break;
-	default:
+	    default:
 		break;
 	}
-	return (ISC_FALSE);
+
+        /* Non-negated, non-loopback */
+        insecure_prefix_found = ISC_TRUE;
+        return;
 }
 
+/*
+ * Return ISC_TRUE iff the acl 'a' is considered insecure, that is,
+ * if it contains IP addresses other than those of the local host.
+ * This is intended for applications such as printing warning 
+ * messages for suspect ACLs; it is not intended for making access
+ * control decisions.  We make no guarantee that an ACL for which
+ * this function returns ISC_FALSE is safe.
+ */
 isc_boolean_t
 dns_acl_isinsecure(const dns_acl_t *a) {
 	unsigned int i;
+	isc_boolean_t insecure;
+
+	RUNTIME_CHECK(isc_once_do(&insecure_prefix_once,
+				  initialize_action) == ISC_R_SUCCESS);
+
+        /*
+         * Walk radix tree to find out if there are any non-negated,
+         * non-loopback prefixes.
+         */
+	LOCK(&insecure_prefix_lock);
+        insecure_prefix_found = ISC_FALSE;
+        isc_radix_process(a->iptable->radix, is_insecure);
+	insecure = insecure_prefix_found;
+	UNLOCK(&insecure_prefix_lock);
+        if (insecure)
+                return(ISC_TRUE);
+			
+        /* Now check non-radix elements */
 	for (i = 0; i < a->length; i++) {
 		dns_aclelement_t *e = &a->elements[i];
 
@@ -388,34 +512,31 @@ dns_acl_isinsecure(const dns_acl_t *a) {
 			continue;
 
 		switch (e->type) {
-		case dns_aclelementtype_ipprefix:
-			/* The loopback address is considered secure. */
-			if (! is_loopback(&e->u.ip_prefix))
-				return (ISC_TRUE);
-			continue;
-			
-		case dns_aclelementtype_keyname:
-		case dns_aclelementtype_localhost:
+		    case dns_aclelementtype_keyname:
+		    case dns_aclelementtype_localhost:
 			continue;
 
-		case dns_aclelementtype_nestedacl:
-			if (dns_acl_isinsecure(e->u.nestedacl))
-				return (ISC_TRUE);
-			continue;
-			
-		case dns_aclelementtype_localnets:
-		case dns_aclelementtype_any:
+                    case dns_aclelementtype_nestedacl:
+                        if (dns_acl_isinsecure(e->nestedacl))
+                                return (ISC_TRUE);
+                        continue;
+
+		    case dns_aclelementtype_localnets:
 			return (ISC_TRUE);
 
-		default:
+		    default:
 			INSIST(0);
 			return (ISC_TRUE);
 		}
 	}
+
 	/* No insecure elements were found. */
 	return (ISC_FALSE);
 }
 
+/*
+ * Initialize ACL environment, setting up localhost and localnets ACLs
+ */
 isc_result_t
 dns_aclenv_init(isc_mem_t *mctx, dns_aclenv_t *env) {
 	isc_result_t result;