Efficient node data storage, libknot refactoring

Changes:

• new file rr.h:

  • contains functions and structures that work with RRs or RR arrays.
  • this enables us to have RRSet-like functionality inside node_t

• node no longer stores knot_rrset_t, but only structure containing type, data and additional nodes.

• RRSet API cleaned up a lot:

• RRSet is now an entrypoint into zone structure

• It is no longer possible to create RRSet that is not sorted or one that contains duplicates

• Obsolete getter functions removed

• Node and zone contents API cleaned up

• DDNS rewritten to changeset creation only.

• Still far from perfect, but this is the best I can do without new zone API

• Over-complicated prereq check rewritten too

• Changeset application greatly simplified, no need to explicitly handle changes anymore

• Application now preserves the changeset structure, everything is copied

• We could probably simplify the code a lot because of this at many places

rr.h

• missing copyright & that sort of stuff
• ~~knot_rr_rdata should reuse get_rdata (I don't think we need special const getter anyway) :octocat: ~~
  • ~~(same with rrs_get_rr really) :octocat: ~~
• knot_rrs_t is confusing with knot_rrset_t
  • I can't think of better naming though, maybe something like:
  • rr_t -> rdata_t; rrs_t -> rdataset_t;" because rr_t` is not complete RR anyway
  • This is exacerbated by functions like knot_rrs_rr_get_rdata <- like what?
• knot_rrs_synth_rrsig should be somewhere near signatures, dnssec or elsewhere :octocat: almost

rr.c

• I did similar typecasting approach in hhash and I'm not sure if that's the best
  • f.e. knot_rr_ttl() will fail on architectures with strict alignment
  • How about having #pragma pack(1) structure rdata_t { uint16_t size; uint32_t ttl; uint8_t data[] };
    • Then RR_META_SIZE = sizeof(struct) and knot_rrl_ttl could be implemented like: return ((struct rdata_t*)rr)->ttl;
    • Zero packing would take care of the alignment for supported architectures / but we could disable it as well when needed :octocat: will do that. EDIT: , but I don't know where __i386__ is #defined, documentation is really sparse on this. should do it
• rr_seek, rrs_size... could reuse the knot_rr_array_size() for size calculation :octocat: .
• ~~knot_rrs_create_rr_at_pos C&P lines 65 and 75 + array size again ... I think only the "Make space" code is a corner case @jkadlec: Total Eclipse of the Mind, okay. :octocat: ~~
• knot_rr_cmp if either one is NULL, is '-1' correct return? That's the same as 'a < b' :octocat: it's just as bad as 0 or 1, I dunno, maybe assert? :octocat: at least something
  • Shouldn't TTL be compared as well? @jkadlec: No, but I don't remember why. I remembered: If TTL were part of the compare function it would interfere with canonical ordering - it might be useful for equality though, I've added a possibility to compare TTLs into knot_rrset_intersection.
• ERR_ALLOC_FAILED ... okay, but it could print something useful at least like __FILE__, __LINE__ @jkadlec: It does exactly that, doesn't it? my bad
• knot_rrs_*_rr_at_pos something like _(insert|remove)_at is enough I think :octocat: Done, both are static now, and named remore_rr_at add_rr_at

Otherwise it's quite nice and simple.

node.h

• KNOT_NODE_RRSET_COUNT_ONLY_NSEC lone warrior :octocat: forever in our hearts yours trully marauder shields
• struct rr_data name variation, maybe we could have rrset_t and knot_rrset_t? or node_data w/e
  • one more idea - knot_node_t -> rr_data is pretty generic, but what about zone_data -> zone_rr ?
• Why the NODE_EMPTY_DATA? Ternary operator in _RRSET_INIT anyway @jkadlec: Then the macro would be too complicated. :octocat: See below
• NODE_RR_INIT is a little bit confusing, I would expect something like rrset_from_node or equal macro
  • ~~Is it basically the same thing as the knot_node_fill_rrset? @jkadlec: yes, but it can be used when the structure is being declared, hence saving a function call and an extra line. I just think it looks better, that's it. EDIT: will turn it into function. DONE: ~~

node.c

• mm isn't used for additional records / data? :octocat: Nope, because it's malloc'd in zone contents somewhere, when allocators get there, then it will use it.

rdata.h

• rdata_offset is public here? (+ equal to knot_rrs_rr_rdata(rrs, pos) + offset) :octocat: knot_rrs_rr_rdata(rrs, pos) + offset: this looks weird if it's at 35 places in the file. And yes, it is public, because the file is all inline functions - if there is a way how to do it better, then I don't know of it.
• rest is a #226 (closed)

rrset.c

• every "to/from wire" function... should be in the packet, rrset API shouldn't know anything about compression etc.
  • this is probably difficult, but the problem is this is one monolithic function, it could be like parser or state machine so you either give it a callback OR call it until it returns it has no more data to write, you could then receive a series of returns like "(DNAME, data, size), (FIXED, data, size)..." if you look at the wire_one, its mostly the same thing just the size is different and compression needs different treatment :octocat: too complicated for this MR, #228 (closed)
• serialization should be where it's needed, that's like... journal or something? :octocat: zones.c was only place using it.
• ~~new_from is a good smoke & mirrors function, not needed :octocat: ~~
• :octocat: Comment for stuff right below this. I think the right approach here is to not leak information to higher layers - i.e. you want RDATA? No way to get those from RRSet, you need to get RR from RRs (and vice-versa: you want to insert stuff into RRs, well, give me a RR, that's all I know), but since everything in the server used rrset at some point, there's a lot of work for this to be complete (or cocci magic, you pick). I plan to gradually implement this, but I don't wan to make this change in this MR, it's already 3 times more code than I wanted. Issue here: #230 (closed)
• the "create rr_t from (rdata, ttl, size)" code is actually useful and should be in the "rr_t" API (copypasta from knot_rrset_add_rr)
• knot_rrset_add_rr_from_rrset is another example of doing other API's job
  • "knot_rrset_add_rr" should accept rr_t
  • "rr_t" API should have way to construct it from (size, ttl, data)
  • ~~knot_rrset_add_rr_from_rrset should be replaced by two calls: knot_rrset_at(&rr, from, pos); knot_rrset_add_rr(rr); :octocat: ~~
• s/deep_free_content/free_contents/g :octocat:
• knot_rrset_free condition for freeing additionals should be just a NULL check? :octocat: additionals should be freed by node, not RRSet, removed.
• ~~knot_rrset_is_nsec3rel -> move someplace that deals with NSEC3 and stuff :octocat: ~~
• knot_rrset_find_rr_pos should return <0, len(rrset)> if success, errcode if fails, "pos_out" isn't pretty :octocat: turns out it could be removed
• knot_rrset_remove_rr_using_rrset is ... subtract? (now that we have intersect operation) .. how about (_intersect nad _subtract) set-like operations? :octocat: Done, knot_rrs_t now support some basic set operations. Much neat.
• ~~additional_needed should be probably moved as well or prefixed with knot_ :octocat: ~~
• dtto knot_rrset_synth_rrsig this is a very specific operation :octocat: removed totally
• copy_int please no more, I yield :octocat:

rrset.h

• looks sensible (with the comment above and the #230 (closed))
• however, the order of the functions is just random - like init_empty is at the bottom, free is somewhere in the trenches, ... group functions with similar semantics together :octocat: done, it's very pretty indeed now.

rr module:

• RR is simplified RR - you should point it out in Doxygen as it goes to libknot :octocat: xxxxxxx
• rename knot_rr_size() to knot_rr_rdata_size() :octocat: xxxxxxx
• I would rather see an enum with offsets, and use these in getters/setters: :octocat: done in xxxxxxx

enum {
  RR_OFFSET_TYPE = 0,
  RR_OFFSET_TTL = 2,
  RR_OFFSET_RDATA = 6, // or RR_OFFSET_TTL + sizeof(uint32_t)
};
#define RR_META_SIZE RR_OFFSET_RDATA

• In knot_rrs_create_rr_at_pos() IMHO the code is complicated for no reason, first/last RR is no special case - just resize the array, compute the trailing part to be shifted and do memmove (may work even with size == 0). :octocat: xxxxxxx
• Please, remove mm_realloc and handle the reallocation in the rr module using mm_malloc + mm_free. Current realloc has no added value, as you have to supply the old data size. And we will need to move the allocator into libknot - the smaller API the better. :octocat: xxxxxxx
• I like the implicit sorting of RDATA on insertion. It will work fine, till you start modifying existing RDATA. :octocat: Hmm, yes, but I cannot really fix that without bonding the structures somehow.
• Get rid of knot_rrs_synth_rrsig - it is a special case, should be elsewhere, not in libknot.

node module:

• NODE_EMPTY_DATA - const, minimal initializer = { 0 }
• NODE_RR_INIT and NODE_RR_INIT_N can be implemented as function, why is it done as a macro? @jkadlec so that it can be used with fresh declaration, see usage. Fixed: xxxxxxx
• rr_data_clear, rr_data_from - missing static :octocat: Fixed: xxxxxxx

rrset module:

• knot_rrset_intersection doxygen, please add some notes about output allocation. :octocat: xxxxxxx
• knot_rrset_copy_int, knot_rrset_copy - do we need both of them? :octocat: Not really, the first one we could live without, but it's useful in pkt.c. I could move it there, together with knot_rrset_clear :octocat: xxxxxxx clear stayed, copy_int moved.

This is even worse. Just put an assertion here and be done with it. It's a clear user error which should be caught early on. Or leave the -1 and document it, but no useless and complex constructions please

Assertion it is, I agree.

Cool, but drop a line in the doxumentation as well.

Done.

Pff, I don't see why we should have both this and fill_rrset. Both do the same thing, and I'm not a fan of returning structures either. Is it that convenient? I like the usual approach, like with the "fill_rrset" and "rrset_init_empty", it's classic.

And on the serious note - knot_node_rrset_n sounds like counting to me, how about knot_node_rrset_at ?

We don't need both, fill_rrset* is not used at all, I just wanted it to be inline. Better than the macro anyway. As for conveniency, look at the usage, I, for one, think it's very convenient

Okay

"dname_cpy" is really rrsig_owner, but mor importantly - this code repeats itself 3 times already. Can we have like knot_synth_rrsig_data that would do what knot_synth_rrsig does now and knot_synth_rrsig that would create whole new rrset like here?

There was a function like that, but I've removed it. I'll resurrect it as a static here.

Turns out it's not that simple, sometimes I have stack rrset, sometimes I need to alloc it so that I can store it in the changeset.

Same code in knot_rrset_init, knot_rrset_new, knot_rrset_init_empty... C'mon, reuse the crap out of it

Done.

Job 38:11 I'm not going to accept anything new in the zones.c, this file is a dead man walking. Find a proper place for all the things here.

I knew you'd say that, but where should it go? I'll move it back into rrset.h, all these functions should be somewhere close to journal, but there's no such file in master.

If there isn't a proper file, then create one. I have moved this code in the zone events branch anyway so it's going to be easier to extract from another file than from here.

What difference does it make, if it's in rrset.h or in some other file when we merge it? Anyway: 45a6d021 ,virtually only functions originally in rrset.h were copied, moving the rest would create more conflicts anyway. No more please, let's focus back to actual changes in this MR, or it will never be done and I'll lose my mind.

src/knot/updates/xfr-in.{c,h} at commit 3 e f 4 8 5 2

More deletions than insertions mean extra points!

Removing changes from the changes+changeset+changesets hell.

rrs_list_clear() line 45

Comment into Doxygen? :octocat: done

xfrin_transfer_needed() line 92

int64_t local_serial = knot_rrs_soa_serial(soa_rrs); if (local_serial < 0) {

The condition is always false. The function retunrs uint32_t, which is assigned into int64_t. :octocat: fixed

xfrin_transfer_needed() line 109 The same as previous problem. :octocat: fixed

xfrin_take_rr() line 239:

Should return void. :octocat: fixed

xfrin_process_ixfr_packet line 386

I'm just wondering if this branch is reachable. How could be (*chs != NULL && (*chs)->first_soa == NULL)? :octocat: I didn't change this code more than I had to, I really don't know.

xfrin_cleanup_successful_update line 608

Cosmetic: init_list() immediately after deinitialization, or at least in the same order as freeing. :octocat: fixed

xfrin_rollback_update line 659

COPY PASTE WARNING LIGHT IS BLINKING! Now I see why the previous deinitialization was in illogical order. :octocat: you people in Brno and your copypaste problems, fixed.

xfrin_replace_rrs_with_copy line 685

Missing break in the for cycle after assinging the data variable. :octocat: fixed

xfrin_replace_rrs_with_copy line 678

Why is the knot_rrs_t copied manually while knot_rrs_copy() exists? :octocat: I only need knot_rrs_t->data copy, the rest are just numbers.

remove_rr line 770 and add_rr line 835

I'm not sure if I understand this correctly. Why are the removed nodes added to the changeset, and the existing nodes are replaced with a copy? Could not you just store a copy of removed entries into the changeset and do not bother with xfrin_replace_rrs_with_copy()? :octocat: I have two trees, both have the same data. Before I make any change to the data, I have to copy it first. If I did not do any copy, I'd be destroying data in the 'old' tree.

Btw, under which conditions the rollback happens? :octocat: Normally, never. Before, it was at least tested with DDNS test, now I can't think of a normal real-life scenario when the rollback would happen, only no memory left / no space in journal - those kind of errors. I'll add a test with limited journal size.

src/knot/updates/ddns.{c,h}

add_rr_to_list line 49

int ret = knot_rrs_merge(&rrset->rrs, &rr->rrs, NULL);
if (ret != KNOT_EOK) {
	return ret;
}
return KNOT_EOK;

replace with:

return knot_rrs_merge(&rrset->rrs, &rr->rrs, NULL); 

:octocat: fixed

confusing names or name inconsistencies - not sure if it makes sense to fix this at this point. :octocat: These check functions I didn't touch, I'll look into it.

• check_exists_in_list calls knot_ddns_check_exist_full :octocat: check_exists_in_list -> check_stored_rrsets
• knot_ddns_check_prereq calls knot_ddns_check_exist :octocat: knot_ddns_check_prereq -> process_prereq, knot_ddns_check_exist -> check_type_exists
• knot_ddns_check_exist (rrtype) vs knot_ddns_check_exist_full (rrset) :octocat: knot_ddns_check_exist_full -> check_rrset_exists
• no need to use knot_ prefix for internal functions :octocat: fixed
• is_deletion, is_*_removal :octocat: fixed

copy pasted code

• knot_ddns_check_in_use, knot_ddns_check_not_in_use :octocat: I've removed the duplicated subdomain check, it's okay now.
• knot_ddns_check_exist, knot_ddns_check_not_exist :octocat: same as above, it's a bit worse, but still passable I think. I'd vote for dropping the prereqs totally, it's a useless feature anyway.
• add_rr_to_chgset, rem_rr_to_chgset :octocat: look again, only the copy part is the same, if I've turned that into function, I'd save whopping 2 lines of code.

other

• missing semantic checks for NSEC3PARAM (flags must be 0) :octocat: We don't even check this when zone is loaded.