Dive into NSD code


権威DNSサーバを作ろうと思い、オープンソースの権威DNSサーバとして有名なNLnetLabsのNSDのソースコードを読み込んだので、内容についてまとめました。
投稿日時点でのリリースバージョンは 4.3.7 が最新のため、こちらをリファレンス先とします。githubの該当コード行に飛べるように各所にリンクを貼っています。

https://github.com/NLnetLabs/nsd/tree/NSD_4_3_7_REL

また、最終的に作ったものは下記になります。

https://github.com/nimjim/SimpleAuthDNS

DNSプロトコルの基本的な処理を重点的に、他のところはさらっと流していきます。
main()からスタートとして芋づる式に見ていくのですが、非常に長くなるため4つのパートに分けて見ていきます。

## Part1. start from main()

nsd.cのmain関数からスタートします。
さまざまなセットアップが行われていますが、流し読みしつつ、クエリを受け付けるためのソケットセットアップをどこかで行うんだろうなと想像しながら見ていきます。
ざっくりとした構造は下記の通りです。

[main](https://github.com/NLnetLabs/nsd/blob/NSD_4_3_7_REL/nsd.c#L872) (nsd.c)
​&emsp;... various setups ...
​&emsp;[server_main](https://github.com/NLnetLabs/nsd/blob/NSD_4_3_7_REL/server.c#L2430) (server.c)
​&emsp;&emsp;[server_start_children](https://github.com/NLnetLabs/nsd/blob/NSD_4_3_7_REL/server.c#L1456) # start the child processes that handle incoming queries
​&emsp;&emsp;&emsp;[restart_child_servers](https://github.com/NLnetLabs/nsd/blob/NSD_4_3_7_REL/server.c#L409) 
​&emsp;&emsp;&emsp;&emsp;[server_child](https://github.com/NLnetLabs/nsd/blob/NSD_4_3_7_REL/server.c#L2951)
​&emsp;[server_child](https://github.com/NLnetLabs/nsd/blob/NSD_4_3_7_REL/server.c#L2951) (server.c) # Serve DNS requests


## Part2. setup udp/tcp handler

ここでudpハンドラーとtcpハンドラーが登場します。
いずれの場合もソケット/コネクション経由でクエリを受け取り、クエリを処理してレスポンスを作成し、ソケット/コネクションから返してあげるというおおまかな流れが見て取れます。


[server_child](https://github.com/NLnetLabs/nsd/blob/NSD_4_3_7_REL/server.c#L2951) (server.c)
​&emsp;[add_udp_handler](https://github.com/NLnetLabs/nsd/blob/NSD_4_3_7_REL/server.c#L2893)
​&emsp;&emsp;[handle_udp](https://github.com/NLnetLabs/nsd/blob/NSD_4_3_7_REL/server.c#L3378) # Handle incoming queries on the UDP server sockets.
​&emsp;&emsp;&emsp;[nsd_recvmmsg](https://github.com/NLnetLabs/nsd/blob/NSD_4_3_7_REL/server.c#L3277)
​&emsp;&emsp;&emsp;&emsp;rcvd = recvfrom(...)
​&emsp;&emsp;&emsp;[server_process_query_udp](https://github.com/NLnetLabs/nsd/blob/NSD_4_3_7_REL/server.c#L2807)
​&emsp;&emsp;&emsp;&emsp;[query_process](https://github.com/NLnetLabs/nsd/blob/NSD_4_3_7_REL/query.c#L1498) (query.c)
​&emsp;&emsp;&emsp;[nsd_sendmmsg](https://github.com/NLnetLabs/nsd/blob/NSD_4_3_7_REL/server.c#L3320)
​&emsp;&emsp;&emsp;&emsp;sendto(...)
​&emsp;[add_tcp_handler](https://github.com/NLnetLabs/nsd/blob/NSD_4_3_7_REL/server.c#L2912)
​&emsp;&emsp;[handle_tcp_accept](https://github.com/NLnetLabs/nsd/blob/NSD_4_3_7_REL/server.c#L4519) # Handle an incoming TCP connection.
​&emsp;&emsp;&emsp;[perform_accept](https://github.com/NLnetLabs/nsd/blob/NSD_4_3_7_REL/server.c#L4491)
​&emsp;&emsp;&emsp;[handle_tls_reading](https://github.com/NLnetLabs/nsd/blob/NSD_4_3_7_REL/server.c#L4131) # Handle incoming queries on a TLS over TCP connection.
​&emsp;&emsp;&emsp;&emsp;received = SSL_read(...)
​&emsp;&emsp;&emsp;&emsp;[server_process_query](https://github.com/NLnetLabs/nsd/blob/NSD_4_3_7_REL/server.c#L2799)
​&emsp;&emsp;&emsp;&emsp;&emsp;[query_process](https://github.com/NLnetLabs/nsd/blob/NSD_4_3_7_REL/query.c#L1498) (query.c)
​&emsp;&emsp;&emsp;&emsp;[handle_tls_writitng](https://github.com/NLnetLabs/nsd/blob/NSD_4_3_7_REL/server.c#L4353) # Handle outgoing responses on a TLS over TCP connection.
​&emsp;&emsp;&emsp;[handle_tcp_reading](https://github.com/NLnetLabs/nsd/blob/NSD_4_3_7_REL/server.c#L3637) # Handle incoming queries on a TCP connection.
​&emsp;&emsp;&emsp;&emsp;received = read(...)
​&emsp;&emsp;&emsp;&emsp;[server_process_query](https://github.com/NLnetLabs/nsd/blob/NSD_4_3_7_REL/server.c#L2799)
​&emsp;&emsp;&emsp;&emsp;&emsp;[query_process](https://github.com/NLnetLabs/nsd/blob/NSD_4_3_7_REL/query.c#L1498) (query.c)
​&emsp;&emsp;&emsp;&emsp;[handle_tcp_writing](https://github.com/NLnetLabs/nsd/blob/NSD_4_3_7_REL/server.c#L3874) # Handle outgoing responses on a TCP connection.



## Part3. query process

クエリ処理部分を詳しく見ていきましょう。
前半部分で異常なDNSクエリを処理し、その後EDNSのパースやTSIGの処理を行っていますね。
後半のほうでクエリに対する回答作成が行われています。今回はanswer_queryのみピックアップします。

[query_process](https://github.com/NLnetLabs/nsd/blob/NSD_4_3_7_REL/query.c#L1498) (query.c)
​&emsp;check packet size -> drop
​&emsp;check QR bit -> drop
​&emsp;check OPCODE -> drop or [query_error](https://github.com/NLnetLabs/nsd/blob/master/query.c#L129)
​&emsp;perse the question section -> [query_formerror](https://github.com/NLnetLabs/nsd/blob/master/query.c#L167)
​&emsp;OPCODE == NOTIFY -> [answer_notify](https://github.com/NLnetLabs/nsd/blob/master/query.c#L412)
​&emsp;check QDCOUNT -> [query_formerror](https://github.com/NLnetLabs/nsd/blob/master/query.c#L167)
​&emsp;check ANCOUNT or NSCOUNT -> [query_formerror](https://github.com/NLnetLabs/nsd/blob/master/query.c#L167)
​&emsp;[edns_parse_record](https://github.com/NLnetLabs/nsd/blob/NSD_4_3_7_REL/edns.c#L121) (edns.c)
​&emsp;[tsig_parse_rr](https://github.com/NLnetLabs/nsd/blob/NSD_4_3_7_REL/tsig.c#L582) (tsig.c)
​&emsp;[process_tsig](https://github.com/NLnetLabs/nsd/blob/master/query.c#L378) -> [query_error](https://github.com/NLnetLabs/nsd/blob/master/query.c#L129) 
​&emsp;[process_edns](https://github.com/NLnetLabs/nsd/blob/master/query.c#L326) -> return BADVERS(16)
​&emsp;[query_prepare_response](https://github.com/NLnetLabs/nsd/blob/NSD_4_3_7_REL/query.c#L1469) # Update the flags, etc.
​&emsp;[answer_chaos](https://github.com/NLnetLabs/nsd/blob/NSD_4_3_7_REL/query.c#L522)
​&emsp;[answer_axfr_ixfr](https://github.com/NLnetLabs/nsd/blob/NSD_4_3_7_REL/axfr.c#L170) (axfr.c)
​&emsp;if qtype == ANY and refuse_any option and not tcp -> truncate
​&emsp;[answer_query](https://github.com/NLnetLabs/nsd/blob/NSD_4_3_7_REL/query.c#L1444)







## Part4. create answer response

まずはコードの流れを見てみましょう。

[answer_query](https://github.com/NLnetLabs/nsd/blob/NSD_4_3_7_REL/query.c#L1444) (query.c)
​&emsp;[answer_init](https://github.com/NLnetLabs/nsd/blob/NSD_4_3_7_REL/answer.c#L19) (answer.c) # Reset answer rrset count
​&emsp;[namedb_lookup](https://github.com/NLnetLabs/nsd/blob/NSD_4_3_7_REL/namedb.c#L688) (namedb.c)
​&emsp;&emsp;[domain_table_search](https://github.com/NLnetLabs/nsd/blob/NSD_4_3_7_REL/namedb.c#L366)
​&emsp;&emsp;&emsp;[radname_find_less_equal](https://github.com/NLnetLabs/nsd/blob/NSD_4_3_7_REL/radtree.c#L863) (radtree.c)＃radix tree (patricia tree)
​&emsp;&emsp;&emsp;[rbtree_find_less_equal](https://github.com/NLnetLabs/nsd/blob/NSD_4_3_7_REL/rbtree.c#L460) (rbtree.c) # red black tree
​&emsp;[answer_lookup_zone](https://github.com/NLnetLabs/nsd/blob/NSD_4_3_7_REL/query.c#L1283)
​&emsp;&emsp;[domain_find_zone](https://github.com/NLnetLabs/nsd/blob/NSD_4_3_7_REL/namedb.c#L545) (namedb.c) -> return REFUSE
​&emsp;&emsp;[acl_check_incoming](https://github.com/NLnetLabs/nsd/blob/NSD_4_3_7_REL/options.c#L1478) (options.c) -> return REFUSE
​&emsp;&emsp;If the current "closest encloser" does not exist, it will move from child to parent in order until it does exist. 
​&emsp;&emsp;responding to queries for DS RRs
​&emsp;&emsp;see if the zone has expired (for secondary zones)
​&emsp;&emsp;answer nodata for type DS query at the zone apex
​&emsp;&emsp;[domain_find_ns_rrsets](https://github.com/NLnetLabs/nsd/blob/NSD_4_3_7_REL/namedb.c#L582) (namedb.c) # Delegation check
​&emsp;&emsp;if delegation doesn't exist -> [answer_authoritative](https://github.com/NLnetLabs/nsd/blob/NSD_4_3_7_REL/query.c#L1095)
​&emsp;&emsp;&emsp;process NSEC3
​&emsp;&emsp;&emsp;process DNAME and CNAME
​&emsp;&emsp;&emsp;process wildcard
​&emsp;&emsp;&emsp;some dnssec process...
​&emsp;&emsp;&emsp;if match -> [answer_domain](https://github.com/NLnetLabs/nsd/blob/master/query.c#L982)
​&emsp;&emsp;&emsp;&emsp;if qtype == ANY -> return response to ANY type
​&emsp;&emsp;&emsp;&emsp;if qtype == NSEC3 -> return response to NSEC3 type
​&emsp;&emsp;&emsp;&emsp;if [domain_find_rrset](https://github.com/NLnetLabs/nsd/blob/NSD_4_3_7_REL/namedb.c#L517) (qname, qtype) exists ->  add rrset to (qname, qtype)
​&emsp;&emsp;&emsp;&emsp;if [domain_find_rrset](https://github.com/NLnetLabs/nsd/blob/NSD_4_3_7_REL/namedb.c#L517) (qname, CNAME) exists ->  process CNAME and return response
​&emsp;&emsp;&emsp;&emsp;if none of the above applies, [answer_nodata](https://github.com/NLnetLabs/nsd/blob/NSD_4_3_7_REL/query.c#L949)
​&emsp;&emsp;&emsp;&emsp;if needed, add ns rrset to authority section
​&emsp;&emsp;&emsp;if not match -> [answer_nxdomain](https://github.com/NLnetLabs/nsd/blob/NSD_4_3_7_REL/query.c#L970)
​&emsp;&emsp;if delegation exists -> [answer_delegation](https://github.com/NLnetLabs/nsd/blob/NSD_4_3_7_REL/query.c#L890)
​&emsp;​[encode_answer](https://github.com/NLnetLabs/nsd/blob/NSD_4_3_7_REL/answer.c#L61)
​&emsp;​&emsp;[packet_encode_rrset](https://github.com/NLnetLabs/nsd/blob/NSD_4_3_7_REL/packet.c#L111)
​&emsp;​&emsp;​&emsp;If the minimal response size is exceeded during this process, set the TC bit. -> [TC_SET](https://github.com/NLnetLabs/nsd/blob/NSD_4_3_7_REL/packet.h#L59)


長いですが、ここは細かく見ていきます。
namedb_lookupのところで、問い合わせているqnameに該当するものが存在するかどうかや、closest encloserについて調べているようです。[^1]
[^1]: exact=1(True)となるのはclosest_encloser==qnameとなる場合だと読み取ったのですが、少し自信がないので分かる人がいればコメントいただけると嬉しいです。
ところでclosest encloserとは何でしょうか。[RFC8499](https://datatracker.ietf.org/doc/html/rfc8499)に語義の説明があります。


>Closest encloser:  "The longest existing ancestor of a name." (Quoted from [RFC5155], Section 1.3) 
>An earlier definition is "The node in the zone's tree of existing domain names that has the most labels matching the query name (consecutively, counting from >the root label downward). 
>Each match is a 'label match' and the order of the labels is the same."  (Quoted from [RFC4592], Section 3.3.1)


↓ [JPRSによる日本語訳](https://jprs.jp/tech/material/rfc/RFC8499-ja.txt)より


>Closest encloser(最近接名):
>"ある名前の実在する先祖(訳注: 親、親の親等)の中で最も長いもの"([RFC5155]のセクション1.3から引用)。
>それ以前の定義は、"実在するドメイン名のゾーンの木構造内にあるノードで、問い合わせ名にラベルが(ルートラベルから下方に向けて連続して)最もマッチするもの。
>ここで、マッチとは'ラベルが一致'し、かつラベルの順序が同じであることを意味する"([RFC4592]のセクション3.3.1から引用)。


つまり、下記のようなイメージでしょうか。

```text:ゾーンが下記のような場合
$ORIGIN = example.com.
... snip ...
bar		NS	ns.bar
ns.bar	A	1.2.3.4
www		A	5.6.7.8
```

```text:Closest_encloser(最近接名)の対応
query for www.foo.bar.example.com  -> closest encloser is bar.example.com
query for www.example.com          -> closest encloser is www.example.com
query for nxdomain0123.example.com -> closest encloser is example.com
query for hoge.net                 -> closest encloser is . (root)
```

後のDSクエリに対する処理やdelegationに関する処理のところでClosest encloserが使用されるようです。

続いてanswer_lookup_zoneの処理を見ていきましょう。[^2]
[^2]: 余談ですが、英語のコードリーディングの記事を読んでいると、関数/メソッドを呼ぶという説明のときに"call"の他に"invoke"という単語をよく見かけます。
まずクエリに対応するゾーンを探していますね。[^3] もし見当違いなクエリが届いてしまっている場合はここでREFUSE応答を返してしまいます。
[^3]: クエリ構造体(struct query)のメンバにzoneが用意されており、そこに見つかったゾーンを入れるという実装をしていて、少し独特だなと感じました。
aclのチェックなどを行ったあと、Closest encloserの修正が行われ、DSクエリへの処理をし、ゾーン情報がexpireしていないか確認しています。
その後、まずdelegationを確認し、qnameにマッチするものがゾーンに存在するか確認し、さらにqtypeに合うものが存在するか確認し、それぞれに対応した回答の作成を行います。
フローとしては下記の通りになります。

![nsd_flow.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/208707/6cfebd4e-e5d4-98ca-8480-28b04bec5a8e.png)

answer_lookup_zone から戻ってきたら、作成した回答をバイナリ形式(Wire format)にエンコードします。
この際にでレスポンスサイズがオーバーしている場合は、ここで truncate されてTCビットがセットされます。

そして Part2 へと戻っていき、UDP/TCPハンドラーによってクエリ元へと回答されます。お疲れさまでした。