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
cons(caddr_t car,pair cdr)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 *
tree_cache(struct tree * tree)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 *
tree_const(unsigned char * data,int len)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 *
tree_concat(struct tree * left,struct tree * right)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 *
tree_limit(struct tree * tree,int limit)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
tree_evaluate(struct tree_cache * tree_cache)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
tree_evaluate_recurse(int * bufix,unsigned char ** bufp,int * bufcount,struct tree * tree)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
do_data_copy(int * bufix,unsigned char ** bufp,int * bufcount,unsigned char * data,int len)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 }
292