func searchServerIP(domain string, version int, DNSservers []string) (answer *dns.Msg, err error) {
	DNSserver := DNSservers[rand.Intn(len(DNSservers))]
	for i := 1; i <= 3; i++ {
		if DNSserver == "" {
			DNSserver = DNSservers[rand.Intn(len(DNSservers))]
		}
	}
	if DNSserver == "" {
		return nil, errors.New("DNSserver is an empty string")
	}
	dnsRequest := new(dns.Msg)
	if dnsRequest == nil {
		return nil, errors.New("Can not new dnsRequest")
	}
	dnsClient := new(dns.Client)
	if dnsClient == nil {
		return nil, errors.New("Can not new dnsClient")
	}
	if version == 4 {
		dnsRequest.SetQuestion(domain+".", dns.TypeA)
	} else if version == 6 {
		dnsRequest.SetQuestion(domain+".", dns.TypeAAAA)
	} else {
		return nil, errors.New("wrong parameter in version")
	}
	dnsRequest.SetEdns0(4096, true)
	answer, _, err = dnsClient.Exchange(dnsRequest, DNSserver)
	if err != nil {
		return nil, err
	}
	return answer, nil
}

func (d *DNSServer) handleRecursive(client *dns.Client, defaultMaxResponseSize int) func(dns.ResponseWriter, *dns.Msg) {
	return func(w dns.ResponseWriter, req *dns.Msg) {
		d.ns.debugf("recursive request: %+v", *req)

		// Resolve unqualified names locally
		if len(req.Question) == 1 && req.Question[0].Qtype == dns.TypeA {
			hostname := dns.Fqdn(req.Question[0].Name)
			if strings.Count(hostname, ".") == 1 {
				d.handleLocal(defaultMaxResponseSize)(w, req)
				return
			}
		}

		for _, server := range d.upstream.Servers {
			reqCopy := req.Copy()
			reqCopy.Id = dns.Id()
			response, _, err := client.Exchange(reqCopy, fmt.Sprintf("%s:%s", server, d.upstream.Port))
			if err != nil || response == nil {
				d.ns.debugf("error trying %s: %v", server, err)
				continue
			}
			d.ns.debugf("response: %+v", response)
			response.Id = req.Id
			if err := w.WriteMsg(response); err != nil {
				d.ns.infof("error responding: %v", err)
			}
			return
		}

		d.errorResponse(req, dns.RcodeServerFailure, w)
	}
}

// Perform DNS resolution
func resolve(w http.ResponseWriter, r *http.Request, server string, domain string, querytype uint16) {
	m := new(dns.Msg)
	m.SetQuestion(domain, querytype)
	m.MsgHdr.RecursionDesired = true

	w.Header().Set("Content-Type", "application/json")
	w.Header().Set("Access-Control-Allow-Origin", "*")

	c := new(dns.Client)

Redo:
	if in, _, err := c.Exchange(m, server); err == nil { // Second return value is RTT, not used for now
		if in.MsgHdr.Truncated {
			c.Net = "tcp"
			goto Redo
		}

		switch in.MsgHdr.Rcode {
		case dns.RcodeServerFailure:
			error(w, 500, 502, "The name server encountered an internal failure while processing this request (SERVFAIL)")
		case dns.RcodeNameError:
			error(w, 500, 503, "Some name that ought to exist, does not exist (NXDOMAIN)")
		case dns.RcodeRefused:
			error(w, 500, 505, "The name server refuses to perform the specified operation for policy or security reasons (REFUSED)")
		default:
			jsonify(w, r, in.Question, in.Answer, in.Ns, in.Extra)
		}
	} else {
		error(w, 500, 501, "DNS server could not be reached")
	}
}

