1 /* $NetBSD: radix.h,v 1.8 2022/09/23 12:15:33 christos Exp $ */ 2 3 /* 4 * Copyright (C) Internet Systems Consortium, Inc. ("ISC") 5 * 6 * SPDX-License-Identifier: MPL-2.0 7 * 8 * This Source Code Form is subject to the terms of the Mozilla Public 9 * License, v. 2.0. If a copy of the MPL was not distributed with this 10 * file, you can obtain one at https://mozilla.org/MPL/2.0/. 11 * 12 * See the COPYRIGHT file distributed with this work for additional 13 * information regarding copyright ownership. 14 */ 15 16 #ifndef _RADIX_H 17 #define _RADIX_H 18 19 #include <inttypes.h> 20 #include <string.h> 21 22 #include <isc/magic.h> 23 #include <isc/mutex.h> 24 #include <isc/net.h> 25 #include <isc/refcount.h> 26 #include <isc/types.h> 27 28 #define NETADDR_TO_PREFIX_T(na, pt, bits) \ 29 do { \ 30 const void *p = na; \ 31 memset(&(pt), 0, sizeof(pt)); \ 32 if (p != NULL) { \ 33 (pt).family = (na)->family; \ 34 (pt).bitlen = (bits); \ 35 if ((pt).family == AF_INET6) { \ 36 memmove(&(pt).add.sin6, &(na)->type.in6, \ 37 ((bits) + 7) / 8); \ 38 } else \ 39 memmove(&(pt).add.sin, &(na)->type.in, \ 40 ((bits) + 7) / 8); \ 41 } else { \ 42 (pt).family = AF_UNSPEC; \ 43 (pt).bitlen = 0; \ 44 } \ 45 isc_refcount_init(&(pt).refcount, 0); \ 46 } while (0) 47 48 typedef struct isc_prefix { 49 isc_mem_t *mctx; 50 unsigned int family; /* AF_INET | AF_INET6, or AF_UNSPEC for 51 * "any" */ 52 unsigned int bitlen; /* 0 for "any" */ 53 isc_refcount_t refcount; 54 union { 55 struct in_addr sin; 56 struct in6_addr sin6; 57 } add; 58 } isc_prefix_t; 59 60 typedef void (*isc_radix_destroyfunc_t)(void *); 61 typedef void (*isc_radix_processfunc_t)(isc_prefix_t *, void **); 62 63 #define isc_prefix_tochar(prefix) ((char *)&(prefix)->add.sin) 64 #define isc_prefix_touchar(prefix) ((u_char *)&(prefix)->add.sin) 65 66 /* 67 * We need "first match" when we search the radix tree to preserve 68 * compatibility with the existing ACL implementation. Radix trees 69 * naturally lend themselves to "best match". In order to get "first match" 70 * behavior, we keep track of the order in which entries are added to the 71 * tree--and when a search is made, we find all matching entries, and 72 * return the one that was added first. 73 * 74 * An IPv4 prefix and an IPv6 prefix may share a radix tree node if they 75 * have the same length and bit pattern (e.g., 127/8 and 7f::/8). To 76 * disambiguate between them, node_num and data are two-element arrays: 77 * 78 * - node_num[0] and data[0] are used for IPv4 client addresses 79 * - node_num[1] and data[1] are used for IPv6 client addresses 80 * 81 * A prefix of 0/0 (aka "any" or "none"), is always stored as IPv4, 82 * but matches all IPv6 addresses too. 83 */ 84 85 #define RADIX_V4 0 86 #define RADIX_V6 1 87 #define RADIX_FAMILIES 2 88 89 #define ISC_RADIX_FAMILY(p) (((p)->family == AF_INET6) ? RADIX_V6 : RADIX_V4) 90 91 typedef struct isc_radix_node { 92 isc_mem_t *mctx; 93 uint32_t bit; /* bit length of the prefix */ 94 isc_prefix_t *prefix; /* who we are in radix tree */ 95 struct isc_radix_node *l, *r; /* left and right children */ 96 struct isc_radix_node *parent; /* may be used */ 97 void *data[RADIX_FAMILIES]; /* pointers to IPv4 98 * and IPV6 data */ 99 int node_num[RADIX_FAMILIES]; /* which node 100 * this was in 101 * the tree, 102 * or -1 for glue 103 * nodes */ 104 } isc_radix_node_t; 105 106 #define RADIX_TREE_MAGIC ISC_MAGIC('R', 'd', 'x', 'T'); 107 #define RADIX_TREE_VALID(a) ISC_MAGIC_VALID(a, RADIX_TREE_MAGIC); 108 109 typedef struct isc_radix_tree { 110 unsigned int magic; 111 isc_mem_t *mctx; 112 isc_radix_node_t *head; 113 uint32_t maxbits; /* for IP, 32 bit addresses */ 114 int num_active_node; /* for debugging purposes */ 115 int num_added_node; /* total number of nodes */ 116 } isc_radix_tree_t; 117 118 isc_result_t 119 isc_radix_search(isc_radix_tree_t *radix, isc_radix_node_t **target, 120 isc_prefix_t *prefix); 121 /*%< 122 * Search 'radix' for the best match to 'prefix'. 123 * Return the node found in '*target'. 124 * 125 * Requires: 126 * \li 'radix' to be valid. 127 * \li 'target' is not NULL and "*target" is NULL. 128 * \li 'prefix' to be valid. 129 * 130 * Returns: 131 * \li ISC_R_NOTFOUND 132 * \li ISC_R_SUCCESS 133 */ 134 135 isc_result_t 136 isc_radix_insert(isc_radix_tree_t *radix, isc_radix_node_t **target, 137 isc_radix_node_t *source, isc_prefix_t *prefix); 138 /*%< 139 * Insert 'source' or 'prefix' into the radix tree 'radix'. 140 * Return the node added in 'target'. 141 * 142 * Requires: 143 * \li 'radix' to be valid. 144 * \li 'target' is not NULL and "*target" is NULL. 145 * \li 'prefix' to be valid or 'source' to be non NULL and contain 146 * a valid prefix. 147 * 148 * Returns: 149 * \li ISC_R_NOMEMORY 150 * \li ISC_R_SUCCESS 151 */ 152 153 void 154 isc_radix_remove(isc_radix_tree_t *radix, isc_radix_node_t *node); 155 /*%< 156 * Remove the node 'node' from the radix tree 'radix'. 157 * 158 * Requires: 159 * \li 'radix' to be valid. 160 * \li 'node' to be valid. 161 */ 162 163 isc_result_t 164 isc_radix_create(isc_mem_t *mctx, isc_radix_tree_t **target, int maxbits); 165 /*%< 166 * Create a radix tree with a maximum depth of 'maxbits'; 167 * 168 * Requires: 169 * \li 'mctx' to be valid. 170 * \li 'target' to be non NULL and '*target' to be NULL. 171 * \li 'maxbits' to be less than or equal to RADIX_MAXBITS. 172 * 173 * Returns: 174 * \li ISC_R_NOMEMORY 175 * \li ISC_R_SUCCESS 176 */ 177 178 void 179 isc_radix_destroy(isc_radix_tree_t *radix, isc_radix_destroyfunc_t func); 180 /*%< 181 * Destroy a radix tree optionally calling 'func' to clean up node data. 182 * 183 * Requires: 184 * \li 'radix' to be valid. 185 */ 186 187 void 188 isc_radix_process(isc_radix_tree_t *radix, isc_radix_processfunc_t func); 189 /*%< 190 * Walk a radix tree calling 'func' to process node data. 191 * 192 * Requires: 193 * \li 'radix' to be valid. 194 * \li 'func' to point to a function. 195 */ 196 197 #define RADIX_MAXBITS 128 198 #define RADIX_NBIT(x) (0x80 >> ((x)&0x7f)) 199 #define RADIX_NBYTE(x) ((x) >> 3) 200 201 #define RADIX_WALK(Xhead, Xnode) \ 202 do { \ 203 isc_radix_node_t *Xstack[RADIX_MAXBITS + 1]; \ 204 isc_radix_node_t **Xsp = Xstack; \ 205 isc_radix_node_t *Xrn = (Xhead); \ 206 while ((Xnode = Xrn)) { \ 207 if (Xnode->prefix) 208 209 #define RADIX_WALK_END \ 210 if (Xrn->l) { \ 211 if (Xrn->r) { \ 212 *Xsp++ = Xrn->r; \ 213 } \ 214 Xrn = Xrn->l; \ 215 } else if (Xrn->r) { \ 216 Xrn = Xrn->r; \ 217 } else if (Xsp != Xstack) { \ 218 Xrn = *(--Xsp); \ 219 } else { \ 220 Xrn = (isc_radix_node_t *)0; \ 221 } \ 222 } \ 223 } \ 224 while (0) 225 226 #endif /* _RADIX_H */ 227