1 files changed, 121 insertions, 132 deletions

diff --git a/pkg/tcpip/stack/linkaddrcache.go b/pkg/tcpip/stack/linkaddrcache.go
index 77bb0ccb9..267df60d1 100644
--- a/pkg/tcpip/stack/linkaddrcache.go
+++ b/pkg/tcpip/stack/linkaddrcache.go
@@ -42,10 +42,11 @@ type linkAddrCache struct {
 	// resolved before failing.
 	resolutionAttempts int
 
-	mu      sync.Mutex
-	cache   map[tcpip.FullAddress]*linkAddrEntry
-	next    int // array index of next available entry
-	entries [linkAddrCacheSize]linkAddrEntry
+	cache struct {
+		sync.Mutex
+		table map[tcpip.FullAddress]*linkAddrEntry
+		lru   linkAddrEntryList
+	}
 }
 
 // entryState controls the state of a single entry in the cache.
@@ -60,9 +61,6 @@ const (
 	// failed means that address resolution timed out and the address
 	// could not be resolved.
 	failed
-	// expired means that the cache entry has expired and the address must be
-	// resolved again.
-	expired
 )
 
 // String implements Stringer.
@@ -74,8 +72,6 @@ func (s entryState) String() string {
 		return "ready"
 	case failed:
 		return "failed"
-	case expired:
-		return "expired"
 	default:
 		return fmt.Sprintf("unknown(%d)", s)
 	}
