path: root/usr.sbin/dhcpd/tree.c

/*	$Id: tree.c,v 1.5 2004/04/15 21:47:13 hshoexer Exp $	*/

/* Routines for manipulating parse trees... */

/*
 * Copyright (c) 1995, 1996, 1997 The Internet Software Consortium.
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. 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.
 * 3. Neither the name of The Internet Software Consortium nor the names
 *    of its contributors may be used to endorse or promote products derived
 *    from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE INTERNET SOFTWARE CONSORTIUM 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 INTERNET SOFTWARE CONSORTIUM 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.
 *
 * This software has been written for the Internet Software Consortium
 * by Ted Lemon <mellon@fugue.com> in cooperation with Vixie
 * Enterprises.  To learn more about the Internet Software Consortium,
 * see ``http://www.vix.com/isc''.  To learn more about Vixie
 * Enterprises, see ``http://www.vix.com''.
 */

#include "dhcpd.h"

static time_t tree_evaluate_recurse(int *, unsigned char **, int *,
    struct tree *);
static time_t do_host_lookup(int *, unsigned char **, int *,
    struct dns_host_entry *);
static void do_data_copy(int *, unsigned char **, int *, unsigned char *, int);

pair
cons(caddr_t car, pair cdr)
{
	pair	foo = (pair)dmalloc(sizeof *foo, "cons");
	if (!foo)
		error ("no memory for cons.");
	foo->car = car;
	foo->cdr = cdr;
	return foo;
}

struct tree_cache *
tree_cache(struct tree *tree)
{
	struct tree_cache	*tc;

	tc = new_tree_cache("tree_cache");
	if (!tc)
		return 0;
	tc->value = (unsigned char *)0;
	tc->len = tc->buf_size = 0;
	tc->timeout = 0;
	tc->tree = tree;
	return tc;
}

struct tree *
tree_host_lookup(char *name)
{
	struct tree	*nt;

	nt = new_tree("tree_host_lookup");
	if (!nt)
		error("No memory for host lookup tree node.");
	nt->op = TREE_HOST_LOOKUP;
	nt->data.host_lookup.host = enter_dns_host(name);
	return nt;
}

struct dns_host_entry *
enter_dns_host(char *name)
{
	struct dns_host_entry	*dh;
	int			 len = strlen(name) + 1;

	if (!(dh = (struct dns_host_entry *)dmalloc
	    (sizeof(struct dns_host_entry), "enter_dns_host")) ||
	    !(dh->hostname = dmalloc(len, "enter_dns_host")))
		error("Can't allocate space for new host.");
	strlcpy(dh->hostname, name, len);
	dh->data = (unsigned char *)0;
	dh->data_len = 0;
	dh->buf_len = 0;
	dh->timeout = 0;
	return dh;
}

struct tree *
tree_const(unsigned char *data, int len)
{
	struct tree	*nt;

	if (!(nt = new_tree("tree_const")) || !(nt->data.const_val.data =
	    (unsigned char *)dmalloc(len, "tree_const")))
		error("No memory for constant data tree node.");
	nt->op = TREE_CONST;
	memcpy(nt->data.const_val.data, data, len);
	nt->data.const_val.len = len;
	return nt;
}

struct tree *
tree_concat(struct tree *left, struct tree *right)
{
	struct tree	*nt;

	/* 
	 * If we're concatenating a null tree to a non-null tree, just
	 * return the non-null tree; if both trees are null, return
	 * a null tree.
	 */
	if (!left)
		return right;
	if (!right)
		return left;

	/* If both trees are constant, combine them. */
	if (left->op == TREE_CONST && right->op == TREE_CONST) {
		unsigned char *buf = dmalloc(left->data.const_val.len
		    + right->data.const_val.len, "tree_concat");
		if (!buf)
			error("No memory to concatenate constants.");
		memcpy(buf, left->data.const_val.data,
		    left->data.const_val.len);
		memcpy(buf + left->data.const_val.len,
		    right->data.const_val.data, right->data.const_val.len);
		dfree(left->data.const_val.data, "tree_concat");
		dfree(right->data.const_val.data, "tree_concat");
		left->data.const_val.data = buf;
		left->data.const_val.len += right->data.const_val.len;
		free_tree(right, "tree_concat");
		return left;
	}

	/* Otherwise, allocate a new node to concatenate the two. */
	if (!(nt = new_tree("tree_concat")))
		error("No memory for data tree concatenation node.");
	nt->op = TREE_CONCAT;
	nt->data.concat.left = left;
	nt->data.concat.right = right;
	return nt;
}

