Subject: [homenet] Linux 6724 rule 5.5 (Re: draft-bowbakova-rtgwg-enterprise-pa-multihoming-00)

From: David Lamparter <[email-masked]>
Date: Wed, 20 Jul 2016 14:54:58 +0200

As mentioned on mic during rtgwg, I think the idea of affecting host
source address selection through 6724 rule 5.5 is potentially very
useful and IMHO should be explored.

Hence, I hacked it up for the Linux (4.5.0) kernel; patches are attached
to this mail.  I've been able to gleam a little more detail on the idea:

- it's a bit unclear how an address/prefix's "source" next-hop is kept
  in association.  The simplistic approach of adding a "PA source ipv6
  address" for each of a host's configured addresses falls flat when
  more than 1 router advertises the same prefix, so I implemented it as
  a list -- however, my hack never removes entries off that.  It should
  possibly have a copy of the PA's valid time?

  (Read as: the "Discussion" note in 6724 is right on the mark - the
  details are not quite specified.)

- in that avenue, I don't think it's possible to store the information
  in a route-centric way, because RA lifetimes tend to be shorter.
  If a router goes away and comes back, it seems to me that the prefix's
  associated origin/nexthop should still be there.

- rule 5.5 makes RA preference carry into source address selection.  I
  think this is described in the draft, I just failed to grasp that from
  the presentation.  Very useful for getting source selection right in
  the face of unequal performance uplinks.

- if you want to manage this in an userspace process on Linux, you can
  simply update the route's preferred source attribute.

The attached patchset also has the following caveats that result from me
just doing a quick hack:
- there is no debugging/user visibility of the value
- as mentioned above, tracked source addresses never go away unless the
  entire address dies.  It caps at 4 sources (so you can't exhaust
  kernel memory by spoofing...)
- I should probably pass Linux's "dst" instead of "rt6_info"
- I didn't check for locking/concurrentness violations
- there's a const warning which I ignored.

Either way if anyone wants to tinker with it, here it is.
No warranties, YMMV.  You touch it, it becomes your responsibility ;)

Cheers,

-David

On Wed, Jul 06, 2016 at 04:33:18PM +0000, Fred Baker (fred) wrote:
> At IETF 94, this working group advised the routing ADs and Routing Working Group that PA multihoming would not work without a source/destination routing solution. This draft was developed in response. Routing Working Group requests v6ops review.
> 
> > Begin forwarded message:
> > 
> > From: <[email-masked]>
> > Subject: New Version Notification for draft-bowbakova-rtgwg-enterprise-pa-multihoming-00.txt
> > Date: July 5, 2016 at 5:58:25 PM PDT
> > To: Chris Bowers <[email-masked]>, Jen Linkova <[email-masked]>, "Fred Baker" <[email-masked]>, "J. Linkova" <[email-masked]>
> > 
> > 
> > A new version of I-D, draft-bowbakova-rtgwg-enterprise-pa-multihoming-00.txt
> > has been successfully submitted by Fred Baker and posted to the
> > IETF repository.
> > 
> > Name:		draft-bowbakova-rtgwg-enterprise-pa-multihoming
> > Revision:	00
> > Title:		Enterprise Multihoming using Provider-Assigned Addresses without Network Prefix Translation: Requirements and Solution
> > Document date:	2016-07-05
> > Group:		Individual Submission
> > Pages:		44
> > URL:            https://www.ietf.org/internet-drafts/draft-bowbakova-rtgwg-enterprise-pa-multihoming-00.txt
> > Status:         https://datatracker.ietf.org/doc/draft-bowbakova-rtgwg-enterprise-pa-multihoming/
> > Htmlized:       https://tools.ietf.org/html/draft-bowbakova-rtgwg-enterprise-pa-multihoming-00
> > 
> > 
> > Abstract:
> >  Connecting an enterprise site to multiple ISPs using provider-
> >  assigned addresses is difficult without the use of some form of
> >  Network Address Translation (NAT).  Much has been written on this
> >  topic over the last 10 to 15 years, but it still remains a problem
> >  without a clearly defined or widely implemented solution.  Any
> >  multihoming solution without NAT requires hosts at the site to have
> >  addresses from each ISP and to select the egress ISP by selecting a
> >  source address for outgoing packets.  It also requires routers at the
> >  site to take into account those source addresses when forwarding
> >  packets out towards the ISPs.
> > 
> >  This document attempts to define a complete solution to this problem.
> >  It covers the behavior of routers to forward traffic taking into
> >  account source address, and it covers the behavior of host to select
> >  appropriate source addresses.  It also covers any possible role that
> >  routers might play in providing information to hosts to help them
> >  select appropriate source addresses.  In the process of exploring
> >  potential solutions, this documents also makes explicit requirements
> >  for how the solution would be expected to behave from the perspective
> >  of an enterprise site network administrator .
> > 
> > 
> > 
> > 
> > Please note that it may take a couple of minutes from the time of submission
> > until the htmlized version and diff are available at tools.ietf.org.
> > 
> > The IETF Secretariat
> > 
> 

