/*
 * Copyright (c) 1999 Apple Computer, Inc. All rights reserved.
 *
 * @APPLE_LICENSE_HEADER_START@
 * 
 * Portions Copyright (c) 1999 Apple Computer, Inc.  All Rights
 * Reserved.  This file contains Original Code and/or Modifications of
 * Original Code as defined in and that are subject to the Apple Public
 * Source License Version 1.1 (the "License").  You may not use this file
 * except in compliance with the License.  Please obtain a copy of the
 * License at http://www.apple.com/publicsource and read it before using
 * this file.
 * 
 * The Original Code and all software distributed under the License are
 * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER
 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE OR NON- INFRINGEMENT.  Please see the
 * License for the specific language governing rights and limitations
 * under the License.
 * 
 * @APPLE_LICENSE_HEADER_END@
 */

#include <netdb.h>
#include <sys/types.h>
#include <sys/time.h>
#include <sys/socket.h>
#include <net/if.h>
#include <netinet/in.h>
#include <arpa/inet.h>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <ctype.h>
#include <rpc/types.h>
#include <rpc/xdr.h>
#include <mach/mach.h>
#include <servers/bootstrap.h>
#include <nameser.h>
#include <resolv.h>
#include <netdb.h>
#include <arpa/inet.h>
#include <ifaddrs.h>

#define SOCK_UNSPEC 0
#define IPPROTO_UNSPEC 0

#define WANT_A4_ONLY 1
#define WANT_A6_ONLY 2
#define WANT_A6_PLUS_MAPPED_A4 3
#define WANT_A6_OR_MAPPED4_IF_NO_A6 4

#define LONG_STRING_LENGTH 8192
#define _LU_MAXLUSTRLEN 256

extern int _lu_running(void);
extern mach_port_t _lookupd_port();
extern int _lookup_link();
extern int _lookup_one();
extern int _lookup_all();

struct lu_dict
{
	int count;
	char *type;
	char *name;
	char *cname;
	char *mx;
	char *ipv4;
	char *ipv6;
	char *service;
	char *port;
	char *protocol;
	char *target;
	char *priority;
	char *weight;
	struct lu_dict *lu_next;
};

#define LU_NAME     1
#define LU_CNAME    2
#define LU_MX       3
#define LU_IPV4     4
#define LU_IPV6     5
#define LU_PORT     6
#define LU_TARGET   7
#define LU_PRIORITY 8
#define LU_WEIGHT   9

static int supported_family[] =
{
	PF_UNSPEC,
	PF_INET,
	PF_INET6
};
static int supported_family_count = 3;

static int supported_socket[] =
{
	SOCK_RAW,
	SOCK_UNSPEC,
	SOCK_DGRAM,
	SOCK_STREAM
};
static int supported_socket_count = 4;

static int supported_protocol[] =
{
	IPPROTO_UNSPEC,
	IPPROTO_ICMPV6,
	IPPROTO_UDP,
	IPPROTO_TCP
};
static int supported_protocol_count = 4;

static int supported_socket_protocol_pair[] =
{
	SOCK_RAW,    IPPROTO_UNSPEC,
	SOCK_RAW,    IPPROTO_UDP,
	SOCK_RAW,    IPPROTO_TCP,
	SOCK_RAW,    IPPROTO_ICMPV6,
	SOCK_UNSPEC, IPPROTO_UNSPEC,
	SOCK_UNSPEC, IPPROTO_UDP,
	SOCK_UNSPEC, IPPROTO_TCP,
	SOCK_UNSPEC, IPPROTO_ICMPV6,
	SOCK_DGRAM,  IPPROTO_UNSPEC,
	SOCK_DGRAM,  IPPROTO_UDP,
	SOCK_STREAM, IPPROTO_UNSPEC,
	SOCK_STREAM, IPPROTO_TCP
};
static int supported_socket_protocol_pair_count = 12;

static int
gai_family_type_check(int f)
{
	int i;
	
	for (i = 0; i < supported_family_count; i++)
	{
		if (f == supported_family[i]) return 0;
	}

	return 1;
}

static int
gai_socket_type_check(int s)
{
	int i;
	
	for (i = 0; i < supported_socket_count; i++)
	{
		if (s == supported_socket[i]) return 0;
	}

	return 1;
}

static int
gai_protocol_type_check(int p)
{
	int i;
	
	for (i = 0; i < supported_protocol_count; i++)
	{
		if (p == supported_protocol[i]) return 0;
	}

	return 1;
}

static int
gai_socket_protocol_type_check(int s, int p)
{
	int i, j, ss, sp;
	
	for (i = 0, j = 0; i < supported_socket_protocol_pair_count; i++, j+=2)
	{
		ss = supported_socket_protocol_pair[j];
		sp = supported_socket_protocol_pair[j+1];
		if ((s == ss) && (p == sp)) return 0;
	}

	return 1;
}

static int
gai_inet_pton(const char *s, struct in6_addr *a6)
{
	if (s == NULL) return 0;
	if (a6 == NULL) return 0;
	return inet_pton(AF_INET6, s, (void *)&a6->__u6_addr.__u6_addr32[0]);
}

char *
gai_strerror(int err)
{
	switch (err)
	{
		case EAI_ADDRFAMILY: return "Address family for nodename not supported";
		case EAI_AGAIN: return "Temporary failure in name resolution";
		case EAI_BADFLAGS:	return "Invalid value for ai_flags";
		case EAI_FAIL: return "Non-recoverable failure in name resolution";
		case EAI_FAMILY: return "ai_family not supported";
		case EAI_MEMORY: return "Memory allocation failure";
		case EAI_NODATA: return "No address associated with nodename";
		case EAI_NONAME: return "nodename nor servname provided, or not known";
		case EAI_SERVICE: return "servname not supported for ai_socktype";
		case EAI_SOCKTYPE: return "ai_socktype not supported";
		case EAI_SYSTEM: return "System error";
		case EAI_BADHINTS: return "Bad hints";
		case EAI_PROTOCOL: return "ai_protocol not supported";
	}

	return "Unknown error";
}

