RRset merge operation is too slow for big RRsets

Query cmts1-dhcp.longlines.com. A takes more than 10 seconds, probably because some

$\mathcal{O}(n^2)$

complexity in kr_ranked_rrarray_add() or something like that.

Such query can be used to DoS resolver so we have to fix that.

assigned to @vcunat

1. step: a simple fix in libknot. knot_rdataset_add() is quadratic by itself, so that kresd degenerates to cubic (!). After fixing this to linear (kresd goes quadratic, consequently), this query takes < 100 ms of CPU time for me, including the UDP+TCP fallback and some priming actions.

2. step: make kresd go away from insertion-sorting when iterator picks RRs. That's more complex – in particular it requires modifications of internal APIs, and my first attempts still aren't without regressions.

I'm sorry... I confused 10ms with 100ms. Now I fixed it above. Further libknot change got me to < 60 ms, but that part is not planned for 2.9 or at least not for 2.9.1 ATM EDIT: inside 2.9 as 6d85ad87 and f9952435.

changed the description

changed milestone to %4.3.0

mentioned in merge request !902 (closed)

mentioned in merge request !903 (merged)

made the issue visible to everyone

closed via merge request !903 (merged)

mentioned in commit 782682db

mentioned in issue #447 (closed)