addrselect.go

     1  // Copyright 2015 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  // Minimal RFC 6724 address selection.
     6  
     7  package net
     8  
     9  import (
    10  	"net/netip"
    11  	"sort"
    12  )
    13  
    14  func sortByRFC6724(addrs []IPAddr) {
    15  	if len(addrs) < 2 {
    16  		return
    17  	}
    18  	sortByRFC6724withSrcs(addrs, srcAddrs(addrs))
    19  }
    20  
    21  func sortByRFC6724withSrcs(addrs []IPAddr, srcs []netip.Addr) {
    22  	if len(addrs) != len(srcs) {
    23  		panic("internal error")
    24  	}
    25  	addrAttr := make([]ipAttr, len(addrs))
    26  	srcAttr := make([]ipAttr, len(srcs))
    27  	for i, v := range addrs {
    28  		addrAttrIP, _ := netip.AddrFromSlice(v.IP)
    29  		addrAttr[i] = ipAttrOf(addrAttrIP)
    30  		srcAttr[i] = ipAttrOf(srcs[i])
    31  	}
    32  	sort.Stable(&byRFC6724{
    33  		addrs:    addrs,
    34  		addrAttr: addrAttr,
    35  		srcs:     srcs,
    36  		srcAttr:  srcAttr,
    37  	})
    38  }
    39  
    40  // srcAddrs tries to UDP-connect to each address to see if it has a
    41  // route. (This doesn't send any packets). The destination port
    42  // number is irrelevant.
    43  func srcAddrs(addrs []IPAddr) []netip.Addr {
    44  	srcs := make([]netip.Addr, len(addrs))
    45  	dst := UDPAddr{Port: 53}
    46  	for i := range addrs {
    47  		dst.IP = addrs[i].IP
    48  		dst.Zone = addrs[i].Zone
    49  		c, err := DialUDP("udp", nil, &dst)
    50  		if err == nil {
    51  			if src, ok := c.LocalAddr().(*UDPAddr); ok {
    52  				srcs[i], _ = netip.AddrFromSlice(src.IP)
    53  			}
    54  			c.Close()
    55  		}
    56  	}
    57  	return srcs
    58  }
    59  
    60  type ipAttr struct {
    61  	Scope      scope
    62  	Precedence uint8
    63  	Label      uint8
    64  }
    65  
    66  func ipAttrOf(ip netip.Addr) ipAttr {
    67  	if !ip.IsValid() {
    68  		return ipAttr{}
    69  	}
    70  	match := rfc6724policyTable.Classify(ip)
    71  	return ipAttr{
    72  		Scope:      classifyScope(ip),
    73  		Precedence: match.Precedence,
    74  		Label:      match.Label,
    75  	}
    76  }
    77  
    78  type byRFC6724 struct {
    79  	addrs    []IPAddr // addrs to sort
    80  	addrAttr []ipAttr
    81  	srcs     []netip.Addr // or not valid addr if unreachable
    82  	srcAttr  []ipAttr
    83  }
    84  
    85  func (s *byRFC6724) Len() int { return len(s.addrs) }
    86  
    87  func (s *byRFC6724) Swap(i, j int) {
    88  	s.addrs[i], s.addrs[j] = s.addrs[j], s.addrs[i]
    89  	s.srcs[i], s.srcs[j] = s.srcs[j], s.srcs[i]
    90  	s.addrAttr[i], s.addrAttr[j] = s.addrAttr[j], s.addrAttr[i]
    91  	s.srcAttr[i], s.srcAttr[j] = s.srcAttr[j], s.srcAttr[i]
    92  }
    93  
    94  // Less reports whether i is a better destination address for this
    95  // host than j.
    96  //
    97  // The algorithm and variable names comes from RFC 6724 section 6.
    98  func (s *byRFC6724) Less(i, j int) bool {
    99  	DA := s.addrs[i].IP
   100  	DB := s.addrs[j].IP
   101  	SourceDA := s.srcs[i]
   102  	SourceDB := s.srcs[j]
   103  	attrDA := &s.addrAttr[i]
   104  	attrDB := &s.addrAttr[j]
   105  	attrSourceDA := &s.srcAttr[i]
   106  	attrSourceDB := &s.srcAttr[j]
   107  
   108  	const preferDA = true
   109  	const preferDB = false
   110  
   111  	// Rule 1: Avoid unusable destinations.
   112  	// If DB is known to be unreachable or if Source(DB) is undefined, then
   113  	// prefer DA.  Similarly, if DA is known to be unreachable or if
   114  	// Source(DA) is undefined, then prefer DB.
   115  	if !SourceDA.IsValid() && !SourceDB.IsValid() {
   116  		return false // "equal"
   117  	}
   118  	if !SourceDB.IsValid() {
   119  		return preferDA
   120  	}
   121  	if !SourceDA.IsValid() {
   122  		return preferDB
   123  	}
   124  
   125  	// Rule 2: Prefer matching scope.
   126  	// If Scope(DA) = Scope(Source(DA)) and Scope(DB) <> Scope(Source(DB)),
   127  	// then prefer DA.  Similarly, if Scope(DA) <> Scope(Source(DA)) and
   128  	// Scope(DB) = Scope(Source(DB)), then prefer DB.
   129  	if attrDA.Scope == attrSourceDA.Scope && attrDB.Scope != attrSourceDB.Scope {
   130  		return preferDA
   131  	}
   132  	if attrDA.Scope != attrSourceDA.Scope && attrDB.Scope == attrSourceDB.Scope {
   133  		return preferDB
   134  	}
   135  
   136  	// Rule 3: Avoid deprecated addresses.
   137  	// If Source(DA) is deprecated and Source(DB) is not, then prefer DB.
   138  	// Similarly, if Source(DA) is not deprecated and Source(DB) is
   139  	// deprecated, then prefer DA.
   140  
   141  	// TODO(bradfitz): implement? low priority for now.
   142  
   143  	// Rule 4: Prefer home addresses.
   144  	// If Source(DA) is simultaneously a home address and care-of address
   145  	// and Source(DB) is not, then prefer DA.  Similarly, if Source(DB) is
   146  	// simultaneously a home address and care-of address and Source(DA) is
   147  	// not, then prefer DB.
   148  
   149  	// TODO(bradfitz): implement? low priority for now.
   150  
   151  	// Rule 5: Prefer matching label.
   152  	// If Label(Source(DA)) = Label(DA) and Label(Source(DB)) <> Label(DB),
   153  	// then prefer DA.  Similarly, if Label(Source(DA)) <> Label(DA) and
   154  	// Label(Source(DB)) = Label(DB), then prefer DB.
   155  	if attrSourceDA.Label == attrDA.Label &&
   156  		attrSourceDB.Label != attrDB.Label {
   157  		return preferDA
   158  	}
   159  	if attrSourceDA.Label != attrDA.Label &&
   160  		attrSourceDB.Label == attrDB.Label {
   161  		return preferDB
   162  	}
   163  
   164  	// Rule 6: Prefer higher precedence.
   165  	// If Precedence(DA) > Precedence(DB), then prefer DA.  Similarly, if
   166  	// Precedence(DA) < Precedence(DB), then prefer DB.
   167  	if attrDA.Precedence > attrDB.Precedence {
   168  		return preferDA
   169  	}
   170  	if attrDA.Precedence < attrDB.Precedence {
   171  		return preferDB
   172  	}
   173  
   174  	// Rule 7: Prefer native transport.
   175  	// If DA is reached via an encapsulating transition mechanism (e.g.,
   176  	// IPv6 in IPv4) and DB is not, then prefer DB.  Similarly, if DB is
   177  	// reached via encapsulation and DA is not, then prefer DA.
   178  
   179  	// TODO(bradfitz): implement? low priority for now.
   180  
   181  	// Rule 8: Prefer smaller scope.
   182  	// If Scope(DA) < Scope(DB), then prefer DA.  Similarly, if Scope(DA) >
   183  	// Scope(DB), then prefer DB.
   184  	if attrDA.Scope < attrDB.Scope {
   185  		return preferDA
   186  	}
   187  	if attrDA.Scope > attrDB.Scope {
   188  		return preferDB
   189  	}
   190  
   191  	// Rule 9: Use the longest matching prefix.
   192  	// When DA and DB belong to the same address family (both are IPv6 or
   193  	// both are IPv4 [but see below]): If CommonPrefixLen(Source(DA), DA) >
   194  	// CommonPrefixLen(Source(DB), DB), then prefer DA.  Similarly, if
   195  	// CommonPrefixLen(Source(DA), DA) < CommonPrefixLen(Source(DB), DB),
   196  	// then prefer DB.
   197  	//
   198  	// However, applying this rule to IPv4 addresses causes
   199  	// problems (see issues 13283 and 18518), so limit to IPv6.
   200  	if DA.To4() == nil && DB.To4() == nil {
   201  		commonA := commonPrefixLen(SourceDA, DA)
   202  		commonB := commonPrefixLen(SourceDB, DB)
   203  
   204  		if commonA > commonB {
   205  			return preferDA
   206  		}
   207  		if commonA < commonB {
   208  			return preferDB
   209  		}
   210  	}
   211  
   212  	// Rule 10: Otherwise, leave the order unchanged.
   213  	// If DA preceded DB in the original list, prefer DA.
   214  	// Otherwise, prefer DB.
   215  	return false // "equal"
   216  }
   217  
   218  type policyTableEntry struct {
   219  	Prefix     netip.Prefix
   220  	Precedence uint8
   221  	Label      uint8
   222  }
   223  
   224  type policyTable []policyTableEntry
   225  
   226  // RFC 6724 section 2.1.
   227  // Items are sorted by the size of their Prefix.Mask.Size,
   228  var rfc6724policyTable = policyTable{
   229  	{
   230  		// "::1/128"
   231  		Prefix:     netip.PrefixFrom(netip.AddrFrom16([16]byte{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0x01}), 128),
   232  		Precedence: 50,
   233  		Label:      0,
   234  	},
   235  	{
   236  		// "::ffff:0:0/96"
   237  		// IPv4-compatible, etc.
   238  		Prefix:     netip.PrefixFrom(netip.AddrFrom16([16]byte{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0xff, 0xff}), 96),
   239  		Precedence: 35,
   240  		Label:      4,
   241  	},
   242  	{
   243  		// "::/96"
   244  		Prefix:     netip.PrefixFrom(netip.AddrFrom16([16]byte{}), 96),
   245  		Precedence: 1,
   246  		Label:      3,
   247  	},
   248  	{
   249  		// "2001::/32"
   250  		// Teredo
   251  		Prefix:     netip.PrefixFrom(netip.AddrFrom16([16]byte{0x20, 0x01}), 32),
   252  		Precedence: 5,
   253  		Label:      5,
   254  	},
   255  	{
   256  		// "2002::/16"
   257  		// 6to4
   258  		Prefix:     netip.PrefixFrom(netip.AddrFrom16([16]byte{0x20, 0x02}), 16),
   259  		Precedence: 30,
   260  		Label:      2,
   261  	},
   262  	{
   263  		// "3ffe::/16"
   264  		Prefix:     netip.PrefixFrom(netip.AddrFrom16([16]byte{0x3f, 0xfe}), 16),
   265  		Precedence: 1,
   266  		Label:      12,
   267  	},
   268  	{
   269  		// "fec0::/10"
   270  		Prefix:     netip.PrefixFrom(netip.AddrFrom16([16]byte{0xfe, 0xc0}), 10),
   271  		Precedence: 1,
   272  		Label:      11,
   273  	},
   274  	{
   275  		// "fc00::/7"
   276  		Prefix:     netip.PrefixFrom(netip.AddrFrom16([16]byte{0xfc}), 7),
   277  		Precedence: 3,
   278  		Label:      13,
   279  	},
   280  	{
   281  		// "::/0"
   282  		Prefix:     netip.PrefixFrom(netip.AddrFrom16([16]byte{}), 0),
   283  		Precedence: 40,
   284  		Label:      1,
   285  	},
   286  }
   287  
   288  // Classify returns the policyTableEntry of the entry with the longest
   289  // matching prefix that contains ip.
   290  // The table t must be sorted from largest mask size to smallest.
   291  func (t policyTable) Classify(ip netip.Addr) policyTableEntry {
   292  	// Prefix.Contains() will not match an IPv6 prefix for an IPv4 address.
   293  	if ip.Is4() {
   294  		ip = netip.AddrFrom16(ip.As16())
   295  	}
   296  	for _, ent := range t {
   297  		if ent.Prefix.Contains(ip) {
   298  			return ent
   299  		}
   300  	}
   301  	return policyTableEntry{}
   302  }
   303  
   304  // RFC 6724 section 3.1.
   305  type scope uint8
   306  
   307  const (
   308  	scopeInterfaceLocal scope = 0x1
   309  	scopeLinkLocal      scope = 0x2
   310  	scopeAdminLocal     scope = 0x4
   311  	scopeSiteLocal      scope = 0x5
   312  	scopeOrgLocal       scope = 0x8
   313  	scopeGlobal         scope = 0xe
   314  )
   315  
   316  func classifyScope(ip netip.Addr) scope {
   317  	if ip.IsLoopback() || ip.IsLinkLocalUnicast() {
   318  		return scopeLinkLocal
   319  	}
   320  	ipv6 := ip.Is6() && !ip.Is4In6()
   321  	ipv6AsBytes := ip.As16()
   322  	if ipv6 && ip.IsMulticast() {
   323  		return scope(ipv6AsBytes[1] & 0xf)
   324  	}
   325  	// Site-local addresses are defined in RFC 3513 section 2.5.6
   326  	// (and deprecated in RFC 3879).
   327  	if ipv6 && ipv6AsBytes[0] == 0xfe && ipv6AsBytes[1]&0xc0 == 0xc0 {
   328  		return scopeSiteLocal
   329  	}
   330  	return scopeGlobal
   331  }
   332  
   333  // commonPrefixLen reports the length of the longest prefix (looking
   334  // at the most significant, or leftmost, bits) that the
   335  // two addresses have in common, up to the length of a's prefix (i.e.,
   336  // the portion of the address not including the interface ID).
   337  //
   338  // If a or b is an IPv4 address as an IPv6 address, the IPv4 addresses
   339  // are compared (with max common prefix length of 32).
   340  // If a and b are different IP versions, 0 is returned.
   341  //
   342  // See https://tools.ietf.org/html/rfc6724#section-2.2
   343  func commonPrefixLen(a netip.Addr, b IP) (cpl int) {
   344  	if b4 := b.To4(); b4 != nil {
   345  		b = b4
   346  	}
   347  	aAsSlice := a.AsSlice()
   348  	if len(aAsSlice) != len(b) {
   349  		return 0
   350  	}
   351  	// If IPv6, only up to the prefix (first 64 bits)
   352  	if len(aAsSlice) > 8 {
   353  		aAsSlice = aAsSlice[:8]
   354  		b = b[:8]
   355  	}
   356  	for len(aAsSlice) > 0 {
   357  		if aAsSlice[0] == b[0] {
   358  			cpl += 8
   359  			aAsSlice = aAsSlice[1:]
   360  			b = b[1:]
   361  			continue
   362  		}
   363  		bits := 8
   364  		ab, bb := aAsSlice[0], b[0]
   365  		for {
   366  			ab >>= 1
   367  			bb >>= 1
   368  			bits--
   369  			if ab == bb {
   370  				cpl += bits
   371  				return
   372  			}
   373  		}
   374  	}
   375  	return
   376  }
   377
View as plain text