static int
is_ipv4_address(const char *s)
{
	struct in_addr a;

	if (s == NULL) return 0;
	return inet_aton(s, &a);
}

static int
is_ipv6_address(const char *s)
{
	struct in6_addr a;

	if (s == NULL) return 0;
	return gai_inet_pton(s, &a);
}

static void
append_addrinfo(struct addrinfo **l, struct addrinfo *a)
{
	struct addrinfo *x;

	if (l == NULL) return;
	if (a == NULL) return;

	if (*l == NULL)
	{
		*l = a;
		return;
	}

	x = *l;

	if (a->ai_family == PF_INET6)
	{
		if (x->ai_family == PF_INET)
		{
			*l = a;
			a->ai_next = x;
			return;
		}

		while ((x->ai_next != NULL) && (x->ai_next->ai_family != PF_INET)) x = x->ai_next;
		a->ai_next = x->ai_next;
		x->ai_next = a;
	}
	else
	{
		while (x->ai_next != NULL) x = x->ai_next;
		a->ai_next = NULL;
		x->ai_next = a;
	}
}

static void
free_lu_dict(struct lu_dict *d)
{
	struct lu_dict *next;

	while (d != NULL)
	{
		next = d->lu_next;
		if (d->type != NULL) free(d->type);
		if (d->name != NULL) free(d->name);
		if (d->cname != NULL) free(d->cname);
		if (d->mx != NULL) free(d->mx);
		if (d->ipv4 != NULL) free(d->ipv4);
		if (d->ipv6 != NULL) free(d->ipv6);
		if (d->service != NULL) free(d->service);
		if (d->port != NULL) free(d->port);
		if (d->protocol != NULL) free(d->protocol);
		if (d->target != NULL) free(d->target);
		if (d->priority != NULL) free(d->priority);
		if (d->weight != NULL) free(d->weight);
		free(d);
		d = next;
	}
}

static int
_lu_str_equal(char *a, char *b)
{
	if (a == NULL)
	{
		if (b == NULL) return 1;
		return 0;
	}

	if (b == NULL) return 0;

	if (!strcmp(a, b)) return 1;
	return 0;
}

static int
lu_dict_equal(struct lu_dict *a, struct lu_dict *b)
{
	if (a == NULL) return 0;
	if (b == NULL) return 0;

	if (_lu_str_equal(a->type, b->type) == 0) return 0;
	if (_lu_str_equal(a->name, b->name) == 0) return 0;
	if (_lu_str_equal(a->cname, b->cname) == 0) return 0;
	if (_lu_str_equal(a->mx, b->mx) == 0) return 0;
	if (_lu_str_equal(a->ipv4, b->ipv4) == 0) return 0;
	if (_lu_str_equal(a->ipv6, b->ipv6) == 0) return 0;
	if (_lu_str_equal(a->service, b->service) == 0) return 0;
	if (_lu_str_equal(a->port, b->port) == 0) return 0;
	if (_lu_str_equal(a->protocol, b->protocol) == 0) return 0;
	if (_lu_str_equal(a->target, b->target) == 0) return 0;
	if (_lu_str_equal(a->priority, b->priority) == 0) return 0;
	if (_lu_str_equal(a->weight, b->weight) == 0) return 0;
	return 1;
}

/*
 * Append a single dictionary to a list if it is unique.
 * Free it if it is not appended.
 */
static void
merge_lu_dict(struct lu_dict **l, struct lu_dict *d)
{
	struct lu_dict *x, *e;

	if (l == NULL) return;
	if (d == NULL) return;

	if (*l == NULL)
	{
		*l = d;
		return;
	}

	e = *l;
	for (x = *l; x != NULL; x = x->lu_next)
	{
		e = x;
		if (lu_dict_equal(x, d))
		{
			free_lu_dict(d);
			return;
		}
	}

	e->lu_next = d;
}

static void
append_lu_dict(struct lu_dict **l, struct lu_dict *d)
{
	struct lu_dict *x, *next;

	if (l == NULL) return;
	if (d == NULL) return;

	if (*l == NULL)
	{
		*l = d;
		return;
	}

	x = d;

	while (x != NULL)
	{
		next = x->lu_next;
		x->lu_next = NULL;
		merge_lu_dict(l, x);
		x = next;
	}
}

/*
 * We collect values for the following keys:
 *
 *    name
 *    cname
 *    port
 *    ip_address
 *    ipv6_address
 *    target
 *    mail_exchanger
 *    priority
 *    preference
 *    weight
 */
static void
lookupd_process_dictionary(XDR *inxdr, struct lu_dict **l)
{
	int i, nkeys, j, nvals;
	int addme;
	char *key, *val;
	struct lu_dict *d;

	if (!xdr_int(inxdr, &nkeys)) return;

	d = (struct lu_dict *)malloc(sizeof(struct lu_dict));
	memset(d, 0, sizeof(struct lu_dict));

	for (i = 0; i < nkeys; i++)
	{
		key = NULL;

		if (!xdr_string(inxdr, &key, LONG_STRING_LENGTH))
		{
			free_lu_dict(d);
			return;
		}

		addme = 0;
		if (!strcmp(key, "name")) addme = LU_NAME;
		else if (!strcmp(key, "cname")) addme = LU_CNAME;
		else if (!strcmp(key, "mail_exchanger")) addme = LU_MX;
		else if (!strcmp(key, "ip_address")) addme = LU_IPV4;
		else if (!strcmp(key, "ipv6_address")) addme = LU_IPV6;
		else if (!strcmp(key, "port")) addme = LU_PORT;
		else if (!strcmp(key, "target")) addme = LU_TARGET;
		else if (!strcmp(key, "priority")) addme = LU_PRIORITY;
		else if (!strcmp(key, "preference")) addme = LU_PRIORITY;
		else if (!strcmp(key, "weight")) addme = LU_WEIGHT;
		free(key);

		if (!xdr_int(inxdr, &nvals))
		{
			free_lu_dict(d);
			return;
		}
	
		for (j = 0; j < nvals; j++)
		{
			val = NULL;
			if (!xdr_string(inxdr, &val, LONG_STRING_LENGTH))
			{
				free_lu_dict(d);
				return;
			}

			if (addme == 0) free(val);
			else if (addme == LU_NAME) d->name = val;
			else if (addme == LU_CNAME) d->cname = val;
			else if (addme == LU_MX) d->mx = val;
			else if (addme == LU_IPV4) d->ipv4 = val;
			else if (addme == LU_IPV6) d->ipv6 = val;
			else if (addme == LU_PORT) d->port = val;
			else if (addme == LU_TARGET) d->target = val;
			else if (addme == LU_PRIORITY) d->priority = val;
			else if (addme == LU_WEIGHT) d->weight = val;

			if (addme != 0) d->count++;
			addme = 0;
		}
	}

	merge_lu_dict(l, d);
}

