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->only_match_scope_zero = 0; 101 node->edge[0] = NULL; 102 node->edge[1] = NULL; 103 node->parent_edge = NULL; 104 node->next = NULL; 105 node->prev = NULL; 106 return node; 107 } 108 109 /** Size in bytes of node and parent edge 110 * @param tree: tree the node lives in 111 * @param n: node which size must be calculated 112 * @return size in bytes. 113 **/ 114 static inline size_t 115 node_size(const struct addrtree *tree, const struct addrnode *n) 116 { 117 return sizeof *n + sizeof *n->parent_edge + n->parent_edge->len + 118 (n->elem?tree->sizefunc(n->elem):0); 119 } 120 121 struct addrtree * 122 addrtree_create(addrlen_t max_depth, void (*delfunc)(void *, void *), 123 size_t (*sizefunc)(void *), void *env, uint32_t max_node_count) 124 { 125 struct addrtree *tree; 126 log_assert(delfunc != NULL); 127 log_assert(sizefunc != NULL); 128 tree = (struct addrtree *)calloc(1, sizeof(*tree)); 129 if (!tree) 130 return NULL; 131 tree->root = node_create(tree, NULL, 0, 0); 132 if (!tree->root) { 133 free(tree); 134 return NULL; 135 } 136 tree->size_bytes = sizeof *tree + sizeof *tree->root; 137 tree->first = NULL; 138 tree->last = NULL; 139 tree->max_depth = max_depth; 140 tree->delfunc = delfunc; 141 tree->sizefunc = sizefunc; 142 tree->env = env; 143 tree->node_count = 0; 144 tree->max_node_count = max_node_count; 145 return tree; 146 } 147 148 /** 149 * Scrub a node clean of elem 150 * @param tree: tree the node lives in. 151 * @param node: node to be cleaned. 152 */ 153 static void 154 clean_node(struct addrtree *tree, struct addrnode *node) 155 { 156 if (!node->elem) return; 157 tree->size_bytes -= tree->sizefunc(node->elem); 158 tree->delfunc(tree->env, node->elem); 159 node->only_match_scope_zero = 0; 160 node->elem = NULL; 161 } 162 163 /** Remove specified node from LRU list */ 164 static void 165 lru_pop(struct addrtree *tree, struct addrnode *node) 166 { 167 if (node == tree->first) { 168 if (!node->next) { /* it is the last as well */ 169 tree->first = NULL; 170 tree->last = NULL; 171 } else { 172 tree->first = node->next; 173 tree->first->prev = NULL; 174 } 175 } else if (node == tree->last) { /* but not the first */ 176 tree->last = node->prev; 177 tree->last->next = NULL; 178 } else { 179 node->prev->next = node->next; 180 node->next->prev = node->prev; 181 } 182 } 183 184 /** Add node to LRU list as most recently used. */ 185 static void 186 lru_push(struct addrtree *tree, struct addrnode *node) 187 { 188 if (!tree->first) { 189 tree->first = node; 190 node->prev = NULL; 191 } else { 192 tree->last->next = node; 193 node->prev = tree->last; 194 } 195 tree->last = node; 196 node->next = NULL; 197 } 198 199 /** Move node to the end of LRU list */ 200 static void 201 lru_update(struct addrtree *tree, struct addrnode *node) 202 { 203 if (tree->root == node) return; 204 lru_pop(tree, node); 205 lru_push(tree, node); 206 } 207 208 /** 209 * Purge a node from the tree. Node and parentedge are cleaned and 210 * free'd. 211 * @param tree: Tree the node lives in. 212 * @param node: Node to be freed 213 */ 214 static void 215 purge_node(struct addrtree *tree, struct addrnode *node) 216 { 217 struct addredge *parent_edge, *child_edge = NULL; 218 int index; 219 int keep = node->edge[0] && node->edge[1]; 220 221 clean_node(tree, node); 222 parent_edge = node->parent_edge; 223 if (keep || !parent_edge) return; 224 tree->node_count--; 225 index = parent_edge->parent_index; 226 child_edge = node->edge[!node->edge[0]]; 227 if (child_edge) { 228 child_edge->parent_node = parent_edge->parent_node; 229 child_edge->parent_index = index; 230 } 231 parent_edge->parent_node->edge[index] = child_edge; 232 tree->size_bytes -= node_size(tree, node); 233 free(parent_edge->str); 234 free(parent_edge); 235 lru_pop(tree, node); 236 free(node); 237 } 238 239 /** 240 * If a limit is set remove old nodes while above that limit. 241 * @param tree: Tree to be cleaned up. 242 */ 243 static void 244 lru_cleanup(struct addrtree *tree) 245 { 246 struct addrnode *n, *p; 247 int children; 248 if (tree->max_node_count == 0) return; 249 while (tree->node_count > tree->max_node_count) { 250 n = tree->first; 251 if (!n) break; 252 children = (n->edge[0] != NULL) + (n->edge[1] != NULL); 253 /** Don't remove this node, it is either the root or we can't 254 * do without it because it has 2 children */ 255 if (children == 2 || !n->parent_edge) { 256 lru_update(tree, n); 257 continue; 258 } 259 p = n->parent_edge->parent_node; 260 purge_node(tree, n); 261 /** Since we removed n, n's parent p is eligible for deletion 262 * if it is not the root node, caries no data and has only 1 263 * child */ 264 children = (p->edge[0] != NULL) + (p->edge[1] != NULL); 265 if (!p->elem && children == 1 && p->parent_edge) { 266 purge_node(tree, p); 267 } 268 } 269 } 270 271 inline size_t 272 addrtree_size(const struct addrtree *tree) 273 { 274 return tree?tree->size_bytes:0; 275 } 276 277 void addrtree_delete(struct addrtree *tree) 278 { 279 struct addrnode *n; 280 if (!tree) return; 281 clean_node(tree, tree->root); 282 free(tree->root); 283 tree->size_bytes -= sizeof(struct addrnode); 284 while ((n = tree->first)) { 285 tree->first = n->next; 286 clean_node(tree, n); 287 tree->size_bytes -= node_size(tree, n); 288 free(n->parent_edge->str); 289 free(n->parent_edge); 290 free(n); 291 } 292 log_assert(sizeof *tree == addrtree_size(tree)); 293 free(tree); 294 } 295 296 /** 297 * Get N'th bit from address 298 * @param addr: address to inspect 299 * @param addrlen: length of addr in bits 300 * @param n: index of bit to test. Must be in range [0, addrlen) 301 * @return 0 or 1 302 */ 303 static int 304 getbit(const addrkey_t *addr, addrlen_t addrlen, addrlen_t n) 305 { 306 log_assert(addrlen > n); 307 (void)addrlen; 308 return (int)(addr[n/KEYWIDTH]>>((KEYWIDTH-1)-(n%KEYWIDTH))) & 1; 309 } 310 311 /** 312 * Test for equality on N'th bit. 313 * @return 0 for equal, 1 otherwise 314 */ 315 static inline int 316 cmpbit(const addrkey_t *key1, const addrkey_t *key2, addrlen_t n) 317 { 318 addrkey_t c = key1[n/KEYWIDTH] ^ key2[n/KEYWIDTH]; 319 return (int)(c >> ((KEYWIDTH-1)-(n%KEYWIDTH))) & 1; 320 } 321 322 /** 323 * Common number of bits in prefix. 324 * @param s1: first prefix. 325 * @param l1: length of s1 in bits. 326 * @param s2: second prefix. 327 * @param l2: length of s2 in bits. 328 * @param skip: nr of bits already checked. 329 * @return common number of bits. 330 */ 331 static addrlen_t 332 bits_common(const addrkey_t *s1, addrlen_t l1, 333 const addrkey_t *s2, addrlen_t l2, addrlen_t skip) 334 { 335 addrlen_t len, i; 336 len = (l1 > l2) ? l2 : l1; 337 log_assert(skip < len); 338 for (i = skip; i < len; i++) { 339 if (cmpbit(s1, s2, i)) return i; 340 } 341 return len; 342 } 343 344 /** 345 * Tests if s1 is a substring of s2 346 * @param s1: first prefix. 347 * @param l1: length of s1 in bits. 348 * @param s2: second prefix. 349 * @param l2: length of s2 in bits. 350 * @param skip: nr of bits already checked. 351 * @return 1 for substring, 0 otherwise 352 */ 353 static int 354 issub(const addrkey_t *s1, addrlen_t l1, 355 const addrkey_t *s2, addrlen_t l2, addrlen_t skip) 356 { 357 return bits_common(s1, l1, s2, l2, skip) == l1; 358 } 359 360 void 361 addrtree_insert(struct addrtree *tree, const addrkey_t *addr, 362 addrlen_t sourcemask, addrlen_t scope, void *elem, time_t ttl, 363 time_t now, int only_match_scope_zero) 364 { 365 struct addrnode *newnode, *node; 366 struct addredge *edge; 367 int index; 368 addrlen_t common, depth; 369 370 node = tree->root; 371 log_assert(node != NULL); 372 373 /* Protect our cache against too much fine-grained data */ 374 if (tree->max_depth < scope) scope = tree->max_depth; 375 /* Server answer was less specific than question */ 376 if (scope < sourcemask) sourcemask = scope; 377 378 depth = 0; 379 while (1) { 380 log_assert(depth <= sourcemask); 381 /* Case 1: update existing node */ 382 if (depth == sourcemask) { 383 /* update this node's scope and data */ 384 clean_node(tree, node); 385 node->ttl = ttl; 386 node->only_match_scope_zero = only_match_scope_zero; 387 node->elem = elem; 388 node->scope = scope; 389 tree->size_bytes += tree->sizefunc(elem); 390 return; 391 } 392 index = getbit(addr, sourcemask, depth); 393 /* Get an edge to an unexpired node */ 394 edge = node->edge[index]; 395 while (edge) { 396 /* Purge all expired nodes on path */ 397 if (!edge->node->elem || edge->node->ttl >= now) 398 break; 399 purge_node(tree, edge->node); 400 edge = node->edge[index]; 401 } 402 /* Case 2: New leafnode */ 403 if (!edge) { 404 newnode = node_create(tree, elem, scope, ttl); 405 if (!newnode) return; 406 if (!edge_create(newnode, addr, sourcemask, node, 407 index)) { 408 clean_node(tree, newnode); 409 tree->node_count--; 410 free(newnode); 411 return; 412 } 413 tree->size_bytes += node_size(tree, newnode); 414 lru_push(tree, newnode); 415 lru_cleanup(tree); 416 return; 417 } 418 /* Case 3: Traverse edge */ 419 common = bits_common(edge->str, edge->len, addr, sourcemask, 420 depth); 421 if (common == edge->len) { 422 /* We update the scope of intermediate nodes. Apparently 423 * the * authority changed its mind. If we would not do 424 * this we might not be able to reach our new node. */ 425 node->scope = scope; 426 depth = edge->len; 427 node = edge->node; 428 continue; 429 } 430 /* Case 4: split. */ 431 if (!(newnode = node_create(tree, NULL, 0, 0))) 432 return; 433 node->edge[index] = NULL; 434 if (!edge_create(newnode, addr, common, node, index)) { 435 node->edge[index] = edge; 436 clean_node(tree, newnode); 437 tree->node_count--; 438 free(newnode); 439 return; 440 } 441 lru_push(tree, newnode); 442 /* connect existing child to our new node */ 443 index = getbit(edge->str, edge->len, common); 444 newnode->edge[index] = edge; 445 edge->parent_node = newnode; 446 edge->parent_index = (int)index; 447 448 if (common == sourcemask) { 449 /* Data is stored in the node */ 450 newnode->elem = elem; 451 newnode->scope = scope; 452 newnode->ttl = ttl; 453 newnode->only_match_scope_zero = only_match_scope_zero; 454 } 455 456 tree->size_bytes += node_size(tree, newnode); 457 458 if (common != sourcemask) { 459 /* Data is stored in other leafnode */ 460 node = newnode; 461 newnode = node_create(tree, elem, scope, ttl); 462 if (!edge_create(newnode, addr, sourcemask, node, 463 index^1)) { 464 clean_node(tree, newnode); 465 tree->node_count--; 466 free(newnode); 467 return; 468 } 469 tree->size_bytes += node_size(tree, newnode); 470 lru_push(tree, newnode); 471 } 472 lru_cleanup(tree); 473 return; 474 } 475 } 476 477 struct addrnode * 478 addrtree_find(struct addrtree *tree, const addrkey_t *addr, 479 addrlen_t sourcemask, time_t now) 480 { 481 struct addrnode *node = tree->root; 482 struct addredge *edge = NULL; 483 addrlen_t depth = 0; 484 485 log_assert(node != NULL); 486 while (1) { 487 /* Current node more specific then question. */ 488 log_assert(depth <= sourcemask); 489 /* does this node have data? if yes, see if we have a match */ 490 if (node->elem && node->ttl >= now && 491 !(sourcemask != 0 && node->only_match_scope_zero)) { 492 /* saved at wrong depth */; 493 log_assert(node->scope >= depth); 494 if (depth == node->scope || 495 (node->scope > sourcemask && 496 depth == sourcemask)) { 497 /* Authority indicates it does not have a more 498 * precise answer or we cannot ask a more 499 * specific question. */ 500 lru_update(tree, node); 501 return node; 502 } 503 } 504 /* This is our final depth, but we haven't found an answer. */ 505 if (depth == sourcemask) 506 return NULL; 507 /* Find an edge to traverse */ 508 edge = node->edge[getbit(addr, sourcemask, depth)]; 509 if (!edge || !edge->node) 510 return NULL; 511 if (edge->len > sourcemask ) 512 return NULL; 513 if (!issub(edge->str, edge->len, addr, sourcemask, depth)) 514 return NULL; 515 log_assert(depth < edge->len); 516 depth = edge->len; 517 node = edge->node; 518 } 519 } 520 521 /** Wrappers for static functions to unit test */ 522 int unittest_wrapper_addrtree_cmpbit(const addrkey_t *key1, 523 const addrkey_t *key2, addrlen_t n) { 524 return cmpbit(key1, key2, n); 525 } 526 addrlen_t unittest_wrapper_addrtree_bits_common(const addrkey_t *s1, 527 addrlen_t l1, const addrkey_t *s2, addrlen_t l2, addrlen_t skip) { 528 return bits_common(s1, l1, s2, l2, skip); 529 } 530 int unittest_wrapper_addrtree_getbit(const addrkey_t *addr, 531 addrlen_t addrlen, addrlen_t n) { 532 return getbit(addr, addrlen, n); 533 } 534 int unittest_wrapper_addrtree_issub(const addrkey_t *s1, addrlen_t l1, 535 const addrkey_t *s2, addrlen_t l2, addrlen_t skip) { 536 return issub(s1, l1, s2, l2, skip); 537 } 538