1 /* $NetBSD: nametree.c,v 1.2 2025/01/26 16:25:23 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 /*! \file */ 17 18 #include <stdbool.h> 19 20 #include <isc/mem.h> 21 #include <isc/refcount.h> 22 #include <isc/result.h> 23 #include <isc/string.h> 24 #include <isc/urcu.h> 25 #include <isc/util.h> 26 27 #include <dns/fixedname.h> 28 #include <dns/nametree.h> 29 #include <dns/qp.h> 30 31 #define NAMETREE_MAGIC ISC_MAGIC('N', 'T', 'r', 'e') 32 #define VALID_NAMETREE(kt) ISC_MAGIC_VALID(kt, NAMETREE_MAGIC) 33 34 struct dns_nametree { 35 unsigned int magic; 36 isc_mem_t *mctx; 37 isc_refcount_t references; 38 dns_nametree_type_t type; 39 dns_qpmulti_t *table; 40 char name[64]; 41 }; 42 43 struct dns_ntnode { 44 isc_mem_t *mctx; 45 isc_refcount_t references; 46 dns_name_t name; 47 bool set; 48 uint8_t *bits; 49 }; 50 51 /* QP trie methods */ 52 static void 53 qp_attach(void *uctx, void *pval, uint32_t ival); 54 static void 55 qp_detach(void *uctx, void *pval, uint32_t ival); 56 static size_t 57 qp_makekey(dns_qpkey_t key, void *uctx, void *pval, uint32_t ival); 58 static void 59 qp_triename(void *uctx, char *buf, size_t size); 60 61 static dns_qpmethods_t qpmethods = { 62 qp_attach, 63 qp_detach, 64 qp_makekey, 65 qp_triename, 66 }; 67 68 static void 69 destroy_ntnode(dns_ntnode_t *node) { 70 if (node->bits != NULL) { 71 isc_mem_cput(node->mctx, node->bits, node->bits[0], 72 sizeof(char)); 73 } 74 dns_name_free(&node->name, node->mctx); 75 isc_mem_putanddetach(&node->mctx, node, sizeof(dns_ntnode_t)); 76 } 77 78 #if DNS_NAMETREE_TRACE 79 ISC_REFCOUNT_TRACE_IMPL(dns_ntnode, destroy_ntnode); 80 #else 81 ISC_REFCOUNT_IMPL(dns_ntnode, destroy_ntnode); 82 #endif 83 84 void 85 dns_nametree_create(isc_mem_t *mctx, dns_nametree_type_t type, const char *name, 86 dns_nametree_t **ntp) { 87 dns_nametree_t *nametree = NULL; 88 89 REQUIRE(ntp != NULL && *ntp == NULL); 90 91 nametree = isc_mem_get(mctx, sizeof(*nametree)); 92 *nametree = (dns_nametree_t){ 93 .magic = NAMETREE_MAGIC, 94 .type = type, 95 }; 96 isc_mem_attach(mctx, &nametree->mctx); 97 isc_refcount_init(&nametree->references, 1); 98 99 if (name != NULL) { 100 strlcpy(nametree->name, name, sizeof(nametree->name)); 101 } 102 103 dns_qpmulti_create(mctx, &qpmethods, nametree, &nametree->table); 104 *ntp = nametree; 105 } 106 107 static void 108 destroy_nametree(dns_nametree_t *nametree) { 109 nametree->magic = 0; 110 111 dns_qpmulti_destroy(&nametree->table); 112 113 isc_mem_putanddetach(&nametree->mctx, nametree, sizeof(*nametree)); 114 } 115 116 #if DNS_NAMETREE_TRACE 117 ISC_REFCOUNT_TRACE_IMPL(dns_nametree, destroy_nametree); 118 #else 119 ISC_REFCOUNT_IMPL(dns_nametree, destroy_nametree); 120 #endif 121 122 static dns_ntnode_t * 123 newnode(isc_mem_t *mctx, const dns_name_t *name) { 124 dns_ntnode_t *node = isc_mem_get(mctx, sizeof(*node)); 125 *node = (dns_ntnode_t){ 126 .name = DNS_NAME_INITEMPTY, 127 }; 128 isc_mem_attach(mctx, &node->mctx); 129 isc_refcount_init(&node->references, 1); 130 131 dns_name_dupwithoffsets(name, mctx, &node->name); 132 133 return node; 134 } 135 136 static bool 137 matchbit(unsigned char *bits, uint32_t val) { 138 unsigned int len = val / 8 + 2; 139 unsigned int mask = 1 << (val % 8); 140 141 if (len <= bits[0] && (bits[len - 1] & mask) != 0) { 142 return true; 143 } 144 return false; 145 } 146 147 isc_result_t 148 dns_nametree_add(dns_nametree_t *nametree, const dns_name_t *name, 149 uint32_t value) { 150 isc_result_t result; 151 dns_qp_t *qp = NULL; 152 uint32_t size, pos, mask, count = 0; 153 dns_ntnode_t *old = NULL, *new = NULL; 154 155 REQUIRE(VALID_NAMETREE(nametree)); 156 REQUIRE(name != NULL); 157 158 dns_qpmulti_write(nametree->table, &qp); 159 160 switch (nametree->type) { 161 case DNS_NAMETREE_BOOL: 162 new = newnode(nametree->mctx, name); 163 new->set = value; 164 break; 165 166 case DNS_NAMETREE_COUNT: 167 new = newnode(nametree->mctx, name); 168 new->set = true; 169 result = dns_qp_deletename(qp, name, (void **)&old, &count); 170 if (result == ISC_R_SUCCESS) { 171 count += 1; 172 } 173 break; 174 175 case DNS_NAMETREE_BITS: 176 result = dns_qp_getname(qp, name, (void **)&old, NULL); 177 if (result == ISC_R_SUCCESS && matchbit(old->bits, value)) { 178 goto out; 179 } 180 181 size = pos = value / 8 + 2; 182 mask = 1 << (value % 8); 183 184 if (old != NULL && old->bits[0] > pos) { 185 size = old->bits[0]; 186 } 187 188 new = newnode(nametree->mctx, name); 189 new->bits = isc_mem_cget(nametree->mctx, size, sizeof(char)); 190 if (result == ISC_R_SUCCESS) { 191 memmove(new->bits, old->bits, old->bits[0]); 192 result = dns_qp_deletename(qp, name, NULL, NULL); 193 INSIST(result == ISC_R_SUCCESS); 194 } 195 196 new->bits[pos - 1] |= mask; 197 new->bits[0] = size; 198 break; 199 default: 200 UNREACHABLE(); 201 } 202 203 result = dns_qp_insert(qp, new, count); 204 /* 205 * We detach the node here, so any dns_qp_deletename() will 206 * destroy the node directly. 207 */ 208 dns_ntnode_detach(&new); 209 210 out: 211 dns_qp_compact(qp, DNS_QPGC_MAYBE); 212 dns_qpmulti_commit(nametree->table, &qp); 213 return result; 214 } 215 216 isc_result_t 217 dns_nametree_delete(dns_nametree_t *nametree, const dns_name_t *name) { 218 isc_result_t result; 219 dns_qp_t *qp = NULL; 220 dns_ntnode_t *old = NULL; 221 uint32_t count; 222 223 REQUIRE(VALID_NAMETREE(nametree)); 224 REQUIRE(name != NULL); 225 226 dns_qpmulti_write(nametree->table, &qp); 227 result = dns_qp_deletename(qp, name, (void **)&old, &count); 228 switch (nametree->type) { 229 case DNS_NAMETREE_BOOL: 230 case DNS_NAMETREE_BITS: 231 break; 232 233 case DNS_NAMETREE_COUNT: 234 if (result == ISC_R_SUCCESS && count-- != 0) { 235 dns_ntnode_t *new = newnode(nametree->mctx, name); 236 new->set = true; 237 result = dns_qp_insert(qp, new, count); 238 INSIST(result == ISC_R_SUCCESS); 239 dns_ntnode_detach(&new); 240 } 241 break; 242 default: 243 UNREACHABLE(); 244 } 245 dns_qp_compact(qp, DNS_QPGC_MAYBE); 246 dns_qpmulti_commit(nametree->table, &qp); 247 248 return result; 249 } 250 251 isc_result_t 252 dns_nametree_find(dns_nametree_t *nametree, const dns_name_t *name, 253 dns_ntnode_t **ntnodep) { 254 isc_result_t result; 255 dns_ntnode_t *node = NULL; 256 dns_qpread_t qpr; 257 258 REQUIRE(VALID_NAMETREE(nametree)); 259 REQUIRE(name != NULL); 260 REQUIRE(ntnodep != NULL && *ntnodep == NULL); 261 262 dns_qpmulti_query(nametree->table, &qpr); 263 result = dns_qp_getname(&qpr, name, (void **)&node, NULL); 264 if (result == ISC_R_SUCCESS) { 265 dns_ntnode_attach(node, ntnodep); 266 } 267 dns_qpread_destroy(nametree->table, &qpr); 268 269 return result; 270 } 271 272 bool 273 dns_nametree_covered(dns_nametree_t *nametree, const dns_name_t *name, 274 dns_name_t *found, uint32_t bit) { 275 isc_result_t result; 276 dns_qpread_t qpr; 277 dns_ntnode_t *node = NULL; 278 bool ret = false; 279 280 REQUIRE(VALID_NAMETREE(nametree)); 281 282 dns_qpmulti_query(nametree->table, &qpr); 283 result = dns_qp_lookup(&qpr, name, NULL, NULL, NULL, (void **)&node, 284 NULL); 285 if (result == ISC_R_SUCCESS || result == DNS_R_PARTIALMATCH) { 286 if (found != NULL) { 287 dns_name_copy(&node->name, found); 288 } 289 switch (nametree->type) { 290 case DNS_NAMETREE_BOOL: 291 ret = node->set; 292 break; 293 case DNS_NAMETREE_COUNT: 294 ret = true; 295 break; 296 case DNS_NAMETREE_BITS: 297 ret = matchbit(node->bits, bit); 298 break; 299 } 300 } 301 302 dns_qpread_destroy(nametree->table, &qpr); 303 return ret; 304 } 305 306 static void 307 qp_attach(void *uctx ISC_ATTR_UNUSED, void *pval, 308 uint32_t ival ISC_ATTR_UNUSED) { 309 dns_ntnode_t *ntnode = pval; 310 dns_ntnode_ref(ntnode); 311 } 312 313 static void 314 qp_detach(void *uctx ISC_ATTR_UNUSED, void *pval, 315 uint32_t ival ISC_ATTR_UNUSED) { 316 dns_ntnode_t *ntnode = pval; 317 dns_ntnode_detach(&ntnode); 318 } 319 320 static size_t 321 qp_makekey(dns_qpkey_t key, void *uctx ISC_ATTR_UNUSED, void *pval, 322 uint32_t ival ISC_ATTR_UNUSED) { 323 dns_ntnode_t *ntnode = pval; 324 return dns_qpkey_fromname(key, &ntnode->name); 325 } 326 327 static void 328 qp_triename(void *uctx, char *buf, size_t size) { 329 dns_nametree_t *nametree = uctx; 330 snprintf(buf, size, "%s nametree", nametree->name); 331 } 332