"Fossies" - the Fresh Open Source Software Archive

Member "go/src/net/addrselect.go" (9 Sep 2020, 9735 Bytes) of package /windows/misc/go1.14.9.windows-386.zip:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) Go source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file.

    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 }