Discover default routers from Router Advertisements

This change allows the netstack to do NDP's Router Discovery as outlined by
RFC 4861 section 6.3.4.

Note, this change will not break existing uses of netstack as the default
configuration for the stack options is set in such a way that Router Discovery
will not be performed. See `stack.Options` and `stack.NDPConfigurations` for
more details.

This change introduces 2 options required to take advantage of Router Discovery,
all available under NDPConfigurations:
- HandleRAs: Whether or not NDP RAs are processes
- DiscoverDefaultRouters: Whether or not Router Discovery is performed

Another note: for a NIC to process Router Advertisements, it must not be a
router itself. Currently the netstack does not have per-interface routing
configuration; the routing/forwarding configuration is controlled stack-wide.
Therefore, if the stack is configured to enable forwarding/routing, no Router
Advertisements will be processed.

Tests: Unittest to make sure that Router Discovery and updates to the routing
table only occur if explicitly configured to do so. Unittest to make sure at
max stack.MaxDiscoveredDefaultRouters discovered default routers are remembered.
PiperOrigin-RevId: 278965143

1 files changed, 414 insertions, 12 deletions

diff --git a/pkg/tcpip/stack/ndp_test.go b/pkg/tcpip/stack/ndp_test.go
index cc789b5af..0dbe4da9d 100644
--- a/pkg/tcpip/stack/ndp_test.go
+++ b/pkg/tcpip/stack/ndp_test.go
@@ -15,9 +15,12 @@
 package stack_test
 
 import (
+	"encoding/binary"
+	"fmt"
 	"testing"
 	"time"
 
+	"github.com/google/go-cmp/cmp"
 	"gvisor.dev/gvisor/pkg/tcpip"
 	"gvisor.dev/gvisor/pkg/tcpip/buffer"
 	"gvisor.dev/gvisor/pkg/tcpip/checker"
@@ -29,10 +32,19 @@ import (
 )
 
 const (
-	addr1     = "\x0a\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x01"
-	addr2     = "\x0a\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x02"
-	addr3     = "\x0a\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x03"
-	linkAddr1 = "\x02\x02\x03\x04\x05\x06"
+	addr1          = "\x0a\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x01"
+	addr2          = "\x0a\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x02"
+	addr3          = "\x0a\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x03"
+	linkAddr1      = "\x02\x02\x03\x04\x05\x06"
+	linkAddr2      = "\x02\x02\x03\x04\x05\x07"
+	linkAddr3      = "\x02\x02\x03\x04\x05\x08"
+	defaultTimeout = 250 * time.Millisecond
+)
+
+var (
+	llAddr1 = header.LinkLocalAddr(linkAddr1)
+	llAddr2 = header.LinkLocalAddr(linkAddr2)
+	llAddr3 = header.LinkLocalAddr(linkAddr3)
 )
 
 // TestDADDisabled tests that an address successfully resolves immediately
@@ -77,26 +89,86 @@ type ndpDADEvent struct {
 	err      *tcpip.Error
 }
 
+type ndpRouterEvent struct {
+	nicid tcpip.NICID
+	addr  tcpip.Address
+	// true if router was discovered, false if invalidated.
+	discovered bool
+}
+
 var _ stack.NDPDispatcher = (*ndpDispatcher)(nil)
 
 // ndpDispatcher implements NDPDispatcher so tests can know when various NDP
 // related events happen for test purposes.
 type ndpDispatcher struct {
-	dadC chan ndpDADEvent
+	dadC           chan ndpDADEvent
+	routerC        chan ndpRouterEvent
+	rememberRouter bool
+	routeTable     []tcpip.Route
 }
 
 // Implements stack.NDPDispatcher.OnDuplicateAddressDetectionStatus.
-//
-// If the DAD event matches what we are expecting, send signal on n.dadC.
 func (n *ndpDispatcher) OnDuplicateAddressDetectionStatus(nicid tcpip.NICID, addr tcpip.Address, resolved bool, err *tcpip.Error) {
-	n.dadC <- ndpDADEvent{
-		nicid,
-		addr,
-		resolved,
-		err,
+	if n.dadC != nil {
+		n.dadC <- ndpDADEvent{
+			nicid,
+			addr,
+			resolved,
+			err,
+		}
 	}
 }
 
+// Implements stack.NDPDispatcher.OnDefaultRouterDiscovered.
+func (n *ndpDispatcher) OnDefaultRouterDiscovered(nicid tcpip.NICID, addr tcpip.Address) (bool, []tcpip.Route) {
+	if n.routerC != nil {
+		n.routerC <- ndpRouterEvent{
+			nicid,
+			addr,
+			true,
+		}
+	}
+
+	if !n.rememberRouter {
+		return false, nil
+	}
+
+	rt := append([]tcpip.Route(nil), n.routeTable...)
+	rt = append(rt, tcpip.Route{
+		Destination: header.IPv6EmptySubnet,
+		Gateway:     addr,
+		NIC:         nicid,
+	})
+	n.routeTable = rt
+	return true, rt
+}
+
+// Implements stack.NDPDispatcher.OnDefaultRouterInvalidated.
+func (n *ndpDispatcher) OnDefaultRouterInvalidated(nicid tcpip.NICID, addr tcpip.Address) []tcpip.Route {
+	if n.routerC != nil {
+		n.routerC <- ndpRouterEvent{
+			nicid,
+			addr,
+			false,
+		}
+	}
+
+	var rt []tcpip.Route
+	exclude := tcpip.Route{
+		Destination: header.IPv6EmptySubnet,
+		Gateway:     addr,
+		NIC:         nicid,
+	}
+
+	for _, r := range n.routeTable {
+		if r != exclude {
+			rt = append(rt, r)
+		}
+	}
+	n.routeTable = rt
+	return rt
+}
+
 // TestDADResolve tests that an address successfully resolves after performing
 // DAD for various values of DupAddrDetectTransmits and RetransmitTimer.
 // Included in the subtests is a test to make sure that an invalid
@@ -609,3 +681,333 @@ func TestSetNDPConfigurations(t *testing.T) {
 		})
 	}
 }