static int
encode_kv(XDR *x, char *k, char *v)
{
	int n = 1;

	if (!xdr_string(x, &k, _LU_MAXLUSTRLEN)) return 1;
	if (!xdr_int(x, &n)) return 1;
	if (!xdr_string(x, &v, _LU_MAXLUSTRLEN)) return 1;

	return 0;
}

static int
gai_files(struct lu_dict *q, struct lu_dict **list)
{
	int port, i;
	struct servent *s;
	struct hostent *h;
	struct lu_dict *d;
	char str[64], portstr[64];
	struct in_addr a4;

	if (!strcmp(q->type, "service"))
	{
		s = NULL;
		if (q->name != NULL)
		{
			s = getservbyname(q->name, q->protocol);
		}
		else if (q->port != NULL)
		{
			port = atoi(q->port);
			s = getservbyport(port, q->protocol);
		}
		if (s == NULL) return 0;
	
		d = (struct lu_dict *)malloc(sizeof(struct lu_dict));
		memset(d, 0, sizeof(struct lu_dict));

		if (s->s_name != NULL) d->name = strdup(s->s_name);
		sprintf(str, "%u", ntohl(s->s_port));
		d->port = strdup(str);
		if (s->s_proto != NULL) d->protocol = strdup(s->s_proto);

		merge_lu_dict(list, d);
		return 1;
	}

	if (!strcmp(q->type, "host"))
	{
		s = NULL;
		if (q->service != NULL)
		{
			s = getservbyname(q->service, q->protocol);
		}
		else if (q->port != NULL)
		{
			port = atoi(q->port);
			s = getservbyport(port, q->protocol);
		}

		sprintf(portstr, "0");
		if (s != NULL) sprintf(portstr, "%u", ntohl(s->s_port));

		h = NULL;
		if (q->name != NULL)
		{
			h = gethostbyname(q->name);
		}
		else if (q->ipv4 != NULL)
		{
			if (inet_aton(q->ipv4, &a4) == 0) return -1;
			h = gethostbyaddr((char *)&a4, sizeof(struct in_addr), PF_INET);
		}
		else 
		{
			/* gethostbyaddr for IPV6? */
			return 0;
		}
		
		if (h == NULL) return 0;

		for (i = 0; h->h_addr_list[i] != 0; i++)
		{
			d = (struct lu_dict *)malloc(sizeof(struct lu_dict));
			memset(d, 0, sizeof(struct lu_dict));

			if (h->h_name != NULL)
			{
				d->name = strdup(h->h_name);
				d->target = strdup(h->h_name);
			}
			memmove((void *)&a4.s_addr, h->h_addr_list[i], h->h_length);

			sprintf(str, "%s", inet_ntoa(a4));
			d->ipv4 = strdup(str);

			if (s != NULL)
			{
				if (s->s_name != NULL) d->service = strdup(s->s_name);
				d->port = strdup(portstr);
			}

			merge_lu_dict(list, d);
		}
		return i;
	}

	return 0;
}

static int
gai_lookupd(struct lu_dict *q, struct lu_dict **list)
{
	unsigned datalen;
	XDR outxdr;
	XDR inxdr;
	int proc;
	char *listbuf;
	char databuf[_LU_MAXLUSTRLEN * BYTES_PER_XDR_UNIT];
	int n, i, na;
	kern_return_t status;
	mach_port_t server_port;

	if (q == NULL) return 0;
	if (q->count == 0) return 0;
	if (q->type == NULL) return 0;
	
	if (list == NULL) return -1;

	server_port = MACH_PORT_NULL;
	if (_lu_running()) server_port = _lookupd_port(0);

	if (server_port == MACH_PORT_NULL) return gai_files(q, list);

	status = _lookup_link(server_port, "query", &proc);
	if (status != KERN_SUCCESS) return gai_files(q, list);

	xdrmem_create(&outxdr, databuf, sizeof(databuf), XDR_ENCODE);

	/* Encode attribute count */
	na = q->count;
	if (!xdr_int(&outxdr, &na))
	{
		xdr_destroy(&outxdr);
		return -1;
	}

	if (encode_kv(&outxdr, "_lookup_category", q->type) != 0)
	{
		xdr_destroy(&outxdr);
		return -1;
	}

	if (q->name != NULL)
	{
		if (encode_kv(&outxdr, "name", q->name) != 0)
		{
			xdr_destroy(&outxdr);
			return -1;
		}
	}

	if (q->ipv4 != NULL)
	{
		if (encode_kv(&outxdr, "ip_address", q->ipv4) != 0)
		{
			xdr_destroy(&outxdr);
			return -1;
		}
	}

	if (q->ipv6 != NULL)
	{
		if (encode_kv(&outxdr, "ipv6_address", q->ipv6) != 0)
		{
			xdr_destroy(&outxdr);
			return -1;
		}
	}

	if (q->service != NULL)
	{
		if (encode_kv(&outxdr, "service", q->service) != 0)
		{
			xdr_destroy(&outxdr);
			return -1;
		}
	}

	if (q->port != NULL)
	{
		if (encode_kv(&outxdr, "port", q->port) != 0)
		{
			xdr_destroy(&outxdr);
			return -1;
		}
	}

	if (q->protocol != NULL)
	{
		if (encode_kv(&outxdr, "protocol", q->protocol) != 0)
		{
			xdr_destroy(&outxdr);
			return -1;
		}
	}

	listbuf = NULL;
	datalen = 0;

	n = xdr_getpos(&outxdr) / BYTES_PER_XDR_UNIT;
	status = _lookup_all(server_port, proc, databuf, n, &listbuf, &datalen);
	if (status != KERN_SUCCESS)
	{
		xdr_destroy(&outxdr);
		return -1;
	}

	xdr_destroy(&outxdr);

	datalen *= BYTES_PER_XDR_UNIT;

	xdrmem_create(&inxdr, listbuf, datalen, XDR_DECODE);

	if (!xdr_int(&inxdr, &n))
	{
		xdr_destroy(&inxdr);
		return -1;
	}
	
	for (i = 0; i < n; i++)
	{
		lookupd_process_dictionary(&inxdr, list);
	}

	xdr_destroy(&inxdr);

	vm_deallocate(mach_task_self(), (vm_address_t)listbuf, datalen);
	
	return n;
}

