1 // Copyright 2020 The gVisor Authors.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14 15 package stack
16 17 import (
18 "math"
19 "math/rand"
20 "sync"
21 "time"
22 23 "gvisor.dev/gvisor/pkg/tcpip"
24 )
25 26 const (
27 // defaultBaseReachableTime is the default base duration for computing the
28 // random reachable time.
29 //
30 // Reachable time is the duration for which a neighbor is considered
31 // reachable after a positive reachability confirmation is received. It is a
32 // function of a uniformly distributed random value between the minimum and
33 // maximum random factors, multiplied by the base reachable time. Using a
34 // random component eliminates the possibility that Neighbor Unreachability
35 // Detection messages will synchronize with each other.
36 //
37 // Default taken from REACHABLE_TIME of RFC 4861 section 10.
38 defaultBaseReachableTime = 30 * time.Second
39 40 // minimumBaseReachableTime is the minimum base duration for computing the
41 // random reachable time.
42 //
43 // Minimum = 1ms
44 minimumBaseReachableTime = time.Millisecond
45 46 // defaultMinRandomFactor is the default minimum value of the random factor
47 // used for computing reachable time.
48 //
49 // Default taken from MIN_RANDOM_FACTOR of RFC 4861 section 10.
50 defaultMinRandomFactor = 0.5
51 52 // defaultMaxRandomFactor is the default maximum value of the random factor
53 // used for computing reachable time.
54 //
55 // The default value depends on the value of MinRandomFactor.
56 // If MinRandomFactor is less than MAX_RANDOM_FACTOR of RFC 4861 section 10,
57 // the value from the RFC will be used; otherwise, the default is
58 // MinRandomFactor multiplied by three.
59 defaultMaxRandomFactor = 1.5
60 61 // defaultRetransmitTimer is the default amount of time to wait between
62 // sending reachability probes.
63 //
64 // Default taken from RETRANS_TIMER of RFC 4861 section 10.
65 defaultRetransmitTimer = time.Second
66 67 // minimumRetransmitTimer is the minimum amount of time to wait between
68 // sending reachability probes.
69 //
70 // Note, RFC 4861 does not impose a minimum Retransmit Timer, but we do here
71 // to make sure the messages are not sent all at once. We also come to this
72 // value because in the RetransmitTimer field of a Router Advertisement, a
73 // value of 0 means unspecified, so the smallest valid value is 1. Note, the
74 // unit of the RetransmitTimer field in the Router Advertisement is
75 // milliseconds.
76 minimumRetransmitTimer = time.Millisecond
77 78 // defaultDelayFirstProbeTime is the default duration to wait for a
79 // non-Neighbor-Discovery related protocol to reconfirm reachability after
80 // entering the DELAY state. After this time, a reachability probe will be
81 // sent and the entry will transition to the PROBE state.
82 //
83 // Default taken from DELAY_FIRST_PROBE_TIME of RFC 4861 section 10.
84 defaultDelayFirstProbeTime = 5 * time.Second
85 86 // defaultMaxMulticastProbes is the default number of reachabililty probes
87 // to send before concluding negative reachability and deleting the neighbor
88 // entry from the INCOMPLETE state.
89 //
90 // Default taken from MAX_MULTICAST_SOLICIT of RFC 4861 section 10.
91 defaultMaxMulticastProbes = 3
92 93 // defaultMaxUnicastProbes is the default number of reachability probes to
94 // send before concluding retransmission from within the PROBE state should
95 // cease and the entry SHOULD be deleted.
96 //
97 // Default taken from MAX_UNICASE_SOLICIT of RFC 4861 section 10.
98 defaultMaxUnicastProbes = 3
99 100 // defaultMaxAnycastDelayTime is the default time in which the stack SHOULD
101 // delay sending a response for a random time between 0 and this time, if the
102 // target address is an anycast address.
103 //
104 // Default taken from MAX_ANYCAST_DELAY_TIME of RFC 4861 section 10.
105 defaultMaxAnycastDelayTime = time.Second
106 107 // defaultMaxReachbilityConfirmations is the default amount of unsolicited
108 // reachability confirmation messages a node MAY send to all-node multicast
109 // address when it determines its link-layer address has changed.
110 //
111 // Default taken from MAX_NEIGHBOR_ADVERTISEMENT of RFC 4861 section 10.
112 defaultMaxReachbilityConfirmations = 3
113 )
114 115 // NUDDispatcher is the interface integrators of netstack must implement to
116 // receive and handle NUD related events.
117 type NUDDispatcher interface {
118 // OnNeighborAdded will be called when a new entry is added to a NIC's (with
119 // ID nicID) neighbor table.
120 //
121 // This function is permitted to block indefinitely without interfering with
122 // the stack's operation.
123 //
124 // May be called concurrently.
125 OnNeighborAdded(tcpip.NICID, NeighborEntry)
126 127 // OnNeighborChanged will be called when an entry in a NIC's (with ID nicID)
128 // neighbor table changes state and/or link address.
129 //
130 // This function is permitted to block indefinitely without interfering with
131 // the stack's operation.
132 //
133 // May be called concurrently.
134 OnNeighborChanged(tcpip.NICID, NeighborEntry)
135 136 // OnNeighborRemoved will be called when an entry is removed from a NIC's
137 // (with ID nicID) neighbor table.
138 //
139 // This function is permitted to block indefinitely without interfering with
140 // the stack's operation.
141 //
142 // May be called concurrently.
143 OnNeighborRemoved(tcpip.NICID, NeighborEntry)
144 }
145 146 // ReachabilityConfirmationFlags describes the flags used within a reachability
147 // confirmation (e.g. ARP reply or Neighbor Advertisement for ARP or NDP,
148 // respectively).
149 type ReachabilityConfirmationFlags struct {
150 // Solicited indicates that the advertisement was sent in response to a
151 // reachability probe.
152 Solicited bool
153 154 // Override indicates that the reachability confirmation should override an
155 // existing neighbor cache entry and update the cached link-layer address.
156 // When Override is not set the confirmation will not update a cached
157 // link-layer address, but will update an existing neighbor cache entry for
158 // which no link-layer address is known.
159 Override bool
160 161 // IsRouter indicates that the sender is a router.
162 IsRouter bool
163 }
164 165 // NUDConfigurations is the NUD configurations for the netstack. This is used
166 // by the neighbor cache to operate the NUD state machine on each device in the
167 // local network.
168 //
169 // +stateify savable
170 type NUDConfigurations struct {
171 // BaseReachableTime is the base duration for computing the random reachable
172 // time.
173 //
174 // Reachable time is the duration for which a neighbor is considered
175 // reachable after a positive reachability confirmation is received. It is a
176 // function of uniformly distributed random value between minRandomFactor and
177 // maxRandomFactor multiplied by baseReachableTime. Using a random component
178 // eliminates the possibility that Neighbor Unreachability Detection messages
179 // will synchronize with each other.
180 //
181 // After this time, a neighbor entry will transition from REACHABLE to STALE
182 // state.
183 //
184 // Must be greater than 0.
185 BaseReachableTime time.Duration
186 187 // LearnBaseReachableTime enables learning BaseReachableTime during runtime
188 // from the neighbor discovery protocol, if supported.
189 //
190 // TODO(gvisor.dev/issue/2240): Implement this NUD configuration option.
191 LearnBaseReachableTime bool
192 193 // MinRandomFactor is the minimum value of the random factor used for
194 // computing reachable time.
195 //
196 // See BaseReachbleTime for more information on computing the reachable time.
197 //
198 // Must be greater than 0.
199 MinRandomFactor float32
200 201 // MaxRandomFactor is the maximum value of the random factor used for
202 // computing reachabile time.
203 //
204 // See BaseReachbleTime for more information on computing the reachable time.
205 //
206 // Must be great than or equal to MinRandomFactor.
207 MaxRandomFactor float32
208 209 // RetransmitTimer is the duration between retransmission of reachability
210 // probes in the PROBE state.
211 RetransmitTimer time.Duration
212 213 // LearnRetransmitTimer enables learning RetransmitTimer during runtime from
214 // the neighbor discovery protocol, if supported.
215 //
216 // TODO(gvisor.dev/issue/2241): Implement this NUD configuration option.
217 LearnRetransmitTimer bool
218 219 // DelayFirstProbeTime is the duration to wait for a non-Neighbor-Discovery
220 // related protocol to reconfirm reachability after entering the DELAY state.
221 // After this time, a reachability probe will be sent and the entry will
222 // transition to the PROBE state.
223 //
224 // Must be greater than 0.
225 DelayFirstProbeTime time.Duration
226 227 // MaxMulticastProbes is the number of reachability probes to send before
228 // concluding negative reachability and deleting the neighbor entry from the
229 // INCOMPLETE state.
230 //
231 // Must be greater than 0.
232 MaxMulticastProbes uint32
233 234 // MaxUnicastProbes is the number of reachability probes to send before
235 // concluding retransmission from within the PROBE state should cease and
236 // entry SHOULD be deleted.
237 //
238 // Must be greater than 0.
239 MaxUnicastProbes uint32
240 241 // MaxAnycastDelayTime is the time in which the stack SHOULD delay sending a
242 // response for a random time between 0 and this time, if the target address
243 // is an anycast address.
244 //
245 // TODO(gvisor.dev/issue/2242): Use this option when sending solicited
246 // neighbor confirmations to anycast addresses and proxying neighbor
247 // confirmations.
248 MaxAnycastDelayTime time.Duration
249 250 // MaxReachabilityConfirmations is the number of unsolicited reachability
251 // confirmation messages a node MAY send to all-node multicast address when
252 // it determines its link-layer address has changed.
253 //
254 // TODO(gvisor.dev/issue/2246): Discuss if implementation of this NUD
255 // configuration option is necessary.
256 MaxReachabilityConfirmations uint32
257 }
258 259 // DefaultNUDConfigurations returns a NUDConfigurations populated with default
260 // values defined by RFC 4861 section 10.
261 func DefaultNUDConfigurations() NUDConfigurations {
262 return NUDConfigurations{
263 BaseReachableTime: defaultBaseReachableTime,
264 LearnBaseReachableTime: true,
265 MinRandomFactor: defaultMinRandomFactor,
266 MaxRandomFactor: defaultMaxRandomFactor,
267 RetransmitTimer: defaultRetransmitTimer,
268 LearnRetransmitTimer: true,
269 DelayFirstProbeTime: defaultDelayFirstProbeTime,
270 MaxMulticastProbes: defaultMaxMulticastProbes,
271 MaxUnicastProbes: defaultMaxUnicastProbes,
272 MaxAnycastDelayTime: defaultMaxAnycastDelayTime,
273 MaxReachabilityConfirmations: defaultMaxReachbilityConfirmations,
274 }
275 }
276 277 // resetInvalidFields modifies an invalid NDPConfigurations with valid values.
278 // If invalid values are present in c, the corresponding default values will be
279 // used instead. This is needed to check, and conditionally fix, user-specified
280 // NUDConfigurations.
281 func (c *NUDConfigurations) resetInvalidFields() {
282 if c.BaseReachableTime < minimumBaseReachableTime {
283 c.BaseReachableTime = defaultBaseReachableTime
284 }
285 if c.MinRandomFactor <= 0 {
286 c.MinRandomFactor = defaultMinRandomFactor
287 }
288 if c.MaxRandomFactor < c.MinRandomFactor {
289 c.MaxRandomFactor = calcMaxRandomFactor(c.MinRandomFactor)
290 }
291 if c.RetransmitTimer < minimumRetransmitTimer {
292 c.RetransmitTimer = defaultRetransmitTimer
293 }
294 if c.DelayFirstProbeTime == 0 {
295 c.DelayFirstProbeTime = defaultDelayFirstProbeTime
296 }
297 if c.MaxMulticastProbes == 0 {
298 c.MaxMulticastProbes = defaultMaxMulticastProbes
299 }
300 if c.MaxUnicastProbes == 0 {
301 c.MaxUnicastProbes = defaultMaxUnicastProbes
302 }
303 }
304 305 // calcMaxRandomFactor calculates the maximum value of the random factor used
306 // for computing reachable time. This function is necessary for when the
307 // default specified in RFC 4861 section 10 is less than the current
308 // MinRandomFactor.
309 //
310 // Assumes minRandomFactor is positive since validation of the minimum value
311 // should come before the validation of the maximum.
312 func calcMaxRandomFactor(minRandomFactor float32) float32 {
313 if minRandomFactor > defaultMaxRandomFactor {
314 return minRandomFactor * 3
315 }
316 return defaultMaxRandomFactor
317 }
318 319 // +stateify savable
320 type nudStateMu struct {
321 sync.RWMutex `state:"nosave"`
322 323 config NUDConfigurations
324 325 // reachableTime is the duration to wait for a REACHABLE entry to
326 // transition into STALE after inactivity. This value is calculated with
327 // the algorithm defined in RFC 4861 section 6.3.2.
328 reachableTime time.Duration
329 330 expiration tcpip.MonotonicTime
331 prevBaseReachableTime time.Duration
332 prevMinRandomFactor float32
333 prevMaxRandomFactor float32
334 }
335 336 // NUDState stores states needed for calculating reachable time.
337 //
338 // +stateify savable
339 type NUDState struct {
340 clock tcpip.Clock
341 // TODO(b/341946753): Restore when netstack is savable.
342 rng *rand.Rand `state:"nosave"`
343 mu nudStateMu
344 }
345 346 // NewNUDState returns new NUDState using c as configuration and the specified
347 // random number generator for use in recomputing ReachableTime.
348 func NewNUDState(c NUDConfigurations, clock tcpip.Clock, rng *rand.Rand) *NUDState {
349 s := &NUDState{
350 clock: clock,
351 rng: rng,
352 }
353 s.mu.config = c
354 return s
355 }
356 357 // Config returns the NUD configuration.
358 func (s *NUDState) Config() NUDConfigurations {
359 s.mu.RLock()
360 defer s.mu.RUnlock()
361 return s.mu.config
362 }
363 364 // SetConfig replaces the existing NUD configurations with c.
365 func (s *NUDState) SetConfig(c NUDConfigurations) {
366 s.mu.Lock()
367 defer s.mu.Unlock()
368 s.mu.config = c
369 }
370 371 // ReachableTime returns the duration to wait for a REACHABLE entry to
372 // transition into STALE after inactivity. This value is recalculated for new
373 // values of BaseReachableTime, MinRandomFactor, and MaxRandomFactor using the
374 // algorithm defined in RFC 4861 section 6.3.2.
375 func (s *NUDState) ReachableTime() time.Duration {
376 s.mu.Lock()
377 defer s.mu.Unlock()
378 379 if s.clock.NowMonotonic().After(s.mu.expiration) ||
380 s.mu.config.BaseReachableTime != s.mu.prevBaseReachableTime ||
381 s.mu.config.MinRandomFactor != s.mu.prevMinRandomFactor ||
382 s.mu.config.MaxRandomFactor != s.mu.prevMaxRandomFactor {
383 s.recomputeReachableTimeLocked()
384 }
385 return s.mu.reachableTime
386 }
387 388 // recomputeReachableTimeLocked forces a recalculation of ReachableTime using
389 // the algorithm defined in RFC 4861 section 6.3.2.
390 //
391 // This SHOULD automatically be invoked during certain situations, as per
392 // RFC 4861 section 6.3.4:
393 //
394 // If the received Reachable Time value is non-zero, the host SHOULD set its
395 // BaseReachableTime variable to the received value. If the new value
396 // differs from the previous value, the host SHOULD re-compute a new random
397 // ReachableTime value. ReachableTime is computed as a uniformly
398 // distributed random value between MIN_RANDOM_FACTOR and MAX_RANDOM_FACTOR
399 // times the BaseReachableTime. Using a random component eliminates the
400 // possibility that Neighbor Unreachability Detection messages will
401 // synchronize with each other.
402 //
403 // In most cases, the advertised Reachable Time value will be the same in
404 // consecutive Router Advertisements, and a host's BaseReachableTime rarely
405 // changes. In such cases, an implementation SHOULD ensure that a new
406 // random value gets re-computed at least once every few hours.
407 //
408 // s.mu MUST be locked for writing.
409 func (s *NUDState) recomputeReachableTimeLocked() {
410 s.mu.prevBaseReachableTime = s.mu.config.BaseReachableTime
411 s.mu.prevMinRandomFactor = s.mu.config.MinRandomFactor
412 s.mu.prevMaxRandomFactor = s.mu.config.MaxRandomFactor
413 414 randomFactor := s.mu.config.MinRandomFactor + s.rng.Float32()*(s.mu.config.MaxRandomFactor-s.mu.config.MinRandomFactor)
415 416 // Check for overflow, given that minRandomFactor and maxRandomFactor are
417 // guaranteed to be positive numbers.
418 if math.MaxInt64/randomFactor < float32(s.mu.config.BaseReachableTime) {
419 s.mu.reachableTime = time.Duration(math.MaxInt64)
420 } else if randomFactor == 1 {
421 // Avoid loss of precision when a large base reachable time is used.
422 s.mu.reachableTime = s.mu.config.BaseReachableTime
423 } else {
424 reachableTime := int64(float32(s.mu.config.BaseReachableTime) * randomFactor)
425 s.mu.reachableTime = time.Duration(reachableTime)
426 }
427 428 s.mu.expiration = s.clock.NowMonotonic().Add(2 * time.Hour)
429 }
430