contrib/isc-dhcp/common/tree.c

   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 "dhcpd.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 }