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