1/*	$KAME: name6.c,v 1.25 2000/06/26 16:44:40 itojun Exp $	*/
2
3/*-
4 * SPDX-License-Identifier: BSD-3-Clause
5 *
6 * Copyright (C) 1995, 1996, 1997, 1998, and 1999 WIDE Project.
7 * All rights reserved.
8 *
9 * Redistribution and use in source and binary forms, with or without
10 * modification, are permitted provided that the following conditions
11 * are met:
12 * 1. Redistributions of source code must retain the above copyright
13 *    notice, this list of conditions and the following disclaimer.
14 * 2. Redistributions in binary form must reproduce the above copyright
15 *    notice, this list of conditions and the following disclaimer in the
16 *    documentation and/or other materials provided with the distribution.
17 * 3. Neither the name of the project nor the names of its contributors
18 *    may be used to endorse or promote products derived from this software
19 *    without specific prior written permission.
20 *
21 * THIS SOFTWARE IS PROVIDED BY THE PROJECT AND CONTRIBUTORS ``AS IS'' AND
22 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
23 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
24 * ARE DISCLAIMED.  IN NO EVENT SHALL THE PROJECT OR CONTRIBUTORS BE LIABLE
25 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
26 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
27 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
28 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
29 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
30 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
31 * SUCH DAMAGE.
32 */
33/*
34 * ++Copyright++ 1985, 1988, 1993
35 * -
36 * Copyright (c) 1985, 1988, 1993
37 *    The Regents of the University of California.  All rights reserved.
38 *
39 * Redistribution and use in source and binary forms, with or without
40 * modification, are permitted provided that the following conditions
41 * are met:
42 * 1. Redistributions of source code must retain the above copyright
43 *    notice, this list of conditions and the following disclaimer.
44 * 2. Redistributions in binary form must reproduce the above copyright
45 *    notice, this list of conditions and the following disclaimer in the
46 *    documentation and/or other materials provided with the distribution.
47 * 3. Neither the name of the University nor the names of its contributors
48 *    may be used to endorse or promote products derived from this software
49 *    without specific prior written permission.
50 *
51 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
52 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
53 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
54 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
55 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
56 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
57 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
58 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
59 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
60 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
61 * SUCH DAMAGE.
62 * -
63 * Portions Copyright (c) 1993 by Digital Equipment Corporation.
64 *
65 * Permission to use, copy, modify, and distribute this software for any
66 * purpose with or without fee is hereby granted, provided that the above
67 * copyright notice and this permission notice appear in all copies, and that
68 * the name of Digital Equipment Corporation not be used in advertising or
69 * publicity pertaining to distribution of the document or software without
70 * specific, written prior permission.
71 *
72 * THE SOFTWARE IS PROVIDED "AS IS" AND DIGITAL EQUIPMENT CORP. DISCLAIMS ALL
73 * WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES
74 * OF MERCHANTABILITY AND FITNESS.   IN NO EVENT SHALL DIGITAL EQUIPMENT
75 * CORPORATION BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL
76 * DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR
77 * PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS
78 * ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
79 * SOFTWARE.
80 * -
81 * --Copyright--
82 */
83
84/*
85 *	Atsushi Onoe <onoe@sm.sony.co.jp>
86 */
87
88#include <sys/cdefs.h>
89__FBSDID("$FreeBSD$");
90
91#include "namespace.h"
92#include <sys/param.h>
93#include <sys/socket.h>
94#include <sys/time.h>
95#include <sys/queue.h>
96#include <netinet/in.h>
97#ifdef INET6
98#include <net/if.h>
99#include <sys/sysctl.h>
100#include <sys/ioctl.h>
101#include <netinet6/in6_var.h>	/* XXX */
102#endif
103
104#include <arpa/inet.h>
105#include <arpa/nameser.h>
106
107#include <errno.h>
108#include <netdb.h>
109#include <resolv.h>
110#include <stdio.h>
111#include <stdlib.h>
112#include <string.h>
113#include <stdarg.h>
114#include <nsswitch.h>
115#include <unistd.h>
116#include "un-namespace.h"
117#include "netdb_private.h"
118#include "res_private.h"
119
120#ifndef MAXALIASES
121#define	MAXALIASES	10
122#endif
123#ifndef	MAXADDRS
124#define	MAXADDRS	20
125#endif
126#ifndef MAXDNAME
127#define	MAXDNAME	1025
128#endif
129
130#ifdef INET6
131#define	ADDRLEN(af)	((af) == AF_INET6 ? sizeof(struct in6_addr) : \
132					    sizeof(struct in_addr))
133#else
134#define	ADDRLEN(af)	sizeof(struct in_addr)
135#endif
136
137#define	MAPADDR(ab, ina) \
138do {									\
139	memcpy(&(ab)->map_inaddr, ina, sizeof(struct in_addr));		\
140	memset((ab)->map_zero, 0, sizeof((ab)->map_zero));		\
141	memset((ab)->map_one, 0xff, sizeof((ab)->map_one));		\
142} while (0)
143#define	MAPADDRENABLED(flags) \
144	(((flags) & AI_V4MAPPED) || \
145	 (((flags) & AI_V4MAPPED_CFG)))
146
147union inx_addr {
148	struct in_addr	in_addr;
149#ifdef INET6
150	struct in6_addr	in6_addr;
151#endif
152	struct {
153		u_char	mau_zero[10];
154		u_char	mau_one[2];
155		struct in_addr mau_inaddr;
156	}		map_addr_un;
157#define	map_zero	map_addr_un.mau_zero
158#define	map_one		map_addr_un.mau_one
159#define	map_inaddr	map_addr_un.mau_inaddr
160};
161
162struct policyqueue {
163	TAILQ_ENTRY(policyqueue) pc_entry;
164#ifdef INET6
165	struct in6_addrpolicy pc_policy;
166#endif
167};
168TAILQ_HEAD(policyhead, policyqueue);
169
170#define AIO_SRCFLAG_DEPRECATED	0x1
171
172struct hp_order {
173	union {
174		struct sockaddr_storage aiou_ss;
175		struct sockaddr aiou_sa;
176	} aio_src_un;
177#define aio_srcsa aio_src_un.aiou_sa
178	u_int32_t aio_srcflag;
179	int aio_srcscope;
180	int aio_dstscope;
181	struct policyqueue *aio_srcpolicy;
182	struct policyqueue *aio_dstpolicy;
183	union {
184		struct sockaddr_storage aiou_ss;
185		struct sockaddr aiou_sa;
186	} aio_un;
187#define aio_sa aio_un.aiou_sa
188	int aio_matchlen;
189	char *aio_h_addr;
190	int aio_initial_sequence;
191};
192
193static struct	 hostent *_hpcopy(struct hostent *, int *);
194static struct	 hostent *_hpaddr(int, const char *, void *, int *);
195#ifdef INET6
196static struct	 hostent *_hpmerge(struct hostent *, struct hostent *, int *);
197static struct	 hostent *_hpmapv6(struct hostent *, int *);
198#endif
199static struct	 hostent *_hpsort(struct hostent *, res_state);
200
201#ifdef INET6
202static struct	 hostent *_hpreorder(struct hostent *);
203static int	 get_addrselectpolicy(struct policyhead *);
204static void	 free_addrselectpolicy(struct policyhead *);
205static struct	 policyqueue *match_addrselectpolicy(struct sockaddr *,
206	struct policyhead *);
207static void	 set_source(struct hp_order *, struct policyhead *);
208static int	 matchlen(struct sockaddr *, struct sockaddr *);
209static int	 comp_dst(const void *, const void *);
210static int	 gai_addr2scopetype(struct sockaddr *);
211#endif
212
213/*
214 * Functions defined in RFC2553
215 *	getipnodebyname, getipnodebyaddr, freehostent
216 */
217
218struct hostent *
219getipnodebyname(const char *name, int af, int flags, int *errp)
220{
221	struct hostent *hp;
222	union inx_addr addrbuf;
223	res_state statp;
224	u_long options;
225
226	switch (af) {
227	case AF_INET:
228#ifdef INET6
229	case AF_INET6:
230#endif
231		break;
232	default:
233		*errp = NO_RECOVERY;
234		return NULL;
235	}
236
237	if (flags & AI_ADDRCONFIG) {
238		int s;
239
240		if ((s = _socket(af, SOCK_DGRAM | SOCK_CLOEXEC, 0)) < 0)
241			return NULL;
242		/*
243		 * TODO:
244		 * Note that implementation dependent test for address
245		 * configuration should be done every time called
246		 * (or appropriate interval),
247		 * because addresses will be dynamically assigned or deleted.
248		 */
249		_close(s);
250	}
251
252#ifdef INET6
253	/* special case for literal address */
254	if (inet_pton(AF_INET6, name, &addrbuf) == 1) {
255		if (af != AF_INET6) {
256			*errp = HOST_NOT_FOUND;
257			return NULL;
258		}
259		return _hpaddr(af, name, &addrbuf, errp);
260	}
261#endif
262	if (inet_aton(name, (struct in_addr *)&addrbuf) == 1) {
263		if (af != AF_INET) {
264			if (MAPADDRENABLED(flags)) {
265				MAPADDR(&addrbuf, &addrbuf.in_addr);
266			} else {
267				*errp = HOST_NOT_FOUND;
268				return NULL;
269			}
270		}
271		return _hpaddr(af, name, &addrbuf, errp);
272	}
273
274
275	statp = __res_state();
276	if ((statp->options & RES_INIT) == 0) {
277		if (res_ninit(statp) < 0) {
278			*errp = NETDB_INTERNAL;
279			return NULL;
280		}
281	}
282
283	options = statp->options;
284	statp->options &= ~RES_USE_INET6;
285
286	hp = gethostbyname2(name, af);
287	hp = _hpcopy(hp, errp);
288#ifdef INET6
289	if (af == AF_INET6)
290		hp = _hpreorder(hp);
291
292	if (af == AF_INET6 && ((flags & AI_ALL) || hp == NULL) &&
293	    MAPADDRENABLED(flags)) {
294		struct hostent *hp2 = gethostbyname2(name, AF_INET);
295		if (hp == NULL)
296			if (hp2 == NULL)
297				*errp = statp->res_h_errno;
298			else
299				hp = _hpmapv6(hp2, errp);
300		else {
301			if (hp2 && strcmp(hp->h_name, hp2->h_name) == 0) {
302				struct hostent *hpb = hp;
303				hp = _hpmerge(hpb, hp2, errp);
304				freehostent(hpb);
305			}
306		}
307	}
308#endif
309
310	if (hp == NULL)
311		*errp = statp->res_h_errno;
312
313	statp->options = options;
314	return _hpsort(hp, statp);
315}
316
317struct hostent *
318getipnodebyaddr(const void *src, size_t len, int af, int *errp)
319{
320	struct hostent *hp;
321	res_state statp;
322	u_long options;
323
324#ifdef INET6
325	struct in6_addr addrbuf;
326#else
327	struct in_addr addrbuf;
328#endif
329
330	switch (af) {
331	case AF_INET:
332		if (len != sizeof(struct in_addr)) {
333			*errp = NO_RECOVERY;
334			return NULL;
335		}
336		if (rounddown2((long)src, sizeof(struct in_addr))) {
337			memcpy(&addrbuf, src, len);
338			src = &addrbuf;
339		}
340		if (((struct in_addr *)src)->s_addr == 0)
341			return NULL;
342		break;
343#ifdef INET6
344	case AF_INET6:
345		if (len != sizeof(struct in6_addr)) {
346			*errp = NO_RECOVERY;
347			return NULL;
348		}
349		if (rounddown2((long)src, sizeof(struct in6_addr) / 2)) {
350			/* XXX */
351			memcpy(&addrbuf, src, len);
352			src = &addrbuf;
353		}
354		if (IN6_IS_ADDR_UNSPECIFIED((struct in6_addr *)src))
355			return NULL;
356		if (IN6_IS_ADDR_V4MAPPED((struct in6_addr *)src)
357		||  IN6_IS_ADDR_V4COMPAT((struct in6_addr *)src)) {
358			src = (char *)src +
359			    (sizeof(struct in6_addr) - sizeof(struct in_addr));
360			af = AF_INET;
361			len = sizeof(struct in_addr);
362		}
363		break;
364#endif
365	default:
366		*errp = NO_RECOVERY;
367		return NULL;
368	}
369
370	statp = __res_state();
371	if ((statp->options & RES_INIT) == 0) {
372		if (res_ninit(statp) < 0) {
373			RES_SET_H_ERRNO(statp, NETDB_INTERNAL);
374			return NULL;
375		}
376	}
377
378	options = statp->options;
379	statp->options &= ~RES_USE_INET6;
380
381	hp = gethostbyaddr(src, len, af);
382	if (hp == NULL)
383		*errp = statp->res_h_errno;
384
385	statp->options = options;
386	return (_hpcopy(hp, errp));
387}
388
389void
390freehostent(struct hostent *ptr)
391{
392	free(ptr);
393}
394
395/*
396 * Private utility functions
397 */
398
399/*
400 * _hpcopy: allocate and copy hostent structure
401 */
402static struct hostent *
403_hpcopy(struct hostent *hp, int *errp)
404{
405	struct hostent *nhp;
406	char *cp, **pp;
407	int size, addrsize;
408	int nalias = 0, naddr = 0;
409	int al_off;
410	int i;
411
412	if (hp == NULL)
413		return hp;
414
415	/* count size to be allocated */
416	size = sizeof(struct hostent);
417	if (hp->h_name != NULL)
418		size += strlen(hp->h_name) + 1;
419	if ((pp = hp->h_aliases) != NULL) {
420		for (i = 0; *pp != NULL; i++, pp++) {
421			if (**pp != '\0') {
422				size += strlen(*pp) + 1;
423				nalias++;
424			}
425		}
426	}
427	/* adjust alignment */
428	size = ALIGN(size);
429	al_off = size;
430	size += sizeof(char *) * (nalias + 1);
431	addrsize = ALIGN(hp->h_length);
432	if ((pp = hp->h_addr_list) != NULL) {
433		while (*pp++ != NULL)
434			naddr++;
435	}
436	size += addrsize * naddr;
437	size += sizeof(char *) * (naddr + 1);
438
439	/* copy */
440	if ((nhp = (struct hostent *)malloc(size)) == NULL) {
441		*errp = TRY_AGAIN;
442		return NULL;
443	}
444	cp = (char *)&nhp[1];
445	if (hp->h_name != NULL) {
446		nhp->h_name = cp;
447		strcpy(cp, hp->h_name);
448		cp += strlen(cp) + 1;
449	} else
450		nhp->h_name = NULL;
451	nhp->h_aliases = (char **)((char *)nhp + al_off);
452	if ((pp = hp->h_aliases) != NULL) {
453		for (i = 0; *pp != NULL; pp++) {
454			if (**pp != '\0') {
455				nhp->h_aliases[i++] = cp;
456				strcpy(cp, *pp);
457				cp += strlen(cp) + 1;
458			}
459		}
460	}
461	nhp->h_aliases[nalias] = NULL;
462	cp = (char *)&nhp->h_aliases[nalias + 1];
463	nhp->h_addrtype = hp->h_addrtype;
464	nhp->h_length = hp->h_length;
465	nhp->h_addr_list = (char **)cp;
466	if ((pp = hp->h_addr_list) != NULL) {
467		cp = (char *)&nhp->h_addr_list[naddr + 1];
468		for (i = 0; *pp != NULL; pp++) {
469			nhp->h_addr_list[i++] = cp;
470			memcpy(cp, *pp, hp->h_length);
471			cp += addrsize;
472		}
473	}
474	nhp->h_addr_list[naddr] = NULL;
475	return nhp;
476}
477
478/*
479 * _hpaddr: construct hostent structure with one address
480 */
481static struct hostent *
482_hpaddr(int af, const char *name, void *addr, int *errp)
483{
484	struct hostent *hp, hpbuf;
485	char *addrs[2];
486
487	hp = &hpbuf;
488	hp->h_name = (char *)name;
489	hp->h_aliases = NULL;
490	hp->h_addrtype = af;
491	hp->h_length = ADDRLEN(af);
492	hp->h_addr_list = addrs;
493	addrs[0] = (char *)addr;
494	addrs[1] = NULL;
495	return (_hpcopy(hp, errp));
496}
497
498#ifdef INET6
499/*
500 * _hpmerge: merge 2 hostent structure, arguments will be freed
501 */
502static struct hostent *
503_hpmerge(struct hostent *hp1, struct hostent *hp2, int *errp)
504{
505	int i, j;
506	int naddr, nalias;
507	char **pp;
508	struct hostent *hp, hpbuf;
509	char *aliases[MAXALIASES + 1], *addrs[MAXADDRS + 1];
510	union inx_addr addrbuf[MAXADDRS];
511
512	if (hp1 == NULL)
513		return _hpcopy(hp2, errp);
514	if (hp2 == NULL)
515		return _hpcopy(hp1, errp);
516
517#define	HP(i)	(i == 1 ? hp1 : hp2)
518	hp = &hpbuf;
519	hp->h_name = (hp1->h_name != NULL ? hp1->h_name : hp2->h_name);
520	hp->h_aliases = aliases;
521	nalias = 0;
522	for (i = 1; i <= 2; i++) {
523		if ((pp = HP(i)->h_aliases) == NULL)
524			continue;
525		for (; nalias < MAXALIASES && *pp != NULL; pp++) {
526			/* check duplicates */
527			for (j = 0; j < nalias; j++)
528				if (strcasecmp(*pp, aliases[j]) == 0)
529					break;
530			if (j == nalias)
531				aliases[nalias++] = *pp;
532		}
533	}
534	aliases[nalias] = NULL;
535	if (hp1->h_length != hp2->h_length) {
536		hp->h_addrtype = AF_INET6;
537		hp->h_length = sizeof(struct in6_addr);
538	} else {
539		hp->h_addrtype = hp1->h_addrtype;
540		hp->h_length = hp1->h_length;
541	}
542
543	hp->h_addr_list = addrs;
544	naddr = 0;
545	for (i = 1; i <= 2; i++) {
546		if ((pp = HP(i)->h_addr_list) == NULL)
547			continue;
548		if (HP(i)->h_length == hp->h_length) {
549			while (naddr < MAXADDRS && *pp != NULL)
550				addrs[naddr++] = *pp++;
551		} else {
552			/* copy IPv4 addr as mapped IPv6 addr */
553			while (naddr < MAXADDRS && *pp != NULL) {
554				MAPADDR(&addrbuf[naddr], *pp++);
555				addrs[naddr] = (char *)&addrbuf[naddr];
556				naddr++;
557			}
558		}
559	}
560	addrs[naddr] = NULL;
561	return (_hpcopy(hp, errp));
562}
563#endif
564
565/*
566 * _hpmapv6: convert IPv4 hostent into IPv4-mapped IPv6 addresses
567 */
568#ifdef INET6
569static struct hostent *
570_hpmapv6(struct hostent *hp, int *errp)
571{
572	struct hostent hp6;
573
574	if (hp == NULL)
575		return NULL;
576	if (hp->h_addrtype == AF_INET6)
577		return _hpcopy(hp, errp);
578
579	memset(&hp6, 0, sizeof(struct hostent));
580	hp6.h_addrtype = AF_INET6;
581	hp6.h_length = sizeof(struct in6_addr);
582	return _hpmerge(&hp6, hp, errp);
583}
584#endif
585
586/*
587 * _hpsort: sort address by sortlist
588 */
589static struct hostent *
590_hpsort(struct hostent *hp, res_state statp)
591{
592	int i, j, n;
593	u_char *ap, *sp, *mp, **pp;
594	char t;
595	char order[MAXADDRS];
596	int nsort = statp->nsort;
597
598	if (hp == NULL || hp->h_addr_list[1] == NULL || nsort == 0)
599		return hp;
600	for (i = 0; (ap = (u_char *)hp->h_addr_list[i]); i++) {
601		for (j = 0; j < nsort; j++) {
602#ifdef INET6
603			if (statp->_u._ext.ext->sort_list[j].af !=
604			    hp->h_addrtype)
605				continue;
606			sp = (u_char *)&statp->_u._ext.ext->sort_list[j].addr;
607			mp = (u_char *)&statp->_u._ext.ext->sort_list[j].mask;
608#else
609			sp = (u_char *)&statp->sort_list[j].addr;
610			mp = (u_char *)&statp->sort_list[j].mask;
611#endif
612			for (n = 0; n < hp->h_length; n++) {
613				if ((ap[n] & mp[n]) != sp[n])
614					break;
615			}
616			if (n == hp->h_length)
617				break;
618		}
619		order[i] = j;
620	}
621	n = i;
622	pp = (u_char **)hp->h_addr_list;
623	for (i = 0; i < n - 1; i++) {
624		for (j = i + 1; j < n; j++) {
625			if (order[i] > order[j]) {
626				ap = pp[i];
627				pp[i] = pp[j];
628				pp[j] = ap;
629				t = order[i];
630				order[i] = order[j];
631				order[j] = t;
632			}
633		}
634	}
635	return hp;
636}
637
638#ifdef INET6
639/*
640 * _hpreorder: sort address by default address selection
641 */
642static struct hostent *
643_hpreorder(struct hostent *hp)
644{
645	struct hp_order *aio;
646	int i, n;
647	char *ap;
648	struct sockaddr *sa;
649	struct policyhead policyhead;
650
651	if (hp == NULL)
652		return hp;
653
654	switch (hp->h_addrtype) {
655	case AF_INET:
656#ifdef INET6
657	case AF_INET6:
658#endif
659		break;
660	default:
661		return hp;
662	}
663
664	/* count the number of addrinfo elements for sorting. */
665	for (n = 0; hp->h_addr_list[n] != NULL; n++)
666		;
667
668	/*
669	 * If the number is small enough, we can skip the reordering process.
670	 */
671	if (n <= 1)
672		return hp;
673
674	/* allocate a temporary array for sort and initialization of it. */
675	if ((aio = malloc(sizeof(*aio) * n)) == NULL)
676		return hp;	/* give up reordering */
677	memset(aio, 0, sizeof(*aio) * n);
678
679	/* retrieve address selection policy from the kernel */
680	TAILQ_INIT(&policyhead);
681	if (!get_addrselectpolicy(&policyhead)) {
682		/* no policy is installed into kernel, we don't sort. */
683		free(aio);
684		return hp;
685	}
686
687	for (i = 0; i < n; i++) {
688		ap = hp->h_addr_list[i];
689		aio[i].aio_h_addr = ap;
690		sa = &aio[i].aio_sa;
691		switch (hp->h_addrtype) {
692		case AF_INET:
693			sa->sa_family = AF_INET;
694			sa->sa_len = sizeof(struct sockaddr_in);
695			memcpy(&((struct sockaddr_in *)sa)->sin_addr, ap,
696			    sizeof(struct in_addr));
697			break;
698#ifdef INET6
699		case AF_INET6:
700			if (IN6_IS_ADDR_V4MAPPED((struct in6_addr *)ap)) {
701				sa->sa_family = AF_INET;
702				sa->sa_len = sizeof(struct sockaddr_in);
703				memcpy(&((struct sockaddr_in *)sa)->sin_addr,
704				    &ap[12], sizeof(struct in_addr));
705			} else {
706				sa->sa_family = AF_INET6;
707				sa->sa_len = sizeof(struct sockaddr_in6);
708				memcpy(&((struct sockaddr_in6 *)sa)->sin6_addr,
709				    ap, sizeof(struct in6_addr));
710			}
711			break;
712#endif
713		}
714		aio[i].aio_dstscope = gai_addr2scopetype(sa);
715		aio[i].aio_dstpolicy = match_addrselectpolicy(sa, &policyhead);
716		set_source(&aio[i], &policyhead);
717		aio[i].aio_initial_sequence = i;
718	}
719
720	/* perform sorting. */
721	qsort(aio, n, sizeof(*aio), comp_dst);
722
723	/* reorder the h_addr_list. */
724	for (i = 0; i < n; i++)
725		hp->h_addr_list[i] = aio[i].aio_h_addr;
726
727	/* cleanup and return */
728	free(aio);
729	free_addrselectpolicy(&policyhead);
730	return hp;
731}
732
733static int
734get_addrselectpolicy(struct policyhead *head)
735{
736#ifdef INET6
737	int mib[] = { CTL_NET, PF_INET6, IPPROTO_IPV6, IPV6CTL_ADDRCTLPOLICY };
738	size_t l;
739	char *buf;
740	struct in6_addrpolicy *pol, *ep;
741
742	if (sysctl(mib, nitems(mib), NULL, &l, NULL, 0) < 0)
743		return (0);
744	if ((buf = malloc(l)) == NULL)
745		return (0);
746	if (sysctl(mib, nitems(mib), buf, &l, NULL, 0) < 0) {
747		free(buf);
748		return (0);
749	}
750
751	ep = (struct in6_addrpolicy *)(buf + l);
752	for (pol = (struct in6_addrpolicy *)buf; pol + 1 <= ep; pol++) {
753		struct policyqueue *new;
754
755		if ((new = malloc(sizeof(*new))) == NULL) {
756			free_addrselectpolicy(head); /* make the list empty */
757			break;
758		}
759		new->pc_policy = *pol;
760		TAILQ_INSERT_TAIL(head, new, pc_entry);
761	}
762
763	free(buf);
764	return (1);
765#else
766	return (0);
767#endif
768}
769
770static void
771free_addrselectpolicy(struct policyhead *head)
772{
773	struct policyqueue *ent, *nent;
774
775	for (ent = TAILQ_FIRST(head); ent; ent = nent) {
776		nent = TAILQ_NEXT(ent, pc_entry);
777		TAILQ_REMOVE(head, ent, pc_entry);
778		free(ent);
779	}
780}
781
782static struct policyqueue *
783match_addrselectpolicy(struct sockaddr *addr, struct policyhead *head)
784{
785#ifdef INET6
786	struct policyqueue *ent, *bestent = NULL;
787	struct in6_addrpolicy *pol;
788	int matchlen, bestmatchlen = -1;
789	u_char *mp, *ep, *k, *p, m;
790	struct sockaddr_in6 key;
791
792	switch(addr->sa_family) {
793	case AF_INET6:
794		key = *(struct sockaddr_in6 *)addr;
795		break;
796	case AF_INET:
797		/* convert the address into IPv4-mapped IPv6 address. */
798		memset(&key, 0, sizeof(key));
799		key.sin6_family = AF_INET6;
800		key.sin6_len = sizeof(key);
801		_map_v4v6_address(
802		    (char *)&((struct sockaddr_in *)addr)->sin_addr,
803		    (char *)&key.sin6_addr);
804		break;
805	default:
806		return(NULL);
807	}
808
809	for (ent = TAILQ_FIRST(head); ent; ent = TAILQ_NEXT(ent, pc_entry)) {
810		pol = &ent->pc_policy;
811		matchlen = 0;
812
813		mp = (u_char *)&pol->addrmask.sin6_addr;
814		ep = mp + 16;	/* XXX: scope field? */
815		k = (u_char *)&key.sin6_addr;
816		p = (u_char *)&pol->addr.sin6_addr;
817		for (; mp < ep && *mp; mp++, k++, p++) {
818			m = *mp;
819			if ((*k & m) != *p)
820				goto next; /* not match */
821			if (m == 0xff) /* short cut for a typical case */
822				matchlen += 8;
823			else {
824				while (m >= 0x80) {
825					matchlen++;
826					m <<= 1;
827				}
828			}
829		}
830
831		/* matched.  check if this is better than the current best. */
832		if (matchlen > bestmatchlen) {
833			bestent = ent;
834			bestmatchlen = matchlen;
835		}
836
837	  next:
838		continue;
839	}
840
841	return(bestent);
842#else
843	return(NULL);
844#endif
845
846}
847
848static void
849set_source(struct hp_order *aio, struct policyhead *ph)
850{
851	struct sockaddr_storage ss = aio->aio_un.aiou_ss;
852	socklen_t srclen;
853	int s;
854
855	/* set unspec ("no source is available"), just in case */
856	aio->aio_srcsa.sa_family = AF_UNSPEC;
857	aio->aio_srcscope = -1;
858
859	switch(ss.ss_family) {
860	case AF_INET:
861		((struct sockaddr_in *)&ss)->sin_port = htons(1);
862		break;
863#ifdef INET6
864	case AF_INET6:
865		((struct sockaddr_in6 *)&ss)->sin6_port = htons(1);
866		break;
867#endif
868	default:		/* ignore unsupported AFs explicitly */
869		return;
870	}
871
872	/* open a socket to get the source address for the given dst */
873	if ((s = _socket(ss.ss_family, SOCK_DGRAM | SOCK_CLOEXEC,
874	    IPPROTO_UDP)) < 0)
875		return;		/* give up */
876	if (_connect(s, (struct sockaddr *)&ss, ss.ss_len) < 0)
877		goto cleanup;
878	srclen = ss.ss_len;
879	if (_getsockname(s, &aio->aio_srcsa, &srclen) < 0) {
880		aio->aio_srcsa.sa_family = AF_UNSPEC;
881		goto cleanup;
882	}
883	aio->aio_srcscope = gai_addr2scopetype(&aio->aio_srcsa);
884	aio->aio_srcpolicy = match_addrselectpolicy(&aio->aio_srcsa, ph);
885	aio->aio_matchlen = matchlen(&aio->aio_srcsa, (struct sockaddr *)&ss);
886#ifdef INET6
887	if (ss.ss_family == AF_INET6) {
888		struct in6_ifreq ifr6;
889		u_int32_t flags6;
890
891		memset(&ifr6, 0, sizeof(ifr6));
892		memcpy(&ifr6.ifr_addr, &ss, ss.ss_len);
893		if (_ioctl(s, SIOCGIFAFLAG_IN6, &ifr6) == 0) {
894			flags6 = ifr6.ifr_ifru.ifru_flags6;
895			if ((flags6 & IN6_IFF_DEPRECATED))
896				aio->aio_srcflag |= AIO_SRCFLAG_DEPRECATED;
897		}
898	}
899#endif
900
901  cleanup:
902	_close(s);
903	return;
904}
905
906static int
907matchlen(struct sockaddr *src, struct sockaddr *dst)
908{
909	int match = 0;
910	u_char *s, *d;
911	u_char *lim, r;
912	int addrlen;
913
914	switch (src->sa_family) {
915#ifdef INET6
916	case AF_INET6:
917		s = (u_char *)&((struct sockaddr_in6 *)src)->sin6_addr;
918		d = (u_char *)&((struct sockaddr_in6 *)dst)->sin6_addr;
919		addrlen = sizeof(struct in6_addr);
920		lim = s + addrlen;
921		break;
922#endif
923	case AF_INET:
924		s = (u_char *)&((struct sockaddr_in *)src)->sin_addr;
925		d = (u_char *)&((struct sockaddr_in *)dst)->sin_addr;
926		addrlen = sizeof(struct in_addr);
927		lim = s + addrlen;
928		break;
929	default:
930		return(0);
931	}
932
933	while (s < lim)
934		if ((r = (*d++ ^ *s++)) != 0) {
935			while ((r & 0x80) == 0) {
936				match++;
937				r <<= 1;
938			}
939			break;
940		} else
941			match += 8;
942	return(match);
943}
944
945static int
946comp_dst(const void *arg1, const void *arg2)
947{
948	const struct hp_order *dst1 = arg1, *dst2 = arg2;
949
950	/*
951	 * Rule 1: Avoid unusable destinations.
952	 * XXX: we currently do not consider if an appropriate route exists.
953	 */
954	if (dst1->aio_srcsa.sa_family != AF_UNSPEC &&
955	    dst2->aio_srcsa.sa_family == AF_UNSPEC) {
956		return(-1);
957	}
958	if (dst1->aio_srcsa.sa_family == AF_UNSPEC &&
959	    dst2->aio_srcsa.sa_family != AF_UNSPEC) {
960		return(1);
961	}
962
963	/* Rule 2: Prefer matching scope. */
964	if (dst1->aio_dstscope == dst1->aio_srcscope &&
965	    dst2->aio_dstscope != dst2->aio_srcscope) {
966		return(-1);
967	}
968	if (dst1->aio_dstscope != dst1->aio_srcscope &&
969	    dst2->aio_dstscope == dst2->aio_srcscope) {
970		return(1);
971	}
972
973	/* Rule 3: Avoid deprecated addresses. */
974	if (dst1->aio_srcsa.sa_family != AF_UNSPEC &&
975	    dst2->aio_srcsa.sa_family != AF_UNSPEC) {
976		if (!(dst1->aio_srcflag & AIO_SRCFLAG_DEPRECATED) &&
977		    (dst2->aio_srcflag & AIO_SRCFLAG_DEPRECATED)) {
978			return(-1);
979		}
980		if ((dst1->aio_srcflag & AIO_SRCFLAG_DEPRECATED) &&
981		    !(dst2->aio_srcflag & AIO_SRCFLAG_DEPRECATED)) {
982			return(1);
983		}
984	}
985
986	/* Rule 4: Prefer home addresses. */
987	/* XXX: not implemented yet */
988
989	/* Rule 5: Prefer matching label. */
990#ifdef INET6
991	if (dst1->aio_srcpolicy && dst1->aio_dstpolicy &&
992	    dst1->aio_srcpolicy->pc_policy.label ==
993	    dst1->aio_dstpolicy->pc_policy.label &&
994	    (dst2->aio_srcpolicy == NULL || dst2->aio_dstpolicy == NULL ||
995	     dst2->aio_srcpolicy->pc_policy.label !=
996	     dst2->aio_dstpolicy->pc_policy.label)) {
997		return(-1);
998	}
999	if (dst2->aio_srcpolicy && dst2->aio_dstpolicy &&
1000	    dst2->aio_srcpolicy->pc_policy.label ==
1001	    dst2->aio_dstpolicy->pc_policy.label &&
1002	    (dst1->aio_srcpolicy == NULL || dst1->aio_dstpolicy == NULL ||
1003	     dst1->aio_srcpolicy->pc_policy.label !=
1004	     dst1->aio_dstpolicy->pc_policy.label)) {
1005		return(1);
1006	}
1007#endif
1008
1009	/* Rule 6: Prefer higher precedence. */
1010#ifdef INET6
1011	if (dst1->aio_dstpolicy &&
1012	    (dst2->aio_dstpolicy == NULL ||
1013	     dst1->aio_dstpolicy->pc_policy.preced >
1014	     dst2->aio_dstpolicy->pc_policy.preced)) {
1015		return(-1);
1016	}
1017	if (dst2->aio_dstpolicy &&
1018	    (dst1->aio_dstpolicy == NULL ||
1019	     dst2->aio_dstpolicy->pc_policy.preced >
1020	     dst1->aio_dstpolicy->pc_policy.preced)) {
1021		return(1);
1022	}
1023#endif
1024
1025	/* Rule 7: Prefer native transport. */
1026	/* XXX: not implemented yet */
1027
1028	/* Rule 8: Prefer smaller scope. */
1029	if (dst1->aio_dstscope >= 0 &&
1030	    dst1->aio_dstscope < dst2->aio_dstscope) {
1031		return(-1);
1032	}
1033	if (dst2->aio_dstscope >= 0 &&
1034	    dst2->aio_dstscope < dst1->aio_dstscope) {
1035		return(1);
1036	}
1037
1038	/*
1039	 * Rule 9: Use longest matching prefix.
1040	 * We compare the match length in a same AF only.
1041	 */
1042	if (dst1->aio_sa.sa_family == dst2->aio_sa.sa_family) {
1043		if (dst1->aio_matchlen > dst2->aio_matchlen) {
1044			return(-1);
1045		}
1046		if (dst1->aio_matchlen < dst2->aio_matchlen) {
1047			return(1);
1048		}
1049	}
1050
1051	/* Rule 10: Otherwise, leave the order unchanged. */
1052
1053	/*
1054	 * Note that qsort is unstable; so, we can't return zero and
1055	 * expect the order to be unchanged.
1056	 * That also means we can't depend on the current position of
1057	 * dst2 being after dst1.  We must enforce the initial order
1058	 * with an explicit compare on the original position.
1059	 * The qsort specification requires that "When the same objects
1060	 * (consisting of width bytes, irrespective of their current
1061	 * positions in the array) are passed more than once to the
1062	 * comparison function, the results shall be consistent with one
1063	 * another."
1064	 * In other words, If A < B, then we must also return B > A.
1065	 */
1066	if (dst2->aio_initial_sequence < dst1->aio_initial_sequence)
1067		return(1);
1068
1069	return(-1);
1070}
1071
1072/*
1073 * Copy from scope.c.
1074 * XXX: we should standardize the functions and link them as standard
1075 * library.
1076 */
1077static int
1078gai_addr2scopetype(struct sockaddr *sa)
1079{
1080#ifdef INET6
1081	struct sockaddr_in6 *sa6;
1082#endif
1083	struct sockaddr_in *sa4;
1084
1085	switch(sa->sa_family) {
1086#ifdef INET6
1087	case AF_INET6:
1088		sa6 = (struct sockaddr_in6 *)sa;
1089		if (IN6_IS_ADDR_MULTICAST(&sa6->sin6_addr)) {
1090			/* just use the scope field of the multicast address */
1091			return(sa6->sin6_addr.s6_addr[2] & 0x0f);
1092		}
1093		/*
1094		 * Unicast addresses: map scope type to corresponding scope
1095		 * value defined for multcast addresses.
1096		 * XXX: hardcoded scope type values are bad...
1097		 */
1098		if (IN6_IS_ADDR_LOOPBACK(&sa6->sin6_addr))
1099			return(1); /* node local scope */
1100		if (IN6_IS_ADDR_LINKLOCAL(&sa6->sin6_addr))
1101			return(2); /* link-local scope */
1102		if (IN6_IS_ADDR_SITELOCAL(&sa6->sin6_addr))
1103			return(5); /* site-local scope */
1104		return(14);	/* global scope */
1105		break;
1106#endif
1107	case AF_INET:
1108		/*
1109		 * IPv4 pseudo scoping according to RFC 3484.
1110		 */
1111		sa4 = (struct sockaddr_in *)sa;
1112		/* IPv4 autoconfiguration addresses have link-local scope. */
1113		if (((u_char *)&sa4->sin_addr)[0] == 169 &&
1114		    ((u_char *)&sa4->sin_addr)[1] == 254)
1115			return(2);
1116		/* Private addresses have site-local scope. */
1117		if (((u_char *)&sa4->sin_addr)[0] == 10 ||
1118		    (((u_char *)&sa4->sin_addr)[0] == 172 &&
1119		     (((u_char *)&sa4->sin_addr)[1] & 0xf0) == 16) ||
1120		    (((u_char *)&sa4->sin_addr)[0] == 192 &&
1121		     ((u_char *)&sa4->sin_addr)[1] == 168))
1122			return(14);	/* XXX: It should be 5 unless NAT */
1123		/* Loopback addresses have link-local scope. */
1124		if (((u_char *)&sa4->sin_addr)[0] == 127)
1125			return(2);
1126		return(14);
1127		break;
1128	default:
1129		errno = EAFNOSUPPORT; /* is this a good error? */
1130		return(-1);
1131	}
1132}
1133#endif
1134