summaryrefslogtreecommitdiffstats
path: root/lib/dns/badcache.c
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--lib/dns/badcache.c440
1 files changed, 440 insertions, 0 deletions
diff --git a/lib/dns/badcache.c b/lib/dns/badcache.c
new file mode 100644
index 0000000..5c784be
--- /dev/null
+++ b/lib/dns/badcache.c
@@ -0,0 +1,440 @@
+/*
+ * Copyright (C) Internet Systems Consortium, Inc. ("ISC")
+ *
+ * This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/.
+ *
+ * See the COPYRIGHT file distributed with this work for additional
+ * information regarding copyright ownership.
+ */
+
+/*! \file */
+
+#include <config.h>
+
+#include <inttypes.h>
+#include <stdbool.h>
+
+#include <isc/buffer.h>
+#include <isc/log.h>
+#include <isc/hash.h>
+#include <isc/mem.h>
+#include <isc/mutex.h>
+#include <isc/platform.h>
+#include <isc/print.h>
+#include <isc/string.h>
+#include <isc/time.h>
+#include <isc/util.h>
+
+#include <dns/badcache.h>
+#include <dns/name.h>
+#include <dns/rdatatype.h>
+#include <dns/types.h>
+
+typedef struct dns_bcentry dns_bcentry_t;
+
+struct dns_badcache {
+ unsigned int magic;
+ isc_mutex_t lock;
+ isc_mem_t *mctx;
+
+ dns_bcentry_t **table;
+ unsigned int count;
+ unsigned int minsize;
+ unsigned int size;
+ unsigned int sweep;
+};
+
+#define BADCACHE_MAGIC ISC_MAGIC('B', 'd', 'C', 'a')
+#define VALID_BADCACHE(m) ISC_MAGIC_VALID(m, BADCACHE_MAGIC)
+
+struct dns_bcentry {
+ dns_bcentry_t * next;
+ dns_rdatatype_t type;
+ isc_time_t expire;
+ uint32_t flags;
+ unsigned int hashval;
+ dns_name_t name;
+};
+
+static isc_result_t
+badcache_resize(dns_badcache_t *bc, isc_time_t *now, bool grow);
+
+isc_result_t
+dns_badcache_init(isc_mem_t *mctx, unsigned int size, dns_badcache_t **bcp) {
+ isc_result_t result;
+ dns_badcache_t *bc = NULL;
+
+ REQUIRE(bcp != NULL && *bcp == NULL);
+ REQUIRE(mctx != NULL);
+
+ bc = isc_mem_get(mctx, sizeof(dns_badcache_t));
+ if (bc == NULL)
+ return (ISC_R_NOMEMORY);
+ memset(bc, 0, sizeof(dns_badcache_t));
+
+ isc_mem_attach(mctx, &bc->mctx);
+ result = isc_mutex_init(&bc->lock);
+ if (result != ISC_R_SUCCESS)
+ goto cleanup;
+
+ bc->table = isc_mem_get(bc->mctx, sizeof(*bc->table) * size);
+ if (bc->table == NULL) {
+ result = ISC_R_NOMEMORY;
+ goto destroy_lock;
+ }
+
+ bc->size = bc->minsize = size;
+ memset(bc->table, 0, bc->size * sizeof(dns_bcentry_t *));
+
+ bc->count = 0;
+ bc->sweep = 0;
+ bc->magic = BADCACHE_MAGIC;
+
+ *bcp = bc;
+ return (ISC_R_SUCCESS);
+
+ destroy_lock:
+ DESTROYLOCK(&bc->lock);
+ cleanup:
+ isc_mem_putanddetach(&bc->mctx, bc, sizeof(dns_badcache_t));
+ return (result);
+}
+
+void
+dns_badcache_destroy(dns_badcache_t **bcp) {
+ dns_badcache_t *bc;
+
+ REQUIRE(bcp != NULL && *bcp != NULL);
+ bc = *bcp;
+
+ dns_badcache_flush(bc);
+
+ bc->magic = 0;
+ DESTROYLOCK(&bc->lock);
+ isc_mem_put(bc->mctx, bc->table, sizeof(dns_bcentry_t *) * bc->size);
+ isc_mem_putanddetach(&bc->mctx, bc, sizeof(dns_badcache_t));
+ *bcp = NULL;
+}
+
+static isc_result_t
+badcache_resize(dns_badcache_t *bc, isc_time_t *now, bool grow) {
+ dns_bcentry_t **newtable, *bad, *next;
+ unsigned int newsize, i;
+
+ if (grow)
+ newsize = bc->size * 2 + 1;
+ else
+ newsize = (bc->size - 1) / 2;
+
+ newtable = isc_mem_get(bc->mctx, sizeof(dns_bcentry_t *) * newsize);
+ if (newtable == NULL)
+ return (ISC_R_NOMEMORY);
+ memset(newtable, 0, sizeof(dns_bcentry_t *) * newsize);
+
+ for (i = 0; bc->count > 0 && i < bc->size; i++) {
+ for (bad = bc->table[i]; bad != NULL; bad = next) {
+ next = bad->next;
+ if (isc_time_compare(&bad->expire, now) < 0) {
+ isc_mem_put(bc->mctx, bad,
+ sizeof(*bad) + bad->name.length);
+ bc->count--;
+ } else {
+ bad->next = newtable[bad->hashval % newsize];
+ newtable[bad->hashval % newsize] = bad;
+ }
+ }
+ bc->table[i] = NULL;
+ }
+
+ isc_mem_put(bc->mctx, bc->table, sizeof(*bc->table) * bc->size);
+ bc->size = newsize;
+ bc->table = newtable;
+
+ return (ISC_R_SUCCESS);
+}
+
+void
+dns_badcache_add(dns_badcache_t *bc, dns_name_t *name,
+ dns_rdatatype_t type, bool update,
+ uint32_t flags, isc_time_t *expire)
+{
+ isc_result_t result;
+ unsigned int i, hashval;
+ dns_bcentry_t *bad, *prev, *next;
+ isc_time_t now;
+
+ REQUIRE(VALID_BADCACHE(bc));
+ REQUIRE(name != NULL);
+ REQUIRE(expire != NULL);
+
+ LOCK(&bc->lock);
+
+ result = isc_time_now(&now);
+ if (result != ISC_R_SUCCESS)
+ isc_time_settoepoch(&now);
+
+ hashval = dns_name_hash(name, false);
+ i = hashval % bc->size;
+ prev = NULL;
+ for (bad = bc->table[i]; bad != NULL; bad = next) {
+ next = bad->next;
+ if (bad->type == type && dns_name_equal(name, &bad->name)) {
+ if (update) {
+ bad->expire = *expire;
+ bad->flags = flags;
+ }
+ break;
+ }
+ if (isc_time_compare(&bad->expire, &now) < 0) {
+ if (prev == NULL)
+ bc->table[i] = bad->next;
+ else
+ prev->next = bad->next;
+ isc_mem_put(bc->mctx, bad,
+ sizeof(*bad) + bad->name.length);
+ bc->count--;
+ } else
+ prev = bad;
+ }
+
+ if (bad == NULL) {
+ isc_buffer_t buffer;
+ bad = isc_mem_get(bc->mctx, sizeof(*bad) + name->length);
+ if (bad == NULL)
+ goto cleanup;
+ bad->type = type;
+ bad->hashval = hashval;
+ bad->expire = *expire;
+ bad->flags = flags;
+ isc_buffer_init(&buffer, bad + 1, name->length);
+ dns_name_init(&bad->name, NULL);
+ dns_name_copy(name, &bad->name, &buffer);
+ bad->next = bc->table[i];
+ bc->table[i] = bad;
+ bc->count++;
+ if (bc->count > bc->size * 8)
+ badcache_resize(bc, &now, true);
+ if (bc->count < bc->size * 2 && bc->size > bc->minsize)
+ badcache_resize(bc, &now, false);
+ } else
+ bad->expire = *expire;
+
+ cleanup:
+ UNLOCK(&bc->lock);
+}
+
+bool
+dns_badcache_find(dns_badcache_t *bc, dns_name_t *name,
+ dns_rdatatype_t type, uint32_t *flagp,
+ isc_time_t *now)
+{
+ dns_bcentry_t *bad, *prev, *next;
+ bool answer = false;
+ unsigned int i;
+
+ REQUIRE(VALID_BADCACHE(bc));
+ REQUIRE(name != NULL);
+ REQUIRE(now != NULL);
+
+ LOCK(&bc->lock);
+
+ /*
+ * XXXMUKS: dns_name_equal() is expensive as it does a
+ * octet-by-octet comparison, and it can be made better in two
+ * ways here. First, lowercase the names (use
+ * dns_name_downcase() instead of dns_name_copy() in
+ * dns_badcache_add()) so that dns_name_caseequal() can be used
+ * which the compiler will emit as SIMD instructions. Second,
+ * don't put multiple copies of the same name in the chain (or
+ * multiple names will have to be matched for equality), but use
+ * name->link to store the type specific part.
+ */
+
+ if (bc->count == 0)
+ goto skip;
+
+ i = dns_name_hash(name, false) % bc->size;
+ prev = NULL;
+ for (bad = bc->table[i]; bad != NULL; bad = next) {
+ next = bad->next;
+ /*
+ * Search the hash list. Clean out expired records as we go.
+ */
+ if (isc_time_compare(&bad->expire, now) < 0) {
+ if (prev != NULL)
+ prev->next = bad->next;
+ else
+ bc->table[i] = bad->next;
+
+ isc_mem_put(bc->mctx, bad, sizeof(*bad) +
+ bad->name.length);
+ bc->count--;
+ continue;
+ }
+ if (bad->type == type && dns_name_equal(name, &bad->name)) {
+ if (flagp != NULL)
+ *flagp = bad->flags;
+ answer = true;
+ break;
+ }
+ prev = bad;
+ }
+ skip:
+
+ /*
+ * Slow sweep to clean out stale records.
+ */
+ i = bc->sweep++ % bc->size;
+ bad = bc->table[i];
+ if (bad != NULL && isc_time_compare(&bad->expire, now) < 0) {
+ bc->table[i] = bad->next;
+ isc_mem_put(bc->mctx, bad, sizeof(*bad) + bad->name.length);
+ bc->count--;
+ }
+
+ UNLOCK(&bc->lock);
+ return (answer);
+}
+
+void
+dns_badcache_flush(dns_badcache_t *bc) {
+ dns_bcentry_t *entry, *next;
+ unsigned int i;
+
+ REQUIRE(VALID_BADCACHE(bc));
+
+ for (i = 0; bc->count > 0 && i < bc->size; i++) {
+ for (entry = bc->table[i]; entry != NULL; entry = next) {
+ next = entry->next;
+ isc_mem_put(bc->mctx, entry, sizeof(*entry) +
+ entry->name.length);
+ bc->count--;
+ }
+ bc->table[i] = NULL;
+ }
+}
+
+void
+dns_badcache_flushname(dns_badcache_t *bc, dns_name_t *name) {
+ dns_bcentry_t *bad, *prev, *next;
+ isc_result_t result;
+ isc_time_t now;
+ unsigned int i;
+
+ REQUIRE(VALID_BADCACHE(bc));
+ REQUIRE(name != NULL);
+
+ LOCK(&bc->lock);
+
+ result = isc_time_now(&now);
+ if (result != ISC_R_SUCCESS)
+ isc_time_settoepoch(&now);
+ i = dns_name_hash(name, false) % bc->size;
+ prev = NULL;
+ for (bad = bc->table[i]; bad != NULL; bad = next) {
+ int n;
+ next = bad->next;
+ n = isc_time_compare(&bad->expire, &now);
+ if (n < 0 || dns_name_equal(name, &bad->name)) {
+ if (prev == NULL)
+ bc->table[i] = bad->next;
+ else
+ prev->next = bad->next;
+
+ isc_mem_put(bc->mctx, bad, sizeof(*bad) +
+ bad->name.length);
+ bc->count--;
+ } else
+ prev = bad;
+ }
+
+ UNLOCK(&bc->lock);
+}
+
+void
+dns_badcache_flushtree(dns_badcache_t *bc, dns_name_t *name) {
+ dns_bcentry_t *bad, *prev, *next;
+ unsigned int i;
+ int n;
+ isc_time_t now;
+ isc_result_t result;
+
+ REQUIRE(VALID_BADCACHE(bc));
+ REQUIRE(name != NULL);
+
+ LOCK(&bc->lock);
+
+ result = isc_time_now(&now);
+ if (result != ISC_R_SUCCESS)
+ isc_time_settoepoch(&now);
+
+ for (i = 0; bc->count > 0 && i < bc->size; i++) {
+ prev = NULL;
+ for (bad = bc->table[i]; bad != NULL; bad = next) {
+ next = bad->next;
+ n = isc_time_compare(&bad->expire, &now);
+ if (n < 0 || dns_name_issubdomain(&bad->name, name)) {
+ if (prev == NULL)
+ bc->table[i] = bad->next;
+ else
+ prev->next = bad->next;
+
+ isc_mem_put(bc->mctx, bad, sizeof(*bad) +
+ bad->name.length);
+ bc->count--;
+ } else
+ prev = bad;
+ }
+ }
+
+ UNLOCK(&bc->lock);
+}
+
+
+void
+dns_badcache_print(dns_badcache_t *bc, const char *cachename, FILE *fp) {
+ char namebuf[DNS_NAME_FORMATSIZE];
+ char typebuf[DNS_RDATATYPE_FORMATSIZE];
+ dns_bcentry_t *bad, *next, *prev;
+ isc_time_t now;
+ unsigned int i;
+ uint64_t t;
+
+ REQUIRE(VALID_BADCACHE(bc));
+ REQUIRE(cachename != NULL);
+ REQUIRE(fp != NULL);
+
+ LOCK(&bc->lock);
+ fprintf(fp, ";\n; %s\n;\n", cachename);
+
+ TIME_NOW(&now);
+ for (i = 0; bc->count > 0 && i < bc->size; i++) {
+ prev = NULL;
+ for (bad = bc->table[i]; bad != NULL; bad = next) {
+ next = bad->next;
+ if (isc_time_compare(&bad->expire, &now) < 0) {
+ if (prev != NULL)
+ prev->next = bad->next;
+ else
+ bc->table[i] = bad->next;
+
+ isc_mem_put(bc->mctx, bad, sizeof(*bad) +
+ bad->name.length);
+ bc->count--;
+ continue;
+ }
+ prev = bad;
+ dns_name_format(&bad->name, namebuf, sizeof(namebuf));
+ dns_rdatatype_format(bad->type, typebuf,
+ sizeof(typebuf));
+ t = isc_time_microdiff(&bad->expire, &now);
+ t /= 1000;
+ fprintf(fp, "; %s/%s [ttl "
+ "%" PRIu64 "]\n",
+ namebuf, typebuf, t);
+ }
+ }
+ UNLOCK(&bc->lock);
+}