func TestDNS_NonExistingLookup(t *testing.T) {
	dir, srv := makeDNSServer(t)
	defer os.RemoveAll(dir)
	defer srv.agent.Shutdown()

	addr, _ := srv.agent.config.ClientListener("", srv.agent.config.Ports.DNS)

	// lookup a non-existing node, we should receive a SOA
	m := new(dns.Msg)
	m.SetQuestion("nonexisting.consul.", dns.TypeANY)

	c := new(dns.Client)
	in, _, err := c.Exchange(m, addr.String())
	if err != nil {
		t.Fatalf("err: %v", err)
	}

	if len(in.Ns) != 1 {
		t.Fatalf("Bad: %#v %#v", in, len(in.Answer))
	}

	soaRec, ok := in.Ns[0].(*dns.SOA)
	if !ok {
		t.Fatalf("Bad: %#v", in.Ns[0])
	}
	if soaRec.Hdr.Ttl != 0 {
		t.Fatalf("Bad: %#v", in.Ns[0])
	}

}

func TestDNS_ServiceLookup_TagPeriod(t *testing.T) {
	dir, srv := makeDNSServer(t)
	defer os.RemoveAll(dir)
	defer srv.agent.Shutdown()

	testutil.WaitForLeader(t, srv.agent.RPC, "dc1")

	// Register node
	args := &structs.RegisterRequest{
		Datacenter: "dc1",
		Node:       "foo",
		Address:    "127.0.0.1",
		Service: &structs.NodeService{
			Service: "db",
			Tags:    []string{"v1.master"},
			Port:    12345,
		},
	}

	var out struct{}
	if err := srv.agent.RPC("Catalog.Register", args, &out); err != nil {
		t.Fatalf("err: %v", err)
	}

	m := new(dns.Msg)
	m.SetQuestion("v1.master.db.service.consul.", dns.TypeSRV)

	c := new(dns.Client)
	addr, _ := srv.agent.config.ClientListener("", srv.agent.config.Ports.DNS)
	in, _, err := c.Exchange(m, addr.String())
	if err != nil {
		t.Fatalf("err: %v", err)
	}

	if len(in.Answer) != 1 {
		t.Fatalf("Bad: %#v", in)
	}

	srvRec, ok := in.Answer[0].(*dns.SRV)
	if !ok {
		t.Fatalf("Bad: %#v", in.Answer[0])
	}
	if srvRec.Port != 12345 {
		t.Fatalf("Bad: %#v", srvRec)
	}
	if srvRec.Target != "foo.node.dc1.consul." {
		t.Fatalf("Bad: %#v", srvRec)
	}

	aRec, ok := in.Extra[0].(*dns.A)
	if !ok {
		t.Fatalf("Bad: %#v", in.Extra[0])
	}
	if aRec.Hdr.Name != "foo.node.dc1.consul." {
		t.Fatalf("Bad: %#v", in.Extra[0])
	}
	if aRec.A.String() != "127.0.0.1" {
		t.Fatalf("Bad: %#v", in.Extra[0])
	}
}

func TestMsgOverflow(t *testing.T) {
	if testing.Short() {
		t.Skip("skipping test in short mode.")
	}

	s := newTestServer(t, false)
	defer s.Stop()

	c := new(dns.Client)
	m := new(dns.Msg)

	// TODO(miek): rethink how to enable metrics in tests.
	if !metricsDone {
		Metrics()
	}

	for i := 0; i < 2000; i++ {
		is := strconv.Itoa(i)
		m := &msg.Service{
			Host: "2001::" + is, Key: "machine" + is + ".machines.skydns.test.",
		}
		addService(t, s, m.Key, 0, m)
		defer delService(t, s, m.Key)
	}
	m.SetQuestion("machines.skydns.test.", dns.TypeSRV)
	resp, _, err := c.Exchange(m, "127.0.0.1:"+StrPort)
	if err != nil {
		t.Fatal(err)
	}
	t.Logf("%s", resp)

	if resp.Rcode != dns.RcodeServerFailure {
		t.Fatalf("expecting server failure, got %d", resp.Rcode)
	}
}

