/*      $KAME: name6.c,v 1.25 2000/06/26 16:44:40 itojun Exp $  */

/*-
 * SPDX-License-Identifier: BSD-3-Clause
 *
 * Copyright (C) 1995, 1996, 1997, 1998, and 1999 WIDE Project.
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. Neither the name of the project nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE PROJECT AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE PROJECT OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */
/*
 * ++Copyright++ 1985, 1988, 1993
 * -
 * Copyright (c) 1985, 1988, 1993
 *    The Regents of the University of California.  All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. Neither the name of the University nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 * -
 * Portions Copyright (c) 1993 by Digital Equipment Corporation.
 *
 * Permission to use, copy, modify, and distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies, and that
 * the name of Digital Equipment Corporation not be used in advertising or
 * publicity pertaining to distribution of the document or software without
 * specific, written prior permission.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND DIGITAL EQUIPMENT CORP. DISCLAIMS ALL
 * WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS.   IN NO EVENT SHALL DIGITAL EQUIPMENT
 * CORPORATION BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL
 * DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR
 * PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS
 * ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
 * SOFTWARE.
 * -
 * --Copyright--
 */

/*
 *      Atsushi Onoe <onoe@sm.sony.co.jp>
 */

#include "namespace.h"
#include <sys/param.h>
#include <sys/socket.h>
#include <sys/time.h>
#include <sys/queue.h>
#include <netinet/in.h>
#ifdef INET6
#include <net/if.h>
#include <sys/sysctl.h>
#include <sys/ioctl.h>
#include <netinet6/in6_var.h>   /* XXX */
#endif

#include <arpa/inet.h>
#include <arpa/nameser.h>

#include <errno.h>
#include <netdb.h>
#include <resolv.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdarg.h>
#include <nsswitch.h>
#include <unistd.h>
#include "un-namespace.h"
#include "netdb_private.h"
#include "res_private.h"

#ifndef MAXALIASES
#define MAXALIASES      10
#endif
#ifndef MAXADDRS
#define MAXADDRS        20
#endif
#ifndef MAXDNAME
#define MAXDNAME        1025
#endif

#ifdef INET6
#define ADDRLEN(af)     ((af) == AF_INET6 ? sizeof(struct in6_addr) : \
                                            sizeof(struct in_addr))
#else
#define ADDRLEN(af)     sizeof(struct in_addr)
#endif

#define MAPADDR(ab, ina) \
do {                                                                    \
        memcpy(&(ab)->map_inaddr, ina, sizeof(struct in_addr));         \
        memset((ab)->map_zero, 0, sizeof((ab)->map_zero));              \
        memset((ab)->map_one, 0xff, sizeof((ab)->map_one));             \
} while (0)
#define MAPADDRENABLED(flags) \
        (((flags) & AI_V4MAPPED) || \
         (((flags) & AI_V4MAPPED_CFG)))

union inx_addr {
        struct in_addr  in_addr;
#ifdef INET6
        struct in6_addr in6_addr;
#endif
        struct {
                u_char  mau_zero[10];
                u_char  mau_one[2];
                struct in_addr mau_inaddr;
        }               map_addr_un;
#define map_zero        map_addr_un.mau_zero
#define map_one         map_addr_un.mau_one
#define map_inaddr      map_addr_un.mau_inaddr
};

struct policyqueue {
        TAILQ_ENTRY(policyqueue) pc_entry;
#ifdef INET6
        struct in6_addrpolicy pc_policy;
#endif
};
TAILQ_HEAD(policyhead, policyqueue);

#define AIO_SRCFLAG_DEPRECATED  0x1

struct hp_order {
        union {
                struct sockaddr_storage aiou_ss;
                struct sockaddr aiou_sa;
        } aio_src_un;
#define aio_srcsa aio_src_un.aiou_sa
        u_int32_t aio_srcflag;
        int aio_srcscope;
        int aio_dstscope;
        struct policyqueue *aio_srcpolicy;
        struct policyqueue *aio_dstpolicy;
        union {
                struct sockaddr_storage aiou_ss;
                struct sockaddr aiou_sa;
        } aio_un;
#define aio_sa aio_un.aiou_sa
        int aio_matchlen;
        char *aio_h_addr;
        int aio_initial_sequence;
};

