DNS message format and client lookups

Deep dive

How it works

In: a name, a record type, a resolver address · Out: typed records with TTLs, or an error (NXDOMAIN, SERVFAIL, truncated) · State: cache of (name, type, class) with expiry; in-flight ID and source port · Cost: one round trip per cache miss; parse O(bytes)

1. Query. Header: random 16-bit ID, flags with RD=1, QDCOUNT=1 (bytes 4-11 are QD/AN/NS/AR counts). Question: QNAME labels (length byte, at most 63 bytes each, 255 in total, ending in a 0 byte), QTYPE (A=1, CNAME=5, MX=15, TXT=16, AAAA=28, SRV=33, OPT=41), QCLASS=1. Add an EDNS OPT record advertising UDP size 1232.
2. Send from a random source port; retransmit with backoff. Accept only a response whose source address, port, ID and question match (RFC 5452).
3. TC set: retry over TCP, each message preceded by a 2-byte length (length prefix); pipeline queries on one connection (RFC 7766).
4. RCODE: 0 NOERROR, 2 SERVFAIL, 3 NXDOMAIN; NOERROR with no matching answer is NODATA.
5. Read records: NAME, TYPE, CLASS, 32-bit TTL, RDLENGTH, RDATA. A name byte with bits 11 starts a pointer: low 14 bits = offset from message start. CNAME, MX and SRV data hold names that may point anywhere in the message.
6. Interpret: A 4 bytes, AAAA 16 (RFC 3596); MX = 16-bit preference + name, lowest first; TXT = one or more length-prefixed character-strings; SRV = priority, weight, port, target: take the lowest priority, then pick by weight with a running sum and a random number in 0..=sum (RFC 2782). Bound CNAME chains yourself.
7. Cache until now+TTL (top bit set counts as 0, RFC 2181). Cache NXDOMAIN/NODATA for the SOA MINIMUM, capped by the SOA TTL (RFC 2308).

Code

#[derive(Debug, PartialEq)]
pub enum Data {
    A([u8; 4]), Aaaa([u8; 16]), Cname(String), Txt(Vec<Vec<u8>>), Other(u16),
    Mx { pref: u16, exchange: String }, Srv { priority: u16, weight: u16, port: u16, target: String },
}
#[derive(Debug, PartialEq)]
pub struct Rr { pub name: String, pub ttl: u32, pub data: Data }
#[derive(Debug)]
pub struct Response { pub id: u16, pub rcode: u8, pub tc: bool, pub answers: Vec<Rr> }
#[derive(Debug, PartialEq)] pub enum Err { Short, BadName, Loop }

