1 /* $OpenBSD: tree.c,v 1.17 2016/02/06 23:50:10 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 58 static time_t tree_evaluate_recurse(int *, unsigned char **, int *, 59 struct tree *); 60 static void do_data_copy(int *, unsigned char **, int *, unsigned char *, int); 61 62 pair 63 cons(caddr_t car, pair cdr) 64 { 65 pair foo; 66 67 foo = calloc(1, sizeof *foo); 68 if (!foo) 69 error("no memory for cons."); 70 foo->car = car; 71 foo->cdr = cdr; 72 return foo; 73 } 74 75 struct tree_cache * 76 tree_cache(struct tree *tree) 77 { 78 struct tree_cache *tc; 79 80 tc = new_tree_cache("tree_cache"); 81 if (!tc) 82 return 0; 83 tc->value = NULL; 84 tc->len = tc->buf_size = 0; 85 tc->timeout = 0; 86 tc->tree = tree; 87 return tc; 88 } 89 90 struct tree * 91 tree_const(unsigned char *data, int len) 92 { 93 unsigned char *d; 94 struct tree *nt; 95 96 d = calloc(1, len); 97 nt = calloc(1, sizeof(struct tree)); 98 if (!nt || !d) 99 error("No memory for constant data tree node."); 100 101 memcpy(d, data, len); 102 103 nt->op = TREE_CONST; 104 nt->data.const_val.data = d; 105 nt->data.const_val.len = len; 106 107 return nt; 108 } 109 110 struct tree * 111 tree_concat(struct tree *left, struct tree *right) 112 { 113 struct tree *nt; 114 115 /* 116 * If we're concatenating a null tree to a non-null tree, just 117 * return the non-null tree; if both trees are null, return 118 * a null tree. 119 */ 120 if (!left) 121 return right; 122 if (!right) 123 return left; 124 125 /* If both trees are constant, combine them. */ 126 if (left->op == TREE_CONST && right->op == TREE_CONST) { 127 unsigned char *buf; 128 129 buf = calloc(1, left->data.const_val.len 130 + right->data.const_val.len); 131 132 if (!buf) 133 error("No memory to concatenate constants."); 134 memcpy(buf, left->data.const_val.data, 135 left->data.const_val.len); 136 memcpy(buf + left->data.const_val.len, 137 right->data.const_val.data, right->data.const_val.len); 138 free(left->data.const_val.data); 139 free(right->data.const_val.data); 140 left->data.const_val.data = buf; 141 left->data.const_val.len += right->data.const_val.len; 142 free(right); 143 return left; 144 } 145 146 /* Otherwise, allocate a new node to concatenate the two. */ 147 nt = calloc(1, sizeof(struct tree)); 148 if (!nt) 149 error("No memory for data tree concatenation node."); 150 nt->op = TREE_CONCAT; 151 nt->data.concat.left = left; 152 nt->data.concat.right = right; 153 return nt; 154 } 155 156 struct tree * 157 tree_limit(struct tree *tree, int limit) 158 { 159 struct tree *rv; 160 161 /* If the tree we're limiting is constant, limit it now. */ 162 if (tree->op == TREE_CONST) { 163 if (tree->data.const_val.len > limit) 164 tree->data.const_val.len = limit; 165 return tree; 166 } 167 168 /* Otherwise, put in a node which enforces the limit on evaluation. */ 169 rv = calloc(1, sizeof(struct tree)); 170 if (!rv) { 171 warning("No memory for data tree limit node."); 172 return NULL; 173 } 174 rv->op = TREE_LIMIT; 175 rv->data.limit.tree = tree; 176 rv->data.limit.limit = limit; 177 return rv; 178 } 179 180 int 181 tree_evaluate(struct tree_cache *tree_cache) 182 { 183 unsigned char *bp = tree_cache->value; 184 int bc = tree_cache->buf_size; 185 int bufix = 0; 186 187 /* 188 * If there's no tree associated with this cache, it evaluates to a 189 * constant and that was detected at startup. 190 */ 191 if (!tree_cache->tree) 192 return 1; 193 194 /* Try to evaluate the tree without allocating more memory... */ 195 tree_cache->timeout = tree_evaluate_recurse(&bufix, &bp, &bc, 196 tree_cache->tree); 197 198 /* No additional allocation needed? */ 199 if (bufix <= bc) { 200 tree_cache->len = bufix; 201 return 1; 202 } 203 204 /* 205 * If we can't allocate more memory, return with what we 206 * have (maybe nothing). 207 */ 208 bp = calloc(1, bufix); 209 if (!bp) { 210 warning("no more memory for option data"); 211 return 0; 212 } 213 214 /* Record the change in conditions... */ 215 bc = bufix; 216 bufix = 0; 217 218 /* 219 * Note that the size of the result shouldn't change on the 220 * second call to tree_evaluate_recurse, since we haven't 221 * changed the ``current'' time. 222 */ 223 tree_evaluate_recurse(&bufix, &bp, &bc, tree_cache->tree); 224 225 /* 226 * Free the old buffer if needed, then store the new buffer 227 * location and size and return. 228 */ 229 free(tree_cache->value); 230 tree_cache->value = bp; 231 tree_cache->len = bufix; 232 tree_cache->buf_size = bc; 233 return 1; 234 } 235 236 static time_t 237 tree_evaluate_recurse(int *bufix, unsigned char **bufp, 238 int *bufcount, struct tree *tree) 239 { 240 int limit; 241 time_t t1, t2; 242 243 switch (tree->op) { 244 case TREE_CONCAT: 245 t1 = tree_evaluate_recurse(bufix, bufp, bufcount, 246 tree->data.concat.left); 247 t2 = tree_evaluate_recurse(bufix, bufp, bufcount, 248 tree->data.concat.right); 249 if (t1 > t2) 250 return t2; 251 return t1; 252 253 case TREE_CONST: 254 do_data_copy(bufix, bufp, bufcount, tree->data.const_val.data, 255 tree->data.const_val.len); 256 t1 = MAX_TIME; 257 return t1; 258 259 case TREE_LIMIT: 260 limit = *bufix + tree->data.limit.limit; 261 t1 = tree_evaluate_recurse(bufix, bufp, bufcount, 262 tree->data.limit.tree); 263 *bufix = limit; 264 return t1; 265 266 default: 267 warning("Bad node id in tree: %d.", tree->op); 268 t1 = MAX_TIME; 269 return t1; 270 } 271 } 272 273 static void 274 do_data_copy(int *bufix, unsigned char **bufp, int *bufcount, 275 unsigned char *data, int len) 276 { 277 int space = *bufcount - *bufix; 278 279 /* If there's more space than we need, use only what we need. */ 280 if (space > len) 281 space = len; 282 283 /* 284 * Copy as much data as will fit, then increment the buffer index 285 * by the amount we actually had to copy, which could be more. 286 */ 287 if (space > 0) 288 memcpy(*bufp + *bufix, data, space); 289 *bufix += len; 290 } 291