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