Bug 243213 - [RHEL4] Sortlist option of resolv.conf does not return entries in a balanced fashion
[RHEL4] Sortlist option of resolv.conf does not return entries in a balanced ...
Status: CLOSED NOTABUG
Product: Red Hat Enterprise Linux 4
Classification: Red Hat
Component: glibc (Show other bugs)
4.2
All Linux
low Severity high
: ---
: ---
Assigned To: Jeff Law
:
Depends On:
Blocks:
  Show dependency treegraph
 
Reported: 2007-06-07 18:12 EDT by jrichardson
Modified: 2016-11-24 10:57 EST (History)
4 users (show)

See Also:
Fixed In Version:
Doc Type: Bug Fix
Doc Text:
Story Points: ---
Clone Of:
Environment:
Last Closed: 2012-01-24 23:50:20 EST
Type: ---
Regression: ---
Mount Type: ---
Documentation: ---
CRM:
Verified Versions:
Category: ---
oVirt Team: ---
RHEL 7.3 requirements from Atomic Host:
Cloudforms Team: ---


Attachments (Terms of Use)

  None (edit)
Description jrichardson 2007-06-07 18:12:21 EDT
Description of problem:
When performing a lookup of a RR rrset in DNS with the sortlist option specified
in resolv.conf the resolver appears to "prefer" the specific hosts over others.
I'm not sure if it is picking the 1st result in a specific network returned or
the lowest IP'ed or not.

Version-Release number of selected component (if applicable):
~]# rpm -qa bind-libs
bind-libs-9.2.4-2


How reproducible:
Always

Steps to Reproduce:
1. Create a RR entry in DNS that spans multiple networks. For Example:
rrtest   IN A 192.168.1.1
rrtest   IN A 192.168.1.2
rrtest   IN A 192.168.1.3
;... (add needed entries) ...
rrtest   IN A 192.168.2.1
rrtest   IN A 192.168.2.2
rrtest   IN A 192.168.2.3
;... (add needed entries) ...

2. Update /etc/resolv.conf with the sortlist option
   sortlist 192.168.1.0/255.255.255.0 
This should tell the resolver to prefer networks in 192.168.1.0/24 over
192.168.2.0/24
3. Test name lookups
  
Actual results:
To test this, I wrote a little for loop:

[root@myhost ~]# for i in `seq 1 100`; do ping -c 1 rrtest.mydomain.tld; done |
grep icmp_seq | awk '{print $5;'} | sort | uniq -c
     63 (192.168.1.1):
      6 (192.168.1.2):
      8 (192.168.1.3):
      7 (192.168.1.4):
      6 (192.168.1.5):
     10 (192.168.1.6):
[root@myhost ~]# for i in `seq 1 100`; do ping -c 1 rrtest.mydomain.tld; done |
grep icmp_seq | awk '{print $5;'} | sort | uniq -c
     70 (192.168.1.1):
      6 (192.168.1.2):
     10 (192.168.1.3):
      2 (192.168.1.4):
      8 (192.168.1.5):
      4 (192.168.1.6):
[root@myhost ~]# for i in `seq 1 100`; do ping -c 1 rrtest.mydomain.tld; done |
grep icmp_seq | awk '{print $5;'} | sort | uniq -c
     61 (192.168.1.1):
      5 (192.168.1.2):
      9 (192.168.1.3):
     13 (192.168.1.4):
      4 (192.168.1.5):
      8 (192.168.1.6):
[root@myhost ~]# for i in `seq 1 100`; do ping -c 1 rrtest.mydomain.tld; done |
grep icmp_seq | awk '{print $5;'} | sort | uniq -c
     63 (192.168.1.1):
      7 (192.168.1.2):
      9 (192.168.1.3):
      6 (192.168.1.4):
      8 (192.168.1.5):
      7 (192.168.1.6):
[root@myhost ~]# for i in `seq 1 100`; do ping -c 1 rrtest.mydomain.tld; done |
grep icmp_seq | awk '{print $5;'} | sort | uniq -c
     49 (192.168.1.1):
      5 (192.168.1.2):
     12 (192.168.1.3):
     14 (192.168.1.4):
     11 (192.168.1.5):
      9 (192.168.1.6):