void
freeaddrinfo(struct addrinfo *a)
{
	struct addrinfo *next;

	while (a != NULL)
	{
		next = a->ai_next;
		if (a->ai_addr != NULL) free(a->ai_addr);
		if (a->ai_canonname != NULL) free(a->ai_canonname);
		free(a);
		a = next;
	}
}

static struct addrinfo *
new_addrinfo_v4(int flags, int sock, int proto, unsigned short port, struct in_addr addr, char *cname)
{
	struct addrinfo *a;
	struct sockaddr_in *sa;
	int len;

	a = (struct addrinfo *)malloc(sizeof(struct addrinfo));
	memset(a, 0, sizeof(struct addrinfo));
	a->ai_next = NULL;

	a->ai_flags = flags;
	a->ai_family = PF_INET;
	a->ai_socktype = sock;
	a->ai_protocol = proto;

	a->ai_addrlen = sizeof(struct sockaddr_in);
	sa = (struct sockaddr_in *)malloc(a->ai_addrlen);
	memset(sa, 0, a->ai_addrlen);
	sa->sin_len = a->ai_addrlen;
	sa->sin_family = PF_INET;
	sa->sin_port = port;
	sa->sin_addr = addr;
	a->ai_addr = (struct sockaddr *)sa;

	if (cname != NULL)
	{
		len = strlen(cname) + 1;
		a->ai_canonname = malloc(len);
		memmove(a->ai_canonname, cname, len);
	}

	return a;
}

static struct addrinfo *
new_addrinfo_v6(int flags, int sock, int proto, unsigned short port, struct in6_addr addr, char *cname)
{
	struct addrinfo *a;
	struct sockaddr_in6 *sa;
	int len;

	a = (struct addrinfo *)malloc(sizeof(struct addrinfo));
	memset(a, 0, sizeof(struct addrinfo));
	a->ai_next = NULL;

	a->ai_flags = flags;
	a->ai_family = PF_INET6;
	a->ai_socktype = sock;
	a->ai_protocol = proto;

	a->ai_addrlen = sizeof(struct sockaddr_in6);
	sa = (struct sockaddr_in6 *)malloc(a->ai_addrlen);
	memset(sa, 0, a->ai_addrlen);
	sa->sin6_len = a->ai_addrlen;
	sa->sin6_family = PF_INET6;
	sa->sin6_port = port;
	sa->sin6_addr = addr;
	a->ai_addr = (struct sockaddr *)sa;

	if (cname != NULL)
	{
		len = strlen(cname) + 1;
		a->ai_canonname = malloc(len);
		memmove(a->ai_canonname, cname, len);
	}

	return a;
}

static void
grok_nodename(const char *nodename, int family, struct lu_dict *q)
{
	if (nodename == NULL) return;
	if (q == NULL) return;

	if (((family == PF_UNSPEC) || (family == PF_INET)) && is_ipv4_address(nodename))
	{
		q->ipv4 = (char *)nodename;
	}
	else if (((family == PF_UNSPEC) || (family == PF_INET6)) && is_ipv6_address(nodename))
	{
		q->ipv6 = (char *)nodename;
	}
	else
	{
		q->name = (char *)nodename;
	}
}
	
static void
grok_service(const char *servname, struct lu_dict *q)
{
	int port;
	char *p;

	if (servname == NULL) return;
	if (q == NULL) return;

	port = 0;
	for (p = (char *)servname; (port == 0) && (*p != '\0'); p++)
	{
		if (!isdigit(*p)) port = -1;
	}

	if (port == 0) q->port = (char *)servname;
	else q->service = (char *)servname;
}

static int
gai_numerichost(struct lu_dict *h, struct lu_dict **list)
{
	struct lu_dict *a;
	int n;

	if (h == NULL) return 0;
	if (list == NULL) return -1;

	n = 0;

	if (h->ipv4 != NULL)
	{
		a = (struct lu_dict *)malloc(sizeof(struct lu_dict));
		memset(a, 0, sizeof(struct lu_dict));
		a->ipv4 = strdup(h->ipv4);
		merge_lu_dict(list, a);
		n++;
	}

	if (h->ipv6 != NULL)
	{
		a = (struct lu_dict *)malloc(sizeof(struct lu_dict));
		memset(a, 0, sizeof(struct lu_dict));
		a->ipv6 = strdup(h->ipv6);
		merge_lu_dict(list, a);
		n++;
	}

	return n;	
}

static int
gai_numericserv(struct lu_dict *s, struct lu_dict **list)
{
	struct lu_dict *a;

	if (s == NULL) return 0;
	if (s->port == NULL) return 0;
	if (list == NULL) return -1;

	a = (struct lu_dict *)malloc(sizeof(struct lu_dict));
	memset(a, 0, sizeof(struct lu_dict));
	a->port = strdup(s->port);
	merge_lu_dict(list, a);
	return 1;	
}