+
+// raBuf returns a valid NDP Router Advertisement.
+//
+// Note, raBuf does not populate any of the RA fields other than the
+// Router Lifetime.
+func raBuf(ip tcpip.Address, rl uint16) tcpip.PacketBuffer {
+	icmpSize := header.ICMPv6HeaderSize + header.NDPRAMinimumSize
+	hdr := buffer.NewPrependable(header.IPv6MinimumSize + icmpSize)
+	pkt := header.ICMPv6(hdr.Prepend(icmpSize))
+	pkt.SetType(header.ICMPv6RouterAdvert)
+	pkt.SetCode(0)
+	// Populate the Router Lifetime.
+	binary.BigEndian.PutUint16(pkt.NDPPayload()[2:], rl)
+	pkt.SetChecksum(header.ICMPv6Checksum(pkt, ip, header.IPv6AllNodesMulticastAddress, buffer.VectorisedView{}))
+	payloadLength := hdr.UsedLength()
+	iph := header.IPv6(hdr.Prepend(header.IPv6MinimumSize))
+	iph.Encode(&header.IPv6Fields{
+		PayloadLength: uint16(payloadLength),
+		NextHeader:    uint8(icmp.ProtocolNumber6),
+		HopLimit:      header.NDPHopLimit,
+		SrcAddr:       ip,
+		DstAddr:       header.IPv6AllNodesMulticastAddress,
+	})
+
+	return tcpip.PacketBuffer{Data: hdr.View().ToVectorisedView()}
+}
+
+// TestNoRouterDiscovery tests that router discovery will not be performed if
+// configured not to.
+func TestNoRouterDiscovery(t *testing.T) {
+	// Being configured to discover routers means handle and
+	// discover are set to true and forwarding is set to false.
+	// This tests all possible combinations of the configurations,
+	// except for the configuration where handle = true, discover =
+	// true and forwarding = false (the required configuration to do
+	// router discovery) - that will done in other tests.
+	for i := 0; i < 7; i++ {
+		handle := i&1 != 0
+		discover := i&2 != 0
+		forwarding := i&4 == 0
+
+		t.Run(fmt.Sprintf("HandleRAs(%t), DiscoverDefaultRouters(%t), Forwarding(%t)", handle, discover, forwarding), func(t *testing.T) {
+			ndpDisp := ndpDispatcher{
+				routerC: make(chan ndpRouterEvent, 10),
+			}
+			e := channel.New(10, 1280, linkAddr1)
+			s := stack.New(stack.Options{
+				NetworkProtocols: []stack.NetworkProtocol{ipv6.NewProtocol()},
+				NDPConfigs: stack.NDPConfigurations{
+					HandleRAs:              handle,
+					DiscoverDefaultRouters: discover,
+				},
+				NDPDisp: &ndpDisp,
+			})
+			s.SetForwarding(forwarding)
+
+			if err := s.CreateNIC(1, e); err != nil {
+				t.Fatalf("CreateNIC(1) = %s", err)
+			}
+
+			// Rx an RA with non-zero lifetime.
+			e.InjectInbound(header.IPv6ProtocolNumber, raBuf(llAddr2, 1000))
+			select {
+			case <-ndpDisp.routerC:
+				t.Fatal("unexpectedly discovered a router when configured not to")
+			case <-time.After(defaultTimeout):
+			}
+		})
+	}
+}
+
+// TestRouterDiscoveryDispatcherNoRemember tests that the stack does not
+// remember a discovered router when the dispatcher asks it not to.
+func TestRouterDiscoveryDispatcherNoRemember(t *testing.T) {
+	ndpDisp := ndpDispatcher{
+		routerC: make(chan ndpRouterEvent, 10),
+	}
+	e := channel.New(10, 1280, linkAddr1)
+	s := stack.New(stack.Options{
+		NetworkProtocols: []stack.NetworkProtocol{ipv6.NewProtocol()},
+		NDPConfigs: stack.NDPConfigurations{
+			HandleRAs:              true,
+			DiscoverDefaultRouters: true,
+		},
+		NDPDisp: &ndpDisp,
+	})
+
+	if err := s.CreateNIC(1, e); err != nil {
+		t.Fatalf("CreateNIC(1) = %s", err)
+	}
+
+	routeTable := []tcpip.Route{
+		{
+			header.IPv6EmptySubnet,
+			llAddr3,
+			1,
+		},
+	}
+	s.SetRouteTable(routeTable)
+
+	// Rx an RA with short lifetime.
+	lifetime := time.Duration(1)
+	e.InjectInbound(header.IPv6ProtocolNumber, raBuf(llAddr2, uint16(lifetime)))
+	select {
+	case r := <-ndpDisp.routerC:
+		if r.nicid != 1 {
+			t.Fatalf("got r.nicid = %d, want = 1", r.nicid)
+		}
+		if r.addr != llAddr2 {
+			t.Fatalf("got r.addr = %s, want = %s", r.addr, llAddr2)
+		}
+		if !r.discovered {
+			t.Fatal("got r.discovered = false, want = true")
+		}
+	case <-time.After(defaultTimeout):
+		t.Fatal("timeout waiting for router discovery event")
+	}
+
+	// Original route table should not have been modified.
+	if got := s.GetRouteTable(); !cmp.Equal(got, routeTable) {
+		t.Fatalf("got GetRouteTable = %v, want = %v", got, routeTable)
+	}
+
+	// Wait for the normal invalidation time plus an extra second to
+	// make sure we do not actually receive any invalidation events as
+	// we should not have remembered the router in the first place.
+	select {
+	case <-ndpDisp.routerC:
+		t.Fatal("should not have received any router events")
+	case <-time.After(lifetime*time.Second + defaultTimeout):
+	}
+
+	// Original route table should not have been modified.
+	if got := s.GetRouteTable(); !cmp.Equal(got, routeTable) {
+		t.Fatalf("got GetRouteTable = %v, want = %v", got, routeTable)
+	}
+}
+
+func TestRouterDiscovery(t *testing.T) {
+	ndpDisp := ndpDispatcher{
+		routerC:        make(chan ndpRouterEvent, 10),
+		rememberRouter: true,
+	}
+	e := channel.New(10, 1280, linkAddr1)
+	s := stack.New(stack.Options{
+		NetworkProtocols: []stack.NetworkProtocol{ipv6.NewProtocol()},
+		NDPConfigs: stack.NDPConfigurations{
+			HandleRAs:              true,
+			DiscoverDefaultRouters: true,
+		},
+		NDPDisp: &ndpDisp,
+	})
+
+	waitForEvent := func(addr tcpip.Address, discovered bool, timeout time.Duration) {
+		t.Helper()
+
+		select {
+		case r := <-ndpDisp.routerC:
+			if r.nicid != 1 {
+				t.Fatalf("got r.nicid = %d, want = 1", r.nicid)
+			}
+			if r.addr != addr {
+				t.Fatalf("got r.addr = %s, want = %s", r.addr, addr)
+			}
+			if r.discovered != discovered {
+				t.Fatalf("got r.discovered = %t, want = %t", r.discovered, discovered)
+			}
+		case <-time.After(timeout):
+			t.Fatal("timeout waiting for router discovery event")
+		}
+	}
+
+	if err := s.CreateNIC(1, e); err != nil {
+		t.Fatalf("CreateNIC(1) = %s", err)
+	}
+
+	// Rx an RA from lladdr2 with zero lifetime. It should not be
+	// remembered.
+	e.InjectInbound(header.IPv6ProtocolNumber, raBuf(llAddr2, 0))
+	select {
+	case <-ndpDisp.routerC:
+		t.Fatal("unexpectedly discovered a router with 0 lifetime")
+	case <-time.After(defaultTimeout):
+	}
+
+	// Rx an RA from lladdr2 with a huge lifetime.
+	e.InjectInbound(header.IPv6ProtocolNumber, raBuf(llAddr2, 1000))
+	waitForEvent(llAddr2, true, defaultTimeout)
+
+	// Should have a default route through the discovered router.
+	if got, want := s.GetRouteTable(), []tcpip.Route{{header.IPv6EmptySubnet, llAddr2, 1}}; !cmp.Equal(got, want) {
+		t.Fatalf("got GetRouteTable = %v, want = %v", got, want)
+	}
+
+	// Rx an RA from another router (lladdr3) with non-zero lifetime.
+	l3Lifetime := time.Duration(6)
+	e.InjectInbound(header.IPv6ProtocolNumber, raBuf(llAddr3, uint16(l3Lifetime)))
+	waitForEvent(llAddr3, true, defaultTimeout)
+
+	// Should have default routes through the discovered routers.
+	if got, want := s.GetRouteTable(), []tcpip.Route{{header.IPv6EmptySubnet, llAddr2, 1}, {header.IPv6EmptySubnet, llAddr3, 1}}; !cmp.Equal(got, want) {
+		t.Fatalf("got GetRouteTable = %v, want = %v", got, want)
+	}
+
+	// Rx an RA from lladdr2 with lesser lifetime.
+	l2Lifetime := time.Duration(2)
+	e.InjectInbound(header.IPv6ProtocolNumber, raBuf(llAddr2, uint16(l2Lifetime)))
+	select {
+	case <-ndpDisp.routerC:
+		t.Fatal("Should not receive a router event when updating lifetimes for known routers")
+	case <-time.After(defaultTimeout):
+	}
+
+	// Should still have a default route through the discovered routers.
+	if got, want := s.GetRouteTable(), []tcpip.Route{{header.IPv6EmptySubnet, llAddr2, 1}, {header.IPv6EmptySubnet, llAddr3, 1}}; !cmp.Equal(got, want) {
+		t.Fatalf("got GetRouteTable = %v, want = %v", got, want)
+	}
+
+	// Wait for lladdr2's router invalidation timer to fire. The lifetime
+	// of the router should have been updated to the most recent (smaller)
+	// lifetime.
+	//
+	// Wait for the normal lifetime plus an extra bit for the
+	// router to get invalidated. If we don't get an invalidation
+	// event after this time, then something is wrong.
+	waitForEvent(llAddr2, false, l2Lifetime*time.Second+defaultTimeout)
+
+	// Should no longer have the default route through lladdr2.
+	if got, want := s.GetRouteTable(), []tcpip.Route{{header.IPv6EmptySubnet, llAddr3, 1}}; !cmp.Equal(got, want) {
+		t.Fatalf("got GetRouteTable = %v, want = %v", got, want)
+	}
+
+	// Rx an RA from lladdr2 with huge lifetime.
+	e.InjectInbound(header.IPv6ProtocolNumber, raBuf(llAddr2, 1000))
+	waitForEvent(llAddr2, true, defaultTimeout)
+
+	// Should have a default route through the discovered routers.
+	if got, want := s.GetRouteTable(), []tcpip.Route{{header.IPv6EmptySubnet, llAddr3, 1}, {header.IPv6EmptySubnet, llAddr2, 1}}; !cmp.Equal(got, want) {
+		t.Fatalf("got GetRouteTable = %v, want = %v", got, want)
+	}
+
+	// Rx an RA from lladdr2 with zero lifetime. It should be invalidated.
+	e.InjectInbound(header.IPv6ProtocolNumber, raBuf(llAddr2, 0))
+	waitForEvent(llAddr2, false, defaultTimeout)
+
+	// Should have deleted the default route through the router that just
+	// got invalidated.
+	if got, want := s.GetRouteTable(), []tcpip.Route{{header.IPv6EmptySubnet, llAddr3, 1}}; !cmp.Equal(got, want) {
+		t.Fatalf("got GetRouteTable = %v, want = %v", got, want)
+	}
+
+	// Wait for lladdr3's router invalidation timer to fire. The lifetime
+	// of the router should have been updated to the most recent (smaller)
+	// lifetime.
+	//
+	// Wait for the normal lifetime plus an extra bit for the
+	// router to get invalidated. If we don't get an invalidation
+	// event after this time, then something is wrong.
+	waitForEvent(llAddr3, false, l3Lifetime*time.Second+defaultTimeout)
+
+	// Should not have any routes now that all discovered routers have been
+	// invalidated.
+	if got := len(s.GetRouteTable()); got != 0 {
+		t.Fatalf("got len(s.GetRouteTable()) = %d, want = 0", got)
+	}
+}
+
+// TestRouterDiscoveryMaxRouters tests that only
+// stack.MaxDiscoveredDefaultRouters discovered routers are remembered.
+func TestRouterDiscoveryMaxRouters(t *testing.T) {
+	ndpDisp := ndpDispatcher{
+		routerC:        make(chan ndpRouterEvent, 10),
+		rememberRouter: true,
+	}
+	e := channel.New(10, 1280, linkAddr1)
+	s := stack.New(stack.Options{
+		NetworkProtocols: []stack.NetworkProtocol{ipv6.NewProtocol()},
+		NDPConfigs: stack.NDPConfigurations{
+			HandleRAs:              true,
+			DiscoverDefaultRouters: true,
+		},
+		NDPDisp: &ndpDisp,
+	})
+
+	if err := s.CreateNIC(1, e); err != nil {
+		t.Fatalf("CreateNIC(1) = %s", err)
+	}
+
+	expectedRt := [stack.MaxDiscoveredDefaultRouters]tcpip.Route{}
+
+	// Receive an RA from 2 more than the max number of discovered routers.
+	for i := 1; i <= stack.MaxDiscoveredDefaultRouters+2; i++ {
+		linkAddr := []byte{2, 2, 3, 4, 5, 0}
+		linkAddr[5] = byte(i)
+		llAddr := header.LinkLocalAddr(tcpip.LinkAddress(linkAddr))
+
+		e.InjectInbound(header.IPv6ProtocolNumber, raBuf(llAddr, 5))
+
+		if i <= stack.MaxDiscoveredDefaultRouters {
+			expectedRt[i-1] = tcpip.Route{header.IPv6EmptySubnet, llAddr, 1}
+			select {
+			case r := <-ndpDisp.routerC:
+				if r.nicid != 1 {
+					t.Fatalf("got r.nicid = %d, want = 1", r.nicid)
+				}
+				if r.addr != llAddr {
+					t.Fatalf("got r.addr = %s, want = %s", r.addr, llAddr)
+				}
+				if !r.discovered {
+					t.Fatal("got r.discovered = false, want = true")
+				}
+			case <-time.After(defaultTimeout):
+				t.Fatal("timeout waiting for router discovery event")
+			}
+
+		} else {
+			select {
+			case <-ndpDisp.routerC:
+				t.Fatal("should not have discovered a new router after we already discovered the max number of routers")
+			case <-time.After(defaultTimeout):
+			}
+		}
+	}
+
+	// Should only have default routes for the first
+	// stack.MaxDiscoveredDefaultRouters discovered routers.
+	if got := s.GetRouteTable(); !cmp.Equal(got, expectedRt[:]) {
+		t.Fatalf("got GetRouteTable = %v, want = %v", got, expectedRt)
+	}
+}