ndp_cache.c
Go to the documentation of this file.
1 /**
2  * @file ndp_cache.c
3  * @brief Neighbor and destination cache management
4  *
5  * @section License
6  *
7  * SPDX-License-Identifier: GPL-2.0-or-later
8  *
9  * Copyright (C) 2010-2024 Oryx Embedded SARL. All rights reserved.
10  *
11  * This file is part of CycloneTCP Open.
12  *
13  * This program is free software; you can redistribute it and/or
14  * modify it under the terms of the GNU General Public License
15  * as published by the Free Software Foundation; either version 2
16  * of the License, or (at your option) any later version.
17  *
18  * This program is distributed in the hope that it will be useful,
19  * but WITHOUT ANY WARRANTY; without even the implied warranty of
20  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
21  * GNU General Public License for more details.
22  *
23  * You should have received a copy of the GNU General Public License
24  * along with this program; if not, write to the Free Software Foundation,
25  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
26  *
27  * @author Oryx Embedded SARL (www.oryx-embedded.com)
28  * @version 2.4.0
29  **/
30 
31 //Switch to the appropriate trace level
32 #define TRACE_LEVEL NDP_TRACE_LEVEL
33 
34 //Dependencies
35 #include "core/net.h"
36 #include "ipv6/ipv6_misc.h"
37 #include "ipv6/icmpv6.h"
38 #include "ipv6/ndp.h"
39 #include "ipv6/ndp_cache.h"
40 #include "ipv6/ndp_misc.h"
41 #include "debug.h"
42 
43 //Check TCP/IP stack configuration
44 #if (IPV6_SUPPORT == ENABLED && NDP_SUPPORT == ENABLED)
45 
46 
47 /**
48  * @brief Update Neighbor cache entry state
49  * @param[in] entry Pointer to a Neighbor cache entry
50  * @param[in] newState New state to switch to
51  **/
52 
54 {
55 #if defined(NDP_CHANGE_STATE_HOOK)
56  NDP_CHANGE_STATE_HOOK(entry, newState);
57 #endif
58 
59  //Save current time
60  entry->timestamp = osGetSystemTime();
61  //Switch to the new state
62  entry->state = newState;
63 }
64 
65 
66 /**
67  * @brief Create a new entry in the Neighbor cache
68  * @param[in] interface Underlying network interface
69  * @return Pointer to the newly created entry
70  **/
71 
73 {
74  uint_t i;
76  NdpNeighborCacheEntry *entry;
77  NdpNeighborCacheEntry *oldestEntry;
78 
79  //Get current time
81 
82  //Keep track of the oldest entry
83  oldestEntry = NULL;
84 
85  //Loop through Neighbor cache entries
86  for(i = 0; i < NDP_NEIGHBOR_CACHE_SIZE; i++)
87  {
88  //Point to the current entry
89  entry = &interface->ndpContext.neighborCache[i];
90 
91  //Check the state of the Neighbor cache entry
92  if(entry->state == NDP_STATE_NONE)
93  {
94  //Initialize Neighbor cache entry
95  osMemset(entry, 0, sizeof(NdpNeighborCacheEntry));
96 
97  //Return a pointer to the Neighbor cache entry
98  return entry;
99  }
100  else if(entry->state == NDP_STATE_PERMANENT)
101  {
102  //Static Neighbor cache entries are never updated
103  }
104  else
105  {
106  //Keep track of the oldest entry in the table
107  if(oldestEntry == NULL)
108  {
109  oldestEntry = entry;
110  }
111  else if(entry->state == NDP_STATE_STALE &&
112  oldestEntry->state != NDP_STATE_STALE)
113  {
114  oldestEntry = entry;
115  }
116  else if(entry->state != NDP_STATE_STALE &&
117  oldestEntry->state == NDP_STATE_STALE)
118  {
119  }
120  else if((time - entry->timestamp) > (time - oldestEntry->timestamp))
121  {
122  oldestEntry = entry;
123  }
124  else
125  {
126  }
127  }
128  }
129 
130  //Any entry available in the Neighbor cache?
131  if(oldestEntry != NULL)
132  {
133  //Drop any pending packets
134  ndpFlushQueuedPackets(interface, oldestEntry);
135  //The oldest entry is removed whenever the table runs out of space
136  ndpChangeState(oldestEntry, NDP_STATE_NONE);
137  //Initialize Neighbor cache entry
138  osMemset(oldestEntry, 0, sizeof(NdpNeighborCacheEntry));
139  }
140 
141  //Return a pointer to the Neighbor cache entry
142  return oldestEntry;
143 }
144 
145 
146 /**
147  * @brief Search the Neighbor cache for a given IPv6 address
148  * @param[in] interface Underlying network interface
149  * @param[in] ipAddr IPv6 address
150  * @return A pointer to the matching entry is returned. NULL is returned if
151  * the specified IPv6 address could not be found in the Neighbor cache
152  **/
153 
155  const Ipv6Addr *ipAddr)
156 {
157  uint_t i;
158  NdpNeighborCacheEntry *entry;
159 
160  //Loop through Neighbor cache entries
161  for(i = 0; i < NDP_NEIGHBOR_CACHE_SIZE; i++)
162  {
163  //Point to the current entry
164  entry = &interface->ndpContext.neighborCache[i];
165 
166  //Check whether the entry is currently in use
167  if(entry->state != NDP_STATE_NONE)
168  {
169  //Current entry matches the specified address?
170  if(ipv6CompAddr(&entry->ipAddr, ipAddr))
171  {
172  return entry;
173  }
174  }
175  }
176 
177  //No matching entry in Neighbor cache
178  return NULL;
179 }
180 
181 
182 /**
183  * @brief Periodically update Neighbor cache
184  * @param[in] interface Underlying network interface
185  **/
186 
188 {
189  uint_t i;
190  systime_t time;
191  NdpNeighborCacheEntry *entry;
192 
193  //Get current time
194  time = osGetSystemTime();
195 
196  //Go through Neighbor cache
197  for(i = 0; i < NDP_NEIGHBOR_CACHE_SIZE; i++)
198  {
199  //Point to the current entry
200  entry = &interface->ndpContext.neighborCache[i];
201 
202  //Check the state of the Neighbor cache entry
203  if(entry->state == NDP_STATE_PERMANENT)
204  {
205  //Static Neighbor cache entries are never updated
206  }
207  else if(entry->state == NDP_STATE_INCOMPLETE)
208  {
209  //The Neighbor Solicitation timed out?
210  if(timeCompare(time, entry->timestamp + entry->timeout) >= 0)
211  {
212  //Increment retransmission counter
213  entry->retransmitCount++;
214 
215  //Check whether the maximum number of retransmissions has been exceeded
217  {
218  //Retransmit the multicast Neighbor Solicitation message
219  ndpSendNeighborSol(interface, &entry->ipAddr, TRUE);
220 
221  //Save the time at which the message was sent
222  entry->timestamp = time;
223  //Set timeout value
224  entry->timeout = interface->ndpContext.retransTimer;
225  }
226  else
227  {
228  //Drop packets that are waiting for address resolution
229  ndpFlushQueuedPackets(interface, entry);
230 
231  //The entry should be deleted since address resolution has failed
233  }
234  }
235  }
236  else if(entry->state == NDP_STATE_REACHABLE)
237  {
238  //Periodically time out Neighbor cache entries
239  if(timeCompare(time, entry->timestamp + entry->timeout) >= 0)
240  {
241  //Enter STALE state
243  }
244  }
245  else if(entry->state == NDP_STATE_STALE)
246  {
247  //The neighbor is no longer known to be reachable but until traffic
248  //is sent to the neighbor, no attempt should be made to verify its
249  //reachability
250  }
251  else if(entry->state == NDP_STATE_DELAY)
252  {
253  //Wait for the specified delay before sending the first probe
254  if(timeCompare(time, entry->timestamp + entry->timeout) >= 0)
255  {
256  //Reset retransmission counter
257  entry->retransmitCount = 0;
258 
259  //Send a unicast Neighbor Solicitation message
260  ndpSendNeighborSol(interface, &entry->ipAddr, FALSE);
261 
262  //Set timeout value
263  entry->timeout = interface->ndpContext.retransTimer;
264  //Switch to the PROBE state
266  }
267  }
268  else if(entry->state == NDP_STATE_PROBE)
269  {
270  //The request timed out?
271  if(timeCompare(time, entry->timestamp + entry->timeout) >= 0)
272  {
273  //Increment retransmission counter
274  entry->retransmitCount++;
275 
276  //Check whether the maximum number of retransmissions has been
277  //exceeded
279  {
280  //Send a unicast Neighbor Solicitation message
281  ndpSendNeighborSol(interface, &entry->ipAddr, FALSE);
282 
283  //Save the time at which the packet was sent
284  entry->timestamp = time;
285  //Set timeout value
286  entry->timeout = interface->ndpContext.retransTimer;
287  }
288  else
289  {
290  //The entry should be deleted since the host is not reachable
291  //anymore
293 
294  //If at some point communication ceases to proceed, as determined
295  //by the Neighbor Unreachability Detection algorithm, next-hop
296  //determination may need to be performed again
297  ndpUpdateNextHop(interface, &entry->ipAddr);
298  }
299  }
300  }
301  else
302  {
303  //Just for sanity
305  }
306  }
307 }
308 
309 
310 /**
311  * @brief Flush Neighbor cache
312  * @param[in] interface Underlying network interface
313  **/
314 
316 {
317  uint_t i;
318  NdpNeighborCacheEntry *entry;
319 
320  //Loop through Neighbor cache entries
321  for(i = 0; i < NDP_NEIGHBOR_CACHE_SIZE; i++)
322  {
323  //Point to the current entry
324  entry = &interface->ndpContext.neighborCache[i];
325 
326  //Check the state of the Neighbor cache entry
327  if(entry->state == NDP_STATE_PERMANENT)
328  {
329  //Static Neighbor cache entries are never updated
330  }
331  else
332  {
333  //Drop packets that are waiting for address resolution
334  ndpFlushQueuedPackets(interface, entry);
335 
336  //Delete Neighbor cache entry
338  }
339  }
340 }
341 
342 
343 /**
344  * @brief Send packets that are waiting for address resolution
345  * @param[in] interface Underlying network interface
346  * @param[in] entry Pointer to a Neighbor cache entry
347  * @return The number of packets that have been sent
348  **/
349 
351 {
352  uint_t i;
353  NdpQueueItem *item;
354 #if (ETH_SUPPORT == ENABLED)
355  NetInterface *physicalInterface;
356 
357  //Point to the physical interface
358  physicalInterface = nicGetPhysicalInterface(interface);
359 #endif
360 
361  //Reset packet counter
362  i = 0;
363 
364  //Check the state of the Neighbor cache entry
365  if(entry->state == NDP_STATE_INCOMPLETE)
366  {
367  //Loop through the queued packets
368  for(i = 0; i < entry->queueSize; i++)
369  {
370  //Point to the current queue item
371  item = &entry->queue[i];
372 
373 #if (ETH_SUPPORT == ENABLED)
374  //Ethernet interface?
375  if(physicalInterface->nicDriver != NULL &&
376  physicalInterface->nicDriver->type == NIC_TYPE_ETHERNET)
377  {
378  size_t length;
379 
380  //Retrieve the length of the IPv6 packet
381  length = netBufferGetLength(item->buffer) - item->offset;
382  //Update IP statistics
383  ipv6UpdateOutStats(interface, &entry->ipAddr, length);
384 
385  //Send the IPv6 packet
386  ethSendFrame(interface, &entry->macAddr, ETH_TYPE_IPV6,
387  item->buffer, item->offset, &item->ancillary);
388  }
389 #endif
390  //Release memory buffer
391  netBufferFree(item->buffer);
392  }
393  }
394 
395  //The queue is now empty
396  entry->queueSize = 0;
397 
398  //Return the number of packets that have been sent
399  return i;
400 }
401 
402 
403 /**
404  * @brief Flush packet queue
405  * @param[in] interface Underlying network interface
406  * @param[in] entry Pointer to a Neighbor cache entry
407  **/
408 
410 {
411  uint_t i;
412  NdpQueueItem *item;
413 
414  //Check the state of the Neighbor cache entry
415  if(entry->state == NDP_STATE_INCOMPLETE)
416  {
417  //Loop through the queued packets
418  for(i = 0; i < entry->queueSize; i++)
419  {
420  //Point to the current queue item
421  item = &entry->queue[i];
422 
423  //Check whether the address resolution has failed
425  {
426  //Check whether the packet has been forwarded
427  if(item->srcInterface != NULL)
428  {
429  //A Destination Unreachable message should be generated by a
430  //router in response to a packet that cannot be delivered
432  ICMPV6_CODE_ADDR_UNREACHABLE, 0, item->buffer, item->offset);
433  }
434  }
435 
436  //Release memory buffer
437  netBufferFree(item->buffer);
438  }
439  }
440 
441  //The queue is now empty
442  entry->queueSize = 0;
443 }
444 
445 
446 /**
447  * @brief Create a new entry in the Destination Cache
448  * @param[in] interface Underlying network interface
449  * @return Pointer to the newly created entry
450  **/
451 
453 {
454  uint_t i;
455  systime_t time;
456  NdpDestCacheEntry *entry;
457  NdpDestCacheEntry *oldestEntry;
458 
459  //Get current time
460  time = osGetSystemTime();
461 
462  //Keep track of the oldest entry
463  oldestEntry = &interface->ndpContext.destCache[0];
464 
465  //Loop through Destination cache entries
466  for(i = 0; i < NDP_DEST_CACHE_SIZE; i++)
467  {
468  //Point to the current entry
469  entry = &interface->ndpContext.destCache[i];
470 
471  //Check whether the entry is currently in use or not
473  {
474  //Erase contents
475  osMemset(entry, 0, sizeof(NdpDestCacheEntry));
476  //Return a pointer to the Destination cache entry
477  return entry;
478  }
479 
480  //Keep track of the oldest entry in the table
481  if((time - entry->timestamp) > (time - oldestEntry->timestamp))
482  {
483  oldestEntry = entry;
484  }
485  }
486 
487  //The oldest entry is removed whenever the table runs out of space
488  osMemset(oldestEntry, 0, sizeof(NdpDestCacheEntry));
489 
490  //Return a pointer to the Destination cache entry
491  return oldestEntry;
492 }
493 
494 
495 /**
496  * @brief Search the Destination Cache for a given destination address
497  * @param[in] interface Underlying network interface
498  * @param[in] destAddr Destination IPv6 address
499  * @return A pointer to the matching entry is returned. NULL is returned if
500  * the specified address could not be found in the Destination cache
501  **/
502 
504  const Ipv6Addr *destAddr)
505 {
506  uint_t i;
507  NdpDestCacheEntry *entry;
508 
509  //Loop through Destination Cache entries
510  for(i = 0; i < NDP_DEST_CACHE_SIZE; i++)
511  {
512  //Point to the current entry
513  entry = &interface->ndpContext.destCache[i];
514 
515  //Current entry matches the specified destination address?
516  if(ipv6CompAddr(&entry->destAddr, destAddr))
517  {
518  return entry;
519  }
520  }
521 
522  //No matching entry in Destination Cache
523  return NULL;
524 }
525 
526 
527 /**
528  * @brief Flush Destination Cache
529  * @param[in] interface Underlying network interface
530  **/
531 
533 {
534  //Clear the Destination Cache
535  osMemset(interface->ndpContext.destCache, 0,
536  sizeof(interface->ndpContext.destCache));
537 }
538 
539 #endif
unsigned int uint_t
Definition: compiler_port.h:50
Debugging facilities.
uint32_t time
error_t ethSendFrame(NetInterface *interface, const MacAddr *destAddr, uint16_t type, NetBuffer *buffer, size_t offset, NetTxAncillary *ancillary)
Send an Ethernet frame.
Definition: ethernet.c:399
@ ETH_TYPE_IPV6
Definition: ethernet.h:168
error_t icmpv6SendErrorMessage(NetInterface *interface, uint8_t type, uint8_t code, uint32_t parameter, const NetBuffer *ipPacket, size_t ipPacketOffset)
Send an ICMPv6 Error message.
Definition: icmpv6.c:507
ICMPv6 (Internet Control Message Protocol Version 6)
@ ICMPV6_TYPE_DEST_UNREACHABLE
Definition: icmpv6.h:53
@ ICMPV6_CODE_ADDR_UNREACHABLE
Definition: icmpv6.h:80
Ipv4Addr ipAddr
Definition: ipcp.h:105
Ipv4Addr destAddr
Definition: ipv4.h:299
const Ipv6Addr IPV6_UNSPECIFIED_ADDR
Definition: ipv6.c:65
Ipv6Addr
Definition: ipv6.h:251
#define ipv6CompAddr(ipAddr1, ipAddr2)
Definition: ipv6.h:120
void ipv6UpdateOutStats(NetInterface *interface, const Ipv6Addr *destIpAddr, size_t length)
Update IPv6 output statistics.
Definition: ipv6_misc.c:1518
Helper functions for IPv6.
error_t ndpSendNeighborSol(NetInterface *interface, const Ipv6Addr *targetIpAddr, bool_t multicast)
Send a Neighbor Solicitation message.
Definition: ndp.c:1689
NDP (Neighbor Discovery Protocol)
#define NDP_MAX_UNICAST_SOLICIT
Definition: ndp.h:151
#define NDP_DEST_CACHE_SIZE
Definition: ndp.h:60
NdpState
Neighbor cache entry states.
Definition: ndp.h:248
@ NDP_STATE_NONE
Definition: ndp.h:249
@ NDP_STATE_PROBE
Definition: ndp.h:254
@ NDP_STATE_DELAY
Definition: ndp.h:253
@ NDP_STATE_REACHABLE
Definition: ndp.h:251
@ NDP_STATE_STALE
Definition: ndp.h:252
@ NDP_STATE_PERMANENT
Definition: ndp.h:255
@ NDP_STATE_INCOMPLETE
Definition: ndp.h:250
#define NDP_NEIGHBOR_CACHE_SIZE
Definition: ndp.h:53
#define NDP_MAX_MULTICAST_SOLICIT
Definition: ndp.h:144
uint_t ndpSendQueuedPackets(NetInterface *interface, NdpNeighborCacheEntry *entry)
Send packets that are waiting for address resolution.
Definition: ndp_cache.c:350
void ndpFlushDestCache(NetInterface *interface)
Flush Destination Cache.
Definition: ndp_cache.c:532
void ndpFlushNeighborCache(NetInterface *interface)
Flush Neighbor cache.
Definition: ndp_cache.c:315
NdpNeighborCacheEntry * ndpFindNeighborCacheEntry(NetInterface *interface, const Ipv6Addr *ipAddr)
Search the Neighbor cache for a given IPv6 address.
Definition: ndp_cache.c:154
NdpDestCacheEntry * ndpFindDestCacheEntry(NetInterface *interface, const Ipv6Addr *destAddr)
Search the Destination Cache for a given destination address.
Definition: ndp_cache.c:503
void ndpFlushQueuedPackets(NetInterface *interface, NdpNeighborCacheEntry *entry)
Flush packet queue.
Definition: ndp_cache.c:409
NdpNeighborCacheEntry * ndpCreateNeighborCacheEntry(NetInterface *interface)
Create a new entry in the Neighbor cache.
Definition: ndp_cache.c:72
void ndpChangeState(NdpNeighborCacheEntry *entry, NdpState newState)
Update Neighbor cache entry state.
Definition: ndp_cache.c:53
void ndpUpdateNeighborCache(NetInterface *interface)
Periodically update Neighbor cache.
Definition: ndp_cache.c:187
NdpDestCacheEntry * ndpCreateDestCacheEntry(NetInterface *interface)
Create a new entry in the Destination Cache.
Definition: ndp_cache.c:452
Neighbor and destination cache management.
void ndpUpdateNextHop(NetInterface *interface, const Ipv6Addr *unreachableNextHop)
Update next-hop field of Destination Cache entries.
Definition: ndp_misc.c:554
Helper functions for NDP (Neighbor Discovery Protocol)
TCP/IP stack core.
#define NetInterface
Definition: net.h:36
void netBufferFree(NetBuffer *buffer)
Dispose a multi-part buffer.
Definition: net_mem.c:282
size_t netBufferGetLength(const NetBuffer *buffer)
Get the actual length of a multi-part buffer.
Definition: net_mem.c:297
NetInterface * nicGetPhysicalInterface(NetInterface *interface)
Retrieve physical interface.
Definition: nic.c:84
@ NIC_TYPE_ETHERNET
Ethernet interface.
Definition: nic.h:83
#define osMemset(p, value, length)
Definition: os_port.h:135
#define timeCompare(t1, t2)
Definition: os_port.h:40
#define TRUE
Definition: os_port.h:50
#define FALSE
Definition: os_port.h:46
systime_t osGetSystemTime(void)
Retrieve system time.
uint32_t systime_t
System time.
Destination cache entry.
Definition: ndp.h:567
systime_t timestamp
Timestamp to manage entry lifetime.
Definition: ndp.h:571
Ipv6Addr destAddr
Destination IPv6 address.
Definition: ndp.h:568
Neighbor cache entry.
Definition: ndp.h:549
systime_t timestamp
Timestamp to manage entry lifetime.
Definition: ndp.h:554
Ipv6Addr ipAddr
Unicast IPv6 address.
Definition: ndp.h:551
NdpQueueItem queue[NDP_MAX_PENDING_PACKETS]
Packets waiting for address resolution to complete.
Definition: ndp.h:557
MacAddr macAddr
Link layer address associated with the IPv6 address.
Definition: ndp.h:552
NdpState state
Reachability state.
Definition: ndp.h:550
uint_t retransmitCount
Retransmission counter.
Definition: ndp.h:556
uint_t queueSize
Number of queued packets.
Definition: ndp.h:558
systime_t timeout
Timeout value.
Definition: ndp.h:555
NDP queue item.
Definition: ndp.h:536
NetInterface * srcInterface
Interface from which the packet has been received.
Definition: ndp.h:537
NetBuffer * buffer
Packet waiting for address resolution.
Definition: ndp.h:538
size_t offset
Offset to the first byte of the packet.
Definition: ndp.h:539
NetTxAncillary ancillary
Additional options.
Definition: ndp.h:540
uint8_t length
Definition: tcp.h:368