pidgin: 0de8339e: Changes to our DNS SRV record sorting, c...
markdoliner at pidgin.im
markdoliner at pidgin.im
Mon Jun 29 02:55:22 EDT 2009
-----------------------------------------------------------------
Revision: 0de8339ed2206f013cb9b8105fe3c73ccc2a0f72
Ancestor: 11d28a9362597cbea7fa0957f4202037131a3d6b
Author: markdoliner at pidgin.im
Date: 2009-06-29T06:49:59
Branch: im.pidgin.pidgin
URL: http://d.pidgin.im/viewmtn/revision/info/0de8339ed2206f013cb9b8105fe3c73ccc2a0f72
Modified files:
ChangeLog libpurple/dnssrv.c libpurple/dnssrv.h
ChangeLog:
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.
-------------- next part --------------
============================================================
--- ChangeLog dae07a147fa43f64a716783fbf3c80dea5fcbfb1
+++ ChangeLog 83780b67a94f2848528e209e42a70977cba0a938
@@ -18,6 +18,8 @@ version 2.6.0 (??/??/2009):
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
============================================================
--- libpurple/dnssrv.c 791a8be0b1e30b593327fbf6f13d8ebaf6d635ff
+++ libpurple/dnssrv.c 85b1b59ad4af7daa2ec9f3cad86219e35e8a4292
@@ -94,6 +94,17 @@ typedef struct _PurpleSrvInternalQuery {
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 @@ responsecompare(gconstpointer ar, gconst
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 @@ resolve(int in, int out)
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:
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 @@ res_thread(gpointer data)
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;
============================================================
--- libpurple/dnssrv.h b38c7db2e5f57b20e11e6b47776d239002063997
+++ libpurple/dnssrv.h 09cb8035323d51975d5dcf1ff776423cdc410dd8
@@ -41,6 +41,12 @@ struct _PurpleSrvResponse {
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);
/**
More information about the Commits
mailing list