static struct    hostent *_hpcopy(struct hostent *, int *);
static struct    hostent *_hpaddr(int, const char *, void *, int *);
#ifdef INET6
static struct    hostent *_hpmerge(struct hostent *, struct hostent *, int *);
static struct    hostent *_hpmapv6(struct hostent *, int *);
#endif
static struct    hostent *_hpsort(struct hostent *, res_state);

#ifdef INET6
static struct    hostent *_hpreorder(struct hostent *);
static int       get_addrselectpolicy(struct policyhead *);
static void      free_addrselectpolicy(struct policyhead *);
static struct    policyqueue *match_addrselectpolicy(struct sockaddr *,
        struct policyhead *);
static void      set_source(struct hp_order *, struct policyhead *);
static int       matchlen(struct sockaddr *, struct sockaddr *);
static int       comp_dst(const void *, const void *);
static int       gai_addr2scopetype(struct sockaddr *);
#endif

/*
 * Functions defined in RFC2553
 *      getipnodebyname, getipnodebyaddr, freehostent
 */

struct hostent *
getipnodebyname(const char *name, int af, int flags, int *errp)
{
        struct hostent *hp;
        union inx_addr addrbuf;
        res_state statp;
        u_long options;

        switch (af) {
        case AF_INET:
#ifdef INET6
        case AF_INET6:
#endif
                break;
        default:
                *errp = NO_RECOVERY;
                return NULL;
        }

        if (flags & AI_ADDRCONFIG) {
                int s;

                if ((s = _socket(af, SOCK_DGRAM | SOCK_CLOEXEC, 0)) < 0)
                        return NULL;
                /*
                 * TODO:
                 * Note that implementation dependent test for address
                 * configuration should be done every time called
                 * (or appropriate interval),
                 * because addresses will be dynamically assigned or deleted.
                 */
                _close(s);
        }
        
#ifdef INET6
        /* special case for literal address */
        if (inet_pton(AF_INET6, name, &addrbuf) == 1) {
                if (af != AF_INET6) {
                        *errp = HOST_NOT_FOUND;
                        return NULL;
                }
                return _hpaddr(af, name, &addrbuf, errp);
        }
#endif
        if (inet_aton(name, (struct in_addr *)&addrbuf) == 1) {
                if (af != AF_INET) {
                        if (MAPADDRENABLED(flags)) {
                                MAPADDR(&addrbuf, &addrbuf.in_addr);
                        } else {
                                *errp = HOST_NOT_FOUND;
                                return NULL;
                        }
                }
                return _hpaddr(af, name, &addrbuf, errp);
        }


        statp = __res_state();
        if ((statp->options & RES_INIT) == 0) {
                if (res_ninit(statp) < 0) {
                        *errp = NETDB_INTERNAL;
                        return NULL;
                }
        }
        
        options = statp->options;
        statp->options &= ~RES_USE_INET6;
        
        hp = gethostbyname2(name, af);
        hp = _hpcopy(hp, errp);
#ifdef INET6
        if (af == AF_INET6)
                hp = _hpreorder(hp);

        if (af == AF_INET6 && ((flags & AI_ALL) || hp == NULL) &&
            MAPADDRENABLED(flags)) {
                struct hostent *hp2 = gethostbyname2(name, AF_INET);
                if (hp == NULL)
                        if (hp2 == NULL)
                                *errp = statp->res_h_errno;
                        else
                                hp = _hpmapv6(hp2, errp);
                else {
                        if (hp2 && strcmp(hp->h_name, hp2->h_name) == 0) {
                                struct hostent *hpb = hp;
                                hp = _hpmerge(hpb, hp2, errp);
                                freehostent(hpb);
                        }
                }
        }
#endif
        
        if (hp == NULL)
                *errp = statp->res_h_errno;
        
        statp->options = options;
        return _hpsort(hp, statp);
}

