changeset 27295:3e516701dd33

Changes to our DNS SRV record sorting, care of Vijay Vijay Raghunathan from Meebo. SRV records have two fields that determine the order in which the results should be used: 1. Priority (which we call "pref" for some reason). Records with a lower priority will be used first. 2. Weight. Records with a higher weight are more likely to be used first, but there is some amount of randomness. We were actually doing this backwards and using records with lower weight first. And we weren't randomizing. But now we are.

--- a/ChangeLog	Mon Jun 29 05:02:24 2009 +0000
+++ b/ChangeLog	Mon Jun 29 06:49:59 2009 +0000
@@ -18,6 +18,8 @@
 	  from you on MSN.
 	* DNS servers are re-read when DNS queries fail in case the system has
 	  moved to a new network and the old servers are not accessible.
+	* DNS SRV records with equal priority are sorted with respect to their
+	  weight as specified in RFC 2782.  (Vijay Raghunathan)
 	* GnuTLS logging (disabled by default) can be controlled through the
 	  PURPLE_GNUTLS_DEBUG environment variable, which is an integer between
 	  0 and 9 (higher is more verbose). Higher values may reveal sensitive

--- a/libpurple/dnssrv.c	Mon Jun 29 05:02:24 2009 +0000
+++ b/libpurple/dnssrv.c	Mon Jun 29 06:49:59 2009 +0000
@@ -94,6 +94,17 @@
 	char query[256];
 } PurpleSrvInternalQuery;
 
+typedef struct _PurpleSrvResponseContainer {
+	PurpleSrvResponse *response;
+	int sum;
+} PurpleSrvResponseContainer;
+
+/**
+ * Sort by priority, then by weight.  Strictly numerically--no
+ * randomness.  Technically we only need to sort by pref and then
+ * make sure any records with weight 0 are at the beginning of
+ * their group, but it's just as easy to sort by weight.
+ */
 static gint
 responsecompare(gconstpointer ar, gconstpointer br)
 {
@@ -112,6 +123,129 @@
 	return 1;
 }
 