Expected results:
I expected the results to be equally as balanced just as when not using the sort
list. For example, without the sortlist here is the results from the above test:
[root@myhost ~]# for i in `seq 1 100`; do ping -c 1 rrtest.mydomain.tld; done |
grep icmp_seq | awk '{print $5;'} | sort | uniq -c
      3 (192.168.1.1):
      6 (192.168.1.2):
     10 (192.168.1.3):
     11 (192.168.1.4):
     11 (192.168.1.5):
      5 (192.168.1.6):
      7 (192.168.2.1):
     13 (192.168.2.2):
      8 (192.168.2.3):
      6 (192.168.2.4):
      7 (192.168.2.5):
     13 (192.168.2.6):
[root@myhost ~]# for i in `seq 1 100`; do ping -c 1 rrtest.mydomain.tld; done |
grep icmp_seq | awk '{print $5;'} | sort | uniq -c
      8 (192.168.1.1):
      5 (192.168.1.2):
     12 (192.168.1.3):
      4 (192.168.1.4):
      6 (192.168.1.5):
      9 (192.168.1.6):
      9 (192.168.2.1):
     10 (192.168.2.2):
     10 (192.168.2.3):
      9 (192.168.2.4):
      8 (192.168.2.5):
     10 (192.168.2.6):
[root@myhost ~]# for i in `seq 1 100`; do ping -c 1 rrtest.mydomain.tld; done |
grep icmp_seq | awk '{print $5;'} | sort | uniq -c
     12 (192.168.1.1):
      9 (192.168.1.2):
      7 (192.168.1.3):
     12 (192.168.1.4):
      7 (192.168.1.5):
     10 (192.168.1.6):
      8 (192.168.2.1):
      5 (192.168.2.2):
      8 (192.168.2.3):
     12 (192.168.2.4):
      6 (192.168.2.5):
      4 (192.168.2.6):
[root@myhost ~]# for i in `seq 1 100`; do ping -c 1 rrtest.mydomain.tld; done |
grep icmp_seq | awk '{print $5;'} | sort | uniq -c
      8 (192.168.1.1):
     11 (192.168.1.2):
      4 (192.168.1.3):
     10 (192.168.1.4):
      8 (192.168.1.5):
     13 (192.168.1.6):
      6 (192.168.2.1):
      6 (192.168.2.2):
     11 (192.168.2.3):
      7 (192.168.2.4):
      7 (192.168.2.5):
      9 (192.168.2.6):
[root@myhost ~]# for i in `seq 1 100`; do ping -c 1 rrtest.mydomain.tld; done |
grep icmp_seq | awk '{print $5;'} | sort | uniq -c
     14 (192.168.1.1):
      4 (192.168.1.2):
      8 (192.168.1.3):
     11 (192.168.1.4):
      5 (192.168.1.5):
      9 (192.168.1.6):
     11 (192.168.2.1):
     11 (192.168.2.2):
      6 (192.168.2.3):
      5 (192.168.2.4):
     10 (192.168.2.5):
      6 (192.168.2.6):

Notice how the results are much more balanced across hosts?

Additional info: 

I initially thought this may be tied to the small number of hosts in these two
networks, this test only shows 6 hosts in each network; however I have done the
same test with a 48-host RR dns entry (24 hosts in two networks) and the result
is the same.
Comment 1 Adam Tkac 2007-06-08 07:15:21 EDT
Sounds like glibc resolver problem for me. Reassigning to proper component

Adam
Comment 2 jrichardson 2007-06-08 09:26:07 EDT
Please let me know what additional information is requried for troubleshooting.
Thanks
Comment 3 Jakub Jelinek 2007-06-08 09:55:26 EDT
Can't reproduce.
The only place that uses _res.nsort and _res.sort_list in libnss_dns.so.2
is:
      if (_res.nsort && haveanswer > 1 && qtype == T_A)
        addrsort (host_data->h_addr_ptrs, haveanswer);
and that certainly doesn't decrease randomization within each sort_list class.