struct hostent *
getipnodebyaddr(const void *src, size_t len, int af, int *errp)
{
        struct hostent *hp;
        res_state statp;
        u_long options;
        
#ifdef INET6
        struct in6_addr addrbuf;
#else
        struct in_addr addrbuf;
#endif
        
        switch (af) {
        case AF_INET:
                if (len != sizeof(struct in_addr)) {
                        *errp = NO_RECOVERY;
                        return NULL;
                }
                if (rounddown2((long)src, sizeof(struct in_addr))) {
                        memcpy(&addrbuf, src, len);
                        src = &addrbuf;
                }
                if (((struct in_addr *)src)->s_addr == 0)
                        return NULL;
                break;
#ifdef INET6
        case AF_INET6:
                if (len != sizeof(struct in6_addr)) {
                        *errp = NO_RECOVERY;
                        return NULL;
                }
                if (rounddown2((long)src, sizeof(struct in6_addr) / 2)) {
                        /* XXX */
                        memcpy(&addrbuf, src, len);
                        src = &addrbuf;
                }
                if (IN6_IS_ADDR_UNSPECIFIED((struct in6_addr *)src))
                        return NULL;
                if (IN6_IS_ADDR_V4MAPPED((struct in6_addr *)src)
                ||  IN6_IS_ADDR_V4COMPAT((struct in6_addr *)src)) {
                        src = (char *)src +
                            (sizeof(struct in6_addr) - sizeof(struct in_addr));
                        af = AF_INET;
                        len = sizeof(struct in_addr);
                }
                break;
#endif
        default:
                *errp = NO_RECOVERY;
                return NULL;
        }

        statp = __res_state();
        if ((statp->options & RES_INIT) == 0) {
                if (res_ninit(statp) < 0) {
                        RES_SET_H_ERRNO(statp, NETDB_INTERNAL);
                        return NULL;
                }
        }
        
        options = statp->options;
        statp->options &= ~RES_USE_INET6;

        hp = gethostbyaddr(src, len, af);
        if (hp == NULL)
                *errp = statp->res_h_errno;
        
        statp->options = options;       
        return (_hpcopy(hp, errp));
}

void
freehostent(struct hostent *ptr)
{
        free(ptr);
}

/*
 * Private utility functions
 */

/*
 * _hpcopy: allocate and copy hostent structure
 */
static struct hostent *
_hpcopy(struct hostent *hp, int *errp)
{
        struct hostent *nhp;
        char *cp, **pp;
        int size, addrsize;
        int nalias = 0, naddr = 0;
        int al_off;
        int i;

        if (hp == NULL)
                return hp;

        /* count size to be allocated */
        size = sizeof(struct hostent);
        if (hp->h_name != NULL)
                size += strlen(hp->h_name) + 1;
        if ((pp = hp->h_aliases) != NULL) {
                for (i = 0; *pp != NULL; i++, pp++) {
                        if (**pp != '\0') {
                                size += strlen(*pp) + 1;
                                nalias++;
                        }
                }
        }
        /* adjust alignment */
        size = ALIGN(size);
        al_off = size;
        size += sizeof(char *) * (nalias + 1);
        addrsize = ALIGN(hp->h_length);
        if ((pp = hp->h_addr_list) != NULL) {
                while (*pp++ != NULL)
                        naddr++;
        }
        size += addrsize * naddr;
        size += sizeof(char *) * (naddr + 1);

        /* copy */
        if ((nhp = (struct hostent *)malloc(size)) == NULL) {
                *errp = TRY_AGAIN;
                return NULL;
        }
        cp = (char *)&nhp[1];
        if (hp->h_name != NULL) {
                nhp->h_name = cp;
                strcpy(cp, hp->h_name);
                cp += strlen(cp) + 1;
        } else
                nhp->h_name = NULL;
        nhp->h_aliases = (char **)((char *)nhp + al_off);
        if ((pp = hp->h_aliases) != NULL) {
                for (i = 0; *pp != NULL; pp++) {
                        if (**pp != '\0') {
                                nhp->h_aliases[i++] = cp;
                                strcpy(cp, *pp);
                                cp += strlen(cp) + 1;
                        }
                }
        }
        nhp->h_aliases[nalias] = NULL;
        cp = (char *)&nhp->h_aliases[nalias + 1];
        nhp->h_addrtype = hp->h_addrtype;
        nhp->h_length = hp->h_length;
        nhp->h_addr_list = (char **)cp;
        if ((pp = hp->h_addr_list) != NULL) {
                cp = (char *)&nhp->h_addr_list[naddr + 1];
                for (i = 0; *pp != NULL; pp++) {
                        nhp->h_addr_list[i++] = cp;
                        memcpy(cp, *pp, hp->h_length);
                        cp += addrsize;
                }
        }
        nhp->h_addr_list[naddr] = NULL;
        return nhp;
}

/*
 * _hpaddr: construct hostent structure with one address
 */
