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