.@ Tony Finch – blog

This is a follow-up to my unfinished series of posts last month.

(Monday’s notes) (Tuesday’s notes) (Wednesday’s notes) (Thursday’s notes)

On the Friday of the beer festival I found myself rather worn out. I managed to write a missing function (delete an element copy-on-write style) but that was about it.

When I got back to work after the bank holiday there was a bunch of stuff demanding more urgent attention so I wasn’t able to find time to finish the qp trie hacking until this week.


The nice thing about testing data structures is you can get a very long way with randomized testing and a good set of invariant checks.

When there’s a bug I tend to rely on voluminous dumps of how the trie structure changes as it mutates, with pointer values so I can track allocation and reuse. I stare at them wondering how the heck that pointer got where it shouldn’t be, until enlightenment dawns.


There were a number of notable bugs:


Having dealt with those, I have at last submitted my patches to CZ.NIC! There is still a lot of work to do, changing the DNS-specific parts of Knot so that UPDATE/IXFR transactions use the COW API instead of a copy of the entire zone.

One thing I’m not entirely sure about is whether I have been working with a valid memory model; in particular I have assumed that it’s OK to flip COW flags in shared words without any interlocks. The COW flags are only written in a single threaded way by the mutation thread; the concurrent read-only threads pay no attention to the COW flags, though they read the words that hold the flags.

If this is wrong, I might need to sprinkle some RCU calls through the qp trie implementation to ensure it works correctly…