Head

GCC Code Coverage Report

Directory:	./		Exec	Total	Coverage
File:	usr.sbin/dhcpd/tree.c	Lines:	0	105	0.0 %
Date:	2017-11-07	Branches:	0	40	0.0 %


/*	$OpenBSD: tree.c,v 1.18 2017/02/13 19:13:14 krw 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 <sys/types.h>
#include <sys/socket.h>

#include <net/if.h>

#include <netinet/in.h>

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "dhcp.h"
#include "tree.h"
#include "dhcpd.h"
#include "log.h"

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

pair
cons(caddr_t car, pair cdr)
{
	pair foo;

	foo = calloc(1, sizeof *foo);
	if (!foo)
		fatalx("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 = NULL;
	tc->len = tc->buf_size = 0;
	tc->timeout = 0;
	tc->tree = tree;
	return tc;
}

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

	d = calloc(1, len);
	nt = calloc(1, sizeof(struct tree));
	if (!nt || !d)
		fatalx("No memory for constant data tree node.");

	memcpy(d, data, len);

	nt->op = TREE_CONST;
	nt->data.const_val.data = d;
	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;

		buf = calloc(1, left->data.const_val.len
		    + right->data.const_val.len);

		if (!buf)
			fatalx("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);
		free(left->data.const_val.data);
		free(right->data.const_val.data);
		left->data.const_val.data = buf;
		left->data.const_val.len += right->data.const_val.len;
		free(right);
		return left;
	}

	/* Otherwise, allocate a new node to concatenate the two. */
	nt = calloc(1, sizeof(struct tree));
	if (!nt)
		fatalx("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 = calloc(1, sizeof(struct tree));
	if (!rv) {
		log_warnx("No memory for data tree limit node.");
		return NULL;
	}
	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).
	 */
	bp = calloc(1, bufix);
	if (!bp) {
		log_warnx("no more memory for option data");
		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.
	 */
	free(tree_cache->value);
	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_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:
		log_warnx("Bad node id in tree: %d.", tree->op);
		t1 = MAX_TIME;
		return t1;
	}
}

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;
}


Generated by: GCOVR (Version 3.3)