func main() {
	if len(os.Args) != 2 {
		fmt.Printf("%s NAMESERVER\n", os.Args[0])
		os.Exit(1)
	}
	conf, _ := dns.ClientConfigFromFile("/etc/resolv.conf")

	m := new(dns.Msg)
	m.Question = make([]dns.Question, 1)
	c := new(dns.Client)

	addr := addresses(conf, c, os.Args[1])
	if len(addr) == 0 {
		fmt.Printf("No address found for %s\n", os.Args[1])
		os.Exit(1)
	}
	for _, a := range addr {
		m.Question[0] = dns.Question{"version.bind.", dns.TypeTXT, dns.ClassCHAOS}
		in, rtt, _ := c.ExchangeRtt(m, a)
		if in != nil && len(in.Answer) > 0 {
			fmt.Printf("(time %.3d µs) %v\n", rtt/1e3, in.Answer[0])
		}
		m.Question[0] = dns.Question{"hostname.bind.", dns.TypeTXT, dns.ClassCHAOS}
		in, rtt, _ = c.ExchangeRtt(m, a)
		if in != nil && len(in.Answer) > 0 {
			fmt.Printf("(time %.3d µs) %v\n", rtt/1e3, in.Answer[0])
		}
	}
}

func lookup(name string, queryType uint16, client *dns.Client, servAddr string, suffix string, edns bool) (*dns.Msg, error) {
	msg := &dns.Msg{}
	lname := strings.Join([]string{name, suffix}, ".")
	msg.SetQuestion(dns.Fqdn(lname), queryType)

	if edns {
		msg.SetEdns0(dns.DefaultMsgSize, false)
	}

	response, _, err := client.Exchange(msg, servAddr)
	if err == dns.ErrTruncated {
		if client.Net == "tcp" {
			return nil, fmt.Errorf("got truncated message on TCP (64kiB limit exceeded?)")
		}
		if edns { // Truncated even though EDNS is used
			client.Net = "tcp"
		}
		return lookup(name, queryType, client, servAddr, suffix, !edns)
	}
	if err != nil {
		return nil, err
	}
	if msg.Id != response.Id {
		return nil, fmt.Errorf("DNS ID mismatch, request: %d, response: %d", msg.Id, response.Id)
	}
	return response, nil
}

// perform a DNS query and assert the reply code, number or answers, etc
func assertExchange(t *testing.T, z string, ty uint16, minAnswers int, maxAnswers int, expErr int) *dns.Msg {
	c := new(dns.Client)
	c.UDPSize = testUDPBufSize
	m := new(dns.Msg)
	m.RecursionDesired = true
	m.SetQuestion(z, ty)
	m.SetEdns0(testUDPBufSize, false) // we don't want to play with truncation here...

	r, _, err := c.Exchange(m, fmt.Sprintf("127.0.0.1:%d", testPort))
	t.Logf("Response:\n%+v\n", r)
	wt.AssertNoErr(t, err)
	if minAnswers == 0 && maxAnswers == 0 {
		wt.AssertStatus(t, r.Rcode, expErr, "DNS response code")
	} else {
		wt.AssertStatus(t, r.Rcode, dns.RcodeSuccess, "DNS response code")
	}
	answers := len(r.Answer)
	if minAnswers >= 0 && answers < minAnswers {
		wt.Fatalf(t, "Number of answers >= %d", minAnswers)
	}
	if maxAnswers >= 0 && answers > maxAnswers {
		wt.Fatalf(t, "Number of answers <= %d", maxAnswers)
	}
	return r
}

