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.
51static const int kIPv6AddrScopeLinkLocal = 1;
52static const int kIPv6AddrScopeSiteLocal = 2;
53static const int kIPv6AddrScopeGlobal = 3;
54
55static address_sorting_source_addr_factory* g_current_source_addr_factory =
56 NULL;
57
58static 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
64bool 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
69static 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
87static 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
93static 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
98static 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
104static 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
109static 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
114static 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
119static 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
124static 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
130static 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
135address_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
147static 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
176static 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
203static 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
222static 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
230static 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
249static 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
268static 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
274static 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
280static 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
300static 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
329void 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
338static 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
349void 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
361void 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
369void 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