static void
merge_addr4(struct in_addr a, struct sockaddr_in ***l, int *n)
{
	int i;
	struct sockaddr_in *sa4;

	for (i = 0; i < *n; i++)
	{
		if (((*l)[i]->sin_family == PF_INET) && (a.s_addr == (*l)[i]->sin_addr.s_addr)) return;
	}
	
	sa4 = (struct sockaddr_in *)malloc(sizeof(struct sockaddr_in));
	memset(sa4, 0, sizeof(struct sockaddr_in));

	sa4->sin_family = PF_INET;
	sa4->sin_addr = a;

	if (*n == 0) *l = (struct sockaddr_in **)malloc(sizeof(struct sockaddr_in *));
	else *l = (struct sockaddr_in **)realloc(*l, (*n + 1) * sizeof(struct sockaddr_in *));

	(*l)[*n] = sa4;
	(*n)++;
}

static void
merge_addr6(struct in6_addr a, struct sockaddr_in6 ***l, int *n)
{
	int i;
	struct sockaddr_in6 *sa6;

	for (i = 0; i < *n; i++)
	{
		if (((*l)[i]->sin6_family == PF_INET6)
		&& (a.__u6_addr.__u6_addr32[0] == (*l)[i]->sin6_addr.__u6_addr.__u6_addr32[0])) return;
	}
	
	sa6 = (struct sockaddr_in6 *)malloc(sizeof(struct sockaddr_in6));
	memset(sa6, 0, sizeof(struct sockaddr_in6));

	sa6->sin6_family = PF_INET6;
	sa6->sin6_addr = a;

	if (*n == 0) *l = (struct sockaddr_in6 **)malloc(sizeof(struct sockaddr_in6 *));
	else *l = (struct sockaddr_in6 **)realloc(*l, (*n + 1) * sizeof(struct sockaddr_in6 *));

	(*l)[*n] = sa6;
	(*n)++;
}

/*
 * N.B. We use sim_family to store protocol in the sockaddr.
 * sockaddr is just used here as a data structure to keep
 * (port, protocol) pairs.
 */
static void
merge_plist(unsigned short port, unsigned short proto, struct sockaddr_in ***l, int *n)
{
	int i;
	struct sockaddr_in *sa4;

	for (i = 0; i < *n; i++)
	{
		if ((port == (*l)[i]->sin_port) && (proto == (*l)[i]->sin_family)) return;
	}
	
	sa4 = (struct sockaddr_in *)malloc(sizeof(struct sockaddr_in));
	memset(sa4, 0, sizeof(struct sockaddr_in));

	sa4->sin_port = port;
	sa4->sin_family = proto;

	if (*n == 0) *l = (struct sockaddr_in **)malloc(sizeof(struct sockaddr_in *));
	else *l = (struct sockaddr_in **)realloc(*l, (*n + 1) * sizeof(struct sockaddr_in *));

	(*l)[*n] = (struct sockaddr_in *)sa4;
	(*n)++;
}

/*
 * Compute x[n + 1] = (7^5 * x[n]) mod (2^31 - 1).
 * From "Random number generators: good ones are hard to find",
 * Park and Miller, Communications of the ACM, vol. 31, no. 10,
 * October 1988, p. 1195.
 */
static int
gai_random()
{
	static int did_init = 0;
	static unsigned int randseed = 1;
	int x, hi, lo, t; 
	struct timeval tv;

	if (did_init++ == 0)
	{
		gettimeofday(&tv, NULL);
		randseed = tv.tv_usec;
		if(randseed == 0) randseed = 1;
	}

	x = randseed;
	hi = x / 127773;
	lo = x % 127773;
	t = 16807 * lo - 2836 * hi;
	if (t <= 0) t += 0x7fffffff;
	randseed = t;
	return t;
}

/*
 * Sort by priority and weight.
 */
void
lu_prioity_sort(struct lu_dict **l)
{
	struct lu_dict *d, **nodes;
	unsigned int x, count, i, j, bottom, *pri, *wgt, swap, t;

	if (*l == NULL) return;

	count = 0;
	for (d = *l; d != NULL; d = d->lu_next) count++;
	nodes = (struct lu_dict **)malloc(count * sizeof(struct lu_dict *));
	pri = (unsigned int *)malloc(count * sizeof(unsigned int));
	wgt = (unsigned int *)malloc(count * sizeof(unsigned int));

	for (i = 0, d = *l; d != NULL; d = d->lu_next, i++)
	{
		nodes[i] = d;

		x = (unsigned int)-1;
		if (d->priority != NULL) x = atoi(d->priority);
		pri[i] = x;

		x = 0;
		if (d->weight != NULL) x = atoi(d->weight);
		wgt[i] = (gai_random() % 10000) * x;
	}

	/* bubble sort by priority */
	swap = 1;
	bottom = count - 1;

	while (swap == 1)
	{
		swap = 0;
		for (i = 0, j = 1; i < bottom; i++, j++)
		{
			if (pri[i] < pri[j]) continue;
			if ((pri[i] == pri[j]) && (wgt[i] < wgt[j])) continue;
			swap = 1;

			t = pri[i];
			pri[i] = pri[j];
			pri[j] = t;

			t = wgt[i];
			wgt[i] = wgt[j];
			wgt[j] = t;

			d = nodes[i];
			nodes[i] = nodes[j];
			nodes[j] = d;
		}

		bottom--;
	}
	
	*l = nodes[0];
	bottom = count - 1;
	for (i = 0, j = 1; i < bottom; i++, j++) nodes[i]->lu_next = nodes[j];
	nodes[bottom]->lu_next = NULL;

	free(pri);
	free(wgt);
	free(nodes);
}

/*
 * Get service records from lookupd
 */
