1 /*
2 * Copyright (C) Internet Systems Consortium, Inc. ("ISC")
3 *
4 * SPDX-License-Identifier: MPL-2.0
5 *
6 * This Source Code Form is subject to the terms of the Mozilla Public
7 * License, v. 2.0. If a copy of the MPL was not distributed with this
8 * file, you can obtain one at https://mozilla.org/MPL/2.0/.
9 *
10 * See the COPYRIGHT file distributed with this work for additional
11 * information regarding copyright ownership.
12 */
13
14 /*
15 * This source was adapted from MRT's RCS Ids:
16 * Id: radix.c,v 1.10.2.1 1999/11/29 05:16:24 masaki Exp
17 * Id: prefix.c,v 1.37.2.9 2000/03/10 02:53:19 labovit Exp
18 */
19
20 #include <inttypes.h>
21
22 #include <isc/mem.h>
23 #include <isc/radix.h>
24 #include <isc/types.h>
25 #include <isc/util.h>
26
27 #define BIT_TEST(f, b) (((f) & (b)) != 0)
28
29 static isc_result_t
30 _new_prefix(isc_mem_t *mctx, isc_prefix_t **target, int family, void *dest,
31 int bitlen);
32
33 static void
34 _deref_prefix(isc_prefix_t *prefix);
35
36 static isc_result_t
37 _ref_prefix(isc_mem_t *mctx, isc_prefix_t **target, isc_prefix_t *prefix);
38
39 static int
40 _comp_with_mask(void *addr, void *dest, u_int mask);
41
42 static void
43 _clear_radix(isc_radix_tree_t *radix, isc_radix_destroyfunc_t func);
44
45 static isc_result_t
_new_prefix(isc_mem_t * mctx,isc_prefix_t ** target,int family,void * dest,int bitlen)46 _new_prefix(isc_mem_t *mctx, isc_prefix_t **target, int family, void *dest,
47 int bitlen) {
48 isc_prefix_t *prefix;
49
50 REQUIRE(target != NULL);
51
52 if (family != AF_INET6 && family != AF_INET && family != AF_UNSPEC) {
53 return (ISC_R_NOTIMPLEMENTED);
54 }
55
56 prefix = isc_mem_get(mctx, sizeof(isc_prefix_t));
57
58 if (family == AF_INET6) {
59 prefix->bitlen = (bitlen >= 0) ? bitlen : 128;
60 memmove(&prefix->add.sin6, dest, 16);
61 } else {
62 /* AF_UNSPEC is "any" or "none"--treat it as AF_INET */
63 prefix->bitlen = (bitlen >= 0) ? bitlen : 32;
64 memmove(&prefix->add.sin, dest, 4);
65 }
66
67 prefix->family = family;
68 prefix->mctx = NULL;
69 isc_mem_attach(mctx, &prefix->mctx);
70
71 isc_refcount_init(&prefix->refcount, 1);
72
73 *target = prefix;
74 return (ISC_R_SUCCESS);
75 }
76
77 static void
_deref_prefix(isc_prefix_t * prefix)78 _deref_prefix(isc_prefix_t *prefix) {
79 if (prefix != NULL) {
80 if (isc_refcount_decrement(&prefix->refcount) == 1) {
81 isc_refcount_destroy(&prefix->refcount);
82 isc_mem_putanddetach(&prefix->mctx, prefix,
83 sizeof(isc_prefix_t));
84 }
85 }
86 }
87
88 static isc_result_t
_ref_prefix(isc_mem_t * mctx,isc_prefix_t ** target,isc_prefix_t * prefix)89 _ref_prefix(isc_mem_t *mctx, isc_prefix_t **target, isc_prefix_t *prefix) {
90 INSIST(prefix != NULL);
91 INSIST((prefix->family == AF_INET && prefix->bitlen <= 32) ||
92 (prefix->family == AF_INET6 && prefix->bitlen <= 128) ||
93 (prefix->family == AF_UNSPEC && prefix->bitlen == 0));
94 REQUIRE(target != NULL && *target == NULL);
95
96 /*
97 * If this prefix is a static allocation, copy it into new memory.
98 * (Note, the refcount still has to be destroyed by the calling
99 * routine.)
100 */
101 if (isc_refcount_current(&prefix->refcount) == 0) {
102 isc_result_t ret;
103 ret = _new_prefix(mctx, target, prefix->family, &prefix->add,
104 prefix->bitlen);
105 return (ret);
106 }
107
108 isc_refcount_increment(&prefix->refcount);
109
110 *target = prefix;
111 return (ISC_R_SUCCESS);
112 }
113
114 static int
_comp_with_mask(void * addr,void * dest,u_int mask)115 _comp_with_mask(void *addr, void *dest, u_int mask) {
116 /* Mask length of zero matches everything */
117 if (mask == 0) {
118 return (1);
119 }
120
121 if (memcmp(addr, dest, mask / 8) == 0) {
122 u_int n = mask / 8;
123 u_int m = ((~0U) << (8 - (mask % 8)));
124
125 if ((mask % 8) == 0 ||
126 (((u_char *)addr)[n] & m) == (((u_char *)dest)[n] & m)) {
127 return (1);
128 }
129 }
130 return (0);
131 }
132
133 isc_result_t
isc_radix_create(isc_mem_t * mctx,isc_radix_tree_t ** target,int maxbits)134 isc_radix_create(isc_mem_t *mctx, isc_radix_tree_t **target, int maxbits) {
135 isc_radix_tree_t *radix;
136
137 REQUIRE(target != NULL && *target == NULL);
138
139 radix = isc_mem_get(mctx, sizeof(isc_radix_tree_t));
140
141 radix->mctx = NULL;
142 isc_mem_attach(mctx, &radix->mctx);
143 radix->maxbits = maxbits;
144 radix->head = NULL;
145 radix->num_active_node = 0;
146 radix->num_added_node = 0;
147 RUNTIME_CHECK(maxbits <= RADIX_MAXBITS); /* XXX */
148 radix->magic = RADIX_TREE_MAGIC;
149 *target = radix;
150 return (ISC_R_SUCCESS);
151 }
152
153 /*
154 * if func is supplied, it will be called as func(node->data)
155 * before deleting the node
156 */
157
158 static void
_clear_radix(isc_radix_tree_t * radix,isc_radix_destroyfunc_t func)159 _clear_radix(isc_radix_tree_t *radix, isc_radix_destroyfunc_t func) {
160 REQUIRE(radix != NULL);
161
162 if (radix->head != NULL) {
163 isc_radix_node_t *Xstack[RADIX_MAXBITS + 1];
164 isc_radix_node_t **Xsp = Xstack;
165 isc_radix_node_t *Xrn = radix->head;
166
167 while (Xrn != NULL) {
168 isc_radix_node_t *l = Xrn->l;
169 isc_radix_node_t *r = Xrn->r;
170
171 if (Xrn->prefix != NULL) {
172 _deref_prefix(Xrn->prefix);
173 if (func != NULL) {
174 func(Xrn->data);
175 }
176 } else {
177 INSIST(Xrn->data[RADIX_V4] == NULL &&
178 Xrn->data[RADIX_V6] == NULL);
179 }
180
181 isc_mem_put(radix->mctx, Xrn, sizeof(*Xrn));
182 radix->num_active_node--;
183
184 if (l != NULL) {
185 if (r != NULL) {
186 *Xsp++ = r;
187 }
188 Xrn = l;
189 } else if (r != NULL) {
190 Xrn = r;
191 } else if (Xsp != Xstack) {
192 Xrn = *(--Xsp);
193 } else {
194 Xrn = NULL;
195 }
196 }
197 }
198 RUNTIME_CHECK(radix->num_active_node == 0);
199 }
200
201 void
isc_radix_destroy(isc_radix_tree_t * radix,isc_radix_destroyfunc_t func)202 isc_radix_destroy(isc_radix_tree_t *radix, isc_radix_destroyfunc_t func) {
203 REQUIRE(radix != NULL);
204 _clear_radix(radix, func);
205 isc_mem_putanddetach(&radix->mctx, radix, sizeof(*radix));
206 }
207
208 /*
209 * func will be called as func(node->prefix, node->data)
210 */
211 void
isc_radix_process(isc_radix_tree_t * radix,isc_radix_processfunc_t func)212 isc_radix_process(isc_radix_tree_t *radix, isc_radix_processfunc_t func) {
213 isc_radix_node_t *node;
214
215 REQUIRE(func != NULL);
216
217 RADIX_WALK(radix->head, node) { func(node->prefix, node->data); }
218 RADIX_WALK_END;
219 }
220
221 isc_result_t
isc_radix_search(isc_radix_tree_t * radix,isc_radix_node_t ** target,isc_prefix_t * prefix)222 isc_radix_search(isc_radix_tree_t *radix, isc_radix_node_t **target,
223 isc_prefix_t *prefix) {
224 isc_radix_node_t *node;
225 isc_radix_node_t *stack[RADIX_MAXBITS + 1];
226 u_char *addr;
227 uint32_t bitlen;
228 int tfam = -1, cnt = 0;
229
230 REQUIRE(radix != NULL);
231 REQUIRE(prefix != NULL);
232 REQUIRE(target != NULL && *target == NULL);
233 RUNTIME_CHECK(prefix->bitlen <= radix->maxbits);
234
235 *target = NULL;
236
237 node = radix->head;
238
239 if (node == NULL) {
240 return (ISC_R_NOTFOUND);
241 }
242
243 addr = isc_prefix_touchar(prefix);
244 bitlen = prefix->bitlen;
245
246 while (node != NULL && node->bit < bitlen) {
247 if (node->prefix) {
248 stack[cnt++] = node;
249 }
250
251 if (BIT_TEST(addr[node->bit >> 3], 0x80 >> (node->bit & 0x07)))
252 {
253 node = node->r;
254 } else {
255 node = node->l;
256 }
257 }
258
259 if (node != NULL && node->prefix) {
260 stack[cnt++] = node;
261 }
262
263 while (cnt-- > 0) {
264 node = stack[cnt];
265
266 if (prefix->bitlen < node->bit) {
267 continue;
268 }
269
270 if (_comp_with_mask(isc_prefix_tochar(node->prefix),
271 isc_prefix_tochar(prefix),
272 node->prefix->bitlen))
273 {
274 int fam = ISC_RADIX_FAMILY(prefix);
275 if (node->node_num[fam] != -1 &&
276 ((*target == NULL) ||
277 (*target)->node_num[tfam] > node->node_num[fam]))
278 {
279 *target = node;
280 tfam = fam;
281 }
282 }
283 }
284
285 if (*target == NULL) {
286 return (ISC_R_NOTFOUND);
287 } else {
288 return (ISC_R_SUCCESS);
289 }
290 }
291
292 isc_result_t
isc_radix_insert(isc_radix_tree_t * radix,isc_radix_node_t ** target,isc_radix_node_t * source,isc_prefix_t * prefix)293 isc_radix_insert(isc_radix_tree_t *radix, isc_radix_node_t **target,
294 isc_radix_node_t *source, isc_prefix_t *prefix) {
295 isc_radix_node_t *node, *new_node, *parent, *glue = NULL;
296 u_char *addr, *test_addr;
297 uint32_t bitlen, fam, check_bit, differ_bit;
298 uint32_t i, j, r;
299 isc_result_t result;
300
301 REQUIRE(radix != NULL);
302 REQUIRE(target != NULL && *target == NULL);
303 REQUIRE(prefix != NULL || (source != NULL && source->prefix != NULL));
304 RUNTIME_CHECK(prefix == NULL || prefix->bitlen <= radix->maxbits);
305
306 if (prefix == NULL) {
307 prefix = source->prefix;
308 }
309
310 INSIST(prefix != NULL);
311
312 bitlen = prefix->bitlen;
313 fam = prefix->family;
314
315 if (radix->head == NULL) {
316 node = isc_mem_get(radix->mctx, sizeof(isc_radix_node_t));
317 node->bit = bitlen;
318 for (i = 0; i < RADIX_FAMILIES; i++) {
319 node->node_num[i] = -1;
320 }
321 node->prefix = NULL;
322 result = _ref_prefix(radix->mctx, &node->prefix, prefix);
323 if (result != ISC_R_SUCCESS) {
324 isc_mem_put(radix->mctx, node,
325 sizeof(isc_radix_node_t));
326 return (result);
327 }
328 node->parent = NULL;
329 node->l = node->r = NULL;
330 if (source != NULL) {
331 /*
332 * If source is non-NULL, then we're merging in a
333 * node from an existing radix tree. To keep
334 * the node_num values consistent, the calling
335 * function will add the total number of nodes
336 * added to num_added_node at the end of
337 * the merge operation--we don't do it here.
338 */
339 for (i = 0; i < RADIX_FAMILIES; i++) {
340 if (source->node_num[i] != -1) {
341 node->node_num[i] =
342 radix->num_added_node +
343 source->node_num[i];
344 }
345 node->data[i] = source->data[i];
346 }
347 } else {
348 int next = ++radix->num_added_node;
349 if (fam == AF_UNSPEC) {
350 /* "any" or "none" */
351 for (i = 0; i < RADIX_FAMILIES; i++) {
352 node->node_num[i] = next;
353 }
354 } else {
355 node->node_num[ISC_RADIX_FAMILY(prefix)] = next;
356 }
357
358 memset(node->data, 0, sizeof(node->data));
359 }
360 radix->head = node;
361 radix->num_active_node++;
362 *target = node;
363 return (ISC_R_SUCCESS);
364 }
365
366 addr = isc_prefix_touchar(prefix);
367 node = radix->head;
368
369 while (node->bit < bitlen || node->prefix == NULL) {
370 if (node->bit < radix->maxbits &&
371 BIT_TEST(addr[node->bit >> 3], 0x80 >> (node->bit & 0x07)))
372 {
373 if (node->r == NULL) {
374 break;
375 }
376 node = node->r;
377 } else {
378 if (node->l == NULL) {
379 break;
380 }
381 node = node->l;
382 }
383
384 INSIST(node != NULL);
385 }
386
387 INSIST(node->prefix != NULL);
388
389 test_addr = isc_prefix_touchar(node->prefix);
390 /* Find the first bit different. */
391 check_bit = (node->bit < bitlen) ? node->bit : bitlen;
392 differ_bit = 0;
393 for (i = 0; i * 8 < check_bit; i++) {
394 if ((r = (addr[i] ^ test_addr[i])) == 0) {
395 differ_bit = (i + 1) * 8;
396 continue;
397 }
398 /* I know the better way, but for now. */
399 for (j = 0; j < 8; j++) {
400 if (BIT_TEST(r, (0x80 >> j))) {
401 break;
402 }
403 }
404 /* Must be found. */
405 INSIST(j < 8);
406 differ_bit = i * 8 + j;
407 break;
408 }
409
410 if (differ_bit > check_bit) {
411 differ_bit = check_bit;
412 }
413
414 parent = node->parent;
415 while (parent != NULL && parent->bit >= differ_bit) {
416 node = parent;
417 parent = node->parent;
418 }
419
420 if (differ_bit == bitlen && node->bit == bitlen) {
421 if (node->prefix != NULL) {
422 /* Set node_num only if it hasn't been set before */
423 if (source != NULL) {
424 /* Merging nodes */
425 for (i = 0; i < RADIX_FAMILIES; i++) {
426 if (node->node_num[i] == -1 &&
427 source->node_num[i] != -1) {
428 node->node_num[i] =
429 radix->num_added_node +
430 source->node_num[i];
431 node->data[i] = source->data[i];
432 }
433 }
434 } else {
435 if (fam == AF_UNSPEC) {
436 /* "any" or "none" */
437 int next = radix->num_added_node + 1;
438 for (i = 0; i < RADIX_FAMILIES; i++) {
439 if (node->node_num[i] == -1) {
440 node->node_num[i] =
441 next;
442 radix->num_added_node =
443 next;
444 }
445 }
446 } else {
447 int foff = ISC_RADIX_FAMILY(prefix);
448 if (node->node_num[foff] == -1) {
449 node->node_num[foff] =
450 ++radix->num_added_node;
451 }
452 }
453 }
454 *target = node;
455 return (ISC_R_SUCCESS);
456 } else {
457 result = _ref_prefix(radix->mctx, &node->prefix,
458 prefix);
459 if (result != ISC_R_SUCCESS) {
460 return (result);
461 }
462 }
463 INSIST(node->data[RADIX_V4] == NULL &&
464 node->node_num[RADIX_V4] == -1 &&
465 node->data[RADIX_V4] == NULL &&
466 node->node_num[RADIX_V4] == -1);
467 if (source != NULL) {
468 /* Merging node */
469 for (i = 0; i < RADIX_FAMILIES; i++) {
470 int cur = radix->num_added_node;
471 if (source->node_num[i] != -1) {
472 node->node_num[i] =
473 source->node_num[i] + cur;
474 node->data[i] = source->data[i];
475 }
476 }
477 } else {
478 int next = ++radix->num_added_node;
479 if (fam == AF_UNSPEC) {
480 /* "any" or "none" */
481 for (i = 0; i < RADIX_FAMILIES; i++) {
482 node->node_num[i] = next;
483 }
484 } else {
485 node->node_num[ISC_RADIX_FAMILY(prefix)] = next;
486 }
487 }
488 *target = node;
489 return (ISC_R_SUCCESS);
490 }
491
492 new_node = isc_mem_get(radix->mctx, sizeof(isc_radix_node_t));
493 if (node->bit != differ_bit && bitlen != differ_bit) {
494 glue = isc_mem_get(radix->mctx, sizeof(isc_radix_node_t));
495 }
496 new_node->bit = bitlen;
497 new_node->prefix = NULL;
498 result = _ref_prefix(radix->mctx, &new_node->prefix, prefix);
499 if (result != ISC_R_SUCCESS) {
500 isc_mem_put(radix->mctx, new_node, sizeof(isc_radix_node_t));
501 if (glue != NULL) {
502 isc_mem_put(radix->mctx, glue,
503 sizeof(isc_radix_node_t));
504 }
505 return (result);
506 }
507 new_node->parent = NULL;
508 new_node->l = new_node->r = NULL;
509 for (i = 0; i < RADIX_FAMILIES; i++) {
510 new_node->node_num[i] = -1;
511 new_node->data[i] = NULL;
512 }
513 radix->num_active_node++;
514
515 if (source != NULL) {
516 /* Merging node */
517 for (i = 0; i < RADIX_FAMILIES; i++) {
518 int cur = radix->num_added_node;
519 if (source->node_num[i] != -1) {
520 new_node->node_num[i] = source->node_num[i] +
521 cur;
522 new_node->data[i] = source->data[i];
523 }
524 }
525 } else {
526 int next = ++radix->num_added_node;
527 if (fam == AF_UNSPEC) {
528 /* "any" or "none" */
529 for (i = 0; i < RADIX_FAMILIES; i++) {
530 new_node->node_num[i] = next;
531 }
532 } else {
533 new_node->node_num[ISC_RADIX_FAMILY(prefix)] = next;
534 }
535 memset(new_node->data, 0, sizeof(new_node->data));
536 }
537
538 if (node->bit == differ_bit) {
539 INSIST(glue == NULL);
540 new_node->parent = node;
541 if (node->bit < radix->maxbits &&
542 BIT_TEST(addr[node->bit >> 3], 0x80 >> (node->bit & 0x07)))
543 {
544 INSIST(node->r == NULL);
545 node->r = new_node;
546 } else {
547 INSIST(node->l == NULL);
548 node->l = new_node;
549 }
550 *target = new_node;
551 return (ISC_R_SUCCESS);
552 }
553
554 if (bitlen == differ_bit) {
555 INSIST(glue == NULL);
556 if (bitlen < radix->maxbits &&
557 BIT_TEST(test_addr[bitlen >> 3], 0x80 >> (bitlen & 0x07)))
558 {
559 new_node->r = node;
560 } else {
561 new_node->l = node;
562 }
563 new_node->parent = node->parent;
564 if (node->parent == NULL) {
565 INSIST(radix->head == node);
566 radix->head = new_node;
567 } else if (node->parent->r == node) {
568 node->parent->r = new_node;
569 } else {
570 node->parent->l = new_node;
571 }
572 node->parent = new_node;
573 } else {
574 INSIST(glue != NULL);
575 glue->bit = differ_bit;
576 glue->prefix = NULL;
577 glue->parent = node->parent;
578 for (i = 0; i < RADIX_FAMILIES; i++) {
579 glue->data[i] = NULL;
580 glue->node_num[i] = -1;
581 }
582 radix->num_active_node++;
583 if (differ_bit < radix->maxbits &&
584 BIT_TEST(addr[differ_bit >> 3], 0x80 >> (differ_bit & 07)))
585 {
586 glue->r = new_node;
587 glue->l = node;
588 } else {
589 glue->r = node;
590 glue->l = new_node;
591 }
592 new_node->parent = glue;
593
594 if (node->parent == NULL) {
595 INSIST(radix->head == node);
596 radix->head = glue;
597 } else if (node->parent->r == node) {
598 node->parent->r = glue;
599 } else {
600 node->parent->l = glue;
601 }
602 node->parent = glue;
603 }
604
605 *target = new_node;
606 return (ISC_R_SUCCESS);
607 }
608
609 void
isc_radix_remove(isc_radix_tree_t * radix,isc_radix_node_t * node)610 isc_radix_remove(isc_radix_tree_t *radix, isc_radix_node_t *node) {
611 isc_radix_node_t *parent, *child;
612
613 REQUIRE(radix != NULL);
614 REQUIRE(node != NULL);
615
616 if (node->r && node->l) {
617 /*
618 * This might be a placeholder node -- have to check and
619 * make sure there is a prefix associated with it!
620 */
621 if (node->prefix != NULL) {
622 _deref_prefix(node->prefix);
623 }
624
625 node->prefix = NULL;
626 memset(node->data, 0, sizeof(node->data));
627 return;
628 }
629
630 if (node->r == NULL && node->l == NULL) {
631 parent = node->parent;
632 _deref_prefix(node->prefix);
633
634 if (parent == NULL) {
635 INSIST(radix->head == node);
636 radix->head = NULL;
637 isc_mem_put(radix->mctx, node, sizeof(*node));
638 radix->num_active_node--;
639 return;
640 }
641
642 if (parent->r == node) {
643 parent->r = NULL;
644 child = parent->l;
645 } else {
646 INSIST(parent->l == node);
647 parent->l = NULL;
648 child = parent->r;
649 }
650
651 isc_mem_put(radix->mctx, node, sizeof(*node));
652 radix->num_active_node--;
653
654 if (parent->prefix) {
655 return;
656 }
657
658 /* We need to remove parent too. */
659 if (parent->parent == NULL) {
660 INSIST(radix->head == parent);
661 radix->head = child;
662 } else if (parent->parent->r == parent) {
663 parent->parent->r = child;
664 } else {
665 INSIST(parent->parent->l == parent);
666 parent->parent->l = child;
667 }
668
669 child->parent = parent->parent;
670 isc_mem_put(radix->mctx, parent, sizeof(*parent));
671 radix->num_active_node--;
672 return;
673 }
674
675 if (node->r) {
676 child = node->r;
677 } else {
678 INSIST(node->l != NULL);
679 child = node->l;
680 }
681
682 parent = node->parent;
683 child->parent = parent;
684
685 _deref_prefix(node->prefix);
686
687 if (parent == NULL) {
688 INSIST(radix->head == node);
689 radix->head = child;
690 isc_mem_put(radix->mctx, node, sizeof(*node));
691 radix->num_active_node--;
692 return;
693 }
694
695 isc_mem_put(radix->mctx, node, sizeof(*node));
696 radix->num_active_node--;
697
698 if (parent->r == node) {
699 parent->r = child;
700 } else {
701 INSIST(parent->l == node);
702 parent->l = child;
703 }
704 }
705