Implement neighbor unreachability detection for ARP and NDP.

This change implements the Neighbor Unreachability Detection (NUD) state
machine, as per RFC 4861 [1]. The state machine operates on a single neighbor
in the local network. This requires the state machine to be implemented on each
entry of the neighbor table.

This change also adds, but does not expose, several APIs. The first API is for
performing basic operations on the neighbor table:
 - Create a static entry
 - List all entries
 - Delete all entries
 - Remove an entry by address

The second API is used for changing the NUD protocol constants on a per-NIC
basis to allow Neighbor Discovery to operate over links with widely varying
performance characteristics. See [RFC 4861 Section 10][2] for the list of
constants.

Finally, the last API is for allowing users to subscribe to NUD state changes.
See [RFC 4861 Appendix C][3] for the list of edges.

[1]: https://tools.ietf.org/html/rfc4861
[2]: https://tools.ietf.org/html/rfc4861#section-10
[3]: https://tools.ietf.org/html/rfc4861#appendix-C

Tests:
 pkg/tcpip/stack:stack_test
 - TestNeighborCacheAddStaticEntryThenOverflow
 - TestNeighborCacheClear
 - TestNeighborCacheClearThenOverflow
 - TestNeighborCacheConcurrent
 - TestNeighborCacheDuplicateStaticEntryWithDifferentLinkAddress
 - TestNeighborCacheDuplicateStaticEntryWithSameLinkAddress
 - TestNeighborCacheEntry
 - TestNeighborCacheEntryNoLinkAddress
 - TestNeighborCacheGetConfig
 - TestNeighborCacheKeepFrequentlyUsed
 - TestNeighborCacheNotifiesWaker
 - TestNeighborCacheOverflow
 - TestNeighborCacheOverwriteWithStaticEntryThenOverflow
 - TestNeighborCacheRemoveEntry
 - TestNeighborCacheRemoveEntryThenOverflow
 - TestNeighborCacheRemoveStaticEntry
 - TestNeighborCacheRemoveStaticEntryThenOverflow
 - TestNeighborCacheRemoveWaker
 - TestNeighborCacheReplace
 - TestNeighborCacheResolutionFailed
 - TestNeighborCacheResolutionTimeout
 - TestNeighborCacheSetConfig
 - TestNeighborCacheStaticResolution
 - TestEntryAddsAndClearsWakers
 - TestEntryDelayToProbe
 - TestEntryDelayToReachableWhenSolicitedOverrideConfirmation
 - TestEntryDelayToReachableWhenUpperLevelConfirmation
 - TestEntryDelayToStaleWhenConfirmationWithDifferentAddress
 - TestEntryDelayToStaleWhenProbeWithDifferentAddress
 - TestEntryFailedGetsDeleted
 - TestEntryIncompleteToFailed
 - TestEntryIncompleteToIncompleteDoesNotChangeUpdatedAt
 - TestEntryIncompleteToReachable
 - TestEntryIncompleteToReachableWithRouterFlag
 - TestEntryIncompleteToStale
 - TestEntryInitiallyUnknown
 - TestEntryProbeToFailed
 - TestEntryProbeToReachableWhenSolicitedConfirmationWithSameAddress
 - TestEntryProbeToReachableWhenSolicitedOverrideConfirmation
 - TestEntryProbeToStaleWhenConfirmationWithDifferentAddress
 - TestEntryProbeToStaleWhenProbeWithDifferentAddress
 - TestEntryReachableToStaleWhenConfirmationWithDifferentAddress
 - TestEntryReachableToStaleWhenConfirmationWithDifferentAddressAndOverride
 - TestEntryReachableToStaleWhenProbeWithDifferentAddress
 - TestEntryReachableToStaleWhenTimeout
 - TestEntryStaleToDelay
 - TestEntryStaleToReachableWhenSolicitedOverrideConfirmation
 - TestEntryStaleToStaleWhenOverrideConfirmation
 - TestEntryStaleToStaleWhenProbeUpdateAddress
 - TestEntryStaysDelayWhenOverrideConfirmationWithSameAddress
 - TestEntryStaysProbeWhenOverrideConfirmationWithSameAddress
 - TestEntryStaysReachableWhenConfirmationWithRouterFlag
 - TestEntryStaysReachableWhenProbeWithSameAddress
 - TestEntryStaysStaleWhenProbeWithSameAddress
 - TestEntryUnknownToIncomplete
 - TestEntryUnknownToStale
 - TestEntryUnknownToUnknownWhenConfirmationWithUnknownAddress

 pkg/tcpip/stack:stack_x_test
 - TestDefaultNUDConfigurations
 - TestNUDConfigurationFailsForNotSupported
 - TestNUDConfigurationsBaseReachableTime
 - TestNUDConfigurationsDelayFirstProbeTime
 - TestNUDConfigurationsMaxMulticastProbes
 - TestNUDConfigurationsMaxRandomFactor
 - TestNUDConfigurationsMaxUnicastProbes
 - TestNUDConfigurationsMinRandomFactor
 - TestNUDConfigurationsRetransmitTimer
 - TestNUDConfigurationsUnreachableTime
 - TestNUDStateReachableTime
 - TestNUDStateRecomputeReachableTime
 - TestSetNUDConfigurationFailsForBadNICID
 - TestSetNUDConfigurationFailsForNotSupported

