From 9f0f17cd57970def9808a7899f178edd27185ba2 Mon Sep 17 00:00:00 2001 From: Thadeu Lima de Souza Cascardo Date: Sun, 6 Apr 2008 14:46:40 -0300 Subject: [PATCH] Code to sort SRV results from udns according to RFC 2782. --- sort_udns.c | 165 ++++++++++++++++++++++++++++++++++++++++++++++++++++ sort_udns.h | 25 ++++++++ 2 files changed, 190 insertions(+) create mode 100644 sort_udns.c create mode 100644 sort_udns.h diff --git a/sort_udns.c b/sort_udns.c new file mode 100644 index 0000000..8b0336b --- /dev/null +++ b/sort_udns.c @@ -0,0 +1,165 @@ +/* + * Copyright (C) 2008 Thadeu Lima de Souza Cascardo + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 2 of the License, or + * (at your option) any later version. + * + * This program 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. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see . + * + */ + +#include +#include +#include +#include +#include +#include + +/* + * Our own implementation of random integer numbers in a range. + */ +static int random_int_range (int start, int end) +{ + long long r; + int range = end - start; + r = random () * range; + r = r / RAND_MAX; + return start + r; +} + +/* + * Since we implement the proposed algorithm from RFC 2782, entries + * with weight 0 should come before those with non-zero weight. + */ +static int dns_srv_compare (const void* a, const void* b) +{ + struct dns_srv* addr_a = (struct dns_srv*) a; + struct dns_srv* addr_b = (struct dns_srv*) b; + if (addr_a->priority != addr_b->priority) + return addr_a->priority - addr_b->priority; + if (addr_b->weight == 0) + return 1; + else if (addr_a->weight == 0) + return -1; + return 0; +} + +/* + * Order a vector of addresses with priorities and weights by priority + * putting those with weight 0 at the start of those with the same + * priority. + */ +static void dns_srv_sort_priority (void* srvaddr, int n) +{ + qsort (srvaddr, n, sizeof (struct dns_srv), dns_srv_compare); +} + +/* + * Move entries between j and i one position forward and move i to j + * position. + */ +static void dns_srv_switch (struct dns_srv* srvaddr, int j, int i) +{ + struct dns_srv entry; + memcpy (&entry, &(srvaddr[i]), sizeof (struct dns_srv)); + memmove (&(srvaddr[j+1]), &(srvaddr[j]), sizeof (struct dns_srv) * (i - j)); + memcpy (&(srvaddr[j]), &entry, sizeof (struct dns_srv)); +} + +/* + * Given a vector of addresses with priorities and weights, sort them + * according to RFC 2782.. + */ + +void dns_srv_sort (struct dns_srv* srvaddr, int n) +{ + int i; + int j; + int prio; + int sum; + int wrand; + dns_srv_sort_priority (srvaddr, n); + prio = 0; + for (j = 0; j < n;) + { + sum = 0; + /* Compute the sum of weights for the priority prio */ + for (i = j; i < n && srvaddr[i].priority == prio; i++) + { + sum += srvaddr[i].weight; + } + /* If there is no more nodes with priority prio, get next prio */ + if (i == j && srvaddr[i].priority > prio) + { + prio = srvaddr[i].priority; + } + else + { + while (sum > 0) + { + wrand = random_int_range (0, sum + 1); + for (i = j; i < n && srvaddr[i].weight < wrand; i++) + { + wrand -= srvaddr[i].weight; + } + assert (i < n); + assert (srvaddr[i].priority == prio); + dns_srv_switch (srvaddr, j, i); + sum -= srvaddr[j].weight; + j++; + } + /* Those remaining addresses with weight 0 */ + for (i = j; i < n && srvaddr[i].priority == prio; i++, j++); + } + } +} + +#ifdef TEST +/* + * A test, should be put on another file and built and run with make + * tests. One issue is that verifying full correctness is not + * possible, since this should be random. However, addresses with + * different priorities have an order that should be respected and are + * possible to test. + */ +int main (int argc, char** argv) +{ + int i; + struct dns_rr_srv* rr; + struct dns_srv* srv; + char* domain = "holoscopio.com."; + if (argc > 1) + domain = argv[1]; + dns_init (1); + rr = dns_resolve_srv (NULL, domain, "xmpp-client", "tcp", 0); + if (rr == NULL) + { + printf ("No results.\n"); + exit (0); + } + printf ("Before sorting:\n"); + for (i = 0; i < rr->dnssrv_nrr; i++) + { + srv = &(rr->dnssrv_srv[i]); + printf ("%s %d %d %d\n", srv->name, srv->port, srv->priority, srv->weight); + } + srandom (time (0)); + dns_srv_sort (rr->dnssrv_srv, rr->dnssrv_nrr); + printf ("\nAfter sorting:\n"); + for (i = 0; i < rr->dnssrv_nrr; i++) + { + srv = &(rr->dnssrv_srv[i]); + printf ("%s %d %d %d\n", srv->name, srv->port, srv->priority, srv->weight); + } + free (rr); + return 0; +} +#endif diff --git a/sort_udns.h b/sort_udns.h new file mode 100644 index 0000000..7db89a8 --- /dev/null +++ b/sort_udns.h @@ -0,0 +1,25 @@ +/* + * Copyright (C) 2008 Thadeu Lima de Souza Cascardo + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 2 of the License, or + * (at your option) any later version. + * + * This program 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. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see . + * + */ + +#ifndef SORT_UDNS_H +#define SORT_UDNS_H + +void dns_srv_sort (struct dns_srv* srvaddr, int n); + +#endif + -- 2.20.1