Line	Branch	Exec	Source
1			/* $OpenBSD: tree.c,v 1.18 2017/02/13 19:13:14 krw Exp $ */
2
3			/* Routines for manipulating parse trees... */
4
5			/*
6			* Copyright (c) 1995, 1996, 1997 The Internet Software Consortium.
7			* All rights reserved.
8			*
9			* Redistribution and use in source and binary forms, with or without
10			* modification, are permitted provided that the following conditions
11			* are met:
12			*
13			* 1. Redistributions of source code must retain the above copyright
14			* notice, this list of conditions and the following disclaimer.
15			* 2. Redistributions in binary form must reproduce the above copyright
16			* notice, this list of conditions and the following disclaimer in the
17			* documentation and/or other materials provided with the distribution.
18			* 3. Neither the name of The Internet Software Consortium nor the names
19			* of its contributors may be used to endorse or promote products derived
20			* from this software without specific prior written permission.
21			*
22			* THIS SOFTWARE IS PROVIDED BY THE INTERNET SOFTWARE CONSORTIUM AND
23			* CONTRIBUTORS ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES,
24			* INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
25			* MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
26			* DISCLAIMED. IN NO EVENT SHALL THE INTERNET SOFTWARE CONSORTIUM OR
27			* CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
28			* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
29			* LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
30			* USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
31			* ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
32			* OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
33			* OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
34			* SUCH DAMAGE.
35			*
36			* This software has been written for the Internet Software Consortium
37			* by Ted Lemon <mellon@fugue.com> in cooperation with Vixie
38			* Enterprises. To learn more about the Internet Software Consortium,
39			* see ``http://www.vix.com/isc''. To learn more about Vixie
40			* Enterprises, see ``http://www.vix.com''.
41			*/
42
43			#include <sys/types.h>
44			#include <sys/socket.h>
45
46			#include <net/if.h>
47
48			#include <netinet/in.h>
49
50			#include <stdio.h>
51			#include <stdlib.h>
52			#include <string.h>
53
54			#include "dhcp.h"
55			#include "tree.h"
56			#include "dhcpd.h"
57			#include "log.h"
58
59			static time_t tree_evaluate_recurse(int , unsigned char , int ,
60			struct tree *);
61			static void do_data_copy(int , unsigned char , int , unsigned char *, int);
62
63			pair
64			cons(caddr_t car, pair cdr)
65			{
66			pair foo;
67
68			foo = calloc(1, sizeof *foo);
69			if (!foo)
70			fatalx("no memory for cons.");
71			foo->car = car;
72			foo->cdr = cdr;
73			return foo;
74			}
75
76			struct tree_cache *
77			tree_cache(struct tree *tree)
78			{
79			struct tree_cache *tc;
80
81			tc = new_tree_cache("tree_cache");
82			if (!tc)
83			return 0;
84			tc->value = NULL;
85			tc->len = tc->buf_size = 0;
86			tc->timeout = 0;
87			tc->tree = tree;
88			return tc;
89			}
90
91			struct tree *
92			tree_const(unsigned char *data, int len)
93			{
94			unsigned char *d;
95			struct tree *nt;
96
97			d = calloc(1, len);
98			nt = calloc(1, sizeof(struct tree));
99			if (!nt \|\| !d)
100			fatalx("No memory for constant data tree node.");
101
102			memcpy(d, data, len);
103
104			nt->op = TREE_CONST;
105			nt->data.const_val.data = d;
106			nt->data.const_val.len = len;
107
108			return nt;
109			}
110
111			struct tree *
112			tree_concat(struct tree left, struct tree right)
113			{
114			struct tree *nt;
115
116			/*
117			* If we're concatenating a null tree to a non-null tree, just
118			* return the non-null tree; if both trees are null, return
119			* a null tree.
120			*/
121			if (!left)
122			return right;
123			if (!right)
124			return left;
125
126			/* If both trees are constant, combine them. */
127			if (left->op == TREE_CONST && right->op == TREE_CONST) {
128			unsigned char *buf;
129
130			buf = calloc(1, left->data.const_val.len
131			+ right->data.const_val.len);
132
133			if (!buf)
134			fatalx("No memory to concatenate constants.");
135			memcpy(buf, left->data.const_val.data,
136			left->data.const_val.len);
137			memcpy(buf + left->data.const_val.len,
138			right->data.const_val.data, right->data.const_val.len);
139			free(left->data.const_val.data);
140			free(right->data.const_val.data);
141			left->data.const_val.data = buf;
142			left->data.const_val.len += right->data.const_val.len;
143			free(right);
144			return left;
145			}
146
147			/* Otherwise, allocate a new node to concatenate the two. */
148			nt = calloc(1, sizeof(struct tree));
149			if (!nt)
150			fatalx("No memory for data tree concatenation node.");
151			nt->op = TREE_CONCAT;
152			nt->data.concat.left = left;
153			nt->data.concat.right = right;
154			return nt;
155			}
156
157			struct tree *
158			tree_limit(struct tree *tree, int limit)
159			{
160			struct tree *rv;
161
162			/* If the tree we're limiting is constant, limit it now. */
163			if (tree->op == TREE_CONST) {
164			if (tree->data.const_val.len > limit)
165			tree->data.const_val.len = limit;
166			return tree;
167			}
168
169			/* Otherwise, put in a node which enforces the limit on evaluation. */
170			rv = calloc(1, sizeof(struct tree));
171			if (!rv) {
172			log_warnx("No memory for data tree limit node.");
173			return NULL;
174			}
175			rv->op = TREE_LIMIT;
176			rv->data.limit.tree = tree;
177			rv->data.limit.limit = limit;
178			return rv;
179			}
180
181			int
182			tree_evaluate(struct tree_cache *tree_cache)
183			{
184			unsigned char *bp = tree_cache->value;
185			int bc = tree_cache->buf_size;
186			int bufix = 0;
187
188			/*
189			* If there's no tree associated with this cache, it evaluates to a
190			* constant and that was detected at startup.
191			*/
192			if (!tree_cache->tree)
193			return 1;
194
195			/* Try to evaluate the tree without allocating more memory... */
196			tree_cache->timeout = tree_evaluate_recurse(&bufix, &bp, &bc,
197			tree_cache->tree);
198
199			/* No additional allocation needed? */
200			if (bufix <= bc) {
201			tree_cache->len = bufix;
202			return 1;
203			}
204
205			/*
206			* If we can't allocate more memory, return with what we
207			* have (maybe nothing).
208			*/
209			bp = calloc(1, bufix);
210			if (!bp) {
211			log_warnx("no more memory for option data");
212			return 0;
213			}
214
215			/* Record the change in conditions... */
216			bc = bufix;
217			bufix = 0;
218
219			/*
220			* Note that the size of the result shouldn't change on the
221			* second call to tree_evaluate_recurse, since we haven't
222			* changed the ``current'' time.
223			*/
224			tree_evaluate_recurse(&bufix, &bp, &bc, tree_cache->tree);
225
226			/*
227			* Free the old buffer if needed, then store the new buffer
228			* location and size and return.
229			*/
230			free(tree_cache->value);
231			tree_cache->value = bp;
232			tree_cache->len = bufix;
233			tree_cache->buf_size = bc;
234			return 1;
235			}
236
237			static time_t
238			tree_evaluate_recurse(int bufix, unsigned char *bufp,
239			int bufcount, struct tree tree)
240			{
241			int limit;
242			time_t t1, t2;
243
244			switch (tree->op) {
245			case TREE_CONCAT:
246			t1 = tree_evaluate_recurse(bufix, bufp, bufcount,
247			tree->data.concat.left);
248			t2 = tree_evaluate_recurse(bufix, bufp, bufcount,
249			tree->data.concat.right);
250			if (t1 > t2)
251			return t2;
252			return t1;
253
254			case TREE_CONST:
255			do_data_copy(bufix, bufp, bufcount, tree->data.const_val.data,
256			tree->data.const_val.len);
257			t1 = MAX_TIME;
258			return t1;
259
260			case TREE_LIMIT:
261			limit = *bufix + tree->data.limit.limit;
262			t1 = tree_evaluate_recurse(bufix, bufp, bufcount,
263			tree->data.limit.tree);
264			*bufix = limit;
265			return t1;
266
267			default:
268			log_warnx("Bad node id in tree: %d.", tree->op);
269			t1 = MAX_TIME;
270			return t1;
271			}
272			}
273
274			static void
275			do_data_copy(int bufix, unsigned char bufp, int bufcount,
276			unsigned char *data, int len)
277			{
278			int space = bufcount - bufix;
279
280			/* If there's more space than we need, use only what we need. */
281			if (space > len)
282			space = len;
283
284			/*
285			* Copy as much data as will fit, then increment the buffer index
286			* by the amount we actually had to copy, which could be more.
287			*/
288			if (space > 0)
289			memcpy(bufp + bufix, data, space);
290			*bufix += len;
291			}