Try:
#include <assert.h>
#include <string.h>
#include <stdlib.h>
#include <netinet/in.h>
#include <resolv.h>
#include <arpa/inet.h>
#include <sys/socket.h>
#include <time.h>
#define MAX_NR_ADDRS 35

static void addrsort (char **ap, int num);

static void
addrsort (char **ap, int num)
{
  int i, j;
  char **p;
  short aval[MAX_NR_ADDRS];
  int needsort = 0;

  p = ap;
  if (num > MAX_NR_ADDRS)
    num = MAX_NR_ADDRS;
  for (i = 0; i < num; i++, p++)
    {
      for (j = 0 ; (unsigned)j < _res.nsort; j++)
        if (_res.sort_list[j].addr.s_addr ==
            (((struct in_addr *)(*p))->s_addr & _res.sort_list[j].mask))
          break;
      aval[i] = j;
      if (needsort == 0 && i > 0 && j < aval[i-1])
        needsort = i;
    }
  if (!needsort)
    return;

  while (needsort++ < num)
    for (j = needsort - 2; j >= 0; j--)
      if (aval[j] > aval[j+1])
        {
          char *hp;

          i = aval[j];
          aval[j] = aval[j+1];
          aval[j+1] = i;

          hp = ap[j];
          ap[j] = ap[j+1];
          ap[j+1] = hp;
        }
      else
        break;
}

int
main (void)
{
  struct in_addr v[12];
  char *w[12];
  int first[12];
  int i, j, k, n;
  int mask;
  memset (first, 0, sizeof (first));
  _res.nsort = 1;
  _res.sort_list[0].addr = (struct in_addr) { .s_addr = htonl (0xc0a80100) };
  _res.sort_list[0].mask = htonl (0xffffff00);
  srandom (time (NULL));
  for (i = 0; i < 12; i++)
    v[i].s_addr = htonl (0xc0a80101 + (i % 6) + (i >= 6 ? 0x100 : 0));
  for (k = 0; k < 100000; k++)
    {
      mask = (1 << 12) - 1;
      for (i = 0; i < 12; i++)
        {
          n = random () % (12 - i);
          for (j = 0; j < 12; j++)
            if (mask & (1 << j))
              if (n-- == 0)
                break;
          assert (j < 12);
          w[i] = (char *) &v[j];
          mask &= ~(1 << j);
        }
      addrsort (w, 12);
      first [((struct in_addr *) w[0]) - &v[0]]++;
    }
  /* for (i = 0; i < 12; i++)
    printf ("n %d %s\n", i, inet_ntoa (*(struct in_addr *)w[i])); */
  for (i = 0; i < 12; i++)
    printf ("%d %d\n", i, first[i]);
  return 0;
}

(which has a copy of RHEL4's libc/resolv/nss_dns/dns-host.c's addrsort) and
you'll see that it is distributed roughly equally.
Comment 4 jrichardson 2007-06-08 10:13:14 EDT
Can you explain the non-distributed results from the above test? Could it not
being using this sort method?

Can you summarize (breifly) the program above and what the output means?
Comment 5 jrichardson 2007-06-08 14:31:29 EDT
My results from running the test....


[root@myhost ~]# for i in `seq 1 10`; do echo "Running test" ;./rhtest ; sleep
3; echo ; done ;
Running test
0 16943
1 16554
2 16624
3 16458
4 16743
5 16678
6 0
7 0
8 0
9 0
10 0
11 0

Running test
0 16735
1 16606
2 16571
3 16710
4 16740
5 16638
6 0
7 0
8 0
9 0
10 0
11 0

Running test
0 16560
1 16545
2 16691
3 16917
4 16636
5 16651
6 0
7 0
8 0
9 0
10 0
11 0

Running test
0 16758
1 16730
2 16703
3 16508
4 16530
5 16771
6 0
7 0
8 0
9 0
10 0
11 0

Running test
0 16626
1 16746
2 16551
3 16686
4 16714
5 16677
6 0
7 0
8 0
9 0
10 0
11 0

Running test
0 16444
1 16749
2 16660
3 16764
4 16764
5 16619
6 0
7 0
8 0
9 0
10 0
11 0

