<commit_before>// Copyright 2020 The gVisor Authors.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

package stack

import (
	"fmt"

	"gvisor.dev/gvisor/pkg/sleep"
	"gvisor.dev/gvisor/pkg/sync"
	"gvisor.dev/gvisor/pkg/tcpip"
)

const neighborCacheSize = 512 // max entries per interface

// NeighborStats holds metrics for the neighbor table.
type NeighborStats struct {
	// FailedEntryLookups counts the number of lookups performed on an entry in
	// Failed state.
	FailedEntryLookups *tcpip.StatCounter
}

// neighborCache maps IP addresses to link addresses. It uses the Least
// Recently Used (LRU) eviction strategy to implement a bounded cache for
// dynamically acquired entries. It contains the state machine and configuration
// for running Neighbor Unreachability Detection (NUD).
//
// There are two types of entries in the neighbor cache:
//  1. Dynamic entries are discovered automatically by neighbor discovery
//     protocols (e.g. ARP, NDP). These protocols will attempt to reconfirm
//     reachability with the device once the entry's state becomes Stale.
//  2. Static entries are explicitly added by a user and have no expiration.
//     Their state is always Static. The amount of static entries stored in the
//     cache is unbounded.
//
// neighborCache implements NUDHandler.
type neighborCache struct {
	nic   *NIC
	state *NUDState

	// mu protects the fields below.
	mu sync.RWMutex

	cache   map[tcpip.Address]*neighborEntry
	dynamic struct {
		lru neighborEntryList

		// count tracks the amount of dynamic entries in the cache. This is
		// needed since static entries do not count towards the LRU cache
		// eviction strategy.
		count uint16
	}
}

var _ NUDHandler = (*neighborCache)(nil)

// getOrCreateEntry retrieves a cache entry associated with addr. 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 (n *neighborCache) getOrCreateEntry(remoteAddr tcpip.Address, linkRes LinkAddressResolver) *neighborEntry {
	n.mu.Lock()
	defer n.mu.Unlock()

	if entry, ok := n.cache[remoteAddr]; ok {
		entry.mu.RLock()
		if entry.neigh.State != Static {
			n.dynamic.lru.Remove(entry)
			n.dynamic.lru.PushFront(entry)
		}
		entry.mu.RUnlock()
		return entry
	}

	// The entry that needs to be created must be dynamic since all static
	// entries are directly added to the cache via addStaticEntry.
	entry := newNeighborEntry(n.nic, remoteAddr, n.state, linkRes)
	if n.dynamic.count == neighborCacheSize {
		e := n.dynamic.lru.Back()
		e.mu.Lock()

		delete(n.cache, e.neigh.Addr)
		n.dynamic.lru.Remove(e)
		n.dynamic.count--

		e.dispatchRemoveEventLocked()
		e.setStateLocked(Unknown)
		e.notifyWakersLocked()
		e.mu.Unlock()
	}
	n.cache[remoteAddr] = entry
	n.dynamic.lru.PushFront(entry)
	n.dynamic.count++
	return entry
}

// entry looks up the neighbor cache for translating address to link address
// (e.g. IP -> MAC). If the LinkEndpoint requests address resolution and there
// is a LinkAddressResolver registered with the network protocol, the cache
// attempts to resolve the address and returns ErrWouldBlock. If a Waker is
// provided, it will be notified when address resolution is complete (success
// or not).
//
// If specified, the local address must be an address local to the interface the
// neighbor cache belongs to. The local address is the source address of a
// packet prompting NUD/link address resolution.
//
// If address resolution is required, ErrNoLinkAddress and a notification
// channel is returned for the top level caller to block. Channel is closed
// once address resolution is complete (success or not).
func (n *neighborCache) entry(remoteAddr, localAddr tcpip.Address, linkRes LinkAddressResolver, w *sleep.Waker) (NeighborEntry, <-chan struct{}, *tcpip.Error) {
	if linkAddr, ok := linkRes.ResolveStaticAddress(remoteAddr); ok {
		e := NeighborEntry{
			Addr:           remoteAddr,
			LinkAddr:       linkAddr,
			State:          Static,
			UpdatedAtNanos: 0,
		}
		return e, nil, nil
	}

	entry := n.getOrCreateEntry(remoteAddr, linkRes)
	entry.mu.Lock()
	defer entry.mu.Unlock()

	switch s := entry.neigh.State; s {
	case Stale:
		entry.handlePacketQueuedLocked(localAddr)
		fallthrough
	case Reachable, Static, Delay, Probe:
		// As per RFC 4861 section 7.3.3:
		//  "Neighbor Unreachability Detection operates in parallel with the sending
		//   of packets to a neighbor. While reasserting a neighbor's reachability,
		//   a node continues sending packets to that neighbor using the cached
		//   link-layer address."
		return entry.neigh, nil, nil
	case Unknown, Incomplete:
		entry.addWakerLocked(w)

		if entry.done == nil {
			// Address resolution needs to be initiated.
			if linkRes == nil {
				return entry.neigh, nil, tcpip.ErrNoLinkAddress
			}
			entry.done = make(chan struct{})
		}

		entry.handlePacketQueuedLocked(localAddr)
		return entry.neigh, entry.done, tcpip.ErrWouldBlock
	case Failed:
		return entry.neigh, nil, tcpip.ErrNoLinkAddress
	default:
		panic(fmt.Sprintf("Invalid cache entry state: %s", s))
	}
}