static struct hostent *
_hpaddr(int af, const char *name, void *addr, int *errp)
{
        struct hostent *hp, hpbuf;
        char *addrs[2];

        hp = &hpbuf;
        hp->h_name = (char *)name;
        hp->h_aliases = NULL;
        hp->h_addrtype = af;
        hp->h_length = ADDRLEN(af);
        hp->h_addr_list = addrs;
        addrs[0] = (char *)addr;
        addrs[1] = NULL;
        return (_hpcopy(hp, errp));
}

#ifdef INET6
/*
 * _hpmerge: merge 2 hostent structure, arguments will be freed
 */
static struct hostent *
_hpmerge(struct hostent *hp1, struct hostent *hp2, int *errp)
{
        int i, j;
        int naddr, nalias;
        char **pp;
        struct hostent *hp, hpbuf;
        char *aliases[MAXALIASES + 1], *addrs[MAXADDRS + 1];
        union inx_addr addrbuf[MAXADDRS];

        if (hp1 == NULL)
                return _hpcopy(hp2, errp);
        if (hp2 == NULL)
                return _hpcopy(hp1, errp);

#define HP(i)   (i == 1 ? hp1 : hp2)
        hp = &hpbuf;
        hp->h_name = (hp1->h_name != NULL ? hp1->h_name : hp2->h_name);
        hp->h_aliases = aliases;
        nalias = 0;
        for (i = 1; i <= 2; i++) {
                if ((pp = HP(i)->h_aliases) == NULL)
                        continue;
                for (; nalias < MAXALIASES && *pp != NULL; pp++) {
                        /* check duplicates */
                        for (j = 0; j < nalias; j++)
                                if (strcasecmp(*pp, aliases[j]) == 0)
                                        break;
                        if (j == nalias)
                                aliases[nalias++] = *pp;
                }
        }
        aliases[nalias] = NULL;
        if (hp1->h_length != hp2->h_length) {
                hp->h_addrtype = AF_INET6;
                hp->h_length = sizeof(struct in6_addr);
        } else {
                hp->h_addrtype = hp1->h_addrtype;
                hp->h_length = hp1->h_length;
        }

        hp->h_addr_list = addrs;
        naddr = 0;
        for (i = 1; i <= 2; i++) {
                if ((pp = HP(i)->h_addr_list) == NULL)
                        continue;
                if (HP(i)->h_length == hp->h_length) {
                        while (naddr < MAXADDRS && *pp != NULL)
                                addrs[naddr++] = *pp++;
                } else {
                        /* copy IPv4 addr as mapped IPv6 addr */
                        while (naddr < MAXADDRS && *pp != NULL) {
                                MAPADDR(&addrbuf[naddr], *pp++);
                                addrs[naddr] = (char *)&addrbuf[naddr];
                                naddr++;
                        }
                }
        }
        addrs[naddr] = NULL;
        return (_hpcopy(hp, errp));
}
#endif

/*
 * _hpmapv6: convert IPv4 hostent into IPv4-mapped IPv6 addresses
 */
#ifdef INET6
static struct hostent *
_hpmapv6(struct hostent *hp, int *errp)
{
        struct hostent hp6;

        if (hp == NULL)
                return NULL;
        if (hp->h_addrtype == AF_INET6)
                return _hpcopy(hp, errp);

        memset(&hp6, 0, sizeof(struct hostent));
        hp6.h_addrtype = AF_INET6;
        hp6.h_length = sizeof(struct in6_addr);
        return _hpmerge(&hp6, hp, errp);
}
#endif

/*
 * _hpsort: sort address by sortlist
 */
static struct hostent *
_hpsort(struct hostent *hp, res_state statp)
{
        int i, j, n;
        u_char *ap, *sp, *mp, **pp;
        char t;
        char order[MAXADDRS];
        int nsort = statp->nsort;

        if (hp == NULL || hp->h_addr_list[1] == NULL || nsort == 0)
                return hp;
        for (i = 0; (ap = (u_char *)hp->h_addr_list[i]); i++) {
                for (j = 0; j < nsort; j++) {
#ifdef INET6
                        if (statp->_u._ext.ext->sort_list[j].af !=
                            hp->h_addrtype)
                                continue;
                        sp = (u_char *)&statp->_u._ext.ext->sort_list[j].addr;
                        mp = (u_char *)&statp->_u._ext.ext->sort_list[j].mask;
#else
                        sp = (u_char *)&statp->sort_list[j].addr;
                        mp = (u_char *)&statp->sort_list[j].mask;
#endif
                        for (n = 0; n < hp->h_length; n++) {
                                if ((ap[n] & mp[n]) != sp[n])
                                        break;
                        }
                        if (n == hp->h_length)
                                break;
                }
                order[i] = j;
        }
        n = i;
        pp = (u_char **)hp->h_addr_list;
        for (i = 0; i < n - 1; i++) {
                for (j = i + 1; j < n; j++) {
                        if (order[i] > order[j]) {
                                ap = pp[i];
                                pp[i] = pp[j];
                                pp[j] = ap;
                                t = order[i];
                                order[i] = order[j];
                                order[j] = t;
                        }
                }
        }
        return hp;
}

