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