1 /* tree.c 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 #ifndef lint 44 static char copyright[] = 45 "$Id: tree.c,v 1.10 1997/05/09 08:14:57 mellon Exp $ Copyright (c) 1995, 1996, 1997 The Internet Software Consortium. All rights reserved.\n"; 46 #endif /* not lint */ 47 48 #include <rosdhcp.h> 49 50 static TIME tree_evaluate_recurse PROTO ((int *, unsigned char **, int *, 51 struct tree *)); 52 static TIME do_host_lookup PROTO ((int *, unsigned char **, int *, 53 struct dns_host_entry *)); 54 static void do_data_copy PROTO ((int *, unsigned char **, int *, 55 unsigned char *, int)); 56 57 pair cons (car, cdr) 58 caddr_t car; 59 pair cdr; 60 { 61 pair foo = (pair)dmalloc (sizeof *foo, "cons"); 62 if (!foo) 63 error ("no memory for cons."); 64 foo -> car = car; 65 foo -> cdr = cdr; 66 return foo; 67 } 68 69 struct tree_cache *tree_cache (tree) 70 struct tree *tree; 71 { 72 struct tree_cache *tc; 73 74 tc = new_tree_cache ("tree_cache"); 75 if (!tc) 76 return 0; 77 tc -> value = (unsigned char *)0; 78 tc -> len = tc -> buf_size = 0; 79 tc -> timeout = 0; 80 tc -> tree = tree; 81 return tc; 82 } 83 84 struct tree *tree_host_lookup (name) 85 char *name; 86 { 87 struct tree *nt; 88 nt = new_tree ("tree_host_lookup"); 89 if (!nt) 90 error ("No memory for host lookup tree node."); 91 nt -> op = TREE_HOST_LOOKUP; 92 nt -> data.host_lookup.host = enter_dns_host (name); 93 return nt; 94 } 95 96 struct dns_host_entry *enter_dns_host (name) 97 char *name; 98 { 99 struct dns_host_entry *dh; 100 101 if (!(dh = (struct dns_host_entry *)dmalloc 102 (sizeof (struct dns_host_entry), "enter_dns_host")) 103 || !(dh -> hostname = dmalloc (strlen (name) + 1, 104 "enter_dns_host"))) 105 error ("Can't allocate space for new host."); 106 strcpy (dh -> hostname, name); 107 dh -> data = (unsigned char *)0; 108 dh -> data_len = 0; 109 dh -> buf_len = 0; 110 dh -> timeout = 0; 111 return dh; 112 } 113 114 struct tree *tree_const (data, len) 115 unsigned char *data; 116 int len; 117 { 118 struct tree *nt; 119 if (!(nt = new_tree ("tree_const")) 120 || !(nt -> data.const_val.data = 121 (unsigned char *)dmalloc (len, "tree_const"))) 122 error ("No memory for constant data tree node."); 123 nt -> op = TREE_CONST; 124 memcpy (nt -> data.const_val.data, data, len); 125 nt -> data.const_val.len = len; 126 return nt; 127 } 128 129 struct tree *tree_concat (left, right) 130 struct tree *left, *right; 131 { 132 struct tree *nt; 133 134 /* If we're concatenating a null tree to a non-null tree, just 135 return the non-null tree; if both trees are null, return 136 a null tree. */ 137 if (!left) 138 return right; 139 if (!right) 140 return left; 141 142 /* If both trees are constant, combine them. */ 143 if (left -> op == TREE_CONST && right -> op == TREE_CONST) { 144 unsigned char *buf = dmalloc (left -> data.const_val.len 145 + right -> data.const_val.len, 146 "tree_concat"); 147 if (!buf) 148 error ("No memory to concatenate constants."); 149 memcpy (buf, left -> data.const_val.data, 150 left -> data.const_val.len); 151 memcpy (buf + left -> data.const_val.len, 152 right -> data.const_val.data, 153 right -> data.const_val.len); 154 dfree (left -> data.const_val.data, "tree_concat"); 155 dfree (right -> data.const_val.data, "tree_concat"); 156 left -> data.const_val.data = buf; 157 left -> data.const_val.len += right -> data.const_val.len; 158 free_tree (right, "tree_concat"); 159 return left; 160 } 161 162 /* Otherwise, allocate a new node to concatenate the two. */ 163 if (!(nt = new_tree ("tree_concat"))) 164 error ("No memory for data tree concatenation node."); 165 nt -> op = TREE_CONCAT; 166 nt -> data.concat.left = left; 167 nt -> data.concat.right = right; 168 return nt; 169 } 170 171 struct tree *tree_limit (tree, limit) 172 struct tree *tree; 173 int limit; 174 { 175 struct tree *rv; 176 177 /* If the tree we're limiting is constant, limit it now. */ 178 if (tree -> op == TREE_CONST) { 179 if (tree -> data.const_val.len > limit) 180 tree -> data.const_val.len = limit; 181 return tree; 182 } 183 184 /* Otherwise, put in a node which enforces the limit on evaluation. */ 185 rv = new_tree ("tree_limit"); 186 if (!rv) 187 return (struct tree *)0; 188 rv -> op = TREE_LIMIT; 189 rv -> data.limit.tree = tree; 190 rv -> data.limit.limit = limit; 191 return rv; 192 } 193 194 int tree_evaluate (tree_cache) 195 struct tree_cache *tree_cache; 196 { 197 unsigned char *bp = tree_cache -> value; 198 int bc = tree_cache -> buf_size; 199 int bufix = 0; 200 201 /* If there's no tree associated with this cache, it evaluates 202 to a constant and that was detected at startup. */ 203 if (!tree_cache -> tree) 204 return 1; 205 206 /* Try to evaluate the tree without allocating more memory... */ 207 tree_cache -> timeout = tree_evaluate_recurse (&bufix, &bp, &bc, 208 tree_cache -> tree); 209 210 /* No additional allocation needed? */ 211 if (bufix <= bc) { 212 tree_cache -> len = bufix; 213 return 1; 214 } 215 216 /* If we can't allocate more memory, return with what we 217 have (maybe nothing). */ 218 if (!(bp = (unsigned char *)dmalloc (bufix, "tree_evaluate"))) 219 return 0; 220 221 /* Record the change in conditions... */ 222 bc = bufix; 223 bufix = 0; 224 225 /* Note that the size of the result shouldn't change on the 226 second call to tree_evaluate_recurse, since we haven't 227 changed the ``current'' time. */ 228 tree_evaluate_recurse (&bufix, &bp, &bc, tree_cache -> tree); 229 230 /* Free the old buffer if needed, then store the new buffer 231 location and size and return. */ 232 if (tree_cache -> value) 233 dfree (tree_cache -> value, "tree_evaluate"); 234 tree_cache -> value = bp; 235 tree_cache -> len = bufix; 236 tree_cache -> buf_size = bc; 237 return 1; 238 } 239 240 static TIME tree_evaluate_recurse (bufix, bufp, bufcount, tree) 241 int *bufix; 242 unsigned char **bufp; 243 int *bufcount; 244 struct tree *tree; 245 { 246 int limit; 247 TIME t1, t2; 248 249 switch (tree -> op) { 250 case TREE_CONCAT: 251 t1 = tree_evaluate_recurse (bufix, bufp, bufcount, 252 tree -> data.concat.left); 253 t2 = tree_evaluate_recurse (bufix, bufp, bufcount, 254 tree -> data.concat.right); 255 if (t1 > t2) 256 return t2; 257 return t1; 258 259 case TREE_HOST_LOOKUP: 260 return do_host_lookup (bufix, bufp, bufcount, 261 tree -> data.host_lookup.host); 262 263 case TREE_CONST: 264 do_data_copy (bufix, bufp, bufcount, 265 tree -> data.const_val.data, 266 tree -> data.const_val.len); 267 t1 = MAX_TIME; 268 return t1; 269 270 case TREE_LIMIT: 271 limit = *bufix + tree -> data.limit.limit; 272 t1 = tree_evaluate_recurse (bufix, bufp, bufcount, 273 tree -> data.limit.tree); 274 *bufix = limit; 275 return t1; 276 277 default: 278 warn ("Bad node id in tree: %d."); 279 t1 = MAX_TIME; 280 return t1; 281 } 282 } 283 284 static TIME do_host_lookup (bufix, bufp, bufcount, dns) 285 int *bufix; 286 unsigned char **bufp; 287 int *bufcount; 288 struct dns_host_entry *dns; 289 { 290 struct hostent *h; 291 int i; 292 int new_len; 293 294 #ifdef DEBUG_EVAL 295 debug ("time: now = %d dns = %d %d diff = %d", 296 cur_time, dns -> timeout, cur_time - dns -> timeout); 297 #endif 298 299 /* If the record hasn't timed out, just copy the data and return. */ 300 if (cur_time <= dns -> timeout) { 301 #ifdef DEBUG_EVAL 302 debug ("easy copy: %x %d %x", 303 dns -> data, dns -> data_len, 304 dns -> data ? *(int *)(dns -> data) : 0); 305 #endif 306 do_data_copy (bufix, bufp, bufcount, 307 dns -> data, dns -> data_len); 308 return dns -> timeout; 309 } 310 #ifdef DEBUG_EVAL 311 debug ("Looking up %s", dns -> hostname); 312 #endif 313 314 /* Otherwise, look it up... */ 315 h = gethostbyname (dns -> hostname); 316 if (!h) { 317 #ifndef NO_H_ERRNO 318 switch (h_errno) { 319 case HOST_NOT_FOUND: 320 #endif 321 warn ("%s: host unknown.", dns -> hostname); 322 #ifndef NO_H_ERRNO 323 break; 324 case TRY_AGAIN: 325 warn ("%s: temporary name server failure", 326 dns -> hostname); 327 break; 328 case NO_RECOVERY: 329 warn ("%s: name server failed", dns -> hostname); 330 break; 331 case NO_DATA: 332 warn ("%s: no A record associated with address", 333 dns -> hostname); 334 } 335 #endif /* !NO_H_ERRNO */ 336 337 /* Okay to try again after a minute. */ 338 return cur_time + 60; 339 } 340 341 #ifdef DEBUG_EVAL 342 debug ("Lookup succeeded; first address is %x", 343 h -> h_addr_list [0]); 344 #endif 345 346 /* Count the number of addresses we got... */ 347 for (i = 0; h -> h_addr_list [i]; i++) 348 ; 349 350 /* Do we need to allocate more memory? */ 351 new_len = i * h -> h_length; 352 if (dns -> buf_len < i) { 353 unsigned char *buf = 354 (unsigned char *)dmalloc (new_len, "do_host_lookup"); 355 /* If we didn't get more memory, use what we have. */ 356 if (!buf) { 357 new_len = dns -> buf_len; 358 if (!dns -> buf_len) { 359 dns -> timeout = cur_time + 60; 360 return dns -> timeout; 361 } 362 } else { 363 if (dns -> data) 364 dfree (dns -> data, "do_host_lookup"); 365 dns -> data = buf; 366 dns -> buf_len = new_len; 367 } 368 } 369 370 /* Addresses are conveniently stored one to the buffer, so we 371 have to copy them out one at a time... :'( */ 372 for (i = 0; i < new_len / h -> h_length; i++) { 373 memcpy (dns -> data + h -> h_length * i, 374 h -> h_addr_list [i], h -> h_length); 375 } 376 #ifdef DEBUG_EVAL 377 debug ("dns -> data: %x h -> h_addr_list [0]: %x", 378 *(int *)(dns -> data), h -> h_addr_list [0]); 379 #endif 380 dns -> data_len = new_len; 381 382 /* Set the timeout for an hour from now. 383 XXX This should really use the time on the DNS reply. */ 384 dns -> timeout = cur_time + 3600; 385 386 #ifdef DEBUG_EVAL 387 debug ("hard copy: %x %d %x", 388 dns -> data, dns -> data_len, *(int *)(dns -> data)); 389 #endif 390 do_data_copy (bufix, bufp, bufcount, dns -> data, dns -> data_len); 391 return dns -> timeout; 392 } 393 394 static void do_data_copy (bufix, bufp, bufcount, data, len) 395 int *bufix; 396 unsigned char **bufp; 397 int *bufcount; 398 unsigned char *data; 399 int len; 400 { 401 int space = *bufcount - *bufix; 402 403 /* If there's more space than we need, use only what we need. */ 404 if (space > len) 405 space = len; 406 407 /* Copy as much data as will fit, then increment the buffer index 408 by the amount we actually had to copy, which could be more. */ 409 if (space > 0) 410 memcpy (*bufp + *bufix, data, space); 411 *bufix += len; 412 } 413