From ce6fbd623115c88cfdf0f5ed36b01cca201ba78e Mon Sep 17 00:00:00 2001 From: Dan Winship Date: Thu, 28 May 2009 15:27:04 -0400 Subject: [PATCH] Fix multiple bugs in g_srv_target_list_sort() In particular, targets with weight 0 should be very UNlikely to be selected, not very likely, as they were before. However, even ignoring that bug in the logic, there was an additional bug (swapping list items would cause the 0-weight items to get re-ordered incorrectly anyway), and the code contained several fencepost errors. This patch also adds gio/tests/srvtarget.c, which confirms that for a sample list of targets, we now generate all possible correct random sortings and no incorrect sortings, and the correct sortings occur in roughly the expected proportions (though if the current code is still wrong, those proportions may be wrong as well). http://bugzilla.gnome.org/show_bug.cgi?id=583398 --- gio/gsrvtarget.c | 92 ++++++++++++------------- gio/tests/Makefile.am | 6 +- gio/tests/srvtarget.c | 157 ++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 205 insertions(+), 50 deletions(-) create mode 100644 gio/tests/srvtarget.c diff --git a/gio/gsrvtarget.c b/gio/gsrvtarget.c index 4210ea137..526b0ddfb 100644 --- a/gio/gsrvtarget.c +++ b/gio/gsrvtarget.c @@ -229,12 +229,7 @@ compare_target (gconstpointer a, gconstpointer b) * that all those with weight 0 are placed at the beginning of * the list" */ - if (ta->weight == 0) - return -1; - else if (tb->weight == 0) - return 1; - else - return g_random_int_range (-1, 1); + return ta->weight - tb->weight; } else return ta->priority - tb->priority; @@ -253,10 +248,9 @@ compare_target (gconstpointer a, gconstpointer b) GList * g_srv_target_list_sort (GList *targets) { - gint sum, val, priority, weight; - GList *first, *last, *n; + gint sum, num, val, priority, weight; + GList *t, *out, *tail; GSrvTarget *target; - gpointer tmp; if (!targets) return NULL; @@ -275,62 +269,62 @@ g_srv_target_list_sort (GList *targets) } } - /* Sort by priority, and partly by weight */ + /* Sort input list by priority, and put the 0-weight targets first + * in each priority group. Initialize output list to %NULL. + */ targets = g_list_sort (targets, compare_target); + out = tail = NULL; - /* For each group of targets with the same priority, rebalance them - * according to weight. + /* For each group of targets with the same priority, remove them + * from @targets and append them to @out in a valid order. */ - for (first = targets; first; first = last->next) + while (targets) { - /* Skip @first to a non-0-weight target. */ - while (first && ((GSrvTarget *)first->data)->weight == 0) - first = first->next; - if (!first) - break; - - /* Skip @last to the last target of the same priority. */ - priority = ((GSrvTarget *)first->data)->priority; - last = first; - while (last->next && - ((GSrvTarget *)last->next->data)->priority == priority) - last = last->next; - - /* If there's only one non-0 weight target at this priority, - * we can move on to the next priority level. - */ - if (last == first) - continue; - - /* Randomly reorder the non-0 weight targets, giving precedence - * to the ones with higher weight. RFC 2782 describes this in - * terms of assigning a running sum to each target and building - * a new list. We do things slightly differently, but should get - * the same result. + priority = ((GSrvTarget *)targets->data)->priority; + + /* Count the number of targets at this priority level, and + * compute the sum of their weights. */ - for (n = first, sum = 0; n != last->next; n = n->next) - sum += ((GSrvTarget *)n->data)->weight; - while (first != last) + sum = num = 0; + for (t = targets; t; t = t->next) + { + target = (GSrvTarget *)t->data; + if (target->priority != priority) + break; + sum += target->weight; + num++; + } + + /* While there are still targets at this priority level... */ + while (num) { - val = g_random_int_range (0, sum); - for (n = first; n != last; n = n->next) + /* Randomly select from the targets at this priority level, + * giving precedence to the ones with higher weight, + * according to the rules from RFC 2782. + */ + val = g_random_int_range (0, sum + 1); + for (t = targets; ; t = t->next) { - weight = ((GSrvTarget *)n->data)->weight; - if (val < weight) + weight = ((GSrvTarget *)t->data)->weight; + if (weight >= val) break; val -= weight; } - tmp = first->data; - first->data = n->data; - n->data = tmp; + targets = g_list_remove_link (targets, t); + + if (!out) + out = t; + else + tail->next = t; + tail = t; sum -= weight; - first = first->next; + num--; } } - return targets; + return out; } #define __G_SRV_TARGET_C__ diff --git a/gio/tests/Makefile.am b/gio/tests/Makefile.am index 46b9fa69a..e49c29ea3 100644 --- a/gio/tests/Makefile.am +++ b/gio/tests/Makefile.am @@ -28,7 +28,8 @@ TEST_PROGS += \ buffered-input-stream \ sleepy-stream \ filter-streams \ - simple-async-result + simple-async-result \ + srvtarget SAMPLE_PROGS = resolver socket-server socket-client echo-server httpd send-data @@ -106,4 +107,7 @@ send_data_SOURCES = send-data.c send_data_LDADD = $(progs_ldadd) \ $(top_builddir)/gthread/libgthread-2.0.la +srvtarget_SOURCES = srvtarget.c +srvtarget_LDADD = $(progs_ldadd) + DISTCLEAN_FILES = applications/mimeinfo.cache diff --git a/gio/tests/srvtarget.c b/gio/tests/srvtarget.c new file mode 100644 index 000000000..dcbc143c0 --- /dev/null +++ b/gio/tests/srvtarget.c @@ -0,0 +1,157 @@ +/* GLib testing framework examples and tests + * Copyright (C) 2009 Red Hat, Inc. + * + * This work is provided "as is"; redistribution and modification + * in whole or in part, in any medium, physical or electronic is + * permitted without restriction. + * + * This work is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. + * + * In no event shall the authors or contributors be liable for any + * direct, indirect, incidental, special, exemplary, or consequential + * damages (including, but not limited to, procurement of substitute + * goods or services; loss of use, data, or profits; or business + * interruption) however caused and on any theory of liability, whether + * in contract, strict liability, or tort (including negligence or + * otherwise) arising in any way out of the use of this software, even + * if advised of the possibility of such damage. + */ + +#include +#include +#include +#include + +#define NUM_TRIALS 250000 + +struct { + const char *order; + int expected, seen; +} ordering[] = { + /* There are 32 legitimate orderings; the result always has to start + * with either "fe" (usually) or "ef" (rarely). For the remaining + * letters, "cbda" is the most likely, with various other orders + * possible, down to "adbc" being the most improbable. However, + * almost all "fe" orderings are more likely than almost any "ef" + * orderings. The complete probability ordering, from most-likely + * to least-likely is something roughly like: + */ + { "fecbda", 0.2468 * NUM_TRIALS, 0}, + { "febcda", 0.1885 * NUM_TRIALS, 0}, + { "fecdba", 0.1346 * NUM_TRIALS, 0}, + { "fedcba", 0.0830 * NUM_TRIALS, 0}, + { "febdca", 0.0706 * NUM_TRIALS, 0}, + { "fedbca", 0.0571 * NUM_TRIALS, 0}, + { "fecbad", 0.0496 * NUM_TRIALS, 0}, + { "febcad", 0.0374 * NUM_TRIALS, 0}, + { "fecabd", 0.0185 * NUM_TRIALS, 0}, + { "fecdab", 0.0136 * NUM_TRIALS, 0}, + { "fecadb", 0.0110 * NUM_TRIALS, 0}, + { "febacd", 0.0108 * NUM_TRIALS, 0}, + { "feacbd", 0.0096 * NUM_TRIALS, 0}, + { "fedcab", 0.0083 * NUM_TRIALS, 0}, + { "feabcd", 0.0073 * NUM_TRIALS, 0}, + { "feacdb", 0.0058 * NUM_TRIALS, 0}, + { "efcbda", 0.0049 * NUM_TRIALS, 0}, + { "febdac", 0.0048 * NUM_TRIALS, 0}, + { "febadc", 0.0043 * NUM_TRIALS, 0}, + { "fedbac", 0.0038 * NUM_TRIALS, 0}, + { "efbcda", 0.0038 * NUM_TRIALS, 0}, + { "feadcb", 0.0036 * NUM_TRIALS, 0}, + { "fedacb", 0.0035 * NUM_TRIALS, 0}, + { "feabdc", 0.0029 * NUM_TRIALS, 0}, + { "feadbc", 0.0026 * NUM_TRIALS, 0}, + { "fedabc", 0.0026 * NUM_TRIALS, 0}, + { "efcdba", 0.0026 * NUM_TRIALS, 0}, + { "efdcba", 0.0017 * NUM_TRIALS, 0}, + { "efbdca", 0.0014 * NUM_TRIALS, 0}, + { "efdbca", 0.0011 * NUM_TRIALS, 0}, + { "efcbad", 0.0010 * NUM_TRIALS, 0}, + { "efbcad", 0.0008 * NUM_TRIALS, 0}, + { "efcabd", 0.0004 * NUM_TRIALS, 0}, + { "efcdab", 0.0003 * NUM_TRIALS, 0}, + { "efcadb", 0.0002 * NUM_TRIALS, 0}, + { "efbacd", 0.0002 * NUM_TRIALS, 0}, + { "efacbd", 0.0002 * NUM_TRIALS, 0}, + { "efdcab", 0.0002 * NUM_TRIALS, 0}, + { "efabcd", 0.0002 * NUM_TRIALS, 0}, + { "efacdb", 0.0001 * NUM_TRIALS, 0}, + { "efbdac", 0.0001 * NUM_TRIALS, 0}, + { "efadcb", 0.0001 * NUM_TRIALS, 0}, + { "efdbac", 0.0001 * NUM_TRIALS, 0}, + { "efbadc", 0.0001 * NUM_TRIALS, 0}, + { "efdacb", 0.0001 * NUM_TRIALS, 0}, + { "efabdc", 0.0001 * NUM_TRIALS, 0}, + { "efadbc", 0.00005 * NUM_TRIALS, 0}, + { "efdabc", 0.00005 * NUM_TRIALS, 0} +}; +#define NUM_ORDERINGS G_N_ELEMENTS (ordering) + +static void +test_srv_target_ordering (void) +{ + GList *targets, *sorted, *t; + char result[7], *p; + int i, o; + + targets = NULL; + /* name, port, priority, weight */ + targets = g_list_append (targets, g_srv_target_new ("a", 0, 2, 0)); + targets = g_list_append (targets, g_srv_target_new ("b", 0, 2, 10)); + targets = g_list_append (targets, g_srv_target_new ("c", 0, 2, 15)); + targets = g_list_append (targets, g_srv_target_new ("d", 0, 2, 5)); + targets = g_list_append (targets, g_srv_target_new ("e", 0, 1, 0)); + targets = g_list_append (targets, g_srv_target_new ("f", 0, 1, 50)); + + for (i = 0; i < NUM_TRIALS; i++) + { + g_random_set_seed (i); + + sorted = g_srv_target_list_sort (g_list_copy (targets)); + + for (t = sorted, p = result; t; t = t->next) + *(p++) = *g_srv_target_get_hostname (t->data); + *p = '\0'; + g_list_free (sorted); + + for (o = 0; o < NUM_ORDERINGS; o++) + { + if (!strcmp (result, ordering[o].order)) + { + ordering[o].seen++; + break; + } + } + + /* Assert that @result matched one of the valid orderings */ + if (o == NUM_ORDERINGS) + { + char *msg = g_strdup_printf ("result '%s' is invalid", result); + g_assertion_message (G_LOG_DOMAIN, __FILE__, __LINE__, G_STRFUNC, msg); + } + } + + /* Assert that each ordering appeared roughly the expected + * number of times. + */ + for (o = 0; o < NUM_ORDERINGS; o++) + { + g_assert_cmpint (ordering[o].seen, >, ordering[o].expected / 2); + g_assert_cmpint (ordering[o].seen, <, ordering[o].expected * 2); + } + + g_resolver_free_targets (targets); +} + +int +main (int argc, char **argv) +{ + g_type_init (); + g_test_init (&argc, &argv, NULL); + + g_test_add_func ("/srvtarget/srv-target-ordering", test_srv_target_ordering); + + return g_test_run(); +} -- 2.34.1