From 48f7d55f27518d31d5a316669e6ad282b134082c Mon Sep 17 00:00:00 2001
From: Miek Gieben <miek@miek.nl>
Date: Mon, 28 Mar 2016 21:18:16 +0100
Subject: Get positive dnssec stuff going

---
 middleware/file/tree/tree.go | 39 +++++++++++++++------------------------
 1 file changed, 15 insertions(+), 24 deletions(-)

(limited to 'middleware/file/tree/tree.go')

diff --git a/middleware/file/tree/tree.go b/middleware/file/tree/tree.go
index 234060eba..7f51b89f0 100644
--- a/middleware/file/tree/tree.go
+++ b/middleware/file/tree/tree.go
@@ -47,7 +47,7 @@ func newElem(rr dns.RR) *Elem {
 	return &e
 }
 
-// Types returns the types from with type qtype from e.
+// Types returns the RRs with type qtype from e.
 func (e *Elem) Types(qtype uint16) []dns.RR {
 	if rrs, ok := e.m[qtype]; ok {
 		// TODO(miek): length should never be zero here.
@@ -56,6 +56,7 @@ func (e *Elem) Types(qtype uint16) []dns.RR {
 	return nil
 }
 
+// All returns all RRs from e, regardless of type.
 func (e *Elem) All() []dns.RR {
 	list := []dns.RR{}
 	for _, rrs := range e.m {
@@ -64,6 +65,7 @@ func (e *Elem) All() []dns.RR {
 	return list
 }
 
+// Insert inserts rr into e. If rr is equal to existing rrs this is a noop.
 func (e *Elem) Insert(rr dns.RR) {
 	t := rr.Header().Rrtype
 	if e.m == nil {
@@ -130,6 +132,7 @@ func Less(a *Elem, rr dns.RR) int {
 // Assuming the same type and name this will check if the rdata is equal as well.
 func equalRdata(a, b dns.RR) bool {
 	switch x := a.(type) {
+	// TODO(miek): more types, i.e. all types.
 	case *dns.A:
 		return x.A.Equal(b.(*dns.A).A)
 	case *dns.AAAA:
@@ -259,8 +262,7 @@ func (t *Tree) Len() int {
 	return t.Count
 }
 
-// Get returns the first match of q in the Tree. If insertion without
-// replacement is used, this is probably not what you want.
+// Get returns the first match of rr in the Tree.
 func (t *Tree) Get(rr dns.RR) *Elem {
 	if t.Root == nil {
 		return nil
@@ -287,11 +289,8 @@ func (n *Node) search(rr dns.RR) *Node {
 	return n
 }
 
-// Insert inserts the Comparable e into the Tree at the first match found
-// with e or when a nil node is reached. Insertion without replacement can
-// specified by ensuring that e.Compare() never returns 0. If insert without
-// replacement is performed, a distinct query Comparable must be used that
-// can return 0 with a Compare() call.
+// Insert inserts rr into the Tree at the first match found
+// with e or when a nil node is reached.
 func (t *Tree) Insert(rr dns.RR) {
 	var d int
 	t.Root, d = t.Root.insert(rr)
@@ -340,8 +339,7 @@ func (n *Node) insert(rr dns.RR) (root *Node, d int) {
 	return
 }
 
-// DeleteMin deletes the node with the minimum value in the tree. If insertion without
-// replacement has been used, the left-most minimum will be deleted.
+// DeleteMin deletes the node with the minimum value in the tree.
 func (t *Tree) DeleteMin() {
 	if t.Root == nil {
 		return
@@ -369,8 +367,7 @@ func (n *Node) deleteMin() (root *Node, d int) {
 	return
 }
 
-// DeleteMax deletes the node with the maximum value in the tree. If insertion without
-// replacement has been used, the right-most maximum will be deleted.
+// DeleteMax deletes the node with the maximum value in the tree.
 func (t *Tree) DeleteMax() {
 	if t.Root == nil {
 		return
@@ -401,7 +398,7 @@ func (n *Node) deleteMax() (root *Node, d int) {
 	return
 }
 
-// Delete removes rr from the tree, is the node turns empty, that node is return with DeleteNode.
+// Delete removes rr from the tree, is the node turns empty, that node is deleted with DeleteNode.
 func (t *Tree) Delete(rr dns.RR) {
 	if t.Root == nil {
 		return
@@ -420,9 +417,7 @@ func (t *Tree) Delete(rr dns.RR) {
 	}
 }
 
-// DeleteNode deletes the node that matches e according to Compare(). Note that Compare must
-// identify the target node uniquely and in cases where non-unique keys are used,
-// attributes used to break ties must be used to determine tree ordering during insertion.
+// DeleteNode deletes the node that matches rr according to Less().
 func (t *Tree) DeleteNode(rr dns.RR) {
 	if t.Root == nil {
 		return
@@ -469,8 +464,7 @@ func (n *Node) delete(rr dns.RR) (root *Node, d int) {
 	return
 }
 
-// Return the minimum value stored in the tree. This will be the left-most minimum value if
-// insertion without replacement has been used.
+// Min returns the minimum value stored in the tree.
 func (t *Tree) Min() *Elem {
 	if t.Root == nil {
 		return nil
@@ -484,8 +478,7 @@ func (n *Node) min() *Node {
 	return n
 }
 
-// Return the maximum value stored in the tree. This will be the right-most maximum value if
-// insertion without replacement has been used.
+// Max returns the maximum value stored in the tree.
 func (t *Tree) Max() *Elem {
 	if t.Root == nil {
 		return nil
@@ -499,7 +492,7 @@ func (n *Node) max() *Node {
 	return n
 }
 
-// Floor returns the greatest value equal to or less than the query q according to q.Compare().
+// Floor returns the greatest value equal to or less than the rr according to Less().
 func (t *Tree) Floor(rr dns.RR) *Elem {
 	if t.Root == nil {
 		return nil
@@ -528,9 +521,7 @@ func (n *Node) floor(rr dns.RR) *Node {
 	return n
 }
 
-// TODO(successor, predecessor)
-
-// Ceil returns the smallest value equal to or greater than the query q according to q.Compare().
+// Ceil returns the smallest value equal to or greater than the rr according to Less().
 func (t *Tree) Ceil(rr dns.RR) *Elem {
 	if t.Root == nil {
 		return nil
-- 
cgit v1.2.3


From b67ecb3e550a5aa87243bda26085011c0b63999c Mon Sep 17 00:00:00 2001
From: Miek Gieben <miek@miek.nl>
Date: Tue, 29 Mar 2016 20:47:45 +0100
Subject: More nameerror stuff

---
 middleware/file/lookup.go    | 24 ++++++++++++++++++++----
 middleware/file/tree/tree.go |  8 ++++----
 2 files changed, 24 insertions(+), 8 deletions(-)

(limited to 'middleware/file/tree/tree.go')

diff --git a/middleware/file/lookup.go b/middleware/file/lookup.go
index 0e2c4cb80..e89796585 100644
--- a/middleware/file/lookup.go
+++ b/middleware/file/lookup.go
@@ -1,6 +1,8 @@
 package file
 
 import (
+	"fmt"
+
 	"github.com/miekg/coredns/middleware/file/tree"
 	"github.com/miekg/dns"
 )
@@ -35,6 +37,7 @@ func (z *Zone) Lookup(qname string, qtype uint16, do bool) ([]dns.RR, []dns.RR,
 
 	elem := z.Tree.Get(rr)
 	if elem == nil {
+		// wildcard lookup
 		return z.nameError(elem, rr, do)
 	}
 
@@ -66,12 +69,16 @@ func (z *Zone) noData(elem *tree.Elem, do bool) ([]dns.RR, []dns.RR, []dns.RR, R
 }
 
 func (z *Zone) nameError(elem *tree.Elem, rr dns.RR, do bool) ([]dns.RR, []dns.RR, []dns.RR, Result) {
+	ret := []dns.RR{}
 	if do {
-		ret := append([]dns.RR{z.SOA}, z.SIG...)
-		return nil, ret, nil, Success
+		ret = append(ret, z.SIG...)
+		// Now we need two NSEC, one to deny the wildcard and one to deny the name.
+		elem := z.Tree.Prev(rr)
+		fmt.Printf("%+v\n", elem.All())
+		elem = z.Tree.Prev(wildcard(rr))
+		fmt.Printf("%+v\n", elem.All())
 	}
-	// NSECs!
-	return nil, []dns.RR{z.SOA}, nil, NameError
+	return nil, ret, nil, NameError
 }
 
 func (z *Zone) lookupSOA(do bool) ([]dns.RR, []dns.RR, []dns.RR, Result) {
@@ -137,3 +144,12 @@ func signatureForSubType(rrs []dns.RR, subtype uint16) []dns.RR {
 	}
 	return sigs
 }
+
+// wildcard returns rr with the first label exchanged for a wildcard '*'.
+func wildcard(rr dns.RR) dns.RR {
+	// root label, TODO(miek)
+	s := rr.Header().Name
+	i, _ := dns.NextLabel(s, 0)
+	rr.Header().Name = "*" + s[i:]
+	return rr
+}
diff --git a/middleware/file/tree/tree.go b/middleware/file/tree/tree.go
index 7f51b89f0..342bcefa8 100644
--- a/middleware/file/tree/tree.go
+++ b/middleware/file/tree/tree.go
@@ -492,8 +492,8 @@ func (n *Node) max() *Node {
 	return n
 }
 
-// Floor returns the greatest value equal to or less than the rr according to Less().
-func (t *Tree) Floor(rr dns.RR) *Elem {
+// Prev returns the greatest value equal to or less than the rr according to Less().
+func (t *Tree) Prev(rr dns.RR) *Elem {
 	if t.Root == nil {
 		return nil
 	}
@@ -521,8 +521,8 @@ func (n *Node) floor(rr dns.RR) *Node {
 	return n
 }
 
-// Ceil returns the smallest value equal to or greater than the rr according to Less().
-func (t *Tree) Ceil(rr dns.RR) *Elem {
+// Next returns the smallest value equal to or greater than the rr according to Less().
+func (t *Tree) Next(rr dns.RR) *Elem {
 	if t.Root == nil {
 		return nil
 	}
-- 
cgit v1.2.3


From bf6d90600be7eac782e076b7c5f334e83ba9dea0 Mon Sep 17 00:00:00 2001
From: Miek Gieben <miek@miek.nl>
Date: Wed, 30 Mar 2016 16:45:02 +0000
Subject: add closest encloser stuff

---
 middleware/canonical.go         |  7 +++++--
 middleware/file/closest.go      | 16 ++++++++++++++++
 middleware/file/closest_test.go | 34 ++++++++++++++++++++++++++++++++++
 middleware/file/dnssec_test.go  |  3 ++-
 middleware/file/lookup.go       |  1 +
 middleware/file/tree/tree.go    | 19 ++++---------------
 6 files changed, 62 insertions(+), 18 deletions(-)
 create mode 100644 middleware/file/closest.go
 create mode 100644 middleware/file/closest_test.go

(limited to 'middleware/file/tree/tree.go')

diff --git a/middleware/canonical.go b/middleware/canonical.go
index 5d51231c2..b8953f655 100644
--- a/middleware/canonical.go
+++ b/middleware/canonical.go
@@ -17,8 +17,11 @@ func Less(a, b string) int {
 	aj := len(a)
 	bj := len(b)
 	for {
-		ai, _ := dns.PrevLabel(a, i)
-		bi, _ := dns.PrevLabel(b, i)
+		ai, oka := dns.PrevLabel(a, i)
+		bi, okb := dns.PrevLabel(b, i)
+		if oka && okb {
+			return 0
+		}
 		// sadly this []byte will allocate...
 		ab := []byte(a[ai:aj])
 		toLowerAndDDD(ab)
diff --git a/middleware/file/closest.go b/middleware/file/closest.go
new file mode 100644
index 000000000..daee27314
--- /dev/null
+++ b/middleware/file/closest.go
@@ -0,0 +1,16 @@
+package file
+
+import "github.com/miekg/dns"
+
+// ClosestEncloser returns the closest encloser for rr.
+func (z *Zone) ClosestEncloser(rr dns.RR) string {
+	elem := z.Tree.Prev(rr)
+	if elem == nil {
+		// SOA?
+		return ""
+	}
+	for _, r := range elem.All() {
+		return r.Header().Name
+	}
+	return ""
+}
diff --git a/middleware/file/closest_test.go b/middleware/file/closest_test.go
new file mode 100644
index 000000000..643e4943f
--- /dev/null
+++ b/middleware/file/closest_test.go
@@ -0,0 +1,34 @@
+package file
+
+import (
+	"strings"
+	"testing"
+
+	"github.com/miekg/dns"
+)
+
+func TestClosestEncloser(t *testing.T) {
+	z, err := Parse(strings.NewReader(dbMiekNL), testzone, "stdin")
+	if err != nil {
+		t.Fatalf("expect no error when reading zone, got %q", err)
+	}
+
+	tests := []struct {
+		in, out string
+	}{
+		{"miek.nl.", "miek.nl."},
+		{"blaat.miek.nl.", "miek.nl."},
+		{"blaat.blaat.miek.nl.", "miek.nl."},
+		{"blaat.a.miek.nl.", "archive.miek.nl."},
+	}
+
+	mk, _ := dns.TypeToRR[dns.TypeA]
+	rr := mk()
+	for _, tc := range tests {
+		rr.Header().Name = tc.in
+		ce := z.ClosestEncloser(rr)
+		if ce != tc.out {
+			t.Errorf("expected ce to be %s for %s, got %s", tc.out, tc.in, ce)
+		}
+	}
+}
diff --git a/middleware/file/dnssec_test.go b/middleware/file/dnssec_test.go
index 96eff6660..ed8b6a607 100644
--- a/middleware/file/dnssec_test.go
+++ b/middleware/file/dnssec_test.go
@@ -61,9 +61,10 @@ var dnssecTestCases = []coretest.Case{
 		},
 	},
 	{
-		Qname: "b.miek.nl.", Qtype: dns.TypeA, // Do: true, // need sorting first
+		Qname: "b.miek.nl.", Qtype: dns.TypeA, Do: true,
 		Rcode: dns.RcodeNameError,
 		Ns: []dns.RR{
+			coretest.RRSIG("miek.nl.	1800	IN	RRSIG	SOA 8 2 1800 20160426031301 20160327031301 12051 miek.nl. FIrzy07acBbtyQczy1dc="),
 			coretest.SOA("miek.nl.	1800	IN	SOA	linode.atoom.net. miek.miek.nl. 1282630057 14400 3600 604800 14400"),
 		},
 	},
diff --git a/middleware/file/lookup.go b/middleware/file/lookup.go
index 3d3de9679..10f308cf1 100644
--- a/middleware/file/lookup.go
+++ b/middleware/file/lookup.go
@@ -2,6 +2,7 @@ package file
 
 import (
 	"github.com/miekg/coredns/middleware/file/tree"
+
 	"github.com/miekg/dns"
 )
 
diff --git a/middleware/file/tree/tree.go b/middleware/file/tree/tree.go
index 342bcefa8..05dfdfa7d 100644
--- a/middleware/file/tree/tree.go
+++ b/middleware/file/tree/tree.go
@@ -17,8 +17,7 @@ package tree
 // TODO(miek): fix docs
 
 import (
-	"strings"
-
+	"github.com/miekg/coredns/middleware"
 	"github.com/miekg/dns"
 )
 
@@ -112,21 +111,11 @@ func (e *Elem) Delete(rr dns.RR) (empty bool) {
 	return
 }
 
-// TODO(miek): need case ignore compare that is more efficient.
 func Less(a *Elem, rr dns.RR) int {
-	aname := ""
-	for _, ar := range a.m {
-		aname = strings.ToLower(ar[0].Header().Name)
-		break
-	}
-	rname := strings.ToLower(rr.Header().Name)
-	if aname == rname {
-		return 0
-	}
-	if aname < rname {
-		return -1
+	for _, ar := range a.m { // Get first element in a
+		return middleware.Less(ar[0].Header().Name, rr.Header().Name)
 	}
-	return 1
+	return 0
 }
 
 // Assuming the same type and name this will check if the rdata is equal as well.
-- 
cgit v1.2.3


From 8feef98188d7823b9c7fc99469cb2f588b61757d Mon Sep 17 00:00:00 2001
From: Miek Gieben <miek@miek.nl>
Date: Wed, 30 Mar 2016 20:13:48 +0100
Subject: Fix closest encloser

---
 middleware/canonical.go         |  4 ++--
 middleware/file/closest.go      | 22 +++++++++++++--------
 middleware/file/closest_test.go |  7 +++++--
 middleware/file/tree/tree.go    | 42 ++++++++++++++++++++++++++++++++++++-----
 4 files changed, 58 insertions(+), 17 deletions(-)

(limited to 'middleware/file/tree/tree.go')

diff --git a/middleware/canonical.go b/middleware/canonical.go
index b8953f655..9dacba78c 100644
--- a/middleware/canonical.go
+++ b/middleware/canonical.go
@@ -8,10 +8,10 @@ import (
 
 // Less returns <0 when a is less than b, 0 when they are equal and
 // >0 when a is larger than b.
-// The function order names in DNSSEC canonical order.
+// The function orders names in DNSSEC canonical order: RFC 4034s section-6.1
 //
 // See http://bert-hubert.blogspot.co.uk/2015/10/how-to-do-fast-canonical-ordering-of.html
-// for a blog article on how we do this. And https://tools.ietf.org/html/rfc4034#section-6.1 .
+// for a blog article on this implementation:
 func Less(a, b string) int {
 	i := 1
 	aj := len(a)
diff --git a/middleware/file/closest.go b/middleware/file/closest.go
index daee27314..8f9d9a8ba 100644
--- a/middleware/file/closest.go
+++ b/middleware/file/closest.go
@@ -4,13 +4,19 @@ import "github.com/miekg/dns"
 
 // ClosestEncloser returns the closest encloser for rr.
 func (z *Zone) ClosestEncloser(rr dns.RR) string {
-	elem := z.Tree.Prev(rr)
-	if elem == nil {
-		// SOA?
-		return ""
-	}
-	for _, r := range elem.All() {
-		return r.Header().Name
+	// tree/tree.go does not store a parent *Node pointer, so we can't
+	// just follow up the tree. TODO(miek): fix.
+
+	offset, end := dns.NextLabel(rr.Header().Name, 0)
+	for !end {
+		elem := z.Tree.Get(rr)
+		if elem != nil {
+			return elem.Name()
+		}
+		rr.Header().Name = rr.Header().Name[offset:]
+
+		offset, end = dns.NextLabel(rr.Header().Name, offset)
 	}
-	return ""
+
+	return z.SOA.Header().Name
 }
diff --git a/middleware/file/closest_test.go b/middleware/file/closest_test.go
index 643e4943f..db0b718b2 100644
--- a/middleware/file/closest_test.go
+++ b/middleware/file/closest_test.go
@@ -17,9 +17,12 @@ func TestClosestEncloser(t *testing.T) {
 		in, out string
 	}{
 		{"miek.nl.", "miek.nl."},
+		{"www.miek.nl.", "www.miek.nl."},
+
 		{"blaat.miek.nl.", "miek.nl."},
-		{"blaat.blaat.miek.nl.", "miek.nl."},
-		{"blaat.a.miek.nl.", "archive.miek.nl."},
+		{"blaat.www.miek.nl.", "www.miek.nl."},
+		{"www.blaat.miek.nl.", "miek.nl."},
+		{"blaat.a.miek.nl.", "a.miek.nl."},
 	}
 
 	mk, _ := dns.TypeToRR[dns.TypeA]
diff --git a/middleware/file/tree/tree.go b/middleware/file/tree/tree.go
index 05dfdfa7d..ca616ad67 100644
--- a/middleware/file/tree/tree.go
+++ b/middleware/file/tree/tree.go
@@ -13,7 +13,7 @@
 // Heavily modified by Miek Gieben for use in DNS zones.
 package tree
 
-// TODO(miek): locking? lockfree
+// TODO(miek): locking? lockfree would be nice. Will probably go for fine grained locking on the name level.
 // TODO(miek): fix docs
 
 import (
@@ -64,6 +64,14 @@ func (e *Elem) All() []dns.RR {
 	return list
 }
 
+// Return the domain name for this element.
+func (e *Elem) Name() string {
+	for _, rrs := range e.m {
+		return rrs[0].Header().Name
+	}
+	return ""
+}
+
 // Insert inserts rr into e. If rr is equal to existing rrs this is a noop.
 func (e *Elem) Insert(rr dns.RR) {
 	t := rr.Header().Rrtype
@@ -112,10 +120,7 @@ func (e *Elem) Delete(rr dns.RR) (empty bool) {
 }
 
 func Less(a *Elem, rr dns.RR) int {
-	for _, ar := range a.m { // Get first element in a
-		return middleware.Less(ar[0].Header().Name, rr.Header().Name)
-	}
-	return 0
+	return middleware.Less(rr.Header().Name, a.Name())
 }
 
 // Assuming the same type and name this will check if the rdata is equal as well.
@@ -539,6 +544,33 @@ func (n *Node) ceil(rr dns.RR) *Node {
 	return n
 }
 
+// Do performs fn on all values stored in the tree. A boolean is returned indicating whether the
+// Do traversal was interrupted by an Operation returning true. If fn alters stored values' sort
+// relationships, future tree operation behaviors are undefined.
+func (t *Tree) Do(fn func(e *Elem) bool) bool {
+	if t.Root == nil {
+		return false
+	}
+	return t.Root.do(fn)
+}
+
+func (n *Node) do(fn func(e *Elem) bool) (done bool) {
+	if n.Left != nil {
+		done = n.Left.do(fn)
+		if done {
+			return
+		}
+	}
+	done = fn(n.Elem)
+	if done {
+		return
+	}
+	if n.Right != nil {
+		done = n.Right.do(fn)
+	}
+	return
+}
+
 /*
 Copyright ©2012 The bíogo Authors. All rights reserved.
 
-- 
cgit v1.2.3