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

View as plain text