#ifdef INET6
/*
 * _hpreorder: sort address by default address selection
 */
static struct hostent *
_hpreorder(struct hostent *hp)
{
        struct hp_order *aio;
        int i, n;
        char *ap;
        struct sockaddr *sa;
        struct policyhead policyhead;

        if (hp == NULL)
                return hp;

        switch (hp->h_addrtype) {
        case AF_INET:
#ifdef INET6
        case AF_INET6:
#endif
                break;
        default:
                return hp;
        }

        /* count the number of addrinfo elements for sorting. */
        for (n = 0; hp->h_addr_list[n] != NULL; n++)
                ;

        /*
         * If the number is small enough, we can skip the reordering process.
         */
        if (n <= 1)
                return hp;

        /* allocate a temporary array for sort and initialization of it. */
        if ((aio = malloc(sizeof(*aio) * n)) == NULL)
                return hp;      /* give up reordering */
        memset(aio, 0, sizeof(*aio) * n);

        /* retrieve address selection policy from the kernel */
        TAILQ_INIT(&policyhead);
        if (!get_addrselectpolicy(&policyhead)) {
                /* no policy is installed into kernel, we don't sort. */
                free(aio);
                return hp;
        }

        for (i = 0; i < n; i++) {
                ap = hp->h_addr_list[i];
                aio[i].aio_h_addr = ap;
                sa = &aio[i].aio_sa;
                switch (hp->h_addrtype) {
                case AF_INET:
                        sa->sa_family = AF_INET;
                        sa->sa_len = sizeof(struct sockaddr_in);
                        memcpy(&((struct sockaddr_in *)sa)->sin_addr, ap,
                            sizeof(struct in_addr));
                        break;
#ifdef INET6
                case AF_INET6:
                        if (IN6_IS_ADDR_V4MAPPED((struct in6_addr *)ap)) {
                                sa->sa_family = AF_INET;
                                sa->sa_len = sizeof(struct sockaddr_in);
                                memcpy(&((struct sockaddr_in *)sa)->sin_addr,
                                    &ap[12], sizeof(struct in_addr));
                        } else {
                                sa->sa_family = AF_INET6;
                                sa->sa_len = sizeof(struct sockaddr_in6);
                                memcpy(&((struct sockaddr_in6 *)sa)->sin6_addr,
                                    ap, sizeof(struct in6_addr));
                        }
                        break;
#endif
                }
                aio[i].aio_dstscope = gai_addr2scopetype(sa);
                aio[i].aio_dstpolicy = match_addrselectpolicy(sa, &policyhead);
                set_source(&aio[i], &policyhead);
                aio[i].aio_initial_sequence = i;
        }

        /* perform sorting. */
        qsort(aio, n, sizeof(*aio), comp_dst);

        /* reorder the h_addr_list. */
        for (i = 0; i < n; i++)
                hp->h_addr_list[i] = aio[i].aio_h_addr;

        /* cleanup and return */
        free(aio);
        free_addrselectpolicy(&policyhead);
        return hp;
}

static int
get_addrselectpolicy(struct policyhead *head)
{
#ifdef INET6
        int mib[] = { CTL_NET, PF_INET6, IPPROTO_IPV6, IPV6CTL_ADDRCTLPOLICY };
        size_t l;
        char *buf;
        struct in6_addrpolicy *pol, *ep;

        if (sysctl(mib, nitems(mib), NULL, &l, NULL, 0) < 0)
                return (0);
        if ((buf = malloc(l)) == NULL)
                return (0);
        if (sysctl(mib, nitems(mib), buf, &l, NULL, 0) < 0) {
                free(buf);
                return (0);
        }

        ep = (struct in6_addrpolicy *)(buf + l);
        for (pol = (struct in6_addrpolicy *)buf; pol + 1 <= ep; pol++) {
                struct policyqueue *new;

                if ((new = malloc(sizeof(*new))) == NULL) {
                        free_addrselectpolicy(head); /* make the list empty */
                        break;
                }
                new->pc_policy = *pol;
                TAILQ_INSERT_TAIL(head, new, pc_entry);
        }

        free(buf);
        return (1);
#else
        return (0);
#endif
}

