osbase/net/dns/forward: add DNS forward handler
This adds a DNS server handler for forwarding queries to upstream DNS
resolvers, with a built-in cache. The implementation is partially based
on CoreDNS. The proxy, cache and up packages are only lightly modified.
The forward package itself however is mostly new code. Unlike CoreDNS,
it supports changing upstreams at runtime, and has integrated caching
and answer order randomization.
Some improvements over CoreDNS:
- Concurrent identical queries only result in one upstream query.
- In case of errors, Extended DNS Errors are added to replies.
- Very large replies are not stored in the cache to avoid using too much
memory.
Change-Id: I42294ae4997d621a6e55c98e46a04874eab75c99
Reviewed-on: https://review.monogon.dev/c/monogon/+/3258
Reviewed-by: Lorenz Brun <lorenz@monogon.tech>
Tested-by: Jenkins CI
diff --git a/osbase/net/dns/forward/cache/cache.go b/osbase/net/dns/forward/cache/cache.go
new file mode 100644
index 0000000..8c151a6
--- /dev/null
+++ b/osbase/net/dns/forward/cache/cache.go
@@ -0,0 +1,115 @@
+// Package cache implements a cache. The cache hold 256 shards, each shard
+// holds a cache: a map with a mutex. There is no fancy expunge algorithm, it
+// just randomly evicts elements when it gets full.
+package cache
+
+// Taken and modified from CoreDNS, under Apache 2.0.
+
+import (
+ "sync"
+
+ "golang.org/x/sys/cpu"
+)
+
+const shardSize = 256
+
+// Cache is cache.
+type Cache[T any] struct {
+ shards [shardSize]shard[T]
+}
+
+// shard is a cache with random eviction.
+type shard[T any] struct {
+ items map[uint64]T
+ size int
+
+ sync.RWMutex
+
+ _ cpu.CacheLinePad
+}
+
+// New returns a new cache.
+func New[T any](size int) *Cache[T] {
+ ssize := size / shardSize
+ if ssize < 4 {
+ ssize = 4
+ }
+
+ c := &Cache[T]{}
+
+ // Initialize all the shards
+ for i := 0; i < shardSize; i++ {
+ c.shards[i] = shard[T]{items: make(map[uint64]T), size: ssize}
+ }
+ return c
+}
+
+// Get returns the element under key, and whether the element exists.
+func (c *Cache[T]) Get(key uint64) (el T, exists bool) {
+ shard := key % shardSize
+ return c.shards[shard].Get(key)
+}
+
+// Put adds a new element to the cache. If the element already exists,
+// it is overwritten.
+func (c *Cache[T]) Put(key uint64, el T) {
+ shard := key % shardSize
+ c.shards[shard].Put(key, el)
+}
+
+// GetOrPut returns the element under key if it exists,
+// or else stores newEl there. This operation is atomic.
+func (c *Cache[T]) GetOrPut(key uint64, newEl T) (el T, exists bool) {
+ shard := key % shardSize
+ return c.shards[shard].GetOrPut(key, newEl)
+}
+
+// Remove removes the element indexed with key.
+func (c *Cache[T]) Remove(key uint64) {
+ shard := key % shardSize
+ c.shards[shard].Remove(key)
+}
+
+func (s *shard[T]) Get(key uint64) (el T, exists bool) {
+ s.RLock()
+ el, exists = s.items[key]
+ s.RUnlock()
+ return
+}
+
+func (s *shard[T]) Put(key uint64, el T) {
+ s.Lock()
+ if len(s.items) >= s.size {
+ if _, ok := s.items[key]; !ok {
+ for k := range s.items {
+ delete(s.items, k)
+ break
+ }
+ }
+ }
+ s.items[key] = el
+ s.Unlock()
+}
+
+func (s *shard[T]) GetOrPut(key uint64, newEl T) (el T, exists bool) {
+ s.Lock()
+ el, exists = s.items[key]
+ if !exists {
+ if len(s.items) >= s.size {
+ for k := range s.items {
+ delete(s.items, k)
+ break
+ }
+ }
+ s.items[key] = newEl
+ el = newEl
+ }
+ s.Unlock()
+ return
+}
+
+func (s *shard[T]) Remove(key uint64) {
+ s.Lock()
+ delete(s.items, key)
+ s.Unlock()
+}