123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390 |
- // Copyright 2015 The Go Authors. All rights reserved.
- // Use of this source code is governed by a BSD-style
- // license that can be found in the LICENSE file.
- //go:build aix || darwin || dragonfly || freebsd || hurd || linux || netbsd || openbsd || solaris
- // Minimal RFC 6724 address selection.
- package net
- import "sort"
- func sortByRFC6724(addrs []IPAddr) {
- if len(addrs) < 2 {
- return
- }
- sortByRFC6724withSrcs(addrs, srcAddrs(addrs))
- }
- func sortByRFC6724withSrcs(addrs []IPAddr, srcs []IP) {
- if len(addrs) != len(srcs) {
- panic("internal error")
- }
- addrAttr := make([]ipAttr, len(addrs))
- srcAttr := make([]ipAttr, len(srcs))
- for i, v := range addrs {
- addrAttr[i] = ipAttrOf(v.IP)
- srcAttr[i] = ipAttrOf(srcs[i])
- }
- sort.Stable(&byRFC6724{
- addrs: addrs,
- addrAttr: addrAttr,
- srcs: srcs,
- srcAttr: srcAttr,
- })
- }
- // srcsAddrs tries to UDP-connect to each address to see if it has a
- // route. (This doesn't send any packets). The destination port
- // number is irrelevant.
- func srcAddrs(addrs []IPAddr) []IP {
- srcs := make([]IP, len(addrs))
- dst := UDPAddr{Port: 9}
- for i := range addrs {
- dst.IP = addrs[i].IP
- dst.Zone = addrs[i].Zone
- c, err := DialUDP("udp", nil, &dst)
- if err == nil {
- if src, ok := c.LocalAddr().(*UDPAddr); ok {
- srcs[i] = src.IP
- }
- c.Close()
- }
- }
- return srcs
- }
- type ipAttr struct {
- Scope scope
- Precedence uint8
- Label uint8
- }
- func ipAttrOf(ip IP) ipAttr {
- if ip == nil {
- return ipAttr{}
- }
- match := rfc6724policyTable.Classify(ip)
- return ipAttr{
- Scope: classifyScope(ip),
- Precedence: match.Precedence,
- Label: match.Label,
- }
- }
- type byRFC6724 struct {
- addrs []IPAddr // addrs to sort
- addrAttr []ipAttr
- srcs []IP // or nil if unreachable
- srcAttr []ipAttr
- }
- func (s *byRFC6724) Len() int { return len(s.addrs) }
- func (s *byRFC6724) Swap(i, j int) {
- s.addrs[i], s.addrs[j] = s.addrs[j], s.addrs[i]
- s.srcs[i], s.srcs[j] = s.srcs[j], s.srcs[i]
- s.addrAttr[i], s.addrAttr[j] = s.addrAttr[j], s.addrAttr[i]
- s.srcAttr[i], s.srcAttr[j] = s.srcAttr[j], s.srcAttr[i]
- }
- // Less reports whether i is a better destination address for this
- // host than j.
- //
- // The algorithm and variable names comes from RFC 6724 section 6.
- func (s *byRFC6724) Less(i, j int) bool {
- DA := s.addrs[i].IP
- DB := s.addrs[j].IP
- SourceDA := s.srcs[i]
- SourceDB := s.srcs[j]
- attrDA := &s.addrAttr[i]
- attrDB := &s.addrAttr[j]
- attrSourceDA := &s.srcAttr[i]
- attrSourceDB := &s.srcAttr[j]
- const preferDA = true
- const preferDB = false
- // Rule 1: Avoid unusable destinations.
- // If DB is known to be unreachable or if Source(DB) is undefined, then
- // prefer DA. Similarly, if DA is known to be unreachable or if
- // Source(DA) is undefined, then prefer DB.
- if SourceDA == nil && SourceDB == nil {
- return false // "equal"
- }
- if SourceDB == nil {
- return preferDA
- }
- if SourceDA == nil {
- return preferDB
- }
- // Rule 2: Prefer matching scope.
- // If Scope(DA) = Scope(Source(DA)) and Scope(DB) <> Scope(Source(DB)),
- // then prefer DA. Similarly, if Scope(DA) <> Scope(Source(DA)) and
- // Scope(DB) = Scope(Source(DB)), then prefer DB.
- if attrDA.Scope == attrSourceDA.Scope && attrDB.Scope != attrSourceDB.Scope {
- return preferDA
- }
- if attrDA.Scope != attrSourceDA.Scope && attrDB.Scope == attrSourceDB.Scope {
- return preferDB
- }
- // Rule 3: Avoid deprecated addresses.
- // If Source(DA) is deprecated and Source(DB) is not, then prefer DB.
- // Similarly, if Source(DA) is not deprecated and Source(DB) is
- // deprecated, then prefer DA.
- // TODO(bradfitz): implement? low priority for now.
- // Rule 4: Prefer home addresses.
- // If Source(DA) is simultaneously a home address and care-of address
- // and Source(DB) is not, then prefer DA. Similarly, if Source(DB) is
- // simultaneously a home address and care-of address and Source(DA) is
- // not, then prefer DB.
- // TODO(bradfitz): implement? low priority for now.
- // Rule 5: Prefer matching label.
- // If Label(Source(DA)) = Label(DA) and Label(Source(DB)) <> Label(DB),
- // then prefer DA. Similarly, if Label(Source(DA)) <> Label(DA) and
- // Label(Source(DB)) = Label(DB), then prefer DB.
- if attrSourceDA.Label == attrDA.Label &&
- attrSourceDB.Label != attrDB.Label {
- return preferDA
- }
- if attrSourceDA.Label != attrDA.Label &&
- attrSourceDB.Label == attrDB.Label {
- return preferDB
- }
- // Rule 6: Prefer higher precedence.
- // If Precedence(DA) > Precedence(DB), then prefer DA. Similarly, if
- // Precedence(DA) < Precedence(DB), then prefer DB.
- if attrDA.Precedence > attrDB.Precedence {
- return preferDA
- }
- if attrDA.Precedence < attrDB.Precedence {
- return preferDB
- }
- // Rule 7: Prefer native transport.
- // If DA is reached via an encapsulating transition mechanism (e.g.,
- // IPv6 in IPv4) and DB is not, then prefer DB. Similarly, if DB is
- // reached via encapsulation and DA is not, then prefer DA.
- // TODO(bradfitz): implement? low priority for now.
- // Rule 8: Prefer smaller scope.
- // If Scope(DA) < Scope(DB), then prefer DA. Similarly, if Scope(DA) >
- // Scope(DB), then prefer DB.
- if attrDA.Scope < attrDB.Scope {
- return preferDA
- }
- if attrDA.Scope > attrDB.Scope {
- return preferDB
- }
- // Rule 9: Use longest matching prefix.
- // When DA and DB belong to the same address family (both are IPv6 or
- // both are IPv4 [but see below]): If CommonPrefixLen(Source(DA), DA) >
- // CommonPrefixLen(Source(DB), DB), then prefer DA. Similarly, if
- // CommonPrefixLen(Source(DA), DA) < CommonPrefixLen(Source(DB), DB),
- // then prefer DB.
- //
- // However, applying this rule to IPv4 addresses causes
- // problems (see issues 13283 and 18518), so limit to IPv6.
- if DA.To4() == nil && DB.To4() == nil {
- commonA := commonPrefixLen(SourceDA, DA)
- commonB := commonPrefixLen(SourceDB, DB)
- if commonA > commonB {
- return preferDA
- }
- if commonA < commonB {
- return preferDB
- }
- }
- // Rule 10: Otherwise, leave the order unchanged.
- // If DA preceded DB in the original list, prefer DA.
- // Otherwise, prefer DB.
- return false // "equal"
- }
- type policyTableEntry struct {
- Prefix *IPNet
- Precedence uint8
- Label uint8
- }
- type policyTable []policyTableEntry
- // RFC 6724 section 2.1.
- var rfc6724policyTable = policyTable{
- {
- Prefix: mustCIDR("::1/128"),
- Precedence: 50,
- Label: 0,
- },
- {
- Prefix: mustCIDR("::/0"),
- Precedence: 40,
- Label: 1,
- },
- {
- // IPv4-compatible, etc.
- Prefix: mustCIDR("::ffff:0:0/96"),
- Precedence: 35,
- Label: 4,
- },
- {
- // 6to4
- Prefix: mustCIDR("2002::/16"),
- Precedence: 30,
- Label: 2,
- },
- {
- // Teredo
- Prefix: mustCIDR("2001::/32"),
- Precedence: 5,
- Label: 5,
- },
- {
- Prefix: mustCIDR("fc00::/7"),
- Precedence: 3,
- Label: 13,
- },
- {
- Prefix: mustCIDR("::/96"),
- Precedence: 1,
- Label: 3,
- },
- {
- Prefix: mustCIDR("fec0::/10"),
- Precedence: 1,
- Label: 11,
- },
- {
- Prefix: mustCIDR("3ffe::/16"),
- Precedence: 1,
- Label: 12,
- },
- }
- func init() {
- sort.Sort(sort.Reverse(byMaskLength(rfc6724policyTable)))
- }
- // byMaskLength sorts policyTableEntry by the size of their Prefix.Mask.Size,
- // from smallest mask, to largest.
- type byMaskLength []policyTableEntry
- func (s byMaskLength) Len() int { return len(s) }
- func (s byMaskLength) Swap(i, j int) { s[i], s[j] = s[j], s[i] }
- func (s byMaskLength) Less(i, j int) bool {
- isize, _ := s[i].Prefix.Mask.Size()
- jsize, _ := s[j].Prefix.Mask.Size()
- return isize < jsize
- }
- // mustCIDR calls ParseCIDR and panics on any error, or if the network
- // is not IPv6.
- func mustCIDR(s string) *IPNet {
- ip, ipNet, err := ParseCIDR(s)
- if err != nil {
- panic(err.Error())
- }
- if len(ip) != IPv6len {
- panic("unexpected IP length")
- }
- return ipNet
- }
- // Classify returns the policyTableEntry of the entry with the longest
- // matching prefix that contains ip.
- // The table t must be sorted from largest mask size to smallest.
- func (t policyTable) Classify(ip IP) policyTableEntry {
- for _, ent := range t {
- if ent.Prefix.Contains(ip) {
- return ent
- }
- }
- return policyTableEntry{}
- }
- // RFC 6724 section 3.1.
- type scope uint8
- const (
- scopeInterfaceLocal scope = 0x1
- scopeLinkLocal scope = 0x2
- scopeAdminLocal scope = 0x4
- scopeSiteLocal scope = 0x5
- scopeOrgLocal scope = 0x8
- scopeGlobal scope = 0xe
- )
- func classifyScope(ip IP) scope {
- if ip.IsLoopback() || ip.IsLinkLocalUnicast() {
- return scopeLinkLocal
- }
- ipv6 := len(ip) == IPv6len && ip.To4() == nil
- if ipv6 && ip.IsMulticast() {
- return scope(ip[1] & 0xf)
- }
- // Site-local addresses are defined in RFC 3513 section 2.5.6
- // (and deprecated in RFC 3879).
- if ipv6 && ip[0] == 0xfe && ip[1]&0xc0 == 0xc0 {
- return scopeSiteLocal
- }
- return scopeGlobal
- }
- // commonPrefixLen reports the length of the longest prefix (looking
- // at the most significant, or leftmost, bits) that the
- // two addresses have in common, up to the length of a's prefix (i.e.,
- // the portion of the address not including the interface ID).
- //
- // If a or b is an IPv4 address as an IPv6 address, the IPv4 addresses
- // are compared (with max common prefix length of 32).
- // If a and b are different IP versions, 0 is returned.
- //
- // See https://tools.ietf.org/html/rfc6724#section-2.2
- func commonPrefixLen(a, b IP) (cpl int) {
- if a4 := a.To4(); a4 != nil {
- a = a4
- }
- if b4 := b.To4(); b4 != nil {
- b = b4
- }
- if len(a) != len(b) {
- return 0
- }
- // If IPv6, only up to the prefix (first 64 bits)
- if len(a) > 8 {
- a = a[:8]
- b = b[:8]
- }
- for len(a) > 0 {
- if a[0] == b[0] {
- cpl += 8
- a = a[1:]
- b = b[1:]
- continue
- }
- bits := 8
- ab, bb := a[0], b[0]
- for {
- ab >>= 1
- bb >>= 1
- bits--
- if ab == bb {
- cpl += bits
- return
- }
- }
- }
- return
- }
|