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