1 files changed, 326 insertions, 0 deletions

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;
+}