Date: Sat, 27 Aug 2016 14:43:13 +0000 (UTC) From: "Andrey A. Chernov" <ache@FreeBSD.org> To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org Subject: svn commit: r304911 - head/lib/libc/net Message-ID: <201608271443.u7REhDdb091584@repo.freebsd.org>
next in thread | raw e-mail | index | archive | help
Author: ache Date: Sat Aug 27 14:43:13 2016 New Revision: 304911 URL: https://svnweb.freebsd.org/changeset/base/304911 Log: The formal behavior of qsort is unstable with regard to objects that are equal. Unfortunately, RFC 3484 requires that otherwise equal objects remain in the order supplied by the DNS server. The present code attempts to deal with this by returning -1 for objects that are equal (i.e., returns that the first parameter is less then the second parameter). Unfortunately, the qsort API does not state that the first parameter passed in is in any particular position in the list. PR: 212122 Submitted by: Herbie.Robinson@stratus.com MFC after: 3 days Modified: head/lib/libc/net/getaddrinfo.c Modified: head/lib/libc/net/getaddrinfo.c ============================================================================== --- head/lib/libc/net/getaddrinfo.c Sat Aug 27 13:47:52 2016 (r304910) +++ head/lib/libc/net/getaddrinfo.c Sat Aug 27 14:43:13 2016 (r304911) @@ -224,6 +224,7 @@ struct ai_order { struct policyqueue *aio_dstpolicy; struct addrinfo *aio_ai; int aio_matchlen; + int aio_initial_sequence; }; static const ns_src default_dns_files[] = { @@ -708,6 +709,7 @@ reorder(struct addrinfo *sentinel) aio[i].aio_dstpolicy = match_addrselectpolicy(ai->ai_addr, &policyhead); set_source(&aio[i], &policyhead); + aio[i].aio_initial_sequence = i; } /* perform sorting. */ @@ -1066,6 +1068,23 @@ comp_dst(const void *arg1, const void *a } /* 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); }
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?201608271443.u7REhDdb091584>