nsrep.c 4.57 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
/*  Copyright (C) 2014 CZ.NIC, z.s.p.o. <knot-dns@labs.nic.cz>

    This program is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

Marek Vavruša's avatar
Marek Vavruša committed
17
#include <assert.h>
18 19 20
#include <sys/socket.h>
#include <netinet/in.h>
#include <netdb.h>
21
#include <libknot/internal/sockaddr.h>
Marek Vavruša's avatar
Marek Vavruša committed
22

23
#include "lib/nsrep.h"
24
#include "lib/rplan.h"
Marek Vavruša's avatar
Marek Vavruša committed
25
#include "lib/defines.h"
26
#include "lib/generic/pack.h"
27

28 29 30
/** Some built-in unfairness ... */
#define FAVOUR_IPV6 20 /* 20ms bonus for v6 */

31 32 33 34 35 36 37 38 39 40 41 42 43
/** @internal Macro to set address structure. */
#define ADDR_SET(sa, family, addr, len) do {\
    	memcpy(&sa ## _addr, (addr), (len)); \
    	sa ## _family = (family); \
	sa ## _port = htons(KR_DNS_PORT); \
} while (0)

/** Update nameserver representation with current name/address pair. */
static void update_nsrep(struct kr_nsrep *ns, const knot_dname_t *name, uint8_t *addr, unsigned score)
{
	ns->name = name;
	ns->score = score;
	if (addr == NULL) {
44
		ns->addr.ip.sa_family = AF_UNSPEC;
45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
		return;
	}

	size_t len = pack_obj_len(addr);
	void *addr_val = pack_obj_val(addr);
	switch(len) {
	case sizeof(struct in_addr):
		ADDR_SET(ns->addr.ip4.sin, AF_INET, addr_val, len); break;
	case sizeof(struct in6_addr):
		ADDR_SET(ns->addr.ip6.sin6, AF_INET6, addr_val, len); break;
	default: assert(0); break;
	}
}

#undef ADDR_SET

61
static unsigned eval_addr_set(pack_t *addr_set, kr_nsrep_lru_t *rttcache, unsigned score, uint8_t **addr)
62 63
{
	/* Name server is better candidate if it has address record. */
64 65 66 67
	uint8_t *it = pack_head(*addr_set);
	while (it != pack_tail(*addr_set)) {
		void *val = pack_obj_val(it);
		size_t len = pack_obj_len(it);
68 69
		/* Get RTT for this address (if known) */
		unsigned *cached = rttcache ? lru_get(rttcache, val, len) : NULL;
70
		unsigned addr_score = (cached) ? *cached : KR_NS_UNKNOWN / 2;
71 72 73 74
		/* Give v6 a head start */
		unsigned favour = (len == sizeof(struct in6_addr)) ? FAVOUR_IPV6 : 0;
		if (addr_score < score + favour) {
			*addr = it;
75 76 77 78
			score = addr_score;
		}
		it = pack_obj_next(it);
	}
79 80 81 82 83 84 85 86 87 88 89 90 91
	return score;
}

static int eval_nsrep(const char *k, void *v, void *baton)
{
	struct kr_nsrep *ns = baton;
	unsigned score = KR_NS_MAX_SCORE;
	uint8_t *addr = NULL;

	/* Favour nameservers with unknown addresses to probe them,
	 * otherwise discover the current best address for the NS. */
	pack_t *addr_set = (pack_t *)v;
	if (addr_set->len == 0) {
92
		score = KR_NS_UNKNOWN;
93 94
	} else {
		score = eval_addr_set(addr_set, ns->repcache, score, &addr);
95 96
	}

97 98 99 100
	/* Probabilistic bee foraging strategy (naive).
	 * The fastest NS is preferred by workers until it is depleted (timeouts or degrades),
	 * at the same time long distance scouts probe other sources (low probability).
	 * Servers on TIMEOUT (depleted) can be probed by the dice roll only */
101
	if (score < ns->score && (ns->flags & QUERY_NO_THROTTLE || score < KR_NS_TIMEOUT)) {
102
		update_nsrep(ns, (const knot_dname_t *)k, addr, score);
103 104 105 106 107 108 109
	} else {
		/* With 5% chance, probe server with a probability given by its RTT / MAX_RTT */
		unsigned roll = rand() % KR_NS_MAX_SCORE;
		if ((roll % 100 < 5) && (roll >= score)) {
			update_nsrep(ns, (const knot_dname_t *)k, addr, score);
			return 1; /* Stop evaluation */
		}
110 111 112 113 114
	}

	return kr_ok();
}

115
int kr_nsrep_elect(struct kr_nsrep *ns, map_t *nsset, kr_nsrep_lru_t *repcache)
116
{
117
	ns->repcache = repcache;
118
	ns->addr.ip.sa_family = AF_UNSPEC;
119
	ns->score = KR_NS_MAX_SCORE + 1;
120
	return map_walk(nsset, eval_nsrep, ns);
121
}
122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138

int kr_nsrep_update(struct kr_nsrep *ns, unsigned score, kr_nsrep_lru_t *repcache)
{
	if (!ns || !repcache || ns->addr.ip.sa_family == AF_UNSPEC) {
		return kr_error(EINVAL);
	}

	char *addr = kr_nsrep_inaddr(ns->addr);
	size_t addr_len = kr_nsrep_inaddr_len(ns->addr);
	unsigned *cur = lru_set(repcache, addr, addr_len);
	if (!cur) {
		return kr_error(ENOMEM);
	}
	/* Score limits */
	if (score > KR_NS_MAX_SCORE) {
		score = KR_NS_MAX_SCORE;
	}
139 140 141
	if (score <= KR_NS_UNKNOWN) {
		score = KR_NS_UNKNOWN + 1;
	}
142 143 144 145 146 147 148 149 150
	/* Set initial value or smooth over last two measurements */
	if (*cur != 0) {
		*cur = (*cur + score) / 2;
	} else {
	/* First measurement, reset */
		*cur = score;
	}
	return kr_ok();
}