summaryrefslogtreecommitdiffstats
path: root/utils/cache_gc/kr_cache_gc.c
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/kr_cache_gc.c
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 'utils/cache_gc/kr_cache_gc.c')
-rw-r--r--utils/cache_gc/kr_cache_gc.c326
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;
+}