Running test
0 16617
1 16615
2 16720
3 16663
4 16586
5 16799
6 0
7 0
8 0
9 0
10 0
11 0

Running test
0 16552
1 16576
2 16655
3 16801
4 16708
5 16708
6 0
7 0
8 0
9 0
10 0
11 0

Running test
0 16630
1 16666
2 16723
3 16668
4 16797
5 16516
6 0
7 0
8 0
9 0
10 0
11 0

Running test
0 16661
1 16650
2 16721
3 16657
4 16680
5 16631
6 0
7 0
8 0
9 0
10 0
11 0
Comment 6 Jakub Jelinek 2007-06-11 07:48:44 EDT
The program simulates the conditions you reported - it applies the sort
function that libnss_dns.so is using on randomly permutated 12 IPs you mentioned
above (i.e. what DNS servers ought to return) and shows how many times each of
the IPs was returned as first (i.e. one that will be picked up by gethostbyname).
IPs 6 through 11 are supposed to be never seen there, as they have lower
priority, and the other IPs are seen roughl the same number of times.

Besides code to initialize _res.nsort and _res.sort_list from /etc/resolv.conf's
sortlist the above sort function is the only place that uses these 2 vars, so
no, it can't use any other sort method if you can exhibit it only with sortlist
in resolv.conf and not without that.
Comment 7 jrichardson 2007-06-11 11:53:58 EDT
I can see that the results from your application validate the sorting algorithm,
however, do you still see that the real-world output above is not consistent
with the results of the the sort alogorithm? *Something* is happening somewhere
to make this not random and the bug may not exist in the sorting algorithm, but
it does exist somewhere.
Comment 8 Adam Tkac 2007-07-20 07:03:57 EDT
Hm, I'm not sure what exactly you expected. You want sorted output from resolver
(addresses are ping-ed from min to max for example) or load-balanced output
(addresses are ping-ed in random sequence)?