static void
free_addrselectpolicy(struct policyhead *head)
{
        struct policyqueue *ent, *nent;

        for (ent = TAILQ_FIRST(head); ent; ent = nent) {
                nent = TAILQ_NEXT(ent, pc_entry);
                TAILQ_REMOVE(head, ent, pc_entry);
                free(ent);
        }
}

static struct policyqueue *
match_addrselectpolicy(struct sockaddr *addr, struct policyhead *head)
{
#ifdef INET6
        struct policyqueue *ent, *bestent = NULL;
        struct in6_addrpolicy *pol;
        int matchlen, bestmatchlen = -1;
        u_char *mp, *ep, *k, *p, m;
        struct sockaddr_in6 key;

        switch(addr->sa_family) {
        case AF_INET6:
                key = *(struct sockaddr_in6 *)addr;
                break;
        case AF_INET:
                /* convert the address into IPv4-mapped IPv6 address. */
                memset(&key, 0, sizeof(key));
                key.sin6_family = AF_INET6;
                key.sin6_len = sizeof(key);
                _map_v4v6_address(
                    (char *)&((struct sockaddr_in *)addr)->sin_addr,
                    (char *)&key.sin6_addr);
                break;
        default:
                return(NULL);
        }

        for (ent = TAILQ_FIRST(head); ent; ent = TAILQ_NEXT(ent, pc_entry)) {
                pol = &ent->pc_policy;
                matchlen = 0;

                mp = (u_char *)&pol->addrmask.sin6_addr;
                ep = mp + 16;   /* XXX: scope field? */
                k = (u_char *)&key.sin6_addr;
                p = (u_char *)&pol->addr.sin6_addr;
                for (; mp < ep && *mp; mp++, k++, p++) {
                        m = *mp;
                        if ((*k & m) != *p)
                                goto next; /* not match */
                        if (m == 0xff) /* short cut for a typical case */
                                matchlen += 8;
                        else {
                                while (m >= 0x80) {
                                        matchlen++;
                                        m <<= 1;
                                }
                        }
                }

                /* matched.  check if this is better than the current best. */
                if (matchlen > bestmatchlen) {
                        bestent = ent;
                        bestmatchlen = matchlen;
                }

          next:
                continue;
        }

        return(bestent);
#else
        return(NULL);
#endif

}

static void
set_source(struct hp_order *aio, struct policyhead *ph)
{
        struct sockaddr_storage ss = aio->aio_un.aiou_ss;
        socklen_t srclen;
        int s;

        /* set unspec ("no source is available"), just in case */
        aio->aio_srcsa.sa_family = AF_UNSPEC;
        aio->aio_srcscope = -1;

        switch(ss.ss_family) {
        case AF_INET:
                ((struct sockaddr_in *)&ss)->sin_port = htons(1);
                break;
#ifdef INET6
        case AF_INET6:
                ((struct sockaddr_in6 *)&ss)->sin6_port = htons(1);
                break;
#endif
        default:                /* ignore unsupported AFs explicitly */
                return;
        }

        /* open a socket to get the source address for the given dst */
        if ((s = _socket(ss.ss_family, SOCK_DGRAM | SOCK_CLOEXEC,
            IPPROTO_UDP)) < 0)
                return;         /* give up */
        if (_connect(s, (struct sockaddr *)&ss, ss.ss_len) < 0)
                goto cleanup;
        srclen = ss.ss_len;
        if (_getsockname(s, &aio->aio_srcsa, &srclen) < 0) {
                aio->aio_srcsa.sa_family = AF_UNSPEC;
                goto cleanup;
        }
        aio->aio_srcscope = gai_addr2scopetype(&aio->aio_srcsa);
        aio->aio_srcpolicy = match_addrselectpolicy(&aio->aio_srcsa, ph);
        aio->aio_matchlen = matchlen(&aio->aio_srcsa, (struct sockaddr *)&ss);
#ifdef INET6
        if (ss.ss_family == AF_INET6) {
                struct in6_ifreq ifr6;
                u_int32_t flags6;

                memset(&ifr6, 0, sizeof(ifr6));
                memcpy(&ifr6.ifr_addr, &ss, ss.ss_len);
                if (_ioctl(s, SIOCGIFAFLAG_IN6, &ifr6) == 0) {
                        flags6 = ifr6.ifr_ifru.ifru_flags6;
                        if ((flags6 & IN6_IFF_DEPRECATED))
                                aio->aio_srcflag |= AIO_SRCFLAG_DEPRECATED;
                }
        }
#endif

  cleanup:
        _close(s);
        return;
}