/// Query with RD set and an EDNS(0) OPT record advertising 1232 bytes.
pub fn build_query(id: u16, name: &str, qtype: u16) -> Vec<u8> {
    let mut q = id.to_be_bytes().to_vec();
    q.extend([1, 0, 0, 1, 0, 0, 0, 0, 0, 1]); // flags RD; QD=1 AN=0 NS=0 AR=1
    for label in name.trim_end_matches('.').split('.').filter(|l| !l.is_empty()) {
        q.push(label.len() as u8); // caller guarantees label <= 63 bytes
        q.extend(label.as_bytes());
    }
    q.extend([0]); q.extend(qtype.to_be_bytes()); q.extend([0, 1]); // root label, QTYPE, QCLASS IN
    q.extend([0, 0, 41, 0x04, 0xD0, 0, 0, 0, 0, 0, 0]); // OPT: root, type 41, size 1232, ttl 0, rdlen 0
    q
}
fn u16_at(m: &[u8], p: usize) -> Result<u16, Err> {
    Ok(u16::from_be_bytes(m.get(p..p + 2).ok_or(Err::Short)?.try_into().unwrap()))
}
/// Returns (dotted name, offset just after the name at `p`, i.e. after the first pointer).
pub fn read_name(m: &[u8], mut p: usize) -> Result<(String, usize), Err> {
    let (mut name, mut end, mut hops) = (String::new(), None, 0);
    loop {
        let l = *m.get(p).ok_or(Err::Short)? as usize;
        match l & 0xC0 {
            0x00 if l == 0 => { p += 1; break; }
            0x00 => {
                let lab = m.get(p + 1..p + 1 + l).ok_or(Err::Short)?;
                if name.len() + l + 1 > 255 { return Err(Err::BadName); }
                name.push_str(&String::from_utf8_lossy(lab)); name.push('.');
                p += 1 + l;
            }
            0xC0 => {
                end.get_or_insert(p + 2);
                hops += 1;
                if hops > 16 { return Err(Err::Loop); } // bounds pointer chains and cycles
                p = (l & 0x3F) << 8 | *m.get(p + 1).ok_or(Err::Short)? as usize;
            }
            _ => return Err(Err::BadName), // 01 and 10 label types are reserved
        }
    }
    Ok((if name.is_empty() { ".".into() } else { name }, end.unwrap_or(p)))
}
pub fn parse_response(m: &[u8]) -> Result<Response, Err> {
    let flags = u16_at(m, 2)?;
    let mut p = 12;
    for _ in 0..u16_at(m, 4)? { p = read_name(m, p)?.1 + 4; } // skip question: QTYPE, QCLASS
    let mut answers = Vec::new();
    for _ in 0..u16_at(m, 6)? {
        let (name, q) = read_name(m, p)?;
        let ttl = u32::from_be_bytes(m.get(q + 4..q + 8).ok_or(Err::Short)?.try_into().unwrap());
        let (rd, rdlen) = (q + 10, u16_at(m, q + 8)? as usize);
        let rdata = m.get(rd..rd + rdlen).ok_or(Err::Short)?; // RDATA must fit in the packet
        let data = match u16_at(m, q)? {
            1 if rdlen == 4 => Data::A(rdata.try_into().unwrap()),
            28 if rdlen == 16 => Data::Aaaa(rdata.try_into().unwrap()),
            5 => Data::Cname(read_name(m, rd)?.0),
            15 => Data::Mx { pref: u16_at(m, rd)?, exchange: read_name(m, rd + 2)?.0 },
            33 => Data::Srv { priority: u16_at(m, rd)?, weight: u16_at(m, rd + 2)?,
                              port: u16_at(m, rd + 4)?, target: read_name(m, rd + 6)?.0 },
            16 => {
                let (mut i, mut parts) = (0, vec![]);
                while i < rdlen { // character-strings: 1 length byte + data
                    let n = rdata[i] as usize;
                    parts.push(rdata.get(i + 1..i + 1 + n).ok_or(Err::Short)?.to_vec());
                    i += 1 + n;
                }
                Data::Txt(parts)
            }
            t => Data::Other(t),
        };
        answers.push(Rr { name, ttl: if ttl >> 31 == 1 { 0 } else { ttl }, data }); // RFC 2181 s8
        p = rd + rdlen;
    }
    Ok(Response { id: u16_at(m, 0)?, rcode: (flags & 0xF) as u8, tc: flags & 0x0200 != 0, answers })
}
#[cfg(test)]
mod tests {
    use super::*;
    fn rr(typ: u16, ttl: u32, rd: &[u8]) -> Vec<u8> { // NAME = pointer to offset 12
        [&[0xC0, 12, (typ >> 8) as u8, typ as u8, 0, 1][..], &ttl.to_be_bytes(), &(rd.len() as u16).to_be_bytes(), rd].concat()
    }
    fn msg(flags: u16, rrs: &[Vec<u8>]) -> Vec<u8> {
        let h = [0x12, 0x34, (flags >> 8) as u8, flags as u8, 0, 1, 0, rrs.len() as u8, 0, 0, 0, 0];
        [&h[..], b"\x07example\x03com\x00\x00\x0F\x00\x01", &rrs.concat()].concat() // question at offset 12
    }
    #[test]
    fn parse_and_reject() {
        let mx = rr(15, 300, b"\x00\x0a\x04mail\xC0\x0c"); // "mail" + pointer to example.com
        let srv = rr(33, 60, b"\x00\x01\x00\x05\x1f\xc9\x03sip\xC0\x0c");
        let txt = rr(16, 3600, b"\x05v=spf\x03abc");
        let a = rr(1, 1 << 31, &[192, 0, 2, 1]);
        let r = parse_response(&msg(0x8180, &[mx.clone(), srv, txt, a])).unwrap();
        assert_eq!(r.answers[0].data, Data::Mx { pref: 10, exchange: "mail.example.com.".into() });
        assert_eq!((r.answers[0].name.as_str(), r.answers[0].ttl), ("example.com.", 300));
        assert_eq!(r.answers[1].data, Data::Srv { priority: 1, weight: 5, port: 8137, target: "sip.example.com.".into() });
        assert_eq!(r.answers[2].data, Data::Txt(vec![b"v=spf".to_vec(), b"abc".to_vec()]));
        assert_eq!((r.answers[3].ttl, r.tc), (0, false)); // TTL with top bit set -> 0
        assert!(parse_response(&msg(0x8380, &[])).unwrap().tc); // TC bit: retry over TCP
        let mut lp = msg(0x8180, &[]); lp.truncate(12); lp.extend([0xC0, 12, 0, 15, 0, 1]);
        assert_eq!(parse_response(&lp).unwrap_err(), Err::Loop); // name points at itself
        let full = msg(0x8180, &[mx]);
        assert!((0..full.len()).all(|n| parse_response(&full[..n]).is_err())); // every truncation
    }
}

