1 | /* $NetBSD: getaddrinfo.c,v 1.82 2006/03/25 12:09:40 rpaulo Exp $ */ |
2 | /* $KAME: getaddrinfo.c,v 1.29 2000/08/31 17:26:57 itojun Exp $ */ |
3 | /* |
4 | * Copyright (C) 1995, 1996, 1997, and 1998 WIDE Project. |
5 | * All rights reserved. |
6 | * |
7 | * Redistribution and use in source and binary forms, with or without |
8 | * modification, are permitted provided that the following conditions |
9 | * are met: |
10 | * 1. Redistributions of source code must retain the above copyright |
11 | * notice, this list of conditions and the following disclaimer. |
12 | * 2. Redistributions in binary form must reproduce the above copyright |
13 | * notice, this list of conditions and the following disclaimer in the |
14 | * documentation and/or other materials provided with the distribution. |
15 | * 3. Neither the name of the project nor the names of its contributors |
16 | * may be used to endorse or promote products derived from this software |
17 | * without specific prior written permission. |
18 | * |
19 | * THIS SOFTWARE IS PROVIDED BY THE PROJECT AND CONTRIBUTORS ``AS IS'' AND |
20 | * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
21 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
22 | * ARE DISCLAIMED. IN NO EVENT SHALL THE PROJECT OR CONTRIBUTORS BE LIABLE |
23 | * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL |
24 | * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS |
25 | * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) |
26 | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT |
27 | * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY |
28 | * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF |
29 | * SUCH DAMAGE. |
30 | * |
31 | */ |
32 | |
33 | /* |
34 | * This is an adaptation of Android's implementation of RFC 6724 |
35 | * (in Android's getaddrinfo.c). It has some cosmetic differences |
36 | * from Android's getaddrinfo.c, but Android's getaddrinfo.c was |
37 | * used as a guide or example of a way to implement the RFC 6724 spec when |
38 | * this was written. |
39 | */ |
40 | |
41 | #include "address_sorting_internal.h" |
42 | |
43 | #include <errno.h> |
44 | #include <inttypes.h> |
45 | #include <limits.h> |
46 | #include <stdlib.h> |
47 | #include <string.h> |
48 | #include <sys/types.h> |
49 | |
50 | // Scope values increase with increase in scope. |
51 | static const int kIPv6AddrScopeLinkLocal = 1; |
52 | static const int kIPv6AddrScopeSiteLocal = 2; |
53 | static const int kIPv6AddrScopeGlobal = 3; |
54 | |
55 | static address_sorting_source_addr_factory* g_current_source_addr_factory = |
56 | NULL; |
57 | |
58 | static bool address_sorting_get_source_addr(const address_sorting_address* dest, |
59 | address_sorting_address* source) { |
60 | return g_current_source_addr_factory->vtable->get_source_addr( |
61 | g_current_source_addr_factory, dest, source); |
62 | } |
63 | |
64 | bool address_sorting_get_source_addr_for_testing( |
65 | const address_sorting_address* dest, address_sorting_address* source) { |
66 | return address_sorting_get_source_addr(dest, source); |
67 | } |
68 | |
69 | static int ipv6_prefix_match_length(const struct sockaddr_in6* sa, |
70 | const struct sockaddr_in6* sb) { |
71 | unsigned char* a = (unsigned char*)&sa->sin6_addr; |
72 | unsigned char* b = (unsigned char*)&sb->sin6_addr; |
73 | int cur_bit = 0; |
74 | while (cur_bit < 128) { |
75 | int high_bit = 1 << (CHAR_BIT - 1); |
76 | int a_val = a[cur_bit / CHAR_BIT] & (high_bit >> (cur_bit % CHAR_BIT)); |
77 | int b_val = b[cur_bit / CHAR_BIT] & (high_bit >> (cur_bit % CHAR_BIT)); |
78 | if (a_val == b_val) { |
79 | cur_bit++; |
80 | } else { |
81 | break; |
82 | } |
83 | } |
84 | return cur_bit; |
85 | } |
86 | |
87 | static int in6_is_addr_loopback(const struct in6_addr* ipv6_address) { |
88 | uint32_t* bits32 = (uint32_t*)ipv6_address; |
89 | return bits32[0] == 0 && bits32[1] == 0 && bits32[2] == 0 && |
90 | bits32[3] == htonl(1); |
91 | } |
92 | |
93 | static int in6_is_addr_v4mapped(const struct in6_addr* ipv6_address) { |
94 | uint32_t* bits32 = (uint32_t*)ipv6_address; |
95 | return bits32[0] == 0 && bits32[1] == 0 && bits32[2] == htonl(0x0000ffff); |
96 | } |
97 | |
98 | static int in6_is_addr_v4compat(const struct in6_addr* ipv6_address) { |
99 | uint32_t* bits32 = (uint32_t*)ipv6_address; |
100 | return bits32[0] == 0 && bits32[1] == 0 && bits32[2] == 0 && bits32[3] != 0 && |
101 | bits32[3] != htonl(1); |
102 | } |
103 | |
104 | static int in6_is_addr_sitelocal(const struct in6_addr* ipv6_address) { |
105 | uint8_t* bytes = (uint8_t*)ipv6_address; |
106 | return bytes[0] == 0xfe && (bytes[1] & 0xc0) == 0xc0; |
107 | } |
108 | |
109 | static int in6_is_addr_linklocal(const struct in6_addr* ipv6_address) { |
110 | uint8_t* bytes = (uint8_t*)ipv6_address; |
111 | return bytes[0] == 0xfe && (bytes[1] & 0xc0) == 0x80; |
112 | } |
113 | |
114 | static int in6_is_addr_6to4(const struct in6_addr* ipv6_address) { |
115 | uint8_t* bytes = (uint8_t*)ipv6_address; |
116 | return bytes[0] == 0x20 && bytes[1] == 0x02; |
117 | } |
118 | |
119 | static int in6_is_addr_ula(const struct in6_addr* ipv6_address) { |
120 | uint8_t* bytes = (uint8_t*)ipv6_address; |
121 | return (bytes[0] & 0xfe) == 0xfc; |
122 | } |
123 | |
124 | static int in6_is_addr_teredo(const struct in6_addr* ipv6_address) { |
125 | uint8_t* bytes = (uint8_t*)ipv6_address; |
126 | return bytes[0] == 0x20 && bytes[1] == 0x01 && bytes[2] == 0x00 && |
127 | bytes[3] == 0x00; |
128 | } |
129 | |
130 | static int in6_is_addr_6bone(const struct in6_addr* ipv6_address) { |
131 | uint8_t* bytes = (uint8_t*)ipv6_address; |
132 | return bytes[0] == 0x3f && bytes[1] == 0xfe; |
133 | } |
134 | |
135 | address_sorting_family address_sorting_abstract_get_family( |
136 | const address_sorting_address* address) { |
137 | switch (((struct sockaddr*)address)->sa_family) { |
138 | case AF_INET: |
139 | return ADDRESS_SORTING_AF_INET; |
140 | case AF_INET6: |
141 | return ADDRESS_SORTING_AF_INET6; |
142 | default: |
143 | return ADDRESS_SORTING_UNKNOWN_FAMILY; |
144 | } |
145 | } |
146 | |
147 | static int get_label_value(const address_sorting_address* resolved_addr) { |
148 | if (address_sorting_abstract_get_family(resolved_addr) == |
149 | ADDRESS_SORTING_AF_INET) { |
150 | return 4; |
151 | } else if (address_sorting_abstract_get_family(resolved_addr) != |
152 | ADDRESS_SORTING_AF_INET6) { |
153 | return 1; |
154 | } |
155 | struct sockaddr_in6* ipv6_addr = (struct sockaddr_in6*)&resolved_addr->addr; |
156 | if (in6_is_addr_loopback(&ipv6_addr->sin6_addr)) { |
157 | return 0; |
158 | } else if (in6_is_addr_v4mapped(&ipv6_addr->sin6_addr)) { |
159 | return 4; |
160 | } else if (in6_is_addr_6to4(&ipv6_addr->sin6_addr)) { |
161 | return 2; |
162 | } else if (in6_is_addr_teredo(&ipv6_addr->sin6_addr)) { |
163 | return 5; |
164 | } else if (in6_is_addr_ula(&ipv6_addr->sin6_addr)) { |
165 | return 13; |
166 | } else if (in6_is_addr_v4compat(&ipv6_addr->sin6_addr)) { |
167 | return 3; |
168 | } else if (in6_is_addr_sitelocal(&ipv6_addr->sin6_addr)) { |
169 | return 11; |
170 | } else if (in6_is_addr_6bone(&ipv6_addr->sin6_addr)) { |
171 | return 12; |
172 | } |
173 | return 1; |
174 | } |
175 | |
176 | static int get_precedence_value(const address_sorting_address* resolved_addr) { |
177 | if (address_sorting_abstract_get_family(resolved_addr) == |
178 | ADDRESS_SORTING_AF_INET) { |
179 | return 35; |
180 | } else if (address_sorting_abstract_get_family(resolved_addr) != |
181 | ADDRESS_SORTING_AF_INET6) { |
182 | return 1; |
183 | } |
184 | struct sockaddr_in6* ipv6_addr = (struct sockaddr_in6*)&resolved_addr->addr; |
185 | if (in6_is_addr_loopback(&ipv6_addr->sin6_addr)) { |
186 | return 50; |
187 | } else if (in6_is_addr_v4mapped(&ipv6_addr->sin6_addr)) { |
188 | return 35; |
189 | } else if (in6_is_addr_6to4(&ipv6_addr->sin6_addr)) { |
190 | return 30; |
191 | } else if (in6_is_addr_teredo(&ipv6_addr->sin6_addr)) { |
192 | return 5; |
193 | } else if (in6_is_addr_ula(&ipv6_addr->sin6_addr)) { |
194 | return 3; |
195 | } else if (in6_is_addr_v4compat(&ipv6_addr->sin6_addr) || |
196 | in6_is_addr_sitelocal(&ipv6_addr->sin6_addr) || |
197 | in6_is_addr_6bone(&ipv6_addr->sin6_addr)) { |
198 | return 1; |
199 | } |
200 | return 40; |
201 | } |
202 | |
203 | static int sockaddr_get_scope(const address_sorting_address* resolved_addr) { |
204 | if (address_sorting_abstract_get_family(resolved_addr) == |
205 | ADDRESS_SORTING_AF_INET) { |
206 | return kIPv6AddrScopeGlobal; |
207 | } else if (address_sorting_abstract_get_family(resolved_addr) == |
208 | ADDRESS_SORTING_AF_INET6) { |
209 | struct sockaddr_in6* ipv6_addr = (struct sockaddr_in6*)&resolved_addr->addr; |
210 | if (in6_is_addr_loopback(&ipv6_addr->sin6_addr) || |
211 | in6_is_addr_linklocal(&ipv6_addr->sin6_addr)) { |
212 | return kIPv6AddrScopeLinkLocal; |
213 | } |
214 | if (in6_is_addr_sitelocal(&ipv6_addr->sin6_addr)) { |
215 | return kIPv6AddrScopeSiteLocal; |
216 | } |
217 | return kIPv6AddrScopeGlobal; |
218 | } |
219 | return 0; |
220 | } |
221 | |
222 | static int compare_source_addr_exists(const address_sorting_sortable* first, |
223 | const address_sorting_sortable* second) { |
224 | if (first->source_addr_exists != second->source_addr_exists) { |
225 | return first->source_addr_exists ? -1 : 1; |
226 | } |
227 | return 0; |
228 | } |
229 | |
230 | static int compare_source_dest_scope_matches( |
231 | const address_sorting_sortable* first, |
232 | const address_sorting_sortable* second) { |
233 | bool first_src_dst_scope_matches = false; |
234 | if (sockaddr_get_scope(&first->dest_addr) == |
235 | sockaddr_get_scope(&first->source_addr)) { |
236 | first_src_dst_scope_matches = true; |
237 | } |
238 | bool second_src_dst_scope_matches = false; |
239 | if (sockaddr_get_scope(&second->dest_addr) == |
240 | sockaddr_get_scope(&second->source_addr)) { |
241 | second_src_dst_scope_matches = true; |
242 | } |
243 | if (first_src_dst_scope_matches != second_src_dst_scope_matches) { |
244 | return first_src_dst_scope_matches ? -1 : 1; |
245 | } |
246 | return 0; |
247 | } |
248 | |
249 | static int compare_source_dest_labels_match( |
250 | const address_sorting_sortable* first, |
251 | const address_sorting_sortable* second) { |
252 | bool first_label_matches = false; |
253 | if (get_label_value(&first->dest_addr) == |
254 | get_label_value(&first->source_addr)) { |
255 | first_label_matches = true; |
256 | } |
257 | bool second_label_matches = false; |
258 | if (get_label_value(&second->dest_addr) == |
259 | get_label_value(&second->source_addr)) { |
260 | second_label_matches = true; |
261 | } |
262 | if (first_label_matches != second_label_matches) { |
263 | return first_label_matches ? -1 : 1; |
264 | } |
265 | return 0; |
266 | } |
267 | |
268 | static int compare_dest_precedence(const address_sorting_sortable* first, |
269 | const address_sorting_sortable* second) { |
270 | return get_precedence_value(&second->dest_addr) - |
271 | get_precedence_value(&first->dest_addr); |
272 | } |
273 | |
274 | static int compare_dest_scope(const address_sorting_sortable* first, |
275 | const address_sorting_sortable* second) { |
276 | return sockaddr_get_scope(&first->dest_addr) - |
277 | sockaddr_get_scope(&second->dest_addr); |
278 | } |
279 | |
280 | static int compare_source_dest_prefix_match_lengths( |
281 | const address_sorting_sortable* first, |
282 | const address_sorting_sortable* second) { |
283 | if (first->source_addr_exists && |
284 | address_sorting_abstract_get_family(&first->source_addr) == |
285 | ADDRESS_SORTING_AF_INET6 && |
286 | second->source_addr_exists && |
287 | address_sorting_abstract_get_family(&second->source_addr) == |
288 | ADDRESS_SORTING_AF_INET6) { |
289 | int first_match_length = |
290 | ipv6_prefix_match_length((struct sockaddr_in6*)&first->source_addr.addr, |
291 | (struct sockaddr_in6*)&first->dest_addr.addr); |
292 | int second_match_length = ipv6_prefix_match_length( |
293 | (struct sockaddr_in6*)&second->source_addr.addr, |
294 | (struct sockaddr_in6*)&second->dest_addr.addr); |
295 | return second_match_length - first_match_length; |
296 | } |
297 | return 0; |
298 | } |
299 | |
300 | static int rfc_6724_compare(const void* a, const void* b) { |
301 | const address_sorting_sortable* first = (address_sorting_sortable*)a; |
302 | const address_sorting_sortable* second = (address_sorting_sortable*)b; |
303 | int out = 0; |
304 | if ((out = compare_source_addr_exists(first, second))) { |
305 | return out; |
306 | } |
307 | if ((out = compare_source_dest_scope_matches(first, second))) { |
308 | return out; |
309 | } |
310 | if ((out = compare_source_dest_labels_match(first, second))) { |
311 | return out; |
312 | } |
313 | // TODO: Implement rule 3; avoid deprecated addresses. |
314 | // TODO: Implement rule 4; avoid temporary addresses. |
315 | if ((out = compare_dest_precedence(first, second))) { |
316 | return out; |
317 | } |
318 | // TODO: Implement rule 7; prefer native transports. |
319 | if ((out = compare_dest_scope(first, second))) { |
320 | return out; |
321 | } |
322 | if ((out = compare_source_dest_prefix_match_lengths(first, second))) { |
323 | return out; |
324 | } |
325 | // Prefer that the sort be stable otherwise |
326 | return (int)(first->original_index - second->original_index); |
327 | } |
328 | |
329 | void address_sorting_override_source_addr_factory_for_testing( |
330 | address_sorting_source_addr_factory* factory) { |
331 | if (g_current_source_addr_factory == NULL) { |
332 | abort(); |
333 | } |
334 | g_current_source_addr_factory->vtable->destroy(g_current_source_addr_factory); |
335 | g_current_source_addr_factory = factory; |
336 | } |
337 | |
338 | static void sanity_check_private_fields_are_unused( |
339 | const address_sorting_sortable* sortable) { |
340 | address_sorting_address expected_source_addr; |
341 | memset(&expected_source_addr, 0, sizeof(expected_source_addr)); |
342 | if (memcmp(&expected_source_addr, &sortable->source_addr, |
343 | sizeof(address_sorting_address)) || |
344 | sortable->original_index || sortable->source_addr_exists) { |
345 | abort(); |
346 | } |
347 | } |
348 | |
349 | void address_sorting_rfc_6724_sort(address_sorting_sortable* sortables, |
350 | size_t sortables_len) { |
351 | for (size_t i = 0; i < sortables_len; i++) { |
352 | sanity_check_private_fields_are_unused(&sortables[i]); |
353 | sortables[i].original_index = i; |
354 | sortables[i].source_addr_exists = address_sorting_get_source_addr( |
355 | &sortables[i].dest_addr, &sortables[i].source_addr); |
356 | } |
357 | qsort(sortables, sortables_len, sizeof(address_sorting_sortable), |
358 | rfc_6724_compare); |
359 | } |
360 | |
361 | void address_sorting_init() { |
362 | if (g_current_source_addr_factory != NULL) { |
363 | abort(); |
364 | } |
365 | g_current_source_addr_factory = |
366 | address_sorting_create_source_addr_factory_for_current_platform(); |
367 | } |
368 | |
369 | void address_sorting_shutdown() { |
370 | if (g_current_source_addr_factory == NULL) { |
371 | abort(); |
372 | } |
373 | g_current_source_addr_factory->vtable->destroy(g_current_source_addr_factory); |
374 | g_current_source_addr_factory = NULL; |
375 | } |
376 | |