diff libpurple/dnssrv.c @ 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/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;