Adam
Comment 9 jrichardson 2007-07-20 10:21:56 EDT
My expectation was to have a randomized rrset that listed all addresses from one
network before another. Since I was unable to achieve this using the client-side
resolv.conf sortlist option, I implemented this on my DNS servers (running Bind
9.4.0-3.

When a client does a lookup for a for a rrset it will sort the returned list of
addresses to the client based on the network that the clients are in.

For example, I have a DNS rrset that consists of the following:

test                     IN      A       172.21.15.1
test                     IN      A       172.21.15.3
test                     IN      A       172.21.15.5
test                     IN      A       172.21.15.7
test                     IN      A       172.21.15.9
test                     IN      A       172.21.15.11
test                     IN      A       172.21.15.13
test                     IN      A       172.21.15.15
test                     IN      A       172.21.15.17
test                     IN      A       172.21.15.19
test                     IN      A       172.21.15.21
test                     IN      A       172.21.15.23
test                     IN      A       172.21.15.25
test                     IN      A       172.21.15.27
test                     IN      A       172.21.15.29
test                     IN      A       172.21.15.31
test                     IN      A       172.21.15.33
test                     IN      A       172.21.15.35
test                     IN      A       172.21.15.37
test                     IN      A       172.21.15.39
test                     IN      A       172.21.15.41
test                     IN      A       172.21.15.43
test                     IN      A       172.21.15.45
test                     IN      A       172.21.15.47
test                     IN      A       172.30.252.201
test                     IN      A       172.30.252.202
test                     IN      A       172.30.252.203
test                     IN      A       172.30.252.204
test                     IN      A       172.30.252.205
test                     IN      A       172.30.252.206
test                     IN      A       172.30.252.207
test                     IN      A       172.30.252.208
test                     IN      A       172.30.252.209
test                     IN      A       172.30.252.210
test                     IN      A       172.30.252.211
test                     IN      A       172.30.252.212
test                     IN      A       172.30.252.213
test                     IN      A       172.30.252.214
test                     IN      A       172.30.252.215
test                     IN      A       172.30.252.216
test                     IN      A       172.30.252.217
test                     IN      A       172.30.252.218
test                     IN      A       172.30.252.219
test                     IN      A       172.30.252.220
test                     IN      A       172.30.252.221
test                     IN      A       172.30.252.222
test                     IN      A       172.30.252.223
test                     IN      A       172.30.252.224


Using the sortlist option, I should be able to 'sort' the results based on
networks. I want all my hosts on 172.30.0.0/16 to use the 172.30.252.* hosts. By
specifying the sortlist parameter in resolv.conf this "sorta" works. See above
results how "most" of the time the first result return in the rrset is the same.

By configuring the sortlist option on the server side; you basically say
"requests coming from network a.b.c.d/ee prefer the network f.g.h.i/kk"; this
works as intended:

myclient# host test
test.mydomain.tld has address 172.30.252.223
test.mydomain.tld has address 172.30.252.218
test.mydomain.tld has address 172.30.252.214
test.mydomain.tld has address 172.30.252.213
test.mydomain.tld has address 172.30.252.209
test.mydomain.tld has address 172.30.252.201
test.mydomain.tld has address 172.30.252.221
test.mydomain.tld has address 172.30.252.208
test.mydomain.tld has address 172.30.252.211
test.mydomain.tld has address 172.30.252.219
test.mydomain.tld has address 172.30.252.215
test.mydomain.tld has address 172.30.252.206
test.mydomain.tld has address 172.30.252.224
test.mydomain.tld has address 172.30.252.212
test.mydomain.tld has address 172.30.252.217
test.mydomain.tld has address 172.30.252.203
test.mydomain.tld has address 172.30.252.220
test.mydomain.tld has address 172.30.252.207
test.mydomain.tld has address 172.30.252.210
test.mydomain.tld has address 172.30.252.222
test.mydomain.tld has address 172.30.252.216
test.mydomain.tld has address 172.30.252.204
test.mydomain.tld has address 172.30.252.202
test.mydomain.tld has address 172.30.252.205
test.mydomain.tld has address 172.21.15.39
test.mydomain.tld has address 172.21.15.13
test.mydomain.tld has address 172.21.15.19
test.mydomain.tld has address 172.21.15.23
test.mydomain.tld has address 172.21.15.17
test.mydomain.tld has address 172.21.15.25
test.mydomain.tld has address 172.21.15.15
test.mydomain.tld has address 172.21.15.9
test.mydomain.tld has address 172.21.15.41
test.mydomain.tld has address 172.21.15.45
test.mydomain.tld has address 172.21.15.43
test.mydomain.tld has address 172.21.15.37
test.mydomain.tld has address 172.21.15.5
test.mydomain.tld has address 172.21.15.29
test.mydomain.tld has address 172.21.15.7
test.mydomain.tld has address 172.21.15.21
test.mydomain.tld has address 172.21.15.1
test.mydomain.tld has address 172.21.15.27
test.mydomain.tld has address 172.21.15.31
test.mydomain.tld has address 172.21.15.11
test.mydomain.tld has address 172.21.15.3
test.mydomain.tld has address 172.21.15.35
test.mydomain.tld has address 172.21.15.33
test.mydomain.tld has address 172.21.15.47
Comment 10 Adam Tkac 2007-07-20 11:41:54 EDT
If I understand correctly you want when client is from 192.168.1.0/24 then named
serve addresses from for example 192.168.1.0/24 range and when client is from
192.168.2.0/24 then named could reply with RRs from 192.168.100.0/24 range
(example). If yes, you're completely wrong. Resolver (and his /etc/resolv.conf
configfile) is only asking nameserver for correct response. So if you specify
sortlist option on server side it only affects behavior when someone on server
side asks through gethostbyname function.
When your clients asks nameserver for RRs server doesn't use resolver (because
communication between servers/finding RRs in database is far more sophisticated
than simple ask and get answer). You have to configure your server correctly.
Please see BIND9 ARM (http://www.isc.org/index.pl?/sw/bind/arm94/), especially
statement about views (6. BIND 9 Configuration Reference -> view). Does it help you?

Adam
Comment 11 Adam Tkac 2007-07-20 11:45:39 EDT
And I've seen you're using bind 9.4.0 series. It has security bug which allows
DoS attack (CVE-2007-2241). I recommend you update to 9.4.1

Adam

Note You need to log in before you can comment on or make changes to this bug.