static int
matchlen(struct sockaddr *src, struct sockaddr *dst)
{
        int match = 0;
        u_char *s, *d;
        u_char *lim, r;
        int addrlen;

        switch (src->sa_family) {
#ifdef INET6
        case AF_INET6:
                s = (u_char *)&((struct sockaddr_in6 *)src)->sin6_addr;
                d = (u_char *)&((struct sockaddr_in6 *)dst)->sin6_addr;
                addrlen = sizeof(struct in6_addr);
                lim = s + addrlen;
                break;
#endif
        case AF_INET:
                s = (u_char *)&((struct sockaddr_in *)src)->sin_addr;
                d = (u_char *)&((struct sockaddr_in *)dst)->sin_addr;
                addrlen = sizeof(struct in_addr);
                lim = s + addrlen;
                break;
        default:
                return(0);
        }

        while (s < lim)
                if ((r = (*d++ ^ *s++)) != 0) {
                        while ((r & 0x80) == 0) {
                                match++;
                                r <<= 1;
                        }
                        break;
                } else
                        match += 8;
        return(match);
}

static int
comp_dst(const void *arg1, const void *arg2)
{
        const struct hp_order *dst1 = arg1, *dst2 = arg2;

        /*
         * Rule 1: Avoid unusable destinations.
         * XXX: we currently do not consider if an appropriate route exists.
         */
        if (dst1->aio_srcsa.sa_family != AF_UNSPEC &&
            dst2->aio_srcsa.sa_family == AF_UNSPEC) {
                return(-1);
        }
        if (dst1->aio_srcsa.sa_family == AF_UNSPEC &&
            dst2->aio_srcsa.sa_family != AF_UNSPEC) {
                return(1);
        }

        /* Rule 2: Prefer matching scope. */
        if (dst1->aio_dstscope == dst1->aio_srcscope &&
            dst2->aio_dstscope != dst2->aio_srcscope) {
                return(-1);
        }
        if (dst1->aio_dstscope != dst1->aio_srcscope &&
            dst2->aio_dstscope == dst2->aio_srcscope) {
                return(1);
        }

        /* Rule 3: Avoid deprecated addresses. */
        if (dst1->aio_srcsa.sa_family != AF_UNSPEC &&
            dst2->aio_srcsa.sa_family != AF_UNSPEC) {
                if (!(dst1->aio_srcflag & AIO_SRCFLAG_DEPRECATED) &&
                    (dst2->aio_srcflag & AIO_SRCFLAG_DEPRECATED)) {
                        return(-1);
                }
                if ((dst1->aio_srcflag & AIO_SRCFLAG_DEPRECATED) &&
                    !(dst2->aio_srcflag & AIO_SRCFLAG_DEPRECATED)) {
                        return(1);
                }
        }

        /* Rule 4: Prefer home addresses. */
        /* XXX: not implemented yet */

        /* Rule 5: Prefer matching label. */
#ifdef INET6
        if (dst1->aio_srcpolicy && dst1->aio_dstpolicy &&
            dst1->aio_srcpolicy->pc_policy.label ==
            dst1->aio_dstpolicy->pc_policy.label &&
            (dst2->aio_srcpolicy == NULL || dst2->aio_dstpolicy == NULL ||
             dst2->aio_srcpolicy->pc_policy.label !=
             dst2->aio_dstpolicy->pc_policy.label)) {
                return(-1);
        }
        if (dst2->aio_srcpolicy && dst2->aio_dstpolicy &&
            dst2->aio_srcpolicy->pc_policy.label ==
            dst2->aio_dstpolicy->pc_policy.label &&
            (dst1->aio_srcpolicy == NULL || dst1->aio_dstpolicy == NULL ||
             dst1->aio_srcpolicy->pc_policy.label !=
             dst1->aio_dstpolicy->pc_policy.label)) {
                return(1);
        }
#endif

        /* Rule 6: Prefer higher precedence. */
#ifdef INET6
        if (dst1->aio_dstpolicy &&
            (dst2->aio_dstpolicy == NULL ||
             dst1->aio_dstpolicy->pc_policy.preced >
             dst2->aio_dstpolicy->pc_policy.preced)) {
                return(-1);
        }
        if (dst2->aio_dstpolicy &&
            (dst1->aio_dstpolicy == NULL ||
             dst2->aio_dstpolicy->pc_policy.preced >
             dst1->aio_dstpolicy->pc_policy.preced)) {
                return(1);
        }
#endif

        /* Rule 7: Prefer native transport. */
        /* XXX: not implemented yet */

        /* Rule 8: Prefer smaller scope. */
        if (dst1->aio_dstscope >= 0 &&
            dst1->aio_dstscope < dst2->aio_dstscope) {
                return(-1);
        }
        if (dst2->aio_dstscope >= 0 &&
            dst2->aio_dstscope < dst1->aio_dstscope) {
                return(1);
        }

        /*
         * Rule 9: Use longest matching prefix.
         * We compare the match length in a same AF only.
         */
        if (dst1->aio_sa.sa_family == dst2->aio_sa.sa_family) {
                if (dst1->aio_matchlen > dst2->aio_matchlen) {
                        return(-1);
                }
                if (dst1->aio_matchlen < dst2->aio_matchlen) {
                        return(1);
                }
        }

        /* Rule 10: Otherwise, leave the order unchanged. */

        /* 
         * Note that qsort is unstable; so, we can't return zero and 
         * expect the order to be unchanged.
         * That also means we can't depend on the current position of
         * dst2 being after dst1.  We must enforce the initial order
         * with an explicit compare on the original position.
         * The qsort specification requires that "When the same objects 
         * (consisting of width bytes, irrespective of their current 
         * positions in the array) are passed more than once to the 
         * comparison function, the results shall be consistent with one 
         * another."  
         * In other words, If A < B, then we must also return B > A.
         */
        if (dst2->aio_initial_sequence < dst1->aio_initial_sequence)
                return(1);

        return(-1);
}

