diff options
Diffstat (limited to '')
| -rw-r--r-- | lib/cache/api.c | 889 | ||||
| -rw-r--r-- | lib/cache/api.h | 201 | ||||
| -rw-r--r-- | lib/cache/cdb_api.h | 68 | ||||
| -rw-r--r-- | lib/cache/cdb_lmdb.c | 710 | ||||
| -rw-r--r-- | lib/cache/cdb_lmdb.h | 23 | ||||
| -rw-r--r-- | lib/cache/entry_list.c | 293 | ||||
| -rw-r--r-- | lib/cache/entry_pkt.c | 224 | ||||
| -rw-r--r-- | lib/cache/entry_rr.c | 146 | ||||
| -rw-r--r-- | lib/cache/impl.h | 412 | ||||
| -rw-r--r-- | lib/cache/knot_pkt.c | 106 | ||||
| -rw-r--r-- | lib/cache/nsec1.c | 511 | ||||
| -rw-r--r-- | lib/cache/nsec3.c | 501 | ||||
| -rw-r--r-- | lib/cache/peek.c | 724 |
13 files changed, 4808 insertions, 0 deletions
diff --git a/lib/cache/api.c b/lib/cache/api.c new file mode 100644 index 0000000..c0591d6 --- /dev/null +++ b/lib/cache/api.c @@ -0,0 +1,889 @@ +/* Copyright (C) 2014-2017 CZ.NIC, z.s.p.o. <knot-dns@labs.nic.cz> + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <https://www.gnu.org/licenses/>. + */ + +#include <assert.h> +#include <errno.h> +#include <limits.h> +#include <sys/stat.h> +#include <sys/time.h> +#include <time.h> +#include <unistd.h> + +#include <libknot/descriptor.h> +#include <libknot/dname.h> +#include <libknot/errcode.h> +#include <libknot/rrtype/rrsig.h> + +#include "contrib/cleanup.h" +#include "contrib/ucw/lib.h" +#include "lib/cache/api.h" +#include "lib/cache/cdb_lmdb.h" +#include "lib/defines.h" +#include "lib/generic/trie.h" +#include "lib/resolve.h" +#include "lib/rplan.h" +#include "lib/utils.h" + +#include "lib/cache/impl.h" + +/* TODO: + * - Reconsider when RRSIGs are put in and retrieved from the cache. + * Currently it's always done, which _might_ be spurious, depending + * on how kresd will use the returned result. + * There's also the "problem" that kresd ATM does _not_ ask upstream + * with DO bit in some cases. + */ + + +/** Cache version */ +static const uint16_t CACHE_VERSION = 5; +/** Key size */ +#define KEY_HSIZE (sizeof(uint8_t) + sizeof(uint16_t)) +#define KEY_SIZE (KEY_HSIZE + KNOT_DNAME_MAXLEN) + + +/** @internal Forward declarations of the implementation details + * \param optout[out] Set *optout = true; when encountering an opt-out NSEC3 (optional). */ +static ssize_t stash_rrset(struct kr_cache *cache, const struct kr_query *qry, + const knot_rrset_t *rr, const knot_rrset_t *rr_sigs, uint32_t timestamp, + uint8_t rank, trie_t *nsec_pmap, bool *has_optout); +/** Preliminary checks before stash_rrset(). Don't call if returns <= 0. */ +static int stash_rrset_precond(const knot_rrset_t *rr, const struct kr_query *qry/*logs*/); + +/** @internal Removes all records from cache. */ +static inline int cache_clear(struct kr_cache *cache) +{ + cache->stats.delete += 1; + return cache_op(cache, clear); +} + +/** @internal Open cache db transaction and check internal data version. */ +static int assert_right_version(struct kr_cache *cache) +{ + /* Check cache ABI version. */ + /* CACHE_KEY_DEF: to avoid collisions with kr_cache_match(). */ + uint8_t key_str[4] = "VERS"; + knot_db_val_t key = { .data = key_str, .len = sizeof(key_str) }; + knot_db_val_t val = { NULL, 0 }; + int ret = cache_op(cache, read, &key, &val, 1); + if (ret == 0 && val.len == sizeof(CACHE_VERSION) + && memcmp(val.data, &CACHE_VERSION, sizeof(CACHE_VERSION)) == 0) { + ret = kr_error(EEXIST); + } else { + int oldret = ret; + /* Version doesn't match. Recreate cache and write version key. */ + ret = cache_op(cache, count); + if (ret != 0) { /* Non-empty cache, purge it. */ + kr_log_info("[ ][cach] incompatible cache database detected, purging\n"); + if (oldret) { + kr_log_verbose("bad ret: %d\n", oldret); + } else if (val.len != sizeof(CACHE_VERSION)) { + kr_log_verbose("bad length: %d\n", (int)val.len); + } else { + uint16_t ver; + memcpy(&ver, val.data, sizeof(ver)); + kr_log_verbose("bad version: %d\n", (int)ver); + } + ret = cache_clear(cache); + } + /* Either purged or empty. */ + if (ret == 0) { + /* Key/Val is invalidated by cache purge, recreate it */ + val.data = /*const-cast*/(void *)&CACHE_VERSION; + val.len = sizeof(CACHE_VERSION); + ret = cache_op(cache, write, &key, &val, 1); + } + } + kr_cache_sync(cache); + return ret; +} + +int kr_cache_open(struct kr_cache *cache, const struct kr_cdb_api *api, struct kr_cdb_opts *opts, knot_mm_t *mm) +{ + if (!cache) { + return kr_error(EINVAL); + } + /* Open cache */ + if (!api) { + api = kr_cdb_lmdb(); + } + cache->api = api; + int ret = cache->api->open(&cache->db, opts, mm); + if (ret != 0) { + return ret; + } + memset(&cache->stats, 0, sizeof(cache->stats)); + cache->ttl_min = KR_CACHE_DEFAULT_TTL_MIN; + cache->ttl_max = KR_CACHE_DEFAULT_TTL_MAX; + /* Check cache ABI version */ + kr_cache_make_checkpoint(cache); + (void)assert_right_version(cache); + + char *fpath; + ret = asprintf(&fpath, "%s/data.mdb", opts->path); + if (ret > 0) { + kr_cache_emergency_file_to_remove = fpath; + } else { + assert(false); /* non-critical, but still */ + } + return 0; +} + +const char *kr_cache_emergency_file_to_remove = NULL; + + +#define cache_isvalid(cache) ((cache) && (cache)->api && (cache)->db) + +void kr_cache_close(struct kr_cache *cache) +{ + if (cache_isvalid(cache)) { + cache_op(cache, close); + cache->db = NULL; + } + free(/*const-cast*/(char*)kr_cache_emergency_file_to_remove); + kr_cache_emergency_file_to_remove = NULL; +} + +int kr_cache_sync(struct kr_cache *cache) +{ + if (!cache_isvalid(cache)) { + return kr_error(EINVAL); + } + if (cache->api->sync) { + return cache_op(cache, sync); + } + return kr_ok(); +} + +int kr_cache_insert_rr(struct kr_cache *cache, const knot_rrset_t *rr, const knot_rrset_t *rrsig, uint8_t rank, uint32_t timestamp) +{ + int err = stash_rrset_precond(rr, NULL); + if (err <= 0) { + return kr_ok(); + } + ssize_t written = stash_rrset(cache, NULL, rr, rrsig, timestamp, rank, NULL, NULL); + /* Zone's NSEC* parames aren't updated, but that's probably OK + * for kr_cache_insert_rr() */ + if (written >= 0) { + return kr_ok(); + } + + return (int) written; +} + +int kr_cache_clear(struct kr_cache *cache) +{ + if (!cache_isvalid(cache)) { + return kr_error(EINVAL); + } + int ret = cache_clear(cache); + if (ret == 0) { + kr_cache_make_checkpoint(cache); + ret = assert_right_version(cache); + } + return ret; +} + +/* When going stricter, BEWARE of breaking entry_h_consistent_NSEC() */ +struct entry_h * entry_h_consistent(knot_db_val_t data, uint16_t type) +{ + (void) type; /* unused, for now */ + if (!data.data) return NULL; + /* Length checks. */ + if (data.len < offsetof(struct entry_h, data)) + return NULL; + const struct entry_h *eh = data.data; + if (eh->is_packet) { + uint16_t pkt_len; + if (data.len < offsetof(struct entry_h, data) + sizeof(pkt_len)) { + return NULL; + } + memcpy(&pkt_len, eh->data, sizeof(pkt_len)); + if (data.len < offsetof(struct entry_h, data) + sizeof(pkt_len) + + pkt_len) { + return NULL; + } + } + + bool ok = true; + ok = ok && kr_rank_check(eh->rank); + ok = ok && (!kr_rank_test(eh->rank, KR_RANK_BOGUS) + || eh->is_packet); + ok = ok && (eh->is_packet || !eh->has_optout); + + return ok ? /*const-cast*/(struct entry_h *)eh : NULL; +} + +int32_t get_new_ttl(const struct entry_h *entry, const struct kr_query *qry, + const knot_dname_t *owner, uint16_t type, uint32_t now) +{ + int32_t diff = now - entry->time; + if (diff < 0) { + /* We may have obtained the record *after* the request started. */ + diff = 0; + } + int32_t res = entry->ttl - diff; + if (res < 0 && owner && qry && qry->stale_cb) { + /* Stale-serving decision, delegated to a callback. */ + int res_stale = qry->stale_cb(res, owner, type, qry); + if (res_stale >= 0) + return res_stale; + } + return res; +} + +int32_t kr_cache_ttl(const struct kr_cache_p *peek, const struct kr_query *qry, + const knot_dname_t *name, uint16_t type) +{ + const struct entry_h *eh = peek->raw_data; + return get_new_ttl(eh, qry, name, type, qry->timestamp.tv_sec); +} + +/** Check that no label contains a zero character, incl. a log trace. + * + * We refuse to work with those, as LF and our cache keys might become ambiguous. + * Assuming uncompressed name, as usual. + * CACHE_KEY_DEF + */ +static bool check_dname_for_lf(const knot_dname_t *n, const struct kr_query *qry/*logging*/) +{ + const bool ret = knot_dname_size(n) == strlen((const char *)n) + 1; + if (!ret) { WITH_VERBOSE(qry) { + auto_free char *n_str = kr_dname_text(n); + VERBOSE_MSG(qry, "=> skipping zero-containing name %s\n", n_str); + } } + return ret; +} + +/** Return false on types to be ignored. Meant both for sname and direct cache requests. */ +static bool check_rrtype(uint16_t type, const struct kr_query *qry/*logging*/) +{ + const bool ret = !knot_rrtype_is_metatype(type) + && type != KNOT_RRTYPE_RRSIG; + if (!ret) { WITH_VERBOSE(qry) { + auto_free char *type_str = kr_rrtype_text(type); + VERBOSE_MSG(qry, "=> skipping RR type %s\n", type_str); + } } + return ret; +} + +/** Like key_exact_type() but omits a couple checks not holding for pkt cache. */ +knot_db_val_t key_exact_type_maypkt(struct key *k, uint16_t type) +{ + assert(check_rrtype(type, NULL)); + switch (type) { + case KNOT_RRTYPE_RRSIG: /* no RRSIG query caching, at least for now */ + assert(false); + return (knot_db_val_t){ NULL, 0 }; + /* xNAME lumped into NS. */ + case KNOT_RRTYPE_CNAME: + case KNOT_RRTYPE_DNAME: + type = KNOT_RRTYPE_NS; + default: + break; + } + + int name_len = k->buf[0]; + k->buf[name_len + 1] = 0; /* make sure different names can never match */ + k->buf[name_len + 2] = 'E'; /* tag for exact name+type matches */ + memcpy(k->buf + name_len + 3, &type, 2); + k->type = type; + /* CACHE_KEY_DEF: key == dname_lf + '\0' + 'E' + RRTYPE */ + return (knot_db_val_t){ k->buf + 1, name_len + 4 }; +} + + +/** The inside for cache_peek(); implementation separated to ./peek.c */ +int peek_nosync(kr_layer_t *ctx, knot_pkt_t *pkt); +/** function for .produce phase */ +int cache_peek(kr_layer_t *ctx, knot_pkt_t *pkt) +{ + struct kr_request *req = ctx->req; + struct kr_query *qry = req->current_query; + /* We first check various exit-conditions and then call the _real function. */ + + if (!kr_cache_is_open(&req->ctx->cache) + || ctx->state & (KR_STATE_FAIL|KR_STATE_DONE) || qry->flags.NO_CACHE + || (qry->flags.CACHE_TRIED && !qry->stale_cb) + || !check_rrtype(qry->stype, qry) /* LATER: some other behavior for some of these? */ + || qry->sclass != KNOT_CLASS_IN) { + return ctx->state; /* Already resolved/failed or already tried, etc. */ + } + /* ATM cache only peeks for qry->sname and that would be useless + * to repeat on every iteration, so disable it from now on. + * LATER(optim.): assist with more precise QNAME minimization. */ + qry->flags.CACHE_TRIED = true; + + if (qry->stype == KNOT_RRTYPE_NSEC) { + VERBOSE_MSG(qry, "=> skipping stype NSEC\n"); + return ctx->state; + } + if (!check_dname_for_lf(qry->sname, qry)) { + return ctx->state; + } + + int ret = peek_nosync(ctx, pkt); + kr_cache_sync(&req->ctx->cache); + return ret; +} + + + +/** It's simply inside of cycle taken out to decrease indentation. \return error code. */ +static int stash_rrarray_entry(ranked_rr_array_t *arr, int arr_i, + const struct kr_query *qry, struct kr_cache *cache, + int *unauth_cnt, trie_t *nsec_pmap, bool *has_optout); +/** Stash a single nsec_p. \return 0 (errors are ignored). */ +static int stash_nsec_p(const knot_dname_t *dname, const char *nsec_p_v, + struct kr_request *req); + +/** The whole .consume phase for the cache module. */ +int cache_stash(kr_layer_t *ctx, knot_pkt_t *pkt) +{ + struct kr_request *req = ctx->req; + struct kr_query *qry = req->current_query; + struct kr_cache *cache = &req->ctx->cache; + + /* Note: we cache even in KR_STATE_FAIL. For example, + * BOGUS answer can go to +cd cache even without +cd request. */ + if (!kr_cache_is_open(cache) || !qry + || qry->flags.CACHED || !check_rrtype(knot_pkt_qtype(pkt), qry) + || qry->sclass != KNOT_CLASS_IN) { + return ctx->state; + } + /* Do not cache truncated answers, at least for now. LATER */ + if (knot_wire_get_tc(pkt->wire)) { + return ctx->state; + } + /* Stash individual records. */ + ranked_rr_array_t *selected[] = kr_request_selected(req); + int unauth_cnt = 0; + trie_t *nsec_pmap = trie_create(&req->pool); + if (!nsec_pmap) { + assert(!ENOMEM); + goto finally; + } + bool has_optout = false; + /* ^^ DNSSEC_OPTOUT is not fired in cases like `com. A`, + * but currently we don't stash separate NSEC3 proving that. */ + for (int psec = KNOT_ANSWER; psec <= KNOT_ADDITIONAL; ++psec) { + ranked_rr_array_t *arr = selected[psec]; + /* uncached entries are located at the end */ + for (ssize_t i = arr->len - 1; i >= 0; --i) { + ranked_rr_array_entry_t *entry = arr->at[i]; + if (entry->qry_uid != qry->uid) { + continue; + /* TODO: probably safe to break but maybe not worth it */ + } + int ret = stash_rrarray_entry(arr, i, qry, cache, &unauth_cnt, + nsec_pmap, &has_optout); + if (ret) { + VERBOSE_MSG(qry, "=> stashing RRs errored out\n"); + goto finally; + } + /* LATER(optim.): maybe filter out some type-rank combinations + * that won't be useful as separate RRsets. */ + } + } + + trie_it_t *it; + for (it = trie_it_begin(nsec_pmap); !trie_it_finished(it); trie_it_next(it)) { + stash_nsec_p((const knot_dname_t *)trie_it_key(it, NULL), + (const char *)*trie_it_val(it), req); + } + trie_it_free(it); + /* LATER(optim.): typically we also have corresponding NS record in the list, + * so we might save a cache operation. */ + + stash_pkt(pkt, qry, req, has_optout); + +finally: + if (unauth_cnt) { + VERBOSE_MSG(qry, "=> stashed also %d nonauth RRsets\n", unauth_cnt); + }; + kr_cache_sync(cache); + return ctx->state; /* we ignore cache-stashing errors */ +} + +/** Preliminary checks before stash_rrset(). Don't call if returns <= 0. */ +static int stash_rrset_precond(const knot_rrset_t *rr, const struct kr_query *qry/*logs*/) +{ + if (!rr || rr->rclass != KNOT_CLASS_IN) { + assert(!EINVAL); + return kr_error(EINVAL); + } + if (!check_rrtype(rr->type, qry)) { + return kr_ok(); + } + if (!check_dname_for_lf(rr->owner, qry)) { + return kr_ok(); + } + return 1/*proceed*/; +} + +static ssize_t stash_rrset(struct kr_cache *cache, const struct kr_query *qry, + const knot_rrset_t *rr, const knot_rrset_t *rr_sigs, uint32_t timestamp, + uint8_t rank, trie_t *nsec_pmap, bool *has_optout) +{ + assert(stash_rrset_precond(rr, qry) > 0); + if (!cache) { + assert(!EINVAL); + return kr_error(EINVAL); + } + + const int wild_labels = rr_sigs == NULL ? 0 : + knot_dname_labels(rr->owner, NULL) - knot_rrsig_labels(rr_sigs->rrs.rdata); + if (wild_labels < 0) { + return kr_ok(); + } + const knot_dname_t *encloser = rr->owner; /**< the closest encloser name */ + for (int i = 0; i < wild_labels; ++i) { + encloser = knot_wire_next_label(encloser, NULL); + } + int ret = 0; + + /* Construct the key under which RRs will be stored, + * and add corresponding nsec_pmap item (if necessary). */ + struct key k_storage, *k = &k_storage; + knot_db_val_t key; + switch (rr->type) { + case KNOT_RRTYPE_NSEC3: + /* Skip "suspicious" or opt-out NSEC3 sets. */ + if (rr->rrs.count != 1) return kr_ok(); + if (KNOT_NSEC3_FLAG_OPT_OUT & knot_nsec3_flags(rr->rrs.rdata)) { + if (has_optout) *has_optout = true; + return kr_ok(); + } + /* fall through */ + case KNOT_RRTYPE_NSEC: + if (!kr_rank_test(rank, KR_RANK_SECURE)) { + /* Skip any NSEC*s that aren't validated. */ + return kr_ok(); + } + if (!rr_sigs || !rr_sigs->rrs.count || !rr_sigs->rrs.rdata) { + assert(!EINVAL); + return kr_error(EINVAL); + } + const knot_dname_t *signer = knot_rrsig_signer_name(rr_sigs->rrs.rdata); + const int signer_size = knot_dname_size(signer); + k->zlf_len = signer_size - 1; + + void **npp = nsec_pmap == NULL ? NULL + : trie_get_ins(nsec_pmap, (const char *)signer, signer_size); + assert(!nsec_pmap || (npp && ENOMEM)); + if (rr->type == KNOT_RRTYPE_NSEC) { + key = key_NSEC1(k, encloser, wild_labels); + break; + } + + assert(rr->type == KNOT_RRTYPE_NSEC3); + const knot_rdata_t * const rdata = rr->rrs.rdata; + if (rdata->len <= 4) return kr_error(EILSEQ); /*< data from outside; less trust */ + const int np_dlen = nsec_p_rdlen(rdata->data); + if (np_dlen > rdata->len) return kr_error(EILSEQ); + key = key_NSEC3(k, encloser, nsec_p_mkHash(rdata->data)); + if (npp && !*npp) { + *npp = mm_alloc(&qry->request->pool, np_dlen); + if (!*npp) { + assert(!ENOMEM); + break; + } + memcpy(*npp, rdata->data, np_dlen); + } + break; + default: + ret = kr_dname_lf(k->buf, encloser, wild_labels); + if (ret) { + assert(!ret); + return kr_error(ret); + } + key = key_exact_type(k, rr->type); + } + + /* Compute materialized sizes of the new data. */ + const knot_rdataset_t *rds_sigs = rr_sigs ? &rr_sigs->rrs : NULL; + const int rr_ssize = rdataset_dematerialize_size(&rr->rrs); + assert(rr_ssize == to_even(rr_ssize)); + knot_db_val_t val_new_entry = { + .data = NULL, + .len = offsetof(struct entry_h, data) + rr_ssize + + rdataset_dematerialize_size(rds_sigs), + }; + + /* Prepare raw memory for the new entry. */ + ret = entry_h_splice(&val_new_entry, rank, key, k->type, rr->type, + rr->owner, qry, cache, timestamp); + if (ret) return kr_ok(); /* some aren't really errors */ + assert(val_new_entry.data); + + const uint32_t ttl = rr->ttl; + /* FIXME: consider TTLs and expirations of RRSIGs as well, just in case. */ + + /* Write the entry itself. */ + struct entry_h *eh = val_new_entry.data; + memset(eh, 0, offsetof(struct entry_h, data)); + eh->time = timestamp; + eh->ttl = MAX(MIN(ttl, cache->ttl_max), cache->ttl_min); + eh->rank = rank; + if (rdataset_dematerialize(&rr->rrs, eh->data) + || rdataset_dematerialize(rds_sigs, eh->data + rr_ssize)) { + /* minimize the damage from incomplete write; TODO: better */ + eh->time = 0; + eh->ttl = 0; + eh->rank = 0; + assert(false); + } + assert(entry_h_consistent(val_new_entry, rr->type)); + + #if 0 /* Occasionally useful when debugging some kinds of changes. */ + { + kr_cache_sync(cache); + knot_db_val_t val = { NULL, 0 }; + ret = cache_op(cache, read, &key, &val, 1); + if (ret != kr_error(ENOENT)) { // ENOENT might happen in some edge case, I guess + assert(!ret); + entry_list_t el; + entry_list_parse(val, el); + } + } + #endif + + /* Update metrics */ + cache->stats.insert += 1; + + /* Verbose-log some not-too-common cases. */ + WITH_VERBOSE(qry) { if (kr_rank_test(rank, KR_RANK_AUTH) + || rr->type == KNOT_RRTYPE_NS) { + auto_free char *type_str = kr_rrtype_text(rr->type), + *encl_str = kr_dname_text(encloser); + VERBOSE_MSG(qry, "=> stashed %s%s %s, rank 0%.2o, " + "%d B total, incl. %d RRSIGs\n", + (wild_labels ? "*." : ""), encl_str, type_str, rank, + (int)val_new_entry.len, (rr_sigs ? rr_sigs->rrs.count : 0) + ); + } } + + return (ssize_t) val_new_entry.len; +} + +static int stash_rrarray_entry(ranked_rr_array_t *arr, int arr_i, + const struct kr_query *qry, struct kr_cache *cache, + int *unauth_cnt, trie_t *nsec_pmap, bool *has_optout) +{ + ranked_rr_array_entry_t *entry = arr->at[arr_i]; + if (entry->cached) { + return kr_ok(); + } + const knot_rrset_t *rr = entry->rr; + if (rr->type == KNOT_RRTYPE_RRSIG) { + return kr_ok(); /* reduce verbose logging from the following call */ + } + int ret = stash_rrset_precond(rr, qry); + if (ret <= 0) { + return ret; + } + + /* Try to find corresponding signatures, always. LATER(optim.): speed. */ + ranked_rr_array_entry_t *entry_rrsigs = NULL; + const knot_rrset_t *rr_sigs = NULL; + for (ssize_t j = arr->len - 1; j >= 0; --j) { + /* TODO: ATM we assume that some properties are the same + * for all RRSIGs in the set (esp. label count). */ + ranked_rr_array_entry_t *e = arr->at[j]; + bool ok = e->qry_uid == qry->uid && !e->cached + && e->rr->type == KNOT_RRTYPE_RRSIG + && knot_rrsig_type_covered(e->rr->rrs.rdata) == rr->type + && knot_dname_is_equal(rr->owner, e->rr->owner); + if (!ok) continue; + entry_rrsigs = e; + rr_sigs = e->rr; + break; + } + + ssize_t written = stash_rrset(cache, qry, rr, rr_sigs, qry->timestamp.tv_sec, + entry->rank, nsec_pmap, has_optout); + if (written < 0) { + kr_log_error("[%05u.%02u][cach] stash failed, ret = %d\n", qry->request->uid, + qry->uid, ret); + return (int) written; + } + + if (written > 0) { + /* Mark entry as cached for the rest of the query processing */ + entry->cached = true; + if (entry_rrsigs) { + entry_rrsigs->cached = true; + } + if (!kr_rank_test(entry->rank, KR_RANK_AUTH) && rr->type != KNOT_RRTYPE_NS) { + *unauth_cnt += 1; + } + } + + return kr_ok(); +} + +static int stash_nsec_p(const knot_dname_t *dname, const char *nsec_p_v, + struct kr_request *req) +{ + const struct kr_query *qry = req->current_query; + struct kr_cache *cache = &req->ctx->cache; + uint32_t valid_until = qry->timestamp.tv_sec + cache->ttl_max; + /* LATER(optim.): be more precise here ^^ and reduce calls. */ + static const int32_t ttl_margin = 3600; + const uint8_t *nsec_p = (const uint8_t *)nsec_p_v; + int data_stride = sizeof(valid_until) + nsec_p_rdlen(nsec_p); + + unsigned int log_hash = 0xFeeeFeee; /* this type is simpler for printf args */ + auto_free char *log_dname = NULL; + WITH_VERBOSE(qry) { + log_hash = nsec_p_v ? nsec_p_mkHash((const uint8_t *)nsec_p_v) : 0; + log_dname = kr_dname_text(dname); + } + /* Find what's in the cache. */ + struct key k_storage, *k = &k_storage; + int ret = kr_dname_lf(k->buf, dname, false); + if (ret) return kr_error(ret); + knot_db_val_t key = key_exact_type(k, KNOT_RRTYPE_NS); + knot_db_val_t val_orig = { NULL, 0 }; + ret = cache_op(cache, read, &key, &val_orig, 1); + if (ret && ret != -ABS(ENOENT)) { + VERBOSE_MSG(qry, "=> EL read failed (ret: %d)\n", ret); + return kr_ok(); + } + /* Prepare new entry_list_t so we can just write at el[0]. */ + entry_list_t el; + int log_refresh_by = 0; + if (ret == -ABS(ENOENT)) { + memset(el, 0, sizeof(el)); + } else { + ret = entry_list_parse(val_orig, el); + if (ret) { + VERBOSE_MSG(qry, "=> EL parse failed (ret: %d)\n", ret); + return kr_error(0); + } + /* Find the index to replace. */ + int i_replace = ENTRY_APEX_NSECS_CNT - 1; + for (int i = 0; i < ENTRY_APEX_NSECS_CNT; ++i) { + if (el[i].len != data_stride) continue; + if (nsec_p && memcmp(nsec_p, (uint8_t *)el[i].data + sizeof(uint32_t), + data_stride - sizeof(uint32_t)) != 0) { + continue; + } + /* Save a cache operation if TTL extended only a little. */ + uint32_t valid_orig; + memcpy(&valid_orig, el[i].data, sizeof(valid_orig)); + const int32_t ttl_extended_by = valid_until - valid_orig; + if (ttl_extended_by < ttl_margin) { + VERBOSE_MSG(qry, + "=> nsec_p stash for %s skipped (extra TTL: %d, hash: %x)\n", + log_dname, ttl_extended_by, log_hash); + return kr_ok(); + } + i_replace = i; + log_refresh_by = ttl_extended_by; + break; + } + /* Shift the other indices: move the first `i_replace` blocks + * by one position. */ + if (i_replace) { + memmove(&el[1], &el[0], sizeof(el[0]) * i_replace); + } + } + /* Prepare old data into a buffer. See entry_h_splice() for why. LATER(optim.) */ + el[0].len = data_stride; + el[0].data = NULL; + knot_db_val_t val; + val.len = entry_list_serial_size(el), + val.data = mm_alloc(&req->pool, val.len), + entry_list_memcpy(val.data, el); + /* Prepare the new data chunk */ + memcpy(el[0].data, &valid_until, sizeof(valid_until)); + if (nsec_p) { + memcpy((uint8_t *)el[0].data + sizeof(valid_until), nsec_p, + data_stride - sizeof(valid_until)); + } + /* Write it all to the cache */ + ret = cache_op(cache, write, &key, &val, 1); + if (ret || !val.data) { + VERBOSE_MSG(qry, "=> EL write failed (ret: %d)\n", ret); + return kr_ok(); + } + if (log_refresh_by) { + VERBOSE_MSG(qry, "=> nsec_p stashed for %s (refresh by %d, hash: %x)\n", + log_dname, log_refresh_by, log_hash); + } else { + VERBOSE_MSG(qry, "=> nsec_p stashed for %s (new, hash: %x)\n", + log_dname, log_hash); + } + return kr_ok(); +} + + +static int peek_exact_real(struct kr_cache *cache, const knot_dname_t *name, uint16_t type, + struct kr_cache_p *peek) +{ + if (!check_rrtype(type, NULL) || !check_dname_for_lf(name, NULL)) { + return kr_error(ENOTSUP); + } + struct key k_storage, *k = &k_storage; + + int ret = kr_dname_lf(k->buf, name, false); + if (ret) return kr_error(ret); + + knot_db_val_t key = key_exact_type(k, type); + knot_db_val_t val = { NULL, 0 }; + ret = cache_op(cache, read, &key, &val, 1); + if (!ret) ret = entry_h_seek(&val, type); + if (ret) return kr_error(ret); + + const struct entry_h *eh = entry_h_consistent(val, type); + if (!eh || eh->is_packet) { + // TODO: no packets, but better get rid of whole kr_cache_peek_exact(). + return kr_error(ENOENT); + } + *peek = (struct kr_cache_p){ + .time = eh->time, + .ttl = eh->ttl, + .rank = eh->rank, + .raw_data = val.data, + .raw_bound = knot_db_val_bound(val), + }; + return kr_ok(); +} +int kr_cache_peek_exact(struct kr_cache *cache, const knot_dname_t *name, uint16_t type, + struct kr_cache_p *peek) +{ /* Just wrap with extra verbose logging. */ + const int ret = peek_exact_real(cache, name, type, peek); + if (false && VERBOSE_STATUS) { /* too noisy for usual --verbose */ + auto_free char *type_str = kr_rrtype_text(type), + *name_str = kr_dname_text(name); + const char *result_str = (ret == kr_ok() ? "hit" : + (ret == kr_error(ENOENT) ? "miss" : "error")); + VERBOSE_MSG(NULL, "_peek_exact: %s %s %s (ret: %d)", + type_str, name_str, result_str, ret); + } + return ret; +} + +int kr_cache_remove(struct kr_cache *cache, const knot_dname_t *name, uint16_t type) +{ + if (!cache_isvalid(cache)) { + return kr_error(EINVAL); + } + if (!cache->api->remove) { + return kr_error(ENOSYS); + } + struct key k_storage, *k = &k_storage; + int ret = kr_dname_lf(k->buf, name, false); + if (ret) return kr_error(ret); + + knot_db_val_t key = key_exact_type(k, type); + return cache_op(cache, remove, &key, 1); +} + +int kr_cache_match(struct kr_cache *cache, const knot_dname_t *name, + bool exact_name, knot_db_val_t keyval[][2], int maxcount) +{ + if (!cache_isvalid(cache)) { + return kr_error(EINVAL); + } + if (!cache->api->match) { + return kr_error(ENOSYS); + } + + struct key k_storage, *k = &k_storage; + + int ret = kr_dname_lf(k->buf, name, false); + if (ret) return kr_error(ret); + + // use a mock type + knot_db_val_t key = key_exact_type(k, KNOT_RRTYPE_A); + /* CACHE_KEY_DEF */ + key.len -= sizeof(uint16_t); /* the type */ + if (!exact_name) { + key.len -= 2; /* '\0' 'E' */ + if (name[0] == '\0') ++key.len; /* the root name is special ATM */ + } + return cache_op(cache, match, &key, keyval, maxcount); +} + +int kr_unpack_cache_key(knot_db_val_t key, knot_dname_t *buf, uint16_t *type) +{ + if (key.data == NULL || buf == NULL || type == NULL) { + return kr_error(EINVAL); + } + + int len = -1; + const char *tag, *key_data = key.data; + for (tag = key_data + 1; tag < key_data + key.len; ++tag) { + /* CACHE_KEY_DEF */ + if (tag[-1] == '\0' && (tag == key_data + 1 || tag[-2] == '\0')) { + if (tag[0] != 'E') return kr_error(EINVAL); + len = tag - 1 - key_data; + break; + } + } + + if (len == -1 || len > KNOT_DNAME_MAXLEN) { + return kr_error(EINVAL); + } + + int ret = knot_dname_lf2wire(buf, len, key.data); + if (ret < 0) { + return kr_error(ret); + } + + /* CACHE_KEY_DEF: jump over "\0 E/1" */ + memcpy(type, tag + 1, sizeof(uint16_t)); + + return kr_ok(); +} + + +int kr_cache_remove_subtree(struct kr_cache *cache, const knot_dname_t *name, + bool exact_name, int maxcount) +{ + if (!cache_isvalid(cache)) { + return kr_error(EINVAL); + } + + knot_db_val_t keyval[maxcount][2], keys[maxcount]; + int ret = kr_cache_match(cache, name, exact_name, keyval, maxcount); + if (ret <= 0) { /* ENOENT -> nothing to remove */ + return (ret == KNOT_ENOENT) ? 0 : ret; + } + const int count = ret; + /* Duplicate the key strings, as deletion may invalidate the pointers. */ + int i; + for (i = 0; i < count; ++i) { + keys[i].len = keyval[i][0].len; + keys[i].data = malloc(keys[i].len); + if (!keys[i].data) { + ret = kr_error(ENOMEM); + goto cleanup; + } + memcpy(keys[i].data, keyval[i][0].data, keys[i].len); + } + ret = cache->api->remove(cache->db, keys, count); +cleanup: + kr_cache_sync(cache); /* Sync even after just kr_cache_match(). */ + /* Free keys */ + while (--i >= 0) { + free(keys[i].data); + } + return ret; +} + diff --git a/lib/cache/api.h b/lib/cache/api.h new file mode 100644 index 0000000..61bf796 --- /dev/null +++ b/lib/cache/api.h @@ -0,0 +1,201 @@ +/* Copyright (C) 2014-2017 CZ.NIC, z.s.p.o. <knot-dns@labs.nic.cz> + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <https://www.gnu.org/licenses/>. + */ + +#pragma once + +#include <libknot/consts.h> +#include <libknot/rrset.h> +#include <sys/time.h> +#include "lib/cache/cdb_api.h" +#include "lib/defines.h" +#include "contrib/ucw/config.h" /*uint*/ + +/** When knot_pkt is passed from cache without ->wire, this is the ->size. */ +static const size_t PKT_SIZE_NOWIRE = -1; + + +#include "lib/module.h" +/* Prototypes for the 'cache' module implementation. */ +int cache_peek(kr_layer_t *ctx, knot_pkt_t *pkt); +int cache_stash(kr_layer_t *ctx, knot_pkt_t *pkt); + + +/** + * Cache structure, keeps API, instance and metadata. + */ +struct kr_cache +{ + knot_db_t *db; /**< Storage instance */ + const struct kr_cdb_api *api; /**< Storage engine */ + struct { + uint32_t hit; /**< Number of cache hits */ + uint32_t miss; /**< Number of cache misses */ + uint32_t insert; /**< Number of insertions */ + uint32_t delete; /**< Number of deletions */ + } stats; + + uint32_t ttl_min, ttl_max; /**< TTL limits */ + + /* A pair of stamps for detection of real-time shifts during runtime. */ + struct timeval checkpoint_walltime; /**< Wall time on the last check-point. */ + uint64_t checkpoint_monotime; /**< Monotonic milliseconds on the last check-point. */ +}; + +/** + * Open/create cache with provided storage options. + * @param cache cache structure to be initialized + * @param api storage engine API + * @param opts storage-specific options (may be NULL for default) + * @param mm memory context. + * @return 0 or an error code + */ +KR_EXPORT +int kr_cache_open(struct kr_cache *cache, const struct kr_cdb_api *api, struct kr_cdb_opts *opts, knot_mm_t *mm); + +/** + * Path to cache file to remove on critical out-of-space error. (do NOT modify it) + */ +KR_EXPORT extern +const char *kr_cache_emergency_file_to_remove; + +/** + * Close persistent cache. + * @note This doesn't clear the data, just closes the connection to the database. + * @param cache structure + */ +KR_EXPORT +void kr_cache_close(struct kr_cache *cache); + +/** Run after a row of operations to release transaction/lock if needed. */ +KR_EXPORT +int kr_cache_sync(struct kr_cache *cache); + +/** + * Return true if cache is open and enabled. + */ +static inline bool kr_cache_is_open(struct kr_cache *cache) +{ + return cache->db != NULL; +} + +/** (Re)set the time pair to the current values. */ +static inline void kr_cache_make_checkpoint(struct kr_cache *cache) +{ + cache->checkpoint_monotime = kr_now(); + gettimeofday(&cache->checkpoint_walltime, NULL); +} + +/** + * Insert RRSet into cache, replacing any existing data. + * @param cache cache structure + * @param rr inserted RRSet + * @param rrsig RRSIG for inserted RRSet (optional) + * @param rank rank of the data + * @param timestamp current time + * @return 0 or an errcode + */ +KR_EXPORT +int kr_cache_insert_rr(struct kr_cache *cache, const knot_rrset_t *rr, const knot_rrset_t *rrsig, uint8_t rank, uint32_t timestamp); + +/** + * Clear all items from the cache. + * @param cache cache structure + * @return 0 or an errcode + */ +KR_EXPORT +int kr_cache_clear(struct kr_cache *cache); + + +/* ** This interface is temporary. ** */ + +struct kr_cache_p { + uint32_t time; /**< The time of inception. */ + uint32_t ttl; /**< TTL at inception moment. Assuming it fits into int32_t ATM. */ + uint8_t rank; /**< See enum kr_rank */ + struct { + /* internal: pointer to eh struct */ + void *raw_data, *raw_bound; + }; +}; +KR_EXPORT +int kr_cache_peek_exact(struct kr_cache *cache, const knot_dname_t *name, uint16_t type, + struct kr_cache_p *peek); +/* Parameters (qry, name, type) are used for timestamp and stale-serving decisions. */ +KR_EXPORT +int32_t kr_cache_ttl(const struct kr_cache_p *peek, const struct kr_query *qry, + const knot_dname_t *name, uint16_t type); + +KR_EXPORT +int kr_cache_materialize(knot_rdataset_t *dst, const struct kr_cache_p *ref, + knot_mm_t *pool); + + +/** + * Remove an entry from cache. + * @param cache cache structure + * @param name dname + * @param type rr type + * @return number of deleted records, or negative error code + * @note only "exact hits" are considered ATM, and + * some other information may be removed alongside. + */ +KR_EXPORT +int kr_cache_remove(struct kr_cache *cache, const knot_dname_t *name, uint16_t type); + +/** + * Get keys matching a dname lf prefix + * @param cache cache structure + * @param name dname + * @param exact_name whether to only consider exact name matches + * @param keyval matched key-value pairs + * @param maxcount limit on the number of returned key-value pairs + * @return result count or an errcode + * @note the cache keys are matched by prefix, i.e. it very much depends + * on their structure; CACHE_KEY_DEF. + */ +KR_EXPORT +int kr_cache_match(struct kr_cache *cache, const knot_dname_t *name, + bool exact_name, knot_db_val_t keyval[][2], int maxcount); + +/** + * Remove a subtree in cache. It's like _match but removing them instead of returning. + * @return number of deleted entries or an errcode + */ +KR_EXPORT +int kr_cache_remove_subtree(struct kr_cache *cache, const knot_dname_t *name, + bool exact_name, int maxcount); + +/** + * Find the closest cached zone apex for a name (in cache). + * @param is_DS start searching one name higher + * @return the number of labels to remove from the name, or negative error code + * @note timestamp is found by a syscall, and stale-serving is not considered + */ +KR_EXPORT +int kr_cache_closest_apex(struct kr_cache *cache, const knot_dname_t *name, bool is_DS, + knot_dname_t **apex); + +/** + * Unpack dname and type from db key + * @param key db key representation + * @param buf output buffer of domain name in dname format + * @param type output for type + * @return length of dname or an errcode + * @note only "exact hits" are considered ATM, moreover xNAME records + * are "hidden" as NS. (see comments in struct entry_h) + */ +KR_EXPORT +int kr_unpack_cache_key(knot_db_val_t key, knot_dname_t *buf, uint16_t *type); diff --git a/lib/cache/cdb_api.h b/lib/cache/cdb_api.h new file mode 100644 index 0000000..814a5f5 --- /dev/null +++ b/lib/cache/cdb_api.h @@ -0,0 +1,68 @@ +/* Copyright (C) 2016-2017 CZ.NIC, z.s.p.o. <knot-dns@labs.nic.cz> + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <https://www.gnu.org/licenses/>. +*/ + +#pragma once + +#include <libknot/db/db.h> + +/* Cache options. */ +struct kr_cdb_opts { + const char *path; /*!< Cache URI path. */ + size_t maxsize; /*!< Suggested cache size in bytes. */ +}; + +/*! Cache database API. + * This is a simplified version of generic DB API from libknot, + * that is tailored to caching purposes. + */ +struct kr_cdb_api { + const char *name; + + /* Context operations */ + + int (*open)(knot_db_t **db, struct kr_cdb_opts *opts, knot_mm_t *mm); + void (*close)(knot_db_t *db); + int (*count)(knot_db_t *db); + int (*clear)(knot_db_t *db); + + /** Run after a row of operations to release transaction/lock if needed. */ + int (*sync)(knot_db_t *db); + + /* Data access */ + + int (*read)(knot_db_t *db, const knot_db_val_t *key, knot_db_val_t *val, + int maxcount); + int (*write)(knot_db_t *db, const knot_db_val_t *key, knot_db_val_t *val, + int maxcount); + + /** Remove maxcount keys. + * \returns the number of succesfully removed keys or the first error code + * It returns on first error, but ENOENT is not considered an error. */ + int (*remove)(knot_db_t *db, knot_db_val_t keys[], int maxcount); + + /* Specialised operations */ + + /** Find key-value pairs that are prefixed by the given key, limited by maxcount. + * \return the number of pairs or negative error. */ + int (*match)(knot_db_t *db, knot_db_val_t *key, knot_db_val_t keyval[][2], int maxcount); + /** Not implemented ATM. */ + int (*prune)(knot_db_t *db, int maxcount); + + /** Less-or-equal search (lexicographic ordering). + * On successful return, key->data and val->data point to DB-owned data. + * return: 0 for equality, > 0 for less, < 0 kr_error */ + int (*read_leq)(knot_db_t *db, knot_db_val_t *key, knot_db_val_t *val); +}; diff --git a/lib/cache/cdb_lmdb.c b/lib/cache/cdb_lmdb.c new file mode 100644 index 0000000..621d2e8 --- /dev/null +++ b/lib/cache/cdb_lmdb.c @@ -0,0 +1,710 @@ +/* Copyright (C) 2016-2017 CZ.NIC, z.s.p.o. <knot-dns@labs.nic.cz> + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <https://www.gnu.org/licenses/>. +*/ + +#include <assert.h> +#include <fcntl.h> +#include <stdbool.h> +#include <stdlib.h> +#include <string.h> +#include <sys/stat.h> +#include <sys/types.h> +#include <unistd.h> +#include <lmdb.h> + +#include "contrib/cleanup.h" +#include "lib/cache/cdb_lmdb.h" +#include "lib/cache/api.h" +#include "lib/utils.h" + + +/* Defines */ +#define LMDB_DIR_MODE 0770 +#define LMDB_FILE_MODE 0660 + +struct lmdb_env +{ + size_t mapsize; + MDB_dbi dbi; + MDB_env *env; + + /** Cached transactions + * + * - only one of (ro,rw) may be active at once + * - non-NULL .ro may be active or reset + * - non-NULL .rw is always active + */ + struct { + bool ro_active, ro_curs_active; + MDB_txn *ro, *rw; + MDB_cursor *ro_curs; + } txn; +}; + +/** @brief Convert LMDB error code. */ +static int lmdb_error(int error) +{ + /* _BAD_TXN may happen with overfull DB, + * even during mdb_get with a single fork :-/ */ + if (error == MDB_BAD_TXN) { + kr_log_info("[cache] MDB_BAD_TXN, probably overfull\n"); + error = ENOSPC; + } + switch (error) { + case MDB_SUCCESS: + return kr_ok(); + case MDB_NOTFOUND: + return kr_error(ENOENT); + case ENOSPC: + case MDB_MAP_FULL: + case MDB_TXN_FULL: + return kr_error(ENOSPC); + default: + kr_log_error("[cache] LMDB error: %s\n", mdb_strerror(error)); + return kr_error(error); + } +} + +/** Conversion between knot and lmdb structs for values. */ +static inline knot_db_val_t val_mdb2knot(MDB_val v) +{ + return (knot_db_val_t){ .len = v.mv_size, .data = v.mv_data }; +} +static inline MDB_val val_knot2mdb(knot_db_val_t v) +{ + return (MDB_val){ .mv_size = v.len, .mv_data = v.data }; +} + + +/*! \brief Set the environment map size. + * \note This also sets the maximum database size, see \fn mdb_env_set_mapsize + */ +static int set_mapsize(MDB_env *env, size_t map_size) +{ + long page_size = sysconf(_SC_PAGESIZE); + if (page_size <= 0) { + return KNOT_ERROR; + } + + /* Round to page size. */ + map_size = (map_size / page_size) * page_size; + int ret = mdb_env_set_mapsize(env, map_size); + if (ret != MDB_SUCCESS) { + return lmdb_error(ret); + } + + return 0; +} + +#define FLAG_RENEW (2*MDB_RDONLY) +/** mdb_txn_begin or _renew + handle MDB_MAP_RESIZED. + * + * The retrying logic for MDB_MAP_RESIZED is so ugly that it has its own function. + * \note this assumes no transactions are active + * \return MDB_ errcode, not usual kr_error(...) + */ +static int txn_get_noresize(struct lmdb_env *env, unsigned int flag, MDB_txn **txn) +{ + assert(!env->txn.rw && (!env->txn.ro || !env->txn.ro_active)); + int ret; + if (flag == FLAG_RENEW) { + ret = mdb_txn_renew(*txn); + } else { + ret = mdb_txn_begin(env->env, NULL, flag, txn); + } + if (ret != MDB_MAP_RESIZED) { + return ret; + } + //:unlikely + /* Another process increased the size; let's try to recover. */ + kr_log_info("[cache] detected size increased by another process\n"); + ret = mdb_env_set_mapsize(env->env, 0); + if (ret != MDB_SUCCESS) { + return ret; + } + if (flag == FLAG_RENEW) { + ret = mdb_txn_renew(*txn); + } else { + ret = mdb_txn_begin(env->env, NULL, flag, txn); + } + return ret; +} + +/** Obtain a transaction. (they're cached in env->txn) */ +static int txn_get(struct lmdb_env *env, MDB_txn **txn, bool rdonly) +{ + assert(env && txn); + if (env->txn.rw) { + /* Reuse the *open* RW txn even if only reading is requested. + * We leave the management of this to the cdb_sync command. + * The user may e.g. want to do some reads between the writes. */ + *txn = env->txn.rw; + return kr_ok(); + } + + if (!rdonly) { + /* avoid two active transactions */ + if (env->txn.ro && env->txn.ro_active) { + mdb_txn_reset(env->txn.ro); + env->txn.ro_active = false; + env->txn.ro_curs_active = false; + } + int ret = txn_get_noresize(env, 0/*RW*/, &env->txn.rw); + if (ret == MDB_SUCCESS) { + *txn = env->txn.rw; + assert(*txn); + } + return lmdb_error(ret); + } + + /* Get an active RO txn and return it. */ + int ret = MDB_SUCCESS; + if (!env->txn.ro) { //:unlikely + ret = txn_get_noresize(env, MDB_RDONLY, &env->txn.ro); + } else if (!env->txn.ro_active) { + ret = txn_get_noresize(env, FLAG_RENEW, &env->txn.ro); + } + if (ret != MDB_SUCCESS) { + return lmdb_error(ret); + } + env->txn.ro_active = true; + *txn = env->txn.ro; + assert(*txn); + return kr_ok(); +} + +static int cdb_sync(knot_db_t *db) +{ + struct lmdb_env *env = db; + int ret = kr_ok(); + if (env->txn.rw) { + ret = lmdb_error(mdb_txn_commit(env->txn.rw)); + env->txn.rw = NULL; /* the transaction got freed even in case of errors */ + } else if (env->txn.ro && env->txn.ro_active) { + mdb_txn_reset(env->txn.ro); + env->txn.ro_active = false; + env->txn.ro_curs_active = false; + } + return ret; +} + +/** Obtain a read-only cursor (and a read-only transaction). */ +static int txn_curs_get(struct lmdb_env *env, MDB_cursor **curs) +{ + assert(env && curs); + if (env->txn.ro_curs_active) { + goto success; + } + /* Only in a read-only txn; TODO: it's a bit messy/coupled */ + if (env->txn.rw) { + int ret = cdb_sync(env); + if (ret) return ret; + } + MDB_txn *txn = NULL; + int ret = txn_get(env, &txn, true); + if (ret) return ret; + + if (env->txn.ro_curs) { + ret = mdb_cursor_renew(txn, env->txn.ro_curs); + } else { + ret = mdb_cursor_open(txn, env->dbi, &env->txn.ro_curs); + } + if (ret) return ret; + env->txn.ro_curs_active = true; +success: + assert(env->txn.ro_curs_active && env->txn.ro && env->txn.ro_active + && !env->txn.rw); + *curs = env->txn.ro_curs; + assert(*curs); + return kr_ok(); +} + +static void free_txn_ro(struct lmdb_env *env) +{ + if (env->txn.ro) { + mdb_txn_abort(env->txn.ro); + env->txn.ro = NULL; + } + if (env->txn.ro_curs) { + mdb_cursor_close(env->txn.ro_curs); + env->txn.ro_curs = NULL; + } +} + +/*! \brief Close the database. */ +static void cdb_close_env(struct lmdb_env *env) +{ + assert(env && env->env); + + /* Get rid of any transactions. */ + cdb_sync(env); + free_txn_ro(env); + + mdb_env_sync(env->env, 1); + mdb_dbi_close(env->env, env->dbi); + mdb_env_close(env->env); + memset(env, 0, sizeof(*env)); +} + +/*! \brief Open database environment. */ +static int cdb_open_env(struct lmdb_env *env, unsigned flags, const char *path, size_t mapsize) +{ + int ret = mkdir(path, LMDB_DIR_MODE); + if (ret == -1 && errno != EEXIST) { + return kr_error(errno); + } + + MDB_env *mdb_env = NULL; + ret = mdb_env_create(&mdb_env); + if (ret != MDB_SUCCESS) { + return lmdb_error(ret); + } + + ret = set_mapsize(mdb_env, mapsize); + if (ret != 0) { + mdb_env_close(mdb_env); + return ret; + } + + ret = mdb_env_open(mdb_env, path, flags, LMDB_FILE_MODE); + if (ret != MDB_SUCCESS) { + mdb_env_close(mdb_env); + return lmdb_error(ret); + } + + /* Keep the environment pointer. */ + env->env = mdb_env; + env->mapsize = mapsize; + return 0; +} + +static int cdb_open(struct lmdb_env *env, const char *path, size_t mapsize) +{ + /* Cache doesn't require durability, we can be + * loose with the requirements as a tradeoff for speed. */ + const unsigned flags = MDB_WRITEMAP | MDB_MAPASYNC | MDB_NOTLS; + int ret = cdb_open_env(env, flags, path, mapsize); + if (ret != 0) { + return ret; + } + + /* Open the database. */ + MDB_txn *txn = NULL; + ret = mdb_txn_begin(env->env, NULL, 0, &txn); + if (ret != MDB_SUCCESS) { + mdb_env_close(env->env); + return lmdb_error(ret); + } + + ret = mdb_dbi_open(txn, NULL, 0, &env->dbi); + if (ret != MDB_SUCCESS) { + mdb_txn_abort(txn); + mdb_env_close(env->env); + return lmdb_error(ret); + } + + ret = mdb_txn_commit(txn); + if (ret != MDB_SUCCESS) { + mdb_env_close(env->env); + return lmdb_error(ret); + } + + return 0; +} + +static int cdb_init(knot_db_t **db, struct kr_cdb_opts *opts, knot_mm_t *pool) +{ + if (!db || !opts) { + return kr_error(EINVAL); + } + + struct lmdb_env *env = malloc(sizeof(*env)); + if (!env) { + return kr_error(ENOMEM); + } + memset(env, 0, sizeof(struct lmdb_env)); + + /* Clear stale lockfiles. */ + auto_free char *lockfile = kr_strcatdup(2, opts->path, "/.cachelock"); + if (lockfile) { + if (unlink(lockfile) == 0) { + kr_log_info("[cache] cleared stale lockfile '%s'\n", lockfile); + } else if (errno != ENOENT) { + kr_log_info("[cache] failed to clear stale lockfile '%s': %s\n", lockfile, + strerror(errno)); + } + } + + /* Open the database. */ + int ret = cdb_open(env, opts->path, opts->maxsize); + if (ret != 0) { + free(env); + return ret; + } + + *db = env; + return 0; +} + +static void cdb_deinit(knot_db_t *db) +{ + struct lmdb_env *env = db; + cdb_close_env(env); + free(env); +} + +static int cdb_count(knot_db_t *db) +{ + struct lmdb_env *env = db; + MDB_txn *txn = NULL; + int ret = txn_get(env, &txn, true); + if (ret != 0) { + return ret; + } + + MDB_stat stat; + ret = mdb_stat(txn, env->dbi, &stat); + + return (ret == MDB_SUCCESS) ? stat.ms_entries : lmdb_error(ret); +} + +static int cdb_clear(knot_db_t *db) +{ + struct lmdb_env *env = db; + /* First try mdb_drop() to clear the DB; this may fail with ENOSPC. */ + /* If we didn't do this, explicit cache.clear() ran on an instance + * would lead to the instance detaching from the cache of others, + * until they reopened cache explicitly or cleared it for some reason. + */ + { + MDB_txn *txn = NULL; + int ret = txn_get(env, &txn, false); + if (ret == kr_ok()) { + ret = lmdb_error(mdb_drop(txn, env->dbi, 0)); + if (ret == kr_ok()) { + ret = cdb_sync(db); + } + if (ret == kr_ok()) { + return ret; + } + } + kr_log_info("[cache] clearing error, falling back\n"); + } + + /* We are about to switch to a different file, so end all txns, to be sure. */ + (void) cdb_sync(db); + free_txn_ro(db); + + /* Since there is no guarantee that there will be free + * pages to hold whole dirtied db for transaction-safe clear, + * we simply remove the database files and reopen. + * We can afford this since other readers will continue to read + * from removed file, but will reopen when encountering next + * error. */ + mdb_filehandle_t fd = -1; + int ret = mdb_env_get_fd(env->env, &fd); + if (ret != MDB_SUCCESS) { + return lmdb_error(ret); + } + const char *path = NULL; + ret = mdb_env_get_path(env->env, &path); + if (ret != MDB_SUCCESS) { + return lmdb_error(ret); + } + + auto_free char *mdb_datafile = kr_strcatdup(2, path, "/data.mdb"); + auto_free char *mdb_lockfile = kr_strcatdup(2, path, "/lock.mdb"); + auto_free char *lockfile = kr_strcatdup(2, path, "/.cachelock"); + if (!mdb_datafile || !mdb_lockfile || !lockfile) { + return kr_error(ENOMEM); + } + /* Find if we get a lock on lockfile. */ + ret = open(lockfile, O_CREAT|O_EXCL|O_RDONLY, S_IRUSR); + if (ret == -1) { + kr_log_error("[cache] clearing failed to get ./.cachelock; retry later\n"); + /* As we're out of space (almost certainly - mdb_drop didn't work), + * we will retry on the next failing write operation. */ + return kr_error(errno); + } + close(ret); + /* We acquired lockfile. Now find whether *.mdb are what we have open now. */ + struct stat old_stat, new_stat; + if (fstat(fd, &new_stat) || stat(mdb_datafile, &old_stat)) { + ret = errno; + unlink(lockfile); + return kr_error(ret); + } + /* Remove underlying files only if current open environment + * points to file on the disk. Otherwise just reopen as someone + * else has already removed the files. + */ + if (old_stat.st_dev == new_stat.st_dev && old_stat.st_ino == new_stat.st_ino) { + kr_log_verbose("[cache] clear: identical files, unlinking\n"); + // coverity[toctou] + unlink(mdb_datafile); + unlink(mdb_lockfile); + } else + kr_log_verbose("[cache] clear: not identical files, reopening\n"); + /* Keep copy as it points to current handle internals. */ + auto_free char *path_copy = strdup(path); + size_t mapsize = env->mapsize; + cdb_close_env(env); + ret = cdb_open(env, path_copy, mapsize); + /* Environment updated, release lockfile. */ + unlink(lockfile); + return ret; +} + +static int cdb_readv(knot_db_t *db, const knot_db_val_t *key, knot_db_val_t *val, + int maxcount) +{ + struct lmdb_env *env = db; + MDB_txn *txn = NULL; + int ret = txn_get(env, &txn, true); + if (ret) { + return ret; + } + + for (int i = 0; i < maxcount; ++i) { + /* Convert key structs */ + MDB_val _key = val_knot2mdb(key[i]); + MDB_val _val = val_knot2mdb(val[i]); + ret = mdb_get(txn, env->dbi, &_key, &_val); + if (ret != MDB_SUCCESS) { + ret = lmdb_error(ret); + if (ret == kr_error(ENOSPC)) { + /* we're likely to be forced to cache clear anyway */ + ret = kr_error(ENOENT); + } + return ret; + } + /* Update the result. */ + val[i] = val_mdb2knot(_val); + } + return kr_ok(); +} + +static int cdb_write(struct lmdb_env *env, MDB_txn **txn, const knot_db_val_t *key, + knot_db_val_t *val, unsigned flags) +{ + /* Convert key structs and write */ + MDB_val _key = val_knot2mdb(*key); + MDB_val _val = val_knot2mdb(*val); + int ret = mdb_put(*txn, env->dbi, &_key, &_val, flags); + + /* Try to recover from doing too much writing in a single transaction. */ + if (ret == MDB_TXN_FULL) { + ret = cdb_sync(env); + if (ret) { + ret = txn_get(env, txn, false); + } + if (ret) { + ret = mdb_put(*txn, env->dbi, &_key, &_val, flags); + } + } + if (ret != MDB_SUCCESS) { + return lmdb_error(ret); + } + + /* Update the result. */ + val->data = _val.mv_data; + val->len = _val.mv_size; + return kr_ok(); +} + +static int cdb_writev(knot_db_t *db, const knot_db_val_t *key, knot_db_val_t *val, + int maxcount) +{ + struct lmdb_env *env = db; + MDB_txn *txn = NULL; + int ret = txn_get(env, &txn, false); + + for (int i = 0; ret == kr_ok() && i < maxcount; ++i) { + /* This is LMDB specific optimisation, + * if caller specifies value with NULL data and non-zero length, + * LMDB will preallocate the entry for caller and leave write + * transaction open, caller is responsible for syncing thus committing transaction. + */ + unsigned mdb_flags = 0; + if (val[i].len > 0 && val[i].data == NULL) { + mdb_flags |= MDB_RESERVE; + } + ret = cdb_write(env, &txn, &key[i], &val[i], mdb_flags); + } + + return ret; +} + +static int cdb_remove(knot_db_t *db, knot_db_val_t keys[], int maxcount) +{ + struct lmdb_env *env = db; + MDB_txn *txn = NULL; + int ret = txn_get(env, &txn, false); + int deleted = 0; + + for (int i = 0; ret == kr_ok() && i < maxcount; ++i) { + MDB_val _key = val_knot2mdb(keys[i]); + MDB_val val = { 0, NULL }; + ret = lmdb_error(mdb_del(txn, env->dbi, &_key, &val)); + if (ret == kr_ok()) + deleted++; + else if (ret == KNOT_ENOENT) + ret = kr_ok(); /* skip over non-existing entries */ + } + + return ret < 0 ? ret : deleted; +} + +static int cdb_match(knot_db_t *db, knot_db_val_t *key, knot_db_val_t keyval[][2], int maxcount) +{ + struct lmdb_env *env = db; + MDB_txn *txn = NULL; + int ret = txn_get(env, &txn, true); + if (ret != 0) { + return ret; + } + + /* LATER(optim.): use txn_curs_get() instead, to save resources. */ + MDB_cursor *cur = NULL; + ret = mdb_cursor_open(txn, env->dbi, &cur); + if (ret != 0) { + return lmdb_error(ret); + } + + MDB_val cur_key = val_knot2mdb(*key); + MDB_val cur_val = { 0, NULL }; + ret = mdb_cursor_get(cur, &cur_key, &cur_val, MDB_SET_RANGE); + if (ret != MDB_SUCCESS) { + mdb_cursor_close(cur); + return lmdb_error(ret); + } + + int results = 0; + while (ret == MDB_SUCCESS) { + /* Retrieve current key and compare with prefix */ + if (cur_key.mv_size < key->len || memcmp(cur_key.mv_data, key->data, key->len) != 0) { + break; + } + /* Add to result set */ + if (results < maxcount) { + keyval[results][0] = val_mdb2knot(cur_key); + keyval[results][1] = val_mdb2knot(cur_val); + ++results; + } else { + break; + } + ret = mdb_cursor_get(cur, &cur_key, &cur_val, MDB_NEXT); + } + + mdb_cursor_close(cur); + return results; +} + + +static int cdb_prune(knot_db_t *db, int limit) +{ + return -1; +#if 0 + /* Sync in-flight transactions */ + cdb_sync(db); + + /* Prune old records */ + struct lmdb_env *env = db; + MDB_txn *txn = NULL; + int ret = txn_get(env, &txn, false); + if (ret != 0) { + return ret; + } + + MDB_cursor *cur = NULL; + ret = mdb_cursor_open(txn, env->dbi, &cur); + if (ret != 0) { + return lmdb_error(ret); + } + + MDB_val cur_key, cur_val; + ret = mdb_cursor_get(cur, &cur_key, &cur_val, MDB_FIRST); + if (ret != 0) { + mdb_cursor_close(cur); + return lmdb_error(ret); + } + + int results = 0; + struct timeval now; + gettimeofday(&now, NULL); + while (ret == 0 && results < limit) { + /* Ignore special namespaces. */ + if (cur_key.mv_size < 2 || ((const char *)cur_key.mv_data)[0] == 'V') { + ret = mdb_cursor_get(cur, &cur_key, &cur_val, MDB_NEXT); + continue; + } + /* Check entry age. */ + struct kr_cache_entry *entry = cur_val.mv_data; + if (entry->timestamp > now.tv_sec || + (now.tv_sec - entry->timestamp) < entry->ttl) { + ret = mdb_cursor_get(cur, &cur_key, &cur_val, MDB_NEXT); + continue; + } + /* Remove entry */ + mdb_cursor_del(cur, 0); + ++results; + ret = mdb_cursor_get(cur, &cur_key, &cur_val, MDB_NEXT); + } + mdb_cursor_close(cur); + return ret < 0 ? ret : results; +#endif +} + +static int cdb_read_leq(knot_db_t *env, knot_db_val_t *key, knot_db_val_t *val) +{ + assert(env && key && key->data && val); + MDB_cursor *curs = NULL; + int ret = txn_curs_get(env, &curs); + if (ret) return ret; + + MDB_val key2_m = val_knot2mdb(*key); + MDB_val val2_m = { 0, NULL }; + ret = mdb_cursor_get(curs, &key2_m, &val2_m, MDB_SET_RANGE); + if (ret) return lmdb_error(ret); + /* test for equality //:unlikely */ + if (key2_m.mv_size == key->len + && memcmp(key2_m.mv_data, key->data, key->len) == 0) { + ret = 0; /* equality */ + goto success; + } + /* we must be greater than key; do one step to smaller */ + ret = mdb_cursor_get(curs, &key2_m, &val2_m, MDB_PREV); + if (ret) return lmdb_error(ret); + ret = 1; +success: + /* finalize the output */ + *key = val_mdb2knot(key2_m); + *val = val_mdb2knot(val2_m); + return ret; +} + + +const struct kr_cdb_api *kr_cdb_lmdb(void) +{ + static const struct kr_cdb_api api = { + "lmdb", + cdb_init, cdb_deinit, cdb_count, cdb_clear, cdb_sync, + cdb_readv, cdb_writev, cdb_remove, + cdb_match, cdb_prune, + cdb_read_leq + }; + + return &api; +} diff --git a/lib/cache/cdb_lmdb.h b/lib/cache/cdb_lmdb.h new file mode 100644 index 0000000..bc2c7d6 --- /dev/null +++ b/lib/cache/cdb_lmdb.h @@ -0,0 +1,23 @@ +/* Copyright (C) 2016-2017 CZ.NIC, z.s.p.o. <knot-dns@labs.nic.cz> + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <https://www.gnu.org/licenses/>. +*/ + +#pragma once + +#include "lib/cache/cdb_api.h" +#include "lib/defines.h" + +KR_EXPORT KR_CONST +const struct kr_cdb_api *kr_cdb_lmdb(void); diff --git a/lib/cache/entry_list.c b/lib/cache/entry_list.c new file mode 100644 index 0000000..6a5001c --- /dev/null +++ b/lib/cache/entry_list.c @@ -0,0 +1,293 @@ +/* Copyright (C) 2017 CZ.NIC, z.s.p.o. <knot-dns@labs.nic.cz> + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <https://www.gnu.org/licenses/>. + */ + +/** @file + * Implementation of chaining in struct entry_h. Prototypes in ./impl.h + */ + +#include "lib/cache/impl.h" +#include "lib/utils.h" + + +static int entry_h_len(knot_db_val_t val); + + +void entry_list_memcpy(struct entry_apex *ea, entry_list_t list) +{ + assert(ea); + memset(ea, 0, offsetof(struct entry_apex, data)); + ea->has_ns = list[EL_NS ].len; + ea->has_cname = list[EL_CNAME ].len; + ea->has_dname = list[EL_DNAME ].len; + for (int i = 0; i < ENTRY_APEX_NSECS_CNT; ++i) { + ea->nsecs[i] = list[i].len == 0 ? 0 : + (list[i].len == 4 ? 1 : 3); + } + uint8_t *it = ea->data; + for (int i = 0; i < EL_LENGTH; ++i) { + if (list[i].data) { + memcpy(it, list[i].data, list[i].len); + /* LATER(optim.): coalesce consecutive writes? */ + } else { + list[i].data = it; + } + it += to_even(list[i].len); + } +} + +int entry_list_parse(const knot_db_val_t val, entry_list_t list) +{ + const bool ok = val.data && val.len && list; + if (!ok) { + assert(!EINVAL); + return kr_error(EINVAL); + } + /* Parse the apex itself (nsec parameters). */ + const struct entry_apex *ea = entry_apex_consistent(val); + if (!ea) { + return kr_error(EILSEQ); + } + const uint8_t *it = ea->data, + *it_bound = knot_db_val_bound(val); + for (int i = 0; i < ENTRY_APEX_NSECS_CNT; ++i) { + if (it > it_bound) { + return kr_error(EILSEQ); + } + list[i].data = (void *)it; + switch (ea->nsecs[i]) { + case 0: + list[i].len = 0; + break; + case 1: + list[i].len = sizeof(uint32_t); /* just timestamp */ + break; + case 3: { /* timestamp + NSEC3PARAM wire */ + if (it + sizeof(uint32_t) + 4 > it_bound) { + return kr_error(EILSEQ); + } + list[i].len = sizeof(uint32_t) + + nsec_p_rdlen(it + sizeof(uint32_t)); + break; + } + default: + return kr_error(EILSEQ); + }; + it += to_even(list[i].len); + } + /* Parse every entry_h. */ + for (int i = ENTRY_APEX_NSECS_CNT; i < EL_LENGTH; ++i) { + list[i].data = (void *)it; + bool has_type; + switch (i) { + case EL_NS: has_type = ea->has_ns; break; + case EL_CNAME: has_type = ea->has_cname; break; + case EL_DNAME: has_type = ea->has_dname; break; + default: assert(false); return kr_error(EINVAL); /* something very bad */ + } + if (!has_type) { + list[i].len = 0; + continue; + } + if (it >= it_bound) { + assert(!EILSEQ); + return kr_error(EILSEQ); + } + const int len = entry_h_len( + (knot_db_val_t){ .data = (void *)it, .len = it_bound - it }); + if (len < 0) { + assert(false); + return kr_error(len); + } + list[i].len = len; + it += to_even(len); + } + assert(it == it_bound); + return kr_ok(); +} + +/** Given a valid entry header, find its length (i.e. offset of the next entry). + * \param val The beginning of the data and the bound (read only). + */ +static int entry_h_len(const knot_db_val_t val) +{ + const bool ok = val.data && ((ssize_t)val.len) > 0; + if (!ok) return kr_error(EINVAL); + const struct entry_h *eh = val.data; + const uint8_t *d = eh->data; /* iterates over the data in entry */ + const uint8_t *data_bound = knot_db_val_bound(val); + if (d >= data_bound) return kr_error(EILSEQ); + if (!eh->is_packet) { /* Positive RRset + its RRsig set (may be empty). */ + int sets = 2; + while (sets-- > 0) { + d += rdataset_dematerialized_size(d); + if (d > data_bound) { + assert(!EILSEQ); + return kr_error(EILSEQ); + } + } + } else { /* A "packet" (opaque ATM). */ + uint16_t len; + if (d + sizeof(len) > data_bound) return kr_error(EILSEQ); + memcpy(&len, d, sizeof(len)); + d += 2 + to_even(len); + } + if (d > data_bound) { + assert(!EILSEQ); + return kr_error(EILSEQ); + } + return d - (uint8_t *)val.data; +} + +struct entry_apex * entry_apex_consistent(knot_db_val_t val) +{ + //XXX: check lengths, etc. + return val.data; +} + +/* See the header file. */ +int entry_h_seek(knot_db_val_t *val, uint16_t type) +{ + int i = -1; + switch (type) { + case KNOT_RRTYPE_NS: i = EL_NS; break; + case KNOT_RRTYPE_CNAME: i = EL_CNAME; break; + case KNOT_RRTYPE_DNAME: i = EL_DNAME; break; + default: return kr_ok(); + } + + entry_list_t el; + int ret = entry_list_parse(*val, el); + if (ret) return ret; + *val = el[i]; + return val->len ? kr_ok() : kr_error(ENOENT); +} + +static int cache_write_or_clear(struct kr_cache *cache, const knot_db_val_t *key, + knot_db_val_t *val, const struct kr_query *qry) +{ + int ret = cache_op(cache, write, key, val, 1); + if (!ret) return kr_ok(); + /* Clear cache if overfull. It's nontrivial to do better with LMDB. + * LATER: some garbage-collection mechanism. */ + if (ret == kr_error(ENOSPC)) { + ret = kr_cache_clear(cache); + const char *msg = "[cache] clearing because overfull, ret = %d\n"; + if (ret) { + kr_log_error(msg, ret); + } else { + kr_log_info(msg, ret); + ret = kr_error(ENOSPC); + } + return ret; + } + VERBOSE_MSG(qry, "=> failed backend write, ret = %d\n", ret); + return kr_error(ret ? ret : ENOSPC); +} + + +/* See the header file. */ +int entry_h_splice( + knot_db_val_t *val_new_entry, uint8_t rank, + const knot_db_val_t key, const uint16_t ktype, const uint16_t type, + const knot_dname_t *owner/*log only*/, + const struct kr_query *qry, struct kr_cache *cache, uint32_t timestamp) +{ + //TODO: another review, perhaps incuding the API + const bool ok = val_new_entry && val_new_entry->len > 0; + if (!ok) { + assert(!EINVAL); + return kr_error(EINVAL); + } + + int i_type; + switch (type) { + case KNOT_RRTYPE_NS: i_type = EL_NS; break; + case KNOT_RRTYPE_CNAME: i_type = EL_CNAME; break; + case KNOT_RRTYPE_DNAME: i_type = EL_DNAME; break; + default: i_type = 0; + } + + /* Get eh_orig (original entry), and also el list if multi-entry case. */ + const struct entry_h *eh_orig = NULL; + entry_list_t el; + int ret = -1; + if (!kr_rank_test(rank, KR_RANK_SECURE) || ktype == KNOT_RRTYPE_NS) { + knot_db_val_t val; + ret = cache_op(cache, read, &key, &val, 1); + if (i_type) { + if (!ret) ret = entry_list_parse(val, el); + if (ret) memset(el, 0, sizeof(el)); + val = el[i_type]; + } + /* val is on the entry, in either case (or error) */ + if (!ret) { + eh_orig = entry_h_consistent(val, type); + } + } else { + /* We want to fully overwrite the entry, so don't even read it. */ + memset(el, 0, sizeof(el)); + } + + if (!kr_rank_test(rank, KR_RANK_SECURE) && eh_orig) { + /* If equal rank was accepted, spoofing a *single* answer would be + * enough to e.g. override NS record in AUTHORITY section. + * This way they would have to hit the first answer + * (whenever TTL nears expiration). + * Stale-serving is NOT considered, but TTL 1 would be considered + * as expiring anyway, ... */ + int32_t old_ttl = get_new_ttl(eh_orig, qry, NULL, 0, timestamp); + if (old_ttl > 0 && !is_expiring(eh_orig->ttl, old_ttl) + && rank <= eh_orig->rank) { + WITH_VERBOSE(qry) { + auto_free char *type_str = kr_rrtype_text(type), + *owner_str = kr_dname_text(owner); + VERBOSE_MSG(qry, "=> not overwriting %s %s\n", + type_str, owner_str); + } + return kr_error(EEXIST); + } + } + + if (!i_type) { + /* The non-list types are trivial now. */ + return cache_write_or_clear(cache, &key, val_new_entry, qry); + } + /* Now we're in trouble. In some cases, parts of data to be written + * is an lmdb entry that may be invalidated by our write request. + * (lmdb does even in-place updates!) Therefore we copy all into a buffer. + * (We don't bother deallocating from the mempool.) + * LATER(optim.): do this only when neccessary, or perhaps another approach. + * This is also complicated by the fact that the val_new_entry part + * is to be written *afterwards* by the caller. + */ + el[i_type] = (knot_db_val_t){ + .len = val_new_entry->len, + .data = NULL, /* perhaps unclear in the entry_h_splice() API */ + }; + knot_db_val_t val = { + .len = entry_list_serial_size(el), + .data = NULL, + }; + void *buf = mm_alloc(&qry->request->pool, val.len); + entry_list_memcpy(buf, el); + ret = cache_write_or_clear(cache, &key, &val, qry); + if (ret) return kr_error(ret); + memcpy(val.data, buf, val.len); /* we also copy the "empty" space, but well... */ + val_new_entry->data = (uint8_t *)val.data + + ((uint8_t *)el[i_type].data - (uint8_t *)buf); + return kr_ok(); +} + diff --git a/lib/cache/entry_pkt.c b/lib/cache/entry_pkt.c new file mode 100644 index 0000000..00e73d4 --- /dev/null +++ b/lib/cache/entry_pkt.c @@ -0,0 +1,224 @@ +/* Copyright (C) 2017 CZ.NIC, z.s.p.o. <knot-dns@labs.nic.cz> + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <https://www.gnu.org/licenses/>. + */ + +/** @file + * Implementation of packet-caching. Prototypes in ./impl.h + * + * The packet is stashed in entry_h::data as uint16_t length + full packet wire format. + */ + +#include "lib/utils.h" +#include "lib/layer/iterate.h" /* kr_response_classify */ +#include "lib/cache/impl.h" + + +/** Compute TTL for a packet. Generally it's minimum TTL, with extra conditions. */ +static uint32_t packet_ttl(const knot_pkt_t *pkt, bool is_negative) +{ + bool has_ttl = false; + uint32_t ttl = UINT32_MAX; + /* Find minimum entry TTL in the packet or SOA minimum TTL. */ + for (knot_section_t i = KNOT_ANSWER; i <= KNOT_ADDITIONAL; ++i) { + const knot_pktsection_t *sec = knot_pkt_section(pkt, i); + for (unsigned k = 0; k < sec->count; ++k) { + const knot_rrset_t *rr = knot_pkt_rr(sec, k); + if (is_negative) { + /* Use SOA minimum TTL for negative answers. */ + if (rr->type == KNOT_RRTYPE_SOA) { + return MIN(rr->ttl, knot_soa_minimum(rr->rrs.rdata)); + } else { + continue; /* Use SOA only for negative answers. */ + } + } + if (knot_rrtype_is_metatype(rr->type)) { + continue; /* Skip metatypes. */ + } + ttl = MIN(ttl, rr->ttl); + } + } + /* If no valid TTL present, go with zero (will get clamped to minimum). */ + return has_ttl ? ttl : 0; +} + + +void stash_pkt(const knot_pkt_t *pkt, const struct kr_query *qry, + const struct kr_request *req, const bool has_optout) +{ + /* In some cases, stash also the packet. */ + const bool is_negative = kr_response_classify(pkt) + & (PKT_NODATA|PKT_NXDOMAIN); + const struct kr_qflags * const qf = &qry->flags; + const bool want_negative = qf->DNSSEC_INSECURE || !qf->DNSSEC_WANT || has_optout; + const bool want_pkt = qf->DNSSEC_BOGUS /*< useful for +cd answers */ + || (is_negative && want_negative); + + if (!want_pkt || !knot_wire_get_aa(pkt->wire) + || pkt->parsed != pkt->size /*< malformed packet; still can't detect KNOT_EFEWDATA */ + ) { + return; + } + + /* Compute rank. If cd bit is set or we got answer via non-validated + * forwarding, make the rank bad; otherwise it depends on flags. + * TODO: probably make validator attempt validation even with +cd. */ + uint8_t rank = KR_RANK_AUTH; + const bool risky_vldr = is_negative && qf->FORWARD && qf->CNAME; + /* ^^ CNAME'ed NXDOMAIN answer in forwarding mode can contain + * unvalidated records; original commit: d6e22f476. */ + if (knot_wire_get_cd(req->qsource.packet->wire) || qf->STUB || risky_vldr) { + kr_rank_set(&rank, KR_RANK_OMIT); + } else { + if (qf->DNSSEC_BOGUS) { + kr_rank_set(&rank, KR_RANK_BOGUS); + } else if (qf->DNSSEC_INSECURE) { + kr_rank_set(&rank, KR_RANK_INSECURE); + } else if (!qf->DNSSEC_WANT) { + /* no TAs at all, leave _RANK_AUTH */ + } else if (has_optout) { + /* All bad cases should be filtered above, + * at least the same way as pktcache in kresd 1.5.x. */ + kr_rank_set(&rank, KR_RANK_SECURE); + } else assert(false); + } + + const uint16_t pkt_type = knot_pkt_qtype(pkt); + const knot_dname_t *owner = knot_pkt_qname(pkt); /* qname can't be compressed */ + + // LATER: nothing exists under NXDOMAIN. Implement that (optionally)? +#if 0 + if (knot_wire_get_rcode(pkt->wire) == KNOT_RCODE_NXDOMAIN + /* && !qf->DNSSEC_INSECURE */ ) { + pkt_type = KNOT_RRTYPE_NS; + } +#endif + + /* Construct the key under which the pkt will be stored. */ + struct key k_storage, *k = &k_storage; + knot_db_val_t key; + int ret = kr_dname_lf(k->buf, owner, false); + if (ret) { + /* A server might (incorrectly) reply with QDCOUNT=0. */ + assert(owner == NULL); + return; + } + key = key_exact_type_maypkt(k, pkt_type); + + /* For now we stash the full packet byte-exactly as it came from upstream. */ + const uint16_t pkt_size = pkt->size; + knot_db_val_t val_new_entry = { + .data = NULL, + .len = offsetof(struct entry_h, data) + sizeof(pkt_size) + pkt->size, + }; + /* Prepare raw memory for the new entry and fill it. */ + struct kr_cache *cache = &req->ctx->cache; + ret = entry_h_splice(&val_new_entry, rank, key, k->type, pkt_type, + owner, qry, cache, qry->timestamp.tv_sec); + if (ret) return; /* some aren't really errors */ + assert(val_new_entry.data); + struct entry_h *eh = val_new_entry.data; + memset(eh, 0, offsetof(struct entry_h, data)); + eh->time = qry->timestamp.tv_sec; + eh->ttl = MAX(MIN(packet_ttl(pkt, is_negative), cache->ttl_max), cache->ttl_min); + eh->rank = rank; + eh->is_packet = true; + eh->has_optout = qf->DNSSEC_OPTOUT; + memcpy(eh->data, &pkt_size, sizeof(pkt_size)); + memcpy(eh->data + sizeof(pkt_size), pkt->wire, pkt_size); + + WITH_VERBOSE(qry) { + auto_free char *type_str = kr_rrtype_text(pkt_type), + *owner_str = kr_dname_text(owner); + VERBOSE_MSG(qry, "=> stashed packet: rank 0%.2o, TTL %d, " + "%s %s (%d B)\n", + eh->rank, eh->ttl, + type_str, owner_str, (int)val_new_entry.len); + } +} + + +int answer_from_pkt(kr_layer_t *ctx, knot_pkt_t *pkt, uint16_t type, + const struct entry_h *eh, const void *eh_bound, uint32_t new_ttl) +{ + struct kr_request *req = ctx->req; + struct kr_query *qry = req->current_query; + + uint16_t pkt_len; + memcpy(&pkt_len, eh->data, sizeof(pkt_len)); + if (pkt_len > pkt->max_size) { + return kr_error(ENOENT); + } + + /* Copy answer and reparse it, but keep the original message id. */ + uint16_t msgid = knot_wire_get_id(pkt->wire); + knot_pkt_clear(pkt); + memcpy(pkt->wire, eh->data + 2, pkt_len); + pkt->size = pkt_len; + int ret = knot_pkt_parse(pkt, 0); + if (ret == KNOT_EFEWDATA || ret == KNOT_EMALF) { + return kr_error(ENOENT); + /* LATER(opt): try harder to avoid stashing such packets */ + } + if (ret != KNOT_EOK) { + assert(!ret); + return kr_error(ret); + } + knot_wire_set_id(pkt->wire, msgid); + + /* Add rank into the additional field. */ + for (size_t i = 0; i < pkt->rrset_count; ++i) { + assert(!pkt->rr[i].additional); + uint8_t *rr_rank = mm_alloc(&pkt->mm, sizeof(*rr_rank)); + if (!rr_rank) { + return kr_error(ENOMEM); + } + *rr_rank = eh->rank; + pkt->rr[i].additional = rr_rank; + } + + /* Adjust TTL in each record. */ + const uint32_t drift = eh->ttl - new_ttl; + for (knot_section_t i = KNOT_ANSWER; i <= KNOT_ADDITIONAL; ++i) { + const knot_pktsection_t *sec = knot_pkt_section(pkt, i); + for (unsigned k = 0; k < sec->count; ++k) { + knot_rrset_t *rrs = // vv FIXME?? + /*const-cast*/(knot_rrset_t *)knot_pkt_rr(sec, k); + /* We need to be careful: due to enforcing minimum TTL + * on packet, some records may be below that value. + * We keep those records at TTL 0. */ + if (rrs->ttl >= drift) { + rrs->ttl -= drift; + } else { + rrs->ttl = 0; + } + } + } + + /* Finishing touches. TODO: perhaps factor out */ + struct kr_qflags * const qf = &qry->flags; + qf->EXPIRING = is_expiring(eh->ttl, new_ttl); + qf->CACHED = true; + qf->NO_MINIMIZE = true; + qf->DNSSEC_INSECURE = kr_rank_test(eh->rank, KR_RANK_INSECURE); + qf->DNSSEC_BOGUS = kr_rank_test(eh->rank, KR_RANK_BOGUS); + if (qf->DNSSEC_INSECURE || qf->DNSSEC_BOGUS) { + qf->DNSSEC_WANT = false; + } + qf->DNSSEC_OPTOUT = eh->has_optout; + VERBOSE_MSG(qry, "=> satisfied by exact packet: rank 0%.2o, new TTL %d\n", + eh->rank, new_ttl); + return kr_ok(); +} + diff --git a/lib/cache/entry_rr.c b/lib/cache/entry_rr.c new file mode 100644 index 0000000..94dd0e8 --- /dev/null +++ b/lib/cache/entry_rr.c @@ -0,0 +1,146 @@ +/* Copyright (C) 2017 CZ.NIC, z.s.p.o. <knot-dns@labs.nic.cz> + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <https://www.gnu.org/licenses/>. + */ + +/** @file + * Implementation of RRset (de)materialization, i.e. (de)serialization to storage + * format used in cache (some repeated fields are omitted). Prototypes in ./impl.h + */ + +#include "lib/cache/impl.h" + +int rdataset_dematerialize(const knot_rdataset_t *rds, uint8_t * restrict data) +{ + /* FIXME: either give up on even alignment and thus direct usability + * of rdatasets as they are in lmdb, or align inside cdb_* functions + * (request sizes one byte longer and shift iff on an odd address). */ + //if ((size_t)data & 1) VERBOSE_MSG(NULL, "dematerialize: odd address\n"); + //const uint8_t *data0 = data; + if (!data) { + assert(data); + return kr_error(EINVAL); + } + const uint16_t rr_count = rds ? rds->count : 0; + memcpy(data, &rr_count, sizeof(rr_count)); + data += sizeof(rr_count); + if (rr_count) { + size_t size = knot_rdataset_size(rds); + memcpy(data, rds->rdata, size); + data += size; + } + //VERBOSE_MSG(NULL, "dematerialized to %d B\n", (int)(data - data0)); + (void)data; + return kr_ok(); +} + +/** Materialize a knot_rdataset_t from cache with given TTL. + * Return the number of bytes consumed or an error code. + */ +static int rdataset_materialize(knot_rdataset_t * restrict rds, const uint8_t * const data, + const uint8_t *data_bound, knot_mm_t *pool) +{ + assert(rds && data && data_bound && data_bound > data && !rds->rdata + /*&& !((size_t)data & 1)*/); + assert(pool); /* not required, but that's our current usage; guard leaks */ + const uint8_t *d = data; /* iterates over the cache data */ + { + uint16_t rr_count; + memcpy(&rr_count, d, sizeof(rr_count)); + d += sizeof(rr_count); + rds->count = rr_count; + if (!rr_count) { /* avoid mm_alloc(pool, 0); etc. */ + return d - data; + } + } + /* First sum up the sizes for wire format length. */ + const knot_rdataset_t rds_tmp = { + .count = rds->count, + .rdata = (knot_rdata_t *)d, + }; + size_t rds_size = knot_rdataset_size(&rds_tmp); /* TODO: we might overrun here already, + but we need to trust cache anyway...*/ + if (d + rds_size > data_bound) { + VERBOSE_MSG(NULL, "materialize: EILSEQ!\n"); + return kr_error(EILSEQ); + } + rds->rdata = mm_alloc(pool, rds_size); + if (!rds->rdata) { + return kr_error(ENOMEM); + } + memcpy(rds->rdata, d, rds_size); + d += rds_size; + //VERBOSE_MSG(NULL, "materialized from %d B\n", (int)(d - data)); + return d - data; +} + +int kr_cache_materialize(knot_rdataset_t *dst, const struct kr_cache_p *ref, + knot_mm_t *pool) +{ + struct entry_h *eh = ref->raw_data; + return rdataset_materialize(dst, eh->data, ref->raw_bound, pool); +} + + +int entry2answer(struct answer *ans, int id, + const struct entry_h *eh, const uint8_t *eh_bound, + const knot_dname_t *owner, uint16_t type, uint32_t new_ttl) +{ + /* We assume it's zeroed. Do basic sanity check. */ + if (ans->rrsets[id].set.rr || ans->rrsets[id].sig_rds.rdata + || (type == KNOT_RRTYPE_NSEC && ans->nsec_p.raw) + || (type == KNOT_RRTYPE_NSEC3 && !ans->nsec_p.raw) + ) + { + assert(false); + return kr_error(EINVAL); + } + /* Materialize the base RRset. */ + knot_rrset_t *rr = ans->rrsets[id].set.rr + = knot_rrset_new(owner, type, KNOT_CLASS_IN, new_ttl, ans->mm); + if (!rr) { + assert(!ENOMEM); + return kr_error(ENOMEM); + } + int ret = rdataset_materialize(&rr->rrs, eh->data, eh_bound, ans->mm); + if (ret < 0) goto fail; + size_t data_off = ret; + ans->rrsets[id].set.rank = eh->rank; + ans->rrsets[id].set.expiring = is_expiring(eh->ttl, new_ttl); + /* Materialize the RRSIG RRset for the answer in (pseudo-)packet. */ + bool want_rrsigs = true; /* LATER(optim.): might be omitted in some cases. */ + if (want_rrsigs) { + ret = rdataset_materialize(&ans->rrsets[id].sig_rds, eh->data + data_off, + eh_bound, ans->mm); + if (ret < 0) goto fail; + /* Sanity check: we consumed exactly all data. */ + int unused_bytes = eh_bound - (uint8_t *)eh->data - data_off - ret; + if (unused_bytes) { + kr_log_error("[cach] entry2answer ERROR: unused bytes: %d\n", + unused_bytes); + assert(!EILSEQ); + ret = kr_error(EILSEQ); + goto fail; /* to be on the safe side */ + } + } + return kr_ok(); +fail: + assert(/*false*/!ret); + /* Cleanup the item that we might've (partially) written to. */ + knot_rrset_free(ans->rrsets[id].set.rr, ans->mm); + knot_rdataset_clear(&ans->rrsets[id].sig_rds, ans->mm); + memset(&ans->rrsets[id], 0, sizeof(ans->rrsets[id])); + return kr_error(ret); +} + diff --git a/lib/cache/impl.h b/lib/cache/impl.h new file mode 100644 index 0000000..a08f355 --- /dev/null +++ b/lib/cache/impl.h @@ -0,0 +1,412 @@ +/* Copyright (C) 2017 CZ.NIC, z.s.p.o. <knot-dns@labs.nic.cz> + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <https://www.gnu.org/licenses/>. + */ + +/** @file + * Header internal for cache implementation(s). + * Only LMDB works for now. + */ +#pragma once + +#include <stdbool.h> +#include <stdint.h> + +#include <libdnssec/error.h> +#include <libdnssec/nsec.h> +#include <libknot/consts.h> +#include <libknot/db/db.h> +#include <libknot/dname.h> + +#include "contrib/cleanup.h" +#include "contrib/murmurhash3/murmurhash3.h" /* hash() for nsec_p_hash() */ +#include "lib/cache/cdb_api.h" +#include "lib/resolve.h" + +/* Cache entry values - binary layout. + * + * It depends on type which is recognizable by the key. + * Code depending on the contents of the key is marked by CACHE_KEY_DEF. + * + * 'E' entry (exact hit): + * - ktype == NS: struct entry_apex - multiple types inside (NS and xNAME); + * - ktype != NS: struct entry_h + * * is_packet: uint16_t length, the rest is opaque and handled by ./entry_pkt.c + * * otherwise RRset + its RRSIG set (possibly empty). + * '1' or '3' entry (NSEC or NSEC3) + * - struct entry_h, contents is the same as for exact hit + * - flags don't make sense there + */ + +struct entry_h { + uint32_t time; /**< The time of inception. */ + uint32_t ttl; /**< TTL at inception moment. Assuming it fits into int32_t ATM. */ + uint8_t rank : 6; /**< See enum kr_rank */ + bool is_packet : 1; /**< Negative-answer packet for insecure/bogus name. */ + bool has_optout : 1; /**< Only for packets; persisted DNSSEC_OPTOUT. */ + uint8_t _pad; /**< We need even alignment for data now. */ + uint8_t data[]; +}; +struct entry_apex; + +/** Check basic consistency of entry_h for 'E' entries, not looking into ->data. + * (for is_packet the length of data is checked) + */ +struct entry_h * entry_h_consistent(knot_db_val_t data, uint16_t type); + +struct entry_apex * entry_apex_consistent(knot_db_val_t val); + +/** Consistency check, ATM common for NSEC and NSEC3. */ +static inline struct entry_h * entry_h_consistent_NSEC(knot_db_val_t data) +{ + /* ATM it's enough to just extend the checks for exact entries. */ + const struct entry_h *eh = entry_h_consistent(data, KNOT_RRTYPE_NSEC); + bool ok = eh != NULL; + ok = ok && !eh->is_packet && !eh->has_optout; + return ok ? /*const-cast*/(struct entry_h *)eh : NULL; +} + + +/* nsec_p* - NSEC* chain parameters */ + +static inline int nsec_p_rdlen(const uint8_t *rdata) +{ + //TODO: do we really need the zero case? + return rdata ? 5 + rdata[4] : 0; /* rfc5155 4.2 and 3.2. */ +} +static const int NSEC_P_MAXLEN = sizeof(uint32_t) + 5 + 255; // TODO: remove?? + +/** Hash of NSEC3 parameters, used as a tag to separate different chains for same zone. */ +typedef uint32_t nsec_p_hash_t; +static inline nsec_p_hash_t nsec_p_mkHash(const uint8_t *nsec_p) +{ + assert(nsec_p && !(KNOT_NSEC3_FLAG_OPT_OUT & nsec_p[1])); + return hash((const char *)nsec_p, nsec_p_rdlen(nsec_p)); +} + +/** NSEC* parameters for the chain. */ +struct nsec_p { + const uint8_t *raw; /**< Pointer to raw NSEC3 parameters; NULL for NSEC. */ + nsec_p_hash_t hash; /**< Hash of `raw`, used for cache keys. */ + dnssec_nsec3_params_t libknot; /**< Format for libknot; owns malloced memory! */ +}; + + + +/** LATER(optim.): this is overshot, but struct key usage should be cheap ATM. */ +#define KR_CACHE_KEY_MAXLEN (KNOT_DNAME_MAXLEN + 100) /* CACHE_KEY_DEF */ + +struct key { + const knot_dname_t *zname; /**< current zone name (points within qry->sname) */ + uint8_t zlf_len; /**< length of current zone's lookup format */ + + /** Corresponding key type; e.g. NS for CNAME. + * Note: NSEC type is ambiguous (exact and range key). */ + uint16_t type; + /** The key data start at buf+1, and buf[0] contains some length. + * For details see key_exact* and key_NSEC* functions. */ + uint8_t buf[KR_CACHE_KEY_MAXLEN]; + /* LATER(opt.): ^^ probably change the anchoring, so that kr_dname_lf() + * doesn't need to move data after knot_dname_lf(). */ +}; + +static inline size_t key_nwz_off(const struct key *k) +{ + /* CACHE_KEY_DEF: zone name lf + 0 ('1' or '3'). + * NSEC '1' case continues just with the name within zone. */ + return k->zlf_len + 2; +} +static inline size_t key_nsec3_hash_off(const struct key *k) +{ + /* CACHE_KEY_DEF NSEC3: tag (nsec_p_hash_t) + 20 bytes NSEC3 name hash) */ + return key_nwz_off(k) + sizeof(nsec_p_hash_t); +} +/** Hash is always SHA1; I see no plans to standardize anything else. + * https://www.iana.org/assignments/dnssec-nsec3-parameters/dnssec-nsec3-parameters.xhtml#dnssec-nsec3-parameters-3 + */ +static const int NSEC3_HASH_LEN = 20, + NSEC3_HASH_TXT_LEN = 32; + +/** Finish constructing string key for for exact search. + * It's assumed that kr_dname_lf(k->buf, owner, *) had been ran. + */ +knot_db_val_t key_exact_type_maypkt(struct key *k, uint16_t type); + +/** Like key_exact_type_maypkt but with extra checks if used for RRs only. */ +static inline knot_db_val_t key_exact_type(struct key *k, uint16_t type) +{ + switch (type) { + /* Sanity check: forbidden types represented in other way(s). */ + case KNOT_RRTYPE_NSEC: + case KNOT_RRTYPE_NSEC3: + assert(false); + return (knot_db_val_t){ NULL, 0 }; + } + return key_exact_type_maypkt(k, type); +} + + +/* entry_h chaining; implementation in ./entry_list.c */ + +enum { ENTRY_APEX_NSECS_CNT = 2 }; + +/** Header of 'E' entry with ktype == NS. Inside is private to ./entry_list.c + * + * We store xNAME at NS type to lower the number of searches in closest_NS(). + * CNAME is only considered for equal name, of course. + * We also store NSEC* parameters at NS type. + */ +struct entry_apex { + /* ENTRY_H_FLAGS */ + bool has_ns : 1; + bool has_cname : 1; + bool has_dname : 1; + + uint8_t pad_; /**< Weird: 1 byte + 2 bytes + x bytes; let's do 2+2+x. */ + int8_t nsecs[ENTRY_APEX_NSECS_CNT]; /**< values: 0: none, 1: NSEC, 3: NSEC3 */ + uint8_t data[]; + /* XXX: if not first, stamp of last being the first? + * Purpose: save cache operations if rolled the algo/params long ago. */ +}; + +/** Indices for decompressed entry_list_t. */ +enum EL { + EL_NS = ENTRY_APEX_NSECS_CNT, + EL_CNAME, + EL_DNAME, + EL_LENGTH +}; +/** Decompressed entry_apex. It's an array of unparsed entry_h references. + * Note: arrays are passed "by reference" to functions (in C99). */ +typedef knot_db_val_t entry_list_t[EL_LENGTH]; + +static inline uint16_t EL2RRTYPE(enum EL i) +{ + switch (i) { + case EL_NS: return KNOT_RRTYPE_NS; + case EL_CNAME: return KNOT_RRTYPE_CNAME; + case EL_DNAME: return KNOT_RRTYPE_DNAME; + default: assert(false); return 0; + } +} + +/** There may be multiple entries within, so rewind `val` to the one we want. + * + * ATM there are multiple types only for the NS ktype - it also accommodates xNAMEs. + * \note `val->len` represents the bound of the whole list, not of a single entry. + * \note in case of ENOENT, `val` is still rewound to the beginning of the next entry. + * \return error code + * TODO: maybe get rid of this API? + */ +int entry_h_seek(knot_db_val_t *val, uint16_t type); + +/** Prepare space to insert an entry. + * + * Some checks are performed (rank, TTL), the current entry in cache is copied + * with a hole ready for the new entry (old one of the same type is cut out). + * + * \param val_new_entry The only changing parameter; ->len is read, ->data written. + * \return error code + */ +int entry_h_splice( + knot_db_val_t *val_new_entry, uint8_t rank, + const knot_db_val_t key, const uint16_t ktype, const uint16_t type, + const knot_dname_t *owner/*log only*/, + const struct kr_query *qry, struct kr_cache *cache, uint32_t timestamp); + +/** Parse an entry_apex into individual items. @return error code. */ +int entry_list_parse(const knot_db_val_t val, entry_list_t list); + +static inline size_t to_even(size_t n) +{ + return n + (n & 1); +} + +static inline int entry_list_serial_size(const entry_list_t list) +{ + int size = offsetof(struct entry_apex, data); + for (int i = 0; i < EL_LENGTH; ++i) { + size += to_even(list[i].len); + } + return size; +} + +/** Fill contents of an entry_apex. + * + * @note NULL pointers are overwritten - caller may like to fill the space later. + */ +void entry_list_memcpy(struct entry_apex *ea, entry_list_t list); + + + +/* Packet caching; implementation in ./entry_pkt.c */ + +/** Stash the packet into cache (if suitable, etc.) + * \param has_optout whether the packet contains an opt-out NSEC3 */ +void stash_pkt(const knot_pkt_t *pkt, const struct kr_query *qry, + const struct kr_request *req, bool has_optout); + +/** Try answering from packet cache, given an entry_h. + * + * This assumes the TTL is OK and entry_h_consistent, but it may still return error. + * On success it handles all the rest, incl. qry->flags. + */ +int answer_from_pkt(kr_layer_t *ctx, knot_pkt_t *pkt, uint16_t type, + const struct entry_h *eh, const void *eh_bound, uint32_t new_ttl); + + +/** Record is expiring if it has less than 1% TTL (or less than 5s) */ +static inline bool is_expiring(uint32_t orig_ttl, uint32_t new_ttl) +{ + int64_t nttl = new_ttl; /* avoid potential over/under-flow */ + return 100 * (nttl - 5) < orig_ttl; +} + +/** Returns signed result so you can inspect how much stale the RR is. + * + * @param owner name for stale-serving decisions. You may pass NULL to disable stale. + * @note: NSEC* uses zone name ATM; for NSEC3 the owner may not even be knowable. + * @param type for stale-serving. + */ +int32_t get_new_ttl(const struct entry_h *entry, const struct kr_query *qry, + const knot_dname_t *owner, uint16_t type, uint32_t now); + + +/* RRset (de)materialization; implementation in ./entry_rr.c */ + +/** Size of the RR count field */ +#define KR_CACHE_RR_COUNT_SIZE sizeof(uint16_t) + +/** Compute size of serialized rdataset. NULL is accepted as empty set. */ +static inline int rdataset_dematerialize_size(const knot_rdataset_t *rds) +{ + return KR_CACHE_RR_COUNT_SIZE + (rds == NULL ? 0 : knot_rdataset_size(rds)); +} + +static inline int rdataset_dematerialized_size(const uint8_t *data) +{ + knot_rdataset_t rds; + memcpy(&rds.count, data, sizeof(rds.count)); + rds.rdata = (knot_rdata_t *)(data + sizeof(rds.count)); + return sizeof(rds.count) + knot_rdataset_size(&rds); +} + +/** Serialize an rdataset. */ +int rdataset_dematerialize(const knot_rdataset_t *rds, uint8_t * restrict data); + + +/** Partially constructed answer when gathering RRsets from cache. */ +struct answer { + int rcode; /**< PKT_NODATA, etc. */ + struct nsec_p nsec_p; /**< Don't mix different NSEC* parameters in one answer. */ + knot_mm_t *mm; /**< Allocator for rrsets */ + struct answer_rrset { + ranked_rr_array_entry_t set; /**< set+rank for the main data */ + knot_rdataset_t sig_rds; /**< RRSIG data, if any */ + } rrsets[1+1+3]; /**< see AR_ANSWER and friends; only required records are filled */ +}; +enum { + AR_ANSWER = 0, /**< Positive answer record. It might be wildcard-expanded. */ + AR_SOA, /**< SOA record. */ + AR_NSEC, /**< NSEC* covering or matching the SNAME (next closer name in NSEC3 case). */ + AR_WILD, /**< NSEC* covering or matching the source of synthesis. */ + AR_CPE, /**< NSEC3 matching the closest provable encloser. */ +}; + +/** Materialize RRset + RRSIGs into ans->rrsets[id]. + * LATER(optim.): it's slightly wasteful that we allocate knot_rrset_t for the packet + * + * \return error code. They are all bad conditions and "guarded" by assert. + */ +int entry2answer(struct answer *ans, int id, + const struct entry_h *eh, const uint8_t *eh_bound, + const knot_dname_t *owner, uint16_t type, uint32_t new_ttl); + + +/* Preparing knot_pkt_t for cache answer from RRs; implementation in ./knot_pkt.c */ + +/** Prepare answer packet to be filled by RRs (without RR data in wire). */ +int pkt_renew(knot_pkt_t *pkt, const knot_dname_t *name, uint16_t type); + +/** Append RRset + its RRSIGs into the current section (*shallow* copy), with given rank. + * \note it works with empty set as well (skipped) + * \note pkt->wire is not updated in any way + * \note KNOT_CLASS_IN is assumed + */ +int pkt_append(knot_pkt_t *pkt, const struct answer_rrset *rrset, uint8_t rank); + + + +/* NSEC (1) stuff. Implementation in ./nsec1.c */ + +/** Construct a string key for for NSEC (1) predecessor-search. + * \param add_wildcard Act as if the name was extended by "*." + * \note k->zlf_len is assumed to have been correctly set */ +knot_db_val_t key_NSEC1(struct key *k, const knot_dname_t *name, bool add_wildcard); + +/** Closest encloser check for NSEC (1). + * To understand the interface, see the call point. + * \param k space to store key + input: zname and zlf_len + * \return 0: success; >0: try other (NSEC3); <0: exit cache immediately. */ +int nsec1_encloser(struct key *k, struct answer *ans, + const int sname_labels, int *clencl_labels, + knot_db_val_t *cover_low_kwz, knot_db_val_t *cover_hi_kwz, + const struct kr_query *qry, struct kr_cache *cache); + +/** Source of synthesis (SS) check for NSEC (1). + * To understand the interface, see the call point. + * \return 0: continue; <0: exit cache immediately; + * AR_SOA: skip to adding SOA (SS was covered or matched for NODATA). */ +int nsec1_src_synth(struct key *k, struct answer *ans, const knot_dname_t *clencl_name, + knot_db_val_t cover_low_kwz, knot_db_val_t cover_hi_kwz, + const struct kr_query *qry, struct kr_cache *cache); + + +/* NSEC3 stuff. Implementation in ./nsec3.c */ + +/** Construct a string key for for NSEC3 predecessor-search, from an NSEC3 name. + * \note k->zlf_len is assumed to have been correctly set */ +knot_db_val_t key_NSEC3(struct key *k, const knot_dname_t *nsec3_name, + const nsec_p_hash_t nsec_p_hash); + +/** TODO. See nsec1_encloser(...) */ +int nsec3_encloser(struct key *k, struct answer *ans, + const int sname_labels, int *clencl_labels, + const struct kr_query *qry, struct kr_cache *cache); + +/** TODO. See nsec1_src_synth(...) */ +int nsec3_src_synth(struct key *k, struct answer *ans, const knot_dname_t *clencl_name, + const struct kr_query *qry, struct kr_cache *cache); + + + +#define VERBOSE_MSG(qry, ...) QRVERBOSE((qry), "cach", ## __VA_ARGS__) + +/** Shorthand for operations on cache backend */ +#define cache_op(cache, op, ...) (cache)->api->op((cache)->db, ## __VA_ARGS__) + + +static inline uint16_t get_uint16(const void *address) +{ + uint16_t tmp; + memcpy(&tmp, address, sizeof(tmp)); + return tmp; +} + +/** Useful pattern, especially as void-pointer arithmetic isn't standard-compliant. */ +static inline uint8_t * knot_db_val_bound(knot_db_val_t val) +{ + return (uint8_t *)val.data + val.len; +} + diff --git a/lib/cache/knot_pkt.c b/lib/cache/knot_pkt.c new file mode 100644 index 0000000..56836a6 --- /dev/null +++ b/lib/cache/knot_pkt.c @@ -0,0 +1,106 @@ +/* Copyright (C) 2017 CZ.NIC, z.s.p.o. <knot-dns@labs.nic.cz> + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <https://www.gnu.org/licenses/>. + */ + +/** @file + * Implementation of preparing knot_pkt_t for filling with RRs. + * Prototypes in ./impl.h + */ + +#include "lib/cache/impl.h" + +int pkt_renew(knot_pkt_t *pkt, const knot_dname_t *name, uint16_t type) +{ + /* Update packet question if needed. */ + if (!knot_dname_is_equal(knot_pkt_qname(pkt), name) + || knot_pkt_qtype(pkt) != type || knot_pkt_qclass(pkt) != KNOT_CLASS_IN) { + int ret = kr_pkt_recycle(pkt); + if (ret) return kr_error(ret); + ret = knot_pkt_put_question(pkt, name, KNOT_CLASS_IN, type); + if (ret) return kr_error(ret); + } + + pkt->parsed = pkt->size = PKT_SIZE_NOWIRE; + knot_wire_set_qr(pkt->wire); + knot_wire_set_aa(pkt->wire); + return kr_ok(); +} + +/** Reserve space for additional `count` RRsets. + * \note pkt->rr_info gets correct length but is always zeroed + */ +static int pkt_alloc_space(knot_pkt_t *pkt, int count) +{ + size_t allocd_orig = pkt->rrset_allocd; + if (pkt->rrset_count + count <= allocd_orig) { + return kr_ok(); + } + /* A simple growth strategy, amortized O(count). */ + pkt->rrset_allocd = MAX( + pkt->rrset_count + count, + pkt->rrset_count + allocd_orig); + + pkt->rr = mm_realloc(&pkt->mm, pkt->rr, + sizeof(pkt->rr[0]) * pkt->rrset_allocd, + sizeof(pkt->rr[0]) * allocd_orig); + if (!pkt->rr) { + return kr_error(ENOMEM); + } + /* Allocate pkt->rr_info to be certain, but just leave it zeroed. */ + mm_free(&pkt->mm, pkt->rr_info); + pkt->rr_info = mm_alloc(&pkt->mm, sizeof(pkt->rr_info[0]) * pkt->rrset_allocd); + if (!pkt->rr_info) { + return kr_error(ENOMEM); + } + memset(pkt->rr_info, 0, sizeof(pkt->rr_info[0]) * pkt->rrset_allocd); + return kr_ok(); +} + +int pkt_append(knot_pkt_t *pkt, const struct answer_rrset *rrset, uint8_t rank) +{ + /* allocate space, to be sure */ + int rrset_cnt = (rrset->set.rr->rrs.count > 0) + (rrset->sig_rds.count > 0); + int ret = pkt_alloc_space(pkt, rrset_cnt); + if (ret) return kr_error(ret); + /* write both sets */ + const knot_rdataset_t *rdss[2] = { &rrset->set.rr->rrs, &rrset->sig_rds }; + for (int i = 0; i < rrset_cnt; ++i) { + assert(rdss[i]->count); + /* allocate rank */ + uint8_t *rr_rank = mm_alloc(&pkt->mm, sizeof(*rr_rank)); + if (!rr_rank) return kr_error(ENOMEM); + *rr_rank = (i == 0) ? rank : (KR_RANK_OMIT | KR_RANK_AUTH); + /* rank for RRSIGs isn't really useful: ^^ */ + if (i == 0) { + pkt->rr[pkt->rrset_count] = *rrset->set.rr; + pkt->rr[pkt->rrset_count].additional = rr_rank; + } else { + /* append the RR array */ + pkt->rr[pkt->rrset_count] = (knot_rrset_t){ + .owner = knot_dname_copy(rrset->set.rr->owner, &pkt->mm), + /* ^^ well, another copy isn't really needed */ + .ttl = rrset->set.rr->ttl, + .type = KNOT_RRTYPE_RRSIG, + .rclass = KNOT_CLASS_IN, + .rrs = *rdss[i], + .additional = rr_rank, + }; + } + ++pkt->rrset_count; + ++(pkt->sections[pkt->current].count); + } + return kr_ok(); +} + diff --git a/lib/cache/nsec1.c b/lib/cache/nsec1.c new file mode 100644 index 0000000..74b3d34 --- /dev/null +++ b/lib/cache/nsec1.c @@ -0,0 +1,511 @@ +/* Copyright (C) 2017 CZ.NIC, z.s.p.o. <knot-dns@labs.nic.cz> + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <https://www.gnu.org/licenses/>. + */ + +/** @file + * Implementation of NSEC (1) handling. Prototypes in ./impl.h + */ + +#include "lib/cache/impl.h" +#include "lib/dnssec/nsec.h" +#include "lib/layer/iterate.h" + + +/** Reconstruct a name into a buffer (assuming length at least KNOT_DNAME_MAXLEN). + * \return kr_ok() or error code (<0). */ +static int dname_wire_reconstruct(knot_dname_t *buf, const struct key *k, + knot_db_val_t kwz) +{ + /* Reconstruct from key: first the ending, then zone name. */ + int ret = knot_dname_lf2wire(buf, kwz.len, kwz.data); + if (ret < 0) { + VERBOSE_MSG(NULL, "=> NSEC: LF2wire ret = %d\n", ret); + assert(false); + return ret; + } + /* The last written byte is the zero label for root -> overwrite. */ + knot_dname_t *zone_start = buf + ret - 1; + assert(*zone_start == '\0'); + ret = knot_dname_to_wire(zone_start, k->zname, KNOT_DNAME_MAXLEN - kwz.len); + if (ret != k->zlf_len + 1) { + assert(false); + return ret < 0 ? ret : kr_error(EILSEQ); + } + return kr_ok(); +} + + +knot_db_val_t key_NSEC1(struct key *k, const knot_dname_t *name, bool add_wildcard) +{ + /* we basically need dname_lf with two bytes added + * on a correct place within the name (the cut) */ + int ret; + const bool ok = k && name + && !(ret = kr_dname_lf(k->buf, name, add_wildcard)); + if (!ok) { + assert(false); + return (knot_db_val_t){ NULL, 0 }; + } + + uint8_t *begin = k->buf + 1 + k->zlf_len; /* one byte after zone's zero */ + uint8_t *end = k->buf + 1 + k->buf[0]; /* we don't use the final zero in key, + * but move it anyway */ + if (end < begin) { + assert(false); + return (knot_db_val_t){ NULL, 0 }; + } + int key_len; + if (end > begin) { + memmove(begin + 2, begin, end - begin); + key_len = k->buf[0] + 1; + } else { + key_len = k->buf[0] + 2; + } + /* CACHE_KEY_DEF: key == zone's dname_lf + '\0' + '1' + dname_lf + * of the name within the zone without the final 0. Iff the latter is empty, + * there's no zero to cut and thus the key_len difference. + */ + begin[0] = 0; + begin[1] = '1'; /* tag for NSEC1 */ + k->type = KNOT_RRTYPE_NSEC; + + /* + VERBOSE_MSG(NULL, "<> key_NSEC1; name: "); + kr_dname_print(name, add_wildcard ? "*." : "" , " "); + kr_log_verbose("(zone name LF length: %d; total key length: %d)\n", + k->zlf_len, key_len); + */ + + return (knot_db_val_t){ k->buf + 1, key_len }; +} + + +/** Assuming that k1 < k4, find where k2 is. (Considers DNS wrap-around.) + * + * \return Intuition: position of k2 among kX. + * 0: k2 < k1; 1: k1 == k2; 2: k1 is a prefix of k2 < k4; + * 3: k1 < k2 < k4 (and not 2); 4: k2 == k4; 5: k2 > k4 + * \note k1.data may be NULL, meaning assumption that k1 < k2 and not a prefix + * (i.e. return code will be > 2) + */ +static int kwz_between(knot_db_val_t k1, knot_db_val_t k2, knot_db_val_t k4) +{ + assert(k2.data && k4.data); + /* CACHE_KEY_DEF; we need to beware of one key being a prefix of another */ + int ret_maybe; /**< result, assuming we confirm k2 < k4 */ + if (k1.data) { + const int cmp12 = memcmp(k1.data, k2.data, MIN(k1.len, k2.len)); + if (cmp12 == 0 && k1.len == k2.len) /* iff k1 == k2 */ + return 1; + if (cmp12 > 0 || (cmp12 == 0 && k1.len > k2.len)) /* iff k1 > k2 */ + return 0; + ret_maybe = cmp12 == 0 ? 2 : 3; + } else { + ret_maybe = 3; + } + if (k4.len == 0) { /* wrap-around */ + return k2.len > 0 ? ret_maybe : 4; + } else { + const int cmp24 = memcmp(k2.data, k4.data, MIN(k2.len, k4.len)); + if (cmp24 == 0 && k2.len == k4.len) /* iff k2 == k4 */ + return 4; + if (cmp24 > 0 || (cmp24 == 0 && k2.len > k4.len)) /* iff k2 > k4 */ + return 5; + return ret_maybe; + } +} + + +/** NSEC1 range search. + * + * \param key Pass output of key_NSEC1(k, ...) + * \param value[out] The raw data of the NSEC cache record (optional; consistency checked). + * \param exact_match[out] Whether the key was matched exactly or just covered (optional). + * \param kwz_low[out] Output the low end of covering NSEC, pointing within DB (optional). + * \param kwz_high[in,out] Storage for the high end of covering NSEC (optional). + * It's only set if !exact_match. + * \param new_ttl[out] New TTL of the NSEC (optional). + * \return Error message or NULL. + * \note The function itself does *no* bitmap checks, e.g. RFC 6840 sec. 4. + */ +static const char * find_leq_NSEC1(struct kr_cache *cache, const struct kr_query *qry, + const knot_db_val_t key, const struct key *k, knot_db_val_t *value, + bool *exact_match, knot_db_val_t *kwz_low, knot_db_val_t *kwz_high, + uint32_t *new_ttl) +{ + /* Do the cache operation. */ + const size_t nwz_off = key_nwz_off(k); + if (!key.data || key.len < nwz_off) { + assert(false); + return "range search ERROR"; + } + knot_db_val_t key_nsec = key; + knot_db_val_t val = { NULL, 0 }; + int ret = cache_op(cache, read_leq, &key_nsec, &val); + if (ret < 0) { + if (ret == kr_error(ENOENT)) { + return "range search miss"; + } else { + assert(false); + return "range search ERROR"; + } + } + if (value) { + *value = val; + } + /* Check consistency, TTL, rank. */ + const bool is_exact = (ret == 0); + if (exact_match) { + *exact_match = is_exact; + } + const struct entry_h *eh = entry_h_consistent_NSEC(val); + if (!eh) { + /* This might be just finding something else than NSEC1 entry, + * in case we searched before the very first one in the zone. */ + return "range search found inconsistent entry"; + } + /* Passing just zone name instead of owner, as we don't + * have it reconstructed at this point. */ + int32_t new_ttl_ = get_new_ttl(eh, qry, k->zname, KNOT_RRTYPE_NSEC, + qry->timestamp.tv_sec); + if (new_ttl_ < 0 || !kr_rank_test(eh->rank, KR_RANK_SECURE)) { + return "range search found stale or insecure entry"; + /* TODO: remove the stale record *and* retry, + * in case we haven't run off. Perhaps start by in_zone check. */ + } + if (new_ttl) { + *new_ttl = new_ttl_; + } + if (kwz_low) { + *kwz_low = (knot_db_val_t){ + .data = (uint8_t *)key_nsec.data + nwz_off, + .len = key_nsec.len - nwz_off, + }; /* CACHE_KEY_DEF */ + } + if (is_exact) { + /* Nothing else to do. */ + return NULL; + } + /* The NSEC starts strictly before our target name; + * now check that it still belongs into that zone. */ + const bool nsec_in_zone = key_nsec.len >= nwz_off + /* CACHE_KEY_DEF */ + && memcmp(key.data, key_nsec.data, nwz_off) == 0; + if (!nsec_in_zone) { + return "range search miss (!nsec_in_zone)"; + } + /* We know it starts before sname, so let's check the other end. + * 1. construct the key for the next name - kwz_hi. */ + /* it's *full* name ATM */ + const knot_rdata_t *next = (const knot_rdata_t *) + (eh->data + KR_CACHE_RR_COUNT_SIZE); + if (KR_CACHE_RR_COUNT_SIZE != 2 || get_uint16(eh->data) == 0) { + assert(false); + return "ERROR"; + /* TODO: more checks? */ + } + /* + WITH_VERBOSE { + VERBOSE_MSG(qry, "=> NSEC: next name: "); + kr_dname_print(next, "", "\n"); + } + */ + knot_dname_t ch_buf[KNOT_DNAME_MAXLEN]; + knot_dname_t *chs = kwz_high ? kwz_high->data : ch_buf; + if (!chs) { + assert(false); + return "EINVAL"; + } + { + /* Lower-case chs; see also RFC 6840 5.1. + * LATER(optim.): we do lots of copying etc. */ + knot_dname_t lower_buf[KNOT_DNAME_MAXLEN]; + ret = knot_dname_to_wire(lower_buf, next->data, + MIN(next->len, KNOT_DNAME_MAXLEN)); + if (ret < 0) { /* _ESPACE */ + return "range search found record with incorrect contents"; + } + knot_dname_to_lower(lower_buf); + ret = kr_dname_lf(chs, lower_buf, false); + } + if (ret) { + assert(false); + return "ERROR"; + } + knot_db_val_t kwz_hi = { /* skip the zone name */ + .data = chs + 1 + k->zlf_len, + .len = chs[0] - k->zlf_len, + }; + assert((ssize_t)(kwz_hi.len) >= 0); + /* 2. do the actual range check. */ + const knot_db_val_t kwz_sname = { + .data = (void *)/*const-cast*/(k->buf + 1 + nwz_off), + .len = k->buf[0] - k->zlf_len, + }; + assert((ssize_t)(kwz_sname.len) >= 0); + bool covers = /* we know for sure that the low end is before kwz_sname */ + 3 == kwz_between((knot_db_val_t){ NULL, 0 }, kwz_sname, kwz_hi); + if (!covers) { + return "range search miss (!covers)"; + } + if (kwz_high) { + *kwz_high = kwz_hi; + } + return NULL; +} + + +int nsec1_encloser(struct key *k, struct answer *ans, + const int sname_labels, int *clencl_labels, + knot_db_val_t *cover_low_kwz, knot_db_val_t *cover_hi_kwz, + const struct kr_query *qry, struct kr_cache *cache) +{ + static const int ESKIP = ABS(ENOENT); + /* Basic sanity check. */ + const bool ok = k && ans && clencl_labels && cover_low_kwz && cover_hi_kwz + && qry && cache; + if (!ok) { + assert(!EINVAL); + return kr_error(EINVAL); + } + + /* Find a previous-or-equal name+NSEC in cache covering the QNAME, + * checking TTL etc. */ + knot_db_val_t key = key_NSEC1(k, qry->sname, false); + knot_db_val_t val = { NULL, 0 }; + bool exact_match; + uint32_t new_ttl; + const char *err = find_leq_NSEC1(cache, qry, key, k, &val, + &exact_match, cover_low_kwz, cover_hi_kwz, &new_ttl); + if (err) { + VERBOSE_MSG(qry, "=> NSEC sname: %s\n", err); + return ESKIP; + } + + /* Get owner name of the record. */ + const knot_dname_t *owner; + knot_dname_t owner_buf[KNOT_DNAME_MAXLEN]; + if (exact_match) { + owner = qry->sname; + } else { + int ret = dname_wire_reconstruct(owner_buf, k, *cover_low_kwz); + if (unlikely(ret)) return ESKIP; + owner = owner_buf; + } + /* Basic checks OK -> materialize data. */ + { + const struct entry_h *nsec_eh = val.data; + int ret = entry2answer(ans, AR_NSEC, nsec_eh, knot_db_val_bound(val), + owner, KNOT_RRTYPE_NSEC, new_ttl); + if (ret) return kr_error(ret); + } + + /* Final checks, split for matching vs. covering our sname. */ + const knot_rrset_t *nsec_rr = ans->rrsets[AR_NSEC].set.rr; + const uint8_t *bm = knot_nsec_bitmap(nsec_rr->rrs.rdata); + uint16_t bm_size = knot_nsec_bitmap_len(nsec_rr->rrs.rdata); + assert(bm); + + if (exact_match) { + if (kr_nsec_bitmap_nodata_check(bm, bm_size, qry->stype, nsec_rr->owner) != 0) { + VERBOSE_MSG(qry, + "=> NSEC sname: match but failed type check\n"); + return ESKIP; + } + /* NODATA proven; just need to add SOA+RRSIG later */ + VERBOSE_MSG(qry, "=> NSEC sname: match proved NODATA, new TTL %d\n", + new_ttl); + ans->rcode = PKT_NODATA; + return kr_ok(); + } /* else */ + + /* Inexact match. First check if sname is delegated by that NSEC. */ + const int nsec_matched = knot_dname_matched_labels(nsec_rr->owner, qry->sname); + const bool is_sub = nsec_matched == knot_dname_labels(nsec_rr->owner, NULL); + if (is_sub && kr_nsec_children_in_zone_check(bm, bm_size) != 0) { + VERBOSE_MSG(qry, "=> NSEC sname: covered but delegated (or error)\n"); + return ESKIP; + } + /* NXDOMAIN proven *except* for wildcards. */ + WITH_VERBOSE(qry) { + auto_free char *owner_str = kr_dname_text(nsec_rr->owner), + *next_str = kr_dname_text(knot_nsec_next(nsec_rr->rrs.rdata)); + VERBOSE_MSG(qry, "=> NSEC sname: covered by: %s -> %s, new TTL %d\n", + owner_str, next_str, new_ttl); + } + + /* Find label count of the closest encloser. + * Both endpoints in an NSEC do exist (though possibly in a child zone) + * and any prefixes of those names as well (empty non-terminals), + * but nothing else exists inside this "triangle". + * + * Note that we have to lower-case the next name for comparison, + * even though we have canonicalized NSEC already; see RFC 6840 5.1. + * LATER(optim.): it might be faster to use the LFs we already have. + */ + knot_dname_t next[KNOT_DNAME_MAXLEN]; + int ret = knot_dname_to_wire(next, knot_nsec_next(nsec_rr->rrs.rdata), sizeof(next)); + if (ret < 0) { + assert(!ret); + return kr_error(ret); + } + knot_dname_to_lower(next); + *clencl_labels = MAX( + nsec_matched, + knot_dname_matched_labels(qry->sname, next) + ); + + /* Empty non-terminals don't need to have + * a matching NSEC record. */ + if (sname_labels == *clencl_labels) { + ans->rcode = PKT_NODATA; + VERBOSE_MSG(qry, + "=> NSEC sname: empty non-terminal by the same RR\n"); + } else { + ans->rcode = PKT_NXDOMAIN; + } + return kr_ok(); +} + +/** Verify non-existence after kwz_between() call. */ +static bool nonexistence_ok(int cmp, const knot_rrset_t *rrs) +{ + if (cmp == 3) { + return true; + } + if (cmp != 2) { + return false; + } + const uint8_t *bm = knot_nsec_bitmap(rrs->rrs.rdata); + uint16_t bm_size = knot_nsec_bitmap_len(rrs->rrs.rdata); + return kr_nsec_children_in_zone_check(bm, bm_size) != 0; +} + +int nsec1_src_synth(struct key *k, struct answer *ans, const knot_dname_t *clencl_name, + knot_db_val_t cover_low_kwz, knot_db_val_t cover_hi_kwz, + const struct kr_query *qry, struct kr_cache *cache) +{ + /* Construct key for the source of synthesis. */ + knot_db_val_t key = key_NSEC1(k, clencl_name, true); + const size_t nwz_off = key_nwz_off(k); + if (!key.data || key.len < nwz_off) { + assert(false); + return kr_error(1); + } + /* Check if our sname-covering NSEC also covers/matches SS. */ + knot_db_val_t kwz = { + .data = (uint8_t *)key.data + nwz_off, + .len = key.len - nwz_off, + }; + assert((ssize_t)(kwz.len) >= 0); + const int cmp = kwz_between(cover_low_kwz, kwz, cover_hi_kwz); + if (nonexistence_ok(cmp, ans->rrsets[AR_NSEC].set.rr)) { + VERBOSE_MSG(qry, "=> NSEC wildcard: covered by the same RR\n"); + return AR_SOA; + } + const knot_rrset_t *nsec_rr = NULL; /**< the wildcard proof NSEC */ + bool exact_match; /**< whether it matches the source of synthesis */ + if (cmp == 1) { + exact_match = true; + nsec_rr = ans->rrsets[AR_NSEC].set.rr; + } else { + /* Try to find the NSEC for SS. */ + knot_db_val_t val = { NULL, 0 }; + knot_db_val_t wild_low_kwz = { NULL, 0 }; + uint32_t new_ttl; + const char *err = find_leq_NSEC1(cache, qry, key, k, &val, + &exact_match, &wild_low_kwz, NULL, &new_ttl); + if (err) { + VERBOSE_MSG(qry, "=> NSEC wildcard: %s\n", err); + return kr_ok(); + } + /* Materialize the record into answer (speculatively). */ + knot_dname_t owner[KNOT_DNAME_MAXLEN]; + int ret = dname_wire_reconstruct(owner, k, wild_low_kwz); + if (ret) return kr_error(ret); + const struct entry_h *nsec_eh = val.data; + ret = entry2answer(ans, AR_WILD, nsec_eh, knot_db_val_bound(val), + owner, KNOT_RRTYPE_NSEC, new_ttl); + if (ret) return kr_error(ret); + nsec_rr = ans->rrsets[AR_WILD].set.rr; + } + + assert(nsec_rr); + const uint32_t new_ttl_log = + kr_verbose_status ? nsec_rr->ttl : -1; + const uint8_t *bm = knot_nsec_bitmap(nsec_rr->rrs.rdata); + uint16_t bm_size = knot_nsec_bitmap_len(nsec_rr->rrs.rdata); + int ret; + struct answer_rrset * const arw = &ans->rrsets[AR_WILD]; + if (!bm) { + assert(false); + ret = kr_error(1); + goto clean_wild; + } + if (!exact_match) { + /* Finish verification that the source of synthesis doesn't exist. */ + const int nsec_matched = + knot_dname_matched_labels(nsec_rr->owner, clencl_name); + /* we don't need to use the full source of synthesis ^ */ + const bool is_sub = + nsec_matched == knot_dname_labels(nsec_rr->owner, NULL); + if (is_sub && kr_nsec_children_in_zone_check(bm, bm_size) != 0) { + VERBOSE_MSG(qry, + "=> NSEC wildcard: covered but delegated (or error)\n"); + ret = kr_ok(); + goto clean_wild; + } + /* We have a record proving wildcard non-existence. */ + WITH_VERBOSE(qry) { + auto_free char *owner_str = kr_dname_text(nsec_rr->owner), + *next_str = kr_dname_text(knot_nsec_next(nsec_rr->rrs.rdata)); + VERBOSE_MSG(qry, "=> NSEC wildcard: covered by: %s -> %s, new TTL %d\n", + owner_str, next_str, new_ttl_log); + } + return AR_SOA; + } + + /* The wildcard exists. Find if it's NODATA - check type bitmap. */ + if (kr_nsec_bitmap_nodata_check(bm, bm_size, qry->stype, nsec_rr->owner) == 0) { + /* NODATA proven; just need to add SOA+RRSIG later */ + WITH_VERBOSE(qry) { + const char *msg_start = "=> NSEC wildcard: match proved NODATA"; + if (arw->set.rr) { + auto_free char *owner_str = kr_dname_text(nsec_rr->owner); + VERBOSE_MSG(qry, "%s: %s, new TTL %d\n", + msg_start, owner_str, new_ttl_log); + } else { + /* don't repeat the RR if it's the same */ + VERBOSE_MSG(qry, "%s, by the same RR\n", msg_start); + } + } + ans->rcode = PKT_NODATA; + return AR_SOA; + + } /* else */ + /* The data probably exists -> don't add this NSEC + * and (later) try to find the real wildcard data */ + VERBOSE_MSG(qry, "=> NSEC wildcard: should exist (or error)\n"); + ans->rcode = PKT_NOERROR; + ret = kr_ok(); +clean_wild: + if (arw->set.rr) { /* we may have matched AR_NSEC */ + knot_rrset_free(arw->set.rr, ans->mm); + arw->set.rr = NULL; + knot_rdataset_clear(&arw->sig_rds, ans->mm); + } + return ret; +} + diff --git a/lib/cache/nsec3.c b/lib/cache/nsec3.c new file mode 100644 index 0000000..d2ae72a --- /dev/null +++ b/lib/cache/nsec3.c @@ -0,0 +1,501 @@ +/* Copyright (C) 2018 CZ.NIC, z.s.p.o. <knot-dns@labs.nic.cz> + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <https://www.gnu.org/licenses/>. + */ + +/** @file + * Implementation of NSEC3 handling. Prototypes in ./impl.h + */ + +#include "lib/cache/impl.h" + +#include "contrib/base32hex.h" +#include "lib/dnssec/nsec.h" +#include "lib/layer/iterate.h" + +#include <libknot/rrtype/nsec3.h> + +static const knot_db_val_t VAL_EMPTY = { NULL, 0 }; + +/** Common part: write all but the NSEC3 hash. */ +static knot_db_val_t key_NSEC3_common(struct key *k, const knot_dname_t *zname, + const nsec_p_hash_t nsec_p_hash) +{ + int ret; + const bool ok = k && zname + && !(ret = kr_dname_lf(k->buf, zname, false)); + if (!ok) { + assert(false); + return VAL_EMPTY; + } + + /* CACHE_KEY_DEF: key == zone's dname_lf + '\0' + '3' + nsec_p hash (4B) + * + NSEC3 hash (20B == NSEC3_HASH_LEN binary!) + * LATER(optim.) nsec_p hash: perhaps 2B would give a sufficient probability + * of avoiding collisions. + */ + uint8_t *begin = k->buf + 1 + k->zlf_len; /* one byte after zone's zero */ + begin[0] = 0; + begin[1] = '3'; /* tag for NSEC3 */ + k->type = KNOT_RRTYPE_NSEC3; + memcpy(begin + 2, &nsec_p_hash, sizeof(nsec_p_hash)); + return (knot_db_val_t){ + .data = k->buf + 1, + .len = begin + 2 + sizeof(nsec_p_hash) - (k->buf + 1), + }; +} + +knot_db_val_t key_NSEC3(struct key *k, const knot_dname_t *nsec3_name, + const nsec_p_hash_t nsec_p_hash) +{ + knot_db_val_t val = key_NSEC3_common(k, nsec3_name /*only zname required*/, + nsec_p_hash); + if (!val.data) return val; + int len = base32hex_decode(nsec3_name + 1, nsec3_name[0], + knot_db_val_bound(val), KR_CACHE_KEY_MAXLEN - val.len); + if (len != NSEC3_HASH_LEN) { + return VAL_EMPTY; + } + val.len += len; + return val; +} + +/** Construct a string key for for NSEC3 predecessor-search, from an non-NSEC3 name. + * \note k->zlf_len and k->zname are assumed to have been correctly set */ +static knot_db_val_t key_NSEC3_name(struct key *k, const knot_dname_t *name, + const bool add_wildcard, const struct nsec_p *nsec_p) +{ + bool ok = k && name && nsec_p && nsec_p->raw; + if (!ok) return VAL_EMPTY; + knot_db_val_t val = key_NSEC3_common(k, k->zname, nsec_p->hash); + if (!val.data) return val; + + /* Make `name` point to correctly wildcarded owner name. */ + uint8_t buf[KNOT_DNAME_MAXLEN]; + int name_len; + if (add_wildcard) { + buf[0] = '\1'; + buf[1] = '*'; + name_len = knot_dname_to_wire(buf + 2, name, sizeof(buf) - 2); + if (name_len < 0) return VAL_EMPTY; /* wants wildcard but doesn't fit */ + name = buf; + name_len += 2; + } else { + name_len = knot_dname_size(name); + } + /* Append the NSEC3 hash. */ + const dnssec_binary_t dname = { + .size = name_len, + .data = (uint8_t *)/*const-cast*/name, + }; + + #if 0 // LATER(optim.): this requires a patched libdnssec - tries to realloc() + dnssec_binary_t hash = { + .size = KR_CACHE_KEY_MAXLEN - val.len, + .data = val.data + val.len, + }; + int ret = dnssec_nsec3_hash(&dname, &nsec_p->libknot, &hash); + if (ret != DNSSEC_EOK) return VAL_EMPTY; + assert(hash.size == NSEC3_HASH_LEN); + + #else + dnssec_binary_t hash = { .size = 0, .data = NULL }; + int ret = dnssec_nsec3_hash(&dname, &nsec_p->libknot, &hash); + if (ret != DNSSEC_EOK) return VAL_EMPTY; + if (hash.size != NSEC3_HASH_LEN || !hash.data) { + assert(false); + return VAL_EMPTY; + } + memcpy(knot_db_val_bound(val), hash.data, NSEC3_HASH_LEN); + free(hash.data); + #endif + + val.len += hash.size; + return val; +} + +/** Return h1 < h2, semantically on NSEC3 hashes. */ +static inline bool nsec3_hash_ordered(const uint8_t *h1, const uint8_t *h2) +{ + return memcmp(h1, h2, NSEC3_HASH_LEN) < 0; +} + +/** NSEC3 range search. + * + * \param key Pass output of key_NSEC3(k, ...) + * \param nsec_p Restrict to this NSEC3 parameter-set. + * \param value[out] The raw data of the NSEC3 cache record (optional; consistency checked). + * \param exact_match[out] Whether the key was matched exactly or just covered (optional). + * \param hash_low[out] Output the low end hash of covering NSEC3, pointing within DB (optional). + * \param new_ttl[out] New TTL of the NSEC3 (optional). + * \return Error message or NULL. + * \note The function itself does *no* bitmap checks, e.g. RFC 6840 sec. 4. + */ +static const char * find_leq_NSEC3(struct kr_cache *cache, const struct kr_query *qry, + const knot_db_val_t key, const struct key *k, const struct nsec_p *nsec_p, + knot_db_val_t *value, bool *exact_match, const uint8_t **hash_low, + uint32_t *new_ttl) +{ + /* Do the cache operation. */ + const size_t hash_off = key_nsec3_hash_off(k); + if (!key.data || key.len < hash_off) { + assert(false); + return "range search ERROR"; + } + knot_db_val_t key_found = key; + knot_db_val_t val = { NULL, 0 }; + int ret = cache_op(cache, read_leq, &key_found, &val); + /* ^^ LATER(optim.): incrementing key and doing less-than search + * would probably be slightly more efficient with LMDB, + * but the code complexity would grow considerably. */ + if (ret < 0) { + if (ret == kr_error(ENOENT)) { + return "range search miss"; + } else { + assert(false); + return "range search ERROR"; + } + } + if (value) { + *value = val; + } + /* Check consistency, TTL, rank. */ + const bool is_exact = (ret == 0); + if (exact_match) { + *exact_match = is_exact; + } + const struct entry_h *eh = entry_h_consistent_NSEC(val); + if (!eh) { + /* This might be just finding something else than NSEC3 entry, + * in case we searched before the very first one in the zone. */ + return "range search found inconsistent entry"; + } + /* Passing just zone name instead of owner. */ + int32_t new_ttl_ = get_new_ttl(eh, qry, k->zname, KNOT_RRTYPE_NSEC3, + qry->timestamp.tv_sec); + if (new_ttl_ < 0 || !kr_rank_test(eh->rank, KR_RANK_SECURE)) { + return "range search found stale or insecure entry"; + /* TODO: remove the stale record *and* retry, + * in case we haven't run off. Perhaps start by in_zone check. */ + } + if (new_ttl) { + *new_ttl = new_ttl_; + } + if (hash_low) { + *hash_low = (uint8_t *)key_found.data + hash_off; + } + if (is_exact) { + /* Nothing else to do. */ + return NULL; + } + /* The NSEC3 starts strictly before our target name; + * now check that it still belongs into that zone and chain. */ + const uint8_t *nsec_p_raw = eh->data + KR_CACHE_RR_COUNT_SIZE + + 2 /* RDLENGTH from rfc1034 */; + const int nsec_p_len = nsec_p_rdlen(nsec_p_raw); + const bool same_chain = key_found.len == hash_off + NSEC3_HASH_LEN + /* CACHE_KEY_DEF */ + && memcmp(key.data, key_found.data, hash_off) == 0 + /* exact comparison of NSEC3 parameters */ + && nsec_p_len == nsec_p_rdlen(nsec_p->raw) + && memcmp(nsec_p_raw, nsec_p->raw, nsec_p_len) == 0; + if (!same_chain) { + return "range search miss (!same_chain)"; + } + /* We know it starts before sname, so let's check the other end. + * A. find the next hash and check its length. */ + if (KR_CACHE_RR_COUNT_SIZE != 2 || get_uint16(eh->data) == 0) { + assert(false); + return "ERROR"; + /* TODO: more checks? Also, `next` computation is kinda messy. */ + } + const uint8_t *hash_next = nsec_p_raw + nsec_p_len + + sizeof(uint8_t) /* hash length from rfc5155 */; + if (hash_next[-1] != NSEC3_HASH_LEN) { + return "unexpected next hash length"; + } + /* B. do the actual range check. */ + const uint8_t * const hash_searched = (uint8_t *)key.data + hash_off; + bool covers = /* we know for sure that the low end is before the searched name */ + nsec3_hash_ordered(hash_searched, hash_next) + /* and the wrap-around case */ + || nsec3_hash_ordered(hash_next, (const uint8_t *)key_found.data + hash_off); + if (!covers) { + return "range search miss (!covers)"; + } + return NULL; +} + +/** Extract textual representation of NSEC3 hash from a cache key. + * \param text must have length at least NSEC3_HASH_TXT_LEN+1 (will get 0-terminated). */ +static void key_NSEC3_hash2text(const knot_db_val_t key, char *text) +{ + assert(key.data && key.len > NSEC3_HASH_LEN); + const uint8_t *hash_raw = knot_db_val_bound(key) - NSEC3_HASH_LEN; + /* CACHE_KEY_DEF ^^ */ + int len = base32hex_encode(hash_raw, NSEC3_HASH_LEN, (uint8_t *)text, + NSEC3_HASH_TXT_LEN); + assert(len == NSEC3_HASH_TXT_LEN); (void)len; + text[NSEC3_HASH_TXT_LEN] = '\0'; +} + +/** Reconstruct a name into a buffer (assuming length at least KNOT_DNAME_MAXLEN). + * \return kr_ok() or error code (<0). */ +static int dname_wire_reconstruct(knot_dname_t *buf, const knot_dname_t *zname, + const uint8_t *hash_raw) +{ + int len = base32hex_encode(hash_raw, NSEC3_HASH_LEN, buf + 1, NSEC3_HASH_TXT_LEN); + if (len != NSEC3_HASH_TXT_LEN) { + assert(false); + return kr_error(EINVAL); + } + buf[0] = len; + int ret = knot_dname_to_wire(buf + 1 + len, zname, KNOT_DNAME_MAXLEN - 1 - len); + return ret < 0 ? kr_error(ret) : kr_ok(); +} + +static void nsec3_hash2text(const knot_dname_t *owner, char *text) +{ + assert(owner[0] == NSEC3_HASH_TXT_LEN); + memcpy(text, owner + 1, MIN(owner[0], NSEC3_HASH_TXT_LEN)); + text[NSEC3_HASH_TXT_LEN] = '\0'; +} + +int nsec3_encloser(struct key *k, struct answer *ans, + const int sname_labels, int *clencl_labels, + const struct kr_query *qry, struct kr_cache *cache) +{ + static const int ESKIP = ABS(ENOENT); + /* Basic sanity check. */ + const bool ok = k && k->zname && ans && clencl_labels + && qry && cache; + if (!ok) { + assert(!EINVAL); + return kr_error(EINVAL); + } + + /*** Find the closest encloser - cycle: name starting at sname, + * proceeding while longer than zname, shortening by one label on step. + * We need a pair where a name doesn't exist *and* its parent does. */ + /* LATER(optim.): perhaps iterate in the other order - that + * should help significantly against deep queries where we have + * a shallow proof in the cache. We can also optimize by using + * only exact search unless we had a match in the previous iteration. */ + const int zname_labels = knot_dname_labels(k->zname, NULL); + int last_nxproven_labels = -1; + const knot_dname_t *name = qry->sname; + for (int name_labels = sname_labels; name_labels >= zname_labels; + --name_labels, name += 1 + name[0]) { + /* Find a previous-or-equal NSEC3 in cache covering the name, + * checking TTL etc. */ + const knot_db_val_t key = key_NSEC3_name(k, name, false, &ans->nsec_p); + if (!key.data) continue; + WITH_VERBOSE(qry) { + char hash_txt[NSEC3_HASH_TXT_LEN + 1]; + key_NSEC3_hash2text(key, hash_txt); + VERBOSE_MSG(qry, "=> NSEC3 depth %d: hash %s\n", + name_labels - zname_labels, hash_txt); + } + knot_db_val_t val = { NULL, 0 }; + bool exact_match; + uint32_t new_ttl; + const uint8_t *hash_low; + const char *err = find_leq_NSEC3(cache, qry, key, k, &ans->nsec_p, &val, + &exact_match, &hash_low, &new_ttl); + if (err) { + WITH_VERBOSE(qry) { + auto_free char *name_str = kr_dname_text(name); + VERBOSE_MSG(qry, "=> NSEC3 encloser error for %s: %s\n", + name_str, err); + } + continue; + } + if (exact_match && name_labels != sname_labels + && name_labels + 1 != last_nxproven_labels) { + /* This name exists (checked rank and TTL), and it's + * neither of the two interesting cases, so we do not + * keep searching for non-existence above this name. */ + VERBOSE_MSG(qry, + "=> NSEC3 encloser: only found existence of an ancestor\n"); + return ESKIP; + } + /* Optimization: avoid the rest of the last iteration if pointless. */ + if (!exact_match && name_labels == zname_labels + && last_nxproven_labels != name_labels + 1) { + break; + } + + /* Basic checks OK -> materialize data, cleaning any previous + * records on that answer index (unsuccessful attempts). */ + knot_dname_t owner[KNOT_DNAME_MAXLEN]; + { + int ret = dname_wire_reconstruct(owner, k->zname, hash_low); + if (unlikely(ret)) continue; + } + const int ans_id = (exact_match && name_labels + 1 == last_nxproven_labels) + ? AR_CPE : AR_NSEC; + { + const struct entry_h *nsec_eh = val.data; + memset(&ans->rrsets[ans_id], 0, sizeof(ans->rrsets[ans_id])); + int ret = entry2answer(ans, ans_id, nsec_eh, knot_db_val_bound(val), + owner, KNOT_RRTYPE_NSEC3, new_ttl); + if (ret) return kr_error(ret); + } + + if (!exact_match) { + /* Non-existence proven, but we don't know if `name` + * is the next closer name. + * Note: we don't need to check for the sname being + * delegated away by this record, as with NSEC3 only + * *exact* match on an ancestor could do that. */ + last_nxproven_labels = name_labels; + WITH_VERBOSE(qry) { + char hash_low_txt[NSEC3_HASH_TXT_LEN + 1]; + nsec3_hash2text(owner, hash_low_txt); + VERBOSE_MSG(qry, + "=> NSEC3 depth %d: covered by %s -> TODO, new TTL %d\n", + name_labels - zname_labels, hash_low_txt, new_ttl); + } + continue; + } + + /* Exactly matched NSEC3: two cases, one after another. */ + const knot_rrset_t *nsec_rr = ans->rrsets[ans_id].set.rr; + const uint8_t *bm = knot_nsec3_bitmap(nsec_rr->rrs.rdata); + uint16_t bm_size = knot_nsec3_bitmap_len(nsec_rr->rrs.rdata); + assert(bm); + if (name_labels == sname_labels) { + if (kr_nsec_bitmap_nodata_check(bm, bm_size, qry->stype, + nsec_rr->owner) != 0) { + VERBOSE_MSG(qry, + "=> NSEC3 sname: match but failed type check\n"); + return ESKIP; + } + /* NODATA proven; just need to add SOA+RRSIG later */ + VERBOSE_MSG(qry, + "=> NSEC3 sname: match proved NODATA, new TTL %d\n", + new_ttl); + ans->rcode = PKT_NODATA; + return kr_ok(); + + } /* else */ + + assert(name_labels + 1 == last_nxproven_labels); + if (kr_nsec_children_in_zone_check(bm, bm_size) != 0) { + VERBOSE_MSG(qry, + "=> NSEC3 encloser: found but delegated (or error)\n"); + return ESKIP; + } + /* NXDOMAIN proven *except* for wildcards. */ + WITH_VERBOSE(qry) { + auto_free char *name_str = kr_dname_text(name); + VERBOSE_MSG(qry, + "=> NSEC3 encloser: confirmed as %s, new TTL %d\n", + name_str, new_ttl); + } + *clencl_labels = name_labels; + ans->rcode = PKT_NXDOMAIN; + /* Avoid repeated NSEC3 - remove either if the hashes match. + * This is very unlikely in larger zones: 1/size (per attempt). + * Well, deduplication would happen anyway when the answer + * from cache is read by kresd (internally). */ + if (unlikely(0 == memcmp(ans->rrsets[AR_NSEC].set.rr->owner + 1, + ans->rrsets[AR_CPE ].set.rr->owner + 1, + NSEC3_HASH_LEN))) { + memset(&ans->rrsets[AR_CPE], 0, sizeof(ans->rrsets[AR_CPE])); + /* LATER(optim.): perhaps check this earlier and avoid some work? */ + } + return kr_ok(); + } + + /* We've ran out of options. */ + if (last_nxproven_labels > 0) { + /* We didn't manage to prove existence of the closest encloser, + * meaning the only chance left is a *positive* wildcard record. */ + *clencl_labels = last_nxproven_labels - 1; + ans->rcode = PKT_NXDOMAIN; + /* FIXME: review */ + } + return ESKIP; +} + +int nsec3_src_synth(struct key *k, struct answer *ans, const knot_dname_t *clencl_name, + const struct kr_query *qry, struct kr_cache *cache) +{ + /* Find a previous-or-equal NSEC3 in cache covering or matching + * the source of synthesis, checking TTL etc. */ + const knot_db_val_t key = key_NSEC3_name(k, clencl_name, true, &ans->nsec_p); + if (!key.data) return kr_error(1); + WITH_VERBOSE(qry) { + char hash_txt[NSEC3_HASH_TXT_LEN + 1]; + key_NSEC3_hash2text(key, hash_txt); + VERBOSE_MSG(qry, "=> NSEC3 wildcard: hash %s\n", hash_txt); + } + knot_db_val_t val = { NULL, 0 }; + bool exact_match; + uint32_t new_ttl; + const uint8_t *hash_low; + const char *err = find_leq_NSEC3(cache, qry, key, k, &ans->nsec_p, &val, + &exact_match, &hash_low, &new_ttl); + if (err) { + VERBOSE_MSG(qry, "=> NSEC3 wildcard: %s\n", err); + return kr_ok(); + } + + /* LATER(optim.): avoid duplicities in answer. */ + + /* Basic checks OK -> materialize the data (speculatively). */ + knot_dname_t owner[KNOT_DNAME_MAXLEN]; + { + int ret = dname_wire_reconstruct(owner, k->zname, hash_low); + if (unlikely(ret)) return kr_ok(); + const struct entry_h *nsec_eh = val.data; + ret = entry2answer(ans, AR_WILD, nsec_eh, knot_db_val_bound(val), + owner, KNOT_RRTYPE_NSEC3, new_ttl); + if (ret) return kr_error(ret); + } + const knot_rrset_t *nsec_rr = ans->rrsets[AR_WILD].set.rr; + + if (!exact_match) { + /* The record proves wildcard non-existence. */ + WITH_VERBOSE(qry) { + char hash_low_txt[NSEC3_HASH_TXT_LEN + 1]; + nsec3_hash2text(owner, hash_low_txt); + VERBOSE_MSG(qry, + "=> NSEC3 wildcard: covered by %s -> TODO, new TTL %d\n", + hash_low_txt, new_ttl); + } + return AR_SOA; + } + + /* The wildcard exists. Find if it's NODATA - check type bitmap. */ + const uint8_t *bm = knot_nsec3_bitmap(nsec_rr->rrs.rdata); + uint16_t bm_size = knot_nsec3_bitmap_len(nsec_rr->rrs.rdata); + assert(bm); + if (kr_nsec_bitmap_nodata_check(bm, bm_size, qry->stype, nsec_rr->owner) == 0) { + /* NODATA proven; just need to add SOA+RRSIG later */ + VERBOSE_MSG(qry, "=> NSEC3 wildcard: match proved NODATA, new TTL %d\n", + new_ttl); + ans->rcode = PKT_NODATA; + return AR_SOA; + + } /* else */ + /* The data probably exists -> don't add this NSEC3 + * and (later) try to find the real wildcard data */ + VERBOSE_MSG(qry, "=> NSEC3 wildcard: should exist (or error)\n"); + ans->rcode = PKT_NOERROR; + memset(&ans->rrsets[AR_WILD], 0, sizeof(ans->rrsets[AR_WILD])); + return kr_ok(); +} + diff --git a/lib/cache/peek.c b/lib/cache/peek.c new file mode 100644 index 0000000..1af1627 --- /dev/null +++ b/lib/cache/peek.c @@ -0,0 +1,724 @@ +/* Copyright (C) 2018 CZ.NIC, z.s.p.o. <knot-dns@labs.nic.cz> + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <https://www.gnu.org/licenses/>. + */ + +#include "lib/cache/impl.h" + +#include "lib/dnssec/ta.h" +#include "lib/layer/iterate.h" + +/* The whole file only exports peek_nosync(). + * Forwards for larger chunks of code: */ + +static int found_exact_hit(kr_layer_t *ctx, knot_pkt_t *pkt, knot_db_val_t val, + uint8_t lowest_rank); +static int closest_NS(struct kr_cache *cache, struct key *k, entry_list_t el, + struct kr_query *qry, bool only_NS, bool is_DS); +static int answer_simple_hit(kr_layer_t *ctx, knot_pkt_t *pkt, uint16_t type, + const struct entry_h *eh, const void *eh_bound, uint32_t new_ttl); +static int try_wild(struct key *k, struct answer *ans, const knot_dname_t *clencl_name, + uint16_t type, uint8_t lowest_rank, + const struct kr_query *qry, struct kr_cache *cache); + +static int peek_encloser( + struct key *k, struct answer *ans, int sname_labels, + uint8_t lowest_rank, const struct kr_query *qry, struct kr_cache *cache); + + +static int nsec_p_init(struct nsec_p *nsec_p, knot_db_val_t nsec_p_entry, bool with_knot) +{ + const size_t stamp_len = sizeof(uint32_t); + if (nsec_p_entry.len <= stamp_len) { /* plain NSEC if equal */ + nsec_p->raw = NULL; + nsec_p->hash = 0; + return kr_ok(); + } + nsec_p->raw = (uint8_t *)nsec_p_entry.data + stamp_len; + nsec_p->hash = nsec_p_mkHash(nsec_p->raw); + if (!with_knot) return kr_ok(); + /* Convert NSEC3 params to another format. */ + const dnssec_binary_t rdata = { + .size = nsec_p_rdlen(nsec_p->raw), + .data = (uint8_t *)/*const-cast*/nsec_p->raw, + }; + int ret = dnssec_nsec3_params_from_rdata(&nsec_p->libknot, &rdata); + return ret == DNSSEC_EOK ? kr_ok() : kr_error(ret); +} + +static void nsec_p_cleanup(struct nsec_p *nsec_p) +{ + dnssec_binary_free(&nsec_p->libknot.salt); + /* We don't really need to clear it, but it's not large. (`salt` zeroed above) */ + memset(nsec_p, 0, sizeof(*nsec_p)); +} + +/** Compute new TTL for nsec_p entry, using SOA serial arith. + * \param new_ttl (optionally) write the new TTL (even if negative) + * \return error code, e.g. kr_error(ESTALE) */ +static int nsec_p_ttl(knot_db_val_t entry, const uint32_t timestamp, int32_t *new_ttl) +{ + if (!entry.data) { + assert(!EINVAL); + return kr_error(EINVAL); + } + uint32_t stamp; + if (!entry.len) { + return kr_error(ENOENT); + } + if (entry.len < sizeof(stamp)) { + assert(!EILSEQ); + return kr_error(EILSEQ); + } + memcpy(&stamp, entry.data, sizeof(stamp)); + int32_t newttl = stamp - timestamp; + if (new_ttl) *new_ttl = newttl; + return newttl < 0 ? kr_error(ESTALE) : kr_ok(); +} + +static uint8_t get_lowest_rank(const struct kr_request *req, const struct kr_query *qry) +{ + /* TODO: move rank handling into the iterator (DNSSEC_* flags)? */ + const bool allow_unverified = + knot_wire_get_cd(req->qsource.packet->wire) || qry->flags.STUB; + /* in stub mode we don't trust RRs anyway ^^ */ + if (qry->flags.NONAUTH) { + return KR_RANK_INITIAL; + /* Note: there's little sense in validation status for non-auth records. + * In case of using NONAUTH to get NS IPs, knowing that you ask correct + * IP doesn't matter much for security; it matters whether you can + * validate the answers from the NS. + */ + } else if (!allow_unverified) { + /* Records not present under any TA don't have their security + * verified at all, so we also accept low ranks in that case. */ + const bool ta_covers = kr_ta_covers_qry(req->ctx, qry->sname, qry->stype); + /* ^ TODO: performance? TODO: stype - call sites */ + if (ta_covers) { + return KR_RANK_INSECURE | KR_RANK_AUTH; + } /* else falltrhough */ + } + return KR_RANK_INITIAL | KR_RANK_AUTH; +} + + +/** Almost whole .produce phase for the cache module. + * \note we don't transition to KR_STATE_FAIL even in case of "unexpected errors". + */ +int peek_nosync(kr_layer_t *ctx, knot_pkt_t *pkt) +{ + struct kr_request *req = ctx->req; + struct kr_query *qry = req->current_query; + struct kr_cache *cache = &req->ctx->cache; + + struct key k_storage, *k = &k_storage; + int ret = kr_dname_lf(k->buf, qry->sname, false); + if (unlikely(ret)) { + assert(false); + return ctx->state; + } + + const uint8_t lowest_rank = get_lowest_rank(req, qry); + + /**** 1. find the name or the closest (available) zone, not considering wildcards + **** 1a. exact name+type match (can be negative answer in insecure zones) */ + { + knot_db_val_t key = key_exact_type_maypkt(k, qry->stype); + knot_db_val_t val = { NULL, 0 }; + ret = cache_op(cache, read, &key, &val, 1); + if (!ret) { + /* found an entry: test conditions, materialize into pkt, etc. */ + ret = found_exact_hit(ctx, pkt, val, lowest_rank); + } + } + if (ret && ret != -abs(ENOENT)) { + VERBOSE_MSG(qry, "=> exact hit error: %d %s\n", ret, kr_strerror(ret)); + assert(false); + return ctx->state; + } else if (!ret) { + return KR_STATE_DONE; + } + + /**** 1b. otherwise, find the longest prefix zone/xNAME (with OK time+rank). [...] */ + k->zname = qry->sname; + ret = kr_dname_lf(k->buf, k->zname, false); /* LATER(optim.): probably remove */ + if (unlikely(ret)) { + assert(false); + return ctx->state; + } + entry_list_t el; + ret = closest_NS(cache, k, el, qry, false, qry->stype == KNOT_RRTYPE_DS); + if (ret) { + assert(ret == kr_error(ENOENT)); + if (ret != kr_error(ENOENT) || !el[0].len) { + return ctx->state; + } + } + switch (k->type) { + case KNOT_RRTYPE_CNAME: { + const knot_db_val_t v = el[EL_CNAME]; + assert(v.data && v.len); + const int32_t new_ttl = get_new_ttl(v.data, qry, qry->sname, + KNOT_RRTYPE_CNAME, qry->timestamp.tv_sec); + ret = answer_simple_hit(ctx, pkt, KNOT_RRTYPE_CNAME, v.data, + knot_db_val_bound(v), new_ttl); + /* TODO: ^^ cumbersome code; we also recompute the TTL */ + return ret == kr_ok() ? KR_STATE_DONE : ctx->state; + } + case KNOT_RRTYPE_DNAME: + VERBOSE_MSG(qry, "=> DNAME not supported yet\n"); // LATER + return ctx->state; + } + + /* We have to try proving from NSEC*. */ + auto_free char *log_zname = NULL; + WITH_VERBOSE(qry) { + log_zname = kr_dname_text(k->zname); + if (!el[0].len) { + VERBOSE_MSG(qry, "=> no NSEC* cached for zone: %s\n", log_zname); + } + } + +#if 0 + if (!eh) { /* fall back to root hints? */ + ret = kr_zonecut_set_sbelt(req->ctx, &qry->zone_cut); + if (ret) return ctx->state; + assert(!qry->zone_cut.parent); + + //VERBOSE_MSG(qry, "=> using root hints\n"); + //qry->flags.AWAIT_CUT = false; + return ctx->state; + } + + /* Now `eh` points to the closest NS record that we've found, + * and that's the only place to start - we may either find + * a negative proof or we may query upstream from that point. */ + kr_zonecut_set(&qry->zone_cut, k->zname); + ret = kr_make_query(qry, pkt); // TODO: probably not yet - qname minimization + if (ret) return ctx->state; +#endif + + /** Structure for collecting multiple NSEC* + RRSIG records, + * in preparation for the answer, and for tracking the progress. */ + struct answer ans; + memset(&ans, 0, sizeof(ans)); + ans.mm = &pkt->mm; + const int sname_labels = knot_dname_labels(qry->sname, NULL); + + /* Try the NSEC* parameters in order, until success. + * Let's not mix different parameters for NSEC* RRs in a single proof. */ + for (int i = 0; ;) { + int32_t log_new_ttl = -123456789; /* visually recognizable value */ + ret = nsec_p_ttl(el[i], qry->timestamp.tv_sec, &log_new_ttl); + if (!ret || VERBOSE_STATUS) { + nsec_p_init(&ans.nsec_p, el[i], !ret); + } + if (ret) { + VERBOSE_MSG(qry, "=> skipping zone: %s, %s, hash %x;" + "new TTL %d, ret %d\n", + log_zname, (ans.nsec_p.raw ? "NSEC3" : "NSEC"), + (unsigned)ans.nsec_p.hash, (int)log_new_ttl, ret); + /* no need for nsec_p_cleanup() in this case */ + goto cont; + } + VERBOSE_MSG(qry, "=> trying zone: %s, %s, hash %x\n", + log_zname, (ans.nsec_p.raw ? "NSEC3" : "NSEC"), + (unsigned)ans.nsec_p.hash); + /**** 2. and 3. inside */ + ret = peek_encloser(k, &ans, sname_labels, + lowest_rank, qry, cache); + nsec_p_cleanup(&ans.nsec_p); + if (!ret) break; + if (ret < 0) return ctx->state; + cont: + /* Otherwise we try another nsec_p, if available. */ + if (++i == ENTRY_APEX_NSECS_CNT) return ctx->state; + /* clear possible partial answers in `ans` (no need to deallocate) */ + ans.rcode = 0; + memset(&ans.rrsets, 0, sizeof(ans.rrsets)); + } + + /**** 4. add SOA iff needed */ + if (ans.rcode != PKT_NOERROR) { + /* Assuming k->buf still starts with zone's prefix, + * look up the SOA in cache. */ + k->buf[0] = k->zlf_len; + knot_db_val_t key = key_exact_type(k, KNOT_RRTYPE_SOA); + knot_db_val_t val = { NULL, 0 }; + ret = cache_op(cache, read, &key, &val, 1); + const struct entry_h *eh; + if (ret || !(eh = entry_h_consistent(val, KNOT_RRTYPE_SOA))) { + assert(ret); /* only want to catch `eh` failures */ + VERBOSE_MSG(qry, "=> SOA missed\n"); + return ctx->state; + } + /* Check if the record is OK. */ + int32_t new_ttl = get_new_ttl(eh, qry, k->zname, KNOT_RRTYPE_SOA, + qry->timestamp.tv_sec); + if (new_ttl < 0 || eh->rank < lowest_rank || eh->is_packet) { + VERBOSE_MSG(qry, "=> SOA unfit %s: rank 0%.2o, new TTL %d\n", + (eh->is_packet ? "packet" : "RR"), + eh->rank, new_ttl); + return ctx->state; + } + /* Add the SOA into the answer. */ + ret = entry2answer(&ans, AR_SOA, eh, knot_db_val_bound(val), + k->zname, KNOT_RRTYPE_SOA, new_ttl); + if (ret) return ctx->state; + } + + /* Find our target RCODE. */ + int real_rcode; + switch (ans.rcode) { + case PKT_NODATA: + case PKT_NOERROR: /* positive wildcarded response */ + real_rcode = KNOT_RCODE_NOERROR; + break; + case PKT_NXDOMAIN: + real_rcode = KNOT_RCODE_NXDOMAIN; + break; + default: + assert(false); + case 0: /* i.e. nothing was found */ + /* LATER(optim.): zone cut? */ + VERBOSE_MSG(qry, "=> cache miss\n"); + return ctx->state; + } + + if (pkt_renew(pkt, qry->sname, qry->stype) + || knot_pkt_begin(pkt, KNOT_ANSWER) + ) { + assert(false); + return ctx->state; + } + knot_wire_set_rcode(pkt->wire, real_rcode); + + bool expiring = false; // TODO + VERBOSE_MSG(qry, "=> writing RRsets: "); + for (int i = 0; i < sizeof(ans.rrsets) / sizeof(ans.rrsets[0]); ++i) { + if (i == 1) knot_pkt_begin(pkt, KNOT_AUTHORITY); + if (!ans.rrsets[i].set.rr) continue; + expiring = expiring || ans.rrsets[i].set.expiring; + ret = pkt_append(pkt, &ans.rrsets[i], ans.rrsets[i].set.rank); + if (ret) { + assert(false); + return ctx->state; + } + kr_log_verbose(kr_rank_test(ans.rrsets[i].set.rank, KR_RANK_SECURE) + ? "+" : "-"); + } + kr_log_verbose("\n"); + + /* Finishing touches. */ + struct kr_qflags * const qf = &qry->flags; + qf->EXPIRING = expiring; + qf->CACHED = true; + qf->NO_MINIMIZE = true; + + return KR_STATE_DONE; +} + +/** + * This is where the high-level "business logic" of aggressive cache is. + * \return 0: success (may need SOA); >0: try other nsec_p; <0: exit cache immediately. + */ +static int peek_encloser( + struct key *k, struct answer *ans, const int sname_labels, + uint8_t lowest_rank, const struct kr_query *qry, struct kr_cache *cache) +{ + /** Start of NSEC* covering the sname; + * it's part of key - the one within zone (read only) */ + knot_db_val_t cover_low_kwz = { NULL, 0 }; + knot_dname_t cover_hi_storage[KNOT_DNAME_MAXLEN]; + /** End of NSEC* covering the sname. */ + knot_db_val_t cover_hi_kwz = { + .data = cover_hi_storage, + .len = sizeof(cover_hi_storage), + }; + + /**** 2. Find a closest (provable) encloser (of sname). */ + int clencl_labels = -1; + bool clencl_is_tentative = false; + if (!ans->nsec_p.raw) { /* NSEC */ + int ret = nsec1_encloser(k, ans, sname_labels, &clencl_labels, + &cover_low_kwz, &cover_hi_kwz, qry, cache); + if (ret) return ret; + } else { + int ret = nsec3_encloser(k, ans, sname_labels, &clencl_labels, + qry, cache); + clencl_is_tentative = ret == ABS(ENOENT) && clencl_labels >= 0; + /* ^^ Last chance: *positive* wildcard record under this clencl. */ + if (ret && !clencl_is_tentative) return ret; + } + + /* We should have either a match or a cover at this point. */ + if (ans->rcode != PKT_NODATA && ans->rcode != PKT_NXDOMAIN) { + assert(false); + return kr_error(EINVAL); + } + const bool ncloser_covered = ans->rcode == PKT_NXDOMAIN; + + /** Name of the closest (provable) encloser. */ + const knot_dname_t *clencl_name = qry->sname; + for (int l = sname_labels; l > clencl_labels; --l) + clencl_name = knot_wire_next_label(clencl_name, NULL); + + /**** 3. source of synthesis checks, in case the next closer name was covered. + **** 3a. We want to query for NSEC* of source of synthesis (SS) or its + * predecessor, providing us with a proof of its existence or non-existence. */ + if (ncloser_covered && !ans->nsec_p.raw) { + int ret = nsec1_src_synth(k, ans, clencl_name, + cover_low_kwz, cover_hi_kwz, qry, cache); + if (ret == AR_SOA) return 0; + assert(ret <= 0); + if (ret) return ret; + + } else if (ncloser_covered && ans->nsec_p.raw && !clencl_is_tentative) { + int ret = nsec3_src_synth(k, ans, clencl_name, qry, cache); + if (ret == AR_SOA) return 0; + assert(ret <= 0); + if (ret) return ret; + + } /* else (!ncloser_covered) so no wildcard checks needed, + * as we proved that sname exists. */ + + /**** 3b. find wildcarded answer, if next closer name was covered + * and we don't have a full proof yet. (common for NSEC*) */ + if (!ncloser_covered) + return kr_ok(); /* decrease indentation */ + /* Construct key for exact qry->stype + source of synthesis. */ + int ret = kr_dname_lf(k->buf, clencl_name, true); + if (ret) { + assert(!ret); + return kr_error(ret); + } + const uint16_t types[] = { qry->stype, KNOT_RRTYPE_CNAME }; + for (int i = 0; i < (2 - (qry->stype == KNOT_RRTYPE_CNAME)); ++i) { + ret = try_wild(k, ans, clencl_name, types[i], + lowest_rank, qry, cache); + if (ret == kr_ok()) { + return kr_ok(); + } else if (ret != -ABS(ENOENT) && ret != -ABS(ESTALE)) { + assert(false); + return kr_error(ret); + } + /* else continue */ + } + /* Neither attempt succeeded, but the NSEC* proofs were found, + * so skip trying other parameters, as it seems very unlikely + * to turn out differently than by the same wildcard search. */ + return -ABS(ENOENT); +} + + +static int answer_simple_hit(kr_layer_t *ctx, knot_pkt_t *pkt, uint16_t type, + const struct entry_h *eh, const void *eh_bound, uint32_t new_ttl) +#define CHECK_RET(ret) do { \ + if ((ret) < 0) { assert(false); return kr_error((ret)); } \ +} while (false) +{ + struct kr_request *req = ctx->req; + struct kr_query *qry = req->current_query; + + /* All OK, so start constructing the (pseudo-)packet. */ + int ret = pkt_renew(pkt, qry->sname, qry->stype); + CHECK_RET(ret); + + /* Materialize the sets for the answer in (pseudo-)packet. */ + struct answer ans; + memset(&ans, 0, sizeof(ans)); + ans.mm = &pkt->mm; + ret = entry2answer(&ans, AR_ANSWER, eh, eh_bound, + qry->sname, type, new_ttl); + CHECK_RET(ret); + /* Put links to the materialized data into the pkt. */ + ret = pkt_append(pkt, &ans.rrsets[AR_ANSWER], eh->rank); + CHECK_RET(ret); + + /* Finishing touches. */ + struct kr_qflags * const qf = &qry->flags; + qf->EXPIRING = is_expiring(eh->ttl, new_ttl); + qf->CACHED = true; + qf->NO_MINIMIZE = true; + qf->DNSSEC_INSECURE = kr_rank_test(eh->rank, KR_RANK_INSECURE); + if (qf->DNSSEC_INSECURE) { + qf->DNSSEC_WANT = false; + } + VERBOSE_MSG(qry, "=> satisfied by exact %s: rank 0%.2o, new TTL %d\n", + (type == KNOT_RRTYPE_CNAME ? "CNAME" : "RRset"), + eh->rank, new_ttl); + return kr_ok(); +} +#undef CHECK_RET + + +/** TODO: description; see the single call site for now. */ +static int found_exact_hit(kr_layer_t *ctx, knot_pkt_t *pkt, knot_db_val_t val, + uint8_t lowest_rank) +{ + struct kr_request *req = ctx->req; + struct kr_query *qry = req->current_query; + + int ret = entry_h_seek(&val, qry->stype); + if (ret) return ret; + const struct entry_h *eh = entry_h_consistent(val, qry->stype); + if (!eh) { + assert(false); + return kr_error(ENOENT); + // LATER: recovery in case of error, perhaps via removing the entry? + // LATER(optim): pehaps optimize the zone cut search + } + + int32_t new_ttl = get_new_ttl(eh, qry, qry->sname, qry->stype, + qry->timestamp.tv_sec); + if (new_ttl < 0 || eh->rank < lowest_rank) { + /* Positive record with stale TTL or bad rank. + * LATER(optim.): It's unlikely that we find a negative one, + * so we might theoretically skip all the cache code. */ + + VERBOSE_MSG(qry, "=> skipping exact %s: rank 0%.2o (min. 0%.2o), new TTL %d\n", + eh->is_packet ? "packet" : "RR", eh->rank, lowest_rank, new_ttl); + return kr_error(ENOENT); + } + + const uint8_t *eh_bound = knot_db_val_bound(val); + if (eh->is_packet) { + /* Note: we answer here immediately, even if it's (theoretically) + * possible that we could generate a higher-security negative proof. + * Rank is high-enough so we take it to save time searching. */ + return answer_from_pkt (ctx, pkt, qry->stype, eh, eh_bound, new_ttl); + } else { + return answer_simple_hit(ctx, pkt, qry->stype, eh, eh_bound, new_ttl); + } +} + + +/** Try to satisfy via wildcard (positively). See the single call site. */ +static int try_wild(struct key *k, struct answer *ans, const knot_dname_t *clencl_name, + const uint16_t type, const uint8_t lowest_rank, + const struct kr_query *qry, struct kr_cache *cache) +{ + knot_db_val_t key = key_exact_type(k, type); + /* Find the record. */ + knot_db_val_t val = { NULL, 0 }; + int ret = cache_op(cache, read, &key, &val, 1); + if (!ret) { + ret = entry_h_seek(&val, type); + } + if (ret) { + if (ret != -ABS(ENOENT)) { + VERBOSE_MSG(qry, "=> wildcard: hit error %d %s\n", + ret, strerror(abs(ret))); + assert(false); + } + WITH_VERBOSE(qry) { + auto_free char *clencl_str = kr_dname_text(clencl_name), + *type_str = kr_rrtype_text(type); + VERBOSE_MSG(qry, "=> wildcard: not found: *.%s %s\n", + clencl_str, type_str); + } + return ret; + } + /* Check if the record is OK. */ + const struct entry_h *eh = entry_h_consistent(val, type); + if (!eh) { + assert(false); + return kr_error(ret); + // LATER: recovery in case of error, perhaps via removing the entry? + } + int32_t new_ttl = get_new_ttl(eh, qry, qry->sname, type, qry->timestamp.tv_sec); + /* ^^ here we use the *expanded* wildcard name */ + if (new_ttl < 0 || eh->rank < lowest_rank || eh->is_packet) { + /* Wildcard record with stale TTL, bad rank or packet. */ + VERBOSE_MSG(qry, "=> wildcard: skipping %s, rank 0%.2o, new TTL %d\n", + eh->is_packet ? "packet" : "RR", eh->rank, new_ttl); + return -ABS(ESTALE); + } + /* Add the RR into the answer. */ + ret = entry2answer(ans, AR_ANSWER, eh, knot_db_val_bound(val), + qry->sname, type, new_ttl); + VERBOSE_MSG(qry, "=> wildcard: answer expanded, ret = %d, new TTL %d\n", + ret, (int)new_ttl); + if (ret) return kr_error(ret); + ans->rcode = PKT_NOERROR; + return kr_ok(); +} + +int kr_cache_closest_apex(struct kr_cache *cache, const knot_dname_t *name, bool is_DS, + knot_dname_t ** apex) +{ + if (!cache || !cache->db || !name || !apex || *apex) { + assert(!EINVAL); + return kr_error(EINVAL); + } + struct key k_storage, *k = &k_storage; + int ret = kr_dname_lf(k->buf, name, false); + if (ret) + return kr_error(ret); + entry_list_t el_; + k->zname = name; + ret = closest_NS(cache, k, el_, NULL, true, is_DS); + if (ret && ret != -abs(ENOENT)) + return ret; + *apex = knot_dname_copy(k->zname, NULL); + if (!*apex) + return kr_error(ENOMEM); + return kr_ok(); +} + +/** \internal for closest_NS. Check suitability of a single entry, setting k->type if OK. + * \return error code, negative iff whole list should be skipped. + */ +static int check_NS_entry(struct key *k, knot_db_val_t entry, int i, + bool exact_match, bool is_DS, + const struct kr_query *qry, uint32_t timestamp); + +/** + * Find the longest prefix zone/xNAME (with OK time+rank), starting at k->*. + * + * The found type is returned via k->type; the values are returned in el. + * \note we use k->type = KNOT_RRTYPE_NS also for the nsec_p result. + * \param qry can be NULL (-> gettimeofday(), but you lose the stale-serve hook) + * \param only_NS don't consider xNAMEs + * \return error code + */ +static int closest_NS(struct kr_cache *cache, struct key *k, entry_list_t el, + struct kr_query *qry, const bool only_NS, const bool is_DS) +{ + /* get the current timestamp */ + uint32_t timestamp; + if (qry) { + timestamp = qry->timestamp.tv_sec; + } else { + struct timeval tv; + if (gettimeofday(&tv, NULL)) return kr_error(errno); + timestamp = tv.tv_sec; + } + + int zlf_len = k->buf[0]; + + // LATER(optim): if stype is NS, we check the same value again + bool exact_match = true; + bool need_zero = true; + /* Inspect the NS/xNAME entries, shortening by a label on each iteration. */ + do { + k->buf[0] = zlf_len; + knot_db_val_t key = key_exact_type(k, KNOT_RRTYPE_NS); + knot_db_val_t val; + int ret = cache_op(cache, read, &key, &val, 1); + if (ret == -abs(ENOENT)) goto next_label; + if (ret) { + assert(!ret); + if (need_zero) memset(el, 0, sizeof(entry_list_t)); + return kr_error(ret); + } + + /* Check consistency, find any type; + * using `goto` for shortening by another label. */ + ret = entry_list_parse(val, el); + if (ret) { + assert(!ret); // do something about it? + goto next_label; + } + need_zero = false; + /* More types are possible; try in order. + * For non-fatal failures just "continue;" to try the next type. */ + const int el_count = only_NS ? EL_NS + 1 : EL_LENGTH; + for (int i = 0; i < el_count; ++i) { + ret = check_NS_entry(k, el[i], i, exact_match, is_DS, + qry, timestamp); + if (ret < 0) goto next_label; else + if (!ret) { + /* We found our match. */ + k->zlf_len = zlf_len; + return kr_ok(); + } + } + + next_label: + /* remove one more label */ + exact_match = false; + if (k->zname[0] == 0) { + /* We miss root NS in cache, but let's at least assume it exists. */ + k->type = KNOT_RRTYPE_NS; + k->zlf_len = zlf_len; + assert(zlf_len == 0); + if (need_zero) memset(el, 0, sizeof(entry_list_t)); + return kr_error(ENOENT); + } + zlf_len -= (k->zname[0] + 1); + k->zname += (k->zname[0] + 1); + k->buf[zlf_len + 1] = 0; + } while (true); +} + +static int check_NS_entry(struct key *k, const knot_db_val_t entry, const int i, + const bool exact_match, const bool is_DS, + const struct kr_query *qry, uint32_t timestamp) +{ + const int ESKIP = ABS(ENOENT); + if (!entry.len + /* On a zone cut we want DS from the parent zone. */ + || (i <= EL_NS && exact_match && is_DS) + /* CNAME is interesting only if we + * directly hit the name that was asked. + * Note that we want it even in the DS case. */ + || (i == EL_CNAME && !exact_match) + /* DNAME is interesting only if we did NOT + * directly hit the name that was asked. */ + || (i == EL_DNAME && exact_match) + ) { + return ESKIP; + } + + uint16_t type; + if (i < ENTRY_APEX_NSECS_CNT) { + type = KNOT_RRTYPE_NS; + int32_t log_new_ttl = -123456789; /* visually recognizable value */ + const int err = nsec_p_ttl(entry, timestamp, &log_new_ttl); + if (err) { + VERBOSE_MSG(qry, + "=> skipping unfit nsec_p: new TTL %d, error %d\n", + (int)log_new_ttl, err); + return ESKIP; + } + } else { + type = EL2RRTYPE(i); + /* Find the entry for the type, check positivity, TTL */ + const struct entry_h *eh = entry_h_consistent(entry, type); + if (!eh) { + VERBOSE_MSG(qry, "=> EH not consistent\n"); + assert(false); + return kr_error(EILSEQ); + } + const int32_t log_new_ttl = get_new_ttl(eh, qry, k->zname, type, timestamp); + const uint8_t rank_min = KR_RANK_INSECURE | KR_RANK_AUTH; + const bool ok = /* For NS any kr_rank is accepted, + * as insecure or even nonauth is OK */ + (type == KNOT_RRTYPE_NS || eh->rank >= rank_min) + /* Not interested in negative bogus or outdated RRs. */ + && !eh->is_packet && log_new_ttl >= 0; + WITH_VERBOSE(qry) { if (!ok) { + auto_free char *type_str = kr_rrtype_text(type); + const char *packet_str = eh->is_packet ? "packet" : "RR"; + VERBOSE_MSG(qry, + "=> skipping unfit %s %s: rank 0%.2o, new TTL %d\n", + type_str, packet_str, eh->rank, (int)log_new_ttl); + } } + if (!ok) return ESKIP; + } + k->type = type; + return kr_ok(); +} + |