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