static void
gai_serv_lookupd(const char *servname, int proto, int numericserv, struct lu_dict **list)
{
	struct lu_dict q, *sub;

	memset(&q, 0, sizeof(struct lu_dict));
	q.count = 3;
	q.type = "service";

	grok_service(servname, &q);
	if (q.service != NULL)
	{
		q.name = q.service;
		q.service = NULL;
	}

	if ((proto == IPPROTO_UNSPEC) || (proto == IPPROTO_UDP))
	{
		sub = NULL;
		q.protocol = "udp";
		if (numericserv == 1) gai_numericserv(&q, &sub);
		else gai_lookupd(&q, &sub);
		append_lu_dict(list, sub);
		for (; sub != NULL; sub = sub->lu_next) sub->protocol = strdup("udp");
	}

	if ((proto == IPPROTO_UNSPEC) || (proto == IPPROTO_TCP))
	{
		sub = NULL;
		q.protocol = "tcp";
		if (numericserv == 1) gai_numericserv(&q, &sub);
		else gai_lookupd(&q, &sub);
		append_lu_dict(list, sub);
		for (; sub != NULL; sub = sub->lu_next) sub->protocol = strdup("tcp");
	}
}

/*
 * Find a service.
 */
static int
gai_serv(const char *servname, const struct addrinfo *hints, struct addrinfo **res)
{
	struct lu_dict *list, *d;
	int proto, family, socktype, setcname, wantv4, wantv6;
	unsigned short port;
	char *loopv4, *loopv6;
	struct addrinfo *a;
	struct in_addr a4;
	struct in6_addr a6;

	loopv4 = "127.0.0.1";
	loopv6 = "0:0:0:0:0:0:0:1";

	family = PF_UNSPEC;
	proto = IPPROTO_UNSPEC;
	setcname = 0;

	if (hints != NULL)
	{
		proto = hints->ai_protocol;
		if (hints->ai_socktype == SOCK_DGRAM) proto = IPPROTO_UDP;
		if (hints->ai_socktype == SOCK_STREAM) proto = IPPROTO_TCP;

		if (hints->ai_flags & AI_CANONNAME) setcname = 1;

		if ((hints->ai_flags & AI_PASSIVE) == 1)
		{
			loopv4 = "0.0.0.0";
			loopv6 = "0:0:0:0:0:0:0:0";
		}

		family = hints->ai_family;
	}

	wantv4 = 1;
	wantv6 = 1;
	if (family == PF_INET6) wantv4 = 0;
	if (family == PF_INET) wantv6 = 0;

	list = NULL;
	gai_serv_lookupd(servname, proto, 0, &list);
	if (list == NULL) gai_serv_lookupd(servname, proto, 1, &list);
		
	for (d = list; d != NULL; d = d->lu_next)
	{
		/* We only want records with port and protocol specified */
		if ((d->port == NULL) || (d->protocol == NULL)) continue;

		port = htons(atoi(d->port));
		proto = IPPROTO_UDP;
		socktype = SOCK_DGRAM;
		if (!strcasecmp(d->protocol, "tcp"))
		{
			proto = IPPROTO_TCP;
			socktype = SOCK_STREAM;
		}

		if (wantv4 == 1)
		{
			inet_aton(loopv4, &a4);
			a = new_addrinfo_v4(0, socktype, proto, port, a4, NULL);
			append_addrinfo(res, a);
		}

		if (wantv6 == 1)
		{
			gai_inet_pton(loopv6, &a6);
			a = new_addrinfo_v6(0, socktype, proto, port, a6, NULL);
			append_addrinfo(res, a);
		}
	}

	free_lu_dict(list);

	/* Set cname in first result */
	if ((setcname == 1) && (*res != NULL))
	{
		if (res[0]->ai_canonname == NULL) res[0]->ai_canonname = strdup("localhost");
	}

	return 0;
}

/*
 * Find a node.
 */
static void
gai_node_lookupd(const char *nodename, int family, int numerichost, struct lu_dict **list)
{
	struct lu_dict q;

	memset(&q, 0, sizeof(struct lu_dict));
	q.count = 2;
	q.type = "host";

	grok_nodename(nodename, family, &q);
	if (numerichost) gai_numerichost(&q, list);
	else gai_lookupd(&q, list);
}

/*
 * Find a node.
 */
static int
gai_node(const char *nodename, const struct addrinfo *hints, struct addrinfo **res)
{
	int i, family, numerichost, setcname, a_list_count, wantv4, wantv6;
	struct lu_dict *list, *d, *t;
	char *cname;
	struct in_addr a4;
	struct in6_addr a6;
	struct addrinfo *a;
	struct sockaddr **a_list;
	struct sockaddr_in *sa4;
	struct sockaddr_in6 *sa6;

	a_list_count = 0;
	a_list = NULL;

	numerichost = 0;
	family = PF_UNSPEC;
	setcname = 0;
	cname = NULL;

	if (hints != NULL)
	{
		family = hints->ai_family;
		if (hints->ai_flags & AI_NUMERICHOST) numerichost = 1;
		if (hints->ai_flags & AI_CANONNAME) setcname = 1;
	}

	wantv4 = 1;
	wantv6 = 1;
	if (family == PF_INET6) wantv4 = 0;
	if (family == PF_INET) wantv6 = 0;

	t = NULL;
	gai_node_lookupd(nodename, family, numerichost, &t);
	if ((t == NULL) && (numerichost == 0))
	{
		gai_node_lookupd(nodename, family, 1, &t);
	}

	/* If the nodename is an alias, look up the real name */
	list = NULL;
	for (d = t; d != NULL; d = d->lu_next)
	{
		if (d->cname != NULL)
		{
			if (cname == NULL) cname = strdup(d->cname);
			gai_node_lookupd(d->cname, family, 0, &t);
		}
	}

	append_lu_dict(&list, t);
	
	for (d = list; d != NULL; d = d->lu_next)
	{
		/* Check for cname */
		if ((cname == NULL) && (d->name != NULL) && (strchr(d->name, '.') != NULL))
		{
			cname = strdup(d->name);
		}

		/* Check for ipv4 address */
		if ((d->ipv4 != NULL) && (wantv4 == 1))
		{
			inet_aton(d->ipv4, &a4);
			merge_addr4(a4, (struct sockaddr_in ***)&a_list, &a_list_count);
		}

		/* Check for ipv6 address */
		if ((d->ipv6 != NULL) && (wantv6 == 1))
		{
			gai_inet_pton(d->ipv6, &a6);
			merge_addr6(a6, (struct sockaddr_in6 ***)&a_list, &a_list_count);
		}
	}

	/* Last chance for a name */
	for (d = list; (cname == NULL) && (d != NULL); d = d->lu_next)
	{
		if (d->name != NULL) cname = strdup(d->name);
	}

	free_lu_dict(list);

	for (i = 0; i < a_list_count; i++)
	{
		if (a_list[i]->sa_family == PF_INET)
		{
			sa4 = (struct sockaddr_in *)a_list[i];
			a = new_addrinfo_v4(0, 0, 0, 0, sa4->sin_addr, NULL);
			append_addrinfo(res, a);
		}
		else if (a_list[i]->sa_family == PF_INET6)
		{
			sa6 = (struct sockaddr_in6 *)a_list[i];
			a = new_addrinfo_v6(0, 0, 0, 0, sa6->sin6_addr, NULL);
			append_addrinfo(res, a);
		}

		free(a_list[i]);
	}

	if (a_list_count > 0) free(a_list);

	/* Set cname in first result */
	if ((setcname == 1) && (*res != NULL))
	{
		if (res[0]->ai_canonname == NULL)
		{
			res[0]->ai_canonname = cname;
			cname = NULL;
		}
	}
	
	if (cname != NULL) free(cname);

	return 0;
}