> _______________________________________________
> v6ops mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/v6ops

>From 2d1bf126d3e776deabcab4ef8b6f941636b8bc67 Mon Sep 17 00:00:00 2001
From: David Lamparter <[email-masked]>
Date: Wed, 20 Jul 2016 10:37:54 +0200
Subject: [PATCH 1/3] net/ipv6: track autoconfigured address' origin

---
 include/net/addrconf.h |  3 ++-
 include/net/if_inet6.h | 11 +++++++++++
 net/ipv6/addrconf.c    | 15 ++++++++++++++-
 net/ipv6/ndisc.c       |  3 ++-
 4 files changed, 29 insertions(+), 3 deletions(-)

diff --git a/include/net/addrconf.h b/include/net/addrconf.h
index 47f52d3..33f2652 100644
--- a/include/net/addrconf.h
+++ b/include/net/addrconf.h
@@ -226,7 +226,8 @@ static inline bool ipv6_is_mld(struct sk_buff *skb, int nexthdr, int offset)
 }
 
 void addrconf_prefix_rcv(struct net_device *dev,
-			 u8 *opt, int len, bool sllao);
+			 u8 *opt, int len, bool sllao,
+			 const struct in6_addr *source);
 
 /*
  *	anycast prototypes (anycast.c)
diff --git a/include/net/if_inet6.h b/include/net/if_inet6.h
index 1c8b682..f79faa9 100644
--- a/include/net/if_inet6.h
+++ b/include/net/if_inet6.h
@@ -38,6 +38,14 @@ enum {
 	INET6_IFADDR_STATE_DEAD,
 };
 
+/* for RFC6724 rule 5.5, we want to know what router advertised a prefix;
+ * however, there may be multiple such routers, so it needs to be a list.
+ * (think redundant default gateways)
+ *
+ * to prevent spoofed packets filling memory - and to keep this simple -
+ * this is a fixed-size list. */
+#define INET6_IFADDR_ORIGINRTR_MAX	4
+
 struct inet6_ifaddr {
 	struct in6_addr		addr;
 	__u32			prefix_len;
@@ -75,6 +83,9 @@ struct inet6_ifaddr {
 
 	struct rcu_head		rcu;
 	struct in6_addr		peer_addr;
+
+	size_t			origin_rtr_count;
+	struct in6_addr		origin_rtr[INET6_IFADDR_ORIGINRTR_MAX];
 };
 
 struct ip6_sf_socklist {
diff --git a/net/ipv6/addrconf.c b/net/ipv6/addrconf.c
index fd065f2..f148278 100644
--- a/net/ipv6/addrconf.c
+++ b/net/ipv6/addrconf.c
@@ -2338,7 +2338,19 @@ static bool is_addr_mode_generate_stable(struct inet6_dev *idev)
 	       idev->addr_gen_mode == IN6_ADDR_GEN_MODE_RANDOM;
 }
 
-void addrconf_prefix_rcv(struct net_device *dev, u8 *opt, int len, bool sllao)
+static void addr_register_origin(struct inet6_ifaddr *addr,
+				 const struct in6_addr *rtr)
+{
+	if (!rtr)
+		return;
+	if (addr->origin_rtr_count == ARRAY_SIZE(addr->origin_rtr))
+		return;
+	addr->origin_rtr[addr->origin_rtr_count] = *rtr;
+	addr->origin_rtr_count++;
+}
+
+void addrconf_prefix_rcv(struct net_device *dev, u8 *opt, int len, bool sllao,
+			 const struct in6_addr *source)
 {
 	struct prefix_info *pinfo;
 	__u32 valid_lft;
@@ -2556,6 +2568,7 @@ ok:
 			in6_ifa_put(ifp);
 			addrconf_verify();
 		}
+		addr_register_origin(ifp, source);
 	}
 	inet6_prefix_notify(RTM_NEWPREFIX, in6_dev, pinfo);
 	in6_dev_put(in6_dev);
