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 } 533