+/**
+ * Iterate over a list of PurpleSrvResponseContainer making the sum
+ * the running total of the sums.  Select a random integer in the range
+ * (1, sum+1), then find the first element greater than or equal to the
+ * number selected.  From RFC 2782.
+ *
+ * @param list The list of PurpleSrvResponseContainer.  This function
+ *        removes a node from this list and returns the new list.
+ * @param container_ptr The PurpleSrvResponseContainer that was chosen
+ *        will be returned here.
+ */
+static GList *select_random_response(GList *list,
+		PurpleSrvResponseContainer **container_ptr)
+{
+	GList *cur;
+	size_t runningtotal;
+	int r;
+
+	runningtotal = 0;
+	cur = list;
+
+	while (cur) {
+		PurpleSrvResponseContainer *container = cur->data;
+		runningtotal += container->response->weight;
+		container->sum = runningtotal;
+		cur = cur->next;
+	}
+
+	/*
+	 * If the running total is greater than 0, pick a number between
+	 * 1 and the runningtotal inclusive. (This is not precisely what
+	 * the RFC algorithm describes, but we wish to deal with integers
+	 * and avoid floats.  This is functionally equivalent.)
+	 * If running total is 0, then choose r = 0.
+	 */
+	r = runningtotal ? g_random_int_range(1, runningtotal + 1) : 0;
+	cur = list;
+	while (r > ((PurpleSrvResponseContainer *)cur->data)->sum) {
+		cur = cur->next;
+	}
+
+	/* Set the return parameter and remove cur from the list */
+	*container_ptr =  cur->data;
+	return g_list_delete_link(list, cur);
+}
+
+/**
+ * Reorder a GList of PurpleSrvResponses that have the same priority
+ * (aka "pref").
+ */
+static void srv_reorder(GList *list, int num)
+{
+	int i;
+	GList *cur;
+	GList *container_list = NULL;
+	PurpleSrvResponseContainer *container;
+
+	if (num < 2)
+		/* Nothing to sort */
+		return;
+
+	/* First build a list of container structs */
+	for (i = 0, cur = list; i < num; i++, cur = cur->next) {
+		container = g_new(PurpleSrvResponseContainer, 1);
+		container->response = cur->data;
+		container_list = g_list_prepend(container_list, container);
+	}
+	container_list = g_list_reverse(container_list);
+
+	/*
+	 * Re-order the list that was passed in as a parameter.  We leave
+	 * the list nodes in place, but replace their data pointers.
+	 */
+	cur = list;
+	while (container_list) {
+		container_list = select_random_response(container_list, &container);
+		cur->data = container->response;
+		g_free(container);
+		cur = cur->next;
+	}
+}
+
+/**
+ * Sorts a GList of PurpleSrvResponse's according to the
+ * algorithm described in RFC 2782.
+ *
+ * @param response GList of PurpleSrvResponse's
+ * @param The original list, resorted
+ */
+static GList *purple_srv_sort(GList *list)
+{
+	GList *cur, *start;
+	int count;
+	int pref;
+
+	if (!list || !list->next)
+		/* Nothing to sort */
+		return list;
+
+	list = g_list_sort(list, responsecompare);
+
+	start = cur = list;
+	count = 1;
+	while (cur) {
+		PurpleSrvResponse *next_response;
+		pref = ((PurpleSrvResponse *)cur->data)->pref;
+		next_response = cur->next ? cur->next->data : NULL;
+		if (!next_response || next_response->pref != pref) {
+			/*
+			 * The 'count' records starting at 'start' all have the same
+			 * priority.  Sort them by weight.
+			 */
+			srv_reorder(start, count);
+			start = cur->next;
+			count = 0;
+		}
+		count++;
+		cur = cur->next;
+	}
+
+	return list;
+}
+
 #ifndef _WIN32
 
 G_GNUC_NORETURN static void
@@ -191,7 +325,7 @@
 			srvres->port = port;
 			srvres->weight = weight;
 
-			ret = g_list_insert_sorted(ret, srvres, responsecompare);
+			ret = g_list_prepend(ret, srvres);
 		} else if (query.type == T_TXT) {
 			txtres = g_new0(PurpleTxtResponse, 1);
 			txtres->content = g_strndup((gchar*)(++cp), dlen-1);
@@ -204,6 +338,10 @@
 
 end:
 	size = g_list_length(ret);
+
+	if (query.type == T_SRV)
+		ret = purple_srv_sort(ret);
+
 	/* TODO: Check return value */
 	write(out, &(query.type), sizeof(query.type));
 	write(out, &size, sizeof(size));
@@ -397,11 +535,11 @@
 				srvres->port = srv_data->wPort;
 				srvres->weight = srv_data->wWeight;
 
-				lst = g_slist_insert_sorted(lst, srvres, responsecompare);
+				lst = g_slist_prepend(lst, srvres);
 			}
 
 			MyDnsRecordListFree(dr, DnsFreeRecordList);
-			query_data->results = lst;
+			query_data->results = purple_srv_sort(lst);
 		} else if (type == DNS_TYPE_TXT) {
 			PDNS_RECORD dr_tmp;
 			GSList *lst = NULL;

--- a/libpurple/dnssrv.h	Mon Jun 29 05:02:24 2009 +0000
+++ b/libpurple/dnssrv.h	Mon Jun 29 06:49:59 2009 +0000
@@ -41,6 +41,12 @@
 	int pref;
 };
 
+/**
+ * @param resp An array of PurpleSrvResponse of size results.  The array
+ *        is sorted based on the order described in the DNS SRV RFC.
+ *        Users of this API should try each record in resp in order,
+ *        starting at the beginning.
+ */
 typedef void (*PurpleSrvCallback)(PurpleSrvResponse *resp, int results, gpointer data);
 
 /**