[Dnsmasq-discuss] [PATCH v2] Optimize ipset/server/local/address/rebind-domain-ok performance
Chen Wei
weichen302 at icloud.com
Wed Feb 25 07:28:15 GMT 2015
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
Hi list,
Current --ipset/server/local/address/rebind-domain-ok takes O(n) to
match a domain name. This patch attempts to achieve O(1).
Let's call the basic element of this patch htree_node:
struct htree_node {
char *label; /* key */
void *ptr;
uint32_t h1; /* from hash function 1 */
/*
* hash value from hash function 2, used for double hashing in open
* addressing hash table
*/
uint32_t h2;
struct htree_node **sub; /* the hash table */
unsigned sub_size; /* size of hash table */
int sub_count; /* items stored in hash table */
int sub_loadmax; /* max items stored before upsizing sub */
int sub_maxprobe; /* max probes for insertion, upsizing upon reach */
};
The htree_node mapes key(label) to value(ptr), serve as a container for
a generic pointer and a hash table. It supports at least two operations:
* add a new key,
struct htree_node *htree_add(struct htree_node *np, char *key)
The added key is returned as an allocated new node, which can then be
used to carry a pointer, or a hash table
* lookup a key
struct htree_node *htree_find(struct htree_node *np, char *key)
The lookup return a htree_node for extracting the ptr/hash table, or
for modifying the ptr/hash table.
In fact, htree_node->sub does not necessarily need to be a hash table,
other data structure, such as binary tree can also be used.
Test on a list of few thousands domain names, the size of an open
addressing hash table for N items is close to 2N, and all lookup take
less than 7 probes for that table size. Therefor the space efficiency
and performance is acceptable. An open addressing hash table can work
with table size of 2^n, which is a bonus. Although deletion is
difficult, but it is not an issue for this patch since only add and
lookup involved.
Combine with few helper functions, the htree_node is used to match
domain name by chaining hash tables together:
root
|
+---------------------+
com org
| |
+------------------+ +-------------+
yahoo google twitter debian freebsd
| | | |
www mail +---------+ www
cn jp uk us
|
ftp
hash table for [com, org, ...]
table for [yahoo, google, twitter, ...](com),
table for [debian, freebsd, ...](org)
...
table for [www, mail]
table for [cn, jp, uk, us, ...]
...
Cheers,
Chen Wei
- ---
Makefile | 4 +-
src/dnsmasq.c | 4 +-
src/dnsmasq.h | 48 +++-
src/forward.c | 793 ++++++++++++++++++++++++++++++---------------------------
src/htree.c | 486 +++++++++++++++++++++++++++++++++++
src/network.c | 8 +-
src/option.c | 427 ++++++++++++++++++++-----------
7 files changed, 1232 insertions(+), 538 deletions(-)
create mode 100644 src/htree.c
diff --git a/Makefile b/Makefile
index 2910320..0ccbbe4 100644
- --- a/Makefile
+++ b/Makefile
@@ -24,7 +24,7 @@ MANDIR = $(PREFIX)/share/man
LOCALEDIR = $(PREFIX)/share/locale
BUILDDIR = $(SRC)
DESTDIR =
- -CFLAGS = -Wall -W -O2
+CFLAGS = -Wall -W -O0 -g
LDFLAGS =
COPTS =
RPM_OPT_FLAGS =
@@ -73,7 +73,7 @@ objs = cache.o rfc1035.o util.o option.o forward.o network.o \
dnsmasq.o dhcp.o lease.o rfc2131.o netlink.o dbus.o bpf.o \
helper.o tftp.o log.o conntrack.o dhcp6.o rfc3315.o \
dhcp-common.o outpacket.o radv.o slaac.o auth.o ipset.o \
- - domain.o dnssec.o blockdata.o tables.o loop.o inotify.o
+ domain.o dnssec.o blockdata.o tables.o loop.o inotify.o htree.o
hdrs = dnsmasq.h config.h dhcp-protocol.h dhcp6-protocol.h \
dns-protocol.h radv-protocol.h ip6addr.h
diff --git a/src/dnsmasq.c b/src/dnsmasq.c
index e903a24..e62b6e4 100644
- --- a/src/dnsmasq.c
+++ b/src/dnsmasq.c
@@ -250,7 +250,7 @@ int main (int argc, char **argv)
#endif
#ifdef HAVE_IPSET
- - if (daemon->ipsets)
+ if (daemon->htree_ipsets)
ipset_init();
#endif
@@ -627,6 +627,8 @@ int main (int argc, char **argv)
}
#ifdef HAVE_LINUX_NETWORK
+ free(hdr);
+ free(data);
if (option_bool(OPT_DEBUG))
prctl(PR_SET_DUMPABLE, 1, 0, 0, 0);
#endif
diff --git a/src/dnsmasq.h b/src/dnsmasq.h
index 89e758b..8f64b08 100644
- --- a/src/dnsmasq.h
+++ b/src/dnsmasq.h
@@ -510,10 +510,31 @@ struct server {
struct server *next;
};
- -struct ipsets {
- - char **sets;
- - char *domain;
- - struct ipsets *next;
+struct htree_node {
+ char *label; /* key */
+ void *ptr;
+ uint32_t h1; /* from hash function 1 */
+ /*
+ * hash value from hash function 2, used for double hashing in open
+ * addressing hash table
+ */
+ uint32_t h2;
+ struct htree_node **sub; /* the hash table */
+ unsigned sub_size; /* size of hash table */
+ int sub_count; /* items stored in hash table */
+ int sub_loadmax; /* max items stored before upsizing sub */
+ int sub_maxprobe; /* max probes for insertion, upsizing upon reach */
+};
+
+struct special_domain {
+ struct server *server;
+ union mysockaddr addr;
+ int domain_flags;
+};
+
+struct ipsets_names {
+ char **sets; /* ipsets names end with NULL ptr */
+ int count;
};
struct irec {
@@ -944,7 +965,13 @@ extern struct daemon {
struct iname *if_names, *if_addrs, *if_except, *dhcp_except, *auth_peers, *tftp_interfaces;
struct bogus_addr *bogus_addr, *ignore_addr;
struct server *servers;
- - struct ipsets *ipsets;
+
+ struct htree_node *htree_ipsets; /* for --ipset domain names*/
+ /* setnames stored here to reduce redundancy */
+ struct htree_node *htree_ipset_names;
+ /* for --server/local/address/rebind-domain-ok domain names */
+ struct htree_node *htree_special_domains;
+
int log_fac; /* log facility */
char *log_file; /* optional log file */
int max_logs; /* queue limit */
@@ -1370,6 +1397,17 @@ void ipset_init(void);
int add_to_ipset(const char *setname, const struct all_addr *ipaddr, int flags, int remove);
#endif
+/* htree.c */
+#define MAXLABELS 128
+struct htree_node *htree_new_node(char *label, int len);
+struct htree_node *htree_find_or_add(struct htree_node *node, char *label);
+struct htree_node *domain_match(struct htree_node *root, char *domain);
+struct htree_node *domain_find_or_add(struct htree_node *root, char *domain);
+struct server *lookup_or_install_new_server(struct server *serv);
+void htree_free (struct htree_node *node);
+void print_server_special_domains(struct htree_node *node,
+ char *parents[], int current_level);
+
/* helper.c */
#if defined(HAVE_SCRIPT)
int create_helper(int event_fd, int err_fd, uid_t uid, gid_t gid, long max_fd);
diff --git a/src/forward.c b/src/forward.c
index 438e9fa..aebf660 100644
- --- a/src/forward.c
+++ b/src/forward.c
@@ -30,7 +30,10 @@ static int do_check_sign(struct frec *forward, int status, time_t now, char *nam
static int send_check_sign(struct frec *forward, time_t now, struct dns_header *header, size_t plen,
char *name, char *keyname);
#endif
- -
+static int tcp_conn_serv(struct server *serv, time_t now,
+ unsigned char *packet, size_t payload_size,
+ union mysockaddr *peer_addr, union mysockaddr *local_addr,
+ int *added_pheader, int *no_cache_dnssec, int *cache_secure);
/* Send a UDP packet with its source address set as "source"
unless nowild is true, when we just send it with the kernel default */
@@ -118,126 +121,115 @@ int send_from(int fd, int nowild, char *packet, size_t len,
return 1;
}
- -
- -static unsigned int search_servers(time_t now, struct all_addr **addrpp,
- - unsigned int qtype, char *qdomain, int *type, char **domain, int *norebind)
- -
+
+/* search domain pattern for --address, --local, --server, --rebind-domain-ok
+
+ if matches --address, the address is stored in addrpp
+
+ if matches --server, a pointer to one of servers in daemon->servers is
+ stored in fwdserv, unless --server=/example.org/#, in which case fwdserv
+ will be NULL, means use normal server
+
+ if matches --rebind-domain-ok, the passed in norebind will be set to 1
+
+ we find longest match, e.g. given pattern debian.org and cn.debian.org,
+ ftp.cn.debian.org will match cn.debian.org
+ */
+static unsigned int
+search_servers (time_t now, struct all_addr **addrpp,
+ unsigned int qtype, char *qdomain, int *type,
+ char **domain, int *norebind, struct server **fwdserv)
{
- - /* If the query ends in the domain in one of our servers, set
- - domain to point to that name. We find the largest match to allow both
- - domain.org and sub.domain.org to exist. */
- -
- - unsigned int namelen = strlen(qdomain);
- - unsigned int matchlen = 0;
- - struct server *serv;
+ unsigned int namelen = strlen (qdomain);
unsigned int flags = 0;
- -
- - for (serv = daemon->servers; serv; serv=serv->next)
- - /* domain matches take priority over NODOTS matches */
- - if ((serv->flags & SERV_FOR_NODOTS) && *type != SERV_HAS_DOMAIN && !strchr(qdomain, '.') && namelen != 0)
- - {
- - unsigned int sflag = serv->addr.sa.sa_family == AF_INET ? F_IPV4 : F_IPV6;
- - *type = SERV_FOR_NODOTS;
- - if (serv->flags & SERV_NO_ADDR)
- - flags = F_NXDOMAIN;
- - else if (serv->flags & SERV_LITERAL_ADDRESS)
- - {
- - if (sflag & qtype)
- - {
- - flags = sflag;
- - if (serv->addr.sa.sa_family == AF_INET)
- - *addrpp = (struct all_addr *)&serv->addr.in.sin_addr;
- -#ifdef HAVE_IPV6
- - else
- - *addrpp = (struct all_addr *)&serv->addr.in6.sin6_addr;
- -#endif
- - }
- - else if (!flags || (flags & F_NXDOMAIN))
- - flags = F_NOERR;
- - }
- - }
- - else if (serv->flags & SERV_HAS_DOMAIN)
- - {
- - unsigned int domainlen = strlen(serv->domain);
- - char *matchstart = qdomain + namelen - domainlen;
- - if (namelen >= domainlen &&
- - hostname_isequal(matchstart, serv->domain) &&
- - (domainlen == 0 || namelen == domainlen || *(matchstart-1) == '.' ))
- - {
- - if (serv->flags & SERV_NO_REBIND)
- - *norebind = 1;
- - else
- - {
- - unsigned int sflag = serv->addr.sa.sa_family == AF_INET ? F_IPV4 : F_IPV6;
- - /* implement priority rules for --address and --server for same domain.
- - --address wins if the address is for the correct AF
- - --server wins otherwise. */
- - if (domainlen != 0 && domainlen == matchlen)
- - {
- - if ((serv->flags & SERV_LITERAL_ADDRESS))
- - {
- - if (!(sflag & qtype) && flags == 0)
- - continue;
- - }
- - else
- - {
- - if (flags & (F_IPV4 | F_IPV6))
- - continue;
- - }
- - }
- -
- - if (domainlen >= matchlen)
- - {
- - *type = serv->flags & (SERV_HAS_DOMAIN | SERV_USE_RESOLV | SERV_NO_REBIND);
- - *domain = serv->domain;
- - matchlen = domainlen;
- - if (serv->flags & SERV_NO_ADDR)
- - flags = F_NXDOMAIN;
- - else if (serv->flags & SERV_LITERAL_ADDRESS)
- - {
- - if (sflag & qtype)
- - {
- - flags = sflag;
- - if (serv->addr.sa.sa_family == AF_INET)
- - *addrpp = (struct all_addr *)&serv->addr.in.sin_addr;
+ unsigned int sflag;
+ struct htree_node *np;
+ struct special_domain *obj;
+
+ *type = 0;
+ /* label of root node is "#", means --address=/#/1.2.3.4 */
+ if (daemon->htree_special_domains && daemon->htree_special_domains->label &&
+ *daemon->htree_special_domains->label == '#')
+ np = daemon->htree_special_domains;
+ else
+ np = domain_match (daemon->htree_special_domains, qdomain);
+
+ if (np != NULL)
+ {
+ obj = (struct special_domain *) np->ptr;
+
+ *type |= SERV_HAS_DOMAIN;
+
+ if (obj->domain_flags & SERV_NO_REBIND)
+ *norebind = 1;
+
+ /* no server, domain is local only */
+ if (obj->domain_flags & SERV_NO_ADDR)
+ {
+ flags = F_NXDOMAIN;
+
+ }
+ else if (obj->domain_flags & SERV_LITERAL_ADDRESS)
+ {
+ /* --address and AF matches */
+ sflag = obj->addr.sa.sa_family == AF_INET ? F_IPV4 : F_IPV6;
+ if (sflag & qtype)
+ {
+ flags = sflag;
+ if (obj->addr.sa.sa_family == AF_INET)
+ *addrpp = (struct all_addr *) &obj->addr.in.sin_addr;
#ifdef HAVE_IPV6
- - else
- - *addrpp = (struct all_addr *)&serv->addr.in6.sin6_addr;
+ else
+ *addrpp = (struct all_addr *) &obj->addr.in6.sin6_addr;
#endif
- - }
- - else if (!flags || (flags & F_NXDOMAIN))
- - flags = F_NOERR;
- - }
- - else
- - flags = 0;
- - }
- - }
- - }
- - }
- -
- - if (flags == 0 && !(qtype & F_QUERY) &&
- - option_bool(OPT_NODOTS_LOCAL) && !strchr(qdomain, '.') && namelen != 0)
+ }
+
+ }
+ else if (obj->domain_flags & SERV_USE_RESOLV)
+ {
+ /* --server=8.8.8.8 */
+ *type = 0; /* use normal server */
+ *fwdserv = NULL;
+
+ }
+ else
+ {
+ *fwdserv = obj->server;
+ flags = 0;
+ }
+ }
+ else
+ {
+ *type = 0; /* use normal servers for this domain */
+ *fwdserv = NULL;
+ }
+
+ if (flags == 0 && !(qtype & F_QUERY) &&
+ option_bool (OPT_NODOTS_LOCAL) && !strchr (qdomain, '.')
+ && namelen != 0)
/* don't forward A or AAAA queries for simple names, except the empty name */
flags = F_NOERR;
- -
- - if (flags == F_NXDOMAIN && check_for_local_domain(qdomain, now))
+
+ if (flags == F_NXDOMAIN && check_for_local_domain (qdomain, now))
flags = F_NOERR;
if (flags)
{
int logflags = 0;
- -
+
if (flags == F_NXDOMAIN || flags == F_NOERR)
- - logflags = F_NEG | qtype;
- -
- - log_query(logflags | flags | F_CONFIG | F_FORWARD, qdomain, *addrpp, NULL);
+ logflags = F_NEG | qtype;
+
+ log_query (logflags | flags | F_CONFIG | F_FORWARD, qdomain, *addrpp,
+ NULL);
}
else if ((*type) & SERV_USE_RESOLV)
{
- - *type = 0; /* use normal servers for this domain */
+ *type = 0; /* use normal servers for this domain */
*domain = NULL;
}
- - return flags;
+
+ return flags;
}
static int forward_query(int udpfd, union mysockaddr *udpaddr,
@@ -250,6 +242,7 @@ static int forward_query(int udpfd, union mysockaddr *udpaddr,
struct all_addr *addrp = NULL;
unsigned int flags = 0;
struct server *start = NULL;
+ struct server *fwdserv = NULL;
#ifdef HAVE_DNSSEC
void *hash = hash_questions(header, plen, daemon->namebuff);
#else
@@ -321,7 +314,7 @@ static int forward_query(int udpfd, union mysockaddr *udpaddr,
else
{
if (gotname)
- - flags = search_servers(now, &addrp, gotname, daemon->namebuff, &type, &domain, &norebind);
+ flags = search_servers(now, &addrp, gotname, daemon->namebuff, &type, &domain, &norebind, &fwdserv);
if (!flags && !(forward = get_new_frec(now, NULL, 0)))
/* table full - server failure. */
@@ -386,7 +379,6 @@ static int forward_query(int udpfd, union mysockaddr *udpaddr,
if (!flags && forward)
{
- - struct server *firstsentto = start;
int forwarded = 0;
/* If a query is retried, use the log_id for the retry when logging the answer. */
@@ -422,95 +414,90 @@ static int forward_query(int udpfd, union mysockaddr *udpaddr,
}
#endif
- - while (1)
- - {
- - /* only send to servers dealing with our domain.
- - domain may be NULL, in which case server->domain
- - must be NULL also. */
- -
- - if (type == (start->flags & SERV_TYPE) &&
- - (type != SERV_HAS_DOMAIN || hostname_isequal(domain, start->domain)) &&
- - !(start->flags & (SERV_LITERAL_ADDRESS | SERV_LOOP)))
- - {
- - int fd;
+ /* we have the server for our domain by lookup
+ * daemon->htree_special_domains */
+ int fd;
- - /* find server socket to use, may need to get random one. */
- - if (start->sfd)
- - fd = start->sfd->fd;
- - else
- - {
+ /* didn't find a server matches query domain */
+ if (fwdserv == NULL)
+ {
+ for (fwdserv = daemon->servers;
+ fwdserv != NULL; fwdserv = fwdserv->next)
+ {
+ //TODO figure out how to skip unresponsive server
+ if (!(fwdserv->flags & (SERV_HAS_DOMAIN | SERV_LOOP)))
+ {
+ break;
+ }
+ }
+ }
+
+ if (fwdserv->sfd)
+ fd = fwdserv->sfd->fd;
+ else
+ {
#ifdef HAVE_IPV6
- - if (start->addr.sa.sa_family == AF_INET6)
- - {
- - if (!forward->rfd6 &&
- - !(forward->rfd6 = allocate_rfd(AF_INET6)))
- - break;
- - daemon->rfd_save = forward->rfd6;
- - fd = forward->rfd6->fd;
- - }
- - else
+ if (fwdserv->addr.sa.sa_family == AF_INET6)
+ {
+ if (forward->rfd6 == NULL)
+ forward->rfd6 = allocate_rfd (AF_INET6);
+ daemon->rfd_save = forward->rfd6;
+ fd = forward->rfd6->fd;
+ }
+ else
#endif
- - {
- - if (!forward->rfd4 &&
- - !(forward->rfd4 = allocate_rfd(AF_INET)))
- - break;
- - daemon->rfd_save = forward->rfd4;
- - fd = forward->rfd4->fd;
- - }
+ {
+ if (forward->rfd4 == NULL)
+ forward->rfd4 = allocate_rfd (AF_INET);
+ daemon->rfd_save = forward->rfd4;
+ fd = forward->rfd4->fd;
+ }
#ifdef HAVE_CONNTRACK
- - /* Copy connection mark of incoming query to outgoing connection. */
- - if (option_bool(OPT_CONNTRACK))
- - {
- - unsigned int mark;
- - if (get_incoming_mark(&forward->source, &forward->dest, 0, &mark))
- - setsockopt(fd, SOL_SOCKET, SO_MARK, &mark, sizeof(unsigned int));
- - }
+ /* Copy connection mark of incoming query to outgoing connection. */
+ if (option_bool (OPT_CONNTRACK))
+ {
+ unsigned int mark;
+ if (get_incoming_mark (&forward->source, &forward->dest, 0, &mark))
+ setsockopt (fd, SOL_SOCKET, SO_MARK, &mark,
+ sizeof (unsigned int));
+ }
#endif
- - }
- -
- - if (sendto(fd, (char *)header, plen, 0,
- - &start->addr.sa,
- - sa_len(&start->addr)) == -1)
- - {
- - if (retry_send())
- - continue;
- - }
- - else
- - {
- - /* Keep info in case we want to re-send this packet */
- - daemon->srv_save = start;
- - daemon->packet_len = plen;
- -
- - if (!gotname)
- - strcpy(daemon->namebuff, "query");
- - if (start->addr.sa.sa_family == AF_INET)
- - log_query(F_SERVER | F_IPV4 | F_FORWARD, daemon->namebuff,
- - (struct all_addr *)&start->addr.in.sin_addr, NULL);
+ }
+
+ //TODO are we retry correctly here?
+ if (sendto (fd, (char *) header, plen, 0,
+ &fwdserv->addr.sa, sa_len (&fwdserv->addr)) == -1)
+ {
+ retry_send ();
+ }
+
+ else
+ {
+ /* Keep info in case we want to re-send this packet */
+ daemon->srv_save = fwdserv;
+ daemon->packet_len = plen;
+
+ if (!gotname)
+ strcpy (daemon->namebuff, "query");
+ if (fwdserv->addr.sa.sa_family == AF_INET)
+ log_query (F_SERVER | F_IPV4 | F_FORWARD, daemon->namebuff,
+ (struct all_addr *) &fwdserv->addr.in.sin_addr, NULL);
#ifdef HAVE_IPV6
- - else
- - log_query(F_SERVER | F_IPV6 | F_FORWARD, daemon->namebuff,
- - (struct all_addr *)&start->addr.in6.sin6_addr, NULL);
- -#endif
- - start->queries++;
- - forwarded = 1;
- - forward->sentto = start;
- - if (!forward->forwardall)
- - break;
- - forward->forwardall++;
- - }
- - }
- -
- - if (!(start = start->next))
- - start = daemon->servers;
- -
- - if (start == firstsentto)
- - break;
- - }
- -
+ else
+ log_query (F_SERVER | F_IPV6 | F_FORWARD, daemon->namebuff,
+ (struct all_addr *) &fwdserv->addr.in6.sin6_addr, NULL);
+#endif
+ fwdserv->queries++;
+ forwarded = 1;
+ forward->sentto = fwdserv;
+ if (forward->forwardall)
+ forward->forwardall++;
+ }
+
if (forwarded)
- - return 1;
- -
+ return 1;
+
/* could not send on, prepare to return */
header->id = htons(forward->orig_id);
free_frec(forward); /* cancel */
@@ -533,29 +520,21 @@ static size_t process_reply(struct dns_header *header, time_t now, struct server
char **sets = 0;
int munged = 0, is_sign;
size_t plen;
+ struct htree_node *np;
+ struct ipsets_names *obj;
(void)ad_reqd;
(void) do_bit;
#ifdef HAVE_IPSET
- - if (daemon->ipsets && extract_request(header, n, daemon->namebuff, NULL))
+ if (daemon->htree_ipsets && extract_request(header, n, daemon->namebuff, NULL))
{
- - /* Similar algorithm to search_servers. */
- - struct ipsets *ipset_pos;
- - unsigned int namelen = strlen(daemon->namebuff);
- - unsigned int matchlen = 0;
- - for (ipset_pos = daemon->ipsets; ipset_pos; ipset_pos = ipset_pos->next)
- - {
- - unsigned int domainlen = strlen(ipset_pos->domain);
- - char *matchstart = daemon->namebuff + namelen - domainlen;
- - if (namelen >= domainlen && hostname_isequal(matchstart, ipset_pos->domain) &&
- - (domainlen == 0 || namelen == domainlen || *(matchstart - 1) == '.' ) &&
- - domainlen >= matchlen)
- - {
- - matchlen = domainlen;
- - sets = ipset_pos->sets;
- - }
- - }
+ np = domain_match(daemon->htree_ipsets, daemon->namebuff);
+ if (np != NULL)
+ {
+ obj = (struct ipsets_names *) np->ptr;
+ sets = obj->sets;
+ }
}
#endif
@@ -714,6 +693,7 @@ void reply_query(int fd, int family, time_t now)
if (!(server->flags & (SERV_LITERAL_ADDRESS | SERV_NO_ADDR)) &&
sockaddr_isequal(&server->addr, &serveraddr))
break;
+ /* TODO server may also come from the list for special domains */
if (!server)
return;
@@ -1659,6 +1639,169 @@ static int tcp_key_recurse(time_t now, int status, struct dns_header *header, si
}
#endif
+/* try establish tcp connection to upstream server and forward query
+ *
+ * return -1 on tcp connect/read/write error
+ * 0 on upstream response has 0 length DNS message, or DNSSEC error
+ * > 0 DNS message length received from upstream server */
+static int tcp_conn_serv(struct server *serv, time_t now,
+ unsigned char *packet, size_t payload_size,
+ union mysockaddr *peer_addr, union mysockaddr *local_addr,
+ int *added_pheader, int *no_cache_dnssec, int *cache_secure)
+{
+ unsigned char *payload = packet + 2; /* skip msg length field */
+ struct dns_header *header = (struct dns_header *) payload;
+ unsigned int gotname;
+ unsigned short qtype;
+ int checking_disabled = header->hb4 & HB4_CD;
+ unsigned int m = 0;
+ u16 msg_len;
+
+#ifdef HAVE_DNSSEC
+ unsigned char *newhash, hash[HASH_SIZE];
+ if ((newhash = hash_questions (header, (unsigned int) payload_size,
+ daemon->namebuff)))
+ memcpy (hash, newhash, HASH_SIZE);
+ else
+ memset (hash, 0, HASH_SIZE);
+#else
+ unsigned int crc =
+ questions_crc (header, (unsigned int) payload_size, daemon->namebuff);
+#endif
+
+ if (serv->tcpfd == -1)
+ {
+ if ((serv->tcpfd =
+ socket (serv->addr.sa.sa_family, SOCK_STREAM, 0)) == -1)
+ return -1;
+
+#ifdef HAVE_CONNTRACK
+ /* Copy connection mark of incoming query to outgoing connection. */
+ if (option_bool (OPT_CONNTRACK))
+ {
+ unsigned int mark;
+ struct all_addr local;
+#ifdef HAVE_IPV6
+ if (local_addr->sa.sa_family == AF_INET6)
+ local.addr.addr6 = local_addr->in6.sin6_addr;
+ else
+#endif
+ local.addr.addr4 = local_addr->in.sin_addr;
+
+ if (get_incoming_mark (peer_addr, &local, 1, &mark))
+ setsockopt (serv->tcpfd, SOL_SOCKET, SO_MARK, &mark,
+ sizeof (unsigned int));
+ }
+#endif
+
+ if (!local_bind (serv->tcpfd, &serv->source_addr, serv->interface, 1) ||
+ connect (serv->tcpfd, &serv->addr.sa, sa_len (&serv->addr)) == -1)
+ {
+ close (serv->tcpfd);
+ serv->tcpfd = -1;
+ return -1;
+ }
+
+#ifdef HAVE_DNSSEC
+ if (option_bool (OPT_DNSSEC_VALID))
+ {
+ size_t new_size =
+ add_do_bit (header, payload_size, ((char *) header) + 65536);
+
+ /* For debugging, set Checking Disabled, otherwise, have the upstream
+ check too, this allows it to select auth servers when one is
+ returning bad data. */
+ if (option_bool (OPT_DNSSEC_DEBUG))
+ header->hb4 |= HB4_CD;
+
+ if (payload_size != new_size)
+ *added_pheader = 1;
+
+ payload_size = new_size;
+ }
+#endif
+
+ }
+
+ /* get query name again for logging - may have been overwritten */
+ if (!(gotname = extract_request (header, (unsigned int) payload_size,
+ daemon->namebuff, &qtype)))
+ strcpy (daemon->namebuff, "query");
+
+ u16 n_size = htons (payload_size);
+ memcpy (packet, &n_size, sizeof (u16));
+
+ if (!read_write (serv->tcpfd, packet, payload_size + sizeof (u16), 0) ||
+ !read_write (serv->tcpfd, (unsigned char *) &msg_len, 2, 1) ||
+ !(m = (unsigned int) ntohs (msg_len)) ||
+ !read_write (serv->tcpfd, payload, (int) m, 1))
+ {
+ close (serv->tcpfd);
+ serv->tcpfd = -1;
+ return -1;
+ }
+
+ if (serv->addr.sa.sa_family == AF_INET)
+ log_query (F_SERVER | F_IPV4 | F_FORWARD, daemon->namebuff,
+ (struct all_addr *) &serv->addr.in.sin_addr, NULL);
+#ifdef HAVE_IPV6
+ else
+ log_query (F_SERVER | F_IPV6 | F_FORWARD, daemon->namebuff,
+ (struct all_addr *) &serv->addr.in6.sin6_addr, NULL);
+#endif
+
+#ifdef HAVE_DNSSEC
+ if (option_bool (OPT_DNSSEC_VALID) && !checking_disabled)
+ {
+ /* Limit to number of DNSSEC questions, to catch loops and avoid filling
+ * cache. */
+ int keycount = DNSSEC_WORK;
+ int status =
+ tcp_key_recurse (now, STAT_TRUNCATED, header, m, 0, daemon->namebuff,
+ daemon->keyname, serv, &keycount);
+ char *result;
+
+ if (keycount == 0)
+ result = "ABANDONED";
+ else
+ result =
+ (status ==
+ STAT_SECURE ? "SECURE" : (status ==
+ STAT_INSECURE ? "INSECURE" : "BOGUS"));
+
+ log_query (F_KEYTAG | F_SECSTAT, "result", NULL, result);
+
+ if (status == STAT_BOGUS)
+ *no_cache_dnssec = 1;
+
+ if (status == STAT_SECURE)
+ *cache_secure = 1;
+ }
+#endif
+
+ /* restore CD bit to the value in the query */
+ if (checking_disabled)
+ header->hb4 |= HB4_CD;
+ else
+ header->hb4 &= ~HB4_CD;
+
+ /* There's no point in updating the cache, since this process will exit and
+ lose the information after a few queries. We make this call for the alias and
+ bogus-nxdomain side-effects. */
+ /* If the crc of the question section doesn't match the crc we sent, then
+ someone might be attempting to insert bogus values into the cache by
+ sending replies containing questions and bogus answers. */
+#ifdef HAVE_DNSSEC
+ newhash = hash_questions (header, m, daemon->namebuff);
+ if (!newhash || memcmp (hash, newhash, HASH_SIZE) != 0)
+ m = 0;
+#else
+ if (crc != questions_crc (header, m, daemon->namebuff))
+ m = 0;
+#endif
+
+ return (int) m;
+}
/* The daemon forks before calling this: it should deal with one connection,
blocking as neccessary, and then return. Note, need to be a bit careful
@@ -1672,8 +1815,8 @@ unsigned char *tcp_request(int confd, time_t now,
#ifdef HAVE_AUTH
int local_auth = 0;
#endif
- - int checking_disabled, ad_question, do_bit, added_pheader = 0;
- - int check_subnet, no_cache_dnssec = 0, cache_secure = 0;
+ int checking_disabled, ad_question, do_bit, check_subnet;
+ int added_pheader = 0, no_cache_dnssec = 0, cache_secure = 0;
size_t m;
unsigned short qtype;
unsigned int gotname;
@@ -1684,11 +1827,12 @@ unsigned char *tcp_request(int confd, time_t now,
/* largest field in header is 16-bits, so this is still sufficiently aligned */
struct dns_header *header = (struct dns_header *)payload;
u16 *length = (u16 *)packet;
- - struct server *last_server;
+ struct server *last_server, *fwdserv, *serv;
struct in_addr dst_addr_4;
union mysockaddr peer_addr;
socklen_t peer_len = sizeof(union mysockaddr);
int query_count = 0;
+ int ret;
if (getpeername(confd, (struct sockaddr *)&peer_addr, &peer_len) == -1)
return packet;
@@ -1816,183 +1960,72 @@ unsigned char *tcp_request(int confd, time_t now,
}
}
+ //TODO use fwdserv
if (gotname)
- - flags = search_servers(now, &addrp, gotname, daemon->namebuff, &type, &domain, &norebind);
- -
- - if (type != 0 || option_bool(OPT_ORDER) || !daemon->last_server)
- - last_server = daemon->servers;
- - else
- - last_server = daemon->last_server;
+ flags = search_servers(now, &addrp, gotname, daemon->namebuff, &type, &domain, &norebind, &fwdserv);
- - if (!flags && last_server)
- - {
- - struct server *firstsendto = NULL;
- -#ifdef HAVE_DNSSEC
- - unsigned char *newhash, hash[HASH_SIZE];
- - if ((newhash = hash_questions(header, (unsigned int)size, daemon->namebuff)))
- - memcpy(hash, newhash, HASH_SIZE);
- - else
- - memset(hash, 0, HASH_SIZE);
- -#else
- - unsigned int crc = questions_crc(header, (unsigned int)size, daemon->namebuff);
- -#endif
- - /* Loop round available servers until we succeed in connecting to one.
- - Note that this code subtley ensures that consecutive queries on this connection
- - which can go to the same server, do so. */
- - while (1)
- - {
- - if (!firstsendto)
- - firstsendto = last_server;
- - else
- - {
- - if (!(last_server = last_server->next))
- - last_server = daemon->servers;
- -
- - if (last_server == firstsendto)
- - break;
- - }
- -
- - /* server for wrong domain */
- - if (type != (last_server->flags & SERV_TYPE) ||
- - (type == SERV_HAS_DOMAIN && !hostname_isequal(domain, last_server->domain)) ||
- - (last_server->flags & (SERV_LITERAL_ADDRESS | SERV_LOOP)))
- - continue;
- -
- - if (last_server->tcpfd == -1)
- - {
- - if ((last_server->tcpfd = socket(last_server->addr.sa.sa_family, SOCK_STREAM, 0)) == -1)
- - continue;
- -
- -#ifdef HAVE_CONNTRACK
- - /* Copy connection mark of incoming query to outgoing connection. */
- - if (option_bool(OPT_CONNTRACK))
- - {
- - unsigned int mark;
- - struct all_addr local;
- -#ifdef HAVE_IPV6
- - if (local_addr->sa.sa_family == AF_INET6)
- - local.addr.addr6 = local_addr->in6.sin6_addr;
- - else
- -#endif
- - local.addr.addr4 = local_addr->in.sin_addr;
- -
- - if (get_incoming_mark(&peer_addr, &local, 1, &mark))
- - setsockopt(last_server->tcpfd, SOL_SOCKET, SO_MARK, &mark, sizeof(unsigned int));
- - }
- -#endif
- -
- - if ((!local_bind(last_server->tcpfd, &last_server->source_addr, last_server->interface, 1) ||
- - connect(last_server->tcpfd, &last_server->addr.sa, sa_len(&last_server->addr)) == -1))
- - {
- - close(last_server->tcpfd);
- - last_server->tcpfd = -1;
- - continue;
- - }
- -
- -#ifdef HAVE_DNSSEC
- - if (option_bool(OPT_DNSSEC_VALID))
- - {
- - size_t new_size = add_do_bit(header, size, ((char *) header) + 65536);
- -
- - /* For debugging, set Checking Disabled, otherwise, have the upstream check too,
- - this allows it to select auth servers when one is returning bad data. */
- - if (option_bool(OPT_DNSSEC_DEBUG))
- - header->hb4 |= HB4_CD;
- -
- - if (size != new_size)
- - added_pheader = 1;
- -
- - size = new_size;
- - }
- -#endif
- - }
- -
- - *length = htons(size);
- -
- - /* get query name again for logging - may have been overwritten */
- - if (!(gotname = extract_request(header, (unsigned int)size, daemon->namebuff, &qtype)))
- - strcpy(daemon->namebuff, "query");
- -
- - if (!read_write(last_server->tcpfd, packet, size + sizeof(u16), 0) ||
- - !read_write(last_server->tcpfd, &c1, 1, 1) ||
- - !read_write(last_server->tcpfd, &c2, 1, 1) ||
- - !read_write(last_server->tcpfd, payload, (c1 << 8) | c2, 1))
- - {
- - close(last_server->tcpfd);
- - last_server->tcpfd = -1;
- - continue;
- - }
- -
- - m = (c1 << 8) | c2;
- -
- - if (last_server->addr.sa.sa_family == AF_INET)
- - log_query(F_SERVER | F_IPV4 | F_FORWARD, daemon->namebuff,
- - (struct all_addr *)&last_server->addr.in.sin_addr, NULL);
- -#ifdef HAVE_IPV6
- - else
- - log_query(F_SERVER | F_IPV6 | F_FORWARD, daemon->namebuff,
- - (struct all_addr *)&last_server->addr.in6.sin6_addr, NULL);
- -#endif
- -
- -#ifdef HAVE_DNSSEC
- - if (option_bool(OPT_DNSSEC_VALID) && !checking_disabled)
- - {
- - int keycount = DNSSEC_WORK; /* Limit to number of DNSSEC questions, to catch loops and avoid filling cache. */
- - int status = tcp_key_recurse(now, STAT_TRUNCATED, header, m, 0, daemon->namebuff, daemon->keyname, last_server, &keycount);
- - char *result;
+ ret = 0;
+ serv = last_server = NULL;
+ /* --address=/xxx/1.2.3.4 */
+ if (addrp != NULL)
+ {
+ m = 0;
+ }
+ else if (fwdserv != NULL)
+ {
+ /* --server=/example.org/1.2.3.4 */
+ serv = fwdserv;
+ ret = tcp_conn_serv (serv, now, packet, size,
+ &peer_addr, local_addr,
+ &added_pheader, &no_cache_dnssec, &cache_secure);
+ }
+ else
+ {
+ /* use normal server */
+ struct server *firstsendto = NULL;
+ if (option_bool (OPT_ORDER) || !daemon->last_server)
+ last_server = daemon->servers;
+ else
+ last_server = daemon->last_server;
+
+ while (1)
+ {
+ if (!firstsendto)
+ firstsendto = last_server;
+ else
+ {
+ if (!(last_server = last_server->next))
+ last_server = daemon->servers;
+
+ if (last_server == firstsendto)
+ break;
+ }
+
+ if (type != (last_server->flags & SERV_TYPE) ||
+ last_server->flags & SERV_HAS_DOMAIN ||
+ last_server->flags & SERV_LOOP)
+ continue;
+
+ serv = last_server;
+ ret = tcp_conn_serv (serv, now, packet, size,
+ &peer_addr, local_addr,
+ &added_pheader, &no_cache_dnssec, &cache_secure);
+ /* something wrong with tcp connect/read/write */
+ if (ret <= 0)
+ continue;
+
+ break;
+ }
+ }
+
+ if (ret > 0)
+ m = process_reply (header, now, serv, ret,
+ option_bool (OPT_NO_REBIND) && !norebind,
+ no_cache_dnssec, cache_secure, ad_question,
+ do_bit, added_pheader, check_subnet, &peer_addr);
- - if (keycount == 0)
- - result = "ABANDONED";
- - else
- - result = (status == STAT_SECURE ? "SECURE" : (status == STAT_INSECURE ? "INSECURE" : "BOGUS"));
- -
- - log_query(F_KEYTAG | F_SECSTAT, "result", NULL, result);
- -
- - if (status == STAT_BOGUS)
- - no_cache_dnssec = 1;
- -
- - if (status == STAT_SECURE)
- - cache_secure = 1;
- - }
- -#endif
- -
- - /* restore CD bit to the value in the query */
- - if (checking_disabled)
- - header->hb4 |= HB4_CD;
- - else
- - header->hb4 &= ~HB4_CD;
- -
- - /* There's no point in updating the cache, since this process will exit and
- - lose the information after a few queries. We make this call for the alias and
- - bogus-nxdomain side-effects. */
- - /* If the crc of the question section doesn't match the crc we sent, then
- - someone might be attempting to insert bogus values into the cache by
- - sending replies containing questions and bogus answers. */
- -#ifdef HAVE_DNSSEC
- - newhash = hash_questions(header, (unsigned int)m, daemon->namebuff);
- - if (!newhash || memcmp(hash, newhash, HASH_SIZE) != 0)
- - {
- - m = 0;
- - break;
- - }
- -#else
- - if (crc != questions_crc(header, (unsigned int)m, daemon->namebuff))
- - {
- - m = 0;
- - break;
- - }
- -#endif
- -
- - m = process_reply(header, now, last_server, (unsigned int)m,
- - option_bool(OPT_NO_REBIND) && !norebind, no_cache_dnssec,
- - cache_secure, ad_question, do_bit, added_pheader, check_subnet, &peer_addr);
- -
- - break;
- - }
- - }
- -
/* In case of local answer or no connections made. */
- - if (m == 0)
+ if (m == 0)
m = setup_reply(header, (unsigned int)size, addrp, flags, daemon->local_ttl);
}
}
diff --git a/src/htree.c b/src/htree.c
new file mode 100644
index 0000000..55e0f90
- --- /dev/null
+++ b/src/htree.c
@@ -0,0 +1,486 @@
+/* htree.c Chen Wei <weichen302 at gmail.com>
+
+ Use cascade of open addressing hash tables to store config options that
+ involve domain names.
+
+ root
+ |
+ +---------------------+
+ com org
+ | |
+ +------------------+ +-------------+
+ yahoo google twitter debian freebsd
+ | | | |
+ www mail +---------+ www
+ cn jp uk us
+ |
+ ftp
+
+ The lookup steps over domain name hierarchy top-down. All labels are stored
+ in open addressing hash tables. Sub-level labels that belong to different
+ parent nodes are stored separately. e.g. yahoo, google, and twitter are in
+ one hash table, while debian and freebsd are in another.
+
+ The hash table size is power of 2, two hash functions are used to compute
+ hash bucket. For locating a particular label from hash table, two hash
+ values are compared first, only if they are match, should the more
+ expensive string comparison be used to confirm the search.
+
+
+ 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; version 2 dated June, 1991, or
+ (at your option) version 3 dated 29 June, 2007.
+
+ 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/>.
+*/
+
+#include "dnsmasq.h"
+
+#define OPEN_ADDRESSING_MAXPROBE 7
+#define OPEN_ADDRESSING_DEFAULT_SIZE 4
+#define FNV1_32A_INIT ((uint32_t)0x811c9dc5)
+#define max(A, B) ((A) > (B) ? (A) : (B))
+
+static char buf[MAXDNAME];
+
+/* prototypes */
+static struct htree_node *htree_find (struct htree_node *node, char *label);
+static void htree_add (struct htree_node *node, struct htree_node *sub);
+static void htree_upsizing (struct htree_node *np);
+static inline void normalize_domain_name (char *dst, char *src, int len);
+
+/* hash function 1 for double hashing
+ * 32 bit Fowler/Noll/Vo hash */
+static inline uint32_t dblhash_1 (char *key)
+{
+ uint32_t hval = FNV1_32A_INIT;
+ unsigned char *s = (unsigned char *) key;
+
+ while (*s)
+ {
+ hval ^= (uint32_t) * s++;
+ hval +=
+ (hval << 1) + (hval << 4) + (hval << 7) + (hval << 8) + (hval << 24);
+ }
+
+ return hval;
+}
+
+/* hash function 2 for double hashing
+ * modified Shift-Add-XOR hash, return an odd number */
+static inline uint32_t dblhash_2 (char *key)
+{
+ uint32_t h = 0;
+ unsigned char *s = (unsigned char *) key;
+
+ while (*s)
+ h ^= (h << 5) + (h >> 2) + *s++;
+
+ return h % 2 ? h : h + 1;
+}
+
+/* convert domain to lower cases, remove leading blank, leading and trailing
+ * dot. End string with \0 */
+static inline void normalize_domain_name (char *d, char *s, int len)
+{
+ int i;
+
+ /* skip leading dot and blank */
+ for ( ; *s != '\0' && (*s == '.' || *s == '\t' || *s == ' '); s++)
+ ;
+
+ for (i = 0; i < len && *s != '\0'; i++, s++)
+ {
+ if (*s >= 'A' && *s <= 'Z')
+ d[i] = *s + 'a' - 'A';
+ else
+ d[i] = *s;
+ }
+
+ /* should not happen since the source string limited to MAXDNAME */
+ if (i == len)
+ i--;
+
+ for ( ; d[i] == '.'; i--)
+ ;
+
+ if (i < (len - 1))
+ d[++i] = '\0';
+ else
+ /* something wrong with the source string(domain name), it exceeds
+ * MAXDNAME, terminate the dst string with '\0' anyway */
+ d[i] = '\0';
+}
+
+struct htree_node * htree_init_sub (struct htree_node *node)
+{
+ unsigned n;
+
+ if (node->sub != NULL)
+ return node;
+
+ node->sub_size = OPEN_ADDRESSING_DEFAULT_SIZE;
+ node->sub_loadmax = node->sub_size * 3 / 4; /* max loading factor 0.75 */
+ node->sub = safe_malloc (node->sub_size * sizeof (struct htree_node *));
+ for (n = 0; n < node->sub_size; n++)
+ node->sub[n] = NULL;
+
+ return node;
+}
+
+/* allocate and initialize a new node */
+struct htree_node * htree_new_node (char *label, int label_len)
+{
+ struct htree_node *node;
+
+ node = safe_malloc (sizeof (struct htree_node));
+ if (node == NULL)
+ return NULL;
+
+ if (label == NULL || label_len == 0)
+ {
+ node->h1 = 0;
+ node->h2 = 0;
+ node->label = NULL;
+ }
+ else
+ {
+ node->label = strdup (label);
+ node->h1 = dblhash_1 (label);
+ node->h2 = dblhash_2 (label);
+ }
+
+ node->sub_count = 0;
+ node->sub_size = 0;
+ node->sub_loadmax = 0;
+ node->sub_maxprobe = 0;
+ node->sub = NULL;
+ node->ptr = NULL;
+
+ return node;
+}
+
+/* double the size of hash table attached to a htree_node, it calls with
+ * htree_add with each other. The table size starts with 2^2, so that the new
+ * size remains 2^x, the double hash used is chosen to work with 2^n slots */
+static void htree_upsizing (struct htree_node *np)
+{
+ struct htree_node **oldnodes;
+ unsigned i, oldsize;
+
+ oldsize = np->sub_size;
+ oldnodes = np->sub;
+ np->sub_size = oldsize * 2;
+ np->sub_loadmax = np->sub_size * 3 / 4;
+ np->sub_count = 0;
+ np->sub_maxprobe = 0;
+ np->sub = safe_malloc (np->sub_size * sizeof (struct htree_node *));
+ for (i = 0; i < np->sub_size; i++)
+ np->sub[i] = NULL;
+
+ for (i = 0; i < oldsize; i++)
+ {
+ if (oldnodes[i] != NULL)
+ {
+ htree_add (np, oldnodes[i]);
+ }
+ }
+
+ free (oldnodes);
+}
+
+/* add a sub-node, upsize if needed, calls with htree_upsizing with each other */
+static void htree_add (struct htree_node *node, struct htree_node *sub)
+{
+ int n;
+ uint32_t dh, idx;
+
+ if (node->sub == NULL)
+ htree_init_sub (node);
+
+ n = 0;
+ dh = sub->h1;
+ while (1)
+ {
+ /* eq to dh % node->sub_size, since sub_size is power of 2*/
+ idx = dh & (node->sub_size - 1);
+ if (node->sub[idx] == NULL)
+ {
+ node->sub[idx] = sub;
+ node->sub_count += 1;
+ break;
+ }
+ else
+ {
+ dh += sub->h2;
+ n++;
+ }
+ }
+
+ node->sub_maxprobe = max (n, node->sub_maxprobe);
+ /*
+ * If it takes a lots of probes to find an empty slot, or the used slots
+ * close to loading max, upsize the table
+ */
+ if (node->sub_maxprobe > OPEN_ADDRESSING_MAXPROBE ||
+ node->sub_count > node->sub_loadmax)
+ {
+ htree_upsizing (node);
+ }
+
+ return;
+}
+
+struct htree_node *htree_find_or_add (struct htree_node *node, char *label)
+{
+ struct htree_node *np;
+
+ if ((np = htree_find (node, label)) == NULL)
+ {
+ if (node->sub == NULL)
+ htree_init_sub (node);
+ np = htree_new_node (label, strlen (label));
+ htree_add (node, np);
+ }
+
+ return np;
+}
+
+/* lookup the label in node's sub, return the pointer, NULL if not found */
+static struct htree_node *htree_find (struct htree_node *node, char *label)
+{
+ uint32_t h1, h2, dh, idx;
+ struct htree_node *np;
+
+ /* this domain doesn't have sub-domains */
+ if (node->sub == NULL)
+ return NULL;
+
+ dh = h1 = dblhash_1 (label);
+ h2 = dblhash_2 (label);
+ idx = dh & (node->sub_size - 1);
+ while ((np = node->sub[idx]) != NULL)
+ {
+ if (np->h1 == h1 && np->h2 == h2)
+ if (strcmp (np->label, label) == 0)
+ return np;
+
+ dh += h2;
+ idx = dh & (node->sub_size - 1);
+ }
+
+ return NULL;
+}
+
+/* look up the whole domain pattern by step over DNS name hierarchy top down.
+ * for example, if the pattern is cn.debian.org, the lookup will start with
+ * org, then debian, then cn. The longest pattern wins. */
+struct htree_node * domain_match(struct htree_node *root, char *domain)
+{
+ char *labels[MAXLABELS];
+ int i, label_num;
+ int len = (int) sizeof(buf);
+ struct htree_node *node, *res;
+
+ if (root == NULL)
+ return NULL;
+
+ memset(buf, 0, sizeof(buf));
+ normalize_domain_name (buf, domain, len);
+
+ for (i = 0; i < MAXLABELS; i++)
+ labels[i] = NULL;
+
+ label_num = 0;
+ labels[label_num++] = &buf[0];
+
+ /* split domain name into labels */
+ for (i = 0; i < len && buf[i] != '\0'; i++)
+ {
+ if (buf[i] == '.')
+ {
+ buf[i] = '\0';
+ labels[label_num++] = &buf[i + 1];
+ }
+ }
+
+ node = root;
+ res = NULL;
+ for (i = label_num - 1; i >= 0; i--)
+ {
+ node = htree_find (node, labels[i]);
+ if (node == NULL)
+ break;
+
+ /* repeatedly overwrite with node that has option set while walk down the
+ * domain name tree to match config option with longest pattern */
+ if (node->ptr != NULL)
+ res = node;
+ }
+
+ return res;
+}
+
+/* add a domain pattern in the form of debian.org to root or find the node
+ * match the domain pattern (for modify) */
+struct htree_node *domain_find_or_add (struct htree_node *root, char *domain)
+{
+ char *labels[MAXLABELS];
+ int i, label_num;
+ int len = (int) sizeof(buf);
+ struct htree_node *node;
+
+ memset(buf, 0, sizeof(buf));
+ normalize_domain_name (buf, domain, len);
+
+ for (i = 0; i < MAXLABELS; i++)
+ labels[i] = NULL;
+
+ label_num = 0;
+ labels[label_num++] = &buf[0];
+
+ for (i = 0; i < len && buf[i] != '\0'; i++)
+ {
+ if (buf[i] == '.')
+ {
+ buf[i] = '\0';
+ labels[label_num++] = &buf[i + 1];
+ }
+ }
+
+ node = root;
+ for (i = label_num - 1; i >= 0; i--)
+ node = htree_find_or_add (node, labels[i]);
+
+ return node;
+}
+
+/* free node and all sub-nodes recursively. Unused. */
+void htree_free (struct htree_node *node)
+{
+ struct htree_node *np;
+ unsigned i;
+
+ if (node->sub_count > 0)
+ {
+ for (i = 0; i < node->sub_size; i++)
+ {
+ np = node->sub[i];
+ if (np != NULL)
+ {
+ if (np->label != NULL)
+ free (np->label);
+
+ if (np->ptr != NULL)
+ free (np->ptr);
+
+ htree_free (np);
+ }
+ }
+ free (node->sub);
+ }
+
+ free (node);
+}
+
+/* only compare addr, source_addr, interface, and flags */
+static inline int is_same_server(struct server *s1, struct server *s2)
+{
+ if (memcmp(&s1->addr, &s2->addr, sizeof(union mysockaddr)) != 0)
+ return 0;
+
+ if (strncmp(s1->interface, s2->interface, IF_NAMESIZE + 1) != 0)
+ return 0;
+
+ if (s1->flags != s2->flags)
+ return 0;
+
+ return 1;
+}
+
+/* duplicate a struct server, but only copy addr, source_addr, interfaces, and
+ * flags
+ * return the allocated pointer */
+static inline struct server *serverdup(struct server *src)
+{
+ struct server *dst;
+
+ dst = safe_malloc(sizeof(struct server));
+ memcpy(dst, src, sizeof(struct server));
+
+ return dst;
+}
+
+/* lookup server by compare addr, source_addr, interface, and flags with
+ * servers in daemon->servers link list. If no match found, then insert a new
+ * server
+ *
+ * Return the lookup result or the newly created server */
+struct server *lookup_or_install_new_server(struct server *serv)
+{
+ struct server *res;
+
+ res = NULL;
+ for (res = daemon->servers; res != NULL; res = res->next) {
+ if (is_same_server(res, serv))
+ break;
+ }
+
+ if (res == NULL) {
+ res = serverdup(serv);
+ res->next = daemon->servers;
+ daemon->servers = res;
+ }
+
+ return res;
+}
+
+/* print the daemon->htree_special_domains tree recursively */
+void print_server_special_domains (struct htree_node *node,
+ char *parents[], int current_level)
+{
+ struct htree_node *np;
+ struct special_domain *obj;
+ char buf[MAXDNAME];
+ char ip_buf[16];
+ int j, level;
+ int port = 0;
+ uint32_t i;
+
+ level = current_level + 1;
+ if (node->label != NULL)
+ {
+ parents[level] = node->label;
+ if (node->ptr != NULL)
+ {
+ obj = (struct special_domain *) node->ptr;
+ if (obj->domain_flags & SERV_HAS_DOMAIN)
+ {
+ memset (buf, 0, MAXDNAME);
+ for (j = level; j > 1; j--)
+ {
+ strcat (buf, parents[j]);
+ strcat (buf, ".");
+ }
+ buf[strlen (buf) - 1] = '\0';
+ port = prettyprint_addr (&obj->server->addr, ip_buf);
+ my_syslog(LOG_INFO, _("using nameserver %s#%d for domain %s"),
+ ip_buf, port, buf);
+ }
+ }
+ }
+
+ if (node->sub_count > 0)
+ {
+ for (i = 0; i < node->sub_size; i++)
+ if ((np = node->sub[i]) != NULL)
+ print_server_special_domains (np, parents, level);
+ }
+}
diff --git a/src/network.c b/src/network.c
index 7045253..774936b 100644
- --- a/src/network.c
+++ b/src/network.c
@@ -1422,6 +1422,10 @@ void check_servers(void)
if (!option_bool(OPT_NOWILD))
enumerate_interfaces(0);
+ char *levels[MAXLABELS + 1]; /* the root node starts at 1 */
+ struct htree_node *root = daemon->htree_special_domains;
+ print_server_special_domains(root, levels, 0);
+
for (serv = daemon->servers; serv; serv = serv->next)
{
if (!(serv->flags & (SERV_LITERAL_ADDRESS | SERV_NO_ADDR | SERV_USE_RESOLV | SERV_NO_REBIND)))
@@ -1461,13 +1465,11 @@ void check_servers(void)
if (!(serv->flags & SERV_NO_REBIND))
{
- - if (serv->flags & (SERV_HAS_DOMAIN | SERV_FOR_NODOTS | SERV_USE_RESOLV))
+ if (serv->flags & (SERV_FOR_NODOTS | SERV_USE_RESOLV))
{
char *s1, *s2;
if (!(serv->flags & SERV_HAS_DOMAIN))
s1 = _("unqualified"), s2 = _("names");
- - else if (strlen(serv->domain) == 0)
- - s1 = _("default"), s2 = "";
else
s1 = _("domain"), s2 = serv->domain;
diff --git a/src/option.c b/src/option.c
index e4b4865..e36aafa 100644
- --- a/src/option.c
+++ b/src/option.c
@@ -1980,7 +1980,7 @@ static int one_opt(int option, char *arg, char *errstr, char *gen_err, int comma
serv = opt_malloc(sizeof(struct server));
memset(serv, 0, sizeof(struct server));
serv->domain = d;
- - serv->flags = SERV_HAS_DOMAIN | SERV_NO_ADDR;
+ serv->flags = SERV_HAS_DOMAIN | SERV_NO_ADDR;
serv->next = daemon->servers;
daemon->servers = serv;
}
@@ -2223,93 +2223,198 @@ static int one_opt(int option, char *arg, char *errstr, char *gen_err, int comma
case 'A': /* --address */
case LOPT_NO_REBIND: /* --rebind-domain-ok */
{
- - struct server *serv, *newlist = NULL;
- -
- - unhide_metas(arg);
- -
- - if (arg && (*arg == '/' || option == LOPT_NO_REBIND))
- - {
- - int rebind = !(*arg == '/');
- - char *end = NULL;
- - if (!rebind)
- - arg++;
- - while (rebind || (end = split_chr(arg, '/')))
- - {
- - char *domain = NULL;
- - /* elide leading dots - they are implied in the search algorithm */
- - while (*arg == '.') arg++;
- - /* # matches everything and becomes a zero length domain string */
- - if (strcmp(arg, "#") == 0)
- - domain = "";
- - else if (strlen (arg) != 0 && !(domain = canonicalise_opt(arg)))
- - option = '?';
- - serv = opt_malloc(sizeof(struct server));
- - memset(serv, 0, sizeof(struct server));
- - serv->next = newlist;
- - newlist = serv;
- - serv->domain = domain;
- - serv->flags = domain ? SERV_HAS_DOMAIN : SERV_FOR_NODOTS;
- - arg = end;
- - if (rebind)
- - break;
- - }
- - if (!newlist)
- - ret_err(gen_err);
- - }
- - else
- - {
- - newlist = opt_malloc(sizeof(struct server));
- - memset(newlist, 0, sizeof(struct server));
+ unhide_metas (arg);
+
+ char *start_addr, *s;
+ char *err;
+ struct server newserv;
+ struct htree_node *np = NULL;
+ struct special_domain *obj;
+
+ memset (&newserv, 0, sizeof (struct server));
#ifdef HAVE_LOOP
- - newlist->uid = rand32();
+ newserv.uid = rand32 ();
#endif
- - }
- -
- - if (servers_only && option == 'S')
- - newlist->flags |= SERV_FROM_FILE;
- -
- - if (option == 'A')
- - {
- - newlist->flags |= SERV_LITERAL_ADDRESS;
- - if (!(newlist->flags & SERV_TYPE))
- - ret_err(gen_err);
- - }
- - else if (option == LOPT_NO_REBIND)
- - newlist->flags |= SERV_NO_REBIND;
- -
- - if (!arg || !*arg)
- - {
- - if (!(newlist->flags & SERV_NO_REBIND))
- - newlist->flags |= SERV_NO_ADDR; /* no server */
- - if (newlist->flags & SERV_LITERAL_ADDRESS)
- - ret_err(gen_err);
- - }
- -
- - else if (strcmp(arg, "#") == 0)
- - {
- - newlist->flags |= SERV_USE_RESOLV; /* treat in ordinary way */
- - if (newlist->flags & SERV_LITERAL_ADDRESS)
- - ret_err(gen_err);
- - }
- - else
- - {
- - char *err = parse_server(arg, &newlist->addr, &newlist->source_addr, newlist->interface, &newlist->flags);
- - if (err)
- - ret_err(err);
- - }
- -
- - serv = newlist;
- - while (serv->next)
- - {
- - serv->next->flags = serv->flags;
- - serv->next->addr = serv->addr;
- - serv->next->source_addr = serv->source_addr;
- - strcpy(serv->next->interface, serv->interface);
- - serv = serv->next;
- - }
- - serv->next = daemon->servers;
- - daemon->servers = newlist;
- - break;
+ if (arg == NULL)
+ break;
+
+ if (daemon->htree_special_domains == NULL)
+ daemon->htree_special_domains = htree_new_node (NULL, 0);
+
+ /* scan the address part first
+ * --xxxx=/example.org/ample.com/temple.net/address-of-server
+ * ^ */
+ start_addr = NULL;
+ if (strchr (arg, '/') == NULL)
+ {
+ /* --xxxx=example.org (only availabe for --rebind-domain-ok) */
+ if (option == LOPT_NO_REBIND)
+ newserv.flags |= SERV_NO_REBIND;
+ else if (option == 'S')
+ start_addr = arg; /* --server=8.8.8.8 */
+
+ }
+ else
+ {
+ for (s = arg; *s != '\0'; s++)
+ {
+ if (*s == '/')
+ start_addr = s;
+ }
+ start_addr++;
+ }
+
+ /* --xxxx=/example.org/# , here "#" means use standard server */
+ if (start_addr != NULL)
+ {
+ if (*start_addr == '#')
+ {
+ newserv.flags |= SERV_USE_RESOLV;
+ }
+
+ /* --xxxx=/example.org/here-is-empty */
+ else if (*start_addr == '\0')
+ {
+ /* give --server domain but no ip means the domain is local and
+ * it may answer queries from /etc/hosts or DHCP but should
+ * never be forwarded to upstream servers */
+ if (!(newserv.flags & SERV_NO_REBIND))
+ newserv.flags |= SERV_NO_ADDR; /* no server */
+
+ if (option == 'A')
+ ret_err ("--address must specify address");
+ }
+
+ /* --xxxx=/example.org/8.8.8.8#53 at source-ip|interface#port
+ * --xxxx=8.8.8.8 */
+ else
+ {
+ err =
+ parse_server (start_addr, &newserv.addr, &newserv.source_addr,
+ newserv.interface, &newserv.flags);
+ if (err)
+ ret_err (err);
+
+ }
+
+ }
+ /* --server */
+ if (servers_only && option == 'S')
+ newserv.flags |= SERV_FROM_FILE;
+
+ /* --rebind-domain-ok */
+ if (option == LOPT_NO_REBIND)
+ newserv.flags |= SERV_NO_REBIND;
+
+ /* --address will be handled inside the domain htree_node */
+
+
+ /* the arg pattern can be
+ * --xxxx=example.org (only availabe for --rebind-domain-ok) or
+ * --xxxx=/example.org/ or
+ * --xxxx=/example.org/ample.com/temple.net/ */
+ if (*arg == '/' || option == LOPT_NO_REBIND)
+ {
+ int rebind = !(*arg == '/');
+ char *end = NULL;
+ if (!rebind)
+ arg++;
+ while (rebind || (end = split_chr (arg, '/')))
+ {
+ char *domain = NULL;
+ /* elide leading dots - they are implied in the search algorithm */
+ while (*arg == '.')
+ arg++;
+
+ /* wrong config option --xxxx=/./1.2.3.4 */
+ if (strlen (arg) == 0)
+ continue;
+
+ /* --address=/#/1.2.3.4
+ * use label in the root node to mark #(match all domains) */
+ if (strcmp (arg, "#") == 0)
+ {
+ np = daemon->htree_special_domains;
+ free(np->label);
+ np->label = strdup("#");
+ }
+ else if (!(domain = canonicalise_opt (arg)))
+ {
+ option = '?';
+ }
+ else
+ {
+ np = domain_find_or_add(daemon->htree_special_domains, domain);
+ }
+
+ free(domain);
+ /* domain unrecognizable */
+ if (np == NULL)
+ continue;
+
+ if (np->ptr == NULL)
+ {
+ obj = opt_malloc (sizeof (struct special_domain));
+ memset (obj, 0, sizeof (struct special_domain));
+ obj->domain_flags = 0;
+ }
+ else
+ {
+ obj = (struct special_domain *) np->ptr;
+ }
+
+ obj->domain_flags = newserv.flags;
+ if (option == 'A')
+ {
+ obj->server = NULL;
+ obj->domain_flags |= SERV_LITERAL_ADDRESS;
+ memcpy (&obj->addr, &newserv.addr, sizeof (union mysockaddr));
+ }
+ else if (option == 'S' || option == LOPT_LOCAL)
+ {
+ if (newserv.flags & SERV_NO_ADDR)
+ {
+ obj->server = NULL;
+ obj->domain_flags = SERV_NO_ADDR;
+ }
+ else
+ {
+ /* pointer to one of servers in daemon->servers link
+ * list, no memory will be leaked if obj->server been
+ * overwritten */
+ newserv.flags |= SERV_HAS_DOMAIN;
+ obj->server = lookup_or_install_new_server (&newserv);
+ obj->server->domain = NULL;
+ obj->domain_flags |= SERV_HAS_DOMAIN;
+ }
+ }
+
+ if (option == LOPT_NO_REBIND)
+ {
+ /* the rebind flag here instead of the one in struct server
+ * will be used by forward */
+ obj->domain_flags |= SERV_NO_REBIND;
+ }
+
+ if (option == LOPT_LOCAL)
+ {
+ obj->domain_flags |= SERV_NO_ADDR;
+ }
+
+ np->ptr = (void *) obj;
+
+ arg = end;
+ if (rebind)
+ break;
+ }
+ }
+ /* --server=8.8.8.8 */
+ else if ((strchr (arg, '/') == NULL && option == 'S'))
+ {
+ lookup_or_install_new_server (&newserv);
+ }
+
+ break;
}
case LOPT_REV_SERV: /* --rev-server */
@@ -2352,65 +2457,85 @@ static int one_opt(int option, char *arg, char *errstr, char *gen_err, int comma
break;
#else
{
- - struct ipsets ipsets_head;
- - struct ipsets *ipsets = &ipsets_head;
- - int size;
- - char *end;
- - char **sets, **sets_pos;
- - memset(ipsets, 0, sizeof(struct ipsets));
- - unhide_metas(arg);
- - if (arg && *arg == '/')
- - {
- - arg++;
- - while ((end = split_chr(arg, '/')))
- - {
- - char *domain = NULL;
- - /* elide leading dots - they are implied in the search algorithm */
- - while (*arg == '.')
- - arg++;
- - /* # matches everything and becomes a zero length domain string */
- - if (strcmp(arg, "#") == 0 || !*arg)
- - domain = "";
- - else if (strlen(arg) != 0 && !(domain = canonicalise_opt(arg)))
- - option = '?';
- - ipsets->next = opt_malloc(sizeof(struct ipsets));
- - ipsets = ipsets->next;
- - memset(ipsets, 0, sizeof(struct ipsets));
- - ipsets->domain = domain;
- - arg = end;
- - }
- - }
- - else
- - {
- - ipsets->next = opt_malloc(sizeof(struct ipsets));
- - ipsets = ipsets->next;
- - memset(ipsets, 0, sizeof(struct ipsets));
- - ipsets->domain = "";
- - }
- - if (!arg || !*arg)
- - {
- - option = '?';
- - break;
- - }
- - size = 2;
- - for (end = arg; *end; ++end)
- - if (*end == ',')
- - ++size;
- -
- - sets = sets_pos = opt_malloc(sizeof(char *) * size);
- -
- - do {
- - end = split(arg);
- - *sets_pos++ = opt_string_alloc(arg);
- - arg = end;
- - } while (end);
- - *sets_pos = 0;
- - for (ipsets = &ipsets_head; ipsets->next; ipsets = ipsets->next)
- - ipsets->next->sets = sets;
- - ipsets->next = daemon->ipsets;
- - daemon->ipsets = ipsets_head.next;
- -
- - break;
+ int size;
+ char *end;
+ char **sets, **sets_pos;
+ int sets_count = 0;
+ unhide_metas (arg);
+ struct htree_node *np = NULL;
+ struct htree_node *setname = NULL;
+ struct ipsets_names *obj;
+ char *domain = NULL;
+
+ if (daemon->htree_ipsets == NULL)
+ daemon->htree_ipsets = htree_new_node (NULL, 0);
+
+ if (daemon->htree_ipset_names == NULL)
+ daemon->htree_ipset_names = htree_new_node (NULL, 0);
+
+ if (arg && *arg == '/')
+ {
+ arg++;
+ while ((end = split_chr (arg, '/')))
+ {
+ /* elide leading dots - they are implied in the search algorithm */
+ while (*arg == '.')
+ arg++;
+ /* # matches everything and becomes a zero length domain string */
+ if (strcmp (arg, "#") == 0 || !*arg)
+ /* ignore match all domain directive # for now */
+ /* domain = ""; */
+ ;
+ else if (strlen (arg) != 0 && !(domain = canonicalise_opt (arg)))
+ option = '?';
+
+ if (domain != NULL)
+ np = domain_find_or_add (daemon->htree_ipsets, domain);
+ free(domain);
+
+ arg = end;
+ }
+ }
+
+ if (!arg || !*arg)
+ {
+ option = '?';
+ break;
+ }
+ size = 2;
+ for (end = arg; *end; ++end)
+ if (*end == ',')
+ ++size;
+
+ sets = sets_pos = opt_malloc (sizeof (char *) * size);
+
+ do
+ {
+ end = split (arg);
+ // only store one copy of setname in daemon->htree_ipset_names
+ setname = htree_find_or_add(daemon->htree_ipset_names, arg);
+ *sets_pos++ = setname->label;
+ sets_count++;
+ arg = end;
+ }
+ while (end);
+
+ struct ipsets_names *old_obj;
+ *sets_pos = NULL;
+ if (np != NULL)
+ {
+ obj = opt_malloc(sizeof(struct ipsets_names));
+ obj->sets = sets;
+ obj->count = sets_count;
+ if (np->ptr != NULL) {
+ old_obj = (struct ipsets_names *) np->ptr;
+ free(old_obj->sets);
+ free(old_obj);
+ }
+ np->ptr = (void *) obj;
+ }
+
+ break;
}
#endif
@@ -4361,7 +4486,7 @@ void read_opts(int argc, char **argv, char *compile_opts)
{
char *buff = opt_malloc(MAXDNAME);
int option, conffile_opt = '7', testmode = 0;
- - char *arg, *conffile = CONFFILE;
+ char *arg, *conffile = NULL;
opterr = 0;
@@ -4476,7 +4601,15 @@ void read_opts(int argc, char **argv, char *compile_opts)
}
if (conffile)
- - one_file(conffile, conffile_opt);
+ {
+ one_file(conffile, conffile_opt);
+ free(conffile);
+ }
+ else
+ {
+ one_file(CONFFILE, conffile_opt);
+ }
+
/* port might not be known when the address is parsed - fill in here */
if (daemon->servers)
- --
1.7.10.4
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.12 (GNU/Linux)
iQIcBAEBAgAGBQJU7XgzAAoJEFXRMNWCXLEmGKkQAIljbaoBsOeKexF5cM9EGhPi
P4eG908/8T6dsFOKnEXRE/0K5PvlnOsBiODmONAoc1nSGP3iRVwvM0IQhWEAhqND
B9ScOoBwAKAkFnTvPmZd6/mjSJ6vklRdPJ6+RgNrConreHCutR3v9hX36yOnuP7P
KBNO2KVAXcwQS9ynLw5wiK8/pQ3YyZ4g7yvfKtKJThHxki2xI71h/MGtKi1poY+z
NoSBJ/4G+HEJp4E10h38Kow0fpiUJvgWkPkiR9EnqqJq310IyttTRJn5NRVvm/uA
gs2hXaKNMO1bVwSmam93eyrvwBpkPsmoWJIFGx3oHvSDZ8tfFBrN7xaAO9uCh2xH
M49eaMqDBJJSj+/ERH8v8TZ2uIeGaTMovMy+l2j+qW3QzoYVv4GmyjgjvZrDCF33
60uRNwPDnetEEVtvnasmDDeddKYY98L7FfLItSP6tUKN6RtwK7roLIbPnfBaYKKc
DagugAr1xtJ8NjGpZxXITEJPtp4maNAmGo40+t72zAy8zHFk0jX50iZdsDOcRppN
F+aH08DEP9cliaN4Ha383nQE4vWQla/PHbWLV8iFFVN7mWOEbrS5TdqfZk/4IGWE
YHcyG5NxCfCOsM4P6rnCwBltm1T6y3DZ1dnwXo31aQhyjeZ1qLJaWFoDI3objq+V
DZA0J1cQvYkwaek5O8CU
=ZOcR
-----END PGP SIGNATURE-----
More information about the Dnsmasq-discuss
mailing list