diff --git a/net/ipv6/ndisc.c b/net/ipv6/ndisc.c
index 84afb9a..b298da6 100644
--- a/net/ipv6/ndisc.c
+++ b/net/ipv6/ndisc.c
@@ -1385,7 +1385,8 @@ skip_routeinfo:
 		     p = ndisc_next_option(p, ndopts.nd_opts_pi_end)) {
 			addrconf_prefix_rcv(skb->dev, (u8 *)p,
 					    (p->nd_opt_len) << 3,
-					    ndopts.nd_opts_src_lladdr != NULL);
+					    ndopts.nd_opts_src_lladdr != NULL,
+					    &ipv6_hdr(skb)->saddr);
 		}
 	}
 
-- 
2.7.3

>From 57c57fdc9ddbfa627660117d4d257e17dc4c6b3f Mon Sep 17 00:00:00 2001
From: David Lamparter <[email-masked]>
Date: Wed, 20 Jul 2016 11:24:46 +0200
Subject: [PATCH 2/3] net/ipv6: add ipv6_rt_get_saddr()

---
 include/net/addrconf.h  |  3 +++
 net/ipv6/addrconf.c     | 26 +++++++++++++++++++++++---
 net/ipv6/fib6_rules.c   |  4 +---
 net/ipv6/route.c        |  3 +--
 net/ipv6/xfrm6_policy.c |  3 ++-
 5 files changed, 30 insertions(+), 9 deletions(-)

