[net/dns] Resolve AF_UNSPEC on dual-stacked systems. Sort addresses according to RFC3484.

net/dns/address_sorter_posix.cc

+// Copyright (c) 2012 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "net/dns/address_sorter.h"
+
+#include <stdint.h>
+#include <netinet/in.h>
+
+#include <algorithm>
+#include <map>
+#include <vector>
+
+#include "base/eintr_wrapper.h"
+#include "base/logging.h"
+#include "base/memory/scoped_vector.h"
+#include "net/base/address_list.h"
+#include "net/base/network_change_notifier.h"
+#include "net/base/net_errors.h"
+#include "net/base/net_util.h"
+#include "net/socket/client_socket_factory.h"
+#include "net/udp/datagram_client_socket.h"
+
+namespace net {
+
+namespace {
+
+// TODO(szym): Document general approach.
+// http://tools.ietf.org/html/draft-ietf-6man-rfc3484bis-03
+
+// Generic policy entry.
+struct PolicyEntry {
+  // IPv4 addresses must be mapped to IPv6.
+  unsigned char prefix[kIPv6AddressSize];
+  unsigned prefix_length;
+  unsigned value;
+};
+
+typedef std::vector<PolicyEntry> PolicyTable;
+
+// Sort table by decreasing prefix size to allow longest prefix matching.
+bool ComparePolicy(const PolicyEntry& a, const PolicyEntry& b) {
+  return a.prefix_length > b.prefix_length;
+}
+
+// Creates sorted PolicyTable from |table| with |size| entries.
+PolicyTable LoadPolicy(PolicyEntry* table, size_t size) {
+  PolicyTable result(table, table + size);
+  std::sort(result.begin(), result.end(), ComparePolicy);
+  return result;
+}
+
+// Search |table| for matching prefix of |address|. |table| must be sorted by
+// descending prefix (prefix of another prefix must be later in table).
+unsigned GetPolicyValue(const PolicyTable& table,
+                        const IPAddressNumber& address) {
+  if (address.size() == kIPv4AddressSize)
+    return GetPolicyValue(table, ConvertIPv4NumberToIPv6Number(address));
+  for (unsigned i = 0; i < table.size(); ++i) {
+    const PolicyEntry& entry = table[i];
+    IPAddressNumber prefix(entry.prefix, entry.prefix + kIPv6AddressSize);
+    if (IPNumberMatchesPrefix(address, prefix, entry.prefix_length))
+      return entry.value;
+  }
+  NOTREACHED();
+  // The last entry is the least restrictive, so assume it's default.
+  return table.back().value;
+}
+
+enum AddressScope {
+  SCOPE_NODELOCAL = 1,
+  SCOPE_LINKLOCAL = 2,
+  SCOPE_SITELOCAL = 5,
+  SCOPE_ORGLOCAL = 8,
+  SCOPE_GLOBAL = 14,
+};
+
+bool IsMulticast(const IPAddressNumber& address) {
+  return address[0] == 0xFF;
+}
+
+AddressScope GetMulticastScope(const IPAddressNumber& address) {
+  return static_cast<AddressScope>(address[1] & 0x0F);
+}
+
+bool IsIPv6Loopback(const IPAddressNumber& address) {
+  // IN6_IS_ADDR_LOOPBACK
+  unsigned char kLoopback[kIPv6AddressSize] = {
+      0, 0, 0, 0, 0, 0, 0, 0,
+      0, 0, 0, 0, 0, 0, 0, 1,
+  };
+  return address == IPAddressNumber(kLoopback, kLoopback + kIPv6AddressSize);
+}
+
+bool IsLinkLocal(const IPAddressNumber& address) {
+  // IN6_IS_ADDR_LINKLOCAL
+  return (address[0] == 0xFE) && ((address[1] & 0xC0) == 0x80);
+}
+
+bool IsSiteLocal(const IPAddressNumber& address) {
+  // IN6_IS_ADDR_SITELOCAL
+  return (address[0] == 0xFE) && ((address[1] & 0xC0) == 0xC0);
+}
+
+AddressScope GetScope(const PolicyTable& table,
+                      const IPAddressNumber& address) {
+  if (address.size() == kIPv6AddressSize) {
+    if (IsMulticast(address)) {
+      return GetMulticastScope(address);
+    } else if (IsIPv6Loopback(address) || IsLinkLocal(address)) {
+      return SCOPE_LINKLOCAL;
+    } else if (IsSiteLocal(address)) {
+      return SCOPE_SITELOCAL;
+    } else {
+      return SCOPE_GLOBAL;
+    }
+  } else if (address.size() == kIPv4AddressSize) {
+    return static_cast<AddressScope>(GetPolicyValue(table, address));
+  } else {
+    NOTREACHED();
+    return SCOPE_NODELOCAL;
+  }
+}
+
+// Default policy table. RFC 3484, Section 2.1.
+// Updated for glibc: http://www.akkadia.org/drepper/linux-rfc3484.html
+// Precedence and label are separate to support /etc/gai.conf.
+PolicyEntry kDefaultPrecedenceTable[] = {
+  // ::1/128 -- loopback
+  { { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 }, 128, 60 },
+  // fc00::/7 -- multicast
+  { { 0xFC }, 7, 50 },
+  // ::/0 -- any
+  { { }, 0, 40 },
+  // ::ffff:0:0/96 -- IPv4 mapped
+  { { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0xFF, 0xFF }, 96, 30 },
+  // 2002::/16 -- 6to4
+  { { 0x20, 0x02, }, 17, 20 },
+  // 2001::/32 -- Teredo
+  { { 0x20, 0x01, 0, 0 }, 32, 10 },
+  // ::/96 -- IPv4 compatible
+  { { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, 96, 1 },
+  // fec0::/16 -- unique local address
+  { { 0xFE, 0xC0 }, 16, 1 },
+  // 3ffe::/16 -- 6bone
+  { { 0x3F, 0xFE }, 16, 1 },
+};
+
+PolicyEntry kDefaultLabelTable[] = {
+  // ::1/128 -- loopback
+  { { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 }, 128, 0 },
+  // fc00::/7 -- multicast
+  { { 0xFC }, 7, 1 },
+  // ::/0 -- any
+  { { }, 0, 2 },
+  // ::ffff:0:0/96 -- IPv4 mapped
+  { { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0xFF, 0xFF }, 96, 3 },
+  // 2002::/16 -- 6to4
+  { { 0x20, 0x02, }, 17, 4 },
+  // 2001::/32 -- Teredo
+  { { 0x20, 0x01, 0, 0 }, 32, 5 },
+  // ::/96 -- IPv4 compatible
+  { { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, 96, 10 },
+  // fec0::/16 -- unique local address
+  { { 0xFE, 0xC0 }, 16, 11 },
+  // 3ffe::/16 -- 6bone
+  { { 0x3F, 0xFE }, 16, 12 },
+};
+
+// Default mapping of IPv4 addresses to scope.
+PolicyEntry kDefaultScopeTable[] = {
+  { { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0xFF, 0xFF, 0x7F }, 104,
+      SCOPE_LINKLOCAL },

[mmenke, 2012/06/07 18:32:34]

nit:  Think this and the next one both fit on one line.

+  { { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0xFF, 0xFF, 0xA9, 0xFE }, 112,
+      SCOPE_LINKLOCAL },
+  { { }, 0, SCOPE_GLOBAL },
+};
+
+// Returns number of matching initial bits between the addresses |a1| and |a2|.
+unsigned CommonPrefixLength(const IPAddressNumber& a1,
+                            const IPAddressNumber& a2) {
+  DCHECK_EQ(a1.size(), a2.size());
+  for (size_t i = 0; i < a1.size(); ++i) {
+    unsigned diff = a1[i] ^ a2[i];
+    if (!diff)
+      continue;
+    for (unsigned j = 0; j < CHAR_BIT; ++j) {
+      if (diff & (1 << (CHAR_BIT - 1)))
+        return i * CHAR_BIT + j;
+      diff <<= 1;
+    }
+  }
+  return a1.size() * CHAR_BIT;
+}
+
+struct SourceAddressInfo {
+  AddressScope scope;
+  unsigned label;
+  // Only needed if more than one source address in the list.
+  unsigned prefix_length;
+  bool deprecated;  // vs. preferred RFC4862
+  bool home;        // vs. care-of RFC6275
+  bool native;
+};
+
+typedef std::map<IPAddressNumber, SourceAddressInfo> SourceAddressMap;
+
+struct SortElement {
+  IPAddressNumber address;
+  AddressScope scope;
+  unsigned precedence;
+  unsigned label;
+  const SourceAddressInfo* src;
+  unsigned common_prefix_length;
+};
+
+// RFC 3484, section 6.
+bool CompareRFC3484(const SortElement* a1, const SortElement* a2) {
+  // Rule 1: Avoid unusable destinations.
+  // Unusable destinations are already filtered out.
+
+  // Rule 2: Prefer matching scope.
+  bool scope_match1 = (a1->src->scope == a1->scope);
+  bool scope_match2 = (a2->src->scope == a2->scope);
+  if (scope_match1 != scope_match2)
+    return scope_match1;
+
+  // Rule 3: Avoid deprecated addresses.
+  if (a1->src->deprecated != a2->src->deprecated)
+    return !a1->src->deprecated;
+
+  // Rule 4: Prefer home addresses.
+  if (a1->src->home != a2->src->home)
+      return !a1->src->home;
+
+  // Rule 5: Prefer matching label.
+  bool label_match1 = (a1->src->label == a1->label);
+  bool label_match2 = (a2->src->label == a2->label);
+  if (label_match1 != label_match2)
+    return label_match1;
+
+  // Rule 6: Prefer higher precedence.
+  if (a1->precedence != a2->precedence)
+    return a1->precedence > a2->precedence;
+
+  // Rule 7: Prefer native transport.
+  if (a1->src->native != a2->src->native)
+    return !a1->src->native;
+
+  // Rule 8: Prefer smaller scope.
+  if (a1->scope != a2->scope)
+    return a1->scope < a2->scope;
+
+  // Rule 9: Use longest matching prefix.
+  if (a1->address.size() == a2->address.size()) {
+    if (a1->common_prefix_length != a1->common_prefix_length)
+      return a1->common_prefix_length > a1->common_prefix_length;
+  }
+
+  // Rule 10: Leave the order unchanged.
+  // stable_sort takes care of that.
+  return false;
+}
+
+#if defined(OS_LINUX)
+class SourceAddressTracker : public NetworkChangeNotifier::IPAddressObserver {
+ public:
+  typedef base::Callback<void(const SourceAddressMap&)> Callback;
+  SourceAddressTracker(Callback callback) : callback_(callback) {
+    // TODO: ask for Netlink updates on NEWLINK
+  }
+  virtual ~SourceAddressTracker() {}
+ private:
+  // NetworkChangeNotifier::IPAddressObserver:
+  virtual void OnIPAddressChanged() OVERRIDE {
+    // TODO: ask NetworkChangeNotifier for detailed source info
+  }
+
+  // TODO: Handle NEWLINK updates.
+
+  SourceAddressMap source_info_;
+  Callback callback_;
+};
+
+#endif  // defined(OS_LINUX)
+
+class AddressSorterPosix : public AddressSorter {
+ public:
+  explicit AddressSorterPosix(ClientSocketFactory* socket_factory);
+  ~AddressSorterPosix() {}
+
+  virtual void Sort(AddressList* list) const OVERRIDE;
+
+ private:
+#if defined(OS_LINUX)
+  void OnSourceAddressUpdate(const SourceAddressMap& source_info);
+
+  SourceAddressTracker source_tracker_;
+  SourceAddressMap source_info_;
+  // TODO(szym): remove.
+  SourceAddressInfo mock_source_info_;
+#endif
+
+  ClientSocketFactory* socket_factory_;
+  PolicyTable precedence_table_;
+  PolicyTable label_table_;
+  PolicyTable scope_table_;
+
+  DISALLOW_COPY_AND_ASSIGN(AddressSorterPosix);
+};
+
+AddressSorterPosix::AddressSorterPosix(ClientSocketFactory* socket_factory)
+    :
+#if defined(OS_LINUX)
+      source_tracker_(base::Bind(&AddressSorterPosix::OnSourceAddressUpdate,
+                                 base::Unretained(this))),
+#endif
+      socket_factory_(socket_factory),
+      precedence_table_(LoadPolicy(kDefaultPrecedenceTable,
+                                   arraysize(kDefaultPrecedenceTable))),
+      label_table_(LoadPolicy(kDefaultLabelTable,
+                              arraysize(kDefaultLabelTable))),
+      scope_table_(LoadPolicy(kDefaultScopeTable,
+                              arraysize(kDefaultScopeTable))) {
+#if defined(OS_LINUX)
+  mock_source_info_.scope = SCOPE_GLOBAL;
+  mock_source_info_.deprecated = false;
+  mock_source_info_.home = false;
+  mock_source_info_.native = false;
+  mock_source_info_.label = static_cast<unsigned>(-1);
+  mock_source_info_.prefix_length = 0;
+#endif
+}
+
+bool AddressSorterPosix::Sort(AddressList* list) const {
+  ScopedVector<SortElement> sort_list;
+
+  for (size_t i = 0; i < list->size(); ++i) {
+    scoped_ptr<SortElement> el(new SortElement());
+    el->address = (*list)[i].address();
+    el->scope = GetScope(scope_table_, el->address);
+    el->precedence = GetPolicyValue(precedence_table_, el->address);
+    el->label = GetPolicyValue(label_table_, el->address);
+
+    scoped_ptr<DatagramClientSocket> socket(
+        socket_factory_->CreateDatagramClientSocket(
+            DatagramSocket::DEFAULT_BIND,
+            RandIntCallback(),
+            NULL /* NetLog */,
+            NetLog::Source()));
+
+    if (socket->Connect(IPEndPoint(el->address, 0 /* port */)) != OK)
+      continue;
+    IPEndPoint endpoint;
+    // Filter out unsable destinations.

[mmenke, 2012/06/07 18:32:34]

nit:  unusable.

[mmenke, 2012/06/07 18:32:34]

Also, doesn't this comment also apply to the line above it as well?  At least I
assume it would also catch bad destination addresses.

+    if (socket->GetLocalAddress(&endpoint) != OK);
+      continue;
+#if defined(OS_LINUX)
+    SourceAddressMap::const_iterator it = source_info_.find(endpoint.address());
+    if (it != source_info_.end()) {
+      el->src = &(it->second);
+    } else {
+      // TODO(szym): This should not be possible.

[mmenke, 2012/06/07 18:32:34]

Are you sure about this?  Adapters can be removed/added and the map may not yet
have been updated.

+      el->src = &(mock_source_info_);
+    }
+#elif defined(OS_MACOSX) || defined(OS_BSD)
+    NOTIMPLEMENTED();
+    // TODO(szym): ioctl SIOCGIFFLAGS to get deprecated
+#endif
+
+    if (el->address.size() == endpoint.address().size()) {
+      el->common_prefix_length = std::min(
+          CommonPrefixLength(el->address, endpoint.address()),
+          el->src->prefix_length);
+    }
+    sort_list.push_back(el.release());
+  }
+
+  std::stable_sort(sort_list.begin(), sort_list.end(), CompareRFC3484);
+
+  list->clear();
+  for (size_t i = 0; i < sort_list.size(); ++i) {
+    list->push_back(IPEndPoint(sort_list[i]->address, 0 /* port */));
+  }
+  return true;
+}
+
+#if defined(OS_LINUX)
+void AddressSorterPosix::OnSourceAddressUpdate(
+    const SourceAddressMap& source_info) {
+  source_info_ = source_info;
+}
+#endif
+
+}  // namespace
+
+// static
+scoped_ptr<AddressSorter> AddressSorter::CreateAddressSorter() {
+  return scoped_ptr<AddressSorter>(
+      new AddressSorterPosix(ClientSocketFactory::GetDefaultFactory()));
+}
+
+}  // namespace net
+