[1]: https://tools.ietf.org/html/rfc4861
[2]: https://tools.ietf.org/html/rfc4861#section-10
[3]: https://tools.ietf.org/html/rfc4861#appendix-C

Updates #1889
Updates #1894
Updates #1895
Updates #1947
Updates #1948
Updates #1949
Updates #1950

PiperOrigin-RevId: 324070795

1 files changed, 33 insertions, 0 deletions

diff --git a/pkg/tcpip/stack/nic.go b/pkg/tcpip/stack/nic.go
index 9256d4d43..f21066fce 100644
--- a/pkg/tcpip/stack/nic.go
+++ b/pkg/tcpip/stack/nic.go
@@ -16,6 +16,7 @@ package stack
 
 import (
 	"fmt"
+	"math/rand"
 	"reflect"
 	"sort"
 	"strings"
@@ -45,6 +46,7 @@ type NIC struct {
 	context NICContext
 
 	stats NICStats
+	neigh *neighborCache
 
 	mu struct {
 		sync.RWMutex
@@ -141,6 +143,16 @@ func newNIC(stack *Stack, id tcpip.NICID, name string, ep LinkEndpoint, ctx NICC
 		nic.mu.packetEPs[netProto.Number()] = []PacketEndpoint{}
 	}
 
+	// Check for Neighbor Unreachability Detection support.
+	if ep.Capabilities()&CapabilityResolutionRequired != 0 && len(stack.linkAddrResolvers) != 0 {
+		rng := rand.New(rand.NewSource(stack.clock.NowNanoseconds()))
+		nic.neigh = &neighborCache{
+			nic:   nic,
+			state: NewNUDState(stack.nudConfigs, rng),
+			cache: make(map[tcpip.Address]*neighborEntry, neighborCacheSize),
+		}
+	}
+
 	nic.linkEP.Attach(nic)
 
 	return nic
@@ -1540,6 +1552,27 @@ func (n *NIC) setNDPConfigs(c NDPConfigurations) {
 	n.mu.Unlock()
 }
 
+// NUDConfigs gets the NUD configurations for n.
+func (n *NIC) NUDConfigs() (NUDConfigurations, *tcpip.Error) {
+	if n.neigh == nil {
+		return NUDConfigurations{}, tcpip.ErrNotSupported
+	}
+	return n.neigh.config(), nil
+}
+
+// setNUDConfigs sets the NUD configurations for n.
+//
+// Note, if c contains invalid NUD configuration values, it will be fixed to
+// use default values for the erroneous values.
+func (n *NIC) setNUDConfigs(c NUDConfigurations) *tcpip.Error {
+	if n.neigh == nil {
+		return tcpip.ErrNotSupported
+	}
+	c.resetInvalidFields()
+	n.neigh.setConfig(c)
+	return nil
+}
+
 // handleNDPRA handles an NDP Router Advertisement message that arrived on n.
 func (n *NIC) handleNDPRA(ip tcpip.Address, ra header.NDPRouterAdvert) {
 	n.mu.Lock()