A toy DNS resolver
jvns.ca
jvns.ca
I mean, probably true and accurate for many things. But if so that's not really a standard for how to handle it. It just means that, to be compliant, you need to figure it out and doing something about it.
What was interesting is that, for names not already in held in a cache, this system was able to beat the speed of full-blown DNS resolvers like BIND, dnscache, pdns_recursor, unbound, etc.
The reason it worked is that DNS resolution tends to follow certain patterns. There were 43 different paths DNS lookups take in the real world that I discovered. Some of them are extremely common. Some of them are extremely rare. These paths are simply the reflection of how people configure DNS. The most common pattern is also the most efficient. It only requires three queries. The least common patterns require many more queries. Arguably some of them could be called evidence of "DNS misconfiguration".
The program "brute forces" resolution by trying the most common patterns first. If it succeeds, it exits. If it fails, it will retry using the next most common pattern.
When the size growth of the root.zone exploded thanks to new gTLDs, this made the size of the custom filter that parses the TLD from stdin ridiculously large. That said, some of those new TLDs are rare to see and some are not even in active use. Is it even worth including them. The same question arises with all the different patterns a DNS lookup can follow. Some are so rare and so inefficient, why bother "supporting" them when writing a resolver.
The problem with DNS resolution IMO is that people believe there should be almost no rules in how someone configures DNS. If a website operator wants to force a user to make 18 DNS queries to get the IP addresss of their website, when it could easily be done in 3-5 queries, she can do that, and people expect a DNS resolver to be able to deal with that scenario. From a user perspective, this is stupid. Obviously these scenarios make for slower lookups. As the number of dependencies increases, i.e., number of different nameservers involved, the likelihood of failure increases. Not to mention this makes writing a DNS resolver more complicated.
From comments I read on HN, it sometimes seems that some programmers yearn for complexity. Simple, linear things that work fast and reliably are not interesting. Lord only knows how much we all suffer as a result of that perversion. One HN commenter called it a complexity fetish.
I used to worry about the size of this filter program but when I see how people routinely use double-digit MB binaries today, including some very large Go ones for DNS stuff, I guess I could have carried on and ignored it. I could have hardcoded the full spectrum of new gTLDs. It would probably be no larger than the large binaries people use today.
The filter program was generated directly from the root.zone file. I think root.zone only changed twice in the eight years I was using this method. Both times it was some rarely used ccTLD replacing a nameserver. Regenerating the filter program, i.e., compiling it, took about 60 seconds.
At the time, I was working on another filter that hardcoded the addresses for the "most common" registrar nameservers. Then people started adopting DoT and DoH, I lost interest in unencrypted authoritative DNS^1 and stopped using DNS altogether. Now I store selected bulk DNS data in the memory of a TLS forward proxy. I eliminated the variable delay of DNS when making HTTP requests and I got network-wide "ad blocking" as a side benefit.
1. I awlays thought about starting a registrar that offers encrypted authoritative DNS via DNSCurve, using the CurveDNS forwarder. Why. Because no one else ever did it. I use CurveDNS in the "home lab" and it works flawlessly.
from dnslib import DNSRecord,DNSError,QTYPE
ROOT_NS='198.41.0.4'
def find_cname(a,qtype,cname):
for r in a.rr:
if QTYPE[r.rtype] == qtype and r.rname == cname:
return str(r.rdata)
elif QTYPE[r.rtype] == 'CNAME' and r.rname == cname:
return find_cname(a,qtype,str(r.rdata))
return resolve(str(r.rdata),qtype,ROOT_NS)
def resolve(name,qtype='A',ns=ROOT_NS):
print(f"dig -r @{ns} {name} {qtype}")
q = DNSRecord.question(name,qtype)
a = DNSRecord.parse(q.send(ns))
if q.header.id != a.header.id:
raise DNSError('Response transaction id does not match query transaction id')
for r in a.rr:
if QTYPE[r.rtype] == qtype and r.rname == name:
return str(r.rdata)
elif QTYPE[r.rtype] == 'CNAME' and r.rname == name:
return find_cname(a,qtype,str(r.rdata))
for r in a.ar:
if QTYPE[r.rtype] == 'A':
return resolve(name,qtype,str(r.rdata))
for r in a.auth:
if QTYPE[r.rtype] == 'NS':
return resolve(name,qtype,resolve(str(r.rdata),'A',ROOT_NS))
raise ValueError("Cant resolve domain")
if __name__ == '__main__':
import sys
def get_arg(i,d):
try: return sys.argv[i]
except IndexError: return d
print(resolve(get_arg(1,"google.com"), get_arg(2,"A"), get_arg(3,ROOT_NS)))
Disclaimer: I am author of dnslib [https://github.com/paulc/dnslib]Edit: Better CNAME support
"creeting" may be a typo
- No Safe navigator: require 4 lines of code
- No ternary support: require 6 lines of code
- No map or filter functions (meaning you have to implement these in like 5-6 lines of code)
- Golang relies on built-in generator comments to help alleviate all of the typing.
> No ternary support: require 6 lines of code
> No map or filter functions (meaning you have to implement these in like 5-6 lines of code)
I like that Go doesnt have these. Many programmers seem to want these big bloated programming languages. So thats what you end up with, a bunch of slow bloated programming languages. Personally I just want something like C, but with a couple of minimal extra features (maps, built in package management, bounds checking). For me, Go is the closest thing I have found to C, without many of the C pitfalls.
> Golang relies on built-in generator comments to help alleviate all of the typing.
I have been programming Go for a few years, and I have like one file in all of my code that uses a generator comment. That file is to interface with the Windows API. Regarding pure Go code, I dont use generator comments at all, so I think this comment is overblown.
Those features are added to remove bloat from your source code.
No ternary support: require 6 lines of code
I'm glad Go does not have those, it makes the code less readable. It's only useful for simple operation and very often chained and abused.
Edit: I got confused which post you were replying to. My apologies.
if ((Lflag ? chown : lchown)(p->fts_accpath, s->st_uid, -1))
(void)printf(" not modified: %s\n",
strerror(errno));
which relies on the identical signature of chown(2) and lchown(2) syscalls.It's not as verbose as Enterprise™ Java, but hurdling that competition-height limbo-bar doesn't make something compact.
- Namespace system strongly favours single-word names
- Type embedding allows for single-dot access (not this.path.is.long())
- Zero-elements allow for elegant, zero-line initialization and existance checks, alleviating in part the need safe navigatorion operators.
Also I'd argue that the lack of map and filter are programmer nudges towards more elegant, compact solutions, but that's hard to prove. I've been annoyed with the lack of standard ways of doing things as well, but most often it turned out that I was simply doing it wrong, and Go was carefully designed to make the wrong way annoying to use. The compactness doesn't stem from using fewer lines to express simple constructs like if else, but the overall code organisation and structure that are the result of nudges like this one, as well as the code encapsulation they use (no classes, but interfaces and structs) and acyclic dependencies.
Generics will come out with the next version, though.
One of my favorite pieces of software.
It's worrying that your uptime indicates you don't patch frequently.
See here: https://cr.yp.to/djbdns/guarantee.html
https://www.kernel.org/doc/html/latest/livepatch/livepatch.h...
https://wiki.archlinux.org/title/Kernel_live_patching
Most enterprise distros provide a service for that, as the actual work is to create the binary patch fixing the security issues at hand, as one can not always just use the upstream version, e.g., if that introduces internal ABI changes or changes locking (order) - as then you'd need to patch X sites atomically at once to ensure nothing falls apart, can be done but hard to get right.
So yes, if you're willing to put in the money or work you can have systems that run for years and still are just as secure as those that frequently reboot into new updated kernels.
The slug contains the old title, not suggesting it was an editorial by OP (but could perhaps do with a similar update on HN?)
I’m not going to write this completely from
scratch – I think parsing DNS packets is really
interesting, but it’s definitely more than 80
lines of code, and I find that it kind of
distracts from the algorithm.
Which, seems legit to me. This article was a fun read to refresh on exactly what goes on in resolving basic records.The world needs more simple recursive lookup examples, and absolutely does not need more explication of DNS message parsing, any more than than an article talking about etcd's Raft implementation would benefit from a hand-rolled implementation of Protobufs.
Yikes, everybody.
Or maybe it already is encouraged and people just aren't aware this counts as "misleading" or "linkbait" since it's not well described what the cutoff point is.
Either way both titles like this one and discussions of have long gotten old.
Edit: looks like the article moved to "A toy DNS resolver", excellent choice of wording IMO.
The ability to leave a short (less than 100? 140?) description would be one the ways which would allows not to clickba^W editorialize the titles.
Or the submission author can do the same by leaving the comment about it in the first comment.
The community can moderate that, though
Increasingly more accurate titles always accepted of course though but one thing for sure is the class of "<x> in <y lines>" are demonstrably a continuous problem to the point they are talked about instead of the articles they represent, they are not just minor wording nits one could come up with after staring at a title long enough.
Edit: I really like the title the article itself changed to "A toy DNS resolver".
To this old demoscener, that sounds like a challenge...
Writing a resolver in it is a fun project, but bragging about the line count is silly.
miekg/dns is also 20,000 lines of code most of which are not relevant to the task of doing a recursive lookup.
and gatekeeping is silly too..
Honestly the comments of this type on this article sound more like you didn't actually read the article and are just knee jerk putting someone down. I hope that is not the case but maybe it would be good to examine why the message is coming off so distastefully.
You're not going to win this argument, no matter how many synonyms for "encode" and "decode" you come up with.
If you hold the opinion that a 12 line for loop is heavier lifting than the underlying library doing the aforementioned things, that's your right.
I'm not messing with you; as someone who does an unfortunate amount of DNS hacking, it is crazymaking to see so many people express the opinion that the hard part of doing DNS is just formatting the records. The argument you're presenting is a little like saying that "malloc" would be doing the heavy lifting in a C implementation of a graph minimum cost spanning tree.
This also isn't just an aesthetic argument. There is something profound about it. No language standard library I'm aware of includes a recursive lookup, despite the fact that you've pegged it as a "12 line for loop". They all in some way or other include DNS message codecs, but not the recursive lookup, despite the fact that it would be immensely useful to be able to write programs that did recursive lookups directly rather than relying on the system's configured recursive resolver. The reason for that is at least partly that recursive lookup is mystifying and spooks library implementors.
I've had the displeasure of writing both a series of DNS codecs and a recursive lookup routine. The codecs I've done throughout my career, going back to like 1997 with exploits for the Kashpureff cache poisoning bug. The recursor I finally got around to writing just a couple months ago, because recursive lookups are freaking complicated.
That the author got this recursive lookup so small that it broke everyone's brains is just more reason to be interested in this article. It's certainly not a reason to dismiss it. The reactions on this thread are pretty embarrassing.
I know because I've done it (I wrote a an authoritative DNS server from scratch for a registry platform we did for .name).
To write a full fledged library for it for a resolver (an authoritative server can take plenty of shortcuts depending on purpose) is complex, but I absolutely agree the basics that you'd demonstrate if writing a toy one to demonstrate would be just a distraction.
https://github.com/jvns/tiny-resolver/blob/main/resolver.sh - the recursive lookup is 16 lines for + switch.
I'm sorry to say this, but if the recursive lookup can be implemented with a for and a 3-way switch that a CS 101 student can write, it's really not doing the heavy lifting. It may be interesting to know about it, it may be the case that multiple resolves don't have the implementation, but it's a trivial piece of code, let's not idolize it.
For me personally, having the power of hitting an endpoint and receiving useful information is really satisfying. Creating the request and parsing the reply are probably 90% of that process. And frankly, that was the first think I was looking for when I skimmed the article. "Are DNS replies really that easy to parse?". The fact that I need to make a switch on the reply and potentially make a recursive request somewhere else is trivial once you get the actual useful info from the remote.
I'm not criticising the article or the title. It's my opinion that parsing is more important, I'm not faulting the author. But I'm having a hard time accepting your arguments.
My argument is that DNS codecs are not the interesting or tricky part of writing recursive resolvers.
Having had the pleasure of writing a bunch of DNS codecs, I'm having trouble even conceptualizing what's interesting about writing one. I don't think most people look at DNS and think "I could do this, but for the difficulty of constructing an NS record".
Unbound leans on libresolv, so I don't think it's cheating to lean on external libraries - most of the hard part about resolvers is all the crufty RFCs you have to support anyway, not the basic nuts and bolts of resolving an A record.
As far as I know (we use the same library for our authority servers) `miekg/dns` doesn't even do recursive lookups.
It's not just that, though. It's also that recursive lookups are the probably the most mystifying aspect of DNS. DNS message parsers are straight-line code; there are lots of them, including in POSIX libc. What you don't have in POSIX libc is a function that does a complete from-the-root recursive lookup for a name; most DNS "client" implementations stop at "send the request to the local recursive cache".
To see that function implemented in such a tiny amount of code is itself super interesting.
Essentially, what you're saying is that the article disappointed you because it purported to be about making pizza, but didn't first specify how to make the oven.
func dnsQuery(name string, server net.IP) *dns.Msg {
fmt.Printf("dig -r @%s %s\n", server.String(), name)
msg := new(dns.Msg)
msg.SetQuestion(name, dns.TypeA)
c := new(dns.Client)
reply, _, _ := c.Exchange(msg, server.String()+":53")
return reply
}
func main() {
name := os.Args[1]
if !strings.HasSuffix(name, ".") {
name = name + "."
}
fmt.Println("Result:", resolve(name))
}
While I agree it's impressively simply laid out and as an exercise good to see people getting hands-on with underpinning protocols (I'm a fan of this), it also does its job as a follow up to her previous blog post on the subject.People taking umbrage with the title as posted here (and the original site title) are IMO not wrong. The article title has been changed to "A toy DNS resolver" now, so obviously it was contentious enough that she thought to change it.
If the author took the time to write a 15 line roundTrip() function that called m.Pack(), udpConn.Write(), udpConn.SetDeadline(1s), and udpConn.Read(), would your argument here evaporate? Then it's not a very good argument, is it?
No it's more akin about him saying he made a pizza, but all that was done was import a pizza and then sprinkle some pepperoni on it.
Imagine if I said I made an HTTP server in 6 lines.
const express = require("express");
const app = express();
app.get("/", (req, res) => {
res.send('Hello World!');
});
app.listen(8080);
I think it would be reasonable for people to say that I didn't make a HTTP server in 6 lines.Just how I used a library to make a HTTP server me and I handled requests/responses, the author of this article used a library to handle DNS requests/responses. The 80 lines figure for making a DNS resolver is misleading when there are 26k lines of Go code (according to cloc) for handling DNS that are just in a library instead of the main file.
The majority of the 20,000 lines of non-test code in miekg/dns are just handlers for record types the author of this article didn't need; much of the rest of it is stuff like zone file parsing and DNSSEC signatures, which again have nothing to do with what the author wrote.
What you conspicuously won't find in miekg/dns: a recursive lookup routine.
Sure, but it implements the building blocks that you need to create one. Those building blocks are going to be where a good chunk of code is going to be. (Yes, there is a lot of code from that library that will be unused)
I don't think author can claim "in 80 lines of code" when the code depends on a much bigger library than itself.
The comment might seem like its being dismissive with the current title "A toy DNS resolver", but at the time of writing it was not just a shallow dismissal.