1 /* $NetBSD: badcache.c,v 1.9 2025/01/26 16:25:21 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 <inttypes.h> 19 #include <stdbool.h> 20 21 #include <isc/async.h> 22 #include <isc/buffer.h> 23 #include <isc/hash.h> 24 #include <isc/log.h> 25 #include <isc/loop.h> 26 #include <isc/mem.h> 27 #include <isc/mutex.h> 28 #include <isc/rwlock.h> 29 #include <isc/spinlock.h> 30 #include <isc/stdtime.h> 31 #include <isc/string.h> 32 #include <isc/thread.h> 33 #include <isc/time.h> 34 #include <isc/urcu.h> 35 #include <isc/util.h> 36 37 #include <dns/badcache.h> 38 #include <dns/fixedname.h> 39 #include <dns/name.h> 40 #include <dns/rdatatype.h> 41 #include <dns/types.h> 42 43 typedef struct dns_bcentry dns_bcentry_t; 44 45 typedef struct dns_bckey { 46 const dns_name_t *name; 47 dns_rdatatype_t type; 48 } dns__bckey_t; 49 50 struct dns_badcache { 51 unsigned int magic; 52 isc_mem_t *mctx; 53 struct cds_lfht *ht; 54 struct cds_list_head *lru; 55 uint32_t nloops; 56 }; 57 58 #define BADCACHE_MAGIC ISC_MAGIC('B', 'd', 'C', 'a') 59 #define VALID_BADCACHE(m) ISC_MAGIC_VALID(m, BADCACHE_MAGIC) 60 61 #define BADCACHE_INIT_SIZE (1 << 10) /* Must be power of 2 */ 62 #define BADCACHE_MIN_SIZE (1 << 8) /* Must be power of 2 */ 63 64 struct dns_bcentry { 65 isc_loop_t *loop; 66 isc_stdtime_t expire; 67 uint32_t flags; 68 69 struct cds_lfht_node ht_node; 70 struct rcu_head rcu_head; 71 struct cds_list_head lru_head; 72 73 dns_name_t name; 74 dns_rdatatype_t type; 75 }; 76 77 static void 78 bcentry_print(dns_bcentry_t *bad, isc_stdtime_t now, FILE *fp); 79 80 static void 81 bcentry_destroy(struct rcu_head *rcu_head); 82 83 static bool 84 bcentry_alive(struct cds_lfht *ht, dns_bcentry_t *bad, isc_stdtime_t now); 85 86 dns_badcache_t * 87 dns_badcache_new(isc_mem_t *mctx, isc_loopmgr_t *loopmgr) { 88 REQUIRE(loopmgr != NULL); 89 90 uint32_t nloops = isc_loopmgr_nloops(loopmgr); 91 dns_badcache_t *bc = isc_mem_get(mctx, sizeof(*bc)); 92 *bc = (dns_badcache_t){ 93 .magic = BADCACHE_MAGIC, 94 .nloops = nloops, 95 }; 96 97 bc->ht = cds_lfht_new(BADCACHE_INIT_SIZE, BADCACHE_MIN_SIZE, 0, 98 CDS_LFHT_AUTO_RESIZE | CDS_LFHT_ACCOUNTING, NULL); 99 INSIST(bc->ht != NULL); 100 101 bc->lru = isc_mem_cget(mctx, bc->nloops, sizeof(bc->lru[0])); 102 for (size_t i = 0; i < bc->nloops; i++) { 103 CDS_INIT_LIST_HEAD(&bc->lru[i]); 104 } 105 106 isc_mem_attach(mctx, &bc->mctx); 107 108 return bc; 109 } 110 111 void 112 dns_badcache_destroy(dns_badcache_t **bcp) { 113 REQUIRE(bcp != NULL && *bcp != NULL); 114 REQUIRE(VALID_BADCACHE(*bcp)); 115 116 dns_badcache_t *bc = *bcp; 117 *bcp = NULL; 118 bc->magic = 0; 119 120 dns_bcentry_t *bad = NULL; 121 struct cds_lfht_iter iter; 122 cds_lfht_for_each_entry(bc->ht, &iter, bad, ht_node) { 123 INSIST(!cds_lfht_del(bc->ht, &bad->ht_node)); 124 bcentry_destroy(&bad->rcu_head); 125 } 126 RUNTIME_CHECK(!cds_lfht_destroy(bc->ht, NULL)); 127 128 isc_mem_cput(bc->mctx, bc->lru, bc->nloops, sizeof(bc->lru[0])); 129 130 isc_mem_putanddetach(&bc->mctx, bc, sizeof(dns_badcache_t)); 131 } 132 133 static int 134 bcentry_match(struct cds_lfht_node *ht_node, const void *key0) { 135 const dns__bckey_t *key = key0; 136 dns_bcentry_t *bad = caa_container_of(ht_node, dns_bcentry_t, ht_node); 137 138 return (bad->type == key->type) && 139 dns_name_equal(&bad->name, key->name); 140 } 141 142 static uint32_t 143 bcentry_hash(const dns__bckey_t *key) { 144 isc_hash32_t state; 145 isc_hash32_init(&state); 146 isc_hash32_hash(&state, key->name->ndata, key->name->length, false); 147 isc_hash32_hash(&state, &key->type, sizeof(key->type), true); 148 return isc_hash32_finalize(&state); 149 } 150 151 static dns_bcentry_t * 152 bcentry_lookup(struct cds_lfht *ht, uint32_t hashval, dns__bckey_t *key) { 153 struct cds_lfht_iter iter; 154 155 cds_lfht_lookup(ht, hashval, bcentry_match, key, &iter); 156 157 return cds_lfht_entry(cds_lfht_iter_get_node(&iter), dns_bcentry_t, 158 ht_node); 159 } 160 161 static dns_bcentry_t * 162 bcentry_new(isc_loop_t *loop, const dns_name_t *name, 163 const dns_rdatatype_t type, const uint32_t flags, 164 const isc_stdtime_t expire) { 165 isc_mem_t *mctx = isc_loop_getmctx(loop); 166 dns_bcentry_t *bad = isc_mem_get(mctx, sizeof(*bad)); 167 *bad = (dns_bcentry_t){ 168 .type = type, 169 .flags = flags, 170 .expire = expire, 171 .loop = isc_loop_ref(loop), 172 .lru_head = CDS_LIST_HEAD_INIT(bad->lru_head), 173 }; 174 175 dns_name_init(&bad->name, NULL); 176 dns_name_dup(name, mctx, &bad->name); 177 178 return bad; 179 } 180 181 static void 182 bcentry_destroy(struct rcu_head *rcu_head) { 183 dns_bcentry_t *bad = caa_container_of(rcu_head, dns_bcentry_t, 184 rcu_head); 185 isc_loop_t *loop = bad->loop; 186 isc_mem_t *mctx = isc_loop_getmctx(loop); 187 188 dns_name_free(&bad->name, mctx); 189 isc_mem_put(mctx, bad, sizeof(*bad)); 190 191 isc_loop_unref(loop); 192 } 193 194 static void 195 bcentry_evict_async(void *arg) { 196 dns_bcentry_t *bad = arg; 197 198 RUNTIME_CHECK(bad->loop == isc_loop()); 199 200 cds_list_del(&bad->lru_head); 201 call_rcu(&bad->rcu_head, bcentry_destroy); 202 } 203 204 static void 205 bcentry_evict(struct cds_lfht *ht, dns_bcentry_t *bad) { 206 if (!cds_lfht_del(ht, &bad->ht_node)) { 207 if (bad->loop == isc_loop()) { 208 bcentry_evict_async(bad); 209 return; 210 } 211 212 isc_async_run(bad->loop, bcentry_evict_async, bad); 213 } 214 } 215 216 static bool 217 bcentry_alive(struct cds_lfht *ht, dns_bcentry_t *bad, isc_stdtime_t now) { 218 if (cds_lfht_is_node_deleted(&bad->ht_node)) { 219 return false; 220 } else if (bad->expire < now) { 221 bcentry_evict(ht, bad); 222 return false; 223 } 224 225 return true; 226 } 227 228 #define cds_lfht_for_each_entry_next(ht, iter, pos, member) \ 229 for (cds_lfht_next(ht, iter), \ 230 pos = cds_lfht_entry(cds_lfht_iter_get_node(iter), \ 231 __typeof__(*(pos)), member); \ 232 pos != NULL; /**/ \ 233 cds_lfht_next(ht, iter), \ 234 pos = cds_lfht_entry(cds_lfht_iter_get_node(iter), \ 235 __typeof__(*(pos)), member)) 236 237 static void 238 bcentry_purge(struct cds_lfht *ht, struct cds_list_head *lru, 239 isc_stdtime_t now) { 240 size_t count = 10; 241 dns_bcentry_t *bad; 242 cds_list_for_each_entry_rcu(bad, lru, lru_head) { 243 if (bcentry_alive(ht, bad, now)) { 244 break; 245 } 246 if (--count == 0) { 247 break; 248 } 249 } 250 } 251 252 void 253 dns_badcache_add(dns_badcache_t *bc, const dns_name_t *name, 254 dns_rdatatype_t type, uint32_t flags, isc_stdtime_t expire) { 255 REQUIRE(VALID_BADCACHE(bc)); 256 REQUIRE(name != NULL); 257 258 isc_loop_t *loop = isc_loop(); 259 uint32_t tid = isc_tid(); 260 struct cds_list_head *lru = &bc->lru[tid]; 261 262 isc_stdtime_t now = isc_stdtime_now(); 263 if (expire < now) { 264 expire = now; 265 } 266 267 rcu_read_lock(); 268 struct cds_lfht *ht = rcu_dereference(bc->ht); 269 INSIST(ht != NULL); 270 271 dns__bckey_t key = { 272 .name = name, 273 .type = type, 274 }; 275 uint32_t hashval = bcentry_hash(&key); 276 277 /* struct cds_lfht_iter iter; */ 278 dns_bcentry_t *bad = bcentry_new(loop, name, type, flags, expire); 279 struct cds_lfht_node *ht_node; 280 do { 281 ht_node = cds_lfht_add_unique(ht, hashval, bcentry_match, &key, 282 &bad->ht_node); 283 if (ht_node != &bad->ht_node) { 284 dns_bcentry_t *found = caa_container_of( 285 ht_node, dns_bcentry_t, ht_node); 286 bcentry_evict(ht, found); 287 } 288 } while (ht_node != &bad->ht_node); 289 290 /* No locking, instead we are using per-thread lists */ 291 cds_list_add_tail_rcu(&bad->lru_head, lru); 292 293 bcentry_purge(ht, lru, now); 294 295 rcu_read_unlock(); 296 } 297 298 isc_result_t 299 dns_badcache_find(dns_badcache_t *bc, const dns_name_t *name, 300 dns_rdatatype_t type, uint32_t *flagp, isc_stdtime_t now) { 301 REQUIRE(VALID_BADCACHE(bc)); 302 REQUIRE(name != NULL); 303 304 isc_result_t result = ISC_R_NOTFOUND; 305 306 rcu_read_lock(); 307 struct cds_lfht *ht = rcu_dereference(bc->ht); 308 INSIST(ht != NULL); 309 310 dns__bckey_t key = { 311 .name = name, 312 .type = type, 313 }; 314 uint32_t hashval = bcentry_hash(&key); 315 316 dns_bcentry_t *found = bcentry_lookup(ht, hashval, &key); 317 318 if (found != NULL && bcentry_alive(ht, found, now)) { 319 result = ISC_R_SUCCESS; 320 if (flagp != NULL) { 321 *flagp = found->flags; 322 } 323 } 324 325 uint32_t tid = isc_tid(); 326 struct cds_list_head *lru = &bc->lru[tid]; 327 bcentry_purge(ht, lru, now); 328 329 rcu_read_unlock(); 330 331 return result; 332 } 333 334 void 335 dns_badcache_flush(dns_badcache_t *bc) { 336 REQUIRE(VALID_BADCACHE(bc)); 337 338 rcu_read_lock(); 339 struct cds_lfht *ht = rcu_dereference(bc->ht); 340 INSIST(ht != NULL); 341 342 /* Flush the hash table */ 343 dns_bcentry_t *bad; 344 struct cds_lfht_iter iter; 345 cds_lfht_for_each_entry(ht, &iter, bad, ht_node) { 346 bcentry_evict(ht, bad); 347 } 348 349 rcu_read_unlock(); 350 } 351 352 void 353 dns_badcache_flushname(dns_badcache_t *bc, const dns_name_t *name) { 354 REQUIRE(VALID_BADCACHE(bc)); 355 REQUIRE(name != NULL); 356 357 isc_stdtime_t now = isc_stdtime_now(); 358 359 rcu_read_lock(); 360 struct cds_lfht *ht = rcu_dereference(bc->ht); 361 INSIST(ht != NULL); 362 363 dns_bcentry_t *bad; 364 struct cds_lfht_iter iter; 365 cds_lfht_for_each_entry(ht, &iter, bad, ht_node) { 366 if (dns_name_equal(&bad->name, name)) { 367 bcentry_evict(ht, bad); 368 continue; 369 } 370 371 /* Flush all the expired entries */ 372 (void)bcentry_alive(ht, bad, now); 373 } 374 375 rcu_read_unlock(); 376 } 377 378 void 379 dns_badcache_flushtree(dns_badcache_t *bc, const dns_name_t *name) { 380 REQUIRE(VALID_BADCACHE(bc)); 381 REQUIRE(name != NULL); 382 383 isc_stdtime_t now = isc_stdtime_now(); 384 385 rcu_read_lock(); 386 struct cds_lfht *ht = rcu_dereference(bc->ht); 387 INSIST(ht != NULL); 388 389 dns_bcentry_t *bad; 390 struct cds_lfht_iter iter; 391 cds_lfht_for_each_entry(ht, &iter, bad, ht_node) { 392 if (dns_name_issubdomain(&bad->name, name)) { 393 bcentry_evict(ht, bad); 394 continue; 395 } 396 397 /* Flush all the expired entries */ 398 (void)bcentry_alive(ht, bad, now); 399 } 400 401 rcu_read_unlock(); 402 } 403 404 static void 405 bcentry_print(dns_bcentry_t *bad, isc_stdtime_t now, FILE *fp) { 406 char namebuf[DNS_NAME_FORMATSIZE]; 407 char typebuf[DNS_RDATATYPE_FORMATSIZE]; 408 409 dns_name_format(&bad->name, namebuf, sizeof(namebuf)); 410 dns_rdatatype_format(bad->type, typebuf, sizeof(typebuf)); 411 fprintf(fp, "; %s/%s [ttl %" PRIu32 "]\n", namebuf, typebuf, 412 bad->expire - now); 413 } 414 415 void 416 dns_badcache_print(dns_badcache_t *bc, const char *cachename, FILE *fp) { 417 dns_bcentry_t *bad; 418 isc_stdtime_t now = isc_stdtime_now(); 419 420 REQUIRE(VALID_BADCACHE(bc)); 421 REQUIRE(fp != NULL); 422 423 fprintf(fp, ";\n; %s\n;\n", cachename); 424 425 rcu_read_lock(); 426 struct cds_lfht *ht = rcu_dereference(bc->ht); 427 INSIST(ht != NULL); 428 429 struct cds_lfht_iter iter; 430 cds_lfht_for_each_entry(ht, &iter, bad, ht_node) { 431 if (bcentry_alive(ht, bad, now)) { 432 bcentry_print(bad, now, fp); 433 } 434 } 435 436 rcu_read_unlock(); 437 } 438
Indexes created Sat Feb 28 05:31:39 UTC 2026