/*
 * Find a service+node.
 */
static void
gai_nodeserv_lookupd(const char *nodename, const char *servname, const struct addrinfo *hints, struct lu_dict **list)
{
	struct lu_dict q, *sub;
	int proto, family;

	family = PF_UNSPEC;
	proto = IPPROTO_UNSPEC;

	if (hints != NULL)
	{
		if (hints->ai_flags & AI_NUMERICHOST) return;
		family = hints->ai_family;

		proto = hints->ai_protocol;
		if (hints->ai_socktype == SOCK_DGRAM) proto = IPPROTO_UDP;
		if (hints->ai_socktype == SOCK_STREAM) proto = IPPROTO_TCP;
	}

	memset(&q, 0, sizeof(struct lu_dict));
	q.count = 4;
	q.type = "host";

	grok_nodename(nodename, family, &q);
	grok_service(servname, &q);

	if ((proto == IPPROTO_UNSPEC) || (proto == IPPROTO_UDP))
	{
		sub = NULL;
		q.protocol = "udp";
		gai_lookupd(&q, &sub);
		append_lu_dict(list, sub);
		for (; sub != NULL; sub = sub->lu_next) sub->protocol = strdup("udp");
	}

	if ((proto == IPPROTO_UNSPEC) || (proto == IPPROTO_TCP))
	{
		sub = NULL;
		q.protocol = "tcp";
		gai_lookupd(&q, &sub);
		append_lu_dict(list, sub);
		for (; sub != NULL; sub = sub->lu_next) sub->protocol = strdup("tcp");
	}
}

static void
gai_node_pp(const char *nodename, unsigned short port, int proto, int family, int setcname, struct addrinfo **res)
{
	struct lu_dict *list, *d;
	int i, wantv4, wantv6, a_list_count, socktype;
	char *cname;
	struct sockaddr **a_list;
	struct in_addr a4;
	struct in6_addr a6;
	struct sockaddr_in *sa4;
	struct sockaddr_in6 *sa6;
	struct addrinfo *a;

	socktype = SOCK_UNSPEC;
	if (proto == IPPROTO_UDP) socktype = SOCK_DGRAM;
	if (proto == IPPROTO_TCP) socktype = SOCK_STREAM;

	cname = NULL;

	wantv4 = 1;
	wantv6 = 1;
	if (family == PF_INET6) wantv4 = 0;
	if (family == PF_INET) wantv6 = 0;

	/* Resolve node name */
	list = NULL;
	gai_node_lookupd(nodename, family, 0, &list);
	if (list == NULL)
	{
		gai_node_lookupd(nodename, family, 1, &list);
	}

	/* Resolve aliases */
	for (d = list; d != NULL; d = d->lu_next)
	{
		if (d->cname != NULL)
		{
			if (cname == NULL) cname = strdup(d->cname);
			gai_node_lookupd(d->cname, family, 0, &list);
		}
	}

	a_list_count = 0;

	for (d = list; d != NULL; d = d->lu_next)
	{
		/* Check for cname */
		if ((cname == NULL) && (d->name != NULL) && (strchr(d->name, '.') != NULL))
		{
			cname = strdup(d->name);
		}

		/* Check for ipv4 address */
		if ((d->ipv4 != NULL) && (wantv4 == 1))
		{
			inet_aton(d->ipv4, &a4);
			merge_addr4(a4, (struct sockaddr_in ***)&a_list, &a_list_count);
		}

		/* Check for ipv6 address */
		if ((d->ipv6 != NULL) && (wantv6 == 1))
		{
			gai_inet_pton(d->ipv6, &a6);
			merge_addr6(a6, (struct sockaddr_in6 ***)&a_list, &a_list_count);
		}
	}

	free_lu_dict(list);
	
	for (i = 0; i < a_list_count; i++)
	{
		if (a_list[i]->sa_family == PF_INET)
		{
			sa4 = (struct sockaddr_in *)a_list[i];
			a = new_addrinfo_v4(0, socktype, proto, port, sa4->sin_addr, NULL);
			append_addrinfo(res, a);
		}
		else if (a_list[i]->sa_family == PF_INET6)
		{
			sa6 = (struct sockaddr_in6 *)a_list[i];
			a = new_addrinfo_v6(0, socktype, proto, port, sa6->sin6_addr, NULL);
			append_addrinfo(res, a);
		}

		free(a_list[i]);
	}

	if (a_list_count > 0) free(a_list);

	/* Set cname in first result */
	if ((setcname == 1) && (*res != NULL))
	{
		if (res[0]->ai_canonname == NULL)
		{
			res[0]->ai_canonname = cname;
			cname = NULL;
		}
	}
	
	if (cname != NULL) free(cname);
}