func recurseNS(c *dns.Client, fulldomain string, labels []string) (string, error) {
	var lastns string
	if len(labels) > 0 {
		var err error
		lastns, err = recurseNS(c, fulldomain, labels[1:])
		if err != nil {
			fmt.Printf("ERROR WITH LABELS %v: %s\n", labels, err.Error())
			return "", err
		}
	} else {
		return rootns[rand.Intn(len(rootns))], nil
	}

	m := new(dns.Msg)
	m.SetQuestion(fulldomain, dns.TypeA)
	r, _, err := c.Exchange(m, lastns+":53")
	if err != nil {
		return "", fmt.Errorf("error getting NS for %q: %q", fulldomain, err.Error())
	}

	nslist := make([]string, 0)
	if len(r.Ns) > 0 {
		for i := range r.Ns {
			if ns, ok := r.Ns[i].(*dns.NS); ok {
				nslist = append(nslist, ns.Ns)
			}
		}
	}

	if len(nslist) == 0 {
		return lastns, nil
	}

	return nslist[rand.Intn(len(nslist))], nil
}

// Send a DNS query via UDP, configured by a Request object. If successful,
// stores response details in Result object, otherwise, returns Result object
// with an error string.
func SendQuery(request *Request) (result Result, err error) {
	log.Printf("Sending query: %s", request)
	result.Request = *request

	record_type, ok := dns.StringToType[request.RecordType]
	if !ok {
		result.Error = fmt.Sprintf("Invalid type: %s", request.RecordType)
		return result, errors.New(result.Error)
	}

	m := new(dns.Msg)
	if request.VerifySignature == true {
		log.Printf("SetEdns0 for %s", request.RecordName)
		m.SetEdns0(4096, true)
	}
	m.SetQuestion(request.RecordName, record_type)
	c := new(dns.Client)
	in, rtt, err := c.Exchange(m, request.Destination)
	// log.Printf("Answer: %s [%d] %s", in, rtt, err)

	result.Duration = rtt
	if err != nil {
		result.Error = err.Error()
	} else {
		for _, rr := range in.Answer {
			answer := Answer{
				Ttl:    rr.Header().Ttl,
				Name:   rr.Header().Name,
				String: rr.String(),
			}
			result.Answers = append(result.Answers, answer)
		}
	}
	return result, nil
}

// shouldTransfer checks the primaries of zone, retrieves the SOA record, checks the current serial
// and the remote serial and will return true if the remote one is higher than the locally configured one.
func (z *Zone) shouldTransfer() (bool, error) {
	c := new(dns.Client)
	c.Net = "tcp" // do this query over TCP to minimize spoofing
	m := new(dns.Msg)
	m.SetQuestion(z.origin, dns.TypeSOA)

	var Err error
	serial := -1

Transfer:
	for _, tr := range z.TransferFrom {
		Err = nil
		ret, err := middleware.Exchange(c, m, tr)
		if err != nil || ret.Rcode != dns.RcodeSuccess {
			Err = err
			continue
		}
		for _, a := range ret.Answer {
			if a.Header().Rrtype == dns.TypeSOA {
				serial = int(a.(*dns.SOA).Serial)
				break Transfer
			}
		}
	}
	if serial == -1 {
		return false, Err
	}
	return less(z.Apex.SOA.Serial, uint32(serial)), Err
}

func (api *APIv1) ClaimDomain(w http.ResponseWriter, r *http.Request) {
	vars := mux.Vars(r)
	uid := context.Get(r, "uid").(*gouuid.UUID)
	domain := dns.Fqdn(vars["domain"])
	m := new(dns.Msg)
	m.SetQuestion(domain, dns.TypeCNAME)
	c := new(dns.Client)
	rr, _, err := c.Exchange(m, "8.8.8.8:53")
	if err != nil {
		log.Printf("Could not check domain’s records: %s", err)
		http.Error(w, "Could not check domain’s records", http.StatusInternalServerError)
		return
	}

	if !containsValidCNAMERecord(uid, rr.Answer) {
		http.Error(w, "Did not find your UID in domain’s CNAME records", http.StatusUnauthorized)
		return
	}

	err = api.domainmgr.ClaimDomain(vars["domain"], uid)
	if err == ErrAlreadyClaimed {
		log.Printf("Domain %s alread claimed", vars["domain"])
		http.Error(w, "Domain already claimed", http.StatusForbidden)
		return
	} else if err != nil {
		log.Printf("Could not claim domain %s: %s", vars["domain"], err)
		http.Error(w, "Could not claim domain", http.StatusInternalServerError)
		return
	}
	http.Error(w, "", http.StatusNoContent)
}

