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