addrselect.go

Documentation: net

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