Discover on-link prefixes from Router Advertisements' Prefix Information options

This change allows the netstack to do NDP's Prefix Discovery as outlined by
RFC 4861 section 6.3.4. If configured to do so, when a new on-link prefix is
discovered, the routing table will be updated with a device route through
the nic the RA arrived at. Likewise, when such a prefix gets invalidated, the
device route will be removed.

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 Prefix Discovery
will not be performed. See `stack.Options` and `stack.NDPConfigurations` for
more details.

This change reuses 1 option and introduces a new one that is required to take
advantage of Prefix Discovery, all available under NDPConfigurations:
- HandleRAs: Whether or not NDP RAs are processes
- DiscoverOnLinkPrefixes: Whether or not Prefix Discovery is performed (new)

Another note: for a NIC to process Prefix Information options (in 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 (and by extension the Prefix
Information options) will be processed.

Tests: Unittest to make sure that Prefix Discovery and updates to the routing
table only occur if explicitly configured to do so. Unittest to make sure at
max stack.MaxDiscoveredOnLinkPrefixes discovered on-link prefixes are
remembered.
PiperOrigin-RevId: 280049278

4 files changed, 836 insertions, 33 deletions

diff --git a/pkg/tcpip/header/ndp_options.go b/pkg/tcpip/header/ndp_options.go
index a2b9d7435..1ca6199ef 100644
--- a/pkg/tcpip/header/ndp_options.go
+++ b/pkg/tcpip/header/ndp_options.go
@@ -85,17 +85,22 @@ const (
 	// within an NDPPrefixInformation.
 	ndpPrefixInformationPrefixOffset = 14
 
-	// NDPPrefixInformationInfiniteLifetime is a value that represents
-	// infinity for the Valid and Preferred Lifetime fields in a NDP Prefix
-	// Information option. Its value is (2^32 - 1)s = 4294967295s
-	NDPPrefixInformationInfiniteLifetime = time.Second * 4294967295
-
 	// lengthByteUnits is the multiplier factor for the Length field of an
 	// NDP option. That is, the length field for NDP options is in units of
 	// 8 octets, as per RFC 4861 section 4.6.
 	lengthByteUnits = 8
 )
 
+var (
+	// NDPPrefixInformationInfiniteLifetime is a value that represents
+	// infinity for the Valid and Preferred Lifetime fields in a NDP Prefix
+	// Information option. Its value is (2^32 - 1)s = 4294967295s
+	//
+	// This is a variable instead of a constant so that tests can change
+	// this value to a smaller value. It should only be modified by tests.
+	NDPPrefixInformationInfiniteLifetime = time.Second * 4294967295
+)
+
 // NDPOptionIterator is an iterator of NDPOption.
 //
 // Note, between when an NDPOptionIterator is obtained and last used, no changes
@@ -461,3 +466,13 @@ func (o NDPPrefixInformation) PreferredLifetime() time.Duration {
 func (o NDPPrefixInformation) Prefix() tcpip.Address {
 	return tcpip.Address(o[ndpPrefixInformationPrefixOffset:][:IPv6AddressSize])
 }
+
+// Subnet returns the Prefix field and Prefix Length field represented in a
+// tcpip.Subnet.
+func (o NDPPrefixInformation) Subnet() tcpip.Subnet {
+	addrWithPrefix := tcpip.AddressWithPrefix{
+		Address:   o.Prefix(),
+		PrefixLen: int(o.PrefixLength()),
+	}
+	return addrWithPrefix.Subnet()
+}
diff --git a/pkg/tcpip/stack/ndp.go b/pkg/tcpip/stack/ndp.go
index 8e49f7a56..8357dca77 100644
--- a/pkg/tcpip/stack/ndp.go
+++ b/pkg/tcpip/stack/ndp.go
@@ -46,11 +46,18 @@ const (
 
 	// defaultDiscoverDefaultRouters is the default configuration for
 	// whether or not to discover default routers from incoming Router
-	// Advertisements as a host.
+	// Advertisements, as a host.
 	//
 	// Default = true.
 	defaultDiscoverDefaultRouters = true
 
+	// defaultDiscoverOnLinkPrefixes is the default configuration for
+	// whether or not to discover on-link prefixes from incoming Router
+	// Advertisements' Prefix Information option, as a host.
+	//
+	// Default = true.
+	defaultDiscoverOnLinkPrefixes = true
+
 	// minimumRetransmitTimer is the minimum amount of time to wait between
 	// sending NDP Neighbor solicitation messages. Note, RFC 4861 does
 	// not impose a minimum Retransmit Timer, but we do here to make sure
@@ -72,6 +79,14 @@ const (
 	//
 	// Max = 10.
 	MaxDiscoveredDefaultRouters = 10
+
+	// MaxDiscoveredOnLinkPrefixes is the maximum number of discovered
+	// on-link prefixes. The stack should stop discovering new on-link
+	// prefixes after discovering MaxDiscoveredOnLinkPrefixes on-link
+	// prefixes.
+	//
+	// Max = 10.
+	MaxDiscoveredOnLinkPrefixes = 10
 )
 
 // NDPDispatcher is the interface integrators of netstack must implement to
@@ -106,6 +121,24 @@ type NDPDispatcher interface {
 	// This function is not permitted to block indefinitely. This function
 	// is also not permitted to call into the stack.
 	OnDefaultRouterInvalidated(nicID tcpip.NICID, addr tcpip.Address) []tcpip.Route
+
+	// OnOnLinkPrefixDiscovered will be called when a new on-link prefix is
+	// discovered. Implementations must return true along with a new valid
+	// route table if the newly discovered on-link prefix should be
+	// remembered. If an implementation returns false, the second return
+	// value will be ignored.
+	//
+	// This function is not permitted to block indefinitely. This function
+	// is also not permitted to call into the stack.
+	OnOnLinkPrefixDiscovered(nicID tcpip.NICID, prefix tcpip.Subnet) (bool, []tcpip.Route)
+
+	// OnOnLinkPrefixInvalidated will be called when a discovered on-link
+	// prefix is invalidated. Implementers must return a new valid route
+	// table.
+	//
+	// This function is not permitted to block indefinitely. This function
+	// is also not permitted to call into the stack.
+	OnOnLinkPrefixInvalidated(nicID tcpip.NICID, prefix tcpip.Subnet) []tcpip.Route
 }
 
 // NDPConfigurations is the NDP configurations for the netstack.
@@ -130,6 +163,11 @@ type NDPConfigurations struct {
 	// be discovered from Router Advertisements. This configuration is
 	// ignored if HandleRAs is false.
 	DiscoverDefaultRouters bool
+
+	// DiscoverOnLinkPrefixes determines whether or not on-link prefixes
+	// will be discovered from Router Advertisements' Prefix Information
+	// option. This configuration is ignored if HandleRAs is false.
+	DiscoverOnLinkPrefixes bool
 }
 
 // DefaultNDPConfigurations returns an NDPConfigurations populated with
@@ -140,6 +178,7 @@ func DefaultNDPConfigurations() NDPConfigurations {
 		RetransmitTimer:        defaultRetransmitTimer,
 		HandleRAs:              defaultHandleRAs,
 		DiscoverDefaultRouters: defaultDiscoverDefaultRouters,
+		DiscoverOnLinkPrefixes: defaultDiscoverOnLinkPrefixes,
 	}
 }
 
@@ -167,6 +206,10 @@ type ndpState struct {
 
 	// The default routers discovered through Router Advertisements.
 	defaultRouters map[tcpip.Address]defaultRouterState
+
+	// The on-link prefixes discovered through Router Advertisements' Prefix
+	// Information option.
+	onLinkPrefixes map[tcpip.Subnet]onLinkPrefixState
 }
 
 // dadState holds the Duplicate Address Detection timer and channel to signal
@@ -183,11 +226,11 @@ type dadState struct {
 }
 
 // defaultRouterState holds data associated with a default router discovered by
-// a Router Advertisement.
+// a Router Advertisement (RA).
 type defaultRouterState struct {
 	invalidationTimer *time.Timer
 
-	// Used to signal the timer not to invalidate the default router (R) in
+	// Used to inform the timer not to invalidate the default router (R) in
 	// a race condition (T1 is a goroutine that handles an RA from R and T2
 	// is the goroutine that handles R's invalidation timer firing):
 	//   T1: Receive a new RA from R
@@ -198,10 +241,33 @@ type defaultRouterState struct {
 	//   T2: Obtains NIC's lock & invalidates R immediately
 	//
 	// To resolve this, T1 will check to see if the timer already fired, and
-	// signal the timer using this channel to not invalidate R, so that once
-	// T2 obtains the lock, it will see that there is an event on this
-	// channel and do nothing further.
-	doNotInvalidateC chan struct{}
+	// inform the timer using doNotInvalidate to not invalidate R, so that
+	// once T2 obtains the lock, it will see that it is set to true and do
+	// nothing further.
+	doNotInvalidate *bool
+}
+
+// onLinkPrefixState holds data associated with an on-link prefix discovered by
+// a Router Advertisement's Prefix Information option (PI) when the NDP
+// configurations was configured to do so.
+type onLinkPrefixState struct {
+	invalidationTimer *time.Timer
+
+	// Used to signal the timer not to invalidate the on-link prefix (P) in
+	// a race condition (T1 is a goroutine that handles a PI for P and T2
+	// is the goroutine that handles P's invalidation timer firing):
+	//   T1: Receive a new PI for P
+	//   T1: Obtain the NIC's lock before processing the PI
+	//   T2: P's invalidation timer fires, and gets blocked on obtaining the
+	//       NIC's lock
+	//   T1: Refreshes/extends P's lifetime & releases NIC's lock
+	//   T2: Obtains NIC's lock & invalidates P immediately
+	//
+	// To resolve this, T1 will check to see if the timer already fired, and
+	// inform the timer using doNotInvalidate to not invalidate P, so that
+	// once T2 obtains the lock, it will see that it is set to true and do
+	// nothing further.
+	doNotInvalidate *bool
 }
 
 // startDuplicateAddressDetection performs Duplicate Address Detection.
@@ -440,14 +506,13 @@ func (ndp *ndpState) handleRA(ip tcpip.Address, ra header.NDPRouterAdvert) {
 			if !timer.Stop() {
 				// If we reach this point, then we know the
 				// timer fired after we already took the NIC
-				// lock. Signal the timer so that once it
-				// obtains the lock, it doesn't actually
-				// invalidate the router as we just got a new
-				// RA that refreshes its lifetime to a non-zero
-				// value. See
-				// defaultRouterState.doNotInvalidateC for more
+				// lock. Inform the timer not to invalidate the
+				// router when it obtains the lock as we just
+				// got a new RA that refreshes its lifetime to a
+				// non-zero value. See
+				// defaultRouterState.doNotInvalidate for more
 				// details.
-				rtr.doNotInvalidateC <- struct{}{}
+				*rtr.doNotInvalidate = true
 			}
 
 			timer.Reset(rl)
@@ -459,8 +524,117 @@ func (ndp *ndpState) handleRA(ip tcpip.Address, ra header.NDPRouterAdvert) {
 		}
 	}
 
-	// TODO(b/140948104): Do Prefix Discovery.
-	// TODO(b/141556115): Do Parameter Discovery.
+	// TODO(b/141556115): Do (RetransTimer, ReachableTime)) Parameter
+	//                    Discovery.
+
+	// We know the options is valid as far as wire format is concerned since
+	// we got the Router Advertisement, as documented by this fn. Given this
+	// we do not check the iterator for errors on calls to Next.
+	it, _ := ra.Options().Iter(false)
+	for opt, done, _ := it.Next(); !done; opt, done, _ = it.Next() {
+		switch opt.Type() {
+		case header.NDPPrefixInformationType:
+			if !ndp.configs.DiscoverOnLinkPrefixes {
+				continue
+			}
+
+			pi := opt.(header.NDPPrefixInformation)
+
+			prefix := pi.Subnet()
+
+			// Is the prefix a link-local?
+			if header.IsV6LinkLocalAddress(prefix.ID()) {
+				// ...Yes, skip as per RFC 4861 section 6.3.4.
+				continue
+			}
+
+			// Is the Prefix Length 0?
+			if prefix.Prefix() == 0 {
+				// ...Yes, skip as this is an invalid prefix
+				// as all IPv6 addresses cannot be on-link.
+				continue
+			}
+
+			if !pi.OnLinkFlag() {
+				// Not on-link so don't "discover" it as an
+				// on-link prefix.
+				continue
+			}
+
+			prefixState, ok := ndp.onLinkPrefixes[prefix]
+			vl := pi.ValidLifetime()
+			switch {
+			case !ok && vl == 0:
+				// Don't know about this prefix but has a zero
+				// valid lifetime, so just ignore.
+				continue
+
+			case !ok && vl != 0:
+				// This is a new on-link prefix we are
+				// discovering.
+				//
+				// Only remember it if we currently know about
+				// less than MaxDiscoveredOnLinkPrefixes on-link
+				// prefixes.
+				if len(ndp.onLinkPrefixes) < MaxDiscoveredOnLinkPrefixes {
+					ndp.rememberOnLinkPrefix(prefix, vl)
+				}
+				continue
+
+			case ok && vl == 0:
+				// We know about the on-link prefix, but it is
+				// no longer to be considered on-link, so
+				// invalidate it.
+				ndp.invalidateOnLinkPrefix(prefix)
+				continue
+			}
+
+			// This is an already discovered on-link prefix with a
+			// new non-zero valid lifetime.
+			// Update the invalidation timer.
+			timer := prefixState.invalidationTimer
+
+			if timer == nil && vl >= header.NDPPrefixInformationInfiniteLifetime {
+				// Had infinite valid lifetime before and
+				// continues to have an invalid lifetime. Do
+				// nothing further.
+				continue
+			}
+
+			if timer != nil && !timer.Stop() {
+				// If we reach this point, then we know the
+				// timer already fired after we took the NIC
+				// lock. Inform the timer to not invalidate
+				// the prefix once it obtains the lock as we
+				// just got a new PI that refeshes its lifetime
+				// to a non-zero value. See
+				// onLinkPrefixState.doNotInvalidate for more
+				// details.
+				*prefixState.doNotInvalidate = true
+			}
+
+			if vl >= header.NDPPrefixInformationInfiniteLifetime {
+				// Prefix is now valid forever so we don't need
+				// an invalidation timer.
+				prefixState.invalidationTimer = nil
+				ndp.onLinkPrefixes[prefix] = prefixState
+				continue
+			}
+
+			if timer != nil {
+				// We already have a timer so just reset it to
+				// expire after the new valid lifetime.
+				timer.Reset(vl)
+				continue
+			}
+
+			// We do not have a timer so just create a new one.
+			prefixState.invalidationTimer = ndp.prefixInvalidationCallback(prefix, vl, prefixState.doNotInvalidate)
+			ndp.onLinkPrefixes[prefix] = prefixState
+		}
+
+		// TODO(b/141556115): Do (MTU) Parameter Discovery.
+	}
 }
 
 // invalidateDefaultRouter invalidates a discovered default router.
@@ -477,8 +651,8 @@ func (ndp *ndpState) invalidateDefaultRouter(ip tcpip.Address) {
 
 	rtr.invalidationTimer.Stop()
 	rtr.invalidationTimer = nil
-	close(rtr.doNotInvalidateC)
-	rtr.doNotInvalidateC = nil
+	*rtr.doNotInvalidate = true
+	rtr.doNotInvalidate = nil
 
 	delete(ndp.defaultRouters, ip)
 
@@ -508,9 +682,9 @@ func (ndp *ndpState) rememberDefaultRouter(ip tcpip.Address, rl time.Duration) {
 	}
 
 	// Used to signal the timer not to invalidate the default router (R) in
-	// a race condition. See defaultRouterState.doNotInvalidateC for more
+	// a race condition. See defaultRouterState.doNotInvalidate for more
 	// details.
-	doNotInvalidateC := make(chan struct{}, 1)
+	var doNotInvalidate bool
 
 	ndp.defaultRouters[ip] = defaultRouterState{
 		invalidationTimer: time.AfterFunc(rl, func() {
@@ -519,16 +693,103 @@ func (ndp *ndpState) rememberDefaultRouter(ip tcpip.Address, rl time.Duration) {
 			ndp.nic.mu.Lock()
 			defer ndp.nic.mu.Unlock()
 
-			select {
-			case <-doNotInvalidateC:
+			if doNotInvalidate {
+				doNotInvalidate = false
 				return
-			default:
 			}
 
 			ndp.invalidateDefaultRouter(ip)
 		}),
-		doNotInvalidateC: doNotInvalidateC,
+		doNotInvalidate: &doNotInvalidate,
+	}
+
+	ndp.nic.stack.routeTable = routeTable
+}
+
+// rememberOnLinkPrefix remembers a newly discovered on-link prefix with IPv6
+// address with prefix prefix with lifetime l.
+//
+// The prefix identified by prefix MUST NOT already be known.
+//
+// The NIC that ndp belongs to and its associated stack MUST be locked.
+func (ndp *ndpState) rememberOnLinkPrefix(prefix tcpip.Subnet, l time.Duration) {
+	if ndp.nic.stack.ndpDisp == nil {
+		return
+	}
+
+	// Inform the integrator when we discovered an on-link prefix.
+	remember, routeTable := ndp.nic.stack.ndpDisp.OnOnLinkPrefixDiscovered(ndp.nic.ID(), prefix)
+	if !remember {
+		// Informed by the integrator to not remember the prefix, do
+		// nothing further.
+		return
+	}
+
+	// Used to signal the timer not to invalidate the on-link prefix (P) in
+	// a race condition. See onLinkPrefixState.doNotInvalidate for more
+	// details.
+	var doNotInvalidate bool
+	var timer *time.Timer
+
+	// Only create a timer if the lifetime is not infinite.
+	if l < header.NDPPrefixInformationInfiniteLifetime {
+		timer = ndp.prefixInvalidationCallback(prefix, l, &doNotInvalidate)
+	}
+
+	ndp.onLinkPrefixes[prefix] = onLinkPrefixState{
+		invalidationTimer: timer,
+		doNotInvalidate:   &doNotInvalidate,
 	}
 
 	ndp.nic.stack.routeTable = routeTable
 }
+
+// invalidateOnLinkPrefix invalidates a discovered on-link prefix.
+//
+// The NIC that ndp belongs to and its associated stack MUST be locked.
+func (ndp *ndpState) invalidateOnLinkPrefix(prefix tcpip.Subnet) {
+	s, ok := ndp.onLinkPrefixes[prefix]
+
+	// Is the on-link prefix still discovered?
+	if !ok {
+		// ...Nope, do nothing further.
+		return
+	}
+
+	if s.invalidationTimer != nil {
+		s.invalidationTimer.Stop()
+		s.invalidationTimer = nil
+		*s.doNotInvalidate = true
+	}
+
+	s.doNotInvalidate = nil
+
+	delete(ndp.onLinkPrefixes, prefix)
+
+	// Let the integrator know a discovered on-link prefix is invalidated.
+	if ndp.nic.stack.ndpDisp != nil {
+		ndp.nic.stack.routeTable = ndp.nic.stack.ndpDisp.OnOnLinkPrefixInvalidated(ndp.nic.ID(), prefix)
+	}
+}
+
+// prefixInvalidationCallback returns a new on-link prefix invalidation timer
+// for prefix that fires after vl.
+//
+// doNotInvalidate is used to signal the timer when it fires at the same time
+// that a prefix's valid lifetime gets refreshed. See
+// onLinkPrefixState.doNotInvalidate for more details.
+func (ndp *ndpState) prefixInvalidationCallback(prefix tcpip.Subnet, vl time.Duration, doNotInvalidate *bool) *time.Timer {
+	return time.AfterFunc(vl, func() {
+		ndp.nic.stack.mu.Lock()
+		defer ndp.nic.stack.mu.Unlock()
+		ndp.nic.mu.Lock()
+		defer ndp.nic.mu.Unlock()
+
+		if *doNotInvalidate {
+			*doNotInvalidate = false
+			return
+		}
+
+		ndp.invalidateOnLinkPrefix(prefix)
+	})
+}
diff --git a/pkg/tcpip/stack/ndp_test.go b/pkg/tcpip/stack/ndp_test.go
index 50ce1bbfa..494244368 100644
--- a/pkg/tcpip/stack/ndp_test.go
+++ b/pkg/tcpip/stack/ndp_test.go
@@ -96,6 +96,13 @@ type ndpRouterEvent struct {
 	discovered bool
 }
 
+type ndpPrefixEvent struct {
+	nicID  tcpip.NICID
+	prefix tcpip.Subnet
+	// true if prefix was discovered, false if invalidated.
+	discovered bool
+}
+
 var _ stack.NDPDispatcher = (*ndpDispatcher)(nil)
 
 // ndpDispatcher implements NDPDispatcher so tests can know when various NDP
@@ -104,6 +111,8 @@ type ndpDispatcher struct {
 	dadC           chan ndpDADEvent
 	routerC        chan ndpRouterEvent
 	rememberRouter bool
+	prefixC        chan ndpPrefixEvent
+	rememberPrefix bool
 	routeTable     []tcpip.Route
 }
 
@@ -169,6 +178,54 @@ func (n *ndpDispatcher) OnDefaultRouterInvalidated(nicID tcpip.NICID, addr tcpip
 	return rt
 }
 
+// Implements stack.NDPDispatcher.OnOnLinkPrefixDiscovered.
+func (n *ndpDispatcher) OnOnLinkPrefixDiscovered(nicID tcpip.NICID, prefix tcpip.Subnet) (bool, []tcpip.Route) {
+	if n.prefixC != nil {
+		n.prefixC <- ndpPrefixEvent{
+			nicID,
+			prefix,
+			true,
+		}
+	}
+
+	if !n.rememberPrefix {
+		return false, nil
+	}
+
+	rt := append([]tcpip.Route(nil), n.routeTable...)
+	rt = append(rt, tcpip.Route{
+		Destination: prefix,
+		NIC:         nicID,
+	})
+	n.routeTable = rt
+	return true, rt
+}
+
+// Implements stack.NDPDispatcher.OnOnLinkPrefixInvalidated.
+func (n *ndpDispatcher) OnOnLinkPrefixInvalidated(nicID tcpip.NICID, prefix tcpip.Subnet) []tcpip.Route {
+	if n.prefixC != nil {
+		n.prefixC <- ndpPrefixEvent{
+			nicID,
+			prefix,
+			false,
+		}
+	}
+
+	rt := make([]tcpip.Route, 0)
+	exclude := tcpip.Route{
+		Destination: prefix,
+		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
@@ -682,16 +739,19 @@ func TestSetNDPConfigurations(t *testing.T) {
 	}
 }
 
-// raBuf returns a valid NDP Router Advertisement.
+// raBufWithOpts returns a valid NDP Router Advertisement with options.
 //
-// Note, raBuf does not populate any of the RA fields other than the
+// Note, raBufWithOpts 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
+func raBufWithOpts(ip tcpip.Address, rl uint16, optSer header.NDPOptionsSerializer) tcpip.PacketBuffer {
+	icmpSize := header.ICMPv6HeaderSize + header.NDPRAMinimumSize + int(optSer.Length())
 	hdr := buffer.NewPrependable(header.IPv6MinimumSize + icmpSize)
 	pkt := header.ICMPv6(hdr.Prepend(icmpSize))
 	pkt.SetType(header.ICMPv6RouterAdvert)
 	pkt.SetCode(0)
+	ra := header.NDPRouterAdvert(pkt.NDPPayload())
+	opts := ra.Options()
+	opts.Serialize(optSer)
 	// Populate the Router Lifetime.
 	binary.BigEndian.PutUint16(pkt.NDPPayload()[2:], rl)
 	pkt.SetChecksum(header.ICMPv6Checksum(pkt, ip, header.IPv6AllNodesMulticastAddress, buffer.VectorisedView{}))
@@ -708,6 +768,35 @@ func raBuf(ip tcpip.Address, rl uint16) tcpip.PacketBuffer {
 	return tcpip.PacketBuffer{Data: hdr.View().ToVectorisedView()}
 }
 
+// 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 {
+	return raBufWithOpts(ip, rl, header.NDPOptionsSerializer{})
+}
+
+// raBufWithPI returns a valid NDP Router Advertisement with a single Prefix
+// Information option.
+//
+// Note, raBufWithPI does not populate any of the RA fields other than the
+// Router Lifetime.
+func raBufWithPI(ip tcpip.Address, rl uint16, prefix tcpip.AddressWithPrefix, onLink bool, vl uint32) tcpip.PacketBuffer {
+	flags := uint8(0)
+	if onLink {
+		flags |= 128
+	}
+
+	buf := [30]byte{}
+	buf[0] = uint8(prefix.PrefixLen)
+	buf[1] = flags
+	binary.BigEndian.PutUint32(buf[2:], vl)
+	copy(buf[14:], prefix.Address)
+	return raBufWithOpts(ip, rl, header.NDPOptionsSerializer{
+		header.NDPPrefixInformation(buf[:]),
+	})
+}
+
 // TestNoRouterDiscovery tests that router discovery will not be performed if
 // configured not to.
 func TestNoRouterDiscovery(t *testing.T) {
@@ -1011,3 +1100,440 @@ func TestRouterDiscoveryMaxRouters(t *testing.T) {
 		t.Fatalf("got GetRouteTable = %v, want = %v", got, expectedRt)
 	}
 }
+
+// TestNoPrefixDiscovery tests that prefix discovery will not be performed if
+// configured not to.
+func TestNoPrefixDiscovery(t *testing.T) {
+	prefix := tcpip.AddressWithPrefix{
+		Address:   tcpip.Address("\x01\x02\x03\x04\x05\x06\x07\x08\x00\x00\x00\x00\x00\x00\x00\x00"),
+		PrefixLen: 64,
+	}
+
+	// Being configured to discover prefixes 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
+	// prefix 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), DiscoverOnLinkPrefixes(%t), Forwarding(%t)", handle, discover, forwarding), func(t *testing.T) {
+			ndpDisp := ndpDispatcher{
+				prefixC: make(chan ndpPrefixEvent, 10),
+			}
+			e := channel.New(10, 1280, linkAddr1)
+			s := stack.New(stack.Options{
+				NetworkProtocols: []stack.NetworkProtocol{ipv6.NewProtocol()},
+				NDPConfigs: stack.NDPConfigurations{
+					HandleRAs:              handle,
+					DiscoverOnLinkPrefixes: discover,
+				},
+				NDPDisp: &ndpDisp,
+			})
+			s.SetForwarding(forwarding)
+
+			if err := s.CreateNIC(1, e); err != nil {
+				t.Fatalf("CreateNIC(1) = %s", err)
+			}
+
+			// Rx an RA with prefix with non-zero lifetime.
+			e.InjectInbound(header.IPv6ProtocolNumber, raBufWithPI(llAddr2, 0, prefix, true, 10))
+
+			select {
+			case <-ndpDisp.prefixC:
+				t.Fatal("unexpectedly discovered a prefix when configured not to")
+			case <-time.After(defaultTimeout):
+			}
+		})
+	}
+}
+
+// TestPrefixDiscoveryDispatcherNoRemember tests that the stack does not
+// remember a discovered on-link prefix when the dispatcher asks it not to.
+func TestPrefixDiscoveryDispatcherNoRemember(t *testing.T) {
+	prefix := tcpip.AddressWithPrefix{
+		Address:   tcpip.Address("\x01\x02\x03\x04\x05\x06\x07\x08\x00\x00\x00\x00\x00\x00\x00\x00"),
+		PrefixLen: 64,
+	}
+	subnet := prefix.Subnet()
+
+	ndpDisp := ndpDispatcher{
+		prefixC: make(chan ndpPrefixEvent, 10),
+	}
+	e := channel.New(10, 1280, linkAddr1)
+	s := stack.New(stack.Options{
+		NetworkProtocols: []stack.NetworkProtocol{ipv6.NewProtocol()},
+		NDPConfigs: stack.NDPConfigurations{
+			HandleRAs:              true,
+			DiscoverDefaultRouters: false,
+			DiscoverOnLinkPrefixes: 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 prefix with a short lifetime.
+	const lifetime = 1
+	e.InjectInbound(header.IPv6ProtocolNumber, raBufWithPI(llAddr2, 0, prefix, true, lifetime))
+	select {
+	case r := <-ndpDisp.prefixC:
+		if r.nicID != 1 {
+			t.Fatalf("got r.nicID = %d, want = 1", r.nicID)
+		}
+		if r.prefix != subnet {
+			t.Fatalf("got r.prefix = %s, want = %s", r.prefix, subnet)
+		}
+		if !r.discovered {
+			t.Fatal("got r.discovered = false, want = true")
+		}
+	case <-time.After(defaultTimeout):
+		t.Fatal("timeout waiting for prefix 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 some buffer to
+	// make sure we do not actually receive any invalidation events as
+	// we should not have remembered the prefix in the first place.
+	select {
+	case <-ndpDisp.prefixC:
+		t.Fatal("should not have received any prefix 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 TestPrefixDiscovery(t *testing.T) {
+	prefix1 := tcpip.AddressWithPrefix{
+		Address:   tcpip.Address("\x01\x02\x03\x04\x05\x06\x07\x08\x00\x00\x00\x00\x00\x00\x00\x00"),
+		PrefixLen: 64,
+	}
+	prefix2 := tcpip.AddressWithPrefix{
+		Address:   tcpip.Address("\x01\x02\x03\x04\x05\x06\x07\x09\x00\x00\x00\x00\x00\x00\x00\x00"),
+		PrefixLen: 64,
+	}
+	prefix3 := tcpip.AddressWithPrefix{
+		Address:   tcpip.Address("\x01\x02\x03\x04\x05\x06\x07\x09\x0a\x00\x00\x00\x00\x00\x00\x00"),
+		PrefixLen: 72,
+	}
+	subnet1 := prefix1.Subnet()
+	subnet2 := prefix2.Subnet()
+	subnet3 := prefix3.Subnet()
+
+	ndpDisp := ndpDispatcher{
+		prefixC:        make(chan ndpPrefixEvent, 10),
+		rememberPrefix: true,
+	}
+	e := channel.New(10, 1280, linkAddr1)
+	s := stack.New(stack.Options{
+		NetworkProtocols: []stack.NetworkProtocol{ipv6.NewProtocol()},
+		NDPConfigs: stack.NDPConfigurations{
+			HandleRAs:              true,
+			DiscoverOnLinkPrefixes: true,
+		},
+		NDPDisp: &ndpDisp,
+	})
+
+	waitForEvent := func(subnet tcpip.Subnet, discovered bool, timeout time.Duration) {
+		t.Helper()
+
+		select {
+		case r := <-ndpDisp.prefixC:
+			if r.nicID != 1 {
+				t.Fatalf("got r.nicID = %d, want = 1", r.nicID)
+			}
+			if r.prefix != subnet {
+				t.Fatalf("got r.prefix = %s, want = %s", r.prefix, subnet)
+			}
+			if r.discovered != discovered {
+				t.Fatalf("got r.discovered = %t, want = %t", r.discovered, discovered)
+			}
+		case <-time.After(timeout):
+			t.Fatal("timeout waiting for prefix discovery event")
+		}
+	}
+
+	if err := s.CreateNIC(1, e); err != nil {
+		t.Fatalf("CreateNIC(1) = %s", err)
+	}
+
+	// Receive an RA with prefix1 in an NDP Prefix Information option (PI)
+	// with zero valid lifetime.
+	e.InjectInbound(header.IPv6ProtocolNumber, raBufWithPI(llAddr2, 0, prefix1, true, 0))
+	select {
+	case <-ndpDisp.prefixC:
+		t.Fatal("unexpectedly discovered a prefix with 0 lifetime")
+	case <-time.After(defaultTimeout):
+	}
+
+	// Receive an RA with prefix1 in an NDP Prefix Information option (PI)
+	// with non-zero lifetime.
+	e.InjectInbound(header.IPv6ProtocolNumber, raBufWithPI(llAddr2, 0, prefix1, true, 100))
+	waitForEvent(subnet1, true, defaultTimeout)
+
+	// Should have added a device route for subnet1 through the nic.
+	if got, want := s.GetRouteTable(), []tcpip.Route{{subnet1, tcpip.Address([]byte(nil)), 1}}; !cmp.Equal(got, want) {
+		t.Fatalf("got GetRouteTable = %v, want = %v", got, want)
+	}
+
+	// Receive an RA with prefix2 in a PI.
+	e.InjectInbound(header.IPv6ProtocolNumber, raBufWithPI(llAddr2, 0, prefix2, true, 100))
+	waitForEvent(subnet2, true, defaultTimeout)
+
+	// Should have added a device route for subnet2 through the nic.
+	if got, want := s.GetRouteTable(), []tcpip.Route{{subnet1, tcpip.Address([]byte(nil)), 1}, {subnet2, tcpip.Address([]byte(nil)), 1}}; !cmp.Equal(got, want) {
+		t.Fatalf("got GetRouteTable = %v, want = %v", got, want)
+	}
+
+	// Receive an RA with prefix3 in a PI.
+	e.InjectInbound(header.IPv6ProtocolNumber, raBufWithPI(llAddr2, 0, prefix3, true, 100))
+	waitForEvent(subnet3, true, defaultTimeout)
+
+	// Should have added a device route for subnet3 through the nic.
+	if got, want := s.GetRouteTable(), []tcpip.Route{{subnet1, tcpip.Address([]byte(nil)), 1}, {subnet2, tcpip.Address([]byte(nil)), 1}, {subnet3, tcpip.Address([]byte(nil)), 1}}; !cmp.Equal(got, want) {
+		t.Fatalf("got GetRouteTable = %v, want = %v", got, want)
+	}
+
+	// Receive an RA with prefix1 in a PI with lifetime = 0.
+	e.InjectInbound(header.IPv6ProtocolNumber, raBufWithPI(llAddr2, 0, prefix1, true, 0))
+	waitForEvent(subnet1, false, defaultTimeout)
+
+	// Should have removed the device route for subnet1 through the nic.
+	if got, want := s.GetRouteTable(), []tcpip.Route{{subnet2, tcpip.Address([]byte(nil)), 1}, {subnet3, tcpip.Address([]byte(nil)), 1}}; !cmp.Equal(got, want) {
+		t.Fatalf("got GetRouteTable = %v, want = %v", got, want)
+	}
+
+	// Receive an RA with prefix2 in a PI with lesser lifetime.
+	lifetime := uint32(2)
+	e.InjectInbound(header.IPv6ProtocolNumber, raBufWithPI(llAddr2, 0, prefix2, true, lifetime))
+	select {
+	case <-ndpDisp.prefixC:
+		t.Fatal("unexpectedly received prefix event when updating lifetime")
+	case <-time.After(defaultTimeout):
+	}
+
+	// Should not have updated route table.
+	if got, want := s.GetRouteTable(), []tcpip.Route{{subnet2, tcpip.Address([]byte(nil)), 1}, {subnet3, tcpip.Address([]byte(nil)), 1}}; !cmp.Equal(got, want) {
+		t.Fatalf("got GetRouteTable = %v, want = %v", got, want)
+	}
+
+	// Wait for prefix2's most recent invalidation timer plus some buffer to
+	// expire.
+	waitForEvent(subnet2, false, time.Duration(lifetime)*time.Second+defaultTimeout)
+
+	// Should have removed the device route for subnet2 through the nic.
+	if got, want := s.GetRouteTable(), []tcpip.Route{{subnet3, tcpip.Address([]byte(nil)), 1}}; !cmp.Equal(got, want) {
+		t.Fatalf("got GetRouteTable = %v, want = %v", got, want)
+	}
+
+	// Receive RA to invalidate prefix3.
+	e.InjectInbound(header.IPv6ProtocolNumber, raBufWithPI(llAddr2, 0, prefix3, true, 0))
+	waitForEvent(subnet3, false, defaultTimeout)
+
+	// Should not have any routes.
+	if got := len(s.GetRouteTable()); got != 0 {
+		t.Fatalf("got len(s.GetRouteTable()) = %d, want = 0", got)
+	}
+}
+
+func TestPrefixDiscoveryWithInfiniteLifetime(t *testing.T) {
+	// Update the infinite lifetime value to a smaller value so we can test
+	// that when we receive a PI with such a lifetime value, we do not
+	// invalidate the prefix.
+	const testInfiniteLifetimeSeconds = 2
+	const testInfiniteLifetime = testInfiniteLifetimeSeconds * time.Second
+	saved := header.NDPPrefixInformationInfiniteLifetime
+	header.NDPPrefixInformationInfiniteLifetime = testInfiniteLifetime
+	defer func() {
+		header.NDPPrefixInformationInfiniteLifetime = saved
+	}()
+
+	prefix := tcpip.AddressWithPrefix{
+		Address:   tcpip.Address("\x01\x02\x03\x04\x05\x06\x07\x08\x00\x00\x00\x00\x00\x00\x00\x00"),
+		PrefixLen: 64,
+	}
+	subnet := prefix.Subnet()
+
+	ndpDisp := ndpDispatcher{
+		prefixC:        make(chan ndpPrefixEvent, 10),
+		rememberPrefix: true,
+	}
+	e := channel.New(10, 1280, linkAddr1)
+	s := stack.New(stack.Options{
+		NetworkProtocols: []stack.NetworkProtocol{ipv6.NewProtocol()},
+		NDPConfigs: stack.NDPConfigurations{
+			HandleRAs:              true,
+			DiscoverOnLinkPrefixes: true,
+		},
+		NDPDisp: &ndpDisp,
+	})
+
+	waitForEvent := func(discovered bool, timeout time.Duration) {
+		t.Helper()
+
+		select {
+		case r := <-ndpDisp.prefixC:
+			if r.nicID != 1 {
+				t.Errorf("got r.nicID = %d, want = 1", r.nicID)
+			}
+			if r.prefix != subnet {
+				t.Errorf("got r.prefix = %s, want = %s", r.prefix, subnet)
+			}
+			if r.discovered != discovered {
+				t.Errorf("got r.discovered = %t, want = %t", r.discovered, discovered)
+			}
+		case <-time.After(timeout):
+			t.Fatal("timeout waiting for prefix discovery event")
+		}
+	}
+
+	if err := s.CreateNIC(1, e); err != nil {
+		t.Fatalf("CreateNIC(1) = %s", err)
+	}
+
+	// Receive an RA with prefix in an NDP Prefix Information option (PI)
+	// with infinite valid lifetime which should not get invalidated.
+	e.InjectInbound(header.IPv6ProtocolNumber, raBufWithPI(llAddr2, 0, prefix, true, testInfiniteLifetimeSeconds))
+	waitForEvent(true, defaultTimeout)
+	select {
+	case <-ndpDisp.prefixC:
+		t.Fatal("unexpectedly invalidated a prefix with infinite lifetime")
+	case <-time.After(testInfiniteLifetime + defaultTimeout):
+	}
+
+	// Receive an RA with finite lifetime.
+	// The prefix should get invalidated after 1s.
+	e.InjectInbound(header.IPv6ProtocolNumber, raBufWithPI(llAddr2, 0, prefix, true, testInfiniteLifetimeSeconds-1))
+	waitForEvent(false, testInfiniteLifetime)
+
+	// Receive an RA with finite lifetime.
+	e.InjectInbound(header.IPv6ProtocolNumber, raBufWithPI(llAddr2, 0, prefix, true, testInfiniteLifetimeSeconds-1))
+	waitForEvent(true, defaultTimeout)
+
+	// Receive an RA with prefix with an infinite lifetime.
+	// The prefix should not be invalidated.
+	e.InjectInbound(header.IPv6ProtocolNumber, raBufWithPI(llAddr2, 0, prefix, true, testInfiniteLifetimeSeconds))
+	select {
+	case <-ndpDisp.prefixC:
+		t.Fatal("unexpectedly invalidated a prefix with infinite lifetime")
+	case <-time.After(testInfiniteLifetime + defaultTimeout):
+	}
+
+	// Receive an RA with a prefix with a lifetime value greater than the
+	// set infinite lifetime value.
+	e.InjectInbound(header.IPv6ProtocolNumber, raBufWithPI(llAddr2, 0, prefix, true, testInfiniteLifetimeSeconds+1))
+	select {
+	case <-ndpDisp.prefixC:
+		t.Fatal("unexpectedly invalidated a prefix with infinite lifetime")
+	case <-time.After((testInfiniteLifetimeSeconds+1)*time.Second + defaultTimeout):
+	}
+
+	// Receive an RA with 0 lifetime.
+	// The prefix should get invalidated.
+	e.InjectInbound(header.IPv6ProtocolNumber, raBufWithPI(llAddr2, 0, prefix, true, 0))
+	waitForEvent(false, defaultTimeout)
+}
+
+// TestPrefixDiscoveryMaxRouters tests that only
+// stack.MaxDiscoveredOnLinkPrefixes discovered on-link prefixes are remembered.
+func TestPrefixDiscoveryMaxOnLinkPrefixes(t *testing.T) {
+	ndpDisp := ndpDispatcher{
+		prefixC:        make(chan ndpPrefixEvent, stack.MaxDiscoveredOnLinkPrefixes+3),
+		rememberPrefix: true,
+	}
+	e := channel.New(10, 1280, linkAddr1)
+	s := stack.New(stack.Options{
+		NetworkProtocols: []stack.NetworkProtocol{ipv6.NewProtocol()},
+		NDPConfigs: stack.NDPConfigurations{
+			HandleRAs:              true,
+			DiscoverDefaultRouters: false,
+			DiscoverOnLinkPrefixes: true,
+		},
+		NDPDisp: &ndpDisp,
+	})
+
+	if err := s.CreateNIC(1, e); err != nil {
+		t.Fatalf("CreateNIC(1) = %s", err)
+	}
+
+	optSer := make(header.NDPOptionsSerializer, stack.MaxDiscoveredOnLinkPrefixes+2)
+	expectedRt := [stack.MaxDiscoveredOnLinkPrefixes]tcpip.Route{}
+	prefixes := [stack.MaxDiscoveredOnLinkPrefixes + 2]tcpip.Subnet{}
+
+	// Receive an RA with 2 more than the max number of discovered on-link
+	// prefixes.
+	for i := 0; i < stack.MaxDiscoveredOnLinkPrefixes+2; i++ {
+		prefixAddr := [16]byte{1, 2, 3, 4, 5, 6, 7, 8, 0, 0, 0, 0, 0, 0, 0, 0}
+		prefixAddr[7] = byte(i)
+		prefix := tcpip.AddressWithPrefix{
+			Address:   tcpip.Address(prefixAddr[:]),
+			PrefixLen: 64,
+		}
+		prefixes[i] = prefix.Subnet()
+		buf := [30]byte{}
+		buf[0] = uint8(prefix.PrefixLen)
+		buf[1] = 128
+		binary.BigEndian.PutUint32(buf[2:], 10)
+		copy(buf[14:], prefix.Address)
+
+		optSer[i] = header.NDPPrefixInformation(buf[:])
+
+		if i < stack.MaxDiscoveredOnLinkPrefixes {
+			expectedRt[i] = tcpip.Route{prefixes[i], tcpip.Address([]byte(nil)), 1}
+		}
+	}
+
+	e.InjectInbound(header.IPv6ProtocolNumber, raBufWithOpts(llAddr1, 0, optSer))
+	for i := 0; i < stack.MaxDiscoveredOnLinkPrefixes+2; i++ {
+		if i < stack.MaxDiscoveredOnLinkPrefixes {
+			select {
+			case r := <-ndpDisp.prefixC:
+				if r.nicID != 1 {
+					t.Fatalf("got r.nicID = %d, want = 1", r.nicID)
+				}
+				if r.prefix != prefixes[i] {
+					t.Fatalf("got r.prefix = %s, want = %s", r.prefix, prefixes[i])
+				}
+				if !r.discovered {
+					t.Fatal("got r.discovered = false, want = true")
+				}
+			case <-time.After(defaultTimeout):
+				t.Fatal("timeout waiting for prefix discovery event")
+			}
+		} else {
+			select {
+			case <-ndpDisp.prefixC:
+				t.Fatal("should not have discovered a new prefix after we already discovered the max number of prefixes")
+			case <-time.After(defaultTimeout):
+			}
+		}
+	}
+
+	// Should only have device routes for the first
+	// stack.MaxDiscoveredOnLinkPrefixes discovered on-link prefixes.
+	if got := s.GetRouteTable(); !cmp.Equal(got, expectedRt[:]) {
+		t.Fatalf("got GetRouteTable = %v, want = %v", got, expectedRt)
+	}
+}
diff --git a/pkg/tcpip/stack/nic.go b/pkg/tcpip/stack/nic.go
index 28a28ae6e..9ed9e1e7c 100644
--- a/pkg/tcpip/stack/nic.go
+++ b/pkg/tcpip/stack/nic.go
@@ -118,6 +118,7 @@ func newNIC(stack *Stack, id tcpip.NICID, name string, ep LinkEndpoint, loopback
 			configs:        stack.ndpConfigs,
 			dad:            make(map[tcpip.Address]dadState),
 			defaultRouters: make(map[tcpip.Address]defaultRouterState),
+			onLinkPrefixes: make(map[tcpip.Subnet]onLinkPrefixState),
 		},
 	}
 	nic.ndp.nic = nic