@@ -84,64 +80,46 @@ func (s entryState) String() string {
 // A linkAddrEntry is an entry in the linkAddrCache.
 // This struct is thread-compatible.
 type linkAddrEntry struct {
+	linkAddrEntryEntry
+
 	addr       tcpip.FullAddress
 	linkAddr   tcpip.LinkAddress
 	expiration time.Time
 	s          entryState
 
 	// wakers is a set of waiters for address resolution result. Anytime
-	// state transitions out of 'incomplete' these waiters are notified.
+	// state transitions out of incomplete these waiters are notified.
 	wakers map[*sleep.Waker]struct{}
 
+	// done is used to allow callers to wait on address resolution. It is nil iff
+	// s is incomplete and resolution is not yet in progress.
 	done chan struct{}
 }
 
-func (e *linkAddrEntry) state() entryState {
-	if e.s != expired && time.Now().After(e.expiration) {
-		// Force the transition to ensure waiters are notified.
-		e.changeState(expired)
-	}
-	return e.s
-}
-
-func (e *linkAddrEntry) changeState(ns entryState) {
-	if e.s == ns {
-		return
-	}
-
-	// Validate state transition.
-	switch e.s {
-	case incomplete:
-		// All transitions are valid.
-	case ready, failed:
-		if ns != expired {
-			panic(fmt.Sprintf("invalid state transition from %s to %s", e.s, ns))
-		}
-	case expired:
-		// Terminal state.
-		panic(fmt.Sprintf("invalid state transition from %s to %s", e.s, ns))
-	default:
-		panic(fmt.Sprintf("invalid state: %s", e.s))
-	}
-
+// changeState sets the entry's state to ns, notifying any waiters.
+//
+// The entry's expiration is bumped up to the greater of itself and the passed
+// expiration; the zero value indicates immediate expiration, and is set
+// unconditionally - this is an implementation detail that allows for entries
+// to be reused.
+func (e *linkAddrEntry) changeState(ns entryState, expiration time.Time) {
 	// Notify whoever is waiting on address resolution when transitioning
-	// out of 'incomplete'.
-	if e.s == incomplete {
+	// out of incomplete.
+	if e.s == incomplete && ns != incomplete {
 		for w := range e.wakers {
 			w.Assert()
 		}
 		e.wakers = nil
-		if e.done != nil {
-			close(e.done)
+		if ch := e.done; ch != nil {
+			close(ch)
 		}
+		e.done = nil
 	}
-	e.s = ns
-}
 
-func (e *linkAddrEntry) maybeAddWaker(w *sleep.Waker) {
-	if w != nil {
-		e.wakers[w] = struct{}{}
+	if expiration.IsZero() || expiration.After(e.expiration) {
+		e.expiration = expiration
 	}
+	e.s = ns
 }
 
 func (e *linkAddrEntry) removeWaker(w *sleep.Waker) {
@@ -150,53 +128,54 @@ func (e *linkAddrEntry) removeWaker(w *sleep.Waker) {
 
 // add adds a k -> v mapping to the cache.
 func (c *linkAddrCache) add(k tcpip.FullAddress, v tcpip.LinkAddress) {
-	c.mu.Lock()
-	defer c.mu.Unlock()
-
-	entry, ok := c.cache[k]
-	if ok {
-		s := entry.state()
-		if s != expired && entry.linkAddr == v {
-			// Disregard repeated calls.
-			return
-		}
-		// Check if entry is waiting for address resolution.
-		if s == incomplete {
-			entry.linkAddr = v
-		} else {
-			// Otherwise create a new entry to replace it.
-			entry = c.makeAndAddEntry(k, v)
-		}
-	} else {
-		entry = c.makeAndAddEntry(k, v)
-	}
+	// Calculate expiration time before acquiring the lock, since expiration is
+	// relative to the time when information was learned, rather than when it
+	// happened to be inserted into the cache.
+	expiration := time.Now().Add(c.ageLimit)
 
-	entry.changeState(ready)
+	c.cache.Lock()
+	entry := c.getOrCreateEntryLocked(k)
+	entry.linkAddr = v
+
+	entry.changeState(ready, expiration)
+	c.cache.Unlock()
 }
 
-// makeAndAddEntry is a helper function to create and add a new
-// entry to the cache map and evict older entry as needed.
-func (c *linkAddrCache) makeAndAddEntry(k tcpip.FullAddress, v tcpip.LinkAddress) *linkAddrEntry {
-	// Take over the next entry.
-	entry := &c.entries[c.next]
-	if c.cache[entry.addr] == entry {
-		delete(c.cache, entry.addr)
+// getOrCreateEntryLocked retrieves a cache entry associated with k. The
+// returned entry is always refreshed in the cache (it is reachable via the
+// map, and its place is bumped in LRU).
+//
+// If a matching entry exists in the cache, it is returned. If no matching
+// entry exists and the cache is full, an existing entry is evicted via LRU,
+// reset to state incomplete, and returned. If no matching entry exists and the
+// cache is not full, a new entry with state incomplete is allocated and
+// returned.
+func (c *linkAddrCache) getOrCreateEntryLocked(k tcpip.FullAddress) *linkAddrEntry {
+	if entry, ok := c.cache.table[k]; ok {
+		c.cache.lru.Remove(entry)
+		c.cache.lru.PushFront(entry)
+		return entry
 	}
+	var entry *linkAddrEntry
+	if len(c.cache.table) == linkAddrCacheSize {
+		entry = c.cache.lru.Back()
 
-	// Mark the soon-to-be-replaced entry as expired, just in case there is
-	// someone waiting for address resolution on it.
-	entry.changeState(expired)
+		delete(c.cache.table, entry.addr)
+		c.cache.lru.Remove(entry)
 
-	*entry = linkAddrEntry{
-		addr:       k,
-		linkAddr:   v,
-		expiration: time.Now().Add(c.ageLimit),
-		wakers:     make(map[*sleep.Waker]struct{}),
-		done:       make(chan struct{}),
+		// Wake waiters and mark the soon-to-be-reused entry as expired. Note
+		// that the state passed doesn't matter when the zero time is passed.
+		entry.changeState(failed, time.Time{})
+	} else {
+		entry = new(linkAddrEntry)
 	}
 
-	c.cache[k] = entry
-	c.next = (c.next + 1) % len(c.entries)
+	*entry = linkAddrEntry{
+		addr: k,
+		s:    incomplete,
+	}
+	c.cache.table[k] = entry
+	c.cache.lru.PushFront(entry)
 	return entry
 }
 
@@ -208,43 +187,55 @@ func (c *linkAddrCache) get(k tcpip.FullAddress, linkRes LinkAddressResolver, lo
 		}
 	}
 
-	c.mu.Lock()
-	defer c.mu.Unlock()
-	if entry, ok := c.cache[k]; ok {
-		switch s := entry.state(); s {
-		case expired:
-		case ready:
-			return entry.linkAddr, nil, nil
-		case failed:
-			return "", nil, tcpip.ErrNoLinkAddress
-		case incomplete:
-			// Address resolution is still in progress.
-			entry.maybeAddWaker(waker)
-			return "", entry.done, tcpip.ErrWouldBlock
-		default:
-			panic(fmt.Sprintf("invalid cache entry state: %s", s))
+	c.cache.Lock()
+	defer c.cache.Unlock()
+	entry := c.getOrCreateEntryLocked(k)
+	switch s := entry.s; s {
+	case ready, failed:
+		if !time.Now().After(entry.expiration) {
+			// Not expired.
+			switch s {
+			case ready:
+				return entry.linkAddr, nil, nil
+			case failed:
+				return entry.linkAddr, nil, tcpip.ErrNoLinkAddress
+			default:
+				panic(fmt.Sprintf("invalid cache entry state: %s", s))
+			}
 		}
-	}
 
-	if linkRes == nil {
-		return "", nil, tcpip.ErrNoLinkAddress
-	}
+		entry.changeState(incomplete, time.Time{})
+		fallthrough
+	case incomplete:
+		if waker != nil {
+			if entry.wakers == nil {
+				entry.wakers = make(map[*sleep.Waker]struct{})
+			}
+			entry.wakers[waker] = struct{}{}
+		}
 
-	// Add 'incomplete' entry in the cache to mark that resolution is in progress.
-	e := c.makeAndAddEntry(k, "")
-	e.maybeAddWaker(waker)
+		if entry.done == nil {
+			// Address resolution needs to be initiated.
+			if linkRes == nil {
+				return entry.linkAddr, nil, tcpip.ErrNoLinkAddress
+			}
 
-	go c.startAddressResolution(k, linkRes, localAddr, linkEP, e.done) // S/R-SAFE: link non-savable; wakers dropped synchronously.
+			entry.done = make(chan struct{})
+			go c.startAddressResolution(k, linkRes, localAddr, linkEP, entry.done) // S/R-SAFE: link non-savable; wakers dropped synchronously.
+		}
 
-	return "", e.done, tcpip.ErrWouldBlock
+		return entry.linkAddr, entry.done, tcpip.ErrWouldBlock
+	default:
+		panic(fmt.Sprintf("invalid cache entry state: %s", s))
+	}
 }
 
 // removeWaker removes a waker previously added through get().
 func (c *linkAddrCache) removeWaker(k tcpip.FullAddress, waker *sleep.Waker) {
-	c.mu.Lock()
-	defer c.mu.Unlock()
+	c.cache.Lock()
+	defer c.cache.Unlock()
 
-	if entry, ok := c.cache[k]; ok {
+	if entry, ok := c.cache.table[k]; ok {
 		entry.removeWaker(waker)
 	}
 }
@@ -256,8 +247,8 @@ func (c *linkAddrCache) startAddressResolution(k tcpip.FullAddress, linkRes Link
 		linkRes.LinkAddressRequest(k.Addr, localAddr, linkEP)
 
 		select {
-		case <-time.After(c.resolutionTimeout):
-			if stop := c.checkLinkRequest(k, i); stop {
+		case now := <-time.After(c.resolutionTimeout):
+			if stop := c.checkLinkRequest(now, k, i); stop {
 				return
 			}
 		case <-done:
@@ -269,38 +260,36 @@ func (c *linkAddrCache) startAddressResolution(k tcpip.FullAddress, linkRes Link
 // checkLinkRequest checks whether previous attempt to resolve address has succeeded
 // and mark the entry accordingly, e.g. ready, failed, etc. Return true if request
 // can stop, false if another request should be sent.
-func (c *linkAddrCache) checkLinkRequest(k tcpip.FullAddress, attempt int) bool {
-	c.mu.Lock()
-	defer c.mu.Unlock()
-
-	entry, ok := c.cache[k]
+func (c *linkAddrCache) checkLinkRequest(now time.Time, k tcpip.FullAddress, attempt int) bool {
+	c.cache.Lock()
+	defer c.cache.Unlock()
+	entry, ok := c.cache.table[k]
 	if !ok {
 		// Entry was evicted from the cache.
 		return true
 	}
-
-	switch s := entry.state(); s {
-	case ready, failed, expired:
+	switch s := entry.s; s {
+	case ready, failed:
 		// Entry was made ready by resolver or failed. Either way we're done.
-		return true
 	case incomplete:
-		if attempt+1 >= c.resolutionAttempts {
-			// Max number of retries reached, mark entry as failed.
-			entry.changeState(failed)
-			return true
+		if attempt+1 < c.resolutionAttempts {
+			// No response yet, need to send another ARP request.
+			return false
 		}
-		// No response yet, need to send another ARP request.
-		return false
+		// Max number of retries reached, mark entry as failed.
+		entry.changeState(failed, now.Add(c.ageLimit))
 	default:
 		panic(fmt.Sprintf("invalid cache entry state: %s", s))
 	}
+	return true
 }
 
 func newLinkAddrCache(ageLimit, resolutionTimeout time.Duration, resolutionAttempts int) *linkAddrCache {
-	return &linkAddrCache{
+	c := &linkAddrCache{
 		ageLimit:           ageLimit,
 		resolutionTimeout:  resolutionTimeout,
 		resolutionAttempts: resolutionAttempts,
-		cache:              make(map[tcpip.FullAddress]*linkAddrEntry, linkAddrCacheSize),
 	}
+	c.cache.table = make(map[tcpip.FullAddress]*linkAddrEntry, linkAddrCacheSize)
+	return c
 }