// removeWaker removes a waker that has been added when link resolution for
// addr was requested.
func (n *neighborCache) removeWaker(addr tcpip.Address, waker *sleep.Waker) {
	n.mu.Lock()
	if entry, ok := n.cache[addr]; ok {
		delete(entry.wakers, waker)
	}
	n.mu.Unlock()
}

// entries returns all entries in the neighbor cache.
func (n *neighborCache) entries() []NeighborEntry {
	entries := make([]NeighborEntry, 0, len(n.cache))
	n.mu.RLock()
	for _, entry := range n.cache {
		entry.mu.RLock()
		entries = append(entries, entry.neigh)
		entry.mu.RUnlock()
	}
	n.mu.RUnlock()
	return entries
}

// addStaticEntry adds a static entry to the neighbor cache, mapping an IP
// address to a link address. If a dynamic entry exists in the neighbor cache
// with the same address, it will be replaced with this static entry. If a
// static entry exists with the same address but different link address, it
// will be updated with the new link address. If a static entry exists with the
// same address and link address, nothing will happen.
func (n *neighborCache) addStaticEntry(addr tcpip.Address, linkAddr tcpip.LinkAddress) {
	n.mu.Lock()
	defer n.mu.Unlock()

	if entry, ok := n.cache[addr]; ok {
		entry.mu.Lock()
		if entry.neigh.State != Static {
			// Dynamic entry found with the same address.
			n.dynamic.lru.Remove(entry)
			n.dynamic.count--
		} else if entry.neigh.LinkAddr == linkAddr {
			// Static entry found with the same address and link address.
			entry.mu.Unlock()
			return
		} else {
			// Static entry found with the same address but different link address.
			entry.neigh.LinkAddr = linkAddr
			entry.dispatchChangeEventLocked()
			entry.mu.Unlock()<commit_msg>Correctly lock when listing neighbor entries<commit_after>// Copyright 2020 The gVisor Authors.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

package stack

import (
	"fmt"

	"gvisor.dev/gvisor/pkg/sleep"
	"gvisor.dev/gvisor/pkg/sync"
	"gvisor.dev/gvisor/pkg/tcpip"
)

const neighborCacheSize = 512 // max entries per interface

// NeighborStats holds metrics for the neighbor table.
type NeighborStats struct {
	// FailedEntryLookups counts the number of lookups performed on an entry in
	// Failed state.
	FailedEntryLookups *tcpip.StatCounter
}

// neighborCache maps IP addresses to link addresses. It uses the Least
// Recently Used (LRU) eviction strategy to implement a bounded cache for
// dynamically acquired entries. It contains the state machine and configuration
// for running Neighbor Unreachability Detection (NUD).
//
// There are two types of entries in the neighbor cache:
//  1. Dynamic entries are discovered automatically by neighbor discovery
//     protocols (e.g. ARP, NDP). These protocols will attempt to reconfirm
//     reachability with the device once the entry's state becomes Stale.
//  2. Static entries are explicitly added by a user and have no expiration.
//     Their state is always Static. The amount of static entries stored in the
//     cache is unbounded.
//
// neighborCache implements NUDHandler.
type neighborCache struct {
	nic   *NIC
	state *NUDState

	// mu protects the fields below.
	mu sync.RWMutex

	cache   map[tcpip.Address]*neighborEntry
	dynamic struct {
		lru neighborEntryList

		// count tracks the amount of dynamic entries in the cache. This is
		// needed since static entries do not count towards the LRU cache
		// eviction strategy.
		count uint16
	}
}

var _ NUDHandler = (*neighborCache)(nil)

// getOrCreateEntry retrieves a cache entry associated with addr. 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 (n *neighborCache) getOrCreateEntry(remoteAddr tcpip.Address, linkRes LinkAddressResolver) *neighborEntry {
	n.mu.Lock()
	defer n.mu.Unlock()

	if entry, ok := n.cache[remoteAddr]; ok {
		entry.mu.RLock()
		if entry.neigh.State != Static {
			n.dynamic.lru.Remove(entry)
			n.dynamic.lru.PushFront(entry)
		}
		entry.mu.RUnlock()
		return entry
	}

	// The entry that needs to be created must be dynamic since all static
	// entries are directly added to the cache via addStaticEntry.
	entry := newNeighborEntry(n.nic, remoteAddr, n.state, linkRes)
	if n.dynamic.count == neighborCacheSize {
		e := n.dynamic.lru.Back()
		e.mu.Lock()

		delete(n.cache, e.neigh.Addr)
		n.dynamic.lru.Remove(e)
		n.dynamic.count--

		e.dispatchRemoveEventLocked()
		e.setStateLocked(Unknown)
		e.notifyWakersLocked()
		e.mu.Unlock()
	}
	n.cache[remoteAddr] = entry
	n.dynamic.lru.PushFront(entry)
	n.dynamic.count++
	return entry
}

// entry looks up the neighbor cache for translating address to link address
// (e.g. IP -> MAC). If the LinkEndpoint requests address resolution and there
// is a LinkAddressResolver registered with the network protocol, the cache
// attempts to resolve the address and returns ErrWouldBlock. If a Waker is
// provided, it will be notified when address resolution is complete (success
// or not).
//
// If specified, the local address must be an address local to the interface the
// neighbor cache belongs to. The local address is the source address of a
// packet prompting NUD/link address resolution.
//
// If address resolution is required, ErrNoLinkAddress and a notification
// channel is returned for the top level caller to block. Channel is closed
// once address resolution is complete (success or not).
func (n *neighborCache) entry(remoteAddr, localAddr tcpip.Address, linkRes LinkAddressResolver, w *sleep.Waker) (NeighborEntry, <-chan struct{}, *tcpip.Error) {
	if linkAddr, ok := linkRes.ResolveStaticAddress(remoteAddr); ok {
		e := NeighborEntry{
			Addr:           remoteAddr,
			LinkAddr:       linkAddr,
			State:          Static,
			UpdatedAtNanos: 0,
		}
		return e, nil, nil
	}

	entry := n.getOrCreateEntry(remoteAddr, linkRes)
	entry.mu.Lock()
	defer entry.mu.Unlock()

	switch s := entry.neigh.State; s {
	case Stale:
		entry.handlePacketQueuedLocked(localAddr)
		fallthrough
	case Reachable, Static, Delay, Probe:
		// As per RFC 4861 section 7.3.3:
		//  "Neighbor Unreachability Detection operates in parallel with the sending
		//   of packets to a neighbor. While reasserting a neighbor's reachability,
		//   a node continues sending packets to that neighbor using the cached
		//   link-layer address."
		return entry.neigh, nil, nil
	case Unknown, Incomplete:
		entry.addWakerLocked(w)

		if entry.done == nil {
			// Address resolution needs to be initiated.
			if linkRes == nil {
				return entry.neigh, nil, tcpip.ErrNoLinkAddress
			}
			entry.done = make(chan struct{})
		}

		entry.handlePacketQueuedLocked(localAddr)
		return entry.neigh, entry.done, tcpip.ErrWouldBlock
	case Failed:
		return entry.neigh, nil, tcpip.ErrNoLinkAddress
	default:
		panic(fmt.Sprintf("Invalid cache entry state: %s", s))
	}
}

// removeWaker removes a waker that has been added when link resolution for
// addr was requested.
func (n *neighborCache) removeWaker(addr tcpip.Address, waker *sleep.Waker) {
	n.mu.Lock()
	if entry, ok := n.cache[addr]; ok {
		delete(entry.wakers, waker)
	}
	n.mu.Unlock()
}

// entries returns all entries in the neighbor cache.
func (n *neighborCache) entries() []NeighborEntry {
	n.mu.RLock()
	defer n.mu.RUnlock()

	entries := make([]NeighborEntry, 0, len(n.cache))
	for _, entry := range n.cache {
		entry.mu.RLock()
		entries = append(entries, entry.neigh)
		entry.mu.RUnlock()
	}
	return entries
}

// addStaticEntry adds a static entry to the neighbor cache, mapping an IP
// address to a link address. If a dynamic entry exists in the neighbor cache
// with the same address, it will be replaced with this static entry. If a
// static entry exists with the same address but different link address, it
// will be updated with the new link address. If a static entry exists with the
// same address and link address, nothing will happen.
func (n *neighborCache) addStaticEntry(addr tcpip.Address, linkAddr tcpip.LinkAddress) {
	n.mu.Lock()
	defer n.mu.Unlock()

	if entry, ok := n.cache[addr]; ok {
		entry.mu.Lock()
		if entry.neigh.State != Static {
			// Dynamic entry found with the same address.
			n.dynamic.lru.Remove(entry)
			n.dynamic.count--
		} else if entry.neigh.LinkAddr == linkAddr {
			// Static entry found with the same address and link address.
			entry.mu.Unlock()
			return
		} else {
			// Static entry found with the same address but different link address.
			entry.neigh.LinkAddr = linkAddr
			entry.dispatchChangeEventLocked()
			entry.mu.Unlock()
{'fraction_non_alphanumeric': 0.09225721784776902, 'fraction_numerical': 0.0031496062992125984, 'mean_word_length': 3.5360119047619047, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3810242', 'n_tokens_mistral': 4710, 'n_tokens_neox': 4425, 'n_words': 1785}