struct tree *
tree_limit(struct tree *tree, int limit)
{
	struct tree	*rv;

	/* If the tree we're limiting is constant, limit it now. */
	if (tree->op == TREE_CONST) {
		if (tree->data.const_val.len > limit)
			tree->data.const_val.len = limit;
		return tree;
	}

	/* Otherwise, put in a node which enforces the limit on evaluation. */
	rv = new_tree("tree_limit");
	if (!rv)
		return(struct tree *)0;
	rv->op = TREE_LIMIT;
	rv->data.limit.tree = tree;
	rv->data.limit.limit = limit;
	return rv;
}

int
tree_evaluate(struct tree_cache *tree_cache)
{
	unsigned char	*bp = tree_cache->value;
	int		 bc = tree_cache->buf_size;
	int		 bufix = 0;

	/* 
	 * If there's no tree associated with this cache, it evaluates to a
	 * constant and that was detected at startup.
	 */
	if (!tree_cache->tree)
		return 1;

	/* Try to evaluate the tree without allocating more memory... */
	tree_cache->timeout = tree_evaluate_recurse(&bufix, &bp, &bc,
	    tree_cache->tree);

	/* No additional allocation needed? */
	if (bufix <= bc) {
		tree_cache->len = bufix;
		return 1;
	}

	/*
	 * If we can't allocate more memory, return with what we
	 * have (maybe nothing).
	 */
	if (!(bp = (unsigned char *)dmalloc(bufix, "tree_evaluate")))
		return 0;

	/* Record the change in conditions... */
	bc = bufix;
	bufix = 0;

	/* 
	 * Note that the size of the result shouldn't change on the
	 * second call to tree_evaluate_recurse, since we haven't
	 * changed the ``current'' time.
	 */
	tree_evaluate_recurse(&bufix, &bp, &bc, tree_cache->tree);

	/*
	 * Free the old buffer if needed, then store the new buffer
	 * location and size and return.
	 */
	if (tree_cache->value)
		dfree(tree_cache->value, "tree_evaluate");
	tree_cache->value = bp;
	tree_cache->len = bufix;
	tree_cache->buf_size = bc;
	return 1;
}

static time_t
tree_evaluate_recurse(int *bufix, unsigned char **bufp,
    int *bufcount, struct tree *tree)
{
	int	limit;
	time_t	t1, t2;

	switch (tree->op) {
	case TREE_CONCAT:
		t1 = tree_evaluate_recurse(bufix, bufp, bufcount,
		    tree->data.concat.left);
		t2 = tree_evaluate_recurse(bufix, bufp, bufcount,
		    tree->data.concat.right);
		if (t1 > t2)
			return t2;
		return t1;

	case TREE_HOST_LOOKUP:
		return do_host_lookup(bufix, bufp, bufcount,
		    tree->data.host_lookup.host);

	case TREE_CONST:
		do_data_copy(bufix, bufp, bufcount, tree->data.const_val.data,
		    tree->data.const_val.len);
		t1 = MAX_TIME;
		return t1;

	case TREE_LIMIT:
		limit = *bufix + tree->data.limit.limit;
		t1 = tree_evaluate_recurse(bufix, bufp, bufcount,
		    tree->data.limit.tree);
		*bufix = limit;
		return t1;

	default:
		warn("Bad node id in tree: %d.", tree->op);
		t1 = MAX_TIME;
		return t1;
	}
}