// NewDNSResolverImpl constructs a new DNS resolver object that utilizes the
// provided list of DNS servers for resolution.
func NewDNSResolverImpl(
	readTimeout time.Duration,
	servers []string,
	caaSERVFAILExceptions map[string]bool,
	stats metrics.Scope,
	clk clock.Clock,
	maxTries int,
) *DNSResolverImpl {
	// TODO(jmhodges): make constructor use an Option func pattern
	dnsClient := new(dns.Client)

	// Set timeout for underlying net.Conn
	dnsClient.ReadTimeout = readTimeout
	dnsClient.Net = "tcp"

	return &DNSResolverImpl{
		dnsClient:                dnsClient,
		servers:                  servers,
		allowRestrictedAddresses: false,
		caaSERVFAILExceptions:    caaSERVFAILExceptions,
		maxTries:                 maxTries,
		clk:                      clk,
		stats:                    stats,
		txtStats:                 stats.NewScope("TXT"),
		aStats:                   stats.NewScope("A"),
		aaaaStats:                stats.NewScope("AAAA"),
		caaStats:                 stats.NewScope("CAA"),
		mxStats:                  stats.NewScope("MX"),
	}
}

func TestDNSTtlRR(t *testing.T) {
	s := newTestServerDNSSEC(t, false)
	defer s.Stop()

	serv := &msg.Service{Host: "10.0.0.2", Key: "ttl.skydns.test.", Ttl: 360}
	addService(t, s, serv.Key, time.Duration(serv.Ttl)*time.Second, serv)
	defer delService(t, s, serv.Key)

	c := new(dns.Client)

	tc := dnsTestCases[9] // TTL Test
	t.Logf("%v\n", tc)
	m := new(dns.Msg)
	m.SetQuestion(tc.Qname, tc.Qtype)
	if tc.dnssec == true {
		m.SetEdns0(4096, true)
	}
	resp, _, err := c.Exchange(m, "127.0.0.1:"+StrPort)
	if err != nil {
		t.Errorf("failing: %s: %s\n", m.String(), err.Error())
	}
	t.Logf("%s\n", resp)

	for i, a := range resp.Answer {
		if a.Header().Ttl != 360 {
			t.Errorf("Answer %d should have a Header TTL of %d, but has %d", i, 360, a.Header().Ttl)
		}
	}
}

func DnsQuery(query string, wg *sync.WaitGroup, config *dns.ClientConfig, cm *chanman.ChanMan) {
	defer wg.Done()
	dnsClient := new(dns.Client)
	message := new(dns.Msg)
	message.SetQuestion(dns.Fqdn(query), dns.TypeA)
	message.RecursionDesired = true

	response, rtt, err := dnsClient.Exchange(message, net.JoinHostPort(config.Servers[0], "53"))

	if err != nil {
		log.Println(err)
		cm.RunChan <- true
	}

	if response == nil {
	} else {
		if response.Rcode != dns.RcodeSuccess {
			log.Println(" query fail")
		}
		var stat = new(dnsstat.Info)
		stat.Rtt = rtt
		cm.StatsChan <- stat
		cm.RunChan <- true
	}
}

