[ipxe-devel] [RFC 3/3] [ipv6] Implement source address selection

Thomas Bächler thomas at archlinux.org
Wed Feb 3 19:12:44 GMT 2016


Previously, ipxe would always choose the first usable address for IPv6 routing. This
is problematic when an interface has a globally routable and a ULA address. This patch
partially implements the source address selection algorithm from RFC 6724, section 5.

Since ipxe's IPv6 implementation is incomplete, only rules 1, 2, 6 and 8 of this
algorithm are applicable in this case.
---
 src/net/ipv6.c | 347 ++++++++++++++++++++++++++++++++++++++++++++++++++++-----
 1 file changed, 319 insertions(+), 28 deletions(-)

diff --git a/src/net/ipv6.c b/src/net/ipv6.c
index bbc00d3..82ea4b9 100644
--- a/src/net/ipv6.c
+++ b/src/net/ipv6.c
@@ -68,6 +68,98 @@ ipv6_statistics_family __ip_statistics_family ( IP_STATISTICS_IPV6 ) = {
 	.stats = &ipv6_stats,
 };
 
+/** Entry in the ipv6 policy table */
+struct ipv6_policytable_entry {
+	struct in6_addr address;
+	unsigned int prefix_len;
+	struct in6_addr prefix_mask;
+	unsigned int precedence;
+	unsigned int label;
+};
+
+/** IPv6 policy table according to RFC 6724
+ *
+ * Prefix        Precedence Label
+ * ::1/128               50     0
+ * ::/0                  40     1
+ * ::ffff:0:0/96         35     4
+ * 2002::/16             30     2
+ * 2001::/32              5     5
+ * fc00::/7               3    13
+ * ::/96                  1     3
+ * fec0::/10              1    11
+ * 3ffe::/16              1    12
+ *
+ * The label is used for source address selection.
+ * The precedence and label are used for destination
+ * address selection (not implemented here).
+ */
+static const struct ipv6_policytable_entry policytable[] = {
+	{
+	  .address = { .s6_addr16 = { 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, htons( 0x0001 ) } },
+	  .prefix_len = 128,
+	  .prefix_mask = { .s6_addr16 = { 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff } },
+	  .precedence = 50,
+	  .label = 0
+	},
+	{
+	  .address = { .s6_addr16 = { 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0 } },
+	  .prefix_len = 0,
+	  .prefix_mask = { .s6_addr16 = { 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0 } },
+	  .precedence = 40,
+	  .label = 1
+	},
+	{
+	  .address = { .s6_addr16 = { 0x0, 0x0, 0x0, 0x0, 0x0, 0xffff, 0x0, 0x0 } },
+	  .prefix_len = 96,
+	  .prefix_mask = { .s6_addr16 = { 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0x0, 0x0 } },
+	  .precedence = 35,
+	  .label = 4
+	},
+	{
+	  .address = { .s6_addr16 = { htons( 0x2002 ), 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0 } },
+	  .prefix_len = 16,
+	  .prefix_mask = { .s6_addr16 = { 0xffff, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0 } },
+	  .precedence = 30,
+	  .label = 2
+	},
+	{
+	  .address = { .s6_addr16 = { htons( 0x2001 ), 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0 } },
+	  .prefix_len = 32,
+	  .prefix_mask = { .s6_addr16 = { 0xffff, 0xffff, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0 } },
+	  .precedence = 5,
+	  .label = 5
+	},
+	{
+	  .address = { .s6_addr16 = { htons( 0xfc00 ), 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0 } },
+	  .prefix_len = 7,
+	  .prefix_mask = { .s6_addr16 = { htons( 0xfe00 ), 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0 } },
+	  .precedence = 3,
+	  .label = 13
+	},
+	{
+	  .address = { .s6_addr16 = { 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0 } },
+	  .prefix_len = 96,
+	  .prefix_mask = { .s6_addr16 = { 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0x0, 0x0 } },
+	  .precedence = 1,
+	  .label = 3
+	},
+	{
+	  .address = { .s6_addr16 = { htons( 0xfec0 ), 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0 } },
+	  .prefix_len = 10,
+	  .prefix_mask = { .s6_addr16 = { 0xffc0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0 } },
+	  .precedence = 1,
+	  .label = 11
+	},
+	{
+	  .address = { .s6_addr16 = { htons( 0x3ffe ), 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0 } },
+	  .prefix_len = 16,
+	  .prefix_mask = { .s6_addr16 = { 0xffff, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0 } },
+	  .precedence = 1,
+	  .label = 12
+	}
+};
+
 /**
  * Determine debugging colour for IPv6 debug messages
  *
@@ -268,6 +360,184 @@ int ipv6_set_address ( struct net_device *netdev, struct in6_addr *address ) {
 }
 
 /**
+ * Return the policy table entry for the specified address
+ *
+ * @v address		IPv6 address
+ * @ret rc		Policy table entry
+ *
+ * With the default policy table, this function never returns NULL.
+ */
+static const struct ipv6_policytable_entry* ipv6_policytable_get(struct in6_addr *address) {
+	unsigned int i, j;
+	const struct ipv6_policytable_entry* best = NULL;
+	int skip;
+
+	for ( i = 0; i < sizeof( policytable ) / sizeof( policytable[0] ); ++i ) {
+		skip = 0;
+		for ( j = 0; j < ( sizeof ( address->s6_addr32 ) / sizeof ( address->s6_addr32[0] ) ) ; ++j ) {
+			if ( (( address->s6_addr32[j] ^ policytable[i].address.s6_addr32[j])
+			  & policytable[i].prefix_mask.s6_addr32[j] ) != 0 )
+			{
+				skip = 1;
+				break;
+			}
+		}
+		if ( !skip && ( best == NULL || policytable[i].prefix_len > best->prefix_len ) )
+			best = &policytable[i];
+	}
+	return best;
+}
+
+/**
+ * Source address selection rule 1
+ *
+ * @v first		First IPv6 address
+ * @v second		First IPv6 address
+ * @v dest		Destination address
+ * @ret rc		Comparison result
+ *
+ * This function implements the first rule from RFC 6724, section 5. It tests whether
+ * either of the addresses is equal to the destination address.
+ *
+ * If the first address should be preferred over the second, this function returns -1.
+ * If the second address should be preferred over the first, this function returns 1.
+ * If neither the first nor the second address should be preferred over the other, this
+ * function returns 0.
+ */
+static int address_selection_compare_identical(struct ipv6_miniroute *first, struct ipv6_miniroute *second, struct in6_addr *dest)
+{
+	int firstIdentical = IN6_ARE_ADDR_EQUAL( first, dest ),
+	  secondIdentical = IN6_ARE_ADDR_EQUAL( second, dest );
+
+	if (firstIdentical && !secondIdentical)
+		return -1;
+	else if (!firstIdentical && secondIdentical)
+		return 1;
+	else
+		return 0;
+}
+
+/**
+ * Source address selection rule 2
+ *
+ * @v first		First IPv6 address
+ * @v second		First IPv6 address
+ * @v dest		Destination address
+ * @ret rc		Comparison result
+ *
+ * This function implements the second rule from RFC 6724, section 5. It determines
+ * the preferred address by comparing the scope of the first and second address and
+ * the destination.
+ *
+ * We only consider the link-local and global scopes, since all other scopes are
+ * irrelevant for iPXE.
+ *
+ * If the first address should be preferred over the second, this function returns -1.
+ * If the second address should be preferred over the first, this function returns 1.
+ * If neither the first nor the second address should be preferred over the other, this
+ * function returns 0.
+ */
+static int address_selection_compare_scope(struct ipv6_miniroute *first, struct ipv6_miniroute *second, struct in6_addr *dest)
+{
+	int firstLinkLocal = IN6_IS_ADDR_NONGLOBAL( &first->address ),
+	  secondLinkLocal = IN6_IS_ADDR_NONGLOBAL( &second->address ),
+	  destLinkLocal = IN6_IS_ADDR_NONGLOBAL( dest );
+
+	if ( firstLinkLocal && !secondLinkLocal )
+		return destLinkLocal ? -1 : 1;
+	else if ( secondLinkLocal && !firstLinkLocal )
+		return destLinkLocal ? 1 : -1;
+	else
+		return 0;
+}
+
+/**
+ * Source address selection rule 6
+ *
+ * @v first		First IPv6 address
+ * @v second		First IPv6 address
+ * @v dest		Destination address
+ * @ret rc		Comparison result
+ *
+ * This function implements the 6th rule from RFC 6724, section 5. It determines
+ * the preferred address by comparing the policy label of the first and second address
+ * with the destination's policy label.
+ *
+ * If the first address should be preferred over the second, this function returns -1.
+ * If the second address should be preferred over the first, this function returns 1.
+ * If neither the first nor the second address should be preferred over the other, this
+ * function returns 0.
+ */
+static int address_selection_compare_label(struct ipv6_miniroute *first, struct ipv6_miniroute *second, struct in6_addr *dest) {
+	unsigned int labelFirst = ipv6_policytable_get(&first->address)->label,
+	  labelSecond = ipv6_policytable_get(&second->address)->label,
+	  labelDest = ipv6_policytable_get(dest)->label;
+
+	if ( labelFirst == labelDest && labelSecond != labelDest )
+		return -1;
+	else if ( labelFirst != labelDest && labelSecond == labelDest )
+		return 1;
+	else
+		return 0;
+}
+
+/**
+ * Returns the common prefix length of two ipv6 addresses
+ *
+ * @v first		First IPv6 address
+ * @v second		First IPv6 address
+ */
+static unsigned int common_prefix_length(struct in6_addr *first, struct in6_addr *second) {
+	uint64_t common_prefix = ( ( ( (uint64_t)htonl( first->s6_addr32[0] ) ) << 32 ) | (uint64_t)htonl( first->s6_addr32[1] ) ) ^
+	  ( ( ( (uint64_t)htonl( second->s6_addr32[0] ) ) << 32 ) | (uint64_t)htonl( second->s6_addr32[1] ) );
+
+	unsigned int len = 0;
+	while ( common_prefix >> len != 0 )
+		++len;
+
+	return 64 - len;
+}
+
+/**
+ * Source address selection rule 8
+ *
+ * @v first		First IPv6 address
+ * @v second		First IPv6 address
+ * @v dest		Destination address
+ * @ret rc		Comparison result
+ *
+ * This function implements the 8th rule from RFC 6724, section 5. It determines
+ * the preferred address by choosing the address that shares the longest common
+ * prefix with the destination.
+ *
+ * If the first address should be preferred over the second, this function returns -1.
+ * If the second address should be preferred over the first, this function returns 1.
+ * If neither the first nor the second address should be preferred over the other, this
+ * function returns 0.
+ */
+static int address_selection_compare_common_prefix_length(struct ipv6_miniroute *first, struct ipv6_miniroute *second, struct in6_addr *dest) {
+	unsigned int first_common_prefix_length = common_prefix_length(&first->address, dest),
+	  second_common_prefix_length = common_prefix_length(&second->address, dest);
+
+	if ( first_common_prefix_length > second_common_prefix_length )
+		return -1;
+	else if ( second_common_prefix_length > first_common_prefix_length )
+		return 1;
+	else
+		return 0;
+}
+
+/**
+ * Source address selection rules
+ */
+static int (*const source_address_comparison_functions[])(struct ipv6_miniroute*, struct ipv6_miniroute*, struct in6_addr*) = {
+	&address_selection_compare_identical,
+	&address_selection_compare_scope,
+	&address_selection_compare_label,
+	&address_selection_compare_common_prefix_length
+};
+
+/**
  * Perform IPv6 routing
  *
  * @v scope_id		Destination address scope ID (for link-local addresses)
@@ -277,47 +547,68 @@ int ipv6_set_address ( struct net_device *netdev, struct in6_addr *address ) {
  */
 static struct ipv6_miniroute * ipv6_route ( unsigned int scope_id,
 					    struct in6_addr **dest ) {
-	struct ipv6_miniroute *miniroute;
-
-	/* Find first usable route in routing table */
-	list_for_each_entry ( miniroute, &ipv6_miniroutes, list ) {
+	struct ipv6_miniroute *current;
+	struct ipv6_miniroute *best = NULL;
+	unsigned int i;
+	int cmp;
 
+	/* Find route and source address */
+	list_for_each_entry ( current, &ipv6_miniroutes, list ) {
 		/* Skip closed network devices */
-		if ( ! netdev_is_open ( miniroute->netdev ) )
+		if ( ! netdev_is_open ( current->netdev ) )
 			continue;
 
 		/* Skip routing table entries with no usable source address */
-		if ( ! ( miniroute->flags & IPV6_HAS_ADDRESS ) )
+		if ( ! ( current->flags & IPV6_HAS_ADDRESS ) )
 			continue;
 
-		if ( IN6_IS_ADDR_NONGLOBAL ( *dest ) ) {
-
-			/* If destination is non-global, and the scope ID
-			 * matches this network device, then use this route.
-			 */
-			if ( miniroute->netdev->index == scope_id )
-				return miniroute;
-
-		} else {
-
-			/* If destination is an on-link global
-			 * address, then use this route.
-			 */
-			if ( ipv6_is_on_link ( miniroute, *dest ) )
-				return miniroute;
+		/* Skip all unusable addresses */
+		if ( ( ! IN6_IS_ADDR_NONGLOBAL ( *dest ) || current->netdev->index != scope_id ) &&
+		  ( IN6_IS_ADDR_NONGLOBAL ( *dest ) || ( ! ipv6_is_on_link ( current, *dest ) && ! ( current->flags & IPV6_HAS_ROUTER ) ) ) )
+			continue;
 
-			/* If destination is an off-link global
-			 * address, and we have a default gateway,
-			 * then use this route.
+		if ( best == NULL )
+		{
+			/* There is no previous best address, use the current one */
+			best = current;
+		}
+		else
+		{
+			/* Compare this address to the previous best
+			 *
+			 * If the current address is strictly better than the previous best, use it.
+			 * Otherwise, keep the previous best address.
 			 */
-			if ( miniroute->flags & IPV6_HAS_ROUTER ) {
-				*dest = &miniroute->router;
-				return miniroute;
+			for ( i = 0; i < sizeof(source_address_comparison_functions) / sizeof(source_address_comparison_functions[0]); ++i )
+			{
+				cmp = source_address_comparison_functions[i]( best, current, *dest );
+				if ( cmp < 0 )
+				{
+					/* The previous best address is strictly better than the current one in this comparison. */
+					break;
+				}
+				else if ( cmp > 0 )
+				{
+					/*
+					 * The current address is strictly beter than the previous best in this comparison. Use the current
+					 * address as new best address.
+					 */
+					best = current;
+					break;
+				}
 			}
 		}
 	}
 
-	return NULL;
+	if ( best != NULL )
+	{
+		/* We found an address. Check if we need to use a router. */
+		if ( best->flags & IPV6_HAS_ROUTER &&
+		  ! ( IN6_IS_ADDR_NONGLOBAL ( *dest ) || ipv6_is_on_link ( best, *dest ) ) )
+			*dest = &best->router;
+	}
+
+	return best;
 }
 
 /**
-- 
2.6.3


More information about the ipxe-devel mailing list