/*
 * Copy from scope.c.
 * XXX: we should standardize the functions and link them as standard
 * library.
 */
static int
gai_addr2scopetype(struct sockaddr *sa)
{
#ifdef INET6
        struct sockaddr_in6 *sa6;
#endif
        struct sockaddr_in *sa4;

        switch(sa->sa_family) {
#ifdef INET6
        case AF_INET6:
                sa6 = (struct sockaddr_in6 *)sa;
                if (IN6_IS_ADDR_MULTICAST(&sa6->sin6_addr)) {
                        /* just use the scope field of the multicast address */
                        return(sa6->sin6_addr.s6_addr[2] & 0x0f);
                }
                /*
                 * Unicast addresses: map scope type to corresponding scope
                 * value defined for multcast addresses.
                 * XXX: hardcoded scope type values are bad...
                 */
                if (IN6_IS_ADDR_LOOPBACK(&sa6->sin6_addr))
                        return(1); /* node local scope */
                if (IN6_IS_ADDR_LINKLOCAL(&sa6->sin6_addr))
                        return(2); /* link-local scope */
                if (IN6_IS_ADDR_SITELOCAL(&sa6->sin6_addr))
                        return(5); /* site-local scope */
                return(14);     /* global scope */
                break;
#endif
        case AF_INET:
                /*
                 * IPv4 pseudo scoping according to RFC 3484.
                 */
                sa4 = (struct sockaddr_in *)sa;
                /* IPv4 autoconfiguration addresses have link-local scope. */
                if (((u_char *)&sa4->sin_addr)[0] == 169 &&
                    ((u_char *)&sa4->sin_addr)[1] == 254)
                        return(2);
                /* Private addresses have site-local scope. */
                if (((u_char *)&sa4->sin_addr)[0] == 10 ||
                    (((u_char *)&sa4->sin_addr)[0] == 172 &&
                     (((u_char *)&sa4->sin_addr)[1] & 0xf0) == 16) ||
                    (((u_char *)&sa4->sin_addr)[0] == 192 &&
                     ((u_char *)&sa4->sin_addr)[1] == 168))
                        return(14);     /* XXX: It should be 5 unless NAT */
                /* Loopback addresses have link-local scope. */
                if (((u_char *)&sa4->sin_addr)[0] == 127)
                        return(2);
                return(14);
                break;
        default:
                errno = EAFNOSUPPORT; /* is this a good error? */
                return(-1);
        }
}
#endif