diff --git a/include/net/addrconf.h b/include/net/addrconf.h
index 33f2652..95cee9a 100644
--- a/include/net/addrconf.h
+++ b/include/net/addrconf.h
@@ -83,6 +83,9 @@ struct inet6_ifaddr *ipv6_get_ifaddr(struct net *net,
 int ipv6_dev_get_saddr(struct net *net, const struct net_device *dev,
 		       const struct in6_addr *daddr, unsigned int srcprefs,
 		       struct in6_addr *saddr);
+int ipv6_rt_get_saddr(struct net *net, const struct rt6_info *rt,
+		      const struct in6_addr *daddr, unsigned int srcprefs,
+		      struct in6_addr *saddr);
 int __ipv6_get_lladdr(struct inet6_dev *idev, struct in6_addr *addr,
 		      u32 banned_flags);
 int ipv6_get_lladdr(struct net_device *dev, struct in6_addr *addr,
diff --git a/net/ipv6/addrconf.c b/net/ipv6/addrconf.c
index f148278..b0aedd3 100644
--- a/net/ipv6/addrconf.c
+++ b/net/ipv6/addrconf.c
@@ -1287,6 +1287,7 @@ struct ipv6_saddr_dst {
 	int scope;
 	int label;
 	unsigned int prefs;
+	const struct in6_addr *nh;
 };
 
 static inline int ipv6_saddr_preferred(int type)
@@ -1518,9 +1519,11 @@ out:
 	return hiscore_idx;
 }
 
-int ipv6_dev_get_saddr(struct net *net, const struct net_device *dst_dev,
-		       const struct in6_addr *daddr, unsigned int prefs,
-		       struct in6_addr *saddr)
+static int __ipv6_rtdev_get_saddr(struct net *net, const struct rt6_info *rt,
+				  const struct net_device *dst_dev,
+				  const struct in6_addr *daddr,
+				  unsigned int prefs,
+				  struct in6_addr *saddr)
 {
 	struct ipv6_saddr_score scores[2], *hiscore;
 	struct ipv6_saddr_dst dst;
@@ -1537,6 +1540,7 @@ int ipv6_dev_get_saddr(struct net *net, const struct net_device *dst_dev,
 	dst.scope = __ipv6_addr_src_scope(dst_type);
 	dst.label = ipv6_addr_label(net, daddr, dst_type, dst.ifindex);
 	dst.prefs = prefs;
+	dst.nh = rt ? &rt->rt6i_gateway : NULL;
 
 	scores[hiscore_idx].rule = -1;
 	scores[hiscore_idx].ifa = NULL;
@@ -1599,8 +1603,24 @@ int ipv6_dev_get_saddr(struct net *net, const struct net_device *dst_dev,
 	in6_ifa_put(hiscore->ifa);
 	return 0;
 }
+
+int ipv6_dev_get_saddr(struct net *net, const struct net_device *dst_dev,
+		       const struct in6_addr *daddr, unsigned int prefs,
+		       struct in6_addr *saddr)
+{
+	return __ipv6_rtdev_get_saddr(net, NULL, dst_dev, daddr, prefs, saddr);
+}
 EXPORT_SYMBOL(ipv6_dev_get_saddr);
 
+int ipv6_rt_get_saddr(struct net *net, const struct rt6_info *rt,
+		      const struct in6_addr *daddr, unsigned int prefs,
+		      struct in6_addr *saddr)
+{
+	const struct net_device *dst_dev = ip6_dst_idev(&rt->dst)->dev;
+	return __ipv6_rtdev_get_saddr(net, rt, dst_dev, daddr, prefs, saddr);
+}
+EXPORT_SYMBOL(ipv6_rt_get_saddr);
+
 int __ipv6_get_lladdr(struct inet6_dev *idev, struct in6_addr *addr,
 		      u32 banned_flags)
 {
diff --git a/net/ipv6/fib6_rules.c b/net/ipv6/fib6_rules.c
index ed33abf..d91b6f5 100644
--- a/net/ipv6/fib6_rules.c
+++ b/net/ipv6/fib6_rules.c
@@ -104,9 +104,7 @@ static int fib6_rule_action(struct fib_rule *rule, struct flowi *flp,
 		    r->src.plen && !(flags & RT6_LOOKUP_F_HAS_SADDR)) {
 			struct in6_addr saddr;
 
-			if (ipv6_dev_get_saddr(net,
-					       ip6_dst_idev(&rt->dst)->dev,
-					       &flp6->daddr,
+			if (ipv6_rt_get_saddr(net, rt, &flp6->daddr,
 					       rt6_flags2srcprefs(flags),
 					       &saddr))
 				goto again;
diff --git a/net/ipv6/route.c b/net/ipv6/route.c
index ed44663..8e6218d 100644
--- a/net/ipv6/route.c
+++ b/net/ipv6/route.c
@@ -2546,8 +2546,7 @@ int ip6_route_get_saddr(struct net *net,
 	if (rt && rt->rt6i_prefsrc.plen)
 		*saddr = rt->rt6i_prefsrc.addr;
 	else
-		err = ipv6_dev_get_saddr(net, idev ? idev->dev : NULL,
-					 daddr, prefs, saddr);
+		err = ipv6_rt_get_saddr(net, rt, daddr, prefs, saddr);
 	return err;
 }
 
diff --git a/net/ipv6/xfrm6_policy.c b/net/ipv6/xfrm6_policy.c
index c074771..19005e6 100644
--- a/net/ipv6/xfrm6_policy.c
+++ b/net/ipv6/xfrm6_policy.c
@@ -64,7 +64,8 @@ static int xfrm6_get_saddr(struct net *net, int oif,
 		return -EHOSTUNREACH;
 
 	dev = ip6_dst_idev(dst)->dev;
-	ipv6_dev_get_saddr(dev_net(dev), dev, &daddr->in6, 0, &saddr->in6);
+	ipv6_rt_get_saddr(dev_net(dev), (struct rt6_info *)dst,
+			  &daddr->in6, 0, &saddr->in6);
 	dst_release(dst);
 	return 0;
 }
-- 
2.7.3

>From f396b90dc6dfd36f282ba574c1add619d7345ad3 Mon Sep 17 00:00:00 2001
From: David Lamparter <[email-masked]>
Date: Wed, 20 Jul 2016 11:25:23 +0200
Subject: [PATCH 3/3] net/ipv6: implement RFC6724 (addrconf) rule 5.5

---
 net/ipv6/addrconf.c | 14 ++++++++++++++
 1 file changed, 14 insertions(+)

diff --git a/net/ipv6/addrconf.c b/net/ipv6/addrconf.c
index b0aedd3..64ea39d 100644
--- a/net/ipv6/addrconf.c
+++ b/net/ipv6/addrconf.c
@@ -1262,6 +1262,7 @@ enum {
 	IPV6_SADDR_RULE_HOA,
 #endif
 	IPV6_SADDR_RULE_OIF,
+	IPV6_SADDR_RULE_OIF_RTR,
 	IPV6_SADDR_RULE_LABEL,
 	IPV6_SADDR_RULE_PRIVACY,
 	IPV6_SADDR_RULE_ORCHID,
@@ -1312,6 +1313,7 @@ static int ipv6_get_saddr_eval(struct net *net,
 			       int i)
 {
 	int ret;
+	size_t j;
 
 	if (i <= score->rule) {
 		switch (i) {
@@ -1390,6 +1392,18 @@ static int ipv6_get_saddr_eval(struct net *net,
 		ret = (!dst->ifindex ||
 		       dst->ifindex == score->ifa->idev->dev->ifindex);
 		break;
+	case IPV6_SADDR_RULE_OIF_RTR:
+		/* Rule 5.5: Prefer prefixes announced by nexthop */
+		ret = 0;
+		if (!dst->nh)
+			break;
+		for (j = 0; j < score->ifa->origin_rtr_count; j++)
+			if (ipv6_addr_equal(&score->ifa->origin_rtr[j],
+					    dst->nh)) {
+				ret = 1;
+				break;
+			}
+		break;
 	case IPV6_SADDR_RULE_LABEL:
 		/* Rule 6: Prefer matching label */
 		ret = ipv6_addr_label(net,
-- 
2.7.3

---

From: Brian E Carpenter <[email-masked]>
Date: Thu, 21 Jul 2016 00:59:05 +1200

> useful and IMHO should be explored.

And please note that draft-ietf-6man-multi-homed-host-07 (in IETF Last Call)
recommends hosts to support this, exactly to assist SADR solutions.

    Brian

---

From: David Lamparter <[email-masked]>
Date: Wed, 20 Jul 2016 15:06:36 +0200

> recommends hosts to support this, exactly to assist SADR solutions.

Yay!  I'm also happy to add that googling around the topic tells me at
least Windows already implements rule 5.5:
http://blog.ipspace.net/2016/01/ipv6-address-allocation-is-operating.html

-David

---

From: Lorenzo Colitti <[email-masked]>
Date: Wed, 20 Jul 2016 15:13:05 +0200

>   possibly have a copy of the PA's valid time?

The way I thought of doing this would be to alternatively/additionally keep
a pointer from the default router that announced a given prefix (which does
have the link-local address of the router) to each address that was
configured from that prefix. That way, when an address goes away you can
scan the FIB and find another router to associate with that prefix.

As for lifetimes expiring, you would need to have somewhere to keep dummy
zero-lifetime default routes. It might be possible to do this in the FIB
itself by adding a special entry that doesn't ever match anything, or has
an infinite metric, or a different type...

---

From: Brian E Carpenter <[email-masked]>
Date: Thu, 21 Jul 2016 01:22:15 +1200

> an infinite metric, or a different type...

Please tell us ASAP if there is anything we should add to
https://tools.ietf.org/html/draft-ietf-6man-multi-homed-host-03#section-3.2
or thereabouts.

    Brian

---

From: David Lamparter <[email-masked]>
Date: Wed, 20 Jul 2016 15:38:07 +0200

On Wed, Jul 20, 2016 at 03:13:05PM +0200, Lorenzo Colitti wrote:
> configured from that prefix.

That turns nontrivial as soon as you have 4191 RIOs, especially if the
router is trying to do walled gardens by sending its RAs with lifetime =
0 (as suggested in section 4.2.2 of pa-multihoming).

> That way, when an address goes away you can scan the FIB and find
> another router to associate with that prefix.

[I assume "address goes away" meant "router goes away"]

> an infinite metric, or a different type...

That sounds quite a bit more complicated than address-centric
handling...  we're 1:N for router['s LL address] to routes and also 1:N
for router['s LL address] to prefixes, and then 1:N for prefix to
derived addresses.

I'd rather copy the prefix lifetime (either valid or preferred -
probably former?) onto the same list entry where a configured address's
RA source LL is also stored; that replicates only the last 1:N step...
(So, for each address, in its list of RA sources that the prefix was
seen from, there will be a potentially-distinct lifetime.)

-David

P.S.: Does anyone know the details of how Windows implements this?

---

From: David Lamparter <[email-masked]>
Date: Wed, 20 Jul 2016 16:34:10 +0200

> https://tools.ietf.org/html/draft-ietf-6man-multi-homed-host-03#section-3.2

I do see some trouble in use-cases where more than one actual router
(actual = not counting extra link-local addresses on the same router) is
present on a link, advertising the same prefix to hosts.  (This is
reasonably likely in homenet scenarios, maybe less in enterprise.)

If the host only tracks a maximum of one RA source LL for a
prefix/address, but the router with that LL happens to not be the one
actually used (e.g. preference, router gone, more specific route from
RIO, whatever else) then the functionality is lost.  It's particularly
bad if the one RA source LL is the one prefix was first seen from (and
then, worst-case, never updated).

(The neccessary precondition / assumption being broken there is that the
test "was prefix X announced by router Y" doesn't report false
negatives.  I haven't applied brain to false positives yet.)

-David

---

From: Brian E Carpenter <[email-masked]>
Date: Thu, 21 Jul 2016 19:25:45 +1200

> negatives.  I haven't applied brain to false positives yet.)

Is this any worse than if the single default router in a traditional host
goes away, which will break all off-link packets until something happens?

I'm not saying it isn't a problem, but it doesn't sound like it's a new
problem that applies only in the multihomed case.

    Brian

---

From: Lorenzo Colitti <[email-masked]>
Date: Thu, 21 Jul 2016 09:49:46 +0200

> to this mail.  I've been able to gleam a little more detail on the idea:

David, do you intend to keep working on the patches? Think you could send
them to netdev as an RFC patchset, with proper signoff? Once it's on netdev
other people can iterate on them, even if you lose interest :-)

---

From: David Lamparter <[email-masked]>
Date: Wed, 27 Jul 2016 20:39:10 +0200

> other people can iterate on them, even if you lose interest :-)

I've uploaded the patches (with signoffs) to:
https://aurora.nox.tf/tmp/rule55/

NB: patch 2 of 3 is slightly different from the version I mailed, I
accidentally lost a NULL check in ipv6_rt_get_saddr().

I do _not_ intend to continue working on these since I now believe the
functionality should be put on neighbor cache entries.  This requires
some (minor IMHO) rework to make these neighbor entries stay alive until
their prefix information times out.  By putting it there, it can support
addresses that are configured from dhcpv6 or static/admin.  The code
linked above only works for SLAAC.

=> the patches are intended purely for testing, for example if someone
hacks on the router side and wants to use Linux VMs to test the full
picture.

Cheers,

-David