summaryrefslogtreecommitdiffstats
path: root/utils/cache_gc
diff options
context:
space:
mode:
authorDaniel Baumann <daniel.baumann@progress-linux.org>2024-04-07 15:26:00 +0000
committerDaniel Baumann <daniel.baumann@progress-linux.org>2024-04-07 15:26:00 +0000
commit830407e88f9d40d954356c3754f2647f91d5c06a (patch)
treed6a0ece6feea91f3c656166dbaa884ef8a29740e /utils/cache_gc
parentInitial commit. (diff)
downloadknot-resolver-830407e88f9d40d954356c3754f2647f91d5c06a.tar.xz
knot-resolver-830407e88f9d40d954356c3754f2647f91d5c06a.zip
Adding upstream version 5.6.0.upstream/5.6.0upstream
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to '')
-rw-r--r--utils/cache_gc/.gitignore2
-rw-r--r--utils/cache_gc/README.rst20
-rw-r--r--utils/cache_gc/categories.c56
-rw-r--r--utils/cache_gc/categories.h10
-rw-r--r--utils/cache_gc/db.c280
-rw-r--r--utils/cache_gc/db.h37
-rw-r--r--utils/cache_gc/kr_cache_gc.c326
-rw-r--r--utils/cache_gc/kr_cache_gc.h41
-rw-r--r--utils/cache_gc/main.c163
-rw-r--r--utils/cache_gc/meson.build31
-rw-r--r--utils/cache_gc/test.integr/deckard.yaml37
-rw-r--r--utils/cache_gc/test.integr/val_rrsig.rpl737
12 files changed, 1740 insertions, 0 deletions
diff --git a/utils/cache_gc/.gitignore b/utils/cache_gc/.gitignore
new file mode 100644
index 0000000..86ce5b1
--- /dev/null
+++ b/utils/cache_gc/.gitignore
@@ -0,0 +1,2 @@
+kres_cache_gc
+
diff --git a/utils/cache_gc/README.rst b/utils/cache_gc/README.rst
new file mode 100644
index 0000000..8d991b2
--- /dev/null
+++ b/utils/cache_gc/README.rst
@@ -0,0 +1,20 @@
+.. SPDX-License-Identifier: GPL-3.0-or-later
+
+.. _garbage-collector:
+
+Garbage Collector
+-----------------
+
+.. note:: When using systemd, ``kres-cache-gc.service`` is enabled by default
+ and does not need any manual configuration.
+
+Knot Resolver employs a separate garbage collector daemon which periodically
+trims the cache to keep its size below size limit configured using
+:envvar:`cache.size`.
+
+To execute the daemon manually, you can use the following command to run it
+every second:
+
+.. code-block:: bash
+
+ $ kres-cache-gc -c /var/cache/knot-resolver -d 1000
diff --git a/utils/cache_gc/categories.c b/utils/cache_gc/categories.c
new file mode 100644
index 0000000..19dec45
--- /dev/null
+++ b/utils/cache_gc/categories.c
@@ -0,0 +1,56 @@
+/* SPDX-License-Identifier: GPL-3.0-or-later */
+#include "categories.h"
+
+#include <libknot/libknot.h>
+#include "lib/utils.h"
+
+static bool rrtype_is_infrastructure(uint16_t r)
+{
+ switch (r) {
+ case KNOT_RRTYPE_NS:
+ case KNOT_RRTYPE_DS:
+ case KNOT_RRTYPE_DNSKEY:
+ case KNOT_RRTYPE_A:
+ case KNOT_RRTYPE_AAAA:
+ return true;
+ default:
+ return false;
+ }
+}
+
+static int get_random(int to)
+{
+ // We don't need these to be really unpredictable,
+ // but this should be cheap enough not to be noticeable.
+ return kr_rand_bytes(1) % to;
+}
+
+// TODO this is just an example, make this more clever
+category_t kr_gc_categorize(gc_record_info_t * info)
+{
+ category_t res;
+
+ if (!info->valid)
+ return CATEGORIES - 1;
+
+ switch (info->no_labels) {
+ case 0: /* root zone */
+ res = 5;
+ break;
+ case 1: /* TLD */
+ res = 10;
+ break;
+ default: /* SLD and below */
+ res = (rrtype_is_infrastructure(info->rrtype) ? 15 : 20);
+ if (info->entry_size > 300)
+ /* Penalty for big answers */
+ res += 30;
+ break;
+ }
+
+ if (info->expires_in <= 0) {
+ res += 40;
+ }
+
+ return res + get_random(5);
+}
diff --git a/utils/cache_gc/categories.h b/utils/cache_gc/categories.h
new file mode 100644
index 0000000..388fbe7
--- /dev/null
+++ b/utils/cache_gc/categories.h
@@ -0,0 +1,10 @@
+/* SPDX-License-Identifier: GPL-3.0-or-later */
+#pragma once
+
+#include "kr_cache_gc.h"
+
+typedef uint8_t category_t;
+
+#define CATEGORIES 100 // number of categories
+
+category_t kr_gc_categorize(gc_record_info_t * info);
diff --git a/utils/cache_gc/db.c b/utils/cache_gc/db.c
new file mode 100644
index 0000000..fc4a2fd
--- /dev/null
+++ b/utils/cache_gc/db.c
@@ -0,0 +1,280 @@
+/* SPDX-License-Identifier: GPL-3.0-or-later */
+
+#include "db.h"
+
+#include "lib/cache/cdb_lmdb.h"
+#include "lib/cache/impl.h"
+
+#include <ctype.h>
+#include <time.h>
+#include <sys/stat.h>
+
+int kr_gc_cache_open(const char *cache_path, struct kr_cache *kres_db,
+ knot_db_t ** libknot_db)
+{
+ char cache_data[strlen(cache_path) + 10];
+ snprintf(cache_data, sizeof(cache_data), "%s/data.mdb", cache_path);
+
+ struct stat st = { 0 };
+ if (stat(cache_path, &st) || !(st.st_mode & S_IFDIR)
+ || stat(cache_data, &st)) {
+ printf("Error: %s does not exist or is not a LMDB.\n", cache_path);
+ return -ENOENT;
+ }
+
+ struct kr_cdb_opts opts = { .path = cache_path, .maxsize = 0/*don't resize*/ };
+
+ int ret = kr_cache_open(kres_db, NULL, &opts, NULL);
+ if (ret || kres_db->db == NULL) {
+ printf("Error opening Resolver cache (%s).\n", kr_strerror(ret));
+ return -EINVAL;
+ }
+
+ *libknot_db = kr_cdb_pt2knot_db_t(kres_db->db);
+ if (*libknot_db == NULL) {
+ printf("Out of memory.\n");
+ return -ENOMEM;
+ }
+
+ return 0;
+}
+
+int kr_gc_cache_check_health(struct kr_cache *kres_db, knot_db_t ** libknot_db)
+{
+ int ret = kr_cache_check_health(kres_db, 0);
+ if (ret == 0) {
+ return 0;
+ } else if (ret != 1) {
+ kr_gc_cache_close(kres_db, *libknot_db);
+ return ret;
+ }
+ /* Cache was reopen. */
+ free(*libknot_db);
+ *libknot_db = kr_cdb_pt2knot_db_t(kres_db->db);
+ if (*libknot_db == NULL) {
+ printf("Out of memory.\n");
+ return -ENOMEM;
+ }
+ return 0;
+}
+
+void kr_gc_cache_close(struct kr_cache *kres_db, knot_db_t * knot_db)
+{
+ free(knot_db);
+ kr_cache_close(kres_db);
+}
+
+int kr_gc_key_consistent(knot_db_val_t key)
+{
+ const uint8_t *kd = key.data;
+ ssize_t i;
+ /* CACHE_KEY_DEF */
+ if (key.len >= 2 && kd[0] == '\0') {
+ /* Beware: root zone is special and starts with
+ * a single \0 followed by type sign */
+ i = 1;
+ } else {
+ /* find the first double zero in the key */
+ for (i = 2; kd[i - 1] || kd[i - 2]; ++i) {
+ if (kr_fails_assert(i < key.len))
+ return kr_error(EINVAL);
+ }
+ }
+ // the next character can be used for classification
+ switch (kd[i]) {
+ case 'E':
+ (void)0; // C can't have a variable definition following a label
+ uint16_t type;
+ if (kr_fails_assert(i + 1 + sizeof(type) <= key.len))
+ return kr_error(EINVAL);
+ memcpy(&type, kd + i + 1, sizeof(type));
+ return type;
+ case '1':
+ return KNOT_RRTYPE_NSEC;
+ case '3':
+ return KNOT_RRTYPE_NSEC3;
+ case 'S': // the rtt_state entries are considered inconsistent, at least for now
+ return -1;
+ default:
+ kr_assert(!EINVAL);
+ return kr_error(EINVAL);
+ }
+}
+
+/// expects that key is consistent! CACHE_KEY_DEF
+static uint8_t entry_labels(knot_db_val_t * key, uint16_t rrtype)
+{
+ uint8_t lab = 0, *p = key->data;
+ while (*p != 0) {
+ while (*p++ != 0) {
+ if (p - (uint8_t *) key->data >= key->len) {
+ return 0;
+ }
+ }
+ lab++;
+ }
+ if (rrtype == KNOT_RRTYPE_NSEC3) {
+ // We don't know the number of labels so easily,
+ // but let's classify everything as directly
+ // below the zone apex (that's most common).
+ ++lab;
+ }
+ return lab;
+}
+
+void debug_printbin(const char *str, unsigned int len)
+{
+ putchar('"');
+ for (int idx = 0; idx < len; idx++) {
+ char c = str[idx];
+ if (isprint(c))
+ putchar(c);
+ else
+ printf("`%02hhx`", c);
+ }
+ putchar('"');
+}
+
+/** Return one entry_h reference from a cache DB value. NULL if not consistent/suitable. */
+static const struct entry_h *val2entry(const knot_db_val_t val, uint16_t ktype)
+{
+ if (ktype != KNOT_RRTYPE_NS)
+ return entry_h_consistent(val, ktype);
+ /* Otherwise we have a multi-purpose entry.
+ * Well, for now we simply choose the most suitable entry;
+ * the only realistic collision is DNAME in apex where we'll prefer NS. */
+ entry_list_t el;
+ if (entry_list_parse(val, el))
+ return NULL;
+ for (int i = ENTRY_APEX_NSECS_CNT; i < EL_LENGTH; ++i) {
+ if (el[i].len)
+ return entry_h_consistent(el[i], EL2RRTYPE(i));
+ }
+ /* Only NSEC* meta-data inside. */
+ return NULL;
+}
+
+int kr_gc_cache_iter(knot_db_t * knot_db, const kr_cache_gc_cfg_t *cfg,
+ kr_gc_iter_callback callback, void *ctx)
+{
+ unsigned int counter_iter = 0;
+ unsigned int counter_gc_consistent = 0;
+ unsigned int counter_kr_consistent = 0;
+
+ knot_db_txn_t txn = { 0 };
+ knot_db_iter_t *it = NULL;
+ const knot_db_api_t *api = knot_db_lmdb_api();
+ gc_record_info_t info = { 0 };
+ int64_t now = time(NULL);
+
+ int ret = api->txn_begin(knot_db, &txn, KNOT_DB_RDONLY);
+ if (ret != KNOT_EOK) {
+ printf("Error starting DB transaction (%s).\n", knot_strerror(ret));
+ return ret;
+ }
+
+ it = api->iter_begin(&txn, KNOT_DB_NOOP); // _FIRST is split for easier debugging
+ if (it == NULL) {
+ printf("Error: failed to create an iterator.\n");
+ api->txn_abort(&txn);
+ return KNOT_ERROR;
+ }
+ it = api->iter_seek(it, NULL, KNOT_DB_FIRST);
+ if (it == NULL)
+ printf("Suspicious: completely empty LMDB at this moment?\n");
+
+ int txn_steps = 0;
+ while (it != NULL) {
+ knot_db_val_t key = { 0 }, val = { 0 };
+ ret = api->iter_key(it, &key);
+ if (ret == KNOT_EOK && key.len == 4 && memcmp("VERS", key.data, 4) == 0) {
+ /* skip DB metadata */
+ goto skip;
+ }
+ if (ret == KNOT_EOK) {
+ ret = api->iter_val(it, &val);
+ }
+ if (ret != KNOT_EOK) {
+ goto error;
+ }
+
+ info.entry_size = key.len + val.len;
+ info.valid = false;
+ const int entry_type = kr_gc_key_consistent(key);
+ const struct entry_h *entry = NULL;
+ if (entry_type >= 0) {
+ counter_gc_consistent++;
+ entry = val2entry(val, entry_type);
+ }
+ /* TODO: perhaps improve some details around here:
+ * - rtt_state entries are considered gc_inconsistent;
+ * therefore they'll be the first to get freed (see kr_gc_categorize())
+ * - xNAME have .rrtype NS
+ * - DNAME hidden on NS name will not be considered here
+ * - if zone has NSEC* meta-data but no NS, it will be seen
+ * here as kr_inconsistent */
+ if (entry != NULL) {
+ info.valid = true;
+ info.rrtype = entry_type;
+ info.expires_in = entry->time + entry->ttl - now;
+ info.no_labels = entry_labels(&key, entry_type);
+ }
+ counter_iter++;
+ counter_kr_consistent += info.valid;
+ if (VERBOSE_STATUS) {
+ if (!entry_type || !entry) { // don't log fully consistent entries
+ printf
+ ("GC %sconsistent, KR %sconsistent, size %zu, key len %zu: ",
+ entry_type ? "" : "in", entry ? "" : "IN",
+ (key.len + val.len), key.len);
+ debug_printbin(key.data, key.len);
+ printf("\n");
+ }
+ }
+ ret = callback(&key, &info, ctx);
+
+ if (ret != KNOT_EOK) {
+ error:
+ printf("Error iterating database (%s).\n",
+ knot_strerror(ret));
+ api->iter_finish(it);
+ api->txn_abort(&txn);
+ return ret;
+ }
+
+ skip: // Advance to the next GC item.
+ if (++txn_steps < cfg->ro_txn_items || !cfg->ro_txn_items/*unlimited*/) {
+ it = api->iter_next(it);
+ } else {
+ /* The transaction has been too long; let's reopen it. */
+ txn_steps = 0;
+ uint8_t key_storage[key.len];
+ memcpy(key_storage, key.data, key.len);
+ key.data = key_storage;
+
+ api->iter_finish(it);
+ api->txn_abort(&txn);
+
+ ret = api->txn_begin(knot_db, &txn, KNOT_DB_RDONLY);
+ if (ret != KNOT_EOK) {
+ printf("Error restarting DB transaction (%s).\n",
+ knot_strerror(ret));
+ return ret;
+ }
+ it = api->iter_begin(&txn, KNOT_DB_NOOP);
+ if (it == NULL) {
+ printf("Error: failed to create an iterator.\n");
+ api->txn_abort(&txn);
+ return KNOT_ERROR;
+ }
+ it = api->iter_seek(it, &key, KNOT_DB_GEQ);
+ // NULL here means we'we reached the end
+ }
+ }
+
+ api->txn_abort(&txn);
+
+ kr_log_debug(CACHE, "iterated %u items, gc consistent %u, kr consistent %u\n",
+ counter_iter, counter_gc_consistent, counter_kr_consistent);
+ return KNOT_EOK;
+}
diff --git a/utils/cache_gc/db.h b/utils/cache_gc/db.h
new file mode 100644
index 0000000..7865471
--- /dev/null
+++ b/utils/cache_gc/db.h
@@ -0,0 +1,37 @@
+/* SPDX-License-Identifier: GPL-3.0-or-later */
+#pragma once
+
+#include <lib/cache/api.h>
+#include <libknot/libknot.h>
+
+#include "kr_cache_gc.h"
+
+int kr_gc_cache_open(const char *cache_path, struct kr_cache *kres_db,
+ knot_db_t ** libknot_db);
+
+/** A wrapper around kr_cdb_api::check_health that keeps libknot_db up to date.
+ * \return zero or negative error code. */
+int kr_gc_cache_check_health(struct kr_cache *kres_db, knot_db_t ** libknot_db);
+
+void kr_gc_cache_close(struct kr_cache *kres_db, knot_db_t * knot_db);
+
+typedef int (*kr_gc_iter_callback)(const knot_db_val_t * key,
+ gc_record_info_t * info, void *ctx);
+
+int kr_gc_cache_iter(knot_db_t * knot_db, const kr_cache_gc_cfg_t *cfg,
+ kr_gc_iter_callback callback, void *ctx);
+
+/** Return RR type corresponding to the key or negative error code.
+ *
+ * Error is returned on unexpected values (those also trigger assertion)
+ * and on other kinds of data in cache (e.g. struct rtt_state).
+ */
+int kr_gc_key_consistent(knot_db_val_t key);
+
+/** Printf a *binary* string in a human-readable way. */
+void debug_printbin(const char *str, unsigned int len);
+
+/** Block run in --verbose mode; optimized when not run. */
+#define VERBOSE_STATUS __builtin_expect(KR_LOG_LEVEL_IS(LOG_DEBUG), false)
+/* TODO: replace when solving GC logging properly */
+
diff --git a/utils/cache_gc/kr_cache_gc.c b/utils/cache_gc/kr_cache_gc.c
new file mode 100644
index 0000000..5978345
--- /dev/null
+++ b/utils/cache_gc/kr_cache_gc.c
@@ -0,0 +1,326 @@
+/* SPDX-License-Identifier: GPL-3.0-or-later */
+// standard includes
+#include <inttypes.h>
+#include <limits.h>
+#include <stdio.h>
+#include <time.h>
+
+// libknot includes
+#include <libknot/libknot.h>
+
+// dynarray is inside libknot since 3.1, but it's differently named
+#ifdef knot_dynarray_declare
+ #define dynarray_declare knot_dynarray_declare
+ #define dynarray_define knot_dynarray_define
+ #define dynarray_foreach knot_dynarray_foreach
+#else
+ #include <contrib/dynarray.h>
+#endif
+
+// resolver includes
+#include <lib/cache/api.h>
+#include <lib/cache/impl.h>
+#include <lib/defines.h>
+#include "lib/cache/cdb_lmdb.h"
+#include "lib/utils.h"
+
+#include "kr_cache_gc.h"
+
+#include "categories.h"
+#include "db.h"
+
+// section: dbval_copy
+
+static knot_db_val_t *dbval_copy(const knot_db_val_t * from)
+{
+ knot_db_val_t *to = malloc(sizeof(knot_db_val_t) + from->len);
+ if (to != NULL) {
+ memcpy(to, from, sizeof(knot_db_val_t));
+ to->data = to + 1; // == ((uit8_t *)to) + sizeof(knot_db_val_t)
+ memcpy(to->data, from->data, from->len);
+ }
+ return to;
+}
+
+// section: rrtype list
+
+dynarray_declare(rrtype, uint16_t, DYNARRAY_VISIBILITY_STATIC, 64)
+ dynarray_define(rrtype, uint16_t, DYNARRAY_VISIBILITY_STATIC)
+static void rrtypelist_add(rrtype_dynarray_t * arr, uint16_t add_type)
+{
+ bool already_present = false;
+ dynarray_foreach(rrtype, uint16_t, i, *arr) {
+ if (*i == add_type) {
+ already_present = true;
+ break;
+ }
+ }
+ if (!already_present) {
+ rrtype_dynarray_add(arr, &add_type);
+ }
+}
+
+static void rrtypelist_print(rrtype_dynarray_t * arr)
+{
+ char type_s[32] = { 0 };
+ dynarray_foreach(rrtype, uint16_t, i, *arr) {
+ knot_rrtype_to_string(*i, type_s, sizeof(type_s));
+ printf(" %s", type_s);
+ }
+ printf("\n");
+}
+
+dynarray_declare(entry, knot_db_val_t *, DYNARRAY_VISIBILITY_STATIC, 256)
+ dynarray_define(entry, knot_db_val_t *, DYNARRAY_VISIBILITY_STATIC)
+static void entry_dynarray_deep_free(entry_dynarray_t * d)
+{
+ dynarray_foreach(entry, knot_db_val_t *, i, *d) {
+ free(*i);
+ }
+ entry_dynarray_free(d);
+}
+
+typedef struct {
+ size_t categories_sizes[CATEGORIES];
+ size_t records;
+} ctx_compute_categories_t;
+
+int cb_compute_categories(const knot_db_val_t * key, gc_record_info_t * info,
+ void *vctx)
+{
+ ctx_compute_categories_t *ctx = vctx;
+ category_t cat = kr_gc_categorize(info);
+ (void)key;
+ ctx->categories_sizes[cat] += info->entry_size;
+ ctx->records++;
+ return KNOT_EOK;
+}
+
+typedef struct {
+ category_t limit_category;
+ entry_dynarray_t to_delete;
+ size_t cfg_temp_keys_space;
+ size_t used_space;
+ size_t oversize_records;
+} ctx_delete_categories_t;
+
+int cb_delete_categories(const knot_db_val_t * key, gc_record_info_t * info,
+ void *vctx)
+{
+ ctx_delete_categories_t *ctx = vctx;
+ category_t cat = kr_gc_categorize(info);
+ if (cat >= ctx->limit_category) {
+ knot_db_val_t *todelete = dbval_copy(key);
+ size_t used = ctx->used_space + key->len + sizeof(*key);
+ if ((ctx->cfg_temp_keys_space > 0 &&
+ used > ctx->cfg_temp_keys_space) || todelete == NULL) {
+ ctx->oversize_records++;
+ free(todelete);
+ } else {
+ entry_dynarray_add(&ctx->to_delete, &todelete);
+ ctx->used_space = used;
+ }
+ }
+ return KNOT_EOK;
+}
+
+struct kr_cache_gc_state {
+ struct kr_cache kres_db;
+ knot_db_t *db;
+};
+
+void kr_cache_gc_free_state(kr_cache_gc_state_t **state)
+{
+ if (kr_fails_assert(state))
+ return;
+ if (!*state) { // not open
+ return;
+ }
+ kr_gc_cache_close(&(*state)->kres_db, (*state)->db);
+ free(*state);
+ *state = NULL;
+}
+
+int kr_cache_gc(kr_cache_gc_cfg_t *cfg, kr_cache_gc_state_t **state)
+{
+ // The whole function works in four "big phases":
+ //// 1. find out whether we should even do analysis and deletion.
+ if (kr_fails_assert(cfg && state))
+ return KNOT_EINVAL;
+ int ret;
+ // Ensure that we have open and "healthy" cache.
+ if (!*state) {
+ *state = calloc(1, sizeof(**state));
+ if (!*state) {
+ return KNOT_ENOMEM;
+ }
+ ret = kr_gc_cache_open(cfg->cache_path, &(*state)->kres_db,
+ &(*state)->db);
+ } else { // To be sure, we guard against the file getting replaced.
+ ret = kr_gc_cache_check_health(&(*state)->kres_db, &(*state)->db);
+ // In particular, missing data.mdb gives us kr_error(ENOENT) == KNOT_ENOENT
+ }
+ if (ret) {
+ free(*state);
+ *state = NULL;
+ return ret;
+ }
+ knot_db_t *const db = (*state)->db; // frequently used shortcut
+
+ const double db_usage = kr_cdb_lmdb()->usage_percent((*state)->kres_db.db);
+ const bool large_usage = db_usage >= cfg->cache_max_usage;
+ if (cfg->dry_run || large_usage || VERBOSE_STATUS) { // don't print this on every size check
+ printf("Usage: %.2lf%%\n", db_usage);
+ }
+ if (cfg->dry_run || !large_usage) {
+ return KNOT_EOK;
+ }
+
+ //// 2. classify all cache items into categories
+ // and compute which categories to delete.
+ kr_timer_t timer_analyze = { 0 }, timer_choose = { 0 }, timer_delete =
+ { 0 }, timer_rw_txn = { 0 };
+
+ kr_timer_start(&timer_analyze);
+ ctx_compute_categories_t cats = { { 0 }
+ };
+ ret = kr_gc_cache_iter(db, cfg, cb_compute_categories, &cats);
+ if (ret != KNOT_EOK) {
+ kr_cache_gc_free_state(state);
+ return ret;
+ }
+
+ //ssize_t amount_tofree = knot_db_lmdb_get_mapsize(db) * cfg->cache_to_be_freed / 100;
+ // Mixing ^^ page usage and entry sizes (key+value lengths) didn't work
+ // too well, probably due to internal fragmentation after some GC cycles.
+ // Therefore let's scale this by the ratio of these two sums.
+ ssize_t cats_sumsize = 0;
+ for (int i = 0; i < CATEGORIES; ++i) {
+ cats_sumsize += cats.categories_sizes[i];
+ }
+ /* use less precise variant to avoid 32-bit overflow */
+ ssize_t amount_tofree = cats_sumsize / 100 * cfg->cache_to_be_freed;
+
+ kr_log_debug(CACHE, "tofree: %zd / %zd\n", amount_tofree, cats_sumsize);
+ if (VERBOSE_STATUS) {
+ for (int i = 0; i < CATEGORIES; i++) {
+ if (cats.categories_sizes[i] > 0) {
+ printf("category %.2d size %zu\n", i,
+ cats.categories_sizes[i]);
+ }
+ }
+ }
+
+ category_t limit_category = CATEGORIES;
+ while (limit_category > 0 && amount_tofree > 0) {
+ amount_tofree -= cats.categories_sizes[--limit_category];
+ }
+
+ printf("Cache analyzed in %.0lf msecs, %zu records, limit category is %d.\n",
+ kr_timer_elapsed(&timer_analyze) * 1000, cats.records, limit_category);
+
+ //// 3. pass whole cache again to collect a list of keys that should be deleted.
+ kr_timer_start(&timer_choose);
+ ctx_delete_categories_t to_del = { 0 };
+ to_del.cfg_temp_keys_space = cfg->temp_keys_space;
+ to_del.limit_category = limit_category;
+ ret = kr_gc_cache_iter(db, cfg, cb_delete_categories, &to_del);
+ if (ret != KNOT_EOK) {
+ entry_dynarray_deep_free(&to_del.to_delete);
+ kr_cache_gc_free_state(state);
+ return ret;
+ }
+ printf
+ ("%zu records to be deleted using %.2lf MBytes of temporary memory, %zu records skipped due to memory limit.\n",
+ to_del.to_delete.size, ((double)to_del.used_space / 1048576.0),
+ to_del.oversize_records);
+
+ //// 4. execute the planned deletions.
+ const knot_db_api_t *api = knot_db_lmdb_api();
+ knot_db_txn_t txn = { 0 };
+ size_t deleted_records = 0, already_gone = 0, rw_txn_count = 0;
+
+ kr_timer_start(&timer_delete);
+ kr_timer_start(&timer_rw_txn);
+ rrtype_dynarray_t deleted_rrtypes = { 0 };
+
+ ret = api->txn_begin(db, &txn, 0);
+ if (ret != KNOT_EOK) {
+ printf("Error starting R/W DB transaction (%s).\n",
+ knot_strerror(ret));
+ entry_dynarray_deep_free(&to_del.to_delete);
+ kr_cache_gc_free_state(state);
+ return ret;
+ }
+
+ dynarray_foreach(entry, knot_db_val_t *, i, to_del.to_delete) {
+ ret = api->del(&txn, *i);
+ switch (ret) {
+ case KNOT_EOK:
+ deleted_records++;
+ const int entry_type = kr_gc_key_consistent(**i);
+ if (entry_type >= 0) // some "inconsistent" entries are OK
+ rrtypelist_add(&deleted_rrtypes, entry_type);
+ break;
+ case KNOT_ENOENT:
+ already_gone++;
+ if (VERBOSE_STATUS) {
+ // kresd normally only inserts (or overwrites),
+ // so it's generally suspicious when a key goes missing.
+ printf("Record already gone (key len %zu): ", (*i)->len);
+ debug_printbin((*i)->data, (*i)->len);
+ printf("\n");
+ }
+ break;
+ case KNOT_ESPACE:
+ printf("Warning: out of space, bailing out to retry later.\n");
+ api->txn_abort(&txn);
+ goto finish;
+ default:
+ printf("Warning: skipping deletion because of error (%s)\n",
+ knot_strerror(ret));
+ api->txn_abort(&txn);
+ ret = api->txn_begin(db, &txn, 0);
+ if (ret != KNOT_EOK) {
+ printf
+ ("Error: can't begin txn because of error (%s)\n",
+ knot_strerror(ret));
+ goto finish;
+ }
+ continue;
+ }
+ if ((cfg->rw_txn_items > 0 &&
+ (deleted_records + already_gone) % cfg->rw_txn_items == 0) ||
+ (cfg->rw_txn_duration > 0 &&
+ kr_timer_elapsed_us(&timer_rw_txn) > cfg->rw_txn_duration)) {
+ ret = api->txn_commit(&txn);
+ if (ret == KNOT_EOK) {
+ rw_txn_count++;
+ usleep(cfg->rw_txn_delay);
+ kr_timer_start(&timer_rw_txn);
+ ret = api->txn_begin(db, &txn, 0);
+ }
+ if (ret != KNOT_EOK) {
+ printf("Error: transaction failed (%s)\n",
+ knot_strerror(ret));
+ goto finish;
+ }
+ }
+ }
+ ret = api->txn_commit(&txn);
+
+finish:
+ printf("Deleted %zu records (%zu already gone) types", deleted_records,
+ already_gone);
+ rrtypelist_print(&deleted_rrtypes);
+ printf("It took %.0lf msecs, %zu transactions (%s)\n\n",
+ kr_timer_elapsed(&timer_delete) * 1000, rw_txn_count, knot_strerror(ret));
+
+ rrtype_dynarray_free(&deleted_rrtypes);
+ entry_dynarray_deep_free(&to_del.to_delete);
+
+ // OK, let's close it in this case.
+ kr_cache_gc_free_state(state);
+
+ return ret;
+}
diff --git a/utils/cache_gc/kr_cache_gc.h b/utils/cache_gc/kr_cache_gc.h
new file mode 100644
index 0000000..c64e99e
--- /dev/null
+++ b/utils/cache_gc/kr_cache_gc.h
@@ -0,0 +1,41 @@
+/* SPDX-License-Identifier: GPL-3.0-or-later */
+#pragma once
+
+#include <stdbool.h>
+#include <stddef.h>
+#include <stdint.h>
+
+typedef struct {
+ size_t entry_size; // amount of bytes occupied in cache by this record
+ bool valid; // fields further down are valid (ignore them if false)
+ int64_t expires_in; // < 0 => already expired
+ uint16_t rrtype;
+ uint8_t no_labels; // 0 == ., 1 == root zone member, 2 == TLD member ...
+ uint8_t rank;
+} gc_record_info_t;
+
+typedef struct {
+ const char *cache_path; // path to the LMDB with resolver cache
+ unsigned long gc_interval; // waiting time between two whole garbage collections in usecs (0 = just one-time cleanup)
+
+ size_t temp_keys_space; // maximum amount of temporary memory for copied keys in bytes (0 = unlimited)
+
+ size_t rw_txn_items; // maximum number of deleted records per RW transaction (0 = unlimited)
+ size_t ro_txn_items; // maximum number of iterated records (RO transactions, 0 = unlimited)
+ unsigned long rw_txn_duration; // maximum duration of RW transaction in usecs (0 = unlimited)
+ unsigned long rw_txn_delay; // waiting time between two RW transactions in usecs
+
+ uint8_t cache_max_usage; // maximum cache usage before triggering GC (percent)
+ uint8_t cache_to_be_freed; // percent of current cache usage to be freed during GC
+
+ bool dry_run;
+} kr_cache_gc_cfg_t;
+
+/** State persisting across kr_cache_gc() invocations (opaque).
+ * NULL pointer represents a clean state. */
+typedef struct kr_cache_gc_state kr_cache_gc_state_t;
+
+/** Do one iteration of cache-size check and (if necessary) GC pass. */
+int kr_cache_gc(kr_cache_gc_cfg_t *cfg, kr_cache_gc_state_t **state);
+void kr_cache_gc_free_state(kr_cache_gc_state_t **state);
+
diff --git a/utils/cache_gc/main.c b/utils/cache_gc/main.c
new file mode 100644
index 0000000..2e863e6
--- /dev/null
+++ b/utils/cache_gc/main.c
@@ -0,0 +1,163 @@
+/* SPDX-License-Identifier: GPL-3.0-or-later */
+#include <signal.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <unistd.h>
+
+#include "lib/defines.h"
+#include "lib/utils.h"
+#include <libknot/libknot.h>
+#include <lmdb.h>
+
+#include "kresconfig.h"
+#include "kr_cache_gc.h"
+
+volatile static int killed = 0;
+
+static void got_killed(int signum)
+{
+ (void)signum;
+ switch (++killed) {
+ case 1:
+ break;
+ case 2:
+ exit(5);
+ break;
+ case 3:
+ abort();
+ default:
+ kr_assert(false);
+ }
+}
+
+static void print_help()
+{
+ printf("Usage: kr_cache_gc -c <resolver_cache> [ optional params... ]\n");
+ printf("Optional params:\n");
+ printf(" -d <garbage_interval(millis)>\n");
+ printf(" -l <deletes_per_txn>\n");
+ printf(" -L <reads_per_txn>\n");
+ printf(" -m <rw_txn_duration(usecs)>\n");
+ printf(" -u <cache_max_usage(percent)>\n");
+ printf(" -f <cache_to_be_freed(percent-of-current-usage)>\n");
+ printf(" -w <wait_next_rw_txn(usecs)>\n");
+ printf(" -t <temporary_memory(MBytes)>\n");
+ printf(" -n (= dry run)\n");
+}
+
+static long get_nonneg_optarg()
+{
+ char *end;
+ const long result = strtol(optarg, &end, 10);
+ if (result >= 0 && end && *end == '\0')
+ return result;
+ // not OK
+ print_help();
+ exit(2);
+}
+
+int main(int argc, char *argv[])
+{
+ printf("Knot Resolver Cache Garbage Collector, version %s\n", PACKAGE_VERSION);
+ if (setvbuf(stdout, NULL, _IONBF, 0) || setvbuf(stderr, NULL, _IONBF, 0)) {
+ fprintf(stderr, "Failed to to set output buffering (ignored): %s\n",
+ strerror(errno));
+ fflush(stderr);
+ }
+
+ signal(SIGTERM, got_killed);
+ signal(SIGKILL, got_killed);
+ signal(SIGPIPE, got_killed);
+ signal(SIGCHLD, got_killed);
+ signal(SIGINT, got_killed);
+
+ kr_cache_gc_cfg_t cfg = {
+ .ro_txn_items = 200,
+ .rw_txn_items = 100,
+ .cache_max_usage = 80,
+ .cache_to_be_freed = 10
+ };
+
+ int o;
+ while ((o = getopt(argc, argv, "hnvc:d:l:L:m:u:f:w:t:")) != -1) {
+ switch (o) {
+ case 'c':
+ cfg.cache_path = optarg;
+ break;
+ case 'd':
+ cfg.gc_interval = get_nonneg_optarg();
+ cfg.gc_interval *= 1000;
+ break;
+ case 'l':
+ cfg.rw_txn_items = get_nonneg_optarg();
+ break;
+ case 'L':
+ cfg.ro_txn_items = get_nonneg_optarg();
+ break;
+ case 'm':
+ cfg.rw_txn_duration = get_nonneg_optarg();
+ break;
+ case 'u':
+ cfg.cache_max_usage = get_nonneg_optarg();
+ break;
+ case 'f':
+ cfg.cache_to_be_freed = get_nonneg_optarg();
+ break;
+ case 'w':
+ cfg.rw_txn_delay = get_nonneg_optarg();
+ break;
+ case 't':
+ cfg.temp_keys_space = get_nonneg_optarg();
+ cfg.temp_keys_space *= 1048576;
+ break;
+ case 'n':
+ cfg.dry_run = true;
+ break;
+ case 'v':
+ kr_log_level_set(LOG_DEBUG);
+ break;
+ case ':':
+ case '?':
+ case 'h':
+ print_help();
+ return 1;
+ default:
+ kr_assert(false);
+ }
+ }
+
+ if (cfg.cache_path == NULL) {
+ print_help();
+ return 1;
+ }
+
+ int exit_code = 0;
+ kr_cache_gc_state_t *gc_state = NULL;
+ bool last_espace = false;
+ do {
+ int ret = kr_cache_gc(&cfg, &gc_state);
+
+ /* Let's tolerate ESPACE unless twice in a row. */
+ if (ret == KNOT_ESPACE) {
+ if (!last_espace)
+ ret = KNOT_EOK;
+ last_espace = true;
+ } else {
+ last_espace = false;
+ }
+
+ // ENOENT: kresd may not be started yet or cleared the cache now
+ // MDB_MAP_RESIZED: GC bailed out but on next iteration it should be OK
+ if (ret && ret != KNOT_ENOENT && ret != kr_error(MDB_MAP_RESIZED)) {
+ printf("Error (%s)\n", knot_strerror(ret));
+ exit_code = 10;
+ break;
+ }
+
+ usleep(cfg.gc_interval);
+ } while (cfg.gc_interval > 0 && !killed);
+
+ kr_cache_gc_free_state(&gc_state);
+
+ return exit_code;
+}
diff --git a/utils/cache_gc/meson.build b/utils/cache_gc/meson.build
new file mode 100644
index 0000000..02ab6c6
--- /dev/null
+++ b/utils/cache_gc/meson.build
@@ -0,0 +1,31 @@
+## utils/cache_gc
+# SPDX-License-Identifier: GPL-3.0-or-later
+
+cache_gc_src = files([
+ 'categories.c',
+ 'db.c',
+ 'kr_cache_gc.c',
+ 'main.c',
+])
+c_src_lint += cache_gc_src
+
+if build_utils
+ cache_gc = executable(
+ 'kres-cache-gc',
+ cache_gc_src,
+ dependencies: [
+ kresconfig_dep,
+ contrib_dep,
+ libkres_dep,
+ libknot,
+ luajit_inc,
+ ],
+ install: true,
+ install_dir: get_option('sbindir'),
+ )
+
+integr_tests += [
+ ['gc_cache_overflow', meson.current_source_dir() / 'test.integr'],
+]
+
+endif
diff --git a/utils/cache_gc/test.integr/deckard.yaml b/utils/cache_gc/test.integr/deckard.yaml
new file mode 100644
index 0000000..b1a8b15
--- /dev/null
+++ b/utils/cache_gc/test.integr/deckard.yaml
@@ -0,0 +1,37 @@
+# SPDX-License-Identifier: GPL-3.0-or-later
+programs:
+- name: kresd1
+ binary: kresd
+ additional:
+ - -n
+ - ../kresd1/
+ templates:
+ - lib/cache/overflow.test.integr/kresd_config.j2
+ - tests/config/test_dns_generators.lua
+ configs:
+ - config
+ - dns_gen.lua
+- name: kresd2
+ binary: kresd
+ additional:
+ - -n
+ - ../kresd1/
+ templates:
+ - lib/cache/overflow.test.integr/kresd_config.j2
+ - tests/config/test_dns_generators.lua
+ configs:
+ - config
+ - dns_gen.lua
+- name: gc
+ binary: kres-cache-gc
+ additional:
+ # small cache needs shorter RW transactions and larger "percentages"
+ - -l8
+ - -u50
+ - -f20
+ - -d1
+ - -c
+ - ../kresd1/
+ conncheck: False
+ templates: []
+ configs: []
diff --git a/utils/cache_gc/test.integr/val_rrsig.rpl b/utils/cache_gc/test.integr/val_rrsig.rpl
new file mode 100644
index 0000000..22002b7
--- /dev/null
+++ b/utils/cache_gc/test.integr/val_rrsig.rpl
@@ -0,0 +1,737 @@
+query-minimization: off
+CONFIG_END
+
+SCENARIO_BEGIN Test validator with qtype RRSIG response
+
+STEP 1 QUERY
+ENTRY_BEGIN
+REPLY RD DO
+SECTION QUESTION
+www.example.com. IN A
+ENTRY_END
+
+STEP 2 CHECK_ANSWER
+ENTRY_BEGIN
+MATCH opcode rcode flags question answer
+REPLY QR RD RA AD DO NOERROR
+SECTION QUESTION
+www.example.com. IN A
+SECTION ANSWER
+www.example.com. IN A 192.0.2.1
+ENTRY_END
+
+STEP 3 QUERY
+ENTRY_BEGIN
+REPLY RD DO
+SECTION QUESTION
+www.example.com. IN A
+ENTRY_END
+
+STEP 4 CHECK_ANSWER
+ENTRY_BEGIN
+MATCH opcode rcode flags question answer
+REPLY QR RD RA AD DO NOERROR
+SECTION QUESTION
+www.example.com. IN A
+SECTION ANSWER
+www.example.com. IN A 192.0.2.1
+ENTRY_END
+
+STEP 5 QUERY
+ENTRY_BEGIN
+REPLY RD DO
+SECTION QUESTION
+www.example.com. IN A
+ENTRY_END
+
+STEP 6 CHECK_ANSWER
+ENTRY_BEGIN
+MATCH opcode rcode flags question answer
+REPLY QR RD RA AD DO NOERROR
+SECTION QUESTION
+www.example.com. IN A
+SECTION ANSWER
+www.example.com. IN A 192.0.2.1
+ENTRY_END
+
+STEP 7 QUERY
+ENTRY_BEGIN
+REPLY RD DO
+SECTION QUESTION
+www.example.com. IN A
+ENTRY_END
+
+STEP 8 CHECK_ANSWER
+ENTRY_BEGIN
+MATCH opcode rcode flags question answer
+REPLY QR RD RA AD DO NOERROR
+SECTION QUESTION
+www.example.com. IN A
+SECTION ANSWER
+www.example.com. IN A 192.0.2.1
+ENTRY_END
+
+STEP 9 QUERY
+ENTRY_BEGIN
+REPLY RD DO
+SECTION QUESTION
+www.example.com. IN A
+ENTRY_END
+
+STEP 10 CHECK_ANSWER
+ENTRY_BEGIN
+MATCH opcode rcode flags question answer
+REPLY QR RD RA AD DO NOERROR
+SECTION QUESTION
+www.example.com. IN A
+SECTION ANSWER
+www.example.com. IN A 192.0.2.1
+ENTRY_END
+
+STEP 11 QUERY
+ENTRY_BEGIN
+REPLY RD DO
+SECTION QUESTION
+www.example.com. IN A
+ENTRY_END
+
+STEP 12 CHECK_ANSWER
+ENTRY_BEGIN
+MATCH opcode rcode flags question answer
+REPLY QR RD RA AD DO NOERROR
+SECTION QUESTION
+www.example.com. IN A
+SECTION ANSWER
+www.example.com. IN A 192.0.2.1
+ENTRY_END
+
+STEP 13 QUERY
+ENTRY_BEGIN
+REPLY RD DO
+SECTION QUESTION
+www.example.com. IN A
+ENTRY_END
+
+STEP 14 CHECK_ANSWER
+ENTRY_BEGIN
+MATCH opcode rcode flags question answer
+REPLY QR RD RA AD DO NOERROR
+SECTION QUESTION
+www.example.com. IN A
+SECTION ANSWER
+www.example.com. IN A 192.0.2.1
+ENTRY_END
+
+STEP 15 QUERY
+ENTRY_BEGIN
+REPLY RD DO
+SECTION QUESTION
+www.example.com. IN A
+ENTRY_END
+
+STEP 16 CHECK_ANSWER
+ENTRY_BEGIN
+MATCH opcode rcode flags question answer
+REPLY QR RD RA AD DO NOERROR
+SECTION QUESTION
+www.example.com. IN A
+SECTION ANSWER
+www.example.com. IN A 192.0.2.1
+ENTRY_END
+
+STEP 17 QUERY
+ENTRY_BEGIN
+REPLY RD DO
+SECTION QUESTION
+www.example.com. IN A
+ENTRY_END
+
+STEP 18 CHECK_ANSWER
+ENTRY_BEGIN
+MATCH opcode rcode flags question answer
+REPLY QR RD RA AD DO NOERROR
+SECTION QUESTION
+www.example.com. IN A
+SECTION ANSWER
+www.example.com. IN A 192.0.2.1
+ENTRY_END
+
+STEP 19 QUERY
+ENTRY_BEGIN
+REPLY RD DO
+SECTION QUESTION
+www.example.com. IN A
+ENTRY_END
+
+STEP 20 CHECK_ANSWER
+ENTRY_BEGIN
+MATCH opcode rcode flags question answer
+REPLY QR RD RA AD DO NOERROR
+SECTION QUESTION
+www.example.com. IN A
+SECTION ANSWER
+www.example.com. IN A 192.0.2.1
+ENTRY_END
+
+STEP 21 QUERY
+ENTRY_BEGIN
+REPLY RD DO
+SECTION QUESTION
+www.example.com. IN A
+ENTRY_END
+
+STEP 22 CHECK_ANSWER
+ENTRY_BEGIN
+MATCH opcode rcode flags question answer
+REPLY QR RD RA AD DO NOERROR
+SECTION QUESTION
+www.example.com. IN A
+SECTION ANSWER
+www.example.com. IN A 192.0.2.1
+ENTRY_END
+
+STEP 23 QUERY
+ENTRY_BEGIN
+REPLY RD DO
+SECTION QUESTION
+www.example.com. IN A
+ENTRY_END
+
+STEP 24 CHECK_ANSWER
+ENTRY_BEGIN
+MATCH opcode rcode flags question answer
+REPLY QR RD RA AD DO NOERROR
+SECTION QUESTION
+www.example.com. IN A
+SECTION ANSWER
+www.example.com. IN A 192.0.2.1
+ENTRY_END
+
+STEP 25 QUERY
+ENTRY_BEGIN
+REPLY RD DO
+SECTION QUESTION
+www.example.com. IN A
+ENTRY_END
+
+STEP 26 CHECK_ANSWER
+ENTRY_BEGIN
+MATCH opcode rcode flags question answer
+REPLY QR RD RA AD DO NOERROR
+SECTION QUESTION
+www.example.com. IN A
+SECTION ANSWER
+www.example.com. IN A 192.0.2.1
+ENTRY_END
+
+STEP 27 QUERY
+ENTRY_BEGIN
+REPLY RD DO
+SECTION QUESTION
+www.example.com. IN A
+ENTRY_END
+
+STEP 28 CHECK_ANSWER
+ENTRY_BEGIN
+MATCH opcode rcode flags question answer
+REPLY QR RD RA AD DO NOERROR
+SECTION QUESTION
+www.example.com. IN A
+SECTION ANSWER
+www.example.com. IN A 192.0.2.1
+ENTRY_END
+
+STEP 29 QUERY
+ENTRY_BEGIN
+REPLY RD DO
+SECTION QUESTION
+www.example.com. IN A
+ENTRY_END
+
+STEP 30 CHECK_ANSWER
+ENTRY_BEGIN
+MATCH opcode rcode flags question answer
+REPLY QR RD RA AD DO NOERROR
+SECTION QUESTION
+www.example.com. IN A
+SECTION ANSWER
+www.example.com. IN A 192.0.2.1
+ENTRY_END
+
+STEP 31 QUERY
+ENTRY_BEGIN
+REPLY RD DO
+SECTION QUESTION
+www.example.com. IN A
+ENTRY_END
+
+STEP 32 CHECK_ANSWER
+ENTRY_BEGIN
+MATCH opcode rcode flags question answer
+REPLY QR RD RA AD DO NOERROR
+SECTION QUESTION
+www.example.com. IN A
+SECTION ANSWER
+www.example.com. IN A 192.0.2.1
+ENTRY_END
+
+STEP 33 QUERY
+ENTRY_BEGIN
+REPLY RD DO
+SECTION QUESTION
+www.example.com. IN A
+ENTRY_END
+
+STEP 34 CHECK_ANSWER
+ENTRY_BEGIN
+MATCH opcode rcode flags question answer
+REPLY QR RD RA AD DO NOERROR
+SECTION QUESTION
+www.example.com. IN A
+SECTION ANSWER
+www.example.com. IN A 192.0.2.1
+ENTRY_END
+
+STEP 35 QUERY
+ENTRY_BEGIN
+REPLY RD DO
+SECTION QUESTION
+www.example.com. IN A
+ENTRY_END
+
+STEP 36 CHECK_ANSWER
+ENTRY_BEGIN
+MATCH opcode rcode flags question answer
+REPLY QR RD RA AD DO NOERROR
+SECTION QUESTION
+www.example.com. IN A
+SECTION ANSWER
+www.example.com. IN A 192.0.2.1
+ENTRY_END
+
+STEP 37 QUERY
+ENTRY_BEGIN
+REPLY RD DO
+SECTION QUESTION
+www.example.com. IN A
+ENTRY_END
+
+STEP 38 CHECK_ANSWER
+ENTRY_BEGIN
+MATCH opcode rcode flags question answer
+REPLY QR RD RA AD DO NOERROR
+SECTION QUESTION
+www.example.com. IN A
+SECTION ANSWER
+www.example.com. IN A 192.0.2.1
+ENTRY_END
+
+STEP 39 QUERY
+ENTRY_BEGIN
+REPLY RD DO
+SECTION QUESTION
+www.example.com. IN A
+ENTRY_END
+
+STEP 40 CHECK_ANSWER
+ENTRY_BEGIN
+MATCH opcode rcode flags question answer
+REPLY QR RD RA AD DO NOERROR
+SECTION QUESTION
+www.example.com. IN A
+SECTION ANSWER
+www.example.com. IN A 192.0.2.1
+ENTRY_END
+
+STEP 41 QUERY
+ENTRY_BEGIN
+REPLY RD DO
+SECTION QUESTION
+www.example.com. IN A
+ENTRY_END
+
+STEP 42 CHECK_ANSWER
+ENTRY_BEGIN
+MATCH opcode rcode flags question answer
+REPLY QR RD RA AD DO NOERROR
+SECTION QUESTION
+www.example.com. IN A
+SECTION ANSWER
+www.example.com. IN A 192.0.2.1
+ENTRY_END
+
+STEP 43 QUERY
+ENTRY_BEGIN
+REPLY RD DO
+SECTION QUESTION
+www.example.com. IN A
+ENTRY_END
+
+STEP 44 CHECK_ANSWER
+ENTRY_BEGIN
+MATCH opcode rcode flags question answer
+REPLY QR RD RA AD DO NOERROR
+SECTION QUESTION
+www.example.com. IN A
+SECTION ANSWER
+www.example.com. IN A 192.0.2.1
+ENTRY_END
+
+STEP 45 QUERY
+ENTRY_BEGIN
+REPLY RD DO
+SECTION QUESTION
+www.example.com. IN A
+ENTRY_END
+
+STEP 46 CHECK_ANSWER
+ENTRY_BEGIN
+MATCH opcode rcode flags question answer
+REPLY QR RD RA AD DO NOERROR
+SECTION QUESTION
+www.example.com. IN A
+SECTION ANSWER
+www.example.com. IN A 192.0.2.1
+ENTRY_END
+
+STEP 47 QUERY
+ENTRY_BEGIN
+REPLY RD DO
+SECTION QUESTION
+www.example.com. IN A
+ENTRY_END
+
+STEP 48 CHECK_ANSWER
+ENTRY_BEGIN
+MATCH opcode rcode flags question answer
+REPLY QR RD RA AD DO NOERROR
+SECTION QUESTION
+www.example.com. IN A
+SECTION ANSWER
+www.example.com. IN A 192.0.2.1
+ENTRY_END
+
+STEP 49 QUERY
+ENTRY_BEGIN
+REPLY RD DO
+SECTION QUESTION
+www.example.com. IN A
+ENTRY_END
+
+STEP 50 CHECK_ANSWER
+ENTRY_BEGIN
+MATCH opcode rcode flags question answer
+REPLY QR RD RA AD DO NOERROR
+SECTION QUESTION
+www.example.com. IN A
+SECTION ANSWER
+www.example.com. IN A 192.0.2.1
+ENTRY_END
+
+STEP 51 QUERY
+ENTRY_BEGIN
+REPLY RD DO
+SECTION QUESTION
+www.example.com. IN A
+ENTRY_END
+
+STEP 52 CHECK_ANSWER
+ENTRY_BEGIN
+MATCH opcode rcode flags question answer
+REPLY QR RD RA AD DO NOERROR
+SECTION QUESTION
+www.example.com. IN A
+SECTION ANSWER
+www.example.com. IN A 192.0.2.1
+ENTRY_END
+
+STEP 53 QUERY
+ENTRY_BEGIN
+REPLY RD DO
+SECTION QUESTION
+www.example.com. IN A
+ENTRY_END
+
+STEP 54 CHECK_ANSWER
+ENTRY_BEGIN
+MATCH opcode rcode flags question answer
+REPLY QR RD RA AD DO NOERROR
+SECTION QUESTION
+www.example.com. IN A
+SECTION ANSWER
+www.example.com. IN A 192.0.2.1
+ENTRY_END
+
+STEP 55 QUERY
+ENTRY_BEGIN
+REPLY RD DO
+SECTION QUESTION
+www.example.com. IN A
+ENTRY_END
+
+STEP 56 CHECK_ANSWER
+ENTRY_BEGIN
+MATCH opcode rcode flags question answer
+REPLY QR RD RA AD DO NOERROR
+SECTION QUESTION
+www.example.com. IN A
+SECTION ANSWER
+www.example.com. IN A 192.0.2.1
+ENTRY_END
+
+STEP 57 QUERY
+ENTRY_BEGIN
+REPLY RD DO
+SECTION QUESTION
+www.example.com. IN A
+ENTRY_END
+
+STEP 58 CHECK_ANSWER
+ENTRY_BEGIN
+MATCH opcode rcode flags question answer
+REPLY QR RD RA AD DO NOERROR
+SECTION QUESTION
+www.example.com. IN A
+SECTION ANSWER
+www.example.com. IN A 192.0.2.1
+ENTRY_END
+
+STEP 59 QUERY
+ENTRY_BEGIN
+REPLY RD DO
+SECTION QUESTION
+www.example.com. IN A
+ENTRY_END
+
+STEP 60 CHECK_ANSWER
+ENTRY_BEGIN
+MATCH opcode rcode flags question answer
+REPLY QR RD RA AD DO NOERROR
+SECTION QUESTION
+www.example.com. IN A
+SECTION ANSWER
+www.example.com. IN A 192.0.2.1
+ENTRY_END
+
+STEP 61 QUERY
+ENTRY_BEGIN
+REPLY RD DO
+SECTION QUESTION
+www.example.com. IN A
+ENTRY_END
+
+STEP 62 CHECK_ANSWER
+ENTRY_BEGIN
+MATCH opcode rcode flags question answer
+REPLY QR RD RA AD DO NOERROR
+SECTION QUESTION
+www.example.com. IN A
+SECTION ANSWER
+www.example.com. IN A 192.0.2.1
+ENTRY_END
+
+STEP 63 QUERY
+ENTRY_BEGIN
+REPLY RD DO
+SECTION QUESTION
+www.example.com. IN A
+ENTRY_END
+
+STEP 64 CHECK_ANSWER
+ENTRY_BEGIN
+MATCH opcode rcode flags question answer
+REPLY QR RD RA AD DO NOERROR
+SECTION QUESTION
+www.example.com. IN A
+SECTION ANSWER
+www.example.com. IN A 192.0.2.1
+ENTRY_END
+
+STEP 65 QUERY
+ENTRY_BEGIN
+REPLY RD DO
+SECTION QUESTION
+www.example.com. IN A
+ENTRY_END
+
+STEP 66 CHECK_ANSWER
+ENTRY_BEGIN
+MATCH opcode rcode flags question answer
+REPLY QR RD RA AD DO NOERROR
+SECTION QUESTION
+www.example.com. IN A
+SECTION ANSWER
+www.example.com. IN A 192.0.2.1
+ENTRY_END
+
+STEP 67 QUERY
+ENTRY_BEGIN
+REPLY RD DO
+SECTION QUESTION
+www.example.com. IN A
+ENTRY_END
+
+STEP 68 CHECK_ANSWER
+ENTRY_BEGIN
+MATCH opcode rcode flags question answer
+REPLY QR RD RA AD DO NOERROR
+SECTION QUESTION
+www.example.com. IN A
+SECTION ANSWER
+www.example.com. IN A 192.0.2.1
+ENTRY_END
+
+STEP 69 QUERY
+ENTRY_BEGIN
+REPLY RD DO
+SECTION QUESTION
+www.example.com. IN A
+ENTRY_END
+
+STEP 70 CHECK_ANSWER
+ENTRY_BEGIN
+MATCH opcode rcode flags question answer
+REPLY QR RD RA AD DO NOERROR
+SECTION QUESTION
+www.example.com. IN A
+SECTION ANSWER
+www.example.com. IN A 192.0.2.1
+ENTRY_END
+
+STEP 71 QUERY
+ENTRY_BEGIN
+REPLY RD DO
+SECTION QUESTION
+www.example.com. IN A
+ENTRY_END
+
+STEP 72 CHECK_ANSWER
+ENTRY_BEGIN
+MATCH opcode rcode flags question answer
+REPLY QR RD RA AD DO NOERROR
+SECTION QUESTION
+www.example.com. IN A
+SECTION ANSWER
+www.example.com. IN A 192.0.2.1
+ENTRY_END
+
+STEP 73 QUERY
+ENTRY_BEGIN
+REPLY RD DO
+SECTION QUESTION
+www.example.com. IN A
+ENTRY_END
+
+STEP 74 CHECK_ANSWER
+ENTRY_BEGIN
+MATCH opcode rcode flags question answer
+REPLY QR RD RA AD DO NOERROR
+SECTION QUESTION
+www.example.com. IN A
+SECTION ANSWER
+www.example.com. IN A 192.0.2.1
+ENTRY_END
+
+STEP 75 QUERY
+ENTRY_BEGIN
+REPLY RD DO
+SECTION QUESTION
+www.example.com. IN A
+ENTRY_END
+
+STEP 76 CHECK_ANSWER
+ENTRY_BEGIN
+MATCH opcode rcode flags question answer
+REPLY QR RD RA AD DO NOERROR
+SECTION QUESTION
+www.example.com. IN A
+SECTION ANSWER
+www.example.com. IN A 192.0.2.1
+ENTRY_END
+
+STEP 77 QUERY
+ENTRY_BEGIN
+REPLY RD DO
+SECTION QUESTION
+www.example.com. IN A
+ENTRY_END
+
+STEP 78 CHECK_ANSWER
+ENTRY_BEGIN
+MATCH opcode rcode flags question answer
+REPLY QR RD RA AD DO NOERROR
+SECTION QUESTION
+www.example.com. IN A
+SECTION ANSWER
+www.example.com. IN A 192.0.2.1
+ENTRY_END
+
+STEP 79 QUERY
+ENTRY_BEGIN
+REPLY RD DO
+SECTION QUESTION
+www.example.com. IN A
+ENTRY_END
+
+STEP 80 CHECK_ANSWER
+ENTRY_BEGIN
+MATCH opcode rcode flags question answer
+REPLY QR RD RA AD DO NOERROR
+SECTION QUESTION
+www.example.com. IN A
+SECTION ANSWER
+www.example.com. IN A 192.0.2.1
+ENTRY_END
+
+STEP 81 QUERY
+ENTRY_BEGIN
+REPLY RD DO
+SECTION QUESTION
+www.example.com. IN A
+ENTRY_END
+
+STEP 82 CHECK_ANSWER
+ENTRY_BEGIN
+MATCH opcode rcode flags question answer
+REPLY QR RD RA AD DO NOERROR
+SECTION QUESTION
+www.example.com. IN A
+SECTION ANSWER
+www.example.com. IN A 192.0.2.1
+ENTRY_END
+
+STEP 83 QUERY
+ENTRY_BEGIN
+REPLY RD DO
+SECTION QUESTION
+www.example.com. IN A
+ENTRY_END
+
+STEP 84 CHECK_ANSWER
+ENTRY_BEGIN
+MATCH opcode rcode flags question answer
+REPLY QR RD RA AD DO NOERROR
+SECTION QUESTION
+www.example.com. IN A
+SECTION ANSWER
+www.example.com. IN A 192.0.2.1
+ENTRY_END
+
+STEP 85 QUERY
+ENTRY_BEGIN
+REPLY RD DO
+SECTION QUESTION
+www.example.com. IN A
+ENTRY_END
+
+STEP 86 CHECK_ANSWER
+ENTRY_BEGIN
+MATCH opcode rcode flags question answer
+REPLY QR RD RA AD DO NOERROR
+SECTION QUESTION
+www.example.com. IN A
+SECTION ANSWER
+www.example.com. IN A 192.0.2.1
+ENTRY_END
+
+SCENARIO_END