sort_udns.c

   1 /*
   2  * Copyright (C) 2008  Thadeu Lima de Souza Cascardo <cascardo@holoscopio.com>
   3  *
   4  * This program is free software: you can redistribute it and/or modify
   5  * it under the terms of the GNU General Public License as published by
   6  * the Free Software Foundation, either version 2 of the License, or
   7  * (at your option) any later version.
   8  *
   9  * This program is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  * GNU General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program.  If not, see <http://www.gnu.org/licenses/>.
  16  *
  17  */
  18
  19 #include <udns.h>
  20 #include <stdio.h>
  21 #include <stdlib.h>
  22 #include <string.h>
  23 #include <time.h>
  24 #include <assert.h>
  25
  26 /*
  27  * Our own implementation of random integer numbers in a range.
  28  */
  29 static int random_int_range (int start, int end)
  30 {
  31   long long r;
  32   int range = end - start;
  33   r = random () * range;
  34   r = r / RAND_MAX;
  35   return start + r;
  36 }
  37
  38 /*
  39  * Since we implement the proposed algorithm from RFC 2782, entries
  40  * with weight 0 should come before those with non-zero weight.
  41  */
  42 static int dns_srv_compare (const void* a, const void* b)
  43 {
  44   struct dns_srv* addr_a = (struct dns_srv*) a;
  45   struct dns_srv* addr_b = (struct dns_srv*) b;
  46   if (addr_a->priority != addr_b->priority)
  47     return addr_a->priority - addr_b->priority;
  48   if (addr_b->weight == 0)
  49     return 1;
  50   else if (addr_a->weight == 0)
  51     return -1;
  52   return 0;
  53 }
  54
  55 /*
  56  * Order a vector of addresses with priorities and weights by priority
  57  * putting those with weight 0 at the start of those with the same
  58  * priority.
  59  */
  60 static void dns_srv_sort_priority (void* srvaddr, int n)
  61 {
  62   qsort (srvaddr, n, sizeof (struct dns_srv), dns_srv_compare);
  63 }
  64
  65 /*
  66  * Move entries between j and i one position forward and move i to j
  67  * position.
  68  */
  69 static void dns_srv_switch (struct dns_srv* srvaddr, int j, int i)
  70 {
  71   struct dns_srv entry;
  72   memcpy (&entry, &(srvaddr[i]), sizeof (struct dns_srv));
  73   memmove (&(srvaddr[j+1]), &(srvaddr[j]), sizeof (struct dns_srv) * (i - j));
  74   memcpy (&(srvaddr[j]), &entry, sizeof (struct dns_srv));
  75 }
  76
  77 /*
  78  * Given a vector of addresses with priorities and weights, sort them
  79  * according to RFC 2782..
  80  */
  81
  82 void hc_dns_srv_sort (struct dns_srv* srvaddr, int n)
  83 {
  84   int i;
  85   int j;
  86   int prio;
  87   int sum;
  88   int wrand;
  89   dns_srv_sort_priority (srvaddr, n);
  90   prio = 0;
  91   for (j = 0; j < n;)
  92     {
  93       sum = 0;
  94       /* Compute the sum of weights for the priority prio */
  95       for (i = j; i < n && srvaddr[i].priority == prio; i++)
  96         {
  97           sum += srvaddr[i].weight;
  98         }
  99       /* If there is no more nodes with priority prio, get next prio */
 100       if (i == j && srvaddr[i].priority > prio)
 101         {
 102           prio = srvaddr[i].priority;
 103         }
 104       else
 105         {
 106           while (sum > 0)
 107             {
 108               wrand = random_int_range (0, sum + 1);
 109               for (i = j; i < n && srvaddr[i].weight < wrand; i++)
 110                 {
 111                   wrand -= srvaddr[i].weight;
 112                 }
 113               assert (i < n);
 114               assert (srvaddr[i].priority == prio);
 115               dns_srv_switch (srvaddr, j, i);
 116               sum -= srvaddr[j].weight;
 117               j++;
 118             }
 119           /* Those remaining addresses with weight 0 */
 120           for (i = j; i < n && srvaddr[i].priority == prio; i++, j++);
 121         }
 122     }
 123 }
 124
 125 #ifdef TEST
 126 /*
 127  * A test, should be put on another file and built and run with make
 128  * tests. One issue is that verifying full correctness is not
 129  * possible, since this should be random. However, addresses with
 130  * different priorities have an order that should be respected and are
 131  * possible to test.
 132  */
 133 int main (int argc, char** argv)
 134 {
 135   int i;
 136   struct dns_rr_srv* rr;
 137   struct dns_srv* srv;
 138   char* domain = "holoscopio.com.";
 139   if (argc > 1)
 140     domain = argv[1];
 141   dns_init (NULL, 1);
 142   rr = dns_resolve_srv (NULL, domain, "xmpp-client", "tcp", 0);
 143   if (rr == NULL)
 144     {
 145       printf ("No results.\n");
 146       exit (0);
 147     }
 148   printf ("Before sorting:\n");
 149   for (i = 0; i < rr->dnssrv_nrr; i++)
 150     {
 151       srv = &(rr->dnssrv_srv[i]);
 152       printf ("%s %d %d %d\n", srv->name, srv->port, srv->priority, srv->weight);
 153     }
 154   srandom (time (0));
 155   hc_dns_srv_sort (rr->dnssrv_srv, rr->dnssrv_nrr);
 156   printf ("\nAfter sorting:\n");
 157   for (i = 0; i < rr->dnssrv_nrr; i++)
 158     {
 159       srv = &(rr->dnssrv_srv[i]);
 160       printf ("%s %d %d %d\n", srv->name, srv->port, srv->priority, srv->weight);
 161     }
 162   free (rr);
 163   return 0;
 164 }
 165 #endif