func (p *Parser) handleExplanation() string {
	resolvedDomain, err := ParseMacroToken(p, p.Explanation)
	if err != nil || isEmpty(&resolvedDomain) {
		// TODO(zaccone): Should we return some internal error
		return ""
	}
	resolvedDomain = NormalizeHost(resolvedDomain)
	query := new(dns.Msg)
	query.SetQuestion(resolvedDomain, dns.TypeTXT)
	c := new(dns.Client)
	response, _, err := c.Exchange(query, Nameserver)
	if err != nil || (response != nil && response.Rcode != dns.RcodeSuccess) {
		return ""
	}

	explanation := make([]string, 0, len(response.Answer))
	for _, answer := range response.Answer {
		if q, ok := answer.(*dns.TXT); ok {
			for _, txt := range q.Txt {
				explanation = append(explanation, txt)
			}
		}
	}

	// RFC 7208, section 6.2 specifies that result string should be
	// concatenated with no spaces.
	parsedExplanation, err := ParseMacro(p, strings.Join(explanation, ""))
	if err != nil {
		return ""
	}
	return parsedExplanation
}

func lookup(msg *dns.Msg, client *dns.Client, server string, edns bool) (*dns.Msg, error) {
	if edns {
		opt := &dns.OPT{
			Hdr: dns.RR_Header{
				Name:   ".",
				Rrtype: dns.TypeOPT,
			},
		}
		opt.SetUDPSize(dns.DefaultMsgSize)
		msg.Extra = append(msg.Extra, opt)
	}

	response, _, err := client.Exchange(msg, server)
	if err != nil {
		return nil, err
	}

	if msg.Id != response.Id {
		return nil, fmt.Errorf("DNS ID mismatch, request: %d, response: %d", msg.Id, response.Id)
	}

	if response.MsgHdr.Truncated {
		if client.Net == "tcp" {
			return nil, fmt.Errorf("Got truncated message on tcp")
		}

		if edns { // Truncated even though EDNS is used
			client.Net = "tcp"
		}

		return lookup(msg, client, server, !edns)
	}

	return response, nil
}

func TestDNSTtlRRset(t *testing.T) {
	s := newTestServerDNSSEC(t, false)
	defer s.Stop()

	ttl := uint32(60)
	for _, serv := range services {
		addService(t, s, serv.Key, uint64(ttl), serv)
		defer delService(t, s, serv.Key)
		ttl += 60
	}
	c := new(dns.Client)
	tc := dnsTestCases[9]
	t.Logf("%v\n", tc)
	m := new(dns.Msg)
	m.SetQuestion(tc.Qname, tc.Qtype)
	if tc.dnssec == true {
		m.SetEdns0(4096, true)
	}
	resp, _, err := c.Exchange(m, "127.0.0.1:"+StrPort)
	if err != nil {
		t.Fatalf("failing: %s: %s\n", m.String(), err.Error())
	}
	t.Logf("%s\n", resp)
	ttl = 360
	for i, a := range resp.Answer {
		if a.Header().Ttl != ttl {
			t.Errorf("Answer %d should have a Header TTL of %d, but has %d", i, ttl, a.Header().Ttl)
		}
	}
}

// defaultExtResolver queries other nameserver, potentially recurses; callers should probably be invoking extResolver
// instead since that's the pluggable entrypoint into external resolution.
func (res *Resolver) defaultExtResolver(r *dns.Msg, nameserver, proto string, cnt int) (in *dns.Msg, err error) {
	defer logging.CurLog.NonMesosRecursed.Inc()

	timeout := extQueryTimeout
	if res.config.Timeout != 0 {
		timeout = time.Duration(res.config.Timeout) * time.Second
	}

	c := dns.Client{
		Net:          proto,
		DialTimeout:  timeout,
		ReadTimeout:  timeout,
		WriteTimeout: timeout,
	}

	for i := 0; i < cnt; i++ {
		in, _, err = c.Exchange(r, nameserver)
		if err != nil || len(in.Ns) == 0 || (in.Authoritative && len(in.Answer) > 0) {
			break
		} else if soa, ok := in.Ns[0].(*dns.SOA); ok {
			nameserver = soa.Ns
		}
	}

	return in, err
}