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