MFC r304911

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

1 files changed, 19 insertions, 0 deletions

diff --git a/lib/libc/net/getaddrinfo.c b/lib/libc/net/getaddrinfo.c
index 56500c6..0d86fe5 100644
--- a/lib/libc/net/getaddrinfo.c
+++ b/lib/libc/net/getaddrinfo.c
@@ -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 *arg2)
 	}
 
 	/* 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);
 }