Complexity and constants

• Parse is O(message length); hops are capped at 16, names at 255 bytes.
• A www.example.com query with OPT is 45 bytes (measured). 1232 = IPv6 minimum MTU 1280 minus 48 bytes of IPv6+UDP headers (dnsflagday.net).
• Measured, Apple M4 Pro, one core, --release: a 110-byte response with 4 answers (MX, A, TXT, AAAA) parses in order of 430 ns (about 2.3 M messages/s); building a query takes order of 100 ns. Cost driver: String/Vec allocation.
• The bound is latency: one round trip per miss; TCP adds a handshake.

Efficiency

• Cost: one UDP round trip per cache miss (latency dominates: order of sub-ms on a LAN, tens of ms over a WAN); CPU about 0.4 µs to parse, 0.1 µs to build (measured above); 45-byte query.
• Levers:
  • TTL and negative cache — removes the round trip for repeats (RFC 2308) — clients resolving the same names often.
  • EDNS buffer 1232 — avoids fragmentation and most TCP fallbacks (dnsflagday.net) — answers over 512 bytes.
  • Pipelining on one TCP/TLS connection — one handshake for many queries (RFC 7766 §6.2.1) — parallel lookups, DoT.
  • Parse to offsets/borrowed slices — drops per-name allocation (gain not measured) — high query rates.
  • Serve stale while refreshing — hides failing upstreams (RFC 8767) — long-lived caches.
• Naive → standard → state of the art:
  • Blocking lookup per use, fixed ID, no cache · one round trip every time, spoofable.
  • Random ID and port, TTL cache, EDNS 1232, TC to TCP · one round trip per miss.
  • Local caching resolver, serve-stale, reused DoT/DoH connection · hits at memory speed.

Implementation notes

• Compare names ASCII case-insensitively; labels may hold any byte (the code uses lossy UTF-8 for brevity).
• Check the response's question, not only the ID; connect the UDP socket so the kernel drops other peers.
• OPT: CLASS = sender's UDP size, TTL = extended RCODE, version, flags (RFC 6891); sizes under 512 count as 512.
• DoT (RFC 7858, port 853): same bytes with the 2-byte length inside TLS. DoH (RFC 8484): application/dns-message, ID 0 recommended.

Pitfalls

• A pointer to itself or in a cycle loops forever: cap hops, or accept only pointers to earlier offsets.
• Trusting RDLENGTH: check rd + rdlen <= len and that names inside RDATA stay within it.
• Counts up to 65535 per section: never pre-allocate from a count.
• TXT with several character-strings: join without separator (long DKIM keys).
• Ignoring TC hides records; reusing ID and source port on retries makes queries predictable.

Variants and alternatives

In production

OS stubs, browsers, crawlers, mail transfer agents, Kubernetes cluster DNS, SIP stacks, DKIM/SPF/DMARC checkers, firmware resolvers.

Implementations

Sources

• Mockapetris, RFC 1035: Domain Names - Implementation and Specification, 1987. rfc
• Elz, Bush, RFC 2181: Clarifications to the DNS Specification, 1997. rfc
• Andrews, RFC 2308: Negative Caching of DNS Queries, 1998. rfc
• Gulbrandsen, Vixie, Esibov, RFC 2782: DNS SRV, 2000. rfc
• Thomson et al., RFC 3596: DNS Extensions to Support IPv6, 2003. rfc
• Hubert, van Mook, RFC 5452: Making DNS More Resilient against Forged Answers, 2009. rfc
• Damas, Graff, Vixie, RFC 6891: EDNS(0), 2013. rfc
• Dickinson et al., RFC 7766: DNS Transport over TCP, 2016. rfc
• Hu et al., RFC 7858: DNS over TLS, 2016. rfc
• Hoffman, McManus, RFC 8484: DNS over HTTPS, 2018. rfc
• Lawrence, Kumari, Sood, RFC 8767: Serving Stale Data, 2020. rfc
• Rosenberg, Schulzrinne, RFC 3263: Locating SIP Servers, 2002. rfc
• DNS Flag Day 2020, Fragmentation avoidance. site
• Kubernetes, DNS for Services and Pods. docs
• IANA, DNS Parameters. registry