static int
gai_nodeserv(const char *nodename, const char *servname, const struct addrinfo *hints, struct addrinfo **res)
{
	struct lu_dict *srv_list, *node_list, *s, *n;
	int numerichost, family, proto, setcname;
	int wantv4, wantv6, i, j, gotmx, p_list_count;
	unsigned short port;
	char *cname;
	struct sockaddr **p_list;
	struct sockaddr_in *sa4;

	numerichost = 0;
	family = PF_UNSPEC;
	proto = IPPROTO_UNSPEC;
	setcname = 0;
	cname = NULL;
	wantv4 = 1;
	wantv6 = 1;

	if (hints != NULL)
	{
		family = hints->ai_family;
		if (hints->ai_flags & AI_NUMERICHOST) numerichost = 1;
		if (hints->ai_flags & AI_CANONNAME) setcname = 1;

		proto = hints->ai_protocol;
		if (hints->ai_socktype == SOCK_DGRAM) proto = IPPROTO_UDP;
		if (hints->ai_socktype == SOCK_STREAM) proto = IPPROTO_TCP;
	}

	if (family == PF_INET6) wantv4 = 0;
	if (family == PF_INET) wantv6 = 0;

	/* First check for this particular host / service (e.g. DNS_SRV) */

	srv_list = NULL;
	gai_nodeserv_lookupd(nodename, servname, hints, &srv_list);
	lu_prioity_sort(&srv_list);

	if (srv_list != NULL)
	{
		for (s = srv_list; s != NULL; s = s->lu_next)
		{
			if (s->port == NULL) continue;
			if (s->protocol == NULL) continue;

			i = htons(atoi(s->port));
			j = IPPROTO_UDP;
			if (!strcmp(s->protocol, "tcp")) j = IPPROTO_TCP;
			gai_node_pp(s->target, i, j, family, setcname, res);
		}

		free_lu_dict(srv_list);
		return 0;
	}

	/*
	 * Special case for smtp: collect mail_exchangers.
	 */
	gotmx = 0;
	node_list = NULL;

	if (!strcmp(servname, "smtp"))
	{
		gai_node_lookupd(nodename, family, numerichost, &node_list);
		if ((node_list == NULL) && (numerichost == 0))
		{
			gai_node_lookupd(nodename, family, 1, &node_list);
		}

		lu_prioity_sort(&node_list);

		for (n = node_list; (n != NULL) && (gotmx == 0); n = n->lu_next)
		{
			if (n->mx != NULL) gotmx = 1;
		}

		if ((gotmx == 0) && (node_list != NULL))
		{
			free_lu_dict(node_list);
			node_list = NULL;
		}
	}

	/*
	 * Look up service, look up node, and combine port/proto with node addresses.
	 */
	srv_list = NULL;
	gai_serv_lookupd(servname, proto, 0, &srv_list);
	if (srv_list == NULL) gai_serv_lookupd(servname, proto, 1, &srv_list);
	if (srv_list == NULL) return 0;

	p_list_count = 0;
	for (s = srv_list; s != NULL; s = s->lu_next)
	{
		if (s->port == NULL) continue;
		if (s->protocol == NULL) continue;

		i = htons(atoi(s->port));
		j = IPPROTO_UDP;
		if (!strcmp(s->protocol, "tcp")) j = IPPROTO_TCP;

		merge_plist(i, j, (struct sockaddr_in ***)&p_list, &p_list_count);
	}

	free_lu_dict(srv_list);
	
	for (i = 0; i < p_list_count; i++)
	{
		sa4 = (struct sockaddr_in *)p_list[i];
		port = sa4->sin_port;
		/* N.B. sin_family is overloaded */
		proto = sa4->sin_family;

		if (gotmx == 1)
		{
			for (n = node_list; n != NULL; n = n->lu_next)
			{
				if (n->mx != NULL) gai_node_pp(n->mx, port, proto, family, setcname, res);
			}
		}
		else
		{
			gai_node_pp(nodename, port, proto, family, setcname, res);
		}

		free(p_list[i]);
	}

	if (node_list != NULL) free_lu_dict(node_list);

	if (p_list_count > 0) free(p_list);
	return 0;
}

int
getaddrinfo(const char *nodename, const char *servname, const struct addrinfo *hints, struct addrinfo **res)
{
	int status;
	struct lu_dict *list;

	if (res == NULL) return 0;
	*res = NULL;
	list = NULL;

	/* Check input */
	if ((nodename == NULL) && (servname == NULL)) return EAI_NONAME;

	/* Check hints */
	if (hints != NULL)
	{
		if (hints->ai_addrlen != 0) return EAI_BADHINTS;
		if (hints->ai_canonname != NULL) return EAI_BADHINTS;
		if (hints->ai_addr != NULL) return EAI_BADHINTS;
		if (hints->ai_next != NULL) return EAI_BADHINTS;

		/* Check for supported protocol family */
		if (gai_family_type_check(hints->ai_family) != 0) return EAI_FAMILY;

		/* Check for supported socket */
		if (gai_socket_type_check(hints->ai_socktype) != 0) return EAI_BADHINTS;

		/* Check for supported protocol */
		if (gai_protocol_type_check(hints->ai_protocol) != 0) return EAI_BADHINTS;

		/* Check that socket type is compatible with protocol */
		if (gai_socket_protocol_type_check(hints->ai_socktype, hints->ai_protocol) != 0) return EAI_BADHINTS;
	}

	status = 0;

	if (nodename == NULL)
	{
		/* If node is NULL, find service */
		status = gai_serv(servname, hints, res);
		if ((status == 0) && (*res == NULL)) status = EAI_NODATA;
		return status;
	}

	if (servname == NULL)
	{
		/* If service is NULL, find node */
		status = gai_node(nodename, hints, res);
		if ((status == 0) && (*res == NULL)) status = EAI_NODATA;
		return status;
	}

	/* Find node + service */
	status = gai_nodeserv(nodename, servname, hints, res);
	if ((status == 0) && (*res == NULL)) status = EAI_NODATA;
	return status;
}