contrib/unbound/edns-subnet/addrtree.c

   1 /*
   2  * edns-subnet/addrtree.c -- radix tree for edns subnet cache.
   3  *
   4  * Copyright (c) 2013, NLnet Labs. All rights reserved.
   5  *
   6  * This software is open source.
   7  *
   8  * Redistribution and use in source and binary forms, with or without
   9  * modification, are permitted provided that the following conditions
  10  * are met:
  11  *
  12  * Redistributions of source code must retain the above copyright notice,
  13  * this list of conditions and the following disclaimer.
  14  *
  15  * Redistributions in binary form must reproduce the above copyright notice,
  16  * this list of conditions and the following disclaimer in the documentation
  17  * and/or other materials provided with the distribution.
  18  *
  19  * Neither the name of the NLNET LABS nor the names of its contributors may
  20  * be used to endorse or promote products derived from this software without
  21  * specific prior written permission.
  22  *
  23  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  24  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  25  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  26  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  27  * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  28  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
  29  * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
  30  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
  31  * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
  32  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
  33  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  34  */
  35 /** \file
  36  * addrtree -- radix tree for edns subnet cache.
  37  */
  38
  39 #include "config.h"
  40 #include "util/log.h"
  41 #include "util/data/msgreply.h"
  42 #include "util/module.h"
  43 #include "addrtree.h"
  44
  45 /**
  46  * Create a new edge
  47  * @param node: Child node this edge will connect to.
  48  * @param addr: full key to this edge.
  49  * @param addrlen: length of relevant part of key for this node
  50  * @param parent_node: Parent node for node
  51  * @param parent_index: Index of child node at parent node
  52  * @return new addredge or NULL on failure
  53  */
  54 static struct addredge *
  55 edge_create(struct addrnode *node, const addrkey_t *addr,
  56         addrlen_t addrlen, struct addrnode *parent_node, int parent_index)
  57 {
  58         size_t n;
  59         struct addredge *edge = (struct addredge *)malloc( sizeof (*edge) );
  60         if (!edge)
  61                 return NULL;
  62         edge->node = node;
  63         edge->len = addrlen;
  64         edge->parent_index = parent_index;
  65         edge->parent_node = parent_node;
  66         /* ceil() */
  67         n = (size_t)((addrlen / KEYWIDTH) + ((addrlen % KEYWIDTH != 0)?1:0));
  68         edge->str = (addrkey_t *)calloc(n, sizeof (addrkey_t));
  69         if (!edge->str) {
  70                 free(edge);
  71                 return NULL;
  72         }
  73         memcpy(edge->str, addr, n * sizeof (addrkey_t));
  74         /* Only manipulate other objects after successful alloc */
  75         node->parent_edge = edge;
  76         log_assert(parent_node->edge[parent_index] == NULL);
  77         parent_node->edge[parent_index] = edge;
  78         return edge;
  79 }
  80
  81 /**
  82  * Create a new node
  83  * @param tree: Tree the node lives in.
  84  * @param elem: Element to store at this node
  85  * @param scope: Scopemask from server reply
  86  * @param ttl: Element is valid up to this time. Absolute, seconds
  87  * @return new addrnode or NULL on failure
  88  */
  89 static struct addrnode *
  90 node_create(struct addrtree *tree, void *elem, addrlen_t scope,
  91         time_t ttl)
  92 {
  93         struct addrnode* node = (struct addrnode *)malloc( sizeof (*node) );
  94         if (!node)
  95                 return NULL;
  96         node->elem = elem;
  97         tree->node_count++;
  98         node->scope = scope;
  99         node->ttl = ttl;
 100         node->edge[0] = NULL;
 101         node->edge[1] = NULL;
 102         node->parent_edge = NULL;
 103         node->next = NULL;
 104         node->prev = NULL;
 105         return node;
 106 }
 107
 108 /** Size in bytes of node and parent edge
 109  * @param tree: tree the node lives in
 110  * @param n: node which size must be calculated
 111  * @return size in bytes.
 112  **/
 113 static inline size_t
 114 node_size(const struct addrtree *tree, const struct addrnode *n)
 115 {
 116         return sizeof *n + sizeof *n->parent_edge + n->parent_edge->len +
 117                 (n->elem?tree->sizefunc(n->elem):0);
 118 }
 119
 120 struct addrtree *
 121 addrtree_create(addrlen_t max_depth, void (*delfunc)(void *, void *),
 122         size_t (*sizefunc)(void *), void *env, uint32_t max_node_count)
 123 {
 124         struct addrtree *tree;
 125         log_assert(delfunc != NULL);
 126         log_assert(sizefunc != NULL);
 127         tree = (struct addrtree *)calloc(1, sizeof(*tree));
 128         if (!tree)
 129                 return NULL;
 130         tree->root = node_create(tree, NULL, 0, 0);
 131         if (!tree->root) {
 132                 free(tree);
 133                 return NULL;
 134         }
 135         tree->size_bytes = sizeof *tree + sizeof *tree->root;
 136         tree->first = NULL;
 137         tree->last = NULL;
 138         tree->max_depth = max_depth;
 139         tree->delfunc = delfunc;
 140         tree->sizefunc = sizefunc;
 141         tree->env = env;
 142         tree->node_count = 0;
 143         tree->max_node_count = max_node_count;
 144         return tree;
 145 }
 146
 147 /**
 148  * Scrub a node clean of elem
 149  * @param tree: tree the node lives in.
 150  * @param node: node to be cleaned.
 151  */
 152 static void
 153 clean_node(struct addrtree *tree, struct addrnode *node)
 154 {
 155         if (!node->elem) return;
 156         tree->size_bytes -= tree->sizefunc(node->elem);
 157         tree->delfunc(tree->env, node->elem);
 158         node->elem = NULL;
 159 }
 160
 161 /** Remove specified node from LRU list */
 162 static void
 163 lru_pop(struct addrtree *tree, struct addrnode *node)
 164 {
 165         if (node == tree->first) {
 166                 if (!node->next) { /* it is the last as well */
 167                         tree->first = NULL;
 168                         tree->last = NULL;
 169                 } else {
 170                         tree->first = node->next;
 171                         tree->first->prev = NULL;
 172                 }
 173         } else if (node == tree->last) { /* but not the first */
 174                 tree->last = node->prev;
 175                 tree->last->next = NULL;
 176         } else {
 177                 node->prev->next = node->next;
 178                 node->next->prev = node->prev;
 179         }
 180 }
 181
 182 /** Add node to LRU list as most recently used. */
 183 static void
 184 lru_push(struct addrtree *tree, struct addrnode *node)
 185 {
 186         if (!tree->first) {
 187                 tree->first = node;
 188                 node->prev = NULL;
 189         } else {
 190                 tree->last->next = node;
 191                 node->prev = tree->last;
 192         }
 193         tree->last = node;
 194         node->next = NULL;
 195 }
 196
 197 /** Move node to the end of LRU list */
 198 static void
 199 lru_update(struct addrtree *tree, struct addrnode *node)
 200 {
 201         if (tree->root == node) return;
 202         lru_pop(tree, node);
 203         lru_push(tree, node);
 204 }
 205
 206 /**
 207  * Purge a node from the tree. Node and parentedge are cleaned and
 208  * free'd.
 209  * @param tree: Tree the node lives in.
 210  * @param node: Node to be freed
 211  */
 212 static void
 213 purge_node(struct addrtree *tree, struct addrnode *node)
 214 {
 215         struct addredge *parent_edge, *child_edge = NULL;
 216         int index;
 217         int keep = node->edge[0] && node->edge[1];
 218
 219         clean_node(tree, node);
 220         parent_edge = node->parent_edge;
 221         if (keep || !parent_edge) return;
 222         tree->node_count--;
 223         index = parent_edge->parent_index;
 224         child_edge = node->edge[!node->edge[0]];
 225         if (child_edge) {
 226                 child_edge->parent_node  = parent_edge->parent_node;
 227                 child_edge->parent_index = index;
 228         }
 229         parent_edge->parent_node->edge[index] = child_edge;
 230         tree->size_bytes -= node_size(tree, node);
 231         free(parent_edge->str);
 232         free(parent_edge);
 233         lru_pop(tree, node);
 234         free(node);
 235 }
 236
 237 /**
 238  * If a limit is set remove old nodes while above that limit.
 239  * @param tree: Tree to be cleaned up.
 240  */
 241 static void
 242 lru_cleanup(struct addrtree *tree)
 243 {
 244         struct addrnode *n, *p;
 245         int children;
 246         if (tree->max_node_count == 0) return;
 247         while (tree->node_count > tree->max_node_count) {
 248                 n = tree->first;
 249                 if (!n) break;
 250                 children = (n->edge[0] != NULL) + (n->edge[1] != NULL);
 251                 /** Don't remove this node, it is either the root or we can't
 252                  * do without it because it has 2 children */
 253                 if (children == 2 || !n->parent_edge) {
 254                         lru_update(tree, n);
 255                         continue;
 256                 }
 257                 p = n->parent_edge->parent_node;
 258                 purge_node(tree, n);
 259                 /** Since we removed n, n's parent p is eligible for deletion
 260                  * if it is not the root node, caries no data and has only 1
 261                  * child */
 262                 children = (p->edge[0] != NULL) + (p->edge[1] != NULL);
 263                 if (!p->elem && children == 1 && p->parent_edge) {
 264                         purge_node(tree, p);
 265                 }
 266         }
 267 }
 268
 269 inline size_t
 270 addrtree_size(const struct addrtree *tree)
 271 {
 272         return tree?tree->size_bytes:0;
 273 }
 274
 275 void addrtree_delete(struct addrtree *tree)
 276 {
 277         struct addrnode *n;
 278         if (!tree) return;
 279         clean_node(tree, tree->root);
 280         free(tree->root);
 281         tree->size_bytes -= sizeof(struct addrnode);
 282         while ((n = tree->first)) {
 283                 tree->first = n->next;
 284                 clean_node(tree, n);
 285                 tree->size_bytes -= node_size(tree, n);
 286                 free(n->parent_edge->str);
 287                 free(n->parent_edge);
 288                 free(n);
 289         }
 290         log_assert(sizeof *tree == addrtree_size(tree));
 291         free(tree);
 292 }
 293
 294 /**
 295  * Get N'th bit from address
 296  * @param addr: address to inspect
 297  * @param addrlen: length of addr in bits
 298  * @param n: index of bit to test. Must be in range [0, addrlen)
 299  * @return 0 or 1
 300  */
 301 static int
 302 getbit(const addrkey_t *addr, addrlen_t addrlen, addrlen_t n)
 303 {
 304         log_assert(addrlen > n);
 305         (void)addrlen;
 306         return (int)(addr[n/KEYWIDTH]>>((KEYWIDTH-1)-(n%KEYWIDTH))) & 1;
 307 }
 308
 309 /**
 310  * Test for equality on N'th bit.
 311  * @return 0 for equal, 1 otherwise
 312  */
 313 static inline int
 314 cmpbit(const addrkey_t *key1, const addrkey_t *key2, addrlen_t n)
 315 {
 316         addrkey_t c = key1[n/KEYWIDTH] ^ key2[n/KEYWIDTH];
 317         return (int)(c >> ((KEYWIDTH-1)-(n%KEYWIDTH))) & 1;
 318 }
 319
 320 /**
 321  * Common number of bits in prefix.
 322  * @param s1: first prefix.
 323  * @param l1: length of s1 in bits.
 324  * @param s2: second prefix.
 325  * @param l2: length of s2 in bits.
 326  * @param skip: nr of bits already checked.
 327  * @return common number of bits.
 328  */
 329 static addrlen_t
 330 bits_common(const addrkey_t *s1, addrlen_t l1,
 331         const addrkey_t *s2, addrlen_t l2, addrlen_t skip)
 332 {
 333         addrlen_t len, i;
 334         len = (l1 > l2) ? l2 : l1;
 335         log_assert(skip < len);
 336         for (i = skip; i < len; i++) {
 337                 if (cmpbit(s1, s2, i)) return i;
 338         }
 339         return len;
 340 }
 341
 342 /**
 343  * Tests if s1 is a substring of s2
 344  * @param s1: first prefix.
 345  * @param l1: length of s1 in bits.
 346  * @param s2: second prefix.
 347  * @param l2: length of s2 in bits.
 348  * @param skip: nr of bits already checked.
 349  * @return 1 for substring, 0 otherwise
 350  */
 351 static int
 352 issub(const addrkey_t *s1, addrlen_t l1,
 353         const addrkey_t *s2, addrlen_t l2,  addrlen_t skip)
 354 {
 355         return bits_common(s1, l1, s2, l2, skip) == l1;
 356 }
 357
 358 void
 359 addrtree_insert(struct addrtree *tree, const addrkey_t *addr,
 360         addrlen_t sourcemask, addrlen_t scope, void *elem, time_t ttl,
 361         time_t now)
 362 {
 363         struct addrnode *newnode, *node;
 364         struct addredge *edge;
 365         int index;
 366         addrlen_t common, depth;
 367
 368         node = tree->root;
 369         log_assert(node != NULL);
 370
 371         /* Protect our cache against too much fine-grained data */
 372         if (tree->max_depth < scope) scope = tree->max_depth;
 373         /* Server answer was less specific than question */
 374         if (scope < sourcemask) sourcemask = scope;
 375
 376         depth = 0;
 377         while (1) {
 378                 log_assert(depth <= sourcemask);
 379                 /* Case 1: update existing node */
 380                 if (depth == sourcemask) {
 381                         /* update this node's scope and data */
 382                         clean_node(tree, node);
 383                         node->ttl = ttl;
 384                         node->elem = elem;
 385                         node->scope = scope;
 386                         tree->size_bytes += tree->sizefunc(elem);
 387                         return;
 388                 }
 389                 index = getbit(addr, sourcemask, depth);
 390                 /* Get an edge to an unexpired node */
 391                 edge = node->edge[index];
 392                 while (edge) {
 393                         /* Purge all expired nodes on path */
 394                         if (!edge->node->elem || edge->node->ttl >= now)
 395                                 break;
 396                         purge_node(tree, edge->node);
 397                         edge = node->edge[index];
 398                 }
 399                 /* Case 2: New leafnode */
 400                 if (!edge) {
 401                         newnode = node_create(tree, elem, scope, ttl);
 402                         if (!newnode) return;
 403                         if (!edge_create(newnode, addr, sourcemask, node,
 404                                 index)) {
 405                                 clean_node(tree, newnode);
 406                                 tree->node_count--;
 407                                 free(newnode);
 408                                 return;
 409                         }
 410                         tree->size_bytes += node_size(tree, newnode);
 411                         lru_push(tree, newnode);
 412                         lru_cleanup(tree);
 413                         return;
 414                 }
 415                 /* Case 3: Traverse edge */
 416                 common = bits_common(edge->str, edge->len, addr, sourcemask,
 417                         depth);
 418                 if (common == edge->len) {
 419                         /* We update the scope of intermediate nodes. Apparently
 420                          * the * authority changed its mind. If we would not do
 421                          * this we might not be able to reach our new node. */
 422                         node->scope = scope;
 423                         depth = edge->len;
 424                         node = edge->node;
 425                         continue;
 426                 }
 427                 /* Case 4: split. */
 428                 if (!(newnode = node_create(tree, NULL, 0, 0)))
 429                         return;
 430                 node->edge[index] = NULL;
 431                 if (!edge_create(newnode, addr, common, node, index)) {
 432                         node->edge[index] = edge;
 433                         clean_node(tree, newnode);
 434                         tree->node_count--;
 435                         free(newnode);
 436                         return;
 437                 }
 438                 lru_push(tree, newnode);
 439                 /* connect existing child to our new node */
 440                 index = getbit(edge->str, edge->len, common);
 441                 newnode->edge[index] = edge;
 442                 edge->parent_node = newnode;
 443                 edge->parent_index = (int)index;
 444
 445                 if (common == sourcemask) {
 446                         /* Data is stored in the node */
 447                         newnode->elem = elem;
 448                         newnode->scope = scope;
 449                         newnode->ttl = ttl;
 450                 }
 451
 452                 tree->size_bytes += node_size(tree, newnode);
 453
 454                 if (common != sourcemask) {
 455                         /* Data is stored in other leafnode */
 456                         node = newnode;
 457                         newnode = node_create(tree, elem, scope, ttl);
 458                         if (!edge_create(newnode, addr, sourcemask, node,
 459                                 index^1)) {
 460                                 clean_node(tree, newnode);
 461                                 tree->node_count--;
 462                                 free(newnode);
 463                                 return;
 464                         }
 465                         tree->size_bytes += node_size(tree, newnode);
 466                         lru_push(tree, newnode);
 467                 }
 468                 lru_cleanup(tree);
 469                 return;
 470         }
 471 }
 472
 473 struct addrnode *
 474 addrtree_find(struct addrtree *tree, const addrkey_t *addr,
 475         addrlen_t sourcemask, time_t now)
 476 {
 477         struct addrnode *node = tree->root;
 478         struct addredge *edge = NULL;
 479         addrlen_t depth = 0;
 480
 481         log_assert(node != NULL);
 482         while (1) {
 483                 /* Current node more specific then question. */
 484                 log_assert(depth <= sourcemask);
 485                 /* does this node have data? if yes, see if we have a match */
 486                 if (node->elem && node->ttl >= now) {
 487                         /* saved at wrong depth */;
 488                         log_assert(node->scope >= depth);
 489                         if (depth == node->scope ||
 490                                 (node->scope > sourcemask &&
 491                                  depth == sourcemask)) {
 492                                 /* Authority indicates it does not have a more
 493                                  * precise answer or we cannot ask a more
 494                                  * specific question. */
 495                                 lru_update(tree, node);
 496                                 return node;
 497                         }
 498                 }
 499                 /* This is our final depth, but we haven't found an answer. */
 500                 if (depth == sourcemask)
 501                         return NULL;
 502                 /* Find an edge to traverse */
 503                 edge = node->edge[getbit(addr, sourcemask, depth)];
 504                 if (!edge || !edge->node)
 505                         return NULL;
 506                 if (edge->len > sourcemask )
 507                         return NULL;
 508                 if (!issub(edge->str, edge->len, addr, sourcemask, depth))
 509                         return NULL;
 510                 log_assert(depth < edge->len);
 511                 depth = edge->len;
 512                 node = edge->node;
 513         }
 514 }
 515
 516 /** Wrappers for static functions to unit test */
 517 int unittest_wrapper_addrtree_cmpbit(const addrkey_t *key1,
 518         const addrkey_t *key2, addrlen_t n) {
 519         return cmpbit(key1, key2, n);
 520 }
 521 addrlen_t unittest_wrapper_addrtree_bits_common(const addrkey_t *s1,
 522         addrlen_t l1, const addrkey_t *s2, addrlen_t l2, addrlen_t skip) {
 523         return bits_common(s1, l1, s2, l2, skip);
 524 }
 525 int unittest_wrapper_addrtree_getbit(const addrkey_t *addr,
 526         addrlen_t addrlen, addrlen_t n) {
 527         return getbit(addr, addrlen, n);
 528 }
 529 int unittest_wrapper_addrtree_issub(const addrkey_t *s1, addrlen_t l1,
 530         const addrkey_t *s2, addrlen_t l2,  addrlen_t skip) {
 531         return issub(s1, l1, s2, l2, skip);
 532 }