From 6845a9b8a1c595b5c240fa09eaaafe9f779f28c3 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Vladim=C3=ADr=20=C4=8Cun=C3=A1t?= Date: Wed, 13 Nov 2019 14:07:46 +0100 Subject: [PATCH] iterate: better efficiency on huge RRsets - written relatively defensively - act OK even if the API isn't used in an ideal way - CI lint:scan-build: bump the error count; It's only another instance of the mis-detected array_push(). - the removed stale note in modules/meson.build isn't really related --- .gitlab-ci.yml | 2 +- NEWS | 4 ++ daemon/lua/kres-gen.lua | 2 + daemon/lua/kres-gen.sh | 1 + doc/upgrading.rst | 10 +++ lib/cache/api.c | 1 + lib/dnssec.c | 1 + lib/layer/iterate.c | 17 ++++- lib/resolve.c | 1 + lib/utils.c | 140 ++++++++++++++++++++++++++++++++++++++-- lib/utils.h | 10 ++- modules/dns64/dns64.lua | 1 + modules/meson.build | 1 - 13 files changed, 179 insertions(+), 12 deletions(-) diff --git a/.gitlab-ci.yml b/.gitlab-ci.yml index 1c144f50..a6904948 100644 --- a/.gitlab-ci.yml +++ b/.gitlab-ci.yml @@ -226,7 +226,7 @@ lint:scan-build: script: - export SCANBUILD="scan-build --status-bugs -no-failure-reports $(./scripts/get-scanbuild-args.sh)" - ninja -C build_ci* scan-build || true - - test "$(ls build_ci*/meson-logs/scanbuild/*/report-*.html | wc -l)" = 29 # we have this many errors ATM :-) + - test "$(ls build_ci*/meson-logs/scanbuild/*/report-*.html | wc -l)" = 31 # we have this many errors ATM :-) lint:tidy: <<: *test diff --git a/NEWS b/NEWS index b84918a4..3fad57b8 100644 --- a/NEWS +++ b/NEWS @@ -1,6 +1,10 @@ Knot Resolver ?? ================================ +Security +-------- +- improve performance with huge RRsets (DoS, #518) + Bugfixes -------- - http module: use SO_REUSEPORT (!879) diff --git a/daemon/lua/kres-gen.lua b/daemon/lua/kres-gen.lua index ed48d753..01431ead 100644 --- a/daemon/lua/kres-gen.lua +++ b/daemon/lua/kres-gen.lua @@ -126,6 +126,7 @@ struct ranked_rr_array_entry { _Bool yielded : 1; _Bool to_wire : 1; _Bool expiring : 1; + _Bool in_progress : 1; knot_rrset_t *rr; }; typedef struct ranked_rr_array_entry ranked_rr_array_entry_t; @@ -351,6 +352,7 @@ int kr_family_len(int); struct sockaddr *kr_straddr_socket(const char *, int, knot_mm_t *); int kr_straddr_split(const char *, char * restrict, uint16_t *); int kr_ranked_rrarray_add(ranked_rr_array_t *, const knot_rrset_t *, uint8_t, _Bool, uint32_t, knot_mm_t *); +int kr_ranked_rrarray_finalize(ranked_rr_array_t *, uint32_t, knot_mm_t *); void kr_qflags_set(struct kr_qflags *, struct kr_qflags); void kr_qflags_clear(struct kr_qflags *, struct kr_qflags); int kr_zonecut_add(struct kr_zonecut *, const knot_dname_t *, const void *, int); diff --git a/daemon/lua/kres-gen.sh b/daemon/lua/kres-gen.sh index fd16e492..b0fe7ee1 100755 --- a/daemon/lua/kres-gen.sh +++ b/daemon/lua/kres-gen.sh @@ -213,6 +213,7 @@ ${CDEFS} ${LIBKRES} functions <<-EOF kr_straddr_socket kr_straddr_split kr_ranked_rrarray_add + kr_ranked_rrarray_finalize kr_qflags_set kr_qflags_clear kr_zonecut_add diff --git a/doc/upgrading.rst b/doc/upgrading.rst index 01be9359..c428b408 100644 --- a/doc/upgrading.rst +++ b/doc/upgrading.rst @@ -5,6 +5,16 @@ Upgrading This section summarizes steps required for upgrade to newer Knot Resolver versions. We advise users to also read :ref:`release_notes` for respective versions. +4.2.2 to 4.3+ +============= + +Module changes +-------------- + +* In case you directly call ``kr_ranked_rrarray_add()`` from your own module, + you need to additionally call ``kr_ranked_rrarray_finalize()`` after each batch + (before changing the added memory regions). + .. _upgrade-from-3-to-4: 4.x to 4.2.1+ diff --git a/lib/cache/api.c b/lib/cache/api.c index 88feb0ee..7d5dd441 100644 --- a/lib/cache/api.c +++ b/lib/cache/api.c @@ -658,6 +658,7 @@ static int stash_rrarray_entry(ranked_rr_array_t *arr, int arr_i, /* 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]; + assert(!e->in_progress); 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 diff --git a/lib/dnssec.c b/lib/dnssec.c index da095dbb..228feb71 100644 --- a/lib/dnssec.c +++ b/lib/dnssec.c @@ -461,6 +461,7 @@ int kr_dnssec_matches_name_and_type(const ranked_rr_array_t *rrs, uint32_t qry_u int ret = kr_error(ENOENT); for (size_t i = 0; i < rrs->len; ++i) { const ranked_rr_array_entry_t *entry = rrs->at[i]; + assert(!entry->in_progress); const knot_rrset_t *nsec = entry->rr; if (entry->qry_uid != qry_uid || entry->yielded) { continue; diff --git a/lib/layer/iterate.c b/lib/layer/iterate.c index 069b34f0..503edb3b 100644 --- a/lib/layer/iterate.c +++ b/lib/layer/iterate.c @@ -1096,13 +1096,15 @@ static int resolve(kr_layer_t *ctx, knot_pkt_t *pkt) return resolve_error(pkt, req); } + int state; /* Forwarding/stub mode is special. */ if (query->flags.STUB) { - return process_stub(pkt, req); + state = process_stub(pkt, req); + goto rrarray_finalize; } /* Resolve authority to see if it's referral or authoritative. */ - int state = process_authority(pkt, req); + state = process_authority(pkt, req); switch(state) { case KR_STATE_CONSUME: /* Not referral, process answer. */ VERBOSE_MSG("<= rcode: %s\n", rcode ? rcode->name : "??"); @@ -1116,6 +1118,17 @@ static int resolve(kr_layer_t *ctx, knot_pkt_t *pkt) break; } +rrarray_finalize: + /* Finish construction of libknot-format RRsets. */ + (void)0; + ranked_rr_array_t *selected[] = kr_request_selected(req); + for (knot_section_t i = KNOT_ANSWER; i <= KNOT_ADDITIONAL; ++i) { + int ret = kr_ranked_rrarray_finalize(selected[i], query->uid, &req->pool); + if (unlikely(ret)) { + return KR_STATE_FAIL; + } + } + return state; } diff --git a/lib/resolve.c b/lib/resolve.c index 6ef20979..8e365d78 100644 --- a/lib/resolve.c +++ b/lib/resolve.c @@ -477,6 +477,7 @@ static int write_extra_ranked_records(const ranked_rr_array_t *arr, uint16_t reo for (size_t i = 0; i < arr->len; ++i) { ranked_rr_array_entry_t * entry = arr->at[i]; + assert(!entry->in_progress); if (!entry->to_wire) { continue; } diff --git a/lib/utils.c b/lib/utils.c index 0725083f..cb15f463 100644 --- a/lib/utils.c +++ b/lib/utils.c @@ -692,6 +692,11 @@ static int to_wire_ensure_unique(ranked_rr_array_t *array, size_t index) return kr_ok(); } +/* Implementation overview of _add() and _finalize(): + * - for rdata we just maintain a list of pointers (in knot_rrset_t::additional) + * - we only construct the final rdataset at the end (and thus more efficiently) + */ +typedef array_t(knot_rdata_t *) rdata_array_t; int kr_ranked_rrarray_add(ranked_rr_array_t *array, const knot_rrset_t *rr, uint8_t rank, bool to_wire, uint32_t qry_uid, knot_mm_t *pool) { @@ -711,42 +716,85 @@ int kr_ranked_rrarray_add(ranked_rr_array_t *array, const knot_rrset_t *rr, continue; } /* Found the entry to merge with. Check consistency and merge. */ - bool ok = stashed->rank == rank && !stashed->cached; + bool ok = stashed->rank == rank && !stashed->cached && stashed->in_progress; if (!ok) { assert(false); return kr_error(EEXIST); } + /* assert(rr->rrs.count == 1); */ + /* ^^ shouldn't be a problem for this function, but it's probably a bug */ + /* It may happen that an RRset is first considered useful * (to_wire = false, e.g. due to being part of glue), * and later we may find we also want it in the answer. */ stashed->to_wire = stashed->to_wire || to_wire; - return knot_rdataset_merge(&stashed->rr->rrs, &rr->rrs, pool); + /* We just add the reference into this in_progress RRset. */ + rdata_array_t *ra = stashed->rr->additional; + if (ra == NULL) { + /* RRset not in array format yet -> convert it. */ + ra = stashed->rr->additional = mm_alloc(pool, sizeof(*ra)); + if (!ra) { + return kr_error(ENOMEM); + } + array_init(*ra); + int ret = array_reserve_mm(*ra, stashed->rr->rrs.count + rr->rrs.count, + kr_memreserve, pool); + if (ret) { + return kr_error(ret); + } + knot_rdata_t *r_it = stashed->rr->rrs.rdata; + for (int ri = 0; ri < stashed->rr->rrs.count; + ++ri, r_it = knot_rdataset_next(r_it)) { + if (array_push(*ra, r_it) < 0) { + abort(); + } + } + } else { + int ret = array_reserve_mm(*ra, ra->len + rr->rrs.count, + kr_memreserve, pool); + if (ret) { + return kr_error(ret); + } + } + /* Append to the array. */ + knot_rdata_t *r_it = rr->rrs.rdata; + for (int ri = 0; ri < rr->rrs.count; + ++ri, r_it = knot_rdataset_next(r_it)) { + if (array_push(*ra, r_it) < 0) { + abort(); + } + } + return kr_ok(); } /* No stashed rrset found, add */ int ret = array_reserve_mm(*array, array->len + 1, kr_memreserve, pool); - if (ret != 0) { - return kr_error(ENOMEM); + if (ret) { + return kr_error(ret); } ranked_rr_array_entry_t *entry = mm_alloc(pool, sizeof(ranked_rr_array_entry_t)); if (!entry) { return kr_error(ENOMEM); } - knot_rrset_t *copy = knot_rrset_copy(rr, pool); - if (!copy) { + + knot_rrset_t *rr_new = knot_rrset_new(rr->owner, rr->type, rr->rclass, rr->ttl, pool); + if (!rr_new) { mm_free(pool, entry); return kr_error(ENOMEM); } + rr_new->rrs = rr->rrs; + assert(rr_new->additional == NULL); entry->qry_uid = qry_uid; - entry->rr = copy; + entry->rr = rr_new; entry->rank = rank; entry->revalidation_cnt = 0; entry->cached = false; entry->yielded = false; entry->to_wire = to_wire; + entry->in_progress = true; if (array_push(*array, entry) < 0) { /* Silence coverity. It shouldn't be possible to happen, * due to the array_reserve_mm call above. */ @@ -757,6 +805,84 @@ int kr_ranked_rrarray_add(ranked_rr_array_t *array, const knot_rrset_t *rr, return to_wire_ensure_unique(array, array->len - 1); } +/** Comparator for qsort() on an array of knot_data_t pointers. */ +static int rdata_p_cmp(const void *rp1, const void *rp2) +{ + /* Just correct types of the parameters and pass them dereferenced. */ + const knot_rdata_t + *const *r1 = rp1, + *const *r2 = rp2; + return knot_rdata_cmp(*r1, *r2); +} +int kr_ranked_rrarray_finalize(ranked_rr_array_t *array, uint32_t qry_uid, knot_mm_t *pool) +{ + for (ssize_t array_i = array->len - 1; array_i >= 0; --array_i) { + ranked_rr_array_entry_t *stashed = array->at[array_i]; + if (stashed->qry_uid != qry_uid) { + continue; /* We apparently can't always short-cut the cycle. */ + } + if (!stashed->in_progress) { + continue; + } + rdata_array_t *ra = stashed->rr->additional; + if (!ra) { + /* No array, so we just need to copy the rdataset. */ + knot_rdataset_t *rds = &stashed->rr->rrs; + knot_rdataset_t tmp = *rds; + int ret = knot_rdataset_copy(rds, &tmp, pool); + if (ret) { + return kr_error(ret); + } + } else { + /* Multiple RRs; first: sort the array. */ + stashed->rr->additional = NULL; + qsort(ra->at, ra->len, sizeof(ra->at[0]), rdata_p_cmp); + /* Prune duplicates: NULL all except the last instance. */ + int dup_count = 0; + for (int i = 0; i + 1 < ra->len; ++i) { + if (knot_rdata_cmp(ra->at[i], ra->at[i + 1]) == 0) { + ra->at[i] = NULL; + ++dup_count; + QRVERBOSE(NULL, "iter", "deleted duplicate RR\n"); + } + } + /* Prepare rdataset, except rdata contents. */ + int size_sum = 0; + for (int i = 0; i < ra->len; ++i) { + if (ra->at[i]) { + size_sum += knot_rdata_size(ra->at[i]->len); + } + } + knot_rdataset_t *rds = &stashed->rr->rrs; + rds->count = ra->len - dup_count; + #if KNOT_VERSION_HEX >= 0x020900 + rds->size = size_sum; + #endif + if (size_sum) { + rds->rdata = mm_alloc(pool, size_sum); + if (!rds->rdata) { + return kr_error(ENOMEM); + } + } else { + rds->rdata = NULL; + } + /* Everything is ready; now just copy all the rdata. */ + uint8_t *raw_it = (uint8_t *)rds->rdata; + for (int i = 0; i < ra->len; ++i) { + if (ra->at[i] && size_sum/*linters*/) { + const int size = knot_rdata_size(ra->at[i]->len); + memcpy(raw_it, ra->at[i], size); + raw_it += size; + } + } + assert(raw_it == (uint8_t *)rds->rdata + size_sum); + } + stashed->in_progress = false; + } + return kr_ok(); +} + + int kr_ranked_rrarray_set_wire(ranked_rr_array_t *array, bool to_wire, uint32_t qry_uid, bool check_dups, bool (*extraCheck)(const ranked_rr_array_entry_t *)) diff --git a/lib/utils.h b/lib/utils.h index f806c8ff..0c932bae 100644 --- a/lib/utils.h +++ b/lib/utils.h @@ -195,6 +195,7 @@ struct ranked_rr_array_entry { bool yielded : 1; bool to_wire : 1; /**< whether to be put into the answer */ bool expiring : 1; /**< low remaining TTL; see is_expiring; only used in cache ATM */ + bool in_progress : 1; /**< build of RRset in progress, i.e. different format of RR data */ knot_rrset_t *rr; }; typedef struct ranked_rr_array_entry ranked_rr_array_entry_t; @@ -407,10 +408,17 @@ KR_EXPORT int kr_rrkey(char *key, uint16_t class, const knot_dname_t *owner, uint16_t type, uint16_t additional); -/** @internal Add RRSet copy to ranked RR array. */ +/** Add RRSet copy to a ranked RR array. + * + * To convert to standard RRs inside, you need to call _finalize() afterwards, + * and the memory of rr->rrs.rdata has to remain until then. + */ KR_EXPORT int kr_ranked_rrarray_add(ranked_rr_array_t *array, const knot_rrset_t *rr, uint8_t rank, bool to_wire, uint32_t qry_uid, knot_mm_t *pool); +/** Finalize in_progress sets - all with matching qry_uid. */ +KR_EXPORT +int kr_ranked_rrarray_finalize(ranked_rr_array_t *array, uint32_t qry_uid, knot_mm_t *pool); /** @internal Mark the RRSets from particular query as * "have (not) to be recorded in the final answer". diff --git a/modules/dns64/dns64.lua b/modules/dns64/dns64.lua index 0ee40e08..28aaeadc 100644 --- a/modules/dns64/dns64.lua +++ b/modules/dns64/dns64.lua @@ -96,6 +96,7 @@ function M.layer.consume(state, req, pkt) req.pool) end end + ffi.C.kr_ranked_rrarray_finalize(req.answ_selected, qry.uid, req.pool); end return M diff --git a/modules/meson.build b/modules/meson.build index 215475a7..d4a0ab5a 100644 --- a/modules/meson.build +++ b/modules/meson.build @@ -25,7 +25,6 @@ config_tests += [ ['nsid', files('nsid/nsid.test.lua')], ['dns64', files('dns64/dns64.test.lua')], ['ta_update', files('ta_update/ta_update.test.lua'), ['snowflake']], - # NOTE: https://gitlab.labs.nic.cz/knot/knot-resolver/issues/496 ['prefill', files('prefill/prefill.test/prefill.test.lua')], ] -- 2.22.0