static time_t
do_host_lookup(int *bufix, unsigned char **bufp, int *bufcount,
    struct dns_host_entry *dns)
{
	struct hostent	*h;
	int		 i;
	int		 new_len;

#ifdef DEBUG_EVAL
	debug("time: now = %d  dns = %d %d  diff = %d", cur_time, dns->timeout,
	    cur_time - dns->timeout);
#endif

	/* If the record hasn't timed out, just copy the data and return. */
	if (cur_time <= dns->timeout) {
#ifdef DEBUG_EVAL
		debug("easy copy: %x %d %x", dns->data, dns->data_len,
		    dns->data ? *(int *)(dns->data) : 0);
#endif
		do_data_copy(bufix, bufp, bufcount, dns->data, dns->data_len);
		return dns->timeout;
	}
#ifdef DEBUG_EVAL
	debug("Looking up %s", dns->hostname);
#endif

	/* Otherwise, look it up... */
	h = gethostbyname(dns->hostname);
	if (h == NULL) {
		switch (h_errno) {
		case HOST_NOT_FOUND:
			warn("%s: host unknown.", dns->hostname);
			break;
		case TRY_AGAIN:
			warn("%s: temporary name server failure",
			      dns->hostname);
			break;
		case NO_RECOVERY:
			warn("%s: name server failed", dns->hostname);
			break;
		case NO_DATA:
			warn("%s: no A record associated with address",
			    dns->hostname);
		}
		/* Okay to try again after a minute. */
		return cur_time + 60;
	}

#ifdef DEBUG_EVAL
	debug("Lookup succeeded; first address is %x",
	       h->h_addr_list[0]);
#endif

	/* Count the number of addresses we got... */
	for (i = 0; h->h_addr_list[i]; i++)
		;

	/* Do we need to allocate more memory? */
	new_len = i * h->h_length;
	if (dns->buf_len < i) {
		unsigned char *buf =
			(unsigned char *)dmalloc(new_len, "do_host_lookup");
		/* If we didn't get more memory, use what we have. */
		if (!buf) {
			new_len = dns->buf_len;
			if (!dns->buf_len) {
				dns->timeout = cur_time + 60;
				return dns->timeout;
			}
		} else {
			if (dns->data)
				dfree(dns->data, "do_host_lookup");
			dns->data = buf;
			dns->buf_len = new_len;
		}
	}

	/*
	 * Addresses are conveniently stored one to the buffer, so we
	 * have to copy them out one at a time... :'(
	 */
	for (i = 0; i < new_len / h->h_length; i++)
		memcpy(dns->data + h->h_length * i, h->h_addr_list[i],
		    h->h_length);
#ifdef DEBUG_EVAL
	debug("dns->data: %x  h->h_addr_list[0]: %x",
	    *(int *)(dns->data), h->h_addr_list[0]);
#endif
	dns->data_len = new_len;

	/*
	 * Set the timeout for an hour from now.
	 * XXX This should really use the time on the DNS reply.
	 */
	dns->timeout = cur_time + 3600;

#ifdef DEBUG_EVAL
	debug("hard copy: %x %d %x", dns->data, dns->data_len,
	    *(int *)(dns->data));
#endif
	do_data_copy(bufix, bufp, bufcount, dns->data, dns->data_len);
	return dns->timeout;
}

static void
do_data_copy(int *bufix, unsigned char **bufp, int *bufcount,
    unsigned char *data, int len)
{
	int	space = *bufcount - *bufix;

	/* If there's more space than we need, use only what we need. */
	if (space > len)
		space = len;

	/*
	 * Copy as much data as will fit, then increment the buffer index
	 * by the amount we actually had to copy, which could be more.
	 */
	if (space > 0)
		memcpy(*bufp + *bufix, data, space);
	*bufix += len;
}