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

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
}